\documentclass[techrep]{ipsjpapers}
\usepackage[dvipdfm]{graphicx}
\usepackage{url}
\usepackage{listings}
\usepackage{enumitem}

\lstset{
  language=C,
  tabsize=2,
  frame=single,
  basicstyle={\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=1zw,%
  lineskip=-0.5ex%
}

\renewcommand{\lstlistingname}{Code}
\input{dummy.tex} %% Font 

% ユーザが定義したマクロなど．
\makeatletter

\begin{document}

% 和文表題
\title{Monad に基づくメタ計算を基本とする Gears OS の設計}
% 英文表題
\etitle{}

% 所属ラベルの定義
\affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
\affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}

% 和文著者名
\author{
  小久保 翔平\affiref{1}
  \and
  伊波 立樹\affiref{2}
  \and
  河野 真治\affiref{2}
}

% 英文著者名
\eauthor{
  Shohei KOKUBO\affiref{1}\and
  Tatsuki Iha\affiref{2}\and
  Shinji KONO\affiref{2}
}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{小久保 翔平\\
        〒903-0213 沖縄県西原町千原1番地\\
	琉球大学工学部情報工学科\\
        TEL: (098)895-2221\qquad FAX: (098)895-8727\\
        email: kokubo@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
  本研究室では Code Gear, Data Gear を用いた並列フレームワークの開発を行なっている。
  並列実行に必要な Meta な機能を関数型言語における Monad の原理に基づいて、実現することにした。
  今回設計した Gears OS では Code Gear, Data Gear それぞれに Meta Code Gear と  Meta Data Gear を付属させる。
  Code Gear が実行されるとそれに属する Meta Code Gear が実行され、Meta Computation が行われる。
  Meta Computation は OS が行うネットワーク管理、メモリ管理等の資源制御を行う。
  本論文では基本的な機能を CbC(Continuation based C) で実装し、評価する。
\end{abstract}

% 英文概要
\begin{eabstract}
\end{eabstract}

% 表題などの出力
\maketitle

% 本文はここから始まる

% Introduce
\section{Gears OS}
並列実行は Code の並列実行だけでなく、Data の単位が重要である。
本研究では Code Gear, Data Gear という単位で細かく分割し、依存関係を記述することで並列実行するフレームワーク Gears OS の開発を行なっている。
Code Gear, Data Gear はそれぞれ他の Code Gear, Data Gear に接続することで機能や Data 自体を拡張することが可能である。

従来の OS が行う排他制御、メモリ管理、並列実行などは Meta Computation に相当する。
Gears OS では、Meta な機能を関数型言語における Monad に基づいて実現する。

Gears OS を用いて作成されたプログラムに対する Model Checking を行う機能を提供する。
Model Chaecking によって、並列実行時のデッドロックの検出などを行う。
これにより、プログラムの信頼性を保証する。

Gears OS は接続する Gear を変更することでプログラムの振る舞いを変更することを可能にする柔軟性、Monad に基づくメタ計算による並行制御、Model Checking を用いた信頼性の確保を目的とする。

% Theory
\section{Monad とメタ計算}
関数型言語では入力から出力を得る通常の計算の他にメタ計算と呼ばれるもの
がある。
メタ計算の例として、失敗する可能性がある計算、並行処理、入出力などの副
作用、メモリ管理などがある。
メタ計算の理論的な表現として、Monad を用いることが Moggi らにより提案\cite{Monad}
されている。
Gears OS ではメタ計算を表現するのに、Monad と軽量継続を用いる。

Monad は関数が返す通常の値を含むデータ構造であり、メタ計算を表現するの
に必要な情報を格納している。
失敗する可能性がある計算の場合は、計算が失敗したかどうかのフラグが
Monad に含まれる。
並行処理の場合は、Monad は可能な計算の interleaving(並び替え) になるが、
実際に並び替えを持っているわけではなく、マルチプロセッサで実行する環境
そのものが Monad に対応する。

通常の関数を Monad を返すように変更することにより、メタ関数が得られる。
逆に Monad の中にある通常の戻り値のみに着目すると通常の関数に戻る。
このように、Monad を用いたメタ計算の表現では通常の計算とメタ計算が一対
一に対応する。

一般的には複数の Monad の組み合わせが Monad になることを示すのは難しい。
Gears OS では Code と Data を分離して、Code から他の Code への呼び出し
を継続を用いて行う。
Gears OS での Monad は Meta Code と Meta Data になる。

% Code Gear
% Data Gear
% Meta Code Gear
% Meta Data Gear
\section{Code Gear と Data Gear}
Gears OS ではプログラムの実行単位として様々な Gear を使う。
Gear が平行実行の単位、データ分割、Gear 間の接続などになる。

Code Gear はプログラムの実行コードそのものであり、CUDA
の kernel に相当する。
Code Gear は複数の Data Gear を参照し、一つまたは複数の Data Gear に書
き込む。
Code Gear は接続された Data Gear 以外には触らない。
Code Gear はサブルーチンコールではないので、呼び出し元に戻る概念はない。
その代わりに、次に実行する Code Gear を指定する機能(軽量継続)を持つ。

Data Gear には、int や文字列などの Primitive Data Type が入る。
自分が持っていない Code Gear, Data Gear は名前で指し示す。

Gear の特徴の一つはその処理が Code Gear, Data Gear に閉じていることに
ある。
これにより、Code Gear の実行時間、メモリ使用量を予測可能なものにする。

Code Gear, Data Gear はポインタを直接には扱わない。
これにより、Code と Data の分離性を上げて、ポインタ関連のセキュリティフ
ローを防止する。

Code Gear, Data Gear はそれぞれ関係を持っている。
例えば、ある Code Gear の次に実行される Code Gear、全体で木構造を持つ
Data Gear などである。
Gear の関連付けは Meta Gear を通して行う。
Meta Gear は、いままでの OS におけるライブラリや内部のデータ構造に相当
する。
なので、Meta Gear は Code Gear, Data Gear へのポインタを持っている。
% s/Segment/Gear

% Context
\section{継続}
ある Code Gear から継続するときには、次に実行する Code Gear を名前で指
定する。
Meta Code Gear が名前を解釈して、処理を対応する Code Gear に引き渡す。
これらは、従来の OS の Dynamic Loading Library や Command 呼び出しに対
応する。
名前と Code Gear へのポインタの対応は Meta Data Gear に格納される。
この Meta Data Gear を Context と呼ぶことにする。
これは従来の OS の Process や Thread に対応する。

Context には以下のようなものが格納される。
\begin{itemize}
\item Code Gear の名前とポインタの対応表
\item Data Gear の Allocation 用の情報
\item Code Gear が参照する Data Gear へのポインタ
\item Data Gear に格納される Data Type の情報
\end{itemize}

\lstinputlisting[caption=Context]{source/context.h}

\paragraph*{Code Gear の名前とポインタの対応表}
Code Gear の名前とポインタの対応は enum と関数ポインタによって表現される。
これにより、実行時に比較ルーチンなどを動的に変更することが可能になる。

\paragraph*{Data Gear の Allocation 用の情報}
Context の生成時にある程度の領域を確保する。
Context にはその領域へのポインタとサイズが格納されている。
そのポインタを必要な Data Gear のサイズに応じて、インクリメントすることによって Data Gear の Allocation を実現する。

\paragraph*{Code Gear が参照する Data Gear へのポインタ}
Context には Data Gear へのポインタが格納されている。
Code Gear は Context を通して Data Gear へアクセスする。

\paragraph*{Data Gear に格納される Data Type の情報}
Data Gear は union と struct によって表現される。
Context には Data Gear の Data Type の情報が格納されている。
この情報から確保する Data Gear のサイズなどを決定する。

\lstinputlisting[caption=initContext]{source/context.c}

% Persistent
\section{Persistent Data Gear}
Data Gear の管理には木構造を用いる。
この木構造は非破壊で構築される。
非破壊的木構造では、図\ref{fig:non-destructive_tree}のように編集元の木構造を破壊することなく新しい木構造を構成する。
破壊的木構造と異なりロックの必要がなく、平行して読み書き、参照を行うことが可能である。
また、変更前の木構造をすべて保持しているので過去のデータにアクセスすることができる。

\begin{figure}[!h]
  \centering
  \includegraphics[width=70mm]{images/nondestructive_tree_modification.pdf}
  \caption{木構造の非破壊的編集}
  \label{fig:non-destructive_tree}
\end{figure}

% allocator
\section{Allocator}
Gears OS では Context の生成時にある程度の領域を確保し、その領域を指すポインタをインクリメントすることで Allocation を実現する。

Context には Allocation 用の Data Gear が格納されている。
この Data Gear に確保するサイズと確保後に接続する Code Gear の名前を書き込み、Allocation を行う Code Gear に接続することで必要な領域を確保する。

\lstinputlisting[caption=Allocator]{source/allocate.h}

% List
\section{List}
通常 List は要素と次へのポインタを持つ構造体で表現される。
Gears OS の場合、Meta レベル以外でポインタは扱わないので図\ref{fig:list}のように任意の要素を持つ Data Gear と次へのポインタを持つ Meta Data Gear の組によって List は表現される。

\begin{figure}[!h]
  \centering
  \includegraphics[width=70mm]{images/List.pdf}
  \caption{List の表現}
  \label{fig:list}
\end{figure}

\section{}
\nocite{*}
\bibliographystyle{ipsjunsrt}
\bibliography{sigos}

\end{document}