Projeto Final de Redes de Petris (1)

Prévia do material em texto

Universidade Federal de Pernambuco
Departamento de Engenharia Eletrônica e Sistemas
Curso de Engenharia Eletrônica
Disciplina: Redes de Petri
Problema do jantar dos filósofos com Redes de Petri
Lucas Quadros Cavalcanti
Professor: Tomaz de Carvalho Barros
Recife, Agosto / 2024
1. Introdução
O problema do jantar dos filósofos é um exemplo que visa ilustrar de forma fácil
problemas de computação referente a simultaneidade. Este problema descreve um grupo de
filósofos sentados à mesa, podendo estes apenas estar comendo ou pensando. Enquanto
comem, não pensam e, enquanto pensam, não comem. Os filósofos sentam-se em uma
mesa circular, cada um com uma tigela de arroz. Um Hashi é colocado entre cada filósofo,
assim cada filósofo tem um Hashi à sua esquerda e um Hashis à sua direita.
Desta forma, os filósofos só conseguirão comer se possuir os dois hashis, caso não
tenha nenhum ou só tenha um, estará impedido de comer. O filósofo só pode usar o Hashis
à sua esquerda ou direita imediata. Os filósofos nunca falam uns com os outros, o que cria
uma perigosa possibilidade de impasse. Impasse poderia ocorrer se todo filósofo segurasse
um Hashis esquerdo e esperasse perpetuamente por um Hashis direito (ou vice-versa).
Originalmente usado como meio de ilustrar o problema do impasse, este sistema
atinge o impasse quando há um ‘ciclo de solicitações injustificadas’. Neste caso o filósofo P1
espera que o Hashis seja agarrado pelo filósofo P2 que está esperando o Hashi do filósofo
P3 e assim por diante, fazendo uma corrente circular.
Já a falta de Hashis disponíveis é uma analogia ao bloqueio de recursos
compartilhados na programação de computadores reais. Bloquear um recurso é uma técnica
comum para garantir que o recurso seja acessado por apenas um programa ou parte de um
programa por vez. O desafio ocorre quando existem múltiplos recursos que devem ser
adquiridos individualmente.
Quando vários programas estão envolvidos no bloqueio de vários recursos, pode
ocorrer um conflito. Por exemplo, o programa precisa de dois arquivos para processar.
Quando dois desses programas bloqueiam um arquivo cada, ambos os programas
aguardam o outro para desbloquear o outro arquivo, o que nunca acontecerá.
Figura 1 - Exemplo do Jantar dos filósofos (Noodles foi dito como arroz e
Chopstick como Hashi)
2. Desenvolvimento
2.1. Redes Petri
A Rede de Petri, foi desenvolvida por Carl Adam Petri em 1962 e a qual deu origem
ao SFC (Sequential Function Charts), sendo esta uma ferramenta gráfica e matemática
poderosa para a modelagem e análise de Sistemas de Eventos Discretos (SEDs). Essa
técnica é amplamente utilizada para descrever e investigar sistemas com características
como concorrência, assíncronia, distribuição, paralelismo, não determinismo e/ou
estocasticidade. Em sua função gráfica, as Redes de Petri auxiliam na comunicação visual,
na simulação de gráficos de fluxo, e na criação de diagramas de blocos e redes. Sua
modelagem, termina por facilitar o entendimento do problema a ser analisado, possibilitando
a simplificação deste.
Uma Rede de Petri é um grafo direcionado, ponderado e bipartido, constituído por
dois tipos principais de elementos: lugares e transições. Os lugares são representados por
círculos, enquanto as transições são indicadas por barras. Estes elementos estruturais são
conectados por arcos orientados, que ligam lugares a transições e transições a lugares. Os
arcos podem ter rótulos com valores inteiros positivos, que representam seu peso; um arco
com peso k pode ser interpretado como k arcos paralelos, como mostrado na Figura 2. A
ficha determina em que etapa está o processo, possibilitando a análise das mais diversas
possibilidades do sistema atuar.
Figura 2 - Exemplo de Redes de Petri
2.2. Modelando em redes de Petri o problema
Podemos então definir o problema do jantar dos filósofos com representação de
redes de petris. Primeiramente, analisando as possibilidades do problema. Onde cada
filósofo pode estar em apenas um dos dois estados: pensando ou comendo. Desta
forma, temos que as seguintes ações são feitas:
● Pensar: O filósofo não faz nada e libera ambos os garfos.
● Pegar Garfo: O filósofo tenta pegar o garfo à sua esquerda e depois o garfo
à sua direita.
● Comer: O filósofo come quando tem ambos os garfos.
● Largar Garfo: Após comer, o filósofo larga ambos os garfos.
Logo, para facilitar, iremos analisar apenas um filósofo. Modelando este em
redes de Petri. Podemos representar os estados de comendo e pensando do filósofo
como lugares. Além de haver ou não Hashi disponível também como um lugar, com
isto consigo definir minhas transições. Para haver a transição de pensando para
comendo, tenho que ter os hashi em ambos os lados disponíveis. Logo para a
primeira transição, três condições haverá de ser atendida:
1. O filósofo deve estar pensando.
2. Deve haver Hashi a esquerda do filósofo.
3. Deve haver Hashi a direita do filósofo.
Analisando minha última transição, basicamente após comer ele deve devolver
os Hashis ao lugar e voltar a pensar. Com estas informações consigo chegar a um
modelo de redes de Petri para o problema, chegando à Figura 3.
Figura 3 - Modelo de Petri de um filósofo no problema do jantar dos filósofos.
Onde os lugares a e b são a representação dos Hashi, que quando o lugar tiver
com fichas, significa que há Hasi disponível para uso. Já o lugar p1 representa o
filósofo pensando e o lucar c1 o filósofo comendo. Apontando as transições, onde I1
seria a representação da primeira transição definida acima. Por fim, a transição f1
denota o retorno do filósofo a pensar, devolvendo os Hashis. Passando pelas
seguintes fases, mostrado na Figura 4.
Figura 4 - Todas as possibilidades que o filósofo pode passar.
Para os demais filósofos terão o mesmo comportamento, basta agora unir
estes. Para isto, podemos analisar que o ponto compartilhado a rede de Petri. Assim
notamos que os Hashi que são compartilhados entre si, podendo então ser modelado
da seguinte forma.
Figura 5 - União dos modelos de Petri com os lugares externo da rede em
comum.
Apenas restando a união destes para chegar no modelo final, representado
pela Figura 6. Onde cada número seria um filósofo, e os lugares em comum seriam a
interligação deste, como comentado anteriormente. Este problema pode ser
representado com mais filósofos a mesa.
Figura 6- Modelo de Petri final do problema do jantar dos filósofos.
2.3. Construindo um sistema digital do problema a partir do modelo em
Petri
Como as redes de Petri são representação matemáticas do problema.
Podemos representar através de hardware, mais especificamente representar como
circuitos digitais. Onde Flip-Flops SR podem ser utilizados como lugares e portas
lógicas utilizados como transições.
Explicando melhor o funcionamento de Flip-Flop do tipo SR, onde este tipo de
circuito sequencial que tem duas entradas principais e duas saídas. As entradas são
denominadas Set (S) e Reset (R), e as saídas são geralmente rotuladas como Q e Q'
(not Q). Chegando a tabela verdade a seguir:
Tabela 1 - Tabela verdade de um Flip-Flop SR
Já as transições se é interpretada como a porta lógica AND. podendo então
chegar a uma representação básica mostrada na Figura a seguir.
Figura 7 - Modelo de Petri para modelo em Hardware.
Com isso, utilizado a ferramenta CircuitMaker para realizar a simulação do
problema. Podemos modelar o sistema da seguinte forma:
1. Todos os lugares se tornarão Flip-Flops SR.
2. Todas as transições se tornarão portas lógicas AND.
3. Para a transição I1 ocorrer, os Flip-Flops SR que representam os lugares a, b
e p1 tem que ter um nível lógico alto.
4. Para a transição f1 ocorrer, o Flip-Flop SR que representa o lugar c1 tem que
ter um nível lógico alto.
5. Os Flip-Flops SR que representam os lugares a, b e p1 são resetados quando
c1 tiver um nível lógico alto.
6. O Flip-Flop SR que representa o lugar c1 será resetado quando a, b e p1 tiver
um nível lógico alto.
S R Q
0 0 Mantém o valor atual
0 1 Q em nível baixo
1 0Q em nível alto
1 1 indefinição
Com estas condições consigo construir o seguinte circuito lógico mostrado na
Figura 8. Onde U2 seria o lugar p1, U3 o lugar c1, U4 o lugar a e U5 o lugar b. Já U1A
e U1B são respectivamente I1 e f1.
Figura 8 - Modelo em Hardware de um filósofo no estado inicial.
Figura 9 - Modelo em Hardware de um filósofo no estado de comendo.
Figura 10 - Modelo em Hardware de um filósofo retornando ao estado inicial.
Com isso, basta unir-se com os demais filósofos, da mesma forma da
modelagem da rede de Petri para o problema. Chegando então ao seguinte circuito lógico.
Figura 11 - Modelo em Hardware de todos os filósofos.
3. Conclusão
O problema do Jantar dos Cinco Filósofos é um exemplo clássico de problemas de
sincronização e concorrência, frequentemente utilizado para ilustrar os desafios envolvidos
na gestão de recursos compartilhados e evitar situações de deadlock.
Ao modelar este problema usando Redes de Petri, podemos obter uma visão clara e
formal sobre como os filósofos interagem com os garfos e como essas interações podem
ser geridas de maneira a garantir que todos possam comer sem que o sistema entre em um
estado de impasse.
O estudo do problema do jantar dos filósofos através de Redes de Petri demonstra a
eficácia desta ferramenta na análise e modelagem de problemas de concorrência. A
modelagem oferece uma abordagem clara e estruturada que pode ser aplicada não apenas
a problemas teóricos, mas também a situações práticas em sistemas distribuídos e
ambientes de computação concorrente. A compreensão adquirida através desta modelagem
pode ser valiosa para o desenvolvimento de sistemas robustos e eficientes, ajudando a
prevenir e resolver problemas de sincronização e gerenciamento de recursos em diversos
contextos.
Um dos principais pontos deste problema seria a identificação de deadlock, que seria
um ponto onde o sistema não tem para onde prosseguir, travando todo o resto. Utilizando
Redes de Petri, é possível identificar e evitar condições de deadlock e garantir a segurança
do sistema. As redes permitem a análise de estados alcançáveis e a validação de que o
sistema pode progredir para uma condição onde todos os filósofos possam eventualmente
comer sem que um ciclo de espera interminável ocorra.
Por fim, a utilização da ferramenta do CircuitMaker para simular o sistema
encontrado, passei por problemas para implementar a lógica correta, pois desta forma atual
eles atuam ao mesmo tempo. Não havendo conflito entre estes para acessar o mesmo
Hashi. O que terminou por sempre funcionar de forma simultânea todos os filósofos.
4. Referências
[1] Redes de Petri. 2023. Disponível em:
<https://edisciplinas.usp.br/pluginfile.php/1881413/mod_resource/content/0/Aula_Redes%20
de%20Petri.pdf> Acesso em: 08 ago. 2024.
[2] Jantar dos Filósofos – Entenda como um Sistema Operacional organiza a disputa de
recursos. 2023. Disponível em:
<https://www.deviante.com.br/noticias/entre-forks-e-segredos/> Acesso em: 08 ago. 2024.
[3] Dining Philosophers Problem. 2012. Disponível em:
<https://lass.cs.umass.edu/~shenoy/courses/fall13/lectures/Lec10_notes.pdf> Acesso em:
08 ago. 2024.
[4] Dining Philosopher Problem Using Semaphores. 2024. Disponível em:
<https://www.geeksforgeeks.org/dining-philosopher-problem-using-semaphores/0> Acesso
em: 08 ago. 2024.