Kódování:  ASCII - ISO Latin 2 - MS Windows - Kameníci - Jiné

Přepínání procesů, časový souběh

Úkolem tohoto cvičení je:

Pseudoparalelní běh procesů

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.

Úloha 1: Realizace cyklického přepínání úloh

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:

Časový souběh

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:

  1. načtení hodnoty x do registru procesoru
  2. zvýšení hodnoty x
  3. zápis nové hodnoty do paměti.
Pokud oba procesy provedou příkaz sekvenčně, bude mít x správnou hodnotu x := x + 2:
     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ů.

Úloha 2: Generování časového souběhu

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í.)

Příkladové řešení úlohy 1


Lukáš Petrlík
luki@kiv.zcu.cz