RISC-V OSを作ろう (2) ~ タスク切り替え

執筆者 : 高橋 浩和


はじめに

前回はbootプログラムが動くところまできました。今回は、複数のタスクが切り替わりながら並列動作できる仕組みを作ります。 まだ割り込み機能は無いので、タスクからスケジューラを明示的に呼び出すことにより、別のタスクへ切り替えてもらうという仕組みにします。

マルチタスク

それぞれのタスクは、あたかも自分がCPUを専有しているかのようにプログラムを実行することができます。 各タスクに仮想的なCPUを割り当てることにより実現します。仮想的なCPUとは、実CPUのコピーです。各タスクを管理するデータ構造を用意し、その中にCPUのイメージを保存します。 タスクが動作するときは、タスク管理データにあるCPUのイメージを実CPUに転送します。タスクが動作を中断するときは、実CPUの状態をタスク管理データの中に保存します。

f:id:takava:20210528093451j:plain

RISC-Vアーキテクチャにおけるタスクコンテキスト

まず最小限の機能のOSを考えます。実装単純化のため、ここではタスクは浮動小数点演算を行わないものとします。 タスクのコンテキスト(タスク固有の状態)は、スタックと汎用レジスタの値とPCの値となります。*1

関数呼び出し

タスク切り替え関数を実装する前に、RISC-V環境における関数呼び出しの仕組みを見ておきます。

RISC-V ABIの関数呼び出し規約ではRISC-Vの汎用レジスタの利用方法を定めており、関数呼び出しに関して汎用レジスタを3つのグループに分けることができます。

  1. 呼び出し先関数退避レジスタ(Callee saved registers)。

    関数呼び出しを跨いで値が変化しないことが保証されるレジスタ。関数内でこのレジスタを使用する時は、レジスタ値を一旦退避し、関数終了時に書き戻す必要があります。

  2. 関数呼び出し元退避レジスタ(Caller saved registers)。

    呼び出された関数内で自由に使用してよいレジスタ。関数呼び出し元は、レジスタ値を壊されたくない時は、関数呼び出し前にその値の退避を行なわなければなりません。

  3. 変更不可。値が常に一定であるレジスタ
レジスタ名 別名 説明 グループ
x0 zero ゼロ固定 3.
x1 ra 関数戻りアドレス 2.
x2 sp スタックポインタ 1.
x3 gp グローバルポインタ 3.
x4 tp スレッドポインタ 3.
x5 t0 作業レジスタ, リンクレジスタ 2.
x6-x7 t1-t2 作業レジスタ 2.
x8 s0/fp パーマネントレジスタ、フレームポインタ 1.
x9 s1 パーマネントレジスタ 1.
x10-x11 a0-a1 関数引数、関数戻り値 2.
x12-x17 a2-a7 関数引数 2.
x18-x27 s2-s11 パーマネントレジスタ 1.
x28-x31 t3-t6 作業レジスタ 2.

関数実行中、その関数が使用するスタック領域はSP(スタックポインタ)とFP(フレームポインタ)で示されます。 現在実行中の関数が使用するスタック領域の上端(低位アドレス側)をSP(スタックポインタ)が指し、終端(高位アドレス側)をFP(フレームポインタ)が指します。 ただし、gccの最適化によりフレームポインタを使用するコードは殆どが削除されてしまいます*2

f:id:takava:20210531162619j:plain

関数呼び出し時、引数は可能な限りA0-A7レジスタを使って渡します。 レジスタに載せることができない引数(9個以上の引数、構造体引数など)は、呼び出し元の関数のスタック域を使って渡します。 関数の戻り値も可能な限りA0-A1レジスタを使って、関数呼び出し元に返します。 レジスタに載せることができない戻り値の場合は、引数の場合と同様スタックを使用して渡します。

作業レジスタ(T0-T6)、関数引数レジスタ(A0-A7)は関数内で自由に値を書き換えることが可能です。 これらのレジスタ値は、必要があれば関数呼び出し元が退避することになっています。

一方、パーマネントレジスタ(S0-S11)は、関数終了時には関数呼び出し時の値に戻すことが要求されているレジスタです。 関数内で利用する場合には、あらかじめレジスタの値をスタック上に退避します。

ローカル変数は可能な限り作業レジスタやパーマネントレジスタ上に確保されますが、レジスタに乗りきらない変数はスタック上に確保されます。

RAには現在実行中の関数からの戻り番地が入っており、関数終了時にはRAの値をPCに転送します。現在の関数から更に別の関数を呼び出す場合は、関数呼び出し時にRAが書き換えられてしまうため、あらかじめRAの値をスタックに退避しておく必要があります。*3

