©2000 Paulo Adeodato Avaliação de Desempenho de Sistemas Análise de Fila Única Paulo Adeodato Departamento de Informática Universidade Federal de Pernambuco

©2000 Paulo Adeodato

Avaliação de Desempenho de Avaliação de Desempenho de Sistemas Análise de Fila ÚnicaSistemas Análise de Fila Única

Paulo AdeodatoDepartamento de Informática

Universidade Federal de Pernambuco


ConteúdoConteúdo Processos de Nascimento-Morte Análise do Comportamento no Regime Permanente Exemplo Propriedades de Filas Únicas Limitações da Análise


Características da Fila ÚnicaCaracterísticas da Fila Única O sistema mais simples Aplicações:

• CPU única• dispositivos isolados

Processo de nascimento-morte: processo de Markov com a transição de estados limitada aos vizinhos• e.g. n(t+1) {n(t)-1, n(t), n(t)+1}

Seqüências temporais de variáveis aleatórias• n(t) número de jobs numa CPU no instante de tempo t• w(t) tempo de espera na fila no instante de tempo t

Utilizados para representar o estado de sistemas com filas


Tipos de Processos Estocásticos-1Tipos de Processos Estocásticos-1

Cadeias deMarkov

tempo contínuoespaço contínuo

tempo discretoespaço contínuo

tempo contínuoespaço discreto

tempo discretoespaço discreto

Processosde Markov

n(t)n(t)

w(t)w(t)

Cadeiasestocásticas


Processos Estocásticos-2Processos Estocásticos-2 Classificação:

• Tempo: discreto ou contínuo• Estado: discreto ou contínuo• Memória:

com memória Y(t+1)=f [Y(t),Y(t-1),...,Y(t-r+1)] sem memória Y(t+1)=f [Y(t)]

Processo de Markov:• sem memória distribuição exponencial• válido para filas do tipo M/M/m:

n(t) cadeia de Markov w(t) processo de Markov


Análise do Processo de Nascimento-Análise do Processo de Nascimento-Morte em Regime PermanenteMorte em Regime Permanente

Objetivos:• Associar a cada estado n(t) a sua probabilidade de

ocorrência pn e deduzir as demais informações a partir do conhecimento desse espaço de probabilidade.


Roteiro de Análise do Processo de Roteiro de Análise do Processo de Nascimento-Morte em Regime Nascimento-Morte em Regime

PermanentePermanente

0

0

1

1

1

2

2

2

3

j-2

j-1

j-1

j-1

j

j

j

j+1

j+1

j+1

j+2

1- Criar o modelo do diagrama de transição de estados de um processo de nascimento-morte para a fila desejada



PermanentePermanente2- A partir do diagrama de transições de estado, obter as

probabilidades de transição para cada estado no instante (t+t)

3- Rearranjar a equação da probabilidade de transição do estado j para obter a sua taxa de variação ao longo do tempo e tomar o limite t 0

njdt

tdpt

tpttp jjj

