Module 5 - Synchronisation de Processus

(ou threads, ou fils ou tâches)

Chapitre 6 (Silberchatz)

Module 5 1
 Problèmes avec concurrence = parallélisme

Les threads concurrents doivent parfois partager
des données (fichiers ou mémoire commune) et
des ressources
 On parle donc de tâches coopératives

Si l’accès n’est pas contrôlé, le résultat de
l’exécution du programme peut dépendre de
l’ordre d’entrelacement de l’exécution des
instructions (non-déterministe).

Un programme peut fournir différents résultats à
partir d’une exécution qui peuvent être parfois
indésirables.

Module 5 2
 Exemple

Deux threads exécutent X demande une

cette même procédure et réservation
partagent la même base de d’avion
données

Ils peuvent être Base de données
interrompus n’importe dit que le
quand fauteuil A est

Le résultat de l ’exécution disponible
concurrente de P1 et P2
dépend de l’ordre de leur Fauteuil A est
entrelacement assigné à X et
marqué occupé

Module 5 3
 Vue globale d’une exécution possible
P1 P2
Interruption
M. Leblanc demande une ou retard
réservation d’avion
M. Guy demande une
réservation d’avion

Base de données dit

que fauteuil 30A est
disponible Base de données dit
que fauteuil 30A est
disponible

Fauteuil 30A est Fauteuil 30A est

assigné à Leblanc et assigné à Guy et
marqué occupé marqué occupé

Module 5 4
 Deux opérations en parallèle sur une variable a
partagée (b est privé à chaque processus)
P1 interruption P2
b=a
b=a
b++
a=b
b++
a=b
Supposons que a soit 0 au début
P1 travaille sur le plus vieux a donc le résultat final sera a=1.
Sera a=2 si les deux tâches sont exécutées l’une après l’autre
Si a était sauvegardé quand P1 est interrompu, il ne pourrait pas être partagé avec P2 (il y aurait deux
a tandis que nous en voulons une seule)
Module 5 5
 3ème exemple
Thread P1 Thread P2

static char a; static char a;

void echo() void echo()

{ {
cin >> a;
cin >> a;
cout << a;
}
cout << a;
}
Si la var a est partagée, le premier a est effacé/remplacé
Si elle est privée, l’ordre d’affichage est renversé
Module 5 6
 Autres exemples

Des threads qui travaillent en simultanément sur

une matrice, un pour la mettre à jour et l`autre
pour en extraire des statistiques

Problème qui affecte le programme du tampon

borné, v. manuel

Quand plusieurs threads exécutent en parallèle, nous ne

pouvons pas faire d’hypothèse sur la vitesse d’exécution
des threads, ni leur entrelacement
 Peuvent être différents à chaque exécution du programme

Module 5 7
 Section Critique

Partie d’un programme dont l’exécution ne

doit pas être entrelacé avec autres
programmes

Une fois qu’une tâche y entre, il faut lui permettre

de terminer cette section sans permettre aux
autres tâches de jouer sur les mêmes données

Module 5 8
 Le problème de la section critique

Lorsqu’un thread manipule une donnée (ou ressource)
partagée, nous disons qu’il se trouve dans une section
critique (SC) (associée à cette donnée)

Le problème de la section critique est de trouver un
algorithme d`exclusion mutuelle de threads dans l’exécution
de leur SCs afin que le résultat de leurs actions ne
dépendent pas de l’ordre d’entrelacement de leur exécution
(avec un ou plusieurs processeurs)

L’exécution des sections critiques doit être mutuellement
exclusive: à tout instant, un seul thread peut exécuter une
SC pour une variable donnée (même lorsqu’il y a plusieurs
processeurs)

Ceci peut être obtenu en plaçant des instructions spéciales
dans les sections d`entrée et sortie

Pour simplifier les choses, assumons qu’il n’y a qu’une
seule SC dans un programme.

Module 5 9
 Structure du programme

Chaque thread doit donc demander une permission avant
d’entrer dans une section critique (SC)

La section de code qui effectue cette requête est la section
d’entrée

La section critique est normalement suivie d’une section de
sortie

Le code qui reste est la section restante (SR): non-critique

repeat
section d’entrée
section critique
section de sortie
section restante
forever

Module 5 10
 Application

X demande une
réservation d’avion

Section d’entrée

Base de données dit que

fauteuil A est disponible
Section
critique Fauteuil A est assigné à X et
marqué occupé

Section de sortie

Module 5 11
 Critères nécessaires pour solutions valides

Exclusion Mutuelle:
 À tout instant, au plus un thread peut être dans une
section critique (SC) pour une variable donnée

Progrès:
 absence d’interblocage (Chap 7)
 si un thread demande d`entrer dans une section critique
à un moment où aucun autre thread en fait requête, il
doit être en mesure d’y entrer
 Non interférence:
 Si un thread s’arrête dans sa section restante, ceci ne doit
