Algoritmos de 2 procesos: de los intentos a Peterson

Intercalador con verificación exhaustiva

Elige un algoritmo y juega de planificador: cada clic ejecuta una línea. Hay dos buscadores que recorren todo el espacio de estados:

🔎 Buscar contraejemplo: la traza más corta que rompe la exclusión mutua, lleva a deadlock o viola el progreso.
⏳ ¿Starvation?: busca con el algoritmo de Tarjan una componente del grafo en que un proceso quiere entrar para siempre mientras el otro sigue entrando, con ambos planificados (planificación justa).

Intercalador de algoritmos de exclusión mutua

Tú eres el planificador: cada clic ejecuta una línea de P0 o P1. Las escrituras y lecturas son atómicas, como en los exámenes.

Código de P_i (j = el otro) · 05-OSL-Mutual exclusion Algorithms, diap. 25–30

0// sección no críticaP0P1
1while (lock != 0) ;
2lock = 1;
3/* SECCIÓN CRÍTICA */
4lock = 0;

lock0

Traza (0 pasos)

Todavía no hay pasos.

Leer lock y escribir lock = 1 son DOS operaciones (check-then-act): si ambos leen 0 antes de que alguno escriba, entran los dos. La solución real es un test-and-set atómico.

Veredicto verificado

Algoritmo	Exclusión mutua	Deadlock-free	Progreso	Starvation-free
Lock ingenuo (`while (lock); lock = 1`)	✘ (6 pasos)	✔	✔	✘
Alternancia estricta (`order`)	✔	✔	✘ (1 paso)	— (el problema es el progreso)
Intento 2 de Dekker: esperar y luego flag	✘ (6 pasos)	✔	✔	✘
Intento 3 de Dekker: flag y luego esperar	✔	✘ (4 pasos)	✔	✘ (por el deadlock)
Interés + alternancia con if (clase 05)	✘ (7 pasos)	✔	✔	—
Interés + alternancia con while (lab 06)	✔	✔	✔	✘
Dekker	✔	✔	✔	✔
Peterson	✔	✔	✔	✔
Dijkstra del lab (N = 2)	✔	✔	✔	✘
Dijkstra 1965 real (`b[]`, `c[]`, `k`; N = 2)	✔	✔	✔	✘
Peterson de las diapositivas (`turn = j`)	✔	✔	✔	✔ (cota 1)
Peterson con `turn = j` antes que `flag[i] = true`	✘ (8 pasos)	✔	✔	—
Hyman (E1 2026-1)	✘ (9 pasos)	✔	✔	✘
Flaky (E1 2024-I)	✔	✘ (6 pasos)	✔	✘

La tabla sale de ejecutar los dos buscadores sobre cada algoritmo. Todos suponen lecturas y escrituras atómicas y ejecución en el orden del código (consistencia secuencial). Las demostraciones formales de cada «✔» (Dekker, Peterson, filtro, torneo) están en demostraciones.

La progresión: por qué cada intento falla

Intento 1 · lock ingenuo. Leer lock != 0 y luego escribir lock = 1 es un check-then-act no atómico. Si ambos leen 0 antes de escribir, los dos entran. Hace falta test-and-set.

Intento 2 · alternancia estricta (while (order != i); SC; order = j;). Hay exclusión mutua, pero:

obliga a alternar 0, 1, 0, 1 (si P0 quiere entrar 1 vez por hora y P1 1000 veces, P1 queda al ritmo de P0);
si un hilo se detiene fuera de la SC, o termina, el otro no vuelve a entrar nunca. Viola el requisito 2 y la propiedad (c) de Dijkstra.

Intento 3 · vector de interés (interest[i] = T; while (interest[j]);). Si ambos marcan su interés, deadlock. La versión que primero espera y después marca (intento 2 de Stallings) rompe la exclusión mutua.

Intento 4 · cortesía (while (interest[j]) { interest[i] = F; sleep; interest[i] = T; }). Si ambos van al mismo paso, livelock: ceden y reintentan sincronizados para siempre. Se rompe con un poco de asimetría, pero sigue siendo un bug.

Interés + alternancia. La clase 05 (diap. 46) propone solo esperar a order si el otro está interesado, y pregunta: «¿puedes dar un ejemplo donde no basta?»

Respuesta: contraejemplo de la diapositiva 49 (verificado)

Con order = 0 y ambos interest en F:

#	P0	P1	interest
1		`interest[1] = T`	[F, T]
2		`if (interest[0])`: es F, así que salta la espera
3	`interest[0] = T`	(a punto de entrar)	[T, T]
4	`if (interest[1])`: T, así que evalúa `while (order != 0)`
5	`order == 0`, así que entra a la SC	entra a la SC

El que salta el if nunca mira order, y el otro tiene justo el turno a su favor, así que entran ambos. La corrección es hacer que la espera por order se evalúe siempre que haya conflicto, como en Dekker o Peterson.

El lab 06 (Listing 5) usa la versión con while (ceder, esperar order, reintentar). La búsqueda exhaustiva dice: ✔ exclusión mutua, ✔ deadlock-free, ✘ starvation. P0 baja su interés, pasa la espera porque order ya es 0, y en esa ventana P1 lo adelanta. Al salir, P1 deja order = 0 de nuevo. (El resumen previo de lab2 decía que esta versión era «≈ Peterson y sin starvation»: no es cierto.)

Dekker (el primero correcto, 1965)

