%%
%% 研究報告用スイッチ
%% [techrep]
%%
%% 欧文表記無しのスイッチ(etitle,eabstractは任意)
%% [noauthor]
%%

%\documentclass[submit,techrep]{ipsj}
\documentclass[submit,techrep,noauthor]{ipsj}



\usepackage[dvips, dvipdfmx]{graphicx}
\usepackage{latexsym}
\usepackage{listings}
\lstset{
  language=C,
  tabsize=2,
  frame=single,
  basicstyle={\tt\footnotesize}, %
  identifierstyle={\footnotesize}, %
  commentstyle={\footnotesize\itshape}, %
  keywordstyle={\footnotesize\ttfamily}, %
  ndkeywordstyle={\footnotesize\ttfamily}, %
  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,
}
\usepackage{caption}


\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\|{\verb|}
%

%\setcounter{巻数}{59}%vol59=2018
%\setcounter{号数}{10}
%\setcounter{page}{1}
\renewcommand{\lstlistingname}{Code}

\begin{document}


\title{GearsOSの分散ファイルシステムの設計}

\etitle{Designing a Distributed File System for GearsOS}

\affiliate{IPSJ}{情報処理学会\\
IPSJ, Chiyoda, Tokyo 101--0062, Japan}


\paffiliate{JU}{琉球大学理工学研究科情報工学専攻\\
Johoshori Uniersity}

\author{一木貴裕}{Ikki Takahiro}{KIE}[ikki-tkhr@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Kono Shinzi}{IE}[kono@ie.u-ryukyu.ac.jp]

\begin{abstract}
本研究室ではgearというプログラミング概念を持つ, 分散フレームワークChristieを開発している. Christieはノード同士がDatagearと呼ばれる変数データを送信しあうことにより, 簡潔に分散プログラムの記述を行うことができる.
このChristieの仕組みを, 同様に本研究室が開発しているGearsOSに組み込み, ファイルシステムを構築したい. GearsOSはノーマルレベルとメタレベルを分けて記述できるContinuation based C(CbC)で構成されており、Christieと近い仕様をもつ. 
\end{abstract}


%
%\begin{jkeyword}
%情報処理学会論文誌ジャーナル，\LaTeX，スタイルファイル，べからず集
%\end{jkeyword}
%
%\begin{eabstract}
%This document is a guide to prepare a draft for submitting to IPSJ
%Journal, and the final camera-ready manuscript of a paper to appear in
%IPSJ Journal, using {\LaTeX} and special style files.  Since this
%document itself is produced with the style files, it will help you to
%refer its source file which is distributed with the style files.
%\end{eabstract}
%
%\begin{ekeyword}
%IPSJ Journal, \LaTeX, style files, ``Dos and Dont's'' list
%\end{ekeyword}

\maketitle

%1
\section{GearsOSのファイルシステムの開発}
当研究室ではOSの信頼性の検証を目的としたOSであるGearsOSを開発している. 
GearsOSはユーザレベルとメタレベルを分離して記述が行える言語であるContinuation based C(以下CbC)で記述されており, Gearというプログラミング概念を持つ.

GearsOSは現在開発途上であるため, 現在は言語フレームワークとしてしか動作しない。OSとして起動するためにこれから実装が必要な機能が多く存在しており, その中の一つとして分散ファイルシステムが挙げられる. 
GearsOSの分散ファイルシステムを構成するために、当研究室が開発している分散フレームワークChristieの仕組みを用いようと考えた. 

ChrsitieはGearsOSのもつGearという概念とよく似た, 別のGearというプログラミング概念を持っており, DataGearと呼ばれる変数データを接続されたノード同士が送信しあうことで分散処理を簡潔に記述することができる. DataGearは指定された型と名前を持つkeyに対応しており, プログラムが必要なkeyにデータが揃ってから初めてプログラムが処理される.
また, ChrisiteはTopologyManagerと呼ばれる機能を持っており, 任意の形でノード同士の配線を行いTopologyを形成する機能を持っている. 


