Introdução à Avaliação de Desempenho

N. L. VijaykumarLAC/INPE

vijay@lac.inpe.br

IntroduçãoSistemas Modernos Complexos

ComputaçãoComunicaçãoManufaturaAplicações Espaciais

Como detectar e compreender o seu comportamento antes de construir o sistema?

O que é Avaliação de Desempenho

Análise de desempenho é um tópico importante e vários esforços estão sendo dedicados a este tópico.Estudo do comportamento de um sistemaDetectar gargalos bem antes da sua implementação.O ideal é aplicar este processo na fase inicial da construção de um sistema.

O que é Avaliação de Desempenho (cont.)

Na realidade, esta fase é ignorada em geral e nem sempre é possível corrigir o problema.Mesmo que seja possível corrigir o problema, nem sempre é uma alternativa eficiente e pode ser muito caro.Às vezes, é mais barato reconstruir o sistemaOs objetivos de desempenho são critérios pré-definidos.

O que é Avaliação de Desempenho (cont.)

Estes critérios podem ser medidos. Por exemplo, tempo de resposta, rendimento, utilização de recursosOutro fator fundamental é a possibilidade de associar algum tipo de custo a vários cenários

O que é Avaliação de Desempenho (cont.)

As métricas são baseadas no comportamento de sistemas em função de tempo.As métricas podem ser observadas por um usuário ou uma “ entidade” externa.

O que é Avaliação de Desempenho (cont.)

Disponibilidade (Availability): Fração de tempo que um recurso é disponível para uso em operação normal.

Um servidor que está fora por uma hora por dia tem uma disponibilidade de 0.96

O que é Avaliação de Desempenho (cont.)

Gargalo (recurso): Em qualquer sistema com mais de um componente, o gargalo é o recurso com o menor rendimento máximo. O desempenho do gargalo restringe o desempenho de todo o sistema.

O que é Avaliação de Desempenho (cont.)

Latência (Tempo de Resposta): Tempo (delay) entre o início e término de uma operação ou seja tempo entre a solicitação de um serviço e o atendimento daquele serviço.

O que é Avaliação de Desempenho (cont.)

Banda (Pathlength): Tempo de processamento (Processing time per unit of work).

Utilização dividida por rendimento.

O que é Avaliação de Desempenho (cont.)

Rendimento (Throughput ou Capacity): tarefa completada por unidade de tempo ou taxa com a qual novos resultados chegam

Mensagens por segundo.Transações por minuto.

O que é Avaliação de Desempenho (cont.)

Utilização: Fração de tempo que um recurso (CPU, disco, rede) está ocupado.

O que é Avaliação de Desempenho (cont.)

Benefícios ao considerar desempenhoSe torna parte intrínseca do projetoRespostas a perguntas como “ Projeto satisfaz os objetivos especificados?”Conhecimento a priori das restrições impostas ao projetoPode-se evitar problemas quando construir de fato o projeto

Características de sistemasSistemas reativos

Reagem a algum estímulo

Desligado Ligado

Soluções para obtenção de desempenho

Métodos empíricosRealizar experimentos em modelos simples que já foram implementados e estão disponíveis

SimulaçãoComportamento do sistema a ser avaliado é reproduzidoExecutado por um programa de computadorEstatísticas obtidas são interpretadas para se ter uma idéia do desempenho

Soluções para obtenção de desempenho (cont.)

Métodos matemáticosSoluções analíticasCadeias de Markov

Propriedade “ memory-less” (distribuição exponencial)

Ocorre com freqüência em aplicações como: tempo de vida de determinados equipamentos, chamadas telefônicas, etc.Ocorrência de um próximo evento está condicionadaapenas ao seu estado atual

Soluções para obtenção de desempenho (cont.)

Simulação

Soluções para obtenção de desempenho (cont.)

Simulação pode ser definida como um processo de criar um MODELO de um sistema que já existe ou o que se propõe a implementar para:

Identificar ou compreender fatores que controlam o sistema.Prever o comportamento futuro do sistema.

Soluções para obtenção de desempenho (cont.)

Sistemas descritos quantitativamente por equações ou regras podem ser simulados.Simulações ESTÁTICAS: sistema não muda com o tempo.Simulações DINÂMICAS: sistema evolve com o tempo e o objetivo é compreender com esta evolução é realizada.

Soluções para obtenção de desempenho (cont.)

Simulação Dinâmica – prever a maneira como um sistema evolue e responde ao seu ambiente para poder identificar quaisquer mudanças que ajudariam o sistema a desempenhar da forma desejada.

Soluções para obtenção de desempenho (cont.)

Simulação da população de salmão num rio.

Prever mudanças na população.Compreender quantitativamente os impactos de algumas possíveis ações (pesca, perda de “ habitat” ) para garantir que a população não seja extinta no futuro.

Soluções para obtenção de desempenho (cont.)

SimulaçãoParâmetros – constante durante toda a simulaçãoEstados – mudanças no tempoOutras variáveis – restante das variáveis

Soluções para obtenção de desempenho (cont.)

Linguagens: SLAM, ECSL, SIMANAlto nível e permitem desenvolvimento rápido quando comparadas com C++ e FORTRAN.

Simuladores: Witness, ProModel, NS, TaylorII

Data driven ou seja pouca ou nenhuma programação necessária. Porém apresentam limitações.

Soluções para obtenção de desempenho (cont.)

Sistemas Híbridos: combinam a flexibilidade da linguagem de Simulação com a facilidade de user-friendliness de um data driven system.

Arena

Soluções para obtenção de desempenho (cont.)

Representação gráfica de uma cadeia de Markov

0 1

2

0.10.2

0.20.2

ModelagemPor que MODELAGEM?Os modelos são mais simplesEmbute somente as características essenciaisCusto quase desprezívelPara avaliar desempenho de um sistema reativo, é preciso descrever o comportamento de um sistema ou seja é preciso MODELAR

Modelagem (cont.)Modelagem será baseada em que?

Texto?Gráfico?

Basta ter uma representação do modelo em texto ou em gráfico?

É preciso associar alguma técnica (Simulação ou Solução Analítica) para obter o desempenho do sistema

Modelagem (cont.)Representação por texto

Linguagem NaturalLinguagem Específica e “ costurada” para lidar com modelagem de um sistemaLinguagem baseada na tecnologia de interoperabilidade XML (eXtensible Markup Language)

Modelagem (cont.)Representação gráfica

Diagramas de estadosRedes de FilasRedes de PetriStatechartsOutros …

Modelagem (cont.)A pergunta continua

QUAL A TÉCNICA A SER ASSOCIADA A UMA REPRESENTAÇÃO?

SimulaçãoSolução Analítica (escopo do curso)

Cadeia de Markovprocesso estocástico, caracterizado pela propriedade “ memoryless” ou sem memória ou esquecimentose o estado do sistema é conhecido em um determinado instante, o comportamento do sistema no estado subseqüente é independente da história passada do processo, dependendo apenas deste estado atual

Diagramas de estadoRelembrando a representação gráfica de uma Cadeia de Markov

0 1

2

0.10.2

0.20.2

Diagramas de estado (cont.)

Conjunto de estados e conjunto de transições entre os estadosUma escolha natural para representar Cadeia de Markov

Os eventos e1, e

2, e

3 e e

4

devem seguir uma distribuiçãoEXPONENCIAL

Obtenção de medidas de desempenho

Resolver Cadeia de MarkovMétodos Diretos

Eliminação GaussAlgorítmo Grassmann

Métodos IterativosPotênciaJacobGauss-SeidelSobre Relaxação Sucessiva (Successive Over Relaxation)

Obtenção de medidas de desempenho (cont.)

Resolvendo a cadeia, obtém-se probabilidades limite

Diagramas de Estado: Desvantagens