pas affecter les autres threads
 Mais on fait l’hypothèse qu’un thread qui entre dans une
section critique, en sortira.

Attente limitée (bounded waiting):
 Aucun thread n’est empêché éternellement d’atteindre
sa SC (pas de famine)

Module 5 12
 Types de solutions

Solutions par logiciel
 des algorithmes dont la validité ne s’appuie pas sur
l’existence d’instruction spéciales

Solutions fournies par le matériel
 s’appuient sur l’existence de certaines instructions (du
processeur) spéciales

Solutions fournies pas le SE
 procure certains appels du système au programmeur

Toutes les solutions se basent sur l’atomicité de l’accès à la
mémoire centrale: une adresse de mémoire ne peut être
affectée que par une instruction à la fois, donc par un thread
à la fois.

Plus en général, toutes les solutions se basent sur
l’existence d’instructions atomiques, qui fonctionnent
comme des SCs de base

Atomicité = indivisibilité
Module 5 13
 Solutions par logiciel
(pas pratiques, mais intéressantes pour comprendre le problème)

Considérons d’abord 2 threads

 Algorithmes 1 et 2 ne sont pas valides
 Montrent la difficulté du problème
 Algorithme 3 est valide (algorithme de Peterson)

Notation
 Débutons avec 2 threads: T0 et T1
 Lorsque nous discutons de la tâche Ti, Tj dénotera
toujours une autre tâche différente (i != j)

Module 5 14
 Algorithme 1: threads se donnent mutuellement le tour

La variable partagée turn est
initialisée à 0 ou 1

La SC de Ti est exécutée si
turn = i

Ti est occupé à attendre si Tj Thread Ti:
est dans SC.

Fonctionne pour l’exclusion
repeat
mutuelle! while(turn!=i){};

Pas de famine (seulement 1 SC
thread à son tour selon
turn). turn = j;

Mais le critère de progrès SR Rien
n’est pas satisfait car forever
l’exécution des SCs doit faire
strictement alterner

Ex 1: T0 possède une longue SR et T1 possède une courte SR. Si turn==0, T0 entre

dans sa SC et puis sa SR (turn==1). T1 entre dans sa SC et puis sa SR (turn==0), et
tente d’entrer dans sa SC: refusée! il doit attendre que T0 lui donne le tour.

Module 5 15
 initialisation de turn à 0 ou 1

Thread T0: Thread T1:

repeat repeat

while(turn!=0){}; while(turn!=1){};
SC SC
turn = 1; turn = 0;
SR SR
forever forever

Algorithme 1 vue globale

Ex 2: Généralisation à n threads: chaque fois, avant qu’un thread puisse entrer dans sa
section critique, il lui faut attendre que tous les autres aient eu cette chance!

Module 5 16
 Algorithme 2 ou l’excès de courtoisie...

Une variable Booléenne par

Thread: flag[0] et flag[1]

Ti signale qu’il désire exécuter
sa SC par: flag[i] =vrai
Thread Ti:

Mais il n’entre pas si l’autre repeat
est aussi intéressé! flag[i] = vrai;

Exclusion mutuelle ok

Progrés ok while(flag[j]==vrai){};

Absence de famine pas SC
satisfait:
flag[i] = faux;

Considérez la séquence:
SR
 T0: flag[0] = vrai forever rien faire
 T1: flag[1] = vrai
 Chaque thread attendra
indéfiniment pour exécuter
sa SC: on a une famine
Module 5 17
 Après vous, Après vous,
monsieur monsieur
Thread T0: Thread T1:
repeat repeat
flag[0] = vrai; flag[1] = vrai;
while(flag[1]==vrai){}; while(flag[0]==vrai){};
SC SC
flag[0] = faux; flag[1] = faux;
SR SR
forever forever

Algorithme 2 vue globale

T0: flag[0] = vrai

T1: flag[1] = vrai
interblocage!

Module 5 18
 Algorithme 3 (dit de Peterson): bon!

combine les deux idées: flag[i]=intention d’entrer; turn=à qui le tour

Initialisation: Thread Ti:

 flag[0] = flag[1] = faux repeat
 turn = i ou j flag[i] = vrai;
// je veux entrer

Désire d’exécuter SC est turn = j;
indiqué par flag[i] = vrai // je donne une chance à l’autre

flag[i] = faux à la section de do while
sortie (flag[j]==vrai && turn==j){};
SC
flag[i] = faux;
SR
forever

Module 5 19
 Entrer ou attendre?

Thread Ti attend si:

 Tj veut entrer est c’est la chance de Tj
 flag[j]==vrai et turn==j

Un thread Ti entre si:

 Tj ne veut pas entrer ou c’est la chance de Ti
 flag[j]==faux ou turn==i

Pour entrer, un thread dépend de la bonne volonté

de l’autre qu’il lui donne la chance!

