panda's tech note

Advent Calendar 2018: advos

Day 23: 非特権タスクとマルチタスキング（その1）

今日は，17日目に実行したRing 3で実行するタスクを複数用意し，マルチタスキングを実装します。

マルチタスキングとスケジューラ

OSの一つの機能として，複数のタスクを同時に実行できるようにするマルチタスキングです。正確には同時に実行しているわけではなく，CPU，メモリ，およびその他の計算機資源を時空間で分割することで，複数のタスクが同時に実行しているように見せかけています。メモリは（スワップ機能を無視すれば）空間的に分割し，資源を複数のタスクで共有します。これは主に仮想メモリの機能で効率的に実現されます。一方，CPUは時間で計算機資源を分割します。近年ではマルチコアプロセッサが普通になったので，空間的にも分割して実行します。このCPUを時空間で分割し，複数のタスクを実行することを スケジューリング と呼びます。メモリの動的割り当てについてもスケジューリングという用語を使うことがあります。CPUとメモリの共有のイメージは下図のようになります。同じ色が同一のタスクについてその資源が使われていることを表します。

Resource Sharing

マルチタスキングの実現方法は大きく分けて以下の2つがあります。

  • Preemptive multitasking: 外部からの割り込み（preemption）でタスクを切り替えるアプローチ
  • Non-preemptive multitasking (Cooperative multitasking): 各タスクがタスク切り替えのタイミングを制御するアプローチ

今回は通常の汎用OSと同様に，Preemptive multitaskingを実装します。

スケジューリングを効率的に行うために様々なスケジューリングアルゴリズムが研究開発されてきました。CPUのスケジューリングは，以下のようなものがあります。

  • バッチシステム: タスクのスループットを最大化し，CPUを最も効率的に使用するシステム
    • First-Come First-Serve: 最初に来たタスクから順に処理するアルゴリズム
    • Shortest Job First: 最も短い（と予測される）タスクから順に処理するアルゴリズム
    • Shortest Remaining Time Next: Shortest Job FirstのPreemptive multitaskingバージョン。Preemption後，最も終了までにかかる時間が短いタスクから再開させるアルゴリズム
  • インタラクティブシステム: 汎用OSのように入出力に応じて複数のタスクや周辺機器が相互に作用するシステム
    • Round-Robin Scheduling: タスクを順に実行するアルゴリズム
    • Priority Scheduling: タスクに優先度を付けて優先度の高いアクティブなタスクから順に実行するアルゴリズム
    • Priority Scheduling w/ Multiple Queue (different quantum): 優先度ごとにタスクキューを用意し，優先度の高いキューから実行するアルゴリズム
    • Shortest Process Next: タスクの実行時間が短い（と予測される）タスクを次に実行するアルゴリズム
    • Guaranteed Scheduling: CPUの利用時間をモニタリングして，fairnessを公平に保つアルゴリズム
    • Lottery Scheduling: 宝くじスケジューリングと呼ばれるアルゴリズムで，各タスクに宝くじ（チケット）を割り当て，スケジューラがランダムに番号を選び，対応するタスクをスケジューリングするアルゴリズム
    • Fair-Share Scheduling: Round-Robinスケジューリングでquantum（クオンタム: preemptionまでの時間）を，計算機資源の割り当てが公平になるように割り当てるアルゴリズム
  • リアルタイムシステム: 実行時間が保証される（ハードリアルタイム），または実行時間のデッドラインが保証ではないが設定される（ソフトリアルタイム）システム。通常，実行時間が短く，予測可能なタスクであるため，外部割り込みなどで呼び出されて実行される

APICタイマ

Preemptive multitaskingを実現するために，preemptionの割り込みとしてAPICタイマを使います。APICは各論理コアごとに存在する（Local APIC）ので，各コアで独立したタイマを持つことができます。タイマ割り込みの周期はOSやディストリビューション，バージョンによって異なりますが，今回は100 Hz（10ms）にしたいと思います。

バスクロックの計測

ここで問題になるのが，5日目で説明したPICのタイマが1周する周期は1193181.67 Hzで固定でしたが，APICはCPUモデルごとに異なることです。そのため，最初にAPICタイマの周波数（バスクロック・Bus frequency）を測る必要があります。14日目に使用したACPIタイマを使って，この周波数を計測します。計測するために，タイマのカウンタをセットし，カウントダウンを開始する関数lapic_set_timer()とカウントダウンを停止し，現在のカウンタを読み出すlapic_stop_and_read_timer()関数を以下のように定義します。lapic_set_timer()の第一引数は初期カウンタです。第二引数は，Local APICのカウンタが32ビットであるため，バスクロックが非常に高い場合，計測時間中にカウンタが0になってしまう可能性があるため，カウンタの減算を数倍遅くします。後述する計測実装で指定しているAPIC_TMRDIV_X16を指定した場合は，16クロックに1カウント減算されます。

