\documentclass[12pt,a4paper,platex]{jreport} 
\usepackage{master_paper}
\usepackage{ascmac}
\usepackage[dvipdfmx]{graphicx}
\usepackage{here}
\usepackage{listings}
\usepackage{comment}
\usepackage{url}
\usepackage[deluxe, multi]{otf}



%\input{dummy.tex} %% font


\jtitle{GearsOSのファイルシステムにおけるGCと\\レプリケーション}
\etitle{GC and Replication in the File System of GearsOS}
\year{2024年 3月}
\eyear{March 2024}
\author{又吉 雄斗}
\eauthor{Matayoshi Yuto}
\chife{指導教員：教授 和田 知久}
\echife{Supervisor: Prof. Wada Tomohisa}

\marklefthead{% 左上に挿入
  \begin{minipage}[b]{.4\textwidth}
    琉球大学大学院学位論文(修士)
\end{minipage}}

% \markleftfoot{% 左下に挿入
%  \begin{minipage}{.8\textwidth}
%    Gears OS の Paging
% \end{minipage}}

\newcommand\figref[1]{図 \ref{fig:#1}}
\newcommand\coderef[1]{ソースコード \ref{code:#1}}

\lstset{
  frame=single,
  keepspaces=true,
  stringstyle={\ttfamily},
  commentstyle={\ttfamily},
  identifierstyle={\ttfamily},
  keywordstyle={\ttfamily},
  basicstyle={\ttfamily},
  breaklines=true,
  xleftmargin=0zw,
  xrightmargin=0zw,
  framerule=.2pt,
  columns=[l]{fullflexible},
  numbers=left,
  stepnumber=1,
  numberstyle={\scriptsize},
  numbersep=1em,
  language={},
  tabsize=4,
  lineskip=-0.5zw,
  escapechar={@},
}
\def\lstlistingname{ソースコード}
\def\lstlistlistingname{ソースコード目次}

%%% 索引のために以下の2行を追加
\usepackage{makeidx,multicol}
\makeindex
\begin{document}
%rome
\makecover

\maketitle

\pagenumbering{roman}
\setcounter{page}{0}
\newpage
\makecommission
%\input{chapter/signature.tex}

\newpage

%要旨
\input{chapter/abstract.tex}

\mainmatter
%目次
\tableofcontents

%図目次
\listoffigures

%リスト目次
\lstlistoflistings

%chapters

\chapter{GearsOSにおけるファイルシステムとDB}

情報システムの信頼性を確保することは重要な課題である．
2023年には，銀行，航空機予約，電子決済などのシステムで障害が発生し，
社会的な影響を及ぼした\cite{zengin,ana,glory}．
これらのシステムの不具合を防ぎ，
提供者や利用者のリスクを最小限に抑えるためには，堅牢なシステム構築が不可欠である．
アプリケーション，オペレーティングシステム，データベース，そして物理的なコンポーネントまで，
様々な要素が連携してこれらのシステムを支えており，
これらの一つ一つに対する厳密な検証が，全体としての堅牢性を高めることに繋がる．

当研究室では，信頼性の保証を目的としたGearsOSを開発しており，
定理証明やモデル検査などの形式手法を用いて信頼性を保証できることを目標としている\cite{modelcheck}．
一般的にソフトウェアの動作を検証する手法としてテストコードを用いることが挙げられる．
しかしながら，OSなどの大規模なソフトウェアにおいて人力で記述するテストコードのみでは
カバレッジが不十分であり，検証漏れが発生する可能性がある．
よって，GearsOSはテストコードに加え，
形式手法を用いることでより厳密に動作検証を行うことができるソフトウェアの構築を目指す．
GearsOSは当研究室で開発しているプログラム言語であるContinuation based C(CbC)で記述されており，
ノーマルレベルとメタレベルを容易に切り分けることを可能とする拡張性を有す．
CbCによって本来行いたい処理をノーマルレベルで記述し，
形式手法の処理をメタレベルで記述するといった書き分け，
拡張を比較的容易に可能とする．

OSの重要な機能の1つとしてファイルシステムが挙げられる．
OSの機能は多岐に渡り，複雑であるためOS全体を検証することは非常に難しいとされる．
そのため，OSのコンポーネントの中でも特に重要で全体に影響を及ぼすファイルシステムを検証することが，
OSを検証するための最初の課題として取り上げられる\cite{10.1007/s00165-006-0022-3}．
ファイルシステムには可変長の文字列を格納するファイルと，
そのファイルにアクセスするための名前管理の機能がある．
ファイルの名前の一貫性は名前管理によって保証される．
しかし，ファイルに同時に書き込まれた際の一貫性を保証する機能を
ファイルシステムとしては持っておらず，
ファイルの書き込みを制御するロック機構をアプリケーションが持つことによって，
ファイルの一貫性を保証している．ファイルシステムによく似たものとしてDBが挙げられる．
DBは入力の属性名と型の組み合わせを複数持つレコードと，
特定の属性をキーとしたテーブルがある．
また，レコードのinsert，delete，updateの直列化可能性を保証する機能を持つ．
ファイルシステムとDBは格納するものの形式やそれにアクセスする方法，
直列化可能性を保証する手法が異なるが，
データをある形式で保持する仕組みであるという本質的な部分において違いはない．
よって，ファイルシステムとDBを同一のシステムとして実装することが可能であると考える．

当研究室におけるDBに関する取り組みとして木構造分散データベースJungleが挙げられる\cite{christie}．
Jungleは非破壊RedBlackTreeを基本構造とし，木構造を直接扱うデータベースである．
木構造を扱うことによって，XMLやJsonで記述された構造をデータベースの設計をすることなく読み込むことが可能である
といった特徴を持つ．
分散フレームワークAliceによって分散構成をとり，
その仕組みの改良版として分散フレームワークChristieが開発された．
Christieは木構造などのデータ構造をネットワーク上でやり取りすることができ，
GearsOSの分散ファイルシステムとして使えるのが望ましい．


ファイルシステムはGearsOSにおいても実装をする必要があると考えられ，
当研究室ではGearsOSにおける，
分散ファイルシステムやi-nodeを用いたファイルシステムの設計をしてきた\cite{cfile, file, directory}．
それらのファイルシステムは基本構造として非破壊RedBlackTreeを持つ．
しかし，非破壊RedBlackTreeはデータが無尽蔵に増加するため，実用上の問題があると言える．
よって，データの増加を防ぐような仕組みが必要である．
また，本システムにはデータの多重度や一貫性を確保するための機能がないため実装したい．
本研究では，実用的なGearsOSのファイルシステムの構築を目指し，
データの多重度や一貫性の確保，非破壊RedBlackTreeの無尽蔵な増加を防ぐためのGCとレプリケーション，
バックアップ機構の設計を行い，
それらを実現するために必要なRedBlackTreeのコピーの仕組みの設計，構築，考察を行った．

\chapter{軽量継続を基本とする言語CbC}

Continuation based C(CbC)\cite{cbcllvm,cbc}はC言語の下位言語であり，
関数呼び出しを行わない軽量な継続を基本とするプログラミング言語である．
CbCは処理の単位のCodeGear，データの単位のDataGearといったGearの概念をもつ．
CodeGearはC言語などにおける関数と違い，gotoによるjmp命令が用いられ，
プログラムの継続においてコールスタックを持たない．
これを通常の関数による継続と区別して，軽量継続と呼ぶ．
軽量継続によってリフレクションのような処理の挿入や切り分けを容易にしている．

\section{Gearの概念}

CbCには処理の単位のCodeGearとデータの単位であるDataGearという概念が存在する．
CodeGearは\texttt{\_\_code}という記述で宣言することができる．
CbCはC言語の下位言語であるため，通常の関数も使用することは可能だが，
基本的にCodeGearの単位でプログラミングを行う．
DataGearはCodeGearで入出力される変数データである．
図\ref{fig:dgcg}はCodeGearとDataGearの入出力の関係を表している．
CodeGearはDataGearを複数入力として受け取ることができ，
別のDataGearに複数書き込み出力することができる．
特に，入力のDataGearをInput DataGear，出力のDataGearをOutput DataGearと呼ぶ．
gotoで次のCodeGearに遷移する際，Output DataGearを次のCodeGearのInput DataGearとして渡すことができる．

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

\section{gotoによる軽量継続}

CodeGearから次のCodeGearに遷移していく一連の動作を継続と呼ぶ．
通常の関数の場合，関数から次の関数へ遷移する時にfunction callが行われる．
function callは前の関数へ戻る場合があり，そのためにcall stackを保存する．
他方，CbCの継続はfunction callをせずにgotoによるjmpで行われる．
jmpはfunction callと異なり，call stackによる変数などの環境を保存しない．
よって，CbCのgotoによる継続はfunction callによる継続と比較して軽量であるといえる．
そのことから，CbCにおける継続をfunction callによる継続と区別して，軽量継続と呼ぶ．
軽量継続の利点としてリフレクションのような処理をより柔軟に行える点が挙げられる．
リフレクションはプログラム自身のメタデータを分析し，
それによってプログラムを実行時に書き換える一種のメタプログラミング手法である．
一般的にクラスやメソッド，関数の単位で書き換えが行われる．
手法の例としてJavaにおけるAspectJライブラリを用いたプログラミングが挙げられる\cite{10.1145/1353482.1353504}．
軽量継続の場合，CodeGear遷移のどの地点においてもメタな処理を挿入することが可能であるため，
より柔軟なリフレクションが可能と考える．


\section{CodeGearの記述例}

CbCのプログラム例をソースコード\ref{src:cbc}に示す．
まずmain関数においてadd1 CodeGearへgotoを行う．
その際add1へInput DataGearとしてnを渡す．
Cのgotoが\texttt{goto label;}という記法で，ラベリングした箇所へjmpを行うのに対し，
CbCのgotoは\texttt{goto add1(n);}という記法で，add1 CodeGearへn DataGearを渡してjmpを行う．
add1は処理の最後にadd2 CodeGearへgotoを行う．
その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進め，
最後はexit\_codeへgotoすることで処理を終了する．

\lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}

\chapter{信頼性の保証を目的としたGearsOS}

GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである．
GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ．
軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する．
同様にGearの概念を持つContinuation based C（CbC）で記述されており，ノーマルレベルとメタレベルの処理を切り分けることが容易である．
また，GearsOSは現在開発途上であり，OSとして動作するために今後実装しなければならない機能がいくつか残っている．

\section{3種類のGearsOS}

GearsOSには現在3つの種類がある．
1つ目が形式手法による信頼性の向上を目的とした，GearsAgdaと呼ばれるGearsOSである\cite{gearsagda}．
これは，定理証明支援系であるAgdaによって実装されており，
森 逸汰によるGearsAgdaによるRed Black Treeの検証などの取り組みがされている\cite{garbtree}．
2つ目はスタンドアロンOSの開発を目的とした，CbC\_xv6と呼ばれるGearsOSがある\cite{cbcxv6}．
これは，教育用に開発されたx.v6\cite{xv6}をCbCで書き換える形で実装している．
CbC\_xv6では仲吉 菜々子によるGears OSのCodeGear Managementの取り組みがされている\cite{gearscodemngment}．
3つ目はユーザーレベルタスクマネジメントの実装を目的としたGearsOSがある．
これは，CbCによって実装されており，
分散ファイルシステムの設計やRedBlackTreeでのディレクトリシステムの構築などの取り組みがされている\cite{cfile, directory}．

本研究では，CbCによって実装されたユーザーレベルタスクマネジメント実装のGearsOSを対象に
ファイルシステムのレプリケーションやGC機能の実装を考える．
以下，GearsOSはユーザーレベルタスクマネジメント実装のGearsOSを指す．

\section{GearsOSとGearsAgda}

GearsAgdaではRedBlackTreeの証明が進められており，
それはGearsOSの信頼性の保証につながっている．
GearsAgdaはGearsOSの実行単位CodeGearと直接対応しており，
GearsAgdaでRedBlackTreeを証明できれば，GearsOSの大部分の構造を証明できたことになる．
なぜならば，GearsOSの構造の多くはRedBlackTreeで構成されているからである．
RedBlackTreeの証明の現状はfindの証明が完了し，insertの証明を進めているところである．

\section{メタ処理を記述するmetaGear}

図\ref{fig:meta-cgdg}はCodeGearの遷移とMetaCodeGearの関係を表している．
OSのプログラムはユーザーが実際に行いたい処理を表現するノーマルレベルと，
カーネルが行う処理を表現するメタレベルが存在する．
ノーマルレベルで見るとCodeGearがDataGearを受け取り，
処理後にDataGearを次のCodeGearに渡すという動作をしているように見える．
しかしながら，実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，
それらの計算はMetaCodeGearで行われる．
その際，MetaCodeGearに渡されるDataGearのことは特にMetaDataGearと呼ばれる．
また，CodeGearの前に実行されるMetaCodeGearは特にstubCodeGearと呼ばれ，
メタレベルを含めるとstubCodeGearとCodeGearを交互に実行する形で遷移していく．

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

\section{全てのGearを参照するContext}

ContextはGearsOS上全てのCodeGear，DataGearの参照を持ち，CodeGearとDataGearの接続に用いられる．
OS上の処理の実行単位で，従来のOSにおけるプロセスに相当する機能であるといえる．
また，CodeGearをDataGearの一種であると考えると，ContextはGearの概念ではMetaDataGearに当たる．
Contextはノーマルレベルから直接参照されず，必ずMetaDataGearとしてMetaCodeGearから参照される．
それは，ノーマルレベルのCodeGearがContextを直接参照してしまうと，
メタレベルを切り分けた意味がなくなってしまうためである．

図\ref{fig:context}はContextを参照する流れを表したものである．
まずCodeGearがOutputDataGearへデータをoutputする．
stubCodeGearはInputDataGear（前のCodeGearのOutputDataGear）とOutputDataGearをContextから参照し，次のCodeGearへgotoを行う．
CodeGearでの処理後，OutputDataGearへデータをoutputする．

Contextはいくつかの種類に分けることができる．
OS全体のContextを管理するKernel Contextやユーザープログラムごとに存在するUser Context，
CPUやGPUごとに存在するCPU Contextがある．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=150mm]{fig/context.pdf}
  \end{center}
  \caption{Contextを参照する流れ}
  \label{fig:context}
\end{figure}

\section{モジュール化の仕組みInterface}

Gears OSにはモジュール化の仕組みであるInterfaceという概念が存在する．
モジュール化とはJavaのクラスのように複数のメソッドや属性を1つの機能として
まとめて記述することである．
GearsOSではInterfaceによって，DataGearやCodeGearを複数まとめてモジュール化する．
Interfaceは仕様と実装を分けて記述する．
例としてQueue Interfaceの仕様記述部分をソースコード\ref{src:Queue.h}に示す．

\lstinputlisting[label=src:Queue.h, caption=Queueのインターフェース]{src/Queue.h}

Interfaceの仕様はC言語の構造体定義の形で記述する．
2，3行目はDataGearを記述しており，DataGearは\texttt{union Data*}型で表現する．
ここにはInterfaceにおいて，CodeGearが使用するDataGearを列挙する．
5行目から10行目まではCodeGearの引数型を記述しており，\texttt{\_\_code}型で表現する．
ここに列挙したCodeGearはInterfaceのAPIとして機能する．
InterfaceのAPIの呼び出し例をソースコード\ref{exinterface}に示す．

\begin{lstlisting}[label=exinterface,frame=lrbt,caption={Interfaceの呼び出し}]
  __code odgCommitCPUWorker3(struct CPUWorker* worker, struct Context* task) {
    int i = worker->loopCounter;
    struct Queue* queue = GET_WAIT_LIST(task->data[task->odg+i]);
    goto queue->take(odgCommitCPUWorker4);
  }
\end{lstlisting}

4行目でgotoによってqueue Interfaceのtake CodeGearに継続するよう記述している．
takeのinputDataGearにはodgCommitCPUWorker4 CodeGearを指定している．
ソースコード\ref{src:Queue.h}の仕様記述ではtakeにはqueue，nextがinputDataGearの型として指定されている．
しかし，実際に呼び出す際にはnextに当たるodgCommitCPUWorker4のみを渡している．
仕様記述の際に全てのCodeGearの第1引数(inputDataGear)に渡している\texttt{Impl* queue}は，
仕様から実装のCodeGearにgotoするために必要な記述である．
軽量継続において，CodeGearを跨いで状態を保持することはできない．
よって仕様から実装に遷移するためには，実装のCodeGearをinput DataGearとして渡す必要がある．
このImplの第1引数はstubCodeGearで自動挿入されるため，
実際にAPIを使用する際は渡す必要がない．
inputDataGearのnextはCodeGearの処理が終わった際に次にgotoするCodeGearを指定する．
よって，take CodeGearの処理が全て終了すると，次にodgCommitCPUWorker4へgotoする．
nextは\texttt{next(...)}と引数に\texttt{...}が渡される．
これは仕様を記述する時点では不定である次に遷移するCodeGearのinputDataGearを表現している．
GearsOSでgotoする際は実際にはContextから必要な値を取り出す．
よって，\texttt{...}は必要な値をContextから取り出すことを意味している．

次にInterfaceの実装について説明する．
Queue Interfaceの実装の1つであるSingleLinkedQueueをソースコード\ref{src:SingleLinkedQueue.cbc}に示す．

\lstinputlisting[label=src:SingleLinkedQueue.cbc, caption=Queueのインターフェース]{src/SingleLinkedQueue.cbc}

3行目の\texttt{\#impl as}はInterfaceの実装を記述する際に指定する．
implの直後に実装したいInterfaceの仕様を指定し，
asの後ろには実装の型名を記述する．
そのため，\texttt{\#impl "Queue.h" as "SingleLinkedQueue.h"}は仕様Queueの実装を
SingleLinkedQueueとして定義することになる．
7行目の\texttt{createSingleLinkedQueue}はSingleLinkedQueueのコンストラクタを定義しており，
DataGearのアロケートやCodeGearを保持するメソッドの初期化を行っている．
8，9行目ではnewでアロケートを行っている．
アロケートのようなメタレベルの処理はノーマルレベルには記述されない．
そのためこのnewはC言語のnewとは違うGearsOS独自の記述であり，
実際にはメタレベルにアロケートを行う処理を挿入している．
10〜16行目ではSingleLinkedQueueで使用するCodeGearとDataGearを
queueのメソッドとして初期化している．
CodeGearはQueueの仕様で記述したCodeGearと一致している．
\texttt{C\_}で始まる記述にはenum CodeにおけるCodeGearの整数を格納している．
CodeGearはenum Codeで整数と対応付けられており，
この整数を元にCodeGearが参照される．
20行目以降では\texttt{putSingleLinkedQueue}や\texttt{takeSingleLinkedQueue}
のように，仕様で記述されたCodeGearを実装している．
15，16行目では実装の型定義で定義されたその実装独自のDataGearを初期化している．
実装の型定義はソースコード\ref{src:SingleLinkedQueue.h}の通りである．

\lstinputlisting[label=src:SingleLinkedQueue.h, caption=SingleLinkedQueueの型定義]{src/SingleLinkedQueue.h}

3行目にあるように，実装の型定義ではimplキーワードで実装した型名を指定する．
4，5行目でSingleLinkedQueueが独自にもつtop，lastのDataGearを記述している．

\section{GearsOSのRedBlackTree}

Red-black tree(赤黒木)は二分探索木の一種で，
ノードに赤か黒の色を付けて色に関するいくつかの条件をもつデータ構造である．
木に対する探索，挿入，削除操作における最悪計算量がO(log n)であるため，
赤黒木は大規模なデータを扱う際に効率的なデータ構造となる．

GearsOSのRedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり，
ディレクトリ構造を表現するために使用されている．
GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に示す．

\lstinputlisting[label=src:Tree.h, caption=Treeの仕様]{src/Tree.h}

ソースコード\ref{src:Tree.h}より，Treeはtree DataGearと
put，get，remove，nextの4つのCodeGearをAPIとして持っていることがわかる．
他にも探索や木のローテートを行うCodeGearが実装されているが，
RedBlackTreeのAPIとして提供しているのはput，get，removeの3つであり，
RedBlackTree Interfaceの使用者は木に対してこの3つの操作ができる．
それぞれノードの挿入，取得，削除を行うCodeGearである．
取得は，指定したnodeと一致するノードを木から探し，
存在すればそのまま返す．
次に，RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す．

\lstinputlisting[label=src:RedBlackTreeImpl.cbc, caption=RedBlackTreeの実装]{src/RedBlackTreeImpl.cbc}

ソースコード\ref{src:RedBlackTreeImpl.cbc}の4行目から，
RedBlackTreeはTreeの実装であることがわかり，
13〜16行目で仕様に対応するCodeGearを初期化している．
19，20行目ではRedBlackTreeが実装で持つ変数を初期化している．
次に，RedBlackTreeの実装の型定義をソースコード\ref{src:RedBlackTree.h}に示す．

\lstinputlisting[label=src:RedBlackTree.h, caption=RedBlackTreeの実装の型定義]{src/RedBlackTree.h}

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=100mm]{fig/rbtree_def.pdf}
  \end{center}
  \caption{RedBlackTreeのノードの種類}
  \label{fig:rbtree-def}
\end{figure}

2〜7行目はRedBlackTreeが持つノードを表しており，
それぞれのノードの役割は図\ref{fig:rbtree-def}のように示される．
rootはRedBlackTreeの全てのノードを参照できる親ツリーのルートノードを指す．
読み込み中のノードはcurrentで指されており，追加するノードをnewNodeで表している．
また，RedBlackTreeは挿入，更新，削除の際に木の回転操作を行う．
その際，起点のノード(current)に対して親のノードをparent，祖父母のノードをgrandparentで指す．
8行目のnodeStackは木の操作時，木を辿るために使用するスタックである．
9行目のfindNodeNextはfindNode CodeGearを実行後，次に実行するCodeGearを保持する．
10行目のresultはノードを探索する際のノードの比較結果を保持する．

ソースコード\ref{src:RedBlackTree.h}にある通り，
RedBlackTreeはNode構造体を複数持つ．
ソースコード\ref{src:Node.h}にNodeの型定義を示す．

\lstinputlisting[label=src:Node.h, caption=Nodeの型定義]{src/Node.h}

1，2行目よりノードのキーがint型であり，valueとしてDataGearのポインタを持つことがわかる．
また，3〜7行目よりleft，rightで子のNodeのポインタを持つことによって木構造を構築し，
enum ColorでRedBlackTreeとして必要なノードの色を表現していることがわかる．

\section{ALLOCATE}

DataGearを用意する際は図\ref{src:SingleLinkedQueue.cbc}の15行目にあるように，
\texttt{singleLinkedQueue->top = new Element();}のような形でnewキーワードを用いる．
これはビルド時に生成されるALLOCATEマクロに変換される．
図\ref{src:allocate.h}はALLOCATEマクロの例である．
ALLOCATEマクロはContext(context)と用意したいDataGearの型名tを渡す．
contextは\texttt{context->heap}で示されるヒープ領域を持っており，
この領域にDataGearを保持する．
6行目でDataGearのサイズ分のメモリ領域をヒープ上に確保していることがわかる．
なお，ALLOCATEマクロを直接呼ばずにnewキーワードで記述するのは，
ノーマルレベルからmetaDataGearに当たるContextを直接参照しないようにするためである．

\lstinputlisting[label=src:allocate.h, caption=ALLOCATEの定義]{src/allocate.h}

\chapter{GearsFileSystem}

ファイルシステムはOSにおいてユーザーやアプリケーションが使用するファイルや
プロセスの管理に用いられる重要なシステムである．
そのため，GearsOSにおいてもi-nodeを用いたディレクトリシステムや，
DataGearManagerによる分散ファイルシステムの仕組みをもつ，
GearsFileSystemの取り組みを行ってきた．

\section{i-nodeを用いたディレクトリシステム}

GearsFileSystemにはi-nodeを用いたディレクトリの仕組みが存在する\cite{directory}．
i-nodeは主にUnix系のファイルシステムで用いられる，
ファイルの属性情報が書かれたデータである．
inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある．
またinodeは識別番号としてinode numberを持つ．
inode numberは一つのファイルシステム内で一意の番号であり，\texttt{ls -i}コマンドで確認可能である．
inodeはファイルシステム始動時にinode領域をディスク上に確保する．
そのためinode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる．
inode numberの最大値は\texttt{df -i}コマンドで確認可能である．

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      File Types & directoryやregular fileなど，ファイルの種類 \\
      \hline
      Permissions & read write executeの実行可否\\
      \hline
      UID & ファイル所有者のID \\
      \hline
      GID & ファイル所有グループのID \\
      \hline
      File Size & ファイルのサイズ \\
      \hline
      Time Stamps & ファイル作成，編集日時 \\
      \hline
      Number of link & ハードリンクの数 \\
      \hline
      Location on hard disk & データのアドレス\\
      \hline
    \end{tabular}
    \caption{inodeでのファイル属性情報}
    \label{table:inode}
  \end{center}
\end{table}

GearsFileSystemではi-nodeをi-node numberがkey，
i-nodeでのファイル属性情報をvalueであるノードを持つinode treeをRedBlackTreeで表現している．
また，ファイル名からi-node numberを検索するためのindex treeも同じRedBlackTreeで表現している．
データ構造にRedBlackTreeのみを用いているのは，
ls，cd，mkdirといった，ディレクトリ操作を行うためのUnix Likeなユーザーインターフェースをもつ．
図\ref{fig:GearsDir}にGears Directoryの処理の例を示す．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/gears_dir.pdf}
  \end{center}
  \caption{i-nodeを用いたディレクトリシステムの処理の流れ}
  \label{fig:GearsDir}
\end{figure}

lsコマンドはディレクトリ内のファイルやファイル自体の情報を出力するコマンドである．
\texttt{ls hoge.txt}を実行すると\textcircled{\scriptsize 1}index treeを参照し，
ファイル名hoge.txtからi-node numberの2を取得する．
次に，\textcircled{\scriptsize 2}i-node treeを参照し，
i-node numberを元にファイルの属性を取得し，lsコマンドの場合はそれを出力する．

\section{非破壊RedBlackTreeによる構成}

ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する．
一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い\cite{10.1145/2501620.2501623}．
なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために，
B-Treeのようなノードを複数持つことができる構造が効果的だからである．
その点ではRedBlackTreeはB-Treeに劣る．
しかしながら，SSDはランダムアクセスによってデータにアクセスするため，
RedBlackTreeでなくB-Treeを用いる利点は少ないと考える．
よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる．
そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる．
図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している．
編集前の木構造の6のノードをAにアップデートすることを考える．
まず，ルートノードからアップデートしたいノード6までをコピーする．
その後，コピーしたもののノード6をAにアップデートする．
これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である．
参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=150mm]{fig/nonDestroyTreeEdit.pdf}
  \end{center}
  \caption{非破壊的なTree編集}
  \label{fig:TreeEdit}
\end{figure}

\section{RedBlackTreeのトランザクション}

トランザクションはDBの重要な機能の一つである．
データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう
トランザクションの仕組みを考える必要がある．
今回，ファイルシステムは全てRedBlackTreeで実装するため，
RedBlackTreeのノードに対するトランザクションを考える．

トランザクションをwriteとreadに分けて考える．
writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する．
writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える．
そのため，書き込みの並列度はルートの数と一致する．
しかしながら，ルートの置き換えは競合的なので，
複数プロセスから同時に書き込みを行っても1つしか成功しない．
よって，単一のRedBlackTreeに複数の書き込みポイントを作り，
並行実行可能にする必要がある．

% TODO: writeトランザクションの図を入れたい

RedBlackTreeに複数の書き込みポイントを作るために，
キーごとのルートを作成する．
ノードはそれぞれがキーとRedBlackTreeを持つ状態になる．
writeする際は，そのキーのルートを置き換える．
それによって，RedBlackTreeは複数の書き込みポイントを持つことができ，
writeを並行実行することが可能となる．

図\ref{fig:Transaction}にトランザクショナルなwrite操作を表す．
Aの木はファイルシステム全体を表すRedBlackTreeである．
ノードNのデータに対して書き込みすることを考えると，
キーがaであるBの木のルートからロックしCの木を作成して，
Bの木からCの木のルートに入れ替えることで書き込みを行う．
この書き込みを行っている際，
Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=130mm]{fig/transaction.pdf}
  \end{center}
  \caption{トランザクショナルなwrite操作}
  \label{fig:Transaction}
