執筆者 : 金沢工業大学工学部情報工学科　橘真吾 (インターン生)
監修者：高橋浩和

※ 「ARM64 OSを作ろう」連載記事一覧はこちら
※ 「ARM64 OS」のコードはGitHubの時限待ちとセマフォにて公開しています。

1. はじめに

今回はタスクの時限待ちとセマフォを実装します。タスクの時限待ちの機能は、指定時間だけタスクをスケジューリング対象から外す機能です。また、タスクを協調動作させるための仕組みとして、セマフォによる同期機構を実装します。

今回実装するコードの多くが「RISC-V OSを作ろう (5) ～時限待ち」と「RISC-V OSを作ろう (6) ～セマフォ」と共通です。詳細なロジックについてはそちらも併せて参照してください。

2. 時限待ち

時限待ちとは、その名の通り「タスクを指定時間だけ待機させる」機能です。タスクが明示的に「待ち時間」を要求することにより、コンテキストスイッチ後に自タスクを「時限待ち状態」に遷移させ、その待ち時間分だけ時限待ち状態を維持します。タスクスケジューラは時限待ち状態以外のタスクに実行権を与えます。タイマーハンドラは、指定時間を経過したタスクの時限待ち状態を解除し、再度実行可能状態にします。

上記の時限待ち状態を実現するために、TaskControl構造体内にタスク状態を表すstateメンバを追加します。

タスク状態	説明
READY	実行可能状態（スケジューリング対象）
BLOCKED	待機状態（スケジューリング対象外）

時限待ち状態のタスクには、待機状態(BLOCKED)に加えて、int型のexpireメンバに待ち時間の情報を持たせます。expire回のタイマー割り込みが発生すると、タスクを実行可能状態(READY)に戻します。

この実装により、OSは各タスクに無駄なく計算資源を分配できるようになります。

動作仕様

タスクがSnooze(tim)を呼ぶ
- state を BLOCKEDに変更
- expire に timを設定
- _Schedule()を呼んでコンテキストスイッチを実行
スケジューラ
- READY状態のタスクの中から次に実行するタスクを選択
タイマー割り込み（Timer）
- BLOCKEDタスクのexpireをデクリメント
- expire が 0になると、タスクをREADYに遷移

実装の詳細はRISC-V OS版の「RISC-V OSを作ろう (5) ～時限待ち」を参照してください。

3. アイドルタスクの導入

これまでの実装では、すべてのタスクが時限待ちに入り、実行可能なタスクが1つも存在しなくなると不都合が生じます。スケジューラは次に実行権を与えるべきタスクを見つけることができません。このような状態になった場合の対策として、次の方式が考えられます。

タスクスケジューラは実行可能なタスク(READY状態のタスク)が現れるまで待ち続ける。
アイドルタスク(何も仕事をしないタスク)を用意する。実行可能なタスク(READY状態のタスク)が存在しない場合、アイドルタスクに実行権を与える。

本連載のOSでは、2.の対策を採用することとします。

上記の説明ではアイドルタスクは何も仕事をしないタスクと説明していましたが、これでは意味なくCPUの計算資源を消費し、消費電力が無駄になります。 ARM64などの現在のCPUアーキテクチャには、割り込みが発生するまで電力を消費せず待機させるwfi(wait for interrupt)命令が用意されています。今回のアイドルタスクの実装では、このwfi命令を使う実装を採用します。

void Idle(void)
{
    while(1)
    {
        asm volatile("wfi");    // 割り込みがあるまで低電力待機
    }
}

タスクスケジューラはChooseNextTask関数を用いてアイドルタスク以外のREADY状態のタスクから次に実行権を与えるべきタスクを選びます。アイドルタスク(TASKIDLE)以外にREADY状態のタスクが存在しない場合のみ、アイドルタスク(TASKIDLE)を次に実行すべきタスクとして選択するようにします。

