modern_multithreading semafoare si zavoare versiune beta

7/23/2019 Modern_Multithreading Semafoare Si Zavoare Versiune Beta

http://slidepdf.com/reader/full/modernmultithreading-semafoare-si-zavoare-versiune-beta 1/60

3. SEMAFOARE SI ZAVOARE

Semafoarele si zavoarele sunt obiecte folosite pentru sincronizare. Semafoarele suntfolosite in excluderea mutuala si sincronizarea conditionala. Zavoarele sunt de asemenea folosite

in excluderea mutuala si au proprietati speciale care le fac utile in programele orientate-obiect. In

acest capitol vom invata cumsa folosim semafoare si zavoare pentru a crea sectiuni critice si pentru a rezolva diferite probleme de programare. Apoi vom vedea cum se comporta semafoarele

si zavoarele in Java, Win3 si !t"reads. In final,vom arata cum sa contruim semafoare personali-

zate si clase de zavoare care suporta testari si rulari multiple.

3.# SEMAFOARE NUMARATOARE

$n semafor numarator este un obiect de sincronizare care se initializeaza cu o valoareintreaga si se acceseaza prin operatii, numite ! si % &'i()stra #*+. Aceste operatii sunt numite

uneori jos si sus, de decrementare si incrementare, sau respectiv asteapta si semnal. /lasele din

librariile noastre de sincronizare suporta toate aceste tipuri de denumiri.0. 1raditional, un semafor

numarator este definit ca o variabila speciala cu valoare intreaga care este folosita ca un parametru de catre procedurile !0 si %0. 2oi folosim o definitie orientata-obiect in care un

semafor numarator este o instanta a clasei countingSemaphore .

class countingSemap"ore

public countingSemap"oreint initial!ermits0 permits 4 initial!ermits56 public void !0 ...65

public void %0 ...65

private int permits5

6

/and se defineste comportamentul metodelor !0 si %0, este utila intepreta rea in care unsemafor numarator are un rezervor de permisiuni. $n fir apeleaza metoda !0 pentru a obtine o permisiune. 'aca rezervorul este gol, firul asteapta pana cand o permisiune devine disponibila.

$n fir apeleaza metoda %0 pentru a returna o permisiune catre rezervor. $n semafor numarator s

este declarat si initiazat folosind7

countingSemap"ore s#05

%aloarea initiala, in acest caz #, reprezinta numarul initial de permisiuni din

rezervor. In sc"ema care urmeaza este prezentata una din posibilele implementari ale metodei !0

si %0. %ariabila privata de permisiuni de tip intreg memoreaza numarul curent de permisiuni dinrezervor7

public void ! 0 if permits 8 90

--permits5 :: ia o permisiune din rezervor

else :: rezervorul este gol si asteapta o permisiune

asteapta pana cand permisiunea devine pozitiva si apoi decrementeaza permisiunea cu 1.



6

public void % 0

;;permits5 :: returneaza o permisiune in rezervor 6

'aca un fir apeleaza !0 cand valoarea permisiunii este zero, asteapta pana cand permisiunea este pozitiva, o decrementeaza, iar apoi paraseste !05 in caz contrar, permisiunea

este pozitiva si firul o decrementeaza si exista !0. <etoda %0 incrementeaza permisiunea si

niciodata nu bloc"eaza firul care o apeleaza. =ste posibil ca mai multe fire sa astepte in !0 pentru o permisiune. >irul care asteapta si pri-meste o permisiune ca rezultat al unei operatii %0

nu este neaparat firul care a asteptat cel mai mult.

!entru un semafor numarator s, in orice moment de timp, urmatoarea relatie este valabila7

numarul initial de permisiuni0 ; numarul de operatii s.%0 terminate0?numarul de operatii s.!0 terminate0.

Aceasta relatie mai poarta si denumirea de invariant pentru semaforul s. Atentie ca invariant se

refera operatiile !0 si %0 terminate. $n fir care porneste o operatie !0 poate sa fie blocat in !0,deci s-ar putea ca operatia sa nu fie executata imediat. Asa ca numarul de operatii !0 terminate

poate fi mai mic decat numarul de operatii !0 incepute. !entru un semafor numarator, operatiilede tip %0 nu bloc"eaza niciodata apelantul si intotdeauna sunt terminate imediat.

%om evita sa facem referire la @valoarea semaforului s cand descriem com-portamentul

lui s, din moment ce valoarea unui semafor nu este definita clar. 'eobicei, valoarea unui semafor este data de numarul de permisiuni valabile, care este de asteptat sa fie un numar non-negativ. In

implementarea de mai sus, variabila permits reprezinta numarul de permisiuni valabile, iar

aceasta nu este niciodata negative, deci poate fi folosita ca @valoarea lui s. /u toate acestea,

acest detaliu de implementare nu este intotdeauna valabil. In alte implementari ale lui !0 si %0,variabila permits poate avea o valoare negativa cand firele asteapta o permi-siune.

/lasa countingSemaphore nu furnizeaza metode pentru accesul la valoarea unui semafor5

doar !0 si %0 sunt furnizate. /"iar daca valoarea ar fi disponibila, nu ar fi utila din moment ce poate fi modificata de o operatie !0 sau %0 imediat dupa ce aceasta a fost retrasa. 'e aceea, ne

bazam pe invariantul unui semafor pentru ai defini comportamentul. Implementarea de mai sus

