スケジューラ

カバー範囲: CFS (vruntime/赤黒木) → EEVDF (6.6以降) → スケジューリングクラスアーキテクチャ → ロードバランシング → プリエンプション カーネルバージョン: 2.6 ~ 6.x。CFSからEEVDFへの移行を重点的に解説

概要

スケジューラは、カーネル内で最も頻繁に呼び出されるサブシステムの1つです。schedule() の呼び出しごとに、1つの問いに答えなければなりません。「次に誰を実行すべきか？」 この問いは一見単純ですが、「インタラクティブな応答性の良さ」「高いスループット」「公平性」「省電力」「マルチコアへの拡張性」といった要素の間にバランスを取るのは、非常に複雑です。

Linuxの答えは3つの時代を経てきました：

• 2.4: O(n) スケジューラ — すべてのプロセスを走査し、最高優先度のものを選択
• 2.6 ~ 6.5: CFS (Completely Fair Scheduler) — vruntime に基づく赤黒木
• 6.6+: EEVDF — Earliest Eligible Virtual Deadline First

本稿では、CFS と EEVDF の設計原理に焦点を当て、主要なコードパスを追跡します。

スケジューリングクラスアーキテクチャ

Linuxのスケジューラは単一のアルゴリズムではなく、⁠スタック可能なスケジューリングクラスです：

優先度が高い順：

// kernel/sched/sched.h
struct sched_class {
    const struct sched_class *next;  // リスト

    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*yield_task)(struct rq *rq);
    void (*wakeup_preempt)(struct rq *rq, struct task_struct *p, int flags);

    struct task_struct *(*pick_next_task)(struct rq *rq);
    void (*put_prev_task)(struct rq *rq, struct task_struct *p);

    void (*set_cpus_allowed)(struct task_struct *p, ...);
    void (*update_curr)(struct rq *rq);  // ← vruntime を更新する核心
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);     // fork 初期化
    void (*task_dead)(struct task_struct *p);     // exit クリーンアップ
    void (*switched_from)(struct rq *rq, struct task_struct *p);
    void (*switched_to)(struct rq *rq, struct task_struct *p);
};

スケジューリングクラスのスタック可能な設計は、Linuxスケジューラが持つ最もエレガントなアーキテクチャ判断の1つです。リアルタイムタスクと通常タスクは同じ schedule() エントリポイントを共有し、特別な処理は不要です。いずれかのスケジューリングクラスが NULL を返すと、フレームワークは次のクラスに問いかけます。最終的に idle_sched_class が、常に実行可能なプロセスが存在することを保証します。

主要データ構造

runqueue (struct rq)

// kernel/sched/sched.h
struct rq {
    raw_spinlock_t      __lock;         // runqueue全体を保護
    unsigned int        nr_running;     // 実行可能プロセス数 (idle除く)
    unsigned long       nr_switches;    // スケジューリング回数カウンター

    struct cfs_rq       cfs;            // CFS の実行キュー
    struct rt_rq        rt;             // RT の実行キュー
    struct dl_rq        dl;             // Deadline の実行キュー

    struct task_struct  *curr;          // 現在実行中のプロセス
    struct task_struct  *idle;          // 本CPUの idle task
    struct task_struct  *stop;          // 本CPUの stop task

    int                 cpu;            // CPU ID
    unsigned long       clock;          // rq内部のクロック
    unsigned long       clock_task;     // IRQ/softirq時間を除いた実際の経過時間

    struct sched_domain *sd;            // スケジューリングドメイン (ロードバランシング用)
};

各CPUには独自の struct rq が存在します。ロック粒度は per-rq であり、これはスケジューリングの決定には自CPUのロックのみを取得すればよいことを意味します。これが、スケジューラが多数のCPUを持つシステムで拡張可能であるための鍵です。raw_spinlock_t は、スケジューラティックがいつでも発生しうるため、このロックを取得する際には割り込みを無効化しなければならないことを意味します。

sched_entity — スケジューリングエンティティ

// include/linux/sched.h
struct sched_entity {  // task_struct に内包
    struct load_weight  load;           // 重み (nice値から変換)
    unsigned long       runnable_weight;
    struct rb_node      run_node;       // CFS 赤黒木のノード
    unsigned int        on_rq;          // runqueue にあるかどうか

