% withpage: ページ番号をつける (著者確認用)
  % english: 英語原稿用フォーマット
  \documentclass{ipsjprosym}
  %\documentclass[withpage,english]{ipsjprosym}
  \usepackage{listings}
  \usepackage[dvipdfmx]{graphicx}
  \usepackage{latexsym}
  \usepackage{comment}
  \lstset{
    language=C,
    tabsize=2,
    frame=single,
    basicstyle={\ttfamily\footnotesize},% 
    identifierstyle={\footnotesize},% 
    commentstyle={\footnotesize\itshape},% 
    keywordstyle={\footnotesize\bfseries},% 
    ndkeywordstyle={\footnotesize},% 
    stringstyle={\footnotesize\ttfamily},
    breaklines=true,
    captionpos=b,
    columns=[l]{fullflexible},% 
    xrightmargin=0zw,% 
    xleftmargin=1zw,% 
    aboveskip=1zw,
    numberstyle={\scriptsize},% 
    stepnumber=1,
    numbersep=0.5zw,% 
    lineskip=-0.5ex,
  }
  \renewcommand{\lstlistingname}{Code}
  \usepackage{caption}
  \captionsetup[lstlisting]{font={small,tt}}

\begin{document}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{継続を中心とした言語 \\ Gears OS のデモンストレーション}

%\affiliate{IPSJ}{情報処理学会}
\affiliate{IE}{琉球大学工学部情報工学科}

\author{宮城 光希}{Mitsuki MIYAGI}{IE}[mir3636@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Shinji KONO}{IE}[kono@ie.u-ryukyu.ac.jp]

% はじめに
\begin{abstract}
    現代の OS では拡張性と信頼性を両立させることが要求されている。
    信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
    Gears OS は Continuation based C(CbC) によってアプリケーションと OS そのものを記述する。
    CbC はこの Code Gear と Data Gear の単位でプログラムを記述する。
    システムやアプリケーションを記述するためにCode Gear と Data Gear を柔軟に再利用する必要がある。
    このときに機能を接続するAPIと実装の分離が可能であることが望ましい。
    Gears OS の信頼性を保証するために、形式化されたモジュールシステムを提供する必要がある。
    本論文では、Interface を用いたモジュールシステムの説明とその応用としての並列 API について考察する。
    並列API は継続を基本とした関数型プログラミングと両立する必要がある。
    ここでは、CbC の goto 文を拡張したpar goto 文を導入する。
    par goto 文を用いることによって Gears OS は並列処理を行う。
    また、本研究ではハードウェア上でメタレベルの処理、および並列実行を可能とするために、raspberry pi 上での Gears OS の実装についての考察を行う。
   
\end{abstract}

\begin{jkeyword}
OS, プログラミング言語, CbC, Gears OS
\end{jkeyword}

\maketitle

% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{メタ計算を使った並列処理}
プログラムの処理において、プログラミング言語で記述される部分をノーマルレベルの計算と呼ぶ。
コードが実行される時には、処理系の詳細や使用する資源、あるいは、コードの仕様や型などの言語以外の部分が服属する。
これをメタレベルの計算という。

従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。
しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で
実際のシステムコール単位では不十分である。

Gears OS はノーマルレベルの計算とメタレベルの計算を階層化することで、
ノーマルレベルの計算の信頼性をメタレベルから保証できることを目指して開発している。

メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。
しかし、関数やクラスなどの単位は容易に分割できない。
そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
これによりシステムコードよりも細かくバイトコードよりも大きなメタ計算の単位を提供できる

ノーマルレベルとメタレベルを共通して表現できる言語として Continuation based C(以下CbC)\cite{cbc}を用いる。
CbC は関数呼出時の暗黙の環境(Environment)を使わずに、コードの単位を行き来できる引数付き goto 文(parametarized goto)を持つ C と互換性のある言語である。
この CbC を用いて、Code Gear と Data Gear、さらにそのメタ構造を導入する。
これらを用いることで、検証された Gears OS を構築したい。

