Técnicas de Simulação - DCA | FEECrafael/ia369/tecnicas.pdf · •Embora seja teoricamente bem articulada, esta modelagem pode ser custosa e longa •Por outro lado, algumas estruturas

1Simulação de Sistemas Dinâmicos

6. Técnicas de Simulação

Um programa para simulação (simulador) podeser organizado de muitas maneiras sendo as maisusuais:

Contexto :

•Sistemas dinâmicos a eventos discretos•Simulação enquanto computação numérica

•Orientação a eventos:Exercício estrito de um autômato estocástico; oprogramador deve estabelecer como o estado sealtera com a ocorrência de eventos.

•Orientação a processos:O programador deve identificar no sistema"entidades" que estão submetidas a "processos";em seguida deve descrever as interações entreos processos.

•Orientação ao exame de atividades:O programador deve identificar no sistema as"atividades" e as condições para seu início e término.

Técnicas de Simulação



Orientação a Eventos

Esta abordagem é estritamente baseada no mo-delo autômato estocástico desenvolvido no capí-tulo anterior.

Um autômato temporizado pode ser representa-do por um esquema de escalonamento de eventos

Um autômato estocástico pode ser representa-do por um esquema semelhante, com pequenasmodificações.

O interêsse destas representações é devidoà sua proximidade com a implementação deum programa.



calendário de eventose1 t1e2 t2... ...

estadox

atualiza es-tado:p(x’;x,e’)

atualiza tempo

deleta eventosinfactíveis acrescenta even-

tos habilitadose reoordena.

geração de var. aleatória vi,k

tempot

inicialização

t’

t’x’

x’



Execução do programa:

P1) Remover a primeira linha do calendário;

P2) Atualizar o tempo com o valor t1;

P3) Atualizar o estado de acordo com p(x’;x,e1);

P4) Deletar do calendário as linhas correspondentesa eventos infactíveis no novo estado;

P5) Acrescentar ao calendário os eventos factíveis queainda não estejam escalonados; o tempo associadoao novo evento é obtido adicionando-se ao tempocorrente a um valor sorteado da estrutura de relógio;

P6) Reordenar o calendário por ordem crescente dovalor do tempo em que os eventos foram escalona-dos.



Componentes do programa:

1) Estado: uma lista onde as variáveis do estado são ar-mazenadas;

2) Tempo: uma variável onde o tempo de simulação éarmazenado;

3) Calendário de Eventos: uma lista onde todos os e-ventos escalonados são armazenados juntamente comseu instante de ocorrência;

4) Registros de Dados: variáveis e/ou listas de armaze-namento de dados a serem utilizados em estimações;

5) Rotina de Inicialização: inicializa todas as estruturasde dados descritas, ao início da simulação;

6) Rotina de Atualização do Tempo: identifica o pró-ximo evento a ocorrer e avança o tempo de simulaçãopara o tempo de ocorrência daquele evento;



7) Rotina de Atualização do Estado: Atualiza oestado através de sorteio com base no próximo e-vento;

8) Rotinas de Geração de Variáveis Aleatórias:Geram, a partir de números aleatórios gerados pelocomputador, amostras da variáveis aleatórias asso-ciadas aos tempos de vida dos eventos, de acôrdo com as distribuições definidas a-priori;

9) Rotina de Geração de Relatórios: Calcula es-timações das grandezas de interêsse a partir dosdados coletados na execução de uma simulação;

10) Programa Principal: Responsável pela co-ordenação geral de todos os componentes; chamainicialmente a rotina de inicialização; durante aexecução chama repetidamente as rotinas de atua-lização e atualiza o calendário; termina o programa.



Exemplo:

chegada de clientes partida de clientesfila servidor

Suponhamos que sejam dadas as distribuições de probabi-lidade dos intervalos de chegada e dos tempos de serviçoe se deseja avaliar neste sistema as seguintes medidas dedesempenho:

Tempo de sistema médio:

esperança do tempo de permanência de um cliente nosistema

∑=

=N

1kkN S

N1S

onde Sk é o tempo de permanência no sistemado k-ésimo cliente.

(serão simulados N clientes)



Probabilidade de exceder o "deadline":

D = deadlinenN = número de clientes que excederam o deadline

Nn

P NDN =

Utilização do Servidor:

Probabilidade de o servidor estar ocupado duranteo tempo requerido para atender N clientes, ρN

T(i) = tempo total observado em que o compri-mento da fila é i

∑∞

=

=0i

