Multitasking, RTOS, and Scheduling

Phase 5 ended with a single program: how it’s structured, compiled, and optimized for one thread of control running to completion. Real embedded systems rarely get that luxury; they have to juggle multiple, independently-timed activities on one CPU and guarantee that every one of them still meets its deadline. That’s the subject of this phase, and it’s arguably the point the whole series has been building toward: Phase 1‘s models of computation and its treatment of mutual exclusion, Phase 2‘s insistence that concurrency and parallelism are different things, and the hardware concurrency mechanisms built up across Phases 2 through 4 (interrupts, pipelining, multicore) all converge here into one practical question: how do you actually guarantee that a real-time embedded system meets its deadlines?

Tasks, Processes, and Why You Need a Scheduler

Start with vocabulary, since the two books use it slightly differently and it’s worth holding both versions in your head at once. A task is an application-level unit of functionality, logically distinct and often running at its own rate; a process is one execution of a program with its own state (registers plus memory, possibly its own address space if there’s an MMU behind it); a thread is a process that shares an address space with others. Wolf tends to use “task” and “process” interchangeably; Lee and Seshia are more precise about the distinction, as the multitasking discussion later in this phase will show.

The motivating problem here is a practical one, not an academic taste for abstraction: hand-rolled multi-rate control code, a counter dividing up a main loop here, some ad hoc button polling shoved into a compression loop there, gets unmanageably fragile the moment any of the individual execution times vary even slightly. The task/process abstraction, plus an OS that knows how to switch between tasks, exists specifically to solve that fragility, not as a style preference.

Once you’re thinking in terms of tasks, three timing quantities do most of the work. Release time is when a process becomes eligible to run, not when it actually starts; deadline is when it must finish; period is the time between successive executions of a periodic task, with rate defined as 1/period. A task graph, a directed acyclic graph of data-dependent processes, formalizes the precedence constraints between tasks; it has to be acyclic, since a cycle would be meaningless in a system that executes periodically.

The fundamental capacity metric underneath all of this is CPU utilization: over an interval $t$, for a set of processes with CPU times $C_i$,

$$U = \frac{\sum_i C_i}{t}, \qquad 0 \le U \le 1$$

which by construction can never exceed 1. Evaluating it correctly for a set of periodic tasks requires the hyperperiod, the least common multiple of all the individual periods, since that’s the shortest window guaranteed to cover every possible combination of process executions.

Underneath the scheduling theory sits a simple state model: a process is waiting, ready, or executing, and it can move from executing back to ready via preemption. Only one process executes at a time (or an idle process runs, if nothing else is ready). This three-state model is the OS-level analog of the Mealy-machine state semantics from Phase 1, just applied to whole processes instead of individual state variables.

The two simplest scheduling policies, useful as a baseline before getting into priority-based scheduling, are both static and non-priority-based. Cyclostatic (TDMA) scheduling assigns each process a fixed time slot every hyperperiod, whether or not it actually has work to do in that slot; it’s simple but wastes slots. Round-robin scheduling skips a process that has no work ready and moves straight to the next one, filling slots more efficiently at the cost of less predictable timing per process.

It’s worth carrying forward a concrete cautionary tale from Wolf’s chapter: the Space Shuttle case study, in which a functionally correct software module combined with a subtle, seemingly unrelated timing change (an added initialization delay) produced a real launch-delaying failure. The general lesson generalizes well beyond that one incident: timing bugs can be introduced by changes that have nothing to do with the timing-critical code itself, and they’re notoriously hard to catch in testing, because tests rarely exercise cold-start initialization paths exhaustively.

Building an RTOS: Preemption and Priority-Driven Execution

Preemption is where an RTOS earns its keep, and it does so by deliberately breaking the ordinary C-function-call abstraction. A kernel driven by a periodic timer (the time quantum) can interrupt execution at essentially any point inside any subroutine, not just at a function boundary, and that requires assembly-level context switching: saving and restoring the full register set (the process’s context), tracked in a data structure called the process control block. No high-level language construct does this for you, which is exactly why real RTOS internals are written in a mix of C and inline assembly. Wolf’s walkthrough of FreeRTOS.org makes this concrete: portSAVE_CONTEXT, vTaskSwitchContext, and portRESTORE_CONTEXT are the actual assembly-level machinery behind a context switch.

On top of that mechanism sits a simple rule for priority-driven scheduling: always run the highest-priority process that is currently ready; a running process gets preempted only by a strictly higher-priority process becoming ready, never by one of equal or lower priority. Wolf works this out concretely in a three-process example: once the highest-priority process becomes ready, it is guaranteed to run to completion, even if a lower-priority process’s data happens to become available in the meantime.

