Modelo de consistencia

En informática, un modelo de consistencia especifica un contrato entre el programador y un sistema, en el que el sistema garantiza que si el programador sigue las reglas para las operaciones en la memoria, la memoria será consistente y los resultados de lectura, escritura o actualización de la memoria será predecible. Los modelos de consistencia se utilizan en sistemas distribuidos como sistemas de memoria compartida distribuida o almacenes de datos distribuidos (como sistemas de archivos, bases de datos, sistemas de replicación optimista o almacenamiento en caché web). La consistencia es diferente de la coherencia, que ocurre en los sistemas con o sin caché, y es la consistencia de los datos con respecto a todos los procesadores. La coherencia se ocupa de mantener un orden global en el que todos los procesadores ven las escrituras en una sola ubicación o una sola variable. La coherencia se ocupa de la ordenación de las operaciones en múltiples ubicaciones con respecto a todos los procesadores.

Los lenguajes de alto nivel, como C++ y Java, mantienen el contrato de consistencia al traducir las operaciones de memoria en operaciones de bajo nivel de una manera que preserva la semántica de la memoria, reordenando algunas instrucciones de memoria y encapsulando la sincronización requerida con llamadas de biblioteca como pthread_mutex_lock().

Ejemplo

Supongamos que ocurre el siguiente caso:

• La fila X se replica en los nodos M y N
• El cliente A escribe la fila X para node M
• Después de un período de tiempo t, el cliente B lee la fila X del nodo N

El modelo de consistencia determina si el cliente B definitivamente verá la escritura realizada por el cliente A, definitivamente no, o no puede depender de ver la escritura.

Tipos

Los modelos de consistencia definen reglas para el orden aparente y la visibilidad de las actualizaciones, y están en un continuo con compensaciones. Hay dos métodos para definir y categorizar modelos de consistencia; emitir y ver.

Cuestión

El método de edición describe las restricciones que definen cómo un proceso puede emitir operaciones.

Ver

Ver método que define el orden de operaciones visible a procesos.

Por ejemplo, un modelo de coherencia puede definir que un proceso no puede emitir una operación hasta que se completen todas las operaciones emitidas previamente. Diferentes modelos de consistencia imponen diferentes condiciones. Un modelo de consistencia puede considerarse más fuerte que otro si requiere todas las condiciones de ese modelo y más. En otras palabras, un modelo con menos restricciones se considera un modelo de consistencia más débil.

Estos modelos definen cómo debe diseñarse el hardware y, en un nivel superior, cómo debe codificar el programador. El modelo elegido también afecta la forma en que el compilador puede reordenar las instrucciones. En general, si se ordenan las dependencias de control entre las instrucciones y si se escriben en la misma ubicación, el compilador puede reordenarlas según sea necesario. Sin embargo, con los modelos que se describen a continuación, algunos pueden permitir que se reordenen las escrituras antes de las cargas, mientras que otros no.

Modelos de coherencia sólida

Coherencia estricta

La consistencia estricta es el modelo de consistencia más fuerte. Bajo este modelo, una escritura en una variable por parte de cualquier procesador debe ser vista instantáneamente por todos los procesadores.

El diagrama de modelo estricto y los diagramas de modelo no estrictos describen la restricción de tiempo: instantánea. Se puede entender mejor como si estuviera presente un reloj global en el que cada escritura debería reflejarse en todos los cachés del procesador al final de ese período de reloj. La siguiente operación debe ocurrir solo en el próximo período de reloj.

Este es el modelo más rígido. En este modelo, el resultado esperado del programador se recibirá cada vez. Es determinista. Su relevancia práctica está restringida a un experimento mental y formalismo, porque el intercambio instantáneo de mensajes es imposible. No ayuda a responder la pregunta de resolución de conflictos en escrituras simultáneas en el mismo elemento de datos, porque supone que las escrituras simultáneas son imposibles.

Coherencia secuencial

El modelo de consistencia secuencial fue propuesto por Lamport (1979). Es un modelo de memoria más débil que el modelo de consistencia estricta. Una escritura en una variable no tiene que ser vista instantáneamente, sin embargo, las escrituras en variables por parte de diferentes procesadores deben ser vistas en el mismo orden por todos los procesadores. La consistencia secuencial se cumple si "el resultado de cualquier ejecución es el mismo que si las operaciones (de lectura y escritura) de todos los procesos en el almacén de datos se ejecutaran en algún orden secuencial, y las operaciones de cada procesador individual aparecieran en este orden. secuencia en el orden especificado por su programa." Adve y Gharachorloo, 1996 definen dos requisitos para implementar la consistencia secuencial; orden del programa y atomicidad de escritura.

• Orden del programa: El orden del programa garantiza que cada proceso emite una solicitud de memoria ordenada por su programa.
• Escribe atomicidad: Escribe atomicidad define que las solicitudes de memoria se atienden en función del orden de una sola cola FIFO.

En la coherencia secuencial, no hay noción de tiempo ni de las operaciones de escritura más recientes. Hay algunas operaciones de entrelazado que son iguales para todos los procesos. Un proceso puede ver las operaciones de escritura de todos los procesos, pero solo puede ver sus propias operaciones de lectura. Debe mantenerse el orden del programa dentro de cada procesador y el orden secuencial de las operaciones entre procesadores. Para preservar el orden secuencial de ejecución entre procesadores, todas las operaciones deben parecer ejecutarse instantánea o atómicamente con respecto a todos los demás procesadores.

