Teoria de Filas

Prévia do material em texto

Teoria de Filas 
 
 
 
“A fila que anda é a outra, mas não adianta 
trocar de fila pois a fila que anda é a outra” 
 Lei de Murphy 
 
 
 
Prof. Marcos Cardoso 
 
 
Teoria de Filas 
 
As filas são a “praga” do mundo atual! 
Espera-se em fila no banco, na portaria, no ponto de ônibus, no trânsito, no restaurante... 
(Mário Meireles Teixeira. Introdução à Teoria das Filas). 
 
As formações de filas ocorrem porque a procura pelo serviço é maior do que a capacidade do sistema de 
atender a esta procura. Os motivos para não se aumentar a capacidade de atendimento dos serviços são: 
a) Inviabilidade econômica 
b) Limitação de espaço. 
A Teoria de Filas tenta por meio de análises matemáticas encontrar um ponto de equilíbrio que satisfaça o 
cliente e seja viável economicamente para o provedor do serviço (evitar desperdícios e minimizar gargalos). 
Operação Chegadas Capacidade de processamento 
Banco Clientes Caixas 
Supermercado Consumidores Caixas para pagamento 
Clínica Pacientes Doutores 
Ligações Telefônicas Chamadas Capacidade da Central 
Rede de Dados Requisições Capacidade da Rede 
Serviços Web Pedidos Capacidade do Servidor 
 
 
 
A Teoria de Filas foi elaborada na Dinamarca em 1908, por A. K. Erlang – 
que estudava o redimensionamento de centrais telefônicas para a 
Companhia Telefônica de Copenhagen. 
Agner Krarup Erlang (01/01/1878 – 03/02/1929). Nasceu na Dinamarca. 
Foi matemático, engenheiro e estatístico. 
 
Agner Krarup Erlang 
 
 
 
 
 
 
 
Características de Filas 
 
 
 
1. Tamanho da População 
Número potencial de clientes que podem chegar ao sistema. 
Um cliente é proveniente de uma população (finita ou infinita). 
Se o tamanho da população for grande é mais fácil analisar o sistema com a hipótese de que a população 
seja infinita. 
2. Processo de Chegadas 
O processo de chegada determina o padrão de chegada dos clientes no sistema. Apresenta comportamento 
estocástico, As chegadas ocorrem de acordo com as leis da probabilidade. Deve-se conhecer a função 
distribuição de probabilidade que descreve os tempos entre as chegadas dos clientes. 
A distribuição mais comum é a de Poisson, ou seja, os tempos entre as chegadas são exponencialmente 
distribuídos. Entre outras distribuições, estão a de Erlang, hiperexponencial e arbitrária. 
Clientes podem chegar simultaneamente (chegada em batch). Se for possível, é necessário também saber a 
distribuição de probabilidade do tamanho do batch. 
 A reação do cliente na fila pode variar. Ele pode esperar independentemente do tamanho da fila, também 
pode decidir não entrar no sistema caso a fila esteja muito grande (cliente decepcionado), ele pode esperar 
na fila mas depois de um tempo desistir e sair do sistema, e também pode mudar de uma fila para outra em 
sistemas com servidores paralelos. 
3. Processo de Atendimento - Servidores 
O processo de atendimento é especificado pelo comportamento do fluxo de usuários atendidos. 
É muito provável que exista uma variação no tempo de atendimento de cada cliente no servidor e por este 
motivo, o tempo de atendimento assim como o tempo de chegada é descrito por uma distribuição de 
probabilidade. 
O estado pode ser independente: o processo de atendimento não depende do número de clientes 
esperando pelo serviço. Em contrapartida, em um estado dependente, o processo de atendimento muda de 
acordo com o número de clientes na fila. Por exemplo, um servidor pode trabalhar mais rápido quando a fila 
aumenta ou, ao contrário, ficar impreciso e então mais lento. 
 
4. Postos de Atendimento/ Servidores 
É o recurso que processa os clientes. Podem ser físicos ou não. 
5. Capacidade do Sistema 
É o número máximo de usuários que o sistema comporta (fila + servidores). Pode ser finita ou infinita. 
Na capacidade finita, quando esta é atingida, os usuários que chegam até o instante da próxima liberação 
são rejeitados. 
Se a capacidade do sistema for grande, é mais fácil analisá-lo com a hipótese de que a fila seja infinita. 
6. Fila 
Representa os clientes que estão esperando pelo serviço, juntamente com os que estão sendo atendidos 
pelos servidores. 
 
7. Fila de espera 
Somente os clientes que estão aguardando pelo serviço 
8. Disciplina das Filas 
É o critério estabelecido pela gerência do sistema, segundo o qual os usuários que se encontram na fila são 
atendidos quando um posto fica disponível. Dentre as disciplinas mais utilizadas, podem-se citar: 
 FIFO (first in – first out): os usuários são atendidos na ordem das chegadas. 
 Ex: Compra de ingressos no cinema 
LIFO (last in – first out): o primeiro usuário a ser atendido é o que chegou por último. 
 Ex: Peças em estoques verticais 
PRI (priority service): o atendimento aos usuários segue uma ou mais prioridades preestabelecidas 
pela gerência do sistema. 
 Ex: Cirurgias Hospitalares 
SIRO (Service in random order): o atendimento aos usuários segue uma ordem aleatória. 
 Ex: Consórcios 
 
Notação de Kendall 
David George Kendall (15/01/1918 – 23/10/2007) was an English statistician and 
mathematician, known for his work on probability, statistical shape analysis, ley 
lines and queueing theory. He spent most of his academic life in the University of 
Oxford (1946–1962) and the University of Cambridge (1962–1985). 
A notação de Kendall é utilizada para descrever sistemas de fila. 
David George Kendall 
A/S/m/B/K/SD 
Símbolo Descrição 
A Distribuição dos intervalos de tempo entre chegadas (processo de chegada) 
S Distribuição dos tempos de serviço 
 M Exponencial (Markov, Memoryless) 
 Em Erlang de estágio m 
 Hm Hyperexponencial 
 D Determinístico 
 G Geral (para todas as distribuições) 
m Quantidade de servidores 
B Capacidade máxima do sistema (número de buffers) 
K Tamanho da população 
SD Disciplina de atendimento da fila 
 
M/D/2/∞/FIFO 
Indica um processo de filas com tempos de chegadas exponenciais (M), tempos de serviço 
determinísticos (D), dois servidores em paralelo (2), capacidade ilimitada e disciplina FIFO. 
Em muitas situações utilizamos apenas os três primeiros símbolos, assumindo assim que o sistema tem 
capacidade ilimitada e possui uma disciplina FIFO. 
 
M/M/3/20/1500/FIFO 
• O intervalo entre chegadas sucessivas é distribuído exponencialmente. 
• Os tempos de serviço são exponencialmente distribuídos. 
• Há três servidores. 
• A fila possui buffers para 20 usuários. 3 usuários em atendimento e 17 esperando por serviço. 
Enquanto o número de usuários estiver em seu valor máximo, 20, todos os usuários que 
chegarem serão perdidos até que o comprimento da fila diminua. 
• A população é finita a 1500 usuários. 
• A disciplina de atendimento é FIFO (first in – first out). 
 
Processo de Markov 
 
Andrei Andreyevich Markov (14/06/1856 —20/07/1922) foi um matemático russo. 
Markov formou-se na Universidade Estatal de São Petersburgo em 1878, onde foi 
professor em 1886. Seus primeiros trabalhos foram limite de integrais, teoria da 
aproximação e a convergência de séries. 
Depois de 1900 aplicou métodos de frações contínuas, que havia sido iniciada por 
Pafnuti Tchebychev na teoria da probabilidade. Provou o teorema do limite 
central. 
Markov é particularmente lembrado pelo seu estudo de cadeias de Markov. 
Cadeias de Markov são um formalismo de modelagem de sistemas que descrevem 
o sistema como um processo estocástico. Deste ponto de vista o sistema 
modelado é caracterizado pelos seus estados e a forma pela qual eles se alternam. 
 
Andrei Andreyevich 
Markov 
 
Markov criou uma maneira simples e útil de descrever a dependência entre v.a. de um processo estocástico. 
Um processo de Markov com um espaço de estados discretos (1, 2, 3,....) é conhecido como Cadeia de 
Markov (tempo discreto ou tempo contínuo). 
Cadeia de Markov de tempo contínuo: O tempo de permanência de um processo em um determinado 
estadopossui distribuição exponencial. 
Processo de Markov é “Sem memória” : Estado futuro depende somente do estado presente. A distribuição 
exponencial é uma distribuição sem memória. 
 
