Sammenligning med udveksling ( sammenlign og sæt , sammenlign og swap, CAS ) er en atominstruktion, der sammenligner værdien i hukommelsen med et af argumenterne, og hvis det lykkes, skriver det andet argument til hukommelsen. Understøttet på x86 , Itanium , Sparc og andre processorfamilier .
Som andre atominstruktioner er den beregnet til synkronisering mellem parallelle agenter (på forskellige processorer eller på den samme, men uden mulighed for eksklusiv indfangning). Den vigtigste anvendelse af sammenligning med udveksling er implementeringen af spinlocks og ikke-blokerende algoritmer .
Atominstruktionstilgangen er i modsætning til "betinget notation"-tilgangen ( load-link/store-conditional ) .
Instruktionen til at sammenligne med udvekslingen i x86-processorer kaldes CMPXCHG og udføres som følger:
Dernæst skal programmøren kode en kontrol af ZF-flaget for at finde ud af, om operationen var vellykket, eller på det tidspunkt, hvor den begyndte, blev værdien i hukommelsen erstattet af en anden agent.
For SPARC kaldes instruktionerne for denne operation CASA og CASXA.
Det ser ud til, at interrupts kan deaktiveres på en enkeltprocessormaskine, og så vil hukommelsestilstanden bestemt ikke ændre noget. Men der er to problemer her. Det første problem - at deaktivere interrupts - er en forholdsvis dyr procedure. Det andet problem er, at hvis afbrydelser er deaktiveret, og tråden går ind i en uendelig løkke, kan programmet ikke afsluttes uden at genstarte computeren. Derfor kræver Linux høje tilladelser til koden med denne instruktion, hvilket kan forårsage en del besvær for brugere af programmet.
På en multiprocessor-maskine vil deaktivering af interrupts slet ikke hjælpe, da i en situation:
1. processor kontrollerede, at hukommelsen ikke er låst 2. processor kontrollerede, at hukommelsen ikke er låst 1. processor låst hukommelse 2. processor låst hukommelse 1. processor skiftede hukommelse 2. processor skiftede hukommelse 1. processor ulåst hukommelse 2. processor ulåst hukommelseændringer af 1. processor vil gå tabt, og programmet vil tro, at alt er i orden.
Vi har n processorer, som hver især nogle gange ønsker at få adgang til en delt ressource. For eksempel til en enhed eller en delt hukommelsesplacering.
Før vi starter hovedarbejdet, vil vi tildele dem unikke numre fra 0 til n-1.
Lad os vælge en hukommelsescelle, der viser, hvilken processor der i øjeblikket bruger ressourcen. Værdien -1 vil indikere, at ressourcen ikke er optaget af nogen. Lad os sætte -1 i det.
Under hovedarbejdet skal hver processor kontrollere, at cellen indeholder -1, og i så fald skrive dens nummer ind i den. Hvis cellen er optaget, skal processoren vente, indtil den bliver fri (vi aftalte, at den venter, og vi vil ikke skrive programmer, der ikke opfylder dette krav).
Så programmet kan se sådan ud:
; blokering m_vent: mov eax, -1 mov ecx, 5; vores processornummer er 5 cmpxchg 105BA9D2, ecx ; celleadresse 105BA9D2 jnz m_vent ; hvis ressourcen er låst ; arbejder med en fælles ressource ... ; oplåsning ...Atomisk sammenligning med udvekslingsinstruktioner var ikke en del af C/C++ sprogstandarderne, så de er enten implementeret gennem assembler eller gennem ikke-standard sprogudvidelser. C++11-standarden introducerede et bibliotek af atomare operationer, der har en sammenligning med en udveksling [1] . Der er også flere biblioteker med C/C++ implementeringer af grænseflader til sådanne instruktioner, for eksempel: Intel TBB, boost.atomic, Open Portable Atomics, Glib.
Kommandoen cmpxchg kan kodes direkte ved hjælp af følgende assembler -inline af GCC - kompileren ( GCC Inline Assembly ):
uint32_t * ptr ; uint32_t ret_val , old_val , new_val ; asm flygtig ( "lås \n\t cmpxchgl %1,%2" : "=a" ( ret_val ) : "r" ( new_val ), "m" ( * ptr ), "0" ( old_val ) : "hukommelse" );eller til x86-64 :
uint64_t * ptr ; uint64_t ret_val , old_val , new_val ; asm flygtig ( "lås \n\t cmpxchgq %1,%2" : "=a" ( ret_val ) : "r" ( new_val ), "m" ( * ptr ), "0" ( old_val ) : "hukommelse" );Vær særlig opmærksom på brugen af asm volatile (ikke kun asm ), som instruerer optimeringskompileren om , at denne assembler-indsats har bivirkninger og skal placeres i løkken, hvor den er i koden. Det er også obligatorisk at angive "hukommelse" i clobbering-listen.
GCC og nogle andre compilere understøtter indbyggede udvidelser til at implementere denne instruktion:
TYPE __sync_val_compare_and_swap(TYPE* ptr, TYPE oldval, TYPE newval);Denne udvidelse er muligvis ikke implementeret for alle arkitekturer, der understøttes af gcc, eller ikke i alle versioner af gcc. [2]
Lignende funktioner med et andet navn findes i compilere til Windows og Mac OS X: InterlockedCompareExchange(), OSAtomicCompareAndSwapPtrBarrier().
Eksistensen af en sådan instruktion åbner store horisonter med hensyn til at forbedre kodens ydeevne på grund af muligheden for helt at undgå låse .
Overvej dette stykke pseudokode :
læse værdien af variablen; vi laver noget behandling; skriv den nye værdi af variablen;Den mest almindelige måde at gøre denne kode trådbar på er at introducere synkroniseringsprimitiver ( mutex'er , spinlocks osv.) som dette:
vi laver blokering; læse værdien af variablen; vi laver noget behandling; skriv den nye værdi af variablen; frigør låsenMen en mere elegant metode er ofte anvendelig:
læse værdien af variablen; vi laver noget behandling; producere cmpxchg den nye værdi af variablen, idet det antages, at værdien stadig er lig med den gamle; hvis værdien blev ændret af en anden tråd, gentager vi behandlingen;Overvej et klassisk eksempel på en datastruktur - en sammenkædet liste .
struct ll_node { intkey ; _ // nogle nøgle int val ; // en eller anden værdi struct ll_node * næste ; // peger til næste };Funktionen, der skal indsættes i den sammenkædede liste af noden new_node efter den angivne node, er som følger:
void ll_insert_after ( struct ll_node * node , struct ll_node * new_node ) { ny_node -> næste = node -> næste ; node -> næste = ny_node ; // (!!!) - vær opmærksom på denne linje }Det er klart, at koden kun fungerer korrekt under den antagelse, at værdien af node->next ikke er blevet ændret af en anden tråd, når linjen mærket "(!!!)" kører, ellers risikerer vi at miste ændringerne af andre tråde, spawning noder, der ikke er relateret til listen ( Memory Leak ).
Der er 3 hovedmåder at håndtere dette på:
1) Luk hele den linkede liste med en mutex . Med hensyn til ydeevne er dette den værste måde. For det første vil kun én tråd arbejde med den linkede liste på et givet tidspunkt, hvilket i sig selv negerer alle fordelene ved multithreading . For det andet er situationen i praksis meget værre, end man kunne forvente: mere eller mindre intensivt samtidig arbejde med en sådan sammenkædet liste vil generere enorme (tusinder, titusinder, og i nogle, især intensive tilfælde endda millioner) kontekstskift , som i sig selv i sig selv kan det dræbe ydeevnen af ikke kun selve applikationen, men også systemet som helhed (effekten af "performance drop" øges kvadratisk med antallet af computerkerner).
2) Mere intelligent måde. Skift Mutex til spinlock . Nogle få ledige travle ventecyklusser er meget billigere end et systemopkald og det resulterende kontekstskifte. Det har en reel effekt på SMP -systemer, men på single-core-systemer forårsager det et "sjældent, men velrettet" præstationsdræb på grund af lange tomgangstider.
3) Algoritme uden blokering . Lad os omskrive insert-funktionen som følger: gør node->next value-antagelsen eksplicit. Vi vil eksplicit kontrollere det ved hjælp af cmpxchg kommandoen:
void ll_insert_after ( struct ll_node * node , struct ll_node * new_node ) { struct ll_node * old_val = node -> næste ; // husk den gamle værdi mens ( 1 ) { ny_node -> næste = old_val ; old_val = cmpxchg ( & node -> next , old_val , new_node ); if ( old_val == new_node ) bryde ; // Andre tråde ændrede ikke node->næste. Operationens succes, exit. // Ellers prøv igen } }"Kernen" i den ikke-blokerende logik i denne funktion er CMPXCHG-instruktionen. Den kontrollerer atomisk , at indholdet af hukommelsesplaceringen &node->next stadig indeholder værdien af old_val, og hvis den gør det (og sandsynligheden for dette bedste tilfælde er ekstremt høj), skriver den værdien af new_node-markøren og forlader løkken . I tilfælde af en delingskollision får vi den opdaterede værdi af old_val og indtaster en ny iteration af løkken.
I tilfælde af den sammenkædede liste, der er betragtet ovenfor, er sandsynligheden for en kollision ekstremt lille. Formelt er det lig med P count =(n/N)*p funk , hvor N er antallet af poster på listen, n er antallet af samtidige tråde, p funk er forholdet mellem den tid, hver tråd bruger inde i indsæt funktion til det samlede tidsflow-arbejde.
Den største ulempe, der hindrer brugen af kommandoen cmpxchg i låseløse algoritmer, er, at kommandoen kun erstatter én værdi. I det tilfælde, hvor det kun er en pointerværdi eller en heltalsvariabel, er dette tilstrækkeligt. Imidlertid er det meget ofte nødvendigt at atomisk betinget erstatte to bundne variabler . For eksempel: en pegepind til en buffer og dens længde, en pegepind til begyndelsen og slutningen af data osv. Til disse formål er CMPXCHG (32-bit), CMPXCHG8B (64-bit) og CMPXCHG16B ( x86 64 ) kommandoerne introduceret i Intel-processorer. Kravet om at understøtte CMPXCHG16B-kommandoen af processoren dukkede i øvrigt op i MS Windows version 8.1 x64.
I SPARC-processorer udføres disse funktioner af CASA- og CASXA-instruktionerne.