En informática , la carga vinculada / condicional de almacenamiento [1] ( LL / SC ), a veces conocida como carga reservada / condicional de almacenamiento [2] ( LR / SC ), son un par de instrucciones que se utilizan en subprocesos múltiples para lograr la sincronización . Load-link devuelve el valor actual de una ubicación de memoria, mientras que un almacén condicional posterior a la misma ubicación de memoria almacenará un nuevo valor solo si no se han producido actualizaciones en esa ubicación desde el load-link. Juntos, esto implementa una operación de lectura-modificación-escritura atómica sin bloqueos .
" Enlace de carga " también se conoce como enlace de carga , [ cita requerida ] reservada de carga , [2] y bloqueada por carga . [ cita requerida ]
LL / SC fue originalmente [ citación necesaria ] propuesto por Jensen, Hågensen, y Broughton para el S-1 AAP multiprocesador [1] en el Laboratorio Nacional Lawrence Livermore .
Comparación de LL / SC y compare-and-swap
Si se ha producido alguna actualización, se garantiza que el condicional de almacenamiento fallará, incluso si el valor leído por el enlace de carga se ha restaurado desde entonces. Como tal, un par LL / SC es más fuerte que una lectura seguida de una comparación e intercambio (CAS), que no detectará actualizaciones si se ha restaurado el valor anterior (consulte el problema ABA ).
Las implementaciones reales de LL / SC no siempre tienen éxito incluso si no hay actualizaciones simultáneas en la ubicación de la memoria en cuestión. Cualquier evento excepcional entre las dos operaciones, como un cambio de contexto , otro enlace de carga o incluso (en muchas plataformas) otra operación de carga o almacenamiento, hará que el condicional de almacenamiento falle de forma espuria. Implementaciones más grandes les fallan si hay alguna actualización de difusión a través del bus de memoria. Esto es llamado LL / SC débil por los investigadores, ya que rompe muchos algoritmos teóricos de LL / SC. [3] La debilidad es relativa y algunas implementaciones débiles se pueden utilizar para algunos algoritmos.
LL / SC es más difícil de emular que CAS. Además, detener la ejecución de código entre instrucciones LL / SC emparejadas, como cuando se avanza en un solo paso a través del código, puede evitar el progreso hacia adelante, lo que dificulta la depuración. [4]
Sin embargo, LL / SC es equivalente a CAS en el sentido de que cualquiera de las primitivas puede implementarse en términos de la otra, en O (1) y sin esperar . [5]
Implementaciones
Las instrucciones LL / SC son compatibles con:
- Alfa : ldl_l / stl_c y ldq_l / stq_c
- PowerPC / Power ISA : lwarx / stwcx y ldarx / stdcx
- MIPS : ll / sc
- ARM : ldrex / strex (ARMv6 y v7) y ldxr / stxr (ARM versión 8)
- RISC-V : lr / sc [2]
- ARCO : LLOCK / SCOND
Algunas CPU [ ¿cuáles? ] requieren que la dirección a la que se accede exclusivamente se configure en modo de escritura directa.
Por lo general, las CPU rastrean la dirección vinculada a la carga en una línea de caché u otra granularidad, de modo que cualquier modificación en cualquier parte de la línea de caché (ya sea a través de la tienda condicional de otro núcleo o simplemente por una tienda ordinaria) es suficiente para hacer que la tienda -condicional a fallar.
Todas estas plataformas proporcionan LL / SC débil [ aclaración necesaria ] . La implementación de PowerPC permite que un par LL / SC envuelva cargas e incluso almacene en otras líneas de caché (aunque este enfoque es vulnerable a compartir líneas de caché falsas). Esto le permite implementar, por ejemplo, el recuento de referencias sin bloqueos frente a gráficos de objetos cambiantes con reutilización arbitraria del contador (que de lo contrario requiere doble comparación e intercambio , DCAS). RISC-V proporciona una garantía arquitectónica de progreso eventual para secuencias LL / SC de longitud limitada.
Algunas implementaciones ARM definen bloques dependientes de la plataforma, que van desde 8 bytes hasta 2048 bytes, y un intento de LL / SC en cualquier bloque dado falla si hay entre LL y SC un acceso normal a la memoria dentro del mismo bloque. Otras implementaciones de ARM fallan si hay una modificación en cualquier parte de todo el espacio de direcciones. La primera implementación es la más sólida y práctica.
LL / SC tiene dos ventajas sobre CAS al diseñar una arquitectura de almacenamiento de carga : las lecturas y escrituras son instrucciones separadas, como lo requiere la filosofía de diseño (y la arquitectura de canalización ); y ambas instrucciones se pueden ejecutar utilizando sólo dos registros (dirección y valor), encajando naturalmente en ISA de 2 operandos comunes . CAS, por otro lado, requiere tres registros (dirección, valor antiguo, valor nuevo) y una dependencia entre el valor leído y el valor escrito. x86 , al ser una arquitectura CISC , no tiene esta restricción; aunque los chips modernos bien pueden traducir una instrucción CAS en microoperaciones LL / SC separadas internamente.
Extensiones
Las implementaciones de hardware LL / SC normalmente no permiten el anidamiento de pares LL / SC. [6] Se puede utilizar un mecanismo LL / SC anidado para proporcionar una primitiva MCAS (CAS de varias palabras, donde las palabras se pueden dispersar). [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 se basa en la generación de código automatizada; [8] lo han utilizado 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 la lista de omisión basada en JDK CAS . [9]
Ver también
- Sincronización sin bloqueo
- Memoria transaccional
Referencias
- ^ a b "Proyecto S-1" . Wiki de Ciencias de la Computación de Stanford . 2018-11-30.
- ^ a b c Andrew Waterman; Krste Asanović, eds. (7 de mayo de 2017). "7.2 Instrucciones de carga reservada / condicional de almacenamiento". Manual del conjunto de instrucciones de RISC-V, volumen 1: ISA a nivel de usuario, versión 2.2 (PDF) .
- ^ Beckmann, Nathan. "Sincronización" (PDF) . 15-740: Arquitectura informática, otoño de 2018 . Universidad Carnegie Mellon . Consultado el 23 de abril de 2021 .
- ^ Keno Fischer (2 de mayo de 2020). "Vista previa de la función de Julia 1.5: informe de errores de viaje en el tiempo (Linux)" . Consultado el 14 de mayo de 2020 .
- ^ James H. Anderson; Mark Moir (1995). "Construcciones universales para operaciones con múltiples objetos". PODC '95 Actas del decimocuarto simposio anual de ACM sobre principios de computación distribuida . ACM. págs. 184-193. doi : 10.1145 / 224964.224985 . ISBN 0-89791-710-3. Vea su Tabla 1, Figuras 1 y 2 y la Sección 2 en particular.
- ^ James R. Larus; Ravi Rajwar (2007). Memoria transaccional . Morgan y Claypool. pag. 55. ISBN 978-1-59829-124-7.
- ^ Keir Fraser (febrero de 2004). Práctica cerradura-libertad (PDF) (Informe técnico). Laboratorio de Computación de la Universidad de Cambridge. pag. 20. UCAM-CL-TR-579.
- ^ Brown, Trevor; Ellen, Faith; Ruppert, Eric (2013). "Primitivas pragmáticas para estructuras de datos sin bloqueo" (PDF) . PODC '13 Actas del simposio ACM de 2013 sobre principios de computación distribuida . ACM. págs. 13-22. doi : 10.1145 / 2484239.2484273 . ISBN 978-1-4503-2065-8.Ver también diapositivas
- ^ Trevor Brown; Faith Ellen; Eric Ruppert (2014). "Una técnica general para árboles sin bloqueo" (PDF) . Simposio PPoPP '14 ACM SIGPLAN sobre Principios y Práctica de la Programación Paralela . ACM. págs. 329–342. doi : 10.1145 / 2555243.2555267 . ISBN 978-1-4503-2656-8.
- Jensen, Eric H .; Hagensen, Gary W .; Broughton, Jeffrey M. (noviembre de 1987). Un nuevo enfoque para el acceso exclusivo a datos en multiprocesadores de memoria compartida (PDF) (Informe técnico). Laboratorio Nacional Lawrence Livermore. UCRL-97663. Archivado desde el original (PDF) el 02/02/2017 . Consultado el 22 de febrero de 2012 .
- Bruner, John D .; Hagensen, Gary W .; Jensen, Eric H .; Pattin, Jay C .; Broughton, Jeffrey M. (11 de noviembre de 1987). Coherencia de caché en el AAP S-1 (PDF) (Informe técnico). Laboratorio Nacional Lawrence Livermore. UCRL-97646. Archivado desde el original (PDF) el 2 de febrero de 2017 . Consultado el 10 de noviembre de 2013 .
- Detlefs, D .; Martin, P .; Moir, M .; Steele, Jr., Guy L. (2001). "Contaje de referencias sin bloqueo". PODC '01 Actas del vigésimo simposio anual de ACM sobre principios de computación distribuida . ACM. págs. 190–9. CiteSeerX 10.1.1.92.8221 . doi : 10.1145 / 383962.384016 . ISBN 1-58113-383-9.
- Reinholtz, Kirk (diciembre de 2004). "Punteros de conteo de referencia atómica" . Diario de usuarios de C / C ++ .
- Sites, RL (febrero de 1993). "Arquitectura Alpha AXP". Comm. ACM . 36 (2): 33–44. doi : 10.1145 / 151220.151226 .