Jämförelse med utbyte ( compare and set , compare and swap, CAS ) är en atominstruktion som jämför värdet i minnet med ett av argumenten och, om det lyckas, skriver det andra argumentet till minnet. Stöds på x86 , Itanium , Sparc och andra processorfamiljer .
Liksom andra atominstruktioner är den avsedd för synkronisering mellan parallella agenter (på olika processorer eller på samma, men utan möjlighet till exklusiv fångst). Huvudapplikationen för jämförelse med utbyte är implementeringen av spinlocks och icke-blockerande algoritmer .
Atominstruktionsmetoden är motsatsen till "villkorlig notation"-metoden ( load-link/store-conditional ) .
Instruktionen att jämföra med utbytet i x86-processorer kallas CMPXCHG och exekveras enligt följande:
Därefter måste programmeraren koda en kontroll av ZF-flaggan för att ta reda på om operationen lyckades eller när den började, ersattes värdet i minnet av en annan agent.
För SPARC kallas instruktionerna för denna operation CASA och CASXA.
Det verkar som om avbrott kan inaktiveras på en maskin med en processor, och då kommer minnestillståndet definitivt inte att ändra någonting. Men det finns två problem här. Det första problemet - att inaktivera avbrott - är en relativt dyr procedur. Det andra problemet är att om avbrott är inaktiverade och tråden går in i en oändlig loop, kan programmet inte avslutas utan att starta om datorn. Därför kräver Linux höga behörigheter för koden med denna instruktion, vilket kan orsaka mycket besvär för användare av programmet.
På en multiprocessor-maskin hjälper det inte alls att inaktivera avbrott, eftersom i en situation:
1:a processorn kontrollerade att minnet inte är låst 2:a processorn kontrollerade att minnet inte är låst 1:a processorlåst minne 2:a processorlåst minne 1:a processorn bytte minne 2:a processorn bytte minne 1:a processorns olåsta minne 2:a processorns olåsta minneändringar av den första processorn kommer att gå förlorade, och programmet kommer att tro att allt är bra.
Vi har n processorer, som var och en ibland vill komma åt någon delad resurs. Till exempel till en enhet eller en delad minnesplats.
Innan vi börjar huvudarbetet kommer vi att tilldela dem unika nummer från 0 till n-1.
Låt oss välja en minnescell som indikerar vilken processor som för närvarande använder resursen. Värdet -1 kommer att indikera att resursen inte är upptagen av någon. Låt oss lägga -1 i den.
Under huvudarbetet måste varje processor kontrollera att cellen innehåller -1, och i så fall skriva in dess nummer i den. Om cellen är upptagen måste processorn vänta tills den blir ledig (vi kom överens om att den väntar och vi kommer inte att skriva program som inte uppfyller detta krav).
Så programmet kan se ut så här:
; blockering m_wait: mov eax, -1 mov ecx, 5 ; vårt processornummer är 5 cmpxchg 105BA9D2, ecx ; celladress 105BA9D2 jnz m_wait ; om resursen är låst ; arbeta med en delad resurs ... ; upplåsning ...Atomisk jämförelse med utbytesinstruktioner var inte en del av C/C++-språkstandarderna, så de implementeras antingen genom assembler eller genom icke-standardiserade språktillägg. C++11-standarden introducerade ett bibliotek av atomära operationer som har en jämförelse med ett utbyte [1] . Det finns också flera bibliotek med C/C++ implementeringar av gränssnitt till sådana instruktioner, till exempel: Intel TBB, boost.atomic, Open Portable Atomics, Glib.
Kommandot cmpxchg kan kodas direkt med hjälp av följande assembler -inline i GCC- kompilatorn ( GCC Inline Assembly ):
uint32_t * ptr ; uint32_t ret_val , old_val , new_val ; asm volatile ( "lås \n\t cmpxchgl %1,%2" : "=a" ( ret_val ) : "r" ( new_val ), "m" ( * ptr ), "0" ( old_val ) : "minne" );eller för x86-64 :
uint64_t * ptr ; uint64_t ret_val , old_val , new_val ; asm volatile ( "lås \n\t cmpxchgq %1,%2" : "=a" ( ret_val ) : "r" ( new_val ), "m" ( * ptr ), "0" ( old_val ) : "minne" );Var särskilt uppmärksam på användningen av asm volatile (inte bara asm ), som instruerar optimeringskompilatorn att denna assembler-insats har biverkningar och måste placeras i slingan där den finns i koden. Det är också obligatoriskt att ange "minne" i clobberinglistan.
GCC och några andra kompilatorer stöder inbyggda tillägg för att implementera denna instruktion:
TYPE __sync_val_compare_and_swap(TYPE* ptr, TYPE oldval, TYPE newval);Det här tillägget kanske inte implementeras för alla arkitekturer som stöds av gcc, eller inte i alla versioner av gcc. [2]
Liknande funktioner med ett annat namn finns i kompilatorer för Windows och Mac OS X: InterlockedCompareExchange(), OSAtomicCompareAndSwapPtrBarrier().
Förekomsten av en sådan instruktion öppnar stora horisonter för att förbättra kodens prestanda på grund av möjligheten att undvika lås helt och hållet .
Tänk på denna pseudokod :
läs värdet på variabeln; vi gör en del bearbetning; skriv det nya värdet på variabeln;Det vanligaste sättet att göra den här koden trådbar är att introducera synkroniseringsprimitiver ( mutex , spinlocks , etc.) så här:
vi gör blockering; läs värdet på variabeln; vi gör en del bearbetning; skriv det nya värdet på variabeln; släpp låsetMen en mer elegant metod är ofta tillämpbar:
läs värdet på variabeln; vi gör en del bearbetning; producera cmpxchg det nya värdet på variabeln, förutsatt att värdet fortfarande är lika med det gamla; om värdet ändrades av en annan tråd, upprepar vi bearbetningen;Tänk på ett klassiskt exempel på en datastruktur - en länkad lista .
struct ll_node { intkey ; _ // någon nyckel int val ; // något värde struct ll_node * nästa ; // pekare till nästa };Funktionen att infoga i den länkade listan för noden new_node efter den angivna noden är som följer:
void ll_insert_after ( struct ll_node * node , struct ll_node * new_node ) { ny_nod -> nästa = nod -> nästa ; nod -> nästa = ny_nod ; // (!!!) - var uppmärksam på den här raden }Uppenbarligen kommer koden att fungera korrekt endast under antagandet att värdet på node->next inte har ändrats av en annan tråd när raden märkt "(!!!)" körs, annars riskerar vi att förlora ändringarna av andra trådar, spawning-noder som inte är relaterade till listan ( Memory Leak ).
Det finns tre huvudsakliga sätt att hantera detta:
1) Stäng hela den länkade listan med ett mutex . Prestandamässigt är detta det sämsta sättet. För det första kommer bara en tråd att fungera med den länkade listan vid en given tidpunkt, vilket i sig förnekar alla fördelar med multithreading . För det andra är situationen i praktiken mycket värre än man kan förvänta sig: mer eller mindre intensivt simultant arbete med en sådan länkad lista kommer att generera enorma (tusentals, tiotusentals, och i vissa, särskilt intensiva fall till och med miljoner) kontextväxlingar , vilket i sig självt i sig själv kan det döda prestandan för inte bara själva applikationen utan även systemet som helhet (effekten av "prestandafall" ökar kvadratiskt med antalet datorkärnor).
2) Mer intelligent sätt. Ändra Mutex till spinlock . Några få väntecykler för ledig upptaget är mycket billigare än ett systemsamtal och den resulterande kontextväxeln. Det har en verklig effekt på SMP -system, men på enkärniga system orsakar det en "sällsynt, men välriktad" prestandadöd på grund av långa vilotider.
3) Algoritm utan blockering . Låt oss skriva om infogningsfunktionen enligt följande: gör antagandet om nod->next value explicit. Vi kommer uttryckligen att kontrollera det med kommandot cmpxchg:
void ll_insert_after ( struct ll_node * node , struct ll_node * new_node ) { struct ll_node * old_val = nod -> nästa ; // kom ihåg det gamla värdet medan ( 1 ) { ny_nod -> nästa = gammal_val ; old_val = cmpxchg ( & nod -> next , old_val , new_node ); if ( old_val == new_node ) bryta ; // Andra trådar ändrade inte nod->nästa. Operationens framgång, avsluta. // Annars försök igen } }"Kärnan" i den icke-blockerande logiken för denna funktion är CMPXCHG-instruktionen. Den kontrollerar atomärt att innehållet i minnesplatsen &node->next fortfarande innehåller värdet för old_val, och om det gör det (och sannolikheten för detta bästa fall är extremt hög), skriver den värdet på new_node-pekaren och lämnar loopen . I händelse av en delningskollision får vi det uppdaterade värdet för old_val och anger en ny iteration av slingan.
När det gäller den länkade listan ovan, är sannolikheten för en kollision extremt liten. Formellt är det lika med P count =(n/N)*p funk , där N är antalet poster i listan, n är antalet samtidiga trådar, p funk är förhållandet mellan den tid varje tråd spenderar i listan infoga funktion till det totala tidsflödesarbetet.
Den största nackdelen som hindrar användningen av kommandot cmpxchg i låslösa algoritmer är att kommandot endast ersätter ett värde. I det fall det endast är ett pekvärde eller en heltalsvariabel räcker detta. Men mycket ofta krävs det att atomiskt villkorligt ersätta två bundna variabler . Till exempel: en pekare till en buffert och dess längd, en pekare till början och slutet av data, etc. För dessa ändamål är kommandona CMPXCHG (32-bitars), CMPXCHG8B (64-bitars) och CMPXCHG16B ( x86 64 ) introduceras i Intel-processorer. Förresten, kravet på att stödja kommandot CMPXCHG16B av processorn dök upp i MS Windows version 8.1 x64.
I SPARC-processorer utförs dessa funktioner av CASA- och CASXA-instruktionerna.