PARA Filozofové, kuřáci a holič
Lenka Carr Motyčková 22. duben 2014
PDS Semafory
1
1. Večeřící filozofové (Dijkstra 1968) • Problém: N (typicky 5) flozofů sedí u kulatého stolu, přemýšlí nebo jedí pomocí dvou vidliček, kterých je mezi nimi celkem N, každý z nich používá jednu vidličku nalevo a jednu napravo od něj.
• Dva sousedící flozofové nemohou jíst zároveň a zároveň může jíst nejvýše ⎣N/2⎦ z nich
22. duben 2014
PDS Semafory
2
1. Večeřící filozofové (Dijkstra 1968)
22. duben 2014
PDS Semafory
3
1. Večeřící filozofové (Dining philosophers) • Vzájemné vyloučení při přístupu k vzájemně se překrývajícím množinám sdílených prostředků • i když spíše učebnicový příklad, je podobný skutečným problémům, kdy procesy vyžadují současný přístup k více prostředkům (the problem si not that philosofers hate computer scientists) • Požadavky na správné řešení: 1. 2. 3. 4. 5.
Filosof může jíst jenom pokud má dvě vidličky Dva flosofové nemohou zároveň držet stejnou vidličku Filosofové nesmí uváznout Absence vyhladovění (férové semafory) Maximální paralelismus 22. duben 2014
PDS Semafory
4
1. Večeřící filozofové: synchronizace Návrh: process Philosopher[i = 0 to 4] { while (true) { # filozof i p emýšlí # zvednutí vidli ek # filozof i jí # položení vidli ek } } • potřeba implementovat zvedání a pokládání vidliček, což je sdílený prostředek • každou vidličku můžeme reprezentovat semaforem • zvednutí vidličky: wait a položení vidličky signal 22. duben 2014
PDS Semafory
5
Večeřící filozofové • Semafory implementující atomické akce:
semaphore fork[5] wait(fork[i]); wait(fork[(i+1)mod n]); eat; signal(fork[i]); signal(fork[(i+1)mod n]); • PROBLÉM: všichni flozofové vezmou 1 vidličku a nemohou vzít druhou => deadlock, cyklické čekání • Řešení: Přístup ve stolu v kritické sekci (minimální paralelismus) • jeden z flozofů vezme vidličky v opačném pořadí • 22. duben 2014
PDS Semafory
6
Večeřící filozofové: řešení pomocí semaforů sem fork[5] = {1, 1, 1, 1, 1}; process Philosopher[i = 0 to 3] { while (true) { wait(fork[i]); wait(fork[i+1]); # get left fork then right eat; signal(fork[i]); signal(fork[i+1]); think; }} process Philosopher[4] { while (true) { wait(fork[0]); wait(fork[4]); # get right fork then left eat; signal(fork[0]); signal(fork[4]); think; jiná řešení: ? }} 22. duben 2014
PDS Semafory
7
Večeřící filozofové: řešení pomocí semaforů Ke stolu smí přistoupit jen N -1 flozofů
22. duben 2014
PDS Semafory
8
Večeřící filozofové: férové řešení pomocí semaforů
take_forks (i) { wait (mutex) state[i] = HUNGRY; test(i); signal(mutex); wait (s[i]); }
put_forks(i) { wait (mutex) state[i] = THINKING; test(LEFT); test(RIGHT); signal(mutex); }
test(i) { if (state(i) == HUNGRY & state[LEFT] != EATING & state[RIGHT] != EATING) then {state[i] = EATING; signal (s[i])} }
22. duben 2014
PDS Semafory
9
2. Spící holič Holičství: • 1 holič • N židlí pro čekající zákazníky • 1 křeslo holiče
22. duben 2014
PDS Semafory
10
2. Spící holič Problém: Napište program, který synchronizuje holiče a zákazníky tak, že každý čekající zákazník je někdy obsloužen za následujících podmínek:
•
Když nejsou žádní zákazníci, holič spí
•
Když přijde zákazník a holič spí, zákazník ho probudí a sedne si na křeslo
•
Když přijde zákazník a holič pracuje a je volná židle, zákazník se posadí a čeká
•
Když přijde zákazník a holič pracuje a není volná židle, zákazník opustí holičství
• Když holič dokončí obsluhu zákazníka, tento odejde a čekající zákazník si sedne na křeslo 22. duben 2014
PDS Semafory
11
2. Spící holič int waiting {0, …. , n} ,init 0
// zjišt ní hodnoty semaforu pro odchod zákazníka customers: obec. semaphore {0, …. , n}, init 0 // mutex: binary semaphore, init 1 //p ístup k waiting sync: binary semaphor, init 0 // holi musí ekat, jinak by obsluhoval dalšího barbers: binary semaphore, init 0 // zákazníka d ív, než by p edchozí odešel
22. duben 2014
PDS Semafory
12
2. Spící holič
BARBER
loop wait(customers) //buzení wait(mutex) waiting := waiting – 1 signal(barbers) //#volných holičů signal(mutex) // may swap cut customer's hair wait(sync) //uvolnění křesla end_loop 22. duben 2014
PDS Semafory
CUSTOMER
wait(mutex) if waiting < n then waiting:= waiting +1 //may swap signal(customers) //buzení signal(mutex) wait(barbers) //#volných holičů get haircut signal(sync) //uvolnění křesla else signal(mutex) fi 13
3. Problém kuřáků cigaret Problém: Napište program, který synchronizuje agenta a 3 kuřáky: každý kuřák si ubalí cigaretu a vykouří ji. • Pro ubalení cigarety jsou potřeba 3 věci: tabák, papírek a zápalka. Jeden (proces) kuřák má neomezenou zásobu • tabáku, • druhý papírků a • třetí zápalek Agent položí na stůl dvě libovolné suroviny. Kuřák, který má zbývající surovinu si vezme zbývající dvě ze stolu a ubalí si cigaretu a kouří. 22. duben 2014
PDS Semafory
14
3. Problém kuřáků cigaret Agent čeká, až kuřák dokouří a potom opakuje cyklus. Kód agenta je neměnnou částí zadání • používá 4 semafory; první tři určují, které potřeby jsou na stole • čtvrtý semafor udává, kdy má agent čekat a kdy má položit další potřeby na stůl Sdílené proměnné: • S: array [1..3] pole binárních semaforů, init 0 //odpovídají potřebám • Agent: binární semafor, init 1 Lokální proměnné agenta: • int i, j {1,2,3} 22. duben 2014
PDS Semafory
15
3. Problém kuřáků cigaret PROGRAM AGENTA Je částí zadání, signal znamená položení potřeb na stůl
loop set i and j to two different values [1,2,3] // randomly wait(agent) signal(S[i]) signal(S[j]) end_loop
22. duben 2014
PDS Semafory
16
3. Problém kuřáků cigaret • Pokus o řešení
SMOKER WITH PAPER
SMOKER WITH TOBACCO
SMOKER WITH MATCHES
loop wait(S[2]) wait(S[3]) „smoke“ signal(agent) end_loop
loop wait(S[3]) wait(S[1]) „smoke“ signal(agent) end_loop
loop wait(S[1]) wait(S[2]) „smoke“ signal(agent) end_loop
22. duben 2014
PDS Semafory
17
3. Problém kuřáků cigaret • Pokus o řešení – vede k deadlocku
SMOKER WITH PAPER
SMOKER WITH TOBACCO
SMOKER WITH MATCHES
loop wait(S[2]) wait(S[3]) „smoke“ signal(agent) end_loop
loop wait(S[3]) wait(S[1]) „smoke“ signal(agent) end_loop
loop wait(S[1]) wait(S[2]) „smoke“ signal(agent) end_loop
22. duben 2014
PDS Semafory
18
3. Problém kuřáků cigaret Helpers zjistí, které potřeby jsou dostupné a signalizují příslušného kuřáka • Další sdílené proměnné • R:array [1..6] binárních semaforů, init 0 • mutex: binární semafor, init 1 // přístup k proměnné t • t: integer, init 0 // určuje dostupné prostředky
HELPER WITH PAPER
HELPER WITH TOBACCO
HELPER WITH MATCHES
loop wait(S[1]) wait(mutex) t := t +1 if t ≠ 1 then signal(R[t]) signal(mutex) end_loop
loop wait(S[2]) wait(mutex) t := t +2 if t ≠ 2 then signal(R[t]) signal(mutex) end_loop
loop wait(S[3]) wait(mutex) t := t +4 if t ≠ 4 then signal(R[t]) signal(mutex) end_loop
22. duben 2014
PDS Semafory
19
Hodnoty t: matches
tabacco
0 0 0 1 1 1
0 1 1 0 0 1
22. duben 2014
paper 1 0 1 0 1 0
PDS Semafory
t =1 =2 =3 =4 =5 =6
R[1] R[2] R[3] R[4] R[5] R[6]
nepoužije se nepoužije se kouří vlastník zápalek nepoužije se kouří vlastník tabáku kouří vlastník papírků
20
3. Problém kuřáků cigaret Helpers zjistí, které potřeby jsou dostupné a signalizují příslušného kuřáka • Další sdílené proměnné • R:array [1..6] binárních semaforů, init 0 • mutex: binární semafor, init 1 • t: integer, init 0
HELPER WITH PAPER // 1 // t = 3, 5 loop wait(S[1]) wait(mutex) t := t +1 if t ≠ 1 then signal(R[t]) signal(mutex) end_loop
HELPER WITH TOBACCO // 2 // t = 3, 6 loop wait(S[2]) wait(mutex) t := t +2 if t ≠ 2 then signal(R[t]) signal(mutex) end_loop
22. duben 2014
PDS Semafory
HELPER WITH MATCHES // 4 // t = 5, 6 loop wait(S[3]) wait(mutex) t := t +4 if t ≠ 4 then signal(R[t]) signal(mutex) end_loop 21
3. Problém kuřáků cigaret Další sdílené proměnné • R:array [1..6] binárních semaforů, init 0 • mutex: binární semafor, init 1 • t: atomická proměnná, init 0
SMOKER WITH PAPER // 1
SMOKER WITH TOBACCO // 2
SMOKER WITH MATCHES // 4
loop wait(R[6]) t:= 0 „smoke“ signal(agent) end_loop
loop wait(R[5]) t:=0 „smoke“ signal(agent) end_loop
loop wait(R[3]) t:=0 „smoke“ signal(agent) end_loop
22. duben 2014
PDS Semafory
22
