|
16
|
1 title: Code Gear と Data Gear を持つ Gears OS の設計
|
|
|
2 author: Mitsuki Miyagi, Shinji Kono
|
|
|
3 profile: 琉球大学
|
|
|
4 lang: Japanese
|
|
|
5 code-engine: coderay
|
|
|
6
|
|
18
|
7 # 研究目的
|
|
16
|
8
|
|
17
|
9 - 現代の OS では拡張性と信頼性を両立させることが要求されている。
|
|
16
|
10 <!--信頼性 信頼性を保証するには従来のテストとデバッグでは不十分-->
|
|
|
11 <!--信頼性を保証するには証明とモデル検査を用いる方法がある-->
|
|
17
|
12 - 信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
|
|
19
|
13 - ノーマルレベルの計算とメタレベルの計算を切り離して記述するために Code Gear と Data Gear という単位を用いている。
|
|
18
|
14 - Gears OS は Continuation based C(CbC) によってアプリケーションと OS そのものを記述する。
|
|
26
|
15 - 本研究では、CbC を用いた Gears OS の実装を示す。
|
|
16
|
16
|
|
19
|
17 <!--
|
|
16
|
18 # OS の拡張性と信頼性の両立
|
|
|
19
|
|
21
|
20 - さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。
|
|
|
21 - 時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。
|
|
|
22 - その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。
|
|
|
23 - これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。
|
|
|
24 - 検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。
|
|
|
25 - このため信頼性と拡張性を両立させることが重要である。
|
|
17
|
26 -->
|
|
19
|
27 <!--
|
|
|
28 # 目次？
|
|
|
29 -->
|
|
21
|
30
|
|
27
|
31 # メタ計算
|
|
17
|
32 - プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。
|
|
|
33 - メタ計算はノーマルレベルの計算から切り離して記述したい。
|
|
16
|
34 - そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。
|
|
|
35 - そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
|
|
17
|
36
|
|
16
|
37 # Continuation based C (CbC)
|
|
|
38 - Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。
|
|
20
|
39 - Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する。
|
|
19
|
40 - この goto 文による遷移を軽量継続と呼ぶ。
|
|
20
|
41 - CbC は軽量継続を持ち、C と互換性のある言語である。
|
|
17
|
42
|
|
|
43 # CbC のコード例
|
|
19
|
44 - CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
|
|
16
|
45 - Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
|
|
|
46 - goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する。
|
|
|
47 - この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
|
|
|
48 ```Code_Gear
|
|
26
|
49 __code cg0(int a, int b){
|
|
|
50 goto cg1(a+b);
|
|
16
|
51 }
|
|
|
52
|
|
26
|
53 __code cg1(int c){
|
|
|
54 goto cg2(c);
|
|
16
|
55 }
|
|
|
56 ```
|
|
20
|
57
|
|
16
|
58 # Gears OS
|
|
20
|
59 - Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。
|
|
16
|
60 - 並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
|
|
20
|
61 - Input/Output Data Gear の依存関係が解決された Code Gear を並列実行する。
|
|
|
62
|
|
27
|
63 <div style="text-align: center;">
|
|
|
64 <img src="./fig/normal.pdf" alt="MetaGear" width="600">
|
|
|
65 </div>
|
|
|
66
|
|
20
|
67 # Data Gear
|
|
|
68 - Data Gear は データの単位であり、int や文字列などの Primitive Type を持っている。
|
|
|
69 - Code Gear は任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
|
|
27
|
70 - Code Gear は接続された Data Gear 以外には参照を行わない。
|
|
20
|
71
|
|
|
72 # Gears でのメタ計算
|
|
21
|
73 - Gears OS ではメタ計算を Meta Code Gear、Meta Data Gear で表現する。
|
|
|
74 - Meta Code Gear はノーマルレベルの Code Gear の直後に遷移され、メタ計算を実行する。
|
|
|
75 - Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。
|
|
20
|
76
|
|
21
|
77 <div style="text-align: center;">
|
|
27
|
78 <img src="./fig/meta.pdf" alt="MetaGear" width="600">
|
|
21
|
79 </div>
|
|
16
|
80
|
|
27
|
81 # Gears でのメタ計算
|
|
|
82
|
|
16
|
83 # Gears OS の構成
|
|
23
|
84 - Gears OS は以下の要素で構成される。
|
|
28
|
85 - Context
|
|
29
|
86 - 使用されるCode/Data Gear のリストを持っておりTaskでもある。
|
|
|
87 - TaskQueue
|
|
|
88 - Task のリストを扱う
|
|
|
89 - TaskManager
|
|
|
90 - Task の依存関係の解決、作成や停止を行います。
|
|
|
91 - Worker
|
|
|
92 - Task の実行を行う
|
|
23
|
93
|
|
|
94 # Gears OS の構成図
|
|
|
95
|
|
|
96 <div style="text-align: center;">
|
|
24
|
97 <img src="./fig/gears_structure.pdf" alt="gears_structure" width="900">
|
|
|
98 </div>
|
|
|
99
|
|
|
100 # Context
|
|
|
101 - Context とは使用される Code Gear と Data Gear を全て格納した Meta Data Gear である。
|
|
|
102 - Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。
|
|
|
103 <div style="text-align: center;">
|
|
|
104 <img src="./fig/Gearef.pdf" alt="gearef" width="900">
|
|
23
|
105 </div>
|
|
16
|
106
|
|
24
|
107 # context の定義
|
|
|
108
|
|
|
109 ```contexr
|
|
|
110 /* context define */
|
|
|
111 struct Context {
|
|
26
|
112 int codeNum; //実行可能な Code Gear の数
|
|
24
|
113 __code (**code) (struct Context*); //実行可能な code Gear のリスト
|
|
|
114 void* heapStart; //Data Gear の Allocate用のヒープ
|
|
|
115 void* heap;
|
|
|
116 long heapLimit;
|
|
|
117 int dataNum; //Data Gear の数
|
|
|
118 union Data **data; //Data Gear のリスト
|
|
|
119 };
|
|
|
120 ```
|
|
|
121
|
|
26
|
122 #Context
|
|
|
123 - Code/Data Gear の名前は enum で定義される。
|
|
|
124 - Code/Data Gear の名前とポインタの対応は enum を使って行われる。
|
|
|
125
|
|
|
126 ```code
|
|
|
127 enum Code {
|
|
|
128 C_cg1,
|
|
|
129 C_cg2,
|
|
|
130 };
|
|
|
131 ```
|
|
|
132
|
|
|
133 ```data
|
|
|
134 enum Data {
|
|
|
135 D_dg1,
|
|
|
136 D_dg2,
|
|
|
137 };
|
|
|
138 ```
|
|
27
|
139
|
|
|
140
|
|
21
|
141 <!--
|
|
16
|
142 # CbC による Gears OS 記述の問題点
|
|
|
143 - Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
|
|
|
144 - 本研究ではこれらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
|
|
|
145 - そのためのプロトタイプとして perl スクリプトを作成した。
|
|
21
|
146 -->
|
|
16
|
147
|
|
|
148 # Interface
|
|
23
|
149 - Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
|
|
|
150 - Interface は使用される Data Gear の定義と、それに対する Code Gear の集合である。
|
|
|
151 - Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。
|
|
|
152
|
|
27
|
153 # Interface のコード
|
|
23
|
154 ```interface
|
|
|
155 typedef struct Stack<Type, Impl>{
|
|
|
156 union Data* stack;
|
|
|
157 union Data* data;
|
|
|
158 union Data* data1;
|
|
|
159 __code whenEmpty(...);
|
|
|
160 __code clear(Impl* stack,__code next(...));
|
|
|
161 __code push(Impl* stack,Type* data, __code next(...));
|
|
|
162 __code pop(Impl* stack, __code next(Type* data, ...));
|
|
|
163 __code pop2(Impl* stack, __code next(Type* data, Type* data1, ...));
|
|
|
164 __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
|
|
|
165 __code get(Impl* stack, __code next(Type* data, ...));
|
|
|
166 __code get2(Impl* stack, __code next(Type* data, Type* data1, ...));
|
|
|
167 __code next(...);
|
|
|
168 } Stack;
|
|
|
169 ```
|
|
|
170
|
|
27
|
171 # Interface の実装例
|
|
16
|
172
|
|
|
173 ```impl
|
|
|
174 Stack* createSingleLinkedStack(struct Context* context) {
|
|
|
175 struct Stack* stack = new Stack();
|
|
|
176 struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
|
|
|
177 stack->stack = (union Data*)singleLinkedStack;
|
|
|
178 singleLinkedStack->top = NULL;
|
|
|
179 stack->push = C_pushSingleLinkedStack;
|
|
|
180 stack->pop = C_popSingleLinkedStack;
|
|
|
181 stack->pop2 = C_pop2SingleLinkedStack;
|
|
|
182 stack->get = C_getSingleLinkedStack;
|
|
|
183 stack->get2 = C_get2SingleLinkedStack;
|
|
|
184 stack->isEmpty = C_isEmptySingleLinkedStack;
|
|
|
185 stack->clear = C_clearSingleLinkedStack;
|
|
|
186 return stack;
|
|
|
187 }
|
|
30
|
188 ```
|
|
24
|
189
|
|
30
|
190 # Interface の実装例
|
|
|
191
|
|
|
192 ```impl
|
|
|
193 __code pushSingleLinkedStack(struct SingleLinkedStack* stack,
|
|
|
194 union Data* data, __code next(...)) {
|
|
24
|
195 Element* element = new Element();
|
|
|
196 element->next = stack->top;
|
|
|
197 element->data = data;
|
|
|
198 stack->top = element;
|
|
|
199 goto next(...);
|
|
|
200 }
|
|
|
201
|
|
16
|
202 ```
|
|
|
203 <!--
|
|
|
204
|
|
|
205 <div style="text-align: center;">
|
|
|
206 <img src="./images/multiComponent.pdf" alt="message" width="600">
|
|
|
207 </div>
|
|
|
208
|
|
|
209 -->
|
|
|
210
|
|
24
|
211 # stub Code Gear
|
|
16
|
212
|
|
|
213 - Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。
|
|
24
|
214 - しかし、Meta Data Gear である Context をノーマルレベルの Code Gear から直接アクセスするのはよろしくない。
|
|
16
|
215 - そこで Context から必要なデータを取り出して Code Gear に接続する、メタレベルの stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
|
|
|
216
|
|
30
|
217 # stub Code Gear の例
|
|
16
|
218 ```stub
|
|
30
|
219 __code clearSingleLinkedStack(struct Context *context,
|
|
|
220 struct SingleLinkedStack* stack,enum Code next) {
|
|
16
|
221 stack->top = NULL;
|
|
|
222 goto meta(context, next);
|
|
|
223 }
|
|
|
224
|
|
|
225 __code clearSingleLinkedStack_stub(struct Context* context) {
|
|
30
|
226 SingleLinkedStack* stack =
|
|
|
227 (SingleLinkedStack*)GearImpl(context, Stack, stack);
|
|
16
|
228 enum Code next = Gearef(context, Stack)->next;
|
|
|
229 goto clearSingleLinkedStack(context, stack, next);
|
|
|
230 }
|
|
|
231 ```
|
|
|
232
|
|
24
|
233 # Context、stub Code Gear の自動生成
|
|
|
234 - Gears OS ではノーマルレベルの計算の他に Context や stub などのメタ計算を記述する必要がある。
|
|
|
235 - 現在の CbC で Gears OS を記述すると、このメタ計算の記述も行わなくてはならず、これには多くの労力を要する。
|
|
|
236 - この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。
|
|
25
|
237 <div style="text-align: center;">
|
|
|
238 <img src="./fig/generate_context.pdf" alt="generate_context" width="900">
|
|
|
239 </div>
|
|
24
|
240
|
|
|
241
|
|
16
|
242 # stub Code Gear の生成
|
|
|
243 - stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
|
|
|
244 - stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
|
|
25
|
245 - generate_stub は指定された cbc ファイルの __code で記述された Code Gear を取得。
|
|
|
246 - Code Gear の引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
|
|
|
247 - cbc ファイルの Code Gear から、生成した stub Code Gear を加えたファイルを生成する。
|
|
16
|
248
|
|
30
|
249 # 生成された stub Code Gear
|
|
|
250
|
|
16
|
251 ```stub
|
|
30
|
252 __code clearSingleLinkedStack(struct Context *context,
|
|
|
253 struct SingleLinkedStack* stack,enum Code next) {
|
|
16
|
254 stack->top = NULL;
|
|
|
255 goto meta(context, next);
|
|
|
256 }
|
|
|
257
|
|
|
258 __code clearSingleLinkedStack_stub(struct Context* context) {
|
|
30
|
259 SingleLinkedStack* stack =
|
|
|
260 (SingleLinkedStack*)GearImpl(context, Stack, stack);
|
|
16
|
261 enum Code next = Gearef(context, Stack)->next;
|
|
|
262 goto clearSingleLinkedStack(context, stack, next);
|
|
|
263 }
|
|
|
264 ```
|
|
|
265
|
|
|
266 # Context の生成
|
|
|
267
|
|
25
|
268 - generate_context は context.h から Data Gear、generate_stub から生成されたファイルから Code Gear を取得し、以下を生成する。
|
|
26
|
269 - Code/Data Gear を enum で定義した enumCode.h、enumData.h
|
|
25
|
270 - 取得した Code/Data Gear から Context の生成を行う target-context
|
|
|
271 - Context を生成する際の Data Gear の Allocation を行う dataGearInit.c
|
|
16
|
272
|
|
25
|
273 <div style="text-align: center;">
|
|
30
|
274 <img src="./fig/generate_context3.pdf" alt="generate_context3" width="500">
|
|
25
|
275 </div>
|
|
16
|
276
|
|
|
277 # 今後の課題
|
|
|
278 - 本研究では interface の記述、CbC ファイルから Gears OS の記述に必要な Context と stub の生成を行う perl スクリプトの生成を行なった。
|
|
|
279 - これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
|
|
|
280 - 今後の課題は Code Gear からメタ計算を行う meta Code Gear を生成できるようにし、ユーザーがメタレベルの処理を意識せずにコードを記述できるようにする。
|
|
|
281 - また、今回 perl スクリプトによって Context や stub の生成を行なったが、LLVM/clang 上で実装しコンパイラで直接 CbC を実行できるようにすることを目的とする。
|
|
|
282
|
|
|
283
|
|
18
|
284 [](プロシン発表時間 セッション7 1/21 10:40 - 12:00)
|
