無限遠まで突撃中

ネット日記書きの徒然。

自作OSでマルチタスクやった

この記事は coins Advent Calendar 2019 3日目の記事です。

この記事は WORDIAN Advent Calendar 2019 3日目の記事です。。

この記事は OS-CPU Advent Calendar 2019 3日目の記事です。。。

師走の挨拶

どうもこんにちは、突撃隊です。

64bit自作OS「minOS」をちまちま作っとるのですが、11月でついにマルチタスクを実装できたので解説します。

github.com

設計

スレッドかプロセスか

OSのタスク単位としてとりあえずスレッドを実装することにしました。 プロセスはメモリ空間を分離しなくてはいけないので、その分コーディングが大変だからです。 スレッドならスタックを用意してあげるだけなので簡単簡単。

thread 構造体

スレッドごとの構造体はこんな感じにしてみました。

struct thread_func {
    void (*func)(int, char**);
    int argc;
    char **argv;
};

enum thread_state {
    RUNNABLE,
    SLEEP,
    DEAD
};

struct thread {
    uint64_t *stack;
    uint64_t rsp;
    // uint64_t rip;
    struct thread_func func_info;
    enum thread_state state;
    int index;
};

struct thread ですが、上から順に

  1. スレッドのスタック領域の開始アドレス
  2. スレッドごとのスタックポインタ
  3. スレッドで実行する関数の情報
  4. スレッドの状態
  5. スレッドキューに登録した際のインデックス

です。

順番に解説していきます。

スレッドのスタック

自作の malloc 関数を用いてスタック領域を確保します。 大きさは 0x1000 = 4kB としています。

malloc 関数のソースコードはこちら。

https://github.com/Totsugekitai/minOS/blob/develop/kernel/mm/memory.c

スレッドごとのスタックポインタ

汎用レジスタはスタックに push しますが、スタックポインタは構造体に持たせるほうがやりやすそうです。

スレッドで実行する関数の情報

関数ポインタとその引数を受け取ります。

スレッドの状態

RUNNABLE SLEEP DEAD の3種類を用意しておきました。

スレッドキューに登録した際のインデックス

minOSではスレッドのキューはただの配列です。 スレッドの削除時に配列に登録したときのインデックスが必要になるのでパラメータとして持たせてあります。

どのタイミングでスレッド切り替えをするか

タイマ割り込みのタイミングでスレッド切り替えをすることにしました。 タイマ割り込みの何回かに一回にスケジューラを呼び出してタスクを切り替えます。

coinsLT#110で話したときの資料が詳しいです。

docs.google.com

実装

今回のキモはスレッドのスタックの初期化処理とスレッドを切り替える瞬間の処理です。

スタックの初期化処理

/** スレッドの生成
 * thread構造体の初期化とスタックの初期化を行う
 */
struct thread thread_gen(void (*func)(int, char**), int argc, char **argv)
{
    struct thread thread;

    thread.stack = (uint64_t *)minmalloc(STACK_LENGTH);
    thread.rsp = (uint64_t)(thread.stack + STACK_LENGTH);
    thread.rip = (uint64_t)thread_exec;
    thread.func_info.func = func;
    thread.func_info.argc = argc;
    thread.func_info.argv = argv;

    put_str_num_serial("thread stack bottom: ", (uint64_t)thread.stack + STACK_LENGTH);
    put_str_num_serial("thread rsp: ", thread.rsp);

    return thread;
}

void thread_stack_init(struct thread *thread)
{
    thread->rsp = init_stack(thread->rsp, thread->rip, thread);
    put_str_num_serial("thread stack bottom: ", (uint64_t)thread->stack + STACK_LENGTH);
    put_str_num_serial("thread rsp: ", thread->rsp);
}

void thread_exec(struct thread *thread)
{
    thread->func_info.func(thread->func_info.argc, thread->func_info.argv);
    thread_end(thread->index);
    minfree(thread->stack);
    thread_scheduler();
}

thread_gen 関数でスレッドの生成を行います。 thread 構造体に各種情報を登録していきます。

thread_stack_init でスレッドのスタックの初期化を行います。この時スタックポインタの値も調整されます。

init_stack 関数の実装はレジスタをいじるのでアセンブラで書きます。

.global     init_stack
.align      16
init_stack:           # uint64_t init_stack(uint64_t stack_bottom, uint64_t rip, struct thread *thread);
    cli
    mov     rcx,rsp   # save rsp at rcx
    mov     rsp,rdi   # move rip to rsp
# push general registers to stack
    push    rsi       # push rip(second argument) to stack bottom
                      # because function switch_context requires return rip
    push    0         # rbp
    push    0         # r11
    push    0         # r10
    push    0         # r9
    push    0         # r8
    push    rdx       # rdi
    push    0         # rsi
    push    0         # rcx
    push    0         # rdx
    push    0         # rax
    mov     rax,rsp   # set current rsp to return value
    mov     rsp,rcx   # load rsp from rcx
    sti
    ret

まず現在の rsp を rcx に保存し、今のスタックに戻ってこれるようにします。 次に init_stack 関数の第1引数で受け取ったスレッドのスタックポインタをロードして、スレッドのスタックの初期化作業を始めます。 コード中のコメントと push している数値が初期化のデフォルト値に対応しています。

rdi だけ rdx つまり init_stack に渡された第3引数をセットしていますが、これは thread_exec に渡す引数を設定しています。

