structuri de date concurente - software.ucv.rosoftware.ucv.ro/~cbadica/scd/cap9.pdf · –initial p...

2018-2019

Structuri de date concurente

Capitolul 9

2018-2019

Abordarea naiva

• Simpla combinare a unei implementari secventiale a obiectelor cu zavoare nu este neaparat scalabila. Aceasta metoda se numeste sincronizare grosiera sau naiva (engl. coarse-grained).

• Abordarea grosiera este eficienta cand nivelul de concurenta este scazut. Daca numarul de fire ce acceseaza obiectul concurent creste, atunci obiectul devine un punct de strangulare (engl. bottleneck) a aplicatiei, limitand drastic concurenta.

2018-2019

Folosirea zavoarelor

• Se folosesc clase care implementeaza interfata

Lock din pachetul java.util.concrtent.locks.

• Un exemplu este clasa ReentrantLock.

• Acest sablon de cod ne asigura ca: – Zavorul este achizitonat inainte de a intra in

sectiunea critica

– Zavorul este eliberat indiferent de maniera in care se

iese prin sectiunea critica (normal sau cu exceptie in

sectiunea critica).

2018-2019

Sablonul de folosire a unui zavor

import java.util.concrtent.locks.*;

Lock lock = new ReentrantLock();

// ...

lock.lock();

try {

// ... Cod sectiune critica

} finally {

lock.unlock();

}

Sectiune critica

Declaratii

2018-2019

Alte abordari

• Sincronizare fina (engl. fine-grained synchronization).

• Sincronizare optimista (engl. optimistic synchronization).

• Sincronizare lenesa (engl. lazy synchronization).

• Sincronizare neblocanta (engl. non-blocking synchronization).

2018-2019

Sincronizare fina

• Obiectul se partitioneaza intr-o multime de componente.

• De exemplu o lista se descompune intr-o multime de noduri.

• Accesul la fiecare componenta este protejat de cate un zavor independent.

• Se evita conflictele de acces ale metodelor la aceeasi componenta.

2018-2019

Sincronizare optimista

• Cautarea unei componente are loc fara a folosi zavoare.

• Daca operatia de cautare este reusita atunci se blocheaza accesul la componenta.

• Se verifica apoi ca starea componentei accesate nu s-a modificat din momentul gasirii pana in momentul blocarii accesului la ea.

• Daca este OK, operatia reuseste. Altfel se reia.

• De obicei este mai rapida decat sincronizarea fina, insa in cazul unui esec, compensarea nereusitei este costisitoare.

2018-2019

Sincronizare lenesa

• Ideea este de a amana operatiile costistoare.

• De exemplu, eliminarea unei componente se separa in doua faze:

– Stergerea logica, prin marcarea logica a componentelor sterse

– Stergerea fizica, prin realizarea stergerii propriuzise

• Realizarea stergerii fizice este costisitoare. Insa poate deveni mai eficienta daca se realizeaza in mod “batch” – adica mai multe stergeri deodata.

2018-2019

Sincronizare neblocanta

• Se bazeaza pe evitarea completa a folosirii zavoarelor.

• In schimb se folosesc operatii atomice, cum ar fi compareAndSet.

2018-2019

Multimi abstracte

public interface Set<T> {

boolean add(T x);

boolean remove(T x);

boolean contains(T x);

}

• add(x) adauga x la multime si intoarce true dnd x nu era in multime.

• remove(x) elimina x din multime intorcand true dnd x era in multime.

• contains(x) realizeaza un test de apartenenta, intoarce true dnd x se afla in multime.

2018-2019

Implementarea multimilor cu liste I

• Vom folosi listele inlantuite pentru a implementa multimile sub

forma unor colectii de elemente care nu contin duplicate.

private class Node {

T item;

int key;

Node next;

Node(T item) {

this.item = item;

this.key = item.hashCode();

}

}

• Fiecarui element ii corespunde un nod in lista.

• item memoreaza valoarea elementului

• key este un index (engl. hash code) cu valoare unica pentru fiecare

nod. Se considera ca elementele listei sunt ordonate crescator

conform ordinii definite pentru acest camp.

2018-2019

Implementarea multimilor cu liste II

• Se presupune ca orice lista contine doua noduri

suplimentare numite santinele: head si tail.

• Se presupune ca nodurile santinela nu reprezinta

elemente adaugate, eliminate sau cautate in lista.