/*
 * lapic_set_timer -- set timer
 */
void
lapic_set_timer(uint32_t value, int divide)
{
    uint64_t apic_base;

    apic_base = lapic_base_addr();

    /* Disable timer */
    mfwr32(apic_base + APIC_LVT_TMR, APIC_LVT_DISABLE);

    /* Set divide configuration of the timer */
    mfwr32(apic_base + APIC_TMRDIV, divide);

    /* Vector: lvt[18:17] = 00 : oneshot */
    mfwr32(apic_base + APIC_LVT_TMR, 0x0);

    /* Set initial counter and start the timer */
    mfwr32(apic_base + APIC_INITTMR, value);
}

/*
 * lapic_stop_and_read_timer -- stop and read the timer counter
 */
uint64_t
lapic_stop_and_read_timer(void)
{
    uint64_t apic_base;
    uint32_t t;

    apic_base = lapic_base_addr();

    /* Disable current timer */
    mfwr32(apic_base + APIC_LVT_TMR, APIC_LVT_DISABLE);

    /* Read current timer */
    t = mfrd32(apic_base + APIC_CURTMR);

    return t;
}

この関数とACPIタイマを使って，以下のようにバスクロックを推定するコードを書きました。上述の通り，計測したカウンタはバスクロックの16分の1の速度で減算されているため，最後に<< 4で16倍しています。

static uint64_t
_estimate_bus_freq(acpi_t *acpi)
{
    uint32_t t0;
    uint32_t t1;
    uint32_t probe;
    uint64_t ret;

    /* Start timer */
    t0 = 0xffffffff;
    lapic_set_timer(0xffffffff, APIC_TMRDIV_X16);

    /* Set probe timer (100 ms) */
    probe = 100000;

    /* Sleep probing time */
    acpi_busy_usleep(acpi, probe);

    t1 = lapic_stop_and_read_timer();

    /* Calculate the APIC bus frequency */
    ret = (uint64_t)(t0 - t1) << 4;
    ret = ret * 1000000 / probe;

    return ret;
}

関数呼び出しのオーバーヘッドなどもあり，若干の誤差はありますが，おおよそのバスクロックを測ることができます。MacBook Pro上のQEMUで実行したところ，1000575520 Hzでほぼ1 GHzとなりました。

タイマの設定

Local APICのタイマを設定します。タイマのカウンタ初期値をバスクロック/設定周波数に設定することで，設定周波数ごとにカウンタが0になり，耐回り込みが割り込みベクターvecに入ります。今回は割り込みベクタはIV_LOC_TMR=0x40に設定します。

void
lapic_start_timer(uint64_t busfreq, uint64_t freq, uint8_t vec)
{
    uint64_t apic_base;

    apic_base = lapic_base_addr();

    /* Set counter */
    mfwr32(apic_base + APIC_LVT_TMR, APIC_LVT_PERIODIC | (uint32_t)vec);
    mfwr32(apic_base + APIC_TMRDIV, APIC_TMRDIV_X16);
    mfwr32(apic_base + APIC_INITTMR, (busfreq >> 4) / freq);
}

割り込みハンドラの設定

Local APICタイマ割り込みハンドラとしてsrc/kernel/arch/x86_64/asm.Sに_intr_apic_loc_tmrを以下のように実装しました。割り込みハンドラからはksignal_clock()関数を呼ぶようにしています。

/* 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 */
    /* 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

これを16日目に実装したIDTの割り込みゲート（割り込みベクタ0x40）にセットします。

    idt_setup_intr_gate(IV_LOC_TMR, intr_apic_loc_tmr);

以下のコードでタイマの実行が始まります。

    busfreq = _estimate_bus_freq(acpi);
    lapic_start_timer(busfreq, HZ, IV_LOC_TMR);

このタイマを検証するために，割り込みハンドラから呼び出される関数ksignal_clock()を以下のように実装しました。タイマは約100 Hzで割り込みを行うため，ここで表示しているcnt / 100は約1秒に1カウントずつカウントアップされて画面最下部に表示されます。

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++;
}

ここまでのコードにタグday23_1を付けましたので，以下のコードを参照してください。

今日のまとめ

今日はマルチタスキングの説明とPreemptive Multitaskingを実装する上で必要不可欠なLocal APICタイマの設定まで行いました。明日はマルチタスキングを実装します。