Redes de Autômatos Estocásticos (RAE) – Modelagem e Avaliação · utilizando noções de sincronismo e paralelismo. No Capítulo 3, os exemplos selecionados serão especificados

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL

FACULDADE DE INFORMÁTICA

PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

TRABALHO INDIVIDUAL I

do Curso de Mestrado em Ciência da Computação

Prof. Dr. Paulo Henrique Lemelle Fernandes

Estudo Comparativo de Técnicas de Modelagem em

Redes de Autômatos Estocásticos por

Thais Christina Webber dos Santos

Porto Alegre, agosto de 2002.

SUMÁRIO

LISTA DE ABREVIATURAS .............................................................................................................. 4

LISTA DE FIGURAS........................................................................................................................... 5

LISTA DE TABELAS .......................................................................................................................... 6

RESUMO............................................................................................................................................. 7

1 INTRODUÇÃO ........................................................................................................................... 8

1.1 MOTIVAÇÃO ................................................................................................8 1.2 OBJETIVOS DO TRABALHO...........................................................................9 1.3 METODOLOGIA APLICADA ............................................................................9 1.4 ESTRUTURA DO VOLUME...........................................................................10

2 FUNDAMENTAÇÃO TEÓRICA ............................................................................................... 11

2.1 TÉCNICAS DE AVALIAÇÃO DE DESEMPENHO ...............................................11 2.1.1 Monitoração.........................................................................................11 2.1.2 Simulação............................................................................................12 2.1.3 Métodos Analíticos ..............................................................................13

2.2 O FORMALISMO DE REDES DE AUTÔMATOS ESTOCÁSTICOS (SAN) ............15 2.2.1 Autômatos Estocásticos ......................................................................15 2.2.2 Estados Locais e Globais....................................................................15 2.2.3 Tipos de Transições entre os Estados ................................................16 2.2.4 Taxas e Probabilidades Funcionais ....................................................18 2.2.5 Descrição textual das SAN..................................................................20

3 MODELAGEM DE EXEMPLOS............................................................................................... 21

3.1 REDES DE FILAS DE ESPERA .....................................................................21 3.1.1 Modelo Básico Utilizando apenas Constantes ....................................23 3.1.2 Utilizando Probabilidades Funcionais .................................................25 3.1.3 Utilizando somente Eventos Sincronizantes .......................................27 3.1.4 Considerações sobre as Três Alternativas de Modelagem.................30

3.2 COMPARTILHAMENTO DE RECURSOS .........................................................31 3.2.1 Utilizando Eventos Sincronizantes ......................................................31

2

3.2.2 Utilizando apenas Funções .................................................................34 3.2.3 Considerações sobre as Duas Alternativas de Modelagem................35

3.3 O JANTAR DOS FILÓSOFOS .......................................................................38 3.3.1 Modelo Básico Utilizando Eventos Sincronizantes .............................40 3.3.2 Modelo Básico Utilizando Funções .....................................................42 3.3.3 Considerações sobre as Duas Alternativas de Modelagem Básica....44

3.4 JANTAR DOS FILÓSOFOS COM BEBIDAS......................................................47 3.4.1 Modelo com Bebidas Utilizando Eventos Sincronizantes ...................48 3.4.2 Extensão do Modelo Utilizando Funções ............................................51 3.4.3 Considerações sobre as duas Modelagens com as Bebidas..............53

4 CONCLUSÕES ........................................................................................................................ 56

5 ANEXOS................................................................................................................................... 60

3

L ISTA DE ABREVIATURAS

CPTS Centro de Pesquisa em Teste de Software

PEPS Performance Evaluation in Parallel Systems

PPGCC Programa de Pós-Graduação em Ciência da Computação

QN Queueing Networks (Redes de Filas de Espera)

SAN Stochastic Automata Networks (Redes de Autômatos Estocásticos)

TI 1 Trabalho Individual I

4

LISTA DE FIGURAS

Figura 1 – Exemplo de Redes de Autômatos Estocásticos (SAN) .....................................16 Figura 2 – Autômato equivalente à rede da Figura 1 .........................................................17 Figura 3 – Modelo SAN com transições funcionais ............................................................19 Figura 4 – Modelo exemplo de QN.....................................................................................22 Figura 5 – Modelo SAN para rede de filas de espera aberta .............................................24 Figura 6 – Redes de Filas de Espera com probabilidades funcionais................................26 Figura 7 - Redes de filas de espera com eventos sincronizantes ......................................29 Figura 8 - Compartilhamento de Recursos com Eventos Sincronizantes ..........................32 Figura 9 - Modelo SAN com funções para compartilhamento de recursos ........................34 Figura 10 – Análise dos Resultados da Modelagem com Eventos Sincronizantes............37 Figura 11 - Análise dos Resultados da Modelagem com Funções ....................................37 Figura 12 – Problema do Jantar dos Filósofos ...................................................................38 Figura 13 – Modelo SAN para o problema do Jantar dos Filósofos ...................................40 Figura 14 – Função de Atingibilidade para o “Jantar dos Filósofos” ..................................41 Figura 15 – Modelagem Alternativa para o Jantar dos Filósofos .......................................42 Figura 16 – Funções para as transições de requisição dos garfos ....................................43 Figura 17 - Análise dos Resultados da Modelagem com Eventos Sincronizantes.............46 Figura 18 - Análise dos Resultados da Modelagem com Funções ....................................46 Figura 19 – O Jantar dos Filósofos com Bebidas...............................................................47 Figura 20 – Modelo com Bebidas e Eventos Sincronizantes .............................................49 Figura 21 – Função de atingibilidade para o modelo com eventos sincronizantes ............50 Figura 22 – Modelo com Bebidas e Taxas Funcionais.......................................................51 Figura 23 – Funções definidas para as transições dos autômatos dos filósofos ...............52 Figura 24 – Função de Atingibilidade do modelo com Taxas Funcionais ..........................53

5

LISTA DE TABELAS

Tabela 1 – Parâmetros da QN estabelecidos para a modelagem textual ..........................22 Tabela 2 – Resultados para uma QN com uso de constantes ...........................................24 Tabela 3 – Resultados da modelagem utilizando Funções ................................................26 Tabela 4 – Probabilidades de Rotação para Filas 2 e 3.....................................................28 Tabela 5 – Resultados para rede de filas de espera com sincronizantes ..........................29 Tabela 6 – Quadro comparativo para QN Abertas .............................................................30 Tabela 7 – Taxas utilizadas para Compartilhamento de Recursos ....................................33 Tabela 8 – Características do modelo com eventos sincronizantes...................................33 Tabela 9 – Características do modelo utilizando funções ..................................................35 Tabela 10 – Compartilhamento de Recursos variando a quantidade de recursos.............36 Tabela 11 – Resultados do “Jantar dos Filósofos” com Eventos Sincronizantes...............41 Tabela 12 - Resultados do “Jantar dos Filósofos” com Funções .......................................44 Tabela 13 – “Jantar dos Filósofos” variando o número de filósofos ...................................45 Tabela 14 – Resultados do Modelo com Bebidas e Eventos Sincronizantes.....................50 Tabela 15 – Resultados para o modelo com Bebidas utilizando funções ..........................53 Tabela 16– Análise comparativa dos modelos com Bebidas .............................................54

6

RESUMO

Este trabalho apresenta uma visão geral do formalismo de Redes de Autômatos

Estocásticos (SAN) através da modelagem de exemplos e análise de diferentes formas de

descrição para os mesmos. Este formalismo permite a descrição de modelos onde

autômatos interagem uns com os outros através de primitivas de sincronismo e

paralelismo, como é o caso dos eventos sincronizantes e das taxas funcionais. O objetivo

deste trabalho é estabelecer uma análise comparativa destas duas formas de descrição

dos modelos, ressaltando suas vantagens e desvantagens. A modelagem de problemas

da realidade nos faz observar, dentre as alternativas de representação, as diversas

características particulares para modelar e solucionar estes problemas. As conclusões

nos permitem vislumbrar os benefícios e a aplicabilidade destas abordagens na busca de

desempenho e confiabilidade de sistemas complexos.

7

1 INTRODUÇÃO

A complexidade inerente às aplicações computacionais atuais tem tornado

essencial a utilização de técnicas de avaliação de desempenho. A escolha da técnica

mais adequada em uma determinada situação é um aspecto chave em qualquer projeto

ligado a esta área, e deve considerar alguns critérios como o estágio atual de

desenvolvimento do sistema, disponibilidade de tempo e de ferramentas para realizar a

avaliação, mas sobretudo o nível de precisão requerido nos resultados [10].

Um dos aspectos relevantes do uso destas técnicas é que, muitas vezes, pode ser

fundamental a avaliação dos resultados esperados de um projeto através de simulações e

estimativas de desempenho em situações de aplicação real, principalmente no âmbito do

desenvolvimento de sistemas paralelos e distribuídos. Esta perspectiva pode reduzir

substancialmente o tempo de projeto e desenvolvimento dos sistemas, avaliando o

desempenho de um sistema antes mesmo de implementá-lo [1,6].

1.1 Motivação

Existe uma grande variedade de técnicas de avaliação de desempenho

atualmente, porém para cada situação específica pode ser mais vantajoso utilizar uma ou

outra abordagem. Ou ainda, pode ser interessante utilizar-se de combinações entre estas

técnicas, buscando resultados mais efetivos em termos de avaliação de desempenho.

Contudo, dentre as muitas técnicas conhecidas, recentemente sobressaiu-se um

formalismo chamado Redes de Autômatos Estocásticos (SAN - Stochastic Automata

Networks) [2, 3, 4, 6], que vem com soluções numéricas mais eficientes do que as

alcançadas até agora com outros métodos analíticos. O estudo deste formalismo e a

experimentação com problemas reais tornam-se essenciais para atestar sua

aplicabilidade.

1.2 Objetivos do Trabalho

O formalismo SAN utiliza-se das noções de estado e de transições entre estados

para representação dos eventos. Estes eventos podem estar relacionados a um único

autômato, ou a vários ao mesmo tempo, ocorrendo de acordo com taxas específicas.

Para este segundo caso, existem duas possibilidades de representar eventos que são

disparados em mais de um autômato ao mesmo tempo, ou que dependem do estado de

outros autômatos para realizar uma determinada transição:

taxas funcionais;

eventos sincronizantes.

Dentro deste contexto optou-se, neste Trabalho Individual I, pelo estudo

aprofundado deste método analítico de avaliação de desempenho, o formalismo SAN,

modelando alguns estudos de caso selecionados. O objetivo desta pesquisa é fornecer

subsídios teóricos para futuros trabalhos, tanto na área de avaliação de desempenho,

quanto em projetos ligados ao PPGCC na área de teste e validação, como o projeto

CPTS (HP Brasil/PUCRS) – Centro de Pesquisa em Teste de Software.

1.3 Metodologia Aplicada

O método de pesquisa utilizado neste TI1 baseou-se na coleta de material relativo

à área de avaliação de desempenho de sistemas, enfatizando um dos métodos analíticos

(formalismo SAN). Posteriormente, este formalismo foi utilizado como base para modelar

alguns exemplos, e estes foram escolhidos e modelados diferentemente, tendo por

objetivo mostrar uma utilização mais prática do mesmo, explorando suas características

para a obtenção de soluções eficientes através da ferramenta PEPS2002 [9].

Os exemplos escolhidos foram:

Uma Rede de Filas de Espera Aberta;

Compartilhamento de Recursos;

Problema do “Jantar dos Filósofos”.

9

Todos estes exemplos serão abordados de forma a sugerir alternativas de

modelagem para os mesmos, ressaltando as vantagens e desvantagens das opções

escolhidas em relação ao tamanho do modelo e outras características que afetam o

desempenho.

1.4 Estrutura do Volume

Este trabalho foi dividido em dois grandes capítulos (2 e 3). O Capítulo 2 aborda

uma visão geral sobre a área de avaliação de desempenho descrevendo alguns tipos de

técnicas utilizadas atualmente, com ênfase no formalismo SAN que é o foco deste

trabalho. Basicamente será feita uma conceituação do formalismo, explicitando suas

características para modelagem de problemas da realidade e formas de representação

utilizando noções de sincronismo e paralelismo.

No Capítulo 3, os exemplos selecionados serão especificados e, posteriormente,

modelados utilizando o formalismo SAN. Nesta segunda parte, os eventos modelados e

os valores relacionados às suas taxas de ocorrência, serão discutidos e apresentados de

formas diferentes, demonstrando a versatilidade do formalismo.

Finalmente, nas conclusões serão colocadas as considerações finais deste

trabalho ressaltando a sua contribuição positiva em relação à divulgação do formalismo

SAN para a modelagem de realidades complexas. As conclusões englobam aspectos

relevantes das modelagens de exemplos realizadas no Capítulo 3 em relação às

alternativas de uso das características do formalismo. Em anexo, a este trabalho,

encontra-se o material relativo à modelagem completa dos exemplos apresentados, bem

como os resultados obtidos através da ferramenta PEPS2002.

10

2 FUNDAMENTAÇÃO TEÓRICA

Nas próximas seções teremos uma breve descrição de algumas técnicas de

avaliação de desempenho de sistemas, destacando algumas de suas vantagens e

desvantagens. Será dada uma atenção especial ao formalismo SAN, pois este é o foco de

estudo deste trabalho.

2.1 Técnicas de Avaliação de Desempenho

As técnicas de avaliação de desempenho são consideradas essenciais

atualmente, principalmente devido ao grande número de aplicações implementarem

características como paralelismo e sincronismo. Para exemplificar, pode-se citar

problemas clássicos como o de comunicação entre processos concorrentes, distribuição

de recursos disponíveis, entre outros. O fato é que estes tipos de problemas têm

ocasionado a ampliação do uso de métodos de análise e avaliação de desempenho, no

intuito de melhor realizarem seus propósitos [2, 10]. O uso de técnicas de avaliação de

desempenho pode, como citado anteriormente, reduzir consideravelmente o tempo gasto

com o desenvolvimento de sistemas, visto que possibilitam uma avaliação prévia do

desempenho dos mesmos.

As técnicas existentes podem ser divididas em três abordagens distintas:

monitoração, simulação e métodos analíticos. Segue uma visão geral de cada uma destas

abordagens, fazendo-se uma comparação entre as vantagens e aspectos negativos que

cada uma delas apresenta.

2.1.1 Monitoração

A técnica de monitoração, também chamada de experimentação direta, baseia-se

na simples observação de um sistema real em funcionamento. Apesar de apresentar

maior confiabilidade nos dados obtidos, pois não há abstração quanto ao funcionamento

11

do modelo, esta abordagem apresenta algumas desvantagens como alto custo e tempo

excessivo para uma aplicação confiável da técnica [1, 6, 10]. Além disto, este tipo de

abordagem supõe a existência física do sistema para que este possa ser avaliado.

Outro problema é que o sistema construído para obtenção das medidas pode

apresentar uma certa instabilidade visto que podem ocorrer influências externas não

esperadas. Além disto, com esta técnica é muito difícil replicar um experimento específico,

pois há uma imensa dificuldade em manter o controle das variáveis envolvidas no

experimento [1].

As amostras de funcionamento obtidas através da utilização desta abordagem, só

serão consideradas significativas se com técnicas estatísticas, devidamente utilizadas,

comprovar-se a representatividade das amostras obtidas [1, 6]. Esta desvantagem não é

exclusiva desta abordagem como será visto a seguir.

2.1.2 Simulação

A técnica de simulação consiste no desenvolvimento de um modelo que, como o

próprio nome caracteriza, simula o funcionamento do sistema real levando em

consideração as características funcionais do mesmo em uma escala de tempo adequada

à realidade.

Nesta abordagem deverá ser considerado um certo nível de abstração pois o

modelo não conterá a totalidade das características do sistema, somente as mais

relevantes [1, 6, 10]. Devido a este fato, os atributos devem ser cuidadosamente

selecionados e representados, para que não ocorram certos tipos de erros, normalmente

considerados como de modelagem. Da mesma forma, é necessário avaliar também, se

algumas características relevantes do sistema real foram desconsideradas

indevidamente.

Comparando-a com a primeira abordagem citada, esta tem o custo minimizado,

geralmente consome menos tempo para obter resultados similarmente significativos, mas

12

principalmente permite repetições de experimentos quantas vezes forem necessárias,

mantendo-se bastante estável, pois evita influências externas não previstas.

Nestas duas abordagens apresentadas até o momento, a quantidade e a

representatividade das amostras consideradas são relevantes para a obtenção de

resultados precisos através da aplicação de técnicas estatísticas sobre esta amostragem

[1, 6].

2.1.3 Métodos Analíticos

A técnica de análises ou métodos analíticos consiste em modelar um sistema real,

através das relações matemáticas existentes no funcionamento do sistema, ou seja, é

necessário um nível mais alto de abstração se comparada à abordagem anterior. Através

de relações matemáticas pode-se descrever o sistema como um conjunto de estados

possíveis e definir transições entre estes estados [1, 6]. Esta abordagem é considerada

bem mais complexa do que as anteriores, entretanto não é necessário que se obtenha um

conjunto específico de amostras de funcionamento do sistema modelado, como se

observa nas técnicas citadas anteriormente.

O princípio básico desta técnica é obter uma visão simplificada do sistema a ser

