Systèmes d’Exploitation II

Systèmes d’Exploitation II Chapitre III : La concurrence et synchronisation des processus Amine DHRAIEF 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 commune L’exemple le plus courant de compétition est celui de l’allocation du processeur. Une politique d’allocation attribue le processeur, par tranches de temps successives, aux processus qui en ont besoin. 01/04/18 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. 01/04/18 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. 01/04/18 4 Contexte: 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 01/04/18 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. 01/04/18 6 Contexte: Communication entre Processus Les communications inter processus (InterProcess Communication ou IPC) regroupent l'ensemble des mécanismes permettant la communication et la synchronisation entre processus concurrents (ou distants). 01/04/18 7 SYNCHRONISATION ENTRE PROCESSUS 01/04/2018 8 Exemple : 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. 01/04/2018 9 Exemple : spool d'impression Spool d’impressi oonn Col2 Spool d’impressi on on 01/04/2018 10 Exemple : 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 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. Le fichier du processus A ne sera jamais imprimé; IN ne pointe plus sur le prochain emplacement libre. 01/04/2018 11 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 à 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. 01/04/2018 12 Définition Problème de 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é. 01/04/2018 13 Définition Objet critique: Objet qui ne peut être accèdé 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. 01/04/2018 14 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 . 01/04/2018 15 Conditions pour la survenue d'une exclusion mutuelle Pour mettre en œuvre correctement l’accès exclusif à une section critique, il faut s’assurer que les propriétés suivantes sont vérifiées. Unicité : Un et un seul processus en secton critque Pas d’excès de politesse : Conditon de Progression Si plusieurs processus sont en atente pour entrer dans leur secton critque, alors qu'aucun ne se trouve en secton critque, l'un d'eux doit pouvoir y rentrer au bout d'un temps fni. Non interblocage : Si un processus est bloqué hors sa secton critque, ce blocage ne doit pas empêcher les autres processus d'entrer en secton critque. Équité : Il n'existe aucun privilège entre les divers processus et l’entrée de la secton critque ne doit pas dépendre de la volonté d’un processus partculier. 01/04/2018 16 Conditions pour la survenue d'une exclusion mutuelle 01/04/2018 17 L’EXCLUSION MUTUELLE AVEC ATTENTE ACTIVE 01/04/2018 18 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 01/04/2018 19 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. 01/04/2018 20 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) ; 01/04/2018 21 Algorithme de verrouillage while verrou != 0 do ; // Attente active end while verrou = 1 Section_critique(); verrou = 0 01/04/2018 22 Algorithme de verrouillage Entre le moment où le processus lit verrou et le moment où 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. 01/04/2018 23 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. 01/04/2018 24 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() ; ... } 01/04/2018 25 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. 01/04/2018 26 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 3). 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. 01/04/2018 27 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) 01/04/2018 28 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 */ } 01/04/2018 29 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. 01/04/2018 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) 01/04/2018 31 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 01/04/2018 32 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 01/04/2018 33 Conclusion sur les méthodes d'attente active L’algorithme de Peterson apporte une solutions viable, 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! 01/04/2018 34 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. 01/04/2018 35 LE SOMMEIL ET L’ACTIVATION 01/04/2018 36 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(processus) SLEEP() est un appel système qui bloque le processus appelant jusqu’à 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. 01/04/2018 37 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. 01/04/2018 38 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 01/04/2018 39 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 01/04/2018 40 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 01/04/2018 41 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? */ } } 01/04/2018 42 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 */ } } 01/04/2018 43 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 01/04/2018 44 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 01/04/2018 45 LES SÉMAPHORES 01/04/2018 46 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. » 01/04/2018 47 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. 01/04/2018 48 LES SÉMAPHORES Dijkstra proposait d’exploiter deux opérations, down et up. down (noté aussi P, P = Probeer ('Try')) 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. 01/04/2018 49 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. 01/04/2018 50 LES SÉMAPHORES L’opération up (noté aussi V, V = Verhoog ('Increment', 'Increase by one')) 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 01/04/2018 51 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 laps de temps durant lequel il teste le sémaphore, l’actualise et place si nécessaire le processus en sommeil 01/04/2018 52 Résolution du problème producteur- consommateur avec des sémaphores On utilise trois sémaphores 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 01/04/2018 53 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é à 1 et qui sont utilisé 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 01/04/2018 54 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 */ 01/04/2018 55 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 */ } } 01/04/2018 56 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 */ } } 01/04/2018 57 Tableau de Jean Huber (1721-1786), le Dîner des philosophes Le dîner des philosophes La situation est la suivante : cinq philosophes (initialement mais il peut y en avoir beaucoup plus) se trouvent autour d'une table ; chacun des philosophes a devant lui un plat de spaghetti ; à gauche de chaque plat de spaghetti se trouve une fourchette. Un philosophe n'a que trois états possibles : penser pendant un temps indéterminé ; être affamé (pendant un temps déterminé et fini sinon il y a famine) ; manger pendant un temps déterminé et fini. La famine La famine est un problème que peut avoir un algorithme d'exclusion mutuelle. Il se produit lorsqu'un algorithme n'est pas équitable, c'est-à-dire qu'il ne garantit pas à tous les threads souhaitant accéder à une section critique une probabilité non nulle d'y parvenir en un temps fini. Le dîner des philosophes Des contraintes extérieures s'imposent à cette situation : quand un philosophe a faim, il va se metre dans l'état « afamé » et atendre que les fourchetes soient libres ; pour manger, un philosophe a besoin de deux fourchetes : c'est-à dire les deux fourchetes qui entourent sa propre assiete; si un philosophe n'arrive pas à s'emparer d'une fourchete, il reste afamé pendant un temps déterminé, en atendant de renouveler sa tentatve Le dîner des philosophes Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger, chacun à leur tour. Une non-solution au problème Une non-solution au problème La procédure take_fork() attend que la fourchette spécifiée soit disponible et s’en saisit Cette solution ne fonctionne pas Supposons que les cinq philosophes prennent leurs fourchette gauche en même temps Aucun ne pourra prendre sa fourchette droite Il y aura un interblocage Le dîner des philosophes Il possible de modifier le programme de la façon suivante Après qu’un philosophe a pris sa fourchette gauche, le code détermine si sa fourchette droite est disponible Si ce n’est pas le cas, le philosophe dépose sa fourchette gauche, attend pendant un certain temps, puis recommence le processus Le dîner des philosophes Cette proposition échoue également Tous les philosophes peuvent reprendre l’algorithme simultanément Chacun prend sa fourchette gauche, puis, constate que sa fourchette droite n’est pas disponible, la repose et attend et ainsi de suite Une telle situation, au cours de laquelle tous les programmes continuent de s’ exécuter indéfiniment mais ne progressent jamais, se nomme privation de ressource (ou famine) Solution au dîner des philosophes On utilise un tableau, appelé state, pour suivre l’état du philosophe: il mange, il pense, ou il a faim et tente de s’emparer des fourchettes. Un philosophe ne peut passer à l’état manger que si aucun de ses voisins ne mange à ce moment la. On utilise un tableau de sémaphore, un par individu, de façon que les philosophe soient bloqués si les fourchettes sont prises Solution au dîner des philosophes Solution au dîner des philosophes Le dîner des philosophes Le problème du dîner des philosophes est intéressant pour modéliser des processus qui entrent en concurrence pour un accès exclusif à un nombre limité de ressources, comme c’est le cas des périphériques d’E/S Un autre problème célèbre est celui des lecteurs et des rédacteurs qui permettent de modéliser les accès aux bases de données. Le problème des lecteurs et des rédacteur Imaginons, par exemple, un système de réservation de billets d’avions, où de nombreux processus entrent en concurrence pour y effectuer des lectures et des écritures. Il serait acceptable que plusieurs processus puissent lire la base de donnée en même temps. Mais si un processus est entrain d’actualiser la base (écriture), aucun autre processus ne doit pouvoir y accéder, pas même en lecture. → Comment programmer ces lecteurs et ces rédacteurs ? 01/04/2018 71 Le problème des lecteurs et des rédacteurs, priorité aux lecteurs ! 01/04/2018 72 Le problème des lecteurs et des rédacteur, priorité aux lecteurs ! Le problème des lecteurs et des rédacteur Supposons que, pendant qu’un lecteur utilise la base, un autre lecteur se connecte. Étant donné que deux lecteurs peuvent consulter la base en même temps, le deuxième lecteur est admis. Un troisième lecteur, et d’autre le seront également s‘ils se présentent. C’est alors qu’un rédacteur arrive. Il ne peut pas être admis à entrer dans la base, car les rédacteurs doivent disposer d’une exclusivité d’accès. Le rédacteur est donc suspendu. Le problème des lecteurs et des rédacteur Tant qu’un lecteur au moins est actif, les lecteurs suivants le sont aussi. Une telle stratégie fait que, tant qu’il y a une succession régulière de lecteurs, ceux-ci entrent dès qu’il arrivent. Le rédacteur sera suspendu jusqu’à ce que plus aucun lecteurs ne soit présents LES MUTEX 01/04/2018 76 Les mutex Quand des décomptes ne sont pas nécessaire, on utilise une version simplifiée des sémaphores qu’on appelle des mutex. Ils prennent en charge l’exclusion mutuelle Un mutex est une variable qui peut prendre deux états: déverrouillée ou verrouillée Un seul bit est nécessaire pour la représenter Les mutex Deux procédure 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à verrouillé, 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. Les mutex dans pthreads Le thread qui désire entrer dans une région critique doit tout d’abord verrouiller le mutex associé. Si ce 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. 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 Les mutex dans pthreads Pthreads offre également un mécanisme de synchronisation autre 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 utilisés conjointement Les mutex dans pthreads Si on considère le scénario de producteur-consommateur : Un thread remplit un tampon, un autre le vide Si le producteur découvre que le tampon est plein, il doit se bloquer jusqu'à ce qu'un emplacement se libère Les mutex permettent de faire ce test atomiquement, ce qui conduira un thread à se bloquer si le tampon est plein → C'est une variable de condition qui permettra de le réactiver Les mutex dans pthreads Appel Description pthread cond init Crée une variable de condition * pthread_cond_destroy * Supprime une variable de condition * pthread_cond_wait * Attend une variable de condition * pthread_cond_signal * Envoie un signal au thread en attente sur une variable de condition * pthread_cond_broadcast * Diffuse un signal aux threads en attente sur une variable de condition Les mutex dans pthreads Les deux opérations de base sur les variables de condition sont pthread cond wait qui bloque le thread appelant pthread cond signal qui le débloque Les raisons pour lesquelles on bloque ou on débloque un thread sont externes : Un thread bloqué attend souvent qu'une ressource se libère ou que soit effectuée une certaine tâche La variable de condition signalera que cela est fait L'appel pthread cond broadcast est utilisé lorsqu'il se peut que plusieurs threads attendent le même signal de réveil Les mutex dans pthreads Il faut noter que les variables de condition, à la différence des sémaphores sont sans mémoire. Si on envoie un signal à une variable de conditon sur laquelle il n'y a aucun thread en atente, le signal est perdu Les mutex dans pthreads Les variables conditions sont représentées par le type pthread cond t. On initialise généralement les conditions de manière statique pthread cond t condition = PTHREAD COND INITIALIZER; On peut aussi employer la fonction pthread cond init( ), en passant un second argument NULL int pthread cond init (pthread cond t * condition, pthread condattr t * attributs); Les mutex dans pthreads Voyons à présent l'utilisation effective d'une condition. Tout d'abord, il faut signaler qu'une condition est toujours associée à un mutex, ceci pour éviter des problèmes de concurrence d'accès sur la variable. Les mutex dans pthreads Examinons d'abord le thread qui doit attendre une condition : 1)On initialise la variable condition et le mutex qui lui est associé. 2)Le thread bloque le mutex . 3)Le thread invoque la routine pthread cond wait() qui attend que la condition soit réalisée. 4)Le thread libère le mutex. Les mutex dans pthreads Ce schéma est a priori surprenant puisqu'il semble que, lorsque le second thread désire signaler la réalisation de la condition, l'accès lui soit interdit, le premier thread ayant bloqué le mutex. Les mutex dans pthreads En fait, la fonction pthread cond wait( ) fonctionne en trois temps : 1)D'abord, elle débloque le mutex associé à la condition, et elle se met en attente. Cette opération est réalisée de manière atomique vis-à-vis de la bibliothèque Pthreads. 2)L'attente se poursuit jusqu'à ce que la réalisation de la condition soit indiquée. 3)La condition étant remplie , la fonction termine son attente et bloque à nouveau le mutex , avant de revenir dans le programme appelant Les mutex dans pthreads Les mutex dans pthreads mutex de type pthread mutex t. L'initialisation statique d'un mutex se fait à l'aide de la constante PTHREAD MUTEX INITIALIZER pthread mutex t mutex = PHTREAD MUTEX INITIALIZER; Exemple 1 #include #include #include #include static void * routine threads (void * argument); static int aleatoire (int maximum); pthread mutex t mutex stdout = PTHREAD MUTEX_INITIALIZER; Int main (void) { int i; pthread_t thread; for (i = 0; i < 5; i++){ pthread create (& thread, NULL, routine threads, (void *)&i); Sleep(1) ; } pthread_exit (NULL); } Exemple 1 static void * routine_threads (void * argument) { int numero = (int ) argument; int nombre_iterations; int i; nombre_iterations = 1+aleatoire (5); for (i = 0; i < nombre_iterations; i++) { sleep (aleatoire (3)); pthread mutex lock (& mutex_stdout); fprintf (stdout, "Le thread numéro %d tient le mutex \n", numero); pthread mutex unlock (& mutex_stdout); } return (NULL); } Exemple 1 static int aleatoire (int maximum) { double d; srand(time(NULL)); d=rand()%maximum; return ((int)d); } Exemple 2 include include include include pthreadcond t condition alarme = PTHREADCOND_INITIALIZER; pthread mutext mutex alarme = PTHREAD_MUTEXINITIALIZER; static void * thread_temperature (void * inutile); static void * thread_alarme (void * inutile); static int aleatoire (int maximum); int main (void) { pthread_t thr; pthread create (& thr, NULL, thread temperature, NULL); pthread create (& thr, NULL, thread alarme. NULL); pthread_exit (NULL); } Exemple 2 static void * thread_temperature (void * inutile) { int temperature = 20; while (1) { temperature += aleatoire (5) - 2; fprintf (stdout, "Température : %d \n", temperature); if ((temperature < 16)||(temperature > 24)) { pthread mutex lock( (& mutex_alarme); pthread cond signal (& condition_alarme); pthread mutex unlock (& mutex_alarme); } sleep (1); } return (NULL); } Exemple 2 static void * thread_alarme (void * inutile) { while (1) { pthread mutex lock (& mutex_alarme); pthread cond wait (& condition_alarme, & mutex alarme); pthread mutex unlock (& mutex_alarme); fprintf (stdout, 'ALARME\n"); } return (NULL); } static int aleatoire (int maximum) { double d; srand(time(NULL)); d=rand()%maximum; return ((int)d); } THE END 01/04/2018 100