r PB152 o Operační systémy Jan Staudek http://www.fi.muni.cz/usr/staudek/vyuka/ Verze: jaro 2017 Osnova přednášky □ potřeba a formy IPC (Interprocess Communication) □ IPC sdílenou pamětí □ problémy synchronizace (race conditions) □ problém kritické sekce □ řešení problému kritické sekce softwarově na úrovni aplikace □ řešení problému kritické sekce speciálními instrukcemi □ semafory □ IPC výměnou zpráv □ klasické synchronizační úlohy řešené pomocí semaforů □ monitory □ příklady synchronizace z konkrétních OS Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 2_j Motto platné již 35 let Designing correct routines for controlling concurrent activities proved to be one of the most difficult aspects of systems programming. The ad hoc techniques used by programmers of early multiprogramming and real-time systems were always vulnerable to subtle programming errors whose effects could be observed only when certain relatively rare sequences of actions occurred. The errors are particularly difficult to locate, since the precise conditions under which they appear are very hard to reproduce. THE COMPUTER SCIENCE AND ENGINEERING RESEARCH STUDY , MIT Press, 1980 Jan Staudek, FI MU Brno | PB152 Operační systémy-Komunikace a synchronizace procesů 1 ^ Potřeba a formy IPC, aktivity se dějí souběžně □ Multi-threading / souběžně existující vlákna sdílejí adresový prostor □ Multi-programming, multi-tasking / souběžně existující procesy a vlákna jsou střídavě realizované 1 nebo více procesory □ Multi-processing / participace více procesorů na multi-taskingu □ Distribuované zpracování / souběžně existující procesy jsou realizované více uzly sítě □ Souběžné aktivity mohou mezi sebou soupeřit o omezené zdroje (periferie, soubory dat, oblasti paměti, ...) □ Souběžné aktivity mohou mezi sebou komunikovat výměnou zpráv □ Souběžné aktivity mohou svoje běhy vzájemně synchronizovat Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 3 r Formy koexistence - soupeření souběžných aktivit □ souběžné procesy (vlákna) potřebují speciální podporu od OS / pro komunikace mezi sebou výměnou zpráv /sdílením paměti / pro přidělování procesoru a dalších zdrojů pro jejich běh / pro vzájemnou synchronizaci svých běhů □ soupeření - první ze dvou forem koexistence procesů / vláken / souběžné procesy se ucházejí o zdroje procesor, FAP, globálně dostupné periferie, soubory dat, ... / zdroje soupeřícím procesům typicky přiděluje OS / OS efektivně isoluje soupeřící procesy, aby se chybně neovlivňovaly / soupeřící procesy se vzájemně neznají, soupeřící proces si není vědom existence ostatních soupeřících procesů / realizace procesů musí být deterministická, reprodukovatelná, procesy musí být rušitelné a restartovatelné bez bočních efektů ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 4 Přínosy kooperace a sdílení □ možnost sdílet zdroje, informace eliminuje nutnost redundance □ dojde k urychlení výpočtu prováděného po částech paralelně □ modularizace, jednotlivé systémové funkce lze řešit samostatnými procesy či vlákny □ pohodlí, i uživatel jednotlivec může souběžně řešit více úkolů (editace, tisk, kompilace, ...) Jan Staudek, Fl MU Brno | PB152 Operační systémy-Komunikace a synchronizace procesů 6 Formy koexistence - Kooperace souběžných aktivit □ kooperace - druhá forma koexistence procesů / vláken / kooperující procesy sdílí jistou množinu zdrojů, vzájemně se znají / kooperace se dosahuje buďto implicitním sdílením zdrojů nebo explicitní komunikací kooperujících procesů / vlákna jednoho procesu obvykle kooperují, nesoupeří / procesy mohou jak kooperovat, tak i soupeřit □ proč vlákna/procesy kooperují / aby mohly sdílet jisté zdroje / aby se mohly nezávislé akce řešit souběžně, např. čtení příštího bloku dat během zpracovávání již přečteného bloku dat / aby se podporovala modulárnost architektury aplikačního systému catinfile | tr ' ' '\012' |tr '[A-Z]' '[a-z]1 | sort | uniq-c 3an Staudek, FI MU Brno | PB152 Operační systémy-Komunikace a synchronizace procesů 5 ^ Příklad problému nekonzistence při souběžnosti □ Souběžný přístup ke sdíleným údajům se musí mnohdy provádět neatomickými operacemi / Udržování konzistence dat požaduje používání mechanismů, které zajistí deterministické provádění akcí kooperujících procesů □ Příklad neatomické operace nad sdílenými proměnnými void echoO { chin = getcharO; chout = chin; putchar(chout): } / procesy P\ a P2 provádějí tutéž proceduru echo a / operují se sdílenými proměnnými chin, chout / oba procesy lze přerušit ve kterémkoliv místě / o rychlosti postupu každého z procesů nelze nic předpovědět ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 7 r Příklad problému nekonzistence při souběžnosti □ Příklad možného průběhu procesů PI a P2 Pl P2 chin = getcharO; chout = chin; putchar(chout); chin = getcharO: chout = chin; putchar(chout); / Průběh je validní / V multitaskingovém systému však nemůžeme nic předpokládat o rychlosti běhů jednotlivých procesů neřízená kooperace je zdrojem časové závislých chyb ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 8 Typové úlohy související se souběžnosti □ Synchronizace procesů - čekání procesu na událost □ Komunikace mezi procesy - výměna zpráv / rozšíření synchronizace pro koordinaci různých aktivit, ke sdělení o vzniku události se přidává sdělovaná informace zpráva □ Sdílení prostředků - soupeření (race condition) / procesy používají a modifikují sdílená data, operace zápisu těchto dat musí být vzájemně vyloučené, operace zápisu těchto dat musí být vzájemně vyloučené s operacemi jejich čtení, operace jejich čtení být realizovány souběžně / Pro zabezpečení integrity dat musí programátor použít tzv. kritické sekce zajišťující serializaci konfliktních operací {write x write, read x write) □ Může docházet k „uváznutí" každý proces v systému čeká na událost či zprávu generovanou v některém jiném procesu v systém nebo na uvolnění vstupu do kritické sekce ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 10 Příklad problému nekonzistence při souběžnosti □ Příklad jiného možného průběhu procesů Pl a P2 Pl P2 chin = getcharO; chout = chin; putchar(chout); chin = getcharO; chout = chin; putchar(chout); / Znak načtený v Pl se ztrácí dříve než je zobrazený / Znak načtený v P2 se vypisuje v Pl i P2 3an Staudek, FI MU Brno | PB152 Operační systémy-Komunikace a synchronizace procesů 9___y Bázové formy komunikace mezi procesy □ komunikace mezi procesy - IPC, Interprocess Communication □ Formy IPC / sdílená paměť, shared memory / výměna zpráv, message passing 3an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 11__y Sdílená paměť, výměna zpráv process Ľ LAP procesu B kernel LAP jádra process A LAP procesu A FAP a w « Ol S g í > S S • * S1 m výmena zprav, message passing process A LAP procesu A sha'ed process ii LAP procesu B kernel LAP jádra 33 • A a B musí kritickými sekcemi zajistit, aby B nečetl zprávu M v době, kdy A zprávu M vytváří sdílená paměť, shared memory ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 12 Program producenta a program konzumenta Sdílená data: Producent item nextProduced; #define B UFFERJSIZE 10 typedef struct { ■ ■ ■ } item; item buffer[BUFFERSIZE]; int in = 0; int out = 0; int count = 0; Konzument: item nextConsumed; while (1) { ... I* produkce * I while (1) { while (count == B UFFERJSIZE) while (count == 0) ; I * do nothing * I ; I * do nothing * I ++count; - - count; buffer[in] - nextProduced; nextConsumed - bufferfout]; in = (in + 1) % B UFFERJSIZE; out = (out + 1) % B UFFERJSIZE; } ... I * konzumace * I} Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 14__j Příklad: sdílená vyrovnávací paměť s omezenou kapacitou □ Použití sdílené vyrovnávací paměti s omezenou kapacitou pro výměnu dat mezi Z procesy, producentem a konzumentem. Častý název úlohy: Producent/Konzument (zpráv), resp. také ,,Bounded-Buffer problem11 Rychlosti běhu producenta a konzumenta jsou vzájemně synchronizované pouze ^ těmito dvěma integritními omezeními: b|0| biu b|2| b|3| b|4| .... I.H-/I I yýb2r_ _ ^ |_yklädónl_ Producent 1. Producent nesmí , ^ přeplnit bank pamětí, ^\ musí čekat na uvolnění alespoň 1 místa ť 2. Pokud je bank pamětí prázdný, konzument musí čekat na uložení alespoň 1 zprávy m bin b|2| h[J| m l>|A-/| Producent 3an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 13___y Nutná synchronizace - Race Condition / Souběh R a W neatomickými operacemi stejné položky dat, napr. příkazy + + count a--count se musí provádět atomicky / provést se atomicky = provést se bez přerušení □ příkaz + + count bude ve strojovém jazyku implementovaný takto: registeri = count registeri = registeri + 1 count = registeri □ příkaz--count bude ve strojovém jazyku implementovaný takto: register^ = count register^ = register^ — 1 count = register^ Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 15__y Nutná synchronizace - Race Condition, 2 □ Jestliže se producent i konzument pokusí zkorigovat vyrovnávací paměť současně, mohou se interpretace instrukcí jejich programů v čase prokládat -konkrétní prokládání je ale nepredikovatelné □ Příklad: / Nechť count má iniciální hodnotu 5. / Provedení operací + + count; a--count; nesmí hodnotu count změnit / Možné proložení operací + + count; a--county. producent : register^ = count (register^ = 5) producent : register\ = register\ + 1 (register\ = 6) konzument : register2 = count (register2 = 5) konzument : register^ = register^ — 1 (register2 = 4) producent : count = register\ (count = 6) konzument : count = r agister 2 (count = 4) / Hodnota count je 4, ne správná hodnota 5. r "n Problém kritické sekce □ n procesů soupeří o právo používat jistý sdílený zdroj vzájemně výlučně □ v každém procesu z n se nachází segment kódu programu nazývaný kritická sekce, ve kterém proces vzájemně výlučně přistupuje ke sdílenému zdroji □ je potřeba zajistit, že v jisté kritické sekci sdružené s jistým zdrojem, se bude nacházet nejvýše jeden proces □ modelové prostředí pro hledání řešení problému kritické sekce / předpokládá se, že každý proces běží nenulovou rychlostí / nic se nepředpokládá o relativní rychlosti procesů / žádný proces nezůstane v kritické sekci nekonečně dlouho ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 16 Ilustrace vzájemného vyloučení □ Rychlost běhu procesů neznáme Ra - sdílený zdroj , Operace musí splňovat podmínkL bezpečnosti, safety živosti, llvellness spravedlivosti, fairness PROCESE 1 '! voi d PI j t ■ PROCESS 2 * t /VOI d P2 ! * PROCESS n *t voi d Pn wŕii 1 e (tme) { // ■hi 1 e (true) { viii 1 e [tiut| f /* preceding code */y/ /* preceding code */j • • ■ y* preceding code */s enťercritical *Ra) ; enteiciiticel {Rat; entercritical iRa.) ; /* critical section//; /* critical sectio-n */; /* critical section */; ejiitcritical (Raj ; ^ exitcritical (Eta) ; exitcritical (Ra); /* fallowing code */j 1 1 /+ following code */; } ) /* following code */; 1 ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 17 Vlastnosti správného řešení problému kritické sekce □ Dosažení vzájemného vyloučení, podmínka bezpečnosti, ,,safety" / Jestliže některý proces provádí svoji kritickou sekci, žádný jiný proces nemůže provádět svoji kritickou sekci sdruženou se stejným zdrojem □ Trvalost postupu, podmínka živosti, „liveliness", „progress" / Jestliže žádný proces neprovádí svoji kritickou sekci sdruženou s jistým zdrojem a existuje alespoň jeden proces, který si přeje vstoupit do kritické sekce sdružené se tímto zdrojem, pak výběr procesu, který do takové kritické sekce vstoupí, se nesmí odkládat □ Konečnost doby čekání, podmínka spravedlivosti, „fairness" / Po vydání žádosti jistého procesu z n procesů o vstup do jisté kritické sekce a před uspokojením tohoto požadavku může může být povolen vstup do sdružené kritické sekce nejvýše n-1 procesům ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 18 ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 19 Další vlastnosti správného řešení problému kritické sekce □ Proces, který končí svoji činnost v okamžiku, kdy se nenachází v kritické sekci, musí tak učinit bez interference s ostatními procesy □ Nelze nic předpokládat o relativní rychlosti procesů a počtu procesorů □ Proces pobývá v kritické sekci konečnou dobu Jan Staudek, Fl MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 20 y Elementární řešení problému KS - maskování přerušení □ enteringCriticalSectionO = disable Jnterrupt leavingCriticalSection() = enable Jnterrupt □ proces, který první provede vstup do kritické sekce, zamaskuje přerušení na procesoru □ vlastnosti: / uplatnitelné pouze v 1-procesorových systémech / hloupé, neefektivní řešení / plná eliminace rysů multiprogramování / kritická sekce se stává nedělitelným blokem fyzicky, nikoli logicky Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 22__j Koncept řešení problému kritické seke □ pro názornost předpokládáme existenci 2 procesů, P0 a Pi □ generická struktura procesu Pí do { enteringCriticalSectionO critical section leav ingCriticalSection () reminder section } while (1); □ procesy mohou za účelem dosažení synchronizace svých akcí sdílet společné proměnné □ počátečně připustíme činné (aktivní) čekání procesu na splnění podmínek pro vstup do kritické sekce v enteringCriticalSectionO - busy waiting Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 21 ^ Možné kategorie základen pro řešení problému KS □ Softwarové řešení nezprostředkovávané jinými službami / algoritmy, jejichž správnost se nespoléhá na žádné další služby / používají standardní instrukční repertoár (LOAD, STORE, ...) / na možnost vstupu do KS aktivně čekají, busy waiting □ Hardwarové řešení nezprostředkovávané jinými službami / algoritmy, jejichž správnost se nespoléhá na žádné další služby / používají speciální instrukce strojového jazyka (TST, XCHG, ...) / na možnost vstupu do KS aktivně čekají, busy waiting □ Softwarové řešení zprostředkované operačním systémem / potřebné služby a datové struktury poskytuje OS / na možnost vstupu do KS se čeká pasivně, ve frontě / ex. podpora volání služeb v programovacích systémech/jazycích semafory, monitory, zasílání zpráv Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 23__y r Čistě softwarové řešení boolean flag [2], void P0() while (true) { flag roi = true; while ( flag [1] /* Critical Section flag [0] = false; V remainder V } /" do nothing 7 void P1() { while (true) { flag [1] = true; while (flag [0] 1* critical section flag [1] = false; t* remainder ) ľ do nothing •/ Dosažení vzájemného vylouŕení Pole flag □ba procesy sdílí. Jakmile PO nastaví flagíOj na tme, PI nemůže vstoupit do kritické sekce. Jakmile PI nastaví flag!I] na tme, PO nemůže vstoupit do kritické sekce. Co se stane, když oba procesy současně nastaví svůj flag na true ? UVÁZNOU void mainQ { (lag [0] = false; flag [1] = false; parbegin( PO, P1); Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 24___^ Čistě softwarové řešení, Petersonovo řešení □ Petersonovo řešení nesplňuje podmínku spravedlivosti / Vlákna neuváznou, některé vlákno může ale stárnout při plně synchronním běhu vláken rozhoduje o vítězi soupeření náhodně určená hodnota proměnné turn (0 nebo 1) □ Petersonovo řešení lze generalizovat pro libovolný, předem známý počet procesů Jan Staudek, Fl MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 26 Čistě softwarové řešení, Petersonovo řešení 7; boolean flag [2]; int turn; void P0() { while (true) { flag [0] = true; turn = 1; while ( flag [1] && turn = /* critical section flag [0] = false; /* remainder } } void P1() { while (true) { flag [1] = true; turn = 0; while (flag [0] && t /* critical section flag [1] = false; /* remainder } : 1) /* do nothing 7 7; = 0) /* do nothing 7 "I; 7 } void main() { flag [0] = false; flag [1] = false; parbegin ( PO, P1); } Dosažení vzájemného vyloučení Pole flag a proměnnou turn oba procesy sdílí. Jakmile PO nastaví flag[0] na true, Pl nemůže vstoupit do kritické sekce. Jakmile Pl nastaví flagl 1] na true, PO nemůže vstoupit do kritické sekce. Vzájemnému blokování zabraňuje sdílená proměnná turn, která nabude hodnoty 0 nebo 1 i v případě souběhu příkazů turn = 1 a turn = 0. Žádný proces nemůže usurpovat kritickou sekci trvale, při výstupu vždy dá šanci vstoupit do kritické sekce procesu, se kterým soupeřil. ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 25 Hardwarová podpora synchronizace, speciální instrukce □ Monoprocesory mohou problém násobnosti vstupu do KS vyřešit zamaskováním přerušení / v multiprocesorových systémech zamaskování přerušení na jednom procesoru problém neřeší □ Ex. speciální atomické (= nepřerušitelné) synchronizační instrukce vhodné i pro multiprocesory (x86, Sparc, IBM z series, Intel IA-32 (Pentium), IA-64 (Itanium) ...) / nepřerušitelné do hlavní paměti přistupují vícekrát, nepřerušitelné ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 27 r Hardwarová podpora synchronizace, speciální instrukce □ Test-and-Set Lock, TSL REGISTER,LOCK - / získání hodnoty proměnné LOCK z FAP do registru a nastavení její nenulové hodnoty ve FAP, atomicky □ XCHG, XCHG REGISTER,LOCK- / výměna obsahu dvou paměťových míst (registr x buňka FAP a nebo příp. buňka FAP x buňka FAP) atomicky □ compare-and-swap (int *word, int testval, int newval) / testuje hodnotu proměnné (*worď) proti hodnotě testval, při shodě se nahradí hodnotu proměnné hodnotou newval; jinak ponechá původní hodnotu proměnné / vždy vrací původní hodnotu proměnné, takže místo v paměti se mění pokud vracená hodnota se shoduje s hodnotou použitou jako vzor testu (proběhne swap) Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 28___^ XCHG, princip použití paměť x registr DodDroaramv řešící vsturo a vvstuD do/z kritické sekce enter_region: MOVE REGISTER,#1 XCHG REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region: MOVE LOCK,#0 RET put a 1 in the register swap the contents of the register and lock variable was lock zero? if it was non zero, lock was set, so loop return to caller; critical region entered store a 0 in lock return to caller vyjádření v programovacím jazyky vyšší úrovně Nedělitelně vymění x a r xje lokální proměnná rje globální registr iniciálně : x := 0; repeat (xchg(x, r)) until x - 1; < critical section > xchg(x, r); 1 1 značí dostupnost kritické sekce příprava zamykací hodnoty Cykluje pokud r=0, Bylo r=1 nyní je r=0 a x=1. Uvolnění kritické sekce, r=1. Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 30__j Test-and-Set Lock, princip použití podprogramy řešící vstup a výstup do/z kritické sekce enter_region: TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET leave_region: MOVE LOCK,#0 RET | copy lock to register and set lock to 1 | was lock zero? | if it was nonzero, lock was set, so loop | return to caller; critical region entered I store a 0 in lock I return to caller vyjádření v programovacím jazyky vyšší úrovně Nedělitelně provede x:=r a r:=1 1 značí obsazenost kritické sekce xje lokální proměnná rje globální registr iniciálně = 0 o značí dostupnost kritické sekce repeat (test&setloc(x)) until x = 0; < critical section > r:= 0; Pokud bylo r=1, cykluje, busy waiting Pokud platilo r=0 a nyní platí r=1. Kritická sekce se uvolňuje. Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 29___y XCHG, princip použití paměť x paměť /* program mutualexclusion */ i nt const n = /* number of processes*/; i nt bolt; voi d p (i nt i) { Vtfli I e ( true) { i nt keyi = 1; do exchange (skeyi, sbolt) VUhi I e (keyi != 0) ; /* critical section */; bolt = 0; /* remainder */; } } voi d rrni n( ) { bolt = 0; parbegi n ( P(l) , P(2) , . . P(n)); bolt: synchronizační proměnná - 0 volno Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 31 ^ compare-and-swap, princip použití /* program mutualexclusion */ const i (It n = /* number of processes */; i nt bolt; voi d p (i nt i) { Wtli I e (true) { Vrfli I e (compare_and_swap{&bolt, 0, 1) == 1) /* do nothing */; /* critical section */; bolt = 0; /* remainder */; voi d rrai n() { bolt = 0; parbegi n (P{1), P(2) , - . - ,P(n)); } r "n Závěry z prvních dvou způsobů řešení □ Negativa softwarového řešení / Procesy, které žádají o vstup do svých KS, to dělají metodou „busy waiting", spotřebovávají čas procesoru / Není splněna podmínka spravedlnosti □ závěry ke speciálním instrukcím / klady: vhodné i pro multiprocesory na rozdíl od prostého zamaskování / odmaskování přerušení / negativa aktivní čekání možnost stárnutí díky náhodnosti řešení konfliktu možnost uváznutí díky činnému čekání na vstup do kritické sekce řešení nesplňuje podmínku spravedlnosti □ negativa nevadí, pokud jsou KS krátké a volané řídce / použití v jádru OS toto omezení splňuje r ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 32 ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 33 Semafory □ Synchronizační nástroj / proměnná typu semaphore nabývající hodnot - volno (podle způsobu implementace: zvednutý semafor, 1, true, ...) - obsazeno (shozený semafor, 0, falše, ...) / operace oznamuji událost (zvedám semafor, uvolňuji cestu) - časté názvy: release, signál, semSignal, V (z N L - Vrhogen), / operace čekám na událost (čekám na zvednutý semaforu a shazuji ho) detekcí události se informace o vzniku události ztrácí vyžaduje se např. zajištění volné cesty do kritické sekce - časté názvy: acquire, wait, semWait, P, (z NL - Proberen), / operace inicializace semaforu na počáteční hodnotu □ Semafory jsou službou poskytovanou procesům/vláknům implementovanou v nižší vrstvě software vůči procesům/vláknům (aplikacím) ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 34 Semafory □ Požaduje se, aby se čekání na událost realizovalo pasivně / Podpůrná vrstva potlačí běh procesu/vlákna do doby vzniku události / Standardně se semafory implementují jako služba jádra OS / Jádro OS poskytuje službu nad identifikovatelným semaforem, aplikační účel použití konkrétního semaforu si definuje aplikace □ Nechť je v semaforu S volno/obsazeno implementované 1/0 iniciální hodnotou je 1 □ Pak lze operace nad semaforem S (ATOMICKÉ VŮČI S) symbolicky vyjádřit následovně (zatím s aktivním čekáním) acquire(S) { release(S) { while S <0; 11 no-operation S++; S—; } } ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 35 Vzájemné vyloučení KS pomocí binárního semaforu Semaphore S; acquire(S); criticalSectionQ; release(S); % inicializovaný na 1 Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 36 y Implementace semaforu jako služba z rozhraní služeb OS □ Jsou potřeba dvě pomocné operace, vnitřní operace v jádru / block - potlačuje proces, který operaci acquire(S) vyvolal (běžící proces dá mezi procesy čekající na semafor) / wakeup(P) - přeřazuje čekající proces P mezi připravené procesy □ Idea implementace operací acquire(S) a release(S) v jádru acquire(S){ S. value —; if(S.value <0){ block; } } release(S){ S.value++; if (value < 0) { ...liz fronty čekajících ... 11 je odebrán process P wakeup(P); } } Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 37 ^ Implementace semaforu, 2 □ Implementace musí zaručit, že žádné dva procesy nemohou provádět operace acquireQ a/nebo releaseQ nad stejným semaforem současně □ splnění podmínkek bezpečnosti, živosti a spravedlnosti vůči žádajícím procesům je problém řešený softwarově v jádru OS / živost a spravedlnost zajistí implementace filozofie FIFO v operacích block a wakeup(P) / bezpečnost vzájemná výlučnost je dosažitelná snadno Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 38__j Implementace semaforu, 3 □ Častým řešením operace releaseQ je přesunutí procesů čekajících na zvednutí semaforu mezi připravené procesy s nastavením čítače instrukcí na zopakování operace acquireQ / pořadí aktivace procesů pak určuje dispečer □ V některých implementacích semaforů mohou jejich hodnoty nabývat i záporných hodnot, které pak vesměs vyjadřují počet čekajících aktérů na zvednutí semaforu Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 39 ^ r Implementace semaforu, 4 □ Implementace semaforu se stává problémem kritické sekce □ operace acquireQ a releaseQ musí být atomické □ na 1 procesorovém stroji lze zajistit atomicitu zamaskováním přerušení v jádru OS □ na multiprocesoru se musí použít buďto přímé softwarové řešení kritické sekce nebo se využijí speciální instrukce, pokud je procesor podporuje / „busy waitnig"nelze plně eliminovat, lze ho přesunout z aplikační úrovně (kde mohou být kritické sekce dlouhé) do úrovně jádra OS pro implementaci atomicity operací acquireQ a releaseQ □ v distribuovaném prostředí se musí použít speciální distribuované algoritmy, viz předmět PA 150 Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 40 y Semafor coby synchronizátor □ Má se provést akce B v procesu Pj až po té, co se provede akce A v procesu P; □ použije se semafor flag inicializovaný na 0 / 0 - událost nenastala, 1 událost nastala Pí: A release(flag) acquire(flag) B Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 42 Ilustrace implementace operací na semaforem semWait(s) { Willie ( compare_and_swap(s.flag, /* do nothing */,* 1) 1) s.count—; if (s.count < 0) 1 /* place this process in s.queue*/; /* block ) this process (must also set s.flag to 0)*/; s.flag = 0; semsignal(s) { Will I e ( coipare_and_5¥ap(5 . flag, 0 _/* do nothing */;_ 1) == 1) 5.count++; If (s.count <= 0) ( /* remove a process P from s.queue */; /* place process P on ready list */; 1_ s.flag Kritická sekce Kritická sekce 3an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 41___y Uváznutí a stárnutí □ Uváznutí / dva nebo více procesů neomezeně dlouho čekají na událost, kterou může generovat pouze jeden z čekající procesů / Nechť S a Q jsou dva semafory inicializované na 1 a řádky vyjadřují tok času Pí: acquire(S); acquire(Q); release(S); release(Q); Pf acquire(Q); acquire(S); release(Q); release(S); □ Stárnutí / neomezené blokování, proces nemusí být odstraněný z fronty na semafor nikdy (předbíháním procesy s vyššími prioritami, ...) 3an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 43__y Semafor, typy r □ Binárni semafor (také - mutex lock) / nabývá celočíselných hodnot z intervalu < 0,1 > / odpovídá interpretaci obsazeno/ volno / lze implementovat i instrukcemi TSL nebo XCHG / lze implementovat i přímým Petersonovým řešením □ Obecný semafor / celočíselná hodnota z intervalu < 0,n >, n > 1 / slouží např. k čítání událostí apod. / lze implementovat pouze pomocí komplexnějších funkcí jádra □ implementovatelnost obecného semaforu / binární semafor lze snadno implementovat / obecný semafor lze implementovat semaforem binárním, viz dále Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 44___^ Klasické synchronizační úlohy □ Producent - konzument (Bounded-Buffer Problém) / předávání zpráv mezi 2 procesy □ Čtenáři a písaři (Readers and Writers Problém) / souběžnost čtení a modifikace dat (v databázi, ...) □ Úloha o večeřících filozofech / ilustračně zajímavý problém pro řešení uváznutí - 5 filozofů bud myslí nebo jí -jí špagety jen 2 vidličkami - co se stane, když se všech 5 filozofů najednou chopí např. levé vidličky ? - jio přece časem zemřou hladem, děti" ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 46 Implementace obecného semaforu □ Datové struktury obecného semaforu S s maximální hodnotou C / binary-semaphore SI, S2; int C; □ Inicializace: / SI = 1; S2 = 0; C = iniciální hodnota semaforu S; a release: acquire(Sl); □ operace acquire: acquire(Sl); C-; if(C<0){ release(S 1); acquire(S2); } release(S 1); C++; if(C<0) release(S2); release(S 1); Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 45___y Řešení úlohy producent - konzument □ Potřebujeme 1 binární semafor pro vzájemné vyloučení operací s bankem bufferů - mutex / k banku bufferů smí přistoupit najednou jediný proces □ Potřebujeme 2 obecné semafory pro synchronizaci producenta a konzumenta stavem banku N bufferů - - obecný semafor pro indikaci počtu plných (full) a - obecný semafor pro indikaci počtu prázdných (empty) / co nebylo produkováno, nelze konzumovat, konzumovat lze jen když platí full > 0 / nelze produkovat do plného banku bufferů, produkovat lze jen když platí empty > 0, Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 47__y Řešení úlohy producent - konzument, 2 □ Sdílené datové struktury: / semaphore full, empty, mutex; □ Inicializace: / full - 0; empty - N; mutex - 1 □ operace producenta: a do { vytvoř data v nextp; acquire(empty); acquire(mutex); přidej nextp do buferu; release(mutex); release(full) } while (true); konzumenta: do { acquire(full); acquire(mutex); odeber data z bufferu do nextc; release(mutex); release (empty); konzumuj data z nextc } while (true); Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 48___^ Variace na úlohu producent konzument semaphore notFullA = 1, notFullB = 1; semaphore notEmpty_A = 0, notEmpty_B = 0; int buf a, buf b; threadi (...) { int var_a; while (true) { var_a =. . . ; semWait(notFull_A) buf_a = var_a; semSignal(notEmpty_A) ■ semWait (notEmpty_B) ;■*- var_a = huf_b,- semSignal(notFullB); thread B{. . .) { int var_b; while (true) { var_b =. . . ; semWait(notFull_B); buf_b = var_b; semSignal(notEmptyB) tsemWait(notEmpty_A); var_b = buf_a; semSignal(notFullA); Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 50__j Variace na úlohu producent konzument □ Mějme dva vícevláknové procesy A a B □ Každé vlákno běží cyklicky a vyměňuje si zprávu s některým vláknem druhého procesu □ Zprávou je např. číslo ukládané do sdíleného bufferu □ Musí platit / Poté co vlákno z A zpřístupní zprávu některému vláknu z B, může pokračovat v běhu až získá zprávu od tohoto vlákna z B / Poté co vlákno z B zpřístupní zprávu některému vláknu z A, může pokračovat v běhu až získá zprávu od tohoto vlákna z A / Jakmile vlákno z A zprávu zpřístupní, musí zajistit, aby ji jiné vlákno z A nepřepsalo, dokud si ji některé vlákno z B nepřevezme / Jakmile vlákno z B zprávu zpřístupní, musí zajistit, aby ji jiné vlákno z B nepřepsalo, dokud si ji některé vlákno z A nepřevezme Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 49___y Čtenáři a písaři □ operace zápisu do sdíleného zdroje musí být exklusivní, vzájemně vyloučené s jakoukoli jinou operací □ operace čtení mohou čtený zdroj sdílet □ libovolný počet procesů-čtenářů může číst jeden a tentýž zdroj současně □ v jednom okamžiku smí daný zdroj modifikovat pouze jeden proces-písař □ jestliže proces-písař modifikuje zdroj, nesmí ho současně číst žádný proces-čtenář □ čtenář není konzument, písař není producent, jde o jinou úlohu Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 51 ^ Čtenáři a písaři, 2 □ Čtenáři a písaři s prioritou čtenářů / první čtenář přistupující ke zdroji zablokuje všechny písaře, / poslední z čtenářů končící čtení zdroje uvolní přístup ke zdroji případně čekajícím písařům, písaři se vzájemně vylučují / písaři mohou stárnout, pokud bude trvale alespoň 1 čtenář přistupovat ke zdroji □ Čtenáři a písaři s prioritou písařů / první čtenář přistupující ke zdroji zablokuje všechny písaře, / poslední z čtenářů končící čtení zdroje uvolní přístup ke zdroji případně čekajícím písařům / první písař žádající vstup do kritické sekce novým čtenářům přístup ke zdroji zakáže, noví čtenáři musí čekat na pasivitu všech písařů / čtenáři mohou stárnout, pokud bude ve frontě trvale alespoň 1 písař ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 52 Čtenáři a písaři s prioritou čtenářů Sdílené datové struktury: / semaphore wrt, readcountmutex; var readcount; Inicializace: / wrt - 1; readcountmutex - 1; readcount - 0; pisar: a acquire(wrt); písař modifikuje zdroj release(wrt); čtenář: acquire(readcountmutex); readcount++; if (readcount == 1) acquire(wrt); release(readcountmutex); ... čtení sdíleného zdroje acquire(readcountmutex); readcount —; if (readcount == 0) release(wrt); release(readcountmutex); ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 53 Čtenáři a písaři s prioritou písařů Sdílené datové struktury: / semaphore wrt, rdr, rqueue, writecountmutex, readcountmutex; var readcount, writecount; Inicializace: / wrt - 1; % zajištění vzájemné vyloučení w-w I r-w rdr = 1; % blokování čtenářů chce-li zapisovat alespoň 1 písař rqueue - 1; % obecný semafor pro frontování nových čtenářů writecountmutex - 1; readcountmutex - 1; readcount = 0; writecount = 0; ŕ Čtenáři a písaři s prioritou písařů, 2 písař: acquire(writecountmutex); writecount ++; if (writecount == 1) acquire(rdr); % první z písařů zablokuje nové čtenáře release(writecountmutex); acquire(wrt); % vzájemné vyloučení písařů ... písař modifikuje zdroj ... release(wrt); acquire(writecountmutex); writecount —; if (writecount == 0) release(rdr); % poslední z písařů odblokuje nové čtenáře release(writecountmutex); ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 54 ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 55 Čtenáři a písaři s prioritou písařů, 3 čtenář: acquire(rqueue) ; % frontování dalších nových čt., pokud je alespoň 1 nový čt. blokovaný pís. CLCqilÍre(rdr); % první písař zablokuje nového čtenáře acquire(readcountmutex); readcount ++; if(readcount == 1) acquire(wrt); % písaři musí vyčkat release(readcountmutex); % na dokončení rozpracovaných čtenářů release(rdr); % čištění informací o čekajících čtenářích release(rqueue); % čištění informací o čekajících čtenářích ... čtení sdíleného zdroje ... acquire(readcountmutex); readcount —; if (readcount == 0) release(wrt); % poslední rozpracovaný čtenář připouští písaře release(readcountmutex); i Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 56 > r "n Problémy se semafory □ semafory jsou mocný nástroj pro dosažení vzájemného vyloučení a koordinaci procesů □ operace acquire(S) a release(S) jsou prováděny více procesy a jejich účinek nemusí být vždy explicitně zřejmý □ semafor s explicitním ovládáním operacemi acquire(S) a release(S) je synchronizační nástroj nízké úrovně □ Chybné použití semaforu v jednom procesu hroutí souhru všech kooperujících procesů □ příklady patologického použití semaforů: acquirers); acquire(S); releasees); acquirers); release(T); acquire(S); . Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 57 t Monitory □ Monitor je synchronizační nástroj vysoké úrovně, umožňuje bezpečné sdílení nějakého zdroje souběžnými procesy/vlákny pomocí vyvážených procedur monitor monitor-name { ... % deklarace proměnných public entry Pl(...){...} public entry P2(...){...} } □ Provádění vyvážených procedur PI, P2, ... se implicitně vzájemně vylučují (zajišťuje monitor) □ Podporují jazyky typu Java, prostředí .NET, ... Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 58 Monitory, podmínkové proměnné □ aby proces mohl čekat uvnitř provádění procedury monitoru, musí se v monitoru deklarovat proměnná typu condition, condition x, y; □ pro typ condition jsou definovány dvě operace / x.waitQ; proces, který vyvolá tuto operaci je potlačen (a uvolní monitor) až do doby, kdy jiný proces provede operaci x.signal ■/ x.signalQ; Splnění podmínky x signalizuje proces běžící v monitoru provedením operace x.signal. Operace x.signal aktivuje právě jeden proces, který posléze znovu vstoupí do monitoru, až bude monitor volný. Pokud žádný proces nečeká na splnění podmínky x, je její provedení prázdnou operací. Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 59__y Monitory, podmínkové proměnné, 2 Fronty asociované T /*-*G«G*G* s podmínkami x, y \f y ~*Q*Q> G o.S'l Ě rřinnír^ Fronta na y I vyvážená procedura Provádí . se jediná Fronta na y | vyvážená • procedura pro jediný ■ proces r~uř y.wait L. vyvážené procedura J / V monitoru se smí nacházet nejvýše 1 proces typické řešení: signalizující proces bezprostředně opustí monitor a čeká na pokračování v běhu v monitoru ve frontě urgentqueue ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů Producent-konzument pomocí monitorů, deklarace monitoru /* program producerconsumer */ monitor boundedbuffer; char buffer [JM]; int next in, nextout; int count; cond notfull, notempty; void append (char x) { if (count == N) cwait(notfull); buffer(nextin] = x» nextin ■ (nextin + L] IN; count++; /* one more item in buffer */ csignal(notempty); } void take {char x) { if {count == 0) cwait(notempty)» x = bufferjnextout]; nextout = (nextout + 1) % N; count—[ csignal(notfullJ; /* space for N items */ /* buffer pointers */ /* number of items in buffer */ /* condition variables for synchronization */ nextin = 0; nextout = 0; count = 0; /* buffer is full; avoid overflow */ /* resume any waiting consumer */ /* buffer is empty; avoid underflow */ /* one fewer item in buffer */ /* resume any waiting producer */ /* monitor body */ /* buffer initially empty */ Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 62 Producent-konzument pomocí monitorů, programy P a K void í producer() char x; while (true) { produce(x); append(x); > > void í consumer)) char x; whil« (true) { take(x); consume)x); } } void { } main() parbegin (producer, consumer); Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 61___y Výměna zpráv □ send (destination, message), receive (source, message) □ Synchronizace / Blocking send, blocking receive, randezvous / Nonblocking send, blocking receive / Nonblocking send, Nonblocking receive / blocking = čeká se na komplementární operaci, synchronní / Nonblocking = nečeká se na komplementární operaci, asynchronní □ Adresování / přímé udání identifikace cíle / nepřímé udání místa pro zprávy odebírané přijímačem, port, mailbox □ Vztah mezi vysílačem a přijímačem při nepřímém adresování / 1:1, l:n, m:l, m:n Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 63__y Mailboxy a porty r □ mailbox - schránka pro předávání zpráv / může být privátní pro dvojici komunikujících procesů / může být sdílená více procesy / OS může dělat typovou kontrolu zpráv / OS vytváří mailbox na pokyn procesu / proces je vlastník schránky, může ji rušit / schránka zaniká když její vlastník končí □ Port / mailbox patřící jednomu přijímacímu procesu a více procesům zasílajících zprávy / port vytváří přijímací proces / v modelu klient/server je přijímacím procesem server / port se ruší ukončením přijímacího procesu ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 64 Vzájemné vyloučení zprávami □ mailbox mutex sdílená n procesy □ sendQ je asynchronní operací, končí odesláním zprávy □ receiveQ je synchronní operací, čeká až je mailbox mutex neprázdná □ Inicializace: send(mutex, 'go'); □ do kritické sekce vstoupí proces P; který dokončí receiveQ jako první □ Ostatní procesy budou čekat dokud Pt zprávu ,,go"nevrátí do schránky ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů Mailboxy a porty (3) One Tg one 3ft ( b) M any to one (d) M any to many Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 65 ^ Vzájemné vyloučení zprávami, 2 Process Pf. var msg: message; repeat receive(mutex, msg); kritická sekce send(mutex, msg); zbytek procesu forever Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 67 ^ Producent - konzument zprávami Mailbox - bank k synchronizačních zpráv go Iniciální přednastavení k — synchronizačních zpráv goí mayproduce Mailbox - bank k vyrovnávacích pamětí pro produkované zprávy mayconsume ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů Producent - konzument zprávami, 3 Producer: var pmsg: message; repeat receive (mayproduce, pmsg); pmsg:= produced; send(mayconsume, pmsg); forever Consumer: var cmsg: message; repeat receive(mayconsume, cmsg); consume(cmsg); send(mayproduce, go); forever Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 70__j Producent - konzument zprávami, 2 □ Producent umísťuje položky (ve zprávách) do mailboxu / bufferu mayconsume □ Konzument může konzumovat položku bufferu obsahující zprávu s daty □ Mailbox mayproduce je počátečně vyplněna n prázdnými zprávami (n = rozměr bufferu) □ délka mayproduce se produkcí položek zkracuje a konzumací se zvětšuje □ lze podporovat více producentů a konzumentů ]an Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů Čtenáři - písař zprávami zprávami, priorita písaře □ Ke sdíleným údajům přistupuje proces controller □ Ostatní procesy ho žádají o povolení vstupu (writerequest, readrequesť), povolení obdrží získáním zprávy OK □ Konec přístupu procesy sdělují controlleru zprávou finished □ V controlleru jsou tři mailboxy, pro každý typ zprávy jeden □ Proměnná count v controlleru je inicializována na nej vyšší možný počet čtenářů (např. 100) a platí: / count > 0: nečeká žádný písař, mohou být aktivní čtenáři, controller může přijmout pouze finished ■/ count = 0:o přístup žádá pouze písař, controller mu pošle OK a čeká finished / count < 0: písař čeká na dokončení aktivních čtenářů, lze přijmout pouze finished Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 71__y Čtenáři - písaři zprávami zprávami void reader (Int 1) / \ message rnisg.- whi I e (c rue) { miag = ij aend [rsadrequsat, rmsg)j receive (mboxfil, rmag); READUHir (); rmag ■ i; send (finished, rmsg); I void writer(int jl i message rmsg? Uhi I 6 {true) [ ririHg - j; send (writerequest, rmsg); receive [mboz[j]r rmsg)f MRirEUNIT [) ; rms-g = j; send (finished, rraag); VOÍ d controller (J I v.h I (! (true) { i I (count > 0) { dokončení if [I empty (finished)) ( UŽ neaktivních receive (finiahed, mag); j Čtenář ^ count++; else if [! empty (writerequest)) potlačení receive {writereguest, mag); dalších writer_id — msg.id; I Čtenářů count = count - 100; ) else if [! empty (readrequest)) { povolí se receive (readreque^t, rosg) t čtenář count — ; send (msg.id, "OK"); ) ...... žádný aktivní čtenář povolí se písař čeká se na jeho konec a nastaví se iniciální stav i I (count 0) \ send (writer_idH "OK"); receive {finiahed, mag)f count = 1001 I čeká se na dokončení aktivních while [count < 0) I receive {finished, mgg); count++; Úloha o 5 večeřících filozofech □ Klasická synchronizační úloha / ilustračně zajímavý problém pro úvodní ilustraci uváznutí - 5 filozofů bud myslí nebo jí -jí špagety, ale jen dvěma vidličkami - co se stane, když se všech 5 filozofů najednou chopí např. levé vidličky ? -„no přece zemřou hladem, děti" Hledáme řešení - rituál / protokol -zajištující ochranu před uváznutím a stárnutím filozofů Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 72___^ Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 73___y Úloha o 5 večeřících filozofech, řešení semafory /* program diningphilosophers */ semaphore fork [5] = {l}; int i; void philosopher (int i) { while (true) { think () ; wait (fork[i]); wait (fork [(i+1) mod 5]); eat () ; signal (fork [(i + 1) mod 5]); signal(fork[i]); } } void main() { parbegin ( philosopher (0), philosopher (1), philosopher (2) philosopher (3), philosopher (4)); Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 74__j Úloha o 5 večeřících filozofech, ochrana před uváznutím □ zrušení symetrie / jeden filozof je levák, ostatní jsou praváci / levák se liší pořadím získávání vidliček □ Strava se podává n filozofům v jídelně se n — 1 židlemi / vstup do jídelny hlídá obecný semafor počátečně nastavený na kapacitu n — 1 / řešení chránící jak před uváznutím, tak i před stárnutím Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 75__y r Úloha o 5 večeřících filozofech, ochrana před uváznutím /* pro gram diningphilosophers */ semaphore fork[5] = {1}; semaphore room = {4}; int i; void philosopher (int i) { while (true) { think () ; wait (room); wait (fork[i]); wait (fork [ (i+1) mod 5]); eat () ; signal (fork [(i + 1) mod 5]), signal (fork[i]); signal (room); } } void main() { parbegin ( philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4)); } Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 76 y Úloha o 5 večeřících filozofech, řešení monitorem monitor dining controller; cond ForkReady[5]; /* condition variable for synchronization */ boolean fork[5] = {true I; /* ava liability status of each fork */ void get forks (int pid) /* pid is the philosopher id number V int left = pid; int right = (++pid) % 5; /*grant the left fork*/ if (Ifork(left) cwait(ForkReady[left]); / * queue on conditio i variable */ fork(left) = false; /*grant the right fork*/ if {! fork (right) cwait(ForkReady (right) ; / * queue on conditio i variable */ fork(right) = false: void release forks (int pid) int left = pid; int right = (++pid) % 5; /*release the left fork*/ if (empty (ForkReady [ lef t] ] /*no one is waiting for this fork V fork(left) = true; else /* awaken a process waiting on this fork V csignal(ForkReady[left] /'release the right fork*/ if (empty (ForkReady [ right] /*no one is waiting for this fork */ fork(right) = true; else /* awaken a process waiting on this fork V csignal(ForkReady[right } >; Jan Staudek, FI MU Brno | PB152 Operační systémy - Komunikace a synchronizace procesů 78 Úloha o 5 večeřících filozofech, ochrana před uváznutím □ Filozof smí uchopit vidličky pouze když jsou obě (jeho levá i pravá) volné / musí je uchopit uvnitř kritické sekce, pro řešení lze použít monitor / definuje se vektor 5 podmínkových proměnných (čekání na vidličku) / definuje se vektor indikující stav vidliček (true = volná) / definují se dvě monitorové procedury pro získání a uvolnění 2 vidliček / uváznutí nehrozí, v monitoru může bý pouze jeden filozof void philosopher [k=0 to 4] j /* the five philosopher clients */ while (true) ( ; get forks(k); /* client requests two forks via monitor */ chair Barber waits until customer gets up from the chair. zákazník opustil křeslo Customer signals barber when customer gels up from chair. payment Cashier walls for a customer lo pay. pokladník čeká na platbu Customer signals cashier that he has paid. receipt Customer waits for a receipt for payment, je zaplaceno, zák. čeká na stvrzenku Cashier signals that paymenl has been accepted. coord Wait for a barber resource to be free lo perform either the hair cutting or cashiering lunclion. Signal that a barber resource is free- ]an Staudek, FI MU Brno | PB152 Operační systémy-Komunikace a synchronizace procesů 81 Holičství, zákazník void customer () ( int custnr; p— semWait (max_capacity) ; enter_shop{); s&mwait (mutexl) ; custnr - count; count*+; <- pořadové číslo zákazníka generované po jeho vstupu do holičství v holičství se může nacházet nejvýše 20 zákazníků semslgnal(mutexl) j fsemWait(sofa); ^- sit_on_sofa(); semWait(barber_chair); ^— get_up_f rom_sof a [) ; semSignal(sofa); 3it_in_barber_criairO ; r semWait (Tmjtex2) ; enqueuel(custnr); semSignal(cust ready); ^— I- semSignal (mutex2 ) ; semWait(finished[custnr]}; leave_barber_chair[); semSignal(leave_b_chair); pay()j semSignal(payment) j semWait(receipt); exit_shop[); semSignal(max_capacity) -generování pořadového čísla zákazníky v kritické sekci [mutexl} až 4 nejdéle čekající zákazníci sedí na pohovce (obsluha FIFO), případní ostatní (až do 20) čekají ve stoje v čekáme jen tri zákazníci mohou být obsluhování soubéžné (obsluha FIFO) další zákazník může vstát z pohovky (uvolnit na ní místo) a jít ke křeslům holičů, až bude některý holič volný zákazník se staví do fronty na volné křeslo a — budí holiče zákazník je ostříhaný, říká holič zákazník opouští holičského křesla zákazník platí zákazník dostává potvrzení o zaplacení zákazník odchází ]an Staudek, FI MU Brno | PB152 Operační systémy-Komunikace a synchronizace procesů 83 Holičství, holič a pokladna void barber(J int b_cust; while ttrue) ( semWait(cust_ready)j ĽsemWait (tiiutex2) ; dequeuel