応用情報技術者試験過去問を解いてみた R6年度春期問2 待ち行列モデル M/M/1

1 はじめに
2 問題
3 解答
4 解説
5 問題文の但し書きの理由
6 利用率と待ち時間の関係
- 6.1 利用率と待ち時間の関係
- 6.2 利用率と待ち時間の関係のグラフ
7 問題の用語解説
8 この問題の体系的位置づけ
9 現実での利用例
10 待ち行列理論の具体的使用例(WebサーバーでのM/M/1モデル)
11 なぜサーバーの利用率を70%程度に抑えるのか
12 今回の問題の本質
- 12.1 この問題が示している重要な教訓
13 まとめ
14 参考情報

はじめに

今回も、応用情報技術者試験の過去問を解いていきます。

今回扱うのは、
待ち行列理論（M/M/1モデル）の問題です。

ATMやレジの行列など、現実のサービス設計でも使われる理論なので、理解しておくと面白い分野です。

問題

問2
ATM（現金自動預払機）が1台ずつ設置してある二つの支店を統合し，統合後の支店にはATMを1台設置する。統合後のATMの平均待ち時間を求める式はどれか。ここで，待ち時間はM/M/1の待ち行列モデルに従い，平均待ち時間にはサービス時間を含まず，ATMを1台に統合しても十分に処理できるものとする。

〔条件〕
(1) 統合後の平均サービス時間：Ts
(2) 統合前のATMの利用率：両支店ともρ
(3) 統合後の利用者数：統合前の両支店の利用者数の合計

ア　ρ / (1 − ρ) × Ts
イ　ρ / (1 − 2ρ) × Ts
ウ　2ρ / (1 − ρ) × Ts
エ　2ρ / (1 − 2ρ) × Ts

解答

エ $\frac{2ρ}{1-2ρ}T_s$

解説

① M/M/1モデルの平均待ち時間

M/M/1の平均待ち時間（サービス時間を含まない）は

$W_q=\frac{\rho}{1-\rho}T_s$

です。

記号	意味
ρ	利用率
Ts	平均サービス時間
Wq	平均待ち時間

② ATM統合前

支店A

利用率 $\rho$

支店B

利用率 $\rho$

つまり次の状態です。

支店	ATM台数	利用率
A	1	ρ
B	1	ρ

③ ATM統合後

利用者数は合計になるので

到着率は2倍

になります。

サービス時間は変わらないので

利用率は $ρ’ = 2ρ$

になります。

状態	利用率
統合前	ρ
統合後	2ρ

④ 平均待ち時間の計算

平均待ち時間の式 $W_q=\frac{\rho}{1-\rho}T_s$

これに $\rho → 2ρ$

を代入すると $W_q=\frac{2ρ}{1-2ρ}T_s$

となります。

したがって正解は

エ

です。

問題文の但し書きの理由

今回の問題には、次の 但し書き が書かれていました。

平均待ち時間にはサービス時間を含まない
ATMを1台に統合しても十分処理できるものとする

この但し書きが書かれている理由は、問題の解き方を一意に決めるためです。
もう少し具体的に説明します。

1 「平均待ち時間にはサービス時間を含まない」の理由

待ち行列理論では、似た量が2つあります。

記号	意味
$W_q$	待ち行列で待つ時間
$W$	システムにいる時間（待ち時間＋サービス時間）

これらは $W = W_q + \frac{1}{\mu}$

の関係があります。

もし問題文に

「平均待ち時間」

としか書いていないと、

$W_q$ を求めるのか
$W$ を求めるのか

解釈が2通りになってしまいます。

そこで

サービス時間を含まない

と書くことで $W_q$

を求める問題だと明確にしています。

2 「ATMを1台に統合しても十分処理できる」の理由

M/M/1モデルでは $\rho = \frac{\lambda}{\mu}$

が 1未満でないとシステムが成立しません。

もし $\rho \ge 1$

なら

客が来る速度 ≥ 処理速度

なので

待ち行列が無限に伸びます。

つまり

平均待ち時間は定義できません。

そこで

十分処理できる

と書くことで $\rho < 1$

であることを保証しています。

小まとめ

今回の但し書きの役割は次の2つです。

求める量を明確にする
（待ち時間 $W_q$ ）
M/M/1モデルが成立する条件を保証する
（利用率 $\rho < 1$ ）

つまり

問題を数学的に一意に解けるようにするため

に書かれています。

利用率と待ち時間の関係

待ち行列では $W_q=\frac{\rho}{1-\rho}T_s$

という関係があります。

利用率と待ち時間の関係

利用率ρ	待ち時間
0.3	0.43Ts
0.5	1Ts
0.7	2.33Ts
0.8	4Ts
0.9	9Ts

利用率が高くなると
待ち時間が急激に増えるのが特徴です。

利用率と待ち時間の関係のグラフ

問題の用語解説

待ち行列理論

待ち行列理論は

1909年
デンマークの数学者

A.K.エルラン

が電話交換機の研究で発表した理論です。

現在では

通信ネットワーク
サーバー設計
交通工学

など幅広く使われています。

M/M/1モデル

待ち行列理論の基本モデル。

意味は次の通りです。

記号	意味
M	到着がランダム（ポアソン分布）
M	サービス時間がランダム（指数分布）
1	窓口が1つ

