Chap. 7 1

Synchronisation de Processus Synchronisation de Processus (ou threads, ou fils ou tâches)(ou threads, ou fils ou tâches)

Chapitre 7Chapitre 7

http://w3.uqo.ca/luigi/http://w3.uqo.ca/luigi/

Chap. 7 2

Problèmes avec concurrence = parallélismeProblèmes avec concurrence = parallélisme

Les threads concurrents doivent parfois partager données (fichiers ou mémoire commune) et ressources On parle donc de threads coopérants

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

Un programme pourra donner des résultats différents et parfois indésirables de fois en fois

Chap. 7 3

Exemple 1Exemple 1

Deux threads exécutent cette même procédure et partagent la même base de données

Ils peuvent être interrompus n’importe où

Le résultat de l ’exécution concurrente de P1 et P2 dépend de l`ordre de leur entrelacement

M. X demande uneréservation d’avion

Base de données dit que fauteuil A est disponible

Fauteuil A est assigné à X et marqué occupé

Chap. 7 4

Vue globale d’une exécution possibleVue globale d’une exécution possible

M. Guy demande uneréservation d’avion

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

Fauteuil 30A est assigné à Guy et marqué occupé

M. Leblanc demande une réservation d’avion

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

Fauteuil 30A est assigné à Leblanc et marqué occupé

Interruptionou retard

P1 P2

Exécuter deux fois en parallèle le code suivant:

Quel pourrait être le résultat dans b?

Exemple 2Exemple 2

Chap. 7 5

b=ab++a=b

Hypothèse de partage de donnéesHypothèse de partage de données

Chap. 7 6

Partagées entre threads

Les données partagées ne sont pas souvegardées quand on change de thread

Chap. 7 7

b=a

b++a=b

b=ab++a=b

P1 P2

Supposons que a soit 0 au débutP1 travaille sur le 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

Cas pratique: a est un compteur d’accès dans une page web

interruption

Deux opérations en parallèle Deux opérations en parallèle var var a partagée a partagée entre threadentre thread

var var b est privéeb est privée à chaque thread à chaque thread

Chap. 7 8

3ème exemple3ème exemple

Thread P1

static char a;

void echo(){ cin >> a;

cout << a;}

Thread P2

static char a;

void echo(){ cin >> a; cout << a;}

Si la var a est partagée, le premier a est effacé Si elle est privée, l’ordre d’affichage est renversé

Asynchronie des threadsAsynchronie des threads

Quand plusieurs threads exécutent en parallèle, nous ne pouvons pas faire d’hypothèses sur la vitesse d’exécution des threads, ni leur entrelacement

Peuvent être différents à chaque exécution du programme

Chap. 7 9

Chap. 7 10

Autres exemplesAutres exemples

Des threads qui travaillent en simultanéité sur une matrice, par ex. un pour la mettre à jour, l`autre pour en extraire des statistiques

Problème qui affecte le programme du tampon borné, v. manuel

Chap. 7 11

Section CritiqueSection Critique

Partie d’un programme dont l’exécution ne doit pas entrelacer avec autres programmes Indivisibilité ou atomicité de la section

critique Une fois qu’un processus ou fil y entre, il faut lui

permettre de terminer cette section sans permettre à autres de jouer sur les mêmes données La section critique doit être verrouillée afin de devenir

atomique

Entrelacement de threads A et BEntrelacement de threads A et B

Chap. 7 12

A

A Contin.

A Contin.

B

B contin

Les flèches indiquent délais ou interruptionsBeaucoup de possibilités, selon les points où A et B sont interrompus

Atomicité de threads A et B par effet du verrouAtomicité de threads A et B par effet du verrou

Chap. 7 13

A

B A

B

OU

Seulement deux possibilités, quand chacun est exécuté sans interruptions

Section critiqueSection critique

Chap. 7 14

M. X demande uneréservation d’avion

Base de données dit que fauteuil A est disponible

Fauteuil A est assigné à X et marqué occupé

atomique

Chap. 7 15

Le problème de la section critiqueLe problème de la section critique

