2011TomáˇsJankovský Analýzadistribuovanýchalgoritm˚upomoc´ıPetrihos´ıt´ıAnalysisofDistributedAlgorithmsbyMeansofPetriNets VˇSB–TechnickáuniverzitaOstravaFakultaelektrotechnikyainformatikyKatedrainformatiky

(1)

Katedra informatiky

Anal ´yza distribuovan ´ych algoritm ˚u pomoc´ı Petriho s´ıt´ı

Analysis of Distributed Algorithms by Means of Petri Nets

2011 Tom ´aˇs Jankovsk´y

(2)

V Ostravˇe 2011 . . . .

Prohlaˇsuji, ˇze jsem tuto diplomovou práci vypracoval samostatnˇe. Uvedl jsem vˇsechny literárn´ı prameny a publikace, ze kter ých jsem ˇcerpal.

V Ostravˇe 2011 . . . .

(3)

(4)

ritm ˚u pomoc´ı Petriho s´ıt´ı. Algoritmy typicky pˇredstavené pomoc´ı pseudok ódu, jsou pomoc´ı popsan ých metod pˇrevedeny na Petriho s´ıtˇe. Práce je doplnˇena ˇradou skript ˚u a animac´ı, vytvoˇren ých ve volnˇe dostupn ých programov ých prostˇredc´ıch, pro dalˇs´ı pˇribl´ıˇzen´ı ˇctenáˇri. Tato diplomová práce obsahuje shrnut´ı a porovnán´ı monografi´ı Elements of Dis- tributed Algorithms od W. Reisiga s monografi´ı Coloured Petri nets od K. Jensena a L. M.

Kristensena.

Kl´ıˇcov á slova: Distribuované algoritmy, Petriho s´ıtˇe, anal ýza, diplomová práce

Abstract

This diploma thesis describes possibilities of modeling and analysis of distributed algorithms using Petri nets. Algorithms, typically introduced by pseudocode are converted to Petri nets using described methods. Thesis is extended by scripts and animations, created in freely available software, for further approach to reader. This diploma thesis contains summary and comparison between Elements of Distributed Algorithms by W.

Reisig and Coloured Petri nets by K. Jensen and L. M. Kristensen.

Keywords: Distributed algorithms, Petri Nets, Analysis, Master thesis

(5)

Obsah

1 Uvod´ 6

1.1 C´ıle diplomov´e pr´ace . . . 6

1.2 Shrnut´ı obsahu jednotliv ´ych kapitol . . . 7

2 Distribuovan´e algoritmy 8 2.1 Uvod . . . .´ 8

2.2 Distribuovan´e algoritmy . . . 8

2.3 Producent - konzument . . . 8

2.4 Definice Petriho s´ıtˇe, jej´ı struktura, pˇrechod . . . 11

2.5 Vz´ajemn´e vylouˇcen´ı . . . 14

2.6 Sd´ılen´ı zdroj ˚u . . . 16

2.7 Stavov´a anal ´yza Petriho s´ıt´ı . . . 19

2.8 Sd´ılen´ı zdroj ˚u - pokraˇcov´an´ı . . . 20

2.9 Grafov´a transformace Petriho s´ıtˇe . . . 23

2.10 V ´ybˇer vedouc´ıho . . . 27

2.11 Minim´aln´ı kostra grafu . . . 29

3 Vz´ajemn´e vylouˇcen´ı - model 32 3.1 Uvod . . . .´ 32

3.2 Probl´em . . . 32

3.3 Model . . . 33

3.4 Z´avˇer . . . 41

4 Vzájemné vylouˇcen´ı - anal ýza 42 4.1 Uvod . . . .´ 42

4.2 Algebraick´e metody anal ´yzy Petriho s´ıt´ı . . . 42

4.3 Grafov´e metody anal ´yzy Petriho s´ıt´ı . . . 44

4.4 Anal ýza model ˚u vzájemného vylouˇcen´ı . . . 44

4.5 Z´avˇer . . . 47

5 Monografie Elements of Distributed Algorithms 49 5.1 Uvod . . . .´ 49

5.2 Základn´ı systémové modely . . . 49

5.3 Pokroˇcilé systémové modely . . . 54

5.4 Anal ýza základn´ıch systémov ých model ˚u . . . 58

5.5 Anal ýza pokroˇcil ých systémov ých model ˚u . . . 65

5.6 Formáln´ı anal ýza pˇr´ıpadov ých studi´ı . . . 66

5.7 Zhodnocen´ı . . . 66

6 Animace 68 6.1 Uvod . . . .´ 68

6.2 Proces tvorby . . . 68

6.3 Popis jednotliv ´ych animac´ı . . . 68

(6)

6.4 Z´avˇer . . . 69

7 Z´avˇer 70 Pˇr´ılohy 72 A Literatura 72 B jPNS 73 B.1 Uvod . . . .´ 73

B.2 Instalace a spuˇstˇen´ı . . . 73

B.3 Ovl´ad´an´ı . . . 73

C CPN Tools 75 C.1 Uvod . . . .´ 75

C.2 Instalace a spuˇstˇen´ı . . . 75

C.3 Monografie Coloured Petri nets . . . 75

C.4 Popis aplikace CPN Tools . . . 76

C.5 Srovnán´ı s Elements of distributed algoritms . . . 77 D Programové prostˇredky pouˇzité pro vytvoˇren´ı animac´ı 79

(7)

Seznam obr ´azk ˚u

1 Stavov´e zobrazen´ı syst´emu producent - konzument . . . 9

2 Syst´em producent - konzument . . . 10

3 Jednoduch´a s´ıˇt . . . 11

4 Jednoduch´a s´ıˇt po proveden´ı pˇrechodu . . . 12

5 Proveden´ı pˇrechodu v s´ıti s n´asobn ´ymi hranami . . . 13

6 Producent - konzument po proveden´ı pˇrechod ˚u . . . 14

7 Vz´ajemn´e vylouˇcen´ı . . . 14

8 Algoritmus vz´ajemn´eho vylouˇcen´ı . . . 16

9 Distribuovan ´y algoritmus hladov ´ych filozof ˚u . . . 17

10 Uv´aznut´ı v algoritmu hladov ´ych filozof ˚u . . . 18

11 Algoritmus hladov ´ych filozof ˚u bez uv´aznut´ı . . . 21

12 Fragment Lehmann-Rabinova algoritmu uchopen´ı h ˚ulek . . . 23

13 Spojen´ı sekvence m´ıst a pˇrechod ˚u . . . 24

14 Syst´em producent - konzument pro dva objekty . . . 24

15 Syst´em producent - konzument pro x objekt ˚u . . . 25

16 Algoritmus hladov ´ych filozof ˚u pro 3 filozofy . . . 26

17 Algoritmus hladov ´ych filozof ˚u se spojen ´ymi m´ısty . . . 26

18 Zobecnˇen ´y algoritmus 3 hladov ´ych filozof ˚u . . . 27

19 S´ıˇt typu token ring . . . 27

20 V ´ybˇer vedouc´ıho . . . 29

21 Minim´aln´ı kostra . . . 30

22 Minim´aln´ı kostra grafu . . . 30

23 Model vz´ajemn´eho vylouˇcen´ı ˇc. 1 . . . 34

25 Opraven ý model vzájemného vylouˇcen´ı ˇc. 2 . . . 37

26 Koneˇcn ý model vzájemného vylouˇcen´ı ˇc. 2 . . . 38

27 Dekker ˚uv algoritmus . . . 40

28 Pˇr´ıklad pasti a z´amku . . . 44

29 P-invariant algoritmu vz´ajemn´eho vylouˇcen´ı . . . 45

30 P-invariant modelu vz´ajemn´eho vylouˇcen´ı ˇc.1 . . . 46

31 Past v upraveném algoritmu vzájemného vylouˇcen´ı . . . 47

32 Maximáln´ı jedineˇcná soubˇeˇzná sekvence systému producent - konzument z obrázku ˇc´ıslo 2 . . . 50

33 Pr ˚ubˇeh algoritmu hladov ých filozof ˚u zapsan ý zkrácenou formou . . . 52

34 Dekker ˚uv algoritmus podle W. Reisiga . . . 53

35 Distribuovan ´y algoritmus Eratosthenova s´ıta . . . 54

36 Distribuovan ý algoritmus hledán´ı maximáln´ı hodnoty . . . 55

37 Distribuovan ´y algoritmus konsensu . . . 57

38 Distribuovan ´y algoritmus . . . 59

39 Invariant A + C + D = 1 . . . 60

40 Past A, D . . . 61

41 Vedouc´ı formule A, B→D . . . 62

(8)

42 Asymetrick ý algoritmus vzájemného vylouˇcen´ı . . . 62

43 D ˚ukazov ´y graf|=B→C . . . 64

44 Soubˇeˇzn ´y bˇeh A7→B . . . 64

45 Soubˇeˇzn ´y bˇeh A7→B . . . 66

46 Pracovn´ı prostˇred´ı aplikace jPNS . . . 74

47 CPN Tools . . . 77

(9)

Seznam v ýpis ˚ u zdrojov ého k ódu

1 Producent - konzument . . . 9

2 Vz´ajemn´e vylouˇcen´ı . . . 15

3 ˇZivot filozofa . . . 16

4 Lehmann-Rabin ˚uv algoritmus . . . 22

5 Popis problému vzájemného vylouˇcen´ı . . . 32

8 Opraven ý model vzájemného vylouˇcen´ı ˇc. 2 . . . 36

9 Koneˇcn ý model vzájemného vylouˇcen´ı ˇc. 2 . . . 37

10 Dekker ˚uv algoritmus . . . 39

(10)

1 Uvod ´

Jak se v souˇcasné dobˇe rozˇsiˇruje pokryt´ı obor ˚u lidské ˇcinnosti automatick ými systémy, t´ım také nar ˚ustá potˇreba tyto systémy korektnˇe ˇr´ıdit, zajistit jejich optimáln´ı spolupráci a souˇcinnost. Souˇcást´ı tˇechto ˇr´ıd´ıc´ıch prvk ˚u jsou také takzvané distribuované algoritmy.

Term´ın distribuovan ý algoritmus se zpoˇcátku vztahoval pouze na systémy, které byly vytvoˇreny pro práci s mnoha procesory rozm´ıstˇen ými ve velké geografické oblasti.

