🛠️

CodexとSDDでμITRON風RTOSを作る 第3章 3.2: 簡易優先度スケジューラ

に公開
C
RTOS
SDD
Codex
itron
tech

はじめに

この連載では、CodexとSDDを使って、学習・実験目的のμITRON風RTOSを少しずつ作っています。

ここまでの流れは次のとおりです。

  • 第1章：開発準備（構想・環境・公開方針）
  • 第2章：起動と基盤（QEMU起動・シリアル・HAL）
  • 第3章：タスク管理とスケジューラ（タスク管理・スケジューラ）

前回の3.1では、TCBと静的 task_table を作り、タスクを登録して一覧表示できるところまで進みました。

ただし、まだタスクは実行していません。entry 関数はTCBに保持していますが、呼び出していません。スタック情報も保持するだけで、スタックフレームの初期化や切り替えは行っていません。

今回の3.2では、次の段階として「どのタスクを次に実行対象とみなすか」を選ぶ仕組みを追加します。

言い換えると、今回は「簡易スケジューラ編」です。

このプロジェクトは学習・実験目的です。本番利用や安全要求のある用途は想定していません。また、実ITRON/T-Kernel/FreeRTOSなどの既存RTOS実装のソースコードは参照・コピー・流用していません。参考にしているのは、公開されている概念、用語、一般的なRTOS設計原則だけです。

今回のゴール

3.2で扱ったfeature名は、次の2つです。

simple-priority-scheduler
kernel-log-safety

ここでいうfeature名は、cc-sddで仕様、設計、タスク分解、実装、検証を進めるときの作業単位です。

中心になるのは simple-priority-scheduler です。

今回やったことは次のとおりです。

  • task_state_t に TASK_STATE_WAITING を追加する
  • TCBに priority と state を持たせる
  • scheduler_init() を追加する
  • scheduler_select_next() を追加する
  • READY状態のタスクだけを選択対象にする
  • priority は数値が小さいほど高優先度とする
  • 同一 priority の場合はtask tableの登録順で選ぶ
  • kernel側で選択結果をログ出力する
  • kernel側のschedulerログをNULL安全にする

逆に、今回は次のものは扱っていません。

  • task_start() の追加
  • タスク関数の呼び出し
  • READYからRUNNINGへの状態遷移
  • コンテキストスイッチ
  • スタック切り替え
  • タイマ割り込み
  • プリエンプション
  • 動的メモリ

今回作るのは、タスク実行機構ではありません。

あくまで「READYタスクの中から、次に実行対象とみなすタスクを1つ選ぶ」だけです。

なぜ「選択だけ」にするのか

RTOSのスケジューラというと、すぐにタスク切り替えまで想像しがちです。

しかし、実際にタスクを切り替えるには、少なくとも次の要素が必要になります。

  • 現在実行中のタスクを保持する仕組み
  • READY/RUNNINGの状態遷移
  • CPUレジスタの保存と復元
  • スタックポインタの切り替え
  • 初期コンテキストの作成
  • 割り込みやタイマとの接続

これらを一気に入れると、動かないときに原因を切り分けにくくなります。

そこで今回は、スケジューラの責務を「選択」に限定しました。

「どのタスクを選ぶか」が単独で確認できるようになると、次回以降のコンテキストスイッチ実装でも、問題を分けて考えやすくなります。

今回の設計方針

3.2の設計方針は、責務分離を優先しました。

schedulerは選択のみを担当する

scheduler.c は、READYタスクから次候補を選ぶだけです。

タスクを実行しません。TCBを書き換えません。ログも出しません。

scheduler_select_next() の戻り値は const tcb_t * です。これは、schedulerがTCBを読み取るだけで、状態変更しないことを表すためです。

scheduler.cはHAL/arch/serialに依存しない

2.3で導入した依存方向は、今回も維持します。

kernel -> HAL -> arch(x86_64) -> serial -> COM1

schedulerがHAL consoleを直接呼び出すと、選択ロジックとログ出力が混ざってしまいます。

そのため、scheduler選択結果の表示は kernel.c 側で行います。

task_tableはexternしない

task_table は task.c が所有します。

schedulerから直接 extern するのではなく、読み取り用APIを経由します。

int task_get_count(void);
const tcb_t *task_get_by_index(int index);

これにより、task tableの内部構造をscheduler側へ広げすぎないようにしています。

変更したファイル

今回追加・変更した主なファイルは次のとおりです。

kernel/include/scheduler.h
kernel/scheduler.c
kernel/include/task.h
kernel/task.c
kernel/kernel.c
Makefile

それぞれの役割を簡単に整理します。