例

ATM
レジ
受付
サーバー処理

などに使われます。

ちなみに、「M/M/1」という表記は一般に「ケンドール記法」と呼ばれ、
他にも「M/M/c」、「M/G/1」などの表記があります。

利用率（ρ）

利用率は $ρ = λT_s$

で定義されます。

記号	意味
λ	到着率
Ts	サービス時間

利用率とは

装置がどれくらい忙しいか

を表します。

例

利用率	意味
0.5	半分の時間稼働
0.8	ほぼフル稼働
1.0	処理能力限界

この問題の体系的位置づけ

この問題は

応用情報技術者試験の

テクノロジ系

システム性能評価

の分野です。

その中の

待ち行列理論

に該当します。

応用情報
 └ システム性能
      └ 待ち行列理論
           └ M/M/1モデル

現実での利用例

待ち行列理論は実際に

ATM設計
スーパーのレジ数
コールセンター
Webサーバー
空港の保安検査

などで使われています。

待ち行列理論の具体的使用例(WebサーバーでのM/M/1モデル)

待ち行列理論は、実際のシステム設計にも使われています。
ここでは、Webサーバーを例に M/M/1モデルがどのように使われるのかを見ていきます。

Webサーバーの処理の流れ

Webサービスでは、ユーザーからのリクエストは次のように処理されます。

ユーザー → HTTPリクエスト → Webサーバー → 処理 → 応答

これを待ち行列として表すと次のようになります。

リクエスト → [待ち行列] → CPU処理 → 完了

つまり

リクエストがランダムに到着する
サーバーが順番に処理する

という構造になります。

このような構造は M/M/1モデルとして表すことができます。

M/M/1モデルのパラメータ

Webサーバーにおいて、M/M/1モデルのパラメータは次のように対応します。

待ち行列理論	Webサーバー
λ	1秒あたりのリクエスト数
μ	1秒あたりの処理能力
Ts	1リクエストの処理時間
ρ	CPU利用率

利用率は次の式で表されます。 $ρ = \frac{λ}{μ}$

または $ρ = λT_s$

Webサーバーの性能予測に使う

M/M/1モデルを使うと、サーバーの待ち時間を予測できます。

例えば次のサーバーを考えます。

項目	値
平均処理時間	0.05秒
処理能力	20リクエスト/秒

つまり $μ = 20$ です。

アクセス数が10リクエスト/秒の場合

$λ = 10$

利用率 $ρ = \frac{10}{20}$ $ρ = 0.5$

平均待ち時間は $W_q=\frac{ρ}{1-ρ}T_s$

なので $W_q=\frac{0.5}{0.5}×0.05$ $W_q=0.05秒$

つまり

待ち時間は50ms程度です。

※msは「ミリセカンド(ミリ秒)」という単位で、1秒＝1000ミリ秒です。

アクセスが増えた場合

アクセスが増えて $λ = 16$

になると $ρ = 0.8$

待ち時間は $W_q=\frac{0.8}{0.2}×0.05$ $W_q=0.2秒$

つまり

200ms待ちになります。

さらにアクセスが増えると

$λ = 18$

になると $ρ = 0.9$

待ち時間 $W_q=\frac{0.9}{0.1}×0.05$ $W_q=0.45秒$

つまり

450ms待ちになります。

利用率と待ち時間の関係

この結果を整理すると次のようになります。

到着率	利用率	待ち時間
10	0.5	0.05秒
16	0.8	0.2秒
18	0.9	0.45秒

ここで重要なのは

アクセスが少し増えただけで待ち時間が急増する

という点です。

なぜサーバーの利用率を70%程度に抑えるのか

M/M/1モデルの待ち時間の式は $W_q=\frac{ρ}{1-ρ}T_s$

です。

この式を見ると分かるように、利用率が1に近づくと、分母の

$1-ρ$

が小さくなり、待ち時間は急激に増加します。

実際のシステム設計では、次のような目安が使われます。

利用率	状態
50%	余裕がある
70%	通常運用
80%	混雑し始める
90%	レスポンス悪化

そのため、実務では

CPU利用率を70%程度に抑える

設計がよく行われます。

これは

突発的なアクセス増加への余裕を持たせる
待ち時間の急激な増加を防ぐ

ためです。

このように、待ち行列理論は

システム性能設計の基本理論

として利用されています。

今回の問題の本質

この問題が示している重要な教訓

この問題の本質は次の点にあります。

待ち時間は 利用率で決まる
利用率が少し上がるだけで 待ち時間は急激に増える
利用率が1に近づくと 待ち時間は発散する

つまり、この問題は

待ち行列理論における「利用率の重要性」

を理解するための典型的な問題と言えます。

まとめ

最後に、今回の問題を振り返ります。

M/M/1の平均待ち時間

$W_q=\frac{\rho}{1-\rho}T_s$

ATM統合により
利用率が2倍

$ρ’ = 2ρ$

平均待ち時間

$\frac{2ρ}{1-2ρ}T_s$

よって答えは

エ

参考情報

応用情報技術者試験_過去問

過去問題 | 試験情報 | IPA 独立行政法人情報処理推進機構

情報処理推進機構（IPA）の「過去問題」に関する情報です。