avaliado, o qual será denominado modelo. Para isto, utiliza-se de abstrações de alto nível

que fornecem o comportamento real do sistema, contendo características funcionais

suficientes para realizar uma avaliação segura, apesar de considerar um certo nível de

tolerância [1].

Existem diferentes métodos analíticos, mas os mais utilizados baseiam-se em

Cadeias de Markov [11] por se tratar de um formalismo matematicamente não tão

complexo e de modelagem rápida. Ou seja, o tempo para construção dos modelos

baseados em Cadeias de Markov é relativamente reduzido em relação às outras técnicas,

e a confiabilidade, em termos de ausência de erros de modelagem, é maior do que em

outros formalismos considerados mais complexos do que este [1, 11].

13

As Cadeias de Markov descrevem o funcionamento de um sistema através de um

conjunto de estados possíveis e de transições entre estes estados, seguindo taxas

definidas por leis exponenciais. Porém, um de seus aspectos negativos é que pode

ocorrer uma explosão do espaço de estados, o que torna intratável o modelo em particular

e, conseqüentemente, a matriz de transição correspondente [1, 11].

Outro formalismo, as Redes de Filas de Espera (QN – Queueing Networks) [1, 8],

surgiu no final dos anos 50, e é provavelmente o mais popular dos formalismos para

avaliação de desempenho via métodos analíticos, principalmente pela idéia de clientes e

filas (estações de serviço) que este formalismo introduz. QN são fáceis de modelar, e

além disto podem ser facilmente traduzidas para uma representação em Cadeias de

Markov. A desvantagem é que as duas técnicas sofrem limitações referentes ao espaço

total de estados gerado, pois quanto maior este for, mais difícil se torna a sua

representação [1].

Na década de 80, as Redes de Autômatos Estocásticos (SAN) introduzem um

formalismo com grande poder de resolução quando comparado às QN, além de

apresentar mecanismos de sincronismo e paralelismo. Uma das suas principais

características é prover soluções numéricas eficientes, evitando também os prejuízos da

explosão do espaço de estados das Cadeias de Markov, o que já representa uma grande

vantagem ao optar-se por sua utilização [2, 6].

Na próxima Seção serão abordados aspectos do formalismo SAN, para que

posteriormente sejam modelados alguns exemplos de problemas da realidade, verificando

a flexibilidade e a modularidade de representação através deste formalismo.

14

2.2 O Formalismo de Redes de Autômatos Estocásticos (SAN)

O formalismo de Redes de Autômatos Estocásticos, ou simplesmente SAN, é

baseado em Cadeias de Markov com grandes espaços de estados, e propicia uma forma

compacta e modular para descrever realidades complexas, contribuindo para a busca de

soluções numéricas mais eficazes. Logo, este formalismo mantém o poder de modelagem

que se tinha com as Cadeias de Markov, porém tem a vantagem de eliminar problemas

como o da explosão do espaço de estados [1, 4].

2.2.1 Autômatos Estocásticos

O princípio do formalismo SAN é descrever um sistema complexo dividindo-o em

subsistemas quase independentes, pois estes interagirão ocasionalmente [4, 6]. Neste

sistema, cada subsistema é modelado por um autômato [7].

Um autômato é um modelo matemático com entradas e saídas discretas, ou seja,

o sistema pode se encontrar em qualquer estado dentro de um número finito de estados

que compõem este sistema [2]. Nas SAN as interações entre os autômatos são

modeladas através de regras de transição específicas como veremos mais adiante. A

denominação de estocásticos atribuída aos autômatos, neste formalismo, deve-se ao fato

de que o tempo é tratado como uma variável aleatória com distribuição exponencial [1].

Nas próximas seções serão expostos alguns conceitos relacionados às SAN onde

poderemos observar como esta abordagem, dita modular, permite descrever primitivas de

paralelismo e sincronismo.

2.2.2 Estados Locais e Globais

O estado de um autômato resume toda a informação referente a seu passado, pois

as entradas passadas são necessárias para determinar qual será o próximo

comportamento adotado pelo autômato mediante novas entradas. Ou seja, para um

15

determinado conjunto de estados, um sistema poderá assumir somente um estado a cada

momento, e este estado irá variar de acordo com a nova entrada recebida [1, 2].

O estado individual de cada autômato é chamado de estado local. O estado global

de uma SAN é definido como a combinação de todos os estados locais de cada autômato

componente da SAN. A seguir veremos um exemplo em que estas definições poderão ser

entendidas.

2.2.3 Tipos de Transições entre os Estados

A Figura 1 modela um sistema através de dois autômatos estocásticos: o autômato

A(1) com três estados e o autômato A(2) com dois estados.

Figura 1 – Exemplo de Redes de Autômatos Estocásticos (SAN)

A cada unidade de tempo t transcorrida é possível verificar o estado em que cada

autômato modelado se encontra. Este estado é denominado estado local, sendo que no

autômato A(1) há a possibilidade de estarmos em apenas três estados (D, A ou S) e no

autômato A(2) em apenas dois estados (no estado I ou no estado O).

Ainda observando o exemplo acima, pode-se notar diferentes tipos de transições

entre os estados. Estas transições existentes em cada autômato podem ser divididas em

transições locais e transições sincronizadas. No exemplo, as transições locais recebem o

nome li e as transições sincronizadas ei.

16

As transições locais alteram o estado global pela mudança de um estado em

apenas um autômato, enquanto as transições sincronizadas alteram o estado global pela

mudança de estado em dois ou mais autômatos simultaneamente [1, 2, 6]. A vantagem

das transições locais é permitir que os autômatos tenham comportamentos paralelos

através de eventos locais, ou seja, elas mudam somente o estado local do autômato em

que ocorreram e não têm interferências por parte dos estados dos outros autômatos.

Apesar de os eventos serem ditos independentes, eles são disparados um de cada vez,

pois em uma escala de tempo contínua não ocorrem dois ou mais eventos ao mesmo

tempo [6].

As transições sincronizadas permitem que seja representado um certo sincronismo

no disparo de transições entre os autômatos, constituindo eventos sincronizantes entre os

mesmos [1]. Sua ocorrência se dá simultaneamente em todos os autômatos envolvidos,

pressupondo a existência de um autômato mestre, que coordenará a sincronização. Tem-

se então um ou mais autômatos escravos, estes disparados pelo mestre correspondente.

Para cada evento sincronizante têm-se a definição de um único autômato mestre, sendo

as transições, nos demais autômatos, do tipo escravo.

Cabe salientar, que um autômato pode ser mestre de um determinado evento

sincronizante e, ao mesmo tempo, escravo em relação a outro [1]. Vejamos a seguir o

autômato global equivalente à SAN visualizada anteriormente:

Figura 2 – Autômato equivalente à rede da Figura 1

17

O autômato representado na Figura 2, tem cada um dos seus estados como uma

dupla de estados locais de cada autômato da Figura 1. A configuração deste sistema a

cada instante definirá seu estado global. Da mesma forma, levando em consideração a

SAN da Figura 1, o estado global é dado pela combinação de todos os estados locais de

cada um dos dois autômatos constituintes da mesma.

2.2.4 Taxas e Probabilidades Funcionais

Os eventos sincronizantes representam as possíveis interações existentes entre

os autômatos, cujas taxas de ocorrência são, muitas vezes, constantes. Porém, existe

outra forma de representar estas interações: utilizando taxas e probabilidades funcionais.

Um outro tipo de denominação para as transições locais e sincronizadas é que

ambas podem ser chamadas de transições funcionais. Isto ocorrerá quando suas taxas

não forem constantes, ou seja, tem-se uma função do estado local de outros autômatos

da SAN, avaliada conforme os estados atuais do modelo. Logo, as taxas funcionais

podem ser colocadas tanto em transições locais como em transições sincronizadas (no

autômato mestre), e estas podem ser definidas por funções que refletem a avaliação dos

estados atuais da rede de autômatos estocásticos em questão.

Por exemplo, se no autômato A(2) quiséssemos representar uma transição local

funcional (dependente do estado interno do autômato A(1) ), teríamos, por exemplo, a

definição de uma função f como segue abaixo:

f =

AestadonoestánãoAse

