Simulace a n avrh vyv ´jej ´c ´ch se´ syst emujanousek/publications/2008-habilitace.pdf ·...

Simulace a navrh vyvıjejıcıch sesystemu

Vladimır Janousek

Fakulta informacnıch technologiı, Vysoke ucenı technicke v Brne

Brno, 2008

Simulace a navrh vyvıjejıcıch se systemu

Vladimır Janousek1

FIT, Brno University of Technology, Czech Rep., email: [email protected]

Simulace a navrh vyvıjejıcıch se systemu

Vladimır Janousek

Brno 2008

c© Vladimır Janousek, 2008

Predmluva

Aplikacı simulace a formalnıch modelu, zvlaste pak modelu na bazi DEVS (Discrete EventSystems Specification) v navrhu systemu se ve svete dlouhodobe zabyva predevsım skupinaprof. Zeiglera (Univ. of Arizona). Prıstup teto skupiny v poslednı dobe stavı predevsımna zavedenych programovacıch jazycıch, jako je C++ a Java a na sladenı zavedenychmetod softwaroveho inzenyrstvı s vyuzitım modelovanı a simulace v navrhu systemu. Tentoprıstup je s uspechem pouzıvan v prumyslu, zvlaste pak ve vyvoji vojenskych a kosmickychtechnologiı (vyzkum v teto oblasti podporuje zejmena NASA a Ministerstvo obrany USA).

Skupina modelovanı a simulace na FIT VUT v Brne nenı ani zdaleka tak silna, ale takese snazı aplikovat formalnı modely a simulaci ve vyvoji systemu. Vychazı vsak z ponekudjinych korenu, ktere nejsou tak tesne svazany s prumyslem a jsou vhodne spıse pro jinytyp projektu a s tım souvisejıcı jiny prıstup k vyvoji systemu. Klade duraz predevsımna rychle prototypovanı, experimentalnı programovanı, dynamicke jazyky a objektovouorientaci zalozenou na prototypovych objektech. Tento prıstup je obecne vhodny pro navrha vyvoj systemu s nejasnou specifikacı, kterou je treba dopracovat az v ramci vyvoje acıloveho nasazenı. Krome moznosti zkoumat a interaktivne vyvıjet system za behu jetez predmetem zkoumanı moznost automatickeho vyvoje modelu. Oba zmınene prıpadyvyzadujı zabyvat se otevrenostı a reflektivitou v souvislosti s formalnımi modely, simulacıa objektovou orientacı.

Otevrenost, reflektivitu, experimentalnı programovanı a objektovou orientaci se cle-nove skupiny snazı aplikovat priblizne od r. 2000. V te dobe existovala experimentalnıimplementace interpretu Objektove orientovanych Petriho sıtı (OOPN), ktere jsem navrhla formalne definoval v ramci sve disertacnı prace. Pro OOPN jsem v te dobe navrhl konceptotevrene architektury, umoznujıcı reflektivnı zasahy do modelu a simulatoru v dobe behu.Toto tema posleze podrobne zpracoval ve sve disertacnı praci Radek Kocı. Implemento-vana byla tenkrat ale jen cast potrebnych reflektivnıch vlastnostı, ktere byly nezbytne projednoduce experimenty napr. s vnorenou simulacı. V ramci zkoumanı moznostı multipa-radigmatickeho prıstupu k tvorbe modelu s jednoduchym jednotıcım formalismem byloposleze rozhodnuto paralelne aplikovat tytez principy pro podstatne jednodussı formalis-mus, a sice DEVS (Discrete EVent Systems Specification). Dıky konceptualnı jednodu-chosti a hierarchicke strukture s volne vazanymi komponentami je DEVS pouzitelny jakospolecny zaklad pro aplikaci ruznych formalismu v ramci jednoho simulacnıho modelu.Experimentalnı implementace, kterou jsem vytvoril, splnovala vsechny klıcove pozadavky– byl to system s plnou reflektivitou, umoznujıcı neomezene zasahy do simulace v dobebehu. Experimentalne byly tez implementovany vizualnı nastroje pro inspekci a editacimodelu (implementaci techto nastroju provedl v ramci sve diplomove prace Elod Kiron-sky). Vytvorene prostredı nynı poskytuje ramec, do ktereho je mozne potencialne zaclenitinterprety jinych formalismu. V soucasne dobe je do tohoto prostredı vnoren a v tomto pro-

iv

stredı uspesne pouzıvan interpret OOPN (dıky Radkovi Kocımu). Jednou z vetsıch aplikacıOOPN je prostredı pro vyvoj multiagentnıch systemu, ktere jako soucast sve disertacnıprace navrhl a implementoval Zdenek Mazal.

V uvedenem kontextu se nynı jevı jako vhodne popsat klıcove aspekty soucasneho stavupoznanı v oblasti aplikace reflektivity pro potreby modelovanı a simulace vyvıjejıcıch sesystemu. A o tom je tato prace.

Autor

Abstrakt

Tato prace se zabyva problematikou modelovanı, simulace a navrhu systemu s diskretnımiudalostmi s durazem na nepretrzite bezıcı a vyvıjejıcı se systemy. Konkretne se zabyvatemito tematy:

• Vymezenı trıdy vyvıjejıcıch se systemu, zahrnujıcı jak interaktivnı, tak automatickyvyvoj.

• Systemy s diskretnımi udalostmi, formalismus DEVS, jeho varianty, vcetne existujı-cıch modifikacı, zavadejıcıch strukturnı dynamiku.

• Reflektivnı DEVS a otevrena abstraknı architektura pro modelanı, simulaci a navrhsystemu.

• Prostredky pro interaktivnı evolucnı navrh systemu.

• Prıpadove studie, demonstrujıcı reflektivitu a dynamicky vyvoj struktury systemu.

Hlavnım prınosem prace je (1) zmapovanı problematiky vyvıjejıcıch se systemu, za-hrnujıcı predevsım dynamickou manipulaci s modely a simulacemi v kontextu navrhusystemu s vyuzitım simulace, (2) koncept abstraktnı architektury pro simlaci vyvıjejıcıchse systemu a (3) a overenı navrzeneho konceptu abstraktnı achitektury pro vyvıjejıcı sesystemy prıkladem prakticke realizace, aplikovane v nekolika prıpadovych studiıch. To vsev navaznosti na teorii modelovanı a simulace systemu s diskretnımi udalostmi.

vi

Obsah

1 Uvod – vyvıjejıcı se systemy 1

2 Systemy s diskretnımi udalostmi 52.1 Systemy, znalosti, problemy . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Simulacnı modelovanı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Cas, trajektorie a segmenty . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.5 Formalismus DEVS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.5.1 System s diskretnımi udalostmi . . . . . . . . . . . . . . . . . . . . . 82.5.2 Zakladnı model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.5.3 Slozeny model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5.4 Pouzitı portu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5.5 Varianty a rozsırenı zakladnı definice DEVS . . . . . . . . . . . . . . 12

2.6 Hierarchicka simulace DEVS (abstraktnı simulator) . . . . . . . . . . . . . . 122.7 Prakticke pouzitı formalismu DEVS . . . . . . . . . . . . . . . . . . . . . . 15

2.7.1 DEVS a objektova orientace . . . . . . . . . . . . . . . . . . . . . . 162.7.2 Prıklady modelu a jejich implementace . . . . . . . . . . . . . . . . . 16

3 Systemy s dynamicky se menıcı strukturou 213.1 Dynamicky DEVS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Abstraktnı simulator pro dynamicky DEVS . . . . . . . . . . . . . . . . . . 233.3 Aplikace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Otevrena abstraktnı architektura 274.1 Vymezenı pozadovanych vlastnostı . . . . . . . . . . . . . . . . . . . . . . . 274.2 Simulace v realnem case, propojenı s realnym okolım . . . . . . . . . . . . . 274.3 Klonovanı a migrace systemu a simulacı . . . . . . . . . . . . . . . . . . . . 314.4 Ctenı a modifikace modelu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.5 Systemy simulacı (multisimulace) . . . . . . . . . . . . . . . . . . . . . . . . 384.6 Shrnutı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5 Vyvoj systemu v simulaci, nastroj SmallDEVS 415.1 Motivace a zvoleny prıstup . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2 Experimentalnı programovanı a Smalltalk . . . . . . . . . . . . . . . . . . . 425.3 Objektova orientace zalozena na prototypech . . . . . . . . . . . . . . . . . 455.4 Modelovanı systemu prototypovymi objekty . . . . . . . . . . . . . . . . . . 475.5 Sdılene chovanı, znovupouzitelnost . . . . . . . . . . . . . . . . . . . . . . . 50

viii OBSAH

5.6 In(tro)spekce a reflektivita . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.7 Operacnı system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.7.1 Smalltalk a SmallDEVS . . . . . . . . . . . . . . . . . . . . . . . . . 525.7.2 Perzistence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.7.3 Vizualnı nastroje pro manipulaci s modely a simulacemi . . . . . . . 53

5.8 Aplikacnı rozhranı jadra SmallDEVS . . . . . . . . . . . . . . . . . . . . . . 545.9 Poznamka k implementaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6 Specifikace systemu formalismem OOPN 576.1 Petriho sıte a objekty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.1.1 Princip vysokourovnove Petriho sıte . . . . . . . . . . . . . . . . . . 586.1.2 Paralelnı objektove orientovany system . . . . . . . . . . . . . . . . 586.1.3 Modelovanı objektu Petriho sıtemi . . . . . . . . . . . . . . . . . . . 596.1.4 Interakce objektu – zasılanı zprav . . . . . . . . . . . . . . . . . . . 606.1.5 Invokace metod objektu zasılanım zprav . . . . . . . . . . . . . . . . 606.1.6 Atomicka synchronnı interakce objektu . . . . . . . . . . . . . . . . 60

6.2 Formalismus OOPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.2.1 Struktura OOPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.2.2 Reprezentace stavu OOPN . . . . . . . . . . . . . . . . . . . . . . . 626.2.3 Dynamika OOPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.3 Simulator OOPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.4 Zapouzdrenı OOPN do DEVS . . . . . . . . . . . . . . . . . . . . . . . . . . 656.5 Dynamicke aplikacnı rozhranı simulatoru . . . . . . . . . . . . . . . . . . . . 656.6 Shrnutı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7 Reflektivnı simulator DEVS 67

8 Simulace simulujıcıho systemu 718.1 Prıklad vnorene simulace: System hromadne obsluhy, jehoz cast je optima-

lizovana opakovanou vnorenou simulacı . . . . . . . . . . . . . . . . . . . . 718.2 Model s vnorenou simulacı v jazyce SIMULA . . . . . . . . . . . . . . . . . 738.3 Model s vnorenou simulacı v jazyce PNtalk . . . . . . . . . . . . . . . . . . 77

8.3.1 Trıda BankModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778.3.2 Class Bank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818.3.3 Vnorena simulace, interakce casovych os . . . . . . . . . . . . . . . . 828.3.4 Simulace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.4 Zaver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

9 Prostredı pro vyvoj multiagentnıch systemu 859.1 Multiagentnı systemy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859.2 Aplikace v OOPN a DEVS v multiagentnıch systemech . . . . . . . . . . . 869.3 Shrnutı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

10 Dynamicke modely v rızenı projektu 9310.1 Zakladnı pojmy z oblasti rızenı projektu . . . . . . . . . . . . . . . . . . . . 9310.2 Modelovanı projektoveho portfolia . . . . . . . . . . . . . . . . . . . . . . . 9410.3 Shrnutı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

OBSAH ix

11 Zaver 101

x OBSAH

Kapitola 1

Uvod – vyvıjejıcı se systemy

Tato prace se zabyva vyuzitım simulace v navrhu a vyvoji pocıtacovych (i kdyz nikolivnutne jen pocıtacovych) systemu, ktere jsou pouzıvany v realnem prostredı, majı tedydefinovane vstupy a vystupy a pracujı v realnem case. Zvlastnı pozornost je pritom veno-vana vyvoji struktury systemu nejen v prubehu navrhu a testovanı, ale i behem realnehopouzıvanı a udrzby. K vyvoji struktury systemu muze dochazet jednak inkremetalnımizasahy zvencı, jednak automatickou adaptacı systemu na menıcı se vnejsı podmınky.

Modelovacı formalismy Problematika vyvıjejıcıch se systemu bude popsana obecne,na urovni abstraktnıch modelu s rigorozne definovanymi pojmy cas, stav, vstup a vy-stup. Konkretnı formalismus pro nas nenı nijak zavazujıcı, duraz bude kladen na v prımounavaznost na pojmy obecne teorie systemu. Jako spolecny zaklad pro uvahy o pouzitı ruz-nych formalismu bude pouzit formalismus pro specifikaci systemu s diskretnımi udalostmi– DEVS (Discrete EVent systems Specification). Tento formalismus je vyznamny svoubezprostrednı vazbou na obecnou teorii systemu a prave takovou urovnı abstrakce, kteraje idealnı pro simulaci a navrh systemu, ktere jsou predmetem naseho zajmu (t.j. prede-vsım pocıtacovych systemu libovolneho druhu). Ostatnı v uvahu pripadajıcı formalismy,jako jsou napr. konecne automaty, stavove diagramy (statecharts) a Petriho sıte, jsou doDEVS relativne snadno mapovatelne. I systemy jinych typu, jako jsou spojite systemy asystemy s diskretnım casem, lze take do DEVS snadno transformovat. DEVS jako spo-lecny formalnı zaklad pro ruzne prıstupy k modelovanı a simulaci usnadnuje transformacimodelu, portabilitu, migraci a klonovanı modelu, obecny vyvoj novych simulacnıch archi-tektur bez ohledu na konkretnı formalismus nebo specifikacnı jazyk. Vyuzitı formalismu,jako je DEVS, umoznı bezprostrednı provazanı teorie modelovanı a simulace s praxı – mo-dely a simulatory postavene na formalnım zaklade a v souladu s teoriı lze analyzovat jakomatematicke objekty s vyuzitım formalnıch metod a soucasne jsou k dispozici k prımemupraktickemu pouzitı, t.j. jak k simulacnım experimentum, tak k behu v cılovem prostredı.

Vyvoj systemu v simulovanem a v realnem prostredı Zvysujıcı se naroky na kva-litu a schopnosti vyvıjenych systemu, ktere se v dusledku narustajıcıch pozadavku stavajıstale slozitejsımi, vede k vyvoji novych metod navrhu, vyvoje, implementace a udrzbysystemu. Vyvoj systemu v simulaci (Simulation-Based Development) je metoda tvorbypocıtacovych systemu, vyuzıvajıcı dukladne testovanı a verifikaci navrhovaneho systemuve vsech fazıch vyvoje, aniz by bylo nutne se vazat na realne okolı systemu, prıpadne na re-alny cas. Mimo to je simulace ve fazi navrhu uzitecna tehdy, kdyz pro navrhovane systemy

2 KAPITOLA 1. UVOD – VYVIJEJICI SE SYSTEMY

neexistuje predem jasna specifikace. Zde je nezbytne pouzıt evolucnı navrh, ktery spocıvav rychlem a bezprostrednım vytvarnı, modifikaci, testovanı, vyhodnocovanı a porovnavanımnoha kandidatnıch resenı. Podle charakteru hodnotıcı funkce pak muze evoluce systemuprobıhat interaktivne, automaticky, nebo kombinovane. V prıpade interaktivnıho testo-vanı simulovaneho produktu jde o tzv. virtualnı prototypovanı. Podpurna architekturamusı prıslusnou variantu evolucneho navrhu systemu efektivne umoznit.

Adaptace systemu na menıcı se okolnı podmınky Ma-li byt vyvıjeny system vkontaktu s menıcım se prostredım a ma-li i v predem neznamych podmınkach plnit de-finovane cıle, je treba jiz pri navrhu systemu zohlednit moznost adaptace, vyvoje, resp.ucenı. Adaptace systemu na menıcı se prostredı muze byt provadena bud’ inkrementalnımivnejsımi zasahy z prostredı, tedy pusobenım jineho systemu (typicky cloveka-vyvojare),nebo samostatne, na zaklade autonomıho zkoumanı prostredı a ucenı se. Pripustıme-liautonomnı chovanı a adaptaci systemu v neznamem prostredı, ma smysl o systemech,ktere jsou predmetem naseho zkoumanı, uvazovat jako o agentnıch systemech, resp. jakoo inteligentnıch agentech. Pak je vhodne zabyvat se moznymi agentnımi architekturami– system muze byt realizovan jako jednoduchy reaktivnı agent, ktery na zaklade vstupua aktualnıho stavu jednoduse definovanou funkcı generuje vystup, nebo muze byt chapanjako agent deliberativnı (uvazujıcı), jehoz stav je jiz komplikovaneji strukturovan a funkce,modifikujıcı stav na zaklade aktualnıho stavu a vstupu, prıpadne generujıcı vystup na za-klade stavu, jsou pomerne komplikovane funkce, specifikovane napr. prostredky formalnılogiky, prıpadne neuronovymi sıtemi, s vyuzitım fuzzy logiky, genetickych algoritmu apod.

Motivacnı prıklady Smyslem tohoto textu je zmapovat esencialnı skutecnosti, kterese tykajı navrhu a udrzovanı vyvıjejıch se systemu. Pritom je kladen duraz na pouzitısimulace, formalnıch modelu a jejich zachovanı v prubehu a vyvoje i cıloveho nasazenı.Jako motivacnı prıklady a prıpadove studie uvedeme nekolik ruznorodych systemu, kterespojuje prave kontakt s okolnı realitou a duraz na dynamickou manipulaci s modely asimulacemi:

(1) Simulujıcı system. V obecnem pojetı jde o system, jehoz soucastı je simulace.Simuluje-li system sam sebe a pouzıva-li vysledky vlastnı simulace pro modifikaci svehovlastnıho chovanı v budoucnu, mluvıme o reflektivnı simulaci. Jde o prıpad anticipujıcıchosystemu, optimalizujıcıho sve predpokladane budoucı chovanı podle zvolenych kriteriı nazaklade nasobnych simulacı sebe sama. Prıkladem muze byt optimalizace poctu otevre-nych prepazek v bance v zavislosti na zmenach pravdepodobnostnıho rozlozenı prıchozıchklientu v prubehu dne. Jde o analyticky neresitelny problem, proto je nutne pouzıt si-mulaci. Simulace simulujıcıch systemu klade specificke naroky na simulacnı system – jetreba pracovat s nezavislymi casovymi osami a zajistit prenos informacı mezi jednotlivymisimulacemi. To lze resit bud’ s podporou operacnıho systemu (jednotlive simulace spoustetjako procesy OS), nebo v ramci simulacnıho systemu samotneho. Prvnı moznost je snadnodostupna, ale z programatorskeho hlediska tezkopadna, druha moznost je pohodlnejsı, alesimulacnı prostredı ji musı samo o sobe umoznit.

(2) Inkrementalnı vyvoj rıdicıho systemu autonomıho mobilnıho robota v simulovanemprostredı. Jde o vyvoj systemu, jehoz specifikace nenı na pocatku vyvoje zcela jasna aje ji treba dodatecne upresnovat na zaklade vysledku testu, provadenych na pokusnychrealizacıch v ruznych prostredıch. Rıdicı system autonomnıho mobilnıho robota je vhodnevyvıjet a testovat v simulovanem prostredı drıve, nez pristoupıme k testovanı v prostredı

3

realnem. Simulovat pritom lze i tvrdsı podmınky, nez jake ocekavame v realnem prostredı,prıpadne podmınky, ktere sice ocekavame, ale jsou realne tezko vytvoritelne. V prıpade,ze nenı jasny ani okamzik, kdy je cılovy produkt prohlasen za hotovy, musıme pripustit idodatecny vyvoj pri beznem provozu v cılovem prostredı. Aby bylo mozne rıdicı systeminkrementalne vyvıjet jak v simulovanem, tak v realnem prostredı, je nezbytne zachovatmodel rızenı v prubehu celeho vyvoje, vcetne cıloveho nasazenı. Soucastı cılove realizacepak musı byt interpret formalismu, v kterem byl model vytvoren. Soucasne musı byttento interpret zprıstupnen pro monitorovanı stavu a pro inkrementalnı zasahy vyvojare– typicky vzdalene, napr. s vyuzitım webovych sluzeb.

(3) Rızenı projektoveho portfolia, jeho optimalizace a monitorovanı. Projektove port-folio je mnozina aktualne bezıcıch a planovanych projektu. Modely (ramcove plany) pro-jektu, specifikovane napr. sıt’ovymi grafy nebo casovanymi Petriho sıtemi, se pouzıvajı koptimalizaci mechanismu pridelovanı zdroju (rozvrhovanı) a k prubeznemu monitorovanıprubehu projektu. Jak v ramci optimalizace, tak v prubehu monitorovanı se vyuzıva si-mulace. V ramci optimalizace je treba simulovat mnoho kandidatnıch modelu a na zakladevyhodnocenı vysledku vybrat model, ktery nejlepe vyhovuje zadanym kriteriım. V ramcimonitorovanı se pak porovnava simulace planovaneho prubehu projektu s realitou. Postu-pem casu se menı jak projektove portfolio (tj. mnozina aktualnıch projektu), tak strukturadostupnych zdroju. Model celeho systemu se proto musı adekvatnım zpusobem prubezneprizpusobovat takto se menıcım vnejsım podmınkam. Obdobne (v mnohem tytez) pro-blemy se resı v souvislosti se systemy planovanı a rızenı vyroby.

Reflektivnı a metaurovnove architektury Uvedene prıklady demonstrujı vyznamnyaspekt cele trıdy podobnych systemu, kterym je nutnost zabyvat se krome zakladnı (apli-kacnı) urovne take metaurovnı, tedy systemem popisujıcım vyvoj techto systemu. Na tetourovni sledujeme prechody mezi docasne existujıcımi dılcımi systemy. Z praktickeho hle-diska je treba v se v uvedenem kontextu zabyvat krome vzajenneho provazanı reality asimulace (reality-in-the-loop simulation) take metaurovnovou architekturou a reflektivnımrozhranım smulatoru, aby bylo mozne s modely a simulacemi dynamicky (to jest za behu)manipulovat v souladu s teoriı a bez ohledu na to, zda aktorem teto manipulace je vnejsısystem nebo manipulovany system sam.

Souvislosti Metaurovnove a reflektivnı architektury patrı k zakladum pocıtacove vedya jsou neodmyslitelnou soucastı informacnıch technologiı. V oblasti teoretickych zakladustojı za zmınku predevsım Goedeluv dukaz neuplnosti formalnıho systemu a Turinguv uni-verzalnı stroj, pouzity v dukazu nerozhodnutelnosti problemu zastavenı. V oblasti vedyo systemech se napr. Klir zabyva existencı metasystemu, popisujıcıch vyvoj systemu. Zinformacnıch technologiı stojı za zmınku obecne operacnı systemy coz jsou jsou vesmessystemy s metaurovnovou a reflektivnı architekturou – umoznujı vytvarenı a manipulacis programy a procesy, pricemz aktory takove manipulace jsou bezıcı procesy rızene exis-tujıcımi programy. Co do ideove cistoty jsou zajımave systemy, zalozene na dynamickychjazycıch, jako jsou LISP a Smalltalk, prıpadne na jazycıch, ktere jsou LISPem a Small-talkem inspirovany. Zmınene systemy jsou schopne nepretrzite bezet a svymi vlastnımiprostredky samy sebe vyvıjet, a to jak autonomne, tak na zaklade interakce s uzivatelem.Vyvoj systemu za behu na zaklade interakce s vyvojarem je klıcovym predpokladem pro

4 KAPITOLA 1. UVOD – VYVIJEJICI SE SYSTEMY

techniku vyvoje, zvanou experimentalnı programovanı (exploratory programming).1 V ob-lasti umele inteligence je sebemodifikace zakladnım predpokladem schopnosti systemu ucitse.

Hlavnım cılem tohoto textu je popsat fenomen vyvıjejıch se systemu v kontextu simu-lacnıho modelovanı s vyuzitım formalnıch modelu. Motivacı k tomuto pocınanı je snahaaplikovat formalnı modely pri vytvarenı i v ramci udrzby a adaptace pocıtacovych sys-temu na menıcı se podmınky behem jejich zivota. Takove zpruhlednenı vyvıjenych systemui metod jejich vyvoje by melo byt ucinnym prostredkem ke zvysenı jejich uzitne hodnoty.

Obsah Nasledujıcı text je organizovan takto: Po obecnem uvodu do modelovanı a si-mulace systemu s durazem na systemy s diskretnımi udalostmi je popsana problematikasystemu s dynamicky se menıcı strukturou. Pote je definovana abstraktnı architektura prosimulaci vyvıjejıcıch se systemu. Nasleduje diskuse praktickych aspektu definovane archi-tektury, spolu s metodickymi poznamkami. Nakonec jsou uvedeny jednoduche prıpadovestudie, demonstrujıcı aplikaci simulace v navrhu a realizaci vyvıjejıch se systemu.

1Cesky preklad nenı presny, ale v danem kontextu je pouzitelny.

Kapitola 2

Systemy s diskretnımi udalostmi

Kapitola prezentuje systemy s diskretnımi udalostmi, ktere jsou vhodnou abstrakcı promodelovanı pocıtacovych (ale nejen pocıtacovych) systemu v ramci jejich navrhu a vy-voje. Adekvatnost tohoto zpusobu modelovanı je opodstatnena tım, ze jako systemy sdiskretnımi udalostmi lze modelovat vsechny typy dynamickych systemu (t.j. systemu, unichz ma smysl zkoumat chovanı) a tedy vsechny zpusoby aplikacı vyvıjenych systemu.

V navaznosti na zakladnı pojmy teorie systemu a teorie modelovanı a simulace je vnasledujıcıch podkapitolach predstaven formalismus DEVS a jeho abstraktnı simulator.Pro ilustraci prıme vazby teorie a praxe modelovanı a simulace je prezentovana i ukazkapraktickeho pouzitı formalismu DEVS v konkretnım programovacım jazyce.

2.1 Systemy, znalosti, problemy

Klir [Kli85] definuje ramec pro studium systemu, ve kterem rozlisuje 4 epistemologickeurovne, reflektujıcı dostupne znalosti o systemu. Kazda uroven zahrnuje znalosti dostupnev urovnıch nizsıch.

0. Zdrojova uroven (source level, source system) je nejnizsı uroven, kde jde jen o mno-zinu promennych, ktere nas zajımajı.

1. Uroven dat (data level, data system) zahrnuje temporalnı vyvoj promennych v po-dobe casovych rad.

2. Uroven chovanı (behavior level, behavior system), obsahuje znalosti o vztazıch mezihistoriemi promennych. Behavioralnı systemy jsou schopny generovat casove rady(time series), proto se take nazyvajı generativnı systemy.

3. Uroven struktury (structure level, staructural system) zahrnujı znalost o subsyste-mech systemu a o strukture jejıch vzajemnıch vztahu (propojenı).

Tuto hierarchii zavrsuje pata uroven - uroven metasystemu, ktere obsahujı informaci otom, jak se datove, generativnı a strukturnı systemy vyvıjejı v case. Na teto urovni naszajıma dynamika samotneho popisu systemu.

Ve vyse uvedenem kontextu existujı 3 typy problemu k resenı [Kli85]:

1. Analyza systemu. System bud’ existuje, nebo je planovana jeho existence a pokousımese pochopit jeho chovanı. Za pouzitı generativnıho popisu ziskavame a zkoumamedata.

6 KAPITOLA 2. SYSTEMY S DISKRETNIMI UDALOSTMI

2. Inference systemu. System existuje a snazıme se prejıt na vyssı epistemologickouuroven, typicky od dat ke generativnımu popisu.

3. Navrh systemu. System neexistuje a snazıme se ho navrhnout. Prechazıme na vyssıuroven znalostı, od existujıcıch generativnıch komponent ke slozenemu systemu svhodnou strukturou.

Zatımco Klir [Kli85] uvedenou hierarchii znalostı definuje predevsım jako ramec pro zkou-manı moznosti induktivnı identifikace systemu (odvozovanı vyssıch znalostnıch urovnı znizsıch), Zeigler [Zei84, Zei90, ZKP00] a jinı se zamerujı ve vetsı mıre na metody speci-fikace systemu, ktere se dajı uplatnit v modelovacıch a simulacnıch jazycıch. Zabyvajı sepredevsım urovnı struktury a chovanı s cılem generovat data. Diskutovanou otazkou i vteto oblasti je uroven metasystemu, tedy moznost specifikovat a simulovat vyvıjejıcı segenerativnı systemy.

Ucinnym prostredkem pro analyzu chovanı systemu je simulace. Modelovanı a simulacisystemu, zvlaste pak systemu s diskretnımi udalostmi, se venujı nasledujıcı casti kapitoly.

2.2 Simulacnı modelovanı

Zakladnı ramec pro modelovanı a simulaci je podle [ZKP00] definovan ctyrmi entitami(viz obr. 2.1):

1. Zdrojovy system (source system) predstavuje zdroj dat (chovanı).

2. Model predstavuje instrukce pro generovanı dat srovnatelnych s realnym systemem.

3. Simulator provadı instrukce modelu a skutecne generuje chovanı.

4. Experimentalnı ramec (experimental frame) specifikuje podmınky, za kterych systempozorujeme a exeperimentujeme se s nım.

Experimental Frame

SourceSystem

SimulationRelation

ModelingRelation

Simulator

Model

Obrazek 2.1: Zakladnı entity a jejich vztahy

Zakladnı vztahy mezi temito entitami jsou modelovanı a simulace. Relace modelovanıpritom specifikuje, jak model reprezentuje odpovıdajıcı realny system. Mezi systemema modelem musı byt homomorfnı vztah, tj. je prıpustne zjednodusenı. Relace simulacespecifikuje, jak presne simulator realizuje instrukce modelu.

2.3. CAS, TRAJEKTORIE A SEGMENTY 7

Prechod od zdrojoveho systemu k modelu muze byt proveden na zaklade pozorovanıdat zıskanych z experimentu se systemem. Model je pak pouzit k vytvorenı simulatoru,ktery slouzı ke generovanı dat. Chovanı, generovane simulatorem, musı byt validnı, tj.simulator musı generovat stejna nebo podobna data jako zdrojovy system za stejnychpodmınek.

2.3 Cas, trajektorie a segmenty

Zakladnım pojmem dynamickeho systemu je cas, ktery je nezavislou velicinou. Cas jedefinovovan strukturou

time = (T, <),

kdeT je mnozina,< je tranzitivnı, irreflexivnı a antisymetricka relace (usporadanı) nad T .

Jestlize pro kazdou dvojici (t, t′) platı bud’ t < t′, nebo t > t′, nebo t = t′, pak jde olinearnı (uplne) usporadanı. Relaci < definujeme typicky jako linearnı usporadanı, ale vnekterych prıpadech je vhodne pracovat i s castecnym usporadanım, ktere muze modelovatneurcitost v popisu systemu a nasobnost stavovych trajektoriı. Casovou zakladnu T typickydefinujeme tak, ze T = R+

0 (pak jde o spojitou casovou zakladnu), nebo T = N (pak jde odiskretnı casovou zakladnu). Nad T definujeme intervaly: (t1, t2) = τ |t1 < τ < t2, τ ∈ T,[t1, t2] = τ |t1 ≤ τ ≤ t2, τ ∈ T, (t1, t2] = τ |t1 < τ ≤ t2, τ ∈ T. Zapis < t1, t2 > oznacujelibovolny z intervalu. Intervaly nad T nekdy znacıme T<t1,t2>.Je-li T casova zakladna a A libovolna mnozina, funkce

f : T −→ A

se nazyva casova funkce nebo signal. Restrikce f na intervalu < t1, t2 > se nazyva segmentnebo trajektorie

ω :< t1, t2 >−→ A

a zapisuje se ω<t1,t2>. Dva segmenty nazveme sousedıcı, kdyz jejich domeny na sebe na-vazujı. Spojity segment nad spojitou casovou zakladnou je spojity ve vsech bodech. Pocastech spojity segment je spojity ve vsech bodech krome konecneho poctu bodu. Pocastech konstantnı segment je specialnı prıpad po castech spojiteho segmentu. Udalostnısegment ω<t0,tn> :< t0, tn >−→ A∪∅ je segment nad spojitou casovou zakladnou a mno-zinou udalostı A ∪ ∅, kde ∅ znacı ne-udalost. ∅ je hodnotou ω<t0,tn> mezi jednotlivymiudalostmi z mnoziny A, ktere se vyskytly v casech t1, t2, ..., tn−1. Segment nad diskretnıcasovou zakladnou se nazyva sekvence.

2.4 System

System je abstraktnı koncept, popisujıcı chovanı entit v case.1 Popisuje vystupnı chovanına zaklade vstupu a stavove informace. Formalne je system popsan strukturou [ZKP00]

S = (T, X, Ω, Q, q0, Y, δ, λ),1Uvazujeme dynamicky system na urovni 2 Klirovy hierarchie.


kdeT je casova zakladna,X je mnozina vstupnıch hodnot,Y je mnozina vystupnıch hodnot,Ω je mnozina vstupnıch segmentu,Q je mnozina stavu,q0 je pocatecnı stav,δ : Q× Ω −→ Q je prechodova funkce,λ : Q×X −→ Y je vystupnı funkce.

System pritom splnuje nasledujıcı omezenı:(1) Ω je uzavrena vzhledem ke kompozici;(2) pro kazdy par sousedıcıch segmentu ω, ω′ ∈ Ω a pro vsechny stavy q ∈ Q platı:

δ(q, ωω′) = δ(δ(q, ω), ω).

Omezenı (2) zarucuje, ze system muze byt prerusen v libovolnem case a jeho stav jeregistrovan. Pokracovanı z tohoto stavu s pokracovanım vstupnıho segmentu povede dostejneho koncoveho stavu, jako kdyby k prerusenı nedoslo.

Typy systemu Zeigler [ZKP00] definuje 3 zakladnı modelovacı formalismy, resp. typysystemu: System popsany diferencialnımi rovnicemi, system s diskretnım casem a systems diskretnımi udalostmi. Posledne jmenovany formalismus (DEVS, ktery bude popsan vnasledujıcım textu) muze byt modifikovan nebo prımo pouzit pro modelovanı ostatnıchtypu systemu. System popsany diferencialnımi rovnicemi muze byt s vyuzitım vhodnehovzorkovanı a metod numericke integrace preveden na system s diskretnım casem. System sdiskretnım casem muze byt chapan jako zvlastnı prıpad systemu s diskretnımi udalostmi.DEVS je tedy univerzalnı, a proto tento formalismus povazujeme za idealnı nızkourovnovouabstrakci, vhodnou pro vsechny typy systemu. Jine (specialnejsı, prıpadne vysokourovno-vejsı) formalismy je mozne do DEVS relativne snadno transformovat.

