アーランの即時式モデル.

Slides:



Advertisements
Similar presentations
1 例題 ex3b ( 配列 ) 科学科プログラミング. 2 例題 : ex3b  以下の 3 つについて例題を進める ステップ 1 :配列 ステップ 2 :最小と最大 ステップ 3 :文字型の配列.
Advertisements

疫学概論 ポアソン分布 Lesson 9.頻度と分布 §C. ポアソン分布 S.Harano,MD,PhD,MPH.
シミュレーション論Ⅰ 第6回 待ち行列のシミュレーション.
数理情報工学演習第一C プログラミング演習 (第3回 ) 2014/04/21
ISDASインターネット分散観測: ワームの平均寿命はいくらか?
解析的には解が得られない 方程式を数値的に求める。 例:3次方程式
システムプログラミング 第5回 情報工学科 篠埜 功 ヒアドキュメント レポート課題 main関数の引数 usageメッセージ
プログラミング論 I 行列の演算
岩村雅一 知能情報工学演習I 第9回(C言語第3回) 岩村雅一
連立一次方程式 a11x1+a12x2+a13x3+...+a1nxn= b1
システムプログラミング 第11回 シグナル 情報工学科  篠埜 功.
基礎プログラミング (第五回) 担当者: 伊藤誠 (量子多体物理研究室) 内容: 1. 先週のおさらいと続き (実習)
プログラミング実習 1・2 クラス 第 1 週目 担当教員:  渡邊 直樹.
問題 1 フィボナッチ数列 xn は次で定義される。
第2章補足Ⅱ 2項分布と正規分布についての補足
コンピュータープログラミング (C言語)(8) 1.乱数(復習) 2.配列とその利用
アルゴリズムとデータ構造 補足資料6-3 「サンプルプログラムcat3.c」
ネットワーク性能評価.
関数 関数とスタック.
精密工学科プログラミング基礎Ⅱ 第3回資料 今回の授業で習得してほしいこと: 2次元配列の使い方 (前回の1次元配列の復習もします.)
第7回 条件による繰り返し.
C言語講座 第3回 ポインタ、配列.
ニュートン法の解の計算 情報電子工学系学科 電気電子工学コース・情報通信システム工学コース
プログラミング演習 バージョン1 担当教員:綴木 馴.
Cプログラミング演習 第6回 ファイル処理と配列.
第10回関数 Ⅱ (ローカル変数とスコープ).
量的表現 Quantitation.
フーリエ級数展開 ~矩形波について~ 長江 栞 中島 涼 中村 勇樹
岩村雅一 知能情報工学演習I 第9回(後半第3回) 岩村雅一
高度プログラミング演習 (03).
知能情報工学演習I 第12回(後半第6回) 課題の回答
最小自乗法.
第7回 条件による繰り返し.
第10回 FIR回路とIIR回路.
超幾何分布とポアソン分布 超幾何分布 ポアソン分布.
四則演算,変数 入力文,出力文,代入文, ライブラリ関数
プログラミング基礎a 第7回 C言語によるプログラミング入門 ファイル入出力
関数への道.
プログラムの制御構造 配列・繰り返し.
岩村雅一 知能情報工学演習I 第9回(後半第3回) 岩村雅一
第14章 ファイル操作 14.1 ファイルへの書き込み 14.2 ファイルからの読み込み 14.3 ファイルへの追加書き込み
岩村雅一 知能情報工学演習I 第9回(C言語第3回) 岩村雅一
様々な情報源(4章).
疑似乱数, モンテカルロ法によるシミュレーション
ウィルスって どの位感染しているのかな? 菊池研究室  小堀智弘.
メモリとメモリアドレス, ポインタ変数,関数へのポインタ渡し
岩村雅一 知能情報工学演習I 第9回(後半第3回) 岩村雅一
プログラミング序論演習.
プログラミング演習I 2003年4月30日(第3回) 木村巌.
復習 2次元配列 4列 j = 0 j = 1 j = 2 j = 3 i = 0 i = 1 i = 2 3行
連立一次方程式 a11x1+a12x2+a13x3+...+a1nxn= b1
疫学概論 ポアソン分布 Lesson 9.頻度と分布 §C. ポアソン分布 S.Harano,MD,PhD,MPH.
待ち行列シミュレーション.
確率と統計2007(最終回) 平成20年1月17日(木) 東京工科大学 亀田弘之.
精密工学科プログラミング基礎 第7回資料 (11/27実施)
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
ループだよ!難しいよ! 第5章 while(ループ);.
cp-15. 疑似乱数とシミュレーション (C プログラミング演習,Visual Studio 2019 対応)
ヒープソート.
cp-3. 計算 (C プログラミング演習,Visual Studio 2019 対応)
Cプログラミング演習 ニュートン法による方程式の求解.
モジュール分割.
プログラミング基礎a 第7回 C言語によるプログラミング入門 ファイル入出力
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
確率的フィルタリングを用いた アンサンブル学習の統計力学 三好 誠司 岡田 真人 神 戸 高 専 東 大, 理 研
四則演算,変数 入力文,出力文,代入文, ライブラリ関数
計算技術研究会 第5回 C言語勉強会 関数(function)を使う
第5回 配列.
プログラミング演習I 補講用課題
岩村雅一 知能情報工学演習I 第9回(C言語第3回) 岩村雅一
Presentation transcript:

