El algoritmo de Peterson

1. Qué es el algoritmo de Peterson

El algoritmo de Peterson es una solución por software para la exclusión mutua entre dos hilos. Fue propuesto por Gary Peterson en 1981. Usa dos variables compartidas: una bandera por hilo (indicando intención de entrar) y una variable de turno (para desempatar).

Peterson combinó las ideas de los intentos anteriores (bandera + turno) de una forma que cumple los tres requisitos: exclusión mutua, progreso y espera acotada. Es la solución clásica que se enseña en todos los cursos de sistemas operativos.

El algoritmo es notable porque no usa instrucciones atómicas del hardware: solo usa lecturas y escrituras de variables compartidas. Esto lo hace portable y fácil de entender, aunque, como veremos, no funciona correctamente en procesadores modernos sin barreras de memoria.

2. El código completo

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <stdio.h>

volatile int bandera[2] = {0, 0};   /* 0 = no quiere entrar, 1 = quiere entrar */
volatile int turno = 0;              /* a quién le toca si ambos quieren entrar */

void entrar(int id)
{
    bandera[id] = 1;                 /* levantar la bandera */
    turno = 1 - id;                  /* ceder el turno al otro */
    while (bandera[1 - id] && turno == 1 - id) { }  /* esperar */
}

void salir(int id)
{
    bandera[id] = 0;                 /* bajar la bandera */
}

/* Uso: */
/* entrar(0); */
/* ... sección crítica ... */
/* salir(0); */

El algoritmo tiene dos variables compartidas:

• bandera[0] y bandera[1]: indican si cada hilo quiere entrar a su sección crítica.
• turno: indica a quién le toca entrar si ambos quieren. El último en asignar turno cede el turno al otro.

La clave está en la línea turno = 1 - id: el hilo que quiere entrar cede el turno al otro. Esto parece contraintuitivo, pero es lo que garantiza la exclusión mutua.

3. Cómo funciona

Peterson funciona así:

1. El hilo levanta su bandera: bandera[id] = 1. Indica que quiere entrar. intención
2. Cede el turno al otro: turno = 1 - id. Si ambos quieren entrar, el último en ceder gana. desempate
3. Espera: while (bandera[1-id] && turno == 1-id). Espera solo si el otro quiere entrar Y le toca al otro. espera
4. Entra a la sección crítica. entrar
5. Al salir, baja la bandera: bandera[id] = 0. salir

La condición de espera es la clave: un hilo espera solo si el otro quiere entrar Y le toca al otro. Si el otro no quiere entrar (bandera baja), no espera. Si le toca a él (turno == id), no espera.

4. La demostración

Peterson cumple los tres requisitos. La demostración se basa en el análisis de los posibles estados:

4.1 Exclusión mutua

Supongamos que ambos hilos están en su sección crítica simultáneamente. Para que el hilo 0 entre, debe haber salido del while, lo que requiere que bandera[1] == 0 o turno == 0. Para que el hilo 1 entre, debe haber salido del while, lo que requiere que bandera[0] == 0 o turno == 1.

Si ambos están en la sección crítica:

• Si bandera[0] == 1 y bandera[1] == 1 (ambos quieren entrar), entonces para que el hilo 0 haya entrado, turno debe ser 0. Para que el hilo 1 haya entrado, turno debe ser 1. Contradicción: turno no puede ser 0 y 1 a la vez.
• Si bandera[0] == 0 o bandera[1] == 0, entonces al menos un hilo no quiere entrar, así que no puede estar en la sección crítica (porque levantó la bandera antes de entrar).

Por lo tanto, ambos hilos no pueden estar en la sección crítica simultáneamente. La exclusión mutua se cumple.

4.2 Progreso

Si ningún hilo está en la sección crítica y el hilo 0 quiere entrar:

• Si el hilo 1 no quiere entrar (bandera[1] == 0), el hilo 0 no espera y entra.
• Si el hilo 1 quiere entrar (bandera[1] == 1), entonces el hilo 0 espera solo si turno == 1. Si turno == 0, el hilo 0 entra. Si turno == 1, el hilo 1 entra (porque su condición de espera es bandera[0] && turno == 0, y turno == 1), así que el hilo 1 progresa.

En todos los casos, algún hilo progresa. El progreso se cumple.

4.3 Espera acotada

Si el hilo 0 quiere entrar y está esperando (es decir, bandera[1] == 1 y turno == 1), entonces el hilo 1 puede entrar a la sección crítica a lo sumo una vez antes de que el hilo 0 entre. Esto es porque:

• El hilo 1 está en la sección crítica o va a entrar.
• Cuando el hilo 1 sale, baja su bandera (bandera[1] = 0).
• El hilo 0 ve que bandera[1] == 0 y sale del while.

El hilo 0 no espera a que el hilo 1 entre y salga más de una vez. La espera acotada se cumple.

5. Verificación de la exclusión mutua

La demostración de la exclusión mutua se basa en el análisis de los posibles estados de las variables:

En todos los casos, a lo sumo un hilo puede estar en la sección crítica. La exclusión mutua se cumple.

6. Verificación del progreso

Para verificar el progreso, consideramos todos los casos en los que un hilo quiere entrar:

• Si el hilo 0 quiere entrar y el hilo 1 no quiere (bandera[1] == 0), el hilo 0 entra inmediatamente.
• Si ambos quieren entrar, el que cedió el turno más recientemente (el que tiene turno == su_id) espera, y el otro entra.
• Si el hilo que espera (turno == su_id) y el otro no quiere entrar, el que espera entra.

En todos los casos, algún hilo progresa. El progreso se cumple.

7. Verificación de la espera acotada