Estas operaciones solo necesitan "aparecer" completar porque es físicamente imposible enviar información instantáneamente. Por ejemplo, en un sistema que utiliza un solo bus compartido globalmente, una vez que se publica información en una línea de bus, se garantiza que todos los procesadores verán la información en el mismo instante. Por lo tanto, pasar la información a la línea de bus completa la ejecución con respecto a todos los procesadores y parece que se ha ejecutado. Las arquitecturas sin caché o las arquitecturas en caché con redes de interconexión que no son instantáneas pueden contener una ruta lenta entre los procesadores y las memorias. Estas rutas lentas pueden dar como resultado una inconsistencia secuencial, porque algunas memorias reciben los datos de transmisión más rápido que otras.

La consistencia secuencial puede producir resultados no deterministas. Esto se debe a que la secuencia de operaciones secuenciales entre procesadores puede ser diferente durante diferentes ejecuciones del programa. Todas las operaciones de memoria deben ocurrir en el orden del programa.

La linealizabilidad (también conocida como consistencia atómica o memoria atómica) se puede definir como consistencia secuencial con una restricción de tiempo real, al considerar una hora de inicio y una hora de finalización para cada operación. Una ejecución es linealizable si cada operación tiene lugar en un orden linealizable colocando un punto entre su hora de inicio y su hora de finalización y garantiza la coherencia secuencial.

La verificación de la coherencia secuencial a través de la verificación del modelo es indecidible en general, incluso para los protocolos de coherencia de caché de estado finito.

Coherencia causal

La consistencia causal definida por Hutto y Ahamad, 1990, es un debilitamiento del modelo de consistencia secuencial al categorizar eventos en aquellos relacionados causalmente y aquellos que no lo están. Define que solo las operaciones de escritura que están causalmente relacionadas deben ser vistas en el mismo orden por todos los procesos. Por ejemplo, si un evento b tiene efecto a partir de un evento anterior a, la consistencia causal garantiza que todos los procesos vean el evento b después del evento a. Tanenbaum et al., 2007 proporcionan una definición más estricta de que un almacén de datos se considera causalmente coherente en las siguientes condiciones:

• Los escritos que están potencialmente relacionados causalmente deben ser vistos por todos los procesos en el mismo orden.
• Los escritos concurrentes pueden verse en un orden diferente en diferentes máquinas.

Este modelo relaja la consistencia secuencial en las escrituras simultáneas de un procesador y en las escrituras que no están causalmente relacionadas. Dos escrituras pueden relacionarse causalmente si una escritura en una variable depende de una escritura anterior en cualquier variable si el procesador que realiza la segunda escritura acaba de leer la primera escritura. Las dos escrituras podrían haber sido realizadas por el mismo procesador o por procesadores diferentes.

Al igual que en la coherencia secuencial, las lecturas no necesitan reflejar los cambios de forma instantánea; sin embargo, deben reflejar todos los cambios en una variable de forma secuencial.

W(x)2 ocurre después de W(x)1 debido a la lectura hecha por P2 a x antes de W(x)2, por lo que este ejemplo es causalmente consistente bajo Hutto y Ahamad's definición (aunque no bajo Tanenbaum et al.'s, porque W(x)2 y W(x)3 no se ven en el mismo orden para todos los procesos). Sin embargo, R(x)2 y R(x)3 ocurren en un orden diferente en P3 y P4, por lo que este ejemplo es secuencialmente inconsistente.

Coherencia del procesador

Para mantener la consistencia en los datos y lograr sistemas de procesador escalables donde cada procesador tiene su propia memoria, se derivó el modelo de consistencia del procesador. Todos los procesadores deben ser coherentes en el orden en que ven las escrituras realizadas por un procesador y en la forma en que ven las escrituras de diferentes procesadores en la misma ubicación (se mantiene la coherencia). Sin embargo, no es necesario que sean coherentes cuando las escrituras las realizan distintos procesadores en distintas ubicaciones.

Cada operación de escritura se puede dividir en varias subescrituras para todas las memorias. Una lectura de una de esas memorias puede ocurrir antes de que se complete la escritura en esta memoria. Por lo tanto, la lectura de datos puede estar obsoleta. Por lo tanto, un procesador en PC puede ejecutar una carga más joven cuando una tienda más antigua necesita detenerse. Leer antes de escribir, leer después de leer y escribir antes de escribir aún se conserva en este modelo.

El modelo de consistencia del procesador es similar al modelo de consistencia de PRAM con una condición más fuerte que define que todos los demás procesos deben ver todas las escrituras en la misma ubicación de memoria en el mismo orden secuencial. La consistencia del procesador es más débil que la consistencia secuencial pero más fuerte que el modelo de consistencia PRAM.

El sistema multiprocesador Stanford DASH implementa una variación de la consistencia del procesador que es incomparable (ni más débil ni más fuerte) con las definiciones de Goodman. Todos los procesadores deben ser coherentes en el orden en que ven las escrituras de un procesador y en la forma en que ven las escrituras de diferentes procesadores en la misma ubicación. Sin embargo, no es necesario que sean coherentes cuando las escrituras las realizan distintos procesadores en distintas ubicaciones.

Consistencia de RAM canalizada o consistencia FIFO

La consistencia RAM canalizada (consistencia PRAM) fue presentada por Lipton y Sandberg en 1988 como uno de los primeros modelos de consistencia descritos. Debido a su definición informal, de hecho hay al menos dos implementaciones sutilmente diferentes, una por Ahamad et al. y uno de Mosberger.