2.5 Formalismus DEVS

DEVS je zkratka pro Discrete EVent System Specification, tedy specifikaci systemu s dis-kretnımi udalostmi [ZKP00]. Pro tento formalismus je definovan abstraktnım simulator,ktery lze krome specifikace semantiky chapat take jako vzor pro realnou implementaci.

2.5.1 System s diskretnımi udalostmi

Neformalne lze system s diskretnımi udalostmi popsat nasledujıcım zpusobem. Systemma vstupy a vystupy pozorovatelne jako udalosti. Na nektere vstupy system reaguje vy-stupem (okamzite nebo se zpozdenım), na nektere viditelne nereaguje (jen prechazı mezivnitrnımi stavy). Nekdy generuje vystup bez prıme vnejsı prıciny. Uvnitr system prechazımezi vnitrnımi stavy, a to bud’ samovolne (pote, co v danem stavu stravil jisty cas), nebona zaklade vnejsı udalosti (udalosti na vstupu). Vystup vzdy zavisı jen na aktualnım stavua je pozorovatleny jako udalost pri samovolnem prechodu systemu do stavu nasledujıcıho.Na obr. 2.2 je zobrazen vstupnı udalostnı segment (x), stavova trajektorie (s), trajektorieuplynuleho casu (e) pro aktualnı stav a vystupnı udalostnı segment (y).

2.5. FORMALISMUS DEVS 9

x1 x2

t1 t2 t3t0

x

s

e

y

t

t

t

t

y1

Obrazek 2.2: Casove segmenty systemu s diskretnımi udalostmi

Souvislost s obecnou definicı systemu Casova zakladna systemu s diskretnımi uda-lostmi je

T = R+0 .

Vstupnı a vystupnı segmenty jsou udalostnı segmenty. Je-li S je mnozina stavu, stavovatrajektorie je po castech konstantnı segment nad S a T . Podle obecne definice systemumusı stav registrovat i dobu setrvavanı ve stavu s ∈ S, proto definujeme Q jako mnozinuuplnych stavu

Q = (s, e)|e ∈ S, e ∈ R+0 .

Prvky Q jsou dvojice, tvorene stavem a casem setrvavanı systemu ve stavu s. Totalnıstavova trajektorie je po castech spojity segment nad Q a T .

2.5.2 Zakladnı model

Zakladnı model je specifikovan algebraickou strukturou

M = (X, S, Y, δint, δext, λ, ta),

kdeX je mnozina vstupnıch udalostı,S je mnozina stavu,Y je mnozina vystupnıch udalostı,δint : S −→ S je internı prechodova funkce,δext : Q×X −→ S je externı prechodova funkce, kde

Q = (s, e) | s ∈ S, 0 ≤ e ≤ ta(s) je mnozina uplnych stavu,e je cas uplynuly od poslednı udalosti,

λ : S −→ Y je vystupnı funkce,


ta : S −→ R+0 ∪ ∞ je funkce posuvu casu.

Interpretace formalismu System je v danem okamziku ve stavu s ∈ S. Nevyskytne-lise zadna externı udalost, system setrva ve stavu s p o dobu ta(s) time. Zvlastnı hodnotouta(s) je symbol ∞ – v takovem prıpade je system pasivnı a planuje setrvat ve stavus navzdy. Dosahne-li uplynuly cas e hodnoty ta(s), vystup λ(s) se objevı na vystupua system zmenı stav na δint(s). Vyskytne-li se externı udalost x ∈ X v case e ≤ ta(s),system zmenı stav na δext(s, e, x). Vystup se generuje pouze v okamziku, kdy e = ta(s). Prikonfliktu internıho a externıho prechodu (majı-li se provest ve stejnem casovem okamziku)se provede pouze externı prechod.

Atomicky model Uvedeny formalismus umoznuje specifikovat jakykoli system s dis-kretnımi udalostmi. Chapeme-li ale system jako hierarchickou strukturu, vyse uvedenadefinice odpovıda specifikaci atomickemu modelu, zakladnı nedelitelne jednotce systemu.Prıklady mohou byt generator, procesor, fronta, binarnı cıtac apod. Systemy slozene zesubsystemu pak specifikujeme jako slozene modely.

2.5.3 Slozeny model

Dalsım konceptem formalismu DEVS je hierarchie – system muze byt dekomponovan dosubsystemu. Subsystemy jsou propojeny a mohou na sebe vzajemne pusobit prostrednic-tvım svych externıch (vstupnıch a vystupnıch) udalostı. Stav slozeneho systemu je pakurcen stavy vsech jeho subsystemu. Slozenım a propojenım systemu vznikne opet system.

Slozeny model je definovan strukturou

Nself = (X, Y, D, Md, Id, Zi,d, select)

kdeX je mnozina vstupnıch udalostı,Y je mnozina vystupnıch udalostı,D je mnozina jmen submodelu,Md |d ∈ D je mnozina submodelu,Id |d ∈ D ∪ self je specifikace propojenı,∀d ∈ D ∪ self : Id ⊆ D ∪ self, d /∈ Id,

Zi,d |i ∈ Id, d ∈ D ∪ self je specifikace prekladu udalostı,Zi,d : X −→ Xd pro i = self ,Zi,d : Yi −→ Y pro d = self ,Zi,d : Yi −→ Xd pro i 6= self a d 6= self ,

select : 2D − −→ D je preferencnı funkce.

Interpretace formalismu Id pro kazdy model d je mozina jmen modelu, jejichz vy-stupy jsou pripojeny na vstup modelu d. Zi,d pro kazdy model i, ktery je pripojen navstup modelu d, specifikuje preklad vystupnı udalosti modelu i na vstupnı udalost modelud. self identifikuje slozeny model N . Funkce select se pouzıva k resenı konfliktu sou-casnych udalostı – vybıra jeden submodel z mnoziny submodelu, ve kterych je aktualneproveditelny internı prechod.

2.5. FORMALISMUS DEVS 11

Uzavrenost vzhledem ke skladanı Mnozina systemu je uzavrena vzhledem k operaciskladanı. Tomu odpovıda skutecnost, ze i slozeny model je model se stavy, vstupy a vystupya muze byt popsan jako zakladnı DEVS. Tato vlastnost byla formalne dokazana a dukazlze najıt napr. v [ZKP00].

2.5.4 Pouzitı portu

Stavove promenne a porty Mnoziny internıch stavu a mnoziny vstupnıch a vystup-nıch udalosti je mozne specifikovat jako strukturovane mnoziny, coz nam umoznı pouzıtlibovolny pocet vstupnıch a vystupnıch portu a libovolny pocet stavovych promennych.Strukturovana mnozina

S = (V, S1 × S2×, ...× Sn)

je definovana mnozinou promennych V , |V | = n, a kartezskym soucinem mnozin hodnotjedotlivych promennych. Takze v definici DEVS s n stavovymi promennymi v1, v2, ...vn, pvstupnımi porty ip1, ip2, ..., ipp a q vystupnımi porty op1, op2, ..., opp muzeme mnozinyX, S a Y zapsat takto:

X = (ip1, ..., ipp, (xip1 , ..., xipp)|xip1 ∈ Xip1 , ..., xip1 ,∈ Xipp),S = (v1, ...vn, (sv1 , ..., svn)|sv1 ∈ Sv1 , ..., svn ,∈ Svn),

Y = (op1, ..., opp, (yop1 , ..., yopq)|yop1 ∈ Yop1 , ..., yopq ,∈ Sopq).

Strukturovana mnozina muze byt specifikovana i jinak, jako mnozina dvojic (jmeno, hodnota),v nasem prıpade:

X = (p, v)|p ∈ InPorts, v ∈ Xp,S = (v, s)|v ∈ StV ariables, s ∈ Sv,

Y = (p, v)|p ∈ OutPorts, v ∈ Yp,

pricemz

InPorts = p|(p, v) ∈ X,StV ariables = v|(v, s) ∈ S,

OutPorts = p|(p, v) ∈ Y .

Alternativnı definice slozeneho modelu Jsou-li X a Y strukturovane mnoziny, spe-cifikaci propojenı lze definovat mezi jednotlivymi porty jednotlivych modelu a funkci pre-kladu udalostı definovat jako identitu. Toto zjednodusenı specifikace slozeneho modeluje snadno prakticky pouzitelne a je skutecne pouzito ve vsech realnych implementacıchformalismu DEVS. Nasleduje formalnı definice toho typu specifikace slozeneho modelu.

Nself = (Xself , Yself , D, Md, EIC, IC, EOC, select),

kdeXself = (p, v)|p ∈ InPortsself , v ∈ Xp,self je mnozina vstupnıch udalostı,Yself = (p, v)|p ∈ OutPortsself , v ∈ Yp,self je mnozina vystupnıch udalostı,D je mnozina jmen submodelu,Md |d ∈ D je mnozina submodelu se vstupy Xd a vystupy Yd,


Xd = (p, v)|p ∈ InPortsd, v ∈ Xp,dYd = (p, v)|p ∈ OutPortsd, v ∈ Yp,d,

EIC = ((self, ipself ), (d, ipd))|ipself ∈ InPortsself , d ∈ D, ipd ∈ InPortsdje mnozina externıch vstupnıch propojenı,

IC = ((a, opa), (b, ipb))|a, b ∈ D, opa ∈ OutPortsa, ipb ∈ InPortsbje mnozina internıch propojenı,

EOC = ((d, opd), (self, opself ))|opself ∈ OutPortsself , d ∈ D, opd ∈ OutPortsdje mnozina externıch vystupnıch propojenı,

select : 2D − −→ D je preferencnı funkcea jsou splnena nasledujıcı omezenı:

∀((a, p), (b, q)) ∈ IC =⇒ a 6= b,∀((a, p), (b, q)) ∈ EIC : Xp,a ⊆ Xq,b,∀((a, p), (b, q)) ∈ IC : Yp,a ⊆ Xq,b,∀((a, p), (b, q)) ∈ EOC : Yp,a ⊆ Yq,b.

2.5.5 Varianty a rozsırenı zakladnı definice DEVS

Existujı ruzne varianty a modifikace DEVS, jako je paralelnı DEVS, celularnı DEVS, sym-bolicky DEVS, fuzzy DEVS, nebo DEVS s dynamickou strukturou. Existuje take moznostmapovanı jinych formalismu do DEVS. Takto lze mapovat napr. konecne automaty, Pe-triho sıte, stavove diagramy, ale i diferencialnı rovnice (prostrednictvım numericke inte-grace). DEVS lze tedy chapat jako spolecny zaklad pro multiparadigmaticke modelovanıa simulaci [ZKP00].

2.6 Hierarchicka simulace DEVS (abstraktnı simulator)

Simulace DEVS je organizovana hierarchicky (viz obr. 2.3). Hierarchie simulatoru odpovıdahierarchii modelu. Kazdy simulator je zodpovedny za simulaci sveho modelu, je podrızennadrazenemu simulatoru a muze mıt podrızene simulatory. Ke komunikaci simulatoru pri

Root Coordinator

Coordinator

Coordinator Simulator

Simulator Simulator

Coupled Model

Coupled Model Atomic Model

Atomic Model Atomic Model

Obrazek 2.3: Mapovanı mezi modely a simulatory

simulaci slouzı zpravy (viz obr. 2.4):

• (i, t) - inicializacnı zpravy posıla nadrazeny simulator podrızenym pri odstartovanısimulace,

2.6. HIERARCHICKA SIMULACE DEVS (ABSTRAKTNI SIMULATOR) 13

• (∗, t) - pokyn nadrazeneho simulatoru podrızenemu k vygenerovanı vystupu a pro-vedenı internıho prechodu planovaneho na cas t,

• (y, t) - vystupnı zpravy posıla podrızeny simulator nadrazenemu (nadrazeny simlu-ator je zopdpovedny za jejich prıpadnou distribuci),

• (x, t) - vstupnı zpravy posıla nadrazeny simulator podrızenym a vynucuje tak prı-padnou distribuci a provedenı externıho prechodu,

• (done, tnext) - podrızeny signalizuje nadrazenemu dokoncenı zpracovanı zpravy (i, t),(∗, t), nebo (x, t) a oznamuje cas provedenı nasledujıcıho internıho prechodu.

Root Coordinator

Coordinator


Simulator

(i, t) (*, t)(done, t)

(x, t)

(y, t)

(*, t)

(done, t)

(i, t) (x, t)

(y, t)(*, t)

(done, t)

(i, t)

Simulator

(x, t)

(y, t)(*, t)

(done, t)

(i, t)(x, t)

(y, t)

(*, t)

(done, t)

(i, t)

Obrazek 2.4: Zpravy pouzıvane pri simulaci DEVS

Kazdy simulator udrzuje informaci o case poslednı udalosti tlast a case nasledujıcı plano-vane udalosti tnext, je schopen provest planovanou udalost a reagovat na vstupnı udalost.Simulator slozeneho modelu (Coordinator) udrzuje tnext pro vsechny submodely, delegujena ne provadenı udalostı a distribuuje udalosti mezi submodely podle jejich propojenı. Nanejvyssı urovni simulaci rıdı korenovy (hlavnı) simulator (Root Coordinator), ktery ini-ciuje provadenı jednotlivych kroku simulace. Dale uvedene algoritmy vychazejı z [ZKP00]a [Van00].

Abstraktnı korenovy simulator Korenovy simulator je zodpovedny za postupne pro-vadenı kroku simulace. Je spusten s parametry podrızeny simulator child, cas zacatku akonce simulace tBEGIN , tEND. Pouzıva promenne t a tnext. Algoritmus:

t := tBEGIN

posli (i, t) podrızenemu simulatoru childpockej na (done, tnext) od podrızeneho simulatoru childt := tnext

dokud t < tEND opakuj:posli (∗, t) podrızenemu simulatoru childpockej na (done, tnext) od podrızeneho simulatoru childt := tnext


Abstraktnı simulator atomickeho modelu

M = (X, S, Y, δint, δext, λ, ta)

pouzıva promenne tlast, tnext, y, uplny stav (s, e) a parent. Algoritmus:

Na zpravu (i, t) od nadrazeneho simulatoru parent reaguj takto:tlast := t− etnext := tlast + ta(s)posli (done, tnext) nadrazenemu simulatoru parent

Na zpravu (∗, t) od nadrazeneho simulatoru parent reaguj takto:y := λ(s)posli (y, t) nadrazenemu simulatoru parents := δint(s)tlast := ttnext := tlast + ta(s)posli (done, tnext) nadrazenemu simulatoru parent

Na zpravu (x, t) od nadrazeneho simulatoru parent reaguj takto:e := t− tlast

s := δext(s, e, x)tlast := ttnext := tlast + ta(s)posli (done, tnext) nadrazenemu simulatoru parent

Abstraktnı simulator (koordinator) slozeneho modelu

Nself = (X, Y, D, Md, Id, Zi,d, select)

pouzıva promenne tlast, tnext, y, eventList, imminent, d, receivers, activeChildren aparent. Algoritmus:

Na zpravu (i, t) od nadrazeneho simulatoru parent reaguj takto:∀d ∈ D :

posli (i, t) simulatoru dactiveChildren := D

Na zpravu (done, tnext) od podrızeneho simulatoru d reaguj takto:eventList := (eventList− (d, )) ∪ (d, tdnext)activeChildren := activeChildren− dJe-li activeChildren = ∅, pak:

tlast := ttnext := mintdnext|d ∈ Dposli (done, tnext) nadrazenemu simulatoru

Na zpravu (∗, t) od nadrazeneho simulatoru parent reaguj takto:imminent := d|(d, tdnext) ∈ eventList, tdnext = td := select(imminent)posli (∗, t) simulatoru dactiveChildren := d

2.7. PRAKTICKE POUZITI FORMALISMU DEVS 15

Na zpravu (y, t) od podrızeneho simulatoru d reaguj takto:Je-li d ∈ Iself a Zd,self (y) 6= ∅, pak:

yself = Zd,self (y)posli (yself , t) nadrazenemu simulatoru parent

receivers := d|d ∈ D, self ∈ Id, Zself,d(x) 6= ∅∀d ∈ receivers :

xd := Zself,d(x)posli (xd, t) simulatoru d

activeChildren := activeChildren ∪ receivers

Na zpravu (x, t) od nadrazeneho simulatoru reaguj takto:receivers := d|d ∈ D, self ∈ Id, Zself,d(x) 6= ∅∀d ∈ receivers :


activeChildren := receivers

Korektnı implementace V korektnı implementaci pri prijetı zpravy (∗, t) vzdy platıt = tnext a pri prijetı zpravy (x, t) vzdy platı tlast ≦ t ≦ tnext. Dukaz korektnı synchronizaceabstraktnıho simulatoru je podan v [ZKP00].

Prerusovanı a klonovanı simulacı Uvedeny abstraktnı simulator pripoustı moznostprerusenı a nasledneho pokracovanı simulace (vcetne moznosti klonovanı a migrace) zapredpokladu, ze mezitım nedojde k manipulaci se strukturou. Pro potreby dynamickeeditace modelu je treba simulator upravit. Tato problematika bude podrobne popsana vkapitole 4.

RT simulace a HIL Uvedeny abstraktnı simulator nenı pripraven na moznost propojenıs realnym okolım. Tato problematika bude diskutovana v kapitole 4.

Paralelnı a distribuovana simulace Simulaci lze paralelizovat a distribuovat. V tomtoprıpade je vhodne pouzıt paralelnı variantu DEVSu, ktera se nepatrne lisı od klasickevarianty. Tato varianta pocıta s moznostı soucasnych udalostı na vstupech modelu a jepopsana v [ZKP00]. Pro dalsı vyklad nenı podstatne, o kterou variantu jde. Proto budepro jednoduchost pouzita varianta klasicka.

2.7 Prakticke pouzitı formalismu DEVS

DEVS byl v dobe sveho vzniku urcen k tomu, aby bylo mozne formalne popsat a praco-vat modely, ktere se pak obvykle implementovaly beznym zpusobem, typicky v udalostneorientovanem simulacnım jazyce Simscript. Lepsı moznostı je ale pouzıt DEVS prımo proimplementaci a odstranit tak nutnost explicitnıho mapovanı formalismu do programova-cıho jazyka. K tomuto ucelu byly vytvoreny podpurne knihovny pro bezne programovacıjazyky, jako je LISP, C, C++, Java, Smalltalk apod.

Existuje rada implementacı DEVS, jako prıklady lze uvest ADEVS (University of Ari-zona), CD++ (Carleton University), DEVS/HLA (ACIMS), DEVSJAVA (ACIMS), GA-LATEA (USB Venezuela), GDEVS (Aix-Marseille III, France), JDEVS (Universite de


Corse - France), PyDEVS (McGill), PowerDEVS (University of Rosario, Argentina), Sim-Beans (University of Linz, Austria), VLE (Universite du Litoral -France), SmallDEVS(Brno University of Technology, Czech Republic), James (University of Rostock, Ger-many).2 V soucasne dobe v prumyslu nejpouzıvanejsı implementacı je DEVSJAVA, kteroupouzıva napr. NASA a DoD (USA).

2.7.1 DEVS a objektova orientace

Nejcastejsı implementace v soucasne dobe existujı pro objektove orientovane jazyky C++a Java. Implementace DEVS v objektove orientovanem jazyce zalozenem na trıdach vedek typickemu zpusobu modelovanı, kde modely jsou vytvareny jako podtrıdy existujıcıchtrıd (modelu). Podtrıda definuje instancnı promenne pro reprezentaci stavu a redefinujemetody, odpovıdajıcı funkcım δext, λ, δint, ta atomickeho modelu, prıpadne specifikuje ko-lekci submodelu (tj. instancı prıslusnych trıd), spolu s relacı propojenı pro slozene modely.V obou prıpadech je inicializacnı metoda zodpovedna za vytvorenı vstupnıch a vystup-nıch portu. Vyuzitı dedicnosti pro specifikaci modelu je vyznamnym prınosem, stejne taki instanciace modelu. Dıky tomu lze udrzovat knihovny znovupouzitelnych modelu.

2.7.2 Prıklady modelu a jejich implementace

Pro ilustraci praktickeho pouzitı formalismu DEVS pro tvorbu simulacnıch modelu budeuveden jednoduchy prıklad, demonstrujıcı prıme mapovanı matematickeho modelu do pro-gramovacıho jazyka. Pro implementaci bude pouzit Smalltalk [GR89] s modelovacım pro-stredım SmallDEVS [Jan06]. V jinych objektove orientovanych jazycıch a prostredıch, jakoje JAVADEVS apod., je princip modelovanı totozny, lisı se jen v pouzitem programovacımjazyku a v nazvech nekterych metod.3 Pro potreby vykladu v tomto textu je Smalltalkvhodnejsı jednak kvuli strucnosti a prehlednosti, jednak proto, ze pro vyklad v kapitole 5bude pouzitı Smalltalku kvuli jeho specifikym vlastnostem prakticky nezbytne.

Prıklad Specifikujme hrace pingpongu:4

PingPongP layer = (X, S, Y, δint, δext, λ, ta, s0),

kdeX = (receive, ball),Y = (send, ball),S = send, receive,δint(send) = receive, δint(receive) = receive,δext(receive, e, (receive, ball)) = send, δext(send, e, x) = send,λ(send) = (send, ball), λ(receive) = ∅,ta(send) = 0.5, ta(receive) =∞.

2Seznam je prevzat z prezentace B.P. Zeiglera na konferenci Mosim08: Modelisation, Optimisation etSimulation des Systmes, March 31-April 2 2008, Paris, France.

3SmallDEVS umonuje pro modelovanı pouzıt krome kasickeho prıstupu k objektove orientaci, zalo-zeneho na trıdach, take jiny, flexibilnejsı prıstup, ktery bude popsan v kapitole 5. Na tomto mıste alezustaneme u klasickeho prıstupu, ktery je zcela konformnı s bezne pouzıvanymi nastroji pro modelovanıa simulaci na bazi formalismu DEVS. Prıklady zde uvedene lze tedy jednoduse adaptovat pro libovolny zalternativnıch nastroju.

4Specifikaci systemu jsme rozsırili o pocatecnı stav s0 ∈ S.


s0 = send.

V praktickych implementacıch formalismu DEVS atomicky model definuje mnozinu vstup-nıch a vystupnıch portu, mnozinu stavovych promennych, funkci posuvu casu, prechodovefunkce (internı a externı), vystupnı funkci a pocatecnı stav. Nasleduje implementace mo-delu PingPongP layer v prostredı SmallDEVS. AtomicDEVS subclass : #PingPongPlayer

instanceVariableNames: ’phase ’

in i t ia l i zesuper in i t ia l i ze .phase←#send.se l f addInputPortNamed: #receive .se l f addOutputPortNamed: #send.

