Aula 6 Teoria de Fila

Prévia do material em texto

Avaliação de Desempenho
Teoria de Fila
 
Teoria de Filas
Representação
 
Teoria de Filas
Notação de Kendall
Representação para os sistemas de filas
A / S / m / B / K / SD
A: Distribuição do Tempo entre chegadas;
S: Distribuição do Tempo de Serviço;
Distribuições mais comuns são:
M(exponencial), Ek (Erlang), Hk (Hiperexponencial), 
D(Determinística), G (Geral), GI (Distribuição genérica 
com tempo entre chegadas independente)
 
Teoria de Filas
Notação de Kendall
A / S / m / B / K / SD
m: Número de Servidores;
B: Capacidade do Sistema
Inclui os clientes em serviço e aqueles aguardando pelo 
serviço
Se não for explicitado é considerada infinita;
K: Tamanho da População
Se não for explicitado é considerada infinita;
 
Teoria de Filas
Notação de Kendall
A / S / m / B / K / SD
SD: Disciplina de Serviço
Comuns:
FIFO,
LCFS, ...
Se não for explicitado é considerada FIFO;
 
Teoria de Filas
Disciplinas de atendimento
 
Teoria de Filas
Notação de Kendall
Exemplo
Descreva o seguinte sistema de fila:
M/M/3/20/1500/FCFS
 
Teoria de Filas
Notação de Kendall
Solução
M/M/3/20/1500/FCFS
1.O tempo entre chegadas sucessivas é exponencialmente 
distribuído (chegada poissoniana)
2.Os tempos de serviço são exponencialmente distribuídos
3.Existem três servidores
4.A fila tem capacidade de armazenamento de 20 clientes; 
3 em serviço e 17 em espera
5.Há um total de 1500 clientes a serem servidos
6.A disciplina de serviço diz que o primeiro a chegar será o 
primeiro a ser atendido.
 
Teoria de Filas
Notação de Kendall
Exemplo
Descreva o seguinte sistema de fila:
D/M/10/50
M/Ek /5/15/270
M/G/∞
 
Teoria de Filas
Regras Gerais
Taxas
A taxa média de chegada é dada por:
λ=1/E[τ];
τ é o tempo entre duas chegadas sucessivas.
A taxa média de partida é dada por:
μ=1/E[s].
s é o tempo de serviço.
 
Teoria de Filas
Regras Gerais
Variáveis aleatórias
ns é o número de clientes em serviço;
nq é o número de clientes esperando por serviço;
n é o número médio de clientes no sistema,
Também chamado de comprimento da fila.
Inclui os clientes em serviço e aqueles que estão 
esperando por serviço;
n=ns +nq E[n]= E[n⇒ s]+E[nq]
 
Teoria de Filas
Regras Gerais
Variáveis aleatórias
s é o tempo de serviço;
w é o tempo de espera por serviço;
r é o tempo de resposta ou tempo no sistema.
Inclui tempo de espera por serviço e o tempo de serviço;
r=s+w E[r]= E[w] + E[s]⇒
Condição de estabilidade
A taxa média de chegada dos clientes deve ser menor 
que a taxa com a qual o sistema os processa ou λ<mμ.
 
Teoria de Filas
Regras Gerais
Lei de Little
Lei de Little ou fórmula de Little diz:
Número médio de clientes no sistema = taxa de 
chegada X tempo médio de resposta
E[n]=λE[t]
Se aplica a qualquer parte do sistema. Assim:
E[nq]=λE[w]
# médio de clientes na fila = taxa de 
chegada X tempo médio de espera
 
Teoria de Filas
Tipos de processo estocásticos
Processo de estado discreto e estado contínuo
Número de processos da fila do escalonador (estado 
discreto)
O tempo de espera por serviço (estado contínuo)
Um processo estocástico a estado discreto é chamado 
de cadeia
 
Teoria de Filas
Tipos de processo estocásticos
Processo de Markov (PM)
Os estados futuros dependem apenas do presente do 
processo.
Propriedade da ausência de memória 
Processo de Nascimento e Morte
São casos particulares de PM onde as transições 
ocorrem apenas entre estados adjacentes
 
