\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx} 
\usepackage{picins}
\usepackage{fancyhdr}
\usepackage{listings}
\usepackage{caption}
\usepackage{latexsym}
\usepackage{url}
\usepackage{abstract}
\usepackage{float}

%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\usepackage{comment}
\usepackage{listings}
\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}}

\renewcommand{\abstractname}{概要}
 
\begin{document}
\title{xv6 kernel上でのCbCによるinterfaceの実装\\CbC interface implementation in xv6 kernel}
\author{学籍番号 : 165723C 氏名 : 坂本昂弘 {}{} 指導教員 : 河野真治}
\date{2019年10月23日}
\maketitle
\thispagestyle{fancy} 

\section{xv6のOSの信頼性保証}
現代ではOSの信頼性の保証と拡張性の実現が求められている.
信頼性をノーマルレベルの計算に対して保 証し，拡張性をメタレベルの計算で実現することを目標にContinuation based C (CbC)を用いて Gears OS を設計中である.
前段階としてシンプルであるが基本的な機能を揃えた OS である xv6 を CbC で書き換えようとしている.

CbCにはCodeGearという処理の基本的な単位があり,これらを利用する事によってstackに値を積む事なくCodeGear間を遷移することができる.
%そのため,CbCのInterfaceを使うとモジュール化ができる.また,
 stackが無い事によってOS内部の明確化が実現できる.
%CbCを用いた Gears OSの研究を行なっている.
%しかし, Gears OS を直接実機に実装することはできなかった為, 前段階としてシンプルであるが基本的な機能を揃えた OS である xv6 を CbC で書き換える.
%形式手法
さらにCbC は 定理証明支援系 Agda に置き換えることができるように構築されている.Agdaを利用する事により,CbCの関数などが正常な動きをしているのかどうかを判断することが可能となる．
%CbCのinterfaceを使うとモジュール化ができる.また, stackが無い事によってOS内部の明確化も実現できる.
CbCのInterface は Gears OS のモジュール化の仕組みである. このInterfaceは,JavaのInterfaceやHaskellの型クラスに対応し,導入することで仕様と実装に分けて記述することが出来る.そのため,CbCのInterfaceを使うとモジュール化ができる.

これらのことを用い,CbCのInterfaceをxv6に搭載する事によりkernelの中の処理を明確にし, OSの信頼性を保証したい.
また,xv6のInterface実装によりモジュール化が可能とし,拡張性の実現を目指す.

\section{xv6}
xv6\cite{xv6}とはMITのオペレーティングコースの教育目的で2006年に開発されたオペレーティングシステムである.
xv6 はオリジナルである v6 が非常に古いC言語で書かれている為, ANSI-Cに書き換えられ x86 に再実装された. xv6 はreadやwriteなどのsystemcall,プロセス,仮想メモリ,カーネルとユーザーの分離,割り込み,ファイルシステムなどUnixの基本的な構造を持っている.

\section{Continuation based C}
xv6 kernel上でinterfaceを実装する際,当研究室で開発されたプログラミング言語 Continuation based C (CbC)を用いる.
CbC は基本的な処理単位を CodeGearとして定義し，CodeGea間で遷移するようにプログラムを記述するC言語と互換性のあるプログラミング言語である.
CodeGearは返り値を持たない為,関数内で処理が終了すると呼び出し元の関数に戻ることがなく別のCodeGearへ遷移する.
以下のCode1にCodeGear遷移時のコード例を示す.
\lstinputlisting[label=cbcexample,  caption=CodeGearの継続の例]{src/cbc_example.cbc}
%図かコードを入れても良いかも

またCbCにおけるCodeGear間の継続にはスタックが使用できず,呼び出し元の環境などを持たない為軽量継続と呼ぶ.
現在CbCはCコンパイラであるGCC及びLLVMをバックエンドとしたclang上で実装されている．
%今回 ,このCbCに存在するInterfaceをxv6に実装していく.



\section{CbCとAgdaの対応}
Agdaとは定理証明を支援する関数型のプログラミング言語である.
数学の証明に使われる自然演繹と型付きλ計算については対応があり,Agdaでは型付きλ計算を記述する事によって検証することができる.

