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. 2. En déduire les sections en exclusion mutuelle.
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. 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. TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 2 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 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. 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.
Exercice 3
Algorithme de Peterson 1. Rappeler le principe de l’algorithme de Peterson. 2. Prouver que cet algorithme respecte toutes les exigences d’un bon mécanisme de contrôle d’accès. TD3 : Synchronisation des Processus avec Attente Active MME. LILIA SFAXI
2011/2012 MME. IMEN LASSOUED 3
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 ; 1. La propriété d'exclusion mutuelle est-elle préservée ? 2. La propriété de non-blocage est-elle préservée ? 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. » 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. 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. »