N )i(TT

NN

N1i

N T)0(T1

T

)i(Tˆ −==ρ

∑ =



Comprimento médio da fila:

pN(i) = probabilidade de que o comprimento dafila seja i, durante o tempo requerido para atenderN clientes

Por definição o comprimento médio é dado por:

∑∞

=

⋅=0i

NN )i(piQ

Tem-se:

NN T

)i(T)i(p =

Portanto:

∑∞

=

⋅=0iN

N )i(TiT1Q



Vai-se supor, para execução do exemplo, que as chegadase serviços obedecem a:

123

1,0

2,0

3,0

4,0

5,0

a 1=0

,4 a 2=0

,7

a 3=1

,1a 4

=2,8

a 5=4

,5 a 6=5

,0

d 1=2

,0d 2=2

,5

d 3=3

,5d 4=3

,8

d 5=5

,3co

mpr

im.

da fi

la

tem

po



As informações relevantes para a simulação são:

tempo estado

0,0 0

lista de eventos escalonados

tipo instante

tempos de chegada12345

tempos de sistema12345

duração-comp.-filaT(0)T(1)T(2)T(3)

nN 0

As informações necessárias para estimar os critérios dedesempenho são:



inicializar:t=0,0estado=0evento(1)=ainstante(1)=sorteion=0

tempos dechegada

n≥N

n=n+1

t=instante(1)e=evento(1)

estado=estado+1 estado=estado−1

deleta 1a linha do calendário

deleta linhas "d" incluir linha "d" se necessário

incluir linha "a" se necessário

reordenar o calendário

atualizar estatísticas

tempos dechegada

e=a

estado=0

tempos deserviço

fim

s

s

n

n

s

n



Orientação a Processos

•A técnica anterior é fundamentada nos autômatos estocásticos

•Embora seja teoricamente bem articulada, esta modelagempode ser custosa e longa

•Por outro lado, algumas estruturas se repetem em muitasaplicações, como é o caso das filas.

•Ocorre portanto que muitos simuladores são organizados em torno das estruturas mais comuns nas aplicações.

•Os conceitos a seguir são utilizados como base para asabordagens deste tipo.

•A tarefa de modelagem, nestes casos, consiste em "montar" o modelo do sistema a partir dos "blocos" pré-programados



Entidade:

•Objeto que requer a execução de alguma ação (serviço).

•Exemplos: peças num sistema de manufatura, jobs numsistema de computadores, pacotes numa rede de comu-nicações.

•Num mesmo sistema podem coexistir vários tipos de en-entidades. Cada tipo será submetido a um processo dife-rente.

Processo:

•Sequência de eventos separados por intervalos de tem-po. Durante cada intervalo de tempo uma entidade es-tará recebendo serviço ou esperando por serviço.

•Um processo pode ser caracterizado por suas funções,como veremos a seguir.

•O Sistema a Eventos Discretos é visto como um con-junto de entidades que se submetem a processos.

Idéia básica:



a) chegada;b) entrada na fila;c) requisição de serviço; se o servidor está livre a entidade

o ocupa; senão fica na fila até o servidor ficar oci-oso;

d) início do serviço, que dura o tempo correspon-dente ao "tempo de serviço";

e) liberação do servidor, quando o serviço termina;f) partida do sistema.

Funções de Processo:

1) Funções Lógicas: ações instantâneas tomadas pelaentidade; por exemplo, os itens a) b) e) f) no exem-plo acima.

2) Funções de Atraso: ações que envolvem a retençãoda entidade por algum período de tempo. Dois tipos:

2.1) Tempo especificado ou Atividade: em geraldeterminado por um gerador de Var. Aleató-rias; exemplo: tempo de serviço.

2.2) Tempo não especificado ou Atraso: determi-nado pelo estado do sistema; exemplo: tempode espera na fila

Exemplo: processo numa fila:



•Atributos: informações que caracterizam individualmen-te uma entidade de algum tipo; por exemplo o instante dechegada de uma peço num sistema de manufatura, desti-no de uma mensagem numa rede de computadores.

•Recursos: objetos que provêem os serviços requisitadospelas entidades; por exemplo máquinas num sistema demanufatura, processadores num sistema de computado-res, chaveadores num sistema de telefonia. As funçõesde processo do tipo "atividade" estão associadas aos re-cursos.

•Filas: conjuntos de entidades esperando pelo mesmo re-curso. Em geral, uma entidade está em alguma fila, a me-nos que esteja sendo servida por um recurso. A funçõesde processo do tipo "atraso" estão associadas às filas.

Outras definições:



O diagrama de tempo abaixo ilustra o conceito deinteração entre processos:

São ainda usuais as terminologias:

atividade = espera incondicionalatraso = espera condicional

final de uma atividade = evento primário(deve ser modelado)

final de um atraso = evento secundário(pode não ser modelado)

Considere-se a fila do exemplo anterior:

tempo

tempo

evento dechegada

evento dechegada

atraso

atraso

atividade

atividade

início deserviço

início deserviço

interação

evento defim de serviço

evento defim de serviço

clienten

clienten+1



Um Simulador Orientado a Processos ou a Interação de Processos é um programa quepermite "construir" processos e definir regrasde interação entre eles.

Portanto a modelagem orientada a processo vê o sistema a eventos discretos sob o ponto de vista das entidades e seu "ciclo-de-vida".

A progamação deste tipo de simulador é feitaatravés de:

•sintaxe adequada ou

•programação visual (arranjo de ícones)

Um simulador orientado a processos deve provercomo facilidades de programação as funções deprocesso mais comuns

