Mercurial > hg > Papers > 2022 > ikki-master

comparison Paper/chapter/5-Implementation.tex @ 22:bd9284f9151d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
tweak
author ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
date Wed, 09 Feb 2022 23:58:05 +0900
parents f8a089dbfe06
children 90e6ac8805e2
comparison
equal deleted inserted replaced
21:f8a089dbfe06 22:bd9284f9151d
44 44
45 \begin{figure}[h] 45 \begin{figure}[h]
46 \begin{center} 46 \begin{center}
47 \includegraphics[width=150mm]{./images/GearsFile.pdf} 47 \includegraphics[width=150mm]{./images/GearsFile.pdf}
48 \end{center} 48 \end{center}
49 \caption{GearsFSのread/writeAPI} 49 \caption{GearsFSの呼び出し/書き込み}
50 \label{fig:gearsFile} 50 \label{fig:gearsFile}
51 \end{figure} 51 \end{figure}
52 52
53 53
54 ファイルに対して書き込み、つまり従来のwriteにあたる処理を行う場合はInputQueueのkeyを指定してput操作を行う。 54 ファイルに対して書き込み、つまり従来のwriteにあたる処理を行う場合はInputQueueのkeyを指定してput操作を行う。
55 最終的にInputQueueに格納されたデータはInputQueueから取り出され、mainQueueに対して格納される。 55 最終的にInputQueueに格納されたデータはInputQueueから取り出され、mainQueueに対して格納される。
56 56
57 ファイルの読み込み(read)を行う際はOutputQueueに対してTake操作を行えば良い。 57 ファイルの読み込み(既存のファイルシステムでのread)を行う際はOutputQueueに対してTake操作を行えば良い。
58 OutputQueueにはmainQueueの要素が複製されており、OutputQueue内の要素を全てTakeのループにより呼び出す。 58 OutputQueueにはmainQueueの要素が複製されており、OutputQueue内の要素を全てTakeのループにより呼び出す。
59 ファイルを呼び出す側は取り出したレコードを順番に読むことでファイルを構築する。 59 ファイルを呼び出す側は取り出したレコードを順番に読むことでファイルを構築する。
60 60
61 GearsOSのファイルは大域的な資源として同時に複数のプロセスから参照が可能になる作りにしたい。 61 GearsOSのファイルは大域的な資源として同時に複数のプロセスから参照が可能になる作りにしたい。
62 OutputQueueは複数のプロセスからファイルreadが行われた際に、データの整合性が失われてしまう危険性がある。 62 OutputQueueは複数のプロセスからファイル読み込みが行われた際に、データの整合性が失われてしまう危険性がある。
63 そのため、OutputQueueはCAS(Compare And Swap)を実装したSynchronizedQueueを用いる。 63 そのため、OutputQueueはCAS(Compare And Swap)を実装したSynchronizedQueueを用いる。
64 しかしファイルのアクセス権限の設定などにより、データアクセスが単一のプロセスからしか許さないもしくは想定されない環境では 64 しかしファイルのアクセス権限の設定などにより、データアクセスが単一のプロセスからしか許さないもしくは想定されない環境では
65 読み込みの高速化とメモリの軽量化のため、 65 読み込みの高速化とメモリの軽量化のため、
66 SingleLinkedな(単純な)Queueを用いることも考えられる。 66 SingleLinkedな(単純な)Queueを用いることも考えられる。
67 ファイルに対する書き込みやMainQueueは単一プロセスのみからのアクセスとなるためSingleLickedなキューで実装する。 67 ファイルに対する書き込みやMainQueueは単一プロセスのみからのアクセスとなるためSingleLickedなキューで実装する。
85 85
86 86
87 \section{WordCount例題} 87 \section{WordCount例題}
88 GearsFSのAPIの構成をWordCount例題を通して行った。 88 GearsFSのAPIの構成をWordCount例題を通して行った。
89 WordCount例題とは、指定したファイルの中身を読み取り、文字数と行数列、加えて文字列を出力するという例題である。 89 WordCount例題とは、指定したファイルの中身を読み取り、文字数と行数列、加えて文字列を出力するという例題である。
90 この例題により連続したレコードをQueueから順次読みだすreadAPIを構築した。 90 この例題により連続したレコードをQueueから順次読みだす処理を構築した。
91 コード\ref{src:WcImpl}にCbCで記述した、Unixファイルに対してWordCountを行うプログラムの一部を示す。 91 コード\ref{src:WcImpl}にCbCで記述した、Unixファイルに対してWordCountを行うプログラムの一部を示す。
92 92
93 ファイルとWordCountの接続はUNIXのシェルのようにプログラムの外で行われる。 93 ファイルとWordCountの接続はUNIXのシェルのようにプログラムの外で行われる。
94 ファイルは事前にC言語のFILE型構造体を用いて開かれ、行列であるwc\texttt{->}strTableへ内部文字列を行区切りで保存されている。 94 ファイルは事前にC言語のFILE型構造体を用いて開かれ、行列であるwc\texttt{->}strTableへ内部文字列を行区切りで保存されている。
95 MainからファイルのOpenが完了した後、CodeGear:putStrinに遷移し、strTableから文字列を行ごと呼び出しCountUpへ入力し遷移する。 95 MainからファイルのOpenが完了した後、CodeGear:putStrinに遷移し、strTableから文字列を行ごと呼び出しCountUpへ入力し遷移する。
96 CodeGear:CountUpにて文字列の出力と文字数を読み取り記録、そしてputStringへ遷移する。 96 CodeGear:CountUpにて文字列の出力と文字数を読み取り記録、そしてputStringへ遷移する。
97 ファイルの文字列がある間はputStringとCountUpをループし続け、 97 ファイルの文字列がある間はputStringとCountUpをループし続け、
98 putStringはstrTableの中身がなくなった(EOF)ならshowResultへ遷移する形となる。 98 putStringはstrTableの中身がなくなった(EOF)ならshowResultへ遷移する形となる。
99 図\ref{fig:WordCount}にCGの遷移図を示す。 99 図\ref{fig:WordCount}にCGの遷移図を示す。
100
101 WordCountのFileOpenとWordCount処理を別ノード上で行うことで、ファイルの読み込みとファイルの送信の構成が行える。
100 102
101 \lstinputlisting[label=src:WcImpl, caption=Unixファイルに対するWordCount.cbcの一部]{src/WcImpl.cbc} 103 \lstinputlisting[label=src:WcImpl, caption=Unixファイルに対するWordCount.cbcの一部]{src/WcImpl.cbc}
102 104
103 \begin{figure}[h] 105 \begin{figure}[h]
104 \begin{center} 106 \begin{center}
224 226
225 227
226 228
227 \section{ディレクトリシステム} 229 \section{ディレクトリシステム}
228 本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている\cite{mata-thesis}。 230 本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている\cite{mata-thesis}。
229 GearsFSのディレクトリシステムはUnixOSのディレクトリシステムのinodeの仕組みを用いて再現することを試みている。 231 GearsFSのディレクトリシステムはUnixOSのディレクトリシステムのi-nodeの仕組みを用いて再現することを試みている。
230 通常のUnixのディレクトリシステムと異なる点として、ディレクトリを赤黒木(RedBlackTree)を用いて構成する。 232 通常のUnixのディレクトリシステムと異なる点として、ディレクトリを赤黒木(RedBlackTree)を用いて構成する。
231 233
232 図\ref{fig:GearsDirectory}にGearsFSの構成図を示す。 234 図\ref{fig:GearsDirectory}にGearsFSの構成図を示す。
233 一つのディレクトリは赤黒木を持ち、あるディレクトリの中に位置するファイル(ディレクトリ含む)は親ディレクトリが持つ赤黒木の中にノードとして同等に配置される。 235 一つのディレクトリは赤黒木を持ち、あるディレクトリの中に位置するファイル(ディレクトリ含む)は親ディレクトリが持つ赤黒木の中にノードとして同等に配置される。
234 あるディレクトリに存在するファイルを参照する場合は、ディレクトリの持つTreeに対して探索を行えば良い。 236 あるディレクトリに存在するファイルを参照する場合は、ディレクトリの持つTreeに対して探索を行えば良い。
242 \end{center} 244 \end{center}
243 \caption{GearsDirectory} 245 \caption{GearsDirectory}
244 \label{fig:GearsDirectory} 246 \label{fig:GearsDirectory}
245 \end{figure} 247 \end{figure}
246 248
247 GearsのディレクトリシステムはUnixのinodeの仕様を用いる。 249 GearsのディレクトリシステムはUnixのi-nodeの仕様を用いる。
248 inodeとはファイルごとのユニークな番号(inode番号)。データ領域へのポインタや作成日時、サイズなどのメタデータを保存するための領域である。 250 i-nodeとはファイルごとのユニークな番号(i-node番号)。データ領域へのポインタや作成日時、サイズなどのメタデータを保存するための領域である。
249 GearsFSの赤黒木を用いたディレクトリシステムに実際に保存されるノードはkeyがFileName、 251 GearsFSの赤黒木を用いたディレクトリシステムに実際に保存されるノードはkeyがFileName、
250 valueがinodeのペアを保持している。 252 valueがi-nodeのペアを保持している。
251 DirectoryTreeをファイル名で探索を行うことで任意のファイルのinode番号を手に入れ、DirectroyTreeとは別に実装されたkeyにinode番号とペアとして 253 DirectoryTreeをファイル名で探索を行うことで任意のファイルのi-node番号を手に入れ、DirectroyTreeとは別に実装されたkeyにi-node番号とペアとして
252 ファイルのディスクアドレスを保持させるTreeをinode番号で探索させる形となる。 254 ファイルのディスクアドレスを保持させるTreeをi-node番号で探索させる形となる。
253 この形で実装することにより、ファイル自身が所属するDirectoryをinodeが保持でき、 255 この形で実装することにより、ファイル自身が所属するDirectoryをi-nodeが保持でき、
254 ファイルの複数のアカウントでの共有などによる親Directoryが複数存在する場合や、 256 ファイルの複数のアカウントでの共有などによる親Directoryが複数存在する場合や、
255 親DirectoryのFileNameが変更された場合においてもDirectoryの構造の障害の発生を防げぐことができる。 257 親DirectoryのFileNameが変更された場合においてもDirectoryの構造の障害の発生を防げぐことができる。
256 258
257 259
258 260