Ir al contenido
CS3015 · SO

Productor–consumidor: de la versión sin sincronización al monitor

El problema

Sección titulada «El problema»

Un productor deja ítems en un buffer de tamaño N y un consumidor los saca. Ejemplos de clase: una máquina de gaseosas (el repartidor no puede meter más de lo que cabe y el cliente no puede sacar de una máquina vacía) y el pipeline de gcc (cpp | cc1 | cc2 | as | ld). El buffer existe para que ambos no tengan que trabajar al mismo ritmo (lockstep).

Tres restricciones:

  1. El consumidor espera si el buffer está vacío (restricción de planificación).
  2. El productor espera si está lleno (restricción de planificación).
  3. Uno a la vez manipula el buffer (exclusión mutua).

Buffer circular: un índice f para insertar, un índice i para extraer y un contador c. Con i == f el buffer puede estar vacío (c == 0) o lleno (c == N). Por eso hace falta el contador.

La evolución (laboratorio 08)

Sección titulada «La evolución (laboratorio 08)»

1. Sin sincronización (prod-cons-no-sync.c) produce dos bugs distintos:

  • el consumidor lee antes de que haya algo, por ejemplo item = -1: falta la restricción 1;
  • el productor sobrescribe ítems no leídos (desborda el buffer): falta la restricción 2.

2. Busy waiting (while (c == N); y while (c == 0);):

  • corrige la lógica, pero c++ y c-- no son atómicos (mov, inc, mov), así que se pierden actualizaciones. La solución es atomic_inc o un mutex;
  • además, desperdicia CPU.

3. Dormir «a mano» (if (c == 0) sleep(); … if (c == 1) wakeup_consumer();) causa un lost wake-up. Entre que el consumidor evalúa c == 0 y ejecuta sleep(), el productor produce y llama a wakeup antes de que el consumidor duerma: el aviso se pierde y el consumidor duerme para siempre. Revisar la condición y dormir debe ser atómico.

4. FUTEX (prod-cons-futex.c): el contador se actualiza con __atomic_fetch_add y la espera usa futex.

/* productor */                                   /* consumidor */
while (cont == N_ITEMS)                           while (cont == 0)
    futex_wait(&cont, N_ITEMS);                       futex_wait(&cont, 0);
final = (final + 1) % N_ITEMS;                    initial = (initial + 1) % N_ITEMS;
buffer[final] = i;                                aux = buffer[initial];
__atomic_fetch_add(&cont, 1, __ATOMIC_SEQ_CST);   __atomic_fetch_add(&cont, -1, __ATOMIC_SEQ_CST);
if (cont == 1) futex_wake(&cont, 1);              if (cont == N_ITEMS - 1) futex_wake(&cont, 1);
  • Por qué no hay lost wake-up: futex_wait(&cont, 0) hace que el kernel compruebe atómicamente que cont siga valiendo 0 antes de dormir; si el productor ya lo incrementó, retorna de inmediato y el while vuelve a mirar (traza).
  • Por qué solo despierta en los bordes: solo puede haber alguien durmiendo si el buffer estaba vacío (cont pasó de 0 a 1) o lleno (pasó de N a N − 1). En los demás casos se ahorra la syscall.
  • Detalle fino (propio): if (cont == 1) vuelve a leer cont después del fetch_add, y el otro hilo puede haberlo cambiado entre medio. Con 1 productor y 1 consumidor no causa un bug (quien podría estar durmiendo no puede cambiar cont), pero lo robusto es usar el valor que retorna la operación atómica: if (__atomic_fetch_add(&cont, 1, __ATOMIC_SEQ_CST) == 0) futex_wake(&cont, 1);.
  • Con varios productores o consumidores, esto no basta: los índices final e initial también se comparten y hace falta un lock.

5. Semáforos, la solución canónica. Con 1 productor y 1 consumidor ni siquiera hace falta un mutex, porque cada uno toca solo su extremo del buffer:

semaphore full = 0, empty = N;
Producer: while (1) { wait(empty); f = (f+1)%N; buffer[f] = produce(); signal(full);  }
Consumer: while (1) { wait(full);  i = (i+1)%N; consume(buffer[i]);    signal(empty); }

6. Con varios productores o consumidores hace falta un mutex para los índices compartidos. Esta es la versión completa, con un semáforo por restricción:

Semaphore fullSlots = 0;           // restricción del consumidor
Semaphore emptySlots = bufSize;    // restricción del productor
Semaphore mutex = 1;               // exclusión mutua


Producer(item) {                   Consumer() {
    emptySlots.P();                    fullSlots.P();
    mutex.P();                         mutex.P();
    Enqueue(item);                     item = Dequeue();
    mutex.V();                         mutex.V();
    fullSlots.V();                     emptySlots.V();
}                                      return item; }