Como ficaria a representação gráfica com centenas de estados e centenas de arcos de transição entre estes estados?Sistemas modernos necessitam que paralelismo seja consideradoNecessidade de buscar técnicas de Necessidade de buscar técnicas de mais alto nívelmais alto nível

Redes de Filas

Redes de Filas (cont.)Notação de Kendal: A/S/m/[B]/[K]/[SD]

A(*): Distribuição do Tempo entre chegadasS(*): Distribuição do Tempo de Serviçom: Número de ServidoresB:Capacidade do Sistema, ou número de buffers (se omitidacapacidade infinita)K: Tamanho da População (se omitido, tamanho infinito)SD: Disciplina de Serviço, comuns são: FIFO, LCFS, ... (se omitida disciplina FIFO)

(*)Distribuições mais comuns sãoM (Exponencial), Ek (Erlang), Hk(Hiperexponencial), D(Deterministica), G (Geral)

Redes de Filas (cont.)

Redes de Filas (cont.)

Redes de Filas (cont.)

 = Taxa de chegada

= Taxa de Serviço

Redes de Filas (cont.)Número médio de clientes (jobs) numa fila = Número médio de clientes no sistema = Tempo médio por cliente na fila =Tempo médio por cliente que permance no sistema = Intensidade de tráfego =

•          

¿

Redes de PetriTécnica de modelagem com forte base matemáticaPermite representar sistemas paralelos, concorrentes, assíncronos e não-determinísticosTécnica muito conhecida e popular inclusive com conferências específicas

Redes de Petri (cont.)

Redes de Petri (cont.)Redes de Petri coloridasRedes de Petri HierárquicasRedes de Petri Temporadas DeterminísticasRedes de Petri EstocásticasRedes de Petri Estocásticas Generalizadas

StatechartsCriados por Harel em 1987Extensão dos Diagramas de EstadoPermite representar Hierarquia, Paralelismo e SincronizaçãoElementos básicos: Estados, Condições, Eventos, Ações, Transições, Variáveis, Expressões

Statecharts (cont.)Eventos externos (taxa estocástica)Eventos internos

true [Condition]Exemplo: true [in(Estado A)]

exit (Estado A)entered (Estado A)ação

Statecharts (cont.)

Hierarquia

Statecharts (cont.)

Atividades Paralelas

Statecharts (cont.)

Sincronização eIndependência

Statecharts (cont.)

Entrada por Histórico

Statecharts (cont.)A solução para tratar a especificação em Statecharts para obtenção de medidas de desempenho

Se possuir a Cadeia de Markov do sistema, resolvendo a cadeia, obtém-se as probabilidades limiteEntão, CONVERTER a especificação Statecharts para uma Cadeia de Markov

Statecharts na Avaliação de Desempenho

Statecharts na Avaliação de Desempenho (cont.)

Statecharts na Avaliação de Desempenho (cont.)

Statecharts na Avaliação de Desempenho (cont.)

Statecharts na Avaliação de Desempenho (cont.)

Statecharts na Avaliação de Desempenho (cont.)

Exemplo

Exemplo: a correspondente cadeia de Markov

Servidor de Arquivos em Ambiente Distribuído

Servidor de Arquivos em Ambiente Distribuído

P­Queue

Busy­P

Free­P

T1

T5

T3

T2

T4

T6

D­Queue

Busy­D

Free­DSource

Exit

• •

•

Servidor de Arquivos em Ambiente Distribuído

Proc

Free

tr[not in (Free.Proc_Q)] /dec_p P

•

Busy 0.04eos

{p}/ inc_d

{1­p}

Disc

Free

tr[not in (Free.Disc_Q)] /dec_d

•

Busy     0.05

eos/ inc_p

Proc_Q

Free   Busy

inc_p

dec_p

Proc_D

Free   Busy

inc_d

dec_d

•• •

Ready   0.083

λ/inc_p

Source

Servidor de Arquivos em Ambiente Distribuído

 

