Synchronisation de Processus - Université de Sherbrooke

Synchronisation de Processus - Université de Sherbrooke

Module 5 - Synchronisation de Processus (ou threads, ou fils ou tches) Chapitre 6 (Silberchatz) Module 5 1 Problmes avec concurrence = paralllisme Les threads concurrents doivent parfois partager donnes (fichiers ou mmoire commune) et ressources Module On parle donc de tches coopratives Si laccs nest pas contrl, le rsultat de

lexcution du programme pourra dpendre de lordre dentrelacement de lexcution des instructions (non-dterminisme). Un programme pourra donner des rsultats diffrents et parfois indsirables de fois en fois 2 Un exemple Module Deux threads excutent cette mme procdure et partagent la mme base de donnes Ils peuvent tre interrompus nimporte o Le rsultat de l excution concurrente de P1 et P2 dpend de l`ordre de leur

entrelacement M. X demande une rservation davion Base de donnes dit que fauteuil A est disponible Fauteuil A est assign X et marqu occup 3 Vue globale dune excution possible P1 M. Leblanc demande une rservation davion Interruption ou retard P2 M. Guy demande une rservation davion

Base de donnes dit que fauteuil 30A est disponible Fauteuil 30A est assign Leblanc et marqu occup Module Base de donnes dit que fauteuil 30A est disponible Fauteuil 30A est assign Guy et marqu occup 4 Deux oprations en parallle sur une var a partage (b est priv chaque processus) P1 b=a interruption

P2 b=a b++ a=b b++ a=b Supposons que a soit 0 au dbut P1 travaille sur le vieux a donc le rsultat final sera a=1. Sera a=2 si les deux tches sont excutes lune aprs lautre Module 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) 5 3me exemple Thread P1 Thread P2 static char a;

static char a; void echo() { cin >> a; void echo() { cin >> a; cout << a; } cout << a; } Si la var a est partage, le premier a est effac Si elle est prive, lordre daffichage est renvers Module 6 Autres exemples

Module Des threads qui travaillent en simultanit sur une matrice, par ex. un pour la mettre jour, l`autre pour en extraire des statistiques Problme qui affecte le programme du tampon born, v. manuel Quand plusieurs threads excutent en parallle, nous ne pouvons pas faire dhypothses sur la vitesse dexcution des threads, ni leur entrelacement Peuvent tre diffrents chaque excution du programme 7 Section Critique Module Partie dun programme dont lexcution de doit pas entrelacer avec autres programmes Une fois quun tche y entre, il faut lui permettre

de terminer cette section sans permettre autres tches de jouer sur les mmes donnes 8 Le problme de la section critique Module Lorsquun thread manipule une donne (ou ressource) partage, nous disons quil se trouve dans une section critique (SC) (associe cette donne) Le problme de la section critique est de trouver un algorithme d`exclusion mutuelle de threads dans l`excution de leur SCs afin que le rsultat de leurs actions ne dpendent pas de lordre dentrelacement de leur excution (avec un ou plusieurs processeurs)

Lexcution des sections critiques doit tre mutuellement exclusive: tout instant, un seul thread peut excuter une SC pour une var donne (mme lorsquil y a plusieurs processeurs) Ceci peut tre obtenu en plaant des instructions spciales dans les sections d`entre et sortie Pour simplifier, dornavant nous faisons lhypothse quil ny a qune seule SC dans un programme. 9 Structure du programme Chaque thread doit donc demander une permission avant dentrer dans une section critique (SC) La section de code qui effectue cette requte est la section dentre La section critique est normalement suivie dune section de sortie Le code qui reste est la section restante (SR): non-critique

repeat section dentre section critique section de sortie section restante forever Module 10 Application M. X demande une rservation davion Section dentre Section critique Base de donnes dit que fauteuil A est disponible Fauteuil A est assign X et marqu occup Section de sortie Module

11 Critres ncessaires pour solutions valides Exclusion Mutuelle: tout instant, au plus un thread peut tre dans une section critique (SC) pour une variable donne Progrs: absence d`interblocage (Chap 7) si un thread demande d`entrer dans une section critique un moment o aucun autre thread en fait requte, il devrait tre en mesure dy entrer Non interfrence:

Mais on fait l hypothse quun thread qui entre dans une section critique, en sortira. Attente limite (bounded waiting): Module Si un thread sarrte dans sa section restante, ceci ne devrait pas affecter les autres threads aucun thread ternellement empch datteindre sa SC (pas de famine) 12 Types de solutions

Solutions par logiciel des algorithmes dont la validit ne sappuie pas sur lexistence d`instruction spciales Solutions fournies par le matriel sappuient sur lexistence de certaines instructions (du processeur) spciales Solutions fournies pas le SE procure certains appels du systme au programmeur Toutes les solutions se basent sur latomicit de laccs la mmoire centrale: une adresse de mmoire ne peut tre affecte que par une instruction la fois, donc par un thread la fois. Plus en gnral, toutes les solutions se basent sur l existence dinstructions atomiques, qui fonctionnent comme SCs de base Atomicit = indivisibilit Module 13 Solutions par logiciel

