執筆者 : 高橋浩和

はじめに

今回はタスクを協調動作させるための仕組みとして、セマフォによる同期機構を実現します。

セマフォ

今回はバイナリセマフォを実装します*1。

排他制御したい資源*2に対応したセマフォを定義します。セマフォを取得したタスクのみ、そのセマフォに対応付けられた資源を操作可能という決まりを導入します。これによりセマフォを取得したタスクは、独占的に資源を操作することができます。セマフォの取得に失敗したタスクは、セマフォが解放されるまで待つ必要があります。

f:id:takava:20211108122340j:plain

セマフォ管理データ構造

セマフォ状態を管理するデータ構造SemaphoreControlを用意します。 owner_taskメンバは、このセマフォを取得しているタスクを記録します。取得されていない場合には、SEM_AVAILABLEを代入しておくこととします。

struct SemaphoreControl {
    TaskIdType owner_task;
};

タスクを管理するデータ構造TaskControlのtarget_semメンバには取得を試みているセマフォを記録します。セマフォ取得要求時に、他のタスクがセマフォを取得済みであった場合に利用します。セマフォ取得待ちしていないときは、NO_SEMを代入しておくこととします。

struct TaskControl {
        :
    SemIdType target_sem;
        :
};

f:id:takava:20211108162440j:plain

セマフォ取得とセマフォ解放

セマフォ取得を要求する関数AcquireSemaphoreを用意します。

AcquireSemaphore関数は、セマフォが解放状態にある場合、セマフォを取得します。SemaphoreControlオブジェクトのowner_taskメンバがSEM_AVAILABLEの場合、Sempahoreオブジェクトのowner_taskメンバにセマフォ取得を要求したタスクを登録します。

セマフォが他のタスクに取得されている場合、セマフォ取得を要求したタスクのTaskControlオブジェクトのtarget_semメンバに取得を試みるセマフォを登録し、タスクを待機状態BLOCKEDに変更します(_TaskBlock関数)。

セマフォが解放されると、セマフォ取得待ちで待機していたタスクは_TaskBlock関数から復帰してきます。動作を再開したタスクはセマフォの解放状態を再確認し、解放状態であればセマフォを取得します。セマフォ取得待ち状態から同時に複数のタスクが動作を再開することがあるため、セマフォの解放状態の再確認は必須です。

void AcquireSemaphore(SemIdType sem)
{
    DisableInt();
    while (SemaphoreControl[sem].owner_task != SEM_AVAILABLE) {
        TaskControl[CurrentTask].target_sem = sem;
        _TaskBlock();
    }
    SemaphoreControl[sem].owner_task = CurrentTask;

    EnableInt();
}

void _TaskBlock(void)
{
    TaskControl[CurrentTask].state = BLOCKED;
    _Schedule();
}

セマフォが即時取得できなかった場合にはエラーにするセマフォ取得関数TryToAcquireSemaphore関数も用意します。 AcquireSemaphore関数と異なり、セマフォの解放を待ち合わせません。

int TryToAcquireSemaphore(SemIdType sem)
{
    DisableInt();
    if (SemaphoreControl[sem].owner_task == SEM_AVAILABLE) {
        SemaphoreControl[sem].owner_task = CurrentTask;
    }
    EnableInt();
    return SemaphoreControl[sem].owner_task == CurrentTask;
}

ReleaseSemaphore関数は、セマフォを解放状態にします。SemaphoreControlオブジェクトのowner_taskメンバにSEM_AVAILABLEを代入します。

