16/12/2013
Leis Operacionais
Avaliação de Desempenho de
Sistemas Discretos
Parte V: Análise Operacional
Professor: Reinaldo Gomes
[email protected]
Parâmetros Operacionais
Representam as informações que podem ser medidas
durante um intervalo de observação finito
Valores diferentes podem ser obtidos de uma observação para outra
Básicos: valores medidos diretamente durante um período de
observação finito
Relações existentes no sistema que não dependem de
nenhuma suposição sobre seu funcionamento
Distribuição dos tempos de serviço/tempo entre chegadas
Regras gerais e “robustas” que são muito úteis porque:
Muito simples
Baseadas em dados obtidos facilmente
Fornecem métricas de desempenho úteis
“The operational analysis of queueing network models”,
P.J. Denning e J.P. Buzen, Computing Surveys, vol. 10,
No. 3, September 1978, pp.225-261
Estabelece relações entre quantidades baseadas em dados que
podem ser medidos ou conhecidos
Parâmetros Operacionais
T = intervalo de observação
Ci = número de conclusões
Ai = número de chegadas
Bi = tempo de ocupação
Taxa de chegadas
Número de fregueses, quantidade de fregueses em fila, ...
Secundários: Calculados através dos valores obtidos pelos
parâmetros básicos
Vazão
Utilização dos servidores, tempo médio de serviço, ...
Utilização
Tempo médio de serviço
Caixa Preta
Parâmetros Operacionais
Exemplo 1
Durante um período de observação de 1 minuto, um
único recurso (ex., CPU) esteve ocupado por 36
segundos. Um total de 1800 transações chegaram ao
sistema. O número total de transações processadas
também foi 1800. Determine:
A taxa de chegadas
O tempo médio de serviço por transação
A utilização do sistema
A vazão do sistema
Parâmetros Operacionais
Exemplo 1
T = 60s
B1 = 36s
A1 e C1 = 1.800 transações
S1 = B1 / C1 = 36/1800 = 1/50 s por transação
U1 = B1 / T = 36/60 = 60%
λ1 = A1 / T = 1800/60 = 30 tps
X1 = C1 / T = 1800/60 = 30 tps
1
16/12/2013
Leis Operacionais
Lei da Utilização
Relações Fundamentais
Utilização
Lei da Utilização
Lei da Demanda de Serviço
Lei do Fluxo Forçado
Se Ci = Ai (todos os fregueses foram atendidos –
sistema aberto), então Xi = λi, tendo:
Lei de Little
Lei do Tempo de Resposta Geral
Lei do Tempo de Resposta Interativa
Lei da Utilização
Lei da Utilização
X= C/T
U=B/T
(No. Transações /
Intervalo Observação) = C / T
λ tps
U
X tps
λ
U
ped./s
X ped./s
S
S
S=B/C
U=S*X
(Tempo Ocupado /
No. Transações)
=B/C
Lei da Utilização
No caso do recurso i possuir mi servidores, temos
que a utilização é obtida através de:
Se o sistema considerar a chegada de fregueses
através de múltiplas classes de serviço:
Lei da Utilização
Exemplo 2
A capacidade de um canal de comunicação é 56 Kbps e é
usado para transmitir pacotes de 1.500 bytes à taxa de 3
pacotes/s. Qual a utilização deste canal?
Inicie identificando as variáveis operacionais fornecidas ou
que podem ser obtidas dos dados
A vazão do recurso X1 é 3 pacotes/s
O tempo médio serviço (transmissão) por pacote
Cada pacote tem 1500 bytes = 12000 bits = 12 Kbits
12 kbits / 56 kbps = 0,214 segundos / pacote = S1
Lei da utilização: S1 * X1 = 0,214 * 3 = 0,642 = 64,2%
2
16/12/2013
Lei da Utilização
Exemplo 3
Um servidor de BD tem uma CPU e três discos. Todas as
transações tem demandas semelhantes para os recursos e o
servidor BD recebe demanda constante de serviço (modelo
com RF fechada). Medições feitas em uma hora indicam
13680 transações executadas, com o número de r/w por
segundo e utilização de cada disco como segue:
Disco1: 24 r/s + 8 w/s = 32 IO/s e U1 = 0,30
Disco2: 28 r/s + 8 w/s = 36 IO/s e U2 = 0,41
Disco3: 40 r/s + 10 w/s = 50 IO/s e U3 = 0,54
Qual o tempo médio por pedido gasto em cada disco?
Qual a vazão do SBD?
Lei da Utilização
Exemplo 4
Uma rede transmite 1000 pacotes/segundo. Cada
pacote tem um tempo médio de transmissão = 0.15
msec. Qual é a utilização deste rede?
Solução 4: Da Lei da Utilização
1000 x 0.00015 = 0.15 = 15%
Lei da Utilização
Exemplo 3
A vazão de cada disco, Xi (i = 2,3,4) é o número total
de IO / s (a CPU é recurso 1)
Usando a Lei de Utilização, os tempos médios de
serviço são:
S2 = U2 / X2 = 0,30 / 32 = 0,0094 s
S3 = U3 / X3 = 0,41 / 36 = 0,0114 s
S4 = U4 / X4 = 0,54 / 50 = 0,0108 s
A vazão, X0, do sistema é C0 / T = {13.680 transações /
[1h (=3.600 s)]} = 3,8 tps
Lei da Demanda de Serviço
Demanda de Serviço associada a um recurso +
conjunto de solicitações (demandas) ao recurso
Demanda de Serviço = Di é o tempo médio total
gasto por um pedido típico de certo tipo no recurso i
(podemos definir Di,r para múltiplas classes)
Soma de todos os tempos de serviços nas “visitas” do
pedido (freguês) ao recurso
Calculada diretamente da utilização do recurso e vazão do sistema
Não inclui tempo de espera em fila (apenas “serviço”)
No caso de vários pedidos visitando o recurso, a demanda
de serviço é a média das somas dos tempos de serviço para
cada tipo de pedido naquele recurso
Lei da Demanda de Serviço
Lei da Demanda de Serviço
Exemplo 5
6 transações realizam 3 operações de I/O em disco
Tempo (ms) para cada I/O e transação (T1-6):
IO1 T1=10; T2=15; T3=13; T4=10; T5=12; T6=14
IO2 T1=12; T2=12; T3=12; T4=11; T5=13; T6=12
IO3 T1=11; T2=14; T3=11; T4=11; T5=11; T6=13
Soma 33
41
36
32
36
39
Média = 36,2 (ms)
Esta é a demanda de serviço no disco devido à carga
das 6 transações
S1
S2
S3
S4
Demanda de serviço (D)
U
X0= (C0 / τ ) tps
D = (Ui * τ) / C0 = Ui / (C0 / τ) = Ui / X0
3
16/12/2013
Lei da Demanda de Serviço
Lei da Demanda de Serviço
Exemplo 6
S1
S2
S3
S4
Demanda de serviço (D)
U
Um Servidor Web (SW) é monitorado por 10 minutos
(600s) e a sua CPU apresenta 90% de utilização (neste
intervalo). O log do SW revela que 30.000 pedidos são
processados no intervalo. Qual a demanda de serviço
da CPU para o SW?
Τ = 600s
X0 = 30000 / 600 = 50 pedidos/s
UCPU = 0,9
DCPU = UCPU / X0 = 0,9/50 = 0,018 s/pedido
i
Di = Σ1 Si = Vi Si
Lei do Fluxo Forçado
Lei do Fluxo Forçado
Maneira simples de relacionar vazão do recurso i
(Xi) com a vazão do sistema (X0)
Igual ao número de visitas de um pedido (freguês) a
aquele recurso vezes a vazão do sistema
Em um sistema aberto a vazão é o número de transações
que deixam o sistema por unidade de tempo
Em sistemas fechados a vazão é o número de transações
que voltam para a entrada do sistema por unidade de tempo
Xi = Vi * X0
No caso de múltiplas classes: Xi,r = Vi,r * X0,r
A taxa de visita pode ser obtida através de:
Lei de Little
Exemplo 7
Qual o número médio de I/Os em cada disco do
Exemplo 3?
Solução 7
Vi = Xi / X0, assim:
V1= 32 / 3,8 = 8,4 visitas ao disco 1 por transação ao BD
V2= 36 / 3,8 = 9,5
V3= 50 / 3,8 = 13,2
Lei de Little
Indica o número médio de clientes em um
dispositivo
λ tps
X tps
BAR
W
S
R
No. médio de
fregueses no
BAR
=
Taxa média
de chegadas X
ao BAR
Tempo médio
gasto no BAR
λ = Taxa média de chegada de fregueses (transações)
X = Vazão média
W = Tempo médio de espera
S = Tempo médio de serviço
R = Tempo médio de resposta
4
16/12/2013
Lei de Little
Lei de Little
Aplicação a filas únicas
Algumas observações
Aplicável a qualquer “caixa preta”
À fila
λ
X
N
Ao servidor
Ao sistema: fila + servidor
R
Sistema com múltiplos recursos
Equilíbrio ⇒ λ = X
N = λR = X R
Lei de Little
Exemplo 8
Considere um grande portal que oferece serviços
gratuitos de e-mail para 1.5 milhão de fregueses.
Durante o horário de pico, a gerência estima que 15%
dos fregueses estão ativos.
Cada freguês envia uma média de 4.5 e-mails por hora
(3600 s) neste horário. O tamanho médio das
mensagens de e-mail é 8400 bytes. Cada mensagem
leva 4 segundos para ser processada e despachada.
Qual deve ser o tamanho médio da área de spool de emails?
Lei de Little
Exemplo 9 (Atraso em roteador)
Relatórios SNMP para o roteador 373.57.7.300
informam uma fila média de 3.0 datagramas e uma
vazão medida de 380 kB/segundo.
O datagrama IP tem em média 1200 bytes
Lei de Little
Exemplo 8 – Solução
Vazão= fregueses ativos x e-mails / s
Vazão = (1500000 x 0.15) x (4.5 / 3600)
Vazão = 281.25 e-mails / s
Lei de Little
n=X*R
No_de e-mails = Vazão x Tempo de Processamento
No_de e-mails = 281.25 e-mails/s * 4 s = 1125
Tamanho médio da área de Spool = 1125 x 8400 = 9.01
MB
Lei de Little
Exemplo 9 (Atraso em roteador) – Solução
Usando a Lei de Little
Tamanho médio de fila = Vazão * Atraso médio
Atraso médio = Tamanho médio de fila / Vazão
Tamanho médio de fila = 3.0 Datagramas * 1.200
BpDatagrama = 3600 Bytes
Atraso médio = 3600 Bytes / 380 kBps = 9.47 msec
Qual o atraso médio de processamento neste roteador?
5
16/12/2013
Lei do Tempo de Resposta Geral
Utilizado para calcular o tempo de resposta em
sistemas onde temos um terminal por usuário e o
resto do sistema é dividido por todos eles, o que
permite o tratamento de sistemas não balanceados
...
Sistema
Central
Lei do Tempo de Resposta Geral
Se dividirmos os dois lados por X, teremos:
Pela Lei do Fluxo Forçado temos que Xi = XVi ,
portanto Vi = Xi/X
Podemos então simplificar a expressão acima para:
Se considerarmos a Lei de Little (Q = X*R) no
subsistema central teremos:
Q = Q1 + Q2 + ... + QN, ou
XR = X1R1 + X2R2 + ... + XNRN
Lei do Tempo de Resposta Interativa
Um sistema interativo, devemos considerar 4
características: o número de clientes usando o
sistema (M), o “think time” (Z), o tempo médio de
resposta do servidor (R) e vazão do sistema (X0)
M = M + N (No. Médio de clientes nos terminais + No.
Médio de fregueses no servidor)
Pela Lei de Little: M = X0 * Z e N = X0 * R
Lei do Tempo de Resposta Interativa
Ou simplesmente:
Lei do Tempo de Resposta Interativa
Exemplo 10
Um portal corporativo provê serviços Web para os
funcionários da empresa. Em média, 500 empregados
estão online navegando no portal a qualquer instante.
O log do portal revela que 6.480 pedidos são
processados por hora (em média) e o “tempo médio de
processamento” é de 5s
Qual é o tempo médio entre a chegada de resposta a
um pedido e um novo pedido ser submetido por um
funcionário?
Logo:
Lei do Tempo de Resposta Interativa
Exemplo 10 – Solução
Precisamos calcular Z
R = M/X0 – Z
A vazão X0 = 6480 / 3600 = 1.8 pedidos / s
M: o número de funcionários online = 500
Z = M/Xo – R = 500 / 1.8 – 5 = 273 s
Lei do Tempo de Resposta Interativa
Exemplo 11 - Sistema fechado
Suponha que 50 estações-de-trabaho são servidas por
um servidor de arquivos com fila única e que cada
estação faz processamento independente (“think time”)
por 0.5 s em média entre pedidos consecutivos ao
servidor
O servidor de arquivos atende a 80 pedidos/s (X0 = 80)
Qual o tempo de resposta?
Solução 11
R = M/X0 - Z = 50 / 80 - 0.5 = 0.125 s
6
16/12/2013
Leis Operacionais - Resumo
Lei da Utilização
Lei da Demanda de Serviço
Lei do Fluxo Forçado
Lei de Little
Di = Ui / X0
Xi = Vi * X0
N = λ*R ou N = X*R
Lei do Tempo de Resposta Geral
Lei do Tempo de Resposta Interativa
Limites de Desempenho
Principais Limites
Limites superiores para a vazão
Limites inferiores para tempo resposta
Limite de utilização (dispositivo de gargalo)
Limites de Desempenho
As Leis Operacionais nos oferecem um conjunto de
medidas de desempenho relacionadas com os
parâmetros usados no modelo
Informações sobre os limites possíveis para o
sistema são extremamente importantes
Verificar se a carga máxima do sistema suporta a
demanda que será passada para ele
Verificar se um limite para o tempo de resposta pode
ser atendido
Verificar se um determinado recurso suporta a carga de
trabalho necessária
Dispositivo de Gargalo
Combinando a Lei do Fluxo Forçado com a Lei da
Utilização, nós temos:
Utilização do i-ésimo dispositivo é:
O cálculo desses limites podem:
Ser obtidos sem resolver modelo
Levar em consideração a demanda de serviço
Considerar o gargalo
Recurso com maior utilização ou com maior demanda de
serviço
Dispositivo de Gargalo
Comentários
Dispositivos de delay podem possuir utilizações mais
altas sem gerar nenhum problema no funcionamento
do sistema, portanto, eles não representam gargalos
Apenas servidores entram no cálculo do maior Di
O gargalo do sistema é o limitador para se obter uma
maior vazão, portanto:
Melhorar o funcionamento do gargalo do sistema tende a
trazer mais benefícios do que melhorar o desempenho de
outros componentes
A identificação do gargalo deve ser um dos primeiros
passos do em uma avaliação de desempenho
Onde
representa a demanda total de
serviço no dispositivo para todas as visitas de uma
transação
O dispositivo que possuir o maior valor de Di tem a
maior utilização e será o gargalo do sistema
Limite para a vazão
O limite para a vazão de um sistema é obtido
através de X0, que é representado pela expressão
Para um sistema com uma carga de trabalho
elevada temos que o limite superior para a vazão é
obtido através de:
X0 ≤ 1 / max {Di}
Onde o valor de Di se refere ao gargalo do sistema
7
16/12/2013
Limite para a vazão
Limite para a vazão
Se considerarmos que um sistema possui carga de
trabalho leve, com N fregueses em execução
concorrente, ao aplicarmos a Lei de Little teremos:
N = R * X0
Mas, para um sistema com K recursos, o tempo de
resposta R é pelo menos a soma das demandas de
serviço (na ausência de filas)
ou
Sistema
Interativo
Limite para a vazão
Exemplo 12 – Solução
A demanda máxima de serviço determina a vazão máxima
Como a CPU não é o gargalo (UCPU = 35% vs. 30%, 41% e
54% - vide Solução 3), vazão máxima é obtida quando a
demanda em cada disco é igual à média dos valores iniciais
DCPU = UCPU / X0 = 0,35 / 3,8 = 0,092 s
D1 = U1 / X0 = 0,30 / 3,8 = 0,079 s
D2 = U2 / X0 = 0,41 / 3,8 = 0,108 s
D3 = U3 / X0 = 0,54 / 3,8 = 0,142 s
No caso acima, vazão máxima = 1 / 0,142 = 7,04 tps
D1 = D2 = D3 = média (0,079+0,108+0,142)/3 = 0,1097 s
Vazão máxima neste caso = 1 / 0,1097 = 9,12 tps (29,5% a mais.
Alcançado apenas com balanceamento)
Exemplo 12
Considere o SBD do problema 3. Assuma que a
demanda de serviço na CPU seja fixada em 0,092 s
(utilização de 35% e vazão do sistema X0 = 3.8 tps –
vide Problema 3) . Quais valores das demandas de
serviço nos 3 discos produzem a maior vazão possível
do sistema (enquanto mantém constante a soma das
demandas nos 3 discos)?
OBS: Problema acima é de balanceamento de carga
(i.e., maximizar a vazão pelo deslocamento de carga
entre os discos)
Limite para tempo de resposta
Considerando novamente a Lei de Little, temos que
o tempo de resposta é:
R = N / X0
Pelo limite de vazão do sistema sabemos que X0
corresponde a
, portanto:
logo
Limite para tempo de resposta
Exemplo 13
Se considerarmos novamente o servidor BD do
problema 3, qual o limite inferior para o tempo de
resposta do sistema?
Solução
A soma das demandas de serviço é
(0,092+0,079+0,108+0,142) = 0,421; com o máximo
de 0,142 s
Os limites para TR são portanto:
R ≥ max [0,142 * N, 0,421]
8