ABA-problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 april 2021; kontroller kräver 3 redigeringar .

I multitasking- beräkningar uppstår ABA-problemet under synkronisering , när en minnescell läses två gånger läses samma värde båda gångerna och "värdet är samma"-tecknet tolkas som "ingenting har förändrats." En annan tråd kan dock köras mellan dessa två läsningar, ändra värdet, göra något annat och återställa det gamla värdet. Således kommer den första tråden att luras att tro att ingenting har förändrats, även om den andra tråden redan har förstört detta antagande.

ABA-problemet uppstår när flera trådar (eller processer ) kommer åt delat minne en i taget . Här är ett exempel på händelseförloppet som ledde fram till ABA-problemet:

Även om det kan fortsätta att fungera, är det möjligt att dess beteende kommer att vara felaktigt på grund av andra, dolda delade minnesförändringar (som den inte har spårat).

Vanligtvis stöter man på ABA-problemet när man implementerar låsfria strukturer och algoritmer. Om du tar bort ett element från listan , förstör det och sedan skapar ett nytt element och lägger till det igen i listan, finns det en chans att det nya elementet kommer att placeras i stället för det gamla. Pekaren till det nya elementet kommer att sammanfalla med pekaren till det gamla, vilket kommer att leda till ett problem: likheten mellan tecken är inte likheten mellan data som helhet.

Exempel

Tänk på en låsfri stack :

