アーランの即時式モデル

到達目標

•アーランの即時式モデルを理解する

•アーランの即時式モデルを使って，サーバがs台あ

り、待ち行列がないときのジョブ棄却率を求めるこ

とができるようになる

•アーランの即時式モデルについて，自分の言葉で

説明できるようになる

–待ち行列モデルの種類，待ち行列長，システム内のジョ

ブ数，到着したジョブの振るまい，定常確率

あらすじ

1. 「M/M/S 待ち行列モデル」の定常状態

2. 「アーランの即時式モデル」と「M/M/S 待ち行

列モデル」の関係

•システム内の占有サーバ数がSのとき，到着した

ジョブは棄却される

3. アーランの即時式モデルを使った，ジョブ棄却

率の計算

M/M/S 待ち行列モデル

到着過程：ポアソン分布

処理時間分布：指数分布

サーバ数： S個

M/M/S 待ち行列モデル

サーバ数：S

待ち行列

サーバ

ポアソン到着

処理時間は指数分布

M/M/S 待ち行列モデルの解析

•状態遷移

–システム内のジョブ数を「状態」と見る

•定常状態

–定常状態での、各「状態」の確率を求める

•システムの「処理率」を求める

状態

状態０：システム内のジョブ数が０

状態１：システム内のジョブ数が１

状態S: システム内のジョブ数がS

状態遷移

•ジョブが到着：

状態ｋから状態ｋ+１に遷移

•ジョブが完了：

状態ｋから状態ｋｰ１に遷移

遷移確率に関する方程式

•微小時間 ⊿ｔ（限りなく０に近い）についての式

•「ジョブの到着」と「ジョブの完了」は、「同時」には

起きない

•「ジョブの完了」の確率は、⊿ｔと μの式

•「ジョブの到着」の確率は、⊿ｔと λの式

「ジョブの完了」に関する式

•ｋ≦S ならば（ｋは状態番号）

–サーバに空きがある

ｋμ⊿t (1ｰμ⊿t) ≒ｋμ⊿t

•ｋ＞Sならば（ｋは状態番号）

–サーバは全て忙しい

Sμ⊿t (1ｰμ⊿t) ≒Sμ⊿t

k-1

S-1

「ジョブの到着」に関する式

λ⊿t

状態遷移

•ジョブが到着：

状態ｋから状態ｋ+１に遷移

λ⊿t

•ジョブが完了：

状態ｋから状態ｋ－１に遷移

ｋ≦S ならば：ｋμ⊿t

ｋ＞Sならば： Sμ⊿t

状態遷移図

１－λ

状態０状態１

１－μ－λ

２μ

状態

S-1

状態

Sμ

１－Sμ－λ

Sμ

状態

S＋1

１－Sμ－λ

１－（S－１）μ－λ

定常状態方程式

０＜ｎ＜S では

（λ＋ｎμ）Pｎ= λPnｰ1+ （ｎ＋１）μPn+1

S ≦ｎでは

（λ＋Sμ）Pｎ= λPnｰ1+ SμPn+1

λP0= μP1

定常確率をP0で表す

０＜ｎ＜S では

Pn =

S ≦ｎでは

Pn =

λP0

μn!

( )n

λP0

μS!S

( )n

n-S

システム処理能力ρ

ρ= λ/μ

• λ⊿

ｔ

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

数」の平均

• μ⊿

ｔ

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

ｔ

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

待ち合わせが生じる確率

•システム内のジョブ数が S 以上

•Pqueue = ∑ Pn

= ∑

= ∑ P0

n=S

∞

λP0

μS!S

( )n

n-S

n=S

∞

n=S

∞(Sρ) 1

S! S

n-S

アーランの即時式モデル

•サーバがs台あり、待ち行列がない（M/M/S/S モデ

ル）ときのジョブ棄却率を求めよう

待ち行列モデルM/M/S/S

サーバ数：S

待ち行列なし

処理時間は指数分布

ポアソン到着

アーランの即時式モデル

•待ち行列モデル： M/M/S/S

•入力回線数：無限

•待ち行列長： L＝０

•システム内の最大占有サーバ数： K＝S

「即時式」の意味

•待ち行列なし（待ち行列長が０）

•システム内の占有サーバ数がSのとき，到

着したジョブは棄却される

ジョブのモデル

•ジョブの到着

–平均λのポアソン分布

→ある時刻に客が到着してから時間t内に次の客が到着す

る確率はポアソン分布に従う：１－e－λｔ

–微少時間⊿tの間にジョブが到着する確率：λ⊿ｔ

•ジョブの処理時間

–平均１/μの指数分布

–微少時間⊿tの間に処理が終わる確率： μ⊿ｔ

システム処理能力：ρ＝λ/μ

課題

•ジョブ到着と，使用されるサーバ数の関係

を明らかにする

•「最適」なサーバ数の設計などに利用

状態

状態０：系内のジョブの数が０

状態１：系内のジョブの数が１

状態S: 系内のジョブの数が S