Teoria de Filas
Tipos de processo estocásticos
Processo de Poisson
Se os tempos entre as chegadas são variáveis 
aleatórias Independentes e Identicamente Distribuídas 
(IID) - (exponencialmente)
Então, o número de chegadas no intervalo (t, t+x) 
segue uma distribuição de Poisson
Seu uso é comum em teoria de filas devido a 
propriedade da ausência de memória associada a 
distribuição exponencial nos tempos entre chegadas
 
Teoria de Filas
Tipos de processo estocásticos
Processo de Poisson
Propriedades
A soma de k fluxos poissonianos com taxas médias 
λi resultam em um processo de Poisson com taxa 
média de λ:
λ
λ1
λ2
λk
λ=∑
i=1
k
λ i
 
Teoria de Filas
Tipos de processo estocásticos
Processo de Poisson
Propriedades
Se um processo de Poisson é dividido em k fluxos, 
de modo que a probabilidade de um cliente ir para o 
i-ésimo subfluxo é dada por pi, então cada subfluxo 
também é um processo poissoniano com taxa média 
piλ
λ
p1λ
p2λ
pk λ
p1
p2
pk
∑ pi=1
 
Teoria de Filas
Tipos de processo estocásticos
Processo de Poisson
Propriedades
A taxa média de partida de uma fila M/M/1 com taxa 
média de chegada λ, são poissonianas com a 
mesma taxa média.
Recursoλ λ
 
Teoria de Filas
Tipos de processo estocásticos
Processo de Poisson
Propriedades
 A taxa média de partida de uma fila M/M/m com taxa 
média de chegada λ, são poissonianas com a 
mesma taxa média desde que condição de 
estabilidade seja obedecida
1
m
λ<mμλ λ
 
Teoria de Filas
Tipos de processo estocásticos
Relação entre os Processos estocásticos
Processo de Markov
Processo de Nasc. e Morte
Processo de Poisson
Processos
Estocásticos
 
Teoria de Filas
Processo de Nascimento e Morte
Caso especial de um Processo de Markov;
As transições somente ocorrem entre os estados 
adjacentes;
Nascimento:
A chegada de um cliente aumenta a população do 
sistema;
Morte:
A partida de um cliente diminui a população do sistema.
 
Teoria de Filas
Processo de Nascimento e Morte
0 1 2 N-2 N-1 N N+1
λ0 λ1 λN-2 λN-1 λN
μ1 μ2 μN-1 μN μN+1
Estado:
Equilíbrio → Fluxo de entrada = Fluxo de saída
 
Teoria de Filas
Processo de Nascimento e Morte
Estados Fluxo de entrada = Fluxo de saída
0 μ1 p1 = λ0 p0
1 λ0 p0 + μ2 p2 = (λ1 + μ1)p1
2 λ1 p1 + μ3 p3 = (λ2 + μ2)p2
…. ...................
N-1 λN-2 pN-2 + μN pN = (λN-1 + μN-1)pN-1
N λN-1 pN-1 + μN+1 pN+1 = (λN + μN)pN
….. ..................
 
Teoria de Filas
Processo de Nascimento e Morte
Estados:
p1=(λ0/μ1) p0
p2=(λ1/μ2) p1+(μ1 p1−λ0 p0)/μ2
=(λ1/μ2) p1+(μ1 p1−μ1 p1)/μ2
=(λ1/μ2) p1
=(λ1λ0 /μ2μ1)P0
0:
1:
 
Teoria de Filas
Processo de Nascimento e Morte
Estado n-1:
pn=(λn−1/μn) pn−1+(μn−1 pn−1−λn−2 pn−2)/μn
=(λn−1/μn) pn−1+(μn−1 pn−1+μn−1 pn−1)/μn
=(λn−1/μn) pn−1
=(λn−1λn−2…λ0/μnμn−1…μ1)Pn−1
n−1:
pn+1=(λn/μn+1) pn+(μn pn−λn−1 pn−1)/μn+1
=(λn/μn+1) pn
=(λnλn−1…λ0 /μn+1μn…μ1)P0
N−ésimo estado :
 
Teoria de Filas
Processo de Nascimento e Morte
Geral:
pn=p0∏
i=0
n−1 λi
μi+1 , n=1,2,. ..
 
Teoria de Filas
Processo de Nascimento e Morte
 Condição de estabilidade →0<p0≤1
Implica que λi/μi+1<1;
Para que exista o equilíbrio, a taxa média com o 
qual os clientes chegam, deve ser menor que 
aquela com a qual o sistema os processa;
Caso contrário, o sistema é instável.
p0=
1
1+∑
n=1
∞
∏
i=0
n−1 λ i
μi+1
∑
n=0
∞
pn=1
 
