Problema ABA

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 14 aprilie 2021; verificările necesită 3 modificări .

În calculul multitasking , problema ABA apare în timpul sincronizării , când o celulă de memorie este citită de două ori, aceeași valoare este citită de ambele ori, iar semnul „valoarea este aceeași” este interpretat ca „nimic nu s-a schimbat”. Cu toate acestea, un alt thread poate rula între aceste două citiri, poate schimba valoarea, face altceva și restabili valoarea veche. Astfel, primul fir va fi înșelat să creadă că nimic nu s-a schimbat, deși al doilea fir a distrus deja această presupunere.

Problema ABA apare atunci când mai multe fire de execuție (sau procese ) accesează memoria partajată pe rând . Iată un exemplu de succesiune de evenimente care duc la problema ABA:

Deși poate continua să funcționeze, este posibil ca comportamentul său să fie incorect din cauza altor modificări ascunse ale memoriei partajate (pe care nu le-a urmărit).

De obicei, problema ABA este întâlnită la implementarea unor structuri și algoritmi fără blocare . Dacă eliminați un element din listă , îl distrugeți și apoi creați un nou element și îl adăugați înapoi în listă, există șansa ca noul element să fie plasat în locul celui vechi. Indicatorul către noul element va coincide cu indicatorul către cel vechi, ceea ce va duce la o problemă: egalitatea semnelor nu este egalitatea datelor în ansamblu.

Exemplu

Luați în considerare o stivă fără blocare :

