Avaliação de Desempenho de Sistemas
Análise de Fila Única
Paulo Adeodato
Departamento de Informática
Universidade Federal de Pernambuco
©2000 Paulo Adeodato
Conteúdo
Processos de Nascimento-Morte
 Análise do Comportamento no Regime Permanente
 Exemplo
 Propriedades de Filas Únicas
 Limitações da Análise

©2000 Paulo Adeodato
Caracterí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)
• w(t)

número de jobs numa CPU no instante de tempo t
tempo de espera na fila no instante de tempo t
Utilizados para representar o estado de sistemas com
filas
©2000 Paulo Adeodato
Tipos de Processos Estocásticos-1
tempo contínuo
espaço contínuo
tempo contínuo
espaço discreto
©2000 Paulo Adeodato
tempo discreto
espaço contínuo
Processos
de Markov
Cadeias
estocásticas
Cadeias de
Markov
tempo discreto
n(t)
espaço discreto
w(t)
Processos 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
©2000 Paulo Adeodato
Análise do Processo de Nascimento-Morte
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.
©2000 Paulo Adeodato
Roteiro de Análise do Processo de
Nascimento-Morte em Regime Permanente
1- Criar o modelo do diagrama de transição de estados de
um processo de nascimento-morte para a fila desejada
0
0
1
1
1
2
j-2
2
2
©2000 Paulo Adeodato
j-1
j-1
3
j-1
j
j
j
j+1
j+1
j+1
j+2
Roteiro de Análise do Processo de
Nascimento-Morte em Regime Permanente
2- 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
lim
t 0
p j (t  t )  p j (t )
t
©2000 Paulo Adeodato

dp j (t )
dt
, j  0,1,2,...n
Roteiro de Análise do Processo de
Nascimento-Morte em Regime Permanente
4- Achar o ponto de equilíbrio (regime permanente, t )
lim
t 
dp j (t )
dt
 0,
j  0,1,2,...n
* 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)
 j  j
 j 1
p j 1 
pj 
p j 1 ,
 j 1
 j 1
0
p1 
p0
1
©2000 Paulo Adeodato
j  1,2,...n
Roteiro de Análise do Processo de
Nascimento-Morte em Regime Permanente
6- Eliminar a recursão
n 1 
01 n1
j
pn 
p0  p0 
,
12 n
j 0  j 1
n  1,2,
* apenas as probabilidades estabilizam; os estados variam
7- Obter a probabilidade do estado j=0 a partir do axioma
de Kolmogorov

p
n 0
©2000 Paulo Adeodato
n
 1  p0 
1
j
1  
n 0 j 0  j 1

n 1
Análise da Fila Única M/M/1
em Regime Permanente
1- Considerar os parâmetros dos processos de chegada e
atendimento da fila independentes do tamanho da mesma
n   , n  0,1,2,...
 n   , n  1,2,3,...

0

1



2

©2000 Paulo Adeodato

j-1



j


j+1


Análise da Fila Única M/M/1
em Regime Permanente
2- Simplificar a expressão da probabilidades associadas a
cada estado no processo de nascimento-morte
 pn   n p0 ,
n  1,2,3,... 
n
p

(
1


)

 

1
1 n
  

  p0 
n  0,1,2,...
2



1      ...


onde  é definida como a intensidade de tráfego.
O somatório só converge se o sistema for estável 
 < 1.
©2000 Paulo Adeodato
Propriedades da Fila Única M/M/1

Utilização (U): probabilidade de haver alguém utilizando o
sistema
U  1  p0  

Tamanho médio da fila (E[n])


E[n]   npn   n(1   ) 
n
n 0
n 1

1 

Variância do tamanho da fila (V[n])

Coeficiente de variação do tamanho da fila (C.V.[n])



2
2
2
2
n
V [n]  E[n ]  E[n]    n (1   )   E[n] 
2
(
1


)
 n1

©2000 Paulo Adeodato

V [n]
C.V .[n] 

E[n]

Propriedades da Fila Única M/M/1

Probabilidade de haver n ou mais jobs na fila


j n
j n
P( N  n)   p j   (1   ) j   n

