Typové synchronizační úlohy PA150 o Principy operačních systémů Jan Staudek http://www.fi.muni.cz/usr/staudek/vyuka/ Verze: jaro 2020 Motto platné již 40 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 PA 150 - Komunikace a synchronizace procesů 1 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í semaforu □ monitory □ příklady synchronizace z konkrétních OS y Jan Staudek, FI MU Brno I PA150 - Komunikace a synchronizace procesu 2 J Potřeba a formy IPC, aktivity se dějí souběžně □ Multi-threading J souběžně běžící vlákna sdílejí zdroje svých procesů □ Multi-programming, multi-tasking / souběžně běžící procesy soupeří o zdroje □ Multi-processing / implementace prostředí multi-taskingu s více procesory □ 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 I PA 150 - Komunikace a synchronizace procesů 3 Formy koexistence - soupeření souběžných aktivit □ souběžné procesy (vlákna) potřebují speciální podporu od OS J 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 J pro vzájemnou synchronizaci svých běhů □ soupeření - první ze dvou forem koexistence procesů / vláken / souběžné aktivity 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í aktivity, aby se chybně neovlivňovaly / soupeřící aktivity se vzájemně neznají, soupeřící aktivita si není vědoma existence ostatních soupeřících procesů J realizace souběžných aktivit musí být deterministická, reprodukovatelná, aktivity typu transakce musí být rušitelné a restartovatelné bez bočních efektů Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 4 Formy koexistence - Kooperace souběžných aktivit □ kooperace - druhá forma koexistence procesů / vláken J kooperující procesy sdílí jistou množinu zdrojů, vzájemně se znají J 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 J 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 Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 5 Přínosy kooperace a sdílení □ možnost sdílet zdroje, eliminuje se nutnost redundance □ dojde k urychlení výpočtu prováděného po částech paralelně □ snadnější 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, FI MU Brno PA 150 - Komunikace a synchronizace procesů 6 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 J 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 echo() { chin = getchar(); chout = chin; putchar(chout); } / vlákna P\ a P2 provádějí tutéž proceduru echo a S operují se sdílenými proměnnými chin, chout J obě vlákna lze přerušit ve kterémkoliv místě / o rychlosti postupu každého z vláken nelze nic předpovědět Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 7 Příklad problému nekonzistence při souběžnosti □ Příklad možného průběhu vláken Pl a P2 Pl P2 chin = getchar(); chout = chin; putchar(chout); chin = getchar(); chout = chin; putchar(chout); / Tento průběh je validní J V multitaskingovém systému však nemůžeme nic předpokládat o rychlosti běhů jednotlivých procesů a vláken neřízená kooperace je zdrojem časové závislých chyb Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 8 Příklad problému nekonzistence při souběžnosti □ Příklad jiného možného průběhu vláken Pl a P2 Pl P2 chin = getchar(); chin = getchar(); chout = chin; chout = chin; putchar(chout); putchar(chout); J Znak načtený v Pl se ztrácí dříve než je zobrazený J Znak načtený v P2 se vypisuje v Pl i P2 Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 9 Typové úlohy související se souběžností □ Synchronizace - čekání aktivity na událost □ Komunikace mezi procesy - výměna zpráv mezi procesy J 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) S 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ě J 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 Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 10 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 Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 11 Sdílená paměť, výměna zpráv process A LAP procesu A process B LAP procesu B kernel LAP jádra I- výmena zprav, message passing process A LAP procesu A shared process B LAP procesu B kernel LAP jádra sdílená paměť, shared memory M A a B musí kritickými sekcemi zajistit, aby B nečetl zprávu M v době, kdy A zprávu M vytváří Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 12 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 procesy producent a konzument. Č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 integ řitními h|0| b|l| M2) N3) N4I omezeními: 1. Producent nesmí t Výběr přeplnit bank pamětí, musí čekat na uvolnění " alespoň 1 místa / ^ ----- h: ' C ----- Mill ... Vkládání Producent V. nu l>|2] hPl h|4| • • • • l*W] Pokud je bank pamětí prázdný, konzument musí čekat na uložení alespoň 1 zprávy 'v/ Producent Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 13 Program producenta a program konzumenta Sdílená data: Mefine BUFFERJšIZE 10 typedef struct { ... } item; item buffer[B UFFER JSIZE]; int in = 0; int out = 0; int count = 0; Producent item nextProduced; while (1) { ... I* produkce * / while (count == BUFFER JSIZE) ; I * do nothing * I +-\-count; buffer [in] = nextProduced; in = (in + 1) % B UFFER JŠIZE; Konzument: item nextConsumed; while (1) { while (count == ; / * do nothing * / - - count; nextConsumed = bufferfout]; out = (out + 1) % B UFFER JŠIZE; I* konzumace * I} Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 14 Nutná synchronizace - Race Condition / Souběžné neatomické operace se stejnou položky dat, např. 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 I PA 150 - Komunikace a synchronizace procesů 15 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: J Nechť count má iniciální hodnotu 5. / Provedení operací + + county a--county nesmí hodnotu count změnit / Možné proložení operací + + county a--county. producent : registeri = count (registeri = 5) producent : registeri = registeri + 1 (registeri = 6) konzument : register^ — count (register^ — 5) konzument : register2 = register — 1 (register = 4) producent : count = registeri (count = 6) konzument : count = register^ (count = 4) / Hodnota count je 4, ne správná hodnota 5. Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 16 Problém kritické sekce □ n aktivit soupeří o právo používat jistý sdílený zdroj vzájemně výlučně □ v každé z n aktivit se nachází segment kódu programu nazývaný kritická sekce, ve kterém aktivita přistupuje ke sdílenému zdroji vzájemně výlučně □ je potřeba zajistit, že v jisté kritické sekci sdružené s jistým zdrojem, se bude nacházet nejvýše jedna aktivita □ modelové prostředí pro hledání řešení problému kritické sekce / předpokládá se, že každý proces/vlákno běží nenulovou rychlostí / nic se nepředpokládá o relativní rychlosti procesů/váken J žádný proces/vlákno nezůstane v kritické sekci nekonečně dlouho V Jan Staudek, FI MU Brno I PA150 - Komunikace a synchronizace procesů 17 J Ilustrace vzájemného vyloučení / Rychlost běhu procesů neznáme Ra — sdílený zdroj PROCESS 1 *{ voi d Pi { vh\ I c (true) { /* preceding code * entercritical {Ra)r /* critical sectio exitcritical (Ra) ; /* following code + ^ J__ Operace musí splňovat podmínku bezpečnosti, safety živosti, tivefiness spravedlivosti, faimess : /1 PROCESS 2 *t oi d P2 whi I e (L.rje) f /* preceding code */; entercritical {Ra); /* critical section */; exitcritical (Ra); /* following code */; \ I L PROCESS n '! voi d Pn { ub'l I e (true) f /* preceding code */; entercritical (Ra): /* critical section */; exitcritical {Ra); /* following code */; > J__ / bezpečnost - do kritické sekce vstoupí jediný proces (vlákno) / živost - požadavek na vstup do kritické sekce se splní v konečném čase / spravedlivost - požadavky na vstup do kritické sekce se uspokojují v pořadí FIFO Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 18 Vlastnosti správného řešení problému kritické sekce □ Dosažení vzájemného vyloučení, podmínka bezpečnosti, „safety" S 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" S 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, „faimess" S 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 Jan Staudek, FI MU Brno PA 150 - 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, FI MU Brno PA 150 - Komunikace a synchronizace procesů 20 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 { enteringCriticalSectionQ critical section leavingCriticalSectionQ 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 enteringCriticalSectionQ - busy waiting Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 21 Elementární řešení problému KS - maskování přerušení □ enteringCriticalSection() = disable_interrupt leavingCriticalSection() = enable_interrupt □ proces, který první provede vstup do kritické sekce, zamaskuje přerušení na procesoru □ vlastnosti: / uplatnitelné pouze v 1-procesorových systémech J hloupé, neefektivní řešení J plná eliminace rysů multiprogramování J kritická sekce se stává nedělitelným blokem fyzicky, nikoli logicky Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 22 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 J používají standardní instrukční repertoár (LOAD, STO RE, ...) / na možnost vstupu do KS aktivity 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 aktivity 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 aktivita č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 I PA 150 - Komunikace a synchronizace procesů 23 Cistě softwarové řešení boolean flag [2]; void P0() < while (true) { flaq rOl = true; while (flag [1] /* critical section flag [0] = false; r remainder 7; ) void P1() { while (true) { flag [1] = true; wnne { nag [0] T critical section flag [1] = false; /" remainder V } } void main() { flag [0] = false; flag [1] = false; parbegin ( PO, P1); } ) /* do nothing 7 ; 7; ) /* do nothing 7 7 ; Dosažení vzájemného vyloučení Pole flag oba procesy sdílí. Jakmile PO nastaví flag{Qj na trne, Pl nemůže vstoupit do kritické sekce. Jakmile Pl nastaví flag{lj na trne, PO nemůže vstoupit do kritické sekce. Co se stane, když oba procesy současně nastaví svůj flag na true ? UVÁZNOU Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 24 Cistě softwarové řešení, Petersonovo řešení boolean flag [2]; int turn; void P0() { while (true) { flag [0] = true; turn = 1; while ( flag [1] && turn == 1) /* do nothing */ ; /* critical section */; flag [0] = false; /* remainder } } void P1() { 7; } void main() while (true) { flag [1] = true; turn = 0; while (flag [0] && turn == 0) /* do nothing */ ; /* critical section 7 ; flag [1] = false; /* remainder 7 } { 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 trne, Pl nemůže vstoupit do kritické sekce. Jakmile Pl nastaví flag[l] na trne, 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. Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 25 f "N Cistě softwarové řešení, Petersonovo řešení □ Petersonovo řešení nesplňuje podmínku spravedlivosti J 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, FI MU Brno PA 150 - Komunikace a synchronizace procesů 26 Hardwarová podpora synchronizace, speciální instrukce □ Monoprocesory mohou problém násobnosti vstupu do KS vyřešit zamaskováním přerušení J 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ě Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 27 Hardwarová podpora synchronizace, speciální instrukce □ Test-and-Set Lock, TSL REGISTER,LOCK- J získání hodnoty proměnné LOCK z FAP do registru a nastavení její nenulové hodnoty ve FAP, atomicky □ XCHG, XCHG REGISTER,LOCK- J 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é (*word) 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, uzamčení) Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 28 Test-and-Set Lock, princip použití podprogramy řešící vstup a výstup enter_region: TSL REGISTER,LOCK CMP REGISTER,#0 JNE enter_region RET kritické sekce I copy lock to register and set lock to 1 I was lock zero? I if it was nonzero, lock was set, so loop I return to caller; critical region entered leave_region: MOVE LOCK,#0 RET store a 0 in lock return to caller vyjádření v programovacím jazyky vyšší úrovně Nedělitelně provede x:=r a r:=1 xje lokální proměnná r je globální registr iniciálně repeat (test&setloc(x)) until x = 0; < critical section > r:= 0; 1 značí obsazenost kritické sekce 0 0 značí dostupnost kritické sekce 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 PA 150 - Komunikace a synchronizace procesů 29 XCHG, princip použití paměť x registr Dodoroaramv řešící vstuo a vvstim do/z kritické sekce enter^region: MOVE REGISTER,#1 XCHG REGISTER,LOCK CMP REGISTER,#0 JNE enter_region 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 leave_region: MOVE LOCK,#0 RET 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á r je globální registr iniciálně = 1 x := 0; repeat (xchg(x, r)) until x = 1; < critical section > xchg(x, r); 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 PA 150 - Komunikace a synchronizace procesů 30 XCHG, princip použití paměť x paměť /* program mutualexclusion */ i nt const n = /* number of processes*/; int bolt; voi d p (i nt i) { Ufli I e ( true) { i nt keyi = 1; do exchange (&keyi, Sbolt) Whi I e (keyi != 0); /* critical section */; bolt = 0; /* remainder */; } } vol d mai n() { } bolt = 0; parbegi n { P(l), p(2), , P(n)); bolt: synchronizační proměnná = 0 volno bolt -- zástrčka západka Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 31 compare-and-swap, princip použití /* program mutualexclusion */ const i nt n = /* number of processes */; int bolt; voi d p (i nt i) { Vrfli I e (true) ( VWhi I e (compareandswap {Sbolt, 0, 1) — 1) /* do nothing */; /* critical section */; bolt = 0; /* remainder +/; i } vol d nrai n{) { bolt = 0; parbegi n (P{1), P(2), . . . ,P / odpovídá interpretaci obsazeno/ volno / lze jej implementovat i instrukcemi TSL, XCHG, ... / lze jej 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 jej 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 I PA 150 - Komunikace a synchronizace procesů 43 r Implementace obecného semaforu □ Datové struktury obecného semaforu S s maximálni hodnotou C / binary-semaphore SI, S2; int C; □ Inicializace: / SI = 1; S2 = 0; C = iniciální hodnota semaforu S; □ operace acquire: a release: acquire(Sl); acquire(Sl); C++; if(C<0) if (C < 0) { release(S2); release(Sl); Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 44 Klasické synchronizační úlohy □ Producent - konzument {Bounded-Buffer Problem) S předávání zpráv mezi 2 procesy □ Čtenáři a písaři {Readers and Writers Problem) S 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 ? - jiopřece časem zemřou hladem, děti' Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 45 Řešení úlohy producent - konzument □ Potřebujeme 1 binární semafor pro vzájemné vyloučení operací s bankem bufferů - mutex S 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) S 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 PA 150 - Komunikace a synchronizace procesů 46 Řešení úlohy producent - konzument, 2 □ Sdílené datové struktury: / semaphore full, empty, mutex; □ Inicializace: / full = 0; empty = N; mutex = 1 □ operace producenta: a konzumenta: cfo { cfo { vytvoř data v nextp; acquire(full); acquire(empty); acquire(mutex); acquire(mutex); odeber data z bufferu do nextc; přidej nextp do buferu; release(mutex); release(mutex); release(empty); release(full) konzumuj data z nextc } while (true); } while (true); Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesu 47 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 číslo ukládané do sdíleného bufferu □ Řešení musí zajistit: J Poté co vlákno Al z procesu A zpřístupní zprávu některému vláknu BI z procesu B, Al může pokračovat v běhu až získá zprávu od BI J Poté co vlákno BI z procesu B zpřístupní zprávu některému vláknu Al z procesu A, BI může pokračovat v běhu až získá zprávu od Al / Jakmile vlákno Al 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 BI zprávu zpřístupní, musí zajistit, aby ji jiné vlákno z B nepřepsalo, dokud si ji některé vlákno Al nepřevezme Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesu 48 Variace na úlohu producent konzument □ N ej jednodušší řešení je použití dvou vyrovnávacích pamětí, jednu pro zprávy B^Aa jednu pro zprávy A —► B . □ Velikost každé vyrovnávací paměti musí být jedna. J Pokud by byl rozměr větší než 1, nemohli bychom zaručit validní sladění zpráv / Například, Bl mohlo obdržet zprávu od AI a poté poslalo zprávu AI. Ale pokud má buffer má více slotů, může zprávu ze slotu pro AI načíst jiné vlákno z A Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 49 Variace na úlohu producent konzument semaphore notFull A = 1, notFull B semaphore notEmpty A = 0, notEmpty int buf a, buf b; = i; B = 0; thread A(. . . ) thread B ( . . .) { ( int var a; int var b; while (true) { while (true) { * * ■ var a = . . . -r * ■ ■ var b =•..; semWait (notFull A) j*. semWait(notFull B) ; buf a = var a; / buf b = var b; semSignal (notEmpty_A) 7^ ..... semSignal (notEmpty B} } semWait(notEmpty B);4....... \"'""*semWait (notEmpty A) ; var a = buf b; / var b = buf a; semSignal(notFull B); semSignal(notFull A); } } } } Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 50 Č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 PA 150 - 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, J 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, J 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řů J čtenáři mohou stárnout, pokud bude ve frontě trvale alespoň 1 písař Jan Staudek, FI MU Brno I PA 150 - 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: acquire(wrt); • • • písař modifikuje zdroj • • • release(wrt); čtenář: acquire(readcountmutex); readcount-\--\-; i f (readcount == 1) acquire(wrt); release(readcountmutex); ... čtení sdíleného zdroje acquire(readcountmutex); readcount —; if (readcount == 0) release(wrt); release(readcountmutex); Jan Staudek, FI MU Brno PA 150 - 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 / 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; Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 54 Čtenáři a písaři s prioritou písařů, 2 písař: acquire(writecountmutex); writecount ++; if (writecount == 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); Jan Staudek, FI MU Brno PA 150 - 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. acquire(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); Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 56 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ů: acquire(S); acquire(S); release(S); m m m m m m m m m acquire(S); release(T); acquire(S); Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesu 57 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 Pl, P2, ... se implicitně vzájemně vylučují (zajišťuje monitor) □ Podporují jazyky typu Java, prostředí .NET, ... Jan Staudek, FI MU Brno PA 150 - 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 PA 150 - Komunikace a synchronizace procesů 59 Monitory, podmínkové proměnné, 2 / 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 Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 60 Producent-konzument pomocí monitorů, programy P a K void producer() { char x; while (true) { produce(x); append(x); } > void consumer() { char x; while (true) { take(x); consume(x); > > void main() { parbegin (producer, consumer); > Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 61 Producent-konzument pomocí monitorů, deklarace monitoru /* program producer-consumer */ monitor boundedbuffer; char buffer [N]; int nextin, nextout; int count; cond notfull, notempty; void append (char x) f if (count. == N) cwait (notfull) ; buffer(nextin] ■ x; nextin ■ (nextin +1) % N; count++; /* one more item in buffer */ csignal(notempty); } void take {char x) { if (count ■■ 0) cwait(notempty)j x - buffer[nextout]; nextout = (nextout + 1) % N; count—; csignal(notfull}; /* space for N items */ /* buffer pointers */ /* number of items in buffer */ /* condition variables for synchronization */ } { /* buffer is full; avoid overflow */ nextin = 0 f nextout = 0; count = 0: /* 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 PA 150 - Komunikace a synchronizace procesů 62 Výměna zpráv □ send (destination, message), receive (source, message) □ Synchronizace / Blocking send, blocking receive, randezvous J Nonblocking send, blocking receive J Nonblocking send, Nonblocking receive J blocking = čeká se na komplementární operaci, synchronní J Nonblocking = nečeká se na komplementární operaci, asynchronní □ Adresování J přímé - udání identifikace cíle J 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í J 1:1, l:n, m:l, m:n V Jan Staudek, FI MU Brno I PA150 - Komunikace a synchronizace procesů 63 J Mailboxy a porty □ mailbox - schránka pro předávání zpráv J 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 J proces je vlastník schránky, může ji rušit J schránka zaniká když její vlastník končí □ Port J 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 J v modelu klient/server je přijímacím procesem server J port se ruší ukončením přijímacího procesu Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 64 Mailboxy a porty (c) One to many [dj M any to many Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 65 Vzájemné vyloučení zprávami □ mailbox mutex sdílená n procesy □ sendQ je asynchronní operací, končí odesláním zprávy □ receive() je synchronní operací, čeká až je mailbox mutex neprázdná □ Inicializace: send(mutex, 'go'); □ do kritické sekce vstoupí proces Pí který dokončí receive() jako první □ Ostatní procesy budou čekat dokud Pí zprávu ,,go"nevrátí do schránky Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 66 Vzájemné vyloučení zprávami, 2 Process var msg: message; repeat receive(mutex, msg); kritická sekce send(mutex, msg); zbytek procesu forever mutex Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 67 Producent - konzument zprávami Mailbox -- bank k synchronizačních zpráv go Iniciální přednastavení k ^-1 synchronizačních gC I_?Prav 9°' 8<[ mayproduce go -- bank k vyrovnávacích pamětí pro produkované zprávy mayconsume Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 68 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šuj e □ lze podporovat více producentů a konzumentů Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 69 Producent - konzument zprávami, 3 Producer: var pmsg: message; repeat receive(mayproduce, pmsg); pmsg:= produceQ; send(mayconsume, pmsg); forever Consumer: var cmsg: message; repeat receive(mayconsume, cmsg); consume(cmsg); send(mayproduce, go); forever Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 70 f "N Č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, readrequest), 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 S count = 0: o přístup žádá pouze písař, controller mu pošle OK a čeká finished S count < 0: písař čeká na dokončení aktivních čtenářů, lze přijmout pouze finished Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 71 Čtenáři - písaři zprávami zprávami void reader(int i] \ message rraag; Vtfii I e (true) \ mag — ij send (readrequeat, rmsg); receive [mbox[i], rmsq); READUNIT (); rmag ■ i; send (finished, rmsg); I void writer (int ]) { message rrasg; While (true) { rmsg = j; send (writerequestj rmsg); receive (mbox[j]r rrasg); URITEUNIT Of rmsg = j; send (finished, rmsg); ) voi d controller () whi I dokončení už neaktivních I čtenářů potlačení dalších čtenářů pos/olí se čtenář žádný aktivní čtenář, povolí se písař čeká se na jeho konec a nastaví se iniciální stav čeká se na dokončení aktivních čtenářů) le (true) if (count > 0) ] if (I empty (finished)} { receive (finished, mag); count++; } el se if ( !empty (writerequeat receive (writereguest, mag writer_id = mag*id; count = ccunt - 100; } else if (!empty (readrequeat) receive (readrequest, nag) count--; send (msg.idr "OK"); } .X................................................................................ if ) i (count — 0) { aend (writer_id, "OK"); receive (finished, msg)j count = 100; ) receive (finished, msg) count++; Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 72 Úloha o 5 večeřících filozofech □ Klasická synchronizační úloha J 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 ? -„nopř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 PA 150 - Komunikace a synchronizace procesů 73 Ú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]); parbegin ( philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4)); } void main() { Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 74 Ú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 J 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 J řešení chránící jak před uváznutím, tak i před stárnutím Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 75 Úloha o 5 večeřících filozofech, ochrana před uváznutím /* program diningphilosophers */ semaphore fork[5] = {l}; 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 PA 150 - Komunikace a synchronizace procesů 76 Ú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é J musí je uchopit uvnitř kritické sekce, pro řešení lze použít monitor J 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á) J definují se dvě monitorové procedury pro získání a uvolnění 2 vidliček J uváznutí nehrozí, v monitoru může bý pouze jeden filozof void philosopher[k=0 to 4] /* the five philosopher clients */ { while (true) { ; get_forks(k); /* client requests two forks via monitor */ ; release_forks(k); /* client releases forks via the monitor */ } } Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 77 Ú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}; /* availability status of each fork */ void get_forks (int pid) /* pid is the philosopher id number */ { int left = pid; int right = (++pid) % 5; /*grant the left fork*/ if (! fork (left) cwait(ForkReady[left]); fork(left) = false; /*grant the right fork*/ if (! fork (right) cwait(ForkReady(right); fork(right) = false: } void release_f orks (int pid) { int left = pid; int right = (++pid) % 5; /*release the left fork*/ if (empty (ForkReady [left] ) fork(left) = true; /* gueue on condition variable */ /* gueue on condition variable */ /*no one is waiting for this fork */ else /* awaken a process waiting on this fork */ csignal(ForkReady[left]); /*release the right fork*/ if (empty (ForkReady [right] ) fork(right) = true; /*no one is waiting for this fork */ else /* awaken a process waiting on this fork */ csignal(ForkReady[right]); Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 78 Komplexní příklad synchronizace, holičství □ V holičství jsou tři holiči, jedna pokladna, čekárna pro 20 zákazníků s pohovkou pro 4 sedící zákazníky, jeden vchod a jeden východ □ Holičství obslouží za den až 50 zákazníků □ Požární předpisy povolují nejvýše 20 zákazníků v provozovně R arbor uliairN D Cashier Standing room area SuJ'j. Fxil Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesu 79 Komplexní příklad synchronizace, holičství □ Do plné provozovny zákazník nevstupuje □ V čekárně zákazníci podle pořadí příchodu sedí na pohovce, je-li na ní místo, nebo stojí □ Jakmile má holič volno, obsluhuje nejdéle čekajícího zákazníka □ Pohovka se udržuje stále plná, pokud jsou v čekárně alespoň 4 zákazníci □ Ostříhaný zákazník platí holiči u pokladny, holič vybírá peníze od zákazníka. Pokladna je jedna jediná. □ Holič buď stříhá zákazníka nebo přebírá peníze u pokladny nebo spí ve svém křesle - čeká na zákazníka Jan Staudek, FI MU Brno I PA 150 - Komunikace a synchronizace procesů 80 Holičství, bázové synchronizační (FIFO) semafory Semaphore Wait Operation Signal Operation max capacity az 20 Customer waits for space to enter shop. Exiting customer signals customer wailing to enter. sofa az4 Customer wails for seal on sofa. Customer leaving sofa signals customer waiting for sofa. barber chair a* 3 Customer waits for empty bnrher chain zák. vstane z pohovky až je alsp 1 holič volný Barber signals when that barbers chair is empty. cust ready Barber waits until a customer is in the chair, zák. si sedl na volné křeslo, bud! holiče Customer signals barber that customer is in the chair. finished Customer waits until his haircut is complete. zákazník čeká na dokončení ostříhání Barber signals when cutting hair of this customer is done. leave b chair Barber waits until customer gets up from the chair, zákazník sděluje, že opustil křeslo Customer signals barber when customer gels up from chair. payment Cashier wails for a customer lo pay. holič u pokladny ceká na platbu Customer signals cashier that he has paid. receipt Customer waits for a receipt for payment, zákazní čeká na stvrzenku Cashier signals that payment has been accepted. coord Wait for a barber resource to be free to perform either the hair cutting or cashiering function. Signal that a barber resource is free. Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 81 Holičství, poznámky k řešení □ Zákazníkovi se přiřadí unikátní pořadové číslo custnr S To odpovídá přebrání pořadového čísla zákazníkem při vstupu / jedinečnost bude zaručovat pomocný semafor mutexl □ Semafor finished je předefinován jako pole 50 semaforů □ Jakmile se zákazník posadí do holičského křesla provede semWait(finished[custnr], čeká na dokončení svého ostříhání na svém vlastním semaforu □ Jakmile holič ukončí stříhání svého zákazníka, provede semSignal(finished[b_cusť\), uvolní svého zákazníka Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 82 Holičství, poznámky k řešení □ Zákazník umístí své číslo do fronty enqueuel těsně před svou signalizací holičovi semaforem cust.ready □ Když je holič je připraven stříhat, odebere pomocí operace dequeuel(b_ust) nejvyšší číslo z fronty queuel a zapamatuje si je ve své lokální proměnné b_cust Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 83 Holičství, celkový program /* program barbershop2 */ semaphore max capacity = 2 0; semaphore sofa - 4; semaphore barberchair = 3, coord = 3; semaphore mutexl = 1, mutex2 = 1; semaphore custready = 0, leavebchair = 0, payment^ 0, receipt = 0; semaphore finished [50] = {0}; int count; void customer O void barber(} void cashier U { i i void main() { count := 0; parbegin (customer,. . . 50 times,, . . customer, barber, barber, barber, cashier); } □ Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 84 Holičství, zákazník void customer {} { in t custnr; i—■ semwait(max_capacity)j enter_shop{) semWait (rmitexl)j custnr = count; count*+ ; - semSignal (mutexl) ; fsemwa.lt(sola); -4- Bit_on_sofa(); semWait(barber_chair); M— get_up_from_8ofa 0 j LsemSignal(sofa) ; sit_in_barber_chair0 j semWait(imitex2)j enqueuel(custnr); semSignal(cust ready); — LsemSignal(mutex2); semWait(finished[custnr]); leave_barber_chair(); semSignal(leave_b_chair); pay(); semSignal(payment); semWait(receipt); exit_shop(); 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ů 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í semSignal (max_capacity) ^- zákazník odchází Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 85 Holičství, holič a pokladna void barber() { Iiit b_cust? while (trueJ { Ľ Ľ semWait(cust_ready); semwait(mutex2); dequeuel(b_cust); eemSignal (imitex2 J ; semwait(coord); cuthaír(}; semsignal(coord); semSignal ( f inished [b_ciist ] } eemWait [ leave_^3_chair) ; semsignal(barber_chair); čeká na zákazníka vybírá zákazníka z fronty na volné křeslo strihá sděluje zákazníkovi, že je ostrihaný čeká až zákazník opustí křeslo signalizuje volné kreslo Void cashier 0 { while (true) { eemwait(payment); LsemWait(coord); acceptjpayO ; semsignal(coord); Be mS i gna1(rece ipt); } spouští se platba vybírá se platba vydává se potvrzení o zaplacení Jan Staudek, FI MU Brno PA 150 - Komunikace a synchronizace procesů 86