Aulas 8 & 9
Filas M/G/1
Eytan Modiano
MIT
1
Fila M/G/1
• Taxa de chegada de Poisson λ.
• Tempo de serviço tem distribuição arbitrária com um dado E[X] e
E[X2].
– Tempos de serviço são independentes e identicamente distribuídos
(IID);
– Instantes de chegada independentes;
– E[tempo de serviço] = 1/µ;
– Fila com um único servidor.
2
Pollaczek-Khinchin (P-K)
λE [X 2 ]
W=
2(2 − ρ )
Onde: ρ = λ/µ = λE[X] = utilização.
•
A partir da formula de Little,
NQ = λW
T = E[X] + W
N = λT= NQ + ρ
3
Exemplos M/G/1
• Exemplo 1:
M/M/1 E[X] = 1/µ; E[X2] = 2/µ2
W=
λ
µ (1 − ρ )
2
=
ρ
µ (1 − ρ )
• Exemplo 2: M/D/1 (tempo de serviço constante 1/µ).
E[X] = 1/µ; E[X2] = 1/µ2
W=
λ
2 µ 2 (1 − ρ )
=
ρ
2 µ (1 − ρ )
4
Prova do Pollaczek-Khinchin
• Seja
Wi = tempo de espera na fila da i-ésima chegada.
Ri = Tempo de serviço residual visto por i (ou seja,tempo de serviço
ainda a ser feito para os clientes em serviço).
Ni = Número de clientes encontrados na fila por i.
Wi = Ri +
i −1
j =i − N i
Xj
• E[Wi] = Aqui utilizamos a propriedade PASTA mais a propriedade do
tempo de serviço independente.
• W = R + λW/µ => W = R/(1-ρ).
– Utilizando a formula de Little.
5
O que é R?
(média temporal do tempo de serviço residual)
• Seja M(t) = Número de usuários servidos no instante t.
E[R(t)] = 1/t (soma das áreas nos triângulos)
1
1
Rt = ∫ R(τ )dτ =
t 0
t
• Quando t → infinito
chegada.
M (t )
t
M (t )
i=1
xi2
M (t )
M (t )
i =1
1 M (t )
xi2 = ⋅
2 t
M (t )
i =1
xi2
M (t )
M (t )
= taxa média de saída = taxa média de
t
= E[X2] ⇒ R = λE[X2]/2
6
Fila M/G/1 com férias
• Útil para sistemas de polling e reservas (ex.: token rings).
• Quando a fila é vazia, o servidor toma umas férias.
• Tempos de férias são IID e independentes dos tempos de serviço e de
chegada:
– Se o sistema esta vazio após umas férias, o servidor volta de férias;
– O único impacto na análise é que um pacote chegando a um sistema
vazio deve esperar pelo fim das férias do servidor.
Wi = Ri +
i −1
j =i − N i
Xj
E[Wi] = E[Ri] + E[X]E[Ni] = R + NQ/µ = R/(1-ρ)
7
Serviço Residual Médio
(com férias)
2
t
1
1  M (t ) X i2 L (t ) V j 
R = [ R(t )] = ∫ R(τ )dτ =
+


t0
t  i =1 2
j =1 2

R = lim t →∞
•
•
E[ M (t )] E[ X 2 ] L(t ) E[V 2 ]
+
2
2
t
t
Onde L(t) é o número de ferias pegas até o instante t.
M(t) é o número de clientes servidos no instante t.
8
Tempo de Serviço Médio Residual
(com férias)
• Quando t→∞, M(t)/t → λ e L(t)/t → λv = taxa de férias.
• Agora, seja I = 1 se o sistema está de férias e I = 0 se o sistema estiver
ocupado.
• Pela lei de Little temos:
– E[I] = E[#férias] = P (sistema não ativo) = 1-ρ = λv E[V]
⇒ λv = (1-ρ)/E[V]
Portanto,
E[ X 2 ] (1 − ρ ) E[V 2 ]
R=λ
+
2
2 E[V ]
Lembre W=R/(1-ρ)
E[ X 2 ] E[V 2 ]
W =λ
+
2(1 − ρ ) 2 E[V ]
9
Exemplo: Sistema M/D/1 Fatiados
(divididos em intervalos de tempo)
Cada fatia (cada intervalo de tempo) = tempo de transmissão de um pacote = 1/µ.
• Transmissão pode iniciar somente no início da fatia.
• Se o sistema está vazio no início da fatia, o servidor não está disponível
para a duração da fatia (férias).
λ / µ2 λ / µ
E[X] = E[v] = 1/µ
E[X2] = E[v2] = 1/µ2
1 µ2
1µ
λ µ2
λ µ
W=
+
=
+
2(1 − λ µ ) 2 µ 2( µ − λ ) 2
E[ X ]
= WM / D / 1 +
2
• Observe que em média 1/2 fatia é gasta esperando o início de uma
fatia.
10
Exemplo: FDM
• Suponha m fluxos de Poisson com comprimentos fixo de pacotes e
com taxas de chegada λ/m cada multiplexados pelo FDM. Tráfego total
= λ.
Suponha que demore m unidades de tempo para transmitir um pacote
portanto µ=1/m.
A carga total no sistema: ρ = λ.
• Temos um sistema M/D/1 {W=λ E[x2]/2(1-ρ)}
WFDM
(λ / m) m 2
ρ ⋅m
=
=
2(1 − ρ )
2(1 − ρ )
11
FDM Dividido em Intervalos de Tempo (fatiado)
•
Suponha agora que o sistema é fatiado e a transmissão ocorre somente no
início de uma fatia (que corresponde a m unidades de tempo).
•
Esta é uma fila M/D/1com férias
– O servidor fica de férias durante “m” unidades de tempo quando não há
nada para transmitir.
E[V] = m; E[V2] = m2
WSFDM = WFDM + E[V2]/2E[V]
= WFDM + m/2
12
Exemplo: TDM
• O TDM com uma fatia por pacote tem mesmo comportamento (uma
sessão tem que esperar pela sua própria fatia), portanto:
W = R/(1-ρ)
E[ X 2 ] (1 − ρ ) E[V 2 ]
R=λ
+
2
2 E[V ]
E[ X 2 ] E[V 2 ]
+
W =λ
2(1 − ρ ) 2 E[V ]
13
Exemplo: TDM
• Portanto, WTDM = WFDM + m/2
Adicionando o tempo de transmissão do pacote, resulta que o TDM
é o melhor pois o tempo de transmissão é = 1 em vez m.
TFDM = [WFDM] + m
TSFDM = [WFDM + m/2]+m
TTDM = [WFDM + m/2]+1
= TFDM -[m/2-1]
14