RISC-V OSを作ろう (4) ~ タイムシェアリングスケジューリング

執筆者 : 高橋 浩和

はじめに

今回はタイムシェアリングスケジューリング機能を実装します。 タイマ割り込みを契機にタスクスケジューラを起動することにより実現します。

実装方針

今まではタスクコンテキストからの明示的なタスクスケジューラ呼び出しのみであったため、タスクスケジューラを呼び出すタスクと、タスクスケジューラにより実行権を与えられるタスクは異なっていても、どちらもタスクコンテストでした。 今回はタイマハンドラのコンテキストからタスクスケジューラを呼び出し、タイマハンドラが終了せずにタスクスケジューラによって選択されたタスクに実行権が与えられます。タイマハンドラに割り込まれたタスクは、実行中のタイマハンドラごと実行を中断させられます。 この実行を中断されたタスクは、しばらくするとタスクスケジューラにより再度実行権をあたえられます。このタスクは、タイマハンドラの終了処理から実行を再開し、タスクの実行中断地点へ復帰します。

実現にあたっては、幾つか注意しなければならない点があります。

  1. タスクスケジューラ実行中にタイマ割り込みが入らないこと

    タスクスケジューラ実行中にタイマ割り込みが入り、そこから起動されたタイマハンドラがタスクスケジューラを呼び出すとコンテキストが壊れます。

  2. タスクスケジューラはタスクコンテキスト上で呼び出すこと

    実行状態はタスク状態(割り込み・例外発生状態ではない)であることが必要です。 また、タスクスケジューラはタスクスタックを使って動作する前提で実装されています。

タスクスケジューラ

タスクスケジューラは全割り込み禁止状態で実行します。 Schedule関数は割り込み禁止(DisableInt関数)した後、タスクスケジューラの本体関数_Scheduleを呼び出すこととします。 タスクスケジューラ終了時には割り込み許可(EnableInt関数)を行ないます。

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

void Schedule(void)
{
    DisableInt();
    _Schedule();
    EnableInt();
}

割り込み禁止・許可はMSTATUSレジスタのMIEビット操作により実現します。

    .equ   MSTATUS_MIE, 0x8

    .global EnableInt
    .type EnableInt,@function
EnableInt:
    li    t0, MSTATUS_MIE
    csrrs zero, mstatus, t0
    ret
    .size EnableInt,.-EnableInt

    .global DisableInt
    .type DisableInt,@function
DisableInt:
    li    t0, MSTATUS_MIE
    csrrc zero, mstatus, t0
    ret
    .size DisableInt,.-DisableInt

タイマハンドラ入口

タイマハンドラ本体(Timer関数)が0以外を戻り値とした場合、タスクスケジューラを呼び出すものとします。 戻り値はa0レジスタに格納されています。 Timer関数からの復帰時にスタックをタスクスタックへ切り戻した(mv sp, s0)後、 beqz a0, 1fの行で戻り値を確認しています。a0が0であった場合はタイマハンドラ終了処理へ分岐します。

a0が0以外であった場合は分岐せず、タスクスケジューラ本体(_Schedule)を呼び出します。

タスクスケジューラ呼び出し前にMEPC、MSTATUSレジスタの値の退避を行ないます。タスクスケジューラ関数呼び出しから戻った時に、本関数からタイマに割り込まれたタスクに復帰するために必要となります。MEPCには復帰アドレス、MSTATUSにはタスクコンテキスト実行時の状態が格納されています。

f:id:takava:20210824104523j:plain

タスクが利用していた汎用レジスタのうち関数呼び出し元退避レジスタ(Caller saved registers)の値は退避済みです。 退避先はタスクスタックであり、タスクスケジューラによりスタック切り替えが行われます。他タスクに実行権が移ってもこれら退避された値が壊されることはありません。 呼び出し先関数退避レジスタ(Callee saved registers)は、タスクスケジューラから呼び出されるタスク切り替え関数(TaskSwitch)にて切り替えが行われます。

f:id:takava:20210823191730j:plain

更にタスクスケジューラ呼び出し前に、MSTATUSレジスタのゼロクリア(csrw mstatus, zero)により、MIEフィールドのクリア(割り込み禁止)とMPPフィールドのクリア(割り込み・例外発生状態解除)を行ないます。これにより、タスクコンテキストからの明示的タスクスケジューラ呼び出し時と同じ状態で、タスクスケジューラ本体(_Schedule)が実行されることになります。

    .balign 4
