|
1
|
1 \documentclass[techrep]{ipsjpapers}
|
|
|
2 \usepackage[dvipdfmx]{graphicx}
|
|
|
3 \usepackage{url}
|
|
|
4 \usepackage{listings,jlisting}
|
|
|
5 \usepackage{enumitem}
|
|
|
6
|
|
|
7 \lstset{
|
|
|
8 language=C,
|
|
|
9 tabsize=2,
|
|
|
10 frame=single,
|
|
|
11 basicstyle={\ttfamily\footnotesize},%
|
|
|
12 identifierstyle={\footnotesize},%
|
|
|
13 commentstyle={\footnotesize\itshape},%
|
|
|
14 keywordstyle={\footnotesize\bfseries},%
|
|
|
15 ndkeywordstyle={\footnotesize},%
|
|
|
16 stringstyle={\footnotesize\ttfamily},
|
|
|
17 breaklines=true,
|
|
|
18 captionpos=b,
|
|
|
19 columns=[l]{fullflexible},%
|
|
|
20 xrightmargin=0zw,%
|
|
|
21 xleftmargin=1zw,%
|
|
|
22 aboveskip=1zw,
|
|
|
23 numberstyle={\scriptsize},%
|
|
|
24 stepnumber=1,
|
|
|
25 numbersep=0.5zw,%
|
|
|
26 lineskip=-0.5ex,
|
|
|
27 }
|
|
|
28 \renewcommand{\lstlistingname}{Code}
|
|
|
29
|
|
|
30 \input{dummy.tex} %% Font
|
|
|
31
|
|
|
32 % ユーザが定義したマクロなど．
|
|
|
33 \makeatletter
|
|
|
34
|
|
|
35 \begin{document}
|
|
|
36
|
|
|
37 % 和文表題
|
|
|
38 \title{Gears OS におけるコード記述}
|
|
|
39 % 英文表題
|
|
|
40 \etitle{}
|
|
|
41
|
|
|
42 % 所属ラベルの定義
|
|
|
43 \affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
|
|
|
44 \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.}
|
|
|
45
|
|
|
46 % 和文著者名
|
|
|
47 \author{
|
|
|
48 宮城 光希\affiref{1}
|
|
|
49 \and
|
|
|
50 河野 真治\affiref{2}
|
|
|
51 }
|
|
|
52
|
|
|
53 % 英文著者名
|
|
|
54 \eauthor{
|
|
|
55 Mitsuki MIYAGI\affiref{1}
|
|
|
56 \and
|
|
|
57 Shinji KONO\affiref{2}
|
|
|
58 }
|
|
|
59
|
|
|
60 % 連絡先（投稿時に必要．製版用では無視される．）
|
|
|
61 \contact{宮城 光希\\
|
|
|
62 〒903-0213 沖縄県西原町千原1番地\\
|
|
|
63 琉球大学工学部情報工学科\\
|
|
|
64 TEL: (098)895-2221\qquad FAX: (098)895-8727\\
|
|
|
65 email: mir3636@cr.ie.u-ryukyu.ac.jp}
|
|
|
66
|
|
|
67 % 和文概要
|
|
|
68 \begin{abstract}
|
|
|
69 Gears OS は Continuation based C によってアプリケーションとOSそのものを記述する。
|
|
|
70 OS の下ではプログラムの記述は通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等の記述しなければならない処理が存在する。
|
|
|
71 これらの計算をメタ計算と呼ぶ。
|
|
|
72 メタ計算を通常の計算から切り離して記述するために、Code Gear、Data Gear という単位を提案している。
|
|
|
73 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在する。
|
|
|
74 Code Gear 間の接続は次の Code Gear の番号と thread structure に相当する context によって行われる。
|
|
|
75 ユーザーレベルではメタ構造を直接見ることはなく、継続を用いた関数型プログラミングに見える。
|
|
|
76 メタレベルから見た Data Gear をユーザーレベルの Code Gear に接続するには stub という Meta Code Gear を用いる。
|
|
|
77 stub と Meta はユーザーレベル Code Gear と Data Gear からスクリプトにより作成される。
|
|
|
78 変換に必要な情報はプログラムを構成する Code Gear と Data Gear の集まりから得る。この集まりを Interface として定義している。
|
|
|
79 本論文では、Interfaceを用いたプログラミングと、メタ計算の実例を示す。
|
|
|
80 \end{abstract}
|
|
|
81
|
|
|
82 % 英文概要
|
|
|
83 \begin{eabstract}
|
|
|
84 \end{eabstract}
|
|
|
85
|
|
|
86 % 表題などの出力
|
|
|
87 \maketitle
|
|
|
88
|
|
|
89 % 本文はここから始まる
|
|
|
90
|
|
|
91 % Introduce
|
|
|
92 % Code Gear は関数に比べて細かく分割されているのでメタ計算をより柔軟に記述できる。
|
|
|
93
|
|
5
|
94 % 研究目的
|
|
|
95
|
|
|
96 % 信頼性の高いOS
|
|
|
97 % これをアセンブラにしていろいろなアプリケーションを作る
|
|
|
98 % きょだいなCDGの上で動かすと既存のアプリケーションを動かすことができる
|
|
|
99
|
|
1
|
100 \section{Continuation based C (CbC)}
|
|
|
101 CbC は Code Gear という処理の単位を用いて記述するプログラミング言語である。
|
|
|
102 Code Gear は CbC における最も基本的な処理単位である。
|
|
|
103 Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。
|
|
|
104 CbC では Code Gear は \_\_code という型を持つ関数の構文で定義される。
|
|
|
105 ただし、これは \_\_code 型の戻り値を返すという意味ではなく、Code Gear であることを示すフラグである。
|
|
|
106 Code Gear は戻り値を持たないので、関数とは異なり return 文は存在しない。
|
|
|
107
|
|
|
108 Code Gear から次の Code Gear への遷移は goto による継続で処理を行い、次の Code Gear へ引数として出力を与える。
|
|
|
109 図は Code Gear 間の処理の流れを表している。
|
|
4
|
110 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。
|
|
|
111
|
|
|
112 \begin{figure}[ht]
|
|
|
113 \begin{center}
|
|
|
114 \includegraphics[width=70mm]{./pic/codesegment.pdf}
|
|
|
115 \end{center}
|
|
|
116 \caption{goto による code gear 間の継続}
|
|
|
117 \label{fig:cs}
|
|
|
118 \end{figure}
|
|
1
|
119
|
|
|
120 goto の後に Code Gear 名と引数を並べて、次の Code Gear への遷移を記述する。
|
|
|
121 この goto の行き先を継続と呼ぶ。
|
|
|
122
|
|
|
123 Scheme の継続と異なり CbC には呼び出し元の環境がないので、この継続は単なる行き先である。
|
|
|
124 したがってこれを軽量継続と呼ぶ。
|
|
|
125 軽量継続により、並列化、ループ制御、関数コールとスタックの操作を意識した最適化がソースコードレベルで行えるようにする。
|
|
|
126
|
|
|
127 \section{Gears OS}
|
|
|
128 Gears OS は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
|
|
|
129 Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
|
|
|
130 Gears OS は Input/Output Data Gear の依存関係が解決された Task を並列実行する。
|
|
|
131 Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
|
|
|
132 Code Gear は任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
|
|
|
133 また、接続された Data Gear 以外には参照を行わない。
|
|
|
134 処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
|
|
|
135
|
|
|
136 Gears OS では メタ計算 を Meta Code Gear、Meta Data Gear で表現する。
|
|
|
137 Meta Code Gear は通常のCode Gear の直後に遷移され、メタ計算を実行する。
|
|
|
138 Meta Code Gear で OS の機能であるメモリ管理やスレッド管理を行う。
|
|
|
139
|
|
|
140 CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。
|
|
|
141
|
|
4
|
142 \section{Gears OS の構成}
|
|
|
143 Gears OS は以下の要素で構成される。
|
|
|
144
|
|
|
145 \begin{itemize}
|
|
|
146 \item Context
|
|
|
147 \item TaskQueue
|
|
|
148 \item TaskManager
|
|
|
149 \item Worker
|
|
|
150 \end{itemize}
|
|
|
151
|
|
|
152 図\ref{fig:gearsos} に Gears OS の構成図を示す。
|
|
|
153
|
|
|
154 \begin{figure}[ht]
|
|
|
155 \begin{center}
|
|
|
156 \includegraphics[width=70mm]{./pic/gears_structure}
|
|
|
157 \end{center}
|
|
|
158 \caption{Gears OS の構成図}
|
|
|
159 \label{fig:gearsos}
|
|
|
160 \end{figure}
|
|
1
|
161
|
|
|
162 Gears OS には Context と呼ばれる接続可能な Code Gear、Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
|
|
|
163 Gears OSは必要なCode Gear、Data Gearに参照したい場合、このContext を通す必要がある。
|
|
|
164
|
|
|
165 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
|
|
4
|
166 Context は Task でもあり、TaskManager によって Context が生成され Task Queue へ挿入する。
|
|
|
167 Gears OS における Task Queue は Synchronized Queue で実現される。
|
|
|
168 Worker は TaskQueue から Task である Context を取得し、 Input/Output Data Gear の依存関係が解決されたものから並列実行される。
|
|
|
169
|
|
|
170 \section{CbC による Gears OS 記述の問題}
|
|
|
171
|
|
|
172 Gears OS を CbC で実装する上でメタ計算の記述が煩雑であることがわかった。
|
|
|
173 これらのメタ計算を自動生成することにより Gears OS を記述する上においてより良い構文をユーザーに提供することにした。
|
|
1
|
174
|
|
5
|
175 最初にインターフェースを使う使用例を書く
|
|
|
176
|
|
|
177
|
|
1
|
178 \section{interface の記述}
|
|
5
|
179 % union data はジェネラルなデータセグメントこれには
|
|
|
180 % goto のひきすうとしてつかう フレームを表している
|
|
|
181 関数呼び出しのabi
|
|
|
182 ひきすうで呼び出されるcg ひきすうはぜんぶ定義されていなければならない
|
|
|
183 メタデータセグメント
|
|
|
184 名前付きの変数が現れる
|
|
|
185 書き込みは**読み込みは*
|
|
|
186 いんたーふぇーすなので実装がいる
|
|
|
187
|
|
|
188
|
|
|
189
|
|
|
190
|
|
|
191
|
|
|
192
|
|
|
193
|
|
1
|
194 interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
|
|
|
195 Code Gear、Data Gear に参照するために Context を通す必要があるが、
|
|
2
|
196 interface を記述することでデータ構造のapiと Data Gear を結びつけることが出来、呼び出しが容易になった。
|
|
1
|
197 %create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
|
|
|
198 %return で interface を返し、その先で Code Gear や Data Gear へ継続できるようになる。
|
|
|
199
|
|
4
|
200 \lstinputlisting[label=src:interface, caption=interface]{./src/Stack.cbc}
|
|
|
201
|
|
1
|
202 \section{Gearef、GearImpl}
|
|
5
|
203
|
|
|
204
|
|
|
205
|
|
|
206
|
|
|
207
|
|
1
|
208 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
|
|
4
|
209 Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すため、リスト\ref{gearef1} のようにコードが煩雑になってしまう。
|
|
1
|
210 そこで Code Gear がデータを参照するための Gearef というマクロを定義した。
|
|
|
211 Gearef に Context と型を渡すことでデータの参照が行える。
|
|
|
212 また impliment のデータを参照する際も、ポインタでの記述が複雑になってしまうため 同様に GearImpl を定義した。
|
|
|
213 GearImpl は Context と interface 名、interface の変数名を指定して参照する。
|
|
4
|
214 Gearef と GearImpl を用いたコードがリスト\ref{gearef2}である。
|
|
|
215
|
|
|
216 \lstinputlisting[label=gearef1, caption=Gearef1]{./src/ex_code1}
|
|
|
217 \lstinputlisting[label=gearef2, caption=Gearef2]{./src/ex_code2}
|
|
1
|
218
|
|
|
219 \section{stub Code Gear}
|
|
3
|
220 Code Gear が必要とする Data Gear を取り出す際に Context を通す必要があるが、
|
|
|
221 Context を直接扱うのはセキュリティ上好ましくない。
|
|
1
|
222 そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
|
|
|
223 stub Code Gear は Code Gear 毎に生成され、次の Code Gear へと継続する間に挟まれる。
|
|
|
224 \section{Context、stub Code Segment の自動生成}
|
|
|
225
|
|
|
226 Gears OS では 通常の計算の他に Context や stub などのメタ計算を記述する必要があが、Gears OS を現在の CbC の機能のみを用いて記述するとこのメタ計算の記述を行わなくてはならず、これには多くの労力を要する。
|
|
|
227 この記述を助けるために Context を生成する generate\_context と stub Code Gear を生成する generate\_stub を perl スクリプトで作成した。
|
|
|
228
|
|
|
229 \section{stub Code Segment の生成}
|
|
|
230 stub Code Gear は Code Gear 間の継続に挟まれる Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
|
|
3
|
231 Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
|
|
1
|
232 stub Code Gear を 自動生成することによって Code Gear の記述量を約半分にすることができる。
|
|
|
233
|
|
|
234 stub を生成するために generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得し、引数から必要な Data Gear を選択する。
|
|
|
235 generate\_stub は引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
|
|
|
236 この時既に stub Code Gear が記述されている Code Gear は無視される。
|
|
|
237
|
|
4
|
238 cbc ファイルから、生成した stub Code Gear を加えて stub を加えたコードに変換を行う。(\ref{stack_c})
|
|
|
239
|
|
|
240 \lstinputlisting[label=src:stack_c, caption=stub]{./src/ex_stub}
|
|
1
|
241
|
|
|
242 \section{Context の生成}
|
|
|
243 Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
|
|
|
244 Data Gear を取得するために generate context は context の定義を読み宣言されている Data Gear を取得する。
|
|
|
245
|
|
4
|
246 \lstinputlisting[label=src:context, caption=context]{./src/context1.c}
|
|
|
247
|
|
1
|
248 Code Gear の取得は指定された stub を加えたコードから \_\_code 型を見て行う。
|
|
|
249 取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
|
|
|
250
|
|
|
251 Code/Data Gear の名前とポインタの対応は generate\_context によって生成される enum Code、enum Data を指定することで接続を行う。
|
|
|
252 また、generate context は取得した Code/Data Gear から Context の生成を行うコードも生成する。
|
|
|
253
|
|
|
254 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
|
|
|
255 Code Gear は Context を通して Data Gear へアクセスする。
|
|
|
256 Data Gear の Allocation を行うコードは dataGearInit.cに生成される。
|
|
|
257
|
|
|
258 Data Gear は union Data とその中の struct によって表現される。
|
|
|
259 Context には Data Gear の Data Type の情報が格納されている。
|
|
|
260 この情報から確保される Data Gear のサイズなどを決定する。
|
|
|
261
|
|
4
|
262 \lstinputlisting[label=src:init_context, caption=initcontext]{./src/context2.c}
|
|
|
263
|
|
1
|
264 \section{今後の課題}
|
|
|
265 本研究では LLVM/Clang のデバッグ、interface の記述、CbC ファイルから Gears OS の記述に必要な Context と stub の生成を行う perl スクリプトの生成を行なった。
|
|
|
266 これにより Gears OS のコードの煩雑さは改善され、ユーザーは Context への接続を意識する必要がなくなった。
|
|
3
|
267
|
|
|
268 %しかし、現在のスクリプトでは stub
|
|
|
269
|
|
1
|
270 今後の課題は Code Gear からメタ計算を行う meta Code Gear を生成できるようにし、ユーザーがメタレベルの処理を意識せずにコードを記述できるようにする。
|
|
|
271 また、今回 perl スクリプトによって Context や stub の生成を行なったが、LLVM/clang 上で実装しコンパイラで直接 CbC を実行できるようにすることを目的とする。
|
|
|
272
|
|
5
|
273 % めたけいさんをどこに挟むかというのをかく 上
|
|
|
274
|
|
1
|
275 %\begin{figure}[ht]
|
|
|
276 % \begin{center}
|
|
|
277 % \includegraphics[width=70mm]{./pic/cbc_goto.pdf}
|
|
|
278 % \end{center}
|
|
|
279 % \caption{gotoによる Code Segment 間の接続}
|
|
|
280 % \label{fig:cbc_goto}
|
|
|
281 %\end{figure}
|
|
|
282
|
|
|
283 %\lstinputlisting[label=src:initContext, caption=initContext]{./src/context.c}
|
|
|
284
|
|
|
285 \nocite{*}
|
|
|
286 \bibliographystyle{ipsjunsrt}
|
|
|
287 \bibliography{sigos}
|
|
|
288
|
|
|
289 \end{document}
|
