Motivación

  • Problemas de la espera ocupada:

    • La espera activa es ineficiente: los procesos ocupan el procesador incluso aunque no puedan avanzar
    • El uso de variables compartidas genera esquemas:
      • Demasiado complejos
      • Muy artificiales
      • Propensos a errores: No hay una separación entre las variables de los cómputos de los procesos y las utilizadas para sincronización.
      • Inadecuados para grandes esquemas de protección.
      • Fuertemente acoplados: los procesos deben de saber unos de otros.

  • Los semáforos son señales simples que pueden obligar a un proceso a detenerse en una posición determinada.

  • Con la estructura adecuada de señales podemos satisfacer cualquier requisito de coordinación.

  • Los semáforos se usan como mecanismo de sincronización entre procesos.

  • Los procesos se bloquean o ejecutan condicionados únicamente por el valor de una variable entera.

Problemas inherentes a la programación concurrente

Los semáforos son una herramienta para resolver problemas tanto de exclusión mutua como de sincronización.

  • Exclusión mutua: sólo uno de los procesos debe estar en la sección crítica en un instante dado.
  • Sincronización: un proceso debe esperar la ocurrencia de un evento para poder seguir ejecutándose.

En resumen: los semáforos permiten sustituir la espera activa por una espera bloqueante, resolviendo los problemas de eficiencia y coordinación propios de la programación concurrente.

Definición

struct Semaphore {
    unsigned value;
    Queue q;
}
  • Un semáforo es un TAD formado por un valor numérico y una cola de procesos bloqueados.
  • Fueron inventados por Edsger Dijkstra (1965) y se usaron por primera vez en el sistema operativo THEOS (1974). En este otro enlace puedes ver un poco más de la intrahistoria de THEOS.
  • Un semáforo bloquea un proceso cuando éste no puede realizar la operación deseada, evitando el desperdiciar tiempo de CPU.
  • De este modo, los semáforos permiten sustituir la espera activa por una espera bloqueante, más eficiente y fácil de razonar.

Operaciones sobre semáforos

  • P: del holandés proberen te verlagen (intentar decrementar). Si el contador es mayor que 0 lo decrementa, en caso contrario bloquea el proceso que lo llamó. Más conocida como wait, acquire o lock.

  • V: del holandés verhoog (incrementar). Si hay algún proceso bloqueado en el semáforo, lo desbloquea, en caso contario, incrementa el valor de la variable. Más conocida como signal, release o post.

    def wait(s):
   if s.value > 0:
     s.value -= 1
   else:
        add(process, s.queue)
        block(process)

  • Si value es mayor que 0: se decrementa el valor del semáforo.

  • Si value es 0: se bloquea el proceso que llamó a wait.

    def signal(s):
   if empty(s.queue):
     s.value += 1
   else:
     process = get(s.queue)
     sched(process)

  • Si no hay procesos bloqueados en la cola del semáforo, se incrementa su valor.

  • En en caso contrario, se desbloquea a un proceso.

Ejercicio 1:

  • Para implementar los semáforos se requiere utilizar mecanismos de espera ocupada para acceder a algunas variables. Indica qué lineas de código son una sección crítica en el código anterior.
  • Justifica brevemente por qué no hay espera activa prolongada.

Otras operaciones (dependen de la implementación)

  • Asignar un valor al semáforo
  • Obtener el valor del semáforo
  • Intentar wait sólo si no produce bloqueo del proceso (try_lock)
  • Elección de la política de desbloqueo de procesos
  • …

La definición de un semáforo implica la exclusión mutua en la ejecución de las operaciones por él definidas Esta exclusión mutua se consigue mediante funciones proporcionadas por el sistema operativo (típicamente espera con bloqueo)

Exclusión mutua

  • La exclusión mutua garantiza que solo un proceso o hilo puede acceder a la sección crítica en cada instante.
  • Con un semáforo inicializado a 1, podemos implementarla fácilmente.
Semaphore s = 1;
...
s.wait();
critical_section();
s.signal();
...

  • Cuando el primer proceso entre a la sección crítica decrementará su valor y continuará.

  • Si otro proceso desea entrar, value será cero, por lo que se bloqueará hasta que el primero ejecute signal.

  • Ejemplos de uso de semáforos:

    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; // Used for a unnamed POSIX semaphore

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\n", tid, counter);
}

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

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

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

    printf("Counter value: %d Expected: %d\n", counter, MAX_COUNT);
    return 0;
}
    Python 
    import threading
