スケジューラのクラス階層：Linux が次に実行するタスクを決める仕組み

Linux スケジューラは、1 秒間に何十億回もある問いに答え続けます。「次に実行すべきタスクはどれか？」一見シンプルなこの問いの裏には、C の struct 関数ポインタによるポリモーフィックなクラス階層、リンカセクションを活用した優先順位付けの工夫、キャッシュラインを意識して設計された per-CPU ランキューがあります。さらに BPF でスケジューリングポリシーを記述するための新しいフレームワークも潜んでいます。本記事ではこれらすべてを詳しく解説します。

記事 2 で見たように、sched_init() は start_kernel() の早い段階で呼ばれ、スケジューラを起動します。本記事では、その初期化によって何が構築されるのか、そしてスケジューリングの仕組みが実行時にどう動作するのかを掘り下げます。

struct task_struct：プロセスディスクリプタ

システム上のすべてのプロセスとスレッドは struct task_struct で表現されます。条件コンパイルされるフィールドだけで 800 行以上に及ぶ、カーネル内でも最大級の構造体の1つです。

include/linux/sched.h#L820-L919

スケジューリングに関係するフィールドは thread_info の直後から始まります。

struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
    struct thread_info      thread_info;
#endif
    unsigned int            __state;
    unsigned int            saved_state;

    randomized_struct_fields_start

    void                    *stack;
    ...
    int                     on_rq;
    int                     prio;
    int                     static_prio;
    int                     normal_prio;
    unsigned int            rt_priority;

    struct sched_entity     se;
    struct sched_rt_entity  rt;
    struct sched_dl_entity  dl;
#ifdef CONFIG_SCHED_CLASS_EXT
    struct sched_ext_entity scx;
#endif
    const struct sched_class *sched_class;
    ...

classDiagram
    class task_struct {
        +unsigned int __state
        +int prio
        +int static_prio
        +int on_rq
        +sched_entity se
        +sched_rt_entity rt
        +sched_dl_entity dl
        +sched_ext_entity scx
        +sched_class* sched_class
    }
    class sched_entity {
        +u64 vruntime
        +u64 deadline
        +struct load_weight load
    }
    class sched_rt_entity {
        +struct list_head run_list
        +unsigned int time_slice
    }
    class sched_dl_entity {
        +u64 dl_deadline
        +u64 dl_period
        +u64 dl_runtime
    }
    task_struct --> sched_entity
    task_struct --> sched_rt_entity
    task_struct --> sched_dl_entity

いくつか注目すべき点があります。まず randomized_struct_fields_start — これは GCC プラグインで、以降のフィールドのレイアウトをランダム化することでエクスプロイトを困難にします。次に、各タスクは複数のスケジューリングクラスに対応するエンティティを同時に持っています（CFS 用の se、リアルタイム用の rt、デッドライン用の dl、sched_ext 用の scx）が、sched_class ポインタが指すクラスだけが実際にアクティブです。最後に、scx フィールドは CONFIG_SCHED_CLASS_EXT が有効な場合のみ存在します。

ヒント： task_struct を読む際は、すべてのフィールドを理解しようとしなくて構いません。スケジューリング、メモリ、シグナル、クレデンシャルなど、調べているサブシステムに関連するフィールドだけに絞って読み進めましょう。

struct sched_class：スケジューリングの vtable

スケジューラの拡張性を支えているのが struct sched_class です。各スケジューリングポリシーが実装する関数ポインタのテーブルであり、カーネル全体に広く使われている「C vtable」パターンの典型例です。

kernel/sched/sched.h#L2497-L2658

struct sched_class {
#ifdef CONFIG_UCLAMP_TASK
    int uclamp_enabled;
#endif
    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
    bool (*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_task)(struct rq *rq, struct rq_flags *rf);
    void (*put_prev_task)(struct rq *rq, struct task_struct *p, struct task_struct *next);
    void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);
    int (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*update_curr)(struct rq *rq);
    ...
};

ソースコード内のコメントには、各操作のロックコンテキスト（rq->lock、task_rq_lock など）が明記されています。これは非常に重要な情報で、誤ったタイミングで呼び出すとデッドロックやデータ破壊につながります。

主要な操作は以下の通りです。

enqueue_task / dequeue_task — ランキューへのタスクの追加・削除
pick_task — そのクラスのキューから次に実行するタスクを選択
wakeup_preempt — ウェイクアップしたタスクが現在のタスクをプリエンプトすべきかを判断
put_prev_task / set_next_task — コンテキストスイッチの後処理を管理
task_tick — タイマーティックのたびに呼ばれ、実行時間の計上を行う

クラス階層とリンカセクションの仕組み