%2
\section{現代のファイルシステムについて}


%2.1
\section{Continuation based C}
GearsOSはC言語の下位言語であるContinuation based Cを用いて記述されている. CbCは関数呼び出しでなく, 継続を導入しており, スタック領域を用いずjmp命令でコード間を移動することにより軽量な継続を実現している. CbCではこの継続を用いてfor文などのループの代わりに再起呼び出しを行う. 実際のOSやアプリケーションを記述する際にはGCCまたはLLVM/clangのCbC実装を用いる.

CbCでは関数の代わりにCodeGearという単位でプログラミングを行う. CodeGearは\texttt{\_\_code}で宣言を行い, 各CodeGearはDataGearと呼ばれる変数データを入力として受け取り, その結果を別のDataGearに書き込む. 特に入力のDataGeatをInputDataGear, 出力されるDataGearを OutputDataGearと呼ぶ. CodeGearとDataGearの関係図を図\ref{fig:cgdg}に示す. 
CodeGearは関数呼び出しのスタックを持たないため, 一度CodeGearを遷移すると元の処理に戻ってくることができない. 

CbCコードの例をソースコード\ref{src:cbc_example}に示す．%refを使う

\begin{figure}[tb]
    \begin{center}
        \includegraphics[width=80mm]{images/cgdg.pdf}
    \end{center}
    \caption{CodeGearと入出力の関係図}
    \label{fig:cgdg}
\end{figure}

\begin{lstlisting}[frame=lrbt,label=src:cbc_example,caption={CbCの例題}]
void syscall(void)
#include <stdio.h>
__code CG2(){
  int i = 10;
  printf("i = %d\n", i);
}

__code CG1(){
  printf("Hello\n");
  goto CG2();
}

int main(){
  goto CG1();
}

\end{lstlisting}


\section{CbCを用いたOSの記述}
CodeGearの遷移はノーマルレベルから見ると単純にCodeGearがDataGearをInput, Outputをのみ繰り返し, コードブロックを移動しているように見える.
 CodeGearが別のDataGearに遷移する際のDataGearとの関係性を図\ref{fig:meta-cgdg} に示す. ノーマルレベルではDataGearを受け取ったCodeGearを実行, 実行結果をDataGearに書き込み別のCodeGearに継続していると見える. 

しかし, 実際にはCodeGearから別のCodeGearへの遷移にはデータの整合性の確認などのメタ計算が必要となる. 
コード間の遷移に必要となるメタ計算は,  MetaCodeGearと呼ばれるCodeGearごとに実装されたCodeGearで行う. 
MetaCodeGearで参照されるDataGearをMetaDataGear呼び, また, CodeGearの直前に実行されるMetaCodeGearをStubCodeGearと呼ぶ.
これらMeta計算部分を含めたCodeGearの遷移とDataGearの関係性を図示すると図\ref{fig:meta-cgdg} の下段の形に表せる. CordGearの実行前後に実行されるMetaCodeGearや入出力のDataGearをMetaDagaGearから取り出すなどのメタ計算が加わる.

MetaCodeGearは詳細な処理の変更や, スクリプトに問題がある場合を除き, プログラマが直接実装する必要がなく, GearsOSが持つPerlスクリプトにより, GearsOSがビルドされる際に生成される. 

CodeGearの遷移に重要な役割を持つMetaDataGearとしてcontextが存在する。
contextは遷移先のCodeGearとMetaDataGearの紐付けや, 計算に必要なDataGearの保存や管理を行う.
加えてcontextは処理に必要になるCodeGearの番号とMetaCodeGearの対応表や, DataGearの格納場所を持つ. contextと各データ構造の役割を図\ref{fig:context}に示す.
計算に必要なデータ構造と処理を持つデータ構造であることから, contextは従来のOSのプロセスに相当し, ユーザープログラムごとにcontextが存在している.


\begin{figure}[tb]
    \begin{center}
        \includegraphics[width=80mm]{images/meta-cg-dg.pdf}
    \end{center}
    \caption{CodeGearとMetaCodeGearの関係図}
    \label{fig:meta-cgdg}