En consistencia PRAM, todos los procesos ven las operaciones de un solo proceso en el mismo orden en que fueron emitidas por ese proceso, mientras que las operaciones emitidas por diferentes procesos pueden verse en diferente orden desde diferentes procesos. La consistencia de la PRAM es más débil que la consistencia del procesador. PRAM relaja la necesidad de mantener la coherencia con una ubicación en todos sus procesadores. Aquí, las lecturas de cualquier variable se pueden ejecutar antes que las escrituras en un procesador. Leer antes de escribir, leer después de leer y escribir antes de escribir aún se conserva en este modelo.

Coherencia de caché

La coherencia de la caché requiere que todas las operaciones de escritura en la misma ubicación de memoria se realicen en algún orden secuencial. La consistencia de la caché es más débil que la consistencia del procesador e incomparable con la consistencia de la PRAM.

Consistencia lenta

En consistencia lenta, si un proceso lee un valor previamente escrito en una ubicación de memoria, no puede leer posteriormente ningún valor anterior de esa ubicación. Las escrituras realizadas por un proceso son inmediatamente visibles para ese proceso. La coherencia lenta es un modelo más débil que la coherencia de memoria caché y PRAM.

Ejemplo: El diagrama de memoria lenta muestra un ejemplo de consistencia lenta. El primer proceso escribe 1 en la ubicación de memoria X y luego escribe 1 en la ubicación de memoria Y. El segundo proceso lee 1 de Y y luego lee 0 de X aunque X se escribió antes que Y.

Hutto, Phillip W. y Mustaque Ahamad (1990) ilustran que mediante una programación adecuada, la memoria lenta (coherencia) puede ser expresiva y eficiente. Mencionan que la memoria lenta tiene dos propiedades valiosas; localidad y apoyando la reducción de la memoria atómica. Proponen dos algoritmos para presentar la expresividad de la memoria lenta.

Garantías de sesión

Estos 4 modelos de coherencia se propusieron en un artículo de 1994. Se centran en las garantías en la situación en la que solo un usuario o aplicación realiza modificaciones de datos.

Coherencia de lectura monotónica

Tanenbaum et al., 2007 define la consistencia de lectura monotónica de la siguiente manera:

"Si un proceso lee el valor de un elemento de datos x, cualquier operación de lectura sucesiva en x por parte de ese proceso siempre devolverá el mismo valor o un valor más reciente."

La coherencia de lectura monotónica garantiza que después de que un proceso lea un valor del elemento de datos x en el momento t, nunca verá el valor anterior de ese elemento de datos.

Coherencia de escritura monotónica

Tanenbaum et al., 2007 definen la condición de consistencia de escritura monotónica de la siguiente manera:

"Una operación de escritura realizada por un proceso en un elemento de datos X se completa antes de cualquier operación de escritura sucesiva en X por parte del mismo proceso."

Coherencia de lectura de sus escrituras

Un valor escrito por un proceso en un elemento de datos X siempre estará disponible para una operación de lectura sucesiva realizada por el mismo proceso en el elemento de datos X.

Coherencia de escritura, seguimiento y lectura

En la consistencia escrituras-seguimiento-lecturas, las actualizaciones se propagan después de realizar las operaciones de lectura anteriores. Tanenbaum et al., 2007 define la siguiente condición para la consistencia escritura-seguimiento-lectura:

"Se garantiza que una operación de escritura realizada por un proceso en un elemento de datos x después de una operación de lectura anterior en x por el mismo proceso tendrá lugar en el mismo valor de x que se leyó o en uno más reciente.&# 34;

Modelos de coherencia de memoria débiles

Los siguientes modelos requieren una sincronización específica por parte de los programadores.

Pedido débil

El ordenamiento débil clasifica las operaciones de memoria en dos categorías: operaciones de datos y operaciones de sincronización. Para hacer cumplir el orden del programa, un programador necesita encontrar al menos una operación de sincronización en un programa. Las operaciones de sincronización indican al procesador que se asegure de que ha completado y visto todas las operaciones anteriores realizadas por todos los procesadores. El orden y la atomicidad del programa se mantienen solo en las operaciones de sincronización y no en todas las lecturas y escrituras. Esto se derivó del entendimiento de que ciertas operaciones de memoria, como las que se realizan en una sección crítica, no necesitan ser vistas por todos los procesadores hasta que se completen todas las operaciones en la sección crítica. Asume que reordenar las operaciones de memoria a las regiones de datos entre las operaciones de sincronización no afecta el resultado del programa. Esto aprovecha el hecho de que los programas escritos para ejecutarse en un sistema multiprocesador contienen la sincronización necesaria para garantizar que no se produzcan carreras de datos y que siempre se produzcan resultados SC.

X = 1;
cercaxready = 1;

cercamientras (!xready) {};

cercay = 2;

La coherencia no está relajada en este modelo. Una vez que se cumplen estos requisitos, todos los demás datos " Las operaciones se pueden reordenar. La forma en que esto funciona es que un contador rastrea el número de operaciones de datos y hasta que este contador se convierte en cero, la operación de sincronización no se emite. Además, no se emiten más operaciones de datos a menos que se completen todas las sincronizaciones anteriores. Las operaciones de memoria entre dos variables de sincronización se pueden superponer y reordenar sin afectar la corrección del programa. Este modelo asegura que la atomicidad de escritura siempre se mantenga, por lo tanto, no se requiere una red de seguridad adicional para el pedido débil.

Para mantener el pedido débil, las operaciones de escritura antes de una operación de sincronización deben realizarse globalmente antes de la operación de sincronización. Las operaciones presentes después de una operación de sincronización también deben realizarse solo después de que se complete la operación de sincronización. Por lo tanto, los accesos a las variables de sincronización son secuencialmente consistentes y cualquier lectura o escritura debe realizarse solo después de que se hayan completado las operaciones de sincronización previas.

