Real-Time Scheduling Algorithms in Operating Systems
Explore real-time scheduling algorithms like Rate Monotonic (RM) and Earliest Deadline First (EDF) in operating systems. Learn how these algorithms prioritize tasks to meet deadlines in a timely and efficient manner. Discover the importance of task modeling and the challenges of ensuring tasks complete within their deadlines. Find out how RM and EDF can guarantee task completion and examine the concept of hyperperiod in determining feasibility.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Real-Time Scheduling David Ferry CSCI 3500 Operating Systems Saint Louis University St. Louis, MO 63103 1
Real-Time Problem Domain Real-time is not real fast Some problems require high predictability and reliability, e.g. sense-compute-actuate loop at 10-1000Hz Cyber Physical Gather Sensor Data Sensors Compute Response Actuators Send Actuator Commands CSCI 3500 - Operating Systems 2
Real-Time Task Model Multiple tasks, each with: Periodic rate, T Worst-case execution time, C Deadline relative to release time, D Note: There is no advantage to completing a job early! Task Period, T WCET, C Deadline, D A 3 1 3 B 5 3 5 A A A A A B B B B B B B B B 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 CSCI 3500 - Operating Systems 3
Rate Monotonic (RM) Algorithm Preemptive Rate Monotonic The task with the shortest period always executes as highest priority. A A A A A B B B B B B B B B A B B A B B A B B A B B A B 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 CSCI 3500 - Operating Systems 4
Earliest Deadline First (EDF) Preemptive Earliest Deadline First The task with the next deadline always executes as highest priority. A A A A A B B B B B B B B B A B B B A B A B B A B B B A 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 CSCI 3500 - Operating Systems 5
Earliest Deadline First (EDF) Preemptive Earliest Deadline First The task with the next deadline always executes as highest priority. A A A A A B B B B B B B B B A B B B A B A B B A B B B A EDF A B B A B B A B B A B B A B RM CSCI 3500 - Operating Systems 6
Real-Time Scheduling Problem Given a set of tasks, does a particular scheduling algorithm guarantee they will all get enough time to complete by their deadline, and how do we prove it? Here we can prove that RM and EDF work for this particular task set with an appeal to the hyperperiod... Is there a better way? What if hyperperiod was large? Restart A B B B A B A B B A B B B A EDF A B B A B B A B B A B B A B RM 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 CSCI 3500 - Operating Systems 7
Schedulablity Tests RM and EDF are common names because they have rigorously proven schedulability tests that make it easy to decide whether they can schedule a task set or not. These are usually sufficient but not necessary. If a task set meets the criteria then we know it can be scheduled, but if it doesn t meet the criteria we don t know that it can t be scheduled. For RM and EDF these tests are utilization bounds. CSCI 3500 - Operating Systems 8
Utilization The utilizationof a task is it s execution requirement divided by its period. I.e. Ui = Ci / Ti so for example: Task Period, T WCET, C Deadline, D Utilization A 3 1 3 0.333 B 5 3 5 0.6 The utilization of a task set is the sum all utilizations in the task set. CSCI 3500 - Operating Systems 9
RM & EDF Utilization Bounds Liu and Layland (1973) proved that a set of n tasks is schedulable under RM if: U = Ci / Ti n(21/n 1) Or for large n: U 0.69 Xu and Parnas (1990) proved a set of tasks is schedulable under EDF if: U = Ci / Ti 1 CSCI 3500 - Operating Systems 10
Sufficiency vs. Necesscity Schedulability tests are only sufficient, not necessary: E.g.: Utilization of this task set is 0.933 Task Period, T WCET, C Deadline, D Utilization A 3 1 3 0.333 B 5 3 5 0.6 A B B A B B A B B A B B A B RM Schedulability bound from last slide for n=2: U n(21/n 1) = 2*( 2 - ) = 0.83 CSCI 3500 - Operating Systems 11
