Warum ‚schnell‘ nicht reicht: Echtzeitbetriebssysteme (RTOS), WCET, RMS- vs. EDF-Scheduling und die Mars-Pathfinder-Prioritätsinversion

1. Der fundamentale Graben zwischen „schnell“ und „Echtzeit“

Im Alltag wird „Echtzeitverarbeitung“ oft mit „extrem schneller Ausführung“ gleichgesetzt. Doch selbst ein Hochleistungs-Server mit Gigahertz-Mehrkernprozessor und riesigem L3-Cache, der Datenbankabfragen im Schnitt in einer Millisekunde beantwortet, dürfte niemals die Fly-by-Wire-Flugsteuerung eines Verkehrsflugzeugs, einen Kfz-Airbag oder einen Herzschrittmacher steuern. Warum? Weil Universalrechner auf maximalen durchschnittlichen Durchsatz (Average Throughput) optimiert sind: Wenn die Berechnung in $99{,}999\,\%$ der Fälle $0{,}5\,\text{ms}$ dauert, aber einmal pro Million Aufrufe wegen eines Cache-Misses, Page-Faults oder Garbage-Collection-Laufs $200\,\text{ms}$ benötigt, stürzt das Flugzeug ab oder der Airbag zündet erst nach dem Aufprall.

Nach der klassischen Definition von Donald Gillies und Hermann Kopetz lautet das Axiom der Echtzeitverarbeitung: Die Korrektheit eines Echtzeitsystems hängt nicht nur vom logisch-arithmetischen Ergebnis ab, sondern zwingend auch vom physischen Zeitpunkt $t$, zu dem das Ergebnis vorliegt (relativ zur Deadline $d_i$). Anhand der Zeitnutzenfunktion (Time-Utility Function, $U(t)$) unterscheidet man drei Klassen:

$$U_{\text{hard}}(t) = \begin{cases} V & (t \le d) \\ -\infty & (t > d) \end{cases}, \qquad U_{\text{firm}}(t) = \begin{cases} V & (t \le d) \\ 0 & (t > d) \end{cases}, \qquad U_{\text{soft}}(t) = \begin{cases} V & (t \le d) \\ V e^{-\alpha(t-d)} & (t > d) \end{cases}$$

Harte Echtzeit (Hard Real-Time): Jedes Überschreiten der Deadline ($t > d$) führt zu einer Katastrophe ($U = -\infty$, z. B. Fluglageregelung, ABS). Erfordert formale mathematische Vorab-Garantien.
Feste Echtzeit (Firm Real-Time): Verspätete Ergebnisse sind wertlos ($U = 0$) und werden sofort verworfen (z. B. optische Aussortierung am Fließband, Hochfrequenzhandel).
Weiche Echtzeit (Soft Real-Time): Der Nutzen sinkt nach $d$ kontinuierlich ab (z. B. 60-fps-Videostreaming, VoIP-Audio).

Architekturmerkmal	Universal-OS (GPOS: Linux / Windows / macOS)	Echtzeit-OS (RTOS: VxWorks / QNX / FreeRTOS / seL4)
Primäres Optimierungsziel	Maximaler Durchschnittsdurchsatz & Fairness (CFS / EEVDF)	Zeitlicher Determinismus & garantierte Worst-Case-Reaktionszeit (WCRT)
Interrupt- & Dispatch-Latenz	Mikrosekunden bis Dutzende Millisekunden (stochastischer Long-Tail)	Hunderte Nanosekunden bis wenige Mikrosekunden (strikte $O(1)$-Obergrenze)
Kernel-Präemptierbarkeit	Monolithische Kernel mit nicht-präemptierbaren Spinlock-Pfaden	Vollständig präemptierbarer Kernel oder minimaler Mikrokernel (QNX, seL4)
Speicher- & Hardware-Kontrolle	Virtueller Speicher mit Page-Faults, `malloc`, GC, volle Spekulation	Statische Partitionen, $O(1)$-Pools, Scratchpad-SRAM (TCM) & Cache-Locking