Tempo médio de resposta (E[r])
Lei de Little: E[n]=  E[r]
 1
1
E[r ] 



1     (1   )
E[n]

F.D.A. do tempo de resposta (F[r]) (fdp exponencial)
 ar
f (r )  ae
r
F (r )   f ( x) dx  1  e
0
©2000 Paulo Adeodato
 ar
E[r ]  

0
1
x f ( x) dx 
a
Propriedades da Fila Única M/M/1

F.D.A. do tempo de resposta (F[r]) (por comparação)
1
1
E[r ] 

 a   (1   )
 (1   ) a
logo:
F (r )  1  e

  (1  ) r
Variância do tempo de resposta (V[r])
1
1
V [r ]  2 
2
a
 (1   )
©2000 Paulo Adeodato
Propriedades 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
©2000 Paulo Adeodato
Análise da Fila Única M/M/m
em Regime Permanente
1- Considerar os parâmetros dos processos de chegada e
atendimento da fila independentes do tamanho da mesma
n   ,
n  0,1,2,...,
n  1,2,3,...m  1
n  m, m  1,...,
 n ,
n  
m ,

0

1


2
2
©2000 Paulo Adeodato


m-1
3
m-1
m

m

m+1
m
m
Análise da Fila Única M/M/m/B
em Regime Permanente
1- Considerar os parâmetros dos processos de chegada e
atendimento da fila independentes do tamanho da mesma
n   ,
n  0,1,2,...,B  1
 n , n  1,2,3,...m  1
n  
m , n  m, m  1,...,B

0

1


2
2
©2000 Paulo Adeodato



m-1 m
3
m-1
m


B
m+1
m
m
m
Análise da Fila Única M/M/m
em Regime Permanente
2- Simplificar a expressão da probabilidades associadas a
cada estado no processo de nascimento-morte
 pn   n p0 ,
n  1,2,3,... 
n
p

(
1


)

 

1
1 n
  

  p0 
n  0,1,2,...
2



1      ...


onde  é definida como a intensidade de tráfego.
O somatório só converge
se o sistema for estável 
n
 pn   p0 ,
n  1,2,3,... 
n
p

(
1


)


<1.  
n
1
1

p 
 

  0
n  0,1,2,...
2



1      ...


©2000 Paulo Adeodato
Propriedades da Fila Única M/M/1

Utilização (U): probabilidade de haver alguém utilizando o
sistema
U  1  p0  

Tamanho médio da fila (E[n])


E[n]   npn   n(1   ) 
n
n 0
n 1

1 

Variância do tamanho da fila (V[n])

Coeficiente de variação do tamanho da fila (C.V.[n])



2
2
2
2
n
V [n]  E[n ]  E[n]    n (1   )   E[n] 
2
(
1


)
 n1

©2000 Paulo Adeodato

V [n]
C.V .[n] 

E[n]

Propriedades da Fila Única M/M/1

Probabilidade de haver n ou mais jobs na fila


j n
j n
P( N  n)   p j   (1   ) j   n

Tempo médio de resposta (E[r])
Lei de Little: E[n]=  E[r]
 1
1
E[r ] 



1     (1   )
E[n]

F.D.A. do tempo de resposta (F[r]) (fdp exponencial)
 ar
f (r )  ae
r
F (r )   f ( x) dx  1  e
0
©2000 Paulo Adeodato
 ar
E[r ]  

0
1
x f ( x) dx 
a
Propriedades da Fila Única M/M/1

F.D.A. do tempo de resposta (F[r]) (por comparação)
1
1
E[r ] 

 a   (1   )
 (1   ) a
logo:
F (r )  1  e

  (1  ) r
Variância do tempo de resposta (V[r])
1
1
V [r ]  2 
2
a
 (1   )
©2000 Paulo Adeodato
Limitações da Análise
©2000 Paulo Adeodato
Referências Bibliográficas

Raj Jain (1991)
The Art of Computer Systems Performance Analysis:
Techniques for Experimental Design, Measurement and
Modeling
John Wiley & Sons
Capítulo 31
©2000 Paulo Adeodato