M/M/1待ち行列モデル

読み：えむえむわんまちぎょうれつもでる　／　英語表記：M/M/1 queue

性能・監視・運用

要求の到着がポアソン過程に従い、各要求の処理時間が互いに独立で指数分布に従う、窓口が1つの待ち行列モデル。待ち行列の長さに上限を設けない場合、窓口の利用率をρ、平均サービス時間をTsとすると、0≦ρ＜1での平均待ち時間はρ ÷（1 − ρ）× Tsで求められる。

イマシルちゃんの解説

一つの窓口に仕事が次々に届くと、処理しきれない分は順番を待つことになるね。
M/M/1待ち行列モデルは、こうした待ち時間を確率を使って見積もるためのモデルだよ。
到着間隔と処理時間のばらつきには、短い時間ほど起こりやすい指数分布を仮定するんだ。
窓口が一つで、待てる件数には上限がないものとして考えるよ。
平均では処理が追いついていても、仕事が集中すれば待ち時間が生まれるの。
特に窓口がほぼ休みなく働く状態へ近づくと、平均待ち時間は急に長くなるんだ。
サーバや回線の処理能力に余裕を持たせる理由を考えるのに役立つよ。

より深い解説

ケンドール記号

待ち行列のモデルは、「到着の分布／サービス時間の分布／窓口の数」で表す。

記号	意味
M	ランダム（到着はポアソン分布、サービス時間は指数分布に従う）
D	一定（決まった時間）
G	一般の分布

M/M/1 は、到着がランダム、サービス時間が指数分布、窓口が1つのモデルである。

公式

記号	意味
λ	平均到着率（単位時間あたりに来る客の数）
Ts	平均サービス時間（1人の処理にかかる時間）
ρ	利用率（窓口が使われている割合）＝ λ × Ts

求めるもの	式
平均待ち時間 Tw	ρ ÷（1 − ρ）× Ts
平均応答時間（待ち時間＋サービス時間）	Tw ＋ Ts ＝ Ts ÷（1 − ρ）
平均待ち行列長（待っている客の数）	ρ² ÷（1 − ρ）

ρ が1に近づくと、1 − ρ が0に近づくため、待ち時間は急激に長くなる。ρ が1以上だと、行列は限りなく伸び続ける。

計算例

ある窓口に、1時間あたり平均10件の処理要求が来る。1件の処理には平均3分かかる。

Ts ＝ 3分、λ ＝ 10件 ÷ 60分＝ 1/6件/分
ρ ＝ λ × Ts ＝ 1/6 × 3 ＝ 0.5
平均待ち時間＝ 0.5 ÷（1 − 0.5）× 3 ＝ 3分
要求してから処理が終わるまでの平均時間＝ 3 ＋ 3 ＝ 6分

時間の単位（秒、分、時間）をそろえてから計算するのがポイントである。処理時間が「データ量 ÷ 処理速度」で与えられるときは、まず Ts を求める。

ネットワークでの使い道

ルータの出力の待ち行列、サーバへの要求の処理、プリンタの印刷の待ちなど、「1つの処理装置に、ランダムに仕事が届く」場面の、遅延の見積もりに使う。回線の利用率が高くなると遅延が急に増えるため、利用率に余裕を持たせて設計する。

実際の試験ではここに出る！全3問

ネットワークスペシャリスト

午前Ⅱ

テクニカルエンジニア（ネットワーク）

午前

H20秋問7