Despre Performanta Spinlock-urilor
Un SpinLock este relativ usor de implementat,deoarece cam fiecare procesor are instructiuni speciale pentru citirea si
setarea valorii unui spinlock folosind doar o singura instructiune atomica.De exemplu,avand un spinlock s, intr-un sistem multiprocesor,
si mai multe thread-uri,fiecare executande-se pe cate un procesor,care incearca sa intre in sectiunea lor critica.Fiecare thread
va apela o functie speciala (AcquireSpinLock()) pentru a incerca sa intre in sectiunea critica.aceasta functie va face urmatoarele
:va citi intr-o variabila temporara valoarea spinlock-ului s,si va scrie in s o noua valoare,aceste doua operatii avand loc
in cadrul unei singure instructiuni.De exemplu daca s = 0 atunci spinlock-ul este liber si nici un thread nu este in scetiunea
sa critica,iar s = 1 inseamna ca spinlock-ul este ocupat,adica un thread se afla in sectiunea sa critica.
Dupa executarea acestei instructiuni atomice,vom compara valarea initiala a spinlock-ului cu 1.Daca s era 0 atunci
thread-ul poate intra linistit in sectiunea sa critica,insa daca s era 1 atunci mai incerca odata.Mai pe romaneste,
ceea ce face ruitna AcquireSpinlock(),este sa testeze si sa seteze valoarea lui s,intr-un ciclu atat timp cat s este
“ocupat”( = 1).Cand s este pus pe 0,primul thread care va executa AcquireSpinlock(),va intra in sectiunea critica.
Operatia care citeste valoarea lui intr-o variabila temporara si apoi seteaza valoarea lui s la o alta valoare
poarta numele de “test and set”.O asemenea operatie,pe majoritatea platformelor este furnizata sub forma unei intructiuni,
ca de exemplu instructiunile XCHG(eXCHanGe – interschimb) sau BTS
(Bit Test and Set),din setul de instructiuni a procesoarelor din familia x86.
Un test and set ar putea arata cam asa in pseudocod:
int TestAndSet(SpinLock* s){ int temp; temp = *s; *s = 1; return (temp); }
…iar o functie de acquireing a unui spinlock care va cicla atat timp cat spinlock-ul este liber,la fiecare pas
testand si setand valoarea sa,arata cam asa:
void AcquireSpinlock(SpinLock *s){ while(TestAndSet(s)) ; }
Cam asta e toata logica din spatele unui spinlock,insa exista niste probleme.In primul rand asa cum am spus,TestAndSet,trebuie sa fie o operatie
atomica,o operatie care sa se execute ca un tot unitar.In cazul nostru,ea este o functie,care are doua intructiuni in corpul
(in afara de instructiunea de return).Tinand cont de faptul ca un spinlock trebuie sa functioneze pe un sitem cu mai mult de un procesor,
evident exista riscul ca doua thread-uri ,fiecare executandu-se pe cate un CPU,sa incerce se apeleze rutina AcquireSpinLock.Acest
lucru este posibil,iar cele doua thread-uri,vor testa si seta simultan valoarea lui s,amandoua gasind-ul “liber”,deci
ambele thread-uri vor intra in acelasi timp in sectiunea lor critica,deci avem race condition.In aceasta situatie,
cele doua thread-uri pot modifica simultan,fara nici un fel de constrangere,respectiva resursa critica(de exemplu o variabila partajata)
putand avea parte de un rezultat eronat.Not Good 
.
Deci….in concluzie un spinlock,desi e simplu de implementat,nu putem sa-l implementam intr-un limbaj ca C/C++.
Pentru asta vom apela la limbajul de asamblare,deoarece asa cum am spus in setul de instructiuni avem cateva instructiuni care
sa testeze si sa seteze valoarea unei variabile.
O posibila implementare in Assembler a functiei AcquireSpinlock().
AcquireSpinlock proc _Acquire: mov ax,1 lock xchg spinlock,ax cmp ax,1 je _Acquire ret AcquireSpinlock endp
Sa vedem ce face aceasta functie.Mai intai va scrie in registrului ax,valoarea 1.
Urmatoarea instructiune este echivalentul lui TestAndSet(Spinlock* s) in limbaj de asamblare.Aceasta instructiune va
interschimba valoarea lui ax,adica 1 cu valoarea spinlock-ului.Aceasta interschimbare se va realiza intr-un singur ciclu de ceas,
nefiind necesare doua sau 3 instructiuni pentru a realiza interschimbarea celor doua locatii(registru – memorie).
In fata acestei instructiuni se afla eticheta lock.Acest lucru ne spune ca in cazul in care mai multe
thread-uri ce ruleaza pe procesoare diferite vor incerca sa apeleze aceasta functie,doar unuia i se va acorda acces sa execute
aceasta instructiune.Acest prefix blocheaza magistrala sistemului pe parcursul executiei sale.Sa presupunem ca avem
3 thread-uri T1,T2 si T3 fiecare ruland pe cate un procesor,T1 ruleaza pe procesorul P1,T2 pe P2,iar T3 pe P3.Si sa
presupunem ca toate cele 3 thread-uri “doresc” sa intre in sectiunea lor critica.
Sa zicem ca resursa critica este o variabila int i,iar sectiunea critica a fiecarui thread
presupune incrementarea variabilei i (i++).Astfel fiecare thread va face urmatoarele actiuni:
AcquireSpinlock(s); i++; //Sectiune critica ReleaseSpinlock(s);
In sistemul nostru cu 3 procesoare,sa presupunem ca fiecare din cele 3 thread-uri “ajung” simultan la apelul AcquireSpinlock(s).
Fara prefixul lock in fata instructiunii xchg,acel cod in limbaj de asamblare ar fi fost echivalent cu
versiunea scrisa in C,deoarece fiecare din cele 3 thread-uri va executa simultan aceste instructiuni,inclusiv instructiunea xchg,
,deci in concluzie toate cele 3 thread-uri vor intra in sectiunea critica.Insa in cazul de fata instructiunea xchg este precedata
de prefixul lock,iar cand cele 3 thread-uri vor ajunge simultan “in fata” acestei instructiuni,vom avea
certitudinea ca doar unul dintre ele o va executa la un moment dat.Primul thread care va executa lock xchg …
va bloca in acelasi timp si magistrala sistemului,iar celelalte thread-uri vor trebui sa astepte pana cand primul thread va termina de executat
instructiunea xchg.Astfel primul thread care va executa aceasta instructiune va fi si cel care va intra in sectiunea critica,iar
apoi restul de thread-uri vor executa in mod serial instructiunea lock xchg,dupa care vor compara valoarea lui spinlock cu 1.In caz de egalitate,
vor repeta procesul.
Astfel celelalte thread-uri care nu au intrat in sectiunea critica vor cicla de atatea ori pana cand thread-ul care a intrat in sectiunea
critica va elibera spinlock-ul.Cand aceasta se va intampla,aceste thread-uri “vor intra in lupta”,iar primul care va executa testand set-ul
va fi intra in sectiunea critica,si tot asa pana cand toate thread-urile si-au executat codul din cadrul sectiunii critice.
Functia care elibereaza un spinlock este si mai simpla.Ea arata cam asa:
ReleaseSpinlock proc mov spinlock,0 ret ReleaseSpinlock endp
Si gata.Asa lucreaza un spinlock.Nimic mai mult.
Desi aceasta solutie este buna,in sensul ca ne garanteaza faptul ca doar un singur thread la un moment dat se va
afla in sectiunea sa critica,evitand astfel problemele cauzate de race conditions,este si cea mai slaba(lipsita de
performanta).De ce?…..pai sa vedem asta printr-un exemplu:
Sa presupunem ca avem un sistem cu 10 procesoare,si la un moment dat avem 10 thread-uri care doresc sa intre in
sectinea lor critica relativa la o anumita resursa(sa zicem o variabila intreaga i).Fiecare thread va rula pe cate un CPU distinct.
Pentru a-si exprima dorinta de a intra in sectiunea critica,fiecare thread va face un apel la functia AcquireSpinlock,pentru
a incerca sa “castige” spinlock-ul asociat resursei i.Evident ca doar unul dintre ele va reusi acest lucru,si anume
primul thread care a “vazut” spinlock-ul liber,il va seta pe 1 si va continua.Celelalte thread-uri is vor incerca si ele norocul,
insa vor “observa” ca spinlock-ul este ocupat,si deci vor incerca din nou.Astfel avem 9 thread-uri care vor incerca sa “castige”
respectivul spinlock,fiind in busy waiting(desi se zice ca ele asteapta,in realitate dupa cum ati si vazut un thread care”asteapta” un la spinlock
cicleaza pana cand acel spinlock devine liber.Cu toate ca face ceva ,adica nu se va alfa intr-o coada de asteptare,
nu va face nimik util,de aceea se mai spune si busy waiting).Asa cum am spus mai devreme,fiecare thread va incerca sa castige spinlock-ul,
iar in incercarea sa va executa si instructiunea xchg cu prefixul lock in fata,deci va bloca magistrala pe parcursul executarii ei.Insa asta nu e
foarte rau deoarece respectiva instuctiune in realitate se executa destul de repede.Insa in cazul de fata avem 9 thread-uri care vor face
asa ceva ,si nu vor face asta doar odata ci de atatea ori pana cand spinlock-ul va fi eliberat.Daca presupunem ca thread-ul 2 va executa de 100 de ori
acel ciclu while,iar thread-ul 3 de 80 de ori,la fiecare executie magistrala sistemului va fi blocata pt o scurta perioada de timp,incetinind astfel si
procesoarele care nu sunt in busy waiting si care “fac” lucruri utile.Si mai mult de atat,am considerat dor doua thread-uri care se afla in
busy waiting,insa in exemplul nostru avem 9:-(.Not Good.Aceasta situatia in care thread-urile care sunt busy waiting incetinesc sau impiedica
celelalte procesoare care fac lucruri utile se numeste HOT SPOT.Situatia e destul de neplacuta,cele 9 thread-uri vor executa in mod serial
instructiunea xchg pt a castiga magistrala ca sa nu interfereze cu alte thread-uri ce s-ar putea sa execute aceiasi instructiune in acelasi timp:-),si
asa cum am mai zis fiecare din cele 9 thread-uri vor executa instructiunea de mai multe ori,asta depinzand de cat de mult timp va sta in sectiunea critica,
thread-ul care a castigat spinlock-ul.Ganditi-va ca acel thread care se afla in sectiunea critica doreste sa scrie niste rezultate
in memorie,deci pentru asta are nevoie de acces la magistrala sistemului;insa s-ar putea sa nu poate sa scrie rezultate in acel timp,
deoarece “cineva” este in cursul executarii unei intructiuni xchg,iar dupa aia poate alt thread aflat in busy waiting,va executa xchg si asa mai departe.
Deci thread-ul care a castigat lock-ul s-ar putea sa astepte destul de mult pana sa scrie un rezultat in memorie.
Exista anumite implementari alternative,care pot elimina aceasta situatie de hot spot,lasand astfel celelalte procesoare sa isi faca treaba
fara sa mai astepte 100 de ani sa scrie un rezultat in memorie atunci cand au nevoie.O alternativa ar fi ca atunci cand un thread
doreste sa intre in sectiunea lui critica,sa execute un xchg,pentru a seta spinlock-ul la valoarea 1,iar apoi in caz de valoarea veche
a spinlock-ul era 0….ne-am scos 
….intram in sectiunea critica…in caz ca altcineva inaintea noastra a ocupat spinlock-ul,deci valoarea sa veche este 1,
vom testa intr-un ciclu valoarea spinlock-ul(CACHE SPINING sau SPIN-ON-READ).Ce inseamna asta…ca in loc sa executam instructiunea xchg de atatea ori pana spinlock-ul se elibereaza,
fiindca instructiunea xchg implica si o scriere si o citire,si vom bloca magistrala de atatea ori,o vom executa odata ,iar in caz de esec,vom
testa valoarea variabilei spinlock.O posibila implementare ar arata cam asa:
void AcquireSpinLock(SpinLock *L){ while (TestAndSet(L)) while (*L == 1) ; }
Care este diferenta dintre prima implementare si aceasta?….fiindca la prima vedere pare ca aceasta implementare
ar aduce un plus de complexitate,deoarece am mai adaugat un ciclu while?….ei bine nu e chiar asa….iar aceasta solutie
pe langa ca faptul ca nu aduce un plus de complexitate fata de prima implementare,ba mai mult e si mai eficienta:P
Pentru a putea intelege exact de ce …voi incerca sa explic cateva chestii legate de memoriile cache al procesoarelor,iar apoi vom reveni la
acest exemplu,ca sa vedem de ce el este mai bun decat primul.
memoriile cache
In general un procesor are urmatoarea misiune:sa ia instructiuni din memoria calculatorului si sa le execute,dupa care
posibil sa scrie niste informatii in registri sau din nou in memorie.Cam asta e ..asa in mare tot ce trebe sa faca un procesor.
Faza in care un procesor “ia” o instructiune din memoria RAM,se numeste FECTCHING,dupa care acea instructiune va fi depusa intr-un buffer
intern al procesorului.Urmeaza apoi faza de DECODING(decodificare),in care procesorul “incearca sa vada” ce fel de instructiune este ea,
si sa “vada” daca acea instructiune este una simpla ,sau are nevoie de un operand din memorie,sau de vreu registru.Dupa ce procesorul se “prinde”
ce vrea sa faca acasta instructiune,incepe efectiv executarea ei de catre unitatea de executie,dupa care posibil sa se scrie un nou rezultat
undeva in memorie sau intr-un registru.Dupa cum vedeti executarea oricarei instructiuni de catre un procesor implica mai multe faze(aici este vorba de FETCHING-DECODING-EXECUTION-WRITE),
insa in fucntie de procesor pot exista mai multe faze.Toate fazele in afara de prima se vor executa de obicei foarte repede.Prima faza
va lua ceva timp deoarece va trebui sa “dialogheze” cu memoria,iar cum memoria RAM lucreaza la o frecventa mult mai mica
decat cea a procesorului,vor interveni niste stari de asteptatre.Adica procesorul va trimite un request catre controller-ul memoriei ram,
comunicand-ui ca ar dori o anumita adresa sau o valoare stocata la o anumita adresa.Apoi procesorul va astepta pana cand acest request va fi satisfacut de
catre memorie,evident la o viteza mai scazuta.
Pentru a minimiza numarul starilor de asteptare,proiectantii au introdus asa numitele memorii cache,care pastreaza in ele
rezultatele cele mai des folosite.De ce?….Deoarece este destul de probabil ca un anumit element din memorie care a fost
folosit de procesor sa fie folosit si in viitorul foarte apropiat.Acest lucru se numeste localizare temporala a referintei.Tot in memoria cache,mai sunt pastrate si locatiile din memorie,adiacente cu
elementul care a fost folosit de catre procesor,si pentru care exista o probabilitate mare,sa fie folosite si ele in viitor.
Se presupune ca daca un element de la o anumita locatie de memorie a fost folosit recent de carte procesor,si elementele aflate
in locatii de memorie succesive cu acesta sa urmeze sa fie folosite de procesor.Acest lucru se numeste localizare spatiala a referintei.Poate ca pare …io stiu….complicat la prima vedere…
insa nu este asa.Iar pentru asata voi da un exemplu pentru a intelege si mai bine:).Ma rog…Faza de fetching a procesorului lucreaza cam asa:Mai
intai se “uita” in memoria cache pentru elementul solicitat,iar daca il gaseste …totul e ok…am putut obtine acea valoare fara sa
asteptam la memoria RAM(evident mult mai mare si mai lenta).Acest lucru se numeste CACHE HIT.In cazul in care un anumit element nu a fost gasit in memoria cache,
il “vom cauta” in memoria RAM,insa va trebui sa asteptam ceva mai mult,asa cum am zis mai devreme.Cand un anumit element solicitat de procesor nu este gasit in cache,vom spune ca am avut parte de un CACHE MISS,si
drept urmare va trebui sa il cautam in RAM.Sa luam un exemplu.Fie:
for(i = 0 ; i <= 20 ; i++){ v[i] = i*i; }
Un exemplu simplu….fiecare element al vectorului v va lua valoarea i la patrat,unde i este pozitia pe care se afla el.
Acest exemplu foloseste din plin ceea ce se numeste locazizare temporala si spatiala a referentei.Este vorba de un ciclu for.Variabila contor este i.
Mai mult de atat,i va fi accesata la fiecare ciclu din cele 20 de cicluri cate se vor executa,deci avem localizare temporala a referintei.Pentru asta,
variabila i va fi pastrata in memoria cache,astfel incat,atunci cand la un ciclu urmator,procesorul sa nu mai astepte sa o aduca din memorie,
ci o va lua direct din meoria cache,deoarece memoria cache lucreaza la frecventa procesorului,nemaifiind nevoie de stari de asteptate suplimentare.
Mai mult de atat,observam ce elementele vectorului v sunt accesate unul dupa altul,deci avem localizare spatiala a referintei.
Si este natural,ca atunci procesorul,doreste sa obtina adresa lui v[0] pentru a scrie in ea,sa aduca din memoria RAM in memoria cache si urmatoarele locatii de memorie,
pentru ca la urmatoarele accese,procesorul sa nu mai astepte la memoria RAM,fiindca ar fi un timp consumat degeaba:P,ci sa le ia direct din cache la o viteza mult mai mare.
Evident un element ce a fost gasit in cache(cache hit),si care urmeza a fi scris(ca de exemplu v[i] = i*i),va fi scris in cache,iar apoi in memoria RAM,pentru
ca elementele din RAM sa fie intr-o stare consistenta.
Acum ca tot am vb atat de mult despre memoria cache,sa ne intoarcem la exemplul cu spinlock-ul nostru:P
Sa ne mai uitam odata la cele doua implementari:
void AcquireSpinlock(SpinLock *s){ while(TestAndSet(s)) ; } void AcquireSpinLock(SpinLock *L){ while (TestAndSet(L)) while (*L == 1) ; }
OK….In prima implementare,se va apela functia TestAndSet(),caruia i se va transmite un pointer catre spinlock-ul nostru.Aceasta functie(TestAndSet),asa cum am mai
spus de o mie de ori va face asa:
int TestAndSet(SpinLock *s){ int temp = 1; __asm{ mov ax,temp mov bp,s lock xchg ax,ds:[bp] } return (temp); }
NOTA:
Cam asta face rutina TestAndSet,aici fiind implementata in Visual C++.Am preferat aceasta implementare deoarece este in C iar partea care trebuie neaparat codata in assembler este inserata direct in codul de C,
si nu in Assembler pur asa cum am facut prima oara.Am folosit acea notatie cam urata cu ds:[bp].Ideea e ca noi transmitem functiei un pointer la
spinlock,si nu valoarea lui,deoarece trebuie sa modificam valoarea spinlock-ului,deci folosim apelul prin referinta,asa cum este el in C,folosind pointeri.
In partea de assembler,prin instructiunea mov bp,s registrul bp va contine valoarea lui s(s este pointer la spinlock),adica
adresa de memorie a spinlock-ului.pentru a ne referi la valoarea continuta la o anumita locatie de memorie in mod indirect(adica fara sa stim exact la ce adresa este),in aseembler folosim ceea ce se
numeste adresarea bazata.Ma rog…exista o discutie lunga vis-a-vis de adresarea memoriei in assembler….recomand The Art ofAssembly…e pe departe cea mai buna
Deci acum ca am vazut cum arata TestAndSet scrisa in Visual C++,sa revenim……Deci cum spuneam,in prima implementare,
functia TestAndSet va intoarce in variabila temp valoarea spinlock-ului inainte ca ea sa fi fost setata(valoarea veche).Daca aceasta fost 0,evident conform regulilor din C,
ciclul while nu se mai executa si se va trece mai departe,adica se va intra in sectiunea critica,insa…daca valoarea veche este 1 atunci ciclul se va executa inca odata(tot conform regulilor din C…tot ce este 0 este fals…daca conditia unui if este egala cu 0,atunci corpul if-ului nu se va executa,la fel si pt while sau do…insa daca este 1,se va executa inca odata)
Deci daca valoarea veche a spinlock-ului este 1 ciclul while se va executa pana cand ea va fi pusa pe 0.La fiecare executie,asa cum am mai spus,functia TestAndSet,va executa lock xchg…,care va bloca magistrala creand ceea ce se numeste HOT SPOT.
In cea de-a doua implementare,functia TestAndSet() se va executa doar odata,iar daca valoarea intoarsa este 0 vom intra in sectiunea critica…daca nu…inseamna ca valoarea intoarsa de rutina TestAndSet este 1,deci vom intra in corpul cicluului while
si vom executa ce se afla acolo…adica un alt ciclu while care va testa valoarea spinlock-ului,pointat de catre pointerul L.Ideea din spatelei acestei chestii este ca..acum vom cicla in jurul variabilei pointer pe care procesorul o va gasi in memoria cache,
si pe care o va gasi imediat…si fara sa mai execute lock xchg de fiecare data,blocand astfel magistrala,care ar putea fi folosita de alte procesoare care “fac” lucruri utile:)…eh deja parca ne-am mai linsitit
In exemplu nostru …cel cu 10 procesoare,cele 9 procesoare care vor dori sa intre in sectiunea lor critica,se vor afla in busy waiting,dar de data aceasta vor cicla testand doar valoarea din memorie a spinlock-ul(pe care o vor lua din cache-urile proprii),fara sa mai creeze situatia neplacuta de hot spot.
Procesoarele care fac lucruri utile si care vor dori sa scrie diverse rezultate in RAM cand se afla in sectiunea critica,o vor putea face fara sa existe asteptari prea mari,datorate executarii lui xchg de catre cele 9 procesoare asa cum se intampla in prima implementare:-)
NOTA:Aceasta modalitatate de a testa un spinlock se numeste cache spining,deoarece procesoarele aflate in busy waiting vor lua valoare din memoria cache a variabilei spinlock si o vor testa.Avem localizare temporala a referintei…va mai aduceti aminte?:P
O alta implementare ar mai putea arata asa:
if(TestAndSet(s)){ while(*s == 1) //nu faem nimik ; }else{ //totul este ok...adica valoare veche a spinlock-ului intoarsa de rutina TestAndSet //este 0,deci am setat *s pe 1 si mergem mai departe(in sectiunea critica) break; } }
Acum o intrebare va vine in minte.Ok…metoda este mai buna decat prima.Dar ce se intampla atunci cand un thread care se afla in sectiunea critica,
elibereaza spinlock-ul?…hmmmm….in sitemele multiprocesor exista ceea ce se numeste coerenta memoriilor cache.
Ce inseamna asta?Asta inseamna ca atunci cand un procesor va modifica o valoare din memorie care se afla in cache-ul altui
procesor,atunci si acea intrare din cache-ul procesorului,fie se va modifica la noua valoare scrisa de celalalt procesor,fie intrarea respectiva va fi invalidata.
Pentru a realiza aceasta,procesorul care va modifica valoarea respectiva din memorie,va trimite un IPI(Inter Processor Interrupt),procesoarelor care detin in memoria lor cache o copie a valorii tocmai modificate,
pentru a le instiinta de faptul ca acea valoare a fost modificata.Atunci cand o procesorul care a primita cel IPI isi va invalida linia din cache care contine
acea variabila recent modificata de un alta procesor din sistem,spunem ca avem un sistem cu coerenta a cache-urilor bazata pe invalidare.In cazul in care procesorul ce a
primit acel IPI,isi va modifica copia variabilei din cache-ul sau la noua valoare scrisa de celalalt procesor,spunem ca avem coerenta a cache-urilor prin scriere distribuita.
Evident ca sistemele cu coerenta a memoriilor cache prin scriere distribuita este mai bun deoarece la urmatoarea accesare a acelei copii din cache nu se va produce un cache miss,ci din contra,aceasta accelerand procesul de regasire a unei variabile direct
in cache-ul procesorului.In cazul in care avem un sistem multiprocesor cu coerenta a cache-urilor prin invalidare de linii,atunci la
urmatoarea accesare a acelei variabile,procesorul o va cauta in cache insa linia pe care se afla este invalidata,producandu-se astfel un cache miss,iar porcesorul respectiv va trebui sa o caute in memoria principala.
Sa presupunem ca avem un sistem multiprocesor cu coerenta a memoriilor cache prin invalidare de linii.Si sa mai presupunem ca un procesor se afla in sectiunea sa critica,iar celelalte procesoare sunt in asteptare ocupata(busy waiting).
La un moment dat thread-ul care se afla in sectiunea critica,si-a facut “treaba”,si va “dori” sa iasa facand un apel la rutina
ReleaseSpinLock(s),care,cum am mai zis,nu face altceva decat ii atribuie lui *s valoarea 0(spinlock-ul este acum liber,si poate fi castigat de alte thread-uri ce ruleaza pe alte procesoare din sistem).
Cand ReleaseSpinLock() a scris valoarea 0 la adresa de memorie unde se afla spinlock-ul,automat(este garantat prin hardware acest mecanism),procesorul respectiv(cel pe care se executa ReleaseSpinLock),va trimite in o instiintare(o intrerupere interprocesor) celorlalte
procesoare din sistem care au cate o copie a valorii spinlock-ului in memoriile lor cache,rezultand invalidarea acelor linii din cache-urile fiecaruia.
Evident ca la urmatoarea accesare,a valorii spinlock-ului procesoarele vor cauta aceasta valoare in cache si va rezulta un cache miss,urmand ca ele sa caute acea valoare in memoria RAM.Si aici este o mica problema…tot legata de performanta…dar nu foarte costisitoare,deoarece
,cache miss-urile se realizeaza fooooarte repede(chiar si starile de asteptare)…undeva in jurul a cateva nanosecunde…deci extrem de repede…dar oricum e bine de stiut si asta:
Un thread a eliberat spinlock-ul,provocand astfel o invalidare a liniilor din cache-urile procesoarelor ce detin o copie a
valorii acestuia.Fiecare procesor va produce un cache miss cautand valoarea in RAM…primul care a gasit spinlock-ul in RAM il va seta la valoarea 1(conform algoritmului de castigare a unui spin lock,prin ce-a de a doua metoda),
si va intra linistit in sectiunea sa critica.Intre timp alte procesoare mai lenese vor produce un cache miss,urmand si ele sa caute valoarea spinlock-ului in RAM,o vor seta si ele tot pe 1,iar apoi vor testa valoarea veche a spinlock-ului pastratat in variabila temp.Care,evident este tot 1,si in concluzie isi vor rezuma busy waiting-ul.
Problema este ca fiecare procesor care va executa TestAndSet(),va suprascrie valoarea spinlock-ului,generand iar un sir de IPI-iuricare vor invalida copiile din cache-urile procesoarelor ce contrin pe o linie o valoare a lui spinlock.
Astfel se va genera o serie de invalidari pentru o anumita perioada de timp,iar procesoarele vor produce o serie de cache miss-uri.
De exemplu primul thread care a setat valoare spinlock-ului pe 1 si a testat valoarea veche,a vazut ca este 0 deci a intrtat in sectiunea critica.
Al doilea procesor va face acelasi lucru,insa va valoarea veche acuma este 1,deci va ramane in continuare in busy waiting.Al treilea procesor evident va face acelasi lucru,va vedea valoarea veche a lui spinlock ca este 1 deci isi va rezuma busy waiting-ul,insa el a setat spinlock-ul la valoarea 1,provocand astfel o invalidare a liniilor din cache-url celorlalte procesoare,implicit si al procesorului care a testa si
a setat spinlock-ul inaitea sa,ir acesta din urma iar va prioduce un cache miss.Al patrulea procesor va face acelasi lucru(va seta spinlock-ul la 1 si va testa vechea valoare),provocand iar o serie de invalidari de linii din cache.Iar acum cele doua procesoare care au testat si au setat spinlock-ul inaintea sa,vor produce din nou cache miss….si tot asa…
Insa perioada asta de “agitatie” in care procesoarele produc cache miss dupa cache miss va trece foarte repede si oricum va fi invizibila aplicatiei,deoarece se vor realiza intr-un timp foarte rapid.
Alte alternative pentru implementarea spinlock-urilor.(InQueued SpinLock & SpinLock Acquireing with delay)
O alta alternativa pentru implementarea spinlock-urilor este ceea ce se numeste Queueing SpinLock.Ce inseamna asta?
Inseamna ca,daca avem un numar oarecere de procesoare P,care doresc sa intre in sectiunea lor critica,acestea in loc sa cicleze testand valoarea spinlock-ului,vor fi asezate intr-o coada,fiecaruia
dandui-se un flag in jurul caruia sa se “invarta”:).Cand unul din procesoare a ieshit din sectiunea sa critica,ii va da dreptul urmatorului procesor din coada sa intre in sectiunea sa critica.O posibila implementare in
pseudocod a acestui algoritm ar arata cam asa:
//Constante #define OWNER 0 #define BUSY 1 typedef struct _KSPIN_LOCK_INQUEUED{ intultim; //Vectorul flags va retine cate o pozitie pentru fiecare procesor //doritor de a intra in sectiunea critica. //P este numarul total de procesoare din sistem. int flags[P]; }KSPIN_LOCK_INQUEUED,*PKSPIN_LOCK_INQUEUED; KSPIN_LOCK_INQUEUED lock; //lock este spinlock-ul nostru:-) PKSPIN_LOCK_INQUEUED SpinLock = &lock; //SpinLock este pointer la spinlock-ul nostru:-) SpinLock->ultim = 0; SpinLock->flags[0] = OWNER; void AcquireQueuedSpinLock(PKSPIN_LOCK_INQUEUED SpinLock){ int spin; spin = ReadAndIncrement(SpinLock->ultim); //ReadAndIncrement este o rutina care va implementa //instructiunea atomica read and increment,care pe //anumite platforme s-ar putea sa nu fie disponbibila... //Pe Intel ea se se poate implementa folosind //instructiunea XADD(eXchange and ADD). while(SpinLock->flags[spin] == BUSY) ; //Nu facem nimik....just spining:P } void ReleasequeuedSpinLock(){ SpinLock->flags[spin] = BUSY; SpinLock->flags[spin + 1] = OWNER; }
Sa vedem ce facem aici….In prumul rand aici spinlock-ul este implementat sub forma unei structuri care contine o variabila intreaga
numita “ultim”,care la prima vedere are un rol de ciudat,si un array cu un anumit numar de elemente care poate parea si mai ciudat:P.
Sa vedem exact despre ce este vorba.Observati in partea de initializare a spinlock-ului ca ultim ia valoarea 0 iar flags[0] = OWNER.
Avem acele doua #define-uri acolo,OWNER = 0 iar BUSY = 1.Astfel primul element din vectorul flags a fost initializat cu valoarea OWNER(0),iar restul elementelor au fost initializate cu valoarea BUSY(1).
Variabila ultim va fi incermentata la fiecare incercare de acquireing a spinlock-ului.Daca ne uitam in corpul functiei AcquireSpinLock observam,
ca avem o variabila locala spin in care vom depune valoarea lui ultim.Rutina ReadAndIncrement,mai intai va intoarce valoarea veche a lui ultim iar apoi o va incremneta.
La primul apel spin va avea valoarea 0,iar ultim va fi incrementata la valoarea 1.Asa cum stim,…la initializarea spinlock-ului,flags[0] = OWNER,deci acum vom testa valoarea asociata din array-ul flags(valoarea asociata fiind spin)
…deci flags[spin] = 0…intram in sectiunea critica.Celelalte thread-uri vor incerca sa fac acelasi lucru.De exemplu,
al-doilea thread va obtine in variabila sa locala spin valaorea lui ultim care acuma este 1 si o va incrementa(pe ultim) la valoarea 2.
Apoi va executa ciclul while si va “vedea” ca flags[1] = BUSY,si atat timp cat este busy va executa acest ciclu,pana cand va deveni liber.
Deci in concluzie fiecare thread va testa intr-un ciclu while,o anumita valoare.
Rutina care elibereaza un spinlock este chioar simpla.Va pune pe flag-ul personal valoarea busy,si apoi va acorda
controlul urmatorului procesor.
Aceasta implementare este foarte buna din punctul de vedere al performantei,deoarece procesoarele care nu au reusit sa intre in sectiunea
lor critica vor testa valoarea unui flag privat,fara sa interogheze valoarea spinlock-lui.Acest lucru este bun deoarece,fata de prima
implementare,nu avem parte de hot spot-uri,care sa sugrume magistrala sistemului,incetinind astfel si procesoarele care
fac lucruri utile,…aici fiecare procesor va testa valoarea unei variabile locale thread-ului,care se va afla in cache,iar spre deosebire
de prima implementare,atunci cand un thread va parasi sectiunea sa critica,va “lasa” controlul spinlock-ului in “grija” altui thread din coada,
care doarea sa intre in sectiunea sa crtica,nemaiexistand astfel acea “lupta” intre thread-uri..care sa intre primul in sectiunea critica.
Pe langa asta fata de primele doua implementari,unde atunci cand un thread iese din sectiunea sa critica,unul din thread-urile care erau in
busy waiting va inra in sectiunea critica…insa doar acela care va fi mai “rapid”…adica thread-ul care va intra in sectiunea critica este ales intr-un mod aleator,existand
riscul ca anumite thread-uri sa astepte destul de mult.Aici insa avem o coada FIFO,adica primul thread care si-a anuntat dorinta de a intra in sectiunea critica,acela va intra,apoi al doilea…si asa mai departe.
