Ce document, conçu pour les étudiants en première année d'ingénierie en Systèmes d'Exploitation Avancés, présente une série d'exercices pratiques (TD3) sur la synchronisation des processus avec attente active.
Il couvre les notions fondamentales et les algorithmes clés suivants :
- L'exclusion mutuelle et les sections critiques.
- L'analyse de mécanismes de synchronisation par variables partagées.
- Les algorithmes de Peterson et de Dekker, incluant la démonstration de leurs propriétés (exclusion mutuelle, progression, attente bornée et absence d'interblocage).
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 :
- Actions A1
- Actions A2 (lire F2)
- Actions A3
- Actions A4 (écrire F3)
- Actions A5
Programme B :
- Actions B1
- Actions B2 (écrire F3)
- Actions B3 (lire F1)
- Actions B4
- Actions B5
Programme C :
- Actions C1 (lire F3)
- Actions C2
- Actions C3
- Actions C4 (écrire F2)
- 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 pour F2 : A2 et C4.
- Sections en exclusion mutuelle pour F3 : A4, B2 et C1.
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
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 proposé :
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 illustrant le problème :
Tour P1 P2
faux
(1) si (tour = vrai) (2) si (tour = vrai)
-> non -> non
vrai (3) tour <- vrai
SC (4) tour <- vrai
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 :
Algorithme (1) de Pi :
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.
Exclusion Mutuelle
Supposons que P0 est en SC. Montrons que P1 ne peut pas être en SC.
- P0 en SC implique tour = 0.
- P1 veut entrer en SC, mais la condition "tant que tour <> 1" retourne vrai, car tour = 0. Donc P1 est en attente et ne peut pas entrer en SC.
Progression
C’est quand un processus n’a pas besoin de la SC, il ne doit pas interdire l’accès à un autre processus qui en a besoin. Soient les programmes A et B des processus respectifs P1 et P2.
Exemple de programmes A et B :
A B A1 (SC) B1 A2 B2(SC) A3 B3 A4 B4(SC)
Scénario présentant un problème de progression :
Tour P1 P2
0
(1) A1 (SC)
(2) B1
1 (3) A1 (LSC) (Libération SC)
(4) B2 (SC)
0 (6) A2
(8) A3
(10) A4 (terminé) (5) B2 (LSC) (Libération SC)
(7) B3
(9) B4 (ESC) att (Essai d'Entrée SC, attente)
(11) B4 (ESC) att (Essai d'Entrée SC, attente)
4. Pour remédier à cet inconvénient, on emploie au lieu de "tour", deux variables booléennes D0 et D1. Di est vraie si Pi demande à passer en section critique. L’algorithme (2) de Pi est alors :
Algorithme (2) de Pi :
tant_que vrai faire actions avant section critique Di <- vrai tant_que D(1-i) 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, donc D0 est faux. Cela est vrai car :
- Si P0 n’est jamais entré en SC, D0 est initialisé à faux.
- Si P0 a quitté la SC, il a remis D0 à faux dans la partie libérer_SC.
- P1 veut accéder à la SC, donc D1 est vrai.
- Si D0 est faux, P1 peut passer, la condition "tant_que D(1-i) faire rien" étant fausse pour P1.
Conclusion : 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.
Scénario d'interblocage :
D0 D1 P1 P2
Faux Faux
Vrai Faux (1) D0 <- vrai
Vrai Vrai (2) D1 <- vrai
(3) tant que (D1 = vrai) (4) tant que (D0 = vrai)
-> vrai attendre -> vrai attendre
Exercice 3 : Algorithme de Peterson
1. Rappeler le principe de l’algorithme de Peterson.
Algorithme de Peterson :
//ALGO de Peterson
#define FALSE 0
#define TRUE 1
#define N 2 //nombre de processus
Int turn ; // à 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 dans 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 trois 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
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 trois propositions suivantes sont vérifiées au même temps :
- (i) Pi en SC <=> interested[j] = faux ou turn = j
- (ii) Pj en SC <=> interested[i] = faux ou turn = i
- (iii) Pi en SC et Pj en SC <=> interested[i] = vrai et interested[j] = vrai
Ceci étant absurde car interested[j] = faux et interested[j] = vrai au même temps (idem pour interested[i] et pour turn). D'où l'exclusion mutuelle est garantie par ce mécanisme.
b. Progression
Supposons que Pi est dans la section restante (c'est-à-dire en dehors de la section critique). Alors interested[i] = faux. Supposons aussi que Pj ne peut pas entrer dans la section critique. Alors on aura interested[i] = vrai et turn = i (Pi est dans sa section critique).
Ce qui est absurde car interested[i] = faux et interested[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 entrer). 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
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é <=> interested[j] = vrai et turn = j
- (ii) Pj bloqué <=> interested[i] = vrai et turn = i
Ceci est absurde car "turn" ne peut être égal à "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 interested[i] = vrai et interested[j] = vrai. Or turn = j (c'est la dernière valeur enregistrée dans "turn"). Donc Pi entre dans sa section critique et Pj attend. Mais si Pi veut encore entrer dans sa section critique, alors interested[i] = vrai, mais turn = j (Pj est le dernier à avoir écrit dans "turn"), 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.
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 ; var p2_veut_entrer : boolean ; var tour : 1..2 ;
L'algorithme du Processus P1 est le suivant :
initialisations:
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) then begin
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 ;
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.
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 sortis.
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 a 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.
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 sa section critique, or nous avons montré que c’est impossible (question 2), 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 2e fois, P1 est obligé d’exécuter le PS avant de passer une 2e 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 2e boucle "while" et P2 obtient la SC avant P1.
On a vu dans une question précédente que si P2 attend dans la 2e 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 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.
Foire Aux Questions (FAQ)
1. Qu'est-ce que l'exclusion mutuelle et pourquoi est-elle nécessaire ?
L'exclusion mutuelle est une propriété qui garantit qu'un seul processus peut accéder à une ressource critique (comme une section de code ou un fichier partagé) à un moment donné. Elle est essentielle pour prévenir les conditions de concurrence et assurer l'intégrité des données dans les systèmes multi-processus ou multi-threads.
2. Quelles sont les trois exigences principales d'un bon mécanisme de contrôle d'accès à la section critique ?
Un bon mécanisme doit satisfaire trois exigences : l'exclusion mutuelle (un seul processus en SC à la fois), la progression (si aucun processus n'est en SC et que certains veulent y entrer, un de ceux-là doit pouvoir le faire), et l'attente bornée (aucun processus ne doit attendre indéfiniment avant d'accéder à la SC, évitant la famine).
3. Quel est le principal inconvénient de l'attente active simple pour l'exclusion mutuelle ?
Le principal inconvénient de l'attente active simple est qu'elle ne garantit pas l'atomicité des opérations de test et de mise à jour des variables de contrôle. Cela peut conduire à des conditions de concurrence où plusieurs processus entrent simultanément en section critique, violant ainsi le principe d'exclusion mutuelle.