O Jantar dos Filósofos

ADS 2010-2 Trabalho 2

Ângelo Marcos Rigo

Clauter Gatti

Gabriel José da Silva Oliveira

{angelo.rigo@gmail.com, clauter_gatti@dell.com, gabriel.oliveira@acad.pucrs.br}

Faculdade de Informática – PUCRS

90619-900  -  Porto Alegre – RS – Brasil

23 de novembro de 2010

Sumário

Introdução        2

Modelo Básico Utilizando Funções        3

Resultado Obtidos        4

Probabilidade de Cada Filósofo estar Pensando, Esperando e Comendo        6

Média de Filósofos Esperando pelos Garfos        7

Média de Filósofos Comendo        8

Análise da Probabilidade da Média de Filósofos Esperando pelos Garfos        9

Prova de que Dois Filósofos Vizinhos Nunca Comem ao Mesmo Tempo        11

Execução do Modelo sem Prevenção de Deadlock        12

Conclusão        16

Introdução

Este exemplo descreve o “Jantar dos Filósofos”, um problema clássico de sincronização entre processos simultâneos. Supõe-se que existem cinco filósofos em torno de uma mesa. Nesta mesa encontram-se apenas cinco garfos e cinco pratos de massa. A vida de um filósofo consiste em pensar e comer. Porém, para comer, cada filósofo necessita de dois garfos. Assim, se um filósofo está comendo, seus dois vizinhos não podem comer. A disposição dos filósofos e dos garfos na mesa ficará como segue (Figura 1):

[pic 1]

Figura 1 -  Problema do Jantar dos Filósofos.

Neste problema são cinco filósofos, e estes serão representados por cinco autômatos chamados de F, contendo três estados cada um: pensar (P), segurar o garfo direito (D) e segurar o garfo esquerdo (E). A modelagem supõe que para comer, um filósofo necessita efetivamente estar com dois garfos em mãos e, logo depois, voltar a pensar liberando os dois garfos. A alternativa de modelagem que será mostrada, a seguir, sugere uma solução utilizando funções. Contudo considerou-se que quando um filósofo estiver com os dois garfos em mãos, o tempo que o mesmo leva para libera-los já pressupõe o tempo gasto comendo, não necessitando então modelar mais um estado.

Exite um problema que ocorre quando dois filósofos vizinhos ficam com fome e tentam pegar o mesmo garfo para comer. Esta situação remonta o que ocorreria com dois processos concorrentes que querem utilizar um mesmo recurso; se a sincronização não for resolvida, estes processos poderão ficar em espera infinita, um pelo outro, situação conhecida como deadlock. Para solucionar este problema, na modelagem dos autômatos dos filósofos estabelece-se um filósofo “canhoto” que, ao contrário dos outros, segura primeiro o garfo à sua esquerda e após o da direita.

As taxas que descrevem o tempo gasto pelos filósofos em cada um de seus possíveis estados são as seguintes:

• cada filósofo demora 10 u.t. (unidades de tempo) para segurar cada um dos garfos que necessita, respectivamente;
• um filósofo passa 4 u.t. comendo e, logo depois, solta os garfos e volta a pensar;
• um filósofo fica com fome após 1 u.t. pensando.

Modelo Básico Utilizando Funções

A alternativa para a modelagem deste problema é a utilização de taxas funcionais em cada transição, onde cada filósofo será representado por um autômato. A Figura 2 mostra a representação gráfica desta abordagem:

[pic 2]

Figura 2 - Modelagem Alternativa para o Jantar dos Filósofos.

As taxas funcionais definidas abaixo garantem que os filósofos só poderão comer se seus vizinhos não estiverem comendo.Vejamos como estas funções foram descritas textualmente para os filósofos no formato SAN (Tabela 1):

Tabela 1 - Funções para as Transições dos Autômatos dos Filósofos.

A função de atingibilidade definida garante que quando um filósofo estiver comendo (no estado E, ou no D no caso de F5), os seus vizinhos não podem estar comendo também. Na Figura 3, podemos observar a função de atingibilidade definida para este problema:

[pic 3]

Figura 3- Função de Atingibilidade para o “Jantar dos Filósofos”.

Na próxima seção serão discutidos os resultados obtidos.

Resultado Obtidos

Vejamos o modelo acima criado na modelagem textual para a ferramenta PERHAPS2009:

// ================ *** Jantar dos Filosofos *** ================

//  Modelo Utilizando Funcoes - Evitando Deadlock

// ==============================================================

identifiers

  taxaSegurarGarfo = 10;

  taxaPensando     = 1;

  taxaComendo      = 4;

  fPdp1            = (st F5 == P) * taxaPensando;

...