Module 5 20
Thread T0: Thread T1:
repeat repeat
flag[0] = vrai; flag[1] = vrai;
// T0 veut entrer // T1 veut entrer
turn = 1; turn = 0;
// T0 donne une chance à T1 // T1 donne une chance à 0
while while
(flag[1]==vrai&&turn=1){}; (flag[0]==vrai&&turn=0){};
SC SC
flag[0] = faux; flag[1] = faux;
// T0 ne veut plus entrer // T1 ne veut plus entrer
SR SR
forever forever

Algorithme de Peterson vue globale

Module 5 21
 Scénario pour le changement de contrôle
Thread T0: Thread T1:
… …
SC flag[1] = vrai;
flag[0] = faux; // T1 veut entrer
// T0 ne veut plus entrer turn = 0;
SR // T1 donne une chance à T0
while
… (flag[0]==vrai&&turn=0){};
//test faux, entre
…
T1 prend la relève, donne une chance à T0 mais T0 a dit
qu’il ne veut pas entrer.
T1 entre donc dans la SC
Module 5 22
 Autre scénario de changement de contrôle
Thread T0: Thread T1:

SC
flag[0] = faux;
// T0 ne veut plus entrer flag[1] = vrai;
SR // T1 veut entrer
flag[0] = vrai; turn = 0;
// T0 veut entrer // T1 donne une chance à T0
turn = 1; // mais T0 annule cette action
// T0 donne une chance à T1
while while
(flag[1]==vrai&&turn=1){}; (flag[0]==vrai&&turn=0){};
// test vrai, n’entre pas //test faux, entre

T0 veut rentrer mais est obligé de donner une chance à T1, qui entre

Module 5 23
 Mais avec un petit décalage, c’est encore T0!
Thread T0:
Thread T1:
SC
flag[0] = faux;
// 0 ne veut plus entrer
RS
flag[0] = vrai;
// 0 veut entrer
flag[1] = vrai;
turn = 1;
// 1 veut entrer
// 0 donne une chance à 1
// mais T1 annule cette action
turn = 0;
// 1 donne une chance à 0
while while
(flag[1]==vrai&&turn=1){}; (flag[0]==vrai&&turn=0){};
// test faux, entre // test vrai, n’entre pas
Si T0 et T1 tentent simultanément d’entrer dans SC, seule une valeur de turn
survivra:
Module 5 non-déterministe (on ne sait pas qui gagnera), mais l’exclusion fonctionne 24
 Donc cet algorithme n’oblige pas une tâche
d’attendre d’autres qui pourraient ne pas avoir besoin de la SC
Supposons que T0 soit le seul à avoir besoin de la SC, ou que T1 soit
lent à agir: T0 peut rentrer de suite (flag[1]==faux la dernière fois que T1
est sorti)
flag[0] = vrai // prend l’initiative

turn = 1 // donne une chance à l’autre

while flag[1]==vrai && turn=1 {} //test faux, entre

SC

flag[0] = faux // donne une chance à l’autre

Cette propriété est désirable

Module 5 25
 Algorithme 3: preuve de validité

Exclusion mutuelle est assurée car:

 T0 et T1 ne peuvent être tous deux dans SC
seulement si turn est simultanément égal à 0 et 1
(ce qui est impossible)

Démontrons que progrès et attente limitée

sont satisfaits:
 Ti ne peut pas entrer dans SC seulement si en
attente dans la boucle while() avec condition:
flag[ j] == vrai et turn = j.
 Si Tj ne veut pas entrer dans SC alors flag[ j] =
faux et Ti peut alors entrer dans SC
Module 5 26
 Algorithme 3: preuve de validité (cont.)
 Si Tj a effectué flag[ j]=vrai et se trouve dans le
while(), alors turn==i ou turn==j
 Si
 turn==i, alors Ti entre dans SC.
 turn==j alors Tj entre dans SC mais il mettra
flag[ j] =false à la sortie: permettant à Ti d’entrer
dans SC
 mais si Tj a le temps de faire flag[ j]=true, il
devra aussi faire turn=i
 Puisque Ti ne peut modifier turn dans le
while(), Ti entrera dans SC après au plus une
entrée dans SC par Tj (attente limitée)

Module 5 27
 A propos d’échecs des threads

La solution qui satisfait les 3 critères (EM, progrès

et attente limitée), procure une robustesse face à
l’échec d’un thread dans sa section restante (SR)
 un thread qui échoue dans sa SR est équivalent à
un thread ayant une SR infiniment longue...

Par contre, aucune solution valide ne procure pas
de robustesse face à l'échec d’un thread dans sa
section critique (SC)
 un thread Ti qui échoue dans sa SC n’envoie pas
de signal aux autres threads: donc pour eux Ti est
encore dans sa SC...

Module 5 28
 Extension à >2 threads

L ’algorithme de Peterson peut être

généralisé à plus de 2 threads

