Planification des tâches dans les systèmes temps réel : gestion de la inversion de priorité et prévention des blocages

I. Les défis de déterminisme dans les systèmes temps réel

L'exigence fondamentale des systèmes temps réel embarqués est la « réponse déterministe » — les tâches doivent se terminer avant leurs échéances. Toutefois, cette certitude est souvent compromise en pratique. Un exemple emblématique est le redémarrage fréquent du lander Mars Pathfinder en 1997, causé par un blocage de tâches de haute priorité par une tâche de priorité moyenne, entraînant un problème classique d'inversion de priorité.

Un scénario plus proche de la réalité est celui d’un contrôleur industriel utilisant FreeRTOS, où une tâche de contrôle moteur de haute priorité doit s’exécuter dans un cycle de 1 ms mais parfois dépasse ce délai jusqu’à 3 ms. L'analyse révèle que la tâche basse priorité de collecte de données détenait un verou mutex, et qu'une tâche de journalisation de priorité moyenne a préempté la tâche basse priorité, empêchant ainsi l’accès au verrou. Ce type de "tâche intermédiaire qui interfère" est l'un des pièges les plus subtils et dangereux dans la conception de planificateurs RTOS.

II. Mécanismes de planification RTOS et problèmes centraux

La planification dans un RTOS diffère fondamentalement de celle d’un système d’exploitation généraliste : tandis que les OS classiques visent à l’équité et à la capacité de traitement, les RTOS cherchent à assurer la déterminité et la prévisibilité. Comprendre les principes théoriques permet d'éviter les problèmes d’inversion de priorité et de blocage à la phase de conception.

