Synchronisation des processus

Contexte

Les systèmes d'exploitation modernes reposent sur le multiprogrammation, permettant à plusieurs entités concurrentes, telles que les processeurs, les périphériques d'entrée/sortie et les utilisateurs, de s'exécuter simultanément. Les processus et threads, abstractions fournies par le système, facilitent cette gestion. L'ordonnancement des processeurs, via divers algorithmes, optimise leur utilisation. Cependant, la coordination entre ces entités soulève des défis de synchronisation.

Les threads indépendants n'ont pas d'états ou de ressources partagés, leur exécution est déterministe et reproductible. En revanche, les threads coopérants partagent des ressources, ce qui introduit une indétermination et une non-reproductibilité, rendant les bogues intermittents et difficiles à déboguer sans conception soignée.

La collaboration entre threads et processus offre des avantages : partage de ressources (par exemple, multi-utilisateurs sur une machine), accélération par chevauchement des opérations d'E/S et du calcul, ou modularité en décomposant les programmes en composants plus petits, comme dans la compilation avec GCC.

Concepts clés

Condition de course (Race Condition) : Un défaut où le résultat dépend de l'ordre d'exécution concurrent ou temporel, menant à une indétermination et non-reproductibilité.

Opération atomique : Une exécution indivisible, sans interruption ou échec partiel. En pratique, même des instructions simples comme x++ ne sont pas atomiques, car elles impliquent plusieurs étapes. De plus, des facteurs comme les pipelines, l'exécution hors d'ordre ou les fautes de page peuvent briser l'atomicité.

Section critique : Une portion de code dans un processus qui accède à des ressources partagées et ne doit pas être exécutée simultanément par un autre processus.

Exclusion mutuelle : Lorsqu'un processus est dans une section critique et accède à une ressource partagée, aucun autre processus ne doit y accéder.

Blocage (Deadlock) : Deux ou plusieurs processus attendent indéfiniment la libération de ressources, bloquant ainsi toute progression.

Famine (Starvation) : Un processus prêt à s'exécuter est continuellement ignoré par l'ordonnanceur, restant inactif.

Verrou (Lock) et déverrouillage (Unlock) : Mécanismes de protection des ressources, où un verrou empêche l'accès et un déverrouillage le permet. Un blocage peut survenir si plusieurs processus attendent mutuellement des verrous.

Protection des sections critiques

Pour garantir l'exclusion mutuelle, trois propriétés essentielles sont requises : exclusion mutuelle stricte, progression (tout thread désirant entrer y parvient finalement) et attente bornée (un thread en attente entre dans un délai fini). Une option supplémentaire est d'éviter l'attente active.

Méthode 1 : Désactivation des interruptions matérielles

En désactivant les interruptions, aucun changement de contexte ne se produit, éliminant la concurrence. Cette méthode est simple mais restrictive : elle affecte tout le système, peut causer des retards de réponse, et n'est pas adaptée aux systèmes multiprocesseurs. À utiliser avec prudence.

Méthode 2 : Solutions logicielles

Pour deux processus, l'algorithme de Peterson assure l'exclusion mutuelle sans matériel spécial. Voici une implémentation alternative avec des noms de variables modifiés :

boolean demande[] = {false, false};
int jeton = 0;

do {
    demande[proc] = true;
    jeton = autre;
    while (demande[autre] && jeton == autre) {
        // attente active
    }
    // Section critique
    demande[proc] = false;
    // Section restante
} while (true);

L'algorithme de Dekker, historiquement important, et l'algorithme de Bakery, extensible à N processus, offrent des solutions logicielles. Cependant, ils nécessitent une attente active et des opérations atomiques sur la mémoire.

Méthode 3 : Abstractions avancées

Les systèmes d'exploitation fournissent des primitives comme les verrous et les sémaphores, construites à partir d'instructions atomiques matérielles telles que Test-and-Set et Échange (Exchange).

Test-and-Set lit une valeur mémoire, la teste et la définit à 1 de manière atomique. L'Échange permute deux valeurs mémoire. Exemples avec des noms de variables modifiés :

boolean testAndSet(boolean *cible) {
    boolean valeurLue = *cible;
    *cible = true;
    return valeurLue;
}

void echanger(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

Implémentation d'un verrou avec Test-and-Set utilisant une attente active :

class Verrou {
    int etat = 0;
}

Verrou::Acquerir() {
    while (testAndSet(etat)) {
        // attente active
    }
}

Verrou::Liberer() {
    etat = 0;
}

Pour éviter l'attente active, une file d'attente peut être utilisée pour suspendre les threads en attente. Une alternative avec la méthode d'échange :

int verrou = 0;
int cle;

do {
    cle = 1;
    while (cle == 1) echanger(&verrou, &cle);
    // Section critique
    verrou = 0;
    // Section restante
} while (true);

Ces méthodes offrent des compromis : l'attente active consomme des ressources processeur et peut causer de la famine ou des blocages dans certaines situations. Les verrous sont des abstractions courantes pour implémenter l'exclusion mutuelle, généralement supportées par le matériel.