defineste !0 si %0 fara sa specifice detalii despre cum se implementeaza operatia wait in !0 saucum sa fie asigurata excluderea mutuala pentru accesul variabilei parta(ate permits. <ai tarziu

vom discuta despre aceste probleme de implementare si vom prezenta imple-mentari Java si /;;

ale clasei countingSemaphore.

3. >BCBSID=A S=<A>BAD=CBD

!entru a invata cum se folosesc semafoarele este nevoie de exercitiu. 'ar exista nisteidiome si minisabaloane comune cu care semafoarele pot fi folosite pentru a rezolva problema.

Aceste sabloane sunt decrise mai (os. Decunoasterea si aplicarea acestor sabloane este primul pas

spre a intelege si a scrie programe bazate pe semafoare.

3..#. ACB/AD=A D=S$DS=CBD



/onsiderati problema in care trei fire de executie concureaza pentru doua resurse. 'aca

nici una din resurse nu este disponibila, un fir trebuie sa astepte pana cand una din resurse este

eliberata de catre alt fir. !unctul 3.# ne prezinta o solutie cu semafor pentru aceasta problema;countingSemaphore s este initializat la , unde este numarul initial de resurse disponibile.

Apelurile catre s.P() si s.V() inco(oara sectiunea de folosire a resurselor. 'aca doua fire din cele

trei folosesc resurse, al treilea fir va fi blocat cand va executa operatia s.!0. $n fir care executa ooperatie s.%0 face ca resursa sa, sa fie disponibila pentru alte fire. Asta inseamna ca un fir care

este blocat intr-o operatie s.!0 va fi deblocat cand se va executa o operatie de tip s.%0.

Invariantul semaforului s si plasarea operatiilor !0 si %0 ga-ranteaza ca nu pot exista mai multde doua operatii s.!0 terminate fara interventia unei operatii s.%0.

countingSemap"ore s05 ::doua resurse sunt valabile initial

1"read# 1"read 1"read3s.!05 s.!05 s.!05

:E foloseste resursa E: :E foloseste resursa E: :E foloseste resursa E:

s.%05 s.%05 s.%05

3.1 Alocarea resurselor folosind semafoare.

Semafoarele numaratoare sunt o solutie perfecta la problema alocarii resurselor.

Dezervorul de permisiuni reprezentat de semaforul s, indica direct catre rezervorul de resurse

administrat. 'e exemplu, daca valoarea lu s.permits este , sunt valabile resurse. <etodele !0si %0 se ocupa de toata administrarea interna necesara7 numara resurele, verifica numarul

disponibil de resurse si bloc"eaza fire cand nu exista resurse disponibile. 'in pacate, o solutie

atat de simpla nu exista pentru fiecare problema. $nele probleme cer ca operatiile de

administrare sa fie facute in afara operatiilor !0 si %0, iar semafoarele sa fie folosite pentru altelucruri pe langa administrarea resurselor.

3.. SABLOANE DE SEMAFOARE SUPLIMENTARE

=xemplul 3. prezinta o solutie alternativa la problema alocarii resurselor. Aceasta solutie

este mult mai complicata, dar ilustreaza cateva sabloane folosite mai des. In aceasta solutie,variabila parta(ata count monitorizeaza numarul de re-surse disponibile. %ariabila count este

initializata cu valoarea . /and valoarea variabilei count este mai mare decat zero, inseamna ca

exista o resursa disponibila.

%aloarea variabilei count este decrementata atunci cand o resursa este luata si incrementata cando resursa este eliberata. %ariabila parta(ata waiting monitorizea-za numarul firelor in asteptare.

/and un fir doreste sa utilizeze o resursa, verifica valoarea variabilei count. 'aca aceasta valoare

este mai mica sau egala cu zero, firul incrementeaza varibila waiting si apoi se autobloc"eazaexecutand operatia resourceAvailable.P(). /and un fir elibereaza o resursa, verifica valoarea

variabilei waiting . 'aca aceasta valoare este mai mare decat zero, un fir in asteptare este anuntat

ca exista o resursa disponibila5 in caz contrar, variabila count este incre-mentata pentru cacererile viitoare pentru resurse sa fie aprobate. Bbservam ca variabila count nu este incrementata

cand un fir in asteptare este notificat, la fel cum si count nu este decrementata dupa ce un fir in

asteptare primeste o resursa.



Acesta solutie include mai multe sabloane care apar mai des in solutii bazate pe semafoare.

Aceste sabloane se bazeaza pe invariantul semaforului si a plasarii ope-ratiilor !0 si %0 pentru a

crea sincronizarea necesara.

Semafoarele de tip ute! pot fi folosite pentru a rezolva problema sectiunii critice. $n

semafor, numit tipic mute! de la @excludere mutuala0 este initializat la #.

:: variabilele parta(ate de fire

int count 4 5 :: numarul de resurse disponibileint Faiting 4 95 :: numarul de fire in asteptare

:: furnizeaza excluderea mutuala pentru count si waiting

countingSemap"ore mutex 4 neF countingSemap"ore#05

:: folosit ca o coada de fire blocatecountingSemap"ore resourceAvailable 4 neF countingSemap"ore905

1"read i :: fiecare fir executa urmatorul cod7

mutex.!05 :: intra in sectiunea critica

if count890 :: exista o resursa disponibilaGcount--5 :: exista cu o resursa mai putin disponibila

mutex.%05 :: iese din sectiunea critica6

else

Faiting;;5 :: inca un fir in asteptaremutex.%05 :: iese din sectiunea critica

resourceAvailable.!05 :: asteapta o resursa

6

:E foloseste resursa E:mutex.!05 :: intra in sectiunea critica

if Faiting890 :: exista fire in asteptareG

--Faiting5 :: exista cu un fir mai putin in asteptareresourceAvailable.%05 :: anunta un fir in asteptare

6

else count;;5 :: returneaza o resursa in rezervor mutex.%05

6

Exemplu 3.2 Solutie alternativa la problema alocarii resurselor

B sectiune critica incepe cum un apel la mute!.P() si se termina cu un apel la mute!.V()"

mutex.!0

:E sectiune critica E:

mutex.%0

Invariantul semaforului asigura terminarea alternativa a operatiilor !0 si %0, care permit

sa existe cate un fir pe rand in interiorul sectiunii critice. In exem-plul 3., semaforul mute! este

folosit pentru a crea sectiuni critice pentru variabile-le parta(ate count si waiting.



#ntra$si$%esteaza 'eseori, un fir va intra intr-o sectiune critica si apoi va testa o conditie care

implica variabile parta(ate. In exemplul 3., testul pentru disponibili-tatea resurselor urmaresteapelul la mute!.P()"

mutex.!05if count890 :: testeaza disponibilitatea resurselor5 count este o variabila

parta(ata

...5 :: count&' inseamna ca o resursa este disponibila6

else

...5

resourceAvailable.!05 :: asteapta pentru o resursa6

B alternativa la declararea i va contine o operatie !0, pentru ca firul sa se poata

autobloca pana cand este anuntat ca a fost satisfacuta conditia. #esi$#nainte$Sa astepti $n fir care se executa in interiorul unei sectiuni critice, va iesi din ea

inainte sa se bloc"eze peste o operatie !0. #esi$#nainte$Sa asteptieste necesar din moment ce un fir care se autobloc"eaza intr-o sectiune critica poate sa creeze o

situatie de dead-loc). In exemplul 3., cand nu este nici o resursa disponibila, mute!.V() este

executat inainte de resourceAvailable.P().

mutex.%05 :: iesire din sectiunea critica

resourceAvailable.!05 :: asteapta pentru o resursa

'aca un fir nu a apelat mute!.V() pentru a iesi din sectiunea critica inainte sa apeleze

resourceAvailable.P() alte fire nu vor putea sa intre in sectiunea critica, si nu vor aparea apeluri

la resourceAvailable.V(). #esi$#nainte$Sa astepti este un sablon folositor, dar este deasemenea sisursa unor erori de programare subtile. In Sectiunea 3.H vom arata cum sa facem acest sablon

mai sigur.

*onditia Statului la *oada + $n semafor poate fi folosit ca o coada de fire care as-teapta ca oconditie sa devina adevarata. 'aca valoarea initiala a unui semafor s este zero si numarul de

operatii s.P() incepute nu este niciodata mai mic decat numarul de operatii s.V() terminate,

invariantul semaforului asigura ca fiecare operatie s.P() bloc"eaza garantat firul apelant.

Aceasta indica faptul ca s este folosit ca o coada, nu ca un contor de resurse.In exemplul 3., semaforul resourceAvailable este folosit ca o coada de fire care asteapta ca o

resursa sa devina disponibila. Semaforul resourceAvailable este initi-alizat la zero si toate

operatiile resourceAvailable.V() sunt executate cand cel putin un fir asteapta7

if Faiting890 :: daca unul sau mai multe fire asteapta

resourceAvailable.%05 :: atunci anunta un fir blocat

In aceste conditii, un apel la resourceAvailable.P() intotdeauna va bloca firul apelant, iar un apel

la resourceAvailable.V() intodeauna va debloca un fir in asteptare. Aceste sabloane reprezinta



baza in construirea solutiilor bazate pe semafoare. %om vedea aceste sabloane si alte cateva

folosite de-a pe parcusul exemple-lor din sectiunea 3..

3.3 SEMAFOARE BINARE SI ZAVOARE

Sablonul cu mute! este cel mai folosit sablon cu semafor si merita studiat in detaliu. $nsemafor numit mute! este initializat cu valoarea #. Apelurile la mute!.P() si mute!.V() creeaza o

sectiune critica &'i()stra #*+7

1"read# 1"read

mutex.!05 mutex.!05 :E sectiune critica E: :E sectiune critica E:

mutex.%05 mutex.%05

'atorita valorii initiale # a mute!$ului si a plasarii lui mute!.P() si mute!.V() in (urul sectiuniicritice, o operatie mute!.P() va fi terminata prima, apoi mute!.V() si apoi mute!.P() si tot asa

mai departe. !entru acest sablon, putem lasa mutexul sa functioneze ca un semafor numarator,sau putem folosi un tip de semafor mai re-strictiv numit semaor binar.

$n semafor binar trebuie initializat cu valoarea # sau 9, iar terminare operatiilor !0 si

%0 trebuie sa alterneze. Atentie ca operatiile !0 si %0 pot fi pornite in orice ordine, dar terminarea lor trebuie sa fie alternativa.0. 'aca valoarea initiala a semaforului este #, care este

cazul sectiunilor critice, prima operatie care trebuie terminata este !0. 'aca o operatie %0 este

incercata intai, aceasta va bloca apelantul ei. Similar, daca valoarea initiala a semaforului este

9, prima operatie teminata trebuie sa fie de tip %0. 'eaceea, operatiile !0 si %0 ale unuisemafor binar pot bloca firele apelante. Amintiti-va sa semafoarele numaratoare au operatia !0

de blocare, dar operatia %0 nu bloc"eaza niciodata firul care o apeleaza.

$n al treilea tip de obiect de sincronizare se numeste zavor mute! sau mai simplu zavor poate fi folosit pentru a rezolva problema sectiunii critice.

Zavoarele asigura excluderea mutuala dar nu si conditia de sincronizare0. Bpera-tiile aplicate

unui zavor se numesc loc,() si unloc,(). Sablonul ute! pentru zavoa-re si semafoare arata lafel7

mutexCoc) mutex5

1"read# 1"readmutex.loc)05 mutex.loc)05

:E sectiune critica E: :E sectiune critica E:

mutex.unloc)05 mutex.unloc)05

Spre deosebire de un semafor, un zavor are un detinator, iar aceasta proprietate de a fi detinut

(oaca un rol important in comportamentul unui zavor7

• $n fir trimite o cerere de detinere a zavorului C, apeland -.loc,().

• $n fir care apeleaza -.loc,() devine detinatorul daca zavorul nu este detinut de alt fir5

contrar, firul este blocat.



• $n fir elibereaza detinerea lui C apeland -.unloc,(). 'aca firul nu il detine pe C, apelul la

-.unloc,() genereaza o eroare.

• $n fir care detine de(a zavorul C si apeleaza -.loc,() din nou, nu este blocat. 'e fapt, este

normal pentru un fir sa ceara si sa primeasca detinerea unui zavor care de(a il detine. 'ar firul detinator trebuie sa apeleze -.unloc,() de acelasi numar de ori care a apelat -.loc,()

inainte ca alt fir sa devina detina-torul lui C.• $n zavor care permite firului de care este detinut sa fie blocat din nou se numeste zavor

recursiv.

Zavoarele sunt folosite deobicei in metodele claselor. Acest lucru este ilustrat de urmatoareaclasa7

class loc)ableBb(ect public void >0

mutex.loc)05

...5

mutex.unloc)056

public void 0

mutex.loc)05...5 >05 ...5 :: metoda () apeleaza metoda /()

mutex.unloc)05

6 private mutexCoc) mutex5

6

Zavorul mute! in cadrul clasei loc,able0bject este folosit pentru a transforma metodele >0 si

0 in sectiuni critice. 'eaceea, doar un singur fir la un moment-dat poate fi executat in cadrulmetodei loc,able0bject. /and un fir apeleaza meto-da 0, mutex-ul este blocat. /and metoda

0 apeleaza metoda >0, mute!.loc,() este executat in >0, dar firul apelant nu este blocat dinmoment ce de(a detine mute!-ul. 'aca mute! ar fi fost un semafor binar in loc de zavor, apelul

de la 0 la >0 ar fi blocat firul apelant cand mute!.P() era executat in >0. Amintitiva ca

terminarea operatiilor !0 si %0 intr-un semafor binar trebuie sa alterneze.0 Aceasta ar crea osituatie de deadloc) din moment ce nici un alt fir nu poate fi executat in cadrul lui >0 sau 0.

=xista cateva diferente intre zavoare si semafoare binare7

• !entru un semafor binar, daca sunt facute doua apeluri la !0 fara interventia unui apel la

%0, al doilea apel va bloca. 'ar un fir care detine un zavor si trimite o cerere de detineredin nou nu este blocat. atentie deoarece zavoare-le nu sunt intotdeauna recursive, deci

consultati documentatia inainte de a folosi un zavor.0

• 'etinatorul pentru apelurile succesive la loc,() si unloc,() trebuie sa fie acelasi fir. 'ar

apelurile succesive la !0 si %0 pot fi facute de fire diferite.



'in moment ce zavoarele sunt mai flexibile cand vorbim de apelarea metodelor, vom folosi

deobicei zavoare in loc de semafoare pentru a crea obiecte blocabile. /u toate acestea vom

intampina situatii unde nu este posibila folosirea zavoare-lor fara violarea restrictiilor privinddetinerea. In aceste situatii, folosim semafoare binare sau numaratoare.

1raducere /apitolul 3.H7

Implementare Semafoare7

!roblema Semafoarelor poate fi implementata la nivel utilizator, la nivelul sistemului de

operare,sau cu suport "ardFare. 2u exista sisteme de operare sau limba(e de programare care sa

suporte reluarea programului prin semafoare. In aceasta sectiune vom discuta despre cum sa

implementam semafoare. <ai tarziu vom prezenta implementari ale semafoarelor la nivel

utilizator in limba(ul Java si /;;:Win3:!t"reads. 'e asemenea vom arata cum acesteimplementari pot fi extinse pentru a suporta urmarirea executiei si reluarea acesteia, si o te"nica

interesanta de testare.

3.H.#

Implementarea !0 si %0

!unctele 3.3 si 3.H arata cateva posibile implementari ale operatiilor realizate de !0 si %0.

Aceste implementari ilustreaza mecanisme variate pentru blocare si deblocare firelor de executie.

Implementarile # si in Cistingul 3.3 sunt pentru operatiile de numarare ale semafoarelor !0 si

%0. Aceste implementari difera in functie de cum manipuleaza operatia Fait, in !05

Implementarea # foloseste ocupat-asteptand pentru a intarsia firele de executie. /and un fir de

executie in asteptare este activate in !0, el trebuie sa reverifice valorile permisiunilor. = posibil

ca un fir de executie activ va gasi mereu o valoare a permisiunilor egala cu 9 si deci nu va fi

permis niciodata ca !0 sa isi termine operatia. Semafoarele cu astfel de implementare se numesc

semafoare slabe.

Implementarea bloc"eaza firele de executie in asteptare intr-o coada pana cand acestea sunt

c"emate. Klocand firele de executie evitam ca /!$ sa consume cicluri, dar necesita suport de la

limba(ul de programare sau sistemul de operare. /and un fir de executie blocat in !0 este activat

de o operatie din %0 , firului de executie ii va fi permis sa isi executa operatia !0. Aceasta

implementeaza un semafor puternic.

I<!C=<=21AD=A # >BCBS=S1= B/$!A1-AS1=!1A2'



I<!C=<=21AD=A SEMAFOARE 93

// I<!C=<=21AD=A # >BCBS=S1= S=<IB/$!A1-AS1=!1A2'

!07 F"ile permits 44 90

Sleep..05

6

permits 4 permits - #5

%07 permits 4 permits ; #5

:: Implementarea foloseste o coada de fire de executie blocate5 permisiunile pot fi negative5

!07 permits 4 permits - #5

if permits L 90 asteapta intr-o coada de fire de executie blocate pana esti anuntat.

%07 permits 4 permits ; #5

if permits L4 90 anunta un fir de executie in asteptate

Cisting 3.3 Implemetarea lui P() si V() pentru numararea semaoarelor.

Implementarea 3foloseste cozi de fire de executie blocate.%0poate bloca firul de executie

c"emat.

!07 if permits 44 90

asteapta intr-o coada de fire de executie blocate pana esti anuntat.

permits 4 95

if coada firelor de executie blocate in %0 nu e goala0

anunta un fir de executie blocat in %05

%07 if permits 44 #0

asteapta intr-o coada de fire de executie blocate pana esti anuntat.

permits 4 #5

if coada firelor de executie blocate in !0 nu e goala0



anunta un fir de executie blocat in !05

Li!i"# 3.$ Implementarea lui P() si V()pentru semaoare binare.

Implementarea 3 in Cisting 3.H este pentru semafoare binare. In Implementarea

3, un fir de executie ce executa s.V() intr$un semaor binar blocat.

if permits are valoarea 1. /onform cu aceasta implementare, invariantul pentru un semafor

binarM este urmatorul7

(( valoarea initiala a lui s ( care e 9 sau # ))

; ( numarul de operatii complete s.V ())

; ( numarul de operatii complete s.P ())' sau 1

<ulte carti care definesc semafoarele binare nu explica clar daca operatia %0 este blocanta sau

nonblocanta. In aceasta carte noi folosim operatia %0 blocanta. /lasa Java binarMSemap"ore

presentata mai tarziu este bazata pe Implemenatarea 3.

B implementare a lui !0 si %0 trebuie sa asigure ca excluderea reciproca are loc cand variabilele

puse in comun si cozile din implementare sunt accesate. 'e exemplu Implementarea # in Cisting

3.3. !resupunem ca valoarea permisiunilor 4#. 'aca mai multe fire de executie executa o

operatie !0 in aproximativ acelasi timp,unul din firele de executie ar trebui sadecrementeze

persmisiunile la 9, iar celelalte ar trebui sa astepte. Implemetarile lui !0 si %0 pot rezolva

aceasta critica problema a n-fire de executie pentru permisiuni ale variabilelor puse in comun,

folosind una dintre solutiile discutate in capitolul .

!07 entrM-section5F"ile permits 44 90

exit-section5

5 :: null-statement

entrM-section565

permits 4 permits - #5exit-section5%07 entrM-section5

permits 4 permits ; #5

exit-section5

Ope%&!iile !0 si %0 sunt acum operatii atomice.



Alte solutii la problema critica pot fi folosite in implementarea operatiilor !0 si %0 daca acestea

sunt disponibile.

Java ofera o solutie ce este similara cu blocarea mutex mentionata in sectiunea 3.3.

Kloca(ele Java sunt folosite in implementarile Java de semafoare prezentate in Sectiune 3.+.Implemetarile semafoarele ce au fost prezentate pana acum pot fi implementate la nivel

utilizator. Semafoarele pot fi implementate si la nivel sMstem de operare. Cisting 3. arata

implemetarea operatiilor !0 si %0 ca operatii in nucleul sistemului de operare. Sunt create

sectiuni critice activand si dezactivand intreruperi. !entru o masina multi processor cu s"ared

memorM, dezactivarea intreruperilor poate sa nu functioneze, asa ca instructiuni "ardFare

atomice ca cele descries in Sectiunea .3 pot fi folosite. &AndreFs 999 descrie cum se

implementeaza semafoare in nucleul sistemului de operare.

3.$.2

VP'( Ope%&!i)"

B operatie semafor in plus pe care o folosim in aceasta carte este operatia %!0.

In loc sa scriem7

s.%05 t.!05

!s07 disable interrupts5

permits 4 permits - #5

if permits L 90

add t"e calling t"read to t"e Nueue for s and c"ange its state to bloc)ed5

sc"edule anot"er t"read5

6

enable interrupts5

%s07 disable interrupts5

permits 4 permits ; #5

if permits L4 90

select a t"read from t"e Nueue for s5 c"ange t"e t"readOs state to readM5



6

enable interrupts5

Li!i"# 3.Impleme"!&%e& lui P() i V()in nucleul unui system de operare.

.

/ombinam operatiile separate %0 si !0 intr-o singura operatie atomica %!07

t.%!s05

B executie a t,%!s0 este ec"ivalenta cu s.%05t.!0, cu excepia faptului ca in timpul executiei lui

t.%!s0 nici o operatie de intervenire !0 , %0, %!0 nu este permisa a fi pornita in s si t.

!unem restrictia ca t.%!s0 poate fi folosit doar in cazurile in care operatie %0 in s nu poate

bloca firul de executie c"emat. Aceasta inseamna ca s este un semafor de numarare sau s este un

semafor binar ce garantat este intr-o stare in care operatia %0 nu va fi blocata. >olosim operatia

%!0 mai mult in capitolul H, unde datorita cazului particular pentru care folosim operatia %!0

aceasta restrictie garantat este satisfacuta mereu.

/onsideram urmatorul fragment7

binarMSemap"ore t905

1"read # 1"read

s.%05 t.!05

t.!05

Sa presupunem ca imediat dupa 1"readul # se executa o operatie s.%0. =ste posibil ca operatia

t.!0 in 1"read-ul va fi executata inainte de executia t.!0 din 1"readul #. !e de alta parte, daca

t.%!s0 este folosit in 1"read #, este posibila o sc"imbare de context dupa partea s.%0 a

operatiei %!0 , dar partea t.!0 a operatie %!0 garantat va bloca 1"read # inainte ca operatia

t.!0 sa bloc"eze 1"read-ul .

B sc"imbare de context succesiva intre operatiile %0 si !0 este deseori o sursa de erori subtile.

B operatie %0 urmata de o operatie !0 apare in modelul iesire inainte de asteptareexit-before-

Fait0.



mutex.%0 5 ::sectiunea iesire de urgenta5

some/ondition.!05 ::asteapta pana o conditie e adevarata

$n fir de executie 10 ce executa mutex.%0 elibereaza excluderea reciproca. 1otusi alte fire de

executie pot intra in sectiunile lor critice si sa isi execute functiile lor mutex.%0 si

some/ondition.!0. Aceasta poate crea o problema, care e deseori sub forma unui punct mort. B

solutie ec"ivalenta ce nu foloseste modelul exit-before-Fait poate fi dificil de gasit. Bperatia

%!0 elimina aceste tipuri de erori si, cum vom vedea in capitolele viitoare, %!0 se va dovedi

a(utator in construirea claselor ce suporta testare si depanare.

Implementarea lui t.%!s0 e o combinatie de implementari ale %0 si !0 cu o complicatie7

excluderea reciproca trebuie obtinuta pentru ambele semafoare s si t cand operatia %!0 incepe.

Aceasta e necesar pentru a preveni alte operatii s si t sa se completeze cat timp operatia %!0 este

in progres. Bricum, bloca(ul lui s si t trebuie facut cu gri(a pentru a evita punctul mort.

B implemetare a %!0 este aratata in Sectiunea 3.+

3.* SOLUTII PENTRU PROBLEME DE PRO+RAMARE ,ON,URENTE BAZATE PE

SEMAFOARE.

In aceasta sectiune prezentam solutii la diferite probleme clasice de sincronizare.

Aceste probleme au fost dezvoltate pentru a demonstra ca un constructor particular de

sincronizare poate fi folosit pentru a rezolva o problema de sincronizare frecvent aparuta.

3.*.1

Brdonarea =venimentelor

!resupunem ca segmental de cod /# din firul de executie 1PD=A' # trebuie sa fie executat

segmental de cod / din firul de executie 1PD=A' . !unem s ca fiind un semafor de numarare

initializat cu 9.

T-READ 1 T-READ 2

.P'( ,2

,1 .V'(



Bperatia s.!0 va bloca 1PD=A' # pana cand 1PD=A' isi va executa operatia s.%0 . Aceasta

garanteaza ca segmental de cod /# este executat dupa /.

3.*.2

Kuffer-e delimitate

!roblema bufferelor delimitate &'i()stra #*+ a fost prezentata in /apitolul #.

$n buffer delimitat are n sloturi. >iecare slot este folosit pentru a stoca un item.

Itemurile sunt depozitate in buffer de un singur producator si extrase din buffer de un singur

consumator. $n producator nu poate depune un item cand toate sloturile sunt pline. $n

consumator nu poate extrage un item cand toate sloturile sunt goale.

int buffer& 4 neF int&n5

countingSemap"ore emptMSlotsn05

countingSemap"ore fullSlots905

!roducer

int in 4 95

int item5

...

:E produce item E:

emptMSlots.!05 :: Fait if t"ere are no emptM slots

buffer&in 4 item5 :: in is t"e index for a deposit

in 4 in ; #0 Q n5 :: 9 R in L n5 and in 4 out;items in buffer0Qn

fullSlots.%05 :: signal t"at a slot Fas filled

...

6

/onsumer



int out 4 95

int item5

fullSlots.!05 :: Fait if t"ere are no full slots

item 4 buffer&out5 :: out is t"e index for a Fit"draF

out 4 out ; #0 Q n5 :: 9 R out L n

emptMSlots.%05 :: signal t"at a slot Fas emptied

:E consume item E:

6

Li!i"# 3. Kounded buffer using semap"ores.

Solutia din problema buffer -delimitat prezentata in Cisting 3.+ foloseste doua semafoare de

numarare pentru conditia de sincronizare. Semafoarele fullSlots si emptMSlots sunt folosite ca

numaratoare de resurse, numarand sloturile pline si goale, respectiv din buffer.

countingSemap"ore fullSlots 4 95 :: numarul sloturilor pline

countingSemap"ore emptMSlots 4 n5 :: numarul sloturilor goale



/onditia numarul sloturilor pline; numarul sloturilor goale 44n0 este adevarata inainte si dupa

fiecare operatie de depunere si extragere. !roducatorul depune itemuri in slotul buffer&in si

consumatorul extrage itemi din slotul buffer&out. /um in si out nu pot avea aceleasi valori cand

bufferul este accesat, nu e necesara nici o sectiune de urgenta pentru accesarea sloturilor din

buffer.

3..3

<asa filozofilor.

=xista n filozofi ce isi petrec timpul mancand si gandind. =i stau la o masa cu n locuri. $n bol

cu orez se alfta in mi(locul mesei. =xista un betigas intre fiecare perec"e de filozofi. /and un

filozof este flamand el ia cele betigase ce se afla langa el la un moment dat. /and a luat

betigasele, le tine pana cand a terminat de mancat. Apoi lasa betigasele cate unu pe rand si incepe

sa gandeasca.

Solutiile pentru masa filozofilor nu trebuie sa contina puncte moarte sau vreunul din filozofi sa

fie flamand. B situatie clasica de punct mort este create in solutii ce implementeaza o politica de

tip "old-and TFait. Aceasta politica permite unui filozof sa tina un betigas, la care nu doreste sa

renunte, cat timp asteapta celalalt betigas.

In general punctele moarte pot fi evitate prin oprirea firelor de executie de la a retine resurse cat

timp asteapta altele. Aceasta poate fi realizata prin punerea unui fir de executie blocat sa dea

inapoi resursele sale astfel incat celelalte fire va avea destul sau prin fortarea unui fir de executie

sa ceara toate resursele necesare odata sau prin ordonarea cererilor de resurse in asa fel incat safie prevenit punctul mort.

In ciuda eforturilor noastre, puncte moarte pot totusi avea loc, caz in care detectia punctelor

moarte devine importanta. In Sectiunea 3..H este descrisa o metoda de detectie a punctelor

moarte ce este scrisa in clasele noastre cu bloca(e si semafoare.

B proprietate in plus, numita paralelism maximal poate fi de asemenea necesara.

Aceasta proprietate e satisfacuta de o solutie ce permite unui filozof sa manance atat timp cat

vecinii lui nu mananca. Aceasta cerinta e incalcata in situatiile "old-and-Fait, unde filozofii

vecini, tin fiecare cate un betigas si nu pot manca.

Solutia #7

In solutia din Cistin 3.U toti n filozofii isi iau betigasele in aceeasi ordine. >iecare betigas e

reprezentat de un semafor binar, ce serveste ca un simplu numarator de resurse ce e initializat cu

#. A lua un betigas e implementat ca o operatie !0, iar eliberarea unui betigas ca o operatie %0.



!entru un program cu filozofi , ar fi posibila executarea urmatoarei secvente7

P0il))p0e% )mple!e chopsticks[0].P() &" 0& & )"!ex! 4i!0.

P0il))p0e% 1 )mple!e chopsticks[1].P() &" 0& & )"!ex! 4i!0.



P0il))p0e% $ )mple!e chopsticks[4].P() &" i 5l)6e &! chopstick[0].P().

E&0 )7 p0il))p0e% 8 18 28 &" 3 %eume exeu!i)" &" i 5l)6e )"