アーランの即時式モデル

到達目標 アーランの即時式モデルを理解する アーランの即時式モデルを使って,サーバがs台あり、待ち行列がないときのジョブ棄却率を求めることができるようになる アーランの即時式モデルについて,自分の言葉で説明できるようになる 待ち行列モデルの種類,待ち行列長,システム内のジョブ数,到着したジョブの振るまい,定常確率

あらすじ 「M/M/S 待ち行列モデル」の定常状態 「アーランの即時式モデル」と「M/M/S 待ち行列モデル」の関係 アーランの即時式モデルを使った,ジョブ棄却率の計算

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

M/M/S 待ち行列モデル 到着過程: ポアソン分布 処理時間分布: 指数分布 サーバ数: S個

M/M/S 待ち行列モデル サーバ 待ち行列 ポアソン到着 サーバ数:S 処理時間は指数分布

M/M/S 待ち行列モデルの解析 状態遷移 定常状態 システムの「処理率」を求める システム内のジョブ数を「状態」と見る 定常状態での、各「状態」の確率を求める システムの「処理率」を求める

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

状態遷移 ジョブが到着: 状態 k から状態 k+1 に遷移 ジョブが完了: 状態 k から状態 kー1 に遷移

遷移確率に関する方程式 微小時間 ⊿t(限りなく0に近い)についての式 「ジョブの到着」と「ジョブの完了」は、「同時」には起きない 微小時間 ⊿t(限りなく0に近い)についての式 「ジョブの到着」と「ジョブの完了」は、「同時」には起きない 「ジョブの完了」の確率は、⊿t と μの式 「ジョブの到着」の確率は、⊿t と λの式

「ジョブの完了」に関する式 k≦S ならば(kは状態番号) kμ⊿t (1ーμ⊿t) ≒ kμ⊿t k>Sならば(kは状態番号) サーバに空きがある kμ⊿t (1ーμ⊿t) ≒ kμ⊿t k>Sならば(kは状態番号) サーバは全て忙しい Sμ⊿t (1ーμ⊿t) ≒ Sμ⊿t k-1 S-1

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

状態遷移 ジョブが到着: 状態 k から状態 k+1 に遷移 λ⊿t ジョブが完了: 状態 k から状態 k-1 に遷移 k≦S ならば:   kμ⊿t k>Sならば: Sμ⊿t

状態遷移図 1-λ λ λ λ λ λ 状態 S+1 状態0 状態 S-1 状態 S 状態1 μ 2μ Sμ Sμ Sμ 1-μ-λ

