Correction de l'examen de systèmes opératoires

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

15 Novembre 2000

1   Exclusion mutuelle

On considère le problème de l'exclusion mutuelle dans le contexte d'une architecture multiprocesseur. Seules les opérations de lecture et les opérations d'écriture d'un mot mémoire sont considérées comme atomiques.

On suppose qu'il existe N processus numérotés de 0 à N-1 qui peuvent classiquement demander l'accès en exclusion mutuelle à une ressource commune. Pour résoudre ce problème, on se propose d'utiliser la notion de privilège. Le privilège donne le droit d'entrer en exclusion mutuelle au processus qui l'obtient. Si un seul processus à la fois peut obtenir ce privilège, alors la propriété d'exclusion mutuelle est garantie. Pour faire circuler le privilège entre les processus, on place les processus sur un anneau logique. Chaque processus aura ainsi un successeur (et un prédécesseur). Pour matérialiser la possession du privilège par un processus on utilise un booléen. Le tableau EstPriv(N) indique pour chaque élément EstPriv[i], si le processus i correspondant possède ou non le privilège. Initialement, on suppose que les valeurs des éléments du tableau sont :
EstPriv[0] /\ (pour tout i : 0 < i < N :: ¬ EstPriv[i])

Pour l'algorithme des opérations Entrer et Sortir, on propose donc les solutions suivantes où suc(x) désigne l'indice du successeur du processus x sur l'anneau logique :

           Entrer(int i) {                              Sortir( int i) {
              while ( ! EstPriv[i] ) do { } ;              EstPriv[suc(i)] = true ;
              }                                            EstPriv[i] = false ;
                                                           }