• Valorile cheilor nodurilor santinela sunt: – Valoarea minima (o valoare mai mica decat orice valoare

care poate aparea in lista) pentru head

– Valoarea maxima (o valoare mai mare decat orice valoare

care poate aparea in lista) pentru tail.

2018-2019

Variabile suplimentare

• Orice fir A care realizeaza o operatie de cautare /

eliminare din lista va folosi doua referinte:

– 𝑐𝑟𝑡𝐴 ce reprezinta nodul curent

– 𝑝𝑟𝑒𝑑𝐴 ce reprezinta predecesorul nodului curent

– Initial 𝑐𝑟𝑡𝐴 = 𝑝𝑟𝑒𝑑𝐴 = ℎ𝑒𝑎𝑑

2018-2019

Adaugarea unui element

• crt = nodul curent

• pred = nodul predecesor

• Se compara cheia nodului de inserat (b in acest caz) cu cheia

nodului curent crt: – Daca avem identificare atunci operatia se termina si se intoarce false.

– Daca nu avem identificare operatia continua pana cand eventual

intalnim un nod cu o cheie mai mare, caz in care are loc inserarea

folosind pred si crt si se intoarce true.

Sursa: Herlithy & Shavit, 2012

crt

2018-2019

Eliminarea unui element

• Se presupune ca elementul care trebuie sters este cel indicat de

referinta crt (elementul cu cheia b in acest caz).

• Stergerea are loc setand campul next al elementului pred astfel

incat sa indice catre sucesorul elementului de sters indicat de

referinta crt.


crt

2018-2019

Rationament concurent

• Rationamentul asupra structurilor de date concurente presupune

folosirea invariantilor = proprietati intotdeauna adevarate: – Un invariant este adevarat dupa ce obiectul este creat

– Odata invariantul adevarat, nu este posibil ca vreun fir sa faca un pas

astfel incat invariantul sa devina fals.

• Invariantii trebuie pastrati la fiecare executie a unei metode a

obiectului. Fie ℳ aceasta multime de metode.

• Se presupune ca obiectul este liber de interferenta (engl.

freedom of interference) dnd singura modalitate de a modifica

obiectul este prin intermediul metodelor din multimea ℳ. • Exemplu: pentru lista considerata ℳ = *𝑎𝑑𝑑(), 𝑟𝑒𝑚𝑜𝑣𝑒(),

𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑠()+. Lista este libera de interferenta intrucat nodurile

sunt interne listei si ele nu pot fi modificate direct din exterior.

2018-2019

Valoare abstracta si reprezentare concreta

• Valoare abstracta = reprezentarea matematica a valorii unui

obiect. Pe exemplul nostru, ea este o multime de elemente.

• Reprezentare concreta = implementarea valorii unui obiect. Pe

exemplul nostru, ea este o lista de noduri.

• Un invariant de reprezentare caracterizeaza ce reprezentari

concrete corespund unei valori abstracte valide a obiectului. Pe

exemplul nostru avem urmatorii invarianti de reprezentare: – Nodurile santinela nu sunt niciodata adaugate sau eliminate.

– Cheile sunt unice, iar nodurile sunt sortate crescator dupa cheie.

• Corespondenta dintre o reprezentare concreta care satisface

invariantii de reprezentare si valoarea abstracta a unui obiect se

face prin intermediul unei functii de abstractizare a

reprezentarii (engl. abstraction map).

2018-2019

Liniarizabilitate

• Liniarizabilitatea = proprietate de siguranta = orice

executie concurenta este echivalenta cu o executie

secventiala care este conforma cu ordinea reala de

executie a metodelor.

• Pentru a arata ca o structura de date concurenta este

liniarizabila este suficient: – Sa identificam un punct de liniarizare = un pas atomic prin

care fiecare apel de metoda isi produce efectul asupra

structurii. Pasul poate fi: o scriere, o citire sau o operatie

atomica complexa.

– Sa verificam ca prin aplicarea functiei de abstractizare a

reprezentarii in fiecare punct de liniarizare rezulta o

reprezentare valida de valori abstracte ale structurii.

2018-2019

Progres

• Pentru metodele care folosesc zavoare se impune

ca aceste zavoare sa asigure: – lipsa interblocajului

– lipsa infometarii

• Proprietatile de progres ale zavoarelor mostenesc

de proprietatile de progres ale obiectelor ce le

folosesc.

2018-2019

Sincronizare grosiera

