Avaliação de Desempenho de Sistemas
Leis Operacionais de Filas
Paulo Adeodato
Departamento de Informática
Universidade Federal de Pernambuco
©2000 Paulo Adeodato
Conteúdo
Introdução
 Lei da utilização
 Lei do fluxo forçado
 Lei de Little
 Lei do tempo de resposta geral
 Lei do tempo de resposta interativo
 Análise de gargalo
 Limitações da Análise

©2000 Paulo Adeodato
Introdução às Leis Operacionais

Idéia básica:
Muitos problemas de filas podem ser resolvidos por relações
simples e gerais que não requerem qualquer suposição a respeito
das distribuições de probabilidade dos processos de chegada e
de atendimento.
Essas relações são chamadas de leis operacionais.
Elas podem ser interpretadas a partir de um modelo do tipo caixapreta.
©2000 Paulo Adeodato
Introdução às Leis Operacionais

Definições/Glossário:
• Operacional: o que pode ser diretamente medido.
• Suposições operacionalmente testáveis: suposições que podem
ser verificadas por meio de medições (equilíbrio do fluxo de
processos x independência estatística numa seqüência de
variáveis).
• Quantidades operacionais: aquelas que podem ser diretamente
medidas durante um período finito de tempo (e. g. número de
chegadas, tempo de utilização etc.)
• Variáveis operacionais: variáveis derivadas das quantidades
operacionais a partir das grandezas operacionais.

Paralelo com grandezas físicas
• É sempre útil fazer uma analogia das quantidades, variáveis e
leis operacionais com grandezas e leis da Física.
• As leis operacionais são relações que se preservam em cada
período de observação
©2000 Paulo Adeodato
Definição de Variáveis Operacionais
número de chegadas Ai
Taxa de chegada i 

tempo
T
número de jobs concluídos Ci
Vazão X i 

tempo
T
tempo ocupado Bi
UtilizaçãoU i 

tempo total
T
tempo ocupado
Bi
Tempo médio de serviçoSi 

número de jobs concluídos Ci
©2000 Paulo Adeodato
Lei de Utilização
Bi Ci Bi
Ui 
 
T
T Ci
 Ui  X i Si
Utilização Vazão Tempo médio de serviço

Exemplo 31.1 revisitado:
O gateway recebe os pacotes a uma taxa de 125 pps e leva em
média 2 milissegundos para processar cada um. Qual a utilização
do gateway?
• Vazão= 125 pps
• Tempo de serviço= 2 x 10-3 s
• Utilização: Ui = Xi x Si = 125 x 2 x 10-3 = 25 %
• Chegamos ao mesmo resultado anterior sem ter sido necessária
qualquer suposição sobre as distribuições de probabilidade.
©2000 Paulo Adeodato
Lei do Fluxo Forçado

Equilíbrio do fluxo de jobs:
• pode ser obtido considerando um tempo suficientemente longo
• de modo a ter válida para cada dispositivo a relação:
Ai  Ci

Considerando as grandezas
Vi  número médio de visitas por job ao dispositivo i
Ci  número de tarefas (visitas) concluídas pelo dispositivo i
C0  número de jobs concluídos pelo sistema

Se o fluxo de jobs é equilibrado temos:
Ci  C0Vi
©2000 Paulo Adeodato
Ci
ou Vi 
C0
Lei do Fluxo Forçado

Sabemos que:
número de jobs concluídos C0
Vazão do sistema X 

tempo
T
Ci
Vazão do dispositiv o X i 
T
Ci Ci C0
 Re-arranjando a equação:
Xi 


T C0 T

Substituindo as duas razões obtemos a Lei do Fluxo
Forçado que é valida na condição de equilíbrio do fluxo
de jobs:
X i  X Vi
©2000 Paulo Adeodato
Lei de Little

Versão anterior:
E[n]   E[r ]

Versão revisitada:
Qi  i Ri
onde:
Qi  número médio de jobs no dispositivo i
i  taxa de chegada ao dispositivo i
Ri  tempo médio de resposta do dispositivo i

Exemplo 33.4:
O tamanho médio das filas do exemplo 33.2 foi medido: 8,88; 3,19 e
1,40 jobs na CPU, no disco A e no disco B, respectivamente. Quais
eram os tempos médios de resposta desses dispositivos?
©2000 Paulo Adeodato
Lei de Little

Do exemplo anterior:
XCPU=35,48

XB=19,60
Dado do exemplo atual:
QCPU=8,88

XA=15,75
QA=3,19
QB=1,40
Assim, pela Lei de Little (Q=XR):
RCPU
RA
RB
= QCPU / XCPU
= QA / XA
= QB / XB
©2000 Paulo Adeodato
= 8,88/35,48 = 0,250 s
= 3,19/ 15,70 = 0,203 s
= 1,40/ 19,60 = 0,071 s
Lei do Tempo de Resposta Geral
Bi Ci Bi
Ui 
 
T
T Ci
 Ui  X i Si
Utilização Vazão Tempo médio de serviço

Exemplo 31.1 revisitado:
O
• É interessante a analogia com o fluxo de água numa mangueira já
cheia de água
©2000 Paulo Adeodato
Lei do Tempo de Resposta Interativo
Bi Ci Bi
Ui 
 
T
T Ci
 Ui  X i Si
Utilização Vazão Tempo médio de serviço

Exemplo 31.1 revisitado:
O
• É interessante a analogia com o fluxo de água numa mangueira já
cheia de água
©2000 Paulo Adeodato
Análise de Gargalo

Combinando a lei da utilização com a Lei do Fluxo
Forçado que é valida na condição de equilíbrio do fluxo
de jobs:
©2000 Paulo Adeodato
Lei do Fluxo Forçado

Exemplo 33.2:
Operacional:
©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 33
©2000 Paulo Adeodato