Pontifı́cia Universidade Católica do Rio Grande do Sul
Faculdade de Informática
Pós-Graduação em Ciência da Computação
Um Estudo sobre Redes de Petri
Estocásticas Generalizadas
Afonso Henrique Corrêa de Sales
Orientador: Prof. Dr. Paulo Henrique Lemelle Fernandes
Trabalho individual I
Porto Alegre, agosto de 2002
Resumo
Este trabalho visa estudar um formalismo utilizado para avaliação de desempenho de
sistemas: Redes de Petri Estocásticas Generalizadas. O formalismo de Redes de Petri Estocásticas Generalizadas é derivado do formalismo de Redes de Petri Estocásticas que, conseqüentemente, deriva do formalismo de Redes de Petri. Todos os formalismos são definidos
e exemplificados de uma maneira informal a partir de suas primitivas de modelagem. A conclusão tece como trabalhos futuros a formulação de um relatório técnico contendo a definição
formal dos formalismos de Redes de Petri, Redes de Petri Estocásticas e Redes de Petri
Estocásticas Generalizadas de modo a definir-se inequivocamente suas propriedades de modelagem, bem como o estudo do formalismo de Redes de Petri Estocásticas Generalizadas
Superpostas à vista de uma resolução numérica eficiente e uma eventual comparação com o
formalismo de Redes de Autômatos Estocásticos.
Sumário
LISTA DE TABELAS
ii
LISTA DE FIGURAS
iii
LISTA DE SÍMBOLOS E ABREVIATURAS
iv
Capı́tulo 1: Introdução
1
Capı́tulo 2: Redes de Petri
2.1
2.2
Descrição Informal . . . . .
2.1.1 Marcas . . . . . . .
2.1.2 Regras de Execução
2.1.3 Atingibilidade . . . .
2.1.4 Limitação . . . . . .
2.1.5 Segurança . . . . . .
2.1.6 Vivacidade . . . . .
Exemplo de Modelagem . .
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Capı́tulo 3: Redes de Petri Estocásticas
3.1
3.2
Descrição Informal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo de Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Capı́tulo 4: Redes de Petri Estocásticas Generalizadas
4.1
4.2
Descrição Informal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemplo de Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
4
4
5
6
7
7
7
10
11
15
18
18
25
Capı́tulo 5: Conclusão
28
REFERÊNCIAS BIBLIOGRÁFICAS
30
i
Lista de Tabelas
3.1
Marcações da Figura 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4.1
4.2
4.3
4.4
Switching distribution da GSPN descrita
Marcações da Figura 4.1 . . . . . . . . .
Switching distribution da GSPN descrita
Marcações da Figura 4.6 . . . . . . . . .
20
22
25
26
ii
na Figura
. . . . . .
na Figura
. . . . . .
4.1
. .
4.6
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Lista de Figuras
2.1
2.2
2.3
2.4
2.5
Exemplo de representação gráfica de uma Rede de Petri . . .
Exemplo de uma Rede de Petri marcada . . . . . . . . . . . .
Disparo da transição t1 de uma Rede de Petri . . . . . . . . .
Árvore de atingibilidade da Figura 2.2 . . . . . . . . . . . . .
Compartilhamento de recursos com exclusão mútua - Rede de
. . . .
. . . .
. . . .
. . . .
Petri .
3.1
3.2
3.3
3.4
3.5
3.6
Exemplo de uma Rede de Petri Temporizada . . . .
Exemplo de uma Rede de Petri Estocástica . . . . .
Árvore de atingibilidade da Figura 3.2 . . . . . . . .
Cadeia de Markov equivalente à Figura 3.2 . . . . .
Compartilhamento de recursos com exclusão mútua Árvore de atingibilidade da Figura 3.5 . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
Petri Estocástica
. . . . . . . . .
4.1
4.2
4.3
4.4
4.5
4.6
Exemplo de uma Rede de Petri Estocástica Generalizada [13] . . . . . . . . .
Árvore de atingibilidade caso a Figura 4.1 fosse uma SPN . . . . . . . . . . .
Árvore de atingibilidade da Figura 4.1 . . . . . . . . . . . . . . . . . . . . . .
Cadeia de Markov da Figura 4.1 compreendendo vanishing e tangible markings
Cadeia de Markov da Figura 4.1 somente com tangible markings . . . . . . .
Compartilhamento de recursos com exclusão mútua - Rede de Petri Estocástica
Generalizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Árvore de atingibilidade da Figura 4.6 . . . . . . . . . . . . . . . . . . . . . .
Cadeia de Markov da Figura 4.6 compreendendo vanishing e tangible markings
Cadeia de Markov da Figura 4.6 somente com tangible markings . . . . . . .
4.7
4.8
4.9
iii
. . . . .
. . . . .
. . . . .
. . . . .
Rede de
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
4
5
6
8
10
11
12
13
15
16
19
22
23
23
24
25
27
27
27
Lista de Sı́mbolos e Abreviaturas
PN
SPN
Petri Nets
Stochastic Petri Nets
2
2
GSPN
SGSPN
Generalized Stochastic Petri Nets
Superposed Generalized Stochastic Petri Nets
2
2
SAN
TPN
Stochastic Automata Networks
Timed Petri Nets
2
10
CTMC
Continuous-Time Markov Chains
11
iv
1
Introdução
Através da evolução tecnológica das últimas décadas, o desenvolvimento de sistemas computacionais distribuı́dos e redes de computadores encontra-se em ascendência. Esta crescente
evolução tem exigido o desenvolvimento de ferramentas que permitem a modelagem e análise
do desempenho e confiabilidade dos mesmos. Contudo, este desenvolvimento tem se tornado
cada vez mais complexo, ressaltando assim a importância da área de avaliação de desempenho
de sistemas computacionais [13].
A avaliação de desempenho de sistemas utiliza técnicas que permitem ao projetista de
sistemas analisar como o sistema em questão se comportará, e se a arquitetura utilizada é a
mais adequada às suas necessidades. As técnicas utilizadas em avaliação de desempenho de
sistemas são divididas em três grupos [23]:
• Monitoração;
• Simulação;
• Métodos analı́ticos.
A monitoração baseia-se na observação direta do funcionamento de sistemas reais, enquanto a simulação consiste em construir um modelo que simule o funcionamento de sistemas. Os métodos analı́ticos consistem na construção de modelos analı́ticos que reduzem o
funcionamento de um sistema real a relações matemáticas. Os métodos analı́ticos possuem
uma vantagem em relação as outras técnicas, pois não há uma preocupação com um conjunto
especı́fico de amostras de funcionamento do sistema para a obtenção das medidas de desempenho.
Por reduzirem o funcionamento do sistema a relações matemáticas, os métodos analı́ticos
descrevem o sistema real como um conjunto de estados e transições estocásticas entre os estados. Um processo estocástico 1 é um processo cuja ocorrência é descrita por uma variável
aleatória. Desta forma, os modelos estocásticos são usados para reduzir um problema complexo em um problema de fácil entendimento. O formalismo de modelagem é uma linguagem
alfanumérica ou gráfica para a especificação de modelos [13]. Um formalismo é responsável
pela ausência de ambigüidade no modelo, sendo composto por um conjunto de primitivas e
um conjunto de regras de utilização.
O formalismo de modelagem tem evoluı́do desde 1890 onde iniciaram-se os estudos sobre
Cadeias de Markov [31]. Jackson iniciou o trabalho sobre o formalismo de Redes de Filas de
1
Processo aleatório.
1
Espera no final da década de 50 [9, 10]. No final dos anos 70, este formalismo teve um grande
avanço devido aos trabalhos realizados por Little [11], Baskett, Chandy, Muntz e Palacios [2],
e Reiser e Lavenberg [25].
Entretanto, o formalismo de Redes de Filas de Espera à forma-produto não provê mecanismos de sincronismo e paralelismo, salvo os estudos feitos em G-Networks [7] e Limited
Capacity QN [3]. Conseqüentemente, tal formalismo não possui a precisão necessária para a
descrição de sistemas complexos.
O formalismo de Redes de Petri (PN) [22, 21, 26] surgiu para suprir tais necessidades. Tal
formalismo define uma técnica de especificação de sistemas que possibilita uma representação
matemática e possui mecanismos de análise que permitem a verificação de propriedades e a
verificação da corretude do sistema especificado [12]. As Redes de Petri podem variar desde
simples temporizações constantes [27, 30] até mecanismos mais sofisticados, tais como:
• Redes de Petri Estocásticas (SPN) [6];
• Redes de Petri Estocásticas Generalizadas (GSPN) [15, 14];
• Redes de Petri Estocásticas Generalizadas Superpostas (SGSPN) [4, 5].
Este trabalho tem o objetivo de estudar: Redes de Petri, Redes de Petri Estocásticas e
Redes de Petri Estocásticas Generalizadas. Tal estudo tem como finalidade a formulação de
um texto introdutório - survey - sobre o tema proposto, onde possa-se identificar as bases
de uma futura prova da equivalência do formalismo de Redes de Petri Estocásticas com o
formalismo de Redes de Autômatos Estocásticos (SAN) [24].
No presente trabalho, faz-se uma descrição do formalismo básico de Redes de Petri no
capı́tulo 2. Apresenta-se no capı́tulo 3, a extensão que introduz o conceito de processos estocásticos, as Redes de Petri Estocásticas. A seguir, no capı́tulo 4, descreve-se a extensão
que introduz o conceito de transições imediatas, as Redes de Petri Estocásticas Generalizadas. Por fim, na conclusão, ressalta-se os assuntos estudados e aponta-se futuros trabalhos
envolvendo Redes de Petri Estocásticas Generalizadas Superpostas.
2
2
Redes de Petri
Uma Rede de Petri é uma abstração de um sistema real. Ela é um modelo formal do fluxo
de dados do sistema modelado em questão. As propriedades, conceitos e técnicas para modelagem de uma Rede de Petri foram desenvolvidas utilizando métodos simples e poderosos
para descrição, análise do fluxo de dados e controle de sistema.
O formalismo de Redes de Petri é utilizado principalmente em sistemas que possam
aprensentar atividades assı́ncronas e concorrentes. Redes de Petri têm sido utilizadas principalmente para a modelagem de sistemas de eventos em que estes possam ocorrer concorrentemente, havendo obstáculos na concorrência, precedência ou freqüência desses eventos
[21].
2.1
Descrição Informal
A estrutura de uma Rede de Petri é um grafo bipartido que compreende um conjunto de
lugares P , um conjunto de transições T , e um conjunto de arcos direcionados A. Os lugares
são representados graficamente por cı́rculos, as transições por barras e os arcos direcionados
por setas. Os arcos direcionados conectam os lugares às transições e as transições aos lugares.
p1
p2
t4
t1
p3
t2
p4
t3
t5
p5
t6
Figura 2.1: Exemplo de representação gráfica de uma Rede de Petri
Tem-se, na Figura 2.1, um exemplo da representação gráfica de uma Rede de Petri que
possui 5 lugares e 6 transições.
3
Um lugar é uma entrada para uma transição se existe um arco direcionado do lugar para
a transição em questão. Analogamente, um lugar é uma saı́da de uma transição se existe um
arco direcionado da transição para o lugar em questão.
2.1.1
Marcas
Uma Rede de Petri pode ser considerada marcada quando ela possuir tokens ou marcas. Tokens encontram-se nos lugares. As transições, quando disparadas, consomem tokens
dos lugares que as alimentam e geram marcas nos lugares por elas alimentadas. Tokens são
sinais em uma Rede de Petri representados graficamente por um ponto preto. A quantidade e
a posição dos tokens em uma Rede de Petri podem variar durante o funcionamento da mesma.
Uma Rede de Petri marcada é definida pelo número mn de tokens contidos em cada lugar
pn da rede [13]. Uma marcação Mi de uma Rede de Petri é definida pelo conjunto de mn dos
lugares da mesma, ou seja, a marcação inicial de uma Rede de Petri é M0 = {m0 , m1 , m2 ,
..., mn }.
Na Figura 2.2, tem-se um exemplo de uma Rede de Petri marcada.
p1
p2
t4
t1
p3
t2
p4
t3
t5
p5
t6
Figura 2.2: Exemplo de uma Rede de Petri marcada
2.1.2
Regras de Execução
Uma Rede de Petri é executada através do disparo de transições. Para ocorrer o disparo
de uma transição, é necessário que esta transição esteja habilitada para isto. Uma transição é
considerada habilitada para disparar quando todos os lugares de entrada dela contiverem pelo
menos um token. Analisando a Figura 2.2, nota-se que a transição t1 possui apenas o lugar
p1 como entrada, e este possui pelo menos um token. Logo, a transição t1 está habilitada e
pode ser disparada.
Quando uma transição é disparada - Figura 2.3 (a) - remove-se um token de cada lugar
de entrada da transição em questão e então coloca-se um token em cada lugar de saı́da da
4
mesma - Figura 2.3 (b).
p1
p2
t4
p1
t1
p3
t2
p4
t3
p2
t4
t5
(a)
p3
t2
p4
p5
t6
t1
t3
t5
p5
t6
(b)
Figura 2.3: Disparo da transição t1 de uma Rede de Petri
Cada disparo de uma transição pode modificar a distribuição dos tokens nos lugares e
conseqüentemente pode produzir uma nova marcação Mj para a Rede de Petri.
Tokens são considerados entidades atômicas (indivisı́veis1 ). Ou seja, o disparo de uma
transição pode desativar outros possı́veis disparos, removendo tokens que poderiam ser consumidos por uma ou outra transição alimentada por um mesmo lugar de entrada. Observando
a Figura 2.3, pode-se notar que após o disparo da transição t1 , os lugares p2 e p3 receberam
um token cada. Por conseguinte, as transições t2 e t3 passaram a estar habilitadas para o
disparo. O disparo da transição t2 coloca um token no lugar p4 e habilita a transição t4 ; o
disparo da transição t3 coloca um token no lugar p5 e também habilita o disparo da transição
t5 . Neste momento, as transições t4 , t5 e t6 estão habilitadas a serem disparadas, porém apenas uma destas três transições pode ser disparada. A seleção do disparo é não determinı́stica
e o disparo de uma transição desativa automaticamente o disparo da outra2 .
2.1.3
Atingibilidade
O resultado do disparo de uma transição de uma marcação Mi pode gerar uma nova
marcação Mj . A marcação Mj é dita imediatamente atingı́vel de Mi se ela pode ser obtida
do disparo de uma transição habilitada em Mi . Uma marcação Mk é dita atingı́vel de Mi
se existir uma seqüência de disparo de transições que levem o estado da Rede de Petri em
questão de Mi para Mk .
O funcionamento de uma Rede de Petri gera uma seqüência M de marcações {M0 , M1 ,
M2 , ...} e uma seqüência T de transições {t1 , t2 , ...}. O disparo de uma transição tk , habilitada em Mi , pode mudar o estado da Rede de Petri de Mi para Mj e assim por diante.
1
A mudança de marcação é um processo discreto e não contı́nuo.
Neste exemplo, o disparo da transição t4 não desativa o disparo da transição t5 , e vice-versa. Porém, o
disparo da transição t6 desativa o disparo das outras duas transições.
2
5
Com isso, pode-se definir o conjunto de atingibilidade de uma Rede de Petri. O termo
atingibilidade também é conhecido como reachability [12]. O conjunto de atingibilidade R
é composto por todas as marcação distintas de M que são atingı́veis a partir de M0 . As
marcações do conjunto M podem ser representadas na forma de uma árvore. A Figura 2.4
mostra a árvore de atingibilidade do exemplo apresentado na Figura 2.2.
M 0 = {1, 0, 0, 0, 0}
t1
M 1 = {0, 1, 1, 0, 0}
t2
t3
M 2 = {0, 0, 1, 1, 0}
t4
M1
M 3 = {0, 1, 0, 0, 1}
t3
t2
M 4 = {0, 0, 0, 1, 1}
t4
M3
t6
M4
t5
M1
t5
M0
M2
Figura 2.4: Árvore de atingibilidade da Figura 2.2
A árvore de atingibilidade é construı́da a partir da marcação inicial M0 da Rede de Petri
em questão. Em seguida, leva-se em conta todas as marcações imediatamente atingı́veis desta
marcação inicial. Somente M1 é imediatamente atingı́vel a partir da marcação inicial. A partir desta nova marcação, repete-se o mesmo procedimento. Logo, M2 e M3 são as marcações
imediatamente atingı́veis a partir de M1 . Considerando M2 como a nova marcação, tem-se
as marcações M1 - obtida anteriormente - e M4 . A marcação M3 também gera as marcações
M1 e M4 . Repetindo o mesmo procedimento para M4 , consegue-se as marcações M0 , M2 e
M3 . Desta forma, obtem-se a árvore de atingibilidade do exemplo em questão.
A construção da árvore a partir da marcação inicial M0 poderia gerar uma árvore de
tamanho infinito. Entretanto, para se represetar a árvore em um tamanho finito, quando
encontra-se um marcação já atingida, não expande-se a marcação em questão, considerandoa como uma marcação duplicada. As marcação duplicadas são representadas pelas folhas 3
da árvore.
2.1.4
Limitação
Um lugar de uma Rede de Petri pode apresentar a propriedade de limitação. O termo
limitação também é conhecido como boundedness [12]. Um lugar pode ser dito como k-limitado
ou simplesmente limitado se o número de tokens do lugar não excede o limite k do mesmo.
3
As folhas da árvore de atingibilidade são marcações as quais não são mais expandidas por já terem sido
obtidas anteriormente.
6
No exemplo apresentado na Figura 2.2, para todos os lugares da Rede de Petri em questão,
o limite k é igual a 1. Pois, nenhum lugar da Rede de Petri deste exemplo contém mais de 1
token.
Uma Rede de Petri também pode ser denominada limitada. Diz-se que uma Rede de Petri
é limitada se o limite de todos os lugares for menor que infinito. Logo, pode-se concluir que
a Rede de Petri da Figura 2.2 é 1-limitada, pois nenhum lugar desta rede acumula mais do
que 1 token em qualquer marcação possı́vel da mesma.
2.1.5
Segurança
Um lugar de uma Rede de Petri pode ser considerado seguro se ele tiver no máximo 1
token, ou seja, um lugar que é 1-limitado é considerado um lugar seguro. O conceito de
segurança é simplesmente uma particularização do conceito de limitação. O termo segurança
também é conhecido como safeness [12].
Esta propriedade é uma das mais importantes para a modelagem de sistemas digitais,
visto que um lugar pode ser modelado como uma porta ou mesmo um flip-flop [12].
Logo, pode-se dizer que uma Rede de Petri é segura se o limite k de todos os lugares da
mesma não exceder 1 token. Como pode-se observar, a Rede de Petri apresentada no exemplo
da Figura 2.2 é uma rede segura, pois ela é uma rede 1-limitada.
2.1.6
Vivacidade
O conceito de vivacidade está definido em função das possibildades de disparo das transições.
O termo vivacidade também é conhecido como liveness [12]. Vivacidade é uma propriedade
fundamental para sistemas do mundo real. Porém, muitas vezes é muito caro observar esta
propriedade em alguns sistemas de grande porte [12].
Uma transição é potencialmente disparável em uma marcação M0 se existe uma marcação
Mi atingı́vel a partir de M0 , ou seja, uma transição é considerada viva se esta não é passı́vel
de um impasse ou deadlock. Impasse em uma Rede de Petri é a impossibilidade do disparo
de qualquer transição da mesma.
2.2
Exemplo de Modelagem
Um exemplo de modelagem de uma Rede de Petri é o caso de compartilhamento de recursos entre componentes do sistema. Na Figura 2.5, tem-se um exemplo de modelagem de
Rede de Petri para o compartilhamento de recursos com exclusão mútua.
A Figura 2.5 apresenta a Rede de Petri que representa o processo de produção em uma
fábrica de água mineral. Supõe-se que esta fábrica possua uma única máquina responsável
pela manufatura da garrafa de água e da tampinha da mesma. Portanto, quando esta máquina
estiver sendo usada para fabricar as garrafas, o processo de manufatura das tampinhas deverá
aguardar para que possa-se utilizar a mesma máquina e vice-versa.
7
p0
t0
p9
p1
p2
t1
t2
p3
p7
p4
t3
t4
p5
p6
t5
p8
Figura 2.5: Compartilhamento de recursos com exclusão mútua - Rede de Petri
Tendo em vista a rede da Figura 2.5, o lugar p0 da rede representa o depósito de matériaprima e o lugar p9 a habilitação do sistema para a manufatura. Os lugares p1 e p2 representam,
respectivamente, os repositórios de matéria-prima para as garrafas e tampinhas. Os lugares
p3 e p4 representam o processo de manufatura das garrafas e o processo de manufatura das
tampinhas respectivamente.
O lugar p7 representa a máquina responsável pela linha de produção da fábrica. Um token
neste lugar representa que a máquina está disponı́vel. Quando não se encontrar um token
neste lugar, significa que a máquina não está disponı́vel, ou seja, um dos dois processos está
utilizando a máquina. Os lugares p5 e p6 são, respectivamente, os depósitos das garrafas e
das tampinhas. Por último, o lugar p8 representa o processo de montagem da garrafa de água
mineral.
A transição t0 representa o inı́cio do processo de manufatura. Neste momento, é feita
a distribuição de matéria-prima para os depósitos p1 e p2 para a manufatura de garrafas
e tampinhas. As transições t1 e t2 representam, respectivamente, o inı́cio dos processos de
manufatura das garrafas e tampinhas. Como o lugar p7 possui apenas um token, apenas uma
das duas transições t1 ou t2 poderá ocorrer. Quando uma dessas transições ocorrer, automaticamente o disparo da outra transição será impossibilitado, pois o token do lugar p7 será
consumido.
A transição t3 representa o término da manufatura de garrafas e, conseqüentemente, a
liberação da máquina. Da mesma forma, a transição t4 libera a máquina e termina com o
8
processo de manufatura de tampinhas. O disparo da transição t3 colocará um token em p5 e
o disparo da transição t4 colocará um token em p6 . Quando uma destas transições ocorrerem,
automaticamente será colocado um token em p7 , liberando a máquina para um novo processo
de manufatura. Quando ambos os lugares p5 e p6 contiverem pelo menos um token, então a
transição t5 é disparada. Quando isso ocorrer, um token é colocado no lugar p8 e outro no
lugar p9 , habilitando o processo de manufatura de outras garrafas e tampinhas, desde que
haja matéria-prima.
Muitas outras áreas de estudo podem ser mencionadas como possı́veis assuntos para a
modelagem de Redes de Petri, incluindo alocação de recursos, sistemas operacionais, redes de
filas, controle de tráfico, entre outros. O formalismo de Redes de Petri é uma ferramenta de
grande facilidade para modelagem de uma vasta variedade de sistemas.
9
3
Redes de Petri Estocásticas
Usando o formalismo de Redes de Petri, é possı́vel descrever somente a estrutura lógica
de sistemas, pois tal formalismo não inclui nenhum conceito de tempo. Entretanto, freqüentemente, o conceito de tempo tem um papel importante na descrição do comportamento de
sistemas.
A introdução do conceito de tempo no formalismo de Redes de Petri permite a descrição
de um comportamento dinâmico de sistemas [13]. Noe e Nutt [20], Merlin e Farber [16] e
Zuberek [32] usaram o conceito de tempo para a modelagem do comportamento de sistemas
computacionais - Redes de Petri Temporizadas (TPN) - associando um tempo fixo no disparo
de transições.
O formalismo de Redes de Petri Temporizadas tem como sua principal caracterı́stica a
associação de um atraso fixo para cada transição do modelo - Figura 3.1.
p1
t 1,ϑ 1
p2
p3
t 2,ϑ 2
p4
t 3,ϑ 3
Figura 3.1: Exemplo de uma Rede de Petri Temporizada
Redes de Petri Temporizadas foram o passo inicial para a criação do formalismo de Redes
de Petri Estocásticas (SPN). A possibilidade de unir a habilidade do formalismo de Redes de
Petri para descrever sincronização e concorrência com um modelo estocástico é o principal
atrativo para obter-se uma avaliação quantitativa de sistemas computacionais complexos.
10
Os primeiros estudos sobre Redes de Petri Estocásticas foram desenvolvidos por Symons
[29], Natkin [19] e Molloy [18]. As Redes de Petri Estocásticas são obtidas através da associação de um tempo distribuı́do exponencialmente com o disparo de cada transição da rede.
3.1
Descrição Informal
O formalismo de Redes de Petri Estocásticas é uma ferramenta para modelagem e avaliação
de desempenho de sistemas envolvendo concorrência, não-determinismo e sincronização [1].
Redes de Petri Estocásticas são definidas assumindo que todas as transições são temporizadas e que o atraso no disparo das transições é associado a uma variável aleatória distribuı́da
exponencialmente.
Dada uma Rede de Petri Estocástica com uma marcação que possua diversas transições
habilitadas a serem disparas, uma das transições ocorre. Quando uma transição de uma Rede
de Petri Estocástica é disparada, assim como no formalismo de Redes de Petri, uma nova
marcação pode ser gerada. Esta nova marcação pode conter transições que já encontravam-se
habilitadas na marcação anterior, mas não foram disparadas. Por causa da propriedade de
ausência de memória 1 da distribuição exponencial, pode-se assumir que a atividade associada
a cada transição é recomeçada para qualquer nova marcação.
A estrutura de uma Rede de Petri Estocástica possui os mesmos elementos contidos na
estrutura da uma Rede de Petri acrescido do conjunto L = {l1 , l2 , ..., lm } de taxas de disparos,
possivelmente dependente de marcação, associadas às transições - Figura 3.2. Segundo Molloy
[18], devido a propriedade de ausência de memória da distribuição exponencial do atraso dos
disparos, o formalismo de Redes de Petri Estocásticas é isomórfico ao formalismo de Cadeias
de Markov de Tempo Contı́nuo (CTMC).
p1
αm1
p3
γ
t3
δ
t4
β
t1
p2
t2
p4
Figura 3.2: Exemplo de uma Rede de Petri Estocástica
É possı́vel mostrar que uma Rede de Petri Estocástica é ergódica se para qualquer marcação
desta rede atingida a partir da marcação inicial, pode-se novamente atingir a marcação ini1
Do inglês memoryless
11
cial. Logo, se uma Rede de Petri Estocástica é ergódica, é possı́vel calcular a distribuição da
probabilidade de solução estacionária das marcações da mesma resolvendo a equação:
πQ = 0
(3.1)
Com a restrição adicional:
X
πi = 1
(3.2)
i
Onde Q é o gerador infinitesimal cujos os elementos são obtidos através das taxas de
disparos correspondentes às transições e π é o vetor de probabilidade de solução estacionária.
Para auxiliar na construção da Cadeia de Markov equivalente à Rede de Petri Estocástica
da Figura 3.2, constrói-se a árvore de atingibilidade da rede em questão. O processo para
a construção da árvore de atingibilidade de uma Rede de Petri Estocástica segue o mesmo
processo da construção da árvore de uma Rede de Petri. A Figura 3.3 representa a árvore de
atingibilidade da Rede de Petri Estocástica da Figura 3.2.
M 0 = {2, 0, 0, 0}
t 1(2)
M 1 = {1, 1, 1, 0}
t3
t2
M 3 = {1, 1, 0, 1}
t4
M1
t 1(1)
M0
M 2 = {0, 2, 2, 0}
t 1(1)
t3
t2
M 4 = {0, 2, 1, 1}
M4
t2
t3
M3
M1
t4
M 5 = {0, 2, 0, 2}
M2
t4
M4
Figura 3.3: Árvore de atingibilidade da Figura 3.2
A partir da árvore de atingibilidade, pode-se construir a Cadeia de Markov. O espaço
de estados da Cadeia de Markov correspondente à árvore de atingibilidade de uma Rede de
Petri Estocástica é equivalente às marcações encontradas na mesma. Ou seja, na Figura 3.3,
a árvore de atingibilidade possui 5 marcações que serão equivalentes aos estados da Cadeia
de Markov - Figura 3.4.
Tendo em vista a Figura 3.4, constata-se que a taxa de transição do estado 0 para o
estado 1 é igual a t1 (2). O valor entre parênteses corresponde ao número de tokens do lugar
p1 na marcação M0 , visto que esta transição é dependente de m1 . Por conseguinte, a taxa de
12
0
t 1(2)
t2
1
t 1(1)
t3
t2 t4
2
3
t4 t2
t3
t 1(1)
4
t3
t4
5
Figura 3.4: Cadeia de Markov equivalente à Figura 3.2
transição do estado 1 para o estado 2 e do estado 3 para o estado 4 é igual a t1 (1), visto que
m1 é igual a 1 em M1 e M3 .
Assumindo que as taxas de transição α = β = γ = δ = 1, pode-se obter o gerador infinitesimal Q a partir da árvore de atingibilidade. O gerador infinitesimal é uma matriz cujos
elementos qij são obtidos através do somatório das taxas de disparo das transições habilitadas
na marcação Mi as quais os disparos geram a marcação Mj . Em (3.3), tem-se a matriz do
gerador infinitesimal da Rede de Petri Estocástica da Figura 3.2.




