Compare-and-swap

I datavetenskapen är compare-and-swap (ungefär: jämför-och-byt ut, ofta förkortat CAS) en atomär operation CAS(M, V, N) som används i program med flera parallella processer eller trådar för att uppnå synkronisering. Operationen jämför värdet i en minnescell med adressen M med ett givet värde V. Endast om värdet i minnescellen är samma som V ändras värdet i minnescellen till det givna nya värdet N. De ovanstående stegen utförs som en enda atomär operation; andra trådar garanteras inte kunna uppdatera minnescellen M. Operationen måste slutligen rapportera huruvida det önskade värdet verkligen blev uppdaterat i minnescellen. Detta kan göras antingen med en boolesk variabel (denna variant kallas ofta compare-and-set), eller genom att återvända det värdet som fanns i M innan operationen påbörjades (inte värdet N som eventuellt lagrades i M).

Historik

Compare-and-swap och compare-and-swap-double (som byter ut två minnesceller samtidigt) har varit standardinstruktioner i IBM System/370-arkitekturen och alla dess efterföljare sedan 1970. Operativsystemen som körs på dessa arkitekturer använder denna instruktion flitigt för att förenkla process- och processorparallellism samtidigt som de undviker spinlocks som användes i tidigare varianter av IBM:s operativsystem. Samtidigt eliminerades användandet av test-and-set. Resultatet blev väsentligt ökad prestanda.

Moderna processorarkitekturer implementerar nästan alltid en variant av CAS för att möjliggöra effektiv parallellism. Hos x86- och Itaniumarkitekturerna används till exempel instruktionen CMPXCHG (compare and exchange) för ändamålet.

Implementering

Följande funktion, skriven i C, simulerar en variant av compare-and-swap som återvänder det gamla värdet i minnescellen. Dock uppvisar funktionen inte den atomäritet som en verklig compare-and-swap-instruktion uppvisar.

int compare_and_swap(int * M, int V, int N)
{
    int gammalt_varde = *M;
    if (gammalt_varde == V)
        *M = N;
    return gammalt_varde;
}

Värdet gammalt_varde returneras alltid, men kan testas efter compare_and_swap för att se om det är samma värde som V. Om värdena är olika betyder det att en annan process har lyckats exekvera en konkurrerande compare_and_swap och därmed ändrat värdet i M från V.

Bruk

CAS används för att implementera synkroniseringsoperationer som semaforer och mutexar, och även låsfria algoritmer. Maurice Herlihy bevisade 1991 att CAS kan användas för att implementera flera av dessa algoritmer än atomär läsning, atomär skrivning eller fetch-and-add.

Algoritmer som grundar sig på CAS brukar läsa en viktig minnescell och minnas det lästa, "gamla" värdet. Baserat på de lästa värdet beräknar algoritmerna ett nytt värde. Sedan försöker de att byta in det nya värdet med CAS. Om CAS returnerar ett annorlunda värde än det "gamla" värdet har algoritmen misslyckats och måste börja om: minnescellen läses på nytt, ett nytt värde beräknas om, och CAS-operation prövas igen. Detta upprepas tills CAS-operationen lyckas, eller tills algoritmen beslutar att för mycket tid har gått åt och avbryter operationen helt med en timeout.