• Clasa CoarseList satisface aceleasi proprietati de progres ca si

zavorul folosit. De exemplu, daca zavorul asigura lipsa

infometarii atunci si clasa are aceasta proprietate.

import java.util.concrtent.locks.*;

public class CoarseList<T> {

private Node head, tail;

private Lock lock = new ReentrantLock();

public CoarseList() {

head = new Node(Integer.MIN_VALUE);

head.next = tail = new Node(Integer.MAX_VALUE);

}

2018-2019

Sincronizare grosiera – adaugare element public boolean add(T item) {

Node pred, crt;

int key = item.hashCode();

lock.lock();

try {

pred = head; crt = pred.next;

while (crt.key < key) {

pred = crt; crt = crt.next;

}

if (key == crt.key) {

return false;

} else {

Node node = new Node(item);

node.next = crt; pred.next = node;

return true;

}

} finally {

lock.unlock();

}

}

Punctul de liniarizare pentru orice

metoda care achizitioneaza un zavor

este momentul achizitiei zavorului.

2018-2019

Sincronizare grosiera – eliminare element public boolean remove(T item) {

Node pred, crt;


lock.lock();

try {




}

if (key == crt.key) {

pred.next = crt.next;

return true;

} else {

return false;

}

} finally {

lock.unlock();

}

}

}

2018-2019

Sincronizare grosiera – apartenenta element

Tema !

2018-2019

Testare

• Test secvential: – Firul curent executa succesiunea de adaugari ale elementelor 0, 1, …,

TEST_SIZE

– Firul curent executa succesiunea de teste de apartenenta ale

elementelor 0, 1, …, TEST_SIZE

– Firul curent executa succesiunea de eliminari ale elementelor 0, 1, …,

TEST_SIZE

• Test paralel: – Se executa operatii concurente din firele 0, 1, ..., THREADS

– Fiecare fir executa PER_THREAD = TEST_SIZE / THREADS operatii

– Fiecare fir i = 0, 1, ..., THREADS se ocupa de elementele i

PER_THREAD, i PER_THREAD + 1, ..., i PER_THREAD +

PER_THREAD - 1 = (i+1) PER_THREAD - 1

2018-2019

Testare adaugare concurenta

• Fiecare fir i = 0, 1, ..., THREADS executa secvential

adaugarile elementelor i PER_THREAD, i

PER_THREAD + 1, ..., i PER_THREAD +

PER_THREAD - 1 = (i+1) PER_THREAD – 1

• Cele THREADS fire se executa concurent

• Firul curent testeaza secvential apartenenta fiecarui

element i = 0, 1, ..., TEST_SIZE la multime

• Firul curent elimina secvential fiecare element i = 0, 1,

..., TEST_SIZE la multime

2018-2019

Testare eliminare concurenta

• Firul curent adauga secvential fiecare element i = 0, 1,

..., TEST_SIZE la multime

• Firul curent testeaza secvential apartenenta fiecarui

element i = 0, 1, ..., TEST_SIZE la multime

• Fiecare fir i = 0, 1, ..., THREADS executa secvential

eliminarile elementelor i PER_THREAD, i

PER_THREAD + 1, ..., i PER_THREAD +

PER_THREAD - 1 = (i+1) PER_THREAD – 1

• Cele THREADS fire se executa concurent

2018-2019

Testare adaugare si eliminare concurenta

• Se creaza THREADS fire: – Pentru i = 0, 1, ..., THREADS si pentru fiecare j = 0, 1, ...,

PER_THREAD - 1 firul i executa secvential adaugarea

elementului i PER_THREAD + j urmata de eliminarea

elementului i PER_THREAD + j

• Cele THREADS fire se executa concurent, astfel ca

avem operatii de adaugare si eliminare realizate in mod

concurent, dar de fiecare data eliminarea unui element

se executa dupa adaugarea sa.

2018-2019

Testare folosind JUint

