l 1 Introduction to Embedded Systems Chapter 12: Operating Systems, Microkernels, & Scheduling Edward A. Lee Alberto Sangiovanni-Vincentelli UC Berkeley EECS 149/249A Fall 2014 Scheduling, UC Berkeley: 2 Source This lecture draws heavily from: Giorgio C. Buttazzo, Hard Real-Time Computing Systems, Springer, 2004.l 2 Scheduling, UC Berkeley: 3 Responsibilities of a Microkernel (a small, custom OS) ¢ Scheduling of threads or processes l Creation and termination of threads l Timing of thread activations ¢ Synchronization l Semaphores and locks ¢ Input and output l Interrupt handling Scheduling, UC Berkeley: 4 A Few More Advanced Functions of an Operating System – Not discussed here… ¢ Memory management l Separate stacks l Segmentation l Allocation and deallocation ¢ File system l Persistent storage ¢ Networking l TCP/IP stack ¢ Security l User vs. kernel space l Identity managementl 3 Scheduling, UC Berkeley: 5 Outline of a Microkernel ¢ Main: l set up periodic timer interrupts; l create default thread data structures; l dispatch a thread (procedure call); l execute main thread (idle or power save, for example). ¢ Thread data structure: l copy of all state (machine registers) l address at which to resume executing the thread l status of the thread (e.g. blocked on mutex) l priority, WCET (worst case execution time), and other info to assist the scheduler Scheduling, UC Berkeley: 6 Outline of a Microkernel ¢ Timer interrupt service routine: l dispatch a thread. ¢ Dispatching a thread: l disable interrupts; l save state (registers) into current thread data structure; l save return address from the stack for current thread; l determine which thread should execute (scheduling); l if the same one, enable interrupts and return; l copy thread state into machine registers; l replace program counter on the stack for the new thread; l enable interrupts; l return.l 4 Scheduling, UC Berkeley: 7 When can a new thread be dispatched? ¢ Under non-preemptive scheduling: l When the current thread completes. ¢ Under Preemptive scheduling: l Upon a timer interrupt l Upon an I/O interrupt (possibly) l When a new thread is created, or one completes. l When the current thread blocks on or releases a mutex l When the current thread blocks on a semaphore l When a semaphore state is changed l When the current thread makes any OS call • file system access • network access • … Scheduling, UC Berkeley: 8 The Focus in this Lecture: How to decide which thread to schedule? Considerations: ¢ Preemptive vs. non-preemptive scheduling ¢ Periodic vs. aperiodic tasks ¢ Fixed priority vs. dynamic priority ¢ Priority inversion anomalies ¢ Other scheduling anomaliesl 5 Scheduling, UC Berkeley: 9 Preemptive Scheduling Assume all threads have priorities ¢ either statically assigned (constant for the duration of the thread) ¢ or dynamically assigned (can vary). Assume further that the kernel keeps track of which threads are “enabled” (able to execute, e.g. not blocked waiting for a semaphore or a mutex or for a time to expire). Preemptive scheduling: l At any instant, the enabled thread with the highest priority is executing. l Whenever any thread changes priority or enabled status, the kernel can dispatch a new thread. Scheduling, UC Berkeley: 10 Rate Monotonic Scheduling Assume n tasks invoked periodically with: l periods T1, … ,Tn (impose real-time constraints) l worst-case execution times (WCET) C1, … ,Cn • assumes no mutexes, semaphores, or blocking I/O l no precedence constraints l fixed priorities l preemptive scheduling Theorem: If any priority assignment yields a feasible schedule, then priorities ordered by period (smallest period has the highest priority) also yields a feasible schedule. RMS is optimal in the sense of feasibility. Liu and Leland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,” J. ACM, 20(1), 1973.l 6 Scheduling, UC Berkeley: 11 Feasibility for RMS Feasibility is defined for RMS to mean that every task executes to completion once within its designated period. Scheduling, UC Berkeley: 12 Showing Optimality of RMS: Consider two tasks with different periods Is a non-preemptive schedule feasible? C1 T1 C2 T2l 7 Scheduling, UC Berkeley: 13 Showing Optimality of RMS: Consider two tasks with different periods Non-preemptive schedule is not feasible. Some instance of the Red Task (2) will not finish within its period if we do non-preemptive scheduling. C1 T1 C2 T2 Scheduling, UC Berkeley: 14 Showing Optimality of RMS: Consider two tasks with different periods What if we had a preemptive scheduling with higher priority for red task? C1 T1 C2 T2l 8 Scheduling, UC Berkeley: 15 Showing Optimality of RMS: Consider two tasks with different periods Preemptive schedule with the red task having higher priority is feasible. Note that preemption of the blue task extends its completion time. preempted C1 C1 Scheduling, UC Berkeley: 16 Showing Optimality of RMS: Alignment of tasks Completion time of the lower priority task is worst when its starting phase matches that of higher priority tasks. Thus, when checking schedule feasibility, it is sufficient to consider only the worst case: All tasks start their cycles at the same time. T1 C1l 9 Scheduling, UC Berkeley: 17 Showing Optimality of RMS: (for two tasks) It is sufficient to show that if a non-RMS schedule is feasible, then the RMS schedule is feasible. Consider two tasks as follows: C1 T1 C2 T2 Scheduling, UC Berkeley: 18 Showing Optimality of RMS: (for two tasks) The non-RMS, fixed priority schedule looks like this: T2 C2 C1 From this, we can see that the non-RMS schedule is feasible if and only if We can then show that this condition implies that the RMS schedule is feasible. 221TCC ≤+l 10 Scheduling, UC Berkeley: 19 Showing Optimality of RMS: (for two tasks) The RMS schedule looks like this: (task with smaller period moves earlier) T2 C2 C1 The condition for the non-RMS schedule feasibility: is clearly sufficient (though not