Q=



-2
1
0
0
0
0
2
-3
1
1
0
0
0
1
-2
0
1
0
0
1
0
-2
1
0
0
0
1
1
-3
1
0
0
0
0
1
-1








(3.3)
Utilizando o gerador infinitesimal Q obtido em (3.3), pode-se resolver a equação (3.1) e
obter os valores do vetor π:
π=
1
11
2
11
2
11
2
11
2
11
2
11
É possı́vel, a partir do vetor π, obter uma avaliação quantitativa do comportamento da
Rede de Petri Estocástica. A probabilidade de uma condição em especial de uma Rede de
13
Petri Estocástica pode ser calculada pela equação:
P {A} =
X
πi
(3.4)
i∈A
Onde A é o subconjunto de marcações atingı́veis a partir da marcação inicial que satisfaça
a condição requerida.
Também é possı́vel calcular, através da equação (3.5), o número médio de tokens em um
determinado lugar.
E[mi ] =
k
X
[nP {A(i, n)}]
(3.5)
n=1
Onde A(i, n) é o subconjunto de marcações atingı́veis a partir da marcação inicial as quais
o número de tokens do lugar pi é igual a n, e k é o limite máximo de tokens do lugar em
questão. Ou seja, o lugar pi é k-limitado.
Como exemplo, pode-se calcular o número médio de tokens do lugar p1 da Rede de Petri
Estocástica da Figura 3.2. Usando a equação (3.5), tem-se:
6
E[m1 ] = 1 P {A(1, 1)} +2 P {A(1, 2)} = 2π0 + π1 + π3 =
| {z }
| {z }
11
π1 +π3
π0
A taxa média de disparo da transição tj por unidade de tempo é calculada pela equação:
 