0e% "ex! P() )pe%&!i)".

Acum toti cei filozofi sunt blocati. Are loc un punct mort global, cat timp fiecare filozof isi tine

betigasul stang si asteapta pentru totdeauna pentru betgigasul drept.

binarMSemap"ore c"opstic)s& 4 neF binarMSemap"ore&n5

for int ( 4 95 ( L n5 (;;0 c"opstic)s&( 4 neF binarMSemap"ore#05

p"ilosop"erint i :E 9..n-# E:0

F"ile true0

:E t"in) E:

c"opstic)s&i.!05 :: pic) up left c"opstic)

c"opstic)s&i;#0 Q n.!05 :: pic) up rig"t c"opstic)

:E eat E:

c"opstic)s&i.%05 :: put doFn left c"opstic)

c"opstic)s&i;#0 Q n.%05 :: put doFn rig"t c"opstic)

6

6



Li!i"# 3. 'ining p"ilosop"ers using semap"ores7 Solution #.

S)lu!i& 2.

Aceasta solutie e asemanatoare solutiei # doar ca la o masa cu n locuri au voie sa stea doar n-#

filozofi. $n semafor denumit @locuri cu valoare initiala n-# este folosit ca si numarator de

resurse pentru a numara numarul de locuri valabile. >iecare filozof executa seats.!0 inainte de a

lua betigasul stang si seats.%0 inainte de a apuca betigasul drept. Aceasta solutie nu satisface

paralelismul maximal atat timp cat e posibil ca doi vecini sa tina un betigas dar sunt nevoitori in

