Transcript Class 8
ELN5622 Embedded Systems Class 8 Spring, 2003 Aaron Itskovich [email protected] Overview Operating Systems vs. Executives Real-Time Operating Systems Desirable Attributes Examples Operating Systems vs. Executives Desktop Systems – – – – General purpose Deep functionality Generous resources Multiple I/O channels Embedded Systems – – – – Special purpose Limited functionality Limited resources Single I/O channel Operating Systems vs. Executives (cont.) So, why do we need an OS? – Well, we don't, always But... – The natural decomposition of a system might involve multiple tasks (threads) – Abstracting-out hardware dependencies allows us to run on multiple or one processors without or with small changes in application software – Fast embedded processors are getting cheap Operating Systems vs. Executives (cont.) Real-Time Operating Systems A Real-Time OS (RTOS) means: – Upper-bound on response time to external events • e.g., interrupts, timer – Fast context switch time Hard real-time – Missed deadline causes system malfunction (e.g., plane crashes, assembly line stops) Soft real-time – Missed deadline causes system degradation (Not so bad for example might drop a few frames of video) Real-Time Operating Systems (cont.) Preemptable kernel – Longest path through the kernel is short – Interrupts are not disabled for a long time POSIX – Portable Operating System Interface (Unix) – Standard API for real-time Oss Process – Unit of resource allocation Thread – Unit of scheduling Context Switches Pseudo-Parallelism – Threads run concurrently Steps: – – – – Choose a thread to run Save current context (PC, registers, MMU info) Load new context Run A context switch between sibling threads is cheaper than for non-sibling threads Scheduling Meeting deadlines requires preemption – FIFO scheduling – Round-robin scheduling – Preemptive-priority scheduling 2 Ready Running 3 1 Waiting 4 1: Preempted 2: Scheduled 3: Wait (e.g., I/O) 4: Signal (e.g., I/O complete) FIFO Scheduling Thread runs until it voluntarily gives up CPU – Cooperative scheduling – To do I/O FIFO Scheduling (cont.) P0 0 Process Burst Time P0 P1 P2 P3 7 15 6 3 P1 7 P2 2 2 P3 28 31 Round-Robin Scheduling Each thread runs for a given timeslice CPU does a context switch after timeslice expires Fair scheduling policy Round-Robin Scheduling (cont.) P0 0 Process Arrival Time Burst Time P0 P1 P2 P3 0 1 2 3 7 15 6 3 P1 4 P2 8 P3 12 P0 15 P1 18 P2 22 24 P1 31 *Assume timeslice = 4 Preemptive-Priority Scheduling Each thread has a priority OS guarantees highest priority thread always runs OS takes CPU from a running, lower-priority thread 0 P1 1 P5 2 P3 ... 63 Pidle P4 P0 P2 Preemptive-Priority Scheduling (cont.) P0 0 Process Arrival Time P0 P1 P2 P3 0 1 2 3 P2 2 7 15 6 3 P3 8 Burst Time Priority P0 11 3 4 1 2 P1 16 31 Measures of OS Performance The main measures of OS performance – – – – – Size of OS footprint Interrupt latency Context switch time Hardware supported Memory protection support Measures of OS Performance (cont.) Interrupt service time Interrupt Occurs Interrupt Handler Runs Interrupt Handler Finishes Interrupted Process Continues Execution time Til Til Tint Tiret Tint Tiret Interrupt Latency Interrupt Processing Time Interrupt Termination Time Measures of OS Performance (cont.) Context switch time – QNX Neutrino Processor Speed (MHz) Context Switch (µsec) 7400 G4 PowerPC 460 0.6 R527X MIPS 166 2.3 AMD-K-1 555 0.6 SH-4 200 1.9 SA-1110 StrongARM 207 1.8 Communicating processes Despite process abstraction, different computations (processes) sometimes want to communicate. Communication can increase the modularity and robustness of programs – (one process for each action, the application can continue if one of the sub processes fails) Communicating processes (cont) Shared memory as a way of communication between processes – processes all have access to a shared are of memory where one process can change a vari-able that can be seen by all other processes. – How to deal with racing conditions? Process 1 Shared Memory Process 2 Race conditions An atomic action is an indivisible action an action taken by a process than cannot be interrupted by a context switch. When accesses to a shared variable are not atomic, call it a race condition. Race condition example shared int x =3; process_1 () { x =x +1; print x; Note } that although x process_2 () { x =x +1; print x; =} x +1 looks like one statement, it probably compiles into at least 2 and probably three machine instructions. A likely translation is: LOAD r1<-x ADD r1+1->r1 STORE r1->x Race condition example(cont) Process 1 Process 2 variable 4 5 5 5 4 5 4 4 4 If the program is controlling radiation therapy, maybe somebody's life at risk. Critical section Only code that is manipulating shared data needs to worry about them. Sections of code that are accessing shared data are called critical sections or critical regions Ensure that only one process is ever executing code in the critical section (Mutual exclusion – Mutex) Mutual exclusion Simple and Wrong int flag; void enter_region(int process) { while ( flag == 1 ); flag = 1; } void leave_region(int process) { flag = 0; } Alteration int turn; void enter_region(int process) { while ( turn != process ) ; } void leave_region(int process) { int other = 1 - process; turn = other; } Dekker’s Algorithm int favored_process; int interested[2]; void enter_region(int process) { int other = 1-process; interested[process] = TRUE; while ( interested[other] ) { if ( favored_process == other ) { interested[process] = FALSE; while ( favored_process == other ); interested[process] = TRUE; } } } void leave_region(int process) { int other = 1 - process; favored_process = other; interested[process] = FALSE; } Hardware assistance Disable interrupts – Breaks process isolation – Turning off interrupts for any period of time is extremely hazardous. test-and-set instruction, which makes testing a flag and resetting it’s value an atomic action. Resource contention and resource access control Resources, Resource Access, and How Things Can Go Wrong: The Mars Pathfinder Incident Resources, Critical Sections, Blocking Priority Inversion, Deadlocks Nonpreemptive Critical Sections Priority Inheritance Protocol Priority Ceiling Mars Pathfinder Incident Landing on July 4, 1997 “experiences software glitches” Pathfinder experiences repeated Resets after starting gathering of metrological data. Resets generated by watchdog process. Timing overruns caused by priority inversion. Priority inversion How to solve priority inversion Priority inheritance – Priority Inheritance means that when a thread waits on a mutex owned by a lower priority thread, the priority of the owner is increased to that of the waiter. Ceiling protocol – Priority Ceiling means that while a thread owns the mutex it runs at a priority higher than any other thread that may acquire the mutex – A beneficial feature of the priority ceiling solution is that tasks can share resources simply by changing their priorities, thus eliminating the need for semaphores Deadlock In case you are using more than one mutex you can get deadlock Mailboxes Known Memory Location with Key – Post - write to the location – Pend - read from the location Scheduler allows Post and Pend operations If no key in the mailbox, the task blocks Accept or Check operation - don’t block if no key Scheduler checks for keys and unblocks tasks Mailbox Interrupt may force this (no busy waiting) Links Embedded Operating System Links: http://www.vxworks.com/ http://www.qnx.com/ http://www.lynxos.com/ http://www.embedded-linux.org/ http://www.embeddedlinux.com/ http://www.mentor.com/embedded/vrtxos/ Lab Load the “echo” program to the evaluation board.