少しややこしいので説明すると、まずスレッドで実行する関数を thread_exec で包みます。 そして thread_exec をスレッドで実行する関数として登録します（thread_gen をよく見ると関数の設定で thread_exec を登録している）。 というのも、 thread_exec でスレッドの関数が終わった際の終了処理とスケジューラ呼び出しを行うからです。 thread_exec には thread 構造体へのポインタが必要なので、レジスタの初期化を行うときに rdi つまり第一引数に thread 構造体へのポインタを設定してやることで引数を渡します。 thread_exec の末尾3行はスレッドの状態を変更し、mallocした領域を開放し、スケジューラを呼び出します。

thread_gen と thread_stack_init はこんな感じで使います。

    // スレッドを生成
    struct thread thread0 = thread_gen(console, 0, 0);
    struct thread thread1 = thread_gen(task_a, 0, 0);
    struct thread thread2 = thread_gen(task_b, 0, 0);
    struct thread thread3 = thread_gen(task_c, 0, 0);

    // initialize stack
    thread_stack_init(&thread0);
    thread_stack_init(&thread1);
    thread_stack_init(&thread2);
    thread_stack_init(&thread3);

スレッドを切り替える処理

まずタイマの割り込みハンドラでスケジューラを呼び出す処理を見ましょう。

/**
 * タイマ割り込みハンドラ
 * クロック値を進めて、スケジューラを呼び出す
*/
__attribute__((interrupt))
void timer_handler(struct InterruptFrame *frame)
{
    // クロック値を進める
    milli_clock++;
    // EOIをPICに送る
    io_outb(PIC0_OCW2, PIC_EOI);
    io_outb(PIC1_OCW2, PIC_EOI);

    /** 周期が来たらスケジューラを呼び出す
     * 各種パラメータはint_handler.hで設定
     */
    if (milli_clock > previous_interrupt + timer_period && milli_clock > 100) {
        previous_interrupt = milli_clock;
        put_str_num_serial("timer_handler old rip: ", frame->rip);
        puts_serial("\n");
        thread_scheduler();
    }
}

if の条件式でスケジューラを呼び出す条件を設定しています。 間隔をグローバル変数 timer_period で指定しています。 一定時間が経ったら thread_scheduler を呼び出すようになっています。

次に thread_scheduler を見てみましょう。

void thread_scheduler(void)
{
    // update current_thread_index
    int old_thread_index = current_thread_index;
    int i = 1;
    while (current_thread_index == old_thread_index) {
        if (threads[(current_thread_index + i) % THREAD_NUM]->state == RUNNABLE) {
            current_thread_index = (current_thread_index + i) % THREAD_NUM;
        }
        i++;
    }

    put_str_num_serial("next thread index: ", (uint64_t)current_thread_index);
    put_str_num_serial("next start rsp: ", threads[current_thread_index]->rsp);
    put_str_num_serial("next start func address: ", (uint64_t)(threads[current_thread_index]->func_info.func));
    puts_serial("\n");
    puts_serial("dispatch start\n\n");

    switch_context(&threads[old_thread_index]->rsp, threads[current_thread_index]->rsp);
}

前半部でスレッドキューから次に実行するスレッドを選択しています。

後半部で重要な処理は switch_context です。見てみましょう。

switch_context:   # void switch_context(uint64_t *current_rsp, uint64_t next_rsp);
# push current task's general registers to stack
    push    rbp
    push    r11
    push    r10
    push    r9
    push    r8
    push    rdi
    push    rsi
    push    rdx
    push    rcx
    push    rax
# switch rsp
    mov     [rdi],rsp
    mov     rsp,rsi
# pop next task's general registers from stack
    pop     rax
    pop     rcx
    pop     rdx
    pop     rsi
    pop     rdi
    pop     r8
    pop     r9
    pop     r10
    pop     r11
    pop     rbp
# return to next task
    ret

レジスタをいじるためアセンブラでしか書けません。

まず現在実行しているスレッドのレジスタの値を保存するために、現在のスレッドのスタックに現在のスレッドのレジスタを保存しています。

次にスタックポインタ rsp の処理です。 現在のスタックポインタを現在のスレッドの構造体に保存し、次に実行するスレッドのスタックポインタを読み出します。

するとここでスタックが切り替わるため、次に実行するスレッドのスタックから次に実行するスレッドのレジスタを読み出すことができます。 ですので次に実行するスレッドのレジスタをスタックから読み出します。

最後に ret で rip を読み出し、次のスレッドにジャンプします。

最後の ret でどこにジャンプするのか？

これは少しややこしいですので説明します。 switch_context が呼ばれた瞬間のスタックが属するスレッドをAt、次に実行するスレッドをBtとします。

まず switch_context 中で rsp が切り替わったときにスタックがBtのものに切り替わります。 レジスタをpopしていって最後に ret を発行すると、 スタックはBtのもので rip は thread_scheduler 関数の switch_context から抜けた所に飛びます。

thread_scheduler 関数はこれ以上の処理はないため、 スタックはBtのもので rip はタイマ割り込みハンドラの timer_handler の thread_scheduler から抜けた所に飛びます。

timer_handler はこれ以上の処理はないため、 スタックはBtのもので rip は割り込み前に実行していた所がロードされます。 スタックがBtのもの なので、ロードされる rip はスタックBtに積まれた関数中のアドレスであり、スタックBtに積まれる関数というのはスレッドBtに登録されている関数です。

実装は以上

たぶんこれで動くと思います。

まとめ

タスクスイッチの実装はスタックにレジスタを積まなくてはならず、かなりややこしい部分です。 実装は大変苦労しましたが、喜びもひとしおでしたね。