スケジューラとアルゴリズム

スケジューラとアルゴリズム

解説

このレッスンで分かること

• スケジューラは「次に走らせるプロセスを選ぶ」コンポーネントで、OS の体感性能を決定づけます
• 古典的には FIFO・ラウンドロビン・優先度・SJF などのアルゴリズムが知られています
• Linux は CFS（Completely Fair Scheduler）、その後継として 2023 年に EEVDF が採用されました

解説

スケジューラとアルゴリズム とは

スケジューラとアルゴリズム。本レッスンでは、スケジューラとアルゴリズム の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

主要スケジューリングアルゴリズム比較

スケジューラの目的

CPU は 1 コアあたり同時に 1 つの命令しか実行できません。一方、システムには数百のプロセスが居て、それぞれ「動かしてほしい」と並んでいます。スケジューラの仕事はこの 行列を裁く ことです。良いスケジューラは下記を高い水準で両立します。

これらは互いに矛盾するため、用途に応じて重み付けが変わります。

代表的なアルゴリズム

• FIFO は実装が簡単だが、長いジョブが詰まると全員待たされる
• SJF は短いジョブから処理し平均待ち時間が最小だが、長いジョブが飢餓状態に
• ラウンドロビン は固定タイムスライスで巡回。対話システム向き
• 優先度ベース は重要度で順位付け。優先度逆転問題に注意
• MLFQ は複数のキューに優先度を付け、I/O 多めのプロセスを優遇
• CFS は「各プロセスが使った仮想時間」が一番少ない者を次に走らせる公平共有方式
• EEVDF は CFS の進化版で、遅延敏感なタスクの応答性が改善

Linux CFS の仕組み

CFS は赤黒木にプロセスを並べ、キーは vruntime（仮想実行時間）です。プロセスが CPU を使うと vruntime が増え、最小のものが次に選ばれます。nice 値（-20 ～ +19）で進む速さを調整し、優先度の高いプロセスは vruntime がゆっくり進みます。

chrt を使うとリアルタイムスケジューリングクラス（SCHED_FIFO / SCHED_RR）に切替えられます。

I/O バウンドと CPU バウンド

スケジューラは「最近 CPU を使った時間」を見ることで、I/O 待ちが多いプロセスを 対話的 と判断し優先します。これは「ユーザーがキーを打ったらすぐ応答する」体感を作るための工夫です。動画エンコードのように CPU を貪るバッチ処理は逆に優先度が落ちます。

トレードオフ

• 公平性を強くすると、ゲーム・音楽プレイヤなど 遅延敏感なタスク が割を食うことがあります。これを補うのが SCHED_DEADLINE 等のリアルタイムクラスです
• タイムスライスを短くすると応答性は上がりますが、スイッチコストでスループットが落ちます。Linux のデフォルトは数 ms ですが、サーバー用途では延ばす設定もよく見られます

よくある誤解

• 「CPU 100% = 悪い」は誤解で、ジョブが CPU を使い切るのは効率的な状態でもあります。本当の悪は 待たされている時間 が長いことです
• 「nice -n -20 にすれば最速」も誤解で、優先度を上げすぎると逆に他のプロセス（特に OS の管理タスク）を干上がらせて不安定になります

やってみよう

top を起動し H を押してスレッド単位表示にしてみてください。PR（優先度）と NI（nice 値）の列を観察すると、リアルタイム優先度（rt 表示）のプロセスが裏で動いていることが分かります。

まとめ

このレッスンの要点は、スケジューリング 4 指標 / 古典アルゴリズム / CFS と EEVDF の 3 点です。実務でこれらを切り分けて説明できるようになると、設計レビューや障害対応の精度が一段上がります。

理解度チェック

Q. Linux の Completely Fair Scheduler (CFS) が「次に走らせるプロセス」を選ぶ基準は？

1. 到着順 (FIFO)
2. 予測実行時間が最短のもの (SJF)
3. vruntime (仮想実行時間) が最小のもの
4. メモリ使用量が最小のもの

答えを見る

正解は 3。CFS は赤黒木に並べたプロセスから、累積で CPU を最も使っていない (= vruntime 最小) ものを次に選ぶ公平共有方式です。

出典 (References)

• Linux Kernel — CFS Design
• Linux Kernel — EEVDF Scheduler (since 6.6)
• Operating Systems: Three Easy Pieces — Scheduling

最終更新: 2026-05-28

関連レッスン

• プロセスとは
• スレッドとプロセスの違い
• コンテキストスイッチ
• プロセス間通信（IPC）

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は プロセス間通信（IPC） で、プロセス同士がどうやってデータをやり取りするかを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

1. スケジューラ の要点を自分の言葉で説明できる
2. このレッスンの最小コード (または操作手順) を見ずに書ける
3. 練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. スケジューラ とは何か、1 文で説明してください。

関連レッスン

• コンテキストスイッチ
• スレッドとプロセスの違い
• プロセスとは