⚡

CodexとSDDでμITRON風RTOSを作る 第6章 6.3: プリエンプション判断基盤

に公開
C
RTOS
osdev
SDD
itron
tech

はじめに

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

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

  • 第1章：開発準備（構想・環境・公開方針）
  • 第2章：起動と基盤（QEMU起動・シリアル・HAL）
  • 第3章：タスク管理とスケジューラ（タスク管理・スケジューラ・currentタスク）
  • 第4章：タスク実行モデル（entry呼び出し・return観測・cooperative runner）
  • 第5章：コンテキストスイッチ基盤（stack・register保存領域・最小context switch）
  • 第6章：同期・タイマ基盤（セマフォ・タイマ・今回プリエンプション判断）

6.1では、セマフォ基盤を追加しました。

sem_create()
wai_sem()
sig_sem()
sem_dump()

ただし、6.1のセマフォはまだtimeoutやpreemptionと接続していません。wai_sem() によりtaskをWAITINGにすること、sig_sem() により1つのtaskをREADYに戻すことを、boot-time verificationとして観測できる段階です。

6.2では、タイマ基盤を追加しました。

timer_init()
timer_tick()
timer_get_ticks()

ここでも、まだhardware timer interruptはありません。timer_tick() をkernel boot中の検証処理から明示的に呼び出し、system tickが増えることをQEMU serial logで確認する段階でした。

今回の6.3では、その次の段階として「プリエンプション判断基盤」を扱います。

ただし、今回作るものは完全なプリエンプティブRTOSではありません。目的は、タイマを契機にして、現在のtaskより高優先度のREADY taskがあるかを判断できる基盤を作ることです。

このプロジェクトは学習・実験目的です。本番利用や安全要求のある用途は想定していません。また、既存RTOS実装のソースコードは参照・コピー・流用せず、一般的なRTOS設計の概念をもとに独自実装として進めています。

今回のゴール

今回扱うfeature名は次のとおりです。

preemption-foundation

対応するtagは次を想定しています。

v6.3-preemption-foundation

今回の到達点は、次の段階です。

timer tick
  -> preemption decision
  -> higher-priority READY task is detected as switch target

ここでのpreemption decisionは「切り替え判断」、switch targetは「切り替え候補」という意味で使っています。

ここで実際のcontext switchまで実行するわけではありません。

今回のschedulerは、あくまで「選択」と「判断」だけを担当します。current taskの確定はdispatcher側の責務として残します。register save/restoreやstack切り替えはcontext switch側の責務として残します。

確認したいことは、次の2つです。

current taskより高優先度のREADY taskがある
  -> switch targetとして観測する

current taskより高優先度のREADY taskがない
  -> switchしない判断として観測する

この判断ができれば、後の段階で本格的なinterrupt-driven dispatchやcontext switchへ接続するときに、どの層が何を担当するべきかを崩さずに進められます。

今回やること・やらないこと

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

  • schedulerにpreemption判断APIを追加する
  • current taskとREADY候補を比較する
  • currentより高優先度のREADY taskがあればswitch targetとして返す
  • currentがない場合はno switchとして扱う
  • currentがRUNNINGでない場合はinvalid currentとして扱う
  • 同じpriorityのREADY taskはpreemption対象にしない
  • timer tick後にpreemption判断を呼ぶboot-time smokeを追加する
  • QEMU serial logでpreemption判断結果を確認する

逆に、今回やらないことは次のとおりです。

  • hardware timer interruptの本格接続
  • 割り込み復帰時のdispatch
  • 割り込みネスト制御
  • preemption判断結果による実際のcontext switch
  • task-to-taskの継続的な自動切り替え
  • time slice
  • round-robin
  • timeout付きwait
  • sleep queue / delay queue
  • ready queueの本格実装
  • priority inheritance
  • μITRON互換API

つまり、今回の実装は「preemption foundation」です。preemptionという名前は出てきますが、まだtimer interruptで自動的にtaskを奪って切り替える段階ではありません。

