Comparar i intercanviar

Comparar i intercanviar, també conegut per les sigles CAS (de l'anglés Compare And Swap), és una operació atòmica usada en el disseny d'algoritmes concurrents per a permetre la sincronisació de fils d'eixecució sense recórrer a bloquejos dels mateixos.

Descripció

Bàsicament consistix en comparar el valor d'una variable en un valor esperat i, si el valor és l'esperat, llavors intercanvia el valor de la variable en el d'una atra variable. Tot açò realisat d'una forma atòmica. La atomicidad garantisa que el nou valor és calculat basat en informació actualisada; si entretant el valor ha segut actualisat per un atre fil d'eixecució, l'escritura fallarà, El resultat de l'operació té que indicar si es va realisar la substitució; açò pot ser realisat en una simple resposta booleana (a esta variant se li crida 'comparar i establir), o retornant el valor llegit de la memòria (no l'escrit).

Més formalment podem definir l'algoritme de la següent forma:

Paràmetros d'entrada:

Una localisació de memòria V a on el valor té que ser reemplaçat.

Un valor vell Al qual va ser llegit pel fil l'última volta.

Un nou valor B el qual deuria ser escrit sobre V

Supongam que crec que V deuria tindre el valor A ya que té el valor B. Si V no té el valor B llavors no es deuria fer res i se'm deuria donar una resposta indicant-me que estava equivocat.

En resum, quan varis fils d'eixecució intenten actualisar la mateixa variable simultàneament usant CAS, un gana i actualisa el valor de la variable i el restant pert. Pero els perdedors no són sancionats en la suspensió del fil, ells són lliures de tornar a intentar realisar l'operació o simplement no fer res.

La tècnica CAS és optimista ya que procedix en l'actualisació a l'espera de tindre èxit, no obstant pot haver fallo, que serà detectat, si un atre fil ha actualisat la variable des de que ell la va examinar per última volta.

Eixemple

Supongam que V és una localisació de memòria a on està almagasenat el valor 10. Hi ha múltiples fils que volen incrementar este valor i usar el valor incrementat per a atres operacions. Supongam els següents passos:

1. Fils 1 i 2 volen realisar l'increment, lligen el valor i decidixen que volen incrementar-ho a 11.
2. Fil 1 entra primer en CAS i compara V en l'últim valor llegit. Açò provocarà que el valor de V siga sobreescrito i es convertixca a 11
3. Fil 2 entra en CAS i intenta realisar l'operació i esta falla tornant el valor 11
4. Fil 2 decidix tornar a llegir i decidix incrementar a 12
5. Fil 2 entra en CAS i actualisa el valor de la variable a 12.