Les Mécanismes de Synch PDF

Communication interprocessus 1  Plan 1. Introduction 2. Sections critiques et exclusion mutuelle 3. Exclusion mutuelle par attente active 1. Le masquage des interruptions 2. Les variables de verrouillage 3. L’alternance stricte 4. La solution de Pete...

Communication interprocessus 1  Plan 1. Introduction 2. Sections critiques et exclusion mutuelle 3. Exclusion mutuelle par attente active 1. Le masquage des interruptions 2. Les variables de verrouillage 3. L’alternance stricte 4. La solution de Peterson 4. Exclusion mutuelle sans attente active a. Les primitives sleep et wakeup b. Les sémaphores 2  Introduction Sur une plateforme multiprogrammée les processus ont généralement besoin de communiquer pour compléter leurs tâches. L’exécution d’un processus peut être affecter par l’exécution des autres processus ou il peut affecter lui-même leurs exécutions. La communication interprocessus est assurée généralement via des données partagées qui peuvent se trouver dans la mémoire principale ou dans un fichier. Les accès concurrents (simultanés) à des données partagées peuvent conduire à des incohérences dans les résultats obtenus. 3  Introduction: exemple illustratif Exemple : la spoule d’impression Démon d’impression Processus A’ … 3 2 1 0 … f2 f1 f0 Répertoire de spoule Processus B Variable partagée in=3 Schéma d’exécution: A : lire in, B : lire in, next_free_slot = 3 next_free_slot = 3, Interruption: la CPU bascule vers entrée3 = fichierB, le processus B in = 4 A : entrée3 = fichierA, in = 4 4 Problème: le fichierB ne sera jamais imprimé  Sections critiques et exclusion mutuelle Le problème précédent est dû aux conflits d’accès à la même ressource. La partie du programme à partir de laquelle on accède à la ressource partagée est appelée section (région) critique. Solution: L’exclusion mutuelle est une méthode qui assure qu’un seul processus est autorisé d’accéder à une ressource partagée; les autres processus seront exclus de la même activité. A entre dans sa section A quitte sa section critique critique A B quitte sa section critique B t1 t2 t3 t4 5 B tente d’entrer dans sa B entre dans sa section section critique critique Sections critiques et exclusion mutuelle Quatre conditions doivent être vérifier pour assurer l’exclusion mutuelle: 1. Deux processus ne doivent pas se trouver simultanément dans leurs sections critiques.(exclusion mutuelles) 2. Aucun processus à l’extérieur de sa section critique ne doit bloquer les autres processus.(progression) 3. Aucun processus ne doit attendre indéfiniment pour entrer dans sa section critique.(famine- interblocage) 4. Il ne faut pas faire d’hypothèse quant à la vitesse ou le nombre de processeurs  Exclusion mutuelle par attente active Un processus désirant entrer dans une section critique doit être mis en attente jusqu’à ce que la section critique devient libre. Un processus quittant la section critique doit le signaler aux autres processus. Algorithme d’accès à une section critique : Entrer_Section_Critique () Section_Critique() L’attenteQuitter_Section_Critique() peut être : Active : la procédure Entrer_Section_Critique est une boucle dont la condition est un test qui porte sur des variables indiquant la présence ou non d’un processus en Section critique. Non active : le processus passe dans l’état endormi et ne sera réveillé que 7 lorsqu’il sera autorisé à entrer en section critique.  Solutions de l’exclusion mutuelle par attente active Solution 1: Masquage des interruptions ▪ Lorsqu’un processus entre en section critique il doit masquer les interruptions. Pas de commutation de processus ▪ Lorsqu’ il quitte sa section critique il doit restaurer les interruptions. C’est une solution matérielle qui permet de résoudre complètement le problème. Mais elle est dangereuse en mode utilisateur s’il oublie de restaurer les interruptions. 8  Solutions de l’exclusion mutuelle par attente active Solution 2: Variables de verrouillage Un verrou est variable binaire partagée qui indique la présence d’un processus en section critique. si verrou=0 alors section critique libre si verrou=1 alors section critique occupée void entrer_Section_Critique () Void { quitter_Section_Critique while (verrou == 1) ; { verrou=1 ; verrou=0 ; } } Cette solution ne garantie pas l’exclusion mutuelle car le verrou est une variable partagée qui peut constituer aussi une section critique. 9  Solutions de l’exclusion mutuelle par attente active Solution 3: Alternance stricte Tour est une variable partagée qui indique le numéro de processus autorisé à entrer en section critique. void entrer_Section_Critique (int Void process) quitter_Section_Critique { () while (Tour!=process) ; Tour = (Tour+1) %N ; }L’alternance stricte est une solution simple } et facile a implémenter. Mais, un processus qui possède Tour peut ne pas être intéressé immédiatement par la section critique et en même temps il bloque un autre processus qui demande. 10 Problème de famine  Solutions de l’exclusion mutuelle par attente active Solution 4: Solution de Peterson #define FAUX 0 #define VRAI 1 Void #define N 2 quitter_Section_Critique int tour ; () int interesse[N] ; { void entrer_Section_Critique (int process) { Cette solution assure interesse[process]=FAUX complètement l’exclusion int autre ; ; mutuelle. autre = 1-process ; } interesse[process]=VRAI; attend sa section critique tour = process ; while (tour == process && processeur inutilement interesse[autre] == VRAI) ; (attente active). 11 }  Exclusion mutuelle sans attente active L’idée est qu’un processus qui ne peut pas entrer en section critique passe à l’état bloqué au lieu de consommer le temps processeur inutilement. Il sera réveillé lorsqu’il pourra y entrer. Les primitives Sleep et Wakeup: Le système d’exploitation offre deux appels système: 1. Sleep (dormir) qui bloque le processus appelant. 2. Wakeup (réveiller) qui réveille le processus donné en argument. 12  Exclusion mutuelle sans attente active Application des primitives Sleep et Wakeup au modèle Producteur Consommateur: Producteur … f2 f1 f0 Tampon Variable partagée compteur=3 Consommateur Deux processus (le producteur et le consommateur) coopèrent en partageant un même tampon: Le producteur produit des objets qu’il dépose dans le tampon. Le consommateur retire des objets du tampon pour les consommer. 13  Exclusion mutuelle sans attente active #define N 100 while (TRUE) int compteur = 0 ; if (compteur == 0) sleep() void producteur () { ; while (TRUE) retirer_objet(); retirer l’objet du { tampon //produire produire_objet() ; l’objet compteur = compteur – if (compteur == N) sleep () ;//si suivant 1; tampon plein ,dormir if (compteur == N-1) mettre_objet() ; // mettre l’objet dans tampon wakeup (producteur) ;// compteur = compteur + 1 ; //nb objets réveiller le producteur dans tampon inc. consommer_objet(…) ; if (compteur == 1) // réveiller le } consommateur } wakeup(consommateur) ; 14 }  Exclusion mutuelle sans attente active Analyse de cette solution : 1. L’accès à la variable compteur n’est pas protégé, ce qui peut entraîner des incohérences dans les valeurs prises par cette Variable. 2. Réveils perdus : c’est le principal défaut de ce mécanisme. Un signal wakeup envoyé à un processus qui ne dort 15  Les sémaphores Pour remédier au problème des réveils en attente (les wakeup perdus), l’idée est d’employé une variable entière appelée: Sémaphore à laquelle est associée une file d’attente des processus bloqués. sémaphore=0 🡪 aucun réveil n’est mémorisé sémaphore>0 🡪 un ou plusieurs réveils sont en attente Un sémaphore s est manipulé par les opérations : 1. down(s) : - décrémente la valeur de s si s>0, - si s=0, alors le processus est mis en attente. 2. up(s) : - incrémente la valeur de s, - si un ou plusieurs processus sont en attente sur ce 16 sémaphore, l'un d'entre eux est réveillé,  Un sémaphore S est un entier qui est accessible seulement par ces 2 opérations atomiques et mutuellement (en revanche) exclusives (spécifique) : down(s) : -La vérification du compteur -La décrémentation du compteur/Le passage en sommeil dans le cas d’un compteur égal à zéro. up(s) :- La vérification du compteur -L’incrémentation du compteur/Réveil d’un processus* 17  Les sémaphores Pour assurer l’exclusion mutuelle un sémaphore peut être programmé de la manière suivante : initialisation mutex = 1 down (mutex) up (mutex) 18  Initialisation d'un sémaphore function Init(semaphore sem, int val) { disable_interrupt; sem.K:= val; enable_interrupt; } 19  Opération Down(sem) function Down(semaphore sem) { disable_interrupt; if (sem.K == 0) { L.suivant = processus_courant; processus_courant.state= bloque; reordonnancement = vrai; } sem.K=sem.K-1; enable_interrupt; 20 }  Opération Up(sem) function Up(semaphore sem) { disable_interrupt; sem.K=sem.K+1; if (not L.vide) { processus_reveille= L.tete; processus_reveille.state = prêt; reordonnancement = vrai; } enable_interrupt; 21 }  Les sémaphores Application au modèle Producteur / Consommateur : Trois sémaphores sont nécessaires: 1. plein: compte le nombre de places occupées 2. vide : compte le nombre de places libres 3. Mutex : assure que le producteur et le consommateur n'accèdent jamais en même moment à la mémoire tampon. 22  Les sémaphores Application au modèle Producteur / Consommateur : #define N 100 typedef int semaphore; semaphore mutex=1 ; semaphore vide=N; void producteur () { void consommateur () { Semaphore plein=0; { produire_objet() ; { down(plein); //dec nb de down(vide); //dec nb de places place occupée vide down(mutex); // entrer s_c down(mutex); // entrer s_c mettre_objet() ; retirer_objet(); up(mutex); // quitter s_c up(mutex); // quitter s_c 23 up(plein) }// inc nb de place up(vide); // inc nombre des places vides occupée