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:
self. Pomocou neho pristupujeme k atribútom objektu. Ak má nejaká metóda viac argumentov, self je vždy prvý. __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á). V module ppds sa nachádzajú (okrem iných) nasledovné triedy použiteľné pre synchronizáciu:
Mutex 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é:
|
1 2 3 4 5 6 |
from fei.ppds import Mutex m = Mutex() m.lock() m.unlock() |
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:
|
1 2 3 4 5 6 7 |
from fei.ppds import Event m = Event() m.signal() # alebo m.set() m.wait() m.clear() |
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().
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from random import randint from time import sleep from fei.ppds import Thread, Semaphore, Mutex """Vypisovat na monitor budeme pomocou funkcie 'print' importovanej z modulu 'ppds'. To kvoli tomu, aby neboli 'rozbite' vypisy. """ from fei.ppds import print class SimpleBarrier: def __init__(self, N): self.N = N # ... def wait(self): # ... pass def barrier_example(barrier, thread_id): """Predpokladajme, ze nas program vytvara a spusta 5 vlakien, ktore vykonavaju nasledovnu funkciu, ktorej argumentom je zdielany objekt jednoduchej bariery """ sleep(randint(1,10)/10) print("vlakno %d pred barierou" % thread_id) barrier.wait() print("vlakno %d po bariere" % thread_id) # priklad pouzitia ADT SimpleBarrier sb = SimpleBarrier(5) # doplnit kod, v ktorom sa vytvara a spusta 5 vlakien # ... |
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í:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
from time import sleep from random import randint from fei.ppds import Thread, Mutex, Semaphore """Vypisovat na monitor budeme pri zamknutom mutexe pomocou funkcie 'print' z modulu 'fei.ppds', aby sme nemali rozbite vypisy. """ from fei.ppds import print def rendezvous(thread_name): sleep(randint(1,10)/10) print('rendezvous: %s' % thread_name) def ko(thread_name): print('ko: %s' % thread_name) sleep(randint(1,10)/10) def barrier_example(thread_name): """Kazde vlakno vykonava kod funkcie 'barrier_example'. Doplnte synchronizaciu tak, aby sa vsetky vlakna pockali nielen pred vykonanim funkcie 'ko', ale aj *vzdy* pred zacatim vykonavania funkcie 'rendezvous'. """ while True: # ... rendezvous(thread_name) # ... ko(thread_name) # ... """Vytvorime vlakna, ktore chceme synchronizovat. Nezabudnime vytvorit aj zdielane synchronizacne objekty, a dat ich ako argumenty kazdemu vlaknu, ktore chceme pomocou nich synchronizovat. """ threads = list() for i in range(5): t = Thread(barrier_example, 'Thread %d' % i) threads.append(t) for t in threads: t.join() |
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.
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í.