flowchart TB
    A[Mécanismes de planification RTOS] --> B[Inversion de priorité]
    A --> C[Blocage (deadlock)]
    A --> D[Variation de temps d'exécution]

    B --> B1[Causes : tâche basse priorité détenant ressource, tâche moyenne prenant la main]
    B --> B2[Solutions : protocole d'héritage de priorité]
    B --> B3[Solutions : protocole de plafond de priorité]

    C --> C1[Causes : attente circulaire de ressources]
    C --> C2[Solutions : allocation ordonnée des ressources]
    C --> C3[Solutions : mécanismes de timeout]

    D --> D1[Causes : perturbations d'interruption + délais de planification]
    D --> D2[Solutions : partage de temps + masquage d'interruption]
    D --> D3[Solutions : attribution statique de priorités]

    B2 --> E[Analyse de planifiabilité]
    B3 --> E
    C2 --> E
    D2 --> E

    E --> F[RMA : analyse monotone de taux]
    E --> G[DMA : analyse monotone de délai]

2.1 Planification à priorité fixe et analyse de planifiabilité

La stratégie de planification la plus répandue dans les RTOS est la planification préemptive à priorité fixe. Chaque tâche reçoit une priorité statique, et le planificateur sélectionne toujours celle de priorité la plus élevée dans la file d'attente prête.

Le cœur de l'analyse de planifiabilité est de déterminer si toutes les tâches peuvent respecter leurs échéances. L'analyse monotone de taux (Rate Monotonic Analysis, RMA) fournit une condition suffisante : les priorités sont assignées décroissantes selon les périodes (plus courte période → plus haute priorité), et l'utilisation totale du CPU doit être inférieure ou égale à U ≤ n(2^(1/n) - 1) pour que toutes les tâches soient planifiables.

2.2 Inversion de priorité : causes et protocoles

L’inversion de priorité survient lorsque trois conditions sont réunies : une tâche de basse priorité détient une ressource partagée (verrou mutex), une tâche de haute priorité essaie d'accéder à la même ressource et est bloquée, une tâche de priorité moyenne préempte la tâche basse priorité. La tâche haute priorité est indirectement bloquée pendant la durée d’exécution de la tâche moyenne.

Le protocole d’héritage de priorité (Priority Inheritance Protocol, PIP) résout ce problème en faisant que la tâche de basse priorité hérite temporairement la priorité de la tâche de haute priorité tant qu’elle détiendra le verrou. Ainsi, la tâche de priorité moyenne ne peut pas préempter la tâche basse priorité, éliminant l’inversion.

Le protocole de plafond de priorité (Priority Ceiling Protocol, PCP) est plus radical : chaque verrou mutex est associé à une priorité plafond (la priorité maximale des tâches pouvant demander ce verrou). Lorsque la tâche acquiert le verrou, elle est immédiatement promue à cette priorité plafond. PCP non seulement résout l’inversion de priorité, mais empêche aussi les blocages.

2.3 Prévention du blocage : allocation ordonnée des ressources

Les quatre conditions nécessaires à un blocage sont : exclusivité, détention et attente, impossibilité de retrait, et attente circulaire. La stratégie la plus utile dans les RTOS pour éviter ces blocages est de casser la condition de "dépendance circulaire" — les tâches doivent acquérir les ressources dans un ordre strictement croissant.

III. Implémentation du code de planification RTOS

3.1 Verrou mutex avec héritage de priorité

#include <stdint.h>
#include <stdbool.h>

// Structure de contrôle de tâche (version simplifiée)
typedef struct {
    uint8_t base_priority;      // Priorité de base
    uint8_t current_priority;   // Priorité actuelle (peut être augmentée)
    const char* name;
} TaskTCB;

// Verrou mutex avec héritage de priorité
typedef struct {
    TaskTCB* owner;             // Tâche actuellement propriétaire
    uint8_t ceiling_priority;   // Priorité plafond (utilisée par PCP)
    bool use_pcp;               // Mode PCP activé
} PriorityInheritMutex;

// File d'attente prête (simplifiée : indexée par priorité)
#define MAX_PRIORITY 32
static TaskTCB* ready_queue[MAX_PRIORITY];
static uint8_t highest_ready = 0;

/**
 * Acquérir un mutex
 * Si le mutex est détenu par une tâche basse priorité, déclenche l’héritage de priorité
 */
int pi_mutex_lock(PriorityInheritMutex* mutex, TaskTCB* current_task) {
    if (mutex->owner == NULL) {
        // Mutex libre, acquisition directe
        mutex->owner = current_task;

        // Mode PCP : promouvoir immédiatement à la priorité plafond
        if (mutex->use_pcp) {
            current_task->current_priority = mutex->ceiling_priority;
        }
        return 0;
    }

    if (mutex->owner == current_task) {
        // Réacquisition (non récursive, erreur)
        return -1;
    }

    // Mutex occupé par une autre tâche
    TaskTCB* owner = mutex->owner;

    if (mutex->use_pcp) {
        // Mode PCP : pas d’inversion possible
        // Le détenteur est déjà à la priorité plafond
        // La tâche courante bloque
        return -2;  // Bloquer
    }

    // Mode PIP : héritage de priorité
    // Si la tâche courante a une priorité supérieure, promouvoir le détenteur
    if (current_task->current_priority > owner->current_priority) {
        owner->current_priority = current_task->current_priority;
        // Réinsérer la tâche dans la file d'attente prête (priorité modifiée)
        // Dans un vrai RTOS, cela déclencherait un réévaluation du planificateur
    }

    // La tâche courante bloque
    return -2;
}

/**
 * Libérer un mutex
 * Restaure la priorité originale du détenteur
 */
int pi_mutex_unlock(PriorityInheritMutex* mutex, TaskTCB* current_task) {
    if (mutex->owner != current_task) {
        return -1;  // Non-détenteur
    }

    // Restaurer la priorité initiale
    current_task->current_priority = current_task->base_priority;

    // Libérer le mutex
    mutex->owner = NULL;

    // Réveiller la tâche la plus prioritaire dans la file d'attente
    // Dans un vrai RTOS, il faudrait parcourir la file d'attente
    return 0;
}

3.2 Outil d’analyse de planifiabilité

#include <math.h>
#include <stdio.h>

// Paramètres de tâche
typedef struct {
    double period;       // Période (ms)
    double wcet;         // Temps d'exécution pire cas (ms)
    double deadline;     // Échéance (ms)
    uint8_t priority;    // Priorité
} RTTask;

/**
 * Analyse monotone de taux (RMA)
 * Vérifie si l'ensemble des tâches est planifiable
 * Retour : 0 = planifiable, -1 = non planifiable
 */
int rma_analysis(const RTTask* tasks, int count) {
    // Tri par période croissante (plus courte période → plus haute priorité)
    // Supposons que tasks soit déjà trié par priorité

    double total_utilization = 0.0;

    for (int i = 0; i < count; i++) {
        double ui = tasks[i].wcet / tasks[i].period;
        total_utilization += ui;

        // Calcul du temps de réponse maximum (Ri)
        // Ri = Ci + Σ(Ri/Tj) * Cj (j < i)
        double ri = tasks[i].wcet;
        double ri_prev = 0.0;

        // Itération pour résoudre l'équation
        int max_iterations = 100;
        for (int iter = 0; iter < max_iterations; iter++) {
            ri_prev = ri;
            double interference = 0.0;

            // Calcul de l'interférence des tâches de plus haute priorité
            for (int j = 0; j < i; j++) {
                double num_requests = ceil(ri_prev / tasks[j].period);
                interference += num_requests * tasks[j].wcet;
            }

            ri = tasks[i].wcet + interference;

            // Convergence
            if (fabs(ri - ri_prev) < 1e-6) {
                break;
            }

            // Divergence : temps de réponse supérieur à l’échéance
            if (ri > tasks[i].deadline) {
                printf("Tâche %d non planifiable : Ri=%.2f > Di=%.2f\n",
                       i, ri, tasks[i].deadline);
                return -1;
            }
        }

        printf("Tâche %d : période=%.1fms, WCET=%.1fms, "
               "temps de réponse=%.2fms, échéance=%.1fms [%s]\n",
               i, tasks[i].period, tasks[i].wcet,
               ri, tasks[i].deadline,
               ri <= tasks[i].deadline ? "OK" : "FAIL");
    }

    // Vérifier la borne RMA
    double rma_bound = count * (pow(2.0, 1.0 / count) - 1.0);
    printf("Utilisation CPU totale : %.2f%%, borne RMA : %.2f%%\n",
           total_utilization * 100, rma_bound * 100);

    if (total_utilization <= rma_bound) {
        printf("Conditions RMA satisfaites, ensemble planifiable\n");
        return 0;
    }

    printf("Dépassement de la borne RMA, mais analyse de réponse peut encore réussir\n");
    return 0;
}

3.3 Prévention du blocage : allocation ordonnée des ressources

#define MAX_RESOURCES 8

// Numérotation globale des ressources
static uint8_t resource_order[MAX_RESOURCES] = {
    0, 1, 2, 3, 4, 5, 6, 7
};

// Plus grande ressource détenu par chaque tâche
static uint8_t task_max_held_resource[16] = {0};

/**
 * Acquisition ordonnée des ressources
 * Règle : une tâche ne peut acquérir une ressource que si son numéro est supérieur
 * à celles déjà possédées, empêchant les cycles
 */
int ordered_resource_acquire(uint8_t task_id, uint8_t resource_id,
                              PriorityInheritMutex* mutex, TaskTCB* current_task) {
    // Vérifier violation de l'ordre
    if (resource_id <= task_max_held_resource[task_id]) {
        return -3;  // Violation de l'ordre
    }

    int result = pi_mutex_lock(mutex, current_task);
    if (result == 0) {
        // Succès, mettre à jour le max
        if (resource_id > task_max_held_resource[task_id]) {
            task_max_held_resource[task_id] = resource_id;
        }
    }

    return result;
}

/**
 * Libération de ressource
 */
void ordered_resource_release(uint8_t task_id, uint8_t resource_id,
                               PriorityInheritMutex* mutex, TaskTCB* current_task) {
    pi_mutex_unlock(mutex, current_task);

    // Réinitialiser
    task_max_held_resource[task_id] = 0;
}

IV. Compromis architecturaux dans les stratégies de planification RTOS

Compromis 1 : choix entre PIP et PCP. PIP est simple à implémenter mais ne prévient pas les blocages (chaînes d’héritage). PCP empêche à la fois l’inversion et le blocage, mais est plus complexe, nécessitant une connaissance globale de priorités. Recommandé : utiliser PIP pour < 5 verrous, PCP pour plus de verrous ou haute sécurité.

Compromis 2 : priorité statique vs EDF. L’EDF a une limite théorique de 100% d’utilisation, supérieure à RMA (69%). Mais en cas de surcharge, EDF est imprévisible (toutes les tâches manquent leur échéance), tandis que les priorités fixes affectent uniquement les basses priorités. Les systèmes critiques doivent privilégier les priorités statiques.

Compromis 3 : gestion des interruptions vs planification. Les routines de service d’interruption (ISR) ont une priorité supérieure à toute tâche. Les ISR longues retardent toutes les tâches. Il est recommandé de limiter les ISR à des actions minimales (effacement du flag d'interruption, envoi d’un sémaphore) et de déléguer le traitement à des tâches.

V. Conclusion

Le principal défi de la planification des tâches RTOS est d’équilibrer la concurrence de ressources et les contraintes temporelles tout en maintenant la déterminité. Les protocoles d’héritage de priorité résolvent l’inversion, l’allocation ordonnée prévient les blocages, et l’analyse de planifiabilité vérifie la faisabilité — tous indispensables.

Étapes de mise en œuvre :

1. Mesurer les périodes et WCET de toutes les tâches pour constituer un tableau de paramètres ;
2. Appliquer l’analyse RMA pour valider la planifiabilité, ajuster si nécessaire ;
3. Utiliser des verrous PIP ou PCP pour toutes les ressources partagées, et définir une numérotation stricte pour éviter les blocages. Le principe clé : la déterminité d’un système temps réel est conçue, pas testée.