\end{figure}

% TODO: read時常に最新の情報が取れないことを説明する図を入れたい

readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である．
しかし，常に最新の情報を読み込めるとは限らない．
最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる．

\section{ディスク上とメモリ上のデータ構造}


ファイルシステムは全てRedBlackTreeで構成する．
それにより，プログラムの証明がより簡単になるからである．
また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである．
よって，それらはまとめてRedBlackTreeで構成する．

ファイルシステムとDBの違いとして，スキーマが挙げられる．
DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する．
対して，ファイルシステムにはスキーマに当たるものがなく，
データはファイルパスによって管理される．
スキーマを定義することによってデータは構造化され，
構造化されたデータは非構造化データと比較して，
インデックスを作成することが容易であり，データの検索性が向上する利点がある．
しかしながら，スキーマはDBの運用中に変更されることがあり，
スキーマを変更した以前へロールバックができない問題がある．

ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると，
スキーマを定義する必要のないスキーマレスなDBが必要になる．
ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ
DBがスキーマによって実現していた機能を付け加えることを考えたい．


\section{DataGearManagerによる分散ファイルシステム}

本研究室では，一木 貴裕\cite{cfile}GearsOSの分散ファイルシステム設計が行われ，
GearsOSの分散ファイルシステムに必要なDataGearManagerの通信路の実装がされた．
DataGearManager(以下DGMとする)はノード間でDataGearのやり取りをするための通信路を構成するための仕組みである．
図\ref{fig:DGM}にDGMのSocket通信によるWordCount例題の動作を示す．
DGMはRemoteDGMとLocalDGMがペアとなり，
RemoteDGMが送信先ノードのLocalDGMに接続することでDataGearの送信を可能にする．
RemoteからLocalへの片側方向通信となるため，相互通信したい際は2ペアで構成する．
この際の接続はC言語のSocketインターフェースを使用している．
Node BのLocal DGMが受け取ったファイルのデータをWordCountのCodeGearが処理をし，
Node AのLocalDGMに接続されたRemoteDGMに処理結果をPutすることで，
Node Aに処理結果を返している．
このように，別Nodeからデータを受け取り，
そのデータをしょりして受け取り元に処理結果などを返すことが可能な仕組みである．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=150mm]{fig/dgm.pdf}
  \end{center}
  \caption{DGMのSocket通信によるWordCount例題}
  \label{fig:DGM}
