1

Synchronisation des
processus
2
3
 On désire effectuer une somme des N premiers nombres en utilisant
des processus légers.
 On divise le travail en deux processus
 Le 1 er calcul S1=1+2+…+M; M=N%2
 Le 2 eme calcul S2=(M+1)+ (M+2)+…+N
 somme_totale =S1+S2

4
 7
Pointer à la case 9 : la
in Ecrasement du fichier
case 8 ne sera jamais
A utilisée. B de A dans la case 7

1- Ecrire dans le spool 2- Ecrire dans le spool Pointer à la case 8.

4- Incrémentation de “in” 3- Incrémentation de “in”

5
 Résultat attendu :
solde=100

solde est toujours égale à

1000 6
 A1,
A2

7
8
9
Indiquer que la section critique est
occupée

Indiquer que la section critique est

libérée

10
11
Interruption

12
13
14
15
flag[i]=flag[j]

16
17
 Problème : attente active = consommation du temps CPU 18
19
 Valeur initiale de verrou est 0.

 entrer_region :
while(TSL(verrou) ) ;

 quitter_region :
verrou =0;

20
21
section
22
23
24
 a

Tampon plein : blocage du

producteur.
Tampon vide: blocage du
consommateur

25
26
27
 Moniteur = { variables globales + sections critiques d’un
même problème}
 Pour assurer l’exclusion mutuelle, à tout moment un
processus au plus est actif dans le moniteur.
 Si un processus est actif dans le moniteur et un autre
demande à y accéder (appel une procédure du moniteur), ce
dernier est mis en attente.
 C’est le compilateur qui se charge de cette tâche. Pour ce
faire, il rajoute au moniteur le code nécessaire pour assurer
l’exclusion mutuelle.
 Cette solution est plus simple que les sémaphores et autres
solutions, puisque le programmeur n’a pas à se préoccuper
de contrôler les accès aux sections critiques.
 La majorité des compilateurs utilisés actuellement ne
supportent pas les moniteurs (à l’exception de JAVA,
Concurrent Pascal et Modula-3). 28
 Est un module contenant:
 une ou plusieurs procédures
 une séquence d’initialisation
 Variables globales et locales
 Caractéristiques:
 variables locales accessibles seulement à l’aide d’une
procédure du moniteur
 un thread entre dans le moniteur en invoquant une de
ses procédures
 un seul thread peut s’exécuter dans le moniteur à tout
instant
29
 Il assure à lui seul l’exclusion mutuelle: pas besoins
de le programmer explicitement
 On assure la protection des données partagées en
les plaçant dans le moniteur
 Le moniteur verrouille les données partagées
lorsqu’un thread y entre
 Synchronisation de threads est effectuée en
utilisant des variables conditionnelles qui
représentent des conditions après lesquelles un
thread pourrait attendre avant d’exécuter dans le
moniteur
30
monitor nom-de-moniteur
{ // déclarations de vars/Const
public entryp1(. . .) {code de méthode p1}
public entryp2(. . .) {code de méthode p2}
...
<Initialisation des vars/Const>
}

 La seule façon de manipuler les vars internes au

moniteur est d’appeler une des méthodes d’entrée
31
32
 Le processus actif dans le moniteur a besoin d’une ressource
détenue ou d’une action accomplie par un autre en attente
du moniteur.
 Pour éviter des situations d’interblocage, il faut trouver un
moyen permettant à un processus actif à l’intérieur d’un
moniteur de se suspendre pour laisser place à un autre.

 Exemple : Producteur/consommateur
 Le consommateur est actif dans le moniteur et le tampon est vide
=> il devrait se mettre en attente et laisser place au producteur.

 Le producteur est actif dans le moniteur et le tampon est plein =>

il devrait se mettre en attente et laisser place au consommateur.
33
34
 On appelle variable condition, une var qui peut être
testée et
 endorme le thread qui la teste si la condition est fausse
 le réveille quand la condition devient vraie

35
 Une variable de condition est une variable manipulée au moyen de
