今日はマルチタスキングの残りの部分を実装します。

17日目にRing 3に遷移するときに説明しましたが，Ring 0からRing 3に遷移する際はiretqを使います。逆にRing 3からRing 0へは割り込みハンドラや例外により遷移します。

タスクの切り替えは，タイマ割り込みハンドラの後に行うことにします。割り込みハンドラの後に別のタスクを再実行するため，割り込みハンドラでは，すべてのレジスタをスタックに保存します。今回は簡単のため，浮動小数点は扱わない前提で整数レジスタのみを保存します。このスタックに保存されたレジスタを スタックフレーム（Stackframe） と呼びます。スタックにrax, rbx, ..., gsの順で積んでいった場合，スタックフレームは以下の構造体のようになります。割り込みハンドラが呼ばれる際にCPLが変わる場合は，%ss, %rsp, %rflags, %cs, %ripをそれぞれ64ビット領域としてスタックに積むので，一番下にはこれらの値が格納されています。

struct stackframe64 {
    /* Segment registers */
    uint16_t gs;
    uint16_t fs;

    /* Base pointer */
    uint64_t bp;

    /* Index registers */
    uint64_t di;
    uint64_t si;

    /* Generic registers */
    uint64_t r15;
    uint64_t r14;
    uint64_t r13;
    uint64_t r12;
    uint64_t r11;
    uint64_t r10;
    uint64_t r9;
    uint64_t r8;
    uint64_t dx;
    uint64_t cx;
    uint64_t bx;
    uint64_t ax;

    /* Restored by `iretq' instruction */
    uint64_t ip;            /* Instruction pointer */
    uint64_t cs;            /* Code segment */
    uint64_t flags;         /* Flags */
    uint64_t sp;            /* Stack pointer */
    uint64_t ss;            /* Stack segment */
} __attribute__ ((packed));

各タスクは，このスタックフレームとページテーブル（仮想メモリ情報）をコンテキストとして保持します。つまり，タスクの切り替えは，スタックフレームの切り替えとページテーブルの切り替えを割り込みハンドラないで行うことで実現できます。今回は，ページテーブルの切り替えは面倒なので，同じページテーブルを共有します。Unix系OSで言うところのスレッドのように実現します。また，メモリの権限管理を追加するにはメモリアロケータも変更する必要があるため，今回は簡単のために，17日目同様にすべてのページへのアクセス権をRing 3に付与しました。

今回は，17日目と同様にBSPのみで実装します。16日目にBSP以外のプロセッサAPを起動しましたが，どうやら時間の都合でBSPのみしか扱うことができないようです。基本的にAP固有の初期化は，PAEの有効化，スタックの設定，BSPで設定したGDT，IDTの読み込み，ページテーブルのセット，Local APICタイマの設定だけです。プロセッサ間通信にはシグナリングにはIPIを使い，データは共有メモリ上で行います。注意点は，メモリ管理構造体などは複数のプロセッサから並行して使用できるようになっていないため，適宜ロックをかけることくらいです。後日，アドベントカレンダー外で扱うかもしれません（気が向いたら）。

まず，タスクスイッチを行うために，タスクのコンテキスト情報を定義します。今回はページテーブルは共有なので，以下のようにスタックフレームとTSSのSP0，ユーザスタック，カーネルスタックを定義します。

struct arch_task {
    /* Restart point (stackframe) */
    struct stackframe64 *rp;
    /* SP0 for TSS */
    uint64_t sp0;
    /* User stack */
    void *ustack;
    /* Kernel stack */
    void *kstack;
} __attribute__ ((packed));

このタスクを切り替えるために，プロセッサに現在実行中のタスクとタスクスイッチで切り替えられる次のタスクを以下の構造体で保持します。cur_taskが現在実行中のタスク，next_taskが次に切り替えられるタスクです。

struct arch_cpu_data {
    struct arch_task *cur_task;
    struct arch_task *next_task;
} __attribute__ ((packed));

専用のスペースを割り当てた0x00060000-0x0006ffffのグローバル変数領域のうち0x68e00-0x6efffをCPUのタスクスイッチ用に使います。この領域にstruct arch_cpu_dataを置きます（仮想アドレスを使うので，struct arch_cpu_data *cpu = 0xc0068e00;とします）。

