En informática , compare-and-swap ( 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 función de información actualizada; si el valor hubiera sido actualizado por otro subproceso mientras tanto, la escritura fallaría. El resultado de la operación debe indicar si realizó la sustitución; esto se puede hacer con una respuesta booleana simple (esta variante a menudo se llama compare-and-set ), o devolviendo el valor leído de la ubicación de 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 devuelve verdadero
Esta operación se utiliza para implementar primitivas de sincronización como semáforos y mutexes , [1] así como algoritmos más sofisticados sin bloqueos y sin esperas . Maurice Herlihy (1991) demostró que CAS puede implementar más de estos algoritmos que lectura atómica , escritura o búsqueda y adición , y asumiendo una cantidad de memoria bastante grande [ aclaración necesaria ] , que puede implementarlos todos. [2] CAS es equivalente a load-link/store-conditional , en el sentido de que se puede usar un número constante de invocaciones de cualquiera de las primitivas para implementar la otra de manera sin esperas . [3]
Los algoritmos construidos en torno a CAS suelen leer una ubicación de memoria clave y recordar el valor anterior. Basándose en ese valor anterior, calculan un valor nuevo. A continuación, intentan intercambiar el nuevo valor mediante CAS, donde la comparación comprueba que la ubicación sigue siendo igual al valor anterior. Si CAS indica que el intento ha fallado, debe repetirse 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 una operación CAS falla, los investigadores han descubierto que el rendimiento total del sistema se puede mejorar en sistemas multiprocesador (donde muchos subprocesos actualizan constantemente alguna variable compartida en 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 comparación e intercambio, aquí hay un algoritmo para incrementar o decrementar atómicamente un entero . Esto es útil en una variedad de aplicaciones que usan contadores. La función add realiza la acción *p ← *p + a , atómicamente (nuevamente denotando la indirección del puntero por * , como en C) y devuelve el valor final almacenado en el contador. A diferencia del pseudocódigo cas anterior, no hay ningún requisito de que cualquier secuencia de operaciones sea atómica excepto cas .
función add(p: puntero a int, a: int) devuelve int hecho ← falso mientras no esté hecho valor ← *p // Incluso esta operación no necesita ser atómica. hecho ← cas(p, valor, valor + a) valor de retorno + a
En este algoritmo, si el valor de *p cambia después (o mientras) se obtiene y antes de que el CAS realice el almacenamiento, el CAS notará e informará este hecho, lo que hará que el algoritmo vuelva a intentarlo. [5]
Algunos algoritmos basados en CAS se ven afectados por el problema de una coincidencia de falso positivo o el problema ABA , y deben solucionarlo . Es posible que entre el momento en que se lee el valor anterior y el momento en que se intenta realizar CAS, 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 como el valor anterior, tiene un significado diferente: por ejemplo, podría ser una dirección reciclada o un contador de versión encapsulada.
Una solución general para esto es usar un CAS de doble longitud (DCAS). Por ejemplo, en un sistema de 32 bits, se puede usar un CAS de 64 bits. La segunda mitad se usa para almacenar un contador. 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 un ABA, aunque el valor del puntero será el mismo, es extremadamente improbable que el contador sea el mismo (para un valor de 32 bits, tendría que haber ocurrido un múltiplo de 2 32 operaciones, lo que haría que el contador se ajustara y, en ese momento, el valor del puntero también tendría que ser, por casualidad, el mismo).
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, las longitudes reducidas de los contadores comienzan a hacer posible el ABA a velocidades de CPU modernas.
Una técnica simple que ayuda a aliviar este problema es almacenar un contador ABA en cada elemento de la estructura de datos, en lugar de utilizar un solo contador ABA para toda la estructura de datos.
Una solución más complicada pero más efectiva es implementar la recuperación de memoria segura (SMR, por sus siglas en inglés). Esto es, en efecto, una recolección de basura sin bloqueos. La ventaja de usar SMR es la seguridad de que un puntero dado existirá solo una vez en cualquier momento en la estructura de datos, por lo que el problema de ABA se resuelve por completo. (Sin SMR, se utilizará algo así como una lista libre, para garantizar que se pueda acceder a todos los elementos de datos de forma segura (sin violaciones de acceso a memoria) incluso cuando ya no estén presentes en la estructura de datos. Con SMR, solo se accederá a los elementos que realmente se encuentran actualmente en la estructura de datos).
En ocasiones 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 deshabilitando 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 en que sea correcto y no cuelgue accidentalmente la máquina en un bucle infinito o en un fallo 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 solo a ejecutarse en máquinas monoprocesador se beneficiarán de las instrucciones atómicas, como en el caso de futexes de Linux .
En los 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 lo tanto no se lograría la atomicidad. La instrucción de comparación e intercambio permite que cualquier procesador pruebe y modifique atómicamente una ubicación de memoria, lo que evita este tipo de colisiones entre múltiples procesadores.
En las arquitecturas multiprocesador de nivel de servidor de la década de 2010, la comparación y el intercambio son económicos en comparación con una carga simple que no se sirve desde la memoria caché. Un artículo de 2013 señala que un CAS es solo 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]
La instrucción de comparación e intercambio (y de comparación e intercambio doble) ha sido parte integral de las arquitecturas IBM 370 (y todas las posteriores) desde 1970. Los sistemas operativos que funcionan en estas arquitecturas hacen un uso extensivo de esta instrucción para facilitar el paralelismo de procesos (es decir, tareas del sistema y del usuario) y procesadores (es decir, procesadores centrales), al tiempo que eliminan, en la mayor medida posible, los " bloqueos de giro deshabilitados " que se habían empleado en los sistemas operativos IBM anteriores. De manera similar, también se eliminó el uso de prueba y configuración . En estos sistemas operativos, las nuevas unidades de trabajo pueden instanciarse "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 instrucción de comparación e intercambio ( CMPXCHG ) (en un multiprocesador se debe utilizar 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 basadas en bloqueos y no bloqueantes . [4]
Las operaciones de contador atómico y máscara de bits atómica en el núcleo 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; la adaptación de Linux a estas arquitecturas utiliza un spinlock . [7]
Muchos compiladores de C admiten el uso de comparación e intercambio ya sea con las funciones C11 <stdatomic.h> , [8] o alguna extensión C no estándar de ese compilador C en particular, [9] o llamando a una función escrita directamente en lenguaje ensamblador utilizando la instrucción de comparación e intercambio.
La siguiente función C muestra el comportamiento básico de una variante de comparación e intercambio que devuelve el valor antiguo 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 de comparación e intercambio real:
int comparar_e_intercambiar ( int * reg , int valor_antiguo , int valor_nuevo ) { ATÓMICO (); int valor_registro_antiguo = * reg ; si ( valor_registro_antiguo == valor_antiguo ) * reg = valor_nuevo ; FIN_ATÓMICO (); devolver valor_registro_antiguo ; } 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 de compare_and_swapcontra su propio PID (= newval). El proceso ganador encuentra compare_and_swapel valor inicial que no es PID (por ejemplo, cero). Para los perdedores, devolverá el PID ganador.
Esta es la lógica en el Manual de software Intel Vol 2A:
bool compare_and_swap ( int * accum , int * dest , int newval ) { if ( * accum == * dest ) { * dest = newval ; devolver verdadero ; } else { * acum = * destino ; devolver falso ; } } 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