Podľa prednášky implementujte riešenie problému fajčiarov. Pri modifikácii, v ktorej agent nečaká na signalizáciu alokovania zdrojov, vyriešte problém zvýhodňovania fajčiarov a v dokumentácii toto svoje riešenie vhodným spôsobom opíšte.
Podľa prednášky implementujte riešenie problému hodujúcich divochov.
Vypracujte program, ktorý rieši modifikovaný synchronizačný problém hodujúcich divochov (Dining Savages).
Divosi vždy ZAČÍNAJÚ večerať všetci spolu. Keď sa všetci zídu, začnú si postupne naberať z hrnca (a pripadne budiť kuchára). Porcie do hrnca vkladá kuchár, nie divoch!
Vhodne modelujte daný problém podľa nasledovných požiadaviek:
Pre overenie modelu použite výpisy podľa nasledovnej špecifikácie formátu:
"divoch %2d: prisiel som na veceru, uz nas je %2d"
"divoch %2d: uz sme vsetci, zaciname vecerat"
"divoch %2d: pocet zostavajucich porcii v hrnci je %2d"
"divoch %2d: budim kuchara"
"divoch %2d: beriem si porciu"
"divoch %2d: hodujem"
"kuchar: varim"
Ide o úlohu Hodujúcich divochov, ktorá je založená na myšlienke Producentov a konzumentov, rozšírená o sledovanie stavu „skladu“ (koľko porcií sa nachádza v hrnci).
Štandardné riešenie Hodujúcich divochov však treba rozšíriť ešte o bariéru, aby sa pred každým hodovaním najprv zišli všetci divosi, až potom môže začať každodenná večerná hostina.
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 |
def init(): mutex := Mutex() servings := 0 fullPot := Semaphore(0) emptyPot := Semaphore(0) barrier1 := SimpleBarrier() barrier2 := SimpleBarrier() for savage_id in [0, 1, 2, ..., N-1]: create_and_run_thread(savage, savage_id) create_and_run_thread(cook) def getServingFromPot(savage_id): print("divoch %2d: beriem si porciu", savage_id) servings := servings - 1 def savage(savage_id): while True: barrier1.wait("divoch %2d: prisiel som na veceru, uz nas je %2d", savage_id, print_each_thread = True) barrier2.wait("divoch %2d: uz sme vsetci, zaciname vecerat", savage_id, print_last_thread = True) mutex.lock() print("divoch %2d: pocet zostavajucich porcii v hrnci je %2d" % (savage_id, servings)) if servings == 0: print("divoch %2d: budim kuchara" % savage_id) emptyPot.signal() fullPot.wait() getServingFromPot(savage_id) mutex.unlock() # konkurentne vykonavany kod print("divoch %2d: hodujem" % savage_id) def putServingsInPot(): print("kuchar: varim") servings := M def cook(): while True: emptyPot.wait() putServingsInPot() fullPot.signal() |
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 |
"""Riesenie modifikovaneho problemu divochov.""" from fei.ppds import Semaphore, Mutex, Thread, print from random import randint from time import sleep """M a N su parametre modelu, nie synchronizacie ako takej. Preto ich nedavame do zdielaneho objektu. M - pocet porcii misionara, ktore sa zmestia do hrnca. N - pocet divochov v kmeni (kuchara nepocitame). """ M = 2 N = 3 class SimpleBarrier: """Vlastna implementacia bariery kvoli specialnym vypisom vo funkcii wait(). """ def __init__(self, N): self.N = N self.mutex = Mutex() self.cnt = 0 self.sem = Semaphore(0) def wait(self, print_str, savage_id, print_last_thread=False, print_each_thread=False): self.mutex.lock() self.cnt += 1 if print_each_thread: print(print_str % (savage_id, self.cnt)) if self.cnt == self.N: self.cnt = 0 if print_last_thread: print(print_str % (savage_id)) self.sem.signal(self.N) self.mutex.unlock() self.sem.wait() class Shared: """V tomto pripade musime pouzit zdielanu strukturu. Kedze Python struktury nema, pouzijeme triedu bez vlastnych metod. Preco musime pouzit strukturu? Lebo chceme zdielat hodnotu pocitadla servings, a to jednoduchsie v Pythone asi neurobime. Okrem toho je rozumne mat vsetky synchronizacne objekty spolu. Pri zmene nemusime upravovat API kazdej funkcie zvlast. """ def __init__(self): self.mutex = Mutex() self.servings = 0 self.full_pot = Semaphore(0) self.empty_pot = Semaphore(0) self.barrier1 = SimpleBarrier(N) self.barrier2 = SimpleBarrier(N) def get_serving_from_pot(savage_id, shared): "Pristupujeme ku zdielanej premennej. Funkcia je volana pri zamknutom mutexe, preto netreba riesit serializaciu v ramci samotnej funkcie. """ print("divoch %2d: beriem si porciu" % savage_id) shared.servings -= 1 def eat(savage_id): print("divoch %2d: hodujem" % savage_id) # Zjedenie porcie misionara nieco trva... sleep(0.2 + randint(0, 3) / 10) def savage(savage_id, shared): while True: """Pred kazdou hostinou sa divosi musia pockat. Kedze mame kod vlakna (divocha) v cykle, musime pouzit dve jednoduche bariery za sebou alebo jednu zlozenu, ale kvoli prehladnosti vypisov sme sa rozhodli pre toto riesenie. """ shared.barrier1.wait( "divoch %2d: prisiel som na veceru, uz nas je %2d", savage_id, print_each_thread=True) shared.barrier2.wait("divoch %2d: uz sme vsetci, zaciname vecerat", savage_id, print_last_thread=True) # Nasleduje klasicke riesenie problemu hodujucich divochov. shared.mutex.lock() print("divoch %2d: pocet zostavajucich porcii v hrnci je %2d" % (savage_id, shared.servings)) if shared.servings == 0: print("divoch %2d: budim kuchara" % savage_id) shared.empty_pot.signal() shared.full_pot.wait() get_serving_from_pot(savage_id, shared) shared.mutex.unlock() eat(savage_id) def put_servings_in_pot(M, shared): """M je pocet porcii, ktore vklada kuchar do hrnca. Hrniec je reprezentovany zdielanou premennou servings. Ta udrziava informaciu o tom, kolko porcii je v hrnci k dispozicii. """ print("kuchar: varim") # navarenie jedla tiez cosi trva... sleep(0.4 + randint(0, 2) / 10) shared.servings += M def cook(M, shared): """Na strane kuchara netreba robit ziadne modifikacie kodu. Riesenie je standardne podla prednasky. Navyse je iba argument M, ktorym explicitne hovorime, kolko porcii ktory kuchar vari. Kedze v nasom modeli mame iba jedneho kuchara, ten navari vsetky potrebne porcie a vlozi ich do hrnca. """ while True: shared.empty_pot.wait() put_servings_in_pot(M, shared) shared.full_pot.signal() def init_and_run(N, M): """Spustenie modelu""" threads = list() shared = Shared() for savage_id in range(0, N): threads.append(Thread(savage, savage_id, shared)) threads.append(Thread(cook, M, shared)) for t in threads: t.join() if __name__ == "__main__": init_and_run(N, M) |
Vypracujte program, ktorý rieši modifikovaný synchronizačný problém hodujúcich divochov (Dinning Savages).
V kmeni je viacero kuchárov. Keď divoch zistí, že je hrniec prázdny, zobudí VŠETKÝCH kuchárov, ktorí si môžu pri varení navzájom pomáhať a spoločne variť. PRÁVE JEDEN kuchár oznámi čakajúcemu divochovi, že je dovarené. Porcie do hrnca vkladá kuchár, nie divoch!
Vhodne modelujte daný problém podľa nasledovných požiadaviek:
Ponechávame ako domácu úlohu na precvičenie.