Ｍ／Ｇ／ｓ／ｓ待ち行列への考察（２）

待ち行列理論

では、Ｍ／Ｇ／ｓ／ｓ待ち行列では定常状態確率分布がサーバのサービス時間分布の形に依存しない、といことが間違いかといいますと、どうもそうではなさそうです。試しにM/E_2/2/2待ち行列について状態遷移図を書いてみると下の図のようになります。

  • 図６


左の図で状態０はジョブの数がゼロの状態、状態１：１はジョブの数が１でサービスのフェーズが１、状態１：２はジョブの数が１でサービスのフェーズが２、状態２：１１はジョブの数が２でサービスのフェーズは２つのジョブともに１、状態２：１２はジョブの数が２でサービスのフェーズは片方のジョブが１でもう片方のジョブが２、状態２：２２はジョブの数が２でサービスのフェーズは２つのジョブともに２、の状態を示しています。遷移の確率は「Ｍ／Ｇ／１／１待ち行列（２） 」の時と同じように
\frac{1}{t_e}dt
を省略して書いています。全ての遷移について遷移確率が上図のようになるわけを説明するのは煩雑になるのでやめますが、２，３説明しますと、状態２：１１→状態２：１２の遷移確率が４になっているのは、１つのジョブについてフェーズ１から２への遷移確率は２ですが、この場合フェーズ１のジョブが２つあるので、２×２＝４になります。同様に状態２：２２→状態１：２の遷移の確率も処理終了になる可能性のジョブが２つあるので２×２＝４になります。

この状態遷移図から各状態の定常状態確率を求めるのはちょっと難しそうです。そこでこの遷移図を以下の３つに分解して、それぞれの遷移が平衡していると仮定します。

  • 図７

  • 図８

  • 図９


図７から平衡方程式を作ると

  • 2up(0)=2p(1:1)・・・・(3)
  • 2p(1:1)=2p(1:2)・・・・(4)

となります。ここから

  • up(0)=p(1:1)=p(1:2)・・・・(5)

が導かれます。また、フェーズに関わらずシステム内にジョブが１個ある確率p(1)は

  • p(1)=p(1:1)+p(1:2)・・・・(6)

なので、

  • p(1)=2up(0)・・・・(7)

になります。
次に図８から平衡方程式を作ると

  • 2up(1:1)=4p(2:11)・・・・(8)
  • 4p(2:11)=2p(2:12)・・・・(9)

よって

  • p(2:11)=\frac{u}{2}p(1:1)・・・・(10)
  • p(2:12)=up(1:1)・・・・(11)

これらを式(5)と一緒に考えると

  • p(2:11)=\frac{u^2}{2}p(0)・・・・(12)
  • p(2:12)=u^2p(0)・・・・(13)

となります。最後に図９から平衡方程式を作ると

  • 2up(1:2)=2p(2:12)・・・・(14)
  • 2p(2:12)=4p(2:22)・・・・(15)

ところで式(14)の左辺は式(5)から2u^2p(0)となります。一方、式(14)の右辺は式(13)からやはり2u^2p(0)となり、式(14)は自動的に成り立っていることになります。式(15)と(13)から

  • p(2:22)=\frac{u^2}{2}p(0)・・・・(16)

となります。フェーズに関わらずシステム内にジョブが２個ある確率p(2)は

  • p(2)=p(2:11)+p(2:12)+p(2:22)・・・・(17)

なので、式(12)(13)(16)より

  • p(2)=2u^2p(0)・・・・(18)

式(7)と並べて書くと

  • p(1)=2up(0)・・・・(7)
  • p(2)=2u^2p(0)・・・・(18)

ところがＭ／Ｍ／２／２待ち行列でも式(7)(18)は成り立ちます。