今回は以下の3種類のタスクを定義します。簡単のためにグローバル変数を使います。

struct arch_task *taska;
struct arch_task *taskb;
struct arch_task *taski;

この3つのタスクの実態は以下の3つのタスクです。taska (task_a)は22行目にカウントアップし，値を22行目に出力する無限ループです。taskb (task_b)もほぼ同じタスクで，23行目に出力します。taski (task_idle)は実行可能なタスクがない場合にCPUを停止するためにhltするタスクです。今回はhltが呼ばれたことを確認するために，他のタスクと同様に21行目にカウンタを出力します。こちらは，hlt命令でCPUが停止するので，このタスク実行中の 割り込みごとにカウントアップします。

void
task_a(void)
{
    uint16_t *base;
    uint64_t cnt = 0;

    while ( 1 ) {
        base = (uint16_t *)0xc00b8000;
        base += 80 * 22;
        print_hex(base, cnt, 8);
        cnt++;
    }
}

void
task_b(void)
{
    uint16_t *base;
    uint64_t cnt = 0;

    while ( 1 ) {
        base = (uint16_t *)0xc00b8000;
        base += 80 * 23;
        print_hex(base, cnt, 8);
        cnt++;
    }
}

void
task_idle(void)
{
    uint16_t *base;
    uint64_t cnt = 0;

    while ( 1 ) {
        base = (uint16_t *)0xc00b8000;
        base += 80 * 21;
        print_hex(base, cnt, 8);
        cnt++;
        __asm__ __volatile__ ("hlt");
    }
}

これらのタスクは以下のコードで初期化します。kmalloc()も簡易的に実装しました。src/kernel/arch/x86_64/arch.cを参照してください。

static int
_prepare_multitasking(void)
{
    struct arch_cpu_data *cpu;

    /* Task A */
    taska = kmalloc(sizeof(struct arch_task));
    if ( NULL == taska ) {
        return -1;
    }
    taska->kstack = kmalloc(4096);
    if ( NULL == taska->kstack ) {
        return -1;
    }
    taska->ustack = kmalloc(4096);
    if ( NULL == taska->ustack ) {
        return -1;
    }
    taska->rp = taska->kstack + 4096 - 16 - sizeof(struct stackframe64);
    kmemset(taska->rp, 0, sizeof(struct stackframe64));
    taska->sp0 = (uint64_t)taska->kstack + 4096 - 16;
    taska->rp->sp = (uint64_t)taska->ustack + 4096 - 16;
    taska->rp->ip = (uint64_t)task_a;
    taska->rp->cs = GDT_RING3_CODE64_SEL + 3;
    taska->rp->ss = GDT_RING3_DATA64_SEL + 3;
    taska->rp->fs = GDT_RING3_DATA64_SEL + 3;
    taska->rp->gs = GDT_RING3_DATA64_SEL + 3;
    taska->rp->flags = 0x202;
    /* Task B */
    taskb = kmalloc(sizeof(struct arch_task));
    if ( NULL == taskb ) {
        return -1;
    }
    taskb->kstack = kmalloc(4096);
    if ( NULL == taskb->kstack ) {
        return -1;
    }
    taskb->ustack = kmalloc(4096);
    if ( NULL == taskb->ustack ) {
        return -1;
    }
    taskb->rp = taskb->kstack + 4096 - 16 - sizeof(struct stackframe64);
    kmemset(taskb->rp, 0, sizeof(struct stackframe64));
    taskb->sp0 = (uint64_t)taskb->kstack + 4096 - 16;
    taskb->rp->sp = (uint64_t)taskb->ustack + 4096 - 16;
    taskb->rp->ip = (uint64_t)task_b;
    taskb->rp->cs = GDT_RING3_CODE64_SEL + 3;
    taskb->rp->ss = GDT_RING3_DATA64_SEL + 3;
    taskb->rp->fs = GDT_RING3_DATA64_SEL + 3;
    taskb->rp->gs = GDT_RING3_DATA64_SEL + 3;
    taskb->rp->flags = 0x202;

    /* Idle task */
    taski = kmalloc(sizeof(struct arch_task));
    if ( NULL == taski ) {
        return -1;
    }
    taski->kstack = kmalloc(4096);
    if ( NULL == taski->kstack ) {
        return -1;
    }
    taski->ustack = kmalloc(4096);
    if ( NULL == taski->ustack ) {
        return -1;
    }
    taski->rp = taski->kstack + 4096 - 16 - sizeof(struct stackframe64);
    kmemset(taski->rp, 0, sizeof(struct stackframe64));
    taski->sp0 = (uint64_t)taski->kstack + 4096 - 16;
    taski->rp->sp = (uint64_t)taski->ustack + 4096 - 16;
    taski->rp->ip = (uint64_t)task_idle;
    taski->rp->cs = GDT_RING0_CODE_SEL;
    taski->rp->ss = GDT_RING0_DATA_SEL;
    taski->rp->fs = GDT_RING0_DATA_SEL;
    taski->rp->gs = GDT_RING0_DATA_SEL;
    taski->rp->flags = 0x202;

    /* Set the task A as the initial task */
    cpu = (struct arch_cpu_data *)0xc0068e00;
    cpu->cur_task = NULL;
    cpu->next_task = taska;

    return 0;
}