V pr ˚ubˇehu ˇcasu se tento term´ın pˇrenesl a nyn´ı popisuje i algoritmy pracuj´ıc´ımi v m´ıstn´ı s´ıti nebo pˇr´ıpadnˇe ve sd´ılené pamˇeti multiprocesoru. Distribuované algoritmy jsou dnes souˇcást´ı celé ˇrady aplikac´ı, zahrnuj´ıc´ı telekomunikace, distribuované informaˇcn´ı procesy nebo sledován´ı proces ˚u v reálném ˇcase. Vˇetˇsina souˇcasn ých kontroln´ıch systém ˚u, jako jsou systémy ˇr´ızen´ı letového provozu nebo systémy kontroluj´ıc´ı jaderné elektrárny, jsou kriticky závislé na distribuovan ých systémech. Proto je nutné, aby tyto systémy byly maximálnˇe spolehlivé a efektivn´ı, a to i v pˇr´ıpadˇe velmi sloˇzit ých proces ˚u.

Tato diplomová práce se zab ývá problematikou základn´ıch distribuovan ých systém ˚u, jejich reprezentac´ı pomoc´ı Petriho s´ıt´ı a anal ýzou, kterou tato reprezentace umoˇz ˇnuje.

1.1 C´ıle diplomov ´e pr ´ace

C´ılem této diplomové práce je seznámit ˇctenáˇre s nˇekolika vybran ými problémy distribuovan ých algoritm ˚u a jejich obvyklou reprezentac´ı pomoc´ı programového pseudok ó- du. Algoritmy obsaˇzené v této diplomové práci jsem studoval z jejich p ˚uvodn´ıch zdroj ˚u, a jako jeden z pˇr´ınos ˚u této diplomové práce vid´ım seznámen´ı ˇctenáˇre s tˇemito d´ıly.

Programov ý pseudok ód vybran ých algoritm ˚u bude porovnán s reprezentac´ı pomoc´ı Petriho s´ıt´ı. ˇCtenáˇr se tak m ˚uˇze seznámit se základn´ımi prvky teorie Petriho s´ıt´ı a bude schopen porozumˇet, navrhnout a analyzovat jednoduché algoritmy sám.

Reprezentace distribuovan ých algoritm ˚u pomoc´ı Petriho s´ıt´ı je popsána v monografii Reisig, W. : Elements of distributed algorithms (Springer 1998). ˇCtenáˇr se bude moci seznámit s obsahem tohoto d´ıla. Dalˇs´ı pˇr´ınos této diplomové práce nab´ız´ı porovnán´ı v ýˇse uvedené monografie s monografi´ı Coloured Petri nets (Springer 2009), kterou jsem prostudoval aˇz v pr ˚ubˇehu vytváˇren´ı animac´ı, a která na problematiku vyuˇzit´ı Petriho s´ıt´ı nahl´ıˇz´ı z jiného úhlu.

D ˚uleˇzitou souˇcást´ı mé diplomové práce jsou elektronické animace popisuj´ıc´ı distribuo- vané algoritmy, vybrané po dohodˇe s vedouc´ım diplomové práce. Algoritmy byly vybrány tak, aby pokryly nejzákladnˇejˇs´ı problémy v oblasti distribuované informatiky. Z d ˚uvodu srovnán´ı jsou uvedené algoritmy také obsaˇzeny v monografii Elements of distributed algorithms. Moˇznosti modelován´ı a anal ýzy budou pˇredvedeny na algoritmu vzájemného vylouˇcen´ı v nˇekolika variantách, ve kter ých se pokus´ım zhodnotit vyuˇzit´ı v ýpoˇcetn´ı s´ıly Petriho s´ıt´ı k tomuto úˇcelu. Spolu s elektronick ými animacemi vytvoˇr´ım ve volnˇe dostupn ých aplikac´ıch soubor pˇr´ıklad ˚u distribuovan ých algoritm ˚u, popisovan ých v této diplomové práci, které detailnˇeji pˇribl´ıˇz´ı problematiku budouc´ım diplomant ˚um. Závˇerem provedu i srovnán´ı mezi pouˇzit ými programov ými nástroji.

(11)

1.2 Shrnut´ı obsahu jednotliv ´ych kapitol

Teoretická ˇcást této diplomové práce se skládá ze ˇctyˇr hlavn´ıch ˇcást´ı.

Kapitola 2 se zab ývá základy distribuovan ých algoritm ˚u. ˇCtenáˇr se seznám´ı s nˇekolika vybran ými distribuovan ými algoritmy a jejich reprezentac´ı pomoc´ı fragment ˚u pseudok ó- d ˚u. Na tˇechto algoritmech bude pˇredstaveno i pouˇzit´ı Petriho s´ıt´ı jako alternativy pro modelován´ı chován´ı a vlastn´ı anal ýzu distribuovan ých systém ˚u. Pro ˇctenáˇre, kteˇr´ı se s Petriho s´ıtˇemi dosud nesetkali, tato kapitola pˇrináˇs´ı i formáln´ı základy teorie Petriho s´ıt´ı.

Kapitola 3 je zamˇeˇrena na algoritmus vzájemného vylouˇcen´ı. V této kapitole je znázor- nˇeno postupné modelován´ı tohoto algoritmu spoleˇcnˇe s anal ýzou jednotliv ých krok ˚u.

Jednoduch ý model je podroben anal ýze a na základˇe zjiˇstˇen ých nedostatk ˚u je k nˇemu pˇripojována dalˇs´ı konstrukce, která zajist´ı vˇsechny poˇzadované vlastnosti, a cel ý tento proces je nˇekolikrát zopakován. Na tomto konkrétn´ım pˇr´ıpadu bude moci ˇctenáˇr porov- nat rozd´ıly modelován´ı pomoc´ı pseudok ódu a s pomoc´ı Petriho s´ıt´ı.

Následuj´ıc´ı kapitola 4 popisuje formáln´ı anal ýzu algoritm ˚u z pˇredeˇslé kapitoly s ohledem na ˇzádouc´ı vlastnosti. V rámci této kapitoly se ˇctenáˇr seznám´ı se dvˇema základn´ımi pˇr´ıstupy anal ýzy Petriho s´ıt´ı a to s algebraickou metodou pomoc´ı incidenˇcn´ı matice, a dále s metodou grafovou, která pro anal ýzu vyuˇz´ıvá speciáln´ı struktury obsaˇzené v Petriho s´ıti.

Kapitola 5 pˇrináˇs´ı ˇctenáˇri náhled do monografie Reisig, W.: Elements of Distributed Algorithms (Springer 1998). ˇCtenáˇr se seznám´ı se zamˇeˇren´ım této knihy, s pouˇzit ými technikami jej´ıho autora a v neposledn´ı ˇradˇe se srovnán´ım nˇekter ých jeho algoritm ˚u s algoritmy, které vzeˇsly z této diplomové práce. Touto kapitolou konˇc´ı teoretická ˇcást diplomové práce.

Kapitola 6 se vˇenuje vlastn´ımu postupu vytvoˇren´ı animac´ı pro tuto diplomovou práci a jejich krátkému popisu.

(12)

2 Distribuovan ´e algoritmy

2.1 Uvod´

Tato kapitola je zamˇeˇrena na popis problému distribuovan ých algoritm ˚u. Ctenáˇr seˇ seznám´ı s nˇekolika distribuovan ými algoritmy, které se pouˇz´ıvaj´ı pro ˇreˇsen´ı základn´ıch v ýpoˇcetn´ıch problém ˚u. S ohledem na moˇznosti srovnán´ı jsem vyb´ıral pouze takové algoritmy, které jsou obsaˇzeny i v monografii Elements of Distributed Algorithms. Jed- notlivé distribuované algoritmy jsou reprezentovány jak v programovém pseudok ódu, tak i Petriho s´ıtˇemi, které jsou doplnˇeny odpov´ıdaj´ıc´ım teoretick ým základem. Infor- mace k této kapitole jsem ˇcerpal z monografi´ı [1], [2] a [3].

2.2 Distribuovan ´e algoritmy

V souˇcasné dobˇe jsme obklopeni mnoˇzstv´ım prvk ˚u a proces ˚u spojen ých navzájem v s´ıt´ıch a komunikuj´ıc´ıch mezi sebou za úˇcelem splnˇen´ı spoleˇcného úkolu. Tyto procesy mus´ı jednat spontánnˇe a nezávisle na sobˇe, ale s ohledem na ostatn´ı, a tak vytváˇrej´ı spoleˇcné - distribuované v ýpoˇcetn´ı prostˇred´ı. I kdyˇz jednotlivé procesy tohoto prostˇred´ı jsou schopné nezávislé práce, pouze jejich spojen´ı umoˇz ˇnuje splnˇen´ı zadaného úkolu.

Abychom tyto spoleˇcné úkoly mohli vyˇreˇsit, mus´ıme vytvoˇrit sadu pravidel urˇcuj´ıc´ıch, kdo má co dˇelat, pokud moˇzno bez synchronizace a dohledu zvenˇc´ı. Mus´ıme tedy vytvoˇrit distribuovan ý algoritmus, kter ý zaruˇcuje jak korektnost (tedy správné vyˇreˇsen´ı zadaného problému) tak i efektivnost (vytvoˇren ý algoritmus mus´ı m´ıt pˇrimˇeˇrenˇe malé náklady).

Distribuovan´e algoritmy jsou tedy celky, spojuj´ıc´ı algoritmy jednotliv ´ych proces ˚u.

Tyto procesy jsou ˇcasto provádˇeny soubˇeˇznˇe na nezávisl ých procesorech a maj´ı pouze ˇcásteˇcnou informaci o tom, co dˇelá zbytek algoritmu.

Proto základn´ım c´ılem pˇri tvorbˇe distribuovaného algoritmu je úspˇeˇsná spolupráce jeho jednotliv ých ˇcást´ı nezávisle na moˇzn ých chybách ˇci pˇreruˇsen´ı komunikace. Jen tyto algoritmy mohou b ýt úspˇeˇsnˇe implementovány pro ˇr´ızen´ı kritick ých proces ˚u, jako jsou systémy ˇr´ızen´ı letového provozu nebo systémy ˇr´ızen´ı jadern ých elektráren. V ýbˇer odpov´ıdaj´ıc´ıho algoritmu potom závis´ı na charakteristice problému a také na charakteristice samotného algoritmu.

2.3 Producent - konzument

Jedn´ım z nejjednoduˇsˇs´ıch distribuovan ´ych algoritm ˚u je syst´em producent - konzument.

M ˚uˇzeme si ho pˇredstavit jako soustavu dvou proces ˚u, producenta a konzumenta, které vykonávaj´ı nˇekolik akc´ı - vyrob, dodej na sklad, vyjmi ze skladu, spotˇrebuj. Dále budeme uvaˇzovat o skladovém m´ıstˇe s kapacitou jedné poloˇzky. Tento algoritmus bˇeˇznˇe nacház´ı uplatnˇen´ı v r ˚uzn ých oblastech, od databáz´ı, pˇres komunikaˇcn´ı protokoly, aˇz po operaˇcn´ı systémy.

