はじめに

システムを利用していると、処理がすぐに開始されず、順番待ちになることがあります。

例えば、次のような状況です。

Webサーバに大量のアクセスが集中する
プリンタに複数の印刷要求が届く
データベースへの問い合わせが集中する
ネットワーク機器に大量のパケットが到着する
CPUに複数の処理要求が発生する

このような場合、処理装置が空くまで要求を待たせることがあります。

処理要求
   │
   ▼
┌─────────────┐
│ 待ち行列    │
│ A → B → C   │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ 処理装置    │
└─────────────┘
       │
       ▼
    処理完了

このとき、

「平均で何秒待つのか？」

「処理装置の利用率が高くなると、待ち時間はどう変化するのか？」

「処理装置を2台に増やすと、どれくらい改善するのか？」

といった問題を数学的に考えるのが、**待ち行列理論（Queueing Theory）**です。

今回は、次の内容を学びます。

待ち行列理論
│
├─ 基本事項
│   ├─ 待ち行列モデル
│   ├─ トランザクションの到着
│   ├─ サービス時間
│   └─ 利用率
│
├─ 待ち時間の計算
│   ├─ 平均待ち時間
│   ├─ 平均応答時間
│   └─ 待ち行列の長さ
│
├─ ネットワーク評価への適用
│
├─ ケンドール記号と確率分布
│   ├─ ポアソン分布
│   ├─ 指数分布
│   └─ M/M/1モデル
│
└─ M/M/sモデル
    ├─ 複数の処理装置
    └─ 平均待ち時間の計算

1. 待ち行列理論とは

1-1. 待ち行列理論の基本

**待ち行列理論（Queueing Theory）**とは、処理要求が発生してから処理が完了するまでの待ち時間や、待っている要求の数などを分析する理論です。

身近な例として、レジでの会計を考えてみましょう。

お客さんA ─┐
お客さんB ─┤
お客さんC ─┤
           ▼
       ┌───────┐
       │ レジ  │
       └───────┘
           │
           ▼
        会計完了

レジが空いていれば、すぐに会計できます。

しかし、前のお客さんが会計中であれば、順番を待つ必要があります。

コンピュータシステムでも、基本的な考え方は同じです。

例えば、1台のサーバが同時に処理できる要求数には限りがあります。

そのため、要求が集中すると待ち行列が発生します。

2. 待ち行列のモデル

2-1. 待ち行列モデルの構成

待ち行列モデルは、主に次の要素で構成されます。

到着する要求
待ち行列
サービスを提供する処理装置
処理を終えた要求

       到着
        │
        ▼
┌────────────────┐
│ 待ち行列       │
│ 要求A → 要求B  │
└───────┬────────┘
        │
        ▼
┌────────────────┐
│ サービス窓口   │
│ CPU・サーバ等  │
└───────┬────────┘
        │
        ▼
       完了

ここでいうサービスとは、処理装置が要求に対して実行する処理のことです。

Webサーバであれば、HTTPリクエストへの応答処理などが該当します。

2-2. 待ち行列の基本要素

待ち行列理論では、次の記号を利用します。

記号	名称	意味
λ（ラムダ）	平均到着率	単位時間当たりの平均到着件数
μ（ミュー）	平均サービス率	処理装置1台が単位時間に処理できる平均件数
1/μ	平均サービス時間	1件の処理に必要な平均時間
ρ（ロー）	利用率	処理装置がどれくらい使用されているか
Wq	平均待ち時間	処理開始までに待つ平均時間
W	平均応答時間	到着から処理完了までの平均時間
Lq	平均待ち行列長	処理待ちになっている平均件数
L	平均系内数	待機中と処理中を合わせた平均件数

これらの記号は、待ち行列の計算で頻繁に登場します。

3. トランザクションの到着

3-1. トランザクションとは

**トランザクション（Transaction）**とは、システムが処理する一つの要求や処理単位です。

