Tema 3: Primeras aproximaciones al problema de la programación concurrente

Introducción y conceptos básicos

Problemas de sincronización entre procesos

En un sistema concurrente pueden aparecer diferentes problemas de sincronización:

Competencia por recursos no compartibles: Por ejemplo, el acceso exclusivo a una impresora o la escritura sobre una posición de memoria.
Cooperación compartiendo información: Si varios procesos leen y escriben sobre las mismas estructuras de datos, pueden producirse inconsistencias y fallos en la coherencia de datos.
Cooperación mediante paso de mensajes: Requiere establecer un orden y secuencia correctos para el envío y la recepción de mensajes.

Por tanto, es imprescindible disponer de reglas y primitivas formales de sincronización entre procesos.

Tipos de sincronización

Existen dos tipos fundamentales de sincronización en programación concurrente:

Exclusión mutua: Garantiza que un recurso no compartible (sección crítica) solo pueda ser accedido por un único proceso a la vez.
Serialización (o condición de sincronización): Un proceso debe detenerse y esperar a que otro proceso modifique el estado de un recurso o complete una tarea previa antes de continuar.

Asimismo, los mecanismos de sincronización se pueden clasificar según el nivel técnico donde reside el soporte:

Soporte directo del hardware de la CPU (sin variables compartidas):
- Inhibición de interrupciones a nivel de procesador (CLI/STI).
Sistemas basados en memoria compartida (RAM):
- Por software puro (solo load y store atómicos): Algoritmos de estado mediante variables compartidas (Intentos 1-4, Dekker, Peterson, Lamport).
- Con soporte atómico de hardware (instrucciones RMW): Instrucciones de la CPU (xchg, TAS, CAS) que operan atómicamente sobre variables en RAM para construir Spinlocks.
- Abstracciones de alto nivel gestionadas por el SO: Semáforos, cerrojos (mutex), variables de condición, regiones críticas y monitores.
Sistemas basados en memoria distribuida:
- Paso de mensajes, tuberías, sockets y llamadas a procedimientos remotos (RPC).

Exclusión mutua

Definición

La exclusión mutua es necesaria cuando varios procesos o hilos desean utilizar un recurso no compartible (recurso crítico).
El bloque de código donde un proceso accede a dicho recurso compartido se denomina sección crítica.

Ejemplos típicos:

Modificación de una variable global compartida por dos hilos:

x = 0

def proceso1():
    global x
    for i in range(1000):
        x = x + 1   # Sección crítica

def proceso2():
    global x
    for i in range(1000):
        x = x + 1   # Sección crítica

Envío de trabajos a un dispositivo físico no entrelazable (como una impresora).

Protocolos de entrada y salida

Para garantizar la exclusión mutua, cada proceso debe ejecutar un protocolo de entrada (preprotocolo) antes de acceder a la sección crítica y un protocolo de salida (posprotocolo) al finalizar.

El esquema general de ejecución de cada proceso es:

while True:
    # Código no crítico
    entry_critical_section()   # Preprotocolo de entrada
    critical_section()         # Sección crítica
    exit_critical_section()    # Posprotocolo de salida
    # Código no crítico

Los protocolos de entrada y salida deben ser eficientes y cumplir tres propiedades fundamentales:

Exclusión mutua: No pueden coincidir dos o más procesos simultáneamente en la sección crítica.
Progreso: Si ningún proceso está en la sección crítica y varios solicitan entrar, la decisión sobre cuál accede no puede posponerse indefinidamente.
Espera limitada: Todo proceso que solicite entrar en la sección crítica debe poder hacerlo en un tiempo finito (ausencia de inanición).

Requisitos de Dijkstra

Edsger Dijkstra estableció cuatro requisitos adicionales indispensables para considerar correcto un algoritmo de exclusión mutua:

Simetría: La solución debe ser idéntica para todos los procesos, sin otorgar prioridades estáticas arbitrarias.
Independencia de velocidades: No se pueden hacer suposiciones sobre las velocidades relativas de ejecución de los procesos ni asumir que son constantes.
No interferencia: Un proceso que se detiene o termina fuera de su sección crítica no debe bloquear a los demás.
Decisión finita: La decisión sobre qué proceso entra en la sección crítica debe tomarse en un número finito de pasos.

Variantes de la exclusión mutua

Existen extensiones al concepto de exclusión mutua pura:

Exclusión múltiple: Como máximo $k$ procesos pueden estar en la sección crítica simultáneamente (p. ej. mediante semáforos de conteo).
Exclusión mutua por categorías: Solo procesos del mismo tipo pueden acceder a la vez (p. ej. el problema de los lectores y escritores: múltiples lectores pueden leer a la vez, pero un escritor exige acceso exclusivo).

Problemas derivados

Si los protocolos de entrada y salida no cumplen los requisitos anteriores, surgen los fallos clásicos de la programación concurrente:

Condición de carrera (Data Race): Ocurre cuando dos o más procesos leen y escriben en memoria compartida sin sincronización, haciendo que el resultado final dependa del orden de intercalación.
Interbloqueo (Deadlock): Ocurre cuando dos o más procesos quedan bloqueados mutuamente esperando recursos que el otro posee, impidiendo todo progreso.
Inanición (Starvation): Ocurre cuando un proceso nunca logra acceder a la sección crítica porque el sistema otorga sistemáticamente prioridad a otros procesos.

Ejercicio de clase: Requisitos de Dijkstra

A continuación se presentan cuatro escenarios defectuosos. Identifica qué requisito de Dijkstra o propiedad fundamental se viola en cada uno:

Dos procesos entran simultáneamente en la sección crítica porque leen una variable de control con valor False al mismo tiempo.
Un proceso $P_0$ quiere entrar en la sección crítica, pero debe esperar a que $P_1$ entre primero; si $P_1$ nunca desea entrar, $P_0$ queda bloqueado indefinidamente.
Un proceso $P_2$ solicita entrar a la sección crítica, pero el algoritmo siempre da paso a $P_0$ y $P_1$ , por lo que $P_2$ nunca consigue acceder.
Un protocolo de sincronización funciona correctamente en la CPU del laboratorio, pero al ejecutarse en un procesador más rápido falla porque uno de los hilos adelanta al otro.

Serialización de procesos

La serialización (o condición de sincronización) consiste en imponer un orden temporal específico en la ejecución de hilos o procesos concurrentes, garantizando que una operación solo se ejecute cuando el sistema se encuentre en un estado determinado.

A diferencia de la exclusión mutua (que evita accesos simultáneos a un recurso), la serialización asegura que las operaciones ocurran en la secuencia lógica adecuada.
Si la condición no se cumple, el proceso solicitante debe esperar a que otro proceso modifique el estado.

Ejemplo intuitivo: Productor / Consumidor

El productor deposita elementos en un buffer compartido. Si el buffer está lleno, debe esperar a que haya espacio.

El consumidor extrae elementos del buffer. Si el buffer está vacío, debe esperar a que el productor inserte al menos un elemento.

Ejercicio de clase: Exclusión mutua vs. Serialización

Determina si en cada uno de los siguientes escenarios se requiere exclusión mutua, serialización, ambas o ninguna:

Dos hilos incrementan de forma concurrente una variable global counter.
Varios usuarios envían trabajos a una única impresora.
Un proceso productor quiere insertar un dato en un buffer que está lleno.
Un proceso consumidor quiere extraer un dato de un buffer que está vacío.
Un sistema de base de datos permite lecturas concurrentes de una tabla, pero solo una escritura a la vez.
Dos hilos leen simultáneamente una constante global que jamás se modifica.
Una aplicación de vídeo debe esperar a que se hayan descargado los primeros frames al buffer antes de comenzar la reproducción.
Distintas taquillas de un cine venden entradas para la misma sala desde terminales independientes.

