複数窓口と資源プーリング

5 分で読了 #待ち行列理論 #基礎理論

このページの目次

同じ総流量を二つの窓口で扱うとき、ランダムに別の列へ割り当てるより、一つの待機列を共有すると空き資源を使いやすくなります。ただし10 msの窓口二つが5 msの窓口一つになるわけではありません。

M/M/cの状態依存能力

Poisson到着、各窓口で独立な指数処理率 $μ$ 、共通FCFS列、放棄なし、無限待機容量を仮定します。系内に $n$ 要求あれば総完了率は $min (n, c) μ$ です。

提供負荷 $a = λ / μ$ 、一窓口あたり利用率 $ρ = a / c$ とします。定常条件は $ρ < 1$ 。隣接状態平衡から：

$π_{0} = [n = 0 \sum c - 1 \frac{a ^{n}}{n !} + \frac{a ^{c}}{c ! ( 1 - ρ )}]^{- 1} .$

到着者が待つのは系内数が $c$ 以上の場合で、その確率がErlang Cです。

$C (c, a) = \frac{a ^{c}}{c ! ( 1 - ρ )} π_{0}, E [W_{q}] = \frac{C ( c , a )}{c μ - λ}, E [T] = E [W_{q}] + \frac{1}{μ} .$

待ち時間の裾は $P (W_{q} > t) = C (c, a) e^{- (c μ - λ) t}$ 。系内時間には自身の処理が加わるため、一般に総時間を率 $c μ - λ$ の指数分布と扱うことはできません。

各 $μ = 100$ /sの二窓口、総 $λ = 160$ /sなら、 $a = 1.6, ρ = 0.8$ 、 $π_{0} = 1/9$ 、 $C = 32/45 \approx 0.7111$ 。共通列の平均待ちは17.78 ms、平均系内時間27.78 msです。

各到着が独立に等確率で一窓口を選ぶなら、Poisson分流により80/sのM/M/1が二つできます。それぞれ平均待ち40 ms、系内時間50 ms。同じ機器でも、空き資源の協調で待ちが変わります。

図を準備しています

複数窓口と資源プーリング · 実験

各窓口は指数処理、μ=100/s、総到着率λ=cμρ。共通FCFS列と独立な一様ランダム分配を比べます。cを変えると総到着率も変わります。各比較では利用率と総能力を揃え、ロック競合は含めません。

まず二窓口で $ρ$ を変え、次に窓口数を変えます。実験では $λ = c μ ρ$ に従い、 $c$ と一緒に総流量も変わります。一窓口あたり利用率を固定した規模効果であり、一定の外部流量に対する増設実験ではありません。 $c = 1$ で曲線が一致することを確認できます。

共通列から速やかに配ること、窓口が仕事に対して交換可能なことが必要です。局所性、機器種別、権限によって自由な割当ができない場合があります。ロック競合、通信、キャッシュの影響はM/M/cに含みません。ランダム分流は比較基準で、最短列、最少接続、ワークスティーリングとは異なります。

待機区のない損失モデルはErlang B、混雑時に待たせるのがErlang Cです。放棄があればErlang A、一般処理時間ならM/G/cの近似やシミュレーションを検討します。名前が似ていても公式は交換できません。

考え方

二窓口では各要求の平均処理は10 msで、要求が一つなら一窓口だけが動きます。単一200/sなら平均5 ms。状態1の完了率から既に異なり、応答分布も変わります。

考え方

各ワーカーが独立に本当の制約資源を提供する場合に限ります。主に二つのDB枠を争っているなら、その資源を別にモデル化するかネットワークを作り、相互作用を測ります。

NPTELの複数窓口講義は状態依存完了率からErlang Cを導きます。資料間で記号が違うため、本シリーズは $a = λ / μ$ 、 $ρ = a / c$ に統一します。