M/M/1 待ち行列

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

確率論の一分野である待ち行列理論において、M/M/1 待ち行列 (M/M/1 queue) は、サーバーが一つで、要求の到着はポアソン過程に従い、サービス時間は指数分布に従うような待ち行列の長さを記述するモデルである。名前はケンドールの記号に基づく。 最も基礎的な待ち行列モデルであり、このモデルからはいくつもの閉じた式としての魅力的な研究対象を得ることができる。このモデルを複数のサーバーに拡張したものがM/M/c 待ち行列である。

定義

M/M/1 待ち行列は、状態空間を集合 {0,1,2,3,...} とする確率過程でる。ここで、この数字は現在サービス中の要求を含めた待ち行列の長さに対応する。

• 要求の到着は速度 λ のポアソン過程に従って生じ、状態 i から i + 1 へ遷移する。
  
• サービス時間は M/M/1 待ち行列の速度パラメータ μ の指数分布に従い、平均サービス時間は 1/μ である。
• 唯一のサーバーは待ち行列の先頭にある要求を、先着順方式に則って一つずつ処理する。サービスが終了すると要求は待ち行列から除去され、待ち行列の長さは一つ減少する。
• バッファは無限のサイズを持ち、要求が待ち行列に入れないという状況は起こらないものとする。

このモデルは状態空間 {0,1,2,3,...} 上の連続時間マルコフ連鎖により記述することでき、その推移速度行列は以下のようになる。

$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) とすると、以下を得る。

$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]$

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

定常解析

このモデルは λ < μ のときにのみ安定である。到着速度の平均がサービス速度の平均よりも早ければ、行列は再現なく伸びていくことになり定常分布を持たない。定常分布は t を大きくする極限をとることにより得られる。

M/M/1 待ち行列について、様々な性能指標を計算することができる。バッファ利用率を ρ = λ/μ と書くことにすると、 ρ < 1 が行列が安定となる条件である。ρ はサーバーが占有されている時間の平均割合を記述する。

システム内の要求数

定常過程が状態 i (サービス中のものを含めて i 個の要求が待ち行列にある状態） である確率は以下のようになる。

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

システム内の要求数はパラメータ 1 − ρ の幾何分布に従うことが見てとれる。従って、システム内の要求数の平均は ρ/(1 − ρ) であり、分散は ρ/(1 − ρ)² となる。この結果はプロセッサ共有などを含むどんな work conserving service regime についてもいえる。

サーバーのビジー時間

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

$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₁ は第一種変形ベッセル関数であり、ラプラス変換により得られる。

M/M/1 ビジー時間のラプラス変換は次のようになる。

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

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

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

応答時間

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

先着順方式

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

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

プロセッサ共有方式

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

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

$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 は次の方程式の根のうち小さい方である。

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

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

拡散近似

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