システム境界と待ち行列の時間線

平均処理時間が10 msでも、要求が10 ms以内に返るとは限りません。待ち行列理論は資源を待つ時間と占有する時間を分け、到着、処理、順序、容量が待ち時間をどう変えるかを調べます。

まず対象の境界を決める

サービス入口、接続プール、ワーカープール、データベースには、それぞれ別の待ち行列があり得ます。いつ入っていつ出るのか、処理中の要求も数えるのかを定義します。下図の対象は待機区と処理区で、受付拒否はその外側で起きます。

要求 $i$ の到着を $a_i$、処理開始を $b_i$、退出を $d_i$ とします。本章では処理を中断せず、完了だけが退出理由です。

$$W_{q,i}=b_i-a_i,S_i=d_i-b_i,T_i=d_i-a_i=W_{q,i}+S_i.$$

$W_q$ は待ち時間、$S$ は処理時間、$T$ は系内時間または応答時間です。系内数は $N(t)=Q(t)+B(t)$ で、$Q$ は待機中、$B$ は処理中を数えます。単一窓口では $B$ は0か1、窓口が $c$ 個なら最大 $c$ です。

処理時間は境界によって変わります。接続の貸出から返却までの占有時間には、遠隔I/O待ちも含まれ得ます。CPU実行時間とは違います。非同期I/Oでスレッドを解放しても、接続、メモリ、下流の割当量は保持される場合があります。

一つの軌跡を計算する

単一窓口、先着順（FIFO / FCFS）、仕事があれば休まない条件では：

$$b_i=\max (a_i,d_{i-1}),d_i=b_i+S_i.$$

初期は空、直前の完了時刻は0とします。到着 $[0,1,2,3]$ s、処理時間 $[4,1,1,1]$ sなら、開始は $[0,4,5,6]$、完了は $[4,5,6,7]$。待ち時間 $[0,3,3,3]$ の平均は2.25 s、系内時間はすべて4 sです。平均処理時間は1.75 sにすぎません。

累積到着、開始、完了を $A(t),G(t),D(t)$ とすると、初期が空で途中の破棄がなければ $N=A-D$、$Q=A-G$、$B=G-D$。曲線間の縦の差は個数、同じ要求に対応する横の距離は時間です。

先頭だけ長くすると誰が影響を受けるか予想します。次に到着間隔を広げ、待機が消えても処理帯の幅は残ることを確認します。同時刻では完了を先に扱い、解放された資源を到着者が利用できます。

軌跡から統計へ

到着率 $\lambda$、単一窓口の平均処理能力 $\mu =1/E[S]$ の単位は要求/sです。$L=E[N]$ と $L_q=E[Q]$ は定常平均個数です。実際の完了率 $X$ は提供流量とは異なり、暇な窓口が常に $\mu$ の速さで完了を出すわけではありません。

単一窓口、損失なし、安定かつ仕事保存的な場合、稼働割合は $\rho =\lambda E[S]$。複数資源を持つシステムのCPU使用率や、並行数をスレッド数で割った値と自動的に一致するものではありません。安定条件と裾の評価には、後の章の確率モデルが必要です。

確認問題

1. 接続プールの境界内に100要求あり、20要求が接続を保持しています。$N,Q,B$ はいくつですか。

2. CPU使用率30%で応答時間が伸びています。待ち行列を原因から除外できますか。

続けて読む

CMUの性能モデル講義もシステムの用語と性能指標から始めます。実際の資源制約は Google SREを参照してください。次章は同種の軌跡からLittleの法則を導きます。