Obtenir le pack complet des cours, TDs, examens sur Systèmes d’Exploitation!
Vous souhaitez maîtriser Systèmes d’Exploitation ? Ne cherchez plus, nous avons le pack bien choisi pour vous.
Accédez à une collection complète des supports de cours, des travaux dirigés (TDs) corrigés, TPs avec solution, examens...
Télécharger packInstitut Supérieur d’Informatique Université de Tunis el Manar MME. LILIA SFAXI MME. IMEN LASSOUED TD3 : Synchronisation des Processus avec Attente Active Systèmes d’Exploitation Avancés – 1
ère année ING. Année Universitaire : 2011/2012 TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 1 TD3 : Synchronisation des Processus avec Attente Active Systèmes d’Exploitation Avancés
Exercice 1
Exclusion mutuelle Dans un système informatique, on dispose de trois fichiers F1, F2 et F3 et de trois processus dont les programmes A, B et C ont les structures suivantes : Programme A Programme B Programme C Actions A1 Actions B1 Actions C1 (lire F3) Actions A2 (lire F2) Actions B2 (écrire F3) Actions C2 Actions A3 Actions B3 (lire F1) Actions C3 Actions A4 (écrire F3) Actions B4 Actions C4 (écrire F2) Actions A5 Actions B5 Actions C5 Chaque fichier ne peut ni être lu et modifié en même temps, ni modifié par plusieurs processus en même temps. 1. Donner pour chaque fichier les sections critiques de A, B et C. F1 : pas de section critique car il n’est pas accédé en écriture F2 : A2 et C4 F3 : A4, B2 et C1 2. En déduire les sections en exclusion mutuelle. Sections en exclusion mutuelle : A2 et C4 (F2) A4, B2 et C1 (F3)
Exercice 2
Exclusion mutuelle par variables partagées On dispose de deux processus (P0 et P1) dont le squelette de programme est celui donné dans le cours. 1. Rappeler le squelette des programmes destinés à s’exécuter en parallèle dans des conditions de concurrence. SR ; Entrer_SC() ; SC ; Libérer_SC() ; SR TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 2 L’objectif de l’exercice est d’établir un algorithme utilisant des variables partagées par les processus pour réaliser l’exclusion mutuelle des sections critiques en respectant ses spécifications. On ne fait aucune hypothèse sur l’atomicité des manipulations des variables. 2. Préciser pourquoi une simple attente active sur une variable tour qui vaudrait vrai ou faux selon qu’un processus est ou non en section critique, immédiatement suivie d’une mise à jour de tour, ne convient pas. Algorithme : Tour = faux ; Entrer_sc(){ Si (tour=vrai) attendre ; Tour <- vrai ; } Ne convient pas, car le test sur tour et le changement de sa valeur ne sont pas atomiques. Scénario : Tour P1 P2 faux
(1) si (tour =vrai)
-> non
(2) si (tour =vrai)
-> non vrai (3) tour <- vrai
(4) tour <- vrai SC SC 3. On propose dans un premier algorithme, la solution suivante. La variable tour prend les valeurs : 0 ou 1. L’algorithme (1) de Pi est le suivant : tant_que vrai faire actions avant section critique tant_que tour <> i faire rien section critique i tour ← 1-i TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 3 actions après section critique Noter que 1-i = 0 si i = 1, et 1 si i = 0. La phase d’initialisation du système est réduite à : tour ← 0. Montrer que l’exclusion mutuelle est bien réalisée mais que la condition de progression n’est pas satisfaite. (1) Exclusion Mutuelle Supposons que P0 est en SC. MQ P1 ne peut pas être en SC. P0 en SC -> tour = 0 P1 veut entrer en SC -> tant que retourne vrai car tour <> 1
-> Attente ! Ne peut pas entrer en SC (2) Progression C’est quand un processus n’a pas besoin de la SC, il ne doit pas interdire l’accès à 1 autre processus qui en a besoin. Soient les pg A et B des processus resp. P1 et P2. A B A1 (SC) B1 A2 B2(SC) A3 B3 A4 B4(SC) Un scénario présentant un problème de progression Tour P1 P2 0
(1) A1 (SC)
(2) B1 1 (3) A1 (LSC)
(4) B2 (SC) 0 (6) A2 (8) A3 (10) A4 (terminé) (5) B2 (LSC) (7) B3 (9) B4 (ESC) att (11) B4 (ESC) att TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 4 4. Pour remédier à cet inconvénient, on emploie au lieu de tour, deux variables booléennes D0 et D1. Di est vraie ssi Pi demande à passer en section critique. L’algorithme (2) de Pi est alors : tant_que vrai faire actions avant section critique Di ← vrai tant_que D(i-1) faire rien section critique i Di ← faux actions après section critique D(1-i) désigne D1 si i = 0 et D0 si i = 1. Les variables Di sont initialisées à faux. Montrer que la progression est maintenant assurée. Montrer que le système possède un état d’interblocage. Progression Un processus qui n’a pas besoin de la SC ne doit pas interdire l’accès à un autre qui en a besoin. P0 n’a pas besoin de la SC -> D0 faux, car • Si P0 n’est jamais entré en SC, D0 initialisé à faux, • Si P0 a quitté la SC, il a remis D0 à 0 dans la partie libérer_SC P1 veut accéder à la SC -> D1 vrai • Si D0 faux, il passe -> vrai Si P0 ne veut pas accéder à la SC, P1 peut le faire Interblocage Chaque processus attend que l’autre lui cède la place D0 D1 P1 P2 Faux Faux
Vrai Faux (1) D0 = vrai Vrai Vrai (2) D1 = vrai
(3) tant que (D1=vrai)
-> vrai attendre TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 5
(4) tant que (D0=vrai)
-> vrai attendre
Exercice 3
Algorithme de Peterson 1. Rappeler le principe de l’algorithme de Peterson. //ALGO de Peterson # define FALSE 0 # define TRUE 1 # define N 2 //nbr processus Int turn ; // a qui le tour Int interested[N]; //initialisé à 0 void entrer_SC(int MonNumero) { //MonNumero=0 pour P0, 1 pour P1 int other ;
//autre processus other=1-MonNumero ; interested[MonNumero]=TRUE; //vouloir entrer ds SC turn=MonNumero;
//définit l’indicateur while(turn==MonNumero && interested[other]=TRUE) ; /* attente active */ } Void liberer_SC(int MonNumero) { interested[MonNumero]=FALSE; //Sortie de SC } 2. Prouver que cet algorithme respecte toutes les exigences d’un bon mécanisme de contrôle d’accès. Le mécanisme précédent est l'algorithme de Peterson. Ce mécanisme est un bon mécanisme de contrôle d'accès à la section critique. En effet, il respecte les 3 exigences d'un bon système de contrôle d'accès à la section critique (à part l'exigence qu'il n'y a aucune hypothèse ni sur la vitesse des processus ni sur le nombre de processus) qui sont: a- Exclusion mutuelle TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 6 On va démontrer l'exclusion mutuelle par l'absurde. Supposons que l'exclusion mutuelle n'est pas réalisée,alors Pi et Pj peuvent être dans la section critique au même temps.
En d'autres termes, les 3 propositions suivantes sont vérifiées au même temps: (i) Pi en SC <=> veutEntrer[j]=faux ou tour=j (ii) Pj en SC <=> veutEntrer[i]=faux ou tour=i (iii) Pi en SC et Pj en SC <=>veutEntrer[i]=vrai et veutEntrer[j]=vrai Ceci étant absurde car veutEntrer[j]=faux et veutEntrer[j]=vrai au même temps. (idem pour veutEntrer[i] et pour tour). D'où l'exclusion mutuelle est garantie par ce mécanisme. b- Progression Supposons que Pi est dans la section restante (i.e, en dehors de la section critique) Alors veutEntrer[i]=faux Supposons aussi que Pj ne peut pas entrer dans la section critique Alors on aura veutEntrer[i]=vrai et tour=i (Pi est dans sa section critique) Ce qui est absurde car veutEntrer[i]=faux et veutEntrer[i]=vrai au même temps. En d'autres termes, si Pi n'est pas dans sa section critique, alors il ne va pas interdire l'accès à Pj dans sa section critique (Ceci n'est autre qu'une garantie que le choix du prochain processus à entrer dans sa section critique est réalisé parmi les processus qui sont intéressés par y enter). D'où le respect du déroulement. c- Attente bornée L'attente bornée va être démontrée par l'absence de famine et l'absence d'interblocage. c1- Absence d'interblocage TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 7 Supposons que Pi et Pj sont bloqués au même temps,
Alors les propositions suivantes sont vérifiées au même temps: (i) Pi bloqué <=> veutEntrer[j]=vrai et tour=j
(ii) Pj bloqué <=> veutEntrer[i]=vrai et tour=i Ceci est absurde car tour ne peut être égale à i et j au même temps. D'où l'absence de l'interblocage. c2- Absence de famine Deux cas vont être traités. CAS 1. Si Pi a demandé l'entrée dans sa section critique et Pj est déjà dans sa section critique
alors Pi ne va pas attendre indéfiniment car le déroulement est assuré. CAS 2. Si Pi et Pj demandent ensemble l'accès à la section critique
alors nous aurons veutEntrer[i]=vrai et veutEntrer[j]=vrai
or tour=j
/*c'est la dernière valeur enregistrée dans tour.*/
donc Pi entre dans sa section critique et Pj attend
mais si Pi veut encore entrer dans sa section critique
alors veutEntrer[i]=vrai
mais tour=j (Pj est le dernier à avoir écrit dans tour)
donc interdiction de l'entrée de Pi et entrée de Pj En conclusion, chaque processus demandant l'accès à sa section critique attend au plus un passage de l'autre processus par sa section critique. Conclusion finale: l'algorithme de Peterson fournit un bon mécanisme de contrôle d'accès à la section critique. TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 8
Exercice 4
Algorithme de Dekker C'est une solution logicielle qui utilise une variable tour et deux booléens initialisés à faux : p1_veut_entrer et p2_veut_entrer. Déclarations communes : var p1_veut_entrer : boolean ; p2_veut_entrer : boolean ; tour : 1..2 ; L'algorithme du Processus P1 est le suivant : intialisations: p1_veut_entrer := false ; p2_veut_entrer := false ; tour := 1 ;
/* ou 2 */ repeat p1_veut_entrer := true ; while (p2_veut_entrer) do if (tour = 2) thenbegin p1_veut_entrer := false ;
while (tour = 2) do ; /* attendre */
p1_veut_entrer := true ;
end ; Section Critique tour := 2 ; p1_veut_entrer := false ; Section Restante until false ; TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 9 Dans les preuves qui suivent : – SR signifie “Section Restante” – SC signifie “Section Critique” – PE signifie “Protocole d’Entrée” (instructions entre SR et SC) – PS signifie “Protocole de Sortie” (instructions entre SC et SR) 1. La propriété d'exclusion mutuelle est-elle préservée ? On veut montrer que P1 et P2 ne peuvent être simultanément en section critique. Preuve directe. Supposons que (Hypothèses) : – P1 est en SC, – P2 est en dehors de la SC et montrons que P2 ne peut pas rejoindre P1. TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 10 Remarquons d’abord que pour un processus qui n’est pas déjà en SC, la sortie du PE est un point de passage obligatoire pour atteindre la SC. Donc pour montrer que P2 ne peut pas rejoindre P1, il suffirait de montrer que P2 ne peut pas franchir ce point (sortie du PE). C’est ce que nous allons faire. Des hypothèses et de la remarque précédente on déduit que : – Comme P1 est en SC, veut1 = vrai et ne peut changer tant que P1 reste en SC – Pour franchir la sortie du PE, P2 doit être entré dans le PE (évident). – Une fois entré en PE, P2 ne peut sortir que si veut1 devient faux. Donc P2 ne peut pas quitter le PE tant que P1 se trouve en SC. CQFD. 2. La propriété de non-blocage est-elle préservée ? On veut montrer que P1 et P2 ne peuvent tous les deux rester indéfiniment dans le PE. Preuve directe. Nous allons montrer que si les deux processus sont en PE, l’un des deux doit obligatoirement quitter le PE en un temps fini. Hypothèses : P1 et P2 sont tous les deux entrés dans le PE et n’en sont pas sorti. Remarquons d’abord que la variable tour ne peut plus changer de valeur tant que les deux processus restent dans le PE. Supposons alors que tour = 1. Déductions : – veut1 = vrai et sa valeur ne peut pas changer car tour = 1. – P2 boucle dans le PE car veut1 = vrai – comme P2 boucle il est obligé de passer par le test if en un temps fini, car il n’y pas d’instructions en dehors du if qui puisse le bloquer – une fois entré dans le if, P2 reste bloqué dans la 2e boucle while tant que tour = 1 – tant que P2 est bloqué dans la 2e boucle, veut2 = faux et cette valeur ne change plus – donc veut2 = faux au bout d’un temps fini et cette valeur ne peut plus changer Dire que veut2 devient faux au bout d’un temps fini implique que P1 sort du PE au bout d’un temps fini. On démontre de même que si tour = 2, c’est P2 qui sort du PE au bout d’un temps fini. Par conséquent, quelle que soit la valeur de tour, l’un des deux processus sort du PE au bout d’un temps fini. CQFD. 3. Hypothèses : P2 est en attente dans la boucle while(tour = 1)do; et P1 est en SC. La propriété suivante est-elle vérifiée : « Si P1 conserve l'unité centrale, il peut exécuter sa SC autant de fois qu'il le désire. En revanche, lorsque P1 a exécuté sa section de sortie, P2 peut entrer en SC dès que l'UC lui est accordée. » Hypothèses : P2 est en attente dans le while de la ligne 6, P1 est en section critique. TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 11 Si P1 est le seul à s’exécuter, comme seul P2 peut modifier veut2, veut2 va rester faux. Donc, à chaque fois que P1 voudra entrer en section critique, il ne rentrera pas dans le while de la ligne 3, et entrera donc immédiatement en section critique. En revanche, dès que P1 sort de sa section critique, tour vaut 2. Si P2 s’exécute assez longtemps pour mettre veut2 à vrai, veut2 sera vrai tant que P2 ne sera pas passé dans sa section critique (si tour = 2, P2 ne met pas veut2 à faux dans sa section d’entrée, et tour ne peut être mis à 1 que par P2 dans sa section de sortie.) Or, tant que veut2 est vrai, P1 ne peut pas entrer en section critique (à cause du while de la ligne 3). Si P2 n’entre pas dans sa section critique, veut2 reste vrai, et P1 n’entre pas non plus dans se section critique, or nous avons montré que c’est impossible (question 2.3), donc P2 finit par entrer en section critique. 4. Vérifier la propriété de progression : un processus en Section Restante ne peut pas empêcher un autre processus d'entrer en SC. Si P1 est en section restante, alors veut1 est faux, et donc P2 ne rentrera pas dans (ou sortira de) la boucle while de la ligne 3, et rentrera immédiatement en section critique. 5. La propriété d'attente bornée est-elle réalisée si l'on adopte la convention suivante : « Lorsqu'un Processus Pi est dans sa section d'entrée avec le booléen pi_veut_entrer à faux, il n'est provisoirement plus en attente de sa section critique. » Pour démontrer la propriété d’attente bornée, il faut prouver qu’un processus ne peut pas obtenir la SC une infinité de fois pendant que l’autre attend la SC. Montrons que si P2 attend (dans le PE) alors cette propriété est vérifiée en adoptant la convention proposée. Si P2 attend et tour = 2, c’est que P1 est soit dans le PE soit dans la SC. – S’il se trouve déjà en SC et qu’il souhaite repasser une 2
ème fois, P1 est obligé d’exécuter le PS avant de passer une 2
ème fois, et on se retrouve dans la situation tour = 1 et P2 qui attend (voir plus loin). – s’il n’est pas déjà en SC, comme tour = 2, P1 est forcément bloqué dans la 2
ème boucle while et P2 obtient la SC avant P1. On a vu dans une question précédente que si P2 attend dans la 2
ème boucle while, alors P1 peut passer un nombre n de fois à condition de garder le processeur. La convention proposée permet de négliger ce cas de figure : on arrête de compter le nombre de fois que P1 peut passer du fait que P2 n’a pas le processeur. Dans ce cas, si P2 attend avec tour = 1 alors P1 peut passer une première fois ce qui entraîne tour = 2. Et si l’on néglige le temps que P2 doit éventuellement attendre l’UC pour pouvoir exécuter veut2 = vrai (temps pendant lequel P1 pourrait passer plusieurs fois en SC), on TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 12 montre facilement que P1 sera bloqué la deuxième fois qu’il entrera dans son PE, ce qui démontre la propriété d’attente bornée.