t,...2,1,0,

)()()(lim

0




* apenas as probabilidades estabilizam; os estados variam

5- Explicitar a probabilidade do estado j+1 em função dos estados de menor ordem (filas menores)

4- Achar o ponto de equilíbrio (regime permanente, t )

njdt

tdp j

t,...2,1,0 ,0

)(lim

njppp jj

jj

j

jjj ,...2,1 ,1

1

1

11

01

01 pp




* apenas as probabilidades estabilizam; os estados variam

7- Obter a probabilidade do estado j=0 a partir do axioma de Kolmogorov

6- Eliminar a recursão

,2,1 ,1

0 100

21

110

npppn

j j

j

n

nn

0

1

0 1

00 1

1 1

n

n

j j

jnn pp


Análise da Fila Única M/M/1Análise da Fila Única M/M/1em Regime Permanenteem Regime Permanente

1- Considerar os parâmetros dos processos de chegada e atendimento da fila independentes do tamanho da mesma

,...3,2,1 ,,...2,1,0 ,

nn

n

n

0

1

2

j-1

j

j+1


Análise da Fila Única M/M/1Análise da Fila Única M/M/1em Regime Permanenteem Regime Permanente

2- Simplificar a expressão da probabilidades associadas a cada estado no processo de nascimento-morte

,...2,1,0)1(1

...11

,...3,2,1 ,

20

0

np

p

npp nn

nn

onde é definida como a intensidade de tráfego.

O somatório só converge se o sistema for estável < 1.


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 Utilização (U): probabilidade de haver alguém

utilizando o sistema Tamanho médio da fila (E[n])

Variância do tamanho da fila (V[n])

Coeficiente de variação do tamanho da fila (C.V.[n])

01 pU

1)1(][

10

n

nnn nnpnE

22

1

222

)1(][)1(][][][

nEnnEnEnV n

n

][][

].[.nEnV

nVC


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 Probabilidade de haver n ou mais jobs na fila

Tempo médio de resposta (E[r])Lei de Little: E[n]= E[r]

F.D.A. do tempo de resposta (F[r]) (fdp exponencial)

nj

njnjjpnNP

)1()(

)1(11

1][][

nErE

araerf )(

arredxxfrF 1 )()(

0 adxxfxrE 1 )( ][

0


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 F.D.A. do tempo de resposta (F[r]) (por comparação)

)1( 1)1(

1][

aa

rE

rerF )1(1)( logo:

Variância do tempo de resposta (V[r])

22 )1(11][

arV


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 Percentis de ordem q

Tempo médio de espera (E[w])

F.D.A. do tempo de espera (F[w])

Percentis de ordem q


Análise da Fila Única M/M/mAnálise da Fila Única M/M/mem Regime Permanenteem Regime Permanente


,...,1, ,1,...3,2,1 ,

,...,2,1,0 ,

mmnmmnn

n

n

n

0

1

2

2

3

m-1

m-1

m

m

m

m+1

m


Análise da Fila Única M/M/m/BAnálise da Fila Única M/M/m/Bem Regime Permanenteem Regime Permanente


BmmnmmnnBn

n

n

,...,1, ,1,...3,2,1 ,1,...,2,1,0 ,

0

1

2

2

3

m-1

Bm

m

m+1

m

m-1

m

m


Análise da Fila Única M/M/mAnálise da Fila Única M/M/mem Regime Permanenteem Regime Permanente

2- Simplificar a expressão da probabilidades associadas a cada estado no processo de nascimento-morte

,...2,1,0)1(1

...11

,...3,2,1 ,

20

0

np

p

npp nn

nn

onde é definida como a intensidade de tráfego.

O somatório só converge se o sistema for estável < 1.

,...2,1,0)1(1

...11

,...3,2,1 ,

20

0

np

p

npp nn

nn


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 Utilização (U): probabilidade de haver alguém

utilizando o sistema Tamanho médio da fila (E[n])

Variância do tamanho da fila (V[n])

Coeficiente de variação do tamanho da fila (C.V.[n])

01 pU

1)1(][

10

n

nnn nnpnE

22

1

222

)1(][)1(][][][

nEnnEnEnV n

n

][][

].[.nEnV

nVC


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 Probabilidade de haver n ou mais jobs na fila

Tempo médio de resposta (E[r])Lei de Little: E[n]= E[r]

F.D.A. do tempo de resposta (F[r]) (fdp exponencial)

nj

njnjjpnNP

)1()(

)1(11

1][][

nErE

araerf )(

arredxxfrF 1 )()(

0 adxxfxrE 1 )( ][

0


Propriedades da Fila Única M/M/1Propriedades da Fila Única M/M/1 F.D.A. do tempo de resposta (F[r]) (por comparação)

)1( 1)1(

1][

aa

rE

rerF )1(1)( logo:

Variância do tempo de resposta (V[r])

22 )1(11][

arV


Limitações da AnáliseLimitações da Análise


Referências BibliográficasReferências Bibliográficas Raj Jain (1991)

The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement and ModelingJohn Wiley & SonsCapítulo 31

Documents

©2000 Paulo Adeodato Avaliação de Desempenho de Sistemas Análise de Fila Única Paulo Adeodato Departamento de Informática Universidade Federal de Pernambuco