Comert electronic si securitatea datelor - software.ucv.rosoftware.ucv.ro/~cbadica/scd/cap8.pdf ·...

2018-2019

Liniarizabilitate

Capitolul 8

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

Exemplul 1

time

2018-2019

Exemplul 1

time

q.enq(x)

2018-2019

Exemplul 1

time

q.enq(x)

q.enq(y)

2018-2019

Exemplul 1

time

q.enq(x)

q.enq(y) q.deq(x)

2018-2019

Exemplul 1

time

q.enq(x)

q.enq(y) q.deq(x)

q.deq(y)

2018-2019

Exemplul 1

q.enq(x)

q.enq(y) q.deq(x)

q.deq(y)

time

2018-2019

Exemplul 2

time

2018-2019

Exemplul 2

time

q.enq(x)

2018-2019

Exemplul 2

time

q.enq(x) q.deq(y)

2018-2019

Exemplul 2

time

q.enq(x) q.deq(y)

q.enq(y)

2018-2019

Exemplul 2

time

q.deq(y) q.enq(x)

q.enq(y)

2018-2019

Exemplul 3

time

2018-2019

Exemplul 3

time

q.enq(x)

2018-2019

Exemplul 3

time

q.enq(x)

q.deq(x)

2018-2019

Exemplul 3

q.enq(x)

q.deq(x)

time

2018-2019

Exemplul 4

q.enq(x)

time

2018-2019

Exemplul 4

q.enq(x)

time

q.enq(y)

2018-2019

Exemplul 4

q.enq(x)

time

q.enq(y)

q.deq(y)

2018-2019

Exemplul 4

q.enq(x)

time

q.enq(y)

q.deq(y)

q.deq(x)

2018-2019

Exemplul 4

q.enq(x)

q.enq(y)

q.deq(y)

q.deq(x)

time

2018-2019

Registru R/W 1

read(1) write(0)

write(1)

write(2)

read(0)

time

2018-2019

Registru R/W 1

read(1) write(0)

write(1)

write(2)

read(0)

write(1) a avut loc deja

2018-2019

Registru R/W 1

read(1) write(0) write(2)

read(0)


write(1)

2018-2019

Registru R/W 2

read(1) write(0)

write(1)

write(2)

read(1)


2018-2019

Registru R/W 2

read(1) write(0)

read(1)


write(1)

write(2)

2018-2019

Registru R/W 3

write(0)

write(1)

write(2)

read(1)

time

2018-2019

Registru R/W 3

write(0)

read(1) write(1)

write(2)

time

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

Exemplu

A q.enq(x)

fir

obiect

metoda

argumente

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

Exemplu

A q: void

fir

obiect

rezultat

2018-2019

Exemplu

A q: empty()

fir

obiect

exceptie

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 =


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 𝐴.


H =


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


Invocare in asteptare

H =

2018-2019



Efectul sau ar fi putut sau nu sa aiba loc

H =

2018-2019



Elimina invocarile in asteptare

H =

2018-2019



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


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


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=


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=


Firele 𝐴 si 𝐵 observa acelasi

lucru in istoriile 𝐻 si 𝐺


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

Ce inseamna →𝒢 ⊆ →𝒮 ?

→𝒢= *𝑎 → 𝑐, 𝑏 → 𝑐+

→𝒮= *𝑎 → 𝑏, 𝑎 → 𝑐, 𝑏 → 𝑐+

time

a

b

time S

c G

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


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


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


time

B.q.enq(4) B.q.deq(4)

A.q.enq(3)

2018-2019

Exemplu


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

Exemplu

time

q.enq(x)

q.enq(y)

q.deq(y)

2018-2019

Exemplu

time

q.enq(x)

q.enq(y)

q.deq(y) q.enq(x)

q.enq(y)

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.

Comert electronic si securitatea datelor - software.ucv.rosoftware.ucv.ro/~cbadica/scd/cap8.pdf ·...

Documents

Transcript of Comert electronic si securitatea datelor - software.ucv.rosoftware.ucv.ro/~cbadica/scd/cap8.pdf ·...