Como nos simuladores orientados a eventos, o tempode simulação avança de evento em evento; um calen-dário deve fazer parte do simulador (transparente aomodelador).



Exemplo:

"Drive-in" com dois garçons:

O modelador deve "montar" o processo e atravésdos recursos do simulador deve definir como in-teragem.

gera clientes

fila

serviço A serviço B

saída declientes

A=ociosos n



geraçãode clientes

filapartida de clientes

garçon A

garçon B

lógica deroteamento

A B chave0 0 c0 1 c1 0 b1 1 ×

lógica

circulação de entidades

sinais de controle

chave

c

b

Exemplo: Programação Visual



Orientação ao Exame de Atividades

•O tempo de simulação avança por incrementos fixos,em contraste com as abordagens anteriores;

•A cada avanço de tempo, todas as atividades tem suascondições de início verificadas;

•O modelador deve se concentrar em modelar as condi-ções, simples ou complexas, para o início de cada ati-vidade.

Vantagens:•simplicidade conceitual:

menor esforço de codificação•modelos modulares

facilidade de manutenção, compreensão emodificação (por outros analistas em outromomento)

Desvantagem:•tempo de processamento

Nesta forma básica, seu uso é pouco difundido



Evolução: modelo de três fases

•Fase1: Avançar o tempo de simulação até o instante dopróximo evento primário;

•Fase2: Executar todos o eventos primários;

•Fase3: Verificar as condições de início de todas as ati-vidades e executar os eventos secundários quando fôro caso; repetir até que nenhum evento possa ser exe-cutado.

O programa simulador deve ter um calendário no qualsão incluídos somente os eventos primários

Neste tipo de simulador o início de serviço deve serindependente da chegada de uma entidade

Desse modo uma entidade é sempre colocada numafila, independentemente do status do servidor; os e-ventos de chegada e partida são sempre executáveis.



Exemplo: "Drive-in" comdois garçons:

Inicializar;Gerar chegadas

t=instante(1)e=evento(1)

deleta 1a linha do calendário

n

e=c

e=a

e=b

n=n+1

A=ocioso

B=ocioso

A=ocioso e n>0

B=ocioso e n>0

A=ocupadon=n-1agendar a

B=ocupadon=n-1agendar b

houve início deatividade

s

s

s

s

s

n

n

n

n

s



Processamento de Listas

Em simuladores, listas são utilizadas principalmente em:

•calendários;•entidades e seus atributos;

Usualmente, linguagens de simulação provêem meca-nismos de manipulação, transparentes ao usuário.

Em linguagens de uso geral (alto nível) e mesmo emsimuladores (facultativamente), o programador deveprogramar as operações.

Um registro (record) é uma célula de informaçãonuma lista, podendo ser uma linha de um calendárioou a informação referente a uma entidade.

Um registro é composto de campos.



Registro de uma linha do calendário:

tipo de evento instante atributos suplementares

campos

Registro associado a uma entidade:

identificador atributo1 atributo2 ... atributo n

Em algumas implementações pode haver um campodedicado a um apontador do próximo registro.



Operações típicas em uma lista:

•Remoção de um registro do topo de uma lista•Remoção de um registro de algum ponto da lista•Inclusão de um registro de entidade no topo ou fim da lista

•Inclusão de um registro em um ponto arbitrárioda lista segundo algum critério.

As operações em pontos arbitrários da lista podem en-volver buscas, sendo o principal objetivo das técnicasde processamento de listas torná-las eficientes.

Possibilidades de implementação:

•vetores (arrays)•alocação dinâmica



Vetores (arrays):

Registros ocupam posições contíguas da memória,R(i). Espaço total deve ser pré-especificado.

vantagem: qualquer registro pode ser recuperadosem busca.

desvantagem: inclusão ou exclusão de um registrono meio da lista implica numa grande operação deleitura e re-escrita.

Há duas maneiras de ordenar uma lista implementadavia vetores:

•Segundo a própria posição na memória;•Segundo um apontador contido no próprio registro

A primeira maneira é marcadamente ineficaz.



Exemplo: headptr=3R(1) = [T1; 0,0; 0]R(2) = [T2; 10,0; 4]R(3) = [T3; 5,0; 2]R(4) = [T4; 10,0; 0]R(5) = [T5; 0,0; 0]R(6) = [T6; 0,0; 0]

Remoção do topo da lista:headptr = R(headptr, next)

Alocação Dinâmica:

Cada registro contém um campo com a posição dememória do próximo registro.

A alocação de um espaço na memória é gerenciadapela linguagem de programação ou sistema operaci-onal.



Exemplo:

headptr

[T2; 10,0; ptr2]

[T3; 5,0; ptr1] [T4; 10,0; 0]

Outras implementações:

•dupla ligação (para frente e para trás)•apontador para o meio da lista

Documents

Técnicas de Simulação - DCA | FEECrafael/ia369/tecnicas.pdf · •Embora seja teoricamente bem articulada, esta modelagem pode ser custosa e longa •Por outro lado, algumas estruturas