Vz ajemn e vyloucen v distribuovan em prostred PA 150 Principy operacnch syst em u Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Verze: podzim 2020 Distribuovan e vz ajemn e vyloucen 2 Distributed Mutual Exclusion (DME) 2 Dva a/nebo vce procesu bezcch v DS obsahuj kriticke sekce, KS, sdruzene s jistym sdlenym objektem, 2 KS v techto procesech se mus pri behu procesu vzajemne vyloucit, tj. mus se provest seriove 2 Neexistuj sdlene promenne typu semafor ani nelze pro implementaci pouzt nektere lokaln jadro OS 2 Vzajemne vyloucen mus byt zalozeno vyhradne na vymene zprav, a to pomoc asynchronn vymeny zprav a bez znalosti stavu systemu jako celku 2 Proces provadejc kritickou sekci (nebo do n vstupujc) oznacme jako privilegovany proces Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 1 Distribuovan e vz ajemn e vyloucen 2 Podmnka bezpecnosti { dosahne se vzajemneho vyloucen V kazde kon guraci DS je privilegovany nejvyse jeden proces 2 Podmnka zivosti { zamezuje se starnut procesu Predpoklad { zadny proces nezustane privilegovany trvale Jestlize proces p zkous vstoupit do KS, pak se stane privilegovany v konecnem case 2 podmnka spravedlivosti, podpodmnka zivosti Bud'to { porad vstupu do KS = porad vydan zadost o vstup do KS Nebo obecnejs omezen { kazdy ostatn proces z DS sm zadajc proces predbehnout nejvyse 1x Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 2 Distribuovan e vz ajemn e vyloucen, zp usoby resen 2 Rzen prstupu ke zdroji v DS v ramci kriticke sekce muze byt zajist'ovane servery spravujcmi dane zdroje { model klient-server, zamky (locks), konstantn slozitost, typicke resen pro databazove systemy s transakcnm zpracovanm, pro zadajc procesy je resen vzajemne vylucnosti transparentn (viz transakcn zpracovan na zaver cyklu prednasek) 2 Distribuovana resen mohou byt zalozena { na predavan prznaku (token) prava vstupu do kriticke sekce mezi procesy nebo { na centralizovane sprave jedinym serverem v systemu { nebo na distribuovane dohode zadajcch procesu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 3 Distribuovan e vz ajemn e vyloucen, zp usoby resen 2 Distribuovana resen mohou regularnosti komunikacnch cest (v zavorkach se uvad slozitost) token ring, kruh { predavan prava vstupu pro kruhu (n) proces drzc pravo vstupu je privilegovany tree, strom { algoritmus Raymond (log n) zalozene na zskan souhlasu partnerskych procesu token-passing { algoritmus Suzuki-Kasami (n) casova raztka { algoritmus Ricart-Agrawala (2n–1), distribuovana fronta hlasovac kvora { algoritmus Maekawa ( √ n ), aby se proces stal privilegovany, mus zskat souhlas od jisteho kvora procesu, kazdy par kvor mus mt neprazdny prunik Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 4 DME { centralizovan e resen 2 Jeden z procesu v systemu { koordinator vstupu do KS (server) 2 Proces, ktery chce vstoupit do KS (klient), zasla koordinatorovi zpravu se zadost o vstup do KS { request 2 O porad vstupu procesu do KS rozhoduje koordinator, procesu zadajcmu o vstup do KS posla koordinator zpravu { reply { povolujc vstup do KS 2 Jakmile proces (klient) prijme zpravu reply, vstupuje do KS 2 Jakmile proces (klient) opoust KS, posla koordinatorovi zpravu release Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 5 DME { centralizovan e resen OK je zprava s vyznamem reply Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 6 DME { centralizovan e resen 2 Kazdy vstup do KS pozaduje zaslan 3 zprav request, reply, release 2 Vlastnosti za splnen podmnky bezpecnosti a zivosti algoritmus odpovda server, logicky cas procesu se pritom nemus sledovat Pocet procesu soupercch o vstup do KS nen limitovany Algoritmus nesplnuje podmnku spravedlivosti, protoze nerespektuje logicky cas v DS Vykon serveru a komunikacn vykon cest k serveru mohou predstavovat uzke msto Vypadek serveru zpusob vypadek celeho DS, vypadek klienta ostatn klienty neovlivnuje Koordinatorem muze byt jeden z procesu, ktere soutez o prstup; aby byl vybran jediny novy koordinator, mus procesy provest volebn algoritmus (viz pozdeji) Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 7 DME { Ricart, Agrawala (1981) 2 vstup do KS se res distribuovanou dohodou procesu 2 procesy udrzuj (Lamportovy) logicke hodiny, pri shode casovych raztek zadost o priorite zadosti rozhoduje (jedinecne) id procesu 2 proces zada o vstup do KS zpravou reguest rozeslanou N procesum ve skupine 2 zpravou reply osloveny proces dava zadajcmu procesu souhlas ke vstupu do KS 2 zpravy request jsou casove raztkovane (logickym casem), casove raztko urcuje prioritu kon iktnch pozadavku 2 Kdyz proces Pi chce vstoupit do KS, vygeneruje nove T Si = T Si + 1, a zasle vsem procesum request (Pi, T Si) Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 8 DME { Ricart, Agrawala (1981) 2 Kdyz proces Pj prijme zpravu request (Pi, T Si), odpovda reply procesu Pi bud'to okamzite (ani nen v KS, ani nezada o vstup do KS) nebo opozdene (je v KS nebo pozadal o vstup do KS drve) Pj pozadal o vstup do KS, ale ten mu dosud nebyl povolen, tj. rozeslal request (Pj, T Sj), ale nezskal od vsech procesu reply, pak porovnava sve T Sj s T Si prijatym v request (Pi, T Si) { je-li jeho T Sj vets nez T Si ze zpravy, posla reply Pi okamzite, protoze Pi zadal o vstup do KS drve { jinak zaslan reply procesu Pi odklada do vystupu z KS 2 Kdyz proces Pi prijme zpravu reply od vsech N–1 procesu, muze vstoupit do KS 2 Po opusten KS posla proces zpravy reply vsem procesum, kterym dosud na zpravu request neodpovedel reply Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 9 DME { Ricart, Agrawala (1981), idea programu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 10 DME { Ricart, Agrawala, pˇr´ıklad (1981) Necht' p3 nema zajem o vstup do kriticke sekce Necht' p1 a p2 pozaduj vstup do kriticke sekce soucasne Casove raztko zadosti p1 je 41 a zadosti p2 je 34. p3 na zadosti odpovda bez prodlen Kdyz p2 obdrz zadost p1, zjist, ze jeho vlastn zadost ma nizs casove raztko, tak neodpovda, drz p1 mimo hru. Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 11 DME { Ricart, Agrawala, (1981), prklad Kdyz p1 zjist, ze pozadavek p2 ma nizs casove raztko nez jeho zadost, odpovda okamzite. p2 vstoup do kriticke sekce, zskal souhlas od N − 1 procesu Kdyz p2 opust kritickou sekci, odpov na zadost p1 a p1 muze vstoupi do kriticke sekce Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 12 DME { Ricart, Agrawala, (1981), prklad 2 Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 13 DME { Ricart, Agrawala (1981) 2 Pozitivn vlastnosti je splnena podmnka bezpecnosti N–1 procesu potvrzuje zadajcmu procesu, ze do KS nevstoup dokud zadajc proces KS neopust je splnena podmnka zivosti, { kon iktn zadosti jsou reseny v porad dle behu logickeho casu Jestlize proces opustivs KS nedostane zadnou zadost o vstup do KS, muze do KS vstoupit bez zskan souhlasu ostatnch procesu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 14 DME { Ricart, Agrawala (1981) 2 Nezadouc vlastnosti Minimaln pocet zprav na jeden vstup do KS procesem je 2×(n−1), kde n je pocet procesu, coz je hodne proces mus znat identitu vsech ostatnch procesu v systemu, dynamicke doplnovan a rusen procesu je netrivialn vypadek jednoho procesu zpusob kolaps celeho systemu (stav vsech procesu je potreba trvale monitorovat) protokol je vhodny pro male, stabiln mnoziny kooperujcch procesu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 15 DME { pred av anm prznaku po kruhu 2 Procesy jsou v distribuovanem systemu usporadane do kruhu at' jiz logicky nebo fyzicky necht' kruh je jednosmerny, kazdy proces muze poslat zpravu pouze svemu (napr.) pravemu sousedovi 2 Prznak { specialn zprava { pesek 2 Prznak v DS existuje v jedinem exemplari 2 Proces, ktery chce vstoupit do KS, muze tak ucinit, az kdyz obdrz prznak 2 Proces, ktery obdrz prznak { bud'to vstoup do KS, pokud chce vstoupit do KS a po vystupu z KS prznak posle naslednkovi na kruhu { nebo, nechce-li vstupovat do KS, prznak posle naslednkovi bez prodlen Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 16 DME { pred av anm prznaku po kruhu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 17 DME { pred av anm prznaku po kruhu 2 Prednosti resen je splnena podmnka bezpecnosti je splnena podmnka zivosti nedojde ani k uvaznut ani ke starnut pokud se zna maximaln doba resen KS a pocet procesu v kruhu je znama i maximaln prodleva procesu pred vstupem do KS podmnka spravedlivosti splnena je, avsak ne v porad logickeho casu, ale se zajistenm, ze zadatele muze kazdy proces predbehnout pouze 1x 2 Nedostatky resen (nejsou resitelne trivialne) Ztrata prznaku se mus resit distribuovanou volbou procesu, ktery bude novy prznak generovat Vypadek jednoho uzlu v kruhove sti se mus resit rekonstrukc kruhu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 18 DME, Raymond, pred av an prznaku po stromu 2 Na uzly distribuovaneho systemu se superponuje kostra 2 Po kostre se predava prznak povolujc vstup do KS 2 Prznak existuje v jedinem exemplari, drz ho uzel v teto kon guraci tvorc koren stromu pokryvajc kostru grafu, je tudz privilegovany 2 Pokud prznak povolujc vstup do KS drz uzel i, pak je tento uzel v tomto okamziku korenem stromu pokryvajcm kostru a vsechny uzly obsahuj ukazatel na sveho rodice v tomto stromu 2 Pri predan prznaku jinemu uzlu se kon gurace stromu (orientace hran) aktualizuje Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 19 DME, Raymond, pred av an prznaku po stromu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 20 DME, Raymond, pred av an prznaku po stromu 2 Chovan uzlu kazdy uzel s vyjimkou korene stromu ma v kazdem okamziku pouze jednoho rodice, kteremu predava svuj pozadavek na zskan prznaku a pozadavky svych potomku kazdy uzel udrzuje FIFO frontu zadost o vstup do KS kazdy uzel preposla svemu rodici pouze jeden pozadavek na zskan prznaku, povolen vstupu do KS, pokud uzel j sam pozaduje zskat prznak a jeho fronta nen prazdna, pak se stav do sve vlastn fronty uzel j pouzije zskany prznak pro vstup do sve kriticke sekce je-li v okamziku, kdy prznak obdrzel, v cele sve fronty a je novym korenem stromu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 21 DME, Raymond, pred av an prznaku po stromu 2 Algoritmus uzel i posla zadost o prznak svemu rodici, j { je-li FIFO fronta v j prazdna, j zapse i do sve fronty FIFO a posle zadost svemu rodici, k { nen-li FIFO fronta v j prazdna, j zapse i do sve fronty FIFO uzel j zskava prznak od sveho rodice, od uzlu k, { pokud je na zacatku sve fronty, vstupuje do KS { pokud nen na zacatku sve fronty, preposle prznak i na pocatku fronty a i z FIFO fronty v j odstran { pokud fronta v j po predan prznaku i nen prazdna, mus j poslat poslat i zadost, aby prznak zskal zpet jestlize i pozaduje prznak a jeho fronta nen prazdna, umst sebe do sve fronty. 2 Slozitost algoritmu je O(log n), uvaznut a starnut nehroz Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 22 DME, Raymond, pred av an prznaku po stromu, prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 23 DME, Raymond, pred av an prznaku po stromu, prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 24 DME, Raymond, pred av an prznaku po stromu, prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 25 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 26 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 27 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 28 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 29 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 30 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 31 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 32 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 33 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 34 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 35 DME, Raymond, pred av an prznaku po stromu, dals prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 36 DME, Raymond, pred av an prznaku po stromu 2 Vzajemna vylucnost je plnena trvale v sti je vzdy pouze jeden privilegovany uzel, koren stromu 2 Nemuze dojt ke starnut kazdy pozadavek se nakonec presune na pocatek fronty v retezci pozadavku se nikdy neobjevuje cyklus Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 37 DME { Suzuki-Kasami, pred av an prznaku 2 silne souvisla st' procesu (kazdy proces muze komunikovat s kazdym procesem v sti) 2 Proces sm vstoupit do KS jen kdyz drz opravnen ke vstupu do KS { prznak (token) 2 Prznak predavany mezi procesy je v jedinem exemplari 2 Pokud proces pozadujc vstoupit do KS nedrz prznak, rozesle vsem procesum zpravu request pozadujc zaslan prznaku velmi silne omezen { procesy se mus vzajemne znat 2 Proces, ktery drz prznak a nen v KS, zasle prznak procesu vybranemu z procesu zadajcch o prznak 2 Procesy se vybraj tak, aby se zabranilo starnut, bazi vyberu je cyklicnost Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 38 DME { Suzuki-Kasami, pred av an prznaku 2 Dky asynchronnosti ste proces i prave drzc prznak muze dostat zadost o jeho predan od procesu j az kdyz zadost procesu j uz byla vyrzena. Resen: Takove nadbytecne predan prznaku nenarusuje podmnku bezpecnosti, pouze zatezuje komunikacn system zbytecnymi zpravami Procesy svoje zadosti o prznak poradove csluj, request (Pi, SNi) Kazdy proces si udrzuje N-prvkove pole R (Requests), ve kterem Ri udava poradove cslo posledn prijate zadosti od Pi, request (Pi, SNi) Plat Ri = max(Ri, SNi), pokud Ri > SNi, pak se jedna o uz zastaralou, neplatnou zadost Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 39 DME { Suzuki-Kasami, pred av an prznaku 2 Pokud se zadosti od vce procesu u drzitele prznaku kumuluj, prznak se predava na bazi cyklickeho porad podle jejich identit: Prznak obsahuje N-prvkove pole T (Token), ve kterem Ti udava poradove cslo posledn zadosti o prznak z procesu Pi Kdyz proces Pi drzc prznak opoust KS, nastav Ti = Ri Proces Pi drzc prznak prohlz pole T cyklicky, kdykoliv opoust KS nebo kdyz drz prznak a dostal zadost o prznak cyklicky = pocnaje indexem i + 1 mod N, pak po kroku 1 mod N, Kdyz nalezne Rj = Tj + 1, pak Pj zada o prznak a Pi mu ho posle Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 40 DME { Suzuki-Kasami, pred av an prznaku 2 Pocatecne drz prznak libovolny proces 2 Proces Pi CHCE vstoupit do KS NEDRZI prznak: inkrementuje Ri a vsem ostatnm procesum posle request (Pi, SNi), kde SNi = Ri a ceka az prznak zska DRZI prznak: vstoup do KS a po opusten KS provede Ti = Ri a TEST, zjisten, kteremu procesu ma predat prznak 2 Proces Pi obdrz zadost Pj o povolen vstoupit do KS NEDRZI prznak: v poli R zadost registruje, Rj = max(Rj, SNj) DRZI prznak: provede TEST kteremu procesu ma prznak predat 2 TEST Pi prohledava prznak T v porad i + 1, i + 2, . . . , 1, 2, i − 1 a predava prznak prvnmu procesu Pk, pro ktery plat Rk = Tk + 1 i je pozice v T odpovdajc procesu, ktery prave drz prznak Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 41 DME { Suzuki-Kasami, pred av an prznaku 2 Algoritmus je korektn: existuje jediny prznak 2 Resen je uplne, splnuje podmnku zivost: pozadujc proces muze predbehnout pouze N − 1 procesu dky cyklickemu prohlzen prznaku 2 Pocet zprav zadost o vstup do KS, pokud proces nedrz prznak, N N − 1 zprav request (Pi, T Si) 1 zprava zaslajc prznak 2 Pocet zprav na vstup do KS, pokud proces drz prznak, = 0 Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 42 DME { Suzuki-Kasami, poc atecn stav Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 43 DME { Suzuki-Kasami, 1 z ad a o token Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 44 DME { Suzuki-Kasami, 3 z ad a o token Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 45 DME { Suzuki-Kasami, Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 46 DME { Suzuki-Kasami Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 47 DME { Suzuki-Kasami, jin y prklad Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 48 DME { jednoduch y kv orov y algoritmus 2 proces pozadujc vstup do kriticke sekce posle zadost o povolen vstupu vsem ostatnm procesum 2 procesy tvor kvorum, v kvoru ma kazdy proces prave 1 hlas 2 kazdy osloveny proces, ktery dosud svuj hlas nedal jinemu procesu a nenachaz se v kriticke sekci, povolen udel 2 jakmile proces zska povolen od alespon (N + 1)/2 (napr. 3 z 4 nebo 5), muze vstoupit do kriticke sekce 2 Po opusten kriticke sekce proces vsechny ostatn procesy informuje o uvolnen kriticke sekce { vrat jim jejich hlas 2 Nedostatek { hroz uvaznut napr. kazdy ze tr soubezne zadajcch procesu v mnozine sesti procesu zska po dvou hlasech Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 49 DME { kv orov y algoritmus Maekawa 2 Mamoru Maekawa (1985) 2 organizace procesu pro optimalizaci komunikacn slozitosti kazdemu procesu p z mnoziny P , ve ktere kooperuje N procesu, je prirazen volebn okrsek Vp (voting set), kvorum, tvoreny jistou podmnozinou procesu z mnoziny P procesu p mus pro povolen vstupu do kriticke sekce zskat vsechny hlasy ze sveho okrsku, Vp kazdy volitel ma prave jeden hlas, po vystupu z kriticke sekce proces hlasy svym volitelum vrac kvora se vol tak, aby byla splnena podmnka bezpecnosti, vsechny maj alespon jednoho spolecneho volitele Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 50 DME { kv orov y algoritmus Maekawa, princip kv or Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 51 DME { kv orov y algoritmus Maekawa 2 Podmnky pro kvora, volebn okrsky bezpecnost { kazda dvojice volebnch okrsku ma alespon 1 spolecneho clena { proces, ∀p, q : Vp Vq = ∅, kazdy proces ma pouze jeden hlas ⇒ nemohou byt soucasne zvoleny dva procesy spravedlnost { velikost volebnch okrsku je konstantn ∀p, q : |Vp| = |Vq| = K, vsechny procesy potrebuj pro vstup do KS zskat stejny pocet hlasu, kazdy proces ma stejnou zodpovednost, je obsazen ve stejnem poctu M volebnch okrsku, ∀p, q : |Vi : p ∈ Vi| = |Vj : q ∈ Vj| = M Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 52 DME { kv orov y algoritmus Maekawa 2 komunikacn slozitost odpovda O(|Vp|) clem implementace je minimalizace velikosti volebnch okrsku 2 Konstrukce optimalnch volebnch okrsku N, pocet procesu, necht' plat N = n2 N = n2 je nepodstatne omezen, skutecny pocet lze snadno doplnit sluzebne-formalnmi procesy pouze radne povolujcmi vstup procesy oznacme (i, j) pro 1 ≤ i, j ≤ n, procesy se usporadaj do oznacovac matice n × n volebn okrsek procesu pij tvor procesy v i-tem radku a j-tem sloupci oznacovac matice velikost volebnho okrsku K = O(2 √ N) je dobry vysledek Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 53 DME { kv orov y algoritmus Maekawa Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 54 DME { kv orov y algoritmus Maekawa, idea programu Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 55 DME { kv orov y algoritmus Maekawa 2 V dosud prezentovane zakladn verzi Maekawovuv algoritmus neosetruje uvaznut, nen splnena podmnka zivosti Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 56 DME { kv orov y algoritmus Maekawa 2 Prevence uvaznut { mus se respektovat logicky cas procesy udrzuj nevyrzene pozadavky v porad logickeho casu proces p prijme zadost od procesu r s T Sr p ma volny hlas { povol vstup procesu r p dal jiz hlas jinemu procesu q s T Sq < T Sr { novejs pozadavek procesu r si zarad do sve fronty pozadavku p dal jiz hlas jinemu procesu q s T Sq > T Sr { r je strs proces, p posle mladsmu procesu q zpravu REJECT { pokud q je jiz v kriticke sekci, tj. uz dostal vsechny hlasy ze sveho kvora, odpov (vrat hlas p) az po opusten kriticke sekce { pokud q jeste nezskal vsechny hlasy ze sveho kvora, nen tedy jeste v kriticke sekci, vrat hlas procesu p a ten ho preda procesu r proces p si ve sve fronte pozadavku obnov zadost z q Jan Staudek, FI MU Brno | PA150 { Vz ajemn e vyloucen v distribuovan em prostred 57