Propriedade de Markov (Sem memória) 
)](/)([])(,...,)(,)(/)([ 11111111 nnnnnnnnn tXXtXPXtXXtXXtXXtXP ++−−++ ====== 
 
Propriedade da Distribuição Exponencial (Sem memória) 
Uma v.a. é dita “Sem memória” se a ][]/[ sXPtXtsXP >=>+> 
][
][
],[
]/[ sXP
tXP
tXtsXP
tXtsXP >=
>
>+>=>+> ou ][][],[ tXPsXPtXtsXP >⋅>=>+> 
Temos: 
( ) tStS eee λλλ −−+− ⋅= única distribuição de v.a. contínua com esta propriedade. 
Seja s = 0: ∫∫ =⋅=−=>−=>
−−
t
X
t
xt dxxfdxeetXPtXP
00
)(1][1][ λλ λ 
x
X exf
λλ −⋅=)( → fdp de uma v.a. com distribuição exponencial. 
Processo de Markov de Tempo Contínuo 
 
É um caso especial Processo de Markov em que as transições do Estado Ek são permitidas somente para os 
Estados vizinhos (Ek →Ek+1). 
Neste processo Ek representa o fato de que a população em certo instante é de tamanho k. 
Uma transição de (Ek →Ek+1) é representada como nascimento. 
Uma transição de (Ek →Ek-1) é representada como morte. 
0 1 ... ...
0λ 1λ 2−kλ 1−kλ kλ 1+kλ
1
µ
2
µ 1−kµ kµ 1+kµ 2+kµ
2
2
λ
3µ
k K+1K-1
 
Quanto à natureza dos nascimentos e mortes define-se: 
λk → taxa de nascimento quando a população é de tamanho k. 
µk → taxa de morte quando a população é de tamanho k. 
Condição: os nascimentos e mortes são eventos independentes 
Birth → população] /),( em nasc. 1 exatamente[1 ktttPB ∆+= 
 )(1 tOtB k ∆+∆= λ 
 população] /),( em nasc. 0 exatamente[2 ktttPB ∆+= 
 )(12 tOtB k ∆+∆−= λ 
Death → população] /),( em morte 1 exatamente[1 ktttPD ∆+= 
 )(1 tOtD k ∆+∆= µ 
 população] /),( em mortes 0 exatamente[2 ktttPD ∆+= 
 )(12 tOtD k ∆+∆−= µ 
Objetivo: determinar as frações de tempo em que o sistema permanece em cada estado 
 
Notação: ])([)( kttXPttPk =∆+≡∆+ 
 
morte 
nascimento 
sem alteração 
Ek 
Ek-1 
Ek+1 
Ek 
t t+∆t 
1,)()()()()()()( ,11,11, ≥∆⋅+∆⋅+∆⋅=∆+ ++−− ktptPtptPtptPttP kkkkkkkkkk 
0,)()()()()()( 0,110,000 =∆+∆⋅++∆⋅=∆+ ktOtptPtptPttP 
temos: 1)(
0
≡∑
∞
=k
k tP , utilizando B1, B2, D1 e D2: 
( ) ( ) ( ) ( ))()()()()(1)(1)()( 1111 tOttPtOttPtOttOttPttP kkkkkkkk ∆+∆⋅+∆+∆⋅+∆+∆−⋅∆+∆−⋅=∆+ ++−− µλµλ
 
( ) ( ) 0,)()()()(1)()( 11000 =∆+∆+∆⋅+∆+∆−⋅=∆+ ktOtOttPtOttPttP µλ 
Expandindo: 
1,)()()()()()()( 1111 ≥∆+⋅∆+⋅∆+⋅∆+−=∆+ ++−− ktOtPttPttPttPttP kkkkkkkkk µλµλ 
0,)()()()()( 110000 =∆+⋅∆+⋅∆−=∆+ ktOtPttPttPttP µλ 
1,
)(
)()()()(
)()(
1111 ≥∆
∆+⋅+⋅+⋅+−=
∆
−∆+
++−− k
t
tO
tPtPtP
t
tPttP
kkkkkkk
kk µλµλ 
0,
)(
)()(
)()(
1100
00 =
∆
∆+⋅+⋅−=
∆
−∆+
k
t
tO
tPtP
t
tPttP µλ 
Fazendo 0→∆t 
1,)()()()(
)(
1111 ≥⋅+⋅+⋅+−= ++−− ktPtPtP
dt
tdP
kkkkkkk
k µλµλ 
0,)()(
)(
1100
0 =⋅+⋅−= ktPtP
dt
tdP µλ 
 
Sistemas de telecomunicações trabalham em regime de estado estacionário. 
Não haverá derivadas em função do tempo: 0
)(
=
dt
tdPk
 
A técnica de Inspeção permite determinar o mesmo sistema de equações. 
0 1 ... ...
0λ 1λ 2−kλ 1−kλ kλ 1+kλ
1
µ
2
µ 1−kµ kµ 1+kµ 2+kµ
2
2
λ
3µ
k K+1K-1
 
 
Equação de equilíbrio de fluxos: Fluxo de Entrada = Fluxo de Saída 
Taxa de entrada no Estado Ek : )()( 1111 tPtP kkkk ++−− ⋅+⋅= µλ 
Taxa de saída do Estado Ek : )()( tPkkk ⋅+ µλ 
1,)()()()(
)(
1111 ≥⋅+⋅+⋅+−= ++−− ktPtPtP
dt
tdP
kkkkkkk
k µλµλ 
Solução Transiente – Pure Birth System 
Considere um sistema em que haja somente nascimentos, ou seja µk =0. 
Ainda, considere λk=λ, para todo k > 0. 
0 1 ... ...
λ λ
2 k k+1k-1
λ λ λ λλ
 
Substituindo as duas condições na Equação Diferencial: 
1,)()(
)(
1 ≥⋅+⋅−= − ktPtP
dt
tdP
kk
k λλ 
0),(
)(
0
0 =⋅−= ktP
dt
tdP λ 
Como condição inicial, vamos supor que: 



≠
=
=
0,0
0,1
)0(
k
k
Pk 
Resolvendo para Po(t), k = 0: 
)(
)(
0
0 tP
dt
tdP ⋅−= λ → tetP ⋅−= λ)(0 
Resolvendo para Po(t), k = 1: 
tetPtPtP
dt
tdP ⋅−⋅+⋅−=⋅+⋅−= λλλλλ )()()()( 1011 → tettP ⋅−⋅⋅= λλ)(1 
Resolvendo por indução para k = 2, 3, ....: 
( ) tk
k e
k
t
tP ⋅−⋅⋅= λλ
!
)( 
Para k ≥ 0, t ≥ 0 
A Distribuição de Poisson é um caso particular do 
Processo de Markov – Pure Birth System. 
Siméon Denis Poisson (21/06/1781 — 25/04/1840) foi um matemático e 
físico francês. 
A distribuição de Poisson foi descoberta por Poisson e publicada, 
conjuntamente com a sua teoria da probabilidade, em 1838 no seu trabalho 
Recherches sur la probabilité des jugements en matières criminelles et 
matière civile ("Inquérito sobre a probabilidade em julgamentos sobre 
matérias criminais e civis"). 
O trabalho focava-se em certas variáveis aleatórias N que contavam, entre 
outras coisas, o número de ocorrências discretas de um certo fenômeno 
durante um intervalo de tempo de determinada duração. 
 
Siméon Denis Poisson 
 
Teorema de Little: 
 
John Dutton Conant Little (February 1, 1928) é Professor no Instituto de 
Tecnologia de Massachusetts. 
A Lei de Little foi apresentada em 1961 por John DC Little num artigo publicado no 
jornal académico "Operations Research". Basicamente é um teorema sobre a 
teoria das "Filas de Espera" (Waiting Line Models). 
A relação "L = W λ" tornou-se conhecida como a lei de Little e ganhou 
popularidade à escala global graças à sua importância teórica e prática 
 L = W . λ 
 Length Waiting Arrival 
 Time Rate 
 
 
John Dutton Conant 
Little 
Considere o sistema: 
 
λ: taxa média de chegada dos pacotes 
t : tempo médio gasto pelo pacote 
E[N]: número médio de pacotes no sistema 
O número médio de pacotes no sistema, definido pela Lei de Little: 
[ ] tNNE ⋅== λ 
 
Exemplo 1. Determine o número médio de clientes que chegam no intervalo [0, t]. 
Seja k o número de chegadas de cliente no intervalo de tempo t. 
[ ] ∑
∞
=
⋅=
0
)(
k
k tPkkE → Valor médio v.a. discreta, k. 
[ ] ( ) ( ) ( ) tt
kk
k
k
t
k
k
t
k
t
k
eet
k
t
et
k
t
ee
k
t
kkE ⋅⋅−
∞
−=
=
⋅−
∞
=
⋅−
∞
=
⋅− ⋅⋅⋅=⋅⋅⋅⋅=
−
⋅⋅=⋅⋅⋅= ∑∑∑ λλλλλ λ
λλλλ
1'
0'
'
00 !')!1(! 
Lembrando, série de Taylor: .....!2/1
2 +++= xxex 
[ ] tkE ⋅= λ → Lei de Little 
Vejamos a variância. Inicialmente, vamos determinar: 
[ ] ∑
∞
=
⋅−⋅=−
0
)()1()1(
k
k tPkkkkE → Valor médio função v.a. discreta, k. 
[ ] ∑
∞
=
⋅=
0
)()()(
k
kkk tPkfkfE 
[ ] ( ) ( ) ( ) ( )∑∑∑
∞
=
−
⋅−
∞
=
⋅−
∞
=
⋅−
−
⋅⋅⋅⋅=⋅⋅−⋅⋅=⋅⋅⋅−⋅=−
2
2
2
00 )!2(!
)1(
!
)1()1(
k
k
t
k
k
t
k
t
k
k
t
et
k
t
kkee
k
t
kkkkE
λλλλ λλλ 
[ ] ( ) ( ) ( ) tt
kk
k
k
t eet
k
t
etkkE ⋅⋅−
∞
−=
=
⋅− ⋅⋅⋅=⋅⋅⋅⋅=− ∑ λλλ λ
λλ 2
2'
0'
'
2
!'
)1(
 
[ ] ( )2)1( tkkE ⋅=− λ 
Temos: [ ] [ ]( )222 XEXEX −=σ 
Hipótese: [ ] [ ] [ ] 22 )()1( kEkEkkEK −+−=σ 
Prova: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 2222222 )()()( kEkEkEkEkEkEkEkEkkEK −=−+−=−+−=σ 
( ) ( ) ttttK ⋅=⋅−⋅+⋅= λλλλσ 222 
Conclusão: Nos Processos de Poisson → Média = Variância = λ.t 
 
Exemplo 2. Considere a rede abaixo. Suponha que o fluxo agregado seja dividido em diferentes enlaces. 
Seja pi probabilidade que um pacote de fluxo agregado seja atribuído ao i-ésimo enlace. Se a taxa de fluxo 
agregado for λ pacotes/segundo e as probabilidades pi forem escolhidas de forma independente, mostre 
que o fluxo no i-ésimo enlace é Poisson com taxa λpi. 
 
 
 
 
Considere um intervalo de tempo de comprimento t, durante o qual N chegadas ocorrem. Vamos contar o 
número de maneiras com que podemos selecionar Ni pacotes dos N que irão para o i-ésimo enlace. 
[ ] [ ] ( ) ii
i
nn
i
n
i
inn
ii pp
n
n
nNPnNP
−
∞
=
−⋅⋅





⋅=== ∑ 1 , NNi < 
[ ] ( ) ( ) ( ) ( ) ii
i
ii
i
nn
i
n
i
iinn
n
tnn
i
n
i
inn
t
n
ii pp
nnn
n
n
t
epp
n
n
e
n
t
nNP
−
∞
=
⋅−−
∞
=
⋅− −⋅⋅
−
⋅⋅⋅=−⋅⋅





⋅⋅⋅== ∑∑ 1
!)!(
!
!
1
!
λλ λλ
 
[ ] ( ) ()[ ]∑
∞
=
−⋅− ⋅−⋅⋅
−
⋅⋅⋅⋅==
i
ii
i
nn
nn
i
i
n
i
n
it
ii tp
nn
t
n
p
enNP 1
)!(
1
!
λλλ 
[ ] ( ) ( ) ( ) tp
i
n
itp
i
n
it
ii
i
i
i
i
e
n
tp
e
n
tp
enNP
⋅⋅−⋅−⋅⋅− ⋅⋅⋅=⋅⋅⋅⋅== λλλ λλ
!!
1
 
O fluxo é Poissoniano com taxa: ip⋅= λλ ' 
λ1 
λ2 
λ3 
. 
λn 
Poisson Poisson Poisson 
 
 
 Router 
λp1 
λp2 
λp3 
. 
λpn 
∑= kλλ
 
 
 Router 
Fila Infinita – Fila M/M/1 
 
Considere um servidor acessível a uma população de clientes muito grande. 
A taxa de chegada das requisições (λ requisições/segundo) não é influenciada pelo número de requisições 
que já chegaram e estão sendo processadas. Este modelo será definido como de população infinita. 
Seja a taxa média de processamento dada por X(k)=µ (pedidos/segundo). Observe que X(k) é definida por 
uma constante, não depende do número de requisições presentes no sistema. 
No modelo, o servidor não recusa quaisquer requisições. Todas são enfileiradas para serviço. Essa suposição 
é denominada fila infinita. 
As requisições chegam ao servidor em uma taxa λ (requisições/segundo), entram em fila para serem 
atendidas, são atendidas em uma taxa µ (requisições/segundo) e saem. 
Devemos calcular: 
a) A fração de tempo, pk, em que existem k (k = 0, 1, 2,...) requisições no servidor 
b) O número médio de requisições presentes no servidor 
c) O tempo de resposta médio de uma requisição no servidor 
d) A utilização do servidor 
e) A taxa de processamento do servidor. 
Os estados possíveis (k = 0, 1, 2,...., k) é um número infinito porém enumerável. 
O Diagrama de Transição de Estados STD, representa cada estado por um círculo. 
As transições entre os estados correspondem a eventos físicos no sistema e são representados por setas 
entre os estados. 
0 1 ... ...
λ λ λ λ λ λ
µ µ µ µ µ µ
2
λ
µ
k K+1K-1
 
A chegada de uma nova requisição quando o servidor se encontra no estado k o levará ao estado k+1. A 
taxa de chegada em que essas transições ocorrem é λ (requisições/segundo). 
Se o servidor possui k requisições e uma delas for concluída, o novo estado é k-1. Essas transições ocorrem 
na taxa µ (requisições/segundo). 
Considere o sistema em equilíbrio operacional: o número de requisições presentes no sistema no início de 
um intervalo de observação é igual ao número de requisições presentes no final do intervalo. Neste caso, o 
fluxo de transições entrando em um estado k precisa ser igual ao fluxo de transições saindo desse estado. 
 
Fluxo de entrada = fluxo de saída 
1
12
01
...
−=
=
=
kk pp
pp
pp
λµ
λµ
λµ
 
Combinando as equações: 
,...2,1,.... 021 =




==




== −− kpppp
k
kkk µ
λ
µ
λ
µ
λ
µ
λ
 
 
Temos pk como função de p0. O servidor deverá estar em um estado possível. Assim, a soma das frações de 
tempo em que o servidor está em qualquer estado possível, de 0 a ∞, é igual a 1: 
 
∑∑
∞
=
∞
=
=




==++++++
0
0
0
3210 1.......
k
k
k
kk ppppppp µ
λ
 
1
0
0
−
∞
= 












