Tema 4: Semáforos y mecanismos de sincronización

Motivación

En la sesión anterior comprobamos que resolver la concurrencia exclusivamente mediante espera ocupada (o espera activa) en software puro presenta graves limitaciones:

Ineficiencia en el uso de la CPU: Los procesos atrapados en bucles de sondeo continuo (spinning) consumen el 100% de los ciclos de procesador sin realizar trabajo útil.
Complejidad y acoplamiento: Los algoritmos puramente basados en variables compartidas (Dekker, Peterson, Lamport) resultan difíciles de razonar, altamente acoplados y propensos a condiciones de carrera sutiles en arquitecturas multicore con reordenamiento de memoria.
Falta de escalabilidad: No separan adecuadamente las variables de cómputo de la lógica de sincronización, volviéndose inviables en aplicaciones de gran escala.

Para solucionar estos problemas, surgen los semáforos, introducidos por Edsger Dijkstra en 1965:

Sustituyen la espera activa por una espera bloqueante: cuando un proceso no puede continuar, el sistema operativo suspende su ejecución, cede la CPU a otros procesos listos y solo lo despierta cuando el recurso queda libre.
Proporcionan señales simples y estructuradas capaces de coordinar cualquier esquema de exclusión mutua o sincronización por eventos.

Problemas inherentes a la programación concurrente

Los semáforos permiten abordar con rigor los dos grandes desafíos de la concurrencia:

Exclusión mutua: Garantizar que únicamente un proceso o hilo ejecute una sección crítica en un instante determinado.
Sincronización: Forzar a un proceso a detenerse y esperar a que ocurra un evento o cambie el estado del sistema (serialización).

Definición de semáforo

Un semáforo es un Tipo Abstracto de Datos (TAD) gestionado por el sistema operativo que consta de dos componentes fundamentales:

Una variable entera no negativa (value), que representa los permisos o unidades disponibles del recurso.
Una cola de procesos bloqueados (queue), donde esperan los procesos que intentaron adquirir el semáforo cuando no había permisos.

struct Semaphore {
    unsigned int value;
    Queue queue;
};

Históricamente, los semáforos fueron inventados por Edsger W. Dijkstra (1965) y se utilizaron formalmente en el sistema multiprogramado THE (1968) y en sistemas operativos comerciales tempranos como THEOS.

Operaciones sobre semáforos

Un semáforo solo puede ser manipulado mediante dos operaciones atómicas fundamentales:

Wait (denominada históricamente P, del holandés proberen te verlagen, «intentar decrementar»; también conocida como acquire, down o lock): Decrementa el contador si es mayor que cero. Si es cero, suspende el proceso invocador y lo introduce en la cola del semáforo.
```
def wait(s):
    if s.value > 0:
        s.value -= 1
    else:
        add(current_process, s.queue)
        block(current_process)
```
Signal (denominada históricamente V, del holandés verhogen, «incrementar»; también conocida como release, up o post): Si hay procesos en espera en la cola, extrae uno y lo pasa a estado listo. Si la cola está vacía, incrementa el contador de permisos.
```
def signal(s):
    if empty(s.queue):
        s.value += 1
    else:
        process = get(s.queue)
        sched(process)
```

Semántica de paso de testigo (baton passing)

Nótese que en la definición clásica de Dijkstra con cola explícita, si hay procesos esperando en la cola, signal() no incrementa s.value; en su lugar, transfiere el permiso de ejecución directamente al proceso que despierta. El valor del semáforo solo se incrementa cuando ningún proceso está esperando.

Ejercicio de clase: Atomicidad de wait y signal

Para implementar los semáforos en el kernel se requiere utilizar mecanismos de bajo nivel para acceder a sus variables internas (value y queue). ¿Por qué estas dos funciones completas constituyen en sí mismas una sección crítica?
¿Por qué el uso de instrucciones atómicas de hardware (spinlocks a nivel de kernel) para proteger wait() y signal() es aceptable y no sufre de los inconvenientes de la espera activa prolongada?

Otras operaciones de semáforos

Dependiendo del lenguaje o sistema operativo, las bibliotecas proporcionan extensiones:

Lectura del valor: Consultar el contador actual (ej. sem_getvalue() en POSIX).
Espera no bloqueante (try_wait): Intenta decrementar el semáforo y retorna inmediatamente con un código de error (como EAGAIN) si el recurso está ocupado, sin suspender el hilo.
Espera con límite de tiempo (timed_wait): Bloquea el hilo como máximo durante un intervalo de tiempo especificado.

Exclusión mutua con semáforos

Para garantizar exclusión mutua sobre una sección crítica compartida, se utiliza un semáforo inicializado a 1, denominado habitualmente semáforo binario o mutex:

mutex = Semaphore(1)

# Código del proceso / hilo
mutex.wait()
# --- Sección Crítica ---
mutex.signal()

Primer proceso: Encuentra mutex.value == 1, lo decrementa a 0 y accede inmediatamente a la sección crítica.
Procesos concurrentes: Encuentran mutex.value == 0, se suspenden y quedan encolados en mutex.queue sin consumir CPU.
Salida: Cuando el primer proceso ejecuta mutex.signal(), el siguiente proceso encolado es despertado y pasa a ejecutar la sección crítica.

Implementaciones en distintos lenguajes

Ejemplo en C con semáforos POSIX anónimos (semaphore.c)

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <semaphore.h>

#define NUM_THREADS 4
#define MAX_COUNT 10000000

struct tdata {
    int tid;
};

int counter = 0;
sem_t mutex; // Semáforo POSIX no nominal

