Avaliacao de Desempenho de Sistemas de Informacao - Teoria das Filas

Avaliação de desempenho de Sistemas de Informação Teoria das Filas BACHARELADO EM SISTEMAS DE INFORMAÇÃO Prof Sergio Nascimento sergioonascimentospsenacbr Todos já passaram pelo aborrecimento de ter que esperar em uma fila Fila de ônibus banco restaurante trânsito etc Em sistemas computacionais há filas em vários lugares Filas de impressão pacotes em roteadores processos aguardando processamento da CPU etc As filas surgem porque a demanda de serviço é maior que a capacidade de atendimento do sistema Filas 3 Ramo da probabilidade que estuda o fenômeno da formação de filas em solicitações de serviços Permite criar modelos do sistema estudado para prever o seu comportamento Podese dimensionar um determinado sistema segundo a demanda de seus clientes evitando desperdícios ou gargalos Utilizada para modelar sistemas onde Clientes chegam para ser atendidos Esperam a sua vez de ser atendidos São atendidos e vão embora Teoria das Filas Sistemas de Fluxo Sistema no qual alguma comodity flui se move ou é transferida por meio de um ou mais canais com capacidade limitada de forma a ir de um ponto a outro no sistema Sistemas transferem as comodities à uma taxa finita Classificação Estáveis Determinísticos Instáveis Estocástico A Fila é gerada pelos clientes à espera de atendimento Não inclui os clientes em atendimento Serviço ou atendimento é constituído por um ou mais postos de atendimento Fila Serviço Sistema Sistemas de Fluxo Estáveis Determinísticos Sistemas onde o fluxo passa de forma previsível Quantidade de fluxo pelo canal é constante e conhecida durante o período de observação Taxa de Serviço C e Taxa de Chegadas R Se C R não existe sobrecarga Atendido por Sistemas Estáveis de Canal Único single channel Se C R existe congestionamento Fila Atendido por Sistemas Estáveis com Redes de Canais multiple channel Número de clientes no sistema Em cada instante Estado do sistema Modelos de Filas 1 2 3 P1 1 2 3 ENTRADA SAÍDA SINGLECHANNELSINGLE PHASE P1 P2 P3 1 2 3 ENTRADA 1 2 3 SAÍDA SINGLECHANNELMULTI PHASE 1 2 3 P1 ENTRADA SAÍDA MULTICHANNELSINGLE PHASE P2 1 2 3 P3 1 2 3 1 2 3 1 2 3 P7 ENTRADA SAÍDA MULTICHANNELMULTI PHASE P8 1 2 3 P9 1 2 3 1 2 3 P1 P2 P3 P4 P5 P6 Sistemas de Fluxo Instáveis Estocástico Sistemas onde o fluxo passa de forma aleatória chegada é aleatória Demanda de uso do canal é imprevisível Exemplo internet telefonia IP etc Como os sistemas estáveis também pode apresentar canal único ou rede de canais A Teoria da Filas se propõe a resolver problemas de sistemas de fluxo aleatório estocásticos 1 2 3 ENTRADA 1 2 3 SAÍDA 1 2 3 1 2 3 1 2 3 1 2 3 MEMÓR X Y Z A B C Processos Estocásticos Taxa de Chegada At At P tempo entre chegadas t Probabilidade que o tempo entre chegadas seja menor ou igual a t onde 0At1 Ritmo médio de chegada λ Intervalo médio entre chegadas Ic P1 1 2 3 ENTRADA 1 2 3 SAÍDA 0 5 10 15 20 25 1 2 3 4 5 At t tempo entre chegadas Ic λ Processos Estocásticos Taxa de Serviço Bx Bx P tempo de serviço x Probabilidade que o tempo de serviço seja menor ou igual a x Ritmo médio de atendimento µ Tempo médio de atendimento Ta 0 5 10 15 20 25 1 2 3 4 5 Bx x tempo de serviço Ta µ P1 1 2 3 ENTRADA 1 2 3 SAÍDA Sistema de Filas Caracterização Linha de entrada chegam clientes solicitações pacotes jobs etc com tempo de chegada aleatório A t Clientes se encaminham para o sistema de filas onde são atendidos servidos por um tempo aleatório B x Depois de atendidos são liberados em uma linha de saída Sistemas podem ter m servidores P1 P2 P3 P1 P2 P3 1 2 3 ENTRADA 1 2 3 SAÍDA SINGLECHANNELMULTIPLE PHASE At Bx Variáveis Variáveis referentes ao sistema Ts Tempo médio de permanência no sistema Ns Número médio de clientes no sistema Variáveis referentes ao processo de chegada λ Rítmo médio de chegada Ic Intervalo médio entre chegadas 1 λ Nc Número médio de chegadas no sistema Variáveis referentes à fila Tf Tempo médio de permanência na fila Nf Número médio de clientes na fila Variáveis referentes ao processo de atendimento µ Rítmo médio de atendimento Ta Tempo médio de atendimento ou serviço 1 µ Na Número médio de clientes sendo atendidos c Capacidade de atendimento P1 P2 P3 1 2 3 ENTRADA 1 2 3 SAÍDA SINGLECHANNELMULTIPLE PHASE Nf Na sistema Variáveis de chegada Ritmo médio de chegada λ𝒕 Nc onde Ic λ𝒕 Ritmo médio de chegada de clientes por unidade de tempo Ic Intervalo médio entre chegadas Ex Um sistema recebe 8 chegadas de clientes em um período de 4 minutos Qual o Ritmo médio de chegada P1 1 2 3 ENTRADA 1 2 3 SAÍDA Tc 4min Nc 8 λ𝒕 Nc 8 2 chegadasmin Ic 4 Variáveis de serviço Ritmo médio de Serviço µ𝒕 Na onde Ta µ𝒕 Ritmo médio de serviço por cliente no servidor Ta Tempo médio de atendimento ou serviço Para c servidores em uma mesma fila a taxa total é c µ Ex Cada sistema demora 2 segundos para processar 8 pacotes IP Qual o Ritmo médio de serviço P1 1 2 3 ENTRADA 1 2 3 SAÍDA Ta 2 Na 8 µ Na 8 4 pacotess Ta 2 Ex Para dois sistemas a taxa seria de P1 1 2 3 ENTRADA 1 2 3 SAÍDA Ta 2 2 4 Na 8 µ Na 8 2 pacotess cTa 4 P2 Variáveis Relações Básicas Número de usuário no sistema Ns Nf Na Tempo de permanência no sistema Ts Tf Ta Podese também demonstrar que Na λ µ Ta Ic Portanto Ns Nf Na Ns Nf λ µ Nf TaIc Lei de Little E um dos resultados mais importantes e amplamente usados em desempenho de qualquer sistema O numero medio de clientes N em um sistema estavel em algum intervalo T é igual a taxa media de chegada λ multiplicada pelo tempo medio de servico no sistema T ou seja JDC Little demonstrou que para um sistema estável de filas temos Nf λ x Tf Número médio de clientes na fila é igual à taxa de chegadas multiplicada pelo tempo médio de permanência na fila Ns λ x Ts Número médio de clientes no sistema é igual à taxa de chegadas multiplicada pelo tempo de permanência no sistema Taxa de Utilização Ut tT λ µ Onde t tempo de serviço e T tempo de observação Fração de tempo no qual o servidor está ocupado Ut 0 sistema vazio ocioso Ut 0 sistema ocupado Ut 1 sistema completamente ocupado saturado Sistema estável onde num intervalo grande de observação o número de saídas é igual ao número de chegadas do sistema Medidas e Relacionamentos entre as variáveis Condição de Estabilidade λ cµ c 1 válido para filas infinitas Intensidade de Tráfego mede o congestionamento de sistemas de filas taxa de chegadas λ µ Ta Tc ou λ c µ onde 1 taxa de serviço Vazão Throughput média das solicitações processadas por unidade de tempo taxa de saída do sistema X NT Equilíbrio Taxa de saída é igual à taxa de chegada do sistema λ c µ Throughput para sistema equilibrado Postulados Básicos P1 P2 P3 λ 1 Em qualquer sistema estável o fluxo que entra é igual ao fluxo que sai 2 Em qualquer sistema estável o fluxo de entrada se mantem nas diversas seções do sistema desde que não exista junção ou desdobramento λ P1 P2 P3 λ λ λ λ P1 P2 P3 λ1 λ2 λ3 λ3 3 Em qualquer sistema estável a junção de fluxos equivale às suas somas aritméticas ou seja λ3 λ1 λ2 P1 P2 λ120 λ216 λ34 P3 80 20 λ34 λ216 4 Em qualquer sistema estável o desdobramento percentual de um fluxo é igual ao desdobramento aritmético do mesmo fluxo Assim se após a estação P1 temos 80 do fluxo se deslocando para P3 então o ritmo de chegada em P3 é de 08 x 20 16 clientesminuto Notação de Kendall A S NS B K SD A S distribuição de tempo de chegada e tempo de serviço M Exponencial Poisson Ek Erlang Hk Hiperexponencial D Determinístico G Geral todas as distribuições NS Número de servidores B Número de buffers lugares na fila K Tamanho da população SD Disciplina do serviço FIFO LIFO etc Padrão B K SD FIFO M M 1 M M 1 FIFO chegadas Poisson tempo de serviço exponencial 1 servidor buffer infinito FIFO M M c idem anterior com c servidores Exercícios Teoria das filas 1 Se um sistema apresenta um tempo de serviço de 3 segundos e atende 5 solicitações durante o intervalo de observação por quanto tempo esse servidor esteve ocupado 2 Observamos que 2000 solicitações de serviços chegaram a um determinado componente do sistema durante um intervalo de 20 minutos Qual a taxa de chegada de solicitações em solicitações por segundo 3 Observamos 50 solicitações sendo atendidas em um intervalo de observação de 4 minutos Qual foi o throughput observado em solicitações por segundo 4 Durante um período de 3 horas foi observado um servidor Ele apresenta uma utilização de 65 Qual foi o tempo que ele esteve ocupado durante a observação 5 Um servidor de arquivos está conectado à rede da empresa Ele recebe 150 solicitações de arquivos e atende 45 dessas solicitações durante um intervalo de observação de 30 minutos O servidor gasta 5 segundos para atender cada solicitação Calcule os valores de λ X e U e o tempo que o servidor esteve ocupado 1Se um sistema apresenta um tempo de serviço de 3 segundos e atende 5 solicitações durante o intervalo de observação por quanto tempo esse servidor esteve ocupado Ta 3 seg Na 5 t 3 x 5 15 seg 2Observamos que 2000 solicitações de serviços chegaram a um determinado componente do sistema durante um intervalo de 20 minutos Qual a taxa de chegada de solicitações em solicitações por segundo Nc 2000 Tc 20 min λ 20002060 167 solicitaçõesseg 3Observamos 50 solicitações sendo atendidas em um intervalo de observação de 4 minutos Qual foi o throughput observado em solicitações por segundo Na 50 T 4 min X NaT 50460 021 solicitaçõesseg 4Durante um período de 3 horas foi observado um servidor Ele apresenta uma utilização de 65 Qual foi o tempo que ele esteve ocupado durante a observação T 3 horas U 065 U tT t T x U 3 x 065 195 horas 1h 57 min Exercícios Teoria das filas 5 Um servidor de arquivos está conectado à rede da empresa Ele recebe 150 solicitações de arquivos e atende 45 dessas solicitações durante um intervalo de observação de 30 minutos O servidor gasta 5 segundos para atender cada solicitação Calcule os valores de λ µ U e o tempo que o servidor esteve ocupado Nc 150 solicitações T 30 min Na 45 Ta 5 seg λ NcT 15030 5 solicitaçõesmin µ NT 4530 x 60 0025 solicitaçõesseg U tT t 45 x 5 225 seg T 30 x 60 1800 U 2251800 0125 OU 125 Exercícios Teoria das filas 6Em um determinado sistema observamos que 10 solicitações foram atendidas durante o tempo de observação e que esse servidor esteve ocupado por 200 segundos durante esse mesmo período de observação Qual o tempo médio de serviço observado desse sistema 7Um servidor apresenta uma taxa de chegada de 10 solicitaçõessegundo Se observarmos o servidor por 10 minutos quantas solicitações de serviço chegaram durante o período de observação 8O servidor analisado esteve ocupado por 19 minutos durante um período de observação de 30 minutos Qual é a utilização desse servidor 9Um sistema computacional foi observado durante sete dias e verificouse que em média o sistema estava sendo utilizado por 16 horas em cada dia Qual a utilização do sistema durante esses sete dias Exercícios Teoria das filas 6Em um determinado sistema observamos que 10 solicitações foram atendidas durante o tempo de observação e que esse servidor esteve ocupado por 200 segundos durante esse mesmo período de observação Qual o tempo médio de serviço observado desse sistema Na 10 Ta 200 seg µ NaTa µ10200 seg Ta 1 µ 20010 20 seg 7Um servidor apresenta uma taxa de chegada de 10 solicitaçõessegundo Se observarmos o servidor por 10 minutos quantas solicitações de serviço chegaram durante o período de observação λ 10 solicitaçõesseg T10min λ NcTc Nc λ x Tc 10x10x60 6000 solicitaçõesseg 8O servidor analisado esteve ocupado por 19 minutos durante um período de observação de 30 minutos Qual é a utilização desse servidor U tT 1930 063 OU 63 9Um sistema computacional foi observado durante sete dias e verificouse que em média o sistema estava sendo utilizado por 16 horas em cada dia Qual a utilização do sistema durante esses sete dias U tT 1624 067 OU 67 Exercícios Teoria das filas