(pas pratiques, mais intressantes pour comprendre le pb) Nous considrons dabord 2 threads Algorithmes 1 et 2 ne sont pas valides Algorithme 3 est valide (algorithme de Peterson) Notation Module Montrent la difficult du problme Dbutons avec 2 threads: T0 et T1 Lorsque nous discutons de la tche Ti, Tj dnotera toujours lautre tche (i != j)

14 Algorithme 1: threads se donnent mutuellement le tour La variable partage turn est initialise 0 ou 1 La SC de Ti est excute ssi turn = i Ti est occup attendre si Tj est dans SC. Fonctionne pour lexclusion mutuelle! Pas de famine (seulement 1 thread son tour selon turn).

Mais critre du progrs nest pas satisfait car lexcution des SCs doit strictement alterner Thread Ti: repeat while(turn!=i);}{ SC turn = j; SR Rien forever faire Ex 1: T0 possde une longue SR et T1 possde 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 dentrer dans sa SC: refuse! il doit attendre que T0 lui donne le tour. Module 15 initialisation de turn 0 ou 1 Thread T0: repeat while(turn!=0)

{}; SC turn = 1; SR forever Thread T1: repeat while(turn!=1) {}; SC turn = 0; SR forever Algorithme 1 vue globale Ex 2: Gnralisation n threads: chaque fois, avant quun thread puisse rentrer dans sa section critique, il lui faut attendre que tous les autres aient eu cette chance! Module 16 Algorithme 2 ou lexcs de courtoisie...

Une variable Boolenne par Thread: flag[0] et flag[1] Ti signale quil dsire excuter sa SC par: flag[i] =vrai Mais il nentre pas si lautre est aussi intress! Exclusion mutuelle ok Progrs ok Absence de famine pas satisfait: Considrez la squence: T0: flag[0] = vrai T1: flag[1] = vrai

Module Thread Ti: repeat flag[i] = vrai; while(flag[j]==vrai) {}; SC flag[i] = faux; SR forever rien faire Chaque thread attendra indfiniment pour excuter sa SC: on a une famine 17 Aprs vous, monsieur Aprs vous, monsieur Thread T0: repeat

flag[0] = vrai; while(flag[1]==vrai);}{ SC flag[0] = faux; SR forever Thread T1: repeat flag[1] = vrai; while(flag[0]==vrai);}{ SC flag[1] = faux; SR forever Algorithme 2 vue globale T0: flag[0] = vrai T1: flag[1] = vrai interblocage! Module 18 Algorithme 3 (dit de Peterson): bon! combine les deux ides: flag[i]=intention dentrer; turn= qui le tour

Initialisation: Thread Ti: flag[0] = flag[1] = faux repeat flag[i] = vrai; turn = i ou j // je veux entrer Dsire dexcuter SC est turn = j; indiqu par flag[i] = vrai // je donne une chance lautre do while flag[i] = faux la section de (flag[j]==vrai && turn==j);}{ sortie SC flag[i] = faux; SR forever

Module 19 Entrer ou attendre? Thread Ti attend si: Tj veut entrer est cest la chance de Tj Un thread Ti entre si: Tj ne veut pas entrer ou cest la chance de Ti Module flag[j]==vrai et turn==j

flag[j]==faux ou turn==i Pour entrer, un thread dpend de la bonne volont de lautre quil lui donne la chance! 20 Thread T0: repeat flag[0] = vrai; // T0 veut entrer turn = 1; // T1 veut entrer turn = 0; // T0 donne une chance T1 while (flag[1]==vrai&&turn=1);}{ SC flag[0] = faux; // T0 ne veut plus entrer

SR forever Thread T1: repeat flag[1] = vrai; // T1 donne une chance 0 while (flag[0]==vrai&&turn=0);}{ SC flag[1] = faux; // T1 ne veut plus entrer SR forever Algorithme de Peterson vue globale Module 21 Scnario pour le changement de contrle Thread T0:

SC flag[0] = faux; // T0 ne veut plus entrer SR Thread T1: flag[1] = vrai; // T1 veut entrer turn = 0; // T1 donne une chance T0 while (flag[0]==vrai&&turn=0);}{ //test faux, entre

T1 prend la relve, donne une chance T0 mais T0 a dit quil ne veut pas entrer. T1 entre donc dans la SC Module 22 Autre scnario de changem. de contrle Thread T0: Thread T1: SC flag[0] = faux; // T0 ne veut plus entrer SR flag[0] = vrai; // T0 veut entrer turn = 1; // T0 donne une chance T1 while (flag[1]==vrai&&turn=1);}{ // test vrai, nentre pas

flag[1] = vrai; // T1 veut entrer turn = 0; // T1 donne une chance T0 // mais T0 annule cette action while (flag[0]==vrai&&turn=0);}{ //test faux, entre T0 veut rentrer mais est oblig de donner une chance T1, qui entre Module 23 Mais avec un petit dcalage, cest encore T0! Thread T0: Thread T1: SC flag[0] = faux; // 0 ne veut plus entrer

RS flag[0] = vrai; // 0 veut entrer turn = 1; // 0 donne une chance 1 // mais T1 annule cette action flag[1] = vrai; // 1 veut entrer turn = 0; // 1 donne une chance 0 while while (flag[1]==vrai&&turn=1)( ;}{flag[0]==vrai&&turn=0);}{ // test vrai, nentre pas // test faux, entre Module Si T0 et T1 tentent simultanment dentrer dans SC, seule une valeur pour turn survivra: non-dterminisme (on ne sait pas qui gagnera), mais lexclusion fonctionne

24 Donc cet algo. noblige pas une tche dattendre pour dautres 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 dernire fois que T1 est sorti) flag[0] = vrai // prend linitiative turn = 1 // donne une chance lautre while flag[1]==vrai && turn=1 {} //test faux, entre SC flag[0] = faux // donne une chance lautre