Mais dans ce cas il existe des algorithmes
plus élégants, comme l’algorithme du
boulanger, basée sur l’idée de ‘prendre un
numéro’...
 Pas le temps d’en parler…

Module 5 29
 Une leçon à retenir…

À fin que des threads avec des variables
partagées puissent réussir, il est
nécessaire que tous les threads impliqués
utilisent le même algorithme de
coordination
 Un protocole commun

Module 5 30
 Critique des solutions par logiciel

Difficiles à programmer! Et à comprendre!
 Les solutions que nous verrons dorénavant sont toutes
basées sur l’existence d’instructions spécialisées, qui
facilitent le travail.

Les threads qui requièrent l’entrée dans leur SC

sont occupés à attendre (busy waiting);
consommant ainsi du temps de processeur
 Pour de longues sections critiques, il serait préférable
de bloquer les threads qui doivent attendre...

Module 5 31
 Solutions matérielles: désactivation des
interruptions

Sur un monoprocesseur:
l’exclusion mutuelle est
préservée mais l’efficacité se
détériore: Lorsqu’un Process Pi:
processus est dans sa SC il repeat
est impossible d’entrelacer
l’exécution d’autres inhiber interrupt
processus dans leur SR section critique

Perte d’interruptions rétablir interrupt

Dans un multiprocesseur: section restante
l’exclusion mutuelle n’est forever
pas garantie (long délais et
différentes horloges)

Une solution qui n’est
généralement pas acceptable

Module 5 32
 Solutions matérielles: Instructions spécialisées

Normal: pendant qu’un thread ou processus

accède une adresse de mémoire, aucun autre ne
peut accéder cette adresse en même temps

Extension: instructions de machine exécutant
plusieurs actions (ex: lecture et écriture) sur la
même location de mémoire de manière atomique
(indivisible)

Une instruction atomique ne peut être exécutée
que par un thread/processus à la fois (même en
présence de plusieurs processeurs)

Module 5 33
 L’instruction test-and-set

Un algorithme utilisant

Une version C++ de testset pour l’exclusion
test-and-set: Mutuelle:

La variable partagée b
bool testset(int& i) est initialisée à 0
{
Le 1er Ti/Pi qui met b à 1
if (i==0) { qui entre dans SC
i=1;
Tâche Ti/Pi:
return true; while testset(b)==false {};
} else { SC //entre quand vrai
return false; b=0;
} SR
}

Instruction atomique!
Module 5 34
 L’instruction test-and-set (cont.)

L’exclusion mutuelle est assurée: si Ti entre

dans SC, l’autre Tj est occupé à attendre
 Problème: utilise encore occupé à attendre

Peut procurer facilement l’exclusion mutuelle
mais nécessite des algorithmes plus
complexes pour satisfaire les autres
exigences du problème de la section critique

Lorsque Ti sort de sa SC, la sélection du
prochain Tj qui entrera dans SC est arbitraire:
pas de limite d’attente et donc possibilité de
famine

Module 5 35
 L’instruction ‘Échange’

Certains UCTs (ex: Pentium) offrent une
instruction xchg(a,b) qui interchange
atomiquement le contenue de a et b.

Mais xchg(a,b) souffre des même lacunes que
test-and-set

Module 5 36
 Utilisation de xchg pour l’exclusion mutuelle
(Stallings)

La variable partagée b est usage:

initialisée à 0

Chaque Ti possède une Thread Ti:
variable locale k repeat

Le Ti pouvant entrer dans k = 1
sa SC est celui qui trouve while(k!=0) xchg(k,b);
b=0
SC

Ce Ti exclue tous les xchg(k,b);
autres en attribuant b à 1
SR
 Quand la SC est occupée,
k et b seront à 1 pour forever
toutes taches cherchant à
entrer dans leur SC
 Mais k est 0 pour le thread
qui est dans la SC
Module 5 37
 Solutions basées sur des instructions fournies
par le SE (appels du système)

Les solutions vues jusqu’à présent sont
difficiles à programmer et mal codées.

On a besoin de méthodes qui nous évitent
les erreurs communes, comme la famine,
l’impasse, etc.
 Besoin d’instructions à plus haut niveau

Les méthodes que nous verrons
dorénavant utilisent des instructions
puissantes, qui sont réalisées par des
appels de SE (system calls)

Module 5 38
 Sémaphores

Un sémaphore S est un entier qui, sauf durant l’initialisation,
est accessible seulement par ces 2 opérations atomiques et
mutuellement exclusives:
 wait(S)
 signal(S)

