Exclusion mutuelle réalisée par logiciel

    Dans l'algorithme suivant ( solution 1), écrit en style C++, les fonctions Thread_1() et Thread_2() sont exécutées dans deux threads^[1] différents partageant les variables globales a et AuTourDe (initialisées par exemple à 0 et à 1).

int AuTourDe = 1;                // Indique le tour du thread à s'exécuter void  Thread_1 (void)            // Représente le coeur du thread 1 {     for (;;)     {         while (AuTourDe != 1);   // Attente active         SectionCritique_1 ();    // Partie à exécuter et excl. mutuelle         AuTourDe = 2;            // Le tour passe à l'autre thread         SectionNonCritique_1 (); // Partie à exécuter sans excl. mutuelle     } } // Thread_1() void  Thread_2 (void)            // Représente le coeur du thread 2 {     for (;;)     {         while (AuTourDe != 2);   // Attente active         SectionCritique_2 ();    // Partie à exécuter en excl. mutuelle         AuTourDe = 1;            // Le tour passe à l'autre thread         SectionNonCritique_2 (); // Partie à exécuter sans excl. mutuelle     } } // Thread_2()

    L'exclusion mutuelle est obtenue ici par une stricte alternance des threads. Les deux threads s'exécutent en parallèle (pseudo ou vrai). Si le thread 1 arrive le premier sur la boucle d'attente, il entre dans sa section critique. Puis il en sort et effectue l'instruction AuTourDe = 2. Tant que la valeur de la variable AuTourDe n'a pas été rangée par le thread 1 en mémoire, le thread 2 reste dans sa boucle d'attente, s'il y est déjà arrivé. Dès que la variable AuTourDe est rangée en mémoire, le thread 2 rentre à son tour dans sa section critique, et la situation devient symétrique à celle du début pour les threads 1 et 2.

    Outre l'attente active, l'inconvénient majeur qui rend cette solution irréalisable dans la pratique est justement l'alternance forcée des threads : si l'un des threads a besoin de la ressource critique pour de brefs instants très fréquents, il va être extrêmement pénalisé par l'autre thread si celui-ci utilise rarement la ressource critique.

    La solution suivante (solution 2) tente de supprimer cet inconvénient (les fonctions SectionCritique_solution 2() et SectionNonCritique_x() sont les mêmes que précédemment et ne sont donc pas reportées par la suite, ainsi que la fonction thread_2(), totalement symétrique de thread_1()).

bool UnDansSC   = false;         // Indiquent si le contrôle est dans la bool DeuxDansSC = false;         // section critique de l'un des deux                                  // threads ou dans aucune des deux void  Thread_1 (void)            // Représente le coeur du thread 1 {     for (;;)     {         while (DeuxDansSC);      // Attente active que le thread 2 sorte                                  // de sa section critique         UnDansSC = true;         // Signale au thread 2 qu'il entre                                  // dans sa section critique         SectionCritique_1 ();    // Partie à exécuter et excl. mutuelle         UnDansSC = false;        // Signale au thread 2 qu'il sort de sa                                  // section critique         SectionNonCritique_1 (); // Partie à exécuter sans excl. mutuelle     } } // Thread_1()

    Le mécanisme de signalisation entre les deux threads  est le suivant : au chargement, les variables UnDansSC et DeuxDansSC sont initialisées à false. Le premier thread qui se présente devant sa section critique positionne son indicateur Dans_x à true puis y pénètre. Dès lors, l'autre thread sera bloqué en attente active jusqu'à libération des ressources.

    Cependant le mécanisme tombe en défaut pour une raison simple : pour réaliser l'exclusion mutuelle, les deux threads accèdent en lecture/écriture à des variables partagées (UnDansSC et DeuxDansSC)  sans exclusion mutuelle (et pour cause !). Ainsi, si les deux threads consultent "simultanément" les deux variables (c'est-à-dire si les instructions while(UnDansSC); et while(DeuxDansSC); sont exécutées parallèlement ou immédiatement consécutivement) chacun constate que l'autre n'est pas dans sa section critique et y pénètre donc. Le principe d'exclusion mutuelle n'est pas respecté.

    La version suivante (solution 3) remédie à ce problème : un thread demande à l'autre l'autorisation d'entrer dans sa section critique. Ainsi, il ne pourra pas y pénétrer à l'insu de l'autre (les fonctions SectionCritique_x() et SectionNonCritique_x() sont les mêmes que précédemment). Les variables Le_1_VeutEntrer et Le_2_VeutEntrer sont initialisées à false au lancement.

bool Le_l_VeutEntrer = false;    // Indiquent si les threads 1 ou 2 bool Le_2_VeutEntrer = false;    // désirent pénétrer dans leur section                                  // critique void  Thread_1 (void)            // Représente le coeur du thread 1 {     for (;;)     {         Le_l_VeutEntrer = true;  // Signale au thread 2 qu'il désire                                  // entrer dans sa section critique         while (Le_2_VeutEntrer); // Attente active que le thread 2                                  // sorte de sa section critique         SectionCritique_1 ();    // Partie à exécuter en excl. mutuelle         Le_l_VeutEntrer = false; // Signale au thread 2 qu'il ne                                  // désire plus entrer dans sa section                                  // critique         SectionNonCritique_1 (); // Partie à exécuter sans excl. mutuelle     } } // Thread_1()

    D'un excès, nous sommes tombés dans un autre : les threads, ne voulant se concurrencer, se "font des politesses" à l'entrée de leur section critique. Normalement, le mécanisme marche, sauf lorsque les deux threads signalent "simultanément" leur désir d'accéder aux ressources communes : nous avons obtenu un interblocage (ou étreinte fatale ou, en anglais, un deadlock).

    L'algorithme suivant ( solution 4) essaie de désynchroniser la demande simultanée des deux threads.

