--- a/Paper/chapter/3-GearsOS.tex	Wed Jan 12 01:52:39 2022 +0900
+++ b/Paper/chapter/3-GearsOS.tex	Sun Jan 16 23:43:38 2022 +0900
@@ -155,3 +155,23 @@
 
 
 \lstinputlisting[label=src:SynchronizedQueue.c, caption=SynchronizedQueue.c]{src/SynchronizedQueue.c}
+
+\section{SynchronizedQueue}
+GearsOSには先行研究[先行研究リンク][SingleLinkedな穴蔵さんのやつも？]にてGearsシンタックスを用いて実装されたQueueが存在している。
+Queueは単純なQueueとしての機能を実装したSingleLinkedQueueと、
+マルチスレッドによる複数のプロセスからのアクセスにも対応するためのSynchronizedQueueが存在する。
+
+SynchronizedQueueは複数のプロセスからのアクセスが発生した際のデータの一貫性の保証方法として、
+CAS(Check and Set, Compare and Swap)を採用している。
+CASは値の比較、更新をアトミックに行う命令である。
+CASは更新前と更新後の値を受け取り、更新前の値と書き換え先のメモリ番地の実際の値と比較し、同じだった場合、
+データ競合がないため、データの更新を行う。値が異なった場合は他のプロセスから書き込みが行われたとみなされ、値の更新に失敗する。
+
+GearsOSではCASを行うためのInterfaceをAtomicとして定義している。
+AtomicのInterfaceをソースコード\ref{src:Atomic.h}に示す。
+ptrはデータ格納先のポインタのポインタ、oldData,newDataはそれぞれ更新前の値と更新後の値を示す。
+\texttt{\_\_}code nextにはCASが成功した場合の遷移先を、\texttt{\_\_}code failには失敗した場合の遷移先のCodeGearを指定する。
+
+SynchronizedQueueではデータのputもしくはtakeの際、要素の先頭もしくは最後尾の要素のアドレスに対してCASが行われる(ソースコード\ref{src:SynchronizedQueue.cbc})
+
+\lstinputlisting[label=src:Atomic.h, caption=Atomic.h]{src/Atomic.h}

--- a/Paper/chapter/4-Christie.tex	Wed Jan 12 01:52:39 2022 +0900
+++ b/Paper/chapter/4-Christie.tex	Sun Jan 16 23:43:38 2022 +0900
@@ -162,3 +162,16 @@
 動的TopologyはTopologyManager内にすでに設計されたTopologyの形状を選択した上で
 参加を表明したノードに対して自動的にノードの配線を行う。
 例えばTreeを構成する場合、参加したノードから順番にrootから近い役割を与えていく。
+また、TopologyManagerはCodeGearManagerの一つが運用する。
+図\ref{fig:TM}にTopplogyManagerにて簡単なTree型Topologyを形成する際の図を示す。
+図中の場合、CGAがTopoplogyManagerを所持しており、
+TopologyManagerによってCG1がroot、CG2とCG3がCG1の子として役を割り振られ、接続される形となる。
+
+
+\begin{figure}[tb]
+    \begin{center}
+        \includegraphics[width=150mm]{./images/TopologyManager.pdf}
+    \end{center}
+    \caption{TopologyManagerにてTree型Topologyを形成する際の図}
+    \label{fig:TM}
+\end{figure}

