変動、M/G/1とKingman近似

平均処理時間と利用率が同じでも、ときどき現れる長い仕事が多くの後続要求を待たせます。M/G/1は処理時間の二次モーメントの役割を示し、Kingman近似は到着間隔の変動も平均待ち時間へ取り込みます。

長い仕事に出会いやすい理由

稼働中の窓口をランダムな時刻に見ると、長さ $s$ の処理に出会う重みは $s$ に比例します。長い処理ほど多くの時間を占めるからです。その区間の残余処理時間の面積は $s^2/2$。独立同分布の処理では、稼働中という条件付き平均残余時間は：

$$E[R\mid \text{busy}]=\frac{E[S^2]}{2E[S]}.$$

一定処理時間では $E[S]/2$、指数処理では $E[S]$ です。個々の仕事が常に半分終わっているという意味ではなく、時間標本抽出での平均です。

Pollaczek–Khinchineの公式

Poisson到着、独立同分布の処理時間、到着との独立、単一FCFS窓口、無限容量、$\rho =\lambda E[S]<1$ を仮定します。$E[S^2]<\infty$ のとき、待ちは処理中の残余仕事と前に並ぶ要求の全仕事からなります。PASTAと $L_q=\lambda E[W_q]$ により：

$$E[W_q]=\rho \frac{E[S^2]}{2E[S]}+L_{q}E[S]=\frac{\lambda E[S^2]}{2}+\rho E[W_q].$$

整理するとM/G/1内で厳密なPK平均が得られます。

$$E[W_q]=\frac{\lambda E[S^2]}{2(1-\rho )}=\frac{\rho }{1-\rho }\frac{1+C_s^2}{2}E[S].$$

平均処理10 ms、$\rho =0.8$ で $C_s^2=0,1,9$ なら平均待ちは20、40、200 msです。平均の処理仕事量ではなく、長い処理に遭遇する機会と累積待ちが増えています。

定常分布があっても平均が有限とは限らない

通常の独立同分布M/G/1で、有限 $E[S]$ と $\rho <1$ なら定常状態が存在し得ます。しかし $E[S^2]=\infty$ ならFCFSの平均待ちは無限になり得ます。形状パラメータが1と2の間にある、適切に尺度を設定したPareto処理が例です。

有限データの標本分散が有限でも、母集団の二次モーメントが有限とは証明できません。大きな仕事、タイムアウトによる打切り、要求種別、観測窓の長さによる変化を調べます。少数の極端値だけで裾の分布族を断定しません。

一般到着とKingman近似

FCFS GI/GI/1、独立同分布の間隔と処理、二系列の相互独立、有限二次モーメントでは、よく使う近似は：

$$E[W_q]\approx \frac{\rho }{1-\rho }\frac{C_a^2+C_s^2}{2}E[S].$$

重交通解析に基づく平均の近似であり、一般的な厳密上界でもp99公式でもありません。低負荷、強い依存、バッチ到着では誤差が大きくなる場合があります。実際にPoisson到着なら $C_a^2=1$ でPK厳密値へ戻りますが、そのモーメントだけの一致では十分ではありません。

まず $C_a^2=1$ で処理変動を変え、次に到着変動を1から離します。実線は常にPoisson基準で、破線だけが選択した到着変動を使います。同じ対象への二つの厳密解ではありません。

確認問題

1. 一定処理を同じ平均の指数処理に変えると、M/G/1の平均待ちはどうなりますか。

2. 利用率は高くないのに少数の大きな仕事が全体を遅くします。何から確認しますか。

続けて読む

PKは MIT §4.7、近似と上界の区別は Tran-Gia・Hossfeldの講義を参照してください。本教材の例、コード、図は独自に作成しています。