Cette proprit est dsirable Module 25 Algorithme 3: preuve de validit Exclusion mutuelle est assure car: Dmontrons que progrs et attente limite sont satisfaits: Module T0 et T1 sont tous deux dans SC seulement si turn est simultanment gal 0 et 1 (impossible) 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 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 Module turn==i, alors Ti entre dans SC. turn==j alors Tj entre dans SC mais il fera flag[ j] =false la sortie: permettant Ti dentrer CS mais si Tj a le temps de faire flag[ j]=true, il

devra aussi faire turn=i Puisque Ti ne peut modifier turn lorsque dans le while(), Ti entrera SC aprs au plus une entre dans SC par Tj (attente limite) 27 A propos de lchec des threads Module Si une solution satisfait les 3 critres (EM, progrs et attente limite), elle procure une robustesse face lchec dun thread dans sa section restante (SR) un thread qui choue dans sa SR est comme un thread ayant une SR infiniment longue... Par contre, aucune solution valide ne procure une robustesse face l'chec dun thread dans sa section critique (SC) un thread Ti qui choue dans sa SC nenvoie pas de signal aux autres threads: pour eux Ti est encore dans sa SC... 28

Extension >2 threads L algorithme de Peterson peut tre gnralis au cas de >2 threads Cependant, dans ce cas il y a des algorithmes plus lgants, comme lalgorithme du boulanger, base sur lide de prendre un numro... Module Pas le temps den parler 29 Une leon retenir fin que des threads avec des variables partages puissent russir, il est ncessaire que tous les threads impliqus

utilisent le mme algorithme de coordination Module Un protocole commun 30 Critique des solutions par logiciel Difficiles programmer! Et comprendre! Les threads qui requirent lentre dans leur SC sont occups attendre (busy waiting); consommant ainsi du temps de processeur Module Les solutions que nous verrons dornavant sont toutes

bases sur lexistence dinstructions spcialises, qui facilitent le travail. Pour de longues sections critiques, il serait prfrable de bloquer les threads qui doivent attendre... 31 Solutions matrielles: dsactivation des interruptions Module Sur un uniprocesseur: exclusion mutuelle est prserve mais lefficacit se dtriore: lorsque dans SC il est impossible dentrelacer lexcution avec dautres threads

dans une SR Perte dinterruptions Sur un multiprocesseur: exclusion mutuelle nest pas prserve Une solution qui nest gnralement pas acceptable Process Pi: repeat inhiber interrupt section critique rtablir interrupt section restante forever 32 Solutions matrielles: instructions machine spcialises

Module Normal: pendant quun thread ou processus fait accs une adresse de mmoire, aucun autre ne peut faire accs la mme adresse en mme temps Extension: instructions machine excutant plusieurs actions (ex: lecture et criture) sur la mme case de mmoire de manire atomique (indivisible) Une instruction atomique ne peut tre excute que par un thread la fois (mme en prsence de plusieurs processeurs) 33 Linstruction test-and-set Une version C++ de test-and-set:

bool testset(int& i) { if (i==0){ i=1; return true; } else { return false; } } Un algorithme utilisant testset pour Exclusion Mutuelle: Variable partage b est initialise 0 Cest le 1er Pi qui met b 1 qui entre dans SC Tche Pi: while testset(b)==false {}; SC //entre quand vrai b=0; SR

Instruction atomique! Module 34 Linstruction test-and-set (cont.) Module Exclusion mutuelle est assure: si Ti entre dans SC, lautre Tj est occup attendre Problme: utilise encore occup attendre Peut procurer facilement lexclusion mutuelle mais ncessite algorithmes plus complexes pour satisfaire les autres exigences du problme de la section critique Lorsque Ti sort de SC, la slection du Tj qui entrera dans SC est arbitraire: pas de limite sur lattente: possibilit de famine

35 Instruction change Module Certains UCTs (ex: Pentium) offrent une instruction xchg(a,b) qui interchange le contenue de a et b de manire atomique. Mais xchg(a,b) souffre des mme lacunes que test-and-set 36 Utilisation de xchg pour exclusion mutuelle (Stallings)

Variable partage b est initialise 0 Chaque Ti possde une variable locale k Le Ti pouvant entrer dans SC est celui qui trouve b=0 Ce Ti exclue tous les autres en assignant b 1 Module Quand SC est occupe, k et b seront 1 pour un autre thread qui cherche entrer Mais k est 0 pour le thread qui est dans la SC usage: Thread Ti: repeat k = 1