• Pentru testare se foloseste JUnit 4 (http://junit.org/) ce permite

definirea explicita a metodelor care specifica teste.

• Pentru fiecare modul se creaza o clasa de test care contine

metodele ce specifica testele.

• Specificarea unei metode ce desemneaza un test se face prin

adnotarea @Test (@org.junit.Test).

• Pentru implementarea testelor se poate folosi clasa Assert

(org.junit.Assert). Aceasta clasa pune la dispozitie o serie de

metode de forma assertX unde X reprezinta o conditie care este

verificata la executie. Spre exemplu X poate fi: – True, False

– Equals, Same

– ...

2018-2019

Testarea clasei CoarseList import org.junit.Test;

import org.junit.Assert;

public class CoarseListTest {

private final static int THREADS = 8;

private final static int TEST_SIZE = 128;

private final static int PER_THREAD = TEST_SIZE / THREADS;

CoarseList<Integer> instance;

Thread[] thread;

public CoarseListTest() {

instance = new CoarseList<Integer>();

thread = new Thread[THREADS];

}

@Test public void testSequential() { ...

}

@Test public void testParallelAdd() { ...

}

...

}

2018-2019

Test adaugare concurenta @Test public void testParallelAdd() throws InterruptedException {

System.out.println("parallel add");

for (int i = 0; i < THREADS; i++) {

thread[i] = new AddThread(i * PER_THREAD);

}

for (int i = 0; i < THREADS; i ++) { thread[i].start(); }

for (int i = 0; i < THREADS; i ++) { thread[i].join(); }

for (int i = 0; i < TEST_SIZE; i++) {

Assert.assertTrue("bad contains: " + i,instance.contains(i) );

}

for (int i = 0; i < TEST_SIZE; i++) {

Assert.assertTrue("bad remove: " + i,instance.remove(i) );

}

}

class AddThread extends Thread {

int value;

AddThread(int i) { value = i; }

public void run() {

for (int i = 0; i < PER_THREAD; i++) {

instance.add(value + i);

}

}

}

2018-2019

Sincronizare fina

• In loc de a folosi un singur zavor pentru sincronizarea

fiecarui acces la obiect, sincronizarea fina presupune

sa se desparta obiectul in componente sincronizate

independente, asigurandu-ne doar pentru situatiile in

care apelurile pot interfera prin accesul simultan la o

componenta.

• Se foloseste cate un zavor pentru fiecare nod al listei.

Cand un fir acceseaza un nod, el va bloca accesul la

nod cu un zavor pe care il elibereaza la un moment

ulterior.

2018-2019

Cuplarea zavoarelor

• Fie nodul a avand b ca nod urmator. Zavorul necesar

unui fir pentru accesul la nodul b se va achiziona in

timp ce se mentine zavorul achizitionat anterior pentru

accesul la a. Regula de transmitere “din mana-in-

mana” a zavoarelor se numeste cuplarea zavoarelor

(engl. lock coupling).

• Nu se poate implementa folosind doar mecansimul

synchronized din Java, fiind nevoie de zavoare locale

pentru fiecare nod in parte.

2018-2019

Cuplarea zavoarelor

a b c

2018-2019

Adaugarea unui zavor clasei Node


T item;

int key;

Node next;

Lock lock;

Node(T item) {

this.item = item;

this.key = item.hashCode();

this.lock = new ReentrantLock();

}

Node(T key) {

this.item = null;

this.key = key;

this.lock = new ReentrantLock();

}

void lock() { lock.lock(); }

void unlock() { lock.unlock(); }

}

2018-2019

Adaugare element cu sincronizare fina I public class FineList<T> {

private Node head,tail;

public FineList() {


head.next = tail = new Node(Integer.MAX_VALUE);

}

public boolean add(T item) {


head.lock();

Node pred = head;

try {

crt = pred.next;

crt.lock();

try {


pred.unlock();


Constructor similar pentru

fiecare tip de sincronizare.

2018-2019

Adaugare element cu sincronizare fina II crt.lock();

}

if (crt.key == key) {

return false;

}

Node newNode = new Node(item);

newNode.next = crt;

pred.next = newNode;

return true;

} finally { crt.unlock(); }

} finally { pred.unlock(); }

}

2018-2019

Eliminare element cu sincronizare fina public boolean remove(T item) {

Node pred = head, crt = null;


head.lock();

try {


crt.lock();

try {


pred.unlock();


crt.lock();

}



return true;

}

return false;



}

2018-2019

Verificare apartenenta cu sincronizare fina

TEMA !

2018-2019

Eliminare nod cu sincronizare fina

a b c d

remove(b)

2018-2019

Eliminare nod cu sincronizare fina

a c d

remove(b) De ce avem nevoie de 2

zavoare?

2018-2019

Explicatie eliminare cu sincronizare fina – 1 zavor

• Sa presupunem ca un fir blocheaza doar elementul predecesor