AestadonoestáAse)1(

)1(1

0

λ

Temos então duas taxas de transição distintas dependendo do estado em que se

encontra o modelo. Vejamos a Figura 3:

18

Figura 3 – Modelo SAN com transições funcionais

Outra possibilidade dentro do formalismo é que para cada modelo pode-se definir

uma função de atingibilidade, que em poucas palavras, é uma função booleana que

determina os estados atingíveis do modelo dentro do espaço total de estados. Esta

função definirá, então, o espaço de estados atingível do modelo SAN. Quando esta for

igual a 1, significa que todos os estados do modelo são atingíveis. Normalmente, isto não

é o que acontece na prática, pois em exemplos da realidade facilmente identificamos

condições para que determinados eventos ocorram ou não, dentre estas o estado de

outros autômatos. Isto quer dizer que provavelmente quando estas condições não forem

cumpridas alguns estados globais terão probabilidade nula ou quase nula de ocorrerem.

Para o exemplo mostrado na Figura 1 podemos supor que quando o A(1) estiver no

estado A, o autômato A(2) deve estar no estado I, ou se o A(1) estiver no estado S, o

autômato A(2) deve estar no estado O, por exemplo. Para isto é definida a seguinte função

de atingibilidade:

));()((&))()((

)2()1(

)2()1(

OAstSAstIAstAAsttyreachabili

==→==

==→===

Como se pode notar, o uso de transições funcionais é uma primitiva poderosa do

formalismo SAN, permitindo a representação de comportamentos complexos de forma

bem mais compacta [2]. A demonstração desta característica do formalismo SAN será

19

realizada no Capítulo 3 através da modelagem dos exemplos, e posteriormente discutida

na conclusão deste trabalho.

2.2.5 Descrição textual das SAN

É possível que se faça uma descrição textual de cada SAN modelada

graficamente. Esta abordagem considera cada autômato como um grafo, onde seus

nodos são os estados e os arcos representam a ocorrência de eventos. A descrição

textual é muito simples, flexível, e permite a inserção rápida de novos módulos

(autômatos) ou mesmo a variação das características da rede. Também apresenta

estruturas para replicação de autômatos idênticos ou de blocos com mesmo

comportamento, otimizando ainda mais a representação do modelo.

O software que auxilia na modelagem deste formalismo é conhecido como

PEPS2002, e esta é a ferramenta que permite a avaliação de desempenho das realidades

modeladas através da descrição das SAN textualmente. Formalmente, as SAN são

descritas através de álgebra tensorial. Maiores informações a respeito podem ser

encontradas em [6].

A modelagem dos exemplos deste TI1 será realizada de forma gráfica e textual,

onde as descrições no formato para a gramática do software PEPS2002 encontram-se em

anexos ao final deste documento, bem como os arquivos de resultados gerados através

destes modelos.

20

3 MODELAGEM DE EXEMPLOS

Nesta Seção serão discutidos alguns exemplos modelados através de diferentes

perspectivas, demonstrando a flexibilidade do formalismo SAN. Cada exemplo modelado

apresenta pelo menos duas abordagens distintas de representação, permitindo a

realização de uma análise comparativa de seus aspectos relevantes e dos resultados

obtidos através da ferramenta PEPS2002. O método de solução utilizado para os

exemplos foi o da Potência [3], uma das opções oferecidas pela ferramenta.

Nas representações gráficas dos modelos ficaram implícitas as probabilidades de

ocorrência dos eventos quando estas eram iguais a 1, facilitando a visualização dos

parâmetros envolvidos em cada um dos exemplos. As representações completas dos

modelos no formato SAN, e os seus respectivos arquivos de resultados, encontram-se

nos anexos ao final deste documento.

3.1 Redes de Filas de Espera

As Redes de Filas de Espera (QN – Queueing Networks) são bastante utilizadas

por sua facilidade de modelagem. No entanto, os seus usuários sofrem com suas

limitações (QN à forma-produto) [11] que podem ser superadas representando-se este

modelo através do formalismo SAN, menos limitado em termos de poder de resolução [5].

O exemplo que será modelado consta de uma rede de filas de espera aberta, com

três estações de serviço, capacidade limitada e perda de clientes. A idéia básica é

transformar cada fila do modelo QN em um autômato estocástico no modelo SAN

equivalente. Vejamos na Figura 4, o modelo QN que será transformado em SAN:

21

Figura 4 – Modelo exemplo de QN

Neste exemplo temos três filas, onde todos os clientes entram através da fila 1 e

dividem-se posteriormente entre a fila 2 e a fila 3, com probabilidades π1 e π2,

respectivamente. Logo, apresenta:

σi como tempo médio de atendimento na fila i

Ki é o número máximo de clientes na fila i

Ci é o número de servidores na fila i

Segue abaixo uma tabela com os valores declarados nas modelagens textuais dos

exemplos da próxima Seção (Tabela 1):

F i l a i Σ i K i C i L i

1 0.4 10 1 2

2 0.5 5 2 0

3 0.2 5 1 0

Tabela 1 – Parâmetros da QN estabelecidos para a modelagem textual

Tem-se então três autômatos sendo o primeiro com 11 estados, estes referentes

ao total de clientes da fila 1 (10 clientes) mais o estado 0, correspondente a nenhum

cliente na fila. Este autômato será chamado de F(1). O segundo autômato representa a fila

2, e tem seis estados possíveis (5 clientes mais o estado 0) e é denominado F(2). O

terceiro autômato, assim como o anterior, apresenta também seis estados, pois também

representa uma fila de capacidade 5, ou seja, que comporta cinco clientes, chamado de

F(3).

22

A taxa de saída da fila 1 para a fila 2 será denominada de f12, e para a fila 3 de f 13,

sendo definidas da seguinte maneira:

f 12 = min (Ci , st F( i ) ) * π1

f 13 = min (Ci , st F( i ) ) * π2

No caso de f12 é extremamente necessária a utilização desta fórmula, pois é a

única fila que apresenta dois servidores, logo conforme o número de clientes presentes na

fila, a taxa pode sofrer variações. Nas outras situações, como o número de servidores é

igual a 1, a taxa permanece constante para todas as transições. Maiores informações a

respeito de QN podem ser encontradas em [1, 6 ].

Na próxima Seção abordaremos três opções de modelagem para este problema,

podendo visualizar a versatilidade do formalismo SAN em relação às diferentes formas de

declaração dos modelos e de suas taxas.

As modelagens textuais destes exemplos encontram-se em anexo no final deste

documento. Para todos estes modelos será definida a função de atingibilidade igual a um,

pois nas QN abertas todos os estados são atingíveis [1, 6], não havendo possibilidade de

que algum estado não ocorra.

3.1.1 Modelo Básico Utilizando apenas Constantes

O modelo SAN correspondente a este exemplo possui um autômato para cada fila

e um evento sincronizante para cada passagem possível de clientes entre as filas. Esta

sincronização entre dois autômatos em uma QN modela a saída de um cliente de uma

fila, e a chegada deste mesmo em outra fila.

Neste exemplo não foram utilizadas taxas funcionais, somente eventos

sincronizantes. Adotou-se também as seguintes probabilidades constantes: π1=60% e

π2=40%. Note que as chegadas de clientes na primeira fila e as saídas de clientes da

última fila são representadas por eventos locais, pois são independentes dos estados dos

23

demais autômatos. A saída de clientes da fila 2 ocorre a uma taxa µ2, e a saída de

clientes da fila 3 ocorre a uma taxa µ3. Vejamos abaixo na Figura 5:

Figura 5 – Modelo SAN para rede de filas de espera aberta

O autômato F(1) coordena a saída de clientes da fila 1 e a chegada de clientes nas

filas 2 e 3, ou seja, ele é o mestre desta sincronização na medida em que saem clientes,

sendo as outras duas filas, escravos nas transições que representam a chegada de

clientes em cada uma delas. Observemos agora os resultados obtidos com este modelo

(Tabela 2):

Total de Autômatos 3 autômatos Espaço de Estados 396 estados Total de Estados Atingíveis 396 estados Tamanho do Descritor Normalizado 5 Kbytes Número de Iterações Realizadas 1049 iterações Média de tempo de CPU por Iteração 0.000162 segundos

Tabela 2 – Resultados para uma QN com uso de constantes

24

Definindo a função de atingibilidade igual a 1, temos o tamanho do espaço de

estados igual ao total de estados atingíveis no modelo.

Na próxima Seção, modelaremos as mesmas filas, porém utilizaremos funções

para definir as probabilidades de passagem de clientes para as filas 2 e 3 ao invés de

utilizarmos constantes para π1 e π2.

3.1.2 Utilizando Probabilidades Funcionais

No modelo anterior utilizamos probabilidades constantes de os clientes da fila 1

migrarem para as filas 2 e 3. Porém é possível estabelecermos uma probabilidade

funcional nestas transições, e esta será variável conforme o fluxo destas duas filas

destino, balanceando a carga das mesmas. Vejamos a definição de π1 e π2 para esta

alternativa:

;112);132()13(1

πππ

−=+++= FilastFilastFilast

Estas funções definem que quanto mais clientes tivermos na fila 3 maior a

probabilidade dos clientes que saem da fila 1 irem para a fila 2 e vice-versa. Neste

modelo os eventos sincronizantes são representados por si e os eventos locais por ei.

Todas transições ocorrem através de eventos locais que obedecem a taxas de

ocorrência específicas (f12 e f 13) e probabilidades funcionais (π1 e π2). Observemos a

representação gráfica desta alternativa de modelagem (Figura 6):

25

Figura 6 – Redes de Filas de Espera com probabilidades funcionais

Após realizar a descrição textual deste modelo, obteve-se os seguintes resultados

no PEPS2002 (Tabela 3):


Tabela 3 – Resultados da modelagem utilizando Funções

Observou-se um aumento significativo do tempo por iteração nesta modelagem em

relação à anterior. Entretanto em termos de utilização da memória, o tamanho do descritor

da SAN não teve variações.

26

3.1.3 Utilizando somente Eventos Sincronizantes

Neste modelo utilizaremos apenas eventos sincronizantes entre os autômatos, e

estes definirão o fluxo de clientes que irão para a fila 2 e para a fila 3. O objetivo era

distribuir a carga entre as filas de forma a não sobrecarregar uma determinada fila. Como

o número total de transições e eventos sincronizantes para esta abordagem é muito

grande utilizou-se uma tabela de combinações de estados das filas 2 e 3 para facilitar a

representação gráfica posteriormente (Tabela 4):

i Fila 2 Fila 3 π1 π2

1 0 0 1 0

2 0 1 1 0

3 0 2 1 0

4 0 3 1 0

5 0 4 0.8 0.2

6 0 5 1 Não ocorre

7 1 0 0.5 0.5

8 1 1 0.67 0.33

9 1 2 0.75 0.25

10 1 3 0.8 0.2

11 1 4 0.83 0.17

12 1 5 0.86 Não ocorre

13 2 0 0.33 0.67

14 2 1 0.5 0.5

15 2 2 0.6 0.4

16 2 3 0.67 0.33

17 2 4 0.71 0.29


19 3 0 0.25 0.75

20 3 1 0.4 0.6

21 3 2 0.5 0.5

22 3 3 0.57 0.43

23 3 4 0.625 0.375

27


25 4 0 0.2 0.8

26 4 1 0.33 0.67

27 4 2 0.43 0.57

28 4 3 0.5 0.5

29 4 4 0.55 0.45


31 5 0 Não ocorre 0.83


33 5 2 Não ocorre 0.625



36 5 5 Não ocorre Não ocorre

Tabela 4 – Probabilidades de Rotação para Filas 2 e 3

Os eventos locais são representados por l ( i ). A nomenclatura estabelecida para

os eventos sincronizantes que ocorrem entre a fila 1 e a fila 2 é a seguinte:

(e i, π1), onde i é o número correspondente ao evento

correspondente na tabela construída (Tabela 1).

Para os eventos sincronizantes que ocorrem entre a fila 1 e a fila 3, temos:

(s i, π2), onde i é o número correspondente ao evento

correspondente na tabela construída (Tabela 1).

Para facilitar a implementação visto que temos muitas probabilidades a considerar,

assim como no modelo anterior, utilizamos as funções que representam π1 e π2. Segue

então a representação gráfica deste modelo (Figura 7):

28

Figura 7 - Redes de filas de espera com eventos sincronizantes

Os resultados obtidos com esta modelagem foram os seguintes (Tabela 5):


Tabela 5 – Resultados para rede de filas de espera com sincronizantes

Na próxima Seção será feita uma análise comparativa destes três modelos,

abordando os resultados obtidos nas três estratégias de descrição do problema.

29

3.1.4 Considerações sobre as Três Alternativas de Modelagem

As três abordagens implementam de diferentes maneiras a mesma QN Aberta, e

sobre estas podemos agora realizar uma análise dos resultados avaliando as vantagens e

desvantagens de cada alternativa de modelagem proposta através do quadro comparativo

abaixo (Tabela 6):

Com

Constantes

Com Taxas

Funcionais

Com Eventos

Sincronizantes Resultados Obtidos Aproximadamente

para

Redes De Filas de Espera Dados (100%) Dados (%) Dados (%)

Tempo Médio Gasto por Iteração (segundos) 0.000162 0.00152 938,27

(10x) 0.0237

14629,63

(150x)

Tamanho do Descritor Armazenado (Kbytes) 5 5 - 42 840

(8x)

Tabela 6 – Quadro comparativo para QN Abertas

Como a função de atingibilidade em todos os modelos não é diferente de um, pois

estamos tratando de QN abertas onde todos os estados são atingíveis, não faz sentido

tecermos considerações a respeito deste dado.

Porém, quanto a outros pontos avaliados, é notável o ganho em termos de espaço

de memória utilizado para armazenar o descritor normalizado das SAN que não utilizam

eventos sincronizantes. Tivemos o mesmo resultado com as modelagens com constantes

e com taxas funcionais em relação a este parâmetro, e estes foram significativamente

melhores do que com eventos sincronizantes, com tamanho relativamente oito vezes

menor. Quanto ao tempo médio por iteração observou-se que com taxas funcionais a

resolução foi dez vezes mais lenta do que com constantes, e a com eventos

sincronizantes cento e cinqüenta vezes mais lenta aproximadamente.

Nos próximos exemplos a serem modelados veremos como estes parâmetros

podem variar e como a complexidade do problema deve ser considerada no momento em

que se adota uma destas estratégias.

30

3.2 Compartilhamento de Recursos

O primeiro exemplo de modelagem escolhido é o clássico problema de

compartilhamento de recursos entre processos. Tem-se, então, N diferentes processos

compartilhando a utilização de R recursos idênticos entre si, onde qualquer processo

pode utilizar qualquer recurso, mas cada recurso só é utilizado por um único processo de

cada vez. Os processos podem refletir somente duas situações possíveis neste exemplo:

estar ou não usando algum recurso.

A representação dos processos foi realizada através da modelagem de autômatos

estocásticos – um para cada processo, totalizando N autômatos no modelo. Estes

autômatos foram modelados com dois estados cada um: o estado S (sleep) e o estado U

(using). Além disto, cada estado contém apenas um arco de saída, ou seja, existe uma

única transição (que sai do estado S e vai para o estado U) modelada para representar a

situação de requisição de um recurso, e uma transição que tem origem no estado U e

termina no estado S representando a liberação do recurso.

A partir de agora serão apresentadas duas alternativas para a modelagem deste

exemplo através do formalismo SAN:

uma utiliza apenas eventos sincronizantes entre os autômatos e,

a outra utiliza somente eventos locais e funções.

Considerou-se também que os processos têm diferentes taxas de requisição (λN) e

liberação (µN) dos recursos no intuito de prover uma representação mais fiel da realidade

proposta para análise.

3.2.1 Utilizando Eventos Sincronizantes

Como uma primeira alternativa de modelagem para este problema, teremos, além

dos N autômatos P que representam os processos, um autômato representando a

quantidade de recursos em utilização. Este autômato, que chamaremos de Recs (1), terá o

número de estados compatível com a quantidade de recursos disponíveis estabelecidos

para este exemplo. Porém torna-se necessária a adição de um estado para a situação

31

referente a nenhum recurso em utilização, isto porque não necessariamente teremos

sempre algum recurso sendo utilizado. Portanto, tem-se R+1 estados possíveis para este

autômato.

Para representar a interação entre os autômatos modelados, são utilizados apenas

eventos sincronizantes entre os autômatos P ( i ) e o autômato Recs(1). Vejamos a Figura 8:

Figura 8 - Compartilhamento de Recursos com Eventos Sincronizantes

Na modelagem textual, estabeleceu-se um total de doze processos (N=12)

compartilhando os recursos (a princípio, R=4), ou seja, o modelo representa doze

autômatos com dois estados cada um, e mais um autômato com cinco estados.

Os autômatos que representam os processos foram declarados mestres da

sincronização com os recursos, sendo estabelecidas as seguintes taxas de ocorrência

para as transições entre os estados destes autômatos (Tabela 7):

32

Autômatos P(N) P(1) P(2) P(3) P(4) P(5) P(6) P(7) P(8) P(9) P(10) P(11) P(12)

Taxas de Requisição (λN) 1 1 1 2 2 2 4 4 5 5 6 6

Taxas de Liberação (µN) 5 5 5 5 5 5 5 5 5 5 5 5

Tabela 7 – Taxas utilizadas para Compartilhamento de Recursos

Como podemos observar na descrição do modelo no Anexo I, uma função de

atingibilidade também é definida no intuito de manter a coerência entre os estados dos

autômatos P e o estado do autômato Recs, respeitando as limitações do modelo em

termos de quantidade de recursos disponíveis. Tem-se então que o somatório dos

autômatos P que estão no estado U deve ser coerente com o estado onde o autômato

Recs se encontra. Logo, a função de atingibilidade para este modelo pode ser:

))Re())(((1

)( csstUPstfN

i

i ===== ∑=

O espaço de estados atingíveis neste modelo é obtido através da função de

atingibilidade. Se neste exemplo a função de atingibilidade fosse f =1, significaria que

todos os estados seriam atingíveis. O espaço de estados total é obtido através do

produtório do total de estados de cada autômato. Segue abaixo uma tabela com algumas

das características deste modelo, obtidas através da ferramenta PEPS2002 (Tabela 8):

Total de Autômatos 13 autômatos Espaço de Estados 20480 estados Total de Estados Atingíveis 794 estados Tamanho do Descritor Normalizado 250 Kbytes Número de Iterações Realizadas 136 iterações Média de tempo de CPU porIteração 0.064 segundos

Tabela 8 – Características do modelo com eventos sincronizantes

Contudo, existe a possibilidade de modelarmos este exemplo sem a utilização de

eventos sincronizantes entre os autômatos podendo reduzir o espaço de estados total.

33

3.2.2 Utilizando apenas Funções

Neste exemplo será ilustrada a utilização de elementos funcionais em um modelo

sem eventos sincronizantes. O número de autômatos P que contêm estes dois estados

representará o número total de processos do modelo.

Figura 9 - Modelo SAN com funções para compartilhamento de recursos

Observando a Figura 9 nota-se que a liberação de um recurso é representada por

eventos locais que ocorrem, por exemplo, a uma taxa µN , e representam a transição

existente entre o estado U e o estado S em cada um dos autômatos. Já a requisição de

um recurso é modelada pelos eventos locais l , onde além da taxa de ocorrência λN,

tem-se também uma probabilidade funcional associada a este evento. Esta probabilidade

funcional é definida por:

)(1

Nl

)(2

N

))((1

)( RUPstfN

i

i <=== ∑=

Esta função retorna True (1) caso exista pelo menos um recurso disponível

(número de autômatos utilizando algum recurso é menor do que o total de recursos – R),

ou retorna False (0) no caso contrário.

As taxas de requisição e liberação dos recursos, respectivamente λN e µN, são

estabelecidas como constantes assim como na primeira abordagem apresentada. Além

disto, a função de atingibilidade deve ser redefinida de forma a continuar mantendo a

34

coerência entre os estados dos autômatos P e a quantidade de recursos disponíveis a

cada momento.

A função de atingibilidade declarada avaliará os autômatos de modo a garantir que

o número máximo de processos que estão utilizando os recursos seja equivalente à R

(número de recursos disponíveis). Logo a definição da função de atingibilidade para este

modelo é a que segue:

))((1

)( RUPstfN

i

i =<=== ∑=

Assim sendo, este modelo descreve toda a interação entre os autômatos através

do uso de probabilidades funcionais, sem a necessidade de utilização de eventos

sincronizantes, mesmo assim tendo os mesmos resultados obtidos anteriormente.

Vejamos a Tabela 9:


Tabela 9 – Características do modelo utilizando funções

Como podemos observar o espaço de estados total reduziu consideravelmente ao

excluirmos o autômato correspondente aos recursos. Nota-se que vários aspectos devem

ser considerados ao optarmos por uma ou outra alternativa de modelagem.

3.2.3 Considerações sobre as Duas Alternativas de Modelagem

Na primeira alternativa, o modelo representa 2N * (R+1) estados globais, sendo N

processos compartilhando R recursos. Porém nem todos estes são atingíveis devido à

definição de uma função de atingibilidade diferente de 1. Assim como, na segunda

abordagem, tem-se 2N estados globais.

35

O número de estados atingíveis para estes modelos com N processos

compartilhando R recursos será o mesmo independente da modelagem adotada,

considerando que as funções de atingibilidade definidas são semanticamente idênticas.

Tem-se então o número de estados atingíveis igual a:

, onde representa o número de combinações não ordenadas de i ∑=

N

i

NiC

0

NiC

elementos retirados de um conjunto contendo um total de N elementos.

Uma diferença notável entre estas abordagens é o espaço de estados total, visto

que na modelagem com eventos sincronizantes tem-se um autômato a mais a ser

considerado. Apesar do número de iterações realizado para solucionar os modelos seja o

mesmo nas duas alternativas, o tempo médio gasto por iteração foi reduzido no modelo

em que utilizamos funções, convergindo mais rapidamente para a solução do problema.

Alternativamente, foram modeladas algumas variações nestes exemplos

utilizando-se outras quantidades de recursos disponíveis para N processos (N=12),

podendo então realizar mais análises comparativas. Vejamos os resultados obtidos na

tabela abaixo (Tabela 10):

Com Eventos Sincronizantes Com Funções Resultados Obtidos

N processos (12) - R recursos R=1 R=4 R=8 R=11 R=1 R=4 R=8 R=11

Espaço de Estados Total (estados) 8192 20480 32768 49152 4096 4096 4096 4096

Espaço de Estados Atingíveis (estados) 13 794 3797 4095 13 794 3797 4095

Número de Iterações realizadas 134 136 150 155 134 136 150 155

Tempo Médio Gasto por Iteração (segundos) 0.022 0.070 0.113 0.175 0.048 0.049 0.049 0.051

Tamanho do Descritor Armazenado (Kbytes) 153 250 347 475 38 38 38 38

Tabela 10 – Compartilhamento de Recursos variando a quantidade de recursos

O número de iterações a serem realizadas não depende das escolhas de

modelagem, tanto com a utilização de eventos sincronizantes quanto com a utilização de

funções deve-se esperar o mesmo número de iterações. O que varia, na realidade, é o

tempo médio despendido em cada iteração. No caso da modelagem com eventos

sincronizantes com somente um único recurso disponível obtivemos um tempo melhor do

36

que o obtido em outras alternativas. Em todos os outros casos, a modelagem utilizando

funções mostrou um ganho significativo em termos de tempo de processamento.

Considerando o espaço de memória utilizado para armazenar o descritor dos

modelos, sem dúvida este tem relação direta com a quantidade de autômatos modelados

e seus respectivos conjuntos de estados, bem como com o tipo de evento escolhido para

cada transição. Observemos na Figura 10 um gráfico que mostra a variação dos valores

referentes ao espaço de estados total em relação aos estados atingíveis, para o modelo

com eventos sincronizantes:

Resultados Obtidos - Eventos Sincronizantes

8192

20480 3276849152

13

7943797

4095

1

10

100

1000

10000

100000

1 4 8 11

Total de Recursos

Espaço deEstados Total

Total deEstadosAtingíveis

Figura 10 – Análise dos Resultados da Modelagem com Eventos Sincronizantes

Comparativamente, a Figura 11 apresenta os valores referentes à modelagem com

funções:

Resultados Obtidos - Taxas Funcionais

40964096 4096 4096

13

7943797 4095

1

10

100

1000

10000

1 4 8 11Total de Recursos

Espaço deEstados Total

Total deEstadosAtingíveis

Figura 11 - Análise dos Resultados da Modelagem com Funções

37

Analisando os modelos pode-se concluir que para valores pequenos de R, temos o

espaço de estados atingíveis minimizado em relação ao número total de estados. Na

modelagem com funções o espaço total de estados não se altera, ou seja, é independente

do número de recursos utilizados, porém a quantidade de estados atingíveis varia assim

como no outro modelo. Logo, estes modelos são mais eficientes nos casos em que R não

é muito menor do que N.

Note que a representação completa destes autômatos e suas transições no

formato da gramática para a ferramenta PEPS2002 pode ser observada nos anexos ao

final deste documento. Cabe salientar, que a quantidade de recursos disponíveis e a

quantidade de processos existentes, podem ser ambas redefinidas alterando-se alguns

parâmetros de descrição nos arquivos SAN correspondentes.

3.3 O Jantar dos Filósofos

Este exemplo descreve o “Jantar dos Filósofos”, um problema clássico de

sincronização entre processos simultâneos. Supõe-se que existem cinco filósofos em

torno de uma mesa. Nesta mesa encontram-se apenas cinco garfos e cinco pratos cheios

de macarrão. A vida de um filósofo consiste em pensar e comer. Porém, para comer, cada

filósofo necessita de dois garfos, pois o macarrão é muito difícil de comer com um único

garfo. Assim, se um filósofo está comendo, seus dois vizinhos não podem comer. A

disposição dos filósofos e dos garfos na mesa ficará como segue (Figura 12):

Figura 12 – Problema do Jantar dos Filósofos

38

Neste problema são cinco filósofos, e estes serão representados por cinco

autômatos chamados de F, contendo três estados cada um: pensar (P), segurar o garfo

direito (D) e segurar o garfo esquerdo (E). A modelagem supõe que para comer, um

filósofo necessita efetivamente estar com dois garfos em mãos e, logo depois, voltar a

pensar liberando os dois garfos. As alternativas de modelagens que serão mostradas, a

seguir, sugerem diferentes soluções para garantir esta sincronização. Ressalta-se que a

escolha dos estados de cada autômato pode variar dependendo do nível de detalhe que

se deseja aplicar ao modelo, por exemplo, um quarto estado (C) representando o filósofo

comendo poderia ter sido incluído no modelo. Contudo considerou-se que quando um

filósofo estiver com os dois garfos em mãos, o tempo que o mesmo leva para libera-los já

pressupõe o tempo gasto comendo, não necessitando então modelar mais um estado.

O problema ocorre exatamente quando dois filósofos vizinhos ficam com fome e

tentam pegar o mesmo garfo para comer. Esta situação remonta o que ocorreria com dois

processos concorrentes que querem utilizar um mesmo recurso; se a sincronização não

for resolvida, estes processos poderão ficar em espera infinita, um pelo outro, situação

conhecida como deadlock. Para solucionar este problema, na modelagem dos autômatos

dos filósofos estabelece-se um filósofo “canhoto” que, ao contrário dos outros, segura

primeiro o garfo à sua esquerda e após o da direita.

As taxas que descrevem o tempo gasto pelos filósofos em cada um de seus

possíveis estados são as seguintes:

cada filósofo demora 2 u.t. (unidades de tempo) para segurar cada um dos

garfos que necessita, respectivamente;

um filósofo passa 4 u.t. comendo e, logo depois, solta os garfos e volta a

pensar.

Nas próximas seções, serão modeladas duas alternativas para o problema em

questão, uma utilizando eventos sincronizantes e outra com taxas funcionais.

39

3.3.1 Modelo Básico Utilizando Eventos Sincronizantes

Considerando a modelagem dos autômatos dos filósofos proposta na Seção

anterior, para solucionar a modelagem dos cinco garfos optou-se por um autômato para

cada garfo, cada um com dois estados (L e U, livre e em uso, respectivamente).

Além disto, esta alternativa de modelagem utilizará somente eventos

sincronizantes entre os autômatos, tanto para requisição dos garfos quanto para liberação

dos mesmos. Vejamos a Figura 13:

Figura 13 – Modelo SAN para o problema do Jantar dos Filósofos

Os autômatos dos filósofos foram definidos como mestres da sincronização da

requisição dos garfos utilizando uma taxa λ, sincronizando com a transição do estado L

para o estado U nos autômatos dos garfos. Já a liberação dos mesmos ocorrerá com taxa

µ, sendo os autômatos dos garfos os mestres nesta sincronização. Nota-se que o filósofo

representado pelo autômato F(5) é representado diferentemente dos demais, justamente

para contornar o problema da espera infinita pelo recurso, que neste caso é um garfo.

40

A função de atingibilidade definida garante que quando um filósofo estiver

comendo (no estado E, ou no D no caso de F(5)), os seus vizinhos não podem estar

comendo também. Da mesma forma que, para cada garfo, se um filósofo o tem, este não

poderá ser usado por outro filósofo ao mesmo tempo, apenas na liberação do mesmo.

Além disto, a função de atingibilidade apresenta condições que estabelecem os

estados possíveis dos garfos em relação aos demais autômatos: se um garfo está livre,

os filósofos que podem pegá-lo estão em estados que não correspondem à ação de pegar

este determinado garfo. Na Figura 14, podemos observar a função de atingibilidade

definida para este problema:

Reachability = ( (st F1 == E) -> ( (st F5 ==P) && (st F2 == P) ) ) && ( (st F2 == E) -> ( (st F1 != E) && (st F3 == P) ) ) && ( (st F3 == E) -> ( (st F2 != E) && (st F4 == P) ) ) && ( (st F4 == E) -> ( (st F3 != E )&& (st F5 != D) ) ) && ( (st F5 == D) -> ( (st F4 != E) && (st F1 == P) ) ) && ( (st F1 == D) -> (st F5 == P) ) && ( (st F2 == D) -> (st F1 != E) ) && ( (st F3 == D) -> (st F2 != E) ) && ( (st F4 == D) -> (st F3 != E) ) && ( (st F5 == E) -> (st F1 == P) ) && ( (st G1 == L) <-> ( (st F1 == P) && (st F5 == P) ) ) && ( (st G2 == L) <-> ( (st F2 == P) && (st F1 != E) ) ) && ( (st G3 == L) <-> ( (st F3 == P) && (st F2 != E) ) ) && ( (st G4 == L) <-> ( (st F4 == P) && (st F3 != E) ) ) && ( (st G5 == L) <-> ( (st F4 == P) && (st F5 == P) ) ) ;

Figura 14 – Função de Atingibilidade para o “Jantar dos Filósofos” Vejamos agora os resultados obtidos através da modelagem textual para a

ferramenta PEPS2002 (Tabela 11):

Total de Autômatos 10 autômatos Espaço de Estados 7776 Estados Total de Estados Atingíveis 70 Estados Tamanho do Descritor Normalizado 98 Kbytes Número de Iterações Realizadas 479 Iterações Média de tempo de CPU por Iteração 0.0479 segundos

Tabela 11 – Resultados do “Jantar dos Filósofos” com Eventos Sincronizantes

A próxima alternativa de modelagem será baseada em funções, tendo algumas

diferenças em termos de espaço de estados total e definição da função de atingibilidade.

41

3.3.2 Modelo Básico Utilizando Funções

A outra alternativa para modelagem deste problema é a utilização de taxas

funcionais em cada transição ao invés de utilizarmos eventos sincronizantes entre os

autômatos. Eliminam-se, neste caso, os autômatos que representavam os garfos, ficando

somente com os autômatos que representam os filósofos. Teremos, então, taxas

funcionais que verificam, para cada transição do autômato, os estados dos seus

autômatos vizinhos buscando saber se estes filósofos estão segurando os seus garfos ou

não.

A taxa de requisição (λ) e de liberação (µ) dos garfos será a mesma para todos os

filósofos, como na modelagem anterior. Porém para cada transição de requisição que

ocorrer nos autômatos, estas obedecerão a cada uma das funções definidas para tal

ocorrência multiplicada pela taxa de requisição λ estabelecida. A Figura 15 mostra a

representação gráfica desta abordagem:

Figura 15 – Modelagem Alternativa para o Jantar dos Filósofos

42

Estas taxas funcionais garantem que os filósofos só poderão comer se seus

vizinhos não estiverem comendo. Por exemplo (vide Figura 12 da Seção 3.3), F(1)

depende do estado de F(2) e de F(5), ou seja:

o filósofo F(2) não poderá estar com o garfo esquerdo em mãos;

e o filósofo F(5) não poderá estar segurando o garfo direito.

Vejamos como estas funções foram descritas textualmente para os filósofos no

formato SAN (Figura 16):

Filósofo F (1)

;*)(2;*)(1

)2(

)5(

λ

λ

PFstfPFstf

===

===

Filósofo F (2)

;*)(2;*)!(1

)3(

)1(

λ

λ

PFstfEFstf

===

==

Filósofo F (3)

;*)(2;*)!(1

)4(

)2(

λ

λ

PFstfEFstf

===

==

Filósofo F (4)

;*)!(2;*)!(1

)5(

)3(

λ

λ

DFstfDFstf==

==

Filósofo F (5)

;*)!(2;*)!(1

)4(

)1(

λ

λ

EFstfDFstf==

==

Figura 16 – Funções para as transições de requisição dos garfos

As funções f1 representam a ação de segurar o primeiro garfo e as f2 representam

que o filósofo estará com os dois garfos neste momento, podendo comer. A ordem de

requisição dos garfos depende do filósofo, pois como citado anteriormente, no autômato

F(5) representamos um filósofo “canhoto”.

A função de atingibilidade para este modelo é basicamente a mesma da

modelagem anterior, exceto pelas inserções relativas aos garfos, autômatos que foram

excluídos nesta segunda abordagem. Segue uma tabela que contém os resultados

obtidos através da descrição textual do modelo (Tabela 12):

43


Tabela 12 - Resultados do “Jantar dos Filósofos” com Funções

Na próxima seção serão discutidos os resultados obtidos com estas duas

modelagens para o problema, considerando-se que o espaço de estados atingíveis

manteve-se o mesmo já que as funções de atingibilidade declaradas nas duas alternativas

foram semanticamente idênticas, permitindo então a realização desta análise

comparativa.

3.3.3 Considerações sobre as Duas Alternativas de Modelagem Básica

O espaço de estados total foi reduzido com a modelagem através de funções pela

não necessidade de representação dos garfos através de autômatos. Além disto, como

citado anteriormente, a função de atingibilidade declarada em ambas modelagens é a

mesma em termos semânticos, garantindo o mesmo número de estados atingíveis. Esta

redução no número de autômatos ocasionou também a diminuição considerável do

espaço de memória a ser utilizado para armazenamento do descritor normalizado que

representa a rede.

A modelagem deste exemplo variando o número de filósofos e respectivos

recursos (garfos) foi realizada no intuito de melhor podermos visualizar as diferenças

existentes em termos de resultados obtidos quando se utiliza uma ou outra abordagem.

Vejamos a Tabela 13:

44


N- filósofos N=3 N=4 N=5 N=3 N=4 N=5

Espaço de Estados Total (estados) 216 1296 7776 27 81 243

Espaço de Estados Atingíveis ( estados) 12 27 70 12 27 70

Número de Iterações realizadas 210 294 479 210 294 400

Tempo Médio Gasto por Iteração (segundos) 0.0129 0.00112 0.0479 0 0.0000068 0.0002

Tamanho do Descritor Armazenado (Kbytes) 12 31 98 1 1 3

Tabela 13 – “Jantar dos Filósofos” variando o número de filósofos

Através da Tabela 13 pode-se perceber a economia em termos de espaço de

memória utilizado quando opta-se pela abordagem de taxas funcionais. Da mesma forma,

o espaço total de estados fica notavelmente reduzido, obtendo-se o mesmo número de

estados atingíveis que a abordagem por eventos sincronizantes.

Nota-se nestes exemplos que o tempo médio gasto por iteração, na abordagem

que se utiliza de taxas funcionais apresentou vantagens em relação à outra que se utiliza

apenas eventos sincronizantes. Porém, o número de iterações relativo à modelagem com

cinco filósofos não apresentou o mesmo resultado nas duas implementações propostas, o

que nos leva a considerar que exista alguma diferença nos próprios modelos, ou mesmo,

alguma limitação na ferramenta PEPS2002 para solucionar este modelo, não sendo

possível tecer conclusões definitivas com base somente neste caso específico.

Na Figura 17 temos um gráfico que mostra a variação dos valores referentes ao

espaço de estados total em relação aos estados atingíveis, para o modelo com eventos

sincronizantes:

45

Resultados Obtidos - Eventos Sincronizantes

77761296

21670

2712

1

10

100

1000

10000

3 4 5Total de Filósofos

Espaço de EstadosTotal

Total de EstadosAtingíveis

Figura 17 - Análise dos Resultados da Modelagem com Eventos Sincronizantes

Comparativamente, a Figura 18 apresenta os valores referentes à modelagem com

funções:

Resultados Obtidos - Taxas Funcionais

24381

27 7027

12

1

10

100

1000

3 4 5Total de Filósofos

Espaço de EstadosTotal

Total de EstadosAtingíveis

Figura 18 - Análise dos Resultados da Modelagem com Funções

Analisando os gráficos comparativos destes modelos pode-se concluir que quando

diminuímos o total de filósofos, temos o espaço de estados atingíveis mais próximo ao

número total de estados.

46

A representação completa destes autômatos e suas transições no formato da

gramática para a ferramenta PEPS2002 pode ser observada nos anexos ao final deste

documento.

3.4 Jantar dos Filósofos com Bebidas

O problema do “Jantar dos Filósofos” foi apresentado até o momento como um

conjunto de processos (filósofos) compartilhando cinco recursos de um único tipo (os

garfos). Porém as modelagens realizadas anteriormente agora serão estendidas com o

acréscimo de outros tipos de recursos – as bebidas. Portanto, teremos agora três tipos de

bebidas disponíveis B1, B2 e B3, uma de cada, sendo que qualquer filósofo pode requisitar

qualquer um destes novos recursos enquanto os mesmos estiverem no estado P, e o

recurso não estiver em uso por outro filósofo. Vejamos a Figura 19:

Figura 19 – O Jantar dos Filósofos com Bebidas

Assume-se, como na modelagem apresentada na seção anterior, que à esquerda

do filósofo F(1) temos o filósofo F(2), e à sua direita temos o filósofo F(5), estando o garfo

G(1) entre F(1) e F(5), e o garfo G(2) entre F(1) e F(2), assim por diante.

47

Para a modelagem dos novos autômatos e seus eventos no formato da gramática

para o PEPS2002, optou-se pelas seguintes taxas:

cada filósofo demora 2 u.t. (unidades de tempo) para conseguir uma

bebida;

um filósofo passa 2,5 u.t. bebendo e, logo depois solta a bebida, voltando a

pensar.

Cabe salientar que mais uma vez o problema será modelado através de duas

alternativas, apresentando posteriormente alguns resultados.

3.4.1 Modelo com Bebidas Utilizando Eventos Sincronizantes

Considerando a modelagem apresentada na Seção 3.3.1, serão acrescentados

três estados nos autômatos dos filósofos representando cada uma das possibilidades de

bebidas disponíveis. Além disto, os recursos (bebidas) serão modelados através de três

autômatos C( i ), sendo i = 1, 2 ou 3, com dois estados cada um (L e U), assim como os

autômatos dos garfos. O uso das taxas de requisição (fb) e liberação das bebidas (lb) foi

realizado através de eventos locais. Na descrição textual estas taxas foram definidas

como constantes atribuindo-se às mesmas o valor estabelecido na Seção 3.3.

48

Vejamos a representação gráfica da rede na Figura 20:

Figura 20 – Modelo com Bebidas e Eventos Sincronizantes

A função de atingibilidade definida para este exemplo segue a mesma idéia da

modelagem discutida na Seção 3.3.1, porém com o acréscimo de condições que

estabelecem mais alguns estados possíveis relacionados às bebidas. Ou seja, para

beber, um filósofo deve estar pensando previamente, podendo apenas consumir alguma

das três bebidas disponíveis se esta não estiver em mãos de outro filósofo. Observemos a

Figura 21:

49

reachability = . . . ((st F1 == B1)<-> ( (st F2!= B1) && (st F3!= B1) && (st F4!= B1) && (st F5!= B1) && (st C1 == U) ) ) && ((st F2 == B1)<-> ( (st F3!= B1) && (st F4!= B1) && (st F5!= B1) && (st F1!= B1) && (st C1 == U) ) ) && ((st F3 == B1)<-> ( (st F4!= B1) && (st F5!= B1) && (st F1!= B1) && (st F2!= B1) && (st C1 == U) ) ) && ((st F4 == B1)<-> ( (st F5!= B1) && (st F1!= B1) && (st F2!= B1) && (st F3!= B1) && (st C1 == U) ) ) && ((st F5 == B1)<-> ( (st F1!= B1) && (st F2!= B1) && (st F3!= B1) && (st F4!= B1) && (st C1 == U) ) ) && ((st F1 == B2)<-> ( (st F2!= B2) && (st F3!= B2) && (st F4!= B2) && (st F5!= B2) && (st C2 == U) ) ) && ((st F2 == B2)<-> ( (st F3!= B2) && (st F4!= B2) && (st F5!= B2) && (st F1!= B2) && (st C2 == U) ) ) && ((st F3 == B2)<-> ( (st F4!= B2) && (st F5!= B2) && (st F1!= B2) && (st F2!= B2) && (st C2 == U) ) ) && ((st F4 == B2)<-> ( (st F5!= B2) && (st F1!= B2) && (st F2!= B2) && (st F3!= B2) && (st C2 == U) ) ) && ((st F5 == B2)<-> ( (st F1!= B2) && (st F2!= B2) && (st F3!= B2) && (st F4!= B2) && (st C2 == U) ) ) && ((st F1 == B3)<-> ( (st F2!= B3) && (st F3!= B3) && (st F4!= B3) && (st F5!= B3) && (st C3 == U) ) ) && ((st F2 == B3)<-> ( (st F3!= B3) && (st F4!= B3) && (st F5!= B3) && (st F1!= B3) && (st C3 == U) ) ) && ((st F3 == B3)<-> ( (st F4!= B3) && (st F5!= B3) && (st F1!= B3) && (st F2!= B3) && (st C3 == U) ) ) && ((st F4 == B3)<-> ( (st F5!= B3) && (st F1!= B3) && (st F2!= B3) && (st F3!= B3) && (st C3 == U) ) ) && ((st F5 == B3)<-> ( (st F1!= B3) && (st F2!= B3) && (st F3!= B3) && (st F4!= B3) && (st C3 == U) ) ) && ( (st C1 == L) <-> ( nb B1(F1,F5)== 0) ) && ( (st C2 == L) <-> ( nb B2(F1,F5)== 0) ) && ( (st C3 == L) <-> ( nb B3(F1,F5)== 0) ) ;

Figura 21 – Função de atingibilidade para o modelo com eventos sincronizantes

Da mesma forma, os autômatos que representam as bebidas só estarão no estado

de uso (U) se apenas um filósofo estiver no estado “bebendo” relacionado a cada bebida.

Se estiverem no estado livre (L), nenhum filósofo estará bebendo naquele determinado

momento. Portanto, os resultados obtidos com este modelo são os seguintes (Tabela 14):


Tabela 14 – Resultados do Modelo com Bebidas e Eventos Sincronizantes

50

3.4.2 Extensão do Modelo Utilizando Funções

Assim como na modelagem da Seção 3.3.2, teremos cinco autômatos

representando os filósofos. Porém esta modelagem tem o acréscimo de outros recursos –

três tipos de bebidas disponíveis B1, B2 e B3, uma de cada, sendo que qualquer filósofo

pode requisitar qualquer um destes novos recursos enquanto os mesmos estiverem no

estado P, e o recurso não estiver em uso por outro filósofo.

Excluem-se, neste caso, os autômatos que representavam os garfos e as bebidas,

ficando somente com os autômatos que representam os filósofos. Teremos, então, taxas

funcionais que verificam, para cada transição do autômato, os estados dos seus

autômatos vizinhos buscando saber se estes filósofos estão segurando os seus garfos, ou

bebendo, ou pensando. A representação gráfica do modelo estendido fica como segue

(Figura 22):

Figura 22 – Modelo com Bebidas e Taxas Funcionais

A taxa de requisição (λ) e de liberação (µ) dos garfos será a mesma para todos os

filósofos, como na modelagem anterior. Porém para cada transição de requisição que

ocorrer nos autômatos, estas obedecerão a cada uma das funções definidas para tal

ocorrência multiplicada pela taxa de requisição λ estabelecida. As taxas de requisição (fb)

e liberação (lb) das bebidas também são utilizadas nas respectivas taxas funcionais.

51

Vejamos as taxas funcionais definidas para cada transição de cada autômato do

modelo (Figura 23):

Filósofo F (1)

;*))3(||)2(||)3(||)((2;*))3(||)2(||)3(||)((1

)2()2()2()2(

)5()5()5()5(

λλ

BFstBFstBFstPFstfBFstBFstBFstPFstf

=========

=========

Filósofo F (2)

;*))3(||)2(||)1(||)((2;*)!(1

)3()3()3()3(

)1(

λλ

BFstBFstBFstPFstfEFstf

=========

==

Filósofo F (3)

;*))3(||)2(||)1(||)((2;*)!(1

)4()4()4()4(

)2(

λλ

BFstBFstBFstPFstfEFstf

=========

==

Filósofo F (4)

;*)!(2;*)!(1

)5(

)3(

λλ

DFstfDFstf==

==

Filósofo F (5)

;*)!(2;*)!(1

)4(

)1(

λλ

EFstfDFstf

==

==

Bebidas (funções presentes em todos os filósofos)

fbBnbfbfbBnbfb

fbBnbfb

*)03(3*)02(2

*)01(1

=========

Figura 23 – Funções definidas para as transições dos autômatos dos filósofos

A função de atingibilidade é semanticamente idêntica à declarada no modelo

básico com funções deste problema. A diferença está que com o acréscimo destes três

novos estados em cada autômato, toda vez que um filósofo estiver pensando ele poderá

alternativamente passar para o estado bebendo se o recurso (bebida) estiver livre.

Observemos como é declarada a função de atingibilidade neste caso (Figura 24):

52

Reachability = ( (st F1 == E) -> ( (st F5 ==PP) && (st F2 == P) ) ) && ( (st F2 == E) -> ( (st F1 != E) && (st F3 == P) ) ) && ( (st F3 == E) -> ( (st F2 != E) && (st F4 == P) ) ) && ( (st F4 == E) -> ( (st F3 != E ) && (st F5 != DD) ) ) && ( (st F5 == DD) -> ( (st F4 != E) && (st F1 == P) ) ) && ( (st F1 == D) -> (st F3 == P) ) && ( (st F2 == D) -> (st F1 != E) ) && ( (st F3 == D) -> (st F2 != E) ) && ( (st F4 == D) -> (st F3 != E) ) && ( (st F5 == EE) -> (st F1 == P) )&& ((st F1 == B1)-> ((st F2!= B1) && (st F3!= B1)&& (st F4!= B1) && (st F5!= B1)) )&& ((st F2 == B1)-> ((st F3!= B1) && (st F4!= B1)&& (st F5!= B1) && (st F1!= B1)) )&& ((st F3 == B1)-> ((st F4!= B1) && (st F5!= B1)&& (st F1!= B1) && (st F2!= B1)) )&& ((st F4 == B1)-> ((st F5!= B1) && (st F1!= B1)&& (st F2!= B1) && (st F3!= B1)) )&& ((st F5 == B1)-> ((st F1!= B1) && (st F2!= B1)&& (st F3!= B1) && (st F4!= B1)) )&& ((st F1 == B2)-> ((st F2!= B2) && (st F3!= B2)&& (st F4!= B2) && (st F5!= B2)) )&& ((st F2 == B2)-> ((st F3!= B2) && (st F4!= B2)&& (st F5!= B2) && (st F1!= B2)) )&& ((st F3 == B2)-> ((st F4!= B2) && (st F5!= B2)&& (st F1!= B2) && (st F2!= B2)) )&& ((st F4 == B2)-> ((st F5!= B2) && (st F1!= B2)&& (st F2!= B2) && (st F3!= B2)) )&& ((st F5 == B2)-> ((st F1!= B2) && (st F2!= B2)&& (st F3!= B2) && (st F4!= B2)) )&& ((st F1 == B3)-> ((st F2!= B3) && (st F3!= B3)&& (st F4!= B3) && (st F5!= B3)) )&& ((st F2 == B3)-> ((st F3!= B3) && (st F4!= B3)&& (st F5!= B3) && (st F1!= B3)) )&& ((st F3 == B3)-> ((st F4!= B3) && (st F5!= B3)&& (st F1!= B3) && (st F2!= B3)) )&& ((st F4 == B3)-> ((st F5!= B3) && (st F1!= B3)&& (st F2!= B3) && (st F3!= B3)) )&& ((st F5 == B3)-> ((st F1!= B3) && (st F2!= B3)&& (st F3!= B3) && (st F4!= B3)) );

Figura 24 – Função de Atingibilidade do modelo com Taxas Funcionais

Os resultados obtidos com este modelo são os que seguem (Tabela 15):


Tabela 15 – Resultados para o modelo com Bebidas utilizando funções

A resolução do modelo terminou em um total de iterações divergente de seu

modelo similar que utiliza eventos sincronizantes, inclusive retorna um valor não numérico

como resultado. Estas diferenças e outras considerações serão colocadas analiticamente

na próxima Seção.

3.4.3 Considerações sobre as duas Modelagens com as Bebidas

53

As modelagens básicas com a inclusão de novos estados e autômatos para

representação dos novos recursos, as bebidas, sofreram um aumento significativo no

número total de estados. Porém, este espaço de estados total foi reduzido com a

modelagem através de funções pela não necessidade de representação dos autômatos

dos garfos dos autômatos das bebidas.

Um outro fator a ser considerado, como citado anteriormente, a função de

atingibilidade declarada em ambas as modelagens é a mesma em termos semânticos,

garantindo o mesmo número de estados atingíveis, independente da alternativa de

modelagem escolhida.

Nos modelos básicos da Seção anterior variamos o total de filósofos a fim de

comprovar as vantagens do uso de taxas funcionais ao invés de eventos sincronizantes

em casos como este, onde o número total de estados cresce radicalmente e em

conseqüência, o espaço de memória a ser utilizado é bem maior. Vejamos abaixo um

comparativo destas duas últimas modelagens realizadas (Tabela 16):


N- filósofos N=5 N=5

Espaço de Estados Total (estados) 1990656 7776

Espaço de Estados Atingíveis ( estados) 1093 1093

Número de Iterações realizadas 2790 1354

Tempo Médio Gasto por Iteração (segundos) 14.397 0.0352

Tamanho do Descritor Armazenado (Kbytes) 15715 63

Tabela 16– Análise comparativa dos modelos com Bebidas

É evidente a economia de memória obtida através da redução no número de

autômatos e eventos quando se utilizam taxas funcionais para representação das

transições entre os autômatos.

Um fator interessante que pode ser observado no arquivo de resultados do modelo

com taxas funcionais é que com esta modelagem em particular o modelo não convergiu

para um valor numérico, retornando “nan” (not a number) como resultado, isto indica que

talvez por algum problema de implementação do PEPS2002 este resultado foi obtido não

54

completando o mesmo número de iterações realizado no modelo com eventos

sincronizantes.

Logo, sabendo dos resultados obtidos nas modelagens básicas do problema

apresentadas na Seção 3.3 e analisando a Tabela 16, não se achou necessário avaliar

algumas variações para estes modelos, pois os modelos básicos descritos já serviram

para comprovar que dependendo da complexidade do problema e do tipo de interações

que são necessárias entre os autômatos, pode tornar-se muito trabalhosa a utilização de

eventos sincronizantes, bem como, muitas vezes, inviável em termos de limitações de

recursos físicos e/ou da própria ferramenta PEPS2002.

55

4 CONCLUSÕES

A utilização de Redes de Autômatos Estocásticos (o formalismo SAN) para a

avaliação de desempenho de sistemas tem sido largamente difundida desde os anos 80,

quando efetivamente iniciaram seu estudo e foram publicados diversos trabalhos na área,

tendo como resultado atualmente, o surgimento de aplicações desenvolvidas com o uso

desta técnica.

Dentro deste contexto, neste TI1 foi realizado um estudo deste método analítico,

modelando estudos de caso e enfocando principalmente na representação de eventos

dependentes de mais de um autômato para ocorrer. Como observamos no decorrer deste

trabalho, existem duas possibilidades de representar estes eventos: ou com a utilização

de eventos sincronizantes ou com o uso de taxas funcionais. Cada um dos exemplos

mostrados nas seções anteriores foi propositadamente modelado de diferentes maneiras

através do formalismo SAN, permitindo uma análise comparativa dos mesmos em relação

aos resultados obtidos com cada modelagem.

Concluiu-se que o uso de taxas funcionais proporcionou a redução da maioria dos

modelos em termos de espaço de estados total, pois evitou a modelagem de autômatos

extras para representar os problemas corretamente. Também substituiu, em alguns

casos, uma grande variedade de eventos sincronizantes necessários entre dois ou mais

autômatos, por um único evento local orientado pela taxa funcional definida.

Um fator importante a ser considerado é que em ambas alternativas de

representação pode-se chegar ao resultado esperado igualmente, porém para cada caso

pode ser melhor usar uma ou outra abordagem. Somado a estas vantagens, a utilização

de taxas funcionais proporciona uma redução considerável do espaço de memória

necessário para o armazenamento do descritor de cada SAN modelada. Entretanto,

existem parâmetros que não variam em decorrência da abordagem escolhida, como por

exemplo, o número de iterações e o total de estados atingíveis.

56

Utilizar eventos sincronizantes também pode ser uma boa escolha, principalmente

em problemas de menor de complexidade, pois a diferença numérica entre parâmetros

como tempo por iteração, tamanho em Kbytes do descritor normalizado e espaço de

estados total não chega a ser significativa. Além disto, dependendo do modelo descrito, a

utilização de eventos sincronizantes pode representá-lo mais claramente. Contudo, a

utilização de taxas funcionais não apresentou muitas desvantagens, pelo contrário,

mostrou-se uma alternativa eficiente para a solução de problemas complicados e que têm

um maior custo computacional.

Logo, a escolha correta, ou mais adequada para cada problema, depende

exclusivamente do tempo que pode ser despendido, dos recursos computacionais

disponíveis e da complexidade do problema a ser modelado.

57

REFERÊNCIAS CONSULTADAS

[1] L.Brenner. MQNA – Analisador de Redes de Filas de Espera Markovianas. Porto Alegre. Faculdade de Ciência da Computação da PUCRS.

2001. (Trabalho de Conclusão).

[2] B.Plateau, K.Atif. Stochastic automata networks for modelling parallel systems. IEEE transactions on software engineering, vol. 17, nr. 10. pág. 1093-

1108, 1991.

[3] B.Plateau, W.J.Stewart. Stochastic automata networks: product forms and iterative solutions. INRIA, Rapport de Recherche nr. 2939, 1996.

Anonymous ftp – ftp://ftp.inria.fr/INRIA/Publication/RR/RR-2939.ps.gz

[4] P.Fernandes, B.Plateau. Modeling Finite Capacity Queueing Networks with Stochatic Automata Networks. Fourth International Workshop on Queueing

Networks with Finite Capacity (QNETs 2000). Ilkley, West Yorkshire, UK. 20-21

July 2000. pág. 16/01-16/12.

[5] P.Fernandes, B.Plateau, W.J.Stewart. Efficient descriptor-vector multiplication in stochatic automata networks. Journal of the ACM, vol. 45, n. 3,

May 1998, pp. 381-414.

[6] P.Fernandes, C.G.P.Alegretti, R.Jungblut-Hessel. Avaliação de Desempenho de Sistemas através de redes de Autômatos Estocásticos. VII

ERI - Escola Regional de Informática. Novo Hamburgo - Chapecó - Londrina. 10-

14 maio. 1999. pág. 159-184.

[7] J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley, 1979.

58

[8] Avaliação Quantitativa de Sistemas. Página da disciplina no curso de

graduação em Ciência da Computação da Universidade Católica do Rio Grande do

Sul – PUCRS - http://www.inf.pucrs.br/~paulof/courses/aqs.html (último acesso em

03/07/2002).

[9] PEPS Projects: Performance Evaluation of Parallel Systems. http://www.apache.imag.fr/software/peps/ (último acesso em 26/06/2002)

[10] J.Raj. The Art of Computer Systems Performance Analysis – Techniques for Experimental Design, Measurement, Simulation, and Modeling. Digital Equipment Corporation - Litleton, Massachusetts. John Wiley &

Sons, Inc. 1991.

[11] W.J.Stewart. Introduction to numerical solutions of Markov chains. Princeton University Press, 1994.

59

http://www.apache.imag.fr/software/peps/

5 ANEXOS

ANEXO I – REDES DE FILAS DE ESPERA ABERTAS COM CONSTANTES

//===Redes de filas de espera ==================== identifiers { L1 = 2; //taxa de chegada na fila1 S1 = 0.4; //tempo de atendimento na fila1 S2 = 0.5; //tempo de atendimento na fila2 S3 = 0.2; //tempo de atendimento na fila3 pi1 = 0.6; //probabilidade de ir pra fila1 pi2 = 0.4; //probabilidade de ir pra fila2 F12 = pi1/S1; //taxa de saida de clientes da fila1 para a fila2 F13 = pi2/S1; //taxa de saida de clientes da fila1 para a fila3 F2out1s = 1/S2; //taxa de saida de clientes da fila2 so 1 servidor F2out2s = 2/S2; //taxa de saida de clientes da fila2 ambos servidores F3out= 1/S3; //taxa de saida de clientes da fila3 } reachability = 1; network rfe1 (continuous) { aut fila1 { stt n00 { trs (n01) {loc l (L1)} } stt n01 { trs (n02) {loc l (L1)} trs (n00) { mst s12 (F12) mst s13 (F13) } } stt n02 { trs (n03) {loc l (L1)} trs (n01) { mst s12 (F12) mst s13 (F13) } } stt n03 { trs (n04) {loc l (L1)} trs (n02) { mst s12 (F12) mst s13 (F13) } } stt n04 { trs (n05) {loc l (L1)} trs (n03) { mst s12 (F12) mst s13 (F13) } } stt n05 { trs (n06) {loc l (L1)} trs (n04) { mst s12 (F12) mst s13 (F13) } } stt n06 { trs (n07) {loc l (L1)} trs (n05) { mst s12 (F12) mst s13 (F13) } } stt n07 { trs (n08) {loc l (L1)} trs (n06) { mst s12 (F12) mst s13 (F13) } } stt n08 { trs (n09) {loc l (L1)} trs (n07) { mst s12 (F12) mst s13 (F13) } } stt n09 { trs (n10) {loc l (L1)} trs (n08) { mst s12 (F12)

mst s13 (F13) } } stt n10 { trs (n09) { mst s12 (F12) mst s13 (F13) } } } aut fila2 { stt n00 { trs (n01) {syn s12} } stt n01 { trs (n02) {syn s12} trs (n00) {loc l1s (F2out1s)} } stt n02 { trs (n03) {syn s12} trs (n01) {loc l2s (F2out2s)} } stt n03 { trs (n04) {syn s12} trs (n02) {loc l2s (F2out2s)} } stt n04 { trs (n05) {syn s12} trs (n03) {loc l2s (F2out2s)} } stt n05 { trs (n04) {loc l2s (F2out2s)} } } aut fila3 { stt n00 { trs (n01) {syn s13} } stt n01 { trs (n02) {syn s13} trs (n00) {loc l3 (F3out)} } stt n02 { trs (n03) {syn s13} trs (n01) {loc l3 (F3out)} } stt n03 { trs (n04) {syn s13} trs (n02) {loc l3 (F3out)} } stt n04 { trs (n05) {syn s13} trs (n03) {loc l3 (F3out)} } stt n05 { trs (n05) {syn s13} trs (n04) {loc l3 (F3out)} } // ultima linha indica q este evento s13 pode ocorrer apenas se fila3 cheia //perda que ocorre na fila3 } } results {} //Redes de filas de espera ==============================

61

ANEXO II – REDES DE FILAS DE ESPERA ABERTAS COM CONSTANTES (.TIM)

Os arquivos que seguem anexados referem-se aos resultados obtidos através da

ferramenta PEPS2002 a partir da modelagem textual dos exemplos.

=============================================================== File rfe_n.tim =============================================================== rfe_n.san -- A model with 3 automata and 2 events User name: 'rfe1' ------------ Problem Size ------------ Product state space: 396 states Reachable state space: 396 states Automata sizes: [ 11 6 6 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 5 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 1049 CPU average time per iteration: 0.0001620591039084843 seconds Total CPU time: 0.17 seconds ---------------------- Vector characteristics ---------------------- Name: rfe_n.vct Sum of all elements: 0.9999999999999591 Largest element: 0.0987703558964266 (in position 0) Smallest element: 5.01575432738734e-12 (in position 395) Residue after convergence: 9.827788582938979e-11 (the vector rfe_n.vct is the solution of the model rfe_n.san)

62

ANEXO III – REDES DE FILAS DE ESPERA ABERTAS COM PROBABILIDADES FUNCIONAIS

//===Redes de filas de espera ================ identifiers { L1 = 2; // taxa de chegada na fila 1 S1 = 0.4; // tempo de atendimento na fila 1 S2 = 0.5; // tempo de atendimento na fila 2 S3 = 0.2; // tempo de atendimento na fila 3 //probabilidades funcionais para ir pra fila2 ou fila3 pi1 = (st fila3 + 1)/(st fila2 + st fila3 +1); pi2 = 1 - pi1; F12 = pi1 / S1; // taxa de saida da fila1 para a fila2 F13 = pi2 / S1; // taxa de saida da fila1 para a fila3 F2out1s = 1/S2; // taxa de saida da fila2 so 1 servidor F2out2s = 2/S2; // taxa de saida da fila2 usando ambos servidores F3out = 1/S3; // taxa de saida de clientes da fila3 } reachability = 1; network rfe1 (continuous) { aut fila1 { stt n00 { trs (n01){loc l (L1)} } stt n01 { trs (n02){loc l (L1)} trs (n00){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n02 { trs (n03){loc l (L1)} trs (n01){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n03 { trs (n04){loc l (L1)} trs (n02){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n04 { trs (n05){loc l (L1)} trs (n03){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n05 { trs (n06){loc l (L1)} trs (n04){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n06 { trs (n07){loc l (L1)} trs (n05){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n07 { trs (n08){loc l (L1)} trs (n06){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n08 { trs (n09){loc l (L1)} trs (n07){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n09 { trs (n10){loc l (L1)} trs (n08){mst s12 (F12, pi1) mst s13 (F13, pi2) } } stt n10 { trs (n09){mst s12 (F12, pi1) mst s13 (F13, pi2) } } }

63

aut fila2 { stt n00 { trs (n01) {syn s12} } stt n01 { trs (n02) {syn s12} trs (n00) {loc l1s (F2out1s)} } stt n02 { trs (n03) {syn s12} trs (n01) {loc l2s (F2out2s)} } stt n03 { trs (n04) {syn s12} trs (n02) {loc l2s (F2out2s)} } stt n04 { trs (n05) {syn s12} trs (n03) {loc l2s (F2out2s)} } stt n05 { trs (n04) {loc l2s (F2out2s)} } } aut fila3 { stt n00 { trs (n01) {syn s13} } stt n01 { trs (n02) {syn s13} trs (n00) {loc l3 (F3out)} } stt n02 { trs (n03) {syn s13} trs (n01) {loc l3 (F3out)} } stt n03 { trs (n04) {syn s13} trs (n02) {loc l3 (F3out)} } stt n04 { trs (n05) {syn s13} trs (n03) {loc l3 (F3out)} } stt n05 { trs (n05) {syn s13} trs (n04) {loc l3 (F3out)} } // ultima linha indica q este evento s13 pode ocorrer apenas se fila3 cheia // perda que ocorre na fila3 } } results { } //Redes de filas de espera ==============================

64

ANEXO IV – REDES DE FILAS DE ESPERA ABERTAS COM PROBABILIDADES FUNCIONAIS (.TIM)


ferramenta PEPS2002 a partir da modelagem textual dos exemplos.

=============================================================== File rfe2_n.tim =============================================================== rfe2_n.san -- A model with 3 automata and 2 events User name: 'rfe1' ------------ Problem Size ------------ Product state space: 396 states Reachable state space: 396 states Automata sizes: [ 11 6 6 ] Automata sizes after aggregation: [ ] Current Number of Functions: 2 Size of the Normalized Descriptor: 5 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 1328 CPU average time per iteration: 0.001521084337349398 seconds Total CPU time: 2.02 seconds ---------------------- Vector characteristics ---------------------- Name: rfe_n.vct Sum of all elements: 1.000000000000072 Largest element: 0.08786410225977612 (in position 360) Smallest element: 1.742262478430597e-12 (in position 359) Residue after convergence: 9.850401489494912e-11 (the vector rfe_n.vct is the solution of the model rfe2_n.san)

65

ANEXO V – REDES DE FILAS DE ESPERA ABERTAS COM EVENTOS SINCRONIZANTES

//===Redes de filas de espera ==================== identifiers { L1 = 2; // taxa de chegada na fila 1 S1 = 0.4; // tempo de atendimento na fila 1 S2 = 0.5; // tempo de atendimento na fila 2 S3 = 0.2; // tempo de atendimento na fila 3 //probabilidades funcionais para ir pra fila2 ou fila3 pi1 = (st fila3 + 1)/(st fila2 + st fila3 +1); pi2 = 1 - pi1; F2out1s = 1 / S2; // taxa de saida da fila2 usando so 1 servidor F2out2s = 2 / S2; // taxa de saida da fila2 usando ambos servidores F3out = 1 / S3; // taxa de saida de clientes da fila3 } reachability = 1; network rfe1 (continuous) { aut fila1 { stt n00 { trs(++) { loc l1 (L1)} } stt n[9] { trs(++) { loc l1 (L1)} trs(--) { mst e1 (1, pi1) mst e2 (1, pi1) mst e3 (1, pi1) mst e4 (1, pi1) mst e5 (1, pi1) mst e6 (1, pi1) mst e7 (1, pi1) mst e8 (1, pi1) mst e9 (1, pi1) mst e10 (1, pi1) mst e11 (1, pi1) mst e12 (1, pi1) mst e13 (1, pi1) mst e14 (1, pi1) mst e15 (1, pi1) mst e16 (1, pi1) mst e17 (1, pi1) mst e18 (1, pi1) mst e19 (1, pi1) mst e20 (1, pi1) mst e21 (1, pi1) mst e22 (1, pi1) mst e23 (1, pi1) mst e24 (1, pi1) mst e25 (1, pi1) mst e26 (1, pi1) mst e27 (1, pi1) mst e28 (1, pi1) mst e29 (1, pi1) mst e30 (1, pi1) mst s1 (1, pi2) mst s2 (1, pi2) mst s3 (1, pi2) mst s4 (1, pi2) mst s5 (1, pi2) mst s7 (1, pi2) mst s8 (1, pi2) mst s9 (1, pi2) mst s10 (1, pi2) mst s11 (1, pi2) mst s13 (1, pi2) mst s14 (1, pi2) mst s15 (1, pi2) mst s16 (1, pi2) mst s17 (1, pi2) mst s19 (1, pi2) mst s20 (1, pi2) mst s21 (1, pi2) mst s22 (1, pi2) mst s23 (1, pi2) mst s25 (1, pi2) mst s26 (1, pi2) mst s27 (1, pi2) mst s28 (1, pi2) mst s29 (1, pi2) mst s31 (1, pi2) mst s32 (1, pi2) mst s33 (1, pi2) mst s34 (1, pi2) mst s35 (1, pi2) } } stt n10 { trs(--) { mst e1 (1, pi1) mst e2 (1, pi1) mst e3 (1, pi1) mst e4 (1, pi1) mst e5 (1, pi1) mst e6 (1, pi1) mst e7 (1, pi1) mst e8 (1, pi1) mst e9 (1, pi1) mst e10 (1, pi1) mst e11 (1, pi1) mst e12 (1, pi1) mst e13 (1, pi1) mst e14 (1, pi1) mst e15 (1, pi1) mst e16 (1, pi1) mst e17 (1, pi1) mst e18 (1, pi1) mst e19 (1, pi1) mst e20 (1, pi1) mst e21 (1, pi1) mst e22 (1, pi1) mst e23 (1, pi1) mst e24 (1, pi1) mst e25 (1, pi1) mst e26 (1, pi1) mst e27 (1, pi1) mst e28 (1, pi1) mst e29 (1, pi1) mst e30 (1, pi1) mst s1 (1, pi2) mst s2 (1, pi2) mst s3 (1, pi2) mst s4 (1, pi2) mst s5 (1, pi2) mst s7 (1, pi2) mst s8 (1, pi2) mst s9 (1, pi2) mst s10 (1, pi2) mst s11 (1, pi2) mst s13 (1, pi2) mst s14 (1, pi2) mst s15 (1, pi2) mst s16 (1, pi2) mst s17 (1, pi2) mst s19 (1, pi2) mst s20 (1, pi2) mst s21 (1, pi2) mst s22 (1, pi2) mst s23 (1, pi2) mst s25 (1, pi2) mst s26 (1, pi2) mst s27 (1, pi2) mst s28 (1, pi2) mst s29 (1, pi2) mst s31 (1, pi2) mst s32 (1, pi2) mst s33 (1, pi2) mst s34 (1, pi2) mst s35 (1, pi2) } } }

66

aut fila2 { stt n00 { trs(n00) { syn s1 syn s2 syn s3 syn s4 syn s5 } trs(n01) { syn e1 syn e2 syn e3 syn e4 syn e5 syn e6 } } stt n01 { trs(n00) { loc l1 (F2out1s) } trs(n01) { syn s7 syn s8 syn s9 syn s10 syn s11 } trs(n02) { syn e7 syn e8 syn e9 syn e10 syn e11 syn e12 } } stt n02 { trs(n01) { loc l1 (F2out2s) } trs(n02) { syn s13 syn s14 syn s15 syn s16 syn s17 } trs(n03) { syn e13 syn e14 syn e15 syn e16 syn e17 syn e18 } } stt n03 { trs(n02) { loc l1 (F2out2s) } trs(n03) { syn s19 syn s20 syn s21 syn s22 syn s23 } trs(n04) { syn e19 syn e20 syn e21 syn e22 syn e23 syn e24 } } stt n04 { trs(n03) { loc l1 (F2out2s) } trs(n04) { syn s25 syn s26 syn s27 syn s28 syn s29 } trs(n05) { syn e25 syn e26 syn e27 syn e28 syn e29 syn e30 } } stt n05 { trs(n04) { loc l1 (F2out2s) } trs(n05) { syn s31 syn s32 syn s33 syn s34 syn s35 } } } aut fila3 { stt n00 { trs(n00) { syn e1 syn e7 syn e13 syn e19 syn e25 } trs(n01) { syn s1 syn s7 syn s13 syn s19 syn s25 syn s31 } } stt n01 { trs(n00) { loc l1 (F3out) } trs(n01) { syn e2 syn e8 syn e14 syn e20 syn e26 } trs(n02) { syn s2 syn s8 syn s14 syn s20 syn s26 syn s32 } } stt n02 { trs(n01) { loc l1 (F3out) } trs(n02) { syn e3 syn e9 syn e15 syn e21 syn e27 } trs(n03) { syn s3 syn s9 syn s15 syn s21 syn s27 syn s33 } }

67

stt n03 { trs(n02) { loc l1 (F3out) } trs(n03) { syn e4 syn e10 syn e16 syn e22 syn e28 } trs(n04) { syn s4 syn s10 syn s16 syn s22 syn s28 syn s34 } } stt n04 { trs(n03) { loc l1 (F3out) } trs(n04) { syn e5 syn e11 syn e17 syn e23 syn e29 } trs(n05) { syn s5 syn s11 syn s17 syn s23 syn s29 syn s35 } } stt n05 { trs(n04) { loc l1 (F3out) } trs(n05) { syn e6 syn e12 syn e18 syn e24 syn e30 } } } } results { } //Redes de filas de espera ===========

68

ANEXO VI – REDES DE FILAS DE ESPERA ABERTAS COM EVENTOS SINCRONIZANTES (.TIM)


ferramenta PEPS2002 através da modelagem textual dos exemplos.

=============================================================== File rfe3_n.tim =============================================================== rfe3_n.san -- A model with 3 automata and 60 events User name: 'rfe1' ------------ Problem Size ------------ Product state space: 396 states Reachable state space: 396 states Automata sizes: [ 11 6 6 ] Automata sizes after aggregation: [ ] Current Number of Functions: 2 Size of the Normalized Descriptor: 42 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 779 CPU average time per iteration: 0.02372272143774069 seconds Total CPU time: 18.48 seconds ---------------------- Vector characteristics ---------------------- Name: rfe3_n.vct Sum of all elements: 1.000000000000043 Largest element: 0.4078433560331646 (in position 360) Smallest element: 1.233157403181014e-12 (in position 323) Residue after convergence: 9.646062225886209e-11 (the vector rfe3_n.vct is the solution of the model rfe3_n.san)

69

ANEXO VII – COMPARTILHAMENTO DE RECURSOS COM EVENTOS SINCRONIZANTES

//===Compartilhamento de Recursos identifiers{ //taxas de liberacao dos recursos mu1 = 5; mu2 = 5; mu3 = 5; mu4 = 5; mu5 = 5; mu6 = 5; mu7 = 5; mu8 = 5; mu9 = 5; mu10 = 5; mu11 = 5; mu12 = 5; //taxas de requisicao dos recursos lambda1 = 1; lambda2 = 1; lambda3 = 1; lambda4 = 2; lambda5 = 2; lambda6 = 2; lambda7 = 4; lambda8 = 4; lambda9 = 5; lambda10 = 5; lambda11 = 6; lambda12 = 6; } reachability = (nb u (p1,p12)== st recs); // coerencia entre o estado dos processos p e // o estado dos recursos r, respeitando as limitacoes de recursos. network cr2 (continuous) { aut p1{ stt s {trs (u){mst req1 (lambda1) } } stt u {trs (s){mst lib1 (mu1) } } } aut p2{ stt s {trs (u){mst req2 (lambda2) } } stt u {trs (s){mst lib2 (mu2) } } } aut p3{ stt s {trs (u){mst req3 (lambda3) } } stt u {trs (s){mst lib3 (mu3) } } } aut p4{ stt s {trs (u){mst req4 (lambda4) } } stt u {trs (s){mst lib4 (mu4) } } } aut p5{ stt s {trs (u){mst req5 (lambda5) } } stt u {trs (s){mst lib5 (mu5) } } } aut p6{ stt s {trs (u){mst req6 (lambda6) } } stt u {trs (s){mst lib6 (mu6) } } }

70

aut p7{ stt s {trs (u){mst req7 (lambda7) } } stt u {trs (s){mst lib7 (mu7) } } } aut p8{ stt s {trs (u){mst req8 (lambda8) } } stt u {trs (s){mst lib8 (mu8) } } } aut p9{ stt s {trs (u){mst req9 (lambda9) } } stt u {trs (s){mst lib9 (mu9) } } } aut p10{ stt s {trs (u){mst req10 (lambda10) } } stt u {trs (s){mst lib10 (mu10) } } } aut p11{ stt s {trs (u){mst req11 (lambda11) } } stt u {trs (s){mst lib11 (mu11) } } } aut p12{ stt s {trs (u){mst req12 (lambda12) } } stt u {trs (s){mst lib12 (mu12) } } } //recursos (0..4) aut recs { stt n00 { trs (++) { syn req1 syn req2 syn req3 syn req4 syn req5 syn req6 syn req7 syn req8 syn req9 syn req10 syn req11 syn req12 } } stt n[3] { trs (--) { syn lib1 syn lib2 syn lib3 syn lib4 syn lib5 syn lib6 syn lib7 syn lib8 syn lib9 syn lib10 syn lib11 syn lib12 } trs (++) { syn req1 syn req2 syn req3 syn req4 syn req5 syn req6 syn req7 syn req8 syn req9 syn req10 syn req11 syn req12 } } stt n4 { trs (--) { syn lib1 syn lib2 syn lib3 syn lib4 syn lib5 syn lib6 syn lib7 syn lib8 syn lib9 syn lib10 syn lib11 syn lib12 } } } } results { } //Compartilhamento de Recursos ==============================

71

ANEXO VIII – COMPARTILHAMENTO DE RECURSOS COM EVENTOS SINCRONIZANTES (.TIM)


ferramenta PEPS2002 a partir da implementação com 1, 4, 8 e 11 recursos através de

eventos sincronizantes.

=============================================================== File cr2a_n.tim =============================================================== cr2a_n.san -- A model with 13 automata and 24 events User name: 'cr2' ------------ Problem Size ------------ Product state space: 8192 states Reachable state space: 13 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 153 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 134 CPU average time per iteration: 0.02283582089552239 seconds Total CPU time: 3.06 seconds ---------------------- Vector characteristics ---------------------- Name: cr2a_n.vct Sum of all elements: 1.000000000000002 Largest element: 0.1363636356890721 (in position 3) Smallest element: 0.02272727327918923 (in position 1025) Residue after convergence: 8.64826474322733e-11 (the vector cr2a_n.vct is the solution of the model cr2a_n.san)

72

=============================================================== File cr2_n.tim =============================================================== cr2_n.san -- A model with 13 automata and 24 events User name: 'cr2' ------------ Problem Size ------------ Product state space: 20480 states Reachable state space: 794 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 5 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 250 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 136 CPU average time per iteration: 0.07066176470588235 seconds Total CPU time: 9.609999999999999 seconds ---------------------- Vector characteristics ---------------------- Name: cr2_n.vct Sum of all elements: 1.000000000000004 Largest element: 0.008803591510794373 (in position 17) Smallest element: 1.956355416533086e-05 (in position 19204) Residue after convergence: 8.860561514102e-11 (the vector cr2_n.vct is the solution of the model cr2_n.san)

=============================================================== File cr2b_n.tim =============================================================== cr2b_n.san -- A model with 13 automata and 24 events User name: 'cr2' ------------ Problem Size ------------ Product state space: 36864 states Reachable state space: 3797 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 9 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 379 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 150 CPU average time per iteration: 0.1256666666666667 seconds Total CPU time: 18.85 seconds ---------------------- Vector characteristics ----------------------

73

Name: cr2b_n.vct Sum of all elements: 0.9999999999999938 Largest element: 0.004864875811073158 (in position 29) Smallest element: 1.107030720830608e-06 (in position 36728) Residue after convergence: 8.512355349678952e-11 (the vector cr2b_n.vct is the solution of the model cr2b_n.san)

=============================================================== File cr2c_n.tim =============================================================== cr2c_n.san -- A model with 13 automata and 24 events User name: 'cr2' ------------ Problem Size ------------ Product state space: 49152 states Reachable state space: 4095 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 12 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 475 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 155 CPU average time per iteration: 0.1752258064516129 seconds Total CPU time: 27.16 seconds ---------------------- Vector characteristics ---------------------- Name: cr2c_n.vct Sum of all elements: 1.000000000000004 Largest element: 0.004841555292993071 (in position 38) Smallest element: 1.101723949667889e-06 (in position 49114) Residue after convergence: 8.331290757106202e-11 (the vector cr2c_n.vct is the solution of the model cr2c_n.san)

74

ANEXO IX – COMPARTILHAMENTO DE RECURSOS COM TAXAS FUNCIONAIS (.SAN)

//Compartilhamento de Recursos ===================== identifiers{ recs = 4; //total de recursos //taxas de liberacao dos recursos mu1 = 5; mu2 = 5; mu3 = 5; mu4 = 5; mu5 = 5; mu6 = 5; mu7 = 5; mu8 = 5; mu9 = 5; mu10 = 5; mu11 = 5; mu12 = 5; //taxas de requisicao dos recursos lambda1 = 1; lambda2 = 1; lambda3 = 1; lambda4 = 2; lambda5 = 2; lambda6 = 2; lambda7 = 4; lambda8 = 4; lambda9 = 5; lambda10 = 5; lambda11 = 6; lambda12 = 6; //funcao garante acesso ao recurso quando pelo menos 1 recurso liberado f1 = lambda1 * (nb u < recs); f2 = lambda2 * (nb u < recs); f3 = lambda3 * (nb u < recs); f4 = lambda4 * (nb u < recs); f5 = lambda5 * (nb u < recs); f6 = lambda6 * (nb u < recs); f7 = lambda7 * (nb u < recs); f8 = lambda8 * (nb u < recs); f9 = lambda9 * (nb u < recs); f10 = lambda10 * (nb u < recs); f11 = lambda11 * (nb u < recs); f12 = lambda12 * (nb u < recs); } reachability = nb u <= recs; // no maximo quatro recursos em uso // modelo 12 automatos p network cr1 (continuous) { aut p1{ stt s {trs (u){loc l1 (f1)} } stt u {trs (s){loc l2(mu1)} } } aut p2{ stt s {trs (u){loc l3 (f2)} } stt u {trs (s){loc l4 (mu2)} } } aut p3{ stt s {trs (u){loc l5 (f3)} } stt u {trs (s){loc l6 (mu3)} } }

75

aut p4{ stt s {trs (u){loc l7 (f4)} } stt u {trs (s){loc l8 (mu4)} } } aut p5{ stt s {trs (u){loc l9 (f5)} } stt u {trs (s){loc l10 (mu5)} } } aut p6{ stt s {trs (u){loc l11 (f6)} } stt u {trs (s){loc l12 (mu6)} } } aut p7{ stt s {trs (u){loc l13 (f7)} } stt u {trs (s){loc l14 (mu7)} } } aut p8{ stt s {trs (u){loc l15 (f8)} } stt u {trs (s){loc l16 (mu8)} } } aut p9{ stt s {trs (u){loc l17 (f9)} } stt u {trs (s){loc l18 (mu9)} } } aut p10{ stt s {trs (u){loc l19 (f10)} } stt u {trs (s){loc l20 (mu10)} } } aut p11{ stt s {trs (u){loc l21 (f11)} } stt u {trs (s){loc l22 (mu11)} } } aut p12{ stt s {trs (u){loc l23 (f12)} } stt u {trs (s){loc l24 (mu12)} } } } results { } //Compartilhamento de Recursos ==============================

76

ANEXO X – COMPARTILHAMENTO DE RECURSOS COM TAXAS FUNCIONAIS (.TIM)


ferramenta PEPS2002 a partir da implementação com 1, 4, 8 e 11 recursos através de

taxas funcionais.

=============================================================== File cr1a_n.tim =============================================================== cr1a_n.san -- A model with 12 automata and 0 events User name: 'cr1' ------------ Problem Size ------------ Product state space: 4096 states Reachable state space: 13 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 5 Size of the Normalized Descriptor: 38 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 134 CPU average time per iteration: 0.04835820895522388 seconds Total CPU time: 6.48 seconds ---------------------- Vector characteristics ---------------------- Name: cr1a_n.vct Sum of all elements: 0.9999999999999999 Largest element: 0.1363636356890718 (in position 1) Smallest element: 0.02272727327918918 (in position 512) Residue after convergence: 8.648263355448549e-11 (the vector cr1a_n.vct is the solution of the model cr1a_n.san)

77

=============================================================== File cr1_n.tim =============================================================== cr1_n.san -- A model with 12 automata and 0 events User name: 'cr1' ------------ Problem Size ------------ Product state space: 4096 states Reachable state space: 794 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 5 Size of the Normalized Descriptor: 38 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 136 CPU average time per iteration: 0.04926470588235294 seconds Total CPU time: 6.7 seconds ---------------------- Vector characteristics ---------------------- Name: cr1_n.vct Sum of all elements: 1.000000000000004 Largest element: 0.008803591510794385 (in position 3) Smallest element: 1.956355416533089e-05 (in position 3648) Residue after convergence: 8.860561503259978e-11 (the vector cr1_n.vct is the solution of the model cr1_n.san)

=============================================================== File cr1b_n.tim =============================================================== cr1b_n.san -- A model with 12 automata and 0 events User name: 'cr1' ------------ Problem Size ------------ Product state space: 4096 states Reachable state space: 3797 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 5 Size of the Normalized Descriptor: 38 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 150 CPU average time per iteration: 0.04866666666666666 seconds Total CPU time: 7.3 seconds ----------------------

78

Vector characteristics ---------------------- Name: cr1b_n.vct Sum of all elements: 0.9999999999999938 Largest element: 0.004864875811073158 (in position 3) Smallest element: 1.107030720830608e-06 (in position 4080) Residue after convergence: 8.512355349678952e-11 (the vector cr1b_n.vct is the solution of the model cr1b_n.san)

=============================================================== File cr1c_n.tim =============================================================== cr1c_n.san -- A model with 12 automata and 0 events User name: 'cr1' ------------ Problem Size ------------ Product state space: 4096 states Reachable state space: 4095 states Automata sizes: [ 2 2 2 2 2 2 2 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 5 Size of the Normalized Descriptor: 38 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 155 CPU average time per iteration: 0.05148387096774194 seconds Total CPU time: 7.98 seconds ---------------------- Vector characteristics ---------------------- Name: cr1c_n.vct Sum of all elements: 1.000000000000011 Largest element: 0.004841555292993122 (in position 3) Smallest element: 1.101723949667902e-06 (in position 4092) Residue after convergence: 8.331290811316311e-11 (the vector cr1c_n.vct is the solution of the model cr1c_n.san)

79

ANEXO XI – “JANTAR DOS FILÓSOFOS” – MODELO BÁSICO COM EVENTOS SINCRONIZANTES (.SAN)

//===Jantar do Filosofos - eventos sincronizantes (filsinc1)============================= identifiers { mu = 0.25; lambda = 0.5; } reachability = ( (st F1 == E) -> ( (st F5 ==PP) && (st F2 == P) ) ) && ( (st F2 == E) -> ( (st F1 != E) && (st F3 == P) ) ) && ( (st F3 == E) -> ( (st F2 != E) && (st F4 == P) ) ) && ( (st F4 == E) -> ( (st F3 != E ) && (st F5 != DD) ) ) && ( (st F5 == DD) -> ( (st F4 != E) && (st F1 == P) ) ) && ( (st F1 == D) -> (st F5 == PP) ) && ( (st F2 == D) -> (st F1 != E) ) && ( (st F3 == D) -> (st F2 != E) ) && ( (st F4 == D) -> (st F3 != E) ) && ( (st F5 == EE) -> (st F1 == P) )&& ( (st G1 == L) <-> ( (st F1 == P) && (st F5 == PP) ) ) && ( (st G2 == L) <-> ( (st F2 == P) && (st F1 != E) ) ) && ( (st G3 == L) <-> ( (st F3 == P) && (st F2 != E) ) ) && ( (st G4 == L) <-> ( (st F4 == P) && (st F3 != E) ) ) && ( (st G5 == L) <-> ( (st F4 != E) && (st F5 != DD) ) ) ; //Jantar dos Filosofos network Filosofos (continuous) { aut F1 { stt P { trs (D) {mst s1 (lambda) } } stt D { trs (E) {mst s2 (lambda) } } stt E { trs (P) {syn s3} } } aut F2 { stt P { trs (D) {mst s4 (lambda)} } stt D { trs (E) {mst s5 (lambda)} } stt E { trs (P) {syn s6} } } aut F3 { stt P { trs (D) {mst s7 (lambda)} } stt D { trs (E) {mst s8 (lambda)} } stt E { trs (P) {syn s9} } } aut F4 { stt P { trs (D) {mst s10 (lambda)} } stt D { trs (E) {mst s11 (lambda)} } stt E { trs (P) {syn s12}

80

} } aut F5 { stt PP { trs (EE) {mst s13 (lambda)} } stt DD { trs (PP) {syn s15} } stt EE { trs (DD) {mst s14 (lambda)} } } //garfos aut G1 { stt L { trs (U) {syn s13 syn s1 } } stt U { trs (L) {syn s15 mst s3 (mu)} } } aut G2 { stt L { trs (U) {syn s2 syn s4 } } stt U { trs (L) {syn s3 mst s6 (mu)} } } aut G3 { stt L { trs (U) {syn s5 syn s7 } } stt U { trs (L) {syn s6 mst s9 (mu)} } } aut G4 { stt L { trs (U) {syn s8 syn s10 } } stt U { trs (L) {syn s9 mst s12 (mu)} } } aut G5 { stt L { trs (U) {syn s11 syn s14 } } stt U { trs (L) {syn s12 mst s15 (mu)} } } } results{ FP = st F1==P; FD = st F1==D; FE = st F1==E; } // Jantar dos filosofos (filsinc1) Fim==============================

