Problém ABA

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. dubna 2021; kontroly vyžadují 3 úpravy .

V multitasking computingu nastává problém ABA během synchronizace , kdy je paměťová buňka čtena dvakrát, stejná hodnota je čtena v obou případech a znaménko „hodnota je stejná“ je interpretováno jako „nic se nezměnilo“. Mezi těmito dvěma čteními však může běžet jiné vlákno, změnit hodnotu, provést něco jiného a obnovit starou hodnotu. První vlákno bude tedy oklamáno, že se nic nezměnilo, ačkoli druhé vlákno již tento předpoklad zničilo.

Problém ABA nastává, když více vláken (nebo procesů ) přistupuje ke sdílené paměti po jednom . Zde je příklad sledu událostí vedoucích k problému ABA:

I když může nadále fungovat, je možné, že jeho chování bude nesprávné kvůli jiným, skrytým změnám sdílené paměti (které nesledoval).

Obvykle se problém ABA vyskytuje při implementaci struktur a algoritmů bez zámku . Pokud odeberete prvek ze seznamu , zničíte jej a poté vytvoříte nový prvek a přidáte jej zpět do seznamu, existuje šance, že nový prvek bude umístěn na místo starého. Ukazatel na nový prvek se bude shodovat s ukazatelem na starý, což povede k problému: rovnost znaků není rovností dat jako celku.

Příklad

Zvažte zásobník bez zámku :

