Mercurial > hg > Papers > 2022 > ikki-master

changeset 8:25cf5b9b74a2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add GearsDGM
author ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
date Sat, 22 Jan 2022 23:27:45 +0900
parents b31312c4d2de
children cc4cb64f9af9
files Paper/chapter/5-Implementation.tex Paper/images/GearsDGM.graffle.graffle Paper/images/GearsDGM.pdf Paper/master_paper.pdf Paper/src/LocalDGMQueue.cbc Paper/src/RemoteDGMQueue.cbc
diffstat 6 files changed, 189 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
--- a/Paper/chapter/5-Implementation.tex	Tue Jan 18 21:03:13 2022 +0900
+++ b/Paper/chapter/5-Implementation.tex	Sat Jan 22 23:27:45 2022 +0900
@@ -8,46 +8,19 @@
 ファイル内データを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に相当する。
+それぞれのキューはkey名としてinput/OutputstreamをもつQueueとして呼び出される。
+それぞれのキューはDataGearに相当し、GearsFSのファイルはChrsitieにおけるDataGearManagerに相当する。
 GearsOSのファイル構造へのアクセスを図\ref{fig:gearsFile}に示す。
 また、データのリストとなるQueueの構造を図\ref{fig:QueueElement}に示す。
 
 
+
 \begin{figure}[h]
     \begin{center}
         \includegraphics[width=150mm]{./images/GearsFile.pdf}
@@ -82,6 +55,126 @@
 
 
 
+
+\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の遷移図を示す。
+このように特定の条件を満たすまであるCodeGear間をループ遷移する構成をGearBoxと名付けている。
+
+
+\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{ChristieAPIによるWordCount}
+ChiristieのDataGearManagerの仕組みを基準としたGearsFSのファイル通信のAPIによるWordCountの設計を行った。
+図\ref{fig:ChristieAPI}にChristieAPIによるWordCountを示す。
+ChristieAPIによるファイルデータ通信は2ペアのLocal/RemoteDGMを通して行われる。
+NodeA側が任意のファイルを開き、ファイル内の行ごとの文字列をデータとしてNodeB側に対応するRemoteDGMにputする。
+NodeB側は自身のLocalなDGMからデータを得て、WordCountの処理を行ったのちに
+NodeAに対応するRemoteDGMに対してそのデータに対する処理が完了したことを通知するAck(acknowledgement)をputする。
+Ackを受け取ったOpen側のノードBは再び続きのファイル内文字列をデータとして送信する。
+ここまでの処理が繰り返され、ファイル内の文字列が全て処理されたら、Open側はEoF(End of File)をCount側に対して通知、
+NodeBは最後にWordCountの結果をRemoteDGMに対してputしOpen側に送信する。
+そして、双方のRemoteDGMを閉じることにより通信を終了させる。
+
+図中ではRemoteDGMを複数作成することにより通信のやりとりを行っているが、
+WordCountでない純粋なファイルの送信などの場合、DGMのSocketが持つAckのみでも通信を構成することが可能である。
+そのためデータの一方的な送受信のみならDGMのペアは一つだけでも通信が行うことができる。
+
+
+
+\begin{figure}[h]
+    \begin{center}
+        \includegraphics[width=150mm]{./images/wordCountDGM.jpg}
+    \end{center}
+    \caption{ChristieAPIによるWordCount}
+    \label{fig:ChristieAPI}
+\end{figure}
+
+
+\section{Socket付きQueue}
+ChristieにおけるRocalDataGearManagerはプログラム内で使われるDataGearのkeyとデータを全て所持したコレクションにあたる。
+keyとデータの組み合わせは、keyの名前がつけられたQueueに対して保存される、
+TakeコマンドではそのkeyのQueueからデータを取り出し、Peekの場合は先頭のデータを取り出さず参照のみを行っている。
+つまりChristieのDGMは詳細には単純なQueueの集合であると言える。
+RemoteDGMとLocalDGMの通信の際にはLocalDGMが持つsocketに対してRemoteDGMが接続を行い、putされたkeyとDataをsocket経由でコマンドとして送信する。
+
+GearsOSのChristieAPIの定義のためにsocketに接続されたQueueによるWordCount例題を作成した。
+ソースコード\ref{src:LDGMQueue}にLocalDGM側にあたる、Socket付きのQueueのCodeGear:getData部分を示す。
+加えてソースコード\ref{src:RDGMQueue}にRemoteDGM側にあたるSocket付きのQueueのCodeGear:sendData部分を示す。
+socketはC言語のSocketインターフェースを用いており、
+ImplementのコンストラクタにあたるcreateLocalDGMQueueにて呼び出され、
+Implのメンバ変数であるsocketに置かれている。
+また、既存のQueueから新たなAPIを追加するためにQueueInterfaceを新しく書き換えたcQueue(Communicate Queue)Interfaceを継承している。
+Local側のgetDataはAPIとしての呼び出しが可能となっている。socketが受け取ったデータを最終的にdataとしてQueueに対してputを行う。
+Remote側のsendDataはAPIとしては呼び出しは行えず、putAPIが呼び出されQueueへのput処理が終了した後に遷移され、putしたDataを接続先のQueueに対して送信する。
+送信データは全てのDataGearのUnionとなるData型で受け取る。
+送信データのサイズをUnion Data型のサイズにしている理由は、sizeof関数で返される値は共用体に含まれる構造体の中で最も大きなメモリサイズを返すためである。
+Socketの処理中に問題が発生した場合はinputDataGearとして指定した\texttt{\_\_}code whenError()として入力されたCodeGearに対して遷移する。
+
+GearsOSにおけるファイルはChristieのDGMとして見なすことができる。
+今回作成したQueueはそれぞれInput/OutputStreamに相当する。
+
+\lstinputlisting[label=src:LDGMQueue, caption=LocaDGMQueueのgetData]{src/LocalDGMQueue.cbc}
+\lstinputlisting[label=src:RDGMQueue, caption=RemoteDGMQueueのsendData]{src/RemoteDGMQueue.cbc}
+
+
+
+\section{GearsOSにおけるDataGearManager}
+先で述べたSocket付きのQueueは、DataGearであるQueueとSocketが直接結びついているため、
+一つのDataGearを用いる場合となる最低限の通信しか行えない。
+複数のDataGear(key)を用いての通信を構成するためには複数のQueueを備えることのできるリストを生成し、
+そのリスト自体がsocketを持つ必要がある。
+
+GearsOSではDataGearを保持するQueueのリストとして赤黒木を用いる。
+赤黒木は平衡二分木であり、木に対する操作時に行われる操作によりノードの階層が平衡化される
+そのため各操作の最悪時間計算量O(logN)となり、二分木の中でも実用性を備えている。
+
+DataGearとなるのデータはkeyごとに作られたQueueに保存される、従ってQueueStoreとなる赤黒木にはkeyごとのQueueがノードとして保持される。
+図\ref{fig:GearsDGM}にファイルとなるDataGearManagerに対して任意のkeyに対してput/take操作を行う際の処理を示す。
+いずれの場合もStoreとなる赤黒木に対して任意のkeyのQueueのget操作を行い、そのQueueに対してputもしくはtake操作を行う。
+あくまでこのDGMはファイルに相当するものなので、
+赤黒木に含まれているQueueはInput/OutputStreamと実際にファイルデータを保持しておくmainDataQueueの三つとなる。
+しかし、WordCount例題のackや結果出力のようにStreamとなるkey以外を用いるために、ファイルに関連するkey以外にも任意にQueueを追加することもできる。
+任意のQueueを追加したい場合はStoreとなるTreeに対して、
+Treeが保持していないkeyへputが行われた場合は新しくそのkeyを持つQueueを生成しTreeに持たせる処理を追加すれば良い。
+
+図に示した手順のDataアクセスではファイルの呼び出しなどのDataGearの断続的な参照が行われる場合、
+Treeへの探索処理がボトルネックになってしまう可能性が考えられる。
+これは特定のkeyのQueueのアドレスをmain部分で直接行えるように、
+TreeにkeyのQueue自体のアドレスをOutputさせるAPIを記述することで解決が行えると考えられる。
+
+
+\begin{figure}[h]
+    \begin{center}
+        \includegraphics[width=180mm]{./images/GearsDGM.pdf}
+    \end{center}
+    \caption{GearsOSにおけるファイル(DGM)}
+    \label{fig:GearsDGM}
+\end{figure}
+
+
+
+
+
 \section{ディレクトリシステム}
 本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている。[論文No.]
 GearsFSのディレクトリシステムはUnixOSのディレクトリシステムと同じ仕組みを用いて再現することを試みている。