while k!=0 xchg(k,b); SC xchg(k,b); SR forever 37 Solutions bases sur des instructions fournies par le SE (appels du systme) Les solutions vues jusqu prsent sont difficiles programmer et conduisent du mauvais code. On voudrait aussi qu`il soit plus facile dviter des erreurs communes, comme interblocages, famine, etc. Module

Besoin dinstruction plus haut niveau Les mthodes que nous verrons dornavant utilisent des instructions puissantes, qui sont implantes par des appels au SE (system calls) 38 Smaphores Un smaphore S est un entier qui, sauf pour l'Initialisation, est accessible seulement par ces 2 oprations atomiques et mutuellement exclusives: wait(S) signal(S) Il est partag entre tous les procs qui s`intressent la mme section critique Les smaphores seront prsents en deux tapes: smaphores qui sont occups attendre (busy waiting) smaphores qui utilisent des files d attente

On fait distinction aussi entre smaphores compteurs et smaphores binaires, mais ces derniers sont moins puissants (v. livre). Module 39 Spinlocks dUnix: Smaphores occups attendre (busy waiting) La faon la plus simple dimplanter les smaphores. Utiles pour des situations o

lattente est brve, ou il y a beaucoup dUCTs S est un entier initialis une valeur positive, de faon que un premier thread puisse entrer dans la SC Quand S>0, jusqu n threads peuvent entrer Quand S<=0, il faut attendre S+1 signals (dautres threads) pour entrer wait(S): while S<=0 {}; S--; Attend si no. de threads qui peuvent entrer = 0 ou ngatif signal(S): S++; Augmente de 1 le no des threads qui peuvent entrer Module 40

Atomicit Wait: La squence testdcrment est atomique, mais pas la boucle! S <= 0 Signal est atomique. Rappel: les sections atomiques ne peuvent pas tre excutes simultanment par diffrent threads (ceci peut tre obtenu un utilisant un des mcanismes prcdents) Module V F atomique S-- SC 41 Atomicit et interruptibilit

SC S++ interruptible S <= 0 autre thr. V F atomique S-- SC La boucle nest pas atomique pour permettre un autre thread dinterrompre lattente sortant de la SC Module 42 Utilisation des smaphores pour sections critiques

Module Pour n threads Initialiser S 1 Alors 1 seul thread peut tre dans sa SC Pour permettre k threads dexcuter SC, initialiser S k Thread Ti: repeat wait(S); SC signal(S); SR forever 43 Initialise S >=1

Thread T1: repeat wait(S); SC signal(S); SR forever Thread T2: repeat wait(S); SC signal(S); SR forever Semaphores: vue globale Peut tre facilement gnralis plus. threads Module 44 Utilisation des smaphores pour synchronisation de threads

On a 2 threads: T1 et T2 nonc S1 dans T1 doit tre excut avant nonc S2 dans T2 Dfinissons un smaphore S Initialiser S 0 Synchronisation correcte lorsque T1 contient: et que T2 contient:

Module S1; signal(S); wait(S); S2; 45 Interblocage et famine avec les smaphores Famine: un thread peut narriver jamais excuter car il ne teste jamais le smaphore au bon moment Interblocage: Supposons S et Q initialiss 1 T0 T1

wait(S) wait(Q) wait(Q) Module wait(S) 46 Smaphores: observations Quand S >= 0: Le nombre de threads qui peuvent excuter wait(S) sans devenir bloqus = S S threads peuvent entrer dans la SC noter puissance par rapport mcanismes dj vus dans les solutions o S peut tre >1 il faudra avoir un 2me sm.

pour les faire entrer un la fois (excl. mutuelle) Quand S devient > 1, le thread qui entre le premier dans la SC est le premier tester S (choix alatoire) Module wait(S): while S<=0 {}; S--; ceci ne sera plus vrai dans la solution suivante Quand S < 0: le nombre de threads qui attendent sur S est = |S| - Ne sapplique pas pour smaphores occups attendre 47