ファイル 役割
kernel/include/scheduler.h scheduler公開APIを宣言する
kernel/scheduler.c READYタスクから次候補を選ぶ
kernel/include/task.h TCB、task状態、task読み取りAPIを公開する
kernel/task.c task tableの保持、登録、dump、読み取りAPIを担当する
kernel/kernel.c 起動時にschedulerを呼び、選択結果をHAL console経由で表示する
Makefile kernel/scheduler.c をビルド対象に追加する

task_state_tとTCB

今回、task状態は次のように整理しました。

typedef enum {
    TASK_STATE_UNUSED = 0,
    TASK_STATE_DORMANT,
    TASK_STATE_READY,
    TASK_STATE_RUNNING,
    TASK_STATE_WAITING,
} task_state_t;

3.2で主に使うのは TASK_STATE_READY です。

TASK_STATE_RUNNING は、将来「現在CPU上で実行中のタスク」を表すために使う予定です。TASK_STATE_WAITING は、将来sleepや同期オブジェクト待ちを入れるときに使う予定です。

今回の scheduler_select_next() は、TASK_STATE_READY 以外のタスクを選びません。

つまり、TASK_STATE_WAITING は今回追加しますが、まだ遷移先としては使いません。状態の名前だけ先に用意して、実際の待ち状態への遷移は次回以降に回しています。

TCBには、schedulerが見る情報として priority と state を持たせます。

typedef struct {
    int id;
    const char *name;
    task_entry_t entry;
    int priority;
    task_state_t state;
    void *stack_base;
    unsigned long stack_size;
} tcb_t;

entry やstack情報も保持していますが、3.2ではまだ使いません。

ここは3.1と同じです。登録はするが、実行はしない、という段階です。

scheduler API

今回追加したscheduler APIは2つだけです。

void scheduler_init(void);
const tcb_t *scheduler_select_next(void);

scheduler_init() は、将来scheduler内部状態を持つようになったときの初期化入口です。

3.2の時点では、schedulerに内部状態はほとんどありません。それでも初期化APIを用意しておくことで、今後current taskやラウンドロビン用の情報を持たせるときに拡張しやすくしています。

scheduler_select_next() は、READY状態のタスクから次候補を1つ返します。

READYタスクが1つもなければ NULL を返します。

scheduler_select_nextの実装方針

今回の選択アルゴリズムは、単純な線形探索です。

考え方を擬似コードで書くと、次のようになります。

best = NULL

for each task in task_table:
    if task is NULL:
        continue

    if task->state != TASK_STATE_READY:
        continue

    if best == NULL:
        best = task
        continue

    if task->priority < best->priority:
        best = task

return best

実装の中心部分は、次のような形です。

const tcb_t *scheduler_select_next(void)
{
    const tcb_t *best = NULL;
    int count = task_get_count();

    for (int index = 0; index < count; index++) {
        const tcb_t *task = task_get_by_index(index);

        if (task == NULL) {
            continue;
        }

        if (task->state != TASK_STATE_READY) {
            continue;
        }

        if (best == NULL || task->priority < best->priority) {
            best = task;
        }
    }

    return best;
}

ポイントは次の5つです。

  • READY以外のタスクは無視する
  • best == NULL なら最初のREADYタスクを候補にする
  • より小さい priority のタスクを見つけたら更新する
  • 同一 priority では更新しない
  • READYタスクがなければ NULL を返す

同一priorityで更新しないため、先に見つかったタスクがそのまま残ります。

今回のtask tableは、登録時に先頭から空きスロットを探します。そのため、同一priorityでは登録順に近い順序で選ばれます。

最大タスク数は256なので、現時点では線形探索で十分です。

将来、タスク数や性能を意識する段階になったら、READY queueやpriority bitmapのような構造を検討できます。

kernel側のログ出力

scheduler自身はログを出しません。

選択結果の表示は kernel.c 側で行います。

今回のログ補助関数では、NULL安全性も少し改善しました。

const char *safe_label = (label != NULL) ? label : "(no-label)";
const char *safe_name = (task->name != NULL) ? task->name : "(null)";
const char *state_name = kernel_task_state_to_string(task->state);
const char *safe_state = (state_name != NULL) ? state_name : "UNKNOWN";

これにより、ログ表示の安全性を上げつつ、schedulerの責務は「選択のみ」に保てます。

task == NULL の場合は、次のように表示します。

selected: none

READYタスクがないことはエラーではありません。登録前にschedulerを呼べば、自然に起こる状態です。

SDDで進めた流れ

今回も、3.1と同じくChatGPTと相談しながら、cc-sddに渡す指示内容を検討しました。

ここで使っているcc-sddは、仕様、設計、タスク分解、実装、検証を段階化して進めるための流れです。