    u64                 exec_start;     // 現在の実行開始時間
    u64                 sum_exec_runtime;  // 累積物理実行時間
    u64                 vruntime;       // 仮想実行時間 (CFS/EEVDF のソートキー)
    u64                 prev_sum_exec_runtime;

    // EEVDF 追加 (6.6以降)
    u64                 deadline;       // 仮想デッドライン
    u64                 min_vruntime;   // 現在の cfs_rq における最小 vruntime
    u64                 min_deadline;   // 現在の cfs_rq における最早の deadline
    u64                 vlag;           // ラグ値 (lag) — 再起動時に追従するために使用

    struct sched_entity *parent;
    struct cfs_rq       *cfs_rq;        // 所属する cfs_rq (グループスケジューリング用)
    struct cfs_rq       *my_q;          // これがグループseの場合、その子 cfs_rq
};

CFS: vruntime に基づく公平性

核心思想

CFS は時間スライスを割り当てるのではなく、⁠仮想実行時間 (vruntime) によってソートします：

vruntime = 物理実行時間 × (NICE_0_LOAD / プロセスのweight)

プロセスのnice値が低い（優先度が高い）ほど、weight は大きくなります → 同じ物理実行時間で累積される vruntime は少なくなります → 赤黒木のより左側に配置されます → 先に選択されます。

本質的に、CFS が追求するのは vruntime の収束 です。すべてのプロセスの vruntime は収束すべきであり、vruntime が最小のプロセスを優先してスケジューリングすることは、「CPUに対して最も負債を抱えている」プロセスを補償することと同義です。

nice → weight マッピング

// kernel/sched/core.c
const int sched_prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* -15 */ 29154, 23254, 18705, 14949, 11916,
    /* -10 */  9548,  7620,  6100,  4904,  3906,
    /*  -5 */  3121,  2501,  1991,  1586,  1277,
    /*   0 */  1024,   820,   655,   526,   423,
    /*   5 */   335,   272,   215,   172,   137,
    /*  10 */   110,    87,    70,    56,    45,
    /*  15 */    36,    29,    23,    18,    15,
};

重要な性質：nice値を1つ下げるごとに、weightは約25%増加します。これは、nice -20 のプロセスが得るCPU時間が、nice 0 のプロセスの約87倍になることを意味します（単純な線形関係ではありません）。この指数関数的減衰設計は、CFSの元論文に由来しており、隣接するnice値間の公平な差が一定に保たれることを保証します。

主要関数

// kernel/sched/fair.c

// vruntime を更新 (各tick / enqueue / dequeue / put_prev の呼び出し時に実行)
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;

    if (unlikely(!curr))
        return;

    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))  // 防御: クロックが巻き戻らないように
        return;

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    // 核心変換: 物理時間 → 仮想時間
    curr->vruntime += calc_delta_fair(delta_exec, curr);
}

// 次のエンティティを選択: 赤黒木の最左ノード
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) {
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left) return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

calc_delta_fair() は delta * (NICE_0_LOAD / weight) を実装します。オーバーフローを避けるために128ビット固定小数点演算を使用し、精度の問題も処理しています（非常に小さい delta に対して縮小を行わず、vruntime が全く増加しないのを防ぎます）。

vruntime の境界処理

新しいプロセスの vruntime の初期値を0から始めることはできません— そうすると、新しくforkされたプロセスが長時間CPUを独占してしまいます。CFSの対処法は以下の通りです：

// kernel/sched/fair.c: place_entity()
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) {
    u64 vruntime = cfs_rq->min_vruntime;  // 現在の cfs_rq の min から開始

    if (initial && sched_feat(START_DEBIT))
        // fork された新しいプロセス: vruntime に一時ペナルティを追加
        vruntime += sched_vslice(cfs_rq, se);

    // EEVDF (6.6以降): deadline も同時に設定
    se->deadline = vruntime + calc_delta_fair(se->slice, se);
    se->vruntime = vruntime;
}

sched_vslice() が返すペナルティは、そのプロセスが初めて実行できるスライスの長さにほぼ等しいです。これにより、新しいプロセスが既に実行中のプロセスよりも「貧弱」になることがなく、公平性が保たれます。

min_vruntime の追跡