待ち行列理論では、到着する仕事をトランザクションやジョブ、要求などと呼びます。

例えば、

Webページの表示要求
データベースへの検索要求
プリンタへの印刷要求

などです。

3-2. 平均到着率とは

**平均到着率（Arrival Rate）**とは、単位時間当たりに到着する要求の平均件数です。

一般的に、記号**λ（ラムダ）**で表します。

例えば、1分間に平均30件の要求が到着する場合、

λ = 30件/分

となります。

秒単位に変換すると、

30件 ÷ 60秒
= 0.5件/秒

です。

3-3. 平均到着間隔

平均到着間隔とは、要求が到着する平均的な時間間隔です。

平均到着率がλの場合、平均到着間隔は次の式で求められます。

平均到着間隔 = 1 / λ

例えば、

λ = 0.5件/秒

平均到着間隔
= 1 ÷ 0.5
= 2秒

となります。

つまり、平均すると2秒に1件の要求が到着する計算です。

ただし、実際に必ず2秒ごとに要求が到着するわけではありません。

要求の到着には、ばらつきがあります。

4. サービス時間

4-1. サービス時間とは

**サービス時間（Service Time）**とは、処理装置が一つの要求を処理するために必要な時間です。

例えば、サーバが1件の要求を処理するのに平均0.1秒かかる場合、

平均サービス時間 = 0.1秒

となります。

4-2. 平均サービス率とは

**平均サービス率（Service Rate）**とは、処理装置1台が単位時間当たりに処理できる平均件数です。

一般的に、記号**μ（ミュー）**で表します。

平均サービス時間が0.1秒の場合、

μ = 1 ÷ 0.1
  = 10件/秒

となります。

つまり、平均サービス率は10件/秒です。

平均サービス時間と平均サービス率の関係は、

平均サービス時間 = 1 / μ

です。

5. 利用率

5-1. 利用率とは

**利用率（Utilization）**とは、処理装置がどれくらいの割合で使用されているかを表す指標です。

記号**ρ（ロー）**を使用します。

M/M/1モデルのように処理装置が1台の場合、利用率は次の式で求められます。

ρ = λ / μ

λ：平均到着率
μ：平均サービス率

5-2. 利用率の計算例

例えば、

平均到着率：λ = 8件/秒
平均サービス率：μ = 10件/秒

の場合、

ρ = λ / μ

  = 8 ÷ 10

  = 0.8

となります。

百分率で表すと、

利用率 = 80%

です。

5-3. 利用率が高いとどうなる？

利用率が高くなると、処理装置が空いている時間が少なくなります。

そのため、要求が到着したときに処理装置が使用中である可能性が高くなり、待ち時間が増加します。

特に、M/M/1モデルでは利用率が100%に近づくほど、平均待ち時間が急激に増加します。

利用率

20% → 待ち時間は比較的小さい

50% → 待ち時間が増加

80% → 待ち時間が大きくなる

95% → 待ち時間が急増

100% → 安定した定常状態を保てない

ここが待ち行列理論の重要なポイントです。

利用率が高いほど効率的に見えても、待ち時間の面では不利になることがあります。

6. M/M/1モデル

6-1. M/M/1モデルとは

M/M/1モデルとは、待ち行列理論で利用される代表的なモデルです。

次の条件を仮定します。

要求の到着がポアソン過程に従う
サービス時間が指数分布に従う
処理装置が1台
要求は原則として到着順に処理される
待ち行列の容量に制限がない
要求元の数に制限がない
到着率とサービス率が一定

また、定常状態で平均待ち時間を求めるには、

λ < μ

が必要です。

これは、平均到着率が平均サービス率より小さいことを意味します。

6-2. M/M/1モデルの構成

       M/M/1モデル

要求の到着
    λ
    │
    ▼
┌─────────────┐
│ 待ち行列    │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ 処理装置1台 │
│    μ        │
└──────┬──────┘
       │
       ▼
    処理完了

