待ち行列

さて、実際に勉強を始めようと思います。

まずは応用情報技術者試験対策から。

使用する参考書、計画などはおいおいって事で、早速勉強の本題から書いていきます。

参考書第一章から読み始めます。

今日やったのが第１章「コンピュータの基礎知識」から

• 計算の基礎理論
• プログラムの基礎理論
• 数理応用

まぁ、だいたい基本情報技術者試験対策で勉強しているはずですが、１年というブランク（前回の情報試験は、応用情報を無勉強で受け見事に撃沈）により全くというほど覚えていません。

とは言え、計算の基礎理論は理系ならだれでもわかるであろう集合論とグラフ理論。そして、プログラムの基礎理論も簡単な有限オートマトンと精度の話。

ということで、割と面白かった数理応用の待ち行列について備忘録程度にまとめておきます。

〜待ち行列〜

そもそも、待ち行列とはその名の通り、「何かを待っている行列」を表す。要はスーパーのレジ待ちだとか、行列のできるラーメン屋だとかディズニーランドのアトラクション待ちを想像してみれば良い。

もちろん、ただ待っている行列とは言っても、レジとラーメン屋とビッグサンダーとでは行列の性質が違ってくる。

これらを行列の性質を表すために用いられるのがケンドール記法である。

ケンドール記法は、以下の様な３つの区切りで表される。

「　①　／　②　／　③　」

ここで①②③には、

1. サービスの要求頻度
2. サービスの時間分布
3. サーバー数

が入る。

更に①と②には

• M：ランダム（マルコフ過程）
• G：一般分布
• D：一定

などの記号が入り、③にはサーバー数の数字が入る。

したがって、先に示した例ではレジが１個のスーパー（コンビニ？）の場合

M/M/1

という表現ができる。

なおこの時、ランダムの発生分布はポアソン分布に従う。（まぁ、適当にパラパラ人が来ると思えば、それでいいんだよ）

ここからが待ち行列を考える際に必要な式を考えていく。

まずは３つの基本的な量を定義しておく。

• 平均到着率λ：単位時間あたりの平均到着数
• 平均処理率μ：単位時間あたりの平均処理数
• 利用率ρ：サーバーが処理中である確率（トラフィック密度）

これらは

　ρ　＝　λ／μ

という関係をもつ。

この関係はよく考えれば難しいことはなく、

• （平均到着率）１分間に１人レジに行くような店で、
• （平均処理率）１分間に２人のお客さんを捌けるレジ打ち（速い？）が働いたら、
• （利用率）そのレジ打ちが仕事中にレジを打っている割合は１／２

であると言える。これだけ。

さらに

• 平均処理時間Ts：処理にかかる時間
• 滞留jobの平均Ew：処理中も含めて滞留しているジョブ数の平均
• 平均待ち時間Tq：到着してからの処理開始までの時間
• 平均応答時間Tw：到着して処理が終了するまでの時間

を計算する事ができる。

再び例の（１分間に２人捌く）レジ打ち君に登場してもらうと、

平均処理時間Tsは一人の客にかけるレジ時間ということで、すぐに1min/2=30secで３０秒であるとわかる。

つまり平均処理時間Ts＝1／μ

また、そのことからρ＝λ・Tsも同時に成り立つ。

厄介なのがこの次の「滞留jobの平均Ew」これが非常に重要で、式では

    Ew＝ρ/(1-ρ)

と表される。

意味としては、何人がそのレジにいるか（お会計中の人も含めて）。

計算するとρ＝1/2からEw＝1、つまりこのレジ打ちのレーンには平均1人のお客さんが居るということになるわけだ。

ただし、肝心の根拠が知りたくて調べてみたが、どうもこの参考書には載っていない。

なので、ググりました↓

http://ken510707.blog117.fc2.com/blog-entry-20.html

めちゃ面倒くさい！！！

なのでここでは公式として使います。（いや、自分はちゃんと計算追ったよ…）

すると、平均待ち時間Tqは簡単に求まり、

    Tq＝Ew・Ts

と表される。

これはお客さんがレジを待つ時間。

レジ打ちで計算するとEw=1でTs=1/2なのでTq=1/2。つまり、1分間に2人捌けるレジ打ちをもってしても、お客さんは30秒ほど待たされることになる。これからは、ちょっとぐらいレジで待たされても文句は言えないなぁ…

そんなわけで、これは結構日常生活に役立つ？

さて最後に平均応答時間Tw。

これは先の平均待ち時間に平均処理時間を足したもの。

    Tw＝Tq+Ts

ちょうどお客さんがレジを抜けるのにかかる時間。

Tq=1/2でTs=1/2だから、最終的にこのレジには平均1分かかる計算になる。

う〜ん、これは個人的には意外な結果。

いくらレジ打ちが頑張って来客の倍速で仕事をこなしたとしても、客は結局結構待つことになるみたいです。コンビニとか大変そうだな…

最後に待ち行列の平均待ち時間Tqをグラフに書いてみました。（gnuplotを使用）

この時、平均処理時間Tsは一定であるとします。

このように平均待ち時間Tqの値は使用率ρ=0.7あたりから急激に上昇します。

したがって、M/M/1のような集中処理を行う場合には、常に使用率ρを70％ほどに抑える必要が有ることがわかります。それ以上になると急激に待ち時間増えてしまいます。

これをレジで例えると、レジ打ちは常に100％で働いてもらうと、客の待ち時間が飛躍的に増えてしまうので、70％以下の労働にしなければならない。なんだか変な感じがしますが、こういうものなのでしょうか？

そんなわけで、途中お茶を濁したところもありましたが、待ち行列に関してはだいたいこんなところ。これからもこんなかんじで、興味を持った所にざっくりとしたまとめを書きながら勉強を進めていきたいと思います。

また、なにか記載内容に間違いがあった場合にはご指摘いただけると幸いです。

レジ打ちには寛容に。