Pontifícia - inf.pucrs.br · Star ek r T. Os tos agradecimen ão v para: Meus pais, Neumar e Nelsi Brenner, p or to do o ap oio dado em to das as ... subsistemas quase indep tes

Pontifí ia Universidade Católi a do Rio Grande do Sul

Fa uldade de Informáti a

MQNA - Analisador de Redes de Filas de Espera

Markovianas

Leonardo Brenner

para obtenção do grau de Ba harel em Ciên ia da Computação

da Pontifí ia Universidade Católi a do Rio Grande do Sul

Porto Alegre, Dezembro 2001

.

à meus pais, Neumar e Nelsi, de todo meu oração.

.

Que a força esteja om vo ê...

StarWars

...onde nenhum homem jamais esteve.

Star Trek

Os agrade imentos vão para:

� Meus pais, Neumar e Nelsi Brenner, por todo o apoio dado em todas as ir-

unstân ias, as minhas es olhas e de isões e é laro pelo "apoio" �nan eiro

in ondi ional.

� Meus dois irmãos, Rosália e Ri ardo, pela ajuda dispensada de todas as

maneiras, seja lavando a louça, limpando o apartamento até a ajuda em

pesquisas e trabalhos.

� Todos meus amigos e amigas, os quais não vou itar nenhum por que sempre

falta alguém, pelo momentos agradáveis e divertidos na sua ompanhia, pelas

festas a que muitas vezes me arrastaram e que foram ompensadoras.

� Meu orientador, Paulo Fernandes, por obrança e orientação dispensada du-

rante vários anos de bolsa de pesquisa e prin ipalmente durante esse trabalho

de on lusão.

� Finalmente e espe ialmente agradeço a minha namorada Marina, pela pa iên-

ia ao lado nos �nais de semana passados na frente do omputador, pela

atenção e apoio dedi ada a mim em todos os momentos, pela par eria e om-

panheirismo quanto aos meus planos futuros.

Em �m, agradeço a todos que de alguma maneira me apoiaram, mesmo que tenha

esque ido de men ioná-los aqui.

Resumo:

Redes de Filas de Espera (QN - Queueing Networks) é provavelmente o mais popular dos

formalismos para avaliação de desempenho via métodos analíti os. Parte desta populari-

dade se deve às soluções a forma-produto propostas na dé ada de 70. Bastante populari-

zada pela sua idéia de lientes passando através de �las ( entros de serviço), QN podem

ser traduzidas para Cadeias de Markov, mas esta onversão sofre limitações impostas pela

explosão do espaço de estados gerado. Na dé ada de 80, as Redes de Aut�matos Esto ásti-

os (SAN - Sto hasti Automata Networks) introduzem um formalismo mais poderoso que

as QN, baseado em me anismos de sin ronismo e paralelismo. Utilizando a idéia de um

sistema dividido em subsistemas quase independentes (que interagem o asionalmente), as

SAN provêem soluções numéri as e� ientes, podendo evitar os prejuízos da explosão do

espaço de estados das adeias de Markov. A fa ilidade de modelagem das QN e o poder

de resolução das SAN tornam interessante e extremamente útil uma ferramenta de onver-

são automáti a entre os dois formalismos itados. Este trabalho des reve uma ferramenta

(MQNA) que resolve QN om soluções a forma-produto quando possível e transforma as

QN sem soluções à forma-produto em SAN, podendo ser resolvidas numeri amente.

Palavras have: Avaliação de desempenho, Redes de �las de espera, Redes de aut�-

matos esto ásti os, Soluções numéri as.

Abstra t:

Queueing Networks (QN) is probably the most popular formalism to performan e evalua-

tion using analyti methods. This popularity is partially due to the produ t-form solution

proposed in the 70's. Well known by its very intuitive idea of lients passing by servi e

enters (queues), QN an be translated into Markov hains, but this translation su�ers

limitations imposed by the state spa e explosion problem. By the 80's, the Sto hasti

Automata Networks (SAN) formalism was introdu ed to extend the power of QN by in-

luding the me hanisms of parallelism and syn hronism. SAN models des ribe a system as

a olle tion of almost independent subsystems, i.e., subsystems that intera t o asionally.

Re ently, SAN models an be numeri ally solved by very e� ient methods that avoid most

of the problems due to the state spa e explosion. A tool to onvert QN into SAN mod-

els an ombine the modelling onfort of the QN and the power of solution of the SAN.

This work des ribes a tool (MQNA) to analyti ally solve produ t-form QN and to onvert

non-produ t-form QN into SAN that an be numeri ally solved.

Title: Markovian Queueing Networks Analyser.

Keywords: Queueing networks, Numeri al solutions, Performan e evaluation, Sto has-

ti automata networks.

i

Sumário

1 Introdução 1

1.1 Breve Históri o da Avaliação de Desempenho . . . . . . . . . . . . . . . . . 2

1.1.1 Monitoração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.2 Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.3 Métodos Analíti os . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Estrutura do Volume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

I Fundamentação Teóri a 5

2 Formalismos de Modelagem 7

2.1 Pro essos de Nas imento e Morte . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1 Notação de Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2 Cadeias de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.1 Es ala de Tempo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.2 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.3 Análise Esta ionária . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Redes de Aut�matos Esto ásti os . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.1 Aut�matos Esto ásti os . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.2 Eventos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.3 Funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Redes de Filas de Espera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.1 Redes à Forma-Produto . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.2 De�nição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.3 Número de Servidores . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.4.4 Número de Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4.5 Redes de Filas de Espera Abertas . . . . . . . . . . . . . . . . . . . 26

2.4.6 Redes de Filas de Espera Fe hadas . . . . . . . . . . . . . . . . . . 29

3 Conversão entre Formalismos 35

3.1 Ferramenta PEPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 Método de Conversão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.1 Modelo Bási o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.2 Modelos Multi-Classe . . . . . . . . . . . . . . . . . . . . . . . . . . 38

ii SUMÁRIO

3.3 Gramáti a para Des rição de QN em MQNA . . . . . . . . . . . . . . . . . 40

3.3.1 Unidades Sintáti as . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.2 Modelos CQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.3.3 Modelo para OQN . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4 Gramáti a para PEPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.4.1 De laração de Constantes e Funções . . . . . . . . . . . . . . . . . . 50

3.4.2 Função de Al ançabilidade . . . . . . . . . . . . . . . . . . . . . . . 51

3.4.3 Des rição do Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.4.4 Des rição dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . 53

II Des rição e Implementação da Ferramenta MQNA 55

4 A Ferramenta MQNA 57

4.1 Espe i� ação Geral da Ferramenta . . . . . . . . . . . . . . . . . . . . . . 57

4.1.1 Requisitos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.1.2 Formatos de Arquivos . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.1.3 Interfa e om o Usuário . . . . . . . . . . . . . . . . . . . . . . . . 58

4.1.4 Fun ionalidades do Software . . . . . . . . . . . . . . . . . . . . . . 59

4.1.5 Plataformas Es olhidas . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.2 Des rição Fun ional da Ferramenta . . . . . . . . . . . . . . . . . . . . . . 61

4.2.1 A Criação de Modelos . . . . . . . . . . . . . . . . . . . . . . . . . 62

4.2.2 Compilando um Modelo . . . . . . . . . . . . . . . . . . . . . . . . 62

4.2.3 Obtendo os Índi es de Desempenho . . . . . . . . . . . . . . . . . . 63

4.2.4 Convertendo um Modelo QN para SAN . . . . . . . . . . . . . . . . 64

4.2.5 Alterando Parâmetros do Modelo . . . . . . . . . . . . . . . . . . . 64

4.2.6 Salvando um Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5 Implementação da Ferramenta 67

5.1 Linguagem de Programação Es olhida . . . . . . . . . . . . . . . . . . . . 67

5.1.1 Ferramentas Utilizadas . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2 De�nição das Classes e Métodos . . . . . . . . . . . . . . . . . . . . . . . . 70

5.2.1 Classe Matriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2.2 Classe Qn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.2.3 Classe CQn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.2.4 Classe OQn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.3 De�nição das Interfa es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.3.1 Interfa e Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.3.2 Interfa e Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

III Manual do Usuário 87

6 Guia Rápido de Ini iação 89

6.1 Como Criar e Compilar um Modelo QN . . . . . . . . . . . . . . . . . . . . 90

6.2 Como Salvar um Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

SUMÁRIO iii

6.3 Como Computar os Índi es de Desempenho . . . . . . . . . . . . . . . . . 92

6.4 Como Converter um Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7 Manual de Referên ia do Usuário 97

7.1 Criando Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.1.1 Modelos Bási os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.1.2 Modelos Multi-Classe . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7.1.3 Utilizando o Assistente para Criação de um Novo Modelo . . . . . . 100

7.2 Compilando Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.3 Salvando Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.3.1 Salvar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7.3.2 Salvar omo: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.4 Cal ulando Taxas de Visita . . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.4.1 Cal ulando Todas as Taxas . . . . . . . . . . . . . . . . . . . . . . 104

7.4.2 Cal ulando Taxas de Visita de uma Classe . . . . . . . . . . . . . . 105

7.4.3 Alterando Número Máximo de Iterações . . . . . . . . . . . . . . . 105

7.4.4 Alterando Erro Máximo A eitável . . . . . . . . . . . . . . . . . . . 106

7.5 Computando Índi es de Desempenho . . . . . . . . . . . . . . . . . . . . . 107

7.5.1 Salvando Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.6 Alterando Parâmetros do Modelo . . . . . . . . . . . . . . . . . . . . . . . 108

7.6.1 Alterando Parâmetros das Classes . . . . . . . . . . . . . . . . . . . 108

7.6.2 Alterando Parâmetros das Filas . . . . . . . . . . . . . . . . . . . . 111

7.7 Exibindo Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

7.7.1 Resultados Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

7.7.2 Resultados das Classes . . . . . . . . . . . . . . . . . . . . . . . . . 114

7.8 Convertendo Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

7.9 Utilizando a Ajuda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

8 Exemplos 117

8.1 Modelo OQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

8.1.1 Criando o Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

8.1.2 Computando os Índi es de Desempenho . . . . . . . . . . . . . . . 119

8.1.3 Convertendo o Modelo . . . . . . . . . . . . . . . . . . . . . . . . . 120

8.2 Modelo CQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

8.2.1 Criando o Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

8.2.2 Computando os Índi es de Desempenho . . . . . . . . . . . . . . . 122

8.2.3 Convertendo o Modelo . . . . . . . . . . . . . . . . . . . . . . . . . 122

9 Con lusão 127

A Notação Utilizada 133

A.1 Notação de Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

A.1.1 Tipos de distribuição . . . . . . . . . . . . . . . . . . . . . . . . . . 133

A.1.2 Dis iplinas de atendimento . . . . . . . . . . . . . . . . . . . . . . . 134

A.2 Cadeias de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

A.3 Redes de Aut�matos Esto ásti os . . . . . . . . . . . . . . . . . . . . . . . 134

iv SUMÁRIO

A.4 Redes de Filas de Espera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

A.4.1 De�nição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

A.4.2 Índi es de Desempenho e Auxiliares . . . . . . . . . . . . . . . . . . 135

B Regras e Terminais da Gramáti a para QN 137

B.1 Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

B.2 Regras da gramáti a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

B.2.1 Iní io da Gramáti a . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

B.2.2 De larações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

B.2.3 Redes de Filas de Espera Fe hadas . . . . . . . . . . . . . . . . . . 139

B.2.4 Redes de Filas de Espera Abertas . . . . . . . . . . . . . . . . . . . 139

B.2.5 Populações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

B.2.6 Des rição das Filas . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

B.2.7 Parâmetros das Filas . . . . . . . . . . . . . . . . . . . . . . . . . . 140

B.2.8 Des rição das Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 140

B.2.9 Parâmetros das Classes . . . . . . . . . . . . . . . . . . . . . . . . . 141

B.2.10 Parâmetros das Classes . . . . . . . . . . . . . . . . . . . . . . . . . 141

B.2.11 Auxiliares para Leitura de Números . . . . . . . . . . . . . . . . . . 141

v

Lista de Figuras

2.1 Representação grá� a da notação de Kendall . . . . . . . . . . . . . . . . . 9

2.2 Representação grá� a de uma adeia de Markov . . . . . . . . . . . . . . . 11

2.3 SAN apenas om eventos lo ais . . . . . . . . . . . . . . . . . . . . . . . . 16

2.4 Aut�mato ombinado da Figura 2.3 . . . . . . . . . . . . . . . . . . . . . . 16

2.5 SAN om um evento sin ronizante . . . . . . . . . . . . . . . . . . . . . . . 17

2.6 Aut�mato equivalente om transições sin ronizadas . . . . . . . . . . . . . 17

2.7 SAN om taxas fun ionais . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.8 Aut�mato om taxas fun ionais . . . . . . . . . . . . . . . . . . . . . . . . 19

2.9 Rede de Filas de Espera Aberta . . . . . . . . . . . . . . . . . . . . . . . . 26

2.10 Rede de Filas de Espera Fe hada . . . . . . . . . . . . . . . . . . . . . . . 30

3.1 Interfa e da ferramenta PEPS . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2 Modelo CQN mono- lasse . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.3 Modelo SAN equivalente ao modelo CQN anterior . . . . . . . . . . . . . . 38

3.4 Modelo OQN multi- lasse . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.5 Modelo SAN equivalente . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.1 Organização das lasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.2 Tela prin ipal da versão Windows . . . . . . . . . . . . . . . . . . . . . . . 79

5.3 Dados das lasses para modelos CQN . . . . . . . . . . . . . . . . . . . . . 80

5.4 Dados das lasses para modelos OQN . . . . . . . . . . . . . . . . . . . . . 80

5.5 Nome do novo modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.6 Tipo do novo modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.7 Número de lasses do novo modelo . . . . . . . . . . . . . . . . . . . . . . 82

5.8 Número de �las do novo modelo . . . . . . . . . . . . . . . . . . . . . . . . 82

5.9 Tela de ajuda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.10 Menu prin ipal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.11 Opção para salvar um modelo . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.12 Opção de ál ulo das taxas de visita . . . . . . . . . . . . . . . . . . . . . 85

5.13 Modi� ar parâmetros do modelo . . . . . . . . . . . . . . . . . . . . . . . . 85

5.14 Modi� ar parâmetros das lasses . . . . . . . . . . . . . . . . . . . . . . . 85

5.15 Modi� ar parâmetros das �las . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.16 Exibir índi es de desempenho . . . . . . . . . . . . . . . . . . . . . . . . . 86

5.17 Menu de ajuda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.1 Figura do exemplo1.mqn des rito a seguinte . . . . . . . . . . . . . . . . . 90

vi LISTA DE FIGURAS

6.2 Conversão para SAN om ou sem restrição a apa idade . . . . . . . . . . 94

7.1 Figura do exemplo2.mqn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

7.2 Figura do exemplo3.mqn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

7.3 Nome do novo modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7.4 Tipo do novo modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

7.5 Número de lasses do novo modelo . . . . . . . . . . . . . . . . . . . . . . 102

7.6 Número de �las do novo modelo . . . . . . . . . . . . . . . . . . . . . . . . 102

7.7 Alteração do número máximo de iterações . . . . . . . . . . . . . . . . . . 106

7.8 Alteração do erro máximo a eitável . . . . . . . . . . . . . . . . . . . . . . 107

7.9 Alteração do tempo de serviço . . . . . . . . . . . . . . . . . . . . . . . . . 110

7.10 Alteração da taxa de hegada de lientes . . . . . . . . . . . . . . . . . . . 111

7.11 Alteração do nome da �la . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

7.12 Alteração do número de servidores da �la . . . . . . . . . . . . . . . . . . . 112

7.13 Alteração da apa idade da �la . . . . . . . . . . . . . . . . . . . . . . . . 113

7.14 Conversão para SAN om ou sem restrição a apa idade das �las . . . . . . 116

8.1 Modelo OQN mono- lasse om in o �las . . . . . . . . . . . . . . . . . . . 117

8.2 Modelo CQN om in o �las e uma lasse . . . . . . . . . . . . . . . . . . 120

vii

Lista de Tabelas

3.1 Palavras reservadas da gramáti a para MQNA . . . . . . . . . . . . . . . . 41

6.1 Índi es de desempenho do Exemplo1.mqn . . . . . . . . . . . . . . . . . . . 93

8.1 Índi es de desempenho do modelo oqn_ex.mqn . . . . . . . . . . . . . . . 119

8.2 Índi es de desempenho obtidos por PEPS . . . . . . . . . . . . . . . . . . . 120

8.3 Índi es de desempenho do modelo qn_ex.mqn . . . . . . . . . . . . . . . 122

8.4 Índi es de desempenho do modelo om restrição à apa idade . . . . . . . 126

B.1 Expressões regulares da gramáti a para MQNA . . . . . . . . . . . . . . . 137

B.2 Tokens da gramáti a para MQNA . . . . . . . . . . . . . . . . . . . . . . . 138

viii LISTA DE TABELAS

Capítulo 1

Introdução

Os métodos de análise e avaliação de desempenho de sistemas são ada vez mais utiliza-

dos em todo tipo de sistemas, tanto automáti os quanto manuais, omo meio de melhor

distribuir os re ursos disponíveis. A omplexidade res ente, prin ipalmente dos sistemas

de omputação, torna as té ni as de avaliação de desempenho de grande valia no desen-

volvimento de sistemas paralelos e distribuídos.

É desenvolvido ao longo deste trabalho um estudo sobre avaliação de desempenho de

sistemas. Para isso utiliza-se de alguns formalismos para modelagem de sistemas omo

Redes de Filas de Espera (QN - Queueing Networks) e Redes de Aut�matos Esto ásti os

(SAN - Sto hasti Automata Networks). Além disso, são estudadas também, té ni as

para onversão entre formalismos para modelagem e avaliação de sistemas.

O resultado deste estudo é a espe i� ação de uma ferramenta de software (MQNA) que

implementa os on eitos estudados sobre avaliação de desempenho, mais espe i� amente

sobre o formalismo de QN e té ni as de onversão de modelos QN em modelos em SAN.

Adi ionalmente, a ferramenta MQNA forne e solução à forma-produto de modelos QN,

onde este tipo de solução é possível, baseados nos trabalhos de Baskett, Chandy, Muntz