Teoria de Filas
Fila M/M/1
Notação de Kendall
A=M → O tempo entre chegadas sucessivas é 
exponencialmente distribuído;
S=M → Os tempos de serviço são 
exponencialmente distribuídos;
m=1 → Um servidor
B → Fila infinita;
K → População infinita;
SD → FIFO.
 
Teoria de Filas
Fila M/M/1
Diagrama de transição de estados
0 1 n n+1
λ λ λ
μ μ μ μ
λ
λn=λ , n=0,1,2,. ..
μn=μ , n=0,1,2,. ..
 
Teoria de Filas
Fila M/M/1
Solução é dada pela aplicação do Processo de 
Nascimento e Morte
pn=p0∏
i=0
n−1 λ i
μi+1=p0∏i=0
n−1
λ
μ=p0 ( λμ )
n
n⩾0
pn=
1
1+∑
n=1
∞
∏
i=0
n−1( λ1μn+1 )
= 1
1+∑
n=1
∞
( λμ )
n
A série somente
converge se ρ<1,
onde ρ = λ/μ
 
Teoria de Filas
Fila M/M/1
Assim, as probabilidades do estado de equilíbrio são 
dadas por:
p0=
1
1+
λ
μ
1−λμ
=1−λμ=1−ρ
ρ é chamado intensidade de tráfego
pn=(1−ρ)ρ
n
 
Teoria de Filas
Fila M/M/1
Número médio de clientes no sistema
E [n ]=∑
n=0
∞
npn=∑
n=0
∞
n(1−ρ) pn
=(1−ρ)∑
n=0
∞
npn=(1−ρ)ρ∑
n=0
∞
npn−1
=ρ
(1−ρ)
(1−ρ)2
= ρ
(1−ρ)
 
Teoria de Filas
Fila M/M/1
Pela lei de Little, 
…pode-se computar
o tempo de resposta...
E [t ]=E [n]λ =
ρ
λ(1−ρ)
= λ
λμ(1−ρ)
= 1
μ(1−ρ)
E [n]=λ E [t ]
 
Teoria de Filas
Fila M/M/m
Notação de Kendall
A=M → O tempo entre chegadas sucessivas é 
exponencialmente distribuído;
S=M → Os tempos de serviço são 
exponencialmente distribuídos;
m=m → m servidores.
 
