Chapitre 01
Synchronisation des
processus
Dr. Mohamed-Wassim YOUSSEF
[[Link] @ [Link]]
Systèmes d’exploitation avancées
M1Recherche
Synchronisation des 2
processus
Architectures et Systèmes Evolués
1. Introduction
2. Sections critiques et exclusion mutuelle
3. Exclusion mutuelle par attente active
1. Le masquage des interruptions
2. Les variables de verrouillage
3. L’alternance stricte
4. La solution de Peterson
4. Exclusion mutuelle sans attente active
a. Les primitives sleep et wakeup
b. Les sémaphores
a. Exercices
c. Les moniteurs
Introduction
3
¡ Sur une plateforme multiprogrammée les processus ont
généralement besoin de communiquer pour compléter
leurs tâches.
¡ Un processus est dit indépendant, s’il n’affecte pas les
autres processus ou ne peut pas être affecté par eux. Un
processus qui ne partage pas de données avec d’autres
processus est indépendant.
¡ Un processus est dit coopératif s’il peut affecter les autres
processus en cours d’exécution ou être affecté par eux. Un
processus qui partage des données avec d’autres processus
est un processus coopératif.
¡ Les données partagées par les processus coopératifs se
trouvent en mémoire principale ou en mémoire secondaire
dans un fichier. Il y a alors risque d’incohérence des
données.
Introduction
4
¡ Sur une plateforme multiprogrammée les processus ont
généralement besoin de communiquer pour compléter
leurs tâches.
¡ L’exécution d’un processus peut être affectée par
l’exécution des autres processus ou il peut affecter lui-
même leurs exécutions.
La communication interprocessus est assurée généralement via des
données partagées qui peuvent se trouver dans la mémoire
principale ou dans un fichier.
Les accès concurrents (simultanés) à des données
partagées peuvent conduire à des incohérences dans
les résultats obtenus.
Exemple Illustratif
5
Exemple : la spoule d’impression
Démon d’impression
Processus A
… 3 2 1 0
… f2 f1 f0 Répertoire de spoule
Processus B Variable partagée in=3
Indique la prochaine case vide
Schéma d’exécution:
Processus A : Processus B :
read in, lire in,
case_id = in case_id = in,
Préemption: la CPU bascule vers le spool[case_id] = fichierB,
processus B in ++ ;
Processus A :
spool[case_id] = fichierA,
in ++ ;
Problème: le fichierB ne sera jamais imprimé
Sections critiques et exclusion mutuelle
6
¡ Le problème précédent est dû aux conflits d’accès à la
même ressource.
¡ La partie du programme à partir de laquelle on accède à la
ressource partagée est appelée section (région) critique.
Solution: L’exclusion mutuelle est une méthode qui assure
qu’un seul processus est autorisé d’accéder à une ressource
partagée; les autres processus seront exclus de la même
activité.
(@t1) A entre dans sa (@t3) A quitte sa section
section critique
VUE SIMPLIFIÉE
critique
A
(@t4) B quitte sa
section critique
B
t1 t2 t3 t4
(@t2) B tente d’entrer dans (@t3) B entre dans sa
sa section critique section critique
Modèle d’exécution de processus
7
¡ Un processus désirant entrer dans une section critique doit
être mis en attente jusqu’a ce que la section critique
devient libre.
¡ Un processus quittant la section critique doit le signaler aux
autres processus.
Algorithme d’accès à une section critique :
Entrer_Section_Critique () /* attente si SC non libre */
Section_Critique() /* un seul processus en SC */
Quitter_Section_Critique()
L’attente peut être :
• Active : la procédure Entrer_Section_Critique est une boucle
dont la condition est un test qui porte sur des variables indiquant
la présence ou non d’un processus en Section critique.
• Non active : le processus passe dans l’état endormi et ne sera
réveillé que lorsqu’il sera autorisé à entrer en section critique.
Conditions requise en vue d’une bonne
synchronisation entre les processus
¡ Quatre conditions doivent être vérifiées pour assurer
une bonne synchronisation entre les processus:
1. Exclusion Mutuelle: Deux processus ne doivent pas
se trouver simultanément dans leurs sections critiques.
2. Progression : Aucun processus à l’extérieur de sa
section critique ne doit bloquer les autres processus.
3. Attente bornée : Aucun processus ne doit attendre
indéfiniment pour entrer dans sa section critique.
4. Aucune hypothèse : Il ne faut pas faire d’hypothèse
quant à la vitesse ou le nombre de processeurs
Synchronisation des 9
processus
9
1. Introduction
2. Sections critiques et exclusion mutuelle
3. Exclusion mutuelle par attente active
1. Le masquage des interruptions
2. Les variables de verrouillage
3. L’alternance stricte
4. La solution de Peterson
4. Exclusion mutuelle sans attente active
a. Les primitives sleep et wakeup
b. Les sémaphores
a. Exercices
c. Les moniteurs
Solutions de l’exclusion mutuelle par attente
active 10
¡ Solution 1: Masquage des interruptions
§ Lorsqu’un processus entre en section critique il doit masquer
les interruptions.
Pas de commutation de processus
§ Lorsqu’ il quitte sa section critique il doit restaurer les
interruptions.
• C’est une solution matérielle qui permet de résoudre
complètement le problème. Mais elle est dangereuse en mode
utilisateur s’il oublie de restaurer les interruptions.
Solutions de l’exclusion mutuelle par attente
active 11
Solution 2: Variables de verrouillage
Un verrou est variable binaire partagée qui indique la présence d’un
processus en section critique.
si verrou=0 alors section critique libre
si verrou=1 alors section critique occupée
void entrer_Section_Critique () Void quitter_Section_Critique ()
{ {
while (verrou == 1) ; /* attente active */ verrou=0 ;
verrou=1 ; }
}
Cette solution ne garantie pas l’exclusion mutuelle car le verrou est une
variable partagée qui peut constituer aussi une section critique.
Solutions de l’exclusion mutuelle par attente
active 12
Solution 2-bis : Variables de verrou en matériel: TSL (Test and Set Lock)
Aussi appelée TAS pour Test And Set.
Est une instruction indivisible: réalisée une seule fois par le matériel.
TSL REGISTER, LOCK
(1) Lit le contenu de LOCK dans REGISTRE //(1) et (2) sont indivisibles
(2) Ecrit 1 dans adresse mémoire LOCK // (TSL instruction atomique)
|pseudo-assembleur
entrer_Section_Critique:
TSL REGISTER, LOCK | copie lock dans reg et la définit à 1
CMP REGISTER, #0 | lock etait-elle à 0
JNE entrer_SC | si elle était pas à 0, boucle
RET | retourne à appelant, entre dans SC
quitter_Section_Critique:
MOVE LOCK, #0 | stocke un 0 dans lock
RET | retourne à l’appelant
Solutions de l’exclusion mutuelle par attente
active 13
Solution 3: Alternance stricte
Tour est une variable partagée qui indique le numéro de processus autorisé
a entrer en section critique.
void entrer_Section_Critique (int process) Void quitter_Section_Critique ()
{ {
while (Tour!=process) ; /* attente active */ Tour = (Tour+1) %N ;
} }
L’alternance stricte est une solution simple et facile a implémenter.
Mais, un processus qui possède Tour peut ne pas être intéressé
immédiatement par la section critique et en même temps il bloque un
autre processus qui est demandeur.
Problème de progression
Solutions de l’exclusion mutuelle par attente
active 14
Solution 4: Solution de Peterson
#define FAUX 0 Void quitter_Section_Critique ()
#define VRAI 1 {
#define N 2 (4) interesse[process]=FAUX ;
int tour ; /* à qui le tour */ }
int interesse[N] ; /* initialisé à FAUX */
void entrer_Section_Critique (int process)
{
int autre ; Cette solution assure
(1) autre = 1-process ; complètement l’exclusion
(2) interesse[process]=VRAI; /* process est intéressé */ mutuelle.
(3) tour = process ; /* demander le tour */ Mais, le processus qui attend
while (tour == process && interesse[autre] == VRAI) ; sa section critique
} (A) (B) consomme du temps
processeur inutilement
(attente active).
Peterson N-processus
#define FALSE 0
#define N 10 /* First process is indicated with 1, not 0 */
int turn[N];
int stage[N + 1];
void enterRegion(int process) void leaveRegion(int process)
{
int i, j; {
for (i = 1; i <= N - 1; i++) { stage[process] = FALSE;
stage[process] = i; }
turn[i] = process;
for (j = 1; j <= N; j++) {
if (j == process)
continue;
while (stage[j] >= i && turn[i] == process) ;
}
}
}
Synchronisation des 16
processus
16
1. Introduction
2. Sections critiques et exclusion mutuelle
3. Exclusion mutuelle par attente active
1. Le masquage des interruptions
2. Les variables de verrouillage
3. L’alternance stricte
4. La solution de Peterson
4. Exclusion mutuelle sans attente active
a. Les primitives sleep et wakeup
b. Les sémaphores
a. Exercices
c. Les moniteurs
Exclusion mutuelle sans attente active
17
L’idée est qu’un processus qui ne peut pas entrer en section critique
passe à l’état bloqué au lieu de consommer le temps processeur
inutilement. Il sera réveillé lorsqu’il pourra y entrer.
Les primitives Sleep et Wakeup:
Le système d’exploitation offre deux appels système:
1. Sleep (dormir) qui bloque le processus appelant.
2. Wakeup (réveiller) qui réveille le processus donné en argument.
Exclusion mutuelle sans attente active
18
Application des primitives Sleep et Wakeup au modèle Producteur
Consommateur:
Producteur
… f2 f1 f0 Tampon
Variable partagée Consommateur
compteur=3
Deux processus (le producteur et le consommateur) coopèrent en
partageant un même tampon:
• Le producteur produit des objets qu’il dépose dans le tampon.
• Le consommateur retire des objets du tampon pour les
consommer.
Exclusion mutuelle sans attente active
19
#define N 100 /* taille du tampon */
int compteur = 0 ; /* objets dans tampon */
void producteur () { void consommateur () {
while (TRUE) while (TRUE)
{ {
produire_objet() ; if (compteur == 0) {
if (compteur == N) sleep () ; sleep() ;
mettre_objet() ; }
compteur = compteur + 1 ; retirer_objet()
if (compteur == 1) compteur = compteur – 1 ;
wakeup(consommateur) ; if (compteur == N-1)
} wakeup (producteur) ;
} consommer_objet(…) ;
}
}
Exclusion mutuelle sans attente active
20
¡ Analyse de cette solution :
§ L’accès à la variable compteur n’est pas protégé, ce qui peut
entraîner des incohérences dans les valeurs prises par cette
Variable.
§ Réveils perdus : c’est le principal défaut de ce mécanisme. Un
signal wakeup envoyé à un processus qui ne dort pas
(encore)est perdu.
Les sémaphores
21
Pour remédier au problème es réveils en attente (les wakeup perdus),
l’idée est d’employé une variable entière appelée: Sémaphore à laquelle
est associée une file d’attente des processus bloqués.
sémaphore=0 à aucun réveil n’est mémorisé
sémaphore>0 à un ou plusieurs réveils sont en attente
Un sémaphore s est manipulé par les opérations :
1. down(s) : - décrémente la valeur de s si s>0,
- si s=0, alors le processus est mis en attente.
2. up(s) : - incrémente la valeur de s,
- si un ou plusieurs processus sont en attente sur ce
sémaphore, l'un d'entre eux est réveillé,
Les sémaphores
22
¡ Pour assurer l’exclusion mutuelle un sémaphore peut
être programmé de la manière suivante :
Nom du sémaphore
initialisation mutex = 1 /* nombre de processus autorisés à entrer
simultanément dans la section critique */
down (mutex)
<section_critique>
up (mutex)
Les sémaphores
23
¡ Application au modèle Producteur / Consommateur :
¡ Trois sémaphores sont nécessaires:
§ plein: compte le nombre de places occupées
§ vide : compte le nombre de places libres
§ Mutex : assure que le producteur et le consommateur
n'accèdent jamais en même moment à la mémoire tampon.
Rappel
Producteur/Consommateur avec sémaphores24
#define N 100 // taille du tampon
semaphore mutex 1 ; // contrôle d’accès section critique
semaphore vide N; // contrôle les emplacements vide
Semaphore plein 0; // contrôle les emplacements plein
void producteur () { void consommateur () {
while (TRUE){ while (TRUE){
produire_objet() ;
down(vide); down(plein);
down(mutex); down(mutex);
mettre_objet() ; //SC retirer_objet() //SC
up(mutex); up(mutex);
up(plein) up(vide);
consommer_objet(…) ;
} }
} }
Synchronisation des
processus - Exercices
25
1. Ordonnancement & Synchronisation
2. Pb des Lecteurs/rédacteur
3. Pb du coiffeur endormi
4. Autres utilisations des sémaphores & problèmes
classiques
Exercice 1
26
¡ Q1 : Round robin ( tourniquet) avec q=5ms
Prêt à l’instant Durée
t= d’exécution
P0 0 ms 23 ms
P1 1 ms 17 ms
P2 2 ms 15 ms
¡ Q2 : Round robin ( tourniquet) avec q=5ms +
Synchronisation Attente Active
Durée
Date d’entrée en
Prêt à l’instant Durée d’exécution en d’exécution
section critique t=
t= section critique SR+SC
P0 0 ms 11 ms P0 23 ms 3 ms
P1 1 ms 10 ms P1 17 ms 7 ms
P2 2 ms X P2 15 ms X
Q1
¡ Round robin ( tourniquet) avec q=5ms
Prêt à l’instant Durée
P0 t= d’exécution
P1 P0 0 ms 23 ms
P2 P1 1 ms 17 ms
P2 2 ms 15 ms
0 5 10 15 20 25 30 35 40
40 45 50 52 55
Q2
¡ Round robin ( tourniquet) avec q=5ms
¡ Peterson è Attente active
SC AA
Prêt à l’instant Durée Date d’entrée en Durée d’exécution en
P0 t= d’exécution section critique t= section critique
P1 P0 0 ms 23 ms 3 ms 12 ms
P2 P1 1 ms 17 ms 7 ms 10 ms
P2 2 ms 15 ms X X
0 5 10 15 20 25 30 35 40
40 45 50 55 58
Q3
¡ Round robin ( tourniquet) avec q=5ms
¡ Sommeil et activation
SC
Prêt à l’instant Durée Date d’entrée en Durée d’exécution en
P0 t= d’exécution section critique t= section critique
P1 P0 0 ms 23 ms 3 ms 12 ms
P2 P1 1 ms 17 ms 7 ms 10 ms
P2 2 ms 15 ms X X
0 5 10 15 20 22 27 32 37 40
40 42 47 52 55
30
