Scheduling Algorithms for Real‐Time Applications - 180D-FW-2024/Knowledge-Base-Wiki GitHub Wiki
Scheduling Algorithms for Real-Time Applications
Introduction
Imagine you are hanging out streaming Netflix on your laptop. For some reason, every minute or two, Netflix freezes. Your network is fast and stable, so what is going on? You suddenly remember that you left Adobe Creative Cloud running in the background. Why is a completely unused application taking priority over the one you currently interacting with? Now, imagine if your self-driving Tesla prioritized refreshing the speedometer over stopping for that pedestrian that walked in front of your car. The scheduling algorithm employed by an operating system can be a matter of life and death.
A real time operating system is one in which both the timing and functionality are critical to its correctness. This can be distinguished from a general purpose operating system, such as the one running on your phone, where correctness usually only depends on functionality (with some exceptions).
Soft and Hard Real-Time
Real-time operating systems are further classified into hard real-time and soft real-time systems. Hard real-time systems are characterized by stringent requirements for tasks to be executed at precise intervals or within a defined response time where even a slight deviation can cause the system to fail. This may include systems such as the ones controlling self-driving cars or nuclear reactors. On the other hand, soft real-time systems aim for excellent response time where the only consequence of a missed deadline is reduced performance. Soft real-time systems are much more common, as even streaming music or video is considered a soft real-time application.
Scheduling Algorithm Metrics
Scheduling algorithms are typically compared on the basis of a select few metrics, allowing the system architect to consider tradeoffs for the intended application. Useful metrics that apply to most scheduling algorithms include turnaround time, response time, and fairness. Turnaround time is the period between a task’s arrival and its completion. Response time is the period between a task’s arrival and the first time it is scheduled. Fairness is the equitable distribution of execution time among tasks. Real-time systems require the added complexity of the metrics timeliness and predictability. Timeliness accounts for how closely the system meets its timing requirements, while predictability measures the deviation in timeliness.
Scheduling Algorithms
Scheduling algorithms can be divided into two distinct groups: static scheduling and dynamic scheduling, with the latter being far more complex. A static scheduling algorithm may be used when all the tasks that will ever run (aka the system’s workload) are known at design or build time, in which case the entire order of execution of tasks is fixed according to the desired metrics. In many cases, the workload may change over time. When the workload is unknown at design or build time, a dynamic scheduling algorithm must be used. Dynamic scheduling algorithms must have well defined policies for deciding which task should be run next and how to handle overload. Preemption, or the interruption of a running task to run a higher priority task, is an additional consideration. It is evident that there are countless ways to configure a real-time scheduler. Two of the most common configurations are the Rate Monotonic (RM) and Earliest Deadline First (EDF) scheduling algorithms.
Rate Monotonic Scheduling
The Rate Monotonic scheduling algorithm implements static-priority scheduling, which is a subset of static scheduling for which each task is assigned a fixed priority. The assigned priority is dependent on the frequency that task is run, with higher frequency tasks being assigned higher priorities. RM is considered an optimal scheduling algorithm, so if a set of tasks cannot be scheduled with RM, no other fixed-priority algorithm will be able to schedule them. Shown below is the schedulability test for RM scheduling, where U is the utilization factor, C_i is the worst-case execution time for task _i, T_i is the worst-case period of task _i having a deadline of 1 period later, and n is the number of tasks. As n approaches infinite, U approaches 0.7. This means that for a large number of tasks, RM scheduling can meet all deadlines when CPU utilization is under 70%. Hard real-time systems, where every task must meet strict deadlines, frequently employ static scheduling methods like the RM algorithm due to its predictability and optimality under specific conditions.
Earliest Deadline First Scheduling
The Earliest Deadline First scheduling algorithm is a dynamic priority scheduling algorithm. The assigned priority of each task depends on the task’s deadline, with tasks having a nearer deadline being assigned higher priorities. Each time a task finishes, the priority queue is searched for the task with the next deadline. The schedulability test for EDF is shown below, where C_i is the worst-case execution time for task _i and T_i is the worst-case period of task _i having a deadline of 1 period later. EDF is also an optimal scheduling algorithm, but it can ensure deadlines are met for CPU utilization all the way up to 100%. This means that EDF can guarantee deadlines at higher loading than RM scheduling. All these factors combine to make EDF a popular choice in soft real-time systems.
Conclusion
Real-time scheduling allows computers to be used in situations that a missed deadline can mean system failure or worse. The choice of algorithm impacts how tasks are prioritized and executed, which leads to safety and performance implications. Whether it’s ensuring smooth video streaming or preventing life-threatening failures in autonomous vehicles, the choice of scheduling algorithm is integral to the system’s success.
Sources
https://en.wikipedia.org/wiki/Rate-monotonic_scheduling
https://www.cis.upenn.edu/~lee/06cse480/lec-real-time-scheduling.pdf
https://web.cs.ucla.edu/classes/fall1c/cs111/readings/realtime.html