Problém producenta a spotřebitele

Problém producenta a spotřebitele je jedním z klasických příkladů problémů programování souběžných procesů. Producent vyrábí určitá data a dává je do zásobníku o omezené velikosti. Spotřebitel je zase ze zásobníku odebírá. Producent nemůže přidávat data, pokud je zásobník plný, a spotřebitel nemůže odebírat data, pokud v zásobníku žádná data nejsou. Problém se řeší tak, že se producent uspí, jakmile se zásobník naplní, spotřebitel ho pak probudí, jakmile odebere data ze zásobníku. Stejně tak se postupuje u spotřebitele, když je zásobník prázdný. Při nevhodném řešení může nastat stav, kdy oba usnou a už se nikdy nevzbudí. Dojde tak k deadlocku.

Proč používat vzor producenta a spotřebitele

Vzor producenta a spotřebitele umožňuje lépe souběžně běžet cyklickým procesům, které pracují v různých rychlostech. Díky použití zásobníku jako úložného prostoru může producent vytvářet data nezávisle na rychlosti spotřebitele. Pokud je možnost tvorby dat rychlá, může producent tyto data vytvářet napřed a spotřebitel je pak bude zpracovávat ve svém vlastním tempu. Je to obzvláště vhodné například při komunikaci po síti, kdy fungují dva procesy v různých rychlostech. První proces může neustále přijímat pakety ze sítě, zatímco druhý přijaté pakety analyzuje. V tomto příkladě je první proces producentem a druhý spotřebitelem. S použitím zásobníku mohou být pakety přijaté rychleji, než jsou analyzovány. Komunikace je tak velmi efektivní a minimalizuje ztrátu dat.

Zde je ukázka kódu, ve kterém může dojít k deadlocku:

int pocetPolozek = 0;

producent() {
    while (true) {
        polozka = vytvoritPolozku();
        if (pocetPolozek == VEL_ZASOBNIKU) {
            spat();
        }
        vlozPolozkuDoZasobniku(polozka);
        pocetPolozek = pocetPolozek + 1;
        if (pocetPolozek == 1) {
            vzbudit(spotrebitel);
        }
    }
}

spotrebitel() {
    while (true) {
       if (pocetPolozek == 0) {
           spat();
       }
       
       polozka = vyjmoutPolozkuZeZasobniku();
       pocetPolozek = pocetPolozek – 1;
       
       if (pocetPolozek == VEL_ZASOBNIKU - 1) {
           vzbudit(producent);
       }
       spotrebujPolozku(polozka);
    }
}

Za běžných okolností nedojde k žádnému problému. Rozběhnou se oba procesy, spotřebitel, pokud je počet položek nulový, usne. Když běží producent a zásobník není plný, vloží do něj položku, a probudí spotřebitele. A tak vše běží dál. Problém nastává v této situaci: spotřebitel zjistí, že v zásobníku nejsou žádné položky. Chystá se usnout. Pokud se v tu chvíli ale dostane na řadu producent, který přidá položku a zavolá signál probuzení spotřebitele, spotřebitel ji nepřijme, protože ještě nespí. Pak usne, po krátké době producent naplní zásobník a usne také. Nikdy se však už ani jeden neprobudí. Problém se dá vyřešit pomocí semaforů. Semafor je speciální celočíselný datový typ, asociovaný se dvěma funkcemi:

signal() – jeho zavoláním se celočíselná hodnota semaforu zvedne o 1, nahrazuje volání funkce vzbudit()
cekat() – zavolani funkce cekat() sníží hodnotu semaforu o 1; pokud je hodnota semaforu již před zavoláním 0, nahrazuje toto volání funkci spát(), dokud někdo nezavolá signal() a nezvýší tím hodnotu semaforu o 1

Obě funkce signal() a cekat() jsou nedělitelné atomické operace. Použitím semaforu nahradíme proměnnou pocetPolozek. Zde je kód, který problém řeší vhodným způsobem:

int volne = VEL_ZASOBNIKU;  	// semafor, počet volných slotů v zásobníku
int obsazene = 0;		// semafor, počet obsazených slotů v zásobníku

producent() {
       while (TRUE) {
               polozka = vytvoritPolozku();
               cekat(volne);
               vlozPolozkuDoZasobniku(polozka);
               signal(obsazene);
       }
}

spotrebitel() {
        while (TRUE) {
                cekat(obsazene);
                polozka = vyjmoutPolozkuZeZasobniku();
                signal(volne);
                spotrebujPolozku(polozka);
        }
}

Celočíselné semafory zde vlastně fungují jako zásobníky volání na probuzení, takže se žádný z nich neztratí.

Související články

Externí odkazy

An Analysis of the Producer-Consumer Problem Archivováno 17. 6. 2010 na Wayback Machine.