Double compare-and-swap ( DCAS o CAS2 ) es una primitiva atómica propuesta para soportar ciertas técnicas de programación concurrentes . DCAS toma dos ubicaciones de memoria no necesariamente contiguas y escribe nuevos valores en ellas solo si coinciden con los valores "esperados" suministrados previamente; como tal, es una extensión de la operación mucho más popular de comparar e intercambiar (CAS).
A veces, DCAS se confunde con el sistema de comparación e intercambio de doble ancho ( DWCAS ) implementado por instrucciones como x86 CMPXCHG16B. DCAS, como se describe aquí, maneja dos ubicaciones de memoria no contiguas, generalmente del tamaño de un puntero, mientras que DWCAS maneja dos ubicaciones de memoria adyacentes del tamaño de un puntero.
En su tesis doctoral, Michael Greenwald recomendó agregar DCAS al hardware moderno, demostrando que podría usarse para crear una memoria transaccional de software (STM) fácil de aplicar pero eficiente . Greenwald señala que una ventaja de DCAS frente a CAS es que CAS n de orden superior (elemento múltiple) se puede implementar en O ( n ) con DCAS, pero requiere tiempo O ( n log p ) con CAS unario, donde p es el número de procesos contendientes. [1]
Una de las ventajas de DCAS es la capacidad de implementar deques atómicos (es decir, listas doblemente enlazadas ) con relativa facilidad. [2] Más recientemente, sin embargo, se ha demostrado que un STM se puede implementar con propiedades comparables [ aclaración necesaria ] utilizando sólo CAS. [3] En general, sin embargo, DCAS no es una bala de plata : la implementación de algoritmos sin bloqueo y sin espera usando normalmente es tan complejo y propenso a errores como para CAS. [4]
En un momento, Motorola incluyó DCAS en el conjunto de instrucciones para su serie 68k ; [5] sin embargo, la lentitud de DCAS en relación con otras primitivas (aparentemente debido a problemas de manejo de caché) llevó a evitarlo en contextos prácticos. [6] A partir de 2015 [actualizar], DCAS no es compatible de forma nativa con ninguna CPU generalizada en producción.
La generalización de DCAS a más de dos direcciones a veces se denomina MCAS (CAS de varias palabras); El MCAS puede implementarse mediante un LL / SC encajable , pero esta primitiva no está disponible directamente en el hardware. [3] MCAS se puede implementar en software en términos de DCAS, de varias formas. [7] En 2013, Trevor Brown, Faith Ellen y Eric Ruppert implementaron en software una extensión LL / SC de múltiples direcciones (a la que llaman LLX / SCX) que, si bien es más restrictiva que MCAS [8] , les permitió, a través de algunos generación automatizada de código, para implementar uno de los árboles de búsqueda binaria concurrente de mejor rendimiento (en realidad, un árbol cromático ), superando ligeramente la implementación de lista de omisión basada en JDK CAS . [9]
En general, DCAS puede proporcionarse mediante una memoria transaccional de hardware más expresiva . [10] IBM POWER8 e Intel Intel TSX proporcionan implementaciones funcionales de memoria transaccional. El procesador Rock cancelado de Sun también lo habría admitido.
Referencias
- ^ M. Greenwald. "Sincronización sin bloqueo y diseño de sistemas". Informe técnico de la Universidad de Stanford STAN-CS-TR-99-1624 [1] . (p. 10 en particular)
- ^ Ole Agesen, David L. Detlefs, Christine H. Flood, Alexander T. Garthwaite, Paul A. Martin, Mark Moir, Nir N. Shavit y Guy L. Steele Jr. "Deques concurrentes basados en DCAS". Teoría de los sistemas informáticos 35, no. 3 (2002): 349-386.
- ^ a b Keir Fraser (2004), "Práctica libertad de bloqueo" UCAM-CL-TR-579.pdf
- ^ 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 [2] .
- ^ CAS2
- ^ Greenwald, Michael y David Cheriton. "La sinergia entre la sincronización sin bloqueo y la estructura del sistema operativo". OSDI '96 Actas del segundo simposio de USENIX sobre diseño e implementación de sistemas operativos (1996): 123-136. (en particular la sección 7.1 "Implementación experimental")
- ^ Harris, Timothy L .; Fraser, Keir; Pratt, Ian A. (2002). Una operación práctica de comparación e intercambio de varias palabras . Proc. Int'l Symp. Computación distribuída. CiteSeerX 10.1.1.13.7938 .
- ^ Trevor Brown, Faith Ellen y Eric Ruppert. "Primitivas pragmáticas para estructuras de datos sin bloqueo". En Actas del simposio de ACM de 2013 sobre los principios de la computación distribuida, págs. 13-22. ACM, 2013.
- ^ Trevor Brown, Faith Ellen y Eric Ruppert. "Una técnica general para árboles sin bloqueo". En Actas del XIX simposio ACM SIGPLAN sobre Principios y práctica de la programación paralela, págs. 329-342. ACM, 2014.
- ^ 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.
enlaces externos
- Patente de EE. UU. 4584640 Método y aparato para una instrucción de comparación e intercambio
- Phuong Ha-Hoai ; Tsigas, Philippas . "Rápido, reactivo y sin bloqueo: algoritmos de comparación e intercambio de varias palabras". CiteSeerX 10.1.1.66.3324 . Cite journal requiere
|journal=
( ayuda )