Mercurial > hg > Papers > 2022 > ikki-master
changeset 20:55a0fd236f78
tweak
| author | ichikitakahiro <e165713@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 09 Feb 2022 22:26:31 +0900 |
| parents | 9e6fd2255ee1 |
| children | f8a089dbfe06 |
| files | .DS_Store Paper/chapter/3-GearsOS.tex Paper/chapter/5-Implementation.tex Paper/chapter/6-Evaluation.tex Paper/chapter/abstract.tex Paper/chapter/conclusion.tex Paper/chapter/history.tex Paper/images/.DS_Store Paper/images/cg-dg.graffle Paper/images/cg-dg.pdf Paper/master_paper.pdf Paper/master_paper.tex Paper/src/RedBlackTree.cbc Paper/src/missingParGoto.cbc master.mm slide/images/cg-dg.pdf slide/images/mindMap.png slide/thesis.html slide/thesis.md slide/thesis.pdf.html |
| diffstat | 20 files changed, 1495 insertions(+), 1426 deletions(-) [+] |
line wrap: on
line diff
--- a/Paper/chapter/3-GearsOS.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/chapter/3-GearsOS.tex Wed Feb 09 22:26:31 2022 +0900 @@ -158,7 +158,7 @@ \lstinputlisting[label=src:SynchronizedQueue.c, caption=SynchronizedQueue.c]{src/SynchronizedQueue.c} \section{SynchronizedQueue} -GearsOSには先行研究[先行研究リンク][SingleLinkedな穴蔵さんのやつも？]にてGearsシンタックスを用いて実装されたQueueが存在している。 +GearsOSには先行研究\cite{gears}にてGearsシンタックスを用いて実装されたQueueが存在している。 Queueは単純なQueueとしての機能を実装したSingleLinkedQueueと、 マルチスレッドによる複数のプロセスからのアクセスにも対応するためのSynchronizedQueueが存在する。
--- a/Paper/chapter/5-Implementation.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/chapter/5-Implementation.tex Wed Feb 09 22:26:31 2022 +0900 @@ -1,4 +1,4 @@ -\chapter{GearsFileSystem Implementation} +\chapter{GearsFileSystemの設計と実装} 本章ではGearsOSのFileSystem(以下GearsFS)の実装について解説する。 GearsOSのファイルは分散ファイルシステム的に大域的な資源として、 複数のプロセスから競合的なアクセスが可能を可能としたい。 @@ -97,7 +97,6 @@ ファイルの文字列がある間はputStringとCountUpをループし続け、 putStringはstrTableの中身がなくなった(EOF)ならshowResultへ遷移する形となる。 図\ref{fig:WordCount}にCGの遷移図を示す。 -このように特定の条件を満たすまであるCodeGear間をループ遷移する構成をGearBoxと名付けている。 \lstinputlisting[label=src:WcImpl, caption=Unixファイルに対するWordCount.cbcの一部]{src/WcImpl.cbc} @@ -109,15 +108,15 @@ \label{fig:WordCount} \end{figure} -\section{ChristieAPIによるWordCount} -GearsFSはChristieのLocalDataGearManagerとRemoteDataGearManagerによる通信の仕組みを用いてファイルデータの送受信を構成する。これをChristieAPIと呼ぶ。 +\section{GearsFile APIによるWordCount} +GearsFSはChristieのLocalDataGearManagerとRemoteDataGearManagerによる通信の仕組みを用いてファイルデータの送受信を構成する。これをGearsFile APIと呼ぶ。 ChrstieAPIではファイルをDataGearManagerと見なすことができ、 Local上にRemote先のファイルのploxyとなるRemoteDGMを作成し、 これに対しLocalのファイルへの書き込みと同様に操作を行うことで自動的に通信を行ってくれる。 -ChiristieのDataGearManagerの仕組みを基準としたChristieAPIによるWordCountの設計を行った。 -図\ref{fig:ChristieAPI}にChristieAPIによるWordCountを示す。 -ChristieAPIによるファイルデータ通信は2ペアのLocal/RemoteDGMを通して行われる。 +ChiristieのDataGearManagerの仕組みを基準としたGearsFile APIによるWordCountの設計を行った。 +図\ref{fig:GearsFile API}にGearsFile APIによるWordCountを示す。 +GearsFile APIによるファイルデータ通信は2ペアのLocal/RemoteDGMを通して行われる。 RemoteDGMは接続先のノードが持つLocalDGMのプロキシであり、RemoteDGMに対してput操作を行うことで、相手の持つLocalDGMへのデータの送信が行える。 NodeA側が任意のファイルを開き、ファイル内の行ごとの文字列をデータとしてNodeB側に対応するRemoteDGMにputする。 NodeB側は自身のLocalDGMからデータを得て、WordCountの処理を行ったのちに @@ -137,8 +136,8 @@ \begin{center} \includegraphics[width=150mm]{./images/wordCountDGM.jpg} \end{center} - \caption{ChristieAPIによるWordCount} - \label{fig:ChristieAPI} + \caption{GearsFile APIによるWordCount} + \label{fig:GearsFile API} \end{figure} @@ -146,7 +145,7 @@ RemoteDGMとLocalDGMの接続の際にはLocalDGMが持つsocketに対してRemoteDGMが接続を行い、 Dataの書き込み先のkeyを指定してsocket経由でコマンドとして送信する。 -socketを所有したQueueによるWordCount例題の記述を行うことでGearsOSにおけるsocketの取り扱いと実用性を検証した。 +socketを所有したQueueによるWordCount例題の記述を行うことでGearsOSにおけるsocket通信の実装を行った。 接続元と接続先のsocketは、Queueの作成時に行われ、 socketへのアクセスはQueueにCodeGearとして実装を行った。 ソースコード\ref{src:LDGMQueue}にLocalDGM側にあたる、Socket付きのQueueのCodeGear:getData部分を示す。 @@ -267,9 +266,11 @@ つまり、図中の黒いノード1から探索を行えば過去のデータのノードが参照でき、 赤いノード1から探索を行えば編集後の木構造を参照することができる。 -ファイル構造体のバックアップについては、ファイルのDataレコードをファイルの変更差分を履歴として保持させる形にすることに加え、 -変更日時を保持させることで可能となると考えられる。 -特定の時点のファイルとDirectoryの状態を呼び出す際は、レコードの変更日時を確認し、参照するべきTree構造とレコードを呼び出す形となる。 +ファイル構造体の変更履歴については、ファイルのDataレコードをファイルの変更差分を履歴として保持させる形にすることに加え、 +変更日時を記録させることで実現したい。 +diffコマンドようなファイル差分をレコードにすることにより、gitやMercurialのようなバージョン管理を行う。 +特定の時点のファイルとDirectoryの状態を呼び出す際は、レコードの変更日時を確認し、参照するべきTree構造とレコードの時点まで参照する形となる。 + 変更ログデータを定期的に任意または一定期間ごとに別のストレージに保存することでバックアップを実現する。 また、非破壊的木構造の編集と変更履歴式のデータレコードは変更が行われるたびに、ディレクトリTreeやファイルの容量増加していくという問題が存在する。 @@ -285,8 +286,8 @@ \end{figure} -\section{GearsFSの分散処理} -分散フレームワークChristieとGearsOSFileSystemにおける分散処理について考察する。 +\section{GearsFSの並列処理} +分散フレームワークChristieとGearsOSFileSystemにおける並列処理について考察した。 GearsFSではファイルはDataGearのリストとして実装される。 ファイルの読み取り書き込みを含めた通信はDataGearリストにある特定のkeyのDataGearのQueueに対してDataを書き込み、 もしくは呼び出しを行うことで実現される。 @@ -294,12 +295,12 @@ GearsFSのファイルはChristieのDataGearManagerの仕組みを参考にするものであるが、ChristieのDGMとの明確な違いとして、 GearsFSのDGMはChristieのようにDataGearの差し込みによる通信を構成するだけの用途でなく、ファイルそのものとしての用途を持つという点が存在する。 -そのため、ChristieDGMのように一つのスレッド(CGM)により管理されるものではなく、複数のスレッドから競合的にアクセスが行われるDGMである。 +そのため、ChristieDGMのように一つのノード(CGM)により管理されるものではなく、複数のプロセスから競合的にアクセスが行われるDGMである。 よってDataGearを保持するQueueは純粋なQueueでなく複数のアクセスが行われても、 データの整合性が保たれるSynchronizedなQueueを用いる必要が生じる場面がある。 -Christieのでは分散されたTask(CodeGear)はCodeGearManagerにより実行が行われる。 -GearsFSでは分散処理をCodeGearManagerを用いた実装に代わり、GearsOSに搭載されたpar gotoを利用するという手段が考えられる。 +ChristieのではTask(CodeGear)はCodeGearManagerにより実行が行われる。 +GearsFSでは並列処理をCodeGearManagerを用いた実装に代わり、GearsOSに搭載されたpar gotoを利用するという手段が考えられる。 par gotoとはGearsOSにおける並列処理構文である。 par gotoによる並列処理ではTaskをContextで表現し、TaskのInputDataGearが揃ったTaskをWorkerで処理を行う。 図\ref{fig:WorkerRun}にpar goto構文による並列処理を示す。
--- a/Paper/chapter/6-Evaluation.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/chapter/6-Evaluation.tex Wed Feb 09 22:26:31 2022 +0900 @@ -68,4 +68,5 @@ \lstinputlisting[label=src:mainDist, caption=takeCodeGearから遷移されるstubCodeGear]{src/mainDist.cbc} +\newpage{} \lstinputlisting[label=src:misspar, caption=自動生成にて出力されたTask3のstubCodeGear]{src/missingParGoto.cbc}
--- a/Paper/chapter/abstract.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/chapter/abstract.tex Wed Feb 09 22:26:31 2022 +0900 @@ -11,7 +11,6 @@ 従来のファイルシステムの問題点の一部として、ファイルシステムはデータベースでなくレコード単位での操作が行えない、バックアップや証明書などの機能はアプリケーションに依存している点などが挙げられる。 将来的な実装を鑑みてファイルシステムの実装を行う。 - また、GearsOSを純粋に利用して記述を行うプロジェクトは本研究が初めてとなる。 分散ファイルシステムの構成を行うと同時に、GearsOSの言語フレームワークとしての評価と検討を行った。
--- a/Paper/chapter/conclusion.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/chapter/conclusion.tex Wed Feb 09 22:26:31 2022 +0900 @@ -26,7 +26,9 @@ しかしChristieのTopologyManagerはあくまで分散フレームワークであるChristieに向けて開発されたものである。 そのため、ChristieのTopologyManagerを基準にしながら、分散ファイルシステムに向けた仕様を考案していく必要がある。 例えば、TopologyManagerは参加を表明したノードを任意の形のTopologyに構成するというものだが、 -CodeGearManagerの存在しないGearsFSでは、RemoteDGMによる通信接続に加え、要求されたファイルを見つけ出しメモリ上へ呼び出すという機能を加える必要がある。 +CodeGearManagerの存在しないGearsFSでは、RemoteDGMによる通信接続に加え、 +DNSシステムによるファイルの呼び出しなど通信Topologyの中枢としての役割を持たせたい。 + ファイルシステムの基幹となるディレクトリやファイル通信の設計は行えている。 しかし、実際にファイルシステムとして十分な運用が行えるようになるまでの課題は多く存在している。
--- a/Paper/chapter/history.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/chapter/history.tex Wed Feb 09 22:26:31 2022 +0900 @@ -1,5 +1,5 @@ \chapter*{発表履歴} \begin{itemize} -\item 一木 貴裕, 河野 真治. 分散フレームワークChristirによるBlock chainの実装. 情報処理学会 システムソフトウェアとオペレーティング・システム研究会 (OS), May, 2020 +\item 一木 貴裕, 河野 真治. 分散フレームワークChristirによるBlock chainの実装. 情報処理学会 システムソフトウェアとオペレーティング・システム研究会 (OS), May, 2019 \item 一木 貴裕, 河野 真治. GearsOSの分散ファイルシステムの設計. 情報処理会 システムソフトウェアとオペレーティング・システム研究会（OS）, May, 2021 \end{itemize}
--- a/Paper/master_paper.tex Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/master_paper.tex Wed Feb 09 22:26:31 2022 +0900 @@ -19,8 +19,8 @@ \eyear{March 2022} \author{一木 貴裕} \eauthor{Ikki Takahiro} -\chife{指導教員：教授 和田 知久} -\echife{Supervisor: Prof. Tomohisa Wada} +\chife{指導教員：教授 山田 孝治} +\echife{Supervisor: Prof. Yamada Koji} \marklefthead{% 左上に挿入 \begin{minipage}[b]{.4\textwidth}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Paper/src/RedBlackTree.cbc Wed Feb 09 22:26:31 2022 +0900 @@ -0,0 +1,602 @@ +#include <stdio.h> + +#include "../context.h" +#interface "Tree.h" +#interface "Stack.h" + +extern enum Relational compare(struct Node* node1, struct Node* node2); + +Tree* createRedBlackTree(struct Context* context) { + struct Tree* tree = new Tree(); + struct RedBlackTree* redBlackTree = new RedBlackTree(); + tree->tree = (union Data*)redBlackTree; + redBlackTree->root = NULL; + redBlackTree->nodeStack = createSingleLinkedStack(context); + tree->put = C_putRedBlackTree; + tree->get = C_getRedBlackTree; + tree->remove = C_removeRedBlackTree; + // tree->clear = C_clearRedBlackTree; + return tree; +} + +void printTree1(union Data* data) { + struct Node* node = &data->Node; + if (node == NULL) { + printf("NULL"); + } else { + printf("key = %d (", node->key); + printTree1((union Data*)(node->right)); + printf("), ("); + printTree1((union Data*)(node->left)); + printf(")"); + } +} + +void printTree(union Data* data) { + printTree1(data); + printf("\n"); +} + +__code putRedBlackTree(struct RedBlackTree* tree, struct Node* node) { + struct Node* newNode = &ALLOCATE(context, Node)->Node; + struct Node* root = tree->root; + //printTree((union Data*)(tree->root)); + tree->newNode = newNode; + tree->root = newNode; // this should done at stackClear + tree->parent = NULL; + if (root) { + tree->current = root; + tree->result = compare(tree->current, node); + tree->findNodeNext = C_insertNode; + goto findNode(tree); + } + goto insertNode(tree, node); +} + +__code findNode(struct RedBlackTree* tree) { + struct Stack* nodeStack = tree->nodeStack; + struct Node* oldNode = tree->current; + struct Node* newNode = tree->newNode; + tree->previous = newNode; + *newNode = *oldNode; + goto nodeStack->push((union Data*)newNode, findNode1); +} + +__code findNode1(struct RedBlackTree* tree, struct Node* node, __code next(...)) { + struct Node* oldNode = tree->current; + struct Node* newNode = tree->previous; + struct Node* newnewNode = &ALLOCATE(context, Node)->Node; + int result = tree->result; + if (result == EQ) { + newNode->value = node->value; + // go to stack clear + goto next(...); + } else if (result == GT) { + tree->current = oldNode->right; + newNode->right = newnewNode; + } else { + tree->current = oldNode->left; + newNode->left = newnewNode; + } + tree->newNode = newnewNode; + if (tree->current) { + tree->result = compare(tree->current, node); + goto findNode(tree); + } + goto meta(context, tree->findNodeNext); + // gato tree->findNodeNext(tree, node); + +} + +__code insertNode(struct RedBlackTree* tree, struct Node* node) { + struct Stack* nodeStack = tree->nodeStack; + struct Node* newNode = tree->newNode; + *newNode = *node; + newNode->color = Red; + tree->current = newNode; + goto nodeStack->get2(insertCase1); +} + +__code insertCase1(struct RedBlackTree* tree, struct Node *parent, struct Node *grandparent) { + if (parent != NULL) { + tree->parent = parent; + tree->grandparent = grandparent; + goto insertCase2(tree); + } + tree->root->color = Black; + goto stackClear(); +} + +__code insertCase1_stub(struct Context* context) { + goto insertCase1(context, + &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, + &context->data[D_Stack]->Stack.data->Node, + &context->data[D_Stack]->Stack.data1->Node); +} + +__code insertCase2(struct RedBlackTree* tree) { + if (tree->parent->color == Black) { + goto stackClear(); + } + goto insertCase3(tree); +} + +__code insertCase3(struct RedBlackTree* tree) { + struct Stack* nodeStack = tree->nodeStack; + struct Node* uncle; + + if (tree->grandparent->left == tree->parent) { + uncle = tree->grandparent->right; + } else { + uncle = tree->grandparent->left; + } + + if (uncle && (uncle->color == Red)) { + // do insertcase1 on grandparent, stack must be pop by two + tree->parent->color = Black; + uncle->color = Black; + tree->grandparent->color = Red; + tree->current = tree->grandparent; + goto nodeStack->pop2(insertCase1); + } + goto insertCase4(); +} + +__code insertCase4(struct RedBlackTree* tree, struct RotateTree* rotateTree) { + struct Stack* nodeStack = tree->nodeStack; + + if ((tree->current == tree->parent->right) && (tree->parent == tree->grandparent->left)) { + tree->current = tree->current->left; + tree->parent = tree->grandparent; + + rotateTree->traverse = tree; + rotateTree->next = C_insertCase5; + + goto nodeStack->pop(rotateLeft); + } else if ((tree->current == tree->parent->left) && (tree->parent == tree->grandparent->right)) { + tree->parent = tree->grandparent; + tree->current = tree->current->right; + + rotateTree->traverse = tree; + rotateTree->next = C_insertCase5; + + goto nodeStack->pop(rotateRight); + } + + goto insertCase5(); +} + +__code insertCase5(struct RedBlackTree* tree) { + struct Stack* nodeStack = tree->nodeStack; + goto nodeStack->pop2(insertCase51); +} + +__code insertCase51(struct RedBlackTree* tree, struct RotateTree* rotateTree, struct Node* parent, struct Node* grandparent) { + struct Node* current = tree->current; + tree->parent = parent; + tree->grandparent = grandparent; + + parent->color = Black; + grandparent->color = Red; + + tree->current = grandparent; + + rotateTree->traverse = tree; + rotateTree->next = C_stackClear; + + if ((current == parent->left) && (parent == grandparent->left)){ + goto rotateRight(); + } else { + goto rotateLeft(); + } +} + +__code insertCase51_stub(struct Context* context) { + struct Node* parent = &context->data[D_Stack]->Stack.data->Node; + struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node; + goto insertCase51(context, + &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, + Gearef(context, RotateTree), + parent, + grandparent); +} + +__code rotateLeft(struct RedBlackTree* tree) { + struct Stack* nodeStack = tree->nodeStack; + goto nodeStack->get(rotateLeft1); +} + +__code rotateLeft_stub(struct Context* context) { + struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; + goto rotateLeft(context, traverse); +} + +__code rotateLeft1(struct Node* node, struct RedBlackTree* tree, struct Node* parent, struct RotateTree* rotateTree) { + struct Node* tmp = node->right; + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + tree->root = tmp; + } + + node->right = tmp->left; + tmp->left = node; + tree->current = tmp; + + goto meta(context, rotateTree->next); +} + +__code rotateLeft1_stub(struct Context* context) { + struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; + struct Node* parent = &context->data[D_Stack]->Stack.data->Node; + goto rotateLeft1(context, + traverse->current, + traverse, + parent, + Gearef(context, RotateTree)); +} + +__code rotateRight(struct RedBlackTree* tree) { + struct Stack* nodeStack = tree->nodeStack; + goto nodeStack->get(rotateRight1); +} + +__code rotateRight_stub(struct Context* context) { + struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; + goto rotateLeft(context, traverse); +} + +__code rotateRight1(struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) { + struct Node* tmp = node->left; + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + traverse->root = tmp; + } + + node->left = tmp->right; + tmp->right = node; + traverse->current = tmp; + + goto meta(context, rotateTree->next); +} + +__code rotateRight1_stub(struct Context* context) { + struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; + struct Node* parent = &context->data[D_Stack]->Stack.data->Node; + goto rotateRight1(context, + traverse->current, + traverse, + parent, + Gearef(context, RotateTree)); +} + +__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) { + tree->current = 0; + nodeStack->stack = (union Data*)tree->nodeStack; + nodeStack->next = next; + goto meta(context, tree->nodeStack->clear); +} + +__code getRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) { + if (tree->root) { + tree->current = tree->root; + + goto search(node); + } + + goto next(...); +} + +__code search(struct RedBlackTree* tree, struct Node* node, __code next(...)) { + // compare(context, traverse, traverse->current->key, node->key); + tree->result = compare(tree->current, node); + if (tree->result == EQ) { + *node = *tree->current; + + goto meta(context, next); + } else if (tree->result == GT) { + tree->current = tree->current->right; + } else { + tree->current = tree->current->left; + } + + if (tree->current) { + goto meta(context, C_search); + } + + goto next(...); +} + + +__code removeRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) { + struct Node* newNode = &ALLOCATE(context, Node)->Node; + struct Node* root = tree->root; + printTree((union Data*)(tree->root)); + tree->newNode = newNode; + tree->root = newNode; // this should done at stackClear + tree->parent = NULL; + if (root) { + tree->current = root; + tree->result = compare(tree->current, node); + tree->findNodeNext = C_replaceNodeForDelete2; + goto findNode(tree); + } + goto next(...); +} + + + +__code delete2(struct Node* current) { + if (current->color == Black) { + struct Node* child = current->right == NULL ? current->left : current->right; + current->color = child == NULL ? Black : child->color; + + goto deleteCase1(current); + } + + goto delete3(tree, current); +} + + + +__code delete3(struct RedBlackTree* tree, struct Node* current, __code next(...)) { + struct Node* tmp = current->right == NULL ? current->left : current->right; + struct Stack* nodeStack = tree->nodeStack; + + if (tree->parent) { + if (current == tree->parent->left) + tree->parent->left = tmp; + else + tree->parent->right = tmp; + } else { + tree->root = tmp; + } + + + if (tree->parent == NULL && tmp) { + tmp->color = Black; + } + + current == tree->parent->left ? (tree->parent->left = NULL) : (tree->parent->right = NULL); + + Gearef(context, Stack)->stack = (union Data*) nodeStack; + Gearef(context, Stack)->next = next; + goto meta(context, nodeStack->pop); + +// gato nodeStack->pop(next); +} + + + +__code replaceNodeForDelete2(struct RedBlackTree* tree, struct Node* newNode) { + if (tree->current->left && tree->current->right) { + tree->parent = newNode; + tree->current = newNode->left; + newNode->left = context->heap; + + + tree->parent = newNode; + + goto findMax1(tree,oldNode, newNode); + } + + goto delete2(current); +} + + +__code findMax1(struct RedBlackTree* tree, struct Node* oldNode, struct Node* newNode) { + *newNode = *oldNode; + + if (newNode->right) { + goto findMax2(tree, oldNode, newNode); + } + + tree->current = newNode; + + goto delete2(current); +} + + + + +__code findMax2(struct RedBlackTree* tree, struct Node* oldNode, struct Node* newNode) { + *newNode = *oldNode; + + if (newNode->right->right) { + tree->current = newNode->right; + newNode->right = context->heap; + + tree->parent = newNode; + + goto findMax2(tree, oldNode, newNode); + } + + tree->current = newNode; + + goto delete2(tree,current); +} + + +__code deleteCase1(struct RedBlackTree* tree, struct Node* current) { + if (tree->parent) { + goto deleteCase2(tree,current); + } + + goto delete3(tree, current); +} + + + +__code deleteCase2(struct RedBlackTree* tree, struct Node* current, struct RotateTree* rotateTree) { + struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left; + struct Stack* nodeStack = tree->nodeStack; + + if ((sibling == NULL ? Black : sibling->color) == Red) { + tree->parent->color = Red; + sibling->color = Black; + + current == tree->parent->left ? (tree->parent->left = context->heap) : (tree->parent->right = context->heap); + + struct Node* node = sibling; + + tree->current = tree->parent; + + rotateTree->traverse = tree; + rotateTree->next = C_deleteCase3; + + if (current == tree->parent->left) { + goto nodeStack->push((union Data*)node,rotateLeft); + } else { + goto nodeStack->push((union Data*)node,rotateRight); + } + + goto deleteCase3(tree,current); + } +} + + + +__code deleteCase3(struct RedBlackTree* tree, struct Node* current) { + struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left; + + if (tree->parent->color == Black && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Black && + (sibling->right == NULL ? Black : sibling->right->color) == Black) { + sibling->color = Red; + + tree->current = tree->parent; + goto deleteCase1(current); + } + + goto deleteCase4(current); +} + + + +__code deleteCase4(struct RedBlackTree* tree,struct Node* current) { + struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left; + + if (tree->parent->color == Red && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Black && + (sibling->right == NULL ? Black : sibling->right->color) == Black) { + sibling->color = Red; + tree->parent->color = Black; + + goto delete3(tree,current); + } + + goto deleteCase5(tree,current); +} + + + +__code deleteCase5(struct RedBlackTree* tree, struct Node* current, struct RotateTree* rotateTree) { + struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left; + struct Stack* nodeStack = tree->nodeStack; + // sibling->parent = tree->parent; + + if (current == tree->parent->left && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Red && + (sibling->right == NULL ? Black : sibling->right->color) == Black) { + sibling->color = Red; + sibling->left->color = Black; + + // sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); + sibling == tree->parent->left ? (tree->parent->left = context->heap) : (tree->parent->right = context->heap); + + struct Node* node = new Node(); + node = sibling->left; + + struct Node* tmp = node; + *tmp = *sibling; + tree->parent = current; + + tmp->left = context->heap; +/* struct Node* node = new Node(); */ +/* node = *sibling->left; */ + tree->parent = tmp; + + tree->current = tmp; + + + rotateTree->traverse = tree; + rotateTree->next = C_deleteCase6; + + goto nodeStack->push((union Data*)node,rotateRight); + } else if (current == tree->parent->right && + (sibling == NULL ? Black : sibling->color) == Black && + (sibling->left == NULL ? Black : sibling->left->color) == Black && + (sibling->right == NULL ? Black : sibling->right->color) == Red) { + sibling->color = Red; + sibling->right->color = Black; + + sibling == tree->parent->left ? (tree->parent->left = context->heap) : (tree->parent->right = context->heap); + + struct Node* node = new Node(); + node = sibling->right; + + struct Node* tmp = node; + *tmp = *sibling; + // tmp->parent = current; + + tmp->right = context->heap; +/* struct Node* node = new Node(); */ +/* node = *sibling->right; */ + //node->parent = tmp; + + tree->current = tmp; + + + rotateTree->traverse = tree; + rotateTree->next = C_deleteCase6; + + goto nodeStack->push((union Data*)node,rotateLeft); + } + + goto deleteCase6(tree,current); +} + + +__code deleteCase6(struct RedBlackTree* tree, struct Node* current, struct RotateTree* rotateTree) { + struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left; + struct Stack* nodeStack = tree->nodeStack; + sibling == tree->parent->left ? (tree->parent->left = context->heap) : (tree->parent->right = context->heap); + + struct Node* tmp = sibling; + // *tmp = *sibling; + tree->parent = current; + + tmp->color = tree->parent->color; + tree->parent->color = Black; + + + if (current == tree->parent->left) { + tmp->right->color = Black; + tree->current = tree->parent; + + rotateTree->traverse = tree; + rotateTree->next = C_delete3; + + goto nodeStack->push((union Data*)tmp,rotateLeft); + } else { + tmp->left->color = Black; + tree->current = tree->parent; + + rotateTree->traverse = tree; + rotateTree->next = C_delete3; + + goto nodeStack->push((union Data*)tmp,rotateLeft); + } +}
--- a/Paper/src/missingParGoto.cbc Mon Feb 07 20:58:17 2022 +0900 +++ b/Paper/src/missingParGoto.cbc Wed Feb 09 22:26:31 2022 +0900 @@ -11,7 +11,7 @@ context->task->maxIdg = context->task->idg + 1; context->task->odg = context->task->maxIdg; context->task->maxOdg = context->task->odg + 0; - GET_META(0)->wait = createSynchronizedQueue(context); +## GET_META(0)->wait = createSynchronizedQueue(context); //GET_META(countUp)->wait = createSynchronizedQueue(context); Gearef(context->task, CountUp)->countUp = (union Data*) countUp; Gearef(context->task, CountUp)->num = (union Data*) 0; @@ -21,23 +21,6 @@ element->next = context->taskList; context->taskList = element; - context->task = NEW(struct Context); - initContext(context->task); - context->task->next = countUp2->eNum; - context->task->idgCount = 1; - context->task->idg = context->task->dataNum; - context->task->maxIdg = context->task->idg + 1; - context->task->odg = context->task->maxIdg; - context->task->maxOdg = context->task->odg + 0; - GET_META(0)->wait = createSynchronizedQueue(context); - //GET_META(countUp2)->wait = createSynchronizedQueue(context); - Gearef(context->task, CountUp)->countUp = (union Data*) countUp2; - Gearef(context->task, CountUp)->num = (union Data*) 0; - Gearef(context->task, CountUp)->next = C_test; - element = &ALLOCATE(context, Element)->Element; - element->data = (union Data*)context->task; - element->next = context->taskList; - context->taskList = element; Gearef(context, TaskManager)->taskList = context->taskList; Gearef(context, TaskManager)->next1 = C_code2;
--- a/master.mm Mon Feb 07 20:58:17 2022 +0900 +++ b/master.mm Wed Feb 09 22:26:31 2022 +0900 @@ -1,6 +1,6 @@ <map version="1.0.1"> <!-- To view this file, download free mind mapping software FreeMind from http://freemind.sourceforge.net --> -<node CREATED="1619092826941" ID="ID_1216552110" MODIFIED="1637826202322" TEXT="File sytem api and implementaions of
Gears OS"> +<node CREATED="1619092826941" ID="ID_1216552110" MODIFIED="1644318991492" TEXT="File sytem api and implementaions of
Gears OS"> <node CREATED="1620021507022" ID="ID_1292875411" MODIFIED="1639654933865" POSITION="right" TEXT="研究目的"> <node CREATED="1620021756032" ID="ID_856611637" MODIFIED="1637826345416" TEXT="OSのファイルシステムについての話"> <arrowlink DESTINATION="ID_856611637" ENDARROW="Default" ENDINCLINATION="0;0;" ID="Arrow_ID_1566811280" STARTARROW="None" STARTINCLINATION="0;0;"/> @@ -499,5 +499,64 @@ </node> <node CREATED="1639652420457" ID="ID_1611056721" MODIFIED="1639652424905" TEXT="結論"/> </node> +<node CREATED="1644318991451" ID="ID_867291976" MODIFIED="1644318991451" POSITION="left" TEXT=""> +<node CREATED="1644318975258" HGAP="10" ID="ID_820337769" MODIFIED="1644319023040" TEXT="プレゼン" VSHIFT="111"> +<node CREATED="1644318998218" ID="ID_875318355" MODIFIED="1644319045533" TEXT="GearsOSのファイルシステムの設計と実装"/> +<node CREATED="1644319049338" ID="ID_1582565964" MODIFIED="1644319055504" TEXT="GearsOS"> +<node CREATED="1644319059291" ID="ID_1134665398" MODIFIED="1644319074395" TEXT="CodeGear"> +<node CREATED="1644320108252" ID="ID_736099080" MODIFIED="1644320110534" TEXT="goto"/> +</node> +<node CREATED="1644319074901" ID="ID_1093823552" MODIFIED="1644319078654" TEXT="DataGear"/> +<node CREATED="1644319784240" ID="ID_876571639" MODIFIED="1644319786652" TEXT="Interface"/> +<node CREATED="1644320155931" ID="ID_289693313" MODIFIED="1644320159807" TEXT="(CbC)"/> +</node> +<node CREATED="1644319086234" ID="ID_204611482" MODIFIED="1644319089997" TEXT="メタ計算"> +<node CREATED="1644319093354" ID="ID_1856162831" MODIFIED="1644319102308" TEXT="metaCodeGear"/> +<node CREATED="1644319102612" ID="ID_1647691605" MODIFIED="1644319107849" TEXT="metaDataGear"/> +</node> +<node CREATED="1644319114453" ID="ID_711122304" MODIFIED="1644319472042" TEXT="設計方針"> +<node CREATED="1644319198315" ID="ID_383033123" MODIFIED="1644319205164" TEXT="DataGear単位のトランザクション"/> +<node CREATED="1644319752335" ID="ID_455665151" MODIFIED="1644319945028" TEXT="DataGearManagerInterface"> +<node CREATED="1644319205702" ID="ID_18115554" MODIFIED="1644319208995" TEXT="Take"/> +<node CREATED="1644319209349" ID="ID_1615952526" MODIFIED="1644319210593" TEXT="Put"/> +<node CREATED="1644319210969" ID="ID_1200065842" MODIFIED="1644319242851" TEXT="Peek"/> +</node> +<node CREATED="1644319946626" ID="ID_978720557" MODIFIED="1644319951874" TEXT="LocalDGM"/> +<node CREATED="1644319952335" ID="ID_1132560379" MODIFIED="1644319957528" TEXT="RemoteDGM"/> +<node CREATED="1644319965727" ID="ID_1930183706" MODIFIED="1644319969155" TEXT="Chrsitie"/> +</node> +<node CREATED="1644319472552" ID="ID_1778897268" MODIFIED="1644319487160" TEXT="2段階の実装"> +<node CREATED="1644319495257" ID="ID_1244070690" MODIFIED="1644319511135" TEXT="シングルQueueによる実装"/> +<node CREATED="1644319502738" ID="ID_369807182" MODIFIED="1644319525018" TEXT="赤黒木とkeyを用いての実装"/> +</node> +<node CREATED="1644319355743" ID="ID_362519411" MODIFIED="1644319360617" TEXT="ノーマルレベルAPI"/> +<node CREATED="1644319055795" ID="ID_1785949602" MODIFIED="1644335708643" TEXT="メタレベルでの実装"/> +<node CREATED="1644319380361" ID="ID_855729832" MODIFIED="1644319396282" TEXT="WordCountの例題"/> +<node CREATED="1644319579634" ID="ID_1059126630" MODIFIED="1644319586148" TEXT="実装ずみの機能"> +<node CREATED="1644319588435" ID="ID_1521091760" MODIFIED="1644319595342" TEXT="シングルQueue"/> +<node CREATED="1644319606065" ID="ID_1946049504" MODIFIED="1644319614146" TEXT="inode baseなディレクトリ"> +<node CREATED="1644320076170" ID="ID_1736487979" MODIFIED="1644320081059" TEXT="またゆーくん"/> +</node> +<node CREATED="1644319614883" ID="ID_1457833053" MODIFIED="1644319629741" TEXT="socketを用いた通信"/> +</node> +<node CREATED="1644319535657" ID="ID_537948009" MODIFIED="1644319558142" TEXT="未実装な機能"> +<node CREATED="1644319564117" ID="ID_1965424929" MODIFIED="1644319570861" TEXT="ファイルへの書き込み"/> +<node CREATED="1644319644615" ID="ID_960415053" MODIFIED="1644319652526" TEXT="keyを用いた複数stream"/> +<node CREATED="1644319655019" ID="ID_315963166" MODIFIED="1644319656708" TEXT="peek"/> +<node CREATED="1644319664159" ID="ID_1952202029" MODIFIED="1644319669355" TEXT="メモリ管理"/> +<node CREATED="1644319672813" ID="ID_572761035" MODIFIED="1644319676043" TEXT="バックアップ"/> +</node> +<node CREATED="1644319684270" ID="ID_964727604" MODIFIED="1644319819015" TEXT="まとめ"> +<node CREATED="1644319693185" ID="ID_364033723" MODIFIED="1644319704864" TEXT="GearsOSのファイルシステムを設計"/> +<node CREATED="1644319705539" ID="ID_1830006544" MODIFIED="1644319709918" TEXT="一部の実装"/> +</node> +<node CREATED="1644319819842" ID="ID_636928469" MODIFIED="1644319823033" TEXT="将来の課題"> +<node CREATED="1644319824679" ID="ID_1269749492" MODIFIED="1644319873644" TEXT="自律分散システム"> +<node CREATED="1644319875984" ID="ID_921141997" MODIFIED="1644319880249" TEXT="TopologyManager"/> +<node CREATED="1644319880491" ID="ID_500327016" MODIFIED="1644319886915" TEXT="SecurityManager"/> +</node> +</node> +</node> +</node> </node> </map>
--- a/slide/thesis.html Mon Feb 07 20:58:17 2022 +0900 +++ b/slide/thesis.html Wed Feb 09 22:26:31 2022 +0900 @@ -91,42 +91,20 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsosとその現状">GearsOSとその現状</h2> +<h2 id="gearsosのファイルシステム設計">GearsOSのファイルシステム設計</h2> <ul> - <li>信頼性の保証と拡張性の高さを目指したOSプロジェクト</li> - <li>軽量継続を用いた言語、CbC(Continuation based C)により記述される</li> - <li>ノーマルレベルとメタレベルを分離して記述する</li> - <li>現状では言語フレームワークとしてのみ機能する</li> - <li>OSとして動作するには多くの機能の開発が必要 + <li>GearsOSには現時点でファイルシステムが存在していない</li> + <li>GearsOSのファイルシステムの設計と実装を行った</li> + <li>GearsOSの特性に合わせた実装 <ul> - <li>その中の一つにファイルシステムが挙げられる</li> + <li>CodeGear/DataGearによる継続処理</li> + <li>同じくGear概念を持つ分散フレームワークChristieの仕組みを用いた</li> </ul> </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="従来の物より発展した分散ファイルシステムの設計">従来の物より発展した分散ファイルシステムの設計</h2> -<ul> - <li>データベース的なレコード操作によるアクセス + <li>将来的に重要な機能をOSに取り込みたい <ul> - <li>ファイルに対する全ての操作がTransactionとなる</li> - </ul> - </li> - <li>既存ではアプリケーションが担当する機能を取り込む - <ul> - <li>バックアップの管理</li> - <li>ファイルの型の認識</li> - </ul> - </li> - <li>自律分散を目指した分散ファイルシステム - <ul> - <li>特定のサーバーを中枢にしなくても良い</li> - <li>分散フレームワークChristieの仕組みにより実現する</li> + <li>バックアップ</li> + <li>ファイルの型認識</li> </ul> </li> </ul> @@ -137,15 +115,14 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="cbc-continuation-based-c">CbC (Continuation based C)</h2> +<h2 id="gearsos">GearsOS</h2> <ul> - <li>C言語の拡張言語である</li> - <li>関数に代わる軽量継続をメインに記述する</li> - <li>Gearというプログラム概念 + <li>関数でなくGearという単位を用いて記述する <ul> <li>CodeGear <ul> <li>従来のThreadにあたる</li> + <li>goto文(jump命令)を使って遷移する</li> </ul> </li> <li>DataGear @@ -153,14 +130,15 @@ <li>従来の変数データにあたる</li> </ul> </li> + <li>スタックを持たないため軽量継続と呼ぶ</li> </ul> </li> - <li>DataGearを受け取り処理を行う(InputDataGear)</li> - <li>処理の結果をDataGearに書き出す(OutputDataGear)</li> + <li>CodeGearは処理を行う際、DataGearを参照し処理を行う(InputDataGear)</li> + <li>CodeGearは処理の終了後、以降に必要なデータをDataGearとして出力する(OutputDataGear)</li> </ul> <div style="text-align: center;"> - <img src="images/cgdg.pdf" alt="CodeGearとDataGearの関係" width="800" /> + <img src="images/cg-dg.pdf" alt="cgdgの関係図" width="800" /> </div> @@ -169,23 +147,26 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="cbcのサンプルプログラム">CbCのサンプルプログラム</h2> -<pre><code>__code CG2(int num3){ - printf("num = %d\n", num3); - exit(0); -} - -__code CG1(int num, int num1){ - int num2 = num + num1; - goto CG2(num2); -} - -int main(){ - int a = 2; - int b = 3; - goto CG1(a, b); -} +<h2 id="gearsosのinterface">GearsOSのInterface</h2> +<ul> + <li>APIの宣言を行う + <ul> + <li>定義ファイル(.h)に記述を行う</li> + <li>APIとなるCodeGearとその参照するDataGearを宣言する</li> + <li>DataGear/CodeGearの一時的な置き場としての役割を持つ + <pre><code>typedef struct Tree<>{ +union Data* tree; +struct Node* node; +__code put(Impl* tree,Type* node, __code next(...)); +__code get(Impl* tree, Type* node, __code next(...)); +__code remove(Impl* tree,Type* node, __code next(...)); +__code next(...); +} Tree; </code></pre> + </li> + </ul> + </li> +</ul> @@ -211,9 +192,8 @@ </li> </ul> </li> - <li>ユーザーが記述する上では普段は意識しない</li> + <li>メタレベルの処理はトランスコンパイラにより自動に記述される</li> </ul> - <div style="text-align: center;"> <img src="images/meta-cg-dg.pdf" alt="ノーマルレベルとメタレベルの視点からのGearの関係" width="800" /> </div> @@ -224,143 +204,14 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsosの構成">GearsOSの構成</h2> +<h2 id="datagear単位のトランザクション">DataGear単位のトランザクション</h2> <ul> - <li>Interface - <ul> - <li>定義ファイル(.h)に記述を行う</li> - <li>APIとなるCodeGearとその参照するDataGearを宣言する</li> - <li>コンパイル時にContext(後述)に書き込まれる</li> - </ul> - </li> - <li>Implement - <ul> - <li>Interfaceの実装</li> - <li>プログラム内で共通して利用したい変数</li> - </ul> - </li> -</ul> - -<pre><code>typedef struct Queue<>{ - union Data* queue; - union Data* data; - - __code whenEmpty(...); - __code clear(Impl* queue, __code next(...)); - __code put(Impl* queue, union Data* data, __code next(...)); - __code take(Impl* queue, __code next(union Data* data, ...)); - __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); - __code next(...); -} Queue; -</code></pre> -<pre><code>typedef struct SynchronizedQueue <> impl Queue { - struct Element* top; - struct Element* last; - struct Atomic* atomic; -} SynchronizedQueue; -</code></pre> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="contextとgearの関係性">ContextとGearの関係性</h2> -<ul> - <li>Context - <ul> - <li>遷移の際にデータを全て記録するオブジェクト</li> - <li>プログラムに使われるCodeGear/DataGearを管理する</li> - <li>軽量継続中、必ず引数で参照される</li> - <li>メタレベルなCodeGearからのみ参照される</li> - </ul> - </li> -</ul> -<div style="text-align: center;"> - <img src="images/Context_ref.pdf" alt="Contextの参照" width="900" /> -</div> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsosのトランスコンパイラ">GearsOSのトランスコンパイラ</h2> -<ul> - <li>CbCプログラムはトランスコンパイルによりC言語プログラムに書き換えられる + <li>GearsOSはDataGear単位でプロセスが進行する</li> + <li>従来のファイルシステムは一部の操作のみがTransactionとなっている</li> + <li>GearsOSのファイルシステムはDataGear単位で処理を行いたい <ul> - <li>トランスコンパイルの際に、メタレベルの記述が行われる - <ul> - <li>StubCodeGearの自動生成</li> - <li>Gears向けに記述された演算子(par goto、NEW)の書き換え</li> - </ul> - </li> - </ul> - </li> - <li>StubCodeGearはCbCプログラムへ直に記述することでユーザーの任意の処理に変えられる - <pre><code>__code putSynchronizedQueue_stub(struct Context* context) { - SynchronizedQueue* queue = (SynchronizedQueue*)GearImpl(context, Queue, queue); - Data* data = Gearef(context, Queue)->data; - enum Code next = Gearef(context, Queue)->next; - goto putSynchronizedQueue(context, queue, data, next); -} -</code></pre> - <pre><code>__code putSynchronizedQueue(struct Context *context,struct SynchronizedQueue* queue, -union Data* data, enum Code next) { - ~省略~ -} -</code></pre> - </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="分散フレームワークchristie">分散フレームワークChristie</h2> -<ul> - <li>Java言語で記述された分散フレームワーク</li> - <li>CbCとは異なったGearというプログラム概念がある</li> - <li>特定のkeyに対する変数データ書き込みにより通信を行う</li> - <li>自律分散の実現を目指して開発された</li> - <li>TopologyManagerという機能を持つ</li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="christieのgear">ChristieのGear</h2> -<ul> - <li>CodeGear - <ul> - <li>スレッドに相当する</li> - <li>任意のkey nameを持つDataGearを待ち合わせ、揃ったら処理が実行される</li> - </ul> - </li> - <li>DataGear - <ul> - <li>変数データに相当する</li> - <li>key nameと変数データのペアで管理される</li> - </ul> - </li> - <li>CodeGearManger - <ul> - <li>ノードに相当する</li> - <li>DataGearManagerを所持し、CodeGearとDataGearを管理する</li> - </ul> - </li> - <li>DataGearManager - <ul> - <li>データプールに相当する</li> - <li>DataGearとkeyの組み合わせを保持している</li> - <li>LocalDGMとRemoteDGMの二種類が存在する</li> + <li>軽量継続への利用が行える</li> + <li>一つのDataGearに対する操作がトランザクションとなる</li> </ul> </li> </ul> @@ -371,102 +222,16 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="datagearmanagerによる通信">DataGearManagerによる通信</h2> +<h2 id="gearsosのファイルデータ操作">GearsOSのファイルデータ操作</h2> <ul> - <li>ChristieではDataGearの送受信によりノードどうしの通信を行う</li> - <li>LocalDataGearManager (LocalDGM) - <ul> - <li>CodeGearManagerが持つ、自身のDataGearPool</li> - <li>DataGearの大半はこれを参照する</li> - </ul> - </li> - <li>RemoteDataGearManager (RemoteDGM) + <li>ファイルデータの最小の単位は任意の型を持った構造体(DataGear)である <ul> - <li>他のCodeGearManagerが持つLocalDGMに対応するploxy</li> - <li>書き込みを行うと、対応したCodeGearManagerが持つLocalDGMに書き込みがされる</li> - </ul> - </li> - <li>DataGearManagerによる通信がChristieの通信の要となっている</li> -</ul> -<div style="text-align: center;"> - <img src="images/Remote_DataGearManager.pdf" alt="RemoteDGMの関係図" width="800" /> -</div> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="topologymanagear">TopologyManagear</h2> -<ul> - <li>参加を表明したノードに対して任意の形のTopologyに接続する - <ul> - <li>接続 = RemoteDGMを作成する</li> - <li>接続されたノードは他のノードを相対的な名前で参照できる(例:Child/parent, right/leftなど)</li> + <li>ファイルレコードと名付ける</li> </ul> </li> -</ul> - -<div style="text-align: center;"> - <img src="images/TopologyManager.pdf" alt="TopologyManager" width="800" /> -</div> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfilesystemの方針">GearsFileSystemの方針</h2> -<ul> - <li>データベース的なレコード操作によるファイルアクセス - <ul> - <li>KeyValueStoreに対する書き込み</li> - </ul> - </li> - <li>ファイルのバックアップ - <ul> - <li>ディレクトリの非破壊的編集とファイルの構成方法</li> - </ul> - </li> - <li>ファイルの型の認識 - <ul> - <li>ファイルレコードを適切な形の構造体にする</li> - </ul> - </li> - <li>自律分散を目指した分散ファイルシステム - <ul> - <li>プロトコルを用いないChristieAPI</li> - </ul> - </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造14">GearsFSのファイル構造1/4</h2> -<ul> - <li>ファイルのデータ単位は任意の型を持ったレコード - <ul> - <li>断続的に分割された状態で保存される</li> - <li>Queueに保存される</li> - <li>レコードを先頭から順に読むことでファイルを構成する</li> - </ul> - </li> - <li>ファイルレコードは構造体で再現される - <ul> - <li>ファイルレコード構造体はGearsのDataGearとして利用できる</li> - <li>レコードの構造体によりOSはファイルの型を認識する - <ul> - <li>ファイルの特性に合わせ、レコードとその構成方法を適した形で構成できる</li> - </ul> - </li> - </ul> - </li> + <li>レコードは特定の順番で連続しており、Queueに保存される</li> + <li>GearsのDataGearとして利用できる</li> + <li>構造体の型により処理の分岐が行える</li> </ul> <div style="text-align: center;"> @@ -479,38 +244,33 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造24">GearsFSのファイル構造2/4</h2> +<h2 id="ファイルqueueに対するapi">ファイルQueueに対するAPI</h2> <ul> - <li>ファイルの読み込み/書き込みはStreamを通して行われる + <li>Put <ul> - <li>streamも同様にQueueで構成される</li> - <li>streamはそれぞれ特定のkey nameをもつ</li> - <li>keyを用いることでアクセスが行われる</li> + <li>Queueに対してファイルレコードを入力する</li> + <li>ファイルの更新の際に呼び出す</li> + <li>ファイルの変更をレコードとして書き込む</li> </ul> </li> - <li>最低で、Input/OutputのStreamとファイルデータを保持するmainなQueueの三つで構成される</li> - <li>Write : InputStreamに対してレコードをputすれば良い</li> - <li>Read : OutputStreamからレコードを全てtakeすれば良い</li> -</ul> - -<div style="text-align: center;"> - <img src="images/GearsFile.pdf" alt="streamによるファイルアクセス" width="800" /> -</div> - - + <li>Take + <ul> + <li>Queueからファイルレコードを取り出す</li> + <li>ファイルの中身の読み込みの際に用いる</li> + <li>Queue内のレコードをループで全て取り出せば良い + <pre><code>typedef struct Queue<>{ +union Data* queue; +union Data* data; -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造34">GearsFSのファイル構造3/4</h2> -<ul> - <li>ChristieのDataGearManagerに相当する</li> - <li>GearsOSのファイルは大域的な資源である - <ul> - <li>複数のプロセスより競合的なアクセスが行われる</li> - <li>OutputStreamは複数のアクセスが行われても整合性が保たれる必要がある</li> - <li>CAS(Compare And Swap)が採用されたSynchronizedQueueを用いる</li> +__code whenEmpty(...); +__code clear(Impl* queue, __code next(...)); +__code put(Impl* queue, union Data* data, __code next(...)); +__code take(Impl* queue, __code next(union Data* data, ...)); +__code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); +__code next(...); +} Queue; +</code></pre> + </li> </ul> </li> </ul> @@ -521,16 +281,19 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造44">GearsFSのファイル構造4/4</h2> +<h2 id="gearsosのファイル">GearsOSのファイル</h2> <ul> - <li>stream、mainQueueはDataGearに相当し、keyによるアクセスが行われる</li> - <li>Queueは赤黒木に保持される</li> - <li>key nameで探索が行われ参照される</li> - <li>DGM書き込みは対象のkey nameを指定する</li> + <li>単独のQueueのみではファイル操作に耐えることができない</li> + <li>GearsOSのファイルは複数のQueueをkey nameをつけて保持するリストとなる + <ul> + <li>主体となるデータレコードを保持するQueue</li> + <li>Input/OutputStreamとなるQueue</li> + <li>通信処理を行う際に任意に利用したいデータを受けるQueue</li> + </ul> + </li> + <li>ChristieのDataGearManagerの仕組みを用いる</li> + <li>ファイルであると同時に通信そのものでもある</li> </ul> -<div style="text-align: center;"> - <img src="images/newGearsFile.pdf" alt="DataGearの保存形式" width="800" /> -</div> @@ -538,14 +301,32 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="遠隔からのファイル操作">遠隔からのファイル操作</h2> +<h2 id="datagearmanager">DataGearManager</h2> <ul> - <li>GearsOSのファイルは、ファイル通信そのものにも相当する</li> - <li>RemoteDGMの仕組みを用いることで遠隔からのファイル読み込み/書き込みを行う</li> + <li>keyとvalueの組み合わせとなるDataGearを保持するデータプール</li> + <li>ChristieではCodeGearManagerと呼ばれるノードがCodeGearとDataGearを管理する</li> + <li>LocalDGMはノード本体に対応するデータプールである + <ul> + <li>CodeGearはLocalDGMに対してDataGearを参照する</li> + </ul> + </li> + <li>RemoteDGMは接続する相手ノードに対応するデータプールploxyである + <ul> + <li>RemoteDGMに対してDataGearを書き込むことで、対応するノードのLocalDGMにデータが書き込まれる</li> + </ul> + </li> + <li>GearsFSも同様にファイルploxyを通して通信を行う</li> </ul> + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="datagearmanager-1">DataGearManager</h2> <div style="text-align: center;"> - <img src="images/socketCom.pdf" alt="socketを通じたレコード送信" width="800" /> + <img src="images/Remote_DataGearManager.pdf" alt="RemoteDGMの関係図" width="800" /> </div> @@ -554,44 +335,20 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="socketからの受信データ取り出し">socketからの受信データ取り出し</h2> +<h2 id="socket付きqueueの実装">socket付きQueueの実装</h2> <ul> - <li>socketはImplementに記述される</li> - <li>LocalDGMに相当するファイルは、接続先socketから送信されたデータを取り出す</li> - <li>APIとして記述される</li> - <li>取り出されたデータは次の継続先でQueueに対してputされる</li> -</ul> - -<pre><code>__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenEOF(...), __code whenError(...)){ - union Data* recv_data; - recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0); - if (recv_size == -1) { - printf("recv error\n"); - goto whenError(...); - } - 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); + <li>socketに接続されたQueueにより通信APIの記述を行った</li> + <li>GearsOS上でのsocket操作の記述</li> + <li>Localなqueueに対してRemoteのqueueがソケット接続を行う + <pre><code>TQueue* createRemoteDGMQueue(struct Context* context, char* sNum) { + struct TQueue* tQueue = new TQueue(); + struct RemoteDGMQueue* RemoteDGMQueue = new RemoteDGMQueue(); + RemoteDGMQueue->atomic = createAtomicReference(context); + RemoteDGMQueue->socket = createSocketRemoteDGMQueue(sNum); } </code></pre> + </li> +</ul> @@ -599,23 +356,18 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="remotedgmのsocketによるデータ送信">RemoteDGMのsocketによるデータ送信</h2> +<h2 id="remotequeue側からの送信">RemoteQueue側からの送信</h2> <ul> - <li>RemoteDGM側はsocketを用いてデータを送信する</li> - <li>Queueに対してputされたデータを送信する</li> - <li>putCodeGearの直後に呼び出される + <li>QueueのPutAPIの後に遷移される</li> + <li>putしたデータをsocketを通じて送信する</li> + <li>将来的にsendではなくwriteを用いる <pre><code>__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"); - goto whenError(); - } - recv_size = recv(cQueue->socket, &recv_buf, 1, 0); - if (recv_size == -1) { - printf("recv error\n"); - goto whenError(); - } + //error処理は省略 goto next(...); } </code></pre> @@ -628,12 +380,91 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="wordcount例題">WordCount例題</h2> +<h2 id="localqueue側の受信">LocalQueue側の受信</h2> +<ul> + <li>APIとしてsocketのデータを取り出す</li> + <li>取り出されたデータはQueueにputされる</li> + <li>union Data型でデータを受け取りmain側で処理を行う</li> + <li>取り出されたデータはmain側で処理される</li> + <li>将来的にrecvでなくreadを用いる + <pre><code>__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenError(...)){ + int recv_size, send_size; + char send_buf; + + union Data* recv_data; + recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0); + + //error処理は省略 + Gearef(context, cQueue)->data = recv_data; + goto putLocalDGMQueue(recv_data, next); +} +</code></pre> + </li> +</ul> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="ファイル単位のsocket通信">ファイル単位のsocket通信</h2> <ul> - <li>ChristieAPIの構成をWordCount例題を通して行った</li> - <li>ファイルの中の文字列を1行ずつ読み取り、ファイル内の文字数と行数を調べる</li> - <li>ファイルの送信と文字列のカウントをそれぞれ別ノード上で行うことで、ファイル読み込みとファイルレコードの通信処理が構成できる</li> + <li>実際のファイルは複数のQueueを持つ一つのリストである</li> + <li>Queue単体でなく、リスト(ファイル)単位でsocketを持つ必要がある</li> + <li>リストは赤黒木となる</li> + <li>DataGearをputするkeyを指定して書き込みを行う + <ul> + <li>Localなファイルの同一のQueueに対して書き込みが行われる</li> + </ul> + </li> </ul> +<div style="text-align: center;"> + <img src="images/socketCom.pdf" alt="socketを通じたレコード送信" width="800" /> +</div> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="main部分によるapi">main部分によるAPI</h2> +<ul> + <li>readの場合(リモート側に読み込みたいファイルが存在する) + <ul> + <li>(手順1)ローカル側は空のファイルを作成し、socketを持たせる</li> + <li>(手順2)リモート側は, ローカル側の持つ空ファイルのploxyを作成する</li> + <li>(手順3)リモート側はploxyに対して、目的のファイルのデータをputする</li> + </ul> + </li> + <li>writeの場合(リモート側に書き込みたいファイルが存在する) + <ul> + <li>(手順1)リモート側は対象ファイルにsocketを持たせる</li> + <li>(手順2)ローカル側は対象のファイルに対応するploxyを作成する</li> + <li>(手順3)ローカル側はploxyのkeyに対してデータをputする</li> + </ul> + </li> +</ul> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="wordcountの例題">wordCountの例題</h2> +<ul> + <li>DataGearManagerによるファイル通信APIはWordCount例題を目指して設計した + <ul> + <li>ファイル内の文字列を1行づつ受け取り、文字列,行数をカウントする例題</li> + </ul> + </li> + <li>文字列送信側とCount側を別ノード上で行うことで、ファイルの呼び出しと通信処理が構成できる</li> +</ul> +<div style="text-align: center;"> + <img src="images/wordCountDGM.pdf" alt="リモートDGMによるWordCount" width="800" /> +</div> @@ -659,15 +490,17 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのディレクトリ">GearsFSのディレクトリ</h2> +<h2 id="これから実装が必要となる機能">これから実装が必要となる機能</h2> <ul> - <li>ディレクトリを赤黒木で実装する</li> - <li>赤黒木のノードとしてファイル/ディレクトリが保存される</li> - <li>階層構造はファイル名がkey, データとしてinodeが保存される</li> + <li>keyアクセスに対応したファイル通信 + <ul> + <li>単一のQueueによる通信は確認が行えた</li> + </ul> + </li> + <li>ファイル保存</li> + <li>バックアップ機能</li> + <li>並列処理</li> </ul> -<div style="text-align: center;"> - <img src="images/GearsDirectory.pdf" alt="GearsOSのディレクトリ" width="500" /> -</div> @@ -675,11 +508,10 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのバックアップ12">GearsFSのバックアップ(1/2)</h2> +<h2 id="gearsosのディレクトリとバックアップ">GearsOSのディレクトリとバックアップ</h2> <ul> - <li>ディレクトリツリーを非破壊的な編集で更新する</li> - <li>木構造の編集前の構造が履歴となる</li> - <li>保存容量の圧迫は対応が必要となる</li> + <li>又吉雄斗による並行研究にて、inodeによるファイルシステムが開発されている</li> + <li>赤黒木の非破壊な編集により、ディレクトリの履歴を残すことができる</li> </ul> <div style="text-align: center;"> <img src="images/nonDestroyTreeEdit.pdf" alt="非破壊的なツリー編集" width="800" /> @@ -691,34 +523,44 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのバックアップ22">GearsFSのバックアップ(2/2)</h2> +<h2 id="生成形の問題点">生成形の問題点</h2> <ul> - <li>ファイルレコードを変更差分として構成する + <li>GearsOSのメタレベルの処理の記述はトランスコンパイラにより行われる</li> + <li>場合によりメタレベルの記述を行わなくてはならない <ul> - <li>GithubやMercurialのようなバージョン管理が行える</li> - <li>特定の日時までのレコードを読めばよい</li> + <li>他のInterfaceを継承したオブジェクトからのDataGear継承 + <ul> + <li>例)Queueからのデータ取り出し</li> + <li>トランスコンパイラはどのInterfaceが持つDataGearを参照するべきか判断が難しい</li> + </ul> + </li> </ul> </li> - <li>定期的なファイルの再構築が必要</li> </ul> - +<pre><code>__code Task2(TQueue* localDGMQueue){ + goto localDGMQueue->take(Task3); +} -</div> +__code Task3(TQueue* localDGMQueue, FileString* string){ + printf("take[%s] [num:%d]\n", string->str, string->size); + goto getData(); +} -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfsの並列処理">GearsFSの並列処理</h2> -<ul> - <li>par gotoを用いる案 - <ul> - <li>処理速度が遅い</li> - <li>トランスコンパイラへの依存度が高い</li> - <li>現状バグが存在している</li> - </ul> - </li> - <li>新しく並列処理を開発する</li> -</ul> +//プログラマが実装したいstub +__code Task3_stub(struct Context* context){ + TQueue* localDGMQueue = (struct TQueue*)Gearef(context, TQueue)->tQueue; + FileString* string = Gearef(context, TQueue)->data; + goto Task3(context, localDGMQueue, string); +} + +//自動生成されたErrorなstub +__code Task3_stub(struct Context* context) { + TQueue* localDGMQueue = Gearef(context, TQueue); + FileString* string = Gearef(context, FileString); + goto Task3(context, localDGMQueue, string); +} +</code></pre> @@ -726,45 +568,22 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsosの問題点">GearsOSの問題点</h2> +<h2 id="並列処理構文par-gotoが持つ問題">並列処理構文par gotoが持つ問題</h2> <ul> - <li>記述難易度の高さ</li> - <li>Contextの操作 + <li>par gotoとはGearsOSに実装された並列処理構文である</li> + <li>par gotoはトランスコンパイラへの依存性が高い <ul> - <li>トランスコンパイラでは対応できない継承が存在する</li> - <li>場合によりメタレベルの記述を行わなくてはならない</li> - </ul> - </li> - <li>軽量継続 - <ul> - <li>ループ記述が複雑</li> - <li>goto遷移以降の記述は実行されない</li> + <li>stubCodeGearのように任意な書き換えが行えない</li> </ul> </li> - <li>par gotoの実用が難しい</li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="課題">課題</h2> -<ul> - <li>TopologyManagerの実装 + <li>StreamQueueに対するput/takeの並列処理の実装をpar goto構文で試みた</li> + <li>特定のCodeGearの宣言のみでしか正常な処理が生成されない <ul> - <li>ファイルの配線を行う</li> - <li>DNSの役割</li> - <li>クラスターの管理</li> + <li>Interfaceに記述されたAPICodeGearではバグが生じる</li> + <li>par gotoでの使用を前提としたCodeGearを書かなくてはならない</li> </ul> </li> - <li>並列処理方法の決定 - <ul> - <li>par gotoの改良</li> - <li>新たな案を実装する</li> - </ul> - </li> + <li>処理が重いという問題点も存在する</li> </ul> @@ -775,30 +594,40 @@ <!-- _S9SLIDE_ --> <h2 id="結論">結論</h2> <ul> - <li>GearsFileSystemの設計 + <li>GearsOSのファイルの設計を行った <ul> - <li>ファイルの構成方法 + <li>ファイルの構造の設計</li> + <li>socketによる通信部分の実装</li> + <li>単純化した通信APIの記述</li> + <li>GearsOSの調査</li> + </ul> + </li> + <li>ファイルploxyによる通信実現を行いたい</li> +</ul> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="これからの課題">これからの課題</h2> +<ul> + <li>TopoplogyManagerの設計 + <ul> + <li>参加したノードを任意の形のTopologyに接続する機能</li> + <li>ファイルシステム向けの機能を追加したい <ul> - <li>keyによってアクセスされるQueueのリスト</li> + <li>DNS</li> + <li>中枢としてのTopologyのノード監視</li> </ul> </li> - <li>ファイル操作API - <ul> - <li>ChristieAPI</li> - <li>レコード単位で操作される</li> - </ul> - </li> - <li>ファイル送受信の実装 - <ul> - <li>RemoteDGM(ファイルploxy)</li> - </ul> - </li> - <li>ディレクトリの仕組み - <ul> - <li>赤黒木を用いる</li> - <li>非破壊的な編集によるログ</li> - </ul> - </li> + </ul> + </li> + <li>Securityシステムの追加 + <ul> + <li>証明書などによるファイル操作制限</li> + <li>不正な分散ファイルシステムへのアクセス</li> </ul> </li> </ul> @@ -809,43 +638,7 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="この先保留ページ">この先保留ページ</h2> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsosのimplementation">GearsOSのImplementation</h2> -<ul> - <li>Interfaceの実装である</li> - <li>定義ファイル(.h)に記述を行う</li> - <li>必ず継承元のInterfaceを記述する必要がある</li> - <li>プロセス内のCodeGearが共通して使いたい変数を記述する - <pre><code>typedef struct SynchronizedQueue <> impl Queue { -struct Element* top; -struct Element* last; -struct Atomic* atomic; -} SynchronizedQueue; -</code></pre> - </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="研究成果">研究成果</h2> -<ul> - <li>連続するレコードで構成されるGearsOSファイルの設計</li> - <li>keyアクセスを用いたファイルに対するRead, writeAPI</li> - <li>赤黒木を用いたディレクトリシステムの構築</li> - <li>ファイルのバックアップ考察</li> - <li>ploxyを用いたファイルの送受信</li> -</ul> +<h2 id="この先保留">この先保留</h2> @@ -853,43 +646,20 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="api手順">API手順</h2> +<h2 id="ファイルqueueに対するapi--peek-">ファイルQueueに対するAPI -Peek-</h2> <ul> - <li>readの場合(リモート側に読み込みたいファイルが存在する) + <li>Peek <ul> - <li>(手順1)ローカル側はLocalDGMの相当する空のファイルを作成し、socketを持つ</li> - <li>(手順2)リモート側はローカルの空ファイルのploxyを作成する</li> - <li>(手順3)リモート側はploxyに対してデータをputする</li> - </ul> - </li> - <li>writeの場合(リモート側に書き込みたいファイルが存在する) - <ul> - <li>(手順1)リモート側は対象ファイルにsocketを持たせる</li> - <li>(手順2)ローカル側は対象のファイルに対応するploxy(RemoteDGM)を作成する</li> - <li>(手順3)ローカル側はploxyのkeyに対してデータをputする</li> + <li>QueueのElementを参照するが、削除は行わない</li> + <li>現時点での実装は行っていない</li> + <li>QueueのTopのレコードを変更せずに出力すれば良い +<!–</li> </ul> </li> + <li>RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。 +–></li> </ul> - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="wordcount手順">WordCount手順</h2> -<ul> - <li>(手順1)ファイル内文字列を1行ずつWordCount関数へ入力する、これをループ</li> - <li>(手順2)ファイル内文字列が無くなった場合(EoF)結果を出力し、終了する</li> -</ul> -<div style="text-align: center;"> - <img src="images/wordCountStates.pdf" alt="WordCountの遷移図" width="800" /> -</div> - -<!-- -- RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。 ---> - </div>
--- a/slide/thesis.md Mon Feb 07 20:58:17 2022 +0900 +++ b/slide/thesis.md Wed Feb 09 22:26:31 2022 +0900 @@ -5,59 +5,45 @@ code-engine: coderay -## GearsOSとその現状 -- 信頼性の保証と拡張性の高さを目指したOSプロジェクト -- 軽量継続を用いた言語、CbC(Continuation based C)により記述される -- ノーマルレベルとメタレベルを分離して記述する -- 現状では言語フレームワークとしてのみ機能する -- OSとして動作するには多くの機能の開発が必要 - - その中の一つにファイルシステムが挙げられる - +## GearsOSのファイルシステム設計 +- GearsOSには現時点でファイルシステムが存在していない +- GearsOSのファイルシステムの設計と実装を行った +- GearsOSの特性に合わせた実装 + - CodeGear/DataGearによる継続処理 + - 同じくGear概念を持つ分散フレームワークChristieの仕組みを用いた +- 将来的に重要な機能をOSに取り込みたい + - バックアップ + - ファイルの型認識 -## 従来の物より発展した分散ファイルシステムの設計 -- データベース的なレコード操作によるアクセス - - ファイルに対する全ての操作がTransactionとなる -- 既存ではアプリケーションが担当する機能を取り込む - - バックアップの管理 - - ファイルの型の認識 -- 自律分散を目指した分散ファイルシステム - - 特定のサーバーを中枢にしなくても良い - - 分散フレームワークChristieの仕組みにより実現する - - -## CbC (Continuation based C) -- C言語の拡張言語である -- 関数に代わる軽量継続をメインに記述する -- Gearというプログラム概念 +## GearsOS +- 関数でなくGearという単位を用いて記述する - CodeGear - 従来のThreadにあたる + - goto文(jump命令)を使って遷移する - DataGear - 従来の変数データにあたる -- DataGearを受け取り処理を行う(InputDataGear) -- 処理の結果をDataGearに書き出す(OutputDataGear) - + - スタックを持たないため軽量継続と呼ぶ +- CodeGearは処理を行う際、DataGearを参照し処理を行う(InputDataGear) +- CodeGearは処理の終了後、以降に必要なデータをDataGearとして出力する(OutputDataGear) <div style="text-align: center;"> - <img src="images/cgdg.pdf" alt="CodeGearとDataGearの関係" width="800"> + <img src="images/cg-dg.pdf" alt=cgdgの関係図 width="800"> </div> -## CbCのサンプルプログラム +## GearsOSのInterface +- APIの宣言を行う + - 定義ファイル(.h)に記述を行う + - APIとなるCodeGearとその参照するDataGearを宣言する + - DataGear/CodeGearの一時的な置き場としての役割を持つ ``` -__code CG2(int num3){ - printf("num = %d\n", num3); - exit(0); -} - -__code CG1(int num, int num1){ - int num2 = num + num1; - goto CG2(num2); -} - -int main(){ - int a = 2; - int b = 3; - goto CG1(a, b); -} +typedef struct Tree<>{ + union Data* tree; + struct Node* node; + __code put(Impl* tree,Type* node, __code next(...)); + __code get(Impl* tree, Type* node, __code next(...)); + __code remove(Impl* tree,Type* node, __code next(...)); + __code next(...); +} Tree; ``` ## メタレベルのGear @@ -68,21 +54,41 @@ - CodeGear処理前に呼ばれるものを特にstubCodeGearと呼ぶ - MetaDataGear - MetaCodeGearにて参照されるDataGear -- ユーザーが記述する上では普段は意識しない - +- メタレベルの処理はトランスコンパイラにより自動に記述される <div style="text-align: center;"> <img src="images/meta-cg-dg.pdf" alt="ノーマルレベルとメタレベルの視点からのGearの関係" width="800"> </div> -## GearsOSの構成 -- Interface - - 定義ファイル(.h)に記述を行う - - APIとなるCodeGearとその参照するDataGearを宣言する - - コンパイル時にContext(後述)に書き込まれる -- Implement - - Interfaceの実装 - - プログラム内で共通して利用したい変数 + +## DataGear単位のトランザクション +- GearsOSはDataGear単位でプロセスが進行する +- 従来のファイルシステムは一部の操作のみがTransactionとなっている +- GearsOSのファイルシステムはDataGear単位で処理を行いたい + - 軽量継続への利用が行える + - 一つのDataGearに対する操作がトランザクションとなる + + +## GearsOSのファイルデータ操作 +- ファイルデータの最小の単位は任意の型を持った構造体(DataGear)である + - ファイルレコードと名付ける +- レコードは特定の順番で連続しており、Queueに保存される +- GearsのDataGearとして利用できる +- 構造体の型により処理の分岐が行える + +<div style="text-align: center;"> + <img src="images/QueueElement.pdf" alt=Queueの構造 width="800"> +</div> + +## ファイルQueueに対するAPI +- Put + - Queueに対してファイルレコードを入力する + - ファイルの更新の際に呼び出す + - ファイルの変更をレコードとして書き込む +- Take + - Queueからファイルレコードを取り出す + - ファイルの中身の読み込みの際に用いる + - Queue内のレコードをループで全て取り出せば良い ``` typedef struct Queue<>{ union Data* queue; @@ -96,216 +102,115 @@ __code next(...); } Queue; ``` -``` -typedef struct SynchronizedQueue <> impl Queue { - struct Element* top; - struct Element* last; - struct Atomic* atomic; -} SynchronizedQueue; -``` + -## ContextとGearの関係性 -- Context - - 遷移の際にデータを全て記録するオブジェクト - - プログラムに使われるCodeGear/DataGearを管理する - - 軽量継続中、必ず引数で参照される - - メタレベルなCodeGearからのみ参照される -<div style="text-align: center;"> - <img src="images/Context_ref.pdf" alt="Contextの参照" width="900"> -</div> + -## GearsOSのトランスコンパイラ -- CbCプログラムはトランスコンパイルによりC言語プログラムに書き換えられる - - トランスコンパイルの際に、メタレベルの記述が行われる - - StubCodeGearの自動生成 - - Gears向けに記述された演算子(par goto、NEW)の書き換え -- StubCodeGearはCbCプログラムへ直に記述することでユーザーの任意の処理に変えられる -``` -__code putSynchronizedQueue_stub(struct Context* context) { - SynchronizedQueue* queue = (SynchronizedQueue*)GearImpl(context, Queue, queue); - Data* data = Gearef(context, Queue)->data; - enum Code next = Gearef(context, Queue)->next; - goto putSynchronizedQueue(context, queue, data, next); -} -``` -``` -__code putSynchronizedQueue(struct Context *context,struct SynchronizedQueue* queue, -union Data* data, enum Code next) { - ~省略~ -} -``` +## GearsOSのファイル +- 単独のQueueのみではファイル操作に耐えることができない +- GearsOSのファイルは複数のQueueをkey nameをつけて保持するリストとなる + - 主体となるデータレコードを保持するQueue + - Input/OutputStreamとなるQueue + - 通信処理を行う際に任意に利用したいデータを受けるQueue +- ChristieのDataGearManagerの仕組みを用いる +- ファイルであると同時に通信そのものでもある + -## 分散フレームワークChristie -- Java言語で記述された分散フレームワーク -- CbCとは異なったGearというプログラム概念がある -- 特定のkeyに対する変数データ書き込みにより通信を行う -- 自律分散の実現を目指して開発された -- TopologyManagerという機能を持つ +## DataGearManager +- keyとvalueの組み合わせとなるDataGearを保持するデータプール +- ChristieではCodeGearManagerと呼ばれるノードがCodeGearとDataGearを管理する +- LocalDGMはノード本体に対応するデータプールである + - CodeGearはLocalDGMに対してDataGearを参照する +- RemoteDGMは接続する相手ノードに対応するデータプールploxyである + - RemoteDGMに対してDataGearを書き込むことで、対応するノードのLocalDGMにデータが書き込まれる +- GearsFSも同様にファイルploxyを通して通信を行う -## ChristieのGear -- CodeGear - - スレッドに相当する - - 任意のkey nameを持つDataGearを待ち合わせ、揃ったら処理が実行される -- DataGear - - 変数データに相当する - - key nameと変数データのペアで管理される -- CodeGearManger - - ノードに相当する - - DataGearManagerを所持し、CodeGearとDataGearを管理する -- DataGearManager - - データプールに相当する - - DataGearとkeyの組み合わせを保持している - - LocalDGMとRemoteDGMの二種類が存在する - -## DataGearManagerによる通信 -- ChristieではDataGearの送受信によりノードどうしの通信を行う -- LocalDataGearManager (LocalDGM) - - CodeGearManagerが持つ、自身のDataGearPool - - DataGearの大半はこれを参照する -- RemoteDataGearManager (RemoteDGM) - - 他のCodeGearManagerが持つLocalDGMに対応するploxy - - 書き込みを行うと、対応したCodeGearManagerが持つLocalDGMに書き込みがされる -- DataGearManagerによる通信がChristieの通信の要となっている +## DataGearManager <div style="text-align: center;"> <img src="images/Remote_DataGearManager.pdf" alt="RemoteDGMの関係図" width="800"> </div> -## TopologyManagear -- 参加を表明したノードに対して任意の形のTopologyに接続する - - 接続 = RemoteDGMを作成する - - 接続されたノードは他のノードを相対的な名前で参照できる(例:Child/parent, right/leftなど) - -<div style="text-align: center;"> - <img src="images/TopologyManager.pdf" alt=TopologyManager width="800"> -</div> - -## GearsFileSystemの方針 -- データベース的なレコード操作によるファイルアクセス - - KeyValueStoreに対する書き込み -- ファイルのバックアップ - - ディレクトリの非破壊的編集とファイルの構成方法 -- ファイルの型の認識 - - ファイルレコードを適切な形の構造体にする -- 自律分散を目指した分散ファイルシステム - - プロトコルを用いないChristieAPI - -## GearsFSのファイル構造1/4 -- ファイルのデータ単位は任意の型を持ったレコード - - 断続的に分割された状態で保存される - - Queueに保存される - - レコードを先頭から順に読むことでファイルを構成する -- ファイルレコードは構造体で再現される - - ファイルレコード構造体はGearsのDataGearとして利用できる - - レコードの構造体によりOSはファイルの型を認識する - - ファイルの特性に合わせ、レコードとその構成方法を適した形で構成できる - -<div style="text-align: center;"> - <img src="images/QueueElement.pdf" alt=Queueの構造 width="800"> -</div> +## socket付きQueueの実装 +- socketに接続されたQueueにより通信APIの記述を行った +- GearsOS上でのsocket操作の記述 +- Localなqueueに対してRemoteのqueueがソケット接続を行う +``` +TQueue* createRemoteDGMQueue(struct Context* context, char* sNum) { + struct TQueue* tQueue = new TQueue(); + struct RemoteDGMQueue* RemoteDGMQueue = new RemoteDGMQueue(); + RemoteDGMQueue->atomic = createAtomicReference(context); + RemoteDGMQueue->socket = createSocketRemoteDGMQueue(sNum); +} +``` -## GearsFSのファイル構造2/4 -- ファイルの読み込み/書き込みはStreamを通して行われる - - streamも同様にQueueで構成される - - streamはそれぞれ特定のkey nameをもつ - - keyを用いることでアクセスが行われる -- 最低で、Input/OutputのStreamとファイルデータを保持するmainなQueueの三つで構成される -- Write : InputStreamに対してレコードをputすれば良い -- Read : OutputStreamからレコードを全てtakeすれば良い - -<div style="text-align: center;"> - <img src="images/GearsFile.pdf" alt= streamによるファイルアクセス width="800"> -</div> - - -## GearsFSのファイル構造3/4 -- ChristieのDataGearManagerに相当する -- GearsOSのファイルは大域的な資源である - - 複数のプロセスより競合的なアクセスが行われる - - OutputStreamは複数のアクセスが行われても整合性が保たれる必要がある - - CAS(Compare And Swap)が採用されたSynchronizedQueueを用いる +## RemoteQueue側からの送信 +- QueueのPutAPIの後に遷移される +- putしたデータをsocketを通じて送信する +- 将来的にsendではなくwriteを用いる +``` +__code sendDataRemoteDGMQueue(struct RemoteDGMQueue* cQueue, union Data* data, __code next(...), __code whenError(...)){ + char recv_buf; + int send_size, recv_size; -## GearsFSのファイル構造4/4 -- stream、mainQueueはDataGearに相当し、keyによるアクセスが行われる -- Queueは赤黒木に保持される -- key nameで探索が行われ参照される -- DGM書き込みは対象のkey nameを指定する -<div style="text-align: center;"> - <img src="images/newGearsFile.pdf" alt= DataGearの保存形式 width="800"> -</div> - -## 遠隔からのファイル操作 -- GearsOSのファイルは、ファイル通信そのものにも相当する -- RemoteDGMの仕組みを用いることで遠隔からのファイル読み込み/書き込みを行う + send_size = send(cQueue->socket, data, sizeof(union Data), 0); + recv_size = recv(cQueue->socket, &recv_buf, 1, 0); + //error処理は省略 + goto next(...); +} +``` -<div style="text-align: center;"> - <img src="images/socketCom.pdf" alt=socketを通じたレコード送信 width="800"> -</div> - +## LocalQueue側の受信 +- APIとしてsocketのデータを取り出す +- 取り出されたデータはQueueにputされる +- union Data型でデータを受け取りmain側で処理を行う +- 取り出されたデータはmain側で処理される +- 将来的にrecvでなくreadを用いる +``` +__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenError(...)){ + int recv_size, send_size; + char send_buf; -## socketからの受信データ取り出し -- socketはImplementに記述される -- LocalDGMに相当するファイルは、接続先socketから送信されたデータを取り出す -- APIとして記述される -- 取り出されたデータは次の継続先でQueueに対してputされる - -``` -__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenEOF(...), __code whenError(...)){ union Data* recv_data; recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0); - if (recv_size == -1) { - printf("recv error\n"); - goto whenError(...); - } - 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(...); - } - } + //error処理は省略 Gearef(context, cQueue)->data = recv_data; goto putLocalDGMQueue(recv_data, next); } ``` -## RemoteDGMのsocketによるデータ送信 -- RemoteDGM側はsocketを用いてデータを送信する -- Queueに対してputされたデータを送信する -- putCodeGearの直後に呼び出される -``` -__code sendDataRemoteDGMQueue(struct RemoteDGMQueue* cQueue, union Data* data, __code next(...), __code whenError(...)){ - send_size = send(cQueue->socket, data, sizeof(union Data), 0); - if (send_size == -1) { - printf("send error\n"); - goto whenError(); - } - - recv_size = recv(cQueue->socket, &recv_buf, 1, 0); - if (recv_size == -1) { - printf("recv error\n"); - goto whenError(); - } - goto next(...); -} -``` -## WordCount例題 -- ChristieAPIの構成をWordCount例題を通して行った -- ファイルの中の文字列を1行ずつ読み取り、ファイル内の文字数と行数を調べる -- ファイルの送信と文字列のカウントをそれぞれ別ノード上で行うことで、ファイル読み込みとファイルレコードの通信処理が構成できる +## ファイル単位のsocket通信 +- 実際のファイルは複数のQueueを持つ一つのリストである +- Queue単体でなく、リスト(ファイル)単位でsocketを持つ必要がある +- リストは赤黒木となる +- DataGearをputするkeyを指定して書き込みを行う + - Localなファイルの同一のQueueに対して書き込みが行われる +<div style="text-align: center;"> + <img src="images/socketCom.pdf" alt=socketを通じたレコード送信 width="800"> +</div> + +## main部分によるAPI +- readの場合(リモート側に読み込みたいファイルが存在する) + - (手順1)ローカル側は空のファイルを作成し、socketを持たせる + - (手順2)リモート側は, ローカル側の持つ空ファイルのploxyを作成する + - (手順3)リモート側はploxyに対して、目的のファイルのデータをputする +- writeの場合(リモート側に書き込みたいファイルが存在する) + - (手順1)リモート側は対象ファイルにsocketを持たせる + - (手順2)ローカル側は対象のファイルに対応するploxyを作成する + - (手順3)ローカル側はploxyのkeyに対してデータをputする + + +## wordCountの例題 +- DataGearManagerによるファイル通信APIはWordCount例題を目指して設計した + - ファイル内の文字列を1行づつ受け取り、文字列,行数をカウントする例題 +- 文字列送信側とCount側を別ノード上で行うことで、ファイルの呼び出しと通信処理が構成できる +<div style="text-align: center;"> + <img src="images/wordCountDGM.pdf" alt="リモートDGMによるWordCount" width="800"> +</div> + + ## ChristieAPIによるWordCount - FileOpen側とWordCount側でノードが別れる @@ -318,113 +223,90 @@ </div> +## これから実装が必要となる機能 +- keyアクセスに対応したファイル通信 + - 単一のQueueによる通信は確認が行えた +- ファイル保存 +- バックアップ機能 +- 並列処理 -## GearsFSのディレクトリ -- ディレクトリを赤黒木で実装する -- 赤黒木のノードとしてファイル/ディレクトリが保存される -- 階層構造はファイル名がkey, データとしてinodeが保存される -<div style="text-align: center;"> - <img src="images/GearsDirectory.pdf" alt=GearsOSのディレクトリ width="500"> -</div> - - -## GearsFSのバックアップ(1/2) -- ディレクトリツリーを非破壊的な編集で更新する -- 木構造の編集前の構造が履歴となる -- 保存容量の圧迫は対応が必要となる +## GearsOSのディレクトリとバックアップ +- 又吉雄斗による並行研究にて、inodeによるファイルシステムが開発されている +- 赤黒木の非破壊な編集により、ディレクトリの履歴を残すことができる <div style="text-align: center;"> <img src="images/nonDestroyTreeEdit.pdf" alt=非破壊的なツリー編集 width="800"> </div> -## GearsFSのバックアップ(2/2) -- ファイルレコードを変更差分として構成する - - GithubやMercurialのようなバージョン管理が行える - - 特定の日時までのレコードを読めばよい -- 定期的なファイルの再構築が必要 +## 生成形の問題点 +- GearsOSのメタレベルの処理の記述はトランスコンパイラにより行われる +- 場合によりメタレベルの記述を行わなくてはならない + - 他のInterfaceを継承したオブジェクトからのDataGear継承 + - 例)Queueからのデータ取り出し + - トランスコンパイラはどのInterfaceが持つDataGearを参照するべきか判断が難しい -## GearsFSの並列処理 -- par gotoを用いる案 - - 処理速度が遅い - - トランスコンパイラへの依存度が高い - - 現状バグが存在している -- 新しく並列処理を開発する +``` +__code Task2(TQueue* localDGMQueue){ + goto localDGMQueue->take(Task3); +} + +__code Task3(TQueue* localDGMQueue, FileString* string){ + printf("take[%s] [num:%d]\n", string->str, string->size); + goto getData(); +} -## GearsOSの問題点 -- 記述難易度の高さ -- Contextの操作 - - トランスコンパイラでは対応できない継承が存在する - - 場合によりメタレベルの記述を行わなくてはならない -- 軽量継続 - - ループ記述が複雑 - - goto遷移以降の記述は実行されない -- par gotoの実用が難しい +//プログラマが実装したいstub +__code Task3_stub(struct Context* context){ + TQueue* localDGMQueue = (struct TQueue*)Gearef(context, TQueue)->tQueue; + FileString* string = Gearef(context, TQueue)->data; + goto Task3(context, localDGMQueue, string); +} -## 課題 -- TopologyManagerの実装 - - ファイルの配線を行う - - DNSの役割 - - クラスターの管理 -- 並列処理方法の決定 - - par gotoの改良 - - 新たな案を実装する +//自動生成されたErrorなstub +__code Task3_stub(struct Context* context) { + TQueue* localDGMQueue = Gearef(context, TQueue); + FileString* string = Gearef(context, FileString); + goto Task3(context, localDGMQueue, string); +} +``` + +## 並列処理構文par gotoが持つ問題 +- par gotoとはGearsOSに実装された並列処理構文である +- par gotoはトランスコンパイラへの依存性が高い + - stubCodeGearのように任意な書き換えが行えない +- StreamQueueに対するput/takeの並列処理の実装をpar goto構文で試みた +- 特定のCodeGearの宣言のみでしか正常な処理が生成されない + - Interfaceに記述されたAPICodeGearではバグが生じる + - par gotoでの使用を前提としたCodeGearを書かなくてはならない +- 処理が重いという問題点も存在する + ## 結論 -- GearsFileSystemの設計 - - ファイルの構成方法 - - keyによってアクセスされるQueueのリスト - - ファイル操作API - - ChristieAPI - - レコード単位で操作される - - ファイル送受信の実装 - - RemoteDGM(ファイルploxy) - - ディレクトリの仕組み - - 赤黒木を用いる - - 非破壊的な編集によるログ - - -## この先保留ページ - +- GearsOSのファイルの設計を行った + - ファイルの構造の設計 + - socketによる通信部分の実装 + - 単純化した通信APIの記述 + - GearsOSの調査 +- ファイルploxyによる通信実現を行いたい -## GearsOSのImplementation -- Interfaceの実装である -- 定義ファイル(.h)に記述を行う -- 必ず継承元のInterfaceを記述する必要がある -- プロセス内のCodeGearが共通して使いたい変数を記述する -``` -typedef struct SynchronizedQueue <> impl Queue { - struct Element* top; - struct Element* last; - struct Atomic* atomic; -} SynchronizedQueue; -``` - +## これからの課題 +- TopoplogyManagerの設計 + - 参加したノードを任意の形のTopologyに接続する機能 + - ファイルシステム向けの機能を追加したい + - DNS + - 中枢としてのTopologyのノード監視 +- Securityシステムの追加 + - 証明書などによるファイル操作制限 + - 不正な分散ファイルシステムへのアクセス -## 研究成果 -- 連続するレコードで構成されるGearsOSファイルの設計 -- keyアクセスを用いたファイルに対するRead, writeAPI -- 赤黒木を用いたディレクトリシステムの構築 -- ファイルのバックアップ考察 -- ploxyを用いたファイルの送受信 +## この先保留 -## API手順 -- readの場合(リモート側に読み込みたいファイルが存在する) - - (手順1)ローカル側はLocalDGMの相当する空のファイルを作成し、socketを持つ - - (手順2)リモート側はローカルの空ファイルのploxyを作成する - - (手順3)リモート側はploxyに対してデータをputする -- writeの場合(リモート側に書き込みたいファイルが存在する) - - (手順1)リモート側は対象ファイルにsocketを持たせる - - (手順2)ローカル側は対象のファイルに対応するploxy(RemoteDGM)を作成する - - (手順3)ローカル側はploxyのkeyに対してデータをputする - -## WordCount手順 -- (手順1)ファイル内文字列を1行ずつWordCount関数へ入力する、これをループ -- (手順2)ファイル内文字列が無くなった場合(EoF)結果を出力し、終了する -<div style="text-align: center;"> - <img src="images/wordCountStates.pdf" alt=WordCountの遷移図 width="800"> -</div> - +## ファイルQueueに対するAPI -Peek- +- Peek + - QueueのElementを参照するが、削除は行わない + - 現時点での実装は行っていない + - QueueのTopのレコードを変更せずに出力すれば良い <!-- - RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。 -->
--- a/slide/thesis.pdf.html Mon Feb 07 20:58:17 2022 +0900 +++ b/slide/thesis.pdf.html Wed Feb 09 22:26:31 2022 +0900 @@ -75,42 +75,20 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsosとその現状">GearsOSとその現状</h2> +<h2 id="gearsosのファイルシステム設計">GearsOSのファイルシステム設計</h2> <ul> - <li>信頼性の保証と拡張性の高さを目指したOSプロジェクト</li> - <li>軽量継続を用いた言語、CbC(Continuation based C)により記述される</li> - <li>ノーマルレベルとメタレベルを分離して記述する</li> - <li>現状では言語フレームワークとしてのみ機能する</li> - <li>OSとして動作するには多くの機能の開発が必要 + <li>GearsOSには現時点でファイルシステムが存在していない</li> + <li>GearsOSのファイルシステムの設計と実装を行った</li> + <li>GearsOSの特性に合わせた実装 <ul> - <li>その中の一つにファイルシステムが挙げられる</li> + <li>CodeGear/DataGearによる継続処理</li> + <li>同じくGear概念を持つ分散フレームワークChristieの仕組みを用いた</li> </ul> </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="従来の物より発展した分散ファイルシステムの設計">従来の物より発展した分散ファイルシステムの設計</h2> -<ul> - <li>データベース的なレコード操作によるアクセス + <li>将来的に重要な機能をOSに取り込みたい <ul> - <li>ファイルに対する全ての操作がTransactionとなる</li> - </ul> - </li> - <li>既存ではアプリケーションが担当する機能を取り込む - <ul> - <li>バックアップの管理</li> - <li>ファイルの型の認識</li> - </ul> - </li> - <li>自律分散を目指した分散ファイルシステム - <ul> - <li>特定のサーバーを中枢にしなくても良い</li> - <li>分散フレームワークChristieの仕組みにより実現する</li> + <li>バックアップ</li> + <li>ファイルの型認識</li> </ul> </li> </ul> @@ -121,15 +99,14 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="cbc-continuation-based-c">CbC (Continuation based C)</h2> +<h2 id="gearsos">GearsOS</h2> <ul> - <li>C言語の拡張言語である</li> - <li>関数に代わる軽量継続をメインに記述する</li> - <li>Gearというプログラム概念 + <li>関数でなくGearという単位を用いて記述する <ul> <li>CodeGear <ul> <li>従来のThreadにあたる</li> + <li>goto文(jump命令)を使って遷移する</li> </ul> </li> <li>DataGear @@ -137,14 +114,15 @@ <li>従来の変数データにあたる</li> </ul> </li> + <li>スタックを持たないため軽量継続と呼ぶ</li> </ul> </li> - <li>DataGearを受け取り処理を行う(InputDataGear)</li> - <li>処理の結果をDataGearに書き出す(OutputDataGear)</li> + <li>CodeGearは処理を行う際、DataGearを参照し処理を行う(InputDataGear)</li> + <li>CodeGearは処理の終了後、以降に必要なデータをDataGearとして出力する(OutputDataGear)</li> </ul> <div style="text-align: center;"> - <img src="images/cgdg.pdf" alt="CodeGearとDataGearの関係" width="800" /> + <img src="images/cg-dg.pdf" alt="cgdgの関係図" width="800" /> </div> @@ -153,23 +131,26 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="cbcのサンプルプログラム">CbCのサンプルプログラム</h2> -<pre><code>__code CG2(int num3){ - printf("num = %d\n", num3); - exit(0); -} - -__code CG1(int num, int num1){ - int num2 = num + num1; - goto CG2(num2); -} - -int main(){ - int a = 2; - int b = 3; - goto CG1(a, b); -} +<h2 id="gearsosのinterface">GearsOSのInterface</h2> +<ul> + <li>APIの宣言を行う + <ul> + <li>定義ファイル(.h)に記述を行う</li> + <li>APIとなるCodeGearとその参照するDataGearを宣言する</li> + <li>DataGear/CodeGearの一時的な置き場としての役割を持つ + <pre><code>typedef struct Tree<>{ +union Data* tree; +struct Node* node; +__code put(Impl* tree,Type* node, __code next(...)); +__code get(Impl* tree, Type* node, __code next(...)); +__code remove(Impl* tree,Type* node, __code next(...)); +__code next(...); +} Tree; </code></pre> + </li> + </ul> + </li> +</ul> @@ -195,9 +176,8 @@ </li> </ul> </li> - <li>ユーザーが記述する上では普段は意識しない</li> + <li>メタレベルの処理はトランスコンパイラにより自動に記述される</li> </ul> - <div style="text-align: center;"> <img src="images/meta-cg-dg.pdf" alt="ノーマルレベルとメタレベルの視点からのGearの関係" width="800" /> </div> @@ -208,143 +188,14 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsosの構成">GearsOSの構成</h2> +<h2 id="datagear単位のトランザクション">DataGear単位のトランザクション</h2> <ul> - <li>Interface - <ul> - <li>定義ファイル(.h)に記述を行う</li> - <li>APIとなるCodeGearとその参照するDataGearを宣言する</li> - <li>コンパイル時にContext(後述)に書き込まれる</li> - </ul> - </li> - <li>Implement - <ul> - <li>Interfaceの実装</li> - <li>プログラム内で共通して利用したい変数</li> - </ul> - </li> -</ul> - -<pre><code>typedef struct Queue<>{ - union Data* queue; - union Data* data; - - __code whenEmpty(...); - __code clear(Impl* queue, __code next(...)); - __code put(Impl* queue, union Data* data, __code next(...)); - __code take(Impl* queue, __code next(union Data* data, ...)); - __code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); - __code next(...); -} Queue; -</code></pre> -<pre><code>typedef struct SynchronizedQueue <> impl Queue { - struct Element* top; - struct Element* last; - struct Atomic* atomic; -} SynchronizedQueue; -</code></pre> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="contextとgearの関係性">ContextとGearの関係性</h2> -<ul> - <li>Context - <ul> - <li>遷移の際にデータを全て記録するオブジェクト</li> - <li>プログラムに使われるCodeGear/DataGearを管理する</li> - <li>軽量継続中、必ず引数で参照される</li> - <li>メタレベルなCodeGearからのみ参照される</li> - </ul> - </li> -</ul> -<div style="text-align: center;"> - <img src="images/Context_ref.pdf" alt="Contextの参照" width="900" /> -</div> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsosのトランスコンパイラ">GearsOSのトランスコンパイラ</h2> -<ul> - <li>CbCプログラムはトランスコンパイルによりC言語プログラムに書き換えられる + <li>GearsOSはDataGear単位でプロセスが進行する</li> + <li>従来のファイルシステムは一部の操作のみがTransactionとなっている</li> + <li>GearsOSのファイルシステムはDataGear単位で処理を行いたい <ul> - <li>トランスコンパイルの際に、メタレベルの記述が行われる - <ul> - <li>StubCodeGearの自動生成</li> - <li>Gears向けに記述された演算子(par goto、NEW)の書き換え</li> - </ul> - </li> - </ul> - </li> - <li>StubCodeGearはCbCプログラムへ直に記述することでユーザーの任意の処理に変えられる - <pre><code>__code putSynchronizedQueue_stub(struct Context* context) { - SynchronizedQueue* queue = (SynchronizedQueue*)GearImpl(context, Queue, queue); - Data* data = Gearef(context, Queue)->data; - enum Code next = Gearef(context, Queue)->next; - goto putSynchronizedQueue(context, queue, data, next); -} -</code></pre> - <pre><code>__code putSynchronizedQueue(struct Context *context,struct SynchronizedQueue* queue, -union Data* data, enum Code next) { - ~省略~ -} -</code></pre> - </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="分散フレームワークchristie">分散フレームワークChristie</h2> -<ul> - <li>Java言語で記述された分散フレームワーク</li> - <li>CbCとは異なったGearというプログラム概念がある</li> - <li>特定のkeyに対する変数データ書き込みにより通信を行う</li> - <li>自律分散の実現を目指して開発された</li> - <li>TopologyManagerという機能を持つ</li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="christieのgear">ChristieのGear</h2> -<ul> - <li>CodeGear - <ul> - <li>スレッドに相当する</li> - <li>任意のkey nameを持つDataGearを待ち合わせ、揃ったら処理が実行される</li> - </ul> - </li> - <li>DataGear - <ul> - <li>変数データに相当する</li> - <li>key nameと変数データのペアで管理される</li> - </ul> - </li> - <li>CodeGearManger - <ul> - <li>ノードに相当する</li> - <li>DataGearManagerを所持し、CodeGearとDataGearを管理する</li> - </ul> - </li> - <li>DataGearManager - <ul> - <li>データプールに相当する</li> - <li>DataGearとkeyの組み合わせを保持している</li> - <li>LocalDGMとRemoteDGMの二種類が存在する</li> + <li>軽量継続への利用が行える</li> + <li>一つのDataGearに対する操作がトランザクションとなる</li> </ul> </li> </ul> @@ -355,102 +206,16 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="datagearmanagerによる通信">DataGearManagerによる通信</h2> +<h2 id="gearsosのファイルデータ操作">GearsOSのファイルデータ操作</h2> <ul> - <li>ChristieではDataGearの送受信によりノードどうしの通信を行う</li> - <li>LocalDataGearManager (LocalDGM) - <ul> - <li>CodeGearManagerが持つ、自身のDataGearPool</li> - <li>DataGearの大半はこれを参照する</li> - </ul> - </li> - <li>RemoteDataGearManager (RemoteDGM) + <li>ファイルデータの最小の単位は任意の型を持った構造体(DataGear)である <ul> - <li>他のCodeGearManagerが持つLocalDGMに対応するploxy</li> - <li>書き込みを行うと、対応したCodeGearManagerが持つLocalDGMに書き込みがされる</li> - </ul> - </li> - <li>DataGearManagerによる通信がChristieの通信の要となっている</li> -</ul> -<div style="text-align: center;"> - <img src="images/Remote_DataGearManager.pdf" alt="RemoteDGMの関係図" width="800" /> -</div> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="topologymanagear">TopologyManagear</h2> -<ul> - <li>参加を表明したノードに対して任意の形のTopologyに接続する - <ul> - <li>接続 = RemoteDGMを作成する</li> - <li>接続されたノードは他のノードを相対的な名前で参照できる(例:Child/parent, right/leftなど)</li> + <li>ファイルレコードと名付ける</li> </ul> </li> -</ul> - -<div style="text-align: center;"> - <img src="images/TopologyManager.pdf" alt="TopologyManager" width="800" /> -</div> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfilesystemの方針">GearsFileSystemの方針</h2> -<ul> - <li>データベース的なレコード操作によるファイルアクセス - <ul> - <li>KeyValueStoreに対する書き込み</li> - </ul> - </li> - <li>ファイルのバックアップ - <ul> - <li>ディレクトリの非破壊的編集とファイルの構成方法</li> - </ul> - </li> - <li>ファイルの型の認識 - <ul> - <li>ファイルレコードを適切な形の構造体にする</li> - </ul> - </li> - <li>自律分散を目指した分散ファイルシステム - <ul> - <li>プロトコルを用いないChristieAPI</li> - </ul> - </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造14">GearsFSのファイル構造1/4</h2> -<ul> - <li>ファイルのデータ単位は任意の型を持ったレコード - <ul> - <li>断続的に分割された状態で保存される</li> - <li>Queueに保存される</li> - <li>レコードを先頭から順に読むことでファイルを構成する</li> - </ul> - </li> - <li>ファイルレコードは構造体で再現される - <ul> - <li>ファイルレコード構造体はGearsのDataGearとして利用できる</li> - <li>レコードの構造体によりOSはファイルの型を認識する - <ul> - <li>ファイルの特性に合わせ、レコードとその構成方法を適した形で構成できる</li> - </ul> - </li> - </ul> - </li> + <li>レコードは特定の順番で連続しており、Queueに保存される</li> + <li>GearsのDataGearとして利用できる</li> + <li>構造体の型により処理の分岐が行える</li> </ul> <div style="text-align: center;"> @@ -463,38 +228,33 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造24">GearsFSのファイル構造2/4</h2> +<h2 id="ファイルqueueに対するapi">ファイルQueueに対するAPI</h2> <ul> - <li>ファイルの読み込み/書き込みはStreamを通して行われる + <li>Put <ul> - <li>streamも同様にQueueで構成される</li> - <li>streamはそれぞれ特定のkey nameをもつ</li> - <li>keyを用いることでアクセスが行われる</li> + <li>Queueに対してファイルレコードを入力する</li> + <li>ファイルの更新の際に呼び出す</li> + <li>ファイルの変更をレコードとして書き込む</li> </ul> </li> - <li>最低で、Input/OutputのStreamとファイルデータを保持するmainなQueueの三つで構成される</li> - <li>Write : InputStreamに対してレコードをputすれば良い</li> - <li>Read : OutputStreamからレコードを全てtakeすれば良い</li> -</ul> - -<div style="text-align: center;"> - <img src="images/GearsFile.pdf" alt="streamによるファイルアクセス" width="800" /> -</div> - - + <li>Take + <ul> + <li>Queueからファイルレコードを取り出す</li> + <li>ファイルの中身の読み込みの際に用いる</li> + <li>Queue内のレコードをループで全て取り出せば良い + <pre><code>typedef struct Queue<>{ +union Data* queue; +union Data* data; -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造34">GearsFSのファイル構造3/4</h2> -<ul> - <li>ChristieのDataGearManagerに相当する</li> - <li>GearsOSのファイルは大域的な資源である - <ul> - <li>複数のプロセスより競合的なアクセスが行われる</li> - <li>OutputStreamは複数のアクセスが行われても整合性が保たれる必要がある</li> - <li>CAS(Compare And Swap)が採用されたSynchronizedQueueを用いる</li> +__code whenEmpty(...); +__code clear(Impl* queue, __code next(...)); +__code put(Impl* queue, union Data* data, __code next(...)); +__code take(Impl* queue, __code next(union Data* data, ...)); +__code isEmpty(Impl* queue, __code next(...), __code whenEmpty(...)); +__code next(...); +} Queue; +</code></pre> + </li> </ul> </li> </ul> @@ -505,16 +265,19 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのファイル構造44">GearsFSのファイル構造4/4</h2> +<h2 id="gearsosのファイル">GearsOSのファイル</h2> <ul> - <li>stream、mainQueueはDataGearに相当し、keyによるアクセスが行われる</li> - <li>Queueは赤黒木に保持される</li> - <li>key nameで探索が行われ参照される</li> - <li>DGM書き込みは対象のkey nameを指定する</li> + <li>単独のQueueのみではファイル操作に耐えることができない</li> + <li>GearsOSのファイルは複数のQueueをkey nameをつけて保持するリストとなる + <ul> + <li>主体となるデータレコードを保持するQueue</li> + <li>Input/OutputStreamとなるQueue</li> + <li>通信処理を行う際に任意に利用したいデータを受けるQueue</li> + </ul> + </li> + <li>ChristieのDataGearManagerの仕組みを用いる</li> + <li>ファイルであると同時に通信そのものでもある</li> </ul> -<div style="text-align: center;"> - <img src="images/newGearsFile.pdf" alt="DataGearの保存形式" width="800" /> -</div> @@ -522,14 +285,32 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="遠隔からのファイル操作">遠隔からのファイル操作</h2> +<h2 id="datagearmanager">DataGearManager</h2> <ul> - <li>GearsOSのファイルは、ファイル通信そのものにも相当する</li> - <li>RemoteDGMの仕組みを用いることで遠隔からのファイル読み込み/書き込みを行う</li> + <li>keyとvalueの組み合わせとなるDataGearを保持するデータプール</li> + <li>ChristieではCodeGearManagerと呼ばれるノードがCodeGearとDataGearを管理する</li> + <li>LocalDGMはノード本体に対応するデータプールである + <ul> + <li>CodeGearはLocalDGMに対してDataGearを参照する</li> + </ul> + </li> + <li>RemoteDGMは接続する相手ノードに対応するデータプールploxyである + <ul> + <li>RemoteDGMに対してDataGearを書き込むことで、対応するノードのLocalDGMにデータが書き込まれる</li> + </ul> + </li> + <li>GearsFSも同様にファイルploxyを通して通信を行う</li> </ul> + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="datagearmanager-1">DataGearManager</h2> <div style="text-align: center;"> - <img src="images/socketCom.pdf" alt="socketを通じたレコード送信" width="800" /> + <img src="images/Remote_DataGearManager.pdf" alt="RemoteDGMの関係図" width="800" /> </div> @@ -538,44 +319,20 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="socketからの受信データ取り出し">socketからの受信データ取り出し</h2> +<h2 id="socket付きqueueの実装">socket付きQueueの実装</h2> <ul> - <li>socketはImplementに記述される</li> - <li>LocalDGMに相当するファイルは、接続先socketから送信されたデータを取り出す</li> - <li>APIとして記述される</li> - <li>取り出されたデータは次の継続先でQueueに対してputされる</li> -</ul> - -<pre><code>__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenEOF(...), __code whenError(...)){ - union Data* recv_data; - recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0); - if (recv_size == -1) { - printf("recv error\n"); - goto whenError(...); - } - 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); + <li>socketに接続されたQueueにより通信APIの記述を行った</li> + <li>GearsOS上でのsocket操作の記述</li> + <li>Localなqueueに対してRemoteのqueueがソケット接続を行う + <pre><code>TQueue* createRemoteDGMQueue(struct Context* context, char* sNum) { + struct TQueue* tQueue = new TQueue(); + struct RemoteDGMQueue* RemoteDGMQueue = new RemoteDGMQueue(); + RemoteDGMQueue->atomic = createAtomicReference(context); + RemoteDGMQueue->socket = createSocketRemoteDGMQueue(sNum); } </code></pre> + </li> +</ul> @@ -583,23 +340,18 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="remotedgmのsocketによるデータ送信">RemoteDGMのsocketによるデータ送信</h2> +<h2 id="remotequeue側からの送信">RemoteQueue側からの送信</h2> <ul> - <li>RemoteDGM側はsocketを用いてデータを送信する</li> - <li>Queueに対してputされたデータを送信する</li> - <li>putCodeGearの直後に呼び出される + <li>QueueのPutAPIの後に遷移される</li> + <li>putしたデータをsocketを通じて送信する</li> + <li>将来的にsendではなくwriteを用いる <pre><code>__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"); - goto whenError(); - } - recv_size = recv(cQueue->socket, &recv_buf, 1, 0); - if (recv_size == -1) { - printf("recv error\n"); - goto whenError(); - } + //error処理は省略 goto next(...); } </code></pre> @@ -612,12 +364,91 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="wordcount例題">WordCount例題</h2> +<h2 id="localqueue側の受信">LocalQueue側の受信</h2> +<ul> + <li>APIとしてsocketのデータを取り出す</li> + <li>取り出されたデータはQueueにputされる</li> + <li>union Data型でデータを受け取りmain側で処理を行う</li> + <li>取り出されたデータはmain側で処理される</li> + <li>将来的にrecvでなくreadを用いる + <pre><code>__code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenError(...)){ + int recv_size, send_size; + char send_buf; + + union Data* recv_data; + recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0); + + //error処理は省略 + Gearef(context, cQueue)->data = recv_data; + goto putLocalDGMQueue(recv_data, next); +} +</code></pre> + </li> +</ul> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="ファイル単位のsocket通信">ファイル単位のsocket通信</h2> <ul> - <li>ChristieAPIの構成をWordCount例題を通して行った</li> - <li>ファイルの中の文字列を1行ずつ読み取り、ファイル内の文字数と行数を調べる</li> - <li>ファイルの送信と文字列のカウントをそれぞれ別ノード上で行うことで、ファイル読み込みとファイルレコードの通信処理が構成できる</li> + <li>実際のファイルは複数のQueueを持つ一つのリストである</li> + <li>Queue単体でなく、リスト(ファイル)単位でsocketを持つ必要がある</li> + <li>リストは赤黒木となる</li> + <li>DataGearをputするkeyを指定して書き込みを行う + <ul> + <li>Localなファイルの同一のQueueに対して書き込みが行われる</li> + </ul> + </li> </ul> +<div style="text-align: center;"> + <img src="images/socketCom.pdf" alt="socketを通じたレコード送信" width="800" /> +</div> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="main部分によるapi">main部分によるAPI</h2> +<ul> + <li>readの場合(リモート側に読み込みたいファイルが存在する) + <ul> + <li>(手順1)ローカル側は空のファイルを作成し、socketを持たせる</li> + <li>(手順2)リモート側は, ローカル側の持つ空ファイルのploxyを作成する</li> + <li>(手順3)リモート側はploxyに対して、目的のファイルのデータをputする</li> + </ul> + </li> + <li>writeの場合(リモート側に書き込みたいファイルが存在する) + <ul> + <li>(手順1)リモート側は対象ファイルにsocketを持たせる</li> + <li>(手順2)ローカル側は対象のファイルに対応するploxyを作成する</li> + <li>(手順3)ローカル側はploxyのkeyに対してデータをputする</li> + </ul> + </li> +</ul> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="wordcountの例題">wordCountの例題</h2> +<ul> + <li>DataGearManagerによるファイル通信APIはWordCount例題を目指して設計した + <ul> + <li>ファイル内の文字列を1行づつ受け取り、文字列,行数をカウントする例題</li> + </ul> + </li> + <li>文字列送信側とCount側を別ノード上で行うことで、ファイルの呼び出しと通信処理が構成できる</li> +</ul> +<div style="text-align: center;"> + <img src="images/wordCountDGM.pdf" alt="リモートDGMによるWordCount" width="800" /> +</div> @@ -643,15 +474,17 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのディレクトリ">GearsFSのディレクトリ</h2> +<h2 id="これから実装が必要となる機能">これから実装が必要となる機能</h2> <ul> - <li>ディレクトリを赤黒木で実装する</li> - <li>赤黒木のノードとしてファイル/ディレクトリが保存される</li> - <li>階層構造はファイル名がkey, データとしてinodeが保存される</li> + <li>keyアクセスに対応したファイル通信 + <ul> + <li>単一のQueueによる通信は確認が行えた</li> + </ul> + </li> + <li>ファイル保存</li> + <li>バックアップ機能</li> + <li>並列処理</li> </ul> -<div style="text-align: center;"> - <img src="images/GearsDirectory.pdf" alt="GearsOSのディレクトリ" width="500" /> -</div> @@ -659,11 +492,10 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのバックアップ12">GearsFSのバックアップ(1/2)</h2> +<h2 id="gearsosのディレクトリとバックアップ">GearsOSのディレクトリとバックアップ</h2> <ul> - <li>ディレクトリツリーを非破壊的な編集で更新する</li> - <li>木構造の編集前の構造が履歴となる</li> - <li>保存容量の圧迫は対応が必要となる</li> + <li>又吉雄斗による並行研究にて、inodeによるファイルシステムが開発されている</li> + <li>赤黒木の非破壊な編集により、ディレクトリの履歴を残すことができる</li> </ul> <div style="text-align: center;"> <img src="images/nonDestroyTreeEdit.pdf" alt="非破壊的なツリー編集" width="800" /> @@ -675,34 +507,44 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsfsのバックアップ22">GearsFSのバックアップ(2/2)</h2> +<h2 id="生成形の問題点">生成形の問題点</h2> <ul> - <li>ファイルレコードを変更差分として構成する + <li>GearsOSのメタレベルの処理の記述はトランスコンパイラにより行われる</li> + <li>場合によりメタレベルの記述を行わなくてはならない <ul> - <li>GithubやMercurialのようなバージョン管理が行える</li> - <li>特定の日時までのレコードを読めばよい</li> + <li>他のInterfaceを継承したオブジェクトからのDataGear継承 + <ul> + <li>例)Queueからのデータ取り出し</li> + <li>トランスコンパイラはどのInterfaceが持つDataGearを参照するべきか判断が難しい</li> + </ul> + </li> </ul> </li> - <li>定期的なファイルの再構築が必要</li> </ul> - +<pre><code>__code Task2(TQueue* localDGMQueue){ + goto localDGMQueue->take(Task3); +} -</div> +__code Task3(TQueue* localDGMQueue, FileString* string){ + printf("take[%s] [num:%d]\n", string->str, string->size); + goto getData(); +} -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsfsの並列処理">GearsFSの並列処理</h2> -<ul> - <li>par gotoを用いる案 - <ul> - <li>処理速度が遅い</li> - <li>トランスコンパイラへの依存度が高い</li> - <li>現状バグが存在している</li> - </ul> - </li> - <li>新しく並列処理を開発する</li> -</ul> +//プログラマが実装したいstub +__code Task3_stub(struct Context* context){ + TQueue* localDGMQueue = (struct TQueue*)Gearef(context, TQueue)->tQueue; + FileString* string = Gearef(context, TQueue)->data; + goto Task3(context, localDGMQueue, string); +} + +//自動生成されたErrorなstub +__code Task3_stub(struct Context* context) { + TQueue* localDGMQueue = Gearef(context, TQueue); + FileString* string = Gearef(context, FileString); + goto Task3(context, localDGMQueue, string); +} +</code></pre> @@ -710,45 +552,22 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="gearsosの問題点">GearsOSの問題点</h2> +<h2 id="並列処理構文par-gotoが持つ問題">並列処理構文par gotoが持つ問題</h2> <ul> - <li>記述難易度の高さ</li> - <li>Contextの操作 + <li>par gotoとはGearsOSに実装された並列処理構文である</li> + <li>par gotoはトランスコンパイラへの依存性が高い <ul> - <li>トランスコンパイラでは対応できない継承が存在する</li> - <li>場合によりメタレベルの記述を行わなくてはならない</li> - </ul> - </li> - <li>軽量継続 - <ul> - <li>ループ記述が複雑</li> - <li>goto遷移以降の記述は実行されない</li> + <li>stubCodeGearのように任意な書き換えが行えない</li> </ul> </li> - <li>par gotoの実用が難しい</li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="課題">課題</h2> -<ul> - <li>TopologyManagerの実装 + <li>StreamQueueに対するput/takeの並列処理の実装をpar goto構文で試みた</li> + <li>特定のCodeGearの宣言のみでしか正常な処理が生成されない <ul> - <li>ファイルの配線を行う</li> - <li>DNSの役割</li> - <li>クラスターの管理</li> + <li>Interfaceに記述されたAPICodeGearではバグが生じる</li> + <li>par gotoでの使用を前提としたCodeGearを書かなくてはならない</li> </ul> </li> - <li>並列処理方法の決定 - <ul> - <li>par gotoの改良</li> - <li>新たな案を実装する</li> - </ul> - </li> + <li>処理が重いという問題点も存在する</li> </ul> @@ -759,30 +578,40 @@ <!-- _S9SLIDE_ --> <h2 id="結論">結論</h2> <ul> - <li>GearsFileSystemの設計 + <li>GearsOSのファイルの設計を行った <ul> - <li>ファイルの構成方法 + <li>ファイルの構造の設計</li> + <li>socketによる通信部分の実装</li> + <li>単純化した通信APIの記述</li> + <li>GearsOSの調査</li> + </ul> + </li> + <li>ファイルploxyによる通信実現を行いたい</li> +</ul> + + + +</div> + +<div class='slide'> + <!-- _S9SLIDE_ --> +<h2 id="これからの課題">これからの課題</h2> +<ul> + <li>TopoplogyManagerの設計 + <ul> + <li>参加したノードを任意の形のTopologyに接続する機能</li> + <li>ファイルシステム向けの機能を追加したい <ul> - <li>keyによってアクセスされるQueueのリスト</li> + <li>DNS</li> + <li>中枢としてのTopologyのノード監視</li> </ul> </li> - <li>ファイル操作API - <ul> - <li>ChristieAPI</li> - <li>レコード単位で操作される</li> - </ul> - </li> - <li>ファイル送受信の実装 - <ul> - <li>RemoteDGM(ファイルploxy)</li> - </ul> - </li> - <li>ディレクトリの仕組み - <ul> - <li>赤黒木を用いる</li> - <li>非破壊的な編集によるログ</li> - </ul> - </li> + </ul> + </li> + <li>Securityシステムの追加 + <ul> + <li>証明書などによるファイル操作制限</li> + <li>不正な分散ファイルシステムへのアクセス</li> </ul> </li> </ul> @@ -793,43 +622,7 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="この先保留ページ">この先保留ページ</h2> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="gearsosのimplementation">GearsOSのImplementation</h2> -<ul> - <li>Interfaceの実装である</li> - <li>定義ファイル(.h)に記述を行う</li> - <li>必ず継承元のInterfaceを記述する必要がある</li> - <li>プロセス内のCodeGearが共通して使いたい変数を記述する - <pre><code>typedef struct SynchronizedQueue <> impl Queue { -struct Element* top; -struct Element* last; -struct Atomic* atomic; -} SynchronizedQueue; -</code></pre> - </li> -</ul> - - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="研究成果">研究成果</h2> -<ul> - <li>連続するレコードで構成されるGearsOSファイルの設計</li> - <li>keyアクセスを用いたファイルに対するRead, writeAPI</li> - <li>赤黒木を用いたディレクトリシステムの構築</li> - <li>ファイルのバックアップ考察</li> - <li>ploxyを用いたファイルの送受信</li> -</ul> +<h2 id="この先保留">この先保留</h2> @@ -837,43 +630,20 @@ <div class='slide'> <!-- _S9SLIDE_ --> -<h2 id="api手順">API手順</h2> +<h2 id="ファイルqueueに対するapi--peek-">ファイルQueueに対するAPI -Peek-</h2> <ul> - <li>readの場合(リモート側に読み込みたいファイルが存在する) + <li>Peek <ul> - <li>(手順1)ローカル側はLocalDGMの相当する空のファイルを作成し、socketを持つ</li> - <li>(手順2)リモート側はローカルの空ファイルのploxyを作成する</li> - <li>(手順3)リモート側はploxyに対してデータをputする</li> - </ul> - </li> - <li>writeの場合(リモート側に書き込みたいファイルが存在する) - <ul> - <li>(手順1)リモート側は対象ファイルにsocketを持たせる</li> - <li>(手順2)ローカル側は対象のファイルに対応するploxy(RemoteDGM)を作成する</li> - <li>(手順3)ローカル側はploxyのkeyに対してデータをputする</li> + <li>QueueのElementを参照するが、削除は行わない</li> + <li>現時点での実装は行っていない</li> + <li>QueueのTopのレコードを変更せずに出力すれば良い +<!–</li> </ul> </li> + <li>RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。 +–></li> </ul> - - -</div> - -<div class='slide'> - <!-- _S9SLIDE_ --> -<h2 id="wordcount手順">WordCount手順</h2> -<ul> - <li>(手順1)ファイル内文字列を1行ずつWordCount関数へ入力する、これをループ</li> - <li>(手順2)ファイル内文字列が無くなった場合(EoF)結果を出力し、終了する</li> -</ul> -<div style="text-align: center;"> - <img src="images/wordCountStates.pdf" alt="WordCountの遷移図" width="800" /> -</div> - -<!-- -- RocalDGMを立ち上げるにはDataSegmentクラスが提供する、connectメソッドを用い、接続したいポートのipアドレスとport番号、そして任意のManager名を指定することで立ち上げる。 ---> - </div>