Fila M/M/1

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
M/M/1 queue diagram
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,[1] 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:

Definição do modelo[editar | editar código-fonte]

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 de acordo com um processo de Poisson e movem o processo do estado para .
  • Tempos de serviço têm uma distribuição exponencial com o parâmetro de taxa na fila M/M/1, em que é 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

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.

MM1 queue state space.svg

Solução transiente[editar | editar código-fonte]

Podemos escrever uma função massa de probabilidade dependente de 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 e escrevemos para a probabilidade de estar no estado no tempo . Então[2]

em que , e é 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.[3]

Análise estacionária[editar | editar código-fonte]

O modelo é considerado estável somente se . 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 .

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

Número de clientes no sistema[editar | editar código-fonte]

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

Vemos que o número de clientes no sistema é distribuído geometricamente com parâmetro . Assim, o número médio de clientes no sistema é e a variância do número de clientes no sistema é . Este resultado se mantém para qualquer trabalho que conserve o regime de serviço, tal como compartilhamento de processador.[5]

Período ocupado do servidor[editar | editar código-fonte]

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[6][7][8][9]

em que é uma função de Bessel modificada de primeira espécie,[10] obtida pelo uso da transformada de Laplace e pela inversão da solução.[11]

A transformada de Laplace do período ocupado da fila M/M/1 é dada por[12][13][14]

que dá os momentos do período ocupado, em particular a média é e a variância é dada por

Tempo de resposta[editar | editar código-fonte]

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 . O tempo médio gasto na espera é . A distribuição de tempos de resposta experimentados depende, no entanto, da disciplina de atendimento.

Regra do "primeiro a chegar, primeiro a ser servido"[editar | editar código-fonte]

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 [15] e, por isso, a função densidade da probabilidade[16]

Regra do compartilhamento do processador[editar | editar código-fonte]

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.[17] 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.[17]

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,[17] para a qual uma representação integral é conhecida.[18] A distribuição do tempo de espera (tempo de resposta menos tempo de serviço) para um cliente que demanda uma quantidade de serviço tem a transformada[4]

Em que é a menor raiz da equação

O tempo de resposta médio para uma demanda que chega e requer uma quantidade de serviço pode então ser computada como . Uma abordagem alternativa computa os mesmos resultados usando um método de expansão espectral.[5]

Aproximação de difusão[editar | editar código-fonte]

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

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Sturgul, John R. (2000). Mine design: examples using simulation. [S.l.]: SME. p. vi. ISBN 0-87335-181-9 
  2. Kleinrock, Leonard (1975). Queueing Systems Volume 1: Theory. [S.l.: s.n.] p. 77. ISBN 0471491101 
  3. Abate, J.; Whitt, W. (1987). «Transient behavior of the M/M/l queue: Starting at the origin» (PDF). Queueing Systems. 2. 41 páginas. doi:10.1007/BF01182933 
  4. a b Harrison, Peter; Patel, Naresh M. (1992). performance Modelling of Communication Networks and Computer Architectures. [S.l.]: Addison-Wesley. pp. 172–173, 356 
  5. a b Guillemin, F.; Boyer, J. (2001). «Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory» (PDF). Queueing Systems. 39 (4). 377 páginas. doi:10.1023/A:1013913827667 
  6. Abate, J.; Whitt, W. (1988). «Simple spectral representations for the M/M/1 queue» (PDF). Queueing Systems. 3 (4). 321 páginas. doi:10.1007/BF01157854 
  7. Keilson, J.; Kooharian, A. (1960). «On Time Dependent Queuing Processes». The Annals of Mathematical Statistics. 31 (1): 104–112. JSTOR 2237497. doi:10.1214/aoms/1177705991 
  8. Karlin, Samuel; McGregor, James (1958). «Many server queueing processes with Poisson input and exponential service times». Pacific J. Math. 8 (1): 87–118. MR 0097132. doi:10.2140/pjm.1958.8.87 
  9. Gross, Donald; Shortle, John F.; Thompson, James M.; Harris, Carl M. «2.12 Busy-Period Analysis». Fundamentals of Queueing Theory. [S.l.]: Wiley. ISBN 1118211642 
  10. Adan, Ivo. «Course QUE: Queueing Theory, Fall 2003: The M/M/1 system» (PDF). Consultado em 6 de agosto de 2012 
  11. Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. [S.l.]: Princeton University Press. p. 530. ISBN 0-691-14062-6 
  12. Asmussen, S. R. (2003). «Queueing Theory at the Markovian Level». Applied Probability and Queues. Col: Stochastic Modelling and Applied Probability. 51. [S.l.: s.n.] pp. 60–31. ISBN 978-0-387-00211-8. doi:10.1007/0-387-21525-5_3 
  13. Adan, I.; Resing, J. (1996). «Simple analysis of a fluid queue driven by an M/M/1 queue». Queueing Systems. 22. 171 páginas. doi:10.1007/BF01159399 
  14. Kleinrock, Leonard (1975). Queueing Systems. 1. [S.l.]: Wiley. 215 páginas. ISBN 0471491101 
  15. Harrison, P. G. (1993). «Response time distributions in queueing network models». Performance Evaluation of Computer and Communication Systems. Col: Lecture Notes in Computer Science. 729. [S.l.: s.n.] pp. 147–164. ISBN 3-540-57297-X. doi:10.1007/BFb0013852 
  16. Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. [S.l.]: Princeton University Press. p. 409. ISBN 0-691-14062-6 
  17. a b c Coffman, E. G.; Muntz, R. R.; Trotter, H. (1970). «Waiting Time Distributions for Processor-Sharing Systems». Journal of the ACM. 17. 123 páginas. doi:10.1145/321556.321568 
  18. Morrison, J. A. (1985). «Response-Time Distribution for a Processor-Sharing System». SIAM Journal on Applied Mathematics. 45 (1): 152–167. JSTOR 2101088. doi:10.1137/0145007 
  19. Kingman, J. F. C. (1 de outubro de 1961). «The single server queue in heavy traffic». Mathematical Proceedings of the Cambridge Philosophical Society. 57 (4): 902–904. ISSN 1469-8064. doi:10.1017/S0305004100036094