// cfs_rq->min_vruntime は単調増加し、デキューされたすべてのエンティティの最小 vruntime を追跡
// update_min_vruntime() で更新されます:
static void update_min_vruntime(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    // 可能なすべてのソースから最大値を取得:
    //   現在実行中のプロセスの vruntime
    //   赤黒木の最左ノードの vruntime (存在する場合)
    //   cfs_rq->curr->vruntime (存在する場合)
    u64 vruntime = cfs_rq->min_vruntime;
    if (se) vruntime = max(vruntime, se->vruntime);
    if (cfs_rq->curr) vruntime = max(vruntime, cfs_rq->curr->vruntime);
    cfs_rq->min_vruntime = vruntime;
}
// min_vruntime は決して巻き戻らない — これが公平性を保証する重要な不変条件

EEVDF: 6.6 におけるパラダイムシフト

EEVDF が必要な理由

CFS の vruntime ソートは CPU バウンドなシナリオでは公平ですが、⁠レイテンシ敏感なシナリオでは欠点があります：

• プロセスが長時間スリープしていた場合 → vruntime が他者よりも極端に低くなる → 再起動後に長時間CPUを占有する（レイテンシの急増）
• CFS には「いつ完了すべきか」という概念がなく、「誰が最も実行すべきか」のみが存在する
• 応答レイテンシが予測不可能 — スリープ後のプロセスがCPU上で実行されるまで長時間待つ必要がある場合がある（vruntime が低くても、即時応答が保証されない）

EEVDF は deadline を導入することでこの問題を解決します。各エンティティはキューに入れられる際に、eligible time（実行資格を得る時刻）と deadline（完了期待時刻）を計算します。スケジューラは deadline でソートしますが、eligible なプロセスの中から選択します。

EEVDF 核心アルゴリズム

// kernel/sched/fair.c (6.6以降)

// リクエスト時間 (request): スライスを重みでスケール
static u64 calc_se_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    // se->slice = sysctl_sched_base_slice × (se->load.weight / cfs_rq->load.weight)
    // 重みが大きいプロセスほど slice が大きくなる → deadline が遠くなる → 頻繁に中断されない
    return calc_delta_fair(sysctl_sched_base_slice, se);
}

// キュー投入: deadline を計算
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) {
    u64 vruntime = se->vruntime;
    
    // 1. eligible time: lag 補償
    //    vlag = 平均 vruntime - 自身の vruntime
    //    vlag > 0 (自身が平均より遅れている) → 優先して eligible に
    //    vlag < 0 (自身が平均より進んでいる) → eligible を遅らせる
    se->vlag = avg_vruntime(cfs_rq) - se->vruntime;
    
    // 2. deadline = vruntime + slice
    se->slice = calc_se_slice(cfs_rq, se);
    se->deadline = se->vruntime + se->slice;
}

// pick_next: eligible なエンティティの中から deadline が最早のものを選択
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = __pick_first_entity(cfs_rq);  // vruntime が最小
    struct sched_entity *best = NULL;

    // 赤黒木を線形走査 (vruntime 順にソート済み)、eligible なエンティティの中で deadline が最小のものを見つけるまで
    while (se) {
        // eligible: vlag > 0 → 自身の vruntime < 平均 → CPU時間を取得する資格あり
        if (entity_eligible(cfs_rq, se)) {
            if (!best || se->deadline < best->deadline)
                best = se;
            // deadline が最小だが vruntime がより小さいものがまだ後にある可能性がある → 継続してスキャン
            if (best && best->deadline < se->vruntime)
                break;  // 後続のエンティティは vruntime が大きいため、best よりも良い deadline にはなり得ない
        }
        se = __pick_next_entity(se);  // 赤黒木の中序後継
    }

    return best ?: __pick_first_entity(cfs_rq);  // eligible なエンティティがいない場合 → 最左を選択
}

主な違い：

slice と deadline の動的調整

// sysctl_sched_base_slice: ベーススライス (EEVDF のデフォルトは 3ms)
// 各プロセスの実際の slice = base × (weight / cfs_rq_weight)
// 重みが大きいプロセスはより長い slice を得る → コンテキストスイッチが少なくなる

// プロセスが slice が尽きる前に CPU を手放した場合 (例: IO でブロック):
//   → vruntime の増加が停止 → vlag が大きくなる → 再起動時に eligible になりやすい
//   → インタラクティブな「使ったら待つ」パターンが補償される

lag 補償メカニズム

