\chapter{Continuation based C}
Continuation based C(CbC)\cite{cbcllvm,cbc}とはCの下位言語である．
function callの代わりにgotoによる継続を用いる．
CbCのプログラムはCodeGearと呼ばれる処理の単位で記述し，ノーマルレベルとメタレベルの処理を切り分けることが可能である．

\section{CodeGearとDataGear}
CbCでは関数の代わりにCodeGearという単位でプログラミングを行う．
CodeGearは\emph{\_\_code}という記述で宣言することができる．
データの単位にはDataGearと呼ばれる変数データを用いる．
図\ref{fig:dgcg}はCodeGearとDataGearの関係を表している．
CodeGearはDataGearを入力として受け取り，別のDataGearに書き込み出力することができる．
特に入力のDataGearをInput DataGear，出力のDataGearをOutput DataGearと呼ぶ．
gotoで次のCodeGearに遷移することができ，その際Output DataGearを次のCodeGearのInput DataGearとして渡すことができる．
\begin{figure}[h]
  \begin{center}
      \includegraphics[width=120mm]{figs/dgcgdg.png}
  \end{center}
  \caption{CodeGearとDataGearの関係}
  \label{fig:dgcg}
\end{figure}

\section{軽量継続}
CodeGearから次のCodeGearに遷移していく一連の動作を継続と呼ぶ．
通常の関数の場合，関数から次の関数へ遷移する時にfunction callが行われる．
function callは前の関数へ戻る場合があり，そのためにcall stackを保存する．
CbCの継続はfunction callをせずにgotoによるjmpで行われる．
jmpはfunction callと異なり，call stackのような環境を保存しない．
よってCbCの継続は関数の繊維と比較して軽量であるといえる．
そのことからCbCにおける継続をfunction callにおける継続と区別して，軽量継続と呼ぶ．

\section{CbCの記述例}
CbCのプログラム例をソースコード\ref{src:cbc}に示す．
まずmain関数においてadd1 CodeGearへgotoを行う．
その際add1へInput DataGearとしてnを渡す．
Cのgotoが\emph{goto label;}という記法で，ラベリングした箇所へjmpを行うのに対し，
CbCのgotoは\emph{goto add1(n);}という記法で，add1 CodeGearへn DataGearを渡してjmpを行う．
add1は処理の最後にadd2 CodeGearへgotoを行う．
その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進める．

\lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}


\chapter{GearsOS}
GearsOS\cite{gears,gearsos,cr}は 信頼性と拡張性の両立を目的として，開発されている．
Gearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ．
軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する．
ノーマルレベルとメタレベルの処理を切り分けることができ，同様にGearの概念を持つCbC(Continuation based C)で記述されている．
GearsOSは現在開発途上であり，OSとして動作するために今後実装しなければならない機能がいくつか残っている．

\section{stubCodeGear}
図\ref{fig:meta-cgdg}はCodeGearの遷移とMetaCodeGearの関係を表している．
OSのプログラムはユーザーが実際に行いたい処理を表現するノーマルレベルと，
カーネルが行う処理を表現するメタレベルが存在する．
ノーマルレベルで見るとCodeGearがDataGearを受け取り，
処理後にDataGearを次のCodeGearに渡すという動作をしているように見える．
実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，
それらの計算はMetaCodeGearで行われる．
その際，MetaCodeGearに渡されるDataGearのことは特にMetaDataGearと呼ばれる．
CodeGearの前に実行されるMetaCodeGearは特にstubCodeGearと呼ばれ，
メタレベルを含めるとstubCodeGearとCodeGearを交互に実行する形で遷移していく．
\begin{figure}[h]
  \begin{center}
      \includegraphics[width=100mm]{figs/meta-cg-dg.pdf}
  \end{center}
  \caption{CodeGearとMetaCodeGearの関係}
  \label{fig:meta-cgdg}
\end{figure}

\section{Context}
ContextはGearsOS上全てのCodeGear，DataGearの参照を持ち，CodeGearとDataGearの接続に用いられる．
OS上の処理の実行単位で，従来のOSにおけるプロセスに相当する機能であるといえる．
CodeGearをDataGearの一種であると考えると，
ContextはGearの概念ではMetaDataGearに当たる．
Contextはノーマルレベルから直接参照されず，必ずMetaDataGearとしてMetaCodeGearから参照される．
ノーマルレベルのCodeGearがContextを直接参照してしまうと，
メタレベルを切り分けた意味がなくなってしまうためである．

図\ref{fig:context}はContextを参照する流れを表したものである．
まずCodeGearがOutputDataGearへデータをoutputし，次のstubCodeGearへContextを参照しgotoを行う．
この際直接参照はせず，goto metaを経由しgotoを行う．
stubCodeGearはInputDataGear(前のCodeGearのOutputDataGear)とOutputDataGearを参照し，次のCodeGearへgotoを行う．
CodeGearでの処理後，OutputDataGearへデータをoutputし，次のstubCodeGearへgotoを行う．

Contextはいくつかの種類に分けることができる．
OS全体のContextを管理するKernel Contextやユーザープログラムごとに存在するUser Context，
CPUやGPUごとに存在するCPU Contextがある．
\begin{figure}[h]
  \begin{center}
      \includegraphics[width=130mm]{figs/context.png}
  \end{center}
  \caption{Contextを参照する流れ}
  \label{fig:context}
\end{figure}

\chapter{Christie}
Christieは当研究室で開発を行っているJavaで記述された分散フレームワークである．
CbCと似ているが別物のGearという概念や，任意のTopologyを形成するためのTopologyManagerがある．

\section{Gearの概念}
Christieには以下の4つのGearという概念が存在する．

\begin{itemize}
  \item CodeGear
  \item DataGear
  \item CodeGearManager（以下CGM）
  \item DataGearManager（以下DGM）
\end{itemize}

CodeGearはクラスやスレッドに相当する．DataGearは変数データに相当し，Javaのアノテーションを用いて記述される．
CGMはいわゆるノードに相当し，CodeGear，DataGear，DGMを管理する．
複数のCGM同士が配線され，DataGearを送信し合うことで分散処理を実現している．
DGMはDataGearを管理しているもので変数プールに相当する．

\section{DataGearManager}
DataGearManagerはkey value storeの構造を持つ．
CGMが利用するCGのkeyとputされたDataGearの組み合わせでDataGearを管理する．
DGMはLocalDGMとRemoteDGMに区別することができる．
LocalDGMはCGM自身が所持するDataGearのプールである．
ReomoteDGMはCGMが配線されている別のCGMがもつDGのプールである．

\section{Topology-Manager}
Christieには任意のtopologyを生成し，ノード同士の通信接続を管理ことができるTopology-Managerという機能が存在する．
Topology-Managerで生成できるtopologyには静的topologyと動的topologyの2つがある．
静的topologyはプログラマが任意のtopologyとノードの配線を行うことができる．
dotファイルにノードの配線を記述し，Topology-Managerに参照させることで生成する．
dotファイルに記述したノードの数と参加ノードの数が一致した場合に動作する．
動的topologyは参加を表明したノードに対し，自動的に配線を行う．

\chapter{UnixのFile system}
\section{xv6}
MITで教育用の目的で開発されたOSで，Unixの基本的な構造を持つ．
当研究室ではxv6のCbCでの書き換え，分析を行なっている．
xv6はUnix系のOSであるため，File systemでは\emph{inode}の仕組みが用いられている．

\section{inode}
主にUnix系のファイルシステムで用いられる，ファイルの属性情報が書かれたデータである．
inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある．
またinodeは識別番号としてinode numberを持つ．
inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である．
inodeはファイルシステム始動時にinode領域をディスク上に確保する．
そのためinode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる．
inode numberの最大値は\emph{df -i}コマンドで確認可能である．

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      File Types & directoryやregular fileなど，ファイルの種類 \\
      \hline
      Permissions & read write executeの実行可否\\
      \hline
      UID & ファイル所有者のID \\
      \hline
      GID & ファイル所有グループのID \\
      \hline
      File Size & ファイルのサイズ \\
      \hline
      Time Stamps & ファイル作成，編集日時 \\
      \hline
      Number of link & ハードリンクの数 \\
      \hline
      Location on hard disk & データのアドレス\\
      \hline
    \end{tabular}
    \caption{inodeでのファイル属性情報}
    \label{table:inode}
  \end{center}
\end{table}

\chapter{GearsFileSystemにおけるdirectoryの構成}
当研究室ではxv6のCbCでの実装を行なっているが，今回はxv6のルーチンをCbCで書き換えるのではなく
GearsOSへUnixのFile systemの仕組みを取り入れるアプローチをとる．
ファイルシステムを大まかにディレクトリシステムとファイルの二つに分けて考える．
ディレクトリシステムはUnixのinodeの仕組みを取り入れる．
今回作成した，GearsOSのディレクトリシステムであるgearsDirectoryについて説明する．
ファイルについては次章で述べる．

\section{FileSystemTree}
FileSystemTreeはdirectory構造，inodeの仕組みを取り入れる際に用いるTreeである．
ソースコード\ref{src:ftree}はFileSystemTreeのinterfaceである．
gearsOSにおけるinterfaceはCodeGearと各CodeGearが用いるI/O DataGearの集合を記述する．
FileSystemTreeのinterfaceはfTreeとnodeのDataGearとput，get，remove，nextのCodeGearを持つ．
FileSystemTreeの実体はgearsOSの永続データを構築する際に使用されるRedBlackTreeであり，put，get，removeはRedBlackTreeの操作を行うためのCodeGearである．
nextは遷移先のCodeGearを参照するために用いる．
\lstinputlisting[caption=FTreeのinterface,label=src:ftree]{src/FTree.h}

\section{Treeによるdirectory構造}
ディレクトリ構造は2つのFileSystemTreeで実装する．
1つ目はinode numberとfileのポインタのペアを持つ木である．
inode numberをkey，inodeをvalueとして持つためinode numberからinodeを検索するために用いる(以下，inode treeとする)．
2つ目はfilenameとinode numberのペアを持つ木である．
filenameをkey, inode numberをvalueとして持つため，filenameからinode numberを検索するために用いる．
これはinodeをfilenameで検索するためのindex treeであるといえる(以下，index treeとする)．

図\ref{fig:inode}はindex treeを用いたinodeの検索の流れを表す．
まずindex treeからkeyが2のnodeをgetする．
keyが2のnodeのvalueよりinode numberが0であることがわかる．
次に取得したinode numberをkeyとしてinode treeを検索する．
keyが0のnodeはinode0を持っていて，inodeを参照することができる．

\begin{figure}[h]
  \begin{center}
      \includegraphics[width=120mm]{figs/inode.png}
  \end{center}
  \caption{index treeを用いたinodeの検索の流れ}
  \label{fig:inode}
\end{figure}

\section{Unix Like な interface}
ファイルやディレクトリの操作を行うinterfaceをUnix Likeに実装を行った．
実装を行ったmkdir, ls, cdを説明する．

\subsection{mkdir}
Unixにおいてmkdirは新しくdirectoryを作成するコマンドである．
GearsDirectoryのmkdirはindex treeとinode treeにnodeをputすることでdirectoryを作成する．
ソースコード\ref{src:mkdir}はgearsDirectoryにおけるmkdirのCodeGearである．
まず1行目の\emph{\_\_code mkdir}ではinode treeへinodeのputが行われ，\emph{\_\_code mkdir2}へ遷移する．
次に，11行目の\emph{\_\_code mkdir2}ではindex treeへkeyがfilenameのnodeのputが行われ，nextのCodeGearへ遷移する．
FileSystemTreeのputを2回行うため，mkdirは\emph{\_\_code mkdir}と\emph{\_\_code mkdir2}の2つのCodeGearで構成されている．
InputDataGearの\emph{name}はfilenameを表す．
\lstinputlisting[caption=mkdirのCodeGear,label=src:mkdir]{src/mkdir.cbc}

\subsection{ls}
Unixにおいてlsはファイルやディレクトリの一覧，メタ情報を表示するコマンドである．
GearsDirectoryのlsはindex treeに対し，getをすることでディレクトリのnameを取得する．
Unixのlsコマンドにおける\emph{\$ls filename}に等しい機能である．
ソースコード\ref{src:ls}はgearsDirectoryにおけるlsのCodeGearである．
まず1行目の\emph{\_\_code ls}ではindex treeに対しgetを行うため，index treeのgetへgotoしている．
その後，9行目の\emph{\_\_code ls2}ではnode\verb|->|keyに格納されたgetの結果をprintfで出力する．
本来lsコマンドは引数を渡さずに実行するとcurrent directory下のディレクトリやファイルを一覧で表示するが，
現時点では未実装である．
一覧表示の機能はfilenameのリストをディレクトリに持たせることで実装可能であると思われる．
\lstinputlisting[caption=lsのCodeGear,label=src:ls]{src/ls.cbc}

\subsection{cd}
Unixにおいてcdはディレクトリを移動するコマンドである．
GearsDirectoryのcdはindex treeとinode treeに対しgetを行い，currentDirectoryを書き換えることで実装する．
機能としてはディレクトリが持つ子ディレクトリへの移動ができる．
ソースコード\ref{src:cd}はgearsDirectoryにおけるcdのCodeGearである．
まず1行目の\emph{\_\_code cd2Child}でindex treeに対しgetを行うため，index treeのgetへgotoしている．
次に，9行目の\emph{\_\_code cd2Child2}でinode treeに対しgetを行うため，inode treeのgetへgotoしている．
その後，15行目の\emph{\_\_code cd2Child3}でcurrent directoryを保存しているgearsDirectory\verb|->|currentDirectoryを
getしたnode\verb|->|valueに書き換える．
\lstinputlisting[caption=cdのCodeGear,label=src:cd]{src/cd.cbc}

\section{GearsDirectoryの非破壊的編集によるバックアップ}
GearsOSにおける永続データは非破壊的な編集を行う木構造を用いて保存する．
図\ref{fig:TreeEdit}は非破壊的編集を木構造に対し行う様子である．
赤で示されたノード6をAに編集する場合，まずルートノードから編集ノードまでのパスを全てコピーする．
コピーしたパス上に存在しないノードは，コピー元の木構造と共有する．
それにより，編集後の木構造の赤のルートノードから探索を行う場合は編集されたAのノードが見え，
黒のルートノードから探索を行う場合は編集前の6のノードを見ることができる．
ディレクトリシステムを非破壊的な木構造の編集を用いて実装することにより，
ディレクトリシステム自体にバックアップの機能を搭載することが可能であると考える．

\begin{figure}[h]
  \begin{center}
      \includegraphics[width=120mm]{figs/nonDestroyTreeEdit.pdf}
  \end{center}
  \caption{非破壊的なTree編集}
  \label{fig:TreeEdit}
\end{figure}

\chapter{GearsFileSystemにおけるFileの構成}
ファイルシステムはディレクトリの構成だけでなく，ファイルの構成についても考える必要がある．
本研究と並行する形で一木貴裕による分散ファイルシステムの設計が行われており，
ファイルの構成に関しても実装，検討されている．
GearsOSにおけるファイル構成を説明する．

\section{I/O Stream}
ファイルのInput/Output Streamは競合的なアクセスに対応するため，3つのSynchronizedQueueを用いる．
それぞれをInputQueue, OutputQueue, mainQueueと呼ぶ．
データをinputしたい場合InputQueueへputを行い，取得したい場合OutputQueueからgetを行う．
mainQueueはデータそのものであり，InputQueueからmainQueue，mainQueueからOutputQueueへデータが流れるように接続される．
3つのQueueを通過するデータはelementと呼ばれる．


\section{logによるファイルのバックアップ}
ディレクトリに関しては非破壊的なTree編集を用いることで，バックアップを行うことを考えたが
ファイルに関してはelement


\chapter{WordCount}
WordCount例題\cite{file}はGearsOSのファイルシステムを構築する際に用いてる例題である．
指定したファイルの文字数や行数，ファイルの内の文字列を出力する．
図\ref{fig:WCStates}はWordCount例題の処理の流れを示している．
大きく分けて，指定したファイルをFile構造体としてopenするFileOpenスレッド，
File構造体を受け取り文字数と行数をcountUpするWordCountスレッドの二つのCodeGearで記述することができる．
ファイル内の文字列を行ごとにCountUpに送信し，EOFを受け取ったらループを抜けfinishに移行する．
\begin{figure}[h]
  \begin{center}
      \includegraphics[width=100mm]{figs/wordCountStates.pdf}
  \end{center}
  \caption{WordCount with CbC}
  \label{fig:WCStates}
\end{figure}
\section{API}
\section{GearBox的な処理}

\chapter{今後の課題}
\section{分散ファイルシステム}
\section{信頼性}
\section{shell}