elementului curent. Fie scenariul in care firul 𝐴 elimina 𝑎 in

timp ce firul 𝐵 elimina 𝑏. 𝐴 blocheaza accesul la ℎ𝑒𝑎𝑑 si 𝐵

blocheaza accesul la 𝑎. 𝐴 seteaza ℎ𝑒𝑎𝑑. 𝑛𝑒𝑥𝑡 la 𝑏, iar 𝐵

seteaza 𝑎. 𝑛𝑒𝑥𝑡 la 𝑐. In final se observa ca se elimina doar 𝑎, in

loc de a se elimina 𝑎 si 𝑏.


2018-2019

Eliminare nod cu sincronizare fina si 1 zavor

a b c d

remove(c) remove(b)

2018-2019

Eliminare nod cu sincronizare fina si 1 zavor

a b c d

remove(b) remove(c)

2018-2019

Problema ?

a c d

remove(b) remove(c)

2018-2019

Problema – c nu este eliminat !

a c d

Nodul c nu este eliminat !

remove(b) remove(c)

2018-2019

Explicatie problema

b a c

b a c

• Pentru a elimina pe 𝑐, nodul 𝑏 trebuie redirectat catre

succesorul lui 𝑐.

• Un alt fir poate insa sterge concurent pe 𝑏,

redirectionand un pointer catre 𝑐.

2018-2019

Explicatie eliminare cu sincronizare fina – 2 zavoare

• Regula de transmitere din “mana-in-mana” a zavoarelor ne

asigura ca daca doua apeluri concurente ale metodei remove()

incearca sa elimine noduri adiacente (cum sunt a si b) va

aparea un conflict pe zavorul unui nod comun (A acceseaza

head si a, in timp ce B acceseaza a si b), fortand unul dintre

apeluri sa astepte dupa celalalt.


2018-2019

Evitarea interblocarii in sincronizarea fina

• Pentru evitarea interblocarii firele trebuie sa achizitioneze zavoarele in

aceeasi ordine, de la ℎ𝑒𝑎𝑑 inspre 𝑡𝑎𝑖𝑙. De exemplu, daca firul 𝐴 ce

adauga 𝑎 blocheaza intai 𝑏 si apoi ℎ𝑒𝑎𝑑, iar firul 𝐵 ce doreste sa stearga

pe 𝑏 blocheaza intai ℎ𝑒𝑎𝑑 si apoi 𝑏, fiecare fir va detine un zavor pe care

celalalt fir doreste sa-l achizitioneze, conducand la interblocaj.


2018-2019

Eliminare nod cu sincronizare fina si 2 zavoare

a b c d

remove(b) remove(c)

2018-2019


a b c d

Must

acquire

Lock for

b

remove(c)

2018-2019


a b c d

Cannot

acquire

lock for b

remove(c)

2018-2019


a b c d

Wait! remove(c)

2018-2019


a b d

Proceed

to

remove(b)

2018-2019


a b d

remove(b)

2018-2019


a d

remove(b)

2018-2019


a d

2018-2019

Evitarea interblocarii in sincronizarea fina

• Pentru evitarea interblocarii firele trebuie sa achizitioneze zavoarele in

aceeasi ordine, de la ℎ𝑒𝑎𝑑 inspre 𝑡𝑎𝑖𝑙. De exemplu, daca firul 𝐴 ce

adauga 𝑎 blocheaza intai 𝑏 si apoi ℎ𝑒𝑎𝑑, iar firul 𝐵 ce doreste sa stearga

pe 𝑏 blocheaza intai ℎ𝑒𝑎𝑑 si apoi 𝑏, fiecare fir va detine un zavor pe care

celalalt fir doreste sa-l achizitioneze, conducand la interblocaj.


2018-2019

Pastrarea invariantilor in sincronizarea fina

• Invariantii de reprezentare se pastreaza.

• Functia de abstractizare a reprezentarii:

𝑆 ℎ𝑒𝑎𝑑 = *𝑥│∃𝑛 s. t. node 𝑛 is reachable from ℎ𝑒𝑎𝑑 ∧ 𝑛. 𝑖𝑡𝑒𝑚 = 𝑥+

• Punctul de liniarizare pentru add(x) este punctul in care se

achizitioneaza zavorul pentru un nod curent crt cu cheia mai

mare sau egala decat cheia lui x. Cand nu avem egalitate,

metoda intoarce true, altfel intoarce false. Situatia este similara