（状態はSまで）

状態遷移

•ジョブが到着：

1) ｋ＜S のとき

状態ｋから状態ｋ+１に遷移

2) ｋ=S のとき

状態Sのまま（新しい到着は棄却される）

•ジョブの回線の占有終わり：

状態ｋから状態ｋｰ１に遷移

状態遷移

•ジョブが到着：

1) ｋ＜S のとき

状態ｋから状態ｋ+１に遷移： λ⊿t

•ジョブの回線の占有終わり：

状態ｋから状態ｋｰ１に遷移：ｋμ⊿t

状態遷移図

１－λ

状態０状態１

１－μ－λ

２μ

状態

S-1

状態

Sμ

μ－Sμ

１－（S－１）μ－λ

（S-1)μ

定常状態方程式

（λ＋ｎμ）Pｎ= λPnｰ1+ （ｎ＋１）μPn+11

λP0= μP1

λPn-1 = SμPn

棄却率

•定常状態で，系内にn個のジョブ（0≦n≦s）が

ある確率を Pn とすると

•棄却率：

–システム内の占有サーバ数が Sになる確率：Ps

–上の式で，n=s として計算する

)( 2

tP s











例題１．アーランの即時式モデル

•アーランの即時式モデルを使って，サーバ

がs台あり、n 個のジョブがある確率 Pn を求

めるプログラムを作成し，実行せよ

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

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

例題１．アーランの即時式モデル

プログラムの説明

•ソース：erlung.c

•変数：Lambda, Mu, s

•返り値：n人が系内にいる確率Pn

•実行後パラメータ3つを入力すると

outfile.datというファイルにデータを出力す

る

–入力例：0.05,0.1,3

例題１．アーランの即時式モデル

プログラムの使い方

•コンパイルして実行後メッセージが出るの

でパラメータを入力するとファイルにデータ

が出力される。

–入力データは「,」で区切る

•Gnuplotに対応した形式で出力するので次

のようなコマンドをGnuplotで使うとグラフ化

できる

plot ‘outfile.dat’ with points

#include<stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

main()

{FILE *outfile;

int s, n, n_fact;

double lambda, mu, n_sum,r, rho;

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

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

exit(0);

}

printf("Input (lambda,mu,s) :");

scanf("%lf,%lf,%d", &lambda, &mu, &s);

rho=lambda/mu;

fprintf(outfile,"#n Pn\n");

for (n=1;n<=s;n++) {

int i, s_fact, n_fact; /*_fact=factorial*/

double bunbo, bunshi;

n_fact=1; /*calculate n factorial*/

for(i=1; i<n+1; i++) {

n_fact = n_fact*i;

}

bunbo=1.0; /*Inistial value of BUNBO*/

s_fact = 1;

for(i=0; i<s; i++){

s_fact = s_fact*(i+1); /*s factorial*/

bunbo = bunbo+ (pow(rho,i+1)/s_fact); /*bunbo*/

}

bunshi=pow(rho,n)/n_fact;

fprintf(outfile,"%d %f\n", n, bunshi/bunbo); /*ファイルに出力*/

}

fclose(outfile);

}

例題２．呼損率（Loss Probability）プログラム

•ソース：lossprob.c

•変数：MaxLambda, MinLambda, Mu, s

•返り値：Lambdaを変化させたときの呼損率

•アーランの公式を用いて呼損率を計算。アーラン

の公式でn=sとする。LambdaをMaxからMinまで

100個に分割して計算。

•実行後パラメータ4つ入力するとloss.datというファ

イルにデータを出力する

–入力例：0.01,0.1,0.1,3

#include<stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

#define NUM_DIV 100

main()

{/*

lambda = arraival rate

mu = process rate

rho = utilization rate

FILE *outfile;

int s, n, n_fact,mintime,rate,j;

double lambda,mu,n_sum,r,rho,maxrate,minrate;

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

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

exit(0);

}

printf("Input (Max arrival rate,Min arrival rate, Process rate ,Number of Servers) :");

scanf("%lf,%lf,%lf,%d",&maxrate, &minrate, &mu, &s);

fprintf(outfile,"#lambda Pn\n");

lambda=0.0;

for (j=0;j<NUM_DIV;j++) {

lambda = (maxrate-minrate)*(j+1)/NUM_DIV;

rho = lambda/mu;

int i, s_fact, n_fact; /*_fact=factorial*/

double bunbo,bunshi;

n_fact=1; /*calculate n factorial*/

for(i=1; i<s+1; i++){

n_fact = n_fact*i;

}

bunbo = 1.0; /*Inistial value of BUNBO*/

s_fact = 1;

for(i=0; i<s; i++){

s_fact = s_fact*(i+1); /*s factorial*/

bunbo = bunbo+ (pow(rho,i+1)/s_fact); /*bunbo*/

}

bunshi = pow(rho,s)/n_fact;

fprintf(outfile,"%f %f\n",lambda,bunshi/bunbo);

}

fclose(outfile);

}