Task Aについてのみ解説します。

まず，Task Aの構造体にメモリを割り当てます。

    taska = kmalloc(sizeof(struct arch_task));
    if ( NULL == taska ) {
        return -1;
    }

次にカーネルスタックとユーザスタックをそれぞれ4096バイトずつ割り当てます。本来はユーザスタックは溢れたときにpage faultを起こすようなページテーブルエントリをスタックの下に割り当てることが望ましいですが，今回はそのような処理は省略しています。

    taska->kstack = kmalloc(4096);
    if ( NULL == taska->kstack ) {
        return -1;
    }
    taska->ustack = kmalloc(4096);
    if ( NULL == taska->ustack ) {
        return -1;
    }

ここから，タスクの初期状態を定義するためのスタックフレームの設定を行います。スタックフレームはカーネルからユーザランドに戻るときに使用するため，カーネルスタックに配置します。スタックはアドレスの上位から下位に積まれるため，割り当てたスタック領域の上位側のアドレスをセットします。以下のコードでカーネルスタックの最後の16バイトは空白にして，その前の領域にスタックフレームを配置し，スタックフレームをゼロ初期化します。

    taska->rp = taska->kstack + 4096 - 16 - sizeof(struct stackframe64);
    kmemset(taska->rp, 0, sizeof(struct stackframe64));

17日目に設定したように，Ring 3から割り込みや例外が呼ばれたときのスタックとして，カーネルスタックをTSSのSP0にセットします。そのセットするSP0の値を以下のようにこのタスクに割り当てられたカーネルスタックとします。このアドレスはスタックフレームを取り出してタスクが実行されたときのカーネルスタックポインタと同一のものです（同一である必要はありませんが）。

    taska->sp0 = (uint64_t)taska->kstack + 4096 - 16;

以下のコードでスタックフレームの各レジスタを設定します。スタックポインタはユーザスタックの上位アドレス（こちらも16バイト空白を空けています）を設定します。また，プログラムカウンタ（%rip）はtask_a関数にします。これにより，task_a関数がタスクとして実行されます。ただし，スタックにはret命令で戻るポインタがない（つまりcallではなくjmpしたときのような挙動）ため，今回はタスクはwhile (1)でretが呼ばれないようにしています。プロセスなどを実装するときは，プロセスを実行するための初期化ルーチンをこれにセットすることになります。csにはRing 3用の64ビットコードセグメント（セレクタ）を設定します。CPL=3なので，3を足しています。ss, fs, gsにはそれぞれ64ビットデータセグメント（セレクタ）を指定します。こちらも同様にCPL=3となります。flagsには割り込みを許可するために0x202（IF=1）をセットします。

    taska->rp->sp = (uint64_t)taska->ustack + 4096 - 16;
    taska->rp->ip = (uint64_t)task_a;
    taska->rp->cs = GDT_RING3_CODE64_SEL + 3;
    taska->rp->ss = GDT_RING3_DATA64_SEL + 3;
    taska->rp->fs = GDT_RING3_DATA64_SEL + 3;
    taska->rp->gs = GDT_RING3_DATA64_SEL + 3;
    taska->rp->flags = 0x202;

これでタスクの設定が完了しました。