Teoria de Filas
Fila M/M/m
Diagrama de transição de estados
0 1 2 3
λ λ λ
μ 2μ 3μ
m-2 m-1 m m+1
λ λ λ
(m-1)μ mμ mμ
λn=λ ,n=0,1,2,. .. μn={nμ , n<mmμ , n⩾m
Nota: A taxa de chegada se mantém constante, mas a taxa de serviço 
depende do número de requisições que estão no sistema.
 
Teoria de Filas
Fila M/M/m
Aplicando a solução do processo de Nascimento e 
morte, tem-se as seguintes probabilidades
Onde,
pn={p0(mρ)
n
n!
, n<m
p0
mmρn
m!
, n⩾m
∑
n=0
∞
pn=1
 
Teoria de Filas
Fila M/M/m
A probabilidade de não existir nenhuma requisição no 
sistema é calculada por:
p0=[∑n=0
m−1 (mρ)n
n!
+((mρ)
n
m! )( 11−ρ )]
−1
p0=
1
∑
n=0
m−1 (mρ)n
n!
+( (mρ)
n
m! )( 11−ρ )
OU
 
Teoria de Filas
Fila M/M/m
Dentre as medidas de desempenho está a fórmula de 
Erlang C, empregada na modelagem de sistemas de 
espera.
Probabilidade de ter fila.
P [ fila]=p0( (mρ)
m
m! )( 11−ρ )
 
Teoria de Filas
Fila M/M/m
Onde ρ = λ/mμ é chamado intensidade de tráfego;
Novamente, a condição de existência de equilíbrio é 
ρ<1 ou λ<mμ;
Para que fila M/M/m seja estável, a taxa média com a 
qual os clientes chegam deve ser menor que aquela 
com que os m servidores podem processá-los;
Caso contrário, o sistema é instável.
 
Teoria de Filas
Fila M/M/m/B
Notação de Kendall
A=M → O tempo entre chegadas sucessivas é 
exponencialmente distribuído;
S=M → Os tempos de serviço são exponencialmente 
distribuídos;
m=m → m servidores;
B → capacidade finita.
 
Teoria de Filas
Fila M/M/m/B
A fila M/M/m/B é similar a fila M/M/m exceto que o 
tamanho do buffer B é finito;
Depois que o buffer B encher todas as chegadas 
serão perdidas;
B ≥ m, caso contrário os servidores não serão capaz 
de operar devido a falta de buffer e;
O sistema irá operar efetivamente como fila 
M/M/B/B.
 
Teoria de Filas
Fila M/M/m/B
Diagrama de transição de estados
O sistema pode ser modelado com o processo de nascimento e 
morte usando as seguintes taxas de chegada e serviço.
λn=λ ,n=0,1,2,. .. ,B−1 μn={nμ , n=1,2,. .. ,m−1mμ , n=m,m+1,. .. , B
0 1 2 3
λ λ λ
μ 2μ 3μ
m-1 m B
λ λ
mμ mμ
 
Teoria de Filas
Fila M/M/m/B
Aplicando a solução do processo de Nascimento e 
morte, tem-se
pn={p0(mρ)
n
n!
, 0<n<m
p0
mmρn
m!
, m⩽n⩽B
p0=[1+∑n=0
m−1 (mρ)n
n!
+( (1−ρ
B−m+1)(mρ)m
m!(1−ρ) )]
−1
 
Teoria de Filas
Fila M/M/m/B
Número médio de clientes no sistema e na fila de 
espera
E [n ]=∑
n=1
B
npn
E [nq ]= ∑
n=m+1
B
(n−m) pn
 
Teoria de Filas
Fila M/M/m/B
Taxa de chegada efetiva
Todas as chegadas que ocorrem quando n=B são 
perdidas;
Assim, a taxa de clientes que de fato entram no 
sistema é chamada de taxa de chegada efetiva.
λ '=∑
n=0
B−1
λ pn=λ∑
n=0
B−1
pn
λ '=λ(1−PB)
 
Teoria de Filas
Fila M/M/m/B
Taxa de chegada efetiva
A diferença entre
… representa a taxa de clientes perdidos
λ−λ '=λ PB
 
Teoria de Filas
Fila M/M/m/B
Tempo médio de resposta, pode ser computado 
usando a lei de Little.
Tempo médio de espera
E [r ]= E [n]
λ '
= E [n ]
λ (1−PB) Obs: Note que a lei de Little 
pode agora ser usado pois a 
taxa de chegada é “corrigida” 
para incorporar somente os 
clientes aceitos no sistema
E [w ]=
E [nq]
λ '
=
E [nq]
λ (1−PB)
 
Teoria de Filas
Fila M/M/m/B
Quando B=m a capacidade do sistema são os 
próprios servidores.
Tem-se nesse caso a fórmula de Erlang B.
Que expressa a probabilidade de um cliente 
chegar e ser bloqueado.
P [bloqueio ]=pm=
(mρ)m
m!
p0=
(mρ)m /m!
∑
j=0
m (mρ) j
j !
 
Teoria de Filas
Exercício
Medidas mostram que em um gateway de rede, 
os pacotes chegam com uma taxa média de 
125 pps (pacotes por segundo), e o gateway 
gasta 2 milisegundos para processá-los. Use o 
modelo M/M/1 e analise o gateway. Qual é a 
probabilidade de ocorrer um transbordo no 
buffer se o gateway tem 13 buffers? Quantos 
buffers são necessários para manter a perda 
de pacote abaixo de 1 pacote por milhão.
 
Teoria de Filas
Solução
Taxa média de chegada
λ=125 pps
Tempo médio de serviço
μ =1/0.002 = 500 pps
Utilização do gateway
U=ρ= λ/ μ=0.25
Probabilidade de n pacotes no gateway
pn= (1 - ρ)ρn → pn = 0.75(0.25)n
 
Teoria de Filas
Solução
Número médio de pacotes no gateway
E[n]=ρ/(1- ρ)→E[n]=0.25/0.75→E[n]=0.33
Tempo médio de resposta do gateway
E[r] = (1/μ)/(1- ρ)=(1/500)/(1-0.25)
E[r] = 0.00266 segundos
E[r] = 2.66 milisegundos
 
Solução
Probabilidade de transbordo do buffer
P(ter mais que 13 pacotes no gateway)=ρn=ρ13
1.49x10-8 ≈15 pacotes por bilhão de pacotes
Para a prob. de perda ser menor que 10-6, tem-
se:
ρn ≤ 10-6 ou n>log(10-6)/log(0.25)=9.96
Assim, para a manter a probabilidade de perda 
abaixo de 10-6 são necessários 10 buffers
Teoria de Filas
 
Exemplo
Os estudantes chegam em um centro de 
computação de uma universidade de forma 
poissoniana com uma taxa média de 10 por 
hora. Cada estudante gasta na média 20 
minutos em cada terminal, sendo esse tempo 
distribuído exponencialmente. O centro 
atualmente conta com 5 terminais. Alguns 
estudantes tem reclamado que os tempos de 
espera estão muito longos. Analise tal sistema 
usando o modelo de fila adequado.
Teoria de Filas
 
Solução
O centro é uma fila M/M/5 com taxa média de 
chegada 1/6 minutos e taxa média de serviço de 
1/20 minutos
A intensidade de tráfego
ρ=λ/mμ → 0.167/(5x0.05)
Probabilidade de todos os terminais estarem 
ociosos
p0 =[1+(5X0.67)5/5!(1-0.67)+(5X0.67)1/1!
+(5X0.67)2/2!+(5X0.67)3/3! (5X0.67)4/4!]-1
p0 = 0.0318;
Teoria de Filas
 
Solução
A probabilidade de todos os terminais estarem 
ocupados
ς = p 0 (mρ)m/m!(1- ρ)
ς = 0.0318x(5x0.67)5/5!(1-0.67)=0.33;
Utilização média do terminal
ρ=0.67;
Número médio de estudantes no centro
E[n]=mρ+ρς/(1-ρ)=0.67x0.33/(1-0.67)=4.0
Teoria de Filas
 
Solução
O número médio de estudantes esperando na 
fila
E[nq]=ςρ/(1-ρ)=(0.67x0.33)/(1-0.67)=0.65
O número médio de estudantes usando 
terminal
E[ns]=E[n]-E[nq]=4-0.65=3.35
Teoria de Filas
 
Solução
A média e a variância do tempo gasto no centro de 
serviço:
E[r]=1/μ[1+ ς/m(1- ρ)]=
E[r]= 1/0.05[1+ 0.33/5(1-0.67)]=24
Var[r]=1/μ2 [1+ ς(2- ς)/m2 (1- ρ) 2 ]=
Var[r]= 1/0.052 [1+ 0.33(2- 0.33)/52 (1-0.67)2]
Var[r]=479
Cada estudante gasta, na média, 24 minutos no 
centro. Desses 20 minutos são em serviço, e 4 
são esperando por serviço;
Teoria de Filas
 
Solução
O 90-percentil do tempo de espera é de:
Max{0, E[w]/ςx ln(10ς)}
Max{0, 4/0.33ln(10 x0.33)}=14 minutos;
Assim, 10% dos estudantes tem de esperar 
mais que 14 minutos.
Teoria de FilasExemplo
Os estudantes gostariam de limitar seus 
tempos de espera em, na média, dois minutos 
e não mais que cinco minutos em 90% dos 
casos. Isso é possível? Se positivo, então 
quantos terminais devem são requeridos?
Teoria de Filas
 
Solução
Análise com 6 terminais
λ=0.167 e μ=0.05
Intensidade de tráfego
ρ = 0.167/(6 x0.05)=0.556
Probabilidade de todos terminais estarem ociosos
p0 =0.00346
Probabilidade de todos terminais estarem ocupados
ς =0.15
Tempo médio de espera
E[w]=1.1 minutos
90-percentil do tempo de espera
Max{0, E[w]/ ς x ln(10ς)}
Max{0, 1.1/0.15 ln(10 x 0.15)} = max{0,3}=3 minutos
Assim, com apenas com um terminal a mais é possível 
satisfazer o perfil de atendimento demandado pelos estudantes
Teoria de Filas
 
Notas do capítulo
Ler:
– Capítulo 30 e 31 do Raj Jain (exceto a seção 
3.5)
Teoria de Filas
 
Raj Jain. The art of Computer Systems 
Performance Analysis: technique for 
experimental design, measurement, simulation, 
and modeling, Wiley, 1991.
Bibliografia
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63