Lectores y escritores

1. El problema

El problema de lectores y escritores modela un recurso compartido (como una base de datos, un archivo o una estructura de datos) al que acceden dos tipos de procesos: lectores que solo leen el recurso, y escritores que lo modifican. Varios lectores pueden leer simultáneamente, pero un escritor necesita acceso exclusivo (ningún otro lector ni escritor puede estar accediendo).

El problema fue propuesto por Courtois, Heymans y Parnas en 1971. Es uno de los problemas clásicos de sincronización porque modela situaciones reales (bases de datos, cachés, configuraciones) donde las lecturas son frecuentes y las escrituras son raras.

Las restricciones son:

• Varios lectores simultáneos: si no hay escritor, cualquier número de lectores puede leer.
• Escritor exclusivo: si un escritor está escribiendo, ningún lector ni escritor puede acceder.
• No hay inanición: ningún lector ni escritor espera indefinidamente.

2. Las variantes

Hay tres variantes del problema, que difieren en la prioridad que se da a lectores vs. escritores:

3. Primera solución: prioridad a lectores

En la primera variante, si hay lectores esperando, se les da prioridad sobre los escritores. Los escritores solo se ejecutan cuando no hay lectores.

La solución usa un mutex para proteger el contador de lectores y un semáforo para la exclusión del escritor:

int num_lectores = 0;
sem_t mutex;       /* protege num_lectores */
sem_t recurso;     /* exclusión del escritor (valor 1) */

void lector(void) {
    sem_wait(&mutex);
    num_lectores++;
    if (num_lectores == 1) {
        sem_wait(&recurso);  /* primer lector bloquea al escritor */
    }
    sem_post(&mutex);

    /* Leer el recurso. */

    sem_wait(&mutex);
    num_lectores--;
    if (num_lectores == 0) {
        sem_post(&recurso);  /* último lector libera al escritor */
    }
    sem_post(&mutex);
}

void escritor(void) {
    sem_wait(&recurso);  /* esperar a que no haya lectores */
    /* Escribir el recurso. */
    sem_post(&recurso);
}

El problema de esta solución es que si llegan lectores continuamente, el escritor espera indefinidamente (inanición del escritor).

4. Segunda solución: prioridad a escritores

En la segunda variante, si hay un escritor esperando, se le da prioridad sobre los lectores. Los lectores que llegan después del escritor deben esperar a que el escritor termine.

La solución usa un semáforo adicional para bloquear a los lectores cuando hay un escritor esperando:

int num_lectores = 0;
int num_escritores_esperando = 0;
sem_t mutex;          /* protege los contadores */
sem_t recurso;        /* exclusión (valor 1) */
sem_t no_escritor;    /* bloquea lectores si hay escritor esperando */

void lector(void) {
    sem_wait(&no_escritor);  /* esperar si hay escritor */
    sem_wait(&mutex);
    num_lectores++;
    if (num_lectores == 1) {
        sem_wait(&recurso);
    }
    sem_post(&mutex);
    sem_post(&no_escritor);

    /* Leer el recurso. */

    sem_wait(&mutex);
    num_lectores--;
    if (num_lectores == 0) {
        sem_post(&recurso);
    }
    sem_post(&mutex);
}

void escritor(void) {
    sem_wait(&mutex);
    num_escritores_esperando++;
    sem_post(&mutex);

    sem_wait(&recurso);  /* esperar a que no haya lectores */
    /* Escribir el recurso. */
    sem_post(&recurso);

    sem_wait(&mutex);
    num_escritores_esperando--;
    sem_post(&mutex);
}

El problema de esta solución es que si llegan escritores continuamente, los lectores esperan indefinidamente (inanición del lector).

5. Tercera solución: equitativa

En la tercera variante, se usa una cola FIFO para garantizar que nadie espera indefinidamente. Los lectores y escritores se turnan en orden de llegada.

Esta solución es más compleja pero garantiza la equidad. Se implementa con una cola de espera y un semáforo para cada tipo de acceso.

6. Código completo

La primera variante (prioridad a lectores) es la más usada en la práctica:

#define _POSIX_C_SOURCE 200809L
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int recurso = 0;
int num_lectores = 0;
sem_t mutex;
sem_t recurso_sem;

void *lector(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 3; i++) {
        sem_wait(&mutex);
        num_lectores++;
        if (num_lectores == 1) {
            sem_wait(&recurso_sem);
        }
        sem_post(&mutex);

        /* Leer el recurso. */
        printf("Lector %d: lee %d\n", id, recurso);
        usleep(100000);

        sem_wait(&mutex);
        num_lectores--;
        if (num_lectores == 0) {
            sem_post(&recurso_sem);
        }
        sem_post(&mutex);
    }
    return NULL;
}

void *escritor(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < 2; i++) {
        sem_wait(&recurso_sem);
        /* Escribir el recurso. */
        recurso++;
        printf("Escritor %d: escribe %d\n", id, recurso);
        usleep(200000);
        sem_post(&recurso_sem);
    }
    return NULL;
}

int main(void) {
    sem_init(&mutex, 0, 1);
    sem_init(&recurso_sem, 0, 1);

    pthread_t lectores[4];
    pthread_t escritores[2];
    int ids_l[4] = {0, 1, 2, 3};
    int ids_e[2] = {0, 1};

    for (int i = 0; i < 4; i++) pthread_create(&lectores[i], NULL, lector, &ids_l[i]);
    for (int i = 0; i < 2; i++) pthread_create(&escritores[i], NULL, escritor, &ids_e[i]);

    for (int i = 0; i < 4; i++) pthread_join(lectores[i], NULL);
    for (int i = 0; i < 2; i++) pthread_join(escritores[i], NULL);

    sem_destroy(&mutex);
    sem_destroy(&recurso_sem);
    return 0;
}

7. Propiedades

8. Inanición

La inanición es el principal problema de las variantes con prioridad:

• Prioridad a lectores: si llegan lectores continuamente, los escritores esperan indefinidamente.
• Prioridad a escritores: si llegan escritores continuamente, los lectores esperan indefinidamente.

La solución equitativa evita la inanición usando una cola FIFO, pero es más compleja de implementar.

9. Simulador interactivo

Este simulador muestra cómo lectores y escritores acceden a un recurso compartido:

10. Resumen

• El problema de lectores y escritores modela un recurso compartido con lectores y escritores.
• Varios lectores pueden leer simultáneamente; un escritor necesita acceso exclusivo.
• La primera variante da prioridad a los lectores (posible inanición de escritores).
• La segunda da prioridad a los escritores (posible inanición de lectores).
• La tercera es equitativa (nadie sufre inanición).
• La solución con semáforos usa mutex + recurso (y opcionalmente no_escritor).
• La inanición es el trade-off de la prioridad.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa la primera variante y observa la inanición de escritores.
2. Implementa la segunda variante y observa la inanición de lectores.
3. Implementa la tercera variante (equitativa) con una cola FIFO.
4. Usa pthread_rwlock y compara con tu implementación.
5. Explica por qué los lectores no necesitan exclusión mutua entre sí.
6. Investiga cómo se implementa pthread_rwlock en glibc.