4. 時限待ちの動作確認

これでC言語の時限待ちを実装できたので実行してみましょう。

以下に途中までの完全なコードを掲示しておきます。

github.com

実行結果：

U-Boot> fatload mmc 0:1 0x1000 boot_arm64os.scr
297 bytes read in 73 ms (3.9 KiB/s)
U-Boot> source 0x1000
## Executing script at 00001000
139576 bytes read in 94 ms (1.4 MiB/s)
54874 bytes read in 23 ms (2.3 MiB/s)
Working FDT set to 3000000
## Booting kernel from Legacy Image at 04000000 ...
   Image Name:   
   Image Type:   AArch64 U-Boot Standalone Program (uncompressed)
   Data Size:    139512 Bytes = 136.2 KiB
   Load Address: 04000000
   Entry Point:  04000000
   Verifying Checksum ... OK
   Loading Standalone Program
## Starting application at 0x04000000 ...
Task1
Task2
Task3

Timer


Timer

Task1

Timer

Task2

Timer

Task1
Task3

Timer


Timer

Task1
Task2

Timer


Timer

Task1
Task3

Timer

Task2

Timer

Task1

Timer


Timer

Task1
Task2
Task3
：
：

5. セマフォ

次はバイナリセマフォを実装します。*1

排他制御したい資源*2に対応したセマフォを定義します。セマフォを取得したタスクのみ、そのセマフォに対応付けられた資源を操作可能という決まりを導入することで、独占的な資源操作を保証します。セマフォの取得に失敗したタスクは、セマフォが解放されるまで待機します。

データ構造

SemaphoreControl
- owner_task：保持中のタスクを指す。未取得時はSEM_AVAILABLEを代入。
TaskControl
- target_sem：取得待ちのセマフォ

動作仕様

AcquireSemaphore

セマフォが空き（owner_task == SEM_AVAILABLE）
- 自タスクをowner_taskに設定、セマフォの所有者となる（取得成功）
セマフォが取得済み
- target_semに対象セマフォを記録
- stateをBLOCKEDにして待機（_TaskBlock）
復帰後
- 本関数の先頭から再実行する（※同時復帰したタスクが先にセマフォを取得している可能性があるため、セマフォ状態のチェックから再実行します。）

TryToAcquireSemaphore

セマフォが空きなら、取得
セマフォが取得済みなら待機せずエラーを返す

ReleaseSemaphore

owner_task = SEM_AVAILABLE 、所有者を空きに設定
そのセマフォを待っていたタスク(state == BLOCKEDかつtarget_sem == 対象セマフォ)の待ちを解除する
- target_sem = NO_SEM
- _TaskUnBlockによりREADYへ遷移

実装の詳細はRISC-V OS版のセマフォ編を参照してください。

6. 食事をする哲学者

食事をする哲学者の問題と呼ばれる並列処理の有名な問題があります。今回はこの問題をセマフォを用いて実現します。

哲学者1人にタスク1つを割り当てます。
フォーク1本にセマフォ1つを割り当てます。
丸いテーブルの周りに座った哲学者それぞれの間にフォーク1本を置きます。
両手にフォークを握った哲学者のみが食事をすることができます。
フォークを取れなかった哲学者は瞑想しつつ2本のフォークが取れるのを待ちます。

デッドロックの回避

哲学者を表すタスク5つとフォークを表すセマフォ5つを定義します。各哲学者は以下の操作を繰り返します。

右フォークもAcquireSemaphoreで待機取得すると、全タスクが左フォークを保持したまま相互待ちになり、デッドロックが発生する可能性があります。そのデッドロックを防ぐため、2本目のフォークはTryToAcquireSemaphoreで取得するようにし、取得できない場合は1本目のフォークも手放して「瞑想(時限待ち)」に戻るようにします。

