Análise Aplicada A Desempenho

Revisão de Estatística
(Aplicada a Análise de
Desempenho)
Profa. Jussara M. Almeida
1o Semestre de 2014
Por quê?
•  Modelagem probabilística
•  Avaliação dos resultados
–  Qual a probabilidade do tempo de residência no disco 1
ser inferior a 0.5 segundo?
•  Depende da distribuição de probabilidade do tempo de
residência!!!
–  O tempo médio de resposta é uma boa estimativa do
desempenho do sistema?
•  Depende da variabilidade de R: variância, desvio padrão
•  Caracterização da carga
–  Como modelar o tempo entre chegada de requisições no
servidor?
Variável Aleatória
•  Uma variável aleatória (VA) X em um espaço

amostral s é uma função X: S→ℜ que atribui um
número real a cada ponto amostral em S
ou
•  Uma variável aleatória é uma variável que recebe um

valor numérico como resultado de um experimento.
Exemplos de Variável Aleatória
•  Tempo entre chegadas de clientes em um servidor
•  # visitas à CPU de uma requisição
•  Tempo de residência no sistema
•  Seja Rn o tempo de residência de um cliente j que
encontra n clientes na fila no momento de chegada
–  Xi = tempo de serviço de cliente i (iid)
–  Y = tempo residual do cliente em serviço quando o dado
cliente j chega
–  Então:
•  Ro = Xi,
•  Rn = Y + X1 + X2 + ... + Xn, n ≥ 1
Distribuição de Probabilidade de
uma Variável Aleatória
•  Função de distribuição acumulada (CDF) F da VA
X é definida para todos os números reais b,
b ∈ℜ, como:
F(b) = P(X ≤ b)
•  Propriedades de uma CDF
F é uma função não decrescente: se a < b ⇒ F(a) < F(b)
•  CDF é uma caracterização completa de uma VA.

Exemplo de CDF e CCDF
Intervalo de tempo entre check-ins Número de check-ins

de um mesmo usuário no Foursquare por usuário do Foursquare
CDF: P(X <= x) CCDF : P (X> x)
Variáveis Aleatórias Discretas
•  Pode assumir um número contável de valores
•  Função Probabilidade de Massa (PMF) p():
p(a) = P(X = a)
•  Propriedades:
–  p(xi) ≥ 0, i = 1, 2, ...
–  p(x) = 0, para todos outros valores de x
– 
•  CDF e PMF:
Função de Probabilidade de Massa
•  Representação gráfica da PMF
–  Seja X o número de visitas que cada requisição
faz ao disco
–  p(X): p(0) = 0.25 p(1) = 0.5 p(2) = 0.25
Histograma
•  Outra representação gráfica equivalente
–  Plota o número de vezes que a saída de um experimento
aleatório foi igual a cada ponto amostral
–  Ex: se total de requisições ao servidor = 1000
Variáveis Aleatórias Contínuas
•  Pode assumir um número incontável de valores
•  Função Densidade de Probabilidade (PDF) f():
•  Propriedades:
–  f(x) ≥ 0, ∀x
– 
•  CDF e PDF:
Métricas Simples para
Caracterização de uma
Variável Aleatória
Expectativa
•  Valor Esperado de uma VA X
X discreta X contínua
–  Ex: demanda média nos discos se:

•  90% das requisições visitam disco 1 e 10% visitam o disco 2,
•  tempo de serviço de disco 1 é 15 ms,
•  tempo de serviço do disco 2 é de 10 ms e
•  número de visitas por requisição é o mesmo para os dois
discos e igual a 20 (arquivos com mesmo tamanho)
D = D1 × 0.9 + D2 × 0.1 = 20 × 0.015 × 0.9 + 20 × 0.010 × 0.1

Expectativa
•  Expectativa de uma função da VA X
X discreta X contínua
–  Ex: utilização média dos discos para λ = 100

U = λD
U = U1 × 0.9 + U2 × 0.1
= λ × D1 × 0.9 + λ D2 × 0.1 =
= 100 × 20 × 0.015 × 0.9 + 100 × 20 × 0.010 × 0.1
Variância
•  Variância de uma VA X: variabilidade, espalhamento
dos valores de X
E(X) = E(Y) = 100

