アウトライン
3-1 M/M/S 待ち行列
3-2 アーランの即時式モデル
2
3-1 M/M/S 待ち行列
3
X: 到着過程
→ポアソン分布のとき「M」と書く
Y： 処理時間分布
→指数分布のとき「M」と書く
Z: サーバ数
個数を限定しないとき「S」と書く
K：待ち行列の長さの制限
制限しないときは何も書かない
4
ケンドール記法 M/M/S
M/M/S 待ち行列モデル
サーバ数：S
待ち行列
サーバ
ポアソン分布で到着
処理時間は指数分布 5
M/M/S 待ち行列モデルの解析
•状態遷移
•システム内のジョブ数を「状態」と見る
•定常状態
•定常状態での、各「状態」の確率を求める
•システムの「処理率」を求める
6
状態
状態０： システム内のジョブ数が ０
状態１： システム内のジョブ数が １
状態S: システム内のジョブ数がS
7
状態遷移
•ジョブが到着：
状態 ｋから状態 ｋ+１に遷移
•ジョブが完了：
状態 ｋから状態 ｋｰ１ に遷移
8
遷移確率に関する方程式
•微小時間 ⊿ｔ（限りなく０に近い）につい
ての式
•「ジョブの到着」と「ジョブの完了」は、
「同時」には起きない
•「ジョブの完了」の確率は、⊿ｔ と μの式
•「ジョブの到着」の確率は、⊿ｔ と λの式
9
•ｋ≦S ならば（ｋは状態番号）
•サーバに空きがある
ｋμ⊿t(1ｰμ⊿t) ≒ｋμ⊿t
•ｋ＞Sならば（ｋは状態番号）
•サーバは全て忙しい
Sμ⊿t(1ｰμ⊿t) ≒Sμ⊿t
k-1
S-1
10
「ジョブの完了」に関する式
•ジョブが到着：
状態 ｋから状態 ｋ+１に遷移
λ⊿t
•ジョブが完了：
状態 ｋから状態 ｋ－１ に遷移
ｋ≦S ならば： ｋμ⊿t
ｋ＞Sならば： Sμ⊿t
11
状態遷移
状態遷移図
１－λ
状態０ 状態１
λ
μ
１－μ－λ
λ
２μ
状態
S-1
状態
S
λ
Sμ
１－Sμ－λ
λ
Sμ
λ
Sμ
状態
S＋1
１－Sμ－λ
１－（S－１）μ－λ
12
定常状態方程式
０＜ｎ＜S では
（λ＋ｎμ）Pｎ= λPnｰ1+ （ｎ＋１）μPn+1
S ≦ｎでは
（λ＋Sμ）Pｎ= λPnｰ1+ SμPn+1
λP0= μP1
13
定常確率をP0で表す
０＜ｎ＜S では
Pn =
S ≦ｎでは
Pn =
λP0
μn!
( )n
λP0
μS!S
( )n
n-S
14
システム処理能力ρ
ρ= λ/μ
• λ⊿
ｔ
：「時間 (t, t+⊿t) に到着するジョ
ブ数」の平均
• μ⊿
ｔ
： 「サーバがジョブを処理中の間，
⊿
ｔ
内に完了する処理数」の平均
15
待ち合わせが生じる確率
•システム内のジョブ数が S 以上
•Pqueue = ∑ Pn
= ∑
= ∑ P0
n=S
∞
λP0
μS!S
( ) n
n-S
n=S
∞
n=S
∞(Sρ) 1
S! S
n
n-S
16
3-2 アーランの即時式モデル
17
X: 到着過程
→ポアソン分布のとき「M」と書く
Y： 処理時間分布
→指数分布のとき「M」と書く
Z: サーバ数
個数を限定しないとき「S」と書く
K：待ち行列の長さの制限
K = 1
18
ケンドール記法 M/M/S/1
M/M/S/1 のとき
サーバ数：S
K=1 なので
待ち行列なし
処理時間は指数分布
ポアソン分布で到着
19
アーランの即時式モデル
•待ち行列モデル： M/M/S/S
•入力回線数： 無限
•待ち行列長： L＝０
•システム内の最大占有サーバ数： K＝S
20
「即時式」の意味
K = 1 なので，次の性質を持つ
•待ち行列なし
•待ち行列長は 0
•システム内の占有サーバ数がS （すべてのサーバ
が占有されている）のとき，到着したジョブは棄
却される
•サーバの空きがあれば，直ちに処理される
→即時式
21
•ジョブの到着
•平均λのポアソン分布
→ある時刻に客が到着してから時間t内に次の客が到着
する確率はポアソン分布に従う： １－e－λｔ
•微少時間⊿tの間にジョブが到着する確率：λ⊿ｔ
•ジョブの処理時間
•平均１/μの指数分布
•微少時間⊿tの間に処理が終わる確率： μ⊿ｔ
システム処理能力：ρ＝λ/μ
22
ジョブのモデル
状態
状態０： 系内のジョブの数が ０
状態１： 系内のジョブの数が １
状態S: 系内のジョブの数が S
（状態はSまで）
23
•ジョブが到着：
1) ｋ＜S のとき
状態 ｋ から状態 ｋ+１ に遷移
2) ｋ=S のとき
状態Sのまま（新しい到着は棄却される）
•ジョブの回線の占有終わり：
状態 ｋから状態 ｋｰ１ に遷移
24
状態遷移
•ジョブが到着：
1) ｋ＜S のとき
状態 ｋ から状態 ｋ+１に遷移： λ⊿t
•ジョブの回線の占有終わり：
状態 ｋ から状態 ｋｰ１ に遷移 ： ｋμ⊿t
25
状態遷移
状態遷移図
１－λ
状態０ 状態１
λ
μ
１－μ－λ
λ
２μ
状態
S-1
状態
S
λ
Sμ
μ－Sμ
１－（S－１）μ－λ
λ
（S-1)μ
26
定常状態についての方程式
（λ＋ｎμ）Pｎ= λPnｰ1+ （ｎ＋１）μPn+11
λP0= μP1
λPn-1 = SμPn
27
•定常状態で，系内にn個のジョブ（0≦n≦s）がある
確率を Pn とすると
•棄却率：
•システム内の占有サーバ数が Sになる確率：Ps
•上の式で，n=s として計算する
!2
1
!
)( 2
s
n
tP s
n
n
28
棄却率
