UFMG - Pós-graduação em Ciência da Computação - Programação Paralela

A seguir: A Solução Higiênica: Preliminares Acima: The Drinking Philosophers Problem[#!Drinking!#] Anterior: O Problema dos Filósofos

O Problema dos Filósofos Famintos

• Caso especial em que o coquetel desejado é sempre composto por todas as garrafas acessíveis
• Estados de um filósofo: pensando, faminto, comendo
• Garrafas passam a ser chamadas de garfos
• Dois vizinhos nunca comem simultaneamente
• Se o grafo de conflitos for completo, temos a exclusão mútua global
• Solução ``higiênica'':
  • um garfo está sujo ou limpo
  • garfos (só) sujam-se ao serem usados para comer
  • garfos (só) são limpos ao serem enviados
  • um filósofo comendo só responde a requisicões ao acabar de comer
  • um filósofo faminto:
    • atende a requisições por garfos sujos
    • adia respostas a requisições por garfos limpos
• Base da solução: representação distribuída do grafo H
• u precede v em H ($u \rightarrow v$) sse

  1.

  u possui f_uv, o garfo compartilhado com v, limpo, ou

  2.

  v possui f_uv, sujo, ou

  3.

  f_uv está em trânsito indo de v para u,

• A situação inicial deve garantir que o grafo formado por estas regras é acíclico