Post on 15-Sep-2019
2018-2019
Recapitulare principii
• Principiul I. Invocarile de metode trebuie sa para ca fiind
executate una-cate-una intr-o ordine secventiala. Obs. Ordinea
nu conteaza, important este ca executia sa para secventiala.
• Principiul II. Invocarile de metode separate de un interval
pasiv trebuie sa apara ca fiind executate conform ordinii lor
reale de executie. Obs. Trebuie respectata ordinea temporala
reala a executiei instructiunilor, in ceea ce priveste intervalele
de pasivitate.
• Principiul III. Invocarile de metode trebuie sa para ca fiind
executate conform ordinii programului lor. Obs. Trebuie
respectata ordinea de scriere a instructiunilor in program (in
cadrul fiecarui fir).
2018-2019
Principiul IV
• Principiul IV. Fiecare invocare de metoda trebuie sa
para ca are un efect instantaneu la un moment intre
invocare si raspuns numit punct de liniarizare.
• Conform acestui principiu, ordinea reala a invocarilor
trebuie pastrata. Practic, ordonarea se refera la punctele
de liniarizare.
• Principiul IV defineste o constrangere mai puternica
asupra ordinii executiei instructiunilor decat principiul
III. Se inlocuieste principiul III cu IV.
2018-2019
Liniarizabilitate
• Proprietate de corectitudine care cere respectarea
principiilor I si IV se numeste linearizabilitate
(engl.linearizability).
• Orice executie linearizabila este secvential consistenta,
insa reciproca nu este adevarata !
• Liniarizabilitatea este o proprietate referitoare la
executiile uni obiect concurent.
• Obiect liniarizabil = obiect ale carui executii sunt toate
liniarizabile.
2018-2019
Punctul de liniarizare depinde de executie
• Punctul de liniarizare nu poate fi intodeauna specificat
fara a avea in vedere o anumita executie a unei metode.
• In anumite situatii punctul de liniarizare depinde
(difera) in functie de o anumita executie a metodei.
2018-2019
Eveniment de invocare de metoda
• Un eveniment de invocare (de metoda) se
noteaza prin:
𝐴 𝑥. 𝑚(𝑎∗)
unde: – 𝐴 este firul in care are loc invocarea
– 𝑥 este obiectul asupra caruia are loc invocarea
– 𝑚 este metoda invocata
– 𝑎∗ reprezinta argumentele invocarii
2018-2019
Eveniment raspuns
• Un eveniment raspuns se noteaza prin
𝐴 𝑥 ∶ 𝑟∗ sau 𝐴 𝑥 ∶ 𝑡()
unde: – 𝐴 este firul in care are loc raspunsul
– 𝑥 este obiectul din care s-a generat raspunsul
– 𝑡 este un nume de exceptie
– 𝑟∗ reprezinta rezultatul raspunsului.
• Observatie: metoda care a generat raspunsul
rezulta implicit din context
2018-2019
Istoria executiei
• Executia unui sistem concurent defineste o istorie =
secventa finita de evenimente de invocare si
evenimente raspuns.
• O subistorie a unei istorii ℋ = subsecventa a lui ℋ.
A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3
Secventa de invocari si raspunssuri
H =
2018-2019
Identificarea dintre invocare si raspuns
• Un raspuns si o invocare se identifica (engl. match) dnd ele
contin acelasi obiect 𝑥 si acelasi fir 𝐴.
• Se numeste apel de metoda (engl. method call) in istoria ℋ o
pereche formata dintr-o invocare si urmatorul raspuns cu care
ea se identifica.
A q.enq(3)
A q:void
Acelasi fir Acelasi obiect
Method call
2018-2019
Subistorie a unui obiect
• Se numeste subistorie a unui obiect 𝑥 o subsecventa notata cu
ℋ│𝑥 a lui ℋ care contine toate evenimentele lui ℋ
corespunzatoare obiectului 𝑥.
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3
H =
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3
H|q =
2018-2019
Subistorie a unui fir
• Se numeste subistorie a unui fir 𝐴 o subsecventa notata cu
ℋ│𝐴 a lui ℋ care contine toate evenimentele lui ℋ
corespunzatoare firului 𝐴.
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3
H =
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3
H|B =
2018-2019
Subistorie completa
• 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒(ℋ) reprezinta subistoria lui ℋ formata din
invocarile si raspunsurile care se identifica.
• O invocare este in desfasurare (engl. pending) dnd ea
nu este urmata de un raspuns cu care se identifica.
2018-2019
Subistorie completa – exemplu
A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3
Invocare in asteptare
H =
2018-2019
Subistorie completa – exemplu
A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3
Efectul sau ar fi putut sau nu sa aiba loc
H =
2018-2019
Subistorie completa – exemplu
A q.enq(3) A q:void A q.enq(5) B p.enq(4) B p:void B q.deq() B q:3
Elimina invocarile in asteptare
H =
2018-2019
Subistorie completa – exemplu
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3
Complete(H) =
2018-2019
Subistorie secventiala
• O istorie ℋ se numeste secventiala dnd primul eveniment al lui
ℋ este o invocare si fiecare invocare (posibil exceptand-o pe
ultima) este urmata de un raspuns cu care se identifica.
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5)
2018-2019
Subistorie secventiala
A q.enq(3)
A q:void
B p.enq(4)
B p:void
B q.deq()
B q:3
A q:enq(5)
identificare
identificare
identificare
Invocare finala in asteptare OK
2018-2019
Subistorie secventiala
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3 A q:enq(5)
identificare
identificare
identificare
Invocare finala in asteptare OK
2018-2019
Istorie bine formata
• O istorie ℋ este bine-formata dnd subistoriile firelor sunt
secventiale (acest lucru nu este necesar pentru subistoriile
obiectelor).
H=
A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3
2018-2019
Istorie bine formata
H=
A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3
H|B=
B p.enq(4) B p:void B q.deq() B q:3
A q.enq(3) A q:void
H|A=
2018-2019
Istorii echivalente
• Doua istorii ℋ si ℋ′ sunt echivalente dnd pentru orice fir 𝐴
avem ℋ│𝐴 = ℋ′│𝐴.
H=
A q.enq(3) B p.enq(4) B p:void B q.deq() A q:void B q:3
Firele 𝐴 si 𝐵 observa acelasi
lucru in istoriile 𝐻 si 𝐺
A q.enq(3) A q:void B p.enq(4) B p:void B q.deq() B q:3
G=
H|A = G|A H|B = G|B
2018-2019
Specificatie secventiala
• Pentru a determina daca un obiect este corect, va trebui sa
verificam ca orice istorie secventiala a obiectului este legala
(permisa) pentru obiectul respectiv (adica verifica preconditiile
si postconditiile obiectului).
• O specificatie secventiala a unui obiect este o metoda de a
descrie daca o istorie secventiala a unui obiect (ce implica un
singur fir) este legala.
• Pentru aceasta se pot folosi diverse metode: – Pre- si post-conditii
– Alte metode: automate, expresii regulale, etc.
2018-2019
Istorii legale
• O istorie secventiala (multi-obiect) ℋ este
legala dnd: –pentru orice obiect 𝑥
– subistoria ℋ│𝑥 este legala conform
specificatiei secventiale a obiectului 𝑥.
2018-2019
Precedenta metodelor
• Apelul de metoda 𝑚0 precede apelul de metoda 𝑚1 in istoria
ℋ dnd raspunsul lui 𝑚0 s-a terminat inaintea invocarii lui 𝑚1.
Aceasta se noteaza cu 𝑚0 →ℋ 𝑚1.
• Relatia →ℋ este: – ordine partiala (tranzitiva si pentru orice 𝑚 avem ¬ (𝑚 →ℋ 𝑚).
– ordine totala daca ℋ este secventiala.
A q.enq(3) B p.enq(4) B p.void A q:void B q.deq() B q:3
Method call Method call
2018-2019
Ne-precedenta
A q.enq(3) B p.enq(4) B p.void B q.deq() A q:void B q:3
Apeluri de metode suprapuse
Method call
Method call
2018-2019
Definitia liniarizarii
• Ideea liniarizarii este ca orice istorie este echivalenta cu o
istorie secventiala cu respectarea regulilor: – Daca un apel de metoda precede alt apel de metoda, atunci primul apel
trebuie sa produca efect asupra obiectului inaintea celuilalt apel.
– Daca doua apeluri se suprapun atunci ordinea lor este nedeterminata.
• O extensie a unei istorii ℋ se obtine adaugand raspunsuri la
unele dintre eventualele (zero sau mai multe) invocari in
astepare din ℋ.
• Definitie. O istorie ℋ se numeste liniarizabila dnd ea are o
extensie ℋ′ pentru care exista o istorie secventiala legala 𝒮 a.i.: – 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒(ℋ′) este echivalenta cu 𝒮 (unele invocari au produs efect
fara raspuns)
– If 𝑚0 →ℋ 𝑚1 atunci 𝑚0 →𝒮 𝑚1
2018-2019
Intuitia liniarizarii
• O istorie ℋ este liniarizabila dnd ea poate fi
transformata in istoria 𝒢 prin: – Adaugarea a zero sau mai multe raspunsuri pentru
unele invocari in asteptare
– Eliminarea celorlalte invocari in asteptare
astfel incat 𝒢 este echivalenta cu: – Istoria secventiala legala 𝒮
– →𝒢 ⊆ →𝒮
2018-2019
Exemplu
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 B q:enq(6)
time
B.q.enq(4)
A. q.enq(3)
B.q.deq(4) B. q.enq(6)
2018-2019
Exemplu
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 B q:enq(6)
time
B.q.enq(4)
A. q.enq(3)
B.q.deq(4) B. q.enq(6)
Completeaza aceasta invocare
in asteptare
2018-2019
Exemplu
Completeaza aceasta invocare
in asteptare
time
B.q.enq(4) B.q.deq(4) B. q.enq(6)
A.q.enq(3)
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 B q:enq(6) A q:void
2018-2019
Exemplu
time
B.q.enq(4) B.q.deq(4) B. q.enq(6)
A.q.enq(3)
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 B q:enq(6) A q:void
Elimina aceasta invocare
2018-2019
Exemplu
time
B.q.enq(4) B.q.deq(4) B. q.enq(6)
A.q.enq(3)
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 A q:void
Elimina aceasta invocare
2018-2019
Exemplu
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 A q:void
time
B.q.enq(4) B.q.deq(4)
A.q.enq(3)
2018-2019
Exemplu
A q.enq(3) B q.enq(4) B q:void B q.deq() B q:4 A q:void
time
B.q.enq(4) B.q.deq(4)
A.q.enq(3)
B q.enq(4) B q:void A q.enq(3) A q:void B q.deq() B q:4
Istorie secventiala echivalenta
2018-2019
Compozitionalitatea liniarizarii
• Teorema. O istorie ℋ este liniarizabila dnd pentru orice obiect
𝑥 subistoria ℋ│𝑥 este liniarizabila.
• Acest rezultat ne permite sa construim sisteme concurente
complexe in maniera modulara din obiecte liniarizabile. Aceste
obiecte pot fi construite si verificate separat, asigurand prin
compunerea lor un sistem concurent corect.
• Daca sistemul concurent s-ar baza pe o proprietate de
corectitudine necompozitionala, atunci trebuie satisfacute niste
constrangeri suplimentare asupra obiectelor componente pentru
a ne asigura ca sistemul este corect.
2018-2019
Liniarizarea – proprietate neblocanta
• Teorema. Fie 𝑖 𝑚 = 𝑃 𝑥. 𝑚(𝑎∗) o invocare in asteptarea
metodei totale 𝑚 intr-o istorie liniarizabila ℋ. Atunci exista un
raspuns 𝑟 𝑚 a.i. ℋ ⋅ 𝑟(𝑚) este liniarizabila.
• Demonstratie:
• Fie 𝒮 o liniarizare a lui ℋ. Daca 𝒮 contine un raspuns 𝑟(𝑚) la
𝑖 𝑚 atunci 𝒮 fiind si o liniarizare a lui ℋ ⋅ 𝑟(𝑚), rezulta cctd.
• Altfel, daca 𝑟(𝑚) nu apare in 𝒮 atunci nici 𝑟(𝑚) nu va aparea
nici in 𝒮 intrucat potrivit definitiei 𝒮 nu poate contine invocari
in asteptare. Deoarece metoda 𝑚 este totala rezulta ca exista un
raspuns 𝑟(𝑚) astfel incat istoria secventiala 𝒮′ = 𝒮 ⋅ 𝑖 𝑚 ⋅𝑟(𝑚) este legala. Atunci 𝒮′ este o liniarizare a lui ℋ ⋅ 𝑟(𝑚)
cctd.
2018-2019
Concluzii asupra liniarizarii
• Liniarizarea este o proprietate neblocanta – nonblocking, adica
nu forteaza blocarea unui fir care contine o invocare in
asteptare a unei metode totale.
• A nu se confunda aceasta afirmatie cu posibilitatea aparitiei de
(inter-)blocaje in scopul implementarii liniarizabilitatii unui
anumit obiect.
• Blocarea poate sa apara in cazul unor specificatii secventiale
partiale: daca un fir trebuie sa invoce o metoda partiala pentru
un obiect intr-o stare in care metoda nu este definita, solutia
naturala este asteptarea (blocarea) pana cand obiectul ajunge
intr-o stare pentru care metoda este definita.
• Liniarizabilitatea este o proprietate de corectitudine
corespunzatoare pentru sisteme concurente in timp-real.
2018-2019
• O istorie ℋ este consistenta secvential dnd ea
poate fi transformata in istoria 𝒢 prin: – Adaugarea a zero sau mai multe raspunsuri pentru
unele dintre invocarile in asteptare
– Eliminarea celorlalte invocari in asteptare
astfel incat 𝒢 este echivalenta cu: – Istoria secventiala legala 𝒮
– →𝒢 ⊆ →𝒮
Liniarizabilitate vs consistenta secventiala
Diferenta fata de liniarizabilitate
2018-2019
• Nu se pastreaza ordinea de timp real: – Nu se reordoneaza operatiile realizate de acelasi fir
– Se pot reodona operatiile nesuprapuse realizate de fire
diferite
• Este folosita adesea pentru a descrie arhitecturile
memoriei sistemelor multiprocessor
Consistenta secventiala
2018-2019
Principiul fanionului
• DACA – Alice scrie propria variabila si citeste variabila lui Bob
– Bob scrie propria variabila si citeste variabila lui Alice
• ATUNCI – Cel putin unul dintre Alice si Bob va observa ca variabila
celuilalt a fost scrisa
• Acest principiu reprezinta sablonul de baza pentru
majoritatea algoritmilor de excludere mutuala – Bakery
– Peterson
– Etc.
2018-2019
Principiul fanionului
• Vederea (proiectia) fiecarui fir a istoriei este secvential
consistenta.
• Intreaga istorie nu este secvential consistenta.
x.write(1) y.read(0)
y.write(1) x.read(0)
time
Alice
Bob
2018-2019
Discutie
• Majoritatea arhitectilor hardware considera ca
implementarea consistentei secventiale este prea
costisitoare pentru hardware-ul modern. Astfel ca: – Se incalca implicit principiul fanionului
– Exceptand situatiile cand se cere explicit respectarea sa
• Explicatie: – In sistemele multiprocesor moderne procesoarele nu citesc si
scriu direct din memorie
– Accesele la memorie sunt mult mai lente comparativ cu
viteza procesorului
– Astfel ca citirile si scrierile din/in memorie au loc prin
intermediul cache-ului.
2018-2019
Proprietati de siguranta
• Consistenta pasiva, consistenta secventiala si
liniarizabilitatea sunt proprietati de siguranta.
• O proprietate de siguranta ne spune cand o istorie a
executiei sistemului este corecta.
• O proprietate de siguranta nu ne spune nimic despre
progresul executiei. De acest aspect se ocupa
proprietatile de progres (vivacitate).
2018-2019
Progres
• O implementare se numeste blocanta (engl.blocking) daca o
intarziere intr-un fir poate impiedica progresul altor fire.
• Spre exemplu daca firul A invoca o metoda 𝑒𝑛𝑞() asupra unei
cozi vide la care accesul este controlat de un zavor si apoi se
opreste in mijlocul invocarii, iar un alt fir B invoca 𝑑𝑒𝑞(),
atunci conform liniarizarii apelul 𝑑𝑒𝑞() va avea un raspuns
(coada nu este blocanta), insa firul 𝐵 va fi intarziat atat timp cat
dureaza intarzierea lui 𝐴.
• Exemple de intarzieri in sisteme multiprocesor:
– Cache miss.
– Eroare de paginare (engl. page fault)
– Preem(p)tiune (engl. preemption) de catre nucleul sistemului de
operare
2018-2019
Metode wait-free
• Def: O metoda se numeste wait-free dnd ea garanteaza
ca orice apel al sau se termina intr-un numar finit de
pasi. Un obiect este wait-free dnd toate metodele sale
sunt wait-free. O clasa este wait-free dnd toate
instantele sale sunt wait-free. – O metoda wait-free se numeste bounded wait-free dnd
exista o margine superioara a numarului de pasi necesari
pentru executia metodei. Marginea superioara poate depinde
de numarul de fire.
– O metoda wait-free pentru care durata executiei sale nu
depinde de numarul de fire active se numeste population-
oblivious.
2018-2019
Metode lock-free
• Def: O metoda se numeste lock-free dnd infinit de des anumite
apeluri ale metodei se termina dupa un numar finit de pasi.
• Constrangerea lock-free este mai slaba decat wait-free, adica:
– Orice metoda wait-free este lock-free.
– O metoda lock-free poate produce infometarea unui fir apelant (de
multe ori aceasta infometare este foarte improbabila, asa ca se prefera
o solutie lock-free mai eficienta, fata de o solutie wait-free mai lenta.
• Proprietatea wait-free este utila pentru a specifica progresul la
nivel de metoda.
• Proprietatea lock-free este utila pentru a specifica progresul la
nivel de obiect.
2018-2019
Progres dependent
• Proprietatile de progres wait-free si lock-free garanteaza
progresul independent de planificatorul de fire (procese).
• Implementarea sectiunilor critice (prin blocare pentru excludere
mutuala) face apel la doua proprietati si anume:
– Lipsa interblocarii (engl. deadlock-free)
– Lipsa infometarii (engl. starvation-free)
• Acestea sunt proprietati de progres dependente, intrucat ele
depind de anumite presupuneri referitoare la platforma (s.o.):
– De exemplu, daca se garanteaza ca orice fir eventual paraseste
sectiunea critica (dpdv practic in timp util).
• Sincronizarea cu zavoare poate astfel garanta cel mult
proprietati de progres dependente. Totusi, zavoarele sunt utile
cand aparitia preemptiunii intr-o sectiune critica este rara.
2018-2019
Progres dependent neblocant
• Def.: Un apel de metoda se executa in izolare dnd nici un alt fir nu
executa nici un pas
• Def.: O metoda este obstruction-free dnd din orice punct de la care ea se
executa in izolare, ea se va termina intr-un numar finit de pasi.
• Proprietate: O metoda lock-free este obstruction-free. Se considera o
secventa infinita de invocari ale metodei. Fie in acest sir o invocare astfel
incat de la un punct incolo ea se executa in izolare. Inseamna ca celelalte
apeluri realizate pana atunci fie s-au terminat (deci un numar finit s-au
terminat), fie sunt in desfasurare. Astfel ca daca invocarea nu se termina,
nici celelalte apeluri aflate in desfasurare nu se vor termina, deoarece
apelul se executa in izolare. Astfel cel mult un numar finit de invocari din
sirul infinit se vor termina, contradictie !
• Reciproca este falsa: un fir concurent poate face o invocare oricat de
tarziu dupa apelul in izolare, iar acea invocare poate avea un raspuns,
astfel ca metoda este lock-free, dar nu obstruction-free.
2018-2019
Rezumat conditii de progres
• Deadlock-free: unul dintre firele ce incearca achzitia zavorului eventual
reuseste.
• Starvation-free: orice fir ce incearca achzitia zavorului eventual reuseste
• Lock-free: unul dintre firele ce apeleaza o metoda eventual intoarce un
rezultat pentru apel.
• Wait-free: orice fire ce apeleaza o metoda eventual intoarce un rezultat
pentru apel.