import time

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)

    # Start all threads
    for t in threads:
        t.start()

    # Wait for all threads to complete
    for t in threads:
        t.join()

    print("Counter value: %d Expected: %d\n" % (counter, MAX_COUNT))

if __name__ == "__main__":
    main()

  • En Java también hay semáforos, pero no se suelen utilizar si no se está portando código de otros lenguajes, ya que Java ya ofrece mecanismos de sincronización más directos y seguros de alto nivel como los bloques synchronized o los monitores.

  • En Rust no es necesario usar semáforos binarios, ya que el lenguaje no permite compartir variables entre hilos sin mecanismos seguros como Mutex o RwLock. Tampoco tiene semáforos implementados en la librería estándar pero hay librerías externas como tokio::sync::Semaphore o semaphore::Semaphore.

Ejercicio 2:

Realiza una traza de dos procesos que realizan exclusión mutua mediante un semáforo para acceder a una sección crítica.

Candados, mutexes o locks

Aunque los semáforos pueden resolver la exclusión mutua, en la práctica se emplean mecanismos más simples y seguros: los candados o mutexes, que son semáforos binarios especializados y optimizados para la exclusión mutua.

  • Inicializados a 1 por defecto
  • Sólo el proceso que hizo wait puede hacer signal. Esto es una diferencia fundamental con los semáforos.
  • Algunos sistemas permiten que el mismo hilo haga varios wait, si ya es propietario del lock continúa su ejecución. Se denominan reentrantes.

Uso de candados

Mutex mutex
...
mutex.lock()
critical_section()
mutex.unlock()
...
  • En C los mutex están en la biblioteca POSIX Threads y no son reentrantes (mutex.c).
  • En Python tenemos threading.Lock (no reentrante) y threading.Rlock (reentrante). Se pueden usar también con la cláusula with (programas lock.py y lock_with.py).
  • En la biblioteca estándar de C++ tenemos mutex, thread, condition variable, etc…
  • En D tenemos la parte de bajo nivel de su biblioteca estándar core.sync (mutex, semaphore, condition, etc…) y otros componentes de alto nivel como: std.parallelism o std.process.
  • En Vala tenemos un API orientado a objetos sobre GLib (Mutex, Thread).
  • En la biblioteca estándar de rust disponemos de hilos y primitivas de sincronización (mutex, condvar, etc…), pero no de semáforos. En éste último caso hemos de recurrir a bibliotecas externas.

Ejercicio 3

Supongamos una función de transferencia de dinero entre cuentas:

def transfer(account_a, account_b, amount):
  if account_a.balance >= amount:
      account_a.balance -= amount
      account_b.balance += amount
  • Indica cuales son las secciones críticas.
  • Añade las operaciones lock() y unlock() necesarias.
  • ¿Qué podría ocurrir si dos transferencias simultáneas involucran las mismas cuentas?
  • ¿Qué ventajas tendría usar un mutex global frente a uno por cuenta?

POSIX Mutex

  • Si nuestra aplicación se compone de un sólo proceso con múltiples hilos, la biblioteca pthread.h proporciona mutex (semáforos binarios para hilos).

    #include<pthread.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// inicializar con los atributos por defecto
int pthread_mutex_init (...)    // para otras inicializaciones
int pthread_mutex_destroy(...)  // destruir el candado
int pthread_mutex_lock(...)     // bloquear candado o espera si bloqueado
int pthread_mutex_trylock(...); // bloquear candado y no espera si bloqueado
int pthread_mutex_unlock(...)   // desbloquear candado
...

// Declaración de los datos compartidos y del candado que los protege

struct datos_compartidos {
    declaración de los datos
    pthread_mutex_t candado;
} datos;
...
void codigo_hilo(void *arg){
    ...
    pthread_mutex_lock(&datos.candado);
    // seccion critica
    pthread_mutex_unlock(&datos.candado);
    ...
}

void main(){
    pthread_t hilo_1, hilo_2;
    int error;
    ...
    // Inicializacion del candado
    error = pthread_mutex_init (&datos.candado, NULL);
    //pthread_mutex_t datos.candado = PTHREAD_MUTEX_INITIALIZER;
    if (error)
        // tratamiento del error

    // Creación de los hilos
    error = pthread_create(&hilo_1, NULL, codigo_hilo, NULL);
    if (error)
        // tratamiento del error
    error = pthread_create(&hilo_1, NULL, codigo_hilo, NULL);
    if (error)
        // tratamiento del error
    ...
}

