title: Code Gear と Data Gear を持つ Gears OS の設計
author: Mitsuki Miyagi, Shinji Kono
profile: 琉球大学
lang: Japanese
code-engine: coderay

# 研究目的

- 現代の OS では拡張性と信頼性を両立させることが要求されている。
<!--信頼性 信頼性を保証するには従来のテストとデバッグでは不十分-->
<!--信頼性を保証するには証明とモデル検査を用いる方法がある-->
- 信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
- ノーマルレベルの計算とメタレベルの計算を切り離して記述するために Code Gear と Data Gear という単位を用いている。
- Gears OS は Continuation based C(CbC) によってアプリケーションと OS そのものを記述する。
- 本研究では、CbC を用いた Gears OS の実装を示す。

<!--
# OS の拡張性と信頼性の両立

- さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。
- 時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。
- その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。
- これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。
- 検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。
- このため信頼性と拡張性を両立させることが重要である。
-->
<!--
# 目次？ 
-->

# メタ計算
- プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。
- メタ計算はノーマルレベルの計算から切り離して記述したい。
- そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。
- そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。

# Continuation based C (CbC) 
- Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。
- Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する。
- この goto 文による遷移を軽量継続と呼ぶ。
- CbC は軽量継続を持ち、C と互換性のある言語である。

# CbC のコード例
- CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
- Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
- goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する。
- この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。

```Code_Gear
__code cg0(int a, int b){
  goto cg1(a+b);
}

__code cg1(int c){
  goto cg2(c);
}
```

# Gears OS
- Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。
- 並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
- Input/Output Data Gear の依存関係が解決された Code Gear を並列実行する。

<div style="text-align: center;">
　<img src="./fig/normal.pdf" alt="MetaGear" width="600">
</div>

# Data Gear
- Data Gear は データの単位であり、int や文字列などの Primitive Type を持っている。
- Code Gear は任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
- Code Gear は接続された Data Gear 以外には参照を行わない。

# Gears でのメタ計算
- Gears OS ではメタ計算を Meta Code Gear、Meta Data Gear で表現する。
- Meta Code Gear はノーマルレベルの Code Gear の直後に遷移され、メタ計算を実行する。
- Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。

<div style="text-align: center;">
　<img src="./fig/meta.pdf" alt="MetaGear" width="600">
</div>

# Gears でのメタ計算の記述

- 各 Code Gear の引数は Data Gear である。
- code1, node2 は ノーマルな Code Gear であり、meta は Meta Code Gear である。

```code
__code code1 (struct Array* array) {
    ...
    goto code2(array);
}

__code meta(struct Context* context, enum Code next) {
    goto (context->code[next])(context);
}

__code code2(struct Array* array) {
    ...
}
```

# Gears OS の構成
- Gears OS は以下の要素で構成される。
    - Context 
        - 使用されるCode/Data Gear のリストを持っておりTaskでもある。  
    - TaskQueue 
        - Task のリストを扱う
    - TaskManager 
        - Task の依存関係の解決、作成や停止を行います。
    - Worker 
        - Task の実行を行う 

# Gears OS の構成図

<div style="text-align: center;">
　<img src="./fig/gears_structure.pdf" alt="gears_structure" width="900">
</div>

# Context
- Context とは使用される Code Gear と Data Gear を全て格納した Meta Data Gear である。
- Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。
<div style="text-align: center;">
　<img src="./fig/Gearef.pdf" alt="gearef" width="900">
</div>

# context の定義

```contexr
/* context define */
struct Context {
    int codeNum; //実行可能な Code Gear の数
    __code (**code) (struct Context*); //実行可能な code Gear のリスト
    void* heapStart; //Data Gear の Allocate用のヒープ
    void* heap;
    long heapLimit;
    int dataNum; //Data Gear の数
    union Data **data; //Data Gear のリスト
};
```

#Context
- Code/Data Gear の名前は enum で定義される。
- Code/Data Gear の名前とポインタの対応は enum を使って行われる。 

```code
enum Code {
    C_cg1,
    C_cg2,
};
```

```data
enum Data {
    D_dg1,
    D_dg2,
};
```

# Data Gear の定義
- Data Gear は union と struxt を用いて定義される
- これをもとに必要な Data Gear の allocate を行う

```data
union Data {
    struct Time {
        enum Code next;
        double time;
    } time;
    struct LoopCounter {
        int i;
    } loopCounter;
    ...
};
```


<!--
# CbC による Gears OS 記述の問題点
- Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
- 本研究ではこれらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
- そのためのプロトタイプとして perl スクリプトを作成した。
-->

