RTOS Scheduling – I : Rate-Monotonic TheoryReading List for This LectureComputation & Timing Model of the SystemCharacterizing the Task SetScheduling AlgorithmAssigning Priorities to TasksDeriving Optimum Priority Assignment RuleCritical Instant for a TaskCritical Instant for a Task (contd.)When does Critical Instant occur for a task?ExampleExample (contd.)ObservationObservation (contd.)A Possible Rule for Priority AssignmentProcessor UtilizationHow Large can U be for a Fixed Priority Scheduling Algorithm?Utilization Factor for Rate-Monotonic Priority AssignmentTwo Tasks CaseTwo Tasks Case (contd.)Slide 21Slide 22General CaseGeneral Case (contd.)Theorem 1 RecalledExample #1Example #2Example #2 (contd.)Response Time Analysis for RMResponse Time Analysis (contd.)Slide 31AlgorithmRM SchedulabilityRM Schedulability (contd.)Slide 35Slide 36Deadline Monotonic Priority Assignment (DMP)RM in Distributed/Networked Embedded Systems?Can one do better?Transient OverloadDealing with Transient OverloadSlide 42A Better Approach: Period TransformationUsing Period Transformation to Improve SchedulabilitySporadic TasksHandling Sporadic Tasks: Approach 1Handling Sporadic Tasks: Approach 2 (Deferred Server)Slide 48Task SynchronizationPriority Inversion ExamplePriority Inversion Example (contd.)Process Interactions & BlockingExample: Priority InversionExample: Priority InheritanceResponse Time Calculations & BlockingResponse Time Calculations & Blocking (contd.)Priority Ceiling ProtocolsPriority Ceiling Protocols (contd.)Example of Priority Ceiling Protocol in OperationExample of Priority Ceiling Protocol in Operation (contd.)OCPPExample of OCPPICPPExample of ICPPOCPP vs. ICPPSchedulability Impact of Task SynchronizationSchedulability Impact of Task Synchronization (contd.)Cooperative SchedulingRelease JitterRelease Jitter (contd.)Slide 71Arbitrary DeadlinesArbitrary Deadlines (contd.)Schedulability Condition for Arbitrary DeadlinesSlide 75Arbitrary Deadlines with Release JitterMani SrivastavaUCLA - EE DepartmentRoom: 7702-B Boelter HallEmail: [email protected]: 310-267-2098WWW: http://www.ee.ucla.edu/~mbsCopyright 2001  Mani SrivastavaRTOS Scheduling – I :Rate-Monotonic TheoryEE202A (Fall 2001): Lecture #42Copyright 2001  Mani SrivastavaReading List for This LectureRequiredBalarin, F.; Lavagno, L.; Murthy, P.; Sangiovanni-Vincentelli, A.; Systems, C.D.; Sangiovanni-, A. Scheduling for embedded real-time systems. IEEE Design & Test of Computers, vol.15, (no.1), IEEE, Jan.-March 1998. p.71-82. http://ielimg.ihs.com/iel3/54/14269/00655185.pdf Sha, L.; Rajkumar, R.; Sathaye, S.S. Generalized rate-monotonic scheduling theory: a framework for developing real-time systems. Proceedings of the IEEE, vol.82, (no.1), Jan. 1994. p.68-82. 28 references. http://ielimg.ihs.com/iel1/5/6554/00259427.pdf RecommendedSha, L.; Rajkumar, R.; Lehoczky, J.P. Priority inheritance protocols: an approach to real-time synchronization. IEEE Transactions on Computers, vol.39, (no.9), Sept. 1990. p.1175-85. http://ielimg.ihs.com/iel1/12/2066/00057058.pdfOthersLiu, C.L.; Layland, J.W. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the Association for Computing Machinery, vol.20, (no.1), Jan. 1973. p.46-61. http://nesl.ee.ucla.edu/pw/ee202a/Liu73.pdfLehoczky, J.; Sha, L.; Ding, Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior. Proceedings. Real Time Systems Symposium (Cat. No.89CH2803-5), (Proceedings. Real Time Systems Symposium (Cat. No.89CH2803-5), Santa Monica, CA, USA, 5-7 Dec. 1989.) Los Alamitos, CA, USA: IEEE Comput. Soc. Press, 1989. p.166-71. http://ielimg.ihs.com/iel2/268/2318/00063567.pdf3Copyright 2001  Mani SrivastavaComputation & Timing Modelof the SystemRequests for tasks for which hard deadlines exist are periodic, with constant inter-request intervalsDeadlines consist of runnability constraints onlyeach task must finish before the next request for iteliminates need for buffering to queue tasksTasks are independentrequests for a certain task does not depend on the initiation or completion of requests for other taskshowever, there periods may be relatedRun-time for each task is constant for that task, and does not vary with timecan be interpreted as the maximum running time4Copyright 2001  Mani SrivastavaCharacterizing the Task SetSet on n independent tasks 1, 2, … n Request periods are T1, T2, ... Tn request rate of i is 1/Ti Run-times are C1, C2, ... Cn5Copyright 2001  Mani SrivastavaScheduling AlgorithmSet of rules to determine the task to be executed at a particular momentOne possibility: preemptive & priority driventasks are assigned priorities–statically or dynamicallyat any instant, the highest priority task is run–whenever there is a request for a task that is of higher priority than the one currently being executed, the running task is interrupted, and the newly requested task is startedTherefore, scheduling algorithm == method to assign priorities6Copyright 2001  Mani SrivastavaAssigning Priorities to TasksStatic or fixed approachpriorities are assigned to tasks once for allDynamic approachpriorities of tasks may change from request to requestMixed approachsome tasks have fixed priorities, others don’t7Copyright 2001  Mani SrivastavaDeriving Optimum Priority Assignment Rule8Copyright 2001  Mani SrivastavaCritical Instant for a TaskDeadline for a task = time of next request of itOverflow is said to occur at time t, if t is the deadline of an unfulfilled requestA scheduling algorithm is feasible if tasks can be scheduled so that no overflow ever occursResponse time of a request of a certain task is the time span between the request and the end of response to that task9Copyright 2001  Mani SrivastavaCritical Instant for a Task (contd.)Critical instant for a task = instant at which a request for that task will have the maximum response timeCritical time zone of a task = time interval between a critical instant & the end of the response to the corresponding request of the task10Copyright 2001  Mani SrivastavaWhen does Critical Instant occur for a task?Theorem 1: A critical instant for any task occurs whenever the task is requested simultaneously with requests of all higher priority tasksCan use this to determine whether a given priority assignment will