/* En naiv implementering av en låsfri stack som lider av ABA-problemet. */ klass Stack { flyktig Obj * top_ptr ; // // Tar bort det översta elementet och returnerar en pekare till det. // Obj * Pop () { medan ( 1 ) { Obj * ret_ptr = top_ptr ; if ( ! ret_ptr ) returnera NULL ; Obj * nästa_ptr = ret_ptr -> nästa ; // Om det översta elementet fortfarande är ret, anta att ingen har ändrat stacken. // (Detta påstående är inte alltid sant på grund av ABA-problemet) // Atomiskt ersätt toppen med nästa. if ( CompareAndSwap ( top_ptr , ret_ptr , next_ptr )) { returnera ret_ptr ; } // Annars har stacken ändrats, försök igen. } } // // Lägger till obj_ptr till toppen av stacken. // void Push ( Obj * obj_ptr ) { medan ( 1 ) { Obj * nästa_ptr = top_ptr ; obj_ptr -> nästa = nästa_ptr ; // Om det översta elementet fortfarande är nästa, anta att ingen har ändrat stacken. // (Detta påstående är inte alltid sant, på grund av ABA-problemet) // Atomiskt ersätt topp med obj. if ( CompareAndSwap ( top_ptr , next_ptr , obj_ptr )) { återvända ; } // Annars har stacken ändrats, försök igen. } } };

Denna kod kan vanligtvis förhindra samtidighetsproblem, men lider av ett ABA-problem. Tänk på följande sekvens:

Högen innehåller initialt topp → A → B → C

Tråd 1 börjar köra pop:

ret = A; nästa=B;

Tråd 1 avbryts precis innan CompareAndSwap ...

{ // Tråd 2 kör pop: ret = A ; nästa = B ; CompareAndSwap ( A , A , B ) // Lycka till, topp = B returnera A ; } // Nu på högens topp → B → C { // Tråd 2 dyker upp igen: ret = B ; nästa = C ; CompareAndSwap ( B , B , C ) // Lycka till, topp = C returnera B ; } // Nu högst upp → C radera B ; { // Tråd 2 skjuter A tillbaka till högen: A -> nästa = C ; CompareAndSwap ( C , C , A ) // Luck, top = A }

Högen innehåller nu topp → A → C

Tråd 1 fortsätter:

CompareAndSwap(A, A, B)

Denna instruktion lyckas eftersom top == ret (båda är lika med A), den sätter topp till nästa (som är lika med B). Men B var förstörd! Detta kommer att leda till dåliga resultat...

.Net låter dig implementera CompareAndSwap (CAS) -funktionen atomiskt tack vare Interlocked.CompareExchange()-metoden.

privat statisk bool CAS ( ref Nod < T > plats , Nod < T > newValue , Nod < T > comparand ) { // 1. om jämförelse och plats är lika, så rörde inte en annan tråd plats // 2. plats kommer tilldelas newValue // 3. Metoden kommer att returnera det gamla platsvärdet oavsett tilldelningen // 4. copmarand kommer att jämföra med det gamla platsvärdet (dvs. oldLocation) // 5. om oldLocation(old, returned) inte har varit ändras av en annan tråd, då kommer CAS att returnera true , eftersom det matchar jämförelsen var oldLocation = Interlocked . CompareExchange < Node < T >>( ref location , newValue , comparand ); // detta är en atomär operation return comparand == oldLocation ; }

Ett exempel på en låsfri stack för .Net som använder en atomic CAS-funktion:

public class SimpleStack < T > { private class Node < V > { public Node < V > Next ; offentlig V Objekt ; } privat nod < T > huvud ; public SimpleStack () { head = new Node < T >(); } public void Push ( T item ) { Node < T > nod = new Node < T >(); nod . objekt = objekt ; gör { nod . nästa = huvud . nästa ; } while ( CAS ( ref head . Next , node , node . Next ) == false ); // vänta tills node.Next och head.Next pekar på samma element. // Sedan kan du byta pekare så att huvudet pekar mot noden. Efter det utgång från slingan. } public T Pop () { Node < T > node ; gör { nod = huvud . nästa ; if ( nod == null ) returnerar standard ( T ); } while ( CAS ( ref head . Next , node . Next , node ) == false ); // 1. Det kommer inte att finnas några ABA-problem i CAS. // 2. node.Next kastar inte ett NullReferenceException (nod​!= null), // eftersom minnet hanteras i .Net return node . Objekt ; } }

ABA-problemet för denna stackimplementering på .net görs irrelevant av garbage collector-miljön: vi förlorar eller återanvänder inte (i en annan tråd) referensen till noden (vid åtkomst till node.Next i CAS) om tråd #2 kommer först än tråd #1 kommer att utföra Pop() operationen. I miljöer utan minneshantering är detta problem akut och denna lösning är inte lämplig.

Lösningar

En vanlig lösning är att lägga till ytterligare "mark" -bitar till värdet som testas. Till exempel kan en algoritm som använder jämför-och-byta på pekare använda de lägre bitarna i en adress för att kontrollera hur många gånger pekaren har ändrats. På grund av detta kommer nästa jämför-och-byta inte att fungera eftersom markeringsbitarna inte matchar. Detta löser inte helt problemet, eftersom värdet på taggbitarna kan genomgå en nollomslutning . Vissa arkitekturer tillhandahåller en jämför-och-byte med två ord som möjliggör en större etikett. Detta kallas vanligtvis ABA' eftersom det andra värdet på A skiljer sig något från det första.

Det korrekta men dyra tillvägagångssättet är att använda mellanliggande noder, som inte är användardata, men ger invarians för tilläggs- och borttagningsoperationer. [Valois].

Ett annat tillvägagångssätt är att använda en eller flera hazard pointers (hazard indicators) – pekare som i princip inte kan förekomma i en datastruktur. Varje faropekare betecknar ett mellantillstånd av strukturen i förändringsprocessen; att ha pekare kräver ytterligare synkronisering ( Dag Lee ).

Vissa arkitekturer ger "förstorade" atomoperationer, så att det till exempel är möjligt att atomiskt ändra båda referenserna på en gång, framåt och bakåt, i en dubbelt länkad lista.

Vissa arkitekturer tillhandahåller en belastningslänkad lagringsvillkorssats där en cell endast kan skrivas till om det inte har gjorts några andra skrivningar till den angivna cellen. Detta skiljer effektivt funktionen "cellen innehåller ett värde" från funktionen "cellen har ändrats". Arkitekturexempel är ARM , DEC Alpha , PowerPC .

Litteratur

  1. Damian Dechev, Peter Pirkelbauer och Bjarne Stroustrup. Låsfria arrayer som kan ändras dynamiskt
  2. Julian M Bucknall, Låsfria datastrukturer: stacken. [ett]

Länkar