5. cvičenie – Problém fajčiarov, problém divochov 🚬

Problém fajčiarov

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.

Problém divochov

Podľa prednášky implementujte riešenie problému hodujúcich divochov.

Modifikácia problému divochov #1

Zadanie

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:

zistite, o akú kombináciu synchronizačných problémov sa jedná,
napíšte pseudokód riešenia,
umiestnite vhodné výpisy na overenie funkčnosti modelu,
zvoľte vhodne charakteristiky, na ktorých sa model zakladá (počty vlákien, časovania aktivít, hodnoty ďalších premenných)

Pomôcky

Pre overenie modelu použite výpisy podľa nasledovnej špecifikácie formátu:

Keď divoch prichádza na večeru: "divoch %2d: prisiel som na veceru, uz nas je %2d"
Vypíše len jeden divoch, keď sa všetci zhromaždili: "divoch %2d: uz sme vsetci, zaciname vecerat"
Pred zisťovanie počtu porcii pôjde nasledovný výpis: "divoch %2d: pocet zostavajucich porcii v hrnci je %2d"
Divoch, ktorý zistí, že je hrniec prázdny, vypíše: "divoch %2d: budim kuchara"
Každý divoch, keď si berie porciu, dá o tom vedieť: "divoch %2d: beriem si porciu"
Každý divoch oznamuje, keď porciu konzumuje: "divoch %2d: hodujem"
Počas varenia kuchár vypíše: "kuchar: varim"

O aké synchronizačné úlohy sa jedná?

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.

Pseudokód riešenia

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

						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()

					

			

Riešenie

"""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)

				
					
				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)

					

			

Modifikácia problému divochov #2

Zadanie

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:

Zistite, o akú kombináciu synchronizačných problémov sa jedná,
napíšte pseudokód riešenia,
umiestnite vhodné výpisy na overenie funkčnosti modelu,
zvoľte vhodne charakteristiky, na ktorých sa model zakladá (počty vlákien, časovania aktivít, hodnoty ďalších premenných).

Riešenie

Ponechávame ako domácu úlohu na precvičenie.