Mercurial > hg > Papers > 2020 > menikon-thesis
changeset 26:f1431caec829
tweak
| author | menikon |
|---|---|
| date | Sun, 16 Feb 2020 00:17:41 +0900 |
| parents | d4c7ffd507a3 |
| children | 5317715ca32d |
| files | final_main/fig/seni.graffle final_main/fig/seni.pdf final_main/main.pdf final_sub/pic/seni.graffle final_sub/pic/seni.pdf final_sub/utf8.pdf final_sub/utf8.tex rewrite_xv6_FileSystem_in_CbC.mm |
| diffstat | 8 files changed, 18 insertions(+), 44 deletions(-) [+] |
line wrap: on
line diff
--- a/final_sub/utf8.tex Sat Feb 15 22:13:27 2020 +0900 +++ b/final_sub/utf8.tex Sun Feb 16 00:17:41 2020 +0900 @@ -61,19 +61,14 @@ \thispagestyle{fancy} \centering \begin{onecolabstract} -The OS is required to guarantee reliability and expandability. The Gears OS is being developed using Continuation based C (CbC) with the goal of guaranteeing reliability for normal-level computations and realizing scalability with meta-level computations. -CbC uses a basic processing unit called Code Gear and a data unit called Data Gear. Code Gear of normal level and meta level can be described for detailed processing, and transition between CodeGear can be performed without stacking values. For Code Gear, there is an input Data Gear and an output Data Gear, and reliability is assured by checking whether the expected output is produced for the input. -CbC's Interface is a mechanism for modularizing Gears OS. This Interface corresponds to Java Interface and Haskell type class, and can be described separately by specification and implementation by introducing. By using Interface, it is possible to expand by verification and replacement of functions. -As a pre-stage, it rewrites xv6, which is a simple operating system that has the basic structure of Unix such as process, virtual memory, separation of kernel and user, interrupt, file system, etc., with CbC. -In this paper, we aim to clarify the complicated FileSystem by rewriting the FileSystem of xv6 by CbC, guarantee the reliability, and realize scalability by using Interface. - +The OS is required to guarantee reliability and expandability. The Gears OS is being developed using Continuation based C (CbC) with the goal of guaranteeing reliability for normal-level computation and achieving scalability by meta-level computation. CbC uses a basic unit of processing called Code Gear and a unit of data called Data Gear. For Code Gear, there is an input Data Gear and an output Data Gear, and reliability is assured by checking whether the expected output is obtained for the input. CbC Interface is a mechanism for modularizing Gears OS. The use of Interface makes it possible to expand by verification and replacement of functions. As a pre-stage, it rewrites xv6, which is a simple operating system that has the basic structure of Unix such as processes, virtual memory, separation of kernel and user, interrupts, and file systems, with CbC. In this paper, the goal is to clarify the complex FileSystem by rewriting the xv6 FileSystem with CbC, to guarantee the reliability, and to realize the extensibility by enabling the Interface. \end{onecolabstract}] \section{OS に対する信頼性の保証} OS には信頼性の保証と拡張性の実現が求められている。信頼性をノーマルレベルの 計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Continuation based C (CbC) を用いて Gears OS を開発中である。 -CbC は Code Gear という基本的な処理の単位と Data Gear というデータの単位を用いる。細かい処理に対してノーマルレベルとメタレベルの Code Gear を記述し、stack に 値を積む事なく CodeGear 間を遷移することができる。Code Gear に対して入力の Data Gear と 出力の Data Gear が存在し、入力に対して期待される出力がされてるか検査することで信頼性を保証する。 -CbC の Interface は Gears OS のモジュール化の仕組みである。この Interface は、Java の Interface や Haskell の型クラスに対応し、導入することで仕様と実装に分けて記述することが出来る。Interface を使うことで検証や機能の入れ替えによる拡張が可能となる。 +CbC は Code Gear という基本的な処理の単位と Data Gear というデータの単位を用いる。Code Gear に対して入力の Data Gear と 出力の Data Gear が存在し、入力に対して期待される出力がされてるか検査することで信頼性を保証する。 +CbC の Interface は Gears OS のモジュール化の仕組みである。Interface を使うことで検証や機能の入れ替えによる拡張が可能となる。 前段階としてシンプルであるがプロセス、仮想メモリ、カーネルとユーザーの分離、割り込み、ファイルシステムなど Unix の基本的な構造を持っている OS である xv6 を CbC で書き換えている。 本論文では、xv6 の FileSystem を CbC によって書き換えることにより 複雑な処理である FileSystem を明確化させ信頼性を保証、 Interface を使用可能とすることで拡張性を実現することを目標とする。 \section{xv6} @@ -87,22 +82,10 @@ 以下の Code1 に CodeGear 遷移時のコード例を示す。 \lstinputlisting[label=cbcexample, caption=CodeGearの継続の例]{src/cbc_example.cbc} - -また CbC における CodeGear 間の継続にはスタックが使用されず、呼び出し元の環境などを持たない為軽量継続と呼ぶ。 -現在 CbC は C コンパイラである GCC 及び LLVM をバックエンドとした clang 上で実装されている。 - \section{context} context とは一連の実行が行われる際に使用される CodeGear と DataGear の集合である。 従来のスレッドやプロセスに対応する。Context は接続可能な CodeGear、Data Gear のリスト、Data Gear を確保するメモリ空間、実行される Task への Code Gear 等を持っている。 -CodeGear が別の CodeGear に遷移する際、必ず context を参照し enum で定義された CodeGear の番号を指定し遷移する。ノーマルレベルで見た際の CodeGear、DataGear および context の関係を以下の図1に簡潔に示す。 - -\begin{figure}[ht] - \begin{center} - \includegraphics[width=65mm]{pic/context.pdf} - \end{center} - \caption{CodeGear、DataGear、contxtの関係図} - \label{fig:perl6buil} -\end{figure} +CodeGear が別の CodeGear に遷移する際、必ず context を参照し enum で定義された CodeGear の番号を指定し遷移する。 \section{CbCのInterface} 先述した通り、CbC の Interface は Gears OS のモジュール化の仕組みである。 Interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。呼び出される Code Gear の引数となる Data Gear はここで 全て定義される。 Interface を定義することで複数の実装を持つことができる。このInterfaceは、Java の Interface や Haskell の型クラスに対応し、導入することで仕様と実装に分けて記述することが出来る。 @@ -110,37 +93,22 @@ \section{xv6 の FileSystem} FileSystem とは、コンピュータの資源を操作するための OS が持つ機能のことである。 ファイルといえば記憶装置内に格納されている情報を指すが、xv6 の FileSystem は、デバ イスやプロセス、カーネル内の処理をする際の情報などをファイルとして扱う。OS ごとに 利用している FileSystem は異なるが、一部の OS を除きほとんどの OS には FileSystem が存在する。 - \section{CbC による xv6 FileSystem の書き換え} -FileSystem は複雑な処理を行っている。そのため xv6 の FileSystem 部にInterface を定義、実装してやることにより OS の信頼性が向上すると考えた。本研究で定義した FileSystem の Interface とその実装について図\ref{fig:fsfilesystem}に示した。 +xv6 FileSystem の CbC による書き換え方針は、FileSystem が記述されている fs.c で定義されている 関数を CbC によって書き換えることにより処理の明確化と信頼性の保証をしたい。そのために今回は、Basic Block 単位に書き換えを行った。また、CbC の Interface を用いることにより仕様と実装を分離し拡張性を実現する。 +まず、Filesystem Interfaceを定義し、それに対応したCodeGear を用いることによって Interface を実装していく。Interface を実装する際に明示的に次の遷移先が決まっている場合 +、Java の private メソッドのように扱うため別に分けて private 実装してやる。その際 interface の時と同じようにヘッダーファイルを作成し、使うCodeGear を全て定義する必要がある。どのような処理の流れをするか図\ref{fig: seni}に示す。 \begin{figure}[ht] \begin{center} - \includegraphics[width=80mm]{pic/fsInterface.pdf} + \includegraphics[width=100mm]{pic/seni.pdf} \end{center} - \caption{xv6 FileSystem の Interface と実装} - \label{fig:fsfilesystem} + \caption{} + \label{fig: seni} \end{figure} -書き換え方針は、if 文の中に if 文がある場合や for 文がある場合には処理を細かく分離してやり分 かりやすくする。また、CbC の Interface を用いることにより仕様と実装を分離し拡張性を実現することを目標に行った。 - -書き換えたコードおよび書き換え部分が多いため全ては載せることができないため、具体的に FileSystem のialloc という関数の処理を書き換えた場合どのようになったか図\ref{fig:iallocloop}に示す。 - -\begin{figure}[ht] - \begin{center} - \includegraphics[width=80mm]{pic/iallocloop.pdf} - \end{center} - \caption{allocinode の ループによる遷移図} - \label{fig:iallocloop} -\end{figure} - -ialloc の処理は、iallocfs impl からの受け皿としての allocinode、for 文のループ条件を確認 する allocinode\_loopcheck、ループした際の処理をする allocinode\_loop、ループから抜け た際の処理をする allocinode\_noloop の 4 つの CodeGear から成り立ち。 ループの 条件に当てはまらない際は panic へと処理が移り処理が停止するように書き換えた。 -本論文では ialloc\_impl という関数を取り上げて説明したが、FileSystem が記述されている fs.c で定義されている関数に関しては全て CbC を用いることにより状態遷移ベースに 書き変え挙動を明確化した \section{まとめと今後の課題} - 本研究では xv6 の FileSystem 部分について CbC を用いて書き換えを行った。実際に FileSystem を CbC で書き換えることによって、複雑であった処理の流れを明確にすることができた。さらに、FileSystem を Interface とその実装に書き換えることによって仕様と実装に分けることができた。仕様と実装に分けることによって拡張性を高めることができた。しかし、xv6 は Gears OS を開発する前段階として開発しているので今後は書き換えた xv6 を Gears OS に適応した形に改良していく必要がある。xv6 の FileSystem 部分書き換え後 、デバックをまだ行っていないため正常に動くかどうか確認することが求め られる。また、正常に動作しなかった場合は修正を行い、OS として機能しているか再確認する必要がある。 -今後の課題として、現段階では FileSystem と Paging などの kernel の一部のみ書き換えられているため kernel 全体の書き換えを完了させる必要がある。また、書き換えにより実装した xv6 が実機上で動作するか確認する必要がある。 -\thispagestyle{fancy} + 本研究では xv6 の FileSystem 部分について CbC を用いて書き換えを行った。実際に FileSystem を CbC で書き換えることによって、if 文と for 文を切り出してやるができた。 さらに、FileSystem を Interface とその実装に書き換えることによって仕様と実装に分け、拡張性を高めることができた。xv6 の FileSystem 部分書き換え後 、デバックをまだ行っていないため正常に動くかどうか確認することが求められる。 また、正常に動作しなかった場合は修正を行い、OS として機能しているか再確認する必要がある。\thispagestyle{fancy} %\begin{thebibliography}{9} \nocite{*}
--- a/rewrite_xv6_FileSystem_in_CbC.mm Sat Feb 15 22:13:27 2020 +0900 +++ b/rewrite_xv6_FileSystem_in_CbC.mm Sun Feb 16 00:17:41 2020 +0900 @@ -24,6 +24,12 @@ <node CREATED="1581234915883" ID="ID_278085488" MODIFIED="1581234936960" TEXT="DataGear"> <font NAME="SansSerif" SIZE="28"/> </node> +<node CREATED="1581484591245" ID="ID_1626132706" MODIFIED="1581484615314" TEXT="Meta CodeGear"> +<font NAME="SansSerif" SIZE="28"/> +</node> +<node CREATED="1581484617622" ID="ID_397585043" MODIFIED="1581484628754" TEXT="Meta DataGear"> +<font NAME="SansSerif" SIZE="28"/> +</node> </node> <node CREATED="1580705994831" ID="ID_147343293" MODIFIED="1581366899992" POSITION="right" TEXT="GearsOS"> <font NAME="SansSerif" SIZE="28"/> @@ -89,7 +95,7 @@ <node CREATED="1581363980690" ID="ID_346293316" MODIFIED="1581412844263" TEXT="FileSystem の Interface の実装(fs_impl.CbC一部抜粋)"> <font NAME="SansSerif" SIZE="28"/> </node> -<node CREATED="1581366444540" ID="ID_522190874" MODIFIED="1581366621235" TEXT="fs の Context を載せてInterfaceと比較するのもあり？"> +<node CREATED="1581366444540" ID="ID_522190874" MODIFIED="1581572575490" TEXT="fs の Context を載せてInterfaceと比較するのもあり？"> <font NAME="SansSerif" SIZE="28"/> <node CREATED="1581366506336" ID="ID_184279536" MODIFIED="1581366583430" TEXT="Contextには全てのDataGearとCodeGearがあるがInterfaceは利用するのだけみたいに"> <font NAME="SansSerif" SIZE="28"/>