a se lasa unul pe celalalt sa manance. =xista betigase indea(uns pentru fiecare filozof, dar de fapt

doar unul mananca.0 Aceasta solutie este fara bloca(e. 'aca sunt folosite semafoare cu

>/>Sfirst come first serve0, operatii !0 si %0 aceasta solutie este si fara starvationnici un

filozof nu ramane nemancat0.

S)lu!i& 3.

Aceasta soilutie e asemanatoare solutiei unu doar ca un filozof e desmnat ca fiind filozoful

@impar. >ilozoful impar ia prima data betigasul din partea dreapta in loc sa il ia pe cel din

stanga0. Aceasta solutie e fara bloca(e. 'aca sunt folosite semafoare cu >/>Sfirst come first

serve0, operatii !0 si %0 aceasta solutie este si fara starvationnici un filozof nu ramane

nemancat0.

S)lu!i& $.

In solutia din Cistingul 3. un filozof ia un betigas numai daca ambele sunt disponibile. >iecare

filozof are trei stari posibile7 gandire, foame, mancandt"in)ing, "ungrM, eating0

$n filozof ce ii este foame poate manca doar daca cei doi vecini ai sai nu mananca. 'up ace

mananca, un filozof debloc"eaza un vecin al sau ce ii este foame.

Aceasta solutie e fara bloca(e, si satisface paralelismul maximal, dar pot ramane filozofi in stare

de starvationinfometati0.

$n filozof va infometa daca atunci cand vecinul sau termina de mancat si bune betigasele (os, le

va lua vecinul din partea cealalta.

Aceasta sc"ema poate fi extinsa pentru a preveni infometarea c"iar daca semafoarele nu sunt de

tip >/>S.

Dezolvarea solutie se afla in operatia self&).%0 in functia test0. %ectorul self& este un vector de

semafoare folosit pentru a bloca filozofii care sunt in situatia de a nu putea manca.



final int t"in)ing 4 95 final int "ungrM 4 #5 final int eating 4 5

int state& 4 neF int&n5

for int ( 4 95 ( L n5 (;;0 state&( 4 t"in)ing5

:: mute! provides mutual exclusion for accessing state23.

binarMSemap"ore mutex 4 neF binarMSemap"ore#05

:: p"ilosop"er i bloc)s "erself on sel2i3 F"en s"e is "ungrM but unable to eat

binarMSemap"ore self& 4 neF binarMSemap"ore&n5

for int ( 4 95 ( L n5 (;;0 self&( 4 neF binarMSemap"ore905

p"ilosop"erint i :E 9..n-# E:0

F"ile true0

:E t"in) E:

mutex.!0

state&i 4 "ungrM5

testi05 :: performs sel2i3.V() if p"ilosop"er i can eat

mutex.%05

self&i.!05 :: sel2i3.P() Fill not bloc) if sel2i3.V() Fas

:E eat E: :: performed during call to test(i)

mutex.!05

state&i 4 t"in)ing5

testn ; i - #0 Qn05 :: unbloc) left neig"bor if s"e is "ungrM and can eat

testi ;#0 Qn05 :: unbloc) rig"t neig"bor if s"e is "ungrM and can eat

mutex.%05

6

6

void testint ) :E 9..n-# E:0



:: p"ilosop"er i calls test(i) to c"ec) F"et"er s"e can eat.

:: p"ilosop"er i calls test ((n 4 i $ 1) 5 n0 F"en s"e is finis"ed eating to

:: unbloc) a "ungrM left neig"bor.

:: p"ilosop"er i calls test((i 4 1) 5 n0 F"en s"e is finis"ed eating to

:: unbloc) a "ungrM rig"t neig"bor.

if state&) 44 "ungrM0 VV state&);n-#0 Q n0 4 eating0 VV

state&);#0 Q n 4 eating00

state&) 4 eating

self&).%05 :: unbloc) p"ilosop"er iOs neig"bor, or guarantee

6 :: t"at p"ilosop"er i Fill not bloc) on sel2i3.P().

6

Li!i"# 3.: 'ining p"ilosop"ers using semap"ores7 Solution H.

>ilozoful I se bloc"eaza singur in semaforul self&i cand ii este foame dar in imposibilitate de a

manca. !rima c"emare a filozofului i in functia test0 este de a verifica daca vecinii sai mananca.

'aca nici un vecin nu mananca filozoful i executa self&i.%0 in functia test0.

/um doar filozoful I executa operatia !0 in self&i , si cum filozoful i evident nu este blocat in

semaforul self&i atat timp cat executa self&i.%0, nici un fir de executie nu va fi deblocat de

aceasta operatie %0. <ai mult, cum self&i e initializat cu 9 aceasta operatie %0 nu se bloc"eaza

si filozofului i ii este permis sa continue. Scopul acestei operatii %0 nu este clar pana cand nu

observam ca filozoful I imediat dupa aceea executa self&i.!0, care datorita operatiei %0 ce

tocmai a fost executata se garanteaza non-bloca(.

'aca unul sau ambii vecini ai folozofului i mananca cand functia test e c"emata

self&i.%0 nu este executata, cauzand bloca(ul filozfului i cand executa self&i.!0.



/elelate doua c"emari ale clasei test0 pe care le face filozoful I sunt facute pentru a

debloca vecinii carora le este foame si sunt capabili si manance dupa ce filozoful i termina de

mancat.

3.*.$ ,i!i!)%i i S%ii!)%i

'atele sunt puse in comun de multiple fire de executie. /and un fir de executie citestescrie0

datele puse in comun , este considerat a fi un cititorscriitor0.

/ititorii pot accesa datele puse in comun in mod concurrent, dar un scriitor are intotdeauna acces

exclusiv. 1abela 3.# arata sase strategii diferite pentru a controla cum cititorii si scriitorii primesc

prioritate cand ambii doresc sa acceseze in acelasi timp datele puse in comun.

#. D4W scriitorii si cititorii au prioritate egala si sunt serviti impreuna dupa metoda

>/>Sprimul venit primul servit0. D8W cititorii au in general prioritate mai mare decat scriitorii

3. DLW cititorii au in general prioritate mai mica decat scriitorii<ai multe strategii exista pentru fiecare categorie datorita sc"imbarilor de prioritati in situatii

specifice.

TABLE 3.1

A,,ES STRATE+; DES,RIPTION

D4W.#$n cititor sau un scriitor cu prioritate egala.

D4W <ai multi cititori sau un scriitor cu prioritate egala

D8W# <ai multi cititori sau un scriitor5 scriitori au prioritate mai mare D8W

Ca fel ca D8W# cu exeptia ca atunci cand soseste un cititor, daca

nici un alt cititor nu citeste sau asteapta, se asteapta pana cand

toti scriitorii care au sosit mai devreme au terminat

DLW# <ai multi cititori sau un scriitor cu scriitorul avand prioritate mai

mare

DLW Ca fel ca DLW# cu exeptia ca atunci cand soseste un scriitor, daca

nici un alt scriitor nu scrie sau asteapta, se asteapta pana cand

toti cititorii care au sosit mai devreme au terminat



In strategiile DLW# si DLW, scriitorii vor infometa daca inaintea unui grup de cititori

care au terminat de citit exista mereu alti cititori care vor sa citeasca.

In strategiile D8W.# si D8W. cititorii vor infometa daca inaintea unui grup de scriitori

care au terminat de scris exista mereu alti scriitori care vor sa scrie.

In strategiile D4W.# si D4W. nici un scriitor sau cititor nu va infometa.

>igura 3.* compara strategiile DLW# si DLW. Acest scenario contine evenimente

pentru doi cititori si doi scriitori. In partea umbrita sus /ititorul #, /ititorul si Scriitorul

executa o cerere dupa ce Scriitorul # termina de scris.

'upa linia punctata scenariul e completat folosind cele doua strategii diferite.

!entru strategia DLW# Scriitorul scrie inainte ca cititorii sa citeasca.

!entru strategia DLW ambiilor cititori le este permis sa citeasca inainte ca Scriitorul sa

inceapa sa scrie. Strategia DLW cere Scriitorului sa astepte &ana cand cititorii sositi mai

devreme termina de citit, pe cand Scriitorul a cerut sa scrie atunci cand nici un alt scriitor nu

scria sau astepta. !resupunem ca evenimentele de cerere multipla pot avea loc inainte ca o

decizie sa fie luata in privinta de a permite unui scriitor sau cititor sa inceapa. Aceasta

presupunere e importanta pentru a putea distinge diferite strategii.

>igura 3.#9 compara strategiile D8W# si D8W. Acest scenario contine evenimente

pentru trei scriitori si un cititor. In partea umbrita sus, /ititorul #, Scriitorul si Scriitorul 3

executa o cerere in timp ce Scriitorul # scrie.

!entru strategia D8W#,/ititorul # citeste inainte ca scriitorii sa scrie.

!entru strategia D8W, Ambilor scriitori le este permis sa scrie inainte ca /ititorul # sa

inceapa.Aceasta se intampla deoarece /ititorul # a cerut sa citeasca cand nici un alt cititor nu

citea sau astepta, asa ca /ititorul # trebuie sa astepte pana cand scriitorii care au sosit mai

devreme termina de scris.

In solutia noastra la problema /ititori si Scriitori firele de executie executa operatiile

Dead0 si Write0 dupa forma urmatoare7

Dead0 Write0

entrM-section entrM-section



read Frite

exit-section exit-section

6 6

Sectiunile de intrare si iesire implementeaza una din strategiile din tabelul 3.#

<ai (os se arata implementarea pentru 3 dintre strategii.

D8W#

Aceasta strategie da cititorilor o prioritate mai mare decat scriitorilor si poate cauza

infometarea scriitorilor ce asteapta. In Cistening 3.## folosirea semafoarelor ofera excludere

reciproca pentru operatiile Dead0 si Write0 , cat timp semafoarele

DeadersXNue si WritersXNue implementeaza /ondition Yueue din Sectiunea

3.2.2

Writer# Writer Writer3 Deader#



Fi#u%& 3.1 ,)mp&%&%e& !%&!e#iil)% R<=.1 i R<=.2



Ca sfarsitul operatiei de scriere , cititorii in asteptare au prioritate. 'aca cititorii asteapta in

readersXNue , unul dintre ei este semnalat. Acest prim cititor verifica daca vreun alt cititor asteapta. 'aca se intampla asa, atunci anunta al doilea cititor, ce il anunta pe al treilea, si tot asa.

Aceasta notificare in cascada continua pana cand nici un cititor nu mai asteapta. 'aca nici un

cititor nu asteapta cand a terminat un scriitor, este notificat un scriitor.

Aceasta implementare ilustreaza un alt model important de semafor, numit passing-t"e-

baton. Aveti in vedere ca cititorii intarziati si scriitorii, ies din sectiunile lor critice inainte de a se

bloca singuri in readersXNue.!0 sau FritersXNue.!0. Aceasta e parte din modelul iesi inainte de a

astepta mentionat mai devreme.

int activeDeaders 4 95 :: number of active readers

int activeWriters 4 95 :: number of active Friters

int FaitingWriters 4 95 :: number of Faiting Friters

int FaitingDeaders 4 95 :: number of Faiting readers

binarMSemap"ore mutex 4 neF binarMSemap"ore#05 :: exclusion

binarMSemap"ore readersXNue 4 neF binarMSemap"ore905 :: Faiting readers

binarMSemap"ore FritersXNue 4 neF binarMSemap"ore905 :: Faiting Friters

s"ared'ata x ... 5 :: x is s"ared data

Dead0 Write0

mutex.!05 mutex.!05

if activeWriters 8 90 if activeDeaders 8 9

activeWriters 8 9 0

FaitingDeaders;;5 FaitingWriters;;5

readersXNue.%!mutex05 FritersXNue.%!mutex05

6 6

activeDeaders;;5 activeWriters;;5



if FaitingDeaders 8 90 mutex.%05

FaitingDeaders--5

readersXNue.%05 67 write ! 76

6else mutex.!05

mutex.%05 activeWriters--5

if FaitingDeaders 8 90

67 read ! 76 FaitingDeaders--5

readersXNue.%05

mutex.!05 6

activeDeaders--5 else if FaitingWriters 8 90

if activeDeaders 44 9 VV FaitingWriters--5

FaitingWriters 8 90 FritersXNue.%05

FaitingWriters--5 6

FritersXNue.%05 else

6 mutex.%05

else 6

mutex.%05

6

Li!i"# 3.11 StrategM D &W.#.

Bricum , dupa ce aceste fire de executie intarziate sunt semnalate, ele niciodata nu executa

mutex.!0 pentru a reintra in sectiunea critica. 'e aceea ne asteptam ca cititorii sa execute 7

readersXNue.%!mutex05 :: exit t"e critical section

:: mute!.V()0 and readers89ue.P()0

mutex.!05 :: reenter t"e critical section before continuing



dar operatia mutex.!0 lipseste. !entru a intelege de ce nu e nevoie de aceasta operatie, a(uta sa

ne gandim la excluderea reciproca ca la un baston ce e trecut din fir in fir de executie. /and un

fir de executie in asteptare e notificat, primeste bastonul de la firul de executie ce a notificat.

!osesia bastonului da permisiunea firului de executie de a se executa in sectiunea sa critica. /and

acel fir de execute notifica un alt fir in asteptare, bastonul este pasat din nou. /and nu mai sunt

fire de executie in asteptare o operatie mutex.%0 este executata pentru a eliberea excluderea

reciproca si a se intra in sectiunea critica pentru prima data.

Aceasta te"nica e implementata folosind o instructiune if, ca aceea folosita in notificarea in

cascada de la cititori.

if FaitingDeaders 8 90 :: if anot"er reader is Faiting

FaitingDeaders--5

readersXNue.%05 :: t"en pass t"e baton to a reader i.e., do not

:: release mutual exclusion0

6

else

mutex.%05 :: else release mutual exclusion

/and un un cititor in asteptare este notificat, primeste excludere reciproca pentru a accesa

variabilele puse in comun activeDeaders si FaitingDeaders. 'aca un alt cititor asteapta, bastonul

e pasat la celalalt cititor. 'aca nici un alt cititor nu asteapta excluderea reciproca e eliberata demutex.%0.

D8W. Aceasta strategie permite citirea concurenta si in general da cititorilor o mai mare

prioritate decat scriitorilor. Scriitorii au prioritate in urmatoarea situatie7

/and un cititor cere sa citeasca, daca este un cititor liderexemplu7nici un alt cititor nu

citeste sau asteapta sa citeasca0, el asteapta pana cand toti scriitorii care au sosit mai devreme

termina de scris.Aceasta strategie poate cauza infometarea scriitorilor. In listingul 3.# cand un

cititor D executa Dead07

'aca unul sau mai multi cititori citesc, D incepe sa citeasca imediat

'aca unul sau mai multi cititori asteapta ca scriitorii sa scrie, D este blocat in

mutex

'aca nici un cititor nu citeste sau nu asteapta, D este un cititor lider asa ca r

executa FritersXrXNue.!0 inainte ca D sa o faca. Altfel D poate incepe sa citeasca si scriitorii vor

fi blocati cand vor executa FritersXrXNue.!0.



/and se termina o operatie Write0 semaforul FritersXrXNue este notificat. Scriitorii in

asteptare care au sosit inaintea cititorului lider vor fi inaintea cititorului in coada pentru

FritersXrXNue5deci cititorul lider va trebui sa astepte ca acesti scriitori sat ermine de scris.


mutexCoc) mutex 4 neF mutexCoc)05 :: mutual exclusion for active:eaders

:: condition Nueue for Faiting Friters and t"e first Faiting reader

binarMSemap"ore FritersXrXNue 4 neF binarMSemap"ore#05


Dead0

mutex.loc)05 :: bloc) readers if lead reader Faiting in writers8r89ue