81

82

ANEXO XII – “JANTAR DOS FILÓSOFOS” – MODELO BÁSICO COM EVENTOS SINCRONIZANTES (.TIM)


ferramenta PEPS2002 a partir da implementação com 3, 4, e 5 filósofos através de

eventos sincronizantes. =============================================================== File filsinc13.tim =============================================================== filsinc13.san -- A model with 6 automata and 9 events User name: 'Filosofos' ------------ Problem Size ------------ Product state space: 216 states Reachable state space: 12 states Automata sizes: [ 3 3 3 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 12 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 210 CPU average time per iteration: 9.523809523809524e-05 seconds Total CPU time: 0.02 seconds ---------------------- Vector characteristics ---------------------- Name: filsinc13.vct Sum of all elements: 1.000000000000004 Largest element: 0.2459677413594931 (in position 127) Smallest element: 0.01290322585735492 (in position 51) Residue after convergence: 8.848932350757899e-11 (the vector filsinc13.vct is the solution of the model filsinc13.san) --------------------- Results --------------------- FP: 0.4104838730429688 FD: 0.433870966714533 FE: 0.1556451602425026 ===============================================================

83

=============================================================== File filsinc14.tim =============================================================== filsinc14.san -- A model with 8 automata and 12 events User name: 'Filosofos' ------------ Problem Size ------------ Product state space: 1296 states Reachable state space: 27 states Automata sizes: [ 3 3 3 3 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 31 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 294 CPU average time per iteration: 0.002210884353741497 seconds Total CPU time: 0.65 seconds ---------------------- Vector characteristics ---------------------- Name: filsinc14.vct Sum of all elements: 1 Largest element: 0.2350778220946584 (in position 687) Smallest element: 0.003642494861055377 (in position 148) Residue after convergence: 9.021319498717095e-11 (the vector filsinc14.vct is the solution of the model filsinc14.san) --------------------- Results --------------------- FP: 0.2723444265735414 FD: 0.6261643975552844 FE: 0.1014911758711745 ===============================================================

84

=============================================================== File filsinc15.tim =============================================================== filsinc15.san -- A model with 10 automata and 15 events User name: 'Filosofos' ------------ Problem Size ------------ Product state space: 7776 states Reachable state space: 70 states Automata sizes: [ 3 3 3 3 3 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 98 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 479 CPU average time per iteration: 0.0153027139874739 seconds Total CPU time: 7.33 seconds ---------------------- Vector characteristics ---------------------- Name: filsinc15.vct Sum of all elements: 1.000000000000007 Largest element: 0.2335649031130609 (in position 3967) Smallest element: 0.0003195332750301361 (in position 1067) Residue after convergence: 9.526308756592494e-11 (the vector filsinc15.vct is the solution of the model filsinc15.san) --------------------- Results --------------------- FP: 0.1738351840661126 FD: 0.7608882087047787 FE: 0.06527660722911596 ===============================================================

85

ANEXO XIII – “JANTAR DOS FILÓSOFOS” – MODELO BÁSICO COM FUNÇÕES (.SAN)

//===Jantar do Filosofos - eventos sincronizantes (filsinc1)============================= identifiers { mu = 0.25; lambda = 0.5; } reachability = ( (st F1 == E) -> ( (st F5 ==PP) && (st F2 == P) ) ) && ( (st F2 == E) -> ( (st F1 != E) && (st F3 == P) ) ) && ( (st F3 == E) -> ( (st F2 != E) && (st F4 == P) ) ) && ( (st F4 == E) -> ( (st F3 != E ) && (st F5 != DD) ) ) && ( (st F5 == DD) -> ( (st F4 != E) && (st F1 == P) ) ) && ( (st F1 == D) -> (st F5 == PP) ) && ( (st F2 == D) -> (st F1 != E) ) && ( (st F3 == D) -> (st F2 != E) ) && ( (st F4 == D) -> (st F3 != E) ) && ( (st F5 == EE) -> (st F1 == P) )&& ( (st G1 == L) <-> ( (st F1 == P) && (st F5 == PP) ) ) && ( (st G2 == L) <-> ( (st F2 == P) && (st F1 != E) ) ) && ( (st G3 == L) <-> ( (st F3 == P) && (st F2 != E) ) ) && ( (st G4 == L) <-> ( (st F4 == P) && (st F3 != E) ) ) && ( (st G5 == L) <-> ( (st F4 != E) && (st F5 != DD) ) ) ; //Jantar dos Filosofos network Filosofos (continuous) { aut F1 { stt P { trs (D) {mst s1 (lambda) } } stt D { trs (E) {mst s2 (lambda) } } stt E { trs (P) {syn s3} } } aut F2 { stt P { trs (D) {mst s4 (lambda)} } stt D { trs (E) {mst s5 (lambda)} } stt E { trs (P) {syn s6} } } aut F3 { stt P { trs (D) {mst s7 (lambda)} } stt D { trs (E) {mst s8 (lambda)} } stt E { trs (P) {syn s9} } } aut F4 { stt P { trs (D) {mst s10 (lambda)} } stt D { trs (E) {mst s11 (lambda)} } stt E { trs (P) {syn s12} }

86

} aut F5 { stt PP { trs (EE) {mst s13 (lambda)} } stt DD { trs (PP) {syn s15} } stt EE { trs (DD) {mst s14 (lambda)} } } //garfos aut G1 { stt L { trs (U) {syn s13 syn s1 } } stt U { trs (L) {syn s15 mst s3 (mu)} } } aut G2 { stt L { trs (U) {syn s2 syn s4 } } stt U { trs (L) {syn s3 mst s6 (mu)} } } aut G3 { stt L { trs (U) {syn s5 syn s7 } } stt U { trs (L) {syn s6 mst s9 (mu)} } } aut G4 { stt L { trs (U) {syn s8 syn s10 } } stt U { trs (L) {syn s9 mst s12 (mu)} } } aut G5 { stt L { trs (U) {syn s11 syn s14 } } stt U { trs (L) {syn s12 mst s15 (mu)} } } } results{ FP = st F1==P; FD = st F1==D; FE = st F1==E; } // Jantar dos filosofos (filsinc1) Fim==============================

87

ANEXO XIV – “JANTAR DOS FILÓSOFOS” – MODELO BÁSICO COM FUNÇÕES (.TIM)


ferramenta PEPS2002 a partir da implementação com 3, 4, e 5 filósofos através de taxas

funcionais. =============================================================== File filfunc13.tim =============================================================== filfunc13.san -- A model with 3 automata and 0 events User name: 'filosofos' ------------ Problem Size ------------ Product state space: 27 states Reachable state space: 12 states Automata sizes: [ 3 3 3 ] Automata sizes after aggregation: [ ] Current Number of Functions: 6 Size of the Normalized Descriptor: 1 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 210 CPU average time per iteration: 4.761904761904762e-05 seconds Total CPU time: 0.01 seconds ---------------------- Vector characteristics ---------------------- Name: filfunc13.vct Sum of all elements: 1.000000000000004 Largest element: 0.2459677413594931 (in position 15) Smallest element: 0.01290322585735492 (in position 6) Residue after convergence: 8.848932350757899e-11 (the vector filfunc13.vct is the solution of the model filfunc13.san) --------------------- Results --------------------- FP: 0.4104838730429688 FD: 0.433870966714533 FE: 0.1556451602425026 ===============================================================

88

=============================================================== File filfunc14.tim =============================================================== filfunc14.san -- A model with 4 automata and 0 events User name: 'filosofos' ------------ Problem Size ------------ Product state space: 81 states Reachable state space: 27 states Automata sizes: [ 3 3 3 3 ] Automata sizes after aggregation: [ ] Current Number of Functions: 8 Size of the Normalized Descriptor: 1 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 294 CPU average time per iteration: 6.802721088435374e-05 seconds Total CPU time: 0.02 seconds ---------------------- Vector characteristics ---------------------- Name: filfunc14.vct Sum of all elements: 1 Largest element: 0.2350778220946584 (in position 42) Smallest element: 0.003642494861055377 (in position 9) Residue after convergence: 9.021319498717095e-11 (the vector filfunc14.vct is the solution of the model filfunc14.san) --------------------- Results --------------------- FP: 0.2723444265735414 FD: 0.6261643975552844 FE: 0.1014911758711745 ===============================================================

89

=============================================================== File filfunc15.tim =============================================================== filfunc15.san -- A model with 5 automata and 0 events User name: 'filosofos' ------------ Problem Size ------------ Product state space: 243 states Reachable state space: 70 states Automata sizes: [ 3 3 3 3 3 ] Automata sizes after aggregation: [ ] Current Number of Functions: 10 Size of the Normalized Descriptor: 3 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 479 CPU average time per iteration: 0.0002713987473903966 seconds Total CPU time: 0.13 seconds ---------------------- Vector characteristics ---------------------- Name: filfunc15.vct Sum of all elements: 1.000000000000007 Largest element: 0.2335649031130609 (in position 123) Smallest element: 0.0003195332750301361 (in position 33) Residue after convergence: 9.526308756592494e-11 (the vector filfunc15.vct is the solution of the model filfunc15.san) --------------------- Results --------------------- FP: 0.1738351840661126 FD: 0.7608882087047787 FE: 0.06527660722911596 ===============================================================

90

ANEXO XV – “JANTAR DOS FILÓSOFOS” – MODELO COM BEBIDAS E EVENTOS SINCRONIZANTES (.SAN)

//===Jantar do Filosofos com bebidas- eventos sincronizantes (filsinc2)=========== identifiers { mu = 0.25; //taxa liberacao dos garfos lambda = 0.5; //taxa requisicao dos garfos fb = 0.5; //taxa de requisicao de bebida lb = 0.4; //taxa de liberacao de bebida } reachability = ( (st F1 == E) -> ( (st F5 ==PP) && (st F2 == P) ) ) && ( (st F2 == E) -> ( (st F1 != E) && (st F3 == P) ) ) && ( (st F3 == E) -> ( (st F2 != E) && (st F4 == P) ) ) && ( (st F4 == E) -> ( (st F3 != E ) && (st F5 != DD) ) ) && ( (st F5 == DD) -> ( (st F4 != E) && (st F1 == P) ) ) && ( (st F1 == D) -> (st F5 == PP) ) && ( (st F2 == D) -> (st F1 != E) ) && ( (st F3 == D) -> (st F2 != E) ) && ( (st F4 == D) -> (st F3 != E) ) && ( (st F5 == EE) -> (st F1 == P) )&& ( (st G1 == L) <-> ( (st F1 == P) && (st F5 == PP) ) ) && ( (st G2 == L) <-> ( (st F2 == P) && (st F1 != E) ) ) && ( (st G3 == L) <-> ( (st F3 == P) && (st F2 != E) ) ) && ( (st G4 == L) <-> ( (st F4 == P) && (st F3 != E) ) ) && ( (st G5 == L) <-> ( (st F4 != E) && (st F5 != DD) ) ) &&

((st F1 == B1)<-> ( (st F2!= B1) && (st F3!= B1) && (st F4!= B1) && (st F5!= B1) && (st C1 == U) ) ) && ((st F2 == B1)<-> ( (st F3!= B1) && (st F4!= B1) && (st F5!= B1) && (st F1!= B1) && (st C1 == U) ) ) && ((st F3 == B1)<-> ( (st F4!= B1) && (st F5!= B1) && (st F1!= B1) && (st F2!= B1) && (st C1 == U) ) ) && ((st F4 == B1)<-> ( (st F5!= B1) && (st F1!= B1) && (st F2!= B1) && (st F3!= B1) && (st C1 == U) ) ) && ((st F5 == B1)<-> ( (st F1!= B1) && (st F2!= B1) && (st F3!= B1) && (st F4!= B1) && (st C1 == U) ) ) &&



( (st C1 == L) <-> ( nb B1(F1,F5)== 0) ) && ( (st C2 == L) <-> ( nb B2(F1,F5)== 0) ) && ( (st C3 == L) <-> ( nb B3(F1,F5)== 0) ) ;

network Filosofos (continuous) { // Filosofos aut F1 { stt B1 { trs (P) {syn e1} } stt B2 { trs (P) {syn e2} } stt B3 { trs (P) {syn e3} } stt P { trs (D) {mst s1 (lambda)} trs (B1) {mst cb1 (fb)} trs (B2) {mst cb2 (fb)} trs (B3) {mst cb3 (fb)} } stt D { trs (E) {mst s2 (lambda)}}

91

stt E { trs (P) {syn s3}} } aut F2 { stt B1 { trs (P) {syn e4} } stt B2 { trs (P) {syn e5} } stt B3 { trs (P) {syn e6} } stt P { trs (D) {mst s4 (lambda)} trs (B1) {mst cb4 (fb)} trs (B2) {mst cb5 (fb)} trs (B3) {mst cb6 (fb)} } stt D { trs (E) {mst s5 (lambda)}} stt E { trs (P) {syn s6}} } aut F3 { stt B1 { trs (P) {syn e7} } stt B2 { trs (P) {syn e8} } stt B3 { trs (P) {syn e9} } stt P { trs (D) {mst s7 (lambda)} trs (B1) {mst cb7 (fb)} trs (B2) {mst cb8 (fb)} trs (B3) {mst cb9 (fb)} } stt D { trs (E) {mst s8 (lambda)}} stt E { trs (P) {syn s9} } } aut F4 { stt B1 { trs (P) {syn e10} } stt B2 { trs (P) {syn e11} } stt B3 { trs (P) {syn e12} } stt P { trs (D) {mst s10 (lambda)} trs (B1) {mst cb10 (fb)} trs (B2) {mst cb11 (fb)} trs (B3) {mst cb12 (fb)} } stt D { trs (E) {mst s11 (lambda)}} stt E { trs (P) {syn s12}} } aut F5 { stt B1 { trs (PP) {syn e13} } stt B2 { trs (PP) {syn e14} } stt B3 { trs (PP) {syn e15} } stt PP { trs (EE) {mst s13 (lambda)} trs (B1) {mst cb13 (fb)} trs (B2) {mst cb14 (fb)} trs (B3) {mst cb15 (fb)} } stt DD { trs (PP) {syn s15}} stt EE { trs (DD) {mst s14 (lambda)}} } // Garfos aut G1 { stt L { trs (U) {syn s13 syn s1}} stt U { trs (L) {syn s15 mst s3 (mu)}} } aut G2 { stt L { trs (U) {syn s2 syn s4}} stt U { trs (L) {syn s3 mst s6 (mu)}} }

92

aut G3 { stt L { trs (U) {syn s5 syn s7}} stt U { trs (L) {syn s6 mst s9 (mu)}} } aut G4 { stt L { trs (U) {syn s8 syn s10}} stt U { trs (L) {syn s9 mst s12 (mu)}} } aut G5 { stt L { trs (U) {syn s11 syn s14}} stt U { trs (L) {syn s12 mst s15 (mu)}} } //Copos com bebida

aut C1 { stt L { trs (U) {syn cb1 syn cb4 syn cb7 syn cb10 syn cb13}} stt U { trs (L) {mst e1 (lb) mst e4 (lb) mst e7 (lb) mst e10 (lb) mst e13 (lb)}} }

aut C2 { stt L { trs (U) {syn cb2 syn cb5 syn cb8 syn cb11 syn cb14}} stt U { trs (L) {mst e2 (lb) mst e5 (lb) mst e8 (lb) mst e11 (lb) mst e14 (lb)}} }

aut C3 {

stt L { trs (U) {syn cb3 syn cb6 syn cb9 syn cb12 syn cb15}} stt U { trs (L) {mst e3 (lb) mst e6 (lb) mst e9 (lb) mst e12 (lb) mst e15 (lb)}} }

}

results{ F1P = st F1==P; F1D = st F1==D; F1E = st F1==E; } // Jantar dos filosofos com bebidas (filsinc2) Fim===============

93

ANEXO XVI – “JANTAR DOS FILÓSOFOS” – MODELO COM BEBIDAS E EVENTOS SINCRONIZANTES (.TIM)


ferramenta PEPS2002 a partir da modelagem textual através de eventos sincronizantes.

=============================================================== File filsinc2.tim =============================================================== filsinc2.san -- A model with 13 automata and 45 events User name: 'Filosofos' ------------ Problem Size ------------ Product state space: 1990656 states Reachable state space: 1093 states Automata sizes: [ 6 6 6 6 6 2 2 2 2 2 2 2 2 ] Automata sizes after aggregation: [ ] Current Number of Functions: 0 Size of the Normalized Descriptor: 15715 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 2790 CPU average time per iteration: 14.73818637992832 seconds Total CPU time: 41119.54 seconds ---------------------- Vector characteristics ---------------------- Name: filsinc2.vct Sum of all elements: 1.000000000000025 Largest element: 0.005278336473410847 (in position 1585654) Smallest element: 3.322221117511813e-12 (in position 1193588) Residue after convergence: 9.94444327231947e-11 (the vector filsinc2.vct is the solution of the model filsinc2.san) --------------------- Results --------------------- F1P: 0.2282156675243472 F1D: 0.4028373354559712 F1E: 0.00889540014437863 ===============================================================

ANEXO XVII – “JANTAR DOS FILÓSOFOS” – MODELO COM BEBIDAS E FUNÇÕES (.SAN)

//Jantar dos Filosofos com bebidas - com funcoes (filfunc2)===========

identifiers{

mu = 0.25; //taxa de liberacao dos garfos

lambda = 0.5; //taxa de requisicao dos garfos

fb = 0.5; //taxa de requisicao de bebida

lb = 0.4; //taxa de liberacao de bebida

//Bebidas

fb1 = (nb B1 == 0)*fb;

fb2 = (nb B2 == 0)*fb;

fb3 = (nb B3 == 0)*fb;

//Filosofo 1

func1 = ((st F5 == PP)||(st F5 == B1)||(st F5 == B2)||(st F5 == B3))*lambda; //dir

func2 = ((st F2 == P)||(st F2 == B1)||(st F2 == B2)||(st F2 == B3))*lambda;//esq

//Filosofo 2

func3 = (st F1 != E)*lambda;

func4 = ((st F3 == P)||(st F3 == B1)||(st F3 == B2)||(st F3 == B3))*lambda;

//Filosofo 3


func6 = ((st F4 == P)||(st F4 == B1)||(st F4 == B2)||(st F4 == B3))*lambda;

//Filosofo 4


func8 = (st F5 != DD)*lambda;

//Filosofo 5

func9 = ((st F1 == P)||(st F1 == B1)||(st F1 == B2)||(st F1 == B3))*lambda; //esq

func10 = (st F4 != E)*lambda; //dir

}

reachability =

( (st F1 == E) -> ( (st F5 ==PP) && (st F2 == P) ) ) &&

( (st F2 == E) -> ( (st F1 != E) && (st F3 == P) ) ) &&

( (st F3 == E) -> ( (st F2 != E) && (st F4 == P) ) ) &&

( (st F4 == E) -> ( (st F3 != E ) && (st F5 != DD) ) ) &&

( (st F5 == DD) -> ( (st F4 != E) && (st F1 == P) ) ) &&

95

( (st F1 == D) -> (st F5 == PP) ) &&

( (st F2 == D) -> (st F1 != E) ) &&

( (st F3 == D) -> (st F2 != E) ) &&

( (st F4 == D) -> (st F3 != E) ) &&

( (st F5 == EE) -> (st F1 == P) )&&

((st F1 == B1)-> ((st F2!= B1) && (st F3!= B1)&& (st F4!= B1) && (st F5!= B1)) )&&














((st F5 == B3)-> ((st F1!= B3) && (st F2!= B3)&& (st F3!= B3) && (st F4!= B3)) );

network filosofos (continuous){

aut F1 {

stt B1 { trs (P) {loc l1 (lb) }

}


}


}

stt P { trs (D) {loc l2 (func1) }

trs (B1){loc l3 (fb1) }



}

stt D { trs (E) {loc l6 (func2)}

}

stt E { trs (P) {loc l7 (mu)}

}

}