(13)

Psáno v programovém pseudok ódu vypadá tento algoritmus takto:

(sklad : integer; sklad := 0);

begin parbegin

producent: beginP1: vyrob;

if sklad = 0thensklad := 1; gotoP1 end;

konzument:beginK1: if sklad = 1thensklad := 0; spotˇrebuj;

gotoK1;

end;

parend end;

V ´ypis 1: Producent - konzument

Pseudopˇr´ıkazyparbeginaparendvymezuj´ı oblast, ve kter´e oba procesy, producent i konzument, prob´ıhaj´ı paralelnˇe.

Dalˇs´ı moˇznost´ı, jak tento systém popsat, je pomoc´ı reprezentace stav ˚u jednotliv ých proces ˚u. Pro tento popis si cel ý systém rozdˇel´ıme na tˇri podsystémy - producent, sklad a konzument. Kaˇzd ý z tˇechto podsystém˚u m ˚uˇze nab ýt pouze dvou lokáln´ıch stav ˚u. Pro- ducent se m ˚uˇze nacházet bu ˇd ve stavupˇripraven k výrobˇe(pv) nebopˇripraven k dodán´ına sklad (pd). Konzument má stavypˇripraven k odebrán´ıze skladu (po) apˇripraven ke spotˇrebˇe (ps) a sklad má stavyplný(s1) aprázdný(s0).

pv pd

s0 s1

po ps

producent sklad konzument

Figure 1: Stavov´e zobrazen´ı syst´emu producent - konzument

Nicménˇe tento diagram nepopisuje systém jako celek, a je proto nutné dodat informaci o tom, jak se chovaj´ı jednotlivé procesy. Procespd→pva process0→s1prob´ıhaj´ı souˇcasnˇe. To stejné plat´ı pro procesypo→psas1→s0. Tato informace mus´ı b ýt poskyt- nuta dodateˇcnˇe.

(14)

Jin ý pohled na tento algoritmus pˇredstavuje popis akc´ı, které jednotlivé podsystémy provádˇej´ı. Producent stˇr´ıdá akcivýroba (v) adodán´ına sklad (d) a nekoneˇcná sekvence vdvdvd... popisuje jeho chován´ı. To stejné plat´ı pro akce konzumenta -odbˇerze skladu (o) aspotˇreba(s). Akce skladu jsou spojeny sdodán´ımaodbˇerem, oznaˇc´ıme je proto ¯da ¯o.

Vˇsechny tyto sekvence m ˚uˇzeme zapsat pomoc´ı rovnice:

producent = v.d.producent konzument = o.s.konzument

sklad = ¯d. ¯o.sklad

Cel ý systém pak m ˚uˇzeme zapsat pomoc´ı paraleln´ıho operátoruk, kde pro kaˇzdé x a ¯x plat´ı, ˇze probˇehnou souˇcasnˇe.

producentkskladkkonzument

Obˇe v ýˇse zm´ınˇené metody popisu systému se d´ıvaj´ı na celek jen pod jedn´ım úhlem, bu ˇd jako soustavu r ˚uzn ých stav ˚u, nebo jako soustavu r ˚uzn ých akc´ı, doplnˇenou o dalˇs´ı potˇrebné informace.

Na druhé stranˇe stoj´ı metoda popisu pomoc´ı Petriho s´ıt´ı, která sama o sobˇe poskytuje v ýˇse zm´ınˇené informace, a nav´ıc umoˇz ˇnuje z´ıskat informace dalˇs´ı.

Na následuj´ıc´ım obrázku stejn ý systém reprezentovan ý Petriho s´ıt´ı.

• • •

Figure 2: Syst´em producent - konzument

Z tohoto obrázku, i bez pˇredchoz´ı znalosti Petriho s´ıt´ı, je moˇzné intuitivnˇe pochopit tento algoritmus i jeho pr ˚ubˇeh. Levá ˇcást je systém producent, ve stˇredu se nalézá sklad a vpravo je systém konzument.

(15)

2.4 Definice Petriho s´ıt ˇe, jej´ı struktura, pˇrechod

Na pˇr´ıkladu algoritmu producent konzument si definujeme z´akladn´ı prvky Petriho s´ıt´ı.

Petriho s´ıtˇe se skládaj´ı z m´ıst (stav ˚u), které vyjadˇruj´ı podm´ınku, a událost´ı, které jsou reprezentované pˇrechody. M´ısta jsou graficky znázornˇena kruˇznic´ı, pˇrechody oznaˇcuje- me obdéln´ıkem, nebo úseˇckou. M´ısta jsou spojena s pˇrechody pomoc´ı orientovan ých hran. Vˇzdy je spojeno m´ısto s pˇrechodem nebo pˇrechod s m´ıstem. Nikdy nejsou spojeny pˇrechody s jin ým pˇrechodem a m´ısto s jin ým m´ıstem. V ýsledkem je bipartitn´ı graf s dvˇema typy uzl ˚u, m´ısty a pˇrechody, a s orientovan ými hranami. Na následuj´ıc´ım obrázku ˇc´ıslo 3 je jednoduchá s´ıˇt, která m ˚uˇze reprezentovat podsystém producent.

•

Figure 3: Jednoduch´a s´ıˇt Nyn´ı si definujeme form´alnˇe Petriho s´ıˇt.

Definice 2.1 Struktura Petriho s´ıtˇe je pˇeticehP, T, I, O, Hi, kde

• P je koneˇcn´a mnoˇzina m´ıst

• T je koneˇcn´a mnoˇzina pˇrechod ˚u

• I,O,H jsou zobrazen´ı typu T→ P^MS,po ˇradˇe vstupn´ı funkce, v´ystupn´ı funkce a vstupn´ı inhibiˇcn´ı funkce

P^MSje mnoˇzina vˇsech multimnoˇzin nad mnoˇzinou P

Pro naˇse úˇcely budeme uvaˇzovat speciáln´ı pˇr´ıpad, kdy inhibiˇcn´ı funkce pˇriˇrazuje vˇsem pˇrechod ˚um t∈T prázdnou multimnoˇzinu z P^MS. V tomto pˇr´ıpadˇe nen´ı potˇreba inhibiˇcn´ı funkci H ve struktuˇre PN uvádˇet.

Souˇcasn ý stav celého systému se znázor ˇnuje pomoc´ı znaˇcek zvan ých tokeny, které se umisˇtuj´ı do jednotliv ých m´ıst. Systém vˇzdy vycház´ı z poˇcáteˇcn´ıho znaˇcen´ı, coˇz je v ýchoz´ı znaˇcen´ı pˇred proveden´ım jakéhokoliv pˇrechodu. Formálnˇe ˇreˇceno:

(16)

Definice 2.2 Syst´em Petriho s´ıtˇe (PN syst´em) je pˇeticehP, T, I, O, M0i, kde

• hP, T, I, O,ije struktura PN

• M0 je zobrazen´ı typu P→N, tzv. poˇcáteˇcn´ı znaˇcen´ı, kde N je mnoˇzina pˇrirozených ˇc´ısel Obecnˇe symbolem M oznaˇcujeme jakékoliv zobrazen´ı P→N.

Pˇrechod do nového m´ısta je umoˇznˇen splnˇen´ım podm´ınek pˇrechodu, kter ý urˇcuj´ı poˇcty odeb´ıran ých a um´ısˇtovan ých token ˚u. V grafu je to znázornˇeno ohodnocen´ım orientovan ých hran. Pokud nen´ı explicitnˇe uvedeno hodnocen´ı hrany, má implicitnˇe hodnocen´ı 1. Pˇrechod se m ˚uˇze uskuteˇcnit tehdy, kdyˇz vˇsechna vstupn´ı m´ısta obsahuj´ı dostateˇc- n ý poˇcet token ˚u.

Definice 2.3 Pˇrechod t je provediteln´y pˇri znaˇcen´ı M, jestliˇze plat´ı

(∀p∈^•t)[M(p)≥I(t,p)]

Kde

• ^•t je mnoˇzina vstupn´ıch m´ıst pˇrechodu t

• M(p) je pˇrirozen´e ˇc´ıslo urˇcuj´ıc´ı poˇcet token ˚u v m´ıstˇe p

• I(t,p) je n´asobnost hrany z m´ısta p do pˇrechodu t

Po proveden´ı pˇrechodu se tokeny odeberou ze vstupn´ıch m´ıst v závislosti na ohodnocen´ı orientovan ých hran vystupuj´ıc´ıch ze vstupn´ıch m´ıst a um´ıst´ı do v ýstupn´ıch m´ıst opˇet v závislosti na ohodnocen´ı orientovan ých hran, které do nich vstupuj´ı.

•

Figure 4: Jednoduch´a s´ıˇt po proveden´ı pˇrechodu

Mnoˇzinu pˇrechod ˚u provediteln ých pˇri znaˇcen´ı M oznaˇc´ıme jako E(M). Znaˇcen´ı, pˇri kterém nen´ı ˇzádn ý pˇrechod provediteln ý, oznaˇcujeme uzamˇcen´ı. Tomuto speciáln´ımu stavu systému se budeme vˇenovat pozdˇeji.

(17)

Definice 2.4 Proveden´ı pˇrechodu t pˇri znaˇcen´ı M, vede od znaˇcen´ı M k znaˇcen´ı M’ takov´emu, ˇze plat´ı:

(∀p∈P)[M’(p)=M(p)+O(t,p)-I(t,p)] Kde O(t,p) je n´asobnost hrany z pˇrechodu t do m´ısta p

Proveden´ı pˇrechodu v s´ıt´ıch, které obsahuj´ı násobné hrany, je znázornˇeno na obrázku ˇc´ıslo 5.

=⇒

•••

•

••

2

Figure 5: Proveden´ı pˇrechodu v s´ıti s n´asobn ´ymi hranami

Jak je vidˇet na tomto obrázku, mohou se tokeny v systému Petriho s´ıt´ı ztrácet. M ˚uˇze vˇsak nastat situace, kdy se tokeny mohou i generovat. Tyto vlastnosti vyuˇz´ıvaj´ı speciáln´ı struktury Petriho s´ıt´ı, ke kter ým se vrát´ıme pozdˇeji.

Vybaveni touto teori´ı se jiˇz m ˚uˇzeme vrátit k systému producent a konzument a ukázat si stav systému po proveden´ı nˇekolika pˇrechod ˚u. Pro lepˇs´ı názornost si vˇsechna m´ısta a pˇrechody systému pojmenujeme. Systém jiˇz proˇsel nˇekolika cykly a nyn´ı je podsystém producent ve stavupˇripraven k dodán´ı, je pln ý sklad a podsystém konzument je pˇripraven ke spotˇrebˇe. Popsanou situaci znázor ˇnuje následuj´ıc´ı obrázek ˇc´ıslo 6.