Para verificar la espera acotada, consideramos un hilo que está esperando:

• El hilo 0 está esperando: bandera[1] == 1 y turno == 1.
• El hilo 1 está en la sección crítica o va a entrar.
• Cuando el hilo 1 sale, baja su bandera (bandera[1] = 0).
• El hilo 0 ve que bandera[1] == 0 y sale del while.

El hilo 0 espera a lo sumo a que el hilo 1 complete una entrada y salida. No espera más. La espera acotada se cumple.

8. Por qué funciona

Peterson funciona porque combina dos mecanismos:

1. La bandera de intención: indica que un hilo quiere entrar. Sin bandera, no se puede saber si el otro hilo quiere entrar. intención
2. La variable de turno: desempata cuando ambos quieren entrar. El último en ceder el turno gana. desempate

La combinación es la clave: la bandera sola no garantiza la exclusión mutua (ambos pueden levantarlas a la vez). La variable de turno sola no garantiza el progreso (fuerza la alternancia). Juntas, la bandera indica quién quiere entrar y el turno desempata, garantizando los tres requisitos.

La línea turno = 1 - id es la que hace que el algoritmo funcione: al ceder el turno al otro, el hilo que cede pierde la carrera si ambos quieren entrar. El último en ceder gana porque el otro ya cedió antes.

9. Limitaciones: solo dos hilos

Peterson solo funciona para dos hilos. No se puede extender a más hilos simplemente añadiendo más banderas y un turno compartido. Con más hilos, el algoritmo no garantiza la exclusión mutua.

La razón es que la variable de turno solo puede desempatar entre dos hilos. Con tres o más, no hay un único «último en ceder» que gane: varios hilos pueden ceder el turno al mismo tiempo, y la exclusión mutua se viola.

Para más de dos hilos, se usan otros algoritmos (como el de Lamport o el de Eisenberg-McGuire) o, en la práctica, operaciones atómicas del hardware.

10. Problemas en procesadores modernos

Peterson asume que las operaciones de lectura y escritura de variables compartidas son atómicas y que se ejecutan en el orden en que aparecen en el código. En procesadores modernos, estas suposiciones no se cumplen:

• Reordenamiento de instrucciones: el procesador puede reordenar las instrucciones para optimizar el rendimiento. Por ejemplo, puede ejecutar turno = 1 - id antes de bandera[id] = 1.
• Caché: cada procesador tiene su propia caché. Un hilo puede escribir una variable en su caché, pero otro hilo puede leer un valor obsoleto de su caché.
• Memoria débilmente consistente: el modelo de memoria de los procesadores modernos no garantiza que las escrituras de un hilo sean visibles para otros hilos en el orden en que se escribieron.

Estos problemas pueden causar que Peterson falle: la exclusión mutua se viola porque el reordenamiento hace que un hilo vea un estado inconsistente de las variables.

11. El reordenamiento de instrucciones

Los procesadores modernos reordenan las instrucciones para mejorar el rendimiento. Por ejemplo, si una instrucción de escritura tarda mucho (porque hay un cache miss), el procesador puede ejecutar la siguiente instrucción (de lectura) mientras espera.

En Peterson, el reordenamiento puede causar este escenario:

1. Hilo 0 ejecuta turno = 1 antes de bandera[0] = 1. (reordenamiento) reorden
2. Hilo 1 ejecuta turno = 0 antes de bandera[1] = 1. (reordenamiento) reorden
3. Ambos hilos ven turno con el valor del otro. inconsistente
4. Ambos pasan el while y entran a la sección crítica. violación

Este escenario viola la exclusión mutua. Es raro (depende del reordenamiento y del timing), pero posible.

12. Barreras de memoria

Una barrera de memoria (memory barrier o fence) es una instrucción que obliga al procesador a completar todas las operaciones de memoria anteriores antes de ejecutar las siguientes. Previene el reordenamiento.

Con barreras de memoria, Peterson se puede hacer funcionar en procesadores modernos:

void entrar(int id) {
    bandera[id] = 1;
    memory_barrier();              /* barrera: asegurar que bandera se escriba antes de turno */
    turno = 1 - id;
    memory_barrier();              /* barrera: asegurar que turno se escriba antes de leer */
    while (bandera[1 - id] && turno == 1 - id) { }
}

Las barreras de memoria son costosas (impiden la optimización del procesador), pero son necesarias para que Peterson funcione correctamente.

En C11, las barreras se proporcionan a través de las operaciones atómicas con memory_order. Por ejemplo, atomic_store_explicit(&bandera[id], 1, memory_order_release) incluye una barrera de liberación.

13. Simulador interactivo

Este simulador muestra cómo funciona Peterson para dos hilos. Puedes elegir qué hilo intenta entrar y ver cómo se actualizan las variables:

14. Resumen

• Peterson es una solución por software para la exclusión mutua entre dos hilos.
• Usa una bandera por hilo (intención) y una variable de turno (desempate).
• Cumple los tres requisitos: exclusión mutua, progreso y espera acotada.
• Solo funciona para dos hilos.
• No funciona en procesadores modernos sin barreras de memoria (por reordenamiento).
• Con barreras de memoria, funciona correctamente.
• En la práctica, se usan operaciones atómicas del hardware en lugar de Peterson.

15. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa Peterson en C y verifica que cumple los tres requisitos.
2. Dibuja todos los estados posibles de las variables y verifica la exclusión mutua.
3. Explica por qué Peterson no funciona con tres hilos.
4. Investiga qué son las barreras de memoria y cómo se implementan en C11.
5. Explica cómo el reordenamiento de instrucciones rompe Peterson.
6. Modifica el simulador para añadir un tercer hilo y observa la violación.