Concurrencia: race conditions, SC y requisitos

¿Dónde aparece la concurrencia?

Tres escenarios, que Stallings llama «los temas centrales del diseño de SO»:

• multiprogramación: varios procesos en una sola CPU;
• multiprocesamiento: varios procesos en varias CPUs;
• procesamiento distribuido: varios procesos en varias máquinas.

Tres contextos en los que surge:

• varias aplicaciones que se reparten la CPU;
• aplicaciones estructuradas como procesos concurrentes;
• la estructura del propio SO, que también es software concurrente.

Interleaving (una CPU) y overlapping (varias CPUs) producen los mismos problemas. Incluso con una sola CPU, la velocidad relativa de los procesos es impredecible: depende de los demás procesos, de las interrupciones y de la planificación.

Race condition

«A race condition occurs when multiple processes or threads read and write data items so that the final result depends on the order of execution of instructions.» — Stallings

El «perdedor» de la carrera (el último que escribe) decide el valor final.

echo() compartida (Stallings): P1 lee x en chin y es interrumpido. P2 ejecuta echo completo con y, así que chin = y. P1 continúa e imprime y: el carácter de P1 se perdió y el de P2 salió dos veces. La solución es que solo un proceso a la vez pueda estar en echo().

Otros dos ejemplos:

• a = 1; A hace b = load(a); b = b + 1; store; B hace b = load(a); b = b * 2; store. Si A va primero, a = 4; si B va primero, a = 3.
• b = 1, c = 2; P3 hace b = b + c y P4 hace c = b + c. Si P3 va primero, (b, c) = (3, 5); si P4 va primero, (4, 3). Cambian las dos variables, porque cada proceso lee la del otro.

counter++ no es atómico: son tres instrucciones (READ, ADD, WRITE). Dos hilos que lo ejecutan 10⁸ veces cada uno terminan con menos de 2·10⁸, y el resultado cambia en cada ejecución.

Cómo interactúan los procesos (tabla 5.2)

Grado de conocimiento	Relación	Problemas de control
No se conocen	competencia por recursos	exclusión mutua, deadlock (de recursos reutilizables), starvation
Se conocen indirectamente (comparten un objeto)	cooperación por compartición	exclusión mutua, deadlock, starvation y coherencia de datos
Se conocen directamente (por ID)	cooperación por comunicación (mensajes)	deadlock (de recursos consumibles) y starvation. No hay exclusión mutua, porque no se comparte nada

Coherencia de datos: con la invariante a == b, P1 hace a++; b++ y P2 hace b *= 2; a *= 2. Aunque cada asignación sea exclusiva, intercaladas pueden llevar de a = b = 1 a a = 4, b = 3. La secuencia completa debe ser la sección crítica.

Sección crítica

do {
    entry section      // protocolo de entrada: pedir permiso
    critical section   // acceso al recurso compartido
    exit section       // protocolo de salida: liberar
    remainder section  // lo demás
} while (true);

La race condition es el fenómeno; la región crítica es el código que debe ejecutarse en exclusión.

Dentro del kernel hay dos opciones:

• Kernel expropiable (preemptive): se puede expropiar a un proceso incluso en modo kernel. Responde mejor, pero hay que proteger las estructuras del kernel.
• Kernel no expropiable: el proceso corre hasta que sale del kernel, se bloquea o cede la CPU. Por construcción no hay race conditions en el kernel (en una sola CPU), pero responde peor.

Los 6 requisitos (Stallings §5.2)

1. Exclusión mutua obligatoria: solo un proceso en la SC del mismo recurso.
2. Un proceso detenido en su sección no crítica no debe interferir con los demás.
3. Sin espera indefinida: ni deadlock ni starvation.
4. Si nadie está en la SC, quien pide entrar entra sin demora.
5. Sin suposiciones sobre velocidades relativas ni número de procesadores (solo que cada velocidad es > 0).
6. Se permanece en la SC un tiempo finito.

Las diapositivas los agrupan como exclusión mutua (1), progreso (2, 3 y 4) y espera acotada (5 y 6).

Las propiedades de Dijkstra (1965)

• (a) Simetría: ningún proceso tiene prioridad fija.
• (b) Independencia de las velocidades.
• (c) Un proceso detenido fuera de su SC no bloquea a los demás; esto descarta la alternancia estricta.
• (d) Nada de bloqueo «después de ti» – «después de ti»: la decisión no puede postergarse para siempre.

Las propiedades que siempre piden demostrar

Propiedad	Tipo	Pregunta	Cómo se refuta
Exclusión mutua	safety («nunca pasa algo malo»)	¿Pueden dos estar en la SC?	traza numerada que termina con ambos dentro
Deadlock-free	liveness	si varios quieren entrar, ¿alguno entra?	traza donde todos giran o se bloquean para siempre
Starvation-free	liveness	¿todo el que quiere entrar, entra (espera acotada)?	ciclo repetible donde uno nunca entra
Progreso	liveness	¿quien está fuera de la SC puede impedir la entrada de otro?	el otro está en su sección no crítica y aun así no se puede entrar

