Primitiva cobegin a coend ......................... * původně parbegin, parend (Dijkstra 1968) * explicitně specifikuje sekvenci programu, která má být spuštěna paralelně * "abstraktní" cobegin má formát: cobegin C1 || C2 || ... || Cn coend kde každé Ci je autonomní segment kódu (blok). Poznámka: * implementace cobegin a coend v BACI se od "abstraktního" poněkud liší: - v BACI se může konstrukce cobegin / coend objevit pouze v hlavním programu - v BACI musejí být bloky Ci v cobegin / coend procedury - bloky v cobegin / coend nemohou být vnořeny - na rozdíl od "abstraktního" popisu se jako oddělovač používá znak středník, např.: begin { main } ... cobegin proc1(...); proc2(...); ... ; procN(...) coend; ... end. [] * výsledkem je vytvoření samostatného procesu pro všechna Ci * každé Ci běží nezávisle na ostatních procesech v konstrukci cobegin / coend * program pokračuje za coend až po skončení posledního Ci Příklad použití (v přednáškách používáme "abstraktní" cobegin / coend): begin { (a+b) * (c+d) - (e/f) } cobegin begin cobegin T1 := a+b || T2 := c+d coend; T4 := T1*T2 end || T3 := e/f coend; T5 := T4 - T3 end DC: Je maximálně využito paralelismu? Zkuste si převést aritmetický výraz a + b*c + d - e/f na paralelní program s cobegin/coend tak, aby bylo maximálně využito paralelismu. Jak odpovídá cobegin/coend fcím P a S? * každé Ci (segment kódu) může být dekomponováno na sekvenci příkazů p_i, můžeme psát: S(p_i1, S(p_i2, ...)) * konstrukce cobegin C1 || C2 || ... coend odpovídá následujícímu vnoření fcí P: P(C1, P(C2, ...)). * primitiva cobegin/coend rozšířením fcí S a P se stejnou vyjadřovací silou => omezené na správně vnořené precedenční grafy * jak inplementovat * obecné precedenční grafy mohou být někdy převedeny na správně vnořené pomocí čekání * 1 nebo více procesů musí čekat (u výše uvedeného grafu např. zpozdíme p6 do skončení p3 a p7) * to nemusí být vždy možné, např. pokud p6 musí běžet paralelně s p3 a p7 (např. kvůli komunikaci: není možné pokud p3 a p7 musí běžet současně s p6, aby si s ním vyměnily zprávy) Primitiva fork, join a quit ........................... * Conway, asi 1963 * možnost obecnějšího popisu paralelních aktivit než cobegin/coend Funkce primitiv: * fork x -- provedení primitiva fork způsobí spuštění nového procesu od příkazu označeného návěštím x; nový proces bude běžet paralelně s původním procesem * quit -- provedení tohoto primitiva ukončí proces * join t, y -- atomicky (= nedělitelně) provede: t := t - 1; if t = 0 then goto y; Příklad: výpočet výrazu (a+b)*(c+d)-(e/f) n := 2; fork x3; m := 2; fork x2; t1 := a + b; join m, x4; quit; x2: t2 := c + d; join m, x4; quit; x4: t4 := t1 * t2; join n, x5; quit; x3: t3 := e/f; join n, x5; quit; x5: t5 := t4-t3; Poznámka: V některých textech se uvádí pro tato primitiva poněkud odlišná sémantika: primitivum quit se neuvádí, primitivum join má význam join + quit. Tato modifikace je méně obecná a vychází z pozorování, že join a quit se často užívají společně. [] Vidíme, že je zápis je méně čitelný, než primitiva cobegin a coend, ale postačuje pro popis libovolného precedenčního grafu. Příklad (popis grafu na obr. (d)): t6 := 2; t8 := 3; P1; fork x2; fork x5; fork x7; quit; x2: P2; fork x3; fork x4; quit; x5: P5; join t6, x6; quit; x7: P7; join t8, x8; quit; x3: P3; join t8, x8; quit; x4: P4; join t6, x6; quit; x6: P6; join t8, x8; quit; x8: P8; quit; Hlavní nevýhoda - může být použito kdekoli v programu, např. uvnitř smyček - může program zatemnit. Hlavní výhoda - obecnost. Např. popis iterací: for i:=1 to m do for j:=1 to n do fork e; quit; e: A[i][j]:= ... join t, r; quit; r: ... V paralelních procesech často potřeba soukromých kopií proměnných, pro vytvoření paralelních procesech mohou být proměné deklarovány jako "private" deklarací typu: x1, x2,...xn: private. * soukromé proměnné existují pouze pro procesy které provedly soukromou deklaraci * nové procesy (vytvořené pomocí fork) získají vlastní kopii soukromých proměnných rodičovského procesu Mnoho operačních systémů implementuje v nějaké podobě. Zejména vlákna (threads) - více bodů běhu uvnitř jednoho procesu. Explicitní deklarace procesu ............................ Některé jazyky poskytují mechanismus pro označení úseku kódu jako samostatný proces, jehož spuštění je možné řídit za běhu. Např. jazyk Ada (US DoD, 1981): process p deklarace ... begin ... end * klíčové slovo process označuje segment kódu mezi begin a end jako samostatnou jednotku běhu * v deklaracích mohou být další definice procesů, tyto procesy jsou automaticky spuštěny při spuštění procesu p => statická deklarace procesu * dynamická deklarace - místo "process" je "process type" * definuje template, jehož instance mohou být vytvářeny dynamicky za běhu pomocí "new" Např.: process type p2 deklarace ... begin ... end begin ... q = new p2; ... end Na rozdíl od dříve popsaných primitiv cobegin / coend a fork / join / quit: * new podobné fork a end podobné quit * neumožňuje čekání na dokončení jiného procesu - chybí join nebo coend * proto nutné další mechanismy pro vzájemnou interakci Použití primitiv v reálných operačních systémech a jazycích ........................................................... * Mesa (Lampson & Redel, 1980) - libovolná procedura může být spuštěna jako proces p <- fork q(...) -- vytvoří proces p běžící podle fce q var_list <- join p; -- čeká na dokončení, přiřadí vrácené hodnoty * UNIX - na úrovni procesů - služba fork() vytvoří kopii rodičovského procesu pid = fork(); if (pid == 0) jsem potomek else jsem rodič - potomek může končit pomocí exit(x), rodič může čekat pomocí waitpid(pid, &x, volby_jak); * UNIX - na úrovni vláken - fce typu create f, join t, exit x . t = create f - jako vlákno se spouští fce programovacího jazyka . x = join t - čeká na dokončení vlákna t, vrací hodnotu předanou končícím vláknem pomocí fce exit x . exit x - odpovídá primitivu quit, předává hodnotu x (konktérní názvy fcí jsou delší a argumentů je více; např. vytvoření vlákna by vypadalo result = pthread_create(&thread, NULL, , start_routine, arg); ) Interakce procesů ----------------- Časový souběh aneb problém kritické sekce ......................................... Pokud procesy sdílejí společnou paměť, kterou čtou a zapisují, může nastat časový souběh (race condition). Uvažme například hypotetický příklad, kdy dva procesy budou asynchronně zvětšovat společnou proměnnou x: cobegin ... x := x + 1; ... || ... x := x + 1; ... coend Předpokládejme, že vysokoúrovňový příkaz x := x+1 bude přeložen jako tři strojové instrukce: 1. načtení hodnoty x do registru procesoru (LD R, x) 2. zvýšení hodnoty x (INC R) 3. zápis nové hodnoty do paměti. (LD x, R) Pokud oba procesy provedou příkaz sekvenčně, bude mít x správnou hodnotu x := x+2: Proces 1: Proces 2: LD R, x ... INC R ... LD x, R ... ... LD R, x ... INC R ... LD x, R Pokud procesy běží pseudoparalelně a nastane-li přepnutí kontextu v nevhodném okamžiku, můžeme obdržet po vykonání obou sekvencí chybnou hodnotu x := x + 1: Proces 1: LD R, x // x = 0, R = 0 Proces 2: LD R, x // x = 0, R = 0 INC R // x = 0, R = 1 LD x, R // x = 1, R = 1 Proces 1: // x = 1, R = 0 INC R // x = 1, R = 1 LD x, R // x = 1, R = 1 Výsledek je zřejmě chybný, protože by se mělo provést každé zvětšení hodnoty x (příklad - obsazování sedadel v rezervačním systému). Tentýž problém nastane i pokud máme 2 CPU, např: Proces 1: Proces 2: LD R, x ... INC R LD R, x LD x, R INC R ... LD x, R Ještě horší situace mohou nastat při přidávání prvku do seznamu apod. Časovému souběhu zabráníme tak, že nedovolíme více procesům číst a zapisovat data ve stejném okamžiku. Poznámka: ``Společnou pamětí'' nemusí být pouze hlavní paměť, může jí být i soubor. Při práci nad soubory se problém časového souběhu řeší pomocí zamykání částí souboru. Hledání časových souběhů v reálných programech není jednoduché, protože časový souběh se obvykle projevuje nedeterministicky a programy běží po většinu času bez problémů. [[ZOS 7 "problém přesněji]] Softwarová řešení časového souběhu .................................. [[staré cv. č. 5]] Problém přesněji: * máme několik sekvenčních procesů, !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! [!!!zbytek přepsala jedna dívka z papíru, může v tom být spousta chyb!!!] !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 1 procesu do kritické sekce kom. přes datovou oblast. Každý program obslouží kritickou sekci, ve které je prováděn přístup ke globálním datům. Problém - implementace procesů tak, aby v jednu chvíli byl v kritické sekci pouze jeden z nich. Předpoklad o systému: 1) zápis a čtení ze společné datové oblasti jsou nedělitelné operace; simultární reference (čtení/zápis) ke stejné oblasti více než 1 CPU povede k sekvenčním odkazům v neznámém prostředí. 2) Kritické sekce nemohou mít přiřazenou prioritu 3) Relativní rychlost procesů je neznámá. 4) program se může pozastavit mimo kritickou sekci Většinou cyklické procesy cobegin P1: loop CS1, prog1;end p2:... coend 1) Softwarové řešení ................. Cíl je aby P1 a P2 nebyly v kritické sekci současně = musí se vzájemně vylučovat. Zaručit aby nenastalo jedno ze tří typů blokování: 1) Proces mimo kritickou sekci nesmí bránit jinému procesu vtoupit do kritické sekce 2) Nesmí jeden proces opakovaně vstoupit do kritické sekce, zatímco druhý nemá šanci (hladoví) 3) 2 procesy, které chtějí vstoupit do kritické sekce odkládat řešení (ukonč. smyčkou), který vstoupí. Budeme se dívat na problémy. Problém vyřeší jednoduše, pokud program přistupuje střídsvě do Kritické sekce var turn : integer; turn := 2; cobegin P1: loop while turn = 2 do // čekací smyčka CS1; turn :=2; end loop P2: loop while turn =1 do; // čekací smyčka CS2; turn:=1; end loop coend Porušuje pravidlo 1 -------------------------------------------------- var C1,C2: boolean; C1:= C2:= true; cobegin P1:loop C1:= false; while C2 do // čekací smyčka CS1; C1:= true end loop P2: analogicky k P1 coend Je vz. vylouč., blokování 3 typu, protože oba mohou nastavit současně false. Řešení - nastavit zpátky na true po test. C2 ------------------------------------------------- var C1,C2: boolean; C1:= C2:= true; cobegin P1:loop C1:= false; if C2 then C1:=true else begin CS1; C1:= true; end end loop P2:.... coend Může vést k blokování 2 ??? pokud P2 vždy test. C1; poté co byl nastaven na false. Blokování 3 typu pokud zač. souč. a stej. rychle - test a nikdo neost. (3. typ) v<- řeš. oba while nezávisle na rychlosti. Tyto tři pokusy ilustrují některé problémy. První úplné řešení navrhl Dekker - poměrně složité. Peterson jednodušší a elegantnější algoritmus. Kdyby bylo možné vzájemné blokování; jeden z procesů by musel být stále ve while druhý zatím (1) čeká ve vlastním while nebo (2) opakovaně provádí celou smyčku (1) nemožná, protože turn dovolí jen jedenomu z procesů běžet, (2) nemožná protože P2 nastaví turn na 2 tudíž neprojede while dokud P1 neprovede svou CS. Vzájemné vyloučení? P1 chce vkročit do KS, C1 je false, zjistit zda je cesta pro P2 pro vstup do CS2: 1)P1prošel testemprot. C2 = trou => P2 se nepokouší vstoupit doKS tj. je mimo úsek ??? vymezený C2:= false a C2:= true. Pokud se P2 pokusí vstoupit, můsí nastavit turn na 2. Protože C1 je false, bude čekat dokud C1 neopustí KS. 2) P1prošel testem protože turn=2 => ať už je P2 kdekoli, zjis. že C1= false a turn=2 když dojde k testu.