b'\n_START_ARTICLE_\nTeoria das filas\n_START_SECTION_\nSistema de filas\n_START_PARAGRAPH_\nUma fila ocorre sempre que a procura por um determinado servi\xc3\xa7o \xc3\xa9 maior que a capacidade do sistema de prover este servi\xc3\xa7o._NEWLINE_Um sistema de filas pode ser definido como clientes chegando, esperando pelo servi\xc3\xa7o (se n\xc3\xa3o forem atendidos imediatamente) e saindo do sistema ap\xc3\xb3s terem sido atendidos. "Cliente", em teoria das filas, \xc3\xa9 um termo gen\xc3\xa9rico, aplicando-se n\xc3\xa3o somente a seres humanos. O conceito pode abranger, por exemplo, processos esperando para receber a CPU; pacotes que chegam a um roteador para serem encaminhados; pessoas_NEWLINE_esperando no caixa do supermercado, etc.\n_START_SECTION_\nComponentes de um sistema de filas\n_START_PARAGRAPH_\nUm sistema de filas consiste no processo de chegada, da distribui\xc3\xa7\xc3\xa3o do tempo de servi\xc3\xa7o, do n\xc3\xbamero de servidores, da capacidade do sistema, da popula\xc3\xa7\xc3\xa3o de usu\xc3\xa1rios e da disciplina de atendimento.\n_START_SECTION_\nProcesso de chegada\n_START_PARAGRAPH_\nO processo de chegada indica qual o padr\xc3\xa3o de chegada dos clientes no sistema. Apresenta comportamento estoc\xc3\xa1stico, ou seja, as chegadas ocorrem no tempo e no espa\xc3\xa7o de acordo com as leis da probabilidade; assim, \xc3\xa9 preciso conhecer qual a distribui\xc3\xa7\xc3\xa3o de probabilidade que descreve os tempos entre as chegadas dos clientes._NEWLINE_A distribui\xc3\xa7\xc3\xa3o mais comum \xc3\xa9 a de Poisson, ou seja, os tempos entre as chegadas s\xc3\xa3o exponencialmente distribu\xc3\xaddos. Entre outras distribui\xc3\xa7\xc3\xb5es, est\xc3\xa3o a de Erlang, hiperexponencial e arbitr\xc3\xa1ria._NEWLINE_Clientes podem chegar simultaneamente (chegada em batch). Se for poss\xc3\xadvel, \xc3\xa9 necess\xc3\xa1rio tamb\xc3\xa9m saber a distribui\xc3\xa7\xc3\xa3o de probabilidade do tamanho do batch. A rea\xc3\xa7\xc3\xa3o do cliente na fila pode variar. Ele pode esperar independentemente do tamanho da fila, tamb\xc3\xa9m pode decidir n\xc3\xa3o entrar no sistema caso a fila esteja muito grande (cliente decepcionado), ele pode esperar na fila mas depois de um tempo desistir e sair do sistema, e tamb\xc3\xa9m pode mudar de uma fila para outra em sistemas com servidores paralelos._NEWLINE_O padr\xc3\xa3o de chegada de clientes em fun\xc3\xa7\xc3\xa3o do tempo pode ser permanente; nesse caso o padr\xc3\xa3o n\xc3\xa3o muda no tempo, ou seja, a distribui\xc3\xa7\xc3\xa3o de probabilidade que descreve as chegadas \xc3\xa9 independente do tempo. Tamb\xc3\xa9m pode n\xc3\xa3o ser permanente, isto \xc3\xa9, o padr\xc3\xa3o de chegada muda com o tempo. Por exemplo, a chegada de clientes diminui no hor\xc3\xa1rio de almo\xc3\xa7o.\n_START_SECTION_\nDistribui\xc3\xa7\xc3\xa3o do tempo de servi\xc3\xa7o\n_START_PARAGRAPH_\nAssim como no processo de chegada, tamb\xc3\xa9m \xc3\xa9 necess\xc3\xa1rio conhecer a distribui\xc3\xa7\xc3\xa3o de probabilidade do tempo de servi\xc3\xa7o, sendo v\xc3\xa1lidas as mesmas distribui\xc3\xa7\xc3\xb5es apresentadas._NEWLINE_Os servi\xc3\xa7os podem tamb\xc3\xa9m ser simples ou batch._NEWLINE_O estado pode ser independente: o processo de atendimento n\xc3\xa3o depende do n\xc3\xbamero de clientes esperando pelo servi\xc3\xa7o. Em contrapartida, em um estado dependente, o processo de atendimento muda de acordo com o n\xc3\xbamero de clientes na fila. Por exemplo, um servidor pode trabalhar mais r\xc3\xa1pido quando a fila aumenta ou, ao contr\xc3\xa1rio, ficar confuso e ent\xc3\xa3o mais lento._NEWLINE_Da mesma forma que no processo de chegada, o padr\xc3\xa3o de servi\xc3\xa7o pode variar de acordo com o tempo. Por exemplo, a experi\xc3\xaancia adquirida com o servi\xc3\xa7o pode aumentar a produtividade; o cansa\xc3\xa7o, por outro lado, pode diminu\xc3\xad-la. Caso n\xc3\xa3o haja varia\xc3\xa7\xc3\xa3o o padr\xc3\xa3o \xc3\xa9 estacion\xc3\xa1rio.\n_START_SECTION_\nCapacidade do sistema\n_START_PARAGRAPH_\nRepresenta o n\xc3\xbamero m\xc3\xa1ximo de clientes que o sistema suporta, incluindo os que est\xc3\xa3o em espera e os que est\xc3\xa3o sendo atendidos. A capacidade pode ser infinita (mais f\xc3\xa1cil de analisar) ou finita (por exemplo, n\xc3\xbamero limitado de buffers em um roteador). Se a capacidade for finita, quando o sistema estiver lotado nenhum cliente pode entrar at\xc3\xa9 que um cliente saia do sistema, liberando espa\xc3\xa7o.\n_START_SECTION_\nPopula\xc3\xa7\xc3\xa3o de usu\xc3\xa1rios\n_START_PARAGRAPH_\nEsse componente indica o n\xc3\xbamero potencial de clientes que podem chegar a um sistema. Pode ser finita ou infinita.\n_START_SECTION_\nLeis operacionais\n_START_PARAGRAPH_\nS\xc3\xa3o rela\xc3\xa7\xc3\xb5es simples que n\xc3\xa3o necessitam de nenhuma hip\xc3\xb3tese sobre as distribui\xc3\xa7\xc3\xb5es dos tempos de servi\xc3\xa7o ou dos intervalos entre chegadas. Foram identificadas inicialmente por Buzen em 1976 e posteriormente estendidas por Denning e Buzen em 1978.\n_START_SECTION_\nLei do Fluxo For\xc3\xa7ado\n_START_PARAGRAPH_\nRelaciona o throughput global do sistema com o throughput dos dispositivos individuais._NEWLINE_Seja  o n\xc3\xbamero m\xc3\xa9dio de visitas ao recurso i por uma tarefa. Cada pedido que termina precisa passar, em m\xc3\xa9dia,  vezes pelo recurso i. Se X pedidos forem conclu\xc3\xaddos por unidade de tempo, ent\xc3\xa3o  pedidos ter\xc3\xa3o passado pelo recurso i:_NEWLINE_Esta lei \xc3\xa9 aplic\xc3\xa1vel sempre qua a hip\xc3\xb3tese do sistema em equil\xc3\xadbrio for verdadeira.\n_START_SECTION_\nLei da Demanda de Servi\xc3\xa7o\n_START_PARAGRAPH_\nCombinando as leis da Utiliza\xc3\xa7\xc3\xa3o e do Fluxo For\xc3\xa7ado, obt\xc3\xa9m-se:_NEWLINE_ou_NEWLINE_onde  \xc3\xa9 a demanda total de servi\xc3\xa7o no i-\xc3\xa9simo dispositivo._NEWLINE_O dispositivo com a maior demanda de servi\xc3\xa7o tem a maior utiliza\xc3\xa7\xc3\xa3o, podendo tornar-se um gargalo no sistema.\n_START_SECTION_\nLei Geral do Tempo de Resposta\n_START_PARAGRAPH_\nSistemas de tempo compartilhado podem ser divididos em dois subsistemas: subsistema de terminais e subsistema de central de processamento. Dados os comprimentos individuais  das filas de cada terminal, pode-se determinar :_NEWLINE_Dividindo ambos os lados por X e aplicando a Lei do Fluxo For\xc3\xa7ado:_NEWLINE_ou\n_START_SECTION_\nLei do Tempo de Resposta Interativo\n_START_PARAGRAPH_\nEm um sistema interativo, usu\xc3\xa1rios geram pedidos que s\xc3\xa3o processados por um subsistema central e os resultados s\xc3\xa3o devolvidos ao terminal. Entre cada pedido de um usu\xc3\xa1rio, h\xc3\xa1 um tempo ocioso Z._NEWLINE_Aplicando-se a Lei de Little ao subsistema central, tem-se:_NEWLINE_Aplicando-a aos M terminais:_NEWLINE_Considerando que um cliente ou est\xc3\xa1 sendo atendido ou est\xc3\xa1 ocioso:'