En ciencias de la computación , compare-and-swap ( CAS ) es una instrucción atómica que se usa en multiproceso 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 realiza como una sola operación atómica. La atomicidad garantiza que el nuevo valor se calcule con base en información actualizada; si el valor hubiera sido actualizado por otro hilo mientras tanto, la escritura fallaría. El resultado de la operación debe indicar si realizó la sustitución; esto se puede hacer con un simple booleanorespuesta (esta variante a menudo se llama comparar y establecer ), o devolviendo el valor leído desde la ubicación de la memoria ( no el valor escrito en ella).
Descripción general
Una operación de comparar e intercambiar 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 volver 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 los de lectura, escritura o búsqueda y adición atómica , y asumiendo una cantidad de memoria bastante grande [se necesita aclaración ] , 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 sin esperar . [3]
Los algoritmos construidos alrededor de CAS generalmente leen alguna ubicación de memoria clave y recuerdan el valor anterior. Con base en ese valor anterior, calculan un 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, 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 falla una operación de CAS, los investigadores han descubierto que el rendimiento total del sistema se puede mejorar en los sistemas multiprocesador, donde muchos subprocesos actualizan constantemente alguna variable compartida en particular, si los subprocesos que ven su CAS fallar utilizan un retroceso exponencial, en otras palabras, espere un poco antes de volver a intentar el CAS. [4]
Aplicación de ejemplo: sumador atómico
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 usan contadores. La función agregar realiza la acción * p ← * p + a , atómicamente (de nuevo denotando direccionamiento indirecto del puntero por * , como en C) y devuelve el valor final almacenado en el contador. A diferencia del cas pseudocódigo anterior, no hay ningún requisito de que cualquier secuencia de operaciones sea atómica excepto para cas .
función add (p: puntero a int, a: int) devuelve int hecho ← falso mientras no esté hecho value ← * 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 recupera y antes de que CAS lo almacene, CAS notará e informará este hecho, lo que hará que el algoritmo vuelva a intentarlo. [5]
Problema de ABA
Algunos algoritmos basados en CAS se ven afectados y deben manejar el problema de una coincidencia de falso positivo o el problema de 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 como el valor anterior, tiene un significado diferente: por ejemplo, podría ser una dirección reciclada o un contador de versiones envuelto.
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 usa para sostener 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 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ía 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 usar un índice en una lista libre, en lugar de un puntero completo, por ejemplo, con un CAS de 32 bits, use un índice de 16 bits y un contador de 16 bits. Sin embargo, las longitudes de contador reducidas comienzan a hacer posible 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 eficaz es implementar la recuperación de memoria segura (SMR). De hecho, se trata de una recolección de basura sin bloqueo. La ventaja de usar SMR es la garantía de que un puntero determinado existirá solo una vez en cualquier momento en la estructura de datos, por lo que el problema de ABA está completamente resuelto. (Sin SMR, se utilizará algo parecido a una lista gratuita para garantizar que se pueda acceder a todos los elementos de datos de forma segura (sin infracciones de acceso a la memoria) incluso cuando ya no estén presentes en la estructura de datos. Con SMR, solo los elementos que se encuentran actualmente en el se accederá a la estructura de datos).
Costos y beneficios
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, desactivar las interrupciones tiene numerosos inconvenientes. Por ejemplo, se debe confiar en que el código que tiene permiso para 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, la desactivación de interrupciones a menudo se considera demasiado cara para ser práctica. Por lo tanto, incluso los programas destinados a ejecutarse en máquinas monoprocesador se beneficiarán de las instrucciones atómicas, como en el caso de los futexes de Linux .
En los sistemas multiprocesador, generalmente es imposible deshabilitar 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 comparar e intercambiar permite que cualquier procesador pruebe y modifique atómicamente una ubicación de memoria, evitando tales colisiones de múltiples procesadores.
En las arquitecturas multiprocesador de nivel de servidor de la década de 2010, la comparación e intercambio es barata en comparación con una carga simple que no se proporciona desde la caché. Un artículo de 2013 señala que un CAS es solo 1,15 veces más caro que una carga no almacenada en caché en Intel Xeon ( Westmere-EX ) y 1,35 veces en AMD Opteron (Magny-Cours). [6]
Implementaciones
Compare-and-swap (y compare-and-swap-double) ha sido una parte integral de las arquitecturas IBM 370 (y todas las sucesoras) 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, el sistema y las tareas del usuario) y el procesador (es decir, los procesadores centrales) paralelismo mientras que la eliminación, en el mayor grado posible, los "discapacitados bloqueos de giro ", que habían sido empleados en anteriores sistemas operativos de IBM. Del mismo modo, también se eliminó el uso de test-and-set . En estos sistemas operativos, las nuevas unidades de trabajo se pueden instanciar "globalmente", en la lista de prioridad de servicio global, o "localmente", en la lista de prioridad de servicio local, mediante la ejecución de una única instrucción de comparar e intercambiar. 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 el Se debe utilizar el prefijo LOCK ).
A partir de 2013, la mayoría de las arquitecturas de 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 bloqueos como sin bloqueo . [4]
Las operaciones de contador atómico y de 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 usa un spinlock . [7]
Implementación en C
Muchos compiladores de C admiten el uso de comparar e intercambiar, ya sea con las funciones de C11
, [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 la función comparar y -instrucción de intercambio.
La siguiente función C muestra el comportamiento básico de una variante de comparar e intercambiar 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 una operación real de comparar e intercambiar:
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 (); return old_reg_val ; }
old_reg_val
siempre se devuelve, pero se puede probar después de la compare_and_swap
operació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_swap
para cambiar el valor de reg oldval
.
Por ejemplo, se puede implementar un protocolo de elección de modo que cada proceso verifique el resultado de compare_and_swap
con su propio PID (= newval). El proceso ganador encuentra la compare_and_swap
devolución del valor inicial que no es PID (por ejemplo, cero). Para los perdedores, devolverá el PID ganador.
bool compare_and_swap ( int * acumula , int * dest , int newval ) { if ( * acumula == * dest ) { * dest = newval ; devuelve verdadero ; } más { * acum = * dest ; devolver falso ; } }
Esta es la lógica en el Manual de software Intel Vol 2A.
Extensiones
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.
- Doble comparación e intercambio (DCAS)
- Compara dos ubicaciones de memoria no relacionadas con dos valores esperados y, si son iguales, establece ambas ubicaciones en nuevos valores. La generalización de DCAS a varias palabras (no adyacentes) se denomina MCAS o CASN. DCAS y MCAS son de interés práctico en la implementación conveniente (concurrente) de algunas estructuras de datos como dequeues o árboles de búsqueda binaria . [10] [11] DCAS y MCAS pueden implementarse sin embargo utilizando la memoria transaccional de hardware más expresiva [12] presente en algunos procesadores recientes como IBM POWER8 o en procesadores Intel que soportan Transactional Synchronization Extensions (TSX).
- Comparación e intercambio de doble ancho
- Opera en dos ubicaciones adyacentes del tamaño de un puntero (o, de manera equivalente, una ubicación dos veces más grande que un puntero). En procesadores x86 posteriores, las instrucciones CMPXCHG8B y CMPXCHG16B [13] cumplen esta función, aunque las primeras CPU AMD de 64 bits no admitían CMPXCHG16B (las CPU AMD modernas sí lo hacen). Algunas placas base Intel de la era Core 2 también dificultan su uso, a pesar de que los procesadores lo admiten. Estos problemas se destacaron en el lanzamiento de Windows 8.1 porque requería soporte de hardware para CMPXCHG16B. [14]
- Comparación simple, intercambio doble
- Compara un puntero pero escribe dos. La instrucción cmp8xchg16 de Itanium implementa esto, [15] donde los dos punteros escritos son adyacentes.
- Comparar e intercambiar palabras múltiples
- Es una generalización de la comparación e intercambio normales. Puede usarse para intercambiar atómicamente un número arbitrario de ubicaciones de memoria ubicadas arbitrariamente. Por lo general, la comparación e intercambio de varias palabras se implementa en el software mediante operaciones normales de comparación e intercambio de doble ancho. [16] El inconveniente de este enfoque es la falta de escalabilidad.
Ver también
- Colocación y eliminación condicional
- Buscar y agregar
- Enlace de carga / condicional de tienda
- Sincronización sin bloqueo
- Probar y configurar
- Memoria transaccional
Referencias
- ^ a b Mullender, Sape; Cox, Russ (2008). Semáforos en el Plan 9 (PDF) . 3er Taller Internacional del Plan 9 .
- ^ Herlihy, Maurice (enero de 1991). "Sincronización sin espera" (PDF) . ACM Trans. Programa. Lang. Syst . 13 (1): 124-149. CiteSeerX 10.1.1.56.5659 . doi : 10.1145 / 114005.102808 . Consultado el 20 de mayo de 2007 .
- ^ JH Anderson y M. Moir. "Construcciones universales para operaciones con múltiples objetos". En Proc. 14º Simposio Anual de ACM sobre Principios de Computación Distribuida , páginas 184-193, 1995. Vea su Tabla 1, Figuras 1 y 2 y la Sección 2 en particular.
- ^ a b Dice, Dave; Hendler, Danny; Mirsky, Ilya (2013). "Gestión de contención ligera para operaciones eficientes de comparación e intercambio". arXiv : 1305,5800 [ cs.DC ].
- ^ Goetz, Brian (23 de noviembre de 2004). "Teoría y práctica de Java: ir atómico" . IBM developerWorks .
- ^ Tudor David, Rachid Guerraoui y Vasileios Trigonakis. "Todo lo que siempre quiso saber sobre la sincronización pero tenía miedo de preguntar". Actas del vigésimo cuarto simposio de ACM sobre principios de sistemas operativos . ACM, 2013, págs. 33-48. Detalle en la p. 34
- ^ David S. Miller. "Semántica y comportamiento de las operaciones atómicas y de máscara de bits, para mantenedores de puertos de Linux" Archivado el 20 de marzo de 2012 en Wayback Machine .
- ^ http://en.cppreference.com/w/c/atomic/atomic_compare_exchange
- ^ "Extensiones GNU C para la familia de lenguajes C: funciones integradas para el acceso a la memoria atómica"
- ^ Simon Doherty et al., " DCAS no es una fórmula mágica para el diseño de algoritmos sin bloqueo ". 16º simposio anual de ACM sobre paralelismo en algoritmos y arquitecturas, 2004, págs. 216–224. doi : 10.1145 / 1007912.1007945
- ^ Keir Fraser (2004), "Práctica libertad de bloqueo" UCAM-CL-TR-579.pdf
- ^ Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum y Marek Olszewski. (2009) "Experiencia inicial con una implementación de memoria transaccional de hardware comercial". Informe técnico de Sun Microsystems (60 págs.) SMLI TR-2009-180. Una versión corta apareció en ASPLOS'09 doi : 10.1145 / 1508244.1508263 . El informe completo analiza cómo implementar DCAS utilizando HTM en la sección 5.
- ^ "Manual del desarrollador de software de arquitecturas Intel 64 e IA-32, volumen 2A: referencia del conjunto de instrucciones, AM" (PDF) . Consultado el 15 de diciembre de 2007 .
- ^ http://www.pcworld.com/article/2058683/new-windows-8-1-requirements-strand-some-users-on-windows-8.html
- ^ "Manual del desarrollador de software de la arquitectura Intel Itanium Volumen 3: referencia del conjunto de instrucciones" (PDF) . Consultado el 15 de diciembre de 2007 .
- ^ "Una operación práctica de comparación e intercambio de varias palabras" (PDF) . Consultado el 8 de agosto de 2009 .
enlaces externos
Algoritmos básicos implementados usando CAS
- Sundell, Håkan; Tsigas, Philippas. "Deques prácticos y sin bloqueos mediante la comparación e intercambio de una sola palabra" (PDF) . Cite journal requiere
|journal=
( ayuda ) - Valois, John D. "Listas enlazadas sin bloqueo mediante comparar e intercambiar". CiteSeerX 10.1.1.41.9506 . Cite journal requiere
|journal=
( ayuda ) - Prakash, S .; Lee, Yann Hang; Johnson, T. "Un algoritmo sin bloqueo para colas compartidas que utilizan Comparar e intercambiar" . Cite journal requiere
|journal=
( ayuda ) - Discusión de 2003 " Lock-Free using cmpxchg8b ... " en Intel x86 con referencias a varios documentos y código fuente
Implementaciones de CAS
- Servicio de kernel compare_and_swap de AIX
- El paquete Java
java.util.concurrent.atomic
implementa `compareAndSet` en varias clases - Métodos de clase .NET interbloqueados :: CompareExchange
- API de Windows interbloqueadaCompareExchange