このモデルでは、処理装置が1台なので、要求が集中すると順番待ちが発生します。

7. 平均待ち時間の計算

7-1. 平均待ち時間とは

**平均待ち時間（Average Waiting Time）**とは、要求が到着してから、処理が開始されるまでに待つ平均時間です。

記号Wqで表します。

M/M/1モデルでは、次の式で求められます。

Wq = λ / {μ（μ − λ）}

また、利用率ρを使うと、

Wq = ρ / {μ（1 − ρ）}

とも表せます。

さらに、平均サービス時間をTsとすると、

Wq = Ts × ρ /（1 − ρ）

となります。

7-2. 平均待ち時間の計算例

例えば、

平均到着率：λ = 8件/秒

平均サービス率：μ = 10件/秒

の場合を考えます。

まず、利用率を求めます。

ρ = 8 ÷ 10
  = 0.8

次に、平均待ち時間を求めます。

Wq = λ / {μ（μ − λ）}

   = 8 / {10 ×（10 − 8）}

   = 8 / 20

   = 0.4秒

したがって、

平均待ち時間は0.4秒です。

8. 平均応答時間の計算

8-1. 平均応答時間とは

**平均応答時間（Average Response Time）**とは、要求が到着してから処理が完了するまでの平均時間です。

待ち行列理論では、平均系内時間とも呼ばれます。

記号Wで表します。

平均応答時間には、待ち時間とサービス時間が含まれます。

平均応答時間 = 平均待ち時間 + 平均サービス時間

つまり、

W = Wq + 1/μ

です。

8-2. M/M/1モデルの平均応答時間

M/M/1モデルでは、次の式が成り立ちます。

W = 1 /（μ − λ）

例えば、

λ = 8件/秒

μ = 10件/秒

の場合、

W = 1 /（10 − 8）

  = 1 / 2

  = 0.5秒

となります。

平均応答時間は、0.5秒です。

先ほど求めた平均待ち時間と比較してみましょう。

平均待ち時間：0.4秒

平均サービス時間：0.1秒

平均応答時間
= 0.4 + 0.1
= 0.5秒

計算結果が一致します。

9. 利用率と平均待ち時間の関係

M/M/1モデルでは、利用率が高くなるほど待ち時間が急激に増加します。

平均サービス時間を0.1秒として計算してみましょう。

Wq = 0.1 × ρ /（1 − ρ）

利用率	平均待ち時間
20%	0.025秒
40%	約0.067秒
60%	0.150秒
80%	0.400秒
90%	0.900秒
95%	1.900秒
99%	9.900秒

注目したいのは、利用率90%から99%への変化です。

利用率は9ポイントしか増えていません。

しかし、平均待ち時間は、

0.9秒 → 9.9秒

と、11倍になります。

つまり、利用率が100%に近づくと、待ち時間が急激に増加するのです。

10. 待ち行列の長さ

10-1. 平均待ち行列長とは

**平均待ち行列長（Average Queue Length）**とは、処理開始を待っている要求の平均件数です。

記号Lqで表します。

M/M/1モデルでは、次の式で求められます。

Lq = ρ² /（1 − ρ）

例えば、利用率が80%の場合、

ρ = 0.8

Lq = 0.8² /（1 − 0.8）

   = 0.64 / 0.2

   = 3.2件

となります。

つまり、平均すると3.2件の要求が処理待ちになっています。

10-2. 平均系内数とは

**平均系内数（Average Number in System）**とは、待機中の要求と処理中の要求を合わせた平均件数です。

記号Lで表します。

M/M/1モデルでは、

L = ρ /（1 − ρ）

です。

利用率80%の場合、

L = 0.8 /（1 − 0.8）

  = 0.8 / 0.2

  = 4件

となります。

平均系内数は4件です。

このうち、

平均待ち行列長：3.2件