_prepare_multitasking()関数の最後の以下のコードでtaskaをスケジュールします。

    cpu = (struct arch_cpu_data *)0xc0068e00;
    cpu->cur_task = NULL;
    cpu->next_task = taska;

スタックフレームからタスクを再開する処理は17日目に実装したchcsと同様にアセンブリで記述します。以下のコードは複雑に見えますが，処理自体は単純です。struct arch_cpu_data構造体0xc0068e00からnext_taskを取り出し，NULLでなければこのタスクのスタックフレームをスタックポインタに設定し，各種レジスタをpopしiretq命令を呼ぶことでスタックフレームに保存されたタスクを再開します。

/* Restart a task */
_task_restart:
    /* Task base address (struct arch_task *) */
    movq	$0xc0068e00,%rbp
    /* If the next task is not scheduled, immediately restart this task. */
    cmpq	$0,8(%rbp)	/* next_task */
    jz	2f
    movq	8(%rbp),%rax
    /* If the current task is null, then do not need to save anything. */
    cmpq	$0,0(%rbp)	/* cur_task */
    jz	1f
    /* Save the stack pointer (restart point) */
    movq	0(%rbp),%rax
    movq	%rsp,0(%rax)	/* cur_task->rp */
1:
    /* Notify that the current task is switched (to the kernel) */
    movq	0(%rbp),%rdi
    movq	8(%rbp),%rsi
    /* Task switch (set the stack frame of the new task) */
    movq	8(%rbp),%rax	/* next_task */
    movq	%rax,0(%rbp)	/* cur_task */
    movq	0(%rax),%rsp	/* next_task->rp */
    movq	$0,8(%rbp)	/* next_task */
    /* Setup sp0 in TSS */
    movq	0(%rbp),%rax	/* cur_task */
    movq	8(%rax),%rdx	/* cur_task->sp0 */
    movq	$0xc0078000,%rax	/* TSS */
    movq	%rdx,TSS_SP0(%rax)
2:
    /* Pop all registers from the stackframe */
    popw	%gs
    popw	%fs
    popq	%rbp
    popq	%rdi
    popq	%rsi
    popq	%r15
    popq	%r14
    popq	%r13
    popq	%r12
    popq	%r11
    popq	%r10
    popq	%r9
    popq	%r8
    popq	%rdx
    popq	%rcx
    popq	%rbx
    popq	%rax
    iretq

上記コードの12-13行目は，cur_taskが空で無かった場合は，現在のタスクのスタックフレームを保存し，タスクを切り替えられるようにしています。cur_taskがNULLの場合（初期状態）は，現在のタスクのスタックフレームの保存部分が実行されないため，単純にnext_taskを開始する処理になります。つまり，src/kernel/arch/x86_64/arch.cのbsp_start()の最後の以下の処理は，taskaを実行する処理になります。そのため，これより下のコードは実行されません。

    task_restart();

APICタイマ割り込みハンドラを以下のように変更しました。

/* Timer interrupt of Local APIC */
_intr_apic_loc_tmr:
    /* Push all registers to the stackframe */
    pushq	%rax
    pushq	%rbx
    pushq	%rcx
    pushq	%rdx
    pushq	%r8
    pushq	%r9
    pushq	%r10
    pushq	%r11
    pushq	%r12
    pushq	%r13
    pushq	%r14
    pushq	%r15
    pushq	%rsi
    pushq	%rdi
    pushq	%rbp
    pushw	%fs
    pushw	%gs
    /* Call a function */
    call	_ksignal_clock
    /* APIC EOI */
    movq	$MSR_APIC_BASE,%rcx
    rdmsr			/* Read APIC info to [%edx:%eax]; N.B., higer */
                /*  32 bits of %rax and %rdx are cleared */
                /*  bit [35:12]: APIC Base, [11]: EN */
                /*  [10]: EXTD, and [8]:BSP */
    shlq	$32,%rdx
    addq	%rax,%rdx
    andq	$0xfffffffffffff000,%rdx        /* APIC Base */
    movl	$0,0x0b0(%rdx)       /* EOI */
    jmp	_task_restart

