Institut Suprieur dInformatique
Chapitre 02
Rappel sur la synchronisation des
processus
Dr. MohamedMohamed-Wassim YOUSSEF
2010
[[Link]]
Systmes dexploitation Evolus
M1 - ISI
1re anne Mastere en Informatique
Synchronisation des
processus
1.
2.
3.
Introduction
Sections critiques et exclusion mutuelle
Exclusion mutuelle par attente active
Le masquage des interruptions
Les variables de verrouillage
Lalternance stricte
La solution de Peterson
1.
2.
3.
4.
4.
Exclusion mutuelle sans attente active
Les primitives sleep et wakeup
Les smaphores
a.
b.
a.
c.
Exercices
Les moniteurs
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Introduction
3
Sur une plateforme multiprogramme les processus ont
gnralement besoin de communiquer pour complter leurs
tches.
Lexcution dun processus peut tre affecte par lexcution
des autres processus ou il peut affecter lui-mme leurs
excutions.
La communication interprocessus est assure gnralement via des
donnes partages qui peuvent se trouver dans la mmoire principale ou
dans un fichier.
Les accs concurrents (simultans) des donnes partages
peuvent conduire des incohrences dans les rsultats
obtenus.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Introduction: exemple illustratif
4
Exemple : la spoule dimpression
Dmon dimpression
Processus A
f2
f1
Processus B
f0
Rpertoire de spoule
Variable partage in=3
Schma dexcution:
A : lire in,
next_free_slot = 3
Interruption: la CPU bascule vers le
processus B
B : lire in,
next_free_slot = 3,
entre3 = fichierB,
in = 4
A : entre3 = fichierA,
in = 4
Problme: le fichierB ne sera jamais imprim
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Sections critiques et exclusion mutuelle
5
Le problme prcdent est d aux conflits daccs la mme
ressource.
La partie du programme partir de laquelle on accde la
ressource partage est appele section (rgion) critique.
Solution: Lexclusion mutuelle est une mthode qui assure quun seul
processus est autoris daccder une ressource partage; les autres
processus seront exclus de la mme activit.
A entre dans sa section
critique
A quitte sa section
critique
B quitte sa section
critique
B
t1
B tente dentrer dans sa
section critique
t2
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
t3
t4
B entre dans sa section
critique
M1- ISI 2010
Sections critiques et exclusion mutuelle
Quatre conditions doivent tre vrifies pour assurer
lexclusion mutuelle:
Exclusion Mutuelle: Deux processus ne doivent pas se
trouver simultanment dans leurs sections critiques.
2. Progression : Aucun processus lextrieur de sa section
critique ne doit bloquer les autres processus.
3. Attente borne : Aucun processus ne doit attendre
indfiniment pour entrer dans sa section critique.
4. Aucune hypothse : Il ne faut pas faire dhypothse quant
la vitesse ou le nombre de processeurs
1.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Synchronisation des
processus
1.
2.
3.
Introduction
Sections critiques et exclusion mutuelle
Exclusion mutuelle par attente active
Le masquage des interruptions
Les variables de verrouillage
Lalternance stricte
La solution de Peterson
1.
2.
3.
4.
4.
Exclusion mutuelle sans attente active
Les primitives sleep et wakeup
Les smaphores
a.
b.
a.
c.
Exercices
Les moniteurs
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Exclusion mutuelle par attente active
8
Un processus dsirant entrer dans une section critique doit
tre mis en attente jusqua ce que la section critique devient
libre.
Un processus quittant la section critique doit le signaler aux
autres processus.
Algorithme daccs une section critique :
Entrer_Section_Critique ()
/* attente si SC non libre */
Section_Critique()
/* un seul processus en SC */
Quitter_Section_Critique()
Lattente peut tre :
Active : la procdure Entrer_Section_Critique est une boucle dont la
condition est un test qui porte sur des variables indiquant la prsence
ou non dun processus en Section critique.
Non active : le processus passe dans ltat endormi et ne sera rveill
que lorsquil sera autoris entrer en section critique.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Solutions de lexclusion mutuelle par attente
active
Solution 1: Masquage des interruptions
Lorsquun 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.
Cest une solution matrielle qui permet de rsoudre
compltement le problme. Mais elle est dangereuse en mode
utilisateur sil oublie de restaurer les interruptions.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Solutions de lexclusion mutuelle par attente
active
10
Solution 2: Variables de verrouillage
Un verrou est une variable binaire partage qui indique la prsence dun
processus en section critique.
si verrou=0 alors section critique libre
si verrou=1 alors section critique occupe
void entrer_Section_Critique ()
{
while (verrou == 1) ; /* attente active */
verrou=1 ;
}
Void quitter_Section_Critique ()
{
verrou=0 ;
}
Cette solution ne garantie pas lexclusion mutuelle car le verrou est une
variable partage qui peut constituer aussi une section critique.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Solutions de lexclusion mutuelle par attente
active
11
Solution 3: Alternance stricte
Tour est une variable partage qui indique le numro de processus autoris
entrer en section critique.
void entrer_Section_Critique (int process)
{
while (Tour!=process) ; /* attente active */
}
Void quitter_Section_Critique ()
{
Tour = (Tour+1) %N ;
}
Lalternance stricte est une solution simple et facile a implmenter.
Mais, un processus qui possde Tour peut ne pas tre intress
immdiatement par la section critique et en mme temps il bloque un
autre processus qui est demandeur.
Problme de progression
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Solutions de lexclusion mutuelle par attente
active
12
Solution 4: Solution de Peterson
#define FAUX 0
#define VRAI 1
#define N 2
int tour ; /* qui le tour */
int interesse[N] ; /* initialis FAUX */
void entrer_Section_Critique (int process)
{
int autre ;
(1) autre = 1-process ;
(2) interesse[process]=VRAI; /* process est intress */
(3) tour = process ;
/* demander le tour */
while (tour == process && interesse[autre] == VRAI) ;
(A)
(B)
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
Void quitter_Section_Critique ()
{
(4) interesse[process]=FAUX ;
}
Cette solution assure
compltement lexclusion
mutuelle.
Mais, le processus qui attend
sa section critique
consomme du temps
processeur inutilement
(attente active).
M1- ISI 2010
Synchronisation des
processus
13
13
1.
2.
3.
Introduction
Sections critiques et exclusion mutuelle
Exclusion mutuelle par attente active
Le masquage des interruptions
Les variables de verrouillage
Lalternance stricte
La solution de Peterson
1.
2.
3.
4.
4.
Exclusion mutuelle sans attente active
Les primitives sleep et wakeup
Les smaphores
a.
b.
a.
c.
Exercices
Les moniteurs
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Exclusion mutuelle sans attente active
14
Lide est quun processus qui ne peut pas entrer en section critique
passe ltat bloqu au lieu de consommer le temps processeur
inutilement. Il sera rveill lorsquil pourra y entrer.
Les primitives Sleep et Wakeup:
Le systme dexploitation offre deux appels systme:
1. Sleep (dormir) qui bloque le processus appelant.
2. Wakeup (rveiller) qui rveille le processus donn en argument.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Exclusion mutuelle sans attente active
15
Application des primitives Sleep et Wakeup au modle Producteur
Consommateur:
Producteur
f2
f1
Variable partage
compteur=3
f0
Tampon
Consommateur
Deux processus (le producteur et le consommateur) cooprent en
partageant un mme tampon:
Le producteur produit des objets quil dpose dans le tampon.
Le consommateur retire des objets du tampon pour les
consommer.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Exclusion mutuelle sans attente active
16
#define N 100 /* taille du tampon */
int compteur = 0 ; /* objets dans tampon */
void producteur () {
while (TRUE)
{
produire_objet() ;
if (compteur == N) sleep () ;
mettre_objet() ;
compteur = compteur + 1 ;
if (compteur == 1)
wakeup(consommateur) ;
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
void consommateur () {
while (TRUE)
{
if (compteur == 0) sleep() ;
retirer_objet()
compteur = compteur 1 ;
if (compteur == N-1)
wakeup (producteur) ;
consommer_objet() ;
}
}
M1- ISI 2010
Exclusion mutuelle sans attente active
17
Analyse de cette solution :
Laccs la variable compteur nest pas protg, ce qui peut entraner
des incohrences dans les valeurs prises par cette Variable.
Rveils perdus : cest le principal dfaut de ce mcanisme. Un signal
wakeup envoy un processus qui ne dort pas (encore) est perdu.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Les smaphores
18
Pour remdier au problme des rveils en attente (les wakeup perdus),
lide est demployer une variable entire appele: Smaphore laquelle
est associe une file dattente des processus bloqus.
smaphore=0 aucun rveil nest mmoris
smaphore>0 un ou plusieurs rveils sont en attente
Un smaphore s est manipul par les oprations :
1.
down(s) : - dcrmente la valeur de s si s>0,
- si s=0, alors le processus est mis en attente.
2.
up(s) : - incrmente la valeur de s,
- si un ou plusieurs processus sont en attente sur ce
smaphore, l'un d'entre eux est rveill,
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Les smaphores
19
Pour assurer lexclusion mutuelle un smaphore peut tre
programm de la manire suivante :
Nom du smaphore
initialisation mutex = 1 /* nombre de processus autoriss entrer
simultanment dans la section critique */
down (mutex)
<section_critique>
up (mutex)
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Les smaphores
20
Application au modle Producteur / Consommateur :
Trois smaphores sont ncessaires:
plein: compte le nombre de places occupes
vide : compte le nombre de places libres
Mutex : assure que le producteur et le consommateur n'accdent
jamais en mme moment la mmoire tampon.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Rappel
Producteur/Consommateur avec smaphores
#define N 100
semaphore mutex 1 ;
semaphore vide N;
Semaphore plein 0;
//
//
//
//
21
taille du tampon
contrle daccs section critique
contrle les emplacements vide
contrle les emplacements plein
void producteur () {
while (TRUE){
produire_objet() ;
down(vide);
down(mutex);
mettre_objet() ; //SC
up(mutex);
up(plein)
void consommateur () {
while (TRUE){
down(plein);
down(mutex);
retirer_objet() //SC
up(mutex);
up(vide);
consommer_objet() ;
}
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Synchronisation des
processus - Exercices
22
1.
2.
3.
4.
Ordonnancement & Synchronisation
Pb des Lecteurs/rdacteur
Pb du coiffeur endormi
Autres utilisations des smaphores & problmes classiques
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Exercice 1
23
Q1 : Round robin ( tourniquet) avec q=5ms
Prt linstant
t=
Dure
dexcution
P0
0 ms
23 ms
P1
1 ms
17 ms
P2
2 ms
15 ms
Q2 : Round robin ( tourniquet) avec q=5ms +
Synchronisation Peterson
Dure
dexcution
SR+SC
Date dentre en
section critique t=
Prt linstant
t=
Dure dexcution en
section critique
P0
0 ms
12 ms
P0
23 ms
3 ms
P1
1 ms
10 ms
P1
17 ms
7 ms
P2
2 ms
P2
15 ms
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Q1
Round robin ( tourniquet) avec q=5ms
P0
Prt linstant
t=
Dure
dexcution
P1
P0
0 ms
23 ms
P2
P1
1 ms
17 ms
P2
2 ms
15 ms
10
40
45
50
15
52
20
25
30
35
40
55
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Q2
Round robin ( tourniquet) avec q=5ms
Peterson Attente active
SC AA
P0
Prt linstant
t=
Dure
dexcution
Date dentre en
section critique t=
Dure dexcution en
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
10
15
40
45
50
55
20
25
30
35
40
58
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Q3
Round robin ( tourniquet) avec q=5ms
Sommeil et activation
SC
P0
Prt linstant
t=
Dure
dexcution
Date dentre en
section critique t=
Dure dexcution en
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
40
42
10
47
15
52
20
22
27
32
37
40
55
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Peterson NN-processus
#define FALSE 0
#define N 10 /* First process is indicated with 1, not 0 */
int turn[N+1];
int stage[N + 1];
void enterRegion(int process)
void leaveRegion(int process)
{
{
int i, j;
stage[process] = FALSE;
for (i = 1; i <= N - 1; i++) {
stage[process] = i;
}
turn[i] = process;
for (j = 1; j <= N; j++) {
if (j == process)
continue;
while (stage[j] >= i && turn[i] == process) ;
}
}
}
FAIRE TOURNER POUR PROCESS=1 et PROCESS=2 !!!!!!
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Lecteurs/Rdacteur
28
Une base de donnes peut tre accessible par un seul
rdacteur ou N lecteurs en mme temps
Exclusion mutuelle entre le rdacteur et les N lecteurs
Donner le pseudo code dun processus lecteur et celui du processus
rdacteur
Base de donnes
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Lecteurs/Rdacteur
29
Semaphore mutex 1
Semaphore db 1
int nb_lect = 0 ;
//lecteur
void lecture(){
while (true) {
//
//
//
//
//
contrle laccs nb_lect
contrle laccs la base de donnes
var partages entre lecteurs pour
compter le nombre de lecteurs accdant
actuellement la BD
//boucle sans fin
//redacteur
void ecriture(){
while (true) {
crer_donnes ();
lire_la_BD();
//accs la BD
ecrire_dans_la_BD
utiliser_donnes ();
}
//Section restante
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Lecteurs/Rdacteur
30
Semaphore mutex 1
Semaphore db 1
int nb_lect = 0 ;
//lecteur
void lecture(){
while (true) {
//
//
//
//
//
contrle laccs nb_lect
contrle laccs la base de donnes
var partages entre lecteurs pour
compter le nombre de lecteurs accdant
actuellement la BD
//boucle sans fin
down (mutex);
// la modif de la var. partage nb_lect est une
nb_lect ++;
// section critique entre lecteurs
if (nb_lect == 1) down (db);
//si le premier lecteur
up(mutex);
// libre laccs exclusif nb_lect
lire_la_BD();
//accs la BD
down(mutex);
nb_lect --;
if (nb_lect == 0) up (db);
//si le dernier lecteur
up (mutex)
utiliser_donnes (); //Section restante
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Lecteurs/Rdacteur
31
Semaphore mutex 1
Semaphore db 1
int nb_lect = 0 ;
//redacteur
void ecriture(){
while (true) {
crer_donnes ();
//
//
//
//
//
contrle laccs nb_lect
contrle laccs la base de donnes
var partages entre lecteurs pour
compter le nombre de lecteurs accdant
actuellement la BD
//boucle sans fin
//Section restante
down (db);
ecrire_dans_la_BD();
up (db);
//accs la BD
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Coiffeur endormi
32
Un coiffeur possde un salon avec un sige de coiffeur et une salle
dattente comportant un nombre fixe F de fauteuils.
Sil ny a pas de client, le coiffeur se repose sur son sige de
coiffeur.
Si un client arrive et trouve le coiffeur endormi, il le rveille,
sassoit sur le sige de coiffeur et attend la fin de sa coupe de
cheveux.
Si le coiffeur est occup lorsquun client arrive, le client sassoit et
sendort sur une des chaises de la salle dattente ; si la salle
dattente est pleine, le client ressort.
Lorsque le coiffeur a termin une coupe de cheveux, il fait sortir
son client courant et va rveiller un des clients de la salle dattente.
Si la salle dattente est vide, il se rendort sur son sige jusqu ce
quun nouveau client arrive.
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Coiffeur endormi
33
Rsoudre le pb en vitant les conditions de concurrence
Utilisation de 3 smaphores et un compteur
Semaphore Clients 0;
//bloque le coiffeur sil ny a pas de clients
Semaphore Mutex 1;
//accs exclusif la zone critique
Semaphore Coiffeurs 0;
//bloque le client si
//autre client
le coiffeur est occup avec un
Int Attente = 0 ;
//Le nombre de clients en attente
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Coiffeur endormi
34
Semaphore Clients 0;
Semaphore Mutex 1;
Semaphore Coiffeurs 0;
Int Attente = 0 ;
//Coiffeur
void coiffeur() {
while(1){
//Client
void client() {
if (
) {
Attente = attente + 1
Attente = attente 1;
Obtenir_coupe
}
Couper_cheveux();
else {
}
}
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Coiffeur endormi
35
Semaphore Clients 0;
Semaphore Mutex 1;
Semaphore Coiffeurs 0;
Int Attente = 0 ;
//Client
void client() {
down(Mutex)
//Coiffeur
void coiffeur() {
while(1){
down(Clients);
if (Attente < Chaises) {
Attente = attente + 1
up(Clients) //rveiller coiffeur
up(Mutex)
//attendre son rle pour se
coiffer
down(Coiffeurs)
Obtenir_coupe
}
down(Mutex);
Attente = attente 1;
//rveiller un client
//dans la salle
up(Coiffeurs);
up(Mutex);
Couper_cheveux();
}
}
else {
up(Mutex) //le client part si
pas de chaise
}
}
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Rflchissons !
36
Soient les deux processus P1 et P2 suivants. Ils se partagent
deux smaphores S1 et S2 initialiss 0.
Semaphore S1 0
Semaphore S2 0
P1 {
procedure A1 ;
Up(S2) ;
Down(S1) ;
procedure B1 ;
}
P2 {
procedure A2 ;
Up(S1) ;
Down(S2) ;
procedure B2 ;
}
Quelle synchronisation a-t-on impose sur les excutions des
procdures A1, A2, B1 et B2 (cd, quel ordre dexcution) ?
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
Barrire de synchronisation
37
Les Ai sexcutent toujours avant les Bi, quelque soit lordre de
lexcution des processus P1 et P2
Semaphore S1 0
Semaphore S2 0
P1 {
procedure A1 ;
Up(S2) ;
Down(S1) ;
procedure B1 ;
}
P2 {
procedure A2 ;
Up(S1) ;
Down(S2) ;
procedure B2 ;
}
Ex: Ecrire le code afin dimposer la mme synchronisation pour N
processus en utilisant :
N smaphores
2smaphores et un compteur
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
38
P(i) {procedure A down(mutex); i++;
if(i<N) {up(mutex); down (S[i]); up(S[i+1]);} //bloqu au niveau de son
smaphore, attend que le prcdent le dbloque
Else {up(mutex); up(S[1]); down(S[N]);} //cest le Nme processus qui
commence le dblocage du process 1 qui son tour dbloque le
process 2,
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010
39
smaphore mutex = 1, B= 0;
int compteur = 0; /* nbre de processus arrivs au rendez-vous */
Procdure RDV
Dbut
Procedure A
down(mutex);
compteur ++;
if(compteur< N) /* non tous arrivs */
{ up(mutex); /* on libre mutex et */
down(B); /* on se bloque */
}else
{up(mutex); /* le dernier arriv libre mutex et */
for(i = 1 ;i< N-1 ;i++) up(B); /* rveille les N-1 bloqus, dans l'ordre
d'arrive */
}
Procedure B;
Fin
Dr. Mohamed Wassim Youssef Systmes dexploitation volus
M1- ISI 2010