|
0
|
1 %%
|
|
|
2 %% 研究報告用スイッチ
|
|
|
3 %% [techrep]
|
|
|
4 %%
|
|
|
5 %% 欧文表記無しのスイッチ(etitle,eabstractは任意)
|
|
|
6 %% [noauthor]
|
|
|
7 %%
|
|
|
8
|
|
|
9 %\documentclass[submit,techrep]{ipsj}
|
|
|
10 \documentclass[submit,techrep,noauthor]{ipsj}
|
|
|
11
|
|
|
12
|
|
|
13
|
|
|
14 \usepackage[dvips, dvipdfmx]{graphicx}
|
|
|
15 \usepackage{latexsym}
|
|
|
16 \usepackage{listings}
|
|
|
17 \lstset{
|
|
|
18 language=C,
|
|
|
19 tabsize=2,
|
|
|
20 frame=single,
|
|
|
21 basicstyle={\tt\footnotesize}, %
|
|
|
22 identifierstyle={\footnotesize}, %
|
|
|
23 commentstyle={\footnotesize\itshape}, %
|
|
|
24 keywordstyle={\footnotesize\ttfamily}, %
|
|
|
25 ndkeywordstyle={\footnotesize\ttfamily}, %
|
|
|
26 stringstyle={\footnotesize\ttfamily},
|
|
|
27 breaklines=true,
|
|
|
28 captionpos=t,
|
|
|
29 columns=[l]{fullflexible}, %
|
|
|
30 xrightmargin=0zw, %
|
|
|
31 xleftmargin=1zw, %
|
|
|
32 aboveskip=1zw,
|
|
|
33 numberstyle={\scriptsize}, %
|
|
|
34 stepnumber=1,
|
|
|
35 numbersep=0.5zw, %
|
|
|
36 lineskip=-0.5ex
|
|
|
37 }
|
|
|
38 \usepackage{caption}
|
|
|
39
|
|
|
40
|
|
|
41 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
|
|
|
42 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
|
|
|
43 \def\|{\verb|}
|
|
|
44 %
|
|
|
45
|
|
|
46 %\setcounter{巻数}{59}%vol59=2018
|
|
|
47 %\setcounter{号数}{10}
|
|
|
48 %\setcounter{page}{1}
|
|
|
49 \renewcommand{\lstlistingname}{Code}
|
|
|
50
|
|
|
51 \begin{document}
|
|
|
52
|
|
|
53
|
|
|
54 \title{Gears OSのファイルシステムとDB}
|
|
|
55
|
|
|
56 \affiliate{IPSJ}{情報処理学会\\
|
|
|
57 IPSJ, Chiyoda, Tokyo 101--0062, Japan}
|
|
|
58
|
|
|
59
|
|
|
60 \paffiliate{JU}{琉球大学大学院理工学研究科工学専攻知能情報プログラム\\
|
|
|
61 University of the Ryukyus, Graduate School of Engineering and Science}
|
|
|
62
|
|
|
63 \author{又吉 雄斗}{Matayoshi Yuto}{KIE}[matac@cr.ie.u-ryukyu.ac.jp]
|
|
|
64 \author{佐野 巧曜}{Sano Yoshiaki}{KIE}[yoshisaur@cr.ie.u-ryukyu.ac.jp]
|
|
|
65 \author{河野 真治}{Kono Shinzi}{IE}[kono@ie.u-ryukyu.ac.jp]
|
|
|
66
|
|
|
67 \begin{abstract}
|
|
|
68 当研究室では，Continuation based C（CbC）を用い，定理証明やモデル検査などで信頼性を保証することを目的としたGearsOSを開発している．
|
|
|
69 OSにおいてファイルシステムは重要な機能の一つであるため実装する必要がある．
|
|
|
70 現在，一般的なアプリケーションはファイルシステムとデータベースを併用する形で構成される．
|
|
|
71 DBはSQLによってデータの挿入や変更が可能だがスキーマを事前に定義したり，insert時にそれらのschemaを指定したりする必要がある．
|
|
|
72 GearsOSのファイルシステムではSQLの機能に相当するgrepやfindなどのインターフェースを実装し，
|
|
|
73 アプリケーションのデータベースとしてファイルシステムを使用する構成が取れるようにしたい．
|
|
|
74 ファイルシステムとデータベースの違いについて考え，データベースとしても利用可能なファイルシステムを構築したい．
|
|
|
75 本研究では，ファイルシステムとデータベースの違いについて考察し，Gears OSのファイルシステムの設計について述べる．
|
|
|
76 \end{abstract}
|
|
|
77
|
|
|
78
|
|
|
79 %
|
|
|
80 %\begin{jkeyword}
|
|
|
81 %情報処理学会論文誌ジャーナル，\LaTeX，スタイルファイル，べからず集
|
|
|
82 %\end{jkeyword}
|
|
|
83 %
|
|
|
84 %\begin{eabstract}
|
|
|
85 %This document is a guide to prepare a draft for submitting to IPSJ
|
|
|
86 %Journal, and the final camera-ready manuscript of a paper to appear in
|
|
|
87 %IPSJ Journal, using {\LaTeX} and special style files. Since this
|
|
|
88 %document itself is produced with the style files, it will help you to
|
|
|
89 %refer its source file which is distributed with the style files.
|
|
|
90 %\end{eabstract}
|
|
|
91 %
|
|
|
92 %\begin{ekeyword}
|
|
|
93 %IPSJ Journal, \LaTeX, style files, ``Dos and Dont's'' list
|
|
|
94 %\end{ekeyword}
|
|
|
95
|
|
|
96 \maketitle
|
|
|
97
|
|
|
98 %1
|
|
|
99 \section{GearsOSにおけるファイルシステム}
|
|
|
100
|
|
|
101 アプリケーションの信頼性を保証することは
|
|
|
102 情報システムやコンピュータを用いる業務の信頼性の保障につながる重要な課題である．
|
|
|
103 したがって，アプリケーションの信頼性を保証するために，基盤となるOSの信頼性を高める必要がある．
|
|
|
104
|
|
|
105 当研究室では，信頼性の保証を目的としたGearsOSを開発している．
|
|
|
106 GearsOSは，OSの信頼性を定理証明やモデル検査を行うことで保証することを目指している\cite{modelcheck}．
|
|
|
107 同じく，当研究室で開発しているプログラム言語であるCbC（Continuation based C）で記述されており，
|
|
|
108 ノーマルレベルとメタレベルを簡単に切り分けることを可能としている．
|
|
|
109 そのようにして，CbCでメタレベルの処理を切り出したものに対して，定理証明やモデル検査を行うことで信頼性を保証する．
|
|
|
110
|
|
|
111 GearsOSは現在OSとして重要な機能がいくつか未実装であり，その一つとしてファイルシステムが挙げられる．
|
|
|
112 ファイルシステムはファイルやディレクトリといった構造を持ち，データの保存，整理を行う．
|
|
|
113 また，OSが管理するデータの操作を人間が行いやすいようにインターフェースを提供する．
|
|
|
114 OSの機能の中でも特に重要な機能であるため，GearsOSにも実装を行う必要がある．
|
|
|
115
|
|
|
116 今回GearsOSへファイルシステムを実装するにあたり，Unixのファイルシステムを参考にした．
|
|
|
117 Unixのファイルシステムではファイルのメタデータをinodeの形式で保持している．
|
|
|
118 同様に，inodeの仕組みを用いてGearsOSのファイルシステムを実装したい．
|
|
|
119 また，インターフェースについても，cd，ls，mkdirというようにUnix likeに実装したい．
|
|
|
120 当研究室ではxv6のCbCでの書き換えを行なっているが，今回はxv6のルーチンをCbCで書き換えるのではなく
|
|
|
121 GearsOSへUnixのファイルシステムの仕組みを取り入れるアプローチをとりたい．
|
|
|
122 それはGearsOSとCbCで書き換えたxv6の比較や，互いにファイルシステムの機能の移植が行える様にするためである．
|
|
|
123
|
|
|
124 GearsOSのファイルシステムを構築するにあたり，メモリマネージメントについて考察する．
|
|
|
125 現在，GearsOSにはメモリマネージメントのシステムが存在しない．
|
|
|
126 しかしながら，ファイルシステムを構築するにあたりメモリマネージメントが必要不可欠である．
|
|
|
127 メモリ上のRedBlackTreeで構築されたデータ構造をそのままディスクにコピーする形で実装することを目指したい．
|
|
|
128
|
|
|
129 \section{Continuation based C}
|
|
|
130
|
|
|
131 Continuation based C（CbC）\cite{cbcllvm,cbc}は，当研究室で開発しているCの下位言語である．
|
|
|
132 CbCでは関数の代わりにCodeGearという単位でプログラミングを行う．
|
|
|
133 CodeGearは\emph{\_\_code}という記述で宣言することができる．
|
|
|
134 また，データの単位にはDataGearと呼ばれる変数データを用いる．
|
|
|
135 図\ref{fig:dgcg}はCodeGearと入出力の関係を表している．
|
|
|
136 CodeGearはDataGearを入力として受け取り，別のDataGearに書き込み出力することができる．
|
|
|
137 特に，入力のDataGearをInput DataGear，出力のDataGearをOutput DataGearと呼ぶ．
|
|
|
138 gotoで次のCodeGearに遷移することができ，その際，Output DataGearを次のCodeGearのInput DataGearとして渡すことができる．
|
|
|
139
|
|
|
140 \begin{figure}[ht]
|
|
|
141 \begin{center}
|
|
|
142 \includegraphics[width=80mm]{figs/cgdg.pdf}
|
|
|
143 \end{center}
|
|
|
144 \caption{CodeGearと入出力の関係図}
|
|
|
145 \label{fig:dgcg}
|
|
|
146 \end{figure}
|
|
|
147
|
|
|
148 CodeGearから次のCodeGearに遷移していく一連の動作を継続と呼ぶ．
|
|
|
149 通常の関数の場合，関数から次の関数へ遷移する時にfunction callが行われる．
|
|
|
150 function callは前の関数へ戻る場合があり，そのためにcall stackを保存する．
|
|
|
151 他方，CbCの継続はfunction callをせずにgotoによるjmpで行われる．
|
|
|
152 jmpはfunction callと異なり，call stackのような環境を保存しない．
|
|
|
153 よって，CbCのgotoによる継続はfunction callによる継続と比較して軽量であるといえる．
|
|
|
154 そのことから，CbCにおける継続をfunction callによる継続と区別して，軽量継続と呼ぶ．
|
|
|
155 これらの仕組みにより，ノーマルレベルとメタレベルの処理を容易に切り分けることが可能となる．
|
|
|
156
|
|
|
157 CbCのプログラム例をソースコード\ref{src:cbc}に示す．
|
|
|
158 まずmain関数においてadd1 CodeGearへgotoを行う．
|
|
|
159 その際add1へInput DataGearとしてnを渡す．
|
|
|
160 Cのgotoが\emph{goto label;}という記法で，ラベリングした箇所へjmpを行うのに対し，
|
|
|
161 CbCのgotoは\emph{goto add1(n);}という記法で，add1 CodeGearへn DataGearを渡してjmpを行う．
|
|
|
162 add1は処理の最後にadd2 CodeGearへgotoを行う．
|
|
|
163 その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
|
|
|
164 このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進める．
|
|
|
165
|
|
|
166 \lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}
|
|
|
167
|
|
|
168 \section{GearsOS}
|
|
|
169
|
|
|
170 GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである．
|
|
|
171 GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ．
|
|
|
172 軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する．
|
|
|
173 同様にGearの概念を持つContinuation based C（CbC）で記述されており，ノーマルレベルとメタレベルの処理を切り分けることが容易である．
|
|
|
174 また，GearsOSは現在開発途上であり，OSとして動作するために今後実装しなければならない機能がいくつか残っている．
|
|
|
175
|
|
|
176 ContextはGearsOS上全てのCodeGear，DataGearの参照を持ち，CodeGearとDataGearの接続に用いられる．
|
|
|
177 OS上の処理の実行単位で，従来のOSにおけるプロセスに相当する機能であるといえる．
|
|
|
178 また，CodeGearをDataGearの一種であると考えると，ContextはGearの概念ではMetaDataGearに当たる．
|
|
|
179 Contextはノーマルレベルから直接参照されず，必ずMetaDataGearとしてMetaCodeGearから参照される．
|
|
|
180 それは，ノーマルレベルのCodeGearがContextを直接参照してしまうと，
|
|
|
181 メタレベルを切り分けた意味がなくなってしまうためである．
|
|
|
182
|
|
|
183 図\ref{fig:context}はContextを参照する流れを表したものである．
|
|
|
184 まずCodeGearがOutputDataGearへデータをoutputする．
|
|
|
185 stubCodeGearはInputDataGear（前のCodeGearのOutputDataGear）とOutputDataGearをContextから参照し，次のCodeGearへgotoを行う．
|
|
|
186 CodeGearでの処理後，OutputDataGearへデータをoutputする．
|
|
|
187
|
|
|
188 Contextはいくつかの種類に分けることができる．
|
|
|
189 OS全体のContextを管理するKernel Contextやユーザープログラムごとに存在するUser Context，
|
|
|
190 CPUやGPUごとに存在するCPU Contextがある．
|
|
|
191 \begin{figure}[ht]
|
|
|
192 \begin{center}
|
|
|
193 \includegraphics[width=80mm]{figs/context.pdf}
|
|
|
194 \end{center}
|
|
|
195 \caption{Contextを参照する流れ}
|
|
|
196 \label{fig:context}
|
|
|
197 \end{figure}
|
|
|
198
|
|
|
199 図\ref{fig:meta-cgdg}はCodeGearの遷移とMetaCodeGearの関係を表している．
|
|
|
200 OSのプログラムはユーザーが実際に行いたい処理を表現するノーマルレベルと，
|
|
|
201 カーネルが行う処理を表現するメタレベルが存在する．
|
|
|
202 ノーマルレベルで見るとCodeGearがDataGearを受け取り，
|
|
|
203 処理後にDataGearを次のCodeGearに渡すという動作をしているように見える．
|
|
|
204 しかしながら，実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，
|
|
|
205 それらの計算はMetaCodeGearで行われる．
|
|
|
206 その際，MetaCodeGearに渡されるDataGearのことは特にMetaDataGearと呼ばれる．
|
|
|
207 また，CodeGearの前に実行されるMetaCodeGearは特にstubCodeGearと呼ばれ，
|
|
|
208 メタレベルを含めるとstubCodeGearとCodeGearを交互に実行する形で遷移していく．
|
|
|
209 \begin{figure}[ht]
|
|
|
210 \begin{center}
|
|
|
211 \includegraphics[width=80mm]{figs/meta-cg-dg.pdf}
|
|
|
212 \end{center}
|
|
|
213 \caption{CodeGearとMetaCodeGearの関係}
|
|
|
214 \label{fig:meta-cgdg}
|
|
|
215 \end{figure}
|
|
|
216
|
|
|
217 \section{Unixのファイルシステム}
|
|
|
218
|
|
|
219 UnixのファイルシステムはBTreeとinodeで構成されており，xv6もその仕組みを用いている．
|
|
|
220 xv6\cite{xv6}はMITで教育用の目的で開発されたOSで，Unixの基本的な構造を持つ．
|
|
|
221 当研究室ではxv6のCbCでの書き換え，分析を行なっている\cite{xv6component,xv6kernel}．
|
|
|
222
|
|
|
223 inodeは主にUnix系のファイルシステムで用いられる，ファイルの属性情報が書かれたデータである．
|
|
|
224 inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある．
|
|
|
225 また，inodeは識別番号としてinode numberを持つ．
|
|
|
226 inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である．
|
|
|
227 inodeはファイルシステム始動時にinode領域をディスク上に確保する．
|
|
|
228 そのため，inode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる．
|
|
|
229 inode numberの最大値は\emph{df -i}コマンドで確認可能である．
|
|
|
230
|
|
|
231 \begin{table}[tb]
|
|
|
232 \begin{center}
|
|
|
233 \small
|
|
|
234 \begin{tabular}[htpb]{|c||l|}
|
|
|
235 \hline
|
|
|
236 File Types & ファイルの種類 \\
|
|
|
237 \hline
|
|
|
238 Permissions & read write executeの実行可否\\
|
|
|
239 \hline
|
|
|
240 UID & ファイル所有者のID \\
|
|
|
241 \hline
|
|
|
242 GID & ファイル所有グループのID \\
|
|
|
243 \hline
|
|
|
244 File Size & ファイルのサイズ \\
|
|
|
245 \hline
|
|
|
246 Time Stamps & ファイル作成，編集日時 \\
|
|
|
247 \hline
|
|
|
248 Number of link & ハードリンクの数 \\
|
|
|
249 \hline
|
|
|
250 Location on hard disk & データのアドレス\\
|
|
|
251 \hline
|
|
|
252 \end{tabular}
|
|
|
253 \caption{inodeでのファイル属性情報}
|
|
|
254 \label{table:inode}
|
|
|
255 \end{center}
|
|
|
256 \end{table}
|
|
|
257
|
|
|
258 当研究室ではxv6のCbCでの実装を行なっているが，今回はxv6のFileルーチンをCbCで書き換えるのではなく
|
|
|
259 GearsOSへUnixのファイルシステムの仕組みを取り入れるアプローチをとる．
|
|
|
260 まず，ファイルシステムを大まかにディレクトリシステムとファイルの二つに分けて考える．
|
|
|
261 ディレクトリシステムはUnixのinodeの仕組みを取り入れる．
|
|
|
262 今回作成した，GearsOSのディレクトリシステムであるGearsDirectoryについて説明する．
|
|
|
263 ファイルについては後の章で述べる．
|
|
|
264
|
|
|
265 FileSystemTreeはディレクトリ構造，inodeの仕組みを取り入れる際に用いるTreeである．
|
|
|
266 ソースコード\ref{src:ftree}はFileSystemTreeのinterfaceである．
|
|
|
267 GearsOSにおけるinterfaceはCodeGearと各CodeGearが用いるI/O DataGearの集合を記述する．
|
|
|
268 よって，FileSystemTreeのinterfaceはfTreeとnodeのDataGearとput，get，remove，nextのCodeGearを持つ．
|
|
|
269 FileSystemTreeのfTreeはGearsOSの永続データを構築する際に使用されるRedBlackTreeであり，put，get，removeはRedBlackTreeの操作を行うためのCodeGearである．
|
|
|
270 また，nextは遷移先のCodeGearを参照するために用いる．
|
|
|
271 \lstinputlisting[caption=FTreeのinterface,label=src:ftree]{src/FTree.h}
|
|
|
272
|
|
|
273 ディレクトリ構造は2つのFileSystemTreeで実装する．
|
|
|
274 1つ目はinode numberとfileのポインタのペアを持つ木である．
|
|
|
275 それは，inode numberをkey，inodeをvalueとして持つためinode numberからinodeを検索するために用いる（以下，inode treeとする）．
|
|
|
276 2つ目はfilenameとinode numberのペアを持つ木である．
|
|
|
277 それは，filenameをkey, inode numberをvalueとして持つため，filenameからinode numberを検索するために用いる．
|
|
|
278 また，inodeをfilenameで検索するためのindex treeであるといえる（以下，index treeとする）．
|
|
|
279
|
|
|
280 図\ref{fig:inode}はindex treeを用いたinodeの検索の流れを表す．
|
|
|
281 まずindex treeからkeyがfilenameのnodeをgetする．
|
|
|
282 keyがfilenameのnodeのvalueよりinode numberがわかる．
|
|
|
283 次に，取得したinode numberをkeyとしてinode treeを検索する．
|
|
|
284 keyがinode numberのnodeはvalueとしてinodeを持っていて，inodeを参照することができる．
|
|
|
285
|
|
|
286 \begin{figure}[ht]
|
|
|
287 \begin{center}
|
|
|
288 \includegraphics[width=80mm]{figs/inode.pdf}
|
|
|
289 \end{center}
|
|
|
290 \caption{index treeを用いたinodeの検索の流れ}
|
|
|
291 \label{fig:inode}
|
|
|
292 \end{figure}
|
|
|
293
|
|
|
294 GearsOSにおける永続データは非破壊的な編集を行う木構造を用いて保存する．
|
|
|
295 図\ref{fig:TreeEdit}は非破壊的編集を木構造に対し行う様子である．
|
|
|
296 赤で示されたノード6をAに編集する場合，まずルートノードから編集ノードまでのパスを全てコピーする．
|
|
|
297 コピーしたパス上に存在しないノードは，コピー元の木構造と共有する．
|
|
|
298 それにより，編集後の木構造の赤のルートノードから探索を行う場合は編集されたAのノードが見え，
|
|
|
299 黒のルートノードから探索を行う場合は編集前の6のノードを見ることができる．
|
|
|
300 ディレクトリシステムを非破壊的な木構造の編集を用いて実装することにより，
|
|
|
301 ディレクトリシステム自体にバックアップの機能を搭載することが可能であると考える．
|
|
|
302
|
|
|
303 \begin{figure}[ht]
|
|
|
304 \begin{center}
|
|
|
305 \includegraphics[width=80mm]{figs/nonDestroyTreeEdit.pdf}
|
|
|
306 \end{center}
|
|
|
307 \caption{非破壊的なTree編集}
|
|
|
308 \label{fig:TreeEdit}
|
|
|
309 \end{figure}
|
|
|
310
|
|
|
311 \section{GearsFileSystemにおけるインターフェース}
|
|
|
312
|
|
|
313 ファイルやディレクトリの操作を行うインターフェースをUnix Likeに実装を行った．
|
|
|
314 実装を行ったmkdir, ls, cdを説明する．
|
|
|
315
|
|
|
316 \subsection{mkdir}
|
|
|
317 Unixにおいてmkdirは新しくディレクトリを作成するコマンドである．
|
|
|
318 GearsDirectoryのmkdirはindex treeとinode treeにnodeをputすることでディレクトリを作成する．
|
|
|
319 ソースコード\ref{src:mkdir}はGearsDirectoryにおけるmkdirのCodeGearであり，図\ref{fig:mkdir}はその処理を図で表したものである．
|
|
|
320 まず1行目の\emph{\_\_code mkdir}ではinode treeへinodeのputが行われ，\emph{\_\_code mkdir2}へ遷移する．
|
|
|
321 inodeは4,5行目でkeyにinode number, valueにディレクトリのポインタがセットされる．
|
|
|
322 次に，11行目の\emph{\_\_code mkdir2}ではindex treeへkeyがfilename，valueがinode numberのnodeのputが行われ，nextのCodeGearへ遷移する．
|
|
|
323 このように，FileSystemTreeのputを2回行うため，mkdirは\emph{\_\_code mkdir}と\emph{\_\_code mkdir2}の2つのCodeGearで構成されている．
|
|
|
324 また，InputDataGearの\emph{name}はfilenameを表す．
|
|
|
325 \lstinputlisting[caption=mkdirのCodeGear,label=src:mkdir]{src/mkdir.cbc}
|
|
|
326 \begin{figure}[ht]
|
|
|
327 \begin{center}
|
|
|
328 \includegraphics[width=80mm]{figs/mkdir.pdf}
|
|
|
329 \end{center}
|
|
|
330 \caption{mkdirの操作の流れ}
|
|
|
331 \label{fig:mkdir}
|
|
|
332 \end{figure}
|
|
|
333
|
|
|
334 \subsection{ls}
|
|
|
335 Unixにおいてlsはファイルやディレクトリの一覧，メタ情報を表示するコマンドである．
|
|
|
336 GearsDirectoryのlsはindex treeに対し，getをすることでディレクトリのnameを取得する．
|
|
|
337 これは，Unixのlsコマンドにおける\emph{\$ls filename}に等しい機能である．
|
|
|
338 ソースコード\ref{src:ls}はGearsDirectoryにおけるlsのCodeGearであり，図\ref{fig:ls}はその処理を図で表したものである．
|
|
|
339 まず1行目の\emph{\_\_code ls}ではindex treeに対しgetを行うため，
|
|
|
340 3行目でgetしたいfilenameをkeyにセットし，index treeのgetへgotoしている．
|
|
|
341 その後，9行目の\emph{\_\_code ls2}ではnode\verb|->|keyに格納されたgetの結果をprintfで出力する．
|
|
|
342 本来lsコマンドは引数を渡さずに実行するとカレントディレクトリ下のディレクトリやファイルを一覧で表示するが，
|
|
|
343 現時点では未実装である．
|
|
|
344 なお，一覧表示の機能はfilenameのリストをディレクトリに持たせることで実装可能であると思われる．
|
|
|
345 \lstinputlisting[caption=lsのCodeGear,label=src:ls]{src/ls.cbc}
|
|
|
346 \begin{figure}[ht]
|
|
|
347 \begin{center}
|
|
|
348 \includegraphics[width=80mm]{figs/ls.pdf}
|
|
|
349 \end{center}
|
|
|
350 \caption{lsの操作の流れ}
|
|
|
351 \label{fig:ls}
|
|
|
352 \end{figure}
|
|
|
353
|
|
|
354 \subsection{cd}
|
|
|
355 Unixにおいてcdはディレクトリを移動するコマンドである．
|
|
|
356 GearsDirectoryのcdはindex treeとinode treeに対しgetを行い，currentDirectoryを書き換えることで実装する．
|
|
|
357 機能としてはディレクトリが持つ子ディレクトリへの移動ができる．
|
|
|
358 ソースコード\ref{src:cd}はGearsDirectoryにおけるcdのCodeGearであり，図\ref{fig:cd}はその処理を図で表したものである．
|
|
|
359 まず1行目の\emph{\_\_code cd2Child}でindex treeに対しgetを行うため，index treeのgetへgotoしている．
|
|
|
360 次に，9行目の\emph{\_\_code cd2Child2}でinode treeに対しgetを行うため，inode treeのgetへgotoしている．
|
|
|
361 この際，getは1行目のcd2Childでgetしたnodeのvalueをもとに行う．valueにはinode numberがセットされている．
|
|
|
362 その後，15行目の\emph{\_\_code cd2Child3}でcurrent ディレクトリを保存しているgearsDirectory\verb|->|currentDirectoryを
|
|
|
363 getしたnode\verb|->|valueに書き換える．
|
|
|
364 \lstinputlisting[caption=cdのCodeGear,label=src:cd]{src/cd.cbc}
|
|
|
365 \begin{figure}[ht]
|
|
|
366 \begin{center}
|
|
|
367 \includegraphics[width=80mm]{figs/cd.pdf}
|
|
|
368 \end{center}
|
|
|
369 \caption{cdの操作の流れ}
|
|
|
370 \label{fig:cd}
|
|
|
371 \end{figure}
|
|
|
372
|
|
|
373 \section{GearsFileSystemにおけるファイルの構成}
|
|
|
374
|
|
|
375 ファイルシステムはディレクトリの構成だけでなく，ファイルの構成についても考える必要がある．
|
|
|
376 本研究と並行する形で一木貴裕による分散ファイルシステムの設計が行われており\cite{cfile}，
|
|
|
377 ファイルの構成に関しても実装，検討されている．
|
|
|
378 GearsOSにおけるファイル構成を説明する．
|
|
|
379
|
|
|
380 ファイルのInput/Output Streamは競合的なアクセスに対応するため，3つのSynchronizedQueueを用いる．
|
|
|
381 それぞれをInputQueue, OutputQueue, mainQueueと呼ぶ．
|
|
|
382 データをinputしたい場合InputQueueへputを行い，取得したい場合OutputQueueからgetを行う．
|
|
|
383 mainQueueはデータそのものであり，InputQueueからmainQueue，mainQueueからOutputQueueへデータが流れるように接続される．
|
|
|
384 これらは，Gearの概念ではDataGearにあたり，DataGearManagerにkeyとI/O Queueが対応する形で保持される．
|
|
|
385 ファイルの中身のデータをレコードに分割し，レコードをQueueにputしてstreamに入れる．
|
|
|
386 データを取り出す際はQueueからgetし，順番に読むことでファイルを構築する．
|
|
|
387
|
|
|
388 分散ファイルシステムはファイルのデータ送受信をする際に用いられるAPIを作成する必要がある．
|
|
|
389 WordCount例題\cite{file}を通して，GearsFileのAPIの作成を行う．
|
|
|
390 WordCount例題は指定したファイルの文字数や行数，ファイルの内の文字列を出力する．
|
|
|
391 図\ref{fig:WCStates}はWordCount例題の処理の流れを示している．
|
|
|
392 これは大きく分けて，指定したファイルをFile構造体としてopenするFileOpenスレッド，
|
|
|
393 File構造体を受け取り文字数と行数をcountUpするWordCountスレッドの二つのCodeGearで記述することができる．
|
|
|
394 また，ファイル内の文字列を行ごとにCountUpに送信し，EOFを受け取ったらループを抜けfinishに移行する．
|
|
|
395 \begin{figure}[ht]
|
|
|
396 \begin{center}
|
|
|
397 \includegraphics[width=80mm]{figs/wordCountStates.pdf}
|
|
|
398 \end{center}
|
|
|
399 \caption{WordCount with CbC}
|
|
|
400 \label{fig:WCStates}
|
|
|
401 \end{figure}
|
|
|
402
|
|
|
403 \section{GearsOSのメモリマネージメントシステムの考察}
|
|
|
404
|
|
|
405 GearsOSのメモリマネージメントは，メモリ上のデータとディスク上のデータの構造が等しくなる形で実装をしたい．
|
|
|
406 メモリ上とディスク上でデータの構造を等しくすることで，単純なコピーでメモリとディスク間のデータのやり取りを行うことができる．よって，比較的簡素に実装を行うことができると予想する．
|
|
|
407 しかしながら，メモリ上とディスク上でオフセットの差が出る問題がある．
|
|
|
408 これは，メタ計算でオフセットの差を吸収する処理を行うことで解決させる．
|
|
|
409 また，メモリ上とディスク上のデータのアドレスが異なるため，ユーザーレベルからポインタを用いた場合，問題になる．
|
|
|
410 しかしながら，GearsOSではユーザーレベルでポインタを用いることを禁止しているため，問題ないと考える．
|
|
|
411
|
|
|
412 ガベージコレクションについては，Copying GCを用いる．
|
|
|
413 Copying GCは単純に用いるとメモリ容量が倍必要になるという問題がある．
|
|
|
414 そこで，リンクしているデータのみをコピーすることによってメモリ使用量を削減したい．
|
|
|
415 データがリンクされているかどうかはLinkedListを参照し判断する．
|
|
|
416
|
|
|
417
|
|
|
418 \section{今後の課題}
|
|
|
419
|
|
|
420 \subsection{GearsShell}
|
|
|
421 GearsOSに存在する未実装の機能の一つにshellが挙げられる．
|
|
|
422 現状のGearsOSはユーザーの入力を受け付けることが出来ず，プログラミングインターフェースの様に機能している．
|
|
|
423 GearsFileSystemなどGearsOSの各機能と接続し，今回作成したcdやlsの様なコマンドを受け付けるGearsShellを作成したい．
|
|
|
424
|
|
|
425 \subsection{GearsDirectory filename}
|
|
|
426 現状はGearsDirectoryのfilenameはIntegerの構造で管理されている．
|
|
|
427 しかしながら，filenameは一般的に文字列型であるためIntegerから文字列型に変更する必要がある．
|
|
|
428
|
|
|
429 \subsection{GearsDirectory path}
|
|
|
430 GearsDirectoryにはpathの機能が実装されていない．
|
|
|
431 よってfull path指定のlsなどが実装できない状態である．
|
|
|
432 FileSystemTreeを拡張し，ノードをたどりpathを生成する様な機能を実装する必要がある．
|
|
|
433
|
|
|
434 \subsection{ファイルのバックアップ}
|
|
|
435 ディレクトリに関しては非破壊的なTree編集を用いることで，バックアップを行うことを考えたが
|
|
|
436 ファイルに関してはレコードのDataをファイルの差分履歴として保持し，
|
|
|
437 日時情報を付け加えることでVersion Control Systemのような機能を持たせることが可能であると考えられる．
|
|
|
438
|
|
|
439 \subsection{GearsDirectory on disk}
|
|
|
440 現状はGearsDirectoryのinodeはon memoryで実装されている．
|
|
|
441 データの保存はdisk上に行うため，inodeをdisk上に構築し必要がある
|
|
|
442
|
|
|
443 \section{まとめ}
|
|
|
444
|
|
|
445 本研究では主としてGearsFileSystemの構築に必要なGearsDirectoryの実装について説明した．
|
|
|
446 いくつか課題はあるが，RedBlackTreeのシンプルなインターフェースにより比較的容易に実装を行うことができた．
|
|
|
447 また，RedBlackTreeを用いてinodeの仕組みを構築し，ls，cd，mkdirを作成するなどして，
|
|
|
448 Unix Likeに構築することが出来た．
|
|
|
449 メモリマネージメントについては，今後の研究で実装と考察を行い，
|
|
|
450 Gears OSのメモリマネージメントシステムを構築していく．
|
|
|
451
|
|
|
452 信頼性については，定理証明やモデル検査を用いて保証を行うが，
|
|
|
453 非破壊的なTree編集によるディレクトリのバックアップやファイルのバックアップをファイルシステムに組み込むことでも
|
|
|
454 信頼性の向上が期待できる．形式手法とファイルシステムの機能の両面で信頼性の向上が図れると考える．
|
|
|
455
|
|
|
456 \nocite{*}
|
|
|
457 \bibliographystyle{ipsjunsrt}
|
|
|
458 \bibliography{matac-bib}
|
|
|
459
|
|
|
460 \end{document}
|
