TD SEPC Semestre 2 Deuxième année Filière MIF

De Ensiwiki
Aller à : navigation, rechercher

Problème des philosophes avec les sémaphores et moniteurs

Introduction : N philosophes sont assis a une table circulaire, ils aimeraient manger leur plat de spaghettis avec 2 fourchettes chacun mais il n'y a que N fourchettes. Evidemment ils ne pourront pas tous manger en même temps. Il s'agit d'écrire un outil de synchronisation pour ce problème.

Philosophos.jpg
 Philo(i){
     while(1){
         pense( );
         prendre_fourchette( i );
         manger ( );
         poser_fourchette( i );
     }
 }

Il s'agit donc d'écrire les procédures prendre_fourchette et poser_fourchette.

Première solution : On prend un sémaphore par fourchette Chaque sémaphore est initialisé à 1

 sem fourch[ N ]  = {1,........1}
 prendre_fourchette ( int i ){
       fourch[i].P();               //demande/prend de la fourchette de gauche
       fourch[ (i + 1) % N ].P( );  //demande/prend la fourchette de droite 
 }
 poser_fourchette ( int i ){
       fourch[ i ].V( );           //pose de la fourchette de gauche
       fourch[ (i + 1) % N ].V( ); //pose la fourchette de droite 
 }

Cette implémentation pose un problème d'interblocage dans le cas où les N philosophes décident de manger donc d'appliquer la procédure prendre fourchette. En effet, tous les philosophes détiennent la fourchette qui est à leur droite et attendent que celle qui est a leur gauche se libère.

Deuxième solution : On se centre ici sur les philosophes. Un sémaphore est attribué à chaque philosophe. Etat = { PENSE , MANGE , A_FAIM}

Un philosophe qui veut prendre les fourchettes (donc manger) déclare qu'il a faim. Si l'un de ses deux voisins est en train de manger, il ne peut donc pas prendre les deux fourchettes pour l'instant et donc se met en attente. Si les deux philosophes a coté ne mangent pas alors il peut prendre les deux fourchettes et déclarer qu'il mange. Quand le philosophe a fini de manger, il déclare donc qu'il pense et regarde si ses deux voisins qui forcément ne pouvaient pas manger, en ont dès lors l'opportunité. Si c'est le cas il les réveille.

    sem philo_prive [ N ]
    Etat Etat_Philo[ N ] =  { PENSE, …......., PENSE}
    sem mutex = 1 			 //mutex.c = 1  pour que l'écriture dans le tableau  Etat_Philo
                                       //se fasse en exclusion mutuelle
    test_mange( int i ){
         if (Etat_Philo[ i ] == A_FAIM 
               &&  Etat_Philo[ (i+1)%N ] != MANGE 
               &&  Etat_Philo[ (i-1+N)%N ] != MANGE ) {		
               Etat_Philo[ i ] =  MANGE;
               philo_prive[ i ].V( );
         }	
    }
    prendre_fourchette (int i){
               mutex.P( );
               Etat_Philo[ i ] =  A_FAIM;
               test_mange( i );
               mutex.V( );
               philo_prive[ i ].P( );
    }
    poser_fourchette (int i){
               mutex.P( );
               Etat_Philo[ i ] =  PENSE;
               test_mange((i+1)%N );
               test_mange((i-1+N)%N );
               mutex.V( );
    }

Troisième solution: C'est la même chose que la première solution sauf qu'un philosophe est gaucher et ceci afin d'éviter l'interblocage.

sem fourch[ N ]  = {1,........1}


    prendre_fourchette ( int i ){
          if ( i == N-1) {                   // N-1 : le philosophe gaucher
               fourch[ (i + 1) % N ].P( );
               fourch[ i ].P( );  
          }
          else{	
               fourch[ i ].P( );             //demande/prend de la fourchette de gauche
               fourch[ (i + 1) % N ].P( );   //demande/prend la fourchette de droite 
          }        
    }

