Systèmes d’Exploitations Avancés

Systèmes d’Exploitations Avancés Chapitre III : Synchronisation et communication inter-processus Amine DHRAIEF Mastère professionnel en Modélisation, Bases de Données et Intégration des Systèmes ESEN, Univ. Manouba Contexte: Synchronisation Les relations entre processus peuvent prendre deux formes : compétition pour l’usage d’une ressource partagée ; coopération pour l’exécution coordonnée d’une tâche commun L’exemple le plus courant de compétition est celui de l’allocation de processeur. Une politique d’allocation attribue le processeur, par tranches de temps successives, aux processus qui en ont besoin. 11/10/2016 2 Contexte: Synchronisation Un exemple simple de coopération est celui de la transmission de messages entre deux processus à travers une zone de mémoire commune (la boîte aux lettres) : si la boîte aux lettres est vide, le processus destinataire doit attendre que le processus émetteur y dépose un message ; si la boîte aux lettres est pleine (c’est à- dire si l’on ne peut plus y déposer de message sans détruire un de ceux qui s’y trouvent), le processus émetteur doit attendre que le récepteur retire un message. Dans une situation intermédiaire où la boîte aux lettres n’est ni vide ni entièrement remplie, les deux processus peuvent fonctionner en parallèle à condition de ne pas accéder simultanément au même message. 11/10/2016 3 Contexte: Synchronisation On appelle synchronisation la mise en œuvre des relations entre processus en vue de respecter les contraintes de coopération. L’exemple précédent montre que la synchronisation nécessite de « faire attendre » un processus jusqu’à ce qu’une condition de passage soit réalisée. Cela peut être obtenu de deux manières : par attente active : on fait boucler le processus en attendant que la condition soit réalisée ; par blocage : on fait passer le processus dans un état dit bloqué, dans lequel il cesse de progresser ; lorsque la condition de passage est réalisée, le processus est explicitement débloqué (ou réveillé), et reprend son exécution. 11/10/2016 4 Context: Synchronisation Pour l’étude de la synchronisation, nous considérons l’exécution des processus d’un point de vue purement logique, sans tenir compte des vitesses réelles d’exécution. De ce point de vue, il importe peu que l’exécution se fasse en parallélisme réel ou en pseudo-parallélisme 11/10/2016 5 Contexte: Communication entre Processus Le système d'exploitation gère les processus. Malgré cela, chaque processus : Est une entité autonome et indépendante ; Vit isolé dans son propre espace mémoire ; → Par conséquent : Les processus peuvent se trouver en conflit pour l'accès à certaines ressources communes La solution : → Mécanisme de communication inter-processus : échange d'informations entre les processus en vue de résoudre un problème → Nécessite de la mise en œuvre de mécanismes dits de synchronisation pour gérer ces conflits. 11/10/2016 6 Contexte: Communication entre Processus Les communications inter processus (Inter- Process Communication ou IPC) regroupent l'ensemble des mécanismes permettant la communication et la synchronisation entre processus concurrents (ou distants). 11/10/2016 7 SYNCHRONISATION ENTRE PROCESSUS 11/10/2016 8 Exemple1 : Opérations bancaires Programme 1 exécuté par processus 1 1. courant1 = lire compte (1362A) 2. nouveau1 = courant 1+ 1000 3. écrire compte (1362A, nouveau1) Programme 2 exécuté par processus 2 1. courant2 = lire compte (1362A) 2. nouveau2 = courant2 - 3000 3. écrire compte (1362A, nouveau2) 11/10/2016 9 Exemple 1 : Opérations bancaires Les processus P1 et P2 partagent une zone de mémoire (compte en banque). On ne s'intéresse pas ici a la réalisation concrète de cette opération de partage Les deux processus se déroulent en parallèle L'exécution des opérations peut être entrelacée dans un ordre quelconque, à condition de respecter l'ordre local pour chacun des processus. 11/10/2016 10 Exemple 2 : spool d'impression Quand un processus veut imprimer un fichier, il doit placer le nom de ce fichier dans un répertoire spécial, appelé répertoire de spool. Un autre processus, le démon d'impression, vérifie périodiquement s'il y a des fichiers à imprimer. Si c'est le cas, il les imprime et retire leurs noms du répertoire. 11/10/2016 11 Exemple 2 : spool d'impression 11/10/2016 12 Exemple 2 : spool d'impression Supposons que : Le répertoire d'impression ait un très grand nombre d'emplacements, numérotes 0,1,...,N. Chaque emplacement peut contenir le nom d'un fichier à imprimer; Tous les processus partagent la variable IN qui pointe sur le prochain emplacement libre du répertoire ; Deux processus A et B veulent placer chacun un fichier dans la file d'impression et que la valeur de IN est 7 ; Le processus A place son fichier à la position IN qui vaut 7. Une interruption d'horloge arrive immédiatement après et le processus A est suspendu pour laisser place au processus B; Ce dernier place également son fichier à la position IN qui vaut toujours 7 et met à jour IN qui prend la valeur 8. Il efface ainsi le nom du fichier place par le processus A; Lorsque le processus A sera relancer, il met à jour la valeur de IN qui prend la valeur 9. 11/10/2016 13 Exemple 2 : spool d'impression • Le fichier du processus A ne sera jamais imprimé; • IN ne pointe plus sur le prochain emplacement libre. 11/10/2016 14 Problèmes et solution Le problème provient du fait que le processus B a utilisé une variable partagée avant que A ait fini de s'en servir. On dit que A et B sont dans des situations de concurrence. Pour éviter ces situations de concurrence, il faut une synchronisation des processus, C'est-à-dire empêcher que plus d'un processus ne puisse accéder a des ressources partagées. Il faut donc réaliser l'exclusion mutuelle dans des parties de programme qui concernent l'accès à des ressources partagées. Ces parties sont des sections critiques. 11/10/2016 15 Définition • Synchronisation: Si un des processus impliqués dans l’accès en parallèle à la ressource partagée modifie son contenu; Si les processus en accès simultanés sont tous en mode consultation , il n'y a pas de problème de synchronisation puisque la ressource partagée n'est pas modifié. 11/10/2016 16 Définition • Objet critique: Objet qui ne peut être accède simultanément. Exemple : imprimantes, mémoire, fichiers, variables etc. L'objet critique de l'exemple du spool d'impression précédent est la variable partagée IN. 11/10/2016 17 Définition Section critique: Ensemble de suites d'instructions qui opèrent sur un ou plusieurs objets critiques (partie de code devant être exécutée de manière atomique) qui peuvent produire des résultats imprévisibles lorsqu'elles sont exécutées simultanément par des processus différents. Ainsi, la section critique de l'exemple du spool d'impression est : Lecture de la variable; Insertion d'un nom de fichier dans le répertoire; Mise à jour de IN . 11/10/2016 18 Conditions pour la survenue d'une exclusion mutuelle 4 conditions doivent être vérifiées pour qu'une exclusion mutuelle ait lieu : Un seul processus, au plus, dans la section critique ; Pas d'hypothèses sur la vitesse des processus (ordonnancement) : la vitesse ou le nombre de processeurs ne peuvent avoir d'influence; Aucun processus s’exécutant à l’extérieur de sa section critique ne doit bloquer d’autres processus Aucun processus ne doit attendre trop longtemps avant d'entrer en section critique. → Comment assurer alors une coopération correcte et efficace des processus ? 11/10/2016 19 Conditions pour la survenue d'une exclusion mutuelle 11/10/2016 20 L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE 11/10/2016 21 L’exclusion mutuelle avec attente active I. Masquage d'interruption : solution naïve II. Les variables de verrouillage III. Alternance stricte IV. Algorithme de Peterson V. Test and Set Lock 11/10/2016 22 Masquage d'interruption: solution naïve Avant d'entrer dans une section critique, le processus masque les interruptions ; Il les restaure à la fin de la section critique ; Il ne peut être alors suspendu durant l‘exécution de la section critique. SOLUTION DANGEREUSE car le processus courant peut, pour diverses raisons, ne pas réactiver les interruptions. La solution n'assure pas l'exclusion mutuelle. 11/10/2016 23 Les variables de verrouillage Une autre tentative pour assurer l'exclusion mutuelle est d'utiliser une variable de verrouillage partagée, verrou, unique, initialisée à 0. Pour entrer en section critique, un processus doit tester la valeur du verrou. Si elle est égale à 0, le processus modifie la valeur du verrou à 1 et exécute sa section critique. A la fin de la section critique, il remet le verrou à 0. Sinon, il attend par une attente active que le verrou devienne égal à 0, c'est-a-dire : while(verrou !=0) ; 11/10/2016 24 Algorithme de verrouillage while verrou != 0 do ; // Attente active end while verrou = 1 Section_critique(); verrou = 0 11/10/2016 25 Algorithme de verrouillage • Entre le moment ou le processus lit verrou et le moment ou il écrit dans le verrou (lecture et écriture étant deux opérations distinctes successives), un autre processus peut intervenir ! → Donc n'assure pas l'exclusion mutuelle. 11/10/2016 26 Alternance stricte • Une autre tentative pour assurer l'exclusion mutuelle est de définir une variable tour, initialisée à 0 qui mémorise le tour du processus qui doit entrer en section critique. 11/10/2016 27 Exemple : alternance stricte // Processus P1 while (TRUE) { while (tour !=0)/ loop / ; Section critique() ; tour = 1 ; Section noncritique() ; ... } // Processus P2 while (TRUE) { while (tour !=1) )/ loop /; Section critique() ; tour = 0 ; Section noncritique() ; ... } 11/10/2016 28 Alternance stricte Exemple : Soient 2 processus P1 et P2 : Chacun des deux processus ne peut entrer dans sa section critique que si la valeur de tour est égale à son numéro (0 ou 1) ; Supposons que le processus P1 lise tour et constate que sa valeur est 0 ; il entre dans sa section critique ; Si le processus P2 lit à son tour (valeur 0), il doit attendre dans une boucle le passage de tour à 1 (attente active) ; Quand le processus P1 sort de sa section critique, il met tour à 1. Le processus P2 peut alors entrer dans sa section critique ; quand il en sortira, il mettra tour à 0. 11/10/2016 29 Problème de l’alternance stricte Mais imaginons que le processus P1 s'arrête ; le processus P0 pourra entrer encore une fois dans sa section critique, mais sera ensuite bloqué (violation de la condition 4). Plus encore, on peut imaginer que le processus P1 boucle indéfiniment dans sa section non critique, le processus P0 finira également par être bloqué (violation de la règle 3) ; Cette solution n'assure pas l'exécution mutuelle. 11/10/2016 30 Algorithme de Peterson L'algorithme de Peterson est un algorithme d'exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Il est constitué de deux parties : le protocole d'entrée dans la section critique et le protocole de sortie. Il a été publié par Gary Peterson en 1981. Combinaison de Intervention tour à tour des processus Variable de verrous Variables d’avertissement (warning variables) 11/10/2016 31 Algorithme de Peterson #define FALSE 0 #define TRUE 1 #define N 2 /* number of processes / int turn; / whose turn is it? / int interested ; / all values initially 0 (FALSE)*/ void enter_region(int process) /* process is 0 or 1 */ { int other; /* number of the other process / other = 1 - process; / the opposite of process / interested = TRUE; / show that you are interested / turn = process; / set flag / while (turn == process && interested == TRUE) / null statement */; } void leave_region(int process) /* process: who is leaving */ { interested = FALSE; /* indicate departure from critical region */ } 11/10/2016 32 Algorithme de Peterson Avant d'utiliser les variables partagées (par exemple, avant d'entrer dans sa région critique), chaque processus appelle enter_region avec son numéro de processus, 0 ou 1, en tant que paramètre. Cet appel le fera attendre. Une fois qu'il a terminé avec les variables partagées, le processus appelle leave_region pour indiquer qu'il s’est terminé et pour permettre au deuxième processus d'entrer. 11/10/2016 33 Algorithme de Peterson L'algorithme de Peterson est un algorithme d'exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Il est constitué de deux parties : le protocole d'entrée dans la section critique et le protocole de sortie. Il a été publié par Gary Peterson en 1981. Combinaison de Intervention tour à tour des processus Variable de verrous Variables d’avertissement (warning variables) 11/10/2016 34 Algorithme de Peterson Voyons comment cette solution fonctionne. Initialement, aucun des processus n’est dans sa section critique. Maintenant, le processus 0 exécute enter_region. Il indique son intérêt en définissant sa ensembles élément de tableau et initialise turn à 0. Si processus 1 n'est pas intéressé, enter_region se termine immédiatement. Si le processus 1 appelle maintenant enter_region, il se bloquera jusqu'à ce interested[0] sera à FALSE, un événement qui ne se produit que lorsque le processus 0 appel leave_region et quitte le section critique. 11/10/2016 35 Algorithme de Peterson Considérons maintenant le cas où les deux processus exécutent enter_region presque simultanément. Chacun va enregistrer son numéro de processus dans turn. Le dernier enregistrement est celui qui sera considérer. Supposons que le processus 1 enregistre le dernier, donc turn est à 1. Lorsque les deux processus sont à l'instruction while Le processus 0 l'exécute zéro fois et entre dans sa section critique. Le processus 1 boucles et n’entre pas dans sa section critique 11/10/2016 36 Test and Set Lock • TSL RX, LOCK → tester et positionner le verrous Lit le contenu du mot mémoire lock dans le registre RX Puis stocke une valeur différente de 0 à l’adresse mémoire lock • Ces opérations sont indivisibles → verrouillage du bus mémoire 11/10/2016 37 Test and Set Lock Le verrouillage du bus mémoire est différent de la désactivation des interruptions Désactiver les interruptions lorsqu’on fait une lecture suivi d’un écriture n’empêche pas un autre processeur(cœur) d’accéder via le bus mémoire au mot mémoire entre la lecture et l’écriture L’unique solution: verrouiller le bus mémoire 11/10/2016 38 Test and Set Lock Les ordinateurs multiprocesseurs ont une instruction atomique indivisible appelée TSL (Test and Set Lock) ; L'instruction TSL (instruction en langage machine) exécute, en un seul cycle, de manière indivisible, le chargement d'un mot mémoire dans un registre et le rangement d'une valeur non nulle à l'adresse du mot chargé 11/10/2016 39 Test and Set Lock • La variable partagée lock coordonne l’accès à la mémoire partagée Lorsque lock et à 0, n’importe quel processus peut la positionner à 1 via l’instruction TSL, puis lire ou écrire dans la mémoire partagée Cela fait, le processus repositionne lock à 1 via l’instruction move. 11/10/2016 40 Test and Set Lock Lorsqu'un processeur exécute l'instruction TSL, il verrouille le bus de données pour empêcher les autres processeurs d'accéder à la mémoire pendant la durée de l'opération Cette instruction peut être utilisée pour établir et supprimer des verrous (assurer l'exclusion mutuelle). 11/10/2016 41 Test and Set Lock enter_region: TSL REGISTER,LOCK |copy LOCK to register and set LOCK to 1 CMP REGISTER,#0 |was LOCK zero? JNE ENTER_REGION |if it was non zero, LOCK was set, so loop RET |return to caller; critical region entered leave_region: MOVE LOCK,#0 |store a 0 in LOCK RET |return to caller 11/10/2016 42 Test and Set Lock 2 processus P1 et P2 exécutent des programmes contenant des sections de code critiques vis- à-vis de l'accès à une certaine ressource. Soit le scenario suivant : P1 démarre le premier, c'est-à-dire le S.E lui attribue d'abord le quantum de temps ; Pendant ce quantum, il rentre dans la section critique après avoir fait TSL , LOCK vaut donc 1 ; La fin de quantum intervient alors que P1 est dans sa section critique ; Le S.E attribue un quantum à P2 qui trouve LOCK à un. Il va donc épuiser le reste du quantum dans la boucle de l'instruction TSL . 11/10/2016 43 Test and Set Lock Le S.E redonne le quantum a P1 qui sort de sa section critique, met LOCK a 0 et termine son quantum ; P2 se voit attribuer un quantum et sort de TSL puisque LOCK vaut 0, et il fait passer LOCK a 1, il rentre dans sa section critique, le reste de son quantum ; si P1 veut maintenant rentrer dans sa section critique, il va être bloque sur TSL comme l'a été P2. 11/10/2016 44 Inconvénient du Test and Set Lock Les inconvénients de cette technique du TSL sont : L'attente active (busy waiting) : un processus qui trouve la variable de synchronisation à 1 continuera à la tester jusqu'à ce qu'elle passe à 0. Il reste donc actif, alors qu'il pourrait être suspendu et range dans une file d'attente ; Le fait qu'on ne sache pas qui va prendre la main : ce problème est lié au précédent. En effet, puisqu'il n'y a pas de gestion de la file des processus en attente sur le passage de la variable à 0, le premier qui obtient une réponse satisfaisante au test entre dans sa section critique. Ce n'est pas forcement celui qui la scrute depuis le plus longtemps ! 11/10/2016 45 Conclusion sur les méthodes d'attente active L’algorithme de Peterson et l'utilisation de TLS apportent des solutions viables, mais au prix d'attentes actives qui consomment du temps CPU ! Un inconvénient important également vient des règles d'ordonnancement. Supposons que l'on ait deux processus H, bloqué et L, actif sur une machine monoprocesseur ; supposons que H possède une priorité plus forte que L et que les règles d'ordonnancement soient telles que si H est prêt, il doit devenir actif. Supposons que L soit dans sa section critique ; à ce moment H passe de l‘état bloqué à l‘état prêt : il faut que L passe à l‘état prêt et H à l‘état actif ; mais H restera indéfiniment dans une attente active car L n'est pas sorti de sa section critique et L ne reviendra pas actif tant que H ne le sera pas! 11/10/2016 46 Conclusion sur les méthodes d'attente active Un autre problème est de vérifier qu'il y a un minimum d’équité entre les deux processus, c'est-a- dire que l'un d'entre eux ne peut pas attendre indéfiniment son tour d'accès à la section critique alors que l'autre y accède un nombre infini de fois. Cette question est plus difficile, de même que la généralisation de la solution à un nombre quelconque de processus. 11/10/2016 47 LE SOMMEIL ET L’ACTIVATION 11/10/2016 48 Sleep and Wakeup Plutôt que des solutions avec attente active qui laissent les processus prêts, il faut rechercher des solutions qui bloquent les processus. Une des plus simples solutions est l'utilisation des appels systèmes SLEEP() et WAKEUP() SLEEP() est un appel système qui bloque le processus appelant jusqu'a son réveil par un autre processus ; WAKEUP(processus) est un appel système qui réveille le processus dont le numéro lui est passe en paramètre. 11/10/2016 49 Sleep and Wakeup • Par exemple, un processus H qui veut entrer dans sa section critique est suspendu si un autre processus B est déjà dans sa section critique. • Le processus H sera réveillé par le processus B, lorsqu'il quitte la section critique. 11/10/2016 50 Problème du producteur- consommateur Problème également connu sous le nom de tampon délimité ( boundred-buffer ) Deux processus partagent un tampon commun de taille fixe L’un d’eux le producteur, place des informations dans le tampon; l’autre le consommateur, les récupère. Peut être généralisé en n producteurs, n consommateurs 11/10/2016 51 Problème du producteur- consommateur Les problèmes se produisent lorsque le producteur souhaite placer un nouvel élément dans le tampon alors que ce dernier est déjà plein La solution pour le producteur est d’entrer en sommeil, pour être réveillé lorsque le consommateur aura supprimé un ou plusieurs éléments du tampon Si le consommateur souhaite récupérer un élément dans le tampon et qu’il constate que celui-ci est vide, il entre en sommeil jusqu’à ce que le producteur ait placé quelque chose dans le tampon, opération qui va le réveiller 11/10/2016 52 Problème du producteur- consommateur Pour effectuer le suivi du nombre d’éléments présent dans le tampon, nous avons besoin d’une variable count. Si le nombre maximal d’élément que le tampon peut contenir est N, le code du producteur commence par effectuer un test pour vérifier que la valeur de count est N. Dans l’affirmative le producteur entre en sommeil, dans la négative, il ajoute un élément au tampon et incrémente count. Le consommateur test si count vaut 0, si c’est le cas, il entre en sommeil. Sinon, il récupère un élément et décrémente le compteur 11/10/2016 53 Problème du producteur-consommateur #define N 100 /* number of slots in the buffer / int count = 0; / number of items in the buffer */ void producer(void) { int item; while (TRUE){ /* repeat forever */ item = produce_item(); /* generate next item / if (count == N) sleep(); / if buffer is full, go to sleep / insert_item(item); / put item in buffer / count = count + 1; / increment count of items in buffer / if (count == 1) wakeup(consumer); / was buffer empty? */ } 11/10/2016 54 } Problème du producteur- consommateur void consumer(void) { int item; while (TRUE){ /* repeat forever */ if (count == 0) sleep(); /* if buffer is empty, got to sleep / item = remove_item(); / take item out of buffer / count = count - 1; / decrement count of items in buffer / if (count == N - 1) wakeup(producer); / was buffer full? / consume_item(item); / print item */ } } 11/10/2016 55 Problème du producteur- consommateur La condition de concurrence peut se produire parce que l’accès au décompte n’est pas contraint. Le tampon est vide, le consommateur vient de lire le décompte pour constater qu’il est à 0 À cet instant, l’ordonnanceur décide d’arrêter l’exécution du consommateur et de commencer l’exécution du producteur Ce dernier insère un élément dans le tampon, incrémente à 0 le décompte et constate qu’’il est alors à 1 Partant du principe qu’il était à 0 et que le consommateur était en sommeil, le producteur appel wakeup pour réveiller le consommateur 11/10/2016 56 Problème du producteur- consommateur Le consommateur n’est pas en en sommeil et le signal wakeup est perdu Lorsque le consommateur s’exécute enfin, il teste la valeur du décompte précédemment lue; puisqu’elle est de 0, il se met en sommeil Tôt ou tard, le producteur remplira le tampon et se mettra également en sommeil Les deux « dormiront » pour toujours 11/10/2016 57 LES SÉMAPHORES 11/10/2016 58 Edsger Dijkstra né à Rotterdam le 11 mai 1930 et mort à Nuenen le 6 août 2002, est un mathématicien et informaticien néerlandais du XXe siècle Citations: « Tester un programme peut démontrer la présence de bugs, jamais leur absence. » « Se demander si un ordinateur peut penser est aussi intéressant que de se demander si un sous-marin peut nager. » « La programmation par objets est une idée exceptionnellement mauvaise qui ne pouvait naître qu'en Californie. » « Les progrès ne seront possibles que si nous pouvons réfléchir sur les programmes sans les imaginer comme des morceaux de code exécutable. » « Autrefois les physiciens répétaient les expériences de leurs collègues pour se rassurer. Aujourd'hui ils adhèrent à FORTRAN et s'échangent leurs programmes, bugs inclus. » « À propos des langages : il est impossible de tailler un crayon avec une hache émoussée. Il est vain d'essayer, à la place, de le faire avec dix haches émoussées. » « Il est pratiquement impossible d'enseigner la bonne programmation aux étudiants qui ont eu une exposition antérieure au BASIC : comme programmeurs potentiels, ils sont mentalement mutilés, au-delà de tout espoir de régénération. » « Le plus court chemin d'un graphe n'est jamais celui que l'on croit, il peut surgir de nulle part, et la plupart du temps, il n'existe pas. » 11/10/2016 59 Les sémaphores En 1965, E.W.Dijkstra suggère d’utiliser un nouveau type de variable entière qui devait permettre de décompter le nombre de wakeup enregistrer pour un usage ultérieur Dans sa proposition il appelait ce nouveau type de variable un sémaphore . Celui-ci pouvait prendre une valeur nulle indiquant qu’aucun wakeup n’était enregistré; ou une valeur positive , si un ou plusieurs wakeup étaient en cours. 11/10/2016 60 Les sémaphores Dijkstra proposait d’exploiter deux opérations, down et up . down sur un sémaphore détermine si sa valeur est supérieur à 0. Si c’est le cas, elle la décrémente et poursuit son activité. Si la valeur est de 0, le processus est placé en sommeil sans que down ne se termine pour l’instant Les activités de vérification, de modification et éventuellement de mise en sommeil sont toutes effectuée dans le cadre d’une action atomique unique et indivisible. 11/10/2016 61 Les sémaphores Il est garanti qu’une fois un sémaphore a démarré, aucun autre processus ne peut y accéder tant que l’opération n’est pas terminé ou bloquée. Cette atomicité est essentiel à la résolution des problèmes de synchronisation ainsi pour éviter les conditions de concurrence. 11/10/2016 62 Les sémaphores L’opération up incrémente la valeur du sémaphore concerné Si un ou plusieurs processus se trouvaient en sommeil sur ce sémaphore, incapable de terminer une opération down antérieure, l’un d’eux est choisi par le système et est autorisé à terminé son down Une fois un up accompli sur un sémaphore contenant des processus en sommeil, le sémaphore sera toujours de 0, mais il contiendra un processus en sommeil en moins. L’opération d’incrémentation du sémaphore et d’éveil d’un processus est également indivisible. Aucun processus ne se bloque jamais en faisant un up 11/10/2016 63 Les sémaphores La méthode habituelle consiste à implémenter les appels up et down en tant qu’appels systèmes Le système désactive toutes les interruptions pendant un très court de temps durant lequel il teste le sémaphore, l’actualise et place si nécessaire le processus en sommeil 11/10/2016 64 Résolution du problème producteur- consommateur avec des sémaphores On utilise trois sémaphore Full : pour compter le nombre d’emplacement occupés Empty : pour compter le nombre d’emplacement vide Mutex : pour s’assurer que le producteur et le consommateur n’accède pas simultanément au tampon 11/10/2016 65 Résolution du problème producteur- consommateur avec des sémaphores Au départ Full = 0 Empty = nombre d’emplacement dans le tampon Mutex = 1 Les sémaphores qui sont initialisés à 1 et qui sont utilisés par deux processus ou plus pour faire en sorte que l’un d’entre eux pourra entrer en section critique à un instant donné, sont appelés sémaphore binaire . Si un processus effectue un down jute avant d’entre en section critique et un up juste avant de la quitter, l’exclusion mutuelle est garantie 11/10/2016 66 Résolution du problème producteur- consommateur avec des sémaphores #define N 100 /* number of slots in the buffer / typedef int semaphore; / semaphores are a special kind of int / semaphore mutex = 1; / controls access to critical region / semaphore empty = N; / counts empty buffer slots / semaphore full = 0; / counts full buffer slots */ 11/10/2016 67 Résolution du problème producteur- consommateur avec des sémaphores void producer(void) { int item; while (TRUE){ /* TRUE is the constant 1 */ item = produce_item(); /* generate something to put in buffer / down(&empty); / decrement empty count / down(&mutex); / enter critical region / insert_item(item); / put new item in buffer / up(&mutex); / leave critical region / up(&full); / increment count of full slots */ } } 11/10/2016 68 Résolution du problème producteur- consommateur avec des sémaphores void consumer(void) { int item; while (TRUE){ /* infinite loop */ down(&full); /* decrement full count / down(&mutex); / enter critical region / item = remove_item(); / take item from buffer / up(&mutex); / leave critical region / up(&empty); / increment count of empty slots / consume_item(item); / do something with the item */ } } 11/10/2016 69 LES MUTEX 11/10/2016 70 Les mutex Quand des décomptes ne sont pas nécessaire, on utilise une version simplifiée des sémaphores ce que l’on appelles des mutex. Ils prennent en charge l’exclusion mutuelle Un mutex est une variable qui peut prendre deux états: déverrouillé ou verrouillés Un seul bit est nécessaire pour la représenter 11/10/2016 71 Les mutex Deux procédures interviennent avec les mutex : mutex lock / mutex unlock Lorsqu’un thread (processus) a besoin d’accéder à sa section critique, il invoque mutex_lock. Si le mutex est déverrouillé (la section critique est donc disponible), l’appel réussit et le thread appelant est libre d’entrer en section critique. Si le mutex est déjà vérrouillé, le thread appelant est bloqué jusqu’à ce que le thread en section critique en ait terminé et appel mutex_unlock. Si plusieurs threads sont bloqués sur le mutex, l’un d’eux est choisi aléatoirement pour prendre possession du verrou. 11/10/2016 72 Les mutex dans pthreads Le thread qui désire entrer dans une région critique doit tout d’abord verrouiller le mutex associé Si le mutex est déverrouillé, le thread peut immédiatement entrer et le verrouillage est fait automatiquement, ce qui empêche d’autres threads d’entrer Si le mutex est déjà verrouillé, le thread appelant est bloqué jusqu'au déverrouillage 11/10/2016 73 Les mutex dans pthreads Appel description * pthread_mutex_init * Crée un nouveau mutex * pthread_mutex_destroy * Détruit un mutex * pthread_mutex_lock * Verrouille un mutex * pthread_mutex_unlock * Déverrouille un mutex 11/10/2016 74 Les mutex dans pthreads • Pthreads offre également un mécanisme de synchronisation autre que les mutex, les variables de condition, Ils permettent à un thread de se bloquer non pas à l’entrée d’un région critique mais en fonction d’une certaine condition • Les mutex et les variables de condition sont u...