Comment viter lattente occupe et le choix alatoire dans les smaphores Module Quand un thread doit attendre quun smaphore devienne plus grand que 0, il est mis dans une file dattente de threads qui attendent sur le mme smaphore. Les files peuvent tre PAPS (FIFO), avec priorits, etc. Le SE contrle l`ordre dans lequel les threads entrent dans leur SC. wait et signal sont des appels au SE comme les appels des oprations dE/S. Il y a une file d attente pour chaque smaphore comme il y a une file dattente pour chaque unit dE/S. 48

Smaphores sans attente occupe Un smaphore S devient une structure de donnes: Une valeur Une liste dattente L Un thread devant attendre un smaphore S, est bloqu et ajout la file dattente S.L du smaphore (v. tat bloqu = attente chap 3). Module signal(S) enlve (selon une politique juste, ex: PAPS/FIFO) un thread de S.L et le place sur la liste des threads prts/ready. 49 Implementation

(les botes rprsentent des squences non-interruptibles) wait(S): S.value --; if S.value < 0 { // SC occupe add this thread to S.L; block // thread mis en tat attente (wait) } signal(S): S.value ++; if S.value 0 { // des threads attendent remove a process P from S.L; wakeup(P) // thread choisi devient prt } S.value doit tre initialis une valeur nonngative (dpendant de lapplication, v. exemples) Module 50 Figure montrant la relation entre le contenu de la file et la valeur de S (Stallings)

Quand S < 0: le nombre de threads qui attendent sur S est = |S| Module 51 Wait et signal contiennent elles mmes des SC! Module Les oprations wait et signal doivent tre excutes atomiquement (un seul thr. la fois) Dans un systme avec 1 seule UCT, ceci peut tre obtenu en inhibant les interruptions quand un thread excute ces oprations Normalement, nous devons utiliser un des mcanismes vus avant (instructions spciales,

algorithme de Peterson, etc.) Lattente occupe dans ce cas ne sera pas trop onreuse car wait et signal sont brefs 52 Problmes classiques de synchronisation Module Tampon born (producteur-consommateur) crivains - Lecteurs Les philosophes mangeant 53 Le pb du producteur - consommateur Un problme classique dans l tude des threads communicants

Module un thread producteur produit des donnes (p.ex.des enregistrements d un fichier) pour un thread consommateur 54 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 mme vitesse Module

Des tampons de longueur plus grandes permettent une certaine indpendance. P.ex. droite le consommateur a t plus lent 55 Le tampon born (bounded buffer) une structure de donnes fondamentale dans les SE in: 1re pos. libre b[0] b[1] b[7] b[2] b[6] b[3] b[5] b[4] out: 1re pos. pleine ou

b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] in: 1re pos. libre bleu: plein, blanc: libre out: 1re pos. pleine Le tampon born se trouve dans la mmoire partage entre consommateur et usager Module 56 Pb de sync entre threads pour le tampon born Module

tant donn que le prod et le consommateur sont des threads indpendants, des problmes pourraient se produire en permettant accs simultan au tampon Les smaphores peuvent rsoudre ce problme 57 Smaphores: rappel. Module Soit S un smaphore sur une SC il est associ une file d attente S positif: S threads peuvent entrer dans SC S zro: aucun thread ne peut entrer, aucun thread en attente S ngatif: |S| thread dans file d attente

Wait(S): S - si aprs S >= 0, thread peut entrer dans SC si S < 0, thread est mis dans file d attente Signal(S): S++ si aprs S<= 0, il y avait des threads en attente, et un thread est rveill Indivisibilit = atomicit de ces ops 58 Solution avec smaphores Un smaphore S pour exclusion mutuelle sur laccs au tampon Module Les smaphores suivants ne font pas lEM Un smaphore N pour synchroniser producteur et consommateur sur le nombre

dlments consommables dans le tampon Un smaphore E pour synchroniser producteur et consommateur sur le nombre despaces libres 59 Solution de P/C: tampon circulaire fini de dimension k Initialization: S.count=1; //excl. mut. N.count=0; //esp. pleins E.count=k; //esp. vides append(v): b[in]=v; In ++ mod k; take(): w=b[out]; Out ++ mod k; return w; Module Producer: repeat produce v;

wait(E); wait(S); append(v); signal(S); signal(N); forever Consumer: repeat wait(N); wait(S); w=take(); signal(S); signal(E); consume(w); forever Sections critiques 60 Points importants tudier dgts possibles en interchangeant les instructions sur les smaphores

ou en changeant leur initialisation Gnralisation au cas de plus. prods et cons Module 61 Concepts importants de cette partie du Chap 7 Module Le problme de la section critique

Lentrelacement et latomicit Problmes de famine et interblocage Solutions logiciel Instructions matriel Smaphores occups ou avec files Fonctionnement des diffrentes solutions Lexemple du tampon born 62 Glossaire Atomicit, non-interruptibilit: La dfinition prcise datomicit, non-dterminisme etc. est un peu complique, et il y en a aussi des diffrentes (les curieux pourraient faire une recherche Web sur ces mot cl) Ce que nous discutons dans ce cours est une 1re approximation: une squence dops est atomique si elle est excute toujours sans tre interrompue par aucune autre squence sur les mmes donnes

Module Ou son rsultat ne dpend jamais de lexistence dautres squences en parallle 63 Non-dterminisme et conditions de course Module Non-dterminisme: une situation dans laquelle il y a plusieurs squences doprations possibles un certain moment, mme avec les mmes donnes. Ces diffrentes squences peuvent conduire des rsultats diffrents Conditions de course: Les situations dans lesquelles des activits excutes en parallle sont en course les unes contre les autres pour l`accs des ressources (variables partages, etc.), sont appeles conditions de course .