deux opérations wait and signal (Attendre et signaler).

 wait(x) ([Link]) :
 suspendre l’exécution du processus (thread) appelant ( mise en attente de x);
 autoriser un autre processus en attente du moniteur à y entrer;
 signal(x) ([Link]) :
 débloquer un processus en attente de la condition x.
 Le processus débloqué est soit :
 mis dans la file d’attente des processus suspendus du moniteur (signal and
continue),
 activé dans le moniteur (signal and wait) => Le processus appelant est dans ce
cas mis en attente (Proposé par Hoare)

36
Dans une banque, il y a
une file principale, mais
une fois entré, on pourrait
vous faire attendre dans
un fauteuil dans une file
propre à un service
particulier.

37
 Les sections critiques du problème du producteur/consommateur sont les
opérations de dépôt et de retrait dans le tampon partagé.
 Un dépôt n’est possible que si le tampon n’est pas plein. Pour bloquer le
producteur tant que le buffer est plein, il suffit d’utiliser une variable de
condition nplein et de précéder chaque opération de dépôt par l’action
wait(nplein), si le tampon est plein.
 L’action signal(nplein) sera appelée suite à un retrait d’un buffer plein.

 Un retrait n’est possible que si le tampon n’est pas vide. Pour bloquer le
consommateur tant que le buffer est vide, il suffit d’utiliser une variable de
condition nvide et de précéder chaque opération de retrait par l’action
wait(nvide), si le tampon est vide.
 L’action signal(nvide) sera appelée par l’opération de dépôt dans le cas d’un
dépôt dans un buffer vide.

38
39
 Une file d’attente pour mémoriser les demandes
d’accès au moniteur (file d’attente du moniteur).

 Une file d’attente pour chaque variable de

condition (wait(x)).

 Éventuellement, une file d’attente des processus

suspendus dans le moniteur suite à l’opération
signal(x)

 Si cette dernière file est gérée, elle est plus

prioritaire que la file d’attente du moniteur. 40
2
1

41
 Pour contrôler les accès à un objet partagé, E. W.
Dijkstra (1965) suggéra l’emploi d’un nouveau type
de variables appelées sémaphores.
 Un sémaphore S est constitué d’un compteur à
valeurs entières val(S) et d’une file d’attente f(S)
 A l’initialisation:

Val(S)= i(s) >=0 (valeur initiale du sémaphore)

f(S) est vide

42
 Les sémaphores sont manipulés au moyen de deux
primitives exécutées en exclusion mutuelle:
- P (désigné aussi par down ou wait) et
- V (désigné aussi par up ou signal).

Processus bloqués Processus non bloqués

0 Val (S)

Le processus q qui exécute P(S) est bloqué si val(S)<0

(f(S) q)
V(S) réveille un processus de la file d’attente si elle n’est pas
vide. (P f(S) ) 43
P(S) V(S)
Début Début
Val(S):= Val(S)-1; Val(S):= Val(S)+1;
Si Val(S)<0 alors Si Val(S)<=0 alors
etat[processus]:=‘bloqué’; retirer (processus, f(S));
Insérer (processus, f(S)); etat[processus]:=‘actif’;
Fin Si Fin Si
Fin Fin

Primitives indivisibles

44
45
 Problème :
 Le masquage des interruptions n’assure pas l’exclusion
mutuelle dans un système multiprocesseur.
 Solution :
 Utilisation de l’instruction Test and Set Lock.

46
47
 Remarques :
 Le masquage des interruptions est utilisé ici pour
éviter le problème de boucle infinie (ordonnanceur
à priorité).
 Supposons que S->t = 0 et deux processus P1 et P2
tels que P2 est plus prioritaire que P1 ;
- P1 exécute : TSL(S->t) S->t devient égal à 1
- Interruption de l’exécution de P1 au profit de P2
- P2 rentre dans la boucle while(TSL(S->t) ! =0);
 Une autre solution au problème est l’héritage de
priorité.
48
 Les sémaphores permettent d’assurer l’exclusion mutuelle:

49
50
 Soit S un sémaphore. On distingue par:
