Trabalho Prático 2015.1: Bebida dos Filósofos

Problema da Bebida dos Filósofos

O 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.

Antes de descrever o problema de Bebida dos Filósofos, vamos descrever o Problema do Jantar dos Filósofos: Cinco filósofos se reúnem para jantar e conversar em uma mesa redonda com um garfo colocado sobre a mesa entre cada um deles. Como discutir problemas relacionados filosofia é um exaustivo, eles precisam comer de vez em quando. A fim de fazer isso, um filósofo requer o garfo da esquerda e o da direita, que são compartilhados com os colegas da  esquerda e da direita, respectivamente. Depois de um filósofo comer, os dois garfos são colocado de volta na mesa, possibilitando que outro filósofo possa pegar os garfos e iniciar o jantar. É importante notar que um filósofo deve possuir ambos os garfos, caso contrário, ele não pode comer nada. Devido ao fato de que há apenas cinco garfos e cada filósofo precisa de dois deles para comer, é óbvio que, no máximo, dois filósofos pode comer em paralelo. Uma solução para este problema tem de garantir que vários filósofos possam comer ao mesmo tempo. Além disso, deadlocks (impasses) e starvation (fome) devem ser evitados.
https://sites.google.com/a/larces.uece.br/marcial/cursos/programacao-concorrente-e-paralela-2015-1/trabalho-pratico-2015-1-bebida-dos-filosofos/jantar_filosofos.PNG

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.

A principal diferença nesse problema é o grafo, que ao contrario do grafo circular do jantar dos filósofos, agora temos um grafo genérico. Nenhuma restrição é feita para a estrutura grafo, como distribuição ou grau de conectividade. Os filósofos (processos) são representados pelo nós (vértices) do grafo enquanto as garrafas (recursos compartilhados) são representados pelas arestas do grafo. A generalização é focada em dois pontos: (1) a estrutura do grafo é arbitrária, e, (2) o número e conjunto de garrafas requeridas podem variar. Em cada rodada, cada processo escolhe um subconjunto de suas garrafas adjacentes para esta sessão de bebida. Este subconjunto escolhido não têm necessariamente de ser a mesma em cada sessão de bebida. Se o filósofo escolher todas as garrafas adjacentes em um grafo circular, podemos simular o problema do jantar dos filósofos. Os estados dos filósofos pode ser: tranqüilo, com sede e bebendo, semelhante aos estados pensando, com fome e comendo no problema do jantar dos filósofos. Cada filósofo pode requerer no mínimo uma e no máximo n garrafas, sendo n o número de arestas associadas a cada vértice. 

Descrição da Implementação

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üilocom 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ência

Exemplo 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). 

Dica

Sugerimos dar uma leitura em alguns artigos que propõe soluções para esse problema:





Comments