bool Le_l_VeutEntrer = false;        // Indiquent si les threads 1 ou 2 bool Le_2_VeutEntrer = false;        // désirent pénétrer dans leur section                                      // critique void  Thread_1 (void)                // Représente le coeur du thread 1 {     for (;;)     {         Le_l_VeutEntrer = true;      // Signale au thread 2 qu'il désire                                      // entrer dans sa section critique         while (Le_2_VeutEntrer)         {             Le_l_VeutEntrer = false; // le thread 1 retire sa requête             delai (random);          // puis la présente à nouveau après             Le_l_VeutEntrer = true;  // une durée aléatoire         }         SectionCritique_1 ();        // Partie à exécuter en excl. mutuelle         Le_l_VeutEntrer = false;     // Signale au thread 2 qu'il sort de sa                                      // section critique         SectionNonCritique_1 ();     // Partie à exécuter sans excl. mutuelle     } } // Thread_1()

    C'est une solution lourde dont la justesse ne peut être démontrée théoriquement : le système est non-déterministe, ce qui ne peut pas être accepté comme unique solution générale.  Bien que cette solution puisse conduire à un interblocage, certains auteurs préfèrent appeler cette situation une famine car le blocage est fortuit et non systématique. Il faut cependant remarquer qu'une solution voisine est adoptée en cas de collision sur un réseau Ethernet avec le protocole CSMA/CD.

    Dekker a proposé la première solution permettant de résoudre de façon totalement algorithmique le problème de l'exclusion mutuelle :

int  AuTourDe        = 1;        // Indique quel est le thread prioritaire                                  // en cas de concurrence (aléatoire) bool Le_l_VeutEntrer = false;    // Indiquent si les threads 1 ou 2 bool Le_2_VeutEntrer = false;    // désirent pénétrer dans leur section                                  // critique void  Thread_1 (void)            // Représente le coeur du thread 1 {     for (;;)     {         Le_l_VeutEntrer = true;  // Signale au thread 2 qu'il désire                                  // entrer dans sa section critique         while (Le_2_VeutEntrer)  // Le thread découvre que le         {                        // thread 2 veut aussi accéder aux                                  // ressources critiques             if (2 == AuTourDe)            // Si le thread 2 a la priorité,             {                             // le thread 1 retire sa requête                 Le_l_VeutEntrer = false;  // puis attend que le thread 2                 while (2 == AuTourDe);    // ait fini                 Le_l_VeutEntrer = true;   // Puis il réémet sa requête             }         }         SectionCritique_1 ();    // Partie à exécuter en excl. mutuelle         AuTourDe = 2;         Le_l_VeutEntrer = false; // Signale au thread 2 qu'il ne désire                                  // plus entrer dans sa section critique         SectionNonCritique_1 (); // Partie à exécuter sans excl. mutuelle     } } // Thread_1()

    Le problème de l'interblocage est résolu en proposant que, chaque fois que deux threads désirent entrer "simultanément" dans leur section critique, l'un des deux a la priorité. Cette priorité, initialement déterminée aléatoirement, est inversée à chaque fois qu'un thread sort de sa section critique, c'est-à-dire chaque fois qu'il a été susceptible d'en profiter. Il est à remarquer que la boucle while(Le_2_VeutEntrer) est indispensable. En effet, arrivé à ce stade, le thread 1 ne sait pas où en est le thread 2, peut-être déjà dans sa section critique même si c'est au tour du thread 1. Dans ce cas, le thread 1 doit attendre. Mais le thread 2 peut en être seulement à la requête, auquel cas le thread 1 insiste puisqu'il est prioritaire, et le thread 2 doit s'effacer (d'où Le_2_VeutEntrer = false; dans la fonction correspondante Thread_2(),  non figurée ici).

    Comme on le voit, cet algorithme est très lourd, et encore ne permet-il que de résoudre l'exclusion mutuelle entre deux threads. De nombreux autres travaux ont été effectués, en particulier pour résoudre le problème d'exclusion mutuelle à n threads parallèles par Knuth (1966), Lamport (1974) qui a écrit un algorithme distribué très intéressant, puis Brinch Hansen en 1978. En 1981, Peterson a présenté l'algorithme très élégant suivant :

int LaisserPasser;               // Indique quel est le thread prioritaire                                  // en cas de concurrence (aléatoire) bool Le_l_VeutEntrer = false;    // Indiquent si les threads 1 ou 2 bool Le_2_VeutEntrer = false;    // désirent pénétrer dans leur section                                  // critique void  Thread_1 (void)            // Représente le coeur du thread 1 {     for (;;)     {         Le_l_VeutEntrer = true;  // Signale au thread 2 qu'il désire                                  // entrer dans sa section critique         LaisserPasser = 1;       // Le thread 2 reçoit la priorité         while (Le_2_VeutEntrer   // Le thread 1 attend que le 2 ne soit                     &&           // plus intéressé                (1 == LaisserPasser));         SectionCritique_1 ();    // Partie à exécuter en excl. mutuelle         Le_l_VeutEntrer = false; // Signale au thread 2 qu'il sort de sa                                  // section  critique         SectionNonCritique_1 (); // Partie à exécuter sans excl. mutuelle     } } // Thread_1 ()

    Toute l'astuce de cet algorithme consiste à ne pas utiliser l'exclusion mutuelle pour manipuler la variable LaisserPasser. C'est le dernier qui la met à jour qui perd son tour si l'autre thread est aussi en attente de la ressource critique.

[1] un thread est l'analogue en C/C++ d'une tâche en ADA.