Jak je vidˇet na obrázku ˇc´ıslo 6, je v uvedeném znaˇcen´ı moˇzné provést pouze jedin ý pˇrechod a toodbˇer. Ostatn´ı pˇrechody nen´ı moˇzné provést, protoˇze nˇekterá jejich vstupn´ı m´ısta nemaj´ı dostateˇcn ý poˇcet token ˚u. Po proveden´ı pˇrechoduodbˇerse vyprázdn´ı sklad a systém bude moci provést bu ˇd doplnˇen´ı skladu, nebo akci spotˇreby.

Reprezentace pomoc´ı Petriho s´ıt´ı umoˇz ˇnuje postihnout cel ý systém, provázán´ı jednotliv ých soubˇeˇzn ých akc´ı, podm´ınky pro jejich proveden´ı a zárove ˇn pomoc´ı token ˚u m ˚uˇzeme nasimulovat i dynamiku celého systému a vˇsechny jeho moˇzné stavy. V neposledn´ı ˇradˇe, d´ıky grafové struktuˇre, m ˚uˇzeme pouˇz´ıt cel ý aparát teorie graf ˚u na anal ýzu tohoto systému a d´ıky nˇemu napˇr´ıklad urˇcit, zda je systémreverzibiln´ı(tedy je moˇzné se

(18)

•

pˇripraven k v ýrobˇe prázdn ý sklad pˇripraven k odebrán´ı ze skladu

pˇripraven k dod´an´ı pˇripraven ke spotˇrebˇe

pln ´y sklad

v ´yroba dod´an´ı odbˇer spotˇreba

Figure 6: Producent - konzument po proveden´ı pˇrechod ˚u

vrátit do poˇcáteˇcn´ıho stavu), nebo zda je systémuzavˇrený(jestliˇze z poˇcáteˇcn´ıho znaˇcen´ı je dosaˇzitelné znaˇcen´ı, ve kterém nen´ı ˇzádn ý pˇrechod provediteln ý.)

2.5 Vz ´ajemn ´e vylou ˇcen´ı

Dalˇs´ım jednoduch ým, ale ˇcasto se vyskytuj´ıc´ım problémem v informatice je problém vzájemného vylouˇcen´ı. Algoritmus vzájemného vylouˇcen´ı, kter ý byl poprvé popsán E. W. Dijkstrou v [5], zaruˇcuje pˇr´ıstup ke sd´ılenému zdroji pouze jedinému procesu v dan ý okamˇzik. Tento problém se bˇeˇznˇe vyskytuje v operaˇcn´ıch systémech, databáz´ıch, poˇc´ıtaˇcov ých s´ıt´ıch, vˇsude tam kde je potˇrebné vyˇreˇsit konflikt, ke kterému docház´ı v pˇr´ıpadˇe pokusu o pˇr´ıstup k jedinému sd´ılenému zdroji v´ıce procesy.

Pˇr´ıkladem mohou b ýt dva procesy, proces 1 a proces 2, které pracuj´ı nezávisle na sobˇe a kaˇzd ý z nich má urˇcitou ˇcást, zvanoukritická sekce, do které mus´ı m´ıt voln ý pˇr´ıstup, ale vstoupit do n´ı m ˚uˇze v jednom okamˇziku pouze jeden z proces ˚u.

proces 1

proces 2

sd´ılen´e zdroje crit1

crit2

A

B

Figure 7: Vz´ajemn´e vylouˇcen´ı

(19)

Takovou kritickou sekc´ı m ˚uˇze b ýt napˇr´ıklad pˇr´ıstup ke sd´ılené pamˇeti, do které m ˚uˇze pˇristupovat pouze jedin ý proces. ˇReˇsen´ı tohoto problému zahrnuje nejen pouhé zajiˇstˇen´ı pˇr´ıstupu pouze jednoho procesu v daném okamˇziku, ale je nutné vyˇreˇsit i dalˇs´ı problémy s t´ımto spojené, ke kter ým patˇr´ı uváznut´ı v nˇejaké fázi pr ˚ubˇehu algoritmu, nebo nemoˇz- nost faktického vstupu jednoho z proces ˚u do své kritické sekce.

Nejjednoduˇsˇs´ım ˇreˇsen´ım je pouˇzit´ı kl´ıˇce, kdy pouze proces maj´ıc´ı kl´ıˇc m ˚uˇze vstoupit do své kritické sekce. Pro formáln´ı zápis programov ým pseudok ódem budeme uvaˇzovat dva procesy P1 a P2 a promˇennou kl´ıˇc. Zápis vypadá takto:

( kl´ıˇc : integer; kl´ıˇc := 1);

begin parbegin

proces 1: beginP1: if kl´ıˇc := 0then gotoP1;

kl´ıˇc := 0 kritick ´a sekce 1 kl´ıˇc := 1

zbytek procesu 1;gotoP1 end;

proces 2: beginP2: if kl´ıˇc := 0then gotoP2;

kl´ıˇc := 0 kritick ´a sekce 2 kl´ıˇc := 1

zbytek procesu 2;gotoP2 end;

parend end;

V ýpis 2: Vzájemné vylouˇcen´ı

Jiˇz z tohoto zápisu je zˇrejmé, ˇze zde chyb´ı jak ýkoliv mechanismus, ˇr´ıd´ıc´ı pˇridˇelován´ı kl´ıˇce proces ˚um. Pokud se pod´ıváme na grafickou reprezentaci tohoto distribuovaného algoritmu pomoc´ı Petriho s´ıtˇe, dojdeme ke stejnému zjiˇstˇen´ı. Pokud proces 1 vezme kl´ıˇc a vstoup´ı do své kritické sekce, nem ˚uˇze proces 2 udˇelat to samé.

Avˇsak toto triviáln´ı ˇreˇsen´ı s sebou nese nˇekolik problém ˚u, zejména chybˇej´ıc´ı mechanismus pˇridˇelován´ı kl´ıˇce a také moˇznost v ýskytu situace, ˇze jeden z proces ˚u se do své sekce nemus´ı nikdy dostat.

Algoritmu vzájemného vylouˇcen´ı se budu vˇenovat podrobnˇeji v kapitole ˇc´ıslo 3, ale tato jednoduchá s´ıˇt v sobˇe skr ývá zaj´ımavou strukturu, kterou si bl´ıˇze pop´ıˇseme jiˇz nyn´ı.

V poˇcáteˇcn´ım stavu jsou oba vstupy do kritick ých sekc´ı proveditelné, protoˇze je ve vstupn´ıch m´ıstech dostateˇcn ý poˇcet token ˚u pro proveden´ı pˇrechodu. Jak jiˇz bylo ˇreˇceno, pokud ale jeden z proces ˚u pˇrevezme kl´ıˇc a vstoup´ı do kritické sekce, odstran´ı t´ımto token z m´ıstakl´ıˇca zamez´ı tak druhému procesu v proveden´ı vlastn´ıho pˇrechodu do své kritické sekce. Formálnˇe se tato situace naz ývákonflikt.

Je to stav, kdy proveden´ı jednoho pˇrechodu sniˇzuje stupe ˇn proveditelnosti druhého pˇrechodu. Konflikty rozdˇelujeme nasymetrické (proveden´ı kteréhokoliv pˇrechodu sn´ıˇz´ı stupe ˇn pˇrechodu toho druhého) aasymetrické(proveden´ı jednoho pˇrechodu sn´ıˇz´ı stupe ˇn

(20)

• • •

krit 1 kl´ıˇc krit 2

Figure 8: Algoritmus vz´ajemn´eho vylouˇcen´ı

proveditelnosti druhého pˇrechodu, ale ne naopak). V naˇsem pˇr´ıpadˇe se tedy jedná o konflikt symetrick ý.

2.6 Sd´ılen´ı zdroj ˚u

Zobecnˇen´ım problému vzájemného vylouˇcen´ı dostáváme problém vzájemného sd´ılen´ı v´ıce zdroj ˚u. Pˇr´ıkladem m ˚uˇze b ýt proces vyˇzaduj´ıc´ı pro své spuˇstˇen´ı v´ıce prostˇredk ˚u, jako je tiskárna spolu s databáz´ı a spolu se s´ıˇtov ým portem.

Vˇseobecnˇe známou a populárn´ı verz´ı tohoto problému je konfigurace nˇekolika sub- systém ˚u, kde je kaˇzd ý zdroj sd´ılen dvˇema subsystémy a zárove ˇn kaˇzd ý z tˇechto sub- systém ˚u vyˇzaduje dva zdroje. Tento speciáln´ı pˇr´ıpad byl popsán poprvé E. W. Dijsktrou [5] jako problém hladovˇej´ıc´ıch filozof ˚u. V tomto problému filozofové pˇredstavuj´ı jed- notlivé procesy a j´ıdeln´ı h ˚ulky pˇredstavuj´ı jejich zdroje. Filozofové sed´ı u spoleˇcného stolu a po obou jejich stranách leˇz´ı h ˚ulky potˇrebné k j´ıdlu. Z tohoto nastaven´ı vypl ývá, ˇze ˇzádn ý ze soused´ıc´ıch filozof ˚u nem ˚uˇze j´ıst zárove ˇn. Úkolem tohoto algoritmu je zajistit, aby kaˇzd ý z filozof ˚u mˇel spravedliv ý pˇr´ıstup k j´ıdeln´ım h ˚ulkám, tedy aby kaˇzd ý proces mˇel moˇznost se dostat ke sd´ılen ým zdroj ˚um.

Jednoduch ´y algoritmus popisuj´ıc´ı ˇzivot filozofa vypad´a takto:

cycle beginpˇrem´yˇslej;

uchop (pravou h ˚ulku);uchop (levou h ˚ulku);

jez ;

poloˇz (pravou h ˚ulku);poloˇz (levou h ˚ulku);

end;

V ´ypis 3: ˇZivot filozofa

(21)

Toto jednoduché ˇreˇsen´ı vˇsak opˇet obsahuje problém spravedlivého pˇr´ıstupu ke zdroj ˚um a nav´ıc m ˚uˇze doj´ıt kuváznut´ı(uzamˇcen´ı) systému. Tento speciáln´ı stav je moˇzné demon- strovat na Petriho s´ıti tohoto algoritmu. Z d ˚uvodu zjednoduˇsen´ı znázor ˇnuje následuj´ıc´ı Petriho s´ıˇt pouze ˇctyˇri procesy.

•

• •

•

At al

a2

a3 a4

Bl