Rate-Monotonic and Earliest-Deadline-First Scheduling

With the basic preemption mechanism in place, the real question becomes how to assign priorities, and this is the theoretical core of the whole phase: both books cover the same two algorithms, Lee and Seshia with more rigor (formal theorems and proofs), Wolf with more operational detail (implementation and complexity).

Rate-Monotonic Scheduling (RMS) assigns static priority by period: the shorter a task’s period, the higher its priority. The accompanying analysis technique, Rate-Monotonic Analysis (RMA), rests on a specific set of assumptions that are worth internalizing precisely, since every guarantee below depends on all of them holding: a single CPU, periodic tasks, zero context-switch time, no data dependencies between tasks, constant execution time per task, deadline equal to the end of the period, and a scheduler that always runs the highest-priority ready task. The key analytical shortcut is the critical instant: for any given task, its worst-case response time occurs precisely when it becomes ready at the same moment as every higher-priority task. That means RMA only has to check the aligned-release-time scenario to prove feasibility, not every possible phase offset between tasks.

Liu and Layland’s 1973 RMS optimality theorem, proved in both books via a critical-instant/interchange argument, states that among fixed-priority schedulers, assigning priority by shortest-period-first is optimal: if any fixed-priority assignment yields a feasible schedule for a task set, the rate-monotonic assignment does too. Lee and Seshia’s proof sketch for the two-task case compares the two possible fixed-priority orderings’ worst-case CPU-time requirements within one period. For two tasks with periods $p_1 < p_2$ and worst-case execution times $e_1, e_2$ (aligned release times),

$$\text{giving } \tau_1 \text{ (the shorter period) higher priority is feasible iff } e_2 \le p_1 - e_1$$ $$\text{giving } \tau_2 \text{ higher priority is feasible iff } e_1 + e_2 \le p_1$$

Since the second condition implies the first but not the reverse, giving the shorter-period task higher priority is never worse than the alternative; that’s the essence of the optimality result.

Optimal-among-fixed-priority-schedulers is not the same as optimal in absolute terms, though, and RMS is provably suboptimal on utilization. The Liu-Layland utilization bound quantifies exactly how much:

$$U = \sum_{i=1}^n \frac{e_i}{p_i} \;\le\; n\left(2^{1/n} - 1\right)$$ $$\lim_{n\to\infty} n\left(2^{1/n}-1\right) = \ln 2 \approx 0.693$$

A task set using no more than about 69.3% of the CPU is guaranteed RMS-feasible regardless of how many tasks it has; above that bound, feasibility has to be checked directly rather than assumed (RMS can still succeed there, it just isn’t guaranteed to). For large $n$, this means up to roughly 31% of the CPU can sit idle even in a fully optimal fixed-priority schedule: a real, quantified cost of committing to static priorities, not a hand-wavy caveat.

Earliest-Deadline-First (EDF) takes the opposite approach: dynamic priority, recomputed on every completion, where the scheduler always runs whichever ready task has the nearest deadline. Its non-preemptive ancestor is EDD (Jackson’s algorithm), for a batch of non-repeating tasks with no arrivals, generalized to EDF (Horn’s algorithm) to support arrivals and periodic tasks. Both are provably optimal with respect to minimizing maximum lateness,

$$L_{max} = \max_i \left(f_i - d_i\right)$$

where $f_i$ is task $i$‘s finish time and $d_i$ its deadline (zero or negative for any feasible schedule). The proof is a clean interchange argument: given any adjacent pair of tasks not in earliest-deadline order, swapping them can only reduce, never increase, the maximum lateness, so repeatedly swapping converges on the EDD/EDF ordering without ever making things worse along the way.

EDF’s payoff is that it can achieve up to 100% utilization: $U \le 1$ is both necessary and sufficient for feasibility,

$$U = \sum_{i=1}^n \frac{e_i}{p_i} \le 1 \iff \text{a feasible EDF schedule exists}$$

which is a strictly better guarantee than RMS’s sufficient-only bound. That comes at the cost of a genuinely more complex implementation: EDF needs a dynamically-resorted structure, such as a binary tree keyed by deadline, giving $O(\log n)$ per update, versus RMS’s presorted array with an $O(n)$ scan, since fixed priorities never change once assigned.