\end{figure}

\chapter{GearsFileSystemにおけるGCとレプリケーション}

本章ではRedBlackTreeのCopyによるGCとレプリケーションの基本設計を述べる．
GC，レプリケーション，バックアップをRedBlackTreeのコピーを基礎とする，
統一的な仕組みにより実装することが考えられる．

\section{ファイルシステムの信頼性に関する機能}

ファイルシステムはデータを保持することを基本的な機能とし，その他の機能は追加機能として実装する．
ファイルシステムやDBにおける信頼性に関する追加機能として，
システムの電源断時にデータが残るpersistency，
データを書き込めたかどうかを判定するatomic write，
1つのノードが失われた際にデータを保護する多重性，
複数のコピーを調停するコミット機構などが挙げられる．

システムクラッシュがあった場合にデータを正しい状態に保つ機能として，
ファイルシステムにおいてはジャーナルログを使用する方法がある\cite{10.1145/3477132.3483581}．
ジャーナルログはトランザクション中のメタデータ変更の記録と，
トランザクションのコミットを記録することでクラッシュから安全に復旧することができる．
データの多重度を確保するための一般的な手法として，
データのバックアップやシステム自体のレプリケーションをすることが挙げられる．
メモリ管理の機能としてはガーベージコレクションが挙げられる．
ガベージコレクションは通常プログラム言語のレイヤで行われる．
GearsFilesystemはメモリとディスクを同等に扱うので，
ここにおけるGCとはFilesystem Fragmentationを解消するためのdefragmentation機能であるとも言える．
Filesystem Fragmentationはパフォーマンスの低下につながるため，
FragPickerといったdefragmentationツールが開発されるなど，
現代的なファイルシステムにおいても必要な機能である\cite{10.1145/3611386}．

