Aula 16 - FISIOCOMP

Teoria de Filas – Aula 16
Aula Passada
Correção Prova
Little, medidas de
interesse em filas
Aula de hoje
M/M/1
M/M/m
1
Fila M/M/1

K

Chegadas de clientes seguem um processo de
Poisson com taxa λ → tempo entre chegadas é
exponencialmente distribuído com média 1/λ
Tempo de serviço dos clientes são v.as IIDs →
tempo de serviço é exponencialmente distribuído
com média 1/µ
Escalonamento FCFS (first come first service),
com um único servidor
2
Fila M/M/1

K

Exemplos:
Se um cliente representa um job chegando em
um sistema computacional, o servidor
representa o próprio sistema computacional
Um cliente pode ser uma mensagem em um
roteador e o servidor o canal de comunicação
3
Fila M/M/1

K

Seja N(t) o número total de clientes no sistema
(fila + serviço) no tempo t
O processo que representa a fila é o processo
de nascimento-morte (birth-death), com:
λκ = λ k ≥ 0; µκ = µ k ≥ 1
4
Fila M/M/1

K

Recapitulando o processo birth-death...
QUADRO!!!
5

Fila M/M/1
K

Temos que a distribuição de probabilidades, em
estado estacionário, é dada por:
πk = ρ π0
k
π0 = 1
ρ
πk = ρ (1-ρ)
k
ρ < 1 é a intensidade de tráfego (carga, utilização
no caso M/M/1) no sistema → sistema estável
●
Ρ >= 1 → sistema instável
● No caso estável:
●
πk = ρk(1-ρ) k>=0
6
Fila M/M/1 - Medidas

K
Número médio de clientes (serviço + fila):

Ε[N] = ρ/(1− ρ)
Usando Little, o tempo médio de resposta (espera)
do sistema é dado por (fila + serviço)
E[R] = 1/(µ(1− ρ))
Tempo médio de espera na fila
E[W] = ρ/(µ(1− ρ))
Usando Little, o número médio de clientes na fila:
E[Q] = ρ2/(1− ρ)
7
Fila M/M/1 - Medidas

K

Qual a probabilidade do sistema ter mais do que k
clientes na fila?
Tail Probability
P[N > k] = ρk+1
Podemos aproximar um buffer de roteador por
uma fila M/M/1, e definir qual o valor de k para
que tenhamos uma probabilidade pequena de
perda!
8
Fila M/M/1

K

Número
Médio
Clientes
9
Fila M/M/1

K

10
Fila M/M/1
Exercícios

K

A capacidade de um canal de comunicação
wireless é de 20000 bits por segundo. Este canal é
usado para transmitir caracteres com 8 bits, sendo
a taxa máximade caracteres 2500 por segundo. A
aplicação gera um volume total de 120000
caracteres por segundo.
λ ? µ? ρ? E[Q]? E[N]?
11
Fila M/M/1
Exercícios

K

Desejamos determinar a taxa máx de chegadas
que pode ser suportada por um call center.
Assuma que o tempo de duração média da
conversa telefônica é de 3 min e que a espera não
pode ser de mais de 3 min (em média). Qual é a
taxa máxima de chegada de ligações que o sistema
suporta?
12
Fila M/M/m

K

Considere um sistema com taxa de chegada λ
No entanto, o sistema possui m > 1 servidores,
cada um com taxa de serviço µ
Νovamente usamos o processo birth-death:
λk = λ k = 0,1,2,...
µk = kµ 0<k<m
= mµ k>=m
13
Fila M/M/m

K

14
Fila M/M/m

K

15
Fila M/M/m

K

πk = π0(λ/µ)k (1/k!) k < m
πk = π0(λ/µ)k (1/m!mk-m) k ≥ m
π0 = [ Σm-1k=0(mρ)k/k! + (mρ)m/m!(1/1−ρ) ]-1
ρ = λ/(mµ)
16

K
Fila M/M/m - Medidas

Número médio de clientes (serviço + fila):
Ε[N] = mρ +ρ ((mρ) /m!) (π0/(1− ρ ))
m
2
Seja M a v.a que representa o número de
servidores ocupados
P(M = k) = P(N = k) = πk 0≤ k ≤ m-1
= P(N≥m) = πm/(1− ρ) k = m
17

Fila M/M/m - Medidas
K

18
Comparação entre 
diferente tipos de
Sistemas de Fila
K

Vamos considerar a comparação do tempo médio
de resposta vs carga do sistema para 3 sistemas
diferentes:
M/M/1, com taxa de serviço mµ
● M/M/m
● m filas M/M/1 paralelas, com taxa de
serviço µ → cada cliente escolhe uma
fila com a mesma probabilidade
●
19
Comparação entre 
diferente tipos de
Sistemas de Fila
K

Este tipo de pergunta pode ser feito, p.e., em
relação ao seguinte problema:
Considere um sistema computacional com um
processador do tipo X e um conjunto de
usuários que queiram executar um programa
“longo”. Os usuários estão impacientes pq é
necessário esperar um período grande de tempo
para conseguir os resultados. O administrador
do sistema resolve fazer um upgrade do
mesmo. As seguintes opções são possíveis:
20
Comparação entre 
diferente tipos de
Sistemas de Fila
K

Comprar n-1 processadores adicionais do tipo X,
transformando o sistema em multiprocessado
Comprar um novo processador Y, que é n vezes
mais rápido que o processador X e substituí-lo
Comprar uma máquina para cada usuário em
particular, com o processador do tipo X, sem
permitir que um usuário utilize a máquina do
outro usuário
21

Comparação entre diferente tipos
de Sistemas de Fila
K

Considerando taxa de chegada : λ, m = 10, µ = 2
22

Comparação entre diferente tipos
de Sistemas de Fila
K

Por que estes resultados acontecem??
No caso de 10 filas em paralelo, sempre existe uma
probabilidade diferente de zero de ter alguns servidores
com muitos clientes e outros desocupados. No caso do
sistema M/M/10 esta situação não ocorre
Já o servidor robusto M/M/1 é melhor do que o servidor
M/M/10 para cargas leves porque se existem k < 10
clientes no sistema, para a fila M/M/10 a vazão do
sistema é dada por kµ, enquanto para o servidor
robusto todos os clientes são servidos com a taxa
23
máxima de 10µ = 20