なぜ判断だけに分けるのか

RTOSでプリエンプションというと、timer interruptで実行中taskを止め、より高優先度のtaskへ自動的に切り替える動作を想像しがちです。

しかし、それを一気に入れると、多くの責務が同時に絡みます。

hardware timer interrupt
  -> interrupt handler
  -> tick update
  -> scheduler decision
  -> dispatcher current commit
  -> register save/restore
  -> stack switch
  -> interrupt return

さらに、後の段階ではtimeout、wait queue、priority inheritance、time sliceなども関係してきます。

この段階で全部を入れると、QEMU serial logで何かがおかしくなったときに、どこが原因なのか分かりにくくなります。

そこで今回は、timer tickをきっかけに「切り替えるべき候補があるか」を判断できるところだけに絞ります。

6.2 timer foundation
  -> tickを観測できる

6.3 preemption foundation
  -> tick後にpreemption判断を観測できる

future
  -> interrupt-driven dispatchやcontext switchへ接続する

この段階を挟むことで、次に進むときもscheduler、dispatcher、context switch、timerの責務を分けたまま考えられます。

設計方針

今回の設計で一番重視したのは、責務を混ぜないことです。

各moduleの責務は次のように分けています。

module 今回の責務
timer tickを進める。scheduler判断は持たない
scheduler READY taskを選び、currentと比較する
dispatcher current taskの確定を担当する
task context / arch context switch実行、register save/restoreを担当する
kernel smoke timer tick後に各moduleを順に呼び、ログで観測する

今回追加したschedulerの役割は、次の1点です。

現在のcurrent taskより高優先度のREADY taskがあるかを判断する

schedulerは、判断結果を返すだけです。

次のことは行いません。

  • current taskを変更しない
  • task stateをRUNNINGへ変更しない
  • dispatcherを呼ばない
  • context switchを呼ばない
  • timerを直接扱わない
  • HAL consoleへ直接ログを出さない

また、RUNNINGの意味もこれまで通りです。

この段階のRUNNINGは、dispatcherがcurrentとして採用したことを示す論理状態です。CPUがそのtask stack上で継続実行中であることを保証するものではありません。

ここは、5.3のcontext switch smokeと矛盾しないように特に注意しました。5.3では最小context switch経路を作りましたが、それでも完全なtask lifecycleやinterrupt-driven schedulingではありません。今回も同じく、boot-time verificationとして観測できる最小の段階にとどめます。

preemption判断API

今回追加した中心APIは、scheduler側の次の関数です。

scheduler_preempt_decision_t
scheduler_select_preemption_candidate(const tcb_t *current);

このAPIは、副作用を持たない判定関数として扱います。現在のtask状態を読み取り、切り替え候補を返すだけで、TCBやdispatcherの状態は変更しません。

判断結果は、次のような値として表します。

typedef enum {
    SCHEDULER_PREEMPT_NONE = 0,
    SCHEDULER_PREEMPT_NEEDED,
    SCHEDULER_PREEMPT_INVALID_CURRENT
} scheduler_preempt_reason_t;

typedef struct {
    scheduler_preempt_reason_t reason;
    const tcb_t *current;
    const tcb_t *candidate;
} scheduler_preempt_decision_t;

この構造体では、判断理由、比較基準にしたcurrent task、候補になったREADY taskをまとめて返します。

重要なのは、current と candidate が読み取り専用の観測値だという点です。このAPIはTCBを書き換えません。current taskを確定しません。context switchも行いません。

実際の判断条件は、かなり単純です。

if (candidate->priority < current->priority) {
    decision.reason = SCHEDULER_PREEMPT_NEEDED;
}

このRTOSでは、priorityの数値が小さいほど高優先度として扱っています。そのため、candidate->priority < current->priority の場合だけpreemption対象として扱います。

同じpriorityの場合は、今回のpreemption対象にしません。これはtime sliceをまだ実装していないためです。

timer / scheduler / dispatcher の接続