Ce

Dp

Al Be

Cp

Dt

Ae Bp

Ct

Dl

Ap Bt

Cl

De

app arp brl

brp

cpl

crl

dpp

dpl

apl arl bpp

bpl

cpp

crp

drl drp

Figure 9: Distribuovan ´y algoritmus hladov ´ych filozof ˚u

Pro lepˇs´ı pochopen´ı si tento systém pop´ıˇseme. Filozofy si oznaˇc´ıme A, B,C,Da ti mohou b ýt v jednom ze ˇctyˇr stav ˚u. Napˇr´ıklad filozof A procház´ı stavy At - pˇrem ýˇsl´ı (poˇcáteˇcn´ı stav kaˇzdého filozofa. Je ohodnocen jedn´ım tokenem), Ap- uchopil pravou h ˚ulku, Ae- j´ı (po uchopen´ı druhé h ˚ulky), Al - odevzdal levou h ˚ulku. Dále zde máme reprezentovány samotné j´ıdeln´ı h ˚ulky - a1, a2, a3, a4. Token v tˇechto m´ıstech znaˇc´ı moˇznost uchopen´ı filozofem.

(22)

Uvedená Petriho s´ıˇt obsahuje symetrické konflikty právˇe pˇri procesech uchopen´ı jednotliv ých h ˚ulek. Proces, kter ý ji uchop´ı, znemoˇzn´ı svému sousedovi vstup do stavuj´ı.

Protoˇze zde nen´ı ˇz´adn ´y mechanismus ˇr´ızen´ı pˇrevzet´ı h ˚ulek, m ˚uˇze nastat situace, kdy pouze proces A a proces C budou nekoneˇcnˇe dlouho prob´ıhat a na proces B a D nikdy nepˇrijde ˇrada.

Druhé nebezpeˇc´ı, které tato konstrukce skr ývá, se naz ýváuváznut´ı(deadlock). Obecnˇe to je situace, kdy ˇzádn ý z proces ˚u nem ˚uˇze pokraˇcovat ve své práci. V nˇekter ých pˇr´ıpadech je uzamˇcen´ı ˇzádouc´ı, tedy vyˇzadujeme, aby napˇr´ıklad program po urˇcitém poˇctu krok ˚u skonˇcil. Naopak u operaˇcn´ıho systému vyˇzadujeme, aby bˇeˇzel nepˇretrˇzitˇe, tedy neobsa- hoval ˇzádná uzamˇcen´ı.

Vrát´ıme-li se k naˇsemu pˇr´ıkladu, jistˇe vyˇzadujeme, aby mˇel kaˇzd ý proces moˇznost vyuˇz´ıt sd´ılené prostˇredky a nav´ıc s relativnˇe spravedlivou ˇcetnost´ı. V tomto algoritmu dojde k uváznut´ı v okamˇziku, kdy kaˇzd ý z filozof ˚u uchop´ı svou pravou h ˚ulku, tedy kaˇzd ý z proces ˚u pˇrejde do stavup. V tuto chv´ıli jsou procesy uvázlé, protoˇze pro pˇrechod do dalˇs´ı fáze potˇrebuj´ı pˇr´ıtomnost své levé h ˚ulky, ale ta jiˇz nen´ı volná. Tuto situaci znázor ˇnuje následuj´ıc´ı fragment Petriho s´ıtˇe.

•

Ap Ae

Bp

a2

apl bpp

Figure 10: Uv´aznut´ı v algoritmu hladov ´ych filozof ˚u

Filozof A i B uchopil svou pravou h ˚ulku, tedy i filozof B uchopil h ˚ulku a2. Nyn´ı budou procesy pouze nekoneˇcnˇe dlouho uv´aznut´e v situaci, kdy druhou h ˚ulku nemohou dostat.

(23)

2.7 Stavov ´a anal ´yza Petriho s´ıt´ı

Abychom si formálnˇe popsali situaci uváznutého systému, pop´ıˇseme si nˇekolik vlastnost´ı Petriho s´ıt´ı potˇrebn ých k jejich stavové anal ýze.

• Znaˇcen´ı M’ jedosaˇzitelnéze znaˇcen´ı M, jestliˇze existuje posloupnost pˇrechod ˚u, která je proveditelná ve znaˇcen´ı M a která pˇrevád´ı Petriho s´ıˇt ze znaˇcen´ı M do znaˇcen´ı M’.

• Znaˇcen´ı M Petriho s´ıtˇe se naz ývávˇzdy dosaˇzitelným, jestliˇze je dosaˇzitelné z kaˇzdého dosaˇzitelného znaˇcen´ı.

• PN systém se naz ývá reversibiln´ı, je-li poˇcáteˇcn´ı znaˇcen´ı vˇzdy dosaˇzitelné, a tedy i kaˇzdé libovolné dosaˇzitelné znaˇcen´ı je dosaˇzitelné z libovolného dosaˇzitelného znaˇcen´ı.

• PN systém se naz ývá systémembez uzamˇcen´ı, jestliˇze z poˇcáteˇcn´ıho znaˇcen´ı M0 nen´ı dosaˇzitelné ˇzádné znaˇcen´ı, ve kterém nen´ı ˇzádn ý pˇrechod provediteln ý.

• PN-systém jeˇzivý, jestliˇze pˇri v ývoji systému ˇzádn ý pˇrechod nikdy neztrác´ı moˇznost, ˇze bude nˇekdy v budoucnu znovu proveden, tedy z kaˇzdého dosaˇzitelného znaˇcen´ı je moˇzné spustit v ýpoˇcetn´ı posloupnost obsahuj´ıc´ı vˇsechny pˇrechody.

• M´ısto p PN-systému se naz ývák-omezené(k-bounded), jestliˇze pro kaˇzdé dosaˇzitelné znaˇcen´ı je poˇcet token ˚u v tomto m´ıstˇe nanejv ýˇse rovn ý k.

• PN-systém se naz ývák-omezený, jestliˇze vˇsechna jeho m´ısta jsou k-omezená.

• PN-systémy se naz ývaj´ıbezpeˇcnými(safe), jestliˇze jsou 1-omezené.

Metoda stavové anal ýzy PN systémuhP, T, I, O, M0ise zakládá na konstrukci mnoˇziny dosaˇziteln ých znaˇcen´ı RS(M0)a grafu dosaˇzitelnosti RG.

Definice 2.5 Mnoˇzina dosaˇzitelnosti PN syst´emuhP, T, I, O, M0ije mnoˇzina RS(M0) defino- van´a induktivnˇe takto:

• M0∈RS(M0)

• M0∈RS(M0)V

(∃t∈T)M−→t M’

Kde Mt

−

→M’znaˇc´ı ˇze znaˇcen´ı M’ je bezprostˇrednˇe dosaˇziteln´e ze znaˇcen´ı M.

Graf dosaˇzitelnosti PN systému s mnoˇzinou dosaˇzitelnosti RS(M0) je hranovˇe ohodnocený orien- tovaný graf RG(M0) s následuj´ıc´ımi vlastnostmi:

• RG(M0) je mnoˇzina uzl ˚u grafu

• Mnoˇzina hran A grafu je definov´ana takto:

(24)

◦ A⊆RS x RS x T

◦ hM_i, M_j, ti∈A⇐⇒M_i−→tM_j

• M0 je poˇc´ateˇcn´ı uzel grafu

Máme-li popsán PN systém grafem dosaˇzitelnosti, redukuje se problém anal ýzy PN- systému na problém anal ýzy orientovaného grafu. Plat´ı následuj´ıc´ı vlastnosti:

• Znaˇcen´ı M’ je dosaˇziteln´e ze znaˇcen´ı M ⇐⇒ V grafu RG vede orientovan´a cesta z uzlu M do uzlu M’

• Znaˇcen´ı M je v PN systému vˇzdy dosaˇziteln ým stavem⇐⇒Z kaˇzdého uzlu grafu RG vede orientovaná cesta do uzlu M

• PN systém je reversibiln´ı⇐⇒V grafu RG vede z kaˇzdého uzlu orientovaná cesta do uzlu M0⇐⇒V RG grafu vede orientovaná cesta z kaˇzdého uzlu do kaˇzdého - graf je silnˇe souvisl ý

• PN systém neobsahuje uzamˇcen´ı ⇐⇒ V RG grafu neexistuje uzel, ze kterého by nevedla ˇzádná hrana

• PN systém je ˇziv ý⇐⇒Pro vˇsechny koncové silnˇe souvislé komponenty RG grafu plat´ı: kaˇzd ý pˇrechod ohodnocuje aspo ˇn jednu hranu komponenty

• PN systém je omezen ý⇐⇒Graf RG je koneˇcn ý

Podrobnˇejˇs´ı prohl´ıdka grafu dosaˇzitelnosti umoˇz ˇnuje také identifikovat vzájemnou v ýluˇcnost m´ıst a pˇrechod ˚u, nebo nám umoˇzn´ı nalézt takové znaˇcen´ı, pˇri kterém vznikaj´ı konflikty.

2.8 Sd´ılen´ı zdroj ˚u - pokra ˇcov ´an´ı

Pod´ıváme-li se nyn´ı na Petriho s´ıˇt algoritmu hladov ých filozof ˚u z obrázku ˇc´ıslo 9, m ˚uˇzeme o nˇem ˇr´ıct, jak ých nab ývá vlastnost´ı:

• Vˇsechna m´ısta systému mohou z´ıskat pouze 1 token.=⇒Systém je tedy 1-omezen ý a bezpeˇcn ý

• Systém obsahuje znaˇcen´ı, ve kterém nen´ı provediteln ý ani jeden pˇrechod. =⇒ Systém tedy obsahuje uzamˇcen´ı.

• Pˇri v ývoji systému m ˚uˇze doj´ıt k okamˇziku (uzamˇcen´ı) kdy vˇsechny pˇrechody ztrác´ı moˇznost v budoucnosti.=⇒Systém nen´ı ˇziv ý.

• D´ıky uzamˇcen´ı systému nen´ı moˇznost návratu do poˇcáteˇcn´ıho znaˇcen´ı.=⇒Systém tedy nen´ı reversibiln´ı.

(25)

Jak z této anal ýzy vypl ývá, nen´ı takto navrˇzen ý systém optimáln´ı. Pokus´ıme se tedy odstranit uváznut´ı, které je závaˇznˇejˇs´ım problémem neˇz nespravedlivé rozdˇelován´ı sd´ılen ých zdroj ˚u. Z uvedeného algoritmu vypl ývá, ˇze k uváznut´ı dojde ve chv´ıli, kdy kaˇzd ý proces symetricky zabere jednu ze sd´ılen ých hodnot. ˇReˇsen´ım proto mus´ı b ýt systém, kter ý sd´ılené zdroje zab´ırá v jediném okamˇziku. K mechanismu kontroly moˇznosti zabrán´ı obou sd´ılen ých zdroj ˚u se vrát´ıme pozdˇeji. Petriho s´ıˇt upraveného distribuo- vaného algoritmu potom vypadá takto:

•

• •

•

a1 At

Ae a2

Bt Be

a3 Ct Ce a4

Dt

De

ap bp

cp

dp

ar br

cr

dr

Figure 11: Algoritmus hladov ´ych filozof ˚u bez uv´aznut´ı

Z Petriho s´ıtˇe je patrné, ˇze algoritmus nemá uváznut´ı, protoˇze pokud chce pˇrej´ıt do stavu e, mus´ı m´ıt moˇznost vz´ıt oba sd´ılené zdroje. Nicménˇe stále nemáme zajiˇstˇen ý spravedliv ý pˇr´ıstup vˇsech proces ˚u ke sd´ılen ým zdroj ˚um.

Po proveden´ı stavové anal ýzy docház´ıme ke zjiˇstˇen´ı, ˇze uveden ý systém má zmˇenˇené nˇekteré vlastnosti:

• Vˇsechna m´ısta systému mohou stále z´ıskat pouze 1 token. =⇒ Systém je tedy 1-omezen ý a bezpeˇcn ý

(26)

• Systém jiˇz neobsahuje znaˇcen´ı, ve kterém nen´ı provediteln ý ani jeden pˇrechod.=⇒ Systém tedy neobsahuje uzamˇcen´ı.

• Pˇri v ývoji tohoto systému nem ˚uˇze nastat situace, kdy nˇejak ý pˇrechod ztrác´ı moˇznost budouc´ıho proveden´ı.=⇒Systém je tedy ˇziv ý.

• V systému vˇzdy existuje sekvence pˇrechod ˚u, která vrac´ı systém do poˇcáteˇcn´ıho znaˇcen´ı=⇒Systém je tedy reversibiln´ı.

Nyn´ı se vrát´ıme k mechanismu, kter ý nám zaruˇc´ı, ˇze pˇri pokusu o z´ıskán´ı obou sd´ılen ých promˇenn ých nedojde k uváznut´ı proces ˚u. Jedn´ım z moˇzn ých ˇreˇsen´ı je Lehmann- Rabin ˚uv algoritmus pojmenovan ý po jeho tv ˚urc´ıch [7]. Kaˇzd ý proces zde pracuje pouze se soused´ıc´ımi zdroji, na které se odvolává pomoc´ı relativn´ıch jmen - Res(i,zleva) aRes(i,zprava)s hodnotami volná, obsazená. Dále definujeme lokáln´ı promˇenou ui∈zleva, zprava a operátoropp, kter ý je dopl ˇnkem k hodnotˇe svého argumentu, t.j.opp(zprava)

= zleva aopp(zleva) = zprava

cycle beginpˇrem´yˇslej;

T: ui := random (n áhodn ˇe vybr áno zleva ˇci zprava) P1: if Res(i, ui ) = voln áthenRes(i,ui) := obsazen á;

else gotoP1;

P2: if Res(i,opp(ui)) = voln ´athenRes(i,opp(ui)) := obsazen ´a;gotoE;

E: jez i

ui := random (n áhodn ˇe vybr áno zleva ˇci zprava) Res(i, ui ) = voln á; Res(i,opp(ui)) = voln á;

end;

V ´ypis 4: Lehmann-Rabin ˚uv algoritmus

Cást tohoto fragmentu pseudok ódu si m ˚uˇzeme pro lepˇs´ı porozumˇen´ı zobrazit takéˇ jako Petriho s´ıˇt pro proces A.

Tento algoritmus jiˇz obsahuje mechanismus, kter ý v pˇr´ıpadˇe uchopen´ı jedné h ˚ulky a zjiˇstˇen´ı, ˇze druhá je obsazená, vrát´ı svoji h ˚ulku zpˇet do volné a zaˇcne s novou kontrolou pˇr´ıstupu ke sd´ılen ým h ˚ulkám. V tomto pˇr´ıpadˇe nedojde k úplnému uzamˇcen´ı, protoˇze procesy jsou pˇr´ıpadnˇe restartovány. Obrázek 12 znázor ˇnuje pouze proces uchopen´ı h ˚ulek, proces jejich vrácen´ı je triviáln´ı.

Pokud bychom chtˇeli tyto detailn´ı struktury zaˇclenit do v ýˇse zm´ınˇené struktury algoritmu hladov ých filozof ˚u z obrázku 11, zjistili bychom, ˇze v ýsledná struktura je znaˇcnˇe nepˇrehledná. Toto je také jeden z omezuj´ıc´ıch faktor ˚u vyuˇzit´ı Petriho s´ıt´ı pro modelován´ı sloˇzit ých distribuovan ých systém ˚u.

Tento nedostatek m ˚uˇzeme ˇc´asteˇcnˇe kompenzovat pouˇzit´ım metody transformace grafu.

Pro lepˇs´ı pochopen´ı tohoto probl´emu si tuto transformaci nejdˇr´ıve form´alnˇe definujeme.

(27)

•

Pˇrem ´yˇsl´ı

prav´a h ˚ulka lev´a h ˚ulka

J´ı

uchop L uchop P

vraˇt L vraˇt P

uchop L uchop P

Figure 12: Fragment Lehmann-Rabinova algoritmu uchopen´ı h ˚ulek 2.9 Grafov ´a transformace Petriho s´ıt ˇe

Pro popsán´ı grafové transformace Petriho s´ıtˇe vyuˇzijeme modely algoritm ˚u z pˇredeˇsl ých kapitol. Vyuˇzijeme toho, ˇze je Petriho s´ıˇt orientovan ý bipartitn´ı graf a na jeho uzly pouˇzijeme metodu redukce. Vyuˇz´ıváme redukˇcn´ı pravidla pro transformaci systému na jednoduˇsˇs´ı, tedy na systém, jehoˇz anal ýza bude ˇcasovˇe ménˇe nároˇcná, pˇr´ıpadnˇe triviáln´ı.

Pouˇzitá redukˇcn´ı pravidla mus´ı b ýt vhodnˇe zvolena tak, aby zachovávala vybrané vlastnosti PN systém ˚u. Pˇr´ıkladem m ˚uˇze b ýt ˇzivost, reverzibilita nebo omezenost. Systém vznikl ý pomoc´ı takov ýchto redukˇcn´ıch pravidel pak bude m´ıt stejné vlastnosti jako systém origináln´ı. Následuj´ıc´ı obrázek pˇredstavuje pravidla spojen´ı sekvence m´ıst a spojen´ı sekvence pˇrechod ˚u.

K pravidlu spojen´ı sekvence m´ıst je nutné dodat, ˇze kaˇzdá pˇr´ıpadná dalˇs´ı vstupn´ı hrana m´ısta p1 je také vstupn´ı hranou m´ısta p12 a podobnˇe kaˇzdá v ýstupn´ı hrana m´ısta p2 je i v ýstupn´ı hranou m´ısta p12. Poˇcet token ˚u v m´ıstˇe p12 mus´ı b ýt zárove ˇn roven souˇctu token ˚u v m´ıstech p1 a p2. V pˇr´ıpadˇe spojen´ı sekvence pˇrechod ˚u plat´ı stejná poznámka ohlednˇe vstupn´ıch a v ýstupn´ıch hran, a nav´ıc m´ısto mezi obˇema pˇrechody nesm´ı obsahovat ˇzádné tokeny.

Dalˇs´ı moˇznou metodou transformace sloˇzitˇejˇs´ıho systému na systém jednoduˇsˇs´ı je spojen´ı podobn ých struktur. V tomto pˇr´ıpadˇe se podobné ˇcásti struktury Petriho s´ıtˇe spoj´ı v jednu, která je na vyˇsˇs´ı úrovni. Jej´ı ˇcásti jsou pak reprezentovány popisem jednotliv ých uzl ˚u a hran. Tato metoda je popsána na následuj´ıc´ıch obrázc´ıch ˇc´ıslo 14 a 15, které popisuj´ı diagram systému producent - konzument pro v´ıce objekt ˚u.

V pˇr´ıpadˇe, ˇze bychom chtˇeli m´ıt diagram pro 10 objekt ˚u, nebylo by jiˇz pˇr´ıliˇs vhodné postupovat takto. Proto spoj´ıme podobné struktury do struktury jediné. V ýsledkem je

(28)

p1

p2

p12

t1

t2

⇐⇒ ⇐⇒ t12

Figure 13: Spojen´ı sekvence m´ıst a pˇrechod ˚u

• • •

pˇripraven k produkci prázdn ý sklad pˇripraven ke spotˇrebˇe pˇripraven k dodán´ı a pˇripraven ke spotˇrebˇe a

sklad pln ´y a

pˇripraven k dod´an´ı b pˇripraven ke spotˇrebˇe b

sklad pln ´y b

v ´yroba a dod´an´ı a

v ´yroba b dod´an´ı b

pˇrevzet´ı a spotˇreba a pˇrevzet´ı b spotˇreba b

b b

a a a a

a a

Figure 14: Syst´em producent - konzument pro dva objekty

(29)

diagram systému producent - konzument pro jak ýkoliv objekt, kter ý je znázornˇen na obrázku ˇc´ıslo 15.

• • •

pˇripraven k produkci pr´azdn ´y sklad pˇripraven ke spotˇrebˇe

pˇripraven k dod´an´ı pˇripraven ke spotˇrebˇe

sklad pln ´y x

v ´yroba x dod´an´ı x pˇrevzet´ı x spotˇreba x

x x x x

x x

Figure 15: Syst´em producent - konzument pro x objekt ˚u

Nyn´ı se m ˚uˇzeme vrátit k algoritmu hladov ých filozof ˚u. Pro snazˇs´ı pochopen´ı principu transformace si tento diagram uprav´ıme pouze pro tˇri filozofy A,B,C a troje h ˚ulky f1,f2,f3, tak jak je zobrazen na obrázku ˇc´ıslo 16.

V tomto diagramu m ˚uˇzeme nyn´ı identifikovat tˇri ”podobn´e” skupiny m´ıst a dvˇe

”podobné” skupiny pˇrechod ˚u. Na základˇe v ýˇse uvedené metody spojen´ı podobn ých m´ıst m ˚uˇzeme vytvoˇrit nov ý systém, kter ý má jiˇz pouze tˇri m´ısta nazvanáobˇedvaj´ıc´ı filo- zofové, pˇremýˇslej´ıc´ı filozofové a volné h ˚ulky. Grafické znázornˇen´ı tohoto systému ukazuje obrázek ˇc´ıslo 17.