Lorsqu’un thread manipule une donnée (ou ressource) partagée avec autres, nous disons qu’il se trouve dans une section critique (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 CritSect 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 et atomique: à tout instant, un seul thread peut exécuter une CritSect pour une donnée (même lorsqu’il y a plusieurs UCT)

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

Chap. 7 16

Deux simplificationsDeux simplifications

Pour simplifier, parfois nous ferons l’hypothèse qu’il n’y a qu’une seule CritSect dans un thread

Et nous ne ferons plus distinction entre CritSect pour différentes données

Chap. 7 17

Structure d’un programme typeStructure d’un programme type Le programme est présenté comme boucle infinie: while(true) Chaque thread doit donc demander une permission avant

d’entrer dans une CritSect 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 (leave CritSect) Le code qui reste est la section non-critique

while (true) { enterCritSect CritSect leaveCritSect nonCritSect

}

atomique

Chap. 7 18

ApplicationApplication

M. X demande uneréservation d’avion enterCritSect

Base de données dit que fauteuil A est disponible

Fauteuil A est assigné à X et marqué occupé

leaveCritSect

Section critique

Chap. 7 19

Critères nécessaires pour solutions valides (*)Critères nécessaires pour solutions valides (*) Exclusion Mutuelle

En tout moment, au plus un thread peut être dans une CritSect Déroulement

Une CritSect ne sera donnée qu’à un thread qui attend d’y entrer

Chaque fois qu’une CritSect devient disponible, s’il y a des threads qui l’attendent, un d’eux doit être capable d’y entrer (pas d’interblocage)

Attente bornée (pas de famine) Un thread qui attend d’entrer dans une CritSect pourra enfin y

entrer = aucun thread ne peut être exclu à jamais de la CritSect à

cause d’autres threads qui la monopolisent

Notez la différence entre interblocage et famine

(*) Définitions plus compliquée dans le manuel, mais selon moi sans besoin

Chap. 7 20

Types de solutionsTypes de solutions

Solutions par logiciel des algorithmes qui n’utilisent pas 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 Sections Critiques de base

Chap. 7 21

Solutions par logicielSolutions par logiciel(pas pratiques, mais intéressantes pour comprendre le pb)(pas pratiques, mais intéressantes pour comprendre le pb)

Nous 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 sera toujours

l’autre tâche (i != j) while(X){A}: repète A tant que X est vrai

while(X): attend tant que X est vrai

Chap. 7 22

Idée de l’algorithme 1Idée de l’algorithme 1

Les threads se donnent mutuellement le tour T0T1T0T1…

Réalise l’exclusion mutuelle, mais viole le principe du déroulement: Une CritSect pourra être donnée à des

threads qui n’en ont pas besoin P.ex. après T0, T1 pourrait n’avoir pas besoin d’entrer

Chap. 7 23

Algorithme 1: Algorithme 1: threads se donnent mutuellement le tourthreads se donnent mutuellement le tour

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

La CritSect de Ti est exécutée ssi tour = i

Ti est actif à attendre si Tj est dans CritSect.

Fonctionne pour l’exclusion mutuelle!

Mais critère du déroulement pas satisfait car l’exécution des CritSect doit strictement alterner

Thread Ti:while(true){ while(tour!=i); CritSect tour = j; nonCritSect}

T0T1T0T1… même si l’un des deux n’est pas intéressé du tout

Rien faire

Chap. 7 24

Thread T0:While(true){ while(tour!=0); CritSect tour = 1; nonCritSect}

Thread T1:While(true){ while(tour!=1); CritSect tour = 0; nonCritSect}

Algorithme 1 vue globale

Initialisation de tour à 0 ou 1Rien faire

Chap. 7 25

Exemple: supposez que tour=0 au débutExemple: supposez que tour=0 au début

Thread T0: while(tour!=0);

// premier à entrer

CritSect tour = 1; nonCritSect while(tour!=0);

// entre quand T1 finit

CritSect tour = 1; nonCritSect

etc...

Thread T1:while(tour!=1);

// entre quand T0 finit CritSect tour = 0; nonCritSectwhile(tour!=1);

// entre quand T0 finit CritSect tour = 0; nonCritSect

etc...

Chap. 7 26

Généralisation à n threadsGénéralisation à n threads

Chaque fois, avant qu’un thread puisse rentrer dans la section critique, il lui faut attendre que tous les autres aient eu cette chance! En claire contradiction avec l’exigence de

déroulement Supposez le cas de 1 000 threads, dont

seulement quelques uns sont actifs

Algorithme 2Algorithme 2

L’algorithme 2 prend en compte la critique à l’algorithme 1: Donne la CritSect seulement aux threads qui la

veulent Cependant on ne peut pas permettre à un

processus de se redonner systématiquement la CritSec famine Faut que chaque processus qui veut entrer donne

une chance à des autres avant d’y entrer

Chap. 7 27

Chap. 7 28

Algorithme 2 Algorithme 2 ou l’excès de courtoisie...ou l’excès de courtoisie...

Une variable Booléenne par Thread: veut[0] et veut[1]

Ti signale qu’il désire exécuter sa CritSect par: veut[i] =vrai

Mais il n’entre pas si l’autre est aussi intéressé!

Exclusion mutuelle ok Déroulement pas satisfait: Considérez la séquence:

T0: veut[0] = vrai T1: veut[1] = vrai

Chaque thread attendra indéfiniment pour exécuter sa CritSect: interblocage

Thread Ti:while(true){ veut[i] = vrai; while(veut[j]); CritSect veut[i] = faux; nonCritSect}

                          

rien faire

Chap. 7 29

Thread T0:while(true){ veut[0] = vrai; while(veut[1]); CritSect veut[0] = faux; nonCritSect}

Thread T1:while(true){ veut[1] = vrai; while(veut[0]); CritSect veut[1] = faux; nonCritSect}

Algorithme 2 vue globale

T0: veut[0] = vraiT1: veut[1] = vraiinterblocage!

Après vous, monsieurAprès vous, monsieur

Chap. 7 30

Algorithme 3 Algorithme 3 (dit de Peterson)(dit de Peterson):: bon! bon!

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

Initialisation: veut[0] = veut[1] = faux tour = i ou j

Désir d’exécuter CritSect est indiqué par veut[i] = vrai

veut[i] = faux à la sortie

Thread Ti:while(true){ veut[i] = vrai; // je veux entrer

tour = j; // je donne une chance à l’autre

while (veut[j] && tour==j); CritSect veut[i] = faux; nonCritSect}

Chap. 7 31

Entrer ou attendre?Entrer ou attendre?

Thread Ti attend si: L’autre veut entrer est c’est la chance à lui

veut[j]==vrai et tour==j

Un thread Ti peut entrer si: L’autre ne veut pas entrer ou c’est la chance à lui

veut[j]==faux ou tour==i

Chap. 7 32

Thread T0:while(true){ veut[0] = vrai; // T0 veut entrer tour = 1; // T0 donne une chance à T1 while (veut[1]&&tour=1); CritSect veut[0] = faux; // T0 ne veut plus entrer nonCritSect}

Thread T1:while(true){ veut[1] = vrai; // T1 veut entrer tour = 0; // T1 donne une chance à 0 while (veut[0]&&tour=0); CritSect veut[1] = faux; // T1 ne veut plus entrer nonCritSect}

Algorithme de Peterson vue globale

Initialisations possiblesInitialisations possibles

Afin qu’un premier processus puisse entrer dans CritSec, il faut que le test

veut[j]==faux ou tour==i

soit vrai la première fois pour un des deux processus.

Voici une possibilité:

veut[0]=veut[1]=faux //initialisation

Maintenant, si T1 ne fait rien, veut[1] reste faux et T0 peut entrer

Exercice: Étudier les autres possibilités pour le début.

Chap. 733

Chap. 7 34

Scénario pour le changement de contrôleScénario pour le changement de contrôle

Thread T0:

… CritSect veut[0] = faux; // T0 ne veut plus entrer

…

Thread T1:

… veut[1] = vrai; // T1 veut entrer tour = 0; // T1 donne une chance à T0 while (veut[0]&&tour=0) ; //test faux, entre (F&&V)

…T1 donne une chance à T0 mais T0 a dit qu’il ne veut pas entrer.T1 entre donc dans CritSect

Chap. 7 35

Autre scénario de changem. de contrôleAutre scénario de changem. de contrôleThread T0:

CritSect veut[0] = faux; // T0 ne veut plus entrer nonCritSect veut[0] = vrai; // T0 veut entrer tour = 1; // T0 donne une chance à T1 while (veut[1]==vrai&& tour=1) ; // test vrai, n’entre pas (V&&V)

Thread T1:

veut[1] = vrai; // T1 veut entrer tour = 0; // T1 donne une chance à T0 // mais T0 annule cette action

while (veut[0]&&tour=0) ; //test faux, entre (V&&F)

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

Chap. 7 36

Mais avec un petit décalage, c’est encore T0!Mais avec un petit décalage, c’est encore T0!Thread T0:

CritSect veut[0] = faux; // 0 ne veut plus entrer nonCritSect veut[0] = vrai; // 0 veut entrer tour = 1; // 0 donne une chance à 1 // mais T1 annule cette action

while (veut[1] && tour=1) ; // test faux, entre (V&&F)

Thread T1:

veut[1] = vrai; // 1 veut entrer tour = 0; // 1 donne une chance à 0 while (veut[0]&&tour=0); // test vrai, n’entre pas

Si T0 et T1 tentent simultanément d’entrer dans CritSect, seule une valeur pour tour survivra: non-déterminisme (on ne sait pas qui gagnera), mais l’exclusion fonctionne

Chap. 7 37

N’oblige pas une tâche dN’oblige pas une tâche d’’attendre attendre pour d’autres qui pour d’autres qui pourraient ne pas avoir besoin de la CritSectpourraient ne pas avoir besoin de la CritSect

Supposons que T0 soit le seul à avoir besoin de la CritSect, ou que T1 soit lent à agir: T0 peut rentrer de suite (veut[1]==faux la dernière fois que T1 est sorti)

veut[0] = vrai // prend l’initiative

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

while veut[1] && tour=1 // veut[1]=faux, test faux, entre

CritSect

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

Cette propriété est désirable, mais peut causer famine pour T1 s’il est lent (condition de course, race condition)

Chap. 7 38

Algorithme 3: preuve de validité Algorithme 3: preuve de validité (pas matière d’examen, seulement pour les intéressés…)(pas matière d’examen, seulement pour les intéressés…)

Exclusion mutuelle est assurée car: T0 et T1 sont tous deux dans CritSect seulement

si tour est simultanément égal à 0 et 1 (impossible)

Démontrons que déroulement est satisfaits: Ti ne peut pas entrer dans CritSect seulement si

en attente dans la boucle while avec condition: veut[j] == vrai et tour = j.

Si Tj ne veut pas entrer dans CritSect alors veut[j] = faux et Ti peut entrer dans CritSect

Chap. 7 39

Algorithme 3: preuve de validité (cont.)Algorithme 3: preuve de validité (cont.)

Si Tj a effectué veut[j]=vrai et se trouve dans le while, alors tour==i ou tour==j

Si tour==i, alors Ti entre dans CritSect. tour==j alors Tj entre dans CritSect mais il fera

veut[j] =faux à la sortie: permettant à Ti d’entrer CritSect

mais si Tj a le temps de faire veut[j]=true, il devra aussi faire tour=i

Puisque Ti ne peut modifier tour lorsque dans le while, Ti entrera CritSect après au plus une entrée dans CritSect par Tj (attente limitée)

Différence importanteDifférence importante

Qelle est la différence importante entre Algo 1 et 3? Avec l’Algo 1, tous les processus (interessés

ou non) doivent entrer et sortir de leur SC en tour

Violation de l’exigence de déroulement Avec l’Algo 3, les procs qui ne sont pas

intéressés laissent veut = faux et sont libres de faire autres choses

Chap. 7 40

Exemple Exemple de faute possiblede faute possible

Thread Ti:

while (true) {

veut[i] = vrai; // je veux entrer

tour = j; // je donne une chance à

l’autre

do while

(veut[i] && tour==j);

SC

veut[i] = faux;

SR

}

Cette solution implémente correctement la SC

Un seul proc à la fois peut entrer

Mais elle viole le déroulement veut[i] = faux n’affecte pas Tj car Tj

ne teste pas veut[i] Tj doit attendre que Ti fasse tour=j

après qu’il a fait tour=i, ce qui pourrait ne jamais se vérifier

Chap. 7 41

Chap. 7 42

A propos de l’échec des threadsA propos de l’échec des threads

Si une solution satisfait les critères d’ExclMutuelle et déroulement, elle procure une robustesse face à l’échec d’un thread dans sa nonCritSect un thread qui échoue dans sa nonCritSect est comme un

thread qui ne demande jamais d’entrer... Par contre, aucune solution valide ne procure une

robustesse face à l'échec d’un thread dans sa section critique (CritSect) un thread Ti qui échoue dans sa CritSect n’envoie pas de

signal aux autres threads: pour eux Ti est encore dans sa CritSect...

solution: temporisation. Un thread qui a la SC après un certain temps est interrompu par le SE

Chap. 7 43

Extension à >2 threads Extension à >2 threads

L ’algorithme de Peterson peut être généralisé au cas de >2 threads

http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1778&context=cstech

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

Chap. 7 44

Une leçon à retenir…Une leçon à retenir…

Afin 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

Chap. 7 45

Critique des solutions par logicielCritique 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 CritSect sont actifs à 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... Rappel: scrutation, polling contre interruption

Chap. 7 46

Solutions matérielles: désactivation des Solutions matérielles: désactivation des interruptionsinterruptions

Si plusieurs UCT: exclusion mutuelle n’est pas préservée Donc pas bon en

général

Thread Pi:while(true){ désactiver interrupt CritSect rétablir interrupt nonCritSect}

Chap. 7 47

Solutions matérielles: instructions machine Solutions matérielles: instructions machine spécialiséesspécialisées

Normal: pendant qu’un thread ou processus fait accès à une adresse de mémoire, aucun autre ne peut faire accès à la même adresse en même temps

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

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

Chap. 7 48

L’instruction test-and-set L’instruction test-and-set

Une version C de test-and-set:

Un algorithme utilisant testset pour Exclusion Mutuelle:

Variable partagée b est initialisée à 0

Le 1er Pi qui met b à 1 entre dans CritSect

Les autres trouvent b à 1, n’entrent pasbool testset(int& i)

{ if (i==0) { i=1; return true; } else { return false; }}

Tâche Pi: while testset(b)==false ; CritSect //entre quand vrai b=0; nonCritSect

Instruction indivisible!

Chap. 7 49

bool testset(int& i){

if (i==0) {i=1;return true;

} else {return false;

}}

Tâche Pi:while testset(b)==false ;

CritSect //entre quand vrai

b=0;nonCritSect

Instruction atomique!

Quand un proc Pi cherche d’entrer:

•Si la SC est occupée, • i=1, testset(b)=faux et Pi reste en attente

•Si la SC est libre, • i=0, il est tout de suite mis à 1 mais

testset(b)=vrai et Pi peut entrer

Chap. 7 50

L’instruction test-and-set (cont.)L’instruction test-and-set (cont.)

Exclusion mutuelle est assurée: si Ti entre dans CritSect, l’autre Tj est actif à attendre

Problème: utilise encore actif à attendre Peut procurer facilement l’exclusion mutuelle

mais nécessite algorithmes plus complexes pour satisfaire les autres exigences du problème de la section critique

Lorsque Ti sort de CritSect, la sélection du Tj qui entrera dans CritSect est arbitraire: pas de limite sur l’attente: possibilité de famine

Chap. 7 51

Instruction ‘Échange’ Instruction ‘Échange’ (Swap)(Swap)

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

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

Chap. 7 52

Utilisation de xchg pour exclusion mutuelle Utilisation de xchg pour exclusion mutuelle (Stallings)(Stallings)

Variable partagée b est initialisée à 0

Chaque Ti possède une variable locale k

Le Ti pouvant entrer dans CritSect est celui qui trouve b=0

Ce Ti exclut tous les autres en assignant b à 1 Quand CritSect est occupée,

k et b seront 1 pour un autre thread qui cherche à entrer

Mais k est 0 pour le thread qui est dans la CritSect

Thread Ti:while(true){ k = 1 while k!=0 xchg(k,b); CritSect xchg(k,b); nonCritSect}

usage:

indivisible

Chap. 7 53

Solutions basées sur des instructions fournies Solutions basées sur des instructions fournies par le SEpar le SE (appels du système) (appels du système)

Les solutions vues jusqu’à présent sont difficiles à programmer

On voudrait aussi qu`il soit plus facile d’éviter des erreurs communes, comme interblocages, famine, etc. Besoin d’instruction à plus haut niveau

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

Chap. 7 54

SémaphoresSémaphores

Un sémaphore S est un entier qui, sauf pour l'Initialisation, est accessible seulement par ces 2 opérations indivisibles et mutuellement exclusives: acquire(S) release(S)

Il est partagé entre tous les threads qui s`intéressent à la même CritSect

Les sémaphores seront présentés en deux étapes: sémaphores qui sont actifs à attendre

Scrutation sémaphores qui utilisent interruptions et files

d ’attente

Chap. 7 55

SpinlocksSpinlocks d’Unix: Sémaphores occupés à attendre d’Unix: Sémaphores occupés à attendre (busy waiting)(busy waiting)

La façon la plus simple d’implanter les sémaphores.

Utiles pour des situations où l’attente est brève, ou il y a beaucoup d’UCTs

S est un entier initialisé à une valeur positive, afin qu’un premier thread puisse entrer dans la CritSect

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

S ne peut jamais être négatif

acquire(S): while S=0 ; S--;

release(S): S++;

Attend si no. de threads qui peuvent entrer = 0

Augmente de 1 le no des threads qui peuvent entrer

Chap. 7 56

Indivisibilité

Acquire: La séquence test-décrément est indivisible, mais pas la boucle!

Release est indivisible.

Rappel: les sections indivisibles ne peuvent pas être exécutées simultanément par différent threads

(ceci peut être obtenu en utilisant un des mécanismes précédents)

S = 0

indivisible S - -

F

V

CritSect

IMPORTANT

Chap. 7 57

Indivisibilité et atomicitéIndivisibilité et atomicité

S = 0

atomique S - -

F

VS++

La boucle peut être interrompue pour permettre à un autre thread d’interrompre l’attente quand l’autre thread sort de la CritSect

interruptible autre thr.

CritSect

CritSect

(Autre thread)

Chap. 7 58

Thread T1: while(true){ acquire(S);

CritSect release(S); nonCritSect

}

Thread T2:while(true){ acquire(S); CritSect release(S); nonCritSect}

Semaphores: vue globale

Initialise S à >=1

Peut être facilement généralisé à plus. threads

Chap. 7 59

Utilisation des sémaphores pour sections Utilisation des sémaphores pour sections critiques critiques

Pour n threads Initialiser S à 1 Alors 1 seul thread peut

être dans sa CritSect Pour permettre à k

threads d’exécuter CritSect, initialiser S à k

Thread Ti:while(true){ acquire(S); CritSect release(S); nonCritSect}

Chap. 7 60

Utilisation des sémaphores pour Utilisation des sémaphores pour synchronisation de threadssynchronisation de threads

On a 2 threads P1 dans le premier

thread doit être exécuté avant P2 dans le deuxième

Définissons un sémaphore S

Initialisons S à 0

P1

P2

P1;release(S)

acquire(S);P2

Chap. 7 61

Interblocage et famine avec les sémaphoresInterblocage et famine avec les sémaphores

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

Interblocage: Supposons S et Q initialisés à 1 Ils seront 0 au deuxième acquire

T0 T1

acquire(S)

acquire(Q)

acquire(Q) acquire(S)

Chap. 7 62

Sémaphores: observationsSémaphores: observations

Quand S >= 0: Le nombre de threads qui peuvent exécuter

acquire(S) sans devenir bloqués = S S threads peuvent entrer dans la CritSect noter puissance par rapport à 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 (excl. mutuelle)

Quand S devient > 1, le thread qui entre le premier dans la CritSect est le premier à tester S (choix aléatoire) Famine possible

Ceci ne sera plus vrai dans la solution suivante

acquire(S):while S=0 ; S--;

Chap. 7 63

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

Quand un thread doit attendre qu’un sémaphore devienne plus grand que 0, il est mis dans une file d’attente de threads qui attendent 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 entrent dans leur CritSect

acquire et release sont des appels au 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

Chap. 7 64

Sémaphores sans attente occupéeSémaphores sans attente occupée Un sémaphore S devient une structure de données:

S.value: Une valeur: nombre de processus pouvant entrer S.list Une liste d’attente

acquire(S): bloque thread qui effectue l’opération et l’ajoute à la liste S.list

release(S) enlève (selon une politique juste, ex: PAPS/FIFO) un thread de S.list et le place sur la liste des threads prêts/ready.un tel sémaphore est associé à une liste d’attente comme un disque, une imprimante, etc.

Chap. 7 65

Implementation Implementation (les boîtes représentent des séquences atomiques)(les boîtes représentent des séquences atomiques)

acquire(S): S.value --;if S.value < 0 { // CritSect occupée

add this thread to S.list;block // thread mis en état attente (wait)

}

release(S): S.value ++;if S.value 0 { // des threads attendent

remove a thread P from S.list;wakeup(P) // thread choisi devient prêt

}

S.value doit être initialisé à une valeur non-négative (dépendant de l’application, v. exemples)

Chap. 7 66

Figure montrant la relation entre le contenu de la file et la valeur de S(la séquence montrée n’est pas contigüe)

S > 0: n threads peuvent entrer

S 0: aucun thread ne peut entrer et le nombre de threads qui attendent sur S est = |S|

Stallings

Chap. 7 67

acquireacquire et et releaserelease contiennent elles mêmes des CritSect! contiennent elles mêmes des CritSect!

Les opérations acquire et release doivent être exécutées de manière indivisible (un seul thr. à la fois)

Dans un système avec 1 seule UCT, ceci peut être obtenu en inhibant les interruptions quand un thread exécute ces opérations

Normalement, nous devons utiliser un des mécanismes vus avant instructions spéciales, algorithme de Peterson, etc.

L’attente occupée dans ce cas ne sera pas trop onéreuse car acquire et release sont brefs

ExerciceExercice

Avec cette solution, on peut effectivement éviter la famine!

Expliquez pourquoi et comment

Chap. 7 68

Chap. 7 69

Problèmes classiques de synchronisationProblèmes classiques de synchronisation

Tampon borné (producteur-consommateur) Écrivains - Lecteurs Les philosophes mangeant

Chap. 7 70

Le pb du producteur - consommateurLe pb du producteur - consommateur

Un problème classique dans l ’étude des threads communicants un thread producteur produit des données

(p.ex.des enregistrements d ’un fichier) pour un thread consommateur

Chap. 7 71

Tampons de communicationTampons de communication

Prod

Cons

1 donn

Prod

Cons

1 donn 1 donn1 donn

Si le tampon est de longueur 1, le producteur et consommateur doivent forcement aller à la même vitesse

Des tampons de longueur plus grandes permettent une certaine indépendance. P.ex. à droite le consommateur a été plus lent

Chap. 7 72

Le tampon borné Le tampon borné (bounded buffer)(bounded buffer)une structure de données fondamentale dans les SEune structure de données fondamentale dans les SE

b[0] b[1]

b[7] b[2]

b[6] b[3]

b[4]b[5]

ou

out: 1ère pos. pleine

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

in: 1ère pos. libre

out: 1ère pos. pleine

bleu: plein, blanc: libre

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

Chap. 7 73

Pb de sync entre threads pour le tampon bornéPb de sync entre threads pour le tampon borné

Étant donné que le prod et le consommateur sont des threads indépendants, des problèmes pourraient se produire en permettant accès simultané au tampon

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

Chap. 7 74

Sémaphores: rappelSémaphores: rappel

Soit S un sémaphore sur une CritSect il est associé à une file d ’attente S > 0 : S threads peuvent entrer dans CritSect S = 0 : aucun thread ne peut entrer, aucun thread en attente S < 0 : |S| thread dans file d ’attente

acquire(S): S - - si avant S > 0, ce thread peut entrer dans CritSect si avant S <= 0, ce thread est mis dans file d ’attente

release(S): S++ si avant S < 0, il y avait des threads en attente, et un thread

est réveillé si avant S >= 0, rien (mais un proc de plus pourra entrer)

Indivisibilité de ces ops

Pensez à un petit entrepôtPensez à un petit entrepôt

Ceux qui veulent y apporter des choses, doivent avant tout savoir s’il y a de l’espace Un sémaphore E dit combien d’espace dispo:

Producteur peut entrer si et seulement si il y en a Ceux qui veulent en retirer des choses, doivent avant tout

savoir s’il y en a à retirer Un sémaphore F qui dit combien d’éléments disponibles:

Consommateur peut entrer si et seulement si il y en a Une seule personne peut y travailler à un moment donné

Un sémaphore M dit s’il y a quelqu’un dans l’entrepôt Occupé ou libre

Chap. 7 75

Chap. 7 76

Autrement dit …Autrement dit …

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

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

Un sémaphore M pour exclusion mutuelle sur l’accès au tampon Les sémaphores suivants ne font pas l’ExMut

Chap. 7 77

Solution de P/C: tampon circulaire fini de dimension k

Initialization: M.count=1; //excl. mut. F.count=0; //esp. pleins E.count=k; //esp. vides

Producteur:while(true){ produce v; acquire(E); acquire(M); ajouter(v); release(M); release(F);}

Consommateur:while(true) acquire(F); acquire(M); retirer(); release(M); release(E); consume(w);}

Sections Critiques

ajouter(v): b[in]=v; In ++ mod k;

retirer(): w=b[out]; Out ++ mod k; return w;

Chap. 7 78

Points intéressants à étudierPoints intéressants à étudier

Dégâts possibles en inter changeant les instructions sur les sémaphores

ou en changeant leur initialisation Généralisation au cas de plus. prods et

cons

Chap. 7 79

Concepts importants de cette partie du Chap 7Concepts importants de cette partie du Chap 7

Le problème de la section critique L’entrelacement et l’indivisibilité 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é Par rapport au manuel: ce que nous n’avons pas

vu en classe vous le verrez au lab

Chap. 7 80

Glossaire: atomicitéGlossaire: atomicité

Atomicité, non-interruptibilité: Le mot atomique a été utilisé dans son sens original grec: a-

tomos = non-divisible Faut pas se faire dérouter par le fait que les atomes dans la physique

moderne sont divisibles en électrons, protons, etc. …

La définition précise d’atomicité, non-déterminisme etc. est un peu compliquée, et il y en a aussi des différentes… (faites une recherche Web sur ces mot clé)

Ce que nous discutons dans ce cours est un concept intuitif: une séquence d’ops est atomique si elle est exécutée toujours du début à la fin sans aucune interruption ni autres séquences en parallèle

Chap. 7 81

Non-déterminisme et conditions de courseNon-déterminisme et conditions de course

Non-déterminisme: une situation dans laquelle il y a plusieurs séquences d’opérations possibles à un certain moment, même avec les mêmes données. Ces différentes séquences peuvent conduire à des résultats différents

Conditions de course: Les situations dans lesquelles des activités exécutées en parallèle sont ‘en course’ les unes contre les autres pour l`accès à des ressources (variables partagées, etc.), sont appelées ‘conditions de course ’.

Chap. 7 82

Thread, processusThread, processus

Les termes thread, process, sont presque équivalents dans ce contexte

Tout ce que nous avons dit au sujet de threads concurrent est aussi valable pour processus concurrents

Chap. 7 83

Différents noms pour Différents noms pour acquireacquire, , releaserelease

Acquire, release ont eté appelés des noms différents

Leur inventeur (Dijkstra) les appelait P, V (provenant de mots en Hollandais …)

D’autres auteurs les appellent wait, signal Etc.

Chap. 7 84

Sémaphores binairesSémaphores binaires

Dans les sémaphores binaires, la variable ne peut être que 0 ou 1

P.ex. le sémaphore S dans le producteur-consommateur est binaire

On a prouvé en théorie que tout pb de synchro peut être résolu utilisant seulement des sémaphores binaires, v. manuel

Chap. 7 85

Difficulté des problèmes de synchronisationDifficulté des problèmes de synchronisation

Les problèmes et solutions qui se trouvent dans l’étude du parallélisme et de la répartition sont entre les plus complexes de l’informatique

Car les programmes parallèles ont un comportement mutuel imprévisible dans le temps

Beaucoup de concepts complexes de math, physique etc. peuvent entrer en considération

Heureusement, les langages de programmation comme Java nous cachent cette complexité

Mais pas complètement … les systèmes répartis sont sujets à des pannes imprévisibles dues à des conditions de temporisation non prévues