前回、科目Bの繰り返し処理(for・while)を整理しました。今回は、科目Aに戻り、公式を覚える系の単元として苦手意識を持ちやすい「待ち行列理論(M/M/１)」を整理します。
待ち行列理論とは
待ち行列理論は、窓口に人が並ぶような状況を数式で表すモデルです。基本情報技術者試験では、「M/M/１」という、もっとも基本的なモデルが出題されます。
M/M/１は、「利用者の到着はランダム」「サービス(処理)にかかる時間もランダム」「窓口(サーバー)は１つ」という条件のモデルを指しています。
まず覚える２つの値
M/M/１を理解するうえで、最初に覚えるべき値は次の２つです。
- λ(ラムダ):単位時間あたりに到着する人数(到着率)
- μ(ミュー):単位時間あたりに処理できる人数(サービス率)
例えば、１時間に平均６人が窓口に到着し、窓口が１時間に平均10人まで処理できるなら、λ=６、μ=10です。
利用率(ρ)を求める
次に大事になるのが、窓口がどれくらい混み合っているかを表す「利用率(ρ:ロー)」です。
ρ=λ÷μ
先ほどの例なら、ρ=６÷10=0.6となり、窓口は６割の時間、利用されている状態だと分かります。この利用率は、後の公式にもそのまま使う、いちばん基本になる値です。
平均待ち時間・平均系内人数の公式
M/M/１では、次のような公式で、行列の混み具合を数値化します。
- 系内の平均人数(L)=ρ÷(１−ρ)
- 平均待ち時間(W)=L÷λ
公式そのものを丸暗記するのは大変ですが、「まずλとμを求める→ρを計算する→ρを使ってLやWを求める」という順番だけ覚えておけば、あとは代入するだけで答えが出せます。
覚え方のコツ
自分は、公式を単体で覚えるのではなく、「λ→μ→ρ→L→W」という一直線の流れとして覚えるようにしています。
矢印でつながる順番さえ覚えてしまえば、公式を思い出すきっかけになり、暗記の負担が少し軽くなったように感じています。
学習してみた感想
待ち行列理論は、記号(λ・μ・ρ)が並んでいるだけで身構えてしまいがちですが、中身は「どれくらい混んでいて、どれくらい待たされるか」を数字にしただけの、意外とシンプルな考え方でした。記号の意味と計算の順番を先に押さえてしまえば、あとは数字を当てはめる作業だと感じています。
次回は、命令実行のしくみ(CPU・レジスタ・パイプライン処理)を整理します。
