M/M/1待ち行列

ウィキペディア

M/M/1 待ち行列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/18 14:16 UTC 版)

M/M/1 待ち行列ノード

M/M/1 待ち行列 (英: M/M/1 queue) は確率論の一分野である待ち行列理論の用語で、1列に並んだ客や要求を1つの窓口やサーバが処理する待ち行列で、待ち行列に到着する客や要求がポアソン過程（英語版）に従い、窓口やサーバがこれらを処理する時間が指数分布に従うものを指す。なお、新しく到着した客や要求は待ち行列の一番後ろに並び、窓口やサーバは待ち行列の先頭から順に客や要求を処理するものとする（先着順（英語版）方式）。また待ち行列のバッファは無限に大きいものとする（すなわち、客が待つ部屋は無限に広く、待ち行列の長さに限界がないということ）。

M/M/1待ち行列において、待ち行列が増加する要因（＝客や要求の到着）がポアソン過程に従うという事は、待ち行列の長さが１伸びるのに要する時間が無記憶かつ指数分布に従うことを意味するので、M/M/1待ち行列では、待ち行列の長さが増加する場合も減少する（＝窓口やサーバが客や要求を処理する）場合も指数分布に従う。

またこのことから待ち行列の長さの増加および減少がいずれも無記憶のマルコフ過程に従うので、無記憶のMemoryless もしくはマルコフの Markovianとサーバの台数1とあわせて、ケンドールの記号から「M/M/1」待ち行列と名づけられた。

M/M/1待ち行列は最も基礎的な待ち行列モデルであり^[1]、このモデルからはいくつもの閉じた式（英語版）としての魅力的な研究対象を得ることができる。このモデルを複数のサーバーに拡張したものがM/M/c 待ち行列（英語版）である。

記述

M/M/1 待ち行列は待ち行列の長さによって記述可能なので、M/M/1 待ち行列は待ち行列の長さ全体の集合 {0,1,2,3,...} を状態空間を集合とする確率過程として定義可能である。M/M/1 待ち行列は前述のように長さの増減がいずれも指数分布に従うので、待ち行列への新しい要求が1つ到着するまでの平均時間が 1/λ で、サーバが１つの要求を処理する平均時間が 1/μ であるとすると、

