Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 66 ยท CPU Scheduling

Real-Time and Multiprocessor Scheduling

Learn real-time scheduling with hard and soft deadlines, rate-monotonic and earliest-deadline-first algorithms, plus multiprocessor scheduling, affinity and load balancing, with simulators.

Everything so far assumed one CPU and a goal of "fast and fair". Two common situations change the rules. In a real-time system, results must arrive before a deadline: a late answer is as bad as a wrong one. In a multiprocessor system, there are several CPUs, so the scheduler must also decide where a process runs, not just when.

This final lesson of the chapter covers both. You will meet the two classic real-time algorithms, rate-monotonic scheduling (RMS) and earliest deadline first (EDF), test them in a simulator, and then study how operating systems schedule on several cores: symmetric multiprocessing, processor affinity and load balancing.

Real-time scheduling

Hard real-time A missed deadline is a failure.
Soft real-time Misses lower quality, not safety.
RMS Shorter period, higher fixed priority.
EDF Closest deadline runs first.
1 / 2

Real-time basics

A real-time task is usually periodic: it repeats every period time units, needs C units of CPU each time (its worst-case execution time), and must finish before its deadline, which is typically the end of the period. The CPU utilization of a task set is U = ฮฃ (C_i / P_i). If U > 1, no scheduler can succeed.

Real-time systems value predictability over average speed: they avoid unbounded things such as page faults on critical paths, and the kernel keeps its own non-preemptible sections and interrupt and dispatch latency small and bounded.

Hard real-time Soft real-time
Missed deadline System failure Degraded quality
Guarantees Must be proven in advance Best effort, preference over other tasks
Examples Airbag, pacemaker, flight control Video streaming, audio, games
Typical OS RTOS (VxWorks, QNX, FreeRTOS) General OS with real-time priority class

Rate-Monotonic Scheduling (RMS)

RMS is a static-priority, preemptive algorithm: the shorter a task's period, the higher its fixed priority. A job of a higher-priority task always preempts a lower-priority one. RMS is optimal among static-priority algorithms: if any fixed-priority assignment can meet all deadlines, RMS can.

Schedulability test: a set of n tasks is guaranteed to be schedulable if U โ‰ค n ร— (2^(1/n) - 1). For large n the bound approaches about 69.3%. Above the bound the test is inconclusive (the set may or may not be schedulable).

Earliest Deadline First (EDF)

EDF is a dynamic-priority, preemptive algorithm: at any moment, run the ready job whose deadline is the closest. Priorities change as new jobs arrive. For periodic tasks with deadline equal to period, EDF can schedule any task set with U โ‰ค 1, so it uses the CPU fully. Its drawbacks: more complex implementation, and when the system is overloaded, deadline misses cascade unpredictably. RMS degrades more gracefully (only low-priority tasks miss).

Comparing them in a simulation

The simulator runs a periodic task set for one hyperperiod (the least common multiple of the periods), one time unit at a time, under RMS or EDF, and reports deadline misses.

Python RMS vs. EDF

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Set 1 has low utilization and both succeed. Set 2 has U = 0.971: above the RMS guarantee, and the simulation shows RMS missing a deadline while EDF still meets all of them, because EDF can use the CPU up to 100%.

Priority inversion in real-time systems

When a high-priority task waits for a lock held by a low-priority task, a medium-priority task can preempt the low one and delay the high one indefinitely. In 1997 this was the cause of repeated resets on the Mars Pathfinder lander. The fix, priority inheritance, temporarily raises the lock holder's priority to that of the waiting task. RTOSes provide it in their mutexes.

Multiprocessor scheduling

With several CPUs we have more flexibility and new problems.

Asymmetric multiprocessing (AMP): one master core runs all kernel code and schedules the others, which only run user code. Simple, but the master can become a bottleneck.

Symmetric multiprocessing (SMP): every core runs the kernel and schedules itself. There are two ways to organize the ready queues:

  • One common ready queue. Any core takes the next process. Easy balancing, but the queue is shared data, so access must be locked, and contention grows with core count.
  • A private ready queue per core. Little contention, which is why Linux and Windows do this, but the system must prevent some cores from idling while others are overloaded.

Processor affinity

When a process runs on a core, that core's cache fills with its data. Moving it to another core throws away the warm cache. Processor affinity keeps a process on the same core: soft affinity means the OS tries but may migrate, hard affinity means the process can only run on a given set of cores (taskset on Linux, SetProcessAffinityMask on Windows).

Load balancing

Balancing wants processes to move away from busy cores; affinity wants them to stay put. Two approaches:

  • Push migration: a periodic task checks the loads and pushes processes from overloaded to idle cores.
  • Pull migration (work stealing): an idle core pulls a waiting process from a busy core's queue.

Linux uses both. On NUMA machines (memory attached to specific CPUs) the scheduler also prefers to run processes near their memory, and on multicore with hyper-threading it prefers to put tasks on separate physical cores before sharing one.

Simulating affinity and load balancing

The model below has two cores, each with a private queue. Tasks start unevenly distributed. With balancing enabled, an idle core steals from the busiest core, which shortens the total finishing time (the makespan) at the price of moved tasks.

Python Load balancing with work stealing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without stealing, core 1 sits idle while core 0 works through 25 units. With stealing, the work spreads and the makespan drops sharply, at the cost of a few migrations (and the cache misses they cause on a real machine).

Other considerations

  • Multicore with hardware threads: hyper-threading lets one core appear as two logical CPUs; the scheduler should treat them differently from real cores.
  • Gang scheduling: the threads of one parallel program are scheduled at the same time on different cores, which helps programs whose threads synchronize often.
  • Heterogeneous cores: phones mix fast and efficient cores (big.LITTLE); the scheduler places tasks by demand and energy.
  • Contention for shared caches and memory bandwidth can make two tasks slower together than apart.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In rate-monotonic scheduling, which task gets the highest priority?

    RMS assigns fixed priorities inversely to the period, so the most frequent task wins.
  2. 2. A periodic task set has CPU utilization 0.95 and deadlines equal to periods. Which algorithm can still guarantee all deadlines?

    EDF can schedule any such task set with utilization up to 1.
  3. 3. What is processor affinity?

    Staying on one core preserves cache contents; moving costs cache misses.
  4. 4. Which describes pull migration?

    Idle cores pull (steal) waiting tasks from busy ones.
  5. 5. What distinguishes hard from soft real-time?

    A missed deadline in a hard real-time system is a failure; in a soft one it just reduces quality.

Summary

  • Real-time systems are judged by deadlines; hard real-time forbids misses, soft real-time tolerates a few.
  • RMS gives fixed priority by period and is guaranteed up to a utilization bound (about 69% for many tasks); EDF runs the nearest deadline first and works up to 100% utilization.
  • Priority inheritance cures priority inversion.
  • Multiprocessor systems use SMP with per-core queues, processor affinity and push or pull load balancing.

That completes the CPU scheduling chapter. Return to the Operating Systems track for the next chapters on synchronization, deadlocks and memory.