2. Der Albtraum der Worst-Case Execution Time (WCET)

Jede Scheduling-Theorie setzt voraus, dass für jede Aufgabe $\tau_i$ ihre maximale Ausführungszeit im schlechtesten Fall (Worst-Case Execution Time, $C_i$) exakt bekannt ist. Hier zeigt sich ein tiefes Paradoxon der Rechnerarchitektur: Fast alle Hardware-Mechanismen, die moderne CPUs im Durchschnitt beschleunigen (L1/L2/L3-Caches, Sprungvorhersage, Out-of-Order-Ausführung, TLB, DVFS und nicht maskierbare System Management Interrupts SMI), zerstören die Vorhersagbarkeit der WCET.

In Out-of-Order-Pipelines mit Caches treten sogar Timing Anomalies auf: Ein lokaler Cache-Hit (lokale Beschleunigung) kann dazu führen, dass ein spekulativer Pfad frühzeitig den Bus blockiert und die Gesamtlaufzeit des Programms länger wird als bei einem Cache-Miss! Sicherheitskritische Systeme (DO-178C Level A, ISO 26262 ASIL-D) nutzen daher deterministischen On-Chip-Scratchpad-Speicher (TCM) sowie Cache-Locking und berechnen die obere WCET-Schranke statisch mittels Abstrakter Interpretation und der Implicit Path Enumeration Technique (IPET) als ganzzahliges lineares Optimierungsproblem (ILP) über dem Kontrollflussgraphen (CFG):

$$\text{WCET} = \max \sum_{i=1}^{N} c_i x_i \quad \text{unter den Nebenbedingungen} \quad \sum_{j} d_{j \to i} = x_i = \sum_{k} d_{i \to k} \quad (\text{Flusserhaltung \& Schleifenschranken})$$

3. Liu & Layland (1973): Periodisches Echtzeit-Scheduling (RMS vs. EDF)

Für $n$ unabhängige periodische Tasks $\Gamma = \{\tau_1, \dots, \tau_n\}$ mit $\tau_i = (C_i, T_i, D_i)$ (WCET $C_i$, Periode $T_i$, implizite Deadline $D_i = T_i$) ist die Gesamtprozessorauslastung (Total Utilization) definiert als:

$$U = \sum_{i=1}^{n} \frac{C_i}{T_i}$$

1973 veröffentlichten C. L. Liu und James W. Layland ihre bahnbrechende Arbeit zum Vergleich statischer und dynamischer Prioritäten:

3.1 Rate Monotonic Scheduling (RMS) und die $\ln 2 \approx 69{,}3\,\%$-Schranke

Beim präemptiven Scheduling mit festen Prioritäten vergibt RMS die Prioritäten umgekehrt proportional zur Periodendauer: Je kürzer die Periode $T_i$ (je höher die Rate $1/T_i$), desto höher die statische Priorität. Liu & Layland bewiesen das Critical Instant Theorem (die längste Antwortzeit von $\tau_i$ tritt auf, wenn $\tau_i$ gleichzeitig mit allen höherprioren Tasks bei $t=0$ startet) sowie die Optimalität von RMS unter allen statischen Verfahren mit der kleinsten oberen Auslastungsschranke (Least Upper Bound):

$$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le U_{\text{lub}}(n) = n\left(2^{1/n} - 1\right) \xrightarrow{n \to \infty} \ln 2 \approx 0{,}6931 \quad (69{,}3\,\%)$$

Wichtig: Die $69{,}3\,\%$ sind nur eine hinreichende Bedingung! Bei harmonischen Perioden (jede größere Periode ist ein ganzzahliges Vielfaches der kleineren, z. B. $5\,\text{ms}, 10\,\text{ms}, 20\,\text{ms}$) erreicht auch RMS $100\,\%$ Auslastung. Für allgemeine Task-Mengen liefert die Response-Time Analysis (RTA) von Joseph & Pandya (1986) über eine Fixpunktiteration einen exakten (notwendigen und hinreichenden) Test ($R_i \le D_i$):

