待ち行列シミュレーション

この資料の到達目標

•待ち行列の数理について理解する

–システム内のジョブ総数

–待ち行列の長さ

•待ち行列の定常状態の意味を理解する

–状態遷移

–定常確率

待ち行列で重要な量

「確率」を使って，待ち行列の

振る舞いをとらえる

内容

•基本的な待ち行列（M/M/1/1 待ち行列）による

説明

–待ち行列の長さ

–システム内のジョブ総数

–状態遷移

–定常状態，定常確率

•M/M/1 待ち行列

–M/M/1/1 との違い

•M/M/S

–「M/M/S」の意味

待ち行列とは

スタックとキュー

•スタック

–データの挿入と取り出しの両方を列の一方の

端から行う

•キュー

–一方の端から挿入を，もう一方の端から取り

出しを行う

–取り出されるのは最も古いデータ

–最初に入れたデータが最初に取り出される

–FIFO(first-in-first-out，先入れ先出し)と呼ぶ

データデータデータデータ

値の追加値の取り出し

待ち行列

到着

サーバ

待ち行列

•処理を受けるために順番待ちをする人が

なす列

–銀行の窓口や入場券売り場など

待ち行列の長さ／システム内のジョブ総数

到着

サーバ

待ち行列

待ち行列の長さ

システム内のジョブ総数

遅延時間／待ち時間

待ち時間

ジョブ到着から

サービス開始まで

到着

サーバ

待ち行列

遅延時間

ジョブ到着から

サービス終了まで

遅延時間とシステム内のジョブ総数

の関係

λD ＝N

D: 「遅延時間」の平均

N: 「システム内のジョブ総数」の平均

λDW= NW

DW:「待ち時間」の平均

NW:「待ち行列の長さ」の平均

以下，システム内のジョブ総数，待ち行列の

長さを考える

ケンドール記法 X/Y/Z

到着

サーバ

待ち行列

サーバ数： Z

時間 (t, t+⊿t) に到着

するジョブ数：Xt

ジョブの処理を行う

処理時間：Y

ケンドール記法 X/Y/Z/K

到着

サーバ

待ち行列

サーバ数： Z

時間 (t, t+⊿t) に到着

するジョブ数：Xt

ジョブの処理を行う

処理時間：Y

待ち行列の大きさを

K－１に制限

「待ち行列の大きさ制限」

•待ち行列の大きさに限りがある

–待ち行列の最大長がＫ－１に制限されるとき，

システム内のジョブ総数はＫに制限される

•特にＫ＝０ならば

–すでにサーバが他のジョブを処理中

•到着したジョブは棄却される（待ち行列に入らな

い）

–サーバがジョブを処理していない

•到着したジョブは直ちに処理される

ケンドール記法

X/Y/Z/K

X: 到着過程

Y：処理時間分布

Z: サーバ数

K：待ち行列の大きさ制限

（待ち行列の最大長：K－１）

X/Y/Z

待ち行列の大きさに制限無し

待ち行列解析

•待ち行列の長さはいくらか

•システム内のジョブ総数はいくらか

•ジョブの遅延時間はいくらか

•ジョブの待ち時間はいくらか

手順

•待ち行列の長さ，システム内のジョブ総数の分布

を求めたい

•「システムの状態」と「状態遷移」を考えて，待ち

行列の長さ，システム内のジョブ総数を算出する

–システムの状態：P0, P1, P2, ・・・

（添字は，システム内のジョブ総数）

•定常状態で考える

–システム内のジョブ総数は，初期状態の影響を受ける

–ｔ→∞では，システムの状態は定常確率に漸近する

（初期状態を無視できる）

方針

X: 到着過程

→ポアソン分布のみを考える

Y：処理時間分布

→指数分布のみを考える

Z: サーバ数

→最初は１とする．あとで増やす

K：待ち行列の大きさ制限

→最初は１とする．あとで増やす

平均到着率

•単位時間に到着するジョブの平均値

•待ち行列に加わろうとするジョブのやってく

る頻度

到着率λのポアソン分布

•ジョブの到着がランダム

•「時間 (t, t+⊿t) に到着するジョブ数」に注目

–⊿tに比例して増加

–平均値： λ⊿

ｔ

• λは単位時間あたりの平均ジョブ数

ポアソン分布

