Problema productor-consumidor

En computación, el problema del productor-consumidor es un ejemplo clásico de problema de sincronización de multiprocesos. El programa describe dos procesos, productor y consumidor, ambos comparten un búfer de tamaño finito. La tarea del productor es generar un producto, almacenarlo y comenzar nuevamente; mientras que el consumidor toma (simultáneamente) productos uno a uno. El problema consiste en que el productor no añada más productos que la capacidad del buffer y que el consumidor no intente tomar un producto si el buffer está vacío.

La idea para la solución es la siguiente, ambos procesos (productor y consumidor) se ejecutan simultáneamente y se “despiertan” o “duermen” según el estado del buffer. Concretamente, el productor agrega productos mientras quede espacio y en el momento en que se llene el buffer se pone a “dormir”. Cuando el consumidor toma un producto notifica al productor que puede comenzar a trabajar nuevamente. En caso contrario, si el buffer se vacía, el consumidor se pone a dormir y en el momento en que el productor agrega un producto crea una señal para despertarlo. Se puede encontrar una solución usando mecanismos de comunicación de interprocesos, generalmente se usan semáforos. Una inadecuada implementación del problema puede terminar en un deadlock, donde ambos procesos queden en espera de ser despertados.

Este problema puede ser generalizado para múltiples consumidores y productores.

Aproximación errónea[editar]

Para resolver el problema cualquier programador podría llegar a la solución que se muestra a continuación. En la misma se utilizan dos bibliotecas, sleep y wakeup. La variable global itemCount contiene el número de elementos en el buffer.

int itemCount = 0;

procedure producer() {
    while (true) {
        item = produceItem();

        if (itemCount == BUFFER_SIZE) {
            sleep();
        }

        putItemIntoBuffer(item);
        itemCount = itemCount + 1;

        if (itemCount == 1) {
            wakeup(consumer);
        }
    }
}

procedure consumer() {
    while (true) {

        if (itemCount == 0) {
            sleep();
        }

        item = removeItemFromBuffer();
        itemCount = itemCount - 1;

        if (itemCount == BUFFER_SIZE - 1) {
            wakeup(producer);
        }

        consumeItem(item);
    }
}

El problema con esta aproximación es que puede caer en un deadlock, considere el siguiente escenario:

El consumidor acaba de consultar la variable itemCount, nota que es cero y pasa a ejecutar el bloque if.
Justo antes de llamar a la función sleep() el consumidor es interrumpido y el productor comienza a trabajar.
El productor crea un objeto, lo agrega al buffer y aumenta itemCount.
Como el buffer estaba vacío antes de la última adición el productor intenta despertar al consumidor.
Desafortunadamente el consumidor no estaba durmiendo todavía luego la llamada para despertarlo se pierde. Una vez que el consumidor comienza a trabajar nuevamente pasa a dormir y nunca más será despertado. Esto pasa porque el productor solo lo despierta si el valor de itemCount es 1.
El productor seguirá trabajando hasta que el buffer se llene, cuando esto ocurra se pondrá a dormir también.

Como ambos procesos dormirán por siempre, hemos caído en un deadlock. La esencia del problema es que se perdió una llamada enviada para despertar a un proceso que todavía no estaba dormido. Si no se perdiera, todo funcionaría. Una alternativa rápida sería agregar un bit de espera de despertar a la escena. Cuando se envía una llamada de despertar a un proceso que está despierto, se enciende este bit. Después, cuando el proceso trata de dormirse, si el bit de espera de despertar está encendido, se apagará, pero el proceso seguirá despierto. El bit de espera de despertar actúa como una alcancía de señales de despertar. Aunque el bit de espera de despertar soluciona este caso, es fácil construir ejemplos con tres o más procesos en los que un bit de espera de despertar es insuficiente. Se podría agregar un segundo bit de espera de despertar, o quizá 8 o 32, pero en principio el problema sigue ahí.

Solución usando semáforos[editar]

El uso de semáforos resuelve el problema de las llamadas perdidas. En la solución que se muestra a continuación se usan dos semáforos fillCount y emptyCount. El primero es el número de objetos que existen en el buffer mientras que emptyCount es el número de espacios disponibles donde se puede insertar objetos. fillCount es incrementado y emptyCount es decrementado cuando se inserta un objeto en el buffer. Si el productor intenta decrementar emptyCount cuando su valor es cero, el productor es puesto a dormir. La próxima vez que se consuma un objeto el productor despierta. El consumidor funciona análogamente.