平均処理中件数：0.8件

となります。

処理装置が1台なので、平均処理中件数は利用率ρと一致します。

11. リトルの法則

11-1. リトルの法則とは

**リトルの法則（Little's Law）**とは、安定したシステムにおいて、平均件数・平均到着率・平均滞在時間の関係を表す法則です。

基本式は次のとおりです。

L = λW

L：平均系内数
λ：平均到着率
W：平均系内時間

また、待ち行列部分については、

Lq = λWq

が成り立ちます。

※ここでのλは、安定した状態における実際の平均流入・処理完了率です。

11-2. リトルの法則の計算例

例えば、

平均到着率：8件/秒

平均応答時間：0.5秒

の場合、

L = λW

  = 8 × 0.5

  = 4件

となります。

平均すると、システム内に4件の要求が存在することになります。

先ほどのM/M/1モデルで求めた結果と一致します。

11-3. 待ち行列長の計算

平均待ち時間が0.4秒の場合、

Lq = λWq

   = 8 × 0.4

   = 3.2件

となります。

このように、リトルの法則を利用すると、平均待ち時間から平均待ち行列長を求められます。

12. ネットワーク評価への適用

12-1. ネットワークでも待ち行列が発生する

待ち行列理論は、サーバだけでなくネットワークの性能評価にも利用できます。

例えば、ルータに大量のパケットが到着した場合です。

パケットA ─┐
パケットB ─┤
パケットC ─┤
           ▼
    ┌────────────┐
    │ ルータ     │
    │ 送信待ち   │
    │ バッファ   │
    └─────┬──────┘
          │
          ▼
       出力回線

出力回線が使用中の場合、後から到着したパケットはバッファで待機します。

このとき、待ち行列理論を利用して、平均待ち時間などを評価できます。

12-2. ネットワークにおける到着率とサービス率

ネットワークでは、次のように考えます。

待ち行列の要素	ネットワークでの意味
到着率λ	単位時間当たりに到着するパケット数
サービス率μ	単位時間当たりに送信できるパケット数
待ち行列	送信待ちのパケットが入るバッファ
サービス時間	パケットを送信するための時間
待ち時間	送信開始までバッファで待つ時間

12-3. ネットワークの利用率

例えば、ある回線に平均800パケット/秒が到着し、平均1,000パケット/秒を送信できるとします。

λ = 800パケット/秒

μ = 1,000パケット/秒

利用率は、

ρ = λ / μ

  = 800 / 1,000

  = 0.8

となります。

**利用率は80%**です。

12-4. 平均待ち時間の計算

このネットワークをM/M/1モデルで近似すると、

Wq = λ / {μ（μ − λ）}

   = 800 / {1,000 ×（1,000 − 800）}

   = 800 / 200,000

   = 0.004秒

となります。

つまり、

平均待ち時間は4ミリ秒です。

平均サービス時間は、

1 / μ
= 1 / 1,000
= 0.001秒

なので、平均応答時間は、

W = 0.004 + 0.001

  = 0.005秒

です。

したがって、平均系内時間は5ミリ秒となります。

※これはポアソン到着・指数分布のサービス時間などを仮定した単純なモデルでの計算です。実際のネットワークでは、パケット長や通信の集中、バッファ容量などによって結果が変わります。

12-5. ネットワーク評価で重要なこと

ネットワークの遅延には、主に次の要素があります。

処理遅延
待ち行列遅延
送信遅延
伝搬遅延

処理遅延

ルータなどがパケットのヘッダを確認し、転送先を判断するための時間です。

待ち行列遅延

パケットが送信されるまでバッファで待機する時間です。

送信遅延

パケットの全ビットを回線へ送り出すために必要な時間です。

伝搬遅延

信号が通信媒体を伝わるために必要な時間です。

待ち行列理論は、このうち特に待ち行列遅延の評価に役立ちます。

