Système d’exploitation 3ième Ingénieur Séridi Ali
Chapitre II : Synchronisation des processus
Problématique
Soit P et Q deux processus qui s’exécutent de façon concurrente et qui accèdent à la même
variable d’un compte bancaire CPT.
La mise à jour concurrente des données peut se dérouler sans problème, comme dans la figure
suivante, où la variable CPT, initialement à 2000, a comme valeur finale 1000 (2000 + 1000 -
2000).
Int cpt := 2000
Processus P Processus Q
cpt := cpt+1000 ; cpt := cpt-2000 ;
Charger (Ap,cpt) ; Charger (Aq,cpt) ;
Add (Ap,1000) ; Sub (Aq,2000) ;
Sauvegarder(Ap,cpt) Sauvegarder (Aq,cpt)
cpt := 1000 Résultat correct cpt := 0 Résultat Faux
Malheureusement, la mise à jour concurrente peut aussi générer des incohérences, comme
dans la figure suivante, où la variable CPT, initialement à 2000, a comme valeur finale 0 après
l'exécution du même code. (Cas de l’exécution alternée des instructions niveau assembleur)
Afin d’éviter ce type de problème l’accès à la variable CPT doit se faire en exclusion mutuelle
car c’est une ressource critique.
Problème de l’exclusion mutuelle
Soit P0, P1, P2,…, Pn un ensemble de processus qui possèdent des parties de code qui modifient
des variables communes aux processus. Cette partie de code est dite section critique.
La solution à l’exclusion mutuelle peut être réalisée par deux parties de code qui encadrent la
section critique de chaque processus appelée Prologue (ou protocole d’acquisition) et Epilogue
(ou protocole de libération).
1
Système d’exploitation 3ième Ingénieur Séridi Ali
La solution doit respecter les propriétés suivantes :
1. Assurer l’exclusion Mutuelle : un seul processus peut exécuter la section critique à la fois.
2. Absence de blocage : si aucun processus n’exécute la section critique, alors aucun
processus ne doit être bloqué lors de l’accès à cette dernière, et en cas de défaillance d’un
processus en dehors de la section critique la solution doit rester valide.
3. Aucun privilège : tous les programmes ont les mêmes droits.
4. Attente limitée : un processus demandeur de la section critique ne doit pas attendre
indéfiniment.
5. Déroulement : si aucun processus n’est dans sa section critique et d’autres attendent, seuls
qui sont dans la partie prologue décident qui entre dans la section critique. (Détail de 2)
Solution au problème d’exclusion mutuelle :
Forme de la solution
<Initialisation des variables Communes>
Processus Pi Processus Pj
<Initialisation var locales> <Initialisation var locales>
Cycle Cycle
Programme de Pi Programme de Pj
<Prologue> <Prologue>
<Section Critique > <Section Critique >
<Epilogue> <Epilogue>
Reste du programme Pi Reste du programme Pj
Fin Cycle Fin Cycle
Fin Pi Fin Pj
La partie prologue : assure l’entrée à la S.C exclusive.
La partie épilogue : assure la libération ou de la ressource critique.
Solutions logicielles
Les solutions logicielles utilisent ce qui est permis par la programmation usuelle, sans utiliser
des instructions spéciales prises en charge par le système d’exploitation.
- Solution avec attente active :
La solution avec attente active oblige le processus désirant exécuter une section critique à
entrer dans un test répétitif qui ne sera franchi qu’après la vérification d’une condition qui peut
être mise à jour par d’autres processus.
2
Système d’exploitation 3ième Ingénieur Séridi Ali
Solution pour deux processus :
Solution 1 :
Contexte commun : Tour : 0..1 ; {initialisé à 0 ou 1}
Processus P0
Processus P1
Début
Début
Répéter
Répéter
……
……
Test : Si tour < >0 alors aller à test ;
Test : Si tour < >1 alors aller à test ;
<Section Critique >
<Section Critique >
Tour :=1 ;
Tour :=0 ;
Reste du programme P0
Reste du programme P1
Jusqu'à sortir
Jusqu'à sortir
Fin P0
Fin P1
Cette solution assure l’E.M mais elle n’est pas bonne car : si Tour vaut 0 et P1 veut entrer en section
critique alors que P0 s'est terminé, P1 ne pourra pas entrer en section critique (les deux
processus doivent exécuter alternativement leur section critique). Ce qui est en contradiction
avec la règle 2 ( absence de blocage).
Solution 2 :
Contexte commun : Drapeau : tableau [0..1] de booléens initialisés à faux :
Processus P0 Processus P1
Début Début
Répéter Répéter
…… ……..
Drapeau[0] := vrai ; Drapeau[1] := vrai ;
Test : Si Drapeau[1] alors aller à test ; Test : Si Drapeau[0] alors aller à test ;
<Section Critique > <Section Critique >
Drapeau[0] := Faux ; Drapeau[1] := Faux ;
Reste du programme P0 Reste du programme P1
Jusqu'à sortir Jusqu'à sortir
Fin P0 Fin P1
Cette solution présente l’inconvénient suivant : lorsque les deux processus fixent ensemble leur
drapeau à vrai, ils rentrent dans une attente infinie (interblocage)
3
Système d’exploitation 3ième Ingénieur Séridi Ali
Solution 3 :
Contexte commun : Drapeau: tableau [0.. 1] de booléens initialisés à faux :
Processus P0
Processus P1
Début
Début
Répéter
Répéter
……
……..
Test : Si Drapeau[1] alors aller à test ;
Test : Si Drapeau[0] alors aller à test ;
Drapeau[0] := vrai ;
Drapeau[1] := vrai ;
<Section Critique >
<Section Critique >
Drapeau[0] := Faux ;
Drapeau[1] := Faux ;
Reste du programme P0
Reste du programme P1
Jusqu'à sortir
Jusqu'à sortir
Fin P0
Fin P1
Cette solution ne respecte pas la règle 1 (assurer l’E.M).
Considérons l'exécution des deux processus aux instants consécutifs t0 , t1 t2 et t3 :
- En t0, P0 exécute Test : Si Drapeau[1] alors aller à test ; et trouve Drapeau[1] à faux (la
prochaine instruction qu'il exécutera sera donc celle qui la suit) ; mais une interruption suspend
son exécution au profit de P1;
- En t1, P1 exécute Test : Si Drapeau[0] alors aller à test ; et trouve Drapeau[0] à faux (la
prochaine instruction qu'il exécutera sera donc celle qui la suit) ;
- En t2, P1 exécute Drapeau[1] = vrai et entre en section critique ; puis une interruption suspend
son exécution au profit de P0;
- En t3, P0 exécute Drapeau[0] = vrai et entre en section critique.
Ainsi les deux processus se trouveront tous les deux en section critique. Cela s'explique par le
fait que le test et la modification de la variable Drapeau [0] par le processus P0, n’est pas fait
d'une façon ininterruptible.
Solution 4 :
La solution suivante donnée par Dekker en 1965 a été la première solution acceptable pour
synchroniser deux processus :
4
Système d’exploitation 3ième Ingénieur Séridi Ali
Contexte commun : Drap : tableau [0..1] de booléens initialisés à faux ; Tour : 0..1 ;
Processus P0 Processus P1
Début Début
Répéter Répéter
…… ……
Drap[0] = vrai ; Drap[0] = vrai ;
Tantque Drap[1] Faire Tantque Drap[0] Faire
Si Tour = 1 Alors Si Tour = 0 Alors
Drap[0] : = faux ; Drap[1] : = faux ;
Tantque Tour = 1 Faire rien ; Tantque tour = 0 Faire rien;
Drap[0] := vrai ; Drap[1] := vrai ;
Finsi Finsi
Fintantque Fintantque
<Section Critique > <Section Critique >
Tour= 1; Tour= 0;
Drap[0]= faux ; Drap[1]= faux ;
Reste du programme P0 Reste du programme P1
Jusqu'à sortir Jusqu'à sortir
Fin P0 Fin P1
Solution 5 :
La solution de Dekker étant un peu compliquée, Peterson a proposé en 1981 une solution
correcte et plus simple.
Contexte commun : Drap: tableau [0.. 1 ] de booléens initialisés à faux ; Tour : 0.. 1 ;
Processus P0 Processus P1
Début Début
Répéter Répéter
…… ……..
Drapeau[0] := vrai ; Drapeau[1] := vrai ;
Tour := 1 ; Tour := 0 ;
Test: Si Drapeau[1] et tour=1 Test:Si Drapeau[0] et tour=0
alors aller à test; alors aller à test;
<Section Critique > <Section Critique>
Drapeau[0] := faux ; Drapeau[1] := faux ;
Reste du programme P0 ; Reste du programme P1 ;
Jusqu'à sortir Jusqu'à sortir
Fin P0 Fin P1
5
Système d’exploitation 3ième Ingénieur Séridi Ali
Les solutions matérielles :
Plusieurs machines offrent des instructions matérielles qui s’exécutent de façon atomique
(indivisisble). Nous pouvons distinguer dans cette catégorie plusieurs solutions. Tels que :
Désarmement des interruptions
Cette solution consiste à interdire l’allocation de l’unité centrale à un autre processus tant que
le processus en cours d‘exécution est dans sa section critique, ainsi, nous serons sûr que la
section critique va s’exécuter de manière indivisible.
Puisque l'allocation CPU résulte de la prise en compte d’une interruption non masquées, il suffit
de masquer les interruptions pendant la durée de la section critique. De cette façon aucun autre
processus ne pourra interrompre le processus pendant l’exécution de sa section critique.
Processus Pi
Le comportement des processus Début
est décrit par le schéma suivant : …….
Masquer les interruptions ;
< Section Critique >
Démasquer les interruptions ;
Reste du programme
Fin
A première vue cette solution parait simple, malheureusement elle présente certains
inconvénients :
• Elle n’est pas adaptée aux systèmes multiprocesseurs qui ne gèrent pas les interruptions
par le même processeur. Ainsi, si les interruptions sont masquées sur un processeur
particulier, un processus s’exécutant sur un autre processeur peut accéder
parallèlement à une de ses sections critiques et manipuler ainsi les variables communes.
• Il y a le risque de retarder des processus prioritaires lors de l’exécution d’une longue
section critique bien que ces processus prioritaires puissent ne pas être concernés par
l’exécution de sections critiques.
Instruction Test And Set (TAS)
Teste et modifie le contenu d’un mot mémoire de façon atomique en une valeur Vrai.
Fonction Test-And-Set (var M:Booleen):Booleen;
Début
Test-And-Set := M;
M:= Vrai;
Fin
Nous pouvons exploiter les caractéristiques de l’instruction atomique TAS prises en charge par
le système d’exploitation pour assurer l’exclusion mutuelle comme détaillé dans l’exemple
suivant :
6
Système d’exploitation 3ième Ingénieur Séridi Ali
On utilise une variable globale Lock
initialisée à Faux.
Processus Pi
Début
Répéter
……….
Tantque TAS(lock) faire rien ;
<S.C>
Lock:= faux ;
……….
Jusqu'à sortir
Fin.
L’instruction Swap
Echange le contenu de deux mots mémoire de Procédure Swap(var a,b :booleen)
façon atomique Var temp:booleen;
Début
temp:=a;
a:=b;
b:=temp;
fin
Nous pouvons exploiter les caractéristiques de l’instruction atomiques Swap prise en charge
par le système d’exploitation pour assurer l’exclusion mutuelle comme détaillé dans l’exemple
suivant :
On utilise une variable globale Lock initialisée
à Faux.
Chaque processus dispose d’une variable
locale clé : booléen ;
Processus Pi
Clé :Booléen ;
Début
Répéter
……….
Clé := vrai ;
Repeter
Swap(lock,clé)
Jusqu'à clé = faux ;
<S.C>
Lock:= faux ;
……….
Jusqu'à sortir
Fin.
7
Système d’exploitation 3ième Ingénieur Séridi Ali
Les verrous
Pour éviter enfin l'attente active et le gaspillage qu'elle représente, on veut arrêter le
processus qui doit attendre (lui retirer le processeur). Etant arrêté, il ne peut reprendre de lui-
même son exécution. Il faudra le réveiller. C'est donc le processus qui change la condition
(libère la ressource) qui devra le faire. Pour y parvenir, il devra savoir quels processus sont
bloqués par cette condition. On associe donc au booléen une file d'attente f(v). Ainsi, un verrou
est un couple (v, f(v)), associant un booléen et une file d'attente.
Par défaut, la file d'attente est gérée en FIFO. Mais ceci n'est pas une obligation absolue.
Init : v := 0;
Déverrouiller(v) :
Verrouiller(v) :
si f(v) est non vide alors
si v=0 alors v := 1
début
sinon début
sortir un processus q de f(v);
p -> f(v);
activer q;
blocage de p;
fin
fin;
sinon v := 0;
• Un processus qui se présente entre soit en section critique, soit en file d'attente.
• Son blocage évite l'attente active.
• Le verrou et sa file d'attente sont des ressources critiques. Les procédures Verrouiller et
Déverrouiller, qui les manipulent, doivent être des sections critiques.
Deux méthodes sont possibles pour protéger les primitives :
• Si la machine est monoprocesseur => masquer les interruptions ;
• Si la machine est multiprocesseur => TAS
-Limitation des verrous
Les verrous ne permettent pas de gérer des ressources critiques à plusieurs points d'entrée,
comme par exemple un groupe de tampons.
8
Système d’exploitation 3ième Ingénieur Séridi Ali
Les sémaphores :
Introduit par Dijkstra en 1965, les sémaphores sont des outils hardware élémentaires de
synchronisation et d’exclusion mutuelle qui évitent l’attente active.
Définition :
Un sémaphore est une variable entière qui n’est pas accessible qu’à travers deux
opérations atomiques (primitives) sauf pour l’initialisation qui sont :
- P (de l’Hollandais Proberen qui veut dire tester).
- V (Verhogen qui veut dire signal).
Première Forme des sémaphores binaires :
Soit S un sémaphore.
P(s) est équivalent à : étiq : Si S0 alors aller à étiq
S := S-1
V(s) est équivalent à: S := S+1
Remarques :
- Quand un processus modifie la valeur d’un sémaphore, aucun autre processus ne peut
la modifier simultanément (pris en charge par le SE).
- Un tel sémaphore est appelé sémaphore binaire puisqu’il ne peut avoir que deux valeurs
(0 ou 1).
Utilisation des sémaphores :
a) Pour assurer l’exclusion mutuelle : Pour résoudre le problème d’accès à une section
critique par n processus on peut utiliser un sémaphore commun mutex (pour mutuelle
exclusion) initialisé à 1.
Chaque processus Pi sera décrit comme suit :
a) semaphore mutex :=1 b) semaphore Synch :=0
Processus Pi
Processus P1 Processus P2
Début
Début Début
Repeter
….. …..
…..
….. …..
P(mutex)
S1 P(synch)
Section V(synch) S2
….. …..
V(mutex)
….. …..
….. Partie restante
Fin Fin
Jusqu'à sortir
Fin
b) Pour assurer la synchronisation : Si P1 et P2 deux processus qui s’exécutent en parallèle
où S1 instruction de P1 et S2 instruction de P2. Si on veut exécuter S2 après la fin de S1, on peut
implémenter la solution ci-dessus où on utilise un sémaphore de synchronisation initialisé à 0.
9
Système d’exploitation 3ième Ingénieur Séridi Ali
Inconvénients des sémaphores binaires :
- Utilisation du principe d’attente active
- On ne peut savoir à un instant donné le nombre de processus en attente d’entrée en S.C
Pour remédier à ces inconvénients, la définition de P et V a été modifiée. L’attente active a été
substituée par le blocage du processus et le placement de ce dernier dans une file d’attente.
Ainsi l’implémentation des sémaphores est réalisée en utilisant la structure d’enregistrement.
Type sémaphore = record
Valeur : entier ;
L : liste des processus ;
Fin ;
P(S) équivalent à : [Link] := [Link]-1 ;
Si [Link] < 0 alors début
Ajouter ce processus à la liste S.L ;
Bloquer le processus ;
Fin ;
V(S) équivalent à : [Link] := [Link]+1 ;
Si [Link] 0 alors début
Enlever un processus P de la liste S.L ;
Réveiller le processus P;
Fin ;
Remarque : Avec ce type de sémaphore la valeur peut être négative, elle représente le nombre
de processus qui sont en attente d’entrée en S.C.
Les risques : la manipulation des sémaphores est laissée à la charge du programmeur ce qui
peut poser des cas de défaillance tel que :
a) L’interblocage : S et Q deux sémaphores b) Erreur de programmation
Initialisés à 1.
Processus P01 Processus P0 Processus P1
….. ….. …..
P(Q)
P(S) P(S) V(S)
P(S)
P(Q) … …
… P(S) P(S)
V(Q)
V(S) ….. …..
V(S)
V(Q)
Propriétés des sémaphores
1- La valeur d’un sémaphore n’est jamais initialisée à une valeur négative, mais peut le
devenir suite à une ou plusieurs opérations de P.
2- A tout moment [Link] =valeur initiale + Nbre de P - Nbre de V.
10
Système d’exploitation 3ième Ingénieur Séridi Ali
Exemple d’utilisation de sémaphores
Exemple 01
Pour calculer la somme des éléments d’un tableau on utilise deux processus P1 et P2. Le
premier parcourt les éléments d’indice impair et l’autre les éléments d’indice pair comme
suit :
const M = ……//taille du tableau
var T : tableau [1…M] entier ;
somme : entier initialisé a 0
Processus P1 () Processus P2 () Programme principale
var i :entier var j :entier
debut debut debut
i :=1 ; j :=2 ;
tant que (i≤M) faire tant que (j≤M) faire
P1() ; P2()
somme:= somme+ T[i]; somme:= somme+ T[j];
i:=i+2; j:=j+2; Fin
fin tant que fin tant que
fin fin
1- Quel est le problème posé par cette solution ? justifier.
2- Proposer une solution afin de résoudre ce problème.
3- Une autre variante de la solution précédente consiste à utiliser deux variables globales
somme1 et somme2. La première variable somme1 sera utilisé uniquement par P1
pour calculer la somme des éléments d’indice impair et somme2 sera utilisé
uniquement par P2 pour calculer la somme des éléments d’indice pair. Le résultat final
(somme1+somme2) sera calculé par un nouveau processus P3.
Le programme principal proposé sera :
Debut
P1 ;P2 ;P3
Fin
4- Donner les modifications nécessaires pour P1 et P2 ainsi le code de P3.
Processus P1 () Processus P2 () Programme p3 ()
Var i :entier Var j :entier
Debut Debut Debut
i :=1 ; j :=2 ;
tant que (i≤M) faire tant que (j≤M) faire Somme3 =somme1 + somme2
somme1:= somme1+ T[i]; somme2:= somme2+ T[j]; Fin
i:=i+2; j:=j+2;
fin tant que fin tant que
fin fin
11
Système d’exploitation 3ième Ingénieur Séridi Ali
Exemple 02
Soit l’exécution parallèle des deux processus suivants :
Debut
ProcessusA ;
ProcessusB ;
Fin
Q1 : Utilisez un sémaphore pour synchroniser les 2 processus de telle manière que l’exécution de la
tâche T1 ne soit jamais simultanée avec l’exécution de la tâche T2.
Q2 : Utilisez deux sémaphores pour synchroniser les 2 processus de telle manière que les tâches se
déroulent toujours dans l'ordre : T1T2T1T2T1T2...
Q3 : Utilisez deux sémaphores pour synchroniser les 2 processus de telle manière que les tâches se
déroulent toujours dans l'ordre : T1T2T2T1T2T2T1T2T2...
Solution Exemple N°1
Pour calculer la somme des éléments d’un tableau on utilise deux processus P1 et P2. Le premier
parcourt les éléments d’indice impair et l’autre les éléments d’indice pair comme suit :
Const M = ……//taille du tableau
Var T : tableau [1…M] entier ;
Somme : entier initialisé a 0
S : sémaphore init à 1 ;
Processus P1 () Processus P2 () Programme principale
Var i :entier Var j :entier
Debut Debut Debut
i :=1 ; j :=2 ;
tant que (i≤M) faire tant que (j≤M) faire P1() ; P2()
p(s) p(s)
somme:= somme+ T[i]; somme:= somme+ T[j]; Fin
v(s) v(s)
i:=i+2; j:=j+2;
fin tant que fin tant que
fin fin
1- Quel est le problème posé par cette solution ? justifier.
Problème d’exclusion mutuelle (pour protéger le variable partagé qui est
représenté par le tableau T[i] et la somme
2- Proposer une solution afin de résoudre ce problème.
La Solution utilise les sémaphores pour protéger le tableau T[i] et la somme
Le sémaphore s est initialisé à 1
12
Système d’exploitation 3ième Ingénieur Séridi Ali
3- Une autre variante de la solution précédente consiste à utiliser deux variables globales
somme1 et somme2. La première variable somme1 sera utilisé uniquement par P1
pour calculer la somme des éléments d’indice impair et somme2 sera utilisé
uniquement par P2 pour calculer la somme des éléments d’indice pair. Le résultat final
(somme1+somme2) sera calculé par un nouveau processus P3.
Le programme principal proposé sera :
Debut
P1 ;P2 ;P3
Fin
4- Donner les modifications nécessaires pour P1 et P2 ainsi le code de P3.
S1,S2 : sémaphore init à 0;
Processus P1 () Processus P2 () Programme p3 ()
Var i :entier Var j :entier
Debut Debut Debut
i :=1 ; j :=2 ; P(s1)
tant que (i≤M) faire tant que (j≤M) faire P(s2)
somme1:= somme1+ T[i]; somme2:= somme2+ T[j]; Somme3 =somme1 + somme2
i:=i+2; j:=j+2; Fin
5-
fin 6-
tant que fin tant que
v(s1) v(s2)
7-
fin 8- fin
Solution exemple 02
Q1/Utilisez un sémaphore pour synchroniser les 2 processus de telle manière que l’exécution de la
tâche T1 ne soit jamais simultanée avec l’exécution de la tâche T2.
Semaphore s=1 ;
Q2/Utilisez deux sémaphores pour synchroniser les 2 processus de telle manière que les tâches se
déroulent toujours dans l'ordre : T1T2T1T2T1T2...
Sémaphore s1=1 ; /*pour permettre au processus A de commencer*/
s2=0 ; /*pour empêcher le processus B de commencer jusqu’à ce que A le réveil */
13
Système d’exploitation 3ième Ingénieur Séridi Ali
Q3/Utilisez deux sémaphores pour synchroniser les 2 processus de telle manière que les tâches se
déroulent toujours dans l'ordre : T1T2T2T1T2T2T1T2T2...
Sémaphore s1=2 ; /*pour permettre au processus A de commencer*/
s2=0 ; /*pour empêcher le processus B de commencer jusqu’à ce que A le réveil */
Exemple 03
Problème des philosophes
Soit 5 philosophes qui sont réunis autour d’une table. Chacun d’eux
Processus Philosophe(i)
dispose d’une fourchette et un plat de spaghetti. Pour manger un Début
philosophe a besoin des deux fourchettes droite et gauche, si l’une Repeter
Penser()
seulement est disponible, il ne doit pas la prendre.
Prendre_fourchettes()
Manger()
Chaque philosophe ne fait que penser, manger ou attendre les Déposer_fourchettes()
fourchettes pour manger (faim) selon le processus suivant : Jusqu'à sortir
Fin
- Proposer une solution à ce problème en utilisant les sémaphores.
14
Système d’exploitation 3ième Ingénieur Séridi Ali
Solution au Pb des philosophes :
Etat[0..4] : tableau de {‘Faim’,’Penser’,’Manger’} initialisé à ‘penser’ ;
S [0..4] : tableau de sémaphores init à 0 ;
mutex : sémaphore initialisé à 1 ;
Gauche = (i+4)mod5 ; Droite = (i+1)mod5
Procédure Prendre-Fourchette(i)
Début
P(mutex) ;
Procédure test(i)
Etat[i] :=’faim’ ; Début
test(i) ; Si Etat[i] =’Faim’ et Etat[Droite] ’manger’ et
V(mutex) ; Etat[Gauche] ’manger’ alors
Debut
P(S[i]);
Etat[i] := ‘manger’ ;
Fin V(S[i]);
Fin
Fin
Procédure Déposer-Fourchettes(i)
Début
P(mutex) ;
Etat[i] :=’Pensé’;
test(Gauche) ;
test(Droite) ;
V(mutex) ;
Fin.
15