Lecture 7 Real Time Task SchedulingReal TimeSlide 3Five Characteristics of Real-Time Operating SystemsSystem Modeling in RT SchedulingReal time scheduling: Periodic system modelSlide 7System Model - Assumptions and NotationNon-Repeating ScheduleSchedule ExampleReal-Time Scheduling PoliciesPeriodic tasks: ExampleTime Line Scheduling (Cyclic Scheduling)Execution time based prioritySlide 15QuestionsRate monotonic schedulingRate Monotonic SchedulingPowerPoint PresentationSlide 20Example of Rate Monotonic SchedulingCritical Instant of J3Release J1 EarlierRelease J1 LaterRMS is Optimal…Value of the threshold factorPriority InversionPriority inversion: ExampleExample ContinuedPriority Ceiling ProtocolDeadline SchedulingExample of Deadline Scheduling (cont.)Earliest Deadline First AlgorithmEarliest Deadline First (EDF) AlgorithmSlide 35Slide 36Slide 37EDF SchedulingComparison of EDF and Rate Monotonic SchedulingContext switches : EDF & Rate MonotonicProcessor Utilizations : EDF & Rate MonotonicSlide 42Scheduling of Periodic Dependant tasksExamples of synchronisation protocols:Preemptive vs. Non preemptive schedulingLecture 7Lecture 7Real Time Task SchedulingReal Time Task SchedulingForrest BrewerReal TimeReal TimeANSI defines real time as “A Real time process is a process which delivers the results of processing in a given time span”–A data may require processing at a priori known point in time, or it may be demanded without any priori knowledgeCorrectness of computationDeadlines (latest acceptable time)–Soft deadline•Diminished functionality as deadlines are missed•System does not ‘fail’–Hard deadline•System fails (X-29 wings fall off…)Real TimeReal TimeProcessing guarantees for time-critical applications:–Predictably fast response to time-critical events & accurate timing information•Jitter issues–High degree of schedulability•High degree of resource utilization below which the processing guarantee is a question…–Stability under transient overload•Under system overload, critical jobs processing of must be ensured•Priority Scheme, process preemption–Sharing of Resources•Management of Arbitration–Low OverheadFive Characteristics of Real-Time Five Characteristics of Real-Time Operating SystemsOperating SystemsDeterminism: concerned with how long an operating system delays before acknowledging an event Responsiveness: concerned with how long after acknowledgment, it takes an operating system to finish the event (interrupt) serviceDeterminism and responsiveness together make up the response time to external events which are crucial for real-time systems User control: allow the user (dynamic?) fine-grained control over task priority Reliability: a transient failure may cause financial loss or major equipment damage or even loss of life. Fail-soft operation: during overload, continued operation at a reduced level of serviceSystem Modeling in RT SchedulingSystem Modeling in RT Scheduling–Tasks are the schedulable unit of the system.–A task is characterized by timing constraints and resource requirements.–Periodic task (T) –processing time–deadline–periodProcessing time of TDeadline of TPeriod of TPeriodic task T0Real time scheduling: Real time scheduling: PeriodicPeriodic system modelsystem modelTask: schedulable entity–Processing of separate tasks are assumed mutually independentTiming constraints of a periodic task i is specified by (s, e, D, p)–si-(scheduled) Starting Time of Task i–ei-Processing time of i–fi-Finish time of i–Di-Deadline of i–pi-Period of i–ri-Rate of i = (1/pi)Real time scheduling: Real time scheduling: PeriodicPeriodic system modelsystem modelTasks can be –Preemptive–NonpreemptiveGuarantee ratio–Processing time used by guaranteed tasks versus total processing timeUtilization:niiipeU1System Model - Assumptions and NotationSystem Model - Assumptions and NotationAssumptions:–Periodic tasks without precedence relations•Aimed at “vertical” system decomposition–No OS overhead•time added to every task invocation•this is a problem for preemptive task models–Time Constraints (non-periodic):•C = {t1=(s1, e1, D1), t3=(s3, e3, D3), t2=(s2, e2, D2), …}Non-Repeating ScheduleNon-Repeating ScheduleiiikiiiiiiiiDfsSktsffsnitfsA&},...,1|),,{(1A schedule is a set of execution intervals s=start time of interval, f=finish time of interval,t=the task executed during the intervalA schedule is feasible if every task حk receives at least ek seconds of CPU execution in the schedulekAkfsiiiiiikesfScheduleFeasiblektAatfsaAkii )(),,( }&|),,({)(Note: a task may be segmented into several execution intervalsSchedule ExampleSchedule ExampleC={t1=(0,8,13), t2=(3,5,10), t3=(4,7,20)}–A={(0,3,t1),(3,8,t2),(8,13,t1),(13,7,t3)} is a feasible schedule•for t1, (3-0) + (13-8) = 3 + 5 = 8C={t1=(1,8,12), t2=(3,5,10), t3=(4,7,14)}–No feasible scheduleReal-Time Scheduling PoliciesReal-Time Scheduling PoliciesStatic table-driven –Suitable for periodic tasks/earliest-deadline first scheduling–Requires Static analysis of feasible scheduleStatic priority-driven preemptive  rate monotonic algorithm–Static analysis to determine priority–Traditional priority-driven scheduler is usedDynamic planning-based (evaluate priorities on the fly)–Create a schedule containing the previously scheduled tasks and the new arrival  if all tasks meets their constraints, the new one is acceptedDynamic best effort–No feasibility analysis is performed–Assigned a priority to the new arrival  then apply earliest deadline first–System tries to meet all deadlines and aborts any started process whose deadline is missedPeriodic tasks: ExamplePeriodic tasks: Examplename execution time [msec] period [msec] Deadline [msec] tsk 1 20 100 100 tsk 2 40 150 150 tsk 3 100 350 350 Suppose the tasks tsk 1…tsk 3 have the following propertiesThe tasks get assigned priorities Once assigned, these priorities do not change;The tasks are scheduled according to their priorities, i.e. a ready task with highest priority is executed until a higher priority task becomes ready. Such higher priority task then pre-empts the lower priority task.Time Line Scheduling (Cyclic Scheduling)Time Line Scheduling (Cyclic Scheduling)Time Line Scheduling (Off-line scheduling strategy)–