今回の処理の流れは、次のように分けています。

kernel smoke
  -> timer_tick()
  -> dispatcher_get_current()
  -> scheduler_select_preemption_candidate(current)
  -> log decision

timer_tick() はtickを進めるだけです。

timer moduleは、READY taskを選びません。dispatcher currentを確定しません。context switchも呼びません。

preemption判断は、kernel側のboot-time smoke helperから明示的に呼びます。これにより、timer処理とscheduler判断を混ぜないようにしています。

dispatcherは、current taskを持つ境界です。今回のpreemption判断では、dispatcherから現在のcurrentを読み取ります。

ただし、schedulerが高優先度READY taskを見つけても、その場でcurrentにはしません。

scheduler
  -> switch target candidateを返す

dispatcher / context switch
  -> 将来、current確定や切り替え実行を扱う

この分け方により、今回の実装は「判断基盤」として独立します。後で本格的なdispatch経路を作るときも、schedulerにcurrent確定やregister操作を混ぜずに済みます。

実装概要

今回の主な変更ファイルは次のとおりです。

kernel/include/scheduler.h
kernel/scheduler.c
kernel/kernel.c
kernel/include/timer.h
kernel/include/dispatcher.h
kernel/include/task_context.h
docs/logs/qemu-serial.log

kernel/include/scheduler.h では、preemption判断結果を表す型と、判断APIを追加しました。

typedef enum {
    SCHEDULER_PREEMPT_NONE = 0,
    SCHEDULER_PREEMPT_NEEDED,
    SCHEDULER_PREEMPT_INVALID_CURRENT
} scheduler_preempt_reason_t;

scheduler_preempt_decision_t
scheduler_select_preemption_candidate(const tcb_t *current);

kernel/scheduler.c では、現在のcurrent taskとREADY候補を比較する処理を実装しました。

大まかな流れは次のとおりです。

current == NULL
  -> no switch

current is not RUNNING
  -> invalid current

READY candidate does not exist
  -> no switch

candidate priority is higher than current priority
  -> switch target

otherwise
  -> no switch

kernel/kernel.c では、boot-time preemption smokeを追加しました。

検証シナリオは3つあります。

scenario 確認すること
no-current currentがない場合はswitchしない
higher-ready currentより高優先度のREADY taskをswitch targetとして検出する
no-higher-ready 同じpriorityのREADY taskはswitch targetにしない

smoke中では検証のために一時的にdispatcherでcurrentを作ります。しかし、preemptionを実行するわけではありません。後続のsemaphore smokeやcontext smokeの前提を保つため、検証後はtaskをREADYへ戻しています。

QEMUシリアルログで確認すること

今回の実行結果は次にあります。

docs/logs/qemu-serial.log

まず、6.2で作ったtimer foundationのログが出ます。

[timer-smoke] begin
[timer] init: tick=0
[timer] tick: 1
[timer] tick: 2
[timer] tick: 3
[timer-smoke] current tick=3
[timer-smoke] end

その後、task登録とdumpが行われます。

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

今回追加したpreemption smokeは、その後に出ます。

このRTOSでは、priorityの数値が小さいほど高優先度として扱います。そのため、prio=5 の task_a がcurrentで、prio=1 の task_b がREADYなら、task_b が切り替え候補になります。

[preempt-smoke] begin
[timer] tick: 4
[preempt] no-current result=no-switch reason=no-current current=none candidate=none
[dispatcher] committed current: id=1 name=task_a prio=5 state=RUNNING
[timer] tick: 5
[preempt] higher-ready result=switch-target reason=higher-priority-ready current id=1 name=task_a prio=5 state=RUNNING candidate id=2 name=task_b prio=1 state=READY
[preempt-smoke] restore current result=0 task_id=1
[dispatcher] committed current: id=2 name=task_b prio=1 state=RUNNING
[timer] tick: 6
[preempt] no-higher-ready result=no-switch reason=candidate-not-higher current id=2 name=task_b prio=1 state=RUNNING candidate id=3 name=task_c prio=1 state=READY
[preempt-smoke] restore current result=0 task_id=2
[preempt-smoke] end