Starvation-free ⇒ deadlock-free. Si hay deadlock, no es starvation-free.

Fenómeno	Qué ocurre	Ejemplo
Deadlock	todos bloqueados o esperando algo que solo otro puede dar	intento 3 de Dekker: ambos levantan su flag
Livelock	todos ejecutan instrucciones, pero nadie progresa; se rompe si cambian las velocidades	intento 4: ambos ceden al mismo tiempo, una y otra vez
Starvation	el sistema progresa, pero uno nunca entra	un spinlock TAS con mala suerte

Advertencia: el hardware real reordena

Todas estas demostraciones suponen consistencia secuencial: las lecturas y escrituras ocurren en el orden del código y son atómicas.

• Con optimizaciones, el compilador puede dejar una variable compartida en un registro y no releerla nunca. Por eso en el laboratorio se declaran volatile (en cambio, register es solo una sugerencia de guardar la variable en un registro, lo contrario de lo que se quiere).
• Las CPUs modernas usan modelos más débiles, como TSO en x86: una escritura puede quedar en un store buffer y verse tarde. Peterson puede fallar en hardware real sin barreras de memoria (mfence, atomic_thread_fence). Por eso en la práctica se usan instrucciones atómicas.

Plantillas de demostración

Aquí va la versión corta. Las demostraciones completas (Dekker, Peterson, Almost Dijkstra, filtro, torneo), con la notación de eventos y el formato de las diapositivas, están en demostraciones formales.

Exclusión mutua (por contradicción):

1. Supón que P0 y P1 están ambos en la SC.
2. Toma la última escritura de cada uno antes de su prueba de entrada, por ejemplo write₀(turn = 1) → read₀(flag[1]).
3. Como los registros son atómicos, esas escrituras tienen un orden total. Supón, sin pérdida de generalidad, que P0 fue el último en escribir turn.
4. Deduce qué tuvo que leer el otro proceso y llega a una contradicción.

Refutar con una traza: usa columnas # | P0 | P1 | variables y termina con «⇒ ambos en la SC» o «⇒ ambos en el while para siempre». El intercalador genera la traza.

Starvation: arma un ciclo del tipo P1 espera → P0 sale → P0 reentra antes de que P1 sea planificado → mismo estado inicial, que puede repetirse para siempre.

Ejemplo resuelto: Peterson es mutex (demostración corta)

Supón que ambos están en la SC y que P0 fue el último en escribir turn, así que turn = 1 desde entonces. P0 pasó while (flag[1] && turn == 1), y como turn = 1 no cambió, tuvo que ver flag[1] = false. Pero P1 escribió flag[1] = true antes de escribir turn, lo que ocurrió antes de la escritura de P0, que ocurrió antes de la lectura de P0. Entonces P0 tuvo que leer true. Contradicción. ∎

Autoevaluación

0/7 correctas · 0 respondidas Reiniciar

1. En la cooperación por COMUNICACIÓN (mensajes), ¿cuál NO es un problema de control?

a) Deadlockb) Starvationc) Exclusión mutuad) Ninguno

2. La alternancia estricta viola principalmente…

a) la exclusión mutuab) el progreso: un proceso fuera de la SC impide que el otro entrec) la atomicidadd) nada

3. ¿Qué propiedad es de safety?

a) Starvation-freedomb) Deadlock-freedomc) Exclusión mutuad) Progreso

4. Livelock vs deadlock:

a) Son lo mismob) En el livelock los procesos siguen ejecutando instrucciones pero sin progresarc) El livelock solo ocurre con semáforosd) El deadlock es temporal

5. Invariante a == b; cada asignación es atómica pero la secuencia no. El problema es de…

a) starvationb) coherencia de datosc) livelockd) ninguno

6. ¿Por qué las variables compartidas del laboratorio se declaran volatile?

a) Para hacerlas atómicasb) Para que el compilador no las guarde en un registro y relea siempre la memoriac) Para ponerlas en el stackd) Para que sean thread-local

7. Un kernel NO expropiable…

a) tiene race conditions en el kernel en una sola CPUb) está libre de race conditions en el kernel en una sola CPU, a cambio de peor respuestac) no puede ejecutar syscallsd) es de tiempo real

Fuente ·Stallings 9e §5.2 (lab2/Stallings.pdf) · lab2/Sem3_03-OST-Concurrency.pdf → lab2/Resumenes/01-Concurrencia-Introduccion.md · lab2/Resumenes/13-Stallings-Cap5-Mutex-Sincronizacion.md · lab2/05-OSL-Mutual exclusion Algorithms.pdf · lab2/Resumenes/05-Mutual-Exclusion-Demonstrations.md