Termelő-fogyasztó minta

A Wikipédiából, a szabad enciklopédiából

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[szerkeszté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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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ás[szerkesztés]

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

Fordítás[szerkeszté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.