i(S) : la valeur initiale
n.P(S) : le nombre total d’exécution de P(S)
n.V(S) : le nombre total d’exécution de V(S)
Val (S)= i(S)+n. V(S)- n. P(S) (1)
Soit [Link](S) le nombre de processus bloqués dans f(S).
Si val(S)≥0 Alors [Link](S)=0
Sinon [Link](S)= -Val(S)
Fin Si
[Link](S)= Max(0,-val(S)) (2)
51
 Soit n.f(s) le nombre de procs. qui ont franchi P(S):
Sans être bloqués
Ou bloqués puis débloqués
n.f(S)=n.P(S)-[Link](S) [Link](S)=n.p(S)-n.f(S) (2’)

En ramplaçant (2’)dans (2):

Max(0,-val(S))= n.P(S)-n.f(S)
-n.f(S)= Max(-n.P(S),-Val(S)-n.P(S))
n.f(S)= Min(n.P(S),Val(S)+n.P(S)) (2’’)

En remplaçant (1) dans (2’’):

n.f(S)= Min(n.P(S), i(S)+n.V(S)) (3) 52
Soit nc le nombre de procs. en section critique
nc=n.f(S)- n.V(S) (4) (n.V(S) est le nombre de procs
qui ont quitté la section critique)
D’après (3): n.f(S)= Min(n.P(S),1+n.V(S)) (5)
n.f(S)≤1+n.V(S) n.f(S)-n.V(S)≤1 nc≤1
53
 Si aucun proc. n’est en S.C et si plusieurs procs. sont
bloqués à l’entrée de leur S.C, alors il faut permettre à l’un
d’eux d’ y entrer.
Soit nc=0.D’après (4), nc=n.f(S)-n.V(S)
n.f(S)=n.V(S) n.f(S)<n.V(S)+1
D’après (5) n.f(S)= Min(n.P(S),1+n.V(S))
n.f(S)=n.P(S)
D’après (2’), [Link](S)= n.P(S)-n.f(S)=0
Aucun processus n’est bloqué
54
55
56
 Ecrire un programme qui crée deux threads qui
agissent sur une variable globale; l’un effectue sa
décrémentation et l’autre son incrémentation. Les
deux opération doivent s’inscrire dans un fragment
de code indivisible pour assurer l’accès exclusif à la
variable globale.

57
58
59
 Ecrire un programme semaphore_exemple.c qui
crée plusieurs threads qui accèdent simultanément
à une ressource partagée, en utilisant un
sémaphore pour limiter le nombre de threads
pouvant accéder à cette ressource en même
temps.

60
61
62
63
 Ecrire un programme qui crée deux thread
concurents dont chacun reçoit un numéro propore
à lui et qui executent un code atomique. Ce code
permet à chaque processus d’afficher son numero
suivi du nombre de fois qu’il fait l’affichage (quatre
fois sans aucune interruption).

64
 Chaque tread
affiche son
identifiant 4 fois

n: nombre de
threads comme 0
argument

65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
[0,4])

88
89
90
91
92
93
94
95
96
red-lec.c

97
98
 Un sémaphore binaire mutex, initialisé à 1, pour
assurer l’accès en exclusion mutuelle au moniteur.
 File du mutex = File d’attente du moniteur

 Pour chaque variable de condition x du moniteur,

 un sémaphore binaire x-sem initialisé à 0,
▪ File de x-sem = File d’attente de x
 un compteur du nombre de processus en attente de x.

99
100
 Nombre de
processus en
file d attente

101
102
 Un sémaphore binaire mutex, initialisé à 1, pour assurer l’accès en
exclusion mutuelle au moniteur.
File du mutex = File d’attente du moniteur

 Pour chaque variable de condition x du moniteur,

 un sémaphore binaire x-sem initialisé à 0,
File de x-sem = File d’attente de x
 un compteur du nombre de processus en attente de x.

 Un sémaphore next, initialisé à 0, pour mémoriser tous les

processus qui ont cédé le moniteur à un autre processus (signal
and wait).
File de next = File d’attente des processus suspendus

Un compteur du nombre de processus suspendus à l’intérieur du

moniteur next_count.
103
104
105
106