$$R_i^{(k+1)} = C_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j$$

3.2 Earliest Deadline First (EDF) und die $100\,\%$-Optimalität

Beim dynamischen Scheduling weist EDF jederzeit demjenigen bereiten Job die höchste Priorität zu, dessen absolute Deadline $d_{i,k} = r_{i,k} + D_i$ am nächsten liegt. Auf einem Einzelprozessor ist ein Task-Set unter EDF genau dann einplanbar (notwendig und hinreichend), wenn die Auslastung $100\,\%$ nicht überschreitet:

$$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le 1{,}00 \quad (100\,\%)$$

Beispiel: Sei $\tau_1 = (C_1=2, T_1=5)$ und $\tau_2 = (C_2=4, T_2=7)$, also $U = 2/5 + 4/7 = 97{,}14\,\%$. Unter RMS verdrängt der bei $t=5$ eintreffende Job $\tau_{1,2}$ ($d=10$) den fast fertigen Job $\tau_{2,1}$ ($d=7$, nur noch $1\,\text{ms}$ Restlaufzeit), sodass $\tau_{2,1}$ erst bei $R_2 = 8 > 7$ endet (Deadline Miss!). Unter EDF hingegen gilt bei $t=5$ wegen $d_{2,1}=7 < d_{1,2}=10$, dass $\tau_{2,1}$ weiterlaufen darf und bei $t=6 \le 7$ pünktlich fertig wird!

Trotzdem setzen fast alle industriellen RTOS (VxWorks, FreeRTOS, QNX, AUTOSAR) auf feste Prioritäten (RMS/DMS), weil EDF bei kurzzeitiger Überlast ($U > 1{,}0$) unter einem katastrophalen Domino-Effekt leidet: Ein verspäteter Job hat die älteste Deadline, blockiert die CPU und reißt sämtliche nachfolgenden Tasks in den Abgrund. RMS hingegen schützt hochpriore kritische Tasks bei Überlast vollständig und erlaubt einen extrem schnellen $O(1)$-Bitmap-Scheduler mittels CLZ-Befehl.

Bewertungskriterium	Rate Monotonic (RMS: Statische Priorität)	Earliest Deadline First (EDF: Dynamische Priorität)
Prioritätsvergabe	Statisch fest: kürzere Periode $T_i \implies$ höhere Priorität	Dynamisch: frühere absolute Deadline $d_{i,k} \implies$ höhere Priorität
Auslastungsschranke	Hinreichend: $n(2^{1/n}-1) \to 69{,}3\,\%$ ($100\,\%$ bei harmonischen $T_i$)	Notwendig & hinreichend: immer $100\,\%$ ($\sum C_i/T_i \le 1$)
Kernel-Scheduler-Aufwand	$O(1)$ (Prioritäts-Bitmap + Hardware-`CLZ`-Instruktion)	$O(\log n)$ (dynamischer Min-Heap / Rot-Schwarz-Baum)
Verhalten bei Überlast ($U > 1$)	Stabil & vorhersagbar: Kritische Tasks überleben zu $100\,\%$	Katastrophaler Domino-Effekt: Kaskadierende Ausfälle aller Tasks

4. Der NASA-Mars-Pathfinder-Vorfall (1997) und die Heilung der Prioritätsinversion

Im Juli 1997 erlitt die erfolgreich auf dem Mars gelandete NASA-Sonde Mars Pathfinder (IBM RAD6000 CPU mit VxWorks RTOS) plötzlich wiederholte System-Resets durch den Hardware-Watchdog, wodurch ganze Tagesrationen wissenschaftlicher Daten verloren gingen.

Die Ursache war eine unbeschränkte Prioritätsinversion (Unbounded Priority Inversion) zwischen drei Tasks um ein gemeinsames Mutex $M$ des internen Informationsbusses:

