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).

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ó realitza l'acció , 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 la pseudocodi anterior, no hi ha cap requisit que cap seqüència d'operacions sigui atòmica excepte. 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 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.

Referències

Categoria:Programari