Existe una alta dependencia de la sincronización explícita en el programa. Para los modelos de pedido débiles, el programador debe usar instrucciones de bloqueo atómico, como pruebas y establecimientos, recuperación, almacenamiento, condicional, unido o debe etiquetar variables de sincronización o usar cercas.

consistencia de lanzamiento

El modelo de consistencia de liberación relaja el modelo de consistencia débil al distinguir la operación de sincronización de entrada de la operación de sincronización de salida. Bajo un orden débil, cuando se va a ver una operación de sincronización, todas las operaciones en todos los procesadores deben ser visibles antes de que se realice la operación de sincronización y el procesador continúe. Sin embargo, bajo el modelo de consistencia de liberación, durante la entrada a una sección crítica, denominada como " adquirir ", todas las operaciones con respecto a las variables de memoria locales deben completarse. Durante la salida, denominado como " lanzamiento ", todos los cambios realizados por el procesador local deben propagarse a todos los demás procesadores. La coherencia todavía se mantiene.

La operación de adquisición es una carga/lectura que se realiza para acceder a la sección crítica. Una operación de lanzamiento es una tienda/escritura realizada para permitir que otros procesadores usen las variables compartidas.

Entre las variables de sincronización, la consistencia secuencial o la consistencia del procesador se pueden mantener. Usando SC, todas las variables de sincronización competidores deben procesarse en orden. Sin embargo, con PC, un par de variables competidoras solo deben seguir este orden. Se puede permitir que las adquirir más jóvenes ocurran antes de los lanzamientos anteriores.

rcsc y rcpc

Hay dos tipos de consistencia de liberación, consistencia de liberación con consistencia secuencial (RCSC) y consistencia de liberación con consistencia del procesador (RCPC). El último tipo denota qué tipo de consistencia se aplica a aquellas operaciones nominadas a continuación como especial.

Hay operaciones de memoria especiales (cf. ordinarias), en sí mismas que constan de dos clases de operaciones: sinc o NSYNC . Estos últimos son operaciones no utilizadas para la sincronización; Los primeros son, y consisten en operaciones adquirir y de lanzamiento . Una adquisición es efectivamente una operación de memoria de lectura utilizada para obtener acceso a un cierto conjunto de ubicaciones compartidas. La versión, por otro lado, es una operación de escritura que se realiza para otorgar permiso para acceder a las ubicaciones compartidas.

Para consistencia secuencial (RCSC), las restricciones son:

• adquirir → todos,
• todos → lanzamiento,
• especial → especial.

Para la consistencia del procesador (RCPC) El orden del programa Write to Read está relajado, con restricciones:

• adquirir → todos,
• todos → lanzamiento,
• especial → especial (excepto cuando la escritura especial es seguida por lectura especial).

Nota: La notación anterior A → B implica que si la operación A precede a B en el orden del programa, entonces se aplica el orden del programa.

consistencia de entrada

Esta es una variante del modelo de consistencia de liberación. También requiere el uso de las instrucciones adquirir y para establecer explícitamente una entrada o salida a una sección crítica. Sin embargo, bajo consistencia de entrada, a cada variable compartida se le asigna una variable de sincronización específica para ella. De esta manera, solo cuando la adquisición es a la variable X, todas las operaciones relacionadas con X deben completarse con respecto a ese procesador. Esto permite que ocurran operaciones concurrentes de diferentes secciones críticas de diferentes variables compartidas. La concurrencia no se puede ver para operaciones críticas en la misma variable compartida. Tal modelo de consistencia será útil cuando se puedan procesar diferentes elementos de matriz al mismo tiempo.

consistencia local

En la consistencia local, cada proceso realiza sus propias operaciones en el orden definido por su programa. No hay restricción en el orden en que parecen realizar las operaciones de escritura de otros procesos. La consistencia local es el modelo de consistencia más débil en los sistemas de memoria compartida.

consistencia general

In general consistency, all the copies of a memory location are eventual identical after all processes ' writes are completed.

consistencia eventual

Una consistencia eventual es un modelo de consistencia débil en el sistema con la falta de actualizaciones simultáneas. Define que si ninguna actualización lleva mucho tiempo, todas las réplicas finalmente se vuelven consistentes.

Las bases de datos descentralizadas más compartidas tienen un modelo de consistencia eventual, ya sea base: básicamente disponible; estado blando; eventualmente consistente, o una combinación de ácido y base a veces llamado sal: secuencial; acordado; enérgico; resistente a la manipulación, y también simétrico; sin administrador; enérgico; y tiempo consensuado.

Modelos de consistencia de memoria relajada

Algunos modelos de consistencia diferentes se pueden definir relajando uno o más requisitos en la consistencia secuencial llamados modelos de consistencia relajada. Estos modelos de consistencia no proporcionan consistencia de memoria a nivel de hardware. De hecho, los programadores son responsables de implementar la consistencia de la memoria mediante la aplicación de técnicas de sincronización. Los modelos anteriores se clasifican en función de cuatro criterios y se detallan más.

Hay cuatro comparaciones para definir la consistencia relajada:

Relajación

