Vysvětlete pojmy synchronizace procesů a kritická sekce

Synchronizace procesů je způsob řízení procesů tak, aby žádné dva procesy nepřistupovali zároveň ke stejným datům. Většinou se nesynchronizují procesy, ale vlákna.

Je nutné synchronizovat zejména paralelní procesy z důvodu tzv. Časově závislé chyby

  • Časové závislá chyba: vzniká podle pořadí přístupu procesu k proměnné.
    • Jeden proces načte hodnotu 10 000 a přičte k ní 5000, druhý od 10 000 odečte hodnotu 5000. Jeden proces zapíše hodnotu 15 000, ale druhý ji ihned přepíše hodnotou 5000.

Lze řešit pomocí Bernsteinových podmínek: pokud proces zapisuje do paměti, jiný proces nesmí do této paměti přistupovat.

Kritická sekce

Kritická sekce je část kódu, kterou nelze sdílet. Je třeba zajistit následující:

  • Vzájemné vyloučení: do kritické sekce smí přistupovat pouze jeden proces, který bude zapisovat
  • Dostupnost kritické sekce: proces musí mít možnost se k ní v přiměřeném čase dostat. (Pouze ty procesy, které při uvolněn kritické sekce byly přítomny u čekání mohou rozhodovat, který přistoupí další. Toto rozhodování musí skončit v konečném čase. Zabraňuje vzniku blokování, nebo deadlocku)
  • Konečné čekání: pokud chce proces přistoupit do kritické sekce, musí na něj přijít řada v konečném čase. (Ostatní procesy "předbíhají" čekající proces a neumožní mu vstoupit. Musí tedy existovat nějaké počítadlo, určující kolikrát mohou jiné procesy vstoupit do kritické sekce, než je vynucen přístup čekající procesu.) Zabraňuje vzniku stárnutí)
  • Proces je v kritické sekci konečnou dobu. Správně naprogramovaný proces je v kritické sekci pouze po nezbytně nutnou dobu.

Řešené problémy

  • Deadlock – uváznutí, procesy ze vzájemně zablokují
  • Blokování – proces do kritické sekce nemůže, i když je volná. Zbytečné čekání na uvolnění kritické sekce.
  • Stárnutí – jeden proces čeká nemožně dlouho na povolení k přístupu do kritické sekce

Algoritmy pro přístup do kritické sekce:

  • Petersonův algoritmus: proces se zeptá, zdali nějaký proces nechce do kritické sekce a pokud ano, pustí ho.
  • Bakery algoritmus: FIFO, fronta. Procesy se zařadí za sebe a postupně přistupují do kritické sekce.
  • Hardwarové řešení: funkce TestAndSet. Režie je v rámci procesoru, tato režie je poměrně vysoká a nelze ji tedy použít jako stálé řešení přístupu do kritické sekce.
  • Semafor: celočíselná proměnná, udávající přístup do kritické sekce. Má tři možné stavy: kladnou hodnotu, nulu a zápornou hodnotu. Záporné číslo udává, kolik procesů smí do kritické sekce. Nula říká, že kritická sekce je obsazená a kladná hodnota říká, že kritická sekce je obsazená a kolik procesů čeká ve frontě. Jedná se o vylepšenou frontu. Pokud proces opustí kritickou sekci, semafor sníží hodnotu o 1. Jakýkoliv přístup k semaforu musí být hlídaný, aby se dva procesy nekoukly zároveň, nezjistili že je volno a nevstoupili do kritické sekce. Na toto se používá funkce TestAndSet. Je nutné hlídat jak zápis, tak čtení.
  • Mutex (Binární semafor): Jedná se o zjednodušený semafor, který nabývá pouze stavů 0 a 1. Pokud je stav 0, proces může přistoupit do kritické sekce a změnit hodnotu na 1. Dokud je hodnota 1, žádný další proces do ní nemůže. Po opuštění kritické sekce proces nastaví stav na 0.
  • Monitor: Přístup outsourcujem a zavádíme separátní program, který se stará o přístup do kritické sekce.

Citace