4. cvičenie – Večerajúci filozofi, Atómová elektráreň 🍽️

Večerajúci filozofi

Implementujte riešenie synchronizačného problému večerajúcich filozofov pomocou pravákov a ľavákov tak, aby boli splnené tieto podmienky:

Vidličku môže naraz držať iba jeden filozof,
nesmie nastať uviaznutie (t.j. žiaden filozof sa nenaje),
nesmie sa stať, aby sa niektorý z filozofov nenajedol,
a napokon riešenie musí umožňovať jesť naraz viacerým filozofom.

Snažte sa navrhnúť implementáciu tak, aby bola nezávislá od počtu filozofov. Ich počet určujte globálnou premennou N.

Znovu vhodne nastavte parametre modelu:

dobu premýšľania,
časovú dĺžku jedenia,
umiestnenie výpisov.

Urobte také riešenie, v ktorom sa náhodne budú voliť praváci a ľaváci. Taktiež pri implementácii dbajte na vhodnú znovupoužiteľnosť kódu (napríklad rovnaký kód pre pravákov aj ľavákov). Každý filozof nech je modelovaný práve jedným vláknom počas celej doby behu programu, pričom iba raz (pri jeho vytváraní) určite, či pôjde o ľaváka alebo praváka.

Atómová elektráreň #1

Zadanie

V atómovej elektrárni majú 11 čidiel:

dve čidlá prietoku chladiacej kvapaliny primárneho okruhu,
dve čidlá prietoku chladiacej kvapaliny sekundárneho okruhu,
dve čidlá teploty chladiacej kvapaliny primárneho okruhu,
dve čidlá teploty chladiacej kvapaliny sekundárneho okruhu,
tri čidlá hĺbky zasunutia kontrolných tyčí.

Tieto čidlá sa snažia v neustálom cykle aktualizovať namerané hodnoty v spoločnom údajovom úložisku. V tomto úložisku má každé jedno čidlo svoj priestor, kde aktualizuje tú hodnotu, ktorá mu prislúcha (zohľadnite pri synchronizácii). Aktualizácia údajov trvá každému čidlu 10 až 15 ms (model každého čidla založte iba na tejto vlastnosti).

Okrem čidiel majú v onej elektrárni aj dvoch operátorov, ktorí neustále hľadia každý na svoj monitor, kam sa namerané hodnoty čidiel premietajú. Avšak tieto údaje sa musia zo spoločného úložiska údajov čidiel nejako dostať do monitora. To sa deje tak, že každý monitor posiela žiadosť o aktualizované údaje v neustálom cykle každých 500 ms od dokončenia poslednej aktualizácie (alebo 500 ms od aktivácie monitora). Keď monitor požiada o aktualizáciu údajov, táto sa musí zaručene zrealizovať do 200 ms.

Monitory ovšem môžu začať pracovať (aktivujú sa) iba vtedy, keď aspoň jedno čidlo dodalo údaje do úložiska.

Úlohy

Urobte analýzu, o aké typy synchronizačných úloh (prípadne ich modifikácie či kombinácie) sa v tejto úlohe jedná.
Presne namapujte vami zvolené synchronizačné úlohy (primitívy) na jednotlivé časti zadania.
Napíšte pseudokód riešenia úlohy.
Napíšte program, ktorý bude vhodne modelovať túto synchronizačnú úlohu.
Výpisy:
1. pred simulovanie aktualizácie údajov umiestnite informáciu vo formáte: 'cidlo "%02d": pocet_zapisujucich_cidiel=%02d, trvanie_zapisu=%03d\n'
2. pri čítaní údajov umiestnite informáciu vo formáte: 'monit "%02d": pocet_citajucich_monitorov=%02d, trvanie_citania=%03d\n'

Riešenie

Ide o úlohu vzájomného vylúčenia kategórií procesov. Monitory tvoria jednu kategóriu, čidlá tvoria druhú kategóriu. Pre obe kategórie platí, že viacerí členovia kategórie môžu naraz pristupovať k údajom, a to z toho dôvodu, že:

monitory údaje iba čítajú, nijako ich nemodifikujú, takže viaceré naraz môžu sprístupňovať údaje toho istého čidla,
keďže má každé čidlo svoj priestor, kam ukladá údaje, nemôžu si čidlá navzájom svoje údaje prepisovať; to znamená, že aj čidlá môžu aktualizovať svoje údaje viaceré súčasne.

