Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
Ferramentas de Modelação e Análise de Sistemas baseadas em
Redes de Petri (RdP)
Existem inúmeras ferramentas (software) baseadas em RdP que permitem desenvolver modelar e
analisar sistema de RdP. Algumas destas ferramentas suportam funcionalidades como:
verificação automática de propriedades do modelo; hierarquização do modelo, simulação temporal
e até mesmo geração automática de código.
As ferramentas mais avançadas são comerciais. Existem, no entanto, algumas de utilização livre,
que embora limitadas, possuem funcionalidades interessantes. Destacamos as seguintes:
CPNTOOLS - Computer Tool for Coloured Petri Nets
http://wiki.daimi.au.dk/cpntools/cpntools.wiki
PIPE2 - Platform Independent Petri Net Editor 2
http://pipe2.sourceforge.net/
HPSim
http://home.arcor.de/henryk.a/petrinet/e/hpsim_e.htm
Pelas funcionalidades suportadas e pela sua facilidade de utilização, vai ser utilizado o HPSim
nesta aula prática.
HPSim
O HPSim tem algumas características relevantes:
1. Suporta RdP temporizadas e estocásticas
No HPSim podemos associar “atrasos de disparo” às transições (propriedade do
objecto transição). Uma transição temporizada só dispara depois de passado o tempo
especificado contado a partir do momento em que a transição passou a estar
habilitada. Quando o tempo que especificamos é um número constante, temos uma
rede temporizada; quando o tempo especificado é de acordo com uma determinada
distribuição, então a rede é dita estocástica.
É importante referir que no HPSim a contagem de tempo para o disparo de uma
transição é feita desde o instante em que a transição é habilitada, independentemente
do instante em que uma determinada marca “entrou” na posição anterior à transição.
2. Arcos inibidores
Um arco inibidor é utilizado para impedir o disparo de uma transição quando a posição
anterior contém marcas.
3. Arcos de teste
Um arco de teste é obrigatoriamente utilizado para fazer uma “leitura” de uma posição.
4. Limitação do número máximo de marcas em cada posição
Por omissão, cada posição apenas pode ter uma marca (capacidade limitada a 1).
Esta propriedade pode ser alterada para aumentar a capacidade da posição.
5. Simulação gráfica com saída para ficheiro
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 1/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
Podemos acompanhar graficamente a evolução da marcação da RdP ao longo do
tempo. Adicionalmente, é possível gravar esta evolução num ficheiro que pode ser
analisado por um programa externo.
Exercícios
1.
Rede Simples
Admita um conjunto de quatro nós de rede. Em cada nó são geradas mensagens periodicamente.
Essas mensagens são colocadas numa fila (única em cada nó) de mensagens (com capacidade
máxima 20) para serem enviadas via rede de comunicações. Apenas uma mensagem é
transmitida de cada vez. Uma mensagem demora 2 unidades de tempo a ser transmitida.
a) Modele o sistema descrito.
Resposta:
b) Utilizando o modo de simulação verifique o que acontece quando cada um dos nós gera
uma mensagem em cada 10 unidades de tempo. E quando geram uma mensagem em
cada 5 unidades de tempo?
Resposta: Com 5 unidades de tempo, as filas de mensagens esgotam.
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 2/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
2.
Balanceamento de carga
Um servidor recebe pedidos de páginas web. A responsabilidade deste servidor é distribuir estes
pedidos entre um conjunto de quatro máquinas que vão efectivamente responder a estes pedidos.
Não existe estado entre os vários pedidos.
O balanceamento é feito em “round-robin”: o primeiro pedido vai para a primeira máquina, o
segundo para a segunda, e assim sucessivamente. Quando um pedido for enviado para o último
servidor, passa novamente para o primeiro.
Considere que chega um novo pedido periodicamente, todas as 5 unidades de tempo e que cada
servidor demora 10 unidades de tempo para gerar a página de resposta.
a) Modele o sistema descrito.
Resposta:
b) Utilizando o modo de simulação, determine a cadência máxima (periodicidade mínima dos
pedidos) suportada pelo sistema?
Resposta: 3 unidades de tempo.
c) Suponha que tem de suportar uma cadência de um novo pedido em cada 2 unidades de
tempo. Quantos servidores (se algum) necessita adicionar para suportar esta cadência?
Resposta: 1 servidor.
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 3/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
3.
Rede Token Passing
Admita um conjunto de quatro nós de rede. Em cada nó são geradas mensagens periodicamente.
Essas mensagens são enviadas via rede de comunicações. Apenas uma mensagem pode ser
transmitida de cada vez.
O controlo de acesso ao meio da rede de comunicações é do tipo (token passing): um nó só pode
enviar mensagens quando possui o token. O token circula entre os nós em round-robin (anel
lógico). Quando na “posse” do token, um nó pode enviar no máximo uma mensagem (se a fila não
estiver vazia). Depois, o token é passado ao nó seguinte no anel lógico.
a) Modele o sistema descrito. Assuma que a transmissão de uma mensagem demora 2
unidades de tempo, e que a passagem do token demora 1 unidade de tempo. Em cada nó,
é gerada uma mensagem a cada 50 unidades de tempo.
Resposta:
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 4/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
b) Altere o modelo desenvolvido na alínea a) para considerar que cada nó pode enviar mais
do que uma mensagem (número máximo definido para cada nó da rede).
Resposta: Basta colocar o número de mensagens pretendido em cada nó como peso do
arco anterior à posição onde é verificada a fila de mensagens (depois da transição de
chegada do testemunho ao nó) e no arco anterior à passagem do token. A figura seguinte
exemplifica no Nó 1, que poderá enviar até 2 mensagens por visita do token:
c) Altere o modelo desenvolvido para a alínea a) para considerar que cada nó possui três
filas com prioridades diferentes, e que é enviada uma mensagem (se existir) respeitando
as prioridades das filas.
Resposta: O raciocínio para o modelo é o mesmo. Agora temos mais duas filas de
mensagens. Quando o nó possui o token, verifica as filas por ordem da sua prioridade. Se
alguma das filas contém uma ou mais mensagens, então envia uma mensagem dessa fila.
A figura seguinte ilustra o modelo para o Nó 1:
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 5/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
4.
Base de dados
Uma base de dados cria processos que acedem a uma tabela. Os processos podem ter dois
estados: escrita e leitura.
As operações de leitura e escrita são exclusivas; Quando temos um leitor a aceder à tabela,
nenhum escritor pode aceder a esta e vice-versa.
São permitidos vários leitores ao mesmo tempo, mas por restrições do sistema, apenas podemos
ter um máximo de cinco leitores a aceder à tabela em simultâneo. Quanto a escritores, apenas
podemos ter um de cada vez.
Depois de uma análise à base de dados e aplicação que a utiliza, chegou-se à conclusão que
apenas podem existir em simultâneo um máximo de 50 processos pendentes para ler e 10
pendentes para escrever.
Nota: Este exercício foi feito durante a aula teórico-prática. No entanto a sua modelação em
HPSim requer uma ligeira alteração.
a) Modele o sistema descrito. Assuma que uma operação de escrita demora 5 unidades de
tempo e uma leitura 1 unidade de tempo.
Resposta: A diferença relativamente à solução da aula TP é que em HPSim temos de
separar as operações de leitura para que o tempo para esta operação seja correctamente
modelado:
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 6/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
5.
Base de dados distribuída
Uma base de dados cria processos que acedem a uma tabela. Os processos podem ter dois
estados: escrita e leitura.
As operações de leitura e escrita são exclusivas; isto é, quando existe um leitor a aceder à tabela,
nenhum escritor pode aceder a esta e vice-versa. São permitidos vários leitores ao mesmo tempo,
mas por restrições do sistema, apenas podemos ter um máximo de três leitores a aceder à tabela
ao mesmo tempo. Quanto a escritores, apenas podemos ter um de cada vez.
Quando é efectuada uma escrita, esta deve ser propagada pelos outros servidores. Para isso, os
servidores enviam uma mensagem difundida para todos os outros servidores com a actualização.
Nesta altura o processo fica num estado de espera até que todos os outros servidores confirmem
a actualização. As mensagens e confirmações são enviadas através da rede. Esta apenas pode
ser acedida por um servido de cada vez.
Depois de uma análise à base de dados e aplicação que a utiliza, chegou-se à conclusão que
apenas podem existir em simultâneo um máximo de 50 processos tentar efectuar leituras e 10 a
tentar escrever.
O sistema já se encontra modelado. Para tentar manter o modelo relativamente simples, não foi
efectivamente implementado nenhum dos protocolos típicos para resolver este tipo de problemas
como o Two-phase commit protocol.
Vamos então explorar o modelo implementado. Neste modelo, temos a mesma RdP replicada
para cada nó, assim começamos por analisar a RdP de um nó. A base para o modelo é o
exercício anterior. Continuamos a ter vários leitores que podem efectuar leituras da tabela e
escritores que acedem em exclusivo à tabela:
No que diz respeito à leitura, a única diferença é que apenas pode haver três leitores em
simultâneo. Quanto à escrita, há um bloco para modelar; este bloco diz respeito à escrita,
envio da respectiva mensagem de actualização para outros servidores e espera da
confirmação por parte dos outros. Vejamos como este bloco poderia ser modelado:
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 7/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
A modelação apresentada é relativamente simples. Depois de se garantir o acesso exclusivo à
tabela local, é efectuada a escrita, e de seguida é enviaa a mensagem de actualização e
modelada a espera da(s) confirmação(confirmações). As posições “TO_REMOTE” e
“CNF_FROM_REMOTE” são posições de ligação ao(s) outro(s) nós. Quando o modelo
completo for apresentado veremos melhor o seu significado.
Falta agora modelar a resposta às mensagens de actualização recebidas de outros servidores:
A posição “PEDE_E_REMOTA” modela a recepção de um pedido de actualização (escrita)
remoto e a posição “CNF_TO_REMOTE” o envio da confirmação para o servidor remoto. O
modelo para dois nós apresentado de seguida permite dá uma melhor intuição do modelo.
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 8/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
No entanto, este modelo reflecte erros de concepção.
a) Efectue uma simulação do sistema. Consegue identificar o problema?
Resposta: Neste modelo pode acontecer que os dois nós iniciem uma escrita
independentemente. Nesse caso, ambos ficarão bloqueados à espera da confirmação. É
necessário implementar um coordenador (global) que garanta, de forma distribuída, um
acesso exclusivo à escrita.
O modelo corrigido é apresentado na página seguinte.
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 9/10
Computação Avançada
Aula Prática
Módulo I - Modelação e Análise de Sistemas Computacionais
b) Neste modelo falta ainda modelar o acesso à rede, que é um recurso partilhado entre os
nós. Implemente, no modelo, o acesso à rede.
COMPA, Módulo 1, Prática
Nuno Pereira, Eduardo Tovar
Pág. 10/10