Last Time Real-time scheduling using cyclic executivesToday Real-time scheduling using prioritiesReal-Time Review 1 Motivation Your car’s engine control CPU overloads → BAD Airplane doesn’t update flaps on time → BAD System contains n periodic tasks T1, … , TnTis specified by (P, C, D)Tiis specified by (Pi, Ci, Di) P is period C is execution cost (also called E) D is relative deadline Task Ti is “released” at start of period, executes for Citime units, must finish before Ditime units have passed Often Pi=Di, and in this case we omit DiReal-Time Review 2 Given: A set of real-time tasks A scheduling algorithm Is the task set schedulable? Yes → all deadlines met, foreverNo→ at some point a deadline might be missedNo→ at some point a deadline might be missed Ways to schedule Cyclic executive Static priorities Dynamic priorities …Cyclic Exec. Vs. Prioritiestaskscyclic scheduleexecutive processorCyclic exec.Design time Run timetaskspriority queueprocessorPriority driven Priorities are more flexible but less predictable Priorities may be fixed at design time or computed at runtimeToday’s Assumptions Tasks are running on an RTOS Each task runs in its own preemptive thread Scheduled using priorities Uniprocessor embedded system If system has multiple processors we analyze them separatelyseparately• This works unless we want tasks to migrate between processors Tasks don’t synchronize using locks Later we’ll see how to avoid this assumption No OS overhead Later we’ll see how to avoid this assumptionHow to assign priorities? Rate monotonic (RM) Shorter period tasks get higher priority Deadline monotonic (DM) Tasks with shorter relative deadlines get higher priority Both RM and DM…  Have good theoretical properties Work well in practice Other considerations Criticality Output jitter requirementExample System with 4 tasks: T1= (4,1), T2= (5, 1.8), T3= (20, 1), T4= (20, 2) What is the RM priority assignment?What is the DM priority assignment?What is the DM priority assignment? Will these priority assignments work? Remember: “work” means no deadlines missed, everHow about dynamic priorities? Dynamic priority means that priorities are not fixed at design time – the system can keep changing them as it runs Example algorithms Earliest deadline first (EDF) Least slack time first (LST) First-in first-out (FIFO) Last-in first-out (LIFO) Which of these work, for the example from the previous slide?Utilization Utilization of a task: C / P Utilization of a task set: Sum of task utilizations Schedulable utilization of a scheduling algorithm: Every set of periodic tasks with utilization less or equal than the schedulable utilization of an algorithm can be feasibly scheduled by that algorithmscheduled by that algorithm Higher schedulable utilization is better Schedulable utilization is always ≥ 0.0 and ≤ 1.0 Question: What is the schedulable utilization of…  FIFO scheduling? EDF scheduling? Generic fixed priority scheduling? RM scheduling?FIFO Schedulable Utilization UFIFO= 0.0 Oops! Proof Pick a utilization u Pick an arbitrary period pCreate a task set with two tasksCreate a task set with two tasks• Task 1 has C = p * u/2, P = p (utilization = u/2)• Task 2 has C = p, P = p * 2/u (utilization = u/2) This task set has utilization u and is not schedulableC1C2P2P1EDF Schedulable Utilization UEDF= 1.0 As long as we ignore synchronization between tasks We’ll return to this result laterFixed PrioritySchedulable Utilization UFP= 0C1C2P2P1 URM= ? URM≠ 0 URM≠ 1 T1T21)5,5.2,5()2,1,2(221121≤ 100 %=+===pepeUTTDeadline miss!Simply Periodic Case A set of tasks is simply periodic if, for every pair of tasks, one period is multiple of other period Result: A system of simply periodic, independent, preemptible tasks whose relative deadlines are equal to their periods is schedulable according to RM iff their total utilization does not exceed 1.0their total utilization does not exceed 1.0 Proof: Assume Timisses deadline at time t t is integer multiple of Piand Then, total time to complete jobs with deadline t is:  Tican only miss deadline if U > 1.0,ikkppp<<<<∀∀∀∀∑∑∑∑∑∑∑∑========⋅⋅⋅⋅====⋅⋅⋅⋅====⋅⋅⋅⋅ikkkiikkkpetUtpet11General RM Case Theorem n independent, preemptible, periodic tasks with Di=Pican be feasibly scheduled by RM if its total utilization U is less or equal to For n=1, U = 1.0For n=2, U ≈ 0.83)12(1−−−−nnFor n=2, U ≈ 0.83 For n=∞, U ≈ 0.69RM Proof Sketch General idea Find the most-difficult-to-schedule system of n tasks among all difficult-to-schedule systems of n tasks Difficult-to-schedule Fully utilizes processor for some time intervalAny increase in execution time would make system Any increase in execution time would make system unschedulable Most-difficult-to-schedule System with lowest utilization among difficult-to-schedule systems Difficult-to-schedule situations happen when all tasks are released at once• First prove that this is the most difficult case• Then prove that in this case, the system is schedulableSummary Fixed priority scheduling Not optimal – So why do we care? Simple Efficient  Easy to implement on standard RTOSsPredictable –During overload low-priority jobs losePredictable –During overload low-priority jobs lose Fixed priority scheduling is heavily used in real embedded