La consistencia de la versión es uno de los modelos de consistencia basados en sincronización que se utilizan en la programación concurrente (por ejemplo, en memoria compartida distribuida , transacciones distribuidas, etc.).
Introducción [1]
En los sistemas de computación paralela modernos, se debe mantener la consistencia de la memoria para evitar resultados indeseables. Los modelos de consistencia estricta como la consistencia secuencial se componen intuitivamente, pero pueden ser bastante restrictivos en términos de rendimiento, ya que deshabilitarían el paralelismo a nivel de instrucción, que se aplica ampliamente en la programación secuencial. Para lograr un mejor rendimiento, se exploran algunos modelos relajados y la consistencia de liberación es un intento de relajación agresivo.
Lanzamiento de consistencia frente a consistencia secuencial
Estructura de hardware y esfuerzo a nivel de programa
La coherencia secuencial se puede lograr simplemente mediante la implementación del hardware, mientras que la coherencia de la versión también se basa en la observación de que la mayoría de los programas paralelos están sincronizados correctamente. En el nivel de programación, la sincronización se aplica para programar claramente un cierto acceso a la memoria en un hilo para que ocurra después de otro. Cuando se accede a una variable sincronizada, el hardware se asegura de que todas las escrituras locales en un procesador se hayan propagado a todos los demás procesadores y que todas las escrituras de otros procesadores se vean y recopilen. En el modelo de consistencia de liberación, la acción de entrar y salir de una sección crítica se clasifica como adquirir y liberar y, en cualquier caso, se debe colocar un código explícito en el programa que muestre cuándo realizar estas operaciones .
Condiciones para un resultado coherente secuencial
En general, una memoria compartida distribuida es coherente con el lanzamiento si obedece las siguientes reglas: [2]
1. Antes de que se realice un acceso a una variable compartida, todas las adquisiciones anteriores de este procesador deben haberse completado.
2. Antes de realizar una liberación, todas las lecturas y escrituras anteriores de este proceso deben haberse completado.
3. Los accesos de adquisición y liberación deben ser coherentes con el procesador .
Si se cumplen las condiciones anteriores y el programa está correctamente sincronizado (es decir, los procesadores implementan la adquisición y la liberación correctamente), los resultados de cualquier ejecución serán exactamente los mismos que se habrían ejecutado siguiendo la coherencia secuencial. En efecto, los accesos a las variables compartidas se separan en bloques de operaciones atómicas mediante las primitivas de adquisición y liberación, de modo que se evitarán las carreras y el entrelazado entre bloques.
Implementaciones [3]
Desbloqueo de bloqueo
Un abrepuertas se puede considerar como un tipo de sincronización de liberación. Suponga que se realiza una operación de bucle utilizando el código que se muestra a la derecha. Dos subprocesos tienen la intención de ingresar a una sección crítica y leer el valor más reciente de a , luego salir de la sección crítica. El código muestra que el hilo 0 primero adquiere el bloqueo y entra en la sección crítica. Para ejecutarse correctamente, P1 debe leer el último valor de un escrito por P0. En ese caso, solo un hilo puede estar en la sección crítica a la vez. Por lo tanto, la sincronización en sí misma ha asegurado que la adquisición exitosa del bloqueo en P1 ocurra después de la liberación del bloqueo por P0. Además, se debe garantizar la ordenación S2 -> S3, ya que P0 debe propagar el nuevo valor de a a P1. Por la misma razón, S5 debe ocurrir después de S4.
Es evidente que la corrección no se ve afectada si la memoria accede después del problema de desbloqueo antes de que se complete el desbloqueo o si accede a la memoria antes de un problema de bloqueo después de la adquisición del bloqueo. Sin embargo, el código de la sección crítica no se puede emitir antes de que se complete la adquisición del bloqueo porque es posible que no se garantice la exclusión mutua.
Post-espera
La sincronización posterior a la espera es otra forma de implementación de consistencia de lanzamiento. Como se muestra en el código de la derecha, se puede garantizar la corrección si las operaciones posteriores ocurren solo después de que se completa el acceso a la memoria, especialmente el almacenamiento en 'a'. Aparte de eso, la operación de lectura no debe ejecutarse hasta que se haya completado la operación de espera. S2 actúa como sincronización de liberación y S3 actúa como sincronización de adquisición. Por lo tanto, S2 debe evitar que se produzca una ejecución anterior después de él, y S3 debe evitar que se produzca una ejecución posterior antes. S2 no necesita evitar que ocurra una ejecución posterior antes que él. Asimismo, S3 no necesita evitar que ocurra ninguna ejecución previa después de él.
Consistencia de liberación lenta [4]
La consistencia de liberación diferida es una optimización adicional de la consistencia de liberación. Se asume que el subproceso que ejecuta un acceso de adquisición no necesita los valores escritos por otros subprocesos hasta que se haya completado el acceso de adquisición. Por lo tanto, todo el comportamiento de la coherencia se puede retrasar y se puede ajustar el tiempo para la propagación de escritura.
Ejemplo
Considere los escenarios descritos en la imagen de la derecha. Este caso muestra cuando la propagación de escritura se realiza en un sistema coherente de caché basado en el modelo de consistencia de lanzamiento. El datum variable se propaga completamente antes de la propagación de datumIsReady. Pero el valor de datum no es necesario hasta después de adquirir el acceso de sincronización en P1 y se puede propagar junto con datumIsReady sin dañar el resultado del programa.
La segunda imagen muestra cuál es el caso cuando se aplica la consistencia de liberación diferida. Teniendo en cuenta este escenario, todos los valores escritos antes de la sincronización de la versión se retrasan y se propagan junto con la propagación del acceso de la versión en sí. Por lo tanto, datum y datumIsReady se propagan juntos en el punto de publicación.
"TreadMarks" [5] es una aplicación real de consistencia de liberación diferida.
Mejora del rendimiento sobre la consistencia de la liberación
La consistencia de liberación diferida puede superar la consistencia de liberación en ciertos casos. Si hay un sistema con poco ancho de banda entre procesadores o sufre mucho por los gastos generales más altos debido a la propagación frecuente de bloques pequeños de datos frente a la propagación infrecuente de bloques de datos grandes, LRC realmente puede ayudar al rendimiento.
Considere un sistema que emplea una abstracción de memoria compartida a nivel de software en lugar de una implementación de hardware real. En este sistema, la propagación de escritura se ejecuta en una granularidad de página, lo que hace que sea extremadamente costoso propagar una página completa cuando solo se modifica un bloque en esta página. Por lo tanto, la propagación de la escritura se retrasa hasta que se alcanza un punto de sincronización de la versión y la página completa se modificará en este momento y se propagará toda la página.
Retirarse
LRC requiere realizar la propagación de escritura a granel en el punto de liberación de la sincronización. La propagación de un número tan grande de escrituras en conjunto ralentizará el acceso a la versión y el acceso de adquisición posterior. Por lo tanto, difícilmente puede mejorar el rendimiento de un sistema de coherencia de caché de hardware.
Lanzamiento de consistencia frente a otros modelos de consistencia relajada [6]
Orden débil ( consistencia débil )
La consistencia de la versión requiere más de los programadores en comparación con un pedido débil. Deben etiquetar los accesos de sincronización como adquisiciones o lanzamientos, no solo como accesos de sincronización. De manera similar a la ordenación débil, la consistencia de la versión permite al compilador reordenar libremente las cargas y las tiendas, excepto que no pueden migrar hacia arriba más allá de una sincronización de adquisición y no pueden migrar hacia abajo después de una sincronización de versión. Sin embargo, la ventaja de flexibilidad y rendimiento de la consistencia de la versión se produce a expensas de requerir que los accesos de sincronización se identifiquen e identifiquen correctamente como adquisiciones y versiones. A diferencia de la ordenación débil, los accesos de sincronización no se pueden identificar fácilmente mediante códigos de operación de instrucción únicamente. Por lo tanto, la carga recae sobre los hombros de los programadores para identificar correctamente los accesos de sincronización de adquisición y liberación. [3]
Consistencia del procesador
Para la coherencia del procesador, todos los procesos ven las escrituras de cada procesador en el orden en que se iniciaron. Es posible que las escrituras de diferentes procesadores no se vean en el mismo orden, excepto que las escrituras en la misma ubicación se verán en el mismo orden en todas partes. En comparación con la consistencia del procesador, la consistencia de la versión es más relajada porque no impone el orden entre tiendas que ocurre en la consistencia del procesador. No sigue la intuición de los programadores, ya que es relativamente menos restrictivo para las optimizaciones del compilador.
Ver también
Referencias
- ^ Consistencia de memoria y ordenamiento de eventos en multiprocesadores escalables de memoria compartida por Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta y John Hennessy publicado en ISCA '90 Proceedings of the 17th international international symposium on Computer Architecture
- ^ Tanenbaum, Andrew (1995). Sistemas operativos distribuidos . Educación Pearson. págs. 327–330. ISBN 9788177581799.
- ^ a b Solihin, Yan (2015). Fundamentos de la arquitectura multinúcleo paralela . Chapman & Hall / CRC Computational Science. págs. 315–320. ISBN 9781482211184.
- ^ Consistencia de liberación diferida para memoria compartida distribuida por software por Pete Keleher, Alan L. Cox y Willy Zwaenepoel publicado en Proceeding ISCA '92 Proceedings of the 19th anual international international symposium on Computer architecture
- ^ TreadMarks: memoria compartida distribuida en estaciones de trabajo estándar y sistemas operativos por Pete Keleher, Alan L. Cox, Sandhya Dwarkadas y Willy Zwaenepoel publicado en WTEC'94 Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference
- ^ Culler, David; Gupta, Anoop; Singh, Jaswinder (1997). Arquitectura informática paralela: un enfoque de hardware / software . Morgan Kaufmann Publishers Inc. págs. 620–626. ISBN 1558603433.