X
X
πi lj
fj =
(3.6)
lk 
Mi ∈Aj
∀tk habilitada em Mi
Como demostração, usando a equação (3.6), pode-se calcular a taxa de disparo da transição
t2 , habilitada somente nas marcações M1 , M2 e M4 :
f 2 = π1
|
l2
l2
l2
1
1
1
7
+ π2
+ π4
= π1 + π2 + π4 =
l1 + l2 + l3
l2 + l3
l2 + l3 + l4
3
2
3
33
{z
} |
{z
} |
{z
}
M1
M2
M4
14
3.2
Exemplo de Modelagem
Um exemplo de modelagem de Rede de Petri Estocástica é dado na Figura 3.5, a qual
representa uma variação do exemplo apresentado na Figura 2.5.
p0
φ
t0
m1
p1
α
p2
p3
γ
β
t1
p7
t2
p4
δ
t3
p5
t4
p6
λ
t5
Figura 3.5: Compartilhamento de recursos com exclusão mútua - Rede de Petri Estocástica
A Rede de Petri Estocástica modelada na Figura 3.5 continua representando o processo
de produção em uma fábrica de água mineral. Porém, taxas de disparos estão associadas às
transições da rede. Para manter-se a relação de ergodicidade da Rede de Petri Estocástica
da Figura 3.5 com a Cadeia de Markov que a representa, os lugares p8 e p9 da Rede de Petri
original (Figura 2.5) foram retirados.
Esta Rede de Petri Estocástica possui 30 marcações, descritas na Tabela 3.1, geradas a
partir do disparo das transições.
A Figura 3.6 representa a árvore de atingibilidade do exemplo em questão.
Neste exemplo, supõe-se que a máquina, responsável pela manufatura da garrafa de água
e pela tampinha da mesma, não suporta a produção sobreposta 2 de mais do que 2 unidades
de cada elemento. Logo, o lugar p0 da rede possui apenas 2 tokens, porém a manufatura das
garrafas e tampinhas depende apenas do estoque de matéria-prima destes elementos, os quais
não estão sendo representados. Os lugares p1 e p2 representam os repositórios de matériaprima já alocada para as garrafas e para as tampinhas respectivamente. Os lugares p3 e p4
representam, respectivamente, o processo de manufatura das garrafas e o processo de manufatura das tampinhas.
2
O produção de garrafas e tampinhas ocorre de modo concorrente. Ou seja, enquanto ocorre a produção
de garrafas, a produção de tampinhas aguarda a liberação da máquina, e vice-versa.
15
m0
2
1
0
1
1
0
0
1
1
0
0
1
1
0
0
M0
M1
M2
M3
M4
M5
M6
M7
M8
M9
M10
M11
M12
M13
M14
m1
0
1
2
0
1
1
2
0
1
1
2
0
0
0
1
m2
0
1
2
1
0
2
1
1
0
2
1
0
0
2
1
m3
0
0
0
1
0
1
0
0
0
0
0
0
1
1
0
m4
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
m5
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
m6
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
m7
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
M15
M16
M17
M18
M19
M20
M21
M22
M23
M24
M25
M26
M27
M28
M29
m0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
m1
1
2
0
0
1
2
0
0
1
1
0
1
0
0
0
m2
1
0
0
2
1
0
1
1
0
0
1
0
0
0
0
m3
1
0
0
0
0
0
0
1
0
1
0
0
0
1
0
m4
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
m5
0
0
1
2
1
0
2
1
1
0
2
1
2
1
2
m6
1
1
1
0
1
2
0
1
1
2
1
2
1
2
2
m7
0
0
1
1
1
1
0
0
0
0
1
1
0
0
1
Tabela 3.1: Marcações da Figura 3.5
M0
t 0(2)
M1
t1
t3
M7
t2
M 11
t 0(1)
M 14
t 0(1)
M 19
t 0(1)
M9
M2
t1
M6
t3
t2
M 13
t5
t1
M 14
t4
t3
M 18
M0
M 21
t3
t4
M 27
t4
M 29
M 25
t5
M 11
t5
M7
M 15
t3
t5
M 25
M1
M3
t1
M 28
t3
M 29
t2
M 16
t4
M8
t 0(1)
M 10
t1
M 12
t 0(1)
M 15
t3
M 17
M 20
t2
t5
M 22
M 10
M4
t4
M 19
t1
t2
t2
M6
t4
M9
t1
t 0(1)
t2
M5
M
t 0(1) 5
t4
M 17
t2
t 0(1)
M3
M 23
t4
M 26
t5
t5
t1
t5
M4
M 24
t3
M 26
M8
M 12
t5
M 17
Figura 3.6: Árvore de atingibilidade da Figura 3.5
O lugar p7 representa a máquina responsável pela linha de produção da fábrica. A máquina
suporta apenas uma tarefa por vez, ou seja, um token no lugar p7 indica que a máquina está
disponı́vel. Se este lugar não possuir um token, significa que um dos dois processos de produção
está utilizando a máquina.
Os lugares p5 e p6 são os depósitos das garrafas e das tampinhas respectivamente. Ao
contrário do exemplo modelado na Figura 2.5, este exemplo não possui um lugar representando a junção da garrafa e tampinha de água mineral. Este passo é tratado de forma abstrata
na transição t5 , onde esta ocorre à medida que haja tokens nos lugares p5 e p6 . Conseqüentemente, um token é retirado dos lugares p5 e p6 (depósitos de garrafas e tampinhas) e colocado
no lugar p0 , liberando o processo de manufatura de uma nova garrafa e nova tampinha.
A transição t0 representa o inı́cio do processo de manufatura. Esta transição está associada
16
a uma taxa de disparo dependente da marcação de m1 . Quando a transição t0 é disparada,
um token é removido de p0 e adicionado em p1 e p2 , habilitando o processo de manufatura
das garrafas e tampinhas.
Como as transições t1 e t2 encontram-se em conflito, quando a máquina estiver produzindo
garrafas (lugar p3 ), ela não estará produzindo tampinhas (lugar p4 ), e vice-versa. Quando
uma das transições t3 ou t4 ocorrer, um token será colocado em p7 disponibilizando a máquina
para um novo processo de manufatura. Quando ambos os lugares p5 e p6 contiverem ao menos
um token cada, então a transição t5 é disparada.
Isso caracteriza o fim do processo de manufatura de garrafas e tampinhas, possibilitando
uma possı́vel continuação do processo. Com isso, um token é colocado em p0 permitindo a
produção de uma nova garrafa e tampinha.
O formalismo de Redes de Petri Estocásticas é uma ferramenta muito útil para análise de
sistemas de computadores, visto que permite às atividades de sistemas serem precisamente
descritas através de um gráfico. Este gráfico pode ser convertido para um modelo Markoviano
utilizado para obter-se avaliação quantitativa do sistema em questão.
17
4 Redes de Petri Estocásticas
Generalizadas
Uma caracterı́stica importante do formalismo de Redes de Petri Estocásticas é que ele
pode ser facilmente compreendido por pessoas que não tenham familiaridade com métodos
de modelagem probabilı́stica.
Entretanto, a representação gráfica de sistemas utilizando o formalismo de Redes de Petri
Estocásticas encontra-se limitada à medida que aumenta-se o tamanho e a complexidade do
sistema em questão. Além disso, o número de estados da Cadeia de Markov equivalente à
Rede de Petri cresce muito rapidamente conforme a dimensão do gráfico cresce. Portanto, o
formalismo de Redes de Petri Estocásticas pode ser usado para modelar somente sistemas de
tamanho limitado.
4.1
Descrição Informal
Geralmente, não é desejável associar uma variável aleatória distribuı́da exponencialmente
para cada transição do modelo, conforme descrito no formalismo de Redes de Petri Estocásticas. O formalismo de Redes de Petri Estocásticas Generalizadas (GSPN) associa tempo
somente para alguns eventos que acredita-se ter um grande impacto na avaliação do sistema.
Um tı́pico exemplo disso pode ser o caso em que a seqüência de operações de um sistema
compreende atividades cujas durações diferem bruscamente. Logo, é conveniente que atividades de duração desprezı́vel 1 sejam modeladas somente do ponto de vista lógico, enquanto
que atividades de duração mais longa seriam associadas a uma variável aleatória. Através
desta modelagem, reduz-se o número de estados da Cadeia de Markov equivalente ao modelo,
conseqüentemente reduzindo a complexidade da solução do mesmo. Além disso, a utilidade
de uma estrutura lógica que pode ser usada em conjunto com uma estrutura temporizada
permite a construção de um modelo compacto de sistemas computacionais complexos [13].
O formalismo de Redes de Petri Estocásticas Generalizadas [15] permite duas classes diferentes de transições no modelo: transições imediatas e transições temporizadas. A transição
imediata dispara em tempo zero assim que encontra-se habilitada. A transição temporizada,
assim como no formalismo SPN, dispara após um tempo aleatório, distribuı́do exponencialmente, associado à mesma quando habilitada.
1
Atividades de muito curta duração, ou somente conceitual.
18
As transições temporizadas são representadas graficamente no modelo por barras espessas,
e as transições imediatas por barras finas. Obviamente, as taxas de disparos estão associadas
somente às transições temporizadas, e estas podem ser dependentes da marcação da GSPN.
Na Figura 4.1, tem-se um exemplo de um modelo de Rede de Petri Estocástica Generalizada.
p1
m1 α
t1
p2
p3
t2
t3
p5
t4
p4
p6
β p7
γ
t5
t6
t7
Figura 4.1: Exemplo de uma Rede de Petri Estocástica Generalizada [13]
Como pode ser constatado na Figura 4.1, as transições t1 , t4 e t5 são transições temporizadas, e as transições t2 , t3 , t6 e t7 são transições imediatas. A transição t1 é dependente
da marcação de p1 .
A estrutura de uma Rede de Petri Estocástica Generalizada é a mesma utilizada pela
Rede de Petri Estocástica, porém o conjunto L = {l1 , l2 , ..., lm′ } de taxas de disparo contém
somente m′ elementos, onde m′ é o número de transições temporizadas da Rede de Petri
Estocástica Generalizada. No funcionamento de uma Rede de Petri Estocástica Generalizada,
pode ocorrer que várias transições sejam habilitadas simultaneamente por uma marcação. Se
o conjunto de transições habilitadas H compreender somente transições temporizadas, então
a transição temporizada ti (i ∈ H) dispara com uma probabilidade:
P
li
k∈H lk
,
(4.1)
exatamente como no formalismo de Redes de Petri Estocásticas. Se o conjunto H compreender ambas transições imediatas e temporizadas, então somente as transições imediatadas
serão disparadas. Se o conjunto H compreender zero ou mais transições temporizadas e somente uma única transição imediata, esta transição imediata é que será disparada. Quando
o conjunto H compreender várias transições imediatas, é necessário descrever uma função de
19
densidade de probabilidade que determine qual transição será disparada.
O subconjunto de H compreendendo todas as transições imediatas habilitadas junto com
a distribuição de probabilidade associada as mesmas é chamada de random switch 2 . Esta
distribuição de probabilidade é conhecida como switching distribution 3 . Diferentes marcações
podem gerar um único random switch toda vez que estas marcações habilitarem o mesmo
conjunto de transições imediatas sob as quais uma switching distribution (possivelmente dependente de marcação) pode ser definida [13].
A GSPN descrita na Figura 4.1 possui sete lugares e sete transições. Esta GSPN possui
três transições temporizadas: t1 , t4 e t5 , as quais possuem como taxas de disparo m1 α, β e γ
respectivamente. As transições t2 , t3 , t6 e t7 são transições imediatas, e por definição possuem
taxas de disparo de tempo zero.
As transições t6 e t7 são transições conflitantes. Elas são sempre habilitadas simultaneamente, logo é necessário definir uma switching distribution para cada marcação em que m7
é maior que zero. As transições t2 e t3 também são transições conflitantes, e estas são simultaneamente habilitadas se p3 e p4 contiverem tokens. Por conseguinte, uma switching
distribution deve ser definida para cada marcação em que m2 , m3 e m4 forem maiores que
zero. Como pode ser observado, não mais do que duas transições imediatas podem estar simultaneamente habilitadas. Desta forma, dois random switchs podem ser identificados: para
as transições t2 e t3 , e para as transições t6 e t7 . Assim como na modelagem de Rede de
Petri é necessário especificar-se a marcação inicial como parâmetro de entrada da mesma, em
uma GSPN também é necessário identificar os possı́veis random switch da rede, e definir a
switching distribution da mesma para resolver-se os conflitos das transições. Uma possı́vel
switching distribution para o exemplo da Figura 4.1 é descrito na Tabela 4.1.

 P {t2 } =
