M A S A R Y K O V A UNIVERZITA
F A K U L T A INFORMATIKY
Interaktivní animační prostředí pro
ilustraci distribuovaných algoritmů
D I P L O M O V Á PRÁCE
Miroslav Rabušic
Brno, podzim 2016
Prohlášení
Prohlašuji, že tato diplomová práce je mým původním autorským dílem,
které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu,
které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji
s uvedením úplného odkazu na příslušný zdroj.
Miroslav Rabušic
Vedoucí práce: doc. Ing. Jan Staudek, CSc.
ii
Poděkování
Děkuji vedoucímu práce doc. Ing. Janu Staudkovi, CSc. za podnětné rady.
iii
Shrnutí
Cílem této práce je navrhnout a implementovat interaktivní webové orientovaný
systém, který umožňuje prezentaci a studium chování distribuovaných
algoritmů. Výsledný systém umožňuje definovat procesní prostředí,
na němž bude chování algoritmu ilustrováno. Animační systém nabízí
možnost sledování průběhu algoritmu jak plynule, tak i po krocích reprezentujících
výměny zpráv mezi uzly distribuovaného systému, přičemž
umožňuje i návrat do předchozích stavů. Systém také poskytuje informace
o komunikační složitosti aktuálně řešené úlohy. Chování výsledného systému
je prezentováno implementací animací algoritmu předávání příznaku
v kruhové topologii, Raymondova algoritmu, Hirschberg-Sinclairova
algoritmu a algoritmu pro totální řazení zpráv při skupinové komunikaci
pomocí sekvenceru.
iv
Klíčová slova
animace algoritmů, webová aplikace, distribuovaný systém, distribuovaný
algoritmus, předávání příznaku v kruhové topologii, Raymondův algoritmus,
Hirschberg-Sinclairův algoritmus, totální řazení zpráv při skupinové
komunikaci pomocí sekvenceru, ASP.NET MVC, JavaScript
v
Obsah
1 Úvod 3
2 Distribuované algoritmy a jejich animace 5
2.1 Distribuované algoritmy 5
2.2 Nástroje pro animaci algoritmů 6
3 Analýza a návrh animačního systému 7
3.1 Požadavky na animační systém 7
3.1.1 Funkční požadavky 7
3.1.2 Nefunkční požadavky 8
3.2 Použité technologie 8
3.2.1 ASP.NET MVC 8
3.2.2 HTML 9
3.2.3 CSS 9
3.2.4 JavaScript 9
3.2.5 Použité knihovny 10
3.3 Architektura systému 11
3.3.1 Klientská část 11
3.3.2 Serverová část 19
4 Implementované algoritmy 21
4.1 Distribuované vzájemné vyloučení 21
4.1.1 Předávání příznaku v kruhové topologii 21
4.1.2 Raymondův algoritmus 24
4.2 Volba vedoucího prvku 27
4.2.1 Hirschberg-Sinclairův algoritmus 27
4.3 Multicasting 30
4.3.1 Totální řazení zpráv pomocí sekvenceru 30
1
O B S A H
5 Rozšiřování aplikace 34
5.1 Implementace animace algoritmu 34
5.2 Lokalizace uživatelského rozhraní do dalších jazyků 39
6 Administrace systému 43
6.1 Předdefinovaná prostředí a běhy algoritmů 43
6.2 Nastavení klientské části aplikace 43
7 Závěr 46
Seznam použité literatury 47
Seznam příloh 52
2
1 Úvod
Při výuce nebo studiu chování algoritmů může být vhodné využít nástroje,
které umožňují sledovat akce, které daný algoritmus provádí. K tomuto
účelu slouží animační nástroje, které vizualizují běh algoritmu a zobrazují
změny, které algoritmus provádí.
Tato práce se zaměřuje na vizualizaci distribuovaných algoritmů. Jejím
cílem je navrhnout a implementovat interaktivní webově orientovaný systém,
který umožňuje prezentaci a studium chování distribuovaných algoritmů.
Výsledný systém dovoluje definovat procesní prostředí, na němž
bude chování algoritmu ilustrováno. Animační systém nabízí možnost sledování
průběhu algoritmu jak plynule, tak i po krocích reprezentujících
výměny zpráv mezi uzly distribuovaného systému, přičemž umožňuje
i návrat do předchozích stavů. Systém také poskytuje informace o komunikační
složitosti aktuálně řešené úlohy.
Chování implementovaného systému je prezentováno na následujících
algoritmech: předávání příznaku v kruhové topologii [32], Raymondův algoritmus
[33], Hirschberg-Sinclairův algoritmus [35] a totální řazení zpráv
při skupinové komunikaci pomocí sekvenceru [39].
Kapitola této práce nazvaná Distribuované algoritmy a jejich animace
představuje distribuované systémy a algoritmy a stručně shrnuje současnou
situaci v oblasti nástrojů pro animaci algoritmů.
Další kapitola se zabývá analýzou a návrhem animačního systému.
Shrnuje požadavky kladené na implementovaný systém a představuje nástroje,
které byly na základě požadavků vybrány pro implementaci systému.
Tato kapitola také představuje strukturu základních částí systému
pomocí diagramů tříd.
V následující kapitole jsou stručně představeny algoritmy, jejichž animace
byly v animačním systému vytvořeny, a je nastíněna podoba, ve
které byly tyto algoritmy implementovány.
Následuje kapitola, která popisuje postupy pro rozšíření animačního
systému o animace dalších algoritmů. Tato kapitola také poskytuje návod,
jak lokalizovat uživatelské rozhraní aplikace do dalších jazyků.
Předposlední kapitola práce se zabývá administrací animačního systému,
zejména správou předdefinovaných prostředí pro běh animovaných
3
1. Ú V O D
algoritmů a nastaveními umožňujícími definovat některé parametry uživatelského
rozhraní.
Závěr shrnuje výsledky této práce a nastiňuje možnosti budoucího vývoje
animačního systému.
4
2 Distribuované algoritmy a jejich animace
2.1 Distribuované algoritmy
Distribuovaný systém [1] je množina autonomních výpočetních komponent
(jednotek, procesoru, zařízení, ...) vzájemně propojených nějakou komunikační
strukturou. Distribuovaný systém může být využit například
pro: výměnu informací, sdílení zdrojů, paralelizaci za účelem zvýšení výkonnosti,
replikaci za účelem zvýšení spolehlivosti apod.
Distribuovaný algoritmus [2] je agregací algoritmů běžících v jednotlivých
komponentách distribuovaného systému. Komponenty distribuovaného
systému mění svůj lokální stav a vzájemně interagují. Změnou
lokálního stavu a interakcí jednotlivých komponent se mění stav distribuovaného
systému, který se postupně nachází v jednotlivých konfiguracích.
Každá konfigurace systému je určena okamžitými lokálními stavy všech
komponent a stavy komunikačních médií (přenášené zprávy, obsahy komunikačních
bufferů, ...).
Distribuovaný výpočet je provedení výpočtu podle distribuovaného algoritmu
v distribuovaném systému. Je to posloupnost diskrétních událostí
(přechodů mezi stavy distribuovaného systému). Jestliže procesy distribuovaného
systému při dosahování společného cíle kooperují, pak musí mít
přístup ke globálnímu stavu distribuovaného systému. Znalost globálního
stavu je komplikována následujícími faktory:
• Kterýkoliv z procesů distribuovaného systému může kdykoliv vypadnout
(selhat) a ostatní procesy se o tom nemusí dozvědět.
• Výměna zpráv může selhat, a i když neselže, vesměs se odehrává
v nepředvídatelném čase.
• Je nedosažitelný jednotný běh reálného času, který je v jednotlivých
komponentách distribuovaného systému řízen lokálními hodinami
běžícími v těchto komponentách.
Distribuované systémy se od paralelních multiprocesorových systémů liší
v následujících aspektech:
• Neznalost globálního stavu - proces obvykle nezná lokální stavy
ostatních procesů.
5
2. DISTRIBUOVANÉ ALGORITMY A JEJICH A N I M A C E
• Nedostupnost globálního časového rámce - události nelze uspořádat
podle času jejich výskytu.
• Nedeterminismus - souběh procesů je nedeterministický, opakovaný
běh týchž procesů může generovat různé výsledky.
2.2 Nástroje pro animaci algoritmů
Existuje celá řada nástrojů zabývajících se vizualizací průběhu algoritmů.
Zaměřme se pouze na interaktivní nástroje s webovým rozhraním, které
běží přímo ve webovém prohlížeči bez nutnosti instalace dalších doplňků
nebo programů. Z této skupiny lze zmínit například Data Structure Visualizations
[3], VisuAlgo [4] nebo Algorithm Animations and Visualizations [5].
Tyto nástroje se zabývají animací algoritmů z různých oblastí, například:
algoritmy pro práci s datovými strukturami, řadicí algoritmy, grafové algoritmy
a další. Žádný z těchto nástrojů však nenabízí animaci distribuovaných
algoritmů.
Nástroje umožňující animaci distribuovaných algoritmů je poměrně
obtížné najít. Jediné nástroje, které se podařilo objevit jsou: ViSiDiA [6],
DAJ[7]aLYDIAN [8].
Nástroj ViSiDiA jako jediný z výše uvedených může běžet ve webovém
prohlížeči, avšak jen ve formě Java appletu [9], a tudíž vyžaduje instalaci
běhového prostředí Java Runtime Environment [10]. Na webové stránce
[11] nástroje ViSiDiA jsou k dispozici také Flash animace [12] několika vybraných
distribuovaných algoritmů. Tyto animace však kromě restartování
neumožňují žádnou interakci ze strany uživatele.
Nástroj DAJ je desktopová aplikace napsaná v jazyce Java, a proto
stejně jako ViSiDiA vyžaduje instalaci běhového prostředí Java Runtime
Environment. Vizualizace běhu algoritmu je v tomto nástroji prováděna
textovou formou (nástroj vypisuje zprávy, které si mezi sebou uzly distribuovaného
systému předávají, a události, ke kterým v systému dochází).
Nástroj LYDIANje dostupný pouze ve formě zdrojového kódu a je primárně
určen pro systémy unixového typu. Zdrojové kódy je však možné
zkompilovat také pro operační systémy Windows. [13]
Z výše uvedených informad vyplývá, že neexistuje jednoduše dostupný
nástroj umožňující animaci běhu distribuovaných algoritmů.
6
3 Analýza a návrh animačního systému
Cílem práce je navrhnout a implementovat webové orientovaný systém,
který umožní prezentaci a studium chování distribuovaných algoritmů.
3.1 Požadavky na animační systém
3.1.1 Funkční požadavky
• Uživatel má možnost definovat procesní prostředí pro běh algoritmu
(např. počet uzlů distribuovaného systému a jejich iniciální stavy, případně
topologii systému).
• Animační systém umožňuje sledování průběhu algoritmu jak po jednotlivých
krocích, tak i plynule.
• Lze měnit rychlost animace průběhu algoritmu.
• Animační systém zobrazuje zprávy informující uživatele o průběhu
algoritmu a o změnách, ke kterým v systému, v němž animovaný algoritmus
běží, dochází.
• Uživatel se může mezi jednotlivými stavy distribuovaného systému
libovolně pohybovat oběma směry (animační systém umožňuje návrat
do předchozích stavů).
• Animační systém poskytuje informace o komunikační složitosti aktuálně
řešené úlohy (informuje uživatele o počtu přenesených zpráv).
• Uživatel má možnost ovlivnit průběh algoritmu (tzn., že může definovat
některé akce prováděné uzly distribuovaného systému, například
pro algoritmy pro vzájemné vyloučení může určit okamžik, kdy
chce uzel vstoupit do kritické sekce).
• Prostředí vytvořená pro běh algoritmů lze spolu s akcemi ovlivňujícími
průběh algoritmu ukládat do souboru a následně ze souboru také
načíst.
• Animační systém umožňuje vytvořit kolekci předdefinovaných běhových
prostředí a nabízí uživateli možnost jejich načtení. Kolekce předdefinovaných
běhových prostředí je součástí animačního systému.
7
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
3.1.2 Nefunkční požadavky
• Systém běží v prostředí webového prohlížeče bez nutnosti instalace
nebo spouštění dalších aplikací.
• Minimalizace množství komunikace mezi serverovou a klientskou
částí animačního systému.
3.2 Použité technologie
3.2.1 ASP.NET MVC
ASP.NET MVC [14] je framework pro vytváření webových aplikací, který
implementuje architektonický vzor Model-View-Controller (MVC). MVC
rozděluje aplikaci na tři hlavní komponenty:
• Model - reprezentuje data a související operace.
• View (pohled) - slouží k prezentaci dat (zobrazuje uživatelské rozhraní
aplikace). Převádí data reprezentovaná modelem do podoby
vhodné k interaktivní prezentaci uživateli.
• Controller (řadič) - řídí tok událostí aplikace, zpracovává interakci
uživatele, pracuje s modely a určuje, který pohled bude zobrazen. Radič
reaguje na události (typicky pocházející od uživatele) a zajišťuje
změny v modelu nebo v pohledu.
Framework ASP.NET MVC byl použit pro implementaci serverové části
aplikace. Velká část animačního systému, zejména tedy běh algoritmu, jeho
animace a další související operace, jsou prováděny na straně klienta za
účelem minimalizace množství komunikace mezi serverem a klientem.
Server tedy jen obsluhuje požadavky klientů na zobrazení jednotlivých algoritmů.
Jako odpověď zasílá webovou stránku, která se stará o animaci
algoritmu.
Pro vytváření uživatelského rozhraní obsahuje ASP.NET MVC technologii
ASP.NET Razor [15]. Jedná se o značkovací syntaxi, která se používá
při vytváření dynamických webových stránek. Umožňuje vložit kód napsaný
v jazyce C# nebo Visual Basic přímo do webové stránky - kombinuje
HTML značkování, příkazy programovacího jazyka a šablony pro generování
výsledné HTML stránky.
8
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
ASP.NET MVC a ASP.NET Razor umožnily rozdělení uživatelského rozhraní
na moduly. Jednotlivé webové stránky tvořící uživatelské rozhraní
aplikace jsou z těchto modulů poskládány, což umožňuje snazší implementaci
animace nových algoritmů. Tyto technologie byly také zvoleny
z důvodu předchozích zkušeností s jejich využitím při tvorbě webových
aplikací.
3.2.2 HTML
HTML [16] je značkovací jazyk používaný pro tvorbu webových stránek.
Součástí jazyka HTML je element canvas [17], který slouží pro dynamické
vykreslování grafických objektů, a lze jej tedy vhodně využít pro vykreslení
distribuovaného systému a animaci průběhu algoritmu běžícího v daném
systému. Element canvas je podporován všemi moderními webovými
prohlížeči. [18; 19] Díky tomu může aplikace běžet v prostředí webového
prohlížeče bez nutnosti instalace nebo spouštění zásuvných modulů nebo
dalších aplikací.
3.2.3 CSS
Kaskádové styly (Cascading Style Sheets, CSS) [20] jsou jazyk pro popis
vzhledu a formátování dokumentů napsaných pomocí značkovacího jazyka.
Nejčastěji je využíván pro změnu vzhledu webových stránek a uživatelských
rozhraní napsaných pomocí HTML a XHTML. Jazyk však lze
použít pro libovolný typ XML dokumentu.
3.2.4 JavaScript
JavaScript [21] je multiplatformní, objektově orientovaný skriptovací jazyk.
Používá se zpravidla jako interpretovaný programovací jazyk pro webové
stránky. Často je vkládaný přímo do HTML kódu stránky. S jeho
pomocí jsou obvykle ovládány interaktivní prvky uživatelského rozhraní
(tlačítka, textová pole apod.) nebo tvořeny různé animace a efekty.
Převážná část aplikace - ta část, která běží na straně klienta - je napsána
v jazyce JavaScript. Tento jazyk je využit pro implementaci animací algoritmů
(kreslení na element canvas se provádí pomocí JavaScriptu [17]), implementaci
běhů algoritmů a je také využit pro obsluhu ovládacích prvků
uživatelského rozhraní. JavaScript, stejně jako HTML, umožňuje aplikaci
9
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
běžet v prostředí webového prohlížeče bez nutnosti instalace nebo spouštění
zásuvných modulů nebo dalších aplikací.
3.2.5 Použité knihovny
• jQuery [22] - multiplatformní knihovna jazyka JavaScript, která klade
důraz na interakci mezi jazykem JavaScript a H T M L . Zjednodušuje
procházení H T M L dokumentů, výběr elementů, vytváření animací,
obsluhu událostí a vývoj aplikací využívajících technologii AJAX [23].
Knihovna je snadno rozšiřitelná pomocí zásuvných modulů. V aplikaci
je knihovna jQuery využita zejména pro manipulaci s ovládacími
prvky uživatelského rozhraní (pro jejich skrývání, zobrazování, povolování
a zakazování podle průběhu animace algoritmu a akcí uživa­
tele).
• Bootstrap [24] - sada nástrojů pro tvorbu webu a webových aplikací.
Obsahuje šablony založené na H T M L a CSS sloužící pro úpravu typografie,
formulářů, tlačítek, navigace a dalších komponent uživatelského
rozhraní. Bootstrap je využit pro sjednocení vzhledu rozhraní
aplikace v různých prohlížečích a s jeho pomocí je také vytvořena nabídka
pro přepínání jazyků uživatelského rozhraní.
• Bootstrap-select [25] - zásuvný modul pro knihovnu jQuery, který
využívá Bootstrap a slouží pro vytváření rozbalovacích nabídek s rozšířenou
funkcionalitou (oproti H T M L elementu select). Bootstrap-select
je použit pro rozbalovací nabídky v rámci sjednocení vzhledu
rozhraní aplikace v různých prohlížečích.
• Bootstrap-slider [26] - zásuvný modul pro knihovnu jQuery, který
využívá Bootstrap a slouží pro vytváření posuvníků umožňujících
uživateli zvolit hodnotu. S jeho pomod lze vytvářet také posuvníky
umožňující zvolit interval hodnot. Bootstrap-slider je využit pro posuvníky
pro volbu délky zobrazení komunikace a stavu systému, pro
volbu intervalu hodnot pro délku kritické sekce při animaci Raymondova
algoritmu a také pro volbu intervalu hodnot pro zpoždění zpráv
při animaci algoritmu pro totální řazení zpráv pomocí sekvenceru.
• Underscore.js [27] - knihovna jazyka JavaScript obsahující funkce pro
práci s kolekcemi dat, poli a objekty. Knihovna je použita pro permutace
prvků pole, pro porovnávání obsahů a výpočty rozdílů polí.
10
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
3.3 Architektura systému
3.3.1 Klientská část
Implementované algoritmy a animace jejich průběhů běží ve webovém
prohlížeči na straně klienta. Jediná komunikace se serverem probíhá ve
chvíli, kdy je načtena animace algoritmu (tedy uživatel otevře webovou
stránku s daným algoritmem), a případně ve chvíli, kdy jsou načtena předdefinovaná
prostředí pro běh algoritmu. Ta se načítají na žádost uživatele.
Skripty tvořící klientskou část je možné rozdělit do dvou skupin,
z nichž jedna reprezentuje animovaný algoritmus a distribuovaný systém,
ve kterém algoritmus běží, a druhá slouží pro manipulaci s elementy webové
stránky a reaguje na vstupy uživatele.
Z požadavků kladených na výslednou aplikaci vyplývá, že uživateli
má být umožněno nejen postupné sledování průběhu algoritmu, ale má
mít i možnost návratu do předchozích stavů. Systém, ve kterém algoritmus
běží, je proto navržen tak, aby mohl uchovávat posloupnost měnících se
stavů. Systém je reprezentován třídou System [Obrázek 1]. Úkolem této
třídy je provádění základních operací se systémem, jako jsou přidávání,
odebírání a aktualizace uzlů a komunikačních spojů, přístup k jednotlivým
stavům systému, přepínání mezi nimi a jejich úpravy. Systém také umí vykreslit
svůj aktuální stav a umožňuje vygenerování systému s kruhovou
topologií nebo s topologií úplného grafu.
Posloupnost kroků algoritmu je uchovávána jako posloupnost měnících
se stavů systému. Stav systému (reprezentovaný třídou SystemState
[Obrázek 2]) uchovává globální stav systému v jednom okamžiku. Stav se
skládá z uzlů a komunikačních spojů systému a jejich stavů v daném okamžiku.
Stav dále obsahuje zprávu informující o stavu systému a průběhu
algoritmu, počet zpráv přenesených od zahájení algoritmu a případně data
specifická pro daný animovaný algoritmus.
Uzel systému (reprezentovaný třídou Node) má svůj identifikátor, příchozí
a odchozí komunikační kanály, souřadnice, na kterých se má vykreslit,
a stavy, ve kterých se aktuálně nachází. Stavy uzlu určují, jak bude daný
uzel vykreslen a slouží zejména pro informování uživatele, že uzel v důsledku
průběhu algoritmu nabývá speciálních vlastností. Stav uzlu může
například vyjadřovat, že uzel čeká na obdržení příznaku od jiného uzlu, že
vstoupil do kritické sekce, nebo že je účastníkem právě probíhající volby.
11
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
Každý uzel se může v jednom okamžiku nacházet i ve více stavech. Animovaný
algoritmus má také možnost libovolně využít dodatečnou paměť
uzlu.
Komunikační spoj (třída Link) se skládá ze dvou jednosměrných kanálů
vedoucích v opačných směrech. Komunikační kanál (třída Channel) je reprezentován
dvěma uzly - odesílatelem a příjemcem. Využití komunikačního
kanálu může být povoleno nebo zakázáno, což ovlivní, zda a jak bude
daný kanál vykreslen. Tato vlastnost také může sloužit animovanému algoritmu
jako indikace toho, zda může daný kanál používat pro posílání
zpráv. Kanál také může být označen jako aktivní nebo neaktivní, což
ovlivní způsob, jakým bude vykreslen. Označení kanálu jako aktivní, znamená,
že kanálem probíhá nějaká komunikace. Kanál také umožňuje přenášet
konkrétní zprávu, která se může vykreslit. K tomuto účelu slouží
vlastnost message. Komunikační kanál má dále k dispozici pomocný objekt
(instance třídy ChannelPresentation), který slouží pro uchovávání informace
o aktivitě daného komunikačního kanálu a také pro uchovávání bodů, pomocí
kterých je kanál vykreslen. Pro výpočet těchto bodů slouží metody
třídy Link.
Animované algoritmy nejsou implementovány tak, aby běžely v jednotlivých
uzlech systému, ale tak, že animovaný algoritmus pracuje s globálním
stavem systému. Systém a jeho prvky (stavy, uzly, komunikační
kanály) algoritmu slouží spíše jako datové struktury, do kterých si odkládá
data. Tento přístup byl zvolen z několika důvodů:
• Zprávy informující uživatele o průběhu algoritmu: Algoritmus běžící
v jednotlivých uzlech nezná globální stav systému. Proto by vytvoření
zprávy informující o průběhu algoritmu a o změnách, které v systému
nastaly, vyžadovalo dodatečnou funkcionalitu pro vytváření těchto
zpráv, která by se musela lišit pro každý algoritmus, protože zprávy
zobrazované různými algoritmy se mohou značně lišit.
• Export a import průběhů algoritmů: Vzhledem k tomu, že algoritmus
nezná globální stav systému, byla by vyžadována dodatečná funkcionalita
starající se o ukládání a načítání průběhů algoritmu. Struktura
ukládaných informací závisí na aktuálně animovaném algoritmu.
• Některé algoritmy mohou využívat speciální ovládací prvky, například
Raymondův algoritmus uživateli umožňuje definovat délku kritické
sekce.
12
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
Kromě simulace běhu daného algoritmu v jednotlivých uzlech systému se
animovaný algoritmus stará také o následující úkoly:
• Vytváří zprávy informující uživatele o průběhu algoritmu a o změnách,
které v systému nastaly - algoritmus ví, jaké změny v systému
provedl.
• Stará se o úložiště systémů a běhů (přidávání, mazání, ukládání a načítání),
což umožňuje, aby každý algoritmus využíval vlastní formát
uložených systémů a svých běhů na těchto systémech.
• Poskytuje rozhraní pro funkce obsluhující události (zejména uživatelské
vstupy). Díky tomu mohou animace algoritmů využívat libovolné
ovládací prvky.
• Řídí samotnou animaci algoritmu - určuje kdy a jak je systém vykres­
len.
• Spolu s třídou System se podílí na vytváření systému, ve kterém animovaný
algoritmus běží.
Jako základ pro implementaci animovaných algoritmů slouží třída AbstractAlgorithm
[Obrázek 3]. Jedná se o abstraktní třídu, která reprezentuje
obecný algoritmus obsahující metody společné pro všechny algoritmy. Obsahuje
také několik abstraktních metod předepisujících rozhraní vyžadované
základními ovládacími prvky animace. Jedná se zejména o metody,
které reprezentují běh algoritmu (například metoda nextStep, která zahajuje
přechod systému do následujícího stavu definovaného algoritmem).
Kromě metod obsahuje abstraktní algoritmus také několik vlastností.
Vynecháme-li pomocné vlastnosti a aktuální systém, ve kterém algoritmus
běží, lze zmínit následující:
• Dvě úložiště systémů - jedno slouží pro systémy a běhy vytvořené
nebo načtené uživatelem a druhé pro předdefinované systémy a průběhy
algoritmu. Předdefinované systémy a běhy jsou uloženy na
straně serveru a uživatel má možnost je využít v případě, že nechce
vytvářet vlastní systém nebo definovat vlastní průběh algoritmu.
• Záloha systému - tu lze vytvořit například před čtením z úložiště systémů,
aby nedošlo ke ztrátě aktuálního systému a průběhu algoritmu
v případě, že by čtení selhalo.
• Název algoritmu.
13
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
• Nastavení animace specifická pro daný algoritmus - nastavení jsou
blíže popsána v podkapitole 6.2.
• Volby určující, jak mají být vykresleny komunikační kanály systému
(například, zda má být rozlišováno, jestli je kanál aktivní, nebo ne, zda
mají být vykresleny všechny kanály, nebo jen aktivní apod.).
Třída AbstractAlgorithm je dále rozšířena dvěma abstraktními třídami, a to
RingFullSystemAlgorithm a MeshSystemAlgorithm. [Obrázek 4] První z nich
reprezentuje algoritmus, který běží v systému, jehož topologií je kruh nebo
úplný graf. Druhá třída představuje algoritmus, který může běžet v systému
s libovolnou topologií. Tyto dvě třídy rozšiřují abstraktní algoritmus
o rozhraní pro ovládací prvky umožňující vytvoření systému. Postup vytvoření
se pro systémy s různou topologií liší.
Systémy s kruhovou topologií nebo topologií úplného grafu jsou generovány
automaticky na základě zvolených parametrů, jimiž jsou počet
uzlů systému, případně směr kruhu, pokud se jedná o jednosměrný kruh.
Na rozdíl od nich jsou ostatní systémy vytvářeny postupným přidáváním
jednotlivých uzlů a komunikačních spojů.
Jednotlivé implementované algoritmy pak dědí buď z třídy RingFullSystemAlgorithm,
nebo z třídy MeshSystemAlgorithm podle toho, v jakých
systémech mohou běžet. Implementované algoritmy jsou blíže popsány
v kapitole 4.
14
- Fields
0 ctx : CanvasRenderingCcntext2D
* 0 currentStatelndex : N u m b e r
"•"a savedStatelndex : N u m b e r
System
Class
1
- M e t h o d s
e
o
o
©
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
e
o
o
o
o
o
o
a d d L i n k f N u m b e r n o d e l Id N u m b e r node2ld bool hasDiscreteChannels) : Link
a d d N o d e f N o d e n o d e ) : bool
addStatefSystemState state) : void
calculateChannelsPoints(Link[] links): void
calculateLineslntersectionfCoordinates p1 Coordinates p2 Coordinates q1 Coordinates q2) : Coordinates
calculateRingNodesPoints(Node[] nodes N u m b e r width N u m b e r height): v o i d
clearCanvasQ : void
createFullyConnectedSystem(Number n u m b e r O f N o d e s bool discreteChannels CanvasRenderingContext2D ctx) : System
createRingSystemfNumber numberOfNodes. RingTypeEnum ringType. CanvasRenderingContext2D ctx) : System
deleteAIIStatesO : void
deleteSubsequentStatesf): v o i d
draw(LinkPresentationOptions o p t i o n s ) : void
fillRingWithLinks(Node[] nodes. RingTypeEnum ringType CanvasRenderingContext2D ctx [bool sort = true]): System
fillWithLinks(Node[] nodes bool discreteChannels. CanvasRenderingContext2D ctx, [bool sort = true]): System
fitNodeToCanvasfNode n o d e N u m b e r width. N u m b e r height): void
generateRingNodes(Number numberOfNodes. N u m b e r width. N u m b e r height): Node[]
getCurrentStateO : SystemState
getLinkContainingCoordinates(Coordinates coordinates): Link
g e t N o d e f N u m b e r i d ) : N o d e
getNodeOnCoordinates(Coordinates coordinates): N o d e
c h a n g e N o d e C o o r d i n a t e s f N u m b e r id. Coordinates coordinates): v o i d
islnlnitialState() : bool
isTreefNumber rootld): IsTreeObject
markRootOfTree(Number rootld) : IsTreeObject
moveTolnitialStateO : v o i d
nextState() : SystemState
previousStatef) : SystemState
removeLink(Link link bool destroyLink) : v o i d
removeNode(Number id bool destroyLinks): void
restoreStatef) : void
saveStatelndexO : void
scaleNodesCoordinates(Node[] nodes. N u m b e r width. N u m b e r height N u m b e r oldVVidth. N u m b e r oldHeight. bool scaleAsCircle) : void
sortNodes[Node[] nodes) : Node[]
s w a p N o d e s ( N u m b e r n o d e l Id N u m b e r node2ld) : void
updateChannelsNodesReferences(): void
updateLink(Link link): void
u p d a t e N o d e i N o d e n o d e ) : v o i d
updateStatefSystemState state): v o i d
states: SystemState[] 1
SystemState *
^ Class
Obrázek 1: Diagram tříd znázorňující třídu System.
MemoryContent "
Interface
" M e t h o d s
fi) draw(Coordinates coordinates, CanvasRenderingContext2D ctx): void
0 m e m o r y C o n t e n t
0 nodes : N o d e Q \ '
Node
Class
" Fields
0 id : N u m b e r
H M e t h o d s
<*> c o n t a i n s P o i n t f C o o r d i n a t e s c o o r d i n a t e s ) : b o o l
0 c o p y f ) : N o d e
O d r a w ( C a n v a s R e n d e r i n g C o n t e x t 2 D c t x ) : v o i d
© a drawMultipleStates(CanvasRenderingContext2D c t x ) : v o i d
SystemState
Class
H Fields
0 algorithmSpecific : object
0 m e s s a g e : string
0 messagesSent: N u m b e r
- M e t h o d s
© c o p y ( b o o l k e e p N o d e s b o o l k e e p L i n k s ) : SystemState
0 s t a t e s : N o d e S t a t e E n u m Q
0 receiver f A
0 sender
Message Ä
Interface
0 M e t h o d s
S) draw(CanvaiRenderingContext2D ctx): void
0 m e s s a g e
Y,0 o u t g o i n g C h a n n e l s : ChannelQ \'t0 i n c o m i n g C h a n n d s : ChannelQ
0 coordinates
Coordinates *
Class
a
Fields
0 x : N u m b e r
0 y : N u m b e r
7K
0 a r r o w P o i n t l
K
0 arrowPoint2
K 1
NodeStateEnum
Enum
Default
HasToken
WaitingForToken
InCriticalSection
M a r k e d B y U s e r
A d d i n g L i n k
S w a p p i n g
ElectionParticipant
Sequencer
0 arrowPoint3
K
0 receiverPoint
0 senderPoint
Channel
Class
B
Fields
0 i s A l l o w e d : b o o l
- M e t h o d s
© d r a w ( C a n v a s R e n d e r i n g C o n t e x t 2 D ctx b o o l drawActivity, b o o l d r a w D i r e c t i o n ) : b o o l
© setActivityfbool i s A c t i v e ) : v o i d
7Š
ChannelPresentation *
Class
H Fields
0 d r a w A s A c t i v e : b o o l
0 presentation
/ \ 0 channels : ChannelQ 0 links : Link[] > '
0 link
Link
" Fields
0 hasDiscreteChannels: b o o l
H M e t h o d s
©a c a l c u l a t e A r r o w P o i n t s f N u m b e r angle) : v o i d
© calculatePointsO : v o i d
© a c a l u l a t e E n d P o i n t s ( N u m b e r a n g l e ) : v o i d
© containsPointfCoordinates coordinates) : b o o l
© c o p y Q : Link
© draw(CanvasRenderingContext2D ctx, LinkPresentationOptions o p t i o n s ) : v o i d
© islnRectanglefCoordinates a Coordinates b. Coordinates c Coordinates p ) : b o o l
IsTreeObject
Class
a
Fields
0 h a s C y c l e : b o o l
0 isConnected : b o o l
StorageTypeEnum Ä
Enum
Imported
D o w n l o a d e d
Obrázek 2: Diagram tříd znázorňující základní prvky systému (uzly, komunikační spoje atd.)
a některé pomocné třídy.
Abs tractA tg or it tun
Abstract Class
- Fields
*• a n i m a t i o n A c t i v e : b o o l
** c i r c l e S c a l e : b o o l
0
*
c o m m A c t i v e : b o o l
c o m m A l w a y s D r a w n : b o o l
c o m m u n i c a t i o n T i m e : N u m b e r
c o n t T i m e o u t : N u m b e r
* m o v i n g N o d e s D i s a b l e d : b o o l
n a m e : string
s e t t i n g s : O b j e c t
* s t a t e T i m e : N u m b e r
* s t o r a g e S a v e d : b o o l
3 M e t h o d s
© t a n i m a t e O I v o i d
© c l o s e l m p o r t e d S t o r a g e O ! b o o l
© c r e a t e S y s t e m B a c k u p O : v o i d
© d e l e t e S c e n a r i o ( N u m b e r syslndex. N u m b e r s c e n a r i o l n d e x ) : v o i d
© d e l e t e S y s t e m ( N u m b e r i n d e x ) : v o i d
© d o w n l o a d S t o r a g e f f u n c t i o n s u c c C a l l b a c k , f u n c t i o n e r r o r C a l l b a c k ) : v o i d
© d r a w S y s t e m O ! v o i d
© ttp:Tfcs:s irzii.deScins'iz1
: vsii
© g e t N o d e O n C o o r d i n a t e s f C o o r d i n a t e s c o o r d i n a t e s ) : N o d e
© g e t N u m b e r O f N o d e s O : N u m b e r
© g e t N u m b e r O f S t o r e d S c e n a r i o s ( S t o r a g e T y p e E n u m storage) : N u m b e r [ ]
© getSettingsf) : O b j e c t
© c h a n g e C c m m u n i c a t i o n T i m e [ N u m b e r t ) : v o i d
© c h a n g e N o d e C o o r d i n a t e s f N o d e n o d e C o o r d i n a t e s c o o r d i n a t e s ) : v o i d
© c h a n g e S t a t e T i m e ( N u m b e r t ) : v o i d
© i m p o r t f B l o b file, f u n c t i o n callback, f u n c t i o n e r r o r C a l l b a c k ) : v o i d
© i m p o r t e d S t o r a g e N o t E m p t y O : b o o l
© nextStepO: void
© openStoredScenariofNumber syslndex, Number scenariolndex, StorageT^peEnum storage): void
© p a u s e A n i m a t i o n O : v o i d
© processClickfCoordinates coordinates): void
© r e m o v e S y s t e m B a c k u p O : v o i d
© r e s t a r t F r o m C u r r e n t f ) : v o i d
© restartFromlnitiatO: void
© r e s t o r e S y s t e m B a c k u p O : b o o l
© r u n A n i m a t i o n ( ) : v o i d
© s a v e S t o r a g e f B l o b file, f u n c t i o n callback, f u n c t i o n e r r o r C a l l b a c k ) : v o i d
© s c a l e D r a w n S i z e ( N u m b e r w i d t h . N u m b e r height) : v o i d
O stepBszk'j: boot
© s w i t c h l n p u t P r o c e s s i n g M o d e f C a n v a s C l i c k M o d e s E n u m m o d e ) : v o i d
s y s t e m B a c k u p
SizeObject
Class
lastCanvasSize
c l i c k M o d e
CanvasC lickM odesEnum
Enum
RingFutlSystemAtgorithm
-t> AbstractAlgorithm
MeshSystemAlgorithm
Abstract Class
-t> AbstractAlgorithm
~ ^ ^ t downloadedStorage
\ .
SystemsStorage
Class
i m p o r t e d S t o r a g e
0 s y s t e m s : S t o r e d S y s t e m Q ^'/
StoredSystem
Class
J
DrawnChannekEnum
Enum
•fi* channelDravv
DrawnChannelDirectionEnum ^ LinkPresentationOptions *
Enum ^ _ . Class
M d r a w D i r e c t i o n
d r a w O p t i o n s
Obrázek 3: Diagram tříd znázorňující abstraktní třídy sloužící jako základ pro implementaci
animací algoritmů a s nimi související třídy - část I.: Třída AbstractAlgorithm.
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
SizeObject
Class
- Fields
0 height: Number
0 width : Number
7F& t lastCanvasSize
AbstractAlgorithm V
Abstract Class
MeshSystemAlgorithm A
Abstract Class
-ť AbstractAlgorithm
- Methods
O cioseSystemQ: void
Ô editSystem(CanvasClickModesEnum mode): void
(J) startAlgorithmQ: bool
\ system y y ^ t systemBackup
System
Class
& t swappingNode
Ring Fu USys ternA Igorithm
Abstract Class
-t> AbstractAlgorithm
- Methods
O createSystemQ: void
O getAllowedNumbersOfNodesfNumberx, Numbery): Number[]
<£> startNodesSwappingO : void
® t swapNodes(Coordinates coordinates): void
WL drawOptions _
& t importedStorage ^
0 systems : StoredSystemfJ ^',
StoredSystem
Class
B
Fields
0 scenarios: Object[]
D r a w n C h a n n e l s E n u m
Enum
Both
FirstOnly
SecondOnly
V
^, clickMode
CanvasC lickM odesEnum
Enum
NoAction
AddNode
RemoveNode
AddLink
Removelink
MarkRoot
AlgorithmStarted
SwappingNodes
* L i n k P r e s e n t a t i o n O p t i o n s
Class
S Fields
0 drawActivity : bool
• drawAIIActive: bool
0 prioritizeActive: bool
O channelDraw
0 drawDirection ^
DrawnChannelDirectionEnum
Enum
None
Active
Inactive
All
Obrázek 4: Diagram tříd znázorňující abstraktní třídy sloužící jako základ pro implementaci
animací algoritmů a s nimi související třídy - část II.: Ostatní třídy.
18
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
3.3.2 Serverová část
Vzhledem k tomu, že většina aplikace běží na straně klienta, je rozsah serverové
části menší oproti klientské části. Serverová část nepracuje s velkým
množstvím dat a nevyužívá databázi, proto je část Model vzoru MVC
nevyužitá. Serverová část se tedy skládá zejména z řadičů a pohledů.
Standardně [28] řadiče dědí z třídy System.Web.Mvc.Controller [29].
Aplikace přidává mezivrstvu v podobě třídy BaseController, která dědí
z třídy Controller. Jednotlivé řadiče pak dědí z třídy BaseController. Třída
BaseController se stará o volbu jazyka, ve kterém bude uživatelské rozhraní
zobrazeno. Při práci s různými jazyky je využita pomocná statická třída
CultureHelper. Pro každou kategorii algoritmů existuje jeden řadič. V aktuální
verzi aplikace se jedná o třídy LeaderElectionController (volba vedoucího
prvku), MulticastController (multicasting) a MutualExclusionController
(vzájemné vyloučení). Každý z těchto řadičů pro každý implementovaný
algoritmus dané kategorie obsahuje jednu metodu pro obsluhu požadavků
na zobrazení stránky s animací algoritmu a jednu metodu pro zobrazení
nápovědy k ovládání animace daného algoritmu. Aplikace dále také obsahuje
řadič HomeController, který se stará o obsluhu požadavků na zobrazení
úvodní stránky aplikace, požadavků na změnu jazyka uživatelského
rozhraní a požadavků na stažení předdefinovaných systémů a běhů algo­
ritmů.
Část pohled (View) vzoru MVC se skládá z webových stránek tvořících
uživatelské rozhraní aplikace. Kromě úvodní stránky obsahuje tato část
aplikace dvě šablony: _Layout a _HelpLayout. _Layout slouží pro stránky
s animací algoritmů a _HelpLayout pro nápovědu k používání aplikace.
Šablona _Layout obsahuje všechny prvky stránky (levostrannou nabídku
implementovaných algoritmů, element canvas pro vykreslení animace
atd.) kromě obsahu ovládání animace [Obrázek 5]. O jeho vytvoření
se starají jednotlivé stránky pro animaci algoritmů, jejichž obsah je vkládán
do šablony _Layout. Pro vytvoření ovládání lze využít moduly, do nichž je
celé ovládání animace rozděleno. To je rozděleno na části: „Vytvoření prostředí"
(existují dvě verze, jedna pro algoritmy běžící v systémech s topologií
kruhu nebo úplného grafu a druhá pro algoritmy běžící v systémech
s libovolnou topologií), „Předdefinovaná a uložená prostředí", „Průběh algoritmu"
a „Export a uložení do souboru". Vykreslení jednotlivých modulů
je možné ovlivnit předanými parametry. Například lze určit, zda
19
3. A N A L Ý Z A A N Á V R H A N I M A Č N Í H O SYSTÉMU
algoritmus běží v systémech s topologií úplného grafu (pokud ano, nejsou
zobrazeny ovládací prvky pro výběr směru kruhu) nebo zda algoritmus
podporuje načítání a ukládání průběhů (pokud ne, pak příslušné ovládací
prvky nejsou zobrazeny). Parametry se předávají prostřednictvím dynamického
objektu ViewBag [30].
Šablona _HelpLayout tvoří základ pro stránky nápovědy k používání
aplikace. Nápovědu lze opět poskládat z modulů, jejichž obsah může být
upraven pomocí parametrů předávaných prostřednictvím dynamického
objektu ViewBag. Nápověda je rozdělena na stejné části jako ovládání ani­
mace.
Zobrazit nápovědu » Čeština Zpět
na úvodní stránku
Distribuované vzájemné vyloučeni
Předáváni příznaku po kruhu
Raymondův algoritmus
Volba vedoucího prvku
Hirschberg-Sinclairův algoritmus
Multicasting
Totálni řazeni pomocí sekvenceru
Raymondův algoritmus
Přeneseno zpráv: 5
Uzel 1 předává příznak uzlu 3 Fronta uzlu 1 je neprázdná, a ten proto žádá o vrácení příznaku.
Uzly 4, 7 a 9 posílají žádosti svým rodičům.
Ovládání animace
Vytvoření prostředí
Přidat uzel
Odebrat uzel
Přidat komunikační spoj
Odebrat komunikační spoj
Označit uzel jako kořen
Spustit algoritmus Upravit systém
Zavřít systém
Předdefinovaná a uložená prostředí
Předdefinovaná pmstřeďi
Systém: Systém 1
Průběh: Průběh 1
Uložená prostřed
Načíst ze souboru
Průběh algoritmu
Délka zobrazení komunikace
Kratší £ De
Délka zobrazení stavu
Kratší £ De
Proměnlivá délka kritické sekce
Restartovat z aktuálního stavu
Restartovat z počátečního stavu
Krokovaný režim
Krok zpět Dalši krok
Plynulá animace
Spustit animaci
Obrázek 5: Uživatelské rozhraní - animace Raymondova algoritmu.
Na levé straně se nachází nabídka implementovaných animací algoritmů, uprostřed je
vykreslena animace algoritmu a pod ní je vypsána zpráva o stavu systému a průběhu
algoritmu. Na pravé straně se nachází ovládání animace.
20
4 Implementované algoritmy
Pro demonstraci chování a používání animačního systému byly implementovány
animace následujících algoritmů:
• Distribuované vzájemné vyloučení: předávání příznaku v kruhové topologii
[32] a Raymondův algoritmus [33].
• Volba vedoucího prvku: Hirschberg-Sinclairův algoritmus [35].
• Multicasting: totální řazení zpráv pomocí sekvenceru [39].
Animační systém byl navržen s ohledem na možnost budoucího rozšiřování
množiny animovaných algoritmů. Postup pro implementaci animací
dalších algoritmů je popsán v podkapitole 5.1.
4.1 Distribuované vzájemné vyloučení
Pokud v distribuovaném systému existují dva nebo více procesů, které obsahují
kritické sekce sdružené s nějakým sdíleným objektem, je potřeba zajistit
sériové provedení (vzájemné vyloučení [31]) těchto kritických sekcí.
Řešení vzájemného vyloučení musí splňovat následující podmínky:
• Podmínka bezpečnosti - dosáhne se vzájemného vyloučení (v každé
konfiguraci systému se v kritické sekci nachází nejvýše jeden proces).
• Podmínka živosti - zamezuje se stárnutí a uváznutí procesů (pokud
chce proces vstoupit do kritické sekce, pak do ní vstoupí v konečném
čase).
• Podmínka spravedlivosti - pořadí procesů vstupujících do kritické
sekce odpovídá pořadí žádostí procesů o vstup do kritické sekce (případně
libovolný proces může být předběhnut každým procesem nejvýše
jednou).
4.1.1 Předávání příznaku v kruhové topologii
Při předávání příznaku v kruhové topologii [32] jsou procesy v distribuovaném
systému uspořádány do jednosměrného kruhu. Procesy si ve směru
kruhu předávají speciální zprávu (příznak, token) existující v jediném
exempláři. Pokud chce proces vstoupit do kritické sekce, musí počkat, až
21
4. I M P L E M E N T O V A N É ALGORITMY
obdrží příznak. Když proces obdrží příznak a chce vstoupit do kritické
sekce, pak do ní vstoupí. Jakmile kritickou sekci opustí, předává příznak
svému sousedovi. Pokud proces nechce do kritické sekce vstoupit, předává
příznak bez prodlení. Komunikační složitost tohoto řešení je lineární.
Předávání příznaku v kruhové topologii splňuje podmínku bezpečnosti
a živosti. Je splněna také podmínka spravedlivosti, protože libovolný
proces může být každým procesem předběhnut nanejvýš jednou.
Nevýhodou tohoto řešení je, že se ztráta příznaku musí řešit distribuovanou
volbou procesu, který bude nový příznak generovat. Výpadek uzlu
se musí řešit rekonstrukcí kruhu.
Algoritmus pro předávání příznaku v kruhové topologii je v animačním
systému reprezentován třídou RingTokenPassing [Obrázek 6], která
dědí z abstraktní třídy RingFullSystemAlgorithm, protože algoritmus běží
v systémech s kruhovou topologií. Třída RingTokenPassing implementuje
abstraktní metody zděděné z tříd AbstractAlgorithm a RingFullSystemAlgorithm.
Samotný algoritmus pro předávání příznaku v kruhové topologii je
simulován metodami nextStep afinishStateTransition.Metoda nextStep zahajuje
přechod systému do nového stavu tím, že zahájí odesílání příznaku
následujícímu uzlu. MetodafinishStateTransition je zavolána ve chvíli, kdy
je komunikace dokončena, a simuluje přijetí příznaku následujícím uzlem.
Ten, pokud žádal o vstup do kritické sekce, do kritické sekce vstupuje.
Objekty třídy RingTokenPassingData slouží pro ukládání dodatečných
dat pro jednotlivé stavy systému (vlastnost algorithmSpecific třídy SystemState).
Mezi tato data patří informace o uzlech označených uživatelem pro
vstup do kritické sekce a uzel, který v daném stavu drží příznak.
Třída RtpStoredSystem reprezentuje uložený systém (běhové prostředí)
pro algoritmus pro předávání příznaku v kruhové topologii.
22
4. I M P L E M E N T O V A N É A L G O R I T M Y
R i n g T o k e n P a s s i n g D a t a
a
Fields
^ userChangedNodes: bool[]
RingFullSystemAlgorittvn
Abstract Class
-t> AbstractAlgoritrim
M nodeWithToken
RingTokenPassing
Class
H> RingFullSystemAlgorithm
- Methods
® a _createSystem[Number numberOfNodes Number nodeWithTokenld, RingTypeEnum ringType) : void
© createSystemf): void
O exportfbool includeScenario): void
0B exportScenario(RtpStoredSystem sys): void
® a finishStateTransition(Number nextNodeld): void
S> nextStepO : void
0 openStoredScenario(Number syslndex. Number scenariolndex. StorageTypeEnum storage) : void
® a prepareNextStepO : void
O processClick(Coordinates coordinates): void
O restartFromlnitialQ : void
O stepBack(): bool
StoredSystem
Class
- Fields
^ scenarios: Object[]
~ 2S
^ É ringType
RingTypeEnum
Enum
Forward Direction
ReverseDirection
TwoWay
0 ringType
RtpStoredSystem
Class
"fr StoredSystem
Q Fields
* nodeWithTokenld : Number
Of numberOfNodes: Number
Obrázek 6: Diagram tříd zobrazující třídy reprezentující animaci předávání
příznaku v kruhové topologii.
23
4. I M P L E M E N T O V A N É ALGORITMY
4.1.2 Raymondův algoritmus
Raymondův algoritmus [33] pro svůj běh vyžaduje stromovou strukturu.
Ta vznikne tak, že se na silně souvislý graf uzlů distribuovaného systému
superponuje jeho kostra. Jednotlivé uzly si po kostře předávají příznak
existující v jediném exempláři. Uzel, který drží příznak je kořenem stromu.
Všechny ostatní uzly stromu obsahují ukazatel na svého jediného rodiče,
kterému zasílají požadavky na získání příznaku. Každý uzel si udržuje
frontu požadavků, do které vkládá své požadavky i požadavky, které
obdržel od ostatních uzlů. Uzel svému rodiči zasílá vždy jen jeden požadavek
bez ohledu na počet požadavků, které má ve své frontě.
Kořen smí vstoupit do kritické sekce jen tehdy, když se nachází v čele
vlastní fronty. Pokud kořen opustí kritickou sekci nebo se nenachází v čele
své fronty, bez prodlení předává příznak uzlu, který je první v jeho frontě.
Při předávání příznaku odstraní kořen žádost uzlu, kterému příznak předává,
ze své fronty. Zůstane-li fronta původního kořene neprázdná, pak
spolu s příznakem zasílá i žádost o vrácení příznaku. Při předávání příznaku
se orientace hran v kostře aktualizuje - uzel který obdrží příznak se
stává novým kořenem stromu. Komunikační složitost algoritmu odpovídá
přibližně výšce stromu, tedy O(logn).
Raymondův algoritmus plní podmínku bezpečnosti - v systému vždy
existuje pouze jeden kořen. Je splněna také podmínka živosti, protože platí,
že každý požadavek se v konečném čase dostane na začátek fronty. Podmínka
spravedlivosti je splněna díky tomu, že žádosti jsou řazeny do front,
podle kterých je příznak postupně předáván.
V animačním systému je Raymondův algoritmus reprezentován třídou
Raymond [Obrázek 7], která dědí z třídy MeshSystemAlgorithm, protože algoritmus
vyžaduje stromovou strukturu. Třída Raymond implementuje
abstraktní metody zděděné z tříd AbstractAlgorithm a MeshSystemAlgorithm.
Raymondův algoritmus je simulován metodami nextStep, nextStepRoot,
passToken, sendRequest, finishStateTransition a enterCriticalSection.
Metoda nextStep zahajuje přechod systému do nového stavu tím, že s pomocí
metody sendRequest zahájí posílání žádostí z uzlů, které splňují podmínky
pro poslání žádosti. Metoda nextStepRoot se stará o zahájení
přechodu kořene do nového stavu a metoda passToken zajišťuje případné
předání příznaku. MetodafinishStateTransition je zavolána ve chvíli, kdy je
komunikace dokončena, a simuluje přijetí žádostí uzly, případně přijetí
24
4. I M P L E M E N T O V A N É ALGORITMY
příznaku novým kořenem. V případě, že nový kořen může vstoupit do kritické
sekce je zavolána metoda enterCritkalSection.
Třída Raymond dále obsahuje metody pro vytváření a úpravy systému
a vzhledem k tomu, že ovládání animace Raymondova algoritmu používá
posuvník pro výběr intervalu hodnot pro délku kritické sekce, obsahuje
třída Raymond metodu changeCSLength pro změnu krajních hodnot tohoto
intervalu.
Objekty třídy RaymondData slouží pro ukládání dodatečných dat pro
jednotlivé stavy systému (vlastnost algorithmSpecific třídy SystemState).
Mezi tato data patří informace o uzlech označených uživatelem pro vstup
do kritické sekce, délka aktuálně probíhající kritické sekce a počet žádostí
přidaných do fronty pro každý uzel.
Raymondův algoritmus využívá dodatečnou paměť v uzlech, která je
reprezentována třídou RaymondMemContent implementující rozhraní MemoryContent.
Paměť uzlu obsahuje frontu přijatých žádostí, informaci
o tom, zda uzel odeslal žádost svému rodiči, a počet žádostí přidaných do
fronty v aktuálním stavu.
Třída RaymondStoredSystem reprezentuje uložený systém (běhové prostředí)
pro Raymondův algoritmus. Systém je uložen jako pole uzlů reprezentovaných
jejich souřadnicemi a pole komunikačních spojů v podobě
instancí třídy RaymondStoredLink.
25
1 MemoryContent
RaymondMemContent *
Class
B Fields
^ addedToQueueNum: Number
0 queue: Number[]
* requestSent: bool
B Methods
© copy()! RaymondMemContent
© draw(Coordinates coordinates CanvasRenderingContext2D ctx): void
StoredSystem
Class
B Fields
^ scenarios: Object[]
Raymond
Class
-t> MeshSystemAlgorithm
B Fields
0L
csLengthMax : Number
cslengthMin : Number
edited Restarted : bool
editingSystem: bool
newRootld : Number
pendingRequests: Number[][]
- Methods
© addLink(Coordinates coordinates): void
addNodefCoordinates coordinates): void
askForToken(Coordinates coordinates): void
closeSystemO : void
deselectRoot(): void
editSystem(CanvasClickModesEnum mode): void
enterCriticalSection(): void
exportfbool includeScenario) : void
exportScenariofRaymondStoredSystem sys): void
finishStateTransition(bool rootCopyCreated): void
changeCSLength(Number min. Number max) : void
markRoot[Coordinates coordinates): void
nextStepO : void
nextStepRootf): bool
openStoredScenario(Number syslndex, Number scenari...
passTokenibool copyCreated): void
prepareMessageO : void
prepareNextStepO : void
prepareQueueHighlightsO ! void
prccessClickfCoordinates coordinates) : void
removeLink(Coordinates coordinates): void
removeNodefCoordinates coordinates) : void
restartFromlnitialO : void
sendRequestiNode node) : void
startAlgorithmO i bool
stepBackf) : bool
systemEditedRestart(): void
©
9
©
©a
©
©a
©
©
©
©
9
*.©a
%
©
©
©
©
©
©
9.
RaymondStoredSystem
Class
-f> StoredSystem
- Fields
•
0
height: Number
nodes: Coordinates!]
rootld : Number
width : Number
MeshSystemAlgorithm
_| , Abstract Class
-t> AbstractAlgorithm
0 links : RaymondStoredLinkQ y
Raymonds toredLink
Class
B Fields
0 receiver: Number
* sender: Number
RaymondData
Class
Q Fields
• csLength : Number
• queueAddedLength : Number[]
• userChangedNodes: bool[]
^ 4 newLinkSenderTemp
Obrázek 7: Diagram tříd zobrazující třídy reprezentující animaci Raymondova algoritmu.
4. I M P L E M E N T O V A N É ALGORITMY
4.2 Volba vedoucího prvku
Volba vedoucího prvku [34] slouží k dynamickému výběru uzlu, který
bude plnit určitou speciální roli - koordinátor vzájemného vyloučení nebo
transakcí, centrální časový server, uzel generující příznak při jeho ztrátě
apod. Volba může být vyvolána například kvůli výpadku uzlu, který danou
roli dosud plnil.
Volební algoritmus je decentralizovaný algoritmus - všechny uzly řeší
stejný lokální algoritmus. Každý proces může vyvolat jeden volební běh
(stává se jeho iniciátorem), což znamená, že v prostředí n uzlů může v jednom
okamžiku probíhat až n volebních běhů. Řešení volebního algoritmu
musí splňovat následující podmínky:
• Podmínka bezpečnosti - rozhodnutí uzlu být zvoleným procesem je
zvoleným procesem nezměnitelné, zvolený proces musí být vybrán
jednoznačně i v případě souběžné realizace více volebních běhů.
• Podmínka živosti - volby se účastní všechny uzly, volba skončí v konečném
čase a po jejím ukončení každý její účastník zná zvolený uzel.
4.2.1 Hirschberg-Sinclairův algoritmus
Procesy jsou uspořádány do obousměrného kruhu. Hirschberg-Sinclairův
algoritmus [35] probíhá ve fázích (r = 0,1,2,...). Iniciátor v každé fázi posílá
průzkumnou zprávu, pomocí které zjišťuje, zda má nejvyšší prioritu
(je vedoucím prvkem), oběma směry do vzdálenosti 2r
a očekává pozitivní
potvrzení po odrazu v posledním (nejvzdálenějším) osloveném uzlu. Uzly,
které obdrží průzkumnou zprávu od uzlu s nižší prioritou, tuto zprávu zahodí.
Pouze uzly, které obdržely odpovědi na obě své průzkumné zprávy,
postupují do další fáze. Ostatní uzly jen přenášejí zprávy mezi sousedy.
Vítězem volby se stává uzel, který obdrží svou průzkumnou zprávu. Komunikační
složitost tohoto řešení je 0(n • logn).
Hirschberg-Sinclairův algoritmus je v animačním systému reprezentován
třídou HirschbergSinclair [Obrázek 8], dědící z třídy RingFullSystemAlgorithm,
protože algoritmus běží v systémech s topologií obousměrného
kruhu. Třída HirschbergSinclair implementuje abstraktní metody zděděné
z tříd AbstractAlgorithm a RingFullSystemAlgorithm. Hirschberg-Sinclairův
algoritmus je simulován metodami nextStep afinishStateTransition. Metoda
27
4. I M P L E M E N T O V A N É ALGORITMY
nextStep zahajuje posílání průzkumných zpráv, respektive odpovědí na
tyto zprávy, následujícímu uzlu. Metoda finishStateTransition je zavolána
ve chvíli, kdy je komunikace dokončena, a simuluje přijetí průzkumných
zpráv, respektive odpovědí, uzly. V případě ukončení fáze algoritmu rozhoduje
tato metoda o tom, které uzly ve volbě končí. Tato metoda také rozhoduje
o tom, zda se již některý z uzlů stal vítězem volby.
Objekty třídy HirschbergSinclairData slouží pro ukládání dodatečných
dat pro jednotlivé stavy systému (vlastnost algorithmSpecific třídy SystemState).
Tyto objekty ukládají číslo aktuálně probíhající fáze a také informaci
o tom, zda v následujícím kroku začíná nová fáze.
Třída HirschbergSinclairMsg implementující rozhraní Message reprezentuje
zprávy (průzkumné zprávy i odpovědi na ně) zasílané uzly během
provádění algoritmu. Tyto zprávy obsahují identifikátor původního odesílatele,
fázi, ve které byla zpráva odeslána, vzdálenost, kterou od odesílatele
urazila, komunikační kanál, který ji přenáší, a informaci o tom, zda se
jedná o průzkumnou zprávu nebo odpověď.
Hirschberg-Sinclairův algoritmus využívá dodatečnou paměť v uzlech,
která je reprezentována třídou HirschbergSinclairMemContent implementující
rozhraní MemoryContent. Paměť uzlu ukládá přijaté zprávy.
Třída HsStoredSystem reprezentuje uložený systém (běhové prostředí)
pro Hirschberg-Sinclairův algoritmus. Uložený systém je reprezentován
polem uchovávajícím pořadí identifikátorů uzlů.
28
Cj) Message
H ir sc h be rgSinclairM sg
Class
- Fields
drawn : bool
id : Number
isReply: bool
phase: Number
stepCounter: Number
- Methods
© copy(): HirschbergSinclairMsg
draw(CanvasRenderingContext2D ctx): void
drawForBothChannels(Channel c CanvasRenderingContext2D ctx): void
drawThisOnly(CanvasRenderingContext2D ctx): void
getStringO : string
•
•
o
%
©
& channel
Channel
Class
StoredSystem
Class
- Fields
^ scenarios: Object[]
s
I
1MemoryContent
0 messages: HirschbergSinclairMsg[]
HirschbergSinclairMemContent *
Class
- Methods
© draw(Coordinates coordinates. CanvasRenderingContext2D ctx): void
*
HirschbergSinclair *
Class
-> RingFullSystemAlgorittim
- Fields
*e nodesOrder: Number[]
- Methods
© createSystemO I void
export(bool includeScenario): void
finishStateTransition(): void
getAllowedNumbersOfNodesfNumberx, Number y): Number[]
nextStep(): void
openStoredScenario(Number syslndex. Number scenariolndex. Stora..
prepareNextStepO : void
processClick(Coordinates coordinates): void
restartFromlnitialO : void
stepBackf) i bocl
O
a.
o
o
o
e.
o
o
o
HsStoredSystem
Class
StoredSystem
Q Fields
0 nodesOrder: Number[]
r HirschbergSinclairData
Class
- Fields
• phase: Number
0 startNewPhase: bool
Ring Fu USys tern A Igoiithm
Abstract Class
•+ AbstractAlgorithm
Obrázek 8: Diagram tříd zobrazující třídy reprezentující animaci Hirschberg-Sinclairova
algoritmu.
4. I M P L E M E N T O V A N É ALGORITMY
4.3 Multicasting
Jedná se o problém sdělení zprávy všem procesům náležejícím do skupiny
procesů. [36] Při skupinové komunikaci může být důležité, aby se doručování
zpráv odehrávalo v určitém pořadí. K tomuto účelu existují tři typy
řazení [37]:
• FIFO řazení - posílá-li libovolný proces zprávu a a poté zprávu b, pak
každý korektní proces před obdržením zprávy b obdrží zprávu a.
• Kauzální řazení - jestliže zaslání zprávy a předchází zaslání zprávy b
z hlediska zasílání zpráv v dané skupině, pak každý korektní proces
před obdržením zprávy b obdrží zprávu a.
• Totální řazení - jestliže jeden korektní proces ve skupině obdrží
zprávu a před zprávou b, pak obdrží zprávu a před zprávou b každý
korektní proces v dané skupině.
4.3.1 Totální řazení zpráv pomocí sekvenceru
Při totálním řazení zpráv pomocí sekvenceru [38] jsou zprávy řazeny pomocí
čítače, který je jedinečný v dané skupině procesů. Proces udržující
tento čítač se nazývá sekvencer (sequencer). Jako sekvencer může sloužit
některý z uzlů distribuovaného systému, nebo se může jednat o dedikovaný
uzel. Pro totální řazení zpráv pomocí sekvenceru existují různé přístupy
[39]:
1. Každý proces, který chce rozesílat zprávu, pošle zprávu všem uzlům
a sekvenceru. Jednotlivé uzly si přijatou zprávu umístí do vyrovnávací
fronty. Sekvencer určí přijaté zprávě pořadové číslo a tuto informaci
rozešle všem procesům ve skupině. Přijaté zprávy jsou pak
z fronty doručovány podle pořadových čísel určených sekvencerem.
2. Každý proces, který chce rozesílat zprávu, pošle tuto zprávu pouze
sekvenceru a ten zprávu spolu s jejím pořadovým číslem následně rozešle
všem procesům ve skupině.
3. Každý proces, který chce rozesílat zprávu, si nejdříve vyžádá od sekvenceru
pořadové číslo, které následně spolu se zprávou rozešle všem
procesům dané skupiny.
30
4. I M P L E M E N T O V A N É ALGORITMY
Pro všechny výše uvedené přístupy platí, že sekvencer může být z hlediska
komunikační zátěže a spolehlivosti úzkým profilem řešení. Algoritmus implementovaný
v animačním systému využívá první přístup.
Algoritmus pro totální řazení zpráv pomocí sekvenceru je v animačním
systému reprezentován třídou TotalOrderingSequencer [Obrázek 9], která
dědí z abstraktní třídy RingFullSystemAlgorithm, protože algoritmus běží
v systémech s topologií úplného grafu. Třída TotalOrderingSequencer implementuje
abstraktní metody, které dědí z tříd AbstractAlgorithm a RingFullSystemAlgorithm.
Samotný algoritmus pro totální řazení zpráv pomod
sekvenceru je simulován metodami nextStep afinishStateTransition. Metoda
nextStep zahajuje přechod systému do nového stavu tím, že zahájí odesílání
zpráv z uzlů, které chtějí rozeslat zprávu, pomocí metody multicastMessage
a případně zahájí rozesílání informací o pořadí zpráv, které sekvencer přijal
v předchozím kroku, pokud takové zprávy existují. Metoda finishStäteTransition
je zavolána ve chvíli, kdy je komunikace dokončena, a simuluje
přijetí rozesílaných zpráv. Přijaté zprávy jsou vloženy do front jednotlivých
uzlů. Pokud sekvencer rozesílal informace o pořadí doručených
zpráv, jsou zprávy, kterých se tyto informace týkají, ve frontách uzlů seřazeny
a v následujícím kroku odstraněny.
Animace algoritmu pro totální řazení zpráv pomocí sekvenceru umožňuje
zpožďování zpráv přes několik kroků algoritmu, aby mohla být simulována
situace, kdy uzel od sekvenceru obdrží informaci o pořadí zprávy
dřív, než obdrží samotnou zprávu. Z tohoto důvodu používá ovládání animace
posuvník pro výběr intervalu hodnot pro zpoždění zpráv. Třída TotalOrderingSequencer
tedy obsahuje metodu changeMessagesDelay sloužící
pro změnu krajních hodnot tohoto intervalu.
Objekty třídy TotalOrderingSequencerData slouží pro ukládání dodatečných
dat pro jednotlivé stavy systému (vlastnost algorithmSpecific třídy Systemstäte).
Jedná se o informace o tom, které uzly byly označeny uživatelem
pro rozesílání zpráv. Tyto objekty dále také udržují fronty zpráv, které jsou
na cestě k jednotlivým uzlům.
Zasílané zprávy jsou reprezentovány třídou TosMessage. Tato třída neimplementuje
rozhraní Message a její objekty nejsou přímo vkládány do
jednotlivých komunikačních kanálů a nejsou ani vykreslovány v rámci systému
(uživateli je pouze indikována aktivita komunikačního kanálu). Objekty
třídy TosMessage slouží jen jako pomocné datové struktury, které
umožňují implementaci zpožďování přenášených zpráv.
31
4. I M P L E M E N T O V A N É ALGORITMY
Algoritmus pro totální řazení zpráv pomocí sekvenceru využívá dodatečnou
paměť v uzlech, která je reprezentována třídou ToSequencerMemContent
implementující rozhraní MemoryContent. Paměť uzlu udržuje frontu
přijatých zpráv a počet zpráv již rozeslaných daným uzlem.
Třída TosStoredSystem reprezentuje uložený systém (běhové prostředí)
pro algoritmus pro totální řazení zpráv pomocí sekvenceru.
32
Cp MemoryContent
ToSequencerMemContent
Class
-1
Fields
0
messagesSentNum : Number
orderedNum : Number
orderQueue: string[]
queue: string[]
receivedNum : Number
- Methods
O drawíCocrdinates coordinates CanvasRenderingContext2D ctx): void
StoredSystem
Class
- Fields
* scenarios: Object[]
RingFullSystemAlgorittm V
Abstract Class
-> AbstractAkjoritrim
"A"
TosStoredSystem
Class
-t> StoredSystem
B Fields
* numberOfNodes: Number
0 sequencerld : Number
TotalOrderingSequencerData *
Class
3 Fields
* userChangedNodes: bool[]
T o s M e s s a g e
Class
B Fields
0 delay: Number
•
sender: Number
seq : Number
pendingMessages: TosMessage[]
-J
TotalOrderingSequencer r
Class
"t> RingFullSystem Algorithm
- Fields
maxDelay: Number
^ a minDelay: Number
* a sequencerld : Number
~ Methods
® a _createSystem(Number numberOfNodes. Number sequencerld) : void
® a createMessagefNumber n. Number i) : string
O createSystemO : void
O exportfbool includeScenario): void
® a exportScenariojTosStoredSystem sys): void
® a finishStateTransitionO : void
® a getDelayO : Number
® a getMessagesOrder() I stringfj
O changeMessagesDelay(Number min, Number max): void
^ a multicastMessagefNode node): void
© nextStepO : void
© openStoredScenario(Number syslndex. Number scenariolndex. StorageTypeEnum storage) : void
® a prepareMessageQ : void
©a prepareNextStepO : void
O processClickfCoordinates coordinates) :void
© restartFromlnitialO : void
O stepBacki): bool
Obrázek 9: Diagram tříd zobrazující třídy reprezentující animaci totálního řazení zpráv
pomocí sekvenceru.
5 Rozšiřování aplikace
Aplikaci lze rozšířit implementací animace dalších algoritmů a také přeložením
uživatelského rozhraní aplikace do dalších jazyků.
5.1 Implementace animace algoritmu
Pro přidání animace algoritmu je potřeba vytvořit metody, které budou
obsluhovat požadavky na zobrazení stránky s animací algoritmu a nápo­
vědy1
k ovládání animace. Tyto metody jsou součástí řadičů, které se nacházejí
v souborech v adresáři -IControllers1
. V případě přidávání animace
algoritmu patřícího do skupiny algoritmů, která ještě není definována, je
třeba vytvořit nový řadič reprezentující danou skupinu algoritmů. Tento
řadič musí dědit z třídy BaseController. [Ukázka 1]
[ R o u t e P r e f i x ( " L e a d e r E l e c t i o n " ) ]
p u b l i c c l a s s L e a d e r E l e c t i o n C o n t r o l l e r : BaseController
{
// GET: L e a d e r E l e c t i o n / H i r s c h b e r g S i n c l a i r
[ R o u t e ( " H i r s c h b e r g S i n c l a i r " ) ]
p u b l i c ActionResult H i r s c h b e r g S i n c l a i r ( )
{
return View();
}
// GET: L e a d e r E l e c t i o n / H i r s c h b e r g S i n c l a i r / H e l p
[Route("HirschbergSinclair/Help")]
p u b l i c ActionResult H i r s c h b e r g S i n c l a i r H e l p ( )
{
return View();
}
}
Ukázka 1: Kód řadiče pro algoritmy pro volbu vedoucího prvku obsahujícího
metody pro Hirschberg-Sinclairův algoritmus a jeho nápovědu.
1
Pro správnou funkčnost odkazu na nápovědu, musí být cesta (adresa) nápovědy
ve tvaru x/Help, kde x je adresa stránky s animad daného algoritmu. Cestu lze
změnit pomocí anotace [Route("")] stejně jako na [Ukázce 1].
2
Symbol - reprezentuje kořenový adresář aplikace.
34
5. ROZŠIŘOVÁNÍ APLIKACE
Pro přidávaný algoritmus je dále potřeba vytvořit pohled, tedy webovou
stránku, na které bude algoritmus animován. Pohledy jsou umístěny v adresáři
-IViews obsahujícím podadresáře odpovídající jednotlivým řadičům
(tedy skupinám algoritmů). V těchto adresářích se nacházejí pohledy pro
jednotlivé algoritmy a jejich nápovědy. Adresář Views navíc obsahuje podadresář
Shared, který obsahuje části pohledů sdílené ostatními pohledy.
@{
ViewBag.Title = Resources.HirschbergSinclair;
ViewBag.UseNodeSwapping = t r u e ;
ViewBag.UselnitialNode = falše;
ViewBag.UseScenarios = falše;
}
<div class="controls-group controls-group-not-last">
@Html.Partial("_PartialCreateRingFullSystemControls")
</div>
<div class="controls-group controls-group-not-last">
@ H t m l . P a r t i a l ( " _ P a r t i a l I m p o r t s C o n t r o l s " )
</div>
<div class="controls-group controls-group-not-last">
@ H t m l . P a r t i a l ( " _ P a r t i a l A n i m a t i o n C o n t r o l s " )
</div>
<div class="controls-group">
@ H t m l . P a r t i a l ( " _ P a r t i a l E x p o r t C o n t r o l s " )
</div>
(Ssection S c r i p t s
{
@Scripts.Render("~/bundles/hirschberg-sinclair_"
+ CultureHelper.GetCurrentCulture())
J
Ukázka 2: Pohled pro Hirschberg-Sinclairův algoritmus.
Jak lze vidět na ukázce pohledu pro Hirschberg-Sinclairův algoritmus
[Ukázka 2], pohled se skládá ze tří částí. V první části jsou specifikovány
parametry pro jednotlivé částečné pohledy (moduly), ze kterých je výsledná
stránka poskládána. Pak následuje samotné poskládání stránky
z jednotlivých částí a nakonec jsou připojeny skripty starající se o animaci
algoritmu.
35
5. ROZŠIŘOVÁNÍ APLIKACE
Částečné pohledy (moduly), z nichž se skládá ovládání animace algoritmu,
se nacházejí v adresáři -IViewsIShared a jedná se o soubory:
• _PartialAnimationControls.cshtml,
• _PartialCreateMeshSystemControls.cshtml,
• _PartialCreateRingFullSystemControls.cshtml,
• _PartialExportControls.cshtml,
• _PartialImportsControls.cshtml.
Soubory s moduly pro nápovědu se nacházejí ve stejném adresáři. Jejich
jména místo podřetězce Controls obsahují řetězec Help. Parametry, kterými
lze měnit vlastnosti modulů (jak pro nápovědu, tak i pro ovládání animace),
jsou popsány v podobě komentářů v příslušných souborech.
Implementace animace algoritmu (skriptové části) spočívá v implementaci
třídy reprezentující animovaný algoritmus. Tato třída dědí z jedné
z abstraktních tříd RingFullSystemAlgorithm, nebo MeshSystemAlgorithm.3
Dědění se provádí pomocí funkce _extends a volání konstruktoru rodičovské
třídy v konstruktoru potomka s kontextem potomka. [Ukázka 3] Třída
reprezentující animovaný algoritmus musí implementovat abstraktní metody,
které zdědila z třídy AbstractAlgorithm a z jedné ze dvou tříd, ze které
přímo dědí.
Základní ideou pro práci se systémem (instancí třídy System) a jeho
stavy v aktuálně implementovaných algoritmech je vykreslování rozpracovaného
stavu systému. To znamená, že ve chvíli, kdy je systém vytvořen,
je kromě jeho iniciálního stavu do systému vložen ještě jeden stav, který je
kopií iniciálního stavu a který je použit jako aktuální stav systému, což
znamená, že tento stav je zobrazován uživateli a animovaný algoritmus
nad tímto stavem pracuje. Algoritmus tento stav upravuje podle vstupů
uživatele až do chvíle, kdy systém přejde do dalšího stavu (tzn. je dokončena
komunikace). V tuto chvíli algoritmus upraví systém na základě dokončené
komunikace a definovaných akcí, stav zakonzervuje a podle něj
vytvoří nový stav, který přidá do systému a nastaví jako aktuální. Nový
stav je zobrazen uživateli a algoritmus nad tímto stavem pracuje, dokud
systém nepřejde do dalšího stavu.
3
Popis struktury klientské části se nachází v podkapitole 3.3.1. Implementované
algoritmy a jejich struktura jsou popsány ve 4. kapitole.
36
5. ROZŠIŘOVÁNÍ APLIKACE
Implementace animace algoritmu vyžaduje také implementaci funkce getAlgorithmlnstance,
která umožňuje skriptům pracujícím s ovládacími prvky
a uživatelskými vstupy získat přístup k instanci aktuálně animovaného al­
goritmu.
f u n c t i o n getAlgorithmInstance() {
return new RaymondQ;
}
var Raymond = f u n c t i o n () {
MeshSystemAlgorithm.call(this, "Raymond", raymondSettings);
};
_extends(Raymond, MeshSystemAlgorithm);
Ukázka 3: Funkce getAlgorithmlnstance pro Raymondův algoritmus a definice
třídy Raymond, respektive jejího konstruktoru, který volá konstruktor
rodičovské třídy MeshSystemAlgorithm se svým kontextem. Kód uvedený na
ukázce je vyžadován pro správnoufunkčnost animace a jejího ovládání. Konstruktor
může navíc obsahovat definici vlastností dané třídy.
Dále je doporučeno vytvořit objekt reprezentující nastavení4
specifická pro
animaci přidávaného algoritmu. Tento objekt se předává jako parametr
konstruktoru třídy, ze které animace algoritmu dědí. Pokud algoritmus
specifická nastavení nevyužívá je možné použít x = null nebo x = {}, kde x
reprezentuje jméno objektu uchovávajícího nastavení. Vytvoření prázdného
objektu nastavení, místo pouhého předání hodnoty null, respektive
{}, usnadní případné budoucí použití specifických nastavení pro daný algoritmus
tím, že odbourá nutnost zásahu do více souborů, ke kterému by
při pozdějším přidávání nastavení došlo.
Pokud algoritmus využívá textové řetězce zobrazované uživateli (například
informační zprávy), které by měly být lokalizovány do různých jazyků,
je potřeba vytvořit objekty uchovávající tyto řetězce.5
Dále je také možné doimplementovat úložiště a uložené systémy (běhová
prostředí) pro daný algoritmus a případně další libovolné pomocné
třídy a funkce.
4
Více informad v podkapitole 6.2.
5
Informace o lokalizaci uživatelského rozhraní se nacházejí v podkapitole 5.2.
37
5. ROZŠIŘOVÁNÍ APLIKACE
Skripty klientské části aplikace jsou umístěny v adresáři -/Scripts, který obsahuje
následující podadresáře:
• Help - obsahuje skripty pro nápovědu.
• HomePage - obsahuje skripty pro úvodní stránku aplikace.
• LeaderElection, Multicast, MutualExclusion - obsahují animované algoritmy
rozdělené do skupin, které odpovídají rozdělení řadičů. Každý
z těchto adresářů obsahuje podadresáře reprezentující jednotlivé implementované
algoritmy z dané skupiny. V těchto podadresářích se
nacházejí soubory skriptů, které řeší animaci daného algoritmu.
• Resources - obsahuje objekty ukládající textové řetězce zobrazované
uživateli.
• Settings - obsahuje nastavení klientské části aplikace.
• Shared - obsahuje skripty sdílené různými algoritmy, jako jsou třídy
reprezentující základní prvky systému (uzly, komunikační spoje, systém,
stavy atd.), třídy sloužící jako základ pro implementaci algoritmů
a také funkce, které slouží pro obsluhu ovládacích prvků animace.
Připojení skriptů do webových stránek (pohledů) se provádí pomocí balíků
(bundles) [40]. Balíky se využívají za účelem zmenšení množství přenesených
dat a pro snížení počtu požadavků webového prohlížeče na
server. Balík skriptů umožní spojení více souborů do jednoho. Zároveň je
provedeno zmenšení velikosti jednotlivých souborů (odstraněním komentářů
apod.). Pro konfiguraci balíků slouží statická metoda RegisterBundles
třídy BundleConfig, která se nachází v souboru ~lApp_StartlBundleConfig.es.
[Ukázka 4]
Kromě souborů, které byly přidány v rámci implementace animace algoritmu,
musí balík skriptů obsahovat také soubor, v němž je definována
bundles.Add(new ScriptBundle("~/bundles/raymond_cs-CZ").Include(
"~/Scripts/Shared/mesh-system-algorithm.js"j
"~/Scripts/MutualExclusion/Raymond/*.js",
"~/Scripts/Shared/mesh-systém-specific-controls.jS"J
"~/Scripts/Settings/raymond. j s " ,
"~/Scripts/Resources/cs-CZ/raymond.js"))j
Ukázka 4: Část kódu uvnitř metody RegisterBundles přidávající balík skriptů
s textovými řetězci lokalizovanými pro kulturu cs-CZ pro Raymondův algo­
ritmus.
38
5. ROZŠIŘOVÁNÍ APLIKACE
třída, z níž implementace algoritmu dědí, a také soubor obsahující funkce
pro obsluhu ovládacích prvků animace odpovídající třídě, ze které implementace
algoritmu dědí. Pokud implementovaný algoritmus dědí z třídy
MeshSystemAlgorithm, pak balík musí obsahovat soubory mesh-system-algorithm.js
amesh-system-specific-controls.js. Dědí-liz třídy RingFullSystemAlgorithm,
musí balík obsahovat soubory ring-full-system-algorithm.js a ring-full-
system-specific-controls.js.
Balík dále obsahuje soubor, ve kterém je definován objekt obsahující
nastavení specifická pro přidávaný algoritmus. Pokud animace algoritmu
využívá textové řetězce lokalizované do různých jazyků, je potřeba vytvořit
balík pro každou implementovanou kulturu. Balíky pro jednotlivé kultury
se pak liší jen v souborech obsahujících lokalizované textové řetězce.
Balík se do pohledu připojí tak, že se jeho název doplní o kód aktuální kultury.
Název balíku na [Ukázce 4] končí na cs-CZ. Na [Ukázce 2] pak lze
vidět, že za název vkládaného balíku je připojen kód aktuálně vybrané kultury.
Tento přístup umožňuje do stránky vložit jen soubory skriptů, které
odpovídají jazyku, ve kterém bude uživatelské rozhraní zobrazeno.
Do balíku není třeba přidávat soubory skriptů sdílené všemi algoritmy,
jako jsou třídy reprezentující základní prvky systému, třídu AbstractAlgorithm
ani základní ovládání animace apod. Všechny tyto soubory jsou součástí
balíku připojeného do šablony Layoutcshtml.
Posledním krokem implementace animace nového algoritmu je přidání
odkazu na nově implementovaný algoritmus do nabídky, která se nachází
v souboru ~/Views/Shared/_PartialMenuContent.cshtml. Tím dojde k umístění
odkazu jak do levostranné nabídky, tak i na úvodní stránku aplikace.
5.2 Lokalizace uživatelského rozhraní do dalších jazyků
Aplikace s různými jazyky pracuje v podobě kultur6
[41]. V aktuální verzi
aplikace podporuje angličtinu (en-US) a češtinu (cs-CZ). Jazyk, ve kterém
je zobrazeno rozhraní aplikace, je vybrán podle následujících kritérií:
• Pokud uživatel s aplikací dosud nepracoval nebo neměnil jazyk, je vybrána
kultura na základě seznamu jazyků v jeho prohlížeči. Pokud
6
Kultura je vyjádřena kódem ve tvaru xx-yy, kde xx je kód jazyka a yy je kód státu
nebo území (například cs-CZ nebo en-US).
39
5. ROZŠIŘOVÁNÍ APLIKACE
zde uvedená kultura není aplikací podporována, je vybrána podobná
(obsahující stejný jazyk). Pokud není podobná kultura mezi podporovanými
nalezena, je vybrána výchozí.
• Uživatelem zvolený jazyk (kultura) je uložen v podobě cookie7
[42].
Pokud cookie existuje (je poslána spolu s požadavkem na zobrazení
stránky), je kultura zvolena podle jejího obsahu.
Textové řetězce využívané pro uživatelské rozhraní aplikace lze rozdělit
do dvou skupin: řetězce používané klientskou částí a ostatní, používané
zejména serverovou částí aplikace pro konstrukci webových stránek.
Textové řetězce pro serverovou část se nacházejí v adresáři -/Resources.
Jedná se o soubory Resources.X.resx8
, kde X je kód implementované kultury.
Soubor pro výchozí kulturu (en-US) má název Resources.resx.
Pro přidání další kultury stačí přidat soubor s příslušným jménem. Pro
správnou funkci je potřeba ve vlastnostech souboru nastavit, aby se po přeložení
do podoby objektu, tento objekt nacházel ve jmenném prostoru AlgorithmsVisualiser.Resources.
Dále je doporučeno nastavit hodnotu9
Build
Action na Embedded Resource.
Aby byla aplikace schopná pracovat s novou kulturou, je potřeba přidat
kód dané kultury do seznamu již implementovaných, který je uložen
jako statická kolekce joultures, která je součástí statické třídy CultureHelper
nacházející se v souboru ~IHelperslCultureHelper.cs. Kultura, která se nachází
na prvním místě v tomto seznamu je výchozí kulturou. Pro kultury
se stejným kódem jazyka (například en-US a en-GB) platí, že pokud je z nějakého
důvodu požadován jen jazyk (tedy en), vybere se ta kultura, která
je v seznamu první mezi všemi kulturami se stejným jazykem.
Mezi textové řetězce používané klientskou částí patří zejména zprávy
informující o průběhu algoritmu a o změnách, ke kterým v systému došlo,
7
Jako cookie se v protokolu HTTP označuje malé množství dat, která webový server
pošle prohlížeči a ten je uloží na počítači uživatele. Při každé další návštěvě
téhož serveru pak prohlížeč tato data posílá zpět serveru. Cookies běžně slouží
k rozlišování jednotlivých uživatelů, ukládají se do nich uživatelské předvolby
apod.
8
Soubory s příponou .resx jsou soubory ve formátu XML, ve kterých jsou textové
řetězce uloženy v párech jméno - hodnota. [43]
9
Název volby a hodnota se týkají vývojového prostředí Microsoft Visual Studio.
40
5. ROZŠIŘOVÁNÍ APLIKACE
dále také chybové zprávy a případně textové řetězce spjaté s dynamicky
generovanými ovládacími prvky. S těmito řetězci pracují třídy a pomocné
funkce starající se o animaci algoritmů a obsluhu uživatelských vstupů.
Vzhledem k tomu, že jsou tyto třídy a funkce napsány v jazyce JavaScript,
jsou i řetězce uloženy v objektech napsaných v jazyce JavaScript, které jsou
umístěny v souborech v adresáři -/Scripts/Resources. Tento adresář obsahuje
podadresáře odpovídající jednotlivým implementovaným kulturám.
Každý z těchto adresářů obsahuje soubory s objekty, v nichž jsou řetězce
uloženy.
V souboru general.js se nacházejí řetězce, které jsou společné pro
všechny implementované algoritmy. Ostatní soubory slouží pro ukládání
textových řetězců využívaných jednotlivými animacemi algoritmů a obsahují
zejména zprávy informující o průběhu daného algoritmu.
Některé textové řetězce jsou uloženy jako vlastnosti daného objektu,
jiné jsou návratovou hodnotou metody. [Ukázka 5] Návratové hodnoty
metod jsou využity zejména v případech, kdy je do daného řetězce doplňována
nějaká hodnota, případně seznam hodnot. Využití metody také
umožňuje postihnout případy, kdy na doplňované hodnotě závisí, zda je
daný text v jednotném, nebo v množném čísle.
var raymondRes = {
cs_ ENDING: "Kořen ukončí svou k r i t i c k o u s e k c i v následujícím kroku.",
cs_ LENGTH: f u n c t i o n (length) {
var s = "Délka kritické sekce: " + length;
i f (length == 1) {
s += " krok."j
}
e l s e i f (length > 1 && length <= 4) {
s += " kroky.";
}
e l s e {
s += " kroků.";
}
return s;
}
};
Ukázka 5: Část kódu objektu obsahujícího textové řetězce pro Raymondův algoritmus.
V prvním případě se jedná o vlastnost objektu, ve druhém o metodu.
41
5. ROZŠIŘOVÁNÍ APLIKACE
Přidání klientské části nové kultury se provádí přidáním podadresáře
v adresáři -/Scripts/Resources, jehož název odpovídá kódu přidávané kultury
a do něhož se vloží soubory s přeloženými řetězci.
Následně je nezbytné vytvořit pro novou kulturu balíky skriptů10
. Pro
každý balík závisející na zvolené kultuře je třeba vytvořit další balík s novou
kulturou [Ukázka 6]. Balíky skriptů závisející na zvolené kultuře lze
poznat podle toho, že ve svém názvu obsahují kód nějaké kultury a jejich
součástí je alespoň jeden soubor nacházející se v některém z podadresářů
adresáře -/Scripts/Resources.
bundles.Add(new ScriptBundle("~/bundles/raymond_de-DE").Include(
"~/Scripts/Shared/mesh-system-algorithm.js",
"~/Scripts/MutualExclusion/Raymond/*.js",
"~/Scripts/Shared/mesh-systém-specific-controls.jS"J
"~/Scripts/Settings/raymond.js",
"~/Scripts/Resources/de-DE/raymond.js"))j
Ukázka 6: Vytvoření balíku skriptů s textovými řetězci pro němčinu (de-DE)
pro Raymondův algoritmus. Změny oproti [Ukázce 4] jsou vyznačeny zeleně.
Balíky skriptů jsou představeny v podkapitole 5.1.
42
6 Administrace systému
6.1 Předdefinovaná prostředí a běhy algoritmů
Aplikace umožňuje uživateli vytvořit vlastní prostředí (distribuovaný systém),
ve kterém animovaný algoritmus poběží. Nicméně aplikace poskytuje
také předdefinovaná prostředí spolu s předdefinovanými úlohami
(scénáři pro běh algoritmů). Tato prostředí jsou uložena na serveru a uživatel
má možnost je pomocí aplikace načíst.
Prostředí jsou uložena v adresáři ~/App_Data/PredefinedSystems v souborech
s příponou .json [44]. Pro každý implementovaný algoritmus se zde
nachází jeden soubor, jehož jméno odpovídá jménu algoritmu, které je uloženo
ve vlastnosti name třídy implementující animaci algoritmu. Toto
jméno je předáváno jako parametr konstruktoru třídy, ze které třída implementující
algoritmus dědí. Stejné jméno je přiřazeno souborům, které jsou
vytvořeny aplikací během ukládání exportovaných prostředí a běhů algo­
ritmů.
Soubory s předdefinovanými prostředími odpovídají přesně souborům,
které jsou vytvářeny aplikací při ukládání vyexportovaných prostředí
a běhů. Vzhledem k tomu, že JSON je textový formát je možné soubory
upravovat libovolným textovým editorem. Doporučený postup pro editaci
obsahu souborů je však prostřednictvím aplikace a jejích možností pro export
a ukládání prostředí a běhů algoritmů.
Vzhledem k tomu, že v aktuální verzi aplikace neposkytuje rozhraní
pro administraci předdefinovaných prostředí, je jediným způsobem, jak
soubory na serveru upravovat, přímý přístup k těmto souborům, například
pomocí FTP [45].
6.2 Nastavení klientské části aplikace
Klientská část aplikace obsahuje nastavení, pomocí kterých lze měnit některé
vlastnosti animace, zejména vzhled vykresleného systému. Soubory
s nastaveními se nacházejí v adresáři -/Scripts/Settings. Nastavení jsou uložena
v podobě vlastností objektů napsaných v jazyce JavaScript umístěných
v jednotlivých souborech.
43
6. A D M I N I S T R A C E SYSTÉMU
V souboru global.js se nacházejí nastavení společná pro všechny animované
algoritmy, například:
• povolený počet uzlů systému,
• velikost uzlů, písmo, barvy použité pro různé stavy uzlů,
• barvy komunikačních kanálů, velikost šipky znázorňující směr komunikačního
kanálu, tloušťka čáry,
• minimální velikost elementu canvas, barva jeho pozadí a velikost
okrajů.
var g l o b a l S e t t i n g s = {
system: {
maxNodesNumber: 20,
minNodesNumber: 2
},
node: {
radius: 20,
lineWidth: 2,
i d : {
v e r t i c a l O f f s e t : 1,
f o n t : " A r i a l " ,
f o n t S i z e : 24,
fontWeight: "normal"
b
c o l o r s : [
edge: "#808080", font: "#808080
edge: "#33ff00", font: "#808080
edge: "#00ffff", font: "#808080
edge: "#ff0000", font: "#808080
edge: "#bd95fc"J
font: "#808080
edge: "#ff8000", font: "#808080
edge: "#ff8000", font: "#808080
edge: "#00ffff", font: "#808080
edge: "#33ff00", font: "#808080
Ukázka 7: Část globálního nastavení. Hodnoty pro nastavení rozměrů
(size, height, width, radius apod.) a vzdáleností (distance, padding, offset
apod.) jsou v pixelech. Pro barvu je možné využít libovolný řetězec podporovaný
CSS [46], například hexadecimální kód (#bd95fc), RGB hodnotu
(rgb(189, 149, 252)) apod.
44
6. A D M I N I S T R A C E SYSTÉMU
V dalších souborech se nacházejí nastavení specifická pro jednotlivé animované
algoritmy. Obvykle se jedná o parametry, které mění způsob, jakým
jsou vykresleny obsahy pamětí uzlů, případně zprávy zasílané uzly.
Nastavení specifická pro jednotlivé algoritmy umožňují také změnit
hodnoty v globálních nastaveních. Tato změna se pak týká pouze animace
daného algoritmu. Změnu je možné provést tak, že se objektu reprezentujícímu
nastavení pro daný algoritmus přidá vlastnost, která odpovídá měněné
vlastnosti v objektu globálního nastavení. [Ukázka 8]
var raymondSettings = {
memoryContent: { ... },
node: {
rádius: 30
}
_h
Ukázka 8: Nastavení pro Raymondův algoritmus (vynechána nastavení pro
paměť uzlů) se změněnou velikostí poloměru vykresleného uzlu z 20px na
30px.
Soubory nastavení lze upravovat pomocí libovolného textového editoru.
Aplikace neposkytuje rozhraní pro změnu hodnot nastavení. Stejně jako
v případě předdefinovaných běhových prostředí je možné využít FTP pro
přístup k souborům nastavení uloženým na serveru.
Nastavení klientské části aplikace platí globálně pro všechny uživatele.
Aplikace v současné verzi neumožňuje jednotlivým uživatelům měnit nastavení
podle svých preferencí.
45
7 Závěr
Cílem této práce bylo vytvoření webové aplikace, která slouží k interaktivní
prezentaci a ke studiu chování distribuovaných algoritmů. Práce
stručně představuje problematiku distribuovaných algoritmů a uvádí některé
webové orientované nástroje zabývající se animací algoritmů.
Práce dále shrnuje požadavky kladené na vytvořený systém, na jejichž
základě byly zvoleny nástroje pro jeho implementaci. V práci je také uveden
návrh struktury aplikace s ohledem na použité implementační ná­
stroje.
Na základě návrhu byl vytvořen animační systém, do kterého byly
doimplementovány animace algoritmu pro předávání příznaku v kruhové
topologii, Raymondova algoritmu (oba řeší distribuované vzájemné vyloučení),
Hirschberg-Sinclairova algoritmu (řeší volbu vedoucího prvku) a algoritmu
pro totální řazení zpráv při skupinové komunikaci pomocí
sekvenceru. Jednotlivé algoritmy jsou v práci stručně představeny a je uvedena
struktura jejich implementace.
Práce dále popisuje postupy pro rozšíření aplikace o animace dalších
algoritmů a také pro lokalizaci uživatelského rozhraní do dalších jazyků.
Nakonec jsou v práci shrnuty možnosti pro administraci systému, která
se týká správy předdefinovaných běhových prostředí pro animaci algoritmů
a nastavení, která umožňují změnu některých parametrů uživatelského
rozhraní.
V rámci práce bylo dosaženo vytyčených cílů. Vytvořená aplikace byla
nasazena na webový hosting ASPone.cz [47] a je dostupná na adrese
http://algoritmy-ds.aspone.cz/. Vytvořenou aplikaci je možné použít jako pomůcku
při výuce distribuovaných algoritmů.
Vytvořená aplikace poskytuje prostor pro budoucí vývoj, který se může
zaměřit na následující rozšíření:
• implementace animace dalších algoritmů,
• rozšíření kolekce předdefinovaných prostředí a běhů algoritmů,
• přidání jazyků podporovaných uživatelským rozhraním,
• vytvoření uživatelského rozhraní pro nastavení klientské části aplikace
a umožnění každému uživateli tato nastavení měnit,
• vytvoření rozhraní pro administraci systému.
46
Seznam použité literatury
[1] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 1, Characterization of distributed
systems, s. 1-35. ISBN 978-0-13-214301-1.
[2] LYNCH, N . A. Distributed Algorithms. First Edition. San Francisco,
California: Morgan Kaufmann Publishers, Inc., 1996. 904 s. ISBN 978-
1-55860-348-6.
[3] GALLES, D. Data Structure Visualizations [online]. Verze: 1.5. [7. 12.
2016]. Dostupne z: <http://www.cs.usfca.edu/~galles/visualization/
Algorithms.html>.
[4] HALIM, S. - HALIM, F., et al. VisuAlgo [online]. [7. 12. 2016].
Dostupne z: <https://visualgo.net/>.
[5] VEGH, L. Algorithm Animations and Visualizations [online]. [7. 12.
2016]. Dostupne z: <http://www.algoanim.ide.sk/>.
[6] MOSBAH, M., et al. ViSiDiA [online]. LaBRI, Universite Bordeaux.
Verze: 1.5.1. [8. 12. 2016]. Dostupne z: <http://visidia.labri.fr/html/
home.html>.
[7] BEN-ARI, M., et al. DA]: Distributed Algorithms in Java [program, ZIP].
Weizmann Institute of Science. Verze: 3.4. [8. 12. 2016]. Dostupne z:
<http://www.weizmann.ac.il/sci-tea/benari/software-and-learning-m
aterials/daj-distributed-algorithms-java>.
[8] KOLDEHOFE, B. - PAPATRIANTAFILOU, M. - HA, H. P. - TSIGAS,
P. LYDIAN: An Educational Animation Environment for Distributed Algorithms
and Protocols [program]. Chalmers university of technology.
Verze: 1.3.0. [8. 12. 2016]. Dostupne z: <http://www.cse.chalmers.se/
research/group/lydian/>.
[9] Wikipedia contributors. Java applet [online]. In Wikipedia, The Free
Encyclopedia. Verze: 3. 12. 2016 [Citace: 8. 12. 2016]. Dostupne z:
<https://en.wikipedia.org/w/index.php?title=Java_applet&oldid=752
837650>.
47
S E Z N A M POUŽITÉ LITERATURY
[10] Oracle. Java SE Runtime Environment 8 Downloads [online, program].
[8. 12. 2016]. Dostupné z: <http://www.oracle.com/technetwork/java/
javase/downloads/jre8-do wnloads-2133155.html>.
[11] MOSBAH, M., et al. ViSiDiA: Animations [online]. LaBRI, Université
Bordeaux. [8. 12. 2016]. Dostupné z: <http://visidia.labri.fr/html/
animations.html>.
[12] Wikipedia contributors. Adobe Flash [online]. In Wikipedia, The Free
Encyclopedia. Verze: 24. 11. 2016 [Citace: 8. 12. 2016]. Dostupné z:
<https://en.wikipedia.org/w/index.php?title=Adobe_Flash&oldid=75
1325915>.
[13] KOLDEHOFE, B. - PAPATRIANTAFILOU, M . - HA, H. P. - TSIGAS,
P. LYDIAN: FAQ [online]. Chalmers university of technology. [Citace:
8.12.2016]. Will there be a version for Windows?. Dostupné z: <http://
www.cse.chalmers.se/research/group/lydian/page3.html>.
[14] Microsoft Developer Network. ASP.NET MVC Overview [online].
Microsoft. [Citace: 10.12. 2016]. Dostupné z: <https://msdn.microsoft.
com/en-us/library/dd381412(v=vs.l08).aspx>.
[15] GALLOWAY, J. MVC 3 - Razor View Engine [online, video]. Microsoft
ASP.NET. Microsoft. 4. 4. 2011 [Citace: 10. 12. 2016]. Dostupné z:
<https://www.asp.net/mvc/videos/mvc-3/mvc-3-razor-view-engine>.
[16] WHATWG. HTML: Living Standard [online]. 12. 12. 2016 [Citace: 13.
12. 2016]. Dostupné z: <https://html.spec.whatwg.org/multipage/>.
[17] WHATWG. HTML: Living Standard [online]. 12. 12. 2016 [Citace: 13.
12.2016]. Oddíl 4.12.5, The canvas element. Dostupné z: <https://html.
spec.whatwg.org/multipage/scripting.html#the-canvas-element>.
[18] DEVERIA, A. Canvas (basic support). Can I use [online]. [Citace: 10.
12. 2016]. Dostupné z: <http://caniuse.com/#feat=canvas>.
[19] DEVERIA, A. Text API for Canvas. Can I use [online]. [Citace: 10. 12.
2016]. Dostupné z: <http://caniuse.com/#feat=canvas-text>.
[20] Mozilla Contributors. CSS [online]. Mozilla Developer Network.
Mozilla Foundation. Verze: 21.11. 2016 [Citace: 10.12. 2016]. Dostupné
z: <https://developer.mozilla.org/en-US/docs/Web/CSS$revision/
1145470>.
48
S E Z N A M POUŽITÉ LITERATURY
[21] Mozilla Contributors. JavaScript [online]. Mozilla Developer Network.
Mozilla Foundation. Verze: 21. 11. 2016 [Citace: 10. 12. 2016].
Dostupné z: <https://developer.mozilla. org/en-US/docs/Web/JavaScr
ipt$revision/l 145474>.
[22] The jQuery Foundation, jQuery [online]. [Citace: 12. 12. 2016].
Dostupné z: <http://jquery.com/>.
[23] Mozilla Contributors. Ajax [online]. Mozilla Developer Network.
Mozilla Foundation. Verze: 22.11. 2016 [Citace: 12.12. 2016]. Dostupné
z: <https://developer.mozilla.org/en-US/docs/AJAX$revision/1146
064>.
[24] Bootstrap Team. Bootstrap [online]. [Citace: 12. 12. 2016]. Dostupné z:
<http://getbootstrap.com/>.
[25] MORETO, S., et al. Bootstrap-select [online]. GitHub. [Citace: 12. 12.
2016]. Dostupné z: <https://github.com/silviomoreto/bootstrap-sele
ct>.
[26] KEMP, K. J. - KALKUR, R. Bootstrap-slider [online]. GitHub. [Citace:
12. 12. 2016]. Dostupné z: <https://github.com/seiyria/bootstrap-sli
der>.
[27] ASHKENAS, J., et al. Underscore^ [online]. [Citace: 12. 12. 2016].
Dostupné z: <http://underscorejs.org/>.
[28] ANDERSON, R. Adding a Controller [online]. Microsoft ASP.NET.
Microsoft. 17. 10. 2013 [Citace: 14. 12. 2016]. Dostupné z: <https://
www.asp.net/mvc/overview/getting-started/introduction/adding-a-
controller>.
[29] Microsoft Developer Network. Controller Class [online]. Microsoft.
[Citace: 14.12.2016]. Dostupné z: <https://msdn.microsoft.com/en-us/
library/system.web.mvc.controller(v=vs.H8).aspx>.
[30] Microsoft Developer Network. ControllerBase.ViewBag Property
[online]. Microsoft. [Citace: 14. 12. 2016]. Dostupné z: <https://msdn.
mierosoft.com/en-us/library/system.web.mvc.controllerbase.viewba
g(v=vs.H8).aspx>.
49
S E Z N A M POUŽITÉ LITERATURY
[31] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR, G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 15.2, Distributed mutual exclusion, s.
633-641. ISBN 978-0-13-214301-1.
[32] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR, G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 15.2.1, Algorithms for mutual
exclusion, cast A ring-based algorithm, s. 636-637. ISBN 978-0-13-
214301-1.
[33] RAYMOND, K. A Tree-Based Algorithm for Distributed Mutual
Exclusion. ACM Transactions on Computer Systems. February 1989,
Volume 7, Issue 1, s. 61-77.
[34] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR, G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 15.3, Elections, s. 641-646. ISBN 978-0-
13-214301-1.
[35] HIRSCHBERG, D. S. - SINCLAIR, J. B. Decentralized ExtremaFinding
in Circular Configurations of Processors. Communications of
the ACM. November 1980, Volume 23, Issue 11, s. 627-628.
[36] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR, G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 15.4, Coordination and agreement in
group communication, s. 646-659. ISBN 978-0-13-214301-1.
[37] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR, G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 15.4.3, Ordered multicast, s. 651-659.
ISBN 978-0-13-214301-1.
[38] COULOURIS, G. - DOLLIMORE, J. - KINDBERG, T. - BLAIR, G.
Distributed Systems: Concepts and Design. Fifth Edition. AddisonWesley,
2012. 1008 s. Kapitola 15.4.3, Ordered multicast, cast
Implementing total ordering, s. 654. ISBN 978-0-13-214301-1.
50
S E Z N A M POUŽITÉ LITERATURY
[39] DEFAGO, X. - SCHIPER, A. - URBAN, P. Total Order Broadcast and
Multicast Algorithms: Taxonomy and Survey [online, PDF]. [Citace: 17.
12. 2016]. Kapitola 7, Mechanisms for Message Ordering, s. 17-25.
Dostupne z: <https://infoscience.epfl.ch/record/52563/files/IC_TECH
_REPORT_200356.pdf>.
[40] ANDERSON, R. Bundling and Minification [online]. Microsoft
ASP.NET. Microsoft. 23. 8. 2012 [Citace: 18. 12. 2016]. Dostupne z:
<https://www.asp.net/mvc/overview/performance/bundling-and-mi
nification>.
[41] ANDERSON, R. - BOWDEN, D. - CALIXTO, B. - AFANA, N. Globalization
and Localization [online]. Microsoft. 14. 10. 2016 [Citace: 19. 12.
2016]. Cast Globalization and localization terms. Dostupne z: <https://
docs.microsoft.com/en-us/aspnet/core/fundamentals/localization>.
[42] BARTH, A. HTTP State Management Mechanism [online]. Internet
Engineering Task Force (IETF), April 2011 [Citace: 19. 12. 2016]. RFC
6265. Dostupne z: <https://tools.ietf.org/html/rfc6265>. ISSN 2070-
1721.
[43] Microsoft Developer Network. Resources in .resx File Format [online].
Microsoft. [Citace: 19.12. 2016]. Dostupne z: <https://msdn.microsoft.
com/en-us/library/ekyft91f(v=vs.100).aspx>.
[44] BRAY, T. The JavaScript Object Notation (JSON) Data Interchange Format
[online]. Internet Engineering Task Force (IETF), March 2014 [Citace:
19. 12. 2016]. RFC 7159. Dostupne z: <https://tools.ietf.org/html/
rfc7159>. ISSN 2070-1721.
[45] POSTEL, J. - REYNOLDS, J. File Transfer Protocol (FTP) [online].
Network Working Group, October 1985 [Citace: 19. 12. 2016]. RFC
959. Dostupne z: <https://tools.ietf.org/html/rfc959>.
[46] Mozilla Contributors. Color picker tool [online]. Mozilla Developer
Network. Mozilla Foundation. Verze: 19. 5. 2016 [Citace: 19.12. 2016].
Dostupne z: <https://developer.mozilla.org/en-US/docs/Web/CSS/
CSS_Colors/Color_picker_tool>.
[47] ASPone. ASPone.cz [online]. [Citace: 19. 12. 2016]. Dostupne z:
<http://www.aspone.cz/cz/>.
51
Seznam příloh
• Zdrojový kód aplikace v podobě projektu pro Visual Studio
• Diagram tříd zachycující strukturu celé klientské části se všemi implementovanými
algoritmy
52