\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 は関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。

% 研究目的

% 信頼性の高いOS
% これをアセンブラにしていろいろなアプリケーションを作る
% きょだいなCDGの上で動かすと既存のアプリケーションを動かすことができる

\section{メタ計算の重要性}
% 今ま

プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理、スレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。
これらの計算をメタ計算と呼ぶ。

従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。
実行時にメタ計算の変更を行う場合には、OS 内部のパラメータの変更を使用し、
実行されるユーザープログラム自体への変更は限定的である。
しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で
実際のシステムコール単位では不十分である。
例えば、モデル検査ではアセンブラあるいはバイトコード、インタプリタレベルでのメタ計算が必要になる。
しかし、バイトコードレベルでは粒度が細かすぎて扱いが困難になっている。
具体的にはメタ計算の実行時間が大きくなってしまう。

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

Code Gear は処理の単位である。
関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。
Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。

Continuation based C (CbC)\cite{cbc} はこの Code Gear 単位を用いたプログラミング言語として開発している。

CbCは軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。

また、当研究室で開発している Gears OS\cite{gears} は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
CbC での記述はメタ計算を含まないノーマルレベルでの記述と、 Code Gear、Data Gear の記述を含むメタレベルの記述の2種類がある。
メタレベルでもさらに、メタ計算を用いることが可能になっている。
この2つのレベルはプログラミング言語レベルでの変換として実現される。
CbC は LLVM 上で実装されており、メタレベルでの変換系は本論文では、Perl による変換スクリプトにより実装されている。

Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
Interface は複数の実装を持つことができ、Meta Data Gear によって定義される。
Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。

従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call する。
Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、
操作に対応する Code Gear に goto する。
Context とは使用される Code Gear と Data Gear を全て格納している Meta Data Gear である。
これは従来のスレッド構造体に対応する。
つまり Gears OS では従来はコンパイラが定義する ABI(Aplication Binary Interface) 
を Meta Data Gear として CbC で表現し、メタ計算として操作することができる。

ノーマルレベルでは Context を直接見ることはできず、引数は Code Gear の引数を明示する必要がある。
この時に呼び出し側の引数を不定長引数として追加する構文を CbC に追加した。
これにより Interface 間の呼び出しを簡潔に記述することが出来るようになった。
メタレベルでは Code Gear の引数は単一または複数の Data Gear として見ることができる。
これは Context を直接操作することができることを意味する。
この部分はノーマルレベルの Code Gear を呼び出す stub として生成される。
ノーマルレベルでの goto 文はメタ計算への goto で置き換えられる。
Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。

メタ計算の例としては並列処理があり、Context を切り替えることによって複数のスレッドを実現している。
Context を複数の CPU に割り当てることにより並列実行を可能にしている。


本研究では CbC を用いての Gears OS の実装と Gears OS におけるメタ計算(Context と stub)の自動生成の実装について述べる。

\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 を通す必要がある。

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

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

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 のコードの例}

リスト\ref{excbc}は CbC で記述された stack のコードの一部である。
Code Gear は \_\_code Code Gear で始まり、次の Code Gear へ goto で遷移する。

%,,,の説明
%codegearの説明もっとする？

\lstinputlisting[label=excbc, caption=cbccode]{./src/ex_stack.cbc}

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



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



\section{interface の記述}
% union data はジェネラルなデータセグメントこれには
% goto のひきすうとしてつかう　フレームを表している
%関数呼び出しのabi
%ひきすうで呼び出されるcg ひきすうはぜんぶ定義されていなければならない
%メタデータセグメント
%名前付きの変数が現れる
%書き込みは**読み込みは*
%いんたーふぇーすなので実装がいる

 

 



interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
呼び出される Code Gear の引数となる Data Gear はここで全て定義される。



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

\lstinputlisting[label=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 を加えたコードに変換を行う。(Code\ref{stack_c})

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

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

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

Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。
また、generate context は取得した Code/Data Gear から Context の生成を行うコード (Code\ref{init_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=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}