extTransition(phase = #receive) & (( se l f peekFrom: #receive) = #ball ) ifTrue : [ phase←#send ]

intTransitionphase = #send ifTrue : [ phase←#receive ] .

timeAdvancephase = #send ifTrue : [ ↑ 0.5 ] .phase = #receive ifTrue : [ ↑ Float infinity ] .

outputFncphase = #send ifTrue : [ se l f poke: #ball to : #send ] .

Druhy hrac by mel byt v pocatecnım stavu pasivnı, od prvnıho se lisı jen pocatecnımstavem:

InitiallyPassiveP ingPongP layer = (X, S, Y, δint, δext, λ, ta, s0),

kdeX, S, Y, δint, δext, λ, ta jsou definovany stejne jako v modelu PingPongP layer,s0 = receive.

V objektove orientovane implementaci formalismu DEVS muzeme vyuzıt dedicnosti –v modelu InitiallyPassiveP ingPongP layer, dedıcıho difinici modelu PingPongP layer,nove definujeme pouze inicializacnı metodu, ktera nstavuje pocatecnı stav. PingPongPlayer subclass : #InitiallyPassivePingPongPlayer

in i t ia l i zesuper in i t ia l i ze .phase←#receive .

System dvou hracu je specifikovan jako slozeny DEVS

PingPong = (X, Y, D, Md, EIC, IC, EOC, select),


kdeX = Y = ,D = PlayerA, P layerB,Md = PingPongP layerPlayerA, InitiallyPassiveP ingPongP layerPlayerB,EIC = EOC = ,IC = (PlayerA.send, P layerB.receive), (PlayerB.send, P layerA.receive),∀m ∈ 2D − : select(m) = PlayerA.

Specifikace slozeneho modelu v praktickych iplementacıch DEVS obsahuje mnozinu sub-modelu, mnozinu vlastnıch vstupnıch a vystupnıch portu, specifikaci propojenı mezi portyjednotlivych modelu. Nasleduje implementace modelu hry Ping-Pong v prostredı Small-DEVS. CoupledDEVS subclass : #PingPong

in i t ia l i zesuper in i t ia l i ze .se l f addComponents:

#’Player A’ −> PingPongPlayer new.#’Player B’ −> InitiallyPassivePingPongPlayer new..se l f addCouplings : #’Player A’ . #send −> #’Player B’ . #receive.#’Player B’ . #send −> #’Player A’ . #receive..

Hierarchie simulatoru zastresena korenovym simulatorem je vytvorena nasledujıcım kodem– ten soucasne odstartuje simulaci. PingPong new getSimulator simulate : 1.5. Prubeh simulace je zaznamenan jako sekvence udalostı a zmen stavu. Na obrazku 2.5 jeorientacnı textovy zaznam, generovany behem simulace, existuje ale moznost generovatzaznam v XML pro prıpadne dalsı zpracovanı.

Uvedeny prıklad demonstruje pouzitı formalismu DEVS pro vytvorenı modelu a na-sledne simulacnı overenı jeho spravne funkce (analyzou logu lze zıskat potrebne informaceo chovanı systemu). Existuje samozrejme moznost pouzitı modelu na bazi DEVS k jinymucelum, napr. pro stochastickou simulaci. V takovem prıpade je treba prubezne sbırat datao vyuzitı zdroju, delkach front apod. Jinou moznostı je simulace v realnem case, propojenas realnym okolım. K tomu je treba zajistit komunikaci modelu s okolım a synchronizovatsimulaci s realnym casem. Model pak chapeme jako program s realnymi vstupy a vystupy.Vyhodou tohoto zpusobu programovanı je konformita programu s pouzitym formalismem,coz vytvarı prostor pro aplikaci matematickych metod pro analyzu a verifikaci. Moznostsimulace systemu v simulovanem prostredı pak umoznuje dukladne testovanı vyvıjenehosystemu v prubehu vyvoje. Tomuto zpusobu vyvoje systemu rıkame vyvoj zalozeny nasimulaci (simulation-based development). Jeden z moznych prıstupu k takovemu vyuzitısimulacnıho modelovanı bude popsan v kapitole 5.


****************** time: 0.5* Internal Transition: aPingPong/Player A

* New State:phase: #receive

* Output Port Configuration:send: #event

* Next scheduled internal transition at time Infinity* External Transition: aPingPong/Player B

* Input Port Configuration:receive: #event

* New State:phase: #send

* Root DEVS Output Port Configuration:****************** time: 1.0* Internal Transition: aPingPong/Player B



* Next scheduled internal transition at time Infinity* External Transition: aPingPong/Player A



* Root DEVS Output Port Configuration:****************** time: 1.5* Internal Transition: aPingPong/Player A



* Next scheduled internal transition at time Infinity* External Transition: aPingPong/Player B



* Root DEVS Output Port Configuration:

Obrazek 2.5: Zaznam prubehu simulace


Kapitola 3

Systemy s dynamicky se menıcıstrukturou

Systemy, u kterych se predpoklada adaptace a vyvoj, chapeme obecne jako systemy sdynamickou strukturou. Modelovanı a simulace takovych systemu musı nutne zahrnoutfenomeny jako:

• menıcı se vazby mezi komponentami,

• dynamicky vznikajıcı a zanikajıcı komponenty,

• dynamicky se menıcı definice atomu.

Modifikace struktury modelu lze obecne docılit rozsırenım simulacnıho modelovanı o moz-nost vyjadrit reflektivnı vlastnosti systemu. Princip systemove reflexe tkvı v tom, ze sys-tem vidı svoji vlastnı specifikaci a je schopen do nı dynamicky zasahovat. Tyto zasahy jsousystemem bezprostredne reflektovany, tj. majı okamzity vliv na jeho strukturu a chovanı.

Problematikou reflexe v softwarovych systemech se zabyva rada autoru, napr. [Mae87,MMWY92, Paw98, TUN06, LRS01]. V oblasti formalnıch modelu systemu s diskretnımiudalostmi lze uvest vyvıjejıcıcı se Petriho sıte [ABPD96] a ruzne varianty zavedenı struk-turnı dynamiky do formalismu DEVS, jako je DSDEVS [Bar97] a Dynamic DEVS [Uhr01].Zatımco DSDEVS umonuje dynamiku na urovni slozenych modelu a je konkretne imple-mentovan napr. v ADEVS, Dynamic DEVS (ktery bude uveden v nasledujcıcım textu) jedefinovan obecneji – dynamika je mozna i na urovni atomickych modelu. Definice DynamicDEVS zavadı strukturnı prechody, ktere menı nikoliv stav, ale model (princip je na obr.3.1, strukturnı prechody jsou znazorneny teckovane).

Pro vsechny prıstupy, ktere zavadejı strukturnı dynamiku, platı, ze system s menıcı sestrukturou je vzdy specifikovateny jako system staticky. To znamena, ze je simulovatelnyekvivalentnım systemem se statickou strukturou, jehoz stavovy prostor je rozsıren tak, abyzahrnoval vsechny varianty a prechodove funkce zahrnujı specifikaci prechodovych funkcıvsech variant.

3.1 Dynamicky DEVS

Dynamicky DEVS Dynamicky model je struktura [Uhr01]

DynM = (X, Y, m0, M(m0)),

22 KAPITOLA 3. SYSTEMY S DYNAMICKY SE MENICI STRUKTUROU

Obrazek 3.1: Strukturnı prechody [Uhr01]

kdeX je mnozina vstupnıch udalostı,Y je mnozina vystupnıch udalostı,m0 ∈M(m0) je pocatecnı model,M(m0) je nejmensı mnozina se strukturou (S, s0, δint, δext, ρ, λ, ta)|

S je mnozina stavu,s0 ∈ S je pocatecnı stav,δint : S −→ S je internı prechodova funkce,δext : Q×X −→ S je externı prechodova funkce, kde

Q = (s, e) | s ∈ S, 0 ≤ e ≤ ta(s) je mnozina uplnych stavu,ρ : S −→M(m0) je funkce prechodu mezi modely,λ : S −→ Y je vystupnı funkce,ta : S −→ R+

0 ∪ ∞ je funkce posuvu casu,splnujıcı podmınku∀n ∈M(m0) : (∃m ∈M(m0) : n = ρ(sm), sm ∈ Sm) ∨ n = m0.

Dynamicky slozeny DEVS Dynamicky slozeny model je struktura [Uhr01]

DynN = (X, Y, n0, N(n0)),

kdeX je mnozina vstupnıch udalostı,Y je mnozina vystupnıch udalostı,m0 ∈M(m0) je pocatecnı model (pocatecnı konfigurace),N(n0) je nejmensı mnozina se strukturou (D, ρN , DynMd, Id, Zi,d, select)|

D je mnozina jmen submodelu,ρN : SSS −→M(m0) je funkce prechodu mezi modely, kde

SSS = ×d∈D,m∈DynMdSm,

DynMd |d ∈ D je mnozina submodelu,Id |d ∈ D ∪ self je specifikace propojenı,∀d ∈ D ∪ self : Id ⊆ D ∪ self, d /∈ Id,

Zi,d |i ∈ Id, d ∈ D ∪ self je specifikace prekladu udalostı,Zi,d : X −→ Xd pro i = self ,Zi,d : Yi −→ Y pro d = self ,Zi,d : Yi −→ Xd pro i 6= self a d 6= self ,

3.2. ABSTRAKTNI SIMULATOR PRO DYNAMICKY DEVS 23

select : 2D − −→ D je preferencnı funkce,splnujıcı podmınku∀n ∈ N(m0) : (∃m ∈ N(m0) : n = ρN (sssm), sssm ∈ SSSm) ∨ n = n0.

3.2 Abstraktnı simulator pro dynamicky DEVS

Abstraktnı korenovy simulator Promenne: Podrızeny simulator child, cas zacatkua konce simulace tBEGIN , tEND, aktualnı cas t a cas nasledujıcı planovane udalosti tnext.Algoritmus:

t := tBEGIN

posli (i, t) podrızenemu simulatoru childpockej na (done, s, tnext) od podrızeneho simulatoru childt := tnext

dokud t < tEND opakuj:posli (∗, t) podrızenemu simulatoru childpockej na (done, s, tnext) od podrızeneho simulatoru childt := tnext

Abstraktnı simulator atomickeho modelu Promnne: Aktualnı model m, cas po-slednı udalosti tlast, cas nasledujıcı udalosti tnext, vystup y, uplny stav (sm, e) a nadrazenysimulator parent. Algoritmus:

Na zpravu (i, t) od nadrazeneho simulatoru parent reaguj takto:tlast := t− etnext := tlast + ta(sm)posli (done, sm, tnext) nadrazenemu simulatoru parent

Na zpravu (∗, t) od nadrazeneho simulatoru parent reaguj takto:y := λ(sm)posli (y, t) nadrazenemu simulatoru parentsm := δint(sm)m := ρ(sm)tlast := ttnext := tlast + ta(sm)posli (done, sm, tnext) nadrazenemu simulatoru parent

Na zpravu (x, t) od nadrazeneho simulatoru parent reaguj takto:e := t− tlast

sm := δext(sm, e, x)m := ρ(sm)tlast := ttnext := tlast + ta(sm)posli (done, sm, tnext) nadrazenemu simulatoru parent

Abstraktnı simulator (koordinator) slozeneho modelu Promenne: Aktualnı mo-del n, stav sn, cas poslednı udalosti tlast, cas nasledujıcı udalosti tnext, vystup y, seznam


nasledujıcıch udalostı v submodelech eventList, mnozina submodelu s udalostmi plano-vaymi na aktualnı cas imminent, vybrany submodel d, seznam submodelu pro predanıvstupu receivers, nadrazeny simulator parent. Algoritmus:

Na zpravu (i, t) od nadrazeneho simulatoru parent reaguj takto:∀d ∈ D :

posli (i, t) simulatoru dpockej na (done, s, tnext) od vsech receiversaktualizuj sn

aktualizuj eventListtlast := ttnext := mintdnext|d ∈ Dposli (done, sn, tnext) nadrazenemu simulatoru

Na zpravu (∗, t) od nadrazeneho simulatoru parent reaguj takto:imminent := d|(d, tdnext) ∈ eventList, tdnext = td := select(imminent)posli (∗, t) simulatoru dpockej na (y, t) od simulatoru dje-li d ∈ Iself a Zd,self (y) 6= ∅, pak:

yself = Zd,self (y)posli (yself , t) nadrazenemu simulatoru parent

receivers := d|d ∈ D, self ∈ Id, Zself,d(x) 6= ∅∀d ∈ receivers :


pockej na (done, s, tnext) od vsech receivers aktualizuj sn

Dold := Dn := ρn(sn)∀d ∈ D −Dold : posli (init, t) simulatoru dpockej na (done, s, tnext) od vsech d ∈ D −Dold

aktualizuj sn

aktualizuj eventListtlast := ttnext := mintdnext|d ∈ Dposli (done, sn, tnext) nadrazenemu simulatoru

Na zpravu (x, t) od nadrazeneho simulatoru reaguj takto:receivers := d|d ∈ D, self ∈ Id, Zself,d(x) 6= ∅∀d ∈ receivers :


pockej na (done, s, tnext) od vsech receivers aktualizuj sn

Dold := Dn := ρn(sn)∀d ∈ D −Dold : posli (init, t) simulatoru dpockej na (done, s, tnext) od vsech d ∈ D −Dold

aktualizuj sn

aktualizuj eventList

3.3. APLIKACE 25

tlast := ttnext := mintdnext|d ∈ Dposli (done, sn, tnext) nadrazenemu simulatoru

Korektnı implementace V korektnı implementaci pri prijetı zpravy (∗, t) vzdy platıt = tnext a pri prijetı zpravy (x, t) vzdy platı tlast ≦ t ≦ tnext.

3.3 Aplikace

Dynamicky DEVS (DynDEVS) byl pouzit jako formalnı zaklad systemu James [Uhr01] promodelovanı a simulaci agentnıch systemu. Formalnı model DynDEVS je koncipovan jakouzavreny, neresı problematiku klonovanı a editaci modelu asynchronnımi zasahy z vnejsku.Umoznuje vsak krome vzniku a zaniku modelu take jejich migraci ramci systemu, coz jepro multiagentnı systemy typicke. Vzhledem k tomu, ze migraci provadı model, ktery sechce presunout, je presun soucasti jeho vlastnıho internıho nebo externıho prechodu. Vokamziku migrace je tedy v definovanem stavu, pricemz e = 0. V definici dynamickehoDEVS tak nenı treba pracovat s uplnym stavem (s, e) a lze vystacit jen s tım, ze inicia-lizace nove pridavanych modelu spravne nastavı cas poslednı a planovane udalosti. Ale vprıpade, ze celou simulaci chapeme jako otevreny system se vstupy a vystupy (prıpadnetake s vlastnım, nezavislym casem),1 musıme se zabyvat asynchronnımi zasahy z vnej-sıho sveta. Pak jiz nevystacıme se samotnou reflexı, jako v prıpade DynDEVS, ale musımezprıstupnit reflektivnı rozhranı vnejsımu systemu. Pritom je treba zajistit korektnı chovanıpri klonovanı modelu a editacnıch operacıch v libovolnem okamziku. Touto problematikouse zabyva kapitola 4.

1Otevrene chapanı simulace s moznostı neomezene klonovat a editovat modely je nezbytne pro interak-tivnı evolucnı vyvoj a udrzbu nepretrzite bezıcıch systemu.


Kapitola 4

Otevrena abstraktnı architekturapro simulaci vyvıjejıcıch sesystemu

Kapitola definuje abstraktnı architekturu univerzalnıho systemu pro simulaci vyvıjejıcıchse systemu. Nejprve jsou vymezeny pozadovane vlastnosti, pote je na zaklade jejich analyzyvytvoren navrh vhodne architektury a diskutovany moznosti pouzitı.

4.1 Vymezenı pozadovanych vlastnostı

Systemy, kterymi se hodlame nadale zabyvat a pro ktere mame v umyslu definovat vhodnousimulacnı architekturu, lze charakterizovat jako

• optimalizujıcı, ucıcı se, adaptivnı systemy,

• otevrene, dynamicky zkoumatelne a dynamicky editovatelne systemy,

• reflektivnı systemy.

Vzhledem k predpokladanemu zpusobu pouzitı simulace v ramci navrhu, vyvoje a udrzbysystemu mezi hlavnı pozadavky na podpurne nastroje patrı

• simulace v realnem case, propojenı simulace s okolnı realitou,

• klonovanı a editace modelu v prubehu simulace,

• multisimulace – systemy simulacı, simulace simulacı,

V nasledujıcım textu budou jednotlive pozadavky podrobne analyzovany a bude z nichodvozen navrh otevrene architektury pro modelovanı a simulaci vyvıjejıcıch se systemu.

4.2 Simulace v realnem case, propojenı s realnym okolım

Realny cas Pri simulaci modelu v realnem case plyne cas modelu stejne rychle jako casrealny. Otazkou zustava konkretnı hodnota casoveho udaje, resp. mapovanı mezi hodnotousvetoveho casu a casu modelu. Lze rozlisit dva prıpady:

28 KAPITOLA 4. OTEVRENA ABSTRAKTNI ARCHITEKTURA

Lokalnı realny cas. Tok casu pri simulaci v realnem case muze byt chapan jako realnycas behu modelu. V takovem prıpade hodnota casu v danem okamziku udava realnoudobu, po jakou model od sveho startu bezel. Je-li simulace prerusena, realny cas behumodelu zustava konstantnı, je take pozastaven. Po opetovnem spustenı hodnota casunarusta plynule od hodnoty casu v okamziku prerusenı. Toto chapanı realneho casumodelu je souladu s definicı systemu – jde o cas, v kterem system existuje. Zastavenısimulace znamena, ze system v dobe, kdy je simulace zastavena, neexistuje a jehoexistence pokracuje az po opetovnem spustenı simulace. Zastavovanı a spoustenısimulace jsou operace, ktere model nevnıma a pokud mu metasystem (okolnı realita)tuto informaci neposkytne, zije model ve svem case, aniz by videl nejake prerusenı.

Globalnı realny cas. Tok tohoto casoveho udaje nelze zadnym zpusobem ovlivnit, natozzastavit. Ma-li model pracovat s globalnım realnym casem, pozastavenı simulacezpusobı problem – simulace se opozdı oproti realnemu casu. Po opetovnem spustenıse se zpozdenım provedou akce, planovane na dobu, kdy byla simulace prerusena.Hodnota zpozdenı (latence) muze byt v nekterych aplikacıch kriticka. Nedodrzenıcasoveho ramce (timeoutu) pro provedneı akce je chapano jako selhanı a musı bytsystemem detekovano. To vyzaduje dodat casova omezenı do modelu a tato omezenıv prubehu simulace hlıdat.

V nekterych prıpadech je vyhodne pouzıt proporcionalnı cas. Rychlost toku modelovehocasu vzhlem k ralnemu casu je pak dana koeficientem, tzv. RT-fakorem. Simulace je tedyna realnem case zavisla, ale bezı bud’ zrychlene, nebo zpomalene.

Simulace v realnem case Simulaci je mozne synchronizovat s realnym casem a propo-jit simulovane a realne entity do jednoho celku.1 Zakladnım predpokladem je dostatecnerychle provadenı jednotlivych kroku simulace. Pak stacı po kazdem kroku pockat na hod-notu realneho casu rovnou casu nasledujıcı udalosti v simulacnım case a pak provest dalsıkrok. Problemem, ktery je treba resit v prıpade distribuovane RT simulace, je synchroni-zace hodin na vsech uzlech. Moznym resenım je jeden ze simulacnıch uzlu je prohlasit zareferencnı, ostatnı se pak podle neho synchronizujı.

Vstupne-vystupnı aktivity Interakce simulatoru s vnejsım svetem je realizovana svyuzitım prostredku operacnıho systemu. Z hlediska modelu se interakce s realnym okolımresı specialnımi komponentami (modely), doplnenymi o moznost posılat data do vnejsıhoprostredı a prijımat asynchronne prichazejıcı data z vnejsıho prostredı (viz napr. [Hu04]).V atomickem modelu, reprezentujıcım rozhranı na vnejsı svet, bezı tzv. vstupne-vystupnıaktivita. Jde o proces (nebo mnozinu procesu) operacnıho systemu,2 realizujıcı vystupy acekajıcı na mozne vstupy. Z procesu vstupne-vystupnı aktivity atomickeho modelu muzebyt kdykoli asynchronne (tj. nezavisle na procesu simulace) aktualizovan stav atomickehomodelu. Pri kazde takove zmene musı proces vstupne-vystupnı aktivity okamzite aktuali-zovat tnext := clock hodnotou aktualnıho realneho casu a signalizovat tzv. stavovou udalost

1Toto dava smysl napr. v nekterych fazıch vyvoje rıdicıch systemu – po otestovanı modelu rıdicıhosystemu (presneji rıdicıho systemu realizovaneho jako model) v simulovanem prostredı (obsahujıcım simu-lovany rızeny system) se simulovane prostredı nahradı rozhranım na realne okolı (a realny rızeny system).

2Pojem operacnı system zde zahrnuje jakekoliv vypocetnı prostredı, ve kterem simulator bezı, tj. na-prıklad JVM, Smalltalk, stejne tak, jako napr. UNIX apod.

4.2. SIMULACE V REALNEM CASE, PROPOJENI S REALNYM OKOLIM 29

zaslanım zpravy (se, tnext) nadrazenemu simulatoru. Simulator slozeneho modelu si v re-akci na tuto zpravu aktualizuje tnext pro podrızenou komponentu v seznamu eventList,aktualizuje si vlastnı tnext a posle zpravu (se, tnext) svemu nadrazenemu simulatoru. Kore-novy simulator si v reakci na (se, tnext) aktualizuje tnext, takze v nasledujıcım kroku muzeprıslusny atomicky model na stavovou udalost zareagovat internım prechodem. Reakcesimulatoru na zpravy prichazejıcı z ruznych procesu (z procesu korenoveho simulatoru a zprocesu aktivit v atomech) musı byt kvuli prıstupu ke sdalenym promennym simulatorusynchronizovany.

Abstraktnı simulator pro beh v realnem case Predpokladejme, ze clock je pseu-dopromenna,3 obsahujıcı v kazdem okamziku aktualnı hodnotu realneho casu. Na zacatkusimulace je treba synchronizovat cas modelu a hodiny realneho casu (clock) – lze nastavitbud’ tBEGIN := clock, nebo clock := tBEGIN . V prvnım prıpade pracujeme s globalnımcasem, v druhem prıpade pracujeme casem realneho behu modelu (hodnota clock udavarealnou dobu behu od spustenı). Algoritmus korenoveho simulatoru pro simulaci v realnemcase vypada takto:

synchronizuj clock a tBEGIN

t := tBEGIN


dokud clock < tEND opakuj:cekej na clock = t nebo na prerusenı zpravou (se, tnext)proved’ synchronizovane:4

t := minclock, tnext, tposli (∗, t) podrızenemu simulatoru childpockej na (done, tnext) od podrızeneho simulatoru childt := tnext

Na zpravu (se, tnext) reaguj synchronizovane takto:t := tnext

Simulator atomickeho modelu z kap. 2 doplnıme takto:

Na zpravu (se, tnext) reaguj synchronizovane takto:t := tnext

Posli zpravu (se, tnext) nadrazenemu simulatoru

Na ostatnı zpravy reaguj stejne jako v kap. 2, ale synchronizovane.

Simulator slozeneho modelu z kap. 2 doplnıme takto:

Na zpravu (se, tnext) od podrızeneho simulatoru d reaguj synchronizovane takto:eventList := (eventList− (d, )) ∪ (d, tdnext)t := tnext

3Pseudopromenna je promenna, do ktere v domenove urovni nelze priradit hodnotu, tj. je pro model kdispozici pouze pro ctenı.

4Pod pojmem synchronizovane provedenı mame na mysli kritickou sekci hlıdanou semaforem pro prıstupk promennym simulatoru.


Posli zpravu (se, tnext) nadrazenemu simulatoruNa ostatnı zpravy reaguj stejne jako v kap. 2, ale synchronizovane.

Aktivace a deaktivace vstupne-vystupnıch aktivit Aktivity atomickych modeluse startujı v okamziku spustenı simulace. Pri zastavenı simulace by mely byt ukonceny.Toto je vyznamny pozadavek zejmena v situaci, kdy dovolıme editaci modelu – pro takovezasahy se simulace prechodne zastavı a po provedenı operace se znovu spustı. Kopırovanı,serializace apod. jsou bezpecne jen tehdy, kdyz model neobsahuje zadne bezıcı procesy.

Toto lze realizovat tak, ze ke spustenı vstupne-vystupnıch aktivit atomickeho modeludojde v reakci na zpravu (i, t) a zastavenı aktivit se provede v reakci na zpravu (sync, t),5

kterou zavedeme v nasledujıcı sekci pro potreby klonovanı modelu. Korenovy simulator jepak treba upravit tak, aby pri kazdem startu a zastavenı posılal podrızenemu simulatoruzpravy (i, t) a (sync, t).

Rozsırena definice atomickeho modelu Pro uplnost uvedeme jeste rozsırenou defi-nici atomickeho modelu, ktery je urcem pro simulaci v realnem case a umoznı dynamickeklonovanı a editaci (jak bude ukazano dale). Atomicky model se stavem a vstupne-vystupnıaktivitou je specifikovan algebraickou strukturou

M = (X, S, Y, δint, δext, λ, ta, s0, (s, e), α),

kde(X, S, Y, δint, δext, λ, ta) je DEVS,s0 ∈ S je pocatecnı stav,(s, e) ∈ Q je aktualnı totalnı stav,α je vstupne vystupnı aktivita.

Vstupne-vystupnı aktivita α bezı v realnem case a nezavisle na simulaci ovlivnuje stavs ∈ S. Pri kazde modifikaci stavu s ∈ S oznamuje simulator nadrazenemu simulatorustavovou udalost (se, t) s hodnotou aktualnıho realneho casu. Aktivita α rozumı zpravam(suspendActivity) a (resumeActivity).

Rozsırena definice slozeneho modelu Slozeny model se stavem je definovan libovol-nou ze struktur6

N = (X, Y, D, Md, Id, Zi,d, select),N = (X, Y, D, Md, EIC, IC, EOC, select),

kdeX, Y , D, Id, Zi,d, select, EIC, EOC, IC

jsou definovany stejne jako v klasicke definici (viz kap. 2),Md |d ∈ D je mnozina submodelu, pricemz submodelem je

bud’ atomicky model se stavem a vstupne-vystupnı aktivitou,nebo slozeny model se stavem.

5V simulacnım prostredı SmallDEVS (viz kap. 5) je zastavovanı a spoustnı vstupne-vystupnıch akti-vit implementovano metodami atomickeho modelu prepareToStop a prepareToStart. Tyto metody jsouzdedene jako prazdne a v kazdem modelu, ktery implementuje rozhranı na realitu musı byt adekvatneimplementovany.

6Jejich souvislost byla vysvetlena v kap. 2.

4.3. KLONOVANI A MIGRACE SYSTEMU A SIMULACI 31

4.3 Klonovanı a migrace systemu a simulacı

DynDEVS (viz kap. 3, [Uhr01]) resı problematiku sebemodifikace modelu, kdy ke zmenemodelu dochazı v ramci planovanych udalostı v prubehu simulace. Neresı ani problematikuklonovanı, ani vazbu na vnejsı prostredı, a tedy ani asynchronnı editacnı zasahy do modeluz vnejsıho prostredı, vcetne ovladanı simulatoru. Prave tuto problematiku nynı popısemea rozsırıme abstraktnı simulator DEVS tak, aby takove zasahy umoznil.

Kontinuace a DEVS Kontinuace je objekt, reprezentujıcı pokracovanı vypoctu. Je tosnımek, vytvoreny v libovolnem okamziku z bezıcıho procesu. S kontinuacı se pracuje jakos daty – lze ji ulozit, prenest jinam, kopırovat apod. Kontinuace umoznujı implemento-vat multitasking, klonovanı a migraci procesu, navraty v case, prohledavanı stavovehoprostoru.

Definice systemu i definice DEVS odpovıdajı tomuto konceptu – system s aktualnımstavem obsahuje veskerou potrebnou informaci k provedenı simulace, tj. ke generovanıstavove trajektorie, tj. ke zjistenı budoucıho chovanı.

Dynamicke klonovanı a migrace V prıpade systemu s diskretnımi udalostmi je stavmodelu v libovolnem okamziku urcen uplnym stavem (s, e). Dıky uzavrenosti mnozinysystemu vzhledem ke skladanı pro kazdy slozeny system vzdy existuje ekvivalentnı zakladnısystem s uplnym stavem (s, e). Pritom s kazdym podsystemem lze nakladat stejne jakose slozenym systemem. K tomu, aby bylo mozne kdykoliv porıdit snımek (klon) systemunebo jeho casti, je treba vhodne doplnit abstraktnı simulator. Pred kazdym klonovanım ajinymi operacemi nad bezıcı simulacı je treba formalne aktualizovat uplny stav modelu aod tohoto stavu pak po provedenı operace dal pokracovat.

Vzhledem k tomu, ze system je definovan nezavisle na kontextu7, je mozne bez pro-blemu nechat klon systemu dal existovat v jinem kontextu, nez v jakem bezel original. Jetak mozne realizovat migraci komponent mezi subsystemy v ramci jedne simulace i meziruznymi simulacemi.8

Uprava abstraktnıho simulatoru pro potreby dynamicke editace modelu – syn-chronizace simulatoru Abstraktnı simulator DEVS z kapitoly 2 implicitne pripoustımoznost zastavovanı a klonovanı cele simulace – simulatory si potrebnou informaci pama-tujı a po okopırovanı simulace plynule pokracuje. Problem nastava v prıpade strukturnıeditace modelu, t.j. pri manipulaci s jednotlivymi komponentami ve smyslu klonovanı, od-stranovanı a vkladanı. Po takovych operacıch je treba provest korektnı inicializaci vsechkomponent drıve, nez nechame simulaci pokracovat.

Inicializace se na zacatku pokracovanı simulace musı vzdy provest, aby byla aktualizo-vana hodnota tlast a tnext ve vsech komponentach (po prıpadne editaci struktury se mohoutyto hodnoty stat neaktualnımi) a aby nadrazeny simulator zıskal korektnı informaci o casenasledujıcı udalosti.

7System nevı o hierarchicky nadrazenem systemu ani o systemech, s nimiz je propojen. Na druhe strane,slozeny system zna vsechny sve komponenty i jejich propojenı.

8Toto je v prıpade jineho paradigmatu, jako je napr. objektova orientace, problem – kontext objektu jedan vsemi dostupnymi objekty. Vymenit kontext v prubehu vypoctu pak nenı tak jednoduche, jako je tomuv prıpade formalismu DEVS. Obe paradigmata vsak lze vhodne kombinovat – objekty lze bez problemupouzıt uvnitr komponent DEVS a migraci omezit na komponenty DEVS.


Simulator dynamickeho DEVS [Uhr01] vzdy inicializuje pridavane subsystemy. V na-sem prıpade ale pocıtame se vznikem novych subsystemu klonovanım s naslednou editacı,pricemz k naklonovanı systemu muze dojıt asynchronne, v libovolnem okamziku. Protomusıme resit korektnı vytvorenı klonu tak, aby jeho nasledna inicializace v novem kon-textu probehla spravne a aby klon mohl plynule pokracovat v existenci.

Simulator atomickeho modelu hodnotu e casu straveneho ve stavu s standardne aktua-lizuje pri zpracovanı zpravy (x, t) a tato hodnota je pouzita pouze pro vypocet δext(s, e, x).Pro nepretrzity beh simulace je to v poradku, ale chceme-li simulaci prerusovat a mani-pulovat s jejımi kontinuacemi (ve smyslu klonovanı, migrace, zpetneho navracenı apod.),musıme tuto hodnotu aktualizovat v okamziku prerusenı. Zavedeme proto novou zpravu(sync, t).9 Simulator na (sync, t) reaguje aktualizacı hodnoty uplynuleho casu e. Prıstızprava (i, t) po opetovnem odstartovanı simulace pak spravne synchronizuje pokracovanısimulace.

Vazba simulatoru na vnejsı prostredı, simulator jako system Simulator danehomodelu chapeme opet jako system se vstupy a vystupy. Vstupy jsou udalosti (start),(stop), (reset), (endT ime, t) a udalosti predstavujıcı pozadavky na editacnı operace. Tybudou popsany v sekci 4.4. Sekvence vystupnıch udalostı nese informaci o stavovych trajek-toriıch a udalostnıch segmentech vsech submodelu, vcene zmen stavu samotneho simula-toru (spusten, zastaven apod.). Jde o udalosti (intTr, t, M, y, s, s′), (extTr, t, M, x, e, s, s′),(simulationStarted, t) a (simulationStopped, t). Na editacnı a in(tro)spekcnı operace sys-tem reaguje informacı o strukture a aktualnım stavu modelu, ktereho se operace tyka, tj.(model, M) kde M je model se stavem (viz sekce 4.2).

Simulator

ModelCommand Output

(start)(stop)(reset)(doSteps, n)(endTime, t)(inject, x)(editOp, object)

(intTr, t, M, y, s, s’, tn)(extTr, t, M, x, (s, e), s’, tn)(simulationStarted, t)(simulationStopped, t)(model, M)

X Y

S

Obrazek 4.1: Simulator jako system

Rozsırenı simulatoru atomickeho modelu Abstraktnı simulator atomickeho modeludoplnıme o reakci na zpravu (sync, t). Kvuli prıme souvislosti uvedeme i reakci na zpravu(i, t), reakce na ostatnı zpravy zustavajı stejne jako v kap. 2, jsou jen doplneny o generovanıudalostı odpovıdajıcı zmenam stavu modelu (intTr, t, M, y, s, s′) a (extTr, t, M, x, e, s, s′)do vnejsıho prostredı.

Na zpravu (reset) od nadrazeneho simulatoru parent reaguj takto:s := s0

e := 0tlast := 0tnext :=∞posli (done, tnext) nadrazenemu simulatoru parent

9Stejnou zpravu jsme jiz pouzili v predch. sekci k jinemu ucelu, a sice k zastavenı vstupne-vystupnıaktivity. Oba duvody k jejımu zavedenı jsou nezavisle a muze proto plnit oba ucely soucasne.

4.3. KLONOVANI A MIGRACE SYSTEMU A SIMULACI 33

Na zpravu (i, t) od nadrazeneho simulatoru parent reaguj takto:tlast := t− etnext := tlast + ta(s)posli (resumeActivity) vstupne-vystupnı aktivite αposli (done, tnext) nadrazenemu simulatoru parent

Na zpravu (sync, t) od nadrazeneho simulatoru parent reaguj takto:posli (suspendActivity) vstupne-vystupnı aktivite αe := t− tlast

posli (done, tnext) nadrazenemu simulatoru parent

Rozsırenı simulatoru slozeneho modelu Abstraktnı simulator slozeneho modelu do-plnıme o reakci na zpravu (sync, t). Kvuli prıme souvislosti uvedeme i reakce na zpravy(i, t) a (done, t), reakce na ostatnı zpravy zustavajı stejne jako v kap. 2.

Na zpravu (reset) od nadrazeneho simulatoru parent reaguj takto:∀d ∈ D :

posli (reset) simulatoru dactiveChildren := D

Na zpravu (i, t) od nadrazeneho simulatoru parent reaguj takto (jako v kap. 2):∀d ∈ D :

posli (i, t) simulatoru dactiveChildren := D

Na zpravu (sync, t) od nadrazeneho simulatoru parent reaguj takto:∀d ∈ D :

posli (sync, t) simulatoru dactiveChildren := D

Na zpravu (done, tnext) od podrızeneho simulatoru d reaguj takto (jako v kap. 2):eventList := (eventList− (d, )) ∪ (d, tdnext)activeChildren := activeChildren− dJe-li activeChildren = ∅, pak:

Je-li poslednı zprava od nadrazeneho simulatoru (i, t),pak tlast := maxtdlast|d ∈ D

Je-li poslednı zprava od nadrazeneho simulatoru (∗, t), nebo (x, t),pak tlast := t

tnext := mintdnext|d ∈ Dposli (done, tnext) nadrazenemu simulatoru

Rozsırenı korenoveho simulatoru (ovladanı simulace) Korenovy simulator re-aguje na 4 zpravy z vnejsıho prostredı, slouzıcı k ovladanı simulace: (reset), (start),(stop), (endT ime, te). Do vnejsıho prostredı posıla metaudalosti (simulationStarted, t),(simulationStopped, t). Algoritmus:

t := 0tEND :=∞Na zpravu (start) reaguj takto:


Jestlize p = nil, pakp := novy proces:


te := tEND

generuj metaudalost (simulationStarted, t)dokud t < te opakuj:

posli (∗, t) podrızenemu simulatoru childpockej na (done, tnext) od podrızeneho simulatoru childt := tnext

posli (sync, t) podrzenemu simulatoru childpockej na (done, tnext) od podrızeneho simulatoru childgeneruj metaudalost (simulationStopped, t)p := nil

Na zpravu (stop) reaguj takto:Jestlize t >= te a p = nil, generuj metaudalost (simulationStopped, t)te := t

Na zpravu (reset) reaguj takto:posli (reset) podrızenemu simulatoru childpockej na (done, ) od podrızeneho simulatoru childt := 0te := 0

Na zpravu (endT ime, te) reaguj takto:tEND := te := te

Simulace v realnem case Upravu vyse uvedeneho simulatoru pro beh v realnem casesi na zaklade jiz uvedenych informacı laskavy ctenar provede sam.

4.4 Ctenı a modifikace modelu, dynamicke aplikacnı roz-hranı simulatoru

V predchozı sekci byl popsan simulator, reagujıcı na operace pro ovladanı simulace apripoustejıcı pri pozastavene simulaci provadet klonovanı, migraci a editaci modelu. Nynıdoplnıme navrh dynamickeho aplikacnıho rozhranı simulatoru, ktere umoznı

• dynamickou inspekci modelu a stavu simulace,

• dynamickou zmenu vazeb mezi modely,modelsestavem

• dynamicke vytvarenı a rusenı modelu,

• dynamickou editaci definice atomu,

• dynamicke vytvarenı, editace a rusenı pomocnych objektu.

4.4. CTENI A MODIFIKACE MODELU 35

Objekty Objekty, nad kterymi jsou dynamicky (za behu) k dispozici editacnı operace,jsou prvky mnozin

• SIMULATIONS – mnozina simulacı,

• MODELS – mnozina modelu,

• INPORTS – mnozina vstupnıch portu modelu,

• OUTPORTS – mnozina vystupnıch portu modelu,

• SLOTS – mnozina stavovych promennych modelu s asociovanymi slozkami aktual-nıho stavu modelu,10

• METHODS – mnozina funkcı, specifikujıcıch atomicky model,

• COUPLINGS – mnozina propojenı, specifikujıcıch slozeny model.

Tyto mnoziny jsou hierarchicky organizovany. Na obr. 4.2 je ukazka hierarchie objektuexistujıcıch na pocatku simulace modelu PingPong z kapitoly 2.11 Nedochazı-li k zasahumdo simulace z vnejsku, v prubehu simulace se menı pouze obsah slotu atomickych modelu.

Operace Nad objektem o, resp. nad mnozinou objektu O zavedeme tyto operace:12

• NEW – vytvorı novy objekt o (parametrem je jmeno a specifikace objektu) a pridaho do mnoziny O,

• COPY – zkopıruje objekt o do promenne PASTEBUFFER,

• PASTE – vlozı kopii objektu ulozeneho v promenne PASTEBUFFER do mnozinyO,

• DELETE – odstranı objekt o z mnoziny O,

• CUT – odstranı objekt o z mnoziny O a umıstı ho do promenne PASTEBUFFER,

• RENAME – prejmenuje objekt o (parametrem je nove jmeno) v mnozine O,

• SAV E – ulozı objekt o do vstupne vystupnı promenne IO,13

• LOAD – vlozı objekt ze vstupne vystupnı promenne IO do mnoziny O,14

• EDIT – modifikuje specifikaci objektu o (parametrem je nova specifikace),

• makrooperace slozene z uvedenych operacı.10V objektove orientovanem prostredı zalozenem na prototypovych objektech (viz kap. 5) pracujeme

jeste se specialnımi sloty DELEGATES.11Puvodnı model v kap. 2 je vytvoren z instancı predem pripravenych trıd, a jeho implementace obshuje

i inicializacnı metody, ktere v prıpade, ze se zamerıme jen na objekty simulace bez ohledu na zpusobvytvorenı, nemajı pro specifikaci modelu zadny vyznam, zname-li aktualnı stav. Trıdy a inicializace instancıjsou implementacnı detaily vynucene konkretnım prostredım a nemajı pro simulaci vyznam. Ani definiceDEVS s nicım takovym nepocıta.

12Lze potencialne definovat i jinou sadu operacı, kterou lze docılit tehoz efektu.13Prakticky je objekt ulozen v textove podobe.14Prakticky probehne rekonstrukce objektu z textove reprezentace.


INPORTS

OUTPORTS

MODELS

COUPLINGS

#’Player A’.#send->#’Player B’.#receive.#’Player B’.#send->#’Player A’.#receive.SLOTS

phase

#send

OUTPORTS

#send

INPORTS

#receive

METHODS

extTransition (phase = #receive) & ((self peekFrom: #receive) = #ball) ifTrue: [ phase := #send ]

intTransition phase = #send ifTrue: [ phase := #receive ].

timeAdvance phase = #send ifTrue: [ ^ 0.5 ]. phase = #receive ifTrue: [ ^ Float infinity ].

outputFnc phase = #send ifTrue: [ self poke: #ball to: #send ]

Player A (AtomicDEVS)

SLOTS

phase

#send

OUTPORTS

#send

INPORTS

#receive

METHODS

extTransition (phase = #receive) & ((self peekFrom: #receive) = #ball) ifTrue: [ phase := #send ]

intTransition phase = #send ifTrue: [ phase := #receive ].

timeAdvance phase = #send ifTrue: [ ^ 0.5 ]. phase = #receive ifTrue: [ ^ Float infinity ].

outputFnc phase = #send ifTrue: [ self poke: #ball to: #send ]

Player B (AtomiDEVS)

Ping Pong (CoupleDEVS)

MODEL

Ping Pong (Simulation)

SIMULATIONS

Obrazek 4.2: Hierarchie objektu – snımek stavu simulace PingPong

Uvedene operace lze bez omezenı aplikovat v libovolnem okamziku na libovolne objekty.Jako prıklad lze uvest vsechny objekty na obr. 4.2. Pokud vysledkem operace je funkcnımodel, simulace muze pokracovat. Jinak je simulace ukoncena kvuli chybe.

Jmena objektu Operace jsou parametrizovany jmeny objektu a modifikujı tyto objektynebo mnoziny tyto objekty obsahujıcı. Vzhledem k hierarchicke strukture modelu lze proidentifikaci objektu pouzıt pathname, tj. sekvenci jmen vsech objektu, ktere jsou hierar-chicky vnoreny a pozadovany objekt obsahujı, vcetne jmena tohoto objektu. Napr. v sys-temu na obr. 4.2 muzeme objekt, odpovıdajıcı vystupnı funkci hrace B identifikovat jme-nem "SIMULATIONS/Ping Pong/MODEL/Ping Pong/Player B/METHODS/outputFnc".15

Editacnı zasahy do simulace z vnejsıho prostredı Uvazujme situaci, kdy pozadavkyna editacnı operace prichazejı od vnejsıho systemu, napr. od uzivatele (viz obr. 4.3). Pokud

15Vzhledem k tomu, ze nektere slozky jmena lze eliminovat, aniz by doslo k nejednoznacnosti, muzemetentyz objekt jednoduseji identifikovat jmenem "SIMULATIONS/Ping Pong/Player B/METHODS/outputFnc".

4.4. CTENI A MODIFIKACE MODELU 37

Simulator

ModelCommand OutputX Y

S

User interface

User

Obrazek 4.3: Architektura pro interaktivnı evolucnı vyvoj

simulace bezı, pro kazdou editacnı operaci nad modelem je nutne pozastavit simulaci,provest pozadovanou operaci a pote simulaci znovu spustit:

posli (stop) korenovemu simulatorupockej na (simulationStopped),proved’ editacnı operaci,posli (start) korenovemu simulatorupockej na (simulationStarted)

Pokud simulace nebezı, provede se prımo editacnı operace. Na kazdy realizovatelny poza-davek na editacnı operaci simulator zareaguje provedenım prıslusne operace. Po provedenıeditacnı operace simulator generuje vystupnı udalost (model, M), kde M je model, kterehose editacnı operace tykala.16

Reflektivnı editacnı zasahy – sebemodifikace modelu Tento typ modifikace mo-delu umoznuje definice DynDEVS. Editace modelu je v prıpade formalismu DynDEVSpodle [Uhr01] dovolena v ramci internıho nebo externıho prechodu. Vzhledem k tomu, zealgorimus simulace je synchronnı, je provedenı jakehokoli v zasahu do modelu v tomto oka-mziku bezpecne. Model muze cıst a editovat sam sebe, ale neprımo take kontext, v kteremse nachazı. Nadrazeny model ma k dispozici stav vsech svych subsystemu a soucastı techtodılcıch stavu mohou byt pozadavky na editacnı zasahy v nadrazenem modelu. Vzhledemk tomu, ze slozeny system je konceptualne system paralelnı, musı nadrazeny system re-sit konflikty editacnıch zasahu, pozadovanych v tomtez okamziku ruznymi subsystemysoucasne.17 V prıpade, ze operaci nelze provest, neprovede se. Informaci o kontextu, vkterem se model nachazı, muze zıskat jedine prostrednictvım svych vstupu – to lze zajistitvhodnou strukturou hierarchicky nadrazeneho nadrazeneho slozeneho modelu.

Nas prıstup je zalozen na metaurovnove architekture simulatoru. Model chapeme jakosystem domenove urovne, simulator chapeme jako metasystem,18 ktery ma na vstupufrontu pozadavku na inspekci a editaci, vcetne prıpadnych maker (skriptu). Fronta se vy-prazdnuje po kazdem kroku simulace, pricemz vsechny proveditelne pozadavky na editaci

16Vcetne aktualnıho stavu a vcetne prıpadnych submodelu, viz definice v sekci4.2.17Naprıklad pri provedenı internıho prechodu je generovan vystup, ktery invokuje externı prechody v

navazujıcıch komponentach. Ve vsech techto prechodech mohou byt odpovıdajıcı zmenou stavu pozadovanyzmeny v nadrazenem modelu.

18V obou prıpadech jde o systemy specifikovatelne formalismem DEVS.


modelu jsou zpracovany.19 Reflektivity je dosazeno propojenım vystupu simulatoru najeho vstup (viz obr. 4.4). Vzhledem k tomu, ze na vystupu simulatoru je k dispozici stavmodelu, model muze takto komunikovat s vlastnım simulatorem a docılit tak vykonanıpozadovanych instrospekcnıch i reflektivnıch operacı.

Simulator

Command Output

model struct./state operation req.

ModelX Y

S

Obrazek 4.4: Simulace reflektivnıho systemu

4.5 Systemy simulacı (multisimulace)

Pozvedneme se nynı mimo cas a prostor jedne simulace. Na teto urovni pracujeme s mnohanezavislymi simulacemi a jejich casoprostory a zabyvame se dynamickym vytvarenım,rusenım a propojovanım simulacı. Toto dava smysl pro optimalizaci, vnorenou a reflektivnısimulaci a pro multiparadigmatickou simulaci.

Optimalizace zalozena na simulaci spocıva v prohledavanı prostoru vsech simulacı (avsech modelu) s cılem najıt nejlepsı model podle danych kriteriı, pricemz mıra, dojake jsou kriteria splnena, je odvozena od vysledku simulacnıch experimentu.

Vnorena a reflektivnı simulace je v podstate simulace simulujıcıch systemu – soucastımodelu M je simulator jineho modelu M ′. Pokud M ′ je modelem M , jde o reflektivnısimulaci – simulujeme system, ktery obsahuje model sebe sama a provadı s nımsimulacnı experimenty.

Multiparadigmaticka simulace je realizovana ruznymi simulatory pro ruzna modelo-vacı paradigmata. Pritom simulatory dılcıch modelu (specifikovanych ruznymi for-malismy spjatymi s pouzitymi paradigmaty) jsou synchronizovany a propojeny vramci jedne multisimulace.

Kompozice simulatoru Uvedene prıpady se lisı predevsım tım, zda simulace bezı zkonceptualnıho pohledu paralelne (na stejne urovni), nebo zda jsou simulace vnoreny. Vprvnım prıpade (paralelnı simulace) je simulator zapouzdren tak, ze bezı se synchroni-zovanym casem a zprıstupnuje rozhranı vnoreneho modelu. V druhem prıpade (vnorenasimulace) se simulator jevı jako komponenta, jejız rozhranı (vstupy a vystupy) zprıstup-nuje operace vnoreneho simulatoru, coz jsou z pohledu vnoreneho modelu metaoperace ametainformace (na teto urovni muzeme s modelem a jeho simulacı zachazet zcela libovolnebez jeho ”vedomı”). Vnoreny model pak bezı ve vlastnım, na vnejsım modelu nezavislem,

19Z hlediska prakticke implementace lze frontu v nekterych prıpadech vynechat a editacnı operace pro-vadet prımo. Pro jednoduche zasahy to nevadı, obecne je to ale nutne, kvuli serializaci pozadavku prinasobnemu prıstupu k refl. rozhranı simulatoru z mnoha submodelu soucasne.

4.5. SYSTEMY SIMULACI (MULTISIMULACE) 39

case. Je samozrejme mozne paralelnı simulaci vnorit a vnorene simulace nechat bezetparalelne. Vzhledem k tomu, ze simulator se jevı jako komponenta DEVS, je mozne hoprirozene pouzıt jako submodel slozeneho modelu a pracovat s nım stejne jako s ostatnımikomponentami.

Simulator

ModelCommand OutputSimulator





ModelCommand Output

Obrazek 4.5: Paralelnı simulace

Simulator

ModelCommand Output

Model

Simulator

Command Output

Obrazek 4.6: Vnorena simulace

Multisimulacnı system Multisimulacnı system je system, jehoz subsystemy jsou simu-lace, resp. simulatory.20 Simulator muzeme jednak modelovat (implementovat) prımo jakoDEVS (viz kap. 7), jednak ho muzeme (bez ohledu na realizaci) zapouzdrit do komponentyDEVS (tj. dat mu kompatibilnı rozhranı) a pouzıt ho jako subsystem multisimulacnıho sys-temu, ktery specifikujeme jako DEVS a simulujeme simulatorem DEVS (prıkladem muzebyt simulator pro jine paradigma, uvedeny v kapitole 6). Takto zapouzdreny simulatormuze pracovat bud’ s nezavislym casem, nebo se casem synchronizovanym s nadrazenymsystemem, podle toho, o jaky typ aplikace jde (prıklad vnorene simulace s nezavislymcasem je uveden v kapitole 8).

Planovanı simulacı V multisimulacnım prostredı je treba resit otazku pridelovanı pro-cesoru jednotlivym simulacım. Procesy jednotlivych simulacı jsou obvykle implementovanyjako procesy hostitelskeho operacnıho systemu. Pak se o pridelovanı procesoru stara pla-novac operacnıho systemu. V prıpade multisimulacnıho prostredı SmallDEVS, ktere bude

20Pojem simulace, resp. simulator, pouzıvame analogicky k pojmu proces, resp. procesor v operacnıchsystemech. Proces (v terminologii operacnıch systemu) je objekt, obsahujıcı program a aktualnı stav jehoprovadenı. Totez platı obecne pro procesor. Stejne chapeme i simulaci, resp. simulator - zahrnuje model ajeho aktualnı stav. Z jineho (nadcasoveho) uhlu pohledu jsou jak procesy, tak simulace sekvence udalostımenıcı stav. V nasem pojetı jak proces, tak simulace reprezentujı systemy, schopne generovat budoucıudalosti.


popsano v kapitole 5, se o pridelovanı procesoru stara standardnı planovac Smalltalku.Obdobne by se situace resila i v jinych podobnych prostredıch, jako je napr. Java.

4.6 Shrnutı

V navaznosti na existujıcı prıstupy, zabyvajıcımi se modely s vyvıjejıcı se strukturou (zmı-nenymi v kapitole 3) byla definovana abstraktnı architektura univerzalnıho simulacnıhosystemu s dynamickym aplikacnım rozhranım, umoznujıcı jak interaktivnı vyvoj modelu,tak reflektivitu.

Ke klıcovym atributum teto architektury patrı simulace v realnem case, propojenısimulace s okolnı realitou, klonovanı, migrace a editace submodelu za behu, metaurovnovamultisimulacnı architektura (simulatory jsou systemy, s kterymi se zachazı stejne jako smodely).

Konkretnı implementacı teto abstraktnı architektury je system SmallDEVS, kteremuse venuje kapitola 5.

Kapitola 5

Vyvoj systemu v simulaci, nastrojSmallDEVS

V teto kapitole bude predstaven konkretnı nastroj (SmallDEVS [Jan06]), implementujıcıreflektivitu a podporujıcı interaktivnı inkrementalnı vyvoj systemu za behu. Implementac-nım prostredım je Smalltalk. Popsane principy lze uplatnit i v jinych prostredıch. Existujıcıimplementace ovsem vyuzıva toho, ze Smalltalk sam o sobe je vysoce portabilnım a dojinych systemu vnoritelnym operacnım systemem, podporujıcım perzistenci, multitasking,interaktivitu a experimentalnı programovnı (exploratory programming). Smalltalk a jehoprincipy jsou take jednım z hlavnıch zdroju inspirace pro vybudovanı systemu SmallDEVS.

5.1 Motivace a zvoleny prıstup

Jako motivacnı prıklad lze uvest inkrementalnı vyvoj rıdicıho systemu autonomıho mo-bilnıho robota v simulovanem prostredı. Jde o vyvoj systemu, jehoz specifikace nenı napocatku vyvoje zcela jasna a je ji treba dodatecne upresnovat na zaklade vysledku testu,provadenych na pokusnych realizacıch v ruznych prostredıch, a to jak simulovanych, takrealnych. Vzhledem k tomu, ze je mnohdy nutne dovyvıjet realizovany system pri beznemprovozu v cılovem prostredı, je nezbytne zachovat model rızenı v prubehu celeho vyvoje,vcetne cıloveho nasazenı, s moznostı vratit se kdykoli zpet do prostredı simulovaneho.Cılova realizace rıdicıho systemu pak musı obsahovat simulator modelu rızenı, bezıcı vrealnem case a propojeny s realnym okolım. Pritom je vhodne zajistit vzdalene monitoro-vanı stavu a inkrementalnı zasahy vyvojare do modelu rızenı za bezneho provozu. Uvedenystyl vyvoje systemu klade specificke naroky na podpurne prostredky. Zvoleny prıstup jezalozen na kombinaci ctyr paradigmat:

Experimentalnı modelovanı (exploratory modeling) Jednoduse receno, netvorımemodel, abychom s nım experimentovali, ale experimentujeme, abychom nasli (vytvo-rili) spravny model. Jde v podstate o formu evolucnıho programovanı s interaktivnıfitness funkcı a s interaktivnım generovanım ruznych mutacı modelu.

Otevrene a flexibilnı podpurne prostredky Experimentalnı modelovanı je treba pod-porit odpovıdajıcım nastrojem. K jeho hlavnım rysum musı patrit reflektivnı apli-kacnı rozhranı a interaktivnı vizualnı nastroje pro inspekci a editaci modelu a ma-nipulaci se simulacemi. Otevrenost a flexibilitu potrebnou pro inkrementalnı zasahy

42 KAPITOLA 5. VYVOJ SYSTEMU V SIMULACI, NASTROJ SMALLDEVS

(programove i interaktivnı) v dobe behu muze zajisit objektove orientovany prıstupsmalltalkovskeho typu, ale vyssı mıru flexibility a bezpecnosti (dıky jednodussı rea-lizaci) muze zajistit prıstup zalozeny na prototypovych objektech.

Propojenı reality se simulacı (reality-in-the-loop simulation) V prubehu vyvojea hlavne v cılove realizaci se predpoklada propojenı modelu (ktery ve vhodnem oka-mziku formalne prohlasıme za cılovou realizaci) s realnym okolım. K tomu je nutneokolnı realitu zprıstupnit se stejnym rozhranım, jake majı komponenty modelu. Prak-ticky to znamena prvky realneho okolı zprıstupnit formou specialnıch atomickychkomponent.

Vyvoj v simulaci a zachovanı modelu (model continuity) Vyvoj zalozeny na simu-laci je vhodne krome postupu od simulace k realite umoznit i reverzne, tj. umoznitnavraty z realneho nasazenı zpet do simulace. Vyhodou je pak moznost pracovat i vsimulaci s daty zıskanymi z behu v realnem prostredı. Prakticky to znamena umoznitdynamicke klonovanı komponent modelu (resp. cıloveho programu) a prenos techtoklonu do simulovaneho prostredı.

5.2 Experimentalnı programovanı (exploratory programming)a Smalltalk

Smalltalk je vseobecne chapan jako vzorovy jazyk pro experimentalnı programovanı (ex-ploratory programming), nebot’ poskytuje ucinne prostredky pro interaktivnı zasahy dobezıcıho systemu. V teto casti popıseme podrobneji nektere souvisejıcı skutecnosti.

Experimentalnı programovanı (exploratory programming) Pojem Exploratoryprogramming je tezko prelozitelny. Pouzitelny je termın zkoumave, zkoumajıcı, pokusne,ci experimentalnı programovanı (EP). Poslednı z uvedenych termınu budeme preferovat.

Tento styl programovanı umoznuje rychlou tvorbu prototypu, tedy programu, o kte-rych predpokladame, ze mozna resı zadany problem. Je vhodny v situacıch, kdy nenı kdispozici dostatecna specifikace budoucıho dıla a vhodny zpusob realizace je treba teprveobjevit na zaklade experimentu s pokusnymi realizacemi. Jde o interaktivnı prohlednavanı(exploration) prostoru vsech moznych programu s cılem najıt ten, ktery nejlepe vyhovujeobvykle velmi nejasne zadanym pozadavkum. Takova situace je typicka v oblasti umeleinteligence, ale i v rade jinych prıpadu. LISP, Smalltalk, Prolog a Self jsou typicke jazykyumoznujıcı prave tento styl programovanı. Smalltalk (spolu s jım prımo inspirovanymijazyky, jako je Self) je navıc zajımavy tım, ze tento zpusob programovanı podporuje ivizualnımi nastroji.

Inkrementalnı kompilace Technicky je pro podporu experimentalnıho programovanınezbytna moznost okamziteho prechodu od vytvorenı programu k jeho bezprostrednımuinteraktivnımu (ale i automatickemu) otestovanı. Kompilace tedy musı trvat zlomky, maxi-malne jednotky vterin, nikoliv minuty, jak je tomu u staticky typovanych mainstreamovychjazyku. Take musı probıhat z pohledu uzivatele skryte, bez nutnosti explicitne spoustetkompilator. Toho lze prakticky docılit inkrementalnım kompilatorem, ktery zpracovava jendılcı casti vytvareneho programoveho dıla prave v okamziku jejich modifikace a prelozenykod inkrementalne zakomponovava do vysledneho celku. V prıpade Smalltalku je nejvetsı

5.2. EXPERIMENTALNI PROGRAMOVANI A SMALLTALK 43

a jedinou jednotkou prekladu jedna metoda. Vysledkem je objekt (konkretne zkompilo-vana metoda), ktery je zaregistrovan ve strukture prıslusne trıdy, coz je take objekt, kteryje soucastı objektove pameti (object memory) Smalltalku.

Programovanı za behu Podstatou EP je temer nepretrzite vyuzıvana moznost zkou-mat stav a prubeh vypoctu, pricemz program, ktery rıdı vypocet, je okamzite modifiko-vatelny inkrementalnımi zasahy. Stav vypoctu je take v libovolnem okamziku v sirokemıre editovatelny. Smalltalk poskytuje vizualnı nastroje pro zkoumanı a editaci programu(t.j. systemu trıd a jejich metod) i stavu vypoctu (t.j. obsahu instancnıch promennychjednotlivych objektu). Jak obsah instancnıch promennych zivych objektu, tak i jejichtrıdy a metody lze v libovolnem okamziku modifikovat a bezprostredne zkoumat dusledkytakovych zasahu. Takze jak zkoumanı behu programu, tak samotne programovanı pro-bıha soucasne. Takovymto spojenım programovanı s okamzitym overovanım chovanı lzeobecne dosahnout mnohem vyssı produktivity programatorske prace i vyssı kvality kodunez zdlouhavym opakovanym programovanım, naslednou explicitnı kompilacı a spouste-nım vysledne aplikace s omezenymi moznostmi sledovat chovanı programu, jak je tomu vprıpade beznych programovacıch jazyku, pouzitych pro prototypovanı a evolucnı vyvoj.Bezne programovacı jazyky totiz podporujı klasicky prıstup softwaroveho inzenyrstvı, za-lozeny na dukladne analyze pozadavku a z nı odvozene presne specifikace programovehodıla. To ovsem v prıpade nejasnych pozadavku nelze aplikovat.

Objektova pamet’ Zajımavym dusledkem prıstupu EP je fakt, ze tak zvany zdrojovykod ztracı puvodnı vyznam, protoze to, ceho se programator snazı inkrementalnımi zasahydocılit, nenı primarne zdrojovy text, ale uspokojive bezıcı programove dılo. To se totizvyvojar snazı neustale testovat, analyzovat a upravovat. V prıpade Smalltalku tedy jdeprogramatorovi primarne o vytvorenı fungujıcıcho systemu zivych objektu v perzistentnıobjektove pameti, nikoliv o vytvorenı souboru se zdrojovymi texty, ktere po zkompilovanıa spustenı takovy system objektu pri odstartovanı vytvorı. Programator ve Smalltalkuneedituje zadne textove soubory, ale inkrementalne modifikuje objekty prımo v objektovepameti za pomoci inkrementalnıho kompilatoru spojeneho s nastroji pro navigaci v sys-temu objektu. Kompilator je automaticky aktivovan jako reakce na zasahy programatora,ktery edituje jen jednotlive textove reprezentace metod, ktere jsou mu zprıstupneny vnastroji na prohlızenı trıd. Textovou podobu metod Smalltalk spravuje ve vlastnı rezii aumoznuje prıstup i k historickym verzım metod. Tyto informace Smalltalk uklada do logumimo objektovou pamet’. V prıpade, ze by tento log z jakehokoliv duvodu nebyl k dis-pozici, nabızı k prohlızenı a editaci dekompilovanou podobu metod. Tento prıstup jenompodtrhuje nezavislost Smalltalku na externıch souborech a textech. Predmetem zkoumanıa modifikace jsou vylucne jen zive objekty v objektove pameti Smalltalku.

Export a import objektu Soubory s textovou podobou trıd a jejich metod lze vprıpade potreby kdykoliv ze Smalltalku vygenerovat, ale rozhodne je nelze povazovat zaprimarnı. Prestoze tak mohou byt videny, nejsou to zdrojove texty v pravem smyslu slova.Needitujı se, slouzı typicky jen pro prıpadny prenos vytvoreneho dıla do objektove pametijineho Smalltalku. Takto vygenerovane texty nejsou urceny k tomu, aby je cetl, analyzovala editoval clovek. Jak prohlızenı, tak i analyza a editace systemu trıd se prirozene realizujev jejich primarnı, zive podobe, t.j. v podobe objektu v objektove pameti. Proto takemnohe Smalltalky preferujı export nikoliv v podobe, ktera by zdrojovy text pripomınala,


ale adeji v XML, coz je dnes povazovano za standard pro textovou reprezentaci trıd aobjektu, urcenou ke strojovemu zpracovanı.

Perzistence, obraz pameti Jelikoz nepracujeme se zdrojovymi texty v souborech, ales objektovou pametı, musı system pro EP podporovat moznost jejıho kompletnıho ulozenına externı medium (obvykle do souboru) v podobe tzv. obrazu (image). Tento obraz ob-jektove pameti je pri startu systemu (Smalltalku) nacten a objektova pamet’ je rekonstru-ovana presne v te podobe, v jake byla predtım ulozena. Nektere Smalltalky jsou schopnynepretrzite obraz objektove pameti udrzovat na disku a take resit odkladanı nepouzıva-nych castı na disk v prıpade nedostatku volne operacnı pameti. Takovym Smalltalkem jenapr. system GemStone [?], deklarovany jako objektove orientovany databazovy systempro klient-server aplikace.

Reflektivita a dynamicnost Smalltalk je pomerne rozsahly programovy system vytvo-reny ve Smalltalku samotnem. Jde o typickou ukazku systemu, ktery je sam sebe schopenza behu vyvıjet. K tomu je treba, aby objekty mohly zkoumat a modifikovat objekty(vcetne sebe). Objekt muze zkoumat i modifikovat jak trıdy (tj. mnozinu metod a speci-fikaci reprezentace stavu), tak jejich instance (tj. obsah instancnıch promennych). Modifi-kace trıdy ve Smalltalku okamzite ovlivnı strukturu a chovanı vsech jejıch instacı.

Smalltalk je dynamicky jazyk. To znamena, ze programove struktury mohou vznikat azanikat za behu. Smalltalk je system, vytvoreny a bezıcı ve Smalltalku. Programovanı veSmalltalku znamena postupnou modifikaci Smalltalku smerem ke kyzene aplikaci. Small-talk, resp. aplikace ve Smalltalku vytvarena, tedy ve skutecnosti provadı sebemodifikaci atım se toto programove dılo vyvıjı.

Pouzitelnost EP EP je obecne vhodne v techto situacıch:

• male projekty,

• male tymy (v idealnım prıpade aplikujıcı zasady extremnıho programovanı),

• nejasne zadanı,

• omezene prostredky (cas, prostor, penıze).

EP je naopak nevhodne pro velke projekty a velke tymy. Tam se pocıta prave se zavede-nymi beznymi technikami softwaroveho inzenyrstvı s dukladnou predbeznou analyzou a sexistujıcımi rozsahlymi a otestovanymi knihovnami pro bezne, obvyle staticky typovanejazyky. Take veskere podpurne nastroje, umoznujıcı tymovy vyvoj, jsou zalozeny na spravesouboru se zdrojovymi texty, ktere se povazujı za primarnı a jedinou udrzovanou podobuprogramoveho dıla.

Bezpecnost Jazyky pro EP jsou vesmes jazyky s dynamickou typovou kontrolou. Jazykys dynamickou typovou kontrolou nevyzadujı deklarace typu promennych, protoze nejsou kprekladu zapotrebı. Nektere jazyky (napr. Strongtalk [?]) umoznujı nepovinne deklarovattypy promennych tam, kde to ma vysvetlujıcı, dokumentacnı vyznam. Smalltalk, LISP,Self, Prolog ani Python s deklaracemi typu nepocıtajı. Je vsak treba zduraznit, ze ve vsechtechto prıpadech jde o jazyky typove bezpecne, tj. nemuze za zadnych okolnostı dojıt kchybe, zpusobene aplikacı operace nad nespravnym typem dat.

5.3. OBJEKTOVA ORIENTACE ZALOZENA NA PROTOTYPECH 45

Potencialnı problem dynamicky typovanych jazyku ale tkvı v tom, ze na prıpadnetypove nekompatibility se prijde az za behu. Ale vzhledem k tomu, ze EP je zalozeno navelmi dukladnem testovanı, pravdepodobnost neodhalenı takove chyby je obvykle mnohemprijatelnejsı nez cena vyvoje s pouzitım klasickeho staticky typovaneho jazyka (nehledena fakt, ze staticka typova kontrola neodhalı jine vazne chyby, ktere nejsou zpusobenytypovou nekompatibilitu).

5.3 Objektova orientace zalozena na prototypovych objek-tech

Dalsım zdrojem inspirace pro SmallDEVS je objektova orientace zalozena na prototypo-vych objektech [Lie86]. Vzorovym jazykem, zalozenym na prototypovych objektech je Self[US87]. Prıme pouzitı tohoto jazyka by pro nase ucely bylo problematicke z hlediska inte-roperability a portability, proto vyhodne vyuzujeme toho, ze tento styl programovanı je kdispozici prımo ve Smalltalku dıky rozsırenı, ktere je implementovano v balıku Prototypes[MA04]. Jde o jednoduchy framework pro Smalltalk, nikoliv o vnoreny jazyk. Jazykem prospecifikaci metod zustava Smalltalk. Na rozdıl od klasickeho beztrıdnıho OO jazyka Selfu[US87] jsou zde proto nektere mırne odlisnosti:

• Reprezentace objektu zustava zachovana, takze se rozlisujı datove sloty a metody.

• Jazyk pro specifikaci metod je Smalltalk, takze pro prıstup ke slotum je treba zasılatzpravy explicitne (pres self).

• Lze libovolne vyuzıvat existujıcıch objektu Smalltalku a kombinovat prototypoveobjekty s objekty definovanymi trıdami.

• Vsechny prototypove objekty jsou instancemi trıdy PrototypeObject, ktera je pod-trıdou Behavior, stejne jako metatrıdy.

Zakladnı princip prototypovych objektu lze charakterizovat takto:

• Prototypovy objekt ma sloty, metody a delegaty (viz dale), umı reagovat na zpravy.Reakce na zpravu spocıva v provedenı odpovıdajıcı metody nebo vracenı obsahuodpovıdajıcıcho slotu.

• Dedicnost je realizovana delegacı. Nerozumı-li objekt zprave, hleda se odpovıdajıcımetoda (nebo slot) v delegatech, po nalezenı se metoda provede v kontextu puvod-nıho prıjemce zpravy.

• Prototypovy objekt rozumı metaoperacım pro editaci objektu (manipulaci se sloty,metodami a delegaty).

• Nad libovolnym prototypovym objektem lze v libovolnem okamziku otevrıt Inspek-tor, ktery umoznı interaktivnı zkoumanı a editaci objektu.

Typicke pouzitı a soucasne princip programovanı bez trıd si ukazeme na prıkladech.

Vytvorenı prazdneho objektu anObject← PrototypeObject new.


Inspektor anObject inspect .

Vysledkem je otevrenı inspektoru (obr. 5.1).

Obrazek 5.1: Inspektor prototypoveho objektu

Inspektor je kombinacı browseru a klasickeho smalltalkovskeho inspektoru, protozeprototypovy objekt je v podstate kombinacı trıdy a jejı instance. Pomocı tohoto nastrojeje mozne zkoumat a modifikovat stav objektu, ale take jeho metody a delegaty (delegatijsou objekty, na ktere objekt deleguje zpravy, ktere nenı sam schopen obslouzit – takto jev beztrıdnıch systemech realizovano sdılene chovanı mnoziny objektu, tj. dedicnost).

Klonovanı anotherObject← anObject clone .

Klon je melkou kopiı originalu. Pro jine nez melke kopie je treba vytvorit vlastnı metody.

Operace nad sloty anObject addSlot : ’x ’ .anObject addSlot : ’x ’ withValue: 0.anObject removeSlot : ’x ’ .

Tehoz efektu lze docılit pomocı inspektoru. Stacı vybrat –slots– a sledovat instrukce,prıpadne vybrat konkretnı slot a vyvolat kontextovou nabıdku.

Operace nad metodami anObject addMethod: ’printOnTranscript

Transcript show: se l f x printString ’ .anObject methodSourceAt: #printOnTranscript .anObject removeMethod: #printOnTranscript .

Tehoz efektu lze docılit pomocı inspektoru. Stacı vybrat –methods– a sledovat instrukce,prıpadne vybrat konkretnı metodu a vyvolat kontextovou nabıdku.

5.4. MODELOVANI SYSTEMU PROTOTYPOVYMI OBJEKTY 47

Operace nad delegaty anObject addDelegate : ’parent ’ withValue: (PrototypeObject new).anObject removeDelegate : ’parent ’ .

Tehoz efektu lze docılit pomocı inspektoru – stacı kliknout na –delegates– a sledovatinstrukce, prıpadne kliknout na konkretnıho delegata a vyvolat kontextovou nabıdku.

Zaslanı zpravy anObject printOnTranscript

S prototypovymi objekty lze komunikovat stejne jako s ostatnımi objekty Smallalku. Pro-totypove objekty a ostatnı objekty Smalltalku jsou z vnejsıho pohledu zcela zamenitelnea lze je libovolne kombinovat.

5.4 Modelovanı systemu prototypovymi objekty

Vyjasneme nynı duvody, proc je k modelovanı vyvıjejıcıch se systemu vhodne pouzıt pro-totypove objekty. Trıdnı prıstup k modelovanı je omezujıcı tım, ze bud’ vyzaduje znatvsechny trıdy predem, v dobe kompilace (v prıpade staticky kompilovanych jazyku), nebovyzaduje tvorit (a odstranovat) trıdy za behu (v prıpade dynamickych jazyku). Prvnımoznost skutecne omezuje modelovacı sılu jazyka – dynamicky lze menit jen strukturumodelu, slozeneho z predem znamych komponent. Druha moznost je zbytecne kompliko-vana, i kdyz ji v principu dynamicke jazyky pripoustejı. Duvodem je principialnı staticnostsystemu trıd. Jakekoli dynamicke modifikace toho v principu statickeho systemu jsou sicemozne, ale jejich realizace je komplikovana a ne kazdy jazyk ji umoznuje. Je totiz treba prijakemkoli dynamickem zasahu zachovat konzistenci systemu. Napr. Smalltalk umoznujemodifikovat definici trıdy i v prıpade, ze existujı jejı instance (instance jsou vymeneny zanove se zachovanım puvodnı identity), nebyva to vsak beznym zvykem ve vetsine dyna-mickych jazyku.

Naproti tomu, jakakoliv dynamicka manipulace s prototypovymi objekty je trivialnı,jak jsme videli v predchozı podkapitole. Omezuje se na klonovanı a editaci objektu. Sdı-lene chovanı, kvuli kteremu davajı trıdy smysl, je jednoduse realizovatelne prostrednictvımdelegace, kterou lze take dynamicky menit trivialnım zpusobem. Krome toho, manipulaces prototypovymi objekty pripomına manipulaci s libovolnymi objekty, blızkymi cloveku.Napr. interaktivnı (ale i skriptovana) prace s jakymikoli dokumenty take spocıva v kopı-rovanı a editaci. Chceme-li umoznit interaktivnı dynamicke zasahy do simulace, je tentozpusob manipulace s objekty velmi vhodny dıky sve jednoduchosti a prımocarosti.

generator

jobOut

processor

jobIn

jobDone

discard

jobDone

discard

Obrazek 5.2: Generator a procesor.


Prıklad Nynı ukazeme prıklad modelu, vytoreneho inkrementalne z prototypovych ob-jektu. Nasledujıcı sekvence vyrazu je program (skript), ktery postupne vytvorı model ge-neratrou a procesoru. Tento skript muze byt proveden naraz, nebo mohou byt jednotlivevyrazy vyhodnocovany postupne, krok za krokem v interaktivnım prostredı Smalltalku(ve workspace). Nejprve vytvorıme generator uloh. | system generator processor jobPrototype |jobPrototype← PrototypeObject new.jobPrototype addSlots : ’n ’ −> 0. ’ size ’ −> 0. ’name’ −> ’aJob ’ . .jobPrototype addMethod: ’setSizeBetween : s l and: sh

se l f size : ( s l to : sh) atRandom’ .

generator←AtomicDEVSPrototype new.generator addSlots :

’ jobPrototype ’ −> jobPrototype .’ ia ’ −> 2. ”interval min” ’ ib ’ −> 7. ”interval max”’ sa ’ −> 5. ”job size min” ’sb ’ −> 10. ”job size max”’ f i r s t ’ −> true . ’n ’ −> 0. ”number of jobs generated”.

generator intTransition : ’ se l f f i r s t : false ’ .generator outputFnc: ’

se l f n: se l f n +1.se l f

poke:(( se l f jobPrototype setSizeBetween : se l f sa and: se l f sb) clone

n: se l f n;yourself )

to : #out ’ .generator timeAdvance: ’↑ se l f f i r s t

ifTrue : [ 0 ]ifFalse : [ ( se l f ia to : se l f ib) atRandom ] ’ .

generator addOutputPorts: #out. Nasledujıcı sekvence vyrazu vytvorı model procesoru.

processor←AtomicDEVSPrototype new.processor addSlots :

’queue ’ −> OrderedCollection new.’queueSize ’ −> 5.’processorStatus ’ −> #idle .’currentJob ’ −> nil .’timeSpent ’ −> 0 .

processor addInputPorts : #in.processor addOutputPorts: #out . #discard.processor intTransition : ’

se l f processorStatus caseOf : [ #busy ] −> [

se l f queue size > 0ifTrue : [

se l f currentJob : ( se l f queue removeFirst) ]ifFalse : [

se l f processorStatus : #idle .se l f currentJob : nil ] .

se l f timeSpent : 0 ] .

5.4. MODELOVANI SYSTEMU PROTOTYPOVYMI OBJEKTY 49

[ #discard ] −> [se l f queue removeFirst .se l f queue size <= sel f queueSize ifTrue : [

se l f processorStatus : #busy ] ] .[ #idle ] −> [ ”nothing” ] ’ .

processor extTransition : ’se l f queue add: ( se l f peekFrom: #in ) .

se l f processorStatus caseOf : [ #idle ] −> [

se l f processorStatus : #busy.se l f currentJob : ( se l f queue removeFirst) ] .

[ #busy ] −> [se l f timeSpent : se l f timeSpent + se l f elapsed .se l f queue size > se l f queueSize

ifTrue : [ se l f processorStatus : #discard ] ] .[ #discard ] −> [ ”nothing” ] ’ .

processor outputFnc: ’se l f processorStatus caseOf : [ #busy ] −> [ se l f poke: se l f currentJob to : #out ] .[ #discard ] −> [ se l f poke: ( se l f queue last ) to : #discard ] .[ #idle ] −> [ ”nothing” ] ’ .

processor timeAdvance: ’se l f processorStatus caseOf : [ #busy ] −> [ ↑ se l f currentJob size − se l f timeSpent ] .[ #discard ] −> [ ↑ 0 ] .[ #idle ] −> [ ↑ Float infinity ] ’ .

Komponenty propojıme do jednohoho celku vyhodnocenım nasledujıcı sekvence vyrazu. system←CoupledDEVSPrototype new.system addOutputPorts:

#out .#discard .

system addComponents: #generator −> generator .#processor −> processor .

system addCouplings : #(generator out) −> #(processor in ) .#(processor out) −> #(se l f out ) .#(processor discard) −> #(se l f discard) .

Takto vytvoreny model muze byt simulovan vyhodnocenım vyrazu system getSimulator simulate : 500. Vyse uvedeny kod je skript, ktery zasılanım zprav vhodnym objektum inkrementalne

vytvorı model. Kody metod jsou predany jako parametry odpovıdajıcıch zprav a odpovı-dajıcı objekty si je v reakci na tyto zpravy automaticky zakompilujı do svych struktur.

Pro jakoukoliv manipulaci s modelem je podstatny model sam, nikoliv skript, ktery hovytvoril. Jakoukoliv potrebnou informaci je mozne zıskat komunikacı s objekty modelu.Napr. kod metody, kterou jsme drıve zakompilovali do objektu, lze zıkat takto:

anObject methodSourceAt: aMethodName.


Pro takto inkrementalne vytvoreny programovy system nenı zpusob jeho vytvorenıpodstatny, takze skript, ktery ho vytvoril, nechapeme jako zdrojovy kod v pravem slovasmyslu. Takovy skript lze kdykoli pro existujıcı system automaticky vygenerovat.

Skript, ktery zrekonstruuje objekt (vcetne vcech z neho odkazovanych objektu) muzebyt zıskan vyhodnocenım vyrazu

script ← anObject storeString . Jinou moznostı je zıskat definici objektu v XML s vyuzitım knihovny SIXX:

sixxString ← anObject sixxString . Rekonstrukce objektu se pak provede vyhodnocenım nektereho z vyrazu:

anObject← Object readFrom: StoreString .anObject← Object readSixxFrom: sixxString .

Takto lze manipulovat se vsemi objekty, vcetne modelu a bezıcıch simulacı.

5.5 Sdılene chovanı, znovupouzitelnost

Ve vyse uvednem modelu muzeme jednoduse pridat dalsı procesory naklonovanım extujı-cıcho procesoru. Ale pozdejsı modifikace procesoru se pak dotknou jen jednoho exemplare.Chceme-li zajistit, aby vsechny procesory sdılely jednu definici, je treba ji presunout zprocesoru do separatnıho objektu, ktery se nazyva trait. Samotny procesor je pak popsanmodelem, definujıcım jen instancne specificke skutecnosti a delegujıcım zpracovanı vsechostatnıch zprav na prıslusny trait. Klony takto definovaneho procesoru pak sdılı jednudefinici a jejı prıpadna modifikace pak ovlivnı chovanı vsech klonu. Trait procesoru muzebyt vytvoren takto:

processorTrait←AtomicDEVSTrait new.processorTrait addMethod: ’ intTransition . . . . . . . . ’ .processorTrait addMethod: ’extTransition . . . . . . . . ’ .processorTrait addMethod: ’outputFnc . . . . . . . . ’ .processorTrait addMethod: ’timeAdvance . . . . . . . . ’ .

Metody intTransition, extTransition, outputFnc, timeAdvance traitu jsou definovany stejnejako u procesor ve vyse uvedenem modelu. Spolecne s trait objektem je treba specifikovatprototyp procesoru:

processorPrototype←AtomicDEVSPrototype new.processorPrototype addSlots :

’queue ’ −> OrderedCollection new.’queueSize ’ −> 5.’processorStatus ’ −> #idle .’currentJob ’ −> nil .’timeSpent ’ −> 0 .

processorPrototype addInputPorts : #in.processorPrototype addOutputPorts: #out . #discard.processorPrototype addDelegate : ’defaultTrait ’ withValue: processorTrait .

Specifikovanım delegace na trait zajistıme sdılenı definice chovanı vsemi klony prototypuprocesoru. Nynı muzeme specifikovat system s nekolika procesory stejneho typu:

5.6. IN(TRO)SPEKCE A REFLEKTIVITA 51

system←CoupledDEVSPrototype new.system addOutputPorts: #out . #discard .system addComponents: #generator −> generator .previousPort←#generator . #out.1 to : 3 do: [ : i |

newProcessor← processorPrototype copy.newProcessorName← (#processor , i printString) asSymbol.system addComponents: newProcessorName −> newProcessor .system addCouplings :

previousPort −> newProcessorName. #in.newProcessorName. #out −> #sel f . #out .

previousPort← newProcessorName. #discard ] .system addCouplings : newProcessorName. #discard −> #sel f . #discard .

Poznamenejme, ze trait objekty mohou take delegovat zpracovanı zprav na dalsı traitobjekty. Tımto zpusobem trait objekty hrajı roli trıd a delegace modeluje dedicnost vklasickem prıstupu k objektove orientaci. Je mozna i nasobna delegace i dynamice zmenyteto relace.

5.6 In(tro)spekce a reflektivita

Vyse uvedeny model, obsahujıcı generator a 3 procesory, byl vytvoren skriptem, kterykomponenty dynamicky propojil. Vysledne propojenı lze zkontrolovat. Propojenı zıskamevyhodnocenım vyrazu system couplings nebo system couplingStoreString . Vysledkem je mnozina asociacı dvojic <copmponentName portName>, prıpadne kod, je-hoz vyhodnocenım zıkame prıslusnou struktutu, ktera vypada takto: #generator . #out −> #processor1 . #in.#processor1 . #out −> #sel f . #out.#processor1 . #discard −> #processor2 . #in.#processor2 . #out −> #sel f . #out.#processor2 . #discard −> #processor3 . #in.#processor3 . #out −> #sel f . #out.#processor3 . #discard −> #sel f . #discard.

Tato struktura muze byt (po prıpadnych modifikacıch) pouzita pozdeji jako argumentzprav system removeCouplings: couplings .system addCouplings : couplings . Podobne muzeme zıskat dalsı informace o modelu a jeho komponentach, jako jsou jmenaslotu, objekty, ktere jsou referencovany ze slotu, metody, delegati, komponenty slozeneho


modelu apod. Take muzeme klonovat a editovat cely model nebo libovolnou jeho cast,a to i v prubehu simulace. Muzeme pridavat a odstranovat komponenty, sloty, delegaty,metody apod. Tyto operace jsou prıstupne uzivateli, resp. nadrazenemu systemu, ale take(reflektivne) modelu, ktereho se tyto operace tykajı.

5.7 Operacnı system

Pod pojmem operacnı system rozumıme veskere programove prostredky pro podporu vy-tvarenı a behu aplikacne specifickeho softwaru, vcetne moznosti libovolne manipulace snım. Jde o software, vytvarejıcı potrebnou abstrakci nad tzv. holym pocıtacem a posku-tujıcı operace pro manipulaci s programy a bezıcımi procesy jak uzivateli, tak temto pro-gramum a procesum.

5.7.1 Smalltalk a SmallDEVS

Odmyslıme-li hostitelsky operacnı system, zakladnı vrstvu operacnıho systemu Small-DEVS tvorı Smalltalk. Ten zahrnuje virtualnı stroj, kompilator, vıceprocesove prostredı,knihovnu trıd, vstupy a vystupy a interaktivnı vyvojove nastroje, z nichz pro SmallDEVSjsou podstatne nastroje Workspace a Inspector.1 Workspace umoznuje editaci textu a in-teraktivnı vyhodnocovanı fragmentu kodu. Vysledne objekty mohou byt zkoumany v tex-tove podobe nebo prostrednictvım inspektoru. Inspektor umoznuje zkoumat stav objektu,komunikovat s nım a editovat jeho aktualnı stav.

Model, ktery byl prezentovan vpredchozıch sekcıch, muze byt vytvoren vyhodnocenımprıslusneho kodu ve Workspace. Stejnym zpusobem lze model zkoumat i editovat, jak jizbylo ukazano. Lze tez odstartovat simulaci a sledovat jejı prubeh (log). Simulaci lze spustitjako proces na pozadı a asynchronne s nı komunikovat.

[ s ← system getSimulatorRT. s simulate : 500. ]forkAt : Processor userBackgroudPriority .

s ← system getSimulatorRT.s stopTime: Float infinity .s RTFactor: 1.s start . s stop .

Komunikacı se simulatorem s muzeme zıskat simulovany model a zkoumat stav jeho kom-ponent. Nasledujıcı prıklad otevre inspektor na obsahem slotu ’queue’ prvnıho procesoru:

(s rootDEVS componentNamed: #processor1) model queue inspect Model muzeme v prubehu simulace editovat zpusobem, ktery byl uveden v predchozıchsekcıch. Muzeme tez cely model v libovolnem okamziku klonovat:

savedSystem← system copy. 1Ostatnı nastroje Smalltalku, jako je Browser, Debugger apod., jsou ovsem take k dispozici.

5.7. OPERACNI SYSTEM 53

5.7.2 Perzistence

V predchozıch sekcıch byla perzistence modelu jednoduse resena prirazenım do promen-nych v ramci Workspace. Systematictejsı prıstup je zalozen na vyuzitı hierarchickeho ulo-ziste MyRepository:

MyRepository at : ’/Simulations/GeneratorAnd3Processors ’ put : system. aComponent←MyRepository at : ’/Simulations/GeneratorAnd3Processors ’ . aComponent← (MyRepository componentNamed: ’Simulations ’ )

componentNamed: ’GeneratorAnd3Processors ’ . aComponent addComponents: name1−> object1 . name2−> object2 .

Toto uloziste (vcetne vsech v nem aktualne bezıcıch simulacı) i libovolnou jeho cast lze vlibovolnem okamziku klonovat, prıpadne v textove forme ulozit na externı medium neboprenest do jineho Smalltalku.

5.7.3 Vizualnı nastroje pro manipulaci s modely a simulacemi

Workspace a Inspector, s kterymi jsme vystacili v predchozıch sekcıch, jsou standardnıminastroji, ktere jsou soucastı operacnıho systemu Smalltalku. Prostredı SmallDEVS alenavıc poskytuje specializovane vizualnı nastroje pro sugestivnejsi a prehlednejsı manipulacis modely a simulacemi.

Tyto nastroje byly inspirovany nastroji pro manipulaci s prototypovymi objekty vsystemu Self [US87]. Self je jazyk a system, zalozeny na prototypovych objektech. Zaklad-nım vizualnım nastrojem programatora je tak zvany Outliner. Jde o nastroj, umoznujıcıcızkoumat a modifikovat strukturu objektu. Srovname-li tento nastroj se nastroji Small-talku, Outliner spojuje funkcnost Browseru a Inspectoru, protoze v systemu Self pojemtrıda a instance splyvajı v jeden koncept – objekt obsahuje data i metody. V prostredısystemu Self jsou vizualizovatelne vztahy (reference) mezi objekty a je mozne s obsahyslotu (referencemi na objekty) manipulovat kopırovanım a vkladanım (copy-paste), resp.presouvanım (drag-and-drop). Refaktoring objektu (premist’ovanı slotu mezi ruznymi ob-jekty) je tak mozne provadet intuitivnım, konkretnım a bezprostrednım zpusobem.

Velmi podobne se manipuluje s dokumenty a slozkami pomocı vizualnıch interaktiv-nıch nastroju soudobych operacnıch systemu – ty umoznujı vytvaret, vyjımat, kopıro-vat, vkladat, prejmenovavat a otvırat (new, cut, copy, paste, rename, open) dokumenty aslozky. V nasem prıpade takto pracujeme s objeky, umıstenymi v hierarchicke struktureMyRepository. Rozdıl oproti manipulaci se soubory je ten, ze jde o zive objekty, prıpadnebezıcı simulace (nikoliv pojmenovane retezce zvane soubory) a vse se odehrava v operacnıpameti, nikoliv na externım mediu (prıpadna externalizace objektu v textove podobe jeovsem mozna, jak bylo uvedeno vyse).

Podstatnou vlastnostı vizualnıch nastroju SmallDEVS je jejich transparentnost – umoz-nujı zkoumat a manipulovat s objekty bez ohledu na to, zda byly interaktivne vytvorenytemito nastroji nebo zda vznikly jako vysledek behu programu. Teto transparentnosti jedosazeno tım, ze se nepracuje se zdrojovymi texty objektu, ale pracuje se s objekty prımo(zdrojove texty se neuchovavajı, protoze jsou zbytecne, jak jiz bylo uvedeno).


Kazdy objekt je mozne zkoumat a editovat. Podle typu objektu se otevre odpovıdajıcınastroj. Ke zkoumanı a editaci obecnych objektu slouzı PrototypeObjectInspector (obr.5.1), ke zkoumanı a modifikaci MyRepository slouzı MyRepositoryBrowser (obr. 5.3 vlevonahore), ke zkoumanı atomickych modelu slouzı AtomicModelExplorer (obr. 5.3 vlevodole), ke zkoumanı a editaci slozenych modelu slouzı CoupledModelExplorer (obr. 5.3vpravo nahore), k ovladanı simulacı slouzı SimulationControlPanel (obr. 5.3 vpravo dole).Odpovıdajıcı nastroj se otevre automaticky v dusledku vyhodnocenı vyrazu

anObject open.

Obrazek 5.3: SmallDEVS – vizualnı nastroje pro manipulaci s modely a simulacemi

5.8 Aplikacnı rozhranı jadra SmallDEVS

Obrazek 5.4 ukazuje kompozici protokolu AtomicDEVSPrototype, CoupledDEVSProto-type, PrototypeObjectForSimulation, AtomicDEVSTrait, MyRepository a DEVSRootSol-verRT. Jde o kompletnı aplikacnı rozhranı jadra SmallDEVS, dostupne jak vizualnım vy-vojovym nastrojum, tak programum a skriptum pro tvorbu modelu a manipulaci s nimi.

5.9. POZNAMKA K IMPLEMENTACI 55

Obrazek 5.4: Aplikacnı rozhranı jadra SmallDEVS.

5.9 Poznamka k implementaci

SmallDEVS je implementovan ve Smalltalku za pouzitı rozsırenı Prototypes. Muze bytchapan jako vzor, podle ktereho lze prezentovany koncept realizovat i v jinem prostredı.V prıpade, ze by slo o staticky jazyk, jako je Java, C/C++ apod., nevyhneme se pouzitıvnoreneho interpretu vhodneho dynamickeho jazyka s inkrementalnım kompilatorem.


Kapitola 6

Specifikace systemu s diskretnımiudalostmi objektoveorientovanymi Petriho sıtemi

Prıme pouzitıtı formalismu DEVS pro specifikaci systemu nemusı byt vzdy vyhodne. Pro-blematicke jsou zejmena prıpady, kde se struktura systemu menı prılis rychle a kompli-kovane. Rekonfigurovat strukturu slozeneho modelu by je pak bylo prılis obtızne. Lepsımoznostı je v takovych prıpadech pouzıt objektove paradigma s adresovatelnymi objektya zasılanım zprav. Jako optimalnı se jevı kombinace, ve ktere je DEVS pouzit pro struk-turovanı systemu do vıcemene statickych komponent, zatımco dynamicky vznikajıcı a za-nikajıcı objekty jsou pouzity uvnitr atomickych komponent DEVS.

V nasledujıcım textu je popsana moznost definovat system s diskretnımi udalostni ob-jektove orientovaymi Petriho sıtemi (OOPN). Je strucne predstaven formalismus OOPNa jeho simulator, vcetne zapouzdrenı do atomicke komponenty DEVS. Pritom je zohled-nena moznost dynamickych zasahu do bezıcı simulace v souladu s konceptem otevrenehosystemu, definovaneho v kapitole 4.

6.1 Petriho sıte a objekty

Zakladnı koncept Petriho sıtı definoval v sedesatych letech C. A. Petri. Jde o matematickystroj se sugestivnı vizualnı reprezentacı, ktery srozumitelne modeluje synchronizaci a ko-munkaci procesu v paralelnıch a distribuovanych systemech. Existuje cela rada variantPetriho sıtı. Na tomto mıste se soustredıme predevsım na vysokourovnove Petriho sıte,konkretne pak na Objektove orientovane Petriho sıte (OOPN) [Jan95, Jan98, MVT97,MVT02, JK07]. Ostatnı bezne pouzıvane typy Petriho sıtı jsou subformalismy objek-tove orientovych Petriho sıtı.1 Konkretnı implementacı OOPN je interpret jazyka PNtalk[PNt06, JK03, JK05a, JK05b, MVR+06].

1Objektove orentovane Petriho sıte [Jan98] byly navrzeny s cılem pokryt schopnosti ostatnıch typuPetriho sıtı a umoznit pouzıt Petriho sıte zpusobem, ktery je srovnatelny s programovanım v univerzalnımobjektove orientovanem jazyce.

58 KAPITOLA 6. SPECIFIKACE SYSTEMU FORMALISMEM OOPN

6.1.1 Princip vysokourovnove Petriho sıte

Petriho sıt’ je specifikovana formou bipartitnıho orientovaneho grafu, obsahujıcı dva typyuzlu – mısta a prechody – propojene hranami. Mısta, prechody i hrany mohou byt opat-reny anotacemi, specifikovanymi vhodnym inskripcnım jazykem. Mısta mohou obsahovatmultimnoziny znacek (tokens). Stav systemu je modelovan rozlozenım znacek v mıstech.Ke zmenam stavu dochazı v dusledku provadenı prechodu. Prechod ma definovana vstupnıa vystupnı mısta (ta jsou s prechodem propojena vstupnımi a vystupnımi hranami). Pre-chod je proveditelny, jsou-li v jeho vstupnıch mıstech znacky, ktere jsou specifikovanu navstupnıch hranach. Provedenım prechodu se tyto znacky ze vstupnıch mıst odstranı a dovystupıch mıst se vygenerujı znacky pecifikovane vystupnımi hranami.

Ve vysokourovnove Petriho sıtı mohou znacky reprezentovat libovolna data, ktera mo-hou byt provadenım prechodu libovolne zpracovavana. Vyrazy na hranach specifikujı mul-timnoziny znacek. Mohou obsahovat promenne. Ty musı byt v ramci provedejı prechodunavazany na konkretnı hodnoty. Prechod muze navıc obsahovat straznı podmınku, je-jız splnenı je vyzadovano pro provedenı prechodu. Krome toho muze obsahovat akci,ktera provede libovolny vypocet nad vstupnımi daty. Vysledky pak mohou byt ulozenydo vystupnıch mıst. Na obr. 6.1 je prıklad prechodu ve vysokourovnove Petriho sıti (bezstraznı podmınky a akce). Obsahuje promenne x a y. Je proveditelny pro dve ruzna na-vazanı promennych x = 1, y = A a x = 1, y = B. Jeho provedenı je realizovano prox = 1, y = A.

(a) (b)

x

2‘y+ 3‘B

2‘x

x‘y

2‘7

1 1 24 5 5

A A A B B B

1 1 2

x‘y

2‘7

24 5 5

A

1 2A BB

4 54 5 77

x

2‘y+ 3‘B

2‘x

Obrazek 6.1: Provedenı prechodu ve vysokourovnove Petriho sıti pro navazanı promennychx = 1, y = A. (a) – stav pred provedenım, (b) – stav po provedenı prechodu.

6.1.2 Paralelnı objektove orientovany system

OOPN podle [Jan98] specifikuje paralelnı objektove orientovany system. Takovy systemlze popsat jako abstraktnı matematicky stroj, ktery ma strukturu a chovanı. Strukturaobjektove orientovaneho systemu je urcena mnozinou trıd, specifikujıcıch reprezentaci in-stancı (instancnı promenne) a mnozinu metod, vcetne tzv. implicitnı metody, popisujıcıimplicitnı aktivitu objektu. Dynamika systemu spocıva v postupnych zmenach stavu (pri-cemz jeden stav je definovan jako vychozı). Stav objektove orientovaneho systemu je danmnozinou momentalne existujıcıch objektu. Kazdy z nich se nachazı ve stavu, ktery je danhodnotami instancnıch promennych a stavy vsech momentalne existujıcıch (rozpracova-nych) metod. Evoluci (postupne zmeny stavu) tohoto systemu lze pak definovat pravidly,

6.1. PETRIHO SITE A OBJEKTY 59

specifikujıcımi podmınky vyskytu jistych udalostı a zmeny stavu pri vyskytu techto uda-lostı. V paralelnım objektove orientovanem systemu existujı ctyri typy udalostı:

1. Udalost typu A – zmena stavu objektu bez interakce s ostatnımi objekty.

2. Udalost typu N – vytvorenı noveho objektu pri zaslanı zpravy new prıslusne trıde.

3. Udalost typu F – vytvorenı nove instance metody pri zaslanı odpovıdajıcı zpravy.

4. Udalost typu J – ukoncenı existence instance metody s predanım vysledku volajıcımuobjektu.

Implicitnı soucastı kazde udalosti je garbage collecting, tedy odstranenı nedostupnych ob-jektu.

Udalosti menı stav systemu. Objekty v ramci systemu mohou dynamicky vznikat azanikat, stejne tak i instance metod. Obrazek 6.2 ukazuje dekompozici procesu systemudo objektu, skladajıcıch se z procesu metod (v casovem diagramu jsou mnoziny okamziku,kdy proces existuje, vyznaceny sedymi oblastmi).

s

o0

o1

o2

o3

p0

p1

p2

p3

s

o1

(a)

(b)

(c)

Obrazek 6.2: Proces systemu (a) a jeho dekompozice do objektu (b). Objekt o0 je hlavnı(prvotnı) objekt, existujıcı po dobu existence systemu. Objekt o1 je dale dekomponovando procesu metod (c), p1 je proces implicitnı metody, existujıcı po dobu existence objektu.

6.1.3 Modelovanı objektu Petriho sıtemi

Objektove orientovany paralelnı system lze podle [Jan98] popsat Petriho sıtemi takto:

1. Kazda metoda je definovana samostatnou vysokourovnovou Petriho sıtı, kterou na-zveme sıt’ metody. Sıt’ definujıcı vlastnı aktivitu objektu (jde o tzv. implicitnı me-todu, ktera je implicitne vyvolana vznikem objektu) nazveme sıt’ objektu. Trıda jespecifikovana jednou sıtı objektu a mnozinou sıtı metod.

2. Sıte metod sdılı mısta sıte objektu (prechody sıte metody majı prıstup k mıstumsıte objektu). Tato mısta hrajı podobnou ulohu, jako instancnı promenne v beznychobjektove orientovanych programovacıch jazycıch.

3. Znacky (tokens) v sıtıch reprezentujı objekty (jsou to reference na objekty).

4. Trıdy lze definovat jako podtrıdy existujıcıch trıd, tedy dedenım. Metody jsou dedenyklasickym zpusobem [GR89], dedicnost reprezentace objektu spocıva v dedenı uzlusıte objektu (hrany sıte jsou povazovany za soucast prechodu).


5. Metody jsou invokovany zasılanım zprav. Zaslanı zpravy muze byt specifikovanoanotacı prechodu, patrıcıho nektere sıti metody nebo sıti objektu.

6. Nektere prechody sıte objektu jsou prohlaseny za specialnı metody (tzv. synchronnıporty), urcene pro pro atomickou synchronnı komunikaci, realizovanou zasılanımzprav ze strazı prechodu.

6.1.4 Interakce objektu – zasılanı zprav

x > 0

x

x

y := x + 1

x

y

y := x + 1

x

y

x > 0

guard

action

Obrazek 6.3: Anotace prechodu – straz a akce.

V objektove orientovanem systemu se veskere vypocty realizujı zasılanım zprav. VOOPN je zasılanı zprav mozne specifikovat v ramci akcı a strazı prechodu (viz obr. 6.3).Adresatem zpravy muze byt bud’ primitivnı objekt (napr. cıslo, retezec apod.), nebo ob-jekt, definovany Petriho sıtemi. Adresat, a tedy odpovıdajıcı metoda, se zjistı v ramcizjist’ovanı proveditelnosti prechodu. Muze jıt o metodu primitivnıho objektu, nebo o me-todu, definovanou Petriho sıtı, nebo o synchronnı port.

Zaslanı zpravy, specifikovane ve strazi prechodu, je interpretovano jako atomicka syn-chronnı interakce, ktera spocıva v invokaci synchronnıho portu (viz dale). Zaslanı zpravy,specifikovane v akci prechodu, je interpretovano jako invokace sıte metody.

6.1.5 Invokace metod objektu zasılanım zprav

Sıte metod, specifikovane jako soucast trıd, jsou urceny k dynamicke instanciaci v reakci naprıchozı zpravy. Prijetı zpravy objektem odpovıda udalosti typy F (fork, vytvorenı novehoprocesu metody). Vysledkem je vytvorenı nove instance (kopie) odpovıdajıcı sıte metody(a prıpadne umıstenı parametru do parametrovych mıst). Tato instance sıte existuje, do-kud nedojde k umıstenı znacky do mısta return. Pak muze dojıt k udalosti typu J (join,ukoncenı procesu metody). Tım dojde k ukoncenı existence instance metody, predanı vy-sledku a provedenı vystupnı casti prechodu, ktery zaslanım zpravy metodu invokoval. Naobrazku je znazornen princip invokace metody. Poznamenejme, ze prechody sıte metodymohou pristupovat k mıstum sıte objektu a ovlivnovat tak stav objektu.

6.1.6 Atomicka synchronnı interakce objektu

Zaslanı zpravy neprimitivnımu objektu ve strazi prechodu je interpretovano jako atomickasynchronnı komunikace. Jde o komunikacnı koncept, umoznujıcı podmınit proveditelnostprechodu soucasnou proveditelnostı jineho (volaneho) prechodu, nazvaneho synchronnıport. Jsou-li oba prechody proveditelne, mohou byt provedeny, a to synchronne, jako jednaatomicka operace. Synchronnı port lze povazovat za specialnı druh metody, kterou lze vo-lat ze straze jineho prechodu zaslanım zpravy. Tento druh komunikace je vhodny pro

6.2. FORMALISMUS OOPN 61

y := o msg: x

msg: arg

arg

return

send

receive

wait

return

argx

y

Obrazek 6.4: Invokace metody.

modelovanı synchronizace aktivit objektu ve vıceurovnovych modelech [?]. Princip ato-micke synchronnı interakce, respektujıcı polymorfismus a navazanı promennych prechodua parametru synchronnıho portu je znazornen na obrazku 6.5.

o msg: xmsg: arg

x = arg

Obrazek 6.5: Atomicka synchronnı interakce objektu.

Synchronnı port, ktery jen testuje, ale nemodifikuje obsah mıst odpovıdajıcı sıte ob-jektu, nazyvame predikat. V [Maz08] byl pro potreby citelnejsıho modelovanı do OOPNzaveden take negativnı predikat. Analogicky k not v Prologu, negativnı predikat selze,pokud stejne specifikovany pozitivnı predikat uspeje a naopak. Pomocı negativnıho predi-katu lze testovat neprıtomnost znacky v mıste. Jde o zobecnenı konceptu inhibicnı hranyv Petriho sıtıch.

6.2 Formalismus OOPN

Formalismus OOPN je podrobne popsan a formalne definovan v [Jan98]. Tamtez je po-psana i jeho konkretnı implementace, jazyk a system PNtalk. Vzhledem k pomerne roz-sahlosti originalnı definice jsou dale uvedeny jen nejdulezitejsı pojmy a jejich souvislosti,ktere jsou nutne pro pochopenı nekterych aplikacı v navazujıcıch kapitolach. Zamerıme sepritom na strukturu OOPN, na reprezentaci stavu a na dynamiku OOPN.

6.2.1 Struktura OOPN

Objektove orientovana Petriho sıt’ [Jan98] je definovana jako trojice OOPN = (Σ, c0, oid0),kde Σ je system trıd, c0 je pocatecnı trıda a oid0 je jmeno prvotnıho objektu, ktery jeinstancı c0. System trıd zahrnuje mnozinu trıd, hierarchicky usporadanou podle relacededicnosti. Kazde trıde prıslusı mnozina jmen instancı (domena) a je pro ni definovanastruktura instancı. Specifikace struktury instancı trıdy zahrnuje sıt’ objektu, mnozinu sıtımetod, mnozinu synchronnıch portu, mnozinu selektoru zprav a bijekci mnoziny selektoruzprav na mnozinu, obsahujıcı metody a synchronnı porty. System trıd musı splnovat jiste


podmınky umoznujıcı dedicnost a zarucujıcı, ze pro kazdou instanci sıte lze urcit odpovıda-jıcı sıt’ a trıdu, ve ktere byla tato sıt’ definovana. Anotace Petriho sıtı jsou specifikovanyinskripcnım jazykem umoznujıcım pracovat take s primitivnımi objekty, jako jsou cısla,retezce atd.

Prıklad Prıklad OOPN je na obrazku 6.6. Obsahuje trıdy C0 a C1. Trıda C0 obsahujejen sıt’ objektu. Trıda C1 obsahuje sıt’ objektu, obsahujıcı mısto p a prechod t, a daleobsahuje synchronnı port state: a metody waitFor: a reset. Poznamenejme, ze tentoprıklad nemodeluje nic smysluplneho, pouze demonstruje formalismus OOPN.

x < y

y := x + 1

waitFor: xx

xx

t1

t2

#fail #success

y0

x

0p

xy

return

o

o

o

(x,y)

(x,#fail)

x

xy := o waitFor: xt2

t3

o := C1 new

t1

p2

p4

p12‘#e

1,2 p3

t4

o state: x. x >= 3o reset

#e

state: x

x

x

0

#e

return

reset

t

t

C1 is_a PNC0 is_a PN

Obrazek 6.6: Prıklad OOPN.

6.2.2 Reprezentace stavu OOPN

Stav OOPN je definovan jako system objektu. Objekt je definovan jako system instancı sıtı,obsahujıcı v danem stavu prave jednu instanci sıte objektu a mnozinu instancı sıtı metod,ktere jsou v danem stavu rozpracovany. Kazda instance sıte je dvojice (id, m), kde id jejmeno instance sıte a m je znacenı teto sıte (obsahuje znacenı mıst i prechodu). Znacenım kazdemu mıstu v instanci sıte prirazuje multimnozinu znacek, identifikujıcıch objekty(primitivnı, neprimitivnı i trıdy) a kazdemu prechodu mnozinu invokacı (rozpracovanychmetod). System objektu je uzavreny, tj. zarucuje, ze znacenı vsech instancı sıtı ve vsechobjektech referencujı pouze instance sıtı obsazene v systemu objektu. Take je zaruceno, zeneobsahuje objekty, ktere by nebyly tranzitivne dostupne z prvotnıho objektu.

Pocatecnı system objektu objektove orientovane Petriho sıte OOPN = (Σ, c0, id0) ob-sahuje jediny objekt, identifikovany jmenem id0, ktery je instancı pocatecnı trıdy c0. Zna-cenı jeho sıte objektu odpovıda pocatecnımu znacenı teto sıte, specifikovane ve trıde c0.

Prıklad Uvazujme OOPN specifikovanou trıdami na obrazku 6.6. Pocatecnı stav tetoOOPN je definovan stavem prvotnıho objektu (instance hlavnı trıdy). Obsahuej poratecnıznacenı sıte objektu trıdy C0. Objekt je identifikovan tımtez jmenem jako instance jehosıte objektu, a sice id0. Pocatecnı stav oznacıme s0 a muzeme ho specifikovat tabulkou6.1.

6.2. FORMALISMUS OOPN 63

s0 id0

id0

C0 object net p1 2‘#e

p2 empty

p3 1, 2

p4 empty

t1 empty

t2 empty

t3 empty

Tabulka 6.1: Prıklad systemu objektu – pocatecnı stav s0.

6.2.3 Dynamika OOPN

Dynamika OOPN je definovana pocatecnım systemem objektu a pravidly specifikujıcımiproveditelnost a provadenı prechodu v instancıch sıtı. Provedenı prechodu je udalost, for-malizovana jako ctverice (e, id, t, b), kde e specifikuje typ udalosti (A, N , F nebo J , viz6.1.2, str. 59), jmeno id identifikuje instanci sıte, ve ktere k udalosti doslo, t identifikujeprechod jehoz provedenı udalost zpusobilo a b je navazanı promennych prechodu t. Vyskytudalosti (e, id, t, b) ve stavu S zpusobı zmenu tohoto stavu na S′, coz oznacujeme jako kroka zapisujeme S[e, id, t, b〉S′.

Prechod muze potencialne byt proveden ctyrmi zpusoby, ktere odpovıdajı ctyrem ty-pum udalostı z 6.1.2. Prechod muze byt pro jiste navazanı promennych A-proveden, po-kud zaslanı zpravy vede na primitivnı vypocet, muze byt N-proveden, pokud jde o zaslanızpravy new trıde, muze byt F-proveden, pokud adresatem zpravy je objekt, ktery ma prı-slusnou metodu definovanu Petriho sıtı, a muze byt J-proveden, pokud metoda invokovanapredchozım F-provedenım tohoto prechodu prave skoncila. A-provedenı prechodu odpo-vıda provedenı prechodu ve standardnı Petriho sıti, N-provedenı prechodu ma za nasledekvytvorenı noveho objektu, tj, invokaci prıslusne sıte objektu, F-provedenı ma za nasledekinvokaci prıslusne sıte metody a uplatnı se jen vstupnı hrany prechodu, J-provedenı maza nasledek odstranenı prıslusne instance sıte metody a uplatnı se jen vystupnı hrany pre-chodu. Vzhledem k tomu, ze mezi F- a J-provedenım si prechod musı pamatovat prıslusnouinvokaci, byl zaveden pojem znacenı prechodu. Je to funkce, prirazujıcı kazdemu prechodumnozinu invokacı, tj. dvojic (id, b), kde id je identifikace (jmeno) vytvorene instance sıtea b je navazanı promennych prechodu pri jeho F-provedenı.

Udalosti tvaru (e, id, t, b) postupne modifikujı stav systemu. V jednom okamziku (v da-nem stavu) muze potencialne nastat nekolik udalostı (je zde potencialne nekolik ruzneproveditelnych prechodu), ze kterych se nedetrministicky vybere a uskutecnı jen jedna.

Prıklad Uvazujme OOPN specifikovanou trıdami na obrazku 6.6 a pocastecnı stav z6.2.2. Proved’me sekvenci kroku

s0 [(N, id0, C0.t1, ())〉s1 [(F, id0, C0.t2, (x = 1, o = id1))〉s2 [(F, id0, C0.t2, (x = 2, o = id1))〉s3 [(A, id1, C1.t, (x = 0))〉s4 [(A, id2, C1.waitFor : .t2, (x = 1))〉 s5.


s5 id0 id1

id0 id1 id2 id3

C0 object net p1 #e

p2 id1

p3 empty

p4 empty

t1 empty

t2 (id2, (x, 1), (o, id1)), (id3, (x, 2), (o, id1))t3 empty

C1 object net p 0

t empty

waitFor: x empty 2

return #success empty

t1 empty empty

t2 empty empty

Tabulka 6.2: Prıklad systemu objektu – stav s5.

Vysledny stav s5 je specifikovan tabulkou 6.2. Stav s5 obsahuje dva objekty identifikovanejmeny id0 a id1. Znacenı nekterych mıst a prechodu objektu id0 se zmenilo. Novy objektid1 obsahuje instance sıtı identifikovane jako id1, id2 a id3. Instance sıtı s jmeny id2 a id3jsou invokacemi metody waitFor:, vytvorene provedenım prechodu t2 v objektu id1.

6.3 Simulator OOPN

Simulace OOPN spocıva v opakovanem provadenı kroku simulace. V ramci simulacnıhokroku se provede testovanı proveditelnosti prechodu v jednotlivych instancıch sıtı, tvorıcıchsystem objektu. Z proveditelnych prechodu je pak vybran jeden a proveden.

Pro praci se simulacnım casem je vsak treba tento koncept upravit a zavest moznostspecifikovat cekanı. Stejne jako ostatnı aktivity, tok casu se v OOPN specifikuje zasılanımzprav v ramci akcı prechodu. Cekanı v simulacnım case je specifikovano akcı tvaru selfhold: t. Provedenı prechodu je v takovem prıpade pozdrzeno (v simulacnım case) podefinovanou dobu a teprve po jejım uplynutı je provedena vystupnı cast prechodu.

Planovanı udalostı je v simulatoru OOPN realizovano kalendarem. Prubeh simulace jenasledujıcı:

1. Dokud existuje proveditelny prechod, provede se. Pri provadenı prechodu se do ka-lendare umist’ujı planovane udalosti ve tvaru (cas, udalost). Jde o udalosti typu J(dokoncenı rozpracovaneho prechodu), ktere se planujı v dusledku cekanı, specifiko-vaneho akcı self hold: t.

2. Nenı-li zadny prechod proveditelny, dojde k posuvu casu podle nejblizsı planovaneudalosti a udalost (t.j. dokoncenı cekajıcıcho prechodu) se provede. Pokracuje sebodem 1.

Simulator OOPN pripoustı take zaslanı zpravy self hold: t ve strazi prechodu. Vtakovem prıpade je straz splnena (a prechod se muze provest), pokud je prechod nepretrziteproveditelny po specifikovanou dobu.

6.4. ZAPOUZDRENI OOPN DO DEVS 65

6.4 Zapouzdrenı OOPN do DEVS

Simulator OOPN muzeme popsat, resp. zapouzdrit jako system s diskretnımi udalostmiv souladu s definicı DEVS. To nam umoznı specifikovat komponenty DEVS formalismemOOPN. Princip zapouzdrenı OOPN do DEVS tkvı v tom, ze dve disjunktnı podmno-ziny mnoziny mıst prohlasıme za vstupnı, resp. vystupnı, asynchronnı porty a definujemereprezentaci stavu zapouzdrujıcıho DEVS a funkce zapouzdrujıcıho DEVS takto:

• Mnozina stavu je mnozina systemu objektu, dosazitelnych z pocatecnıho systemuobjektu.

• Vstupnı porty odpovıdajı vstupnım asynchronnım portum hlavnıho objektu. Vy-stupnı porty odpovıdajı vystupnım asynchronnım portum hlavnıho objektu. Hod-noty vstupu a vystupu patrı do mnoziny primitivnıch objektu OOPN.

• Internı prechodova funkce δint realizuje provedenı jedne udalosti v OOPN, planovanena aktualnı cas. V prıpade konfliktu se vybere jedna udalost pomocı preferencnıfunkce select, definovane podobne, jako v prıpade slozenych modelu DEVS (vyberejeden z libovolne podmnoziny mnoziny vsech modu prechodu2).

• Funkce posuvu casu ta vracı dobu, za kterou ma dojıt k nasledujıcı planovane uda-losti v OOPN, tj. bud’ 0, existuje-li alespon jeden proveditelny prechod v aktualnımcase, nebo (tc−t), kde tc je cas nejblizsı planovane udalosti v kalendari a t je cas aktu-alnı, je-li v kalenari alespon jedna polozka. Je-li kalendar prazdny, ta vracı hodnotu∞ (system je pasivovan).

• Externı prechodova funkce δext modifikuje stav vstupnıch asynchronnıch portu hlav-nıho objektu pridanım objektu ze vstupnıch portu DEVS.

• Vystupnı funkce λ mapuje (z implementacnıho hlediska presune) obsah vystupnıchasynchronnıch portu hlavnıho objektu do vystupnıch portu DEVS.

6.5 Dynamicke aplikacnı rozhranı simulatoru

Simulator OOPN muze byt realizovan souladu s principy otevrene abstraktnı architekturypro simulaci vyvıjejıcıch se systemu, popsane v kapitole 4. Dynamicke aplikacnı rozhranısimulatoru OOPN pak umoznuje manipulovat se strukturou trıd i jejich instancı, s meto-dami i s jejich invokacemi. Manipulace spocıva ve ctenı struktury a stavu a v modifikacistruktury a stavu jednotlivych Petriho sıtı. Je-li vysledkem dynamicke manipulace konzis-tentnı system objektu dle definice [Jan98], simulace po tomto zasahu korektne pokracuje,v opacnem prıpade je simulace ukoncena v dusledku chyby.

Trıdy OOPN jsou v PNtalku globalne dostupne jmenem. Prıstup k metodam uvnitrtrıdy je mozny prostrednitvım jmena (selektoru odpovıdajıcı zpravy). Sıt’ objektu je do-stupna pod jmenem #object. Uzly Petriho sıtı jsou take prıstupne prostrednictvım svychjmen. Trıdy, metody, mısta a prechody rozumenı zpravam, ktere odpovıdajı metaoperacımpro inspekci a editaci.

2Mod prechodu je varianta provedenı, zahrnujıcı navazanı promennych, pro ktere je prechod provedi-telny.


Podobne lze pristupovat k reprezentaci aktualnıho stavu. Jde o system objektu, zapouz-drujıcıch mnoziny procesu. Hlavnı objekt je v PNtalku globalne prıstupny pod jmenem#main. Objekty jsou dostupne prostrednictvım referencı, ktere se vyskytujı v podobe zna-cek v mıstech Petriho sıtı. Procesy metod jsou provazany relacı invokace do hierarchickestruktury, ktera ma koren v procesu sıte hlavnıho objektu. Tato hierarchie procesu je ob-vykle vychodiskem pro navigaci ve strukture stavu OOPN. Jednotlive slozky stavu lze cısti editovat pouzitım adekvatnıch metaoperacı.

Integrace OOPN do prostredı SmallDEVS Interpret OOPN (PNtalk) s dynamic-kym aplikacnım rozhranım je intergrovan do prostredı SmallDEVS (popsaneho v kapitole5), kde umoznuje specifikovat atomicke komponenty DEVS pomocı OOPN. Prıstup k prv-kum OOPN je mozny prostrednictvım prohlızece MyRepository (viz kap. 5). Trıdy OOPNjsou v MyRepository prıstupne ve slozce PNtalk. Na dalsı urovni hierarchie jsou metody.Jak trıdy, tak metody lze editovat odpovıdajıcımi vizualnımi nastroji. Procesy OOPN jsouv MyRepository prıstupne jako hierarchicky nizsı polozky pod komponentou DEVS, spec-fikovanou formalismem OOPN. Hierarchicky nizsı uroven trvorı procesy vytvorene procesyna urovni vyssı. Stav procesu je k dispozici jako znacenı odpovıdajıcı Petriho sıte.

6.6 Shrnutı

OOPN lze pouzıt pro specifikaci systemu s diskretnımi udalostmi v souladu s definicıDEVS dıky kompatibilnımu zapouzdrenı. V navaznosti na definici otevrene abstraktnı ar-chitektury pro simulaci vyvıjejıcıch se systemu, ktera byla uvedena za pouzitı formalismuDEVS, lze definovat dynamicke aplikacnı rozhranı i pro simulator OOPN. Praktickou im-plementacı je system PNtalk/SmallDEVS, ktery umoznuje atomicke komponenty DEVSspecifikovat formalismem OOPN. Specifikace atomickych komponent slozeneho modelu po-mocı OOPN prinası vyssı uroven popisu a sugestivnı vizualizovatelnost. AplikovatelnostOOPN a DEVS v simulacnım modelovanı a navrhu systemu je demonstrovana nasledujı-cımi prıpadovymi studiemi.

Kapitola 7

Prıpadova studie: Reflektivnısimulator DEVS

Uzitecnou vlastnostı modelovacıho formalismu je schopnost definovat vlastnı semantiku.Prıkladem muze byt reflektivnı simulator DEVS. Je to simulator DEVS specifikovany jakoDEVS.

Root Coordinator

Coordinator


Simulator Simulator

Coupled Model

Coupled Model Atomic Model

Atomic Model Atomic Model

Obrazek 7.1: Mapovanı mezi modely a simulatory

Pripomenme si nejprve princip hierarchicke simulace DEVS. Kazdemu modelu odpo-vıda prıslusny simulator a na vrcholu hierarchie je korenovy simulator (vz obr. 7.1). Prirealizaci reflektivnıho simulatoru lze vyjıt ze specifikace abstraktnıho simulatoru DEVS.Tu je vsak treba prizpusobit charakteru cıloveho implementacnıho formalismu. Originalnıabstraktnı simulator DEVS podle [ZKP00] je specifikovan s ohledem na implementaciv beznem prog. jazyce a proto obsahuje referenci na nadrazeny simulator a komunikujeprımym predavanım zprav adresatovi (jde o synchronnı komunikaci). Formalismus DEVSnepouzıva reference, komponenty o sobe vzajemne nevı, jen nadrazena komponenta znajejich propojenı (komponenty jsou pojmenovane a propojenı je definovano s vyuzitımjmen komponent a portu). Algoritmy a struktura simulatoru a koordinatoru proto musıbyt upraveny pro takto volne vazane hierarchicky organizovane komponenty komuniku-jıcı asynchrone predavanymi zpravami. Lze pritom vyjıt napr. z [Van00] (podobne jsouspecifikovany algoritmy simulatoru v kap. 2). V nasem prıpade pouzijeme zpravy tvaru(msg, from/to, t). Obsahujı oproti originalu navıc jmena odesilatele, resp. prıjemce. Toto

68 KAPITOLA 7. REFLEKTIVNI SIMULATOR DEVS

adresovanı umoznı pripojit vıce komponent na jeden port, coz zjednodusı propojovanı(pridavanı dedikovanych portu pro kazdou komponentu kompozitu by model ponekudzkomplikovalo).

Simulator atomickeho modelu Simulator atomickeho modelu specifikujeme jako sys-tem

SM = (X, S, Y, δint, δext, λ, ta, M).

Mnozina X obsahuje vsechny zpravy tvaru (i, to, t), (x, to, t), (∗, to, t). Mnozina Y obsa-huje vsechny zpravy tvaru (y, from, tn), (done, form, tn), (log, from, tn). Mnozina S jestrukturovana do promennych tlast, tnext, y, (s, e). Funkce δint, δext, λ, ta jsou definovanytak, aby system reagoval na vstupnı udalosti podle specifikace uvedene v kap. 2 v zavis-losti na specifikaci atomickeho modelu M = (X, S, Y, δint, δext, λ, ta), definovaneho taktezv kap. 2.

Simulator slozeneho modelu Simulator slozeneho modelu (koordinator) specifikujemejako system

SN = (X, S, Y, δint, δext, λ, ta, N),

Mnozina X obsahuje vsechny zpravy tvaru (i, to, t), (x, to, t), (∗, to, t), (y, from, tn), (done,from, tn). Mnozina Y obsahuje vsechny zpravy tvaru (y, from, tn), (done, form, tn),(i, to, t), (x, to, t), (∗, to, t), (log, from, tn). Mnozina S je strukturovana do promennychtlast, tnext, y, eventList receivers, activeChildren (viz algoritmus simulatoru v kap.2). Funkce δint, δext, λ, ta jsou definovany tak, aby system reagoval na vstupnı udalostipodle specifikace uvedene v kap. 2. v zavislosti na specifikaci slozeneho modelu N =(X, Y, D, Md, EIC, EOC, IC, select), definovaneho taktez v kap. 2.

Korenovy simulator Korenovy simulator specifikujeme jako system

SR = (X, S, Y, δint, δext, λ, ta)

Mnozina X obsahuje vsechny zpravy tvaru (start), (stop), (reset), (stopT ime, t), (done,from, tn). Mnozina Y obsahuje vsechny zpravy tvaru (i, to, t), (∗, to, t), (log, from, tn).Mnozina S je strukturovana do promennych, reprezentujıcıch stav simulace, aktualnı cast a cas nasledujıcıc udalostı tnext. Funkce δint, δext, λ, ta jsou definovany tak, aby systemreagoval na vstupnı udalosti provadenım jednotlivych kroku simulace, prıpadne zmenoustavu (zastavenı spustenı) a zmenou paramertu simulace.

Reflektivnı simulator Mejme slozeny model, obsahujıcı generator a procesor, viz obr.7.2. Kompletnı reflektivnı simulator tohoto modelu je pak specifikovan jako slozeny model,zobrazeny na obr. 7.3. Simulator simuluje generator, Simulator2 simuluje processor,Coordinator simuluje cely model a RootSolver rıdı celou simulaci.

Realizace Uvedeny reflektivnı simulator lze pro dany model vygenerovat staticky: Nazaklade modelu se jednou naraz zkonstruuje cela struktura simulatoru pomocı kompila-toru DEVS do DEVS. Takto lze pracovat s DEVS podle puvodnı (staticke) definice. Jinoumoznostı je v reflektivnım simulatoru zprıstupnit kompletnı aplikacnı rozhranı pro dyna-micke vytvarenı, inspekci a editaci modelu (a jejich simulatoru). Pak mame na zacatku k

69

Obrazek 7.2: Model generatoru a procesoru

Obrazek 7.3: Model simulatoru modelu generatoru a procesoru

dispozici pouze korenovy simulator s prazdnym modelem. Dıky zprıstupnenym operacımlze pak dynamicky vytvaret, editovat a manipulovat s modely a s celou simulacı.

Prakticky vyznam reflektivnı simulace DEVS Lze overit funkcnost a analyzovatvykonnostnı aspekty ruznych modifikacı simulatoru DEVS.

Pouzitı jinych formalismu Uvedeny reflektivnı simulator DEVS pouzıva tzv. meta-cirkularnı architekturu. To znamena, ze pro domenovou uroven i pro metauroven je pouzittentyz formalismus. Potencialne je mozne pro ruzne urovne pouzıt ruzne formalismy, resp.jazyky. Nynı zvazıme moznost pouzitı jineho formalismu, konkretne OOPN. Vzhledem ktomu, ze jde o velmi vysokourovnovy formalismus s sirokymi vyjadrovacımi schopnostmi(jako univerzalnı programovacı jazyk) s moznostı komponentıho modelovanı konformnıhos konceptem slozenych modelu DEVS, nebudeme implementovat hierarchicky simulatorDEVS pomocı OOPN (prestoze bychom to mohli udelat analogicky k uvedene implemen-taci simulatoru DEVS pomocı DEVS), ale pouzijeme prıme mapovanı formalismu DEVSdo formalismu OOPN. Mapovanı atomickeho modelu DEVS do OOPN je ukazano naobrazku 7.4. Mechanismus zpracovanı vstupu, modifikace stavu a generovanı vystupu jespecifikovan vysokourovnovou Petriho sıtı. Kazdy konkretnı model, implementovany jakopodtrıda AtomicDEV S, specifikuje (1) funkce DEVS, ktere jsou realizovany odpovıdajı-

70 KAPITOLA 7. REFLEKTIVNI SIMULATOR DEVS

deltaExtS: s E:e: X: x

AtomicDEVS is_a PN

x

yy := self lambdaS: s

t := self time.newS := self deltaExtS: x E: (self time - lastT) X: x

self hold: (self taS: s)

deltaIntS: s

lambdaS: s taS: s

t := self time. newS := self deltaIntS: s

s

lastT

s

snewS

newS

s

s

. .

.

. ...

.

.

x

x

x

xx

x

x x

x

y

.

lastT

lastTt

t

Obrazek 7.4: DEVS v OOPN

cımi metodami v OOPN, a (2) pocatecnı znacenı mısta s, ktere obsahuje pocatecnı stavmodelu.

Tento prıstup je mozne temer beze zmeny pouzıt pro mapovanı DEVS do CPN (Co-loured Petri nets), implementovanych nastrojem CPNTools a vyuzıt jeho konceptu hierar-chickych mıst a prechodu pro realizaci slozenych modelu. Takto lze simulovat a analyzovatmodely na bazi DEVS s vyuzitım standardnıho nastroje pro vysokourovnove Petriho sıte.

Kapitola 8

Prıpadova studie: Simulacesimulujıcıho systemu

Simulujıcı system je system, jehoz soucastı je simulace. Simuluje-li system sam sebe apouzıva-li vysledky vlastnı simulace pro modifikaci sveho vlastnıho chovanı v budoucnu,jde o reflektivnı simulaci.

Do trıdy simulujıcıch systemu typicky patrı systemy, jejichz soucastı je rozhodovacıproces, obsahujıcı simulaci. Takove systemy se v praxi vyskytuji pomerne casto. Stacı sipredstavit situaci [Skl97], kdy skupina expertu navrhne mnozinu moznych resenı danehoproblemu v ramci sloziteho systemu. Pritom dusledky jednotlivych resenı nenı mozne ana-lyticky zjistit ani jednoduse otestovat. Jedinym resenım je pro vsechny navrhy expertuprovest simulacnı experimenty, jejich vysledky porovnat a pote provest rozhodnutı. Si-mulace simulujıcıch systemu pak dava smysl jako soucast procesu rozhodovanı problemu,tykajıcıch se simulujıcıch systemu. Jako prıklad uvedeme optimalizaci poctu otevrenychprepazek v bance v zavislosti na zmenach pravdepodobnostnıho rozlozenı prıchozıch kli-entu v prubehu dne.

8.1 Prıklad vnorene simulace: System hromadne obsluhy,jehoz cast je optimalizovana opakovanou vnorenou si-mulacı

Obrazek 8.1 ukazuje system, ktery chceme simulovat. Jde velmi zjednodusenou abstrakcihypoteticke banky, kde klienti nejprve cekajı ve fronte, by byli obslouzeni urednıkem (teller)zpracovavajıcım jejich pozadavky. Pote je (po cekanı v dalsı fronte) obslouzen urednıkemna pokladne (cashier). Pravdepodobnostnı rozlozenı doby mezi prıchody klientu a dobytrvanı obema typy urednıku jsou znama. Predpokladejme, ze banka ma k dispozici nekolkurednıku, kterı jsou schopni pracovat na libovolne z obou pozic. Rızenı banky chce opti-malizovat pridelenı urednıku k obema typum prepazek v ruznych castech dne, ktere se lisıcetnostı prıchodu klientu do banky. Rozlisujı se tri obdobı, ktera nazveme ”busy”, ”idle”a ”very busy”. Pro nalezenı nejlepsı strategie prrazenı urednıku k prepazkam je pouzitasimulace (je-li system simulovan, jde o vnorenou simulaci): Na zacatku kazde periody seopakovane provede simulace prvnı casti systemu (tj. fronty s mnozinou prepazek prvnıhotypu – teller) pro ruzne pocty urednıku (tellers) v rozsahu od 1 do celkoveho poctu dostup-nych urednıku (10). Na zaklade vysledku jednotlivych simulacı vedenı banky urcı pocty

72 KAPITOLA 8. SIMULACE SIMULUJICIHO SYSTEMU

Obrazek 8.1: System hromadne obsluhy se dvema frontami a obsluznymi linkami (prevzatoz [Skl97])

Obrazek 8.2: Zakladnı idea vnorene simulace (prevzato z [Skl97])

8.2. MODEL S VNORENOU SIMULACI V JAZYCE SIMULA 73

urednıku pro prepazky prvnıho typu (tellers) a druheho typu (cashiers).Pro jednoduchost v nasem simulacnım modelu ponechame vyber nejlepsı varianty na

interaktivnım zasahu uzivatele – program nabıdne moznosti prerozdelenı urednıku (spolus odpovıdajıcımi simulacnımi vysledky), z kterych uzivatel jednu vybere. Rozhodovacımkriteriem je prumerny cas straveny klientem v bance (resp. v jejı prvnı casti, tj. ve frontea u prepazky prvnıho typu).

Pro moznost prımeho porovnanı uvedeme dve implementace modelu tehoz systemu,realizovane v ruznych simulacnıch jazycıch. Jednım z nich je klasicky jazyk pro simulacnımodelovanı (SIMULA), druhy je experimentalnı vizualnı jazyk pro paralelnı objektoveorientovane modelovanı, zalozeny na Petriho sıtıch (PNtalk). Nejprve uvedeme kod simu-lujıcıho modelu v jazyce SIMULA, prevzaty z [Skl97].

8.2 Model s vnorenou simulacı v jazyce SIMULA [Skl97]

Model v jazyce SIMULA vyuzıva toho, ze trıda Simulation definuje simulacnı cas. Kazdainstance teto trıdy (nebo jejı podtrıdy) tedy definuje samostatny svet s vlastnım casem.Metoda Hold() zpusobı cekanı v simulacnım case prıslusne instance trıdy Simulation.SIMULA umoznuje definovat bloky (Begin...End) dedıcı od existujıcıch trıd. Naprıkladkonstrukce Simulation Begin...End definuje blok, dedıcı vlastnosti definovane trıdou Si-mulation. Prıslusny anonymnı objekt (instance nepojenovane trıdy, odpovıdajıcı bloku),se vytvorı (inicializuje) v okamziku, kdy ma dojıt k zahajenı vyhodnocovanı bloku. Vnoro-vanı simulacı v jazyce SIMULA je tedy mozne velmi prımocare definovat vnorenım blokudedıcıch od trıdy Simulation.1 Aby si ctenar ucinil dokonalou predstavu, nasleduje kom-pletnı kod simulacnıho modelu s vnorenou simulacı, predvzaty z [Skl97].

! NESTED Simulation using the Simula ’ s class SIMULATION ;! ;! The example is a model of a bank. Customers are f i r s t ;! served by tel lers , then by cashiers . ;! The input rate changes in three periods : there is a busy ;! period , then an idle period and again a busy one. ;! For each period the repeated inner simulation experiment ;! simulates the f i r s t queue for the particular input rate ;! and for various numbers of servers . Then it shows the ;! results (average time spent at the f i r s t server) and ;! prompts the user for the number of te l lers and the number;! of cashiers . Tellers always finish a service that has ;! already started . The simulation should find the ;! time customers spend in the bank (average and maximum) ;! for various numbers of clerks in the three periods . ;! ;

Simulation Begin! Global variables : ;

1V ostatnıch trıdne zalozenych objektove orientovanych jazycıch, ktere neumoznujı blokum dedit (cozje drtiva vetsina programovacıch jazyku), je treba pro vnorene simulace explicitne prıslusnou instancitrıdy Simulation (nebo jejıho ekvivalentu, pokud je v danem prostredı k dispozici) vytvorit. Princip ovsemzustava zachovan.


Integer Period ,Trial ; ! Period , Trial number;Real Array MinInt,MaxInt(1:3); ! Min and Max intervals ;Real Array Duration(1:3); ! Duration of periods [min] ;Ref(Head) Queue1,Queue2; ! The two queues ;Integer MaxClerks, Tellers , Cashiers ; ! Total numbers;Integer BusyTellers , BusyCashiers ; ! Numbers of working clerks ;Real S1Mean, S1Std, S2Mean, S2Std; ! Random normal servers ;Integer SeedG, SeedS1, SeedS2; ! Seeds of the random generators ;Long Real TotalTime, MaxTime; ! Variables for statist ics ;Integer CustomersOut; ! Number of served customers ;

Process Class Generator ;Begin

While true do begin! Interval between arrivals : ;

Hold(Uniform(MinInt(Period) ,MaxInt(Period) ,SeedG)) ;Activate New Customer(Time) ;

End While;End of Generator ;

Process Class Customer(Arrival ) ; Real Arrival ;Begin

Ref(Customer) Next;Real Spent;

I f (not Queue1.Empty) or (BusyTellers >= Tellers ) thenWait(Queue1) ; ! Has to wait in Queue1;

! Service can start ;BusyTellers← BusyTellers + 1;Hold(Normal(S1Mean, S1Std, SeedS1)) ; ! This is the te l ler service ;BusyTellers← BusyTellers − 1;

I f (not Queue1.Empty) and (BusyTellers < Tellers ) then beginNext :− Queue1. First ;Next.Out; ! First from Queue1 served ;Activate Next after Current ;

End If ;

I f (not Queue2.Empty) or (BusyCashiers >= Cashiers) thenWait(Queue2) ; ! Has to wait in Queue2;

! Service can start ;BusyCashiers← BusyCashiers + 1;Hold(Normal(S2Mean, S2Std, SeedS2)) ; ! This is the cashier service ;BusyCashiers← BusyCashiers − 1;

I f (not Queue2.Empty) and (BusyCashiers < Cashiers) then beginNext :− Queue2. First ;Next.Out; ! First from Queue2 served ;Activate Next after Current ;

End If ;

CustomersOut← CustomersOut + 1;Spent←Time − Arrival ;

8.2. MODEL S VNORENOU SIMULACI V JAZYCE SIMULA 75

TotalTime← TotalTime + Spent;I f Spent > MaxTime then MaxTime← Spent;

End of Customer;

Procedure Report ; ! Experiment evaluation ;Begin

OutText(” ∗∗∗ Report on external simulation ∗∗∗”); OutImage;OutInt(CustomersOut,6) ; OutText(” customers ready at time ”) ;OutFix(Time,2 ,10); OutImage;OutText(”Average time in system: ”) ;OutFix(TotalTime/CustomersOut,2 ,10); OutImage;OutText(”Maximum time in system: ”) ;OutFix(MaxTime,2 ,10); OutImage;

End of Report ;

! MAIN program body;

SeedG ← 11; ! Seeds of random variables ;SeedS1← 13;SeedS2← 17;MinInt(1) ← 1; MaxInt(1) ← 4; ! Min and Max intervals ;MinInt(2) ← 2; MaxInt(2) ← 9;MinInt(3) ← 1; MaxInt(3) ← 3;Duration(1) ← 120; ! Duration of periods ;Duration(2) ← 240;Duration(3) ← 120;MaxClerks ← 6;S1Mean← 6; ! Random normal servers ;S1Std ← 1;S2Mean← 8;S2Std ← 2;Queue1 :− New Head;Queue2 :− New Head;Period← 1;Activate New Generator ;

For Period←1 step 1 until 3 do begin

Real Array TimeSpent(1:MaxClerks) ;

OutText(” ∗∗∗ Results of internal simulation ∗∗∗ Period ”) ;OutInt(Period ,1) ; OutImage;OutText(” Tellers Average time spent”) ; OutImage;

For Trial←1 step 1 until MaxClerks do! ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ;Simulation Begin

! Internal Global variables : ;Real TrialDuration ; ! Internal experiment [min] ;Ref(Head) Queue; ! The queue;Integer Servers ; ! Total number;Integer BusyServers ; ! Numbers of working clerks ;Integer TrialSeedG,TrialSeedS ; ! Seeds of the random generators ;


Long Real TotTime; ! Variables for statist ics ;Integer CustOut; ! Number of served customers ;

Process Class IGenerator ;Begin

While true do beginHold(Uniform(MinInt(Period) ,MaxInt(Period) ,TrialSeedG)) ;Activate New ICustomer(Time) ; ! Interval between arrivals : ;

End While;End of IGenerator ;

Process Class ICustomer(Arrival ) ; Real Arrival ;Begin

Ref(ICustomer) Next;

I f not Queue.Empty or (BusyServers >= Servers) thenWait(Queue) ; ! Has to wait in Queue;

! Service can start ;BusyServers← BusyServers + 1;Hold(Normal(S1Mean, S1Std, TrialSeedS)) ; ! Teller ’ s service ;BusyServers← BusyServers − 1;

I f not Queue.Empty then beginNext :− Queue. First ;Next.Out; ! First from Queue served ;Activate Next after Current ;

End If ;

CustOut←CustOut + 1;TotTime←TotTime + Time − Arrival ;

End of ICustomer;

! Internal MAIN program body;

TrialSeedG← 7; ! Seeds for random variables ;TrialSeedS← 23;Servers← Trial ;TrialDuration← 600;Queue :− New Head;Activate New IGenerator ;Hold(TrialDuration ) ; ! Internal experiment duration ;TimeSpent(Trial) ←TotTime/CustOut;OutInt(Trial ,13);OutFix(TimeSpent(Trial ) ,3 ,23); OutImage;

End of internal simulation ;! ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ;

OutText(”Enter the number of te l l ers : ”) ; OutImage;Tellers ← InInt ;OutText(”Enter the number of cashiers : ”) ; OutImage;Cashiers← InInt ;Hold(Duration(Period )) ;

8.3. MODEL S VNORENOU SIMULACI V JAZYCE PNTALK 77

Report ;OutText(”Press Enter to Continue. ”) ; OutImage; InImage;

End For;End of program; 8.3 Model s vnorenou simulacı specifikovany objektove ori-

entovnymi Petriho sıtemi v jazyce PNtalk

Nynı uvedeme model tehoz systemu, specifikovany objektove orientovanymi Petriho sı-temi (OOPN) v jazyce PNtalk. Vzhledem k prevazne vizualnımu charakteru jazyka PN-talk je styl programovanı vyrazne odlisny od bezneho textoveho, avsak princip, pouzity vpredchozı casti, zustava zachovan. Odlisnosti oproti modelu v jazyce SIMULA jsou danepouzitym jazykem a tım, ze model pro vnorenou simulaci je smysluplne pouzıt jako nad-trıdu vnejsıho modelu. Model je specifikovan dvema trıdami, BankModel a Bank, pricemzBankModel specifikuje zjednoduseny model banky pro vnorenou simulaci (tj. frontu a ured-nıky jednoho typu a Bank specifikuje model celeho systemu se dvena frontami a dvematypy urednıku. Model BankModel je zjednodusenım modelu Bank, proto je vyhodne trıduBank specifikovat jako podtrıdu trıdy BankModel. Vyuzije se zde vyhodne moznosti dedenıstruktury Petriho sıtı.

8.3.1 Trıda BankModel

Trıda BankModel (viz obr. 8.3) modeluje banku jako system hromadne obsluhy. Klientijsou generovani stochasticky casovanym prechodem generator. Banka ma kapacitu 100klientu. Zakaznıci jsou paralelne obsluhovani urednıky, kterı jsou modelovani znackami vmıste clerks (prechod service muze byt provaden nasobne, coz modeluje paralelnı obsluhuklientu mnozinou urednıku). Mısto stat slouzı ke sberu statictickych dat. Model je navrzenpro simulaci ve trech rezimech: busy, idle a very busy. Cıslo 1, 2 nebo 3 vmıste periodreprezentuje prıslusny rezim, ktery v praxi odpovıda urcite casti pracovnıho dne. Ten jedo prıslusneho mısta umısten metodou makeExperimentForPeriod:clerks: (viz obr. 8.4).Tato metoda inicializuje model na zaklade parametru (period a clerks). Pak necha bezetsimulaci po dobu 600 casovych jednotek, coz je doba trvanı experimentu v case modelu(self hold: 600 ). Pote z mısta stat vyzvedne, zpracuje a odevzda (v mıste return) vysledkyexperimentu (prumernou dobu obsluhy jednoho klienta). Predpoklada se, ze nad jednouinstancı modelu se provede jen jeden experiment (model, tak, jak ke specifikovan, projednoduchost nepocıta s moznostı restartu). Pro kazdy experiment se pocıta s vytvorenımnove instance trıdy BankModel.

S takto vytvorenym modelem, ktery bude dale pouzit soufistikovanejsım zpusobem,muzeme experimentovat interaktivnım vyhodnocenım vyrazu

BankModel new makeExperimentForPeriod: 1 clerks: 10

v ramci systemu Smalltalk (s knihovnou PNtalk). Vysledkem vyhodnocenı tohoto vyrazuje prumerny cas straveny klientem v bance (pro zadane parametry).


BankModel is_a PN

#e

p2

arrival

enter

arrival

FIFO

arrival

100‘#e

capacity

#e

#e

self hold: (Normal mean: 6 deviation: 1).

service

#e

totalTime := oldTotalTime + self time - arrival.custOut := oldCustOut + 1.

update_stat

arrival

periodperiod

clerks

#e

p1

(0, 0)

stat

#e

period <= 3

self hold: (Uniform min: (#(1 2 1) at: period) max: (#(4 9 3) at: period)).arrival := self time.

generator

makeExperimentForPeriod: p clerks: c

arrival

arrival(oldCustOut, oldTotalTime)

#e

(custOut, totalTime)

Obrazek 8.3: Trıda BankModel


makeExperimentForPeriod: p clerks: c

periodp

(0, 0)

stat

clerks

cp11

self hold: 600.

experiment#e

#e

p c

#e

return

avgTime := totalTime / custOut.

p

c‘#e

#e

(custOut, totalTime)

avgTime

Obrazek 8.4: Metoda trıdy BankModel, urcena k provedenı simulacnıho experimentu.


Bank is_a BankModel

enter

arrival

FIFOarrival

100‘#e

capacity#e


service

5‘#etellers

#e

#e

1

period

5‘#e cashiers

period

custOut := oldCustOut + 1.spent := self time - arrival.totalTime := oldTotalTime + spent.maxTime := oldMaxTime max: spent.

update_stat

#e

#e

arrival

FIFO2

arrival

(0, 0, 0)

stat

arrival

#e

p1

arrival

period <= 3

self hold: (Uniform min: (#(1 2 1) at: period) max: (#(4 9 3) at: period)).arrival := self time.

generator


service2

arrival

#e

(oldCustOut, oldTotalTime, oldMaxTime)

#e

(custOut, totalTime, maxTime)

#e

p2

arrival

Obrazek 8.5: Trıda Bank – prvnı cast sıte objektu


Bank is_a BankModel

#e

#e

nextPeriod

5‘#e

tellers

period

(5, 5)

clerks12

(cl1,cl2)

1

period

5‘#e

cashiers

10clerks

#ep5

#e

period

#e

self hold: #(120 240 120) at: period.

simulate

p3

(old1,old2)

#e

period

p4

period <= 3

result := self innerSimulationForPeriod: period maxClerks: maxClerks.cl1 := self consultManager: result.cl2 := maxClerks - clerks1.move1 := (old1 - cl1) max: 0.move2 := (old2 - cl2) max: 0.

inner

period

move1

period

nextPeriod := period + 1.

nextPeriod

period

move2

period

move1‘#e

move2‘#e

maxClerks

period > 3

Transcript show: ’Customers: ’, custOut printString; cr; show: ’avg. time: ’, (totalTime/custOut) printString; cr; show: ’max. time: ’, maxTime printString; cr.

endOfSim

move1to2

move2to1(0, 0, 0)

stat

(custOut, totalTime, maxTime)

#e

#e

#e

Obrazek 8.6: Trıda Bank – druha cast sıte objektu, na prvnı cast navazuje mısty periodtellers, cashiers a stat

8.3.2 Class Bank

Jiz vytvorena trıda BankModel bude nynı pouzita jako zaklad pro dalsı specializaci vramci sofistikovanejsıho modelu banky. Navıc ukazeme, jak instance BankModel muze bytsimulovana uvnitr jine simulace.

Sofistikovanejsı model banky se specifikovan trıdou Bank, dedıcı od trıdy BankMo-del. Trıda Bank prdava druhou obsluznou linku (druhou sadu prepazek) a model rızenıbanky, ktery provadı rozhodovanı o prirazovanu urednıku k jednotlivym typum prepazekna zaklade vysledku simulace modelu BankModel.

Sıt’ objektu, definovana trıdou Bank je zobrazena na dvou obrazcıch. Obrazek 8.5zobrazuje pruchod klientu bankou. Zdedene casti sıte objektu, ktere zustavajı beze zmeny,jsou zobrazeny sede. Obrazek 8.6 zobrazuje mechanismus rozhodovanı a premist’ovanıurednıku mezi prepazkami prvnıho a druheho typu na zaklade vysledku simulace bankypro tri faze dne (mısto period).

Vnoreny model je simulovan prechodem inner pro aktualna fazi. Tato cinnost je pro-vadena opakovane (pro fazi 1, 2 a 3), pak simulace koncı – viz cyklus <p5, inner, p3,simulate, p4, nextPeriod, p5>.


innerSimulationForPeriod: p clerks: c

c

(c,b)

results

(c,b)

p13

p

(c,result)

c

(c,result)

return

c

p11

cc

ccp

results

results := OrderedCollection new.

p14

self suspendTime.

suspendTime

p15

c > 0

b := BankModel newIn: Scheduler new.cc := c - 1.

nestedExperiment

c

oldResults results

p12

results size = c

self activateTime.

finishresult := b makeExperimentForPeriod: p clerks: c.

makeExperiment

results

results := oldResults add: (Array with: c with: result).

finishExperiment

Obrazek 8.7: Metoda trıdy Bank, urcena k provedenı vnorene simulace

Po kazde vnorene simulaci probehne rozhodovanı. Rozhodntı o premıstenı urednıkuje realizovano dialogem s uzivatelem (jsou mu pritom predlozeny vysledky simulace). Toje specifikovano metodou consultManager. Doporucena relokace urednıku je specifikovanaobsahem mıst move1 a move2. Prechody move2to1 a move1to2 realizujı relokaci.

8.3.3 Vnorena simulace, interakce casovych os

Vnorena simulace (viz obr. 8.6, prechod inner) je vzdy startovana se dvema parametry,prvnım je faze dne (period p), druhym je pocet dostupnych urednıku (clerks c). Obrazek8.7 ukazuje metodu trıdy Bank, ktera provadı vnorene simulace simulaci a sbıra data.Vnorena simulace je provadena pro vsechny mozne pocty urednıku, zacına se poctem c av kazdem kroku se c dekrementuje (viz obr. 8.6.

Vnorena simulace i rozhodnutı o poctu urednıku u obou typu prepazek probehne zhlediska casu modelu okamzite. V obou prıpadech jde o interakci ruznych casovych os. Vprvnım prıpade jde o cas vnorene simulace, v druhem prıpade jde o realny cas, ve kteremprobehne dialog. Z hlediska casu hlavnıho modelu trvajı obe operace nulovou dobu. Sku-


tecne trvanı vnorene simulace v modelovem case hlavnıho modelu je realizovano zpozdenımv cyklu, provadenıcım jednotlive simulace (viz obr. 8.6, prechod simulate). Vzhledem ktomu, ze OOPN/PNtalk je paralelnı jazyk, spustenı vnorene simulace i dialog s uzivate-lem jsou realizovany jako procesy, ktere bezı paralelne s ostatnımi aktivitami v modelu. Vobou prıpadech ale nenı znama doba ukoncenı, takze nelze udalost ukoncenı naplanovat.Jelikoz chceme, aby vse probehlo s nulovym zpozdenım, resenım je pozastavenı toku casuhlavnıho modelu do okamziku ukoncenı vnorene simulace nebo dialogu s uzivatelem. Protyto ucely existujı operace suspendTime a activateTime. Je li cas pozastaven, planovacdovolı provadet pouze udalosti planovane na aktualnı cas modelu. Po opetovne aktivacise mohou uplatnit i dalsı planovane udalosti a cas modelu se muze posunout, nenı-li naaktualnı cas jiz nic naplanovano. Tyto operace jsou pouzity v metodach consultManager(viz obr. 8.8) a innerSimulationForPeriod:clerks: (viz obr. 8.7)

consultManager: result

result

self suspendTime.tellers := GUI consultResult: result.self activateTime.

consult

return

result

tellers

Obrazek 8.8: Metoda trıdy Bank, urcena k dialogu s uzivatelem

Prechod nestedExperiment (viz obr. 8.7) vytvorı c vnorenych simulacı modelu BankMo-del. Vyraz BankModel newIn: Scheduler new zajistı, ze kazda vnorena simulace je pro-vedena v novem planovaci, tj. s nezavislym casem modelu. Reference na simulaci (vizpromenna b v obr. 8.7) je pak pouzita k provedenı simulacnıho experimentu prechodemmakeExperiment. Prechod finishExperimet posbara vysledky vsech simulacı. Cely tentoproces je odstartovan prechodem suspendTime a ukoncen prechodem finish.

8.3.4 Simulace

Simulace se spustı vyhodnocenım vyrazu Bank new. Postupne probehnou tri faze, pricemzv kazde z nich jsou provedeny vnorene simulace pro ruzne rozdelenı urednıku a jejichvysledky jsou predlozeny uzivateli i interaktivnımu vybery nejlepsı varianty (obr. 8.9).

Tabulka 8.1 zobrazuje simulacnı vysledky vnorenych simulacı pro faze busy, idle a verybusy a pro pocty urednıku od 1 do 10. Tucne jsou vyznaceny vybrane varianty. Celkovevysledky jsou v tabulce 8.2.


Obrazek 8.9: Simulace.

1 2 3 4 5 6 7 8 9 10busy 28.65 14.81 6.14 6.18 5.74 5.88 5.63 6.18 6.32 6.12idle 15.65 5.62 5.85 5.85 5.51 5.85 6.10 6.02 6.32 5.56

very busy 22.59 15.01 7.22 5.89 6.13 6.10 5.90 5.65 6.18 6.12

Tabulka 8.1: Vysledky vnorenych simulacı.

number of customers avg. time max. timemain simulation loop 135 14.74 32.43

Tabulka 8.2: Vysledky simulace.

8.4 Zaver

Prezentovany prıklad ve zjednodusene forme naznacil probematiku simulace simulujıcıchsystemu. V realnych situacıch je treba oproti uvedenemu prıkladu resit komplikovanejsıparametrizaci, prıpadne vytvorenı noveho modelu pro (vnorenou) simulaci na zakladeaktualne dostupnych dat.

Zatımco resenı v jazyce SIMULA umozuje pouze parametrizaci predem vytvorenychmodelu, PNtalk (prıpadne SmallDEVS) umoznuje dynamickou konstrukci vnorenych mo-delu na zaklade vysledku introspekce hlavnıho modelu.

Kapitola 9

Prıpadova studie: Prostredı provyvoj multiagentnıch systemu

V teto kapitole bude predstaveno prostredı pro tvorbu multiagentnıch systemu na baziobjektove orientovanych Petriho sıtı. Jde o demonstraci moznosti programovat agentyformalnımi modely s moznostı jejich dynamicke adaptace za zivota systemu. Tento prıstupje podrobneji popsan v publikacıch [?] a v disertacnı praci [Maz08].

9.1 Multiagentnı systemy

Multiagentnım system je system, ve kterem vzajemne interagujı agenti. Agenti [Woo02]jsou autonomnı entity, schopne dlouhodobe plnit cıle zadane uzivatelem bez jeho dohledu vdanem prostredı. Interakce agentu predstavuje komplexnı socialnı aktivity, jako kooperace,souperenı, vyjednavanı, apod.

Jako prıklady aplikacı multiagentıch systemu lze uvest komplexnı softwarove systemy,kde jednotlive komponenty jsou natolik nezavisle a slozite, ze z hlediska navrhu je efektivnıpovazovat je za zcela samostatne jednotky, ktere spolu komunikujı ve velmi male mıre po-mocı vysokourovnoveho jazyka, naprıklad jen v prıpade nestandardnıch situacı [SBD+00].Dalsımi oblastmi jsou tymova spoluprace robotu (napr. roboticky fotbal [Kit98]), tele-komunikacnı aplikace (mobilnı agenti, migrujıcı je zdrojum dat, coz vede k minimalizacizatızenı komunikacnı infrastruktury) [AM04], rekonfigurovatelne a adaptivnı softwarovesystemy, zahrnujıcı zakazkovou vyrobu [Kou01], rıdıcı systemy letiste [GR96]), distribuo-vane aplikace pro zıskavavı znalostı [KHS97], senzorove sıte [LTO03], semanticky web avyhledavanı informacı [E. 03], simulace socioekonomickych procesu [Mos01] apod. Velkapozornost je venovana nasazovanı multiagentnıch aplikacı v prumyslu, s cımz uzce sou-visı standardizace (o tu se stara organizace FIPA [FIP01]). Soucasne vsak stale pokracujevyzkum vhodnych vnitrnıch modelu agenta – a to jak v teoreticke, tak v prakticke (im-plementacnı) rovine.

Vyuzitı dynamickych modelu Existujı tri hlavnı duvody pro aplikaci dynamickychmodelu v oblasti inteligentnıch (agentnıch) systemu:

• Behem navrhu a vyvoje inteligentnıho systemu je treba se systemem nebo jeho pro-totypem prubezne experimentovat a dovyvıjet ho za behu. Struktura modelu (napr.

86 KAPITOLA 9. PROSTREDI PRO VYVOJ MULTIAGENTNICH SYSTEMU

fragmenty planu deliberativnıho agenta) jsou interaktivne a inkrementalne vyvıjenybehem existence systemu.

• System se vyvıjı vlastnımi prostredky sam. Na zaklade menıcıch se vnejsıch podmınekprovadı prubezne optimalizaci vlastnı struktury s ohledem na aktualnı cıle.

• V prıpade multiagentnıch systemu je treba pocıtat s dynamickym vytvarenım, mi-gracı a rusenım agentu. Iniciatorem manipulace muze byt jak agent, tak uzivatelnebo vyvojar. Agentnı platforma (operacnı system) musı takovouto manipulaci sagenty umoznit.

V nasledujıcım textu bude strucne naznacena realizace agentnıho systemu prostredky Ob-jektove orientovanych Petriho sıtı (OOPN). Vıce detailu lze najıt v [Maz08].

9.2 Aplikace v OOPN a DEVS v multiagentnıch systemech

Predmetem naseho zajmu jsou deliberativnı agenti, zalozenı na Beliefs-Desires-Intentions(BDI) architekture [Bra87]. Takovı agenti pracujı s vnitrnim modelem sveta (beliefs), cıli(desires) a zamery (intentions). Zamery jsou vytvareny v podobe planu, ktere docasnerıdı cinnost agenta a jsou dynamicky vytvareny v souladu s aktualnımi cıli na zakladenekterych vstupnıch udalostı.

Koncept multiagentıho systemu v prostredı PNtalk/SmallDEVS Vzhledem ktomu, ze agentnı systemy jsou ve sve podstate systemy paralelnı a distribuovane, jevıse smysluplnym pouzıt pro jejich specifikaci Petriho sıte. Aplikacı Petriho sıtı v navrhuagentnıch systemu ruznych typu se zabyvalo nekolik autoru, jako jsou [MW97], [WH02],a [YC06]. Tyto prıstupy vesme modelujı agenty barvenymi Petriho sıtemi, resp. sıtemi sobjektovym strukturovanım, ale bez dynamicke instanciace.

V ramci nami zvolene architektury agenta (BDI) jsou Petriho sıte pouzity predevsımpro reprezentaci planu. Vzhledem k tomu, ze se zde na konceptualnı urovni pracuje sdynamicky instanciovatelnymi Petriho sıtemi, jevı se smysluplnym pouzıt pro specifikaciagenta formalismus OOPN, resp. jazyk PNtalk [Jan95] [MVT97] [MVR+06], ktery je naformalismu OOPN zalozen. Krome samotnych agentu je formalismem OOPN (v jazycePNtalk) mozne specifikovat i agentnı platformu (agentnı operacnı system), vytvarejıcı po-trebnou abstrakci okolnı reality a poskytujıcı prostredı pro existenci agentu. Takto navr-zeny agentnı system vyuzıva infrastrukturu, poskytovanou prostredım SmallDEVS [JK06].Jde zejmena o mechanismus rızenı simulacı a vazbu na externı realitu. V nasem prıpadepredpokladame aplikaci v oblasti male mobilnı robotiky. Vazba na realne okolı agentu jev tomto prıpade implementovana jednotnym rozhranım, zprıstupnujıcım jak realne, taksimulovane roboticke platformy. Pro simulaci robotu v simulovanem prostredı je pouzitexternı roboticky simulator.

Agentnı architektura Architektura systemu vychazı z existujıcıch architektur BDIagentu, jako je PRS [GL87] a jeho naslednıci dMars [dLG+04], 3APL [DdBDM03], Ja-dex [PBL03], AgentSpeak [Rao96] and [BWH07]. Nejvıce je inspirovana systemy dMars[dLG+04] a Jason [BWH07]. Originalnım prınosem je (1) formalnı specifikace celeho agent-nıho systemu (jeho obecnych i aplikacne-specifickych soucastı) objektove orientovanymi

9.2. APLIKACE V OOPN A DEVS V MULTIAGENTNICH SYSTEMECH 87

Petriho sıtemi a (2) otevrenost, umoznujıcı experimentovat jak s variantnımi implementa-cemi agentu, tak i s modifikacemi cele agentnı architektury.

Na obr. 9.1 jsou znazorneny nejdulezitejsı trıdy, kterymi je implementovano prostredıPNagent. Z diagramu trıd je patrne, ze multiagentnı system system (MAS) obsahuje komu-nikujıcı agenty (CommunicatingAgent), kterı si mohou prostrednitvım agentnı platformy(Platform) posılat zpravy (ACLMessage). Kazdy agent obsahuje mnozinu planu (Plan-Template). Veskere zmeny stavu systemu jsou dusledkem udalostı (Event). Udalosti proagenta generuje platforma. Kazdy plan ma prirazeny vzory spoustecıch udalostı, prıpadnevzory udalostı, ktere plan suspendujı, obnovı provadenı, zpusobı selhanı, nebo uspesnedokoncenı. Zvlastnım typem udalosti je cıl (Goal). Cıle jsou, na rozdıl od beznych uda-lostı, perzistentnı (zustavajı v platnosti, dokud nejsou splneny, nebo dokud se nestanouneaktualnımi). Instance planu (PlanInstance) jsou soucastı zameru (Intention). Na zakladeudalosti nebo vzniku cıle se instanciuje odpovıdajıcı plan a vytvorı se zamer. Zamer takeobsahuje prıpadne instance podplanu. Obrazek 9.2 obsahuje schematicke znazornenı jadraagenta, ktere interpretuje udalosti. V ramci vyse uvedeneho prostredı musı aplikacnı pro-gramator specifikovat (1) bazi predstav (model sveta, beliefs), (2) metody trıdy agenta,reprezentujıcı agentovy schopnosti, (3) externı udalosti, reprezentujıcı zmeny v prostredı,(4) aplikacne specificke plany.

Obrazek 9.1: Zjednoduseny diagram trıd systemu PNagent, zobrazujıcı nejdulezitejsı trıdya jejich vztahy.

Model sveta (beliefs, baze predstav) Trıda agenta musı vzdy specifikovat modelsveta. Zpusob modelovanı lze demonstrovat na typickem ukazkovem prıkladu pro multi-agentnı systemy, nazvanem Cleaner World. Jde 2D prostredı maticoveho typu, obsahujıcıodpad, agenty a popelnice. Pozice odpadu, popelnic a agentu, stejne jako aktualnı stavagenta, muze byt vyjadren napr. v Prologu takto:

wastePosition(5,6).wastePosition(4,4).binPosition(2,3).


Obrazek 9.2: Schematicke znazornenı struktury interpretu systemu PNagent.

agentPosition(4,5).carryingWaste.

Obrazek 9.3 ukazuje, jak lze tentyz model vyjadrit prostredky OOPN. Fakta jsou modelo-vana znackami v mıstech. Synchronnı port canDropWaste a negativnı predikat notCarry-ingWaste slouzı k testovanı stavu sveta, resp. ke zjistenı, zda stav sveta dovoluje provestnejakou operaci.

Obrazek 9.3: Agentnı prostredı Cleaner World a jeho reprezentace v jazyce PNtalk.

Zamery, plany Zamery obsahujı instance planu. Plany jsou predem pripraveny aplikac-nım programatorem. Tato agentnı architektura nepocıta s vytvarenım planu od pocatcnıchprincipu, jako napr. STRIPS, ale aktivuje predem pripravene dılcı plany podle aktualnısituace. Plany ale mohou byt specifikovany jen castecne a k jejich dospecifikovanı muzedojıt az za behu, pri instaniaci. Plan je specifikovan Petriho sıtı, ktera vzdy obsahuje mıstastart, success a failure. Dalsı mısta a prechody specifikujı kauzalitu jednotlivych operacıa stav provadenı planu. Na obrazku 9.4 je prıklad instance planu. Provadenı prechodu,specifikujıcıch jednotlive kroky provadenı planu, je omezeno strazı self step: myAgent. Od-povıdajıcı synchronnı port je proveditelny, je-li plan aktivnı a interpret planu je pripravenk provedenı kroku. Dalsı stavy provadenı planu (krome #active) jsou #ready (pripravenk aktivaci), #suspended (pozastaven), #succeeded (ukoncen uspesne), #failed (ukoncenneuspesne). Plany majı prideleny priority, ktere se uplatnı pri resenı konfliktu.


Obrazek 9.4: Prıklad planu specifikovaneho Petriho sıtı v prostredı PNagent.

Interpret Interpret je implementovan trıdou BDIAgent. Jadro interpretu je na obrazku9.5. Tradicnı cyklus interpretu BDI agenta – zıskej nove udalosti, vytvor odpovıdajıcıplany, uprav strukturu zameru, vyber jeden zamer a proved’ jeden krok jeho aktualnıhoplanu – je zde rozdelen do dvou nezavislych castı. Cast zobrazena na obrazku 9.5 vpravoje zodpovedna za zpracovanı udalostı – udalosti jsou postupne odebırany z fronty udalostı,majı moznost upravit agentovu bazi znalostı a pote jsou paralelne predany metodam, jezmajı za ukol vytvarenı novych instancı planu, resp. spravu stavu existujıcıch instancı (tedyuspavanı, probouzenı atd.). Druha cast, zachycena na obrazku vlevo, se stara o interpretacistruktury zameru.

Interpret vykonava jeden zamer krok po kroku tak dlouho, dokud je tento zamer pro-veditelny. Pote vybere nahodne jiny proveditelny zamer. Interpretace zameru predstavujevlastnı funkcnost agenta – zde se v jednotlivych krocıch realizujı agentovy plany, tedyprovadejı akce, ktere ovlivnujı prostredı.

Agentnı platforma Trıda Platform definuje prostredı, v kterem agenti existujı. Posky-tuje agentum tri zakladnı sluzby: (1) Spravu zivotnıho cyklu – zejmena prostredky pro


Obrazek 9.5: Zpracovanı udalostı a interpretace zameru agenta.

vytvarenı a odstranovanı agentu, pridelovanı jednoznacnych identifikatoru (AID) apod.,(2) sluzbu bılych stranek (vyhledavanı agentu podle jejich AID), a (3) prenos zprav meziagenty. Jazyk zprav odpovıda podmnozine jazyka FIPA ACL [FIP01]. Nizsı vrstvu plat-formy, vcetne vazby na realne okolı, obstarava prostredı SmallDEVS.

Aplikace prostredı PNagent v oblasti robotiky Vyse popsane multiagentnı pro-stredı bylo experimentalne overeno v oblasti male mobilnı robotiky. Agent je pouzit prorızenı robota. To znamena, ze ma za ukol zpracovavat informace ze senzoru robota aovladat jeho akcnı prvky. Vyvoj rıdicıho softwaru (agenta) probıha v prostredı PNtal-k/SmallDEVS. Senzory a akcnı prvky robota jsou dostupne prostrednictvım specialnıhorozhranı na externı realitu, ktere je v prostredı SmallDEVS realizovano jako komponentas DEVS rozhranım (viz obr. 9.7). Tato komponenta zprıstupnuje rozhranı na Player/Stage(viz obr. 9.6). Player [GVH03] je middleware pro robotiku (vyvinuty v Univ. Of SouthernCalifornia),1 poskytujıcı jednotne rozhranı na senzory a aktuatory fyzickych i simulova-nych robotu. Z hlediska aplikace jde o server, zprıstupnujıcı senzory a aktuatory v abs-trahovane forme klientskym programum, pricemz klientske programy implementujı rızenırobotu. Player obsahuje ovladace jak pro simulovane, tak pro realne senzory a aktuatoryrobotu. K simulaci chovanı robotu v 2D a 3D prostredı slouzı simulatory Stage a Gazebo[GVH03], s kterymi Player spolupracuje. Pri experimentech byl pouzit jeden ze zakladnıch

1http://playerstage.sourceforge.net/


Obrazek 9.6: Simulator Stage

Obrazek 9.7: Rozhranı na Player

modelu robota implementovanych simulatorem, ActiveMedia Pioneer P3-DX 3, vybavenyosmi sonary o rozsahu 45 s dosahem 2,5 m, rozmıstenymi radialne kolem robota, osminaraznıky, kompasem a radiem, umoznujıcım zasılanı zprav ostatnım robotum. Prıkazy,ktere je schopen robot vykonat (odpovıdajı agentovym schopnostem) jsou ctyri: robotse muze pohybovat vpred, zastavit, otocit se o dany uhel a zaslat zpravu pomocı radia.V takto vytvorenem prostredı lze experimantovat s ruznymi multirobotickymi ulohami.Overenı prakticke pouzitelnosti bylo provedeno na uloze formovanı tymu robotu, jak byladefinovana napr. v [HZ04]. Vıce podrobnostı lze najıt v [Maz08].

Od simulace k realite Pro realizaci uvedene multiroboticke ulohy byl pouzit externısoftware, sestavajıcı ze serveru Player a simulatoru Stage. Prechod od simulovanych ro-botu v simulovanem prostredı k realnym robotum v realnem prostredı muze byt provedennekolika zpusoby, prıpadne v nekolika fazıch:

1. PNagent, PNtalk, SmallDEVS a Player bezı na PC, Player komunikuje se senzory aakcnımi prvky robotu radiovym spojenım.

2. PNagent, PNtalk a SmallDEVS bezı na PC, Player bezı na internetove dostupnempalubnım pocıtaci kazdeho robota a prımo pristupuje k jeho senzorum a akcnımprvkum.

3. PNagent, PNtalk a SmallDEVS bezı na nekolika PC (na kazdem bezı rızenı jednoho


robota), Player bezı na palubnım pocıtaci kazdeho robota a prımo pristupuje k jehosenzorum a akcnım prvkum.

4. PNagent, PNtalk, SmallDEVS a Player bezı na palubnım pocıtaci kazdeho robota.

Ve vsech prıpadech lze do prostredı PNagent/PNtalk/SmallDEVS za behu pristupovatpodle konfigurace bud’ lokalne, nebo vzdalene. Je tak mozne behem experimentu detailnesledovat a prıpadne i interaktivne modifikovat stav a strukturu agentu, rıdıcıch roboty.

Obrazek 9.8: Konfigurace systemu pro multirobotickou ulohu.

9.3 Shrnutı

Kombinace formalismu OOPN a DEVS je pro tuto aplikaci uzitecna z nekolika duvodu.Formalismus DEVS, resp. prostredı SmallDEVS, prinası hierarchicky organizovane volnevazane komponenty, udalosti, snadnou manipulaci (plug’n’play), prımou vazbu na teoriimodelovanı a simulace, operacnı system. Formalismus OOPN, resp. jazyk PNtalk, prinasıparalelismus, synchronizaci, objekty, vizualnı jazyk, prirozenou reprezentaci planu. Jakaplikacne specificka cast agenta, tj. reprezentace sveta, dılcı plany atd., tak i obecna ar-chitektura agenta jsou popsany pomocı OOPN v jazyce PNtalk a interpretovany v ramciprostredı SmalDEVS. Tyto prostredky umoznujı interaktivnı (i automaticky) evolucnı vy-voj modelu. Je tedy mozny inkrementalnı vyvoj jak agentnı aplikace, tak i obecne agentnıarchitektury, a to za pouzitı stejnych prostredku. Moznost snadne adaptace agentnı ar-chitektury podle aktualnıch pozadavku dane aplikace muze urychlit a zkvalitnit vyvojagentnıho systemu. Krome toho potencialne umoznuje i automatickou evoluci agentu iagentnı platformy.

Kapitola 10

Prıpadova studie: Dynamickemodely v rızenı projektu

V teto kapitole bude predstaven koncept vyuzitı dynamickych OOPN v rızenı projektu,konkretne v modelovanı projektoveho portfolia pro potreby rozvrhovanı a monitorovanı.

10.1 Zakladnı pojmy z oblasti rızenı projektu

Projekt Projekt [Anb05] je casove ohranicene usilı smerujıcı k vytvorenı unikatnıhoproduktu nebo sluzby.

Rızenı projektu Rızenı projektu [Sch05] je proces planovanı, koordinovanı a rızenı uloha zdroju pro dosazenı definovaneho cıle v danem case, s definovanymi zdroji a s omezenoucenou. Problematika rızenı projektu zahrnuje (1) planovanı projektu, (2) organizaci pro-jektu, (3) rozpocet projektu, (4) odhad a kontrolu spotreby zdroju a casu, (5) rızenı rizikprojektu, (6) rızenı zmen, (7) projektovou dokumentaci.

Rızenı projektoveho portfolia Jde o rızenı nikoliv jednoho projektu, ale skupinyaktualnıch i planovanych projektu, aby se dosahlo konkretnıch cılu. Smyslem rızenı pro-jektoveho portfolia je optimalizace casu, nakladu a zdroju, presahujıcı ramec jednotlivychprojektu [GK03, Lee04]. Mnozina aktualnıch a planovanych projektu, tvorıcı portfolio, sev prubehu casu vyvıjı.

Proces Proces je sekvence aktivit vedoucı k ocekavanemu vysledku. K provadenı aktivitjsou vyuzıvany zdroje, aktivity transfromujı vstupy na vystupy. Aktivity a zdroje v ramciprojektu jsou obvykle chapany jako procesy [Anb05].

Sıt’ovy diagram projektu Sıt’ovy diagram je grafova reprezentace usporadanı jednot-livych aktivit, ktere vedou k cıli projektu. Sıt’ovy diagaram umoznuje specifikovat sekvenceakcı, paralelnı vetve i kolize. Aktivity majı prirazenu dobu trvanı a je tedy mozne ana-lyzovat casove charakteristiky projektu (doba trvanı, kriticka cesta). Casto pouzıvanoualternativou sıt’oveho siagramu je casovana Petriho sıt’.

94 KAPITOLA 10. DYNAMICKE MODELY V RIZENI PROJEKTU

Planovanı Planovanı je proces vyberu a usporadanı aktivit, vedoucıch k dosazenı cıle[Spi92].

Rozvrhovanı Rozvrhovanı [Spi92, Pin02, Pin05] je alokace zdroju umıstenych v caso-prostoru za danych podmınek na aktivity tak, aby se splnila zadana kriteria, naprıkladminimalizace celkove ceny danych zdroju. Vystupem procesu rozvrhovanı je rozvrh. Jednase o datovou strukturu obsahujıcı informace o prirazenı aktivit zdrojum v case.

Staticke a dynamicke planovanı a rozvrhovanı Staticke (off-line) planovanı a roz-vrhovanı [Pin05, Koc02] predpoklada, ze vsechny pozadavky (cıle) a vsechny parametrydostupnych zdroju jsou dopredu znamy a v budoucnu se nemenı. V praxi jsou takove si-tuace vzacne. V prıpade projektoveho portfolia se pocıta s vyvojem cılu i zdroju v case.Behem resenı (za behu systemu) se objevujı nove cıle a tedy vznikajı nove projekty, jineprojekty jsou v dusledku zmeny cılu ruseny nebo jsou jim meneny parametry. Strukturaa parametry zdroju se take s casem menı. Dynamicke (on-line) planovanı a rozvrhovanı[Koc02] predstavuje proces tvorby rozvrhu za behu systemu. Rozvrh je tedy tvoren inkre-mentalne pri zmene aktualne dostupnych informacı. Dulezitym pozadavkem je dostatecnarychlost on-line planovanı a rozvrhovanı.

Monitorovanı Monitorovanı projektu je sledovanı vyznamych udalostı v prubehu resenıprojektu a porovnavanı se simulacı projektu. Typicky jde o sledovanı zacatku a koncujednotlivych aktivit, prıpadne o udalosti, jako jsou neplanovane zmeny ve strukture aparametrech zdroju. V prıpade jakekoli odchylky reality od simulace je treba upravitmodel a okamzite provest dynamicke planovanı a rozvrhovanı, aby model (vcetne rozvrhuzdroju) odpovıdal realite a aby byly splneny vsechny aktualnı pozadavky na system.

10.2 Aplikace dynamickych OOPN v modelovanı projekto-veho portfolia pro potreby rozvrhovanı a monitorovanı

V teto studii ukazeme, ze pro adekvatnı modelovanı projektoveho portfolia na bazi Petrihosıtı je treba pouzıt (at’ uz prımo, nebo jen na konceptualnı urovni) dynamickou variantuObjektove orientovanych Petriho sıtı (OOPN), aby bylo mozne provadet jak klonovanıa editaci pro potreby optimalizace a rozvrhovanı, tak dynamickou modifikaci v prubehumonitorovanı podle menıcıch se vnejsıch podmınek (a reflektovat tak zmeny ve strukturezdroju, pridavanı novych planu, zmeny planu apod).

Pro potreby rızenı projektoveho portfolia se pouzıva rada prıstupu, metod a modelova-cıch formalismu, mnohe z nich vyuzıvajı modely na bazi Petriho sıtı [GK03, AG04, HY03].Vesmes jde o Petriho sıte sice vysokourovnove, ale nestrukturovane. Vyuzitı moznostistrukturovanı, at’ uz statickeho, jako v prıpade hierarchickych Petriho sıtı, tak dynamic-keho, jako v prıpade objektove orientovanych Petriho sıtı, se jevı jako mozne a prınosne.Ocekavanou vyhodou objektove orientovanych Petriho sıtı je adekvatnı strukturovanı mo-delu projektoveho portfolia.

Existuje rada potencialne pouzitelnych prıstupu, kombinujıcıch Petriho sıte a objekty,k nejpropracovanejsım (z hlediska souvisejıcı teorie a moznostı analyzy a verifikace) patrıReference nets [Val98], [Ren06]. V teto studii se ale zamerıme na Objektove orientovane

10.2. MODELOVANI PROJEKTOVEHO PORTFOLIA 95

Petriho sıte (OOPN) [Jan95, Jan98], vychazejıcı dusledne z klasickeho objektoveho pa-radigmatu [GR89]. Hlavnım duvodem tohoto vyberu je koncept dynamicky instanciova-telnych sıtı metod, ktery v konkurencnıch prıstupech chybı a ktery je pro zamyslenouaplikaci klıcovy. Dalsım duvodem je otevrena implementace simulatoru OOPN [JK04],ktera je take pro zamyslenou aplikaci nepostradatelna.

Koncept modelovanı projektoveho protfolia Projektove portfolio lze modelovatpomocı OOPN takto:

• Projektove portfolio je modelovano jednım objektem OOPN. Zdroje jsou modelo-vany objekty, dostupnymi jako znacky v mıstech – znacky nesou reference na objektyzdroju. Tyto odkazy na zdroje jsou distribuovany do mıst sıte objektu podle jejichrolı.

• Sıte metod modelujı jednotlive vzory planu projektu. Jejich instance jsou dynamickyvytvareny a ruseny v okamziku startu, resp. ukoncenı projektu.Tyto plany sdılı prı-stup k mıstum sıte objektu, kde jsou k dispozici zdroje. Start projektu je technickyrealizovan zaslanım odpovıdajıcı zpravy objektu portfolia (s prıpadnymi parametry,upresnujıcımi plan). V tom okamziku je vytvorena nova instance sıte metody (t.j.planu) a zacına bezet.

Model projektoveho portfolia Na obr. 10.1 je prıklad modelu projektoveho portfolia.Obsahuje tri ruzne typy projektu, resp. tri typy planu, modelovane metodami OOPN. Tytoplany sdılı tri typy (resp. role) zdroju. Typy zdroju (jejich role) jsou modelovany mıstysıte objektu portfolia.

Plany A a B jsou na obr. 10.1 znazorneny bez zobrazenı jejich sktruktury, plan C jeukazan i s jeho strukturou. Prechody sıte objektu portfolia obsahujı vyrazy tvaru self pro-jectA: x. Tyto prechody jsou urceny k invokaci odpovıdajıcıch metod zaslanım prıslusnychzprav, tedy pro vytvorenı a nastartovanı jednotlivych konkretnıch projektu. Pozname-nejme, ze jsou prıpustne nasobne invokace metod OOPN, ktere se pak mohou prekryvatv case.

Hierarchicka kompozice planu Plany projektu mohou byt slozeny z podplanu. Ktomu lze pouzıt koncept invokacnıho prechodu, ktery zaslanım zpravy self subplan vytvorınovou instanci subplanu a v okamziku ukoncenı jejıho provadenı pokracuje umıstenımznacek do vystupnıch mıst.

Zdroje a jejich role Obrazek 10.1 neukazuje vsechny detaily – nejsou v nem prozatımuvazovany jednotlive zdroje. Predpoklada se, ze zdroje jsou modelovany znackami v mıs-tech, ktera odpovıdajı jejich rolım. Zdroje jsou instance trıdy Resource (viz obr. 10.2).Vzhledem k tomu, ze znacky v OOPN jsou reference na objekty, kazdy zdroj muze mıt vtakto koncipovanem modelu potencialne vıce nez jednu roli. Obrazek 10.3 ukazuje situaci,kde je jeden zdroj (objekt trıdy Resource), majıcı dve ruzne role, sdılen dvema projekty.

Kazda aktivita pozaduje zdroj urciteho typu (zdroj schopny plnit urcitou roli) naurcitou dobu. Aktivita A1 projektu A pozaduje zdroj s rolı R1 na 10 casovych jednotek,aktivita A2 projektu B pozaduje zdroj s rolı R2 na 5 casovych jednotek. Pozadovabadoba trvanı aktivity je obvykle odhadnuta na zaklade predchozıch zkusenostı s podobnymi


projectA: x

projectC: x

projectB: x

ProjectPortfolio is_a PN

self projectA: x

self projectB: x

self projectC: x

x

x

x

y

y

y

a

b

c

x

y

r1

r2

r3

Obrazek 10.1: Model projektoveho portfolia

Resource is_a PN

allocFor: a duration: d

use

.

self hold: d

d

d

.

.

allocated idle

.return

Obrazek 10.2: Zdroj

..R1 R2

projectA

r

A1

r allocFor: #A1 duration: 10

r use

projectB

r

A2

r allocFor: #A2 duration: 5

r use

a ResourceallocFor: a duration: d

use

.self hold: d

d

d

.

.allocated idle

.return

Obrazek 10.3: Konflikt dvou aktivit pozadujıcıch jeden zdroj se dvemi rolemi


projekty.1 Mısta R1 a R2 obsahujı znacku odkazujıcı na tentyz objekt, modelujıcı sdılenyzdroj. Kazda aktivita se nejprve snazı zdroj alokovat. Nenı-li zdroj dostupny, ceka se najeho uvolnenı. To je specifikovano strazı kazdeho prechodu, modelujıcıho aktivitu. Podarı-lise zdroj alokovat, je nasledne pouzit. Pouzitı zdroje je modelovano casovanym prechodem(viz metoda use v trıde Resource – zpozdenı je realizovano zpravou self hold: d).

SheduledResource is_a Resource

use

.

self hold: d

d

d

.

.allocated idle

allocFor: a duration: dself isScheduledFor: a time: (DateAndTime now) duration: d

schedule

(sa, st, sd)

isScheduledFor: a time: t duration: d(a = sa) & (t >= st) & (t < (st+sd)) & (d <= sd)

.return

Obrazek 10.4: Zdroj s rozvrhem.

Rozvrhy zdroju Obrazek 10.4 ukazuje zdroj s rozvrhem. Straz synchronnıho portu proalokaci zdroje kontroluje, zda je pozadavek v souladu s rozvrhem. Rozvrh je ulozen v mısteschedule jako mnozina trojic (aktivita, cas, trvanı) a je k dispozici na dotaz (volanım syn-chronnıho portu). Rozvrh pro kazdy zdroj je vytvoren vhodnym optimalizacnım procesemmimo model a pote umısten do mısta schedule. Model s doplnenymi rozvrhy pro jednotlivezdroje je pak pouzitelny pro analyzu, overenı spravnosti modelu a pro monitorovnanı.

Schopnosti zdroju Pro kazdy zdroj lze specifikovat jeho schopnost vykonavat urciteaktivity. Jde o mıru vhodnosti zdroje pro danou aktivitu. Tento udaj lze zıskat analyzoudat z predchozıch projektu. Doba vykonavanı aktivity je pak neprımo umerna schopnostizdroje. V prıpade zdroje se schopnostı s = 1.0 je skutecna doba trvanı (tj. doba pouzitızdroje) rovna typickym pozadavkum aktivity, v jinych prıpadech muze byt tato doba delsı(i kratsı). Casovany prechod metody use na zaklade informacı z mısta skills, ktere obsa-huje dvojice (aktivita, schopnost), provede cekanı po dobu (1/s)d. Obrazek 10.4 ukazujedoplnenou verzi trıdy ScheduledResource.

Alokace vıce zdroju pro jednu aktivitu Vyzaduje-li aktivita vıce zdroju, je to trebaodpovıdajıcım zpusobem specifikovat. Obrazek 10.6 ukazuje model aktivity, pozadujıcı trizdroje se dvemi rolemi. Synchronnı pouzitı zdroju (srovnanı zacatku a dob trvanı pouzitızdroju) je modelovano zpravou (a odpovıdajıcı metodou zdroje) r useWith: s with: t.2

V prıpade, ze je pro danou aktivitu nutne pouzıt vıce zdroju, lze zohlednit vhodnostdane kombinace zdroju pro tymovou praci. To lze specifikovat maticı, ktera kazde dvojici

1Naprıklad metodami zıskavanı znalostı z databazı (datamining).2Existujı varianty teto zpravy pro ruzny pocet parametru. Odpovıdajıcı metoda trıdy

ScheduledResource zjistı maximalnı dobu trvanı, nastavı ji vsem zdrojum (volanım k tomu urce-nych synchronnıch portu), pote zasle puvodnı zpravu use paralelne vsem zucastnenym zdrojum vcetnesebe a pocka na jejı dokoncenı vsemi zucastnenymi zdroji.


SheduledResource is_a Resource

use

.

self hold: (1/s)*d

(a, d)

(a, d)

.

.allocated idle

allocFor: a duration: dself isScheduledFor: a time: (DateAndTime now) duration: d

schedule

(sa, st, sd)

isScheduledFor: a time: t duration: d(a = sa) & (t >= st) & (t < (st+sd)) & (d <= sd)

.return

skills(a, s)

Obrazek 10.5: Zdroj s rozvrhem a schopnostmi.

projectA

a Resource

a Resource

a Resource

a Resource

A1

r allocFor: #A1 duration: 10.s allocFor: #A1 duration: 10.t allocFor: #A1 duration: 10

r useWith: s with: t

.R1

r, s

.R2

t ..

Obrazek 10.6: Aktivita vyzadujıcı vıce zdroju

zdroju prirazuje mıru schopnosti spolupracovat. Podobne jako v prıpade typicke dobytrvanı aktivit a schopnosti vykonavat konkretnı aktivity, schopnost tymove spolupracezdroju lze zıskat analyzou dat z predchozıch projektu. Tato schopnost se opet projevı vdelce skutecneho trvanı aktivity. Konkretnı implementace je v metodach typu useWith: rve trıde ScheduledResource.

Koncept pouzitı modelu pro rozvrhovanı a monitorovanı Prakticke pouzitı OOPNv modelovanı projektoveho portfolia pro potreby rozvrhovanı a monitorovanı muzeme nynıpodrobneji specifikovat takto:

• Simulace se pouzıva pro overenı spravnosti navrhu projektu. Zde se uplatnı hlavneinteraktivnı simulace. Model je tez pouzitelny pro analyzu, vedoucı napr. ke zjistenıkriticke cesty v projektu. Start projektu se simuluje invokacı odpovıdajıcı Petrihosıte (to je technicky reseno zaslanam zpravy s prıpadnymi parametry, vysledkem jeinvokace odpovıdajıcı metody objektu projektoveho portfolia).

• Opakovana automaticka simulace je pouzita take jako soucast fitness funkce prioptimalizaci zpusobu pridelovanı zdroju aktivitam. Vysledkem tohto optimalizacnıhoprocesu je rozvrh, ktery vzajemne mapuje zdroje, casove intervaly a aktivity.


• Simulace s definovanymi rozvrhy zdroju je muze byt pouzita k dalsı analyze. Model jejiz deterministicky3 a simulacı lze napr. vygenerovat Ganttuv diagram pro potrebydokumentace projektu. Lze potencialne zohlednit i neurcitost a pracovat s fuzzyrozvrhem.

• Model s definovanym rozvrhem zdroju muze byt pouzit pro monitorovanı projektu.Pro monitoring predpokladame simulaci synchronizovanou realnym casem a uda-lostmi z realneho prostredı. Mapovanı realneheho casu a casu modelu pritom re-spektuje fakt, ze cas modelu pokryva pouze pracovnı dobu.4

• Pri zmene ve strukture zdroju se musı okamzite automaticky aktualizovat mısta,znacky a objekty, ktere tyto zdroje modelujı, a provede se nove rozvrhovanı. Povytvorenı noveho rozvrhu se aktualizujı objekty zdroju (protoze obsahujı vlastnırozvrh pro jednotlive cinnosti).

• Pro potreby rozvrhovanı se vytvorı klon okamziteho stavu (jde o stav modelu vprubehu monitorovanı) a ten je pouzit jako pocatecnı stav pro zkoumanı vsech moz-nych budoucnostı portfolia s ruznymi zpusoby pridelovanı zdroju v ramci zvoleneoptimalizacnı strategie a zvolenych kriteriı.

• Vytvorenı noveho typu projektu (noveho planu) znamena pridanı nove metody ob-jektu portfolia za behu. Sıt’, modelujıcı plan projektu, muze byt podle menıcıchse vnejsıch pozadavku modifikovana v prubehu resenı, stejne tak i jednotlive jejıinstance.

Zachovanı modelu Dıky predpokladane moznosti zasahovat do bezıcı simulace v pru-behu monitorovanı a dıky moznosti stav simulace klonovat a dale pouzıt pro potreby ana-lyzy a optimalizace je snadno realizovatelny fenomen zachovanı modelu (model continuity)v projektovem rızenı. Zakladnı myslenkou je povazovat model projektoveho portfolia spe-cifikovany formalismem OOPN za zakladnı a vsechny ostatnı pohledy na projektove port-folio automaticky generovat, prıpadne z jinych pohledu automaticky generovat a realizovatautomaticke editacnı zasahy do modelu na bazi OOPN.

K prakticke realizaci Uvedeny zpusob pouzitı OOPN vyzaduje realizovat simulatorotevrenym zpusobem. Prakticky to znamena zprıstupnit metaobjektovy protokol (MOP)simulatoru. MOP (jinak tez reflektivnı rozhranı) simulatoru umoznı zasahovat do strukturymodelu za behu.

Takove rozsırenı OOPN bylo jiz navrzeno a experimentalne implementovano v prostredıjazyka a systemu PNtalk, coz je implementace OOPN ve Smalltalku [JK04]. OOPN/PN-talk MOP umoznuje vytvarenı, rusenı, inspekci a editaci jednotlivych Petriho sıtı definujı-cıch trıdy a jednotlivych instancı sıtı implementujıcıch jednotlive zive objekty. Umoznujetake vytvorit klon bezıcıho systemu a ulozit, resp. nacıst ho do/z databaze.

Alternativou k prımemu pouzitı simulatoru OOPN je moznost OOPN pouzıt jen nakonceptualnı urovni s tım, ze samotna realizace muze byt jina. OOPN je mozne trans-formovat do jinych formalismu a prostredı. Cılovou realizacı muze byt napr. databazova

3Zdroje jsou modelovany objekty, dostupnymi jako znacky v mıstech sıte objektu. Straze prechodu mo-delujıcıch jednotlive aktivity v ramci jednotlivych projektu kontrolujı krome okamzite fyzicke dostupnostizdroje take to, zda rozvrh zdroje dovoluje zdroj aktivite pridelit (to je implementovano metodami zdroje).

4Cas modelu by mohl byt zaveden i jinak. Model by pak byl obecnejsı, ale take komplikovanejsı.


aplikace. Pro optimalizaci a rozvrhovanı pak mohou byt pouzity existujıcı obecne nastroje,napr knihovny pro geneticke algoritmy apod.

10.3 Shrnutı

Studii o modelovanı projektoveho portfolia Objektove orientovanymi Petriho sıtemi mu-zeme shrnout takto:

• Obvyklym resenım s vyuzitım Petriho sıtı je udrzovat jednu globalnı vysokourovno-vou Petriho sıt’ pro cele projektove portfolio a tuto Petriho sıt’ postupne v ramcimonitorovanı aktualizovat a po aktualizaci pouzıt jako vychodisko pro rozvrhovanı.

• Modely na bazi OOPN nabızejı moznost pouzıt dynamicky instanciovatelne Petrihosıte pro modelovanı jednotlivych planu projektu. Predem definovane plany lze dy-namicky instanciovat, instance planu mohou byt parametrizovany. Jednotlive planyjsou ale staticky fixovany – odpovıdajıcı Petriho sıte jsou v prıpade klasicke variantyOOPN pevne dany v dobe startu systemu.

• Doporucene resenı: Instanciovatelne Petriho sıte s moznostı editovat jejich strukturuza behu. Plany projektu pak mohou byt libovolne modifikovany, zatımco strukturo-vanı modelu do jednotlivych planu zustava zachovano. Pracuje se s predem defino-vanymi typy planu projektu a s jejich instancemi. Dynamicky lze editovat jak typyplanu, tak jejich jednotlive instance.

Vyhodou prımeho pouzitı OOPN pro modelovanı projektoveho portfolia je adekvatnıstrukturovanı modelu, takze nevznika jedna nestrukturovana sıt’, kde jsou dılcı sıte jednot-livych projektu spojeny do jednoho celku, ale jednotlive sıte existujı a jsou pod kontrolousamostatne (napr. zanik, resp. ukoncenı projektu jsou modelovany adekvatnım zpusobem).Pracuje se tım padem na vyssı urovni nez v prıpade editace jedne nestrukturovane sıte –pojmy problemove domeny jsou v modelu zachovany, vytvorenım modelu se neztracı infor-mace o jednotlivych projektech portfolia. Dalsım prınosem tohoto resenı je zavedenı typu(vzoru) planu, a to jak predem pripravenych, tak i dynamicky vznikajıcıch a dynamickyaktualizovatelnych v prubehu resenı.

Kapitola 11

Zaver

V teto praci byly popsany vybrane aspekty problematiky modelovanı a simulace vyvıjejı-cıch se a nepretrzite bezıcıch systemu, zahrnujıcı jak teoreticka vychodiska, tak moznostiprakticke realizace. Byly uvazovany ruzne aplikacnı oblasti, zahrnujıcı jak automatickou,tak interaktivnı evoluci systemu.

Vyznam DEVS pro modelovanı, simulaci a navrh systemu Hlavnım formalis-mem, pouzitym v tomto textu, je DEVS. Formalizace simulacnıch modelu pomocı DEVSprinası platformne nezavisle simulacnı modely a moznost transformace modelu do ruznychsimulacnıch prostredı. Sofistikovanejsı formalismy, jako jsou naprıklad Petriho sıte a sta-vove diagramy (statecharts) je mozne do DEVS relativne snadno transformovat. S vyuzitımDEVS je mozne srozumitelne a na formalnım zaklade popsat problematiku distribuovanesimulace, viz napr. [ZKP00]. DEVS take hraje vyznamnou ulohu v soucasnych aktivitachv oblasti vyvoje systemu na bazi simulace (Simulation-Based Design and Development),kde koncept zachovanı modelu (Model Continuity) vyznamne prispıva k efektivnosti a bez-pecnosti vyvoje [HZ04]. Hlavnı temata aktualnıho vyzkumu souvisejıcıho s formalismemDEVS lze shrnout takto:

• standardizace modelovaıch formalismu,

• transformace modelu mezi ruznymi formalismy a implementacnımi jazyky,

• metodologie modelovanı a navaznost na metodiky softwaroveho inzenyrstvı,

• interoperabilita nastroju a prenositelnost modelu,

• standardnı knihovny znovupouzitelnych modelu,

• webove sluzby pro simulaci.

Dynamicke prostredı pro modelovanı a simulaci modelu na bazi DEVS, o kterem bylav tomto textu rec, je v souladu s obecnym trendem ve stale vetsı mıre aplikovat dyna-micke programovacı jazyky v realizaci programovych systemu. Vyhodou je rychlejsı vyvojsystemu a moznost sledovat a modifikovat jejich dynamiku, coz vede k lepsımu vhledu dochovanı systemu a tedy ke kvalitneji navzenym systemum. Jednoduchy a srozumitelny for-malnı zaklad modelu na bazi DEVS umoznuje krome simulace a testovanı prımo aplikovati matematicke metody pro analyzu systemu, jejich struktury i chovanı.

102 KAPITOLA 11. ZAVER

Jine formalismy DEVS modeluje system jako stavovy stroj (i kdyz mnozina stavumuze byt i nekonecna) s explicitne vyjadrenym stavem a s explicitne vyjadrenymi pre-chody, modifikujıcımi stav. To nemusı byt na prvnı pohled pro prakticke programovanıprılis vyhodne. DEVS ma ovsem smysl pouzıvat jako komponentnı prostredı, kde s vyhodouvyuzijeme toho, ze jde o volne vazane komponenty, s kterymi je mozne snadno dynamickymanipulovat prave dıky explicitne vyjadrenemu stavu a volne vazbe na ostatnı kompo-nenty. Obvykle prıstupy k programovanı je vyhodne pouzıt uvnitr komponent DEVS. Ma-povanı vybraneho formalismu (jazyka) do komponenty DEVS znamena vyjadrit explicitnestavy a prechody.

V kapitole 6 byla popsana moznost specifikovat komponentu DEVS formalismem OOPN.Vyhodou tohoto prıstupu je citelnejsı, vysokourovnovejsı, vizualnı reprezentovatace mo-delu. Zapouzdrenım interpretu OOPN bylo dosazeno spojenı vyhod paralelnıho objektoveorientovaneho jazyka a komponentnıho prıstupu se snadno dynamicky manipulovatelnymikomponentami. Interpret OOPN zprıstupnuje reflektivnı rozhranı, umoznujıcı s objektyinterpretu manipulovat podobne jako s komponentami DEVS. Vzhledem k charakteru for-malismu jsou zde ale jista omezenı plynoucı z toho, ze objekty (na rozdıl od komponent)jsou provazany referencemi a zachovat konzistenci modelu po editacnıch zasazıch nenızcela jednoduche.1

CAST CAST je zkratka pro Computer-Aided Systems Theory [Pic89]. DEVS, jako mo-delovacı formalismus, ktery bezprostredne z teorie systemu vychazı, dokonale odpovıdakonceptu spojenı pocıtacovych nastroju a teorie systemu. Kazda konkretnı implementaceabstraktnıho simulatoru DEVS je vlastne prımocarou pocıtacovou implementacı teorie sys-temu (s diskretnımi udalostmi). Vezmeme-li v uvahu koncept zachovanı modelu v cıloverealizaci, jde v prıpade DEVS a jinych kompatibilnıch formalismu (DEVS-like systems)o prıklad idealnıho sepetı teorie a praxe tvorby pocıtacovych systemu, kde konkretnı,prakticky realizovane systemy a jejich komponenty jsou soucasne matematickymi objekty,manipulovatenymi v souladu s teoriı a soucasne prımo pouzitelnymi v realnem prostredı.

Pocıtacove nastroje V tomto textu popisovane obecne principy simulacnıho mode-lovanı vyvıjejıcıch se systemu (kapitola 4) jsou ilustrovany konkretnımi implementacemiabtraktnı simulacnı architektury, navrzene prave pro tento typ systemu. Implementacnımprostredım je Smalltalk. V nem vytvorene nastroje SmallDEVS a PNtalk (kapitoly 5 a6) jsou pouzitelne jako pomucky pro studium problematiky modelovanı a simulace a jakodemonstrace nekterych ne zcela beznych prıstupu, jejımz cılem je podporit tvorbu no-vych a dalsı vyvoj existujıcıch simulacnıch nastroju. Propojenı experimentalnıch nastrojuSmallDEVS a PNtalk se soudobymi prumyslove pouzitelnymi a pouzıvanymi nastroji jepotencialne mozne, protoze jako soucast dalsıho vyzkumu se pocıta s moznostı zajistenıinteroperability za pouzitı platformne neutralnıho jazyka DEVSML, na jehoz vyvoji se vkomunite vyzkumnıku z oblasti modelovanı a simulace v soucasne dobe pracuje [MRMZ07].Ve specialnıch prıpadech, kdy nenı treba interoperabilitu s jinymi nastroji resit, lze tytoexperimentalnı nastroje pouzıt prımo. Situaci usnadnuje fakt, ze jde o volne siritelne na-stroje, s jejichz zdrojovym kodem lze dıky liberalnı licenci (MIT) nakladat prakticky bezomezenı.

1Tato problematika je stale predmetem vyzkumu.

103

Originalnı vysledky Hlavnım prınosem teto prace jsou prvnı kroky vedoucı k formali-zaci problematiky vyvıjejıcıch se systemu, zahrnujıcı predevsım dynamickou manipulaci smodely a simulacemi v kontextu navrhu systemu s vyuzitım simulace. Pritom byl kladenduraz na dusledne provazanı teorie modelovanı a simulace (reprezentovane formalismemDEVS) s praxı v podobe nastroju SmallDEVS a PNtalk, ktere byly demonstrovany vnekolika prıpadovych studiıch.

104 KAPITOLA 11. ZAVER

Literatura

[ABPD96] Andrea Asperti, Nadia Busi, Piazza Porta, and S. Donato. Mobile petri nets.Technical report, 1996.

[AG04] Norman P. Archer and Fereidoun Ghasemzadeh. Project portfolio selectionand management. In J.K. Pinto P.W.G. Morris, editor, TheWiley Guide toManaging Projects. Wiley, New York, 2004.

[AM04] K. A. Amin and A. R. Mikler. Agent-based Distance Vector Routing: A Re-source Efficient and Scalable approach to Routing in Large CommunicationNetworks. Journal of Systems and Software, 71(3):215–227, 2004.

[Anb05] F. Anbari. Q & As for the PMBOK Guide. ISBN 1930699395. ProjectManagement Institute, 2005.

[Bar97] F. J. Barros. Modeling formalisms for dynamic structure systems. In ACMTransactions on Modeling and Computer Simulation (TOMACS), 1997.

[Bra87] M. E. Bratman. Intention, Plans, and Practical Reason. Harvard UniversityPress, Cambridge, MA, 1987.

[BWH07] R. H. Bordini, M. Wooldridge, and J. F. Hubner. Programming Multi-AgentSystems in AgentSpeak using Jason (Wiley Series in Agent Technology). JohnWiley & Sons, 2007.

[DdBDM03] M. Dastani, F. de Boer, F. Dignum, and J. Meyer. Programming Agent Deli-beration: an Approach Illustrated Using the 3APL Language. In Proceedingsof AAMAS ’03, pages 97–104, New York, NY, USA, 2003. ACM.

[dLG+04] M. d’Inverno, M. Luck, M. P. Georgeff, D. Kinny, and M. Wooldridge. ThedMARS Architecture: A Specification of the Distributed Multi-Agent Rea-soning System. Autonomous Agents and Multi-Agent Systems, 9(1-2):5–53,2004.

[E. 03] E. I. Hsu and D. L. Mcguinness. Wine Agent: Semantic Web Testbed Ap-plication. In Proceedings of 2003 Description Logics (DL2003), page 5–7.CEUR-WS.org, 2003.

[FIP01] FIPA. FIPA ACL Message Structure Specification. FIPA, 2001.

[GK03] S. Rollins G. Kendall. Advanced Project Portfolio Management and the PMO.J. Ross Publishing, Boca Raton, FL, 2003.

106 LITERATURA

[GL87] M. P. Georgeff and A. L. Lansky. Reactive Reasoning and Planning. In Proce-edings of the Sixth National Conference on Artificial Intelligence (AAAI-87),pages 677–682, Seattle, WA, USA, July 1987. Morgan Kaufmann.

[GR89] A. Goldberg and D. Robson. Smalltalk 80: The Language. Addison-Wesley,1989.

[GR96] Michael Peter Georgeff and Anand S. Rao. A profile of the australian ar-tificial intelligence institute. IEEE Expert: Intelligent Systems and TheirApplications, 11(6):89–92, 1996.

[GVH03] B. P. Gerkey, R. T. Vaughan, and A. Howard. The Player/Stage Project:Tools for Multi-Robot and Distributed Sensor Systems. In Proceedings of the11th International Conference on Advanced Robotics, pages 317–323, 2003.

[Hu04] X. Hu. A Simulation-Based Software Development Methodology for Distribu-ted Real-Time Systems. PhD thesis, The University of Arizona, USA, 2004.

[HY03] X.C. Jiao H.S. Yan, Z. Wang. Modeling, scheduling and simulation of productdevelopment process by extended stochastic high-level evaluation Petri nets.Robotics and Computer-Integrated Manufacturing, 19(4):329–342, 2003.

[HZ04] X. Hu and B. P. Zeigler. Model Continuity to Support Software Developmentfor Distributed Robotic Systems: a Team Formation Example. In Journal ofIntelligent & Robotic Systems, Theory & Application, Special Issue: Multipleand Distributed Cooperating Robots, pages 71–87, 2004.

[Jan95] V. Janousek. PNtalk: Object Orientation in Petri nets. In Proceedings ofEuropean Simulation Multiconference ESM’95, pages 196–200. Prague, CZ,1995.

[Jan98] V. Janousek. Modelovanı objektu Petriho sıtemi. PhD thesis, FEI VUT,Brno, CZ, 1998.

[Jan06] V. Janousek. SmallDEVS. http://www.fit.vutbr.cz/˜janousek/smalldevs,2006.

[JK03] V. Janousek and R. Kocı. PNtalk: Concurrent Language with MOP. InProceedings of the CS&P’2003 Workshop. Warsaw University, Warsawa, PL,2003.

[JK04] V. Janousek and R. Kocı. Towards an Open Implementation of the PNtalkSystem. In Proceedings of the 5th EUROSIM Congress on Modeling andSimulation. EUROSIM-FRANCOSIM-ARGESIM, Paris, FR, 2004.

[JK05a] V. Janousek and R. Kocı. PNtalk Project: Current Research Direction. In Si-mulation Almanac 2005. Faculty of Electrical Engineering, Praha, CZ, 2005.

[JK05b] V. Janousek and R. Kocı. Towards Model-Based Design with PNtalk. InProceedings of the International Workshop MOSMIC’2005. Faculty of ma-nagement science and Informatics of Zilina University, SK, 2005.

LITERATURA 107

[JK06] V. Janousek and E. Kironsky. Exploratory Modeling with SmallDEVS. InProc. of ESM 2006, pages 122–126. EUROSIS, 2006.

[JK07] V. Janousek and R. Kocı. Embedding Object-Oriented Petri Nets into aDEVS-based Simulation Framework. In Proceedings of the 16th InternationalConference on System Science, volume 1, pages 386–395. Wroclaw Universityof Technology, 2007.

[KHS97] H. Kargupta, I. Hamzaoglu, and B. Stafford. Scalable distributed data mining- an agent architecture. In Proceedings the Third International Conferenceon the Knowledge Discovery and Data Mining, page 211–214, Menlo Park,California, 1997. AAAI Press.

[Kit98] H. Kitano, editor. Volume 1395 of Lecture Notes in Computer Science. Sprin-ger, 1998.

[Kli85] G. Klir. Architecture of Systems Problem Solving. Plenum Press, New Yourk,NY, 1985.

[Koc02] Waldemar Kocjan. Dynamic scheduling state of the art report. TechnicalReport T2002:28, Dynamic scheduling state of the art report, 2002.

[Kou01] Adamantios Koumpis. The european ist explantech project. Ubiquity,2(36):1, 2001.

[Lee04] B. Lee. Multi-project management in software engineering using simulationmodeling. Software Quality Journal, 12(1):59–82, 2004.

[Lie86] H. Lieberman. Using Prototypical Objects to Implement Shared Behaviorin Object-Oriented Systems. In OOPSLA ‘86 Conference Proceedings. AlsoSigplan Notices, volume 21, issue 11, pages 214–223, 1986.

[LRS01] R. Laddaga, P. Robertson, and H. Shrobe, editors. Self-Adaptive Software:Applications. Springer, 2001.

[LTO03] Victor Lesser, Milind Tambe, and Charles L. Ortiz, editors. DistributedSensor Networks: A Multiagent Perspective. Kluwer Academic Publishers,Norwell, MA, USA, 2003.

[MA04] H. M. Mosner and R. Allen. Prototypes. http://map.squeak.org, 2004.

[Mae87] P. Maes. Computational reflection. Technical report, Artifical InteligenceLaboratory, Vrije Universiteit Brusel, 1987.

[Maz08] Z. Mazal. Modelovanı uvazujıcıch systemu Petriho sıtemi. PhD thesis, FITVUT, Brno, CZ, 2008.

[MMWY92] H. Masuhara, S. Matsuoka, T. Watanabe, and A. Yonezawa. Object-orientedconcurrent reflective languages can be implemented efficiently. In Proceedingsof the Conference on Object-Oriented Programming Systems, Languages, andApplications (OOPSLA), SIGPLAN Notices, volume 27, number 10, pages127–144. ACM Press, New York, NY, 1992.

108 LITERATURA

[Mos01] Multi-agent based simulation: second international workshop. volume 1979of Lecture notes in computer science: Lecture notes in artificial intelligence,Berlin, 2001. Springer.

[MRMZ07] Saurabh Mittal, Jose Luis Risco-Martın, and Bernard P. Zeigler. Devsml: au-tomating devs execution over soa towards transparent simulators. In Spring-Sim ’07: Proceedings of the 2007 spring simulation multiconference, pages287–295, San Diego, CA, USA, 2007. Society for Computer Simulation Inter-national.

[MVR+06] M. Ceska, V. Janousek, R. Kocı, B. Krena, and T. Vojnar. PNtalk: State ofthe Art. In Proceedings of the Fourth International Workshop on Modellingof Objects, Components, and Agents, pages 301–307. Hamburg, DE, 2006.

[MVT97] M. Ceska, V. Janousek, and T. Vojnar. PNtalk – A Computerized Tool forObject Oriented Petri Nets Modelling. In Proceedings of EUROCAST’97,pages 229–231. Las Palmas de Gran Canaria, ES, 1997.

[MVT02] M. Ceska, V. Janousek, and T. Vojnar. Modelling, Prototyping, and VerifyingConcurrent and Distributed Applications Using Object-Oriented Petri Nets.Kybernetes: The International Journal of Systems and Cybernetics, 2002(9),2002.

[MW97] D. Moldt and F. Wienberg. Multi-Agent-Systems Based on Coloured PetriNets. In Lecture Notes in Computer Science: 18th International Conferenceon Application and Theory of Petri Nets, pages 82–101. Springer-Verlag,1997.

[Paw98] R. Pawlak. Metaobject Protocols For Distributed Programming. Technicalreport, Laboratoire CNAM-CEDRIC, Paris, 1998.

[PBL03] A. Pokahr, L. Braubach, and W. Lamersdorf. Jadex: Implementing a BDI-Infrastructure for JADE Agents. EXP – in search of innovation, 3(3):76–85,2003.

[Pic89] Franz Pichler. From systems theory to cast. In Franz Pichler and RobertoMoreno-Dıaz, editors, EUROCAST, volume 410 of Lecture Notes in Compu-ter Science, pages 2–6. Springer, 1989.

[Pin02] Michael Pinedo. Scheduling: Theory, Algorithms, and Systems. second edi-tion. Prentice Hall, 2002.

[Pin05] Michael Pinedo. Planning and Scheduling in Manufacturing and Services.Springer, 2005.

[PNt06] The PNtalk System. http://www.fit.vutbr.cz/˜janousek/pntalk, 2006.

[Rao96] A. S. Rao. AgentSpeak(L): BDI agents speak out in a logical computablelanguage. In Rudy van Hoe, editor, Seventh European Workshop on ModellingAutonomous Agents in a Multi-Agent World, pages 42–55, Secaucus, NJ,USA, 1996. Springer-Verlag New York, Inc.

LITERATURA 109

[Ren06] Renew – the Reference Net Workshop. http://www.renew.de, 2006.

[SBD+00] S. Subrahmanian, P. Bonatti, J. Dix, T. Eiter, S. Kraus, F. Ozcan, andR. Ross. Heterogeneous Agent Systems. MIT Press/AAAI Press, Cambridge,MA, USA, 2000.

[Sch05] K. Schwalbe. Information Technology Project Management, Fourth Edition.ISBN 1930699395. Course Technology, 2005.

[Skl97] J. Sklenar. Intorduction to OOPN in SIMULA.http://staff.um.edu.mt/jskl1/talk.html, 1997.

[Spi92] M. Spinner. Elements of Project Management: Plan, Schedule, and Control,2nd Ed. Englewood Cliff, NJ, Prentice Hall, 1992.

[TUN06] The TUNES Project for a Free Reflective Computing System.http://tunes.org, 2006.

[Uhr01] A. M. Uhrmacher. Dynamic structures in modeling and simulation: a re-flective approach. ACM Transactions on Modeling and Computer Simulation(TOMACS), 11:206–232, 2001.

[US87] D. Ungar and R. Smith. SELF: The Power of Simplicity. In OOPSLA ‘87Conference Proceedings, pages 227–241, 1987.

[Val98] R. Valk. Petri Nets as Token Objects: An Introduction to Elementary ObjectNets. In Jorg Desel, Manuel Silva (eds.): Application and Theory of PetriNets; Lecture Notes in Computer Science, volume 120. Springer-Verlag, 1998.

[Van00] H. Vangheluwe. Multi-formalism Modelling and Simulation. PhD thesis,Faculty of Science, Ghent University (UGent), December 2000.

[WH02] D. Weyns and T. Holvoet. A Colored Petri Net for a Multi-Agent Appli-cation. In Components, Objects and Agents, MOCA02. Computer ScienceDepartment, Aarhus University, 2002.

[Woo02] M. Wooldridge. Introduction to MultiAgent Systems. John Wiley & Sons,2002.

[YC06] Z. Yu and Y. Cai. Object-Oriented Petri nets Based Architecture Descrip-tion Language for Multi-agent Systems. International Journal of ComputerScience and Network Security, 6(1B):123–131, 2006.

[Zei84] B. P. Zeigler. Multifacetted Modelling and Discrete Event Simulation. Aca-demic Press Prof., Inc., San Diego, CA, 1984.

[Zei90] B. P. Zeigler. Object-Oriented Simulation with Hierarchical, Modular Models:Intelligent Agents and Endomporphic Systems. Academic Press Prof., Inc.,San Diego, CA, 1990.

[ZKP00] B. Zeigler, T. Kim, and H. Praehofer. Theory of Modeling and Simulation.Academic Press, Inc., London, UK, 2000.

Date post:	15-Oct-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Simulace a n avrh vyv ´jej ´c ´ch se´ syst emujanousek/publications/2008-habilitace.pdf ·...

Documents