タスク切り替え関数の方針

タスク切り替え関数にもRISC-V ABI関数呼び出し規約(関数呼び出しの約束事)を守らせます。

タスク切り替え関数は、現在実行しているタスクが利用しているレジスタの値を保存し、次に動作するタスク用に保存されているレジスタ値を読み込みます。 タスク切り替え関数も普通の関数と同じく「呼び出し先関数退避レジスタ」と、関数の戻り番地情報(RA)を保存します。 通常の関数ではその関数内で利用するレジスタに関してのみ「呼び出し先関数退避レジスタ」の値を保存すれば良いのですが、タスク切り替え関数では全ての「呼び出し先関数退避レジスタ」の値を保存する必要があります。このタスクの実行が中断している間に動作する他のタスクにより、これらレジスタは全て書き換えられてしまう可能性があります。

「関数呼び出し元退避レジスタ」は、タスク切り替え関数の中で保存する必要はありません。 これらレジスタは、タスク切り替え関数を呼び出した関数側で考慮済みです*4

タスク切り替え関数を実装しよう

単純化のため、OS起動時に定義したタスクが全て起動され、永久に動き続ける(タスクは終了しない)ものとします。

タスク切り替え

各タスクにそのタスクを管理するためのデータ構造(TaskControl)を割り当てます。 それぞれのTaskControl中にスタック域(task_stack)も確保し、タスク固有のスタック(タスクスタック)として使用します。

タスク切り替え時には、SP以外の「呼び出し先関数退避レジスタ」はこのスタック域に保存することにします。 タスク切り替え関数からの戻り先アドレス(RA)もスタック域に保存します。 RAの保存はPCの保存に相当します。タスクが実行を再開する時はスタック上にあるRAの値をPCに読み込みます。

struct TaskControl {
    unsigned long sp;
    unsigned long task_stack[STACKSIZE];
} TaskControl[NUMBER_OF_TASKS];

TaskSwitch関数は、引数currentが指すTaskControlで管理されるタスクから、 引数nextが指すTaskControlで管理されるタスクへ切り替えます。

void TaskSwitch(struct TaskControl *current, struct TaskControl *next)
{
    switch_context(&next->sp, &current->sp);
}

汎用レジスタの保存、復帰処理はアセンブリコード記述とします(primitives.s ファイルに記述することにします)。

1つめの引数(A0レジスタ)に次に動作するタスクのSPレジスタ保存域へのポインタが渡り、2つめの引数(A1レジスタ)に現在動作しているタスクのSPレジスタ保存域へのポインタが渡ります。 現在使用しているスタック域にS0-S11(呼び出し先関数退避レジスタ)とRAを保存し、その後SPレジスタの値をA1レジスタの指す先(現在動作しているタスクのTaskControlspメンバ)に保存します。 次にA0レジスタの指す先(次に動作するタスクのTaskControlspメンバ)から読み出した値をSPレジスタに代入し(スタックの切り替え)、その後スタックからS0-S11(呼び出し先関数退避レジスタ)とRAに値を読み込みます。 関数の最後のret命令にて、RAの値がPCに代入されます。

f:id:takava:20210528095739j:plain

    .text
    .globl switch_context
    .type switch_context,@function
    .balign 4
switch_context:
    addi  sp, sp, -8*13
    sd    s0, 0*8(sp)
    sd    s1, 1*8(sp)
    sd    s2, 2*8(sp)
    sd    s3, 3*8(sp)
    sd    s4, 4*8(sp)
    sd    s5, 5*8(sp)
    sd    s6, 6*8(sp)
    sd    s7, 7*8(sp)
    sd    s8, 8*8(sp)
    sd    s9, 9*8(sp)
    sd    s10, 10*8(sp)
    sd    s11, 11*8(sp)
    sd    ra, 12*8(sp)
    sd    sp, (a1)

    ld    sp, (a0)
    ld    s0, 0*8(sp)
    ld    s1, 1*8(sp)
    ld    s2, 2*8(sp)
    ld    s3, 3*8(sp)
    ld    s4, 4*8(sp)
    ld    s5, 5*8(sp)
    ld    s6, 6*8(sp)
    ld    s7, 7*8(sp)
    ld    s8, 8*8(sp)
    ld    s9, 9*8(sp)
    ld    s10, 10*8(sp)
    ld    s11, 11*8(sp)
    ld    ra, 12*8(sp)
    addi  sp, sp, 8*13
    ret
    .size switch_context,.-switch_context

