Fila M/M/1

Diagrama de uma fila M/M/1

Em teoria das filas, uma disciplina dentro da teoria matemática das probabilidades, uma fila M/M/1 representa o comprimento de fila em um sistema que tem um único servidor, em que as chegadas são determinadas por um processo de Poisson e os tempos de serviço têm uma distribuição exponencial. O nome do modelo está escrito em notação de Kendall. O modelo é o mais básico dentre os modelos de filas, sendo usado para aproximar sistemas simples, e um objeto atraente de estudo, já que expressões de forma fechada podem ser obtidas para muitas métricas de interesse neste modelo. Uma extensão deste modelo com mais de um servidor é a fila M/M/c. Tem capacidade ilimitada, população infinita, como um processo de nascimento e morte, em que:

$L_{n}=L,$ $n=0,1,2,...,$$\infty$

$M_{n}=M,$ $n=0,1,2,...,$$\infty$

Definição do modelo

Uma fila M/M/1 é um processo estocástico cujo espaço de estados é o conjunto {0, 1, 2, 3...} em que o valor corresponde ao número de clientes no sistema, incluindo aqueles que estão sendo servidos.

• As chegadas ocorrem a uma taxa $\lambda$ de acordo com um processo de Poisson e movem o processo do estado $i$ para $i+1$.
• Tempos de serviço têm uma distribuição exponencial com o parâmetro de taxa $\mu$ na fila M/M/1, em que $1/\mu$ é o tempo médio de serviço.
• Um único servidor atende os clientes um por vez no fim da fila, de acordo com a disciplina first-come, first served ("primeiro a chegar, primeiro a ser servido"), Quando o serviço está completo, o cliente deixa a fila e o número de clientes no sistema é reduzido em um.
• O buffer tem tamanho infinito, então não há limite ao número de clientes que pode conter.

O modelo pode ser descrito como uma cadeia de Markov de tempo contínuo com matriz de taxa de transição

$Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}$

no espaço de estados {0,1,2,3,...}. Esta é igual à cadeia de Markov de tempo contínuo no processo de nascimento e morte. O diagrama do espaço de estados para esta cadeia é como o seguinte.

Solução transitória

Podemos escrever uma função massa de probabilidade dependente de $t$ para descrever a probabilidade de que a fila M/M/1 esteja em um estado particular em um dado tempo. Assumimos que a fila esteja inicialmente no estado $i$ e escrevemos $p_{k}$$(t)$ para a probabilidade de estar no estado $k$ no tempo $t$. Então

$p_{k}(t)=e^{-(\lambda +\mu )t}\left[\rho ^{\frac {k-i}{2}}I_{k-i}(at)+\rho ^{\frac {k-i-1}{2}}I_{k+i+1}(at)+(1-\rho )\rho ^{k}\sum _{j=k+i+2}^{\infty }\rho ^{-j/2}I_{j}(at)\right]$

em que $\rho =\lambda /\mu$, $a=2{\sqrt {\lambda \mu }}$ e $I_{k}$ é uma função de Bessel modificada de primeira espécie. Momentos para a solução transiente podem ser expressos como a soma de duas funções monótonas.

Análise estacionária

O modelo é considerado estável somente se $\lambda <\mu$. Se, em média, as chegadas ocorrem mais rapidamente que as conclusões dos serviços, a fila se tornará indefinidamente longa e o sistema não terá uma distribuição estacionária. A distribuição estacionária é a distribuição limitante para grandes valores de $t$.

Várias medidas de performance podem ser explicitamente computadas para a fila M/M/1. Escrevemos $\rho =\lambda /\mu$ para a intensidade de tráfego (ou utilização do sistema) e precisamos de $\rho <1$ para que a fila seja estável. $\rho$ representa a proporção média do tempo em que o servidor fica ocupado.

Número de clientes no sistema

A probabilidade de que o processo estacionário esteja no estado $i$ (contendo $i$ clientes, incluindo aqueles sendo atendidos) é

$\pi _{i}=(1-\rho )\rho ^{i}.\,$

