Podcast na Diskrétní simulace událostí: Principy a implementace

Kapitoly

Úvod

Co je to diskrétní simulace?

Událost versus Proces

Čtyři stavy každého procesu

Magický kalendář událostí

Nástroje v praxi

Stavební kameny: Seznamy

Jak zařídit (kontrolovaný) chaos

Srdce simulace: Procesy

Velké finále a shrnutí

Přepis

Tereza: Představte si, že sedíte u zkoušky a na papíře vám přistane otázka na diskrétní simulaci. Pro většinu studentů je to přesně ten moment, kdy začnou panikařit. Je to téma, které prý zaskočí osm z deseti lidí.

Adam: Ale vás ne. Protože my vám teď ukážeme ten klíčový princip, díky kterému v tom už nikdy nebudete tápat. Je to jednodušší, než si myslíte.

Tereza: Přesně tak. Tohle je Studyfi Podcast.

Tereza: Adame, tak pojďme na to. Co to vlastně je ta diskrétní simulace? Zní to... no, hodně technicky.

Adam: Zní, ale princip je snadný. Představ si, že nehraješ počítačovou hru, kde se všechno hýbe plynule, ale stolní hru, třeba Člověče, nezlob se.

Tereza: Dobře, to znám. Tam se nehýbu pořád, jen když jsem na řadě.

Adam: Přesně! A to je diskrétní simulace v kostce. Systém – v tomto případě vaše hra – nemění svůj stav plynule, ale jen v určitých, oddělených okamžicích. Těm okamžikům říkáme události.

Tereza: Takže událost je třeba... hod kostkou?

Adam: Ano! Hodíš kostkou, posuneš figurku. Mezi tvým a dalším hodem se stav hry nemění. Všechno jakoby zamrzne. Čas skáče z jedné události na druhou, neplyne souvisle. Proto je to diskrétní – skokové.

Tereza: Aha! Takže charakteristiky jsou... diskrétní čas, náhoda – tedy stochastické chování, jako ten hod kostkou...

Adam: A taky fronty! Přemýšlej o tom – ostatní hráči čekají ve frontě, než na ně přijde řada. A to je další typický znak diskrétních simulací. Používají se třeba na modelování front v bance, provozu na křižovatce nebo toku pacientů v nemocnici.

Tereza: Dobře, takže základem je „událost“. Ale v podkladech se mluví i o „procesech“. Jaký je v tom rozdíl?

Adam: Skvělá otázka, Terezo. To je další klíčový bod. Událost je okamžitá změna. Blesk. Hod kostkou, příchod zákazníka, příjezd autobusu. Je to bod v čase.

Tereza: A proces?

Adam: Proces je celý příběh. Je to posloupnost logicky navazujících událostí. V našem Člověče, nezlob se, tvůj proces je celá cesta jedné figurky od startu až do domečku. Skládá se z mnoha událostí – mnoha hodů kostkou a posunů.

Tereza: Takže proces je jako film a události jsou jednotlivé snímky?

Adam: Perfektní přirovnání! A co je na tom zajímavé, v simulaci běží těchhle „filmů“ spousta najednou. Každý hráč má svůj proces. Počítač mezi nimi ale jen bleskově přepíná. Vypadá to, že se dějí paralelně, ale ve skutečnosti v jeden daný okamžik běží vždy jen jeden.

Tereza: Tomu se říká kvaziparalelní zpracování, že? Jako když žonglér vyhazuje do vzduchu několik míčků – vypadá to, že jsou všechny ve vzduchu najednou, ale on se v každém okamžiku dotýká jen jednoho.

Adam: Přesně tak! Žonglér je náš procesor.

Tereza: Fajn, takže máme několik procesů, které se střídají. Ale asi neběží pořád dokola, že ne? Co se s nimi děje?

Adam: Správně, každý proces může být v jednom ze čtyř stavů. A zase si to ukážeme na naší hře. První stav je jednoduchý: Aktivní.

Tereza: To budu já, když jsem zrovna na tahu a házím kostkou.

Adam: Bingo. V každém okamžiku simulace je aktivní právě jeden proces. Ten, který právě teď něco dělá. Pak máme stav Pozastavený.

Tereza: To zní, jako když musím stát na políčku „Čekej dvě kola“.

Adam: Přesně! Tvůj proces je pozastavený. Víme přesně, kdy se znovu aktivuje – za dvě kola. Je naplánovaný do budoucna. Třetí stav je Pasivní.

Tereza: A to je co? To je, když jen čekám, až na mě přijde řada?

Adam: Ano, ale je v tom drobný rozdíl. V pasivním stavu proces neví, kdy bude aktivován. Jen tak čeká. Třeba tvoje figurka čeká ve startovním domečku. Není naplánovaná, jen čeká, až hodíš šestku, což je událost z jiného procesu, která ji aktivuje.

