\chapter{GearsOS}
GearsOS のメタレベルのプログラムはPerlスクリプトによるトランスコンパイラにて自動生成されるように構成されている。
基本的にユーザーはノーマルレベルのプログラムの記述のみ行う。
メモリ管理あるいはプロセス、あるいは検証やモデル検査はメタレベルで分離する仕組みとなっている。
プログラマは.cbcファイルに対して記述を行うことでプログラムの構成い、
実際に動作するプログラムはトランスコンパイラによりmeta部分の記述追加した.cファイルが動作する。

\section{Interface}
GearsOSの重要な仕様としてInterfaceが存在する。Interaceは DataGear をCの構造体として定義し、
そのDataGearを操作する method のAPI(codeGearの型)を提供する。これは Java などの
Interfaceのモジュール化の仕組みと同様の役割を持つ。

CbCはstackをもたないので、APIで呼び出された引数はstackではなく、プロセスごとのContextというmetaDataGear
に置かれる。つまり引数はInterface構造体の中にすべて用意される。これはAPIなので、
DataGearの中身に相当するDataGearが別に動的に確保する必要がある。これはDataGearの実装であり Impl として
別に用意する。つまり、同じAPIだが、異なる実装を持つ DataGear がある。例えば、SingleLinkedQueue と SyncrhonizedQueueu などが
そういうものである。

GearsOSに実装されているQueueのInterfaceをソースコード\ref{src:Queue.h}に示す。

\lstinputlisting[label=src:Queue.h, caption=Queueのインターフェース]{src/Queue.h}

\texttt{\_\_code}codeで始まる5から10行目はCodeGearの宣言である。
2, 3行目のunion Data型の変数はAPIのCodeGearで使用されるDataGearを記述する。

コード内のCodeGearの第1引数はImpl*型の変数となっており、Interfaceを実装するImplementへのポインタとなる。
CbCはスタックを持たず、複数のCodeGear間をまたいで必要な情報はDataGearのポインタとして持ち運ぶ必要がある。

このInterfaceは以下のように呼び出される。queue はInterfaceへのポインタで、そのAPIであるputを
呼び出す。queue は引数を格納するための構造体で、実装はその中にポインタを通して格納されている。
この構造体は呼び出し毎に書き換えられるので再帰的に使うことはできない。つまり、CbCのInterface
は基本的にループであって、再帰呼び出しを行うには明示的にスタックを用意する必要がある。

\begin{lstlisting}[frame=lrbt,caption={Interfaceの呼び出し}]
    goto queue->put(task, next(...));
\end{lstlisting}

\texttt{\_\_code next(...)}は
そのCodeGearが呼び出される際に入力される別のCodeGearへのポインタであり、
そのAPIのCodeGearの処理後の遷移先のCodeGearを指定することができる。...の意味は
呼び出した引数の構造体を全部含んでいるということで、関数型プログラミングのclosureに近いが、
再帰しないという違いがある。一段だけの関数呼び出しだと思ってもよい。
\texttt{\_\_code whenEmpty(...)}も同様に別CodeGearへのポインタである。
9行目のCodeGearではnextとWhenEmptyと二つのCodeGearのポインタを入力することにより、
処理の結果に応じた複数の遷移先を用意するように構成している。これによりCbCの例外処理を
きれいに記述することができる。Javaのtry/catchのような仕組みは必要ない。

Interfaceと同様にImplementationもDataGearである。
Context内では使用するInterfaceやImplementで定義する
すべての構造体は共用体(union)のData型に登録されている。
InterfaceはDataGearもしくはCodeGearの一時的な保管場所で、Implementationは持続的な保管場所である。

実際には CodeGear/DataGear は、Context内ですべて番号で管理されているので、メタ側から
全部に均等にアクセスすることができる。これにより、OSのプロセス管理、あるいはモデル検査などを
MetaDataGearであるContextを処理する MetaCodeGearとして定義できる。


\section{Implementation}
GearsOSはInterfaceの実装となるImplementの型定義ファイルが実装されている。
Implementationの定義にはInterfaceと同様にヘッダファイルを記述する。
ソースコード\ref{src:SynchronizedQueue.h}にQueueインターフェースの実装の型定義となるSynchronizedQueue.hを示す。
Implementationは実装元のInterfaceを必ず決定する必要があるため、1行目のようにimpl名の後に実装元のInterface名を記述する必要がある。

作成したImplementationは実装元のInterface名のImpl型として使用することが可能となり、
Impl内で記述した変数は後述のコンストラクタで行われる処理によって、プログラム上でimpl*型変数\texttt{->}変数名で参照が行えるようになる。
また、GearsOSは全てのInterface, Implの情報を構造体としてコンパイルする際にContextに記録するため、
ソースコード中2,3,4行ではImplに別のInterfaceを構造体として記述することで、
プログラム内で他のInterfaceを実装したプログラム、もしくはInterfaceを純粋な構造体として呼び出すことができる。

\lstinputlisting[label=src:SynchronizedQueue.h, caption=Queue.hの実装となるSynchronizedQueue.h]{src/SynchronizedQueue.h}