タスクの初期化

今のままでは、まだ一度も動作したことのないタスクに対してタスク切り替えを行なうことはできません。 まだ一度も動作していないタスクのTaskControlとスタックにはタスクの情報が何も入っていないためです。

そこでTaskControlとスタックの初期化が必要となるわけですが、「タスクがタスクエントリ実行時にタスク切り替えが行なわれ、実行が中断している」という状態であるかのように初期化することにします。 スタック上に保存されたS0-S11レジスタの値はゼロ、タスク切り替え関数の戻り先(RA)としてはタスクエントリのアドレスを埋め込みます。 TaskControlspメンバには、このスタック上のS0-S11,RA保存域を指させます。

f:id:takava:20210528100437j:plain

typedef struct {
    unsigned long s0;
    unsigned long s1;
    unsigned long s2;
    unsigned long s3;
    unsigned long s4;
    unsigned long s5;
    unsigned long s6;
    unsigned long s7;
    unsigned long s8;
    unsigned long s9;
    unsigned long s10;
    unsigned long s11;
    unsigned long ra;
} context;

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

最初のタスクの起動

タスクの初期化により、初めて動作するタスクに対してタスク切り替え関数が動作するようになりましたが、 一番最初に動作するタスクには切り替え元となるタスクが存在しません。 最初のタスクの起動用には専用の関数を用意します。この関数は、タスク切り替え関数の後半処理(スタック上の値のレジスタへの読み込み)のみを行ないます。 タスク切り替え関数(switch_context)の途中に、最初のタスクの起動関数の入り口(load_context)を埋め込むことで実現することにします*5

    .text
    .globl switch_context
    .globl load_context
    .type switch_context,@function
    .balign 4
switch_context:
    addi  sp, sp, -8*13
    sd    s0, 0*8(sp)
    sd    s1, 1*8(sp)
    sd    s2, 2*8(sp)
    sd    s3, 3*8(sp)
    sd    s4, 4*8(sp)
    sd    s5, 5*8(sp)
    sd    s6, 6*8(sp)
    sd    s7, 7*8(sp)
    sd    s8, 8*8(sp)
    sd    s9, 9*8(sp)
    sd    s10, 10*8(sp)
    sd    s11, 11*8(sp)
    sd    ra, 12*8(sp)
    sd    sp, (a1)

load_context:
    ld    sp, (a0)
    ld    s0, 0*8(sp)
    ld    s1, 1*8(sp)
    ld    s2, 2*8(sp)
    ld    s3, 3*8(sp)
    ld    s4, 4*8(sp)
    ld    s5, 5*8(sp)
    ld    s6, 6*8(sp)
    ld    s7, 7*8(sp)
    ld    s8, 8*8(sp)
    ld    s9, 9*8(sp)
    ld    s10, 10*8(sp)
    ld    s11, 11*8(sp)
    ld    ra, 12*8(sp)
    addi  sp, sp, 8*13
    ret
    .size switch_context,.-switch_context

下記の例では、タスク3つを初期化した後、TASK1タスクを最初に動作するタスクとして選択しています。

void main(void) {
    clearbss();

    InitTask(TASK1, Task1);
    InitTask(TASK2, Task2);
    InitTask(TASK3, Task3);

    load_context(&TaskControl[TASK1].sp);
}

デバッグ文

gdb接続しなければプログラムの動きが全く分からないのは不便なので、簡単な文字列出力関数を用意したいと思います。 文字列はvirtターゲットが持つuartを通して出力させることにします。virtターゲットは、0x10000000番地に1つ目のuartを持っています。

今回用意した文字列出力関数は、このuartの送信レジスタにどんどん文字を書き込むという仮想マシン環境専用実装になっています。 この実装は手抜きであり、仮想マシン環境以外では動作しません。実ハードウェアではコントローラの初期化が必要ですし、さらに文字書き込み前に送信レジスタが空になるのを待ち合わせなければなりません。

static void put_char(char c)
{
    volatile unsigned char * const uart = (unsigned char *)0x10000000U;
    *uart = c;
}

void print_message(const char *s)
{
    while (*s) put_char(*s++);
}

タスク切り替え関数を動かしてみよう

タスクそれぞれが、次に動作するタスクを指定してタスク切り替え関数TaskSwitchを呼び出すというプログラムを用意しました。

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

void Task1(void)
{
    while (1) {
        print_message("Task1\n");
        TaskSwitch(&TaskControl[TASK1], &TaskControl[TASK2]);
    }
}

