Termelő-fogyasztó minta

A termelő-fogyasztó minta a számítástudományban egy konkurens programtervezési minta, ami függetleníti az objektumok létrehozását azok felhasználásától. A minta egy klasszikus szinkronizációs problémát vet fel. Legalább két szál van benne, egy termelő és egy fogyasztó, és van benne egy buffer is. A termelő feladata objektumok létrehozása, és behelyezése a bufferba. A fogyasztó feladata az objektumok kivétele és felhasználása. A probléma abban áll, hogy a buffer nem tud tetszőleges mennyiségű objektumot tárolni, így ha kiürül, vagy megtelik a raktár, akkor az egyik folyamatnak várakoznia kell.

A megoldást a folyamatok kommunikációja jelenti, tipikusan szemaforok közbeiktatásával. A megoldás nem triviális, a naiv megközelítés holtpontot okozhat, amikor is mindkét folyamat a másikra vár, hogy felébressze. A megoldásra több megvalósítás is van.

A minta és a probléma általánosítható több termelőre és fogyasztóra is.

Naiv megvalósítás

A konkurens programozásban járatlan programozók gyakran a következő naiv, ám hibás megoldást adják a problémára:

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);
    }
}

A kód felhasználja a sleep és a wakeup könyvtári rutinokat. A globális itemCount a bufferban levő objektumok számát tárolja.

Ez a megoldás azért hibás, mert versenyhelyzetet eredményezhet, ami holtpontot okozhat. Tekintsük a következő lefutást:

• A fogyasztó megnézi az itemCountot; azonban mielőtt aludni menne, elveszik tőle a vezérlést.
• A termelő megkapja a vezérlést, legyárt egy objektumot, beteszi a bufferba, és felkelti a fogyasztót.
• A fogyasztó megkapja a vezérlést, de mivel nem alszik, az ébresztés elvész. A fogyasztó elalszik.
• A termelő megkapja a vezérlést, feltölti a buffert, majd aludni megy.

Mivel a folyamatokat semmi sem billentheti ki az alvásból, a program holtpontba jutott.

Ha a nyelv nem szabályozza kellőképpen a globális változókhoz való konkurens hozzáférést, akkor nem kell kimutatni a versenyhelyzetet, hiszen változót oszt meg szinkronizáció nélkül szálak között.

Megoldás szemaforokkal

A szemaforos megoldás két szemafort használ az elveszett jelek problémájának megoldásához, ezek a fillCount és az emptyCount. A fillCount a bufferban levő objektumok számát tartalmazza, míg az emptyCount az üres helyek számát tartja nyilván. Ha az egyik folyamat nulla értékűt próbál csökkenteni, akkor elalszik, de felébred, ha a megfelelő szemafor értéke pozitív (termelő esetén az emptyCount, fogyasztó esetén a fillCount).

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);
    }
}

Megoldás monitorokkal

Az alábbi pszeudokód monitoros megoldást nyújt a problémára. Mivel a monitorok implicit tartalmazzák a kölcsönös kizárást, a kritikus szakaszt nem kell külön védeni. Ez azt jelenti, hogy ez a megoldás akárhány termelővel és fogyasztóval működik módosítás nélkül. Érdemes megjegyezni, hogy monitorokkal nehezebben áll elő versenyhelyzet, mint szemaforokkal.

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);
    }
}

A fenti kódban a while kulcsszót találjuk, amikor teszteljük, hogy a buffer teli van-e. Például több fogyasztó esetén versenyhelyzet adódik, ha a kiürült bufferba új elem került. Egy másik fogyasztó eltávolíthatja az elemet. Előfordulhatna, hogy egyszerre többen próbálnának betenni, vagy kivenni elemet.

Monitorok és szemaforok nélkül

Az egy termelő és fogyasztó mintája szorosan kapcsolódik egy cső vagy egy csatorna megvalósításához. Hatékony kommunikációt tesz lehetővé monitorok, szemaforok és mutexek nélkül. Használatuk lelassítja a programot, mivel kezelésük sok időt igényel. A csövek és a csatornák azért népszerűek, mert elkerülik a szinkronizációt. Később erre egy C példát is mutatunk. Jegyezzük meg, hogy:

• Nincs szükség a közös változók atomi kezelésére, ugyanis ezek helyett olyan változókat használnak, amiket egy-egy szál kezel. Az egész túlcsordulás kezelését is lehet korrekt módon kezelni.
• A példa nem küldi aludni a szálakat. A sched_yield() csak azért van, hogy a kód szépen nézzen ki, törölhető. Kontextustól függ, hogy az alvás mellőzése mennyire elfogadható. A szálkönyvtárak rendszerint szemaforokkal vagy feltételváltozókkal kezelik az alvást. Több processzoros környezetben a szálak alvása és felébresztése ritkább, mint az adattokenek átadása, így az adatátadáson végzett atomi műveletek elkerülése előny.
• A példa nem működik több termelővel illetve fogyasztóval, mivel ekkor versenyhelyzet adódik az állapot ellenőrzésekor. Például ha két fogyasztó is úgy találja, hogy a buffer nem üres, akkor mindketten elfogyaszthatják ugyanazt az objektumot, így az elfogyasztott objektumok száma meghaladhatja a megtermeltekét.
• A példa megköveteli, hogy UINT_MAX + 1 maradék nélkül osztható legyen a buffer méretével, különben nem tudja kezelni az egészek túlcsordulását. Különben ugyanis [Count % BUFFER_SIZE] rossz indexet ad a túlcsordulás után, amikor Count az UINT_MAX után nullára vált. Egy alternatív megoldás két Idx változót kezel, egyet a termelő, egyet a fogyasztó számára, és akkor kell őket növelni, amikor a Count változót kellene. Ekkor a növelés formája: Idx = (Idx + 1) % BUFFER_SIZE.

volatile unsigned int produceCount = 0, consumeCount = 0;
TokenType buffer[BUFFER_SIZE];

void producer(void) {
    while (1) {
        while (produceCount - consumeCount == BUFFER_SIZE)
            sched_yield(); /* `buffer` is full */

        /* You must update the field in the buffer _before_ incrementing your
         * pointer.
         */
        buffer[produceCount % BUFFER_SIZE] = produceToken();
        ++produceCount;
    }
}

void consumer(void) {
    while (1) {
        while (produceCount - consumeCount == 0)
            sched_yield(); /* `buffer` is empty */

        consumeToken(&buffer[consumeCount % BUFFER_SIZE]);
        ++consumeCount;
    }
}

Források

• Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces

Fordítás

Ez a szócikk részben vagy egészben a Producer–consumer problem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.