Problemas de sincronización usados para probar nuevas primitivas de Sistemas Operativos/Concurrencia.

Productor-consumidor (búfer limitado)

Dos procesos comparten un búfer de tamaño fijo: el productor inserta y el consumidor extrae. El productor debe dormir si el búfer está lleno y el consumidor si está vacío. La solución clásica usa tres semáforos (mutex, empty, full) — ver Sistemas Operativos/Semáforos — o un monitor — ver Sistemas Operativos/Mutex y monitores.

La cena de los filósofos (Dijkstra, 1965)

Cinco filósofos alrededor de una mesa, cada uno con un plato y un tenedor entre cada par. Para comer necesitan los dos tenedores adyacentes; alternan entre pensar y comer.

Solución ingenua (tomar el izquierdo y luego el derecho): si todos toman el izquierdo a la vez, nadie obtiene el derecho → interbloqueo (ver Sistemas Operativos/Interbloqueos). Soltar y reintentar tras un tiempo fijo produce inanición (starvation); con tiempo aleatorio funciona casi siempre, pero no garantizado.

Solución de Tanenbaum: un arreglo state[N] (PENSANDO, HAMBRIENTO, COMIENDO) y un semáforo por filósofo. Un filósofo sólo pasa a COMIENDO si ninguno de sus vecinos está comiendo.

const int N = 5;
int LEFT(int i)  { return (i + N - 1) % N; }
int RIGHT(int i) { return (i + 1) % N; }
int state[N];
semaphore mutex = 1;
semaphore s[N];       /* uno por filósofo, inicializados en 0 */

void take_forks(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);            /* intenta obtener ambos tenedores */
    up(&mutex);
    down(&s[i]);        /* se bloquea si no los obtuvo */
}

void put_forks(int i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT(i));         /* ¿puede comer el vecino izquierdo? */
    test(RIGHT(i));        /* ¿y el derecho? */
    up(&mutex);
}

void test(int i) {
    if (state[i] == HUNGRY && state[LEFT(i)] != EATING && state[RIGHT(i)] != EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

Permite el máximo paralelismo posible (dos filósofos comiendo a la vez con N = 5).

Lectores y escritores (Courtois et al., 1971)

Modela el acceso a una base de datos: muchos lectores pueden leer simultáneamente, pero un escritor necesita acceso exclusivo.

semaphore mutex = 1;   /* controla el acceso a rc */
semaphore db = 1;      /* controla el acceso a la base de datos */
int rc = 0;            /* lectores leyendo o queriendo leer */

void reader(void) {
    while (TRUE) {
        down(&mutex);
        rc = rc + 1;
        if (rc == 1) down(&db);   /* primer lector bloquea a escritores */
        up(&mutex);
        read_data_base();
        down(&mutex);
        rc = rc - 1;
        if (rc == 0) up(&db);     /* último lector libera */
        up(&mutex);
        use_data_read();
    }
}

void writer(void) {
    while (TRUE) {
        think_up_data();
        down(&db);
        write_data_base();
        up(&db);
    }
}

Esta versión da prioridad a los lectores: con un flujo constante de lectores, el escritor puede sufrir inanición. Una alternativa hace que los lectores nuevos esperen detrás de un escritor en espera.

El barbero dormilón

Una barbería con un barbero, una silla de barbero y n sillas de espera. Sin clientes, el barbero duerme; un cliente que llega lo despierta o espera, y se va si no hay sillas libres. Es un problema de colas que se resuelve con semáforos customers, barbers y mutex, más un contador waiting.

#sistemas-operativos #tanenbaum #concurrencia