Chapitre 2 : L'Exclusion Mutuelle Entre Processus PDF

Université de Blida 1 Système d’exploitation Département d’informatique L3 SIQ Chapitre 2 : L’Exclusion mutuelle entre Proc...

Université de Blida 1 Système d’exploitation Département d’informatique L3 SIQ Chapitre 2 : L’Exclusion mutuelle entre Processus 1. Position du problème d’exclusion mutuelle Lorsque plusieurs processus s’exécutent sur un ordinateur, ils sont amenés à partager des ressources communes. Malheureusement, le partage des variables sans précaution particulière peut conduire à des résultats imprévisibles. Exemple : Soient deux transactions exécutées par deux threads T1 et T2 lancées en parallèle et pouvant consulter et modifier simultanément un même compte CCP de valeur initiale C0 centralisé dans un fichier commun F. T1 effectue un dépôt (crédit) et T2 effectue un retrait (débit). Procédure T1 Procédure T2 Var Cpt : entier ; Var Cpt : entier ; a1 : Lire Cpt ; a2 : Lire Cpt ; b1 : Cpt := Cpt+SV ; b2 : Cpt := Cpt-SR ; c1 : Réécrire Cpt ; c2 : Réécrire Cpt ; Premier cas : Si l’exécution de T1 et T2 est séquentielle il n’y a aucun problème car il n’y a pas d’accès simultané au même compte. Le résultat final du compte est C0+SV-SR correct. Deuxième cas : Si l’exécution de T1 et T2 est parallèle, il y a un risque car il y a accès simultané au même compte. En effet, soit {a1, a2, b1, b2, c1, c2} l’ordre d’exécution des actions des deux transactions, T1 ayant calculé C0+SV va réécrire cette valeur dans F, puis T2 ayant calculé C0-SR va réécrire cette valeur dans F et ce sera la valeur finale du compte résultat final faux. L’exécution parallèle de T1 et T2 prise sans précautions entraine une incohérence dans le résultat final. C’est le compte CCP commun qui constitue la ressource critique, et les séquences de lecture et modification du compte s’appellent sections critiques de T1 et T2 respectivement. Pour éviter cette incohérence, il faut empêcher l’exécution parallèle de T1 et T2. Les séquences de T1 et T2 doivent être exécutées en exclusion mutuelle. Problème : Pour éviter toute utilisation incorrecte d’une ressource critique, les suites d’instructions qui la manipulent (section critique) dans les différents processus ne doivent jamais s’exécuter simultanément. Les sections critiques de chaque processus doivent s’exécuter en Exclusion mutuelle. Solution : Un contrôle doit avoir lieu durant l’utilisation de ce type de ressource. Ce contrôle consiste en un protocole qui encadre les sections critiques par des séquences spéciales d’instructions. La séquence d’instructions qui précède la section critique est appelée protocole d’acquisition. Ce dernier vise à vérifier que l’accès du processus à sa section critique est possible et aussi interdire l’accès des autres processus à leurs sections critiques. La séquence d’instructions qui suit la section critique est appelée protocole de libération. Elle rend l’accès à la ressource critique possible. L’exclusion mutuelle des processus dans leurs sections critiques n’est garantie que si les protocoles d’acquisition et de libération sont correctement utilisés. Contrôler la compétition entre processus, revient à trouver une solution au problème de l’exclusion mutuelle. Toute solution à l’exclusion mutuelle se décompose en trois étapes : 1) Demande d’entrée en SC ; 2) SC ; 3) Fin et Sortie de la SC ; Différentes approches existent. Quelque soit la solution, elle doit garantir les 4 propriétés énoncées par DIJKSTRA. Chargée de cours Docteur N. TOUBALINE 1/2 Université de Blida 1 Système d’exploitation Département d’informatique L3 SIQ 2. Les quatre propriétés de Dijkstra Propriété 1. A tout instant, un seul processus peut avoir accès à sa section critique. Propriété 2. Si aucun processus n’est dans sa section critique, un processus en attente doit pouvoir accéder à sa section critique au bout d’un temps fini. En d’autre terme, la section critique est toujours atteignable. Propriété 3. Si un processus est bloque en dehors d’une section critique, ce blocage ne doit pas empêcher l’entrée d’un autre processus en sa section critique. Propriété 4. La solution doit être la même pour tous les processus. En d’autre terme, Aucun processus ne doit jouer de rôle privilégié. 3. Les différentes techniques permettant d’assurer l’exclusion mutuelle a) L’exclusion mutuelle par attente active : 1) Solution algorithmique au problème d’exclusion mutuelle Solution de Peterson Les variables communes sont tour et drapeau. Var Drapeau: array [0..1] of boolean ; Tour: (0,1) Initialement: for i:=0 to 1 do drapeau [i]:= false; Tour: =0; ou 1 Processus P0 Processus P1 Drapeau= true; Drapeau= true; Tour=1; Tour=0; While(Drapeauand(Tour=1)do; While(Drapeauand(Tour=0)do; Section_critique(); Section_critique(); Drapeau= false; Drapeau= false; 2) Solution au problème de l’exclusion mutuelle par instruction spéciale Le principe généralement développé par les instructions spéciales est de lire et modifier une ou plusieurs variables communes d’une manière indivisible en une seule instruction. Soit p une variable donnant l’état de la ressource critique : p=vrai ressource occupée ; p=faux ressource libre. La solution la plus immédiate au problème de l’EM consiste à déclarer une variable p donnant l’état de la ressource critique (p=vrai ressource occupée ; p=faux ressource libre). La variable p est elle même une ressource critique : plusieurs processus peuvent simultanément lire p, la trouver à faux puis la forcer à vrai avant de s’engager en SC. Pour éviter ce problème le test et la modification de la variable d’état p se fera d’une manière indivisible c’est à dire en une seule instruction. b) L’exclusion mutuelle par attante passive : Le Verrous Un verrou v est une variable booléenne sur laquelle deux opérations atomiques sont définies, Verrouille(v) et Déverrouille(v). Ce sont les deux seules opérations (mis à part la création et sa destruction) qui peuvent manipuler le verrou. Elles sont équivalentes à l’exécution atomique des séquences d’instructions suivantes: void Verrouille(verrou v) { void Deverrouille(verrou v) { if (v) v = 0; //v = false if (la file associée à v est non vide) else suspendre le processus appelant dans la file associée débloquer un processus en attente dans la file àv; } else v = 1; //v =true } Opération Verrouille(v): Si un verrou v est initialisé à vrai et qu’un processus appelle Verrouille(v), le verrou est positionné à faux. Si un second processus appelle Verrouille(v), alors il passe à l’état bloqué et joint la file d’attente associée à v. Opération Deverrouille(v): S’il y a un processus en attente sur le verrou v, alors ce processus est réactivé en le retirant de la file d’attente associée à v pour joindre la file des processus prêts. S’il n’y a pas de processus en attente pour obtenir le verrou v, le verrou v est libéré en le positionnant à vrai (état initial). Un verrou permet de résoudre le problème de l’EM à n processus de manière simple. Il suffit de verrouiller un verrou v avant d’entrer en SC, bloquant ainsi les autres processus qui accèdent à leur SC protégée par le même verrou v. La sortie d’une SC se fait en déverrouillant v, ce qui libère le verrou ou réveille un processus bloqué pour l’accès à sa SC. Initialisation globale: int v= 1; Demande d’entrée en SC : verrouille (v) Accès à la ressource : Fin et Sortie de la SC : deverouille(v) Chargée de cours Docteur N. TOUBALINE 2/2