Mercurial > hg > Papers > 2018 > mitsuki-sigos

comparison Slide/prosym.md @ 16:b802c7ffb249

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add Slide
author mir3636
date Wed, 17 Jan 2018 13:26:35 +0900
parents
children 016ee461da2a
comparison
equal deleted inserted replaced
15:4c7666f60b9b 16:b802c7ffb249
1 title: Code Gear と Data Gear を持つ Gears OS の設計
2 author: Mitsuki Miyagi, Shinji Kono
3 profile: 琉球大学
4 lang: Japanese
5 code-engine: coderay
6
7 <!--
8 # 研究目的
9
10 現代の OS では拡張性と信頼性を両立させることが要求されている。
11 <!--信頼性 信頼性を保証するには従来のテストとデバッグでは不十分-->
12 <!--信頼性を保証するには証明とモデル検査を用いる方法がある-->
13
14 信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
15 Gears OS は Continuation based C ^\(CbC)によってアプリケーションと OS そのものを記述する。
16
17 CbCはノーマルレベルではメタ構造を直接見ることはなく、継続を用いた関数型プログラミングに見える。
18 メタレベルから見た Data Gear をノーマルレベルの Code Gear に接続するには stub という Meta Code Gear を用いる。
19 stub と Meta はユーザーレベル Code Gear / Data Gear からスクリプトにより作成される。
20
21 ノーマルレベルからメタレベルを含んだコードへの変換に必要な情報はプログラムを構成する Code Gear と Data Gear の集まりから得る。
22 この集まりを Interface として定義している。
23 本研究では、Interfaceを用いたプログラミングと、メタ計算の実例を示す。
24 -->
25
26 # OS の拡張性と信頼性の両立
27
28 さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。
29 時代とともに進歩するハードウェア、サービスに対応して OS 自体が拡張される必要がある。
30 その信頼性を保証するには、従来の テストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。
31 これに対処するため には、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。
32 検証は一度ですむものではなく、アプリケーションやサービス、デバイスが新しくなることに検証をやり直す必要がある。
33 このため信頼性と拡張性を両立させることが重要である。
34 <!--プログラムからデータを分離して扱うデータベースには、
35 プログラム中のデータ構造とRDBの表構造のずれにより、<u>インピーダンスミスマッチ</u>という問題がある。
36
37 データベースのレコードをプログラム中のオブジェクトとして使える<u>OR Mapper</u>や、
38 データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
39
40 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。-->
41
42 # メタ計算の重要性
43 - プログラムを記述する際、ノーマルな処理の他に、メモリ管理やスレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。これらの計算をメタ計算と呼ぶ。
44 - メタ計算はノーマルな計算から切り離して記述したい。
45 - そのためには処理を細かく分割する必要があるが、関数やクラスなどの単位は容易に分割できない。
46 - そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
47 # Continuation based C (CbC)
48 - Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。
49 - CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
50 - Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
51 - goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する。
52 - この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる。
53 ```Code_Gear
54 __code cs0(int a, int b){
55 goto cs1(a+b);
56 }
57
58 __code cs1(int c){
59 goto cs2(c);
60 }
61 ```
62 # Gears OS
63 - Gears OS は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
64 - 並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
65 - またGears OS ではメタ計算を Meta Code Gear、Meta Data Gear で表現する。
66 - Meta Code Gear はノーマルの Code Gear の直後に遷移され、メタ計算を実行する。
67 - Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。
68
69 # Gears OS の構成
70
71 # CbC による Gears OS 記述の問題点
72 - Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
73 - 本研究ではこれらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
74 - そのためのプロトタイプとして perl スクリプトを作成した。
75
76 # Context
77 - Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
78 - Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。
79
80 <img src="./fig/context.svg" alt="message" width="550" >
81
82 # Interface
83 - interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。
84 - create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
85
86 ```impl
87 Stack* createSingleLinkedStack(struct Context* context) {
88 struct Stack* stack = new Stack();
89 struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
90 stack->stack = (union Data*)singleLinkedStack;
91 singleLinkedStack->top = NULL;
92 stack->push = C_pushSingleLinkedStack;
93 stack->pop = C_popSingleLinkedStack;
94 stack->pop2 = C_pop2SingleLinkedStack;
95 stack->get = C_getSingleLinkedStack;
96 stack->get2 = C_get2SingleLinkedStack;
97 stack->isEmpty = C_isEmptySingleLinkedStack;
98 stack->clear = C_clearSingleLinkedStack;
99 return stack;
100 }
101 ```
102 <!--
103
104 <div style="text-align: center;">
105 　<img src="./images/multiComponent.pdf" alt="message" width="600">
106 </div>
107
108 -->
109
110 # Context、stub Code Gear の自動生成
111 - Gears OS ではノーマルレベルの計算の他に Context や stub などのメタ計算を記述する必要がある。
112 - 現在の CbC で Gears OS を記述すると、このメタ計算の記述も行わなくてはならず、これには多くの労力を要する。
113 - この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。
114
115 # Meta の生成
116
117 - Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。
118 - しかし、メタであるContext をノーマルレベルの Code Gear から直接アクセスするのはよろしくない。
119 - そこで Context から必要なデータを取り出して Code Gear に接続する、メタレベルの stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
120
121 ```stub
122 __code clearSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,enum Code next) {
123 stack->top = NULL;
124 goto meta(context, next);
125 }
126
127 __code clearSingleLinkedStack_stub(struct Context* context) {
128 SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack);
129 enum Code next = Gearef(context, Stack)->next;
130 goto clearSingleLinkedStack(context, stack, next);
131 }
132 ```
133
134 # stub Code Gear の生成
135 - stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
136 - stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
137 - generate_stub は指定された cbc ファイルの __code型である Code Gear を取得。
138 - 引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
139 - cbc ファイルのから、生成した stub Code Gear を加えて、c ファイルを生成する。
140
141 ```stub
142 __code clearSingleLinkedStack(struct Context *context,struct SingleLinkedStack* stack,enum Code next) {
143 stack->top = NULL;
144 goto meta(context, next);
145 }
146
147 __code clearSingleLinkedStack_stub(struct Context* context) {
148 SingleLinkedStack* stack = (SingleLinkedStack*)GearImpl(context, Stack, stack);
149 enum Code next = Gearef(context, Stack)->next;
150 goto clearSingleLinkedStack(context, stack, next);
151 }
152 ```
153
154 # Context の生成
155
156 - Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
157 - generate_context は context.h から Data Gear、c ファイルから Code Gear を取得。
158 - 取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
159 - Code/Data Gear の名前とポインタの対応は この enum と関数ポインタによって表現される。
160 - generate_context は取得した Code/Data Gear から Context の生成を行うコードを生成する。
161 - Context には Allocation で生成した Data Gear へのポインタも格納されているが、Data Gear の Allocation を行うコードは dataGearInit.c に生成される。
162 - これらを自動生成することで Gears OS の記述量を約半分にすることができます。
163 <img src="./fig/generate_context.svg" alt="message" width="800" >
164
165 # 比較
166
167 # 今後の課題
168 - 本研究では interface の記述、CbC ファイルから Gears OS の記述に必要な Context と stub の生成を行う perl スクリプトの生成を行なった。
169 - これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
170 - 今後の課題は Code Gear からメタ計算を行う meta Code Gear を生成できるようにし、ユーザーがメタレベルの処理を意識せずにコードを記述できるようにする。
171 - また、今回 perl スクリプトによって Context や stub の生成を行なったが、LLVM/clang 上で実装しコンパイラで直接 CbC を実行できるようにすることを目的とする。
172
173
174 <!--
175 # ChildrenとAttribute
176
177 # Eitherクラス
178
179 # Jungleのサンプルコード
180 # Jungleの木の編集
181
182 # NodePath
183
184 # ノードの追加
185
186 # 移動、ルートノードの追加、コミット
187
188 # Jungleのサンプルコード
189
190 # 検索APIの実装
191
192 # 関数findを用いた検索APIのサンプルコード
193
194 # JungleでのIndexの実装
195
196 # Indexの実装
197
198 # Indexの実装
199
200 # HTML Rendering Engine
201
202 # 構造
203 # ContentTree
204 # Nodeが持つAttribute
205 # LayoutTree
206 # LayoutTreeの主な要素
207 # useにおけるタグ対応表
208 # multiComponent
209 # 設計
210 # コードとギャップのある格納
211
212 # コードとギャップのない格納
213
214 # 性能評価
215
216 # まとめ
217 -->
218 [](プロシン発表時間 セッション4 1/7 8:50 - 10:10)