Problémem filozofa stolování je klasický problém synchronizace, který říká, že pět filozofů sedí kolem kruhového stolu a jejich úkolem je myslet a jíst alternativně. Uprostřed stolu je umístěna miska nudlí spolu s pěti hůlkami pro každého z filozofů. K jídlu potřebuje filozof pravou i levou hůlku. Filosof může jíst pouze tehdy, má-li k dispozici okamžitou levou i pravou hůlku filozofa. V případě, že nejsou k dispozici obě okamžité levé a pravé hůlky filozofa, filozof odloží hůlku (buď levou nebo pravou) a začne znovu přemýšlet.
Jídelní filozof demonstruje velkou třídu problémů s řízením souběžnosti, a proto se jedná o klasický synchronizační problém.
Pět filozofů sedících kolem stolu
Problém filozofů stravování - Pojďme pochopit problém Dining Philosophers pomocí níže uvedeného kódu, použili jsme obrázek 1 jako odkaz, abyste přesně pochopili problém. Pět filozofů je reprezentováno jako P0, P1, P2, P3 a P4 a pět hůlek C0, C1, C2, C3 a C4.
pole v řetězci
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Pojďme diskutovat o výše uvedeném kódu:
Předpokládejme, že Philosopher P0 chce jíst, vstoupí do funkce Philosopher() a provede se vzít_hůlku[i]; tím to drží C0 hůlka poté se provede vezmi hůlku[ (i+1) % 5]; tím to drží C1 hůlka ( protože i = 0, tedy (0 + 1) % 5 = 1)
Podobně předpokládejme, že nyní chce Philosopher P1 jíst, vstoupí do funkce Philosopher() a provede vzít_hůlku[i]; tím to drží C1 hůlka poté se provede vezmi hůlku[ (i+1) % 5]; tím to drží C2 hůlka ( protože i = 1, tedy (1 + 1) % 5 = 2)
Prakticky Chopstick C1 však není k dispozici, protože ji již převzal filozof P0, a proto výše uvedený kód generuje problémy a vytváří závodní podmínky.
armstrongovo číslo
Řešení problému filozofů stravování
K zobrazení hůlky používáme semafor a to skutečně funguje jako řešení problému filozofů stolování. Operace Wait a Signal budou použity pro řešení problému Dining Philosophers Problem, pro výběr hůlky lze provést operaci čekání a pro uvolnění signálu hůlky lze provést semafor.
Semafor: Semafor je celočíselná proměnná v S, ke které kromě inicializace přistupují pouze dvě standardní atomické operace - čekání a signál, jejichž definice jsou následující:
1. wait( S ) { while( S <= 0) ; s--; } 2. signal( s ) { s++; < pre> <p>From the above definitions of wait, it is clear that if the value of S <= 0 then it will enter into an infinite loop(because of the semicolon; after while loop). whereas job signal is to increment value s.< p> <p>The structure of the chopstick is an array of a semaphore which is represented as shown below -</p> <pre> semaphore C[5]; </pre> <p>Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.</p> <p>Let's modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like</p> <pre> void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } </pre> <p>In the above code, first wait operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks from its left and right. The eating function is performed after that.</p> <p>On completion of eating by philosopher i the, signal operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher i have eaten and put down both the left and right chopsticks. Finally, the philosopher starts thinking again.</p> <h3>Let's understand how the above code is giving a solution to the dining philosopher problem?</h3> <p>Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C0 chopstick</strong> and reduces semaphore C0 to 0 <strong>,</strong> after that it execute <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C1 chopstick</strong> ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0</p> <p>Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it will try to hold <strong>C1 chopstick</strong> but will not be able to do that <strong>,</strong> since the value of semaphore C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C2 chopstick</strong> and reduces semaphore C2 to 0, after that, it executes <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C3 chopstick</strong> ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.</p> <p>Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher <strong>P0 and P2, P1 and P3 & P2 and P4</strong> can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem)</p> <h3>The drawback of the above solution of the dining philosopher problem</h3> <p>From the above solution of the dining philosopher problem, we have proved that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat.</p> <p>To avoid deadlock, some of the solutions are as follows -</p> <ul> <li>Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.</li> <li>A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.</li> <li>Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks</li> <li>All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.</li> </ul> <p>The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows:</p> <ul> <li>The philosopher is instructed to think till the left fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to think till the right fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to eat when both forks are available.</li> <li>then, put the right fork down first</li> <li>then, put the left fork down next</li> <li>repeat from the beginning.</li> </ul> <hr></=></p></=> Zpočátku je každý prvek semaforu C0, C1, C2, C3 a C4 inicializován na 1, když jsou hůlky na stole a žádný z filozofů je nezvedá.
Upravme výše uvedený kód problému Dining Philosopher Problem pomocí semaforových operací čekání a signálu, požadovaný kód vypadá takto
void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } Ve výše uvedeném kódu je operace prvního čekání provedena na take_chopstickC[i] a take_chopstickC [ (i+1) % 5]. To ukazuje, že filozof jsem zvedl hůlky zleva a zprava. Poté se provede funkce stravování.
příklady mooreova stroje
Po dokončení jídla filozofem i the se signálová operace provede na take_chopstickC[i] a take_chopstickC [(i+1) % 5]. To ukazuje, že filozof, kterého jsem snědl, a položil levou i pravou hůlku. Nakonec filozof začne znovu přemýšlet.
Pojďme pochopit, jak výše uvedený kód poskytuje řešení problému jídelního filozofa?
Nechť hodnotu i = 0 ( počáteční hodnota ), Předpokládejme, že filozof P0 chce jíst, vstoupí do funkce Philosopher() a provede Wait( take_chopstickC[i] ); tím to drží C0 hůlka a snižuje semafor C0 na 0 , poté se provede Wait( take_chopstickC[(i+1) % 5] ); tím to drží C1 hůlka ( protože i =0, tedy (0 + 1) % 5 = 1) a redukuje semafor C1 na 0
Podobně předpokládejme, že nyní chce Philosopher P1 jíst, vstoupí do funkce Philosopher() a provede Wait( take_chopstickC[i] ); tím se pokusí udržet C1 hůlka ale nebude to moci udělat , protože hodnotu semaforu C1 již filozof P0 nastavil na 0, vstoupí tedy do nekonečné smyčky, kvůli které filozof P1 nebude moci chytit hůlku C1, zatímco pokud chce filozof P2 jíst, vstoupí do filozofa () fungovat a provádět Wait( take_chopstickC[i] ); tím to drží C2 hůlka a redukuje semafor C2 na 0, poté se provede Wait( take_chopstickC[(i+1) % 5] ); tím to drží C3 hůlka ( protože i =2, tedy (2 + 1) % 5 = 3) a redukuje semafor C3 na 0.
Výše uvedený kód tedy poskytuje řešení problému filozofa stolování. Filozof může jíst pouze tehdy, jsou-li k dispozici jak okamžité levé, tak pravé hůlky filozofa, jinak filozof musí čekat. Najednou také mohou jíst dva nezávislí filozofové současně (tj P0 a P2, P1 a P3 & P2 a P4 mohou jíst současně, protože všechny jsou nezávislé procesy a řídí se výše uvedeným omezením problému filozofa stolování)
plná forma i d e
Nevýhoda výše uvedeného řešení problému filozofa stolování
Z výše uvedeného řešení problému filozofa stolování jsme dokázali, že žádní dva sousední filozofové nemohou jíst ve stejném okamžiku. Nevýhodou výše uvedeného řešení je, že toto řešení může vést k uváznutí. Tato situace nastane, pokud všichni filozofové vezmou levou hůlku současně, což vede k uváznutí a žádný z filozofů nemůže jíst.
Aby nedošlo k uváznutí, některá z řešení jsou následující -
- Maximální počet filozofů na stole by neměl být více než čtyři, v tomto případě bude pro filozofa P3 k dispozici hůlka C4, takže P3 začne jíst a po skončení své stravovací procedury odloží obě hůlky C3. a C4, tj. semafor C3 a C4 se nyní zvýší na 1. Nyní bude mít filozof P2, který držel hůlku C2, k dispozici také hůlku C3, takže podobně po jídle hůlku odloží a umožní ostatním filozofům jíst.
- Filozof na sudé pozici by měl vybrat pravou hůlku a poté levou, zatímco filozof na liché pozici by měl vybrat hůlku levou a poté pravou.
- Pouze v případě, že jsou obě hůlky (levá a pravá) k dispozici současně, pouze tehdy by mělo být filozofovi umožněno si hůlky vybrat.
- Všichni čtyři začínající filozofové (P0, P1, P2 a P3) by měli vybrat levou hůlku a poté pravou hůlku, zatímco poslední filozof P4 by si měl vybrat hůlku pravou a poté hůlku levou. To donutí P4 držet svou pravou hůlku jako první, protože pravá hůlka P4 je C0, kterou již drží filozof P0 a její hodnota je nastavena na 0, tj. C0 je již 0, díky čemuž se P4 uvězní v nekonečnu. smyčka a hůlka C4 zůstávají prázdné. Filozof P3 má tedy k dispozici levou hůlku C3 i pravou hůlku C4, proto začne jíst a jakmile skončí, obě hůlky odloží a nechá jíst ostatní, což odstraňuje problém uváznutí.
Návrh problému měl ilustrovat výzvy, jak se vyhnout uváznutí, stav uváznutí systému je stav, ve kterém není možný žádný pokrok systému. Zvažte návrh, kde je každý filozof instruován, aby se choval následovně:
- Filozof je instruován, aby myslel, dokud nebude k dispozici levá vidlice, a když bude k dispozici, podržte ji.
- Filozof je instruován, aby myslel, dokud nebude k dispozici správná vidlička, a když bude k dispozici, držte ji.
- Filozof dostane pokyn k jídlu, když jsou k dispozici obě vidličky.
- pak nejprve položte pravou vidličku
- poté položte levou vidličku dolů
- opakujte od začátku.