• 待ち行列の長さが1つ増加するのにかかる時間tが従う確率密度関数：${\displaystyle \lambda e^{-\lambda t}~~~(t\geq 0)}$

  このマルコフ連鎖の推移速度行列（英語版）は以下のようになる。

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

  過渡解

  M/M/1 待ち行列がある時刻に特定の状態にあったとき、時刻 t に依存する確率質量関数を書き下すことができる。初期状態を i とし、時刻 t に状態 k にある確率を p_k(t) とすると、以下を得る^[2]。

  ${\displaystyle 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]}$

  ここで、 ${\displaystyle \rho =\lambda /\mu }$, ${\displaystyle a=2{\sqrt {\lambda \mu }}}$ とし、 I_k は第一種変形ベッセル関数とする。過渡解のモーメントは二つの単調関数の和として書くことができる^[3]。

  定常解析

  時間 t→∞ のときのM/M/1待ち行列の漸近的な振る舞いは

  ρ = λ/μ

  という値（平均利用率）によって特徴付けられる。

  ρ ≥ 1 の場合は λ≥μ であるので、時間がたつにつれて待ち行列の長さが際限なく伸びていき、定常分布を持たない。

  逆に ρ < 1 であれば安定であり、定常過程を持つことを示すことができる。

  待ち行列の長さ

  ρ < 1 であれば時間 t→∞ とするとき定常過程に漸近する。

  単位時間内に待ち行列に到着する要求の数の平均値は λ であり、同じく単位時間内にサーバが処理する要求の平均値は μ である。定常過程においては増加と減少がつりあわなければならないので、待ち行列の長さが i である確率を π_i とすると、

  ${\displaystyle {\begin{cases}(\lambda +\mu )\pi _{i}=\mu \pi _{i+1}+\lambda \pi _{i-1}&{\text{if }}i>0\\\lambda \pi _{0}=\mu \pi _{1}\end{cases}}}$

  でなければならない。上式で左辺は単位時間あたりに状態iから別の状態(=状態 i-1 と状態 i+1)に遷移する確率で、右辺は単位時間にあたりに別の状態(=状態 i-1 と状態 i+1)から状態iに遷移する確率である。当然、全確率は1なので、

  ${\displaystyle \sum _{i=0}^{\infty }\pi _{i}=1}$

  である。これらを解くことで、π_iが以下のようになる事がわかる^{[4]:172–173}。

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

  すなわち、定常過程における待ち行列の長さはパラメータ 1 − ρ の幾何分布に従う。よって特に、システム内の要求数の平均は ρ/(1 − ρ) であり、分散は ρ/(1 − ρ)² となる。この結果はプロセッサ共有などを含むどんな work conserving service regime^{[訳語疑問点]}についてもいえる^[5]。

  サーバーのビジー時間

  ビジー時間とは、空のシステムに要求が到着してから、全ての要求が処理されてシステムが空に戻るまでの時間と定義される。ビジー時間は次の確率密度関数に従う^[6][7][8][9]。

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

  ここで、I₁ は第一種変形ベッセル関数^[10]であり、ラプラス変換により得られる^[11]。

  M/M/1 ビジー時間のラプラス変換は次のようになる^{[12][13][14]:215}。

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

  これによりビジー時間のモーメントを計算することができ、特に平均は 1/(μ − λ) となり、分散は以下のとおりとなる。

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

  応答時間

  平均応答時間または平均滞在時間（システム内に要求が存在する総時間）はスケジューリング方式に関係なく、リトルの法則を用いて計算でき 1/(μ − λ) となる。平均待ち時間は 1/(μ − λ) − 1/μ = ρ/(μ − λ) となる。応答時間の分布はスケジューリング方式に依存する。

  先着順方式

  定常状態にある待ち行列に到着した要求に対する応答時間（待ち時間とサービス時間の和）のラプラス変換は (μ − λ)/(s + μ − λ) であり^[15]、従って確率密度関数は以下のとおりとなる^[16]。

  ${\displaystyle f(t)={\begin{cases}(\mu -\lambda )e^{-(\mu -\lambda )t}&t>0\\0&{\text{otherwise.}}\end{cases}}}$

  プロセッサ共有方式

  M/M/1-PS 待ち行列では、待機列はなく全てのジョブはサービスキャパシティを等分に受けとる^[17]。例えば単一のサーバーの速度が 16 で、システム内のジョブが 4 つあるものとすると、それぞれのジョブは速度 4 で処理されることになる。ジョブがサービスを受けとる速度は新たなジョブが到着したりシステムからジョブが減ったりするたびに変更される^[17]。

  定常状態にある待ち行列に到着した要求に対する応答時間分布のラプラス変換は1970年に発表され^[17]、積分形式が知られている^[18]。 サービス量 x の要求に対する待ち時間（応答時間からサービス時間を引いたもの）分布のラプラス変換は以下の通りとなる^[4]:356。

  ${\displaystyle 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}}}}$

  ここで、r は次の方程式の根のうち小さい方である。

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

  サービス量 x を必要とする要求の平均応答時間は x μ/(μ − λ) と計算される。スペクトル展開法を用いて計算することもでき、同じ結果を得る^[5]。

  拡散近似

  利用率 ρ が 1 に近いときの過程は、ドリフトパラメータが λ − μ で分散パラメータが λ + μ の反射壁ブラウン運動（英語版）で近似することができる。この重トラフィック極限はジョン・キングマン（英語版）により初めて導かれた^[19]。

  出典

  1. ^ Sturgul, John R. (2000). Mine design: examples using simulation. SME. p. vi. ISBN 0-87335-181-9 
  2. ^ Kleinrock, Leonard (1975). Queueing Systems Volume 1: Theory. p. 77. ISBN 0471491101 
  3. ^ Abate, J.; Whitt, W. (1987). “Transient behavior of the M/M/l queue: Starting at the origin”. Queueing Systems 2: 41. doi:10.1007/BF01182933. http://www.columbia.edu/~ww2040/TransientMM1questa.pdf. 
  4. ^ ^{a b} Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley 
  5. ^ ^{a b} Guillemin, F.; Boyer, J. (2001). “Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory”. Queueing Systems 39 (4): 377. doi:10.1023/A:1013913827667. http://perso.rd.francetelecom.fr/guillemin/PDFfiles/gps.pdf. 
  6. ^ Abate, J.; Whitt, W. (1988). “Simple spectral representations for the M/M/1 queue”. Queueing Systems 3 (4): 321. doi:10.1007/BF01157854. http://www.columbia.edu/~ww2040/SimpleSpectralMM1.pdf. 
  7. ^ Keilson, J.; Kooharian, A. (1960). “On Time Dependent Queuing Processes”. The Annals of Mathematical Statistics 31 (1): 104–112. doi:10.1214/aoms/1177705991. JSTOR 2237497. 
  8. ^ Karlin, Samuel; McGregor, James (1958). “Many server queueing processes with Poisson input and exponential service times”. Pacific J. Math. 8 (1): 87–118. doi:10.2140/pjm.1958.8.87. MR0097132. 
  9. ^ Gross, Donald; Shortle, John F.; Thompson, James M.; Harris, Carl M.. “2.12 Busy-Period Analysis”. Fundamentals of Queueing Theory. Wiley. ISBN 1118211642 
  10. ^ Adan, Ivo. “Course QUE: Queueing Theory, Fall 2003: The M/M/1 system”. 2012年8月6日閲覧。
  11. ^ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. 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. Stochastic Modelling and Applied Probability. 51. pp. 60–31. doi:10.1007/0-387-21525-5_3. ISBN 978-0-387-00211-8 
  13. ^ Adan, I.; Resing, J. (1996). “Simple analysis of a fluid queue driven by an M/M/1 queue”. Queueing Systems 22: 171. doi:10.1007/BF01159399. 
  14. ^ Kleinrock, Leonard (1975). Queueing Systems: Theory, Volume 1. Wiley. ISBN 0471491101 
  15. ^ Harrison, P. G. (1993). “Response time distributions in queueing network models”. Performance Evaluation of Computer and Communication Systems. Lecture Notes in Computer Science. 729. pp. 147–164. doi:10.1007/BFb0013852. ISBN 3-540-57297-X 
  16. ^ Stewart, William J. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. 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. 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. doi:10.1137/0145007. JSTOR 2101088. 
  19. ^ Kingman, J. F. C.; Atiyah (October 1961). “The single server queue in heavy traffic”. Mathematical Proceedings of the Cambridge Philosophical Society 57 (4): 902. doi:10.1017/S0305004100036094. JSTOR 2984229. 

Weblio日本語例文用例辞書

「M/M/1 待ち行列」の例文・使い方・用例・文例

• 最後に入ったものが最初に出るような待ち行列（後入先出法）