
待ち行列とM/M/1――利用率が高いと待ち時間はどうなる?
サーバの処理能力が到着数を上回っていても、到着のばらつきがあれば待ちが生じます。平均だけでなく、どのモデルを置くかが重要です。
到着率・サービス率・利用率
正確な意味: 到着率λは単位時間の平均到着数、サービス率μは窓口一つが単位時間に処理できる平均数です。平均到着間隔は1/λ、平均サービス時間は1/μです。
ざっくり言うと: 入ってくる速さと、さばける速さです。
用途・問題での見方: 1時間に平均12件なら、平均到着間隔は5分です。1件の平均処理時間が4分なら、サービス率は1時間15件です。単位をそろえて計算します。処理時間4分をそのままμ=4としてはいけません。
M/M/1の前提
正確な意味: 基本的なM/M/1は、到着がポアソン過程、サービス時間が独立な指数分布、窓口が一つの待ち行列モデルです。通常、無限の待合容量や先着順などを仮定します。
ざっくり言うと: ばらつきのある到着と処理を、一つの窓口で受けるモデルです。
用途・問題での見方: 安定した定常状態の式を使うにはλ<μが必要です。利用率ρ=λ/μで、ρが1へ近づくほど待ちが大きくなります。平均が同じでも、処理時間が常に一定ならM/M/1の式を無条件に当てはめられません。
待ち時間・系内時間・リトルの法則
正確な意味: 待ち時間Wqは処理開始まで、系内時間Wは待ちと処理の合計です。M/M/1ではW=1/(μ−λ)、Wq=λ/[μ(μ−λ)]=W−1/μです。
ざっくり言うと: 列で待った時間と、窓口を含めて滞在した時間を分けます。
平均系内数Lと到着率λ、平均系内時間WにはL=λWというリトルの法則が成り立ちます。待ち列だけでもLq=λWqです。適用範囲と流入・流出の整合する安定した系など、対応する条件が必要です。
用途・問題での見方: 1分当たりλ=2件、μ=3件ならρ=2/3、W=1分、Wq=2/3分=40秒です。平均処理時間20秒と合わせて1分になります。Lは2件、Lqは4/3件で、処理中を含むかに注意します。
確認問題【オリジナル】
M/M/1の前提を満たし、λ=4件/分、μ=5件/分です。平均待ち時間Wqはどれでしょうか。
ア:0.2分
イ:0.8分
ウ:1分
エ:5分
正解と理由
イ:0.8分です。 W=1/(5−4)=1分、平均処理時間1/5=0.2分なので、待ちは0.8分です。アは処理時間、ウは処理を含めた系内時間です。エはサービス率の数値を時間の値に読み替えています。利用率は0.8で、定常状態の条件を満たします。
参考資料と問題について
学習範囲の確認:IPA「基本情報技術者試験 シラバス Ver.9.2」。本記事は独自の説明・例題です。
考え方の参照:MIT OpenCourseWare:M/M/1 Queue。
確認問題と解説はオリジナルです。公開過去問の転載・改変問題ではありません。出題頻度は未集計です。
前後の記事と学習目次
前の記事:グラフ・最短経路・最適化――つながりと最善の選択を考える