flag[i] = true;
while (flag[j]) {             // ¿el otro también quiere?
    if (turn == j) {          // y es su turno: me aparto
        flag[i] = false;
        while (turn == j) ;   // espero a que me ceda el turno
        flag[i] = true;       // vuelvo a intentarlo
    }
}
/* SC */
turn = j;                     // al salir, le cedo el turno
flag[i] = false;

Combina los flags (intentos 2–4) con el turn del intento 1.

Exclusión mutua: cada proceso levanta su flag antes de mirar el del otro, así que es imposible que ambos hayan visto al otro en F justo antes de entrar.
Deadlock-free: turn vale 0 o 1, así que exactamente uno cede.
Starvation-free: el que cede baja su flag (dejando entrar al otro) y el otro, al salir, hace turn = j, lo que lo libera. Cada uno cede a lo sumo una vez.

Peterson (1981)

flag[i] = true;          // quiero entrar
turn = j;                // pero te cedo la prioridad
while (flag[j] && turn == j) ;
/* SC */
flag[i] = false;

Es mucho más simple que Dekker y se generaliza a N procesos (algoritmo de filtro o árbol de torneos). La demostración de ausencia de bloqueo del libro analiza tres casos: si P0 está bloqueado, entonces flag[1] = T y turn = 1. Pero:

P1 no puede estar desinteresado, porque tiene su flag en T;
P1 no puede estar esperando, porque con turn = 1 puede entrar;
P1 no puede monopolizar la SC, porque antes de cada entrada hace turn = 0.

Peterson en el PC1 2021

acquire_lock(i):  FLAG[i] ← up;  AFTER_YOU ← i;
                  wait (FLAG[j] = down ∨ AFTER_YOU ≠ i)
release_lock(i):  FLAG[i] ← down

AFTER_YOU es la víctima: el último que la escribe cede el paso.

Solución PC1 2021 P1(b): mutex, starvation y deadlock

Exclusión mutua ✔. Por contradicción: el último que escribe AFTER_YOU (digamos P0) solo pasa si ve FLAG[1] = down, y eso es imposible porque P1 levantó su flag antes.
Deadlock-free ✔. Si ambos esperan, AFTER_YOU es 0 o 1; el que no es AFTER_YOU ve AFTER_YOU ≠ i y pasa.
Starvation-free ✔ (espera ≤ 1). Si P1 espera y P0 sale y vuelve a pedir, P0 escribe AFTER_YOU ← 0, así que ahora cede P0.

Nota del profesor: «Peterson, tournament of 2 processes». Para N procesos se construye un árbol de torneo de Peterson.

Algoritmo A del E1 2026-1 (Hyman, 1966)

1. f[i] ← V
2. mientras (turno ≠ i) hacer:
3.     mientras (f[j]) hacer omitir
4.     turno ← i
5. /* SC */
6. f[i] ← F

Este algoritmo se publicó en 1966 como mejora de Dekker, y era incorrecto.

Solución propia (3 pts), verificada con el intercalador

1) Exclusión mutua ✘. Traza con turno = 0:

#	P0	P1	f	turno
1		`f[1] ← V`	[F, V]	0
2		`turno ≠ 1`, así que entra al while		0
3		`f[0] = F`, así que sale del while interno		0
4	`f[0] ← V`	(se desaloja antes de la línea 4)	[V, V]	0
5	`turno = 0`, no entra al while: SC			0
6		`turno ← 1`		1
7		`turno = 1`, sale del while: SC		1

⇒ ambos en la SC. La comprobación de f[j] y la escritura de turno no son atómicas en conjunto.

2) Deadlock ✔ (libre). El que tiene turno = i no entra al while, y el otro gira hasta ver f[j] = F.

3) Starvation ✘. Con turno = 0, P1 gira en while (f[0]). P0 sale (f[0] ← F) y vuelve a pedir (f[0] ← V) antes de que P1 lea, entrando directo porque turno sigue en 0. El ciclo es repetible (lo encuentra «⏳ ¿Starvation?»).

Flaky (E1 2024-I)

public void lock() {
    int me = ThreadID.get();
    do {
        do { turn = me; } while (busy);
        busy = true;
    } while (turn != me);
}
public void unlock() { busy = false; }

Solucionario oficial (resumido) + verificación

Exclusión mutua ✔. Si A y B estuvieran dentro y A pasó primero, A vio turn = A. Para que B pase, turn tuvo que volver a B, es decir, B escribió turn después de que A entrara. Pero A ya había puesto busy = true, así que B no puede salir del bucle interno.
Deadlock ✘. A: turn = A, busy = true. B: turn = B y queda girando porque busy es true. A: ve turn ≠ A y repite el bucle externo, así que también queda en el interno. Nadie liberará busy. El intercalador lo encuentra en 6 pasos.
Starvation ✘, por el deadlock y también por bypass.

Fuente ·lab2/05-OSL-Mutual exclusion Algorithms.pdf (diap. 25–51) · lab2/06-OSL-Mutex.pdf (Listings 1–5) · Stallings §5.1 (Dekker: 4 intentos, Peterson) · lab2/Resumenes/03, 04, 05 · código del curso so/05-OSL-Threads_Mutex/08_lock_attempt.c … 13_interest_alternance.c · for_partial/Evaluaciones_OS_20261 (1).pdf · for_partial/E1_OS_2021_2022_Solver.pdf · for_partial/E1_OS_2024_I__Respuestas_.pdf