このログから、3つのことが確認できます。

まず、currentがない場合は切り替えません。

result=no-switch reason=no-current

次に、currentより高優先度のREADY taskがある場合は、switch targetとして観測できます。

result=switch-target reason=higher-priority-ready
current id=1 name=task_a prio=5
candidate id=2 name=task_b prio=1

最後に、READY taskがあっても同じpriorityであれば、今回のpreemption対象にはしません。

result=no-switch reason=candidate-not-higher
current id=2 name=task_b prio=1
candidate id=3 name=task_c prio=1

preemption smokeの後には、6.1のsemaphore smoke、5.3のcontext smoke、既存のcooperative runnerも続けて動いています。

[sem-smoke] begin
...
[context-smoke] begin
...
[cooperative] iteration=1 begin

つまり、今回のpreemption判断基盤は、既存のセマフォ、タイマ、context switch smokeの流れを壊さずに追加できています。

SDDで進めた流れ

今回もSDDで進めました。

対象specは次です。

.kiro/specs/preemption-foundation/

主に参照したファイルは次の3つです。

requirements.md
design.md
tasks.md

requirementsでは、今回の範囲を「timer tickを契機にpreemption判断を行い、現在taskより高優先度のREADY taskがあるかをserial logで観測できること」に限定しました。

特に、out of scopeを明確にしました。

hardware timer interrupt
interrupt return dispatch
automatic context switch
time slice
round-robin
timeout
sleep queue / delay queue
ready queueの本格実装
μITRON互換API

designでは、責務境界を次のように分けました。

TimerModule
  -> tickを進める

SchedulerModule
  -> currentとREADY候補を比較する
  -> preemption decisionを返す

DispatcherModule
  -> current確定を担当する

KernelMain smoke
  -> timer_tick後に判断APIを呼び、ログで観測する

tasksでは、次の順に分けました。

  • preemption判断APIと型の追加
  • scheduler内の比較ロジック
  • boot-time preemption smoke
  • QEMU serial logによる検証

この分け方により、実装中に「判断したらすぐdispatchするべきか」「timer moduleからschedulerを呼ぶべきか」という逸脱を避けやすくなりました。

検証したこと

検証は次で行いました。

make
make run

make では、schedulerのpreemption判断APIを含むkernel buildが成功することを確認しました。

make run では、QEMU serial logで次を確認しました。

  • kernelが起動する
  • 6.2のtimer smokeが動く
  • task登録ログが出る
  • currentがない場合にno switchになる
  • currentより高優先度のREADY taskがswitch targetになる
  • 同じpriorityのREADY taskはswitch targetにならない
  • preemption判断後にtask状態を戻せる
  • 既存のsemaphore smokeが動く
  • 既存のcontext smokeが動く
  • 既存のcooperative runnerが動く

また、次の点も確認しました。

  • preemption判断でcurrentを変更していない
  • preemption判断でdispatcherを呼んでいない
  • preemption判断でcontext switchをしていない
  • timer moduleにscheduler責務を入れていない
  • 同一priorityをtime sliceとして扱っていない

つまずいた点と対処

今回のつまずきは、「preemption」という名前に引っ張られて実際の切り替えまで進めたくなることでした。

ただし、今回作るのはpreemptionの実行ではなく、preemptionが必要かどうかを判断する部分だけです。

プリエンプションを入れると、すぐに次の要素が欲しくなります。

  • timer interrupt handler
  • interrupt return
  • dispatch boundary
  • task-to-task context switch
  • time slice
  • ready queue
  • timeout wakeup

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

6.3では、次の1点だけを観測できれば十分です。

timer tick後に、高優先度READY taskをswitch targetとして判断できる

そのため、schedulerは判断結果を返すだけにしました。dispatcherやcontext switchは呼びません。