\section{GearsOSのプログラム例}
GearsOSのプログラムの一例として先述したソースコード\ref{src:Queue.h}、\ref{src:SynchronizedQueue.h}をInterface,Implementとして継承した
SynchronizedQueue.cbcの一部分をソースコード\ref{src:SynchronizedQueue.cbc}に示す。
GearsOSにはImplementが記述されたヘッダファイルから、cbcファイルの雛形を自動生成するimpl2cbc.plが導入されている。
雛形には7行目のQueue*を返すcreateSychronizedQueueとその中の処理、
加えて22行目のputSynchronizedQueueのようなInterfaceのヘッダファイル内で記述されたCodeGearが用意されている。

プログラム内で呼び出したいInterfaceは2,3行目のような記述が必要となる。
7から20行目に記述されているcreateSynchronizedQueueはQueueインターフェースをSynchronizedQueueで実装する際のコンストラクタである。
関数呼び出しで実装されており、返り値はInterfaceのポインタである。

コンストラクタ内の記述を解説すると、8,9行目にてQueueとSynchronizedQueueのアロケーションを行い、
14行目の記述にてQueueInterface内のDataGearであるqueueへSynchronizedQueueへのポインタを格納している。
8, 10行目でnew演算子が使われているがこれはGearsOS独自のシンタックスの一つである。
コンパイル時に後述のContextが持つDataGearのヒープ領域のアロケーションを行うマクロへ置き換えられる。
10から13行目の記述では初期はImplementの型定義ファイルに記述された変数の宣言が行われている。
当然プログラマは、宣言した変数に任意の状態が設定されるように変更することができる。
13行目ではatomic型のinterfaceをAtomicReference型で呼び出している。
15から18行目はInterfaceの定義にて記述されたAPIとcbcプログラム内のCodeGearの紐付けを行っている。

\lstinputlisting[label=src:SynchronizedQueue.cbc, caption=SynchronizedQueue.cbcの記述の一部]{src/SynchronizedQueue.cbc}

22行目から38行目はInterfaceで宣言されたputAPIの実装部分である。
Interfaceで宣言されたAPIと対応するCodeGearは.cbcファイル上ではAPI名 + Impl名で宣言する必要がある。
コンストラクタ内13行目にてatomicReferenceの呼び出しを行っているが、atomicInterfaceへのポインタは最終的に返り値のqueueが保持しているため、
atomicInterfaceで定義されたAPIのCodeGearへ遷移することができるようになる。
現状のGearsOSでは一度、Interfaceのポインタ型をプログラム内で宣言し、コンストラクタで生成した実装のポインタを代入、
そしてgoto文を用いて遷移するという冗長な記述が必要となっているため、トランスコンパイラにより改善するといった手段が考えられる。


\section{Context}
ContextとはGearsOSにおける従来のOSのプロセスに相当する概念であるとされる。
英単語としてのcontextは意味として前後関係や状況、環境を意味し、
軽量継続を主体として処理が行われるGearsOSにおいて、Contextは継続に必要なデータ(CodeGear, DataGear)を全て保持している。
GearsOSではCodeGearの遷移の際にこのContextに対してDataGearの一時的な書き込みや、遷移先のポインタなどの情報を書き込み、
Contextを持ち運ぶことにより処理の整合性を保っている。
ノーマルレベルのプログラム上では意識することは少ないが、
メタレベルでは全てのCodeGearは必ずContextをDataGearとして呼び出す仕組みとなっている。
そのためContextはGear概念で言うとMetaDataGearに相当する。

図\ref{fig:context}にCodeGearが遷移する際のContextに対するDataGearの書き込みまたは呼び出しを示す。
CodeGearが遷移する際にOutputDataGearをContextに対して書き込みを行う。
続いて遷移先のstubCodeGearがContextから遷移先CodeGearが必要とするInputDataGear
と出力する必要があるOutputDataGearを参照する。
stubCodeGearでDataGearの準備が完了したあと、本体のCodeGearへ遷移し処理により出力されたデータをOutPutDataGearとして書き出す。
以上の手順で軽量継続の際にContextの参照が行われる。

Contextはノーマルレベルから直接参照を行わない。
Contextをユーザーが自由に操作できると、ノーマルレベルとメタレベルの分離した意味が無くなってしまうためである。
Contextに対するDataGearの操作はstubCodeGearのみならずCodeGear内でも行われるが、それらの記述はトランスコンパイラの自動生成により行われる。
先述のnew演算子がその一例として挙げられる。
もしnew演算子でなく、直にContextの操作が行えてしまうと、
並行に動作している他のUser Contextの中身を書き換えるなどプログラム処理に支障が出るような不正な改ざんが行えてしまう。

\begin{figure}[tb]
    \begin{center}
        \includegraphics[width=150mm]{./images/Context_ref.pdf}
    \end{center}
    \caption{CodeGearの遷移にて行われるContextに対するDataGear参照}
    \label{fig:context}
\end{figure}