最初に意識したのは、「スケジューラ」という言葉の範囲を広げすぎないことです。スケジューラと言うと、タスク選択、状態遷移、コンテキストスイッチ、タイマ割り込みまでまとめて作りたくなります。

しかし3.2では、実行制御には踏み込まず、READYタスクから次候補を選ぶところだけに絞りました。

cc-sddに渡す前に、次の制約を明確にしました。

  • 今回は簡易優先度スケジューラだけを扱う
  • schedulerはタスクを実行しない
  • schedulerはTCBの状態を書き換えない
  • READY状態のタスクだけを選ぶ
  • priority は数値が小さいほど高優先度にする
  • 同一priorityではtask table上で先に見つかったタスクを選ぶ
  • READYタスクがなければ NULL を返す
  • scheduler本体はログ出力に依存しない
  • HAL境界を壊さない
  • kernel側のログ表示はNULL安全にする

実際には、次の順番で進めました。

以下はPowerShellで実行するコマンドではありません。Codex上でcc-sddのSKILLとして呼び出した作業手順です。

$kiro-spec-init simple-priority-scheduler
$kiro-spec-requirements simple-priority-scheduler
$kiro-spec-design simple-priority-scheduler -y
$kiro-spec-tasks simple-priority-scheduler -y
$kiro-impl simple-priority-scheduler
$kiro-validate-impl simple-priority-scheduler

requirements.md では、READYタスクだけを選ぶこと、優先度に従って選ぶこと、同一優先度では登録順で選ぶこと、READYタスクがない場合に NULL を返すことを受け入れ条件にしました。

design.md では、scheduler API、task table読み取りAPI、責務分離、ログ出力の位置づけを整理しました。

tasks.md では、次のように小さく分けました。

  1. 既存のtask管理とHAL境界を確認する
  2. scheduler headerを追加する
  3. scheduler本体を追加する
  4. task table読み取りAPIを追加する
  5. TASK_STATE_WAITING を追加する
  6. scheduler_select_next() を実装する
  7. kernel_main から選択結果をログ出力する
  8. Makefileを更新する
  9. buildとQEMUログを確認する
  10. 最終レビューを行う

実装後、ログ表示のNULL安全性も気になったため、別featureとして kernel-log-safety を追加しました。

このときも、scheduler本体ではなくkernel側のログ補助関数を直す方針にしました。schedulerの責務を「選択」に保つためです。

動作確認

ビルドは次のコマンドで確認しました。

make clean
make

QEMUで確認する場合は、既存の make run を使えます。

make run

直接 -serial stdio で見る場合は、次のように実行します。

qemu-system-x86_64 -kernel build/kernel.elf -serial stdio -display none -no-reboot

出力例は次のようになります。

アドレス値はビルド環境やリンク配置によって変わる可能性があります。

itron-rtos booting...
kernel_main reached
[kernel] task init
[scheduler] before_register selected: none
[task] registered: id=1 name=task_a state=READY prio=5 entry=0x101240 stack_base=0x108000 stack_size=1024
[kernel] task_register task_a returned 1
[task] registered: id=2 name=task_b state=READY prio=1 entry=0x1012b0 stack_base=0x108400 stack_size=1024
[kernel] task_register task_b returned 2
[task] registered: id=3 name=task_c state=READY prio=1 entry=0x1012d0 stack_base=0x108800 stack_size=1024
[kernel] task_register task_c returned 3
[task] dump start
[task] id=1 name=task_a prio=5 state=READY entry=0x101240 stack_base=0x108000 stack_size=1024
[task] id=2 name=task_b prio=1 state=READY entry=0x1012b0 stack_base=0x108400 stack_size=1024
[task] id=3 name=task_c prio=1 state=READY entry=0x1012d0 stack_base=0x108800 stack_size=1024
[task] dump end
[scheduler] after_register selected: id=2 name=task_b prio=1 state=READY

まず、登録前のログは次のとおりです。

[scheduler] before_register selected: none

この時点ではREADYタスクがないため、scheduler_select_next() は NULL を返しています。

次に、3つのタスクを登録しています。

[task] registered: id=1 name=task_a state=READY prio=5 ...
[task] registered: id=2 name=task_b state=READY prio=1 ...
[task] registered: id=3 name=task_c state=READY prio=1 ...

今回のルールでは、数値が小さいほど高優先度です。

そのため、prio=5 の task_a より、prio=1 の task_b と task_c が優先されます。

task_b と task_c は同じpriorityです。この場合は、task table上で先に見つかった task_b が選ばれます。

[scheduler] after_register selected: id=2 name=task_b prio=1 state=READY

また、次のようなentry関数の実行ログは出ていません。

[task_a] executed
[task_b] executed
[task_c] executed

つまり、今回のschedulerは本当に「選択のみ」であり、タスク実行はしていないことが分かります。

