MPM Simulator

Typ: konzolová aplikácia Prog. jazyk: C++ Widget toolkit: Qt

IDE: Qt Creator OS: Linux Licencia: GPL

Simulátor distribuovaných algoritmov v modeli posielania správ (MPM = Message passing model). Momentálne je dokončená konzolová verzia a na grafickom rozhraní sa stále pracuje. Hlavným prínosom programu, čím sa líši od ostatných podobného zamerania, je spôsob akým sa distribuované algoritmy importujú do programu. Na ich zápis sa nepoužíva skriptovací jazyk ani žiadny špeciálny, ale zapisujú sa priamo v C++ s použitím funkcií rozhrania simulátora, ale bez potreby jeho zdrojových kódov a rekompilácie celého programu. Algoritmus sa kompiluje samostatne do dynamickej knižnice a programom je načítaný až za behu.

Tento program som vytvoril za účelom ľahšieho pochopenia distribuovaných algoritmov, ktoré sú pri väčšej komplexnosti dosť náročné na predstavivosť. MPM Simulátor je vhodný na vyskúšanie známych algoritmov, rovnako ako aj na vytvorenie nových. Cieľom tiež bolo vytvoriť jednoduché rozhranie, ktoré zároveň obsahuje všetky nastavenia vyskytujúce sa v MPM modeli. Medzi nimi spomeniem: spoľahlivosť doručenia správy, FIFO / správy doručené v náhodnom poradí, zmysel pre orientáciu v sieti, anonymné siete / identifikátory, synchronicita a mnohé ďalšie. Keďže niektoré algoritmy sú navrhnuté len pre konkrétne nastavenia, umožňuje rozhranie simulátora špecifikovať aké nastavenia sú a aké nie sú prípustné.

Program je objektovo orientovaný a rozdelený do viacerých modulov.
Pred tým než je možné distribuovaný algoritmus simulovať je potrebné postaviť sieť výpočetných uzlov. Za týmto účelom slúži trieda z modulu networkScheme.cpp. Trieda obsahuje veľký počet funkcií, funktorov, preťažených operátorov s cieľom zjednodušenia tohto procesu. Pri vytváraní musí schéma zostať validná podľa pravidiel MPM modelu, čo táto trieda pri každej operácií kontroluje a v prípade nekorektnosti vyhodí výnimku.
Základným modulom je simulator.cpp, ktorý riadi väčšinovú časť simulácie. V architektúre sa nachádza medzi algoritmom a užívateľským rozhraním. Zavádza výpočetné uzly do siete, prijíma z nich signály, spracováva ich a časť v upravenej forme posiela do užívateľského rozhrania. Dôležitou súčasťou simulátora je agregovaná trieda CNetworkConfiguration z modulu networkConfiguration.cpp. Simuluje prostredie ktorým sa prenášajú správy, volí dĺžku posielania správy z povoleného intervalu a náhodne vyberá ktoré správy sa pri prenose stratia (podľa nastavenej spoľahlivosti prenosu). Pokiaľ sú kanály FIFO podľa nastavenia, je úlohou práve tejto triedy zabezpečiť aby sa správy nepredbiehali.
Trieda CNode z modulu node.cpp reprezentuje vypočetný uzol siete. Funkcia tejto triedy je porovnateľná s modemom spájajúcim počítač so sieťou. Poskytuje programátorovi distribuovaného algoritmu sieťové rozhranie pomocou ktorého môže uzol komunikovať s ostatnými uzlami s ktorými je prepojený. Trieda CNode tiež obsahuje virtuálne metódy spúšťané pri konkrétnych udalostiach, u ktorých sa predpokladá že budú preddefinová programátorom. Práve tieto metódy sú kompletnou definíciou algoritmu, jedná sa teda o programovanie riadené udalosťami (event driven programming).
Obalom distribuovaného algoritmu je hlavičkový súbor distributedAlgorithm.h, popisujúci štruktúru triedy v ktorej bude definícia algoritmu uložená. Táto trieda je pri načítaní algoritmu exportovaná a vďaka polymorfizmu sa použije práve preddefinovaná verzia. Obsahom triedy nie je len potomok CNode obsahujúci definíciu algoritmu, ale tiež vektor preferovaných sietí, prípustné a zároveň preferované nastavenia a tiež dve metódy, tzv. validátory, ktoré bližšie popíšem.
Okrem týchto modulov obsahuje program aj ďalšie, jednoduchšie, všeobecnejšieho zamerania, dostatočne popísané v komentároch zdrojových súborov.

schéma MPM Simulátora

Samotný beh simulácie môže byť nič nehovoriaci, nekonečný, dokonca aj nekorektný pokiaľ neexistuje kontrolná ruka nad jeho činnosťou, ktorá sleduje priebeh simulácie a posiela informácie užívateľovi o významných zmenách v sieti. Môže sa jednať napr. o termináciu ktorú algoritmus nevie detekovať. Za týmto účelom som pridal do rozhrania už spomenuté validátory, virtuálne funkcie ktoré sa podľa nastavenia spúšťajú v konkrétnych časových okamihoch a kontrolujú stav simulácie. V deklarácií triedy CDistributedAlgorithm sú prázdne pretože sa predpokladá že budú preddefinované programátorom. Ten má k dispozícií vo vstupných parametroch všetky stavové premenné, môže nariadiť zastavenie simulácie, alebo len poslať informačnú správu o stave užívateľovi.