Mecanismos y soluciones clásicas

1. Soluciones basadas en hardware puro (inhibición de interrupciones)

En sistemas monoprocesador, el sistema operativo conmuta de proceso al recibir una interrupción del reloj.
Idea: Deshabilitar las interrupciones del reloj de la CPU al entrar a la sección crítica (CLI en x86) y rehabilitarlas al salir (STI).
Limitaciones y peligros:
- ¿Qué ocurre si se permite a un proceso de usuario deshabilitar las interrupciones y entra en un bucle infinito? (El sistema completo se congela, ya que el sistema operativo pierde el control del procesador).
- ¿Funciona en sistemas multiprocesador (multicore)? (No. Deshabilitar las interrupciones en un núcleo no impide que los demás núcleos sigan ejecutando código y accediendo a la memoria RAM en paralelo).

2. Soluciones basadas en memoria compartida

Espera ocupada por exclusión mutua (busy waiting)

La espera ocupada (o espera activa) consiste en que un hilo ejecuta repetidamente un bucle comprobando el valor de una variable compartida en memoria RAM hasta que la condición se cumple.

Ventaja: Sencillez conceptual y baja latencia si el tiempo de espera es extremadamente corto.
Inconveniente principal: Consume el 100% de un núcleo de CPU haciendo trabajo nulo, desperdiciando energía y degradando el rendimiento global del sistema.

Las soluciones en memoria compartida mediante espera ocupada se dividen según el soporte de memoria asumido:

Basadas en software puro (solo load y store atómicos): No requieren instrucciones atómicas especiales del hardware. La sincronización se logra por la lógica de las variables de estado.
Con soporte de instrucciones atómicas de hardware (RMW): La CPU proporciona instrucciones atómicas especializadas que leen y escriben en memoria RAM de forma indivisible (xchg, test_and_set, compare_and_swap) para construir Spinlocks.

Intentos básicos basados en software (2 procesos)

Primer intento: Alternancia estricta (`turn`)

turn = 0

def proceso0():
    global turn
    while turn != 0:
        pass   # Espera ocupada
    critical_section()
    turn = 1

def proceso1():
    global turn
    while turn != 1:
        pass   # Espera ocupada
    critical_section()
    turn = 0

Ejercicio de clase: Análisis del primer intento

Si el proceso $P_0$ ejecuta su sección crítica y sale asignando turn = 1, pero $P_1$ no desea entrar a su sección crítica, ¿qué ocurre si $P_0$ necesita volver a acceder a la sección crítica?
¿Qué requisito fundamental de Dijkstra o propiedad de los protocolos de exclusión mutua se viola en este diseño?

Segundo intento: Declaración de intención (`states`)

states = [False, False]

def proceso0():
    while states[1]:
        pass
    states[0] = True
    critical_section()
    states[0] = False

def proceso1():
    while states[0]:
        pass
    states[1] = True
    critical_section()
    states[1] = False

Ejercicio de clase: Análisis del segundo intento

Considere una ejecución entrelazada en la que $P_0$ y $P_1$ evalúan la condición del bucle while exactamente antes de que ninguno modifique su variable en states. ¿Qué valor leerá cada uno?
¿Qué propiedad de la sincronización se viola en este escenario?

Tercer intento: Marcado previo de intención

states = [False, False]

def proceso0():
    states[0] = True
    while states[1]:
        pass
    critical_section()
    states[0] = False

def proceso1():
    states[1] = True
    while states[0]:
        pass
    critical_section()
    states[1] = False

Ejercicio de clase: Análisis del tercer intento

Si $P_0$ ejecuta states[0] = True y $P_1$ ejecuta states[1] = True casi de forma simultánea antes de que ninguno comience su bucle while, ¿cuál es el estado resultante del sistema?
Construye la traza de ejecución de instrucciones que demuestre a qué tipo de fallo conduce esta situación.

