Semántica atómica

La semántica atómica es un tipo de garantía proporcionada por un registro de datos compartido por varios procesadores en una máquina paralela o en una red de computadoras trabajando juntas. La semántica atómica es muy fuerte. Un registro atómico proporciona fuertes garantías incluso cuando hay concurrencia y fallas.

Un registro de lectura/escritura R almacena un valor y se accede a él mediante dos operaciones básicas: lectura y escritura (v). Una lectura devuelve el valor almacenado en R y una escritura (v) cambia el valor almacenado en R a v. Un registro se llama atómico si cumple las dos propiedades siguientes:

1) Cada operación de invocación de una operación de lectura o escritura:

•Debe aparecer como si se ejecutara en un único punto τ(op) en el tiempo.

•τ (op) funciona de la siguiente manera: τb(op) ≤ τ (op) ≤ τe(op): donde τb(op) y τe(op) indican el momento en que comienza y termina la operación op.

•Si op1 ≠ op2, entonces τ (op1)≠τ (op2)

2) Cada operación de lectura devuelve el valor escrito por la última operación de escritura antes de la lectura, en la secuencia donde todas las operaciones están ordenadas por sus valores τ.

Registro atómico/linealizable:

Terminación: cuando un nodo es correcto, tarde o temprano se completará cada operación de lectura y escritura.

Propiedad de seguridad (puntos de linealización para lectura y escritura y operaciones fallidas):

Operación de lectura: parece como si ocurriera en todos los nodos en algún momento entre la invocación y el tiempo de respuesta.

Operación de escritura: similar a la operación de lectura, parece como si ocurriera en todos los nodos en algún momento entre la invocación y el tiempo de respuesta.

Operación fallida (el término atómico proviene de esta noción): parece como si se completara en cada nodo o nunca sucedió en ningún nodo.

Ejemplo: sabemos que un registro atómico es uno que se puede linealizar a un registro seguro secuencial.

La siguiente imagen muestra dónde debemos colocar el punto de linealización para cada operación:

Se puede definir un registro atómico para una variable con un solo escritor pero lectores múltiples (SWMR), escritor único/lector único (SWSR) o escritor múltiple/lector múltiple (MWMR). Aquí hay un ejemplo de un registro atómico de múltiples lectores y múltiples escritores al que acceden tres procesos (P1, P2, P3). Tenga en cuenta que R. read() → v significa que la operación de lectura correspondiente devuelve v, que es el valor del registro. Por tanto, la siguiente ejecución del registro R podría satisfacer la definición de los registros atómicos: R.escribir(1), R.leer()→1, R.escribir(3), R.escribir(2), R.leer()→2, R.leer()→2.