Sincronización

Además de para exclusión mutua, los semáforos pueden emplearse como mecanismos de sincronización general entre procesos o hilos.

  • El valor del semáforo puede interpretarse como un indicador del número de recursos disponibles (permits).
  • Indica el número de llamadas que se pueden hacer a wait sin provocar bloqueo.
  • En exclusión mutua debe ser 1. En este caso reciben el nombre de semáforos binarios.
  • Este tipo de semáforos se denominan semaforos contadores o multiplexes y son útiles, por ejemplo, para limitar el número máximo de tareas concurrentes, impresoras disponibles o procesos en ejecución.

Algoritmo de Barz

  • El algoritmo de Barz permite simular semáforos generales utilizando únicamente semáforos binarios. Es decir, construye un semáforo con valor arbitrario k a partir de dos semáforos binarios y una variable contador.

    mutex = BinarySemaphore(1)
gate = BinarySemaphore(1)
value = K

def general_wait():
    gate.wait()       # si no es el primero debe esperar
    mutex.wait()
    value -= 1
    if value > 0:
        gate.signal()  # permite que entre otro si el valor es positivo
    mutex.signal()

def general_signal():
    mutex.wait()
    value += 1
    if value == 1:
        gate.signal()  # antes estaba en cero, permite que entre otro
    mutex.signal()

  • mutex garantiza la exclusión mutua sobre la variable value.

  • gate regula el acceso a la operación wait() según el valor actual del semáforo.

  • value representa el contador de permisos disponibles, equivalente al valor del semáforo general. Con este esquema, cualquier operación sobre el semáforo puede implementarse empleando solo semáforos binarios, lo que simplifica la implementación en sistemas que no disponen de semáforos generales nativos.

Condición de sincronización

Los semáforos también permiten expresar condiciones de sincronización entre procesos. Cada condición se asocia a un semáforo general, y los procesos pueden esperar o notificar la ocurrencia de un evento mediante las operaciones wait() y signal().

  • Se asocia un semáforo general a cada condición.
  • Un proceso espera a que una condición se cumpla ejecutando una operación wait().
  • Cuando un proceso ha hecho que se cumpla una determinada condición, lo indica ejecutando un signal() sobre dicho semáforo.
  • De este modo, se pueden coordinar procesos que deben ejecutarse en un orden determinado.

Ejercicio 4: Un proceso espera a otro

El proceso $Q$ no puede ejecutar su instrucción $Q_2$ hasta que $P$ haya ejecutado $P_1$.

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

Indica cómo usarías semáforos para resolver este problema.

Ejercicio 5: Ambos procesos deben esperarse

Los procesos $P$ y $Q$ deben alcanzar el mismo punto antes de continuar.

P             Q
...           ...
P1            Q1
(1)           (1)
P2            Q2
...           ...

Indica cómo usarías semáforos para resolver este problema.

Ejercicio 6: Espera con alternativa lógica (OR)

El proceso $Q$ solo puede ejecutar $Q_2$ si P ha ejecutado $P_1$ o $R$ ha ejecutado $R_1$.

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

Indica cómo usarías semáforos para resolver este problema.

Ejercicio 7: Espera con condición múltiple (AND)

El proceso $Q$ solo puede ejecutar $Q_2$ si $P$ ha ejecutado $P_1$ y $R$ ha ejecutado $R_1$.

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

¿Por qué la siguiente solución no es correcta?

Semaphore sync = 0
P                Q             R
...              ...           ...
P1               Q1            R1
sync.signal()    sync.wait()   sync.signal()
P2               sync.wait()   R2
...              Q2            ...
                 ...

Plantea una solución correcta.

Barreras de sincronización

Las barreras de sincronización son un mecanismo que permite coordinar un conjunto de procesos o hilos que trabajan en fases. Cada proceso debe esperar a que todos los demás hayan alcanzado el mismo punto antes de continuar con la siguiente fase.

  • Los procesos se sincronizan por etapas: todos deben finalizar la fase actual antes de empezar la siguiente.
  • En los ejemplos anteriores, esta situación se modelaba usando uno o varios semáforos para puntos de espera concretos.
  • Cuando el número de procesos es pequeño, se puede usar un semáforo por cada punto de sincronización.
  • Sin embargo, al aumentar el número de procesos, esta solución se vuelve ineficiente por el coste de gestión de múltiples semáforos.

