식사하는 철학자의 문제는 다섯 명의 철학자가 원형 테이블 주위에 앉아 있고 그들의 임무는 번갈아 생각하고 먹는 것이라는 고전적인 동기화 문제입니다. 테이블 중앙에는 국수 한 그릇과 각 철학자의 젓가락 5개가 놓여 있습니다. 철학자를 먹으려면 오른쪽 젓가락과 왼쪽 젓가락이 모두 필요합니다. 철학자는 바로 왼쪽과 오른쪽 젓가락을 모두 사용할 수 있는 경우에만 식사를 할 수 있습니다. 철학자의 바로 왼쪽 및 오른쪽 젓가락을 모두 사용할 수 없는 경우 철학자는 (왼쪽 또는 오른쪽) 젓가락을 내려놓고 다시 생각하기 시작합니다.
식사하는 철학자는 동시성 제어 문제의 큰 클래스를 보여 주므로 이는 고전적인 동기화 문제입니다.
테이블 주위에 앉아있는 다섯 명의 철학자
식사 철학자 문제 - 식사 철학자 문제를 아래 코드로 이해해 봅시다. 문제를 정확하게 이해하기 위해 그림 1을 참고 자료로 사용했습니다. 다섯 명의 철학자는 P0, P1, P2, P3, P4로 표시되고 다섯 개의 젓가락은 C0, C1, C2, C3, C4로 표시됩니다.
bash는 구분 기호로 문자열을 분할합니다.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } 위의 코드에 대해 논의해 보겠습니다.
Philosopher P0가 식사를 원한다고 가정하면 Philosopher() 함수에 들어가서 실행됩니다. take_chopstick[i]; 이렇게 하면 유지됩니다. C0젓가락 그 후에는 실행됩니다. take_chopstick[ (i+1) % 5]; 이렇게 하면 유지됩니다. C1 젓가락 ( i =0이므로 (0 + 1) % 5 = 1)
마찬가지로 이제 Philosopher P1이 식사를 원한다고 가정하고 Philosopher() 함수에 입력하여 실행합니다. take_chopstick[i]; 이렇게 하면 유지됩니다. C1 젓가락 그 후에는 실행됩니다. take_chopstick[ (i+1) % 5]; 이렇게 하면 유지됩니다. C2젓가락 ( i =1이므로 (1 + 1) % 5 = 2)
그러나 실제로 젓가락 C1은 철학자 P0이 이미 사용했기 때문에 사용할 수 없습니다. 따라서 위 코드는 문제를 일으키고 경쟁 조건을 생성합니다.
속편 데이터 유형
식사 철학자 문제의 해결
우리는 젓가락을 표현하기 위해 세마포어를 사용하며 이는 식사 철학자 문제의 진정한 해결책으로 작용합니다. 식사 철학자 문제를 해결하기 위해 대기 및 신호 연산이 사용됩니다. 젓가락을 집기 위한 대기 연산이 실행될 수 있고 젓가락을 떼기 위한 신호 세마포어가 실행될 수 있습니다.
세마포어: 세마포어는 S의 정수 변수로, 초기화 외에 두 가지 표준 원자 연산(대기 및 신호)으로만 액세스됩니다. 해당 정의는 다음과 같습니다.
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></=> 처음에는 젓가락이 테이블 위에 있고 어떤 철학자도 집지 않기 때문에 세마포어 C0, C1, C2, C3 및 C4의 각 요소는 1로 초기화됩니다.
위의 식사 철학자 문제 코드를 세마포어 연산 대기 및 신호를 사용하여 수정해 보겠습니다. 원하는 코드는 다음과 같습니다.
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 } } 위 코드에서는 take_chopstickC[i] 및 take_chopstickC [ (i+1) % 5]에 대해 첫 번째 대기 작업이 수행됩니다. 이것은 철학자 내가 왼쪽과 오른쪽에서 젓가락을 집었다는 것을 보여줍니다. 그 후에 식사 기능이 수행됩니다.
라텍스로 테이블 만들기
철학자 i의 식사가 완료되면 take_chopstickC[i]와 take_chopstickC[(i+1)% 5]에 대해 신호 연산을 수행합니다. 이는 내가 밥을 먹고 왼쪽 젓가락과 오른쪽 젓가락을 모두 내려놓은 철학자를 보여준다. 마침내 철학자는 다시 생각하기 시작합니다.
위의 코드가 식사 철학자 문제에 대한 해결책을 어떻게 제공하는지 이해해 봅시다.
i의 값을 0(초기값)으로 하고, 철학자 P0이 먹고 싶어 한다고 가정하면 철학자() 함수에 입력되어 실행됩니다. 잠깐( take_chopstickC[i] ); 이렇게 하면 유지됩니다. C0젓가락 세마포어 C0을 0으로 줄입니다. , 그 후에는 실행됩니다. 잠깐( take_chopstickC[(i+1) % 5] ); 이렇게 하면 유지됩니다. C1 젓가락 ( i =0이므로 (0 + 1) % 5 = 1) 세마포어 C1을 0으로 줄입니다.
마찬가지로 이제 철학자 P1이 식사를 원한다고 가정하고 철학자() 함수에 입력하여 실행합니다. 잠깐( take_chopstickC[i] ); 이렇게 하면 유지하려고 할 것입니다. C1 젓가락 하지만 그렇게 할 수는 없을 거야 , 세마포어 C1의 값은 철학자 P0에 의해 이미 0으로 설정되었으므로 철학자 P1이 젓가락 C1을 선택할 수 없기 때문에 무한 루프에 들어가게 됩니다. 반면 철학자 P2가 먹고 싶어하면 철학자에 들어갑니다. () 함수 및 실행 잠깐( take_chopstickC[i] ); 이렇게 하면 유지됩니다. C2젓가락 세마포어 C2를 0으로 줄인 후 실행됩니다. 잠깐( take_chopstickC[(i+1) % 5] ); 이렇게 하면 유지됩니다. C3젓가락 ( i =2이므로 (2 + 1) % 5 = 3) 세마포어 C3을 0으로 줄입니다.
따라서 위의 코드는 식사하는 철학자 문제에 대한 해결책을 제공합니다. 철학자는 철학자의 바로 왼쪽 및 오른쪽 젓가락을 모두 사용할 수 있는 경우에만 식사를 할 수 있으며, 그렇지 않으면 철학자가 기다려야 합니다. 또한 한 번에 두 명의 독립적인 철학자가 동시에 식사를 할 수도 있습니다(즉, 철학자 P0과 P2, P1과 P3 & P2와 P4 모두 독립적인 과정이고 위의 식사 철학자 문제의 제약을 따르기 때문에 동시에 먹을 수 있습니다.)
CSS 테두리
위의 식사 철학자 문제 해결의 단점
위의 식사하는 철학자 문제의 해결로부터 우리는 이웃에 있는 두 명의 철학자가 같은 시점에 식사를 할 수 없다는 것을 증명했습니다. 위 솔루션의 단점은 이 솔루션이 교착 상태로 이어질 수 있다는 것입니다. 이러한 상황은 모든 철학자가 동시에 왼쪽 젓가락을 집는 경우 발생하며, 이로 인해 교착 상태가 발생하고 철학자 중 누구도 식사를 할 수 없게 됩니다.
교착 상태를 방지하기 위한 일부 솔루션은 다음과 같습니다.
- 테이블에 있는 철학자의 최대 수는 4명을 초과할 수 없습니다. 이 경우 철학자 P3은 젓가락 C4를 사용할 수 있으므로 P3은 식사를 시작하고 식사 절차가 끝나면 두 젓가락 C3을 내려놓습니다. 그리고 C4, 즉 세마포어 C3과 C4는 이제 1로 증가됩니다. 이제 젓가락 C2를 들고 있던 철학자 P2도 젓가락 C3을 사용할 수 있으므로 마찬가지로 식사 후에 젓가락을 내려놓고 다른 철학자들이 식사할 수 있도록 합니다.
- 짝수 위치에 있는 철학자는 오른쪽 젓가락을 선택한 다음 왼쪽 젓가락을 선택하고, 홀수 위치에 있는 철학자는 왼쪽 젓가락을 선택한 다음 오른쪽 젓가락을 선택해야 합니다.
- 두 젓가락(왼쪽과 오른쪽)을 동시에 사용할 수 있는 경우에만 철학자가 젓가락을 선택할 수 있어야 합니다.
- 시작 철학자 4명(P0, P1, P2, P3)은 모두 왼쪽 젓가락을 선택한 다음 오른쪽 젓가락을 선택해야 하고, 마지막 철학자 P4는 오른쪽 젓가락을 선택한 다음 왼쪽 젓가락을 선택해야 합니다. P4의 오른쪽 젓가락은 이미 철학자 P0이 잡고 있고 그 값이 0으로 설정되어 있는 C0이기 때문에 P4는 오른쪽 젓가락을 먼저 잡게 됩니다. 즉, C0은 이미 0이므로 P4는 무한의 세계에 갇히게 됩니다. 고리와 젓가락 C4는 비어있습니다. 따라서 철학자 P3은 왼쪽 C3 및 오른쪽 C4 젓가락을 모두 사용할 수 있으므로 식사를 시작하고 식사가 끝나면 두 젓가락을 모두 내려 놓고 다른 사람이 먹도록 하여 교착 상태 문제를 제거합니다.
문제의 설계는 교착 상태를 피하는 과제를 설명하기 위한 것이었습니다. 시스템의 교착 상태는 시스템의 진행이 불가능한 상태입니다. 각 철학자에게 다음과 같이 행동하도록 지시하는 제안을 생각해 보세요.
- 철학자는 왼쪽 포크를 사용할 수 있을 때까지 생각하고, 사용할 수 있을 때 이를 잡도록 지시받습니다.
- 철학자는 올바른 포크가 나올 때까지 생각하고, 포크가 나올 때 그것을 쥐도록 지시받습니다.
- 철학자는 두 포크를 모두 사용할 수 있을 때 먹으라는 지시를 받습니다.
- 그런 다음 오른쪽 포크를 먼저 내려놓으세요
- 그런 다음 왼쪽 포크를 아래로 내려놓으세요
- 처음부터 반복하세요.