m3
m3 +m4

P {t3 } =
m4
m3 +m4

 P {t6 } =
m4
m3 +m4

P {t7 } =
m3
m3 +m4


se m3 6= 0 ou m4 6= 0

P {t6 } = P {t7 } = 1/2, se m3 = m4 = 0
Tabela 4.1: Switching distribution da GSPN descrita na Figura 4.1
A partir da marcação inicial descrita na Figura 4.1, uma possı́vel execução do estado da
GSPN pode ser a seguinte: a transição t1 dispara com uma taxa 1/(2α), visto que esta é
dependente da marcação de m1 . Com isso, um dos dois tokens contidos em p1 é movido
2
Momento em que é necessário determinar-se qual transição deve ser disparada.
Termo também conhecido como distribuição de escolha ou agulhamento. O termo não foi traduzido visto
que a tradução poderia não contemplar corretamente o sentido do mesmo.
3
20
para p2 . Instantaneamente, ambas as transições t2 e t3 podem dispar. Como estas duas
transições são conflitantes, o disparo da transição é selecionado de acordo com a switching
distribution definida previamente na Tabela 4.1. Neste caso, ambas as transições possuem a
mesma probabilidade. Assume-se que a transição t2 dispara. Logo, remove-se um token de
p2 e p3 , e adiciona-se um token em p5 . Conseqüentemente, as transições temporizadas t1 e t4
encontram-se habilitadas. A transição t1 dispara com probabilidade:
P {t1 } =
α
,
α+β
(4.2)
enquanto a transição t4 dispara com a probabilidade:
P {t4 } =
β
.
α+β
(4.3)
Se a transição t1 disparar primeiro, um token é movido de p1 para p2 . Desse modo, a
transição imediata t3 é habilitada e disparada instanteneamente, visto que é a única transição
habilitada deste tipo no momento. Um token é removido de p2 e p4 , e coloca-se um token
em p6 . Neste momento, a marcação resultante da GSPN contém um token em p5 e p6 . Esta
marcação habilita as transições t4 e t5 , onde cada uma pode disparar com a probabilidade:
P {t4 } =
β
,
β +γ
P {t5 } =
γ
.
β+γ
(4.4)
Agora, assume-se que t4 dispara primeiro, então um token é movido de p5 para p7 , e um
token é colocado em p1 . As duas transições imediatas t6 e t7 estão simultaneamente habilitadas, e como especificado no switching distribution da Tabela 4.1, cada uma das transições
pode disparar com probabilidade igual a 1/2, de forma que o token de p7 pode mover-se tanto
para p3 quanto para p4 . Neste instante, as transições t1 e t5 encontram-se habilitadas, e a
GSPN segue o seu funcionamento.
O conjunto de atingibilidade de uma GSPN pode ser dividido em dois grupos: tangible
markings 4 e vanishing markings 5 . As tangible markings são marcações que habilitam somente
transições temporizadas. Enquanto as vanishing markings são marcações que habilitam ao
menos uma transição imediata. A Tabela 4.2 descreve os estados que compõem o conjunto de
atingibilidade da rede em questão. O conjunto de atingibilidade da GSPN é um subconjunto
do conjunto de atingibilidade da SPN associada, pois as regras de precedência introduzidas
com o uso de transições imediatas não permitem que alguns estados sejam atingı́veis. As
transições temporizadas t1 , t4 e t5 habilitadas nas vanishing markings, por definição, nunca
ocorrerão, pois as transições imediatas habilitadas com estas transições ocorrerão primeiro.
4
5
Termo também conhecido como marcações atingı́veis.
Termo expresso no sentido de marcações efêmeras.
21
Marcação
m1
m2
m3
m4
m5
m6
m7
M0
M3
M4
M9
M22
M24
M31
M32
2
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
1
0
2
0
0
1
1
1
0
2
0
0
0
0
0
0
0
0
0
t1
t1
t1
t4
t1
t1
t5
t4
M1
M5
M6
M7
M8
M14
M15
M28
M29
1
0
0
2
2
1
1
0
0
1
1
1
0
0
0
0
1
1
1
0
1
0
1
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
t1
t3
t2
t1
t1
t1
t1
t3
t2
Tangible Markings
Vanishing Markings
Transições habilitadas
t4
t5
t5
t5
t4
t2
t4
t5
t6
t6
t5
t4
t5
t4
t3
t7
t7
t6 t7
t6 t7
Tabela 4.2: Marcações da Figura 4.1
Assumindo-se que o exemplo descrito na Figura 4.1 representasse uma Rede de Petri
Estocástica, as transições t2 , t3 , t6 e t7 seriam transições temporizadas. O conjunto de atingibilidade para esta rede possuiria 33 estados. A árvore de atingibilidade para a Figura 4.1,
caso esta fosse uma SPN, está representada na Figura 4.2.
M0
t 1(2)
M1
t 1(1)
M5
t3
M3
t 1(1)
M6
t4
t 1(1)
t 1(1)
t6
t6
t6
t7
t 7 t 1(1)
M 27 M 6 M 28
t7
M 30 M 11 M 10
M 18 M 16
t5
t6
t6
t7
M 21 M 4
M 22
t7
t 1(1)
t5
M 14
t 1(1)
M 27 M 8 M 7
t 1(1)
t5
t4
t5
M 31 M 10
t5
M 14
t6
t7
M 23 M 21 M 24 M 3
t 1(1)
t4
M 28 M 7
t3
M 15
t3
t6
M 10
t3
M 20 M 2 M 25
t7
t6
M 10
M0
M 25
M 28
M4
t 1(1)
t7
M 17
M6
t2
M 12
t2
t 1(1)
t3
M 22
M 18
t2
t4
t6
M 11
t6
t6
M 11
t7
M 27 M 29 M 5
t7
M 13
t 1(1)
t7
M 15 M 19 M 1
t7
M 23 M 26 M 2
t6
t5
M8
t 1(1)
t5
M9
t 1(1)
t 1(1)
t3
M 29 M 8
t2
t6
M 16 M 14 M 1 M 17
t7
M7
t 1(1)
t4
M9
M 20
t4
M5
t3
t5
t3
t2
M2
t2
M0
M 19
t 1(1)
t2
M 26 M 24
t2
M 29
t4
M 32 M 11
t4
M 15
Figura 4.2: Árvore de atingibilidade caso a Figura 4.1 fosse uma SPN
Entretanto, o conjunto de atingibilidade da GSPN descrita na Figura 4.1, possui apenas
17 estados. Observe que algumas marcações da árvore de atingibilidade não serão atingı́veis
devido ao uso de transições imediatas e da switching distribution especificada para este exemplo - marcações compreendidas pela área pontilhada da Figura 4.2. A Figura 4.3 representa
a árvore de atingibilidade da Figura 4.1.
Agora que a árvore de atingibilidade está definida, pode-se construir sua Cadeia de Markov
equivalente. Como descrito no capı́tulo anterior, o espaço de estados da Cadeia de Markov
correspondente às marcações da árvore de atingibilidade da rede em questão. Ou seja, na
22
M0
t 1(2)
M1
t2
M3
t 1(1)
t2
M5
M4
t 1(1)
M 28
M 15
t6
M 24
t5
t 1(1)
M7
t3
t4
M 29
t5
M8
t2
M0
t5
t7
M 22
M6
t6
M9
M 14
t6
t 1(1)
M7
t3
t4
t3
M4
t7
M9
M0
t7
M3
M8
t2
M 31
M 32
t5
t4
M 14
M 15
Figura 4.3: Árvore de atingibilidade da Figura 4.1
Figura 4.3, a árvore de atingibilidade possui 17 marcações que serão equivalentes aos 17 estados da Cadeia de Markov - Figura 4.4.
M0
t6
t7
t 1 (2)
t2
M3
t5
t7
M4
t6
t 1 (1)
M7
t3
M1
t 1 (1)
M5
t5
M6
M8
t3 t2
t5
M22
t4
t7
t 1 (1)
M28
M9
M14
M15
t5
t3
t4
t5
t6
t4
M31
M32
M24
t 1 (1)
t2
M29
Figura 4.4: Cadeia de Markov da Figura 4.1 compreendendo vanishing e tangible markings
Os estados pontilhados da Cadeia de Markov da Figura 4.4correspondem às vanishing
markings, enquanto os demais estados correspondem às tangible markings. Como as vanishing markings são marcações que ocorrem em tempo zero, somente as tangible markings são
representadas na Cadeia de Markov - Figura 4.5.
Na Figura 4.5, tem-se apenas as tangible markings da GSPN representando a Cadeia
de Markov equivalente. Na Cadeia de Markov equivalente a GSPN em questão, os arcos
não correspondem simplesmente à taxa de disparo de uma transição. Eles correspondem ao
conjunto de taxas percorridas de um estado ao outro, ou seja, os arcos são rotulados com exatamente uma transição temporizada seguida de uma seqüência finita (possivelmente vazia) de
transições imediatas.
23
M0
t 1 (2), t 2
t 5, t 6
t 5, t 6
t 5, t 7
M3
t 4, t 7
M4
t 5, t 7
t 4, t 6
t 1 (1), t 3
t 1 (1), t 2
M9
t 4, t 7
M22
t 1 (1), t 3
t 1 (2), t 3
t 5, t 6
M24
t 5, t 7
t 1 (1), t 2
M31
t 4, t 6
M32
Figura 4.5: Cadeia de Markov da Figura 4.1 somente com tangible markings
Como pode ser observado na Tabela 4.2, existe 3 possı́veis conflitos entre tangible markings: t1 e t4 , t1 e t5 , e t4 e t5 . A probabilidade de cada transição conflitante disparar está
descrita na equação (4.1). Já nas vanishing markings, dois random switch são identificados:
t2 e t3 , e t6 e t7 .
Note que M1 é a única marcação que possibilita que t2 e t3 encontrem-se em conflito. A
probabilidade de cada uma destas transições conflitantes disparar foi determinada na switching distribution descrita na Tabela 4.1. Neste caso, a probabilidade de ambas as transições
dispararem é igual a 1/2. A definição dos random switch em uma GSPN pode algumas
vezes requerer do desenvolvedor do modelo uma perspicácia e discernimento nas operações do
sistema modelado, pois a definição da switching distribution pode ter um impacto bastante
significativo nos resultados numéricos do modelo.
As marcações M7 , M8 , M14 e M15 são responsáveis por colocarem as transições t6 e t7 em
conflito. Determinou-se dois momentos bem especı́ficos na Tabela 4.1 para solucionar o conflito destas duas transições. Quando não houverem tokens nos lugares p3 e p4 (marcações M14
e M15 ), a probabilidade de ambas as transições dispararem é igual a 1/2. Entretanto, quando
m3 = 0 e m4 = 1 (marcação M7 ), a transição t6 será disparada. Em contra partida, quando
m3 = 1 e m4 = 0 (marcação M8 ), a transição t7 será disparada. Sendo assim, seguindo o
que foi especificado na Tabela 4.1 na modelagem da GSPN em questão, determinou-se que
os lugares p3 e p4 jamais conterão dois tokens. Note que esta limitação não é intrı́nseca da
estrutura e da marcação inicial, mas uma conseqüência das switching distributions definidas
na Tabela 4.1.
Um aspecto crı́tico na modelagem de uma GSPN é a identificação de todos os random
switch do sistema e a definição de uma switching distribution “apropriada” em todas as
marcações.
24
4.2
Exemplo de Modelagem
A Figura 4.6 representa uma variação da Rede de Petri Estocástica representada na Figura
3.5.
p0
φ
t0
m1
p1
p2
t1
p3
γ
t2
p7
p4
δ
t3
p5
t4
p6
t5
Figura 4.6: Compartilhamento de recursos com exclusão mútua - Rede de Petri Estocástica
Generalizada
A Rede de Petri Estocástica modelada na Figura 3.5 possui somente transições temporizadas. Na rede da Figura 4.6, as transições t1 , t2 e t5 passam a ser transições imediatas, ou
seja, disparam em tempo zero assim que encontram-se habilitadas. Esta rede continua representando o processo de produção em uma fábrica de água mineral. A switching distribution
da GSPN modelada como exemplo está definida na Tabela 4.3.

 P {t1 } =

