Embed Size (px)
Citation preview
Figueiredo – de Souza e Silva – 2009
Modelagem e AnáliseAula 9
Aula passadaEquações de fluxoTempo contínuo
Aula de hojeParâmetros de uma filaMedidas de desempenhoCálculo do tempo de esperaResultado de Little
Figueiredo – de Souza e Silva – 2009
Parâmetros da Fila
Processo de chegada (como os pedidos chegam ao recurso)
Processo de serviço (como os pedidos são servidos)
Capacidade de armazenamento da fila
Número de recursos (estações de serviço)
Política de atendimento (como escolher o próximo da fila)
fila recursochegada
na filasaída da
fila
Figueiredo – de Souza e Silva – 2009
Fila – Processo de Chegada
Como definir processo de chegada (demanda)?No banco, como pessoas chegam ao bancoNa rede, como pacotes chegam ao roteadorNo disco, como pedidos de leitura chegamAbstração matemática!
fila recursochegada
na fila saída da fila
Figueiredo – de Souza e Silva – 2009
Fila – Processo de Chegada
Modelo matemático para abstrair processo de chegada
Chegada não é determinística
Necessidade de representação aleatória
Ex. distribuição do tempo entre chegadas● Descreve precisamente o processo de chegada
fila recursochegada
na fila saída da fila
Figueiredo – de Souza e Silva – 2009
Fila – Processo de Serviço
Como definir processo de serviço?
Quanto tempo leva para atender um pedido?
Depende do sistema, geralmente aleatórioModelo matemático para abstrair o processo de
serviço
Ex. distribuição do tempo de serviço
fila recursochegada
na fila saída da fila
Figueiredo – de Souza e Silva – 2009
Parâmetros de uma Fila
A : intervalo de tempo entre chegadas X : tempo de serviço (de 1 pedido) K : capacidade de armazenamento da fila (infinito?) C : número de estações de serviço P : política de atendimento dos elementos em fila
X
A
K... C
A, X geralmente são variáveis aleatórias!
Figueiredo – de Souza e Silva – 2009
Notação de Filas
A / X / C / K – PX
A
K... C
distribuição do tempo entre chegadas
distribuição do tempo de serviço
número de estações de serviço
capacidade de armazenamento
política de atendimento
M = exponencial (memoryless)D = determinísticoEr = Erlang
default: infinito default: FIFO
Exemplo: M/M/1 Qual é a fila?
Figueiredo – de Souza e Silva – 2009
Medidas de Desempenho
em Filas
Utilização: fração de tempo que o servidor está ocupado
Tempo de espera: quantidade de tempo que cada elemento espera na fila
Vazão (Throughput): quantidade de elementos servidos pela fila por unidade de tempo
Fração de descarte: fração de elementos descartados por falta de espaço na fila
K
Figueiredo – de Souza e Silva – 2009
Medidas de Desempenhoem Filas
Tradeoff entre tempo de resposta e vazão
K
Tempo de
espera
Vazão
Comportamento típico
Figueiredo – de Souza e Silva – 2009
Avaliando o Desempenhode uma Fila
ProblemaDado uma fila, qual seu desempenho?
Como assim? Como assim?
Parâmetros da fila (demanda, capacidade, etc.)
Medida: Tempo médio de espera no sistema
Vamos calcular isto!
Figueiredo – de Souza e Silva – 2009
Tempo de EsperaComo calcular o tempo de espera em uma fila?● tempo decorrido desde o instante de chegada
até o instante de saídaIDÉIA: Decompor o tempo de espera em
tempos menores
1) Tempo para finalizar o pedido sendo atendido no instante de chegada
2) Tempo para atender cada um dos pedidos da fila
3) Tempo para atender o pedido que acabou de chegar
Figueiredo – de Souza e Silva – 2009
Variáveis Aleatórias de uma Fila
Nc : número de elementos na fila no instante de chegada (incluindo o que está sendo atendido)
R : tempo residual (tempo para finalizar serviço do elemento sendo atendido)
Xi : tempo necessário para atender o iésimo pedido da fila (i=1, 2, ..., Nc 1)
W : tempo de espera de um elemento (do instante de chegada até o instante de saída)
X
ANc
W
Figueiredo – de Souza e Silva – 2009
Tempo de Espera
X
ANc
W
W: tempo de espera do pedido que chegou● Nc elementos na fila
● 1 em atendimento + Nc – 1 na fila
W = R + X1 + X2 + ... + XNc1 + X
tempo residualdo elemento em atendimento
tempo de serviçodo iésimo elementoda fila
tempo de serviçodo elemento que acabou de chegar
Quanto vale W?
Figueiredo – de Souza e Silva – 2009
Tempo Médio de Espera
Aplicar valor esperado – E[.]
X
ANc
Tempo médio de espera: E[W]
E[W] = E[R + X1 + X2 + ... + XNc1 + X]
E[W] = E[R] + E[X1]+ ... + E[XNc1]+ E[X]
E[W] = E[R] + E[Nc]E[X]
W
Xi são idênticamentedistribuídas
Figueiredo – de Souza e Silva – 2009
Resultado de Little
: taxa média de chegada E[W] : tempo médio que cada pedido permanece
dentro da caixa preta E[N] : número médio de pedidos dentro da caixa
(depois de um tempo muito grande)
Caixa Preta
E[W]
E[N]
Qual é a relação entre eles?
E[N] = E[W] Vamos provaristo hoje!
Figueiredo – de Souza e Silva – 2009
Resultado de Little
Número médio dentro do sistema é igual ao produto da taxa média de chegada pelo tempo médio de permanência no sistema
Intuitivo, mas poderoso (não depende de nenhuma distribuição)
Caixa Preta
E[W]
E[N]
Exemplo:
E[W] = 3.5 minutos
clientes por minuto
E[N] = ?
=2
Figueiredo – de Souza e Silva – 2009
Resolvendo o Tempo Média de Espera
Duas equações:
● Suposição (I) : E[N] = E[Nc] ● Suposição (II) : E[R] = E[X]● Substituindo nas equações acima, temos
E[W] = E[R] + E[Nc]E[X]
E[N] = E[W]
E[W] = E[X] + E[W]E[X]
E[W] = E[X] 1 – E[X]
equação em função dosparâmetros da fila
Figueiredo – de Souza e Silva – 2009
Gráfico do Tempo Médio de Espera
Tempo de espera explode!
E[W] = E[X] 1 – E[X]
E[W]
1/E[X]
Figueiredo – de Souza e Silva – 2009
Suposição I: E[N] = E[Nc]Duas variáveis (medidas)● Número de elementos no sistema● N – em um instante de tempo qualquer● Nc – no instante de uma chegada
Em geral, E[N] é diferente de E[Nc]
Exemplo?
Figueiredo – de Souza e Silva – 2009
ExemploSuponha sistema de fila determinístico● tempo entre chegadas 1s, tempo de serviço 0.5s
Quanto vale E[N] e E[Nc]?
Diferentes!
0 0.5 1.0 1.5 2.0 2.5 t
Evolução do sistema no tempo?
E[N] = 0.5
E[Nc] = 0
Figueiredo – de Souza e Silva – 2009
Suposição I● E[N] = E[Nc]
● Quando isto é verdade?
PASTA
pas
Poisson Arrivals See Time Averages
● Quando o processo de chegada é Poisson● E[N] = E[Nc]
Figueiredo – de Souza e Silva – 2009
Suposição II● E[R] = E[X]● Quando isto é verdade?
Memoryless Distribuição não tem memória
● Quando o tempo de serviço é exponencial
Figueiredo – de Souza e Silva – 2009
Propriedade Memoryless● Propriedade de memoryless
● Distribuição da probabilidade condicional é igual a distribuição da probabilidade original (para o restante do tempo)
P [T st∣T s ]=P [T t ]
Correto
s , t0
P [T 40∣T 30 ]=P [T 10 ]
P [T 4 0∣T 3 0 ]=P [T 40 ]
● Exemplo
Errado!
● A chance de um evento não ocorrer nos próximos 10 segundos é igual a dos primeiros 10 segundos!
Figueiredo – de Souza e Silva – 2009
Tempo Média de EsperaE[W] = E[X]
1 – E[X]● Verdade para toda fila?
Condições necessárias para resultado● Chegada Poisson● Serviço Exponencial● Capacidade Infinita● Política FIFO
Fila M/M/1
Onde violamos dedução em cada caso?
Figueiredo – de Souza e Silva – 2009
Medindo as Medidas de Interesse de uma Fila
N(t)
t
evolução do tamanhoda fila no tempo
● Quanto vale E[N]?● tamanho médio da fila (no tempo)
● Quanto vale E[W]?● tempo médio de espera (de um pedido)
Figueiredo – de Souza e Silva – 2009
Medindo E[N]N(t)
t
● onde T é um tempo qualquer e Ti(T) é o tempo que a fila permanece com i elementos no intervalo [0, T]
E [NT ]=∑ i=0
∞
i∗T iT
T
● Observação: ∑i=0
∞
T iT =T
∑i=0
∞
i∗T i T =∫t=0
t=TN t dt
● Logo:
E [NT ]=∫t=0
t=TN t dt
T
Figueiredo – de Souza e Silva – 2009
Medindo E[W]N(t)
t
● onde n é um númer de saídas do sistema qualquer e e Wi é o tempo de espera da i-ésima saída
E [W ]=∑i=1
nW i
n
● Observação: W i=Si−C i
● Logo:
E [W ]=∑i=1
nSi−C i
n
● onde Ci e Si são os instantes de chegada e saída do i-ésimo elemento
Figueiredo – de Souza e Silva – 2009
Outra Evolução da FilaN t t t
t
: número total dechegadas até t
: número total desaídas até t
t −t tT
= T
T
fila
espera
● Quanto vale N(t)?
● Quanto vale Wi?
● Qual é a taxa média de chegada?
Figueiredo – de Souza e Silva – 2009
Medidas de Interesse
t
t
: número total dechegadas até t
: número total desaídas até t
N t t
tT
fila
espera
● Quanto vale E[N]? E[N] = ∫T
t −t d t
T
● Quanto vale E[W]? E[W] = ∫T
t −t d t
T
Figueiredo – de Souza e Silva – 2009
Provando Resultado de Little
E[N] = ∫T
t −t d t
T
E[W] = ∫T
t −t d t
T
= T
T
● Substituindo, temos:
E[N] T = E[W] T
E[N] = E[W] / T
E[N] = E[W] Resultado de Little!
∫Tt −t d t =E [N ]T
∫Tt −t d t =E [W ] T
T
Figueiredo – de Souza e Silva – 2009
Lei de Little
E[N] = E[W] ● Verdade para toda fila?
Verdade para caixa preta!● independente do que tem dentro da caixa preta
Caixa preta com capacidade finita?● é taxa de chegada a caixa preta
Caixa Preta
p
: taxa de elementos perdidos
e = - p taxa efetiva de entrada