timer_handler:
    addi  sp, sp, -8*18
    sd    ra, 0*8(sp)
    sd    a0, 1*8(sp)
    sd    a1, 2*8(sp)
    sd    a2, 3*8(sp)
    sd    a3, 4*8(sp)
    sd    a4, 5*8(sp)
    sd    a5, 6*8(sp)
    sd    a6, 7*8(sp)
    sd    a7, 8*8(sp)
    sd    t0, 9*8(sp)
    sd    t1, 10*8(sp)
    sd    t2, 11*8(sp)
    sd    t3, 12*8(sp)
    sd    t4, 13*8(sp)
    sd    t5, 14*8(sp)
    sd    t6, 15*8(sp)
    sd    s0, 16*8(sp)

    mv    s0, sp
    la    sp, _stack_end
    jal   Timer
    mv    sp, s0
    beqz  a0, 1f

    sd    s1, 17*8(sp)
    csrr  s0, mepc
    csrr  s1, mstatus
    csrw  mstatus, zero
    jal   _Schedule
    csrw  mepc, s0
    csrw  mstatus, s1
    ld    s1, 17*8(sp)
1:
    ld    ra, 0*8(sp)
    ld    a0, 1*8(sp)
    ld    a1, 2*8(sp)
    ld    a2, 3*8(sp)
    ld    a3, 4*8(sp)
    ld    a4, 5*8(sp)
    ld    a5, 6*8(sp)
    ld    a6, 7*8(sp)
    ld    a7, 8*8(sp)
    ld    t0, 9*8(sp)
    ld    t1, 10*8(sp)
    ld    t2, 11*8(sp)
    ld    t3, 12*8(sp)
    ld    t4, 13*8(sp)
    ld    t5, 14*8(sp)
    ld    t6, 15*8(sp)
    ld    s0, 16*8(sp)
    addi  sp, sp, 8*18
    mret
    .size timer_handler,.-timer_handler

タイムスライス

各タスクにタイムスライス値を与えることにします。このタイムスライス値は、TaskControlのtime_sliceメンバに持たせます。 タスクはタイムスライス値で与えられた回数のタイマ割り込みが発生するまで、実行を継続できるものとします。

struct TaskControl {
        :
    long time_slice;
    long remaining_time;
        :
} TaskControl[NUMBER_OF_TASKS] = {
    {.time_slice = 2},
    {.time_slice = 4},
    {.time_slice = 1},
};

タイマハンドラ(Timer)動作毎に現在実行しているタスクの持ち時間(remaining_timeメンバ)を減算します。持ち時間が0になったら、タイマハンドラ(Timer)の戻り値をTRUEにし、再スケジュールを要求します。再度スケジュールされる時に備え、持ち時間(remaining_timeメンバ)を初期値(time_sliceメンバの値)に戻すことも行なっておきます。

int Timer(void)
{
    print_message("Timer\n");

    do {
        *reg_mtimecmp += INTERVAL;
    } while ((long)(*reg_mtime - *reg_mtimecmp) >= 0);

    if (--TaskControl[CurrentTask].remaining_time <= 0) {
        TaskControl[CurrentTask].remaining_time = TaskControl[CurrentTask].time_slice;
        return TRUE;
    }
    return FALSE;
}

タスク起動時の工夫

タスクスケジューラを割り込み禁止状態で動作するようにしたため、全てのタスクは割り込み禁止状態から動作を始めます。 今までは各タスクのエントリ関数から実行を開始するようにしていましたが、これを共通関数TaskEntryから実行を始めるように変更します。 TaskEntry関数は割り込み許可(EnableInt関数)操作を行なった後、各タスクのエントリ関数を呼び出します。

struct TaskControl {
    void (*entry)(void);
        :
} TaskControl[NUMBER_OF_TASKS] = {
    {.entry = Task1},
    {.entry = Task2},
    {.entry = Task3},
};

static void TaskEntry(void)
{
    EnableInt();
    TaskControl[CurrentTask].entry();
}

static void InitTask(TaskIdType task)
{
    context* p = (context *)&TaskControl[task].task_stack[STACKSIZE] - 1;
    p->ra = (unsigned long)TaskEntry;
    TaskControl[task].sp = (unsigned long)p;
    TaskControl[task].remaining_time = TaskControl[task].time_slice;
}

動かしてみよう

タスクスケジューラを呼び出さずともタスクが自動的に切り替わることを確認します。 タスクTask1、タスクTask2から明示的なタスクスケジューラ呼び出しするコードを削除します。

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

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

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

コードをコンパイルし、動作させます。 Task1動作時にタイマ割り込みが2回発生するとTask2に切り替わっていることが分かります。 Task2動作時にタイマ割り込みが4回発生するとTask3に切り替わっています。 Task3は明示的なタスクスケジューラ呼び出しにより、即座にTask1に切り替わっています。

$ riscv64-unknown-elf-gcc -O2 -mcmodel=medany -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
Task1
Task1
Task1
Task1
Timer
Task1
Task1
Task1
Task1
Timer
Task2
Task2
Task2
Task2
Timer
Task2
Task2
Task2
Task2
Timer
Task2
Task2
Task2
Task2
Timer
Task2
Task2
Task2
Task2
Timer
Task3
Task1
Task1
Task1

最後に

複数のタスクが自動的に切り替わりながら並列動作するようになり、少しOSらしくなってきました。 次回は複数のタスクが連携して動作できるようにするための機能を実現します。

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