Registros safe, regular y atomic

Tema nuevo

Viene de The Art of Multiprocessor Programming (Herlihy, Shavit, Luchangco, Spear), cap. 4. Sirve para precisar qué suponemos cuando decimos «las lecturas y escrituras son atómicas» en Peterson o Bakery.

🎯 Al terminar podrás

1. Leer las siglas SRSW, MRSW y MRMW.
2. Decir qué puede devolver una lectura solapada con una escritura en un registro safe, regular y atomic.
3. Detectar en una línea de tiempo una inversión nuevo → viejo (regular pero no atómico).

Antes necesitas: Exclusión mutua: supuestos de Peterson

• Visual mira el diagrama o la tabla y explica qué cambia en cada paso
• Simulador predice el estado antes de pulsar el paso siguiente

¿Qué es un registro?

Una ubicación de memoria (el nombre es histórico) que guarda un valor binario y soporta dos operaciones:

public interface Register<T> {
    T read();
    void write(T v);
}

T suele ser booleano o un entero de m bits.

Quién lee y quién escribe

Sigla	Significado
SRSW	Single-Reader Single-Writer
MRSW	Multi-Reader Single-Writer
MRMW	Multi-Reader Multi-Writer

Qué garantiza cuando hay concurrencia

El problema está en las lecturas que se solapan en el tiempo con una escritura.

Registro	Lectura sin solapamiento	Lectura solapada con escrituras
Safe	el último valor escrito	cualquier valor válido del dominio (basura legal)
Regular	el último valor escrito	el valor viejo o alguno de los nuevos que se están escribiendo
Atomic	el último valor escrito	como regular y además linealizable

Un registro atómico se comporta como si cada operación ocurriera en un instante dentro de su intervalo (punto de linealización). Consecuencia práctica: no hay inversión nuevo→viejo. Si una lectura devolvió el valor nuevo, ninguna lectura que empiece después de que esa termine puede devolver el viejo.

Atomic ⇒ Regular ⇒ Safe.

🔮 Predice antes de seguir

Un registro guarda 0 y un escritor escribe 1. Durante esa escritura, el lector A lee y obtiene 1. Justo después de que A termina, el lector B empieza y obtiene 0. ¿Puede pasar en un registro regular? ¿Y en uno atómico?

Ya tengo mi respuesta: comparar

• Regular: sí. Cada lectura solapada puede devolver el valor viejo o el nuevo, y no hay ninguna restricción entre lecturas distintas.
• Atómico: no. Si A ya vio el valor nuevo, la escritura «ocurrió» antes del punto de linealización de A. B empieza después de que A termina, así que debe ver 1. Esa es la inversión nuevo → viejo, y la linealizabilidad la prohíbe.

Simulador

¿Safe, regular o atómico?

Un escritor y varios lectores (MRSW). Haz clic en una lectura para cambiar el valor que devuelve y observa cómo cambia la clasificación.

Lecturas sin solapamientoSafe: solapa y devuelve basura¿Regular o no? (diap. 14–17)Atómico (diap. 19)

✔ safe✔ regular✘ atómico (linealizable)

Cada lectura se solapa con write(1): puede devolver el valor viejo (0) o el nuevo (1), así que es regular. Pero read(1) terminó antes de que empezara read(0): esa inversión nuevo→viejo no es linealizable, así que NO es atómico.

El espacio de registros

Tres dimensiones independientes:

1. Lectores y escritores: SRSW → MRSW → MRMW.
2. Tamaño: booleano → m-valuado.
3. Fuerza: safe → regular → atomic.

El resultado central del capítulo es que se puede construir un registro MRMW m-valuado atómico usando solo registros SRSW booleanos safe. Por eso algoritmos como Bakery son válidos «sin hardware especial».

La cadena de construcciones (Herlihy & Shavit, cap. 4)

