M/M/1待ち行列モデルとは？仕組みと待ち時間を図解
M/M/1待ち行列モデルを、動く処理フローと操作できるグラフで解説。ポアソン到着、指数分布、サーバー利用率、平均待ち時間の公式から実際の性能設計まで理解できます。
まず、これだけ理解すればOK
コンピュータが処理できる量に対して、 仕事が大量に届くと順番待ちが発生します。
M/M/1は、そんな待ち時間を 数学的に計算するためのモデルです。
サーバー利用率が100%に近づくほど、 平均待ち時間は急増する。
1. なぜ待ち行列ができるのか？
例えば、1度に1件のリクエストしか処理できない サーバーがあるとします。
処理中に別のリクエストが届くと、 後から届いたものは待たなければなりません。
INTERACTIVE LAB 01
リクエストはどこで待つ？
3件のリクエストを順番に処理してみましょう。
ステップ 1 / 5
t = 0.0 秒待ち行列
処理開始前
サーバー
同時に1件
処理完了
処理済み
Aが到着し、すぐ処理開始
サーバーが空いているため、Aは待たずに処理されます。
3件の処理時間と待ち時間
この例は到着時刻と処理時間を固定した概念図です。 M/M/1の到着過程や指数分布を再現した 確率シミュレーションではありません。
このように、仕事が到着してから 処理開始まで順番を待つ仕組みが「待ち行列」です。
2. 待ち時間・処理時間・応答時間
この3つは似ていますが、 計算上は明確に区別する必要があります。
応答時間 ＝ 待ち時間 ＋ 処理時間
色分けと長さは説明用の例です。
待ち時間
処理を開始するまでにキューで待つ時間
処理時間
サーバーが実際に仕事を処理する時間
応答時間
到着から処理完了までの合計時間
3. M/M/1という名前の意味
M/M/1は、仕事の到着、処理時間、 処理装置の数という3つの特徴を表しています。
到着の仕方
一定時間内の到着件数がポアソン分布に従います。到着間隔は指数分布です。
処理時間
1件の処理時間が指数分布に従います。毎回同じ時間とは限りません。
処理装置の数
サーバーが1台で、同時に1件ずつ処理することを意味します。
ポアソン分布と指数分布の違い
ポアソン分布
「1分間に何件到着するか」のような、 一定時間内の発生件数を表します。
指数分布
「次の到着まで何秒かかるか」や、 ランダムな処理時間を表します。
さらに、基本的なM/M/1では待ち行列の容量に 上限がなく、先着順で処理すると仮定します。
4. 利用率が高いと、なぜ待つのか？
サーバーの利用率とは、 長期的に見てサーバーが処理で忙しくしている 時間の割合です。
処理装置が空いている時間が比較的多い
忙しい時間と空いている時間が半々
ほとんどの時間、処理装置が使用中
利用率90%でも、平均すると10%の空き時間があります。 しかし到着時刻や処理時間にはばらつきがあるため、 リクエストが重なり、長い順番待ちが発生し得ます。
この関係を実際に操作して確認してみましょう。
INTERACTIVE LAB 02
利用率を上げると、待ち時間はどうなる？
スライダーで利用率を変更し、 M/M/1の理論平均値を比較できます。
平均処理時間
1.00秒
実際の処理に使う時間
平均待ち時間
1.00秒
処理が始まるまでの時間
平均応答時間
2.00秒
待ち時間 ＋ 処理時間
利用率と平均待ち時間の曲線
縦軸：平均待ち時間 ÷ 平均処理時間
待ち時間は処理時間の 1.00倍
ちょうど50%。平均待ち時間と平均処理時間が等しくなります。
1秒あたりの処理能力と到着量
利用率は「平均到着率 ÷ 平均処理率」です。
現在の処理率は毎秒 1.00 件、 到着率は毎秒 0.50 件です。 平均到着率が処理能力に近づくほど、 処理待ちが増えやすくなります。
数式に代入すると
Wq = [ρ / (1 − ρ)] × T
= [0.50 / (1 − 0.50)] × 1
= 1.00 秒
待ち行列内の平均リクエスト数
0.50 件
Lq = ρ² / (1 − ρ)
M/M/1の前提条件が成立し、0 ≤ ρ < 1 の定常状態にあるときの理論平均値です。 利用率100%では定常的な有限の平均待ち時間は 成立しません。
5. 平均待ち時間の計算式
M/M/1の定常状態では、平均待ち時間を 次の式で計算できます。
平均待ち時間
Wq = ρ / (1 − ρ) × T
ρ：サーバー利用率
T：1件あたりの平均処理時間
例えば利用率50%の場合、 平均待ち時間と平均処理時間が等しくなります。
Wq = 0.5 / (1 − 0.5) × T
= 0.5 / 0.5 × T
= 1 × T
つまり、平均処理時間が1秒なら 平均待ち時間も1秒です。
6. システム設計ではどう活用する？
待ち行列理論は、処理量と応答性能の関係を 理解するための基礎になります。
API・アプリケーションサーバー
大量のリクエストが集中した際に、処理待ちがどのように増えるかを考える手掛かりになります。
バックグラウンドジョブ
ジョブの到着量とワーカーの処理能力を比較し、キューが増えやすい条件を考えられます。
データベース処理
直列化された処理部分がボトルネックになると、待ち時間が大きくなることがあります。
性能・容量計画
利用率だけでなく、待ち時間と応答時間にも余裕を持たせる設計が重要です。
注意：実際のシステムが必ずM/M/1になるわけではない
複数ワーカー、タイムアウト、優先度、 リトライ、到着の偏り、処理時間の分布などにより 挙動は変わります。 例えば処理時間が常に一定なら、 M/M/1ではなくM/D/1など別のモデルを 検討する必要があります。
7. 関連する重要な考え方
到着率 λ と処理率 μ
λは単位時間あたりの平均到着件数、 μはサーバーが稼働中に単位時間あたり 処理できる平均件数です。 利用率は ρ = λ / μ と表せます。
定常状態の条件
平均到着率が平均処理率を下回る λ < μ の場合に、 M/M/1で有限の定常平均値を求められます。 λ ≥ μ では有限の定常平均待ち時間を 仮定できません。
Littleの法則
定常状態の平均待ち行列長Lqと 平均待ち時間Wqには、 Lq = λ × Wq の関係があります。 待ち時間が増えるほど、 キュー内に存在する平均件数も増えます。
8. 理解を確認する
CHECK YOUR UNDERSTANDING
利用率75%の場合
平均処理時間が2秒、 利用率が75%のとき、 平均待ち時間は何秒でしょうか？
計算結果と解説を見る
Wq = 0.75 / (1 − 0.75) × 2
= 0.75 / 0.25 × 2
= 6秒
応答時間は待ち時間6秒と処理時間2秒の 合計で8秒です。
まとめ
M/M/1は、1台の処理装置とランダムな到着・ 処理時間を前提にした待ち行列モデルです。
サーバー利用率が高くなるほど、 平均待ち時間は急増します。 システムを設計するときは、 処理能力を使い切ることだけでなく、 どれだけ待たせるかにも注目する必要があります。
参考文献
- [1]M/M/1 Queuing System
MathWorks
- [2]Queuing Analysis — M/M/1 Model
NPTEL / IIT Bombay