/* O implementare naivă a unei stive fără blocare care suferă de problema ABA. */ clasă stivă { volatile Obj * top_ptr ; // // Îndepărtează elementul de sus și returnează un pointer către el. // Obj * Pop () { în timp ce ( 1 ) { Obj * ret_ptr = top_ptr ; if ( ! ret_ptr ) returnează NULL ; Obj * next_ptr = ret_ptr -> next ; // Dacă elementul de sus este încă ret, presupunem că nimeni nu a schimbat stiva. // (Această afirmație nu este întotdeauna adevărată din cauza problemei ABA) // Înlocuiește atomic top cu next. if ( CompareAndSwap ( top_ptr , ret_ptr , next_ptr )) { return ret_ptr ; } // În caz contrar, stiva a fost schimbată, încercați din nou. } } // // Adaugă obj_ptr în partea de sus a stivei. // void Push ( Obj * obj_ptr ) { în timp ce ( 1 ) { Obj * next_ptr = top_ptr ; obj_ptr -> next = next_ptr ; // Dacă elementul de sus este încă următorul, presupunem că nimeni nu a schimbat stiva. // (Această afirmație nu este întotdeauna adevărată, din cauza problemei ABA) // Înlocuiește atomic top cu obj. if ( CompareAndSwap ( top_ptr , next_ptr , obj_ptr )) { întoarcere ; } // În caz contrar, stiva a fost schimbată, încercați din nou. } } };

Acest cod poate preveni de obicei problemele de concurență, dar suferă de o problemă ABA. Luați în considerare următoarea secvență:

Stiva conține inițial partea de sus → A → B → C

Thread 1 începe să execute pop:

ret = A; următorul=B;

Thread 1 este întrerupt chiar înainte de CompareAndSwap ...

{ // Thread 2 execută pop: ret = A ; următorul = B ; CompareAndSwap ( A , A , B ) // Succes, top = B return A ; } // Acum în partea de sus a stivei → B → C { // Firul 2 apare din nou: ret = B ; următorul = C ; CompareAndSwap ( B , B , C ) // Succes, top = C return B ; } // Acum în partea de sus a stivei → C șterge B ; { // Firul 2 îl împinge pe A înapoi pe stivă: A -> următorul = C ; CompareAndSwap ( C , C , A ) // Noroc, top = A }

Stiva conține acum partea de sus → A → C

Thread 1 continuă să ruleze:

CompareAndSwap(A, A, B)

Această instrucțiune reușește deoarece top == ret (ambele sunt egale cu A), se setează top la next (care este egal cu B). Dar B a fost distrus! Acest lucru va duce la rezultate proaste...

.Net vă permite să implementați funcția CompareAndSwap (CAS) în mod atomic datorită metodei Interlocked.CompareExchange().

private static bool CAS ( ref Node < T > locație , Node < T > newValue , Node < T > comparand ) { // 1. dacă comparand și locație sunt egale, atunci un alt fir nu a atins locația // 2. locația va fi fi atribuit la newValue // 3. Metoda va returna valoarea veche a locației, indiferent de atribuire // 4. copmarand va compara cu vechea valoare a locației (adică oldLocation) // 5. dacă oldLocation (vechi, returnat) nu a fost schimbat de un alt thread, atunci CAS va returna true , deoarece se potrivește cu comparand var oldLocation = Interblocat . CompareExchange < Node < T >>( locație ref , newValue , comparand ); // aceasta este o operație atomică return comparand == oldLocation ; }

Un exemplu de stivă fără blocare pentru .Net folosind o funcție atomică CAS:

public class SimpleStack < T > { private class Node < V > { public Node < V > Next ; public V Item ; } privat Nod < T > cap ; public SimpleStack () { head = new Node < T >(); } public void Push ( T item ) { Node < T > nod = new Node < T >(); nod . item = item ; face { nod . următorul = cap . următorul ; } while ( CAS ( ref head . Next , node , node . Next ) == false ); // așteptați până la nod.Next și head.Next indică același element. // Apoi puteți schimba pointerii astfel încât capul să indice nodul. După acea ieșire din buclă. } public T Pop () { Node < T > nod ; do { nod = cap . următorul ; if ( nod == null ) returnează implicit ( T ); } while ( CAS ( cap ref . Next , nod . Next , nod ) == false ); // 1. Nu va fi nicio problemă ABA în CAS. // 2. node.Next nu aruncă o NullReferenceException (nod!= null), // deoarece memoria este gestionată în nodul de retur .Net . articol ; } }

Problema ABA pentru această implementare a stivei pe .net este irelevantă de mediul de colectare a gunoiului: nu pierdem sau reutilizam (în alt fir) referința la nod (când accesăm nodul. Următorul în CAS) dacă firul #2 vine pe primul loc decât firul #1 va efectua operația Pop(). În mediile fără management al memoriei, această problemă este acută și această soluție nu este potrivită.

Soluții alternative

O soluție comună este adăugarea de biți „marcaj” suplimentari la valoarea testată. De exemplu, un algoritm care utilizează compararea și schimbarea pe pointeri ar putea folosi biții inferiori ai unei adrese pentru a verifica de câte ori a fost schimbat pointerul. Din această cauză, următoarea comparație și schimbare nu va funcționa, deoarece biții de marcare nu se potrivesc. Acest lucru nu rezolvă complet problema, deoarece valoarea biților de etichetă poate suferi un wraparound zero . Unele arhitecturi oferă o comparație și schimb de două cuvinte care permite o etichetă mai mare. Aceasta se numește de obicei ABA' deoarece a doua valoare a lui A este ușor diferită de prima.

Abordarea corectă, dar costisitoare, este utilizarea nodurilor intermediare, care nu sunt date utilizator, dar oferă invarianță pentru operațiunile de adăugare și eliminare. [Valois].

O altă abordare este utilizarea unuia sau mai multor indicatori de pericol (indicatori de pericol) - indicatori care, în principiu, nu pot apărea într-o structură de date. Fiecare indicator de pericol denotă o stare intermediară a structurii în procesul de schimbare; a avea pointeri necesită o sincronizare suplimentară ( Dag Lee ).

Unele arhitecturi oferă operații atomice „lărgite”, astfel încât, de exemplu, este posibil să se schimbe atomic ambele referințe simultan, înainte și înapoi, într-o listă dublu legată.

Unele arhitecturi oferă o instrucțiune condițională de stocare, legată de încărcare, în care o celulă poate fi scrisă numai dacă nu au existat alte scrieri în celula specificată. Acest lucru separă efectiv caracteristica „celula conține o valoare” de caracteristica „celula a fost schimbată”. Exemple de arhitectură sunt ARM , DEC Alpha , PowerPC .

Literatură

  1. Damian Dechev, Peter Pirkelbauer și Bjarne Stroustrup. Matrice redimensionabile dinamic fără blocare
  2. Julian M Bucknall, Structuri de date fără blocare: stiva. [unu]

Link -uri