# Interface
- Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
- Interface は使用される Data Gear の定義と、それに対する Code Gear の集合である。
- Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。

# Interface のコード
```interface
typedef struct Stack<Type, Impl>{
        union Data* stack;
        union Data* data;
        union Data* data1;
        __code whenEmpty(...);
        __code clear(Impl* stack,__code next(...));
        __code push(Impl* stack,Type* data, __code next(...));
        __code pop(Impl* stack, __code next(Type* data, ...));
        __code pop2(Impl* stack, __code next(Type* data, Type* data1, ...));
        __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
        __code get(Impl* stack, __code next(Type* data, ...));
        __code get2(Impl* stack, __code next(Type* data, Type* data1, ...));
        __code next(...);
} Stack;
```

# Interface の実装例

```impl
Stack* createSingleLinkedStack(struct Context* context) {
    struct Stack* stack = new Stack();
    struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
    stack->stack = (union Data*)singleLinkedStack;
    singleLinkedStack->top = NULL;
    stack->push = C_pushSingleLinkedStack;
    stack->pop  = C_popSingleLinkedStack;
    stack->pop2  = C_pop2SingleLinkedStack;
    stack->get  = C_getSingleLinkedStack;
    stack->get2  = C_get2SingleLinkedStack;
    stack->isEmpty = C_isEmptySingleLinkedStack;
    stack->clear = C_clearSingleLinkedStack;
    return stack;
}
```

# Interface の実装例

```impl
__code pushSingleLinkedStack(struct SingleLinkedStack* stack, 
                                union Data* data, __code next(...)) {
    Element* element = new Element();
    element->next = stack->top;
    element->data = data;
    stack->top = element;
    goto next(...);
}

```
<!-- 

<div style="text-align: center;">
　<img src="./images/multiComponent.pdf" alt="message" width="600">
</div>

-->

# stub Code Gear 

- Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。
- しかし、Meta Data Gear である Context をノーマルレベルの Code Gear から直接アクセスするのはよろしくない。
- そこで Context から必要なデータを取り出して Code Gear に接続する、メタレベルの stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。

# stub Code Gear の例
```stub
__code clearSingleLinkedStack(struct Context *context,
                    struct SingleLinkedStack* stack,enum Code next) {
    stack->top = NULL;
    goto meta(context, next);
}

__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack = 
                (SingleLinkedStack*)GearImpl(context, Stack, stack);
        enum Code next = Gearef(context, Stack)->next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

# Context、stub Code Gear の自動生成
- Gears OS ではノーマルレベルの計算の他に Context や stub などのメタ計算を記述する必要がある。
- 現在の CbC で Gears OS を記述すると、このメタ計算の記述も行わなくてはならず、これには多くの労力を要する。
- この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。


# stub Code Gear の生成
- stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
- stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
- generate_stub は指定された cbc ファイルの __code で記述された Code Gear を取得。
- Code Gear の引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
- cbc ファイルの Code Gear から、生成した stub Code Gear を加えたファイルを生成する。

# 生成された stub Code Gear

```stub
__code clearSingleLinkedStack(struct Context *context,
                    struct SingleLinkedStack* stack,enum Code next) {
    stack->top = NULL;
    goto meta(context, next);
}

__code clearSingleLinkedStack_stub(struct Context* context) {
        SingleLinkedStack* stack = 
                (SingleLinkedStack*)GearImpl(context, Stack, stack);
        enum Code next = Gearef(context, Stack)->next;
        goto clearSingleLinkedStack(context, stack, next);
}
```

# Context の生成

- generate_context は context.h から Data Gear、generate_stub から生成されたファイルから Code Gear を取得し、以下を生成する。
    - Code/Data Gear を enum で定義した enumCode.h、enumData.h
    - 取得した Code/Data Gear から Context の生成を行う target-context
    - Context を生成する際の Data Gear の Allocation を行う dataGearInit.c

<div style="text-align: center;">
　<img src="./fig/generate_context3.pdf" alt="generate_context3" width="600">
</div>

# 今後の課題
- 本研究では CbC を用いた Gears OS の記述、CbC ファイルから Gears OS の記述に必要な Meta の生成を行う perl スクリプトの作成を行なった。
- これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
- 今後の課題は今回 perl スクリプトによって Context や stub を含むファイルの生成を行なったが、LLVM/clang 上で実装しコンパイラから直接 CbC を実行できるようにすることを目的とする。
- また、xv6 を Gears OS での書き換えや、継続ではスタックは積まないため、スタックトレースを使わない手法でのデバッグの考案などもある。

[](プロシン発表時間 セッション7 1/21 10:40 - 12:00)