M/M/1 待ち行列

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

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

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

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

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

記述

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

●待ち行列の長さが1つ増加するのにかかる時間tが従う確率密度関数‥$\lambda e^{-\lambda t}~~~(t\geq 0)$$\lambda e^{-\lambda t}~~~(t\geq 0)$
●待ち行列の長さが1つ減少するのにかかる時間tが従う確率密度関数‥$\mu e^{-\mu t}~~~(t\geq 0)$$\mu e^{-\mu t}~~~(t\geq 0)$
を満たす。λ を平均到着率、μ を平均サービス率という。

よってM/M/1待ち行列は連続時間マルコフ連鎖として記述でき、その状態遷移図は以下のように出生死滅過程として記述可能である‥


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

$Q={\begin{pmatrix}-\lambda &\lambda \\\mu &-(\mu +\lambda )&\lambda \\&\mu &-(\mu +\lambda )&\lambda \\&&\mu &-(\mu +\lambda )&\lambda &\\&&&&\ddots \end{pmatrix}}$$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) とすると、以下を得る。

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

定常解析

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

ρ = λ/μ

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

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

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

待ち行列の長さ

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

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

${\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}}$${\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なので、

$\sum _{i=0}^{\infty }\pi _{i}=1$$\sum _{i=0}^{\infty }\pi _{i}=1$
である。これらを解くことで、π_iが以下のようになる事がわかる。

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

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

サーバーのビジー時間

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

${\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}}} $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 }})$$\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}}}.$${\frac {1+{\frac {\lambda }{\mu }}}{\mu ^{2}(1-{\frac {\lambda }{\mu }})^{3}}}.$

応答時間

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

先着順方式

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

${\displaystyle f($t)={\begin{cases}(\mu -\lambda )e^{-(\mu -\lambda )t}&t>0\\0&{\text{otherwise.}}\end{cases}}} $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}}}$$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.$$\lambda r^{2}-(\lambda +\mu +s)r+\mu =0.$
サービス量 xを必要とする要求の平均応答時間は x μ/(μ − λ) と計算される。スペクトル展開法を用いて計算することもでき、同じ結果を得る。

拡散近似

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