---
# System prepended metadata

title: Uチュートリアル
tags: [ghOSt]

---

<style>
    
    u {
        text-decoration-color: gray;
        text-decoration-style: wavy; /* 波線 */
    }
    
</style>

# 必須条件
ghOStの環境構築は完了しているものとします。

# ghost-userspace の概観
[ghost-userspace](https://github.com/google/ghost-userspace) は [ghost-kernel](https://github.com/google/ghost-kernel) 上で動くアプリケーションを作成するためのフレームワークである。すでにリポジトリの中には ghOSt 版 CFS スケジューラなどが実装されていて、簡単に試すこともできる。

各ディレクトリの説明などはリポジトリの README.md に書かれている。

libディレクトリには、ghOStアプリケーションを作成するためのライブラリが実装されており、簡単に agent を実装したり、ghOStスレッドを生成するプログラムを実装したりできるようになっている。

# ビルドシステム（bazel）
ghost-userspace には Google が開発した bazel というビルドシステムが使われている（説明略）。

# agent の実行
環境構築でビルドが済んでいれば bazel-bin/ ディレクトリが作成され、その配下に agent 用のバイナリが生成されているはずである。FIFO スケジューラは bazel-bin/fifo_per_cpu_agent という名前でビルドされているので、以下のように実行すると FIFO スケジューラを実行することができる。
 
```bash
$ sudo bazel-bin/fifo_per_cpu_agent --ghost_cpus=0-1
Initializing...
Initialization complete, ghOSt active.
^C
Done!
```
* スケジューラの実行には root 権限が必要なので sudo をつけて実行する。
* スケジューラは Ctrl+C で実行を終了できる。
* \-\-ghost-cpus というコマンドライン引数は、このスケジューラが管理するCPUの範囲を定めるものである（agent によって引数の種類は変わる）。今回は CPU0 と CPU1 を管理している。

起動したスケジューラでスレッドを管理するには、スレッドのスケジューリングポリシーが SCHED_GHOST である必要がある（[ポリシーをghOStに変更する方法](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FS1aXXxTZa#tasks)）。リポジトリには、GHOSTスレッドとして重い処理を行うプログラムがあらかじめ用意されているので（[simple_exp](https://github.com/google/ghost-userspace/blob/main/tests/simple_exp.cc)）、それを実行してみるとよい。

bazel-bin/simple_exp を別のターミナルで実行する。
```c
$ bazel-bin/simple_exp
```
simple_exp は起動したagentで管理されているため、CPU0かCPU1でのみ実行されているのを確認することができる。

![image](https://hackmd.io/_uploads/HyZn6Uim6.png)








# ghOStスレッドの生成プログラム
ghOSt スレッドを生成するには、①++自スレッドを特定の enclave の管理下に移動させるか++、②++他スレッドによって enclave の管理下に移動させられるか++、のどちらかの方法で**明示的に**行う必要がある。

まず、①の方法で ghOSt スレッドを生成する方法を見ていく。
ライブラリの [GhostThread](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/ghost.h#L523-L595) クラスを利用すると、新しく ghOSt スレッドとしてスレッドを生成することができる。
```cpp
#include "lib/ghost.h"
using namespace ghost;

int main() {
  // コンストラクタの第1引数には、スケジューリングポリシーを指定する。
  // ここで指定できるのは、以下の2つである。
  //     - GhostThread::KernelScheduler::kCfs
  //     - GhostThread::KernelScheduler::kGhost
  // 第2引数には、新しいスレッドとして実行したい関数を指定する。
  GhostThread t(GhostThread::KernelScheduler::kGhost, [] {   
    system("/usr/bin/bash");
  });

  // 上記のスレッドが終了するまで待機（通常の thread と同じ）
  t.Join();
}
```
:::success
これが①の方法であるのは GhostThread の実装を見るとわかる。
新しく生成したスレッドが自主的に自身のスケジューリングポリシーを ghOSt に変更する、といった処理が行われているのだ。
:::

上記のプログラムをビルドするルールを BUILD ファイルに記述する。
今回は tests/ghost_bash.cc という名前で上記のプログラムを実装したので、以下の様に記述した。
```bazel
cc_binary(
    name = "ghost_bash",
    srcs = [
        "tests/ghost_bash.cc",
    ],
    copts = compiler_flags,
    deps = [
        ":ghost",
    ],
)
```
コマンドラインからビルドし、実行する。
```bash
$ bazel build -c opt ghost_bash
$ bazel-bin/ghost_bash
$ # ⇠このbashはghOStスレッドとして実行されている！
```

②の方法についても見てみる。
今開いているシェルをghOStスレッドにするには、以下のコマンドで簡単に行うことができる。このコマンドがやっているのは、シェルの pid を enclave ディレクトリの tasks ファイルに書き込んでいるだけである。
```bash
$ echo $$ > /sys/fs/ghost/enclave_1/tasks
$ # この時点でghOStで管理されるbashになっている
```

以上が ghOSt スレッドとして bash を起動する方法である。**ghOSt ポリシーは fork 等で子に継承される**ため、<u>この bash で実行したコマンドは全て ghOSt ポリシーを受け継ぐことになる！</u>

対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/6ded7985242f54d9b8b5adce376d4916e0a736e9)

# Per-CPUスケジューラの実装
今度は、スケジューラの実装方法を見ていく。段階的に実装していくことで理解しやすいように心がけた。各実装についての説明は適宜加えるが、諸クラスの使い方などについては[libディレクトリ](/TRsr5r0PQKWgyIPnGqUw7g)を参照してほしい。

## agentプロセスの起動のみを行うプログラム
スケジューラはCPUごとに1つのagentスレッドを生成して管理する。agentスレッドはスケジューリングの決定を行う大切なスレッドなので、ビジー状態になったりスリープしたりしてはならない。agentスレッドが他の通常のスレッドと同じアドレス空間を共有していると、そのようなことが起きてしまう可能性があるため、<u>agentスレッドのみが動作する専用のプロセスを作成し、そこでagentスレッドを隔離することになっている</u>。この仕組みは[AgentProcess](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L520-L587)クラスに実装されている。

AgentProcessはagentスレッド用の新しいプロセスを作成するクラスである。元のプロセスとはRPCによって通信できるようになっている。

ここでは、++①AgentProcessによって新しくagent用のプロセスが作成されること++、++②元のプロセスとRPCによって通信ができること++、++③正常に終了できること++（agentプロセスが終了せずに残ったままになる、といったことが起きない）、を確認する。
:::warning
これらはAgentProcessクラスに実装されている機能です。詳しくは[AgentProcess](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#AgentProcess)の説明を参照してください。
:::

実装に移っていく。まず、新しいスケジューラのためのディレクトリschedulers/tutorial/per_cpu/を作成する。以降のソースコードは、このディレクトリに作成する。このような設計は、[FIFOスケジューラの実装](https://github.com/google/ghost-userspace/tree/main/schedulers/fifo)を参考にしている。

まずは、tut_agent.ccというファイルを以下のように作成する。
　AgentProcessクラスのインスタンスを作成するには [AgentConfig](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/enclave.h#L41-L62) クラスのインスタンスが必要である。マシントポロジーの情報や管理するCPUのリストを指定する必要がある（今回は CPU0, CPU1, CPU4 を管理するスケジューラを作ることにする）。
```cpp
#include <string>
#include <vector>

#include "lib/agent.h"
#include "lib/enclave.h"
#include "lib/topology.h"

#include "schedulers/tutorial/per_cpu/tut_scheduler.h"

using namespace ghost;


int main() {
  // ① agent用プロセスを生成
  AgentConfig config;
  config.topology_ = MachineTopology();
  config.cpus_ = MachineTopology()->ParseCpuStr("0-1,4"); // hard coding
  auto uap = new AgentProcess<TutorialFullAgent, AgentConfig>(config);

  // ② 対話形式のUIで、RPCを通して手元のプロセスとAgent用プロセスの間で通信を行う。
  while (1) {
    std::string s;
    std::cout << "> ";
    std::cin >> s;
    if (s == "q" || s == "quit")
      break;
    try {
      // RPCは数値によって呼び出す処理を指定する。
      int req = std::stoi(s);
      long ret = uap->Rpc(req);
      std::cout << "RpcResponse: " << ret << std::endl;
    } catch (...) {
      std::cerr << "[ Error ] Invalid operation: " << s << std::endl;
    }
  }
  
  // ③ 終了。デストラクタを呼ぶ。
  delete uap;
  std::cout << "\nDone!\n";
}
```

次に、tut_scheduler.hというファイルを以下のように作成する。
　とりあえずは[FullAgent](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L424-L506)の最小実装を用意するだけでいい。FullAgentは抽象クラスなので、いくつかの純粋仮想関数をoverrideした具象クラスが必要。
```cpp
#pragma once

#include "lib/agent.h"


namespace ghost {

class TutorialFullAgent : public FullAgent<> {
public:
  TutorialFullAgent(AgentConfig &config) : FullAgent(config) {
    // not implemented
  }
  
  // RPCで呼び出されるAgentプロセス側の実装
  void RpcHandler(int64_t req, const AgentRpcArgs& args,
                  AgentRpcResponse& response) override { 
    // not implemented
  }
  
  // 純粋仮想関数なので実装が必要。
  std::unique_ptr<Agent> MakeAgent(const Cpu& cpu) override {
    // not implemented
    return nullptr;
  }
};

}; // namespace ghost
```
現段階では必要ないが、tut_scheduler.hの関数本体などを実装するためのソースファイルtut_scheduler.ccも以下のように作成しておく。
```cpp
#include "schedulers/tutorial/per_cpu/tut_scheduler.h"
```

最後に、ルートのBUILDファイルに以下の記述を追加する。
```bazel
cc_binary(
    name = "tutorial_per_cpu_agent",
    srcs = [
        "schedulers/tutorial/per_cpu/tut_agent.cc",
        "schedulers/tutorial/per_cpu/tut_scheduler.cc",
        "schedulers/tutorial/per_cpu/tut_scheduler.h",
    ],
    copts = compiler_flags,
    deps = [
        ":agent",
        ":topology",
    ],
)
```
コマンドラインでビルドする。
```
$ bazel build tutorial_per_cpu_agent
```
ビルド成果物を実行すると以下のように対話型のシェルが起動する。
入力したコマンドはagentプロセスへIPCによって伝達される。
```
$ sudo bazel-bin/tutorial_per_cpu_agent
> 0
RpcResponse: -19
> q

Done!
$
```

数値を指定すれば、その番号のRPCが呼び出される。そのすぐ後にRPCの結果が出力される。-19とあるのは、enclaveがまだオフラインのため-**ENODEV**が返されたことを意味している（詳しくは[agentプロセス側のRPCハンドラの実装を参照](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#%E2%98%85-Rpc)）。

qを送信すればプロセスは完全に終了する。

:::warning
上で実行したFIFOスケジューラとは挙動が大きく違うように見えるが、今回は、RPCの存在を分かりやすくしたかったため、シェルのように実装してみた。**FIFOの実装などでは「Ctrl+C」を検知するとプロセスを終了する**ように要請する、といった具合でRPCは使われている。

また、スケジューラが管理するCPUはコマンドラインで指定できたほうが便利だが、めんどくさかったのでハードコーディングした。
:::

さて、少しカーネルの方を見てみる。今作成したagentもどきを実行中は、システムに /sys/fs/ghost/enclave_1というディレクトリが作成されているはずである。また、qコマンドにより正常に終了するとディレクトリも削除されており、きちんと後片付けができていることも確認できる。

ここで作成された/sys/fs/ghost/enclave_1ディレクトリはghOStFSと呼ばれる疑似ファイルシステムのディレクトリであり、<u>このディレクトリ配下の疑似ファイルに読み書きを行うことで、ghOStカーネルに命令を送ることができる</u>ようになっている。詳しくは[ghOStFS](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FS1aXXxTZa)を参照。

ここで実装した処理のイメージ図を以下に示す。
![CC8FEDD3-5F52-42B8-A471-EF3E6972D36D](https://hackmd.io/_uploads/r1MqPMx8a.jpg)











対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/d9aab86a6a393547a3aee28c04fe38c7c91afb9a)

### まとめ
* この実装では、agentスレッド用のプロセスを作っただけ
* agentスレッドは何1つ生成していない
* RPCによって元のプロセスとagentプロセスの間で通信できる 

次の実装では、agentスレッドを生成するところまで（ただし、agentスレッドは何もしない）を実装する。

## 何もしないスケジューラ
次は、Agentプロセス内にAgentスレッドをCPUごとに作成し、初期化処理を行うところまでを実装する。もう少し段階を分けたかったが、初期化処理がかなり入り組んでいるため、まとめてやることにした。
:::info
「何もしないスケジューラ」とは、agentスレッドが常にCPUをYieldするようなスケジューラのことである。
:::

最低限、新しく実装しなければならないものは以下の3つである。
* [FullAgent](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L424-L506)クラスの派生クラス
* [Agent](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L36-L123)クラスの派生クラス
* [Scheduler](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L95-L154)クラスの派生クラス

<u>これらのクラスは互いに依存しあっている</u>ため、どのクラスも必要不可欠である。各クラスの詳細は [lib ディレクトリ](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp) を参照して欲しい。

:::danger
これら3つのクラスの関係性や初期化の順序などはかなり入り組んでいます。[FIFOスケジューラの実装のところの初期化処理](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FBkiN0cDGa#%E5%88%9D%E6%9C%9F%E5%8C%96%E5%87%A6%E7%90%86)で詳しく扱っていますので、そちらも参考にしてみてください。
:::

これら3つのクラスの実装は、tut_scheduler.hかtut_scheduler.ccに実装していく。

### ★ Schedulerの派生クラス
Schedulerクラスのインスタンスは、基本的にEnclaveに対して1つ作成する（つまりプログラムごとに1つ）。すべてのAgentクラスのインスタンスから参照され、スケジューリングの決定などの処理を行う。Schedulerクラスは、<u>主にメッセージ処理とスケジューリングの決定を行う</u>。

ユーザー空間上で動作するスケジューラを実装するときは、Schedulerの派生クラスの[BasicDispatchScheduler](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L185-L404)を継承するのがよい。
:::info
「ユーザー空間上で動作するスケジューラ」と表記したのは、他にeBPFプログラムとして動作するスケジューラもあるからだ。eBPFで動作するスケジューラはBasicDispatchSchedulerを継承するのではなく、Schedulerを直接継承する。
:::
このクラスを継承するのに最低限実装しなければならないメンバ関数は以下の通り。
```cpp
class TutorialScheduler : public BasicDispatchScheduler<Task<>> {
public:
  // コンストラクタ
  // Channelの開設を行う
  TutorialScheduler(Enclave *enclave, CpuList cpulist, std::shared_ptr<TaskAllocator<Task<>>> allocator)
      : BasicDispatchScheduler(enclave, std::move(cpulist), std::move(allocator)) {
    // 管理対象CPUに対してそれぞれ必要な処理を行っていく。
    for (auto cpu: cpulist) {
      // ① cpu専用のChannelを作成
      channels_[cpu.id()] = enclave->MakeChannel(GHOST_MAX_QUEUE_ELEMS, 0, MachineTopology()->ToCpuList({cpu}));
      
      // ② 最初に作成したChannelをデフォルトのものとして設定する
      if (!default_channel_)
        default_channel_ = channels_[cpu.id()].get();
    }
  }
	
  // 実装必須
  Channel& GetDefaultChannel() final { return *default_channel_; }
  // 実装任意
  Channel& GetAgentChannel(const Cpu &cpu) override { return *channels_[cpu.id()]; }

protected:
  // コンパイルを通すために実装（中身は無）
  void TaskNew(Task<>* task, const Message& msg) final {}
  void TaskRunnable(Task<>* task, const Message& msg) final {}
  void TaskDeparted(Task<>* task, const Message& msg) final {}
  void TaskDead(Task<>* task, const Message& msg) final {}
  void TaskYield(Task<>* task, const Message& msg) final {}
  void TaskBlocked(Task<>* task, const Message& msg) final {}
  void TaskPreempted(Task<>* task, const Message& msg) final {}

private:
  // Channel用メンバ変数
  // このクラスがChannelのインスタンスのライフタイムを管理する
  std::unique_ptr<Channel> channels_[MAX_CPUS];
  Channel *default_channel_ = nullptr;
};
```
Schedulerクラスは派生クラスに対して以下の実装を要求している。
* ==**デフォルトのチャンネルを作成し、それを返す関数GetDefaultChannelを実装する。**==

そのためSchedulerの派生クラスは[Channel](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/channel.h#L75-L95)クラスのインスタンスを管理するメンバ変数を持っておく必要がある。**Per-CPU型であればCPUごとに1つのChannel** を、**Centralized型であれば全体で1つだけのChannel**を持っておけばよい。

Channelを開設する処理はコンストラクタに記述する。それに伴い[GetDefaultChannel](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L125-L126)を実装する。GetDefaultChannelは必ずoverrideしなければならない関数である一方で、[GetAgentChannel](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L127-L133)はPer-CPU型のときにだけ実装しておけばいい。

[TaskXXX](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L373-L398)という関数は純粋仮想関数のみ override しておく（こうしておかないとコンパイルが通らない）。この関数は後ほど実装するが、カーネルから送られてきたメッセージを処理する関数である。

### ◎ MultiThreadedScheduler
BasicDispatchSchedulerは[Task\<>](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L71-L93)インスタンスの管理を行うために**タスクアロケータ**を必要とする。タスクアロケータとはTask\<>インスタンスの作成や消去などを自動で行ってくれるクラスである（[詳しくはこちら](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#TaskAllocator)）。

:::warning
※ Task\<>クラスとはスケジューラの管理対象である**タスクの基本情報をまとめたクラス**であり、スケジューラが管理するタスクごとにインスタンスが1つ存在する。Task\<>には必要最低限の情報しか含まれていないので、**スケジューラを自作するときにはTask\<>の派生クラスを自前で実装する必要がある**が、今回は簡単のためTask\<>を直接利用している。
:::

Per-CPU型におけるSchedulerは複数のagentスレッドから共有されるため、排他処理が必要になってくる。マルチスレッドに対応したSchedulerの作成は以下のようにすればいい。
```cpp
inline std::unique_ptr<TutorialScheduler> TutorialMultiThreadedScheduler(Enclave *enclave, CpuList cpulist) {
  auto allocator = std::make_shared<ThreadSafeMallocTaskAllocator<Task<>>>();
  auto scheduler = std::make_unique<TutorialScheduler>(enclave, std::move(cpulist), std::move(allocator));
  return scheduler;
}
```
:::info
排他処理が必要なのはタスクアロケータのみ。
:::

### ★ Agentの派生クラス
Agentクラスには[LocalAgent](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L125-L136)という派生クラスがあり、このLocalAgentを継承したクラスTutorialAgentを実装する。この派生クラスには[AgentScheduler](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L98)メンバ関数を実装する必要がある。つまり、<u>上で定義したTutorialSchedulerのインスタンスへのポインタをメンバに持っておく必要がある</u>。
```cpp
class TutorialAgent : public LocalAgent {
public:
  TutorialAgent(Enclave *enclave, const Cpu &cpu, TutorialScheduler *scheduler)
    : LocalAgent(enclave, cpu), scheduler_(scheduler) {}
  
  // agentスレッドのメイン部分。
  void AgentThread() override {
    // 最初のこの部分は定形部分。他の全ての初期化の完了を待つ。
    SignalReady();
    WaitForEnclaveReady();
      
    printf("[ Agent Thread %d ] Finish Initialization !\n", gettid());
    
    // ★ agentスレッドが終了するまでひたすらCPUをYieldし続ける。
    while (!Finished()) {
      auto req = enclave_->GetRunRequest(cpu());
      req->LocalYield(status_word().barrier(), 0);
    }
  }

  Scheduler *AgentScheduler() const override { return scheduler_; }

private:
  // スケジューラのインスタンス
  TutorialScheduler *scheduler_;
};
```
**AgentThreadメンバがAgentスレッドのメイン処理部分**になる。
今回はスケジューリングは行わないため、★のwhileループではCPUをYieldするだけの実装にしてある（これはeBPFスケジューラで常套手段）。
:::warning
CPUをYieldする部分の処理についてはRunRequestらへんの解説を参照してください。agent は最高優先度で実行されるため、agentがCPUを明け渡さないと他のスレッドがCPUを使用できません。
:::

### ★ FullAgent の派生クラス
<u>AgentクラスやSchedulerクラスをまとめて管理するためのクラス</u>。

必要最小限の実装は以下の通り。
基本的に FullAgent の派生クラスの実装はこれで全てである（RpcHandler の実装に手を加えるくらい？）。
```cpp
class TutorialFullAgent : public FullAgent<> {
public:
  // コンストラクタ
  // ここで初期化処理を記述する。処理は基本的に以下の3つを順番に実行しておけばよい。
  TutorialFullAgent(AgentConfig &config) : FullAgent(config) {
    scheduler_ = TutorialMultiThreadedScheduler(&enclave_, *enclave_.cpus());
    StartAgentTasks();
    enclave_.Ready();
  }

  // 生成したagentスレッドの後始末を行うように必要な実装
  ~TutorialFullAgent() {
    TerminateAgentTasks();
  }
  
  void RpcHandler(int64_t req, const AgentRpcArgs& args, AgentRpcResponse& response) override { /* not implemented */ }
	
  // Agentの派生クラスのインスタンスを生成するメンバ関数。
  std::unique_ptr<Agent> MakeAgent(const Cpu& cpu) override { 
    return std::make_unique<TutorialAgent>(&enclave_, cpu, scheduler_.get()); 
  }

private:
  std::unique_ptr<TutorialScheduler> scheduler_;
};
```
新しく追加された実装はコンストラクタとデストラクタとMakeAgentメンバ関数である。
FullAgentの派生クラスでは、Schedulerの具象クラスの実体化やAgentの具象クラスの実体化の実装と、初期化処理の記述をする必要がある。

これらのクラス間の関係性をまとめた図を以下に示す。

![F498AD94-0A78-479A-A9F8-D057A692E70A](https://hackmd.io/_uploads/r1jF96FET.jpg)


























以上で「何もしないスケジューラ」の実装が完了した。ここで実装した処理のイメージ図を以下に示す。
![23DB8D38-E5A4-4B00-BFD1-195A0E74360F](https://hackmd.io/_uploads/BJWDYMxI6.jpg)











対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/e1c567ee95f884f381216f50185cdec9ad159030)

### まとめ
* スケジューラを実装するにはAgent, Scheduler, FullAgentそれぞれの派生クラスを実装し、決められた処理を実装する必要がある。
* これらのクラスは互いに依存関係にあるので、概要をつかみにくい。
* これら基底クラスのコンストラクタなどに必要な初期化処理などが記述されているため、ghOStカーネルが求める初期化処理はあまり気にしなくてもスケジューラを実装できる。

次は、ghOStカーネルからメッセージを取得してみる。

## メッセージ受信
初期化が完了したスケジューラはスケジューリングを行うことができる。しかし、今回はスケジューリングの決定は行わず、カーネルから送られてくるメッセージを取得するような実装をしていく。

まず、TutorialAgent::AgentThreadを以下のように変更する。
ひたすら無限ループでTutorialScheduler::Scheduleを呼び出すような処理である。
:::warning
:dart: SchedulerクラスとAgentクラスの役割分担としては、Agentスレッドの管理に関わる部分はAgentクラスで実装し、スケジューリング処理のコアな部分などはSchedulerクラスに実装するようにする。
:::
```cpp
  void AgentThread() override {
    // 省略
    ...
    while (!Finished()) {
      scheduler_->Schedule(cpu(), status_word()); // changed !!
    }
  }
```
引数にはCpuインスタンスとStatusWordインスタンスを渡す。
　Schedulerクラスは全てのagentスレッドから参照されるクラスなので、<u>どのagentがSchedule関数を呼び出したのかを引数cpuによって伝えている</u>。また、<u>トランザクションのコミット時にagentのステータスワードが必要なためagent_swも引数として渡している</u>のだ。
:::warning
:dart: [cpu()](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L71) や [status_word()](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/agent.h#L130) は基底クラスに実装されている。
:::

ここで呼び出される Schedule 関数の実装は以下のようにした（schedulers/per_cpu_tutorial/scheduler.cc というファイルを新しく作成し、そこに実装した）。
```cpp
void TutorialScheduler::Schedule(const Cpu &cpu, const StatusWord &agent_sw) {
  // ① メッセージの処理をする前に barrier の値を読み出しておく。
  BarrierToken barrier = agent_sw.barrier();

  // ② キューに来ているメッセージの処理を順番に行っていく。
  // 　 agent に関連付けられた Channel からメッセージを取り出していく。
  // 　 DispatchMessage の内部でメッセージごとの処理が呼び出される。
  Message msg;
  while (!(msg = channels_[cpu.id()]->Peek()).empty()) {
    DispatchMessage(msg);
    Consume(channels_[cpu.id()].get(), msg);
  }
  
  // ③ 今回もYieldするだけ。
  // 　 Yieldに失敗した場合は、メッセージの処理の最中にカーネル側で barrier の値が更新された
  // 　 ことを意味する。barrier 値が古すぎるよ、ってこと。
  auto req = enclave()->GetRunRequest(cpu);
  req->LocalYield(barrier, 0);
}
```
[DispatchMessage(msg)](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L496-L618)はメッセージキューに溜まっているメッセージの処理を行うメンバ関数である。<u>このメンバ関数の内部でメッセージの種類ごとに仕分けされ、TaskNewメソッドなどが呼び出される仕組み</u>になっている（詳しくは実装を参照）。

例えばMSG_TASK_NEWを見つけたときに呼び出される関数を以下のように実装した。
```cpp
void TutorialScheduler::TaskNew(Task<>* task, const Message& msg) {
  std::cout << msg << std::endl;
}
```
このスケジューラを実行中にghOStスレッドを生成するとMSG_TASK_NEWメッセージが発行されてきているのが分かるはず。以下はsimple_bashを別の端末から実行したときの様子を表している。 TASK_NEWが発行されたところで止まっているのが分かる。
```
$ sudo bazel-bin/per_cpu_tutorial_agent
> M: MSG_TASK_NEW seq=1 B0/9410/20692808834753735 runnable
```

対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/64e4577784f3b49441280fc776e0b28297578b79)

### まとめ
* BasicDispatchSchedulerクラスの機能を使うことで、簡単にメッセージ処理を行うプログラムを書くことができる。
* TaskNewやTaskDeadなどの各メッセージに対応したメンバ関数を実装する必要がある。

ここまでで、ghOStスレッドが生成されたことを検知できるようになった。次はいよいよghOStスレッドにCPU資源を割り当てていく。

## GHOSTタスクを実行状態にする
ここまでで、カーネルからメッセージを取得するところまでを実装した。次はいよいよ**タスクにCPU資源を割り当てる**プログラムを書いていく。この実装が完了すると、やっとスケジューラと呼んでいいようなものができあがる！

タスクを実行状態にするにはトランザクションを行う必要がある。トランザクションでは、実行状態にするGHOSTタスクのGTIDを指定する必要があるため、<u>スケジューラはどのタスクが現在実行可能状態なのか、を把握しておく必要がある</u>。

今回は、実行可能状態のタスクをdequeで管理するrq_というメンバ変数を用いて、実行可能状態のタスクを管理することにした。

```cpp
class TutorialScheduler : public BasicDispatchScheduler<Task<>> {
  ...
private:
  ...	
  // 実行可能キュー
  // このキューの先頭にあるタスクが次に実行状態となるorすでに現在実行中のタスク
  std::deque<Task<> *> rq_;
};
```
rq_の先頭は**実行状態**か**次に実行状態になるタスク**を表すようにする。こうすることで、rq_だけで実行状態のタスクと実行可能状態のタスクを管理できる。

このデータ構造を元にTutorialScheduler::Scheduleの実装を以下のように改変する。
```cpp
void TutorialScheduler::Schedule(const Cpu &cpu, const StatusWord &agent_sw) {
  // ① メッセージの処理をする前に barrier の値を読み出しておく。
  BarrierToken barrier = agent_sw.barrier();

  // ② キューに来ているメッセージの処理を順番に行っていく。
  // 　 agent に関連付けられた Channel からメッセージを取り出していく。
  // 　 DispatchMessage の内部でメッセージごとの処理が呼び出される。
  Message msg;
  while (!(msg = channels_[cpu.id()]->Peek()).empty()) {
    DispatchMessage(msg);
    Consume(channels_[cpu.id()].get(), msg);
  }
  
  // ========== ⇣⇣⇣ 変更箇所 ⇣⇣⇣ ==========
  // ③ スケジューリング
  RunRequest *req = enclave()->GetRunRequest(cpu);
  if (agent_sw.boosted_priority()) {
    // GHOSTタスクより高優先度なタスク（CFSタスクなど）があればCPUを明け渡す
    // RTLA_ON_IDLEを指定することを忘れずに（CPUがIDLE状態になったときにagentを
    // 実行状態にするためのおまじない）！
    req->LocalYield(barrier, RTLA_ON_IDLE);
    return;
  }

  // nextには次に実行状態にするタスクへのポインタを格納する
  Task<> *next = nullptr;
  // ◎ メッセージ処理のときにTaskNew()メンバ関数などでrq_にタスクが
  //  　プッシュされているはず
  if (!rq_.empty()) {
    next = rq_.front();
  }

  if (next) { 
    // next候補があればトランザクションを用意
    req->Open({
      .target = next->gtid,
      .target_barrier = next->seqnum,
      .agent_barrier = barrier,
      .commit_flags = COMMIT_AT_TXN_COMMIT,
    });

    // トランザクションを発行
    if (req->Commit()) {
      // succeeded !! 
    } else {
      // コミットに失敗した場合は、そのトランザクションの状態を出力する（デバッグ用）
      std::cerr << "Failed to commit txn." << std::endl;
      std::cerr << "txn state: " << req->state() << std::endl;
    }
  } else {
    // next候補がなければCPUを明け渡す（CPUはIDLE状態に）
    req->LocalYield(barrier, 0);
  }
}
```
boosted_priorityについては[こちらを参照](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FBkiN0cDGa#prio_boost-%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6)。

◎の部分が**次のタスクを選択する部分**である。今回は、rq_の先頭を選ぶ、という簡単な実装になっている。

RunRequestとは、トランザクションを抽象化したクラスである。agentはこのクラスを利用して、トランザクションを発行したり、トランザクションの結果を参照したりする。今回の例だと、Openでトランザクションに必要な情報を書き込み、Commitでトランザクションをコミットしている。詳しくは[こちらを参照](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#RunRequest)。

◎の部分で次のタスクを選択するためには、rq_にタスクが格納されていないといけない。これはTaskNewで以下のように実装しておけばよい。
```cpp
void TutorialScheduler::TaskNew(Task<>* task, const Message& msg) {
  std::cout << msg << std::endl;
    // メッセージのペイロード部分にTASK_NEWメッセージ固有の情報が格納されている。
  const ghost_msg_payload_task_new* payload = 
    reinterpret_cast<const ghost_msg_payload_task_new *>(msg.payload());
  // taskのseqnumを更新する（必須）
  task->seqnum = msg.seqnum();

  // payload->runnableがtrueのときはそのタスクがすでに実行可能状態であるということ、
  // 逆にfalseのときはスリープ状態であることを意味する。
  if (payload->runnable) {
    rq_.push_back(task);
  }
}
```
:::warning
:dart: 新しくghOStスレッドとなったスレッドが最初に発行するメッセージがMSG_TASK_NEWである。スケジューラはそのメッセージによって、新しく管理対象となったタスクを把握する。

TaskNewではtaskという引数が渡されているが、このTask\<>インスタンスはいつ作られるのか？答えは、[BasicDispatchScheduler::DispatchMessage関数の内部](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/lib/scheduler.h#L541-L555)で作られている。そのため、TaskNewの内部で新しくTask\<>インスタンスを作成する必要はないのである。
:::

他のメッセージに関しても必要な処理を記述する。
```cpp
// スリープ状態 -> 実行可能状態
void TutorialScheduler::TaskRunnable(Task<>* task, const Message& msg) {
  // 実行可能キューの最後尾にtaskを追加
  rq_.push_back(task);
}

// 実行状態 -> スリープ状態
void TutorialScheduler::TaskBlocked(Task<>* task, const Message& msg) {
  CHECK(!rq_.empty());
  CHECK_EQ(task, rq_.front()); // 現在実行状態のタスクはrq_の先頭にいるはず

  rq_.pop_front();
}

// 任意の状態 -> 他のスケジューリングクラス
void TutorialScheduler::TaskDeparted(Task<>* task, const Message& msg) {
  // rq_の中にtaskがある場合はrq_から取り除く
  rq_.erase(std::remove(
    rq_.begin(), 
    rq_.end(), 
    task), rq_.end());

  // タスクが占めるメモリ領域を解放する
  allocator()->FreeTask(task);
}

// スリープ状態 -> タスクの終了
void TutorialScheduler::TaskDead(Task<>* task, const Message& msg) {
  // taskが占めるメモリ領域を解放する
  allocator()->FreeTask(task);
}

// 実行可能状態 -> 実行可能状態
void TutorialScheduler::TaskYield(Task<>* task, const Message& msg) {
  CHECK(!rq_.empty());
  CHECK_EQ(task, rq_.front());

  // rq_の先頭のタスクをrq_の最後尾に移動する
  rq_.pop_front();
  rq_.push_back(task);
}

// 実行可能状態 ➙ 実行可能状態
void TutorialScheduler::TaskPreempted(Task<>* task, const Message& msg) {
  // 特に実装なし
}
```

参考程度にタスク関連のメッセージとタスクの状態遷移の関係図を以下に示す。
![1D692007-F56D-428E-A1FC-9949111FE049](https://hackmd.io/_uploads/B1bBe0_56.jpg)
















ここまで実装できていると、simple_bashを実行することができるようになる。簡易的なスケジューラの完成である！

:::warning
:dart: Per-CPUで実装しているが、現状スケジューリングにはCPU0しか使えていない。他にCPU1やCPU4を使うには（つまりSMP環境に適応するには）、もっと色々とやることがある（後ほど実装する）。
:::

対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/d6c2dcf54176ff7ca8713ed6928994ceb0d8beef)

### まとめ
* スケジューラの核となる部分は**メッセージ処理**と**PNT**と**トランザクション**。
* メッセージ処理に関しては、メッセージごとのコールバックがBasicDispatchSchedulerで定義されているので、それらをoverrideする実装を書けばいい。
* タスクの管理などはC++の好きなデータ構造を利用・自作して行える。
* トランザクションを発行するための作法があるので、そこはしっかり見ておく必要あり。

## Task\<>クラスの派生クラスを実装する

上の説明でもあったが、本来、スケジューラの実装をするときはTask\<>の派生クラスを自前で実装してあげた方がよい。

実際、ghost-userspaceに実装されているどのスケジューラの実装を見ても、Task\<>クラスを直接使っているものはなく、それぞれ**スケジューラに必要な情報を追加した派生クラスを実装している**（例えば[FifoTask](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/fifo/per_cpu/fifo_scheduler.h#L30-L58)や[CfsTask](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/cfs/cfs_scheduler.h#L213-L253)）。

Task\<>も必要最低限の情報は管理してくれるのだが、その管理する情報とはどのスケジューラにも必要な情報のみであり、スケジューラの実装には明らかに足りない。

Task\<>の派生クラスが持っておくべき情報を2つに分けて紹介する。

1つは、**そのタスクが現在スケジュールされているCPUの番号**と**そのタスク状態**についての情報だ。これはPer-CPU型では必須と言っていいだろう。
　スケジューラの実装では、メッセージのコールバックを実装することになるが、<u>渡される引数からはそのタスクが現在管理されているCPUの番号を知ることができない</u>。もちろん、sched_getcpu()などを駆使して知ることは可能だが、タスクにCPUの情報を持たせておくと++何かと便利++になるため、最初の設計の段階で持たせておくことにすべし（特にマイグレーションの実装などで）。
　また、タスクの状態をTask<>の派生クラスで管理しておくとデバッグが楽になる。<u>スケジューラの実装では、タスクの状態変化を適切に管理できていないことによるバグが多い</u>。他のスケジューラの実装を見てみると、状態変化の遷移が正しく行われているのかを、abseilの**CHECKマクロ**などを駆使して検証している（例えば[これ](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/fifo/per_cpu/fifo_scheduler.cc#L124)とか）。

もう1つは、**スケジューリングポリシーを実現する上で必要な情報**である。例えばCfsTaskであれば、そのタスクの[nice](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/cfs/cfs_scheduler.h#L236)値や[vruntime](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/cfs/cfs_scheduler.h#L245)値などが管理されている。

ここでは、タスクの状態を持つ派生クラスTutorialTaskを実装することにする（CPUの情報については、まだSMPに対応していないので、ここでは実装しない）。

まず、タスクの状態を意味する列挙クラスTutorialTaskStateを実装した。最低限、以下のような3つの状態があれば十分だろう（スケジューラの実装によっては、もっと必要）。
```cpp
// タスクの状態を表すenum class
// 簡単に3つの状態のみを扱う。
// タスクの状態
enum class TutorialTaskState {
  kBlocked = 0,
  kQueued,
  kRunning,
};
```
TutorialTaskの実装は以下のようにした。直接state_を書き換えられるような実装にしても良かったのだが、あとあと状態変化の前後に関数をフックしたくなることを見据えて、以下のような実装にしてある。
```cpp
// Task<>の派生クラス
// タスクの状態に関する情報をメンバ変数に含める
struct TutorialTask : public Task<> {
  // この形式のコンストラクタは実装必須。
  // 基本的には以下のような実装でよい。
  TutorialTask(ghost::Gtid& gtid, ghost_sw_info& sw_info) :
    Task<>(gtid, sw_info) {}

  TutorialTaskState GetState() const { return state_; }

  // タスクの状態変化はこのメンバ関数を必ず介すことにする。
  // タスクの状態変化に関するフック関数を簡単に実装できるようにするため。
  void SetState(TutorialTaskState state) { state_ = state; }

  // 便利な関数
  bool blocked() { return state_ == TutorialTaskState::kBlocked; }
  bool queued() { return state_ == TutorialTaskState::kQueued; }
  bool running() { return state_ == TutorialTaskState::kRunning; }

 private:
  TutorialTaskState state_ = TutorialTaskState::kBlocked;
};
```
あとは適宜Task\<>の部分をTutorialTaskに置換すればよい。

タスクのインスタンスが状態に関する情報をもっているということで、以下のように整合性の検査を差し込むことができるようになる。これで、スケジューラがabortしたときに、何が原因でabortしたのか、を簡単にフィードバックできるようになった。
```cpp
// スリープ状態 -> 実行可能状態
void TutorialScheduler::TaskRunnable(TutorialTask* task, const Message& msg) {
  CHECK(task->blocked());

  // 実行可能キューの最後尾にtaskを追加
  task->SetState(TutorialTaskState::kQueued);
  rq_.push_back(task);
}
```
他のメッセージ処理関数でも整合性のチェックが追加されているので、詳しくはコミットの内容を参照してほしい。

対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/fe0314f91cadfa1d7584d5b148c105e3ced8de47)

## ラウンドロビン（もどき）

ここでは簡単なラウンドロビン（もどき）スケジューラを実装していく。ここで実装するスケジューラは、**一定時間ごとにタスクを切り替える**ことで、タスクに平等にCPU時間を分配する。

ラウンドロビン（もどき）スケジューラを実装するためには、<u>一定時間ごとにスケジューラが起きてタスクの切り替えを行う必要がある</u>。ghOStにはCPUのタイマー割り込みが発行されるたびに送られるMSG_CPU_TICKメッセージがあるため、これを利用するとよい。

ただし、<u>デフォルトではMSG_CPU_TICKは送られてこないようになっている</u>。これを送られてくるようにするには、[ghOStFSのdeliver_ticks](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FS1aXXxTZa#deliver_ticks)に1を書き込む必要がある。なお、このような処理はEnclaveクラスがラップしてくれているので、TutorialScheduler::EnclaveReady関数に以下のように実装すればいい。
```cpp
// 初期化処理の最後の方で呼ばれる関数。
void EnclaveReady() final {
  // MSG_CPU_TICKメッセージを発行するように設定
  enclave()->SetDeliverTicks(true);
}
```
:::success
:dart: TutorialScheduler::EnclaveReady関数とは、初期化処理の一番最後で呼び出される関数である。詳しくは[こちら](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#%F0%9F%8C%95-EnclaveReady)。
:::
:::warning
:dart: MSG_CPU_TICKを有効にする別の方法として、AgentConfigのtick_config_を利用するという手もある。どっちの方法を取るにしても、初期化時にenclave()->SetDeliverTicks(true)を実行している、という点ではやっていることは同じである。

この方法でMSG_CPU_TICKを有効にするには、agent.ccを以下のように改変する。
```cpp
int main() {
  ...
  // ① agent用プロセスを生成
  AgentConfig config;
  config.topology_    = MachineTopology();
  config.cpus_        = MachineTopology()->ParseCpuStr("0-1,4");
  config.tick_config_ = CpuTickConfig::kAllTicks; // ☆☆☆ 新しく追加 ☆☆☆
  auto uap = new AgentProcess<TutorialFullAgent, AgentConfig>(config);
  ...
}
```
:::

CpuTickメンバ関数を実装する。このメンバ関数はMSG_CPU_TICKメッセージが送られてきたときに呼び出されるコールバックである。
```cpp
// MSG_CPU_TICKは他のメッセージと干渉する可能性があるため、注意深くする必要がある。
// 例えば、MSG_TASK_BLOCKEDと同じタイミングで発行された場合の処理の手続きをしっかり
// とやる必要がある。
void TutorialScheduler::CpuTick(const Message& msg) {
  if (!rq_.empty()) {
    auto current = rq_.front();

    // もしrq_の先頭が実行状態なら、プリエンプトしrq_の最後尾に追加する
    if (current->running()) {
      current->SetState(TutorialTaskState::kQueued);
      rq_.pop_front();
      rq_.push_back(current);
    }
  }
}
```


:::warning
:dart: MSG_CPU_TICK メッセージは常に送られてくるのではなく、ghOStスレッドが実行中のときにのみ送られてくるので注意。
:::
このような実装にすることで、タイマー割り込みごとに MSG_CPU_TICK メッセージが送られてきて、スケジューラはそのたびにタスクを別のタスクに切り替えることができる。

ここで注意してほしい点がある。それは、MSG_CPU_TICKメッセージとMSG_TASK_BLOCKEDメッセージなどが同時期に発行される場合がある、ということである。このままの実装では、すぐにスケジューラがクラッシュしてしまうため、TaskBlockedなどの実装も変えてあげる必要がある。

例えば、TaskBlockedの実装は以下のように変更する必要がある。本来、MSG_TASK_BLOCKEDメッセージは実行状態のときに発行されてくるが、同時刻に先にMST_CPU_TICKが発行されていた場合、そっちの処理で状態が変わるため、実行可能状態にすでに遷移していることも考えられる。
```cpp
// 実行状態 -> スリープ状態
void TutorialScheduler::TaskBlocked(TutorialTask* task, const Message& msg) {
  // MSG_CPU_TICKとの干渉が考えられるため、!task->running()という場合が考えられる。
  // その場合はtask->queued()となっているはずである。
  if (task->running()) {
    CHECK(!rq_.empty());
    CHECK_EQ(task, rq_.front());
    task->SetState(TutorialTaskState::kBlocked);
    rq_.pop_front();
  } else if (task->queued()) {
    task->SetState(TutorialTaskState::kBlocked);
    rq_.erase(std::remove(
      rq_.begin(), 
      rq_.end(), 
      task), rq_.end());
  } else {
    // B -> B という遷移は起きないはず
    CHECK(false);
  }
}
```

ラウンドロビンが機能しているかどうかを確認するために、以下のようなテストプログラムを作って実行してみた。
```cpp
#include "lib/ghost.h"
using namespace ghost;

// 少々重めの処理
void BusyLoop() {
  for (int i = 0; i < 1000000000; i++);
}

int main() {
  absl::Time program_start = MonotonicNow(); // プログラム開始時間
  absl::Time t1_start, t1_end, t2_start, t2_end;

  GhostThread t1(GhostThread::KernelScheduler::kGhost, [&]() {
    t1_start = MonotonicNow(); // スレッド1の開始時間
    BusyLoop();
    t1_end = MonotonicNow(); // スレッド1の終了時間
  });
  GhostThread t2(GhostThread::KernelScheduler::kGhost, [&]() {
    t2_start = MonotonicNow(); // スレッド2の開始時間
    BusyLoop();
    t2_end = MonotonicNow(); // スレッド2の終了時間
  });

  t1.Join();
  t2.Join();

  std::cout << "計測結果" << std::endl;
  std::cout << std::endl;
  std::cout << "[ t1 ]    start: " << absl::ToInt64Milliseconds(t1_start - program_start) << " ms" << std::endl;
  std::cout << "            end: " << absl::ToInt64Milliseconds(t1_end   - program_start) << " ms" << std::endl;
  std::cout << "        elapsed: " << absl::ToInt64Milliseconds(t1_end   - t1_start     ) << " ms" << std::endl;
  std::cout << std::endl;
  std::cout << "[ t2 ]    start: " << absl::ToInt64Milliseconds(t2_start - program_start) << " ms" << std::endl;
  std::cout << "            end: " << absl::ToInt64Milliseconds(t2_end   - program_start) << " ms" << std::endl;
  std::cout << "        elapsed: " << absl::ToInt64Milliseconds(t2_end   - t2_start     ) << " ms" << std::endl;
}
```
以前のスケジューラの場合の結果は以下のようになった。
```
計測結果

[ t1 ]    start: 5 ms
            end: 1440 ms
        elapsed: 1435 ms

[ t2 ]    start: 1440 ms
            end: 2842 ms
        elapsed: 1402 ms
        
```
一方、ラウンドロビンスケジューラの場合の結果は以下のようになった。
```
計測結果

[ t1 ]    start: 12 ms
            end: 3004 ms
        elapsed: 2991 ms

[ t2 ]    start: 14 ms
            end: 3102 ms
        elapsed: 3088 ms

```
ラウンドロビンの方は2つのスレッドが並行して実行されているのがわかる！

対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/bef0aaeba5cd12776b284a83fa8d4ca09fc08ab9)

## SMPに対応する
これまでのスケジューラの実装はCPU0, 1, 4を指定しておきながら、**CPU0のみしか使ってこなかった**。ここからは、複数のCPUにタスクを分配し、SMP環境に適応したスケジューラを作っていく。

まず最初に、SMPに適応していく前に、**各メッセージキューとghOStスレッドとagentの関係性**を理解しておく必要がある。詳しくは[こちらの記事](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FHy2Oq2mmp#%E3%83%A1%E3%83%83%E3%82%BB%E3%83%BC%E3%82%B8%E3%82%AD%E3%83%A5%E3%83%BC%E3%81%AE%E9%96%A2%E9%80%A3%E4%BB%98%E3%81%91%E3%81%A8WAKEUP%E3%83%AA%E3%82%B9%E3%83%88)にまとめたので、先に目を通してもらいたい。

これまで、<u>タスクがCPU0でのみスケジューリングされていたのは、タスク関連のメッセージがすべてCPU0のメッセージキューにpushされていたから</u>である。新しく作成されたghOStスレッドは、enclaveの中のデフォルトキューというメッセージキューに関連付けられることになっている。今回の場合、デフォルトキューはCPU0のメッセージキューであった。

タスクを他のCPU1やCPU3でスケジュールするためには、**そのタスクのメッセージを別のメッセージキューにpushするように設定する必要がある**。このghOStスレッドとメッセージキューの関連付けを行うシステムコールが[**ASSOC_QUEUE**](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2FS1aXXxTZa#GHOST_IOC_ASSOC_QUEUE)である。


:::success
:point_right: また、CPU関連のメッセージがどのCPUのメッセージキューにpushされるのか、や、そのメッセージキューに新しくメッセージがpushされたときにどのagentが起こされるか、についても設定する必要があるが、幸いなことに、それぞれ[Agent::ThreadBody](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#ThreadBody)と[LocalChannel](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#LocalChannel)のコンストラクタで自動で設定されるので、今回は設定する必要はない。
:::

Channelにタスクを関連付けるには、[Channel::AssociateTask](https://hackmd.io/@cwtjjkgpTyeVG_KcZmF3LQ/HJNj83_ma/https%3A%2F%2Fhackmd.io%2F%40cwtjjkgpTyeVG_KcZmF3LQ%2Frkc6rFXfp#AssociateTask)を実行する。タスクの関連付けは想像以上に難しいため、今回はTaskNewコールバックの内部でのみタスクの振り分けを行うように実装する。

:::warning
:dart: タスクの関連付けが難しい理由としては、タスクのChannel間の移動とタスクがメッセージを発行するタイミングが重ならないようにしなければならない、というのが挙げられる。ASSOC_QUEUEシステムコールを発行したとき、もとのキューにメッセージがまだ残っている場合は、このシステムコールは失敗してしまう。
なお、TaskNewメッセージの到着後は、他のメッセージが発行されてこないことが保証されていると[ここのコメント](https://github.com/google/ghost-userspace/blob/9ca0a1fb6ed88f0c4b0b40a5a35502938efa567f/schedulers/fifo/per_cpu/fifo_scheduler.cc#L133-L134)にあるため、TaskNewでは処理が簡略化される。
:::

実装を簡潔にするため[Task\<>クラスの派生クラスを実装する](#Taskltgtクラスの派生クラスを実装する)の続きからやっていくことにする（つまり、ラウンドロビンの実装はしていないものとして実装していく）。SMP環境に適用するにはいくつかのデータ構造を定義する必要がある。

まず、SMPに対応するということで、TutorialTaskのフィールドにCPUの情報を含ませる。

```cpp
struct TutorialTask : public Task<> {
  ...
  int GetCpu() { return cpu_; }
  void SetCpu(int cpu) { cpu_ = cpu; }

 private:
  ...
  int cpu_ = -1;
};
```

SMP環境では、タスクをCPU間で移動させてあげる必要がある。このとき、rqから別のrqへ移動する処理などを行うため、rqへのアクセスは排他制御をする必要がある。今回は、**スレッドセーフ**なrqとしてTutorialRqクラスを実装した。
```cpp
class TutorialRq {
 public:

  ...

  // キューの最後尾にtaskを追加する。
  void PushBack(TutorialTask *task) {
    std::lock_guard<std::mutex> guard(mtx_);
    rq_.push_back(task);
  }

  ...

 private:
  std::mutex mtx_;
  std::deque<TutorialTask *> rq_;
};
```
TutorialRqに関する詳しい実装はコミットを参照してほしい。単にdequeをMutexでラップしただけのクラスである。

これまでの実装では、rq_はスケジューラで1つしか存在していなかったが、Per-CPU型の場合、rq_は各CPUごとに用意するべきである。他にも、各CPUごとにメッセージキューを管理したりと、CPUごとに管理するデータ構造がいくつか存在する。そこで、**CPUごとに存在するデータ構造を1つにまとめて管理するため**に、TutorialCpuStateクラスを実装した。
```cpp
// CPUごとに管理するデータをまとめたもの。
//  - current: CPUを使用しているghOStタスクへのポインタを格納する。
//             CPUを使用中のタスクがなければnullptrとなる。
//  - agent:   agentスレッド。
//  - channel: CPUに関連付けられたChannelのユニークポインタ。
//  - rq:      実行可能キュー。
struct TutorialCpuState {
  TutorialTask *current = nullptr;
  Agent *agent = nullptr;
  std::unique_ptr<Channel> channel = nullptr;
  TutorialRq rq;
};

class TutorialScheduler : public BasicDispatchScheduler<TutorialTask> {
  ...
 private:
  TutorialCpuState &cpu_state(int cpu) { return cpu_states_[cpu]; }
  TutorialCpuState &cpu_state(const Cpu &cpu) { return cpu_states_[cpu.id()]; }

  TutorialCpuState cpu_states_[MAX_CPUS];
  Channel *default_channel_ = nullptr;
};
```

この変更に伴って、大幅に実装が変更されるため、詳しくはコミットの内容を確認してもらいたい。

次はTaskNewの実装をする。今回の実装では、簡単のため、TaskNewの中でのみタスクの移動を行うようにした。タスクのマイグレーションは、タスクが実行可能状態になったタイミングでやったりすることもできるが、実装が一気に複雑になるので、今回は行わない。なぜなら、このチュートリアルはタスクの**CPU移動の本質を理解することを目的にしているから**だ。

TaskNewの実装に先立って、**新しいタスクをどのCPUに割り当てるか**、を選択する関数SelectCpuを実装した。単にCPU0,CPU1,CPU3を呼び出しごとにローテーションしているだけである。
```cpp
  // 新しいタスクが追加されたとき、そのタスクを割り振るCPUを選択する関数。
  // 実装はかなり単純化していて、cpus()のなかをぐるぐる周る感じ。
  const Cpu SelectCpu() {
    static auto begin = cpus().begin();
    static auto end = cpus().end();
    static auto next = cpus().end();

    if (end == next)
      next = begin;
    return next++;
  }
```

また、SMP環境で便利なMyCpuという関数も実装する。これは、agentスレッドがTutorialSchedulerのコードを実行中に**現在実行しているcpuの番号を知るための関数**である。つまり、TutorialSchedulerのコードを実行中にこの関数を呼び出すと、その返り値は自身のCPU番号に一致する。
```cpp
  // 現在実行中のCPUを返す。
  // TutorialSchedulerはいろいろなスレッドから呼び出されるので、
  // 今どのagentが実行しているのか、といった情報があるとありがたい。
  int MyCpu() {
    static thread_local int cpu = -1;
    if (cpu < 0)
      cpu = sched_getcpu();
    return cpu;
  }
```
では、TaskNewの実装を見ていく。
　処理の順序としては、まずタスクを割り振るCPUを選び、その後ASSOC_QUEUEによってタスクとChannelを関連付ける。もし関連付けに失敗した場合は、デフォルトのChannelに関連付けられたままにする。その後、タスクが実行可能状態であれば、そのタスクをrqにプッシュする。
```cpp
void TutorialScheduler::TaskNew(TutorialTask* task, const Message& msg) {
  // メッセージのペイロード部分にTASK_NEWメッセージ固有の情報が格納されている。
  const ghost_msg_payload_task_new* payload = 
    reinterpret_cast<const ghost_msg_payload_task_new *>(msg.payload());
  // taskのseqnumを更新する（必須）
  task->seqnum = msg.seqnum();
  
  // taskを割り当てるCPUを選択する。
  CHECK_EQ(task->GetCpu(), -1);
  auto cpu = SelectCpu();
  // taskをcpuに関連付ける。
  // ここの処理が正常に終了すると、このtaskに関連するメッセージはそのCPUのメッセージキューに
  // 発行されるようになる。
  int status;
  bool result = cpu_state(cpu).channel->AssociateTask(task->gtid, task->seqnum, &status);
  if (!result) {
    // TaskNewでのASSOC_QUEUEが失敗した場合は、いったんデフォルトキューに関連付けを戻しておく。
    printf("[!] Failed to AssociateTask in TaskNew. status = 0x%08x", status);
    cpu = cpus()[0];
  }

  task->SetCpu(cpu.id());
  printf("[*] Task %d is associated with cpu %d\n", task->gtid.tid(), cpu.id());

  auto &cs = cpu_state(cpu);
  // payload->runnableがtrueのときはそのタスクがすでに実行可能状態であるということ、
  // 逆にfalseのときはスリープ状態であることを意味する。
  if (payload->runnable) {
    task->SetState(TutorialTaskState::kQueued);
    cs.rq.PushBack(task);
    cs.agent->Ping();
  }
}
```

他のメッセージのコールバックについても、TaskBlockedを例に見ていく。実装は以下のようになっていて、先頭の2行はどのメッセージのコールバックにも実装されている。この2行は、**タスクが関連付けられているCPUとこのメッセージを処理しているagentのCPUが一致していることを確認している**。また、現在実行中のタスクをcs.currentで管理するようになったので、そこらへんの実装も変更されている。
```cpp
// 実行状態 -> スリープ状態
void TutorialScheduler::TaskBlocked(TutorialTask* task, const Message& msg) {
  CHECK_EQ(task->GetCpu(), MyCpu());
  auto &cs = cpu_state(MyCpu());

  CHECK_EQ(task, cs.current);
  CHECK(task->running());

  // currentをnullptrに変更する
  task->SetState(TutorialTaskState::kBlocked);
  cs.current = nullptr;
}
```
他のメッセージのコールバックについてはコミットの内容を参照されたい。

ここまで実装できていれば、きちんとCPU1もCPU3も使えるようになっているはずである。試しに、[ラウンドロビン（もどき）](#ラウンドロビン（もどき）)で作成したテストプログラムを実行してみると以下のようになっていた。ラウンドロビンでは1つのCPUでがんばって処理していたのですべてのタスクを終えるまでに約3秒かかっていたが、今回は2つのCPUで手分けして処理を行えたので**約半分の時間**で処理を終えることができた。
```
$ bazel-bin/busy_loop_2_threads
計測結果

[ t1 ]    start: 14 ms
            end: 1424 ms
        elapsed: 1409 ms

[ t2 ]    start: 48 ms
            end: 1453 ms
        elapsed: 1405 ms
```

対応するコミット ➙ [リンク](https://github.com/ruth561/ghost-userspace/commit/4a8b7f5319f7d53b6dd48255c992f5e7c6718a77)

### まとめ
* スケジューラの実装にはrq用のデータ構造、CPUごとに管理するデータ構造をまとめるCpuState、があるとよい。
* タスクのマイグレートにはAssociateTaskを用いる。これは失敗する可能性もあるので、そのエラー処理もしっかり記述する。
* Task構造体にもCPUの情報を付加してあげるとよい。
