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ème des philosophes avec les sémaphores et moniteurs 1 Dîner des Philosoph

Problème des philosophes avec les sémaphores et moniteurs 1 Dîner des Philosophes Cinq philosophes se trouvent autour d'une table ; Chacun des philosophes a devant lui un plat de spaghetti ; A gauche de chaque assiette se trouve une fourchette Un philosophe n'a que trois états possibles : 1. penser pendant un temps indéterminé ; 2. A faim (pendant un temps déterminé et fini sinon il y a famine) ; 3. manger pendant un temps déterminé et fini. Des contraintes extérieures s'imposent à cette situation : • Quand un philosophe a faim, il va se mettre dans l'état « a faim» et attendre que les fourchettes soient libres ; • Pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à sa droite, et celle qui se trouve à sa gauche ; • Si un philosophe n'arrive pas à s'emparer d'une fourchette, il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative. Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger, chacun à leur tour, sans provoquer d’interblocage! 3 Il s'agit donc d'écrire les procédures prendre_fourchette et poser_fourchette. Première solution : 4 Première solution : 5 Première solution : 6 On prend un sémaphore par fourchette Chaque sémaphore est initialisé à 1 sem fourch[ N ] = {1,........1} 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 : 7 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 deus 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 8 En utilisant les moniteurs 9 Déclarons les variables suivantes : • Etat : Tableau[0..4] de (Faim, Pense, Mange) • Self : Tableau[0..4] de Condition La solution à proposer doit garantir les règles suivantes : • Le philosophe i ne peut fixer la variable etat[i] à mange que si ses deux voisins (i-1 mod N) et (i+1 mod N) ne sont pas en train de manger. • Le philosophe i peut se retarder quand il a faim mais il est incapable d’obtenir les baguettes dont il a besoin. En utilisant une instance dp du moniteur Diner_Philosophe, le code d’un processus philosophe devient : Processus Philosophe(i) Début Repeat Penser() ; Dp.prendre_Baguette(i) Manger() ; Dp.Poser_Baguette(i) ; Until False; Fin. 10 Type Diner_Philosophe= Monitor Const N=….; Var Etat : Array[0..N-1] of (Pense, Faim, Mange) ; Self : Array(0..N-] of Condition ; Procedure Prendre_Baguette(i : 0..N-1) Begin Etat[i] :=Faim ; Test(i) ; If Etat[i]<>Mange Then Self[i].attendre() ; End ; Procedure Poser_Baguette(i : 0..N-1) Begin Etat[i] :=Pense ; Test(i-1 mod N) ; Test(i+1 mod N) End ; Procedure Test(i : 0..N-1) Begin If Etat[i-1 mod N]<>mange and Etat[i]=Faim and Etat[i+1 mod N]<>Mange Then Begin Etat[i] :=Mange ; Self[i] .signaler(); End End ; Begin For i=0 to N-1 do Etat[i] :=Pense End. PROBLÈME DES LECTEURS ET DES RÉDACTEURS 1 PROBLÈMEDESLECTEURSETDESRÉDACTEURS Dans le problème des lecteurs et des rédacteurs nous considérons deux classes de processus: les processus lecteurs et les processus rédacteurs. Les processus lecteurs désirent lire des données (par exemple un fichier): les processus rédacteurs désirent modifier ces données. Une solution correcte de ce problème devra assurer l'exclusion mutuelle entre les rédacteurs (pas d'écriture simultanée pour éviter un risque d'incohérence des données) et l'exclusion mutuelle entre les lecteurs et les rédacteurs (pas de lecture pendant une écriture, pour éviter de lire des données dans un état incohérent). Les lecteurs, en l'absence des rédacteurs, doivent toutefois pouvoir accéder simultanément aux données. Présenté ainsi, le problème n'est pas encore entièrement spécifié. Plaçons-nous par exemple à un moment ou une lecture est en cours (par un processus I1). Arrive à cet instant un rédacteur r1 puis un peu plus tard un deuxième lecteur l2. Si nous voulons donner la priorité aux lecteurs, il faut autoriser l2à lire: si nous voulons donner la priorité aux rédacteurs, l2attendra et ne pourra accéder aux données qu'après le rédacteur r1. En fait il y a trois cas à distinguer: 1)- priorité aux lecteurs 2)- priorité aux rédacteurs 2)- même priorité aux lecteurs et aux rédacteurs (c'est-à-dire accès aux données selon l'ordre d'arrivée des processus). 2 Considérons par exemple, durant une écriture, l'ordre d'arrivée suivant (lidésigne un lecteur, ri un rédacteur) : Il, l2, r1 l3, r2. Lorsque l'écriture se termine, l'accès aux données se fait selon l'ordre suivant: 1)- priorité aux lecteurs: I1, l2, l3; puis r1; puis r2; 2)- priorité aux rédacteurs: r1; puis r2; puis I1, l2, l2; 3)- priorité égale: I1, l2; puis r1; puis l3; puis r2. Considérons une procédure p et introduisons la notation suivante: #act(p) : pour désigner le nombre de processus en cours d'exécution de la procédure p; #att(p) : pour désigner le nombre de processus en attente de pouvoir exécuter la procédure p. Dans notre problème, la procédure p sera soit une procédure écrire, soit une procédure lire. La formulation la plus simple du problème des lecteurs et des rédacteurs est alors la suivante: a)- lecture possible lorsque #act( écrire)= 0 b)- écriture possible lorsque #act( écrire)= 0 et #act(lire) = 0 1 3 La priorité aux lecteurs s'exprime ainsi: a)- lecture possible lorsque #act( écrire)= 0 b)- écriture possible lorsque #act( écrire)= 0 et #act(lire) = 0 et #att(lire) = 0 La priorité aux rédacteurs s'exprime de la manière suivante: a)- lecture possible lorsque #act( écrire)= 0 et #att(écrire) = 0 b)- écriture possible lorsque #act( écrire)= 0 et #act(lire) = 0 Le formalisme, tel qu'il est présenté, ne fait pas intervenir l'ordre d'arrivée des processus et ne permet donc pas d'exprimer la variante où l'on donne même priorité aux lecteurs et aux rédacteurs. 1 4 Les Sémaphores : Priorité égale entre lecteurs et rédacteurs Essayons maintenant d'utiliser les sémaphores pour résoudre le problème dans le cas d'une priorité égale entre lecteurs et rédacteurs (la solution avec priorité aux lecteurs n'est pas plus compliquée à exprimer; la solution avec priorité aux rédacteurs constitue quant à elle un petit casse-tête). Voici une première esquisse de la solution dans le cas de priorités égales: 5 Le sémaphore lr est utilisé par les lecteurs et les rédacteurs. Comme la liste d'attente d'un sémaphore est gérée en queue, l'ordre d'arrivée des processus sera l'ordre dans lequel processus accéderont aux données: lecteurs et rédacteurs ont donc même priorité. Cette première esquisse ne réalise toutefois que les conditions: a)- lecture lorsque #act( écrire)= 0 b)- écriture lorsque #act( écrire)= 0 Il faut encore empêcher aux rédacteurs d'écrire lorsqu'une lecture est en cours. Nous ajoutons donc un sémaphore r devant lequel les rédacteurs attendront si une lecture est en cours, Il faut remarquer sur la figure ci-dessous l'exécution conditionnelle de P(r) avant la lecture (ligne 9) et l'exécution conditionnelle de V(r) après la lecture (ligne 13): c'est au premier lecteur débutant la lecture d'empêcher l'accès aux rédacteurs et c'est au dernier lecteur finissant de lire d'autoriser l'accès aux rédacteurs. 16 Cette version est toutefois encore imparfaite: la variable nb_lecteurs est une ressource critique! Il faut en protéger l'accès par un sémaphore mutex. La version finale de la solution est donnée sur la figure ci-dessous. Le sémaphore lr bloque tous les lecteurs nouveaux dès qu'un rédacteur est arrivé. Le sémaphore r bloque toute écriture tant que les lectures ne sont pas finies ; il y a au plus un rédacteur bloqué dans la file associée à r. Dès qu'un lecteur passe ou est réveillé, il incrémente le compteur des lecteurs, bloque éventuellement la ressource et réveille le processus suivant de la file associée à r . L'ordre P(lr) P(r) évite l'étreinte fatale ; on peut aussi faire V(lr) puis V(r). L'ordre FIFO est assuré si les files associées aux sémaphores sont gérées suivant ce principe. 17 Les Sémaphores : Priorité aux lecteurs Le seul cas d'attente d'un lecteur se produit quand un rédacteur écrit dans le fichier ; un rédacteur ne peut accéder au fichier que si aucun lecteur n'est en attente ou en cours de lecture. r est un sémaphore d'exclusion mutuelle pour tous les rédacteurs. Il sert également au premier lecteur qui occupe le fichier et au dernier uploads/Philosophie/ td-interblocage.pdf