Una manera de categorizar la consistencia relajada es definir qué requisitos de consistencia secuencial se relajan. Podemos tener modelos menos estrictos al relajar el orden del programa o escribir requisitos de atomicidad definidos por Adve y Gharachorloo, 1996. El orden del programa garantiza que cada proceso emite una solicitud de memoria ordenada por su programa y escribe atomicidad define que las solicitudes de memoria son atendidos en función del orden de una sola cola FIFO. En la orden relajante del programa, cualquiera o todo el orden de los pares de operación, escribir después de escribir, leer después de escribir, o leer / escribir después de leer, puede ser relajado. En el modelo de atomicidad de escritura relajada, un proceso puede ver sus propios escritos ante cualquier otro procesador.

Sincronización vs. no sincronización

Un modelo de sincronización se puede definir dividiendo los accesos de memoria en dos grupos y asignando diferentes restricciones de consistencia a cada grupo considerando que un grupo puede tener un modelo de consistencia débil mientras que el otro necesita un modelo de consistencia más restrictivo. En cambio, un modelo no sincronizador asigna el mismo modelo de consistencia a los tipos de acceso a la memoria.

Cuestión vs.

El método de edición proporciona simulación de consistencia secuencial definiendo las restricciones de los procesos para emitir operaciones de memoria. Considerando que el método de vista describe las restricciones de visibilidad de los eventos orden de procesos.

Fuerza relativa del modelo

Algunos modelos de consistencia son más restrictivos que otros. En otras palabras, los modelos estrictos de consistencia imponen más limitaciones como requisitos de consistencia. La fuerza de un modelo puede ser definida por el orden del programa o la relajación de la atomicidad y la fuerza de los modelos también se puede comparar. Algunos modelos están directamente relacionados si aplican las mismas relajacións o más. Por otro lado, los modelos que relajan diferentes requisitos no están directamente relacionados.

La consistencia secuencial tiene dos requisitos, el orden del programa y la atomicidad de escritura. Se pueden obtener diferentes modelos de consistencia relajada relajando estos requisitos. Esto se hace para que, junto con restricciones relajadas, aumente el rendimiento, pero el programador es responsable de implementar la consistencia de la memoria mediante la aplicación de técnicas de sincronización y debe tener una buena comprensión del hardware.

Posibles relajaciones:

• Escribe para leer el orden del programa
• Escribe el orden del programa
• Lea y lea para escribir órdenes de programa

Relajado Escribir para leer

Un enfoque para mejorar el rendimiento a nivel de hardware es relajando el PO de una escritura seguida de una lectura que oculta efectivamente la latencia de las operaciones de escritura. La optimización en la que se basa este tipo de relajación es que permite que las lecturas posteriores estén en un orden relajado con respecto a las escrituras anteriores del procesador. Debido a esta relajación, algunos programas como XXX pueden no dar resultados SC debido a esta relajación. Mientras que se espera que programas como YYY dan resultados consistentes debido a la aplicación de las restricciones de orden de programa restantes.

Tres modelos caen en esta categoría. El modelo IBM 370 es el modelo más estricto. Una lectura puede completarse antes de una escritura anterior a una dirección diferente, pero tiene prohibido devolver el valor de la escritura a menos que todos los procesadores hayan visto la escritura. El modelo SPARC V8 Total Store Ordering Model (TSO) relaja parcialmente el modelo IBM 370, permite que una lectura devuelva el valor de su propia escritura de procesador con respecto a otras escrituras en la misma ubicación, es decir, devuelve el valor de su propia escritura antes de que otros lo ven. Similar al modelo anterior, esto no puede devolver el valor de la escritura a menos que todos los procesadores hayan visto la escritura. El modelo de consistencia del procesador (PC) es el más relajado de los tres modelos y relaja ambas limitaciones de modo que una lectura puede completar antes de una escritura anterior incluso antes de que se haga visible para otros procesadores.

En el ejemplo A, el resultado solo es posible en IBM 370 porque la lectura (a) no se emite hasta que se complete la escritura (a) en ese procesador. Por otro lado, este resultado es posible en TSO y PC porque permiten las lecturas de las banderas antes de las escrituras de las banderas en un solo procesador.

En el ejemplo B, el resultado solo es posible con PC, ya que permite que P2 devuelva el valor de una escritura incluso antes de que sea visible para P3. Esto no será posible en los otros dos modelos.

Para garantizar la consistencia secuencial en los modelos anteriores, las redes de seguridad o las cercas se utilizan para hacer cumplir manualmente la restricción. El modelo IBM370 tiene algunas instrucciones especializadas de serialización que se colocan manualmente entre las operaciones. Estas instrucciones pueden consistir en instrucciones de memoria o instrucciones no memoria, como ramas. Por otro lado, los modelos TSO y PC no proporcionan redes de seguridad, pero los programadores aún pueden usar operaciones de lectura-modificación-escritura para que parezca que el orden del programa todavía se mantiene entre una escritura y una lectura siguiente. En el caso de TSO, PO parece mantenerse si el R o W que ya es parte de una R-modify-W es reemplazada por un R-modify-W, esto requiere que W en el R-Modify-W es un 'Dummy' que devuelve el valor de lectura. De manera similar para PC, PO parece mantenerse si la lectura se reemplaza por una escritura o ya es parte de R-Modify-W.

Sin embargo, las optimizaciones del compilador no se pueden hacer después de ejercer esta relajación sola. Las optimizaciones del compilador requieren la flexibilidad completa de reordenar dos operaciones en el PO, por lo que la capacidad de reordenar una escritura con respecto a una lectura no es suficientemente útil en este caso.

Relajado escribir para leer y escribir para escribir

