【情報技術の基礎知識】待ち行列理論と計算方法

はじめに

ネットワークスペシャリストの学習内容整理のために投稿しています。
応用技術まで合格済みですが、馴染み無い分野を全て捨ててきたため、今回のように基本情報レベルのことも整理しています。
誤りや認識違いがありましたらご指摘いただけると嬉しいです。

目的

待ち行列の計算方法の理解。
具体的には、以下のような問題を解くことを目的とします。

問題①

M/M/1の待ち行列モデルにおいて、一定時間以内に到着する客数の分布はどれか。 【応用情報技術者試験H24午前問題】

問題②

複数台のPCで1台のプリンタを共有するシステムがある。このプリンタに対する平均印刷要求回数が毎分1回の時、このプリンタの平均印刷時間（印刷を要求してから終了するまでの時間）は何秒か。ここで、プリンタは平均が15秒の指数分布に従う時間で印刷要求を処理するものとし、プリンタに対する印刷要求はポアソン分布に従うものとする。【NW試験H２９午前2問題】

問題③

通信回線を使用したデータ転送システムにM/M/1の待ち行列モデルを適用すると平均回線待ち時間、平均伝送時間、回線利用率の関係は、次の式で表すことができる。回線利用率が0%から徐々に上がっていく場合、平均回線待ち時間が平均伝送時間よりも最初に長くなるのは、回線利用率が何%を超えた時か【ー】

平均回線待ち時間＝平均伝送時間×(回線利用率/1-回線利用率）　　

問題④

平均回線待ち時間、平均伝送時間、平均回線利用率の関係がM/M/1の待ち行列モデルに従う時、平均回線待ち時間を平均伝送時間の3倍以下にしたい。平均回線利用率を最大何%以下にすべきか。【NW試験H18午前問題】

問題⑤

単一処理を行うオンラインシステムがある。トランザクションは1秒当たり平均0.6件到着し、このトランザクションに対する平均サービス時間は750ミリ秒/犬である。このオンラインシステムの処理に、M/M/1の待ち時間モデルが適用できるものとする時、1トランザクション当たりの平均応答時間は約何秒か。【NW試験H17午前問題】

各用語の解読

待ち行列理論とは

ある列に並ぶ時、平均でどれだけ待たされるかを統計的な計算で求めるための理論。
他の通信の影響があるトラフィックの計算に利用されます。¹
待ち時間に影響するのは、以下3点

• 到着率、どのくらいの頻度で到着するか
• サービス時間、実作業の時間
• 窓口の数、一つの列に窓口がいくつあるか

M/M/1以外のモデルはあらかじめ計算式が用意される。
M/M/1の場合は、問題②④のように問題文中に計算式が用意されない場合があるため、公式を覚える必要がある。

その他のトラフィックに関する代表的な理論としては、アーランの理論があります。

M/M/1とは

到着率(M) / サービス時間(M) / 窓口の数(1)
以下の場合の待ち行列モデル

• 到着率がランダム（M², ポアソン分布）
• サービス時間がランダム（M², 指数分布）

※窓口が3つなら、M/M/3

M/M/1モデルを使った待ち時間の計算

• 利用率³ = 平均サービス時間 / 平均到着時間もしくは　平均サービス時間 x 到着間隔
• 平均待ち時間⁴ = 利用率 / (1-利用率) x 平均サービス時間
• 平均応答時間⁵ = 1 / (1-利用率) x 平均サービス時間

（メモ）平均応答率の整理

平均応答率は、列に並び始めた時から自分の番になるまでの時間（平均待ち時間）に加え自分の処理が完了する時間（平均サービス時間）です。

つまり、平均待ち時間＋平均サービス時間
分解すると、{利用率 / (1-利用率) × 平均サービス時間} + 平均サービス時間
これを公式化したのが、1 / (1-利用率) * 平均サービス時間

以下は自己整理のメモ（中学生レベルですみません）
①分数の掛け算は分子にのみかかるので平均サービス時間を分子に移す

{利用率 × 平均サービス時間 / (1-利用率)} + 平均サービス時間

②分数の足し算なので足している方の平均サービス時間の分母(1-利用率)に揃える

{利用率 × 平均サービス時間 / (1-利用率)} + {(1-利用率) × 平均サービス時間 / (1-利用率)}

③(1-利用率)*平均サービス時間の掛け算をする

{利用率 × 平均サービス時間) / (1-利用率)} + {(1 × 平均サービス時間) - (利用率 × 平均サービス時間) / (1-利用率)}