現状のGearsOSには分散ファイルシステムの通信機能やUnix Likeな
インターフェースを持つi-nodeファイルシステムの基本機能は存在するものの，
多重性やメモリ管理などの信頼性を確保するための機能が存在しない．
これらの機能をファイルシステムのレベルで実装することで，
より堅牢なファイルシステムを構築したい．

\section{メモリの管理手法}

GCのアルゴリズムは大きく分けてMark \& Sweep GC，Reference counting GC，
Copying GCの3つの種類が存在する．
Mark \& Sweep GCはマークフェーズとスイープフェーズからなる．
マークフェーズはヒープ上でルートから参照することができるオブジェクト全てにマークをし，
その後，スイープフェーズでマークされていないオブジェクトを
使用されていないオブジェクトのリストであるフリーリストに接続することでGCを行う．
Reference counting GCはオブジェクトの被参照数を表すReference counterを用いるGCである．
新たに参照される度にReference counterをインクリメントし，
参照が外れる度にデクリメントする．
そのようにして，カウンターが0になった時点でフリーリストに接続することでGCを行う．
CopyingGCはメモリ上のヒープ領域をFrom領域とTo領域に分割し，
ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする．
From領域を参照していたポインタはTo領域のオブジェクトを参照するように置き換える．
その後，From領域とTo領域を入れ替えることでGCを行う．