/* Naivní implementace zásobníku bez zámku, který trpí problémem ABA. */ třída Zásobník { volatile Obj * top_ptr ; // // Odebere horní prvek a vrátí na něj ukazatel. // Obj * Pop () { zatímco ( 1 ) { Obj * ret_ptr = top_ptr ; if ( ! ret_ptr ) return NULL ; Obj * next_ptr = ret_ptr -> next ; // Pokud je horní prvek stále ret, předpokládejme, že nikdo nezměnil zásobník. // (Toto tvrzení není vždy pravdivé kvůli problému ABA) // Atomicky nahradit top za next. if ( CompareAndSwap ( top_ptr , ret_ptr , next_ptr )) { return ret_ptr ; } // V opačném případě se zásobník změnil, zkuste to znovu. } } // // Přidá obj_ptr na vrchol zásobníku. // void Push ( Obj * obj_ptr ) { zatímco ( 1 ) { Obj * next_ptr = top_ptr ; obj_ptr -> dalsi = dalsi_ptr ; // Pokud je horní prvek stále další, předpokládejme, že nikdo nezměnil zásobník. // (Toto tvrzení není vždy pravdivé, kvůli problému ABA) // Atomicky nahraďte top obj. if ( CompareAndSwap ( top_ptr , next_ptr , obj_ptr )) { vrátit se ; } // V opačném případě se zásobník změnil, zkuste to znovu. } } };

Tento kód může obvykle zabránit problémům souběžnosti, ale trpí problémem ABA. Zvažte následující sekvenci:

Zásobník zpočátku obsahuje horní → A → B → C

Vlákno 1 začíná provádět pop:

ret = A; další=B;

Vlákno 1 je přerušeno těsně před CompareAndSwap ...

{ // Vlákno 2 provede pop: ret = A ; další = B ; CompareAndSwap ( A , A , B ) // Hodně štěstí, top = B return A ; } // Nyní na vrcholu zásobníku → B → C { // Vlákno 2 se znovu objeví: ret = B ; další = C ; CompareAndSwap ( B , B , C ) // Hodně štěstí, top = C return B ; } // Nyní na vrcholu zásobníku → C smazat B ; { // Vlákno 2 zatlačí A zpět do zásobníku: A -> další = C ; CompareAndSwap ( C , C , A ) // Luck, top = A }

Zásobník nyní obsahuje horní → A → C

Vlákno 1 stále běží:

Porovnat a vyměnit (A, A, B)

Tato instrukce je úspěšná, protože top == ret (oba se rovnají A), nastaví začátek na další (která se rovná B). Ale B bylo zničeno! To povede ke špatným výsledkům...

.Net umožňuje atomicky implementovat funkci CompareAndSwap (CAS) díky metodě Interlocked.CompareExchange().

private static bool CAS ( ref Node < T > location , Node < T > newValue , Node < T > comparand ) { // 1. pokud jsou comparand a umístění stejné, pak se jiné vlákno nedotklo umístění // 2. location will být přiřazena k newValue // 3. Metoda vrátí starou hodnotu umístění bez ohledu na přiřazení // 4. copmarand porovná se starou hodnotou umístění (tj. oldLocation) // 5. pokud oldLocation(staré, vráceno) nebylo změněno jiným vláknem, pak CAS vrátí true , protože odpovídá srovnání var oldLocation = Interlocked . CompareExchange < Node < T >>( ref location , newValue , comparand ); // toto je atomická operace return comparand == oldLocation ; }

Příklad bezzámkového zásobníku pro .Net pomocí atomické funkce CAS:

public class SimpleStack < T > { private class Node < V > { public Node < V > Next ; veřejná V Položka ; } private Node < T > head ; public SimpleStack () { head = new Node < T >(); } public void Push ( T item ) { Node < T > node = new Node < T >(); uzel . předmět = předmět ; udělat { uzel . další = hlava . další ; } while ( CAS ( ref head . Next , node , node . Next ) == false ); // počkejte, dokud node.Next a head.Next neukazují na stejný prvek. // Potom můžete zaměnit ukazatele tak, aby hlava ukazovala na uzel. Po tomto výstupu ze smyčky. } public T Pop () { Node < T > node ; do { uzel = hlava . další ; if ( node == null ) return default ( T ); } while ( CAS ( ref head . Next , node . Next , node ) == false ); // 1. V CAS nebude problém s ABA. // 2. node.Next nevyvolá výjimku NullReferenceException (node ​​​​!= null), // protože paměť je spravována v .Net return node . položka ; } }

Problém ABA pro tuto implementaci zásobníku na .net se stává irelevantním prostředím garbage collector: neztrácíme ani znovu nepoužíváme (v jiném vlákně) odkaz na uzel (při přístupu k node.Další v CAS), pokud vlákno #2 je první, než vlákno #1 provede operaci Pop(). V prostředích bez správy paměti je tento problém akutní a toto řešení není vhodné.

Řešení

Běžným řešením je přidat k testované hodnotě další bity "značky" . Například algoritmus, který používá porovnávání a zaměňování ukazatelů, může použít nižší bity adresy ke kontrole, kolikrát byl ukazatel změněn. Z tohoto důvodu nebude další porovnání a výměna fungovat, protože bity značek se nebudou shodovat. To problém zcela nevyřeší, protože hodnota tagových bitů může podléhat nulovému obtékání . Některé architektury poskytují dvouslovné porovnání a výměna , které umožňuje větší štítek. To se obvykle nazývá ABA', protože druhá hodnota A se mírně liší od první.

Správným, ale nákladným přístupem je použití mezilehlých uzlů, které nejsou uživatelskými daty, ale poskytují neměnnost pro operace přidávání a odstraňování. [Valois].

Dalším přístupem je použití jednoho nebo více ukazatelů nebezpečí (indikátorů nebezpečí) – ukazatelů, které se v zásadě nemohou objevit v datové struktuře. Každý ukazatel nebezpečí označuje přechodný stav struktury v procesu změny; mít ukazatele vyžaduje další synchronizaci ( Dag Lee ).

Některé architektury poskytují "zvětšené" atomické operace, takže je například možné atomicky měnit obě reference najednou, dopředu i dozadu, ve dvojitě propojeném seznamu.

Některé architektury poskytují podmíněný příkaz propojený se zatížením, ve kterém lze do buňky zapisovat pouze v případě, že do zadané buňky nebyly provedeny žádné jiné zápisy. To efektivně odděluje funkci „buňka obsahuje hodnotu“ od funkce „buňka byla změněna“. Příklady architektury jsou ARM , DEC Alpha , PowerPC .

Literatura

  1. Damian Dechev, Peter Pirkelbauer a Bjarne Stroustrup. Dynamicky měnitelná pole bez uzamčení
  2. Julian M Bucknall, Datové struktury bez zámku: zásobník. [jeden]

Odkazy