Problema del productor y consumidor

El problema del productor y consumidor consiste en la situación siquiente: de una parte se produce algún producto (datos en nuestro caso) que se coloca en algún lugar (una cola en nuestro caso) para que sea consumido por otra parte. Como algoritmo obtenemos:

producer:                consumer:
  forever                  forever
    produce(item)            take(item)
    place(item)              consume(item)

Queremos garantizar que el consumidor no coja los datos más rápido de lo que los está produciendo el productor. Más concretamente:

1. el productor puede generar sus datos en cualquier momento
2. el consumidor puede coger un dato solamente cuando hay alguno
3. para el intercambio de datos se usa una cola a la cual ambos tienen acceso, asi se garantiza el orden correcto
4. ningún dato no está consumido una vez siendo producido

Si la cola puede crecer a una longitud infinita (siendo el caso cuando el consumidor consume más lento de lo que el productor produce), basta con la siguiente solución:

producer:                consumer:
  forever                  forever
    produce(item)            itemsReady.wait()
    place(item)              take(item)
    itemsReady.signal()      consume(item)

donde itemsReady es un semáforo general que se ha inicializado al principio con el valor 0.

El algoritmo es correcto, lo que se vee con la siguiente prueba. Asumimos que el consumidor adelanta el productor. Entonces el número de wait()s tiene que ser más grande que el número de signals():

       #waits > #signals
  ==>  #signals - #waits < 0
  ==>  itemsReady < 0

y la última línea es una contradicción a la invariante del semáforo.

Queremos ampliar el problema introduciendo más productores y más consumidores que trabajen todos con la misma cola. Para asegurar que todos los datos estén consumidos lo más rápido posible por algún consumidor disponible tenemos que proteger el acceso a la cola con un semáforo binario (llamado mutex abajo):

producer:                consumer:
  forever                  forever
    produce(item)            itemsReady.wait()
    mutex.wait()             mutex.wait()
    place(item)              take(item)
    mutex.signal()           mutex.signal()
    itemsReady.signal()      consume(item)

Normalmente no se puede permitir que la cola crezca infinitamente, es decir, hay que evitar producción en exceso también. Como posible solución introducimos otro semáforo general (llamado spacesLeft) que cuenta cuantos espacios quedan libre en la cola. Se inicializa el semáforo con la longitud máxima permitida de la cola. Un productor queda bloqueado si ya no hay espacio en la cola y un consumidor siñala su consumisión.

producer:                consumer:
  forever                  forever
    spacesLeft.wait()        itemsReady.wait()
    produce(item)            mutex.wait()
    mutex.wait()             take(item)
    place(item)              mutex.signal()
    mutex.signal()           consume(item)
    itemsReady.signal()      spacesLeft.signal()