// lag: これが EEVDF と CFS の最大の実装上の違い
// 定義: lag = avg_vruntime - se->vruntime
//   lag > 0: プロセスが平均より遅れている → 優先すべき
//   lag < 0: プロセスが平均より進んでいる → 待つべき

// 再起動時:
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se) {
    // EEVDF: deadline 比較
    if (se->deadline < curr->deadline)
        return 1;  // 新しく再起動されたプロセスの deadline が更早 → プリエンプト

    // vlag の境界も考慮
    // 新しいプロセスの lag が現在のプロセスの lag よりも大幅に大きい場合 → プリエンプトする
    // (特定のプロセスが飢えるのを防ぐ)
    return 0;
}

プリエンプション

再起動プリエンプション (wakeup preemption)

// kernel/sched/fair.c: check_preempt_wakeup()
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) {
    struct sched_entity *se = &p->se;
    struct sched_entity *curr = &rq->curr->se;

    // CFS 旧論理: 再起動されたプロセスが現在実行中のプロセスよりも「非常に貧しい」場合にのみプリエンプト
    //   wakeup_preempt_entity(curr, se) → calc_delta_fair(gran, se)
    //   再起動された vruntime が少なくとも granularity 分だけ遅れていることを要求

    // EEVDF 新論理 (6.6以降):
    //   どちらの deadline が更早か → プリエンプト
    if (se->deadline < curr->deadline)
        resched_curr(rq);
}

tick プリエンプション

// kernel/sched/fair.c: entity_tick()
// 各スケジューラ tick (CONFIG_HZ、通常は 250/500/1000) でトリガー

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) {
    unsigned long ideal_runtime = sched_slice(cfs_rq, curr);
    unsigned long delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;

    // 1. 現在実行中のプロセスが割り当てられたスライスを消費した場合 → NEED_RESCHED を設定
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        return;
    }

    // 2. EEVDF: 赤黒木内に現在実行中のプロセスよりも deadline が早い eligible エンティティがある場合
    if (pick_eevdf(cfs_rq) != curr)
        resched_curr(rq_of(cfs_rq));
}

NEED_RESCHED と遅延スケジューリング

// resched_curr() は TIF_NEED_RESCHED フラグを設定するのみ
// ここで schedule() を実行するわけではない — 我々は割り込みコンテキストにいる！
// 実際のコンテキストスイッチは、ユーザーモード復帰前の exit_to_user_mode_loop() で行われる:
//
// exit_to_user_mode_loop() {
//     if (ti_work & _TIF_NEED_RESCHED)
//         schedule();
// }
//
// または、プリエンプションカーネル (CONFIG_PREEMPT=y) の preempt_schedule_irq() 内

ロードバランシング

スケジューリングドメインの階層

// 現代の 2-ソケット AMD EPYC の典型的な階層:
// SMT (ハイパースレッディング、L1共有) < MC (マルチコア、L3共有) < DIE (同一ソケット) < NUMA (ソケット間)
// 各階層には独自の sched_domain があり、ネストされた CPU マスクを構成する

// kernel/sched/topology.c: 起動時にアーキテクチャコードによって初期化
// x86: arch/x86/kernel/smpboot.c がスケジューリングドメイントポロジを構築
// ARM: drivers/base/arch_topology.c が DT/ACPI から取得

バランシングのトリガー

バランシングには4つのタイプがあります：

// 1. idle balance: CPU が idle になる直前 → schedule() 内で newidle_balance() を呼び出し
//    → 忙しいCPUから積極的にタスクを引き取る (起動が早く、idle 遅延を回避)

// 2. periodic balance: scheduler_tick() → trigger_load_balance()
//    → SCHED_SOFTIRQ → run_rebalance_domains()
//    → softirq によって非同期的に実行、周波数 = 1 / (4 * sched_domain->interval)

// 3. fork/exec balance: wake_up_new_task() → select_task_rq_fair()
//    → find_idlest_cpu() → スケジューリングドメイン内で最も空いているCPUを探す

// 4. wake balance: try_to_wake_up() → select_task_rq_fair()
//    → find_idlest_cpu() または wake_affine() (優先して再起動するCPU)

load_balance 実装

