Úkolem tohoto cvičení je:

• seznámit se s problémem producent-konzument a jeho řešením pomocí sdílené paměti a semaforů
• implementovat řešení problému producent-konzument pomocí sdíleného pole znaků a semaforů

Problém producent-konzument

V minulém cvičení jsme se seznámili s problémem kritické sekce a s jeho řešením pomocí semaforů.

Problém kritické sekce nastává v situacích, kdy procesy přistupují ke zdroji (nejčastěji ke sdílené paměti), který nemůže být v daném okamžiku sdílen více než jedním procesem. V mnoha případech by každý z procesů mohl existovat samostatně - komunikace mezi procesy slouží pouze pro synchronizaci přístupu ke zdroji.

Odlišná situace nastává, spolupracují-li dva nebo více procesů na řešení společné úlohy. V tomto druhém případě procesy o svojí existenci vědí a potřebují spolu komunikovat. Mnohé úlohy tohoto typu spadají do kategorie producent-konzument: Jeden proces (producent) vytváří bloky dat a druhý (konzument) je spotřebovává. Jako příklad si můžeme představit program generující tiskové sestavy a druhý program, který tyto sestavy tiskne na tiskárnu.

Problém producent-konzument (nazývaný někdy také problém ohraničené vyrovnávací paměti) bývá obvykle formulován takto: Dva procesy sdílejí společnou vyrovnávací paměť pevné velikosti. Producent vytváří nové bloky dat a vkládá je do vyrovnávací paměti, odkud je konzument vyjme a zpracuje. Oba procesy běží paralelně a o jejich vzájemné rychlosti nelze nic předpokládat.

Při řešení musíme počítat se situací, kdy producent chce vložit do vyrovnávací paměti položku, ale paměť je již plná. Řešením je pozastavit producenta na dobu, než konzument některou položku vyjme. Podobně musí být pozastaven konzument, pokud by chtěl vyjmout položku z vyrovnávací paměti v době, kdy žádnou položku neobsahovala. Správné řešení musí také zabránit všem časovým souběhům.

Řešení problému producent-konzument pomocí semaforů

Problém producent-konzument lze vyřešit pomocí dvou čítajících semaforů. Semafor nazvaný full bude čítat počet plných položek, semafor empty počet prázdných položek. Semafor full je na počátku nulový, semafor empty obsahuje počet položek vyrovnávací paměti. Tyto semafory slouží pro synchronizaci - zabraňují tomu, aby producent zapisoval do plné nebo konzument četl z prázdné vyrovnávací paměti.

Níže uvedené řešení používá ještě třetí semafor mutex, který zajišťuje, aby do sdílené vyrovnávací paměti v daném okamžiku přistupoval pouze jeden proces.

var 
    empty, full, mutex: semaphore;

    empty:=N;  { počet prázdných položek vyrovnávací paměti }
    full :=0;  { počet plných slotů vyrovnávací paměti }
    mutex:=1;  { semafor pro vzájemné vyloučení }

proces producent:
    while true do
    begin
        vytvoř další položku;
        P(empty);
        P(mutex);
        vlož položku do vyrovnávací paměti;
        V(mutex);
        V(full);
    end;

proces konzument:
    while true do
    begin
        P(full);
        P(mutex);
        vyjmi položku z vyrovnávací paměti;
        V(mutex);
        V(empty);
        zpracuj položku;
    end;

Úloha

Prostudujte výše uvedené řešení problému producent-konzument pomocí sdílené paměti a semaforů.

Semafor mutex nebude zapotřebí, je-li vyrovnávací paměť implementována pomocí pole. Toto tvrzení ověřte.

S použitím modulu podpory "procesů" a vlastní implementace semaforů (viz minulé cvičení) implementujte výše uvedené (Dijkstrovo) řešení problému producent-konzument s těmito vlastnostmi:

• Producent bude produkovat libovolné znaky, před vyprodukováním každého znaku bude čekat náhodnou dobu (použijte generátor pseudonáhodných čísel Turbo Pascalu).
• Konzumace každého znaku bude trvat konstantní dobu.
• Vyrovnávací paměť bude použita jako kruhový buffer.
• Aktuální stav vyrovnávací paměti (její obsazené a volné položky) průběžně znázorňujte - musí být zřejmé, které položky vyrovnávací paměti jsou právě obsazené a které jsou volné. [Nejlepší bude použít funkce modulu Crt.]
• Čítající semafory a operace P a V nad těmito semafory budou implementovány podle požadavků minulého cvičení.