# HG changeset patch # User ichikitakahiro # Date 1620302596 -32400 # Node ID d5db71167d90e56e8fbb01d52105b200a4275fd3 # Parent d0df325948740275326cf8f6c70c4f514acfa99d ... diff -r d0df32594874 -r d5db71167d90 Paper/paper.pdf Binary file Paper/paper.pdf has changed diff -r d0df32594874 -r d5db71167d90 Paper/paper.tex --- a/Paper/paper.tex Thu May 06 16:47:35 2021 +0900 +++ b/Paper/paper.tex Thu May 06 21:03:16 2021 +0900 @@ -25,7 +25,7 @@ ndkeywordstyle={\footnotesize\ttfamily}, % stringstyle={\footnotesize\ttfamily}, breaklines=true, - captionpos=b, + captionpos=t, columns=[l]{fullflexible}, % xrightmargin=0zw, % xleftmargin=1zw, % @@ -33,7 +33,7 @@ numberstyle={\scriptsize}, % stepnumber=1, numbersep=0.5zw, % - lineskip=-0.5ex, + lineskip=-0.5ex } \usepackage{caption} @@ -109,10 +109,10 @@ UNIXファイルシステムではファイルに構造を持たず, カーネルがファイルを単純なバイト配列とみなして処理が行われ, ファイルの実際の取り扱いはプログラムが判断する. ユーザの視点ではファイルを取り扱う際に, OSレベルの観点からファイルを構成する必要がなく, ファイルの拡張子を任意のアプリケーションに適したものにするだけで良い. -全てのファイルはi-nodeと呼ばれるユニークな番号をもち, ファイルのメタデータは全てi-node内に格納されている. i-nodeはファイルの探索の際などに用いられ, ユーザはstat()と呼ばれるシステムコール により共通的にファイル情報を得ることができる. +全てのファイルはi-nodeと呼ばれるユニークな番号をもつデータブロックで表される, ファイルのメタデータは全てi-node内に格納されている. ディレクトリ を格納する i-node はファイルの探索の際などに用いられ, ユーザはstat()と呼ばれるシステムコール により大きさなどのファイルのメタ情報を得ることができる. -また,UNIXは階層型の仮想ファイルシステムを搭載している. -ネットワークを経由してファイルシステムにアクセスする際は, 木構造に構成されたディレクトリTree にリモート先のファイルシステムをマウントすることにより参照することができる. +また, UNIXはデバイスにまたがる仮想ファイルシステムを搭載している. +例えばネットワークを経由してファイルシステムにアクセスする際は, 木構造に構成されたディレクトリTree にリモート先のファイルシステムをマウントすることにより参照することができる. UNIXbaseのファイルシステムを比較・検討をしながらGearsOSを構成していく. @@ -121,15 +121,15 @@ \section{Continuation based C} GearsOSはC言語の下位言語であるContinuation based Cを用いて記述されている. CbCは関数呼び出しでなく, 継続を導入しており, スタック領域を用いずjmp命令でコード間を移動することにより軽量な継続を実現している. CbCではこの継続を用いてfor文などのループの代わりに再起呼び出しを行う. 実際のOSやアプリケーションを記述する際にはGCCまたはLLVM/clangのCbC実装を用いる. -CbCでは関数の代わりにCodeGearという単位でプログラミングを行う. CodeGearは\texttt{\_\_code}で宣言を行い, 各CodeGearはDataGearと呼ばれる変数データを入力として受け取り, その結果を別のDataGearに書き込む. 特に入力のDataGeatをInputDataGear, 出力されるDataGearを OutputDataGearと呼ぶ. CodeGearとDataGearの関係図を図\ref{fig:cgdg}に示す. +CbCでは関数の代わりにCodeGearという単位でプログラミングを行う. CodeGearは\texttt{\_\_code}で宣言を行い, 各CodeGearはDataGearと呼ばれる変数データを入力として受け取り, その結果を別のDataGearに書き込む. 特に入力のDataGearをInputDataGear, 出力されるDataGearを OutputDataGearと呼ぶ. CodeGearとDataGearの関係図を図\ref{fig:cgdg}に示す. CodeGearは関数呼び出しのスタックを持たないため, 一度CodeGearを遷移すると元の処理に戻ってくることができない. -\begin{figure}[tb] +\begin{figure}[h] \begin{center} \includegraphics[width=80mm]{images/cgdg.pdf} \end{center} - \caption{CodeGearと入出力の関係図} + \caption{CodeGearと入出力の関係図} \label{fig:cgdg} \end{figure} @@ -160,7 +160,7 @@ しかし, 実際にはCodeGearから別のCodeGearへの遷移にはデータの整合性の確認などのメタ計算が必要となる. コード間の遷移に必要となるメタ計算は, MetaCodeGearと呼ばれるCodeGearごとに実装されたCodeGearで行う. MetaCodeGearで参照されるDataGearをMetaDataGearと呼び, また, CodeGearの直前に実行されるMetaCodeGearをStubCodeGearと呼ぶ. -これらMeta計算部分を含めたCodeGearの遷移とDataGearの関係性を図示すると図\ref{fig:meta-cgdg} の下段の形に表せる. CordGearの実行前後に実行されるMetaCodeGearや入出力のDataGearをMetaDagaGearから取り出すなどのメタ計算が加わる. +これらMeta計算部分を含めたCodeGearの遷移とDataGearの関係性を図示すると図\ref{fig:meta-cgdg} の下段の形に表せる. CordGearの実行前後に実行されるMetaCodeGearや入出力のDataGearをMetaDataGearから取り出すなどのメタ計算が加わる. MetaCodeGearは詳細な処理の変更や, スクリプトに問題がある場合を除き, プログラマが直接実装する必要がなく, GearsOSが持つPerlスクリプトにより, GearsOSがビルドされる際に生成される. @@ -170,19 +170,19 @@ 計算に必要なデータ構造と処理を持つデータ構造であることから, contextは従来のOSのプロセスに相当し, ユーザープログラムごとにcontextが存在している. -\begin{figure}[tb] +\begin{figure}[h] \begin{center} \includegraphics[width=80mm]{images/meta-cg-dg.pdf} \end{center} - \caption{CodeGearとMetaCodeGearの関係図} + \caption{CodeGearとMetaCodeGearの関係図} \label{fig:meta-cgdg} \end{figure} -\begin{figure}[tb] +\begin{figure}[h] + \caption{Contextを介したCodeGearの継続} \begin{center} \includegraphics[width=80mm]{images/Context_ref.pdf} \end{center} - \caption{Contextを介したCodeGearの継続} \label{fig:context} \end{figure} @@ -209,7 +209,7 @@ DataGearManagerはLocalとRemoteに区分することができ, LocalDGMはCGM自身が所持するDGのプールであり, Localにputすることにより自身の持つkeyにDGを送ることができる. 対するRemoteDataGearManagerはCGMが配線されている別のCGMが持つDGのプールである. つまり, 任意の接続されたRemoteDGMにDGをputすると, 対応したCGM(ノード)が持つDGMのpoolにDGが送信される. RemoteDGMにDGをputする処理が分散処理の肝となっている. RemoteDataGearManagerの仕組みを図\ref{fig:RDGM}に示す. -\begin{figure}[tb] +\begin{figure}[h] \begin{center} \includegraphics[width=80mm]{images/Remote_DataGearManager.pdf} \end{center} @@ -230,7 +230,7 @@ \subsection{Christieのサンプルコード} コード\ref{codes: StartHelloWorld}, \ref{codes: StartHelloCG}はChristieで記述したHello Worldのプログラムである. ユーザープログラムはStartCodeGearクラスを継承したクラス(コード\ref{codes: StartHelloWorld})から開始する. -CodeGearManagerはポート番号を指定した上でcreatCGMメソッドを呼び出すことにより生成される. 生成されたCodeGearManagerは CGM名.setup にてCGMに処理させたいスレッド, つまりCodeGearを持たせることができる. +CodeGearManagerはポート番号を指定した上でcreateCGMメソッドを呼び出すことにより生成される. 生成されたCodeGearManagerは CGM名.setup にてCGMに処理させたいスレッド, つまりCodeGearを持たせることができる. コード \ref{codes: StartHelloCG}はHeloWorldCodeGearの記述である. HelloWorldCodeGearではkey: helloWorldにputされた文字列をprint出力するという単純な処理を記述している. @@ -284,18 +284,17 @@ 動的Topologyは参加を表明したノードに対し, 自動的にノード同士の配線を行う. 例えばTreeを構成する場合, 参加したノードから順番にrootから近い役割を与える. -\section{Gearを用いたファイルシステムの構成} +\section{GearOSのファイルアクセス} Christieの分散ファイルシステムをWordCount例題を通して構築する. WordCount例題とは指定したファイルの中身の文字列を読み取り, 文字数と行列数, 加えて文字列を出力すると言う例題である. -CbCで記述した場合のWordCountプログラムの遷移図を示した図を図\ref{fig:WCGearbox}に示す. +CbCで記述した場合のWordCountプログラムの遷移図を示した図を図に示す. WordCountの例題は大きく分けて, 指定した名前のファイルをFIle構造体としてOpenするFileOpenスレッド, ファイル構造体を受け取り文字列(word)を表示し文字数(bytes)と行数(lines)をCountUpするWordCountスレッドの二つのCodeGearで記述することができる. -図\ref{fig:WCGearbox}で示したWordCountの遷移図はFileをオープンしたCGとWordCountのCGを巡回することにより, +図\ref{fig:WCStates}で示したWordCountの遷移図はFileをオープンしたCGとWordCountのCGを巡回することにより, ブロックを処理していく. - \ref{codes: StartHelloCG} - \ref{fig:WCStates} - \ref{fig:WCDGMwChristie} - -\begin{figure}[tb] +WordCountとファイルの接続はUNIXのシェルのようにプログラムの外で接続される. この接続はTopologyManagerによって接続される. + +ファイルシステム側ではBlockを接続されたCGへgotoで接続すればよい. ここではUNIX上のGearsOSであるのでUNIXのファイルシステムAPIを経由してBlockを投げる. この記述ではファイルの読み込みとWordCountの処理がコードとデータの流れに沿って起こる. +\begin{figure}[h] \begin{center} \includegraphics[width=80mm]{images/wordCountStates.pdf} \end{center} @@ -303,13 +302,42 @@ \label{fig:WCStates} \end{figure} +\section{ChristieAPI} +GearsOS上のファイルは名前のついた大域的な資源であり, 複数のプロセスから競合的にアクセスされる. +前節のAPIではファイルとWordCountが直接的に結合されているので競合的なアクセスは起きない. +そこでDataGears Streamに名前をつけてアクセスするAPIを導入する. これはjava versionのChristieのGearsOS版となる. + +図\ref{fig:WCDGMwChristie}はFileと分離されたWordCountの結合を表している. +File InterfaceはBlockをWordCountに送信するが, 直接的に送るのではなく, WordCountの名前がついたDataGearManagerのploxyに書き込む. FileInterfaceからはRemoteDGMとして見れる. +RemoteDGMに書き込む方法は二通りあり, 一つはgoto文のOutPutに指定する方法がある. +この方法は従来のAPIをつかった方法とほぼ同じになる. +もう一つはRemoteDGMへputするAPIを使う. この手法では複数のRemoteDGMに書き込むことができる. + +DGの受け取りはCodeGearの入力で行われる. 入力の接続はTopologyManagerに行われるが, 入力のDGにkeyを設定するmetaCG を使う. +他のCGがputしたDGに対応するCGがそのcontextで実行される. 実行されたCGはDGをDGMに書き込むことで計算が進む. + +同じ名前(key)を持つDGは複数のCGから競合的にアクセスされる. RemoteDGMはLocalDGMのploxyであり, 他の計算ノードにあって良い. +DGMの同期はGearsOSが管理する. + +FileのeofなどはDGにフラグをつけて関数型プログラミング的に処理される. + +図\ref{fig:WCDGMwChristie}はWordCountをRemoteDGMを用いて記述した際の遷移図である. +NodeAにて任意のファイルを開きDGMを通して1行ごとに文字列をNodeBに送信(put), NodeBにてWordCountの処理を行い, OutputとしてNodeBからWordCountの処理を送り返す. +NodeA側から送信するファイルの行がなくなった場合, NodeB側にeofを送信して双方の処理を終了するといった流れになる. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=80mm]{images/wordCountDGM.pdf} + \end{center} + \caption{WordCountDGM with Christie} + \label{fig:WCDGMwChristie} +\end{figure} \begin{lstlisting}[frame=lrbt,label=codes: UnixFI,caption={UnixFileImpl.cbc}] #include #impl UnixFileImp as "UnixFileImpl.h" - File* createUnixFileImpl(struct Context* context) { File *file = new File(); file->FileImpl = (union Data*)new FileImpl(); @@ -387,16 +415,26 @@ \end{lstlisting} -\begin{figure}[tb] - \begin{center} - \includegraphics[width=80mm]{images/wordCountDGM.pdf} - \end{center} - \caption{WordCountDGM with Christie} - \label{fig:WCDGMwChristie} -\end{figure} -\begin{figure}[tb] +\section{FileSystem Implementation} +GearsOS独自のファイルシステムは単なるDGのリストとなる. 要求されたDGをリストから参照してgotoまたはputで送信する. acknowledgeを待って順次送信すれば良い. この場合ではDGはメモリ上にのみ存在する. + +持続的なファイルシステムの場合はリストまたはB-TreeをSSDやMVMEなどの持続性のあるデバイスに格納する. +これらのデバイスは単なるメモリとして扱ってよく, メモリ上のデータ構造と同様に構築する. + +メモリ領域の管理はメタ計算として実装される. メタレベルでGCやDataGear Poolを用いて不要になったメモリの回収を行う. + +このようにDGM自体がファイルの概念に対応する. DGMに格納されているDGには型があり, 正しく接続するには型変換を提供する必要がある. UNIX的にstd Dataのようなものを提供しても良い. +DGMのデータ構造は複数のものが可能になり, Red-Black-Treeあるいは単方向リストあるいは双方向リストを使うことができる. +物理デバイス上の重複管理や変更履歴管理もDGMが行う. しかし, ノーマルレベル的には単なるDGのリストとして扱う. つまり検証上は単なるリストとなる. +図\ref{fig:fileImpletation}はファイルを別ノードにて参照する際の遷移図である. +WordCountと同様な1行ごとの文字列に加え, 読み込みモード, ファイルのパスなどをputする. 送信の制御としてAckもデータとして送信している. +図\ref{fig:filePersist}はデバイス上に保存されたDGMをLocalDGMとして呼び出し, 操作を行う際の遷移図となる. + + + +\begin{figure}[h] \begin{center} \includegraphics[width=80mm]{images/fileImplementation.pdf} \end{center} @@ -404,7 +442,7 @@ \label{fig:fileImpletation} \end{figure} -\begin{figure}[tb] +\begin{figure}[h] \begin{center} \includegraphics[width=80mm]{images/filePersistency.pdf} \end{center} @@ -412,6 +450,35 @@ \label{fig:filePersist} \end{figure} +\section{競合的アクセスを含む分散計算の検証} +ChristieAPIは競合的なアクセスを含むので逐次型プログラミングのように検証することができない. TopologyManagerは名前付きDataGearManagerを相互に接続するが, これも動的に変更される. +これ全体をモデル検査することを考える. +可能な接続パターンと可能なDGMの内容のパターンを網羅すれば良い. +一般的にはこれは無限あるいは膨大となるが, 抽象化を導入することにより, より様々なレベルでの検証が可能になることが期待される. + +接続とDGMの内容のパターンが確定すれば, その範囲でプログラムは関数型プログラミングとして振る舞う. +この場合の検証はHoare Logicなどで証明的に行うことができる. 証明が複雑な場合でも, DGのパターンをメタ計算で調べるなどの手法を用いることができる. + +\section{比較とまとめ} +GearsOSにおけるファイルシステムAPIの設計に対して議論を行った. +APIは二種類あり, アプリケーションで閉じた決定的な実行を行う直接接続されたものと, もう一つはDataGearManagerに名前をつけて競合的アクセスを許す形でゆるく接続されるものである. + +DataGearManagerはファイルとして見ることもできるし, 分散環境での通信として見ることもできる. +ファイルシステムの同期, 例えばDataGearの待ち合わせはSynclonised Queue的に行われる. +Peekを用いるとブロックしない形でRead Onlyアクセスすることが可能になる. +いずれの場合もアクセスはDataGear単位であり, 不完全な状態なデータになることはない. + +UNIX FileSystemはAPI的にはFile StreamとSocket StreamはRead-Writeでアクセスする. +しかし, その設定はプログラム内部で煩雑な処理が必要となる. +GearsOSではこの部分はTopologyManagerに押し付けられている. +UNIXではStreamに型がないので不完全なデータが生じてしまう. +UNIXファイルシステムにはfsckと呼ばれる修復機能があるが, メモリに対する修復機能は存在しない. +GearsOS側ではそれらはDGMのメタな機能として実装することが可能である. +例えばメモリの一部不良などに対応するDGMを作るといったことが可能になると思われる. + +DGMの名前とその中のDataGear Streamに対応するkeyでアクセスする対象が決まる. これがUNIXでいうi-node番号に相当する. Human Readableな名前空間はそれらに対して自由に構築して良い. +UNIXのファイルシステムと異なり, i-nodeの構成と名前空間の構成は独立で良い. +例えばscrap boxのようなTag baseでのアクセスが考えられる. \begin{thebibliography}{10} @@ -419,7 +486,7 @@ \bibitem{latex}照屋 のぞみ，河野真治 : \textbf{分散フレームワークChristieの設計}．琉球大学理工学研究科修士論文 2018. \bibitem{latex}清水 隆博，河野真治 : \textbf{xv6 の構成要素の継続の分析}．OS研究会2019. \bibitem{latex}清水 隆博，河野真治 : \textbf{継続を基本とした言語による OS のモジュール化}．琉球大学理工学研究科修士論文 2020. -\bibitem{latex}清水 隆博，河野真治 : \textbf{継続を基本とした言語による OS のモジュール化}．琉球大学理工学研究科修士論文 2020. +\bibitem{latex}宮城 光輝，河野真治 : \textbf{継続を基本とした言語による OS のモジュール化}．琉球大学理工学研究科修士論文 2020. \end{thebibliography}