Algunos modelos relajan aún más el orden del programa al relajar incluso las restricciones de orden entre escrituras en diferentes ubicaciones. El modelo de pedido de tienda parcial (PSO) de SPARC V8 es el único ejemplo de dicho modelo. La capacidad de canalizar y superponer escrituras en diferentes ubicaciones desde el mismo procesador es la optimización de hardware clave habilitada por PSO. PSO es similar a TSO en términos de requisitos de atomicidad, ya que permite que un procesador lea el valor de su propia escritura y evita que otros procesadores lean la escritura de otro procesador antes de que la escritura sea visible para todos los demás procesadores. PSO mantiene el orden del programa entre dos escrituras mediante una instrucción STBAR explícita. El STBAR se inserta en un búfer de escritura en implementaciones con búfer de escritura FIFO. Se utiliza un contador para determinar cuándo se han completado todas las escrituras antes de la instrucción STBAR, lo que activa una escritura en el sistema de memoria para incrementar el contador. Un reconocimiento de escritura disminuye el contador, y cuando el contador se convierte en 0, significa que todas las escrituras anteriores se completaron.

En los ejemplos A y B, PSO permite estos dos resultados no coherentes secuencialmente. La red de seguridad que proporciona PSO es similar a la de TSO, impone el orden del programa desde una escritura hasta una lectura y hace cumplir la atomicidad de escritura.

Al igual que en los modelos anteriores, las relajaciones permitidas por PSO no son lo suficientemente flexibles para ser útiles para la optimización del compilador, lo que requiere una optimización mucho más flexible.

Relajantes órdenes de lectura y lectura para escribir programas: Alpha, RMO y PowerPC

En algunos modelos, todas las operaciones a diferentes ubicaciones son relajadas. Una lectura o escritura puede reordenarse con respecto a una lectura o escritura diferente en una ubicación diferente. El ordenamiento débil se puede clasificar en esta categoría y dos tipos de modelos de coherencia de publicación (RCsc y RCpc) también se incluyen en este modelo. También se proponen tres arquitecturas comerciales bajo esta categoría de relajación: los modelos de orden de memoria relajada (RMO) Digital Alpha, SPARC V9 e IBM PowerPC.

Estas tres arquitecturas comerciales exhiben instrucciones de vallas explícitas como sus redes de seguridad. El modelo Alpha proporciona dos tipos de instrucciones de cerca, barrera de memoria (MB) y barrera de memoria de escritura (WMB). La operación MB se puede utilizar para mantener el orden del programa de cualquier operación de memoria antes del MB con una operación de memoria después de la barrera. De manera similar, WMB mantiene el orden del programa solo entre escrituras. El modelo SPARC V9 RMO proporciona una instrucción MEMBAR que se puede personalizar para ordenar lecturas y escrituras anteriores con respecto a futuras operaciones de lectura y escritura. No es necesario usar lectura-modificación-escritura para lograr este orden porque la instrucción MEMBAR se puede usar para ordenar una escritura con respecto a una lectura posterior. El modelo PowerPC utiliza una sola instrucción de valla denominada instrucción SYNC. Es similar a la instrucción MB, pero con la pequeña excepción de que las lecturas pueden ocurrir fuera del orden del programa incluso si se coloca un SYNC entre dos lecturas en la misma ubicación. Este modelo también difiere de Alpha y RMO en términos de atomicidad. Permite ver una escritura antes de que se complete una lectura. Es posible que se requiera una combinación de operaciones de lectura, modificación y escritura para crear una ilusión de atomicidad de escritura.

RMO y PowerPC permiten reordenar las lecturas en la misma ubicación. Estos modelos violan el orden secuencial en los ejemplos A y B. Una relajación adicional permitida en estos modelos es que las operaciones de memoria que siguen a una operación de lectura pueden superponerse y reordenarse con respecto a la lectura. Alpha y RMO permiten que una lectura devuelva el valor de la escritura temprana de otro procesador. Desde la perspectiva de un programador, estos modelos deben mantener la ilusión de atomicidad de escritura aunque permitan que el procesador lea su propia escritura antes.

Modelos de memoria transaccional

El modelo de memoria transaccional es la combinación de modelos de coherencia de caché y consistencia de memoria como modelo de comunicación para sistemas de memoria compartida compatibles con software o hardware; un modelo de memoria transaccional proporciona consistencia de memoria y coherencia de caché. Una transacción es una secuencia de operaciones ejecutadas por un proceso que transforma datos de un estado consistente a otro. Una transacción se confirma cuando no hay conflicto o se aborta. En las confirmaciones, todos los cambios son visibles para todos los demás procesos cuando se completa una transacción, mientras que las anulaciones descartan todos los cambios. En comparación con los modelos de consistencia relajados, un modelo transaccional es más fácil de usar y puede proporcionar un mayor rendimiento que un modelo de consistencia secuencial.

Otros modelos de coherencia

Algunos otros modelos de coherencia son los siguientes:

• Congruencia causal+
• Congruencia del Delta
• Congruencia de tinta
• serializabilidad de una copia
• Serializability
• Congruencia de los campos vectores
• Congruencia débil
• Gran consistencia

Se han concebido varios otros modelos de consistencia para expresar restricciones con respecto al orden o la visibilidad de las operaciones, o para tratar suposiciones específicas de fallas.

consistencia y replicación