64 Module Problmes classiques de synchronisation Lecteurs - Rdacteurs Les philosophes mangeant Moniteurs Threads en Java 65 Smaphores: rappel (les botes rprsentent des squences non-interruptibles) wait(S): S.value --; if S.value < 0 { // SC occupe ajouter ce thread S.L; block

// thread mis en tat attente (wait) } signal(S): S.value ++; if S.value 0 { // des threads attendent enlever un thread P de S.L; wakeup(P) // thread choisi devient prt } S.value doit tre initialis une valeur non-ngative dpendant de lapplication, v. exemples Module 66 Smaphores: rappel. Module Soit S un smaphore sur une SC

il est associ une file d attente S positif: S thread peuvent entrer dans SC S zro: aucun thread ne peut entrer, aucun thread en attente S ngatif: |S| thread dans file d attente Wait(S): S - si aprs S >= 0, thread peut entrer dans SC si S < 0, thread est mis dans file d attente Signal(S): S++ si aprs S<= 0, il y avait des threads en attente, et un thread est transfr la file prt Indivisibilit = atomicit de wait et signal 67 Problme des lecteurs - rdacteurs Plusieurs threads peuvent accder une base de donnes Les rdacteurs doivent tre synchroniss entre eux et par rapport aux lecteurs

Module Pour y lire ou pour y crire il faut empcher un thread de lire pendant lcriture il faut empcher deux rdacteurs d crire simultanment Les lecteurs peuvent y accder simultanment 68 Une solution (nexclut pas la famine)

Module Variable readcount: nombre de threads lisant la base de donnes Smaphore mutex: protge la SC o readcount est mis jour Smaphore wrt: exclusion mutuelle entre rdacteurs et lecteurs Les rdacteurs 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 rdacteurs qui crivent bloquer les rdacteurs sur wrt quand il y a des lecteurs qui lisent redmarrer les rdacteurs quand personne ne lit 69 Les donnes et les rdacteurs Donnes: deux smaphores et une variable mutex, wrt: semaphore (init. 1); readcount : integer (init. 0); Rdacteur wait(wrt);

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

Le dernier lecteur sortant doit permettre l`accs aux rdacteurs Module 71 Observations Module Le 1er lecteur qui entre dans la SC bloque les rdacteurs (wait (wrt)), le dernier les remet en marche (signal (wrt)) Si 1 rdacteur est dans la SC, 1 lecteur attend sur wrt, les autres sur mutex un signal(wrt) peut faire excuter un lecteur ou un rdacteur 72 Le problme des philosophes mangeant

Module 5 philosophes qui mangent et pensent Pour manger il faut 2 fourchettes, droite et gauche On en a seulement 5! Un problme classique de synchronisation Illustre la difficult dallouer ressources aux threads tout en vitant interblocage et famine 73

Le problme des philosophes mangeant Un thread par philosophe Un smaphore par fourchette: fork: array[0..4] of semaphores Initialisation: fork[i ] =1 for i:=0..4 Premire tentative: interblocage si chacun dbute en prenant sa fourchette gauche!

Module Thread Pi: repeat think; wait(fork[i]); wait(fork[i+1 mod 5]); eat; signal(fork[i+1 mod 5]); signal(fork[i]); forever Wait(fork[i]) 74 Le problme des philosophes mangeant Module

Une solution: admettre seulement 4 philosophes la fois qui peuvent tenter de manger Il y aura touj. au moins 1 philosophe qui pourra manger mme si tous prennent 1 fourchette Ajout dun smaphore T qui limite 4 le nombre de philosophes assis la table initial. de T 4 Thread Pi: repeat think; wait(T); wait(fork[i]); wait(fork[i+1 mod 5]); eat; signal(fork[i+1 mod 5]); signal(fork[i]); signal(T); forever

75 Avantage des smaphores (par rapport aux solutions prcdentes) Module Une seule variable partage par section critique deux seules oprations: wait, signal contrle plus localis (que avec les prcds) 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 vite si le SE est quitable (p.ex. files FIFO)

76 Problme avec smaphores: difficult de programmation wait et signal sont disperss 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 (p.ex. oublie de faire signal) Module

Considrez le cas d`un thread qui a des waits et signals dans des boucles et des tests... 77 Moniteurs: une autre solution Constructions (en langage de haut-niveau) qui procurent une fonctionnalit quivalente aux smaphores mais plus facile contrler Disponibles en: Concurrent Pascal, Modula-3... synchronized method en Java (moniteurs simplifis) Module 78 Moniteur Est un module contenant:

une ou plusieurs procdures une squence dinitialisation variables locales Caractristiques: variables locales accessibles seulement laide dune procdure du moniteur un thread entre dans le moniteur en invoquant une de ses procdures un seul thread peut excuter dans le moniteur tout instant (mais plus. threads peuvent tre en attente dans le monit.) Module

79 Moniteur Module Il assure lui seul lexclusion mutuelle: pas besoins de le programmer explicitement On assure la protection des donnes partages en les plaant dans le moniteur Le moniteur verrouille les donnes partages lorsquun thread y entre Synchronisation de threads est effectue en utilisant des variables conditionnelles qui reprsentent des conditions aprs lesquelles un thread pourrait attendre avant dexcuter dans le moniteur 80 Structure gnrale du moniteur (style Java) monitor nom-de-moniteur { // dclarations de vars

public entry p1(. . .){ code de mthode p1} public entry p2(. . .){ code de mthode p2} . . . } La seule faon de manipuler les vars internes au moniteur est dappeler une des mthodes dentre Module 81 Moniteur: Vue schmatique simplifie style Java Module 82 Variables conditionnelles (nexistent pas en Java) sont accessibles seulement dans le moniteur accessibles et modifiables seulement laide de 2 fonctions:

x: wait bloque lexcution du thread excutant sur la condition x x: signal reprend lexcution dun thread bloqu sur la condition x Module le thread pourra reprendre lexcution seulement si un autre thread excute x: signal) Sil en existe plusieurs: en choisir un (file?) Sil nen existe pas: ne rien faire 83 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 prpos soit disponible Module 84 Un concept plus gnral: Variables condition On appelle variable condition une var qui peut tre teste et Module endorme le thread qui la teste si la condition est fausse le rveille quand la condition devient vraie Sont employes dans les moniteurs, mais peuvent aussi tre utilises