Il est partagé entre tous les processus qui s`intéressent

à la même section critique

Les sémaphores seront catégorisés en deux types:
 Les sémaphores qui sont occupés à attendre (busy waiting)
 Les sémaphores qui utilisent des files d ’attente

On distingue aussi les sémaphores compteurs et les
sémaphores binaires, ces derniers sont moins puissants (v.
livre).

Module 5 39
 Spinlocks d’Unix: Sémaphores occupés à attendre
(busy waiting)

La façon la plus simple

d’implanter les sémaphores. wait(S):

Utiles pour des situations où while S<=0 {};
l’attente est brève, où il y a S--;
beaucoup d’UCTs

S est un entier initialisé à une
Attend si le nb de threads qui
valeur positive, de façon qu’un
premier thread puisse entrer peuvent entrer = 0 ou négatif
dans la SC

Quand S>0, jusqu’à n threads
peuvent entrer

Quand S<=0, il faut attendre S+1 signal(S):
signals (d’autres threads) pour S++;
entrer

Augmente de 1 le nb des threads qui

peuvent entrer
Module 5 40
 Atomicité
Wait: La séquence test-
décrément est atomique,
mais pas la boucle!
V
Signal est atomique. S <= 0
F
Rappel: les sections atomiques ne
peuvent pas être exécutées atomique S--
simultanément par différent threads

(ceci peut être obtenu en utilisant un des

mécanismes précédents) SC

Module 5 41
 Atomicité et interruptibilité SC

interruptible S++ autre thr.

V
S <= 0
F

atomique S--

SC
La boucle n’est pas atomique pour permettre à un autre thread
d’interrompre l’attente sortant de la SC
Module 5 42
 Utilisation des sémaphores pour les sections
critiques

Pour n threads
Thread Ti:

Initialiser S à 1
repeat
 Alors 1 seul thread peut wait(S);
être dans sa SC
SC

Pour permettre à k signal(S);
threads d’entrer dans leur SR
SC, initialiser S à k forever

Module 5 43
 Initialise S à >=1

Thread T1: Thread T2:

repeat repeat
wait(S); wait(S);
SC SC
signal(S); signal(S);
SR SR
forever forever

Semaphores: vue globale

Peut être facilement généralisé à plusieurs threads

Module 5 44
 Utilisation des sémaphores pour la
synchronisation de threads

On a 2 threads: T1 et
Synchronisation
T2 correcte lorsque T1/P1

La commande S1 dans contient:
T1 doit être exécuté S1;
avant celle de S2 dans signal(S);
T2

Définissons un
et que T2/P2 contient:
sémaphore S wait(S);

Initialisons S à 0 S2;

Module 5 45
 Interblocage et famine avec les sémaphores

Famine: un thread peut ne jamais arriver à
exécuter s’il ne teste jamais le sémaphore
au bon moment

Inter-blocage: Supposons S et Q initialisés
à1

T0 T1
wait(S)
wait(Q)

wait(Q) wait(S)
Module 5 46
 wait(S):
Sémaphores: observations while S<=0 {};
S--;

Quand S >= 0:
 Le nombre de threads qui peuvent exécuter wait(S)
sans devenir bloqués = S
 S threads peuvent entrer dans la SC
 plus puissant que certains mécanismes déjà vus
 dans les solutions où S peut être >1 il faudra avoir un 2ème sém.
pour les faire entrer un à la fois (exclusion mutuelle ou mutex)

Quand S est > 1, le thread qui entre le premier
dans la SC est le premier à tester S (choix
aléatoire)
 ceci n’est plus vrai dans la solution suivante

Quand S < 0: le nombre de threads qui attendent
sur S est = |S| - Ne s’applique pas pour
sémaphores occupés à attendre

Module 5 47
 Comment éviter l’attente occupée et le choix
aléatoire dans les sémaphores

Quand un thread doit attendre qu’un sémaphore
soit plus grand que 0, il est mis dans une file
d’attente de threads qui postulent sur le même
sémaphore.

Les files peuvent être PAPS (FIFO), avec priorités,
etc. Le SE contrôle l’ordre dans lequel les threads
sont choisis de la queue.

wait et signal deviennet donc des appels de
système comme les appels à des opérations
d’E/S.

Il y a une file d’attente pour chaque sémaphore
comme il y a une file d’attente pour chaque unité
d’E/S.
Module 5 48
 Sémaphores sans attente occupée

Un sémaphore S devient une structure de données:
 Une valeur (S.V)
 Une liste d’attente L (S.L)

Un thread devant attendre un sémaphore S, est bloqué et
ajouté dans la file d’attente S.L du sémaphore (v. état bloqué =
attente chap 3).

signal(S) enlève (selon une politique choisie, ex: PAPS/FIFO)

un thread de S.L et le place sur la liste des threads
prêts/ready.

Module 5 49
 Implementation
(les boîtes réprésentent des séquences non-interruptibles)

wait(S): [Link] --;

if [Link] < 0 { // SC occupée

add this thread to S.L;

block // thread mis en état attente (wait)
}

signal(S): [Link] ++;

if [Link] ≤ 0 { // des threads attendent

remove a process P from S.L;

wakeup(P) // thread choisi devient prêt
}

[Link] doit être initialisé à une valeur non-

négative (dépendant de l’application, v. exemples)
Module 5 50
 Wait et signal contiennent sont aussi des SC!

Les opérations wait et signal doivent être

exécutées atomiquement (un seul thread à la fois)

Dans un système à 1 seule UCT, on peut
neutraliser les interruptions et les opérations sont
courtes (moins de 10 instructions)

Normalement, nous devons utiliser un des
mécanismes déjà vus (instructions spéciales,
algorithme de Peterson, etc.)

L’attente occupée dans ce cas ne sera pas trop
couteuse car wait et signal sont brefs

Module 5 51
 Problèmes classiques de synchronisation

Tampon borné (producteur-consommateur)

Rédacteurs - Lecteurs

Les philosophes mangeant

Module 5 52
 Le problème du producteur - consommateur

Un problème classique dans l ’étude des

threads communicants
 un thread producteur produit des données
([Link] enregistrements d’un fichier) pour un
thread consommateur

Module 5 53
 Tampons de communication

Prod Prod

1 donn 1 donn 1 donn 1 donn

Cons Cons

Si le tampon est de longueur 1, le producteur et consommateur

doivent forcement aller à la même vitesse
Des tampons de plus grandes longueur permettent une certaine
indépendance. [Link]. à droite le consommateur a été plus lent
Module 5 54
 Le tampon borné (bounded buffer)
une structure de données fondamentale dans les SE

in: 1ère
b[0] b[1] pos. libre b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7]
b[7] b[2]

b[6] b[3] ou
in: 1ère out: 1ère
b[5] b[4] pos. libre pos.
pleine
out: 1ère bleu: plein, blanc: libre
pos. pleine

Le tampon borné se trouve dans la mémoire partagée entre

consommateur et usager

Module 5 55
 Pb de sync entre threads pour le tampon borné

Étant donné que le producteur et le

consommateur sont des threads
indépendants, des problèmes peuvent se
produire dans le cas d’accès simultané du
tampon

Les sémaphores peuvent résoudre ce
problème

Module 5 56
 Sémaphores: rappel.

Soit S un sémaphore sur une SC
 il est associé à une file d’attente
 S positif: S threads peuvent entrer dans SC
 S zéro: aucun thread ne peut entrer, pas de thread en attente
 S négatif: |S| thread dans file d ’attente

Wait(S): S - -
 si après S >= 0, thread peut entrer dans SC
 si S < 0, thread est mis dans file d ’attente

Signal(S): S++
 si après S<= 0, il y avait des threads en attente, et un thread
est réveillé

Indivisibilité = atomicité de ces opérations

Module 5 57
 Solution avec sémaphores

Un sémaphore S pour l’exclusion mutuelle
de l’accès du tampon
 Les sémaphores suivants ne font pas l’EM

Un sémaphore N pour synchroniser le
producteur et consommateur avec le
nombre d’éléments consommables dans le
tampon

Un sémaphore E pour synchroniser le
producteur et consommateur avec le
nombre d’espaces libres

Module 5 58
 Solution de P/C: tampon circulaire fini de dimension k

Initialization: [Link]=1; //excl. mut.

[Link]=0; //espaces pleins
[Link]=k; //espaces vides
append(v):
b[in]=v;
Producer: Consumer:
In++ mod k;
repeat repeat
produce v; wait(N);
wait(E); wait(S);
take():
wait(S); w=take();
w=b[out]; append(v); signal(S);
Out++ mod k; signal(S); signal(E);
return w; signal(N); consume(w);
forever forever

Module 5
Sections critiques 59
 Points importants à étudier

dégâts possibles en interchangeant les

instructions sur les sémaphores
 ou en changeant leur initialisation

Généralisation au cas de plusieurs

producteurs et consommateurs

Module 5 60
 Concepts importants de cette partie du Chap 6

Le problème de la section critique

L’entrelacement et l’atomicité

Problèmes de famine et interblocage

Solutions logiciel

Instructions matériel

Sémaphores occupés ou avec files

Fonctionnement des différentes solutions

L’exemple du tampon borné

Module 5 61
 Quelques exemples

Problèmes classiques de synchronisation

Lecteurs - Rédacteurs

Les philosophes mangeant

Moniteurs

Module 5 62
 Sémaphores: rappel
(les boîtes réprésentent des séquences non-interruptibles)

wait(S): [Link] --;

if [Link] < 0 { // SC occupée

ajouter ce thread à S.L;

block // thread mis en état attente (wait)

signal(S): [Link] ++;

if [Link] ≤ 0 { // des threads attendent

enlever un thread P de S.L;

wakeup(P) // thread choisi devient prêt
}

[Link] doit être initialisé à une valeur non-négative

dépendant de l’application, v. exemples
Module 5 63
 Sémaphores: rappel.

Soit S un sémaphore sur une SC
 il est associé à une file d ’attente
 S positif: S thread peuvent entrer dans SC
 S zéro: aucun thread ne peut entrer, aucun thread en
attente
 S négatif: |S| thread dans file d ’attente

Wait(S): S - -
 si après S >= 0, thread peut entrer dans SC
 si S < 0, thread est mis dans file d ’attente

Signal(S): S++
 si après S<= 0, il y avait des threads en attente, et un
thread est transféré à la file prêt

Indivisibilité = atomicité de wait et signal

Module 5 64
 Problème des lecteurs - rédacteurs

Plusieurs threads peuvent accéder à une
base de données
 Pour y lire ou pour y écrire

Les rédacteurs doivent être synchronisés
entre eux et par rapport aux lecteurs
 il faut empêcher à un thread de lire pendant
l’écriture
 il faut empêcher à deux rédacteurs d ’écrire
simultanément

Les lecteurs peuvent y accéder
simultanément

Module 5 65
 Une solution (n’exclut pas la famine)

Variable readcount: nombre de threads lisant la base de
données

Sémaphore mutex: protège la SC où readcount est mis à
jour

Sémaphore wrt: exclusion mutuelle entre rédacteurs et
lecteurs

Les rédacteurs doivent attendre sur wrt
 les uns pour les autres
 et aussi la fin de toutes les lectures

Les lecteurs doivent
 attendre sur wrt quand il y a des rédacteurs qui écrivent
 bloquer les rédacteurs sur wrt quand il y a des lecteurs qui
lisent
 redémarrer les rédacteurs quand personne ne lit

Module 5 66
 Les données et les rédacteurs

Données: deux sémaphores et une variable

mutex, wrt: semaphore (init. 1);
readcount : integer (init. 0);

Rédacteur
wait(wrt);
. . .
// écriture
. . .
signal(wrt);

Module 5 67
 Les lecteurs
wait(mutex);
readcount ++ ;
if readcount == 1 then wait(wrt);
signal(mutex);
Le premier lecteur d ’un groupe pourrait
devoir attendre sur wrt, il doit aussi
bloquer les rédacteurs. Quand il sera
//SC: lecture entré, les suivants pourront entrer
librement

wait(mutex);
readcount -- ;
if readcount == 0 then signal(wrt);
signal(mutex):

Le dernier lecteur sortant doit permettre

l`accès aux rédacteurs
Module 5 68
 Observations