Tanenbaum et al., 2007 define dos razones principales para replicar; confiabilidad y rendimiento. La confiabilidad se puede lograr en un sistema de archivos replicado cambiando a otra réplica en el caso de la falla de réplica actual. La replicación también protege los datos de ser corrompidos al proporcionar múltiples copias de datos en diferentes réplicas. También mejora el rendimiento dividiendo el trabajo. Si bien la replicación puede mejorar el rendimiento y la confiabilidad, puede causar problemas de consistencia entre múltiples copias de datos. Las copias múltiples son consistentes si una operación de lectura devuelve el mismo valor de todas las copias y una operación de escritura como una sola operación atómica (transacción) actualiza todas las copias antes de que se realice cualquier otra operación. Tanenbaum, Andrew y amp; Maarten van Steen, 2007 consulte este tipo de consistencia como consistencia estricta proporcionada por la replicación sincrónica. Sin embargo, aplicar sincronizaciones globales para mantener todas las copias consistentes es costoso. Una forma de disminuir el costo de la sincronización global y mejorar el rendimiento puede ser debilitar las restricciones de consistencia.

Modelos de consistencia centrados en datos

Tanenbaum et al., 2007 define el modelo de consistencia como un contrato entre el software (procesos) y la implementación de memoria (almacén de datos). Este modelo garantiza que si el software sigue ciertas reglas, la memoria funciona correctamente. Dado que, en un sistema sin un reloj global, es difícil definir la última operación entre las escrituras, se pueden aplicar algunas restricciones sobre los valores que pueden devolverse mediante una operación de lectura. El objetivo de los modelos de consistencia centrados en datos es proporcionar una vista consistente en un almacén de datos donde los procesos pueden llevar a cabo actualizaciones concurrentes.

ordenado consistente de operaciones

Algunos modelos de consistencia, como los modelos de consistencia secuencial y también causal, tratan el orden de las operaciones en datos replicados compartidos para proporcionar consistencia. En estos modelos, todas las réplicas deben acordar un pedido global consistente de actualizaciones.

Operaciones de agrupación

En la operación de agrupación, los accesos a las variables de sincronización son secuencialmente consistentes. Se permite que un proceso acceda a una variable de sincronización que se han completado todas las escrituras anteriores. En otras palabras, los accesos a las variables de sincronización no se permiten hasta que todas las operaciones en las variables de sincronización se realicen por completo.

Modelos de consistencia centrados en el cliente

En sistemas distribuidos, es esencial mantener la consistencia secuencial para controlar las operaciones concurrentes. En algunas tiendas de datos especiales sin actualizaciones simultáneas, los modelos de consistencia centrados en el cliente pueden tratar las inconsistencias de una manera menos costosa. Los siguientes modelos son algunos modelos de consistencia centrados en el cliente:

Protocolos de consistencia

La implementación de un modelo de consistencia se define mediante un protocolo de consistencia. Tanenbaum et al., 2007 ilustra algunos protocolos de consistencia para los modelos centrados en datos.

consistencia continua

Consistencia continua introducida por Yu y Vahdat (2000). En este modelo, la semántica de consistencia de una aplicación se describe utilizando CONITS en la aplicación. Dado que los requisitos de consistencia pueden diferir según la semántica de la aplicación, Yu y Vahdat (2000) creen que un modelo de consistencia uniforme predefinido puede no ser un enfoque apropiado. La aplicación debe especificar los requisitos de consistencia que satisfagan la semántica de la aplicación. En este modelo, una aplicación especifica cada requisito de consistencia como una CONIT (abreviatura de unidades de consistencia). Un CONIT puede ser una consistencia física o lógica y se usa para medir la consistencia. Tanenbaum et al., 2007 describe la noción de un CONIT dando un ejemplo.

Hay tres incoherencias que las aplicaciones pueden tolerar.

Desviación en valores numéricos

La desviación numérica limita la diferencia entre el valor del conit y el valor relativo de la última actualización. Se puede asignar un peso a los escritos que definen la importancia de los escritos en una aplicación específica. Los pesos totales de los escritos invisibles para un conit pueden definirse como una desviación numérica en una aplicación. Hay dos tipos diferentes de desviación numérica; desviación numérica absoluta y relativa.

Desviación en el orden

Ordenar la desviación es la discrepancia entre el orden local de escribir en una réplica y su orden relativo en la eventual imagen final.

Desviación en la estabilidad entre las réplicas

La desviación de la estabilidad define la validez de la escritura más antigua ligando la diferencia entre el tiempo actual y el tiempo de la escritura más antigua en un conit no visto localmente. Cada servidor tiene una cola local de escritura incierta que se requiere un orden real para ser determinado y aplicado en un conit. La longitud máxima de la cola de escritura incierta es el límite de la desviación de orden. Cuando el número de escritos supera el límite, en lugar de aceptar el nuevo escrito presentado, el servidor intentará comprometer escritos inciertos comunicando con otros servidores basándose en el orden que escribe debe ser ejecutado.

Si los tres límites de desviación se establecen en cero, el modelo de consistencia continua es la fuerte consistencia.

Protocolos basados en primarios

Los protocolos basados en primarios pueden considerarse como una clase de protocolos de consistencia que son más simples de implementar. Por ejemplo, el orden secuencial es un modelo de consistencia popular cuando se considera un orden constante de operaciones. El orden secuencial se puede determinar como un protocolo basado en el primario. En estos protocolos, hay un primario asociado para cada elemento de datos en un almacén de datos para coordinar las operaciones de escritura en ese elemento de datos.

Protocolos de escritura remota

En el protocolo primario más simple que admite la replicación, también conocido como protocolo de retroceso primario, las operaciones de escritura se reenvían a un solo servidor y las operaciones de lectura se pueden realizar localmente.

