---
title: スケジューリング、先頭ブロッキング、公平性
url: https://doc.liz6.com/ja/theory/03-queueing-theory/07-scheduling-and-fairness
locale: ja
area: theory
tags:
- 待ち行列理論
- 基礎理論
date: 2026-09-10
modified: 2026-09-10
description: 待ち時間は流量や仕事の長さだけでなく、次に誰を処理するかでも変わります。平均応答、裾、公平性、締切、完了仕事量の取引を扱うため、全体平均一つでは評価できません。
---
# スケジューリング、先頭ブロッキング、公平性
待ち時間は流量や仕事の長さだけでなく、次に誰を処理するかでも変わります。平均応答、裾、公平性、締切、完了仕事量の取引を扱うため、全体平均一つでは評価できません。
## 有限バッチで先頭ブロッキングを見る
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に増えます。
**スケジューリング、先頭ブロッキング、公平性 · 実験**
5ジョブはすべて0 s到着、FIFOの同刻順は番号順。ジョブ1以外は1 s。SJFは処理時間既知、非プリエンプティブ、切替費用ゼロです。有限バッチは完了し、オンラインの飢餓は再現しません。
順序を変えて各ジョブの待機帯と処理帯を見てから、長い仕事をさらに延ばします。全員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になれば、処理能力も倍以上ですか。
考え方
いいえ。同じ5ジョブをどちらも12 sで完了します。完了分布と占有面積を変えただけです。短窓の完了率は違っても、全バッチのスループットは同じです。
考え方
選ばれない仕事は完了分布に入りません。群別の待機数、最古年齢、未完了数、実際の処理配分も必要です。成功完了者だけで公平性を判断しません。