= ∑
k
k
p
µ
λ
 
Usando a relação: 1,
)1(0
2
<
−
=×∑
∞
=
U
U
U
Uk
k
k
 
k
kp
p





⋅




 −=
−=
µ
λ
µ
λ
µ
λ
1
10
 
 
A soma infinita á a soma de uma série geométrica. Essa série só converge se λ/µ<1. 
A solução de equilíbrio só poderá ser encontrada se a taxa média de chegada de requisições (λ) for menor 
que a taxa de serviço (µ). 
 
Exemplo 3. 
As requisições chegam ao servidor a uma taxa λ = 30 requisições/segundo. Cada requisição gasta 0,02 
segundos na média para ser processada. Qual é a fração do tempo em que k (k = 0, 1, 2,...) requisições se 
encontram no servidor? 
0 1 ... ...
30=λ
2 k k+1k-1
30=λ 30=λ 30=λ 30=λ30=λ
50=µ 50=µ 50=µ 50=µ 50=µ50=µ
30=λ
50=µ 
Se o servidor pode processar µ requisições/segundo, uma requisição gasta uma média de 1/µ segundos 
para concluir. A taxa de serviço média µ é o inverso do tempo de serviço por requisição. Assim: 
req/seg50
02,0
11 ===µ
st
 
A fração do tempo em que o servidor está ocioso: 
%404,0
50
30
11 00 =→=−=µ
λ−= pp do tempo. 
O servidor é utilizado em: 
%606,04,011 0 =→=−=−= UpU do tempo. 
 
A fração de tempo em que existem k requisições no servidor: 
01866,0
50
30
4,06
03110,0
50
30
4,05
05184,0
50
30
4,04
0864,0
50
30
4,03
144,0
50
30
4,02
24,0
50
30
4,01
66
06
55
05
44
04
33
03
22
02
11
01
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
ppk
ppk
ppk
ppk
ppk
ppk
 
 
Observe: 972,0... 63210 =+++++ ppppp 
 
A utilização do servidor é µλ=−= /1 0pU . Substituindo: 
( ) ( ) 2,..... 1, 0, k para ,1 =⋅−= kk UUp 
A distribuição de estado depende apenas da razão entre as taxas de chegada e de serviço, ou seja da 
Utilização, e não depende de seus valores individuais. 
 
O número médio de requisições no servidor: 
[ ] ( ) ( ) ( ) ( )
( )
[ ] ( )U
U
NkE
U
U
UUkUUUkpkNkE
k
k
k
k
k
k
−
==
−
⋅−=×⋅−=⋅−×=×== ∑∑∑
∞
=
∞
=
∞
=
1
1
111
2
000
 
para o exemplo: [ ] ( ) ( ) servidor. no srequisiçõe5,16,01
6,0
1
=
−
=
−
==
U
U
NkE 
 
A taxa de processamento é µ quando existe pelo menos uma requisição no servidor. Isso ocorre durante 
uma fração de tempo U, e igual a zero quando o servidor está ocioso. A taxa média de processamento, X: 
( ) λ
µ
λµµµ =×=×=−×+×= UUUX 10 
Observe que não há requisições perdidas. 
para o exemplo: s/segundo.requisiçõe30== λX 
 
O tempo médio de resposta do servidor para uma requisição, é obtida pela Lei de Little: 
λµµλµ
λ
λ −
=⋅
−
=⋅
−⋅
=⋅
−
== 11
)1(
11
)1(
1
)1( UUU
U
X
N
R 
 
Quando a utilização é baixa (U→0) o tempo médio de resposta é igual ao tempo médio de serviço de uma 
requisição no servidor (ts = 1/µ). Nenhum tempo é gasto com filas. 
Quando a utilização é alta (U→1), o tempo de resposta R→∞. 
 
Para o exemplo: segundos
X
N
R 05,0
3050
11 =
−
=
λ−µ
== 
 
Se o servidor for duas vezes mais rápido: ./100502 segreq=⋅=µ 
A utilização se torna: 3,0100/30/ === µλU 
O tempo de resposta: segundosR 014,0
30100
11 =
−
=
−
=
λµ 
Se as taxas de chegada e de serviço forem dobradas: 
A utilização se torna: 6,0100/60/ === µλU 
O tempo de resposta: segundosR 025,0
60100
11 =
−
=
−
=
λµ 
Considerações Fila M/M/1 
 
A fila M/M/1 é descrita fazendo os coeficientes de nascimento e morte constantes. 
∞== ,....,2,1,0, kk λλ e ∞== ...,3,2,1, kk µµ 
A capacidade de armazenamento é infinita e a disciplina de atendimento da Fila é FIFO (first in – first out). 
Utilização: )10(/ ≤≤µλ= UU , 01 pU −= 
A fração de tempo em que o sistema permanece em um estado k: 
( ) ( ) 2,..... 1, 0, k para ,1 =⋅−= kk UUp 
 
São utilizados 2 parâmetros para caracterizar uma fila: 
a) O número médio de requisições no sistema: N (na fila + a requisição está sendo atendida) 
∑∑
∞
=
∞
=
⋅⋅−=⋅=
00
)1(
k
k
k
k UkUpkN 
Usando a relação: 1,
)1(0
2
<
−
=×∑
∞
=
U
U
U
Uk
k
k
 
)1( U
U
N
−
= 
De forma similar temos que a variância do número de requisições no sistema, é dada por: 
2
2
)1( U
U
N −
=σ 
b) O numero médio de requisições na fila: Q ( excluindo a requisição que está sendo atendida) 
( )
)1(
1
2
1 U
U
pkQ
k
k −
=⋅−=∑
∞
=
 
( )
2
22
2
1
22
)1(
)1(
1
U
UUU
Qpk
k
kQ −
−−⋅=−⋅−=∑
∞
=
σ 
Tempo médio de Resposta do Sistema: λµµλλ −
=
−⋅
=
−⋅
=== 1
)1(
1
)1( UU
UN
X
N
R 
Tempo médio na fila: 
λ−µ
=
−⋅µ
=
−⋅λ
=
λ
== U
U
U
U
UQ
X
Q
W
)1()1(
2
 
Plotando µR e µW em função da Utilização: 
 
)1(
1
U
R
−
=µ 
)1( U
U
W
−
=µ 
 
Quando a utilização é baixa (U→0): 
 0
/1
→
=µ→
W
tsR
 
Quando a utilização éalta (U→1): 
 
∞→
∞→
W
R
 
 
 
0
2
4
6
8
10
0 0,2 0,4 0,6 0,8 1
 
 
 
 
µR 
µW 
U 
Exemplo 4. 
Determine o número mínimo de servidores para garantir que o tempo de resposta médio não excederá um 
patamar Rmáx. 
 
Seja µ a taxa de processamento de cada servidor, N o número de servidores, λ a taxa de chegada de 
requisições. Supondo balanceamento perfeito de cargas cada servidor recebe λ/N requisições/segundo. 
 
O sistema pode ser modelado como 
um conjunto de N servidores independentes. 
 
 
 
 
 
N/λ µ
 
 
Cada servidor representa uma 
fila M/M/1 com taxa de chegada λ/N. 
Utilizando a Lei de Little, o tempo de resposta médio é determinado por: 
1
/
1
max
max
min
min
max
−⋅
⋅=
−
==
µ
λ
λµ
R
R
N
NX
N
R
 
 
Considerando λ=500 req/s, 
pode-se obter o gráfico do 
número mínimo de 
servidores Nmin em função 
da taxa de processamento, 
µ. Foram considerados 
dois valores para Rmáx 
 
Rmax = 0,4 s 
Rmax = 1 s 
λ = 500 req/ s 
Exemplo 5. Um roteador dedica 80% do tempo no processamento de pacotes de dados. Em media 3,2 
pacotes estão esperando para serem atendidos. Qual é o tempo médio de espera na fila se um pacote tem 
um tempo médio de serviço 1/µ? 
Solução 01: 
ProcessadorBuffer
µ
λ
Wt St
QN SN 
Número de pacotes em serviço: 80,0][80,0]1[ ==→==→ SSSS NNENPN 
Número de pacotes na fila: 2,3][ ==→ QQQ NNN 
Número de pacotes no sistema: SQ NNN += (fila + servidor) 
 
][][ SEWEttR SW +=+= (tempo médio de espera na fila) → ][WE 
 (tempo médio de serviço) → µ= /1][SE 
 
Lei de Little: µλ=⋅λ=∴⋅λ= /][][][ SENEtNE SsS (número médio de pacotes em serviço) 
 2,3][][][ =⋅λ==∴⋅λ= WENEtNE QWQ (número médio de pacotes na fila) 
 
Temos: ][ SNE⋅µ=λ 
 ][][][ WENENE SQ ⋅⋅µ= 
 
µ
⋅=⋅
µ
=⋅
µ
= 14
8,0
2,31
][
][1
][
S
Q
NE
NE
WE 
 
Solução 02: 
Temos: ][][ SEWER += 
Tempo médio de resposta do servidor: 
µ
⋅=
µ
⋅
−
=
µ
⋅
−
= 151
)8,01(
11
)1(
1
U
R 
Tempo médio de serviço → µ= /1][SE 
Tempo médio de espera na fila → 
µ
⋅=
µ
−
µ
⋅= 14115][WE 
Função de Distribuição Condicional – FW(x/n) 
Vamos considerar que uma nova requisição chegue à fila e encontre n requisições no sistema. 
 
O tempo de espera na fila da nova requisição é a soma do tempo remanente R1 da requisição em serviço 
mais o tempo total para servir as (n-1) requisições restantes, ou seja: 
nSSSRW ++++= ....321 
O tempo de serviço remanente também tem distribuição exponencial e média 1/µ. 
O evento que o tempo total para servir as n requisições, W, exceda algum valor de X é equivalente ao 
evento que existam (n-1) ou menos saídas de requisições no intervalo [0, X], ou seja: 
[ ] [ ]x]][0, em saídas menosou 1/ −=> nPnxWP 
[ ] ( )∑
−
=
⋅−⋅⋅=>
1
0 !
/
n
k
x
k
e
k
x
nxWP µ
µ
 
 
Função de distribuição condicional: 
[ ] ( )∑
−
=
⋅−⋅⋅−=≤=
1
0 !
1/)/(
n
k
x
k
W e
k
x
nxWPnxF µ
µ
 
Função distribuição cumulativa: 
)/()(
0
nxFpxF Wn
n
W ⋅=∑
∞
=
 
Solução particular (n=0): 



≤
≥
=
00
01
)0/(
x
x
xFW 
)/()0/()(
1
0 nxFpxFpxF Wn
n
WW ⋅+⋅= ∑
∞
=
 
Considerando: Up −=10 e 
n
n UUp ⋅−= )1( , para x ≥ 0, resulta: 
( )





 ⋅⋅−⋅⋅−+−= ∑∑
−
=
⋅−
∞
=
1
01 !
1)1()1()(
n
k
k
xn
n
W
k
x
eUUUxF
µµ
 
0 X t 
Intervalo de tempo (x) 
Se requisições na fila>1 
Ainda não foi atendido n requisições 
na fila 
P [W >x /n] 
Resolvendo: (A equação foi resolvida e calculada) 
01)( )1( ≥⋅−= ⋅−⋅− xeUxF xUW
µ
 Função distribuição 
0)( )1( ≥⋅= ⋅−⋅− xeUxF xUCW
µ
, Função distribuição complementar: )(1)( xFxF W
C
W −= 
 [ ] 0)( )1( ≥⋅=>= ⋅−⋅− xeUxWPxF xUCW µ 
Exemplo 6. 
Determine E[R], o valor esperado do tempo de resposta do sistema. 
SWR += → Tempo Total = Tempo de espera na fila + Tempo de serviço. 
 W e S são v.a. → R é uma v.a. com distribuição exponencial. 
Teorema 5.5. Quando R e S são v.a. independentes a fdp de R = W+S: ∫
∞
∞−
⋅−= dyyfyxfxf SWR )()()( 
Para a Função distribuição cumulativa, temos: ∫
∞
∞−
⋅−= dyyFyxFxF SWR )()()( 
Substituindo:
xU
W eUxF
⋅−⋅µ−⋅−= )1(1)( , e 0)( ≥⋅µ= ⋅⋅µ− xexF xS 
∫∫
∞
⋅−−⋅−⋅−
∞
⋅⋅⋅−=⋅−=
0
)()1(
0
)1()()()( dyeeUdyyFyxFxF yyxUSWR
µµ µ 
xU
R exF
⋅−⋅−−= )1(1)( µ 
O valor esperado da v.a. R: 
( )UdxxFRE
C
R −⋅
=⋅= ∫
∞
1
1
)(][
0
µ 
Valor médio do tempo de resposta do sistema. 
Tempo de fila + tempo de serviço. 
O tempo total para que uma requisição seja atendida. 
 
Observação: Considere W uma variável aleatória com distribuição exponencial: 
x
W exF
λ−⋅λ−=1)( , para 00 ≥λ≥x Função distribuição cumulativa 
 
x
W exf
λ−⋅λ=)( , para 00 ≥λ≥x Função densidade de probabilidade 
 
O valor esperado da v.a.W com distribuição exponencial: 
 λ
λ λ 1)(][
00
∫∫
∞
−
∞
=⋅⋅⋅=⋅⋅= dxexdxxfxWE xW 
Propriedade: ∫
∞
⋅=
0
)(][ dxxFWE
C
W 
 Prova: 
λ
=⋅=⋅−=⋅= ∫∫ ∫
∞
λ−
∞ ∞
1
)(1)(][
00 0
dxedxxFdxxFWE xW
C
W 
Exemplo 7. Um barbeiro abre seu negócio em t = 0. Seus clientes chegam aleatoriamente de acordo com 
uma distribuição de Poison, ou seja a fdp do tempo entre as chegadas é .)(
t
A etf
⋅λ−⋅λ= Cada corte de 
cabelo demora X segundos. Determine a probabilidade que um segundo cliente ao chegar não precise 
esperar para ser atendido, e o valor médio W do tempo de espera para os seguintes casos: 
a) X = c, é uma constante. 
A probabilidade que o segundo cliente não tenha que esperar é a probabilidade que o tempo entre 
chegadas seja ≥ c: 
 
