En informática , comparar e intercambiar ( CAS ) es una instrucción atómica utilizada en subprocesos múltiples para lograr la sincronización . Compara el contenido de una ubicación de memoria con un valor dado y, solo si son iguales, modifica el contenido de esa ubicación de memoria a un nuevo valor dado. Esto se hace como una única operación atómica. La atomicidad garantiza que el nuevo valor se calcule en base a información actualizada; si mientras tanto otro hilo hubiera actualizado el valor, la escritura fallaría. El resultado de la operación deberá indicar si realizó la sustitución; Esto se puede hacer con una respuesta booleana simple (esta variante a menudo se llama comparar y establecer ), o devolviendo el valor leído de la ubicación de la memoria ( no el valor escrito en ella).
Una operación de comparación e intercambio es una versión atómica del siguiente pseudocódigo , donde * denota acceso a través de un puntero : [1]
función cas(p: puntero a int, antiguo: int, nuevo: int) es si *p ≠ antiguo devuelve falso *p ← nuevo devolver verdadero
Esta operación se utiliza para implementar primitivas de sincronización como semáforos y mutex , [1] así como algoritmos más sofisticados sin bloqueo y sin espera . Maurice Herlihy (1991) demostró que CAS puede implementar más de estos algoritmos que lectura, escritura o búsqueda y adición atómicas , y suponiendo una cantidad de memoria bastante grande [ se necesita aclaración ] , puede implementarlos todos. [2] CAS es equivalente a load-link/store-conditional , en el sentido de que se puede utilizar un número constante de invocaciones de cualquiera de las primitivas para implementar la otra sin esperas . [3]
Los algoritmos creados en torno a CAS normalmente leen alguna ubicación clave de la memoria y recuerdan el valor anterior. Con base en ese valor anterior, calculan algún valor nuevo. Luego intentan intercambiar el nuevo valor usando CAS, donde la comparación verifica que la ubicación siga siendo igual al valor anterior. Si CAS indica que el intento ha fallado, se debe repetir desde el principio: se vuelve a leer la ubicación, se vuelve a calcular un nuevo valor y se vuelve a intentar el CAS. En lugar de volver a intentarlo inmediatamente después de que falla una operación de CAS, los investigadores han descubierto que el rendimiento total del sistema se puede mejorar en sistemas multiprocesador (donde muchos subprocesos actualizan constantemente alguna variable compartida particular) si los subprocesos que ven que su CAS falla utilizan un retroceso exponencial (en otras palabras, esperan). un poco antes de volver a intentar el CAS. [4]
Como ejemplo de caso de uso de comparar e intercambiar, aquí hay un algoritmo para incrementar o disminuir atómicamente un número entero . Esto es útil en una variedad de aplicaciones que utilizan contadores. La función add realiza la acción *p ← *p + a , atómicamente (nuevamente denotando la dirección indirecta del puntero por * , como en C) y devuelve el valor final almacenado en el contador. A diferencia del pseudocódigo cas anterior, no existe ningún requisito de que ninguna secuencia de operaciones sea atómica excepto cas .
función agregar(p: puntero a int, a: int) devuelve int hecho ← falso mientras no haya terminado valor ← *p // Incluso esta operación no necesita ser atómica. hecho ← cas(p, valor, valor + a) valor de retorno + un
En este algoritmo, si el valor de *p cambia después (¡o mientras!) se recupera y antes de que CAS lo almacene, CAS notará e informará este hecho, lo que provocará que el algoritmo lo vuelva a intentar. [5]
Algunos algoritmos basados en CAS se ven afectados y deben manejar el problema de una coincidencia de falso positivo , o el problema ABA . Es posible que entre el momento en que se lee el valor anterior y el momento en que se intenta CAS, algunos otros procesadores o subprocesos cambien la ubicación de la memoria dos o más veces de modo que adquiera un patrón de bits que coincida con el valor anterior. El problema surge si este nuevo patrón de bits, que se ve exactamente igual al valor anterior, tiene un significado diferente: por ejemplo, podría ser una dirección reciclada o un contador de versión ajustado.
Una solución general a esto es utilizar un CAS de doble longitud (DCAS). Por ejemplo, en un sistema de 32 bits, se puede utilizar un CAS de 64 bits. La segunda mitad se utiliza para sostener un mostrador. La parte de comparación de la operación compara el valor leído previamente del puntero y el contador con el puntero y el contador actuales. Si coinciden, se produce el intercambio (se escribe el nuevo valor), pero el nuevo valor tiene un contador incrementado. Esto significa que si se ha producido ABA, aunque el valor del puntero será el mismo, es muy poco probable que el contador sea el mismo (para un valor de 32 bits, tendrían que haber ocurrido un múltiplo de 2 32 operaciones, lo que provocaría que el contador wrap y en ese momento, el valor del puntero también tendría que ser el mismo por casualidad).
Una forma alternativa de esto (útil en CPU que carecen de DCAS) es utilizar un índice en una lista libre, en lugar de un puntero completo; por ejemplo, con un CAS de 32 bits, utilice un índice de 16 bits y un contador de 16 bits. Sin embargo, la longitud reducida de los contadores comienza a hacer posible ABA a velocidades de CPU modernas.
Una técnica sencilla que ayuda a aliviar este problema es almacenar un contador ABA en cada elemento de la estructura de datos, en lugar de utilizar un único contador ABA para toda la estructura de datos.
Una solución más complicada pero más eficaz es implementar la recuperación de memoria segura (SMR). De hecho, esto es una recolección de basura sin bloqueo. La ventaja de utilizar SMR es la seguridad de que un puntero determinado existirá sólo una vez a la vez en la estructura de datos, por lo que el problema ABA está completamente resuelto. (Sin SMR, se utilizará algo así como una lista libre, para garantizar que se pueda acceder de forma segura a todos los elementos de datos (sin violaciones de acceso a la memoria) incluso cuando ya no estén presentes en la estructura de datos. Con SMR, solo los elementos actualmente en la lista se accederá a la estructura de datos).
A veces se piensa que CAS y otras instrucciones atómicas son innecesarias en sistemas monoprocesador, porque la atomicidad de cualquier secuencia de instrucciones se puede lograr desactivando las interrupciones mientras se ejecuta. Sin embargo, deshabilitar las interrupciones tiene numerosas desventajas. Por ejemplo, se debe confiar en que el código al que se le permite hacerlo no sea malicioso y monopolice la CPU, así como que sea correcto y no cuelgue accidentalmente la máquina en un bucle infinito o falla de página. Además, deshabilitar las interrupciones a menudo se considera demasiado costoso para ser práctico. Por lo tanto, incluso los programas destinados únicamente a ejecutarse en máquinas con un solo procesador se beneficiarán de las instrucciones atómicas, como en el caso de los futexes de Linux .
En sistemas multiprocesador, normalmente es imposible desactivar las interrupciones en todos los procesadores al mismo tiempo. Incluso si fuera posible, dos o más procesadores podrían estar intentando acceder a la memoria del mismo semáforo al mismo tiempo y, por tanto, no se lograría la atomicidad. La instrucción de comparar e intercambiar permite que cualquier procesador pruebe y modifique atómicamente una ubicación de memoria, evitando este tipo de colisiones entre múltiples procesadores.
En las arquitecturas multiprocesador de nivel de servidor de la década de 2010, comparar e intercambiar es barato en comparación con una carga simple que no se sirve desde la caché. Un artículo de 2013 señala que un CAS es sólo 1,15 veces más caro que una carga sin caché en Intel Xeon ( Westmere-EX ) y 1,35 veces en AMD Opteron (Magny-Cours). [6]
Comparar e intercambiar (y comparar e intercambiar doble) ha sido una parte integral de las arquitecturas IBM 370 (y todas las posteriores) desde 1970. Los sistemas operativos que se ejecutan en estas arquitecturas hacen un uso extensivo de esta instrucción para facilitar el proceso. (es decir, tareas del sistema y del usuario) y el paralelismo del procesador (es decir, procesadores centrales), eliminando al mismo tiempo, en la mayor medida posible, los " spinlocks deshabilitados " que se habían empleado en sistemas operativos anteriores de IBM. Del mismo modo, también se eliminó el uso de test-and-set . En estos sistemas operativos, se pueden crear instancias de nuevas unidades de trabajo "globalmente", en la lista de prioridades de servicios globales, o "localmente", en la lista de prioridades de servicios locales, mediante la ejecución de una única instrucción de comparación e intercambio. Esto mejoró sustancialmente la capacidad de respuesta de estos sistemas operativos.
En las arquitecturas x86 (desde 80486 ) e Itanium , esto se implementa como la instrucción de comparación e intercambio ( CMPXCHG ) (en un multiprocesador se debe usar el prefijo LOCK ).
A partir de 2013, la mayoría de las arquitecturas multiprocesador admiten CAS en hardware, y la operación de comparación e intercambio es la primitiva de sincronización más popular para implementar estructuras de datos concurrentes tanto basadas en bloqueo como sin bloqueo . [4]
Las operaciones de contador atómico y máscara de bits atómica en el kernel de Linux suelen utilizar una instrucción de comparación e intercambio en su implementación. Las arquitecturas SPARC-V8 y PA-RISC son dos de las pocas arquitecturas recientes que no admiten CAS en hardware; el puerto de Linux para estas arquitecturas utiliza un spinlock . [7]
Muchos compiladores de C admiten el uso de comparar e intercambiar, ya sea con las funciones C11 <stdatomic.h> , [8] o alguna extensión de C no estándar de ese compilador de C en particular, [9] o llamando a una función escrita directamente en lenguaje ensamblador usando el método comparar e intercambiar. -instrucciones de intercambio.
La siguiente función de C muestra el comportamiento básico de una variante de comparación e intercambio que devuelve el valor anterior de la ubicación de memoria especificada; sin embargo, esta versión no proporciona las garantías cruciales de atomicidad que ofrecería una operación real de comparación e intercambio:
int compare_and_swap ( int * reg , int oldval , int newval ) { ATOMIC (); int old_reg_val = * reg ; if ( old_reg_val == oldval ) * reg = newval ; END_ATOMIC (); devolver old_reg_val ; } old_reg_valsiempre se devuelve, pero se puede probar después de la compare_and_swapoperación para ver si coincide oldval, ya que puede ser diferente, lo que significa que otro proceso ha logrado tener éxito en una competencia compare_and_swappara cambiar el valor del registro de oldval.
Por ejemplo, se puede implementar un protocolo de elección de modo que cada proceso verifique el resultado compare_and_swapcon su propio PID (= newval). El proceso ganador encuentra que compare_and_swapdevuelve el valor inicial no PID (por ejemplo, cero). A los perdedores les devolverá el PID ganador.
Esta es la lógica del Manual de software Intel Vol 2A:
bool compare_and_swap ( int * accum , int * dest , int newval ) { if ( * accum == * dest ) { * dest = newval ; devolver verdadero ; } else { * acumulación = * destino ; falso retorno ; } } Dado que CAS opera en una única ubicación de memoria del tamaño de un puntero , mientras que la mayoría de los algoritmos sin bloqueo y sin espera necesitan modificar múltiples ubicaciones, se han implementado varias extensiones.
java.util.concurrent.atomicimplementa 'compareAndSet' en varias clases