EDF’s optimality has a real limit, though: it is not optimal once precedence constraints enter the picture. Lee and Seshia work through a six-task counterexample where plain EDF misses a deadline that a precedence-aware ordering would meet. LDF (Lawler’s algorithm), which builds the schedule backwards starting from the last task, is optimal in the presence of precedence constraints, but it doesn’t support task arrivals. EDF* (Chetto et al.) fixes that by adjusting each task’s effective deadline so it’s no later than the earliest deadline among everything that depends on it: for task $i$ with immediate dependents $D(i)$,

$$d_i' = \min\left(d_i,\ \min_{j \in D(i)} d_j'\right)$$

so a task’s effective deadline gets pulled earlier to match its most time-pressured successor, before ordinary EDF is applied on top. It’s a clean instance of a reusable problem-solving pattern: rationalize the input data before applying a known-optimal algorithm to it.

Both books converge on the same practical verdict about which to pick. RMS is simpler, cheaper, and easier to reason about and verify, which makes it the natural fit for hard real-time, safety-critical work; EDF squeezes more utilization out of the same CPU but is harder to diagnose near overload. Critically, EDF degrades unpredictably under overload: Liu and Layland showed that an overloaded EDF system runs at 100% capacity right up until it suddenly starts missing deadlines, with no warning about which task will miss next. RMS overload, by contrast, is deterministic: the lowest-priority task always misses first. And if a task set genuinely doesn’t fit on the CPU, the real remedies are mundane ones: a faster CPU, reduced process execution time, or, rarely feasible, relaxed deadlines. There’s no scheduling-algorithm trick that manufactures CPU capacity that isn’t there.

Priority Inversion, Inheritance, and the Priority Ceiling Protocol

Priority-based scheduling runs into a specific, famous failure mode once tasks share resources: priority inversion. A low-priority task holding a shared resource (a lock, a bus, anything mutually exclusive) blocks a high-priority task that needs the same resource, and the blocking can become unbounded if a medium-priority task then preempts the low-priority lock-holder: the low-priority task can’t finish and release the lock while it’s preempted, so the high-priority task ends up waiting indefinitely behind a task with no direct claim on the resource at all. This isn’t a theoretical worry: the Mars Pathfinder mission in 1997 suffered exactly this bug, where a low-priority meteorological task holding a lock blocked a high-priority task while medium-priority tasks ran freely, causing repeated system resets on Mars.

The first fix is the priority inheritance protocol: when a high-priority task blocks on a lock held by a lower-priority task, the lock-holder temporarily inherits the blocked task’s priority. That prevents medium-priority tasks from preempting the lock-holder, bounding the inversion to just the time needed to finish the critical section, after which the lock-holder’s priority reverts once it releases the lock. It’s simple, but it doesn’t prevent deadlock on its own.

Sha et al.’s 1990 priority ceiling protocol goes further. Every lock is assigned a priority ceiling, defined as the priority of the highest-priority task that could ever acquire it, and a task is allowed to acquire a new lock only if its own priority is strictly higher than the ceilings of every lock currently held by other tasks. Lee and Seshia work through a two-lock deadlock example showing this provably prevents certain deadlocks, by ruling out any situation where a task holds one lock while blocking on another lock that could complete a cycle back to it. The cost is that the protocol needs to know, in advance, typically via static code inspection, which locks each task can acquire.

There’s also a subtler, cheaper technique worth knowing: data-dependency-aware scheduling. If you know that two processes can never both be ready simultaneously, because one process’s output feeds directly into the other, you can tighten the worst-case CPU-requirement estimate below the naive bound that assumes everything could be ready at once. It’s a reminder that RMA’s “no data dependencies” assumption is a conservative simplification for the general theory, not a hard limit on what can actually be analyzed in a specific system.

Interprocess Communication

Tasks that don’t share a resource in the priority-inversion sense still need to communicate, and Wolf’s chapter lays out the two basic mechanisms. Shared memory and message passing are logically equivalent, in that each can be used to implement the other, but they differ in natural fit: shared memory suits tightly-coupled components sitting on one bus (Wolf’s example is an elastic-buffer text compressor), while message passing suits physically or logically separate units that communicate infrequently (Wolf’s home-automation example, with one microcontroller per device).

Shared memory only works safely with an atomic read-modify-write primitive underneath it. Test-and-set (ARM’s SWP instruction is a concrete example) is what makes a semaphore (P()/V(), or lock/unlock) possible at all. Without an atomic operation, the classic race is unavoidable: both sides check a flag, see it’s zero, both proceed, and one silently overwrites the other’s data. Wolf works through this flag-race scenario explicitly, and it’s worth noting that it’s the hardware-level version of exactly the race condition Lee and Seshia demonstrate in software in their multitasking chapter, covered next.

