Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

PROBLÈMES CLASSIQUES DE SYNCHRONISATION Anissa Omrane 1 Le dîner des philosophe

PROBLÈMES CLASSIQUES DE SYNCHRONISATION Anissa Omrane 1 Le dîner des philosophes Cinq philosophes chinois sont autour d’une table ronde, chaque philosophe a sa propre assiette et une baguette est disponible entre chaque pair d’assiettes. Les philosophes réitèrent les phases de penser et de manger. Pour manger un philosophe a besoin de deux baguettes et il est autorisé à prendre une seule baguette à la fois. Il est clair que c’est impossible que les philosophes puissent manger en même temps. 2 Le dîner des philosophes Le problème consiste à décrire l’algorithme de chaque philosophe pour qu’ils puissent alterner à l’infini des phases de manger et de penser sans qu’il y ait inter-blocages ou famines. 3 Le dîner des philosophes Les philosophes mangent ou pensent Mangent avec 2 baguettes Prennent une seule baguette à la fois Comment prévenir les interbloquages ? 4 Algorithme trivial Philosophe(i){ while (Vrai) { pense( ); prendre_ baguette(i); prendre_ baguette((i+1)%5); manger ( ); poser_ baguette( i ); poser_ baguette((i+1)%5); } } 5 Critiques de la solution triviale Un problème d'inter-blocage, si les N philosophes décident de manger en même temps: En appliquant la procédure prendre_baguette(i). Tous les philosophes détiennent la baguette de droite et attendent que celle de gauche se libère. Solution possible En introduisant une notion de délais aléatoires c’est-à-dire si un philosophe obtient la première et n’obtient pas la seconde baguette, il dépose sa baguette et recommence après un délai aléatoire. Mais cette amélioration peut conduire à une situation de famine. 6 Solution avec les sémaphores Un philosophe qui veut prendre les baguettes pour 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 baguettes et donc se met en attente. Si les deux philosophes à côté ne mangent pas alors il peut prendre les deux baguettes et déclarer qu'il mange. Quand le philosophe a fini de manger, il déclare 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. 7 Solution avec les sémaphores Un sémaphore est attribué à chaque philosophe.  Etat = { PENSE , MANGE , A_FAIM} sem Sem_prive [ N ] //initialisés à zéro Etat Vect_etat[ N ] = { PENSE, …......., PENSE} sem mutex = 1 Philosophe(i){ while (Vrai){ pense( ); prendre_baguettes(i); manger ( ); poser_baguettes( i ); } } 8 Solution avec les sémaphores prendre_baguette (int i) { P(mutex); Vect_etat [ i ] = A_FAIM; test_mange( i ); V(mutex); P(Sem_prive [ i ]); } 9 Solution avec les sémaphores poser_baguette (int i) { P(mutex); Vect_etat [ i ] = PENSE; test_mange((i+1)%N ); test_mange((i-1+N)%N ); V(mutex); } 10 Solution avec les sémaphores test_mange( int i ) { if ( Vect_etat [ i ] == A_FAIM && Vect_etat [ (i+1)%N ] != MANGE && Vect_etat [ (i-1+N)%N ] != MANGE ) { Vect_etat [ i ] = MANGE; V(Sem_prive[ i ]); } } 11 Solution avec un moniteur monitor dinerPhilosophe { // début moniteur enum { PENSE; A_FAIM, MANGE) Etat [5] ; condition File_privé[5]; initialization_code() { for (int i = 0; i < 5; i++) Etat[i] = PENSE; } 12 Solution avec un moniteur // suite moniteur void prendre_baguettes (int i) { Etat[i] = A_FAIM; test(i); if (Etat[i] != MANGE) File_privé [i].wait; } 13 Solution avec un moniteur // suite moniteur void deposer_baguettes (int i) { Etat[i] = PENSE; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } 14 Solution avec un moniteur // suite moniteur void test (int i) { if ( (Etat[(i + 4) % 5] != MANGE) &&(Etat[i] == A_FAIM) &&(Etat[(i + 1) % 5] != MANGE) ) { Etat[i] = MANGE ; File_privé[i].signal () ; } } }// fin Moniteur 15 Solution avec un moniteur Philosophe(i) { while (Vrai) { pense( ); dinerPhilosophe.prendre_baguettes(i); manger ( ); dinerPhilosophe.poser_baguettes(i); } } 16 Le problème des lecteurs/rédacteurs Problème classique qui permet de modéliser les accès à des objets. Par exemple: Accès à un fichier Accès à un enregistrement dans un fichier ou une base de données Dans une base de données, afin de conserver une cohérence, les contraintes sont les suivantes : Plusieurs lecteurs doivent pouvoir lire la base de données en même temps ; Si un rédacteur est en train de modifier la base de données, aucun autre utilisateur (ni rédacteur, ni lecteur) ne doit pouvoir y accéder. 17 Plusieurs lecteurs peuvent lire simultanément les données; Les rédacteurs s’excluent mutuellement; Les lecteurs et les rédacteurs s’excluent mutuellement. Il existe plusieurs variantes du problème : selon la priorité accordée aux intervenants: Priorité aux lecteurs (famine possible des rédacteurs) Priorité aux rédacteurs (famine possible des lecteurs) Accès aux données selon les ordres des arrivées. Toutes les demandes de lecteur qui se suivent sont satisfaites en même temps. 18 Le problème des lecteurs/rédacteurs Variante n°1 : Priorité aux lecteurs. Les règles sont les suivantes: Un lecteur peut accéder à la ressource si : Le nombre de rédacteurs en cours d’écriture vaut 0 Un rédacteur peut accéder à la ressource si: le nombre de lecteurs en attente de la ressource vaut 0 le nombre de lecteurs en cours de lecture vaut 0 Le nombre de rédacteurs en cours d’écriture vaut 0  19 Le problème des lecteurs/rédacteurs Variante n°1 : Priorité aux lecteurs Une variable nbLecteurs mutexLecteurs, qui est en charge de protéger l’accès à la variable nbLecteurs. redacteur, qui permet au premier lecteur qui accède la ressource de bloquer les futurs rédacteurs. Il permet également au rédacteur accédant la ressource de bloquer les lecteurs pendant l’écriture. mutexRedacteurs, qui permet au rédacteur accédant la ressource de bloquer les autres rédacteurs. De ce fait, un seul rédacteur ne peut être en attente du sémaphore redacteur, empêchant ainsi un rédacteur de brûler la priorité à un lecteur. 20 Le problème des lecteurs/rédacteurs Variante n°1 : Priorité aux lecteurs Sémaphore mutexLecteurs initialisé à 1 ; Sémaphore mutexRedacteurs initialisé à 1 ; Sémaphore redacteur initialisé à 1 ; int nbLecteurs=0; 21 Le problème des lecteurs/rédacteurs Lecteur void debutLecture() { P(mutexLecteurs); nbLecteurs++; if (nbLecteurs==1) P(redacteur); V(mutexLecteurs); } void finLecture() { P(mutexLecteurs); nbLecteurs--; if (nbLecteurs==0) V(redacteur); V(mutexLecteurs); } Rédacteur Void debutEcriture() { P(mutexRedacteurs); P(redacteur); } void finEcriture() { V(redacteur); V(mutexRedacteurs); } 22 Le problème des lecteurs/rédacteurs 23 Le problème des lecteurs/rédacteurs Lecteur () Rédacteur() debutLecture() Lectures(); finLectures() debutEcriture() Rédaction () finEcriture() Variante n°2 : Priorité aux rédacteurs. Un lecteur ne peut lire que si aucun rédacteur n’est présent ou en attente. Les règles sont les suivantes : Un lecteur peut accéder à la ressource si: Le nombre de rédacteurs en cours d’écriture vaut 0 Le nombre de rédacteurs en attente d’écriture vaut 0 Un rédacteur peut accéder à la ressource si: Le nombre de lecteurs en cours de lecture vaut 0 Le nombre de rédacteurs en cours d’écriture vaut 0 24 Le problème des lecteurs/rédacteurs Une variable nbLecteurs mutexLecteurs, qui permet de bloquer les lecteurs pendant que des écritures sont en cours. mutexRedacteurs, qui permet de bloquer les rédacteurs pendant que des écritures ou des lectures sont en cours. mutex, qui est en charge de protéger l’accès à la variable nbLecteurs. redacteur, qui permet au premier lecteur qui accède la ressource de bloquer les potentiels rédacteurs. lecteur, qui permet au premier rédacteur arrivé de bloquer les potentiels futurs lecteurs. 25 Le problème des lecteurs/rédacteurs Variante n°2 : Priorité aux rédacteurs. semaphore mutexLecteurs initialisé à 1; semaphore mutexRedacteurs initialisé à 1; semaphore lecteur initialisé à 1; semaphore redacteur initialisé à 1; semaphore mutex initialisé à 1; int nbLecteurs, nbRedacteurs; Priorité aux rédacteurs nbLecteurs=0; nbRedacteurs=0; 26 Le problème des lecteurs/rédacteurs 27 Le problème des lecteurs/rédacteurs Lecteur Rédacteur void debutLecture() { P(mutexLecteurs); P(lecteur); P(mutex); nbLecteurs++; if (nbLecteurs==1) P(redacteur); V(mutex); V(lecteur); V(mutexLecteurs); } void finLecture() { P(mutex); nbLecteurs--; if (nbLecteurs==0) V(redacteur); V(mutex); } void debutEcriture() { P(mutexRedacteurs); nbRedacteurs++; if (nbRedacteurs==1) P(lecteur); V(mutexRedacteurs); P(redacteur); } void finEcriture() { V(redacteur); P(mutexRedacteurs); nbRedacteurs--; if (nbRedacteurs==0) V(lecteur); V(mutexRedacteurs); } Variante n°3 : FIFO. Les demandes d’accès à l’objet sont servies dans l’ordre d’arrivée. S’il y a plusieurs lecteurs consécutifs, ils sont servis ensemble. Les règles sont les suivantes : Un lecteur peut accéder à la ressource si: Le nombre de rédacteurs en cours d’écriture vaut 0 Un rédacteur peut accéder à la ressource si: Le nombre de lecteurs en cours de lecture vaut 0 Le nombre de rédacteurs en cours d’écriture vaut 0 28 Le problème des lecteurs/rédacteurs Variante n°3 : FIFO. Une variable nbLecteurs. mutex, qui est en charge de protéger l’accès à la variable nbLecteurs.  redacteur, qui permet au premier lecteur qui accède la ressource de bloquer les futurs rédacteurs. Il permet également au rédacteur accédant à la ressource de bloquer les lecteurs pendant l’écriture. fifo, une ﬁle d’attente dans laquelle passent tous les lecteurs et les rédacteurs. 29 Le problème des lecteurs/rédacteurs semaphore mutex initialisé à 1; semaphore fifo initialisé à 1; semaphore redacteur initialisé à 1; int nbLecteurs; nbLecteurs=0; 30 Le problème des lecteurs/rédacteurs 31 Lecteur Rédacteur void debutLecture() { P(fifo); P(mutex); nbLecteurs++; if uploads/Philosophie/ problemes-classiques-de-synchronisation.pdf