Barreras para n procesos

El caso general de una barrera puede representarse mediante una estructura cíclica:

while True:
    do_phase()
    barrier(n)

La función barrier(n) asegura que ningún proceso comience la siguiente fase hasta que los n procesos hayan terminado la actual.

Implementación con semáforos

Una barrera puede implementarse utilizando dos semáforos y un contador que se actualiza de forma atómica (o con exclusión mutua si no hay operaciones atómicas disponibles).

  • Y se puede solucionar con dos semáforos y un contador con actualización atómica

  • Si no se dispone de este tipo de contador se necesita además un candado

  • Algunos lenguajes implementan, o están en proceso de implementar, este tipo de barreras.

    Semaphore arrival = 1
Semaphore departure = 0
counter = 0

def barrier(n):
    arrival.wait()
    getAndAdd(counter, 1)
    if counter < n:
        arrival.signal()   (1)
    else:
        departure.signal() (2)

    departure.wait()       (3)

    getAndAdd(counter, -1)
    if counter > 0:
        departure.signal() (4)
    else:
        arrival.signal()   (5)

  • En (1) si no llegaron todos los procesos, permite la llegada de otro

  • En (2) si llegaron todos, autoriza la salida de un proceso

  • En (3) espera la autorización para continuar

  • En (4) si no salieron todos, autoriza la salida del siguiente

  • En (5) si llegaron todos, comienza nuevamente el ciclo de llegadas

  • Veamos cómo queda el código completo (barrier.py)

Tipos e implementaciones

Semáforos fuertes y débiles

Los semáforos pueden clasificarse según la política de planificación que se aplica a los procesos bloqueados en su cola de espera.

  • Semáforos fuertes:
    • La cola de procesos bloqueados sigue una política FIFO (First In, First Out).
    • Garantizan justicia en el acceso: los procesos se desbloquean en el mismo orden en que se bloquearon.
    • Evitan inanición (starvation), asegurando que todos los procesos avanzan eventualmente.
  • Semáforos débiles:
    • Los procesos bloqueados se seleccionan aleatoriamente o según criterios no deterministas.
    • Son más simples de implementar, pero no garantizan equidad.
    • Pueden provocar espera indefinida para algunos procesos si otros son seleccionados repetidamente.

Semáforos System V

Los semáforos System V fueron el primer mecanismo estándar en UNIX para la sincronización entre procesos mediante el kernel. Forman parte del modelo clásico de System V IPC (junto con colas de mensajes y memoria compartida) y permiten que varios procesos coordinen su acceso a recursos compartidos.

Aunque siguen estando disponibles en UNIX y Linux, hoy en día se consideran obsoletos y se utilizan principalmente por motivos de compatibilidad. Su API (semget, semop, semctl) es más compleja y menos portable que la de los semáforos POSIX, que la sustituyen en los sistemas modernos.

Semáforos POSIX

  • Sustituyen a los semáforos System V con una interfaz más simple, moderna y portable.

  • Permiten sincronización entre procesos o hilos.

  • Es un estándar relativamente reciente (1993).

  • Para utilizarlos, debemos incluir la cabecera <semaphore.h>.

  • El tipo del semáforo es sem_t y almacena toda la información relativa al semáforo.

  • Existen dos tipos:

    • Semáforos nominales:
      • Se identifican por un nombre en la jerarquía del sistema de ficheros (por ejemplo, /sem1).
      • Permiten la sincronización entre procesos no relacionados.
      • Se crean y abren mediante sem_open() y se eliminan con sem_unlink().
    • Semáforos anónimos:
      • No tienen nombre en el sistema de ficheros.
      • Se usan para sincronización entre hilos del mismo proceso o entre procesos que comparten memoria.
      • Se inicializan con sem_init() y se destruyen con sem_destroy().

  • Operaciones principales:

    • sem_wait(sem_t *sem): Decrementa y bloquea si el valor es 0
    • sem_post(sem_t *sem): Incrementa y despierta un proceso bloqueado

  • Ejemplos de uso de semáforos:

    Semáforo nominal 
    #include <stdio.h>
