1. L’abîme fondamental entre « rapide » et « temps réel »

Dans le langage courant, « traitement en temps réel » est souvent confondu avec « exécution ultra-rapide ». Pourtant, même un serveur équipé d’un processeur multicœur superscalaire à plusieurs gigahertz répondant en moyenne en une milliseconde ne pourrait jamais piloter les commandes de vol électriques (Fly-by-Wire) d’un avion de ligne, déclencher un airbag automobile ou réguler un stimulateur cardiaque. Pourquoi ? Parce qu’un système généraliste optimise le débit moyen (Average Throughput) : si un calcul prend $0,5\,\text{ms}$ dans $99,999\,\%$ des cas, mais bloque pendant $200\,\text{ms}$ une fois sur un million à cause d’un défaut de cache, d’une faute de page ou d’un ramasse-miettes (GC), l’avion décroche ou l’airbag explose après l’impact.

Selon la définition classique de Donald Gillies et Hermann Kopetz, l’axiome de l’informatique temps réel stipule que la justesse d’un calcul dépend non seulement de son exactitude logique et arithmétique, mais aussi de l’instant physique $t$ auquel le résultat est produit par rapport à son échéance (deadline $d_i$). La fonction d’utilité temporelle $U(t)$ distingue trois classes :

• Temps réel dur (Hard Real-Time) : Tout dépassement d’échéance ($t > d$) provoque une défaillance catastrophique ($U = -\infty$, ex. avionique, freinage ABS). Exige une preuve mathématique statique hors ligne.
• Temps réel ferme (Firm Real-Time) : Un résultat tardif a une valeur nulle ($U = 0$) et est immédiatement abandonné (ex. tri optique sur convoyeur rapide, annulation d’ordre financier HFT).
• Temps réel mou (Soft Real-Time) : L’utilité décroît progressivement après $d$ (ex. décodage vidéo 60 fps, téléphonie VoIP).

2. Le cauchemar du temps d’exécution au pire cas (WCET)

Toute théorie d’ordonnancement temps réel suppose connu à l’avance le temps d’exécution au pire cas (Worst-Case Execution Time, $C_i$) de chaque tâche $\tau_i$. Or, l’architecture des processeurs modernes recèle un paradoxe redoutable : presque tous les mécanismes matériels conçus pour accélérer la vitesse moyenne d’un CPU (caches L1/L2/L3, prédiction de branchement, exécution dans le désordre OoO, TLB, DVFS et interruptions système non masquables SMI) détruisent la prévisibilité du WCET.

Sur les pipelines Out-of-Order dotés de caches apparaissent même des anomalies temporelles (Timing Anomalies) : un succès de cache local (Cache Hit) peut permettre à une instruction spéculative de monopoliser un bus plus tôt, rendant le temps d’exécution global du programme plus long que lors d’un défaut de cache (Cache Miss) ! Les systèmes certifiés (DO-178C niveau A, ISO 26262 ASIL-D) utilisent donc de la mémoire Scratchpad SRAM / TCM déterministe et le verrouillage de cache (Cache Locking), tout en calculant la borne supérieure du WCET par interprétation abstraite et énumération implicite des chemins (IPET) via un programme linéaire en nombres entiers (ILP) sur le graphe de flot de contrôle (CFG) :

3. Liu & Layland (1973) : Ordonnancement périodique (RMS vs EDF)

Soit un ensemble de $n$ tâches périodiques indépendantes $\Gamma = \{\tau_1, \dots, \tau_n\}$ définies par $\tau_i = (C_i, T_i, D_i)$ (WCET $C_i$, période $T_i$, échéance implicite $D_i = T_i$). Le taux d’utilisation global du processeur est :

En 1973, C. L. Liu et James W. Layland ont établi les théorèmes fondamentaux opposant priorités statiques et priorités dynamiques :

3.1 Ordonnancement à vitesse monotone (RMS) et la borne $\ln 2 \approx 69,3\,\%$

En ordonnancement préemptif à priorités fixes, la règle Rate Monotonic (RMS) attribue une priorité statique inversement proportionnelle à la période : plus la période $T_i$ est courte (fréquence $1/T_i$ élevée), plus la priorité est haute. Liu & Layland ont prouvé le théorème de l’instant critique (le pire temps de réponse de $\tau_i$ survient lorsqu’elle est activée simultanément avec toutes les tâches plus prioritaires à $t=0$), ainsi que l’optimalité de RMS parmi les algorithmes à priorités fixes, avec pour plus petite borne supérieure d’utilisation :

Attention : $69,3\,\%$ n’est qu’une condition suffisante ! Si les périodes sont harmoniques (chaque période est un multiple entier des périodes plus courtes, ex. $5\,\text{ms}, 10\,\text{ms}, 20\,\text{ms}$), RMS atteint 100 % d’utilisation. Pour un système quelconque, l’analyse du temps de réponse (RTA) de Joseph & Pandya (1986) fournit une condition nécessaire et suffisante exacte par itération de point fixe ($R_i \le D_i$) :

3.2 Échéance la plus proche d’abord (EDF) et l’optimalité à $100\,\%$

En ordonnancement préemptif à priorités dynamiques, Earliest Deadline First (EDF) accorde à tout instant la priorité maximale au travail prêt dont l’échéance absolue $d_{i,k} = r_{i,k} + D_i$ est la plus proche. Sur monoprocesseur, la condition nécessaire et suffisante d’ordonnançabilité d’EDF atteint la limite physique :

