Modelagem e Análise Aula 9 - Federal University of Rio de...

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 + ... + XNc­1 + 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 + ... + XNc­1 + X]

E[W] = E[R] + E[X1]+ ... + E[XNc­1]+ 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