Signals, whether the lightweight Unix-style kind or the richer parameterized version found in UML, are the “interrupt, but purely software and between processes” IPC primitive: no payload beyond the signal’s own occurrence in the Unix case, or an attached object’s attributes in the UML case.

Threads, Race Conditions, and Deadlock

Lee and Seshia’s multitasking chapter is worth situating within the series’ own layering, since it’s a genuinely useful map of how everything fits together: hardware concurrency mechanisms (interrupts, pipelining, multicore, covered across Phases 2 through 4) sit at the bottom; abstract concurrent models of computation (Phase 1’s later chapters) sit at the top; and multitasking, the subject of this section (threads, processes, message passing), is the middle layer that implements the top using the bottom.

Lee and Seshia use “thread” broadly: a thread is any imperative program that shares memory and runs concurrently with others. Used this broadly, interrupts on bare metal already count as threads, which is worth flagging because it means the race-condition and atomicity issues below already applied back in Phase 3‘s ISR/foreground discussion, just without this vocabulary attached yet.

A race condition, precisely, is what happens when two concurrent code paths access or modify the same resource and the result depends on the order they happen to interleave in. Lee and Seshia’s worked example is a linked list: one thread’s addListener call gets suspended midway through modifying the list, a second thread comes along and corrupts the same list, and the result can silently produce a data structure that later triggers a segfault or, worse, executes garbage memory as if it were code.

The standard fix is a mutex, with pthread_mutex_lock/unlock bracketing a critical section where only one thread may execute at a time. But a mutex around just the writer isn’t enough: every access path to the shared resource, including read-only ones, needs the same protection, or a reader can still observe a torn, inconsistent state. Lee and Seshia’s example of update() reading while addListener() writes makes this concrete, and it’s an easy thing to miss precisely because read-only code doesn’t look dangerous.

Locking introduces its own failure mode: deadlock, where circular lock-acquisition dependencies (task A holds lock1 and wants lock2, task B holds lock2 and wants lock1) leave both threads permanently blocked with no clean recovery; the program has to be aborted. The available mitigations each carry real costs. A single global lock is simple but kills concurrency and real-time responsiveness. Disabling interrupts as a substitute mutex only works if interrupts are the sole suspension mechanism in the system, which is false on most real OSes. Consistent lock-ordering by convention avoids the cycle but is fragile against team-scale mistakes, and it can force expensive lock release/reacquire dances whenever a call needs to grab a “should be first” lock partway through its execution.

Underneath all of this sits an assumption that turns out to be shakier than it looks: sequential consistency, the intuitive guarantee that concurrent execution behaves as if all threads’ operations were interleaved into some single global sequential order, with each thread’s own operations staying in the order it specified them. Lamport’s 1979 result, discussed by Lee and Seshia via Boehm’s 2005 paper, is sobering: most real thread implementations do not actually guarantee this, because both compilers and hardware are free to reorder instructions whenever there’s no visible dependency between threads. The practical defense is the same one used for correctness in general: guard shared-variable access with mutexes, and trust that the mutex implementation itself is correct, since there’s no way around trusting some layer completely.

Lee and Seshia give one section a deliberately blunt title, “the problem with threads,” and the point behind it is that even a deadlock-avoiding fix can introduce a more insidious bug. Their example: copying data before notifying, specifically to avoid holding a lock during callbacks, creates a scenario where an “emergency” update can be silently overwritten by a stale “all normal” notification if the two threads happen to interleave just wrong. That class of bug is worse than deadlock in a specific sense: deadlocks are noticed immediately, because the system hangs, whereas this kind of insidious error can run correctly for years before it manifests.

Message Passing as an Alternative to Shared Memory

An alternative that sidesteps races and deadlock-from-shared-state entirely is Lee and Seshia’s stricter sense of process: a unit that doesn’t share memory with others at all, and communicates only through OS-provided channels, whether that’s files or message passing proper.

Their worked producer/consumer example, built on send/get, layers a condition variable (pthread_cond_wait/pthread_cond_signal) on top of a mutex. A condition variable is explicitly framed as a generalization of Dijkstra’s counting semaphore: instead of blocking on a fixed zero-versus-nonzero test, it blocks on an arbitrary predicate. One subtlety is worth remembering exactly because it’s easy to get wrong: pthread_cond_wait releases the mutex while the calling thread is blocked (otherwise the producer could never acquire the mutex to signal it) and reacquires the mutex before returning. That’s precisely why the wait has to sit inside a while re-check loop rather than a single if: by the time the awakened thread reacquires the lock, the condition it was waiting on may no longer hold.

