|
0
|
1 \chapter{Gears OS}
|
|
|
2 \section{Gears OS}
|
|
|
3 Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
|
|
|
4 Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
|
|
|
5 Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
|
|
|
6 また、接続された Data Gear 以外には参照を行わない。
|
|
|
7 Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。
|
|
|
8 処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
|
|
|
9
|
|
|
10 Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。
|
|
|
11 Meta Code Gear は通常のCode Gear の直後に遷移され、Meta Computation を実行する。
|
|
|
12
|
|
|
13 CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。
|
|
|
14
|
|
|
15 %\section{Gears OS の構成}
|
|
|
16
|
|
|
17 %\begin{itemize}
|
|
|
18 % \item Context
|
|
|
19 % \item TaskQueue
|
|
|
20 % \item TaskManager
|
|
|
21 % \item Persistent Data Tree
|
|
|
22 % \item Worker
|
|
|
23 %\end{itemize}
|
|
|
24
|
|
|
25 %図\ref{fig:gearsos} に Gears OS の構成図を示す。
|
|
|
26
|
|
|
27 %\begin{figure}[htpb]
|
|
|
28 % \begin{center}
|
|
|
29 % \scalebox{0.2}{\includegraphics{fig/gearsos.pdf}}
|
|
|
30 % \end{center}
|
|
|
31 % \caption{Gears OS の構成図}
|
|
|
32 % \label{fig:gearsos}
|
|
|
33 %\end{figure}
|
|
|
34
|
|
4
|
35 \section{Context}
|
|
|
36 Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、TaskQueue へのポインタ、Persistent Data Tree へのポインタ、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
|
|
0
|
37 Gears OS は必要な Code/Data Gear に参照したい場合、この Context を通す必要がある。
|
|
|
38 %メインとなる Context と Worker 用の Context があり、TaskQueue と Persistent Data Tree は共有される。
|
|
|
39 %Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
|
|
|
40 %Persistent Data Tree への書き込みのみで相互作用を発生させ目的の処理を達成する。
|
|
|
41
|
|
|
42 しかし、Context を直接扱うのはセキュリティ上好ましくない。
|
|
|
43 そこで Context から必要なデータを取り出して Code Gear に接続する Meta Code Gear である stub を定義し、これを介して間接的に必要な Data Gear にアクセスする。
|
|
|
44
|
|
4
|
45
|
|
|
46
|
|
2
|
47 %現在 CbC で Gears OS を記述すると通常の Computation に加えて Meta Computation である stub を記述する必要がある。
|
|
|
48 %Meta Computation
|
|
|
49
|
|
0
|
50
|
|
|
51
|
|
2
|
52 %Context や stub は Meta Computation であるため。
|
|
|
53
|
|
|
54 \section{Meta Code Gear}
|
|
4
|
55 Gears OS では Code Gear 間の遷移に Meta レベルの Meta Code Gear を挟む。
|
|
2
|
56 その様子を表したのが図 \ref{fig:metaCS}である。
|
|
4
|
57 Meta Code Gear は メモリの確保やネットワーク管理などの Meta Computation を行う Code Gear である。
|
|
|
58 通常の Code Gear ではこれらの Meta Computation は書かず、Meta Code Gear に必要に応じて記述することになる。
|
|
2
|
59 %通常レベルの Code Gear からは Meta Code Gear への継続は見えず、通常レベルの Code Gear に直接継続しているように見えるべきである
|
|
|
60
|
|
|
61 \begin{figure}[htpb]
|
|
|
62 \begin{center}
|
|
|
63 \scalebox{0.55}{\includegraphics{fig/metaCS.pdf}}
|
|
|
64 \end{center}
|
|
|
65 \caption{meta computation}
|
|
|
66 \label{fig:metaCS}
|
|
|
67 \end{figure}
|
|
|
68
|
|
|
69 \section{stub Code Gear}
|
|
|
70 Gears OS では Code Gear は Meta Code Gear に継続し、その後 Code Gear に継続すると述べたが、正確には Meta Code Gear から Code Gear に継続する際に stub Code Gear を挟む。
|
|
|
71 stub Code Gear では、Code Gear が必要とする Data Gear を context から取り出すという処理を行うものである。
|
|
|
72 stub Code Gear は Code Gear 毎に生成される。
|
|
|
73
|
|
|
74 %この機能により、CbC は Code Gear のみでなく Data Gear を単位として用いることが可能になった。
|
|
|
75 %Meta Code Gear、Meta Data Gear により meta computation を通常の Code Gear 内に記述せずにすむ、Code Gear 間に実行される Meta Code Gear で継続先を変更する、エラーハンドリングを行うといった使い方ができるようになるだろう。
|
|
|
76
|
|
4
|
77 \section{CbC による Gears OS の構文サポート}
|
|
|
78 Gears OS を現在の CbC の機能のみを用いて記述すると Context や Meta Code Gear、Meta Data Gear の記述を行わなくてはならず、これには多くの労力を要する。
|
|
|
79 そのため、この記述を助けるために Context や Meta Code Gear、Meta Data Gear を生成するスクリプトを作成した。
|
|
|
80
|
|
0
|
81
|
|
|
82 %\section{TaskQueue}
|
|
|
83 %ActiveTaskQueue と WaitTaskQueue の 2 つの TaskQueue を持つ。
|
|
|
84 %先頭と末尾の Element へのポインタを持つ Queue を表す Data Gear である。
|
|
|
85 %Element は Task を表す Data Gear へのポインタと次の Element へのポインタを持っている。
|
|
|
86 %Compare and Swap(CAS) を使ってアクセスすることでスレッドセーフな Queue として利用することが可能になる。
|
|
|
87 %
|
|
|
88 %\section{TaskManager}
|
|
|
89 %Task には Input Data Gear, Output Data Gear が存在する。
|
|
|
90 %Input/Output Data Gear から依存関係を決定し、TaskManager が解決する。
|
|
|
91 %依存関係が解決された Task は WaitTaskQueue から ActiveTaskQueue に移される。
|
|
|
92 %TaskManager はメインとなる Context を参照する。
|
|
|
93 %
|
|
|
94 %\section{Persistent Data Tree}
|
|
|
95 %非破壊木構造で構成された Lock-free なデータストアである。
|
|
|
96 %Red-Black Tree として構成することで最悪な場合の挿入・削除・検索の計算量を保証する。
|
|
|
97 %
|
|
|
98 %\section{Worker}
|
|
|
99 %TaskQueue から Task の取得・実行を行う。
|
|
|
100 %Task の処理に必要なデータは Persistent Data Tree から取得する。
|
|
|
101 %処理後、必要なデータを Persistent Data Tree に書き出して再び Task の取得・実行を行う。
|
|
|
102 %
|
|
|
103 \section{interface の記述}
|
|
|
104
|
|
|
105 interface を記述することで
|
|
|
106
|
|
4
|
107 \begin{lstlisting}[frame=lrbt,label=interface,caption={stack の interface}]
|
|
0
|
108 Stack* createSingleLinkedStack(struct Context* context) {
|
|
|
109 struct Stack* stack = new Stack();
|
|
|
110 struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
|
|
|
111 stack->stack = (union Data*)singleLinkedStack;
|
|
|
112 singleLinkedStack->top = NULL;
|
|
|
113 stack->push = C_pushSingleLinkedStack;
|
|
|
114 stack->pop = C_popSingleLinkedStack;
|
|
|
115 stack->pop2 = C_pop2SingleLinkedStack;
|
|
|
116 stack->get = C_getSingleLinkedStack;
|
|
|
117 stack->get2 = C_get2SingleLinkedStack;
|
|
|
118 stack->isEmpty = C_isEmptySingleLinkedStack;
|
|
|
119 stack->clear = C_clearSingleLinkedStack;
|
|
|
120 return stack;
|
|
|
121 }
|
|
|
122 \end{lstlisting}
|
|
|
123
|
|
|
124 %api
|
|
|
125 %impliment
|
|
|
126
|