;;activeDeaders5

if activeDeaders 44 #0

FritersXrXNue.!05 :: bloc) lead reader if a Friter is Friting

mutex.unloc)05

67 read ! 76

mutex.loc)05

--activeDeaders5

if activeDeaders 44 90

FritersXrXNue.%05 :: alloF Faiting Friters, if anM, to Frite

mutex.unloc)05

6

Write0

FritersXrXNue.!05 :: bloc) until no readers are reading or Faiting and



67 write ! 76 :: no Friters are Friting

FritersXrXNue.%05 :: signal lead reader or a Friter at t"e front of t"e Nueue

6

Li!i"# 3.12 StrategM D &W..

Aceasta solutie este interesanta deoarece incalca modelul iesi inainte de a astepta descries mai

devreme. /a o regula un fir de executie va iesi dintr-o sectiune critica inainte sa se bloc"eze

singur intr-o operatie !0. Bricum cititorii lideri incalca aceasta regulacand executa

FriterXrXNue.!0 fara a executa mai inainte mutex.%0 pentru a iesi din sectiunea critica. Aceasta

este c"eia solutiei. 'oar un cititor lider exemplu7 cand activeDeader44#0 pot intra in coada

pentru FritersXrXNue.%0,pe cand toti ceilalti scriitori sunt blocati de mutex.!0 la inceputul

operatiei de citire. /and cititorul lider este eliberat de FritersXrXNue.%0,cititorul lider permite

celorlalti cititori sa intre in sectiunea critica notificand mutex.%0. /eilalti cititori nu vor executa

FritersXrXNue.!0cand activeDeaders44# este adevarat doar pentru cititorul lider.

DLW7

Aceasta strategie permite citirea concurenta si in general da scriitorilor o mai mare prioritate

decat cititorilor. /ititorii au permisiune in urmatoarea situatie7

/and un scriitor cere sa scrie, daca este un scriitor lider exemplu7 nici un alt scriitor nu scrie saunu asteapta sa scrie0 asteapta pana cand toti cititorii care au sosit mai devreme au terminat de

citit.

Aceasta strategie si strategia D8W. sunt simetrice. Solutia din listingul 3.#3 pentru DLW.

difera fata de solutia din listingul 3.# pentru D8W. cu urmatoarele7

Semaforul readersXFXNue este folosit pentru a permite unui scriitor lider sa bloc"eze

cititorii. 'oar un scriitorun scriitor lider0 poate fi blocat in aceasta coada.

Semaforul FritersXrXNue e redenumit FritersXNue, deoarece cititorii nu sunt niciodata

blocati in aceasta coada.

%ariabila FaitingBrWritingWriters e folosita pentru a numara numarul scriitorilor ce

asteapta sau scriu.

/and un Scriitor W executa Write07

'aca unul sau mai multi scriitori asteapta ca cititorii sa termine, W e blocat in mutexXF5



'aca nici un alt scriitor nu scrie sau nu asteapta, W este un scriitor lider, asa ca W executa

readersXFXNue.!0. 'aca un cititor citeste, W va fi blocat in readersXFXNue in spatele oricarui

cititor care asteapta5 altfel W poate incepe sa scrie si cititorii vor fi blocati cand vor executa

readersXFXNue.!0.

W poate fi urmat de mai multi scriitori. /and ultimul dintre acesti scriitori termina elexecuta readersXFXNue.%0pentru a notifica cititorii. 'aca un scriitor care a terminat observa ca

un alt scriitor asteapta, cititorii vor infometa.

>olosirea readersXFXNue asigura ca cititorii care au a(uns inaintea scriitorului lider au prioritate

mai mare. Asta deoarece cititorii si scriitorul lider amandoi c"eama readersXFXNue.!0, si acestia

sunt serviti in ordinea >/>S. /and un cititor blocat in readersXFXNue ii este permis sa citeasca el

executa readersXFXNue.%0 pentru a notifica urmatorul cititor ce asteapta pentru a executa

readersXFXNue.%0, si tot asa. Aceasta notificare in cascada continua pana cand nu mai existacititori care asteapta sau pana cand operatia readersXFXNue.!0 notifica un scriitor lider.

Scriitorul lider executa FritersXNue.!0 pentru a se bloca singur pana cand ceilalti cititori termina

de citit.

3.*.*

Simularea semafoarelor ce numara

!resupunem ca un sistem ofera semafoare binare dar nu semafoare numaratoare.

Cistingul 3.#H arata cum se folosesc semafoarele binare pentru a implementa operatiiile !0 si %0

in clasa countingSemap"ores.


int FaitingBrWritingWriters 4 95 :: number of Friters Faiting or Friting

mutexCoc) mutexXr 4 neF mutexCoc)05 :: exclusion for active:eaders

:: exclusion for waiting0rritingriters

mutexCoc) mutexXF 4 neF mutexCoc)05

binarMSemap"ore FritersXNue 4 neF binarMSemap"ore#05 :: Faiting Friters

:: condition Nueue for Faiting readers and t"e first Faiting Friter

binarMSemap"ore readersXFXNue 4 neF binarMSemap"ore#05




Dead0

readersXFXNue.!05 :: serve Faiting readers and lead Friter >/>S

mutexXr.loc)05

;;activeDeaders5

if activeDeaders 44 #0

FritersXNue.!05 :: bloc) Friters reads are occurring

mutexXr.unloc)05

readersXFXNue.%05 :: signal t"e next Faiting reader or a lead Friter

67 read ! 76

mutexXr.loc)05

--activeDeaders5

if activeDeaders 44 90

FritersXNue.%05 :: alloF Friting

mutexXr.unloc)05

6

Write 0

:: if a lead Friter is Faiting in readers8w89ue, t"is bloc)s ot"er Friters

mutexXF.loc)05

;;FaitingBrWritingWriters5

if FaitingBrWritingWriters 44 #0 :: true if t"is is a lead Friter

readersXFXNue.!05 :: bloc) lead Friter if t"ere are Faiting readers

mutexXF.unloc)05

FritersXNue.!05 :: bloc) if a Friter is Friting or a reader is reading

67 write ! 76



FritersXNue.%05 :: signal Friting is over5 Fa)es up Faiting Friter if anM0

mutexXF.loc)05

-- FaitingBrWritingWriters5

if FaitingBrWritingWriters 44 90 :: no Friters are Faiting or Friting

readersXFXNue.%05 :: so alloF reading

mutexXF.unloc)05

6

Li!i"# 3.13 StrategM D <W..

class countingSemap"ore

private int permits 4 95

:: provides mutual exclusion for permits

private binarMSemap"ore mutex 4 neF binarMSemap"ore#05

:: condition Nueue for t"reads bloc)ed in !

private binarMSemap"ore delaMY 4 neF binarMSemap"ore905

public void !0

mutex.!05

--permits5

if permits L 90

mutex.%05

delaMY.!05

6

else



mutex.%05

6

public void %0

mutex.!05

;;permits5

if permits L4 90

delaMY.%05

mutex.%05

6

6

Li!i"# 3.1$ Implementing counting semap"ores bM using P() and V() operations on binarM

semap"ores.

Semafoare si incuietori in !1PD=A'S

Incuietorile <utex sunt parte a standardului !t"reads!BSI[#.c0.Semafoarele nu sunt parte a!t"reads,dar se gasesc in !BSI[#.b.

const int capacitM 4 35

class Kuffer

private7

int buffer&capacitM5

int count, in, out5

public7

Kuffer0 7 in90, out90, count90 6

int size0 return count56



int Fit"draF 0

int value 4 95

value 4 buffer&out5 :: out este impartit de consumatori

out 4 out ; #0 Q capacitM5

count--5

return value5

6

void deposit int value0

buffer&in 4 value5 :: in este impartit de producatori

in 4 in ; #0 Q capacitM5

count;;5

6

65

Kuffer s"aredKuffer5 :: 3-slot buffer

mutexCoc) mutex', mutexW5

countingSemap"ore emptMSlotscapacitM05

countingSemap"ore fullSlots905

class !roducer 7 public 1"read

public7

virtual voidE run 0

int i5

std77cout LL \producer running\ LL std77endl5

for i495 iL5 i;;0

emptMSlots.!05

mutex'.loc)05



s"aredKuffer.depositi05

std77cout LL \!roduced7 \ LL i LL std77endl5

mutex'.unloc)05

fullSlots.%05

6

return 95

6

65

class /onsumer 7 public 1"read

public7

virtual voidE run 0

int result5

std77cout LL \consumer running\ LL std77endl5

for int i495 iL5 i;;0

fullSlots.!05

mutexW.loc)05

result 4 s"aredKuffer.Fit"draF05

mutexW.unloc)05

std77cout LL \/onsumed7 \ LL result LL std77endl5

emptMSlots.%05

6

return 95

6

65

int main0



std77autoXptrL!roducer8 p#neF !roducer05

std77autoXptrL!roducer8 pneF !roducer05

std77autoXptrL/onsumer8 c#neF /onsumer05

std77autoXptrL/onsumer8 cneF /onsumer05

p#-8start05c#-8start05 p-8start05c-8start05

p#-8(oin05 p-8(oin05 c#-8(oin05 c-8(oin05

return905

6

$n mutex de tip !t"reads este o incuietoare cu un comportament similar celui din WI23

/DI1I/ACXS=/1IB2.Bperatiile pthread mute! loc,() si pthread mute! unloc,() sunt omoloage

cu =nter*riticalSection() si -eave*riticalSection()respectiv"

-unui fir de executie care invoca pthread mute! loc,() pe un mutex i se permite accesul la mutex

daca nici un alt fir de executie nu poseda mutexul.Altfel,firul de executie este blocat.

-$n fir de executie care invoca pthread mute! loc,() pe un mutex si i se acorda accesul la

mutex,devine proprietarul mutexului.

-$n fir de executie elibereaza posesia prin invocarea pthread mute! loc,() .$n fir de executie

care invoca pthread mute! loc,() trebuie sa fie proprietarul mutexului.

-=xista o operatie de asteptare conditionala pthread mute! tr>loc, pt"read mutexXtE mutex0

care nu va bloca niciodata firul de executie invocator.'aca mutexul este in prezent

incuiat,operatia se intoarce imediat cu erroare =K$S].Altfel,firul de executie invocator devine

posesor.

Cista 3.U arata cum trebuie folosit un mutex de tip !t"reads.Initializati mutexul prin invocarea

functiei pthread mute! init().!rimul parametru este adresa mutexului.'aca doriti sa initializati un

mutex cu atribute neinitiale,al doilea parametru poate specifica adresa unui obiect atribut./and

mutexul nu mai este necesar,este distrus prin invocarea functiei pthread mute! destro>().



/and declarati un mutex static cu atribute initiale,puteti folosi macroul !1PD=A' <$1=[

I2I1IACIZ=D in loc sa invocati functia pthread mute!8int().In lista 3.U am fi putut scrie7

pt"readXmutexXt mutex 4 !1PD=A'X<$1=[XI2I1IACIZ=D5

2u este necesara distrugerea unui mutex care a fost initializat cu macroul !1PD=A' <$1=[

I2I1IACIZ=D.

In mod implicit,un mutex !t"reads nu este recursiv,ceea ce inseamna ca un fir de executie nu ar

trebui sa incerece inc"iderea unui mutex pe care il poseda de(a.In orice caz, standardul !BSI[

#993.# 99# permite unui atribut de tip mutex sa fie setat la recursivitate7

pt"readXmutexXt mutex5

pt"readXmutexattrXt mutexAttribute5

int status 4 pt"readXmutexattrXinit VmutexAttribute05

if status 490 :E ... E: 6

status 4 pt"readXmutexattrXsettMpeVmutexAttribute,

!1PD=A'X<$1=[XD=/$DSI%=05

