Filosofos glutões

Problema dos filósofos glutões:
Este é um problema clássico de sincronização entre processos. N filósofos estão sentados ao redor de uma mesa redonda tendo um prato de macarrão diante de si e entre cada dois pratos existe um garfo. A vida de um filósofo é pensar, comer, pensar, comer e assim indefinidamente. No entanto, para comer, o filósofo precisa necessariamente de dois garfos (um que está à sua esquerda e o outro à sua direita). Quando terminou de pensar (por ter fome), tenta pegar os garfos vizinhos para poder comer. Ao terminar de comer, devolve os garfos à mesa.

Solução 1:
• A operação pega_garfo coloca o processo para dormir, se o garfo não estiver disponível. • O número do garfo à direita do filósofo i é i. O número do garfo à esquerda do filósofo i é (i+1)%N.
#define N 5 void filosofo(int i) { while (1) { pensa(); pega_garfo(i); /* espera que garfo esteja livre */ pega_garfo((i+1)%N); /* espera que garfo esteja livre */ come(); devolve_garfo(i); devolve_garfo((i+1)%N); } }

Problema: se todos terminarem de pensar ao mesmo tempo e tentarem pegar o garfo da direita. Ao tentar pegar o garfo da esquerda, não conseguirão e irão todos dormir (estado de "bloqueado"). A situação na qual todos os processos de um sistema estão bloqueados é chamada "deadlock" (ou "travamento"). Pseudo-solução: Após pegar o garfo da direita, verifica se o da esquerda está disponível. Se não estiver, devolve o garfo da direita e tenta novamente pegar os dois garfos mais tarde. Problema: Há a possibilidade dos processos ficarem pegando e devolvendo garfos indefinidamente. A situação na qual os processos estão rodando (estados "rodando" e "pronto") somente tentando pegar os garfos sem jamais comer é chamada "livelock" ou "starvation". Melhora da pseudo-solução: fazer com que o filósofo, quando não conseguir obter o segundo garfo, devolva o primeiro, espere um tempo aleatório e tente novamente. Neste caso, a probabilidade de starvation é pequena, mas é existente e há