プログラミング 見習い

プログラミングの勉強の学習日記的なブログ

応用情報技術者試験 ミスった部分掘り下げ $00001 M/M/1 システム

M/M/sシステムは、

  • サービス時間は指数分布に従う
  • 能力が同じのs台のサーバ
  • 待合室の大きさは無限大
  • 先着順

という特徴のある待ち行列システムらしいです。

以下、サーバーが一台の場合のM/M/1システムについて述べます。

平均到着率(単位時間当たりに到着する客の数)を  \lambda とします。
これはポアソン分布の平均です。
平均サービス時間(客一人当たりの平均サービス時間)を  1/\mu とします。
これは指数分布の平均です。

利用率を  \rho とし、
 \rho = \lambda / \mu
とするらしいです。

平均サービス時間の逆数  \mu は単位時間あたりに何人にサービスを提供できるかを表すので、利用率  \rho 待たされる確率を表すことになります。
(もちろん平均到着率  \lambda が平均サービス率  \mu より大きければ、利用率  \rho は1以上になるが、この場合待ち行列がどんどん長くなることになることになってしまうので、利用率  \rho が1未満であることを仮定するらしいです。)

このときシステム内に  k 人の客が存在する確率はどのようになるでしょう。
この確率を  P_{k} とすることにします。

ある時点  t から微小な時間  \delta t 経過した時点  t + \delta t を考えます。
この区間内では、以下の仮定が成り立っていることとします。

  • 客が二人以上は到着しない
  • 客二人分のサービスが完了することがない
  • 客の到着とサービスの完了が同時刻間に起こらない

このとき、 \delta t の間に到着する客の数(客が到着する確率とも言える)は、  \lambda \delta t です。
ですので、客が一人も到着しない確率は、  (1 - \lambda \delta t) です。

時点  t + \delta t k 人の客がシステム内に存在する確率  P_{k} を考えてみます。
確率  P_{k}は次の3つの確率の和になります。

  • 時点  t においてシステム内に  (k - 1) 人の客が存在し、かつ一人の客が到着する確率。
  • 時点  t においてシステム内に  k 人の客が存在し、かつ新しい客の到着とサービスの完了がない確率。
  • 時点  t においてシステム内に  (k + 1) 人の客が存在し、かつ一人の客へのサービスが完了する確率。

よって、 P_{k} は以下のようになります。

 P_{k} = \lambda \delta t P_{k-1} + (1 - \lambda \delta t - \mu \delta t) P_{k} + \mu \delta t P_{k+1}

ただし、 k = 0 の時は  (k - 1) 人の客が存在することはないので、以下のようになります。

 P_{0} = P_{0} (1 - \lambda \delta t) + P_{1} \mu \delta t

この漸化式から確率  P_{k} P_{0} を用いて、

 P_{k} = \frac{\lambda ^ k}{\mu ^ k} P_{0}

と表せます。
一方微小区間において、客数は  0 から  \infty のいずれかになるので、

 \sum_{k = 0}^{\infty} P_{k} = (1 + \frac{\lambda}{\mu} + \frac{\lambda ^ 2}{\mu ^ 2} + \cdot \cdot \cdot)P_{0} = 1

となり、無限等比級数の公式より( \frac{\lambda}{\mu} < 1)、ごちゃごちゃ計算して、

 P_{0} = 1 - \frac{\lambda}{\mu}

となり、

 P_{k} = \rho ^ k P_{0}

となります。

ここまでくれば後は簡単です。

システム内の平均客数  L は以下のようになります。

 L = \sum_{n = 0}^{\infty} n P_{n} = \frac{\rho}{1 - \rho}

単純な期待値の計算ですね。

システムの平均待ち客数  L_{q} は以下のようになります。

 L_{q} = \sum_{n = 1}^{\infty} (n - 1) P_{n} = \frac{\rho ^ 2}{1 - \rho}

客数が  n の場合、待っている人数は  (n - 1) 人です。
また客数が  n = 0 の場合、当然待ち行列は無いので  n = 1 から始まっています。

平均待ち時間  W_{q} は以下のようになります。

 W_{q} = L_{q} / \lambda = \frac{\rho}{\mu (1 - \rho)}

列に並び初めてから  W_{q} 時間たって、サービスを受けれるようになったとき、後ろには  \lambda W_{q} 人が並んでいるはずで、この値は  L_{q} 人と同じなのでこんな式になるみたいです。