Le 1er lecteur qui entre dans la SC bloque

les rédacteurs (wait (wrt)), le dernier les
remet en marche (signal (wrt))

Si 1 rédacteur est dans la SC, 1 lecteur
attend sur wrt, les autres sur mutex

un signal(wrt) peut faire exécuter un
lecteur ou un rédacteur

Module 5 69
 Le problème des philosophes mangeant

5 philosophes qui
mangent et pensent

Pour manger il faut 2
fourchettes, droite et
gauche

On en a seulement 5!

Un problème classique
de synchronisation

Illustre la difficulté
d’allouer ressources aux
threads tout en évitant
interblocage et famine

Module 5 70
 Le problème des philosophes mangeant

Un thread par
philosophe

Un sémaphore par Thread Pi:
fourchette: repeat
 fork: array[0..4] of think;
semaphores wait(fork[i]);
wait(fork[i+1 mod 5]);
 Initialisation: fork[i ] =1
eat;
for i:=0..4
signal(fork[i+1 mod 5]);

Première tentative: signal(fork[i]);
 interblocage si chacun forever
débute en prenant sa
fourchette gauche!
 Wait(fork[i])

Module 5 71
 Le problème des philosophes mangeant

Une solution: admettre
seulement 4 philosophes
Thread Pi:
à la fois qui peuvent
repeat
tenter de manger
think;