include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <sys/stat.h>
#include <semaphore.h>

#define PATH "./fichero_compartido"

int main(int argc, char *argv[]){
FILE *f;
char *nombre;
sem_t *semaphore;

//composing semaphore name. Must be the same for all process.
nombre = (char*)malloc(strlen("p_mutex")+1);
snprintf(nombre,strlen("p_mutex")+1, "p_mutex");

//attach to semaphore, if not exist will be created
semaphore = sem_open(nombre, O_CREAT, S_IRWXU, 1);


//block semaphore
sem_wait(semaphore);

printf("Puedes comprobar que el semaforo sem.p_mutex esta disponible en /dev/shm\n");
getchar();



f = fopen(PATH, "a");
fprintf(f, "%s\n",argv[1]);
fclose(f);


//unblock semaphoresem_post(semaphore);
sem_post(semaphore);

//dettach the semaphore, if there arent other process attached the semaphore will be removed
sem_close(semaphore);
// El nombre del semaforo es borrado del sistema de ficheros
sem_unlink(nombre);

return 0;
}
    Semáforo anónimo 
    #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; // Used for a unnamed POSIX semaphore

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: %d)\n", tid, counter, max);
}

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

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

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

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

Semáforos vs. Espera Ocupada

  • Si los semáforos residen en la memoria compartida y por tanto hay que acceder a ellos en exclusión mutua, ¿no es la pescadilla que se muerde la cola? En algún momento habrá que recurrir a mecanismos de más bajo nivel.
  • Ventaja fundamental de los semáforos: Aunque internamente usen mecanismos de espera ocupada en secciones muy cortas, permiten bloquear procesos cuando no pueden continuar, liberando el procesador para otros. De esta forma, eliminan la necesidad de que los procesos esperen activamente.
Espera ocupada Semáforos
Descripción Ejecuta un bucle comprobando una variable (consume CPU) El núcleo bloquea el proceso y lo suspende hasta que pueda continuar
Ubicación Espacio de usuario Espacio de núcleo
Consumo de CPU Alto Bajo
Adecuacido para Esperas muy cortas Sincronización general entre procesos e hilos

Variables de condición

Las variables de condición se introducen para simplificar un caso muy común en la sincronización de hilos: cuando un hilo necesita esperar a que se cumpla un predicado que depende de una o varias variables compartidas con otros hilos.

Al ser variables compartidas, deben protegerse mediante un mutex.

Idea de funcionamiento

Las variables de condición permiten que un hilo espere dormido hasta que otra parte del programa le notifique un cambio relevante en lugar de realizar una espera activa comprobando continuamente una condición.

  • El hilo que espera bloquea su ejecución mediante cond_wait().
  • El hilo que notifica un cambio en el estado ejecuta cond_signal() o cond_broadcast().
  • Mientras un hilo está esperando, el mutex se libera automáticamente, de modo que otros hilos puedan modificar las variables compartidas.
  • Al despertar, el hilo vuelve a adquirir el mutex y comprueba de nuevo el predicado.

Ejemplo:

  • Supongamos que el predicado es que dos variables x e y tengan el mismo valor: x == y.
// 'v' es una variable de condicion
// 'm' es un mutex

// Hilo A                  // Hilo B
lock_mutex(&m);            lock_mutex(&m);
while ( x != y )           x += 3;
    cond_wait(&v, &m);       cond_signal(&v);
// Thread CS               // Thread CS
unlock_mutex(&m);          unlock_mutex(&m);
  • ¿Por qué el Hilo A llama a cond_wait() en un bucle en lugar de un if?

Ejercicio 8:

Se presentan tres casos. Indica si usarías un semáforo, un mutex o una variable de condición:

  1. Un contador compartido entre varios hilos.
  2. Un hilo debe esperar a que otro termine una tarea antes de continuar.
  3. Un proceso productor debe bloquearse si una cola está llena.

Posix API

#include <pthread.h>

pthread_cond_t v = 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);
int pthread_cond_broadcast(pthread_cond_t *cond);
  • pthread_cond_wait() bloquea el hilo y libera el mutex.
  • pthread_cond_signal() despierta un hilo en espera.
  • pthread_cond_broadcast() despierta todos los hilos en espera.