Linux には 6 つのスケジューリングクラスがあり、その優先順位の順序は非常に重要です。リアルタイムタスクは必ず CFS タスクをプリエンプトし、デッドラインタスクはリアルタイムタスクをプリエンプトしなければなりません。この順序を実現しているのが、リンカセクションを活用した巧妙な仕組みです。

kernel/sched/sched.h#L2706-L2709

#define DEFINE_SCHED_CLASS(name) \
const struct sched_class name##_sched_class \
    __aligned(__alignof__(struct sched_class)) \
    __section("__" #name "_sched_class")

各スケジューリングクラスは DEFINE_SCHED_CLASS(name) を使って、自身の sched_class インスタンスを名前付きリンカセクションに配置します。リンカスクリプトはこれらのセクションを次の順序に並べます。

include/asm-generic/vmlinux.lds.h lines 153-162

__sched_class_highest = .;
*(__stop_sched_class)
*(__dl_sched_class)
*(__rt_sched_class)
*(__fair_sched_class)
*(__ext_sched_class)
*(__idle_sched_class)
__sched_class_lowest = .;

2702 行目のコメントには「CAREFUL they are laid out in REVERSE order!!!」と注意書きがあります。__sched_class_highest は stop_sched_class（最高優先度）を指しており、ポインタをインクリメントすることで最高優先度から最低優先度へと順に走査できる仕組みになっています。

flowchart LR
    stop["stop<br/>(highest)"] --> dl["deadline"]
    dl --> rt["real-time"]
    rt --> fair["CFS/fair"]
    fair --> ext["sched_ext"]
    ext --> idle["idle<br/>(lowest)"]

この配置を利用したイテレーションマクロが次のものです。

kernel/sched/sched.h#L2746-L2747

#define for_each_active_class(class)    \
    for_active_class_range(class, __sched_class_highest, __sched_class_lowest)

「active（アクティブ）」というキーワードが重要です。next_active_class() 関数はクラスを動的にスキップします。

kernel/sched/sched.h#L2725-L2735

static inline const struct sched_class *next_active_class(const struct sched_class *class)
{
    class++;
#ifdef CONFIG_SCHED_CLASS_EXT
    if (scx_switched_all() && class == &fair_sched_class)
        class++;
    if (!scx_enabled() && class == &ext_sched_class)
        class++;
#endif
    return class;
}

scx_switched_all() が true の場合、CFS は完全にバイパスされ、sched_ext がすべてのフェアスケジューリングを担います。sched_ext が無効の場合は ext クラスがスキップされます。この動的なクラスのスキップこそが、sched_ext のランタイムホットスワップを可能にしている仕組みです。

__schedule() のコンテキストスイッチ処理

スケジューリングのコア関数が __schedule() です。

kernel/sched/core.c#L6764

static void __sched notrace __schedule(int sched_mode)
{
    struct task_struct *prev, *next;
    bool preempt = sched_mode > SM_NONE;
    ...
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    prev = rq->curr;
    ...

処理の流れは以下の通りです。

flowchart TD
    A["__schedule(sched_mode)"] --> B["Get current CPU's rq"]
    B --> C["Lock rq->__lock"]
    C --> D["Handle prev task state<br/>(sleeping? yielding?)"]
    D --> E["pick_next_task()<br/>iterates active classes"]
    E --> F{"next != prev?"}
    F -->|Yes| G["context_switch(rq, prev, next)"]
    F -->|No| H["Unlock and return"]
    G --> I["Switch stack, registers, address space"]

pick_next_task() は、アクティブなスケジューラクラスを優先度の高い順に走査します。実行可能なタスクを持つ最初のクラスが選ばれます。つまり、デッドラインタスクが 1 つでも実行可能な状態であれば、CFS タスクがどれだけ待っていても常にそちらが優先されます。

最後に呼ばれる context_switch() が実際の CPU コンテキストスイッチを行います。レジスタの保存と復元、メモリマッピングの切り替え（プロセスのアドレス空間が異なる場合）、そして rq->curr ポインタの更新が行われます。

CFS と sched_ext

CFS：Completely Fair Scheduler

CFS は通常タスク（SCHED_OTHER）のデフォルトポリシーです。中心的なアイデアは仮想実行時間（vruntime）です。各タスクは実際の CPU 時間をウェイトで割った値に比例して仮想時間を蓄積し、常に vruntime が最小のタスクが次に選ばれます。これにより、比例的なフェアネスが保たれます。

DEFINE_SCHED_CLASS(fair) で定義される CFS の実装は、カーネル内でも最大級の操作構造体の一つです。

kernel/sched/fair.c#L13955-L14001

DEFINE_SCHED_CLASS(fair) = {
    .enqueue_task       = enqueue_task_fair,
    .dequeue_task       = dequeue_task_fair,
    .yield_task         = yield_task_fair,
    .wakeup_preempt     = wakeup_preempt_fair,
    .pick_task          = pick_task_fair,
    .pick_next_task     = pick_next_task_fair,
    .put_prev_task      = put_prev_task_fair,
    .set_next_task      = set_next_task_fair,
    .select_task_rq     = select_task_rq_fair,
    .task_tick          = task_tick_fair,
    .update_curr        = update_curr_fair,
    ...
};

sched_ext：BPF で拡張可能なスケジューリング

sched_ext は革新的な追加機能です。スケジューリングポリシーを BPF プログラムとして記述し、実行時にロードできます。アクティブな場合は CFS を完全に置き換えることも（クラス走査における scx_switched_all() はそのためです）、CFS と共存させることも可能です。

スケジューリングクラス階層により、sched_ext は CFS と idle の間の特定の優先度レベルに組み込まれます。BPF プログラムが pick_task、enqueue_task などの操作を実装することで、研究者や運用担当者はカーネルを再コンパイルすることなく独自のスケジューリングポリシーを試せます。

ヒント： tools/sched_ext/ ディレクトリには scx_simple や scx_layered などの BPF スケジューラのサンプルがあります。コマンド一つでロードできるスケジューリングポリシーの書き方を学ぶのに最適です。

per-CPU ランキューとキャッシュライン設計

各 CPU はそれぞれ専用の struct rq を持ちます。この構造体のレイアウトはキャッシュ性能を徹底的に意識して設計されています。

kernel/sched/sched.h#L1121-L1170

struct rq {
    /* Hot read-mostly data loaded in update_sg_lb_stats() */
    unsigned int        nr_running;
    ...
    unsigned long       cpu_capacity;
    struct task_struct __rcu *curr;
    struct task_struct  *idle;

    /* Next cacheline: the hot lock */
    u64                 nr_switches    ____cacheline_aligned;
    raw_spinlock_t      __lock;
    ...
#ifdef CONFIG_UCLAMP_TASK
    struct uclamp_rq    uclamp[UCLAMP_CNT] ____cacheline_aligned;
#endif
    struct cfs_rq       cfs;
    struct rt_rq        rt;
    struct dl_rq        dl;
#ifdef CONFIG_SCHED_CLASS_EXT
    struct scx_rq       scx;
#endif

flowchart LR
    subgraph CL1["Cache Line 1 (read-mostly)"]
        nr["nr_running"]
        cap["cpu_capacity"]
        curr["curr / donor"]
        idle["idle"]
    end
    subgraph CL2["Cache Line 2 (lock + hot writes)"]
        sw["nr_switches"]
        lock["__lock (spinlock)"]
        nohz["nohz fields"]
    end
    subgraph CL3["Cache Line 3+"]
        cfs["cfs_rq"]
        rt["rt_rq"]
        dl["dl_rq"]
    end
    CL1 -.-> CL2 -.-> CL3

1123 行目のコメントにはその設計意図が説明されています。nr_running や cpu_capacity といったフィールドは「rq->lock を取得せずに、極めてホットなループ内で一括ロードされる」ため、フォールスシェアリングを避けるべく、ロックとは別の専用キャッシュラインに配置されています。ロック自体は ____cacheline_aligned で区切られた次のキャッシュラインに置かれています。

これは過剰な最適化ではありません。スケジューラはすべての CPU で、すべてのコンテキストスイッチで、すべてのタイマーティックで動作します。ここでキャッシュミスを一つ減らすだけで、システム全体のスループットに目に見える改善をもたらすことがあります。

次回の記事

スケジューラがどのようにして次の実行タスクを決定するかが理解できました。次の記事では逆方向のパス、つまりユーザー空間からカーネルへの道筋をたどります。x86-64 の SYSCALL 命令からアセンブリのエントリポイントを経て、C のディスパッチ処理、そしてカーネル最重要の抽象化パターンが大規模に機能する VFS レイヤーへと至るシステムコールの流れを追います。

スケジューラのクラス階層：Linux が次に実行するタスクを決める仕組み

前提知識

スケジューラのクラス階層：Linux が次に実行するタスクを決める仕組み

struct task_struct：プロセスディスクリプタ

struct sched_class：スケジューリングの vtable

クラス階層とリンカセクションの仕組み

__schedule() のコンテキストスイッチ処理

CFS と sched_ext

CFS：Completely Fair Scheduler

sched_ext：BPF で拡張可能なスケジューリング

per-CPU ランキューとキャッシュライン設計

次回の記事