\end{figure}

\begin{figure}[tb]
    \begin{center}
        \includegraphics[width=80mm]{images/Context_ref.pdf}
    \end{center}
    \caption{Contextを介したCodeGearの継続}
    \label{fig:context}
\end{figure}


\section{分散フレームワークChristie}
Christieは当研究室で開発されているjava言語で記述された, 分散フレームワークである.
ChristieはCbCと似ているが異なる仕様を持つGearというプログラミング概念を持つ. 

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

CodeGearはクラスやスレッドに相当する. DataGearは変数データであり, CodeGear内でjavaのアノテーションを用いて記述する.

 DataGearはKeyと必ず対応しており, CodeGear内の全てのKeyにDataGearが揃った際に初めてCodeGearが動作するという仕組みになっている. 

CodeGearManagerはいわゆるノードに相当し, CodeGear, DataGear, DataGearManagerを管理する.  
複数のCodeGearManager同士が配線され,  DataGearを送信し合うことで分散処理を実現している. 

DataGearManagerはDGを管理しているもので変数プールに相当し, CodeGearManagerの持っているDataGearのkeyとputされたデータの全てを所持している. 
DataGearManagerはLocalとRemoteに区分することができ, LocalDataGearManagerはCodeGearManager自身が所持するDataGear(key)のプールであり, Localにputすることにより自身の持つkeyにDataGearを送ることができる.
対するRemoteDataGearManagerはCodeGearManagerが配線されている別のCodeGearManagerが持つDataGearのプールである. つまり, 任意の接続されたRemoteDataGearにDataGearをputすると対応したノードが持つkeyにDataGearが送信される. RemoteDataGearにDataGearをputする処理が分散処理の肝となっている. RemoteDataGearの仕組みを図\ref{fig:RDGM}に示す.

\begin{figure}[tb]
    \begin{center}
        \includegraphics[width=80mm]{images/Remote_DataGearManager.pdf}
    \end{center}
    \caption{RemoteDataGearと接続ノードの関係図}
    \label{fig:RDGM}
\end{figure}


Christieの要となるDataGearのkeyはjavaのアノテーション機能が使われている. アノテーションには以下の4つが存在する. 
\begin{description}
\item[Take] 先頭のDGを読み込み，そのDGを削除する．DGが複数ある場合，この動作を用いる．
\item[Peek] 先頭のDGを読み込むが，DGが削除されない．そのため，特に操作をしない場合は同じデータを参照し続ける．
\item[TakeFrom(Remote DGM name)] Takeと似ているが，Remote DGM nameを指定することで，その接続先(Remote)のDGMからTake操作を行える．
\item[PeekFrom(Remote DGM name)] Peekと似ているが，Remote DGM nameを指定することで，その接続先(Remote)のDGMからPeek操作を行える．
\end{description}



コード\ref{codes: StartHelloWorld}, \ref{codes: StartHelloCG}はChristieで記述したHello Worldのプログラムである. 
ユーザープログラムはStartCodeGearクラスを継承したクラス(コード\ref{codes: StartHelloWorld})から開始する. 
CodeGearManagerはポート番号を指定した上でcreatCGMメソッドを呼び出すことにより生成される. 生成されたCodeGearManagerは CGM名.setup にてCGMに処理させたいスレッド, つまりCodeGearを持たせることができる.  

コード \ref{codes: StartHelloCG}はHeloWorldCodeGearの記述である. 
HelloWorldCodeGearではkey: helloWorldにputされた文字列をprint出力するという単純な処理を記述している. 
 CGM名.getLocalDGM().put("Keyname", 変数データ)にてkeyに変数データを紐付け(putし), CodeGearに設定されている全てのkeyがデータを受け取った際に初めてCodeGearは処理される. HelloWorldCodeGearではString型のhelloWorldというkeyがTake型で設定されている.
 
