Prostředky pro synchronizaci procesů

Aktuální verze z 10. 6. 2015, 11:51

Zakázání přerušení

• V systému se sdílením času přepíná CPU mezi procesy pouze jako důsledek přerušení
• Zakážeme-li přerušení, k přepínání nedochází
• Nejjednodušší řešení, možné pouze v jednoprocesorovém systému
• Není dovoleno v uživatelském režimu

Řešení s aktivním čekáním Základní předpoklady o systému:

1. Zápis a čtení ze společné datové oblasti jsou nedělitelné operace
2. Kritické sekce nemohou mít přiřazenou prioritu
3. Relativní rychlost procesů je neznámá
4. Proces se může pozastavit mimo kritickou sekci

Průběžně se testuje, zra už může proces do kritické sekce vstoupit - plýtvání časem CPU

Petersonovo řešení

• Na začátku není v kritické sekci žádný proces
• Proces 0 volá enter_CS(0)
  • Nastaví interested[0]:=true, turn:=0;
  • Protože interested[1]=false, nebude čekat ve smyčce
• Pokud proces 1 volá enter_CS(1)
  • Nastaví interested[1]:=true, turn:=1;
  • Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_CS(0))
• Co kdyby oba procesy volaly enter_CS téměř současně?
  • Oba nastaví interested na true
  • Oba nastaví turn na své číslo; „téměř souběžný zápis“ se ale provede sekvenčně, tj. nejdříve nastaví turn jeden, hodnota bude přepsána druhým
  • Oba se dostanou do while, proces 0 projde, proces 1 aktivně čeká

Spin-lock s instrukcí TSL

Většina současných počítačů má instrukci, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (TSL - „Test and Set Lock“) - HW podpora

• Proměnná zámek - na počátku 0
• Proces, který chce vstoupit do KS otestuje
  • Pokud 0 nastaví na 1 a vstoupí do KS
  • Pokud 1 čeká
• Problém časového souběhu (pokud by TSL nebyla atomická):
  • Jeden proces přečte, vidí 0
  • Druhý proces je naplánován, přečte, vidí 0, nastaví na 1, vstoupí do KS
  • Po naplánování první zapíše 1 a máme 2 procesy v KS
• Řešení vyžaduje HW podporu

Další možnosti

• Semafory
• Mutexy - někdy nepotřebujeme použít schopnost semaforů čítat, tj. stačila by nám pouze jejich schopnost zajistit vzájemné vyloučení => mutex
• Monitory

Předávání zpráv - primitiva send a receive

1. Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.
2. Pokud při zavolání recese není ve frontě žádná zpráva, může se recese buď zablokovat, nebo se může vrátit s chybou. Ve většině systémů je blokující.

[editovat] Synchronizační primitiva

jsou v operačních systémech prostředky, umožňující zároveň běžícím aplikacím ošetřit současný přístup ke sdíleným prostředkům. Ve smyslu algoritmu se jedná o rozhraní a jeho implementace není důležitá.

Chybné použití synchronizačních primitiv může vést k jejich neúčinnosti (tedy k prostředku stejně mohou přistoupit dva procesy najednou) nebo k deadlocku (vzájemnému zablokování).

Deadlock (česky také uváznutí) je odborný výraz pro situaci, kdy úspěšné dokončení nějaké akce je podmíněno předchozím dokončením jiné akce, přičemž tato jiná akce může být dokončena až po dokončení původní akce. Vzniká paradox, často označovaný jako Co bylo dříve? Slepice nebo vejce?.

V počítači se jedná o zablokování procesů (případně vláken) způsobené čekáním na synchronizačních primitivech. Obvykle k němu dochází v důsledku chyby při jejich programování. Pokud uváznutí nastane, řeší se například zrušením transakce (rollback) nebo násilným ukončením procesů. Některé systémy spoléhají na to, že deadlock nastává zřídka a uživatel si pomůže sám.

[editovat] K uváznutí dojde jen při splnění všech následujících podmínek:

• Vzájemné vyloučení (Mutual exclusion)

Prostředek může v jednom okamžiku používat jenom jeden proces (jinak dojde k chybě).

• Drž a čekej (Hold & wait)

Proces může žádat o další prostředky, i když už má nějaké přiděleny.

• Neodnímatelnost (No preemption)

Jakmile proces zmíněný prostředek vlastní, nelze mu ho bezpečně odejmout, musí ho sám vrátit.

• Čekání do kruhu (Circular wait)

Je možné uzavřít cyklus z procesů čekající každý na svého předchůdce – respektive k deadlocku dojde, jakmile je tento cyklus uzavřen.

Mezi synchronizační primitiva patří zámek a jejich zobecnění semafory, fronty zpráv a monitor.

Zámky a semafory bývají implementovány operačním systémem pomocí atomických operací na sdílené paměti a plánovače.

Pro synchronizaci v paralelním programování stačí atomické operace na sdílené paměti (čekají na sebe procesy na různých procesorech a tedy mohou čekat aktivně) a je možné je implementovat i bez pomoci operačního systému.

Fronty zpráv jsou primitivní operací v případě paralelního programování, ale je možné je implementovat v operačním systému i na jednom procesoru.

Monitor je možné realizovat pouze s podporou programovacího jazyka.

Korektní paralelní program - Nutné podmínky

1. Dva procesy se nesmí nacházet současně ve stejné sdružené sekci.
2. Žádné předpoklady nesmí být kladeny na rychlost a počet procesorů.
3. Pokud proces běžící mimo kritickou sekci nesmí být blokován ostatní procesy.
4. Žádný proces nesmí do nekonečna čekat na vstup do kritické sekce