このページでは、待ち行列のλ・μ・ρの意味、M/M/1モデルの待ち時間の公式と計算、ケンドール記号、窓口が複数あるM/M/Sモデルがわかります。
- 一言で言うと：
- レジの行列のように「処理を待つ時間」を、確率の考え方で計算する話。計算問題が出るテーマで、公式は「ρ ÷（1 − ρ）× 平均サービス時間」がすべての基本。
言葉と記号（λ・μ・ρ）→ 待ち時間の公式 → 通信回線に当てはめる → モデルの表し方と分布（ケンドール記号）→ 窓口が複数のとき（M/M/S）
覚え方の軸
- 3つの記号と逆数の関係：
- λ（平均到着率）の逆数が平均到着間隔、μ（平均サービス率）の逆数が平均サービス時間
- 利用率ρは「サービス時間 ÷ 到着間隔」＝「λ ÷ μ」：
- 1未満が前提。1に近づくほど待ち時間は急に伸びる
- 公式は1本だけ覚える：
- 平均待ち時間 ＝ ρ ÷（1 − ρ）× 平均サービス時間。応答時間はこれに平均サービス時間を足すだけ
- 「待ち時間（サービスを含まない）」か「応答時間（含む）」かを、問題文から必ず見分ける
- 分布は「数えるもの（率）はポアソン、時間（間隔）は指数」
待ち行列理論の基本事項：言葉と記号
- 待ち行列：
- 処理（サービス）を待つ順番待ちの行列。オンラインシステム、Webシステム、通信回線など色々なところにある
- サービス時間は1人ひとり違うので、待ち時間は単純なかけ算では出せない → 確率モデルで考える
- 待ち時間が長いと応答時間も長くなり、性能要件を満たせなくなる。だから待ち時間を計算して、長すぎれば対策を考える
- M/M/1モデル：
- 最も基本のモデル。「客（トランザクション）はランダムに到着し（M）、サービス時間はバラバラで（M）、窓口は1つ」
- 待ち時間を求める基本要素
| 要素 | 記号 | 意味 | 求め方 |
|---|---|---|---|
| 平均到着率 | λ（ラムダ） | 単位時間あたりに到着するトランザクション数 | ― |
| 平均到着間隔 | 1/λ | 到着から次の到着までの平均時間 | 1 ÷ 平均到着率 |
| 平均サービス率 | μ（ミュー） | 単位時間あたりにサービスできるトランザクション数 | ― |
| 平均サービス時間 | 1/μ | 1件がサービスを受ける平均時間 | 1 ÷ 平均サービス率 |
| 利用率 | ρ（ロー） | 単位時間に窓口を使っている割合 | 下の式 |
- 例
- 1分間に5人到着：
- 平均到着率 ＝ 5人/分、平均到着間隔 ＝ 1分 ÷ 5 ＝ 12秒
- 1分間に4人サービスできる：
- 平均サービス率 ＝ 4人/分、平均サービス時間 ＝ 1分 ÷ 4 ＝ 15秒
- 1分間に5人到着：
- 利用率（ρ） ＝
- 平均サービス時間 ÷ 平均到着間隔 ＝（1/μ）÷（1/λ）＝ λ ÷ μ
- M/M/1のとき、トラフィック密度ともいう
- 例：
- 5分ごとに客が来て、1人3分でサービスするなら ρ ＝ 3 ÷ 5 ＝ 0.6
- 例題：
- コピー機の利用が平均30秒に1回あり、1回の利用時間が平均12秒
- 平均到着率 λ ＝ 1/30［回/秒］、平均到着間隔 ＝ 30秒
- 平均サービス率 μ ＝ 1/12［回/秒］、平均サービス時間 ＝ 12秒
- ρ ＝（1/30）÷（1/12）＝ 12 ÷ 30 ＝ 0.4
- 注意：
- 計算するときは時間の単位をそろえる（分と秒が混ざりやすい）
待ち時間の計算：公式は1本
- 4つの量
| 量 | 記号 | サービス中を | 意味 |
|---|---|---|---|
| 平均応答時間 | Ww | 含む | 並んでから、サービスが終わるまでの時間 |
| 平均待ち時間 | Wq | 含まない | 並んでから、サービスが始まるまでの時間 |
| 平均滞留数 | Lw | 含む | 待ち行列の長さ（サービス中も数える） |
| 平均待ち行列長 | Lq | 含まない | 待ち行列の長さ（並んでいる人だけ） |
- 覚え方：
- 「w（whole、全体）」はサービス中も含む、「q（queue、行列）」は並んでいるだけ
- 待ち行列は「途中の割込みや途中の離脱がない」前提なので、FIFOのキュー構造になる
- ★基本公式（M/M/1）
- 平均待ち時間（Wq） ＝
- ρ ÷（1 − ρ）× 平均サービス時間
- 平均応答時間（Ww） ＝
- 平均待ち時間 ＋ 平均サービス時間 ＝ ρ ÷（1 − ρ）× 平均サービス時間 ＋ 平均サービス時間
- 平均応答時間の変形した式：
- 1 ÷（1 − ρ）× 平均サービス時間
- 1 ÷（μ − λ）
- （1 ÷ λ）× Lw（Lw：平均滞留数）
- 平均待ち時間（Wq） ＝
- ★例題：
- 平均4件/秒で発生するトランザクションを、1件あたり平均0.15秒で処理する。平均応答時間は？
- λ ＝ 4件/秒、平均サービス時間 ＝ 0.15秒、μ ＝ 1/0.15
- ρ ＝ 4 × 0.15 ＝ 0.6
- 平均待ち時間 ＝ 0.6 ÷ 0.4 × 0.15 ＝ 0.225秒
- 平均応答時間 ＝ 0.225 ＋ 0.15 ＝ 0.375秒 ＝ 375ミリ秒
- 検算：
- 1 ÷（μ − λ）＝ 1 ÷（6.67 − 4）＝ 1 ÷ 2.67 ≒ 0.375秒（一致）
- 簡単な例題：
- 平均到着間隔5分、平均サービス時間2分 → ρ ＝ 2 ÷ 5 ＝ 0.4
- 平均待ち時間 ＝ 0.4 ÷ 0.6 × 2 ≒ 1.33分、平均応答時間 ＝ 1.33 ＋ 2 ≒ 3.33分
- 検算：
- λ ＝ 0.2人/分、μ ＝ 0.5人/分なので 1 ÷（0.5 − 0.2）＝ 1 ÷ 0.3 ≒ 3.33分（一致）
- ★注意（試験）：
- 「平均待ち時間を求めよ」と書いてあっても、「到着してから終了するまで」とあれば平均応答時間を求める。何を聞かれているかを先に決めてから解く
利用率ρと平衡状態
- ρ ＞ 1：
- 到着のほうがサービスより多いので、行列がどんどん長くなり、収拾がつかなくなる
- ρ ＝ 1：
- 分布が規則型かどうかで違うが、基本的には ρ ＞ 1 と同じく収拾がつかなくなる
- だから基本公式は ρ ＜ 1 が前提
- 平衡状態：
- 「ρ ＜ 1 で、途中の割込みや離脱がない」とき、時刻tで行列にN件あれば、ごく短い時間Δt後もN件、という状態。Δtの間に到着する数と、サービスを受けて去る数が等しい
CPU利用率と応答時間のグラフ
- オンラインリアルタイムシステムで、到着がポアソン分布、処理時間が指数分布（M/M/1）のとき
- 応答時間 ＝
- ρ ÷（1 − ρ）× ts ＋ ts（ρ：利用率、ts：平均サービス時間）
- グラフの形：
- 利用率が低いうちはほぼ平らで、1に近づくと急に跳ね上がる（ρ＝0.5なら2ts、0.8なら5ts、0.9なら10ts）
ネットワーク評価への適用：回線に当てはめる
- 通信回線の電文送受信にM/M/1を当てはめる。対応関係は次のとおり
- 平均回線待ち時間 → 平均待ち時間
- 平均伝送時間 → 平均サービス時間
- 回線利用率 → 利用率
- 平均回線待ち時間 ＝
- 回線利用率 ÷（1 − 回線利用率）× 平均伝送時間
- ★例題：
- 平均回線待ち時間を平均伝送時間の4倍以下にしたい。回線利用率は最大何%以下にすべきか
- W ≦ 4T → ρ ÷（1 − ρ）× T ≦ 4T → ρ ÷（1 − ρ）≦ 4 → ρ ≦ 4 − 4ρ → 5ρ ≦ 4 → ρ ≦ 0.8
- 答え：
- 80%以下
- 応用：
- 「3倍以下」なら ρ ≦ 0.75（75%）。「2倍以下」なら ρ ≦ 2/3 ≒ 67%。「1倍以下（同じ以下）」なら ρ ≦ 0.5（50%）
- 「n倍以下」なら ρ ≦ n ÷（n＋1）と覚えておくと速い
ケンドール記号と確率分布：モデルの表し方
- ケンドール記号：
- 待ち行列モデルを、「到着の分布 / サービスの分布 / 窓口の数（行列の長さの制限）」で表す記号
- 「行列の長さの制限」は省略されることが多い
- 確率分布記号
| 記号 | 到着の分布 | サービスの分布 |
|---|---|---|
| M（ランダム型） | 到着間隔は指数分布、到着個数はポアソン分布 | サービス時間は指数分布、サービス数はポアソン分布 |
| D（規則型） | 一定分布（単位分布） | 一定分布（単位分布） |
| G（一般型） | 一般分布 | 一般分布 |
- M/M/1（∞）が正確に当てはまる条件
- 1つ目のM：
- 単位時間内の到着個数がポアソン分布に従う
- 2つ目のM：
- 窓口のサービス時間（処理時間）が指数分布に従う
- 1：
- 窓口は1つで、サービスは1つずつ先着順
- （∞）：
- 行列の長さ（バッファ）は十分大きく、あふれない
- 1つ目のM：
- 窓口が複数あるモデルはM/M/S（後述）
- 確率分布：
- 確率変数がとる値と、その値をとる確率を表したもの
- 離散型確率分布：
- 1、2、3…と数えられる値をとる（例：ポアソン分布）
- 連続型確率分布：
- 時間や距離のように連続した値をとる（例：指数分布）
- ★到着の分布とサービスの分布（到着の分布が問われる）
- 平均到着率λ、平均サービス率μ → ポアソン分布（数えるもの）
- 平均到着間隔、平均サービス時間 → 指数分布（時間）
- 到着がランダムとは：
- 到着から次の到着までの時間がマルコフ過程で表され、到着に一定の規則がないこと
- ★グラフの見分け（正しいグラフを選ぶ問題が出る）
- ポアソン分布：
- 横軸が到着数・サービス数（とびとびの値）。山の形で、ある数のところで確率が最大になる
- 指数分布：
- 横軸が時間間隔（連続）。0のところが一番高く、右へいくほどなだらかに下がっていく曲線
- ポアソン分布：
M/M/Sモデルの平均待ち時間：窓口が複数のとき
- M/M/Sモデル：
- 窓口がS個あるモデル。複数のWebサーバを並列にして負荷分散するシステムのアクセス待ちなどに使う
- 客は1本の行列に並び、空いた窓口でサービスを受ける
- 利用率 ＝
- λ ÷（μ × S）（S：同じ能力の窓口の数）。窓口がS個になると利用率は1/Sになる
- 方法1：グラフから求める（★試験ではグラフが示される）
- 縦軸が「平均サービス時間を単位とした平均待ち時間」（正規化した待ち時間）、横軸が利用率ρのグラフを読む
- 例：
- 窓口1つ、ρ＝0.75 → S＝1では 0.75 ÷ 0.25 ＝ 3（平均待ち時間 ＝ 3 × 平均サービス時間）
- 到着率が2倍になったので窓口を2つにすると、ρは0.75のまま → S＝2のグラフでは約1.3
- 平均待ち時間は 3倍 → 約1.3倍、つまり 1.3 ÷ 3 ≒ 43% に短くなる
- 平均サービス時間40ミリ秒なら：
- S＝1は 3 × 40ms ＝ 0.12秒、S＝2は 約1.3 × 40ms ≒ 0.05秒
- 検算：
- S＝1のときは ρ ÷（1 − ρ）で、M/M/1の公式と一致する
- 方法2：公式で求める
- 平均待ち時間 ＝
- P × ts ÷（S − λ × ts）（S：窓口数、λ：平均到着率、ts：平均サービス時間）
- P：
- すべての窓口がサービス中である確率。横軸がトラフィック密度 u ＝ λ × ts のグラフ（窓口数ごとの曲線）から読む
- 例題：
- 窓口数2、トランザクションが1秒あたり平均8件、1件の平均処理時間100ミリ秒
- λ ＝ 8件/秒、ts ＝ 0.1秒、u ＝ 8 × 0.1 ＝ 0.8
- グラフ（窓口数2）でu＝0.8のとき、P ≒ 0.23
- 平均待ち時間 ＝ 0.23 × 0.1 ÷（2 − 0.8）＝ 0.023 ÷ 1.2 ≒ 0.019秒 ≒ 19ミリ秒
- 平均処理時間（平均応答時間）＝ 19 ＋ 100 ＝ 約119ミリ秒
- 平均待ち時間 ＝
- ★午後問題では、手順に空欄がある形で出る。公式は問題文に示されるので、「どの値をどこに入れるか」がわかればよい。小数点第何位まで出すかも問題文に書いてある
混同しやすいペア
- 平均到着率λ（単位時間に何件来るか）／平均到着間隔1/λ（何秒おきに来るか）
- 平均サービス率μ（単位時間に何件さばけるか）／平均サービス時間1/μ（1件に何秒かかるか）
- 平均待ち時間Wq（サービスを含まない）／平均応答時間Ww（サービスを含む）
- 平均滞留数Lw（サービス中も数える）／平均待ち行列長Lq（並んでいる人だけ）
- ポアソン分布（数、離散、山形のグラフ）／指数分布（時間、連続、右下がりのグラフ）
- M（ランダム型）／D（規則型）／G（一般型）
- M/M/1（窓口1つ）／M/M/S（窓口S個、利用率は λ÷(μ×S)）
- P（全窓口がサービス中の確率）／ρ（利用率）