④分数の足し算を行う

(利用率 × 平均サービス時間) + (1 × 平均サービス時間) - (利用率 × 平均サービス時間) / (1-利用率)

⑤(利用率 * 平均サービス時間)- (利用率 * 平均サービス時間)で0になる

(1 × 平均サービス時間) / (1-利用率)

⑥分数の掛け算なので平均サービス時間を分子から移す

1 / (1-利用率)　 × 平均サービス時間

##待ち時間理論（問題①の解答）
以下の問題を用いて解いていきます。

M/M/1の待ち行列モデルにおいて、一定時間以内に到着する客数の分布はどれか。 【応用情報技術者試験H24午前問題】

①到着率は、ポアソン分布。サービス時間は、指数分布。
②到着する客数の分布＝到着率なので、ポアソン分布。

##平均応答時間の計算（問題②の解答）
以下の問題を用いて解いていきます。

複数台のPCで1台のプリンタを共有するシステムがある。このプリンタに対する平均印刷要求回数が毎分1回の時、このプリンタの平均印刷時間（印刷を要求してから終了するまでの時間）は何秒か。ここで、プリンタは平均が15秒の指数分布に従う時間で印刷要求を処理するものとし、プリンタに対する印刷要求はポアソン分布に従うものとする。【NW試験H２９午前2問題】

①平均印刷時間（秒）＝平均応答時間（秒）を求める公式を思い出します。
平均応答時間（秒）＝1　/　(1-利用率)　x 平均サービス時間

②利用率の公式を思い出します。
利用率＝平均サービス時間 x 到着間隔

③平均到着間隔（秒）
「平均印刷要求回数が毎分1回」の単位を合わせて平均到着時間60、平均到着間隔1/60（60秒に1回の間隔）とします。

④平均サービス時間
15秒をそのまま使います。

⑤利用率の計算（②の式に③と④を当てはめます）
15 * 1/60　=　1 / 4 = 0.25

⑥平均印刷時間の計算（①の式に④と⑤を当てはめます）
1 / (1-0.25) × 15 = 1 / 0.75 × 15 = 20秒

##平均待ち時間の計算（問題③の解答）
以下の問題を用いて解いていきます。

通信回線を使用したデータ転送システムにM/M/1の待ち行列モデルを適用すると平均回線待ち時間、平均伝送時間、回線利用率の関係は、次の式で表すことができる。回線利用率が0%から徐々に上がっていく場合、平均回線待ち時間が平均伝送時間よりも最初に長くなるのは、回線利用率が何%を超えた時か【ー】

