1. El problema a resolver
Recordemos el problema: dos hilos (o más) tienen una sección crítica que accede a un recurso compartido. Necesitamos un protocolo de entrada y salida que cumpla los tres requisitos: exclusión mutua, progreso y espera acotada.
Los primeros intentos usan solo variables compartidas (sin instrucciones atómicas del hardware). Esto es importante porque muestra qué se puede y qué no se puede hacer con software puro.
Todos los intentos se basan en el mismo esquema:
/* Variables compartidas. */
/* ... */
void entrar(int id) {
/* Protocolo de entrada. */
}
void salir(int id) {
/* Protocolo de salida. */
}
/* Uso: */
entrar(id);
/* sección crítica */
salir(id);2. Intento 1: la variable de turno
La idea más simple es usar una variable turno que indique a quién le toca entrar:
int turno = 0; /* 0 = le toca al hilo 0, 1 = le toca al hilo 1 */
void entrar(int id) {
while (turno != id) { } /* espera hasta que sea su turno */
}
void salir(int id) {
turno = 1 - id; /* cede el turno al otro */
}Análisis:
- Exclusión mutua: ✓ Cumple. Solo un hilo puede tener el turno a la vez.
- Progreso: ✗ No cumple. Si el hilo 0 no quiere entrar a su sección crítica, el hilo 1 no puede entrar aunque el hilo 0 le haya cedido el turno. El hilo 1 espera indefinidamente.
- Espera acotada: ✗ No cumple. El hilo 1 puede esperar indefinidamente si el hilo 0 no quiere entrar.
El problema es que la variable de turno obliga a los hilos a alternarse, incluso si uno no quiere entrar. Si el hilo 0 está haciendo otra cosa, el hilo 1 no puede entrar a su sección crítica.
El progreso requiere que si nadie está en la sección crítica y alguien quiere entrar, alguien entra. Con la variable de turno, si el hilo 0 no quiere entrar, el hilo 1 no puede entrar aunque la sección crítica esté libre.
3. Intento 2: la bandera de intención
La idea es que cada hilo levante una bandera antes de entrar, indicando su intención:
int bandera[2] = {0, 0}; /* 0 = no quiere entrar, 1 = quiere entrar */
void entrar(int id) {
bandera[id] = 1; /* levantar la bandera */
while (bandera[1 - id]) { } /* esperar a que el otro baje la suya */
}
void salir(int id) {
bandera[id] = 0; /* bajar la bandera */
}Análisis:
- Exclusión mutua: ✗ No cumple. Si ambos hilos levantan sus banderas simultáneamente, ambos pasan el
whiley entran a la sección crítica a la vez. - Progreso: ✓ Cumple (cuando no hay carrera). Si un hilo no quiere entrar, el otro puede entrar.
- Espera acotada: ✓ Cumple (cuando no hay carrera). La espera es acotada porque el otro hilo eventualmente baja su bandera.
El problema es que la bandera de intención no garantiza la exclusión mutua: ambos hilos pueden levantar sus banderas a la vez y entrar simultáneamente. La verificación while (bandera[1-id]) no es atómica: entre la verificación y la entrada, el otro hilo puede levantar su bandera.
Si ambos hilos levantan sus banderas simultáneamente, ambos pasan el while y entran a la sección crítica a la vez. La bandera indica intención, pero no garantiza que solo uno entre.
4. Intento 3: turno y bandera combinados
La idea es combinar la variable de turno (para el desempate) con la bandera de intención (para indicar quién quiere entrar):
int turno = 0;
int bandera[2] = {0, 0};
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 */
}Análisis:
- Exclusión mutua: ✓ Cumple. Si ambos levantan banderas, el último en ceder el turno espera.
- Progreso: ✓ Cumple. Si un hilo no quiere entrar, el otro puede entrar.
- Espera acotada: ✗ No cumple. Un hilo puede esperar indefinidamente si el otro levanta su bandera repetidamente.
El problema es que la espera acotada no se garantiza: si el hilo 0 levanta y baja su bandera repetidamente, el hilo 1 puede esperar indefinidamente.
5. Por qué fallan
Los tres intentos fallan por la misma razón fundamental: no usan instrucciones atómicas. Las operaciones de lectura y escritura de variables compartidas no son atómicas en la mayoría de los procesadores, así que el planificador puede interrumpir entre ellas.
Específicamente:
- Intento 1 (turno): falla el progreso porque la variable de turno fuerza la alternancia, incluso si un hilo no quiere entrar.
- Intento 2 (bandera): falla la exclusión mutua porque ambos hilos pueden levantar sus banderas simultáneamente.
- Intento 3 (turno + bandera): falla la espera acotada porque un hilo puede esperar indefinidamente.
Ninguno de los tres cumple los tres requisitos. Se necesita una solución que combine las ideas de forma correcta.
6. Las lecciones aprendidas
Los intentos fallidos enseñan tres lecciones:
- La exclusión mutua requiere atomicidad: la verificación y la entrada deben ser atómicas. Si no lo son, dos hilos pueden pasar la verificación simultáneamente. atomicidad
- El progreso requiere que la entrada no dependa de hilos inactivos: si un hilo no quiere entrar, no debe impedir que otros entren. independencia
- La espera acotada requiere un mecanismo de turnos justo: no basta con ceder el turno; hay que garantizar que cada hilo eventualmente reciba el turno. justicia
Estas lecciones conducen al algoritmo de Peterson (tema 9), que combina la bandera de intención con la variable de turno de una forma que cumple los tres requisitos (para dos hilos).
7. Simulador interactivo
Este simulador permite probar los tres intentos y ver cuál falla:
Simulador · primeros intentos
| Requisito | ¿Se cumple? |
|---|
8. Resumen
- La variable de turno cumple la exclusión mutua pero viola el progreso y la espera acotada.
- La bandera de intención cumple el progreso y la espera acotada pero viola la exclusión mutua.
- La combinación de turno y bandera cumple la exclusión mutua y el progreso pero viola la espera acotada.
- Ninguno de los tres cumple los tres requisitos.
- La causa fundamental es la falta de atomicidad en las operaciones de lectura y escritura.
- Las lecciones conducen al algoritmo de Peterson.
9. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué viola la variable de turno?
El progreso y la espera acotada: si un hilo no quiere entrar, el otro no puede entrar.
2. ¿Qué viola la bandera de intención?
La exclusión mutua: ambos hilos pueden levantar sus banderas simultáneamente.
3. ¿Qué viola la combinación de turno y bandera?
La espera acotada: un hilo puede esperar indefinidamente.
4. ¿Por qué fallan los tres intentos?
Porque no usan instrucciones atómicas. Las operaciones de lectura y escritura no son indivisibles.
5. ¿Qué lección enseña el intento 1?
La entrada no debe depender de hilos inactivos.
6. ¿Qué lección enseña el intento 2?
La verificación y la entrada deben ser atómicas.
7. ¿Qué lección enseña el intento 3?
Se necesita un mecanismo de turnos justo para la espera acotada.
8. ¿Cuál es el siguiente paso después de estos intentos?
El algoritmo de Peterson, que combina las ideas correctamente.
9. ¿Un intento que cumple la exclusión mutua pero no el progreso es útil?
No. Es inútil porque puede bloquear el sistema.
10. ¿Por qué es importante analizar los intentos fallidos?
Porque enseñan qué no funciona y guían hacia la solución correcta.
Para practicar
- Implementa el intento 1 y verifica que viola el progreso.
- Implementa el intento 2 y verifica que viola la exclusión mutua.
- Implementa el intento 3 y verifica que viola la espera acotada.
- Dibuja un intercalado que demuestre la violación de cada requisito.
- Explica por qué la atomicidad resolvería cada problema.
- Investiga el algoritmo de Peterson y cómo cumple los tres requisitos.