%TODO stub のこうで書きすぎ
% context と stub はジェネラルな紹介だけ

\chapter{Gears OS の概念}
Gears OS は信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に開発している OSである。

Gears OS は処理の単位を Code Gear、データの単位を Data Gear と呼ばれる単位でプログラムを構成する。
信頼性や拡張性はメタ計算として、通常の計算とは区別して記述する。

本章では Gears OS を構成する様々な要素について説明する。

\section{Code GearとData Gear}
Gears OS はプログラムとデータの単位として Gear を用いる。
Gear は並列実行の単位、データの分割、Gear 間の接続等になる。

Code Gear はプログラムの処理そのもので、\figref{cdg1} で示しているように任意の数の Input Data Gear を参照し、処理が完了すると任意の数の Output Data Gear に書き込む。
また、Code Gear は接続された Data Gear 以外には参照を行わない。
この Input / Output Data Gear の対応から依存関係を解決し、Code Gear の並列実行を可能とする。

Code Gear 間の移動は継続を用いて行われる。
継続は関数呼び出しとは異なり、呼び出し元に戻らず、Code Gear 内で次の Code Gear への継続を行う。
そのため Code Gear、Data Gear を使ったプログラミングは末尾再帰を強制したスタイルになる。

Gear の特徴として処理やデータの構造が Code Gear、Data Gear に閉じていることにある。
これにより、実行時間、メモリ使用量などを予想可能なものにする事が可能になる。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.6]{./fig/codegear-datagear.pdf}
    \end{center}
    \caption{Code Gear と Data Gear の関係}
    \label{fig:cdg1}
\end{figure}

また Gears OS 自体もこの Code Gear、Data Gear を用いた CbC(Continuation based C) で実装される。
そのため、Gears OS の実装は Code Gear、Data Gear を用いたプログラミングスタイルの指標となる。

\section{Continuation based C}
Gears OS の実装は本研究室で開発されている CbC(Continuation based C) を用いて行う。
CbC は Code Gear を基本的な処理単位として記述できるプログラミング言語である。
CbC の処理系として LLVM\cite{llvm}/Clang と GCC による実装が存在する\cite{kaito-lola}\cite{nobu-prosym}。

CbC の記述例を\coderef{cg1}に、 実際にこのソースコードが実行される際の遷移を\figref{cg1}に示す。
CbC の Code Gear は \_\_code という型を持つ関数として記述する。
Code Gear は継続で次の Code Gear に遷移する性質上、関数とは違い戻り値は持たない。
そのため、\_\_code は Code Gear の戻り値ではなく、Code Gear であることを示すフラグとなっている。
Code Gear から次の Code Gear への遷移は goto 文による継続で処理を行い、次の Code Gear への引数として入出力を与える。
\coderef{cg1}内の goto cg1 (a+b); が継続にあたり、(a+b) がcg1 への入力になる。

\lstinputlisting[caption=Code Gearの軽量継続, label=code:cg1]{./src/cg1.cbc}

CbC の goto 文による継続は Scheme のcall/ccといった継続と異なり、呼び出し元の環境を必要とせず、行き先を指定すれば良い。
この継続を軽量継続と呼ぶ。
\coderef{cg1} は cs0 から cs1 へ継続したあとには cs0 へ戻らずに処理を続ける。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=1.0]{./fig/goto.pdf}
    \end{center}
    \caption{goto 文による Code Gearの軽量継続}
    \label{fig:cg1}
\end{figure}

\section{メタ計算}
プログラムの記述する際は、ノーマルレベルの計算の他に、メモリ管理、スレッド管理、CPUがGPUの資源管理等を記述しなければならない処理が存在する。
これらの計算はノーマルレベルの計算と区別してメタ計算と呼ぶ。

メタ計算は関数型言語では Monad\cite{moggi-monad} を用いて表現される\cite{kkb-sigos}。
Monad は Haskell では実行時の環境を記述する構文として使われる。

従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。
実行時にメタ計算の変更を行う場合には OS 内部のパラメータの変更を使用し、実行されるユーザープログラム自体への変更は限定的である。
しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で実際のシステムコール単位では不十分である。
例えば、モデル検査ではアセンブラあるいは バイトコード、インタプリタレベルでのメタ計算が必要になる。
しかし、バイトコードレベルでは 粒度が細かすぎて扱いが困難になっている。具体的にはメタ計算の実行時間が大きくなってしまう。

