Principy operačních systémů. Lekce 6: Synchronizace procesů

Principy operačních systémů

Lekce 6: Synchronizace procesů

Principy operačních systémů – Ing. Nulíček Vladimír

Kritická sekce • Při multitaskingu (multithreadingu) různé procesy často pracují nad společnou datovou strukturou (např. zápis a čtení do/z fronty) • Kritická sekce - místo programu, kde je prováděn přístup ke společným datům • Problém souběhu – v určitém momentu nemohou do kritické sekce vstoupit dva procesy • Synchronizační primitivum - má za úkol zajistit do kritické sekce exkluzivní přístup a zároveň konečnou dobu čekání na povolení ke vstupu Lekce 6: Synchronizace procesů

2


Příklad souběhu: Současný vklad a výběr


3


Řešení souběhu:


4


Problémy vznikající na kritické sekci • Data race : dva přístupy ke zdroji s výlučným přístupem ze dvou procesů bez synchronizace, alespoň jeden přístup je pro zápis • Uváznutí (deadlock): úspěšné 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. V počítači se jedná o zablokování procesů (případně vláken) způsobené křížovým čekáním na synchronizačních primitivech.


5


Problémy vznikající na kritické sekci • Blokování (blocking) přístupu do KS: situace, kdy proces, jenž žádá o vstup do kritické sekce, musí čekat, přestože je kritická sekce volná a ani o ni nežádal žádný jiný proces • Stárnutí (hladovění, starvation): situace, kdy proces čeká na podmínku, která nemusí nastat (v případě kritické sekce je touto podmínku umožnění vstupu do KS) • Livelock – podobné jako uváznutí, ale s aktivním čekáním (kdy procesy běží, ale jsou omezeny jen na určitý úsek kódu, který opakovaně žádá o přístup ke zdroji s výlučným přístupem, který vlastní některý z procesů této skupiny)


6


Problémy vznikající na kritické sekci Uváznutí Deadlock

Blokování Blocking

Stárnutí (vyhladovění) Starvation


7


Kritická sekce Při řízení přístupu do kritické sekce musí být dodrženy tyto podmínky: 1. Žádné dva procesy nesmí být současně uvnitř stejné kritické sekce. 2. Na řešení nesmí mít vliv počet a rychlost CPU. 3. Žádný proces mimo kritickou sekci nesmí blokovat jiný proces. 4. Žádný proces nesmí zůstat čekat nekonečné dlouho na kritickou sekci.


8


Vzájemné vyloučení s aktivním čekáním • • • •

Zákaz přerušení Zamykací proměnné (Lock Variations) Přesné střídání (Strict Alternation) Petersonův algoritmus


9


Zákaz přerušení • Pokud proces vstoupí do své kritické sekce, zakážou se všechna přerušení – nemůže tedy dojít k přepnutí kontextu • Jakmile proces vystoupí z kritické sekce, přerušení se znovu povolí • Není vhodné pro uživatelské procesy - hrozí nebezpečí zablokování systému • Nelze použít pro víceprocesorové systémy • Zákaz přerušení je ve většině OS umožněn pouze jádru OS jako privilegovaná instrukce • OS zpravidla vnitřně používá zákaz přerušení, aby zajistil nedělitelnost posloupností instrukcí používaných při implementaci jiných synchronizačních konstrukcí.


10


Zamykací proměnné • Softwarové řešení • Sdílená proměnná (zámek) Lock = 0 • Pokud proces vstupuje do kritické sekce, musí otestovat Lock. Je-li Lock = 0, může do kritické sekce vstoupit a nastaví Lock na 1. • Je-li Lock = 1, nemůže žádný jiný proces do kritické sekce vstoupit a musí počkat, až první proces opustí kritickou sekci a nastaví znovu Lock na 0 – aktivní čekání (busy waiting) • Toto řešení úplně nevylučuje časový souběh, pokud druhý proces vstupuje do KS v momentu, kdy ještě není přepnutá proměnná Lock (ale první proces již vstoupil do své KS)


11


Přesné střídání (Strict Alternation)


12


Přesné střídání (Strict Alternation) • Proměnná turn určuje, který z procesů smí vstoupit do kritické sekce. Je-li turn== 0, do kritické sekce může P0, je-li == 1, pak P1. • První proces vstoupí do kritické sekce • Druhý proces detekuje turn=0 a čeká až bude 1 (opakovaně testuje tuto proměnnou, tzv. aktivní čekání, busy waiting) • První proces opustí kritickou sekci, nastaví turn na 1 a povolí vstup druhému procesu • Tento postup vyžaduje pravidelné střídání přístupu obou procesů. • Problém:Nechť P0 proběhne svojí kritickou sekcí velmi rychle, turn= 1 a oba procesy jsou v nekritických částech. P0 je rychlý i ve své nekritické části a chce vstoupit do kritické sekce. Protože však turn== 1, bude čekat, přestože kritická sekce je volná.  Není splněno pravidlo 3  Řešení nepřípustně závisí na rychlostech procesů