以下のHelloWorldプログラムを実行した際の流れを説明する.
 まずポート10000番のCodeGearManagerを生成し, HelloWorldCodeGearをsetupさせる. 
 この時点では必要なkey(key名: helloWorld)にデータが揃っていないのでCodeGearは実行されない. cgm.getLocalDGM().put("helloWorld","hello");にてhelloWorldkeyに文字列"hello"をputすると, HelloWorldCodeGearに必要なDataGearが揃い, print表示が行われる. 
プログラム中ではkey:helloWorldへのputは文字列"hello"と"world"の二回が行われ, print出力結果はhello worldと表示される. 

\begin{lstlisting}[frame=lrbt,label=codes: StartHelloWorld,caption={ChristieにおけるCGMとCGのsetup}]
public class StartHelloWorld extends StartCodeGear {

    public StartHelloWorld(CodeGearManager cgm) {
        super(cgm);
    }

    public static void main(String[] args){
        CodeGearManager cgm = createCGM(10000);
        cgm.setup(new HelloWorldCodeGear());
        cgm.getLocalDGM().put("helloWorld","hello");
        cgm.getLocalDGM().put("helloWorld","world");
    }
}
\end{lstlisting}


\begin{lstlisting}[frame=lrbt,label=codes: StartHelloCG,caption={HelloWorldCodeGear}]
public class HelloWorldCodeGear extends CodeGear {
    @Take
    String helloWorld;

    @Override
    protected void run(CodeGearManager cgm) {
        System.out.print(helloWorld + " ");
        cgm.setup(new HelloWorldCodeGear());
    }
}
\end{lstlisting}

ChristieにはTopologyを形成するための機能TopologyManagerが備わっている.
Topologyに参加するノードに対して名前を与え, 必要とあればノード間の配線を行う. 

TopologyManagerのTopology形成方法として静的Topologyと動的Topologyがある. 
静的Topologyはプログラマが任意の形のTopologyとノードの配線をdotファイルに記述し, TopologyManagerに参照させることで自由な形のTopologyが形成できる. 
現時点では静的TopologyでのTopology形成はdotファイルに記述した参加ノード数に実際に参加するノードの数が達していない場合, 動作しないという制約が存在している. 
動的Topologyは参加を表明したノードに対し, 自動的にノード同士の配線を行う. 例えばTreeを構成する場合, 参加したノードから順番にrootから近い役割を与える. 


\begin{acknowledgment}
A4横型に対するガイドを基に，本稿を作成した．
クラスファイルの作成においては，
京都大学の中島　浩氏にさまざまなご教示を頂き，
さらにBiB\TeX 関連ファイルの利用についても快諾頂いたことを深謝する．
また，A4横型に対するガイドを作成された当時の編集委員会の担当者に深謝する．
\end{acknowledgment}



\begin{thebibliography}{10}

\bibitem{okumura}
奥村晴彦：改訂第5版\LaTeXe 美文書作成入門，
技術評論社(2010).

\bibitem{companion}
Goossens, M., Mittelbach, F. and Samarin, A.:
{\it The LaTeX Companion},
Addison Wesley, Reading, Massachusetts (1993).

\bibitem{book1}
木下是雄：
理科系の作文技術，
中公新書(1981).

\bibitem{book2}
Strunk W. J. and White E.B.:
{\it The Elements of Style, Forth Edition},
Longman (2000).

\bibitem{book3}
Blake G. and Bly R.W.:
{\it The Elements of Technical Writing},
Longman (1993).

\bibitem{book4}
Higham N.J.:
{\it Handbook of Writing for the Mathematical Sciences},
SIAM (1998).

\bibitem{webpage1}
情報処理学会論文誌ジャーナル編集委員会：
投稿者マニュアル(online)，
\urlj{http://www.ipsj.or.jp/journal /submit/manual/j\_manual.html}
(2007.04.05).

\bibitem{webpage2}
情報処理学会論文誌ジャーナル編集委員会：
べからず集(online)，
\urlj{http://www.ipsj.or.jp/journal/manual /bekarazu.html}
(2011.09.15).

\end{thebibliography}




\end{document}