Posledn´ı vˇec, která nám zb ývá pro zobecnˇen´ı algoritmu, je spojit i podobná m´ısta.

Pro tento úˇcel si take definujeme funkce, které jednotliv ým filozof ˚um pˇridˇeluj´ı levou a pravou h ˚ulku:

• l(a) = r(b) = f1

• l(b) = r(c) = f2

• l(c) = r(a) = f3

Tyto funkce m ˚uˇzeme zobecnit na l(x) a r(x). V ýsledn ý algoritmus je znázornˇen na obrázku ˇc´ıslo 18.

Vid´ıme, ˇze tento diagram je mnohem jednoduˇsˇs´ı, s vˇetˇs´ı m´ırou abstrakce a zobecnˇen´ı.

Pro n´asleduj´ıc´ı algoritmy se jiˇz omez´ıme, z d ˚uvodu vyˇsˇs´ı sloˇzitosti struktury, pouze na tyto typy diagram ˚u.

(30)

•

A pˇrem ´yˇsl´ı

B pˇrem ´yˇsl´ı

C pˇrem ´yˇsl´ı

f1 voln´a

f2 voln´a

f3 voln´a

A j´ı B j´ı C j´ı

a bere h ˚ulky

b bere h ˚ulky

c bere h ˚ulky a vrac´ı h ˚ulky

b vrac´ı h ˚ulky

c vrac´ı h ˚ulky

Figure 16: Algoritmus hladov ´ych filozof ˚u pro 3 filozofy

a b

f1

c

pˇrem ´yˇslej´ıc´ı filozofov´e

voln´e h ˚ulky

obˇedvaj´ıc´ı filozofov´e

a bere h ˚ulky

b bere h ˚ulky

c bere h ˚ulky a vrac´ı h ˚ulky

b vrac´ı h ˚ulky

c vrac´ı h ˚ulky

f1 f3

f1 f2 f2 f3 f1 f3

f1 f2 f2 f3

a

c a

c

c c

b b

a a

Figure 17: Algoritmus hladov ´ych filozof ˚u se spojen ´ymi m´ısty

(31)

a b

f1

c

pˇrem ´yˇslej´ıc´ı filozofov´e

voln´e h ˚ulky

obˇedvaj´ıc´ı filozofov´e

uchopen´ı vr´acen´ı

x x

l(x) r(x)

Figure 18: Zobecnˇen ý algoritmus 3 hladov ých filozof ˚u 2.10 V ýb ˇer vedouc´ıho

Tento znám ý a pouˇz´ıvan ý algoritmus se poprvé objevuje v lokáln´ıch s´ıt´ıch typutoken ring. Tyto kruhové s´ıtˇe funguj´ı na principu pˇredáván´ı speciáln´ıho rámce (tzv. tokenu) mezi uzly. Uzel, vlastn´ıc´ı tento token, má jako jedin ý právo vys´ılat. M ˚uˇze se ale stát, ˇze je tento token ztracen, a potom nastává potˇreba nˇejak ým zp ˚usobem tento token znovu vytvoˇrit.

n−2 n−1

0

1

2

i

Figure 19: S´ıˇt typu token ring

Pokud se na tyto uzly pod´ıváme jako na procesy pracuj´ıc´ı v jedné s´ıti, m ˚uˇzeme tento princip rozˇs´ıˇrit i mimo pouhé vys´ılán´ı zpráv na problém ˇr´ızen´ı práce vˇsech tˇechto uzl ˚u v rámci distribuované s´ıtˇe.

Jednoduch ým ˇreˇsen´ım tohoto problému je takzvan ý ”Bully” algoritmus popsan ý v [8]. Tento algoritmus je moˇzné pouˇz´ıt pouze v pˇr´ıpadˇe oˇc´ıslovan ých proces ˚u. Algorit- mus zaˇc´ıná v okamˇziku, kdy jak ýkoliv proces P zjist´ı, ˇze po pevnˇe urˇcené dobˇe nedostal

(32)

zprávu od aktuáln´ıho vedouc´ıho, nebo s n´ım nem ˚uˇze navázat spojen´ı. Od této chv´ıle zaˇc´ıná sekvence krok ˚u tohoto algoritmu.

• P rozeˇsle zpr´avu o volbˇe vˇsem proces ˚um, kter´e maj´ı vˇetˇs´ı ID.

• pokud P nedostane zpˇet zprávu od ˇzádného procesu s vˇetˇs´ım ID, vyhrává volbu a rozeˇsle zprávu o v´ıtˇezstv´ı.

• pokud P dostane zpˇet zprávu od nˇejakého procesu s vˇetˇs´ım ID, vyˇcká pevnˇe urˇcenou dobu, zda se proces s vyˇsˇs´ım ID prohlás´ı za v´ıtˇeze. Pokud tuto zprávu nedostane, spust´ı nové kolo volby.

V pˇr´ıpadˇe, ˇze proces dostane zpr´avu o volbˇe od procesu s niˇzˇs´ım ID, ihned spust´ı nov´e kolo volby.

Dalˇs´ım znám ým ˇreˇsen´ım tohoto problému je Chang-Roberts algoritmus, poprvé popsan ý v [9]. Tento algoritmus pˇredpokládá, ˇze kaˇzd ý proces má univerzáln´ı ID (UID) a jednotlivé procesy mohou vytvoˇrit kruhovou s´ıˇt. Algoritmus se skládá ze dvou ˇcást´ı.

• Kaˇzd ý proces je oznaˇcen jakonez úˇcastnˇený

• Uzel, kter ý zjist´ı nepˇr´ıtomnost vedouc´ıho, zaháj´ı volbu. Oznaˇc´ı se zaz úˇcastnˇeného a odeˇslezprávu o zahájen´ı volbypo smˇeru hodinov ých ruˇciˇcek se sv ým UID.

• Kdyˇz proces obdrˇz´ızprávu o zahájen´ı volby, porovná své UID s UID ve zprávˇe volby.

Pokud má své aktuáln´ı UID vˇetˇs´ı neˇz to ve zprávˇe, pˇrep´ıˇse UID vezprávˇe o zahájen´ı volbysv ým a odeˇsle ji po smˇeru hodinov ých ruˇciˇcek. Oznaˇc´ı se zaz úˇcastnˇeného.

• V pˇr´ıpadˇe ˇze tutozprávu o zahájen´ı volby obdrˇz´ı jiˇz za stavuz úˇcastnˇený, je postup odliˇsn ý. Opˇet porovná své UID s UID ve zprávˇe, ale odeˇsle tuto zprávu dále pouze v pˇr´ıpadˇe, ˇze je nutné UID zprávy pˇrepsat.

Prvn´ı ˇcást algoritmu skonˇc´ı ve chv´ıli, kdy proces obdrˇz´ı zprávu o zahájen´ı volby se sv ým UID. V tuto chv´ıli se spouˇst´ı ˇcást druhá.

• Tento v´ıtˇezn ý proces se oznaˇc´ı jakonez úˇcastnˇený a odeˇslezprávu o výsledku volby, oznamuj´ıc´ı jeho zvolen´ı a jeho UID svému sousedovi.

• Kdyˇz uzel obdrˇz´ı zprávu o v ýsledku volby, oznaˇc´ı se jakonez úˇcastnˇený, zaznamená si UID zvoleného vedouc´ıho azprávu o výsledku volbypoˇsle zase dál.

• Kdyˇz zpráva o v ýsledku volby doputuje k novˇe zvolenému vedouc´ımu, je tento algoritmus v ýbˇeru vedouc´ıho ukonˇcen.

Variantou tˇechto ˇreˇsen´ı je algoritmus, kter ý z celkové mnoˇziny moˇzn ých kandidát ˚u jejich postupn ým porovnáván´ım odstra ˇnuje nevhodné kandidáty. V závˇeru v ýpoˇctu tak z ˚ustává pouze jedin ý, nejlepˇs´ı kandidát. Princip tohoto algoritmu reprezentuje Petriho s´ıˇt na obrázku ˇc´ıslo 20 uvedená v [1].

(33)

V

zpr´avy

ˇcek´a aktualizuje

a

b

c

z≤y

z > y M(x,y)

(x,z) (x,z)

(x,y) (x,y)

(x,y) (x,z)

(x,y)

Figure 20: V ´ybˇer vedouc´ıho

Na zaˇcátku jsou vˇsechny m´ısta ve stavu ˇceká. Pozdˇeji se tu budou objevovat stále lepˇs´ı kandidáti na vedouc´ıho. Jakékoliv m´ısto x z ˇcekaj´ıc´ıch m ˚uˇze pomoc´ı akce a dát vˇedˇet sv ým soused ˚um o sobˇe a svém aktuáln´ım kandidátu na vedouc´ıho y. T´ım se m´ısto stane aktualizuj´ıc´ı. Aktualizuj´ıc´ı m´ısto (x,y) m ˚uˇze dostat zprávu o novém kan- didátu (x,z). Pokud tento novˇe navrˇzen ý kandidát nepˇresáhne stávaj´ıc´ıho kandidáta, m´ısto(x,y)z ˚ustane aktualizuj´ıc´ı pomoc´ı akceb. V opaˇcném pˇr´ıpadˇe se doˇcekaj´ıc´ıchm´ıst vrát´ı s nov ým kandidátemzpomoc´ı akcec. Na konci pak z ˚ustanou pouze dvojice sloˇzené ze vˇsech m´ıst a nejlepˇs´ıho kandidáta.

2.11 Minim ´aln´ı kostra grafu

Posledn´ım algoritmem, kterému se budu vˇenovat v této kapitole, je algoritmus hledán´ı minimáln´ı kostry grafu. Podgraf grafu, kter ý spojuje vˇsechny uzly a je stromem, se naz ývá kostra grafu. Graf m ˚uˇze m´ıt nˇekolik rozd´ıln ých koster. Pokud jsou hrany grafu ohodnoceny, souˇcet tˇechto ohodnocen´ı se naz ýváváha grafu. V takovémto grafu s ohodnocen ými hranami je moˇzné naj´ıt minimáln´ı kostru grafu, která má váhu menˇs´ı nebo rovnu vahám vˇsech ostatn´ıch koster tohoto grafu.

Hledán´ı minimáln´ı kostry grafu se pouˇz´ıvá vˇsude tam, kde je vhodné minimalizo- vat zdroje potˇrebné na komunikaci mezi procesy v rámci s´ıtˇe. Dalˇs´ı vyuˇzit´ı tohoto algoritmu pˇredstavuj´ı aplikace s komplexn´ımi s´ıtˇemi a mnoˇzstv´ım potencionáln´ıch kontroln´ıch problém ˚u. Vyuˇzit´ım vys´ılán´ı pouze po kostˇre tˇechto s´ıt´ı je v ýraznˇe sn´ıˇzena jejich komplexnost a t´ım pádem i sn´ıˇzen ý v ýskyt problém ˚u.