\section{Gears OS}

Gears OS は処理の単位である Code Gear とデータの単位である Data Gear を用いて開発されている。

Code Gear は CbC における最も基本的な処理単位である。
関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。
Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。

Gears OS では、並列実行するための Task を、実行する Code Gear と、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
この Input Data Gear、Output Data Gear の依存関係が解決された Code Gear を並列実行する。

Code Gear は任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
また、接続された Data Gear 以外には参照を行わない。
処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることができる。

Gears OS では メタレベルの計算 を Meta Code Gear、Meta Data Gear で表現する。
(図\ref{fig:metaCS})

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/metaCS.pdf}
 \end{center}
 \caption{Gears でのメタ計算}
 \label{fig:metaCS}
\end{figure}

Meta Code Gear は通常の Code Gear の直後に遷移され、メタレベルの計算を実行する。
Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。

CbC は軽量継続 (goto文) による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。
CbC は LLVM\cite{llvm}、gcc\cite{gcc} 上で実装されており、
メタレベルでの記述は、Perl による変換スクリプトにより生成される stub と goto meta によって Code Gear で記述される。

\section{interface}
Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
Interface は複数の実装を持つことができ、Meta Data Gear によって定義される。
Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。
一つの実行スレッド内で使われる Interface の Code Gear と Data Gear は Meta Data Gear に格納される。
この Meta Data Gear を Context という。
ノーマルレベルでは Context を直接見ることはできない。

メタ計算側ではこれらの Context を常に持ち歩いているので goto 文で引数を用いることはなく、
行き先は Code Gear の番号のみで指定される。

これにより Interface 間の呼び出しを C++ のメソッド呼び出しのように記述することができる。
Interface の実装は、Context 内に格納されているので、オブジェクトごとに実装を変える多様性を実現できている。

呼び出された Code Gear は必要な引数を Context から取り出す必要がある。
これは スクリプトで生成された stub Meta Code Gear で行われる。
Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。

\section{Gears OS の構成}
Gears OS は以下の要素で構成される。

\begin{itemize}
    \item Context
    \item TaskQueue
    \item TaskManager
    \item Worker
\end{itemize}

図\ref{fig:gearsos} に Gears OS の構成図を示す。

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/gears_structure}
 \end{center}
 \caption{Gears OS の構成図}
 \label{fig:gearsos}
\end{figure}

Context には Data Gear の Data Type の情報が格納されている。
この情報から確保する Data Gear のサイズなどを決定する。
Context は Task でもあり、Taskは通常のOSのスレッドに対応する。
Task は実行する Code Gear と Data Gear をすべて持っている。
TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。
Gears OS における Task Queue は Synchronized Queue で実現される。
Worker は TaskQueue から Task である Context を取得し、Task の Code Gear を実行し、Output Data Gear の書き出しを行っている。
Input/Output Data Gear の依存関係が解決されたものから並列実行される。


\section{Gears OS の並列処理}
Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。
Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。
Gears OS では 並列実行する Task を Context で表現する。
Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持
っている
Task の Input Data Gear が揃っているかを TaskManager で判断し、 実行可能な Task を Worker に送信する。
Worker は送信された Task が指定した Code Gear を実行し、Output Data Gear を書き出す。
Context を複製して複数の CPU に割り当てることにより並列実行を可能になる。


\section{並列構文}
Gears OS の並列構文は par goto文で用意されている(Code\ref{pargoto})。
\lstinputlisting[caption=par goto による並列実行, label=pargoto]{./src/parGotoCreateTask.cbc}
par goto の引数には Input/Output Data Gear と 実行後に継続する \_\_exit を渡す。
par goto で生成された Task は \_\_exit に継続することで終了する。

この par goto 文は通常のプログラミングの関数呼び出しのように扱うことができる。

par goto文でも 通常の goto 文と同様にメタへの goto 文へ置き換えられるが、par goto 文では通常の goto 文とは異なる meta code gear へと継続する。
Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、
Output Data Gear への書き出し処理(Commit)に継続される。

Code Gear は Input に指定した Data Gear が全て書き込まれると実行され、実行した結果を Output に指定した Data Gear に書き出しを行う。
Code Gear の引数である\_\_next が持つ引数の Data Gear が Output Data Gear となる。

書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。
参照した Task が持つ実行に必要な Input Data Gear カウンタのデクリメントを行う。
カウンタが0になると Task が待っている Input Data Gear が揃ったことになり、
その Task を TaskManager 経由で 実行される Worker に送信する。

\section{raspberry pi 上での Gears OS の実装}
Gears OS をハードウェア上で実装するために、ARM\cite{arm} プロセッサを搭載したシングルボードコンピュータである Raspberry Pi\cite{rpi} 上での Gears OS 実装する。
ハードウェア上でのメタレベルの計算や並列実行を行うために、Linax 等に比べてシンプルである xv6 の機能の一部を Gears OS に置き換えることで実現させる。
xv6 は UNIX V6 を x86 へ再実装したものであるが、ここでは Raspberry pi 用に移植した xv6\_rpi\_port\cite{xv6rpi} を用いて実装した。

xv6\_rpi\_port を Gears OS で置き換えるためには xv6\_rpi\_portを
CbC コンパイラを用いてコンパイルした kernel が Raspberry Pi 上で動作する必要がある。
そこで GCC 上で実装した CbC コンパイラを ARM 向けに build し xv6\_rpi\_port のクロスコンパイルを行い動作させることができた。

\section{今後の課題}
本研究では Gears OS のプロトタイプの設計と実装、並列実行機構の実装を行った。
Code Gear 、Data Gear を処理とデータの単位として用いて Gears OS を設計した。
Gears OS は Code Gear と Input/Output Data Gear の組を Task とし、並列実行を行う。

Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
Interface は複数の実装をもち、Meta Data Gear として定義される。
従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call するが、
Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、操作に対応する Code Gear に goto する。

並列処理を行う際は Context を生成し、 Code Gear と Input/Output Data Gear を Context に設定して TaskManager 経由で各 Worker の SynchronizedQueue に送信される。
Context の設定はメタレベルの記述になるため、ノーマルレベルでは par goto 文という CbC の goto 文に近い記述で並列処理を行える。
この par goto は通常のプログラミングの関数呼び出しのように扱える。

また、ハードウェア上での実装のため gccbc での xv6\_rpi\_port のクロスコンパイルを行なった。

今後の課題は、
gccbc でクロスコンパイルした xv6\_rpi\_port が実際のハードウェア上で動作することが可能となったため、
CbC で記述された Gears OS も ARM 向けにコンパイルが可能となった。
xv6\_rpi\_port の機能を Gears OS の機能と置き換えていくことで、
ハードウェア上でのメタ計算、並列処理を可能とすることが課題である。  


% BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\nocite{*}
\bibliographystyle{ipsjsort}
\bibliography{prosym}

% BibTeX を使用しない場合
%\begin{thebibliography}{9}
%\bibitem{latex}玉城将士、谷成雄，河野真治 : \textbf{Cassandraを使ったスケーラビリティのあるCMSの設計 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2011.
%\bibitem{latex}玉城将士 : \textbf{非破壊的木構造を用いた分散CMSの設計と実装 }. 琉球大学理工学研究科修士論文、2013
%\bibitem{latex}大城信康 、杉本優 、河野真治 : \textbf{Data Segment の分散データベースへの応用}. 日本ソフトウェア科学会第30回大会論文集. 、2013
%\bibitem{latex}大城信康 : \textbf{分散Database Jungleに関する研究}. 琉球大学理工学研究科修士論文、2014
%\bibitem{latex}金川竜己、河野真治 : \textbf{非破壊的木構造データベースJungleとその評価  }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2015.
%\end{thebibliography}
\end{document}