はじめに
ネットワークスペシャリストの学習内容整理のために投稿しています。
応用技術まで合格済みですが、馴染み無い分野を全て捨ててきたため、今回のように基本情報レベルのことも整理しています。
誤りや認識違いがありましたらご指摘いただけると嬉しいです。
目的
待ち行列の計算方法の理解。
具体的には、以下のような問題を解くことを目的とします。
問題①
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午前問題】
各用語の解読
待ち行列理論とは
ある列に並ぶ時、平均でどれだけ待たされるかを統計的な計算で求めるための理論。
他の通信の影響があるトラフィックの計算に利用されます。1
待ち時間に影響するのは、以下3点
- 到着率、どのくらいの頻度で到着するか
- サービス時間、実作業の時間
- 窓口の数、一つの列に窓口がいくつあるか
M/M/1以外のモデルはあらかじめ計算式が用意される。
M/M/1の場合は、問題②④のように問題文中に計算式が用意されない場合があるため、公式を覚える必要がある。
その他のトラフィックに関する代表的な理論としては、アーランの理論があります。
M/M/1とは
到着率(M) / サービス時間(M) / 窓口の数(1)
以下の場合の待ち行列モデル
※窓口が3つなら、M/M/3
M/M/1モデルを使った待ち時間の計算
- 利用率3 = 平均サービス時間 / 平均到着時間もしくは 平均サービス時間 x 到着間隔
- 平均待ち時間4 = 利用率 / (1-利用率) x 平均サービス時間
- 平均応答時間5 = 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
おわりに
ありがとうございました。
学習に利用している教材
-
他の通信の影響がないトラフィックの計算は、伝送時間=データ量/(通信速度×伝送効率) ↩
-
Ｍ：マルコフ過程（Markov Process）の意味で、「未来の挙動が現在の値だけで決定され、過去の挙動と無関係な確率過程」であることを指す。 ↩
-
利用率：窓口が塞がっている割合 ↩
-
平均待ち時間：利用率 / (1-利用率)は、待ち行列長。何人並んでいるか。つまり平均待ち時間は、並んでいる人数とその並んでいる人の処理が終わる時間。なお、この式でなぜ待ち行列長が求められるのかは、文系脳のせいかわかりませんでした。。 ↩
-
平均応答時間：列に並び始めた時から自分の番になるまでの時間（平均待ち時間）に加え自分の処理が完了する時間（平均サービス時間）。平均待ち時間＋平均サービス時間＝利用率 / (1-利用率) * 平均サービス時間 + 平均サービス時間が1/(1-利用率)*平均サービス時間になる。 ↩