•同じ幅をもった時間区間あたりの到着の仕

方は，時刻に依存しない

•共通部分のない時間区間たちのそれぞれ

の到着の仕方は独立である

•同時刻に2人のジョブがやってくることはな

い

•ごく短い時間 ⊿tの間にジョブが1人来る確

率はλ⊿t

平均処理率

•単位時間に処理を受けるジョブの平均値

•処理がどの程度で行われているかの尺度

処理率μの指数分布

•ジョブの完了時刻がランダム

•「あるジョブの処理の完了から次のジョブ

の完了までの時間」に着目

–平均値：１／μ

• μは単位時間あたりの平均ジョブ完了数

–サーバがジョブを処理中の間，⊿

ｔ

内に完了

する処理数： μ⊿

ｔ

指数分布

•進行中の処理が終了する確率は，それま

でに処理に要した時間に依存しない

•ある時刻に開始される処理は，それ以前

に行われた処理や到着に依存しない

•ごく短い時間 ⊿tの間に処理が1つ終了す

る確率は μ⊿t

「分布」の種類

M: ポアソン分布／指数分布

Ek: k相のアーラン分布

D: 一定分布

G: 一般分布

GI: 独立性を有する一般分布

微小時間の意味

•微小時間 ⊿tの間に到着するジョブ：

–たかだか1人

•時間 ⊿tの間に終了する処理：

–たかだか1つ

•時間 ⊿tの間に「ジョブの到着」「処理

の終了」が同時になされることはない

M/M/1/1 待ち行列

到着サーバ

待ち行列

•ジョブの到着：ランダム

•ジョブの完了時刻：ランダム

•サーバの個数：１個

•待ち行列の大きさ：０個（K－１＝０なので）

システム処理能力ρ

ρ= λ/μ

• λ⊿

ｔ

：「時間 (t, t+⊿t) に到着するジョブ数」の

平均

• μ⊿

ｔ

：「サーバがジョブを処理中の間，⊿

ｔ

内

に完了する処理数」の平均

待ち行列の大きさに限りがないとすると：

λ ＜μ （つまりρ＜１）である必要がある

（さもないと待ち行列があふれる）

サーバの状態遷移

ジョブを処理

していないジョブを処理中

ジョブが到着した

全てのジョブが処理終了した

ジョブが到着

しない

ジョブが処理

終了しない

M/M/1/1 サーバの状態

•ジョブを処理中： P1

•ジョブを処理していない： P0

M/M/1/1待ち行列の

サーバの状態遷移

•制限：待ち行列の大きさは０か１

待ち行列の

長さが０

（処理していない）

待ち行列の

長さが１

（処理中）

λ⊿t

μ⊿t

１－λ⊿t１－ μ⊿t

M/M/1/1待ち行列の

サーバの状態遷移

P0( t+⊿t) = (1－λ⊿t)P0(t) + μ⊿tP1(t)

P1( t+⊿t) = λ⊿tP0(t) + (1－μ⊿t)P1(t)

定常確率

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 =

λ+μ

定常確率

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)の方程式が求まった

定常確率

lim = －(λ+μ)P0(t)+μ

= －(λ+μ)P0(t)+μ

⊿t

P0( t+⊿t) －P0( t)

⊿t→0

d P0( t)

これは P0( t ) の微分方程式

P0( t) = λ+μ

μ+ ( P0( 0 ) －) e

λ+μ

μ－（λ+μ）t

lim P0( t) =

⊿t→0 λ+μ

定常状態における性質

－λP0+μP1= 0

つまり λ⊿t lim P0(t) = μ⊿t lim P1(t)

t→∞ t→∞

新たなジョブが⊿t

以内に到着する確率

処理中のジョブが⊿t

以内に完了する確率

M/M/1/1 まとめ

•定常状態でのサーバの状態

–lim P0(t) =

–lim P1(t) =

•定常状態でのサーバ内のジョブ総数

–0である確率： lim P0(t)，1である確率：lim P1(t)

t→∞

１

１＋ρ

t→∞ t→∞

（但し ρ= λ/μ）

M/M/1 待ち行列

到着サーバ

待ち行列

•ジョブの到着：ランダム

•ジョブの完了時刻：ランダム

•サーバの個数：１個

•待ち行列の大きさ：制限なし