一般的にこれらのGC手法は複数を組み合わせて用いられる．
世代別GCではオブジェクトの生存期間によって適用するGCアルゴリズムを使い分ける．
アロケートされてすぐのオブジェクトを新世代オブジェクト，
任意の回数のGCを生き残ったオブジェクトを旧世代オブジェクトとし，
それぞれの特性に合ったGCアルゴリズムを適用する．
すぐに回収されることが多い新世代オブジェクトはCopying GCで網羅的にGCをし，
長く生き残る旧世代オブジェクトはMark \& Sweep GCで適宜回収するなどが例として挙げられる．
このように複数のGCアルゴリズムを組み合わせることで，
それぞれのアルゴリズムの利点を享受できる．

また，メモリ管理手法としてRust言語の所有権がある．
所有権ではメモリを所有する変数がスコープを抜ける時に，
同時にメモリも解放する．
そのためRustではGCの仕組みを必要とせず，
より高速にメモリの管理を行うことができる．

\section{GearsFileSystemのGC}

GearsFileSystemのGCはCopying GCを基本的なアルゴリズムとする．
他のGC手法と比較して参照できるオブジェクトをコピーするだけであるため，
実装が簡単で，より高いスループットが期待できる．
Mark \& Sweep GCやReference counting GCの場合は，
GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある．
また，同様の構造をコピーするのみで実装することによって，
データの持続性の確保がしやすい．
ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ．
そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い．

