Az étkezési filozófus problémája a klasszikus szinkronizációs probléma, amely szerint Öt filozófus ül egy kör alakú asztal körül, és az a feladatuk, hogy felváltva gondolkodjanak és étkezzenek. Egy tál tésztát helyeznek az asztal közepére, valamint öt pálcikát minden filozófus számára. Ahhoz, hogy egy filozófusnak egyen, szüksége van a jobb és a bal pálcikára is. Egy filozófus csak akkor tud enni, ha a filozófus közvetlen bal és jobb pálcikája is rendelkezésre áll. Abban az esetben, ha a filozófus közvetlen bal és jobb pálcikája nem áll rendelkezésre, akkor a filozófus leteszi (akár bal, akár jobb) pálcikáját, és újra gondolkodni kezd.
Az étkező filozófus a párhuzamosság-vezérlési problémák nagy csoportját mutatja be, ezért ez egy klasszikus szinkronizálási probléma.
Öt filozófus ül az asztal körül
Étkezési filozófusok probléma - Értsük meg a Dining Philosophers problémát az alábbi kóddal, az 1. ábrát referenciaként használtuk, hogy pontosan megértsük a problémát. Az öt filozófust P0, P1, P2, P3 és P4, öt pálcikát pedig C0, C1, C2, C3 és C4 jelképez.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Beszéljük meg a fenti kódot:
propozíciós logika
Tegyük fel, hogy a Philosopher P0 enni akar, belép a Philosopher() függvénybe, és végrehajtja take_chopsticck[i]; ezzel megtartja C0 pálcika ezt követően végrehajtja take_chopsticck[ (i+1) % 5]; ezzel megtartja C1 pálcika ( mivel i = 0, ezért (0 + 1) % 5 = 1)
Hasonlóképpen tegyük fel, hogy P1 Philosopher enni akar, belép a Philosopher() függvénybe, és végrehajtja vegye_evőpálcikát[i]; ezzel megtartja C1 pálcika ezt követően végrehajtja take_chopsticck[ (i+1) % 5]; ezzel megtartja C2 pálcika ( mivel i = 1, ezért (1 + 1) % 5 = 2)
De gyakorlatilag a Chopstick C1 nem elérhető, mivel P0 filozófus már átvette, ezért a fenti kód problémákat generál és versenyfeltételeket generál.
A Dining Philosophers probléma megoldása
Szemafort használunk a pálcika ábrázolására, és ez valóban megoldásként szolgál a Dining Philosophers Probléma megoldására. Az Étkezési Filozófusok Probléma megoldására a Wait és Signal műveleteket alkalmazzuk, a pálcika kiválasztásához várakozási műveletet, míg a pálcikajel elengedéséhez szemafort hajthatunk végre.
Szemafor: A szemafor egy egész szám változó S-ben, amely az inicializáláson kívül csak két szabványos atomi művelettel érhető el - várakozás és jelzés, amelyek definíciói a következők:
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></=> Kezdetben a C0, C1, C2, C3 és C4 szemafor minden elemét 1-re inicializálják, mivel az evőpálcikák az asztalon vannak, és egyik filozófus sem veszi fel őket.
Módosítsuk a Dining Philosopher Probléma fenti kódját várakozás és jelzés szemafor műveletek segítségével, a kívánt kód így néz ki
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 } } A fenti kódban az első várakozási művelet végrehajtásra kerül a take_chopstickC[i] és take_chopstickC [ (i+1) % 5] esetén. Ez azt mutatja, hogy a filozófus balról és jobbról felvette a pálcikát. Az étkezési funkciót ezután hajtják végre.
Amikor a filozófus befejezte az evést, a jelművelet végrehajtásra kerül a take_chopstickC[i] és take_chopstickC [(i+1) % 5]-nél. Ez azt mutatja, hogy a filozófus, akit megettem, és letette a bal és a jobb pálcikát is. Végül a filozófus újra gondolkodni kezd.
java 8
Értsük meg, hogy a fenti kód hogyan ad megoldást az étkezőfilozófus problémára?
Legyen i = 0 (kezdeti érték), tegyük fel, hogy P0 filozófus enni akar, belép a Philosopher() függvénybe, és végrehajtja Wait( take_chopsticckC[i] ); ezzel megtartja C0 pálcika és 0-ra csökkenti a C0 szemafort , ezt követően végrehajtja Wait( take_chopsticckC[(i+1) % 5] ); ezzel megtartja C1 pálcika ( mivel i =0, ezért (0 + 1) % 5 = 1) és a C1 szemafort 0-ra csökkenti
Hasonlóképpen, tegyük fel, hogy P1 Philosopher enni akar, belép a Philosopher() függvénybe, és végrehajtja Wait( take_chopsticckC[i] ); ezzel megpróbálja tartani C1 pálcika de erre nem lesz képes , mivel a C1 szemafor értékét P0 filozófus már 0-ra állította, ezért egy végtelen hurokba fog belépni, ami miatt P1 filozófus nem tudja felvenni a C1 pálcikát, míg ha P2 filozófus enni akar, akkor a Filozófusba lép. () függvényt, és hajtsa végre Wait( take_chopsticckC[i] ); ezzel megtartja C2 pálcika és lecsökkenti a C2 szemafort 0-ra, ezt követően végrehajtja Wait( take_chopsticckC[(i+1) % 5] ); ezzel megtartja C3 pálcika ( mivel i =2, ezért (2 + 1) % 5 = 3), és a C3 szemafort 0-ra csökkenti.
A fenti kód tehát megoldást nyújt az étkezőfilozófus problémára. A filozófus csak akkor tud enni, ha a filozófus közvetlen bal és jobb pálcikája is rendelkezésre áll, különben a filozófusnak várnia kell. Egyszerre két független filozófus is ehet egyszerre (azaz filozófus P0 és P2, P1 és P3 és P2 és P4 egyszerre tudnak enni, mivel mindegyik független folyamat, és az étkezési filozófus probléma fenti megkötését követik)
Az étkezőfilozófus probléma fenti megoldásának hátránya
Az étkezőfilozófus probléma fenti megoldásából bebizonyítottuk, hogy két szomszédos filozófus nem tud enni egy időben. A fenti megoldás hátránya, hogy ez a megoldás holtponthoz vezethet. Ez a helyzet akkor következik be, ha az összes filozófus egyszerre veszi fel a bal evőpálcikáját, ami holtponthoz vezet, és egyik filozófus sem tud enni.
A holtpont elkerülése érdekében néhány megoldás a következő:
- A filozófusok maximális száma az asztalon nem lehet több, mint négy, ebben az esetben a C4 evőpálcika elérhető lesz P3 filozófus számára, így P3 elkezd enni, és az étkezési procedúra befejezése után leteszi mindkét pálcikáját C3. és C4, azaz a C3 és C4 szemafor most 1-re nő. Most P2 filozófusnak, aki a C2 evőpálcikát tartotta, a C3 pálcika is elérhető lesz, így evés után leteszi a pálcikáját, és lehetővé teszi más filozófusok számára az evést.
- A páros helyzetben lévő filozófusnak a jobb pálcikát, majd a bal pálcikát, míg a páratlan helyzetben lévő filozófusnak a bal, majd a jobb pálcikát kell választania.
- Csak abban az esetben, ha mindkét pálcika (bal és jobb) egyszerre elérhető, csak akkor szabad engedni, hogy egy filozófus vegye ki a pálcikáját
- Mind a négy kiinduló filozófusnak (P0, P1, P2 és P3) a bal evőpálcikát, majd a jobb oldali pálcikát kell választania, míg az utolsó filozófusnak, P4-nek a jobb pálcikát, majd a bal evőpálcikát kell választania. Ez arra kényszeríti P4-et, hogy először a jobb evőpálcikáját fogja meg, mivel P4 jobb evőpálcikája C0, amit már P0 filozófus tart, és értéke 0-ra van állítva, azaz C0 már 0, ami miatt P4 egy végtelenbe fog szorulni. hurok és pálcika C4 üresen marad. Ezért a P3 filozófusnak rendelkezésre áll a bal oldali C3 és a jobb oldali C4 pálcika is, ezért elkezd enni, és leteszi mindkét pálcikáját, miután végzett, és hagyja, hogy mások enjenek, ami megszünteti a holtpont problémáját.
A probléma megtervezése az volt, hogy szemléltesse a holtpont elkerülésének kihívásait, a rendszer patthelyzete az az állapot, amelyben a rendszer előrehaladása nem lehetséges. Tekintsünk egy javaslatot, amelyben minden filozófus a következőképpen kell viselkednie:
teljes összeadó áramkör
- A filozófus arra kapott utasítást, hogy addig gondolkodjon, amíg a bal villa rendelkezésre nem áll, ha elérhető, tartsa meg.
- A filozófus arra kapott utasítást, hogy addig gondolkodjon, amíg a megfelelő villa rendelkezésre nem áll, ha elérhető, tartsa meg.
- A filozófust arra utasítják, hogy egyen, amikor mindkét villa rendelkezésre áll.
- majd először tegye le a jobb villát
- ezután tegye le a bal villát
- ismételje meg az elejétől.