pentru remove(x) cu diferenta ca metoda intoarce true daca

avem egalitate, altfel intoarce false.

• FineList verifica lipsa infometarii. Acest rezultat rezulta din

lipsa infometarii zavoarelor si din maniera in care zavoarele

sunt achizitionate si eliberate conform protocolului “din-mana-

in-mana”.

2018-2019

Concluzii asupra sincronizarii fine

• Avantaj:

– Este mai buna decat sincronizarea grosiera deoarece firele

pot accesa lista in maniera concurenta.

• Dezavantaj:

– Se creaza siruri lungi de achizitii-eliberari de zavoare ce

sunt ineficiente.

2018-2019

Sincronizare optimista

• Se foloseste asupra obiectelor reprezentate ca multimi de

noduri (componente) inlantuite prin referinte – liste si arbori,

in situatia in care operatiile presupun cautarea unui anumit nod

(componenta).

• Pentru reducerea costului suplimentar prezent in sincronizarea

fina, cautarea se va realiza fara achizitia de zavoare. Odata

gasita, accesul la componenta respectiva este blocat cu un

zavor, se re-verifica faptul ca acea componenta nu a fost

modificata intre timp, si apoi se executa operatia. In cazul in

care re-verificarea esueaza se reia procedeul de cautare.

• Metoda este eficienta daca probabilitatea de reusita a operatiei

de cautare este mai mare decat probabilitatea de esec.

2018-2019

Adaugarea unui element cu sincronizare optimista



while (true) {

Node pred = head, crt = pred.next;

while (crt.key < key) { pred = crt; crt = crt.next; }

pred.lock(); crt.lock();

try {

if (validate(pred, crt)) {

if (crt.key == key) { return false;

} else {



return true;

}

}

} finally {

pred.unlock(); crt.unlock();

}

}

}

Verifica daca pred este accesibil

din head si daca pred.next este

egal cu crt.

2018-2019

Eliminarea unui element cu sincronizare optimista

public boolean remove(T item) {


while (true) {

Node pred = head, crt = pred.next;


pred.lock(); crt.lock();

try {




return true;

} else { return false; }

}

} finally {

pred.unlock(); crt.unlock();

}

}

}

2018-2019

public boolean validate(Node pred, Node crt) {

Node node = head;

while (node.key <= pred.key) {

if (node == pred) return pred.next == crt;

node = node.next;

}

return false;

}

• Firul 𝐴 elimina 𝑎. In timpul traversarii este posibil ca toate nodurile de la 𝑐𝑢𝑟𝑟𝐴 incolo

(inclusiv 𝑎) sa fie eliminate. Insa firul 𝐴 va ajunge la 𝑎 “eliminandu-l” incorect.

Metoda validate()

Sursa: Herlithy & Shavit, 2012 crtA

2018-2019

Verificare apartenenta cu sincronizare optimista

TEMA !

2018-2019

• Avantaj:

– Poate duce la cresterea performantei (prin cresterea concurentei),

folosind mai putin zavoarele

• Posibilitatea infometarii:

– Clasa OpimisticList nu ofera garantia lipsei infometarii. Este posibil ca

un fir care acceseaza un obiect al acestei clase sa fie intarziat la infinit,

in timp ce alte fir executa in mod repetat operatii de adaugare /

eliminare de noduri.

• Ineficienta:

– Lista este intotdeauna parcursa de cel putin doua ori

Concluzii asupra sincronizarii optimiste

2018-2019

Sincronizare lenesa

• Foloseste o tehnica de amanare a operatiilor considerate mai

dificile. De exemplu, operatia de eliminare a unei componente

dintr-o structura de date se poate diviza in doua: – Eliminarea logica prin marcarea cu un camp 𝑏𝑜𝑜𝑙𝑒𝑎𝑛 special

– Eliminarea fizica prin deconectarea ei de la structura de date

• Se adauga un camp marked initializat cu false la clasa Node.

Cand marked devine true inseamna ca elementul a fost eliminat

“logic” din multime.

• Nu mai este nevoie sa se blocheze accesul la noduri cu zavor.

• Nu mai este necesara validarea prin reparcurgerea listei.

• Elementele multimii sunt date de nodurile nemarcate ce pot fi

atinse din head. Daca un element nu este gasit sau are marked

pe true atunci el nu apartine multimii.

2018-2019

Implementarea operatiilor in sincronizarea lenesa

