\documentclass[techrep]{ipsjpapers}
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{listings,jlisting}
\usepackage{enumitem}

\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}

\input{dummy.tex} %% Font 

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

\begin{document}

% 和文表題
\title{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}
}

% 英文著者名
\eauthor{
  Mitsuki MIYAGI\affiref{1}
  \and
  Shinji KONO\affiref{2}
}

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

% 和文概要
\begin{abstract}
    Gears OS は Continuation based C によってアプリケーションとOSそのものを記述する。
    OS の下ではプログラムの記述は通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等の記述しなければならない処理が存在する。
    これらの計算をメタ計算と呼ぶ。
    メタ計算を通常の計算から切り離して記述するために、Code Gear、Data Gear という単位を提案している。
    Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在する。
    Code Gear 間の接続は次の Code Gear の番号と thread structure に相当する context によって行われる。
    ユーザーレベルではメタ構造を直接見ることはなく、継続を用いた関数型プログラミングに見える。
    メタレベルから見た Data Gear をユーザーレベルの Code Gear に接続するには stub という Meta Code Gear を用いる。
    stub と Meta はユーザーレベル Code Gear と Data Gear からスクリプトにより作成される。
    変換に必要な情報はプログラムを構成する Code Gear と Data Gear の集まりから得る。この集まりを Interface として定義している。
    本論文では、Interfaceを用いたプログラミングと、メタ計算の実例を示す。
\end{abstract}

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

% 表題などの出力
\maketitle

% 本文はここから始まる

% Introduce
% Code Gear は関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。

\section{Continuation based C (CbC)}
CbC は Code Gear という処理の単位を用いて記述するプログラミング言語である。
Code Gear は CbC における最も基本的な処理単位である。
Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。
CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
ただし、これは \_\_code 型の戻り値を返すという意味ではなく、Code Gear であることを示すフラグである。
Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。

Code Gear から次の Code Gear への遷移は goto による継続で処理を行い、次の Code Gear へ引数として出力を与える。
図は Code Gear 間の処理の流れを表している。
図\ref{fig:cs}は Code Gear 間の処理の流れを表している。

\begin{figure}[ht]
 \begin{center}
  \includegraphics[width=70mm]{./pic/codesegment.pdf}
 \end{center}
 \caption{goto による code gear 間の継続}
 \label{fig:cs}
\end{figure}

goto の後に Code Gear 名と引数を並べて、次の Code Gear への遷移を記述する。
この goto の行き先を継続と呼ぶ。

Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。
したがってこれを軽量継続と呼ぶ。
軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。

\section{Gears OS}
Gears OS は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。
Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
Code Gear は任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
また、接続された Data Gear 以外には参照を行わない。
処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。

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

CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。

\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}

Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。

Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
Context は Task でもあり、TaskManager によって Context が生成され Task Queue へ挿入する。
Gears OS における Task Queue は Synchronized Queue で実現される。 
Worker は TaskQueue から Task である Context を取得し、 Input/Output Data Gear の依存関係が解決されたものから並列実行される。

\section{CbC による Gears OS 記述の問題}

Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
これらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。

\section{interface の記述}
interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
Code Gear、Data Gear に参照するために Context を通す必要があるが、
interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。
%create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
%return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。

\lstinputlisting[label=src:interface, caption=interface]{./src/Stack.cbc}

\section{Gearef、GearImpl}
Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すため、リスト\ref{gearef1} のようにコードが煩雑になってしまう。
そこで Code Gear がデータを参照するための Gearef というマクロを定義した。
Gearef に Context と型を渡すことでデータの参照が行える。
また impliment のデータを参照する際も、ポインタでの記述が複雑になってしまうため 同様に GearImpl を定義した。
GearImpl は Context と interface 名、interface の変数名を指定して参照する。
Gearef と GearImpl を用いたコードがリスト\ref{gearef2}である。

\lstinputlisting[label=gearef1, caption=Gearef1]{./src/ex_code1}
\lstinputlisting[label=gearef2, caption=Gearef2]{./src/ex_code2}

\section{stub Code Gear}
Code Gear が必要とする Data Gear を取り出す際に Context を通す必要があるが、
Context を直接扱うのはセキュリティ上好ましくない。
そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する間に挟まれる。
\section{Context、stub Code Segment の自動生成}

Gears OS では 通常の計算の他に Context や stub などのメタ計算を記述する必要があが、Gears OS を現在の CbC の機能のみを用いて記述するとこのメタ計算の記述を行わなくてはならず、これには多くの労力を要する。
この記述を助けるために Context を生成する generate\_context と stub Code Gear を生成する generate\_stub を perl スクリプトで作成した。

\section{stub Code Segment の生成}
stub Code Gear は Code Gear 間の継続に挟まれる Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
stub Code Gear を 自動生成することによって Code Gear の記述量を約半分にすることができる。

stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。
generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
この時既に stub Code Gear が記述されている Code Gear は無視される。

cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(\ref{stack_c})

\lstinputlisting[label=src:stack_c, caption=stub]{./src/ex_stub}

\section{Context の生成}
Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
Data Gear を取得するために generate context は context の定義を読み宣言されている Data Gear を取得する。

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

Code Gear の取得は指定された stub を加えたコードから \_\_code 型を見て行う。
取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。

Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。
また、generate context は取得した Code/Data Gear から Context の生成を行うコードも生成する。

Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
Code Gear は Context を通して Data Gear へアクセスする。
Data Gear の Allocation を行うコードは dataGearInit.cに生成される。

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

\lstinputlisting[label=src:init_context, caption=initcontext]{./src/context2.c}

\section{今後の課題}
本研究では LLVM/Clang のデバッグ、interface の記述、CbC ファイルから Gears OS の記述に必要な Context と stub の生成を行う perl スクリプトの生成を行なった。
これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。

%しかし、現在のスクリプトでは stub 

今後の課題は Code Gear からメタ計算を行う meta Code Gear を生成できるようにし、ユーザーがメタレベルの処理を意識せずにコードを記述できるようにする。
また、今回 perl スクリプトによって Context や stub の生成を行なったが、LLVM/clang 上で実装しコンパイラで直接 CbC を実行できるようにすることを目的とする。

%\begin{figure}[ht]
%    \begin{center}
%        \includegraphics[width=70mm]{./pic/cbc_goto.pdf}
%    \end{center}
%    \caption{gotoによる Code Segment 間の接続}
%    \label{fig:cbc_goto}
%\end{figure}

%\lstinputlisting[label=src:initContext, caption=initContext]{./src/context.c}

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

\end{document}