13


Petersonův algoritmus


14


Petersonův algoritmus • 2 podprogramy: enter_region, leave_region • Proměnná turn udává, který z procesů je na řadě při přístupu do kritické sekce • V poli interested procesy indikují svůj zájem vstoupit do kritické sekce; interested[i]==TRUE znamená, že Pi tuto potřebu má • Na začátku není v kritické sekci žádný proces • Proces 0 volá enter_region(0) – Nastaví interested[0]:=true, turn:=0 – Protože interested[1]=false, nebude čekat ve smyčce • Pokud proces 1 volá enter_region(1) – Nastaví interested[1]:=true, turn:=1 – Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_region(0)) Lekce 6: Synchronizace procesů

15


Petersonův algoritmus • Na začátku není v kritické sekci žádný proces • Proces 0 volá enter_region(0) – Nastaví interested[0]:=true, turn:=0 – Protože interested[1]=false, nebude čekat ve smyčce

• Pokud proces 1 volá enter_region(1) – Nastaví interested[1]:=true, turn:=1 – Bude čekat ve smyčce, dokud se interested[0] nenastaví na false (voláním leave_region(0))


16


Petersonův algoritmus • Předpokládejme, že oba procesy zavolají enter_region 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 (aktivní čekání), proces 0 projde, proces 1 aktivně čeká

• Proces bude čekat jen tehdy, pokud druhý z procesů je na řadě a současně má zájem do kritické sekce vstoupit


17


Spin-lock s instrukcí TSL (Test and Set Lock) • 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 zámek – Pokud zámek=0, nastaví na 1 a vstoupí do KS – Pokud zámek=1 čeká • Problém časového souběhu (pokud by TSL nebyla atomická): – Jeden proces přečte zámek, vidí 0 – Druhý proces je naplánován, přečte zámek, 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 Lekce 6: Synchronizace procesů

18


Synchronizace bez aktivního čekání • Aktivní čekání mrhá strojovým časem – Může způsobit i nefunkčnost při rozdílných prioritách procesů – Např. vysokoprioritní producent zaplní pole, začne aktivně čekat a nedovolí konzumentovi odebrat položku (samozřejmě to závisí na strategii plánování procesů) • Blokování pomocí systémových atomických primitiv – sleep()místo aktivního čekání – proces se zablokuje – wakeup(process)probuzení spolupracujícího procesu při opouštění kritické sekce


19


Synchronizace bez aktivního čekání


20


Synchronizace bez aktivního čekání • Problém: Je zde konkurenční soupeření – count je opět sdílenou proměnnou • Konzument přečetl count== 0 a než zavolá sleep(), je mu odňat procesor • Producent vloží do pole položku a count== 1, načež se pokusí se probudit konzumenta, který ale ještě nespí! • Po znovuspuštění se konzument domnívá, že pole je prázdné a volá sleep() • Po čase producent zaplní pole a rovněž zavolá sleep() – spí oba! • Příčinou této situace je ztráta budícího signálu


21


Synchronizační primitiva • 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á. • Používají se tyto typy synchronizačních primitiv: – – – –

Mutex Zámky resp. Semafory Fronty zpráv Monitory


22


Mutex • •

•

•

Mutex = MUTual Exclusion (vzájemné vyloučení) Algoritmus používaný jako synchronizační prostředek, především u vícevláknových procesů (u jednovláknových nahrazován binárním semaforem). Zabraňuje tomu, aby byly současně vykonávány dva (nebo více) kritické kódy nad stejným sdíleným prostředkem, jako například globální proměnné. Mutex může nabývat dvou stavů: volný a vlastněný. K tomu udržuje dva druhy informace. Prvním je identifikátor procesu, který mutex drží. Druhým je počet uzamknutí. Počet uzamknutí je vyjádřen číslem, které aktualizuje operace lock (získání mutexu) nebo unlock (uvolnění mutexu). Cílem je zabránění více procesům držet daný mutex. Při vícenásobném uzamknutí musí být i stejný počet odemknutí.


23


Mutex • Získání mutexu – mutex je volný - proces se stává držitelem mutexu a počet uzamknutí je 1 – mutex je vlastněn aktuálním procesem - počet uzamknutí se zvýší o 1 – mutex je vlastněn neaktuálním procesem - proces se zablokuje a čeká na uvolnění mutexu