13. ケンドール記号

13-1. ケンドール記号とは

**ケンドール記号（Kendall's Notation）**とは、待ち行列モデルの特徴を簡潔に表すための記法です。

基本形は、

A / B / s

です。

それぞれの意味は次のとおりです。

記号	意味
A	到着間隔の確率分布
B	サービス時間の確率分布
s	サービス窓口の数

例えば、

M/M/1

であれば、

到着間隔：指数分布
サービス時間：指数分布
サービス窓口：1台

を意味します。

13-2. ケンドール記号の拡張形

ケンドール記号には、次のような拡張形もあります。

A / B / s / K / N / D

記号	意味
A	到着間隔の分布
B	サービス時間の分布
s	サービス窓口数
K	システム内に収容できる最大件数
N	要求元の母集団の大きさ
D	処理順序の規則

KやNを省略した場合、通常は無限大を仮定します。

また、Dを省略した場合は、一般的に先着順を仮定します。

14. 到着の分布とサービスの分布

14-1. なぜ確率分布が必要なのか

実際のシステムでは、要求が一定間隔で到着するとは限りません。

例えば、次のような到着が考えられます。

0秒：要求A
1秒：要求B
1.2秒：要求C
5秒：要求D
5.1秒：要求E

このように、要求の到着にはばらつきがあります。

また、サービス時間も一定ではありません。

簡単な検索であれば短時間で完了しますが、複雑な検索では時間がかかる場合があります。

そのため、待ち行列理論では確率分布を利用します。

15. ポアソン分布

15-1. ポアソン分布とは

**ポアソン分布（Poisson Distribution）**とは、一定時間内に発生する事象の回数を表す確率分布です。

例えば、

1分間に到着する要求数
1秒間に到着するパケット数
1時間に発生する問い合わせ数

などをモデル化する際に利用されます。

15-2. ポアソン分布の式

一定時間内の平均発生回数をmとすると、ちょうどk回発生する確率は次の式で表されます。

P(X = k) = e^(-m) × m^k / k!

e：自然対数の底
m：対象時間内の平均発生回数
k：発生回数
k!：階乗

例えば、1分間に平均2件の要求が到着する場合、1分間にちょうど0件到着する確率は、

P(X = 0)
= e^(-2) × 2^0 / 0!
= e^(-2)
≒ 0.1353

となります。

つまり、約13.5%です。

16. 指数分布

16-1. 指数分布とは

**指数分布（Exponential Distribution）**とは、事象が発生するまでの時間間隔などを表す確率分布です。

例えば、

次の要求が到着するまでの時間
1件のサービスが完了するまでの時間

などをモデル化する際に利用されます。

16-2. 指数分布の式

平均到着率がλのポアソン過程では、到着間隔Tは指数分布に従います。

このとき、

P(T > t) = e^(-λt)

となります。

これは、次の要求が到着するまでの時間がtを超える確率を表します。

例えば、平均到着率が1件/秒の場合、次の要求が到着するまで1秒を超える確率は、

P(T > 1)
= e^(-1)
≒ 0.3679

となります。

約36.8%です。

17. ポアソン分布と指数分布の関係

この2つは、セットで覚えることが重要です。

ポアソン分布は「一定時間内の発生回数」。

指数分布は「次の発生までの時間間隔」。

比較項目	ポアソン分布	指数分布
表すもの	発生回数	時間間隔
例	1分間に何件到着するか	次の要求まで何秒か
値の種類	0、1、2、3…の整数	0以上の連続値
M/M/1との関係	到着件数の分布	到着間隔・サービス時間の分布

なお、到着件数がポアソン分布に従うだけでなく、時間的に独立した一定率のポアソン過程を仮定することで、到着間隔が指数分布になります。

18. ケンドール記号で利用する主な分布

ケンドール記号では、次のような文字が使われます。