To, čo je tu zaujímavým problémom, je časovanie. Každé čidlo sa neustále pokúša aktualizovať svoje údaje, a táto aktualizácia trvá 10 až 15 ms. Monitor sa snaží získať aktuálne údaje každých 500 ms. To je rádový nepomer. Nielen počtom čidiel a monitorov, ale aj časov. Je zrejmé, že monitor nemá šancu získať prístup k údajom bez toho, aby sme to nejako synchronizačne zabezpečili. V takto nastavenom systéme prichádza k vyhladovaniu monitorov. Bez riešenia vyhladovenia monitorov nevieme zabezpečiť podmienku, aby sa údaje na monitore aktualizovali do 200 ms od jeho žiadosti o aktuálne údaje.

Ak aj zavedieme do riešenia turniket, ktorý budú riadiť (zamykať) monitory, musíme prešetriť otázku, či dokážeme splniť ohraničenie aktualizácie do 200 ms od žiadosti o údaje. Ak jednému čidlu trvá aktualizácia max. 15 ms, a čidiel máme 11, tak v najhoršom prípade (sériové radenie) musíme počítať s časom 15 x 11, čo je 165 ms (a to je menej než 200 ms, ktoré na to máme). Takže všetko je v poriadku. Musíme si však uvedomiť, že „sériové“ radenie v podstate nie je možné…

V zadanej úlohe nemáme špecifikované, aby sme uvažovali nejaké oneskorenie spôsobené synchronizačnými prvkami (napríklad prechod turniketom). Preto môžeme do modelu zaviesť zjednodušenie, že prechod turniketom je v nulovom čase. To znamená, že ak je turniket zatvorený, a počas zatvorenia sa na ňom vytvorí rad čakateľov na prechod, po uvoľnení každý z nich prejde v nulovom čase, čo v súčte znamená tiež nulu. Toto je nesmierne dôležité pre náš model, pretože pri takomto pohľade na úlohu zistíme, že monitor môže čakať na získanie prístupu k údajom v úložisku maximálne 15 ms. Prečo?

Nech máme všetkých 11 čidiel za turniketom, práve vo chvíli, keď chcú začať každé z nich zápis.
Nech práve v tomto momente chce pristúpiť k údajom monitor, a uzamkne turniket.
Koľko bude trvať čidlám zápis? Zápis bude trvať toľko, koľko trvá najdlhšie zápis niektorému z čidiel, pretože pristupujú k úložisku súčasne. Nakoľko potrebujeme mať istotu ohľadom časovania, zoberme ten najhorší prípad, a to je 15 ms.
Ak niektoré čidlo potrebuje na zápis menej než 15 ms, zastaví sa na turnikete, pretože ten je zamknutý, a zámok drží monitor.
Z uvedeného teda vyplýva, že monitor získa prístup k údajom v úložisku do 15 ms od „podania“ žiadosti (t.j. od uzamknutia turniketu). (Pozor! Zadanie nešpecifikuje časové oneskorenie spôsobené čítaním údajov monitorom! Preto v našom modeli uvažujeme, že prečítanie údajov, ich prenos a zobrazovanie na monitorovacom zariadení sa taktiež deje v nulovom čase.)

Táto úvaha je síce pekná, ale zatiaľ sme neuvažovali druhý monitor… Tu sa nám veci trošku komplikujú… Vieme aj v prípade dvoch monitorov tvrdiť, že ľubovoľný z monitorov dostane prístup k úložisku údajov do 15 ms od podania žiadosti? No, práve v tom je vtip tejto úvahy, že to teda nevieme zabezpečiť! Prečo?

Nech máme všetky čidlá za turniketom, zapisujú alebo chcú zapisovať údaje.
Nech v tejto chvíli zamkne turniket monitor 1.
Nech hneď vzápätí po zamknutí turniketu nejaké čidlo XY ukončí zápis a začne čakať na zamknutom turnikete.
Nech hneď za ním začne na turnikete čakať monitor 2, ktorému práve vypršala 500 ms pauza od poslednej aktualizácie údajov.
Z predošlej úvahy vieme, že monitor 1 bude čakať maximálne 15 ms na získanie prístupu k údajom.
Po ňom získa prístup k turniketu čidlo XY, ktorému bude trvať zápis maximálne 15 ms. Aj keby bolo pred monitorom 2 radených na turnikete viac čidiel, zápis bude znovu (z dôvodov uvedených v predošlej úvahe) maximálne tých 15 ms.
Takže monitor 2 bude čakať na prístup k údajom v úložisku 15 ms, ktoré čaká monitor 1, plus ďalších 15 ms, ktoré čaká, pretože do úložiska môžu zapisovať nejaké čidlá. Spolu to činí 30 ms.
Z uvedeného vyplýva, že ak máme v systéme 2 monitory, na prístup k údajom v úložisku bude ľubovoľný z nich po podaní žiadosti o prístup do úložiska čakať maximálne 30 ms.