if status 4 90 :E ... E:6

status 4 pt"readXmutexXinitVmutex,VmutexAttribute05

if status 4 90 :E ... E: 6

'aca un fir de executie care poseda un mutex recursiv incearca din nou sa inc"ida

mutexul,firului i se permite accesul imediat.Inainte ca un alt fir sa devina posesor,un fir posesor

trebuie sa elibereze un mutex recursiv de atatea ori de cate a cerut posesia.

3.. Semafoare

Semafoarele !BSI[ sunt semafoare numaratoare.Bperatiile semXFait0 si semXpost0 sunt

ec"ivalente cu !0 si respectiv %0.Semafoarele !BSI[ au urmatoarele proprietati7



-$n semafor nu este considerat ca fiin posedat de un fir de executie Tun fir de executie poate

executa semXFait0 pe un semafor si un alt fir de executie poate executa semXpost0.

-/and este creat un semafor,este specificata valoarea initiala a semaforului.%aloarea initiala

trebuie sa fie mai mare sau egala cu zero si mai mica sau egala cu valoarea

S=<X%AC$=X<A[.

Li!i"# 3.2 utilizarea !t"reads

include Lpt"read."8

pt"readXmutexXt mutex5

voidE 1"read#voidE arg0

pt"readXmutexXloc)Vmutex05

:E critical section E:

pt"readXmutexXunloc)Vmutex05

return 2$CC5

6

voidE 1"readvoidE arg0

pt"readXmutexXloc)Vmutex05


pt"readXmutexXunloc)Vmutex05

return 2$CC5

6

int main0



pt"readXt t"readArraM&5 :: arraM of t"read I's

int status5 :: error code

pt"readXattrXt t"readAttribute5 :: t"read attribute

:: initialize mutex

status 4 pt"readXmutexXinitVmutex,2$CC05

if status 4 90 :E See Cisting #.H for error "andling E: 6

:: initialize t"e t"read attribute ob(ect

status 4 pt"readXattrXinitVt"readAttribute05


:: set t"e sc"eduling scope attribute

status 4 pt"readXattrXsetscopeVt"readAttribute,

!1PD=A'XS/B!=XS]S1=<05


:: /reate tFo t"reads and store t"eir I's in arraM threadArra>

status 4 pt"readXcreateVt"readArraM&9, Vt"readAttribute, 1"read#,

voidE0 #C05


status 4 pt"readXcreateVt"readArraM&#, Vt"readAttribute, 1"read,

voidE0 C05


status 4 pt"readXattrXdestroMVt"readAttribute05 :: destroM attribute ob(ect




:: Wait for t"reads to finis"

status 4 pt"readX(oint"readArraM&9,2$CC05


status 4 pt"readX(oint"readArraM&#,2$CC05


:: 'estroM mutex

status 4 pt"readXmutexXdestroMVmutex05

if status 4 90 :E ... E: 6

6

-operatiile semafoarelor urmeaza o conventie diferita de raportare a erorilor. =le returneaza zero

in caz de succes. In caz de esec, ele intorc valoarea -# si memoreaza numarul corespunzator

erorii in errno.>olosim functia / perrorconst c"arE string0 pentru a transcrie valoarea lui errno

intr-un sir si a afisa acel sir in stderr.

-=xista o operatie conditional de asteptare sem tr>wait sem tE sem0 care nu va bloca niciodata

firul de executie invocator. 'aca valoarea semaforului este mai mare de zero,valoarea este

decrementata si operatia se intoarce imediat .Altfel spus,operatia intoarce imediat codul de eroare

=AAI2 indicand ca valoarea semaforului nu a fost mai mare ca zero.

Cista 3. arata cum obiectele semafor !t"reads sunt folosite. >isierul "eader Lsemap"ore."8

trebuie sa fie inclus pentru a folosi operatiile semafoarelor.Semafoarele apartin tipului tMpe

semXt.$n semafor este creat prin invocarea functiei semXinit0.!rimul argument este adresa

semaforului.'aca al doilea argument are o valoare diferita de zero ,semaforul poate fi impartitintre procese./u o valoare egala cu zero,poate fi impartit de firele de executie ale aceluiasi

proces.Al treilea argument este valoarea initiala.Acdn semaforul nu mai ese necesar,este distrus

prin invocarea functiei semXdestroM0.

!utem crea o clasa simpla in /;; care impac"eteaza semafoarele !BSI[,asa cum am facut si cu

semafoarele Win3.Cista 3.* arata clasa ambalata !BSI[Semap"ore.<etodele



!BSI[Semap"ore invoca mai departe functiile corespunzatoare ale semaforului !BSI[.!entru a

testa si depana,vom avea nevoie de o incuietoare de nivel utilizator si clase semafor de tipul celor

pe care le-am dezvoltat pentru Win3.!utem folosi P0S#?Semaphore pentru a implementa

ambele clase./odul pentru /;;:!t"reads

Al claselor mute!-oc, si countingSemaphore este identic cu cel din lista 3.3 si 3.H,exceptiefacand faptul urmator7clasa Fin3Semap"ore ar trebui inlocuita de clasa

!BSI[Semap"ore.'iferenta dintre Win3 si !BSI[ este incapsulata in clasele semafor.

Li!& 3.2:

include Lpt"read."8

include Lsemap"ore."8

include Lstdio."8

semXt s5

voidE 1"read#voidE arg0

int status5

status 4 semXFaitVs05

if status 490

std77cout LL XX>IC=XX LL \7\ LL XXCI2=XX LL \- \ LL flus"5

perror\semXFait failed\05 exitstatus05

6


status 4 semXpostVs05

if status 490




perror\semXpost failed\05 exitstatus05

6

return 2$CC5 :: implicit call to pt"readXexit2$CC05

6

voidE 1"readvoidE arg0

int status5

status 4 semXFaitVs05

if status 490



6


status 4 semXpostVs05

if status 490



6

return 2$CC5 :: implicit call to pt"readXexit2$CC05

6

int main0

pt"readXt t"readArraM&5 :: arraM of t"read I's

int status5 :: error code

pt"readXattrXt t"readAttribute5 :: t"read attribute

:: initialize semap"ore s



status 4 semXinitVs,9,#05

if status 490


perror\semXinit failed\05 exitstatus05

6

:: initialize t"e t"read attribute ob(ect

status 4 pt"readXattrXinitVt"readAttribute05

if status 4 90 :E see Cisting #.H for !t"reads error "andling E:6

:: set t"e sc"eduling scope attribute

status 4 pt"readXattrXsetscopeVt"readAttribute,

!1PD=A'XS/B!=XS]S1=<05


:: /reate tFo t"reads and store t"eir I's in arraM threadArra>

status 4 pt"readXcreateVt"readArraM&9, Vt"readAttribute, 1"read#,

voidE0 #C05


status 4 pt"readXcreateVt"readArraM&#, Vt"readAttribute, 1"read,

voidE0 C05


status 4 pt"readXattrXdestroMVt"readAttribute05 :: destroM t"e attribute ob(ect


:: Wait for t"reads to finis"

status 4 pt"readX(oint"readArraM&9,2$CC05




status 4 pt"readX(oint"readArraM&#,2$CC05


:: 'estroM semap"ore s

status 4 semXdestroMVs05

if status 490


perror\semXdestroM failed\05 exitstatus05

6

6

3.* Inca o nota cu privire la consistenta memoriei parta(ate.

Deamintiti-va din sectiunea ..+ problemele legate de consistenta memoriei parta(ate.

Bptimizarea compilatorului si a partii PardFare poate reordona operatiile de scriere si citire pe

variabile parta(ate, facand dificila intelegerea comportamentului programarii cu fire de executie.

Cista 3.*

include Lpt"read."8

include Lsemap"ore."8

include Lstdio."8

include Liostream8



const int max'efault 4 ***5

class !BSI[Semap"ore

private7

semXt s5

int permits5

public7

void !05

void %05

!BSI[Semap"oreint initial05

^!BSI[Semap"ore05

65

!BSI[Semap"ore77!BSI[Semap"ore int initial0 7 permitsinitial0

:: assume semap"ore is accessed bM t"e t"reads in a single process

int status 4 semXinitVs, 9, initial05

if status 490


perror\semXinit failed\05 exitstatus05

6

6

!BSI[Semap"ore77 ^ !BSI[Semap"ore 0

int status 4 semXdestroMVs05

if status 490




perror\semXdestroM failed\05 exitstatus05

6

6

void !BSI[Semap"ore77!0

int status 4 semXFaitVs05

if status 490



6

6

void !BSI[Semap"ore77%0

int status 4 semXpostVs05

if status 490



6

6

'in fericire, sectiuni critice create folosind operatiile de sincronizare din Java sau operatiile din

Win3 sau libraria !t"reads ofera excluziune mutuala si de asemenea prote(eaza impotriva

reordinarilor nedorite.

Aceste operatii de sincronizare din Java si din librariile firelor de executie interactioneaza cu

sistemul de memorie pentru a se asigura ca variabilele parta(ate accesate in sectiunile criticeau

valori ce sunt consistente de-a lungul firelor de executie.'e exemplu,valorile variabile parta(ate

pe care un fir le poate vedea cand desc"ide un mutex pot de asemenea fi vazute de orice fir de

executie care mai tarziu inc"ide acelasi mutex.'e aceea,o executie in care variabilele parta(ate

sunt corect prote(ate de incuietori sau semafoare este cu siguranta consistenta secvential.Aceasta



garantie ne permite noua sa ignoram problemele consistentei memoriei parta(ate atunci cand

folosim incuietori sau semafoare pentru a crea sectiuni critice in programul nostru.'in acest

motiv,ne propunem regula de a accesa variabilele parta(ate in interiorul sectiunilor critice.In

continuare vom vedea ca aceasta regula de aemenea simplifica testarea si depanarea.

3.#9 $rmarirea,testarea si reluarea pentru semafoare si incuietori.

In aceasta sectiune adresam doua probleme de testare si depanare pentru programe care folosesc

semafoare si incuietori.Intai,descriem o te"nica speciala de testare pentru detectarea incalcarii

excluderii mutuale.Apoi vom arata cum sa urmariti si sa reluati executiile programelor in timpul

depanarii.

3.#9. 1estarea nondeterminista cu algoritmul Coc)set

$n program concurent care foloseste semafoare si incuietori poate fi testat pentru cursele de

date.Amintiti-va din capitolul # ca o cursa de date este un esec in implementarea corecta a

sectiunilor critice pentru accesarea variabilelor nonatomice parta(ate.Abordarea pe care o vom

folosi pentru a detecta cursele de date este de a monitoriza accesarile variabilelor parta(ate si de ane asigura ca fiecare variabile a fost corespunzator incuiata inainte de a fi accesata.'e vreme ce

executiile programului sunt nedeterministice ,va trebui sa executam programul de cateva ori cu

aceeasi intrare de test pentru a creste sansele de a gasi curse de date.Acest tip de testare se

numeste testare nondeterminista.

1estarea nondeterminista a uni program concurent /! implica urmatorii pasi7

#.Selectarea unui set de intrari pentru /!

.!entru fiecare intrare [ selectata,executam /p cu [ de mai multe ori si examinam rezultatul

fiecarei executii.

=xecutiile multiple nondeterministe ale /! cu [ intrari exercita diferite comportamente ale /! si

astfel putem detecta mai multe esecuri decat o singura executie a /! cu intarea [.



Scopul testarii nondeterministe este acela de a detecta cat mai multe comportamente posibile

distincte ale programului .'in nefericire,experimentele au aratat ca executia repetata a unui

program concurent nu conduce la executarea comportamentelor diferite.In absenta variatiilor

semnificative ale intarzierilor I:B sau ale intarzierilor de retea,sau sc"imbari semnificative in

incarcarea programului,programele tind sa arate acelasi comportament de la executie la

executie.<ai mult,efectul de proba,care apare cand programele sunt instrumentate cu cod de

depanare,pot face posibila observarea unor esecuri.

=xista cateva te"nici pe care le putem folosi pentru a creste probabilitatea exercizarii

comportamentelor diferite.$nul este sa sc"imbam algoritmul de planificare al sistemului de

operare.Insa,in multe dintre sistemele de operare comerciale acest lucru nu este posibil.A doua

te"nica este de a insera declaratii Sleept0 in program cu cantitatea de somn t aleasa la

intamplare.=xecutarea unei declaratii Sleept0 forteaza o sc"imbare de context si apoi indirect

afecteaza planificarea firelor de executie.Am implementat aceasta a doua te"nica ca o optiune de

executare pentru programele care folosesc binar>Semaphore countingSemaphore, si clase

mute!-oc, in libraria noastra de sincronizare./and optiunea aceasta este specificata ,declaratiile

Spleep sunt executate la inceputul metodelor !0, %0, si unloc)0.1impul cat dureaza Sleep este

ales intamplator cu o gama programabila.Intarzierile aleatoare pot fi folosite in con(unctie cu

functiile de urmarire si reluare pentru ca fiecare eroare observata sa poate fi de asemenea reluata.

!entru a detecta curse de date,combinam testarea nondeterminista cu algoritmul loc)set.Acest

algoritm verifica ca toate variabilele parta(ate sa urmeze o disciplina a inc"iderii consistenta in

care fiecare variabila parta(ata este prote(ata de o incuietoare.'e vreme ce nu se cunoaste ce

incuietoare va inc"ide fiecare variabila,trebuie sa urmarim executiile si sa incercam sa deducem

o relatie intre incuietori si variabile.!entru fiecare variabila,determinam daca este vreo

incuietoare care este mereu tinuta oricand variabila este accesata.

!entru variabilele parta(ate v,lasam ca setul *andidate-oc,s(v) sa fie acele incuietori care au

prote(at v in timpul executiilor de pana acum.Astfel,o incuietoare l este in *andidate-oc,s(v)

dacain timpul executiei de pana acum,fiecare fir de executie care a accesat v tinea l la momentul

accesarii. *andidate-oc,s(v) este calculat astel"

-cand o noua variabila v este initializata,setul ei de candidati este considerat ca tine toate

incuietorile posibile.

-cand v este accesat pe o operatie de citire sau scriere de 1, *andidate-oc,s(v) esteredefinit.2oua valoare a lui *andidate-oc,s(v) este intersectia dintre *andidate-oc,s(v) si setul

de incuietori retinut de firul 1.

Kazandu-ne pe acest algoritm de rafinare,daca anumite incuietori l prote(eaza consistent v,vor

ramane in *andidate-oc,s(v) pe masura ce *andidate-oc,s(v) este rafinat.'aca

*andidate-oc,s(v) devine gol,el indica ca nu exista nici o incuietoare care prote(eaza v

consistent.<ai (os este algoritmul loc)set7



*andidate-oc,s(v) 4 *andidate-oc,s(v) _ Coc)sPeld105

if *andidate-oc,s(v) 44 60 issue a Farning5

'e exemplu ,in fig 3.39 accesul 1"read# al variabilei parta(ate s este prote(at mai intai de mutex#

si apoi de mutex.Aceasta este o incalcare a excluziunii mutuale care poate fi detectata de

algoritmul loc)set.*andidate-oc,s(s) este initializat la mutex#,mutex6 si este rafinat pe

masura ce s este accesata./and 1"read# inc"ide mutex#,Coc)sPeld%hread10 devine

mutex#6./and s este accesata in prima declaratie de asignare, *andidate-oc,s(s) devine

mutex#,care este intersectia seturilor *andidate-oc,s(s) si -oc,s@eld(%hread1)./and a doua

declaratie de asignare este executata,1"read# incuie retine incuietoarea mutex si singura

disponibila pentru s ramane mutex#.'upa intersectarea dintre *andidate-oc,s(s) si

-oc,s@eld(%hread1) *andidate-oc,s(s) devine gol.Algoritmul loc)set a detectat ca nici oincuietoare nu prote(eaza consistent variabila parta(ata s.

Am implementat algoritmul loc)set in clasa mutexCoc) si in clasa sablon s"ared%ariable din /;

; care a fost prezentata in capitolul 7

-presupunem ca firele de executie pot accesa o s"ared%ariable doar dupa initializarea ei.Insa,nici

o rafinare nu este facuta in timpul initializarii.

-%ariabilele de tip read-onlM pot fi accesate fara sa fie incuiate.Asta inseamna ca avertismentele

sunt probleme doar dupa ce o variabila a fost initializata si a fost accesata de cel putin o operatie

de scriere.

-algoritmul de rafinare poate fi inc"is pentru a se elimina alarmele false.'e exemplu,programul

bounded-buffer prezentat in lista 3.+ poate fi modificat pentru a folosi un tampon al

s"ared%ariables.Aceste variabile sunt impartite intre firele de executie !roducator si

/onsumator,dar nu sunt necesare incuietori./"iar si asa,cand acest program este executa,un

avertisment va fi lansat de algoritmul loc)set./and se determina ca avertismentul poate fi cu



siguranta ignorat,algoritmul loc)set poate fi oprit pentru aceste variabile.Alternativ,tamponul

poate fi implementat folosind s"ared%ariable.

Algoritmul loc)set a fost initial implementat intr-un instrument de testare numit =raser.'e

asemenea a fost implementat ca parte a unei masini virtuale de (ava,numita Java

Apt"finder.Algoritmul loc)set s-a dovedit a fi o te"nica practica de detectare a curselor de date in programe care prote(eaza variabilele parta(ate cu incuietori.Bricum,programele care folosesc

semafoare pentru excluziunea mutuala ,cu sabloane ca passingXt"eXbatton,vor genera alarme

false.Asa cum s-a aratat mai sus pentru programul tamponului delimitat ,loc)set poate da alarme

false c"iar si daca sunt folosite incuietori.2umarul de alarme false poate fi diminuat daca li se

permite utilizatorilor sa inc"ida algoritmul de detectie pentru regiuni de cod sau sa TI asigure

algoritmului de detectie informatii suplimentare./a o te"nica de testare

nondeterminista,algorimul loc)set nu poate dovedi ca un program nu contine curse de date.In

orice caz,stiind ca o anume executie nu contine curse de date poate fi de a(utor in timpul

urmaririi si reluarii ,asa cum vom vedea mai incolo.

3.#9. Secvente S]2 simple pentru semafoare si incuietori.

In general putem caracteriza o executie a unui program concurent ca o secventa de evenimente

sincronizate a unor obiecte sincronizate.B secventa a unor evenimente sincronizate se numeste

secventa S]2.<ai intai definim tipul evenimentelor sincronizate si apoi obiectele sincronizate

care apar in programele ce contin semafoare si incuietori.Acesti doi pasi nu sunt

independenti.Sunt cateva moduri de definire a unei secvente S]2,si definitia unei secvente S]2

are efect asupra proiectarii solutiei de reluare,si viceversa.

Casati /! sa fie un program concurent ce foloseste variabile parta(ate,semafoare si

incuietori.Dezultatul executarii uni /! cu o intrare data depinde de ordinea in care variabilele

parta(ate,semafoarele si incuietorile in /! sunt accesate.Semafoarele sunt accesate folosind

operatii ! si %,incuietorile sunt folosite folosind operatii loc) si unloc),iar variabilele parta(ate

sunt accesate folosind operatii de citire si scriere.Insa,evenimentele sincronizate in /! sunt

executii de read:Frite, !:% si loc):unloc) ale acestor obiecte.

Am aratat ca pot fi variabile parta(ate ce pot fi accesate in implementarile operatiilor !:% sau

loc):unloc).'e fapt,aceste variabile parta(ate pot fi accesate de foarte multe ori,din cauza

buclelor de asteptare ocupate.Insa,nu vom urmari operatiile de citire si scriere pe aceste variabile

parta(ate.'e vreme ce !:% si loc):unloc) sunt operatii atomice ,le vom considera ca operand pe



un singur semafor sau variabila incuiata.Aceasta abstractizare descreste numarul operatiilor ce

necesita urmarire pe parcursul executiei.

B secventa S]2 pentru o variabila parta(ata v este o secventa a operatiei de citire si scriere pe v.

Secventele DeadWrite pentru variabilele parta(ate au fost definite in capitolul .B secventa S]2

pentru o binar>Semaphore sau countingSemaphore s este o secventa de evenimente aurmatoarelor tipuri"

$completare a unei operatii P

- completare a unei operatii V

-Startul unei operatii ! care nu este niciodata inc"eiata din cauza unui punct mort saua unei

exceptii

-Startul unei operatii % care nu este niciodata inc"eiata din cauza unui punct mort saua unei

exceptii

2e referim la o astfel de secventa ca la o secventa !% de s.$n eveniment intr-o secventa !% este

denotat de identificatorul I' al firului de executie care a executat operatia ! sau %.Brdinea in

care firele isi inc"eie operatiile ! sau % nu este neaparat aceeasi ca ordinea in care ele invoca !

sau % si nic macar ca ordinea in care operatiile ! si % incep.!entru operatii care sunt

indeplinite,ordinea lor de inc"eiere este aceea care trebuie reluata,de vreme ce aceasta ordine

determina rezultatul executiei.'e asemenea reluam startul operati5or care nu s-au inc"eiat,astfel

incat aceleasi evenimente ,exceptii si puncte moarte vor aparea in timpul reluarii.

B secventa S]2 pentru un mutexCoc) este o secventa de evenimente de urmatoarele tipuri7

-efectuarea unei operatii loc)

-efectuarea unei operatii unloc)

-startul unei operatii loc) care nu este niciodata inc"eiata din cauza unui punct mort sau a unei

exceptii



-startul unei operatii unloc) care nu este niciodata inc"eiata din cauza unui punct mort sau a unei

exceptii

2e referim la o astfel de secventa ca la o secventa Coc)$nloc) de l.$n eveniment intr-o secventaCoc)$nloc) este denotat de identificatorul firului de executie care a executat operatia loc) sau

unloc).!entru a ilustra aceste definitii ,consideram programul simplu din lista 3.3#.%aloarea

finala a variabilei parta(ate x este # sau .B posibila secventa DeadWrite a variabilei parta(ate x

este7

Asta inseamna ca x a fost mai intai accesata de 1"read# si apoi de 1"read.'e vreme ce 1"read#

a accesat prima data pe x,secventa !% pentru mutex trebuie sa indice ca 1"read# a efectuat

operatiile ! si % inaintea lui 1"read.A doua operatii ! in 1"read este o eroare.Aceasta operatie

! va incepe dar nu se va sfarsi si ar trebui sa fie o operatie % in locul ei.

B secventa S]2 pentru un program concurent /! este o colectie de secvente

DeadWrite,secvente !% si secvente Coc)$nloc).=xista o singura secventa pentru fiecare dintre

variabile,semafor sau incuietoare in program.B secventa S]2 pentru program in lista 3.3#

contine o secventa DeadWrite pentru x si o secventa !% pentru mutex7

Secventa DeadWrite a lui !7 #, 9, 90, , #, 905secventa !% a mute!7 #, #, , 00.

Aceasta este o ordonare partiala a evenimentelor sincronizate in program.Asta inseamna ca

evenimentele pe un singur obiect sunt total ordonate,dar ordinea evenimentelor din mai multe

obiecte diferite nu este specificata.Alternativ,putem defini o secventa S]2 a unui program ca o

secventa singulara total ordonata de evenimente sinconizate peste toate obiectele sincronizate.o

secventa total ordonata de evenimente care este consistenta cu partial ordonata secventa de mai

sus este 7

#, #, 9, 90, #, , , #, 90, .

In general,pot fi doua sau mai multe secvente total ordonate care sunt consistente cu o ordine

partiala data de vreme ce doua evenimente concurente pot aparea in ordonarea totala in alta

ordine.

'efinitia unei secvente S]2 are intentia de a captura ce inseamna pentru o executie sa reia o

alta.!resupunem ca atunci cand programul de mai sus este executat ,1"read executa mutex.!0

si se bloc"eaza deoarece 1"read# este de(a in sectiunea critica.In timpul reluarii acestei



executii ,presupunem ca 1"read executa prima sa operatie mutex.!0 si mutex.%0.Aceste doua

executii nu sunt identice.In orice caz,in ambele executii7

-Secventa operatiilor !0 si %0 completate este aceasi

-%aloarea finala a lui x este

!rin urmare,consideram executia a doua sa o reia pe prima.'esi am putea include evenimente ca

@invoca %0 sau @bloc"eaza in !0 in secventa S]2 a obiectului semafor,nu ni se cere sa

urmarim aceste evenimente pentru a face o reluare de succes,deci le omitem.=venimentele pe

care le ignoram in timpul reuarii pot fi importante cand facem alte lucruri.In continuare, definim

diferite tipuri de secvente S]2 pentru diferitele actiuni ce apar in timpul testarii si depanarii.'e

vreme ce secvetele S]2 pe care le folosim pentru reluare tind sa fie mult mai simple decat alte

secvente S]2,folosim termenul de secvente S]2 simple pentru a ne referi la secventele S]2

care sunt folosite pentru reluare.

In conformitate cu definitia unei secvente simple S]2 pentru /!,trebuie sa fim pregatiti sa

inregistram si sa reluam interplecari arbitrare ale operatiilor de scriere si citire pe variabilele

parta(ate.Aceasta este o solutie de reluare generala,care poate fi aplicata programelor care

folosesc variabile parta(ate si construiesc altceva decat semafoare si incuietori.In orice

caz,aceasta solutie generala e posibil sa nu fie usor de implementat./ontrolara operatiilor de

scriere si citire din timpul reluarii adauga o cantitate semnificativa de depasiri ale executiilor si

necesita accesul la implementarea /!.!rin urmare,examinam cateva solutii alternative.

In lista 3.3# observati ca secventa simpal DeadWrite pentru variabila parta(ata x este complet

determinata de secventa simpla !% a mutexului.Asta inseamna ca,daca reluam secventa !%

pentru mutex,vom reusi,fara un effort suplimentar ,sa reluam de asemenea si secventa DeadWrite

pentru x.Aceasta este o observatie importanta,deoarece inseamna ca daca presupunem ca

variabilele parta(ate sunt mereu accesate in siguranta in sesiunea critica,putem dezvolta o solutie

mai simpla si mai eficienta.

'esigur,in general putem presupune ca excluziunea mutuala rezista cand variabilele parta(ate

sunt accesate.$n programator poate face o eroare cand scrie programul,sau c"iar incalca

excluziunea mutuala intentionat.'aca excluziunea mutuala pentru o anumita variabila parta(ata

nu este critica pentru corectitudinea unui program,sectiunea critica poate fi eliminata pentru a

elimina depasirea ac"izitionarii unei incuietori.'e asemenea,o declaratie ce acceseaza o variabila

parta(ata nu are nevoie de precizie in timpul sectiunii critice daca executia declaratiei este

atomica.



Bbservatia noastra despre sectiunile critice nu duce la o solutie mai buna de reluare.>ace,insa,sa

mareasca importanta excluziunii mutuale si nevoia de constructii sincronizate care sunt necesare

in implementarea corecta a excluziunii mutuale./onstructorul monitor din capitolul H este o

asemenea constructie.>olosirea monitorului imbunatateste ma(or sansele ca variabilele parta(ate

sa fie accesate in interiorul sectiunii critice si realizeaza mai usor executia de reluare.

<omentan,vom incerca sa imbunatatim solutia de reluare prin folosirea algoritmului loc)set in

paralel cu reluarea.In timpul reluarii,presupunem ca variabilele parta(ate sunt accesate in

interiorul sectiunilor critice care sunt implementate cu mutexCoc)s folosite ca incuietori.Asta ne

permite sa ignoram operatiile de scriere si citire asupra variabilelor parta(ate.In timpul

urmaririi,vom folosi algoritmul loc)set pentru a ne valida presupunerea.algoritmul loc)set ne va

spune cand reluarea poate esua.

Asa cum am mentionat anterior,in cazul in care o variabila parta(ata poate fi accesata in siguranta

in afara sectiunii critice,algoritmul loc)set poate fi inc"is pentru acea variabila,astfel incat sa nu

produca un avertisment.In orice caz,asta poate crea o problema pentru reluare deoarecedepindem de fiecare variabila parta(ata sa fie accesata in interiorul sectiunii criticF ,astfel incat

accesul fiecarei variabile parta(ate sa fie reprezentat de operatiile loc)0 sau !0 in urmarirea

executiei.In aceste cazuri,incuietorile pot fi folosite pentru a crea sectiuni critice ,cel putin

temporar,astfel incat reluarea sa poata fi facuta.!roiectarea unui program pentru a fi mai usor de

testat si depanat creste testabilitatea programului.

Casati un /! sa fie un program concurent ce contine incuietori mutex,semafoare binare si

semafoare de numarare.!resupuneti ca variabilele parta(ate sunt accesate corect in interirulsectiunii critice7

-fiecare semafor si incuietoare in /! este un obiect de sincronizare

-evenimentele de sincronizare intr-o secventa !% simpla pentru un semafor sunt patru tipuri de

evenimente definite mai sus

-evenimentele de sincronizare intr-o simpla secventa Coc)$nloc) pentru o incuietoare mutex

sunt patru tipuri de evenimente descrise mai sus

-fiecare eveniment de sincronizare este denotat de identificatorul firului de executie care a

exucutat evenimentul.

!entru a relua executia unui /! trebuie sa reluam secventele !% pentru semafoarele din /! si

secvntele simple Coc)$nloc) pentru incuietorile din /!.In urmatoarea sectiune va vom arata

cum sa faceti asta.



3.#9.3.$rmarirea si reluarea unei secvente simple !% si a unui secvente Coc)$nloc)

%om arata acum cum sa modificam clasele semafor si incuietoare astfel incat ele sa poata urmari

si relua secvente simple !% si Coc)$nloc).

<odificarea metodelor !0 si %07implementarea metodelor !0 si %0 in clase binarMSemap"ore

pot fi modificate astfel incat secventele !% simple sa poate fi colectate si reluate./olectarea unei

secvente !% pentru un semafor este simpla.In timpul executiei indentificatorul firului de executie

care inc"eie o invocarea a metodei s.!0 si s.%0 este inregistrat si salvat intr-un fisier de urmarire

pentru s.metodele !0 si %0 pot fi usor modificate pentru a colectata aceste evenimente.

!entru scopul explicarii metodei de reluare,presupunem ca fiecare semafor are o permisie numita

!%-permit.$n fir de executie trebuie sa retina permisul !% al unui semafor inainte sa execute o

operatie !0 sau %0 pe acel semafor.Brdinea in care firele de executie recepteaza permisul !% al

unui semafor se bazeaza pe o secventa !% care este reluata./ererea unui fir de executie si

eliberarea unui permis !% pentru semafor se face prin invocarea metodelor reNuest!ermit0 si

release!ermit0.Aceste invocari sunt adaugate la implementarea metodelor !0 si %0.<etoda !0

devine7

void !0

if replaM<ode0

control.reNuest!ermitI'05

:: code to loc) t"is semap"ore appears "ere

if replaM<ode0

control.release!ermit05

:E rest of bodM of !0 E:



if trace<ode0

control.trace/omplete!I'05

:: code to unloc) t"is semap"ore appears "ere

6

<et"od V() becomes7

public final void %0

if replaM<ode0

control.reNuest!ermitI'05

:: code to loc) t"is semap"ore appears "ere

if replaM<ode0

control.release!ermit05

:E rest of bodM of %0 E:

if trace<ode0

control.trace/omplete%I'05

:: code to unloc) t"is semap"ore appears "ere