indpendamment 85 Blocage dans les moniteurs threads attendent dans la file dentre ou dans une file de condition (ils n excutent pas) sur x.wait: le thread est plac dans la file de la condition (il n excute pas) x.signal amne dans le moniteur 1 thread de la file x (si Module x vide, aucun effet) 86

Un pb concernant le signal Quand un thread P excute x.signal et libre un thr. Q, il pourrait y avoir 2 thr. qui peuvent excuter, P et Q, ce qui est dfendu. Deux solutions possibles: Module P pourrait attendre jusqu` ce que Q sorte du moniteur, p.ex. dans une file spciale (dite urgente) (v. Stallings) Q pourrait attendre jusqu ce que P sorte du moniteur 87 Terminologie Java (davantage au lab)

Module Les objects avec des mthodes synchronises de Java sont essentiellement des moniteurs Un seul thread la fois peut les excuter Il y a 2 files pour un objet: File dentre File dattente (mthode wait) Un object ne peut avoir que 1 file wait Limitation importante qui complique les choses en Java Wait existe en Java + ou comme dcrit pour les moniteurs Signal sappelle notify Notify() libre 1 seul thread NotifyAll les libres tous Mais ils nexcutent pas: ils sont mis dans la file dentre 88 Files dentre et dattente (Entry and Wait Sets) Module

89 Java: diagramme simplifi de transition dtat threads prt ou en excution nouveau start nouveau excutable = runnable Sleep Wait I/O join stop ou term. de run mort notify Fin E/S

b loqu = not runnable bloqu sur une file associe un vnement Module 90 Un diagramme plus complet new NEW start Notify, E/S termine, resume, interrupted NOT RUNNABLE READY yield ou terminaison tranche ou premption

RUNNABLE = READY ou RUNNING Ordonnanceur choisit fil RUNNING Sleep, wait, I/O, join, suspend complte run method ou exception pas traite DEAD Les mthodes suspend, resume, stop ne sont pas recommandes aujourdhui (deprecated). Module 91 Retour au problme des philosophes mangeant

Module 5 philosophes qui mangent et pensent Pour manger il faut 2 baguettes, droite et gauche On en a seulement 5! Un problme classique de synchronisation Illustre la difficult dallouer ressources aux threads tout en vitant interblocage et famine 92

Philosophes mangeant structures de donnes Chaque philos. a son propre state qui peut tre (thinking, hungry, eating) Chaque condition a sa propre condition self Module philosophe i peut faire state[i] = eating ssi les voisins ne mangent pas le philosophe i peut attendre sur self [ i ] si veut manger, mais ne peut pas obtenir les 2 baguettes 93 Chaque philosophe excute jamais:

Module repeat pickup eat putdown forever 94 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; } } Module Un philosophe mange si ses voisins ne mangent pas et

sil a faim. Une fois mang, il signale de faon quun autre pickup soit possible, si pickup stait arrt sur wait Il peut aussi sortir sans avoir mang si le test est faux 95 Chercher de prendre les baguettes public entry pickUp(int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self[i].wait; } Module Phil. cherche manger en testant, sil sort de test quil nest pas mangeant il attend un autre pickup nest pas possible avant un self[i] signal 96 Dposer les baguettes public entry putDown(int i) { state[i] = THINKING;

// tester les deux voisins test((i + 4) % 5); test((i + 1) % 5); } Module Une fois fini de manger, un philosophe se proccupe de faire manger ses voisins en les testant 97 Une solution ingnieuse, cependant les baguettes ne sont que implicites Il vaut la peine de ltudier Module 98 P/C: tampon circulaire de dimension k

Module Peut consommer seulement si le nombre N dlments consommables est au moins 1 (N = in-out) Peut produire seulement si le nombre E despaces libres est au moins 1 (E = out-in) 99 Variables conditionnelles utilises Si le tampon est plein, le producteur doit attendre quil devienne non-plein Si le tampon est vide, le consommateur doit attendre quil devienne non-vide Module Var conditionnelle notfull Var conditionnelle notempty

100 Moniteur pour P/C avec tampon fini (syntaxe un peu diffrente, pas orient objet) Monitor boundedbuffer: buffer: vecteur[0..k-1] de items; nextin = 0, nextout = 0, count = 0 ; notfull, notempty: condition; Append(v): if (count==k) notfull.wait; buffer[nextin] = v; nextin = (nextin+1 mod k); count ++; notempty.signal; Take(v): if (count==0) notempty.wait; v = buffer[nextout]; nextout = (nextout+1 mod k); count --; notfull.signal; Module 101

La solution Java est plus complique surtout cause du fait que Java na pas de variables conditionnelles nommes V. manuel Module 102 Relation entre moniteurs et autre mcanismes Les moniteurs sont implants utilisant les smaphores ou les autres mcanismes dj vus Il est aussi possible d`implanter les smaphores en utilisant les moniteurs! Module Voir le texte 103

