Mercurial > hg > Papers > 2017 > mitsuki-sigos

comparison paper/sigos.tex @ 8:e04e25ad2f3c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update
author mir3636
date Fri, 21 Apr 2017 21:23:36 +0900
parents 0f3881e77256
children 9df52fe5b3d7
comparison
equal deleted inserted replaced
7:0f3881e77256 8:e04e25ad2f3c
96 % 信頼性の高いOS 96 % 信頼性の高いOS
97 % これをアセンブラにしていろいろなアプリケーションを作る 97 % これをアセンブラにしていろいろなアプリケーションを作る
98 % きょだいなCDGの上で動かすと既存のアプリケーションを動かすことができる 98 % きょだいなCDGの上で動かすと既存のアプリケーションを動かすことができる
99 99
100 \section{メタ計算の重要性} 100 \section{メタ計算の重要性}
101 % 今ま
101 102
102 プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理、スレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。 103 プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理、スレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。
103 これらの計算をメタ計算と呼ぶ。 104 これらの計算をメタ計算と呼ぶ。
104 105
106 従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。
107 実行時にメタ計算の変更を行う場合には、OS 内部のパラメータの変更を使用し、
108 実行されるユーザープログラム自体への変更は限定的である。
109 しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で
110 実際のシステムコール単位では不十分である。
111 例えば、モデル検査ではアセンブラあるいはバイトコード、インタプリタレベルでのメタ計算が必要になる。
112 しかし、バイトコードレベルでは粒度が細かすぎて扱いが困難になっている。
113 具体的にはメタ計算の実行時間が大きくなってしまう。
114
105 メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。 115 メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
106
107 そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。 116 そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
117 これによりシステムコードよりも細かくバイトコードよりも大きなメタ計算の単位を提供できる。
108 118
109 Code Gear は処理の単位である。 119 Code Gear は処理の単位である。
110 関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。 120 関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。
111 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。 121 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。
112 122
113 Continuation based C (CbC)\cite{cbc} はこの Code Gear 単位を用いたプログラミング言語として開発している。 123 Continuation based C (CbC)\cite{cbc} はこの Code Gear 単位を用いたプログラミング言語として開発している。
114 124
115 CbCは軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。 125 CbCは軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。
116 126
117 また、当研究室で開発している Gears OS\cite{gears} は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。 127 また、当研究室で開発している Gears OS\cite{gears} は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
118 128 CbC での記述はメタ計算を含まないノーマルレベルでの記述と、 Code Gear、Data Gear の記述を含むメタレベルの記述の2種類がある。
119 本研究では CbC を用いての Gears OS の実装と Gears OS におけるメタ計算の自動生成を行なう。 129 メタレベルでもさらに、メタ計算を用いることが可能になっている。
130 この2つのレベルはプログラミング言語レベルでの変換として実現される。
131 CbC は LLVM 上で実装されており、メタレベルでの変換系は本論文では、Perl による変換スクリプトにより実装されている。
132
133 Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
134 Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
135 Interface は複数の実装を持つことができ、Meta Data Gear によって定義される。
136 Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。
137
138 従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call する。
139 Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、
140 操作に対応する Code Gear に goto する。
141 Context とは使用される Code Gear と Data Gear を全て格納している Meta Data Gear である。
142 これは従来のスレッド構造体に対応する。
143 つまり Gears OS では従来はコンパイラが定義する ABI(Aplication Binary Interface)
144 を Meta Data Gear として CbC で表現し、メタ計算として操作することができる。
145
146 ノーマルレベルでは Context を直接見ることはできず、引数は Code Gear の引数を明示する必要がある。
147 この時に呼び出し側の引数を不定長引数として追加する構文を CbC に追加した。
148 これにより Interface 間の呼び出しを簡潔に記述することが出来るようになった。
149 メタレベルでは Code Gear の引数は単一または複数の Data Gear として見ることができる。
150 これは Context を直接操作することができることを意味する。
151 この部分はノーマルレベルの Code Gear を呼び出す stub として生成される。
152 ノーマルレベルでの goto 文はメタ計算への goto で置き換えられる。
153 Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。
154
155 メタ計算の例としては並列処理があり、Context を切り替えることによって複数のスレッドを実現している。
156 Context を複数の CPU に割り当てることにより並列実行を可能にしている。
157
158
159 本研究では CbC を用いての Gears OS の実装と Gears OS におけるメタ計算(Context と stub)の自動生成の実装について述べる。
120 160
121 \section{Continuation based C (CbC)} 161 \section{Continuation based C (CbC)}
122 CbC は Code Gear という処理の単位を用いて記述するプログラミング言語である。 162 CbC は Code Gear という処理の単位を用いて記述するプログラミング言語である。
123 Code Gear は CbC における最も基本的な処理単位である。 163 Code Gear は CbC における最も基本的な処理単位である。
124 Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。 164 Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。
178 \end{center} 218 \end{center}
179 \caption{Gears OS の構成図} 219 \caption{Gears OS の構成図}
180 \label{fig:gearsos} 220 \label{fig:gearsos}
181 \end{figure} 221 \end{figure}
182 222
183 Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。 223 Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear を持つ。
184 Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。 224 Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。
225
226 \lstinputlisting[label=context, caption=context]{./src/context1.c}
227
228 Data Gear は union と struct によって表現される。
229 Context には Data Gear の Data Type の情報が格納されている。
230 この情報から確保する Data Gear のサイズなどを決定する。
185 231
186 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。 232 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
187 Context は Task でもあり、TaskManager によって Context が生成され Task Queue へ挿入する。 233 Context は Task でもあり、TaskManager によって Context が生成され Task Queue へ挿入する。
188 Gears OS における Task Queue は Synchronized Queue で実現される。 234 Gears OS における Task Queue は Synchronized Queue で実現される。
189 Worker は TaskQueue から Task である Context を取得し、 Input/Output Data Gear の依存関係が解決されたものから並列実行される。 235 Worker は TaskQueue から Task である Context を取得し、 Input/Output Data Gear の依存関係が解決されたものから並列実行される。
190 236
191 237
192 238
193 \section{cbc のコードの例} 239 \section{CbC のコードの例}
194 240
195 リスト\ref{excbc}は CbC で記述された stack のコードの一部である。 241 リスト\ref{excbc}は CbC で記述された stack のコードの一部である。
196 Code Gear は \_\_code Code Gear で始まり、次の Code Gear へ goto で遷移する。 242 Code Gear は \_\_code Code Gear で始まり、次の Code Gear へ goto で遷移する。
197 243
198 %,,,の説明 244 %,,,の説明
225 271
226 272
227 273
228 274
229 interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。 275 interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
276 呼び出される Code Gear の引数となる Data Gear はここで全て定義される。
277
278
279
230 Code Gear、Data Gear に参照するために Context を通す必要があるが、 280 Code Gear、Data Gear に参照するために Context を通す必要があるが、
231 interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。 281 interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。
232 %create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。 282 %create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
233 %return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。 283 %return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。
234 284
268 318
269 stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。 319 stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。
270 generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。 320 generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
271 また、この時既に stub Code Gear が記述されている Code Gear は無視される。 321 また、この時既に stub Code Gear が記述されている Code Gear は無視される。
272 322
273 cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(\ref{stack_c}) 323 cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(Code\ref{stack_c})
274 324
275 \lstinputlisting[label=stack_cbc, caption=exampleCG]{./src/ex_cbc} 325 \lstinputlisting[label=stack_cbc, caption=exampleCG]{./src/ex_cbc}
276 \lstinputlisting[label=stack_c, caption=stub]{./src/ex_stub} 326 \lstinputlisting[label=stack_c, caption=stub]{./src/ex_stub}
277 327
278 \section{Context の生成} 328 \section{Context の生成}
279 Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。 329 Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
280 Data Gear を取得するために generate context は context の定義 (リスト\ref{context}) を読み宣言されている Data Gear を取得する。 330 Data Gear を取得するために generate context は context の定義 (Code\ref{context}) を読み宣言されている Data Gear を取得する。
281
282 \lstinputlisting[label=context, caption=context]{./src/context1.c}
283 331
284 Code Gear の取得は指定された generate\_stub で生成されたコードから \_\_code 型を見て行う。 332 Code Gear の取得は指定された generate\_stub で生成されたコードから \_\_code 型を見て行う。
285 取得した Code Gear、Data Gear の enum の定義は enumCode.h、enumData.h に生成される。 333 取得した Code Gear、Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
286 334
287 Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。 335 Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。
288 また、generate context は取得した Code/Data Gear から Context の生成を行うコード (リスト\ref{init_context}) も生成する。 336 また、generate context は取得した Code/Data Gear から Context の生成を行うコード (Code\ref{init_context}) も生成する。
289 337
290 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。 338 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
291 Code Gear は Context を通して Data Gear へアクセスする。 339 Code Gear は Context を通して Data Gear へアクセスする。
292 Data Gear の Allocation を行うコードは dataGearInit.cに生成される。 340 Data Gear の Allocation を行うコードは dataGearInit.cに生成される。
293 341