応用情報技術者試験

【応用情報技術者試験対策】待ち行列(キュー)

待ち行列

役所の窓口のようにサービスを受けるために人が待っている状態のことを待ち行列という。

人がやってくる到着率がポアソン分布、サービスを受けている時間(サービス時間)が指数分布に従い、窓口の数が1つの場合を

M/M/1 モデル

という。

待ち行列の用語

  • 平均到着率( λ )
    • 単位時間あたりの平均到着数(件数/時間)
    • 時間あたり何人の人が来るか
  • 平均処理率( μ )
    • 単位時間あたりの平均処理件数(件数/時間)
    • 時間あたり何人の人をさばけるか
  • 利用率( ρ )
    • 窓口が処理中である確率
  • 平均サービス時間(平均処理時間)
    • 1件あたりの処理時間(時間/件)
  • 平均待ち時間
    • 到着してから処理開始までの時間
  • 平均応答時間
    • 到着してから処理完了までの時間

待ち行列(M/M/1)の公式

利用率( ρ )

窓口が処理中である確率

$$\rho = \frac{\lambda}{\mu}$$

 

平均サービス時間(平均処理時間)(ts

1件あたりの処理時間(時間/件)

$$t_s = \frac{1}{\mu}[時間/件]$$

 

処理中と待っている人数の平均(処理中も含めた溜まっているジョブ数の平均)(Ew

$$E_w = \frac{\rho}{1 - \rho}$$

平均待ち時間(tq

到着してから処理開始までの時間。

処理中と待っている人の数 x 平均サービス時間(1件あたりの処理時間)で待ち時間がわかる。

$$
t_q = E_wt_s = \frac{\rho}{1 - \rho} \cdot \frac{1}{\mu} = \frac{\rho}{(1 - \rho)\mu}
$$

平均応答時間(tw

平均応答時間は到着してから処理完了までの時間なので、平均待ち時間に平均サービス時間を加算すれば良い。

$$
t_w = t_q + t_s = \frac{\rho}{(1 - \rho)\mu} + \frac{1}{\mu} = \left(\frac{\rho}{1 - \rho} + 1 \right) \cdot \frac{1}{\mu} = \frac{\rho}{(1 - \rho)\mu}
$$

-応用情報技術者試験

© 2021 フリエン生活 Powered by AFFINGER5