En la computación distribuida, los sistemas de memoria compartida y los sistemas de paso de mensajes son dos métodos de comunicación entre procesos ampliamente estudiados. En los sistemas de memoria compartida , los procesos se comunican accediendo a estructuras de datos compartidas. Un registro compartido (de lectura/escritura) , a veces llamado simplemente registro, es un tipo fundamental de estructura de datos compartida que almacena un valor y tiene dos operaciones: lectura , que devuelve el valor almacenado en el registro, y escritura , que actualiza el valor almacenado. Otros tipos de estructuras de datos compartidas incluyen lectura-modificación-escritura, prueba-y-configuración, comparación-e-intercambio, etc. La ubicación de memoria a la que se accede simultáneamente a veces se denomina registro.
Los registros se pueden clasificar según la condición de consistencia que satisfacen cuando se accede a ellos simultáneamente, el dominio de valores posibles que se pueden almacenar y cuántos procesos pueden acceder con la operación de lectura o escritura , lo que da un total de 24 tipos de registros. [1]
Cuando la lectura y la escritura ocurren simultáneamente, el valor devuelto por la lectura puede no estar determinado de forma única. Lamport definió tres tipos de registros: registros seguros , registros regulares y registros atómicos . [1] Una operación de lectura de un registro seguro puede devolver cualquier valor si es concurrente con una operación de escritura, y devuelve el valor escrito por la operación de escritura más reciente si la operación de lectura no se superpone con ninguna operación de escritura . Un registro regular se diferencia de un registro seguro en que la operación de lectura puede devolver el valor escrito por la operación de escritura completada más reciente o por una operación de escritura con la que se superponga. Un registro atómico satisface la condición más fuerte de ser linealizable .
Los registros se pueden caracterizar por la cantidad de procesos a los que pueden acceder con una operación de lectura o escritura . Un registro de un solo escritor (SW) solo puede ser escrito por un proceso y un registro de múltiples escritores (MW) puede ser escrito por múltiples procesos. De manera similar, un registro de un solo lector (SR) solo puede ser leído por un proceso y un registro de múltiples lectores (MR) puede ser leído por múltiples procesos. Para un registro SWSR, no es necesario que el proceso de escritura y el proceso de lectura sean el mismo.
La figura siguiente ilustra las construcciones etapa por etapa desde la implementación del registro SWSR en un sistema de paso de mensajes asíncrono hasta la implementación del registro MWMR utilizando un objeto SW Snapshot . Este tipo de construcción a veces se denomina simulación o emulación. [2] En cada etapa (excepto la Etapa 3), el tipo de objeto de la derecha puede implementarse mediante el tipo de objeto más simple de la izquierda. Las construcciones de cada etapa (excepto la Etapa 3) se presentan brevemente a continuación. Hay un artículo que analiza los detalles de la construcción de objetos de instantánea .
Una implementación es linealizable si, para cada ejecución, hay un orden de linealización que satisface las dos propiedades siguientes:
Se puede implementar un registro atómico (linealizable) SWSR en un sistema de transmisión de mensajes asincrónico , incluso si los procesos pueden bloquearse. No existe un límite de tiempo para que los procesos entreguen mensajes a los receptores o ejecuten instrucciones locales. En otras palabras, los procesos no pueden distinguir entre procesos que responden lentamente o simplemente bloquean.
La implementación propuesta por Attiya, Bar-Noy y Dolev [3] requiere n > 2 f , donde n es el número total de procesos en el sistema y f es el número máximo de procesos que pueden bloquearse durante la ejecución. El algoritmo es el siguiente:
El orden de linealización de las operaciones es: linealizar las escrituras en el orden en que ocurren e insertar la lectura después de la escritura cuyo valor devuelve. Podemos comprobar que la implementación es linealizable. Podemos comprobar la propiedad 2, especialmente cuando op1 es write y op2 es read , y read es inmediatamente después de write . Podemos demostrarlo por contradicción. Supongamos que read no ve write , y luego, según la implementación, debemos tener dos conjuntos disjuntos de tamaño ( n - f ) entre los n procesos. Entonces 2 * ( n - f ) ≤ n que lleva a n ≤ 2 f , lo que contradice el hecho de que n > 2 f . Entonces, read debe leer al menos un valor escrito por ese write .
Un registro SWMR puede ser escrito por un solo proceso, pero puede ser leído por varios procesos.
Sea n el número de procesos que pueden leer el registro SWMR. Sea R i , 0 < i ≤ n , los lectores del registro SWMR. Sea w el único escritor del SWMR. La figura de la derecha muestra una construcción de un registro SWMR utilizando una matriz de n ( n + 1) registros SWSR. Denotamos la matriz por A . Cada registro SWSR A[ i , j ] es escribible por R i cuando 0 < i ≤ n y es escribible por w cuando i = n + 1 . Cada registro SWSR A[ i , j ] es legible por R j . Las implementaciones de lectura y escritura se muestran a continuación.
El valor t de una operación es el valor de t que escribe y las operaciones se linealizan por valores t. Si la escritura y la lectura tienen el mismo valor t, ordene la escritura antes de la lectura . Si varias lecturas tienen los mismos valores t, ordénelas por el tiempo de inicio.
Podemos utilizar un objeto SW Snapshot de tamaño n para construir un registro MWMR.
El orden de linealización es el siguiente. Ordene las operaciones de escritura por valores t. Si varias operaciones de escritura tienen el mismo valor t, ordene la operación con el ID de proceso pequeño al frente. Inserte operaciones de lectura justo después de la operación de escritura cuyo valor devuelvan, rompiendo los empates por ID de proceso y, si aún hay empates, rompa el empate por hora de inicio.
![{\displaystyle {\ce {{\operatorname {Paso de mensajes} \atop (MP)~Sistema}->[][{\text{Etapa 1}}]SWSR~atómico->[][{\text{Etapa 2}}]SWMR->[][{\text{Etapa 3}}]SW~instantánea->[][{\text{Etapa 4}}]MWMR}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/387091ecf014adf7ec21aba60eb20503b6caf4e5)