Smaphores Java Module Java na pas de smaphore, mais un smaphore peut tre construit du mcanisme de synchronisation de Java. 104 Semaphore Class public class Semaphore { private int value; public Semaphore() { value = 0; } public Semaphore(int value) { this.value = value; } Module 105

Semaphore Class (cont) public synchronized void acquire() { while (value == 0) try { wait(); } catch (InterruptedException ie) { } value--; } public synchronized void release() { ++value; notify(); } } Module 106 Le problme de la SC en pratique... Module Les systmes rels rendent disponibles plusieurs mcanismes qui peuvent tre

utiliss pour obtenir la solution la plus efficace dans diffrentes situations 107 Synchronisation en Solaris 2 (avec UCT multiples) Plusieurs mcanismes utiliss: Module adaptive mutex protge l accs aux donnes partages pour des SC courtes smaphores et condition variables protgent des SC plus importantes serrures lecteurs-rdacteurs (reader-writers locks) protgent des donnes qui normalement ne sont que lues

les mmes mcanismes sont disponibles aux usagers et dans le noyau 108 Adaptive mutex en Solaris 2 Utiliss pour des SC courtes: quand un thread veut accder des donnes partages: Module Si les donnes sont couramm. utilises par un thread excutant sur un autre UCT, l autre thread fait une attente occupe Sinon, le thread est mis dans une file d attente et sera rveill quand les donnes deviennent disponibles 109

Synchronisation Windows XP Utilise linhibition dinterruptions pour protger les ressources dans un systme avec un seul UCT Utilise spinlocks les dans systmes avec multiples UCTs Offre des objets rpartiteur (object dispatcher) qui agit comme mutexes et smaphores Module Offre aussi les vnements (events) semblables un condition variable 110 Concepts importants du Chapitre 7

Sections critiques: pourquoi Difficult du problme de la synch sur SC Accs atomique la mmoire Solutions logiciel `pures` Solution matriel: test-and-set Solutions par appels du systme: Module Bonnes et mauvaises solutions Smaphores, moniteurs, fonctionnement Problmes typiques: tampon born, lecteurs-crivains, philosophes

111

Recently Viewed Presentations

  • QICM Grand Rounds: AHRQ Update

    QICM Grand Rounds: AHRQ Update

    The Role for Communities Next Step for Value Exchanges Medicare Physician Group Practice Demonstration First Year Results of the Physician Demo Better Quality Information (2006 AQA Pilot Project*) HQA and AQA Collaborate Improving Quality and Safety Patient Involvement Campaign New...
  • Review for SBA What evidence might you use

    Review for SBA What evidence might you use

    An organelle is any of the small parts inside a plant or animal cell. Different types of organelle have different functions. 1- Cell Wall- This is the rigid wall that surrounds another membrane and keeps all the organelles inside the...
  • Hello Teachers, TAs, and all other support staff.

    Hello Teachers, TAs, and all other support staff.

    Open Tarsia with this icon on the desktop. If it is not there go to computer>programs>hermitech laboratory>tarsia3.9 (or whatever the latest version is) and right click on this icon >send to desktop and an icon will appear on your desktop.
  • Memory

    Memory

    2. Regression leads an individual faced with anxiety to retreat to a more infantile psychosexual stage. * Defense Mechanisms 3. Reaction Formation causes the ego to unconsciously switch unacceptable impulses into their opposites. People may express feelings of purity when...
  • Atoms &amp; the Periodic Table - Powers Physical Science

    Atoms & the Periodic Table - Powers Physical Science

    Atoms & the Periodic Table. Test Review. 2011. ... Bohr. Chadwick discovered this particle in the nucleus that was hard to detect because it had the same mass as a proton and was electrically neutral ... Sodium has 11 electrons....
  • Slayt 1 - esmakaya.weebly.com

    Slayt 1 - esmakaya.weebly.com

    Da Vinci Venedik'te cumhuriyetin askeri danışmanı oldu. Çok namlulu toplar, fırlatma mekanizmaları, patlayıcılar tasarladı; balistik deneylerle bu silahların etkilerini inceledi. Aynı zamanda döneminin en yetenekli dize doğaçlamacısıydı Hayal ettiği enstrüman "ViolaOrganista'dır.
  • Welcome to the Canadian Safe Boating Site!

    Welcome to the Canadian Safe Boating Site!

    Welcome the Canadian Safe Boating Training Site! Lateral buoys section
  • Progress Not Perfection A Workshop by Kevin A (Alanon) and ...

    Progress Not Perfection A Workshop by Kevin A (Alanon) and ...

    He apologized for lying, stealing, cheating - right away OR he kept it in until he was in "deep trouble" ... How is an amend made by someone who has taken the steps different than a boy who cries wolf...