• Operatia contains() necesita o simpla traversare. Aceasta

operatie este wait-free.

• Operatia add() traverseaza lista, blocheaza accesul la

predecesorul nodului tinta (inaintea caruia are loc inserarea) si

insereaza nodul. Daca traversarea nu gaseste nodul sau il

gaseste cu marked=true atunci ea intoarce false.

• Operatia remove() este “lenesa” si lucreaza in doi pasi. In

primul pas ea marcheaza nodul tinta pentru stergere “logica”.

In pasul al doilea ea realizeaza redirectionarea campului 𝑛𝑒𝑥𝑡

al nodului predecesor, realizand stergerea “fizica” a nodului

tinta.

2018-2019

Adaugarea unui element cu sincronizare lenesa



while (true) {

Node pred = head, crt = head.next;


pred.lock();

try {

crt.lock();

try {


if (crt.key == key) { return false;

} else {



return true;

}

}



}

}

2018-2019

Eliminarea unui element cu sincronizare lenesa

public boolean remove(T item) {


while (true) {

Node pred = head, crt = head.next;



}

pred.lock();

try {

crt.lock();

try {


if (crt.key != key) { return false;

} else {

crt.marked = true; pred.next = crt.next;

return true;

}

}



}

}

2018-2019

Verificare apartenenta cu sincronizare lenesa

public boolean contains(T item) {


Node crt = head;

while (crt.key < key)

crt = crt.next;

return crt.key == key && !crt.marked;

}

• Metodele add() si remove() nu sunt lipsite de infometare.

Infometarea poate sa apara deoarece traversarea listei poate fi

intarziata in mod nedefinit de operatii de modificare aflate in

continua desfasurare.

• Metoda contains() este wait-free. Lista nu poate creste la infinit

datorita unor inserari continue intrucat dimensiunea cheii este

finita.

2018-2019

Metoda validate() in sincronizarea lenesa

private boolean validate(Node pred, Node crt) {

return !pred.marked && !crt.marked &&

pred.next == crt;

}

• Metoda validate() verifica daca: – Elementele pred si crt nu au fost cumva sterse “logic”

– Elementul pred este in continuare predecesorullui crt

2018-2019

Concluzii asupra sincronizarii lenese

• Avantaj: – Se separa pasii de stergere logica prin realizarea marcajului de pasii

care realizeaza stergerea fizica prin eliminarea unui nod. Pe cazul

general operatiile care realizeaza stergerea fizica pot fi grupate si

realizate la un moment convenabil ulterior, astfel incat sa se reduca

efectul operatiilor ce afecteaza structura listei

• Dezavantaj – Apelurile add() si remove() folosesc zavoare, fapt putand conduce la

intarzierea nelimitata a operatiilor respective.

2018-2019

Sincronizare neblocanta

• Sincronizarea neblocanta extinde ideea marcarii logice a

nodurilor eliminate astfel incat sa se renunte definitiv la

folosirea zavoarelor pentru toate cele trei metode: add(),

remove() si contains().

• O varianta naiva este folosirea metodei compareAndSet() a

clasei AtomicReference<T> din pachetul

java.util.concrtent.atomic pentru reprezentarea si actualizarea

campurilor next. Din pacate aceata solutie nu este corecta.

2018-2019

Sincronizare neblocanta – solutie incorecta

• Fie 𝑎 si 𝑏 doua noduri adiacente ale listei, 𝑏 succesorul lui 𝑎.

Metoda naiva nu functioneaza in cazurile in care se executa

concurent: – A: remove(a) si B: add(b)

– A: remove(a) si B:remove(b) (Tema: ?)


2018-2019

Clasa AtomicMarkableReference<T>

• Reprezinta obiecte ce incapsuleaza: – O referinta la un obiect generic de tip 𝑇

– Un marcaj 𝑏𝑜𝑜𝑙𝑒𝑎𝑛

• Clasa permite actualizarea impreuna sau individuala a acestor campuri.

• Metoda ce permite testarea valorilor asteptate ale referintei si marcajului.

Daca testul reuseste, ele se inlocuesc cu noi valori: public boolean compareAndSet(T expectedReference,

T newReference, boolean expectedMark, boolean newMark);

• Metoda ce permite testarea valorii asteptate a referintei. Daca testul

reuseste se modifica marcajul: public boolean attemptMark(T expectedReference,

boolean newMark);