\section{Meta Gear}
Gears OS の Code Gear は関数に比べて細かく分割されているため、メタ計算をより柔軟に記述できる。
Code Gear と Data Gear にはそれぞれメタ計算の区分として Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実装する。
Meta Gear は 制限された Monad に相当し、型付きアセンブラよりは大きな表現単位を提供する。
Haskell などの関数型プログラミング言語では実行環境が複雑であり、実行時の資源使用を明確にすることができないが、Gears OS を記述している CbC はスタック上に隠された環境を持たないので、メタ計算で使用する資源を明確にできる利点がある。
Meta Code Gear は\figref{mcg1}に示すように通常の Code Gear の直後に遷移され、メタ計算を実行する。
また、Meta Code Gear は、その階層からさらにメタ計算を記述することが可能である。

\begin{figure}[htbp]
    \begin{center}
        \includegraphics[scale=0.8]{./fig/meta_cg_dg.pdf}
    \end{center}
    \caption{Meta Code Gear の実行}
    \label{fig:mcg1}
\end{figure}

\section{Context}
Context とは一連の実行で使用される Code Gear と Data Gear の集合である。
従来のスレッドやプロセスに対応する。
Context は接続可能な Code/Data Gear のリスト、Data Gearを確保するメモリ空間、実行される Task への Code Gear等を持っている Meta Data Gearである。
Gears OS では Code Gear と Data Gear への接続を Context を通して行う。

\coderef{context} に Context の定義を示す。

\lstinputlisting[caption=Contextの定義, label=code:context]{./src/context.h}

\coderef{context} は以下の内容を定義している。

\begin{itemize}
    \item Code Gear の名前と関数ポインタとの対応表

        Code Gear の名前とポインタの対応は Context 内の code(\coderef{context} 5行目) に格納される。
        code は全ての Code Gear を列挙した enum と関数ポインタの組で表現される。
        Code Gear の名前は enum で定義され、コンパイル後には整数へと変換される。
        実際に Code Gear に接続する際は番号(enum)を指定することで接続を行う。
        これにより、メタ計算の実行時に接続する Code Gear を動的に切り替えることが可能となる。
    \item Data Gear の Allocation 用の情報

        Data Gear のメモリ空間は事前に領域を確保した後、必要に応じてその領域を割り当てることで実現する。
        実際に Allocation する際は Context内の heap(\coderef{context} 8行目)を Data Gear のサイズ分インクリメントすることで実現する。
    \item Code Gear が参照する DataGear へのポインタ

        Allocation で生成した Data Gear へのポインタは番号を割り振り、Context 内のdata(\coderef{context} 6行目) に格納される。
        Code Gear は data から番号を指定して Data Gear へアクセスする。
    \item 並列実行用の Task 情報

        Context は 並列実行の Task も兼任するため、待っている Input Data Gear のカウンタ、Input/Output Data Gear が格納されている場所を示すインデックス、GPU での実行フラグ等を持っている(\coderef{context} 13-30行目)。
    \item Data Gear の型情報

        Data Gear は構造体を用いて定義する(\coderef{context} 34-49行目)。Timer や TimerImplなどの構造体が Data Gear に相当する。
        メタ計算では任意のData Gear を一律に扱うため、全ての Data Gear の共用体を定義する(\coderef{context} 33-51行目)。
        Data Gear を確保する際のサイズはこの型情報から決定する。
\end{itemize}

\section {stub Code Gear}
stub Code Gear は Code Gear の接続の間に挟まれる Meta Code Gear である。
ノーマルレベルの Code Gear から Meta Data Gear である Context を直接参照してしまうと、ユーザがメタ計算をノーマルレベルで自由に記述できてしまい、メタ計算を分離した意味がなくなってしまう。
stub Code Gear はこの問題を防ぐため、Context から必要な Data Gear のみを ノーマルレベルの Code Gear に渡す処理を行っている。

stub Code Gear は使用される全ての Code Gear 毎に記述する必要がある。
しかし、全ての Code Gear に対して stub Code Gear を記述するのは膨大な記述量になってしまうため、後述する Interface を実装した Code Gear のstub Code Gear はスクリプトで自動生成する。

stub Code Gear はユーザーが自前で記述することも可能である。
つまり、ユーザーがメタ計算を記述することができる。
stub Code Gear を用いたメタ計算の例として、本来 stub Code Gear は対応した Code Gear に継続するが、自前で stub Code Gear を記述することで、継続先を柔軟に変更できる。