\chapter{Gears OS の概念}
Gears OS\cite{kkb-master} は信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に開発している 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=CodeSegmentの軽量継続, 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.7]{./fig/meta_cg_dg.pdf}
    \end{center}
    \caption{Meta Code Gear の実行}
    \label{fig:mcg1}
\end{figure}

\section{Context}
Context は接続可能な Code/Data Gear のリスト、Data Gearを確保するメモリ空間、実行される Task への Code Gear等を持っている Meta Data Gearである。
Gears OS では Code Gear と Data Gear への接続を Context を通して行う。

また、Context は並列実行の Task でもあり、従来のスレッドやプロセスに対応する。
そのため Gears OS で並列実行を行うには Context を生成し、Task の実行を行う。

\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} 4行目) に格納される。
        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 に渡す処理を行っている。

\coderef{stubCodeGear} に stub Code Gear の例を示す。
stub Code Gear は使用される全ての Code Gear 毎に記述する必要がある。
しかし、全ての Code Gear に対して stub Code Gear を記述するのは膨大な記述量になってしまうため、後述する Interface を実装した Code Gear などの型が決まっており、引数が格納されている場所がわかる stub Code Gear はスクリプトで自動生成する。

\lstinputlisting[caption=stub Code Gear, label=code:stubCodeGear]{./src/stubCodeGear.cbc}

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