CbCでは継続を用いてプログラムを記述する.同じくAgdaにも継続の記述方式が存在する.これらの記述は対応している.
以上のことよりCbCをAgdaに書き換える事ができ,CbCで記述されたプログラムはAgdaによって検証することが可能である.
%CbCはAgdaに変換できるように設計されている為,CbCで実装したプログラムはAgdaによって定理証明が可能である.ー＞ってことを書けば良い？


\section{context}
contextとは一連の実行が行われる際に使用されるCodeGearとDataGearの集合である.
従来のスレッドやプロセスに対応する.Context は接続可能な CodeGear, Data Gear のリスト. Data Gear を確保するメモリ空間,実行される Task への Code Gear 等を持っている.
CodeGearが別のCodeGearに遷移する際,必ずcontextを参照しenumで定義されたCodeGearの番号を指定し遷移する.ノーマルレベルで見た際のCodeGar,DataGerおよびcontextの関係を以下の図1に簡潔に示す.

\begin{figure}[ht]
     \begin{center}
     \includegraphics[width=65mm]{pic/context.pdf}
     \end{center}
     \caption{CodeGear,DataGear,contxtの関係図}
    \label{fig:perl6buil}
\end{figure}


%metaGearの話もした方が良い
%CbCのcontextには引数の置き場所が書いてある.contextの中にDatagearが存在し.enumの番号で管理している。
%dataの保存先と実行するdategearの保存先

%パルスさんの修論

%コンテキストには引数置き場所が書いてあるー＞CodeGear
\section{CbCのInterface}
先述した通り, CbCのInterface は Gears OS のモジュール化の仕組みである. Interface は呼び出しの引数になる Data Gear の集合であり，そこで呼び出される Code Gear のエントリである.呼び出される Code Gear の引数となる Data Gear はここで 全て定義される. Interface を定義することで複数の実装を持つことができる.このInterfaceは,JavaのInterfaceやHaskellの型クラスに対応し,導入することで仕様と実装に分けて記述することが出来る.%CbCを agdaに対応するために関数プログラミングスタイルで書く事によってInterfaceの検証も可能になる.

以下の図2は, QueueのInterfaceとSingleLinkedQueueの実装例である.

%\lstinputlisting[label=cbcexample,  caption=CodeGearの継続の例]{src/cbc_queue.cbc}

\begin{figure}[ht]
     \begin{center}
     \includegraphics[width=65mm]{pic/gotoInterface.pdf}
     \end{center}
     \caption{QueueのInterfaceとSingleLinkedQueueの実装例}
    \label{fig:perl6buil}
\end{figure}

\section{xv6のinterface}

%CbCのCodeGear間の遷移時はstackに値を積むことがない.よってCbCのInterfaceを用いる事によってxv6のInterfaceを実装した際, OSの内部が明確化され信頼性を保証することができる.
先述したCbCのInterfaceをxv6のInterfaceに実装する事によって仕様と実装を分けて記述できる.

先行研究\cite{CbC}ではxv6のkernelの一部であるsyscallの部分をCbCによって書き換えされている.それを元にxv6のkernel部のどの部分Interfaceをし,実装するべきかを考察した.以下の図3では, syscallのさらに一部分であるsys\_readをInterfaceを用いて実装するとどうなるか考慮したものを簡潔に表した.

%\newpage
\begin{figure}[ht]
     \begin{center}
     \includegraphics[width=65mm]{pic/xv6_interface.pdf}
     \end{center}
     \caption{sys\_readのInterfaceとその実装の考案}
    \label{fig:perl6buil}
\end{figure}

xv6のkernel部がどのような動きをし,処理はどんな手順を踏むのかを考慮しながらxv6にInterfaceを実装していく.

%呼び出されたCodeGearの番号とcontext上のinterfaceの引数で状態が分かる．
\section{今後の課題}
先行研究\cite{CbC}によって,xv6のkernelの一部をCbCの特徴でもある継続を用いモジュール化された.
しかし現在では, xv6にinterfaceはまだ搭載されていない.そのため今後, xv6のkernelをinterfaceを用いる事によってどのようにモジュール化できるかInterfaceとその実装を考察しながらCbCのinterfaceをxv6に実装していく必要がある.
また,CbCのIntterfaceを利用しているためAgdaを用いて検証することが可能であるため,実装が正しい実装なのか検証することも求められる.

%\begin{thebibliography}{9}

\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}

%\end{thebibliography}
\end{document}