0
|
1 % withpage: ページ番号をつける (著者確認用)
|
|
2 % english: 英語原稿用フォーマット
|
|
3 \documentclass{ipsjprosym}
|
|
4 %\documentclass[withpage,english]{ipsjprosym}
|
2
|
5 \usepackage{listings}
|
0
|
6 \usepackage[dvipdfmx]{graphicx}
|
|
7 \usepackage{latexsym}
|
|
8 \usepackage{comment}
|
|
9 \lstset{
|
|
10 language=C,
|
|
11 tabsize=2,
|
|
12 frame=single,
|
|
13 basicstyle={\ttfamily\footnotesize},%
|
|
14 identifierstyle={\footnotesize},%
|
|
15 commentstyle={\footnotesize\itshape},%
|
|
16 keywordstyle={\footnotesize\bfseries},%
|
|
17 ndkeywordstyle={\footnotesize},%
|
|
18 stringstyle={\footnotesize\ttfamily},
|
|
19 breaklines=true,
|
|
20 captionpos=b,
|
|
21 columns=[l]{fullflexible},%
|
|
22 xrightmargin=0zw,%
|
|
23 xleftmargin=1zw,%
|
|
24 aboveskip=1zw,
|
|
25 numberstyle={\scriptsize},%
|
|
26 stepnumber=1,
|
|
27 numbersep=0.5zw,%
|
|
28 lineskip=-0.5ex,
|
|
29 }
|
|
30 \renewcommand{\lstlistingname}{Code}
|
5
|
31 \usepackage{caption}
|
|
32 \captionsetup[lstlisting]{font={small,tt}}
|
0
|
33
|
|
34 \begin{document}
|
|
35
|
|
36 % Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
37 \title{Code Gear と Data Gear を持つ\\Gears OS の設計}
|
|
38
|
|
39 \affiliate{IPSJ}{情報処理学会}
|
|
40
|
|
41 \author{宮城 光希}{Mitsuki MIYAGI}{}[mir3636@cr.ie.u-ryukyu.ac.jp]
|
|
42 \author{河野 真治}{Shinji KONO}{IPSJ}[kono@ie.u-ryukyu.ac.jp]
|
|
43
|
|
44 % はじめに
|
|
45 \begin{abstract}
|
|
46 現代の OS では拡張性と信頼性を両立させることが要求されている。
|
|
47 信頼性をノーマルレベルの計算に対して保証し、拡張性をメタレベルの計算で実現することを目標に Gears OS を設計中である。
|
|
48 Gears OS は Continuation based C(CbC) によってアプリケーションと OS そのものを記述する。
|
|
49 OS の下ではプログラムの記述は通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等の記述しなければならない処理が存在する。
|
|
50 これらの計算をメタ計算と呼ぶ。
|
|
51 メタ計算を通常の計算から切り離して記述するために、Code Gear、Data Gear という単位を提案している。
|
|
52 CbC はこの Code Gear と Data Gear の単位でプログラムを記述する。
|
|
53 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在する。
|
|
54 Code Gear 間の接続は次の Code Gear の番号と thread structure に相当する Context によって行われる。
|
|
55 ユーザーレベルではメタ構造を直接見ることはなく、継続を用いた関数型プログラミングに見える。
|
|
56 メタレベルから見た Data Gear をユーザーレベルの Code Gear に接続するには stub という Meta Code Gear を用いる。
|
|
57 stub と Meta はユーザーレベル Code Gear と Data Gear からスクリプトにより作成される。
|
|
58 変換に必要な情報はプログラムを構成する Code Gear と Data Gear の集まりから得る。
|
|
59 この集まりを Interface として定義している。
|
|
60 本論文では、Interfaceを用いたプログラミングと、メタ計算の実例を示す。
|
|
61 \end{abstract}
|
|
62
|
|
63 \begin{jkeyword}
|
5
|
64 OS, プログラミング言語, コンパイラ, CbC, Gears OS
|
0
|
65 \end{jkeyword}
|
|
66
|
|
67 \maketitle
|
|
68
|
|
69 % Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
70 \section{メタ計算の重要性}
|
|
71 プログラムを記述する際、ノーマルレベルの処理の他に、メモリ管理、スレッド管理、CPU や GPU の資源管理等、記述しなければならない処理が存在する。
|
|
72 これらの計算をメタ計算と呼ぶ。
|
|
73
|
|
74 従来の OS では、メタ計算はシステムコールやライブラリーコールの単位で行われる。
|
|
75 実行時にメタ計算の変更を行う場合には、OS 内部のパラメータの変更を使用し、
|
|
76 実行されるユーザープログラム自体への変更は限定的である。
|
|
77 しかし、メタ計算は性能測定あるいはプログラム検証、さらに並列分散計算のチューニングなど細かい処理が必要で
|
|
78 実際のシステムコール単位では不十分である。
|
|
79 例えば、モデル検査ではアセンブラあるいはバイトコード、インタプリタレベルでのメタ計算が必要になる。
|
|
80 しかし、バイトコードレベルでは粒度が細かすぎて扱いが困難になっている。
|
|
81 具体的にはメタ計算の実行時間が大きくなってしまう。
|
|
82
|
|
83 メタ計算を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
|
|
84 そこで当研究室ではメタ計算を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
|
|
85 これによりシステムコードよりも細かくバイトコードよりも大きなメタ計算の単位を提供できる。
|
|
86
|
|
87 Code Gear は処理の単位である。
|
|
88 関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。
|
|
89 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いてメタ計算を実現する。
|
|
90
|
|
91 Continuation based C (CbC)\cite{cbc} はこの Code Gear 単位を用いたプログラミング言語として開発している。
|
|
92
|
|
93 CbCは軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。
|
|
94
|
|
95 また、当研究室で開発している Gears OS\cite{gears} は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
|
|
96 CbC での記述はメタ計算を含まないノーマルレベルでの記述と、 Code Gear、Data Gear の記述を含むメタレベルの記述の2種類がある。
|
|
97 メタレベルでもさらに、メタ計算を用いることが可能になっている。
|
|
98 この2つのレベルはプログラミング言語レベルでの変換として実現される。
|
|
99 CbC は LLVM\cite{llvm} 上で実装されており、メタレベルでの変換系は本論文では、Perl による変換スクリプトにより実装されている。
|
|
100
|
|
101 Code Gear と Data Gear は Interface と呼ばれるまとまりとして記述される。
|
|
102 Interface は使用される Data Gear の定義と、それに対する操作を行う Code Gear の集合である。
|
|
103 Interface は複数の実装を持つことができ、Meta Data Gear によって定義される。
|
|
104 Interface の操作に対応する Code Gear の引数は Interface に定義されている Data Gear を通して行われる。
|
|
105
|
|
106 従来の関数呼び出しでは引数をスタック上に構成し、関数の実装アドレスを Call する。
|
|
107 Gears OS では引数は Context 上に用意された Interface の Data Gear に格納され、
|
|
108 操作に対応する Code Gear に goto する。
|
|
109 Context とは使用される Code Gear と Data Gear を全て格納している Meta Data Gear である。
|
|
110 これは従来のスレッド構造体に対応する。
|
|
111 つまり Gears OS では従来はコンパイラが定義する ABI(Application Binary Interface)
|
|
112 を Meta Data Gear として CbC で表現し、メタ計算として操作することができる。
|
|
113
|
|
114 ノーマルレベルでは Context を直接見ることはできず、引数は Code Gear の引数を明示する必要がある。
|
|
115 この時に呼び出し側の引数を不定長引数として追加する構文を CbC に追加した。
|
|
116 これにより Interface 間の呼び出しを簡潔に記述することが出来るようになった。
|
|
117 メタレベルでは Code Gear の引数は単一または複数の Data Gear として見ることができる。
|
|
118 これは Context を直接操作することができることを意味する。
|
|
119 この部分はノーマルレベルの Code Gear を呼び出す stub として生成される。
|
|
120 ノーマルレベルでの goto 文はメタ計算への goto で置き換えられる。
|
|
121 Gears OS でのメタ計算は stub と goto のメタ計算の2箇所で実現される。
|
|
122
|
|
123 メタ計算の例としては並列処理があり、Context を切り替えることによって複数のスレッドを実現している。
|
|
124 Context を複数の CPU に割り当てることにより並列実行を可能にしている。
|
|
125
|
|
126
|
|
127 本研究では CbC を用いての Gears OS の実装と Gears OS におけるメタ計算(Context と stub)の自動生成の実装について述べる。
|
|
128
|
|
129 \section{Continuation based C (CbC)}
|
|
130 CbC は Code Gear という処理の単位を用いて記述するプログラミング言語である。
|
|
131 Code Gear は CbC における最も基本的な処理単位である。
|
|
132 Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。
|
|
133 CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
|
|
134 ただし、これは \_\_code 型の戻り値を返すという意味ではなく、Code Gear であることを示すフラグである。
|
|
135 Code Gear は戻り値を持たないので、Cの関数とは異なり return 文は存在しない。
|
|
136
|
|
137 Code Gear から次の Code Gear への遷移は goto による継続で処理を行い、次の Code Gear へ引数として入出力を与える。
|
|
138 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。
|
|
139
|
|
140 \begin{figure}[ht]
|
|
141 \begin{center}
|
|
142 \includegraphics[width=70mm]{./pic/codesegment.pdf}
|
|
143 \end{center}
|
|
144 \caption{goto による Code Gear 間の継続}
|
|
145 \label{fig:cs}
|
|
146 \end{figure}
|
|
147
|
|
148 CbC の goto による継続は Scheme の継続と異なり呼び出し元の環境がないので、この継続は単なる行き先である。
|
|
149 したがってこれを軽量継続と呼ぶ。
|
|
150 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。
|
|
151
|
|
152 \section{Gears OS}
|
|
153 Gears OS は Code Gear とデータの単位である Data Gear を用いて開発されており、CbC で記述されている。
|
|
154 Gears OS では、並列実行するための Task を、実行する Code Gear と、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
|
|
155 Gears OS は Input/Output Data Gear の依存関係が解決された CodeGear を並列実行する。
|
|
156 Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
|
|
157 Code Gear は任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
|
|
158 また、接続された Data Gear 以外には参照を行わない。
|
|
159 処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることができる。
|
|
160
|
|
161 Gears OS では メタ計算 を Meta Code Gear、Meta Data Gear で表現する。
|
|
162 Meta Code Gear は通常の Code Gear の直後に遷移され、メタ計算を実行する。
|
|
163 Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。
|
|
164
|
|
165 CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。
|
|
166
|
|
167 \section{Gears OS の構成}
|
|
168 Gears OS は以下の要素で構成される。
|
|
169
|
|
170 \begin{itemize}
|
|
171 \item Context
|
|
172 \item TaskQueue
|
|
173 \item TaskManager
|
|
174 \item Worker
|
|
175 \end{itemize}
|
|
176
|
|
177 図\ref{fig:gearsos} に Gears OS の構成図を示す。
|
|
178
|
|
179 \begin{figure}[ht]
|
|
180 \begin{center}
|
|
181 \includegraphics[width=70mm]{./pic/gears_structure}
|
|
182 \end{center}
|
|
183 \caption{Gears OS の構成図}
|
|
184 \label{fig:gearsos}
|
|
185 \end{figure}
|
|
186
|
|
187 Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear を持つ。
|
|
188 Gears OS は必要な Code Gear、Data Gear に参照したい場合、この Context を通す必要がある。
|
3
|
189 Code\ref{context} は Context の定義で Code\ref{initcontext} は Context の生成である。
|
0
|
190
|
5
|
191 \lstinputlisting[caption=Context, label=context]{./src/context1.c}
|
3
|
192 \lstinputlisting[label=initcontext, caption=initContext]{./src/initcontext.c}
|
0
|
193
|
|
194 Data Gear は union と struct によって表現される。
|
|
195 Context には Data Gear の Data Type の情報が格納されている。
|
|
196 この情報から確保する Data Gear のサイズなどを決定する。
|
2
|
197 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
|
0
|
198
|
|
199 Context は Task でもあり、TaskManager によって Context が生成され Task Queue へ挿入する。
|
|
200 Gears OS における Task Queue は Synchronized Queue で実現される。
|
|
201 Worker は TaskQueue から Task である Context を取得し、 Input/Output Data Gear の依存関係が解決されたものから並列実行される。
|
|
202
|
|
203 \section{CbC のコードの例}
|
|
204
|
|
205 Code\ref{excbc}は CbC で記述された stack のコードの一部である。
|
2
|
206 Code Gear は \_\_code Code Gear の記述から始まり、次の Code Gear へ goto で遷移する。
|
0
|
207
|
2
|
208 %...の説明
|
0
|
209 %codegearの説明もっとする?
|
|
210
|
5
|
211 \lstinputlisting[label=excbc, caption=CbC で記述された stack のコード]{./src/ex_stack.cbc}
|
0
|
212
|
5
|
213 \section{CbC による Gears OS 記述の問題}
|
|
214 Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
|
|
215 これらのメタ計算を自動生成、interface、implement の機能を導入することにより、ユーザーレベルにおける CbC 可読性を上げ、
|
|
216 Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
|
|
217
|
|
218 \section{interface と implement}
|
0
|
219 interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
|
|
220 呼び出される Code Gear の引数となる Data Gear はここで全て定義される。
|
|
221
|
2
|
222 Code\ref{interface}は stack の interface である。
|
0
|
223 Code Gear、Data Gear に参照するために Context を通す必要があるが、
|
|
224 interface を記述することでデータ構造の api と Data Gear を結びつけることが出来、呼び出しが容易になった。
|
|
225
|
|
226 \lstinputlisting[label=interface, caption=Interface]{./src/Stack.cbc}
|
1
|
227
|
5
|
228 Code\ref{implement}は stack の implement の例である。
|
|
229 createImpl は関数呼び出しで呼び出され、interface と implement の初期化と Code Gear のポインタの設定を行う。
|
2
|
230 %return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。
|
1
|
231
|
5
|
232 \lstinputlisting[label=implement, caption=Implement]{./src/stackimpl.cbc}
|
0
|
233
|
|
234 \section{Gearef、GearImpl}
|
|
235
|
|
236 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
|
|
237 Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すため、Code\ref{gearef1} のようにコードが煩雑になってしまう。
|
|
238 そこで Code Gear がデータを参照するための Gearef というマクロを定義した。
|
|
239 Gearef に Context と型を渡すことでデータの参照が行える。
|
|
240 また interface の実装を参照する際も、ポインタでの記述が複雑になってしまうため 同様に GearImpl を定義した。
|
|
241 GearImpl は Context と interface 名、interface の変数名を指定して参照する。
|
|
242 Gearef と GearImpl を用いたコードが Code\ref{gearef2}である。
|
|
243
|
5
|
244 \lstinputlisting[label=gearef1, caption=定義前のコード]{./src/ex_code1}
|
|
245 \lstinputlisting[label=gearef2, caption=Gearef、GearImplを用いたコード]{./src/ex_code2}
|
0
|
246
|
|
247 \section{stub Code Gear}
|
|
248 Code Gear が必要とする Data Gear を取り出す際に Context を通す必要があるが、
|
|
249 Context を直接扱うのはセキュリティ上好ましくない。
|
|
250 そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
|
|
251 stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する間に挟まれる。
|
|
252
|
2
|
253 \section{CbC による Gears OS 記述の問題}
|
|
254
|
|
255 %メタの話
|
|
256
|
|
257 Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
|
|
258 これらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
|
|
259
|
0
|
260 \section{stub Code Gear の生成}
|
|
261 stub Code Gear は Code Gear 間の継続に挟まれる Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
|
|
262 Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
|
|
263 stub Code Gear を 自動生成する generate stub を Perl スクリプトで作成することによって Code Gear の記述量を約半分にすることができる。
|
|
264
|
|
265 stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。
|
|
266 generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
|
|
267 また、この時既に stub Code Gear が記述されている Code Gear は無視される。
|
|
268
|
|
269 cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(Code\ref{stack_c})
|
|
270
|
5
|
271 \lstinputlisting[label=stack_c, caption=stub Code Gear]{./src/ex_stub}
|
0
|
272
|
|
273 \section{Context の生成}
|
|
274 generate\_context は Context.h、Interface.cbc、generate\_stub で生成されたImpl.cbc を見て Context を生成する Perl スクリプトである。
|
|
275
|
|
276 \begin{figure}[ht]
|
|
277 \begin{center}
|
|
278 \includegraphics[width=70mm]{./pic/generate_context3.pdf}
|
|
279 \end{center}
|
|
280 \caption{generate\_context による Context の生成}
|
|
281 \label{fig:gc}
|
|
282 \end{figure}
|
|
283
|
|
284 Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
|
|
285
|
|
286 generate\_context は context の定義 (Code\ref{context}) を読み宣言されている Data Gear を取得する。
|
|
287 Code Gear の取得は指定された generate\_stub で生成されたコードから \_\_code 型を見て行う。
|
|
288 取得した Code Gear、Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
|
|
289
|
|
290 Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。
|
|
291 また、generate context は取得した Code/Data Gear から Context の生成を行うコード (Code\ref{init_context}) も生成する。
|
|
292
|
|
293 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
|
|
294 Code Gear は Context を通して Data Gear へアクセスする。
|
|
295 Data Gear の Allocation を行うコードは dataGearInit.cに生成される。
|
|
296
|
|
297 Data Gear は union Data とその中の struct によって表現される。
|
|
298 Context には Data Gear の Data Type の情報が格納されている。
|
|
299 この情報から確保される Data Gear のサイズなどを決定する。
|
|
300
|
5
|
301 \lstinputlisting[label=init_context, caption=生成されたinitContext]{./src/gencontext.c}
|
0
|
302
|
|
303 \section{今後の課題}
|
|
304 本研究では LLVM/Clang のデバッグ、interface の記述、CbC ファイルから Gears OS の記述に必要な Context と stub の生成を行う Perl スクリプトの生成を行なった。
|
|
305 これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
|
|
306
|
|
307 今後の課題は Code Gear からメタ計算を行う meta Code Gear を生成できるようにし、ユーザーがメタレベルの処理を意識せずにコードを記述できるようにする。
|
|
308 また、今回 Perl スクリプトによって Context や stub の生成を行なったが、LLVM/clang 上で実装しコンパイラで直接 CbC を実行できるようにすることを目的とする。
|
|
309
|
|
310 % BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
311 \bibliographystyle{ipsjsort}
|
|
312 \bibliography{prosym}
|
|
313
|
|
314 % BibTeX を使用しない場合
|
|
315 %\begin{thebibliography}{9}
|
|
316 %\bibitem{latex}玉城将士、谷成雄,河野真治 : \textbf{Cassandraを使ったスケーラビリティのあるCMSの設計 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2011.
|
|
317 %\bibitem{latex}玉城将士 : \textbf{非破壊的木構造を用いた分散CMSの設計と実装 }. 琉球大学理工学研究科修士論文、2013
|
|
318 %\bibitem{latex}大城信康 、杉本優 、河野真治 : \textbf{Data Segment の分散データベースへの応用}. 日本ソフトウェア科学会第30回大会論文集. 、2013
|
|
319 %\bibitem{latex}大城信康 : \textbf{分散Database Jungleに関する研究}. 琉球大学理工学研究科修士論文、2014
|
|
320 %\bibitem{latex}金川竜己、河野真治 : \textbf{非破壊的木構造データベースJungleとその評価 }. 情報処理学会システムソフトウェアとオペレーティング・システム研究会、 2015.
|
|
321 %\end{thebibliography}
|
|
322 \end{document}
|
|
323
|