GetForks
- 左フォークをAcquireSemaphoreで取得
- 右フォークをTryToAcquireSemaphoreで取得
取得成功時
- PhilosopherEat*3実行後、ReleaseForksで解放
取得失敗時
- PhilosopherMeditate*4後に再試行

7. セマフォの動作確認

これでC言語のセマフォを用いた排他制御で食事をする哲学者を実装できたので実行してみましょう。

以下に途中までの完全なコードを掲示しておきます。

github.com

実行結果：

U-Boot 2023.07.02 (Dec 13 2025 - 21:44:31 +0900)

DRAM:  948 MiB (effective 7.9 GiB)
RPI 4 Model B (0xd03115)
Core:  211 devices, 17 uclasses, devicetree: board
MMC:   mmcnr@7e300000: 1, mmc@7e340000: 0
Loading Environment from FAT... Unable to read "uboot.env" from mmc0:1... 
In:    serial
Out:   vidconsole
Err:   vidconsole
Net:   eth0: ethernet@7d580000
PCIe BRCM: link up, 5.0 Gbps x1 (SSC)
starting USB...
Bus xhci_pci: Register 5000420 NbrPorts 5
Starting the controller
USB XHCI 1.00
scanning bus xhci_pci for devices... 4 USB Device(s) found
       scanning usb for storage devices... 0 Storage Device(s) found
Hit any key to stop autoboot:  0 
U-Boot> fatload mmc 0:1 0x1000 boot_arm64os.scr
297 bytes read in 73 ms (3.9 KiB/s)
U-Boot> source 0x1000
## Executing script at 00001000
209336 bytes read in 97 ms (2.1 MiB/s)
54874 bytes read in 24 ms (2.2 MiB/s)
Working FDT set to 3000000
## Booting kernel from Legacy Image at 04000000 ...
   Image Name:   
   Image Type:   AArch64 U-Boot Standalone Program (uncompressed)
   Data Size:    209272 Bytes = 204.4 KiB
   Load Address: 04000000
   Entry Point:  04000000
   Verifying Checksum ... OK
   Loading Standalone Program
## Starting application at 0x04000000 ...
Task1    Eating
Task3    Eating
Task5    Meditating

Timer

Task5    Meditating

Timer

Task2    Meditating
Task5    Eating

Timer


Timer

Task2    Meditating

Timer

Task2    Meditating
Task4    Meditating

Timer

Task3    Eating

Timer

Task2    Meditating
Task3    Eating

Timer

Task1    Eating
Task4    Eating

Timer

Task1    Eating
Task3    Meditating

Timer

Task3    Meditating

Timer

Task2    Eating

Timer

Task1    Meditating
Task5    Eating

Timer

Task4    Meditating

Timer

Task1    Meditating
Task5    Eating

Timer

Task4    Meditating

Timer

Task3    Eating
：
：

8. おわりに

今回は基本的な時限待ちとセマフォを実現しました。この仕組みを応用すれば、ある事象発生を待ち合わせる機能に最大待ち時間を設定することにも利用できます。

本連載のARM64 OS編はこれで一旦完結となります。いつかマルチコアやメモリ保護について解説をする機会があるかもしれません。

ここで紹介したプログラムはGitHubにて公開しています。

github.com

*1:カウンティングセマフォというものも存在します。バイナリセマフォでは同時に1つのタスクのみセマフォを取得することができますが、カウンティングセマフォでは指定された数のタスクが同時にセマフォを取得することが可能です。

*2:資源はメモリ上でのデータ構造のこともありますし、デバイスであることもあります。

*3:食事をする

*4:しばらく瞑想する

VA Linux エンジニアブログ

ARM64 OSを作ろう (4) ～時限待ちとセマフォ

1. はじめに

2. 時限待ち

動作仕様

3. アイドルタスクの導入

4. 時限待ちの動作確認

5. セマフォ

データ構造

動作仕様

6. 食事をする哲学者

デッドロックの回避

7. セマフォの動作確認

8. おわりに