Der niedrigpriore Wetter-Task $\tau_L$ (ASI/MET) sperrte das Bus-Mutex $M$;
Der hochpriore Bus-Verteilungstask $\tau_H$ (bc_dist) wurde periodisch geweckt, forderte $M$ an und blockierte, da $\tau_L$ das Mutex hielt;
Bevor $\tau_L$ das Mutex freigeben konnte, trafen mittelpriore Kommunikations-Tasks $\tau_M$ ein, die das Mutex $M$ überhaupt nicht benötigten! Da $\text{Priority}(\tau_M) > \text{Priority}(\tau_L)$ galt, verdrängte $\tau_M$ den Task $\tau_L$ dauerhaft von der CPU. Dadurch konnte $\tau_L$ das Mutex $M$ nicht freigeben, der hochpriore Task $\tau_H$ verhungerte indirekt hinter $\tau_M$, und der Watchdog löste einen kompletten Neustart der Raumsonde aus!

  flowchart TD
    subgraph Bug["Unbeschränkte Prioritätsinversion auf Mars Pathfinder (1997)"]
        B1["1. Niedrigpriorer Task τ_L sperrt Mutex M"] --> B2["2. Hochpriorer Task τ_H fordert M an und wird blockiert"]
        B2 --> B3["3. Mittelpriorer Task τ_M (nutzt M nicht!) wird bereit<br/>Wegen Priority(τ_M) > Priority(τ_L) verdrängt τ_M den Task τ_L"]
        B3 --> B4["4. τ_L kann M nicht freigeben -> τ_H bleibt unbegrenzt blockiert<br/>Watchdog-Timeout löst radikalen System-Reset auf dem Mars aus!"]
    end

  flowchart TD
    subgraph Fix["Synchronisationsprotokolle nach Sha, Rajkumar & Lehoczky (1990)"]
        F1["Lösung A: Priority Inheritance Protocol (PIP)<br/>Sobald τ_H an M blockiert, hebt der Kernel die Priorität von τ_L sofort<br/>auf das Niveau von τ_H an! τ_M kann nicht unterbrechen, τ_L gibt M rasch frei"]
        F2["Lösung B: Immediate Priority Ceiling Protocol (ICPP / Highest Locker)<br/>Jedes Mutex M erhält Ceil(M) = höchste Priorität aller M-Nutzer.<br/>Sofortige Anhebung beim Locken: 100 % deadlock-frei & max. 1 Blockierung (B_i)!"]
        F1 --> F2
    end

Die mathematische Lösung hatten Lui Sha, Ragunathan Rajkumar und John P. Lehoczky bereits 1990 bewiesen:

Priority Inheritance Protocol (PIP): Blockiert ein hochpriorer Task $\tau_H$ an einem von $\tau_L$ gehaltenen Mutex $M$, erbt $\tau_L$ sofort temporär die hohe Priorität von $\tau_H$, sodass $\tau_M$ nicht dazwischenfunken kann. Nachdem die JPL-Ingenieure den Fehler im Erd-Testlabor reproduziert hatten, sandten sie über 190 Millionen Kilometer hinweg einen einzeiligen C-Shell-Befehl zum Mars, der das globale Flag SEM_INVERSION_SAFE für pipe-Mutexe im laufenden RAM von 0 auf 1 setzte – und die Mission war gerettet!
Priority Ceiling Protocol (PCP / ICPP): Da PIP weiterhin Chained Blocking und Deadlocks zulässt, weist ICPP (Standard in POSIX PTHREAD_PRIO_PROTECT und AUTOSAR OS) jedem Mutex $M_k$ statisch eine Obergrenze $\text{Ceil}(M_k) = \max\{\text{Priority}(\tau_i) \mid \tau_i \text{ nutzt } M_k\}$ zu und hebt die Priorität jedes Tasks sofort beim Sperren von $M_k$ auf $\text{Ceil}(M_k)$ an. Dies garantiert mathematisch 100 % Deadlock-Freiheit und begrenzt die Blockierungszeit jedes Tasks auf höchstens einen einzigen kritischen Abschnitt ($B_i$):

$$R_i^{(k+1)} = C_i + B_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j$$