Cuarto intento: Retirada de intención

states = [False, False]

def proceso0():
    states[0] = True
    while states[1]:
        states[0] = False
        states[0] = True
    critical_section()
    states[0] = False

def proceso1():
    states[1] = True
    while states[0]:
        states[1] = False
        states[1] = True
    critical_section()
    states[1] = False

Ejercicio de clase: Análisis del cuarto intento

Para solucionar el bloqueo del tercer intento, este protocolo retira temporalmente la declaración de intención (states[i] = False) dentro del bucle. ¿Qué ocurre si ambos procesos ejecutan este protocolo en estricta sincronía paso a paso?
¿Los procesos están suspendidos o están consumiendo CPU? ¿Cómo se denomina este problema de sincronización?

Algoritmo de Dekker (1963)

Fue la primera solución de software totalmente correcta para dos procesos. Combina la declaración de intención (cs_ready) con una variable de desempate (turn).

cs_ready = [False, False]
turn = 0

def proceso0():
    cs_ready[0] = True
    while cs_ready[1]:
        if turn == 1:
            cs_ready[0] = False
            while turn != 0:
                pass
            cs_ready[0] = True
            
    critical_section()
    cs_ready[0] = False
    turn = 1

def proceso1():
    cs_ready[1] = True
    while cs_ready[0]:
        if turn == 0:
            cs_ready[1] = False
            while turn != 1:
                pass
            cs_ready[1] = True
            
    critical_section()
    cs_ready[1] = False
    turn = 0

Propiedades: Garantiza exclusión mutua, progreso y espera limitada.
Inconveniente: Es complejo, difícil de analizar y no escala fácilmente para más de 2 procesos.

Ejercicio de clase: Algoritmo de Dekker

¿Qué función cumple la variable turn en el algoritmo de Dekker cuando ambos procesos quieren acceder al mismo tiempo?
¿Por qué resulta extremadamente complicado extender el algoritmo de Dekker a $N$ procesos?

Algoritmo de Peterson (1981)

Simplifica notablemente el algoritmo de Dekker invirtiendo el orden de asignación del turno: cada proceso que desea entrar declara su intención y cede cortésmente el turno al otro proceso.

cs_ready = [False, False]
turn = 0

def proceso0():
    cs_ready[0] = True
    turn = 1  # Cede el turno a P1
    while cs_ready[1] and turn == 1:
        pass  # Espera activa si P1 también quiere entrar y tiene el turno
    
    critical_section()
    cs_ready[0] = False

def proceso1():
    cs_ready[1] = True
    turn = 0  # Cede el turno a P0
    while cs_ready[0] and turn == 0:
        pass  # Espera activa si P0 también quiere entrar y tiene el turno
    
    critical_section()
    cs_ready[1] = False

Código fuente multilenguaje del Algoritmo de Peterson

Puedes consultar y ejecutar las implementaciones completas del algoritmo de Peterson en distintos lenguajes en la carpeta de código:

peterson.py (Python con threading)
peterson.c (C con POSIX Threads)
Peterson.java (Java con Thread)
peterson.rs (Rust con thread::spawn)

Algoritmo de Hyman

Hyman intentó simplificar el algoritmo de Peterson cambiando el orden de comprobación de las variables de estado y turno:

states = [False, False]
turn = 0

def proceso0():
    states[0] = True
    while turn != 0:
        while states[1]:
            pass
        turn = 0

    critical_section()
    states[0] = False

def proceso1():
    states[1] = True
    while turn != 1:
        while states[0]:
            pass
        turn = 1

    critical_section()
    states[1] = False

Ejercicio de clase: Análisis del algoritmo de Hyman

Analiza el flujo de control del algoritmo de Hyman cuando un proceso comprueba que el rival no ha declarado intención en ese preciso instante y procede a asignarse el turno a sí mismo.
Encuentra una intercalación de instrucciones entre $P_0$ y $P_1$ que demuestre por qué este algoritmo es incorrecto y viola la exclusión mutua.

