#26 RTOS Part-5: What is "real-time"? Preemptive, priority-based scheduling

Summary

This video explores the fundamentals of real-time priority-based scheduling in operating systems, focusing on the importance of thread blocking and priority assignment. It introduces the Rate-Monotonic Scheduling (RMS) method, where higher-priority threads are assigned to tasks with shorter periods, ensuring real-time deadlines are met. The video highlights the concept of CPU utilization and explains how a scheduler can be proven to meet deadlines when the total CPU utilization is below a specific threshold. It also previews upcoming lessons on commercial RTOSes and inter-thread synchronization.

Takeaways

• 😀 Blocking is essential in a priority-based scheduler. A high-priority thread must block to allow lower-priority threads to run.
• 😀 Without blocking, lower-priority threads will never execute in a priority-based scheduler.
• 😀 The round-robin scheduler executes all threads in succession, regardless of blocking, while a priority-based scheduler requires blocking for lower-priority threads to run.
• 😀 The most important decision when working with a priority-based scheduler is how to assign priorities to threads.
• 😀 Threads with shorter periods (and deadlines) should be assigned higher priorities to meet real-time deadlines.
• 😀 The Rate-Monotonic Scheduling (RMS) method assigns higher priorities to threads with shorter periods, and it is mathematically proven to meet deadlines under certain conditions.
• 😀 In RMS, the CPU utilization of a thread is calculated as the ratio of execution time to period, and the total CPU utilization must be below a theoretical bound to guarantee deadline fulfillment.
• 😀 If the total CPU utilization is below 70% (for many threads), the system will be schedulable and meet all deadlines.
• 😀 RMA/RMS guidelines include assigning priorities monotonically, calculating individual thread utilization, and ensuring the total utilization is below the theoretical bound.
• 😀 Preemptive priority-based scheduling allows higher-priority threads to preempt lower-priority threads, ensuring hard real-time requirements are met.
• 😀 Preemptive scheduling is the norm in real-time systems today, and most modern Real-Time Operating Systems (RTOS) support it.

Q & A

What is the primary purpose of a priority-based scheduler in real-time systems?

The primary purpose of a priority-based scheduler is to ensure that threads with higher priorities are given CPU time before lower-priority threads, allowing the system to meet real-time deadlines efficiently.

Why is blocking an essential concept in a priority-based scheduler?

Blocking is crucial because it allows a high-priority thread to voluntarily relinquish the CPU, giving lower-priority threads a chance to run. Without blocking, lower-priority threads would never get CPU time.

How does the priority of threads affect scheduling in a real-time system?

Threads with shorter periods (or deadlines) should be assigned higher priorities. This ensures that they meet their deadlines, as threads with higher priorities preempt lower-priority threads.

What is the 'Rate-Monotonic Analysis' (RMA), and how is it applied in priority-based scheduling?

Rate-Monotonic Analysis (RMA) is a method for assigning priorities to threads based on their execution rates. Threads with shorter periods (higher rates) are given higher priorities. This method ensures that all threads meet their deadlines, given certain conditions.

What is the utilization bound in RMA, and why is it important?

The utilization bound in RMA is a theoretical limit that ensures all threads meet their deadlines. If the total CPU utilization is below this bound, typically 70%, the set of threads is schedulable. This bound ensures efficient use of the CPU while avoiding overload.

How is CPU utilization calculated for each thread in a priority-based system?

CPU utilization for each thread is calculated as the ratio of the thread's execution time to its period. This gives a measure of how much CPU time each thread needs within its cycle.

What is the total CPU utilization for the Blinky1 and Blinky2 threads, and does it meet the utilization bound?

The total CPU utilization for Blinky1 (1.2ms/2ms) and Blinky2 (3.6ms/54ms) is 66.6%, which is below the theoretical utilization bound of 70%. Therefore, the threads are schedulable and will meet their deadlines.

What does it mean for a function to be 'monotonic' in mathematics, and how does this concept apply to RMA?

A function is called monotonic when it preserves or reverses the order between two ordered sets. In the case of RMA, thread priorities are assigned in a monotonic fashion, meaning threads with higher rates (shorter periods) have higher priorities.

How does preemptive priority-based scheduling decouple threads in the time domain?

Preemptive priority-based scheduling allows high-priority threads to immediately preempt lower-priority threads. This decouples threads in the time domain, ensuring that high-priority threads are unaffected by the execution times or periods of lower-priority threads.

What is the significance of the 1973 paper by C.L. Liu and James W. Layland on real-time scheduling?

The 1973 paper by Liu and Layland introduced the foundational concepts of Rate-Monotonic Scheduling (RMS) and provided mathematical proofs that a static priority-based scheduler could meet all hard-real-time deadlines, given certain conditions. This paper revolutionized real-time scheduling and remains crucial in modern real-time systems.