嵌入式操作系统.ppt

《嵌入式操作系统.ppt》由会员分享，可在线阅读，更多相关《嵌入式操作系统.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Ch4 Process and Operating System,Content,Motivation for processesThe process abstractionContext switching and MultitaskingOperating SystemScheduling policies:RMS;EDF.Interprocess communication.,Multi-task System,Multiple tasksmanage timing complexity:multiple ratesmultimediaautomotiveasynchronous in

2、putuser interfacescommunication systems,Life without processes,Code turns into a mess:interruptions of one task for anotherspaghetti code,time,A,B,C,A,C,A_code();B_code();if (C) C_code();A_code();switch (x) case C: C(); case D: D(); .,Co-routines,ADR r14,co2aco1a ADR r13,co1bMOV r15,r14co1b ADR r13,

3、co1cMOV r15,r14co1c .,co2a ADR r14,co2bMOV r15,r13co2b ADR r14,co2cMOV r15,r13co2c ,Co-routine 1,Co-routine 2,Co-routine methodology,Like subroutine, but caller determines the return address.Co-routines voluntarily give up control to other co-routines.Pattern of control transfers is embedded in the

4、code.,Foreground/background system,又称超循环系统(super loops)应用程序是一个无限循环，循环中调用相应的函数完成相应的操作，可以看作后台行为(任务级)；中断服务程序处理异步事件，可以看作前台行为(中断级)。,Processes,A process is a unique execution of a program.Several copies of a program may run simultaneously or at different times.A process has its own state:registers;memory.

5、The operating system manages processes.,Processes and CPUs,Activation record: copy of process state.Context switch:current CPU context goes out;new CPU context goes in.,CPU,PC,registers,process 1,process 2,.,memory,Terms,Thread = lightweight process: a process that shares memory space with other pro

6、cesses.Reentrancy: ability of a program to be executed several times with the same results.,可重入函数,可重入函数：可以被多个进程同时调用不必担心数据破坏的函数。两种情况：只使用局部变量，即变量保存在寄存器或堆栈中；使用全局变量，则对全局变量进行保护,Examples,Processes in POSIX,Create a process with fork:parent process keeps executing old program;child process executes new pro

7、gram.,process a,process a,process b,fork(),The fork process creates child:childid = fork();if (childid = 0) /* child operations */ else /* parent operations */,execv(),Overlays child code:childid = fork();if (childid = 0) execv(“mychild”,childargs);perror(“execv”);exit(1);,file with child code,Conte

8、xt switching,Who controls when the context is switched?How is the context switched?,Co-operative multitasking,Improvement on co-routines:hides context switching mechanism;still relies on processes to give up CPU.Each process allows a context switch at cswitch() call.Separate scheduler chooses which

9、process runs next.,Problems with co-operative multitasking,Programming errors can keep other processes out:process never gives up CPU;process waits too long to switch, missing input.,Preemptive multitasking,Most powerful form of multitasking:OS controls when contexts switches;OS determines what proc

10、ess runs next.Use timer to call OS, switch contexts:,CPU,timer,interrupt,Flow of control with preemption,time,P1,OS,P1,OS,P2,interrupt,interrupt,Preemptive context switching,Timer interrupt gives control to OS, which saves interrupted processs state in an activation record.OS chooses next process to

11、 run.OS installs desired activation record as current CPU state.,Context switching,Must copy all registers to activation record, keeping proper return value for PC.Must copy new activation record into CPU state.,Context switching in ARM,Save old process:STMIA r13,r0-r14MRS r0,CPSRSTMDB r13,r0,r15,St

12、art new process:ADR r0,NEXTPROCLDR r13,r0LDMDB r13,r0,r14MSR CPSR,r0LDMIA r13,r0-r14MOVS pc,r14,Processes and UML,A process is an active class-independent thread of control.,processClass1,myOperations(),startresume,myAttributes,Signals,UML signals,Signal: object that is passed between processes for

13、active communication:,acomm: datasignal,Designing with active objects,Can mix normal and active objects:,p1: processClass1,master: masterClass,w: wrapperClass,a: rawMsg,ahat: fullMsg,Operating systems,The operating system controls resources:who gets the CPU;when I/O takes place;how much memory is al

14、located.The most important resource is the CPU itself.CPU access controlled by the scheduler.,Process state,A process can be in one of three states:executing on the CPU;ready to run;waiting for data.,executing,ready,waiting,gets dataand CPU,needsdata,gets data,needs data,preempted,getsCPU,Priority-d

15、riven scheduling,Each process has a priority.CPU goes to highest-priority process that is ready.Priorities determine scheduling policy:fixed priority;time-varying priorities.,Priority-driven scheduling example,Rules:each process has a fixed priority (1 highest);highest-priority ready process gets CP

16、U;process continues until done.ProcessesP1: priority 1, execution time 10P2: priority 2, execution time 30P3: priority 3, execution time 20,Priority-driven scheduling example,time,0,30,10,20,60,40,50,P2,P2,P1,P3,Operating system structure,OS needs to keep track of:process priorities;scheduling state

17、;process activation record.Processes may be created:statically before system starts;dynamically during execution.,Embedded vs. general-purpose scheduling,Workstations try to avoid starving processes of CPU access.Fairness = access to CPU.Embedded systems must meet deadlines.Low-priority processes ma