Il y aura touj. au moins 1 wait(T);
philosophe qui pourra wait(fork[i]);
manger wait(fork[i+1 mod 5]);
 même si tous prennent eat;
1 fourchette signal(fork[i+1 mod 5]);

Ajout d’un sémaphore T signal(fork[i]);
qui limite à 4 le nombre signal(T);
de philosophes “assis à forever
la table”
 initial. de T à 4

Module 5 72
 Avantage des sémaphores
(par rapport aux solutions précédentes)

Une seule variable partagée par section
critique

deux seules opérations: wait, signal

contrôle plus localisé (que avec les précéds)

extension facile au cas de plus. threads

possibilité de faire entrer plus. threads à la
fois dans une section critique

gestion de files d`attente par le SE: famine
évitée si le SE est équitable ([Link]. files
FIFO)

Module 5 73
 Problème avec sémaphores: difficulté de programmation

wait et signal sont dispersés parmi

plusieurs threads, mais ils doivent se
correspondre
 V. programme du tampon borné

Utilisation doit être correcte dans tous les
threads

Un seul “mauvais” thread peut faire
échouer toute une collection de threads
([Link]. oublie de faire signal)

Considérez le cas d`un thread qui a des
waits et signals dans des boucles et des
Module 5
tests... 74
 Moniteurs: une autre solution