記号	意味
M	指数分布（マルコフ型）
D	一定時間（確定的）
G	一般分布
Eₖ	アーラン分布

M

**M（Markovian）**は、到着間隔やサービス時間が指数分布に従うことを表します。

D

**D（Deterministic）**は、到着間隔やサービス時間が一定であることを表します。

G

**G（General）**は、一般的な確率分布を表します。

Eₖ

**Eₖ（Erlang Distribution）**は、形状母数kのアーラン分布を表します。

19. 代表的な待ち行列モデル

モデル	到着間隔	サービス時間	窓口数
M/M/1	指数分布	指数分布	1
M/M/2	指数分布	指数分布	2
M/M/s	指数分布	指数分布	s
M/D/1	指数分布	一定	1
M/G/1	指数分布	一般分布	1
D/D/1	一定	一定	1

例えば、M/D/1モデルでは、到着間隔は指数分布に従いますが、サービス時間は一定です。

一方、M/G/1モデルでは、サービス時間に一般的な確率分布を利用します。

20. M/M/sモデルとは

20-1. M/M/sモデルの基本

M/M/sモデルとは、サービス窓口がs台ある待ち行列モデルです。

M/M/1モデルでは、処理装置が1台でした。

一方、M/M/sモデルでは、複数の処理装置が並列に要求を処理します。

例えば、3台のサーバがある場合です。

          M/M/3モデル

要求の到着
     │
     ▼
┌─────────────┐
│ 共通待ち行列│
└──────┬──────┘
       │
  ┌────┼────┐
  │    │    │
  ▼    ▼    ▼
┌───┐┌───┐┌───┐
│S1 ││S2 ││S3 │
└───┘└───┘└───┘
  │    │    │
  ▼    ▼    ▼
   処理完了

このモデルでは、空いている処理装置があれば要求を処理できます。

20-2. M/M/sモデルの利用率

M/M/sモデルでは、サービス窓口がs台あるため、全体の平均処理能力は、

s × μ

となります。

そのため、利用率は次の式で求められます。

ρ = λ /（sμ）

λ：平均到着率
μ：1台当たりの平均サービス率
s：サービス窓口数

定常状態が成立するためには、

λ < sμ

が必要です。

20-3. M/M/sモデルの利用率計算

例えば、

平均到着率：λ = 12件/秒

1台当たりのサービス率：μ = 10件/秒

サーバ台数：s = 2台

の場合、

ρ = λ /（sμ）

  = 12 /（2 × 10）

  = 12 / 20

  = 0.6

となります。

つまり、**各サーバの平均利用率は60%**です。

※各サーバが同じ処理能力を持ち、共通待ち行列から処理するモデルを想定しています。

21. M/M/sモデルの平均待ち時間

21-1. M/M/sモデルの計算式

M/M/sモデルでは、M/M/1モデルより計算が複雑になります。

まず、次の値を定義します。

a = λ / μ

ρ = λ /（sμ）= a / s

このとき、システム内に要求が0件存在する確率P₀は、次の式で求められます。

P₀ = 1 / {Σ[n=0からs−1]（aⁿ / n!）+ aˢ /［s!（1−ρ）］}

ここで、

Σ：指定された範囲の値を合計する記号
n!：階乗
P₀：システム内に要求が存在しない確率

です。

21-2. 待ちが発生する確率

M/M/sモデルでは、すべての処理装置が使用中の場合、要求は待つことになります。

到着した要求が待つ確率は、次の式で求められます。

P(wait) = P₀ × aˢ /［s!（1−ρ）］

これは、**アーランC公式（Erlang C Formula）**と呼ばれるものです。

21-3. 平均待ち時間

平均待ち時間Wqは、次の式で求められます。

Wq = P(wait) /（sμ − λ）

また、平均応答時間Wは、

W = Wq + 1/μ

となります。

このように、M/M/sモデルでは、まず待ちが発生する確率を求め、その結果から平均待ち時間を計算します。

