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,...,$$\mathrm{\infty }$

$M_n=M,$ $n=0,1,2,...,$$\mathrm{\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=\left(\begin{array}{cc}-\lambda & \lambda \\ \mu & -(\mu +\lambda )& \lambda \\ & \mu & -(\mu +\lambda )& \lambda \\ & & \mu & -(\mu +\lambda )& \lambda & \\ & & & & \ddots \end{array}\right)$

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}[{\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}^{\mathrm{\infty }}{\rho }^{-j/2}{I}_j(at)]$

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{array}{cc}\frac{1}{t\sqrt{\rho }}{e}^{-(\lambda +\mu )t}{I}_1(2t\sqrt{\lambda \mu })& t>0\\ 0& \text{de outro modo}\end{array}$

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

$𝔼(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{array}{cc}(\mu -\lambda )e^{-(\mu -\lambda )t}& t>0\\ 0& \text{de outro modo}\end{array}$

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