18、y not run for a long time.,Interprocess communication,Interprocess communication (IPC): OS provides mechanisms so that processes can pass data.Two types of semantics:blocking: sending process waits for response;non-blocking: sending process continues.,IPC styles,Shared memory:processes have some mem

19、ory in common;must cooperate to avoid destroying/missing messages.Message passing:processes send messages along a communication channel-no common address space.,Other operating system functions,I/O DeviceFile systemNetworkingSecurity,Scheduling Policies,Scheduling Policy:How to choose a ready proces

20、s to executeMetrics:Ability to satisfy all deadlines.CPU utilization-percentage of time devoted to useful work.Scheduling overhead-time required to make scheduling decision.,Rate monotonic scheduling,RMS (Liu and Layland): widely-used, analyzable scheduling policy.Analysis is known as Rate Monotonic

21、 Analysis (RMA).,RMA model,All process run on single CPU.Zero context switch time.No data dependencies between processes.Process execution time is constant.Deadline is at end of period.Highest-priority ready process runs.,RMS priorities,Optimal (fixed) priority assignment:shortest-period process get

22、s highest priority;priority inversely proportional to period;break ties arbitrarily.No fixed-priority scheme does better.,RMS Example,Page 238,Process parameters,Ti is computation time of process i; ti is period of process i.,period ti,Pi,computation time Ti,RMS CPU utilization,Utilization for n pro

23、cesses isS i Ti / tiAs number of tasks approaches infinity, maximum utilization approaches 69%.,RMS CPU utilization, contd.,RMS cannot use 100% of CPU, even with zero context switch overhead.Must keep idle cycles available to handle worst-case scenario.However, RMS guarantees all processes will alwa

24、ys meet their deadlines.,RMS implementation,Efficient implementation:scan processes;choose highest-priority active process.,Earliest-deadline-first scheduling,EDF: dynamic priority scheduling scheme.Process closest to its deadline has highest priority.Requires recalculating processes at every timer

25、interrupt.,EDF Example,Page 241,EDF analysis,EDF can use 100% of CPU.But EDF may fail to miss a deadline.,EDF implementation,On each timer interrupt:compute time to deadline;choose process closest to deadline.Generally considered too expensive to use in practice.,Fixing scheduling problems,What if y

26、our set of processes is unschedulable?Change deadlines in requirements.Reduce execution times of processes.Get a faster CPU.,Further Analysis of Modeling Assumption,Priority inversionData dependenciesContext-switching time,Priority inversion,Priority inversion: low-priority process keeps high-priori

27、ty process from running.Improper use of system resources can cause scheduling problems:Low-priority process grabs I/O device.High-priority device needs I/O device, but cant get it until low-priority process is done.Can cause deadlock.,Solving priority inversion,Give priorities to system resources.Ha

28、ve process inherit the priority of a resource that it requests.Low-priority process inherits priority of device if higher.,Data dependencies,Data dependencies allow us to improve utilization.Restrict combination of processes that can run simultaneously.P1 and P2 cant run simultaneously.,P1,P2,Contex

29、t-switching time,Non-zero context switch time can push limits of a tight schedule.Hard to calculate effects-depends on order of context switches.In practice, OS context switch overhead is small.,POSIX scheduling policies,SCHED_FIFO: RMSSCHED_RR: round-robinwithin a priority level, processes are time

30、-sliced in round-robin fashionSCHED_OTHER: undefined scheduling policy used to mix non-real-time and real-time processes.,Interprocess communication,OS provides interprocess communication mechanisms:various efficiencies;communication power.,Signals,A Unix mechanism for simple communication between p

31、rocesses.Analogous to an interrupt-forces execution of a process at a given location.But a signal is caused by one process with a function call.No data-can only pass type of signal.,POSIX signals,Must declare a signal handler for the process using sigaction().Handler is called when signal is receive

32、d.A signal can be sent with sigqueue():sigqueue(destpid,SIGRTMAX-1,sval),POSIX signal types,SIGABRT: abortSIGTERM: terminate processSIGFPE: floating point exceptionSIGILL: illegal instructionSIGKILL: unavoidable process terminationSIGUSR1, SIGUSR2: user defined,Signals in UML,More general than Unix

33、signal-may carry arbitrary data:,aSig,p : integer,someClass,sigbehavior(),POSIX shared memory,POSIX supports counting semaphores with _POSIX_SEMAPHORES option.Semaphore with N resources will not block until N processes hold the semaphore.Semaphores are given name:/sem1P() is sem_wait(), V() is sem_p

34、ost().,POSIX message-based communication,Unix pipe supports messages between processes.Parent process uses pipe() to create a pipe.Pipe is created before child is created so that pipe ID can be passed to child.,POSIX pipe example,/* create the pipe */if (pipe(pipe_ends) 0) perror(“pipe”); break; /*

35、create the process */childid = fork();if (childid = 0) /* child reads from pipe_ends1 */childargs0 = pipe_ends1;execv(“mychild”,childargs);perror(“execv”);exit(1);else /* parent writes to pipe_ends0 */ ,Evaluating performance,May want to test:context switch time assumptions;scheduling policy.Can use

36、 OS simulator to exercise process set, trace system behavior.,Processes and caches,Processes can cause additional caching problems.Even if individual processes are well-behaved, processes may interfere with each other.Worst-case execution time with bad behavior is usually much worse than execution time with good cache behavior.,