Tereza: Takže pozastavený má lístek s časem, kdy má jet, a pasivní jen čeká na zastávce, jestli vůbec něco pojede.

Adam: Krásně řečeno! A poslední stav je Ukončený. To je snadné – tvoje figurka je v domečku. Její příběh, její proces, skončil. Už se nikdy nemůže znovu aktivovat.

Tereza: Dobře, teď mi ale řekni to nejdůležitější. Jak ten počítačový žonglér ví, který míček má chytit příště? Jak si pamatuje, kdo má čekat dvě kola a kdo čeká na šestku? To musí být neuvěřitelný chaos!

Adam: A tady přichází ten slibovaný „aha“ moment. Ten trik, který mate tolik studentů, ale ve skutečnosti je geniálně jednoduchý. Není to žádný chaos. Všechno řídí takzvaný Kalendář událostí.

Tereza: Kalendář událostí. Co to je?

Adam: Představ si ho jako diář nebo chytrou to-do listinu. Ale má jednu superschopnost: je neustále seřazený podle času. Každý pozastavený proces si do něj zapíše poznámku: „Hej, mě probuď v čase X.“

Tereza: A kalendář je udrží seřazené? Takže nahoře je vždy ta nejbližší událost?

Adam: Přesně tak! Simulační program se nemusí pořád dokola všech procesů ptát: „Už jsi na řadě? A co ty?“ Prostě se jen podívá na první položku v kalendáři, zjistí, co se má stát a v jakém čase, provede to a položku smaže.

Tereza: To je elegantní. Takže ten klíč k efektivitě je to neustálé třídění.

Adam: Ano. A technicky je to nejčastěji implementováno jako takzvaný spojový seznam. To je datová struktura, kde každý prvek ví, který je před ním a který za ním. Když přidáváš novou událost, nemusíš přerovnat celý seznam, jen ji chytře vložíš na správné místo. Je to extrémně rychlé.

Tereza: Takže ten velký strašák jménem diskrétní simulace je ve skutečnosti jen o chytrém, seřazeném diáři, který říká, co se má dít dál. To je ono?

Adam: V jádru ano. To je ten řídící mozek celé operace.

Tereza: A když bychom si to chtěli naprogramovat, v čem se to dělá? Existují na to nějaké speciální nástroje?

Adam: Určitě. Historicky byl úplně prvním jazykem, který tohle uměl, jazyk s příhodným názvem SIMULA. Vznikl už v 60. letech v Norsku a je to vlastně dědeček všech objektově orientovaných jazyků, včetně Javy nebo C++.

Tereza: Takže bez simulací bychom možná neměli Javu, jak ji známe?

Adam: Je to tak. Měl obrovský vliv. Dnes se ale pro diskrétní simulace často používá právě Java, pro kterou existuje spousta knihoven. Třeba balík, se kterým se studenti často setkají, se jmenuje javaSimulation.

Tereza: A ten obsahuje už hotové nástroje na ten kalendář?

Adam: Přesně. Obsahuje třídy jako Link, Linkage a Head, což jsou přesně ty stavební kameny pro vytvoření toho rychlého, obousměrného spojového seznamu, o kterém jsme mluvili. Nemusíš vynalézat kolo, jen použiješ hotové a osvědčené součástky.

Tereza: Takže abychom to shrnuli. Diskrétní simulace modeluje systémy, které se mění ve skocích, jako stolní hra. Základem jsou okamžité události, které tvoří delší procesy. A celý ten zdánlivý chaos řídí geniálně jednoduchý princip: kalendář událostí, seřazený seznam, který vždy ví, co se má stát příště.

Adam: Naprosto přesně. A to je to, co potřebujete vědět, aby vás ta zkoušková otázka už nikdy nezaskočila.

Tereza: Super, to dává perfektní smysl. Děkuju, Adame. A když už jsme u těch modelů, co se podívat na něco úplně jiného – na modely, které se učí samy?

Adam: Skvělá otázka, Terezo. Od diskrétních simulací je k samoučícím se modelům jen krůček. Ale než se tam dostanem, musíme si ukázat, v čem se takové modely vlastně staví. A pro spoustu studentů je odpovědí... Java. Konkrétně knihovna JavaSimulation.

Tereza: JavaSimulation... to zní jako něco, co by mohlo být u zkoušky, že?

Adam: Trefa do černého. Ale žádný strach. Není to tak složité, jak se zdá. Představte si to jako... velkou krabici s Legem. Máte tam přesně ty kostičky, které potřebujete k postavení jakékoliv simulace.