M/M/1 待ち行列

•処理の窓口は1つ

•処理を受けるための列は1つ

•いったん行列に加わったら，処理を受ける

まで待ち続ける

•ジョブの到着の仕方はポアソン分布に従う

•処理時間の分布は指数分布に従う

時刻t+⊿tにジョブが1個もない確率

•時刻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

続き

•Pn(t) は，時刻に依存しない（定常状態）と

考えて

Pn(t +⊿t) = Pn(t)

•前ページの式に代入すると

P0(t) λ⊿t=P1(t)μ⊿t

•つまり

P0(t) λ=P1(t)μ

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

続き

•Pn(t+⊿t)=P(A)+P(B)+P(C)から

Pn(t)(λ + μ) = Pn-1(t)λ + Pn+1(t)μ

M/M/1 待ち行列

λP0= μP1

(λ+μ)P1= λP0+μP2

(λ+μ)Pi= λPi-1+μPi+1

M/M/1 待ち行列

P1= ρP0

P2= (1+ρ)P1－ρP0

= (1+ρ) ρP0－ρP0

= ρ P0

Pi = ρ P0

一方，ΣPi=1 なので Pi = （1－ρ）ρ

続き

ΣPi = 1

つまり， P0(t)*(1+ρ+ρ+・・・) = 1

• ρ≧1

–処理できるジョブ数より，やってくる方が多い

– 1+ρ+ρ+・・・は発散する

• ρ<1

– 1+ρ+ρ+・・・=1/（1-ρ）（発散しない）

–P0(t)=1-ρ

平均ジョブ数，平均待ちジョブ数

Ｎ= ΣnPn

= Σn（1－ρ）ρ

Ｎｗ = Σ（n－1)Pn

= ΣnPn－（１－P0）

= N －（１－P0）

１－ρ

平均ジョブ数

•平均ジョブ数をLとおくと

•Lを計算すると

L = ΣnPn

n=0

∞

L= 1-ρ

•処理を受けているジョブを含まない待ち行

列内の平均ジョブ数: 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

平均待ち時間

•ジョブが並びはじめて処理を受け始めるま

での時間の平均： Wq

Lq=λWq

•このことから

Wq= = =

λ λ(1-ρ) μ(1-ρ)

Lqρ ρ2

M/M/S 待ち行列

到着

サーバ

待ち行列

•ジョブの到着：ランダム

•ジョブの完了時刻：ランダム

•サーバの個数： S個

•待ち行列の大きさ：制限なし

M/M/S 待ち行列

N = （∑ + ∑ ）P0

D = Ｎ

(Sρ)

(n-1)!

n=1

S-1 S-1

n=1 S

n(Sρ) n

n-S

課題

•待ち行列プログラムを作成し，実行せよ

– λとμをいろいろ変化させて実行せよ

–また，λ > μのときの振る舞いを確認せよ

サンプルプログラム

#include<stdio.h>

#include <stdlib.h>

#include <time.h>

main()

{FILE *outfile;

int t,out[20], t_max; /*⊿tをtとする*/

long int n;

float ramda,myu,n_sum,r;

if ((outfile=fopen("output.dat", "w")) == NULL) {

printf("can't open file %s\n", out);

exit(0);

}

printf("Input (λ,μ,Ｔ) :");

scanf("%f,%f,%d", &ramda, &myu, &t_max);

srand((unsigned int)time(NULL)); /* ランダム関数を初期化 */

n=0; /*行列の初期ジョブ数は0*/

n_sum=0;

for (t=0;t<=t_max;t++)

{

/* tがt_maxになるまでシュミレーション*/

r = (double)rand() / ((double)RAND_MAX ); /* 0≦r≦1のランダムな実数 */

if ((n!=0) & (myu>=r)) {

n=n-1; /* 処理を受ける*/

}

r = (double)rand() / ((double)RAND_MAX ); /* 0≦r≦1のランダムな実数 */

if (ramda>=r) {

n=n+1; /* ジョブが到着 */

}

fprintf(outfile,"⊿t = %d ジョブ数 = %d\n",t,n); /*ファイルに出力*/

n_sum=n_sum+n;

}

fprintf(outfile,“\n\n平均ジョブ数 = %f\n”,n_sum/t_max);

fclose(outfile);

}