Preguntas de la diapositiva:

  • ¿Por qué la asimetría? Cada uno hace P sobre el recurso que consume y V sobre el que produce: el productor consume espacios vacíos y produce ítems; el consumidor, al revés.
  • ¿Importa el orden de los P? Sí. Invertirlos puede causar deadlock: te bloqueas sosteniendo mutex.
  • ¿Importa el orden de los V? No para la corrección; solo puede afectar la eficiencia de la planificación.
  • ¿Y con 2 productores o 2 consumidores? Hace falta el mutex sobre Enqueue y Dequeue, porque compiten por el mismo índice.
Stallings fig. 5.9: el bug sutil con semáforos binarios (n, s, delay)
int n; binary_semaphore s = 1, delay = 0;
producer: produce(); semWaitB(s); append(); n++; if (n == 1) semSignalB(delay); semSignalB(s);
consumer: semWaitB(delay);
          while (1) { semWaitB(s); take(); n--; semSignalB(s); consume(); if (n == 0) semWaitB(delay); }

Bug: el consumidor deja n = 0 y sale de la SC. Antes de que evalúe if (n == 0), el productor agrega un ítem (n = 1) y hace semSignalB(delay). Luego el consumidor ve n == 1 y no espera. En la siguiente vuelta consume ese ítem, pero delay quedó en 1: después consumirá de un buffer vacío y n llegará a −1.

Mover el if dentro de la SC no sirve, porque produce deadlock. Corrección: copiar n a una variable local dentro de la SC (m = n;) y preguntar por m afuera. La versión limpia usa semáforos contadores: semWait(n); semWait(s); take(); semSignal(s);.

Con monitor (Hoare, notación de Stallings), el monitor garantiza la exclusión mutua solo; el programador pone únicamente las restricciones de planificación:

monitor boundedbuffer;  char buffer[N]; int nextin, nextout, count; cond notfull, notempty;
void append(char x) { if (count == N) cwait(notfull);  buffer[nextin] = x; nextin = (nextin+1)%N; count++; csignal(notempty); }
void take(char *x)  { if (count == 0) cwait(notempty); *x = buffer[nextout]; nextout = (nextout+1)%N; count--; csignal(notfull); }

En Mesa o con pthreads, esos if deben ser while.

Buffer acotado en pthreads (semáforos POSIX)

Sección titulada «Buffer acotado en pthreads (semáforos POSIX)»
sem_t mutex;   // = 1  exclusión mutua sobre el buffer
sem_t vacios;  // = N  huecos libres
sem_t llenos;  // = 0  elementos disponibles


void *productor(void *arg) {         void *consumidor(void *arg) {
    item = producir();                   sem_wait(&llenos);
    sem_wait(&vacios);                   sem_wait(&mutex);
    sem_wait(&mutex);                    item = extraer();
    insertar(item);                      sem_post(&mutex);
    sem_post(&mutex);                    sem_post(&vacios);
    sem_post(&llenos);                   consumir(item);
}                                    }

Regla: primero el semáforo de conteo y después mutex. Nunca te bloquees sosteniendo mutex. El orden de los sem_post no importa, porque post no bloquea.

Buffer acotado con pthread_mutex + pthread_cond (el monitor en C)

Sección titulada «Buffer acotado con pthread_mutex + pthread_cond (el monitor en C)»
int buf[N], in = 0, out = 0, count = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t notfull = PTHREAD_COND_INITIALIZER, notempty = PTHREAD_COND_INITIALIZER;


void put(int x) {                                 int get(void) {
    pthread_mutex_lock(&m);                           pthread_mutex_lock(&m);
    while (count == N)                                while (count == 0)
        pthread_cond_wait(&notfull, &m);                  pthread_cond_wait(&notempty, &m);
    buf[in] = x; in = (in + 1) % N; count++;          int x = buf[out]; out = (out + 1) % N; count--;
    pthread_cond_signal(&notempty);                   pthread_cond_signal(&notfull);
    pthread_mutex_unlock(&m);                         pthread_mutex_unlock(&m);
}                                                     return x; }

Diferencias con la versión de semáforos:

  • Un solo lock protege todo el estado (count, in, out); las condition variables no cuentan nada, son solo colas de espera. La condición se expresa en código (count == N).
  • pthread_cond_wait suelta el mutex atómicamente mientras duerme, así que no hay deadlock por dormir con el lock tomado.
  • while, no if: lo probé con 3 productores y 3 consumidores. Con while, la suma de lo consumido es exacta en las 3 corridas; con if, falla en las 3 (se sacan ítems de un buffer vacío). Los números están en Mutex POSIX y futex.

Todas las implementaciones, comparadas

