Synchronisation des processus
Correction

2ième Année Informatique et Mathématiques Appliquées

Novembre 2001

1   Exclusion mutuelle

On considère le problème de l'exclusion mutuelle dans le contexte d'une architecture multi-processeurs. On suppose que chaque processeur peut exécuter une instruction atomique inc(x) qui renvoie la valeur courante de la variable x et incrémente ensuite celle-ci de façon indivisible. Soit sous forme d'un triplet de Hoare :

{ S=k }   x = inc(S)   { x=k /\ S=k+1 }

On suppose que le nombre de processus existant en parallèle ne peut dépasser une borne fixée N.

Pour l'algorithme des opérations Entrer et Sortir, on propose d'utiliser un compteur (appelé séquenceur) global S de type entier et une variable globale Gagnant de type entier :
                    int S = 0 ; Gagnant = 0 ;
Le principe de la solution consiste à autoriser le processus qui possède le numéro gagnant à entrer en exclusion. L'algorithme de l'opération Entrer est donc le suivant :
           int Entrer() { 
              int  monTour = inc(S) ;
              while ( monTour != Gagnant ) do { } ;
              return (monTour) ;
              } 

Questions - Réponses

  1. Préciser l'invariant garanti par cette solution et sur lequel repose la propriété d'exclusion mutuelle.
    Réponse
    La propriété d'exclusion mutuelle repose sur le fait que la variable séquenceur fournit, à chaque requête d'entrée, un numéro différent, ce qui peut s'exprimer par :

    invariant pour tout i,j :1..N   ::  Pi.monTour = Pj.monTour  =>  i=j

  2. Donner l'algorithme de l'opération Sortir.
    Réponse
    Les numéros fournis par la variable séquenceur étant consécutifs, la primitive Sortir consiste simplement à incrémenter la variable globale Gagnant. Une exception est levée en cas d'appel erroné (appel de la part d'un processus qui n'est pas celui en exclusion mutuelle).
               void Sortir(int monTour) throws SortieErronée { 
                  if (monTour != Gagnant) throw SortieErronée ;
                  Gagnant += 1 ;
                  } 
    
    On remarquera qu'il n'est pas nécessaire d'utiliser l'instruction inc puisque la primitive Sortir ne peut être exécutée que par un seul processus à la fois, celui en exclusion mutuelle.

  3. Le compteur S croît indéfiniment. Trouver une solution utilisant un séquenceur borné.

    Réponse
    L'instruction inc incrémente un mot mémoire de taille finie définissant un intervalle [0..2p[. Une incrémentation de la valeur maximale provoque un débordement et l'on peut alors assurer au niveau matériel l'écriture de la valeur 0. En masquant le débordement, on a alors un compteur « modulo » 2p. En général, p vaut 16 ou 32 bits, soit une valeur nettement supérieure au nombre maximum de processus. On a donc bien N < 2p. On peut donc utiliser un tel compteur borné. La primitive Sortir doit bien entendu compter aussi modulo 2p. On préfère dans ce cas éviter d'avoir recours au masquage du débordement en programmant explicitement le comptage modulo 2p.

               void Sortir(int monTour) throws SortieErronée { 
                  if (monTour != Gagnant) throw SortieErronée ;
                  if (Gagnant == Integer.MAX_VALUE) Gagnant = 0 ;
                  else Gagnant += 1 ;
                  } 
    
    Attention :
    Une telle approche pour compter modulo 2p avec la variable S ne peut être utilisée car la non atomicité de la lecture (du test) et de l'écriture ne garantit plus l'unicité des numéros obtenus. Qui plus est, l'accès en parallèle par plusieurs processus en lecture/écriture à la variable S ne garantit même plus que la valeur lue soit la dernière valeur écrite.

2   Mécanisme de sémaphore

Un sémaphore est utilisé comme compteur de ressources critiques réutilisables. Un processus ayant exécuté plusieurs opérations P pour obtenir des ressources s'arrête inopinément (pour cause de déroutement par exemple).

Questions - Réponses

  1. Quelle est la conséquence de cet événement sur le schéma d'allocation des ressources ?
    Réponse
    Les ressources que le processus a obtenu grâce aux opérations P ne seront pas libérées grâce aux opérations correspondantes V qu'aurait dû exécuter le processus. Par conséquent, ces ressources vont rester inaccessibles aux autres processus.

  2. Proposer une solution pour éviter cette anomalie. On supposera qu'un traitement spécifique peut être exécuté par le noyau de gestion des processus lors de la terminaison anormale du processus.
    Réponse
    Une ressource critique ne pouvant être utilisée que par un seul processus, on suppose que chaque ressource allouée pointe le sémaphore qui la gère. Si l'on conserve une liste des ressources allouées aux processus (dans le descripteur de ce processus), le noyau peut alors parcourir la liste des ressources allouées et pour chaqu'une d'elle obtenir le nom du sémaphore. Une opération V peut alors être exécutée forçant ainsi la libération de la ressource.