void Task2(void)
{
    while (1) {
        print_message("Task2\n");
        TaskSwitch(&TaskControl[TASK2], &TaskControl[TASK3]);
    }
}

void Task3(void)
{
    while (1) {
        print_message("Task3\n");
        TaskSwitch(&TaskControl[TASK3], &TaskControl[TASK1]);
    }
}

オブジェクトファイルを生成し、qemu上で起動します。 3つのタスクが交互に動作していることが分かります。

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

タスクスケジューラの用意

次に動作するタスクを選択するという作業からタスクを解放します。 タスクスケジューラを呼び出すと、タスクスケジューラは何らかのアルゴリズムに基づき次に動作させるタスクを選択し、タスク切り替え関数を呼び出します。

今回は単純なラウンドロビンアルゴリズムを採用します。 タスクスケジューラScheduleを呼び出すと、現在動作してるタスクの次に定義されているタスクを選択し、そのタスクに実行権を渡します。

TaskIdType CurrentTask;

static TaskIdType ChooseNextTask(void)
{
    return (CurrentTask + 1) % NUMBER_OF_TASKS;
}

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

タスクスケジューラを動かしてみよう

タスクからのタスク切り替え関数TaskSwitch呼び出しを、タスクスケジューラSchedule呼び出しに変更します。

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

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

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

先程と同じくオブジェクトファイルを生成し、qemu上で起動します。 動作的には先程のものと同じになりますが、タスクスケジューラのアルゴリズムを修正することでタスクの動作順を変更することができます。

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

この先の連載では、このタスクケジューラ呼び出しという作業からもタスクを解放します。

最後に

今回はタスク切り替え関数を実装しました。このタスク切り替えの仕組みは、Linuxなどの大きなOSでも殆ど同じです。 ここで紹介したプログラムはgithubにて公開しています。まだまだOSと呼べるようなものではありませんが、今後少しづつ機能を追加しOSらしくしていきます。 github.com

興味のある方は、浮動小数点演算レジスタの切り替え機能の追加に挑戦しても良いでしょう。 RISC-V CPUには、浮動小数点演算機能無しのものから、単精度の演算機能のみを提供するもの、倍精度や4倍精度の演算機能を提供するものまであります。 汎用レジスタと同じように、タスク切り替え毎に浮動小数点演算レジスタも切り替える実装であれば難しくありません。

効率的な浮動小数点演算レジスタの切り替えを実現するとなるとかなり大変です。一般的なシステムでは、ほとんどのタスクは浮動小数点演算を行わない、つまり浮動小数点演算レジスタを使わないため、タスク切り替え毎にこの大きな浮動小数点演算レジスタセットも切り替えるのは効率が良いとは言えません。浮動小数点演算レジスタの保存と復帰操作の回数は可能な限り減らしたいところです。機会があれば、浮動小数点演算レジスタセットの切り替えについても触れたいところです。RISC-Vにはこれを支援するための機能もあります。

次回は割り込みを扱います。OSが割り込みを受付け、割り込みハンドラを起動する仕組みを作ります。

おまけ

qemu virtターゲット(RISC-V VirtIO board)のメモリマップはqemuのコードから入手しました。 ドキュメントは見つけることができませんでした。

static const MemMapEntry virt_memmap[] = {
                         :
    [VIRT_UART0] =       { 0x10000000,         0x100 },
                         :
    [VIRT_DRAM] =        { 0x80000000,           0x0 },
};

*1:ステータスレジスタも含めても良いかもしれませんが、現段階の実装ではステータスレジスタにタスク固有な情報は無いので除外します。

*2:オプション-fno-omit-frame-pointerで、最適化を抑制することもできます。

*3:RISC-V ABIでは、関数からの戻り番地を入れることのできるレジスタ(リンクレジスタ)としてT0を使うこともできます。T0を利用した関数呼び出しは、ミリコード(CISCの高機能命令のような処理を行なうプログラムコード)呼び出しなどに利用することを想定しているようです。RAレジスタの値を維持しなければならない関数prorogue/epilogue(前処理、後処理)用ミリコード呼び出しにも使えるようにすることを狙って、T0もリンクレジスタとして指定できるようにしたようです。

*4:C言語で記述してあれば、コンパイラが自動的にレジスタ値を保存復帰するコードを生成します。

*5:swithch_context関数の引数をload_context関数からも利用できるようにするために、第1引数A0に切り替え先のタスクを渡すようにしています。