3. cvičenie – Fibonacci, Vypínač, P-K, Č-Z ?

Fibonacci

Znovu sa pozrite na svoje riešenie Fibonacciho postupnosti z minulého cvičenia. V tomto cvičení minimalizujte počet použitých synchronizačných objektov. T.j., nech tento počet nie je závislý od počtu synchronizovaných vlákien. Použite napríklad myšlienky z prednášky:

skúste navrhnúť riešenie pomocou udalosti,
skúste sa zamyslieť, nakoľko a či je riešenie z prednášky správne; či nie je potrebné urobiť kombináciu udalosti s bariérou.

Odhaľte (prípadne opravte a konzultujte s cvičiacim!) návrhové chyby z prednášky. Implementujte svoje riešenie. Navrhnite a realizujte overenie správnosti svojho riešenia.

Vypínač

Implementujte ADT Lightswitch. ADT Lightswitch nech poskytuje 2 metódy: lock a unlock podľa nasledovnej špecifikácie:

lock(semaphore)
unlock(semaphore)

Interný stav ADT Lightswitch je daný počítadlom counter a mutexom mutex, ktorý chráni integritu počítadla.

Správanie ADT Lightswitch:

Ak vlákno zavolá metódu lock, a toto vlákno je prvým, ktoré sa pokúša „dostať do miestnosti“, nech vyvolá nad semaforom, ktorý je argumentom funkcie lock, operáciu wait().
Ak vlákno zavolá metódu unlock, a toto vlákno je posledným, ktoré sa pokúša „dostať z miestnosti“, nech vyvolá nad semaforom, ktorý je argumentom funkcie unlock, operáciu signal().

Na jednoduchom príklade si overte funkčnosť implementácie. Tento ADT správne využite v niektorej z nasledovných úloh.

Producent-Konzument

Implementujte riešenie problému Konzument-Producent. Experimentujte s rôznymi nastaveniami systému:

čas produkcie výrobku,
čas spracovania výrobku,
počet konzumentov,
počet producentov,
veľkosť úložiska (skladu).

Skúste experimentálne zistiť, aké parametre sú optimálne pre váš systém. Kritériom optimality nech sú:

Počet vyrobených výrobkov za jednotku času (v akom vzťahu sú čas produkcie výrobku, veľkosť úložiska, počet producentov a počet konzumentov?),
počet spracovaných výrobkov za jednotku času (v akom vzťahu sú čas spracovania výrobku, veľkosť úložiska, počet producentov a počet konzumentov?).

V prípade experimentov priemerujte hodnoty 10 opakovaní experimentu pri rovnakých nastaveniach systému; grafy vykresľujte aspoň pre 100 rôznych nastavení modelovaného systému.

Čitatelia-Zapisovatelia

Podobne ako v prípade problematiky Producentov-Konzumentov, aj tu experimentujte s rôznymi nastaveniami systému. Implementujte dve verzie riešenia tohto problému:

bez riešenia vyhladovenia zapisovateľov,
s riešením problému vyhladovenia zapisovateľov (tu si úmyselne vyskúšajte aj „zlú“ implementáciu podľa prednášky – viď. koniec prednášky).

Experimentujte s nasledovnými parametrami systému, a hľadajte medzi nimi závislosti:

počet čitateľov,
počet zapisovateľov,
doba čítania,
doba zápisu.
Pre aký počet čitateľov s danou priemernou dobou čítania sa prejavuje problém vyhladovenia?
Má počet zapisovateľov vplyv na schopnosť čitateľov dostať sa k údajom a prečítať ich?
Je možné, aby sa prejavilo vyhladovenie aj u čitateľov?
Ak doplníme implementáciu o turniket, aby neprišlo k vyhladoveniu zapisovateľov, vieme rozhodnúť, ktorý z kódov zo záveru prednášky je lepší?
Pre daný počet čitateľov, priemernú dobu čítania, priemernú dobu zápisu vieme určit optimálny počet zapisovateľov?
Ak máme danú priemernú dobu zápisu a priemernú dobu čítania, vieme vykresliť graf závislosti medzi počtom zapisovateľov a optimálnym počtom čitateľov (aby sme mohli nasadiť čo najviac čitateľov bez toho, aby prichádzalo k vyhladoveniu zapisovateľov). Vieme urobiť experiment, v ktorom sa bude meniť aj priemerná doba zápisu (mali by sme dostať trojrozmerný graf)?

Podobne ako pri probléme producent-konzument, aj pri týchto experimentoch opakujte merania aspoň 10x pre rovnaké nastavenie systému, a výsledky priemerujte; grafy vykresľujte aspoň pre 100 rôznych nastavení modelovaného systému.

Pri písaní kódu dbajte na prehľadnosť, samočitateľnosť, modularitu a znovupoužiteľnosť kódu. Dodržiavajte štandard PEP8. Vhodne využívajte možnosť komentovania kódu.

Do experimentov vhodným spôsobom vnášajte náhodnosť. Napr. kód zapisovateľa by mohol mať nasledovnú štruktúru:

from time import sleep
from random import randint

def writer_thread(thread_id, shared):
    while True:
        # pred kazdym pokusom o zapis pocka v intervale <0.0; 1> sekundy
        sleep(randint(0, 10)/10)

        shared.roomEmpty.wait()
        # simulujeme dlzku zapisu v intervale <0.3; 0.7> sekundy
        sleep(0.3 + randint(0, 4)/10)
        shared.room_empty.signal()

				
					
				1
2
3
4
5
6
7
8
9
10
11
12

						from time import sleep
from random import randint
 
def writer_thread(thread_id, shared):
    while True:
        # pred kazdym pokusom o zapis pocka v intervale <0.0; 1> sekundy
        sleep(randint(0, 10)/10)
 
        shared.roomEmpty.wait()
        # simulujeme dlzku zapisu v intervale <0.3; 0.7> sekundy
        sleep(0.3 + randint(0, 4)/10)
        shared.room_empty.signal()

					

			

Pre zopakovanie uvádzame aj kód vytvorenia vlákien.

from fei.ppds import Thread, Semaphore, print

class Shared():
    def __init__(self):
        self.room_empty = Semaphore(1)

"""
Vytvorime vlakna, ktore chceme synchronizovat.
Nezabudnime vytvorit aj zdielane synchronizacne objekty,
a dat ich ako argumenty kazdemu vlaknu, ktore chceme pomocou nich
synchronizovat.
"""

shared = Shared()
threads = []

for i in range(10):
    t = Thread(writer_thread, "Writer %d" % i, shared)
    threads.append(t)

for t in threads:
    t.join()

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

						from fei.ppds import Thread, Semaphore, print
 
class Shared():
    def __init__(self):
        self.room_empty = Semaphore(1)
 
"""
Vytvorime vlakna, ktore chceme synchronizovat.
Nezabudnime vytvorit aj zdielane synchronizacne objekty,
a dat ich ako argumenty kazdemu vlaknu, ktore chceme pomocou nich
synchronizovat.
"""
 
shared = Shared()
threads = []
 
for i in range(10):
    t = Thread(writer_thread, "Writer %d" % i, shared)
    threads.append(t)
 
for t in threads:
    t.join()

					

			