∫
∞
⋅=
c
A dttfP )(]esperar Não[ 
c
c
t edteP ⋅−
∞
⋅− =⋅⋅= ∫
λλλ]esperar Não[ 
 
 
 
Caso o cliente chegue antes do término do corte, deverá aguardar na fila: 
 cy ≤ tempo de espera W: yc − 
Y – chegada do cliente 
C – término do corte do cliente anterior 
 
 
 y C t 
 
O valor médio W do tempo de espera: 
∫ ⋅⋅⋅−=
⋅−
C
y dyeycW
0
)( λλ → valor médio da função (c-y) : ∫ ⋅⋅= dxxfxgxgE X )()()]([ 
( )CecW ⋅−−⋅




−= λ
λ
1
1
 
b) X é uma v.a. exponencialmente distribuída com fdp: .)(
t
X etf
⋅µ−⋅µ= 
dx (x)fx]serviço de tempo/serviço de tempochegadas entre P[tempo]esperar Não[ X⋅=≥= ∫
∞
c
P 
Retirando o condicionamento da v.a. x: fdp(x) 
µλ
µµλ µλ
+
=⋅⋅⋅= ∫
∞
⋅−⋅−
0
]esperar Não[ dxeeP xx 
O tempo médio de espera W: Substituindo a constante c por x, e retirando o condicionamento de x: 
( ) ( )λµµ
λµ
λ
µλ
+⋅
=⋅⋅⋅




 −⋅




−= ∫
∞
⋅−⋅−
0
1
1
dxeexW xx 
 Subst. cte c por x ret. o condicionamento de x 
t
A etf
⋅−⋅= λλ)(
área 
C t 
a(t) 
Exemplo 8. Uma estação rádio-base recebe o fluxo originado por N 
usuários dentro de uma célula. 
Os usuários geram tráfego Poissoniano e cada um transmite com 
taxa λ pacotes/seg. A ERB possui um buffer para armazenar os 
dados, e os transmite para o servidor com taxa µ pacotes/seg. 
Qual o valor de N para que o tempo médio de espera na fila não 
seja maior que t com probabilidade de 90%? 
%90][ =≤ tWP → %90)()(
0
=⋅= ∫
∞
dttftF WW 
0)1()(
)1( ≥⋅−= ⋅−⋅− teUtF tUW
µ
 Função distribuição condicional 
9,0)1()(
)1( =⋅−= ⋅−⋅− tUW eUtF
µ
 
tUe
N
U ⋅−⋅⋅=⋅= )1(1,0 µ
µ
λ
 
tUeN ⋅−⋅⋅⋅= )1(1,0µ
λ
µ
 
λ1 
λ2 
λn 
µ 
buffer 
N.λ 
Server 
 
Teoria de Fila Finita – Fila M/M/W 
Considere que o servidor não pode enfileirar todas as requisições recebidas. As requisições que chegam e 
encontram W requisições presentes no servidor – enfileiradas ou sendo processadas – são rejeitadas. 
 
 
O número de requisições é limitado, 
pois cada requisição consome recursos 
do sistema, como espaço nas tabelas 
de roteamento. 
 
Como o servidor recusa quaisquer requisições adicionais quando existem W requisições no sistema, os 
estados possíveis são: 
K = 0, 1, 2,...,k,...,W. 
0 1 ... ... W-1
λ λλ λ λ λ λ
µ µµ µ µ µ µ
2
λ
µ
k K+1K-1 W
λ
µ 
 
Uma requisição que chega e encontra k (k<W) requisições no sistema, causa uma transição para o estado 
k+1 na taxa λ. Uma requisição sendo completada no estado k, causa uma transição para o estado k-1 na 
taxa µ. 
Temos: .,....2,1, Wkpp
k
ok =




⋅=
µ
λ
 
A diferença está no cálculo de p0. Agora temos um número finito de estados: 
10
0
1
00
0
3210
1
1
1
1
1
...
+
∞
=
+
=





−
−
=
=
−





−
⋅=




==+++++ ∑∑
W
k
W
k
W
k
kW
p
pppppppp
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
 
A utilização do servidor é a fração de tempo em que o servidor não está ocioso. Assim: 
10
1
1
1 +





−





−
⋅




=−=
W
W
pU
µ
λ
µ
λ
µ
λ
 
 
Em um servidor com fila finita, as equações são perdidas quando o 
sistema está no estado W. Assim: 
Wperda pP = 
Buffer
Overflow
 
 
O número médio de requisições no servidor: 
[ ]
k
W
k
W
k
k kppkNkE ∑∑
==





×⋅=×==
0
0
0 µ
λ
 
Utilizando: 
2
12
0 )1(
)1(
a
aaWaW
ak
WWW
k
k
−
++−⋅=×
++
=
∑ 
Combinando com o valor de p0: 
[ ] ))/(1()/(1
1)/()1()/(
)/(
1
1
µλµλ
µλµλµλ
−⋅−
+⋅+−⋅⋅⋅= +
+
W
WW WW
N 
 
A taxa de processamento X do servidor é igual a µ quando o servidor estiver ocupado e, igual a zero caso 
contrário. A fração de tempo em que o servidor está ocupado é a sua utilização: 
( )
1)/(1
)/(1
10 +−
−⋅=×=×=−×+×=
W
W
UUUX
µλ
µλλ
µ
λµµµ 
 
O tempo de resposta médio R, é obtido pela Lei de Little: 
( ) ))/(1()/(1
1)/()1()/(1 1
µλµλ
µλµλ
µ −⋅−
+⋅+−⋅⋅==
+
W
WW WW
X
N
R 
Exemplo 9. 
Considere o servidor do exemplo 3, as requisições chegam ao servidor a uma taxa λ = 30 
requisições/segundo. Cada requisição gasta 0,02 segundos na média para ser processada. Entretanto, no 
máximo 6 requisições podem ser enfileiradas no servidor – incluindo as requisições sendo processadas. 
Qual a fração de tempo em que k (k = 0, 1, 2,..., W) requisições se encontram no servidor? 
Temos: reqWsegreqsegreq 6./50./30 ==µ=λ 
0 1
30=λ
2 5 64
30=λ 30=λ 30=λ30=λ
50=µ 50=µ 50=µ 50=µ50=µ
30=λ
50=µ
3
 
 
4115,0
50
30
1
50
30
1
1
1
1610
=





−
−
=





−
−
= ++Wp
µ
λ
µ
λ
 
5885,04115,011 0 =−=−= pU O servidor está em uso em 58,85% do tempo. 
0192,0
50
30
4115,06
0320,0
50
30
4115,05
05333,0
50
30
4115,04
0888,0
50
30
4115,03
1482,0
50
30
4115,02
2469,0
50
30
4115,01
66
06
55
05
44
04
33
03
22
02
11
01
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
=




⋅=





µ
λ⋅=→=
ppk
ppk
ppk
ppk
ppk
ppk
 
 
Observe: 1... 63210 =+++++ ppppp 
Probabilidade de perdas = 0,0192 - Serão perdidas 1,92% das requisições. 
O número médio de requisições no servidor: 
[ ]
srequisicoe
kppkNkE
k
W
k
W
k
k
2984,11551,34115,0
50
30
6
50
30
5
50
30
4
50
30
3
50
30
2
50
30
14115,0
654321
0
0
0
=⋅=













⋅+




⋅+




⋅+




⋅+




⋅+




⋅⋅=






µ
λ×⋅=×== ∑∑
==
 
utilizando a equação: 
[ ]
[ ] srequisicoe
WW
N
W
WW
2984,1
))50/30(1()50/30(1
1)50/30()16()50/30(6
)50/30(
))/(1()/(1
1)/()1()/(
)/(
16
616
1
1
=
−⋅−
+⋅+−⋅⋅=
−⋅−
+⋅+−⋅⋅⋅=
+
+
+
+
µλµλ
µλµλµλ
 
A taxa de processamento X do servidor 
( )
segreqX
UUUX
W
W
/424,29
)50/30(1
)50/30(1
30
)/(1
)/(1
10
16
6
1
=
−
−
⋅=
−
−
⋅=×=×=−×+×=
+
+µλ
µλλ
µ
λµµµ
 
Observe: 
( )
( ) segreqX
pX W
/424,290192,0130
1
=−⋅=
−⋅λ=
 
O tempo de resposta médio R, é obtido pela Lei de Little: 
( ) ( ) seg
WW
X
N
R
W
WW
044127,0
))50/30(1()50/30(1
1)50/30()16()50/30(6
50
1
))/(1()/(1
1)/()1()/(1
6
6161
=
−⋅−
+⋅+−⋅⋅=
−⋅−
+⋅+−⋅⋅==
++
µλµλ
µλµλ
µ
 
 
Exemplo 10. 
Considere o Exemplo 9. Qual deve ser o valor mínimo para o número máximo de requisições aceitas, para 
que menos de 1% das requisições sejam rejeitadas? 
Queremos calcular o valor de W para: 01,00 <




=
W
W pp µ
λ
 
( ) ( ) ( )
( )
aceitassrequisicoeW
W
W
p
W
WW
WW
WWW
W
WW
8
25,7
)024631,0log()6,0log(
01,06,0406,0
01,06,06,099,06,0
01,099,0
01,001,0
01,0
1
1
min
1
11
1
=
>
<⋅
<⋅
<⋅⋅−
<




⋅−










⋅−<




−





<




⋅





−
−
=
+
++
+
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
 
 
 
Exemplo 11. 
Um site de busca com N servidores recebe 500 req/s. A taxa de chegada em cada servidor é λ=500/N req/s. 
Os servidores foram analisados com benchmarks e mostrou capacidade de processar 20 req/s na média. 
Cada servidor pode processar 200 conexões simultaneamente, após este ponto serão rejeitadas. 
Quantos servidores são necessários para oferecer um tempo de resposta médio que não exceda 2segundos 
e uma probabilidade de rejeição abaixo de 5 %. 
( ) ( ) 05,0/25/251
/251
/25
20
/500
05,0
1
1
200
201
1
<⋅
−
−=
==
<





⋅





−
−
= +
N
N
N
p
N
N
p
W
W
WW
µ
λ
µ
λ
µ
λ
µ
λ
 
 
( )
( ) 2))/25(1()/25(1
1)/25()201()/25(200
20
1
2
))/(1()/(1
1)/()1()/(1
200
200201
1
<
−⋅−
+⋅−⋅⋅=
<
−⋅−
+⋅+−⋅⋅=
+
NN
NN
R
WW
R
W
WW
µλµλ
µλµλ
µ
 
 
 
A forma da curva do tempo de resposta é bastante típica de sistemas com filas finitas. A mudança básica 
ocorre quando a utilização atinge 100%. Nesse ponto, a taxa de processamento de cada servidor atinge seu 
valor máximo, µ, e a taxa de processamento torna-se constante e igual a Nxµ. 
 
 
 
 
 
 
Exemplo 12. 
Um site de busca precisa manter atualizado seu Banco de Dados de páginas Web. São utilizados agentes que 
trazem novas páginas para serem indexadas ou atualizadas. O serviço de indexação é capaz de indexar uma 
página/s e possui um buffer finito que pode armazenar, no máximo, 15 páginas. O número de agentes é 
fixo, e cada um traz uma nova página a uma taxa de 0,1 páginas/s. Qual deve ser o número de agentes? 
À medida que o número de agentes aumenta mais páginas trazidas por eles são perdidas devido ao estouro 
do buffer. Para um número decrescente, o serviço de indexação ficará ocioso. 
Se o número de agentes for N e cada um gerar páginas a serem indexadas a 0,1 páginas/s, a taxa de 
chegada total λ = 0,1 N pag/s. A taxa de serviço é constante µ=1 pag/s e a fila é limitada a W=15 páginas. 
Os gráficos de po e pw em função do número de agentes. 
( )160
10
1,01
1,01
1
1
N
N
p
p
W
−
−=






−
−
= +
µ
λ
µ
λ
 
( )
( )15
16
1
1,0
1,01
1,01
1
1
N
N
N
p
p
W
W
WW
⋅
−
−=





⋅





−
−
= + µ
λ
µ
λ
µ
λ
 
p0 = pw = 6,25% 
Taxa de indexação máxima: 93,75 % 
 
Modelos generalizados em nível de sistema 
A taxa de chegada, λk, e a taxa de serviço, µk, podem depender do estado do sistema, k. Em geral podemos 
ter estados infinitos: 
0 1 ... ...
0λ 1λ 2−kλ 1−kλ kλ 1+kλ
1
µ
2
µ 1−kµ kµ 1+kµ 2+kµ
2
2
λ
3µ
k K+1K-1
 
Aplicando o princípio do equilíbrio operacional, o fluxo de transições para um estado k precisa ser igual ao 
fluxo de transições saindo desse estado. 
Fluxo de entrada = fluxo de saída 
∏
−
= +
−
−
−−−
⋅=
⋅⋅⋅==
⋅==
=
==
1
0 1
0
0
1
0
2
11
1
1
0
1
0
2
1
1
2
1
2
0
1
0
1
11
.....
...
....3,2,1
k
i i
i
k
k
k
k
k
k
k
kkkk
pp
ppp
ppp
pp
kpp
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µ
λ
µλ
 
A soma das frações de tempo em que o servidor está em qualquer estado possível, pk, de 0 a ∞, é igual a 1: 
1
0
1
0 1
0
0
1
0 1
0
0
1
−∞
=
−
= +
∞
=
−
= +
∞
=






⋅=
=⋅=
∑ ∏
∑ ∏∑
k
k
i i
i
k
k
i i
i
k
k
p
pp
µ
λ
µ
λ
 
 
 
Dado a estrutura generalizada, podemos considerar muitas alternativas possíveis ao modelar sistemas. 
Consideremos apenas três dimensões para o problema: 
1. Tamanho da População – Infinita e Finita com M clientes. 
2. Taxa de Serviço do Servidor – Fixa X(k)=µ e Variável X(k)=µk. 
3. Tamanho Máximo da Fila – Infinito e Limitado (W requisições). 
 
 
 
 
 
 
Modelos de População Infinita 
 
1. Taxa de Serviço Variável e Fila Infinita 
A taxa de processamento do servidor é normalmente função do número de requisições presentes no 
sistema. 
 
Com cargas pequenas, as requisições apresentam pouco congestionamento nas filas internas. 
Com cargas intensas o congestionamento começa a ser acumular e a taxa de processamento aumenta em 
uma taxa muito menor até que sature, atingindo seu valor máximo. 
 
As expressões para λk e µk são: 
,.....3,2,1)(
,....2,1,0
==
==
kkX
k
k
k
µ
λλ
 
Utilizando as equações para p0 e pk: 
∏
∑
∏
=
−
∞
=
=
⋅












+=
j
i
k
j
j
i
j
k
iXiX
p
1
1
1
1
)()(
1
λλ
 
O somatório possui um número infinito de termos e não pode ser calculado para o caso geral onde todos os 
valores da taxa de processamento são diferentes. Porém, a taxa de processamento satura depois de um 
certo valor de k. 



>
≤
=
JkJX
JkkX
k
,)(
,)(
µ após a saturação a taxa de processamento não muda. 
 
0 1 ... ...
1µ 2µ 1−Jµ )(JX )(JX
2
3µ
J J+1J-1
λ λλ λ λ λ λ
)(JX
 
Temos: 
1
1
0
1)()(
1
−
=






−
⋅++= ∑ ρ
ρ
β
λ
β
λ
Jk
p
JJ
k
k
 






>⋅⋅
≤⋅
=
Jk
J
JX
p
Jk
k
p
p
J
k
k
k
)(
)(
)(
0
0
β
ρ
β
λ
 
)(
)(.....)3()2()1()(
JX
kXXXXk
λρ
β
=
⋅⋅⋅⋅=
 
 
As equações são válidas apenas se λ < X(J), ou seja, se a taxa de chegada for menor que a taxa máxima de 
serviço. 
Observe que as equações para p0 e pk se tornam iguais às equações para o caso de população infinita, taxa 
de serviço fixo e tamanho de fila infinito quando J = 1. 
O número médio de requisições no servidor: 
[ ] ∑
=
×==
W
k
kpkNkE
0
 






−
−⋅++⋅⋅+⋅⋅= ∑
=
2
1
0
)1(
))1()1((
)()( ρ
ρρ
β
λρ
β
λ J
Jk
k
pN
JJ
k
k
 
A taxa media nos modelos abertos com tamanho de fila infinita é igual à taxa de chegada média. Assim: 
.λ=X 
O tempo médio de resposta é obtido pela Lei de Little: 
.
X
N
R = 
 
Exemplo 13. 
Um servidor Web recebe requisições em uma taxa de 30 requisições/segundo. A taxa de processamento do 
servidor quando existe uma requisição presente é de 18 requisições/segundo, para duas requisições é de 35 
requisições/segundo, e para três ou mais requisições é de 50 requisições/segundo. 
Determine a Utilização do Servidor e o tempo médio de resposta. 
 
0 1 ...2 5 64
181 =µ 352 =µ 50)( =JX
J=3
30=λ 30=λ 30=λ 30=λ
50)( =JX 50)( =JX 50)( =JX
30=λ 30=λ 30=λ
50)( =JX 
 
 
Fila M/M/1/∞ – taxa de serviço variável 
 
X(1) = 18 req/s β(1)= 18 
X(2) = 35 req/s β(2)= 630 
X(J) = 50 req/s β(J)= 31500 
 
 
6,0
50
30
)(
===
JX
λρ 
1
33
1
1
1
0
6,01
6,0
)3()(
1
1)()(
1
−
=
−
=






−
⋅++=





−
⋅++= ∑∑ β
λ
β
λ
ρ
ρ
β
λ
β
λ
k
kJJ
k
k
kJk
p 
113321
0
4,0
6,0
31500
27000
31500
27000
630
900
18
30
1
4,0
6,0
)(
30
)3(
30
)2(
30
)1(
30
1
−−





 ⋅++++=





⋅++++=
J
p
ββββ 
[ ] 0,1603056,2380955,1
7
6
7
6
7
10
3
5
1
1
1
0 ==




 ⋅++++= −
−
p 
 
Para k≤ J 
0,267176
18
30
160305,0
)1(
11
01 =⋅=⋅= β
λ
pp 
0,229008
630
30
160305,0
)2(
22
02 =⋅=⋅= β
λ
pp 
0,137405
31500
30
160305,0
)3(
33
03 =⋅=⋅= β
λ
pp 
Para k> J 
0,082443
31500
50
6,0160305,0
)(
)( 344
04 =⋅⋅=⋅⋅=
J
JX
pp
J
β
ρ
0,049466
31500
50
6,0160305,0
)(
)( 355
05 =⋅⋅=⋅⋅=
J
JX
pp
J
β
ρ
0,029679
31500
50
6,0160305,0
)(
)( 366
06 =⋅⋅=⋅⋅=
J
JX
pp
J
β
ρ 
 
 
 






>⋅⋅
≤⋅
=
Jk
J
JX
p
Jk
k
p
p
J
k
k
k
)(
)(
)(
0
0
β
ρ
β
λ
 
 
0,839695160305,011 0 =−=−= pU 
sreqX /30== λ 
 
Número médio de requisições no sistema: 






−
−⋅++⋅⋅+⋅⋅=





−
−⋅++⋅⋅+⋅⋅= ∑∑
==
2
33
1
02
1
0
)6,01(
))6,01()13(6,0(
31500
306,0
)()1(
))1()1((
)()( k
kJJ
k
k
k
k
p
J
Jk
k
pN
β
λ
ρ
ρρ
β
λρ
β
λ
 
srequisiçõe2,27112,238
)6,01(
))6,01()13(6,0(
31500
306,0
31500
303
630
302
18
301
02
3321
0 =⋅=





−
−⋅++⋅⋅+⋅+⋅+⋅⋅= ppN
O tempo médio de resposta é obtido pela Lei de Little: seg0,0757
30
270992,2 ===
X
N
R 
J 
(ponto de Saturação) 
2. Taxa de Serviço Variável e Tamanho de Fila Limitado (W requisições) 
As requisições podem ser perdidas se W requisições estiverem no servidor. Tem-se: 
Para :JW ≥ 
0 1 ... ... W-1
1µ 2µ 1−Jµ )(JX )(JX
2
3µ
J J+1J-1 W
λ λλ λ λ λ λ
)(JX )(JX
λλ
)(JX 



+=
=
=
WJkJX
JkkX
k
,...,1)(
,....,1)(
µ 
 
1
1
0
1
)1(
)()(
1
−−
=






−
−⋅⋅++= ∑ ρ
ρρ
β
λ
β
λ JWJJ
k
k
Jk
p 






+=⋅⋅
=⋅
=
WJk
J
JX
p
Jk
k
p
p
J
k
k
k
,....,1
)(
)(
,....,1
)(
0
0
β
ρ
β
λ
 
 
Para :JW < 
0 1 ... W-1
1µ 2µ
2
3µ
W
λ λ λ λλ
1−Wµ Wµ 
 
WkkXk ,....,1,)( ==µ 
1
1
0
)(
1
−
=






+= ∑
W
k
k
k
p
β
λ
 
Wk
k
pp
k
k ,....,1
)(
0 =⋅= β
λ
 
 
Onde: 
)(
)(.....)3()2()1()(
JX
kXXXXk
λρ
β
=
⋅⋅⋅⋅=
 
 
A fração de requisições perdidas: 





<⋅⋅
≥⋅⋅=
JWWp
JW
J
JX
p
p
W
J
W
W
)(
)(
)(
0
0
βρ
β
ρ
 
 
O número médio de requisições no servidor: 
[ ] ∑
=
×==
W
k
kpkNkE
0
 
 A taxa média de processamento do servidor: 
∑
=
×=
W
k
kpkXX
1
)( 
Para :JW ≥ 
∑∑∑
+===
⋅+×=×=
W
Jk
k
J
k
k
W
k
k pJXpkXpkXX
111
)()()( 
 
O tempo médio de resposta a uma requisição é obtido pela Lei de Little: 
.
X
N
R = 
 
Exemplo 14. Considere o Exemplo 13, exceto que a fila do servidor está limitada a 5 requisições. Calcule a 
Utilização do servidor, a taxa média de processamento, o número médio de requisições, o tempo médio de 
resposta, e a fração de requisições perdidas. 
0 1 2 54
181 =µ 352 =µ 50)( =JX
J=3
30=λ 30=λ 30=λ 30=λ
50)( =JX
30=λ
50)( =JX 
 
 
Fila M/M/1/∞ – taxa de serviço variável 
 
X(1) = 18 req/s β(1)= 18 
X(2) = 35 req/s β(2)= 630 
X(J) = 50 req/s β(J)= 31500 
 
 
6,0
50
30
)(
===
JX
λρ 
 
Temos :JW ≥ 
1
35321
1
1
0
6,01
)6,01(6,0
)()3()2()1(
1
1
)1(
)()(
1
−−−−
=






−
−⋅
⋅++++=





−
−⋅
⋅++= ∑
JJk
p
JJWJJ
k
k
β
λ
β
λ
β
λ
β
λ
ρ
ρρ
β
λ
β
λ
 
1135332
0
4,0
64,06,0
7
6
7
6
7
10
3
5
1
6,01
)6,01(6,0
31500
30
31500
30
630
30
18
30
1
−−−





 ⋅⋅++++=





−
−⋅
⋅++++=p 
[ ] 0,1731535,775238 10 == −p 
 
J 
(ponto de Saturação) 
Para k≤ J 
0,288588
18
30
160305,0
)1(
11
01 =⋅=⋅= β
λ
pp 
0,247361
630
30
160305,0
)2(
22
02 =⋅=⋅= β
λ
pp 
0,148417
31500
30
160305,0
)3(
33
03 =⋅=⋅= β
λ
pp 
Para k> J 
0,082443
31500
50
6,0160305,0
)(
)( 344
04 =⋅⋅=⋅⋅=
J
JX
pp
J
β
ρ
0,049466
31500
50
6,0160305,0
)(
)( 355
05 =⋅⋅=⋅⋅=
J
JX
pp
J
β
ρ
 
 
 
 
 






+=⋅⋅
=⋅
=
WJk
J
JX
p
Jk
k
p
p
J
k
k
k
,....,1
)(
)(
,....,1
)(
0
0
β
ρ
β
λ
 
 
0,8268470,17315311 0 =−=−= pU 
 
A fração de requisições perdidas: srequisiçõe
J
JX
ppp
J
W 049466,0
)(
)(5
05 =⋅⋅== β
ρ 
4,94 % das requisições serão perdidas.O número médio de requisições no servidor: 
[ ] 543210
0
543210 pppppppkNkE
W
k
k ×+×+×+×+×+×=×== ∑
=
 
[ ] seg1,851916== NkE 
 A taxa média de processamento do servidor: 
54321
1
)5()4()3()2()1()( pXpXpXpXpXpkXX
W
k
k ×+×+×+×+×=×=∑
=
 
segreqpkXX
W
k
k /28,3971)(
1
∑
=
=×= 
 
O tempo médio de resposta a uma requisição é obtido pela Lei de Little: 
segR 065215,0
28,3971
1,851916 == 
 
Modelos de População Finita 
 
Considere um servidor acessado por apenas M estações → Modelo Fechado. 
Cada estação envia uma requisição ao servidor, espera pela resposta, a analisa e compõe uma nova 
requisição a ser enviada. 
 
 
 
Cada estação envia 1/Z requisições/segundo ao servidor. 
Se o servidor estiver no estado k, ou seja há k requisições enviadas pelas M estações, M-k estações estarão 
no modo de pensar. 
Cada uma das (M-k) estações gera requisições em uma taxa 1/Z requisições/segundo. 
A taxa média em que as requisições chegam ao servidor no estado k: 
Mk
Z
kM
k ,...,1,0=
−=λ 
 
0 1 ... ... M-1
Z
M
Z
M )1( −
1
µ
1−Mµ2µ 1−kµ kµ 1+kµ 2+kµ
2
3µ
k K+1K-1 M
Mµ
Z
M )2( −
Z
kM )1( +−
Z
kM )( −
Z
1
Z
2
Z
kM )1( −−
Z
kM )2( +−
 
 
 
1. Taxa de Serviço Fixa e Fila Ilimitada 
 
A taxa se serviço não depende do estado k: 
Mkk ,.....,3,2,1== µµ 
 
0 1 ... ... M-1
Z
M
Z
M )1( −
2 k k+1k-1 M
Z
M )2( −
Z
kM )1( +−
Z
kM )( −
Z
1
Z
2
Z
kM )1( −−
Z
kM )2( +−
µ µµ µ µ µ µ µµ 
 
Temos: 
1
0
0
)()!(
!
−
=






⋅⋅−
= ∑
M
k
kZkM
M
p
µ 
Mk
ZkM
M
pp
kk
,....,1
)()!(
!
0 =⋅⋅−
⋅=
µ 
Envio Resposta Envio Z – tempo 
 de pensar 
Exemplo 15. 
Uma aplicação Cliente/Servidor é usada por 5 clientes. O software que roda na estação de trabalho cliente 
executa um cálculo local que dura 0,5 segundos, na média, antes de enviar uma nova requisição ao servidor. 
O servidor pode processar requisições a taxa de 8 requisições/segundo. Determine a Utilização do Servidor. 
1
0
0
)()!(
!
−
=






⋅⋅−
= ∑
M
k
kZkM
M
p
µ 
req/seg 8 seg 2Zclientes 5 === µM 
( ) ( ) ( ) ( ) ( ) ( )
1
5
2
14
2
13
2
12
2
11
2
10
2
1
0
8)!55(
!5
8)!45(
!5
8)!35(
!5
8)!25(
!5
8)!15(
!5
8)!05(
!5
−








⋅⋅−
+
⋅⋅−
+
⋅⋅−
+
⋅⋅−
+
⋅⋅−
+
⋅⋅−
=p
1
543210 4!0
!5
4!1
!5
4!2
!5
4!3
!5
4!4
!5
1
−






⋅
+
⋅
+
⋅
+
⋅
+
⋅
+=p 
1
0
128
15
32
15
16
15
4
5
4
5
1
−






+++++=p 
[ ] 0,1995,023438 10 == −p 0,8011 0 =−= pU 
Mk
ZkM
M
pp
kk
,....,1
)()!(
!
0 =⋅⋅−
⋅=
µ 
0,023
128
5
0,20
0,093
32
15
0,20
0,187
16
15
0,20
0,249
4
5
20,0
0,249
4
5
0,20
5
4
3
2
1
=⋅=
=⋅=
=⋅=
=⋅=
=⋅=
p
p
p
p
p
 
 
O número médio de requisições no servidor: 
[ ] req 1,796267543210 543210
0
=×+×+×+×+×+×=×== ∑
=
pppppppkNkE
W
k
k 
A taxa média de processamento do servidor 
UpXpXpXpXpXpkXX
W
k
k ⋅=×+×+×+×+×=×=∑
=
µ54321
1
)5()4()3()2()1()( 
µ=)(kX (taxa de processamento é constante) 
segreqX /6,407465801,08 =⋅= 
O tempo médio de resposta a uma requisição (Lei de Little): segundos0,28034
407465,6
1,796267 ===
X
N
R 
2. Taxa de Serviço Fixa e Tamanho de Fila Limitado (W<M) 
A taxa se serviço não depende do estado k: 
Wkk ,.....,3,2,1== µµ 
 
0 1 ... ... W-1
Z
M
Z
M )1( −
2 k k+1k-1 W
Z
M )2( −
Z
kM )1( +−
Z
kM )( −
Z
kM )1( −−
Z
kM )2( +−
µ µµ µ µ µ µ µµ
Z
kM )2( +−
Z
WM )1( +−
 
 
Temos: 
1
0
0
)()!(
!
−
=






⋅⋅−
= ∑
W
k
kZkM
M
p
µ 
Wk
ZkM
M
pp
kk
,....,1
)()!(
!
0 =⋅⋅−
⋅=
µ 
 
A fração de requisições perdidas: pw 
 
Exemplo 16. 
Considere o Exemplo anterior, porém o servidor possui capacidade de enfileirar no máximo 4 requisições. 
Determine a Utilização do Servidor e a probabilidade de perda de requisição. 
0 1
Z
M
Z
M )1( −
2 4
Z
M )2( −
Z
kM )2( +−
µ µ µ µ
3
 
4,3,2,1== kk µµ 
1
0
0
)()!(
!
−
=






⋅⋅−
= ∑
W
k
kZkM
M
p
µ 
req. 4 Wreq/seg 8 seg 2Zclientes 5 ==== µM 
( ) ( ) ( ) ( ) ( )
1
4
2
13
2
12
2
11
2
10
2
1
0
8)!45(
!5
8)!35(
!5
8)!25(
!5
8)!15(
!5
8)!05(
!5
−








⋅⋅−
+
⋅⋅−
+
⋅⋅−
+
⋅⋅−
+
⋅⋅−
=p
1
43210
4!1
!5
4!2
!5
4!3
!5
4!4
!5
1
−






⋅
+
⋅
+
⋅
+
⋅
+=p 
1
0
32
15
16
15
4
5
4
5
1
−






++++=p 
[ ] 0,2038224,90625 10 == −p 0,7961781 0 =−= pU 
Wk
ZkM
M
pp
kk
,....,1
)()!(
!
0 =⋅⋅−
⋅=
µ 
0,096
32
15
0,20
0,191
16
15
0,20
0,255
4
5
20,0
0,255
4
5
0,20
4
3
2
1
=⋅=
=⋅=
=⋅=
=⋅=
p
p
p
p
 
 
 
Probabilidade de perdas: 
 0,096
32
15
0,204 =⋅== ppW 
O número médio de requisições no servidor: 
[ ] req 1,719745543210 543210
0
=×+×+×+×+×+×=×== ∑
=
pppppppkNkE
W
k
k 
A taxa média de processamento do servidor: 
UpXpXpXpXpXpkXX
W
k
k ⋅=×+×+×+×+×=×=∑
=
µ54321
1
)5()4()3()2()1()( 
µ=)(kX (taxa de processamento é constante) 
segreqX /6,369427801,08 =⋅= 
O tempo médio de resposta a uma requisição é obtido pela Lei de Little: 
segundos0,2700
6,369427
1,719745 ===
X
N
R 
 
 
3. Taxa de Serviço Variável 



>
=
=
JkJX
JkkX
k
)(
,....,1)(
µ 
 
0 1 ... ... M-1
Z
M
Z
M )1( −
2 J J+1J-1 M
Z
M )2( −
Z
JM )1( +−
Z
JM )( −
Z
JM )1( −−
Z
kM )2( +−
1
µ )(JX
2µ 3µ 1−Jµ )(JX )(JX )(JX)(JX
Z
2
Z
1
 
 
A taxa de chegada: 
Mk
Z
kM
k ,....,0=
−=λ 
 
1
11
0
)()!(
!
)(
)(
)()!(
!
1
−
+==






⋅⋅−
⋅+
⋅⋅−
+= ∑∑
M
Jk
kk
JJ
k
k JXZkM
M
J
JX
kZkM
M
p
ββ 
Mk
ZkM
M
pp
kk
,....,1
)()!(
!
0 =⋅⋅−
⋅=
µ 
Onde: 
)(
)(.....)3()2()1()(
JX
kXXXXk
λρ
β
=
⋅⋅⋅⋅=
 
 
O número médio de requisições no servidor: 
[ ] ∑
=
×==
W
k
kpkNkE
0
 
 A taxa média de processamento do servidor: 
∑∑∑
+===
⋅+×=×=
M
Jk
k
J
k
k
M
k
k pJXpkXpkXX
111
)()()( 
O tempo médio de resposta a uma requisição é obtido pela Lei de Little: 
.
X
N
R = 
 
Exemplo 17. 
Uma aplicação Cliente/Servidor é usada por 5 clientes. O software que roda na estação de trabalho cliente 
executa um cálculo local que dura 0,5 segundos, na média, antes de enviar uma nova requisição ao servidor. 
A taxa de processamento do servidor quando existe uma requisição presente é de 3 req/s, para duas 
requisições é de 5 req/s, e para três ou mais requisições é de 8 req/s. Determine a Utilização do Servidor. 
 
X(1) = 3 req/s β(1)= 3 
X(2) = 5 req/s β(2)= 15 
X(J) = 8 req/s β(J)= 120 
Fila M/M/1/5 – taxa de serviço variável 
2seg Z3clientes 5 === JM 
 
0 1
Z
M
Z
M )1( −
2 54
Z
M )2( −
Z
JM )1( +−
Z
kM )2( +−
31 =µ 52 =µ 83 =µ )(JX
J=3
)(JX 
 
 
1
11
0
)()!(
!
)(
)(
)()!(
!
1
−
+==






⋅⋅−
⋅+
⋅⋅−
+= ∑∑
M
Jk
kk
JJ
k
k JXZkM
M
J
JX
kZkM
M
p
ββ 
1
55
2
144
2
1
3
3
2
12
2
11
2
1
0
)8()!55(
!5
)8()!45(
!5
120
)8(
120)!35(
!5
15)!25(
!5
3)!15(
!5
1
−
















⋅⋅−
+
⋅⋅−
⋅+
⋅⋅−
+
⋅⋅−
+
⋅⋅−
+=p
1
0
2
1
24
3
16
3
10
1
−



 +++++=p 
( ) 0,06185616,16667 10 === −p 0,9381441 0 =−= pU 
Mk
ZkM
M
pp
kk
,....,1
)()!(
!
0 =⋅⋅−
⋅=
µ 
0,030928
128
5
0,20
0,123711
32
15
0,20
0,247423
16
15
0,20
0,329897
4
5
20,0
0,206186
4
5
0,20
5
4
3
2
1
=⋅=
=⋅=
=⋅=
=⋅=
=⋅=
p
p
p
p
p
 
 
O número médio de requisições no servidor: 
[ ] req 2,257732543210 543210
0
=×+×+×+×+×+×=×== ∑
=
pppppppkNkE
W
k
k 
A taxa média de processamento do servidor: 
54321
1
)5()4()3()2()1()( pXpXpXpXpXpkXX
W
k
k ×+×+×+×+×=×=∑
=
 
segreqX /5,48453608= 
O tempo médio de resposta a uma requisição é obtido pela Lei de Little: 
segundos0,41165414
5,48453608
2,257732 ===
X
N
R 
 
 
 
Discouraged Arrival 
 
As chegadas dos pacotes tendem a diminuir quando mais e mais pacotesestão presentes no sistema. 
Considere: ,....2,1,0,
1
=
+
= k
k
k
αλ e ,....2,1, == kk µµ 
0 1 ... ...
α
2
α
2 k k+1k-1
3
α
k
α
1+k
α
2+k
α
1−k
α
µ µµ µ µ µ µ 
Equação Fila infinita: ∏
−
= +
⋅=
1
0 1
0
k
i i
i
k pp µ
λ
, e 
1
0
1
0 1
0
−∞
=
−
= +






⋅= ∑ ∏
k
k
i i
ip
µ
λ
, substituindo: 
µ
α−
= ep0 
,....2,1,0,
!!
11
0
1
0
0 =⋅




=⋅




⋅=+⋅=
−
−
=
∏ k
k
e
k
pkpp
kk
k
i
k
µ
α
µ
α
µ
α
µ
α
 
 
 Número médio de requisições no sistema: 




=
µ
α
N 
Definindo: 0
/ 11 pe −=−= − µαρ 
)1( / µαµµρλ −−⋅=⋅= e .
X
N
R = 
Lei de Little: XRN ⋅= , para sistemas abertos fila infinita: λ⋅= RN . Substituindo: 
Tempo médio na fila: 
)1(
/2 µαµ
α
−−⋅
=
e
R 
 
Modelos com capacidade de Armazenamento Infinita 
 
Numero infinito de servidores- Fila M/M/∞ 
Não há bloqueio. 
 Considere: ∞== ,....,2,1,0, kk λλ e ∞=⋅= ,....,2,1, kkk µµ 
0 1 ... ...
λ
2 k k+1k-1
µ µ)2( +kµ2 µ3 µ)1( −k µk µ)1( +k
λ λ λ λ λ λ
 
Equação Fila infinita: ∏
−
= +
⋅=
1
0 1
0
k
i i
i
k pp µ
λ
, e 
1
0
1
0 1
0
−∞
=
−
= +






⋅= ∑ ∏
k
k
i i
ip
µ
λ
, substituindo: 
,....2,1,0
)1(
1
0
0 =+
⋅= ∏
−
=
k
i
pp
k
i
k µ
λ
 
Se fizermos α = λ, observamos que o resultado é equivalente ao obtido para o modelo anterior: 
( ) ,....2,1,0,
!
/
/
=⋅=
−
k
k
e
p
k
k
µλ
µλ 
 
Número médio de requisições no sistema: 





=
µ
λ
N . 
O numero médio de pacotes do sistema M/M/∞ (taxa decrescente) → M/M/1, quando todos servidores 
estiverem em serviço, Utilização =100%. 
Observe: O tempo médio de resposta do servidor para uma requisição nas Filas M/M/1: 
)1(
1
)1( UU
U
N
−
⋅=⋅
−
=
µ
λ
 
 
Tempo médio na fila é obtido pela Lei de Little:: .
11
µλµ
λ =⋅==
X
N
R 
Numero finito de servidores – Fila M/M/m 
Não há bloqueio. 
 Considere: ∞== ,....,2,1,0, kk λλ e 



≥
≤≤
=
mkm
mkk
k µ
µ
µ
0
 
0 1 ...
λ
2 m-1 mm-2
µ µ2 µ3 µ)2( −m µ⋅− )1(m µ⋅m
λ λ λ λ λ
m+1 ...
λ
µ⋅m
λ λ
m+2
µ⋅m µ⋅m 
Para k ≤ m : 
!
1
)1(
0
1
0
0
k
p
i
pp
k
k
i
k ⋅





⋅=
+
⋅= ∏
−
= µ
λ
µ
λ
 
Para k> m : ∏∏
−
=
−
= ⋅+
⋅
⋅
⋅=
1
0
1
0
)1(
m
i
k
mj
k
im
pp
µ
λ
µ
λ
 
∏ ∏∏ ∏
−
=
−
=
−
=
−
=
−
⋅
+
⋅





⋅=⋅
+
⋅





⋅





⋅=
1
0
1
0
1
0
1
0
1
)1(
11
)1(
1 m
i
k
mj
k
m
i
k
mj
mkm
k
mi
p
mi
pp
µ
λ
µ
λ
µ
λ
 
⋅
⋅
⋅





⋅=




⋅⋅





⋅= −
−
mk
kmkk
k
mm
p
mm
pp
!
11
!
1
00 µ
λ
µ
λ
 
Probabilidade de termos k componentes no sistema: 






⋅
≥
⋅
⋅⋅
≤⋅
=
mk
m
m
p
mk
k
m
p
p
m
k
k
k
!
!
)(
0
0
ρ
ρ
 ⋅<= 1µ
λρ
m
 
1
1
1
0
1
!
)(
!
)(
1
−−
=
∞
=
− 





⋅++= ∑ ∑
m
k mk
mk
kk
mm
m
k
m
p
ρρ
 
1
!
)(
!
)(
01
−=∑∑
==
m
k
km
k
k
k
m
k
m ρρ
 
∑∑∑∑
∞
+=
∞
+=
∞
+=
−
∞
=
⋅+=⋅+=⋅+=⋅
111 !!
)(
!!
)(
!
)(
!
)(1
!
)(
mk
k
mm
mk
mkm
k
m
mk
km
mk
mk
k
m
m
m
m
m
m
m
m
m
m
k
m
m
m
mm
m ρρρρρρρ 






−
⋅=





−
+⋅=
−
⋅+=
−
⋅+=
+
ρ
ρ
ρ
ρρ
ρ
ρρρ
ρ
ρρ
1
1
!
)(
1
1
!
)(
1!
)(
!
)(
1!!
)( 1
m
m
m
m
m
m
m
m
m
m
m
m mmmmmmm
 
Substituindo: 
1
1
0
0
1
1
!
)(
!
)(
−
−
=












−
⋅+= ∑ ρ
ρρ
m
m
k
m
p
mm
k
k
 
Probabilidade de Enfileiramentos – ocorre quando há mais de m componentes no sistema: 
∑∑
∞
=
−
∞
=
⋅⋅==
mk
mk
k
O
mk
k
mm
m
ppenfP
1
!
)(
][
ρ
 






−
⋅+
−
⋅
=
∑
−
=
1
0 1
1
!
)(
!
)(
1
1
!
)(
][
m
k
mk
m
m
m
k
m
m
m
enfP
ρ
ρρ
ρ
ρ
 Fórmula de Erlang C: C(m, λ/µ) 
Nota: 1
1
1
1
0
0
1
−
−
−=−=
+
==
∑∑
U
U
UUU
kk
k
k
k
k
k
 se U < 1. 
Exemplo 18. 
The Erlang-C calculations are described step by step below, using and example of 360 calls per half hour, 
with an average call duration of 4 minutes, and 55 agents. The target answer time for service level is 15 
seconds. 
(1) Specify call arrival rate 
The first parameter needed is the average customer arrival rate. It doesn't matter what time unit is used to 
specify the arrival rate, as long as the same time unit is used for the average call duration. Also, the results 
we shall get for waiting time will be in these time units. 
calls/s 2,0
seg 1800
calls/h 360 ==kλ 
(2) Specify call duration 
The second factor to be specified is the average call duration. This must be expressed in the same time unit 
used for the call arrival rate. 
seg 240min 4 ==St calls/seg 
240
11 ==
St
µ 
(3) Specify number of agents 
The third factor is the number of agents available. 
circuitos 55=m 
(4) Calculate traffic intensity 
The term "traffic intensity" comes from the original application of Erlang-C, which was for telephone 
networks, and the volume of calls was described as the "traffic". We need to calculate the traffic intensity as 
a preliminary step to the rest of the calculations. 
erlangs 482402,0 =⋅==⋅=
µ
λλ Sta 
(5) Calculate agent occupancy 
The agent occupancy, or utilisation, is now calculated by dividing the traffic intensity by the number of 
agents. The agent occupancy will be between 0 and 1. If it is not less than 1 then the agents are overloaded, 
and the Erlang-C calculations are not meaningful, and may give negative waiting times. 
0,873
55
48 ===
m
aρ 
(6) Calculate the Erlang-C formula 
Now we can calculate the main Erlang-C formula. This formula looks complicated, but is straightforward to 
calculate with a few lines of programming. The value of EC(m,u) is needed to calculate the answers we 
actually want. 
0,2387
1
1
!
)(
!
)(
1
1
!
)(
][
1
0
=






−
⋅+
−
⋅
=
∑
−
=
m
k
mk
m
m
m
k
m
m
m
enfP
ρ
ρρ
ρ
ρ
 
(7) Calculate probability of waiting 
EC(m,u) is the probability that a call is not answered immediately, and has to wait. This is a probability 
between 0 and 1, and to express it as a percentage of calls we multiply by 100%. 
 
( )
0,2387
!
1
!
!
][
1
0
=
⋅−+
=
∑
−
=
m
k
km
m
k
a
m
a
m
a
enfP
ρ
 
(8) Calculate average speed of answer (ASA) 
Having calculated EC(m,u) it is quite easy to calculate the average waiting time for a call, which is often 
referred to as the "Average Speed of Answer" or ASA. We have to remember the time units we used for 
arrival rate and call duration. 
 segundos 184,8
)873,01(55
240
2387,0
)1(
][ =
−⋅
⋅=
−⋅
⋅=
ρm
t
enfPT SW 
(9) Calculate service level 
Frequently we want to calculate the probability that a call will be answered in less than a target waiting 
time. The formula for this is given here. Remember that, again, the probability will be on the scale 0 to 1 
and should be multiplied by 100 to express it as a percentage. 
 846,02387,01][1] t timeWaiting[)( 240
15
)4855()(
=−=−=≤=
⋅−−⋅−−
St
t
am
enfPPtW 
(10) Calculate agents needed 
If the service level is specified and you want to calculate the number of agents needed, then you must do a 
bit of (intelligent) trial and error. You have to find the number of agents that will just achieve the service-
level you want. A good starting point is the traffic intensity, rounded up to the next integer. the increase the 
number of agents until the required service-level is reached. 
 
Modelos com capacidade de Armazenamento Finita 
 
1. Sistema com Único servidor e com perdas – Fila M/M/1/W 
Nestes sistemas ocorrem perdas de requisições: há bloqueio. 
 
 Considere: ∞== ,....,2,1,0, kk λλ e Wkk ,...,2,1, == µµ 
0 1 ... ... W-1
λ λλ λ λ λ λµ µµ µ µ µ µ
2
λ
µ
k K+1K-1 W
λ
µ 
Utilizando a equação : ∏
−
=
⋅=
1
0
0
k
i
k pp µ
λ
, obtemos: 





⋅
>
≤





⋅=
Wk
Wkp
p
k
k
0
0 µ
λ
 
1
1
0 1
−
= 













+= ∑
W
k
k
p
µ
λ
, temos: 1
1
1
1
1
01
−
−
−=−=
+
==
∑∑
U
U
UU
WW
k
k
W
k
k
 
)/(1
)/(1 1
0 µλ
µλ
−
−
=
+W
p 
2. Sistema com m servidores e com perdas – Fila M/M/m/m 
há bloqueio. 
 Considere: ∞== ,....,2,1,0, kk λλ e mkkk ,...,2,1, == µµ 
0 1 ...
λ
2 m-1 mm-2
µ µ2 µ3 µ)2( −m µ⋅− )1(m µ⋅m
λ λ λ λ λ
 
Utilizando a equação : mk
i
pp
k
i
k ≤⋅+
⋅= ∏
−
=
1
0
0
)1( µ
λ
, obtemos: 





⋅
>
≤⋅





⋅=
mk
mk
k
p
p
k
k
0
!
1
0 µ
λ
 
1
0
0
!
1
−
= 







⋅





= ∑
k
p
m
k
k
µ
λ
, 
 
Probabilidade de Bloqueio – ocorre quando há m componentes no sistema: 
∑
=












=
m
k
k
m
m
k
m
P
0
!/
!/
µ
λ
µ
λ
 
Fórmula de Erlang β: β (m, λ/µ) 
 
Erlang Loss 
 
Aplicacao do Erlang Loss – Fila M/M/m/m 
a – intensidade de Tráfego (Erlang) 
Pn – Probabilidade de que n usuários estejam no sistema. 
∑
=
m
ki
i
n
n
ia
na
P
0
!/
!/
 
 para n = 0, 1, 2, ..., m. 
 a =( λ/µ). 
Ocorrem bloqueios no sistema quando n=m. 
∑
==
m
ki
i
m
mloss
ia
ma
PL
0
!/
!/
 
a =( λ/µ). 
Fórmula de Erlang β: β (m, a) 
 
Uma forma de calcular B(m,a) e através da fórmula recursiva: 
),1(
1
1
),(
1
ama
m
am −
+=
ββ , ou ),1(
),1(
),(
amam
ama
amB
−⋅+
−⋅=
β
β
 
Carga – define-se carga ou tráfego transportado (ou vazão), representada pelo símbolo ac, à equação: 
[ ]∑
=
−⋅=⋅=
m
n
nc amaPna
1
),(1 β 
A probabilidade de perdas é por definição a proporção de usuários que não podem ser atendidos, portanto: 
),(1 amL
a
a
a
aa
L cc β=⇔−=−= 
Exemplo 19. Aplicando a teoria e Erlang Loss: Dimensionamento de troncos telefônicos 
Dois computadores A e B, cada um suporta 1000 telefones que são conectados por m troncos. Cada tronco 
suporta uma comunicação telefônica no modo half-duplex. Suponha que um telefone seja ocupado por seis 
minutos durante uma hora, e que o telefone possa fazer com igual probabilidade chamada para o mesmo 
grupo local ou telefones de outro grupo. Determine o numero de troncos m necessários para garantir que a 
taxa de sucesso de chamadas seja de pelo menos 99%. 
 
 
 
 
A carga de um telefone para os m troncos: 
erlangsac 025,0
min60
min6
5.05,01, =⋅⋅= 
 prob.gerar prob. receber 
a taxa de bloqueio: L =1% = 0,01. 
11
1, 025,0
11
aa
a
a
aa
L
cc −=−=
−
= → a1= 0,0253 erlangs 
A carga total: erlangsaka cAT 3,25025,010001, =⋅=⋅= 
)3.25,(01,0),( erlmamL ATA ββ =⇔= Tabela: mA = 36 ; mB=36 ; total: 72 troncos. 
 
Exemplo 20. Aplicando a teoria e Erlang Loss 
Uma empresa possui um call center com duas linhas telefônicas para atendimento. Após um período de 
medidas foi observado que as linhas estão ocupadas 15% do tempo e que o “call holding time” médio é de 
10 minutos. Determine a probabilidade de bloqueio de chamadas do call Center no caso em que o “call 
holding time” aumente de 10 para 15 minutos. As chegadas das chamadas são possonianas. 
Dados: '10/1 =µ , µλ /=a , %10=BP 
2/1
2/
2
2
2
aa
a
PLloss ++
== → 
90
191+==⋅ λµa 
Temos: 15/1 =µ → 89315,015
90
191
/ =⋅+== µλa 
 17,4021%0,174021
2/1
2/
2
2
2 →=++
==
aa
a
PLloss 
KB = 1000 
Telefone
KA = 1000 
Telefone
m troncos 
Exemplo 21. A Cabine telefônica 
As chegadas dos clientes a uma cabine telefônica obedecem à lei de Poisson, com taxa de 6 chegadas/hora. 
A duração do telefonema segue uma distribuição exponencial com média de 3 minutos. Pede-se: 
a) Qual a probabilidade de uma pessoa chegar à cabine e não ter que esperar? 
A taxa de chegada das chamadas: inchamadas/m60/6=λ 
A taxa de serviço média µ é o inverso do tempo de serviço por requisição: inchamadas/m
3
11 ==
st
µ 
7,03,01
3/1
60/6
110 =−=−=−= µ
λ
p . A gabine telefônica está desocupada 70% do tempo. 
 
b) Qual é a fração do tempo durante a qual o telefone está em uso? 
30,07,011 0 =−=−= pU . A gabine telefônica está ocupada 30% do tempo. 
c) Qual o número médio de pessoas na fila? 
428,0
30,01
30,0
)1(
=
−
−=
−
=
U
U
N pessoas na fila. 
d) Qual o tempo médio de espera na fila? 
Sistemas abertos – Fila infinita: min28,4
1,0
428,0 ===
λ
N
R 
 
 
Exemplo 22. Uma região de uma grande cidade possui população de 200.000 habitantes. Três companhias 
operadoras de telefonia celular A, B, C competem para fornecer serviços nesta área. A empresa A possui 
394 células com 12 canais cada, a empresa B possui 98 células com 18 canais cada e a empresa C possui 49 
células com 28 canais cada. Determine a quantidade de usuários suportados por cada empresa com um GOS 
= 2% se cada usuário efetua 2 chamadas por hora, em média, com uma duração média de 3 minutos. Qual a 
penetração de mercado de cada empresa. 
 
 
 