Constructions (en langage de haut-niveau)

qui procurent une fonctionnalité
équivalente aux sémaphores mais plus
facile à contrôler

Disponibles en:
 Concurrent Pascal, Modula-3...
• synchronized method en Java (moniteurs simplifiés)

Module 5 75
 Moniteur

Est un module contenant:

 une ou plusieurs procédures
 une séquence d’initialisation
 variables 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 exécuter dans le moniteur
à tout instant (mais plus. threads peuvent être en attente dans le
monit.)
Module 5 76
 Moniteur

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

Module 5 77
 Structure générale du moniteur (style Java)

monitor nom-de-moniteur
{ // déclarations de vars
public entry p1(. . .) {code de méthode p1}
public entry p2(. . .) {code de méthode p2}
. . .
}

La seule façon de manipuler les vars internes au moniteur est

d’appeler une des méthodes d’entrée

Module 5 78
 Moniteur: Vue schématique simplifiée style Java

Module 5 79
 Variables conditionnelles (n’existent pas en Java)

sont accessibles seulement dans le moniteur

accessibles et modifiables seulement à l’aide de 2
fonctions:
 x: wait bloque l’exécution du thread exécutant sur la
condition x
 le thread pourra reprendre l’exécution seulement si un
autre thread exécute x: signal)
 x: signal reprend l’exécution d’un thread bloqué sur la
condition x
 S’il en existe plusieurs: en choisir un (file?)
 S’il n’en existe pas: ne rien faire

Module 5 80
 Moniteur avec variables conditionnelles

Dans une banque, il y a une file

principale, mais une fois entré
on pourrait vous faire attendre
dans un fauteuil jusqu’à ce que
le préposé soit disponible
Module 5 81
 Blocage dans les moniteurs

threads attendent dans la file d’entrée ou dans
une file de condition (ils n ’exécutent pas)

sur [Link]: le thread est placé dans la file de la
condition (il n ’exécute pas)

[Link] amène dans le moniteur 1 thread de la
file x (si x vide, aucun effet)

Module 5 82
 Retour au problème des philosophes mangeant

5 philosophes qui
mangent et pensent

Pour manger il faut 2
baguettes, droite et
gauche

On en a seulement 5!

Un problème classique
de synchronisation

Illustre la difficulté
d’allouer ressources aux
threads tout en évitant
interblocage et famine

Module 5 83
 Philosophes mangeant structures de données

Chaque philos. a son propre state qui peut être
(thinking, hungry, eating)
 philosophe i peut faire state[i] = eating ssi les voisins ne
mangent pas

Chaque condition a sa propre condition self

 le philosophe i peut attendre sur self [ i ] si veut manger,
mais ne peut pas obtenir les 2 baguettes

Module 5 84
 Chaque philosophe exécute à jamais:

repeat
pickup
eat
putdown
forever

Module 5 85
 Un philosophe mange

private test(int i) {
if ( (state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
state[i] = EATING;
self[i].signal;
} Un philosophe mange si ses voisins ne mangent pas et s’il
a faim.
}
Une fois mangé, il signale de façon qu’un autre pickup
soit possible, si pickup s’était arrêté sur wait

Module 5 Il peut aussi sortir sans avoir mangé si le test est faux 86
 Chercher de prendre les baguettes

public entry pickUp(int i) {

state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
self[i].wait;
}

Phil. cherche à manger en testant, s’il sort de test

qu’il n’est pas mangeant il attend – un autre pickup
n’est pas possible avant un self[i] signal
Module 5 87
 Déposer les baguettes

public entry putDown(int i) {

state[i] = THINKING;
// tester les deux voisins

test((i + 4) % 5);
test((i + 1) % 5);
} Une fois fini de manger, un philosophe se
préoccupe de faire manger ses voisins en les
testant
Module 5 88
 Relation entre moniteurs et autre mécanismes

Les moniteurs sont implantés utilisant les

sémaphores ou les autres mécanismes
déjà vus

Il est aussi possible d`implanter les

sémaphores en utilisant les moniteurs!
 Voir le texte

Module 5 89
 Le problème de la SC en pratique...

Les systèmes réels rendent disponibles
plusieurs mécanismes qui peuvent être
utilisés pour obtenir la solution la plus
efficace dans différentes situations

Module 5 90
 Concepts importants du Chapitre 6

Sections critiques: pourquoi

Difficulté du problème de la synch sur SC
 Bonnes et mauvaises solutions

Accès atomique à la mémoire

Solutions logiciel `pures`

Solution matériel: test-and-set

Solutions par appels du système:
 Sémaphores, moniteurs, fonctionnement

Problèmes typiques: tampon borné,
lecteurs-écrivains, philosophes

Module 5 91