@@ -142,4 +235,5 @@
 \end{figure}
 
 
-\section{ChristieAPIによるWordCount}
+
+\section{sokcet付きQueueによるDataGearPool}
Binary file Paper/images/GearsDGM.graffle.graffle has changed
Binary file Paper/images/GearsDGM.pdf has changed
Binary file Paper/master_paper.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/LocalDGMQueue.cbc	Sat Jan 22 23:27:45 2022 +0900
@@ -0,0 +1,37 @@
+__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenEOF(...), __code whenError(...)){
+    int recv_size, send_size;
+    char recv_buf[BUF_SIZE], send_buf;
+
+    union Data* recv_data;
+    recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0);
+    if (recv_size == -1) {
+        printf("recv error\n");
+        goto exit_code();
+    }
+    if (recv_size == 0) {
+        printf("connection ended\n");
+    }
+
+
+    FileString* fileString = NEW(FileString);
+    fileString = recv_data;
+    if (fileString->EoF) == 1) {
+        send_buf = 0;
+        send_size = send(cQueue->socket, &send_buf, 1, 0);
+        if (send_size == -1) {
+            printf("send error\n");
+        }
+        close(cQueue->buffer);
+        goto whenEOF(...);
+    } else {
+        send_buf = 1;
+        send_size = send(cQueue->socket, &send_buf, 1, 0);
+        if (send_size == -1) {
+            printf("send error\n");
+            goto whenError(...);
+        }
+    }
+
+    Gearef(context, cQueue)->data = recv_data;
+    goto putLocalDGMQueue(recv_data, next);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/RemoteDGMQueue.cbc	Sat Jan 22 23:27:45 2022 +0900
@@ -0,0 +1,27 @@
+__code sendDataRemoteDGMQueue(struct RemoteDGMQueue* cQueue, union Data* data, __code next(...), __code whenError(...)){
+    char recv_buf;
+    int send_size, recv_size;
+
+    send_size = send(cQueue->socket, data, sizeof(union Data), 0);
+    if (send_size == -1) {
+        printf("send error\n");
+        close(cQueue->socket);
+        goto whenError();
+    }
+
+    recv_size = recv(cQueue->socket, &recv_buf, 1, 0);
+    if (recv_size == -1) {
+        printf("recv error\n");
+        close(cQueue->socket);
+        goto whenError();
+    } else if (recv_size == 0) {
+        printf("connection ended\n");
+        close(cQueue->socket);
+        goto whenError();
+    } else if(recv_buf == 0) {
+        printf("Finish connection\n");
+        close(cQueue->socket);
+        goto whenError();
+    }
+    goto next(...);
+}