• Uvolnění mutexu – mutex je volný - nedefinovaný stav, nemůže dojít k vyššímu počtu odemčení než bylo zamčení – mutex je vlastněn aktuálním procesem - počet uzamknutí se sníží o 1, pokud je potom nulový, je uvolněn čekajícím procesům – mutex je vlastněn neaktuálním procesem - nedefinovaný stav, neaktuální proces nemůže uvolňovat mutex, ten tak nebude uvolněn Lekce 6: Synchronizace procesů

24


Semafor • Obecný synchronizační nástroj (Dijkstra, NL v r. 1965) • Semafor • Obecný – celočíselná proměnná • Binární (zámek, mutex) – hodnota 0 nebo 1 • Implementace semaforu je založena na 2 atomických operacích:  V (verhogen, též označováno jako up)  P (proberen, též označováno jako down). • Operace down otestuje stav čítače a v případě že je nulový, zahájí čekání. Je-li nenulový, je čítač snížen o jedničku a vstup do kritické sekce je povolen. • Při výstupu z kritické sekce je vyvolána operace up, která odblokuje vstup do kritické sekce pro další (čekající) proces. • Čítač je možné si představit jako omezení počtu procesů, které mohou zároveň vstoupit do kritické sekce nebo například jako počitadlo volných prostředků. • Tato implementace neodstraňuje problém aktivního čekání.


25


Odstranění aktivního čekání • V případě, že je při vyvolání operace down(P) čítač nulový, je nutné volající proces zablokovat. • Čekání je implementováno jako nekonečná smyčka (tzv. aktivní čekání), která může být přerušena pouze vnějším zásahem jiného procesu do počitadla pomocí volání operace up. • Neustálé testování stavu proměnné je možné nahradit pomocí fronty čekajících procesů. Proces je místo aktivního čekání (tj. neustálého kontrolování stavu proměnné) zařazen do fronty, ve které je uspán. • Funkce up(V) je rozšířena o průchod touto frontou, kdy je kromě zvýšení počitadla aktivován pouze proces, který je ve frontě první. Tento proces sníží počitadlo a vstoupí do kritické sekce. Ostatní procesy dále čekají v uspaném stavu.


26


Rozdíl semafor vs. mutex • Semafory se používají pro podobný účel jako mutexy, a to pro kontrolování vstupu do kritických sekcí. • Ale na rozdíl od mutexu, kdy v sekci může být pouze jeden, se semafory lze docílit, že v sekci může být více vláken. • Semafor si můžeme představit jako počítadlo s počáteční hodnotou, kterou nastaví uživatel. Vždy při vstupu do kritické sekce se čeká, dokud není hodnota semaforu větší než nula. • Pokud je, pak se hodnota zmenší o jednu a vstoupí se do kritické sekce. • Na konci sekce se hodnota semaforu o jedničku zvedne.


27


Monitor • Monitor je synchronizační primitivum, které se používá pro řízení přístupu ke sdíleným prostředkům. • Jeho zvláštností je, že jde o speciální konstrukci programovacího jazyka (musí ho tedy implementovat překladač). • Výhodou monitoru oproti jiným primitivům je jeho vysokoúrovňovost, snadněji se používá a je bezpečnější. Při jeho použití je méně pravděpodobné, že programátor udělá chybu. • Monitor se skládá z dat, ke kterým je potřeba řídit přístup, a množiny funkcí, které nad těmito daty operují. • Implementace monitoru např. v Javě (tam je hlavním synchonizačním primitivem), v .NET aj.


28


Monitor • Monitor se podobá třídě z OOP. Odlišností je to, že překladač doplní monitor o zámek, díky němuž se dosáhne vzájemné vyloučení – v jednu chvíli může být uvnitř monitoru jen jeden proces. • Když chce proces vstoupit do monitoru (tj. zavolat jeho funkci), musí nejdříve získat zámek. • Pokud zámek v tu chvíli drží někdo jiný, tak se proces zablokuje a čeká, dokud se zámek neuvolní (tj. dokud jiný proces neopustí monitor nebo nezačne čekat na podmíněnou proměnnou) • Celý proces zamykání je pro programátora transparentní. V programu se funkce monitoru volají stejně jako ostatní funkce. Kód, který provádí zamykání a odemykání, vygeneruje překladač.


29