Observaciones

  • Una variable de condición no almacena el estado del predicado, solo permite la comunicación entre hilos.
  • Debe usarse siempre junto a un mutex que proteja las variables implicadas.
  • Permite sincronización eficiente dentro de un proceso, sin necesidad de recurrir a semáforos o primitivas del kernel.
  • Son especialmente útiles en la implementación de monitores, colas de tareas o buffers compartidos.

Problemas clásicos de sincronización

  • Productor-consumidor
  • Lectores-escritores
  • Comida de los filósofos

Productor-Consumidor

  • Es uno de los modelos más comunes en sistemas concurrentes.

  • Modela la interacción entre dos tipos de procesos:

    • Productores, que generan datos o recursos y los depositan en un buffer.
    • Consumidores, que recogen esos datos del buffer para procesarlos.

  • Para la comunicación sea asíncrona, se utiliza un buffer compartido.

  • El productor deposita elementos en el buffer, y el consumidor los extrae.

  • Requisitos:

    • Exclusión mutua en el acceso al buffer.
    • El consumidor debe esperar si el buffer está vacío.
    • El productor debe esperar si el buffer está lleno (en el caso de buffer limitado).

  • La mayoría de lenguajes proporcionan implementaciones nativas o en bibliotecas

Buffer infinito

producer-consumer-infinite.py

Queue buffer
Semaphore mutex = 1
Semaphore notEmpty = 0

# Productor
while True:
    data = produce()

    mutex.wait()
    buffer.add(data)
    mutex.signal()

    notEmpty.signal()

# Consumidor
while True:
    notEmpty.wait()

    mutex.wait()
    data = buffer.get()
    mutex.signal()

    consume(data)

Buffer limitado

producer-consumer.py

Queue buffer
Semaphore mutex = 1
Semaphore notEmpty = 0           # To get
Semaphore notFull = BUFFER_SIZE  # To put

# Productor
while True:
    data = produce()

    notFull.wait()  # Espera sitio poner producto

    mutex.wait()
    buffer.add(data)
    mutex.signal()

    notEmpty.signal() # Avisa que hay producto

# Consumidor
while True:
    notEmpty.wait()  # Espera a que haya producto

    mutex.wait()
    data = buffer.get()
    mutex.signal()

    notFull.signal() # Avisa de sitio para nuevo producto.

    consume(data)

Lectores-escritores

En este problema varios procesos comparten un recurso (por ejemplo, un fichero o base de datos). Se distinguen dos tipos de procesos:

  • Lectores, que solo leen el recurso (pueden hacerlo simultáneamente).
  • Escritores, que lo modifican (requieren acceso exclusivo). El objetivo es permitir la máxima concurrencia posible sin comprometer la consistencia del recurso.

Requisitos:

  • Varios lectores pueden acceder simultáneamente si no hay ningún escritor.
  • Solo un escritor puede acceder, y ningún lector puede hacerlo al mismo tiempo.
  • Se pueden definir políticas de prioridad:
    • Prioridad a la lectura: los lectores no esperan salvo que haya un escritor activo.
    • Prioridad a la escritura: los escritores no esperan una vez que lo solicitan.

Prioridad lectura

rw_lock.py

readers = 0          # num. lectores en la Secc. crítica
Semaphore writer = 1 # mutex para escritor
Semaphore mx = 1     # mutex acceso a variable "readers" y barrera
                     # para los escritores

def writer_lock():
    writer.wait()

def writer_unlock():
    writer.signal()

def reader_lock():
    mx.wait()
    readers += 1
    if readers == 1:
        writer.wait()
    mx.signal()

def reader_unlock():
    mx.wait()
    readers -= 1
    if readers == 0:
        writer.signal()
    mx.signal()

Ejercicio 9

¿En qué casos podría producirse inanición?

Prioridad escritura

Versión Básica

rw_lock_fair.py

readers = 0          # num. lectores en la Secc. crítica
Semaphore writer = 1 # mutex para escritor
Semaphore mx = 1     # mutex acceso a variable "readers" y barrera
Semaphore entry = 1  # bloquea FUTUROS lectores cuando un escritor quiere entrar

def writer_lock():
    entry.wait()
    writer.wait()

def writer_unlock():
    writer.signal()
    entry.signal()

def reader_lock():
    entry.wait()
    mx.wait()
    readers += 1
    if readers == 1:
        writer.wait()
    mx.signal()
    entry.signal()