Exemple : Pour $\tau_1 = (C_1=2, T_1=5)$ et $\tau_2 = (C_2=4, T_2=7)$, l’utilisation vaut $U = 97,14\,\%$. Sous RMS, l’arrivée de $\tau_{1,2}$ à $t=5$ ($d=10$) préempte aveuglément $\tau_{2,1}$ ($d=7$, à qui il ne reste que $1\,\text{ms}$), entraînant $R_2 = 8 > 7$ (violation d’échéance !). Sous EDF, à $t=5$, comme $d_{2,1}=7 < d_{1,2}=10$, EDF interdit la préemption, permettant à $\tau_{2,1}$ de terminer à $t=6 \le 7$ !

Pourtant, l’industrie (VxWorks, FreeRTOS, QNX, AUTOSAR) préfère toujours RMS/DMS car, en cas de surcharge transitoire ($U > 1,0$), EDF subit un effet domino catastrophique où une tâche en retard monopolise le CPU et fait échouer toutes les tâches suivantes, tandis que RMS protège totalement les tâches critiques de haute priorité et s’implémente en temps $O(1)$ via un bitmap et l’instruction matérielle CLZ.

4. L’incident de la sonde NASA Mars Pathfinder (1997) et l’inversion de priorité

En juillet 1997, peu après son atterrissage sur Mars, la sonde Mars Pathfinder de la NASA (processeur IBM RAD6000 sous RTOS VxWorks) a subi des réinitialisations matérielles répétées déclenchées par son chien de garde (watchdog), effaçant chaque jour de précieuses données scientifiques.

Le coupable était une inversion de priorité non bornée (Unbounded Priority Inversion) impliquant trois tâches autour d’un mutex $M$ protégeant le « bus d’information » partagé :

• La tâche météorologique de basse priorité $\tau_L$ (ASI/MET) verrouille le mutex $M$ ;
• La tâche critique de gestion du bus de haute priorité $\tau_H$ (bc_dist) se réveille, demande $M$ et se bloque ;
• Avant que $\tau_L$ ne libère $M$, des tâches de communication de priorité moyenne $\tau_M$ (qui n’utilisent pas $M$ !) deviennent prêtes. Comme $\text{Priority}(\tau_M) > \text{Priority}(\tau_L)$, $\tau_M$ préempte $\tau_L$ pendant une longue durée, empêchant $\tau_L$ de déverrouiller $M$ et bloquant indirectement $\tau_H$ jusqu’à l’expiration du chien de garde !

  flowchart TD
    subgraph Bug["Inversion de priorité non bornée sur Mars Pathfinder (1997)"]
        B1["1. La tâche basse priorité τ_L verrouille le mutex M"] --> B2["2. La tâche haute priorité τ_H demande M et passe à l'état BLOQUÉ"]
        B2 --> B3["3. La tâche moyenne priorité τ_M (indépendante de M) arrive !<br/>Comme Priority(τ_M) > Priority(τ_L), τ_M préempte τ_L et garde le CPU"]
        B3 --> B4["4. τ_L ne peut pas libérer M -> τ_H reste bloquée indéfiniment<br/>Le chien de garde expire et force le redémarrage complet de la sonde !"]
    end

  flowchart TD
    subgraph Fix["Protocoles de synchronisation de Sha, Rajkumar & Lehoczky (1990)"]
        F1["Solution A : Protocole d'héritage de priorité (PIP)<br/>Dès que τ_H bloque sur M, le noyau élève la priorité effective de τ_L<br/>au niveau de τ_H ! τ_M ne peut plus préempter et τ_L libère M aussitôt"]
        F2["Solution B : Protocole de plafond de priorité immédiat (ICPP)<br/>Chaque mutex M reçoit un plafond Ceil(M) = priorité max de ses utilisateurs.<br/>Élévation immédiate dès le verrouillage : zéro interblocage & 1 seul blocage max (B_i) !"]
        F1 --> F2
    end

Deux protocoles formulés par Sha, Rajkumar et Lehoczky dès 1990 éliminent ce phénomène :

1. Protocole d’héritage de priorité (PIP : Priority Inheritance Protocol) : Dès que $\tau_H$ bloque sur le mutex $M$ détenu par $\tau_L$, le noyau élève temporairement la priorité effective de $\tau_L$ au niveau de $\tau_H$, interdisant toute préemption par $\tau_M$. Après avoir reproduit le bogue au sol, les ingénieurs du JPL ont envoyé à 190 millions de kilomètres une commande C via l’interpréteur VxWorks pour basculer la variable globale SEM_INVERSION_SAFE de 0 à 1 directement en RAM, sauvant ainsi la mission !
2. Protocole de plafond de priorité (PCP / ICPP : Immediate Priority Ceiling Protocol) : Le PIP laisse subsister le blocage en chaîne et le risque d’interblocage (Deadlock). L’ICPP (norme POSIX PTHREAD_PRIO_PROTECT et AUTOSAR OS) attribue à chaque mutex $M_k$ un plafond statique $\text{Ceil}(M_k) = \max\{\text{Priority}(\tau_i) \mid \tau_i \text{ utilise } M_k\}$ et élève la priorité de toute tâche dès l’instant où elle verrouille $M_k$. Cela garantit l’absence totale de deadlock et limite le retard maximal de toute tâche à une seule section critique ($B_i$) :