このセマフォの取得待ちをしているタスクがいる場合、そのタスクのセマフォ取得待ち状態を解除します。 TaskControlオブジェクトのstateメンバがBLOCKEDかつtarget_semメンバが今解放したセマフォを指している場合、 `target_semメンバをNO_SEMでクリアし、_TaskUnblock関数を用いタスクをREADY状態にします。

void ReleaseSemaphore(SemIdType sem)
{
    TaskIdType task;
    DisableInt();
    SemaphoreControl[sem].owner_task = SEM_AVAILABLE;
    for (task = 0; task < NUMBER_OF_TASKS; task++) {
        if (TaskControl[task].state == BLOCKED && TaskControl[task].target_sem == sem) {
            TaskControl[task].target_sem = NO_SEM;
            TaskControl[task].expire = 0;
            _TaskUnblock(task);
        }
    }
    EnableInt();
}

void _TaskUnblock(TaskIdType task)
{
    TaskControl[task].state = READY;
    _Schedule();
}

AcquireSemaphore関数と時限待ちを組み合わせ、指定時間内にセマフォを確保できなかった時にはエラー終了するように拡張することも考えられます。しかし、今回は実装を単純にするため、時限待ち機能は組み込まないことにします。

食事をする哲学者

食事をする哲学者の問題と呼ばれる並列処理の有名な問題があります。今回はこの問題をセマフォを用いて実現します。

ja.wikipedia.org

哲学者1人にタスク1つを割り当てます。
フォーク1本にセマフォ1つを割り当てます。
丸いテーブルの周りに座った哲学者それぞれの間にフォーク1本を置きます。
両手にフォークを握った哲学者のみが食事をすることができます。
フォークを取れなかった哲学者は瞑想しつつ2本のフォークが取れるのを待ちます。

f:id:takava:20211108122457j:plain

実装してみる

哲学者を表すタスク5つとフォークを表すセマフォ5つを定義します。

struct TaskControl {
    enum { READY, BLOCKED} state;
    void (*entry)(void);
    long time_slice;
    long remaining_time;
    int expire;
    SemIdType target_sem;
    unsigned long sp;
    unsigned long task_stack[STACKSIZE];
} TaskControl[NUMBER_OF_TASKS] = {
    {.entry = Task1, .state = READY, .time_slice = 2},
    {.entry = Task2, .state = READY, .time_slice = 4},
    {.entry = Task3, .state = READY, .time_slice = 1},
    {.entry = Task4, .state = READY, .time_slice = 3},
    {.entry = Task5, .state = READY, .time_slice = 1},
    {.entry = Idle,  .state = READY,  .time_slice = 1},
};

#define SEM_AVAILABLE TASKIDLE

struct SemaphoreControl {
    TaskIdType owner_task;
} SemaphoreControl[NUMBER_OF_SEMS] = {
    {.owner_task = SEM_AVAILABLE},
    {.owner_task = SEM_AVAILABLE},
    {.owner_task = SEM_AVAILABLE},
    {.owner_task = SEM_AVAILABLE},
    {.owner_task = SEM_AVAILABLE},
};

哲学者タスクはそれぞれ左右2本のフォークの取得を試み(GetForks関数)、取得に失敗した場合はしばらく瞑想し(PhilosopherMeditate関数)、再度フォークの取得を試みます。フォークの取得に成功したときは食事を行ない(PhilosopherEat関数)、その後フォークを解放します(ReleaseForks関数)。

void TaskJob(const TaskIdType task, const SemIdType fork_left, const SemIdType fork_right)
{
    char taskname[] = "Task?";
    taskname[4] = '1' + task;

    while (1) {
        while ( !GetForks(fork_left, fork_right) ) {
            print_message(taskname);
            PhilosopherMeditate();
        }
        print_message(taskname);
        PhilosopherEat();
        ReleaseForks(fork_left, fork_right);
    }
}

void Task1(void)
{
    TaskJob(TASK1, SEM1, SEM2);
}

void Task2(void)
{
    TaskJob(TASK2, SEM2, SEM3);
}

void Task3(void)
{
    TaskJob(TASK3, SEM3, SEM4);
}

void Task4(void)
{
    TaskJob(TASK4, SEM4, SEM5);
}

void Task5(void)
{
    TaskJob(TASK5, SEM5, SEM1);
}

哲学者タスクがフォークを取る関数GetForksは、左手のフォークfork_leftを取得(AcquireSemaphore関数)後に、TryToAcquireSemaphore関数で右手のフォークfork_rightの取得を試みます。右手のフォークの取得に失敗した場合は左手のフォークも解放し、GetForks関数をエラー終了させます。

右手のフォークもAcquireSemaphore関数で取得する実装は、デッドロックの可能性があるため誤りです。全ての哲学者タスクが左手のフォークを取得した状態で、全哲学者タスクが右手のフォークを取得しようとする状態になる可能性があります。しかし、取得しようとしているフォークを解放してくれる哲学者タスクは存在しません。

f:id:takava:20211108122606j:plain

int GetForks(SemIdType fork_left, SemIdType fork_right)
{
    AcquireSemaphore(fork_left);
    if (TryToAcquireSemaphore(fork_right)) {
        return TRUE;
    }
    ReleaseSemaphore(fork_left);
    return FALSE;
}

void ReleaseForks(SemIdType fork_left, SemIdType fork_right)
{
    ReleaseSemaphore(fork_left);
    ReleaseSemaphore(fork_right);
}

瞑想する関数PhilosopherMeditateと食事する関数PhilosopherEatは適当な時間時限待ちする関数として実現することにします。関数myrandomは疑似乱数を生成する関数です。

void PhilosopherMeditate()
{
    print_message("    Meditating\n");
    Snooze(myrandom() % 2 + 1);
}

void PhilosopherEat()
{
    print_message("    Eating\n");
    spend_time();
    Snooze(myrandom() % 5 + 1);
}

unsigned int myrandom(void)
{
    static unsigned long long x = 11;
    x = (48271 * x) % 2147483647;
    return (unsigned int)x;
}

動かしてみよう

5つのタスクが食事と瞑想を繰り返しながら動作していることが分かります。隣り合うタスクが同時に食事を取る状態にならないことも分かります。

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

最後に

今回の記事で、当初の目的であったOS実装に必要となる基本知識の説明は一区切りつきました。これらは基本的ではありますが、全てのOS実装で必要とされる非常に重要な知識です。これらの知識は、OSに限らずRISC-V CPUを直接操作するプログラムを記述する時にも役立ちます。

今後の連載は未定ですが、少し時間をおいて次のようなトピックについての記事を追加することも考えています。

マルチコア
実行モード切り替え
メモリ保護

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

おまけ

RISC-Vアーキテクチャを通してコンピュータアーキテクチャの理解を深めることのできる本があります。かなり良くできた本なので、より深く学びたい方にはお勧めです。

Computer Architecture: A Quantitative Approach Sixth Edition (日本語翻訳版: コンピュータアーキテクチャ[第6版]定量的アプローチ)
Computer Organization and Design RISC-V Edition

もともとはCPU設計の解説にMIPSアーキテクチャを題材として使っていましたが、現在はRISC-Vアーキクチャベースに書き直されています。なぜこの命令セット(ISA)が定義されたのか？CPUの内部はどのように動作しているのか？などの疑問に答えてくれます。

*1:カウンティングセマフォというものも存在します。バイナリセマフォでは時に1つのタスクのみセマフォを取得することができますが、カウンティングセマフォでは指定された数のタスクが同時にセマフォを取得することが可能です。

*2:資源はメモリ上でのデータ構造のこともありますし、デバイスであることもあります。

VA Linux エンジニアブログ

RISC-V OSを作ろう (6) ～セマフォ