Distribuované ˇreˇsen´ı tohoto problému spoˇc´ıvá v komunikaci mezi jednotliv ými uzly [10]. Na poˇcátku jednotlivé uzly znaj´ı váhu pouze pˇrilehl ých hran. Kaˇzd ý z uzl ˚u pak provád´ı lokáln´ı algoritmus, kter ý se sestává z pos´ılán´ı zpráv po tˇechto hranách a jejich zpracován´ı. Poté je schopen urˇcit, které hrany tvoˇr´ı minimáln´ı kostru grafu.

Uvád´ım zde tento algoritmus pro demonstraci vhodnosti pouˇzit´ı grafové reprezentace, jak ji uvád´ı W. Reisig ve své monografii [1]. Vyuˇz´ıvá k tomuto úˇcelu v ýˇse popsan ý algoritmus V ýbˇeru vedouc´ıho. Tento algoritmus je ukonˇcen s t´ım, ˇze vˇsechny uzly znaj´ı svého vedouc´ıho. Pokud se k této informaci pˇripoj´ı vzdálenost k nˇemu a bliˇzˇs´ı soused

(34)

3 2

2 8

8 6

4

9 9

9

Figure 21: Minim´aln´ı kostra

vzhledem k vedouc´ımu, m ˚uˇze uzel komunikovat s vedouc´ım pr´avˇe pˇres tohoto souseda.

Linky spojuj´ıc´ı takto uzly s vedouc´ım pˇres bliˇzˇs´ı sousedy tvoˇr´ı minim´aln´ı kostru grafu.

Tento algoritmus reprezentuje diagram z obr´azku ˇc´ıslo 22.

(x,y,0) V

zpr´avy

ˇcek´a aktualizuje

a

b

c

j+ 1≥i

j+ 1< i N(x,i)

(x,z,j) (x,z,j)

(x,y,i) (x,y,i)

(x,y,i) (x,z,j+1)

(x,y,i)

Figure 22: Minim´aln´ı kostra grafu

Na poˇcátku vedouc´ı r ˇceká s délkou 0 k vedouc´ımu. Ostatn´ı uzly jsou v m´ıstˇe ak- tualizace, zat´ım bez kandidáta na vedouc´ıho a s nekoneˇcnou vzdálenost´ı. V pozdˇejˇs´ıch fáz´ı obsahuje m´ıstoˇcekátoken (x,y,i), kde je reprezentována trasa délkyizxpˇresyk vedouc´ımu. Cekaj´ıc´ıˇ uzel x zaˇsle svou aktuáln´ı vzdálenost i vˇsem sv ým soused ˚um pomoc´ı akce a a stane seaktualizuj´ıc´ım. Aktualizuj´ıc´ı uzel m ˚uˇze obdrˇzet zprávu (x,z,j). Pokud vzdálenost ve zprávˇejodzk vedouc´ımu nevylepˇs´ı aktuáln´ı vzdálenosti, z ˚ustává uzelx

(35)

u vzdálenostiipˇresypomoc´ı akceb. V opaˇcném pˇr´ıpadˇe zmˇen´ıxvzdálenost naj+1pˇres zpomoc´ı akcec.

Tento algoritmus potvrzuje vhodnost pouˇzit´ı Petriho s´ıt´ı pro reprezentaci distribuovan ých algoritm ˚u, která pˇrináˇs´ı na prvn´ı pohled podobné struktury, které by nebyly tak zˇrejmé pˇri pouˇzit´ı jin ých formalism ˚u.

(36)

3 Vz ´ajemn ´e vylou ˇcen´ı - model

3.1 Uvod´

V této kapitole si vytvoˇr´ıme d ˚ukladn ý model algoritmu vzájemného vylouˇcen´ı podrobnˇe popsan ý v [6].V kaˇzdém kroku si pop´ıˇseme situaci, ukáˇzeme si návrh ˇreˇsen´ı pomoc´ı zápisu v pseudok ódu a pro srovnán´ı i pomoc´ı Petriho s´ıt´ı, které je pro modelován´ı pouˇzito i v monografii Reisig, W.: Elements of distributed algoritms (Springer 1998). Pro zápis v pseudok ódu pouˇziji následuj´ıc´ı pˇr´ıkazy:

• begin je zaˇc´atek procesu

• parbegin je zaˇc´atek paraleln´ıch proces ˚u

• parend je konec paraleln´ıch procesu

• end je konec procesu

Pˇr´ıklad: begin S1, parbegin S2, S3, S4, parend, end 3.2 Probl ´em

Synchronizace je v informatice fundamentáln´ı v ýzvou. Stává se hlavn´ı otazkou v ýkonu a návrhu soubˇeˇzného programován´ı v modern´ıch architekturách.

Soubˇeˇzn ý pˇr´ıstup ke sd´ılen ým prostˇredk ˚um nˇekolika procesy mus´ı b ýt ˇr´ızen, aby nedoˇslo k neˇzádouc´ımu ruˇsen´ı mezi konfliktn´ımi operacemi. Algoritmy vzájemného vy- louˇcen´ı jsou mechanismy slouˇz´ıc´ı právˇe pro ˇr´ızen´ı tˇechto soubˇeˇzn ých pˇr´ıstup ˚u. Proces m ˚uˇze pˇristoupit ke sd´ılenému zdroji pouze uvnitˇr kritické sekce, v n´ıˇz má také garan- tován exkluzivn´ı pˇr´ıstup. Tento pˇr´ıstup je znaˇcnˇe populárn´ı zejména d´ıky jednoduchosti svého modelu a moˇznostem implementace, které jsou efektivn´ı a pˇrenositelné. Vˇsechny souˇcasné soubˇeˇzné programy vyuˇz´ıvaj´ı nˇejak ý ze systém ˚u vzájemného vylouˇcen´ı pro svou synchronizaci. Tento problém se bˇeˇznˇe vyskytuje v operaˇcn´ıch systémech, databáz´ıch, poˇc´ıtaˇcov ých s´ıt´ıch a vˇsude tam, kde je potˇrebné vyˇreˇsit konflikt, ke kterému docház´ı v pˇr´ıpadˇe pokusu o pˇr´ıstup k jedinému sd´ılenému zdroji v´ıce procesy.

Formálnˇe je tento proces definován takto: kaˇzd ý z proces ˚u vykonává sadu instrukc´ı v nekoneˇcné smyˇcce. Tyto instrukce jsou seskupeny do ˇctyˇr skupin: zbytek, vstup, krit- ické sekce, v ýstup.

Programov ý zápis této struktury vypadá následovnˇe:

loop forever ; k ´od zbytku;

k ´od vstupu;

kritick ´a sekce};

k ´od v´ystupu;

endloop

V ýpis 5: Popis problému vzájemného vylouˇcen´ı

(37)

Proces vˇzdy zaˇc´ıná spuˇstˇen´ım zbytkového k ódu. V urˇcit ý okamˇzik m ˚uˇze nastat situace, ve které potˇrebuje spustit k ód v kritické sekci. Pro vstup do kritické sekce mus´ı proces proj´ıt celou procedurou, která zajist´ı, ˇze bˇehem zpracováván´ı své kritické sekce ˇzádn ý j´ın ý proces nespust´ı svoji kritickou sekci. Po v ýstupu z kritické sekce spust´ı v ýstupn´ı k ód, kter ý ostatn´ım proces ˚um oznám´ı, ˇze jiˇz déle nen´ı ve své kritické sekci. Po té se proces vrát´ı ke zbytku k ódu.

Problém vzájemného vylouˇcen´ı je tedy napsat takov ý vstupn´ı a v ýstupn´ı k ód, ˇze cel ý algoritmus dodrˇz´ı dvˇe základn´ı podm´ınky.

• Vzájemné vylouˇcen´ı: ˇZádné dva procesy nejsou ve své kritické sekci ve stejn ý okamˇzik.

• Bez uzamˇcen´ı: Pokud se proces snaˇz´ı dostat do své kritické sekce, pak nˇejak ý pro- ces, ne nutnˇe ten stejn ý, se do kritické sekce dostane.

Druhá podm´ınka zajiˇsˇtuje, ˇze cel ý systém jako celek m ˚uˇze vˇzdy pokraˇcovat ve v ývoji.

To nicménˇe neznamená, ˇze nem ˚uˇze doj´ıt k hladovˇen´ı(starvation) nˇekterého z proces ˚u.

Proto se pˇridává následuj´ıc´ı podm´ınka:

• Bez hladovˇen´ı: Pokud se proces snaˇz´ı dostat do kritick´e sekce, mus´ı do n´ı pozdˇeji i vstoupit.

I kdyˇz je tato podm´ınka mnohem silnˇejˇs´ı neˇz podm´ınka bez uzamˇcen´ı, stále umoˇz ˇnuje nˇekter ým proces ˚u násobnˇe v´ıckrát neˇz proces ˚um, které se zat´ım pouze chystaj´ı ke vstupu. K odstranˇen´ı tohoto chován´ı slouˇz´ı ˇctvrtá podm´ınka vzájemného vylouˇcen´ı:

• Fairness: ˇZádn ý ze vstupuj´ıc´ıch proces ˚u nesm´ı vstoupit do kritické sekce pˇred t´ım, neˇz tam vstoup´ı procesy jiˇz ˇcekaj´ıc´ı pˇred nimi.

V následuj´ıc´ı kapitole se detailnˇeji zamˇeˇr´ıme na modelován´ı distribuovaného vzájem- ného vylouˇcen´ı od nejjednoduˇsˇs´ıch systému po sloˇzitˇejˇs´ı. Zamˇeˇr´ıme se na jednotlivé podm´ınky, které mus´ı vzájemné vylouˇcen´ı dodrˇzet a jak ým zp ˚usobem je m ˚uˇzeme za- komponovat do samotného algoritmu.

3.3 Model

Jak jiˇz bylo zm´ınˇeno v úvodu, prvn´ı podm´ınka algoritmu vzájemného vylouˇcen´ı zn´ı takto:

Ve své kritické sekci m ˚uˇze být v daný okamˇzik pouze jeden proces.

Jednoduch ým ˇreˇsen´ım tohoto problému je pouˇzit´ı speciáln´ı promˇenné tah, která urˇc´ı, kter ý z proces ˚u je na ˇradˇe se vstupem do své kritické sekce. V ýsledkem je potom následu- j´ıc´ı algoritmus: