verificarea programelor concurentesoftware.ucv.ro/~cbadica/scd/cap3.pdfcuvinte a p –daca p si q...
TRANSCRIPT
2018 - 2019
Verificarea programelor concurente
Capitolul 3
2018 - 2019
Rezumat
• Invarianti
• Logica temporala liniara – LTL
• Demonstrarea deductiva a corectitudinii
• Verificarea modelelor
• Algoritmi avansati pentru sectiunea critica
2018 - 2019
Specificarea logica a corectitudinii
• Se considera multimea de variabile VP asociata unui program
concurent P formata din:
– multimea variabilelor globale si locale
– pointerii de control ai proceselor unui program concurent.
• Cu ajutorul acestei multimi de variabile se construiesc
propozitii atomice de forma:
– v = valoare
– v valoare
• Simplificari ale notatiei, in functie de domeniul variabilelor:
– Daca v este o variabila Booleana atunci propozitia atomica v = true se
noteaza prin v si propozitia atomica v = false se noteaza prin v.
– Daca pc este o variabila ce reprezinta un pointer de control atunci
propozitia atomica pc = pi se noteaza prin pi.
2018 - 2019
Sintaxa proprietatilor de corectitudine
• Fie A multimea propozitiilor atomice.
• Multimea proprietatilor de corectitudine P se defineste astfel:
– Propozitiile atomice sunt proprietati de corectitudine, cu alte cuvinte A P
– Daca p si q sunt proprietati de corectitudine, adica p, q P atunci si formulele p q, p q, p q si p sunt proprietati de corectitudine, adica p q, p q, p q , p P
2018 - 2019
Semantica proprietatilor de corectitudine
• O stare a programului concurent P este o multime de asignari ale tuturor variabilelor din VP. Fie SP multimea acestor asignari. O stare a programului P este reprezentata de un element s SP.
• Semantica se defineste prin relatia de “interpretare” ⊨ : SP P.
– Daca v = valoare s atunci s ⊨ v = valoare
– Daca v = valoare s atunci s ⊨ v valoare
– Daca s ⊨ p si s ⊨ q atunci s ⊨ p q
– Daca s ⊨ p sau s ⊨ q atunci s ⊨ p q
– Daca s ⊭ p este fals atunci s ⊨ p
– Daca s ⊨ p q atunci s ⊨ p q
2018 - 2019
Sectiune critica V3
boolean wantp false
boolean wantq false
p q
loop forever
p1: sectiune non-critica
p2: wantp true
p3: await wantq = false
p4: sectiune critica
p5: wantp false
loop forever
q1: sectiune non-critica
q2: wantq true
q3: await wantp = false
q4: sectiune critica
q5: wantq false
A treia incercare
Sursa: M.Ben-Ari, 2006
• Formula p1 q1 wantp wantq este adevarata doar in starea pcp = p1, pcq = q1, wantp = false, wantq = false
• Formula p4 q4 este adevarata cand procesele se afla simultan in sectiunea critica. O conditie de excludere mutuala este (p4 q4).
2018 - 2019
Demonstrarea prin inductie a invariantilor
• Un invariant este o formula logica care este adevarata in
fiecare stare a unui program concurent.
• Deoarece algoritmul “Sectiune critica V3” verifica proprietatea
de excludere mutuala, formula (p4 q4) este un invariant.
• Invariantii I se demonstreaza prin inductie matematica:
– Se demonstreaza ca I este adevarat in starea initiala
– Se presupune ca I este adevarat pentru toate starile pana in starea
curenta si se demonstreaza ca I este adevarat in starea urmatoare.
2018 - 2019
Exemplu
• Notatie: O formula disjunctiva pi pi+1 … pj, unde pk
pentru k = i, i+1, …, j sunt instructiuni succesive in acelasi
proces se noteaza simplificat prin pi..j.
• Propozitie: In cazul algoritmului “Sectiune critica V3”:
a. Formula A p3..5 wantp este un invariant.
b. Formula B wantp p3..5 este un invariant.
c. Formulele p3..5 wantp si q3..5 wantq sunt invarianti
d. Formula (p4 q4) este un invariant.
• Observatii:
– Este suficient sa demonstram a, deoarece b rezulta prin analogie.
– Punctul c rezulta considerand formulele simetrice cu cele din a si b si
combinand toate cele 4 formule.
– Rezulta ca e suficient sa demonstram a si apoi d.
2018 - 2019
Demonstratia punctului a
• Pasul initial e trivial deoarece p3..5 = false si wantp = false.
• In pasul inductiv, intai observam ca executia procesului q nu
afecteaza valoarea formulei. Daca suntem in p1 nu este afectata
valoarea de adevar a formulei. Daca suntem in p3 sau p4 atunci
nu se schimba valorile lui wantp si p3..5, astfel ca invariantul
se pastreaza.
• Daca suntem in p2 atunci in starea urmatoare wantp devine
true, iar p3..5 devine true, asa ca invariantul se pastreaza.
• Daca suntem in p5 atunci in starea urmatoare wantp devine
false si p3..5 devine false, deci invariantul se pastreaza.
• Tema: de demonstrat similar formula B de la punctul b
2018 - 2019
Demonstratia punctului d
• (p4 q4) este invariant dnd p4 q4 este falsa in fiecare
stare.
• p4 q4 este falsa in starea initiala. Presupunem prin absurd ca
ar exista o stare care ar face formula p4 q4 adevarata.
Aceasta stare ar trebui sa fie determinata de instructiunile p3
sau q3. Astfel ca avem doua cazuri:
– (i) fie q se afla deja in q4 si p executa p3,
– (ii) fie p se afla deja in p4 si q executa q3. Datorita simetriei putem
considera doar primul caz.
• Executia lui p3 reuseste doar daca wantq este false. De aici
rezulta ca q3..5 (punctul c de la propozitia anterioara) este
falsa, de unde rezulta q4 este false, contradictie !
2018 - 2019
Logica temporala
• In logica clasica, valoarea de adevar a unei propozitii este statica. Nu se schimba in timp.
• In programare putem defini o propozitie wantp care este false la inceput, apoi devine true, ulterior devine iar false, s.a.m.d. Valoarea de adevar este dinamica, se schimba in timp (depinde de starea curenta a calculului)
• Logica temporala extinde logica clasica (propozitii, predicate) cu operatori temporali, care permit rationamentul cu valori de adevar care se schimba in timp, de-alungul unei cai de calcul.
wantp
time
false
true
2018 - 2019
Semantica logicii temporale liniare – LTL
• Se numeste cale de calcul (engl. computation path) sau
scenariu o secventa de stari = [s0, s1, s2, …].
• In logica temporala liniara (engl. linear temporal logic –
LTL), semantica formulelor se defineste “interpretand” cai de
calcul, spre deosebire de logica propozitiilor, in care semantica
se defineste “interpretand” stari individuale.
• Fie CP multimea tuturor cailor de calcul intr-un program
concurent P si fie ⊨ : CP P, unde P este multimea formulelor.
• Pentru o cale de calcul = [s0, s1, s2, …], pentru j 0 se
noteaza cu j subcalea incepand de la starea j, adica:
j = [sj, sj+1, sj+2, …]
• Daca p este formula netemporala atunci ⊨ p dnd s0 ⊨ p.
2018 - 2019
Operatorul intotdeauna
• Operatorul temporal intotdeauna (engl.always, numit si necesar sau global) este desemnat prin ⃞ sau G (global).
⊨ ⃞p dnd pentru orice j 0 avem j ⊨ p
• O formula ⃞p desemneaza o proprietate de siguranta. Spre exemplu, excluderea mutuala in algoritmul “Sectiune critica V3” se exprima prin ⃞(p4 q4)
2018 - 2019
Operatorul eventual
• Operatorul temporal eventual (engl.sometime, numit si posibil sau viitor) este desemnat prin ⃟ sau F (engl. future).
⊨ ⃟p dnd exista j 0 astfel incat j ⊨ p
• O formula ⃟p desemneaza o proprietate de vivacitate.
• Lipsa infometarii procesului p in algoritmul “Sectiune critica V3” se exprima prin ⃞(p2 ⃟p4). Orice stare in care p2 este true este eventual urmata de o stare in care p4 este true, adica p intra in sectiunea critica.
2018 - 2019
Operatorul pana cand
• Operatorul temporal pana cand (engl.until) este desemnat prin U.
⊨ p1 U p2 dnd exista j 0 astfel incat j ⊨ p2 si pentru orice 0 k < j
avem k ⊨ p1.
• A este reprezentata cu linia gri si B cu linia neagra. Formula A este adevarata primele 5 stari, moment in care B devine adevarata. Deci, indiferent de ce urmeaza dupa acest moment (starea a cincea) concluzionam ca A U B este adevarata.
2018 - 2019
Versiunea “slaba” a operatorului pana cand
• Operatorul temporal pana cand slab (engl. weak until)
este desemnat prin W. El este definit astfel:
⊨ p1 W p2 dnd
(i) exista j 0 astfel incat j ⊨ p2 si pentru orice 0 k < j
avem k ⊨ p1 sau
(ii) pentru orice k 0 avem k ⊨ p1
• Spre deosebire de U, semantica lui W permite ca p2 sa
nu devina niciodata adevarat, caz in care p1 trebuie sa
fie mereu adevarat.
p U q ⃟q (p W q)
p W q ⃞p (p U q)
2018 - 2019
Operatorul urmator • Operatorul temporal urmator (engl.next) este desemnat prin ⃝ sau X.
⊨ ⃝p dnd 1 ⊨ p
• Deci ⃝p este adevarat in starea curenta daca p este adevarat in starea imediat urmatoare.
• Spre exemplu, se considera secventa de instructiuni urmatoare din cadrul aceluiasi proces p:
p1: integer x 0
p2: x 1
p3: x 2
• Ar putea parea intuitiv sa afirmam ca formula:
p3 ⃝(x = 2)
este adevarata. Insa, datorita intreteserii arbitrare a instructiunilor
procesului p cu ale altui proces, e posibil ca (x = 2) sa devina adevarata
nu neaparat in starea imediat urmatoare, ci pur si simplu intr-o stare
viitoare, adica:
p3 ⃟(x = 2)
2018 - 2019
Proprietatile operatorilor intotdeauna si eventual
• Reflexivitate: Operatorii intotdeauna si eventual includ “acum”:
⃞A A
A ⃟A
• Dualitate: Conform legii lui De Morgan, operatorii ⃞ si ⃟ sunt duali.
⃟A ⃞ A
⃞A ⃟ A
• Reguli de expansiune
p U q q ⃝(p (p U q))
⃟p p ⃝⃟p
⃞p p ⃝⃞p
• Idempotenta
⃞⃞p ⃞p
⃟⃟p ⃟p
• Distributivitatea lui ⃞ fata de si prin dualitate a lui ⃟ fata de
⃞(p q) ⃞p ⃞q Nu este adevarat pentru ⃟ !!
Tema: de demonstrat
2018 - 2019
Exemplu de deductie cu operatori temporali
• Proprietate: ⃟⃞p ⃟⃞q ⃟⃞(p q)
• Se demonstreaza aceasta proprietate pornind de la definitie:
• “”: Daca ⃟⃞p ⃟⃞q inseamna ca ⃟⃞p si ⃟⃞q. Deci la un rang i formula ⃞p devine adevarata si la un rang j formula ⃞q devine adevarata. Adica de la i incolo p este adevarata si de la j incolo q este adevarata, deci de la k = max(i,j) incolo p q este adevarata. Adica la rangul k formula ⃞(p q) este adevarata, de unde rezulta ca ⃟⃞(p q).
• “”: Daca ⃟⃞(p q) inseamna ca exista k astfel incat la rangul k avem ⃞(p q). Deci de la k incolo p q e adevarata, deci atat p cat si q sunt separat adevarate. Rezulta ca la rangul k formulele ⃞p si sunt ⃞q adevarate. Adica ⃟⃞p si ⃟⃞q sunt adevarate, deci si conjunctia lor ⃟⃞p ⃟⃞q este adevarata.
2018 - 2019
Algoritmul lui Dekker
boolean wantp false
boolean wantq false
interger turn 1
p q
loop forever
p1: sectiune non-critica
p2: wantp true
p3: while wantq = true
p4: if turn = 2
p5: wantp false
p6: await turn = 1
p7: wantp true
p8: sectiune critica
p9: turn 2
p10: wantp false
loop forever
q1: sectiune non-critica
q2: wantq true
q3: while wantp = true
q4: if turn = 1
q5: wantq false
q6: await turn = 2
q7: wantq true
q8: sectiune critica
q9: turn 1
q10: wantq false
Algoritmul lui Dekker
Sursa: M.Ben-Ari, 2006
2018 - 2019
Demonstratia algoritmului Dekker
• Propozitie: Urmatoarele formule sunt invarianti (un invariant corespunde unei formule ⃞):
a. ⃞(turn = 1 turn = 2) (Invt)
b. ⃞(p3..5 p8..10 wantp) (Invp)
c. ⃞(q3..5 q8..10 wantq) (Invq)
d. ⃞(p8 q8) (excludere mutuala)
• Demonstratie:
a, b si c rezulta din structura algoritmului
Pasul inductiv la d rezulta prin reducere la absurd. Singura modalitate de
a ajunge in (p8 q8) este ca sa avem q8 si p sa fie in p3 sau sa avem p8
si q sa fie in q3. Se considera primul caz. Daca p se afla in p3 si de aici
se ajunge in p8 inseamna ca wantq = false. Dar conform c ar rezulta ca
q8 este fals, contradictie.
• Observatie: Metoda invariantilor se poate folosi doar la demonstrarea proprietatilor de siguranta, nu si a celor de vivacitate !
2018 - 2019
Demonstrarea progresului
• Proprietate de progres: daca s-a ajuns intr-o stare ce
satisface A atunci calculul va trebui sa progreseze intr-
o stare in care este adevarat B. Adica:
⃞(A ⃟B)
• In cadrul deductiilor se foloseste regula de echitate:
– daca o instructiune a unui proces devine activata continuu
atunci ea eventual va fi executata.
2018 - 2019
Instructiuni de atribuire
• Daca numaratorul de program al unui proces p a ajuns
la o instructiune de atribuire:
pi: var expresie
atunci (conform echitatii) ea va fi executata. Deci
exista doua stari s si t astfel incat t se obtine din s prin
incrementarea numaratorului de program al lui p si
modificarea valorii lui var la valoarea expresie: pi, …
pi+1, var = expresie, …
2018 - 2019
Progres / non-progres in sectiunea critica /
necritica
• Prin ipoteza, procesele progreseaza in sectiunea critica. Pentru
algoritmul Dekker:
⃞(p8 ⃟p9)
• Ipoteza nu este valabila in sectiunea necritica. Nu stim ca:
⃞(p1 ⃟p2)
• Astfel este posibil ca procesul p sa ramana indefinit in
sectiunea necritica, adica ⃟⃞p1.
2018 - 2019
Progres pentru instructiuni de control
• Exemplu: in algoritmul Dekker, nu putem concluziona
urmatoarea proprietate de progres, desi pare intuitiva:
⃞((p4 (turn = 2)) ⃟p5)
• Justificare: daca p se afla in p4 si turn = 2, se poate intampla ca
prin intretesere q sa apuce sa executa instructiunea de la q9 ce
va face turn = 1 si astfel cand p va executa pasul p4, va trece la
p3, nu p5 !
• Rationamentul corect se bazeaza pe regula urmatoare:
⃞((p4 ⃞(turn = 2)) ⃟p5)
2018 - 2019
Regula de demonstrare a progresului
• Propozitie: daca formulele:
⃞A ⃟B
⃟⃞A
sunt adevarate atunci va rezulta ca ⃟B este adevarata.
• Demonstratie:
Intuitiv aceasta regula seamana cu modus ponens. Regula a
doua ne spune ca A este indefinit adevarata de la un moment
dat incolo. Atunci, conform primei reguli, aplicata de la acel
moment, B va fi eventual adevarata, c.c.t.d.
2018 - 2019
Progres in algoritmul lui Dekker
• Proprietatea de progres se exprima prin:
“Daca p intra in sectiunea de preprotocol atunci p eventual va
intra in sectiunea critica”
⃞(p2⃟p8)
• Se considera doua cazuri:
– (i) q eventual ramane in sectiunea necritica, adica ⃟⃞q1 si
– (ii) q paraseste intotdeauna sectiunea necritica, adica
⃟⃞q1 ceea ce este echivalent cu ⃞⃟q1.
2018 - 2019
Lema
• Se considera ca suntem in cazul (ii).
• Daca p insista sa intre in sectiunea critica atunci eventual q ii
va ceda locul, adica:
(⃞wantp ⃞turn=1) ⃟⃞wantq
• Demonstratie:
Din ipoteza de progres a lui q rezulta ca q ajunge in q2.
Din progresul atribuirii, q ajunge din q2 in q3
Din ipoteza ⃞wantp si progres in bucla while, q va ajunge la q4
Din ipoteza ⃞turn=1 si progres la if, q va ajunge la q5
Din progresul atribuirii, q ajunge din q5 in q6
Deoarece ⃞turn=1, q va ramane la q6
Din Invq rezulta ca eventual wantq si va ramane asa, adica ⃟⃞wantq
2018 - 2019
Demonstratie progres
• Presupunem prin absurd ca (⃞(p2⃟p8)) adica ⃟(p2 ⃟p8).
Inseamna ca exista o cale de calcul si o stare in care sa avem p2 ⃟p8.
• Sa presupunem ca ⃞turn=2. Acest lucru inseamna ca:
Procesul p progreseaza la instructiunea de atribuire de la p2 la p3
Prin progres la p3, avand in vedere ca ⃟p8, rezulta ca p intra in bucla while la p4.
Conform ipotezei ⃞turn=2, p progreseaza la instructiunea if in p5
Procesul p progreseaza la instructiunea de atribuire de la p5 la p6
Conform ipotezei ⃞turn=2, p ramane la p6
Dar din invariantul Invp rezulta ca eventual wantp si va ramane asa, adica
⃟⃞wantp.
Din ipoteza de progres a lui q rezulta ca q va progresa (ca in cazul lemei) dincolo de q6,
va iesi din bucla si va ajunge in q9
Apoi q va progresa la q10 si vom avea eventual turn=1 adica ⃟turn=1, contradictie !
In concluzie rezulta ca ⃞turn=2, adica ⃟turn=1.
2018 - 2019
Continuare demonstratie progres
• Din p2 ⃟p8 rezulta ca p nu va ajunge la p9 sa poata
executa turn 2. Conform demonstratiei de pana acum am
aratat ca eventual turn va deveni 1 adica ⃟turn=1. Rezulta ca
eventual turn va ramane 1 adica ⃟⃞turn=1.
• Rezulta ca procesul p se va bucla la while in p3 executand doar
p3 si p4. Acest lucru inseamna ca wantp ramane true adica
⃞wantp. Apoi din lema rezulta ca ⃟⃞wantq, contradictie cu
faptul ca p se bucleaza la p3 si p4 fara sa intre in sectiunea
critica.
2018 - 2019
Modelare & verificare vs programare &
testare
Model
Diagrama de stare
Proprietati
Logica temporala
Program
concurent
Cerinte de
comportament
Structura Proprietati
Lume formala abstracta
(matematica)
Lume fizica reala
(programare)
Verificare
Modelare Formalizare
Testare
2018 - 2019
Limbajul Promela
• Un program Promela este compus din:
– declaratii de variabile globale si
– o multime de procese
• Un proces contine:
– declaratii de variabile locale si
– o secventa instructiuni.
• Pe baza starii curente o instructiune poate fi:
– Executabila: poate fi imediat executata
– Blocata: nu poate fi executata
2018 - 2019
Instructiuni Promela
• Atribuire. Intotdeauna executabila.
wantp = true;
• Asertiune. Intotdeauna executabila.
assert(critical <= 1);
• Afisare. Intotdeauna executabila.
printf(“Salut\n”);
• Expresie. Executabila daca expresia nu este zero.
turn == 1;
2018 - 2019
Structuri de control
• O comanda cu garzi are sintaxa: ::alegere -> instr ; instr ; ...
• O structura de control are sintaxa: {if | do}
::alegere -> instr ; instr ; ...
::alegere -> instr ; instr ; ...
...
::alegere -> instr ; instr ; ...
[::else -> instr ; instr ; ...]
{fi| od}
• Daca exista cel putin o alegere adevarata atunci se va alege in mod nedeterminist una spre executie.
• Daca nici o alegere nu este adevarata atunci instructiunea se blocheaza.
• Clauza else este optionala. Cand exista, devine adevarata daca nici una dintre alegeri nu este adevarata.
• do reia alegerea, iar if termina instructiunea dupa prima alegere.
2018 - 2019
Algoritmul Dekker in limbajul Promela
bool wantp = false, wantq = false;
byte turn = 1;
active proctype p() {
do
:: wantp = true;
do
:: wantq ->
if
:: (turn == 2) ->
wantp = false; turn == 1; wantp = true
:: else
fi
:: else -> break
od;
printf(“P se afla in sectiunea critica\n”);
turn = 2;
wantp = false
od
}
Ramura else evita blocarea if-ului
Se iese din bucla do
2018 - 2019
Verificarea excluderii mutuale in SPIN
• Se pot folosi variabile auxiliare.
• Pentru problema sectiunii critice putem folosi un contor critical
initializat cu 0. Ori de cate ori un proces intra in SC, contorul
este incrementat.
• Pentru a verifica excluderea mutuala, si anume ca cel mult un
proces este la un moment dat in SC, putem introduce in SC a
fiecarui proces urmatorul cod ce contine o asertiune:
critical++;
assert(critical <= 1);
critical--;
2018 - 2019
Verificarea lipsei infometarii in SPIN
• Pentru problema SC putem folosi 2 variabile booleene
auxiliare, cate una pe proces, initializate cu false. bool csp = false;
bool csq = false;
• Cand un proces intra in SC, variabila sa booleana devine true,
apoi iar false. Procesul p contine in sectiunea sa critica codul: csp = true;
csp = false;
• Lipsa infometarii procesului p se descrie cu formula LTL:
[]<>csp
• Ea se poate adauga la program pentru verificare cu sintaxa:
ltl { []<>csp }
• Tema: Sa se verifice excluderea mutuala printr-o formula LTL.
2018 - 2019
Algoritmul bakery pentru doua procese
integer np 0, nq 0
p q
loop forever
p1: sectiune non-critica
p2: np nq + 1
p3: await nq = 0 or np nq
p4: sectiune critica
p5: np 0
loop forever
q1: sectiune non-critica
q2: nq np + 1
q3: await np = 0 or nq < np
q4: sectiune critica
q5: nq 0
Algoritmul Bakery (propus de Leslie Lamport)
Sursa: M.Ben-Ari, 2006 Instructiunile din p2 si q2 sunt atomice. Aceasta
presupunere este uneori nerealista.
Tema: sa se analizeze acest algoritm in ipoteza ca
aceste instructiuni se implementeaza cu load si store
in maniera clasica.
2018 - 2019
Descrierea algoritmului Bakery
• Fiecare proces primeste un bilet numerotat, inainte de a intra in
SC. El asteapta ca numarul sau sa devina cel mai mic dintre
biletele aflate in asteptare, apoi intra in SC.
• np si nq sunt numerele biletelor celor 2 procese.
• Valoarea 0 indica faptul ca procesele nu doresc sa intre in SC.
O valoare pozitiva reprezinta o coada implicita a proceselor ce
doresc sa intre in SC. Procesele cu o valoare mai mica a
numarului de pe bilet se afla mai in fata in aceasta coada.
• In cazul in care cele doua procese au numere egale pe bilete, se
da prioritate procesului p (la p3 avem np nq, iar la q3 avem
nq < np).
2018 - 2019
Invarianti ai algoritmului Bakery
• Lema. Urmatoarele formule sunt invarianti
a. np = 0 p1 p2 (Inva)
b. nq = 0 q1 q2 (Invb)
c. p4 (nq = 0) (np nq) (Invc)
d. q4 (np = 0) (nq < np) (Invd)
• Demonstratie
a si b rezulta trivial din structura. Demonstram c, d rezulta prin simetrie.
Initial Invc este adevarat. Presupunem Invc adevarat la pasul curent.
i. Invc este adevarat deoarece p4 este fals. Daca prin absurd Invc ar deveni fals prin
devenirea lui p4 adevarat, inseamna ca p executa p3. Insa astfel ar trebui sa avem
conditia (nq = 0) (np nq) adevarata, contradicitie !
ii. Invc este adevarat deoarece p4 si (nq = 0) (np nq) sunt adevarate. Daca in
pasul urmator Invc ar deveni fals, ar trebui ca (nq = 0) (np nq) sa devina fals. p
ramane la p4, doar q poate schimba variabilele la q2 sau q5. Dupa q2 conditia np
nq ramane adevarata. Dupa q5 conditia nq = 0 ramane adevarata. Contradictie !
2018 - 2019
Excluderea mutuala in algoritmul Bakery
• Combinand Invc si Invd rezulta ca:
p4 q4 ((nq = 0) (np nq)) ((np = 0) (nq < np))
• Dar, daca p4 q4 atunci din Inva si Invb rezulta ca nq 0 si np
0. Rezulta ca va ramane doar implicatia:
p4 q4 (np nq) (nq < np)
• Insa (np nq) (nq < np) este falsa, de unde rezulta ca:
(p4 q4)
• Acest invariant exprima proprietatea de excludere mutuala.
2018 - 2019
Lipsa infometarii in algoritmul Bakery
• Faptul ca p nu este infometat se exprima prin ⃞(p2 ⃟p4).
• Presupunem prin absurd ca exista o stare in care p2 ⃟p4 este fals, adica p2 si ⃟p4 sunt adevarate.
• Prin progres al lui p la atribuirea p2, p3 devine adevarata. Dar corelat cu ⃟p4 inseamna ca p3 va ramane adevarata, adica ⃟⃞p3. Dar, conform Inva, vom avea ⃟⃞(np=k) pentru un k>0. Deoarece p ramane in p3, instructiunea p3 nu va progresa, desi procesul p va executa instructiunea (conform echitatii), gasind conditia falsa. Rezulta ca: ⃞⃟((nq = 0) (np nq)).
• Rezulta ca ⃞⃟(nq 0) ⃞⃟(nq < np). Din ⃞⃟(nq 0) rezulta ca q paraseste SC de o infinitate de ori deci prin progres va executa q2 de o infinitate de ori. Insa din ⃟⃞(np=k) va rezulta ca ⃟⃞(nq=k+1) cu k>0, ce contrazice ⃞⃟(nq < np) !
2018 - 2019
Algoritmul bakery pentru N procese
integer array[1..N] number [0,. …, 0]
pi
loop forever
p1: sectiune non-critica
p2: number[i] 1 + max(number)
p3: for all other processes j
p4: await (number[j] = 0) or (number[i] ≪ number[j])
p5: sectiune critica
p6: number[i] 0
Algoritmul Bakery pentru N procese
Sursa: M.Ben-Ari, 2006
(number[i] ≪ number[j]) (number[i] < number[j])
((number[i] = number[j]) (i < j))
2018 - 2019
Observatii
• Instructiunea de determinare a maximului dintr-un vector este
considerata atomica. Aceasta presupunere se poate inlatura cu
un artificiu (vezi versiunea urmatoare a algoritmului).
• Algoritmul Bakery este elegant deoarece fiecare variabila
globala este scrisa de exact un proces.
• Dezavantaje:
– Daca intotdeauna unul dintre procese se afla in sectiunea critica atunci
numerele biletelor pot creste indefinit
– Fiecare proces va trebui sa evalueze biletele tuturor celorlalte procese,
chiar daca nici unul dintre ele nu vrea sa intre in SC.
2018 - 2019
Algoritmul bakery pentru N procese
integer array[1..N] number [0,. …, 0]
boolean array[1..N] choosing [false, ..., false]
pi
loop forever
p1: sectiune non-critica
p2: choosing[i] true
p3: number[i] 1 + max(number)
p4: choosing[i] false
p5: for all other processes j
p6: await choosing[i] = false
p7: await (number[j] = 0) or (number[i] ≪ number[j])
p8: sectiune critica
p9: number[i] 0
Algoritmul Bakery fara atribuire atomica
Sursa: M.Ben-Ari, 2006
2018 - 2019
Tema
• Sa se implementeze algoritmul Bakery folosind
interfata Lock din Java. Pentru a determina indexul
firului curent se va folosi clasa ThreadID introdusa in
cursul 2.