• Metoda ce intoarce valoarea referintei si stocheaza valoarea marcajului in

componenta 0 a unui vector de valori 𝑏𝑜𝑜𝑙𝑒𝑎𝑛: public T get(boolean[] marked);

• Metoda care intoarce valoarea curenta a referintei:

public T getReference()

2018-2019

Idee sincronizare neblocanta

• Este nevoie de o metoda care sa previna actualizarea campului

next al unui nod sters logic sau fizic.

• Campul next va fi de tip AtomicMarkableReference<Node>.

• Un fir A sterge logic nodul crt marcand campul next. Alte fire

ce executa operatii add() sau remove() traverseaza lista,

concomitent stergand fizic nodurile marcate cu ajutorul

metodei compareAndSet().

• Metoda contains() va ramane similara cu cea a clasei LazyList.

2018-2019

Modificarea clasei Node


T item;

int key;

AtomicMarkableReference<Node> next;

public Node(int k) {

key = k;

item = null;

next = new AtomicMarkableReference<Node>(null, false);

}

public Node(T i) {

item = i;

key = i.hashCode();

next = new AtomicMarkableReference<Node>(null, false);

}

}

2018-2019

Clasa LockFreeList<T>

public class LockFreeList<T> {

private Node head;

public LockFreeList() {


head.next = new AtomicMarkableReference<Node>(

new Node(Integer.MAX_VALUE), false);

}

class Window {

public Node pred;

public Node crt;

Window(Node pred, Node crt) {

this.pred = pred; this.crt = crt;

}

}

// ...

}

2018-2019

Clasa interna Window

• Se creaza o clasa ajutatoare Window. Fiind dat un element a,

metoda find() a listei parcurge lista si determina un obiect

Window ce incapsuleaza doua noduri pred si crt a.i.: – pred este nodul cu cea mai mare cheie mai mica decat a

– crt este nodul cu cea mai mica cheie mai mare sau egala cu a.

• Parcurgerea listei realizeaza stergerea fizica a nodurilor

marcate. Daca in momentul incercarii operatiei de stergere se

constata ca intre timp lista a fost modificata, procesul de

parcurgere al listei este reluat.

• Varianta in care stergerea fizica a elementului crt s-ar realiza

imediat dupa marcare nu este corecta deoarece alte fire pot fie

sterge concurent nodul pred, fie adauga concurent noi noduri

intre pred si crt.

2018-2019

Metoda find() I

• Pe masura ce metoda find() traverseaza lista avansand referinta

crt, se determina daca nodul corespunzator este marcat. In caz

afirmativ se apeleaza metoda compareAndSet() incercand sa se

elimine nodul crt.

• Metoda add(a) apeleaza intai find() pentru a determina obiectul

Window cu componentele pred si crt.

• Daca crt este identic cu a atunci metoda intoarce false. Altfel

se creaza un nod si se incearca inserarea. In caz de esec,

procesul se reia datorita buclei while(true) {…}.

2018-2019

Metoda find() II

public Window find(Node head, int key) {

Node pred = null, crt = null, succ = null;

boolean[] marked = {false};

boolean snip;

retry: while (true) {

pred = head;

crt = pred.next.getReference();

while (true) {

succ = crt.next.get(marked);

while (marked[0]) {

snip = pred.next.compareAndSet(crt,succ,false,false);

if (!snip) continue retry;

crt = succ;

succ = crt.next.get(marked);

}

if (crt.key >= key)

return new Window(pred, crt);

pred = crt;

crt = succ;

}

}

}

2018-2019

Adaugarea unui element cu sincronizare neblocanta



while (true) {

Window window = find(head, key);

Node pred = window.pred, crt = window.crt;


return false;

} else {


node.next =

new AtomicMarkableReference<Node>(crt, false);

if (pred.next.compareAndSet(crt,node,false, false)){

return true;

}

}

}

}

2018-2019

Concluzii asupra sincronizarii neblocante

• Avantaj: – Garanteaza progresul chiar si in prezenta unor intarzieri arbirare.

• Dezavantaj – Necesitatea folosirii unei operatii de modificare atomica a unei

referinte impreuna cu marcajul logic; aceasta operatie aduce costuri

suplimentare in implementare.

– Poate fi necesar sa se reparcurga lista in cazul unor operatii

concurente.

structuri de date concurente - software.ucv.rosoftware.ucv.ro/~cbadica/scd/cap9.pdf · –initial p...

Documents