2. cvičenie – turniket, bariéra ?


Nakoľko sa v dnešnom cvičení budeme venovať definíciám rôznych abstraktných údajových typov, bolo by viac než vhodné vedieť, ako sa pracuje s definíciou tried v jazyku Python. Preto si v úvode cvičenia prejdite časť 12 zo seriálu o jazyku Python: http://howto.py.cz/cap12.htm.

Najdôležitejšie veci špecifické pre jazyk Python:

  1. Každá metóda triedy musí mať aspoň jeden argument: označujeme ho názvom self. Pomocou neho pristupujeme k atribútom objektu. Ak má nejaká metóda viac argumentov, self je vždy prvý.
  2. Ak chceme inicializovať atribúty inštancie pri jej vytváraní, musíme definovať funkciu __init__(self, ...). Nejedná sa ale o konštruktor! V čase volania tejto funkcie už jestvuje v pamäti vytvorená inštancia triedy; táto metóda sa vyvoláva na konci celého procesu vytvárania objektu iba za účelom inicializácie jeho atribútov. Funkcia nemá návratovú hodnotu (presnejšie, iba hodnota None je povolená ako návratová).

Modul ppds

V module ppds sa nachádzajú (okrem iných) nasledovné triedy použiteľné pre synchronizáciu:

  1. Mutex
  2. Event

Mutex implementuje zámok (lock), v ponímaní prednášok semafor inicializovaný na hodnotu 1. Pre zvýšenie čitateľnosti kódu odporúčame na mieste vyžadujúcom mutex využívať túto triedu. Použitie je jednoduché:

Volanie Mutex() vytvorí inštanciu triedy Mutex. Objekt je inicializovaný, mutex je odomknutý. Nad objektom môžete využívať funkcie lock() a unlock(): prvá (z názvu) mutex uzamyká, druhá ho odomyká.

Trieda Event slúži na synchronizáciu pomocou udalostí. Použitie je tiež triviálne:

 

Konštruktor vytvorí objekt triedy Event. Pomocou metódy set() alebo signal() sa signalizuje udalosť; interne sa v objekte nastavuje príznak nastatia udalosti. Volanie wait() blokuje všetky vlákna, ktoré ho vyvolávajú, až pokým nenastane udalosť (teda pokým sa nezavolá metóda set() alebo signal()). Ak sa pomocou set() alebo signal() signalizuje udalosť, všetky vlákna, ktoré sú blokované vo funkcii wait(), budú odblokované. Taktiež platí, že každé volanie wait() po set() alebo signal() nie je blokujúce. To je zrejmé, pretože už udalosť nastala.

Objekt triedy Event je znovupoužiteľný. To znamená, že je možnosť „vynulovať“ nastavenie udalosti pomocou metódy clear(). Po jej zavolaní začnú byť znovu všetky volania wait() blokujúce, až pokým nebude nad týmto objektom (znovu) vyvolaná metóda set() alebo signal().

Úloha 1: ADT SimpleBarrier

Implementujte ADT SimpleBarrier podľa špecifikácie z prednášky. V nej sme na synchronizáciu použili ADT Semafor. Po úspešnej implementácii týmto spôsobom skúste na implementáciu turniketu použiť signalizáciu pomocou udalosti. Pre jednoduchosť prikladáme kostru/schému implementácie v jazyku Python:

Úloha 2: Znovupoužiteľná bariéra

Na ďalšie otestovanie ADT SimpleBarrier implementujte znovupoužiteľnú bariéru podľa špecifikácie z prednášky. Cieľom cvičenia nie je prepisovať kód z prednášky, ale zamyslieť sa nad úlohou a snažiť sa ju vyriešiť. V prípade nejasností je samozrejme potrebné a rozumné hľadať pomoc (napríklad v prednáške).

Skúste vychádzať zo pseudokódu, v ktorom sa nevyužíva vzor „nabitia“ turniketu ani dve jednoduché bariéry. Potom skúste implementovať pseudokód, v ktorom sa využíva „nabitie“ turniketu, a na záver využite v implementácií v predošlej úlohe vami implementovaný ADT SimpleBarrier.

Svoje riešenie overte experimentálne pomocou využitia nasledovných funkcií:

Ak vlákna vykonávajú nekonečný cyklus, nie je také triviálne program zastaviť. V prostredí konzoly OS Linux môžete zastavenie programu vyvolať pomocou stláčania kombinácie kláves Ctrl+C. V prípade spustenia programu z vývojového prostredia IDLE môžete program ukončiť reštartovaním interpretera pomocou navigácie Shell->Restart Shell alebo priamo pomocou kombinácie kláves Ctrl+F6.

Úloha 3: Fibonacciho postupnosť

Vytvorte N vlákien. Vlákno i nech reprezentuje uzol, v ktorom sa vypočítava prvok na pozícii i+2 Fibonacciho postupnosti (0, 1, 1, 2, 3, 5, 8, 13, 21…). Nech všetky vlákna zdieľajú spoločný zoznam, do ktorého sa postupne počas výpočtu ukladajú vypočítané prvky postupnosti. Prvé dva prvky 0 a 1 nech sú v tomto zozname pevne dané. Navrhnite pomocou doteraz prebraných synchronizačných nástrojov takú synchronizáciu, aby vlákno i+2 mohlo vykonávať výpočet jemu určeného Fibonacciho čísla až potom, ako svoje výsledky uložia do zoznamu vlákna, ktoré vypočítavajú predošlé čísla postupnosti (teda po skončení výpočtu vlákien i a i+1). Pri synchronizácii nezabúdajte na krajné prípady!

Na synchronizáciu použite najprv semafory. Potom vytvorte druhú verziu s udalosťami. Riešenie navrhnite tak, aby bolo možné upraviť implementáciu synchronizácie (t.j. vymeniť semafory za udalosti a naopak) bez zásahu do aplikačnej logiky programu!!!

Poznámka k zadaniu: výpočtové vlákna je podľa zadania (prvá veta) potrebné vytvoriť hneď na začiatku, ešte pred spustením výpočtu prvkov postupnosti!

Otázky na zamyslenie (odpovede očakávam v dokumentácii v rámci repozitára):
1) Aký je najmenší počet synchronizačných objektov (semafory, mutexy, udalosti) potrebných na riešenie tejto úlohy?
2) Ktoré z prebratých synchronizačných vzorov (vzájomné vylúčenie, signalizácia, rendezvous, bariéra) sa dajú (rozumne) využiť pri riešení tejto úlohy? Konkrétne popíšte, ako sa ten-ktorý synchronizačný vzor využíva vo vašom riešení.