前半はスタックフレームに各種レジスタを保存しています。その後に，C言語で実装したksignal_clockを呼び出し、APICのEnd-of-Interruptをシグナルします。最後に_task_restartを呼ぶことで，先ほど実装したnext_taskで指定されたタスクへの切り替えを行います。

今回は昨日説明したラウンドロビンスケジューラをハードコーディングして実装します。APICタイマの割り込みハンドラを以下のように実装しました。

void
ksignal_clock(void)
{
    uint16_t *base;
    static uint64_t cnt = 0;

    base = (uint16_t *)0xc00b8000;
    base += 80 * 24;
    print_hex(base, cnt / 100, 8);
    cnt++;

    /* Schedule next task */
    struct arch_cpu_data *cpu;
    cpu = (struct arch_cpu_data *)0xc0068e00;
    if ( cpu->cur_task == taska ) {
        cpu->next_task = taskb;
    } else if ( cpu->cur_task == taskb ) {
        cpu->next_task = taski;
    } else {
        cpu->next_task = taska;
    }
}

以下の部分がスケジューラのハードコーディングです。つまり現在のタスクがtaskaであればtaskb，taskbであればtaski，taskiであればtaskaをスケジュールします。

if ( cpu->cur_task == taska ) {
    cpu->next_task = taskb;
} else if ( cpu->cur_task == taskb ) {
    cpu->next_task = taski;
} else {
    cpu->next_task = taska;
}

このコードをdocker-compose run qemuで実行すると以下のように画面に表示されると思います。

 Welcome to advos (64-bit)!                                                     !
 000000003ba281a0                                                               !
 00000000c0224240                                                               !
 00000000c0224280                                                               !
 00000000c0224280                                                               !
 # of CPU cores = 0x00000008                                                    !
 Base             Length           Domain                                       !
 0000000000000000 00000000000a0000 0000000000000000
 0000000000100000 000000001ff00000 0000000000000000
 0000000020000000 0000000020000000 0000000000000001
 ----------
 System memory map; # of entries = 0x0006
 Base             Length           Type     Attribute
 0000000000000000 000000000009fc00 00000001 00000001
 000000000009fc00 0000000000000400 00000002 00000001
 00000000000f0000 0000000000010000 00000002 00000001
 0000000000100000 000000003fedf000 00000001 00000001
 000000003ffdf000 0000000000021000 00000002 00000001
 00000000fffc0000 0000000000040000 00000002 00000001


 000000000000006d
 00000000000a0cf5
 00000000000ad036
 0000000000000003        

この下の4行のカウンタが上からそれぞれ，

• task_idleでカウントアップされるカウンタ（毎回hltが呼ばれるため，このタスクに切り替わる度にカウントアップされる）
• task_aの無限ループでカウントアップされるカウンタ
• task_bの無限ループでカウントアップされるカウンタ
• 昨日のLocal APICタイマのカウンタ（100 Hzのタイマのカウンタを100で割っているため，約1秒に1回カウントアップされる） となります。真ん中の2行が同時にカウントアップされているように見え，正しくマルチタスキングが実装できていることがわかると思います。

24日間でできるだけことをしました。OSの基礎的な部分は実装できたと思いますが，システムコールとプロセス，ドライバが扱えませんでした。あと3-4日足せばできると思うので，4週間あればOSの基本的な部分は実装できると思います。大学の講義だと通期26回あれば実装できそうです。仕事終わりの時間で文章を書きながら実装していたので，あまり時間が取れなかったので，要望があれば，不足している解説や背景，関連技術などを追加して電子書籍（自費出版的なもの）か何かにでもまとめようと思います。そんな要望はないと思いますが。もし要望があれば，教えてください。

振り返ってみると，ブートローダとメモリ管理に大半を割いてしまいました。OSについては，理論やアルゴリズムは座学で理解していても，いざ実装してみるとハードウェアの仕様を調べたり，実装テクニックが必要であったりします。今日実装したタスクスイッチも，スタックフレームなどは座学では決して出てこないと思います。今回扱えなかったシステムコールやマルチコアのスタック，プロセスの取り扱いなどは，理論では抽象化されて簡単に扱われますが，実装（例えば，forkシステムコールでのメモリのcopy-on-writeの実装など）は非常に複雑になってきます。そもそもforkは自力で実装してみると3日くらいかかると思います。来年のアドベントカレンダーで続きをしようかな……