O problema do filósofo que janta é o clássico problema de sincronização, que diz que Cinco filósofos estão sentados ao redor de uma mesa circular e sua função é pensar e comer alternadamente. Uma tigela de macarrão é colocada no centro da mesa junto com cinco pauzinhos para cada um dos filósofos. Para comer, um filósofo precisa de um pauzinho direito e esquerdo. Um filósofo só pode comer se os pauzinhos esquerdo e direito do filósofo estiverem disponíveis. Caso os pauzinhos esquerdo e direito imediatos do filósofo não estejam disponíveis, o filósofo abaixa o pauzinho (esquerdo ou direito) e começa a pensar novamente.
O filósofo do jantar demonstra uma grande classe de problemas de controle de simultaneidade, portanto, é um problema clássico de sincronização.
Cinco Filósofos sentados à mesa
Problema dos Filósofos de Jantar - Vamos entender o Problema dos Filósofos do Jantar com o código abaixo, usamos a fig 1 como referência para que você entenda exatamente o problema. Os cinco Filósofos são representados como P0, P1, P2, P3 e P4 e os cinco pauzinhos por C0, C1, C2, C3 e 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 } } Vamos discutir o código acima:
Suponha que o Filósofo P0 queira comer, ele entrará na função Philosopher() e executará pegue_chopstick[i]; fazendo isso ele mantém Pauzinho C0 depois disso ele executa pegue_chopstick[(i+1)% 5]; fazendo isso ele mantém pauzinho C1 (já que i = 0, portanto (0 + 1)% 5 = 1)
Da mesma forma, suponha que agora o Filósofo P1 queira comer, ele entrará na função Filósofo() e executará pegue_chopstick[i]; ao fazer isso, ele mantém pauzinho C1 depois disso ele executa pegue_chopstick[(i+1)% 5]; fazendo isso ele mantém Pauzinho C2 (já que i =1, portanto (1 + 1)% 5 = 2)
Mas praticamente o Chopstick C1 não está disponível porque já foi utilizado pelo filósofo P0, portanto o código acima gera problemas e produz condição de corrida.
A solução do problema dos filósofos do jantar
Usamos um semáforo para representar um pauzinho e isso realmente funciona como uma solução para o Problema dos Filósofos do Jantar. As operações de Espera e Sinal serão usadas para a solução do Problema dos Filósofos do Jantar, para escolher um pauzinho a operação de espera pode ser executada enquanto para liberar um sinal de pauzinho o semáforo pode ser executado.
Semáforo: Um semáforo é uma variável inteira em S, que além da inicialização é acessada por apenas duas operações atômicas padrão - espera e sinal, cujas definições são as seguintes:
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></=> Inicialmente, cada elemento do semáforo C0, C1, C2, C3 e C4 é inicializado com 1, pois os pauzinhos estão sobre a mesa e não são pegos por nenhum dos filósofos.
Vamos modificar o código acima do problema do filósofo de jantar usando operações de semáforo, espera e sinal, o código desejado se parece com
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 } } No código acima, a primeira operação de espera é executada em take_chopstickC[i] e take_chopstickC [(i+1)% 5]. Isso mostra ao filósofo que peguei os pauzinhos à esquerda e à direita. A função alimentar é executada depois disso.
Após a conclusão da alimentação pelo filósofo i, a operação de sinal é executada em take_chopstickC[i] e take_chopstickC [(i+1) % 5]. Isso mostra que o filósofo comeu e largou os pauzinhos esquerdo e direito. Finalmente, o filósofo começa a pensar novamente.
Vamos entender como o código acima está dando uma solução para o problema do filósofo do jantar?
Seja o valor de i = 0 (valor inicial), suponha que o Filósofo P0 queira comer, ele entrará na função Philosopher() e executará Espere(take_chopstickC[i]); ao fazer isso, ele mantém Pauzinho C0 e reduz o semáforo C0 para 0 , depois disso ele executa Espere(take_chopstickC[(i+1)% 5]); fazendo isso ele mantém pauzinho C1 (já que i =0, portanto (0 + 1)% 5 = 1) e reduz o semáforo C1 a 0
Da mesma forma, suponha que agora o Filósofo P1 queira comer, ele entrará na função Filósofo() e executará Espere(take_chopstickC[i]); ao fazer isso, ele tentará segurar pauzinho C1 mas não será capaz de fazer isso , como o valor do semáforo C1 já foi definido como 0 pelo filósofo P0, portanto ele entrará em um loop infinito por causa do qual o filósofo P1 não poderá pegar o pauzinho C1 enquanto que se o Filósofo P2 quiser comer, ele entrará no Filósofo ()funcionar e executar Espere(take_chopstickC[i]); fazendo isso ele mantém Pauzinho C2 e reduz o semáforo C2 para 0, após isso executa Espere(take_chopstickC[(i+1)% 5]); fazendo isso ele mantém Pauzinho C3 (já que i =2, portanto (2 + 1)% 5 = 3) e reduz o semáforo C3 a 0.
Conseqüentemente, o código acima fornece uma solução para o problema do jantar do filósofo. Um filósofo só pode comer se os pauzinhos esquerdo e direito do filósofo estiverem disponíveis, caso contrário, o filósofo precisará esperar. Além disso, de uma só vez, dois filósofos independentes podem comer simultaneamente (ou seja, o filósofo P0 e P2, P1 e P3 e P2 e P4 pode comer simultaneamente, pois todos são processos independentes e seguem a restrição acima do problema do filósofo de jantar)
A desvantagem da solução acima do problema do filósofo do jantar
A partir da solução acima do problema do jantar do filósofo, provamos que dois filósofos vizinhos não podem comer ao mesmo tempo. A desvantagem da solução acima é que esta solução pode levar a uma condição de impasse. Essa situação acontece se todos os filósofos pegarem o pauzinho esquerdo ao mesmo tempo, o que leva à condição de impasse e nenhum dos filósofos consegue comer.
Para evitar impasses, algumas das soluções são as seguintes -
- O número máximo de filósofos na mesa não deve ser superior a quatro, neste caso o pauzinho C4 estará disponível para o filósofo P3, então P3 começará a comer e após terminar sua alimentação ele largará os dois pauzinhos C3 e C4, ou seja, os semáforos C3 e C4 serão agora incrementados para 1. Agora o filósofo P2 que segurava o pauzinho C2 também terá o pauzinho C3 disponível, portanto, da mesma forma, ele largará o pauzinho depois de comer e permitirá que outros filósofos comam.
- Um filósofo em uma posição par deve pegar o pauzinho direito e depois o pauzinho esquerdo, enquanto um filósofo em uma posição ímpar deve pegar o pauzinho esquerdo e depois o pauzinho direito.
- Somente no caso de ambos os pauzinhos (esquerdo e direito) estarem disponíveis ao mesmo tempo, só então um filósofo poderá escolher seus pauzinhos
- Todos os quatro filósofos iniciais (P0, P1, P2 e P3) devem escolher o pauzinho esquerdo e depois o pauzinho direito, enquanto o último filósofo P4 deve escolher o pauzinho direito e depois o pauzinho esquerdo. Isso forçará P4 a segurar primeiro o pauzinho direito, já que o pauzinho direito de P4 é C0, que já é segurado pelo filósofo P0 e seu valor está definido como 0, ou seja, C0 já é 0, por causa do qual P4 ficará preso em um infinito loop e pauzinho C4 permanecem vagos. Conseqüentemente, o filósofo P3 tem os pauzinhos C3 esquerdo e C4 direito disponíveis, portanto, ele começará a comer e largará os dois pauzinhos quando terminar e deixará os outros comerem, o que elimina o problema do impasse.
O desenho do problema era ilustrar os desafios de evitar impasses. Um estado de impasse de um sistema é um estado no qual nenhum progresso do sistema é possível. Considere uma proposta onde cada filósofo é instruído a se comportar da seguinte forma:
- O filósofo é instruído a pensar até que o garfo esquerdo esteja disponível, quando estiver disponível, segure-o.
- O filósofo é instruído a pensar até que o garfo certo esteja disponível, quando estiver disponível, segure-o.
- O filósofo é instruído a comer quando ambos os garfos estiverem disponíveis.
- então, coloque o garfo direito primeiro
- então, coloque o garfo esquerdo em seguida
- repita desde o início.