poser_fourchette ne change pas

    poser_fourchette ( int i ){
       fourch[ i ].V( );            //pose de la fourchette de gauche
       fourch[ (i + 1) % N ].V( );  //pose la fourchette de droite 
    }

Quatrième solution :

On modifie la solution 1 de sorte que les philosophes ne puissent pas prendre tous en même temps la fourchette de droite. On introduit pour cela un sémaphore dont le compteur est égal à N-1

  sem s = N-1;
       prendre_fourchette ( int i ){
               s.P( );
               fourch[ i ].P( );            //demande/prend de la fourchette de gauche
               fourch[ (i + 1) % N ].P( );  //demande/prend la fourchette de droite 
               s.V( );
       }

Cinquième solution avec un moniteur :

   Etat = { PENSE ,  MANGE}
   Etat Etat_Philo[ N ] = { PENSE , …............., PENSE}
   cond file_privee [ N ];
      prendre_fourchette ( int i ){
               while (  Etat_Philo[ (i+1)%N ] == MANGE 
                       ||  Etat_Philo[ (i-1+N)%N ] == MANGE ){
                      file_privee[ i ].wait( );
               }
               Etat_Philo  = MANGE;
       }
      poser_fourchette ( int i ){
               if (  Etat_Philo[ (i+2)%N ] == PENSE ) {//si le philosophe de droite a
                                                      //l'opportunité de manger
                        file_privee[ (i+1)%N ].signal( );   //on le réveille si éventuellement il 
                                                           // attend
               }
               if (  Etat_Philo[ (i-2+N)%N ] == PENSE ) {  //si le philosophe de gauche a
                                                           //l'opportunité de manger
                        file_privee[ (i-1+N)%N ].signal;
               }
       }


Producteur consommateur

Des producteurs déposent des messages dans un tampon circulaire de taille N. Des consommateurs retirent et lisent les messages déposés par les producteurs dans le tampon.

Avec les moniteurs

On considère un moniteur composé des procédures deposer(message m) et retirer(message m) et des variables:

     int id_lec = 0;	//indice de la tête de lecture
     int id_ecr = 0;	// indice de la tête d'écriture
     int vides = N;   //nombre de cases libres dans le tampon
     cond  fp ;	//condition d'attente pour les producteurs
     cond  fc ;	//condition d'attente pour les consommateurs

On écrit donc les procédures deposer(message m) et retirer(message m) sachant que puisqu'on est dans un moniteur, l'exécution en exclusion mutuelle est acquise.

     deposer(message m){// si le tampon est plein, on attend
            if (vides == 0){
                 fp.wait( );
            }
            vides --;
            Tampon[id_ecr] = m;
            id_ecr =  (id_ecr + 1)%N;
            fc.signal( );
     }
     retirer(message m){//message est un paramètre  out ici
            if (vides == N){//si le tampon est vide on attend qu'il se remplisse
                fc.wait( );
            }
            vides ++;
            m = Tampon[id_lec];
            id_lec =  (id_lec + 1)%N;
            fp.signal( );
     }

Avec les semaphores

    int id_lec = 0;	//indice de la tête de lecture
    int id_ecr = 0;	// indice de la tête d'écriture
    sem mutex = 1;	//exclusion mutuelle pour les acces aux indices
    sem case_occ = 0; //semaphore qui compte les cases occupées
    sem case_libre = N; //semaphore qui compte les cases libres
    deposer(message m){
           case_libre.P( );
           mutex.P( );
           Tampon[ id_ecr] = m;
           id_ecr = ( id_ecr + 1)%N;
           mutex.V( );
           case_occ.V( );
    }
    retirer(message m){//m est en mode «out»
           case_occ.P( );
           mutex.P( );
           m = Tampon[ id_lec] ;
           id_lec = ( id_lec + 1)%N;
           mutex.V( );
           case_libre.V( );
    }

Imprimables

 Fichier:Producteur consommateur.pdf
 Fichier:Pb philosophes.pdf
 Fichier:Lecteurs redacteurs.pdf
 Fichier:Boites aux lettres serveurs impression.pdf
 Fichier:Boites aux lettres 2.pdf