ALGORITMOS: O Jantar dos Filósofos

O Problema do Jantar dos Filósofos é um problema de programação concorrente proposto por Dijkstra em 1965 e é uma alegoria do que ocorre nos sistemas computacionais multiprocessados que disputam os mesmos recursos limitados e dependem de um algoritmo mestre ou de um sistema operacional que evite a ocorrência de conflitos entre os processos concorrentes. Consiste no seguinte:

Há cinco filósofos sentados ao redor de uma mesa sobre a qual estão cinco talheres. Diante de cada filósofo há uma refeição a comer e os talheres estão dispostos nos dois lados de cada prato de tal forma que há apenas um talher entre cada dois filósofos. Para comer, cada filósofo deve usar dois talheres. Enquanto não comem, os filósofos ficam pensando.

A exigência para a solução deste problema é a criação de um algoritmo que gerencie a janta ordeira do grupo, sem que os filósofos briguem por talheres que estão sendo utilizados.

Considerando que este problema é um problema computacional, é importante percebermos que se escolhermos arbitrariamente um filósofo para comer primeiro, podemos permitir que outro coma desde este esteja em tal posição que o primeiro escolhido não seja incomodado. Isso é fácil de conceber se imaginarmos os filósofos sentados em tal posição que suas cadeiras formem os vértices de um pentágono. Neste caso, para cada filósofo escolhido arbitrariamente, há um filósofo em posição oposta ao vértice que pode também pode comer. Considerando isso, os opostos dos vértice do ângulo agudo (o filósofo sentado na cabeceira da mesa) são os vértices dos ângulos da base (os filósofos sentados na extremidade da mesa). Se escolhêssemos o filósofo sentado na cabeceira para comer primeiro, poderíamos escolher para comer com ele um dos filósofos sentados na extremidade da mesa. Os demais esperariam pelos talheres. De semelhante forma, se escolhêssemos um dos mais próximos ao filósofo na cabeceira, o seu companheiro de janta seria aquele que está do lado oposto da mesa.

Podemos escolher dois filósofos por etapa unitária. Isso nos conduz sempre a três etapas: em duas etapas comem dois e noutra somente um. Assim uma das combinações possíveis (descrita no quadro 1 nas instâncias Th1, Th2 e Th3) segue abaixo em pseudocódigo orientado a objeto que assume o conceito de mutex. No quadro 2, reparar que VarMutex referencia Mesa; P1 referencia F1, F2 e F3 quando passados em parâmetro; idem para P2 que referencia F4 e F5. Reparar também que a classe Thread define vários tipos de parâmetros para “inicia,” cuja execução é determinada e gerenciada pelo escalonador do sistema operacional, aplicando-se o mesmo princípio para a sua sub-classe Filosofo.

1. Programa Principal

   Filosofo F1, F2, F3, F4, F5
   Talher T1, T2, T3, T4, T5
   Thread Th1, Th2, Th3
   Mutex Mesa

   .
   .
   .

   F1.associa (T1, T2)
   F2.associa (T1, T3)
   F3.associa (T3, T5)
   F4.associa (T4, T5)
   F5.associa (T2, T4)

   Th1 = cria Thread (Mesa)
   Th2 = cria Thread (Mesa)
   Th3 = cria Thread (Mesa)

   Th1.inicia (F1)
   Th2.inicia (F2, F4)
   Th3.inicia (F3, F5)

2. Th1.inicia ( … )

Th2.inicia ( … ) e Th3.inicia ( … )

   VarMutex.lock ( )
   P1.inicia ( )

   enquanto P1.ativo ( ) {
      dorme ( )
   }

   VarMutex.unlock ( )

   VarMutex.lock ( )
   P1.inicia ( )
   P2.inicia ( )

   enquanto P1.ativo ( ) ou P2.ativo ( ) {
      dorme ( )
   }

   VarMutex.unlock ( )

3. Objeto “Filósofo”  herda Thread [ Filosofo.inicia ( ) ]

      pega ( )
      come ( )
      lava ( )
      devolve ( )

Anúncios

Os comentários estão desativados.