P {t2 } =

 P {t1 } =

P {t5 } =
m1
m1 +m2
m2
m1 +m2

P {t1 } =





P {t2 } =





P {t5 } =
m1
m5 +m6

m5
m5 +m6

 P {t2 } =
m1
m5 +m6
m6
m5 +m6
P {t5 } =
m2
m5 +m6
m5 +m6
m5 +m6
m2
m5 +m6
Tabela 4.3: Switching distribution da GSPN descrita na Figura 4.6
25
Esta Rede de Petri Estocástica Generalizada possui 24 marcações, descritas na Tabela
4.4, geradas a partir do funcionamento da mesma.
Tangible Markings
Vanishing Markings
Marcação
m0
m1
m2
m3
m4
m5
m6
m7
M0
M3
M4
M5
M6
M11
M12
M13
M14
M15
M16
M21
M24
2
1
1
0
0
1
1
0
0
0
0
0
0
0
0
1
1
2
0
0
0
1
1
2
0
1
0
1
0
2
1
0
0
2
1
1
0
1
0
0
1
0
1
0
0
1
1
0
1
0
0
1
0
0
1
0
1
1
0
0
1
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
2
0
0
0
0
0
0
0
1
0
0
1
1
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
t0
t0
t0
t3
t4
t0
t0
t3
t4
t3
t4
t4
t3
M1
M7
M8
M9
M10
M17
M18
M19
M20
M25
M26
1
1
1
0
0
1
0
0
0
0
0
1
0
1
1
2
0
0
1
2
0
1
1
1
0
2
1
0
2
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
2
1
0
2
1
0
0
1
0
1
1
0
1
2
1
2
1
1
1
1
1
1
1
1
1
1
1
t0
t0
t0
t1
t1
t0
t2
t1
t1
t2
t1
Transições habilitadas
t3
t4
t4
t3
t1 t2
t2
t1
t2
t2
t5
t2 t5
t5
t5
Tabela 4.4: Marcações da Figura 4.6
A transição temporizada t0 habilitada nas vanishing markings, por definição, nunca ocorrerá, pois somente as transições imediatas habilitadas com esta transição poderão ocorrer. A
Figura 4.7 representa a árvore de atingibilidade do exemplo em questão.
As marcações compreendidas pela área pontilhada na árvore de atingibilidade não são
atingidas pelo funcionamento da rede. A Cadeia de Markov equivalente a esta GSPN está
descrito na Figura 4.8.
Os estados pontilhados da Cadeia de Markov correspondem às vanishing markings, enquanto os demais estados correspondem às tangible markings. Somente as tangible markings
são representadas na Cadeia de Markov, visto que as vanishing markings ocorrem em tempo
zero - Figura 4.9.
Com isso, a Cadeia de Markov equivalente encontra-se somente com 13 estados, ao
contrário da SPN equivalente da mesma que possui 30 estados.
Por utilizar transições imediatas, o formalismo de Redes de Petri Estocásticas Generalizadas minimiza o espaço de estados da Cadeia de Markov equivalente a rede. Tal caracterı́stica
é dependente da forma como a mesma foi modelada, de forma que somente os eventos que
tenham alguma relevância na avaliação do sistema tenham um tempo de retardo associado
às transições.
26
M0
t 0(2)
M1
t1
t3
M7
t2
t 0(1)
M 14
M 11
t 0(1)
M 19
M 17
t 0(1)
M2
t1
M6
M9
t1
t2
M 13
t5
M 14
t4
M 18
t2
t4
M 25
t2
M 27
t4
M 29
M 25
t5
M1
M 26
M 12
M 15
t3
M 17
t1
M 24
t5
t3
M4
t5
M 26
M8
t5
M 29
M 11
t1
M 20
M 23
t4
M 28
t3
t 0(1)
t4
M3
t1
M7
t5
t5
t4
M8
t 0(1)
M 16
t2
t5
M 22
t3
M4
M 10
t2
M 15
t3
M 19
t1
M 21
M 10
t1
t3
M0
M6
t4
t3
M9
t 0(1)
t2
M5
M
t 0(1) 5
t4
t2
t 0(1)
M3
M 12
t5
M 17
Figura 4.7: Árvore de atingibilidade da Figura 4.6
M0
t5
t 0 (2)
t1
t3
M3
t 0 (1)
t2
M7
t2
M1
M5 t
4
t3
t3
M11
t2
M14
t4
M19
t1
t2
M13
M25
M21
t2
M10
t1
t3
M16
t3
t4
M8
t4
M9
t 0 (1)
t5
t1
M6
M17
t4
M4
t 0 (1)
t5
M12
t 0 (1)
t5
M15
t4
M18
M20
t1
M24
t3
M26
Figura 4.8: Cadeia de Markov da Figura 4.6 compreendendo vanishing e tangible markings
t 0 (2),t 1
t 0 (2),t 2
M0
t 0 (1)
M5
t 3, t 2
M3
t 3, (t 5 t 1 )
t 4, t 5
t 3, t 5
t 3, t 2
t 4,(t 5 t 1 )
M14
t 0 (1)
t 4, (t 5 t 2 )
t 4, t 1
M4
t 0 (1)
t 3, (t 5 t 2 )
M11
M12
t 0 (1)
M15
t 4, t 1
t 3, t 1
M13
M6
t 4, t 2
t 3, t 2
M21
t 4, (t 5 t 2 )
t 3, (t 5 t 1 )
M24
t 4, t 1
M16
Figura 4.9: Cadeia de Markov da Figura 4.6 somente com tangible markings
27
5
Conclusão
O formalismo de Redes de Petri Estocásticas Generalizadas é uma generalização do formalismo de Redes de Petri Estocásticas, pois ele permite que as transições sejam representadas
com duas semânticas diferentes: imediatas ou temporizadas. Um tempo de disparo aleatório
distribuı́do exponencialmente é associado às transições temporizadas, enquanto as transições
imediatas disparam em tempo zero. Uma GSPN possui dois tipos de marcações: tangible markings, habilitam somente transições temporizadas, e vanishing markings, habilitam
pelo menos uma transição imediata. As vanishing markings podem habilitar um conjunto
de transições imediatas sobre as quais uma switching distribution é definida para descrever
probabilisticamente a seleção da transição a ser disparada. Conjuntos de transições imediatas
habilitadas simultaneamente junto com seus respectivos switching distributions formam os
random switchs.
O formalismo de Redes de Petri Estocásticas Generalizadas é uma ferramenta para uma
descrição precisa de atividades de sistemas. De fato, a representação das atividades do sistema
modelados em uma GSPN é feita de forma direta. Durante a etapa inicial de análise de uma
GSPN (construção do conjunto de atingibilidade) pode-se usar algumas das caracterı́sticas de
Redes de Petri para testar-se a correção do sistema modelado. Por exemplo, a detecção de
deadlocks no sistema.
Uma caracterı́stica distinta do formalismo de GSPN em relação ao formalismo de Redes
de Petri é o isomorfismo com Cadeias de Markov, que permite a avaliação quantitativa do
desempenho de sistemas. Logo, o mapeamento de uma GSPN para um modelo Markoviano equivalente é feito de forma transparente, superando a dificuldade da construção direta
(definição dos estados) da Cadeia de Markov.
Uma descrição detalhada de um sistema pode causar um aumento muito rápido no número
de estados do modelo Markoviano equivalente, visto que a complexidade e o tamanho do sistema modelado também podem crescer. O uso do formalismo de Redes de Petri Estocásticas
Generalizadas reduz o espaço de estados da Cadeia de Markov. Porém, o problema do aumento do tamanho e da complexidade dos sistemas não é solucionado, ele apenas resolve do
ponto de vista da modelagem de sistemas. Existem outros formalismos que têm em vista a
superação de tal dificuldade, tais como: SAN [24], PEPA [8], Balls & Buckets [28] e Decision
Diagrams [17].
Como trabalhos futuros, tem-se o intuito de formular um relatório técnico contendo a
definição formal dos formalismos de Redes de Petri, Redes de Petri Estocásticas e Redes de
Petri Estocásticas Generalizadas de modo a definir inequivocamente suas propriedades de mo28
delagem. Também tem-se como objetivo estudar o formalismo de Redes de Petri Estocásticas
Generalizadas Superpostas à vista de uma resolução numérica eficiente e uma eventual comparação com o formalismo de Redes de Autômatos Estocásticos.
29
Referências Bibliográficas
[1] G. Balbo, S. C. Bruell, and M. Sereno. Arrival theorems for product-form stochastic petri
nets. In Proceedings of the 1994 conference on Measurement and modeling of computer
systems, pages 87–97, Nashville, Tennessee, United States, 1994. ACM Press.
[2] F. Baskett, K. Chandy, R. Muntz, and F. Palacios. Open, closed, and mixed networks
of queues with different classes of customers. Journal of the ACM, 22(2):248–260, 1975.
[3] Y. Dallery. Approximate analysis of general open queueing networks with restricted
capacity. Technical report, Grenoble, 1998.
[4] S. Donatelli. Superposed stochastic automata: a class of stochastic petri nets with
parallel solution and distributed state space. Performance Evaluation, 18:21–36, 1993.
[5] S. Donatelli. Superposed generalized stochastic petri nets: definition and efficient solution. In Proceedings of the 15th International Conference on Applications and Theory of
Petri Nets, pages 258–277, Springer-Verlag, Berlin Heidelberg, 1994. R. Valette.
[6] G. Florin and S. Natkin. Les réseaux de petri stochastiques. Tecniques et Sciences
Informatiques, 4(1):143–160, 1985.
[7] E. Gelenbe and H. Shachnai. On g-networks and resource allocation in multimedia systems. In IEEE Research in Data Engineering, pages 104–110, Orlando, Florida, February
1998.
[8] S. Gilmore and J. Hillston. The pepa workbench: A tool to support a process algebrabased approach to performance modelling. In Computer Performance Evaluation, pages
353–368, 1994.
[9] J. R. Jackson. Networks of waiting lines. Operations Research, 5:518–521, 1957.
[10] J. R. Jackson. Jobshop-like queueing systems. Management Science, 10:131–142, 1963.
[11] J. D. C. Little. A proof of the queueing formula l = λw. Operating Research, 9:383–387,
1961.
[12] P. R. M. Maciel, R. D. Lins, and P. R. F. Cunha. Introdução às Redes de Petri e
Aplicações. 10a Escola de Computação, 1996.
[13] M. Ajmone Marsan, G. Balbo, and G. Conte. Performance Models of Multiprocessor
systems. The MIT Press, 1986.
30
[14] M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling
with Generalized Stochastic Petri Nets. John Wiley and Sons, 1995.
[15] M. Ajmone Marsan, G. Conte, and G. Balbo. A class of generalized stochastic petri
nets for the performance evaluation of multiprocessor systems. ACM Transactions on
Computer Systems, 2(2):93–122, 1984.
[16] P. M. Merlin and D. J. Farber. Recoverability of communication protocols - implications
of a theorical study. IEEE Transactions on Communications, 24(9):1036–1043, 1976.
[17] A. S. Miner, G. Ciardo, and S. Donatelli. Using the exact state space of a markov
model to compute approximate stationary measures. In Proceedings of the International
Conference on Measurements and Modeling of Computer Systems, pages 207–216, Santa
Clara, California, United States, June 2000. ACM Press.
[18] M. K. Molloy. On the Integration of Delay and Throughput Measures in Distributed
Processing Models. PhD thesis, University of California, Los Angeles, 1981.
[19] S. Natkin. Réseaux de Petri Stochastiques. PhD thesis, CNAM, Paris, 1980.
[20] J. D. Noe and G. J. Nutt. Macro e-nets representation of parallel systems. IEEE
Transactions on Computers, C-22(8):718–727, 1973.
[21] J. L. Peterson. Petri nets. ACM Computing Surveys, 9(3):223–252, 1977.
[22] C. A. Petri. Kommunikation mit Automaten. PhD thesis, Institut für instrumentelle
Mathematik, Bonn, 1962.
[23] M. Pidd. Computer simulations and management science. John Wiley and Sons, 1992.
[24] B. Plateau. De l´Evaluation du Parallélisme et de la Synchronisation. PhD thesis,
Paris-Sud, Orsay, 1984.
[25] M. Reiser and S. S. Lavenberg. Mean-value analysis of closed multichain queueing networks. Journal of the ACM, 27(2):313–322, 1980.
[26] W. Reisig. Petri nets: an introduction. Springer-Verlag, Berlin, 1985.
[27] G. Richter. Clocks and their use for time modelling. In Information Systems: Theoretical
and Formal Aspects, pages 49–66, North Holland, Amsterdam, 1985.
[28] W. J. Stewart. Introduction to the numerical solution of Markov chains. Princeton
University Press, 1994.
[29] F. J. W. Symons. Modelling and Analysis of Communication Protocols Using Numerical
Petri Nets. PhD thesis, University of Essex, 1978.
[30] M. Tazza. Análise Quantitativa de Sistemas. Escola Brasileira-Argentina de Informática,
1988.
[31] K. S. Trivedi. Probability & statistics with reliability, queuing, and computer science
applications. Englewood Cliffs: Prentice-Hall, 1982.
[32] W. M. Zuberek. Timed petri nets and preliminary performance evaluation. In Proceedings
of the 7th Annual Symposium on Computer Architecture, La Baule, France, 1980.
31