void *count(void *ptr) {
    long i, max = MAX_COUNT / NUM_THREADS;
    int tid = ((struct tdata *) ptr)->tid;

    for (i = 0; i < max; i++) {
        sem_wait(&mutex);
        counter += 1;
        sem_post(&mutex);
    }
    printf("Fin hilo %d, counter acumulado: %d\n", tid, counter);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t threads[NUM_THREADS];
    struct tdata id[NUM_THREADS];

    sem_init(&mutex, 0, 1); // Inicializado a 1 para exclusión mutua
    for (int i = 0; i < NUM_THREADS; i++) {
        id[i].tid = i;
        pthread_create(&threads[i], NULL, count, (void *) &id[i]);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    sem_destroy(&mutex);
    printf("Counter value: %d Expected: %d\n", counter, MAX_COUNT);
    return 0;
}

Código fuente disponible en semaphore.c.

Salida de ejecución en terminal (Linux / POSIX):

$ gcc -o semaphore semaphore.c -lpthread && ./semaphore
Fin hilo 0, counter acumulado: 2500000
Fin hilo 1, counter acumulado: 5000000
Fin hilo 2, counter acumulado: 7500000
Fin hilo 3, counter acumulado: 10000000
Counter value: 10000000 Expected: 10000000

Ejemplo en Python con threading.Semaphore (semaphore.py)

import threading

THREADS = 4
MAX_COUNT = 1000000

mutex = threading.Semaphore(1)
counter = 0

def thread():
    global counter
    print("Thread {}".format(threading.current_thread().name))
    for i in range(MAX_COUNT // THREADS):
        mutex.acquire()
        counter += 1
        mutex.release()

def main():
    threads = []
    for i in range(THREADS):
        t = threading.Thread(target=thread)
        threads.append(t)
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    print("Counter value: %d Expected: %d" % (counter, MAX_COUNT))

if __name__ == "__main__":
    main()

Código fuente disponible en semaphore.py.

Salida de ejecución en terminal:

$ python3 semaphore.py
Thread Thread-1 (thread)
Thread Thread-2 (thread)
Thread Thread-3 (thread)
Thread Thread-4 (thread)
Counter value: 1000000 Expected: 1000000

Java: Proporciona la clase java.util.concurrent.Semaphore. No obstante, para exclusión mutua pura en Java se prefieren mecanismos nativos de más alto nivel como los bloques synchronized o ReentrantLock.
Rust: La biblioteca estándar de Rust no incluye semáforos generales en std::sync, ya que favorece el modelo de propiedad (ownership) mediante Mutex<T> y RwLock<T>. Para semáforos contadores en Rust se emplean bibliotecas externas como tokio::sync::Semaphore.

Ejercicio de clase: Traza de semáforo binario

Dibuja la traza temporal de dos procesos $P_0$ y $P_1$ que intentan acceder concurrentemente a una sección crítica protegida por un semáforo binario $S=1$ . Indica el valor del contador, el estado de la cola y qué proceso está en ejecución en cada paso.

Cerrojos o mutexes

Aunque un semáforo binario sirve para resolver la exclusión mutua, en la práctica se emplean abstracciones especializadas: los cerrojos o mutexes (Mutual Exclusion locks).

Un mutex difiere de un semáforo binario en dos aspectos cruciales:

Concepto de propiedad (ownership):
- En un mutex, el hilo que ejecuta lock() adquiere la propiedad del cerrojo. Únicamente dicho hilo puede y debe ejecutar unlock(). Si otro hilo intenta liberar el mutex, se genera un error (EPERM en POSIX).
- En un semáforo, no existe dueño. Cualquier hilo puede ejecutar signal(), motivo por el cual los semáforos sirven como señalización de eventos entre hilos distintos y los mutexes no.
Inversión de prioridad (Priority Inversion):
- Dado que el kernel conoce al hilo propietario de un mutex, puede implementar protocolos de herencia de prioridad (Priority Inheritance Protocol), elevando la prioridad del hilo bloqueante para evitar que hilos intermedios lo retrasen indefinidamente. Con semáforos generales esto es imposible.
Reentrada:
- Algunos mutexes son reentrantes (o recursivos): permiten que el mismo hilo vuelva a adquirir el cerrojo múltiples veces consecutivas sin auto-bloquearse (ej. llamadas recursivas), requiriendo el mismo número de unlock() para quedar libre.

Uso de cerrojos (mutexes)

mutex = Lock()

mutex.lock()
# --- Sección Crítica ---
mutex.unlock()

C: pthread_mutex_t en POSIX Threads (ver mutex.c).
Python: threading.Lock (no reentrante) y threading.RLock (reentrante). Admite la sintaxis with mutex: para garantizar la liberación automática incluso ante excepciones (ver lock.py y lock_with.py).
C++: std::mutex, std::unique_lock y std::lock_guard con soporte de RAII.
Rust: std::sync::Mutex, donde el cerrojo envuelve directamente a los datos compartidos (Mutex<T>), impidiendo el acceso a los datos sin haber adquirido previamente el cerrojo en tiempo de compilación.

Ejemplo en C con POSIX Mutex (mutex.c)

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define NUM_THREADS 4
#define MAX_COUNT 10000000

struct tdata {
    int tid;
};

int counter = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void *count(void *ptr) {
    long i, max = MAX_COUNT / NUM_THREADS;
    int tid = ((struct tdata *) ptr)->tid;

    for (i = 0; i < max; i++) {
        pthread_mutex_lock(&mutex);
        counter += 1;
        pthread_mutex_unlock(&mutex);
    }
    printf("End %d counter: %d\n", tid, counter);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t threads[NUM_THREADS];
    struct tdata id[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
        id[i].tid = i;
        pthread_create(&threads[i], NULL, count, (void *) &id[i]);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    pthread_mutex_destroy(&mutex);
    printf("Counter value: %d Expected: %d\n", counter, MAX_COUNT);
    return 0;
}

Código fuente disponible en mutex.c.

Salida de ejecución en terminal:

$ gcc -o mutex mutex.c -lpthread && ./mutex
End 3 counter: 9533850
End 2 counter: 9703085
End 1 counter: 9727720
End 0 counter: 10000000
Counter value: 10000000 Expected: 10000000

Ejemplo en Python con threading.Lock y with (lock_with.py)

import threading

THREADS = 4
MAX_COUNT = 1000000

mutex = threading.Lock()
counter = 0

def thread():
    global counter
    print("Thread {}".format(threading.current_thread().name))
    for i in range(MAX_COUNT // THREADS):
        with mutex:
            counter += 1

def main():
    threads = []
    for i in range(THREADS):
        t = threading.Thread(target=thread)
        threads.append(t)
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    print("Counter value: %d Expected: %d" % (counter, MAX_COUNT))

if __name__ == "__main__":
    main()

Código fuente disponible en lock_with.py.

Salida de ejecución en terminal:

$ python3 lock_with.py
Thread Thread-1 (thread)
Thread Thread-2 (thread)
Thread Thread-3 (thread)
Thread Thread-4 (thread)
Counter value: 1000000 Expected: 1000000

Ejercicio de clase: Transferencia bancaria y Deadlock de Mutex

Supongamos la siguiente función de transferencia entre dos cuentas bancarias:

def transfer(account_a, account_b, amount):
    if account_a.balance >= amount:
        account_a.balance -= amount
        account_b.balance += amount

¿Cuáles son las secciones críticas y qué variables deben protegerse?
Si asignamos un mutex independiente a cada cuenta (account.lock), ¿qué problema de interbloqueo ocurre si se ejecutan simultáneamente transfer(cuenta1, cuenta2, 50) y transfer(cuenta2, cuenta1, 30)?
¿Cómo resolverías este interbloqueo mediante una ordenación global de recursos?

Mutexes en POSIX (pthread_mutex)

En C bajo sistemas UNIX/Linux, la biblioteca pthread proporciona el estándar de mutexes para hilos:

#include <pthread.h>

// Inicialización estática con atributos por defecto
pthread_mutex_t candado = PTHREAD_MUTEX_INITIALIZER;

// Operaciones principales
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);
int pthread_mutex_lock(pthread_mutex_t *mutex);    // Bloquea o duerme si está ocupado
int pthread_mutex_trylock(pthread_mutex_t *mutex); // Retorna inmediatamente sin bloquear
int pthread_mutex_unlock(pthread_mutex_t *mutex);  // Libera el cerrojo

Sincronización con semáforos

Además de la exclusión mutua, los semáforos generales (o semáforos contadores) permiten modelar la disponibilidad de recursos múltiples y la sincronización por eventos:

El valor inicial $K$ del semáforo indica el número de recursos compartidos disponibles o el número de procesos que pueden acceder en paralelo (patrón conocido como multiplex).
Cada llamada a wait() consume un recurso. Cuando el contador llega a 0, las siguientes llamadas se bloquean.
Cada llamada a signal() repone un recurso o despierta a un proceso en espera.

Algoritmo de Barz

El Algoritmo de Barz demuestra que es teóricamente posible implementar un semáforo general contador de valor arbitrario $K$ utilizando únicamente semáforos binarios y una variable entera compartida:

mutex = BinarySemaphore(1)  # Protege la variable value
gate = BinarySemaphore(1)   # Puerta de paso que bloquea cuando value == 0
value = K                   # Contador de permisos disponibles

def general_wait():
    gate.wait()             # Si value era 0 o hay otro hilo esperando, se bloquea aquí
    mutex.wait()            # Exclusión mutua para decrementar
    value -= 1
    if value > 0:
        gate.signal()       # Si aún quedan permisos, reabre la puerta al siguiente
    mutex.signal()

def general_signal():
    mutex.wait()            # Exclusión mutua para incrementar
    value += 1
    if value == 1:
        gate.signal()       # El semáforo pasa de 0 a 1: abre la puerta bloqueada
    mutex.signal()

gate permanece cerrado cuando value == 0, obligando a los nuevos procesos a esperar.
En general_signal(), solo cuando value transiciona de 0 a 1 se ejecuta gate.signal(), permitiendo que el primer proceso bloqueado en gate prosiga.

Condiciones de sincronización

Un semáforo inicializado a 0 sirve como señal de sincronización unilateral: un proceso se detiene en wait() hasta que otro proceso ejecuta signal().

Ejercicio de clase: Un proceso espera a otro

El proceso $Q$ no puede ejecutar su instrucción $Q_2$ hasta que el proceso $P$ haya completado $P_1$ :

Proceso P        Proceso Q
...              ...
P1               Q1
P2               Q2
...              ...

¿Cómo utilizarías semáforos para garantizar este orden de ejecución?

Ejercicio de clase: Encuentro bidireccional

Los procesos $P$ y $Q$ deben sincronizarse en un punto de encuentro: ninguno puede pasar a la siguiente fase hasta que ambos hayan alcanzado dicho punto.

Proceso P               Proceso Q
...                     ...
P1                      Q1
(punto de encuentro)    (punto de encuentro)
P2                      Q2
...                     ...

¿Cómo utilizarías semáforos para resolver este problema? ¿Qué ocurriría si ambos procesos ejecutan la operación wait() antes de la operación signal()?

Ejercicio de clase: Sincronización AND vs. OR

Condición OR: El proceso $Q$ solo puede ejecutar $Q_2$ si el proceso $P$ ha ejecutado $P_1$ o el proceso $R$ ha ejecutado $R_1$ .
Condición AND: El proceso $Q$ solo puede ejecutar $Q_2$ si tanto el proceso $P$ ha ejecutado $P_1$ como el proceso $R$ ha ejecutado $R_1$ .

Proceso P        Proceso Q        Proceso R
...              ...              ...
P1               Q1               R1
P2               Q2               R2
...              ...              ...

Plantea la solución con semáforos para ambos casos. ¿Por qué en la condición AND no basta con un único semáforo si los procesos se ejecutan en un bucle repetitivo?

Barreras de sincronización

Una barrera de sincronización generaliza el concepto de cita a un grupo de $N$ procesos o hilos que operan en fases o etapas sucesivas. Ningún hilo puede iniciar la fase $k+1$ hasta que todos los $N$ hilos hayan finalizado la fase $k$ .

while True:
    do_phase()
    barrier(n)

Implementación de barrera con semáforos

Una barrera reutilizable puede construirse mediante dos fases de torniquete (turnstile) con dos semáforos y un contador:

arrival = Semaphore(1)     # Controla el acceso a la fase de llegada
departure = Semaphore(0)   # Controla la salida hacia la siguiente fase
counter = 0

def barrier(n):
    arrival.wait()
    counter += 1
    if counter < n:
        arrival.signal()   # (1) Permite la entrada del siguiente hilo
    else:
        departure.signal() # (2) El último hilo autoriza el paso de salida

    departure.wait()       # (3) Todos los hilos esperan la salida

    counter -= 1
    if counter > 0:
        departure.signal() # (4) Autoriza la salida del siguiente hilo
    else:
        arrival.signal()   # (5) El último en salir reabre el torniquete de llegada

Implementación completa en Python disponible en barrier.py.

Salida de ejecución en terminal (barrier.py con 10 hilos sincronizados en 20 fases):

$ python3 barrier.py
Start thread Thread-1
Start thread Thread-2
Start thread Thread-3
...
Thread-3 finished phase 0
Thread-7 finished phase 0
Thread-1 finished phase 0
...
Thread-2 finished phase 19
Finished thread Thread-1
Finished thread Thread-2

Tipos e implementaciones de semáforos

Semáforos fuertes y débiles

Según la política de selección del proceso que se despierta cuando se ejecuta signal():

Semáforos fuertes: La cola de procesos bloqueados sigue una disciplina estricta FIFO (First In, First Out). Garantizan equidad (fairness) y previenen totalmente la inanición (starvation).
Semáforos débiles: No garantizan el orden de extracción de los procesos bloqueados (pueden basarse en prioridades o selección no determinista). Son más sencillos de implementar en el kernel, pero pueden provocar inanición si ciertos procesos son postergados indefinidamente.

Semáforos System V

Fueron el mecanismo original de comunicación entre procesos (IPC) en UNIX clásico (junto con colas de mensajes y memoria compartida):

Operan mediante identificadores numéricos y estructuras de conjuntos de semáforos gestionadas por el kernel (semget, semop, semctl).
Resultan engorrosos de programar, consumen estructuras pesadas en el kernel y hoy en día se consideran obsoletos, manteniéndose únicamente por compatibilidad hacia atrás (ver ejemplos sem-1.c y sinSem-1.c).

Semáforos POSIX

El estándar POSIX.1b (1993) reemplazó a System V con una API más ligera, moderna y portable disponible a través de <semaphore.h>:

Existen dos tipos de semáforos POSIX (sem_t):

Semáforos nominales (con nombre):
- Tienen un identificador en el espacio de nombres del sistema de ficheros (habitualmente comenzando con /, como "/p_mutex"). En Linux se exponen en /dev/shm/.
- Permiten la sincronización entre procesos independientes sin relación de parentesco.
- Se abren con sem_open(), se cierran con sem_close() y se eliminan del sistema con sem_unlink().

Ejemplo en C con semáforo nominal POSIX (sem-posix-with-name.c)

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
#include <semaphore.h>

#define PATH "./fichero_compartido"
#define SEM_NAME "/p_mutex"

int main(int argc, char *argv[]) {
    FILE *f;
    sem_t *semaphore;
    const char *msg = (argc > 1) ? argv[1] : "registro_por_defecto";

    semaphore = sem_open(SEM_NAME, O_CREAT, S_IRUSR | S_IWUSR, 1);
    if (semaphore == SEM_FAILED) {
        perror("Error al abrir sem_open");
        return 1;
    }

    sem_wait(semaphore);

    printf("Seccion critica ocupada por proceso %d.\n", getpid());
    printf("Comprueba que el semaforo esta activo (en Linux visible bajo /dev/shm).\n");
    printf("Pulsa [ENTER] para continuar...\n");
    getchar();

    f = fopen(PATH, "a");
    if (f != NULL) {
        fprintf(f, "Proceso %d: %s\n", getpid(), msg);
        fclose(f);
    }

    sem_post(semaphore);
    sem_close(semaphore);
    sem_unlink(SEM_NAME);

    printf("Proceso %d ha liberado el semaforo y finalizado.\n", getpid());
    return 0;
}

Código fuente disponible en sem-posix-with-name.c.

Salida de ejecución en terminal:

$ gcc -o sem_with_name sem-posix-with-name.c -lpthread
$ ./sem_with_name "proceso_cliente"
Seccion critica ocupada por proceso 74449.
Comprueba que el semaforo esta activo (en Linux visible bajo /dev/shm).
Pulsa [ENTER] para continuar...

Proceso 74449 ha liberado el semaforo y finalizado.

Semáforos anónimos (no nominales):
- Residen en la memoria del proceso (o en un segmento de memoria compartida).
- Se inicializan con sem_init(sem_t *sem, int pshared, unsigned int value):
  - Si pshared == 0, el semáforo es compartido únicamente entre hilos del mismo proceso.
  - Si pshared != 0, reside en memoria compartida y coordina procesos distintos.
- Se destruyen con sem_destroy(sem_t *sem).

Ejemplo en C con semáforo anónimo POSIX (sem-posix-no-name.c)

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <semaphore.h>

#define NUM_THREADS 4
#define MAX_COUNT 10000000

struct tdata {
    int tid;
};

int counter = 0;
sem_t mutex;

void *count(void *ptr) {
    long i, max = MAX_COUNT / NUM_THREADS;
    int tid = ((struct tdata *) ptr)->tid;

    for (i = 0; i < max; i++) {
        sem_wait(&mutex);
        counter += 1;
        sem_post(&mutex);
    }
    printf("End %d counter: %d (max: %ld)\n", tid, counter, max);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t threads[NUM_THREADS];
    struct tdata id[NUM_THREADS];

    sem_init(&mutex, 0, 1);
    for (int i = 0; i < NUM_THREADS; i++) {
        id[i].tid = i;
        pthread_create(&threads[i], NULL, count, (void *) &id[i]);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    sem_destroy(&mutex);
    printf("Counter value: %d Expected: %d\n", counter, MAX_COUNT);
    return 0;
}

Código fuente disponible en sem-posix-no-name.c.

Salida de ejecución en terminal (Linux / POSIX):

$ gcc -o sem_no_name sem-posix-no-name.c -lpthread && ./sem_no_name
End 0 counter: 2500000 (max: 2500000)
End 1 counter: 5000000 (max: 2500000)
End 2 counter: 7500000 (max: 2500000)
End 3 counter: 10000000 (max: 2500000)
Counter value: 10000000 Expected: 10000000

Semáforos frente a espera ocupada

Característica	Espera ocupada (Spinlocks)	Semáforos (Blocking wait)
Comportamiento en espera	Bucle continuo comprobando una condición en RAM	El kernel suspende el proceso y lo pone en cola
Consumo de CPU	100% de uso de CPU durante la espera	0% de CPU consumida mientras está bloqueado
Espacio de ejecución	Espacio de usuario	Espacio de núcleo (llamada al sistema)
Coste de conmutación	Prácticamente nulo si la espera es inmediata	Sobrecarga de cambio de contexto (context switch)
Escenario óptimo	Secciones críticas extremadamente cortas (nanosegundos, multicore)	Esperas de duración impredecible o prolongada (milisegundos o más)

¿Cuándo usar cada mecanismo?

En sistemas operativos modernos, las primitivas híbridas (como los futexes en Linux) combinan ambas estrategias: intentan un breve giro en espera activa (spinlock) durante unos pocos ciclos; si el recurso no queda libre de inmediato, realizan la llamada al sistema para dormir al hilo en el kernel.

Variables de condición

Una variable de condición (pthread_cond_t en POSIX) permite que un hilo se suspenda a la espera de que se cumpla una condición booleana arbitraria (un predicado) sobre variables compartidas, sin realizar sondeos continuos.

Idea de funcionamiento

Una variable de condición no almacena ningún valor por sí misma; es simplemente una cola de espera asociada obligatoriamente a un mutex:

El hilo adquiere el mutex y comprueba el predicado.
Si la condición no se cumple, invoca cond_wait(&cond, &mutex). De forma completamente atómica, el sistema operativo:
- Libera el mutex (para que otros hilos puedan entrar y modificar las variables compartidas).
- Suspende al hilo y lo encola en la variable de condición.
Cuando otro hilo altera las variables compartidas de forma que el predicado se vuelve verdadero, ejecuta cond_signal(&cond) (despierta a un hilo) o cond_broadcast(&cond) (despierta a todos los hilos en espera).
El hilo que despierta vuelve a adquirir automáticamente el mutex antes de salir de cond_wait(), garantizando que sigue protegido al retomar la ejecución.

// Hilo que espera (consumidor / observador)
pthread_mutex_lock(&mutex);
while (!condicion_valida) {
    pthread_cond_wait(&cond, &mutex);
}
// Sección crítica protegida con la condición satisfecha
pthread_mutex_unlock(&mutex);

// Hilo que modifica el estado (productor / emisor)
pthread_mutex_lock(&mutex);
condicion_valida = true;
pthread_cond_signal(&cond); // O pthread_cond_broadcast(&cond);
pthread_mutex_unlock(&mutex);

¿Por qué es obligatorio comprobar la condición en un bucle while y no en un if?

El uso de while (!condicion) en lugar de if (!condicion) es estrictamente obligatorio por dos motivos:

Despertares espurios (Spurious Wakeups): Las especificaciones de POSIX y arquitecturas de hardware permiten que un hilo despierte de cond_wait() sin que se haya emitido una señal explícita.
Semántica de Mesa: Cuando un hilo emite cond_signal(), el hilo que espera no se ejecuta instantáneamente; se vuelve elegible para el planificador. Antes de que adquiera el mutex y comience a ejecutar, otro hilo podría haberse intercalado, adquirido el mutex y modificado de nuevo la condición a falso. Al evaluar en un bucle while, el hilo verifica de nuevo el predicado antes de continuar.

API POSIX de variables de condición

#include <pthread.h>

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr);
int pthread_cond_destroy(pthread_cond_t *cond);
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);    // Despierta al menos a un hilo en espera
int pthread_cond_broadcast(pthread_cond_t *cond); // Despierta a todos los hilos en espera

Ejemplo en C con variable de condición (condvar1.c)

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdbool.h>

bool condition = false;
pthread_cond_t condv = PTHREAD_COND_INITIALIZER;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* worker_thread(void* arg) {
    pthread_mutex_lock(&mutex);
    while (!condition) {
        printf("ESPERANDO CONDICION (condition == TRUE)\n");
        pthread_cond_wait(&condv, &mutex);
    }
    pthread_mutex_unlock(&mutex);

    printf("La condición se ha cumplido, por lo que el hilo puede continuar.\n");
    return NULL;
}

int main() {
    pthread_t thread;

    pthread_mutex_lock(&mutex);
    condition = false;
    pthread_mutex_unlock(&mutex);

    pthread_create(&thread, NULL, worker_thread, NULL);

    sleep(1); // Simula trabajo antes de activar la condición

    pthread_mutex_lock(&mutex);
    condition = true;
    pthread_cond_signal(&condv);
    pthread_mutex_unlock(&mutex);

    pthread_join(thread, NULL);
    return 0;
}

Código fuente disponible en condvar1.c.

Salida de ejecución en terminal:

$ gcc -o condvar1 condvar1.c -lpthread && ./condvar1
ESPERANDO CONDICION (condition == TRUE)
La condición se ha cumplido, por lo que el hilo puede continuar.

Ejemplos avanzados adicionales disponibles en condvar2.c y condvar1.rs.

Problemas clásicos de sincronización

Problema del productor-consumidor

Modela la interacción entre procesos que producen elementos y los depositan en un buffer compartido, y procesos consumidores que los extraen.

Requisitos esenciales:

Exclusión mutua: Solo un proceso puede insertar o extraer elementos del buffer al mismo tiempo.
Sincronización:
- El consumidor debe suspenderse si el buffer está vacío.
- El productor debe suspenderse si el buffer está lleno (en buffers acotados).

Buffer infinito

Cuando el buffer tiene capacidad ilimitada, solo es necesario suspender al consumidor cuando no hay elementos:

buffer = Queue()
mutex = Semaphore(1)     # Exclusión mutua sobre la estructura del buffer
not_empty = Semaphore(0) # Señaliza que hay elementos disponibles

# Proceso Productor
while True:
    item = produce_item()
    mutex.wait()
    buffer.append(item)
    mutex.signal()
    not_empty.signal()

# Proceso Consumidor
while True:
    not_empty.wait()     # Espera a que haya elementos disponibles
    mutex.wait()
    item = buffer.pop()
    mutex.signal()
    consume_item(item)

Código disponible en producer-consumer-infinite.py.

Buffer limitado

En un sistema real con un buffer de tamaño finito BUFFER_SIZE, se utiliza un semáforo adicional not_full inicializado a la capacidad máxima:

buffer = Queue()
mutex = Semaphore(1)
not_empty = Semaphore(0)
not_full = Semaphore(BUFFER_SIZE) # Permisos de inserción disponibles

# Proceso Productor
while True:
    item = produce_item()
    not_full.wait()      # Espera si el buffer está lleno
    mutex.wait()
    buffer.append(item)
    mutex.signal()
    not_empty.signal()   # Notifica al consumidor que hay un nuevo elemento

# Proceso Consumidor
while True:
    not_empty.wait()     # Espera si el buffer está vacío
    mutex.wait()
    item = buffer.pop()
    mutex.signal()
    not_full.signal()    # Notifica al productor que hay hueco libre
    consume_item(item)

Código disponible en Python: producer-consumer.py.

Ejemplo en C con buffer circular y semáforos POSIX (buffer-circular-hilos.c)

#include <stdio.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>

#define TAMBUF 8     // Tamaño del búfer circular
#define NUMDATOS 100 // Número de datos a enviar

int buffer[TAMBUF];
int bufin = 0;
int bufout = 0;

pthread_mutex_t buffer_lock = PTHREAD_MUTEX_INITIALIZER;
unsigned long sum = 0;

sem_t hay_datos;
sem_t hay_sitio;

void pon_dato(int item) {
    pthread_mutex_lock(&buffer_lock);
    buffer[bufin] = item;
    bufin = (bufin + 1) % TAMBUF;
    pthread_mutex_unlock(&buffer_lock);
}

void obten_dato(int *itemp) {
    pthread_mutex_lock(&buffer_lock);
    *itemp = buffer[bufout];
    bufout = (bufout + 1) % TAMBUF;
    pthread_mutex_unlock(&buffer_lock);
}

void *productor(void *arg) {
    for (int i = 1; i <= NUMDATOS; i++) {
        sem_wait(&hay_sitio);
        pon_dato(i * i);
        sem_post(&hay_datos);
    }
    pthread_exit(NULL);
}

void *consumidor(void *arg) {
    int midato;
    for (int i = 1; i <= NUMDATOS; i++) {
        sem_wait(&hay_datos);
        obten_dato(&midato);
        sem_post(&hay_sitio);
        sum += midato;
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t tidprod, tidcons;
    unsigned long total = 0;

    for (int i = 1; i <= NUMDATOS; i++) total += i * i;
    printf("El resultado deberia ser %lu\n", total);

    sem_init(&hay_datos, 0, 0);
    sem_init(&hay_sitio, 0, TAMBUF);

    pthread_create(&tidprod, NULL, productor, NULL);
    pthread_create(&tidcons, NULL, consumidor, NULL);

    pthread_join(tidprod, NULL);
    pthread_join(tidcons, NULL);

    sem_destroy(&hay_datos);
    sem_destroy(&hay_sitio);
    pthread_mutex_destroy(&buffer_lock);

    printf("Los hilos produjeron el valor %lu\n", sum);
    return 0;
}

Código fuente disponible en buffer-circular-hilos.c.

Salida de ejecución en terminal (Linux / POSIX):

$ gcc -o buffer-circular-hilos buffer-circular-hilos.c -lpthread && ./buffer-circular-hilos
El resultado deberia ser 338350
Los hilos produjeron el valor 338350

Problema de lectores-escritores

Varios procesos comparten un recurso (fichero o base de datos).

Lectores: Solo inspeccionan los datos. Pueden acceder concurrentemente en número arbitrario.
Escritores: Modifican los datos. Requieren acceso exclusivo (ningún otro escritor ni lector puede coincidir).

Prioridad a la lectura

Los lectores entran libremente mientras no haya un escritor dentro. El primer lector en llegar adquiere el cerrojo del recurso para todos los lectores, y el último en salir lo libera:

readers = 0
mutex_readers = Semaphore(1) # Protege el contador 'readers'
resource_lock = Semaphore(1) # Exclusión mutua sobre el recurso

def writer():
    resource_lock.wait()
    write_database()
    resource_lock.signal()

def reader():
    global readers
    # Entrada de lector
    mutex_readers.wait()
    readers += 1
    if readers == 1:
        resource_lock.wait() # El primer lector bloquea a los escritores
    mutex_readers.signal()

    read_database()

    # Salida de lector
    mutex_readers.wait()
    readers -= 1
    if readers == 0:
        resource_lock.signal() # El último lector libera el cerrojo del recurso
    mutex_readers.signal()

Código en Python: rw_lock.py.

Ejercicio de clase: Inanición de escritores

¿Por qué la solución con prioridad a la lectura puede producir inanición (starvation) indefinida en los procesos escritores?

Prioridad a la escritura

Para evitar que los escritores sufran inanición, se añade un semáforo de torniquete (entry o order) que impide que nuevos lectores entren cuando un escritor desea acceder.

Versión básica

readers = 0
mutex_readers = Semaphore(1)
resource_lock = Semaphore(1)
entry = Semaphore(1)         # Puerta que bloquea la entrada de nuevos lectores

def writer():
    entry.wait()             # Cierra la puerta a nuevos lectores
    resource_lock.wait()     # Espera a que terminen los lectores actuales
    write_database()
    resource_lock.signal()
    entry.signal()           # Reabre la puerta

def reader():
    global readers
    entry.wait()             # Comprueba si hay un escritor esperando
    mutex_readers.wait()
    readers += 1
    if readers == 1:
        resource_lock.wait()
    mutex_readers.signal()
    entry.signal()           # Permite el paso al siguiente

    read_database()

    mutex_readers.wait()
    readers -= 1
    if readers == 0:
        resource_lock.signal()
    mutex_readers.signal()

Código disponible en rw_lock_fair.py.

Versión optimizada

En la versión básica, cada lector debe realizar dos operaciones wait() consecutivas (entry y mutex_readers). En escenarios de alta concurrencia esto degrada el rendimiento. La versión optimizada desacopla los contadores de entrada y salida (readers_in y readers_out), permitiendo a los lectores entrar y salir con mínima contención sobre los semáforos (ver rw_lock_fair_faster.py).

Problema de los filósofos comensales

Cinco filósofos se sientan en una mesa redonda alternando entre pensar y comer. Entre cada dos filósofos adyacentes hay un único palillo (o tenedor), habiendo 5 palillos en total. Para comer arroz, cada filósofo necesita tomar los dos palillos contiguos (izquierdo y derecho).

def philosopher(i):
    while True:
        think()
        pick_forks(i)
        eat()
        release_forks(i)

Solución 1: Exclusión mutua global

Se protege toda la mesa con un único semáforo binario table = Semaphore(1).

Inconveniente: Ineficiente. Si hay 5 filósofos, podrían comer 2 simultáneamente (por ejemplo, el 0 y el 2), pero esta solución reduce la concurrencia a un único comensal a la vez.

Solución 2: Un palillo por filósofo (con interbloqueo)

Se asocia un semáforo binario a cada uno de los 5 palillos:

forks = [Semaphore(1) for _ in range(5)]

def philosopher(i):
    while True:
        think()
        forks[i].wait()           # Toma palillo izquierdo
        forks[(i + 1) % 5].wait() # Toma palillo derecho
        eat()
        forks[i].signal()
        forks[(i + 1) % 5].signal()

Fallo de diseño: Si los 5 filósofos deciden comer a la vez, cada uno toma con éxito su palillo izquierdo (forks[i]). Al intentar tomar el derecho (forks[(i+1)%5]), todos lo encuentran ocupado. El sistema entra en interbloqueo (deadlock) absoluto.
Demostración reproducible en Python: philosophers_deadlock.py.

Salida de ejecución demostrando el interbloqueo (philosophers_deadlock.py):

$ python3 philosophers_deadlock.py
=== Demostración de Deadlock (Espera Circular) en Filósofos ===
Iniciando 5 filósofos que adquieren primero el palillo izquierdo...
Filósofo 0 toma palillo izquierdo (0)...
Filósofo 1 toma palillo izquierdo (1)...
Filósofo 2 toma palillo izquierdo (2)...
Filósofo 3 toma palillo izquierdo (3)...
Filósofo 4 toma palillo izquierdo (4)...
Filósofo 0 intenta tomar palillo derecho (1)...
Filósofo 1 intenta tomar palillo derecho (2)...
Filósofo 2 intenta tomar palillo derecho (3)...
Filósofo 3 intenta tomar palillo derecho (4)...
Filósofo 4 intenta tomar palillo derecho (0)...

[ALERTA DE DEADLOCK] Todos los filósofos tienen su palillo izquierdo y esperan el derecho.
Ninguno puede avanzar ni soltar su palillo (Condiciones de Coffman cumplidas).

Condiciones de Coffman para el interbloqueo

Para que ocurra un interbloqueo deben satisfacerse simultáneamente las cuatro condiciones de Coffman (1971):

Exclusión mutua: Los recursos no son compartibles (un palillo solo puede ser usado por un filósofo a la vez).
Retención y espera (Hold and Wait): Cada filósofo retiene un palillo mientras espera obtener el segundo.
No apropiación (No Preemption): No se puede arrebatar un palillo a un filósofo por la fuerza.
Espera circular (Circular Wait): Existe una cadena cíclica $P_0 \to P_1 \to P_2 \to P_3 \to P_4 \to P_0$ donde cada proceso espera un recurso retenido por el siguiente.

Romper cualquiera de estas cuatro condiciones hace imposible el interbloqueo.

Solución 3: Romper la espera circular (asimetría)

La forma más directa de prevenir el interbloqueo es romper la condición de espera circular rompiendo la simetría de adquisición: obligar a que uno de los filósofos tome los palillos en orden inverso al resto (ej. los filósofos 0 a 3 toman primero el izquierdo y luego el derecho, mientras que el filósofo 4 toma primero el derecho y luego el izquierdo):

def pick_forks(i):
    left = i
    right = (i + 1) % 5
    if i == 4:
        forks[right].wait() # El filósofo 4 invierte el orden
        forks[left].wait()
    else:
        forks[left].wait()  # Los demás toman primero el izquierdo
        forks[right].wait()

Código en Python: philosophers_1.py e implementación en Rust: philo.rs.

Salida de ejecución en terminal (philosophers_1.py):

$ python3 philosophers_1.py
start eat
end eat
start eat
end eat
start eat
start eat
...

Solución 4: Asignación condicional de estado

Se modela el problema como sincronización por estados: cada filósofo puede estar en estado THINKING, HUNGRY o EATING. Un filósofo solo comienza a comer si tiene hambre y ninguno de sus dos vecinos inmediatos está comiendo.

THINKING = 0
HUNGRY = 1
EATING = 2

status = [THINKING] * 5
sync = [Semaphore(0) for _ in range(5)]
mutex = Semaphore(1)

def left(i):
    return (i - 1) % 5

def right(i):
    return (i + 1) % 5

def test(i):
    if status[i] == HUNGRY and status[left(i)] != EATING and status[right(i)] != EATING:
        status[i] = EATING
        sync[i].signal() # Despierta al filósofo para que coma

def pick_forks(i):
    mutex.wait()
    status[i] = HUNGRY
    test(i)
    mutex.signal()
    sync[i].wait()       # Espera hasta que sus vecinos le permitan comer

def release_forks(i):
    mutex.wait()
    status[i] = THINKING
    test(left(i))        # Comprueba si el vecino izquierdo puede comer ahora
    test(right(i))       # Comprueba si el vecino derecho puede comer ahora
    mutex.signal()

Código en Python disponible en philosophers_2.py.

Salida de ejecución en terminal (philosophers_2.py):

$ python3 philosophers_2.py
start eat
start eat
end eat
end eat
start eat
start eat
...

Ejercicio de clase: Inanición en la solución por estados

Aunque la Solución 4 es óptima en concurrencia y libre de interbloqueo, ¿podría un filósofo sufrir inanición si sus dos vecinos alternan sus turnos de comida continuamente? ¿Cómo podría resolverse utilizando colas de prioridad o envejecimiento (aging)?

Ejercicios de autoevaluación

Semáforos vs. Mutex: ¿Por qué un mutex no puede sustituir a un semáforo cuando se requiere coordinar la finalización de una tarea entre dos hilos distintos?
Atomicidad: ¿Por qué la verificación y modificación de s.value en las operaciones wait() y signal() deben realizarse de forma atómica en el kernel?
Semáforos POSIX: ¿En qué situaciones prácticas es obligatorio utilizar semáforos nominales (sem_open) en lugar de semáforos anónimos (sem_init)?
Variables de condición: Explica la interacción atómica entre el mutex y la variable de condición al invocar pthread_cond_wait().
Condiciones de Coffman: Identifica cuál de las cuatro condiciones de Coffman se elimina al limitar a 4 el número de comensales que pueden sentarse simultáneamente a la mesa en el problema de los filósofos.

Código fuente disponible

Todos los ejemplos analizados a lo largo de este tema se encuentran disponibles para su descarga y ejecución directa:

Primitivas de sincronización y exclusión mutua

semaphore.c: Exclusión mutua entre hilos POSIX usando semáforos anónimos (sem_t).
mutex.c: Exclusión mutua entre hilos POSIX usando cerrojos (pthread_mutex_t).
sem-posix-no-name.c: Ejemplo detallado de inicialización y destrucción de semáforos anónimos POSIX.
sem-posix-with-name.c: Sincronización entre procesos independientes usando semáforos nominales (sem_open).
semaphore.py: Exclusión mutua en Python con threading.Semaphore.
lock.py y lock_with.py: Uso de cerrojos explícitos y gestores de contexto with en Python.
barrier.py: Barrera cíclica de sincronización para $N$ hilos.

Variables de condición

condvar1.c: Sincronización de evento básico con pthread_cond_wait() y pthread_cond_signal().
condvar2.c: Coordinación de múltiples hilos trabajadores con variables de condición en C.
condvar1.rs: Variables de condición en Rust con std::sync::Condvar.

Problemas clásicos de concurrencia

producer-consumer.py: Productor-consumidor con buffer acotado en Python.
producer-consumer-infinite.py: Productor-consumidor con buffer no acotado.
buffer-circular-hilos.c: Productor-consumidor en C con buffer circular, semáforos contadores y mutex.
rw_lock.py: Lectores-escritores con prioridad a la lectura.
rw_lock_fair.py: Lectores-escritores con prioridad a la escritura (versión básica).
rw_lock_fair_faster.py: Lectores-escritores optimizado de alto rendimiento.
philosophers_deadlock.py: Demostración reproducible del interbloqueo simétrico en filósofos comensales.
philosophers_1.py: Solución asimétrica rompiendo la espera circular.
philosophers_2.py: Solución óptima condicional basada en estados de los comensales.
philo.rs: Implementación de los filósofos comensales en Rust.

Motivación​

Problemas inherentes a la programación concurrente​

Definición de semáforo​

Operaciones sobre semáforos​

Otras operaciones de semáforos​

Exclusión mutua con semáforos​

Implementaciones en distintos lenguajes​

Cerrojos o mutexes​

Uso de cerrojos (mutexes)​

Mutexes en POSIX (pthread_mutex)​

Sincronización con semáforos​

Algoritmo de Barz​

Condiciones de sincronización​

Barreras de sincronización​

Implementación de barrera con semáforos​

Tipos e implementaciones de semáforos​

Semáforos fuertes y débiles​

Semáforos System V​

Semáforos POSIX​

Semáforos frente a espera ocupada​

Variables de condición​

Idea de funcionamiento​

API POSIX de variables de condición​

Problemas clásicos de sincronización​

Problema del productor-consumidor​

Buffer infinito​

Buffer limitado​

Problema de lectores-escritores​

Prioridad a la lectura​

Prioridad a la escritura​

Versión básica​

Versión optimizada​

Problema de los filósofos comensales​

Solución 1: Exclusión mutua global​

Solución 2: Un palillo por filósofo (con interbloqueo)​

Condiciones de Coffman para el interbloqueo​

Solución 3: Romper la espera circular (asimetría)​

Solución 4: Asignación condicional de estado​

Ejercicios de autoevaluación​

Código fuente disponible​

Primitivas de sincronización y exclusión mutua​

Variables de condición​

Problemas clásicos de concurrencia​

Motivación

Problemas inherentes a la programación concurrente

Definición de semáforo

Operaciones sobre semáforos

Otras operaciones de semáforos

Exclusión mutua con semáforos

Implementaciones en distintos lenguajes

Cerrojos o mutexes

Uso de cerrojos (mutexes)

Mutexes en POSIX (pthread_mutex)

Sincronización con semáforos

Algoritmo de Barz

Condiciones de sincronización

Barreras de sincronización

Implementación de barrera con semáforos

Tipos e implementaciones de semáforos

Semáforos fuertes y débiles

Semáforos System V

Semáforos POSIX

Semáforos frente a espera ocupada

Variables de condición

Idea de funcionamiento

API POSIX de variables de condición

Problemas clásicos de sincronización

Problema del productor-consumidor

Buffer infinito

Buffer limitado

Problema de lectores-escritores

Prioridad a la lectura

Prioridad a la escritura

Versión básica

Versión optimizada

Problema de los filósofos comensales

Solución 1: Exclusión mutua global

Solución 2: Un palillo por filósofo (con interbloqueo)

Condiciones de Coffman para el interbloqueo

Solución 3: Romper la espera circular (asimetría)

Solución 4: Asignación condicional de estado

Ejercicios de autoevaluación

Código fuente disponible

Primitivas de sincronización y exclusión mutua

Variables de condición

Problemas clásicos de concurrencia