aut F2 {


96

}


}


}

stt P { trs (D) {loc l9 (func3)}

trs (B1) {loc l10 (fb1)}



}


}

stt E { trs (P) {loc l14 (mu)} }

}

aut F3 {


}


}


}





}


}

stt E { trs (P) {loc l21 (mu)}

}

}

aut F4 {


}


}


}





}

97


}

stt E { trs (P) {loc l28 (mu)} }

}

aut F5 {

stt B1 { trs (PP){loc l29 (lb)}

}


}


}

stt PP {trs (EE){loc l30 (func9)}

trs (B1){loc l31 (fb1)}



}

stt DD { trs (PP){loc l34 (mu)}

}

stt EE { trs (DD){loc l35 (func10)} }

}

}

results{

F1P = st F1==P;

F1D = st F1==D;

F1E = st F1==E;

}

// Jantar dos filosofos com bebidas (filfunc2) Fim================

98

ANEXO XVIII – “JANTAR DOS FILÓSOFOS” – MODELO COM BEBIDAS E FUNÇÕES (.TIM)


ferramenta PEPS2002 a partir da modelagem textual através de taxas funcionais.

=============================================================== File filfunc2.tim =============================================================== filfunc2.san -- A model with 5 automata and 0 events User name: 'filosofos' ------------ Problem Size ------------ Product state space: 7776 states Reachable state space: 1093 states Automata sizes: [ 6 6 6 6 6 ] Automata sizes after aggregation: [ ] Current Number of Functions: 13 Size of the Normalized Descriptor: 63 Kbytes =============================================================== Solution performed: power method with no preconditionning The multiplication method can be different for each term (mixed method) =============================================================== Number of iterations performed: 1406 CPU average time per iteration: 0.0346230440967283 seconds Total CPU time: 48.68 seconds ---------------------- Vector characteristics ---------------------- Name: filfunc2.san.vct Sum of all elements: 1.000000000000031 Largest element: 0.0122360165661091 (in position 6222) Smallest element: 4.051231599791235e-05 (in position 4893) Residue after convergence: 9.789904108735425e-11 (the vector filfunc2.san.vct is the solution of the model filfunc2.san) --------------------- Results --------------------- F1P: 0.1483185656139297 F1D: 0.4186175971334672 F1E: 0.1388954933270558 ===============================================================

99

100

101

Documents

Redes de Autômatos Estocásticos (RAE) – Modelagem e Avaliação · utilizando noções de sincronismo e paralelismo. No Capítulo 3, os exemplos selecionados serão especificados