<style>

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

</style>

# ghOSt概要

現在、Linuxカーネルのスケジューラの構造は複雑で、新しくスケジューリングポリシーを追加するのが困難となっています。これは、Linuxカーネルのスケジューラ周りのコードを深く理解していないと実装できないのが原因です。**[ghOStカーネル](https://github.com/google/ghost-kernel)は、スケジューラをアプリケーションとして実装できる仕組みを提供する**ことで、新しいスケジューリングポリシーの追加や実験を簡単に行えるようにしてくれます。

⚠ ghOStに関する基本的な内容は、論文やその論文に関する日本語の記事などを参考にしてみてください。ここでは主にGoogleが開発したghost-kernelとghost-userspaceの実装に重点をおいてまとめていきます。

論文URL：https://dl.acm.org/doi/abs/10.1145/3477132.3483542
ghost-kernel：https://github.com/google/ghost-kernel
ghost-userspace：https://github.com/google/ghost-userspace

# ghOStはどのように実現されるか？
ghOStカーネルはLinuxカーネルを改変して作られています。スケジューラ実装の大枠はLinuxカーネルと同じであり、ghOStは1つの sched_class として実装されています（[ghost_sched_class](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/kernel/sched/ghost_core.c#L1174-L1194)）。[ghost_sched_class](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/kernel/sched/ghost_core.c#L1174-L1194) は fair_sched_class と idle_sched_class の間に優先度が設定されているため、**ghOStスレッド**（ghOStで管理されるスレッド）はCFSスレッドなどからプリエンプションされるようになっています。

カーネル空間上の [ghost_sched_class](https://github.com/google/ghost-kernel/blob/edd5f9490d82df24c16f90a62f7be05c6c389867/kernel/sched/ghost_core.c#L1174-L1194) は、ユーザー空間上のスケジューラと協力してスケジューリングの決定を行います。おおまかな役割分担としては、実際にタスクの切り替えなどを行うのがカーネルの仕事で、nextタスクを決定したりするのがスケジューラの仕事です。

カーネルとスケジューラの間にはいくつかの共有メモリが用意され、その共有メモリを介して情報のやり取りを高速に行います。具体的には、**メッセージ通信**、**ステータスワード**、**トランザクション**、の3つです。
|||
|-|-
| メッセージ | カーネル ➙ スケジューラ。++タスクの状態変化やCPUのTick++などの情報がやり取りされる。キューによって実装されている。
| ステータスワード | カーネル ➙ スケジューラ。ghOStスレッドの現在の状態をスケジューラに公開する。runtimeやコンテキストスイッチの回数などが公開される。情報の同期ができているのかを確認するためのシーケンス番号も 公開される。
| トランザクション | スケジューラ ➙ カーネル。スケジューリングの決定などを行うときに使われる。スケジューリングの決定はシステムコールによって行われるが、システムコールの引数では渡しきれない（というか非効率な）ため、共有メモリを介して渡されることになっている。

これらの仕組みを利用し、以下のようなワークフローでスレッドのスケジューリングを行います。
1. CPUタイマーの割り込みが起きたり、ghOStスレッドに状態変化が起きたりすると、カーネルはその内容をメッセージキューにプッシュし、スケジューラを起こす。
2. スケジューラはカーネルからのメッセージを受け取り、スレッドの最新状態を把握する。その情報を元にnextタスクを選択し、トランザクションによってカーネルにnextタスクを実行するように要請する。
3. カーネルはトランザクションの内容をもとにタスクの切り替えを行う。
4. 以下、1. ➙ 2. ➙ 3. を繰り返す。


## 図の補足（agentについて）
アプリケーション側でスケジューリングの決定を行う++スレッドのこと++を **agent** と呼びます。agent は1つのCPUに紐付けられたスレッドであり、スケジューラが管理するCPUごとに1つ存在します。例えば、CPU1, 2, 4を管理するスケジューラには3つのagentスレッドが存在することになります。

スケジューラがユーザー空間で動作することで、++ghOStスレッドと直接的に情報のやり取りをすることができるようになります++。例えば、「今から周期タスクを始めるよ」「これからのタスクは優先度低めでいいよ」といった情報をスケジューラは実行時に受け取ることができます。

:::info
:dart: 実は agent スレッドは特別な sched_class で管理されています（ghost_agent_sched_class）。ghost_agent クラスは他の sched_class よりも優先度が高く設定されているため、agent は最も優先的に実行されることになっています。これにより、++agentが他のスレッドからプリエンプションされることはなくなる++ため、安定して動作することができます。一方で、agentがCPUを開放ない限り、他のスレッドはCPUを使うことができないため、システムに影響がでてしまいます。agentの実装には注意が必要です。

flowchart LR
classDef ghost fill:#CCFFCC
stop --> 
A["ghost_agent"]:::ghost --> dl --> rt --> fair --> 
ghost:::ghost --> idle

:::

# スケジューラのワークフロー

loop {
    // ① メッセージキューが空になるまでメッセージの処理を行う
    DispatchMessage();
    // ② 次に実行状態にするタスクを選ぶ
    next = PickNextTask();
    // ③ トランザクションをコミットする
    // 　 ここでシステムコールが発行されカーネルに一旦処理が移る。
    // 　 コミットに成功したら内部でコンテキストスイッチが起こり、nextが実行状態になる。
    // 　 コミットに失敗したら直ちにシステムコールを終了し戻ってくる。
    result = CommitTransaction(next);
    // ★★★
    if (result == SUCCESS) {
        // nextが実行されたあと、次のスケジューリングのタイミングになったとき。
        // 
    } else {
        // コミットに失敗したのでrunqueueにプッシュし、再度スケジューリングを行なっていく。
        PushRunqueue(next);
    }
}

★★★の部分の状況は、トランザクション成功時と失敗時で以下のように異なる。

# Per-CPU型とCentralized型

ghOStでは2種類のスケジューラを実装することができます。**Per-CPU型**と**Centralized型**です。

## Per-CPU型


Per-CPU型は、CPUごとにスケジューリングを行う方式で、Linuxカーネルのスケジューラと似ています（上図左）。各agentは各々のCPUのみを管理する、といった感じです。Per-CPU型の場合、メッセージキューはCPUごとに1つ用意されます。また、ghOStスレッドは1つのagentに紐付けられて管理され、状態変化などのメッセージはそのagentに向けて送信されます。

スレッドの数に偏りがある場合には、スレッドをagent間で移動するなどして負荷の分散を行うことも可能です。

## Centralized型

Centralized型は、1つのスケジューラがまとめて他のすべてのCPUの管理を行う方式です。ただ1つのagentスレッドが代表してスケジューラとして動き、他のagentスレッドはCPUをYieldし続けます。スケジューラとして動いているagentは **Global Agent** と呼ばれ、それ以外のagentは **Satellite Agent** と呼ばれます。

Centralized型では、Global Agent はメッセージキューを++ポーリング++により見張っています。そのため、Global CPU（Global Agent が動作するCPU）では常に Global Agent が動作している、といった感じになります。

## 図の補足（Enclaveについて）
上図にはEnclaveという単語が出てきます。
:::info
Enclaveとは「飛び地」の意味。
:::
Enclaveとは、システムのCPU資源をポリシーごとに分けて管理するためのものです。Enclave はいくつかのCPUをまとめて管理し、そこにスケジューラをアタッチする、といった使われ方をします。例えば、CPU0〜CPU3を管理するEnclaveを作成し、そのEnclave上でFIFOスケジューラを実行する、といった感じです。

システム上には複数のEnclaveを作成することができ、CPUを分けて別々のポリシーで管理することができるようになります。例えば、CPU0〜CPU2を管理する $\tt Enclvave_1$ と、CPU3を管理する $\tt Enclvave_2$ を作り、$\tt Enclvave_1$ ではCFSスケジューラを動作させ、$\tt Enclvave_2$ ではEDFスケジューラを動作させる、といった管理が簡単に行えるようになります。


Enclaveとは、**ポリシーを分けて管理するもの**、**複数のCPUをまとめて管理できるもの**、のように考えておけばよさそうです。

:::success
:dart: なお、ghost-userspace の実装ではEnclaveはもっと多機能なものとして抽象化されています。これは、ghost-kernel においてEnclaveがカーネルとのやり取りを行う窓口のようなものとして実装されているのが理由だと思います。詳しくは ghOStFS や ghost-userspace の実装を参照してください。
:::

# ghOStのメリット・デメリット
## メリット
ghOStの最大のメリットは**スケジューラの開発・実験のしやすさ**です。

まず第一に、<u>スケジューラは好きなプログラミング言語で開発することができます</u>。といっても ghost-userspace が C\+\+ 向けのしっかりとしたライブラリを提供しているため、C\+\+ 以外で実装することはあまりなさそうですが、カーネルの仕組みさえ理解してしまえば、Rustなどで実装することもできちゃいます。
:::info
ghost-userspaceのライブラリを利用すると、簡潔なスケジューラであれば二百行程度で書けます。その実装の中でもテンプレート的なものがあるので、ポリシー自体の実装は**百行以下**で書けたりします。
:::

また、ghost-kernel は<u>スケジューラが異常終了したときの対処もしっかりと実装されています</u>。スケジューラがクラッシュしたときは、そのスケジューラで管理されていたghOStスレッドをCFSに移動することで、システムに影響が起きないようになっているのです。これにより、スケジューラの開発サイクルが早くなるという利点があります。

最後のメリットとして、無停止アップグレードができる、という点が挙げられます。新しいスケジューラを動作させるために、いったんシステムを再起動する必要はありません。

## デメリット
ghOStのデメリットとしては、やはり性能面が考えられます。

ghOStでは、++スケジューラの処理の度にカーネルとユーザー空間の切り替えが行われる++ため、従来のスケジューラよりは性能面で劣っています。スケジューラのオーバーヘッドが大きいと、スループット性能が低下してしまうといった問題や、起床レイテンシが大きくなってしまうといった問題が発生してしまいます。

:::info
例えば、スケジューラの処理に数msかかってしまうと、「イベントが起きてから処理を開始するまでの時間を1ms以下に留めたい」という要件のあるワークロードなどに対応することができません。
:::

論文では、ghOStの実装によって生じるオーバーヘッドについての評価がされており、その評価結果によると、**ghOStはμスケールでのスケジューリングを実現するのに十分な性能を備えている**ことが示されています。カーネルのスケジューラと比べたときに、ghOStのオーバーヘッドに大きく起因している部分は、**カーネルモードとユーザーモードの切り替えが2度行われる部分**と、**メッセージ通信にかかる部分**です。論文での計測結果によると、どちらも処理にかかる時間は数百ns程度であることが分かっています。計測結果によれば、ghOStスケジューラのオーバーヘッドは既存のカーネルのスケジューラと比較してもわずかに高い程度であり、様々なワークロードに対応可能だと主張されています。

評価の内容に関して詳しくは論文を参照してみてください。

:::info
このようにμスケールでのスケジューリングを可能にするために、ghOStでは実装面でいくつかの工夫をしています。例えば、スケジューリングに必要なカーネル内の情報をagentに伝達する手段として共有メモリを採用しており、オーバーヘッドを小さくとどめています（愚直にファイルなどを経由して公開しようとするとオーバーヘッドが大きくなってしまう）。また、agentスレッドがスケジューラの仕事を行っている最中に他のスレッドにPreemptされてしまうと、それだけで大きなオーバーヘッドにつながってしまうため、agentスレッドは常に最高優先度で実行されるようになっていたりします。
:::

# システムコールとghOStFS

論文では、ghOStは様々なシステムコールを実装すると紹介されています。これらは、以下のような用途で使われます。
* 新しくEnclaveを作成する（表にはない）
* agentスレッドをEnclaveに登録する
* メッセージキューを新しく作成する
* トランザクションをコミットする
* etc...

ghost-kernel でも（名前が微妙に異なったりしますが）似たようなものがそれぞれ実装されています（実際にはもっと多くのシステムコールが実装されています）。これらのシステムコールは、専用のシステムコールを新しく実装するのではなく、<u>`/sys/fs/ghost` にghOSt専用のファイルシステムを作り、その中の疑似ファイルへの操作として実装されています</u>。疑似ファイルへの読み書きやIOCTLなどによってagentからカーネルへの要求が行われるのです。

詳しい内容はこの本の「ghOSt FS」の説明を参照してください。

# アーキテクチャ
ghOStの実装を支える重要な概念がいくつかあります。それぞれについて解説資料を書いたので、詳しくはそれぞれの該当資料を参照してください。

* GTID
* ステータスワード
* メッセージ
* トランザクション
* バリア
* ghOStFS

# このあとの資料の読み方
ghOStに関しては記事をいろいろと書いたので、どのように読んでいけばいいかを紹介します。

**アーキテクチャ**の部分では、ghOStで使われる重要な概念をまとめています。ここを最初に読むことをおすすめします。

また、実際にghOStスケジューラを動かしながら理解を深めていくには、「環境構築」を行い、**ユーザー空間ライブラリ**の「チュートリアル」を最初に進めていくといいと思います。スケジューラのコードは初期化処理が少し複雑になっています。「FIFOスケジューラの実装」のところで初期化処理について詳しく解説しているので、参考にしてみてください。