一般的なCopying GCではFrom領域上のオブジェクトをTo領域にコピーする形で実装される．
一方，GearsFileSystemではファイルやディレクトリの基本構造であるRedBlackTreeをコピーする．
ファイルやディレクトリの操作を行うFromのRedBlackTreeから，
ルートから辿れるノードのみをToのRedBlackTreeとしてコピーする．
それにより，辿れなかったノード，つまり参照されていないノードはコピーされず，
不要なオブジェクトが回収された状態となる．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/rbtree_gc.pdf}
  \end{center}
  \caption{RedBlackTReeのCopyによるGC}
  \label{fig:TreeCopyGC}
\end{figure}

DBの重要な機能の一つにロールバックがある．
RDBのロールバックは，
コミットするまではトランザクションの開始時点に戻ることができる機能を持つ．
コミットが完了するとそれ以前の状態に戻すことはできないが，
データのバックアップをとっておくことで復元を行う．

RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し，
データの復元が行える仕組みを考える．
非破壊的なTree編集はアップデートのたびに，ルートノードを増やす．
つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる．
よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える．

ルートノードはデータのアップデート時に増えるため，
データが際限なく増加していく問題がある．
この問題はCopyingGCを行うことによって解決する．
まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する．
その後，コピーしたものはバックアップないしログとしてディスクに書き込む．
そうすることで，データの増加によるリソースの枯渇を防ぎ，
かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる．


\section{GearsFileSystemのレプリケーション}

DBの多重性を確保する機能としてレプリケーションがある．
レプリケーションはデータや状態が等しいレプリカを別のノードに生成する機能である．
レプリケーション機能があることによって，地理的に距離のあるノードにレプリカを設置することが可能になり，
災害などによって発生するシステム障害を防止することや，
アクセス分散によるネットワーク負荷の低減につながる．
そのため，GearsFileSystemにおいてもレプリケーションの機能を実装したい．

GearsFileSystemではディレクトリをRedBlackTreeによって構成しており，
RedBlackTreeから全てのデータにアクセス可能である．
よって，RedBlackTreeのコピーを行うことによって，
FileSystemのレプリカを作成することが可能であると考えられる．
GearsFileSystemのレプリケーションの基本設計を図\ref{fig:RBTreeReplica}に示す．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/rbtree_replica.pdf}
  \end{center}
  \caption{GearsFileSystemのレプリケーションの考え方}
  \label{fig:RBTreeReplica}
\end{figure}

基本的には図\ref{fig:TreeCopyGC}に示されているGCの仕組みと同様で，
RedBlackTreeのCopyで構成される．
レプリケーションにおいてコピー元をメイン，コピーをレプリカと呼ぶ場合，
Node1がメインでNode2がレプリカとなる．
Node1はGCの仕組みと同様であり，違いはNode2にもコピーを行う部分である．
このように，GCとレプリケーションを同様の仕組みで実装することが考えられる．
しかし，Node2にコピーを行う際はNode1とNode2間で操作やデータを送信するための
通信の仕組みが必要である．
レプリケーションを実装する際の通信の仕組みについて考える必要がある．
データの送受信はDataGearManagerのSocket通信の仕組みを使うことが考えられる．


\section{コピー実行のタイミング}

GCやレプリケーション，バックアップはそれを実行するタイミングが重要である．
GCはメモリの使用状況に応じて実行される．
例えば，RedBlackTreeに新規ノードを追加する際にメモリが不足した場合などが
GCを実行するタイミングとして挙げられる．
レプリケーションは同期のタイミングがあり，同期型，非同期型，準同期型が挙げられる．
また，バックアップは1日に1回，週に1回など定期的な実行をする．
そのため，RedBlackTreeのコピーにコピー実行のタイミングを制御する機構が必要である．
GearsOSは拡張性の高いCbCによって記述され，本来実行したい処理に追加の処理を挿入することが比較的容易に可能である．
図\ref{fig:GCTiming}にGC実行処理の挿入の仕組みの例を示す．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/timing.pdf}
  \end{center}
  \caption{GC実行処理の挿入}
  \label{fig:GCTiming}
\end{figure}

矢印は軽量継続であり，
\textcircled{\scriptsize 1}ではメモリアロケーションを必要とする本来行いたい処理を表している．
\textcircled{\scriptsize 2}はメモリ使用率をチェックするCodeGearを挿入し，
使用率が80\%以上の場合にGCを実行する．
メモリ使用率をチェックするCodeGearは条件によって実行するCodeGearを切り替えるものであり，
既存のGearsOSのコードにもこのような処理を行うものは存在し，
例としてSingleLinkedStackのコードの一部をソースコード\ref{src:isEmpty.cbc}に示す．

\lstinputlisting[label=src:isEmpty.cbc, caption=実行するCodeGearの切り替えのコード]{src/isEmpty.cbc}

CodeGearは遷移先のCodeGearの参照を持つ必要があるため，
inputDataGearとしてnextとwhenEmptyを渡している．
条件分岐は通常のif文で行われ，条件ごとに次のCodeGearを指定している．
このようにして，条件分岐をして実行するCodeGearを切り替えることができる．

\section{別Contextへのコピー}

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/copy_context.pdf}
  \end{center}
  \caption{別Contextへのコピー}
  \label{fig:CopyContext}
\end{figure}

図\ref{fig:CopyContext}にContextとCode Table，Data Tableの関係と，
の複数のContextがある状態を示す．
ContextはそれぞれCode TableとData Tableを持つ．
DataGearをALLOCATEするとData Tableのヒープ領域にそのDataGear分の領域が確保される．
これらの複数のContextはContextキューで管理され，
順次実行される．

RedBlackTreeは別のContextへコピーすると良い．
同じContextへコピーする場合，GCはFromとToの領域が同じヒープ領域に置かれることになる．
ヒープ領域を共有すると，FromからToへの切り替えがしづらい．
また，すでにそのヒープ領域でフラグメンテーションが起きている可能性があり，
Copying GCの利点であるコンパクションができない．
レプリケーションの場合，別のノードでは別のContextが動いているため，
同じContextにコピーできるだけではレプリケーション機能は実現できない．
別のContextへコピーすると，GCの場合，FromとToの領域が別のヒープ領域に置かれる．
そのためContextを切り替えることによってFromからToへの切り替えができ，
まっさらな状態のヒープ領域にコピーを行えるため，
リニアアロケーションをしていればコンパクションが発生する．

