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

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

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

#### 問題①
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の場合は、問題②④のように問題文中に計算式が用意されない場合があるため、<u>公式を覚える必要がある</u>。  

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

https://qiita.com/c3drive/items/011dde0f970d66010783

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

- 到着率がランダム（M[^2], ポアソン分布）
- サービス時間がランダム（M[^2], 指数分布）

※窓口が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


## おわりに
ありがとうございました。

## 学習に利用している教材
<a target="_blank"  href="https://www.amazon.co.jp/gp/product/B09DK5MZXJ/ref=as_li_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=B09DK5MZXJ&linkCode=as2&tag=cocolonifty00-22&linkId=fb23dcb5ac7c2efeaa81215667286b13"><img border="0" src="//ws-fe.amazon-adsystem.com/widgets/q?_encoding=UTF8&MarketPlace=JP&ASIN=B09DK5MZXJ&ServiceVersion=20070822&ID=AsinImage&WS=1&Format=_SL160_&tag=cocolonifty00-22" ></a>　　<a target="_blank"  href="https://www.amazon.co.jp/gp/product/B09MTR2C4M/ref=as_li_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=B09MTR2C4M&linkCode=as2&tag=cocolonifty00-22&linkId=ac860c75c0c0a98e5389cf21663bc882"><img border="0" src="//ws-fe.amazon-adsystem.com/widgets/q?_encoding=UTF8&MarketPlace=JP&ASIN=B09MTR2C4M&ServiceVersion=20070822&ID=AsinImage&WS=1&Format=_SL160_&tag=cocolonifty00-22" ></a>



[^1]: 他の通信の影響がないトラフィックの計算は、伝送時間=データ量/(通信速度×伝送効率)
[^2]: Ｍ：マルコフ過程（Markov Process）の意味で、「未来の挙動が現在の値だけで決定され、過去の挙動と無関係な確率過程」であることを指す。
[^3]: 利用率：窓口が塞がっている割合
[^4]: 平均待ち時間：利用率 / (1-利用率)は、待ち行列長。何人並んでいるか。つまり平均待ち時間は、並んでいる人数とその並んでいる人の処理が終わる時間。なお、この式でなぜ待ち行列長が求められるのかは、文系脳のせいかわかりませんでした。。
[^5]: 平均応答時間：列に並び始めた時から自分の番になるまでの時間（平均待ち時間）に加え自分の処理が完了する時間（平均サービス時間）。平均待ち時間＋平均サービス時間＝利用率 / (1-利用率) * 平均サービス時間 + 平均サービス時間が1/(1-利用率)*平均サービス時間になる。