Comparar e intercambiar
Comparar e intercambiar, también conocido por las siglas CAS (del inglés Compare And Swap), es una operación atómica usada en el diseño de algoritmos concurrentes para permitir la sincronización de hilos de ejecución sin recurrir a bloqueos de los mismos.[1]
Descripción editar
Básicamente consiste en comparar el valor de una variable con un valor esperado y, si el valor es el esperado, entonces intercambia el valor de la variable con el de otra variable. Todo esto realizado de una forma atómica. La atomicidad garantiza que el nuevo valor es calculado basado en información actualizada; si entretanto el valor ha sido actualizado por otro hilo de ejecución, la escritura fallará, El resultado de la operación tiene que indicar si se realizó la sustitución; esto puede ser realizado con una simple respuesta booleana (a esta variante se le llama 'comparar y establecer), o retornando el valor leído de la memoria (no el escrito).[2]
Más formalmente podemos definir el algoritmo de la siguiente forma:[2]
- Parámetros de entrada:
- Una localización de memoria V donde el valor tiene que ser reemplazado.
- Un valor viejo A el cual fue leído por el hilo la última vez.
- Un nuevo valor B el cual debería ser escrito sobre V
- Supongamos que creo que V debería tener el valor A ya que tiene el valor B. Si V no tiene el valor B entonces no se debería hacer nada y se me debería dar una respuesta indicándome que estaba equivocado.
En resumen, cuando varios hilos de ejecución intentan actualizar la misma variable simultáneamente usando CAS, uno gana y actualiza el valor de la variable y el resto pierde. Pero los perdedores no son sancionados con la suspensión del hilo, ellos son libres de volver a intentar realizar la operación o simplemente no hacer nada.[2]
La técnica CAS es optimista ya que procede con la actualización a la espera de tener éxito, sin embargo puede haber fallo, que será detectado, si otro hilo ha actualizado la variable desde que él la examinó por última vez.[2]
Ejemplo editar
Supongamos que V es una localización de memoria donde está almacenado el valor 10. Hay múltiples hilos que quieren incrementar este valor y usar el valor incrementado para otras operaciones. Supongamos los siguientes pasos:[2]
- Hilos 1 y 2 quieren realizar el incremento, leen el valor y deciden que quieren incrementarlo a 11.
- Hilo 1 entra primero en CAS y compara V con el último valor leído. Esto provocará que el valor de V sea sobreescrito y se convierta a 11
- Hilo 2 entra en CAS e intenta realizar la operación y esta falla devolviendo el valor 11
- Hilo 2 decide volver a leer y decide incrementar a 12
- Hilo 2 entra en CAS y actualiza el valor de la variable a 12.
Implementación hardware editar
La técnica CAS está soportada por las CPU's modernas. El acceso a estas rutinas de CPU ponen a disposición del sistema una implementación eficiente al más bajo nivel del algoritmo. Esto puede ser aprovechado por lenguajes de alto nivel. Por ejemplo Java desde versión 5 tiene acceso a estas funciones vía clases del paquete java.util.concurrent.atomic.[3]
Referencias editar
- ↑ Understanding Atomic Operations. jfdube. 30 de noviembre de 2011
- ↑ a b c d e Compare and Swap [CAS Algorithm]. Lokesh Gupta. 13 de junio de 2014
- ↑ Compare and Swap. Jakob Jenkov. 1 de octubre de 2014
Datos: Q128562
