Ｍ／Ｄ／１／２待ち行列

待ち行列理論

では、Ｍ／Ｄ／１／２待ち行列の定常状態確率を求めてみます。サービス終了時のシステム内のジョブ数に注目します。この時、サービスを終了したジョブはジョブ数に含めません。そうするとジョブ数は１の時とゼロの時があります。それぞれの確率をp'(1)、p'(0)で表わします。


あるサービス後にジョブが０個の場合、以下の２つの場合が考えられます。

  • 前のサービス後にジョブが０個で、しばらくサーバが空いており、その後次にジョブが到着してサービス時間の間、ジョブの到着がなかった。
  • 前のサービス後にジョブが１個で、そのジョブのサービス時間の間、ジョブの到着がなかった。

ジョブの到着間隔はポアソン分布（Ｍ）ですから到着間隔の平均値をt_aとすれば到着間隔がtである確率分布f(t)は

  • f(t)=\frac{1}{t_a}\exp\left(-\frac{t}{t_a}\right)・・・・(1)

となります。サービス時間（Ｄなので一定の値）をt_eで表わすことにします。サービス時間の間ジョブが到着しない確率Aは(1)から

  • A=\Bigint_{t_e}^{\infty}f(t)dt=\Bigint_{t_e}^{\infty}\frac{1}{t_a}\exp\left(-\frac{t}{t_a}\right)dt=\left[-\exp\left(-\frac{t}{t_a}\right)\right]_{t_e}^{\infty}
    • =\exp\left(-\frac{t_e}{t_a}\right)

ここで

  • u=\frac{t_e}{t_a}

なので結局

  • A=\exp(-u)・・・・(2)

になります。逆にサービス時間の間、ジョブの到着が１回以上あった確率は1-A=1-\exp(-u)になります。さて、定常状態であることを考えると上の考察から
p'(0)=p'(0)e^{-u}+p'(1)e^{-u}・・・・(3)
となります。


あるサービス後にジョブが１個の場合、以下の２つの場合が考えられます。

  • 前のサービス後にジョブが０個で、しばらくサーバが空いており、その後次にジョブが到着してサービス時間の間、ジョブの到着が１回以上あった。
  • 前のサービス後にジョブが１個で、そのジョブのサービス時間の間、ジョブの到着が１回以上あった。

ここから定常状態であることを考慮すると

  • p'(1)=p'(0)(1-e^{-u})+p'(1)(1-e^{-u})・・・・(4)

が成り立ちます。ところでサービス終了後のジョブ数としては１の場合とゼロの場合しかありません。よって

  • p'(0)+p'(1)=1・・・・(5)

です。式(3)(5)から

  • p'(0)=e^{-u}・・・・(6)

式(4)(5)から

  • p'(1)=1-e^{-u}・・・・(7)

となります。これでp'(0)、p'(1)が求まりました。


「Ｍ／Ｇ／ｓ／ｎの定常状態のジョブ数分布について」で述べたことから

  • p(0)=p'(0)(1-p(2))
  • p(1)=p'(1)(1-p(2))

なので式(6)(7)から

  • p(0)=e^{-u}(1-p(2))・・・・(8)
  • p(1)=(1-e^{-u})(1-p(2))・・・・(9)

が成り立ちます。ここで「Ｍ／Ｇ／１／ｎ待ち行列のp(0)とp(n)の関係」で述べたことから

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

が成り立ちますので、式(10)の右辺に式(8)を代入して

  • u(1-p(2))=1-e^{-u}(1-p(2))
  • (u+e^{-u})(1-p(2))=1
  • 1-p(2)=\frac{1}{u+e^{-u}}・・・・(11)

よって

  • p(2)=1-\frac{1}{u+e^{-u}}・・・・(12)

となります。式(11)を式(8)の右辺に代入して

  • p(0)=\frac{e^{-u}}{u+e^{-u}}・・・・(13)

式(11)を式(9)の右辺に代入して

  • p(1)=\frac{1-e^{-u}}{u+e^{-u}}・・・・(14)

となります。これでＭ／Ｄ／１／２待ち行列の定常状態確率が全て求まりました。まとめると

  • p(0)=\frac{e^{-u}}{u+e^{-u}}・・・・(13)
  • p(1)=\frac{1-e^{-u}}{u+e^{-u}}・・・・(14)
  • p(2)=1-\frac{1}{u+e^{-u}}・・・・(12)

となります。