def reader_unlock():
    mx.wait()
    readers -= 1
    if readers == 0:
        writer.signal()
    mx.signal()
  • Los escritores, al hacer entry.wait(), bloquean la entrada de nuevos lectores.
  • Los lectores que ya estaban dentro pueden terminar, pero no entran nuevos mientras haya un escritor esperando.
  • Garantiza que un escritor no quede esperando indefinidamente.

Presenta inconvenientes:

  • Requiere dos wait consecutivos en reader_lock() (entry y mx).
  • Cada entrada/salida de lector implica más operaciones y puede ralentizar el acceso cuando hay muchos lectores.
  • No es eficiente en situaciones de alta concurrencia.

Versión Optimizada

  • En la solución anterior, los dos wait sobre los semáforos entry y mx hacen ineficiente al algoritmo anterior.
  • El código rw_fair_faster.py es una implementación posterior (2013) que evita este problema.
  • POSIX y Java ofrecen implementaciones similares para el problema de los lectores-escritores.

Los lectores:

  • Los lectores adquieren y liberan entry rápidamente, solo para actualizar el contador readers_in.
  • Al salir, incrementan readers_out.
  • Si hay un escritor esperando (wait == True) y todos los lectores han terminado (readers_in == readers_out), el último lector libera al escritor con writer.release().
  • Se consigue que los lectores no se bloquean entre sí más tiempo del necesario.

Los escritores:

  • El escritor bloquea entry para impedir que entren nuevos lectores.
  • Comprueba si ya no hay lectores activos (readers_in == readers_out):
    • Si no hay, entra directamente.
    • Si los hay, se marca wait = True y se bloquea en writer.acquire().
  • El último lector que salga hará writer.release(), permitiendo que el escritor continúe.
  • Al terminar, el escritor libera entry, dejando pasar a nuevos lectores o escritores.

En resumen:

  • Lectores concurrentes: varios lectores pueden entrar a la vez.
  • Escritor en espera: bloquea nuevas lecturas hasta que terminen los lectores activos.
  • Último lector: detecta que hay un escritor esperando y lo desbloquea.
  • Escritor activo: accede en exclusión mutua.
  • Liberación: el escritor reabre la entrada a nuevos lectores.

Comida de filósofos

  • Cinco filósofos se dedican a pensar y a comer en una mesa circular.
  • En el centro de la mesa hay un cuenco con arroz, y en la mesa hay cinco platos y cinco palillos, uno por cada filósofo.
  • Para pensar, el filósofo no usa ninguno de los palillos.
  • Para comer, cada filósofo necesita los dos palillos adyacentes.
  • El filósofo sólo puede coger un palillo cada vez y no le puede quitar un palillo a un compañero que lo tenga en la mano.
  • Cuando un filósofo tiene los dos palillos come sin soltarlos hasta que termine y vuelva a pensar.

filosofos.png

Figure 1: Comida filósofos.

  • Ilustra los problemas básicos de interbloqueo.

  • Representa los problemas relacionados con la coordinación de los recursos no compartibles de un sistema.

  • Es objeto habitual de estudio y comparación entre los diferentes mecanismos de sincronización

    def philosopher():
while True:
    think()
    pick()     (1)
    eat()
    release()  (2)

Solución 1: Exclusión global

```python
def philosopher():
while True:
    think()
    table.wait() # Coge los palillos
    eat()
    table.signal() # Suelta los palillos
```
  • Exclusión mutua a toda la mesa
  • Sólo un filósofo puede comer a la vez
  • Solución ineficiente, porque podrían comer dos

Solución 2: Un palillo por filósofo

```python
Semaphore forks[5] = [1, 1, 1, 1, 1]

def philosopher(i):
    while True:
        think()
        forks[i].wait()
        forks[(i+1)%5].wait()
        eat()
        forks[i].signal()
        forks[(i+1)%5].signal()
```
  • Exclusión mutua a cada palillo
  • El filósofo i tendrá que coger los palillos i (izquierdo) e (i+1)%5 (derecho).
  • Puede producir interbloqueo si todos intentan comer simultáneamente: 
    Filósofo 0 → tenedor 0, espera 1
Filósofo 1 → tenedor 1, espera 2
Filósofo 2 → tenedor 2, espera 3
Filósofo 3 → tenedor 3, espera 4
Filósofo 4 → tenedor 4, espera 0
  • Ninguno puede continuar.
  • Se produce interbloqueo por espera circular.