Niekto by teraz s veľkou pompou a slávou vyhlásil, že analogickou úvahou dospejeme k tomu, že ak máme v systéme M monitorov, maximálna doba čakania na prístup k údajom môže byť pre ľubovoľný z nich M*15 ms. To, žiaľ, však nie je až tak celkom úplne (hm, ba vôbec nie) pravda. Treba si totiž uvedomiť, čo spôsobuje čakanie monitora: je to prítomnosť čidla/čidiel pred monitorom v čakacej fronte na turnikete. Ak máme v systéme iba 1 čidlo, ľubovoľný monitor môže čakať maximálne 15 ms bez ohľadu, koľko monitorov v systéme máme. Prečo? Lebo ak monitor čaká na čidlo, tak to je práve to jediné, ktoré vykonáva zápis. Ak má systém 2 čidlá, jedno môže zapisovať, a druhé sa môže radiť do fronty. Máme v podstate situáciu opísanú v predošlej úvahe. Ak bude mať systém 3 čidlá, v závislosti od počtu monitorov sa bude čakať maximálne buď 15 ms (1 monitor v systéme), 30 ms (2 monitory v systéme), alebo 45 ms (3 monitory v systéme). Preto pre našu úlohu platí, že s rastúcim počtom M monitorov v systéme a konštantným počtom čidiel (11) bude maximálny čas čakania rovný výrazu min(M, 11) * 15 ms. Ak by sme hľadali závislosť aj od meniaceho sa počtu čidiel C, potom by vzťah mohol vyzerať nasledovne: min(M, C) * 15 ms.

Záver: Ak na riešenie tejto úlohy použijeme vzájomné vylúčenie kategórií s turniketom, ktorý zamykajú monitory, tak vieme túto úlohu jednoducho a efektívne vyriešiť.

Ostáva nám ešte doriešiť inicializačnú fázu elektrárne, v ktorej monitor nemôže pracovať, pokým nie je k dispozícii aspoň jeden platný údaj z ľubovoľného čidla. Na to použijeme synchronizačný vzor signalizácie:

Každý monitor na začiatku bude čakať na udalosť dodania údajov do úložiska,
každé čidlo po aktualizácii údajov v úložisku bude signalizovať dodanie údajov do úložiska.

V nasledovnej časti sa nachádzajú pseudokódy pre riešenie tejto úlohy. Je zrejmé, že za účelom výpisov podľa zadania sme zmenili špecifikáciu ADT Lightswitch tak, aby nám funkcia lock() vrátila počet vlákien „v miestnosti“ platný v čase volania tejto funkcie.

def init():
    accessData = Semaphore(1)
    turniket = Semaphore(1)
    ls_monitor = Lightswitch()
    ls_cidlo = Lightswitch()
    validData = Event()

    for monitor_id in &lt;0,1&gt;:
        create_and_run_thread(monitor, monitor_id)
    for cidlo_id in &lt;0,10&gt;:
        create_and_run_thread(cidlo, cidlo_id)

def monitor(monitor_id):
    // monitor nemôže pracovať, kým nie je aspoň 1 platný údaj v úložisku
    validData.wait()

    while True:
        // monitor má prestávku 500 ms od zapnutia alebo poslednej aktualizácie
        sleep(500 ms)

        // zablokujeme turniket, aby sme vyhodili čidlá z KO
        turniket.wait()
            // získame prístup k úložisku
            pocet_citajucich_monitorov = ls_monitor(accessData).lock()
        turniket.signal()

        // prístup k údajom simulovaný nasledovným výpisom
        print('monit "%02d": pocet_citajucich_monitorov=%02d\n')
        // aktualizovali sme údaje, odchádzame z úložiska
        ls_monitor(accessData).unlock()

def cidlo(cidlo_id):
    while True:
        // čidlá prechádzajú cez turniket, pokým ho nezamkne monitor
        turniket.wait()
        turniket.signal()

        // získame prístup k úložisku
        pocet_zapisujucich_cidiel = ls_cidlo(accessData).lock()
            // prístup k údajom simulovaný čakaním v intervale 10 až 15 ms
            // podľa špecifikácie zadania informujeme o čidle a zápise, ktorý ide vykonať
            trvanie_zapisu = rand(10 az 15 ms)
            print('cidlo "%02d":  pocet_zapisujucich_cidiel=%02d, trvanie_zapisu=%03d\n')
            sleep(trvanie_zapisu)
            // po zapísaní údajov signalizujeme, že údaj je platný
            validData.signal()
        // a odchádzame z úložiska preč
        ls_cidlo(accessData).unlock()

				
					
				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

						def init():
    accessData = Semaphore(1)
    turniket = Semaphore(1)
    ls_monitor = Lightswitch()
    ls_cidlo = Lightswitch()
    validData = Event()
 
    for monitor_id in &lt;0,1&gt;:
        create_and_run_thread(monitor, monitor_id)
    for cidlo_id in &lt;0,10&gt;:
        create_and_run_thread(cidlo, cidlo_id)
 
