INF-103: Avaliao de Desempenho Carlos Alberto Kamienski (
[email protected] ) UFABC Teoria das Filas
Slide 2
2 Modelagem analtica Possibilita explorar um modelo sobre o
qual se tem controle Modelos matemticos simplificados geram
resultados rapidamente Tcnica barata: lpis, papel e crebro Muitos
pressupostos e abstraes so feitas Pode-se perder o comportamento
original Exemplo: sistemas de filas
Slide 3
3 Teoria das Filas Prov modelos para prever o comportamento de
sistemas que oferecem servio para demandas com taxas de chegadas
aleatrias Utilizada para modelar sistemas onde: Clientes chegam
para ser atendidos Esperam sua vez de ser atendidos So atendidos e
vo embora Sistema telefnico: A. K. Erlang - 1909
Slide 4
4 Resultados Possveis Tempo de espera de um cliente Quanto
tempo um cliente espera no banco Quanto tempo um pacote passa em um
roteador Acmulo de clientes na fila Qual o tamanho mdio da fila do
banco Como a fila do roteador se comporta Tempo ocioso/ocupado dos
servidores Quanto tempo o caixa fica livre Qual a utilizao do
roteador Taxa de sada (vazo) Quantos clientes so atendidos por hora
Quantos pacotes so encaminhados por segundo
Slide 5
5 Sistemas de Filas
Slide 6
6 Modelo de Filas Bsico Modela qualquer servio com: Um ou mais
servidores Uma rea de espera (buffer) Clientes chegam para receber
um servio Um cliente que no encontra um servidor livre espera na
fila (buffer) Chegadas Sadas BufferServidor(es) Na filaEm
Servio
Slide 7
7 Caractersticas de um Modelo de Filas Processo de chegada
Distribuio do tempo de servio Nmero de servidores Capacidade do
sistema Tamanho da populao Disciplina de servio
Slide 8
8 Processo de Chegada Normalmente um processo estocstico
Necessrio saber a distribuio de probabilidade do tempo entre
chegadas Normalmente Exponencial Processo Estacionrio no varia A
distribuio de probabilidade que descreve a chegada no varia com o
tempo ( independente do tempo) Processo No Estacionrio varia A
distribuio varia com o tempo (depende do tempo)
Slide 9
9 Processo de Chegada tempo decorrido entre as chegadas dos
clientes n e n+1 um processo estocstico Tempos entre chegadas so
identicamente distribudos e tm a mesma mdia Taxa de chegada =
Slide 10
10 Tempo de Servio Tempo que cada cliente leva para ser
atendido Ex: tempo que o cliente do banco passa no caixa Ex: tempo
para o roteador encaminhar um pacote Semelhante ao processo de
chegada Distribuio de probabilidade para o tamanho das filas
depende de: o processo de chegada o tempo de servio
Slide 11
11 Tempo de Servio tempo que o cliente n passa no servidor um
processo estocstico Tempos de servio so identicamente distribudos
com uma mdia comum Taxa de servio:
Slide 12
12 Nmero de Servidores Representa situaes com filas nicas para
mltiplos servidores Exemplos: supermercados, bancos, etc.
Computadores multiprocessados so exemplos de mltiplos servidores Em
redes, freqentemente h somente 1 servidor (um roteador, hub,
switch, etc.) Infinitos servidores tambm so possveis Ex: sistema
onde o cliente tem atendimento imediato Ex: um self service
Slide 13
13 Capacidade do Sistema Em alguns sistemas de filas, existe
limitao fsica da quantidade de espao de buffer Ex: memria de um
roteador Ex: lista de espera de companhias areas Ex: nmero de
cadeiras na sala de espera Se um cliente chega e no h espao no
buffer, ele tem que desistir do servio Ex: o pacote descartado!
(Drop Tail) Freqentemente usa-se capacidade infinita A anlise mais
fcil quando a fila grande
Slide 14
14 Tamanho da Populao Nmero total de clientes que podem entrar
no sistema Ex: pacotes que podem chegar no roteador Quando o nmero
grande (ou desconhecido) mais fcil considerar tamanho infinito
Slide 15
15 Disciplina de Servio Modo como os clientes so selecionados
para receber o servio quando h uma fila Ou seja, em redes, maneira
como os pacotes so retirados da fila para serem transmitidos
Disciplinas comuns: FCFS: First Come, First Served (FIFO) LCFS:
Last Come, First Served (LIFO) Prioridade: Clientes com mais
prioridade primeiro Circular: Um pouquinho de cada tipo (Round
Robin)
Slide 16
16 Notao de Kendall A/S/NS/B/K/SD A,S = Tempo entre chegadas,
tempo de servio M = Exponencial (Markov, Memoryless) Ek = Erlang Hk
= Hyperexponential D = Determinstico G = Geral (para todas as
distribuies) NS = Nmero de servidores B = Nmero de buffers (lugares
na fila) K = Tamanho da populao SD = Disciplina de Servio FCFS,FCLS
Defaults B=, K=, SD=FCFS M/M/1 = M/M/1/ / /FCFS
Slide 17
17 Descrio das filas: Exemplos M/M/1: chegadas Poisson, tempo
de servio exponencial, 1 servidor, buffer infinito, FCFS M/M/m:
Igual ao anterior, com m servidores M/G/1: chegadas Poisson, tempo
de servio geral, 1 servidor, buffer infinito
Slide 18
18 Variveis Gerais = (Lambda) Taxa mdia de chegada = (Tau)
Tempo entre chegadas s = Tempo mdio de servio = (Mi) Taxa de servio
(vazo ou taxa de sada) = 1/s n = Nmero mdio de clientes no sistema
n q = Nmero mdio de clientes na fila n s = Nmero de clientes
recebendo servio W = Tempo mdio de resposta (fila + servio) W q =
Tempo mdio de espera na fila = (R) Carga (ou fator de utilizao) =
s
Slide 19
19 A Chegada e o Comportamento da Fila n=(rea abaixo da
curva)/T t=Tempo n=usurios no sistema 1 2 3 0 t1t1 1 t2t2 2 t4t4 3
t3t3 1 t5t5 4 t6t6 2 t7t7 3 T 4
Slide 20
20 Lei de Little o nmero mdio de elementos no sistema igual
taxa de chegada vezes o tempo de permanncia no sistema n = W Lei de
Little funciona para sistemas no estado estvel n Tempo Total
(fila+servio)= W
Slide 21
21 Lei de Little Exemplo 1 Sistema de Telefonia Taxa de chegada
= 100 chamadas por minuto Durao das chamadas (permanncia): s = 1/ =
2 minutos Nmero mdio de chamadas simultneas n = s = 100 x 2 = 200
chamadas
Slide 22
22 Lei de Little - Exemplo
Slide 23
23 Lei de Little Exemplo 2 Uma Loja no Shopping Taxa de chegada
= 10 usurios por hora Tempo que passa dentro da loja (permanncia):
s = 1/ = 30 minutos = hora Nmero mdio clientes dentro da loja n = s
= 10 x = 5 clientes
Slide 24
24 Lei de Little Exemplo 3 Um roteador Taxa de chegada = 3000
pacotes por segundo Tempo que demora para ser encaminhado (servio):
s = 1/ = 2ms = 0.002 segundo Nmero mdio de pacotes dentro do
roteador n = s = 3000 x 0.002 = 6 pacotes
Slide 25
25 Resultados Gerais para Filas M/M/1 M/M/1 um tipo de fila
muito usada na prtica Probabilidade de haver exatamente n clientes
no sistema: p n = (1 ) n carga do sistema = Probabilidade de haver
n ou mais clientes no sistema: p n = n Nmero mdio de clientes no
sistema: E[n] = (1 ) Tempo mdio de resposta (permanncia no sistema)
W = (1/ / (1 )
Slide 26
26 Filas M/M/1 - Exemplo Dados de um Roteador: Taxa de chegadas
= 400 pacotes por segundo Roteador leva 2 ms para encaminhar
pacotes Calcular usando uma fila M/M/1: Nmero mdio de pacotes na
fila Probabilidade de descarte no caso de haver espao para 10
pacotes Qual a probabilidade de um pacote encontrar a fila vazia?
Quanto espao na fila seria necessrio para que a taxa de perda fosse
inferior a 0,1%?
Slide 27
27 Filas M/M/1 Exemplo 1/2 = 400 pps s = 0.002 s = 1/s =
1/0.002 = 500 pps = / = 0,8 fila Nmero mdio de pacotes na fila:
E[n] = (1 ) = pacotes no sistema (roteador) Assumindo que tem um
pacote sendo servido, temos n q =E[n] -1 = (1 ) 1 = 3 Probabilidade
de descarte (buffer para 10 pacotes): P(mais que 11 pacotes no
roteador) p n = n p 12 = 12 = 12 = 0,0687
Slide 28
28 Filas M/M/1 Exemplo 2/2 Probabilidade de uma fila vazia
P[fila vazia] = P[um ou zero pacote em atendimento] = p n = (1 ) n
P[fila vazia] = (1 - 0.8) 0 + (1 - 0.8) 1 = 0.2 + 0.2*0.8 = 0.36
Buffers para uma perda mxima de 0,01% (0,0001) n < 10 -4 n >
log 10 -4 n > log(10 -4 )/log(0,8) n > 30.95 Resposta:
n>31 buffer para 30 pacotes
Slide 29
29 E se a chegada no for Poisson? Com chegadas Poisson, a
agregao de vrias fontes de trfego suavizada, de acordo com o
Teorema Central do Limite (TCL) Quando os tempos em chegadas seguem
uma distribuio de cauda pesada (ex: Pareto), a convergncia para o
TCL muito mais lenta!
Slide 30
30 Auto-Similaridade Fenmeno de preservar as principais
caractersticas de alguma entidade quando observada em escalas
distintas (de tempo) fractalauto-similar Se a realizao de um
processo estocstico (srie temporal) agregada em escalas de tempo
distintas e mantm suas propriedades estatsticas mais importantes
(ex: momentos de primeira ou segunda ordem), ela considerada um
processo fractal ou auto-similar
Slide 31
31 Auto-Similaridade Existem evidncias de comportamento
auto-similar no trfego de redes de computadores Conseqncia: filas
dos roteadores trabalham com altos nveis de ocupao Pela presena de
trfego em rajadas em vrias escalas de tempo Causando alta taxa de
perda de pacotes e atraso fim a fim Gerando baixo ndice de utilizao
dos enlaces de comunicao Conhecer a fundo esse fenmeno vital para o
gerenciamento de redes e planejamento de capacidade
Slide 32
32 Ocupao das filas
Slide 33
33 Trfego Auto-Similar
Slide 34
34 Trfego Auto-Similar
Slide 35
INF-103: Avaliao de Desempenho Carlos Alberto Kamienski (
[email protected] ) UFABC Teoria das Filas