動的にバックアップする際のコピーを考える．
別Contextへコピーする場合，ディスクをContextのData Tableのヒープ領域と捉え，
単純にディスク書き込みを行う．
RedBlackTreeは非破壊であり，複数のルートノードによってバージョン管理されている．
そのため，あるバージョンのバックアップをリストアしたい場合がある．
現在のバージョンをディスク上にある特定のバージョンに切り替える場合，
現在のバージョンへの書き込みの最中にバージョンが切り替わるとデータの一貫性を損なう．
そのため，データリストア時の一貫性を確保する仕組みが必要となる．
また，バージョン付きのバックアップは無尽蔵にデータが増加していく問題がある．
それは，任意のタイミングでデータを区切ることで解決できる．
仮想的にData Tableを作成し，そのヒープ領域(ディスク)に対してデータをコピーする．
過去のData Tableのバージョンに戻りたい場合があるため，
Data Tableは前のData Tableの参照を持つ．


\chapter{CopyRedBlackTreeの実装}

データのバックアップやレプリケーション，GCの機能を実装するためには，
データのコピーをする必要がある．
GearsOSのファイルシステムにおいて，データは全てRedBlackTreeに格納される．
しかしながら，現状のRedBlackTreeには木をコピーする機能が無い．
よって，RedBlackTreeに木のコピー機能を実装する必要がある．
CopyRedBlackTreeの実装について述べる．

\section{Tree InterfaceのCopy API}

CopyRedBlackはTree InterfaceのAPIの1つとして実装した．
ソースコード\ref{src:TreeCopy.h}にCopy APIを追加したTree Interfaceの仕様定義を示す．

\lstinputlisting[label=src:TreeCopy.h, caption=Tree Interfaceの使用定義(Copy追加後)]{src/TreeCopy.h}

10行目にcopy()が追加されており，inputDataGearは\texttt{\_\_code} nextのみとしている．
これにより，
\texttt{goto tree->copy(next);}といった記述でRedBlackTreeのコピーを行うことができる．
次にRedBlackTreeの実装の型定義をソースコード\ref{src:CopyRedBlackTree.h}に示す．
9，12行目にある通り，コピー時に使用するtoStackを1つと
木のコピーが完了しているかどうかを示すcopiedフラグを追加している．
今回の実装ではStackを2つ使用する．
追加したtoStackの他に，元からRedBlackTreeの操作に使用しているnodeStackを用いる．
これらのStackはdataとしてNode構造体のポインタを持つ．

\lstinputlisting[label=src:CopyRedBlackTree.h, caption=RedBlackTreeの実装の型定義(Copy追加後)]{src/CopyRedBlackTree.h}

% \lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc}

\section{コピーのアルゴリズム}

コピーは2つのStackを使用し，left方向から深さ優先でRedBlackTreeのノードをリーフ方向に降りながら行う．
図\ref{fig:TreeAndStack}にコピー時のある地点でのコピー元の木と2つのStackの状態を例示する．
leftDownを2回行い，\texttt{tree->current}がkeyが1のノードを指している．
この時，木を辿るためのnodeStackは\texttt{tree->current}以前に辿った3と2のノードが積まれている．
toStackにはコピー元の木のノードとkey，value，colorの値が同じでアドレスが異なるノードが積まれている．
ノードは辿った際にコピーを行いtoStackへと積むため，すでに辿った3，2，1のノードが積まれている．
葉ノードまでたどり着いた時やleft，rightがすでに辿ったノードだった場合はupでroot方向に戻る．
その際は，\texttt{tree->current}を親ノードに付け替え，nodeStackとtoStackを1回popする．
toStackは新規にアロケートした子ノードと親ノードを接続したり，
すでにノードをアロケートしているかどうかを判断するなど，
コピー先の木を操作したり状態を確認したりするために必要である．
例えば，upする場合はコピー元のrightノードの存在を確認し，
toStackのtopをみてすでにrightノードを新規にアロケートしているかを見ることで，
さらにupするかどうかを判断するなどがある．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=150mm]{fig/copy_algo4.pdf}
  \end{center}
  \caption{コピー元のTreeと2つのStackの状態の例}
  \label{fig:TreeAndStack}
\end{figure}

図\ref{fig:CopyCGTransition}にCopy時のCodeGearの大まかな遷移を示す．
四角ノードがCodeGear，丸ノードが遷移条件を表す．
それらを囲む四角はCodeGearの遷移をLeftDown，RightDown，Upの3つのフェーズに区切ったもので，
図を簡略化するためのものである．
フェーズの四角に矢印が向くと，フェーズが持つStart(オレンジで示される箇所)から遷移が始まる．
青のStart，EndはCopyの始めと終わりである．
実際にはleftDownなどはleftDown1，leftDown2のような複数のCodeGearで構成され，
それぞれでStackの操作やアロケート，ノードの存在確認を行う．
Upはすでに木全体を辿ったかどうかを判定し，
辿っていた場合はswap CodeGearへ遷移を行う．
swapはコピー元の木とコピー先の木を入れ替える．
これはCopying GCにおけるFrom領域とTo領域を入れ替える操作を想定している．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/copy_algo3.pdf}
  \end{center}
  \caption{Copy時のCodeGearの大まかな遷移}
  \label{fig:CopyCGTransition}
\end{figure}

\section{アロケーション部分}

新規ノードのアロケーションはcopyRedBlackTree，leftDown，rightDown CodeGearで行われる．
例としてソースコード\ref{src:leftDown1.cbc}にleftDown1 CodeGearを示す．
9行目でコピー先のNodeをnewでアロケーションし，11〜14行目でコピー元からコピー先のノードへkey，value，
colorをコピーしている．
また，10行目のdataはtoStackのtopから得たもので，アロケーションしたノードの親ノードにあたる．
17行目は\texttt{data->left}にアロケーションしたノードを代入している．
そのようにしてアロケーションしたノードはtoStackにpushされ，
次にleftDownで子ノードがアロケーションされる際に参照される．
このようなアロケーションはcopyRedBlackTree，rightDownにおいても同様に行われている．
アロケーションはノーマルレベルではnewキーワードによって記述され，
メタレベルではソースコード\ref{src:allocate.h}で示した\texttt{ALLOCATE}マクロを呼び出すことによって行われる．

\lstinputlisting[label=src:leftDown1.cbc, caption=leftDown1 CodeGear(アロケーション部分の例)]{src/leftDown1.cbc}

ソースコード\ref{allocate}にビルド時に生成された，
newに対応するALLOCATEマクロの呼び出し部分を示す．
\texttt{\&ALLOCATE}にcontextと，アロケートしたいDataGearの型名を渡している．
contextは現在のContextを指しており，別のContextへのアロケーションはされていない．