6

!resupunem ca imlemantarile lui !0 si %0 contin sectiuni critice pentru accesarea variabilelor pe

care le parta(eaza.Am indicat asta prin intermediul comentariilor cu privire la operatiile inc"ide

si desc"ide cre creaza aceste sectiuni critice.Invocarea re9uestPermit() releasePermit()

trace*ompleteP(), si trace*ompleteV() trebuie sa fie pozitionate corect in conformitate cu

sectiunile critice in !0 si %0.Invocarea reNuest!ermit0 apare inainte de operatia de inc"idereiar invocarea release!ermit0 apare imediat dupa operatia de inc"idere.Invocarea

trace*ompleteP() si trace*ompleteV() apare in interiorul sectiunii crtice.Asta asigura ca

evenimentele sunt inregistrate in timpul urmaririi executiei in ordinea in care ele apar.'aca

invocarea functiei trace este facuta in afara sectiunii critice,ordinea invocarilor poate sa nu fie

consistenta cu ordinea in care firele de executie si-au completat operatiile !0 si %0.



<odificarea metodelor loc)0 si unloc)0 7 Implementarile metodelor loc)0 si unloc)0 in clasa

mutexCoc) sunt modificate exact ca metodele !0 si %0./lasa mutexCoc) contine referinte la

re9uestPermit() si releasePermit() inainte si dupa operatia de inc"idere din

