Wiki CC3301

Un semáforo es un contenedor de tickets. En él se pueden depositar un ticket con sem_post y extraer un ticket con sem_wait. La garantía es que si sem_wait no encuentra tickets entonces no retorna hasta que algún thread invoque sem_post para depositar un ticket.

Un semáforo se manipula con las siguientes funciones:

  #include <semaphore.h>
  sem_t sem;
  sem_init(&sem, 0, tickets_iniciales);
  sem_post(&sem);
  sem_wait(&sem);

La siguiente es una implementación correcta de la estructura Buffer del productor/consumidor.

  /* Versión correcta */
  typedef struct {
    int size;
    Cuadro **array;
    int in, out;
    sem_t empty, full;
  } Buffer;
  
  Buffer *nuevoBuffer(int size) {
    Buffer *buf= (Buffer*)malloc(sizeof(Buffer));
    buf->size= size;
    buf->array= (Cuadro**)malloc(size*sizeof(Cuadro*));
    buf->in= buf->out= 0;
    sem_init(&buf->empty, 0, size);
    sem_init(&buf->full, 0, 0);
    return buf;
  }
  
  void put(Buffer *buf, Cuadro *cuadro) {
    sem_wait(&buf->empty);
    buf->array[buf->in]= cuadro;
    buf->in= (buf->in+1) % buf->size;
    sem_post(&buf->full);
  }
  
  Cuadro *get(Buffer *buf) {
    Cuadro *cuadro;
    sem_wait(&buf->full);
    cuadro= buf->array[buf->out];
    buf->out= (buf->out+1) % buf->size;
    sem_post(&buf->empty);
    return cuadro;
  }

Hay muchos problemas que se pueden paralelizar usando la abstracción productor/consumidor. En ellos la solución es la misma de arriba. Solo cambia el código del productor, del consumidor y los ítemes que se depositan en el Buffer. Pero el código del buffer es el mismo.

El problema del productor/consumidor se puede generalizar a múltiples productores y múltiples consumidores que comparten el mismo buffer. Muestre que en este caso el código para depositar y extraer elementos de buffer puede sufrir de data-races. Corrija el código usando un semáforo o mutex adicional.

La segunda solución se basa en que el deadlock solo se produce si los 5 filósofos llegan a cenar. Si se limita a 4 los filósofos que pueden cenar, ya no habrá deadlock. Entonces se usa un semáforo con 4 tickets iniciales:

  pthread_mutex_t palitos[5];
  sem_t portero; /* con 4 tickets iniciales */
  
  void filosofo(int i) {
    for (;;) {
      sem_wait(&portero);
      pthread_mutex_lock(&palitos[i]);
      pthread_mutex_lock(&palitos[(i+1)%5]);
      comer(i, (i+1)%5);
      pthread_mutex_unlock(&palitos[i]);
      pthread_mutex_unlock(&palitos[(i+1)%5]);
      sem_post(&portero);
      pensar();
    }
  }

El problema de esta solución es que solo se aplica a 5 filósofos y 5 palitos. No se puede generalizar a un número variable de threads accediendo a múltiples estructuras de datos.