Exercícios Propostos 
 
1. Um roteador recebe um tráfego de 40 pacotes /segundo. Cada pacote gasta 0,02 segundos em 
média para ser processado. Considere que o buffer do roteador suporte no máximo 6 pacotes. 
a. Desenhe o diagrama de estados. Apresente a Notação de Kendall para a fila. 
b. Qual a probabilidade de um pacote encontrar a fila vazia? 
c. Qual a probabilidade de descarte? 
d. Qual o Tempo médio de Resposta? 
e. Quanto espaço na fila seria necessário para que a taxa de perda fosse inferior a 0,2%? 
 
2. O gerente de um supermercado registrou um fluxo médio de 120 clientes / hora em sua loja. As 
atendentes conseguem atender, em média, 4 clientes / 10 minutos. 
a. Qual deve ser o número de atendentes para que o tempo médio dos clientes na fila seja no 
máximo 3 minutos? 
b. Após treinamento, as atendentes passaram a atender 8 clientes / 10 minutos. Qual o tempo 
médio que os clientes permanecem na fila? 
 
3. Um hospital atende os pacientes a uma taxa de 50 atendimentos/hora. São disponibilizadas senhas 
aos pacientes, que requerem atendimento a uma taxa de 30 atendimentos/hora. As senhas dos 
pacientes atendidos são liberadas para novos atendimentos. Pacientes que não encontram senhas 
disponíveis são encaminhados para outro hospital. 
Senhas Fila Atendimento
Entrada Saída
 