定常状態方程式 0<n<S では (λ+nμ)Pn = λPnー1 + (n+1)μPn+1 S ≦n では (λ+Sμ)Pn = λPnー1 + SμPn+1 λP0 = μP1

定常確率をP0で表す 0<n<S では Pn = S ≦n では n ( ) λ   P0 μ   n! n ( ) λ   P0 n-S μ   S!S

システム処理能力ρ ρ= λ/μ λ⊿t: 「時間 (t, t +⊿ t) に到着するジョブ数」の平均 μ⊿t: 「サーバがジョブを処理中の間,⊿t 内に完了する処理数」の平均

( ) 待ち合わせが生じる確率 システム内のジョブ数が S 以上 Pqueue = ∑ Pn = ∑ = ∑ P0 ∞ n=S n ∞ ( ) λ   P0 n-S μ   S!S n=S ∞ n (Sρ)  1 n-S n=S S!   S

アーランの即時式モデル

アーランの即時式モデル サーバがs台あり、待ち行列がない(M/M/S/S モデル) ときのジョブ棄却率を求めよう

待ち行列モデルM/M/S/S ポアソン到着 待ち行列なし サーバ数:S 処理時間は指数分布

アーランの即時式モデル 待ち行列モデル:  M/M/S/S 入力回線数: 無限 待ち行列長: L=0 システム内の最大占有サーバ数: K=S

「即時式」の意味 待ち行列なし(待ち行列長が0) システム内の占有サーバ数がSのとき,到着したジョブは棄却される

ジョブのモデル ジョブの到着 ジョブの処理時間 システム処理能力:ρ=λ/μ 平均λのポアソン分布 → ある時刻に客が到着してから時間t内に次の客が到着する確率はポアソン分布に従う: 1-e-λt 微少時間⊿tの間にジョブが到着する確率:λ⊿t ジョブの処理時間 平均1/μの指数分布 微少時間⊿tの間に処理が終わる確率: μ⊿t システム処理能力:ρ=λ/μ

課題 ジョブ到着と,使用されるサーバ数の関係を明らかにする 「最適」なサーバ数の設計などに利用

状態 状態0:  系内のジョブの数が 0 状態1:  系内のジョブの数が 1 状態S:  系内のジョブの数が S (状態はSまで)

状態遷移 ジョブが到着: 1) k<S のとき 状態 k から状態 k+1 に遷移 2) k=S のとき    状態 k から状態 k+1 に遷移 2) k=S のとき 状態Sのまま(新しい到着は棄却される) ジョブの回線の占有終わり: 状態 k から状態 kー1 に遷移

状態遷移 ジョブが到着: 1) k<S のとき 状態 k から状態 k+1 に遷移: λ⊿t ジョブの回線の占有終わり:

状態遷移図 1-λ λ λ λ λ 状態0 状態 S-1 状態 S 状態1 μ 2μ (S-1)μ Sμ μ-Sμ 1-μ-λ

定常状態方程式 (λ+nμ)Pn = λPnー1 + (n+1)μPn+11 λP0 = μP1 λPn-1 = SμPn

棄却率 定常状態で,系内にn個のジョブ(0≦n≦s)がある確率を Pn とすると 棄却率: システム内の占有サーバ数が Sになる確率:Ps

例題1.アーランの即時式モデル アーランの即時式モデルを使って,サーバがs台あり、n 個のジョブがある確率 Pn を求めるプログラムを作成し,実行せよ λとμをいろいろ変化させて実行せよ また,λ > μのときの振る舞いを確認せよ

例題1.アーランの即時式モデル プログラムの説明 ソース:erlung.c 変数:Lambda, Mu, s 返り値:n人が系内にいる確率Pn 実行後パラメータ3つを入力するとoutfile.datというファイルにデータを出力する 入力例:0.05,0.1,3

例題1.アーランの即時式モデル プログラムの使い方 コンパイルして実行後メッセージが出るのでパラメータを入力するとファイルにデータが出力される。 入力データは「,」で区切る 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);

例題2.呼損率(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"); 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);