検証したこと

make は成功し、build/kernel.elf が生成されました。

QEMUでは -serial stdio 相当で起動し、前節のログのとおり、登録前は selected: none、登録後は task_b が選ばれることを確認しました。

$kiro-validate-impl の結果は GO でした。

確認した観点は次のとおりです。

  • scheduler_init() を呼べる
  • scheduler_select_next() がREADYタスクだけを選ぶ
  • READYタスクがない場合に NULL を返す
  • 数値が小さい priority のタスクを優先する
  • 同一priorityではtask table上で先に見つかったタスクを選ぶ
  • schedulerがTCBの状態を書き換えない
  • schedulerがHAL/arch/serialに依存しない
  • kernel側で選択結果をログ出力できる
  • kernel側のログ表示がNULL安全になっている
  • make が成功する
  • QEMU -serial stdio で期待ログが出る
  • タスク関数が呼び出されない
  • コンテキストスイッチ、タイマ割り込み、プリエンプションに踏み込んでいない

つまずいた点と対処

スケジューラの範囲が広がりやすい

「スケジューラを作る」と言うと、すぐにタスク切り替えまで入れたくなります。

しかし、今回の目的はそこではありません。

今回は、READYタスクの中から次候補を選ぶだけです。

scheduler_select_next -> 次候補を返す
scheduler_select_next -> タスクを実行しない
scheduler_select_next -> 状態を書き換えない

この制約を明確にしたことで、実装範囲を小さく保てました。

同一priorityの扱いを決める必要があった

優先度が異なる場合は、数値が小さいタスクを選べばよいだけです。

しかし、同じpriorityのタスクが複数ある場合にどうするかは、明示的に決める必要があります。

今回は、task table上で先に見つかったタスクを選ぶことにしました。

if (task->priority < best->priority) {
    best = task;
}

同じpriorityでは更新しないため、先に見つかった候補が残ります。

将来はラウンドロビンを入れるかもしれませんが、今回は単純さと観測しやすさを優先しました。

schedulerにログを入れたくなる

選択結果を確認したいので、scheduler.c の中でログを出したくなります。

しかし、それをするとschedulerがHALやserialに依存し始めます。2.3で整理した依存方向も崩れやすくなります。

そこで、schedulerは const tcb_t * を返すだけにしました。

ログ出力は kernel.c 側で行います。

scheduler.c -> 選択だけ
kernel.c -> 選択結果の表示

この分離により、選択ロジックを小さく保てました。

selected noneをエラー扱いしない

登録前に scheduler_select_next() を呼ぶと、READYタスクがないため NULL が返ります。

これは異常ではありません。

[scheduler] before_register selected: none

このログを最初に出しておくことで、READYタスクがない場合の挙動も確認できました。

現時点でできないこと

3.2の時点では、まだ次のことはできません。

  • タスクを実行する
  • task_start() で開始する
  • READYからRUNNINGへ遷移する
  • 現在実行中のタスクを保持する
  • CPU contextを保存・復元する
  • スタックを切り替える
  • タイマ割り込みでタスクを切り替える
  • プリエンプションする
  • WAITING状態へ入れる
  • WAITING状態からREADYへ戻す

これは未完成というより、意図的に分けています。

3.2では、schedulerの選択ルールだけを単独で確認できる状態にしました。

今回のまとめ

今回は、μITRON風RTOSに簡易優先度スケジューラを追加しました。

できるようになったことは次のとおりです。

  • READY状態のタスクだけを選択対象にできる
  • priority に基づいて次候補を選べる
  • 数値が小さいほど高優先度というルールを導入できた
  • 同一priorityではtask table上の先勝ちにできた
  • READYタスクがない場合は NULL を返せる
  • QEMUのシリアルログで選択結果を確認できた
  • 選択されたタスクをまだ実行していないことを確認できた

今回の実装により、タスク管理とscheduler選択ロジックがつながりました。

まだタスクは動きません。しかし、「どのタスクを動かすべきか」を決めるところまでは到達しました。

ソースコード

公開リポジトリは次です。

https://github.com/pekopagu/itron-rtos

3.2に対応するタグ名は次のとおりです。

v3.2-priority-scheduler

次回以降

次回以降は、今回選んだTCBをどう実行へつなげるかを考えます。

具体的には、次のようなテーマになります。

  • current taskをどこで保持するか
  • READYからRUNNINGへの状態遷移をどこで行うか
  • context switchの入口をどう設計するか
  • stack pointerをTCBにどう持たせるか
  • 初期contextをどう作るか
  • task entryへどう到達するか

3.2で「選択」と「実行」を分けたので、次回はその境界を保ったまま、実行制御へ進む準備をしていきます。

Discussion