a. Qual deve ser o número de senhas necessário para que a taxa de perda seja inferior a 1%? 
b. Qual o tempo médio que o paciente aguarda pelo atendimento? 
 
 
4. Considere os dados de um Roteador: Taxa de chegada = 400 pacotes por segundo. Tempo para 
encaminhar pacotes 2 ms. Calcular usando uma fila M/M/1: (fila infinita, único servidor). 
a. Desenhe o diagrama de estados. 
b. Taxa de serviço. 
c. Taxa média de processamento. 
d. Número médio de pacotes no servidor. 
e. Número médio de pacotes na fila. 
f. Tempo médio de Resposta 
g. Probabilidade de descarte no caso de haver espaço para 10 pacotes na fila. 
h. Qual a probabilidade de um pacote encontrar a fila vazia? 
i. Quanto espaço na fila seria necessário para que a taxa de perda fosse inferior a 0,1%? 
 
5. Uma agência bancária disponibilizou um caixa para o serviço de atendimento prioritário. 
Porém, foi verificado que a taxa de chegada dos clientes comuns é 5 vezes a dos clientes 
prioritários. Quantos caixas comuns deverão ser disponibilizados para que o tempo médio 
de atendimento de ambos os clientes comuns e prioritários seja o mesmo? 
 
6. As requisições chegam a um servidor a taxa de 75 requisições/segundo. Cada requisição gasta 0,01 
segundos na média para ser processada. Considere que o buffer do servidor suporte no máximo 5 
requisições. Responda. 
a. Desenhe o diagrama de estados. 
b. Apresentea Notação de Kendall para a fila 
c. Qual é a fração do tempo em que k (k = 0, 1, 2, 3, 4,5) requisições se encontram no 
servidor? Apresente o gráfico pk versus k. 
d. Utilização do Servidor 
e. Probabilidade de descarte 
f. Número médio de requisições no servidor 
g. Taxa de processamento 
h. Tempo médio de Resposta 
i. Refaça os itens (c, d, e, f, g, h) para uma taxa de chegada de 100 requisições/segundo. 
 
7. Uma aplicação Cliente/Servidor é usada por 4 clientes. O software que roda na estação de trabalho 
cliente executa um cálculo local que dura dois segundos, na média, antes de enviar uma nova 
requisição ao servidor. O servidor pode processar requisições a taxa de 6 requisições/segundo. 
Determine a Utilização do Servidor. 
 
8. Dimensionar a quantidade de linhas de saída de uma central telefônica para uma 
probabilidade de perdas de 0,5%, sendo a quantidade de chamadas de 31 por minuto com 
duração média de 3 minutos. 
 
9. Suponha que uma empresa tenha um call Center com duas linhas telefônicas para atendimento. 
Após um período de medidas foi observado que as linhas estão ocupadas 10 % do tempo e que o 
“call holding time” médio é de 15 minutos. Determine a probabilidade de bloqueio de chamadas do 
call Center no caso em que o “call holding time” aumente de 15 para 20 minutos. As chegadas das 
chamadas são possonianas com taxa constante.