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.

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 nasledovné výpisy:

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"

Štandardné riešenie treba rozšíriť o bariéru, aby sa pred každým hodovaním najprv zišli všetci divosi, až potom môže začať 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,N>:
        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 -= 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()

        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

						def init():
    mutex = Mutex()
    servings = 0
    fullPot = Semaphore(0)
    emptyPot = Semaphore(0)
 
    barrier1 = SimpleBarrier()
    barrier2 = SimpleBarrier()
 
    for savage_id in <0,N>:
        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 -= 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()
 
        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 ppds import Semaphore, Mutex, Thread, print
from random import randint
from time import sleep

# M a N su parametre modelu, nie synchronizaAcie 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()


# 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.
class Shared:
    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)


# Pristupujeme ku zdielanej premennej.
# Preco nie je vo funkcii zamknutie mutexu?!
def get_serving_from_pot(savage_id, shared):
    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()


# Spustenie modelu.


def init_and_run(N, M):
    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

						"""Riesenie modifikovaneho problemu divochov."""
 
from ppds import Semaphore, Mutex, Thread, print
from random import randint
from time import sleep
 
# M a N su parametre modelu, nie synchronizaAcie 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()
 
 
# 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.
class Shared:
    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)
 
 
# Pristupujeme ku zdielanej premennej.
# Preco nie je vo funkcii zamknutie mutexu?!
def get_serving_from_pot(savage_id, shared):
    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()
 
 
# Spustenie modelu.
 
 
def init_and_run(N, M):
    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í 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 úlohu na precvičenie.