Programming embedded systems: RTOS – what is real-time?

This fifth lesson on RTOS finally addresses the real-time aspect of the “Real-Time Operating System” name. Specifically, in the video lesson 26, you add a preemptive, priority-based scheduler to the MiROS RTOS [4], allowing you to mathematically prove that certain sets of threads can always meet all their real-time deadlines.

Lesson 26 – RTOS Part-5: What is “real-time”? Preemptive, priority-based scheduling

What is Real-Time?

Until now, you cared only for the correctness of your code, and any computation performed was considered equally useful. “Real-Time” adds the timeliness requirement, where the usefulness of computation becomes a function of time. In the so-called “hard real-time systems,” a computation is useful from the triggering event to the deadline. After the deadline, the usefulness of the computation becomes negative, which means that a missed deadline represents a system failure. For example, deploying an airbag too late is disastrous.

But there are also “soft real-time systems,” where timeliness is also important, but the deadline is not as firm. For example, a text message is expected to be delivered somewhat timely, say within 20 seconds. But it is still useful for much longer, although its usefulness diminishes with time.

Periodic Threads

As observed already in the 1960s, most real-time systems operate periodically. For example, landing a spacecraft on the lunar surface required corrections to the rocket thrusters that the onboard Apollo Guidance Computer (AGC) [1] had to perform every few milliseconds. Similarly, industrial processes require periodic control ranging from milliseconds to tens of seconds.

Thread Priorities

The round-robin scheduler you have used so far switches the CPU to a different thread at every clock tick. But in hard real-time systems, you don’t care about the fairness in access to the CPU. Instead, you need a different scheduler that allows threads to meet their deadlines.

For example, the Blinky1 thread in the video must run every 2ms, and missing even one of these deadlines is considered a catastrophic failure. In that case, the scheduler must “know” that Blinky1 has a higher priority than Blinky2.

Preemptive, Priority-Based Scheduler

One of the simplest schedulers that consider thread priorities is the preemptive, priority-based scheduler with static priorities. The scheduler always runs the highest-priority thread ready to run.

The most important decision you face when working with the priority-based scheduler is how to assign priorities to your threads. With just two threads, like your Blinky1 and Blinky2, you have only two possibilities. The video shows that assigning higher priority to Blinky1 than Blinky2 meets the real-time deadlines of both threads, while the other possibility immediately fails.

Rate-Monotonic Scheduling

The rule that emerges here is to assign higher priorities to threads with shorter periods (i.e., higher rates). This rule was discovered in 1973 when Liu and Layland published a seminal paper [2]. The method was later generalized and called “Rate-Monotonic Analysis” (RMA) or “Rate-Monotonic Scheduling” (RMS) [3].

In the RMA/RMS method, you need to know the CPU utilization of each thread, which you calculate as the ratio between the measured execution time Cn to the period Tn. For example, the Blinky1 thread in the video has the execution time C1=1.2ms, period T1=2ms, and utilization U1=1.2/2=0.6 (60%). Similarly, Blinky2 has C2=3.6ms, T2=54ms, and U2=3.6/54=0.066 (6.6%).

You then calculate the total CPU utilization as the sum of all individual CPU utilization terms. If this total is below the theoretical bound (worst case ln(2)=0.69 for the infinite number of threads), all threads in the set are guaranteed to meet their deadlines. For Blinky1 and Blinky2 in the video, the total CPU utilization is 0.66, which is below the theoretical bound, and consequently, such a set of threads is “schedulable.”

End Notes

RMA/RMS is the main reason the preemptive, priority-based schedulers became the norm and are supported in most RTOS kernels.

Due to its simplicity, the priority-based scheduler is straightforward, and the video lesson shows how to implement it quite efficiently in the MiROS RTOS [4].

In the next lesson, you’ll advance by another decade from the 1970s to the 1980s, when the commercial RTOSes went mainstream and inter-thread synchronization and communication mechanisms were added. Stay tuned!

[1] “Apollo Guidance Computer Explained,” History Computer

[2] C.L.Liu and James W. Layland, “Scheduling Algorithms for Multiprogramming in Hard-Real-Time Environment,” Journal of the ACM 20(1):46-61, 1973

[3] Lui Sha Mark H. Klein John B. Goodenough, “Rate Monotonic Analysis for Real-Time Systems” Technical Report CMU/SEI-91-TR-6 ESD-91-TR-6, 1991

[4] Miro Samek, MiROS (MInimal Real-Time Operating System), GitHub

Dr. Miro M. Samek is the creator of the open source QP real-time embedded frameworks and the freeware QM graphical model-based design tool. He is also the founder and CEO of Quantum Leaps — the provider of modern embedded software based on active objects and hierarchical state machines as well as tools for visual modeling, automatic code generation, and unit testing of deeply embedded software. Miro teaches the popular YouTube “Modern Embedded Systems Programming” video course on which this article series is based.

Related Contents:

• Programming embedded systems: What is a Real-Time Operating System?
• Programming embedded systems: RTOS – automating the context switch
• Programming embedded systems: RTOS – automating scheduling
• PX5: a new RTOS for real-time multithread scheduling