Ｍ／Ｇ／１／１待ち行列（１）

待ち行列理論

Ｍ／Ｇ／１／１待ち行列は、ジョブの到着間隔の分布がＭ（指数分布）、サーバのサービス時間の分布がＧ（任意）で、サーバが１台の待ち行列であり、さらにシステム内のジョブ数が最大１に制限されている待ち行列です。つまり、サーバが空いている場合と、サーバにジョブがいて他に待ちジョブがいない場合、しか許さない待ち行列です。ということは、待つことを許さない待ち行列、ということです。もしサーバがサービス中に次のジョブが到着した場合は、このジョブは無視されます。（つまり待たずにどこかへ行ってしまいます。）　このような待ち行列について考えていたらおもしろいことに気づきましたので、それをアップします。


最初に考えていたのは、サーバの処理時間分布が指数分布の場合、つまりＭ／Ｍ／１／１待ち行列の場合です。この時の状態遷移図を描くと以下のようになります。

  • 図１


左の図において丸が１つの状態を表わし、丸の中の数字がシステム内のジョブ数を示します。また、状態間を結ぶ矢印が状態遷移を表わし、その近くに書かれている数式が微小な時間経過dtの間に状態遷移が発生する確率を示しています。t_eはサーバの平均サービス時間を示し、uがサーバの稼働率を示しています。状態遷移確率が左の図に示すようになることは到着間隔分布とサービス時間分布がともに指数分布であることから導くことが出来ますが、詳しい説明はここでは省略します。


状態が「０」である定常状態確率をp(0)、「１」である定常状態確率をp(1)で表わすことにし、これらを求めたいと思います。図１から平衡方程式

  • p(0)\frac{u}{t_e}dt=p(1)\frac{1}{t_e}dt・・・・(1)

が成り立つことが分かります。この式の両辺には

  • \frac{1}{t_e}dt

が共通していますから、これらを除いて

  • p(0)u=p(1)・・・・(2)

となることが分かります。指数分布で遷移する状態群による状態遷移図には共通して

  • \frac{1}{t_e}dt

が登場するので、図を簡便にするためにこれを図から取り除くことにします。

  • 図２


すると図１は左の図のようになります。取り除いても平衡方程式は式(1)から式(2)になるだけで求める解には影響しないことがわかります。こちらの図（図２）のほうが分かりやすいので以下、こちらの図を用いることにします。


式(2)と、全ての確率の和が１であること、つまり

  • p(0)+p(1)=1・・・・(3)

から

  • p(0)+up(0)=1
  • (1+u)p(0)=1
  • p(0)=\frac{1}{1+u}・・・・(4)

となり、p(0)を求めることが出来ました。今度は式(4)を式(2)に代入して

  • p(1)=\frac{u}{1+u}・・・・(5)

となり、p(1)を求めることが出来ました。



さて、次に考えたのは、Ｍ／Ｅ2／１／１待ち行列、つまりサービス時間の分布が２次のアーラン分布（E_2）の場合です。