スケジューリング、先頭ブロッキング、公平性

待ち時間は流量や仕事の長さだけでなく、次に誰を処理するかでも変わります。平均応答、裾、公平性、締切、完了仕事量の取引を扱うため、全体平均一つでは評価できません。

有限バッチで先頭ブロッキングを見る

5ジョブが0 sに到着し、処理時間は $[8,1,1,1,1]$ s、FIFOの同刻順は番号順とします。単一窓口、割込みなし、切替費用ゼロです。FIFOの完了時刻は $[8,9,10,11,12]$、平均系内時間10 s。最短ジョブ優先（SJF）は $[1,1,1,1,8]$ の順に実行し、完了時刻 $[1,2,3,4,12]$、平均4.4 sとなります。

どちらも総処理量は12 sです。能力が増えたのではなく、短いジョブを早く系外へ出した結果です。長いジョブの待ちは0から4 sに増えます。

順序を変えて各ジョブの待機帯と処理帯を見てから、長い仕事をさらに延ばします。全員0 s到着なので原点から完了までが系内時間です。番号は同じ仕事を指し、行の位置は実行順を表します。

このバッチで最短順が平均を下げる理由

隣接する処理長を $x>y$、それ以前の経過を $t$ とします。$x$ が先なら二つの完了時刻の和は $2t+2x+y$、交換後は $2t+2y+x$ で、$x-y$ 減ります。後続の開始時刻は変わりません。逆順を順に除けば、同時利用可能、長さ既知、単一窓口、非プリエンプティブなバッチの平均完了時間を最小にできます。

オンライン到着、未知の仕事量、解放時刻、切替費用がある問題には、この交換証明をそのまま使えません。条件を変えた最適化が必要です。

SJFと公平性

FCFSは到着順、SJFは準備済みのうち推定最短、SRPTは割込みを許して残り処理量最短を選びます。長さ既知で割込み費用ゼロの理想単一窓口ではSRPTに平均応答の強い最適性があります。実際には長さを推定し、キャッシュ、トランザクション、資源復元の費用を考慮します。

スローダウン $T_i/S_i$ は相対的な不利益を示します。このバッチの最大値はFIFOで12、SJFで4です。有限バッチは最後に全件完了するため、長期公平性の証明にはなりません。短い仕事が流入し続ければ、低優先度の長い仕事は長期間待たされ得ます。

優先度の経時引上げ、テナントの予約持分、重み付き公平列、バッチ隔離は、混雑を誰が負担するかを変えます。種別・テナント別の待ち、最古の未完了年齢、締切違反、サービス配分を記録します。1%未満の集団への害は全体p99にも隠れ得ます。

一つのリストだけの問題ではない

パーティション内の順序保証は、遅い仕事で後続を止める場合があります。共通プールではバッチが全ワーカーを占有できます。分離は干渉を抑える一方、プーリングの利点を失う場合があります。新しい更新を優先する方法は期限切れを許すデータ向きで、必ず実行すべき注文や決済には適さないことがあります。

確認問題

1. 平均応答が10 sから4.4 sになれば、処理能力も倍以上ですか。

2. 完了ジョブのp99だけで飢餓を検出できますか。

続けて読む

CMUのSRPT研究は資源配分としてスケジューリングを扱います。AWSの滞留処理記事は隔離と新旧仕事の分流を説明しますが、期限切れと最終完了要件に依存します。順序と並行消費はコンシューマグループと協調へ進めます。