Measurement Queuing NetworksHierarchical 

Decomposition

Petri NetsDNAnet 

Simulation

StatechartsSmpl 

Simulation

Network Utilization 0.168 0.169  0.166

Processor Utilization

0.168 0.168  0.167

Disc Utilization 0.084 0.083  0.083

Network throughput

5.065 5.070  5.014

Processor throughput

4.221 4.202  4.199

Disc throughput 1.688 1.667  1.674

 

Servidor de Arquivos

Servidor de Arquivos: medidas de desempenho

Sistema de Manufatura

Sistema de Manufatura: medidas de desempenho

Petri Nets Statecharts

M1 0.9028 0.9002

M2 0.9028 0.8948

R1 0.0893 0.0887

R2 0.1797 0.1814

PerformChartsSoftware – especificação de um sistema reativo em Statecharts reativo para gerar probabilidades limite associando a especificação à Cadeia de MarkovInterface – XML (PcML – PerformCharts Markup Language)Interface – Gráfica (está sendo desenvolvida em cooperação com UFPa)

PerformCharts (cont.)

PerformCharts (cont.)

PerformCharts: Extensões

E q u i p m e n t

P

B

r

a

f{ 1 ­ p }

W

c

{ p }p

TransiçõesProbabilísticas

PerformCharts: Extensões

T 2

F

T 1s 1

f

s 2

H

T 3

a 1a 2a 3

W

c

s 3

E q u i p m e n t

P

Entrada porHistórico

PerformCharts: Extensões

H T 2

H i s t o r y ( P )

A c t i v e

H T 1

e n ( P )

f

s 1

cH T 3

a 1a 2

[ i n ( H T 2 ) ]

c

s 3

T 2

F

T 1

T 3

W

e x ( P ) e x ( T 1 )∧

e x ( P ) e x ( T 3 )∧

e n ( P )

e n ( P )

e x ( P ) e x ( T 2 )∧

s 2a 3

[ i n ( H T 1 ) ]

[ i n ( H T 3 ) ]

P

E q u i p m e n t

BibliografiaRedes de Filas

Bolch, G.; Greiner, S.; de Meer, H.; Trivedi, K.S. Queuing Networks and  Markov  Chains­Modeling  and  Performance  Evaluation  with Computer  Science  Applications.  John  Wiley  &  Sons,  New  York, 1998Bunday, B. An introduction to Queuing theory. Arnold, USA, 1996Kleinrock, L. Queuing Systems. Vol. 1 e 2. John Wiley & Sons, New York, USA, 1976

Redes de Petri

Peterson, J. L. Petri net theory and modeling of systems. Prentice­Hall International, London, 1981

Bibliografia (cont.)Statecharts

Antunes,  D.C.  STATECHARTS:  Um  formalismo  visual  para descrever  Sistemas  do  tipo  Reativo.  Trabalho  de  curso  da Disciplina  Especificação  Formal.  Instituo  de  Informática,  UFRGS, Porto Alegre, 1994Harel,  D.  Statecharts:  A  Visual  Formalism  for  Complex  Systems. Sc. of Computer Progr. 8, 231­274, 1987Harel,  D.;  Politi,  M.  Modeling  Reactive  Systems  with  Statecharts. McGraw­Hill, USA, 1998

Bibliografia (cont.)Resolução de Cadeias de Markov

Bolch, G.; Greiner, S.; de Meer, H.; Trivedi, K.S. Queuing Networks and  Markov  Chains­Modeling  and  Performance  Evaluation  with Computer  Science  Applications.  John  Wiley  &  Sons,  New  York, 1998Philippe, B.; Saad, Y.; Stewart, W. J. Numerical Methods in Markov Chain modeling. Operations Research. 40(6), 1156­1179, 1992Silva, E. A. S.; Muntz, R. R. Métodos Computacionais de Solução de Cadeias de Markov: Aplicações a Sistemas de Computação e Comunicação. VIII Escola de Computação. Gramado, RS, 1992