Prostředky pro synchronizaci procesů
Z FAV wiki
(Rozdíly mezi verzemi)
(Založena nová stránka: 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í nedo...) |
|||
| Řádka 1: | Řádka 1: | ||
Zakázání přerušení | 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 | Řešení s aktivním čekáním | ||
Základní předpoklady o systému: | Základní předpoklady o systému: | ||
| − | + | # Zápis a čtení ze společné datové oblasti jsou nedělitelné operace | |
| − | + | # Kritické sekce nemohou mít přiřazenou prioritu | |
| − | + | # Relativní rychlost procesů je neznámá | |
| − | + | # 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í | 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 | 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 | |
| − | Monitory | + | ** 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, jejich použití a implementace|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 | Předávání zpráv - primitiva send a receive | ||
| − | + | # Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující. | |
| − | + | # 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í. | |
Verze z 29. 8. 2011, 14:57
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:
- Zápis a čtení ze společné datové oblasti jsou nedělitelné operace
- Kritické sekce nemohou mít přiřazenou prioritu
- Relativní rychlost procesů je neznámá
- 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
- Čeká-li primitivum send na převzetí zprávy příjemcem, je blokující (synchronní). Ve většině systémů je neblokující.
- 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í.
