RISC-V OSを作ろう (5) ~ 時限待ち

執筆者 : 高橋 浩和


はじめに

今回はセマフォ機能を説明することを考えていましたが、少し順番を変更し、先にタスクの時限待ちの機能を実現することにしました。 タスクの時限待ちの機能は、指定時間だけタスクをスケジューリング対象から外す機能です。

実装方針

タスクが明示的に要求することにより、自タスクを時限待ち状態にできるようにします。このとき時限待ち状態でいる時間を指定できるようにします。 タスクスケジューラは時限待ち状態のタスク以外から実行権を与えるタスクを選択するようにします。 タイマハンドラには、指定された時間を経過した時限待ち状態のタスクの時限待ちを解除させます。

f:id:takava:20211012104501j:plain

タスク状態

タスクの時限待ち機能を実現するために、タスクの状態として2つの状態を導入します。 タスク状態はTaskControlオブジェクトのstateメンバに持たせます。

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

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

struct TaskControl {
    enum { READY, BLOCKED } state;
        :
    int expire;
        :
};

時限待ち要求

タスクがSnooze関数を呼び出すことにより、呼び出したタスクを時限待ち状態に遷移できるようにします。 タスクの状態をBLOCKEDに変更し、タスクスケジューラ(_Schedule)を呼び出します。 タスクオブジェクトのexpireメンバには時限待ちの時間(tim)を登録します。

void Snooze(int tim)
{
    DisableInt();
    TaskControl[CurrentTask].state = BLOCKED;
    TaskControl[CurrentTask].expire = tim;
    _Schedule();
    EnableInt();
}

呼び出されたタスクスケジューラ(_Schedule)は、ChooseNextTask関数を用いて次に実行権を与えるべきタスクを選びます。 ChooseNextTask関数は、READY状態のタスクの中からが次に実行すべきタスクを選択します。

static TaskIdType ChooseNextTask(void)
{
    TaskIdType task = CurrentTask;

    do {
        task = (task + 1) % NUMBER_OF_TASKS;
    } while (TaskControl[task].state != READY);

    return task;
}

void _Schedule(void)
{
    TaskIdType from = CurrentTask;
    CurrentTask = ChooseNextTask();
    if (from != CurrentTask) {
        TaskSwitch(&TaskControl[from], &TaskControl[CurrentTask]);
    }
}

タイマハンドラの仕事

タイマハンドラ(Timer)の仕事を1つ追加します。 タイマハンドラ(Timer)は、動作毎にBLOCKED状態である全てのタスクのexpireメンバの値から1を引き、expireメンバが0になった時点でそのタスクの状態をREADYに変更し、タスクの待機状態を解除します。READY状態になったタスクは、タスクスケジューラによる実行権付与の対象となります。

int Timer(void)
{
        :
        :
    for (task = 0; task < NUMBER_OF_TASKS; task++) {
        if (TaskControl[task].state == BLOCKED && TaskControl[task].expire > 0) {
            if (--TaskControl[task].expire == 0) {
                TaskControl[task].state = READY;
            }
        }
    }
        :
        :
}

アイドル状態

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

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

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

void Idle(void)
{
    while (1) {
        /* do nothing */
    }
}

typedef enum {
    TASK1 = 0,
    TASK2,
    TASK3,
    TASKIDLE,
    NUMBER_OF_TASKS,
} TaskIdType;

struct TaskControl {
    enum { READY, BLOCKED } state;
    void (*entry)(void);
    long time_slice;
    long remaining_time;
    int expire;
    unsigned long sp;
    unsigned long task_stack[STACKSIZE];
} TaskControl[NUMBER_OF_TASKS] = {
    {.entry = Task1, .state = READY, .time_slice = 2},
    {.entry = Task2, .state = READY, .time_slice = 4},
    {.entry = Task3, .state = READY, .time_slice = 1},
    {.entry = Idle,  .state = READY, .time_slice = 1},
};

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

static TaskIdType ChooseNextTask(void)
{
    TaskIdType task = CurrentTask;

    do {
        task = (task + 1) % NUMBER_OF_TASKS;
    } while (TaskControl[task].state != READY && task != CurrentTask && task != TASKIDLE);

    if (TaskControl[task].state != READY) {
        task = TASKIDLE;
    }

    return task;
}

動かしてみよう

全てのタスクは実行が始まるとSnooze関数を呼び出し、即座に時限待ち状態になるようにします。 全てのタスクが同時に時限待ち状態に入ると本OSはアイドル状態になり、実行可能なタスクが現れるのを待ち続けます。

void Task1(void)
{
    while (1) {
        print_message("Task1\n");
        Snooze(2);
    }
}

void Task2(void)
{
    while (1) {
        print_message("Task2\n");
        Snooze(3);
    }
}

void Task3(void)
{
    while (1) {
        print_message("Task3\n");
        Snooze(4);
    }
}

コードをコンパイルし、動作させます。 タスクは実行が開始すると即座に時限待ち要求を行なうため、殆どの時間はアイドルタスクを除いて全てのタスクがスケジューリング対象外となっていますが、問題なく動作しています。

$ riscv64-unknown-elf-gcc -O2 -mcmodel=medany -ffreestanding -g -c main.c primitives.s start.s
$ riscv64-unknown-elf-ld main.o primitives.o start.o -T riscv-virt.lds
$ qemu-system-riscv64 -nographic -machine virt -m 128M -kernel a.out -bios none
Task1
Task2
Task3
Timer
Timer
Task1
Timer
Task2
Timer
Task1
Task3
Timer
Timer
Task1
Task2

最後に

今回は単純な時限待ちを実現しましたが、他の機能と組み合わせた実装も可能です。 例えば、ある事象発生を待ち合わせる機能に最大待ち時間を設定することなどにも利用できます。

次回はタスク間の排他機能を実現します。複数タスクが連携して動作できるようになります。

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

おまけ

今回の実装では、アイドルタスクは空の無限ループを実行し続けるようにしました。 しかしこの方法では意味なくCPU時間を消費するため、電力を無駄遣いします。このような用途のための何もしない命令*1を備えたCPUも多く、そのようなCPU用のOSのアイドルタスクではそれら何もしない命令を呼び出すようにすると良いでしょう。CPUに何らかのイベントが発生するまでCPUを停止させることができます。

*1:haltやwaitのような名前が付いています。