19-Soft-A4 Real-Time Systems · May 2015
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
National Exams — May 2015 — 04-Soft-A4 Real-Time Systems. Three-hour, closed-book exam (Casio or Sharp approved calculators only). Format: six questions of equal value (20% each); any five constitute a complete paper and only the first five as they appear in the answer book are marked. All six are solved below for completeness. Where a doubt exists as to interpretation, the candidate is expected to state assumptions — engineering assumptions used below are flagged in check callouts.
Reference texts: Jane W. S. Liu, Real-Time Systems (Prentice Hall, 2000) — task models, timing requirements, FCFS and EDF scheduling; Giorgio C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Springer, 3rd ed.) — preemptive dynamic-priority scheduling and the optimality of EDF; Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications (Springer, 2nd ed.) — distributed real-time control, network-induced delay and time-triggered protocols; Katsuhiko Ogata, Modern Control Engineering (Pearson, 5th ed.) — frequency-domain stability, phase margin and delay margin; Ian Sommerville, Software Engineering (Pearson, 10th ed.) — general software-engineering process context.
Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.
Part (1) — desired features of an RTOS. A Real-Time Operating System must guarantee timing correctness, not just eventual correctness, which drives a distinct feature set from a general-purpose OS: (a) Deterministic, bounded response time — interrupt latency, context-switch time and system-call overhead must be known worst-case bounds, not just typical averages. (b) Priority-based preemptive scheduling with a rich, configurable priority space (often 32–256+ levels) so that timing-critical tasks always run ahead of less-urgent ones. (c) Priority inheritance / priority ceiling protocols to bound priority inversion when tasks share mutexes. (d) Predictable, minimal-jitter interrupt handling, typically via a two-level interrupt-service-routine/deferred-procedure-call structure. (e) Fast, deterministic inter-task communication and synchronisation primitives (semaphores, message queues, event flags) with bounded execution time. (f) Fine-grained, high-resolution timers and clocks for scheduling periodic tasks and enforcing deadlines. (g) Small, auditable kernel footprint — a minimal trusted computing base is both a performance requirement (less code to execute on the critical path) and, for hard real-time/safety-critical use, a certification requirement (e.g. DO-178C, IEC 61508). (h) Memory-management determinism — no unbounded-latency paging or garbage collection on the critical path; memory is typically statically allocated or uses bounded-time pool allocators.
Part (2) — why general-purpose desktop OSes are unsuitable. Microsoft Windows and Mac OS are both designed to optimise average-case throughput and interactive responsiveness for a mixed, unpredictable workload of user applications, not to guarantee worst-case timing for any single task. Concretely: their schedulers use complex, dynamically-adjusted, throughput-oriented heuristics (multilevel feedback queues, dynamic priority boosting for I/O-bound and foreground tasks) whose worst-case latency is essentially unbounded and workload-dependent, not analytically provable; virtual-memory subsystems can page a process's memory to disk, introducing latencies of milliseconds and worse at unpredictable moments; device drivers and interrupt handling are not designed for bounded worst-case latency; and background system services (indexing, updates, antivirus scans, garbage-collected runtimes) can consume the CPU for unbounded periods. A general-purpose OS can be made to usually respond quickly, but "usually" is not a guarantee, and a hard real-time system that misses even one deadline has failed by definition — so neither OS, in its standard form, is suitable for hard (or, for anything with a tight deadline, even soft) real-time control. (Real-time variants/patches exist — e.g. RTX for Windows, or real-time kernels that co-run alongside a general-purpose OS — precisely because the stock kernels are unsuitable on their own.)
Part (3) — four commercially available RTOSes. (a) VxWorks (Wind River) — widely used in aerospace, defense, networking and industrial control (flew on multiple NASA Mars rover/lander missions). (b) QNX Neutrino (BlackBerry QNX) — a microkernel RTOS widely used in automotive infotainment/ADAS, industrial and medical systems. (c) Windows CE / Windows Embedded Compact (Microsoft) — a real-time-capable embedded OS distinct from desktop Windows, used in handheld and industrial devices. (d) Integrity RTOS (Green Hills Software) — a partitioned, safety-certified (DO-178B/C) RTOS used in avionics and defense. (Other valid answers include FreeRTOS, ThreadX/Azure RTOS, and LynxOS.)
Part (4) — hard vs. soft real-time systems. A hard real-time system is one in which missing a deadline constitutes a total system failure with potentially catastrophic (safety, financial, or mission) consequences — the correctness of the result is judged jointly on its logical value and on it arriving by the deadline, with zero tolerance for lateness (e.g. an airbag deployment controller, a flight-control law, an anti-lock-brake controller). A soft real-time system is one in which an occasional missed deadline degrades the quality or utility of the system's service but does not constitute outright failure — the value of a late result decays (often gracefully) rather than dropping instantly to zero (e.g. a video-streaming decoder that occasionally drops a frame, or a stock-quote display that is a few hundred milliseconds stale). Between the two, some texts define a firm real-time system, where a late result has zero value (the deadline still matters) but is not itself catastrophic — the task is simply abandoned rather than causing a system failure.