\begin{lstlisting}[label=allocate,frame=lrbt,caption={ビルド時に生成されたALLOCATE部分}]
  struct Node* newNode = &ALLOCATE(context, Node)->Node;
\end{lstlisting}

\section{swap}

swapはコピー自体に関する機能ではなく，Copying GCの動作を想定した機能を実装したものである．
Copying GCがFrom領域とTo領域を入れ替えるように，
コピー前後の木を入れ替える動作をする．
swapは実際にはswap，swap1，swap2のような複数のCodeGearで構成されている．
ソースコード\ref{src:swap.cbc}に木の入れ替え処理を行うswap2 CodeGearを示す．
3行目のtoTreeは，toStackにpushした新しい木のルートノードに当たるノードである．
4行目で新規にRedBlackTreeを作成し，5行目でtoTreeをnewRedBlackTreeのrootに設定している．
その後，7行目でtreeにnewRedBlackTreeを指定することで木の入れ替えを行なっている．
これらの動作は同一のContext上で行われている．
図\ref{fig:swap}で示すように，ContextのData Table上のTree DataGearがもつRedBlackTreeを
同ヒープのFrom RedBlackTreeからTo RedBlackTreeへ参照を入れ替える．

\lstinputlisting[label=src:swap.cbc, caption=swap2 CodeGear(木の入れ替え処理部分)]{src/swap.cbc}

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=120mm]{fig/swap.pdf}
  \end{center}
  \caption{swap時のTree DGとData Tableの様子}
  \label{fig:swap}
\end{figure}

\chapter{実装の評価}


\section{非破壊RedBlackTreeの増大抑制}

今回はCopyRedBlackTreeの実装によって，
コピー先の木はコピー時にrootから参照可能であったノードのみを持ち，
参照されていないノードが排除されているため，
コピーをすることで参照する木の増大を防ぐことが可能である．
しかし，コピー元の木やゴミのメモリ領域を再利用する仕組みがないため，
メモリ領域の使用量の軽減にはつながっていない．
現状は同一Context上のCode Tableのヒープ領域に木をコピーしている．
別Contextへ木をコピーし，
コピー元のContext自体を廃棄する仕組みを実装することでメモリ領域の再利用が可能であると考える．

\section{テストコード}

CopyRedBlackTreeのプログラムを作成する際に，
図\ref{testPattern}のような11パターンの木の状態と10000ノードの木をコピーするテストコードを作成した．
11パターンの木の状態においてコピーは動作した．
10000ノードの木のコピーはヒープオーバーフローによるsegmentation fault errorが発生する．
3616ノードでは動作するため，ヒープ領域の容量が不足していると考えられる．
この事象を解決するためには，ALLOCATEする際にヒープ領域の容量不足を検知し，
ヒープ領域の拡張を行うことが考えられる．
これらのテストコードによってある程度の動作確認は可能であるが，
完全に正しい動作をしているかどうかの証明はできていない．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=120mm]{fig/test_pattern.pdf}
  \end{center}
  \caption{CopyRedBlackTreeのテストパターン}
  \label{fig:testPattern}
\end{figure}

\section{RedBlackTreeの持続性}

CopyRedBlackTreeは木を単純にコピーする機能であるため，
RedBlackTree乃至，データの持続性が確保されている．

\section{Stackの使用}

今回の実装ではSingleLinkedStackを2つ使用している．
CbCはcall stackなどの状態を持たないことによる利点があるため，
Stackを使用することによってその利点を得られなくなることが考えられる．
しかしながら，今回のStackはCall stackとは違い，プログラムの中で明示的に使用され，
また，CodeGear自体が状態を持たないため問題がない．

\chapter{まとめと今後の課題}

本研究ではGearsOSのファイルシステムであるGearsFileSystemにおける
GCとレプリケーションについての考察，CopyRedBlackTreeの実装と考察を行った．

また，今後の課題や議題として次のようなものが挙げられる．

\section{別ContextへのALLOCATION}

今回構築したcopyRedBlackTreeでは，木を同じContext上のヒープ領域にコピーする．
しかし，別ノードへのコピーを実現するには別Contextへコピーを行う必要がある．
現状は，ビルド時にメインのContextとALLOCATIONのマクロを生成するため，
別のContextを指定することができない．
そのため，ALLOCATIONに別Contextを操作するための機能を導入する必要があると考える．

\section{ヒープオーバーフロー問題}

RedBlackTreeはContext上のData Tableのヒープ領域に確保，コピーされる．
この際，ヒープ領域の容量が足りず，ヒープオーバーフローする問題がある．
ヒープ領域はContext生成時に確保され，ALLOCATEマクロによってDataGearが配置される．
ALLOCATEはDataGearをヒープ領域に配置するのみであるため，
容量が足りない場合にヒープ領域を拡張する機能を追加する必要がある．

\section{テストケースの生成}

CopyRedBlackTreeを作成する際，コピーの動作確認のためのテストケースを11パターン用意した．
その際のテストコードの行数が約1000行となった．
開発の効率化のため，より簡潔にテストコードを書けるような仕組みを作る必要があると考える．


\section{GCとレプリケーションの実装}

今回はGCやレプリケーションの実装をするために必要な木のコピー機能であるCopyRedBlackTreeの実装を行った．
Copying GCの動作を想定したswapを作成したものの，
コンパクションが行われないなどGCとして不十分な点がある．
今後は十分な機能をもったGCやレプリケーションを実装していきたい．
GCはContextの廃棄やフリーリスト，GCタイミングの機構が必要である．
また，GearsOS全体をGCすることも考えられる．
レプリケーションは別ノードでのコピーの実行やレプリカとの通信プロトコルを定義する必要があるだろう．

\section{形式手法による信頼性の検証}

Stack領域の圧縮と再利用の仕組み，別Contextへのコピーを実装した後は，
モデル検査で並行実行下で正しく動くことをメモリアロケーション部分を含めて調べたい．
また，GearsAgdaに変換，もしくは記述を行い，定理証明によって並列実行下で正しく動くか，
メモリが正しく開放されているかどうかを検証したい．

\section{その他ファイルシステムの信頼性に関する機能}

今回は木のコピーによる多重度の確保を主に扱った．
ファイルシステムの信頼性に関する追加機能は
多重度以外にも，persistencyやatomic writeに関するものがある，
Journaling Filesystemのようにジャーナルログとトランザクションの機構を取り入れたい．
persistencyはコピーでSSDなどのpersistentなデバイスに木を書き込むことが考えられる．
また，コピーに関しても複数のコピーを調停するコミット機構が必要である．

% %謝辞
\input{chapter/thanks.tex}


%参考文献
\nocite{*}
\bibliography{reference}
\bibliographystyle{junsrt}


%発表履歴
\input{chapter/history.tex}
\addcontentsline{toc}{chapter}{研究関連論文業績}

%付録
\addcontentsline{toc}{chapter}{付録}
\appendix
\input{chapter/appendix.tex}
\end{document}