Problemem filozofa jadającego jest klasyczny problem synchronizacji, który mówi, że pięciu filozofów siedzi wokół okrągłego stołu, a ich zadaniem jest naprzemienne myślenie i jedzenie. Na środku stołu ustawiana jest miska z makaronem i po pięć pałeczek dla każdego z filozofów. Aby zjeść filozofa, potrzebna jest zarówno prawa, jak i lewa pałeczka. Filozof może jeść tylko wtedy, gdy dostępne są zarówno lewe, jak i prawe pałeczki filozofa. W przypadku, gdy zarówno lewa, jak i prawa pałeczka filozofa nie są dostępne, filozof odkłada swoją (lewą lub prawą) pałeczkę i zaczyna myśleć od nowa.
Filozof kulinarny demonstruje dużą klasę problemów kontroli współbieżności, dlatego jest to klasyczny problem synchronizacji.
Pięciu filozofów siedzących wokół stołu
Problem filozofów kulinarnych - Rozumiemy problem Dining Philosophers za pomocą poniższego kodu, użyliśmy rys. 1 jako odniesienia, abyś mógł dokładnie zrozumieć problem. Pięciu Filozofów jest reprezentowanych jako P0, P1, P2, P3 i P4, a pięć pałeczek przez C0, C1, C2, C3 i C4.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Omówmy powyższy kod:
Załóżmy, że Filozof P0 chce zjeść, wejdzie w funkcję Filozof() i wykona weź_pałeczkę[i]; robiąc to, trzyma się Pałeczka C0 po czym następuje wykonanie take_chopstick[(i+1) % 5]; robiąc to, trzyma się Pałeczka C1 (ponieważ i =0, zatem (0 + 1) % 5 = 1)
Podobnie załóżmy, że teraz Filozof P1 chce zjeść, wejdzie w funkcję Filozof() i wykona weź_pałeczkę[i]; robiąc to, trzyma się Pałeczka C1 po czym następuje wykonanie take_chopstick[(i+1) % 5]; robiąc to, trzyma się Pałeczka C2 (ponieważ i =1, zatem (1 + 1) % 5 = 2)
Ale praktycznie Chopstick C1 nie jest dostępny, ponieważ został już zajęty przez filozofa P0, stąd powyższy kod generuje problemy i powoduje sytuację wyścigową.
Rozwiązanie problemu filozofów spożywających posiłki
Używamy semafora do przedstawienia pałeczki, co naprawdę stanowi rozwiązanie Problemu Filozofów Jadalni. Operacje oczekiwania i sygnału zostaną użyte do rozwiązania problemu filozofów jadalni, w przypadku wybrania pałeczki można wykonać operację oczekiwania, natomiast w przypadku zwolnienia pałeczki można wykonać semafor sygnału pałeczki.
ile jest w nas miast
Semafor: Semafor jest zmienną całkowitą w S, do której oprócz inicjalizacji dostęp mają tylko dwie standardowe operacje atomowe - oczekiwanie i sygnał, których definicje są następujące:
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></=> Początkowo każdy element semafora C0, C1, C2, C3 i C4 jest inicjowany na 1, ponieważ pałeczki leżą na stole i nie zostały podniesione przez żadnego z filozofów.
Zmodyfikujmy powyższy kod Problemu Filozofa Jadalni, używając operacji semaforowych czekaj i sygnalizuj, pożądany kod wygląda tak
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 } } W powyższym kodzie pierwsza operacja oczekiwania jest wykonywana na take_chopstickC[i] i take_chopstickC [ (i+1) % 5]. To pokazuje filozofa, że podniosłem pałeczki z lewej i prawej strony. Następnie wykonywana jest funkcja jedzenia.
Po zakończeniu jedzenia przez filozofa i the, wykonywana jest operacja sygnalizacyjna na take_chopstickC[i] i take_chopstickC [ (i+1) % 5]. To pokazuje, że filozof, którego zjadłem, odłożył zarówno lewą, jak i prawą pałeczkę. Wreszcie filozof zaczyna znowu myśleć.
Rozumiemy, w jaki sposób powyższy kod daje rozwiązanie problemu filozofa jadalni?
Niech wartość i = 0 (wartość początkowa), załóżmy, że Filozof P0 chce zjeść, wejdzie w funkcję Filozof() i wykona Czekaj (take_chopstickC[i] ); robiąc to, trzyma się Pałeczka C0 i zmniejsza semafor C0 do 0 , po czym następuje wykonanie Czekaj (take_chopstickC[(i+1) % 5] ); robiąc to, trzyma się Pałeczka C1 (ponieważ i =0, zatem (0 + 1) % 5 = 1) i redukuje semafor C1 do 0
Podobnie, załóżmy, że teraz Filozof P1 chce zjeść, wejdzie w funkcję Filozof() i wykona Czekaj (take_chopstickC[i] ); w ten sposób będzie próbował utrzymać Pałeczka C1 ale nie będzie w stanie tego zrobić , ponieważ wartość semafora C1 została już przez filozofa P0 ustawiona na 0, zatem wejdzie on w nieskończoną pętlę przez co filozof P1 nie będzie mógł podnieść pałeczki C1 natomiast jeśli Filozof P2 będzie chciał jeść to wejdzie do Filozofa () wykonaj funkcję i wykonaj Czekaj (take_chopstickC[i] ); robiąc to, trzyma się Pałeczka C2 i zmniejsza semafor C2 do 0, po czym wykonuje Czekaj (take_chopstickC[(i+1) % 5] ); robiąc to, trzyma się Pałeczka C3 (ponieważ i =2, zatem (2 + 1) % 5 = 3) i redukuje semafor C3 do 0.
Stąd powyższy kod zapewnia rozwiązanie problemu filozofa jadającego. Filozof może jeść tylko wtedy, gdy dostępne są zarówno lewe, jak i prawe pałeczki filozofa, w przeciwnym razie filozof musi poczekać. Również za jednym razem może jeść jednocześnie dwóch niezależnych filozofów (tj P0 i P2, P1 i P3 oraz P2 i P4 mogą jeść jednocześnie, ponieważ wszystkie są niezależnymi procesami i są zgodne z powyższym ograniczeniem problemu filozofa jadalni)
Wada powyższego rozwiązania problemu filozofa jadalni
Z powyższego rozwiązania problemu filozofa spożywającego posiłki udowodniliśmy, że żaden dwóch sąsiadujących ze sobą filozofów nie może jeść w tym samym momencie. Wadą powyższego rozwiązania jest to, że może ono prowadzić do stanu zakleszczenia. Taka sytuacja ma miejsce, jeśli wszyscy filozofowie jednocześnie chwytają lewą pałeczkę, co prowadzi do stanu impasu i żaden z filozofów nie może jeść.
Aby uniknąć impasu, niektóre rozwiązania są następujące:
- Maksymalna liczba filozofów na stole nie powinna być większa niż czterech, w tym przypadku pałeczka C4 będzie dostępna dla filozofa P3, więc P3 zacznie jeść i po zakończeniu swojej procedury jedzenia odłoży obie pałeczki C3 i C4, czyli semafory C3 i C4 zostaną teraz zwiększone do 1. Teraz filozof P2, który trzymał pałeczkę C2, będzie miał także dostępną pałeczkę C3, stąd analogicznie odłoży pałeczkę po jedzeniu i umożliwi jedzenie innym filozofom.
- Filozof znajdujący się na parzystej pozycji powinien wybrać prawą, a następnie lewą pałeczkę, natomiast filozof znajdujący się na nieparzystej pozycji powinien wybrać lewą, a następnie prawą pałeczkę.
- Tylko w przypadku, gdy obie pałeczki (lewa i prawa) są dostępne w tym samym czasie, tylko wtedy filozof powinien mieć możliwość wybrania pałeczek
- Wszyscy czterej filozofowie rozpoczynający grę (P0, P1, P2 i P3) powinni wybrać lewą, a następnie prawą pałeczkę, podczas gdy ostatni filozof P4 powinien wybrać prawą, a następnie lewą pałeczkę. Zmusi to P4 do trzymania swojej prawej pałeczki jako pierwszej, ponieważ prawa pałeczka P4 to C0, którą trzyma już filozof P0 i jej wartość jest ustawiona na 0, tj. C0 wynosi już 0, przez co P4 zostanie uwięziony w nieskończoności pętla i pałeczka C4 pozostają wolne. Zatem filozof P3 ma do dyspozycji zarówno lewą, jak i prawą pałeczkę C4, dlatego zacznie jeść, a gdy skończy, odłoży obie pałeczki i pozwoli innym jeść, co eliminuje problem impasu.
Projekt problemu miał na celu zilustrowanie wyzwań związanych z unikaniem zakleszczenia, stan zakleszczenia systemu to stan, w którym nie jest możliwy żaden postęp systemu. Rozważmy propozycję, w której każdy filozof ma postępować w następujący sposób:
- Filozofowi polecono myśleć, dopóki lewy widelec nie będzie dostępny, a gdy będzie dostępny, przytrzymaj go.
- Filozofowi polecono myśleć, dopóki nie będzie dostępny właściwy widelec, a kiedy będzie dostępny, przytrzymaj go.
- Filozofowi polecono jeść, gdy oba widelce są dostępne.
- następnie odłóż najpierw prawy widelec
- następnie odłóż lewy widelec
- powtórz od początku.