Var(X) = 162.5 Var(Y) = 4645.8
Variância
•  Variância de uma VA X: variabilidade, espalhamento
dos valores de X
Desvio Padrão e
Coeficiente de Variabilidade
•  Desvio Padrão SD(X)
•  Coeficiente de Variabilidade (CV)
–  Diferentemente de SD, que depende da unidade das medições,

o CV é uma medida sem unidade
–  Mede a quantidade de variabilidade relativo ao valor médio
–  Permite comparar a variabilidade existente em distribuições/
amostras diferentes
Distribuição de Probabilidade
•  Para uma caracterização completa de uma VA é preciso
determinar a sua distribuição de probabilidade
–  CDF ou PMF (se discreta) ou PDF (se contínua)
•  Existem várias distribuições discretas e contínuas na

literatura que seguem comportamento bem definido
–  Conhecê-las é importante, pois podemos aplicar resultados
previamente desenvolvidos
•  Ex: uma distribuição exponencial tem uma cauda mais leve
do que uma distribuição Pareto
Caudas pesadas têm impacto no consumo de recursos
(ex: tempo de serviço)
•  Vamos fazer uma revisão rápida. Maior detalhamento nos
caps 4 e 5 de A First Course in Probability, Sheldon Ross
Distribuições Discretas
•  Bernoulli
•  Binomial
•  Poisson
•  Geométrica
•  Zipf
•  Várias outras no livro do Ross
•  Bernoulli (p)
–  X = {0,1} X = {sucesso, falha}
–  p(0) = P(X=0) = 1-p
–  p(1) = P(X=1) = p
•  Binomial (n, p)
–  X = # sucessos em n experimentos independentes,
onde a probabilidade de sucesso em um experimento é p
E(X) = np Var(X) = np(1-p)

•  Poisson (λ)
–  Número de eventos independentes que ocorrem em um intervalo
de tempo (veja discussão em Ross, 4.8)
–  Número de chegadas em um servidor em 1 hora
–  Número de erros de impressão em uma página de um livro
E(X) = Var(X) = λ
λ = # médio de eventos que ocorrem no período
•  Poisson (λ)
–  Muito comumente usado para modelar chegada de sessões
de usuários
•  servidores Web, multimídia, banco de dados, ftp, e-mail
–  Sessões são iniciadas por usuários
•  Chegada de duas sessões tendem a ser independentes:
Poisson é uma boa aproximação
–  Contra-exemplo:
•  Chegada de requisições em um servidor Web
•  Premissa de independência não é válida: existe
dependência entre requisições para o arquivo HTML
e as imagens embutidas nele
•  Geométrica (p)
–  Número de experimentos (sucesso/falha) até que um
sucesso ocorra
E(X) = 1/p
Var(X) = (1-p)/p2
–  Número de retransmissões de mensagem

•  Zipf(α)
–  Comumente usada quando a distribuição é altamente
concentrada em poucos valores
•  Popularidade de arquivos em servidores Web/multimídia
–  90% dos acessos são para 10% dos arquivos
•  Popularidade de palavras na língua inglesa
–  Seja i, o elemento que ocupa a i-esima posição no ranking
de concentração
C é a constante de normalização
Zipf: lei das Potências
Distribuição Zipf
•  Modela popularidade dos remetentes de e-mails
para a UFMG
Distribuições Contínuas
•  Uniforme
•  Normal
•  Exponencial
•  Pareto
•  LogNormal
•  Gamma : ver Ross
•  Weibull : ver Ross

•  Uniforme (a,b)
–  X é uniformemente distribuída no intervalo [a,b], se
•  Normal (µ, σ) ou Gaussiana
µ= valor esperado
σ2 = variância
•  Exponencial (λ)
–  Quantidade de tempo até que determinado evento ocorra
–  Tempo entre chegadas de sessões em um servidor
λ = taxa de chegadas 1/ λ = tempo médio entre chegadas
P(X ≤ 1/λ ) = 1 – e-λ×1/λ = 1 – 1/e ~ 63%
E(X) = 1/ λ
Var(X) = 1/λ2 ⇒ SD(X) = 1/λ ⇒ CV(X) = 1
CV = 1 ⇒ exponencial (aproximação???)
Distribuições Exponencial e Poisson
Processo de
Chegadas
Poisson
Tempo entre Independência