Tereza: Dobře, Lego mi dává smysl. Jaké jsou tedy ty základní kostičky?

Adam: Všechno začíná u propojování. K tomu slouží třídy Linkage, Link a Head. Zní to technicky, ale je to jednoduché. Head je jako nádraží. Ví, který vagón je první a který poslední.

Tereza: A Linkage a Link jsou ty vagóny?

Adam: Skoro. Linkage je ten spojovací mechanismus mezi vagóny. A Link je ten samotný vagón, který už ten mechanismus má. S metodami jako into nebo follow pak můžete vagóny připojovat na konec vlaku nebo za jiný konkrétní vagón. Je to prostě způsob, jak efektivně spravovat seznamy prvků.

Tereza: Takže si vlastně stavíme takový datový vlak. To se mi líbí.

Adam: Přesně tak. Ale co by to bylo za simulaci bez trochy náhody? Od toho je tu třída Random.

Tereza: Generátor náhodných čísel, předpokládám.

Adam: Ano, ale je to víc než jen házení kostkou. Můžete si vybrat z různých typů náhody – takzvaných rozložení. Chcete rovnoměrné? Máte uniform. Nebo slavné Gaussovo normální rozložení? Na to je metoda normal. Můžete si tak nasimulovat cokoliv, od příjezdu zákazníků do obchodu po výšku lidí v populaci.

Tereza: A co ten „seed“, o kterém se často mluví?

Adam: To je geniální věc. Seed je vlastně počáteční číslo pro generátor. Když použijete stejný seed, dostanete vždycky tu samou „náhodnou“ sekvenci čísel. To je klíčové pro ladění. Můžete si tak simulaci pustit stokrát a vždycky poběží stejně, dokud neopravíte chybu.

Tereza: Takže je to vlastně... kontrolovaný chaos.

Adam: Přesně. Jsme přece programátoři, potřebujeme mít chaos pod kontrolou.

Tereza: Dobře, máme vlaky a máme náhodu. Ale co je to hlavní, co tu simulaci vlastně pohání?

Adam: Tím se dostáváme k absolutnímu jádru – ke třídě Process. Tohle je ta nejdůležitější kostička v celém Legu. Každá aktivní věc ve vašem modelu – zákazník, auto, stroj – bude Process.

Tereza: A co takový proces umí?

Adam: Každý proces má svůj vlastní životní příběh. Ten se píše do metody actions. Tam mu řeknete, co má dělat. A pak ho řídíte jako loutku. Metodou activate ho pošlete na scénu, tedy zaplánujete do kalendáře událostí.

Tereza: A co když má mít pauzu?

Adam: Na to je hold. Řeknete hold(10) a proces si na 10 časových jednotek zdřímne. Pak je tu passivate, kterým ho uspíte úplně, dokud ho jiný proces nevzbudí. A spousta dalších, jako wait pro čekání ve frontě nebo cancel pro jeho úplné stažení ze hry.

Tereza: Takže je to vlastně takový herec na jevišti... Má svůj scénář v actions a my ho jako režiséři posíláme na scénu, necháváme čekat v zákulisí nebo ho posíláme domů.

Adam: Lepší přirovnání bych nevymyslel! A právě ten kalendář událostí, o kterém jsme mluvili minule, je tady schovaný pod statickou proměnnou SQS.

Tereza: Páni. Takže když to propojíme, Process je ten herec. Atribut EVTIME říká, kdy má jít na scénu. A metoda actions je jeho scénář. Všechno to řídí neviditelný režisér – ten kalendář SQS.

Adam: Naprosto přesně. A když herec dohraje svou roli, jeho atribut TERMINATED se nastaví na true a je konec. Všechny ty stavy – aktivní, pasivní, pozastavený, ukončený – jsou jen různé fáze jeho života na tom našem simulačním jevišti.

Tereza: Adame, to bylo skvělé. Mám pocit, že se na tyhle třídy v Javě už nedívám jako na hromadu kódu, ale jako na živý systém. Takže abychom to celé uzavřeli...

Adam: Diskrétní simulace modeluje události ve skocích. Základem je kalendář událostí, který ví, co se stane dál. A když to chcete naprogramovat v Javě, sáhnete po knihovně JavaSimulation. Ta vám dá všechny nástroje – Link pro seznamy, Random pro náhodu a hlavně Process pro definování samotných aktérů simulace.

Tereza: A s tímhle v hlavě by nás ta zkoušková otázka už opravdu neměla překvapit. Děkuju moc, Adame!

Adam: Není za co, Terezo. Držím všem palce. Pamatujte, není to o biflování, ale o pochopení principů. A ty teď znáte. Zvládnete to.

Tereza: Díky za poslech Studyfi Podcastu. U příštího dílu se těšíme na slyšenou!