--- a/Paper/chapter/5-Implementation.tex	Wed Jan 12 01:52:39 2022 +0900
+++ b/Paper/chapter/5-Implementation.tex	Sun Jan 16 23:43:38 2022 +0900
@@ -0,0 +1,111 @@
+\chapter{GearsFileSystem Implementation}
+本章ではGearsOSのFileSystem(以下GearsFS)の実装について解説する。
+GearsOSのファイルは分散ファイルシステム的に大域的な資源として、
+複数のプロセスから競合的なアクセスが可能を可能としたい。
+
+GearsFSは分散フレームワークChristieの仕組みの一部を応用する。
+Christieの仕組みを取り入れることで、ファイルの送受信に関しては、
+ファイル内データをDataGearとして送受信することで実現する。
+
+
+\section{WordCount例題}
+GearsFSのAPIの構成をWordCount例題を通して行う。
+WordCount例題とは、指定したファイルの中身を読み取り、文字数と行数列、加えて文字列などを出力するという例題である。
+コード\ref{src:WcImpl}にCbCで記述した、Unixファイルに対してWordCountを行うプログラムの一部を示す。
+
+ファイルとWordCountはUNIXのシェルのようにプログラムの外で行われる。
+ファイルは事前にC言語のFILE型構造体を用いて開かれ、行列であるwc->strTableへ内部文字列を行区切りで保存されている。
+MainからファイルのOpenが完了した後、CodeGear:putStrinに遷移し、strTableから文字列を行ごと呼び出しCountUpへ入力し遷移する。
+CodeGear:CountUpにて文字列の出力と文字数を読み取り記録、そしてputStringへ遷移する。
+ファイルの文字列がある間はputStringとCountUpをループし続け、
+putStringはstrTableの中身がなくなった(EOF)ならshowResultへ遷移する形となる。
+図\ref{fig:WordCount}にCGの遷移図を示す。
+
+
+\lstinputlisting[label=src:WcImpl, caption=Unixファイルに対するWordCount.cbcの一部]{src/WcImpl.cbc}
+
+\begin{figure}[tb]
+    \begin{center}
+        \includegraphics[width=150mm]{./images/UnixWC.pdf}
+    \end{center}
+    \caption{Unixファイルに対するWordCountのCG遷移}
+    \label{fig:WordCount}
+\end{figure}
+
+
+\section{GearsFSのファイル構成}
+GearsOSのファイルは単なるDataGearのListQueueとして実装する。
+また、ファイルのデータを貯蓄する主要なQueueとは別にinputもしくはoutputStreamとなるQueueを持ち合わせている。
+ソースコードに\ref{src:GearsFileImpl.h}GearsOSのファイルのImplementを示す。
+
+\lstinputlisting[label=src:GearsFileImpl.h, caption=GearsFileImpl.h]{src/GearsFileImpl.h}
+
+GearsFSではファイル読み込みもしくは書き込みの際、それぞれinputもしくはoutputの際にストリームのキューに対してアクセスを行う。
+それぞれのキューはGearsのファイル構造体にkeyとのペアとして保存される。
+そのためGearsFSのファイルはChrsitieにおけるDataGearManagerに相当する。
+それぞれのキューはDataGearに相当する。
+GearsOSのファイル構造へのアクセスを図\ref{fig:gearsFile}に示す。
+また、データのリストとなるQueueの構造を図\ref{fig:QueueElement}に示す。
+
+
+\begin{figure}[h]
+    \begin{center}
+        \includegraphics[width=150mm]{./images/GearsFile.pdf}
+    \end{center}
+    \caption{GearsFSのファイル構造}
+    \label{fig:gearsFile}
+\end{figure}
+
+
+\begin{figure}[h]
+    \begin{center}
+        \includegraphics[width=150mm]{./images/QueueElement.pdf}
+    \end{center}
+    \caption{DataQueueの構造}
+    \label{fig:QueueElement}
+\end{figure}
+
+
+ファイルに対して変更、つまり新しく書き込みを行う際はInputQueueのkeyを指定してput操作を行う。
+最終的にInputQueueに格納されたデータはInputQueueから取り出され、mainQueueに対して格納される。
+
+ファイルの読み込みを行う際はOutputQueueに対してTake操作を行えば良い。
+OutputQueueにはmainQueueの要素が複製されており、OutputQueue内の要素を全てTakeで呼び出す。
+ファイルを呼び出す側は取り出したElementのログを順番に読むことでファイルを構築する。
+
+GearsOSのファイルは大域的な資源として同時に複数のプロセスから参照が可能になる作りにしたい。
+そのため、OutputQueueは複数のプロセスから参照が行われた際に、データの整合性が失われてはならない。
+そのため、OutputQueueはCAS(Compare And Swap)を実装したSynchronizedQueueを用いる。
+データアクセスが単一のプロセスからしか許さないもしくは想定されていない環境では容量の軽量化のため、
+SingleLinkedな(単純な)Queueを用いることも考えられる。
+ファイルに対する書き込みやMainQueueは単一プロセスのみからのアクセスとなるためSingleLickedなキューで実装する。
+
+\section{ディレクトリシステム}
+本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている。[論文No.]
+GearsFSのディレクトリシステムはUnixOSのディレクトリシステムと同じ仕組みを用いて再現することを試みている。
+通常のUnixのディレクトリシステムと異なる点として、ディレクトリをRedBlackTreeを用いて構成する。
+
+図\ref{fig:GearsDirectory}にGearsFSの構成図を示す。
+一つのディレクトリは赤黒木であり、あるディレクトリの中に位置するファイル(ディレクトリ含む)は赤黒木の中のノードにvalueとして同等に配置される。
+赤黒木にはファイル下に配置された別のディレクトリもしくはファイル構造が保存される。
+図の例では/(ルートディレクトリ)からUsersディレクトリ下にあるDadというディレクトリ(もしくはファイル)を参照するには、
+/のTree内のUsersを探索、続いてUsersTreeの内部のDadを探索する形となる。
+
+
+
+
+\begin{figure}[h]
+    \begin{center}
+        \includegraphics[width=80mm]{./images/GearsDirectory.pdf}
+    \end{center}
+    \caption{GearsDirectory}
+    \label{fig:GearsDirectory}
+\end{figure}
+
+
+\section{GearsFSのバックアップ}
+GearsOSは将来的にOS自体がバックアップの機能を保持する構成を目指している。
+
+
+
+\section{ChristieAPIによるWordCount}

Binary file Paper/images/TopologyManager.graffle.graffle has changed

Binary file Paper/images/TopologyManager.pdf has changed

Binary file Paper/master_paper.pdf has changed