Sección titulada «Todas las implementaciones, comparadas»
VersiónCorrectaEsperaQué la rompe o la limita
Sin sincronización✘—lee antes de producir, sobrescribe
Busy wait + c++✘activac++ no es atómico
Busy wait + atómico✔activa (gasta CPU)ineficiente
sleep/wakeup a mano✘bloqueantelost wake-up
FUTEX + atómico✔ (1 productor, 1 consumidor)bloqueantecon varios hace falta lock para los índices
Semáforos (llenos, vacios, mutex)✔bloqueanteorden de los wait (deadlock si se invierte)
Mutex + condition variables✔bloqueanteif en vez de while

Simulador

Sección titulada «Simulador»

Elige un escenario. En los escenarios con deadlock, intenta provocarlo tú antes de leer la nota.

Simulador de semáforos

Haz clic en un proceso para ejecutar su siguiente instrucción. Semántica de Stallings: el valor puede ser negativo (|valor| = procesos en cola) y la cola es FIFO.

mutex1
vacios2
llenos0
buffer: □□ (0/2)
Registro vacío.
Orden correcto: primero el semáforo de conteo (vacios/llenos) y luego mutex. Nunca te bloqueas mientras sostienes mutex.

E1 2026-1 · P1.3

Sección titulada «E1 2026-1 · P1.3»
sem_wait(&mutex);
sem_wait(&espacios_vacios);   // ← invertido

Con el buffer lleno, el productor toma mutex y se bloquea en espacios_vacios, reteniendo mutex. El consumidor, que es el único que podría liberar un hueco, se bloquea en sem_wait(&mutex). → C: deadlock.

E1 2024-I · P3: stock con if

Sección titulada «E1 2024-I · P3: stock con if»
Solucionario oficial + detalle

¿Deadlock? Sí. El buyer toma resource y, si stock == 0, hace sem_wait(restock) dentro de la sección protegida. El seller necesita resource para aumentar el stock y hacer sem_post(restock), pero nunca lo obtiene. Hay hold and wait + espera circular.

Sin if y sin deadlock: usar un semáforo contador stock_sem (= 0) que representa las unidades disponibles.

void *seller() {                       void *buyer() {
    while (1) {                            while (1) {
        sem_wait(&resource);                   sem_wait(&stock_sem);   // espera stock FUERA de la SC
        add_one_stock();                       sem_wait(&resource);
        sem_post(&resource);                   buy_one_stock();
        sem_post(&stock_sem);                  sem_post(&resource);
    }                                      }
}                                      }

E1 2024-I · P4: guerreros y aretes (6 pts)

Sección titulada «E1 2024-I · P4: guerreros y aretes (6 pts)»

8 guerreros, 4 aretes, parejas fijas (1,6) (2,7) (3,4) (5,8). Cada uno hace wait(earrings); signal(ready[me]); wait(ready[buddy]); …; signal(earrings).

Solución (oficial corregida + versión simple)

Deadlock: sí. Si toman arete un miembro de cada pareja, por ejemplo G1, G2, G3 y G5, los 4 aretes están tomados. Cada uno espera a su pareja en ready[buddy], y las parejas esperan un arete. Hay hold and wait + espera circular.

Starvation (si no hay deadlock): con semáforos FIFO, cada guerrero recibe su arete en orden, así que no hay starvation.

Corrección simple: eliminar el hold and wait. Primero la cita con la pareja (sin retener nada) y luego un solo miembro pide los aretes de a pares, con un semáforo pares = 2.

sem_t pares;                 // = 2  (dos pares de aretes)
sem_t ready[8], go[8], done[8];   // = 0


void *warrior(int me) {
    int b = buddy(me);
    while (1) {
        sem_post(&ready[me]);  sem_wait(&ready[b]);    // cita: ambos presentes, nada retenido
        if (me < b) { sem_wait(&pares); sem_post(&go[b]); }   // el líder toma el PAR completo
        else          sem_wait(&go[me]);
        put_earring(); fusion(); fight(); undo_fusion();
        if (me < b) { sem_wait(&done[me]); sem_post(&pares); } // el líder devuelve el par
        else          sem_post(&done[b]);
    }
}
  • Sin deadlock: el recurso se pide como unidad (un par por pareja) y quien espera pares no retiene nada, así que no hay hold and wait.
  • Sin starvation: pares es FIFO, así que cada pareja espera como máximo a las parejas que llegaron antes.

El oficial logra lo mismo con una cola de grupos protegida por mutex.

Fuente ·for_partial/Evaluaciones_OS_20261 (1).pdf (P1.3) · for_partial/E1_OS_2024_I__Respuestas_.pdf (P3, P4) · lab2/08-OSL-Producer Consumers.pdf · código del curso so/sem4/08-Producer-consumer/