22. M/M/2モデルの計算例

実際に計算してみましょう。

22-1. 問題

次の条件で動作するM/M/2モデルがあります。

平均到着率：λ = 12件/秒

1台当たりのサービス率：μ = 10件/秒

サービス窓口数：s = 2台

平均待ち時間と平均応答時間を求めます。

22-2. 利用率を求める

まず、利用率ρを求めます。

ρ = λ /（sμ）

  = 12 /（2 × 10）

  = 0.6

利用率は60%です。

22-3. aを求める

a = λ / μ

  = 12 / 10

  = 1.2

となります。

22-4. P₀を求める

s = 2なので、

P₀ = 1 / {1 + a + a² /［2（1−ρ）］}

です。

値を代入すると、

P₀
= 1 / {1 + 1.2 + 1.2² /［2 ×（1−0.6）］}

= 1 / {1 + 1.2 + 1.44 / 0.8}

= 1 / {1 + 1.2 + 1.8}

= 1 / 4

= 0.25

となります。

つまり、システム内に要求が存在しない確率は25%です。

22-5. 待ちが発生する確率を求める

次に、アーランC公式を利用します。

P(wait) = P₀ × a² /［2（1−ρ）］

値を代入すると、

P(wait)
= 0.25 × 1.44 / 0.8

= 0.25 × 1.8

= 0.45

となります。

つまり、**到着した要求が待つ確率は45%**です。

22-6. 平均待ち時間を求める

平均待ち時間は、

Wq = P(wait) /（sμ − λ）

です。

Wq
= 0.45 /（2 × 10 − 12）

= 0.45 / 8

= 0.05625秒

したがって、

平均待ち時間は約0.056秒です。

ミリ秒に変換すると、

56.25ミリ秒

となります。

22-7. 平均応答時間を求める

平均応答時間は、

W = Wq + 1/μ

です。

W
= 0.05625 + 1/10

= 0.05625 + 0.1

= 0.15625秒

したがって、

平均応答時間は約0.156秒です。

23. M/M/1とM/M/2の比較

ここで、サーバを1台から2台に増やした場合を比較してみましょう。

条件は次のとおりです。

平均到着率：12件/秒

1台当たりのサービス率：10件/秒

M/M/1の場合

λ = 12件/秒

μ = 10件/秒

となるため、

λ > μ

です。

この場合、到着する要求の平均件数が処理能力を超えているため、安定した定常状態が成立しません。

したがって、有限の定常平均待ち時間を求められません。

M/M/2の場合

λ = 12件/秒

sμ = 20件/秒

なので、

λ < sμ

となります。

定常状態が成立し、先ほど求めたように、

平均待ち時間：約0.056秒

平均応答時間：約0.156秒

となります。

このように、処理装置を増やすことで、システムの処理能力を高め、待ち時間を短縮できる場合があります。

24. M/M/sモデルとスケールアウトの関係

前の記事では、スケールアウトについて学びました。

スケールアウトとは、サーバ台数を増やしてシステム全体の処理能力を高めることです。

待ち行列理論では、サービス窓口数sを増やすことに相当する場合があります。

【増強前】

要求
 │
 ▼
サーバ1台

M/M/1モデル

【増強後】

       要求
        │
        ▼
     待ち行列
        │
   ┌────┼────┐
   ▼    ▼    ▼
 サーバ サーバ サーバ
   A     B     C

M/M/3モデル

ただし、実際のシステムでは、単純にサーバ台数を増やすだけで理論どおりに性能が向上するとは限りません。

例えば、

データベースがボトルネックになる
ネットワーク帯域が不足する
サーバ間の通信が増加する
負荷が均等に分散されない

といった問題があるためです。

そのため、待ち行列理論は、システム性能を予測するための一つのモデルとして利用します。

25. 応用情報技術者試験で押さえたいポイント

① 平均到着率と平均サービス率

