Redes de Petri 101
Redes de Petri 101
No artigo sobre autômatos finitos, foi dito que eles são bastante "burros". É difícil enfiar sistemas complexos na cabecinha deles. Um exemplo foi a "Bomba ABC". Esta questão ficou me incomodando, depois que terminei o artigo anterior, o que me levou a soprar as brasas da memória e relembrar as redes de Petri.
A rede de Petri é um formalismo bem mais poderoso que o autômato finito, e consegue manter-se bastante simples para desenhar e interpretar.
Novamente, eu gostaria de fazer uma propaganda mais convincente nesta altura do texto, mas preciso introduzir alguns conceitos antes, prometo que demonstro a utilidade deles mais à frente!
Temos abaixo um autômato finito bastante simples, e a rede de Petri equivalente. Numa rede de Petri, os lugares (também chamadas de estados em algumas literaturas) são representados por círculos, as transições são retângulos ou retas. As setas (arcos) conectam transições e lugares.
A grande diferença da rede de Petri é a ficha, aquela bolinha dentro do lugar inicial. Cada transição "come" uma ficha (ou várias) na entrada, e "cospe" uma ficha (ou várias, ou nenhuma) na saída. Se o número não for especificado, é uma ficha por arco.
Se uma transição possui entradas, como é o caso de todas no exemplo acima, ela só está habilitada a disparar quando há fichas para "comer".
A localização das fichas na rede é denominada marcação e representa o estado geral da rede, analogamente ao estado do autômato finito. (Por isso é melhor chamar os círculos de "lugares", porque chamá-los de "estados" cria uma certa ambiguidade. Num autômato finito apenas um estado pode ser o estado atual, enquanto numa rede de Petri pode haver fichas em diversos estados, digo, lugares.)
Ainda no exemplo acima, há um retângulo oco e um pintado. Isto já é uma extensão da rede de Petri original, que pessoalmente acho muito útil. O retângulo oco representa uma transição que depende de um evento externo para disparar (além de exigir a ficha de entrada). Já o retângulo preto, também representado como um simples traço, é uma transição que dispara assim que a(s) ficha(s) de entrada esteja(m) disponível(is). Em autômatos finitos, até onde sei, não existe uma forma padronizada de distinguir entre estes dois tipos de transição.
A rede do primeiro exemplo "morre" em apenas dois lances. Uma vez que a ficha cai no estado final, não pode mais sair. A rede a seguir, embora elementar, está sempre "viva":
Note os dois retângulos ocos — indica que a mudança de estado em qualquer direção depende de dois eventos externos, sem o que ela nunca dispara.
Já a rede a seguir é essencialmente um loop infinito que nunca cessa de trabalhar, porque as transições só precisam de uma ficha para disparar:
O exemplo a seguir mostra uma rede de Petri com marcação antes e depois do disparo. (Copiei este exemplo da Wikipedia, caso veja algo similar por lá.) Note a presença dos pesos na transição, que exige 3 fichas para disparar, e emite apenas 2.
Até agora não exploramos a principal vantagem da rede de Petri que é a representação de concorrência. Para haver concorrência é preciso haver mais de uma ficha, que é o caso dos exemplos equivalentes abaixo.
(Peço ignorar o número circulado em azul, a ideia era colocar diversos casos numa única figura e referenciar por esse número, mas no fim acabei preferindo cortar em pedaços.)
Em ambas as redes acima, a transição final só pode disparar quando há duas fichas no estado intermediário, e cada uma das fichas só pode mover-se para lá quando acontecer um certo evento. O ponto é que cada ficha move-se de forma independente da outra. Para conseguir fazer a mesma coisa com um autômato finito, precisaríamos de cinco estados e uma verdadeira macarronada de setas.
As redes acima também implementam uma condição "AND": a transição final só acontece se as outras duas também acontecerem. Por outro lado, a rede abaixo implementa uma condição "OR":
Uma transição não precisa necessariamente "comer" ou produzir fichas. Pode haver transições puramente produtoras ou consumidoras de fichas. Vide o exemplo abaixo, não muito útil, mas interessante por disparar de forma "sincopada":
Ok, acho que já basta de teoria teórica. Já podemos brincar com alguma "teoria prática".
Vou reintroduzir uma versão simplificada do diagrama de estados do quiosque, desenvolvido no artigo sobre autômatos finitos.
Conforme o artigo original, este autômato tem um problema sério. Tanto o timeout da consulta quanto a impressora podem solicitar a mudança para o estado PARADO, porém a impressora só deveria fazer isso se estava IMPRIMINDO, e o timeout só poderia disparar se estava CONSULTANDO. Não queremos que a impressora cancele uma consulta, e muito menos que o final de uma consulta cancele uma impressão.
Mas um autômato finito não verifica "de onde vem", mas apenas "para onde vai". Também não quer saber "quem" disparou a transição. Claro, sempre podemos fazer estas verificações no código, mas isto negaria a vantagem de usar um autômato. Queremos que nosso código ande nos trilhos sem que exija esforço de nossa parte...
O problema descrito acima é fácil de resolver com a adição de pseudo-estados no autômato:
O autômato acima evita transições indesejadas, porque a impressora só tentará mudar o estado para IMPRIMIU, e o único jeito disso acontecer é se já estivermos no estado IMPRIMINDO. O mesmo vale para a sequência CONSULTA-CONSULTOU. Assim que o estado chega em IMPRIMIU ou CONSULTOU, vai direto a PARADO sem esperar por evento externo.
Agora, vamos modelar o quiosque com a rede de Petri:
À primeira vista, esta rede é mais parecida com o primeiro autômato, que sabemos problemático. Porém, o problema descrito antes não pode acontecer aqui, pois a transição precisa retirar a ficha para disparar — e isto equivale a verificar o estado anterior. Por exemplo, o evento IMPRESSORA só pode mudar o estado para PARADO se a (única) ficha estiver em IMPRIMINDO. Sem ficha, o evento é ignorado, como deve ser.
O exemplo acima foi inventado para ilustrar o artigo, mas tenho um exemplo real, uma situação que enfrentei recentemente. No meu app de fotometria, preciso pedir autorização para usar a câmera. No Android, o app pode (mas nem sempre vai) ser pausado durante o diálogo de autorização, e o app não pode mexer na UI enquanto estiver pausado. Além disso, o callback de autorização pode acontecer antes do app voltar da pausa. O resultado é um autômato finito relativamente complicado:
A complicação advém do fato de haver duas atividades concorrentes: o callback da solicitação de autorização, e a possível pausa e reinício do app. Considerando todas as possibilidades, a execução pode tomar três caminhos diferentes, e o autômato finito precisa conhecer todos. E ainda fica aquele grilo: talvez um celular Android obscuro provoque um caminho de execução imprevisto, deixando meu autômato em coma e um usuário insatisfeito.
O mesmo processo é modelado de forma mais simples e clara usando rede de Petri:
O evento de solicitação produz duas fichas. Uma delas depende do callback para ir adiante. A outra já fica na marca do gol, mas é "escondida" se o celular entrar em pausa. A transição terminal só dispara quando ambas as condições são atendidas: app ativo e autorização respondida. Mas não importa em que ordem isto aconteça.
Finalmente, segue o exemplo de rede de Petri da "bomba ABC", cujo autômato era um verdadeiro espaguete. Para a bomba disparar, três botões (A, B, C) devem ser pressionados em qualquer ordem, mas apenas uma vez.
Note que usamos uma única transição bidirecional por botão, o que funciona numa rede de Petri porque a ficha só deixa uma direção habilitada por vez.
Podemos ainda usar uma "rede de Petri colorida", uma extensão que admite fichas de tipos ou "cores" diferentes. A transição final (que explode a bomba) não pede mais 3 fichas quaisquer, mas sim uma vermelha, uma azul e uma verde.
A bomba ABC é um exemplo simples demais para tirar proveito real de fichas coloridas. Ainda assim, foi possível enxugar bastante o grafo, diminuindo de 7 para 3 lugares.
No artigo sobre autômatos finitos, mostrei uma extensão bastante comum em implementações reais, que é a transmissão de um "contrabando" de dados juntamente com a transição de estado. O mesmo pode ser feito numa implementação real de rede de Petri. Na verdade fica bem mais legítimo, porque existe a figura da ficha, e é natural pensar que esta ficha carregue dados dentro dela. O conceito fica bem poderoso quando pensamos em fichas coloridas, que poderiam ser associadas a diferentes tipos de dados. O formalismo passa a representar não só uma máquina de estado mas também um fluxo de dados.
Por último, vale relembrar o que já foi dito no final do artigo sobre autômatos finitos. Além de diminuir o espaguete de código e forçar o desenvolvedor a pensar um pouco antes de sair programando, o uso de formalismos permite o uso de bibliotecas prontas, geradores de código e verificadores automáticos de consistência.