Paso	De…	A…	Idea
1	SRSW safe	MRSW safe	un arreglo con una copia por lector; el escritor escribe todas y cada lector lee la suya
2	MRSW safe booleano	MRSW regular booleano	el escritor solo escribe si el valor cambia. Así, una lectura solapada devuelve el viejo o el nuevo, porque en un booleano no hay otra opción
3	regular booleano	regular m-valuado	codificación unaria: m bits; se escribe el nuevo valor y se «borra hacia abajo»; el lector toma el primer bit en 1
4	SRSW regular	SRSW atómico	marca de tiempo: el escritor escribe (valor, ts) y el lector recuerda el último par y nunca devuelve uno más viejo
5	SRSW atómico	MRSW atómico	una tabla n × n: cada lector, además, le escribe a los demás lo que leyó, para que nadie vea algo más viejo después
6	MRSW atómico	MRMW atómico	cada escritor lee todas las marcas, toma max + 1 (como Bakery) y escribe en su registro; el lector toma el par (ts, id) mayor

La conclusión es que la «atomicidad» que suponen Peterson y Bakery se puede fabricar en software a partir de lo más débil que existe, a costa de más memoria y más lecturas.

Cómo lo preguntarían

• Dada una línea de tiempo de escrituras y lecturas, clasificar el registro (el simulador de arriba).
• «¿Por qué el diagrama de la diapositiva 17 es regular pero no linealizable?» → read(1) termina antes de que empiece read(0), ambas solapadas con write(1). Cada una por separado es legal (viejo o nuevo), pero en un orden secuencial, después de ver el 1 no se puede volver a ver el 0.
• «Un registro booleano safe, ¿es regular?» → Sí. Si la lectura solapada puede devolver cualquier valor del dominio 1, devuelve el viejo o el nuevo, a menos que la escritura no cambie el valor. Ese es el truco de la construcción de Herlihy: solo escribir si el valor cambia.

⚠️ Errores que cuestan puntos

• Pensar que un registro safe devuelve el viejo o el nuevo cuando hay solapamiento.Puede devolver cualquier valor del dominio. Viejo o nuevo es la garantía de regular.
• Creer que regular y atómico son lo mismo.Atómico agrega la linealizabilidad: no hay inversión nuevo → viejo entre lecturas.

Autoevaluación

0/4 correctas · 0 respondidas Reiniciar

1. Un registro safe, ante una lectura que NO se solapa con escrituras, devuelve…

a) cualquier valorb) el último valor escritoc) el valor iniciald) error

2. Escritura write(1) en curso (valor previo 0). Dos lecturas solapadas: la primera devuelve 1, la segunda (que empieza después de que la primera termina) devuelve 0. El registro puede ser…

a) atómicob) regular pero no atómicoc) ni siquiera safed) MRMW

3. ¿Qué significa MRSW?

a) Many Reads Same Writeb) Multi-Reader Single-Writerc) Multi-Register Shared-Wordd) Memory Read/Store Word

4. Linealizable significa…

a) Que las operaciones no se solapanb) Que existe un orden secuencial, consistente con el tiempo real, que explica todos los resultadosc) Que usa un lockd) Que es SRSW

🗣️ Explícalo tú (Feynman)

Explica con una línea de tiempo la diferencia entre un registro regular y uno atómico.

Dilo en voz alta o escríbelo en 4–5 líneas, sin mirar la página. Después revisa qué te faltó.

Tu explicación debería mencionar…

• Si no hay solapamiento, los dos devuelven el último valor escrito.
• Con solapamiento, regular devuelve el viejo o alguno de los nuevos, sin coherencia entre lecturas.
• Atómico: cada operación «ocurre» en un instante dentro de su intervalo, así que si una lectura vio el nuevo, ninguna posterior ve el viejo.

📈 ¿Qué tan bien lo dominas?

Elige pensando en lo que hiciste, no en lo que leíste. Para marcar 3 tienes que haber resuelto un ejercicio nuevo sin pistas y haberlo justificado. Si solo lo leíste y sientes que «ya entendí», todavía es un 1.

0No lo reconozco o lo confundo con otro tema1Lo entiendo leyendo, pero no lo aplico solo2Resuelvo ejercicios parecidos a los vistos, con alguna pista3Resuelvo uno nuevo sin ayuda y justifico cada paso4Lo transfiero: comparo alternativas y veo casos límite

Fuente ·for_partial/pending_themes/Sem0_6-OST-About registers.pdf · Herlihy & Shavit, The Art of Multiprocessor Programming, cap. 4