# HG changeset patch # User matac42 # Date 1681440201 -32400 # Node ID c4f210d08680498c66d0d7cf6d7b310c15d45d69 # Parent 466b958a341993aedc7d275f924ba427202cdb1b update diff -r 466b958a3419 -r c4f210d08680 Paper/paper.aux --- a/Paper/paper.aux Tue Apr 04 18:46:21 2023 +0900 +++ b/Paper/paper.aux Fri Apr 14 11:43:21 2023 +0900 @@ -13,51 +13,7 @@ \newlabel{fig:dgcg}{{1}{2}} \newlabel{src:cbc}{{1}{2}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {1}{\ignorespaces CbCのプログラム例}}{2}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {3}\hskip 1zw{GearsOS}}{2}{}\protected@file@percent } -\citation{xv6} -\citation{xv6component} -\citation{xv6kernel} -\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Contextを参照する流れ\relax }}{3}{}\protected@file@percent } -\newlabel{fig:context}{{2}{3}} -\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces CodeGearとMetaCodeGearの関係\relax }}{3}{}\protected@file@percent } -\newlabel{fig:meta-cgdg}{{3}{3}} -\@writefile{toc}{\contentsline {section}{\numberline {4}\hskip 1zw{Unixのファイルシステム}}{3}{}\protected@file@percent } -\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces inodeでのファイル属性情報\relax }}{3}{}\protected@file@percent } -\newlabel{table:inode}{{1}{3}} -\newlabel{src:ftree}{{2}{3}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {2}{\ignorespaces FTreeのinterface}}{3}{}\protected@file@percent } -\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces index treeを用いたinodeの検索の流れ\relax }}{4}{}\protected@file@percent } -\newlabel{fig:inode}{{4}{4}} -\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces 非破壊的なTree編集\relax }}{4}{}\protected@file@percent } -\newlabel{fig:TreeEdit}{{5}{4}} -\@writefile{toc}{\contentsline {section}{\numberline {5}\hskip 1zw{GearsFileSystemにおけるインターフェース}}{4}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {5.1}{mkdir}}{4}{}\protected@file@percent } -\newlabel{src:mkdir}{{3}{4}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {3}{\ignorespaces mkdirのCodeGear}}{4}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {5.2}{ls}}{4}{}\protected@file@percent } -\citation{cfile} -\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces mkdirの操作の流れ\relax }}{5}{}\protected@file@percent } -\newlabel{fig:mkdir}{{6}{5}} -\newlabel{src:ls}{{4}{5}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4}{\ignorespaces lsのCodeGear}}{5}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {5.3}{cd}}{5}{}\protected@file@percent } -\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces lsの操作の流れ\relax }}{5}{}\protected@file@percent } -\newlabel{fig:ls}{{7}{5}} -\newlabel{src:cd}{{5}{5}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {5}{\ignorespaces cdのCodeGear}}{5}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {6}\hskip 1zw{GearsFileSystemにおけるファイルの構成}}{5}{}\protected@file@percent } -\citation{file} -\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces cdの操作の流れ\relax }}{6}{}\protected@file@percent } -\newlabel{fig:cd}{{8}{6}} -\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces WordCount with CbC\relax }}{6}{}\protected@file@percent } -\newlabel{fig:WCStates}{{9}{6}} -\@writefile{toc}{\contentsline {section}{\numberline {7}\hskip 1zw{GearsOSのメモリマネージメントシステムの考察}}{6}{}\protected@file@percent } -\@writefile{toc}{\contentsline {section}{\numberline {8}\hskip 1zw{今後の課題}}{6}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {8.1}{GearsShell}}{6}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {8.2}{GearsDirectory filename}}{6}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {8.3}{GearsDirectory path}}{6}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {8.4}{ファイルのバックアップ}}{6}{}\protected@file@percent } -\@writefile{toc}{\contentsline {subsection}{\numberline {8.5}{GearsDirectory on disk}}{6}{}\protected@file@percent } +\@writefile{toc}{\contentsline {section}{\numberline {3}\hskip 1zw{信頼性の保証を目的としたGearsOS}}{2}{}\protected@file@percent } \citation{*} \bibstyle{ipsjunsrt} \bibdata{matac-bib} @@ -67,12 +23,18 @@ \bibcite{gears}{4} \bibcite{gearsos}{5} \bibcite{cr}{6} -\bibcite{xv6}{7} -\bibcite{xv6component}{8} +\bibcite{file}{7} +\bibcite{cfile}{8} \bibcite{xv6kernel}{9} -\bibcite{cfile}{10} -\bibcite{file}{11} +\bibcite{xv6component}{10} +\bibcite{xv6}{11} \bibcite{christie}{12} -\@writefile{toc}{\contentsline {section}{\numberline {9}\hskip 1zw{まとめ}}{7}{}\protected@file@percent } -\newlabel{ipsj@lastpage}{{}{7}} -\gdef \@abspage@last{7} +\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Contextを参照する流れ\relax }}{3}{}\protected@file@percent } +\newlabel{fig:context}{{2}{3}} +\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces CodeGearとMetaCodeGearの関係\relax }}{3}{}\protected@file@percent } +\newlabel{fig:meta-cgdg}{{3}{3}} +\@writefile{toc}{\contentsline {section}{\numberline {4}\hskip 1zw{RedBlackTreeよるファイルシステムの構成}}{3}{}\protected@file@percent } +\@writefile{toc}{\contentsline {section}{\numberline {5}\hskip 1zw{ディスク上とメモリ上のデータ構造}}{3}{}\protected@file@percent } +\@writefile{toc}{\contentsline {section}{\numberline {6}\hskip 1zw{並行アップデート時の問題}}{3}{}\protected@file@percent } +\newlabel{ipsj@lastpage}{{}{4}} +\gdef \@abspage@last{4} diff -r 466b958a3419 -r c4f210d08680 Paper/paper.bbl --- a/Paper/paper.bbl Tue Apr 04 18:46:21 2023 +0900 +++ b/Paper/paper.bbl Fri Apr 14 11:43:21 2023 +0900 @@ -20,13 +20,12 @@ \bibitem{cr} 伊波立樹\：GearsOSの並列処理，修士 (工学) 学位論文 (2018). -\bibitem{xv6} -{Russ Cox, Frans Kaashoek, Robert Morris}: xv6 a simple, Unix-like teaching - operating system, https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf. +\bibitem{file} +河野~真治(琉球大学)一木~貴裕\：GearsOSの分散ファイルシステムの設計，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) + (2021). -\bibitem{xv6component} -清水隆博，河野真治(琉球大学)\：xv6の構成要素の継続の分析，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) - (2020). +\bibitem{cfile} +一木貴裕\：GearsOSの分散ファイルシステム設計，修士 (工学) 学位論文 (2022). \bibitem{xv6kernel} 河野 真治~(琉球大学工学部情報工学科)坂本 昂弘~(琉球大学工学部情報工学科)\：継続を用いた xv6 @@ -34,12 +33,13 @@ の書き換え，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) (2019). -\bibitem{cfile} -一木貴裕\：GearsOSの分散ファイルシステム設計，修士 (工学) 学位論文 (2022). +\bibitem{xv6component} +清水隆博，河野真治(琉球大学)\：xv6の構成要素の継続の分析，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) + (2020). -\bibitem{file} -河野~真治(琉球大学)一木~貴裕\：GearsOSの分散ファイルシステムの設計，情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) - (2021). +\bibitem{xv6} +{Russ Cox, Frans Kaashoek, Robert Morris}: xv6 a simple, Unix-like teaching + operating system, https://pdos.csail.mit.edu/6.828/2018/xv6/book-rev11.pdf. \bibitem{christie} {河野 真治}\：分散フレームワーク Christie と分散木構造データベースJungle diff -r 466b958a3419 -r c4f210d08680 Paper/paper.blg --- a/Paper/paper.blg Tue Apr 04 18:46:21 2023 +0900 +++ b/Paper/paper.blg Fri Apr 14 11:43:21 2023 +0900 @@ -11,14 +11,14 @@ Warning--Missing required argument pages in gears Warning--there's no number and/or volumecr Warning--Missing required argument pages in cr -Warning--there's no number and/or volumexv6component -Warning--Missing required argument pages in xv6component +Warning--there's no number and/or volumefile +Warning--Missing required argument pages in file +Warning--there's no number and/or volumecfile +Warning--Missing required argument pages in cfile Warning--there's no number and/or volumexv6kernel Warning--Missing required argument pages in xv6kernel -Warning--there's no number and/or volumecfile -Warning--Missing required argument pages in cfile -Warning--there's no number and/or volumefile -Warning--Missing required argument pages in file +Warning--there's no number and/or volumexv6component +Warning--Missing required argument pages in xv6component You've used 12 entries, 2334 wiz_defined-function locations, 610 strings with 5492 characters, diff -r 466b958a3419 -r c4f210d08680 Paper/paper.log --- a/Paper/paper.log Tue Apr 04 18:46:21 2023 +0900 +++ b/Paper/paper.log Fri Apr 14 11:43:21 2023 +0900 @@ -1,4 +1,4 @@ -This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 4 APR 2023 18:36 +This is e-pTeX, Version 3.141592653-p4.0.0-220214-2.6 (utf8.euc) (TeX Live 2022) (preloaded format=platex 2022.6.9) 14 APR 2023 11:39 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -3197,63 +3197,13 @@ File: figs/meta-cg-dg.pdf Graphic file (type pdf) - [2] -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 226. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 229. -LaTeX Font Info: Calculating math sizes for size <8.8711> on input line 234. - (./src/FTree.h) [3] -File: figs/inode.pdf Graphic file (type pdf) - -File: figs/nonDestroyTreeEdit.pdf Graphic file (type pdf) - - -Underfull \hbox (badness 4927) in paragraph at lines 311--311 -[]\OT1/cmr/bx/n/11.82813 GearsFileSystem \JY1/gt/m/n/11.82813 におけるインタ ー - [] - + [2] (./paper.bbl LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <9.61035> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 316. +(Font) Font shape `JT1/gt/m/n' tried instead on input line 1. LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <9.61035> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 316. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 320. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 320. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 322. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 323. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 323. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 324. -(./src/mkdir.cbc) -File: figs/mkdir.pdf Graphic file (type pdf) - -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 337. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 339. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 341. - [4] (./src/ls.cbc) -File: figs/ls.pdf Graphic file (type pdf) - -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 359. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 360. -LaTeX Font Info: Kanji font shape `JY1/gt/m/it' undefined -(Font) No change on input line 362. - (./src/cd.cbc) -File: figs/cd.pdf Graphic file (type pdf) - - [5] -File: figs/wordCountStates.pdf Graphic file (type pdf) - - [6] (./paper.bbl +(Font) Font shape `JY1/gt/m/n' tried instead on input line 1. +LaTeX Font Info: Calculating math sizes for size <8.8711> on input line 1. + Underfull \hbox (badness 10000) in paragraph at lines 9--10 []\JY1/mc/m/n/8.8711 並列信頼研究室 []\OT1/cmr/m/n/8.8711 CbC, http://www.cr.ie.u- [] @@ -3264,16 +3214,16 @@ [] -Underfull \hbox (badness 10000) in paragraph at lines 24--26 +Underfull \hbox (badness 10000) in paragraph at lines 41--43 \OT1/cmr/m/n/8.8711 a sim-ple, Unix-like teach-ing op-er-at-ing sys-tem, [] -Underfull \hbox (badness 10000) in paragraph at lines 24--26 +Underfull \hbox (badness 10000) in paragraph at lines 41--43 \OT1/cmr/m/n/8.8711 https://pdos.csail.mit.edu/6.828/2018/xv6/book- [] -) [7 +[3]) [4 ] (./paper.aux) @@ -3281,12 +3231,12 @@ ) Here is how much of TeX's memory you used: - 5227 strings out of 478724 - 82982 string characters out of 5858393 - 769481 words of memory out of 5000000 - 23613 multiletter control sequences out of 15000+600000 - 499512 words of font info for 161 fonts, out of 8000000 for 9000 + 5090 strings out of 478724 + 81062 string characters out of 5858393 + 628481 words of memory out of 5000000 + 23493 multiletter control sequences out of 15000+600000 + 499135 words of font info for 160 fonts, out of 8000000 for 9000 929 hyphenation exceptions out of 8191 - 55i,11n,63p,294b,1696s stack positions out of 10000i,1000n,20000p,200000b,200000s - -Output written on paper.dvi (7 pages, 61032 bytes). + 55i,10n,63p,294b,1696s stack positions out of 10000i,1000n,20000p,200000b,200000s + +Output written on paper.dvi (4 pages, 28236 bytes). diff -r 466b958a3419 -r c4f210d08680 Paper/paper.pdf Binary file Paper/paper.pdf has changed diff -r 466b958a3419 -r c4f210d08680 Paper/paper.synctex.gz Binary file Paper/paper.synctex.gz has changed diff -r 466b958a3419 -r c4f210d08680 Paper/paper.tex --- a/Paper/paper.tex Tue Apr 04 18:46:21 2023 +0900 +++ b/Paper/paper.tex Fri Apr 14 11:43:21 2023 +0900 @@ -165,7 +165,7 @@ \lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc} -\section{GearsOS} +\section{信頼性の保証を目的としたGearsOS} GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである． GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ． @@ -214,244 +214,44 @@ \label{fig:meta-cgdg} \end{figure} -\section{Unixのファイルシステム} - -UnixのファイルシステムはBTreeとinodeで構成されており，xv6もその仕組みを用いている． -xv6\cite{xv6}はMITで教育用の目的で開発されたOSで，Unixの基本的な構造を持つ． -当研究室ではxv6のCbCでの書き換え，分析を行なっている\cite{xv6component,xv6kernel}． - -inodeは主にUnix系のファイルシステムで用いられる，ファイルの属性情報が書かれたデータである． -inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある． -また，inodeは識別番号としてinode numberを持つ． -inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である． -inodeはファイルシステム始動時にinode領域をディスク上に確保する． -そのため，inode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる． -inode numberの最大値は\emph{df -i}コマンドで確認可能である． - -\begin{table}[tb] - \begin{center} - \small - \begin{tabular}[htpb]{|c||l|} - \hline - File Types & ファイルの種類 \\ - \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} - -当研究室ではxv6のCbCでの実装を行なっているが，今回はxv6のFileルーチンをCbCで書き換えるのではなく -GearsOSへUnixのファイルシステムの仕組みを取り入れるアプローチをとる． -まず，ファイルシステムを大まかにディレクトリシステムとファイルの二つに分けて考える． -ディレクトリシステムはUnixのinodeの仕組みを取り入れる． -今回作成した，GearsOSのディレクトリシステムであるGearsDirectoryについて説明する． -ファイルについては後の章で述べる． +\section{RedBlackTreeよるファイルシステムの構成} -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を説明する． +ファイルシステムは全てRedBlackTreeで構成する． +それにより，プログラムの証明がより簡単になるからである． +また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである． +よって，それらをまとめてRedBlackTreeで構成する． -\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} +ファイルシステムとDBの違いとして，スキーマが挙げられる． +DBは事前にスキーマを定義し，それに沿ってデータを挿入したり参照したりする． +対して，ファイルシステムにはスキーマに当たるものがなく， +データはファイルパスによって管理される． +スキーマを定義することによってデータを構造化されるため非構造化データと比較すると +インデックスを作成することが容易でデータの検索性が向上する利点がある． +しかしながら，スキーマはDBの運用中に変更されることがあり， +スキーマを変更した以前へロールバックができない問題がある． -\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におけるファイル構成を説明する． +ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると， +スキーマを定義する必要のないスキーマレスなDBが必要になる． +ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ +DBがスキーマによって実現していた機能を付け加えることを試みる． -ファイルの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を参照し判断する． +RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある． +今回用いるのは，非破壊的な実装のRedBlackTreeである． -\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を生成する様な機能を実装する必要がある． +\section{ディスク上とメモリ上のデータ構造} -\subsection{ファイルのバックアップ} -ディレクトリに関しては非破壊的なTree編集を用いることで，バックアップを行うことを考えたが -ファイルに関してはレコードのDataをファイルの差分履歴として保持し， -日時情報を付け加えることでVersion Control Systemのような機能を持たせることが可能であると考えられる． - -\subsection{GearsDirectory on disk} -現状はGearsDirectoryのinodeはon memoryで実装されている． -データの保存はdisk上に行うため，inodeをdisk上に構築し必要がある - -\section{まとめ} +ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する． +一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い． +なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために， +B-Treeのようなノードを複数持つことができる構造が効果的だからである． +その点ではRedBlackTreeはB-Treeに劣る． +しかしながら，SSDはランダムアクセスによってデータにアクセスするため， +RedBlackTreeでなくB-Treeを用いる利点は少ないと考える． +よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる． +そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる． -本研究では主としてGearsFileSystemの構築に必要なGearsDirectoryの実装について説明した． -いくつか課題はあるが，RedBlackTreeのシンプルなインターフェースにより比較的容易に実装を行うことができた． -また，RedBlackTreeを用いてinodeの仕組みを構築し，ls，cd，mkdirを作成するなどして， -Unix Likeに構築することが出来た． -メモリマネージメントについては，今後の研究で実装と考察を行い， -Gears OSのメモリマネージメントシステムを構築していく． - -信頼性については，定理証明やモデル検査を用いて保証を行うが， -非破壊的なTree編集によるディレクトリのバックアップやファイルのバックアップをファイルシステムに組み込むことでも -信頼性の向上が期待できる．形式手法とファイルシステムの機能の両面で信頼性の向上が図れると考える． +\section{並行アップデート時の問題} \nocite{*} \bibliographystyle{ipsjunsrt}