Compara i intercanvia

En informàtica, compare-and-swap (CAS) és una instrucció atòmica utilitzada en multithreading per aconseguir la sincronització. Compara el contingut d'una ubicació de memòria amb un valor donat i, només si són els mateixos, modifica el contingut d'aquesta ubicació de memòria a un nou valor donat. Això es fa com una única operació atòmica. L'atomicitat garanteix que el nou valor es calcula a partir d'informació actualitzada; si el valor hagués estat actualitzat per un altre fil mentrestant, l'escriptura fallaria. El resultat de l'operació ha d'indicar si ha realitzat la substitució; això es pot fer amb una resposta booleana simple (aquesta variant s'anomena sovint compare-and-set), o bé retornant el valor llegit des de la ubicació de memòria (no el valor escrit en ella).

Visió general

Una operació de comparació i intercanvi és una versió atòmica del següent pseudocodi, on* indica accés mitjançant un punter:

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false
    *p ← new
return true

Aquesta operació s'utilitza per implementar primitives de sincronització com semàfors i mutex, així com algorismes més sofisticats sense bloqueig i sense espera. Maurice Herlihy (1991) va demostrar que CAS pot implementar més d'aquests algorismes que la lectura, l'escriptura o la recuperació i l'addició atòmiques , i suposant un quantitat de memòria, que pot implementar-los tots. CAS és equivalent a load-link/store-conditional, en el sentit que es pot utilitzar un nombre constant d'invocacions de qualsevol primitiva per implementar l'altra de manera sense espera.

Exemple d'aplicació: sumador atòmic

Com a exemple d'ús de comparació i intercanvi, aquí hi ha un algorisme per incrementar o disminuir atòmicament un nombre enter. Això és útil en una varietat d'aplicacions que utilitzen comptadors. La funcióadd realitza l'acció *p ← *p + a, atòmicament (denota una altra vegada la indirecta del punter per*, com en C) i retorna el valor final emmagatzemat al comptador. A diferència de lacas pseudocodi anterior, no hi ha cap requisit que cap seqüència d'operacions sigui atòmica exceptecas.

function add(p: pointer to int, a: int) returns int
    done ← false
    while not done
        value ← *p // Even this operation doesn't need to be atomic.
        done ← cas(p, value, value + a)
return value + a

En aquest algorisme, si el valor de*p canvia després (o mentre!) s'obté i abans que el CAS faci l'emmagatzematge, el CAS notarà i informarà d'aquest fet, fent que l'algorisme torni a intentar-ho.