Papers/2023/matac-sigos: Paper/paper.tex comparison

comparison Paper/paper.tex @ 1:c4f210d08680

update

author	matac42 <matac@cr.ie.u-ryukyu.ac.jp>
date	Fri, 14 Apr 2023 11:43:21 +0900
parents	466b958a3419
children	8b8d396619a9

comparison

equal deleted inserted replaced

-:466b958a3419
+:c4f210d08680
 その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
 このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進める．
 \lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}
-\section{GearsOS}
+\section{信頼性の保証を目的としたGearsOS}
 GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである．
 GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ．
 軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する．
 同様にGearの概念を持つContinuation based C（CbC）で記述されており，ノーマルレベルとメタレベルの処理を切り分けることが容易である．
 \end{center}
 \caption{CodeGearとMetaCodeGearの関係}
 \label{fig:meta-cgdg}
 \end{figure}
-\section{Unixのファイルシステム}
+\section{RedBlackTreeよるファイルシステムの構成}
-UnixのファイルシステムはBTreeとinodeで構成されており，xv6もその仕組みを用いている．
+ファイルシステムは全てRedBlackTreeで構成する．
-xv6\cite{xv6}はMITで教育用の目的で開発されたOSで，Unixの基本的な構造を持つ．
+それにより，プログラムの証明がより簡単になるからである．
-当研究室ではxv6のCbCでの書き換え，分析を行なっている\cite{xv6component,xv6kernel}．
+また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである．
+よって，それらをまとめてRedBlackTreeで構成する．
-inodeは主にUnix系のファイルシステムで用いられる，ファイルの属性情報が書かれたデータである．
-inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある．
+ファイルシステムとDBの違いとして，スキーマが挙げられる．
-また，inodeは識別番号としてinode numberを持つ．
+DBは事前にスキーマを定義し，それに沿ってデータを挿入したり参照したりする．
-inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である．
+対して，ファイルシステムにはスキーマに当たるものがなく，
-inodeはファイルシステム始動時にinode領域をディスク上に確保する．
+データはファイルパスによって管理される．
-そのため，inode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる．
+スキーマを定義することによってデータを構造化されるため非構造化データと比較すると
-inode numberの最大値は\emph{df -i}コマンドで確認可能である．
+インデックスを作成することが容易でデータの検索性が向上する利点がある．
+しかしながら，スキーマはDBの運用中に変更されることがあり，
-\begin{table}[tb]
+スキーマを変更した以前へロールバックができない問題がある．
-\begin{center}
-\small
+ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると，
-\begin{tabular}[htpb]{|c||l|}
+スキーマを定義する必要のないスキーマレスなDBが必要になる．
-\hline
+ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ
-File Types & ファイルの種類 \\
+DBがスキーマによって実現していた機能を付け加えることを試みる．
-\hline
-Permissions & read write executeの実行可否\\
+RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある．
-\hline
+今回用いるのは，非破壊的な実装のRedBlackTreeである．
-UID & ファイル所有者のID \\
-\hline
-GID & ファイル所有グループのID \\
+\section{ディスク上とメモリ上のデータ構造}
-\hline
-File Size & ファイルのサイズ \\
+ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する．
-\hline
+一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い．
-Time Stamps & ファイル作成，編集日時 \\
+なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために，
-\hline
+B-Treeのようなノードを複数持つことができる構造が効果的だからである．
-Number of link & ハードリンクの数 \\
+その点ではRedBlackTreeはB-Treeに劣る．
-\hline
+しかしながら，SSDはランダムアクセスによってデータにアクセスするため，
-Location on hard disk & データのアドレス\\
+RedBlackTreeでなくB-Treeを用いる利点は少ないと考える．
-\hline
+よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる．
-\end{tabular}
+そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる．
-\caption{inodeでのファイル属性情報}
-\label{table:inode}
+\section{並行アップデート時の問題}
-\end{center}
-\end{table}
-当研究室ではxv6のCbCでの実装を行なっているが，今回はxv6のFileルーチンをCbCで書き換えるのではなく
-GearsOSへUnixのファイルシステムの仕組みを取り入れるアプローチをとる．
-まず，ファイルシステムを大まかにディレクトリシステムとファイルの二つに分けて考える．
-ディレクトリシステムはUnixのinodeの仕組みを取り入れる．
-今回作成した，GearsOSのディレクトリシステムであるGearsDirectoryについて説明する．
-ファイルについては後の章で述べる．
-FileSystemTreeはディレクトリ構造，inodeの仕組みを取り入れる際に用いるTreeである．
-ソースコード\ref{src:ftree}はFileSystemTreeのinterfaceである．
-GearsOSにおけるinterfaceはCodeGearと各CodeGearが用いるI/O DataGearの集合を記述する．
-よって，FileSystemTreeのinterfaceはfTreeとnodeのDataGearとput，get，remove，nextのCodeGearを持つ．
-FileSystemTreeのfTreeはGearsOSの永続データを構築する際に使用されるRedBlackTreeであり，put，get，removeはRedBlackTreeの操作を行うためのCodeGearである．
-また，nextは遷移先のCodeGearを参照するために用いる．
-\lstinputlisting[caption=FTreeのinterface,label=src:ftree]{src/FTree.h}
-ディレクトリ構造は2つのFileSystemTreeで実装する．
-1つ目はinode numberとfileのポインタのペアを持つ木である．
-それは，inode numberをkey，inodeをvalueとして持つためinode numberからinodeを検索するために用いる（以下，inode treeとする）．
-2つ目はfilenameとinode numberのペアを持つ木である．
-それは，filenameをkey, inode numberをvalueとして持つため，filenameからinode numberを検索するために用いる．
-また，inodeをfilenameで検索するためのindex treeであるといえる（以下，index treeとする）．
-図\ref{fig:inode}はindex treeを用いたinodeの検索の流れを表す．
-まずindex treeからkeyがfilenameのnodeをgetする．
-keyがfilenameのnodeのvalueよりinode numberがわかる．
-次に，取得したinode numberをkeyとしてinode treeを検索する．
-keyがinode numberのnodeはvalueとしてinodeを持っていて，inodeを参照することができる．
-\begin{figure}[ht]
-\begin{center}
-\includegraphics[width=80mm]{figs/inode.pdf}
-\end{center}
-\caption{index treeを用いたinodeの検索の流れ}
-\label{fig:inode}
-\end{figure}
-GearsOSにおける永続データは非破壊的な編集を行う木構造を用いて保存する．
-図\ref{fig:TreeEdit}は非破壊的編集を木構造に対し行う様子である．
-赤で示されたノード6をAに編集する場合，まずルートノードから編集ノードまでのパスを全てコピーする．
-コピーしたパス上に存在しないノードは，コピー元の木構造と共有する．
-それにより，編集後の木構造の赤のルートノードから探索を行う場合は編集されたAのノードが見え，
-黒のルートノードから探索を行う場合は編集前の6のノードを見ることができる．
-ディレクトリシステムを非破壊的な木構造の編集を用いて実装することにより，
-ディレクトリシステム自体にバックアップの機能を搭載することが可能であると考える．
-\begin{figure}[ht]
-\begin{center}
-\includegraphics[width=80mm]{figs/nonDestroyTreeEdit.pdf}
-\end{center}
-\caption{非破壊的なTree編集}
-\label{fig:TreeEdit}
-\end{figure}
-\section{GearsFileSystemにおけるインターフェース}
-ファイルやディレクトリの操作を行うインターフェースをUnix Likeに実装を行った．
-実装を行ったmkdir, ls, cdを説明する．
-\subsection{mkdir}
-Unixにおいてmkdirは新しくディレクトリを作成するコマンドである．
-GearsDirectoryのmkdirはindex treeとinode treeにnodeをputすることでディレクトリを作成する．
-ソースコード\ref{src:mkdir}はGearsDirectoryにおけるmkdirのCodeGearであり，図\ref{fig:mkdir}はその処理を図で表したものである．
-まず1行目の\emph{\_\_code mkdir}ではinode treeへinodeのputが行われ，\emph{\_\_code mkdir2}へ遷移する．
-inodeは4,5行目でkeyにinode number, valueにディレクトリのポインタがセットされる．
-次に，11行目の\emph{\_\_code mkdir2}ではindex treeへkeyがfilename，valueがinode numberのnodeのputが行われ，nextのCodeGearへ遷移する．
-このように，FileSystemTreeのputを2回行うため，mkdirは\emph{\_\_code mkdir}と\emph{\_\_code mkdir2}の2つのCodeGearで構成されている．
-また，InputDataGearの\emph{name}はfilenameを表す．
-\lstinputlisting[caption=mkdirのCodeGear,label=src:mkdir]{src/mkdir.cbc}
-\begin{figure}[ht]
-\begin{center}
-\includegraphics[width=80mm]{figs/mkdir.pdf}
-\end{center}
-\caption{mkdirの操作の流れ}
-\label{fig:mkdir}
-\end{figure}
-\subsection{ls}
-Unixにおいてlsはファイルやディレクトリの一覧，メタ情報を表示するコマンドである．
-GearsDirectoryのlsはindex treeに対し，getをすることでディレクトリのnameを取得する．
-これは，Unixのlsコマンドにおける\emph{\$ls filename}に等しい機能である．
-ソースコード\ref{src:ls}はGearsDirectoryにおけるlsのCodeGearであり，図\ref{fig:ls}はその処理を図で表したものである．
-まず1行目の\emph{\_\_code ls}ではindex treeに対しgetを行うため，
-3行目でgetしたいfilenameをkeyにセットし，index treeのgetへgotoしている．
-その後，9行目の\emph{\_\_code ls2}ではnode\verb|->|keyに格納されたgetの結果をprintfで出力する．
-本来lsコマンドは引数を渡さずに実行するとカレントディレクトリ下のディレクトリやファイルを一覧で表示するが，
-現時点では未実装である．
-なお，一覧表示の機能はfilenameのリストをディレクトリに持たせることで実装可能であると思われる．
-\lstinputlisting[caption=lsのCodeGear,label=src:ls]{src/ls.cbc}
-\begin{figure}[ht]
-\begin{center}
-\includegraphics[width=80mm]{figs/ls.pdf}
-\end{center}
-\caption{lsの操作の流れ}
-\label{fig:ls}
-\end{figure}
-\subsection{cd}
-Unixにおいてcdはディレクトリを移動するコマンドである．
-GearsDirectoryのcdはindex treeとinode treeに対しgetを行い，currentDirectoryを書き換えることで実装する．
-機能としてはディレクトリが持つ子ディレクトリへの移動ができる．
-ソースコード\ref{src:cd}はGearsDirectoryにおけるcdのCodeGearであり，図\ref{fig:cd}はその処理を図で表したものである．
-まず1行目の\emph{\_\_code cd2Child}でindex treeに対しgetを行うため，index treeのgetへgotoしている．
-次に，9行目の\emph{\_\_code cd2Child2}でinode treeに対しgetを行うため，inode treeのgetへgotoしている．
-この際，getは1行目のcd2Childでgetしたnodeのvalueをもとに行う．valueにはinode numberがセットされている．
-その後，15行目の\emph{\_\_code cd2Child3}でcurrent ディレクトリを保存しているgearsDirectory\verb|->|currentDirectoryを
-getしたnode\verb|->|valueに書き換える．
-\lstinputlisting[caption=cdのCodeGear,label=src:cd]{src/cd.cbc}
-\begin{figure}[ht]
-\begin{center}
-\includegraphics[width=80mm]{figs/cd.pdf}
-\end{center}
-\caption{cdの操作の流れ}
-\label{fig:cd}
-\end{figure}
-\section{GearsFileSystemにおけるファイルの構成}
-ファイルシステムはディレクトリの構成だけでなく，ファイルの構成についても考える必要がある．
-本研究と並行する形で一木貴裕による分散ファイルシステムの設計が行われており\cite{cfile}，
-ファイルの構成に関しても実装，検討されている．
-GearsOSにおけるファイル構成を説明する．
-ファイルのInput/Output Streamは競合的なアクセスに対応するため，3つのSynchronizedQueueを用いる．
-それぞれをInputQueue, OutputQueue, mainQueueと呼ぶ．
-データをinputしたい場合InputQueueへputを行い，取得したい場合OutputQueueからgetを行う．
-mainQueueはデータそのものであり，InputQueueからmainQueue，mainQueueからOutputQueueへデータが流れるように接続される．
-これらは，Gearの概念ではDataGearにあたり，DataGearManagerにkeyとI/O Queueが対応する形で保持される．
-ファイルの中身のデータをレコードに分割し，レコードをQueueにputしてstreamに入れる．
-データを取り出す際はQueueからgetし，順番に読むことでファイルを構築する．
-分散ファイルシステムはファイルのデータ送受信をする際に用いられるAPIを作成する必要がある．
-WordCount例題\cite{file}を通して，GearsFileのAPIの作成を行う．
-WordCount例題は指定したファイルの文字数や行数，ファイルの内の文字列を出力する．
-図\ref{fig:WCStates}はWordCount例題の処理の流れを示している．
-これは大きく分けて，指定したファイルをFile構造体としてopenするFileOpenスレッド，
-File構造体を受け取り文字数と行数をcountUpするWordCountスレッドの二つのCodeGearで記述することができる．
-また，ファイル内の文字列を行ごとにCountUpに送信し，EOFを受け取ったらループを抜けfinishに移行する．
-\begin{figure}[ht]
-\begin{center}
-\includegraphics[width=80mm]{figs/wordCountStates.pdf}
-\end{center}
-\caption{WordCount with CbC}
-\label{fig:WCStates}
-\end{figure}
-\section{GearsOSのメモリマネージメントシステムの考察}
-GearsOSのメモリマネージメントは，メモリ上のデータとディスク上のデータの構造が等しくなる形で実装をしたい．
-メモリ上とディスク上でデータの構造を等しくすることで，単純なコピーでメモリとディスク間のデータのやり取りを行うことができる．よって，比較的簡素に実装を行うことができると予想する．
-しかしながら，メモリ上とディスク上でオフセットの差が出る問題がある．
-これは，メタ計算でオフセットの差を吸収する処理を行うことで解決させる．
-また，メモリ上とディスク上のデータのアドレスが異なるため，ユーザーレベルからポインタを用いた場合，問題になる．
-しかしながら，GearsOSではユーザーレベルでポインタを用いることを禁止しているため，問題ないと考える．
-ガベージコレクションについては，Copying GCを用いる．
-Copying GCは単純に用いるとメモリ容量が倍必要になるという問題がある．
-そこで，リンクしているデータのみをコピーすることによってメモリ使用量を削減したい．
-データがリンクされているかどうかはLinkedListを参照し判断する．
-\section{今後の課題}
-\subsection{GearsShell}
-GearsOSに存在する未実装の機能の一つにshellが挙げられる．
-現状のGearsOSはユーザーの入力を受け付けることが出来ず，プログラミングインターフェースの様に機能している．
-GearsFileSystemなどGearsOSの各機能と接続し，今回作成したcdやlsの様なコマンドを受け付けるGearsShellを作成したい．
-\subsection{GearsDirectory filename}
-現状はGearsDirectoryのfilenameはIntegerの構造で管理されている．
-しかしながら，filenameは一般的に文字列型であるためIntegerから文字列型に変更する必要がある．
-\subsection{GearsDirectory path}
-GearsDirectoryにはpathの機能が実装されていない．
-よってfull path指定のlsなどが実装できない状態である．
-FileSystemTreeを拡張し，ノードをたどりpathを生成する様な機能を実装する必要がある．
-\subsection{ファイルのバックアップ}
-ディレクトリに関しては非破壊的なTree編集を用いることで，バックアップを行うことを考えたが
-ファイルに関してはレコードのDataをファイルの差分履歴として保持し，
-日時情報を付け加えることでVersion Control Systemのような機能を持たせることが可能であると考えられる．
-\subsection{GearsDirectory on disk}
-現状はGearsDirectoryのinodeはon memoryで実装されている．
-データの保存はdisk上に行うため，inodeをdisk上に構築し必要がある
-\section{まとめ}
-本研究では主としてGearsFileSystemの構築に必要なGearsDirectoryの実装について説明した．
-いくつか課題はあるが，RedBlackTreeのシンプルなインターフェースにより比較的容易に実装を行うことができた．
-また，RedBlackTreeを用いてinodeの仕組みを構築し，ls，cd，mkdirを作成するなどして，
-Unix Likeに構築することが出来た．
-メモリマネージメントについては，今後の研究で実装と考察を行い，
-Gears OSのメモリマネージメントシステムを構築していく．
-信頼性については，定理証明やモデル検査を用いて保証を行うが，
-非破壊的なTree編集によるディレクトリのバックアップやファイルのバックアップをファイルシステムに組み込むことでも
-信頼性の向上が期待できる．形式手法とファイルシステムの機能の両面で信頼性の向上が図れると考える．
 \nocite{*}
 \bibliographystyle{ipsjunsrt}
 \bibliography{matac-bib}

Mercurial > hg > Papers > 2023 > matac-sigos

comparison Paper/paper.tex @ 1:c4f210d08680