Chegadas entre eventos
Exponencial
Distribuições Exponencial e Poisson
•  Seja uma distribuição Poisson que denote o número de eventos
N(t) em um intervalo de tempo t
•  Seja T1 o momento do 1o evento
•  Seja Tn o tempo entre o (n-1)-esimo e o n-esimo eventos
•  Sequência {Tn, n=1, 2, ...}: tempos entre chegadas
P(T1 > t) = P(N(t) = 0) = e -λt ⇒ T1 ∼ exponencial(λ)

P(T2 > t | T1 = s) = Prob (0 eventos em (s, s+t) | T1 = s)
= Prob (0 eventos em (s, s+t) (eventos Poisson
são independentes)
= e -λt ⇒ T2 ∼ exponencial(λ)
⇒ T1 , T2, ..., Tn são independentes e têm mesma
distribuição exponencial(λ)
Distribuição Exponencial
•  Exponencial (λ) :
P([X ≤ t + x] ∩ [X > t])
P(X ≤ t + x | X > t) =
P(X > t)
P(t < X ≤ t + x)
=
1 − P(X ≤ t)
Propriedade P(X ≤ t + x) − P(X ≤ t)
=
sem memória 1 − P(X ≤ t)
(memoryless) 1 − e − λ (t +x ) − (1 − e − λt )
=
1 − (1 − e − λt )
1 − e − λt e − λx −1+ e − λt
=
e − λt
e − λr (1 − e − λx ) − λx
= − λt = 1 − e = P(X ≤ x)
e
Propriedade Memoryless
•  Tempo de residência R de um cliente depende do # de clientes na
fila quando ele chega ao centro, dos tempos de serviços destes
clientes e do tempo que o cliente que está sendo servido no
momento de chegada ainda permanecerá em serviço.
–  Seja Xi a VA para o tempo de serviço de cliente i na CPU
–  Seja Xi: exponencial(µ) para todos os clientes
–  Seja Y a VA que denota o tempo residual que o cliente que está
em serviço no momento de chegada ainda permanecerá em
serviço
•  Y também tem distribuição exponencial com parâmetro µ
•  Tempo que ainda falta independe do tempo que já esteve em
serviço
Nós usamos este resultado quando derivamos R para MVA
•  Estado futuro não depende do estado passado
Propriedade Memoryless
•  Distribuição exponencial é a única
distribuição contínua que tem a
propriedade memoryless
•  Por sua vez, distribuição geométrica

é a única discreta que tem a propriedade
memoryless
(FAZER)
Outras Distribuições Contínuas
•  Pareto(α, k)
–  Tamanho de arquivos Web
–  Número de bytes em uma transferência FTP
•  Lognormal (µ, σ)
–  Duração de sessões de usuários e de requisições interativas a
vídeo
–  Tamanho de e-mails
–  Uma VA X é Lognormal (µ, σ) se Y = ln(X) é Normal (µ, σ)
Sumário
•  Caracterização de uma VA X
–  Média de X
–  Variância, desvio padrão, CV
–  CDF
–  PMF (discreta) ou PDF (contínua)
–  Modelo de distribuição e seus parâmetros
–  Várias outras
•  Melhor caracterização depende do que você está

tentando calcular
Caracterização: Exemplo
•  Tempo entre sessões em um servidor de vídeo
Combinando Variáveis Aleatórias
Funções de Distribuição Conjuntas
Se X e Y são independentes
FX,Y(a,b) = F(a)F(b)
pX,Y(a,b) = P(X=a)P(X=b)
fX,Y(x,y)= f(x)f(y) (contínuas)
Prob(X = a, Y ≤ b) =p(X=a)F,Y(b) (X discreta,

Y contínua)
E(g(X)h(Y)) = E(g(X))×E(h(Y))
Aplicações de Distribuição Conjunta
•  Distribuição multinomial:
p1
fluxo 1
p2
Chegada de fluxo 2
clientes
pm
fluxo m
⎛ n ⎞ n1 n 2 n m
P(X1 = n1 ∩ X 2 = n 2 ∩ ...∩ X m = n m ) = ⎜ ⎟ p1 p2 ...pm
⎝ n1n 2 ...n m ⎠
n!
= p1n1 p2n 2 ...pmnm
n1!n 2!...n m !
Aplicações de Distribuição Conjunta
•  Transações no servidor A têm tempo de execução TA ∼ exponencial(λ)
•  Transações no servidor B têm tempo de execução TB ∼ exponencial(µ)
•  Se duas transações T1 e T2 chegam nos sites A e B, respectivamente,
ao mesmo tempo e são servidas imediatamente, qual a probabilidade de
que T1 termine antes que T2
Funções de Variáveis Aleatórias
Soma de Poissons
•  X e Y são VAs independentes, X ∼ Poisson(λ1) e Y ∼ Poisson(λ2)
•  Qual a distribuição de Z=X+Y ?
Z=X+Y é Poisson(λ1+ λ2)

Aplicação: Soma de Poissons
•  Chegada de sessões em um servidor Web, clientes estão em
duas regiões. Mede separadamente em cada região e acha
Poisson. Qual o processo de chegada agregado?
Poisson λ1
Poisson λ2
Poisson λ1 + λ2+…+ λn
Poisson λn
•  Resultado se estende para n VAs independentes, cada uma com

distribuição Poisson
Soma de Exponenciais
•  X e Y são independentes, X ∼exponencial (λ) e Y ∼ exponencial(λ)
•  Qual a distribuição de Z=X+Y ?
Z=X+Y é Erlang com 2

estágios e parâmetro λ
Aplicação: tempo de operação de um sistema com redundância

(X = tempo de operação de componente principal, Y = tempo do standby)
Soma de Exponenciais
•  Genericamente: X1, X2, ... Xn, todas independentes e
exponencial(λ): Z = X1 + X2 + ... Xn ∼ Erlang de n estágios
•  Ex: tempo de processamento dividido em várias etapas. A duração

de cada etapa é exponencialmente distribuída com mesmo λ
Exp(λ) Exp(λ) Exp(λ) Exp(λ)
1 2 3 n
Erlang(n,λ)
•  Se Xi ∼ exponencial (λi), onde λi são diferentes

Z = X1 + X2 + ... Xn ∼ Hipoexponencial (ver Trivedi)
Distribuição dos Mínimos
•  Sistema composto de n componentes. Sistema funciona se
todos componentes estão operando corretamente
•  Tempo de falha : X1, X2, ...., Xn exponencial (λ)
•  Tempo de vida do sistema Z = min (X1, X2, ...., Xn)
P(Z ≤ z) = P (pelo menos um Xi ≤ z) = ?
P (exatamente um Xi ≤ z) = ?
Distribuição dos Mínimos
•  P(Z ≤ z) = P (pelo menos um Xi ≤ z)
p = (1-e-λz)
Z tem distribuição
exponencial com
parâmetro λn
Distribuição dos Máximos
•  n tarefas independentes : X1, X2, ...., Xn: exponencial (λ)
•  Tempo de resposta = tempo de execução da tarefa mais longa
Z = max (X1, X2, ...., Xn)
–  Ex: tempo de resposta de máquina de busca composta de n
processadores executando em paralelo. Cada máquina processa
consulta em uma partição do dicionário
Front-end:
atraso desprezível
Distribuição dos Máximos
•  n tarefas independentes : X1, X2, ...., Xn: exponencial (λ)
•  Tempo de resposta = tempo de execução da tarefa mais longa
Z = max (X1, X2, ...., Xn)
Exercício
Considere um computador paralelo com n processadores.
Sejam X1, X2, ..., Xn, os tempos de falha dos processadores,
cada um exponencialmente distribuído com parâmetro λ.
Qual a distribuição da capacidade de processamento Cn do
computador?
Ordene Xi’s em ordem crescente.

Seja Yi a VA que ocupa a i-esima posição: Y1 = min(Xi)
Cn = nY1 + (n-1) (Y2 – Y1) + (n-2)(Y3-Y2)+ ... +

(n-j)(Yj+1– Yj)+ ... + (Yn – Yn-1)
Y1 = min(Xi) ∼ exponencial(nλ)
Exemplo (cont.)
Sejam W1, W2, ..., Wn-j os tempos restantes de processamento
de cada um dos processadores ainda operando depois que j
processadores falharam
Yj+1 – Yj = min(W1, W2, ..., Wn-j)
Pela propriedade memoryless da exponencial

Wi ∼ exponencial(λ)
Logo Yj+1 – Yj ∼ exponencial((n-j) λ)

Exemplo (cont.)
Lembre que: Cn = nY1 +... +(n-j)(Yj+1– Yj)+ ... + (Yn – Yn-1)
Quais as distribuições de: (n-j)(Yj+1– Yj) e nY1?
Se X ∼ exponencial(λ):
Y = rX ∼ exponencial(λ/r)
Y1 = min(Xi) ∼ exponencial(nλ) → nY1 ∼ exp (nλ/n) ~ exp(λ)

Yj+1 – Yj ∼ exponencial((n-j) λ) → (n-j)(Yj+1– Yj) ∼
exp((n-j)λ/(n-j)) ~ exp(λ)
Logo Cn = soma de exponencial(λ): Cn ∼ Erlang(λ,n)

Análise Aplicada A Desempenho

Enviado por

Direitos autorais:

Formatos disponíveis

Análise Aplicada A Desempenho

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Análise Aplicada A Desempenho

Enviado por

Direitos autorais:

Formatos disponíveis

Revisão de Estatística

• Uma variável aleatória (VA) X em um espaço

• Uma variável aleatória é uma variável que recebe um

• Propriedades de uma CDF

F é uma função não decrescente: se a < b ⇒ F(a) < F(b)

• CDF é uma caracterização completa de uma VA.

Intervalo de tempo entre check-ins Número de check-ins

– Ex: demanda média nos discos se:

D = D1 × 0.9 + D2 × 0.1 = 20 × 0.015 × 0.9 + 20 × 0.010 × 0.1

– Ex: utilização média dos discos para λ = 100

E(X) = E(Y) = 100

• Coeficiente de Variabilidade (CV)

– Diferentemente de SD, que depende da unidade das medições,

• Existem várias distribuições discretas e contínuas na

E(X) = np Var(X) = np(1-p)

– Número de retransmissões de mensagem

• Gamma : ver Ross

• Weibull : ver Ross

• Normal (µ, σ) ou Gaussiana

λ = taxa de chegadas 1/ λ = tempo médio entre chegadas

P(X ≤ 1/λ ) = 1 – e-λ×1/λ = 1 – 1/e ~ 63%

Tempo entre Independência

P(T1 > t) = P(N(t) = 0) = e -λt ⇒ T1 ∼ exponencial(λ)

• Por sua vez, distribuição geométrica

• Melhor caracterização depende do que você está

fX,Y(x,y)= f(x)f(y) (contínuas)

Prob(X = a, Y ≤ b) =p(X=a)F,Y(b) (X discreta,

Z=X+Y é Poisson(λ1+ λ2)

• Resultado se estende para n VAs independentes, cada uma com

Z=X+Y é Erlang com 2

Aplicação: tempo de operação de um sistema com redundância

• Ex: tempo de processamento dividido em várias etapas. A duração

Exp(λ) Exp(λ) Exp(λ) Exp(λ)

• Se Xi ∼ exponencial (λi), onde λi são diferentes

Ordene Xi’s em ordem crescente.

Cn = nY1 + (n-1) (Y2 – Y1) + (n-2)(Y3-Y2)+ ... +

Yj+1 – Yj = min(W1, W2, ..., Wn-j)

Pela propriedade memoryless da exponencial

Logo Yj+1 – Yj ∼ exponencial((n-j) λ)

Quais as distribuições de: (n-j)(Yj+1– Yj) e nY1?

Y1 = min(Xi) ∼ exponencial(nλ) → nY1 ∼ exp (nλ/n) ~ exp(λ)

Logo Cn = soma de exponencial(λ): Cn ∼ Erlang(λ,n)

Você também pode gostar

•  Uma variável aleatória (VA) X em um espaço

•  Uma variável aleatória é uma variável que recebe um

•  Propriedades de uma CDF

•  CDF é uma caracterização completa de uma VA.

–  Ex: demanda média nos discos se:

–  Ex: utilização média dos discos para λ = 100

•  Coeficiente de Variabilidade (CV)

–  Diferentemente de SD, que depende da unidade das medições,

•  Existem várias distribuições discretas e contínuas na

–  Número de retransmissões de mensagem

•  Gamma : ver Ross

•  Weibull : ver Ross

•  Normal (µ, σ) ou Gaussiana

•  Por sua vez, distribuição geométrica

•  Melhor caracterização depende do que você está

•  Resultado se estende para n VAs independentes, cada uma com

•  Ex: tempo de processamento dividido em várias etapas. A duração

•  Se Xi ∼ exponencial (λi), onde λi são diferentes