Problema do Bar dos Filósofos

Problema do Bar dos Filósofos

drinking_philosopher
O Problema do Bar 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 acesso a recursos compartilhados com exclusão mútua.

Problema do Jantar dos Filósofos

Antes de descrever o problema do Bar 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 simultaneamente. 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, o Bar dos Filósofos,  mostrado a seguir.

Problema do Bar dos Filósofos

A principal diferença nesse problema é o grafo de modelagem, 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: tranquilocom sede e bebendo, semelhante aos estados filosofando, 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 do Bar dos Filósofos.

Desenvolva uma classe Filósofo que tenha 3 estados nesta sequencia: tranquilocom 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 2 até n (número de arestas adjacentes ao vértice). As arestas representam o recurso compartilhado (garrafa) e tem acesso em exclusão mútua. 

Utilize os seguintes tempos: Tempo tranquilo: de 0 a 2 segundos (escolhido aleatoriamente)Tempo com sede: tempo 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 Filósofos


/* Jantar do Filosofos */
0, 1, 0, 0, 1,   //vértice 0
1, 0, 1, 0, 0,   //vértice 1
0, 1, 0, 1, 0,   //vértice 2
0, 0, 1, 0, 1,   //vértice 3
1, 0, 0, 1, 0,   //vértice 4


Exemplo 2: Grafo 6 nós com baixa conectividade (máx 3 arestas por nó)
ligth graph

/* Grafo 6 nós baixa conectividade */
0, 1, 0, 0, 0, 1,  //vértice 0
1, 0, 1, 0, 0, 0,  //vértice 1
0, 1, 0, 1, 0, 1,  //vértice 2
0, 0, 1, 0, 1, 1,  //vértice 3
0, 0, 0, 1, 0, 1,  //vértice 4
1, 0, 1, 1, 1, 0,  //vértice 5


Exemplo 3: Grafo 12 nós com alta conectividade  (máx 6 arestas por nó)
dense graph


/* Grafo 12 nós alta conectividade */
0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,  //vértice 0
1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,  //vértice 1
1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,  //vértice 2
0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0,  //vértice 3
1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0,  //vértice 4
0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0,  //vértice 5
0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0,  //vértice 6
0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0,  //vértice 7
0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1,  //vértice 8
0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1,  //vértice 9
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,  //vértice 10
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0,  //vértice 11


Cada filósofo deve beber 6 vezes para os exemplos 1 e 2 e deve beber 3 vezes para o exemplo 3 (uma simulação deve demorar pouco mais de 2 minutos).

Ao final da execução mostrar os tempos de cada filósofo 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 para ver a starvation.

Será considerado correto o programa que não apresentar deadlock durante a execução e os tempos médios de espera dos filósofos seja equilibrada (não houve starvation). 

Dica

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




Comments