Problema da Bebida dos FilósofosO Problema da Bebida dos Filósofos, também conhecida como Drinking Philosophers Problem é uma generalização do problema clássico do Jantar dos Filósofos, proposto por E.W. Dijkstra em 1971. Esse problema é emblemático na área da computação pois pode representar praticamente todos os problemas de programação concorrente em um único exemplo. Mas o principal objetivo é demostrar o controle de acessa a recursos compartilhados com exclusão mútua. A descrição do Problema do Jantar dos Filósofos é bastante restrita. O problema se resume um grafo em ciclo, onde cada processo sempre precisa de recursos ao seu lado para executar sua seção crítica. Em 1984 , Chandy e Misra apresentaram uma generalização deste problema: Problema da Bebida dos Filósofos. O trabalho prático consiste em escrever um programa em C, C++, Java ou Python para simular o problema de Bebida dos Filósofos. Desenvolva uma classe Filósofo que tenha 3 estados nesta sequencia: tranqüilo, com sede e bebendo. O filósofo, ao passar de tranquilo para com sede, deve-se sortear o número de garrafas requeridas, podendo variar de 1 até o número de arestas adjacentes ao vértice. As arestas representam o recurso compartilhado (garrafa) e tem acesse em exclusão mútua. Utilize os seguintes tempos: Tempo tranquilo de 0 a 3 segundos (escolhido aleatoriamente). Tempo com sede até conseguir todas as garrafas. Tempo bebendo 1 segundo. Após beber todas as garrafas, o filósofo retorna a tranquilo. Dado um grafo G = (V, E), é possível representar G através de M, uma matriz quadrada de ordem V, onde Mij = 1 se o vértice i possuir uma aresta ao vértice j, ou Mij = 0 caso contrário. O programa deve ser capaz de ler um arquivo .txt onde cada linha do arquivo representa uma linha de M e cada caractere da linha assume os valores 0 ou 1, indicando as adjacências entre vértices. Considere que o índice de cada caractere nas linhas representa o n-ésimo vértice de G, ou seja, uma coluna de M. É indicado que o programa receba como argumento o local do arquivo contendo a matriz de adjacências. Utilize os seguintes grafos e arquivos da matriz de adjacênciaExemplo 1: Problema Jantar dos Filosofos /* Jantar do Filosofos */ 01001 //vértice 0 10100 //vértice 1 01010 //vértice 2 00101 //vértice 3 10010 //vértice 4 Exemplo 2: Grafo 6 nós baixa conectividade /* Grafo 6 nós baixa conectividade */ 010010 //vértice 1 101010 //vértice 2 010100 //vértice 3 001011 //vértice 4 110100 //vértice 5 000100 //vértice 6 Exemplo 3: Grafo 6 nós alta conectividade /* Grafo 6 nós alta conectividade */ 011110 //vértice 1 100011 //vértice 2 100000 //vértice 3 100010 //vértice 4 110101 //vértice 5 010010 //vértice 6 Cada filósofo deve beber 5 vezes (uma simulação deve demorar pouco mais de 2 minutos). Ao final da execução mostrar os tempos de cada filosofo levou em cada estado (tranquilo, com sede e bebendo). Tempo total para execução e tempo de espera (com sede) médio de cada filósofo. Será considerado correto o programa que não apresentar deadlock durante a execução e os tempos médios de espera dos filosofos seja equilibrada (não houve starvation). DicaSugerimos dar uma leitura em alguns artigos que propõe soluções para esse problema: The Drinking Philosophers Problem de Chandy e Misra An Efficient Solution to the Drinking Philosofers Problem and its Extensions de Ginat, Shankar e Agrawala |