Algoritmo de Lamport (Algoritmo de la Panadería)

Diseñado por Leslie Lamport para solucionar el problema de exclusión mutua para $N$ procesos. Se basa en el sistema de turnos de una panadería: cada proceso obtiene un número de turno y accede en orden creciente.

choosing = [False] * N
number = [0] * N

def proceso_i(i):
    # 1. Tomar turno
    choosing[i] = True
    number[i] = 1 + max(number)
    choosing[i] = False
    
    # 2. Esperar a los procesos con prioridad
    for j in range(N):
        while choosing[j]:
            pass  # Esperar si el proceso j está calculando su número
        while (number[j] > 0) and ((number[j] < number[i]) or (number[j] == number[i] and j < i)):
            pass  # Esperar si el proceso j tiene un número menor (o mismo número y menor ID)
            
    # 3. Sección crítica
    critical_section()
    
    # 4. Salida
    number[i] = 0

Ventajas: Funciona para $N$ procesos y no requiere operaciones atómicas de hardware complejas (RMW), ya que cada proceso únicamente escribe en su propia variable (number[i] y choosing[i]) y solo realiza lecturas sobre las variables de los demás.
Inconveniente: El valor de number puede crecer de forma indefinida en ejecuciones muy largas si no se reinicia el sistema.

Ejercicio de clase: Desempates en el Algoritmo de Lamport

¿Qué ocurre si dos o más procesos calculan el valor 1 + max(number) simultáneamente y obtienen exactamente el mismo número de ticket (number[i] == number[j])? ¿Se viola la exclusión mutua?
¿Por qué se dice que el algoritmo de la panadería no requiere soporte atómico especial por parte del hardware?

Instrucciones atómicas complejas (RMW) en memoria compartida

En los procesadores multicore modernos, los algoritmos basados en solo load y store (como Peterson o Lamport) resultan ineficientes y sufren problemas por el reordenamiento de instrucciones en la CPU y el compilador.

En la práctica, se utilizan primitivas hardware RMW (Read-Modify-Write) que ejecutan de forma atómica en el bus de memoria las operaciones de lectura y modificación:

1. Exchange (`xchg`)

Escribe un nuevo valor en una posición de memoria y devuelve atómicamente el valor anterior que contenía dicha posición:

// Lógica atómica equivalente ejecutada por la CPU:
int xchg(int *ptr, int new_val) {
    int old_val = *ptr;  // 1. Lee el valor antiguo
    *ptr = new_val;      // 2. Escribe el nuevo valor
    return old_val;      // 3. Devuelve el valor antiguo
}

// Uso en un Spinlock (0 = libre, 1 = ocupado):
while (xchg(&lock, 1) == 1) { 
    /* Spin: si lock valía 1, asigna 1 y devuelve 1 (repite bucle).
       Si lock valía 0, asigna 1 y devuelve 0 (sale del bucle y entra). */ 
}

critical_section();

lock = 0; // O xchg(&lock, 0)

2. Test-And-Set (`TAS`)

Escribe true en una variable booleana de memoria y devuelve atómicamente el valor anterior:

// Lógica atómica equivalente:
bool test_and_set(bool *ptr) {
    bool old_val = *ptr;
    *ptr = true;
    return old_val;
}

// Uso en un Spinlock:
while (test_and_set(&lock)) { 
    /* Spin mientras lock valga true */ 
}

critical_section();

lock = false;

3. Compare-And-Swap (`CAS`)

Compara el valor de una posición de memoria *ptr con un valor esperado (expected). Si coinciden, modifica *ptr asignándole new_val. En cualquier caso, devuelve atómicamente el valor anterior que había en memoria:

// Lógica atómica equivalente:
int compare_and_swap(int *ptr, int expected, int new_val) {
    int old_val = *ptr;
    if (old_val == expected) {
        *ptr = new_val; // Solo modifica si *ptr coincide con expected
    }
    return old_val; // Devuelve siempre el valor previo en memoria
}

// Uso en un Spinlock (esperamos 0 para cambiarlo a 1):
while (compare_and_swap(&lock, 0, 1) != 0) { 
    /* Spin: si lock era 0 (libre), lo cambia a 1 y devuelve 0 (sale del bucle).
       Si lock era 1 (ocupado), no modifica nada y devuelve 1 (repite el bucle). */ 
}

critical_section();

lock = 0;

Ejercicio de clase: Comparativa de primitivas atómicas (RMW)

¿Qué diferencia clave existe entre una instrucción atómica Test-And-Set y una instrucción Compare-And-Swap (CAS), y por qué CAS se utiliza ampliamente para construir estructuras de datos libres de bloqueos (lock-free)?

Conclusiones

Limitaciones de la espera activa: Aunque satisface la exclusión mutua, malgasta ciclos de CPU en bucles giratorios (spinning).
Fragilidad del código: Las soluciones por software puro son complejas, difíciles de verificar y se quiebran ante las optimizaciones de los compiladores modernos y los modelos de memoria relajados de la CPU.
Evolución hacia primitivas de alto nivel: Para solucionar estas deficiencias, en los siguientes temas se estudiarán primitivas de sincronización basadas en bloqueo del hilo gestionadas por el sistema operativo, como semáforos, mutadores (mutex), variables de condición y monitores.

Anexo: memoria compartida en Unix / System V

En sistemas operativos reales tipo POSIX/Linux, las variables globales no son compartidas automáticamente entre procesos independientes creados con fork(). Se requiere solicitar segmentos de memoria compartida al kernel (mediante llamadas shmget/shmat en System V o mmap en POSIX).

Ejemplos prácticos en la carpeta de código:

indeterminismo.c: Demostración de condición de carrera sobre memoria compartida System V.
Decker_con_procesos.c: Implementación funcional del algoritmo de Dekker entre procesos fork() usando System V.
counter_peterson.c: Algoritmo de Peterson en C utilizando barreras de memoria del compilador GCC (__sync_synchronize()).
exchange.c: Ejemplo de uso de ensamblador en línea en C con la instrucción xchg.

Aclaraciones

Nota sobre la bibliografía

En ningún caso estas transparencias o notas constituyen por sí solas la totalidad de la bibliografía de la asignatura. Debes estudiar, complementar y profundizar los conceptos utilizando la bibliografía recomendada en la guía docente y el material de la web de la asignatura.

Introducción y conceptos básicos​

Problemas de sincronización entre procesos​

Tipos de sincronización​

Exclusión mutua​

Definición​

Protocolos de entrada y salida​

Requisitos de Dijkstra​

Variantes de la exclusión mutua​

Problemas derivados​

Serialización de procesos​

Mecanismos y soluciones clásicas​

1. Soluciones basadas en hardware puro (inhibición de interrupciones)​

2. Soluciones basadas en memoria compartida​

Espera ocupada por exclusión mutua (busy waiting)​

Intentos básicos basados en software (2 procesos)​

Primer intento: Alternancia estricta (turn)​

Segundo intento: Declaración de intención (states)​

Tercer intento: Marcado previo de intención​

Cuarto intento: Retirada de intención​

Algoritmo de Dekker (1963)​

Algoritmo de Peterson (1981)​

Algoritmo de Hyman​

Algoritmo de Lamport (Algoritmo de la Panadería)​

Instrucciones atómicas complejas (RMW) en memoria compartida​

1. Exchange (xchg)​

2. Test-And-Set (TAS)​

3. Compare-And-Swap (CAS)​

Conclusiones​

Anexo: memoria compartida en Unix / System V​

Ejemplos prácticos en la carpeta de código:​

Aclaraciones​