もう1つ気をつけたのは、smoke中に作ったRUNNING状態を後続ログへ残さないことです。

preemption smokeでは、検証のために task_a や task_b を一時的にcurrentとしてcommitします。そのままにすると、後続のsemaphore smokeやcontext smokeの読み方が変わってしまいます。

そこで、検証後は対象taskをREADYへ戻し、既存のboot-time verification logを従来どおり読めるようにしました。

この処理は本格的なpreemption実行ではありません。あくまで、観測用のsmoke sequenceを読みやすく保つための整理です。

まとめ

今回の6.3では、プリエンプション判断基盤を実装しました。

できたことは次のとおりです。

  • schedulerにpreemption判断APIを追加しました
  • scheduler_preempt_decision_t を追加しました
  • current taskとREADY候補を比較できるようにしました
  • currentがない場合はno switchとして扱いました
  • currentがRUNNINGでない場合はinvalid currentとして扱いました
  • currentより高優先度のREADY taskをswitch targetとして観測しました
  • 同じpriorityのREADY taskはswitch targetにしないことを確認しました
  • timer tick後にpreemption判断を呼ぶboot-time smokeを追加しました
  • QEMU serial logでpreemption発生・非発生を確認しました
  • 既存のtimer、semaphore、context smokeを維持しました

まだできていないことも整理します。

  • hardware timer interruptの本格接続
  • 割り込み復帰時のdispatch
  • 割り込みネスト制御
  • 実際のtask-to-task context switch
  • time slice
  • round-robin
  • timeout付きwait
  • sleep queue / delay queue
  • ready queueの本格実装
  • priority inheritance
  • μITRON互換API

今回の実装は、あくまでpreemption decision foundationです。完全なプリエンプティブRTOSではありません。

しかし、timer tickを契機にして、schedulerが「高優先度READY taskがあるか」を判断し、その結果をQEMU serial logで観測できるようになりました。

ソースコード

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

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

今回の主な変更は次のファイルです。

kernel/include/scheduler.h
kernel/scheduler.c
kernel/kernel.c
kernel/include/timer.h
kernel/include/dispatcher.h
kernel/include/task_context.h
docs/logs/qemu-serial.log
.kiro/specs/preemption-foundation/requirements.md
.kiro/specs/preemption-foundation/design.md
.kiro/specs/preemption-foundation/tasks.md

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

v6.3-preemption-foundation

次回以降

今回の6.3で、timer tick後にpreemption判断を行う土台ができました。

次回以降は、第7章「割り込み基盤編」へ進みます。

第7章では、いきなりtimer interruptを動かすのではなく、まずCPUが割り込みや例外を受け取ったときにkernel側へ入ってこられる経路を作ります。

予定している流れは次のとおりです。

7.1 IDT/GDTと例外ハンドラの最小基盤
7.2 PICまたはAPICの初期化方針
7.3 timer interrupt入口を作る
7.4 interrupt中のログ制約と観測モデル

現時点の timer_tick() は、kernel boot中の検証処理から明示的に呼んでいます。これをPIT/APIC/HPETなどの実timer interruptから呼ぶには、interrupt entry/exit、interrupt handler、CPU context保存の扱いを整理する必要があります。

次に、preemption判断結果を実際のdispatchへ接続することです。今回のschedulerはswitch targetを返すだけです。将来は、その結果をdispatcher/context switch側で受け取り、current確定と切り替え実行へつなぐ必要があります。

ただし、そのときも今回の責務分離は維持したいです。

scheduler
  -> 選択と判断

dispatcher
  -> current確定

context switch
  -> register save/restoreとstack切り替え

timer
  -> tick管理と契機

また、セマフォやWAITING taskとの接続も今後の課題です。6.1ではWAITING遷移を観測できるようになりましたが、timeoutやwait queueはまだありません。timerと同期機構をつなぐには、timeout管理やwake upの順序も設計する必要があります。

これで、完全なプリエンプティブRTOSへ進む前の、preemption decision foundationができました。

Discussion