Elementos de Sistemas de Filas

A Figura 1 mostra os elementos de um sistema de fila única de filas:


População de clientes pode ser considerada limitada (sistemas fechados) ou ilimitada (sistemas abertos). A população ilimitada representa um modelo teórico de sistemas com um grande número de clientes possíveis (um banco em uma rua movimentada, um posto de gasolina na autoestrada). Exemplo de uma população limitada pode ser um número de processos a serem executados (atendidos) por um computador ou um certo número de máquinas a serem reparadas por um técnico de serviço. É necessário levar o termo "cliente" de maneira muito geral. Os clientes podem ser pessoas, máquinas de várias naturezas, processos de computador, chamadas telefônicas, etc.

Chegada define a forma como os clientes entram no sistema. Geralmente, as chegadas são aleatórias com intervalos aleatórios entre duas chegadas adjacentes. Tipicamente, a chegada é descrita por uma distribuição aleatória de intervalos também chamada Padrão de Chegada.

Fila representa um certo número de clientes esperando pelo serviço (é claro que a fila pode estar vazia). Tipicamente, o cliente sendo atendido não é considerado na fila. Às vezes, os clientes formam uma fila literalmente (pessoas esperando em uma fila para um caixa bancário). Às vezes, a fila é uma abstração (aviões esperando por uma pista para pousar). Existem duas propriedades importantes de uma fila: Tamanho Máximo e Disciplina de Fila.

Tamanho Máximo de Fila (também chamado de capacidade do sistema) é o número máximo de clientes que podem esperar na fila (além do(s) que estão sendo atendidos). A fila é sempre limitada, mas alguns modelos teóricos assumem um comprimento de fila ilimitado. Se o comprimento da fila for limitado, alguns clientes são forçados a desistir sem serem atendidos.

Disciplina de Fila representa a forma como a fila é organizada (regras de inserção e remoção de clientes para/de uma fila). Existem estas formas:

FIFO (Primeiro a entrar, primeiro a sair), também chamado de FCFS (Primeiro a chegar, primeiro a ser atendido) - fila ordenada.

LIFO (Último a entrar, primeiro a sair), também chamado de LCFS (Último a chegar, primeiro a ser atendido) - pilha.

SIRO (Atendido em ordem aleatória).

Fila de Prioridade, que pode ser vista como um número de filas para várias prioridades.

Muitos outros métodos de fila mais complexos que geralmente mudam a posição do cliente na fila de acordo com o tempo já gasto na fila, duração esperada do serviço e/ou prioridade. Esses métodos são típicos para sistemas de acesso múltiplo de computador.

A maioria dos parâmetros quantitativos (como o comprimento médio da fila, o tempo médio gasto no sistema) não depende da disciplina de fila. É por isso que a maioria dos modelos não leva a disciplina de fila em conta ou assume a fila FIFO normal. Na verdade, oúnico parâmetro que depende da disciplina de fila é a variância (ou desvio padrão) do tempo de espera. Existe esta importante regra (que pode ser usada, por exemplo, para verificar resultados de um experimento de simulação):

Os dois valores extremos da variância do tempo de espera são para a fila FIFO (mínima) e a fila LIFO (máxima).

Modelos teóricos (sem prioridades) assumem apenas uma fila. Isso não é considerado um fator limitante porque sistemas práticos com mais filas (banco com vários caixas com filas separadas) podem ser vistos como um sistema com uma única fila, porque os clientes sempre selecionam a fila mais curta. É claro que se assume que os clientes saem após serem atendidos. Sistemas com mais filas (e mais servidores) onde os clientes podem ser atendidos mais vezes são chamados de Redes de Filas.

Serviço representa alguma atividade que leva tempo e que os clientes estão esperando. Novamente, leve isso muito geralmente. Pode ser um serviço real realizado em pessoas ou máquinas, mas pode ser um intervalo de tempo de CPU, conexão criada para uma chamada telefônica, ser abatido para um avião inimigo, etc. Tipicamente, um serviço leva tempo aleatório. Modelos teóricos são baseados em distribuição aleatória da duração do serviço, também chamado de Padrão de Serviço. Outro parâmetro importante é o número de servidores. Sistemas com apenas um servidor são chamados de Sistemas de Canal Único, sistemas com mais servidores são chamados de Sistemas de Canal Múltiplo.

Saída representa a forma como os clientes deixam o sistema. A saída é principalmente ignorada por modelos teóricos, mas às vezes os clientes que deixam o servidor entram na fila novamente (sistemas de compartilhamento de tempo "round robin").

A Teoria de Filas é uma coleção de modelos matemáticos de vários sistemas de filas que levam como entrada parâmetros dos elementos acima e fornecem parâmetros quantitativos descrevendo o desempenho do sistema.

Devido à natureza aleatória dos processos envolvidos, a teoria de filas é bastante exigente e todos os modelos são baseados em suposições muito fortes (nem sempre satisfeitas na prática). Muitos sistemas (especialmente redes de filas) não são solucionáveis, portanto, a única técnica que pode ser aplicada é a simulação.

No entanto, os sistemas de filas são praticamente muito importantes por causa do típico compromisso entre os vários custos de fornecer serviço e os custos associados à espera pelo serviço (ou deixar o sistema sem ser atendido). Um serviço de alta qualidade e rápido é caro, mas os custos causados pelos clientes esperando na fila são mínimos. Por outro lado, filas longas podem custar muito porque os clientes (máquinas, por exemplo) não funcionam enquanto esperam na fila ou os clientes desistem devido às filas longas. Portanto, um problema típico é encontrar uma configuração de sistema ideal (por exemplo, o número ideal de servidores). A solução pode ser encontrada aplicando a teoria de filas ou por meio de simulação.

A classificação de Kendall de sistemas

A classificação de Kendall de sistemas de fila de espera (1953) existe em várias modificações. A classificação mais abrangente usa 6 símbolos:

A/B/s/q/c/p

onde:

A é o padrão de chegada (distribuição dos intervalos entre chegadas).

B é o padrão de serviço (distribuição da duração do serviço).

s é o número de servidores.

q é a disciplina de fila (FIFO, LIFO, ...). Omitido para FIFO ou se não especificado.

c é a capacidade do sistema. Omitido para filas ilimitadas.

p é o tamanho da população (número de possíveis clientes). Omitido para sistemas abertos.

Esses símbolos são usados ​​para padrões de chegada e serviço:

M é o processo de Poisson (Markoviano) com distribuição exponencial de intervalos ou duração do serviço, respectivamente.

Em é a distribuição de Erlang de intervalos ou duração do serviço.

D é o símbolo para chegadas determinísticas (conhecidas) e duração do serviço constante.

G é uma distribuição geral (qualquer).

GI é uma distribuição geral (qualquer) com valores aleatórios independentes.

Exemplos:

D/M/1 = entrada determinística (conhecida), um servidor exponencial, uma fila FIFO ilimitada ou não especificada, população de clientes ilimitada.

M/G/3/20 = entrada de Poisson, três servidores com qualquer distribuição, número máximo de clientes 20, população de clientes ilimitada.

D/M/1/LIFO/10/50 = chegadas determinísticas, um servidor exponencial, a fila é uma pilha com tamanho máximo 9, número total de clientes 50.