Message passing is not a free lunch, either. An unbounded queue can exhaust memory outright if the producer outpaces the consumer; bounding the queue avoids that failure mode but reintroduces a real design tradeoff with no universally right answer: too small risks deadlock or starvation, too large wastes memory. And message-passing programs are not immune to concurrency bugs as a category: they can still deadlock through mutual waiting for messages, and they can still be nondeterminate, with the result depending on arbitrary scheduler interleaving. Message passing narrows the failure modes relative to raw shared-memory threads; it doesn’t eliminate them.

Formal Scheduling Theory: Decisions, Criteria, and Anomalies

Zooming out from RMS and EDF specifically, Lee and Seshia’s scheduling chapter gives a general vocabulary for classifying any scheduler you might encounter. A scheduling decision actually has three independent parts: assignment (which processor a task runs on), ordering (in what sequence), and timing (exactly when). Each of these three can be resolved at design time or at run time, which gives a spectrum of scheduler types: fully static (all three decided at design time, no locks needed at run time, but brittle if execution times vary from their assumed worst case), static-order or offline (assignment and ordering fixed in advance, timing deferred to run time), static-assignment (only the processor assignment fixed), and fully dynamic (everything decided at run time). It’s a good checklist for classifying any real scheduler you come across, not just RMS and EDF.

Three distinct criteria are used to compare schedulers, and each fits a different goal. Feasibility asks whether every task meets its deadline: the hard-real-time question. Maximum lateness (defined earlier, in the EDF discussion) asks how bad the worst miss is, which remains a meaningful question even for infeasible or soft-real-time schedules. Makespan, or total completion time, is a throughput or performance goal rather than a real-time one. Which criterion matters depends on whether a task set is hard real-time, where missing a deadline is simply an error, or soft real-time, where a miss is undesirable but tolerable as long as lateness stays small; that distinction should drive both which scheduling policy is appropriate and how pessimistic the worst-case-execution-time analysis feeding into it needs to be.

Scheduling across multiple processors is NP-hard in general, so exact solutions aren’t practical at scale. Hu level scheduling, where a task’s priority is the length of the longest remaining path to a leaf in the precedence graph (a critical-path heuristic), combined with a list scheduler that assigns the highest-priority ready task to the next available processor, is a practical approximation that performs near-optimally in practice without being an exact solution.

The result worth remembering most precisely is Richard’s anomalies, or scheduling anomalies, from Graham’s 1969 paper, because intuition actively misleads here. For a fixed-priority multiprocessor schedule, adding more processors, reducing individual tasks’ execution times, or weakening precedence constraints can all increase the overall makespan. Lee and Seshia’s worked nine-task example demonstrates all three effects at once. The underlying cause is that greedy, priority-respecting scheduling is non-monotonic: a local improvement can produce a worse global outcome purely by shifting which task ends up idling a processor at a critical moment. A parallel version of the same phenomenon shows up with mutex-holding tasks: shortening one task’s execution time can reverse a lock-acquisition order and increase total time. The practical implication is blunt: never assume that faster hardware, faster code, or fewer constraints is automatically a safe, monotonic improvement in a scheduled multiprocessor or multi-lock system without re-checking the actual resulting schedule. Intuition built on single-processor scheduling simply does not transfer.

Where This Leaves Us

Wolf and Lee and Seshia cover essentially the same territory at complementary depths, and reading them together pays off more than either alone would. Wolf gives the operational view: a real FreeRTOS context switch in ARM assembly, concrete shared-memory and test-and-set based IPC, cache-aware multiprocess scheduling, RTOS power-management policies. Lee and Seshia give the formal view: precise task models, theorem-and-proof optimality results for RMS and EDF, the priority ceiling protocol, and a genuinely alarming tour of why raw multithreading is dangerous in the first place. The single idea most worth carrying forward is that every technique in this phase trades some combination of utilization, implementation complexity, and predictability against the others: RMS against EDF, priority inheritance against the priority ceiling protocol, threads against message passing, more processors against fewer. The scheduling-anomalies result is the sharpest possible warning that an intuitive “improvement” along one of these dimensions can silently make another one worse. It’s the same predictability-versus-throughput tension that ran through the pipelines, caches, and compiler optimizations of the preceding phases, just now showing up at the level of whole-system scheduling, arguably the most important throughline in the study plan so far.

One thread worth pulling on once Phase 7 gets into real multiprocessor and multicore embedded designs: the scheduling-anomalies result, that more processors or weaker constraints can make a fixed-priority schedule worse, is exactly the kind of counterintuitive fact that’s easy to forget under deadline pressure, and it deserves a second look the moment multiple cores are actually on the table.