平均到着率：λ

平均サービス率：μ

平均サービス時間：1/μ

② M/M/1モデルの利用率

ρ = λ / μ

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

Wq = λ /［μ（μ−λ）］

④ M/M/1モデルの平均応答時間

W = 1 /（μ−λ）

⑤ リトルの法則

L = λW

Lq = λWq

⑥ M/M/sモデルの利用率

ρ = λ /（sμ）

⑦ M/M/sモデルの平均待ち時間

Wq = P(wait) /（sμ−λ）

26. 練習問題

最後に、今回の内容を確認してみましょう。

問題1：利用率

あるサーバには、平均6件/秒の要求が到着します。

サーバは、平均10件/秒の要求を処理できます。

利用率はいくらでしょうか。

解答

ρ = λ / μ

  = 6 / 10

  = 0.6

答え：60%

問題2：平均待ち時間

次のM/M/1モデルがあります。

平均到着率：λ = 6件/秒

平均サービス率：μ = 10件/秒

平均待ち時間を求めましょう。

解答

Wq = λ /［μ（μ−λ）］

   = 6 /［10 ×（10−6）］

   = 6 / 40

   = 0.15秒

答え：0.15秒

問題3：平均応答時間

問題2の条件で、平均応答時間を求めましょう。

解答

W = 1 /（μ−λ）

  = 1 /（10−6）

  = 1 / 4

  = 0.25秒

答え：0.25秒

問題4：平均待ち行列長

問題2の条件で、平均待ち行列長を求めましょう。

解答

リトルの法則を利用します。

Lq = λWq

   = 6 × 0.15

   = 0.9件

答え：0.9件

問題5：M/M/2モデルの利用率

次の条件で、各サーバの平均利用率を求めましょう。

平均到着率：λ = 15件/秒

1台当たりのサービス率：μ = 10件/秒

サーバ台数：s = 2台

解答

ρ = λ /（sμ）

  = 15 /（2 × 10）

  = 15 / 20

  = 0.75

答え：75%

まとめ

この記事で覚えること

待ち行列理論は、処理要求の待ち時間や待ち行列の長さを分析する理論
平均到着率λは、単位時間当たりに到着する要求の平均件数
平均サービス率μは、処理装置1台が単位時間に処理できる平均件数
平均サービス時間は、1/μで求められる
利用率ρは、処理装置が使用されている割合
M/M/1モデルは、到着間隔とサービス時間が指数分布に従い、処理装置が1台のモデル
平均待ち時間Wqは、処理開始までに待つ平均時間
平均応答時間Wは、到着から処理完了までの平均時間
平均待ち行列長Lqは、処理待ちになっている平均件数
リトルの法則は、平均件数・平均到着率・平均滞在時間の関係を表す法則
ケンドール記号は、待ち行列モデルの到着分布・サービス分布・窓口数などを表す記法
ポアソン分布は、一定時間内の発生回数を表す確率分布
指数分布は、事象が発生するまでの時間間隔などを表す確率分布
M/M/sモデルは、サービス窓口がs台ある待ち行列モデル
アーランC公式は、M/M/sモデルで到着した要求が待つ確率を求める公式
ネットワーク評価では、パケットの到着率や送信能力から待ち時間を推定できる

🍯 はちみつメモ

待ち行列理論は「仕事が来る速さ」と「仕事を処理する速さ」から、待ち時間を考える理論！

λは到着率、μはサービス率、ρは利用率と覚えよう。

M/M/1モデルでは、利用率が100%に近づくほど待ち時間が急激に増えるんだ。

平均待ち時間は処理が始まるまで、平均応答時間は処理が終わるまでという違いも重要だよ！

そして、サーバを複数台に増やした場合はM/M/sモデルで考えられるよ。

応用情報技術者試験では、まずM/M/1モデルの利用率・平均待ち時間・平均応答時間の公式を使いこなせるようにしよう！