平均回線待ち時間＝平均伝送時間×(回線利用率/1-回線利用率）　　

①平均回線待ち時間 > 平均伝送時間の式に提示された式を当てはめます
平均伝送時間　×　(回線利用率/1-回線利用率）　> 平均伝達時間

②(1-回線利用率)を両辺にかけ、平均伝達時間を両辺で割ります
回線利用率 > 1-回線利用率

③「何%を超えた時か」を求めるため、②の式から、回線利用率 = 1-回線利用率が成り立つ値を考えます
0.4の例：0.4 = 0.6で成り立たない
0.5の例：0.5 = 0.5でイコールなので成り立つ
⇒50%(0.5)を超えた時

④余談（①、②を経由せず問題文の式から仮値を当てはめることでも導き出せる)
平均伝送時間10, 回線利用率0.4の例：10×(0.4/1-0.4）　=10x(0.4/0.6)=約6で10より短い
平均伝送時間10, 回線利用率0.5の例：10×(0.5/1-0.5）　=10x(0.5/0.5)=10で10とイコール

##平均待ち時間の応用の計算（問題④の解答）
以下の問題を用いて解いていきます。

平均回線待ち時間、平均伝送時間、平均回線利用率の関係がM/M/1の待ち行列モデルに従う時、平均回線待ち時間を平均伝送時間の3倍以下にしたい。平均回線利用率を最大何%以下にすべきか。【NW試験H18午前問題】　　

①平均待ち時間を求める公式を思い出します。
平均待ち時間＝利用率　/　(1-利用率)　x 平均サービス時間

②平均サービス時間
ここでは、平均伝送時間と捉えます
　　
③利用率の計算（①の式に②を当てはめます）
平均待ち時間＝利用率　/　(1-利用率)　* 平均伝送時間

④「平均回線待ち時間」が「平均伝送時間の3倍以下」の状態を当て嵌めます
利用率/(1-利用率) x 平均伝送時間 <= 3 x 平均伝送時間

⑤(1-利用率)を両辺にかけ、平均伝送時間を両辺で割り、利用率以外の情報を消していきます
利用率 <= 3 x (1-利用率)
利用率 <= 3 - (3 x 利用率)
利用率 + (3 x 利用率) <= 3
4 x 利用率 <= 3
利用率 <= 3 / 4
利用率 <= 75%(0.75)

##平均応答時間の計算（問題⑤の解答）
以下の問題を用いて解いていきます。

単一処理を行うオンラインシステムがある。トランザクションは1秒当たり平均0.6件到着し、このトランザクションに対する平均サービス時間は750ミリ秒/件である。このオンラインシステムの処理に、M/M/1の待ち時間モデルが適用できるものとする時、1トランザクション当たりの平均応答時間は約何秒か。【NW試験H17午前問題】

①平均応答時間を求める公式を思い出します。
平均応答時間＝1 / (1-利用率) x 平均サービス時間

②利用率を求める公式を思い出します。
利用率＝平均サービス時間 x 到着間隔

③平均サービス時間（秒）
「平均サービス時間は750ミリ秒/件」の単位を合わせて平均サービス時間0.75秒とします。

④平均到着間隔
「1秒当たり平均0.6件」の単位を合わせて平均到着間隔0.6/1（1秒に0.6回の間隔）とします。

⑤利用率の計算（②の式に③と④を当てはめます）
0.75 * 0.6/1 =　0.45

⑥平均応答時間の計算（①の式に④と⑤を当てはめます）
1 / (1-0.45) × 0.75 = 1 / 0.55 × 0.75 = 約1.26

おわりに

ありがとうございました。

学習に利用している教材

　　

1. 他の通信の影響がないトラフィックの計算は、伝送時間=データ量/(通信速度×伝送効率) ↩

2. Ｍ：マルコフ過程（Markov Process）の意味で、「未来の挙動が現在の値だけで決定され、過去の挙動と無関係な確率過程」であることを指す。 ↩ ↩²

3. 利用率：窓口が塞がっている割合 ↩

4. 平均待ち時間：利用率 / (1-利用率)は、待ち行列長。何人並んでいるか。つまり平均待ち時間は、並んでいる人数とその並んでいる人の処理が終わる時間。なお、この式でなぜ待ち行列長が求められるのかは、文系脳のせいかわかりませんでした。。 ↩

5. 平均応答時間：列に並び始めた時から自分の番になるまでの時間（平均待ち時間）に加え自分の処理が完了する時間（平均サービス時間）。平均待ち時間＋平均サービス時間＝利用率 / (1-利用率) * 平均サービス時間 + 平均サービス時間が1/(1-利用率)*平均サービス時間になる。 ↩