Vemos que o número de clientes no sistema é distribuído geometricamente com parâmetro $1-\rho$. Assim, o número médio de clientes no sistema é $\rho /(1-\rho )$ e a variância do número de clientes no sistema é $\rho /(1-\rho )^{2}$. Este resultado se mantém para qualquer trabalho que conserve o regime de serviço, tal como compartilhamento de processador.

Período ocupado do servidor

O período ocupado é o período de tempo medido entre o instante em que um cliente chega a um sistema vazio até o instante em que um cliente parte deixando para trás um sistema vazio. O período ocupado tem função densidade de probabilidade

$f(t)={\begin{cases}{\frac {1}{t{\sqrt {\rho }}}}e^{-(\lambda +\mu )t}I_{1}(2t{\sqrt {\lambda \mu }})&t>0\\0&{\text{de outro modo}}\end{cases}}$

em que $I_{1}$ é uma função de Bessel modificada de primeira espécie, obtida pelo uso da transformada de Laplace e pela inversão da solução.

A transformada de Laplace do período ocupado da fila M/M/1 é dada por

$\mathbb {E} (e^{-\theta F})={\frac {1}{2\lambda }}(\lambda +\mu +\theta -{\sqrt {(\lambda +\mu +\theta )^{2}-4\lambda \mu }})$

que dá os momentos do período ocupado, em particular a média é $1/(\mu -\lambda )$ e a variância é dada por

${\frac {1+{\frac {\lambda }{\mu }}}{\mu ^{2}(1-{\frac {\lambda }{\mu }})^{3}}}.$

Tempo de resposta

O tempo médio de resposta ou tempo médio de permanência (tempo total que um cliente passa no sistema) não depende da disciplina de atendimento e pode ser computado usando a Lei de Little como $1/(\mu -\lambda )$. O tempo médio gasto na espera é $1(\mu -\lambda )-1/\mu =\rho (\mu -\lambda )$. A distribuição de tempos de resposta experimentados depende, no entanto, da disciplina de atendimento.

Regra do "primeiro a chegar, primeiro a ser servido"

Para clientes que chegam e encontram a fila como um processo estacionário, o tempo de resposta que eles experimentam (a soma do tempo de espera com o tempo de serviço) tem a transformada $(\mu -\lambda )/(s-\mu -\lambda )$ e, por isso, a função densidade da probabilidade

$f(t)={\begin{cases}(\mu -\lambda )e^{-(\mu -\lambda )t}&t>0\\0&{\text{de outro modo}}\end{cases}}$

Regra do compartilhamento do processador

Em uma fila M/M/1-PS, não há fila de espera e todos os atendimentos recebem uma igual proporção da capacidade de serviço. Suponha que o servidor único atenda a uma taxa 16 e haja 4 atendimentos no sistema. Cada atendimento receberá serviço a uma taxa 4. A taxa de serviço de cada atendimento muda toda vez que uma demanda chega ou sai do sistema.

Para clientes que chegam e encontram a fila como processo estacionário, a transformada de Laplace da distribuição de tempos de resposta experimentados pelos clientes foi publicada em 1970, para a qual uma representação integral é conhecida. A distribuição do tempo de espera (tempo de resposta menos tempo de serviço) para um cliente que demanda uma quantidade $x$ de serviço tem a transformada

$W^{\ast }(s|x)={\frac {(1-\rho )(1-\rho r^{2})e^{-[\lambda (1-r)+s]x}}{(1-\rho r^{2})-\rho (1-r)^{2}e^{-(\mu /r-\lambda r)x}}}$

Em que $r$ é a menor raiz da equação

$\lambda r^{2}-(\lambda +\mu +s)r+\mu =0.$

O tempo de resposta médio para uma demanda que chega e requer uma quantidade $x$ de serviço pode então ser computada como $x\mu /(\mu -\lambda )$. Uma abordagem alternativa computa os mesmos resultados usando um método de expansão espectral.

Aproximação de difusão

Quando a utilização $\rho$ está próxima de um, o processo pode ser aproximado por um movimento browniano refletido com parâmetro de deriva $\lambda -\mu$ e parâmetro de variância $\lambda +\mu$. Este limite de tráfego pesado foi introduzido por John Kingman.

Ver também

• Teoria das filas
• Processo estocástico
• Simulação