Ejemplo: Tanenbaum et al., 2007 da un ejemplo de un protocolo de recuperación primaria. El diagrama del protocolo de copia primaria muestra un ejemplo de este protocolo. Cuando un cliente solicita una escritura, la solicitud de escritura se envía a un servidor primario. El servidor primario envía solicitud a copias de seguridad para realizar la actualización. El servidor recibe el reconocimiento de actualización de todas las copias de seguridad y envía el reconocimiento de la terminación de los escritos al cliente. Cualquier cliente puede leer la última actualización disponible localmente. El intercambio de este protocolo es que un cliente que envía la solicitud de actualización puede tener que esperar tanto tiempo para obtener el reconocimiento para continuar. Este problema se puede resolver realizando las actualizaciones localmente, y luego pidiendo a otros respaldos para realizar sus actualizaciones. El protocolo de respaldo primario no bloqueador no garantiza la consistencia de la actualización en todos los servidores de copia de seguridad. Sin embargo, mejora el rendimiento. En el protocolo de copia de seguridad primaria, todos los procesos verán el mismo orden de las operaciones de escritura ya que este protocolo ordena todos los escritos entrantes basados en un tiempo globalmente único. Los protocolos de bloqueo garantizan que los procesos vean el resultado de la última operación de escritura.

Protocolos de escritura local

En los protocolos de escritura local basadas en la primaria, la copia primaria se mueve entre procesos dispuestos a realizar una actualización. Para actualizar un elemento de datos, un proceso lo mueve primero a su ubicación. Como resultado, en este enfoque, las operaciones de escritura sucesivas se pueden realizar localmente, mientras que cada proceso puede leer su copia local de los elementos de datos. Después de finalizar la actualización principal, la actualización se reenvía a otras réplicas y todos realizan la actualización localmente. Este enfoque no bloqueado puede conducir a una mejora. El diagrama del protocolo de escritura local representa el enfoque de escritura local en protocolos basados en primaria. Un proceso solicita una operación de escritura en un elemento de datos x. El servidor actual se considera como el nuevo primario para un elemento de datos x. Se realiza la operación de escritura y cuando se termina la solicitud, la primaria envía una solicitud de actualización a otros servidores de copia de seguridad. Cada copia de seguridad envía un reconocimiento a la primaria después de finalizar la operación de actualización.

Protocolos de escritura replicada

En los protocolos de escritura replicada, a diferencia del protocolo basado en la primaria, todas las actualizaciones se llevan a cabo en todas las réplicas.

Replicación activa

En la replicación activa, hay un proceso asociado con cada réplica para realizar la operación de escritura. En otras palabras, se envían actualizaciones a cada réplica en forma de operación para ser ejecutadas. Todas las actualizaciones deben realizarse en el mismo orden en todas las réplicas. Como resultado, se requiere un mecanismo de multidifusión totalmente ordenado. Existe un problema de escalabilidad en la implementación de un mecanismo de multidifusión en grandes sistemas distribuidos. Hay otro enfoque en el que cada operación se envía a un coordinador central (secuenciador). El coordinador primero asigna un número de secuencia a cada operación y luego reenvía la operación a todas las réplicas. El segundo enfoque también no puede resolver el problema de escalabilidad.

Protocolos basados en quórum

La votación puede ser otro enfoque en los protocolos de escritura replicada. En este enfoque, un cliente solicita y recibe permiso de múltiples servidores para leer y escribir datos replicados. Como ejemplo, supongamos que en un sistema de archivos distribuido, un archivo se replica en N servidores. Para actualizar un archivo, un cliente debe enviar una solicitud al menos n/2 + 1 Para llegar a su acuerdo para realizar una actualización. Después del acuerdo, se aplican cambios en el archivo y se asigna un nuevo número de versión al archivo actualizado. Del mismo modo, para leer el archivo replicado, un cliente envía una solicitud a los servidores n/2 + 1 para recibir el número de versión asociado de esos servidores. La operación de lectura se completa si todos los números de versión recibidos son la versión más reciente.

protocolos de coherencia de caché

En un sistema de archivos replicado, un protocolo de coherencia de caché proporciona la consistencia del caché, mientras que los cachés generalmente están controlados por los clientes. En muchos enfoques, el hardware subyacente proporciona la consistencia del caché. Algunos otros enfoques en sistemas distribuidos basados en el middleware aplican soluciones basadas en software para proporcionar la consistencia del caché.

Los modelos de consistencia de caché pueden diferir en sus estrategias de detección de coherencia que definen cuando ocurren inconsistencias. Hay dos enfoques para detectar la inconsistencia; Soluciones estáticas y dinámicas. En la solución estática, un compilador determina qué variables pueden causar la inconsistencia del caché. Entonces, el compilador impone una instrucción para evitar el problema de inconsistencia. En la solución dinámica, el servidor verifica las inconsistencias en el tiempo de ejecución para controlar la consistencia de los datos en caché que han cambiado después de que se almacenó en caché.

La estrategia de aplicación de la coherencia es otro protocolo de coherencia de caché. Define cómo proporcionar la consistencia en los cachés utilizando las copias ubicadas en el servidor. Una forma de mantener los datos consistentes es nunca almacenar en caché los datos compartidos. Un servidor puede mantener los datos y aplicar algunos protocolo de consistencia, como protocolos basados en primarios para garantizar la consistencia de los datos compartidos. En esta solución, solo los clientes pueden almacenar datos privados. En el caso de que los datos compartidos se almacenen en caché, hay dos enfoques para hacer cumplir la coherencia del caché.

En el primer enfoque, cuando se actualizan los datos compartidos, el servidor reenvía la invalidación a todos los cachés. En el segundo enfoque, se propaga una actualización. La mayoría de los sistemas de almacenamiento en caché aplican estos dos enfoques o eligen dinámicamente entre ellos.