メインコンテンツへスキップ
見出し画像

待ち行列と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。

    確認問題と解説はオリジナルです。公開過去問の転載・改変問題ではありません。出題頻度は未集計です。

    前後の記事と学習目次

    前の記事:グラフ・最短経路・最適化――つながりと最善の選択を考える

    次の記事:情報量・エントロピー・ハフマン符号――情報を短く表す

    学習ノートの目次に戻る

    この記事が参加している募集

     
     
    ITの知識ゼロから、基本情報技術者試験の勉強を始めました📚 わからなかった言葉や問題を、自分の言葉でまとめる備忘録です。 基礎からコツコツ学んで、いつかは応用情報にも挑戦したいです! 一緒に学んでいただけたらうれしいです🌱

    あなたへのおすすめ