O Jantar dos filósofos

O Jantar dos Filósofos é problema clássico de sincronização proposto por Dijkstra em 1965. A capa da revista Communications of the ACM de Janeiro de 1988 ilustra a aplicação prática deste problema em uma situação do mundo real…

O Jantar dos filósofos, Communications of the ACM, January 1988

Este projeto consiste em implementar o problema do jantar dos filósofos em C, usando uma thread Posix para modelar cada filósofo e um semáforo Posix para cada palito (chopstick).

Cada um dos 5 filósofos tem o seguinte comportamento:

while (true)
{
   meditar (duração aleatória entre 0 e 2 segundos)
   pegar o palito à sua esquerda
   pegar o palito à sua direita
   comer (duração aleatória entre 0 e 2 segundos)
   soltar os palitos
}
  • Devem ser usados semáforos POSIX na solução; laços de espera ocupada (busy-wait) não são permitidos.
  1. Implementar uma solução sem controle de impasses
  2. Implementar uma solução com controle de impasses através de serialização (“solução do saleiro”)
  3. Implementar uma solução com controle de impasses que permita o máximo paralelismo entre os filósofos
  4. Medir o número de filósofos que podem comer por segundo, nas três soluções (desabilitar as pausas para efetuar essa medição)

Para medir o desempenho de cada solução, a thread principal (main) pode executar o seguinte laço, após ter criado as demais threads1):

while(1)
{
   sleep (1) ;
   pthread_mutex_lock (&mut) ;
   printf ("Refeições por segundo: %d\n", numRefeicoes) ;
   numRefeicoes = 0 ;
   pthread_mutex_unlock (&mut) ;
}

O contador numRefeicoes deve ser incrementado cada vez que um filósofo comer; o Mutex mut serve para evitar condições de disputa envolvendo esse contador. Ambos devem ser variáveis globais.

  1. As implementações realizadas
  2. Um relatório sucinto (e no formato correto) descrevendo os resultados observados nas experiências.

1)
Obrigado ao Marco Kawajiri por esta ideia
  • so/jantar_dos_filosofos.txt
  • Última modificação: 2011/09/26 19:32
  • por maziero