Mercurial > hg > Document > Growi

comparison user/menikon/thesis.md @ 0:e12992dca4a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
init from Growi
author anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Wed, 16 Dec 2020 14:05:01 +0900
parents
children b6c284fd5ae4
comparison
equal deleted inserted replaced
-1:000000000000 0:e12992dca4a0
1 # CbC による xv6 の FileSystem の書き換え
2 author: Takahiro Sakamoto, Shinji Kono
3
4 profile: 琉球大学工学部情報工学科並列信頼研
5
6 ## 研究目的
7 - OSに対し高い信頼性を実現させたい
8
9 - そのために当研究室ではContinuation based C (CbC)を用いたGearsOSを設計中である
10
11 - 前段階としてシンプルであるが基本的な機能を揃えたOSであるxv6をCbCで書き換える
12
13 - CbCは処理の基本単位をCodeGearとし、stackに値を積む事なくCodeGear間を遷移する
14
15 - CodeGear間は状態遷移であるためOS内部を明確化することができる
16
17 - 本研究ではOS内部の明確化を実現し信頼性を向上させるためにCbCを用いFileSystemを書き換える
18
19 ## 研究概要
20 -
21 ## Continuation based C
22 * Continuation based C (CbC) はこの Code Gear 処理の単位としてプログラミング言語として開発している。
23 * Code Gear は 関数呼び出し時の環境を使わずに次の Code Gear へと goto 文によって遷移する
24 * この goto 文による遷移を軽量継続と呼ぶ
25 * 継続を用いることによって状態遷移ベースでのプログラミングが可能である
26 * CbC は C と互換性のある言語なので、C の関数も呼び出すことができる
27 ## CbC のコード例
28 * CbC では Code Gear は \_\_code Code Gear 名 (引数) の形で記述される
29 * Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない
30 * goto の後に Code Gear 名と引数を並べて、次の Code Gear の遷移を記述する
31
32 ## CbC のコード例
33 * この goto の行き先を継続と呼び、このときの a+b が次の Code Gear への出力となる
34
35 ```
36 __code cg0(int a, int b){
37 goto cg1(a+b);
38 }
39
40 __code cg1(int c){
41 goto cg2(c);
42 }
43 ```
44 ## CbC の継続
45
46 ## Gears におけるメタ計算
47 * Gears OS ではメタ計算を Meta Code Gear、Meta Data Gear で表現する
48 * Meta Code Gear はノーマルレベルの Code Gear の直後に遷移され、メタ計算を実行する
49 * Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う
50
51 ## Meta Gear
52 * Gears OS では、Meta Code Gear は通常の Code Gear の直前、直後に挿入され、メタ計算を実行する
53 * 通常の計算からはメタ計算は見ることができない
54
55
56 ## Context
57 * Gears OS では Context と呼ばれる、使用されるすべての Code Gear、Data Gear を持つ Meta Data Gear を持っている
58 * Gears OS は必要な Code Gear、Data Gear を参照したい場合、この Context を通す必要がある
59 * Context は Meta Data Gear であるため、Meta Code Gear を介してアクセスする
60
61 ## Context
62 * Context は全ての Code Gear のリストを持っており、enum で番号とアドレスを対応付けている
63 ```
64 enum Code {
65 C_popSingleLinkedStack,
66 C_pushSingleLinkedStack,
67 C_stackTest3,
68 C_assert3,
69 ...
70 };
71 ```
72 ```
73 context->code[C_popSingleLinkedStack] = popSingleLinkedStack_stub;
74 context->code[C_pushSingleLinkedStack] = pushSingleLinkedStack_stub;
75 context->code[C_stackTest3] = stackTest3_stub;
76 context->code[C_assert3] = assert3_stub;
77 ```
78
79 ## Context
80 * Data Gear も Code Gear と同様に Context が全ての Data Gear のリストを持っている
81 * Data Gear のリストも enum で管理されている
82 * これは引数格納用の Data Gear の番号である
83 ```
84 enum DataType {
85 D_Code,
86 D_SingleLinkedStack,
87 D_Stack,
88 D_TaskManager,
89 D_Worker,
90 ...
91 };
92 ```
93
94 ## Interface
95 * Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される
96 * Interface は GearsOS でのモジュール化の仕組み
97 * Interface は使用される Data Gear の定義と、それに対する Code Gear の集合である
98 * Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる
99
100 ## Interface の定義
101 * Stack の Interface の例である
102 * typedef struct Interface 名で記述する
103 * Impl は実際に実装した際のデータ構造の型になる
104
105 ```
106 typedef struct Stack<Impl> {
107 union Data* stack;
108 union Data* data;
109 __code next(...);
110 __code whenEmpty(...);
111
112 __code clear(Impl* stack, __code next(...));
113 __code push(Impl* stack, union Data* data, __code next(...));
114 __code pop(Impl* stack, __code next(union Data* ...));
115 __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
116
117 }
118 ```
119 ## Interface の定義
120 * Data Gear は 操作する Data Gear と
121 操作に必要な全ての Data Gear Gear が記述されている
122 * \_\_code で記述されているものが操作の Code Gear である
123
124 ```
125 typedef struct Stack<Impl> {
126 union Data* stack;
127 union Data* data;
128 __code next(...);
129 __code whenEmpty(...);
130
131 __code clear(Impl* stack, __code next(...));
132 __code push(Impl* stack, union Data* data, __code next(...));
133 __code pop(Impl* stack, __code next(union Data* ...));
134 __code isEmpty(Impl* stack, __code next(...), __code whenEmpty(...));
135
136 }
137 ```
138 ## Interface の実装の記述
139 * ソースコードは Interface の実装の初期化のコードである
140 * 操作の Code Gear には実装した Code Gear の番号が代入されるが、ここを入れ替えることで、複数の実装を持つことができる
141 ```
142 Stack* createSingleLinkedStack(struct Context* context) {
143 struct Stack* stack = new Stack();
144 struct SingleLinkedStack* singleLinkedStack = new SingleLinkedStack();
145 stack->stack = (union Data*)singleLinkedStack;
146 singleLinkedStack->top = NULL;
147 stack->push = C_pushSingleLinkedStack;
148 stack->pop = C_popSingleLinkedStack;
149 stack->isEmpty = C_isEmptySingleLinkedStack;
150 stack->clear = C_clearSingleLinkedStack;
151 return stack;
152 }
153 ```
154 ## xv6 の書き換えの方針
155 * xv6 を CbC で書き換え、Gears OS の機能と置き換えることで Gears OS に OS の基本構造を持たせたい
156 * このためには xv6 をモジュール化することで、xv6 の機能を明らかにする必要がある
157 * xv6 の Interface を定義し、Gears OS の機能をこれに合わせることによって実現したい
158
159 ## CbC による FileSystem の書き換え
160
161 ## まとめと今後の方針