CPUスケジューリング｜コンピュータ基礎

← コンピュータ基礎一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：プロセスとスレッド　|　関連：プロセス間通信（IPC）・性能の評価とアムダールの法則

要点（BLUF）

CPUは有限なので、実行可能なプロセスのうち「次に誰を走らせるか」を選ぶのがスケジューラ。指標は平均待ち時間・応答時間・スループット・公平性。
代表方式：FCFS（到着順・単純だが長いジョブが渋滞を作る）、SJF（短い順・平均待ち時間最小だが飢餓と予測の問題）、RR（時間で輪番・公平で応答が良いが切替コスト）、優先度。
唯一の正解はない。何を最適化したいか（バッチのスループットか、対話の応答性か）で選ぶ。

概念 ── スケジューラは「CPUという1席の配り係」

実行可能（ready）なプロセスは複数あるのに、CPUコアは限られます。誰をどれだけ走らせるかを決めるのがスケジューラ。判断の良し悪しは指標で測ります。

待ち時間：readyキューで待たされた合計時間（短いほど良い）
応答時間（ターンアラウンド）：到着から完了までの総時間
スループット：単位時間に終わるジョブ数
公平性：特定プロセスが飢餓（永遠に後回し）にならないか

これらは同時には最適化できない（トレードオフ）。だから方式が複数あります。

仕組み ── 代表的な方式

FCFS（First-Come First-Served）

到着順に最後まで走らせる（非プリエンプティブ）。単純そのもの。だが長いジョブが先頭にいると、後ろの短いジョブが延々と待たされる（コンボイ効果）。

SJF（Shortest Job First）

残り実行時間が短い順に通す。平均待ち時間を最小化することが理論的に示せる。弱点は2つ：実行時間を事前に正確に知るのは難しい（予測に頼る）こと、長いジョブが短いジョブに割り込まれ続けて飢餓になりうること。

ラウンドロビン（RR）

**タイムスライス（quantum）**ごとに強制的に次へ回す（プリエンプティブ）。全員が定期的にCPUをもらえるので公平で、対話的な応答が良い。スライスが短すぎるとプロセスとスレッドの文脈切り替えが頻発してオーバーヘッドが増え、長すぎるとFCFSに近づく。

優先度スケジューリング

各プロセスに優先度を付け高い順に。リアルタイム性が要る処理を優先できる。低優先度の飢餓対策に、待つほど優先度を上げるエイジングを併用する。

flowchart LR
    new["新規/I/O完了"] --> ready["readyキュー（実行可能な行列）"]
    ready -->|"スケジューラが選ぶ"| cpu["CPU（実行中）"]
    cpu -->|"タイムスライス終了 (RR)"| ready
    cpu -->|"I/O要求"| wait["待機（ブロック）"]
    wait -->|"I/O完了 (割り込み)"| ready
    cpu -->|"終了"| done["exit"]

具体例 ── 平均待ち時間を計算で比べる

古典例：P1=24, P2=3, P3=3（すべて時刻0着）を3方式で（[[#対応ラボ]] の 02-03_scheduling.py）。

def metrics(name, finish, jobs):
    waits = [finish[p]-arr-burst for p,(arr,burst) in jobs.items()]
    print(f"{name}: 平均待ち時間 = {sum(waits)/len(jobs):.2f}")
jobs = {"P1": (0,24), "P2": (0,3), "P3": (0,3)}

実行結果（実機）:

  FCFS: 平均待ち時間 = 17.00 / 平均応答時間 = 27.00
   SJF: 平均待ち時間 =  3.00 / 平均応答時間 = 13.00
RR(q=4): 平均待ち時間 =  4.33 / 平均応答時間 = 14.33

長いP1を先に通すFCFSは平均待ち17。短いP2,P3を先に通すSJFは平均待ち3で最小。RRは公平だが切替が入り中間。同じジョブ集合でも、配り方だけで体感速度が大きく変わるのがわかります。

仕組みの直観 ── なぜこの設計か

SJFが平均待ちを最小化する理由：短いジョブを先に片付けると、待たされる「人数×時間」の総和が減る（レジ列で少額の人を先に通すのと同じ）。だが現実は実行時間が未知で、飢餓も生む。
RRがプリエンプティブな理由：対話システムでは「全員がそこそこ早く反応する」ことが、「一部が最速で残りが待たされる」より価値が高い。公平性と応答性を、切替コストと引き換えに買う。
多くの実OSが多段キューを使う理由：1方式では全要件を満たせない。対話プロセスは高優先度＆RR、バックグラウンドは低優先度、と用途別キューを組み合わせ、エイジングで飢餓を防ぐ（Linux CFSなどはこの発展形）。

⚠️ よくある誤解・落とし穴

「SJFが常に最良」→ 平均待ち時間には最良でも、長ジョブの飢餓と実行時間予測の難しさがある。
「タイムスライスは短いほど公平で良い」→ 短すぎると文脈切り替えのオーバーヘッド（プロセスとスレッド）が支配し、実効スループットが落ちる。
「スケジューリングはCPUを速くする」→ CPUの速さ（性能の評価とアムダールの法則）は変えない。待ち時間の配分を変えるだけ。
「優先度を付ければ安心」→ エイジングなしの固定優先度は低優先度プロセスを飢餓にする。

対応ラボ

cs-foundations-study/labs/02-03_scheduling.py（実行して上記の平均待ち時間・応答時間を確認済み）。

確認できること：FCFS/SJF/RRの指標差、SJFの最小性、RRの公平性と切替コスト