Program bol implementovaný za výrazného využitia funkcionality Qt toolkit-u. Komunikácia medzi uzlami a simulátorom je riadená práve prostredníctvom Qt signálov. Moduly u ktorých sa predpokladá že budú rozhraním do budúceho grafického prostredia používajú kontajnery z Qt (z akademických účelov som používal v ostatných moduloch kontajneri a algoritmy z STL). Pri kompilácií programu použite Qt Creator alebo štandardný postup kompilácie "Qt-programov" z konzoly (qmake MPM_simulator.pro + make).
Aktuálna verzia má zatiaľ len konzolové rozhranie. Trochu interaktivity priniesli dva UNIX signály, preddefinované na konkrétny účel. Informácie o ovládaní zobrazíte spustením programu s argumentom -help.
Na odskúšanie doporučujem spustiť simuláciu ukážkové algoritmy. Sú to typické príklady z učebníc distribuovaných výpočtov. Tieto algoritmy je pred načítaním potrebné skompilovať, rovnakým postupom ako simulátor, s tým rozdielom že nepotrebujete všetky moduly simulátora (viď. *.pro súbor).

Ukážka výstupu programu. Správy sú v tvare [ čas ] popis udalosti.

[ - ] thread has started.
[ 0 ] validator repported: [CORRECT STATE] Admissible initial settings.
Simulation is starting with following settings:
algorithm - file name = ./libuniRingElection.so
algorithm - name = The Peterson / Dolev-Klawe-Rodeh algorithm
algorithm - description = Chef election in unidirectional ring with O(Nlog(N)) message complexity.
output = standart output
scheme = Circle
number of nodes = 3
speed = 0.8
latency = 500ms
min dispatch time = 200ms
max dispatch time = 1000ms
validator type = periodical validation with defined period length
validator period length = 1500ms
messages reliability = 100%
with sense of direction = false
direction of the edge = one direction
synchronicity = asynchronous
message ordering = ordered
initiators = subset of nodes
nodes with unique identificators = true
-----
[ 0 ] simulation started.
[ 2 ] node '45' waked up
[ 2 ] node '45' started computation
[ 2 ] message 'one' was sent from node 45 to node 17
[ 2 ] node '45' finnished computation
[ 3 ] node '54' waked up
[ 3 ] node '54' started computation
[ 3 ] message 'one' was sent from node 54 to node 45
[ 3 ] node '54' finnished computation
[ 411 ] node '17' waked up
[ 411 ] node '17' started computation
[ 411 ] node '17' changed its flag
Node '17' flags:
    chef = false
[ 411 ] node '17' finnished computation
[ 410 ] message 'one' was received by node 17 from node 45
[ 411 ] node '17' started computation
[ 411 ] message 'one' was sent from node 17 to node 54
[ 411 ] node '17' finnished computation
[ 436 ] message 'one' was received by node 45 from node 54
[ 436 ] node '45' started computation
[ 436 ] message 'two' was sent from node 45 to node 17
[ 437 ] node '45' finnished computation
[ 501 ] validator repported: [CORRECT STATE] Chef hasn't been elected yet.
[ 1019 ] message 'one' was received by node 54 from node 17
[ 1019 ] node '54' started computation
[ 1019 ] message 'two' was sent from node 54 to node 45
[ 1019 ] node '54' finnished computation
[ 1268 ] message 'two' was received by node 17 from node 45
[ 1268 ] node '17' started computation
[ 1269 ] message 'two' was sent from node 17 to node 54
[ 1269 ] node '17' finnished computation
[ 1733 ] node '54' started computation
[ 1733 ] message 'one' was sent from node 54 to node 45
[ 1733 ] node '54' finnished computation
[ 1733 ] message 'two' was received by node 54 from node 17
[ 1755 ] message 'two' was received by node 45 from node 54
[ 1755 ] node '45' changed its flag
Node '45' flags:
    chef = false
[ 1755 ] node '45' started computation
[ 1755 ] node '45' finnished computation
[ 2001 ] validator repported: [CORRECT STATE] Chef hasn't been elected yet.
[ 2229 ] message 'one' was received by node 45 from node 54
[ 2229 ] node '45' started computation
[ 2230 ] message 'one' was sent from node 45 to node 17
[ 2230 ] node '45' finnished computation
[ 2942 ] message 'one' was received by node 17 from node 45
[ 2942 ] node '17' started computation
[ 2942 ] message 'one' was sent from node 17 to node 54
[ 2943 ] node '17' finnished computation
[ 3501 ] validator repported: [CORRECT STATE] Chef hasn't been elected yet.
[ 3894 ] message 'one' was received by node 54 from node 17
[ 3894 ] node '54' started computation
[ 3894 ] node '54' changed its flag
Node '54' flags:
    chef = true
[ 3895 ] node '54' finnished computation
[ 5001 ] validator repported: [CORRECT TERMINATION] Chef successfuly elected (Node ID = 54).
[ 5001 ] simulation stopped.
9 messages have been sent (lost included).