Monitor – podmínkové proměnné • Občas je potřeba, aby proces, který je právě v monitoru, počkal na nějakou událost. Monitor poskytuje tuto funkcionalitu pomocí tzv. podmínkových proměnných. – datový typ Condition – Condition x, y • Pro typ Condition jsou definovány dvě operace – x.wait(); Proces, který zavolá tuto operaci je blokován až do doby, kdy jiný proces provede x.signal() – x.signal() Aktivuje právě jeden proces čekající na splnění podmínky x. Pokud žádný proces na x nečeká, pak x.signal()je prázdnou operací Lekce 6: Synchronizace procesů

30


Monitor – podmínkové proměnné • Když funkce monitoru potřebuje počkat na splnění podmínky, vyvolá operaci wait na podmíněné proměnné, která je s touto podmínkou svázána. • Tato operace proces zablokuje, zámek držený tímto procesem je uvolněn a proces je odstraněn ze seznamu běžících procesů a čeká, dokud není podmínka splněna. • Jiné procesy zatím mohou vstoupit do monitoru (zámek byl uvolněn). • Pokud je jiným procesem podmínka splněna, může funkce monitoru „signalizovat“, tj. probudit čekající proces pomocí operace signal


31


Struktura monitoru


32


Synchronizace pomocí zpráv


33


Synchronizace pomocí zpráv


34


Klasické synchronizační úlohy • Problém producent – konzument • Problém čtenářů a písařů • Problém večeřících filosofů


35


Producent - konzument • Dva procesy sdílejí společnou paměť (buffer) pevné velikosti N položek • Jeden proces je producent - generuje nové položky a ukládá je do vyrovnávací paměti • Paralelně běží proces konzument, který data vyjímá a spotřebovává • Procesy mohou běžet různými rychlostmi => musí být zabezpečeno, aby nedošlo k přetečení/podtečení: – Konzument musí být schopen čekat na producenta, nejsou-li data – Producent musí být schopen čekat na konzumenta, je-li buffer plný


36


Producent - konzument • Klasicky se zde sdílená paměť řeší pomocí pole, kde se z jedné strany položky přidávají a z druhé odebírají. • Index kam zapisovat/odebírat počítáme modulo velikost pole. • Kolizím zabráníme pomocí dvou semaforů, kde jeden obsahuje informaci o počtu plných prvků pole (f) a druhý o počtu prázdných prvků (e).  přidání prvku: P(e) V(f)  odebrání prvku: P(f) V(e) P=down

V=up


37


Čtenáři a písaři • • • • •

Některé procesy data jen čtou – čtenáři Jiné procesy potřebují data zapisovat – písaři Souběžné operace čtení mohou čtenou strukturu sdílet Libovolný počet čtenářů může jeden a tentýž zdroj číst současně Operace zápisu musí být exklusivní, vzájemně vyloučená s jakoukoli jinou operací (zápisovou i čtecí) • V jednom okamžiku smí daný zdroj modifikovat nejvýše jeden písař • Jestliže písař modifikuje zdroj, nesmí ho současně číst žádný čtenář


38


Čtenáři a písaři Dva možné přístupy: • Přednost čtenářů – Žádný čtenář nebude muset čekat, pokud sdílený zdroj nebude obsazen písařem. Jinak řečeno: Kterýkoliv čtenář čeká pouze na opuštění kritické sekce písařem. – Může dojít ke stárnutí (starvation) písařů • Přednost písařů – Jakmile je některý písař připraven vstoupit do kritické sekce, čeká jen na její uvolnění (čtenářem nebo písařem). Jinak řečeno: Připravený písař předbíhá všechny připravené čtenáře. – Může dojít ke stárnutí (starvation) čtenářů


39


Čtenáři a písaři s prioritou čtenářů


40


Čtenáři a písaři s prioritou písařů


41


Večeřící filosofové • 5 filosofů sedí kolem kulatého stolu • Každý filosof má před sebou talíř se špagetami • Mezi každými dvěma talíři je vidlička • Špagety jsou tak klouzavé, že filosof potřebuje 2 vidličky, aby mohl jíst • Když filosof dostane hlad, pokusí se vzít 2 vidličky; pokud uspěje, nějakou dobu jí, pak položí vidličky a pokračuje v přemýšlení


42


Večeřící filosofové • Problémy: – Uvíznutí (deadlock): Všichni filozofové zvednou levou vidličku, žádný z nich už nemůže pokračovat, – Vyhladovění (starvation): Pokud by filozofové vzali najednou levou vidličku, budou běžet cyklicky - vidí, že pravá není volná, položí… • Řešení - Dijkstra (pomocí semaforů)


43


Večeřící filosofové


44


Večeřící filosofové – ochrana proti uvíznutí


45

Principy operačních systémů. Lekce 6: Synchronizace procesů

Recommend Documents