Skip to content

Latest commit

 

History

History
51 lines (33 loc) · 2.14 KB

CAS.adoc

File metadata and controls

51 lines (33 loc) · 2.14 KB
Raw

Compare and Swap

Este algoritmo compara el contenido de una posición de memoria contra un valor dado, si los valores son los mismo modifica el contenido con un nuevo valor. Esto es realizado como una operación atómica. La atomicidad garantiza que el nuevo valor fue calculado en base a información actualizada. Si el valor fue actualizado por otro thread, la escritura fallara. El resultado de la operación debe indicar si la operación realizo la substitución; esto puede ser indicado por medio de un valor booleano en la respuesta.

La operación de CAS tiene 3 parámetros:

  • Una ubicación de memoria donde debemos reemplazar el valor

  • Valor anterior que fue leído por el thread

  • Valor nuevo que debe sobrescribir el anterior

CAS dice "Yo creo que la posición V debería tener el valor A; Si esto se cumple entonces pongo el valor B, si esto no se cumple aviso que no se cumplió la substitución". CAS es un locking optimista ya que continua con el update con la esperanza de poder realizarlo, y puede detectar si algún thread actualizo el valor.

Revisemos esto con un ejemplo.

  • El thread 1 y 2 quieren incrementar el valor en V (Valor actual 10) y incrementarlo a 11.

V = 10, A = 0, B = 0

  • Ahora el thread 1 viene primero y compara el valor V con el valor leido anteriormente

V = 10, A = 10, B = 11

IF (A = V) THEN
   	V = B
ELSE
	Operation Failed
	RETURN V

Como se puede observar el valor de V será 11

  • El thread 2 llega e intenta la misma operación

V = 11, A = 10, B = 11

IF (A = V) THEN
	V = B
ELSE
   	Operation Failed
	RETURN V

  • En este caso el valor de V no es igual al de A entonces la operación falla. Dado que el thread 2 ve que no pudo realizar la operación, vuelve a intentarlo con nuevos valores

V = 11, A = 11, B = 12

Ahora la condición se cumple y se incrementa el valor a 12.

En resumen, cuando múltiples threads intentan actualizar la misma variable de forma simultanea usando CAS, uno de ellos realiza la actualización y el resto detecta ese cambio y vuelve a intentarlo con nuevos valores, de esta forma no hay bloqueo entre los thread y estos son libres de reintentar la operación o de no hacer nada.