6a. Real-Time Operating Systems

This was written entirely with AI.

These notes cover Lecture 6a. Lecture 3’s schedulers aim at good average performance. This lecture is about systems where a late answer is a wrong answer: real-time systems. It explains what real-time means, how to describe a real-time process with three numbers, and two schedulers: rate monotonic (RM) and earliest deadline first (EDF). The past papers barely mention this lecture, so the questions below are the lecture’s quiz questions and one past-paper statement. The skill to practise is drawing an RM or an EDF schedule and checking each deadline.

How to use this page. Each section teaches one idea in a few lines, then gives the questions on it. Try each question before you open its answer. The “Exam patterns” table at the end is for the night before.

Quick reference

1. What a Real-Time System Is

A cyber-physical system is a physical system that a computer monitors and controls: cars (airbag, parking assist), aircraft, factory robots, pacemakers. They repeat three steps: sense (read the sensors), decide (run a control law), act (command the motors or valves), all within a reasonable time. What is reasonable depends on the job: milliseconds for car collision avoidance, up to a second for a pacemaker.

Real-time does not mean fast. Real-time means predictable, even in the worst case. The lecture’s picture: a man drowned in a river whose average depth was 20 cm. One deep place was enough. In the same way, a real-time system must meet its deadline every time, not on average.

A real-time system is correct only if the logical result is right and the result comes before its deadline. A late answer is a wrong answer. A real-time OS (RTOS), such as FreeRTOS or MicriumOS, is judged by timeliness: how predictably it meets deadlines. The worst case matters more than the average. Windows and Linux on PCs are time-sharing systems that aim for good average performance, so they are not real-time.

2. Describing a Real-Time Process

One process: ⟨R, C, D⟩. $R$ is the release time (when it becomes ready). $C$ is the CPU time it needs. $D$ is the relative deadline: how long after release it must finish. It needs $C$ units in the interval $[R, R + D)$, and its absolute deadline is $R + D$. Each process here has one CPU burst of length $C$.

Example: P1⟨0, 5, 10⟩ is released at 0, needs 5 units and must finish by 10. P3⟨20, 10, 30⟩ is released at 20 and must finish by 50.

Periodic process: ⟨T, C, D⟩. Real-time work repeats (sense, decide, act). A periodic process releases a new instance every period $T$: at $0, T, 2T, \ldots$. Instance $k$ is released at $kT$ and must finish by $kT + D$. Each instance is itself a real-time process ⟨R, C, D⟩. Example: P⟨10, 5, 7⟩ is released at 0, 10, 20, 30, … and each instance is due at 7, 17, 27, 37, …

Watch the order of the numbers. A single process is ⟨R, C, D⟩. A periodic process is ⟨T, C, D⟩. The first number changes meaning.

3. Why Normal Schedulers Fail

FCFS, SJF and RR do not look at deadlines. Run them on P1⟨0,20,30⟩, P2⟨0,5,10⟩, P3⟨5,10,35⟩, P4⟨20,10,30⟩, P5⟨25,5,10⟩: all three miss some deadline. Under FCFS, P1 (20 units) runs first, so P2 starts at 20 although its deadline is 10. The algorithms give urgent work no priority.

4. Real-Time Scheduling

The problem. Given periodic real-time processes, find a preemptive scheduler for one CPU that meets every deadline of every instance. Running example: P1⟨10, 6, 10⟩, P2⟨19, 4, 19⟩, P3⟨20, 2, 20⟩.

Rate monotonic (RM) is a fixed-priority scheduler: each process has one priority for all its instances. The shorter the period, the higher the priority (ties arbitrary). Here $T_1 = 10 < T_2 = 19 < T_3 = 20$, so P1 > P2 > P3.

To build an RM schedule: (1) give each process a fixed priority by period; (2) mark the release time and deadline of every instance; (3) at every moment run the released, unfinished instance of the highest-priority process (a higher-priority release preempts); (4) check every deadline.

RM can miss a deadline, because it looks only at periods. Change P3 to ⟨20, 2, 14⟩. P3 still has the lowest priority (its period is still 20), so P1 and P2 run first and P3 cannot finish by 14.

Earliest deadline first (EDF) is a dynamic-priority scheduler: the instance with the earliest absolute deadline has the highest priority. The priority belongs to each instance, not to the process. Use the absolute deadline (R + D), not the parameter D. An old instance with a large $D$ can have an earlier absolute deadline than a new one with a small $D$.

To build an EDF schedule: (1) mark the release time and absolute deadline of every instance; (2) at every release and every finish, look at all released, unfinished instances; (3) run the one with the earliest absolute deadline (a new release with an earlier deadline preempts); (4) check every deadline.

With P3⟨20, 2, 14⟩ and P2⟨19, 4, 17⟩, EDF meets every deadline. At time 6, P3’s deadline (14) is earlier than P2’s (17), so P3 runs first. If any scheduler can meet all deadlines of a set on one CPU, EDF can.

Exam patterns

This lecture has not appeared in the past papers I checked. The quiz questions above are the best guide.

Common Traps

• Real-time ≠ fast. It means predictable in the worst case.
• A late answer is a wrong answer.
• Windows and Linux on PCs are not real-time.
• The first number of ⟨R, C, D⟩ is a release time. The first number of ⟨T, C, D⟩ is a period.
• EDF compares absolute deadlines (R + D), not the parameter D.
• RM can miss a deadline that EDF meets. RM uses only the period.
• EDF is more powerful but harder to build, and it is unpredictable under overload.
• FCFS, SJF and RR ignore deadlines, so they can miss them.