Questions - Réponses

  1. Montrer sur un exemple, que l'invariant suivant :
    invariant   pour tout k : (EstPriv[k] => (pour tout i != k : ¬ EstPriv[i]))
    n'est pas garanti par cette solution. Montrer que le privilège peut être perdu, c'est-à-dire que l'état où tous les éléments du tableau EstPriv sont faux est accessible et stable.
    Réponse
    Dans l'état initial, l'invariant est vérifié. Si le processus P0 exécute Entrer(0), il réussit. Lorsqu'il sort d'exclusion mutuelle, l'exécution de la première affectation EstPriv[suc(i)] = true rend l'invariant faux puisque l'état courant vérifie alors EstPriv[0] /\ EstPriv[1]. Si l'on suppose que le processus P0 est alors interrompu avant qu'il n'exécute la deuxième affectation EstPriv[0] = false, le processus P1 peut entrer en exclusion (identique à exécuter l'opération Entrer(1)) puis commencer l'exécution de Sortir(1) jusqu'à la première affectation. Ce schéma peut se reproduire de proche en proche, jusqu'à un état où tous les processus les uns après les autres, sont entrés en exclusion mutuelle, ont exécuté leur section cirtique puis ont débuté l'opération Sortir en exécutant la première affectation. Cependant, aucun ne l'a terminée en exécutant la deuxième affectation. L'état courant vérifie alors pour tout i : EstPriv[i]. L'exécution de la deuxième affectation de chaque opération Sortir en cours par chacun des processus, conduira alors à l'état pour tout i : ¬ EstPriv[i]. Le privilège est alors définitivement perdu, cet état étant stable.

  2. Modifier la solution proposée pour qu'elle garantisse l'invariant précédent et évite la perte définitive du privilège.
    Réponse
    La modification consiste à inverser l'ordre des deux affectations dans l'opération Sortir. L'invariant est alors bien garanti et bien que l'état pour lequel tous les éléments du tableau EstPriv sont faux puisse exister momentanément, celui-ci n'est jamais stable.

  3. Quelle propriété, généralement souhaitable lorsqu'on propose une solution au problème de l'exclusion mutuelle, n'est pas garantie par cette solution ?
    Réponse
    La propriété qui n'est pas vérifiée est la propriété d'indépendance. En effet, tout processus i peut entrer en exclusion mutuelle seulement si le privilège est propagé jusqu'à lui. Autrement dit, après être sorti d'exclusion mutuelle, un processus i ne retrouvera le privilège et ainsi le droit d'entrer en exclusion que lorsque chacun des autres processus aura lui-même obtenu et rendu le privilège. On constate donc qu'un processus ne réussira pas forcément à entrer en exclusion même si tous les autres processus sont hors exclusion.

  4. On aurait pu obtenir une solution similaire en utilisant simplement une seule variable entière globale pour « implanter » la circulation du privilège. Donner les algorithmes des primitives Entrer et Sortir dans ce cas.

    Réponse
    On introduit une variable entière Tour qui prend ses valeurs sur l'intervalle [0..N-1]. Initialement, on peut supposer que Tour égale 0.
            Entrer(int i) {                              Sortir( int i) {
               while ( i != Tour ) do { } ;                  if (i != Tour) abort() ;
               }                                             Tour = suc(i) ;
                                                             }
    

2   Mécanisme de sémaphore

On propose la classe Sémaphore suivante pour décrire le mécanisme de sémaphore. On suppose que ces primitives sont exécutées de façon atomique. La classe Queue implante une file d'attente FIFO d'objets et la référence Actif désigne le processus appelant la primitive :
      class Sémaphore {
         int cpt = 0 ;
         Queue fifo = new Queue ;
         P() { 
            if ( cpt == 0 ) { fifo.insérer(Actif) ; Actif.Suspendre(); } 
            cpt-- ;
            }

         V() {
            Processus unPr ;
            if ( ! fifo.vide ) {unPr = fifo.extraire() ; unPr.Continuer() ;}
            else { cpt++ ; }
            }

         Sémaphore( int v0 ) { cpt = v0 ; }
     }

Questions - Réponses

  1. Dans un contexte monoprocesseur proposer une solution pour obtenir la propriété d'atomicité des primitives.
    Réponse
    Dans un contexte monoprocesseur, l'atomicité d'une primitive peut être obtenue en garantissant que le processeur ne sera pas préempté avant la fin de la primitive. Pour cela, il suffit d'exécuter la primitive en mode ininterruptible.

  2. Montrer que les algorithmes proposés pour les primitives ne garantissent pas le mécanisme de sémaphore et proposer la correction adéquate en justifiant vos modifications.
    Réponse
    L'algorithme de l'opération V n'est pas correct car il ne comptabilise pas toujours le « jeton » normalement produit par cette opération. À titre d'exemple, si le sémaphore a initialement un compteur nul, un premier appel à P sera bloquant et le processus appelant sera inséré dans la file du sémaphore. Si une opération V est alors exécutée, le processus dans la file sera débloqué mais le compteur ne sera pas incrémenté. Par suite, l'opération P se terminera en décrémentant par contre le compteur. Celui-ci deviendra alors négatif alors que l'exécution d'un couple de primitives V,P aurait dû conduire à un compteur nul.

    Une solution correcte peut être obtenue en incrémentant systématiquement le compteur dans la primitive V :
             V() {
                Processus unPr ;
                cpt++ ;
                if ( ! fifo.vide ) {unPr = fifo.extraire() ; unPr.Continuer() ;}
                }
    

3   Moniteurs de Hoare : un canal diffusant

On considère la modélisation et l'implantation sous la forme d'un moniteur de Hoare d'un canal unidirectionnel de communication permettant de diffuser un message à plusieurs récepteurs. Tout message émis par un processus diffuseur sur le canal devra être reçu par des processus lecteurs sur un nombre fixé de sorties numérotées. L'interface de ce moniteur est la suivante :
          moniteur Canal {
              /* dépôt d'un message sur l'entrée du canal */
              Diffuser ( Message m ) ;
             /* lecture du message courant sur la sortie s donnée par l'appelant */
              Message Lire ( int s ) ;
              /* constructeur permettant d'engendrer un objet canal avec p sorties */
               Canal ( int p ) ;
          }

Synchronisation entre processus diffuseur(s) et lecteurs

La diffusion d'un message est de type synchrone : l'opération de diffusion ne se termine que lorsque le message produit a été effectivement lu (consommé) sur les p sorties. Les diffusions sur un canal donné sont traitées séquentiellement et le canal ne comporte donc qu'une seule « case ».

3.1   Première étape

Dans un premier temps, et pour simplifier la recherche d'une solution, on impose simplement que le message courant soit lu p fois sans tenir compte du paramètre « numéro de sortie » dans l'opération Lire. On suppose de plus qu'il n'existe qu'un seul processus diffuseur.

On introduit deux variables d'états : d'une part degré qui mémorise le degré de la diffusion (le nombre de sorties) et d'autre part nbL qui mémorise le nombre de lectures du message courant à faire.

On utilise deux variables conditions : DernierLect permet de synchroniser la terminaison de l'opération de diffusion avec les lectures et MesALire permet de synchoniser les lectures du message courant ;

Les opérations Diffuser et Lire doivent respecter les pré et post-conditions suivantes : On propose la solution incomplète suivante pour la classe moniteur Canal

          moniteur Canal {

              int degré = 0 ;  int nbL = 0 ; Message case ;
              condition DernierLect = new condition ;
              condition MesALire    = new condition ;

              /* dépot d'un message sur l'entrée du canal */
              Diffuser ( Message m ) {
                 case = m.clone() ; 
                 nbL = degré ;
                 /* nbL > 0 */ 
                 MesALire.signal() ;
                 if (nbL > 0) DernierLect.wait() ;
                 /* nbL == 0 */
              }
              /* lecture du message courant sur la sortie s donnée par l'appelant */
              Message Lire ( int s ) {  ...  }

              /* constructeur permettant d'engendrer un objet canal avec p sorties */
              Canal ( int p ) { degré = p ; }
          }

Questions

  1. Programmer l'opération Lire en précisant les pré et post-conditions habituelles associées aux opérations signal et wait ;
    Réponse
                  /* lecture du message courant sur la sortie s */
                  Message Lire ( int s ) {  
                     if (nbL == 0) MesALire.wait() ;
                     /* nbL > 0 */
                     nbL-- ;
                     Message Rep = case ;
                     if (nbL > 0) MesALire.signal() ;  /* réveil en chaîne */
                     else /* nbL == 0 */ DernierLect.signal() ;
                     return Rep ;
                     }
    
  2. On suppose maintenant qu'il existe plusieurs processus diffuseurs. Modifier l'opération Diffuser pour obtenir une solution correcte.
    Réponse
    L'opération Diffuser devient une opération qui doit être exécutée de façon atomique. Une deuxième opération ne peut déposer un message avant que le message précédent déposé ait été lu « degré » fois. L'opération Diffuser devient une section critique. Il suffit donc d'une variable booléenne et d'une variable condition associée pour contrôler l'utilisation de cette section critique.
              moniteur Canal {
                  ...
                  bool Libre = true ;
                  condition AccèsLibre  = new condition ;
                  /* dépot d'un message sur l'entrée du canal */
                  Diffuser ( Message m ) {
                     if (!Libre) AccèsLibre.wait() ;
                     libre = false ;
                     case = m.clone() ; 
                     nbL = degré ;
                     /* nbL > 0 */ 
                     MesALire.signal() ;
                     if (nbL > 0) DernierLect.wait() ;
                     /* nbL == 0 */
                     libre = true ;AccèsLibre.signal() ;
                  }
                  ...
              }
    

3.2   Deuxième étape

On tient compte maintenant des numéros de sorties et l'on veut assurer la lecture du message courant une seule fois sur chaque sortie.

Questions

  1. Récrire les pré et post-conditions des opérations Diffuser et Lire en précisant les variables d'états et les variables conditions introduites ;
    Réponse
    Il faut enregistrer chaque événement de lecture du message diffusé sur chaque sortie. Pour cela, on introduit une variable d'état de type tableau de booléen bool Lu[0..degré-1]. Le nombre d'éléments de ce tableau à vrai sera toujours égal à la valeur de la variable nbL. Autrement dit, le moniteur maintiendra l'invariant :
    invariant   nbL =
     
    --
    \
    /
    --
    i
    (Lu[i]  ?  0  :  1)
    À chaque sortie s, on associe par ailleurs une variable condition. En effet, l'opération Lire(s) sera bloquante tant qu'il n'existera pas de message à lire sur cette entrée. On a donc un tableau de variables conditions MesALire[0..degré-1].

    Les opérations Diffuser et Lire doivent maintenant respecter les pré et post-conditions suivantes :
  2. Modifier les opérations Diffuser et Lire en conséquence pour obtenir la solution recherchée.
    Réponse
              moniteur Canal {
    
                  int degré = 0 ;   Message case ;
                  int nbL = 0 ;              /* Contrôle de la terminaison de Diffuser  */
                  condition DernierLect = new condition ;
                  bool Libre = true ;        /* Protection de l'opération Diffuser      */
                  condition AccèsLibre  = new condition ;
                  bool[] Lu ;                /* Contrôle des lectures sur chaque sortie */
                  condition[] MesALire ;
    
                  /* dépot d'un message sur l'entrée du canal */
                  Diffuser ( Message m ) {
                     if (!Libre) AccèsLibre.wait() ;
                     /*  Libre  */
                     libre = false ;
                     case = m.clone() ; 
                     nbL = degré ; 
                     for ( int k = 0 ; k < degré ; k++ ) {  
                         Lu[k] = false ; MesALire[k].signal() 
                         };
                     if (nbL > 0) DernierLect.wait() ;
                     /*  nbL == 0   */
                     libre = true ; AccèsLibre.signal() ;
                  }
                 /* lecture du message courant sur la sortie s */
                  Message Lire ( int s ) {  
                     if (Lu[s]) MesALire[s].wait() ;
                     /*  nbL > 0 /\ ¬ Lu[s] */ 
                     nbL-- ; Lu[s] = true ;
                     Message Rep = case ;
                     if (nbL == 0)  DernierLect.signal() ;
                     return Rep ;
                     }
                  /* constructeur permettant d'engendrer un objet canal avec p sorties */
                  Canal ( int p ) { 
                     degré = p ; 
                     Lu = new bool[degré] ; MesALire = new condition[degré] ;
                     for ( int k = 0 ; k < degré ; k++ ) Lu[k] =true ;
                     }
              }
    

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