def monitor(monitor_id):
    // monitor nemôže pracovať, kým nie je aspoň 1 platný údaj v úložisku
    validData.wait()
 
    while True:
        // monitor má prestávku 500 ms od zapnutia alebo poslednej aktualizácie
        sleep(500 ms)
 
        // zablokujeme turniket, aby sme vyhodili čidlá z KO
        turniket.wait()
            // získame prístup k úložisku
            pocet_citajucich_monitorov = ls_monitor(accessData).lock()
        turniket.signal()
 
        // prístup k údajom simulovaný nasledovným výpisom
        print('monit "%02d": pocet_citajucich_monitorov=%02d\n')
        // aktualizovali sme údaje, odchádzame z úložiska
        ls_monitor(accessData).unlock()
 
def cidlo(cidlo_id):
    while True:
        // čidlá prechádzajú cez turniket, pokým ho nezamkne monitor
        turniket.wait()
        turniket.signal()
 
        // získame prístup k úložisku
        pocet_zapisujucich_cidiel = ls_cidlo(accessData).lock()
            // prístup k údajom simulovaný čakaním v intervale 10 až 15 ms
            // podľa špecifikácie zadania informujeme o čidle a zápise, ktorý ide vykonať
            trvanie_zapisu = rand(10 az 15 ms)
            print('cidlo "%02d":  pocet_zapisujucich_cidiel=%02d, trvanie_zapisu=%03d\n')
            sleep(trvanie_zapisu)
            // po zapísaní údajov signalizujeme, že údaj je platný
            validData.signal()
        // a odchádzame z úložiska preč
        ls_cidlo(accessData).unlock()

					

			

Implementáciu riešenia láskavo ponechávame na čitateľa, nakoľko prepis tohto pseudokódu do jazyka Python je takmer priamočiary.

Atómová elektráreň #2

Zadanie

V atómovej elektrárni majú 3 čidlá:

jedno čidlo prietoku chladiacej kvapaliny primárneho okruhu (čidlo P)
jedno čidlo teploty chladiacej kvapaliny primárneho okruhu (čidlo T)
jedno čidlo hĺbky zasunutia kontrolnej tyče (čidlo H)

Tieto čidlá sa neustále snažia aktualizovať namerané hodnoty. Údaje ukladajú do spoločného údajového úložiska. Každé čidlo má v úložisku svoj vyhradený priestor, kam údaje ukladá (zohľadnite pri synchronizacii).

Čidlá vykonávajú aktualizáciu každých 50-60 ms. Samotná aktualizácia údajov trvá čidlu P a čidlu T 10-20 ms, avšak čidlu H to trvá 20-25 ms.

Okrem čidiel majú v onej elektrárni osem operátorov, ktorí neustále hľadia každý na svoj monitor, kam sa namerané hodnoty čidiel zobrazujú. Žiadosť o aktualizáciu údajov posiela monitor neustále a nepretržite v cykle. Jedna aktualizácia trvá 40-50 ms.

Monitory môžu začať pracovať iba vtedy, keď už všetky čidlá dodali do úložiska platné údaje.

Úlohy

Urobte analýzu, o aké typy synchronizačných úloh (prípadne ich modifikácie či kombinácie) sa v tejto úlohe jedná.
Presne namapujte vami zvolené synchronizačné úlohy (primitívy) na jednotlivé časti zadania.
Napíšte pseudokód riešenia úlohy.
Napíšte program, ktorý bude vhodne modelovať túto synchronizačnú úlohu.
Výpisy:
1. pred simulovanie aktualizácie údajov umiestnite informáciu vo formáte: 'cidlo "%02d": pocet_zapisujucich_cidiel=%02d, trvanie_zapisu=%03d\n'
2. pri čítaní údajov umiestnite informáciu vo formáte: 'monit "%02d": pocet_citajucich_monitorov=%02d, trvanie_citania=%03d\n'

Riešenie

Ponechávame ako domácu úlohu na precvičenie podľa vzoru predošlého riešenia, ktoré nie je možné aplikovať 1:1 na toto zadanie.