アウトライン
2-1 待ち行列
2-2 ケンドール記法
2-3 M/M/1/1 待ち行列
2-4 M/M/1/1 待ち行列の解析
2-5 M/M/1 待ち行列の解析
2
2-1 待ち行列
3
•スタック
•データの挿入と取り出しの両方を列の一方の端か
ら行う
•キュー
•一方の端から挿入を，もう一方の端から取り出し
を行う
•取り出されるのは最も古いデータ
•最初に入れたデータが最初に取り出される
•FIFO(first-in-first-out，先入れ先出し)と呼ぶ
データ データ データ データ
値の追加 値の取り出し
4
スタックとキュー
到着
サーバ
待ち行列
5
待ち行列
待ち行列
•処理を受けるために順番待ちをする人がな
す列
•銀行の窓口や入場券売り場など
6
待ち行列の長さ，システム内の
ジョブ総数
到着
サーバ
待ち行列
待ち行列の長さ
システム内のジョブ総数 7
待ち時間
ジョブ到着から
サービス開始まで
到着
サーバ
待ち行列
遅延時間
ジョブ到着から
サービス終了まで
8
遅延時間，待ち時間
λD ＝N
D: 「遅延時間」の平均
N: 「システム内のジョブ総数」の平均
λDW= NW
DW:「待ち時間」の平均
NW:「待ち行列の長さ」の平均
以下，システム内のジョブ総数，待ち行列の長さを
考える
9
遅延時間，待ち時間
2-2 ケンドール記法
10
到着
サーバ
待ち行列
サーバ数： Z
時間 (t, t+⊿t) に到着
するジョブ数：Xt
ジョブの処理を行う
処理時間：Y
11
ケンドール記法 X/Y/Z
到着
サーバ
待ち行列
サーバ数： Z
時間 (t, t+⊿t) に到着
するジョブ数：Xt
ジョブの処理を行う
処理時間：Y
待ち行列の長さを
K－１に制限
12
ケンドール記法 X/Y/Z/K
•待ち行列の長さに限りがある
•待ち行列の長さが「最大で Ｋ－１」に制限されるとき，
システム内のジョブ総数は Ｋ に制限される
•Ｋ＝０ の場合は
•すでにサーバが他のジョブを処理中のとき
•到着したジョブは棄却される（待ち行列に入らない）
•サーバがジョブを処理していないとき
•到着したジョブは直ちに処理される
13
待ち行列の長さの制限
X/Y/Z/K
X: 到着過程
Y： 処理時間分布
Z: サーバ数
K：待ち行列の長さ制限
（待ち行列の長さの最大長：K－１）
X/Y/Z
待ち行列の長さに制限無し
14
ケンドール記法
2-3 M/M/1/1 待ち行列
15
X: 到着過程
→ポアソン分布のとき「M」と書く
Y： 処理時間分布
→指数分布のとき「M」と書く
Z: サーバ数
K：待ち行列の長さの制限
16
ケンドール記法
到着 サーバ
待ち行列
•到着過程： ポアソン分布
•処理時間分布： 指数分布
•サーバの個数： １個
•待ち行列の長さの制限： K＝1
17
M/M/1/1 待ち行列
「分布」の種類
M:ポアソン分布／指数分布
Ek: k相のアーラン分布
D: 一定分布
G: 一般分布
GI: 独立性を有する一般分布
18
平均到着率
•単位時間に到着するジョブの平均値
•待ち行列に加わろうとするジョブのやって
くる頻度
19
•ジョブの到着がランダム
•「時間 (t, t+⊿t) に到着するジョブ数」に注目
•⊿tに比例して増加
•平均値： λ⊿
ｔ
• λは単位時間あたりの平均ジョブ数
20
到着率λのポアソン分布
ポアソン分布の特徴
•同じ幅をもった時間区間あたりの到着の仕方
は，時刻に依存しない
•共通部分のない時間区間たちのそれぞれの到
着の仕方は独立である
•同時刻に2人のジョブがやってくることはない
•ごく短い時間 ⊿tの間にジョブが1人来る確率
はλ⊿t
21
平均処理率
•単位時間に処理を受けるジョブの平均値
•処理がどの程度で行われているかの尺度
22
•ジョブの完了時刻がランダム
•「あるジョブの処理の完了から次のジョブの完
了までの時間」に着目
•平均値： １／μ
• μは単位時間あたりの平均ジョブ完了数
•サーバがジョブを処理中の間，⊿
ｔ
内に完了する
処理数： μ⊿
ｔ
23
処理率μの指数分布
指数分布の特徴
•進行中の処理が終了する確率は，それまでに処理
に要した時間に依存しない
•ある時刻に開始される処理は，それ以前に行われ
た処理や到着に依存しない
•ごく短い時間 ⊿tの間に処理が1つ終了する確率は
μ⊿t
24
•微小時間 ⊿tの間に到着するジョブ：
•たかだか1人
•時間 ⊿tの間に終了する処理：
•たかだか1つ
•時間 ⊿tの間に「ジョブの到着」「処理の終了」
が同時になされることはない
25
微小時間の意味
2-4 待ち行列の解析
26
•待ち行列の長さ
•システム内のジョブ総数
•ジョブの遅延時間
•ジョブの待ち時間
27
待ち行列の解析での解析の対象
•確率的に解析
•待ち行列のシステムの状態と状態遷移による
解析
システムの状態：P0, P1, P2, ・・・
（添字は，システム内のジョブ総数）
•定常状態での待ち行列の長さ，ジョブ総数を
算出する
•ｔ→∞では，システムの状態は定常確率に漸近す
る（初期状態を無視できる）
28
解析手順
システム処理能力ρ
ρ= λ/μ
• λ⊿
ｔ
：「時間 (t, t+⊿t) に到着するジョ
ブ数」の平均
• μ⊿
ｔ
： 「サーバがジョブを処理中の間，
⊿
ｔ
内に完了する処理数」の平均
※待ち行列の長さに限りがないとすると：
λ ＜μ （つまりρ＜１）である必要がある
（さもないと待ち行列があふれる）
29
ジョブを処理
していない ジョブを処理中
ジョブが到着した
全てのジョブが処理終了した
ジョブが到着
しない
ジョブが処理
終了しない
状態名 P0 とする 状態名 P1 とする
30
個々のサーバの状態と状態遷移
・K=1 なので，待ち行列の長さは０か１
・状態遷移の確率は，下図の通り
待ち行列の
長さが０
（ジョブを処理していない）
待ち行列の
長さが１
（ジョブを処理中）
λ⊿t
μ⊿t
１－λ⊿t１－ μ⊿t
31
M/M/1/1待ち行列でのサーバの状態遷移
状態名 P0 状態名 P1
P0( t+⊿t) = (1－λ⊿t)P0(t) + μ⊿tP1(t)
P1( t+⊿t) = λ⊿tP0(t) + (1－μ⊿t)P1(t)
32
M/M/1/1待ち行列でのサーバの状態遷移
lim P0(t), lim P1(t) を求めよう
t→∞ t→∞
t→∞ のとき P0(t) →P0, P1(t)→P1（収束する）と仮定す
る
d P0( t)
dt = －λP0(t) +μP1(t)だが（理由は後述）
仮定より，t→∞ のときd P0( t)
dt = 0 なので
－λP0+μP1= 0
これと P0+P1= 1 から， P0 = , P1=
λ+μ
μ
λ+μ
λ
33
M/M/1/1待ち行列での定常確率
P0( t+⊿t) = (1－λ⊿t)P0(t) + μ⊿tP1(t)
P0( t+⊿t) －P0(t) = －λ⊿tP0(t) +μ⊿tP1(t)
= －λP0(t) +μP1(t)
= －(λ+μ)P0(t)+μ
⊿t
P0( t+⊿t) －P0(t)
⊿t
P0( t+⊿t) －P0(t)
（P0(t) + P1(t) = 1から）
P0(t)の方程式が求まった 34
M/M/1/1待ち行列での定常確率
lim = －(λ+μ)P0(t)+μ
= －(λ+μ)P0(t)+μ
⊿t
P0( t+⊿t) －P0( t)
⊿t→0
d P0( t)
dt
これは P0( t ) の微分方程式
P0( t) = λ+μ
μ+ ( P0( 0 ) －) e
λ+μ
μ－（λ+μ）t
lim P0( t) =
⊿t→0 λ+μ
μ
35
M/M/1/1待ち行列での定常確率
定常状態における性質
－λP0+μP1= 0
つまり λ⊿t lim P0(t) = μ⊿t lim P1(t)
t→∞ t→∞
新たなジョブが⊿t
以内に到着する確率
処理中のジョブが⊿t
以内に完了する確率
36
•定常状態
•lim P0(t) =
•lim P1(t) =
•定常状態でのサーバ内のジョブ総数
•0である確率： lim P0(t), 1である確率：lim P1(t)
t→∞
t→∞
ρ
１
１＋ρ
１＋ρ
t→∞
t→∞
（但し ρ= λ/μ）
37
まとめ
M/M/1 待ち行列
38
到着 サーバ
待ち行列
39
M/M/1 待ち行列
•到着過程： ポアソン分布
•処理時間分布： 指数分布
•サーバの個数： １個
•待ち行列の長さの制限： 制限なし
M/M/1 待ち行列
•処理の窓口は1つ
•処理を受けるための列は1つ
•いったん行列に加わったら，処理を受けるま
で待ち続ける
•ジョブの到着の仕方はポアソン分布に従う
•処理時間の分布は指数分布に従う
40
•時刻tにジョブが n 個ある確率： Pn(t)とおく
(n=0,1,2,・・・)
•時刻 t+⊿t にジョブが1個もいないのは，次のいずれかの
場合
1. ジョブが1個もいなくて，⊿tに新たなジョブが来なかった
P(A)=P0(t)*(1- λ⊿t)
2. １個のジョブが処理を受けていて，⊿tの間に処理が終了した
P(B)=P1(t)*μ⊿t
•これらは独立な事象なので，
P0(t+⊿t) = P0(t)*(1-λ⊿t) + P1(t)* μ⊿t
41
時刻 t+⊿t の時点で，ジョブが1個もない確率
続き
•Pn(t) は，時刻に依存しない（定常状態）と考
えて
Pn(t +⊿t) = Pn(t)
•前ページの式に代入すると
P0(t) λ⊿t=P1(t)μ⊿t
•つまり
P0(t) λ=P1(t)μ
42
Pn(t)
•時刻が t から t + ⊿t になった時点で，ジョブの総数
がn である場合は以下の3通り
•時刻tにn 個で，新たなジョブが到着せず，処理も終了し
なかった
P(A) = Pn(t)*(1-λ⊿t)*(1-μ⊿t)
= Pn(t)*(1-λ⊿t– μ⊿t)
•時刻 t にn-1個で，新たなジョブが1つ到着した
P(B) = Pn-1(t)*λ⊿t
•時刻 t にn+1 個で，ジョブの処理が1つ終了した
P(C) = Pn+1(t)*μ⊿t
43
•Pn(t+⊿t)=P(A)+P(B)+P(C)から
Pn(t)(λ + μ) = Pn-1(t)λ + Pn+1(t)μ
44
続き
λP0= μP1
(λ+μ)P1= λP0+μP2
(λ+μ)Pi= λPi-1+μPi+1
45
まとめ
以上から，定常状態における状態遷移
については，次が成り立つ
P1= ρP0
P2= (1+ρ)P1－ρP0
=(1+ρ) ρP0－ρP0
= ρ P0
Pi = ρ P0
一方，ΣPi=1 なので Pi = （1－ρ）ρ
2
i
i
46
すべての状態の確率を P0 の式で書く
ΣPi = 1
つまり， P0(t)*(1+ρ +ρ +・・・) = 1
• ρ≧1
•処理できるジョブ数より，やってくる方が多い
• 1+ρ +ρ +・・・は発散する
• ρ<1
• 1+ρ +ρ +・・・=1/（1-ρ） （発散しない）
•P0(t)=1-ρ
47
12
1 2
1 2
続き
Ｎ= ΣnPn
= Σn（1－ρ）ρ
=
Ｎｗ = Σ（n－1)Pn
= ΣnPn－（１－P0）
= N －（１－P0）
=
n
ρ
１－ρ
ρ
１－ρ
2
48
平均ジョブ数，平均待ちジョブ数
平均ジョブ数
•平均ジョブ数をLとおくと
•Lを計算すると
L = ΣnPn
n=0
∞
L= 1-ρ
ρ
49
•処理を受けているジョブを含まない待ち行列
内の平均ジョブ数: Lq
Lq=Σ(n-1)Pn
=Σ(n-1)(1-ρ)ρn
=ρΣ(n-1)(1-ρ)ρn-1
＝ρΣn(1-ρ)ρn
=ρΣnPn
=ρL
Lq=
n=1
∞
n=1
∞
n=1
∞
n=1
∞
n=1
∞
1-ρ
ρ2
50
平均待ち時間
•ジョブが並びはじめて処理を受け始めるま
での時間の平均： Wq
Lq=λWq
•このことから
Wq= = =
λ λ(1-ρ) μ(1-ρ)
Lqρ ρ2
51
おわりに
•待ち行列の数理
•システム内のジョブ総数
•待ち行列の長さ
•待ち行列の定常状態
•状態遷移
•定常確率
「確率」を使って，待ち行列の
振る舞いをとらえる
52
•ある銀行には４つの窓口がある．この銀行に，１
分に1人の割合で客がポアソン到着するとしよう．
また，１人の客のサービス時間は平均3分の指数
分布に従うものとする．単純のために，1度銀行
に入った客は，サービスを受けるまで必ず待つと
いうことを仮定しよう
（１）この場合のケンドール表記を書け
Ｍ／Ｍ／４
練習１
53
（２）「定常状態」において，１分あたりに平
均で，客は何人帰るか
サーバ４つ
到着
待ち行列
１分あたり平均
１人到着する
１分にあたり
平均３分の処理時間
１分あたり平均
１人帰る
54
（３）システム処理能力（ρ）を答えよ．
サーバ４つ
到着
待ち行列
１分にあたり
平均３分の処理時間
１分あたり平均
１人帰る
１分あたり平均
１人到着する
λ=1, Ｓ=4, μ=1/3 より，
ρ= λ／Ｓμ= ３／４
55
•１つの窓口しかない銀行を考える
•客は，銀行にやってきたとき窓口が空いているか
どうか確認する
•空いていれば窓口で用事を済ませる
•空いていなければあきらめて家に帰り，銀行の用
事を忘れるものとする
到着
待ち行列なし
１分あたり平均
１人帰る
練習２
56
•客は，平均２０分あたり１人のポアソン分布
で銀行に到着し，すべての客は窓口に１０分
間（等しい時間）滞在するとしよう．
•客があきらめて帰る確率はいくらか
•客の到着はλ = 1/20 のポアソン分布
•t = 10 を に代入
•客が来てから次の客が来るまでの時間は， λ =
1/20 の指数分布
•t = 10 を1- e に代入
(λt) e
k!
k-λt
k=0
-λt
57
•Ａさんの電話の話し時間は，平均５分）の指
数分布に従うものと仮定する．
•Ａさんに電話をかけたらたまたま話し中であった．
では，３分後に電話をかけたら再び話し中である
確率はいくらか
•話し時間は，λ= 1/5 の指数分布
•t = 3 を1- e に代入
話し時間がランダム
-λt
練習３
58
