Úkolem tohoto cvičení je:
Většina moderních systémů umožňuje paralelní běh několika programů. Má-li systém k dispozici pouze jeden procesor, poskytuje aplikacím zdání paralelního běhu postupným přepínáním mezi programy - v takovém případě hovoříme o běhu pseudoparalelním.
Realizaci pseudoparalelního běhu lze rozdělit na dvě části, a to na plánování procesů a přepnutí kontextu (každá část bývá realizována samostatným modulem operačního systému). Plánovač procesů (scheduler) určuje, které úloze bude procesor přidělen a přepnutí kontextu (process dispatcher) pak uloží stav aktuální úlohy a zavede stav úlohy vybrané plánovačem.
Nemůže-li proces pokračovat ve své činnosti, například čeká-li na příchod vstupních dat od jiného procesu, vzdá se dobrovolně procesoru a zablokuje se. Plánovací algoritmus zablokované procesy ignoruje. Odblokování procesu se provádí při obsluze příslušné vnější události, například při příchodu vstupních dat. Každý proces se tedy nachází v jednom ze tří základních stavů:
Každý proces je samostatnou jednotkou a systém musí uchovávat jeho stav (hodnoty registrů v době kdy neběží, ve kterém základním stavu proces je apod). Informace o stavu je obvykle uchovávána v tabulce procesů, jejíž každá položka popisuje jeden proces.
Pro plánování procesů se používají různé algoritmy, z nichž nejstarší a nejjednodušší je cyklické plánování (round robin scheduling). Procesu je přidělen časový interval, nazývaný časové kvantum, po který může běžet. Po uplynutí časového kvanta je proces pozastaven a procesor je přidělen dalšímu procesu. Proces je naplánován znovu až poté, co běžely všechny ostatní připravené procesy.
Poskytnutý modul podpory korutin rozšiřte tak, aby podporoval pseudoparalelní běh několika procedur. Rozšíření můžete provést v těchto krocích:
Pokud procesy sdílejí společnou paměť, kterou čtou a zapisují, může nastat časový souběh (race condition). Uvažme například hypotetický příklad, kdy dva procesy budou provádět příkaz
x := x + 1;
Předpokládejme, že výše uvedený příklad bude přeložen jako tři strojové instrukce:
Proces 1: registr := x; { x = 0 } registr := registr + 1; x := registr; { x = 1 } Proces 2: registr := x; { x = 1 } registr := resgistr + 1; x := registr; { x = 2 }
Nastane-li ovšem přepnutí kontextu v nevhodném okamžiku, můžeme obdržet po vykonání obou sekvencí chybnou hodnotu x := x + 1:
Proces 1: registr := x; { x = 0 } Proces 2: registr := x; { x = 0 } registr := resgistr + 1; x := registr; { x = 1 } Proces 1: { registr = 0 } registr := registr + 1; x := registr; { x = 1 }
Výsledek je zřejmě chybný, protože by se mělo provést každé zvětšení hodnoty x (příklad - obsazování sedadel v rezervačním systému).
Časovému souběhu zabráníme tak, že nedovolíme více procesům číst a zapisovat data ve stejném okamžiku. (Konkrétní mechanismus binárních a čítajících semaforů budeme implementovat příští cvičení).
Poznámka: ``Společnou pamětí'' nemusí být pouze hlavní paměť, může jí být i soubor. Při práci nad soubory se problém časového souběhu řeší pomocí zamykání částí souboru.
Hledání časových souběhů v reálných programech není jednoduché, protože časový souběh se obvykle projevuje nedeterministicky a programy běží po většinu času bez problémů.
Pomocí modulu podpory pseudoparalelního běhu procedur vytvořte procedury, které budou pracovat nad společnými daty tak, aby mohl nastat časový souběh. Časový souběh detekujte a oznamte.
(K této úloze nemám příkladové řešení.)
Lukáš Petrlík