1台のネットワーク・プリンタに複数の要求が並んで順番を待っています。このとき,要求を送信してから印刷が完了するまでの時間は「(プリンタが使用可能になるのを)待っている時間」,「プリンタを使用している時間」,「その他の時間(通信時間など)」の合計になります。ここで待っている時間と,使用している時間,および要求が到着する間隔に着目して,これらの関係を理論式で推測していくのが待ち行列問題です。

 今回は最も基本的なM/M/1のモデルを見てみることにしましょう。M/M/1というのはケンドールの記法で表記された待ち行列のモデルで,以下の三つの条件が成り立っている状態を指します。

(1)サービス要求の到着間隔がランダム(ポアゾン分布に従う)
(2)窓口を使用する時間は要求ごとにランダム(指数分布に従う)
(3)待ち行列のサービス窓口は1個

図1●M/M/1の待ち行列モデル
図1●M/M/1の待ち行列モデル

 また,窓口数の後ろに行列の長さの制限を記入する場合もありますが,省略されているときは制限がないということになります。

 ほかにケンドールの記法で待ち行列を考える場合の約束としては,次のものがあります。

●行列へ割り込んだり,列の途中で抜け出すことは考えない
●サービス要求は到着順に受け付ける

利用率と到着率とサービス率

 利用率をρ(ロー),到着率をλ(ラムダ),サービス率をμ(ミュー)とした場合,次の式が成り立ちます。

図2●利用率,到着率,サービス率
図2●利用率,到着率,サービス率

 到着率は単位時間当たりに到着するサービス要求の数,サービス率は単位時間当たりにサーバーが処理できる要求数です。

 式を利用するときは,それぞれの単位時間を統一します。例えば,単位時間を1時間にした場合で,到着するサービス要求が12件,サーバーが処理できる要求数が20件だった場合の利用率は,12÷20=0.6ということになります。

M/M/1の公式

 M/M/1の待ち行列において,待ち時間をTw,平均サービス時間をTsとしたとき,次の式が成り立ちます。

図3●M/M/1の公式
図3●M/M/1の公式

 利用率が0.6で平均サービス時間が3分の場合,上記の式に当てはめると,

0.6÷(1-0.6)×3(分)=4.5(分)

となります。

 このM/M/1モデルは,公式を使用して比較的簡単に待ち時間を求めることができるため,多くの試験で出題されています。

出口 雄一(でぐち ゆういち)
株式会社タケキ IT教育事業部取締役
大手ソフトウエア・ベンダーを経て2003年に独立。現在はネットワーク技術講習会や情報処理技術者試験対策講座の講師を務める。テクニカルエンジニア(ネットワーク)やセキュリティアドミニストレーターなど数多くの国家資格を取得している。
出典:日経NETWORK2006年1月号 82ページより
記事は執筆時の情報に基づいており、現在では異なる場合があります。