Condiciones necesarias para el interbloqueo

Para que se produzca un interbloqueo, deben cumplirse simultáneamente las siguientes condiciones:

  • Exclusión mutua: Los recursos (palillos) no pueden ser compartidos; solo un filósofo puede usar cada uno a la vez.
  • Retención y espera: Cada filósofo mantiene un palillo mientras espera para obtener el otro.
  • No apropiación: Un recurso no puede ser arrebatado por la fuerza a otro proceso; un filósofo no suelta su palillo hasta que termina de comer.
  • Espera circular: Existe un ciclo cerrado de filósofos, cada uno esperando un palillo que otro tiene.

Si se rompe cualquiera de estas condiciones, el interbloqueo deja de ser posible.

Solución 3: Romper la espera circular

  • Hay que impedir alguna de las circunstancias anteriores

  • Lo más sencillo es romper la espera circular

  • Se puede conseguir evitando la simetría en el orden de adquisición de los palillos. Por ejemplo, haciendo que un filósofo cambie el orden de toma de los palillos.

    def pick(i):
    if i < right(i):    # todos menos el último
         forks[i].wait()
         forks[right(i)].wait()
    else:               # el último cambia el orden
         forks[right(i)].wait()
         forks[i].wait()

  • Se resuelve el interbloqueo, pero…

  • La solución no es óptima: en alguna traza podrían comer dos filósofos y sólo come uno.

  • Esperan los filósofos 0, 1, 2 y 4. Sólo come el 3

    forks[0].wait()         # Filosofo 0
  forks[1].wait()       # Filosofo 1
    forks[2].wait()     # Filosofo 2
      forks[3].wait()   # Filosofo 3
        forks[0].wait() # Filosofo 4, Wait en orden decreciente, se bloquea

forks[1].wait()       # Filosofo 0
  forks[2].wait()     # Filosofo 1
    forks[3].wait()   # Filosofo 2
      forks[4].wait() # Filosofo 3, tiene tenedor 4 libre, come y
                      # los otros esperan

Solución 4: Sin interbloqueo

  • Cambio de enfoque: lo vemos como un problema de sincronización philosofers_2.py:

    status[5] = [THINKING, ..., THINKING]
Semaphore sync[5] = [0, 0, 0, 0, 0]
Semaphore mutex = 1

def pick(i):
	mutex.acquire()
	status[i] = HUNGRY
	canEat(i)
	mutex.release()
	sync[i].acquire()

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

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

def canEat(i):
	if status[i] == HUNGRY and status[left(i)] != EATING and status[right(i)] != EATING:
		status[i] = EATING
		sync[i].release()

def release(i):
	mutex.acquire()
	status[i] = THINKING
	canEat(left(i)) # (1)
	canEat(right(i)) # (2)
	mutex.release()

  • Un filósofo podrá estar en cualquiera de estos estados: THINKING, HUNGRY, EATING

  • Un filósofo podrá comer si ninguno de sus vecinos está comiendo, en otro caso espera a que le notifiquen que han acabado

  • Disponemos de un array para representar el estado de los filósofos y un semáforo (mutex) controla la exclusión mutua a este array. El array sync de semáforos proporciona la sincronización entre filósofos.

  • Destacar las líneas (1) y (2), en ellas se evita un deadlock.

Ejercicio 10:

  • ¿Por qué puede haber inanición?
  • ¿Cómo se podría garantizar que todos los filósofos coman eventualmente?

Ejercicio 11:

Responde las siguientes cuestiones breves:

  1. ¿Qué problema resuelven los semáforos frente a la espera ocupada, y por qué son más eficientes?
  2. ¿Qué diferencia hay entre un semáforo binario y un mutex, si ambos pueden tomar los valores 0 y 1?
  3. ¿Por qué las operaciones wait() y signal() deben ejecutarse de forma atómica?
  4. ¿Qué papel desempeña el kernel en la implementación de los semáforos System V y POSIX?
  5. ¿Qué diferencia hay entre los semáforos nominales y los anónimos en POSIX?
  6. ¿Por qué decimos que la espera activa se realiza en el espacio de usuario, mientras que los semáforos actúan en el espacio del kernel?
  7. ¿Por qué las llamadas a cond_wait() deben colocarse dentro de un bucle while y no dentro de un if?
  8. Enumera las cuatro condiciones necesarias para que se produzca un interbloqueo.