1. Por qué necesitamos requisitos
En el tema anterior viste que la exclusión mutua es necesaria para proteger la sección crítica. Pero la exclusión mutua por sí sola no es suficiente: una solución que simplemente bloquee a todos los hilos para siempre garantiza la exclusión mutua, pero es inútil.
Necesitamos criterios precisos para juzgar si una solución es correcta. Estos criterios son los tres requisitos de la exclusión mutua, formulados por Dijkstra en 1965. Toda solución que los cumpla los tres es correcta; si falta alguno, la solución es incorrecta, aunque parezca funcionar en las pruebas.
Los tres requisitos (exclusión mutua, progreso, espera acotada) son el criterio formal para juzgar si una solución de sincronización es correcta. En los temas 8 y 9 se usarán para demostrar que los primeros intentos fallan.
2. Requisito 1: exclusión mutua
La exclusión mutua garantiza que, si un hilo está ejecutando su sección crítica, ningún otro hilo puede estar ejecutando su sección crítica sobre el mismo recurso. En cualquier momento, hay a lo sumo una región crítica activa por recurso compartido.
Este es el requisito más obvio: es la razón por la que se necesita sincronización. Sin exclusión mutua, la sección crítica no está protegida y se producen condiciones de carrera.
La exclusión mutua se refiere a la región crítica, no a la sección crítica: puede haber varios hilos ejecutando la sección crítica en el código (en distintos puntos del programa), pero solo uno a la vez puede estar en la región crítica (ejecutándola).
La exclusión mutua es un requisito de seguridad (safety): garantiza que nunca ocurre algo malo (dos hilos en la sección crítica a la vez). La seguridad se puede expresar como: «nunca ocurre X», donde X es algo malo.
3. Requisito 2: progreso
El progreso (progress) garantiza que, si ningún hilo está en su sección crítica y hay hilos que quieren entrar, la decisión de quién entra a continuación no se puede posponer indefinidamente. Solo los hilos que no están en su sección no crítica (es decir, los que quieren entrar o están en la sección crítica) pueden participar en la decisión.
El progreso evita dos problemas:
- Bloqueo indefinido: un hilo que quiere entrar a la sección crítica espera para siempre, aunque no haya nadie dentro.
- Dependencia de hilos inactivos: la decisión de quién entra no puede depender de un hilo que está en su sección no crítica (es decir, que no quiere entrar). Si un hilo está haciendo otra cosa, no debería impedir que otros entren.
El progreso es un requisito de vivacidad (liveness): garantiza que el sistema siempre hace progreso (algo bueno ocurre eventualmente). La vivacidad se puede expresar como: «eventualmente ocurre Y», donde Y es algo bueno.
La exclusión mutua garantiza que no ocurre algo malo. El progreso garantiza que algo bueno ocurre. Una solución puede tener exclusión mutua pero no progreso (por ejemplo, bloquear a todos los hilos). El progreso es independiente de la exclusión mutua.
4. Requisito 3: espera acotada
La espera acotada (bounded waiting) garantiza que, después de que un hilo solicita entrar a su sección crítica, hay un límite finito en el número de veces que otros hilos pueden entrar a sus secciones críticas antes de que el hilo solicitante entre. En otras palabras, ningún hilo espera indefinidamente.
La espera acotada evita la inanición (starvation): un hilo que quiere entrar a la sección crítica espera para siempre porque otros hilos siempre entran antes.
La espera acotada es más fuerte que el progreso: el progreso solo dice que alguien entra; la espera acotada dice que ese hilo entra en un tiempo acotado. Si hay espera acotada, hay progreso, pero no al revés.
La espera acotada es un requisito de equidad (fairness): garantiza que todos los hilos tengan la oportunidad de ejecutar su sección crítica.
5. Los tres requisitos resumidos
| Requisito | Qué garantiza | Tipo | Qué evita |
|---|---|---|---|
| Exclusión mutua | Solo un hilo a la vez en la sección crítica. | Seguridad (safety) | Condiciones de carrera. |
| Progreso | Si nadie está en la sección crítica y alguien quiere entrar, alguien entra. | Vivacidad (liveness) | Bloqueo indefinido. |
| Espera acotada | Un hilo que quiere entrar no espera indefinidamente. | Equidad (fairness) | Inanición. |
Los tres requisitos son independientes: una solución puede cumplir uno o dos pero no los tres. Una solución correcta debe cumplir los tres.
La relación entre ellos es: espera acotada ⇒ progreso ⇒ (no bloqueo indefinido). Pero exclusión mutua es independiente: se puede tener exclusión mutua sin progreso (bloquear a todos) o progreso sin exclusión mutua (no proteger).
6. Cómo reconocer cuándo una solución falla
Para reconocer si una solución falla un requisito, se busca un contraejemplo: un escenario donde el requisito se viola:
| Requisito | Cómo se viola | Señal |
|---|---|---|
| Exclusión mutua | Dos hilos entran a la sección crítica a la vez. | Resultado incorrecto, condición de carrera. |
| Progreso | Nadie entra a la sección crítica aunque alguien quiere entrar. | El programa se bloquea (deadlock o livelock). |
| Espera acotada | Un hilo espera indefinidamente mientras otros entran repetidamente. | Un hilo nunca ejecuta su sección crítica (inanición). |
La forma de demostrar que una solución falla un requisito es construir un intercalado (una secuencia de ejecución) en el que el requisito se viola. Si existe tal intercalado, la solución es incorrecta.
7. Ejemplos de soluciones que fallan
Veamos tres soluciones que fallan un requisito cada una:
7.1 Solución que falla la exclusión mutua
La solución más simple (y más incorrecta) es no hacer nada:
/* No hay protocolo de entrada ni de salida. */
while (true) {
hacer_trabajo();
counter++; /* sección crítica sin protección */
hacer_mas_trabajo();
}Esta solución viola la exclusión mutua: dos hilos pueden ejecutar counter++ simultáneamente, causando una condición de carrera. Pero cumple el progreso y la espera acotada (no hay espera).
7.2 Solución que falla el progreso
Una solución que bloquea a todos los hilos garantiza la exclusión mutua pero viola el progreso:
/* Un candado global que nunca se libera. */
static int candado = 1; /* 1 = ocupado, 0 = libre */
void entrar() {
while (candado == 1) { } /* espera ocupada */
candado = 1;
}
void salir() {
/* Bug: nunca libera el candado. */
/* candado = 0; <- falta esta línea */
}Esta solución viola el progreso: el primer hilo que entra nunca sale, así que los demás esperan para siempre. Cumple la exclusión mutua (solo un hilo entra) pero viola el progreso y la espera acotada.
7.3 Solución que falla la espera acotada
Una solución que favorece a un hilo puede violar la espera acotada:
/* Un candado que favorece al hilo 0. */
static int turno = 0; /* 0 = hilo 0 puede entrar, 1 = hilo 1 puede entrar */
void entrar(int id) {
while (turno != id) { } /* espera a que sea su turno */
}
void salir(int id) {
turno = 0; /* siempre le da el turno al hilo 0 */
}Esta solución viola la espera acotada para el hilo 1: después de que el hilo 1 sale, el turno vuelve a 0, así que el hilo 1 debe esperar a que el hilo 0 entre y salga antes de poder entrar de nuevo. Si el hilo 0 entra repetidamente, el hilo 1 espera indefinidamente. Cumple la exclusión mutua y el progreso (siempre entra alguien), pero viola la espera acotada.
8. Vivacidad y seguridad
Los tres requisitos se dividen en dos categorías:
- Seguridad (safety): «nunca ocurre algo malo». La exclusión mutua es un requisito de seguridad: nunca dos hilos en la sección crítica a la vez.
- Vivacidad (liveness): «eventualmente ocurre algo bueno». El progreso y la espera acotada son requisitos de vivacidad: eventualmente, un hilo que quiere entrar lo hace.
La seguridad es más fácil de verificar que la vivacidad: para verificar la seguridad, basta con mostrar que no existe un estado donde dos hilos estén en la sección crítica. Para verificar la vivacidad, hay que mostrar que, para cualquier secuencia de ejecución, eventualmente un hilo entra.
La vivacidad incluye conceptos como:
- Deadlock: los hilos se bloquean mutuamente y ninguno progresa.
- Livelock: los hilos están activos pero no progresan (por ejemplo, dos hilos que ceden el turno mutuamente).
- Inanición: un hilo espera indefinidamente porque otros siempre entran antes.
Estos problemas se estudian en detalle en el bloque 8 (interbloqueos).
9. Requisitos en Linux
El núcleo de Linux debe cumplir los tres requisitos en su propia sincronización interna. Los mecanismos que usa son:
- Spinlocks: cumplen exclusión mutua y progreso, pero no garantizan espera acotada (pueden haber inanición).
- Mutexes: cumplen los tres requisitos (con implementaciones correctas).
- Semáforos: cumplen los tres requisitos.
- RCU: cumple exclusión mutua para lectores (múltiples lectores simultáneos) y progreso.
En el espacio de usuario, los mutexes de pthreads y los semáforos POSIX están diseñados para cumplir los tres requisitos. Las operaciones atómicas de C11 (como atomic_fetch_add) cumplen la exclusión mutua por definición (son atómicas).
10. Resumen
- Los tres requisitos son: exclusión mutua, progreso y espera acotada.
- La exclusión mutua garantiza que solo un hilo a la vez esté en la sección crítica.
- El progreso garantiza que si nadie está en la sección crítica, alguien entra.
- La espera acotada garantiza que ningún hilo espera indefinidamente.
- La exclusión mutua es seguridad; el progreso y la espera acotada son vivacidad.
- Una solución correcta debe cumplir los tres requisitos.
- La espera acotada implica el progreso, pero no al revés.
- La exclusión mutua es independiente de los otros dos.
11. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Cuáles son los tres requisitos de una solución correcta?
Exclusión mutua, progreso y espera acotada.
2. ¿Qué garantiza la exclusión mutua?
Que solo un hilo a la vez puede estar en su sección crítica.
3. ¿Qué garantiza el progreso?
Que si nadie está en la sección crítica y alguien quiere entrar, alguien entra.
4. ¿Qué garantiza la espera acotada?
Que un hilo que quiere entrar no espera indefinidamente.
5. ¿Cuál es la diferencia entre seguridad y vivacidad?
La seguridad garantiza que nunca ocurre algo malo. La vivacidad garantiza que eventualmente ocurre algo bueno.
6. ¿La espera acotada implica el progreso?
Sí. Si un hilo espera un tiempo acotado, entonces alguien entra (progreso).
7. ¿El progreso implica la exclusión mutua?
No. Son independientes. Se puede tener progreso sin exclusión mutua.
8. ¿Qué es un deadlock?
Un bloqueo mutuo: los hilos se esperan mutuamente y ninguno progresa.
9. ¿Qué es un livelock?
Los hilos están activos pero no progresan (por ejemplo, cediendo el turno mutuamente).
10. ¿Qué es la inanición?
Un hilo espera indefinidamente porque otros siempre entran antes.
Para practicar
- Diseña una solución que cumpla la exclusión mutua pero viole el progreso.
- Diseña una solución que cumpla la exclusión mutua y el progreso pero viole la espera acotada.
- Explica por qué un mutex de pthreads cumple los tres requisitos.
- Investiga qué es un livelock y da un ejemplo.
- Explica la diferencia entre deadlock y livelock.
- Demuestra que la espera acotada implica el progreso.