semaphore fillCount = 0; // items produced
semaphore emptyCount = BUFFER_SIZE; // remaining space

procedure producer() {
    while (true) {
        item = produceItem();
        down(emptyCount);
            putItemIntoBuffer(item);
        up(fillCount);
    }
}

procedure consumer() {
    while (true) {
        down(fillCount);
            item = removeItemFromBuffer();
        up(emptyCount);
        consumeItem(item);
    }
}

La solución anterior funciona perfectamente cuando hay solo un productor y un consumidor. Cuando múltiples consumidores o productores comparten el mismo espacio de memoria para almacenar el buffer la solución anterior puede llevar a resultados donde dos o más procesos lean o escriban la misma región al mismo tiempo. Para entender como puede ser esto posible imagine como puede ser implementada la función putItemIntoBuffer(). Podría contener dos acciones, una busca un posible espacio y la otra escribe en él. Si la función puede ejecutarse concurrentemente por múltiples productores entonces el siguiente escenario es posible:

Dos productores decrementan emptyCount
Un productor determina el siguiente espacio donde insertar el objeto.
El segundo productor determina el siguiente espacio para insertar el objeto y resulta ser el mismo del primer productor.

Ambos intentan escribir al mismo tiempo.

Para sobreponerse a este problema necesitamos asegurarnos que solo un productor esté ejecutando el método putItemIntoBuffer() a la vez. En otras palabras necesitamos de algún modo tener una sección crítica con exclusión. La solución para múltiples productores y consumidores se muestra a continuación.

semaphore mutex = 1;
semaphore fillCount = 0;
semaphore emptyCount = BUFFER_SIZE;

procedure producer() {
    while (true) {
        item = produceItem();
        down(emptyCount);
            down(mutex);
                putItemIntoBuffer(item);
            up(mutex);
        up(fillCount);
    }
}

procedure consumer() {
    while (true) {
        down(fillCount);
            down(mutex);
                item = removeItemFromBuffer();
            up(mutex);
        up(emptyCount);
        consumeItem(item);
    }
}

Note que el orden en que cada semáforo es incrementado y decrementado es esencial, no usar un orden apropiado puede llevar a un deadlock.

Haciendo uso de monitores[editar]

El siguiente pseudocódigo muestra una solución al problema usando monitores. Como la exclusión mutua está implícita en los monitores no es necesario un esfuerzo extra para proteger la región crítica. En otras palabras, esta variante funciona con cualquier cantidad de productores y consumidores sin otra modificación. Es relevante el hecho de que el uso de monitores hace muchos menos probable la aparición de conflictos que cuando se usan semáforos.

monitor ProducerConsumer {
    int itemCount
    condition full;
    condition empty;

    procedure add(item) {
        while (itemCount == BUFFER_SIZE) {
            wait(full);
        }

        putItemIntoBuffer(item);
        itemCount = itemCount + 1;

        if (itemCount == 1) {
            notify(empty);
        }
    }
    procedure remove() {
        while (itemCount == 0) {
            wait(empty);
        }

        item = removeItemFromBuffer();
        itemCount = itemCount - 1;

        if (itemCount == BUFFER_SIZE - 1) {
            notify(full);
        }

        return item;
    }
}

procedure producer() {
    while (true) {
        item = produceItem()
        ProducerConsumer.add(item)
    }
}

procedure consumer() {
    while (true) {
        item = ProducerConsumer.remove()
        consumeItem(item)
    }
}

Nótese el uso de la sentencia while cuando se comprueba si el buffer está lleno o vacío. Con múltiples consumidores hay un race condition cuando un consumidor es notificado que un objeto ha sido puesto en el buffer pero otro consumidor que está esperando en el monitor lo extrae del buffer antes. Si en vez de una sentencia while se usa un if muchos objetos pueden ser agregados a un buffer lleno o removidos de un buffer vacío.

Véase también[editar]

Enlaces externos[editar]

Ejemplos de problemas clásicos de sincronización

Datos: Q1366130