Contextはプロセスに相当するため、ユーザープログラムごとにContextが存在する。
このContextをUser Contextと呼ぶ。
また実行されているGPUやCPUごとにもContextが必要となり、これをCPU Contextと呼ぶ。
加えてOSとしてUser ContextやCPU Contextを含めた、全体を管理するためのContextも必要となる。
これはKernel ContextやKContextと呼ばれている。
これらのContextは特に、GearsOSに実装されているpar gotoと呼ばれる並列処理用の構文の内部構成などのメタレベルのプログラミングの際に強く意識する必要がある。
GearsOSではKernelContextが複数のUser ContextとCPU Contextを管理し、
ノーマルレベルのプログラムに応じてWorkerに対してTaskを割り振ることで分散処理の機構が実現されている。

\section{トランスコンパイル後の実行プログラム}
先にも述べたように、GearsOS上で記述するプログラムは拡張子が.cbcとなるcbcファイルへ記述を行う。
しかし、実際の動作ファイルはcbcをPerlスクリプトによりトランスコンパイルによりstubCodeGearなどのメタレベルの処理やマクロの書き換えがされた、
拡張子.cファイルとなる。
ソースコード\ref{src:SynchronizedQueue.c}にSynchronizedQueue.cbc(ソースコード\ref{src:SynchronizedQueue.cbc})をトランスコンパイルした結果出力された
SyncheonizedQueue.cの一部である。

cbcからのc言語へのトランスコンパイルはノーマルレベルと分離したいメタレベルの記述が追加、もしくは置き換えが行われる。
GearsOSプログラミングではユーザープログラマは出力後の.cファイルについて、つまりメタレベルに対して意識する必要がなくなるのが理想である。
しかし、開発者側はトランスコンパイラの新たなシンタックスの導入やデバッグ、メタレベルの処理の置き換えなどメタ部分の処理の知識を持つべきである。
また、現状のトランスコンパイラは意図しないバグを持っている可能性があるため、通常のユーザプログラムのデバッグなどの際にも.cファイルを確認する機会がある。

ソースコード\ref{src:SynchronizedQueue.c}中の53行目から58行目までのputSynchronizedQueue\texttt{\_}stubは、cbcファイルに記述されたputSynchronizedQueueの
stubCodeGearである。
stubCodeGearは元のCodeGear名 + \texttt{\_}stubで宣言される。
stubCodeGearはinputDataGearとしてContextを要求する。
54行目ではGearImplマクロを用いてInterfaceの実装型のポインタをContextから呼び出す。
55, 56行目に記述されているGearefマクロはcontextのInterface内で宣言されているDataGearを参照するマクロである。
55行目の場合、QueueInterface内で宣言されているDataGearであるdataを呼び出している。
56行目では共用体として取り扱われているnextCodeGearを呼び出す。
CodeGear本体に必要なinputDataGearをimplで呼び出してから本体のCodeGearへ遷移する。

本体のCodeGearでは、ノーマルレベルでの操作を禁止したいContextに対する操作が追記される。
gotoによる遷移の直前では、遷移先のCodeGearに対して出力するDataGearをContextに対して書き戻すための処理が行われる。
34行目から39行目などに見られるように、ContextのDataGearの保存場所に対する書き込みの際にもGearefマクロが使われる。
GearefコマンドはGearef(Context名、Interface名)\texttt{->}DataGear名で指定される。
また、GearsOS独自のnew演算子はContextのDataGearの保存場所に対してメモリ確保を行うマクロであるALLOCATEに書き換えられる。


\lstinputlisting[label=src:SynchronizedQueue.c, caption=SynchronizedQueue.c]{src/SynchronizedQueue.c}

\section{SynchronizedQueue}
GearsOSには先行研究\cite{gears}にてGearsシンタックスを用いて実装されたQueueが存在している。
Queueは単純なQueueとしての機能を実装したSingleLinkedQueueと、
マルチスレッドによる複数のプロセスからのアクセスにも対応するためのSynchronizedQueueが存在する。

SynchronizedQueueは複数のプロセスからのアクセスが発生した際のデータの一貫性の保証方法として、
CAS(Check and Set, Compare and Swap)を採用している。
CASは値の比較、更新をアトミックに行う命令である。
CASは更新前と更新後の値を受け取り、更新前の値と書き換え先のメモリ番地の実際の値と比較し、同じだった場合、
データ競合がないため、データの更新を行う。値が異なった場合は他のプロセスから書き込みが行われたとみなされ、値の更新に失敗する。

GearsOSではCASを行うためのInterfaceをAtomicとして定義している。
AtomicのInterfaceをソースコード\ref{src:Atomic.h}に示す。
ptrはデータ格納先のポインタのポインタ、oldData,newDataはそれぞれ更新前の値と更新後の値を示す。
\texttt{\_\_}code nextにはCASが成功した場合の遷移先を、\texttt{\_\_}code failには失敗した場合の遷移先のCodeGearを指定する。

SynchronizedQueueではデータのputもしくはtakeの際、要素の先頭もしくは最後尾の要素のアドレスに対してCASが行われる(ソースコード\ref{src:SynchronizedQueue.cbc})

\lstinputlisting[label=src:Atomic.h, caption=Atomic.h]{src/Atomic.h}