// kernel/sched/fair.c: load_balance()
static int load_balance(int this_cpu, struct rq *this_rq, struct sched_domain *sd,
                         enum cpu_idle_type idle) {
    // 1. should_we_balance() — グループ内の最初の idle CPU のみでバランシングを実行 (競合を減らすため)
    // 2. find_busiest_group() — sd の sched_group リスト内で最も忙しいものを探す
    // 3. find_busiest_queue() — 最も忙しいグループ内で最も忙しいCPUの runqueue を探す
    // 4. detach_tasks() — busy な rq から最大 32 個のプロセスをデタッチ (sysctl_sched_nr_migrate)
    //    デタッチされるのは、マイグレーションが許可されているもののみ (cpus_allowed、cgroup でピン留めされていない等)
    // 5. attach_tasks() — this_rq にアタッチし、activate_task() → enqueue_task_fair() を個別に実行
}

グループスケジューリング (CGroup CPU コントローラ)

// 有効化: CONFIG_CGROUP_SCHED
// インターフェース: /sys/fs/cgroup/cpu/<group>/

// cpu.shares   — 重み割り当て (デフォルト 1024)
//   各グループは shares の比率でCPUを分配。A=2048, B=1024 → A:B = 2:1

// cpu.cfs_quota_us   — 周期内の最大CPU時間
// cpu.cfs_period_us  — 周期の長さ (デフォルト 100ms)
//   quota=50000, period=100000 → CPUの最大50%まで使用可能

各 cgroup は task_group に対応し、親 cfs_rq に埋め込まれた sched_entity を含みます。この se は通常のプロセスとして「偽装」され、親グループのスケジューリングに参加します。CPU時間を取得した後、自身の cfs_rq 内でグループ内のプロセスの重みに基づいて二次分配を行います。

デバッグと観測

# プロセスのスケジューリング統計 (最も重要なファイル)
cat /proc/<pid>/sched
# 内容: se.sum_exec_runtime, se.vruntime, se.statistics.wait_sum,
#       nr_switches, nr_voluntary_switches, nr_involuntary_switches

# システム全体のスケジューラデバッグ情報
cat /proc/sched_debug
# 含む: 各CPUの cfs_rq 統計、nr_running、min_vruntime、赤黒木のサイズ

# ftrace: スケジューリングイベントのキャプチャ
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_wakeup/enable
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_migrate_task/enable
cat /sys/kernel/debug/tracing/trace_pipe | head -50

# bpftrace: プロセスごとのスケジューリング遅延の統計
bpftrace -e 'kprobe:finish_task_switch { 
    @[comm] = hist(nsecs - @start[tid]); 
} 
kprobe:__schedule /args->prev/ { 
    @start[args->prev->pid] = nsecs; 
}'

# EEVDF が有効かどうかの確認
grep CONFIG_SCHED_EEVDF /boot/config-$(uname -r)

# カーネルコマンドライン: デバッグ用スイッチ
# sched_verbose — dmesg により多くの情報を出力
# skew_tick=1   — 各CPUのtickをずらしてロック競合を減らす

参考文献と補足

• カーネルドキュメント⁠: Documentation/scheduler/ ディレクトリ、特に sched-design-CFS.rst と sched-eevdf.rst
• LWN:
  • "EEVDF scheduler design" シリーズ (2023, lwn.net/Articles/925371/)
  • "The EEVDF scheduler" (lwn.net/Articles/940176/)
  • "CFS group scheduling" (lwn.net/Articles/240474/)
  • "The multi-queue block and CPU schedulers" (lwn.net/Articles/552451/)
• ソースファイル⁠:
  • kernel/sched/fair.c — CFS/EEVDF (約8000行、スケジューラの本体)
  • kernel/sched/core.c — schedule(), try_to_wake_up() などの共通インターフェース
  • kernel/sched/sched.h — struct rq, struct cfs_rq, sched_class の定義
  • kernel/sched/topology.c — スケジューリングドメインの構築
  • kernel/sched/debug.c — /proc/sched_debug の実装
• 古典論文⁠:
  • "EEVDF: Earliest Eligible Virtual Deadline First" (Stoica & Abdel-Wahab, 1995)
  • "CFS: Completely Fair Process Scheduling in Linux" (MolNar, 2007 LWN)

キーワード: CFS, EEVDF, vruntime, sched_entity, cfs_rq, wakeup preemption, load_balance, sched_domain, cgroup scheduling, vlag