Zdrojové súbory na cvičenie, ktoré vidíte vo výpisoch nižšie, si môžete stiahnuť spoločne ako archív.
Podľa pseudokódu uvedeného v prednáške implementujte ADT Lightswitch. ADT Lightswitch nech poskytuje dve metódy: enter() a leave() podľa nasledovnej špecifikácie:
enter(semaphore) leave(semaphore) Interný stav ADT Lightswitch je daný počítadlom counter a mutexom mutex, ktorý chráni integritu počítadla.
Správanie ADT Lightswitch:
enter(), a toto vlákno je prvým, ktoré sa pokúša „dostať do miestnosti“, nech vyvolá nad semaforom, ktorý je argumentom metódy enter(), operáciu wait(). leave, a toto vlákno je posledným, ktoré sa pokúša „dostať z miestnosti“, nech vyvolá nad semaforom, ktorý je argumentom metódy leave(), operáciu signal(). Na jednoduchom príklade nižšie overte funkčnosť svojej implementácie. Sledujte výpisy. Pokiaľ vojde do miestnosti niektoré vlákno typu A, žiadne iné vlákno (ani typu A) nesmie do miestnosti vojsť, pokým vlákno z miestnosti nevyjde von. Ak vojde do miestnosti vlákno typu B, žiadne vlákno typu A nesmie do miestnosti vojsť. Iné vlákna typu B však do miestnosti môžu ľubovoľne vchádzať. Až keď vyjde z miestnosti posledné vlákno typu B, môže do miestnosti vstúpiť vlákno typu A (alebo aj vlákno typu B).
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
from time import sleep from random import randint from fei.ppds import Thread, Mutex, Semaphore, print class Lightswitch: """ Nalistujte prednasku a podla pseudokodu implementujte ADT LS. """ def __init__(self): # TODO: inicializacia pass def enter(self, sem): # TODO: prve vlakno caka na semafor pass def leave(self, sem): # TODO: posledne vlakno uvolnuje semafor pass def do_A(thread_id): while True: # pred kazdym pokusom o vstup do miestnosti pocka v intervale <0.0; 1> sekundy sleep(randint(0, 10) / 10) room.wait() print(f"{thread_id}: entered the room") # simulujeme dlzku zotrvania v miestnosti v intervale <0.3; 0.7> sekundy sleep(0.3 + randint(0, 4) / 10) print(f"{thread_id}: leaving the room") room.signal() def do_B(thread_id): while True: # pred kazdym pokusom o vstup do miestnosti pocka v intervale <0.0; 1> sekundy sleep(randint(0, 10) / 10) lsB.enter(room) print(f"{thread_id}: entered the room") # simulujeme dlzku zotrvania v miestnosti v intervale <0.1; 0.4> sekundy sleep(0.1 + randint(0, 3) / 10) print(f"{thread_id}: leaving the room") lsB.leave(room) """ Vytvorime vlakna, ktore chceme synchronizovat. Nezabudnime vytvorit aj zdielane synchronizacne objekty. Tie su globalne, dostupne vo funkciach do_A() aj do_B(). """ if __name__ == "__main__": room = Semaphore() lsB = Lightswitch() tA = [Thread(do_A, f"A-{i}") for i in range(2)] tB = [Thread(do_B, f"B-{i}") for i in range(5)] [t.join() for t in tA + tB] |
Upravte funkcionalitu vlákien typu A tak, aby mohli byť v miestnosti súčasne viaceré vlákna typu A. Zároveň musíte zachovať invariant, že pokiaľ je v miestnosti vlákno typu A, nesmie s ním byť v miestnosti vlákno typu B a naopak.
Sledujte výstup simulácie. Skontrolujte, či sa simulácia správa podľa vyššie uvedeného očakávania.
Riešenie uložte ako samostatný súbor s identifikátorom v mene súboru „2a“.
Zvýšte počet vlákien typu B na hodnotu 20 v počet vlákien typu A na hodnotu 3. Spustite simuláciu. Z pozorovania výstupu vyvoďte záver.
V tejto časti chceme dosiahnuť odstránenie vyhladovenia vlákien. Do riešenia doplňte mechanizmus, ktorý zabezpečí, že:
Pozorujte výstup. Ako často sa stáva, že sa v miestnosti budú nachádzať všetky tri vlákna typu A?
Riešenie uložte ako samostatný súbor s identifikátorom v mene súboru „2b“.
Nakoniec zvýhodnite vlákna typu A, aby mali prednosť pri vstupe do miestnosti pred vláknami typu B. To znamená, že ak bude chcieť vlákno typu A vstúpiť do miestnosti, žiadnemu vláknu typu B nebude umožnené do miestnosti vojsť, aj keď sa v miestnosti nachádza nejaké vlákno typu B. Zároveň musíte zachovať invariant, že pokiaľ sa v miestnosti nachádza vlákno typu A, môže do miestnosti vstúpiť iné vlákno typu A, ale nesmie sa v miestnosti nachádzať žiadne vlákno typu B.
Pozorujte výstup simulácie. Mali by ste vidieť, že vláknam typu A sa častejšie darí zotrvať v miestnosti spoločne. To znamená, že pokiaľ sa v miestnosti nachádza nejaké vlákno typu A, ostatným vláknam typu A, ktoré chcú do miestnosti vstúpiť, sa darí „obiehať“ vlákna typu B čakajúce na vstup do miestnosti.
Riešenie uložte ako samostatný súbor s identifikátorom v mene súboru „2c“.
Model synchronizačného problému Producent – Konzument (PK) v sebe zahŕňa niekoľko parametrov, ktoré môžu mať zásadný vplyv na efektivitu modelovaného systému (meranú priepustnosťou, čiže počtom výrobkov vyrobených/spracovaných za jednotku času). Okrem priepustnosti systému je možné zvažovať aj iné kritériá optimality, napríklad latenciu (dobu, ktorú strávi výrobok v systéme, pokým nie je prevzatý na spracovanie). Parameter latencie je obzvlášť zaujímavý v modeloch, ktoré požadujú, aby sa výrobok dostal čo najskôr na spracovanie (odbyt). Príkladom môžu byť typy potravín s krátkou životnosťou (surové mäso) či technologické postupy, kde nasledujúci stupeň spracovania výrobku musí prebehnúť do presne limitovaného času, inak ďalšie spracovanie nebude možné. Zaujímavou optimalizačnou úlohou môže byť zadanie, v ktorom sa požaduje latencia v nejakom špecifikovanom intervale, ktorý nezačína od nuly. Napríklad v hrnčiarstve je to tak, že po vymodelovaní tvaru nádoby nie je možné okamžite nalepiť ucho nádoby. Je potrebné istý čas počkať, až potom sa dá uško prilepiť. Zároveň však platí, že nie je možné čakať príliš dlho.
V nami modelovanom probléme PK nebudeme venovať pozornosť latencii, iba efektivite v závislosti od počtu producentov/konzumentov a veľkosti úložiska (skladu). Čas produkcie a čas spracovania výrobku konzumentov budú mať rovnaké parametre. Rôznu rýchlosť činnosti môžeme modelovať rôznym počtom producentov či konzumentov. Napríklad dvojnásobnú rýchlosť konzumentov vieme modelovať ich dvojnásobným počtom voči počtu producentov.
Nech Np označuje počet producentov, Nc počet konzumentov. Nech Tp označuje čas výroby jedného kusu výrobku a Tc čas spracovania jedného výrobku. Potom Np/Tp je počet výrobkov vyprodukovaných za jednotku času a Nc/Tc je počet výrobkov spracovaných za jednotku času. Celková maximálna teoretická produkcia (efektivita) systému za jednotku času je potom daná ako minimum z týchto dvoch hodnôt: min(Np / Tp, Nc / Tc).
Ak platí, že Np / Tp = Nc / Tc, hovoríme, že systém je vyvážený. V opačnom prípade je systém nevyvážený.
Veľkosť úložiska neovplyvňuje dlhodobý priemer produkcie v ustálenom stave. Úlohou úložiska je eliminovať výkyvy v systéme, ak sú časy Tp a Tc stochastické (náhodné). V prípade, že časy Tp a Tc sú konštantné, úložisko nemá žiaden vplyv na produkciu systému.
V tejto časti cvičenia použite nižšie pripravený programový kód pre simuláciu synchronizačného problému PK.
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 |
import time import random import numpy as np import matplotlib.pyplot as plt from fei.ppds import Semaphore, Mutex, Thread class Simulation: """Model simulacie.""" def __init__( self, p_count: int, c_count: int, buf_size: int, p_time: float, c_time: float, duration: float, stochastic: bool = False, ): self.p_count = p_count # pocet producentov self.c_count = c_count # pocet konzumentov self.buf_size = buf_size # velkost uloziska (skladu) self.p_time = p_time # trvanie vyroby self.c_time = c_time # trvanie spracovania self.duration = duration # trvanie simulacie # priznak, ci je model konstantny alebo stochasticky self.stochastic = stochastic # mutex chraniaci pocty vyrobenych/skonzumovanych vyrobkov self.mutex = Mutex() self.free = Semaphore(buf_size) # strazenie volnych miest v ulozisku self.items = Semaphore(0) # strazenie zaplnenych miest v ulozisku self.produced_count = 0 # pocet vyprodukovanych vyrobkov self.consumed_count = 0 # pocet spracovanych vyrobkov self.running = True # indikator, ci simulacia bezi def producer(self): while self.running: # Simuluj vyrobenie vyrobku. t = ( random.expovariate(1.0 / self.p_time) if self.stochastic else self.p_time ) time.sleep(t) # TODO: implementuj kod producenta: # 1) Pokym je ulozisko plne, cakaj. # 2) Pridaj vyrobok do uloziska (zvys pocet vyprodukovanych vyrobkov # `self.produced_count'). # 3) Signalizuj pridanie vyrobku do uloziska. def consumer(self): while self.running: # TODO: implementuj kod konzumenta: # 1) Pokym je ulozisko prazdne, cakaj. # 2) Zober vyrobok z uloziska (zvys pocet skonzumovanych vyrobkov # `self.consumed_count'). # 3) Signalizuj prevzanie vyrobku z uloziska. # Simuluj spracovanie vyrobku. t = ( random.expovariate(1.0 / self.c_time) if self.stochastic else self.c_time ) time.sleep(t) def run(self) -> float: # Vytvor vlakna. producers = [Thread(self.producer) for _ in range(self.p_count)] consumers = [Thread(self.consumer) for _ in range(self.c_count)] # Pockaj chvilku a ukonci simulaciu. time.sleep(self.duration) self.running = False # Uvolni cakajuce vlakna a ukonci simulaciu. for _ in range(self.buf_size + self.p_count + self.c_count): self.free.signal() self.items.signal() for t in producers + consumers: t.join(timeout=0.1) # Vrat hodnotu produkcie instancie modelu. return self.produced_count / self.duration def exp1_producers_vs_consumers(stochastic: bool = False) -> np.array: """Experiment 1: Pomer producentov a konzumentov. :param stochastic: Ak je True, cas prace producentov a konzumentov je stochasticky, v opacnom pripade konstantny. """ print( "Spustam experiment 1 (Pomer entit)... Bude to trvat cca 100 sekund." ) results = np.zeros((10, 10)) for p in range(1, 11): for c in range(1, 11): batch = [] for _ in range(10): # 10 opakovani sim = Simulation( p, c, buf_size=10, p_time=0.01, c_time=0.01, duration=0.1, stochastic=stochastic, ) batch.append(sim.run()) results[p - 1, c - 1] = np.mean(batch) return results def exp2_buffer_size( N: int, stochastic: bool = False ) -> tuple[range, list[np.float64]]: """Experiment 2: Vplyv velkosti uloziska (stochasticky model). :param N: pocet producentov a konzumentov :param stochastic: Ak je True, cas prace producentov a konzumentov je stochasticky, v opacnom pripade konstantny. """ print( "Spustam experiment 2 (Velkost uloziska)... Bude to trvat cca 100 sekund." ) buffer_sizes = range(1, 101) results = [] for size in buffer_sizes: batch = [] for _ in range(10): # 10 opakovani # Vyvazeny system NvN s nahodnymi casmi sim = Simulation( N, N, buf_size=size, p_time=0.01, c_time=0.01, duration=0.1, stochastic=stochastic, ) batch.append(sim.run()) results.append(np.mean(batch)) if size % 20 == 0: print(f" Spracovane velkosti buffera: {size}/100") return buffer_sizes, results def plot_all(): """Vykresli experimenty.""" res_exp1 = exp1_producers_vs_consumers(stochastic=True) N = 3 buf_sizes, res_exp2 = exp2_buffer_size(N, stochastic=True) fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6)) # Graf 1: Heatmapa im = ax1.imshow( res_exp1, extent=[1, 10, 1, 10], origin='lower', cmap='plasma' ) fig.colorbar(im, ax=ax1, label='Vyrobenych kusov / sekunda') ax1.set_xlabel('Pocet konzumentov') ax1.set_ylabel('Pocet producentov') ax1.set_title('Exp 1: Priepustnost podla poctov PK') # Graf 2: Ciarovy graf ax2.plot(buf_sizes, res_exp2, marker='.', linestyle='-', color='teal') ax2.set_xlabel('Velkost uloziska (kapacita buffera)') ax2.set_ylabel('Priemerna produkcia [ks/s]') ax2.set_title(f'Exp 2: Vplyv velkosti uloziska (Np = Nc = {N})') ax2.grid(True, alpha=0.4) plt.tight_layout() plt.show() if __name__ == "__main__": plot_all() |
Doplňte programový kód metód producer() a consumer(). Spustite program a analyzujte výstupné grafy.
V experimente 2 zmeňte stochastické správanie modelu na konštantné. Spustite program a porovnajte výstupný graf tohto experimentu s grafom stochastického experimentu. Pre lepšiu predstavu môžete meniť počty producentov/konzumentov, systém však ponechajte vyvážený. Aká je optimálna veľkosť úložiska pre vyvážený systém PK s daným počtom producentov/konzumentov? Vyvoďte poučenie.