Paralelizácia vybraných problémov

Milan Kubala
kubala36@uniba.sk

Vedúci projektu:

Tomáš Plachetka
plachetk@dcs.fmph.uniba.sk

Projekt:

Problém:

Prvý semester:

Druhý semester:

Reimplementovanie riešenia z prvého semestra. Dôraz sa kládol na efektivitu upraveného riešenia, prehľadnejší a zrozumiteľnejší kód. Všetky procesy majú jednotný návrh, čo umožnilo výrazne zredukovať počet stavov, do ktorých sa proces môže dostať.

Zdrojový kód

Excelovský súbor so stavmi a správami

----

Ukážky.

Náčrt fungovania programu:

Procesy si medzi sebou posielajú správy. Každá správa obsahuje hlavičku v tvare: (int sender_id)(int msg_id), za ktorou nasleduje zvyšok správy - všetky typy správ sú popísané v súbore procesy.ods - časť MESSAGE TYPES.

Procesy majú jednotný dizajn, každý pracuje na dvoch vláknach.
Prvé využíva len na prijímanie správ od ostatných procesov. Po prijatí správu uloží do fronty, ktorú majú vlákna spoločnú a čaká na ďalšie správy.
Druhé vlákno spí, až kým sa vo fronte niečo neobjaví (resp. kým ho nezobudí druhé vlákno, ktoré vložilo správu do fronty). Správu vyberie a [process.c line=1100] následne podľa hlavičky určí, ktorá funkcia sa má o ňu postarať.

Fungovanie procesov a popisy jednotlivých stavov sa tiež nachádzajú v súbore procesy.ods - časť PROTOCOL. Obsahuje tri sekcie: ukončenie programu, vyriešenie zrážky a vykreslenie.

Ukončenie programu:

Okrem spomenutých dvoch vlákien má hlavný proces ešte jedno dodatočné - to čaká na vstup od užívateľa [process.c line=234]. Keď zaznamená stlačenie klávesnice, informuje o tom ostatné svoje vlákna poslaním správy KEY_PRESSED sebe samému.

  1. Hlavný proces prestane s vykresľovaním a rozpošle ostatným správu NO_MORE_MSGS_NOTIF o tom, že užívateľ žiada ukončiť program. Zvyšok protokolu pre ukončenie je pre všetky procesy rovnaký:
  2. Ak už proces vyriešil všetko ohľadom posledných zrážok, je pripravený skončiť. Ostatné procesy informuje o tom, že už im nebude posielať ďalšie správy - NO_MORE_MSGS_NOTIF.
  3. Proces čaká od ostatných na správy NO_MORE_MSGS_NOTIF. Ak nejakú dostane, zaznačí si ID procesu a čaká ďalej.
  4. Ak už má takto poznačené všetky procesy, usúdi, že môže ukončiť svoju činnosť. Nastaví spoločnú premennú FINAL=1, čím dá druhému vláknu vedieť, že môže skončiť. Zároveň posiela správu samému sebe, čím druhé vlákno spiace na Waite prebudí.
  5. Vlákno, ktoré počúva, sa prebudí a uloží správu do fronty. Následne však zistí, že FINAL==1 a končí.
  6. Po prečítaní aj poslednej správy končí aj druhé vlákno.

Vyriešenie zrážky:

  1. V čase zrážky posiela hlavný proces ostatným správy (TRAIN_CRASHED_NOTIF, TRAIN_CLOSE_NOTIF, TRAIN_DIST_NOTIF) o tom, akú úlohu v zrážke zohrávajú.
  2. Každý vlak prijme správu a podľa toho si aktualizuje údaje. Niektoré potrebujú získať aktualizované údaje aj od svojich susedov. Na to slúžia správy (MSG_FOR_CRASHED, MSG_FOR_CLOSE).
  3. Vlaky si vymenia údaje a posielajú nové časy do zrážok hlavnému procesu (AFTER_CRASH_UPDATE).

Vykreslenie:

  1. Hlavný proces po zrážke pozbiera prichádzajúce údaje od vlakov. Priebežne si počíta čas najbližšej zrážky.
  2. Keď už má všetky, skontroluje, či do zrážky stihne vykresliť situáciu na koľajnici (či zostáva aspoň TIME_STEP času).
  3. Ak áno, požiada vlaky o ich výpočet ich pozícií v čase vykreslenia (NOW + TIME_STEP). Pozbiera údaje a čaká na spomínaný čas. Vykreslí. Vracia sa do bodu 2.
  4. Ak nie, čaká na čas zrážky a pokračuje v sekcii "Vyriešenie zrážky" bodom 1.