3   Moniteurs de Hoare : Groupes de processus

On considère un système de processus parallèles qui accèdent durant leur exécution à une ressource commune. Les processus sont répartis dans des groupes numérotés de 1 à N et tout processus appartient au moins à un groupe. À titre d'exemple, le système peut se composer de 5 processus répartis dans 3 groupes selon le schéma suivant :
g1 = {p1,p3,p5},  g2 = {p2,p4},  g3 = {p1,p2, p3}

La modélisation des processus peut se faire de façon classique en distinguant 3 états caractéristiques, tout processus pouvant exécuter de façon répétitive les transitions suivantes : La figure (1) illustre le graphe de transitions modélisant ce comportement des processus.



Figure 1 : Graphe de transitions des processus


Pour désigner les attributs d'un processus, on utilise la notation pointée Pi.attr. Par exemple, Pi.etat désignera l'état courant du processus.

On utilisera le prédicat Pi.u[g] identique à (Pi.etat=utilisateur[g]).

Synchronisation

La ressource commune peut être accédée par les processus à condition de vérifier la propriété de sûreté suivante :
Exclusivité de groupe
À tout instant, la ressource ne peut être utilisée que par les processus d'un même groupe courant, avec pour conséquence, qu'un processus ne peut utiliser simultanément la ressource en tant que membre de deux groupes différents.
invariant  pour tout i,j ::   Pi.u[g] /\ Pj.u[g'] =>   g = g'

Pour garantir cette propriété, tout accès à la ressource nécessite de passer par le protocole suivant :

      processus P[i] {
         ... ; 
         Exclusivité.Obtenir(g) ; 
         /* utiliser la ressource en tant que membre du groupe g */
         Exclusivité.Libérer() ;
         ...
         }
On se propose de garantir la règle d'exclusivité de groupe en implantant les opérations Obtenir(groupe g) et Libérer() dans un moniteur de Hoare. L'interface de ce moniteur est la suivante :
                moniteur Exclusivité {
                    /* obtenir le droit d'accès */
                    void Obtenir ( int g ) ;
                    /* libérer l'accès */
                    void Libérer () ;
                 }
On introduit les variables d'état (en précisant leur valeur initiale) et conditions suivantes : On propose la solution suivante pour l'opération Obtenir(int g) :
                void Obtenir( int g) {
                   if (g != gc) wait(accès[g]) ;
                   if (np == 0) gc = g ;
                   np += 1 ;
                   signal(accès[g]) ;
                }

Questions - Réponses

  1. Corriger la condition de blocage de l'opération Obtenir(int g), celle proposée étant fausse ;
    Réponse
    L'opération Obtenir est non bloquante si la ressource est libre ou si le groupe demandeur appartient au groupe courant possédant la ressource. Cette précondition s'exprime donc par :
    Pre(Obtenir) = (np = 0) \/ (g = gc)
    La condition de blocage est donc :
    Pre(Obtenir) = (np > 0) /\ (g != gc)

    On remplace donc la première instruction conditionnelle par :
                       if ((np > 0) && ((g != gc)) wait(accès[g]) ;
    

    Autre bonne solution :

    Découpler l'évaluation des deux termes du prédicat :
                    void Obtenir( int g) {
                       if (np == 0) gc = g ;       /* test ressource libre */
                       /*  gc != 0  */
                       if (g != gc) wait(accès[g]) ;
                       /*  gc != 0  /\ g =gc   */  
                       np +=1 ;
                       signal(accès[g]) ;
                    }
    
    Attention toutefois au fait que, dans cette solution, la mise-à-jour de la variable gc lors de l'allocation de la ressource à un nouveau groupe sera à la charge de l'opération Liberer.

  2. Justifier l'occurrence de l'instruction signal(accès[g]) dans l'opération. Préciser son rôle ;
    Réponse
    Il s'agit d'assurer le réveil en chaîne des processus d'un même groupe bloqués en attente de la libération de la ressource. En effet, l'opération Libérer ne peut que réveiller le processus en tête de file d'attente de la variable condition. Or, tous les processus du groupe élu doivent être réactivés.

  3. Montrer que la solution présente un risque de famine et proposer une modification pour éviter ce risque ;
    Réponse
    Cette solution pour la primitive Obtenir peut conduire à la monopolisation de la ressource par un groupe. En effet, lorsqu'un groupe possède l'accès à la ressource, il peut garder ce droit indéfiniment si en permanence au moins un des processus du groupe utilise la ressource. Cette situation de monopole par un groupe provoque la famine des autres groupes. Une solution consiste à bloquer les processus du groupe courant dès qu'il existe au moins un processus en attente appartenant à un autre groupe. Pour tester cette condition, on introduit la fonction int suivant(g) qui teste s'il existe un groupe suivant en attente. Si un tel groupe existe, la fonction renvoie le numéro du groupe en attente. Sinon, par défaut, la fonction renvoie le groupe courant qui lui avait été passé en paramètre. Autrement dit, la fonction évalue le prédicat :
    suivant(g) =  g   if  pour tout  gc != g :: empty(acces[gc])  ~  gc   if   il existe  gc != g ::  ¬ empty(acces[gc])

    L'opération Obtenir s'écrit alors :
                    void Obtenir( int g) {
                       if (np == 0) gc = g ;      /* test ressource libre */
                       /*  gc != 0  */
                       if (g != gc || suivant(g) != g) wait(accès[g]) ;
                       /*  gc != 0  /\ g =gc   */
                       np +=1 ;
                       signal(accès[g]) ;
                    }
    
  4. Lors de la libération de la ressource par le dernier utilisateur du groupe courant, la ressource devenue libre de tout groupe peut être allouée à un autre groupe « demandeur ». Proposer une stratégie de choix parmi les groupes demandeurs de façon à éviter tout risque de famine ;
    Réponse
    Il s'agit ici d'un deuxième type de famine par coalition d'au moins deux groupes. À titre d'exemple, si la ressource libérée est toujours allouée au groupe en attente de plus petit numéro, il suffit qu'un ensemble d'au moins deux groupes ayant des « petits numéros » se coalise pour empêcher les autres groupes d'accéder à la ressource. On remarquera que le premier type de famine traite le cas de la coalition d'un ensemble de groupes réduit à un élément.

    Pour éviter un tel phénomène, il faut donc assurer une équité dans le choix du groupe suivant lorsque la ressource est libérée. Pour cela, lorsque le groupe g libère la ressource, on cherche un groupe comportant au moins un processus en attente par scrutation modulo N des variables conditions (files d'attente) en commençant par le numéro g%N + 1 où % dénote l'opérateur modulo.

  5. Implanter cette stratégie en programmant l'opération Libérer().

    Pour implanter la recherche du nouveau groupe, on peut utiliser une implantation de la fonction suivant utilisée dans l'opération Obtenir. Il suffit que celle-ci respecte le principe de recherche énoncé dans la question précédente. Une implantation possible est par exemple :
           int suivant(int g) {
              boolean vide = true ; int i = 1 ;
              /* Pré :   g=g0 /\ vide /\ i=1  */
              /* Invariant :  pour tout i appartient à ]g0..g[ :: empty(acces[i])  */
              while (vide && i <= N) { 
                g = g%N + 1 ; vide = empty(accès[g]) ; 
                if (vide) i += 1 ;
                } ;
              return (g) ;
              /* Post :  g=g0 => pour tout i!= g0 :: empty(acces[i])  */
              /*       /\ g!=g0 => ¬ empty(acces[g])             */
           }
    
    À l'aide d'une telle fonction, l'opération de libération (commutation) de groupe peut être facilemnt implantée :
          void Liberer() {
             np -=1 ;
             if (np ==0) ; { /*  la ressource est libre */
                /*  recherche d'un nouveau groupe non vide */
                gc = suivant(gc) ;
                /*  empty(acces[gc]) => pour tout g:1..N :: empty(acces[g])  */
                if (empty(accès[gc])) gc = 0 ; else  signal(accès[gc]) ;
             }
          }
    

Une solution complète

En réalité, on peut encore simplifier la solution en remarquant que le compte des processus ayant accès à la ressource suffit pour tester la condition « ressource libre ». On peut alors numéroter les groupes de 0 à N-1 et éviter la remise à zéro de gc lorsque la ressource est libre. On obtient :

    monitor Exclusivité {

       static final int N = ... ;
       int np  = 0 ; /*  nombre de processus ayant obtenus l'accès  */
       int gc  = 0 ; /*  groupe courant si la ressource est occupée  */
       condition accès[N] ; /*  numérotation des groupes de 0 à N-1 */

       int suivant(int g) {
          boolean vide = true ; int i = 1 ;
          /* Pré :   g=g0 /\ vide /\ i=1  */
          /* Invariant :  pour tout i appartient à ]g0..g[ :: empty(acces[i])  */
          while (vide && i <= N) { 
            g = g%N ; vide = empty(accès[g]) ; 
            if (vide) i += 1 ;
            } ;
          return (g) ;
          /* Post :  g=g0 => pour tout i!=g0 :: empty(acces[i])  */
          /*       /\ g!=g0 => ¬ empty(acces[g])             */
       }

       void Obtenir( int g) {
          if (np == 0) gc = g ;       /* test ressource libre */
          if (g != gc || suivant(g) != g) wait(accès[g]) ;
          /*  g =gc  */
          np +=1 ;
          signal(accès[g]) ;
       }

      void Liberer() {
         np -=1 ;
         if (np ==0) { /*  la ressource est libre */
            /*  recherche d'un nouveau groupe non vide */
            gc = suivant(gc) ;
            /*  empty(acces[gc]) => pour tout g:1..N :: empty(acces[g])  */
            if ( ! empty(accès[gc])) signal(accès[gc]) ;
         }
      }
    }

Ce document a été traduit de LATEX par HEVEA.