A INTRODUÇÃO À TEORIA DE FILAS
Por: Thâmara Paiiva • 14/10/2015 • Trabalho acadêmico • 7.374 Palavras (30 Páginas) • 240 Visualizações
INTRODUÇÃO À TEORIA DE FILAS
1. Aspectos Iniciais
A teoria de filas é uma das mais interessantes aplicações da teoria da probabilidade, sendo de grande importância para a análise e dimensionamento de sistemas de comunicações de dados e também em sistemas ligados à ciência da computação. A formação de fila aparece em diversas situações do nosso cotidiano e, de mais interesse para nós, em sistemas aplicados, tais como: filas de usuários para utilizar um terminal, filas de mensagens de entrada esperando para serem processadas por um computador, filas de mensagens esperando por um canal de saída de um concentrador, filas de mensagens esperando pela utilização de uma linha de comunicação em um sistema multiponto, etc.
Neste capítulo, faremos uma introdução à teoria de filas, com uma abordagem o mais aplicada possível. Ou seja, dentro do espírito do nosso curso, não estaremos preocupados em deduzir as expressões que permitem a análise do fenômeno, mas sim, conhecidas essas expressões, como utiliza-las em situações reais, indicando suas potencialidades e limitações. Por esta razão, optamos por apresentar o assunto principalmente através de EXERCÍCIOs.
Antes de prosseguirmos no nosso estudo, faz-se necessário que façamos algumas definições iniciais:
1.1. Utilização de Uma Facilidade: ()
A utilização de uma facilidade é definida como sendo a relação entre o tempo em que a facilidade está ocupada e o tempo total disponível. De outra forma, podemos definir utilização como sendo a relação entre a carga real do sistema e a máxima carga que o sistema pode manusear.
Como Exemplo vamos tomar o caso de uma lanchonete em que o chapista leva em média 5 minutos para fazer um sanduíche. Se o número médio de clientes que procuram esta lanchonete é de 8 clientes por hora, qual a utilização do chapista?
[pic 1]
A pergunta que fazemos a seguir é: Há formação de fila nesta lanchonete? E a resposta é sim! Mesmo que a carga seja inferior à carga máxima manuseável, temos formação de fila, pois os clientes chegam ao sistema de forma aleatória.
EXERCÍCIO 1: Um comutador de pacotes recebe em média 200 pacotes/segundo, cada um com um comprimento médio de 128 bytes. O comutador possui uma única linha de saída com capacidade de 256 kbps. Qual a utilização da linha de saída?
Como veremos ao longo deste capítulo, a utilização da facilidade tem influência direta e significativa no tempo de espera na fila. Como é fácil de concluir, se um cliente chega ao sistema e todos os servidores estão ocupados, este cliente entrará em uma fila de espera para ser atendido. Caso tenhamos um servidor livre, o cliente será atendido imediatamente. Em sistemas em que na grande maioria das vezes o cliente chega e encontra um servidor livre, o tamanho médio da fila é reduzido, mas em compensação temos uma baixa utilização do servidor. Por outro lado, se na maioria das vezes o servidor está ocupado temos uma alta utilização da facilidade mas, em compensação, a fila pode crescer significativamente, causando insatisfação e eventualmente perda de clientes. Assim, o projetista do sistema deve encontrar uma solução de compromisso de modo a atender os clientes dentro do padrão de qualidade desejado definido. Para isto, a teoria de filas é uma importante ferramenta.
Ainda, a utilização de teoria de fila pode ser útil para prevermos o comportamento da qualidade do sistema com o tempo e, com isto, determinarmos estratégias de atualização e/ou crescimento do sistema, de modo que a qualidade não se deteriore além do especificado. Por Exemplo, o modelo analítico de um sistema on-line pode nos mostrar que, com o incremento previsto na carga, o sistema "afundará" em um prazo de dois anos. Com esta informação, e conhecendo o modelo, podemos estudar alternativas para manter a qualidade com o decorrer do tempo, tais como: aumentar a capacidade de memória do sistema, prover uma CPU mais rápida, aumentar a taxa de transmissão da linha de comunicação, etc.
1.2. Algumas Definições
No item anterior utilizamos os termos cliente e servidor. Estes termos são utilizados genericamente em sistemas analisados por teoria de filas. Assim, CLIENTES pode representar pessoas entrando em um banco para fazer um pagamento, mensagens tentando acessar uma linha de transmissão compartilhada, informações requerendo processamento em uma CPU, etc. Da mesma forma, o termo SERVIDOR está associado ao elemento que vai prestar um serviço ao cliente, podendo ser o caixa de um banco, a linha de transmissão compartilhada, a CPU, etc.
O estudo de teoria de filas pode ser dividido em sistemas com SERVIDOR ÚNICO e sistemas com MÚLTIPLOS SERVIDORES. Neste capítulo trataremos e exemplificaremos os dois tipos de sistemas. A figura a seguir ilustra um sistema com múltiplos servidores. Aproveitaremos esta figura para definirmos alguns termos básicos.
[pic 2]
Na figura temos os seguintes parâmetros:
E(n) λ ≡ Taxa média de chegada dos clientes no sistema
Tempo entre chegadas
W Número de clientes na fila
Q Número de clientes no sistema (Na fila e sendo atendidos)
Ainda, definiremos os seguintes parâmetros:
E(ts) = 1/μ = Tempo médio que o servidor leva para atender um cliente = tempo de serviço
μ = taxa de saída de clientes do sistema.
E(tw) = Tempo médio que o cliente permanece na fila, aguardando atendimento
E(tq) = Tempo médio que o cliente permanece no sistema, aguardando atendimento e sendo atendido.
Obviamente, temos:
E(tq) = E(ts) + E(tw) (1.1)
e, também,
Var(tq) = Var(ts) + Var(tw) (1.2)
A utilização da facilidade pode ser calculada pela expressão :
...