Přeskočit na hlavní obsah

Otázka č. 14 - Synchronizace

Synchronizace Procesů a vláken

Vznik kolize mezi procesy​

  • Uživatelské procesy většinou synchronizaci nepotřebují a to výhradně ty, které nekomunikují s ostatními procesy
  • Jinak je to u rutin jádra
  • Rutiny Jádra přistupují velmi často ke sdíleným prostředkům a tudíž dochází ke vzniku kolizí

Cíle synchronizace​

  • zabránit konfliktům mezi procesy nebo vlákny při přístupu ke sdíleným prostředkům o Paměť, soubory, periferní zařízení..
  • více procesů se má v určitém okamžiku sejít (tzv. handshake) kvůli vzájemné dohodě nebo společné akci
  • Pozastavení běhu procesů nebo vláken, dokud nejsou splněny specifikované podmínky nebo nenastane určitá událost
  • Zajistit vykonání určitých funkcí v požadovaném pořadí

2 Typy procesů​

Producent​

  • generuje šifrovací klíče
  • poskytuje data
  • načítá data

Konzument​

  • čte data
  • používá klíče
  • zpracovává data

Problémy​

  • Komunikace mezi těmito procesy nemusí fungovat z důvodů
  1. Konzument čte dříve než mu producent poskytne data
  • Konzument využívá prostředek který ještě není k dispozici
  1. Konzument přečte jednu věc dvakrát
  2. Konzument nestihne přečíst data, protože mu je producent přepíše
  3. Konzument přečte stará i nová data

Kritický kód​

  • Každý přístup ke sdílenému prostředku je potenciálně nebezpečný
  • Takový přístup označujeme jako Kritický kód
  • Je zapotřebí synchronizace aby nedocházelo k negativním souběhům procesů nebo ztrátě dat

2 Typy synchronizace​

  • Oba typy synchronizace lze kombinovat

Čekání na událost​

  • Proces čeká na událost, kterou spustí jiný proces, čímž mu dá najevo, že svůj úkol splnil
  • Tento typ řeší problém s rozdílnými rychlostmi mezi procesy

Vzájemné vyloučení​

  • Synchronizace musí zabránit přístupu dvou procesů k jednomu prostředku (zabránit vykonávání kritického kódu nad jedním prostředkem)
  • Pokud jeden proces zahájil vykonávání kritického kódu, nesmí jiný proces přistoupit k prostředku, dokud proces nedokončí poslední instrukci kritického kódu

Synchronizační prostředky​

Binární semafor​

  • Logický sdílený prostředek
  • Velmi podobné funkci semaforů pro řízení dopravy o Avšak nejsou řízeny prostředky jako jsou auta, motorky.. ale časovou funkcí(přepínají se po čase, nikoliv na žádosti dopravních prostředků (procesů))
  • Nejpodobnější jsou jim dvoustavové semafory železniční tratě o Čekání před červeným semaforem a automatické nastavení na zelenou po projetí vlaku celým úsekem zajišťují vzájemné vyloučení tj. nejvýše jeden vlak může v libovolním okamžiku projiždět daným úsekem
  • Patří mezi nejdéle známe a používané synchronizační prostředky
  • Hlavní výhodou použití bin. Semaforů je jejich jednoduchá sémantika (jednoduchý princip)
  • Nevýhoda při rychlosti
  • Aby byl semafor funkční, musí se testování hodnoty semaforu a jeho nastavení v operaci dít atomicky tj. nesmí být přerušeno přepnutím kontextu
  • 2 Stavy
    • Červená
      • Pokud je semafor ve stavu červená - prostředek je využíván jiným procesem
      • Žádný jiný proces nesmí dovnitř dokud se stav nezmění na zelenou
    • Zelená
      • Pokud je semafor ve stavu zelená – prostředek není využíván jiným procesem
      • Proces si ho může zabrat pro sebe
  • 2 Metody
    • Wait
      • Pokud je proces ve stavu zelená, přepne se do stavu červená
      • Pokud je semafor ve stavu červená, zavolá se na proces metoda wait
      • Proces čeká dokud proces neuvolní prostředek
    • Signal
      • Když proces chce přistoupit na prostředek operaci signal, která přempne semafor na zelenou
  • Použití
    • Lze použít k zajištění vzájemného vyloučení nad kritickým kódem, kde má však silnou konkurenci v MUTEXU( pokud je MUTEX k dispozici, měl by být použit přednostně )
    • Nezastupitelnou roli hraje v synchronizaci producenta a konzumenta nad sdílenou pamětí

MUTEX​

  • Mutual exclusion
  • Synchronizační prostředek, jenž se od binárního semaforu liší v jediném avšak velmi podstatném směru: MUTEX může být uvolněn pouze procesem, který daný MUTEX drží( vstoupil přes něj do kritického kódu )
  • MUTEX může být uzamčen vícekrát jedním procesem
  • Určen 2 hodnotami
  • 2 Hodnoty
    • Identifikátor procesu, jenž MUTEX drží (pokud takový proces existuje, jinak není tato hodnota definována)
    • Počet uzamčení MUTEXU nad nímž jsou definovány 2 atomické operace.
  • 2 Operace
    • LOCK
      • Získání/uzamčení MUTEXU
      • Je-li MUTEX volný proces se stává držitelem MUTEXU a počet uzamknutí nabývá hodnoty 1
      • Je-li vlastněn aktuálním procesem, je pouze zvýšen počet uzamknutí
      • Je-li MUTEX vlastněn jiným než aktuálním procesem, je proces zablokován a čeká na uvolnění MUTEXU
    • UNLOCK
      • Odemčení/uvolnění MUTEXU
      • Je-li MUTEX volný, je chování nedefinováno
      • Je-li vlastněn aktuálním procesem, zmenšuje se počet uzamknutí o 1 a jel-li poté nulový je MUTEX uvolněn a jeden z čekajících procesů je odblokován
      • Je-li MUTEX vlastněn jiným než aktuálním procesem, je chování nedefinováno, ale MUTEX není v žádném případě uvolněn

Uváznutí​

  • Situace, kdy dokončení první akce je podmíněno předchozím dokončením druhé akce, přičemž druhá akce může být dokončena až po dokončení první akce
  • často označovaný jako ‚Co bylo dříve? Slepice nebo vejce?
  • Aby došlo k uváznutí musí být splněna jedna z 4 tzv. Coffmanových podmínek

Zrušení uváznutí​

  • Aplikace
    • Uživatelem – uživatel násilně ukončí jeden z procesů
    • Případě práce s databází může jednu transakci zrušit
  • Jádro
    • Uváznutí procesů v jádře se řeší rebootem

Řešení uváznutí​

  • Vyhýbání (detekce)
    • Algoritmy, které jsou schopny potenciální hrozbu odhalit
    • Velmi pomalé
    • Nebo příliš defenzivní – zbytečně vyloučí až moc potenciálních hrozeb
    • Nejznámější algoritmus – Bankéřův algoritmus
  • Ignorování
    • Používá se v Unixových systémech
    • Uživatel ukončí jeden z procesů
  • Předcházení
    • Zabránění ve splnění jedné ze 4 podmínek