e Pala ios [3℄ e Reiser e Lavenberg [23℄.

2 CAPÍTULO 1. INTRODUÇ�O

1.1 Breve Históri o da Avaliação de Desempenho

Para avaliação de desempenho as té ni as dividem-se basi amente em três abordagens:

monitoração, simulação e métodos analíti os [8, 19℄.

1.1.1 Monitoração

A té ni a de monitoração onsiste na observação de um sistema real. Apesar de tra-

zer maior �delidade nos dados obtidos, esta abordagem apresenta algumas desvantagens

omo alto usto e tempo ex essivos. Outro problema que a monitoração apresenta é

que o sistema onstruído para obtenção dos dados pode ausar instabilidade no sistema

monitorado.

1.1.2 Simulação

A simulação onsiste no desenvolvimento de um modelo que imite o sistema real. Essa

imitação freqüentemente é em menor es ala de tempo e deve se restringir somente a

atributos relevantes do sistema real. Para isso os atributos representados no modelo devem

ser es olhidos om muita autela para que não se in luam erros ditos de modelagem.

Da mesma forma, é ne essário uidar para que não sejam deixados de lado detalhes

importantes do sistema real.

Um dos problemas en ontrados na té ni a de simulação é des obrir a quantidade de

dados que deve ser utilizada nas amostras de fun ionamento. Isso é fundamental para que

o pro esso de simulação não seja nem demasiadamente dispendioso, nem estati amente

insigni� ante a ponto de não representar a realidade a ser avaliada.

1.1.3 Métodos Analíti os

A abordagem de métodos analíti os onsiste em modelar um sistema real através das re-

lações matemáti as existentes no fun ionamento do sistema. Através de relações matemáti-

as pode-se des rever o sistema omo um onjunto de estados possíveis e transições entre

1.2. OBJETIVOS 3

estes estados. A não utilização de um onjunto de amostras na modelagem do sistema re-

presenta uma das prin ipais vantagens dos métodos analíti os sobre a simulação. Porém a

omplexidade dos modelos analíti os tende a ser maior do que nos modelos de simulação.

1.2 Objetivos

Redes de Filas de Espera (QN - Queueing Networks) é provavelmente o mais popular

dos formalismos para avaliação de desempenho via métodos analíti os [13, 19℄. Grande

parte desta popularidade se deve às soluções a forma-produto propostas na dé ada de

70 [3, 14, 23℄. Bastante popularizada pela sua idéia de lientes passando através de

�las ( entros de serviço), QN podem ser traduzidas para Cadeias de Markov. Porém,

esta onversão sofre limitações impostas pela explosão do espaço de estados gerado nas

Cadeias de Markov. Na dé ada de 80, as Redes de Aut�matos Esto ásti os (SAN -

Sto hasti Automata Networks) introduzem um formalismo mais poderoso que as QN,

baseado em me anismos de sin ronismo e paralelismo [8, 6, 21℄. Utilizando a idéia de um

sistema dividido em subsistemas quase independentes (que interagem o asionalmente), as

SAN provêem soluções numéri as e� ientes, podendo evitar os prejuízos da explosão do

espaço de estados das adeias de Markov.

A fa ilidade de modelagem das QN e o poder de resolução das SAN tornam então

interessante e extremamente útil uma ferramenta de onversão automáti a entre os dois

formalismos itados. Este trabalho des reve uma ferramenta de software denominada

MQNA (Markovian Queueing Networks Analyser - Analisador de Redes de Filas de Espera

Markovinas) que resolve QN om soluções a forma-produto quando possível e transforma

QN om espaço �nito de estados ( om ou sem soluções a forma-produto) em SAN. As quais

podem ser resolvidas numeri amente pela ferramenta PEPS[20℄ (Performan e Evaluation

of Parallel System).

4 CAPÍTULO 1. INTRODUÇ�O

1.3 Estrutura do Volume

Este trabalho foi dividido basi amente em três partes distintas. A primeira parte é sub-

divida em dois apítulos, onde o primeiro apítulo des reve os formalismos de modelagem

utilizados ou que tenham relações om os on eitos expostos. O segundo apítulo desta

primeira parte trata basi amente sobre as té ni as de onversão de modelos QN para

modelos SAN.

A segunda parte do trabalho ontém a do umentação da ferramenta MQNA. Nela

é feita a des rição da ferramenta proposta (Capítulo 4) e o relato dos detalhes mais

importantes da implementação (Capítulo 5).

Na ter eira e última parte deste trabalho in lui-se três apítulos. O primeiro apítulo

desta parte é um guia rápido de ini iação da ferramenta. O segundo ontém um manual

mais detalhado das fun ionalidade da mesma e o ter eiro traz dois exemplos de modelagem

e utilização da ferramenta MQNA om modelos QN.

In lui-se ainda dois apêndi es que trazem um resumo das notações utilizadas no de or-

rer do trabalho (Apêndi e A) e um onjunto dos tokens e regras utilizadas na gramáti a

riada para os modelos QN (Apêndi e B).

5

Parte I

Fundamentação Teóri a

Capítulo 2

Formalismos de Modelagem

A boa modelagem de um sistema é in�uen iada muitas vezes pela es olha do formalismo

orreto. Apesar de não haver uma úni a es olha orreta, pois vários formalismos são

apazes de des rever um mesmo sistema om igual representatividade, há no entanto

es olhas mais ou menos adequadas que podem di� ultar ou mesmo, em asos extremos,

impossibilitar a modelagem do sistema através daquele formalismo.

Neste apítulo serão apresentados alguns formalismos de modelagem de sistemas que

servirão omo a base teóri a para implementação da ferramenta MQNA. Dentre os for-

malismos que serão expostos ita-se:

� Pro essos de Nas imento e Morte [11℄ (�las mono-estação);

� Cadeias de Markov [26, 28℄;

� Redes de Aut�matos Esto ásti os (SAN - Sto hasti Automata Networks) [8, 6, 21℄.

Para estes formalismo será feito apenas uma apresentação, sem abranger os métodos de

resolução destes formalismo, por não serem tema deste trabalho. No entanto, sobre Redes

de Filas de Espera (QN - Queueing Networks) [13, 19℄, será apresentado o formalismo para

duas lasses de QN. São elas: Redes de Filas de Espera Fe hadas (CQN - Closed Queueing

Networks) e Redes de Filas de Espera Abertas (OQN - Open Queueing Networks), para as

8 CAPÍTULO 2. FORMALISMOS DE MODELAGEM

quais também serão apresentados os métodos de resolução MVA (Mean Value Analysis)

[23℄ para CQN e BCMP (Baskett, Chandy, Muntz e Pala ios) [3℄ para OQN.

2.1 Pro essos de Nas imento e Morte

Pro essos de nas imento e morte [11℄ são um dos asos mais simples de des rição de

sistemas reais. Admite-se a des rição destes sistemas através de somente dois pro es-

sos esto ásti os

1

que podem ser hamados simboli amente de pro esso de nas imento e

pro esso de morte.

Asso ia-se o pro esso de nas imento ao evento que tro a o estado do sistema de um

estado N para um estado N + 1, respeitando a des rição do modelo. A situação ontraria

asso ia-se o pro esso de morte, que o orre quando o sistema passa de um estado N para

um estado N - 1.

Para representação de Pro essos de Nas imento e Morte ou �las simples é freqüente-

mente utilizada a Notação de Kendall.

2.1.1 Notação de Kendall

A Notação de Kendall [11℄ é largamente usada para des rever sistemas de �las simples

ou Pro essos de Nas imento e Morte. A �la pode ser representada gra� amente omo

apresentado na Figura 2.1, e des rita textualmente pela notação:

A=B= � dis iplina da fila

1

Pro esso esto ásti o é um pro esso onde a o orrên ia de eventos se dá através de leis probabilísti as,

ou seja, as ara terísti as são des ritas por variáveis aleatórias. Desta forma, todos os demais fen�menos

que são relevantes o orrem segundo distribuições probabilísti as.

2.1. PROCESSOS DE NASCIMENTO E MORTE 9

A B

K

Figura 2.1: Representação grá� a da notação de Kendall

onde A indi a o tipo de distribuição para o intervalo de hegada, B representa o tipo

de distribuição para o intervalo de saída e indi a o número de servidores da �la ( > 1).

Os tipos de distribuição normalmente usados são representados por:

M Distribuição exponen ial;

E

(k)

Distribuição de Erlang om k fases;

H

(k)

Distribuição hiperexponen ial om k fases;

C

(k)

Distribuição de Cox om k fases;

D Distribuição determinísti a;

G Distribuição geral;

GI Distribuição geral om tempos de intervalos independentes.

Para este trabalho a distribuição usada nas �las será sempre a distribuição exponen ial,

salvo quando espe i� ado o ontrário.

A dis iplina da �la ou estratégia de serviço determina omo os lientes serão sele iona-

dos na �la. As dis iplinas mais omumente utilizadas são:

� FCFS (First Come First Served) - Primeiro a hegar é o primeiro a ser atendido;

� LCFS Preemptive (Last Come First Served) - Último a hegar é atendido, inter-

rompendo o serviço (preempção);


� FCRS (First Come Randomi Served) - O atendimento é rand�mi o.

A notação de Kendall pode ser estendida de várias maneiras. A mais omum e uti-

lizada neste trabalho a res enta um parâmetro que representa a apa idade da �la. Esse

parâmetro é representado pela letra k. A notação estendida � a então om a seguinte

forma:

A=B= =k � dis iplina da fila

Como apa idade da �la (k) são onsiderados o tamanho da �la de espera ex lusiva-

mente mais o número de servidores, sendo sempre k > .

Os Pro essos de Nas imento e Morte, apesar de simples, são importantes por serem a

base para vários formalismos mais poderosos e omplexos.

2.2 Cadeias de Markov

Cadeias de Markov [26, 28℄ são um formalismo matemáti o para modelagem de sistemas.

Com elas des reve-se o fun ionamento de um sistema qualquer através de um onjunto de

estados possíveis e transições entre esses estados seguindo taxas de�nidas por leis expo-

nen iais. As Cadeias de Markov podem ser interpretadas omo uma máquina de estados

onde os nodos representam os estados possíveis e os ar os representam as transições entre

ada estado.

2.2.1 Es ala de Tempo

Uma adeia de Markov [26, 28℄ pode ser lassi� ada em dois tipos de a ordo om a es ala

de tempo [1℄:

� Cadeias de Markov a es ala de tempo ontínua (CTMC - Continuous Time Markov

Chains);

2.2. CADEIAS DE MARKOV 11

� Cadeias de Markov a es ala de tempo dis reta (DTMC - Dis rete Time Markov

Chains).

As CTMC diferem das DTMC por suas transições entre os estados da adeia poderem

o orrer em um instante de tempo qualquer e não em pontos dis retos de tempo.

2.2.2 Propriedades

Supõem-se para modelar uma adeia de Markov as seguintes propriedades, segundo itado

por Stewart em [27℄:

� Os estados do sistema são dis retos;

� A es ala de tempo para a transição entre os estados do sistema pode ser de forma

ontínua (CTMC) ou dis reta (DTMC);

� A transição entre os estados do sistema depende ex lusivamente do estado atual do

sistema, sem importar por quais estados prévios o sistema já passou ou irá passar ;

� A duração (CTMC) ou a probabilidade (DTMC) de transição de estados do sistema

dá-se obede endo a uma lei exponen ial ;

� A representação grá� a de uma adeia de Markov é feita por aut�matos, onde é

asso iado para ada lugar do aut�mato, um estado do sistema e para ada ar o uma

taxa (CTMC) ou uma probabilidade (DTMC) omo pode ser visto na Figura 2.2;

1

3

2

4

Figura 2.2: Representação grá� a de uma adeia de Markov


� Uma adeia de Markov é representada, matemati amente, por uma matriz de tran-

sição de estados;

� Para CTMC a matriz de transição de estados é hamada de gerador in�nitesimal

(Q) e ada elemento numa linha i e numa oluna j representa a taxa de transição

do sistema do estado i para o estado j. Os elementos diagonais de Q representam o

ajuste ne essário para que a soma dos elementos de ada linha seja igual a zero;

� Para DTMC esta matriz de transição de estados é hamada de matriz esto ásti a

(P) e ada elemento representa a probabilidade de transição entre os estados. Os

elementos diagonais de P representam o ajuste ne essário para que a soma dos

elementos de ada linha dê igual a um.

2.2.3 Análise Esta ionária

O resultado da análise esta ionária para uma adeia de Markov é expresso pelo vetor de

probabilidade marginal dos estados do sistema. Esse vetor de�ne qual a probabilidade

(esta ionária) para ada um dos estados do sistema, ou seja, qual é a probabilidade de

que o sistema se en ontre naquele estado.

Supõe-se numa análise esta ionária o fun ionamento do sistema num tempo virtual-

mente in�nito.

O vetor de probabilidade é obtido pela resolução da matriz de transição através de

métodos de resolução de sistemas de equações lineares tanto numéri os quanto analíti os.

Os métodos analíti os têm a grande vantagem de forne er soluções para o sistema

sem que seja ne essário resolvê-lo numeri amente, porém têm sua apli abilidade bastante

reduzida por só servirem para modelos parti ulares, omo, por exemplo, equações para

resolver pro essos de nas imento e morte [28℄.

Os métodos numéri os, por sua vez, são bem mais abrangentes e podem ser divididos

2.2. CADEIAS DE MARKOV 13

em dois grupos [27℄:

� Métodos numéri os diretos;

� Métodos numéri os iterativos.

Os métodos numéri os diretos forne em uma solução exata para o sistema de equações

após um erto número �nito de passos e são mais indi ados para sistemas de equações

om uma matriz de transição de baixa ordem e não esparsa [26℄.

Já os métodos numéri os iterativos forne em soluções aproximadas que onvergem

para o valor orreto. Os métodos numéri os iterativos são onsiderados mais apropriados

para resolução de Cadeias de Markov do que os métodos numéri os diretos segundo onsta

na literatura [5, 26℄. Alguns exemplos de métodos numéri os iterativos são: Método de

Ja obi, Método da Potên ia e Método de Gauss-Seidel.

Será usado neste trabalho para a resolução de sistemas lineares pequenos o método

numéri o iterativo de Gauss-Seidel, que é dado pela seguinte equação:

x

(k)

j

=

b

j

�

�

P

j�1

i=0

a

ij

x

(k)

i

+

P

n�1

i=j+1

a

ij

x

(k�1)

i

�

a

jj

; 8j 2 S (2.1)

onde:

� a

ij

o elemento na linha i e na oluna j de uma matriz A;

� S é um onjunto de (0..n) onde n é a dimensão da matriz A;

� k é a iteração orrente;

� b

j

é dado pela equação 2.2 a seguir.

b

j

=

X

i2S

a

ij

x

i

(2.2)


Foi adotado o Método de Gauss-Seidel para sistemas pequenos por ele onvergir mais

rapidamente do que o Método de Ja obi e o Método da Potên ia, apesar da sua insta-

bilidade numéri a. Porém por ser apli ado somente a sistema pequenos (menos de 20

estados) sua desvantagem não é relevante.

2.3 Redes de Aut�matos Esto ásti os

As restrições impostas pelos formalismos om soluções analíti as existentes até a dé ada de

70 levaram a bus a de novos formalismos, freqüentemente mais poderosos, que utilizavam

me anismos de sin ronismo e paralelismo.

Rede de Aut�matos Esto ásti os (SAN - Sto hasti Automata Netwoks) [8, 6, 21℄ é

um destes formalismos. SAN são bastante usadas para avaliação de desempenho devido

à equivalên ia de poder de modelagem om as Cadeias de Markov [26, 28℄ e a maior

fa ilidade de des rição de modelos e obtenção de um solução numéri a.

SAN é um formalismo para modelagem de sistemas baseado em Cadeias de Markov

om grandes espaços de estados. As SAN modelam um sistema através de vários sub-

sistemas que interagem o asionalmente, ditos, quase independentes, através de eventos

sin ronizantes e funções. Cada subsistema de uma SAN é des rito através de um aut�-

mato esto ásti o e suas transições através de um pro esso esto ásti o de tempo ontínuo

ou dis reto de�nido por uma distribuição exponen ial [2℄.

Para este trabalho só será utilizado modelos SAN om transições de�nidas por uma

es ala de tempo ontínua.

As SAN são bastante interessantes para modelar, prin ipalmente, sistemas distribuídos

em que as unidades independentes de pro essamento não interagem entre si a todo o

momento [5℄.

2.3. REDES DE AUTÔMATOS ESTOCÁSTICOS 15

Com a utilização de aut�matos esto ásti os para representar os subsistemas quase

independentes de uma SAN pode-se reduzir os prejuízos ausados pela explosão do espaço

de estados das Cadeias de Markov [26, 28, 6℄ viabilizando soluções numéri as e� ientes

[5℄.

2.3.1 Aut�matos Esto ásti os

Aut�mato é um modelo matemáti o de um sistema que possui entradas e saídas dis retas.

O sistema pode se en ontrar em qualquer um dentre um número �nito de estados do

sistema, o que resume as informações sobre entradas anteriores e o que é ne essário para

determinar o omportamento do sistema para as entradas seguintes [9℄.

Baseado nessa de�nição, pode-se des rever um aut�mato omo um onjunto �nito de

estados e um onjunto de transições entre esses estados. A denominação de esto ásti os

atribuída a esses aut�matos dá-se pela razão do tempo ser tratado om uma variável

aleatória om distribuição exponen ial [2℄.

O estado do modelo SAN, hamado de estado global é de�nido pela ombinação do

estado de todos os aut�matos. O estado individual de ada aut�mato é hamado de estado

lo al.

2.3.2 Eventos

Eventos são o orrên ias de transições que mudam o estado de um aut�mato. Transição

é a tro a de um estado para outro dentro de um aut�mato. Nos modelos SAN dois tipos

de eventos ausam transições entre estados:

� Eventos Lo ais - O primeiro tipo de transição de estados são ausados por eventos

lo ais e apesar de serem independentes, o orrem um de ada vez pois numa es ala

de tempo ontínua, nun a podem o orrer duas transições ao mesmo tempo. Os

eventos lo ais mudam somente o estado lo al do aut�mato em que o orreram e não


são in�uen iadas ou mesmo in�uen iam o estado de outros aut�matos. A Figura

2.3 mostra uma SAN om dois aut�matos apenas om eventos lo ais.

�

2

�

1

�

3

�

4

�

5

x

(1)

y

(1)

z

(1)

u

(2)

w

(2)

A

(1)

A

(2)

Figura 2.3: SAN apenas om eventos lo ais

Na Figura 2.4 é apresentado o aut�mato ombinado da Figura 2.3.

�

5

�

4

�

4

xw

yu

yw

zw

zu

�

5

�

5

�

4

xu

�

2

�

2

�

3

�

3

�

1

�

1

Figura 2.4: Aut�mato ombinado da Figura 2.3

� Eventos Sin ronizantes - Os eventos sin ronizantes são um pou o mais omplexos do

que os eventos lo ais por terem a ela vários fatores asso iados, omo, por exemplo:

� Um identi� ador de evento sin ronizante asso iado a duas ou mais transições

sin ronizadas;

� Uma taxa de disparo asso iada a ada evento sin ronizante.

A o orrên ia do evento sin ronizante dá-se simultaneamente em todos os aut�matos

envolvidos. Pode-se ver o pro esso de sin ronização omo uma relação do tipo

2.3. REDES DE AUTÔMATOS ESTOCÁSTICOS 17

mestre-es ravo, em que a o orrên ia do evento sin ronizante em qualquer aut�-

mato, es olhido omo mestre do evento, obriga a o orrên ia do evento nos outros

aut�matos envolvidos, ditos aut�matos es ravos. Os eventos sin ronizantes são rep-

resentados no aut�mato mestre pela tripla (id,� ,�), onde id é o identi� ador do

evento sin ronizante, � é a taxa de disparo e � é a probabilidade de o orrên ia. Nos

aut�matos es ravos a taxa de disparo deve ser 1, sendo a tripla es rita da seguinte

maneira (id, 1, �). Para transições asso iadas a um mesmo evento sin ronizante

partindo do mesmo estado lo al deve-se apresentar a probabilidade de es olha en-

tre estas transições. Conseqüentemente o somatório destas probabilidades deve ser

igual a 1. Uma SAN om um evento sin ronizante é apresentado na Figura 2.5.

�

2

�

1

�

4

(s; 1; 1)

�

3

; (s; �

5

; �

1

)

(s; �

5

; �

2

)

x

(1)

y

(1)

z

(1)

u

(2)

w

(2)

A

(1)

A

(2)

Figura 2.5: SAN om um evento sin ronizante

O aut�mato equivalente à rede apresentada na Figura 2.5, ombina os dois aut�-

matos em um só, om é visto na Figura 2.6.

�

4

�

4

xu

zu

�

3

�

4

�

2

�

2

xw

zw

�

3

yw

�

1

�

1

yu

�

5

�

1

�

5

�

2

Figura 2.6: Aut�mato equivalente om transições sin ronizadas


2.3.3 Funções

As taxas de o orrên ia de eventos lo ais e sin ronizantes podem ser tanto onstantes quan-

to fun ionais. Para taxas de o orrên ia onstantes asso ia-se a elas apenas um número

ou expressão que independe do estado do sistema. Já, para as taxas fun ionais, as quais

pode-se asso iar tanto a eventos lo ais omo sin ronizantes, não tem uma taxa �xa para

o orrên ia mas sim obede e a uma função do estado lo al de outros aut�matos da SAN. A

Figura 2.7 apresenta uma SAN om taxas fun ionais que obede e a função representada

na Equação 2.3.

f =

8

>

>

>

>

>

<

>

>

>

>

>

:

�

1

se A

(1)

= x

(1)

;

0 se A

(1)

= y

(1)

;

�

2

se A

(1)

= z

(1)

:

(2.3)

�

2

�

1

f

(s; 1; 1)

�

3

; (s; �

5

; �

1

)

(s; �

5

; �

2

)

x

(1)

y

(1)

z

(1)

u

(2)

w

(2)

A

(1)

A

(2)

Figura 2.7: SAN om taxas fun ionais

O aut�mato equivalente a SAN representada na Figura 2.7 é mostrado abaixo na

Figura 2.8

Todas as SAN om vários aut�matos podem ser representadas por um úni o aut�mato

ombinado, onde estão des ritos todos os estados da rede.

As SAN são des ritas formalmente através de álgebra tensorial. Mais informações

sobre o formalismo SAN podem ser en ontradas em [21℄.

2.4. REDES DE FILAS DE ESPERA 19

xu

zu

�

3

�

2

�

2

xw

zw

�

3

yw

�

1

�

1

yu

�

2

�

1

�

5

�

1

�

5

�

2

Figura 2.8: Aut�mato om taxas fun ionais

2.4 Redes de Filas de Espera

Proposta na dé ada de 50 o formalismo de Redes de Filas de Espera (QN - Queueing

Networks) [13, 19℄ teve seu surgimento om os trabalhos de Ja kson [10℄ e se tornaram

um dos mais onhe idos e utilizados formalismos para modelagem de sistemas. A grande

popularidade das QN se deve prin ipalmente a sua simpli idade, que se baseia na idéia

de lientes ( onsumidores) passando através de �las (estações de serviços).

As QN tiveram grande avanço até o �nal da dé ada de 70, devido prin ipalmente a

pesquisa desenvolvida por Little [14℄, por Baskett, Chandy, Muntz e Pala ios [3℄ e por

Reiser e Lavenberg [23℄. Os prin ipais resultados desta pesquisa foram soluções a forma-

produto para ertas lasses de QN.

Nestes trabalhos foram de�nidas equações que se apli am basi amente a duas lasses

de QN. As Redes de Filas de Espera Abertas (OQN - Open Queueing Networks), nas quais

o número de lientes é variável, e as Redes de Filas de Espera Fe hadas (CQN - Closed

Queueing Networks), as quais têm um número �xo de lientes na rede. Os algoritmos

para resolução e maiores detalhes sobre essas duas lasses de QN são apresentados nos

itens 2.4.5 e 2.4.6.


QN são onstituídas de várias �las (estações de serviços), as quais são one tadas entre

si. Cada um dessas onexões representam as probabilidades de transição de uma �la para

outra, des revendo possíveis aminhos por onde os lientes podem passar. Cada �la ou

estação de serviço é uma entidade independente que modela um re urso de um sistema

real e des reve a dis iplina de a esso de liente àquele re urso. Para des rever ada �la se

faz uso então da Notação de Kendall, exposta anteriormente na seção 2.1.1. Os lientes

por sua vez, são entidades que utilizam os re ursos serialmente. Os lientes podem por

prin ípio serem transferidos entre duas estações de uma mesma rede, e até retornar para

a própria estação que havia deixado.

A de�nição formal de uma QN impli a na de�nição de ada estação de serviço e

também na de�nição dos aminhos possíveis entre as �las. A de�nição dos aminhos dá-

se através da atribuição de probabilidades de rotação dos lientes através das �las. Essa

atribuição de probabilidade de rotação é a possibilidade de que um liente saia de uma

�la i e vá para uma �la j.

Dos vários tipos de modelos QN existentes, tem-se, no ontexto deste trabalho, inte-

resse nos modelos de QN que podem ser traduzidos para Cadeias de Markov e por isso

são ditos Redes de Filas de Espera Markovianas.

2.4.1 Redes à Forma-Produto

Uma rede é onsiderada à forma-produto quando quatro hipóteses de�nidas para que se

possa obter resultados exatos são veri� adas. Estas hipóteses fazem menção à apa idade

das �las, aos pro essos de hegada e serviço, à probabilidade de rotação de lientes na

rede e ao equilíbrio de �uxo das estações.

Estas hipóteses são:

� Filas de espera om apa idade ilimitada - Por prin ípio, as redes à forma-produto

tem a apa idade das �las ilimitada. Assim, um liente sempre será admitido na


�la de uma estação, des artando a possibilidade de bloqueio ou perda de um liente

em uma estação por falta de espaço em qualquer uma das estações seguintes. Nas

CQN, essa hipótese é interpretada de uma forma direfente devido ao seu número

�xo de lientes. O omprimento dessa hipótese pelas CQN é mais detalhado em

2.4.6;

� Chegada de lientes e taxa de serviço segundo uma lei exponen ial - A hegada de

lientes é des rita por um pro esso Poiss�ni o e o tempo de serviço é expresso por

um pro esso Exponen ial, bastando assim de�nir o valor médio destes pro essos;

� Probabilidade de rotação de lientes segundo um pro esso Markoviano - A rotação

dos lientes é totalmente probabilísti a, sendo que o aminho futuro de um liente

é independente do aminho passado. Toda vez que um liente deixa uma estação

om duas ou mais possibilidades de aminho, este será de�nido aleatoriamente de

a ordo om a probabilidade de rotação de�nida. Por esta de isão ser um evento

independente dos demais estados da rede, a alternân ia entre os estados da rede

pode ser des rita por uma adeia de Markov [26, 28℄;

� Estações om omportamento esta ionário - A hipótese de esta ionariedade admiti-

da para redes à forma-produto, de�ne que o �uxo de lientes através de uma estação

deve ser equilibrado. Sendo assim, a média do número de lientes que entram deve

ser igual a média do número de lientes que saem. Para redes abertas esta hipótese

de�ne ainda que o �uxo de lientes em toda a rede também deve ser equilibrado.

2.4.2 De�nição

Segundo Fernandes e Plateau [7℄ pode-se de�nir as QN Markovianas om a utilização dos

seguintes parâmetros:

M Número de �las na rede;

R Número de diferentes lasses de lientes;

K

i

Capa idade da �la i (número máximo de lientes);


C

i

Número de servidores na �la i;

S

r

i

Tempo médio ne essário para um servidor atender um liente da lasse

r na �la i;

P

r

i;j

Probabilidade de rotação de um liente da lasse r servido na �la i

deixar esta �la e ir para �la j (estes parâmetros são usados para o ál ulo

da taxa média de visitas de lientes da lasse r na �la i que é usualmente

denotado por �

r

i

);

B

r

i;j

Pro edimento dos lientes da lasse r saídos da �la i para �la j quando

a �la j está heia. Dois pro edimentos são possíveis: perda (os lientes

deixam o modelo - existe somente em redes abertas) ou bloqueio (a �la i é

bloqueada);

!

D

i

Vetor indi ando a ordem de prioridade de serviço entre as lasses de

lientes na �la i (a ausên ia deste parâmetro indi a a inexistên ia de prior-

idade entre as lasses);

L

r

i

Taxa média de hegada de lientes da lasse r na �la i, oriundos de fora

do modelo (parâmetro existente somente em redes abertas);

N

r

População total de lientes da lasse r na rede (parâmetro existente

somente em redes fe hadas).

N Vetor om o onjunto das populações (N

1

; N

2

; :::N

r

) de todas as lasses

presentes na rede.

Dentre os índi es de desempenho que podem ser obtidos do modelo om os métodos

para soluções a forma-produto os mais omuns são:

d

r

i

Fluxo médio de lientes da lasse r através da �la i;

u

r

i

Índi e médio de utilização da �la i pelos lientes da lasse r;

n

r

i

População média de lientes da lasse r presentes na �la i;


w

r

i

Tempo médio de resposta para os lientes da lasse r na �la i.

Algumas outras notações intermediarias ainda são usadas na de�niçao ou no ál ulo

dos índi es de desempenho. São elas:

�

r

i

Taxa de visita dos lientes da lasse r na �la i. Esta taxa é al ulada

resolvendo-se um sistema linear riado a partir das probabilidades de ro-

tação dos lientes de ada lasse (P

r

i;j

). Este sistema por sua vez pode ser

resolvido por qualquer método de ál ulo número;

�

r

i

(k) Taxa média de atendimento dos lientes da lasse r na �la i quando há

k lientes na �la;

�

i

(j; k) Probabilidade marginal da �la i om j servidores e k lientes na �la.

2.4.3 Número de Servidores

As QN podem ser lassi� adas em dois tipos tratando-se do número de servidores presentes

em ada estação de serviço. Existem estações mono-servidoras e multi-servidoras. As

estações mono-servidoras ara terizam-se por possuirem apenas um servidor por estação

e o tempo de atendimento dos lientes ser independente da arga da estação. A taxa

média de atendimento de uma estação mono-servidora (�

r

i

) pode ser des rita omo:

�

r

i

(k) =

1

S

r

i

(2.4)

Onde:

k Número de lientes na estação i.

Do ontrário, as estações de serviço multi-servidoras se ara terizam por terem mais

de um servidor por estação, ou seja, o número de servidores (C

i

) de uma estação i deve

ser maior do que um. Nesse aso teremos taxas de prestação de serviço diferen iadas,

dependentes da arga da estação.


O prin ípio bási o de estações om prestação de serviço dependente de arga é a

atribuição de um tempo médio de prestação de serviço distinto, para o número de lientes

presente na estação (denotado por k). Este me anismo de dependên ia de arga pode

representar a presença de diversos servidores através de um artifí io que é o aumento da

taxa de atendimento (diminuição do tempo de prestação de serviço) quando os lientes

podem ser atendidos simultaneamente por vários servidores.

O ál ulo da taxa média de atendimento (�

r

i

) para estações multi-servidoras é expresso

pela seguinte equação

2

.

�

r

i

(k) =

min(k; C

i

)

S

r

i

(2.5)

Onde:

k Número de lientes presentes na estação i.

A possibilidade de de�nirmos um tempo de prestação de serviço dependente da arga

não se resume a estações multi-servidoras, mas esta apli ação (expressa pela Equação 2.5)

é freqüentemente utilizada para representar o uso de mais de um re urso simultaneamente.

Em estações onde o número de servidores é igual à apa idade da �la (C

i

= k) temos

evidentemente uma simpli� ação da Equação 2.6, para:

�

r

i

(k) =

k

S

r

i

(2.6)

Pois, o número de servidores (C

i

) é idênti o ao próprio limite da variação do número

de lientes presentes na estação ( apa idade total da �la i).

2

A notação min(a; ::; z) signi� a o menor valor numéri o entre os valores a até z.


2.4.4 Número de Classes

As QN podem ser lassi� adas de duas maneiras om relação ao número de tipos de

lientes tratados diferen ialmente.

Podemos distinguir as QN que tratam um tipo úni o e indistinguível de lientes. Esse

tipo de QN é denominado de mono- lasse e atende todos os lientes de uma mesma

maneira.

Nas QN multi- lasse, omo são hamadas as QN que tratam vários tipos de lientes

de forma diferen iada, várias ategorias de lientes podem ser de�nidas e ada tipo ou

ategoria representa uma lasse diferente. Para estes tipos distintos de lientes é possível

então de�nir tempos médios de prestação de serviço diferen iados para ada lasse r de

lientes (S

r

i

). Da mesma forma ertos tipos lientes podem ir ular entre estações om

probabilidades de rotação distintas para ada lasse r (P

r

i;j

) e até é possível que algum

tipo de liente não utilize os serviços de uma erta estação. No aso de redes fe hadas

é pre iso ainda de�nir o número de lientes existente na rede para ada lasse (N

r

). No

aso de redes abertas, pre isa-se também de�nir taxas de hegada distintas nas estações

para ada lasse de lientes (L

r

i

). No entanto, o número de servidores (C

i

), assim omo a

apa idade de ada �la (K

i

) são independentes do número de lasses.

Assumiu-se para este trabalho ( omo visto no item 2.4.2) R omo a notação do número

total de lasses de lientes diferen iados para uma determinada rede.

Adi ionalmente é possível ainda de�nir prioridades e mesmo políti as de atendimento

entre lientes de lasses distintas. A dis iplina tradi ional de �la (FIFO) pode ser admitida

entre todas as lasses, porém também é possível admitir prioridades absolutas (uma lasse

sempre tem atendimento prioritário sobre outra), ou até mesmo, políti as omplexas

do tipo time sharing, onde fatias de tempo são distribuídas para ada lasse e pode-se

estabele er preferên ias de atendimento sobre estas.


Note-se porém que não é ne essário que todas as estações sirvam todas as lasses de

lientes. Isso é de�nido pelas probabilidades de rotação expressas individualmente para

ada lasse. Na verdade a úni a limitação imposta é que a hipótese da esta ionariedade

deve ontinuar sendo veri� ada para ada lasse de liente observada isoladamente. Se

existir pelo menos uma estação multi- lasse na rede, então toda a rede é tida omo multi-

lasse, senão a rede é de�nida omo mono- lasse.

2.4.5 Redes de Filas de Espera Abertas

Redes de Filas de Espera Abertas (OQN - Open Queueing Networks) são uma lasse

de QN onde o número de lientes ( onsumidores) na rede não é �xo. Isso é possível

devido a rede ter entradas e saídas em determinadas �las, por onde os lientes oriúndos

do exterior do modelo podem tanto entrar omo sair do ontexto do sistema modelado.

A representação grá� a de uma OQN pode ser vista na Figura 2.9.

Figura 2.9: Rede de Filas de Espera Aberta

Para que uma OQN seja onsidereda à forma-produto, esta deve respeitar as hipóteses

apresentadas em 2.4.1 da seguinte maneira.

Na hipótese da esta ionariedade, a qual deve ser respeitada pelas OQN, determina as

ondições abaixo para essa lasse de QN:

� Para as OQN omo um todo, assim omo para ada estação espe í� a, o número

de lientes que entra deve ser igual ao número de lientes que sai se observarmos a

rede por um tempo in�nito;


� Nenhum liente pode ser gerado ou onsumido em uma estação;

� A soma das probabilidades de saída de lientes da lasse r de uma �la i (P

r

i;j

) para

todas as demais �las (todos valores possíveis de j) devem estar no intervalo entre 0

e 1. A proporção de lientes que abandonarão o modelo para o exterior é dado pela

diferença entre esta soma e o valor 1.

Deve-se obede er também uma ondição de estabilidade, onde diz que:

� Um liente vindo do exterior sempre poderá visitar todas as estações da rede, ainda

que isso não a onteça ne essariamente na mesma passagem pelo modelo;

� Ao sair de toda e qualquer estação o liente sempre poderá atingir, passando por

tantas estações quantas foemr ne essárias, uma das saídas para o exterior do modelo.

Para redes abertas à forma-produto é assumido que a �la não tem a sua apa idade

(K

i

) limitada (K

i

= 1). Da mesma maneira, as �las om apa idade in�nita que não

on orrem por servidores (número de servidores igual à apa idade da �la) assume-se a

mesma notação: C

i

=1.

Com os trabalhos desenvolvidos por Baskett, Chandy, Muntz e Pala ios [3℄, foram

de�nidas equações para obtenção de índi es de desempenho para as OQN. Baseadas no

Teorema da Chegada e na Lei de Little, estas equações se apli am a redes à forma-produto

para OQN multi- lasses.

São apresentadas a seguir as equações para obtenção de alguns índi es de desempenho.

O �uxo médio de lientes de uma lasse r através de uma estação i (d

r

i

) em uma OQN

é dado pela Equação 2.7:

d

r

i

= �

r

i

M

X

j=0

L

r

j

(2.7)

Onde:


P

M

j=0

L

r

j

A taxa de hegada total de lientes do exterior da lasse r no modelo;

�

r

i

Taxa média de visita dos lientes da lasse r em ada estação i.

O �uxo médio geral de uma estação i (d

i

) é al ulado omo:

d

i

=

R

X

r=0

d

r

i

(2.8)

O índi e médio de utilização da �la i pelos lientes de lasse r (u

r

i

), nas OQN é obtido

pela Equação 2.9 abaixo:

u

r

i

= d

r

i

S

r

i

(2.9)

Cada estação de serviço deve ser apaz de atender todos os lientes de todas as lasses

para que a hipótese de esta ionariedade seja respeitada. Isso é indi ado pelo índi e de

utilização geral da �la (u

i

)e deve ser obrigatoriamente menor que 1. O índi e de utilização

geral (u

i

) é al ulado omo sendo:

u

i

=

R

X

r=1

u

r

i

(2.10)

Cabe ressaltar que, aso u

i

> 1 para qualquer �la i, a rede omo um todo não respeita

e hipótese da esta ionariedade. Sendo assim, os índi e a seguir não ne essitariam ser

al ulados.

A Equação 2.11 a seguir é utilizada para obtenção da população média de lientes de

lasse r na �la i (n

r

i

):

n

r

i

=

u

r

i

(1� u

i

)

(2.11)


A população média onsiderando todos os lientes de todas lasses na �la i (n

i

) é dada

por:

n

i

=

R

X

r=1

n

r

i

(2.12)

O tempo médio de resposta dos lientes da lasse r na estação i (w

r

i

) pode ser al ulado

pela Equação 2.13 abaixo:

w

r

i

=

d

r

i

(1� u

i

)

(2.13)

O tempo médio de resposta geral dos lientes numa estação i (w

i

) é uma ponderação

dos tempos médios de resposta da lasse pela a�uxo re ebido na estação i por lientes

desta lasse, ou seja:

w

i

=

R

X

r=1

(d

r

i

w

r

i

)

d

i

(2.14)

É importante ressaltar que através destes índi es de desempenho pode-se avaliar o

modelo dete tando possíveis gargalos e se o modelo respeita a hipótese de esta ionariedade

nas �las de uma OQN.

2.4.6 Redes de Filas de Espera Fe hadas

Redes de Filas de Espera Fe hadas (CQN - Closed Queueing Networks) são uma ategoria

de QN em que o número de lientes na rede é �xo, ou seja, não há entrada nem saída de

lientes do ou para o exterior do sistema modelado. Na Figura 2.10 pode ser vista uma

representação grá� a para as CQN.

As CQN devem respeitar algumas ara terísti as bási as omo o prin ípio onservativo


Figura 2.10: Rede de Filas de Espera Fe hada

(o número de lientes é �xo), o qual determina que:

� Nenhuma interação a onte e entre o modelo e o que está de�nido fora do modelo,

ou seja, ninguém entra e ninguém sai ;

� Nenhum liente pode ser gerado ou onsumido por qualquer estação de serviço;

� A soma das probabilidades de saída de lientes de um �la i (P

r

i;j

) para todas as

demais �las (todos valores possíveis de j) deve ser igual a 1, ou seja, saindo de

uma estação i todo liente deve obrigatoriamente se dirigir a uma outra estação do

modelo ou retornar para ela mesma.

A ondição de estabilidade, ou seja, ao sair de uma estação qualquer, um liente

sempre poderá passar por todas as estações da rede. Para isso a rede deve se enquadrar

nas seguintes de�nições:

� A rede não pode possuir sumidouros de lientes, ou seja, um grupo de estações

onde se entra e não há possibilidade de saída;

� Existe um aminho possível ( om probabilidades de rotação que não sejam nulas)

que permite passar por todas as estações repetidas vezes, riando-se assim i los

que englobam todas as estações.

O prin ípio onservativo juntamente om a hipótese da estabilidade permite que a rede

possua um estado de equilíbrio, ou seja, pode-se de�nir estados médios para a rede depois

do fun ionamento em um tempo su� ientemente grande.


Ao ontrário das OQN à forma-produto, nas CQN também à forma-produto a a-

pa idade máxima de ada �la (K

i

) é de�nida, visto que não faz sentido ter �las om

apa idade maior do que o número total de lientes na rede. Sendo assim, a apa idade

máxima de ada �la (K

i

) é de�nida omo tendo o tamanho do número máximo de lientes

na rede, para que nenhum liente �que bloqueado por não haver apa idade em alguma

estação posterior.

Para obtenção dos índi es de desempenho para CQN multi- lasse e multi-servidor

utiliza-se o algoritmo da Análise do Valor Médio ( MVA - Mean Value Analysis) proposto

por M. Reiser e S. S. Lavenberg em 1980[23℄. Esse algoritmo é substituto do popular

algoritmo da Convolução ( ál ulo da onstante de normalização) proposto por Buzen em

1973 [4℄. São apresentadas a seguir as equações para obtenção dos índi es de desempenho

mais omumente utilizados para ada lasse na ordem em que devem ser exe utadas.

O tempo médio de resposta dos lientes da lasse r na �la i (w

r

i

), para �las om

dis iplina de serviço tipo FIFO e mono-servidor

3

, quando há N lientes na rede é:

w

r

i

(N) = S

r

i

(1 + n

i

(N � 1

r

)) (2.15)

Para estações multi-servidor, no entanto, a equação orreta é:

w

r

i

(N) =

S

r

i

C

i

1 + n

i

(N � 1

r

) +

C

i

�2

X

j=0

(C

i

� j � 1) �

i

(j; N � 1

r

)

!

(2.16)

De�ne-se a probabilidade marginal(�

i

(j; N)), quando j 6= 0 omo sendo:

�

i

(j; N) =

1

j

R

X

r=1

�

r

i

S

r

i

d

r

o

(N) �

i

(j � 1; N � 1

r

)

!

(2.17)

3

Para todas as �las mono-servidor é utlizada a equação a seguir, apesar da rede ser multi-servidor

desde que haja pelo menos �la multi-servidor


Para j = 0 é de�nida a seguinte equação:

�

i

(0; N) = 1�

1

C

i

R

X

r=1

�

r

i

S

r

i

d

r

o

(N)

C

i

�1

X

j=1

(C

i

� j) �

i

(j; N)

!

(2.18)

Por se um algoritmo re ursivo de�ne-se os ritérios de parada omo:

�

i

(0; 0) = 1 (2.19)

e

�

i

(j; 0) = 0 (2.20)

O �uxo médio de lientes da lasse r através da �la i (d

r

i

) quando existem (N) lientes

de ada lasse na rede pode ser al ulado omo sendo:

d

r

i

(N) = �

r

i

d

r

o

(N) (2.21)

Onde �

r

i

é a taxa média de visita dos lientes da lasse r na �la i e é obtido om

a resolução da matriz de probabilidade de rotação da lasse r por qualquer método de

resolução de sistemas lineares. A taxa de �uxo padrão da lasse r (d

r

o

) quando existem N

lientes de ada lasse na rede é obtida pela Equação 2.22 a seguir.

d

r

o

(N) =

N

r

P

M

i=1

�

r

i

w

r

i

(N)

(2.22)

O índi e médio de utilização da �la i pelos lientes de lasse r (u

r

i

) quando há N

lientes na rede é al ulado pela seguinte equação.

u

r

i

(N) =

d

r

i

(N)

�

r

i

(N)

(2.23)


A população média de lientes da lasse r presentes na �la i (n

r

i

) quando há N lientes

de ada na rede é al ulada pela equação 2.24 abaixo.

n

r

i

(N) = d

r

o

(N)w

r

i

(N) �

r

i

(2.24)

É de�nido, no entanto, que quando o número de lientes da lasse r na �la i (N) for

zero a população média da �la i para a lasse r também o será. Isso se faz ne essário

pois sendo esse um algoritmo re ursivo, omo pode-se ver na equação do tempo médio de

resposta (w

r

i

)(2.15), é ne essário um ritério de parada.

n

r

i

(0) = 0 (2.25)

Abaixo são des ritas as equações usadas para obtenção dos índi es gerais de ada �la.

O �uxo médio de lientes pela �la i (d

i

) quando existem N lientes na rede é dado

por:

d

i

(N) =

R

X

r=1

d

r

i

(N) (2.26)

O índi e médio de utilização geral da �la i (u

i

) quando existem N lientes na rede é:

u

i

(N) =

R

X

r=1

u

r

i

(N) (2.27)

A população média de lientes na �la i (n

i

) é de�nido por:

n

i

(N) =

R

X

r=1

n

r

i

(N) (2.28)


Para o tempo médio de resposta para os lientes da �la i (w

i

) quando há N lientes

na rede é dado por:

w

i

(N) =

P

R

r=1

w

r

i

N

r

P

R

r=1

N

r

(2.29)

Pode-se onferir maiores exemplos de modelagem e utilização dos formalismo apresen-

tados neste apítulo na PARTE III (Manual do Usuário) deste trabalho.

O Apêndi e A deste trabalho apresente um resumo de todas as notações utilizadas.

Capítulo 3

Conversão entre Formalismos

Como foi men ionado anteriormente no Capítulo 2, as Redes de Filas de Espera (QN

- Queueing Networks)[13, 19℄ são bastante utilizadas por sua fa ilidade de modelagem,

mas no entanto os usuários sofrem om suas limitações (QN a forma-produto). Já, Re-

des de Aut�matos Esto ásti os (SAN - Sto hasti Automata Networks é um fomralismo

mais poderoso e tem menos limitações que as QN. Porém, sua omplexidade di� ulta a

modelagem.

Com a possibilidade de traduzir modelos do formalismo QN para o formalismo SAN

[8, 6, 21℄, um onversor automáti o pode ser riado para que se possa aproveitar o onforto

da modelagem em QN e o poder de resolução das SAN.

Os modelos onvertidos para SAN podem então ser resolvidos pela ferramenta PEPS,

a qual implementa vários métodos para resolução de modelos SAN.

Para que fosse possível a onversão e a representação de um mesmo sistema através de

modelos QN e SAN ompreendidos pelas duas ferramentas (MQNA e PEPS), de�niu-se

então formatos de arquivos de entrada e saída para estes formalismos. Estes formatos

servem para que a ferramenta MQNA possa re onhe er e armazenar um modelo QN de

um modo textual, visto que o usuário poderá riar ou editar seus moelos diretamente

nestes arquivos, e transforma-los posteriormente em um arquivo om um modelo SAN

36 CAPÍTULO 3. CONVERS�O ENTRE FORMALISMOS

equivalente que seja re onhe ido pela ferramenta PEPS [20℄. Os formatos de arquivos

que serão utilizados são baseados nas gramáti as espe i� adas para a ferramenta MQNA

e para a ferramenta PEPS.

No aso da gramáti a para representação de modelos QN, por ainda não existir um

formato de arquivo padrão para este formalismo, foi riada uma gramáti a espe í� a para

a ferramenta MQNA, a qual atende as exigên ias da ferramenta quanto ao formalismo

QN e ao método de onversão. Para os modelos SAN foi utilizada a gramáti a já de�nida

para a ferramenta PEPS.

As duas gramáti as a ima itadas são apresentadas nos itens 3.3 e 3.4.

3.1 Ferramenta PEPS

PEPS - Performan e Evaluation of Parallel Systems é uma ferramenta de software a a-

dêmi a que ofere e re ursos de modelagem e métodos iterativos (Método da Potên ia,

Método de Arnoldi e GMRES)[25, 27℄ para resolução de modelos SAN. Por apli ar os

on eitos de SAN, apresentados anteriormente no item 2.3, PEPS onsegue evitar os

prejuízos da explosão do espaço de estados das Cadeias de Markov e forne er soluções

numéri as e� ientes. PEPS é uma ferramenta para ambiente Unix om ódigo aberto e

interfa e textual, omo pode ser visto na Figura 3.1.

1) Compile a SAN model 5) Load data structures2) Solve a compiled SAN model 6) Inspect data structures3) Probability vector facilities 7) Sparse matrix facilities4) Preference 8) About this version

0) Exit PEPS (Option 0 always exits the current menu)

+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+| This is PEPS 2000 − The SAN tools | | relesead on: Oct 11 2000 −− compiled on: Oct 23 2001 | +−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−+

Figura 3.1: Interfa e da ferramenta PEPS

3.2. MÉTODO DE CONVERS�O 37

A ferramenta e maiores expli ações sobre o projeto PEPS podem ser en ontradas na

internet nos endereços:

� http://www.inf.pu rs.br/�paulof/peps.html

� http://www-apa he.imag.fr/software/peps

A gramáti a para os arquivos de entrada no formato SAN da ferramenta PEPS, que é

expli ada mais adiante neste apítulo (seção 3.4), será usada também omo formato do

arquivo de saída da ferramenta MQNA quando da onversão de QN para SAN.

3.2 Método de Conversão

Na ferramenta MQNA é implementado o método de onversão QN para SAN onforme

de�nido por Fernandes e Plateau em [7℄. Este método é parti ularmente interessante para

QN que não tenham solução à forma-produto, omo por exemplo, �las om bloqueio, o

que foge as espe i� ações das QN à forma-produto. Porém, CQN à forma-produto podem

ser onvertida em modelos SAN sem fugir das regras para QN à forma-produto, desde

que a apa idade das �las seja igual ao número total de lientes na rede.

3.2.1 Modelo Bási o

A idéia prin ipal deste método de onversão se baseia em transformar ada �la i de um

modelo QN em um aut�mato esto ásti o nos modelos SAN.

A tro a de lientes entre �las diferentes (P

i;j

- probabilidades de rotação) num modelo

QN é representada por eventos sin ronizantes nos modelos SAN. Essa sin ronização entre

dois aut�matos representa a saída de um lientes da uma �la e a hegada em outra numa

QN.

Abaixo é apresentado um exemplo de onversão de um modelo CQN mono- lasse om

três estações de serviço para um modelo SAN equivalente.


1

3

2

�2

M = 3

R = 1

N = 4

C

1

= 1

C

2

= 1

C

3

= 1

S

1

1

= �1

S

1

2

= �2

S

1

3

= �3

�1

K

1

= 3

K

2

= 2

P

1

1;2

= �1

K

3

= 2

P

1

1;3

= �2

Figura 3.2: Modelo CQN mono- lasse

A Figura 3.3 apresenta o modelo CQN da Figura 3.2 onvertido para um modelo SAN

equivalente.

A

(1)

(e

31

; 1; 1)

(e

12

;

1

�1

�1; 1)

(e

13

;

1

�1

�2; 1)

(e

12

;

1

�1

�1; 1)

(e

13

;

1

�1

�2; 1)

(e

12

;

1

�1

�1; 1)

(e

13

;

1

�1

�2; 1)

A

(2)

(e

12

; 1; 1)

(e

12

; 1; 1)

(e

21

; 1; 1)

(e

21

; 1; 1)

(e

21

; 1; 1)

(e

31

; 1; 1)

(e

31

; 1; 1)

(e

21

;

1

�2

; 1)

(e

21

;

1

�2

; 1)

A

(3)

(e

31

;

1

�3

; 1)

(e

31

;

1

�3

; 1)

(e

13

; 1; 1)

(e

13

; 1; 1)

1

1

1

0 00

2 2 2

3

Figura 3.3: Modelo SAN equivalente ao modelo CQN anterior

A seguir é expli ado om mais detalhes a riação dos aut�matos e o uso dos eventos

sin ronizantes para redes multi- lasses.

3.2.2 Modelos Multi-Classe

No aso de QN multi- lasses, essa onversão é um pou o mais so�sti ada, pois transforma-

se ada par " lasse r que visita a �la i" em um aut�mato esto ásti o, onde o número de

lientes da lasse r na �la i representa o estado lo al do aut�mato.

Outro fator que difere a onversão de redes mono e multi- lasses é quanto ao número

3.2. MÉTODO DE CONVERS�O 39

de aut�matos que serão riados. Nas redes mono- lasse, o número de aut�mato riados

será igual ao número de �las existente no modelo QN. Já, para rede multi- lasse, o número

total de aut�mato riados depende das rotas entre as �las no modelo QN, pois só serão

riados os aut�matos por onde passam lientes, ou seja, se em uma �la i não faz parte

da sub-rede por onde passam lientes da lasse r, não será riado o aut�mato para o par

" lasse r �la i".

O número de nodos do aut�mato deve ser igual a apa idade da �la do modelo QN

mais 1, pois o estado zero também deve ser representado.

A tro a de lientes dos modelos QN ontinua sendo modelada por eventos sin ronizante

nos modelos SAN, porém, para QN multi- lasses usa-se ainda taxas fun ionais para re-

presentar restrições da apa idade das �las.

Um modelo OQN om duas lasses diferen iadas de lientes é apresentada na Figura

3.4. É interessante ressaltar que uma das lasses não passa por todas as �las existente no

modelo, neste aso não será riado o aut�mato que representaria o par " lasse r na �la

i".

1

3

2

�2

�1

R = 2

M = 3

K

1

= 3

K

2

= 2

K

3

= 2

C

1

= 1

C

2

= 1

C

3

= 1

L

2

1

= �2

L

1

1

= �1

P

1

1;2

= �1

P

1

1;3

= �2

P

2

1;3

= 1:0

S

1

1

= �1

S

1

2

= �2

S

1

3

= �3

S

2

1

= �4

S

2

3

= �5

Figura 3.4: Modelo OQN multi- lasse

Abaixo é representado um modelo SAN equivalente ao modelo OQN multi- lasse da

Figura 3.4.


3

2

1

0

�1

�1

A

(1

1

)

A

(3

2

)

0

1

(e

2

13

; 1; 1)

1

�5

1

�5

A

(3

1

)

(e

2

13

; 1; 1)

(e

1

13

; 1; 1)

1

�3

1

�3

(e

1

13

; 1; 1)

2

2

1

0

2

0

1

(e

1

12

; 1; 1)

(e

1

12

; 1; 1)

A

(2

1

)

1

�2

1

�2

�1

(e

1

12

;

1

�1

�1; 1)

(e

1

13

;

1

�1

�2; 1)

(e

1

12

;

1

�1

�1; 1)

(e

1

13

;

1

�1

�2; 1)

(e

1

12

;

1

�1

�1; 1)

(e

1

13

;

1

�1

�2; 1)

A

(1

2

)

2

3

1

0

�2

�2

�2

(e

2

12

;

1

�4

; 1)

(e

2

12

;

1

�4

; 1)

(e

2

12

;

1

�4

; 1)

Figura 3.5: Modelo SAN equivalente

3.3 Gramáti a para Des rição de QN em MQNA

A gramáti a riada para a des rição de QN na ferramenta MQNA abrange as duas lasses

de QN apresentadas nos itens 2.4.5 e 2.4.6.

Para uma melhor ompreensão da gramáti a empregada para ada lasse de QN,

visto que ada lasse de QN tem suas ara terísti as próprias, a mesma será apresentada

primeiramente para modelos CQN e em seguida para modelos OQN.

3.3.1 Unidades Sintáti as

Conven ionou-se alguns formatos para números e identi� adores que serão usados na

gramáti a. Seguem alguns exemplos:

� Número inteiro: 1, 3, 5, 1023, 5006;

� Número real : 10, 15.0, 123.43, 0.65, 10e-1, 5.0E+2;

� Identi� ador : um identi� ador é uma seqüên ia qualquer da ara teres alfa-numéri os

que obrigatoriamente deve omeçar por uma letra qualquer, por exemplo, "rede" e

"�la2" são identi� adores válidos.

� Palavras reservadas: Existe na gramáti a um onjunto de palavras reservadas om

a função de identi� ar ada parte do modelo. Essa palavras são:

3.3. GRAMÁTICA PARA DESCRIÇ�O DE QN EM MQNA 41

Palavra Utilização

qn De�ne um modelo CQN

oqn De�ne um modelo OQN

lass Identi� ador de lasse

servers Número de servidores

population População da lasse nos modelos CQN

apa ity Capa idade da �la

queue Identi� ador de �la

network De�ne iní io da des rição da rede

de larations De�ne iní io das de larações de lasses

e �la

servi e Tempo de serviço, utilizado juntamente

om a palavra time

time Tempo de serviço, pre edido da palavra

servi e

arrival Taxa de hegada, utilizada om a

palavra rate

rate Taxa de hegada, pre edido da palavra

arrival

rot De�ne a probabilidade de rotação dos

lientes

Tabela 3.1: Palavras reservadas da gramáti a para MQNA

No Apêndi e B podem ser obtidas as regras da gramáti a utilizada assim omo a

relação de todas as palavras reservadas e símbolos da mesma.

3.3.2 Modelos CQN

A gramáti a para des rever CQN pode ser dividida em dois blo os prin ipais e sub-

dividido em blo os menores omo veremos a seguir. O primeiro vem logo a seguir da

de�nição do tipo do modelo e do número de lasses e �las, nele onsta basi amente as

de larações do modelo. No segundo blo o é a des rição da rede em si.

De�nição do modelo

De�ne qual o tipo de modelo QN que será des rito, no aso deste tópi o, de�ne-se o tipo

pela palavra reservada " qn". Após a de�nição do tipo de modelo atribui-se um nome


através de um identi� ador qualquer. Em seguida informa-se o número de lasses e �las

presentes no modelo. Abaixo é apresentada a sintaxe exata para des rição do modelo.

De�nição do modelo - CQN

qn nome do modelo (número de lasses, número de �las)

De laração de Classes e Filas

Des rição do Modelo

Onde:

nome do modelo O nome do modelo é de�nido através de um identi� ador qualquer,

omo nos exemplos mostrados a ima;

número de lasses Número de lasses que estarão presentes na rede, o qual deve ser

um número inteiro;

número de �las Número de �las que estarão presentes, deve ser representado por um

número inteiro.


Neste blo o é de larado as lasses e �las que serão utilizadas no de orrer do modelo. A

de laração de lasses é feita pela palavra reservada " lass" seguida do nome atribuído

para a lasse. Na de laração de �las utiliza-se da palavra "queue" para de�nir a �la, a

qual é seguida do nome atribuído para a �la. Abaixo segue a sintaxe orreta que deve ser

utilizada.

De laração de Classes e Filas - CQN

de larations {

lass nome da lasse;

queue nome da �la;

...

}


Onde:

nome da lasse Nome da lasse é de�nido através de um identi� ador qualquer e re-

presenta uma lasse diferen iada de lientes;

nome da �la Nome da �la também é de�nido por um identi� ador e de�ne a identi-

� ação para um re urso (�la) do modelo.

A ordem em que as lasses e as �las são de laradas pode ser alterada, por exemplo,

pode-se de larar todas as �las antes das lasses, ou mesmo inter alar as duas. Porém

os nomes, tanto das lasses omo das �las, devem ser diferentes. Tanto para as lasses

omo para as �las, o número de de larações deve ser igual ao número de lasses e �las

de laradas anteriormente na De�nição do modelo.


É neste blo o que o modelo é realmente des rito. Este blo o pode ser dividido em outros

dois blo os menores. O primeiro deles diz respeito a de�nição do número total de lientes

em ada lasse (De�nição de Populações). O segundo ontém a des rição de ada �la

presente no modelo (Des rição de Filas). Segue a sintaxe utilizada neste blo o.

Des rição do Modelo - CQN

network {

De�nição de Populações

Des rição de Filas

}

De�nição de Populações

Estabele e qual a população total (número total de lientes) para ada uma das lasses

perten entes ao modelo. O número de de larações de população deve ser igual ao número

de lasses de laradas na De�nição do Modelo. A de laração de população é feita da

seguinte maneira:


De�nição de Populações - CQN

population lass nome da lasse = população;

...

Onde:

nome da lasse Nome de ada lasse no modelo, a qual foi de�nido no blo o de De la-

ração de Classes e Filas.

população Número inteiro que de�ne a população de ada lasse no modelo.

A de�nição de populações das lasses deve ser repetida o número de vezes igual ao

número de lasses de laradas na De�nição do Modelo


Neste sub-blo o é des rito ada �la que perten e ao modelo. De�ne-se nele o número de

servidores, a apa idade da �la e a des rição de ada lasse que passa por aquela �la.

O número de �las des ritas deve ser igual ao número de �las de laradas na De�nição do

Modelo. Cada �la é representada da maneira que segue.

Des rição de Filas - CQN

queue nome da �la {

server = número de servidores;

apa ity = apa idade da �la;

Des rição de Classes

}

...

Onde:

nome da �la Nome de ada �la que faz parte da rede, o qual foi de�nido em De la-

ração de Classes e Filas. O nome deve ser diferente para ada �la.


número de servidores De�ne o número de servidores para a �la do es opo a que per-

ten e. É de�nido por um número inteiro.

apa idade da �la Tamanho máximo da �la, que é de�nido por um número inteiro.

Para o ál ulo dos índi es de desempenho de rede à forma-produto, o valor

de�nido para apa idade ( apa ity) é ignorado.


Des reve ada lasse perten ente ao modelo que passa por aquela �la. De�ne-se aqui o

tempo de serviço da ada lasse naquela �la e as rotas dos lientes da respe tiva lasse

para as �las seguintes. O nome das lasses men ionadas dentro de ada �la deve ser o

mesmo nome de larado em De laração de Classes e Filas e ada �la pode um máximo de

de larações de lasses dentro do seu es opo. Esse máximo de de larações é o número de

lasses de larado em De�nição do Modelo. O número máximo de rotas (rot) que podem

ser de�nidas equivale ao número de �las de laradas em De�nição do Modelo e o nome

da �la destino deve ser igual ao nome das �las de laradas na De laração de Classes e

Filas, mesmo que a �la a qual o liente irá dirigir-se seja a mesma a que ele perten e.

Des reve-se então ada lasse da seguinte maneira:

Des rição de Classes - CQN

lass nome da lasse {

servi e time = tempo de serviço;

rot nome da �la : probabilidade;

...

}

...

Onde:

nome da lasse Nome de ada lasse no modelo.

tempo de serviço Tempo médio de atendimento para a lasse na �la do es opo a que

perten e. É de�nido por um número real.


probabilidade De�ne a probabilidade de um liente da lasse de larada sair da �la do

atual es opo e ir para outra �la da mesma lasse.

Caso as rotas de uma lasse não passem por uma determinada �la, a des rição daquela

lasse na referida �la deve ser omitida.

3.3.3 Modelo para OQN

Da mesma maneira que a onte ia na gramáti a para modelos CQN, a gramáti a riada

para des rever modelos OQN pode ser também dividida em blo os blo os prin ipais e os

quais por sua vez são divididos em blo os menores. No primeiro blo o é feita a de laração

das lasses e �las que serão posteriormente usadas no modelo. No segundo é feita a

des rição do modelo em si. A sisntaxe exata desta lasse de QN é mostrada a seguir.

De�nição do modelo

De�ne-se pela palavra reservada "oqn", o tipo de QN que será modelado omo sendo

OQN. Após a de�nição do tipo atribui-se para ele um nome qualquer. Em seguida, é

informado o número de lasses e �las do modelo. É apresentada a sintaxe exata para

des rição deste tipo de QN abaixo.

De�nição do modelo - OQN

oqn nome do modelo (número de lasses, número de �las)



Onde:

nome do modelo O nome do modelo é de�nido através de um identi� ador qualquer,

da mesma maneira que nos modelos CQN;

número de lasses Número de lasses que estarão presentes no modelo, o qual deve ser

um número inteiro positivo;


número de �las Número de �las que estarão presentes, deve ser representado por um

número inteiro positivo.


Neste blo o é feita a de laração das lasses e �las que serão utilizadas no modelo. A

de laração de lasses e �las neste blo o é realizada exatamente da mesma maneira que nos

modelos CQN. Para de laração das lasses utiliza-se a palavra reservada " lass" seguida

do nome da lasse. Na de laração de �las utiliza-se da palavra "queue" para de�nir a

�la, a qual é seguida do nome atribuído para a �la. Abaixo segue a sintaxe orreta que

deve ser utilizada.

De laração de Classes e Filas - OQN

de larations {

lass nome da lasse;

queue nome da �la;

...

}

Onde:

nome da lasse Nome da lasse é de�nido através de um identi� ador qualquer e re-

presenta uma lasse diferen iada de lientes;

nome da �la Nome da �la também é de�nido por um identi� ador e de�ne a identi-

� ação para um re urso (�la) do modelo.

A ordem em que as lasses e as �las são de laradas pode ser alterada, por exemplo,

pode-se de larar todas as �las antes das lasses, ou mesmo inter alar as duas. Porém

os nomes, tanto das lasses omo das �las, devem ser diferentes. Tanto para as lasses

omo para as �las, o número de de larações deve ser igual ao número de lasses e �las

de laradas anteriormente na De�nição do modelo.



O modelo é des rito realmente neste blo o. Nele ontém a delimitação para a des rição

da rede e o blo o om a des rição de ada �la do modelo. Segue a sintaxe utilizada neste

blo o.

Des rição do Modelo - OQN

network {


}

Cabe ressalta que ao ontrário das CQN, neste tipo de QN não existe o blo o de

De laração de Populações, visto que nas OQN não existe uma população prede�nida.


Na Des rição de Filas é des rito ada �la perten ente ao modelo. O número de servidores,

a apa idade da �la e a des rição de ada lasse que passa pela �la são des ritos nesse

blo o. O número de �las des ritas deve ser igual ao número de �las de laradas naDe�nição

do Modelo. Cada �la pode ser representada da maneira a seguir.

Des rição de Filas - OQN

queue nome da �la {

server = número de servidores;

apa ity = apa idade da �la;


}

...

Onde:

nome da �la Nome de ada �la que faz parte do modelo, a qual foi de�nida em

De laração de Classes e Filas.


número de servidores De�ne o número de servidores para a �la do es opo ao qual

perten e. É de�nido por um número inteiro positivo.

apa idade da �la Tamanho máximo da �la, que é de�nido por um número inteiro

positivo. No aso do ál ulo dos índi es de desempenho para as redes à

forma-produto, este parâmetro é ignorado.


Este blo o ontém a des rição de ada lasse perten ente aquela �la. Para ada lasse

aão de�nidos o tempo de serviço da lasse naquela �la, a taxa de hegada de lientes do

exterior da lasse na respe tiva �la e também as rotas dos lientes da lasse para as �las

posteriores. A mesma lasse deve ser de larada om o mesmo nome em todas as �las por

onde passa. Cada �la pode ter um máximo de de larações de lasses dentro do seu es opo

e devem obede er as mesmas regras que as CQN, isso é válido também para a de�nição

das rotas.

Des rição de Classes - OQN

lass nome da lasse {

servi e time = tempo de serviço;

arrival rate = taxa de hegada;

rot nome da �la : probabilidade;

...

}

...

Onde:

nome da lasse Nome de ada lasse no modelo. O nome da lasse deve ser previa-

mente de�nido em De laração de Classes e Filas.

tempo de serviço Tempo médio de atendimento ao lientes da lasse na �la do es opo

ao qual perten em. É de�nido por um número real positivo.


taxa de hegada Taxa média de hegada de lientes da respe tiva lasse de fora do

modelo na �la atual.

probabilidade De�ne a probabilidade de um liente da lasse de larada sair da �la do

atual e ir para outra �la na mesma lasse.

Convêm ressaltar que, omo já foi dito anteriomente, a gramáti a apresentada a ima

omo formato de arquivo para a ferramenta MQNA não é um formato padrão, mas sim

um formato que é re onhe ido apenas pela ferramenta MQNA e atende as ne essidades

de resolução de QN à forma-produto e do método de onversão utilizado.

3.4 Gramáti a para PEPS

A gramáti a para o PEPS é um formato para representação do formalismo SAN através

de arquivos texto. A des rição exposta a seguir está de�nida no manual da ferramenta

PEPS [20℄, dá onde podem ser obtidas maiores informações sobre esta gramáti a. Será

apresentada aqui apenas uma visão super� ial sobre a gramáti a para o PEPS, sem entrar

no domínio de ada termo.

Da mesma forma que para as QN, o formato de arquivo re onhe ido por PEPS pode

ser dividido em alguns blo os omo é apresentado a seguir.

3.4.1 De laração de Constantes e Funções

Este blo o ontém as de larações e a ini ialização das onstantes e funções que serão

utilizados pelo modelo SAN. Caso não ne essite de onstantes ou funções este blo o pode

ser omitido. Estas onstantes e funções podem ser utilizadas para representar as taxas e

probabilidades de transição.

De laração de Constantes e Funções - PEPS

De larations {

onstant nome da onstante := valor de onstante;

3.4. GRAMÁTICA PARA PEPS 51

fun tional nome da função := expressão;

...

}

3.4.2 Função de Al ançabilidade

Este blo o ontém a função de al ançabilidade que de�nirá qual é o espaço de estados

atingíveis pelo modelo SAN. A função de al ançabilidade é um função booleana que

retorna true aso o estado possa ser atingido e false aso não possa.

Função de Al ançabilidade - PEPS

rea hability := expressão;

3.4.3 Des rição do Modelo

O blo o da des rição do modelo é o maior omponente do modelo SAN. Ele tem uma es-

trutura hierarquizada onde são des ritos os aut�matos perten entes ao mesmo. É des rito

neste blo o o tipo do modelo e o número de aut�matos de rede.

Des rição do Modelo - PEPS

network nome do modelo (tipo do modelo, número de aut�matos){

Des rição de Aut�matos

}

Des rição de Aut�matos

para ada aut�mato é espe i� ado o nome do aut�mato, o número de repli as dentro

da rede e o número de estados do mesmo. São des ritos também os nodos(estados) do

aut�mato.

Des rição de Aut�matos - PEPS

automaton nome do aut�mato(número de repli as, número de estados) {

Des rição de Nodos

}


...

Des rição de Nodos

A Des rição de Nodos des reve ada nodo(estado) dentro do aut�mato. Deve de�nir-se

prin ipalmente o nome do estado e o número de ar os que partem deste nodo. Des reve-se

também os ar os deste nodo.

Des rição de Nodos - PEPS

node nome do estado (número de ar os {, re ompensa}) {

Des rição de Ar os

}

...

Des rição de Ar os

A Des rição de Ar os de�ne a transição entre os nodos(estados) do aut�mato. De�ne-se o

nodo destino, o número de eventos sin ronizantes asso iados aquele ar o e a taxa transição

lo al.

Des rição de Ar os - PEPS

ar (nome do nodo destino, número de sin ronismo {, taxa lo al }) {

Des rição de Sin ronismos

}

...

Des rição de Sin ronismos

São des ritos neste nível os eventos sin ronizantes rela ionados a ada ar o. De�ne-se o

nome do evento sin ronizante, a taxa de sin ronismo e a probabilidade de rota asso iada.

Des rição de Sin ronismos - PEPS

syn (nome do sin ronismo, taxa de sin ronismo, probabilidade)

3.4. GRAMÁTICA PARA PEPS 53

...

A taxa de sin ronismo e a probabilidade de rota só são espe i� adas no aut�mato

es olhido omo mestre, nos outros é atribuido o valor 1.

3.4.4 Des rição dos Resultados

Neste blo o são de�nidas as funções para obtenção dos índi es de desempenho interes-

santes ao modelo. Estes índi es são des ritos através de um nome e de uma expressão

matemáti a.

Des rição dos Resultados - PEPS

Results {

nome da função := expressão;

...

}

Maiores exemplos de modelagem om as gramáti as a ima apresentadas, bem omo

onversões entre elas são mostradas na PARTE III (Manual do Usuário) deste trabalho.


55

Parte II

Des rição e Implementação da

Ferramenta MQNA

Capítulo 4

A Ferramenta MQNA

O objetivo �nal deste trabalho é a riação de uma ferramenta de software, hamada

MQNA (Markovian Queueing Networks Analyser - Analisador de Redes de Filas de Espera

Markovianas), na qual se apli ou os on eitos até agora estudados sobre Redes de Filas

de Espera (QN), Redes de Aut�matos Esto ásti os (SAN) e métodos de onversão de

modelos QN para modelos SAN.

No de orrer deste apítulo será feita uma des rição mais detalhada da ferramenta

MQNA, assim omo dos requisitos essen iais de interfa e e fun ionalidades que a mesma

deve atender. Serão expostas ainda as plataformas es olhidas para implementação assim

omo as interfa es es olhidas para ada uma destas plataformas.

4.1 Espe i� ação Geral da Ferramenta

MQNA é uma ferramenta de software a adêmi a para análise, resolução e onversão de

modelos des ritos om o formalismo de Redes de Filas de Espera (QN). A ferramenta

possibilita a edição de modelos QN e a obtenção de índi es de desempenho interesantes

aos modelos QN à forma-produto. A onversão de modelos QN para modelos SAN é uma

fun ionalidade adi ional implementada pela ferramenta e o arquivo gerado é exportado

para ferramenta PEPS [20℄. A ferramenta MQNA resolve as duas lasses de QN à forma-

produto estudadas neste trabalho. São elas: Redes de Filas de Espera Fe hadas (CQN) e

58 CAPÍTULO 4. A FERRAMENTA MQNA

Redes de Filas de Espera Abertas (OQN).

4.1.1 Requisitos Gerais

A ferramenta MQNA é apaz de exe utar tanto em plataforma Mi rosoft Windows 9x ou

superior quanto em plataforma Linux

1

, quando ompilada om as ferramentas próprias

da plataforma (g++ para Linux e C++ Builder para Windows).

Por motivos que serão expostos mais adiante neste apítulo, a interfa e da ferramenta

possui duas versões. Para a plataforma Mi rosoft Windows, a interfa e é grá� a e para

plataforma Linux a interfa e é textual.

4.1.2 Formatos de Arquivos

A ferramenta MQNA é apaz de re onhe er e riar arquivos que estejam em onformidade

om a gramáti a para modelos QN des rita na seção 3.3 deste trabalho. MQNA também

exportar arquivos que obedeçam as regras da gramáti a para modelos SAN, expli adas

na seção 3.4, os quais são re onhe idos pela ferramenta PEPS.

4.1.3 Interfa e om o Usuário

Como já men ionado anteriormente, o software tem duas interfa e diferen iadas. Uma

delas grá� a para plataforma Mi rosoft Windows e outra textual para plataforma Linux.

Apesar de interfa es diferen iadas, alguns re ursos são providos pelas duas interfa es:

� Carrega um modelo QN - é possivel arregar um modelo QN de um arquivo texto

que obedeça as regras da gramáti a para modelos QN para as estruturas internas da

ferramenta;

1

Neste trabalho referen ia-se a plataforma Linux omo sendo qualquer plataforma UNIX (Solaris,

AIX, FreeBSD, et )

4.1. ESPECIFICAÇ�O GERAL DA FERRAMENTA 59

� Salva um modelo QN - é possível gerar um arquivo texto de a ordo om a gramáti a

de�nida para modelos QN a partir do dados presentes na ferramenta;

� Salva as taxas de visita - tem-se a possibilidade de re uperar as taxas de visita

al uladas para um modelo QN ;

� Mostra os parâmetros de resolução da matriz - permite a exibição de parâmetros

para a resolução da matriz de probabiliade de rotação, omo número de iterações e

erro máximo a eitável ;

� Mostra os parâmetros do modelo - permite a visualização dos parâmetros do modelo,

tanto das lasses omo das �las, por exemplo, o número de sevidores de uma �la ou

o nome de ada lasse;

� Exibe os índi es de desempenho - o programa possibilita a exibição dos índi es de

desempenho obtidos, tanto os índi es gerais quanto por lasse;

� Sai do programa - En erra o programa.

Espe i� amente para a interfa e grá� a da plataforma Mi rosoft Windows é possível

a riação automâti a de novos modelos QN.

4.1.4 Fun ionalidades do Software

Independente da interfa e ou da plataforma em que o software for utilizado, o mesmo

suporta todas as fun ionalidades abaixo listadas:

� Compila modelos QN - quando da arga de um modelo QN, a ferramenta é apaz

de ompilar um modelo QN des rito segundo a gramáti a anteriormente (seçao 3.3)

apresentada e aponta possíveis erros léxi os e sintáti os do modelo. A ferramenta

des obre também qual lasse de QN (CQN ou OQN) que está sendo arregada;

� Cria arquivos textuais de modelos QN - é possível riar arquivos textuais que obe-

deçam as regras da gramáti a de�nida para modelos QN a partir de um modelo QN

qualquer presente na memória;


� Cal ula as taxas de visita - a partir de uma matriz de probabilidade de rotação é

possível resolver um sistema de equações lineares para des obrir as taxas de visita;

� Altera os parâmetros de resolução - os parâmetros omo número máximo de iterações

e erro máximo a eitável não são �xos e o programa provê métodos para alterá-los;

� Computa os índi es de desempenho - a ferramenta implementa métodos para o ál-

ulo dos índi es de desempenho de a ordo om a lasse de QN presente na mémoria.

O método que será utilizado no ál ulo é des oberto pela ferramenta de a ordo om

o tipo de modelo QN (CQN ou OQN) arregado na memória;

� Modi� a os parâmetros do modelo - o usuário pode modi� ar os parâmetros de um

modelo QN presente na memória;

� Re upera os índi es de desempenho - implementou-se maneiras do usuário re uperar

e exibir os índi es de desempenho anteriormente al ulados;

� Converte um modelo QN para SAN - é possível onverter o modelo QN que está

em memória para um arquivo textual om um modelo SAN equivalente om ou sem

restrição de apa idade;

Todas as fun ionalidades listadas a ima que a ferramenta provê, são suportadas para

qualquer tipo de modelo QN, seja ele aberto (OQN) ou fe hado (CQN), mono ou multi-

lasse. Toma-se por ex essão o método de onversão, onde a opção sem restrição à a-

pa idade só pode ser implementadas nas CQN.

4.1.5 Plataformas Es olhidas

O objetivo de riar uma ferramenta de software que exe ute em mais de uma plataforma

usando o mesmo ódigo fonte é prin ipalmente o de não limitar o uso da mesma a um

grupo de usuário de uma plataforma espe í� a. As duas plataformas es olhidas para

implementação da ferramenta foram, toda a família Mi rosoft Windows

2

e Linux.

2

No de orrer deste será utilizado a notação Windows omo sendo qualquer plataforma Mi rosoft

Windows (95, 98, Me, NT e 2000)

4.2. DESCRIÇ�O FUNCIONAL DA FERRAMENTA 61

Optou-se pela plataforma Windows por ela ter um grande número de usuários e se

ara terizar por uma boa amigabilidade. Já, a opção da plataforma Linux foi fortemente

in�uen iada por ter o arquivo exportado pela onversão de modelos QN para SAN es rito

onforme a gramáti a re onhe ida pela ferramenta PEPS, a qual roda somente sobre

plataforma Linux, fa ilitando assim o uso em onjunto das duas ferramentas.

4.2 Des rição Fun ional da Ferramenta

Esta seção traz um onjunto de passos e instruções sobre omo pro eder no uso normal

da ferramenta MQNA quando da avaliação de algum modelo.

O pro esso para avaliação de desempenho de um sistema qualquer normalmente segue

uma seqüên ia bási a de passos. Os primeiros passos para a avaliação de um modelo são

a modelagem do sistema através da gramáti a de�nida para ferramenta e em seguida a

ompilação do modelo por MQNA.

Com o modelo presente na memória vários aminhos podem ser seguidos, porém os

mais omuns são a omputação dos índi es de desempenho do modelo ou a onversão

deste modelo QN para um modelo SAN.

Menos omum, porém também utilizada, é a alteração de algum parâmetro do modelo

arregado na memória e novamente a omputação dos índi es de desempenho para ob-

servar as mudanças e adequar o modelo. Após este passo normalmente o modelo é salvo

para que �quem registradas as alterações feitas.

A seguir é mostrado omo utilizar as fun ionalidades implementadas na ferramenta

MQNA na avaliação de um modelo seguindo os passos des ritos a ima.


4.2.1 A Criação de Modelos

A riação de um modelo para a ferramenta MQNA é basi amente a edição de um arquivo

textual, que se enquadre nas regras da gramáti a expli ada na seção 3.3, por qualquer

editor de texto.

Entretanto, para a versão Windows há ainda uma segunda forma de riação de modelo.

Essa versão implementa um assistente que oleta e ria um modelo padrão para ser editado

posteriormente.

Para utilizar esse assistente o usuário deve li ar no menu na opção .

Em seguida o usuário deve informar os dados bási os do modelo. Cada tela pede uma

ara terísti a do modelo que será riado.

O usuário pode navegar por essa telas om o uso dos botões , para

passar a tela seguinte, e , para retorna a tela anterior.

Após o término deste pro esso o novo modelo estará arregado na memória e o usuário

poderá alterar os parâmetros do modelo.

4.2.2 Compilando um Modelo

Com o modelo já riado o passo seguinte é ompilar o modelo e arregá-lo na memória.

O pro esso de ompilação é bastante simples nas duas versões da ferramenta. Para

a versão Linux essa função é ativada pela opção 1 do menu prin ipal. Após digitar o

número 1 e ativar essa opção om a te la Enter

3

. Apare erá na tela a opção es olhida e

3

A te la Enter sempre é utilizada para ativar a opção es olhida ou algum parâmetro digitado. Porém

na seqüên ia deste trabalho será men ionado somente a opção ou parâmetro que deve ser digitado,

omitindo a ne essidade da te la Enter.


a mensagem "Nome do arquivo QN:", onde deverá ser informado o nome do arquivo que

ontém o modelo.

Para a versão Windows deve-se abrir o menu e li ar na opção .

Surgirá uma janela para a es olha de arquivo. O arquivo ontendo o modelo QN deve ser

sele ionado e em seguida li ar na opção .

Ao �m dos passos a ima, aso não haja erro no modelo, os quais serão a usados pela

ferramenta, o modelo estará ompilado e arregada na memória.

4.2.3 Obtendo os Índi es de Desempenho

Com o modelo presente na memória a obtenção dos índi es de desempenho é bastante

simples porém as vezes esse pro esso pode ser um pou o longo. O tempo para omputar

o modelo depende do número de lasses e número de �las presentes no modelo. Nos

modelos CQN outro fator que a arreta um aumento no tempo de omputação dos índi es

é a população total de ada lasse.

Na versão Linux a omputação dos índi es de desempenho é ativada pela opção 4 no

menu prin ipal. Após a ativação desta opção, será mostrada na tela uma mensagem da

opção es olhida e a mensagem "Salvar resultado omo:", onde deverá ser informado

o nome do arquivo onde os resultados serão gravados. Ao �m do pro esso de omputação

dos índi es de desempenho, os índi es gerais do modelo serão exibidos na tela.

Na versão Windows, a maneira mais fá il de omputar os índi es de desempenho

quando o modelo já está na memória é li ar no botão . Com isso

os índi es serão omputados e mostrados na parte inferior da tela. Caso seja ne essário

salvar esse índi es em um arquivo, deve-se sele ionar o item no menu

. Após es olhido o nome do arquivo na janela exibida li a-se em .


4.2.4 Convertendo um Modelo QN para SAN

Os passos para onversão de modelo QN para um modelo SAN são bastante pare idos

om os passos para omputação de índi es de desempenho.

Para a versão Linux deve-se es olher a opção 7 no menu prin ipal para fazer a onversão

do modelo. Em seguida é ne essário informar o nome do arquivo onde será gravado o

modelo SAN. A mensagem que apare erá na tela para informação do nome do arquivo é

"Salvar modelo SAN omo:".

Para os modelos CQN uma segunda informações ainda é ne essária. Essa informação

diz respeito a onverter um modelo QN para SAN om ou sem restrição a apa idade. A

mensagem que pede essa informação é "Salvar modelo om restrição de apa idade

(s/n)?".

Para a versão Windows o botão faz essa função. Após li ado

surge uma janela para a es olha do nome do arquivo, quando o nome tiver sido informar

li a-se o botão .

Da mesma maneira que na versão Linux, para modelos CQN é soli itado a informação

sobre restrição de apa idade. Essa informação é oletada através de uma janela os botões

e .

4.2.5 Alterando Parâmetros do Modelo

A alteração dos parâmetros do modelo não é tão omum quanto os demais passos expli-

ados a ima porém algumas vezes é ne essário para a adequação do modelo.

Existe duas maneiras de fazer as alterações. A primeira seria a mudança dos valores

diretamente no arquivo textual, o qual pre isaria ser novamente ompilado seguindo os

passos anteriormente des ritos. A segunda maneira é alterar ada parâmetro individual-


mente através da ferramenta. Essa segunda maneira é parti ularmente mais interessante

pois não ne essita a re ompilação do modelo.

Na versão Linux essas alterações são feitas ativando a opção 5 do menu prin ipal. Essa

opção ativa um segundo menu onde é pedido que tipo de parâmetro que o usuário gostaria

de alterar. Na opção 1 deste menu apare erá para o usuário, os parâmetros de lasse para

a alteração pelo usuário. Quando for feita alguma alteração nos parâmetros de lasse o

usuário deve informar qual a lasse que deseja alterar, as opções disponíveis apare erão

entre parênteses. Após essa es olha é mostrado na tela o valor atual do parâmetro e

pedido um novo valor. Na opção 2 do menu pode-se alterar os parâmetros das �las. Os

passos a serem seguidos são os mesmos para alteração dos parâmetros de lasse, porém

é pedido ao usuário qual a �la que ele deseja alterar, novamente as opções disponíveis

apare erão entre parênteses.

Na versão Windows essas alterações são bem menos laboriosas. Para alteração dos

parâmetros de uma �la basta modi� ar os mesmos na tabela presente no anto superior

direito da tela prin ipal. Para alterar os parâmetros de uma lasse deve-se li ar no botão

, o qual ativará uma segunda janela onde são mostrados

os parâmetros de ada lasse. Para efetivar a alteração deve-se sele ionar o parâmetro

desejado e digitar o novo valor.

4.2.6 Salvando um Modelo

Com o modelo já presente na memória, os passos para salvá-lo são bastante simples.

Para a versão Linux, no menu ativado pela opção 2 do menu prin ipal é mostrado

ao usuário as duas opções para o salvamento do modelo. A primeira opção(1) salva o

modelo num arquivo om o mesmo nome do arquivo de onde foi arregado. Já a opção

2, pergunta ao usuário qual o nome do arquivo onde ele gostaria de salvar o modelo. O

nome deve ser informado após a mensagem "Salvar o modelo omo:".


Na versão Windows, para salvar o modelo no mesmo arquivo de onde foi arregado

deve sele ionar-se o item no menu . Para salvar o modelo om outro

nome deve sele ionar o item no menu . Após sele ionado o item,

surgirá uma janela onde é informado o nome do arquivo onde será salvo o modelo. Deve-se

li ar então no botão para que o modelo seja efetivamente salvo.

Um roteiro mais ompleto e exempli� ado sobre a utilização da ferramenta MQNA é

dado na PARTE III (Manual do Usuário) deste trabalho

Capítulo 5

Implementação da Ferramenta

Este apítulo ontém a do umentação sobre a implementação da ferramenta MQNA. Isso

in lui desde as estruturas de lasses e métodos riados omo também as interfa es tanto

para versão Windows quanto para versão Linux.

A seguir, primeiramente é expli ado qual a linguagem de programação es olhida para

implementação da ferramenta assim omo os motivos que levaram a essa es olha (seção

5.1). Adi ionalmente, é dada uma explanação rápida sobre alguns software também uti-

lizados no desenvolvimento da ferramenta MQNA. Após essa expli ação ini ial sobre a

es olha da linguagem e ferramentas utilizadas, é des rito então omo foi estruturada a

ferramenta, as lasses riadas, omo seus métodos e atributos (seção 5.2). Finalmente a

seção 5.3 apresenta detalhes da implementação das interfa es de ada versão (Windows e

Linux).

5.1 Linguagem de Programação Es olhida

Devido a es olha de riar um ódigo que pudesse ser ompilado e exe utado tanto em

Windows omo em Linux, optou-se pelo uso da linguagem de programação C++. A

es olha desta linguagem para desenvolver a ferramenta MQNA levou alguns fatores em

onsideração, os quais são ne essários para que a ferramenta seja bastante portável. Talvez

o prin ipal destes fatores seja a não ne essidade de instalação prévia de nenhum pa ote

68 CAPÍTULO 5. IMPLEMENTAÇ�O DA FERRAMENTA

ou bibliote a de software além do ompilador C++ (C++ Builder no aso da versão

Windows e g++ para a versão Linux). Ainda assim no aso de utilização da ferramenta

já ompilada, nem mesmo a presença dos ompiladores é ne essária.

Desenvolvendo um pou o mais as razões que justi� am a es olha desta linguagem de

programação alguns fatores avaliados são expli ados abaixo:

� Existên ia de ferramentas adequadas para riação do ódigo �nal nas duas platafor-

mas - Devido a ne essidade de ompilar o ódigo fonte para ada plataforma, levou-

se em onta a existên ia das ferramentas ne essárias nas duas plataformas. Além

disso, as ferramentas es olhidas para ompilação presisavam suportar a interfa e

grá� a no aso da versão Windows e textual para a versão Linux ;

� Rapidez de exe ução do ódigo gerado - Tendo em vista que muitos modelos riados

pelos usuários podem fa ilmente ter grandes dimensões e o upar bastante mémoria

e pro essamento da máquina, é ne essário que haja o mínimo de programas rodando

para que o modelo seja resolvido no menor espaço de tempo possível. A rapidez do

ódigo �nal, foi na verdade, um dos prin ipais motivos da es olha desta linguagem

de programação;

� Independên ia de outros software para exe ução - O primeiro aspe to que justi� a

esta ne essidade é a possibilidade de exe utar a ferramenta em qualquer plataforma

sem que haja nenhum outro software pré-instalado. O segundo aspe to, que vem em

onseqüên ia do primeiro, é a maior disponibilidade de re ursos da máquima quando

da resolução de grandes modelos, isso por não ter a ne essidade de outros software

rodando ao mesmo tempo e disputando pro essador e memória;

� Existên ia de ferramentas auxiliares - Devido a ne essidade da riação de uma

gramáti a para representação textual de modelos QN e onseqüentemente de re o-

nhe imento de um modelo des rito neste padrão, fez-se ne essária a utilização de um

software para re onhe imento léxi o e sintáti o. Neste aso as ferramentas utilizadas

foram "�ex" e "bison" para Linux e "p lex" para Windows. Essas ferramentas são

omentadas na seção seguinte.

5.1. LINGUAGEM DE PROGRAMAÇ�O ESCOLHIDA 69

5.1.1 Ferramentas Utilizadas

No de orrer da implementação da ferramenta MQNA foram utilizadas algumas ferramen-

tas para a riação da gramáti a e ompilação do ódigo fonte.

As ferramentas utilizadas para ompilação foram:

� Borland C++ Builder 5.0 - Esta ferramenta foi utilizada no desenvolvimento de

interfa e grá� a e a ompilação do ódigo fonte na versão Windows. Esta ferramenta

foi es olhida prin ipalmente pelas fa ilidades que ofere e para o desenvolvimento

grá� o ne essário a esta versão;

� g++ - Ferramenta utilizada para ompilação dos ódigos fontes para a versão Linux

por ser padrão em grande parte das plataformas Linux.

As ferramentas utilizadas para a riação da gramáti a para modelos QN foram:

� �ex - Para o re onhe imento léxi o dos tokens da gramáti a foi utlizada a ferramenta

�ex para a versão Linux ;

� p lex - Devido ao ódigo gerado pela ferramenta �ex na versão Linux in luir bibli-

ote as que não existem para Windows, a ferramenta p lex foi então utilizada para

o re onhe imento léxi o. É interessante men ionar que o ódigo de entrada para as

duas ferramentas é exatamente igual, apenas o ódigo gerado por elas é que difere;

� bison - A ferramenta bison foi utilizada neste trabalho para fazer o re onhe imento

sintáti o da gramáti a riada para modelos QN. Ao ontrário do ódigo gerado pelas

ferramentas de re onhe imento léxi o, o ódigo gerado pela ferramenta bison pode

ser ompilado nas duas versões sem nenhuma modi� ação.

Convêm ressaltar que todas as ferramentas utilizadas para re onhe imento da gramáti-

a geram ódigo C++, o qual é ompilado juntamente om o resto dos ódigos fontes do

programa, os quais são expostos nas seções seguintes.


5.2 De�nição das Classes e Métodos

Devido as diferenças entre ada tipo de modelo QN a implementação da ferramenta MQ-

NA foi organizada em várias lasses. Foi riada então uma lasse "pai" hamada Qn

a qual serve de base para duas espe ializações, esta lasse ontém tudo o que é omum

aos dois tipos de modelos QN suportados pela ferramenta. Uma destas espe ializações

tem a função de representar os modelos CQN enquanto a outra representa os modelos

OQN. Criou-se ainda uma quarta lasse que é utlizada para representar as matrizes de

probabilidades de rotação de lientes. Essa quarta lasse foi riada devido a matriz de

probabilidade ter suas ara terísti as próprias, omo atributos e métodos, que suas só

são interessantes a ela, não sendo onveniente implementá-los juntos om alguma outra

lasse.

Esta lasseMatriz é então instan iada na lasse Qn omo um vetor, onde ada posição

representa a matriz de probabilidade de rotação de uma lasse de lientes do modelo.

Na Figura 5.1 pode ser visto omo estas lasses foram organizadas.

Classe Classe

Classe Classe

Qn

CQn OQn

Matriz

instan iação

espe ializaçãoespe ialização

Figura 5.1: Organização das lasses

Nas seções a seguir são apresentados os atributos e métodos mais importantes para

ada uma destas lasses individualmente.

5.2. DEFINIÇ�O DAS CLASSES E MÉTODOS 71

5.2.1 Classe Matriz

A lasse Matriz tem a função de implementar a matriz de probabilidade de rotação dos

lientes de uma lasse. Essa implementação abrange desde o armazenamento da matriz

de probabilidade de rotação em si até um método para resolução de sistemas lineares.

Esse método de resolução de sistemas lineares é ne essário para a resolução de matriz

de probabilidade e obtenção da taxa de visita de uma lasse (�

r

i

).

Optou-se por armazenar a matriz em um formato esparso

1

, visto que, por este tipo de

sistema ter uma grande quantidade de elementos nulos, a matriz armazenada no formato

esparso o upa menos memória.

O método es olhido para a resolução de sistemas lineares foi o método iterativo de

Gauss-Seidel visto na Equação 2.1, por ele se adequar melhor as ne essidade da ferra-

menta.

A seguir são expostos os atributos e prin ipais métodos desta lasse.

Atributos

Devido a simpli idade do armazenamento de uma matriz no formato esparso pou os atri-

butos foram ne essários a essa lasse. Os pou os atributos riados foram então:

d Dimensão da matriz;

nz Número de elementos diferentes de zero;

ol Vetor ontendo as posições de onde omeça e termina ada oluna nos

dois outros vetores (lin e Nz);

lin Vetor ontendo a linha de ada elemento não nulos na matriz plana;

1

No formato esparso armazena-se em três vetores unidimensionais apenas os valores diferentes de zero

de um matriz plana. No primeiro vetor guarda-se os valores não-nulos da matriz. No segundo é guardada

a linha em que ada valor estava e no ter eiro armazena-se em qual posição do vetores anterior omeça

e termina ada oluna.


Nz Vetor ontendo os elementos diferentes de zero da matriz.

Métodos

O método mais importante desta lasse é sem duvida o método para resolução de sistemas

lineares. Porém outros métodos auxiliares são também importantes por olo arem a

matriz na forma ne essária à ferramenta.

Abaixo são apresentados alguns métodos desta lasse.

Veri� aD Este método veri� a os elementos da diagonal prin ipal da matriz, os quais

devem ser sempre um número negativo.

Preen heD Este método é utilizado quando a diagonal prin ipal não foi de�nida da

forma orreta. Este método preen he então a diagonal prin ipal om o valor negativo

orrespondente ao somatório das demais olunas daquela linha.

Read Através deste método é passada uma matriz no formato esparso para ser ar-

mazenada na lasse.

Write Ao ontrário do método Read, este método es reve a matriz esparsa armazenada

em variáveis passadas para o método.

Gauss_Seidel Neste método é implementado o algoritmo de Gauss-Seidel para resolu-

ção de sistemas lineares sobre uma matriz esparsa. Com a resolução desta matriz obtêm-se

as taxas da visita �

r

i

de uma lasse de lientes.

5.2.2 Classe Qn

A lasse Qn é uma lasse abstrata riada para representar as ara terísti as omuns

aos dois tipos de modelos QN (CQN e OQN), os quais são espe ializados em outras


lasses (CQn e OQn). Esta lasse implementa a maioria dos atribuitos e métodos que são

indiferentes ao tipo do modelo representado. Por esse motivo a maior parte dos métodos

por ela implementados dizem respeito a tro a ou a bus a de valores dos atributos da

lasse.

Atributos


R Número de lasses diferentes na rede;

Ci Vetor om o número de servidores de ada �la;

Ki Vetor om o número máximo de lientes de ada �la;

Sri Matriz om tempo médio de serviço dos lientes de ada lasse para

ada �la;

Vri Matriz om as taxas de visita de ada lasse para ada �la

Prij Vetor om as matriz de probabilidade de rotação de ada lasse;

di Vetor om o �uxo médio geral de ada �la;

ni Vetor om a população média geral de ada �la;

ui Vetor om o índi e de utilização geral de ada �la;

wi Vetor om o tempo médio geral de resposta de ada �la;

dri Matriz om o �uxo médio de ada �la para ada lasse;

nri Matriz om a população média de ada �la para ada lasse;

uri Matriz om o índi e de utilização de ada �la para ada lasse;

wri Matriz om o tempo médio de resposta de ada �la para ada lasse;


modelo Nome do modelo;

Filas Vetor om o nome de ada �la;

Classes Vetor om o nome de ada lasse.

Métodos

Pela maioria dos métodos implementados nesta lasse dizer respeito a tro a ou a bus a

de valores dos atributos da lasse, pou os métodos se desta am.

Mui Este é o úni o método que implementa uma função rela ionada ao formalismo de

QN nesta lasse. O método al ula a taxa média de atendimento de uma �la para uma

determinada lasse, de a ordo om a população presente na �la.

5.2.3 Classe CQn

As ara terísti as ex lusivas dos modelos CQN são implementadas nesta lasse. Apesar

de pou os atributos, além dos já implementados na lasse Qn da qual esta lasse é uma

espe ialização, há vários métodos interessantes nesta lasse. A maioria deles implementa

algoritmos para resolução ou onversão de modelo CQN.

Atributos

Nr Vetor om o número de lientes de ada lasse;

Wri Vetor tri-dimensional om o tempo de resposta para ada população

possível da rede;

Nri Vetor tri-dimen ional om a população média de ada �la para ada

lasse e para ada população possível da rede;

Do Vetor bi-dimen ional om o �uxo padrão de ada lasse para ada po-

pulação possível da rede;


pMarg Vetor tri-dimen ional om a probabilidade marginal de a ordo om o

número de servidores na �la para ada população possível da rede.

Métodos

Todos os métodos que dizem respeito a CQN são implementados nas lasses. Porém só

serão apresentados abaixo os métodos prin ipais, visto que, devido a omplexidade de

alguns algoritmos implementados, vários métodos auxiliares foram riados para organizar

melhor o ódigo e não ne essitam uma maior expli ação além da do umentação existente

no próprio ódigo fonte.

Os prin ipais métodos desta lasse são:

Cal ulaVri Este método hama o método de Gauss_Seidel implementado na lasse

Matriz, porém primeiramente ele opia a matriz de probabilidade de rotação para uma

estrutura auxiliar e modi� a a mesma para que esta �que de a ordo om as ne essidades

da ferramenta. Há a ne essidade de passar a matriz para uma estrutura auxiliar pois

quando se for salvar o modelo é ne essário ter a matriz original.

Read Neste método são implementadas as funções para o re onhe imento de um modelo

CQN de um arquivo textual. Os valores ne essários para o preen himento dos dados da

lasse são lidos de um arquivo auxiliar riado a partir da des rição textual do modelo

pelos métodos hamados junto om o re onhe imento léxi o e sintáti o.

Este arquivo auxiliar ontém um formato interno de dados usados pela ferramenta.

Este formato é o seguinte:

Formato interno omentado - CQN

número de lasses

número de �las

vetor om a população de ada lasse


vetor om o número de servidores de ada �la

vetor om a apa idade de ada �la

matriz om o tempo de serviço da �la em ada lasse

matrizes esparsas

nomes das lasses

nomes das �las

Write Este método ria um arquivo textual ontendo a des rição de um modelo CQN

baseado nos dados presentes nos atributos da lasse CQn.

Cal uladnuw O ál ulo dos índi es de desempenho para modelo CQN é feito por este

método. Devido a omplexidade do algoritmo MVA implementado aqui, foram riados

vários métodos auxiliares, os quais al ulam índi es intermediários ne essários ao método.

Destes métodos auxiliares ita-se alguns:

Cal ulaDo Cal ula o �uxo padrão de uma lasse;

Cal ulasnri Cal ula o somatório da população média de ada lasse;

Cal ulaProbMarg Cal ula a probabilidade marginal de uma �la.

Estes métodos auxiliares são protegidos e só podem ser hamados por outros métodos

da lasse.

Converte A função de onversão de modelos CQN para modelos SAN é feita por este

método. Novamente por ser um ódigo bastante extenso, foram riados outros métodos

auxiliares. Basi amente um destes métodos onverte a parte de de larações (ConvDe-

�nes), outro a parte da rede em si (ConvNetwork) e por último a parte dos resultados

(ConvResults).


5.2.4 Classe OQn

A lasse OQn implementa alguns atributos e métodos aos herdados da lasse Qn para

poder representar modelos do tipo OQN. Da mesma maneira que na lasse CQn, pou os

atributos são adi ionados aos da lasse Qn. Porém todos os métodos de ál ulo e onversão

de um modelo OQN para SAN são implementados na lasse.

Abaixo são apresentados os atributos e métodos implementados por esta lasse.

Atributos

Lri Matriz om a taxa de hegada de lientes de ada lasse para ada �la

Métodos

Os métodos mais importantes desta lasse são os mesmos da lasse CQn, entretanto os

algoritmos implementados têm algumas diferenças.

Cal ulaVri Um pou o diferente do método da lasse CQn, este método além de hamar

o método de Gauss_Seidel implementado na lasse Matriz, ele modi� a a matriz de

rotação para in orporar uma dimensão a mais. Há a ne essidade de introduzir mais uma

dimensão pois as taxas de hegadas do exterior do modelo são onsideradas omo uma �la

do modelo quando do ál ulo das taxas de visita, porém a mesma é ignorada nos demais

ál ulos para obtenção dos índi es de desempenho.

Read Da mesma maneira que na lasse CQn, este método implementada as funções

para o re onhe imento de um modelo OQN de um arquivo textual. Entretanto os valores

ne essários para o preen himento dos dados da lasse, lidos do arquivo auxiliar, diferem

um pou o do formato interno estabele ido para os modelos CQN.

O formato para modelos OQN é então:


Formato interno - OQN

número de lasses

número de �las

vetor om o número de servidores de ada �la

vetor om a apa idade de ada �la

matriz om o tempo de serviço da �la em ada lasse

matriz om a taxa de hegada em ada �la para ada lasse

matrizes esparsas

nomes das lasses

nomes das �las

Write Este método ria um arquivo textual ontendo a des rição de um modelo OQN

baseado nos dados presentes nos atributos da lasse OQn.

Cal uladnuw É implementado neste método o algoritmo para o ál ulo dos índi es de

desempenho para modelo OQN. O algoritmo implementado nese método é o algoritmo

de BCMP exposto anteriormente. Diferentemente do algoritmo para resolução de modelo

CQN, este é bastante simples e não houve a ne essidade de implementação de outros

métodos auxiliares.

Converte Este método faz a onversão de modelo OQN para modelo SAN. Como na

lasse CQn, foram riados alguns métodos auxiliares, entretanto há algumas diferenças na

implementação de ada método. Mas, basi amente um destes métodos onverte a parte

de de larações (ConvDe�nes), outro método a parte da rede em si (ConvNetwork) e por

último a parte dos resultados (ConvResults) é onvertida.

5.3 De�nição das Interfa es

Duas interfa es diferen iadas foram riadas para a ferramenta MQNA. A ne essidade de

duas interfa es se deve a prospota da ferramenta de rodar tanto em plataforma Windows

5.3. DEFINIÇ�O DAS INTERFACES 79

quanto em Linux, sendo que a interfa e para Windows é grá� a e para Linux a interfa e

é textual.

Serão apresentadas a seguir as interfa es riadas para ada plataforma. Primeiramente

serão expostas as interfa es para a plataforma Windows e em seguida as interfa es para

a plataforma Linux.

5.3.1 Interfa e Windows

A interfa e grá� a riada para a versão Windows onta basi amente om oito telas. Estas

telas são mostradas a seguir juntamente om a função que desempenham.

A tela mostrada na Figura 5.2 é a tela prin ipal da versão Windows, através dela é

possível abrir, salvar e onverter um modelo ou os resultados al ulados. Nesta tela são

mostrados, o tipo de modelo que está arregado, os dados referentes as �las e na parte

inferior os resultados gerais do modelo.

Figura 5.2: Tela prin ipal da versão Windows

Na tela mostrada na Figura 5.3 é exibido os dados referentes a ada lasse dos modelos

CQN. Os resultados obtidos para ada lasse são mostrados na parte inferior desta tela.


Figura 5.3: Dados das lasses para modelos CQN

A Figura 5.4 mostra tela om a mesma função da tela representada pela Figura 5.3,

porém exibe os dados e resultados dos modelos OQN.

Figura 5.4: Dados das lasses para modelos OQN


A seqüên ia de telas a seguir, ini iada na Figura 5.5 e �nalizada na Figura 5.8, são

utilizadas quando da riação automâti a de um novo modelo. Estas telas tem a função

de auxiliar o usuário na de�nição dos atributos bási os de um modelo QN qualquer.

A primeira tela, mostrada na Figura 5.5, é utilizada para de�nir o nome do modelo.

Figura 5.5: Nome do novo modelo

Na segunda tela é es olhido o tipo do modelo.

Figura 5.6: Tipo do novo modelo

A ter eira tela, Figura 5.7, é onde informa-se o número de lasse que terá o modelo.


Figura 5.7: Número de lasses do novo modelo

Na última tela desta seqüên ia, Figura 5.8, deve ser informado o número de �las que

terá o modelo.

Figura 5.8: Número de �las do novo modelo

A tela seguinte, mostrada na Figura 5.9, é a tela de ajuda e exemplos da versão

Windows. Nesta tela é arregado um arquivo texto de a ordo om a ajuda hamada.

Convêm men ionar que algumas telas da ferramenta foram omitidas desta expli ação

por serem padrão do Windows e geradas automati amente, por exemplo, a tela de diálogo

para abrir um arquivo.


Figura 5.9: Tela de ajuda

5.3.2 Interfa e Linux

Apesar de mais simples que a interfa e da versão Windows a interfa e Linux têm as mesma

fun ionalidades.

Visivelmente inspirada na interfa e da ferramenta PEPS, a interfa e textual da ferra-

menta MQNA bus a trazer o máximo de informações possíveis sobre as operações feitas

sem que atrapalhe o usuário. Para isso foram riados menus de opções que são re-exibidos

após ada operação, � ando as mensagens geradas pela ferramenta registradas a ima dess-

es menus.

A seguir são mostrados os menus disponíveis na versão textual e as fun ionalidades de

ada um deles.

No menu prin ipal, Figura 5.10, tem-se a possibilidade de es olha das várias funções

implementadas na ferramenta. Dentre as funções ita-se:

1 arregar um modelo;

2 salvar um modelo;

3 al ular taxas de visita;

4 al ular índi es de desempenho;

5 alterar parâmetros do modelo;


6 exibir resultados;

7 onverter modelo QN para SAN;

8 informações sobre a ferramenta;

0 en erra o programa.

Figura 5.10: Menu prin ipal

A Figura 5.11 mostra o menu utilizado para salvar um modelo QN presente na

memória, há nele a possibilidade de salvar o modelo om o mesmo nome que foi ar-

regado ou om um nome diferente.

Figura 5.11: Opção para salvar um modelo

O menu mostrado na Figura 5.12 é ativado pela opção três do menu prin ipal e nele

é possível resolver as matrizes de probabilidade de rotação e al ular as taxas de visita.

Há ainda opções para alterar o número máximo de iterações e o erro máximo a eitável.

O menu ativado pela opção in o do menu prin ipal tem a função de alterar os parâ-

metros de um modelo QN.


Figura 5.12: Opção de ál ulo das taxas de visita

Este menu se subdivide em dois outros. Um para modi� ar os parâmetros rela ionados

as lasses e outro para modi� ar os parâmetros de ada �la do modelo.

Convêm ressaltar que as opções exibidas nos menus das Figuras 5.14 e 5.15 são altera-

dos onforme o tipo de modelo arregado na memória. Um exemplo disto é a opção três

do menu da Figura 5.14, a qual só apare e disponível ao usuário quando há um modelo

CQN na memória.

Estes três menus são mostrados nas Figuras 5.13, 5.14 e 5.15 a seguir.

Figura 5.13: Modi� ar parâmetros do modelo

Figura 5.14: Modi� ar parâmetros das lasses

Figura 5.15: Modi� ar parâmetros das �las


No menu da Figura 5.16 o usuário tem a opção de exibir os índi es de desempenho

al ulados. Pode-se optar pela exibição dos índi es gerais, de uma lasse espe í� a ou de

todas as lasses do modelo.

Figura 5.16: Exibir índi es de desempenho

O último menu desta interfa e é o menu de informações da ferramenta, nele podem

ser obtidas informações sobre ada tipo de modelo QN, sobre o método de onversão e

sobre a ferramenta em si.

Figura 5.17: Menu de ajuda

Como já havia sido men ionado anteriormente, o relato da implementação de ferra-

menta MQNA feito aqui, não abrange todos os detalhes da implementação, apenas os

mais importantes. As fun ionalidades mais simples, assim omo mensagens informativas

geradas pela ferramentas podem ser vistas diretamente no ódigo fontes.

87

Parte III

Manual do Usuário

Capítulo 6

Guia Rápido de Ini iação

Esse Guia Rápido de Ini iação é desenvolvido para ajudar o usuário a aprender omo

usar a ferramenta MQNA.

O guia está organizado em seções que ensinam as fun ionalidades mais omumente

utilizadas. A Seção 6.1 expli a omo riar um modelo para MQNA e ompilá-lo. A Seção

6.2 mostra omo salvar o modelo da memória em um arquivo. A Seção 6.3 ensina omo

fazer para resolver o modelo ompilado e salvar os resultados. A Seção 6.4 mostra os

passos ne essários para onverter um modelo QN para um modelo SAN.

Devido as duas interfa es da ferramenta, ada seção apresenta primeiro os passos

ne essários na versão Linux e em seguida os passos para a versão Windows. Salvo quando

os passos independem da interfa e utilizada.

Esse guia de ini iação não traz todas as poten ialidades da ferramenta MQNA. Mas

provê um onhe imento bási o para que o usuário possa explorar mais profundamente as

fun ionalidades implementadas no software.

90 CAPÍTULO 6. GUIA RÁPIDO DE INICIAÇ�O

6.1 Como Criar e Compilar um Modelo QN

A riação de um modelo QN para a ferramenta MQNA pode ser feita om qualquer editor

de texto e onsiste em um arquivo textual ontendo a des rição de um sistema de a ordo

om a gramáti a de�nida para a ferramenta.

Um exemplo bastante simples de uma CQN mono- lasse om três �las pode ser visto

na Figura 6.1.

1

3

2

�2

M = 3

R = 1

N = 10

C

1

= 1

C

2

= 1

C

3

= 1

S

1

1

= 2

S

1

2

= 1

S

1

3

= 1

�1

K

1

= 3

K

2

= 2

K

3

= 5

P

1

1;3

= �2

P

1

1;2

= �1

Figura 6.1: Figura do exemplo1.mqn des rito a seguinte

A Figura 6.1 é des rita textualmente da seguinte maneira.

exemplo1.mqn - CQN mono- lasse

qn exemplo1(1,3)

de larations{

lass 1;

queue q1;

queue q2;

queue q3;

}

network{

population lass 1 = 10;

queue q1 {

servers = 1;

apa ity = 3;

lass 1 {

servi e time = 2;

rot q2: 0.2;

rot q3: 0.8;

}

}

6.2. COMO SALVAR UM MODELO 91

queue q2 {

servers = 1;

apa ity = 2;

lass 1 {

servi e time = 1;

rot q1: 1;

}

}

queue q3 {

servers = 1;

apa ity = 5;

lass 1 {

servi e time = 1;

rot q1: 1;

}

}

}

Vamos onsiderar que o exemplo dado a ima esteja salvo em um arquivo hamado

"exemplo1.mqn". Assim os passos a seguir podem ser melhor exempli� ados.

Linux No menu prin ipal deve-se sele ionar a opção 1 (Compilar um modelo QN). Após

a mensagem "Nome do arquivo QN:" informar o nome do arquivo. Neste aso o arquivo

utilizado é "exemplo1.mqn". Ao �nalizar esses passos o modelo já estará na memória.

Windows No menu sele ionar a opção . Na janela que surgiu sele-

ionar o nome do arquivo ontendo o modelo. Após a seleção li ar no botão

no anto inferior direito para que o modelo seja ompilado.

O modelo somente será ompilado aso não haja problemas na des rição do mesmo.

De modo ontrário a ferramenta avisará do erro en ontrado e terminará a exe ução.

6.2 Como Salvar um Modelo

Com um modelo ompilado na memória pode-se salvar o mesmo em um arquivo textual.

O modelo pode ser salvo tanto no mesmo arquivo de onde foi arregado quanto em um


arquivo diferente.

Linux Para salvar o modelo no mesmo arquivo deve-se sele ionar a opção 2 (Salvar um

modelo QN) no menu prin ipal. Em seguida sele ionar a opção 1 (Salvar) no sub-menu.

O modelo será salvo no mesmo arquivo de onde foi ompilado.

Para salvar o modelo om um arquivo diferente, deve-se sele ionar a opção 2 (Salvar

um modelo QN) no menu prin ipal. Em seguida sele ionar a opção 2 (Salvar omo:) no

sub-menu. Após a mensagem "Salvar modelo omo:" informar o nome do arquivo.

Windows Para salvar o modelo om o mesmo nome deve-se sele ionar o item

no menu . Caso haja um modelo na memória este será salvo no mesmo arquivo

de onde foi ompilado.

No aso de salvar o modelo em um arquivo diferente, sele iona-se o item

no menu . Na janela que surgirá deve-se informar o nome da arquivo e em seguida

li ar no botão na parte inferior do lado direito da janela.

Caso não seja informado a extensão do arquivo, a ferramenta adi ionará a extensão

".mqn" ao nome do arquivo.

6.3 Como Computar os Índi es de Desempenho

Após ompilar o modelo sem que o orra problemas, segue-se alguns passos ne essários

para omputar os índi es de desempenho do modelo.

Linux Sele ionar a opção 4 (Computar índi es de desempenho) no menu prin ipal. Após

a mensagem "Salvar resultado omo:" informar o nome do arquivo onde será salvo

os resultados. Caso não haja problema na omputação dos índi es de desempenho, os

6.4. COMO CONVERTER UM MODELO 93

mesmo estarão salvos no arquivo informado

1

e os índi es gerais de desempenho também

serão mostrados na tela.

Windows A maneira mais simples de omputar os índi es de desempenho é li ar no

botão no entro da tela prin ipal. Os índi es gerais de desempenho

são exibidos na parte inferior da tela prin ipal.

Para visualizar os índi es de desempenho de ada lasse individualmente deve-se li ar

no botão . Surgirá um segunda tela para edição dos pa-

râmetros de ada lasse, na parte inferior das telas são exibidos os índi es de desempenhos

da lasse.

Para o Exemplo1:mqn riado a ima os índi es gerais de desempenho omputados por

MQNA são os seguintes:

Fila Fluxo médio População média Utilização média Tempo médio de resposta

q1 4.999622e-01 9.222770e+00 9.999245e-01 1.844693e+01

q2 9.999245e-02 1.110999e-01 9.999245e-02 1.111083e+00

q3 3.999698e-01 6.661298e-01 3.999698e-01 1.665450e+00

Tabela 6.1: Índi es de desempenho do Exemplo1.mqn

Maiores detalhes sobre omo salvar os resultados obtidos são dados no Manual de

Referên ia do Usuário.

6.4 Como Converter um Modelo

A onversão é usada na maioria das vezes para obtenção de índi es de desempenho de

rede à apa idade limitada, entretanto pode ser útil também na omparação dos resultados

omputados por outras ferramentas.

1

A ferramenta adi iona automati amente a extensão ".res" ao nome do arquivo informado. Isso é

feito para melhor identi� ar os arquivos ontendo os resultados omputados.


Linux Para onverter um modelo QN para SAN deve-se sele ionar a opção 7 (Conveter

um modelo QN para SAN) no menu prin ipal. Em seguida informar o nome de arquivo

após a mensagem "Salvar modelo SAN omo:". O modelo será onvertido e salvo no

arquivo informado.

Ex lusivamente para modelo CQN deve-se informar se a onversão do modelo será

om ou sem restrição à apa idade das �las. Isso deve ser informado após a mensagem

"Salvar modelo om restrição de apa idade(s/n)?" es olhendo as opções `s' ou

`n'.

Windows Para onverter o modelo presente na memória, a maneira mais simples é

li ar no botão no entro da tela prin ipal. Em seguida informar o

nome do arquivo onde será salvo o modelo SAN onvertido. Após informar o nome do

arquivo li ar no botão no lado direito inferior da janela.

Uma segunda informação ainda é ne essária quando da onversão de modelos CQN.

Essa informação é sobre a onversão om ou sem restrição à apa idade das �las. Para

isso deve-se li ar nos botões ou na janela que surgirá na tela

(Figura 6.2).

Figura 6.2: Conversão para SAN om ou sem restrição a apa idade

Convêm ressaltar que aso o modelo do "exemplo1.mqn" seja onvertido sem restrição

à apa idade das �las, os resultados obtidos pela ferramenta PEPS na resolução do modelo

6.4. COMO CONVERTER UM MODELO 95

onvertido são iguais aos resultados omputados pela ferramenta MQNA.

Para informações mais detalhes sobre todas as poten ialidades da ferramenta MQNA

deve-se onsultar o Manual de Referên ia do Usuário (Capítulo 7).


Capítulo 7

Manual de Referên ia do Usuário

Esse Manual de Referên ia do Usuário expli a detalhadamente ada fun ionalidade im-

plementada na ferramenta MQNA.

Da mesma maneira que o Guia Rápido de Ini iação, esse manual está organizado em

seções. Cada seção trata de um assunto isolado que vai desde a riação de modelos até a

utilização da ajuda da ferramenta.

Mais espe i� amente, a Seção 7.1 expli a a riação de modelos. Na Seção 7.2 é exposto

a ompilação dos modelos riados. A Seção 7.3 ontém detalhes de omo salvar um modelo

presente na memória. A Seção 7.4 mostra omo al ular as taxas de visita de um modelo.

Na Seção 7.5 é expli ado omo obter os índi es de desempenho do modelo. A Seção 7.6

expli a o que fazer para alterar os parâmetros do modelo. Na Seção 7.7 mostra-se o que

é ne essário para exibir os índi es de desempenho omputados. A Seção 7.8 expli a os

passos que devem ser seguidos para onverter um modelo QN para SAN. Finalmente a

Seção 7.9 expli a omo obter ajuda na ferramenta.

Devido as duas interfa es implementadas, é apresentado em ada seção primeiramente

os passos para a interfa e Linux e em seguida os passos para a interfa e Windows.

98 CAPÍTULO 7. MANUAL DE REFERÊNCIA DO USUÁRIO

7.1 Criando Modelos

Visto que a ferramenta MQNA ompila modelos QN a partir de um arquivo textual, a

riação dos modelos pode ser feita om a ajuda de qualquer editor de texto.

A seguir é expli ada a estrutura bási a de um modelo e também a estrutura de um

modelo um pou o mais elaborado. Ao �nal desta seção é expli ado a riação de modelos

om o uso de um assistente de riação ex lusivo da versão Windows.

7.1.1 Modelos Bási os

Considerou-se aqui um modelo bási o qualquer modelo QN om apenas uma lasse dife-

ren iada de lientes. Esse modelo bási o que será expli ado a seguir tem o objetivo de

introduzir a gramáti a usada pela ferramenta MQNA na representação de modelo QN.

1

2

M = 2

R = 1

N = 10

K

1

= 6

K

2

= 5

C

1

= 1

C

2

= 1

S

1

1

= 0:2

S

1

2

= 0:1

Figura 7.1: Figura do exemplo2.mqn

A seguir é mostrado um exemplo omentado de um modelo bastante simples om uma

lasse de liente e duas �las, de a ordo om o modelo que representado na Figura 7.1.

exemplo2.mqn - CQN mono- lasse

qn exemplo2(1,2) // entre parênteses de�ne-se o número de lasse e número de �las

de larations{ // iní io das de larações

lass 1; // de laração da lasse

queue q1; // de laração da primeira �la

queue q2; // de laração da segunda �la

} // �m das de larações

network{ // iní io da des rição do modelo

population lass 1 = 10; // população total da lasse, existe somente em CQN

queue q1 { // des rição da primeira �la

servers = 1; // número de servidores desta �la

7.1. CRIANDO MODELOS 99

apa ity = 6; // apa idade da �la, é ignorada no ál ulo à forma-produto

lass 1 { // des rição da lasse nesta �la

servi e time = 0.2; // tempo de serviço desta lasse nesta �la

rot q2: 1; // rotação dos lientes desta lasse

} // �m da des rição da lasse

} // �m da des rição de primeira �la

queue q2 { // des rição da segunda �la

servers = 1; // número de servidores da segunda �la

apa ity = 5; // apa idade da segunda �la

lass 1 { // iní io da des rição da lasse 1

servi e time = 0.1; // tempo de serviço da lasse 1 nesta �la

rot q1: 1; // rotação dos lientes desta lasse saídos desta �la


} // �m da des rição da segunda �la

} // �m da des rição do modelo

7.1.2 Modelos Multi-Classe

Os modelos multi- lasse são em geral um pou o mais so�sti ados que os modelos mono-

lasse. Deve-se uidar prin ipalmente na des rição do modelo que para as duas lasses

estejam des ritas em ada uma das �las.

Abaixo é apresentado, na Figura 7.2, o modelo CQN des rito no "exemplo2.mqn" om

a in lusão de mais uma lasse de lientes.

1

2

S

1

2

= 0:1

S

2

1

= 0:4

S

1

1

= 0:2

C

1

= 1

S

2

2

= 0:2

C

2

= 1

M = 2

R = 2

N

2

= 10

N

1

= 10

K

1

= 11

K

2

= 10

Figura 7.2: Figura do exemplo3.mqn

A seguir é apresentada a des rição textual da Figura 7.2 onforme a gramáti a de�nida

para a ferramenta.

exemplo3.mqn - CQN multi- lasse

qn exemplo3(2,2) // entre parênteses de�ne-se o número de lasse e número de �las

de larations{ // iní io das de larações

lass 1; // de laração da primeira lasse


lass 2; // de laração da segunda lasse

queue q1; // de laração da primeira �la

queue q2; // de laração da segunda �la

} // �m das de larações

network{ // iní io da des rição do modelo

population lass 1 = 10; // população total da lasse 1

population lass 2 = 10; // população total da lasse 2

queue q1 { // des rição da primeira �la

servers = 1; // número de servidores desta �la

apa ity = 11; // apa idade da �la, é ignorada no ál ulo à forma-produto

lass 1 { // des rição da lasse 1 nesta �la


rot q2: 1; // rotação dos lientes desta lasse

} // �m da des rição da primeira lasse

lass 2 { // des rição da segunda lasse


rot q2: 1; // rotação dos lientes da lasse 2

} // �m da des rição da segunda lasse

} // �m da des rição de primeira �la

queue q2 { // des rição da segunda �la

servers = 1; // número de servidores da segunda �la

apa ity = 10; // apa idade da segunda �la



rot q1: 1; // rotação dos lientes desta lasse saídos desta �la




rot q1: 1; // rotação dos lientes da lasse 2

} // �m da des rição da segunda lasse

} // �m da des rição da segunda �la

} // �m da des rição do modelo

7.1.3 Utilizando o Assistente para Criação de um Novo Modelo

O Assistente para Criação de um Novo Modelo é uma fa ilidade ofere ida pela versão

Windows onde é possível a riação de um modelo automati amente. O modelo riado

pelo assistente é um modelo de�nido a partir dos dados oletados pelo assistente. Após

riado, o modelo ontém valores padrões que podem ser alterados pelo usuário onforme

a ne essidade.

7.1. CRIANDO MODELOS 101

Para usar o assistente, deve-se li ar no item no menu . Surgirá

então a janela do assistente, vista na Figura 7.3. Nesta primeira janela deve-se informar

o nome do modelo.

Figura 7.3: Nome do novo modelo

Na segunda janela, mostrada na Figura 7.4, es olhe-se qual o tipo de modelo QN que

deseja-se riar, os tipos possíveis são CQN e OQN.

Figura 7.4: Tipo do novo modelo

O número de lasses de lientes diferen iados que vai existir no modelo é de�nido na

ter eira janela (Figura 7.5) e o número de �las do modelo na quarta janela (Figura 7.5).


Figura 7.5: Número de lasses do novo modelo

Figura 7.6: Número de �las do novo modelo

Para navegar entre as janelas utiliza-se os botões , para passar à janela

seguinte e para retorna à janela anterior. Na última janela deve-se li ar

no botão para terminar o pro esso e riar o modelo. Pode-se an elar o

pro esso de riação a qualquer momento, para isso li a-se no botão .

7.2. COMPILANDO MODELOS 103

7.2 Compilando Modelos

Quando o modelo é ompilado, o mesmo é analisado para ver se está em adequação as

regras da gramáti a de�nida para a ferramenta. Após essa análise gramati al o modelo é

arregado na memória e � a disponível tanto para alterações quanto para a omputação

dos índi es de desempenho.

Linux No menu prin ipal sele ionar a opção 1 (Compilar um modelo QN). Informar o

nome do arquivo, o qual deve ter a extensão ".mqn", após a mensagem "Nome do Arquivo

QN:".

Windows Sele ionar o item no menu . Na janela que surgirá, sele-

ionar o arquivo ontendo o modelo. Após sele ionado li ar no botão .

7.3 Salvando Modelos

Normalmente utilizada após a alteração de algum parâmetro do modelo, a opção de

salvar o modelo pode ser feita de duas maneiras. Simplesmente salvar o modelo ou salvar

o modelo em um arquivo diferente.

7.3.1 Salvar

Essa opção salva o modelo que está na memória no mesmo arquivo de onde foi arregado.

Linux Sele ionar a opção 2 (Salvar um modelo QN) no menu prin ipal. No sub-menu

desta opção sele ionar a opção 1 (Salvar). O modelo será salvo no mesmo arquivo de onde

foi arregado.

Windows No menu basta sele ionar o item que o modelo será salvo

no arquivo de onde foi arregado.


No aso do modelo ter sido riado pelo Assistente e ainda não tiver um arquivo

asso iado, a janela da opção será exibida para a es olha de um novo

arquivo onde será salvo o modelo.

7.3.2 Salvar omo:

Esta opção salva o modelo presente na memória pedindo em qual arquivo salvá-lo.

Linux Sele ionar a opção 2 (Salvar um modelo QN) no menu prin ipal. No sub-menu

desta opção sele ionar a opção 2 (Salvar omo:). Após a mensagem "Salvar o modelo

omo:", informar o nome do arquivo

1

.

Windows Sele ionar o item no menu . Na janela exibida in-

formar o nome do arquivo onde será salvo o modelo e em seguida li ar em .

7.4 Cal ulando Taxas de Visita

Cal ula as taxas de visita usadas para a omputação dos índi es de desempenho. Essas

taxas são obtidas om a resolução da matriz de probabilidade de rotação dos lientes.

Segue algumas maneiras de obté-las sem que seja pre iso omputar o modelo.

7.4.1 Cal ulando Todas as Taxas

Essa opção resolve a matriz de probabilidade de rotação de todas as lasses do modelo.

Linux No menu prin ipal sele ionar a opção 3 (Computar taxas de visita). No sub-

menu desta opção sele ionar a opção 1 (Computar todas as lasses). Após as mensagem

"Salvar vetor de probabilidade omo:", informar o nome do arquivo

2

.

1

Será adi onada a extensão ".mqn", aso está não seja informada.

2

Será adi onada a extensão ".vet" ao nome do arquivo e salvo no diretório "./vet".

7.4. CALCULANDO TAXAS DE VISITA 105

Windows Deve-se li ar no botão para abri a janela

de edição de parâmetros da lasse. Nessa janela li ar no botão .

Para salvar as taxas de visita al uladas deve-se li ar no botão .

Na janela que surgirá deve ser informado o nome do arquivo e em seguida li ar no botão

.

7.4.2 Cal ulando Taxas de Visita de uma Classe

Existente apenas na versão Linux, usa-se para al ular as taxas de visita de uma lasse

espe í� a.

Deve-se para isso sele ionar a opção 3 (Computar taxas de visita) no menu prin ipal.

No sub-menu desta opção sele ionar a opção 2 (Espe i� ar a lasse). Informar a lasse

que deseja-se al ular após a mensagem "Entre o número da lasse a ser omputada

(0..x):"

3

. As taxas al uladas são mostradas na tela.

7.4.3 Alterando Número Máximo de Iterações

O número máximo de iterações é alterado quando a resolução da matriz de probabilidade

de rotação não al ançou o erro máximo a eitável após o número de iterações de�nido.

Linux Deve-se sele ionar a opção 3 (Computar taxas de visita) no menu prin ipal.

Sele ionar novamente a opção 3 (Alterar número de iterações) no sub-menu. Informar o

número de iterações após a mensagem "Entre o número máximo de iterações:".

Windows Há duas possibilidades para mudar o número máximo de iterações. Na

primeira maneira deve-se sele ionar o item no menu na

janela prin ipal. A segunda maneira é mais práti a aso a janela ativa seja a janela de

3

x representa a última lasse do modelo, a es olha da lasse deve ser entre as opções dentro dos

parênteses.


edição de parâmetros das lasses. Nessa janela li a-se no botão

no lado direito superior da janela.

Nos dois asos surgirá uma ter eira janela (Figura 7.7) onde é informado o número de

iterações que se deseja.

Figura 7.7: Alteração do número máximo de iterações

7.4.4 Alterando Erro Máximo A eitável

Normalmente o erro máximo a eitável é alterado quando ne essita-se de uma pre isão

maior nos resultados.

Linux Deve-se sele ionar a opção 3 (Computar taxas de visita) no menu prin ipal. Se-

le ionar a opção 4 (Alterar erro máximo) no sub-menu. Informar o erro máximo a eitável

após a mensagem "Entre o erro máximo a eitável:".

Windows É possível mudar o erro máximo de duas maneiras. Na primeira maneira

deve-se sele ionar o item no menu na janela prin ipal. A segunda

maneira é mais práti a se a janela for a janela de edição dos parâmetros das lasses. Nessa

janela deve-se li ar no botão no lado direito superior da

janela.

Surgirá uma ter eira janela (Figura 7.8), independente da maneira es olhida. Nessa

janela deve ser informado o erro máximo a eitável na resolução da matriz.

7.5. COMPUTANDO ÍNDICES DE DESEMPENHO 107

Figura 7.8: Alteração do erro máximo a eitável

7.5 Computando Índi es de Desempenho

São omputados por MQNA os índi es de desempenho omumente utilizados para avali-

ação de redes à forma-produto. Esses índi es são: o �uxo médio padrão, a utilização

média, a população média e o tempo médio de resposta.

Esses índi es são obtidos através dos seguintes passos.

Linux Computa-se os índi es de desempenho sele ionando a opção 4 (Computar índi es

de desempenho) no menu prin ipal. Após a mensagem "Salvar resultado omo:",

deve-se informar o nome do arquivo onde serão salvos os resultados

4

. Os resultados

gerais do modelo, além de salvo no arquivo informado, são mostrados também na tela.

Windows Duas maneiras são possíveis para omputar os índi es de desempenho do

modelo. Na primeira maneira deve-se sele ionar o item no menu

da janela prin ipal. A segunda maneira é um pou o mais práti a. Deve-se

li ar no botão presente tanto no entro da janela prin ipal quanto

na parte inferior da janela para edição dos parâmetros das lasses.

Os resultados obtidos são exibidos na parte inferior das janelas. Contanto, na janela

4

A ferramenta adi iona automati amente a extensão ".res" ao nome do arquivo informado. Isso é

feito para melhor identi� ar os arquivos ontendo os resultados omputados.


prin ipal são exibidos os índi es gerais do modelo enquanto na janela de edição dos parâ-

metros das lasses são exibidos os índi es de desempenho espe í� os de ada lasse.

7.5.1 Salvando Resultados

Esta é uma opção disponível somente para a versão Windows, visto que na versão Linux

os resultados são salvos juntamente om a omputação dos índi es de desempenho.

Para salvar os resultados omputados em arquivo li a-se no item

no menu . Surgirá uma janela onde deve ser informado o nome do arquivo onde

será salvo os resultados e em seguida li ar no botão .

7.6 Alterando Parâmetros do Modelo

A alteração do modelo é feita normalmente para adequar o modelo riado as ara terísti as

do sistema ou para testar diversas on�gurações observando aquela que melhor se adequa

ao sistema real.

Altera-se normalmente dois tipos de parâmetros. Os parâmetros das lasses e os

parâmetros das �las.

7.6.1 Alterando Parâmetros das Classes

Alguns parâmetros podem ser alterados para ada lasse individualmente. Segue abaixo

omo pro eder para alterar ada parâmetro.

Nome da Classe

Apesar de não afetar os índi es de desempenho do modelo, o nome da lasse serve para

identi� ar o es opo de ada lasse na des rição textual de um modelo QN.

7.6. ALTERANDO PARÂMETROS DO MODELO 109

Linux No menu prin ipal sele iona-se a opção 5 (Alterar parâmetros do modelo). No

sub-menu desta opção sele ionar a opção 1 (Parâmetros das lasses). Neste sub-menu se-

le ionar novamente a opção 1 (Nome da lasse). Após a mensagem "Entre o número da

lasse(0..X):"

5

informa-se qual a lasse que deseja-se alterar o nome. O nome da lasse

deve ser informado após a mensagem "Entre o nome da lasse(x):"

6

.

Windows Caso a janela de edição dos parâmetros da lasse não esteja aberta, deve-

se li ar no botão para abri-la. Sele iona-se então a

aixa de edição ao lado da mensagem . O nome da lasse deve ser

informado na aixa de edição onde apare e o nome atual da lasse.

Tempo de Serviço

Essa parâmetro altera o tempo médio de serviço de uma lasse em uma �la.


sub-menu desta opção sele ionar a opção 1 (Parâmetros das lasses). Neste sub-menu

sele ionar a opção 2 (Tempo de serviço). Após a mensagem "Entre o número da lasse

(0..X):", informa-se qual a lasse que deseja-se alterar. Deve-se informar ainda em qual

�la será feita a alteração. Informa-se a �la após a mensagem "Entre o número da fila

(0..Y):"

7

. O tempo de serviço é informado após a mensagem "Entre o tempo médio de

serviço de lientes da lasse(x) na fila(y):"

8

.

Windows Caso a janela de edição dos parâmetros da lasse não esteja aberta, deve-se

li ar no botão para abri-la. Em seguida deve-se sele-

ionar no quadro om os tempos de serviço a �la desejada (Figura 7.9). Após sele ionada

é só alterar o valor atual para o valor desejado.

5

Entre parênteses são mostradas as opções de lasse, X representa a última lasse do modelo.

6

x representa o número da lasse es olhida.

7

Entre parênteses são mostradas as opções de �la, Y representa a última �la do modelo.

8

x e y representam respe tivamente o número da lasse e da �la es olhidas.


Figura 7.9: Alteração do tempo de serviço

População da Classe

Esse parâmetro só está presente nos modelos CQN e representa a população total de

lientes da lasse.

Altera-se a população da lasse da seguinte maneira.


sub-menu desta opção sele ionar a opção 1 (Parâmetros das lasses). Neste sub-menu sele-

ionar a opção 3 (População da lasse). Após a mensagem "Entre o número da lasse

(0..X):", informa-se qual a lasse que deseja-se alterar a população. Informa-se a nova

população após a mensagem "Entre a população da lasse(x):".

Windows Caso a janela de edição dos parâmetros da lasse não esteja aberta, deve-se

li ar no botão para abri-la. Deve sele ionar-se então

a aixa de edição ao lado da mensagem . Após sele ionada é só

informar a população desejada para efetivar a alteração.

Taxa de Chegada

Assim omo a população da lasse é um parâmetro ex lusivo dos modelos CQN a taxa de

hegada é ex lusividade das OQN.

A alteração da taxa de hegada de uma lasse em uma �la é feita da seguinte maneira.


sub-menu desta opção sele ionar a opção 1 (Parâmetros das lasses). Neste sub-menu

sele ionar a opção 3 (Taxa de hegada da lasse). Após a mensagem "Entre o número da

7.6. ALTERANDO PARÂMETROS DO MODELO 111

lasse(0..X):", informa-se qual a lasse que deseja-se alterar. Deve-se informar também

em qual �la será feita a alteração. Informar a �la após a mensagem "Entre o número

da fila(0..Y):". A taxa de hegada é informada após a mensagem "Entre a taxa de

hegada média de lientes da lasse(x) na fila(y):".

Windows Caso a janela de edição dos parâmetros da lasse não esteja aberta, deve-

se li ar no botão para abri-la. Em seguida deve ser

sele ionada, no quadro om as taxas de hegada (Figura 7.10), a �la desejada. Após

sele ionada é só alterar o valor atual para o valor desejado.

Figura 7.10: Alteração da taxa de hegada de lientes

7.6.2 Alterando Parâmetros das Filas

Os parâmetros das �las que são omumente alterados são basi amente: o nome da �la, o

número de servidores e a apa idade da �la.

A alteração de ada um destes parâmetros é mostrada individualmente a seguir.

Nome da Fila

O nome da �la é utilizado para identi� ar ada �la numa des rição textual do modelo.


sub-menu desta opção sele ionar a opção 2 (Parâmetros das �las). Neste sub-menu sele-

ionar a opção 1 (Nome da �la). Após a mensagem "Entre o número da fila(0..Y):"

9

9

Entre parênteses são mostradas as opções de �la, Y representa a última �la do modelo.


informa-se qual a �la que deseja-se alterar o nome. Informa-se o nome da �la após a men-

sagem "Entre o nome da fila(y):".

Windows A alteração do nome da �la é feita na janela prin ipal da ferramenta. Na

segunda oluna do quadro Cara terísti as das �las (Figura 7.11), deve ser sele ionada a

�la que deseja-se alterar o nome. Após sele ionado é ne essário apenas informar o novo

nome.

Figura 7.11: Alteração do nome da �la

Número de Servidores

Esse parâmetro de�ne o número de servidores em paralelos utilizados na �la.


sub-menu desta opção sele ionar a opção 2 (Parâmetros das �las). Neste sub-menu sele-

ionar novamente a opção 2 (Número de servidores). Após a mensagem "Entre o número

da fila(0..Y):", informa-se qual a �la que deseja-se alterar o número de servidores.

Informa-se então o número de servidores após a mensagem "Entre o número de servi-

dores da fila(y):".

Windows Na janela prin ipal deve ser sele ionada a �la que deseja-se mudar o número

de servidores na ter eira oluna (Figura 7.12) do quadro Cara terísti as das �las. Após

sele ionada a �la desejada é ne essário apenas tro ar o valor exibido pelo valor desejado.

Figura 7.12: Alteração do número de servidores da �la

7.7. EXIBINDO RESULTADOS 113

Capa idade da Fila

A alteração deste parâmetro não in�uen ia nos índi es de desempenho omputados por

MQNA, visto que é ignorado nas redes à forma-produto. No entanto é um parâmetro

importante na onversão para um modelo SAN.

Pode-se alterar a apa iade da �la da seguinte maneira.


sub-menu desta opção sele ionar a opção 2 (Parâmetros das �las). Neste sub-menu se-

le ionar a opção 3 (Capa idade da �la). Após a mensagem "Entre o número da fila

(0..Y):", informa-se qual a �la que deseja-se alterar a apa idade. Informa-se então a

apa idade desejada após a mensagem "Entre a apa idade da fila(y):.

Windows A alteração da apa idade da �la é feita na janela prin ipal da ferramenta

MQNA. Na quarta oluna (Figura 7.13) do quadro Cara terísti as das �las, deve ser

sele ionada a �la desejada para alteração da apa idade. Após sele ionada é ne essário

apenas informar a apa idade desejada.

Figura 7.13: Alteração da apa idade da �la

7.7 Exibindo Resultados

Não muito utilizada na versão Windows, visto que os resultados � am sempre exibidos na

tela após a omputação dos índi es de desempenho, essa fun ionalidade é mais utilizada

na versão Linux.


7.7.1 Resultados Gerais

Os resultados gerais expressam a situação de todo o modelo, onsiderando todas as lasses

presentes.

Linux No menu prin ipal sele iona-se a opção 6 (Exibir resultados). No sub-menu desta

opção sele ionar a opção 1 (Exibir índi es gerais). Os índi es gerais serão então exibidos

na tela.

Windows Após a omputação dos índi es de desempenho, os mesmo são exibidos no

quadro Resultados Gerais da janela prin ipal.

7.7.2 Resultados das Classes

Pode-se exibir o resultado da lasse individualmente, para se fazer isso segue-se os passos

abaixo.

Linux Duas opções são possíveis para exibição dos resultados das lasses.

Para exibir os resultados de uma lasse espe í� a, deve-se no menu prin ipal sele-

ionar a opção 6 (Exibir resultados). Em seguida sele ionar a opção 2 (Espe i� ar

a lasse) neste sub-menu. Depois de informado o número da lasse após a mensagem

"Entre o número da lasse(0..X):", os resultados da lasse serão exibidos na tela.

Para exibir os resultados de todas lasse perten entes ao modelo deve-se sele ionar

a opção 6 (Exibir resultados) no menu prin ipal. Sele ionar então a opção 3 (Todas as

lasses) deste sub-menu. Os resultados de ada lasse do modelo serão mostrados na tela.

Windows Os resultados de ada lasse � am exibidos, após omputados os índi es de

desempenho, na parte inferior da janela para edição dos parâmetros das lasses. Para abrir

a janela de edição dos parâmetros deve-se li ar no botão .

7.8. CONVERTENDO MODELOS 115

7.8 Convertendo Modelos

A onversão de modelos QN para SAN transforma o modelo presente na memória em um

arquivo textual para a ferramenta PEPS.

O pro esso de onversão é bastante simples, os passos ne essário são os seguintes.

Linux No menu prin ipal deve-se sele ionar a opção 7 (Converter modelo QN para

SAN). Após a mensagem "Salvar modelo SAN omo:", informa-se o nome do arquivo

onde será salvo o modelo

10

.

No aso espe í� o de modelos CQN há ainda a opção de não restringir a apa idade das

�las. Informa-se isso após a mensagem "Salvar modelo om restrição de apa idade

(s/n)?" respondendo-se `s' ou `n'.

Windows Dois aminhos são possíveis para onverter um modelo QN para SAN. Uma

maneira é li ar no botão no entro da janela prin ipal. Uma segunda

maneira é sele ionar o item no menu .

Essa duas opções abrem uma janela onde deve-se informar o nome do arquivo SAN e

em seguida li ar em .

Para modelos CQN há a opção de onverter o modelo sem restrição à apa idade das

�las. O tipo de onversão é informado na janela que apare erá na tela (Figura 7.14),

li ando-se nos botões ou .

10

Os modelos onvertidos são salvos no diretório ./san e a ferramenta a res enta automati amente a

extensão ".san" ao nome do modelo.


Figura 7.14: Conversão para SAN om ou sem restrição a apa idade das �las

7.9 Utilizando a Ajuda

O ajuda da ferramenta traz informações bási as sobre ada tipo de modelo suportado

pela ferramenta (CQN e OQN) e sobre o método de onversão implementado.

Linux Es olher a opção 8 (Sobre a ferramenta MQNA) do menu prin ipal. No sub-menu

desta opção deve-se es olher o tópi o que será apresentado.

Esse tópi os são:

� Gramáti a para redes abertas;

� Gramáti a para redes fe hadas;

� O método de onversão;

� Créditos.

Windows Para obter ajuda deve sele ionar um dos itens disponíveis no menu .

Será aberta uma janela para exibir o item de ajuda es olhido da ajuda.

Os itens disponíveis no menu são:

� - Sobre redes de �las de espera abertas;

� - Sobre redes de �las de espera fe hadas;

� - Sobre o método de onversão;

� - Créditos da ferramenta.

Capítulo 8

Exemplos

Como o objetivo de exempli� ar melhor o uso da ferramenta MQNA, esse apítulo traz

dois exemplos ompletos de modelo QN. Será mostrado então: a riação de ada modelo,

OQN e CQN, a obtenção dos índi es de desempenho pela ferramenta MQNA e a onversão

para modelos SAN equivalentes.

8.1 Modelo OQN

O modelo OQN riado para exemplo esse tipo de QN possui uma úni a lasse (mono-

lasse) e in o �las. A representação grá� a deste modelos é vista na Figura 8.1.

K

1

= 3

K

2

= 2

K

3

= 2

K

4

= 2

K

5

= 3

P

1

1;2

= �1

P

1

1;4

= �2

P

1

2;3

= 1:0

P

1

4;5

= 1:0

C

5

= 1

C

4

= 1

C

3

= 1

C

2

= 1

L

1

1

= 2

L

1

2

= 1

P

1

3;1

= �3

S

1

5

= 0:2

S

1

4

= 0:2

S

1

3

= 0:1

S

1

2

= 0:1

P

1

5;1

= �4

S

1

1

= 0:05

C

1

= 1

1

3

4

5

2

�1

�2

M = 5

R = 1

�4

�3

Figura 8.1: Modelo OQN mono- lasse om in o �las

118 CAPÍTULO 8. EXEMPLOS

8.1.1 Criando o Modelo

Assumindo-se os valores �1 = 0:8, �2 = 0:2, �3 = 0:1 e �4 = 0:2 para a rotação dos

lientes da lasse, a des rição textual do modelo da Figura 8.1 é feita da seguinte maneira.

oqn_ex.mqn - OQN mono- lasse

oqn oqn_ex1 (1,5)

de larations {

lass 1;

queue q1;

queue q2;

queue q3;

queue q4;

queue q5;

}

network{

queue q1 {

servers = 1;

apa ity = 3;

lass 1 {

servi e time = 0.05;

arrival rate = 2;

rot q2:0.8;

rot q4:0.2;

}

}

queue q2 {

servers = 1;

apa ity = 2;

lass 1{

servi e time = 0.1;

arrival rate = 1;

rot q3:1.0;

}

}

queue q3 {

servers = 1;

apa ity = 2;

lass 1 {

servi e time = 0.1;

arrival rate = 0;

rot q1:0.1;

}

}

8.1. MODELO OQN 119

queue q4 {

servers = 1;

apa ity = 2;

lass 1 {

servi e time = 0.2;

arrival rate = 0;

rot q5:1.0;

}

}

queue q5 {

servers = 1;

apa ity = 3;

lass 1 {

servi e time = 0.2;

arrival rate = 0;

rot q1:0.2;

}

}

}

8.1.2 Computando os Índi es de Desempenho

Com o modelo na memória da ferramenta omputou-se os índi es de desempenho para o

modelo. A apa idade de ada �la é ignorada pela ferramenta MQNA para que o modelo

obedeça as regras das redes à forma-produto.

Os índi es gerais de desempenho obtidos para o modelo foram:


q1 2.386364e+00 1.354839e-01 1.193182e-01 2.709677e+00

q2 2.909091e+00 4.102564e-01 2.909091e-01 4.102564e+00

q3 2.909091e+00 4.102564e-01 2.909091e-01 4.102564e+00

q4 4.772727e-01 1.055276e-01 9.545455e-02 5.276382e-01

q5 4.772727e-01 1.055276e-01 9.545455e-02 5.276382e-01

Tabela 8.1: Índi es de desempenho do modelo oqn_ex.mqn


8.1.3 Convertendo o Modelo

O resultado da onversão do modelo QN para SAN foi um modelo SAN om 5 aut�matos

onde o número total de estados é 432, dos quais todos são atingíveis.

O modelo gerado foi ompilado e resolvido pela ferramenta PEPS. Utilizou-se para

a resolução o Método da Potên ia, o qual resolveu o modelo após 474 iterações. Os

resultados obtidos pela ferramenta PEPS foram:

Fila Fluxo médio População média Utilização média

q1 2.696244e+00 1.565140e-01 1.348122e-01

q2 3.013758e+00 3.788609e-01 3.013758e-01

q3 2.768665e+00 3.407075e-01 2.768665e-01

q4 5.324615e-01 1.172929e-01 1.064923e-01

q5 5.320325e-01 1.184261e-01 1.064065e-01

Tabela 8.2: Índi es de desempenho obtidos por PEPS

8.2 Modelo CQN

Adotou-se para exempli� ar os modelos CQN um modelo om in os �las, onde uma �las

é multi-servidora, e uma lasse diferen iada de lientes. A �gura representando o modelo

adotado é mostrada abaixo na Figura 8.2.

1

2 3

4 5

�1

�2

K

2

= 3

K

3

= 3

K

4

= 2

K

5

= 2

P

1

1;2

= �1

P

1

4;5

= 1:0

C

5

= 1

C

4

= 1

C

3

= 1

C

2

= 1

C

1

= 2

K

1

= 3

R = 1

M = 5

N = 10

P

1

2;3

= 1:0

P

1

1;4

= �2

P

1

3;1

= 1:0

S

1

5

= 1:0

S

1

4

= 2:0

S

1

3

= 2:0

S

1

2

= 1:0

S

1

1

= 2:0

P

1

5;1

= 1:0

Figura 8.2: Modelo CQN om in o �las e uma lasse

8.2. MODELO CQN 121

8.2.1 Criando o Modelo

O modelo representado pela Figura 8.2 a ima é des rito textual da maneria exposta

abaixo, quando os valores �1 = 0:3 e �2 = 0:7 são assumidos para a probabilidade de

rotação dos lientes no modelo.

qn_ex.mqn - CQN mono- lasse

qn qn_ex1(1,5)

de larations {

lass 1;

queue q1;

queue q2;

queue q3;

queue q4;

queue q5;

}

network {

population lass 1 = 10;

queue q1 {

servers = 2;

apa ity = 3;

lass 1 {

servi e time = 2.0;

rot q2: 0.3;

rot q4: 0.7;

}

}

queue q2 {

servers = 1;

apa ity = 3;

lass 1 {

servi e time = 1.0;

rot q3: 1;

}

}

queue q3 {

servers = 1;

apa ity = 3;

lass 1 {

servi e time = 2.0;

rot q1: 1;

}

}


queue q4 {

servers = 1;

apa ity = 2;

lass 1 {

servi e time = 2.0;

rot q5: 1;

}

}

queue q5 {

servers = 1;

apa ity = 2;

lass 1 {

servi e time = 1.0;

rot q1: 1;

}

}

}

8.2.2 Computando os Índi es de Desempenho

Os índi es de desempenho omputados pela ferramenta MQNA para o modelo des rito no

exemplo " qn_ex.mqn" não levam em onta a restrição à apa idade das �las, ou seja,

os índi es al ulados respeitam as restrições das redes à forma-produto.

Os índi es de desempenho obtidos para o modelo à forma-produto foram os seguintes:


q1 6.921788e-01 2.376579e+00 6.921788e-01 3.433476e+00

q2 2.076536e-01 2.608460e-01 2.076536e-01 1.256159e+00

q3 2.076536e-01 6.962378e-01 4.153073e-01 3.352880e+00

q4 4.845251e-01 5.755678e+00 9.690503e-01 1.187901e+01

q5 4.845251e-01 9.106589e-01 4.845251e-01 1.879487e+00

Tabela 8.3: Índi es de desempenho do modelo qn_ex.mqn

8.2.3 Convertendo o Modelo

O modelo CQN des rito no item 8.2.1 foi onvertido pela ferramenta MQNA primeira-

mente ignorando a restrição de apa idade das �las. Com isso pode-se resolver o modelo

8.2. MODELO CQN 123

pela ferramenta PEPS e obter os índi es iguais aos obtidos pela ferramenta MQNA.

O modelo gerado sem restrição à apa idade das �las possui 5 aut�matos e 161.051

estados, dos quais 1.001 são atingíveis.

O modelo foi resolvido peloMétodo da Potên ia após 968 iterações e obteve os mesmos

resultados para os índi es de desempenho al ulados por MQNA.

Para o modelo gerado om restrição à apa idade das �las, o modelo possuia 5 aut�-

matos e 576 estados, deste apenas 33 eram atingíveis.

O arquivo resultante da onversão do modelo om restrição à apa idade é mostrado

abaixo.

qn_ex.san - Modelo SAN resultante

de larations {

onstant Ci0 := 2;

onstant Ci1 := 1;

onstant Ci2 := 1;

onstant Ci3 := 1;

onstant Ci4 := 1;

onstant Sri00 := 2;

onstant Sri01 := 1;

onstant Sri02 := 2;

onstant Sri03 := 2;

onstant Sri04 := 1;

fun tional Mu00 := 1/Sri00;





fun tional rot_ 1_q1toq2 := min [Ci0,st 1_q1℄ * 0.3 * Mu00;

fun tional rot_ 1_q1toq4 := min [Ci0,st 1_q1℄ * 0.7 * Mu00;

fun tional rot_ 1_q2toq3 := min [Ci1,st 1_q2℄ * 1 * Mu01;




}


rea hability := ((st 1_q1 + st 1_q2 + st 1_q3 + st 1_q4 + st 1_q5) == 10);

network qn_ex1 ( ontinuous, 5) {

automaton 1_q1 (1, 4) {

node n0 (1) { ar (n1, 2) { syn (s_ 1_q3toq1, 1, 1) syn (s_ 1_q5toq1, 1,

1)}}

node n1 (2) { ar (n2, 2) { syn (s_ 1_q3toq1, 1, 1) syn (s_ 1_q5toq1, 1, 1)}

ar (n0, 2) { syn (s_ 1_q1toq2, rot_ 1_q1toq2, 1) syn (s_ 1_q1toq4,

rot_ 1_q1toq4, 1)}}

node n2 (2) { ar (n3, 2) { syn (s_ 1_q3toq1, 1, 1) syn (s_ 1_q5toq1, 1, 1)}

ar (n1, 2) { syn (s_ 1_q1toq2, rot_ 1_q1toq2, 1) syn (s_ 1_q1toq4,

rot_ 1_q1toq4, 1)}}

node n3 (1) { ar (n2, 2) { syn (s_ 1_q1toq2, rot_ 1_q1toq2, 1) syn

(s_ 1_q1toq4, rot_ 1_q1toq4, 1)}}

}


node n0 (1) { ar (n1, 1) { syn (s_ 1_q1toq2, 1, 1)}}

node n1 (2) { ar (n2, 1) { syn (s_ 1_q1toq2, 1, 1)}

ar (n0, 1) { syn (s_ 1_q2toq3, rot_ 1_q2toq3, 1)}}



node n3 (1) { ar (n2, 1) { syn (s_ 1_q2toq3, rot_ 1_q2toq3, 1)}}

}








}






}






}

}

results{

di0 := (( st 1_q1) != 0) * min [Ci0,st 1_q1℄ * Mu00;

8.2. MODELO CQN 125





ni0 := (( st 1_q1));

ni1 := (( st 1_q2));

ni2 := (( st 1_q3));

ni3 := (( st 1_q4));

ni4 := (( st 1_q5));

ui0 := (( st 1_q1) != 0);

ui1 := (( st 1_q2) != 0);

ui2 := (( st 1_q3) != 0);

ui3 := (( st 1_q4) != 0);

ui4 := (( st 1_q5) != 0);

// wi0 := ni0/di0;

// wi1 := ni1/di1;

// wi2 := ni2/di2;

// wi3 := ni3/di3;

// wi4 := ni4/di4;

dri00 := (st 1_q1 !=0) * min [Ci0,st 1_q1℄ * Mu00;





nri00 := st 1_q1;

nri01 := st 1_q2;

nri02 := st 1_q3;

nri03 := st 1_q4;

nri04 := st 1_q5;

uri00 := (st 1_q1 !=0);

uri01 := (st 1_q2 !=0);

uri02 := (st 1_q3 !=0);

uri03 := (st 1_q4 !=0);

uri04 := (st 1_q5 !=0);

}

Este modelo foi resolvido pelo Método da Potên ia após 418 iterações e os resultados

obtidos são apresentados na tabela 8.4.

Os modelos riados neste apítulo para exempli ar o uso da ferramenta MQNA na

resolução e onversão de modelo, são modelos bastante elementares e permitem uma

resolução num urto espaço de tempo nas duas ferramentas (MQNA e PEPS). Entretanto

modelos mais elaborados também podem ser riado e omputados pelas ferramentas. No


Fila Fluxo médio População média Utilização média

q1 9.578846e-01 2.548886e+00 9.934877e-01

q2 9.382082e-01 2.068620e+00 9.382082e-01

q3 4.992738e-01 2.794606e+00 9.985477e-01

q4 4.403093e-01 1.461519e+00 8.806187e-01

q5 7.475779e-01 1.126367e+00 7.475779e-01

Tabela 8.4: Índi es de desempenho do modelo om restrição à apa idade

entanto deve-se ressaltar que modelos muito omplexos ne essitam de grande quantidade

de re ursos do sistema (memória e pro essador) e podem a limitação desses re ursos

inviabilisar a obtenção dos índi es de desempenho.

Capítulo 9

Con lusão

Este trabalho vem juntar-se a um onjunto de trabalhos sobre avaliação de desempenho de

sistemas através de métodos analíti os. Como visto durante todo o do umento, fo ou-se

os objetivos na modelagem e resolução de sistemas através de Redes de Filas de Espera

(QN) e na onversão de QN para Redes de Aut�matos Esto ásti os (SAN). Esses objetivos

extraem o que ada formalismo apresenta de melhor.

No umprimento dos objetivos propostos por este trabalho, ita-se resolução de QN e

onversão para SAN, foi riada então a ferramenta MQNA, a qual tem versões disponíveis

para Linux (textual) e Windows (grá� a).

MQNA é uma ferramenta de software que implementa métodos para obtenção de

índi es de desempenho para QN à forma-produto e pro edimentos de onversão do formal-

ismo QN para SAN. A ferramenta possibilitou uma melhor e mais ompleta representação

textual de modelos QN através da gramáti a de�nida para a ferramenta. MQNA junta na

sua implementação métodos para resolver tanto Redes de Filas de Espera Aberta (OQN)

quanto Redes de Filas de Espera Fe hadas (CQN) em uma só ferramenta a qual identi� a

o modelo ompilado e utiliza o método adequado para ada modelo sem a intervenção

de usuário. Para as QN onde não era possível a solução à forma-produto, foram imple-

mentados métodos para onverter estas QN em SAN, podendo assim obter os índi es de

desempenho interessantes ao modelo. Essa onversão implementada em MQNA fa ilitou

128 CAPÍTULO 9. CONCLUS�O

então o inter âmbio de informações entre modelos riados em diferentes formalismos o que

aumenta o grau de on�ança nos resultados obtidos. MQNA implementa um assistente

para riação rápida de modelos QN. Através de pou os passos é possivel riar rapidamente

um modelo padrão, para alteração posterior pelo usuário, sem que seja ne essário a edição

de um arquivo textual sem nenhuma informação (vazio).

A realização de um trabalho de on lusão sobre este tema foi pessoalmente interessante

pelo tema es olhido ser de grande interesse para minhas ambições de pesquisa. Além

disso a realização do trabalho é ontinuação de um pro esso no qual trabalhei boa parte

da minha vida a adêmi a. Com a �nalização do trabalho teóri o e práti o, os resultados

obtidos foram, a meu ver, bastante satisfatórios e instigaram um interesse na ontinuação

de trabalhos sobre este tema.

No que diz respeito a trabalhos futuros, a ontinuação natural deste trabalho se divide

em trabalhos eminentemente teóri os e trabalhos de implementação. Do ponto de vista

teóri o aberia o estudo de possíveis aproximações analíti as a modelos om restrição de

apa idade, pesquisas para métodos de onversão mais otimizados ou ainda entre outros

formalismos de modelagem. Novos métodos para omputação de índi es de desempenho

para QN à forma-produto também poderiam ser pesquisados.

Do ponto de vista de implementação, os trabalhos futuros in luem a implementação

de algoritmos aproximativos para algumas lasses de QN que não são à forma-produto, a

implementação de outras dis ilinas de atendimento nas �las, omo por exemplo, atendi-

mento rand�mi o ou tempo ompartilhado. Igualmente uma implementação de QN mistas

poderia ser adi ionada à ferramenta e à gramáti a. É parti ularmente interessante uma

maior integração entre as ferramentas MQNA e PEPS, onvergindo as duas para uma

úni a interfa e apaz de tratar de forma análoga diversos formalismos e modelos.

Referên ias Bibliográ� as

[1℄ C.G.P. Alegretti. Avaliação de desempenho de sistema paralelo de malha

regular utilizando rede aut�matos esto ásti o. Porto Alegre. Fa uldade de

Informáti a da PUCRS. 1998. (Trabalho Individual)

[2℄ Avaliação Quantitativa de Sistemas. http://www.inf.pu rs.br/�paulof/ ourses/-

aqs.html (página de dis iplina de urso de graduação em Ciên ia da Computação

- PUCRS - a essada em 23/11/2001).

[3℄ F.Baskett, K.M.Chandy, R.R.Muntz, F.G.Pala ios. Open, losed and mixed networks

of queues with di�erent lasses of ustomers. Journal of the ACM, vol. 22, nr. 2,

1975, pág. 248-260.

[4℄ J.Buzen Computational algorithms for losed queueing networks with exponential

servers. Communi ations of ACM, vol. 16, nr. 9, 1973, pág. 527-531.

[5℄ P.Fernandes.Méthodes numériques pour la solution de systèmes markoviens

à grand espa e d'états. Institut National Polyte hnique de Grenoble. 1998. (These

de Do torat)

[6℄ P.Fernandes, C.G.P.Alegretti, R.Jungblut-Hessel. Avaliação de Desempenho de Sis-

temas através de redes de Aut�matos Esto ásti os. VII ERI - Es ola Regional de

Informáti a. Novo Hamburgo - Chape ó - Londrina. 10-14 maio. 1999. pág. 159-184.

[7℄ P.Fernandes, B.Plateau. Modeling Finite Capa ity Queueing Networks with Sto hati

Automata Networks. Fourth International Workshop on Queueing Networks

with Finite Capa ity (QNETs 2000). Ilkley, West Yorkshire, UK. 20-21 July.

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

130 REFERÊNCIAS BIBLIOGRÁFICAS

[8℄ P.Fernandes, B.Plateau, W.J.Stewart. E� ient des riptor-ve tor multipli ation in

sto hasti automata networks. Journal of the ACM, vol. 45, nr. 3, 1998. pág.

381-414.

[9℄ J.E.Hop roft, J.D.Ullman. Introdu tion to automata theory, languages and

omputation. Reading: Addison-Wesley. 1979.

[10℄ J.R.Ja kson. Jobshop-like queueing systems. Management S ien e, vol. 10, 1963,

pág. 131-142.

[11℄ D.G.Kendall. Some problems in the theory of queues. Journal of the Royal Sta-

tisti al So iety Ser.B.. nr. 13. 1951. pág. 151-185.

[12℄ H.Kobayashi. Modeling and analysys. Reading: Addison-Wesley, 1978.

[13℄ E.Lazowska, J.Zahorjan, G.Graham, K.Sevi .Quantitative system performan e:

omputer system analysis using queueing networks models. Englewood

Cli�s: Prenti e-Hall, 1984.

[14℄ J.D.C.Little. A proof of the queueing formula L = �W . Operations Resear h, vol.

9, 1961, pág. 383-387.

[15℄ J.M Kenna, D.Mitra. Integral Representations and Asymptoti Expansions for Closed

Markovian Queueing Networks: Normal Usage. The Bell Te hni al Journal. vol.

61. nr. 5. May-June 1982. pág. 661-683.

[16℄ J.M Kenna, D.Mitra. Asymptoti Expansions and Integral Representations of Mo-

ments of Queue Lengths in Closed Markovian Networks. Journal of the ACM. vol.

31. nr. 2. April 1984. pág. 346-360.

[17℄ J.M Kenna, D.Mitra. Asymptoti Expansions for Closed Markovian Networks with

State-Dependent Servi e Rates. Journal of the ACM. vol. 33. nr. 3. July 1986. pág.

568-592.

REFERÊNCIAS BIBLIOGRÁFICAS 131

[18℄ J.M Kenna. Asymptoti Expansions of the Sojourn Time Distribution Fun tions of

Jobs in Closed, Produ t-form Queueing Networks. Journal of the ACM. vol. 34.

nr. 4. O t 1987. pág. 985-1003.

[19℄ D.A.Menas é, V.A.F.Almeida.Capa ity Planning for Web Performan e: met-

ri s, models and methods. Prenti e-Hall, 1994.

[20℄ PEPS Projet s: Performan e Evaluation of Parallel Systems. http://www-

apa he.imag.fr/software/peps/ (a essada em 23/11/2001)

[21℄ B.Plateau, K.Atif. Sto hasti automata networks for modelling parallel systems.

IEEE transa tions on software engineering, vol. 17, nr. 10, pág. 1093-1108,

1991.

[22℄ B.Plateau, W.J.Stewart. Sto hasti automata networks: produ t forms and

iterative solutions. INRIA, Rapport de Re her he nr. 2939, 1996. Anonymous ftp

ftp://ftp.inria.fr/INRIA/Publi ation/RR/RR-2939.ps.gz

[23℄ M.Reiser, S.S.Lavenberg. Mean value analysis of losed multi hain queueing net-

works. Journal of the ACM, vol. 27, nr. 2, 1980, pág. 313-322.

[24℄ T.G.Robertazzi.Computer networks and systems: queueing theory and per-

forman e evaluation. New York: Springer-Verlag, 1990.

[25℄ Y.Saad. Iterative methods for sparse linear systems. Boston: PWS Publishing

Company, 1995.

[26℄ E.A.de Souza e Silva, R.R.Muntz. Métodos Computa ionais de soluçao de

adeias de Markov: apli ações a sistemas de omputação e omuni ação.

VIII Es ola de Computação, Instituto de Informáti a, UFRGS, Porto Alegre, 1992.

[27℄ W.J.Stewart. Introdu tion to the numeri al solution of Markov hains.

Prin eton University Press, 1994.

[28℄ K.Trivedi. Probability & statisti s with reliability, queueing and omputer

s ien e appli ations. Englewwod Cli�s, New Jersey: Prenti e-Hall, 1982.

132 REFERÊNCIAS BIBLIOGRÁFICAS

Apêndi e A

Notação Utilizada

Neste apêndi e é en ontrado um resumo de todas as notações utilizadas neste trabalho

agrupada por seção para fa ilitar a onsulta.

A.1 Notação de Kendall

Notação entregada na Notação de Kendall.

A.1.1 Tipos de distribuição

M Distribuição exponen ial;

E

(k)

Distribuição de Erlang om k fases;

H

(k)

Distribuição hiperexponen ial om k fases;

C

(k)

Distribuição de Cox om k fases;

D Distribuição determinísti a;

G Distribuição geral;

GI Distribuição geral om tempos de intervalos independentes.

134 APÊNDICE A. NOTAÇ�O UTILIZADA

A.1.2 Dis iplinas de atendimento

� FCFS (First Come First Served) - Primeiro a hegar é o primeiro a ser atendido;

� LCFS Preemptive (Last Come First Served) - Último a hegar é atendido, inter-

rompendo o serviço (preempção);

� FCRS (First Come Randomi Served) - O atendimento é rand�mi o.

A.2 Cadeias de Markov

Notação utilizada para representada a es ala de tempo nas Cadeias de Markov.

� CTMC Cadeias de Markov a es ala de tempo ontínua;

� DTMC Cadeias de Markov a es ala de tempo dis reta.

A.3 Redes de Aut�matos Esto ásti os

Notação empregada para representação de eventos sin ronizante pela tripla (id,�,�).

id identi� ador do evento sin ronizante;

� taxa de disparo;

� probabilidade de o orrên ia.

A.4 Redes de Filas de Espera

Notação utilizada para de�nição e índi e de desempenho em QN.

A.4.1 De�nição


A.4. REDES DE FILAS DE ESPERA 135

R Número de diferentes lasses de lientes;

K

i

Capa idade da �la i (número máximo de lientes);

C

i

Número de servidores na �la i;

S

r

i

Tempo médio ne essário para um servidor atender um liente da lasse

r na �la i;

P

r

i;j

Probabilidade de rotação de um liente da lasse r servido na �la i

deixar esta �la e ir para �la j;

B

r

i;j

Pro edimento dos lientes da lasse r saídos da �la i para �la j quando

a �la j está heia;

!

D

i

Vetor indi ando a ordem de prioridade de serviço entre as lasses de

lientes na �la i;

L

r

i

Taxa média de hegada de lientes da lasse r na �la i, oriundos de fora

do modelo;

N

r

População total de lientes da lasse r na rede.

A.4.2 Índi es de Desempenho e Auxiliares

Índi es gerais de desempenho

d

i

Fluxo médio de lientes da �la i;

u

i

Índi e médio geral de utilização da �la i;

n

i

População média geral de lientes na �la i;

w

i

Tempo médio geral de resposta para lientes na �la i.

Índi es de desempenho por lasse de lientes

136 APÊNDICE A. NOTAÇ�O UTILIZADA

d

r

i

Fluxo médio de lientes da lasse r através da �la i;

u

r

i

Índi e médio de utilização da �la i pelos lientes da lasse r;

n

r

i

População média de lientes da lasse r presentes na �la i;

w

r

i

Tempo médio de resposta para os lientes da lasse r na �la i.

Índi e auxiliares

�

r

i

Taxa de visita dos lientes da lasse r na �la i;

�

r

i

(k) Taxa média de atendimento dos lientes da lasse r na �la i quando há

k lientes da lasse r na rede;

d

r

o

Fluxo padrão dos lientes da lasse r;

�

i

(j; N) Probabilidade marginal da �la i om j servidores e N lientes na rede.

Apêndi e B

Regras e Terminais da Gramáti a para

QN

Este apêndi e ontém a des rição e representação dos tokens e das regras utlizadas na

ferramenta MQNA.

B.1 Tokens

Identi� ador Expressão regular

digit [0-9℄

integer {digit}+

�oat {integer}"."{integer}

exponent ({integer}|{�oat})[Ee℄[+-℄?{integer}

id [A-Za-z_℄[A-Za-z0-9_℄*

Tabela B.1: Expressões regulares da gramáti a para MQNA

Token real Representação

id TK_ID

integer TK_INTEGER

�oat TK_FLOAT

exponent TK_EXPONENT

138 APÊNDICE B. REGRAS E TERMINAIS DA GRAMÁTICA PARA QN

Token real Representação ( ontinuação)

qn TK_CQN

oqn TK_OQN

lass TK_CLASS

servers TK_SERVERS

population TK_POPULATION

apa ity TK_CAPACITY

queue TK_QUEUE

network TK_NETWORK

de larations TK_DECLARATIONS

servi e TK_SERVICE

time TK_TIME

arrival TK_ARRIVAL

rate TK_RATE

rot TK_ROT

{ TK_LEFT_BRACKET

} TK_RIGHT_BRACKET

( TK_LEFT_PARENTHESIS

) TK_RIGHT_PARENTHESIS

, TK_COMMA

; TK_SEMICOLON

: TK_COLON

= TK_EQUAL

Tabela B.2: Tokens da gramáti a para MQNA

B.2 Regras da gramáti a

B.2.1 Iní io da Gramáti a

mqna:

TK_CQN TK_ID

TK_LEFT_PARENTHESIS n lass TK_COMMA nfila TK_RIGHT_PARENTHESIS

de laration qn

|TK_OQN TK_ID

TK_LEFT_PARENTHESIS n lass TK_COMMA nfila TK_RIGHT_PARENTHESIS

de laration oqn

B.2. REGRAS DA GRAMÁTICA 139

B.2.2 De larações

de laration:

TK_DECLARATION TK_LEFT_BRACKET

de laration_ lass_queue TK_RIGHT_BRACKET

de laration_ lass_queue:

TK_CLASS TK_ID TK_SEMICOLON de laration_ lass_queue2

|TK_QUEUE TK_ID TK_SEMICOLON de laration_ lass_queue2

de laration_ lass_queue2:

TK_CLASS TK_ID TK_SEMICOLON de laration_ lass_queue2

|TK_QUEUE TK_ID TK_SEMICOLON de laration_ lass_queue2

|

B.2.3 Redes de Filas de Espera Fe hadas

qn:

TK_NETWORK TK_LEFT_BRACKET population queue TK_RIGHT_BRACKET

B.2.4 Redes de Filas de Espera Abertas

oqn:

TK_NETWORK TK_LEFT_BRACKET oqueue TK_RIGHT_BRACKET

B.2.5 Populações

population:

TK_POPULATION TK_CLASS TK_ID TK_EQUAL TK_INTEGER TK_SEMICOLON

population2

population2:

TK_POPULATION TK_CLASS TK_ID TK_EQUAL TK_INTEGER TK_SEMICOLON

population2

|

140 APÊNDICE B. REGRAS E TERMINAIS DA GRAMÁTICA PARA QN

B.2.6 Des rição das Filas

queue:

TK_QUEUE TK_ID TK_LEFT_BRACKET servers apa ity

lass TK_RIGHT_BRACKET queue2

queue2:


lass TK_RIGHT_BRACKET queue2

|

oqueue:


o lass TK_RIGHT_BRACKET oqueue2

oqueue2:


o lass TK_RIGHT_BRACKET oqueue2

|

B.2.7 Parâmetros das Filas

servers:

TK_SERVERS TK_EQUAL TK_INTEGER TK_SEMICOLON

apa ity:

TK_CAPACITY TK_EQUAL TK_INTEGER TK_SEMICOLON

B.2.8 Des rição das Classes

lass:

TK_CLASS TK_ID TK_LEFT_BRACKET serv_time rots

TK_RIGHT_BRACKET lass2

lass2:

TK_CLASS TK_ID TK_LEFT_BRACKET serv_time rots

TK_RIGHT_BRACKET lass2

B.2. REGRAS DA GRAMÁTICA 141

|

o lass:

TK_CLASS TK_ID TK_LEFT_BRACKET serv_time arrival

rots2 TK_RIGHT_BRACKET o lass2

o lass2:

TK_CLASS TK_ID TK_LEFT_BRACKET serv_time arrival

rots2 TK_RIGHT_BRACKET o lass2

|

B.2.9 Parâmetros das Classes

serv_time:

TK_SERVICE TK_TIME TK_EQUAL tnum TK_SEMICOLON

arrival:

TK_ARRIVAL TK_RATE TK_EQUAL tnum TK_SEMICOLON

B.2.10 Parâmetros das Classes

rots:

TK_ROT TK_ID TK_COLON tnum TK_SEMICOLON rots2

rots2:

TK_ROT TK_ID TK_COLON tnum TK_SEMICOLON rots2

|

B.2.11 Auxiliares para Leitura de Números

n lass:

TK_INTEGER

nfila:

TK_INTEGER

tnum:

142APÊNDICE B. REGRAS E TERMINAIS DA GRAMÁTICA PARA QN

TK_INTEGER

|TK_FLOAT

|TK_EXPONENT

Documents

Pontifícia - inf.pucrs.br · Star ek r T. Os tos agradecimen ão v para: Meus pais, Neumar e Nelsi Brenner, p or to do o ap oio dado em to das as ... subsistemas quase indep tes