mutexCoc).Deferintele la trace*omplete-oc,() si

trace*ompletenloc,() apar la sfarsitul sectiunii critice respective.

!entru simplificarea urmaririi si reluarii, nu vom urmari evenimentele care reprezinta startul lui

!,%, loc) sau unloc) care nu s-au completat niciodata din cauza unui punct mort sau a unei

exceptii.1otusi,cand operatiile de producere a unui punct mort sunt reluate,invocarea firelor de

executie nu va fi blocata in interiorul corpului oparatiei5din potriva ele vor fi blocate pentru

totdeauna la invocarea reNuest!ermit0 dinaintea operatiei.'evreme ce in ambele cazuri firul de

executie va fi blocat pentru totdeauna,efectul reluarii este acelasi.Similar,evenimentele care

implica exceptiile ce apar in timpul executiei operatiilor !,%,loc) sau unloc) nu vor fi reluate.'ar

urma va indica ca excutia acestor operatii va ridica o eroare,care probabil asigura a(utor destul

pentru depanarea programului.Solutia nostra poate fi extisa astfel incat evenimentele incomplete

sunt de fapt executate.

/ontrolul /lasei7 >iecare semafor si incuietoare este asociat cu un obiect de control.In modul de

reluare, obiectul de control introduce secventa S]2 a semaforului sau incuietorii si se ocupa de

invocarea reNuest!ermit 0 si release!ermit0.In modul de urmarire obiectele de controlcolecteaza evenimentele sincronizate care apar si le inregistreaza intr-un fisier de urmarire./and

un fir de executie invoca reNuest!ermit0 sau una dintre metodele de urmarire isi prezinta

identificatorul id.!resupunem ca toate firele de executie sunt instantieri ale clasei %B%hread

.Aceasta clasa se ocupa de crearea unor id-uri unice pentru firele de executie.

B clasa de control /;; este aratata in lista 3.3./onsideram un semafor s si o secventa simpla

!% pentru s care a fost inregistrata in timpul unei executii anterioare./and obiectul de control

pentru s este creat, el citeste secventa pv simple pentru s intr-un vector

S]2seNuence.!resupunem ca prima operatie (-#,(89 a fost completata si valoarea lui

S]2seNuence(0 este ), asta inseamna ca firul de executie 1)0 trebuie sa execute urmatorul

eveniment./and firul de executie 1(0 invoca metoda reNuest!ermit0 este blocat prin executia lui

1i0.



class control

public7

control0

:E input integer I's into SCDse9uence5 initialize arraMs threads and

has:e9uested E:

6

void reNuest!ermitint I'0

mutex.loc)05

if I' 4 S]2seNuence&index0 :: t"read I' s"ould execute next eventG

"asDeNuested&I' 4 true5 :: 2o5 set flag to remember I'Os reNuest

mutex.unloc)05

t"reads&I'.!05 :: Fait for permission

"asDeNuested&I' 4 false5 :: reset flag and exit re9uestPermit

6

else mutex.unloc)05 :: ]es5 exit re9uestPermit

6

void release!ermit0

mutex.loc)05

;;index5

if index L S]2seNuence.size00 :: Are t"ere more events to replaMG

:: Pas t"e next t"read alreadM reNuested permissionG

if "asDeNuested&S]2seNuence&index0

t"reads&S]2seNuence&index.%05 :: ]es5 Fa)e it up.



6

mutex.unloc)05

6

void trace/omplete!int I'0 ...6 :: record integer I'

void trace/omplete%I'0 ...6 :: record integer I'

private7

:: !%-seNuence or Coc)$nloc)-seNuence5 a seNuence of integer I's

vector S]2seNuence5

binarMSemap"oreE t"reads5 :: all semap"ores are initialized to 9

:: has:e9uested2i3 is true if 1"read i is delaMed in re9uestPermit()5 init to false

boolE "asDeNuested5

int index 4 95 :: S]2seNuence&index is I' of next t"read to execute an event

mutexCoc) mutex5 :: note7 no tracing or replaM is performed for this loc)

6

Li!i"# 3.32

!resupunem ca 1"read incearca sa execute mutex!0 si apoi invoca reNuest!ermit0 inainte ca

1"read#0 sa invoce reNuest!ermit#0.'evreme ce valoarea indexului este zero si valoarea lui

S]2seNuenceindex0 este #,t"read se autobloc"eaza in reNuest!ermit0 prin executarea

t"read0.!0./and t"read# invoc reNuest!ermit#0 I se va permise sa iasa din reNuest!ermit0 si

sa execute operatia mutex.p.1"read# va invoca apoi release!ermit0 .<etoda release!ermit0

incrementeaza indexul la # si verifica daca firul de executie care trebuie sa execute urmatoarea

operatie !:% a invocat de(a reNuest!ermit0 .$rmatorul fir de executie este S]2seNuence&#,care

este #.1"read# nu a invocat reNuest!ermit0 pentru urmatoarea operatie,prin urmare nu se

intampla nimic in release!ermit0.=ventual,1"read# invocareNuest!ermit0 pentru a cere

permisiunea sa-si executeoperatia mutex.%0.1"read# primeste permisiunea,executa

mutex.%0,iar apoi invoca release!ermit0.<etoda release!ermit0 incrementeaza indexul la si

gaseste firul de executie care sa execute urmatoarea operatie !:% in 1"read.1"read avand de(a

invocata reNuest!ermit0,este in continuarte blocat la 1"read&.!0.Asta este indicat de valoarea

lui "asDeNuested& care este adevarata.Astfel,release!ermit0 invoca 1"read&.%0. Asta



permite lui 1"read sa iasa din reNuest!ermit0 si sa execute operatia mutex.!0.1"read va cere

eventual si va primi permisiunea pentru operatia mutex.%0, completand reluarea.

modern_multithreading semafoare si zavoare versiune beta

Documents