10
|
1 \documentclass[twocolumn,twoside,9.5pt]{jarticle}
|
|
2 \usepackage[dvipdfmx]{graphicx}
|
|
3 \usepackage{picins}
|
|
4 \usepackage{fancyhdr}
|
|
5 \usepackage{abstract}
|
|
6 \usepackage{url}
|
|
7 %\pagestyle{fancy}
|
|
8 \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
|
|
9 \rhead{}
|
|
10 \cfoot{}
|
|
11
|
|
12 \setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
|
|
13 \setlength{\headheight}{0mm}
|
|
14 \setlength{\headsep}{5mm}
|
|
15 \setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
|
|
16 \setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
|
|
17 \setlength{\textwidth}{181mm}
|
|
18 \setlength{\textheight}{261mm}
|
|
19 \setlength{\footskip}{0mm}
|
|
20 \pagestyle{empty}
|
|
21
|
|
22 \input{dummy.tex}
|
|
23 \renewcommand{\abstractname}{Abstract}
|
|
24 \begin{document}
|
|
25 \title{CbC 言語による OS 記述}
|
|
26 %\title{Supporting NAT in Screen Sharing System TreeVNC}
|
|
27 \author{135756F 氏名 {宮城}{光希} 指導教員 : 河野 真治}
|
|
28 \date{}
|
|
29 \twocolumn [
|
|
30 \maketitle
|
|
31 \begin{onecolabstract}
|
12
|
32 We are developping Gears OS using Continuation based C (CbC).
|
|
33 Gears OS provids highly reliable computation using meta computation.
|
|
34 CbC gives Code Gear and Data Gear as programing units.
|
|
35 A transfar from a Code Gear to another Code Gear is implemented using a CbC's goto statement,
|
|
36 which is compiled as a jump instraction in CbC.
|
|
37 Meta computations are key components of Gears OS, which provids memory managements, thread managements,
|
|
38 managements of Data/Code Gear themselves.
|
|
39 CbC's goto statments provids a ways of implementing meta computations.
|
|
40 From a view point of meta computation, Data Gear or Code Gear are uniform data units, which are implemented
|
|
41 as union Data in CbC.
|
|
42 In the meta level, a transfar from a Code Gear is a goto statement to meta Code Gear with next Code Gear number and
|
|
43 a Context which coresponds thread structure or an enviroments in a functional programing.
|
|
44 A meta Code Gear handles meta computations such as meta computations.
|
|
45 From a user level, meta structures are not visible directly and a Code Gear looks like a function using continuations.
|
|
46 A stub Code Gear is used as a bridge between meta level and user(nomal) level.
|
|
47 In this paper we create scripts which generate meta Code Gear and stub Code Gear from nomal level Code Gear and Data Gear.
|
|
48 Using these scripts, we can provide a interface mechanisms which are packages of Code Gears and Data Gears.
|
|
49 A simple TaskManager is constracted using the interfaces which is a simple operating systems.
|
|
50 We will constracts various compornents of Gears OS and meta computations which provids reliabilty.
|
|
51 For an example, generating agda program from nomal level Code Gear provids proof suports of the Code Gear.
|
|
52 %CbC で OS を記述する。
|
|
53 %CbCはLLVMで実装されている。
|
|
54 %codeとcode のあいだをcall ではなくjmpで結ぶことができる(goto)
|
|
55 %gotoをつかうことによりOSに必須なmeta計算を実現できる
|
|
56 %メタ計算は例えばメモリ管理スレッド管理CPUやGPUの資源管理そしてData/Code Gear の管理などである
|
|
57 %metaレベルではcode/data gear は一つの塊として操作される。これをcbcではunion dataとして実装している
|
|
58 %code gear 間の接続はつぎのcode gearの番号とthread structure に相当するcontextをmeta code gear にgoto する
|
|
59 %meta code gear で os の 機能であるメモリ管理やスレッド管理を行う。
|
|
60 %ユーザーレベルではmeta構造を直接見ることはなく、継続を用いた関数型プログラミングに見える
|
|
61 %metaレベルから見たdata gearをゆーざーれべるのcode gearに接続するにはstub というmeta code gear を用いる
|
|
62 %stubとmetaはユーザーレベルcodegear とdatagearから生成することができる
|
|
63 %本論文ではstub とcontext 管理構造を生成するスクリプトを作成した
|
|
64 %これによりcode gear とdeta gear をデータを操作するinterface というまとまりにすることができる。
|
|
65 %この仕組みの上に並列処理用のtaskmanagerを簡単なosとして構成することができた。
|
|
66 %こんごはgears os の様々な構成要素を作成していきたい。
|
|
67 %またメタ計算を用いて信頼性をあげる方法についても研究を進めていく。
|
|
68 %例えばユーザーレベルプログラムから定理証明支援系であるagdaのコードを生成することにより、プログラムの正しさを証明していくことが考えられる。
|
10
|
69 \end{onecolabstract}]
|
|
70 \thispagestyle{fancy}
|
|
71
|
|
72 \section{メタ計算の重要性}
|
|
73 プログラムを記述する際、通常の処理の他に、メモリ管理、スレッドの待ち合わせやネットワークの管理、エラーハンドリング等、記述しなければならない処理が存在する。
|
|
74 これらの計算を Meta Computation と呼ぶ。
|
|
75
|
|
76 Meta Computation を通常の計算から切り離して記述するためには処理を細かく分割する必要がある。しかし、関数やクラスなどの単位は容易に分割できない。
|
|
77
|
|
78 そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
|
|
79
|
|
80 Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
|
|
81 Code Gear、Data Gear にはそれぞれメタレベルの単位である Meta Code Gear、Meta Data Gear が存在し、これらを用いて Meta Computation を実現する。
|
|
82
|
|
83 Continuation based C (CbC) はこの Code Gear 単位を用いたプログラミング言語として開発している。
|
|
84
|
|
85 CbCは軽量継続による遷移を行うので、継続前の Code Gear に戻ることはなく、状態遷移ベースのプログラミングに適している。
|
|
86
|
|
87 また、当研究室で開発している Gears OS は Code Gear、 Data Gear の単位を用いて開発されており、CbC で記述されている。
|
|
88
|
|
89 本研究では CbC を用いての Gears OS の実装と CbC における ユーザーの関知しない Meta Computationの自動生成を行なう。
|
|
90
|
|
91 %\begin{figure}[htbp]
|
|
92 % \begin{center}
|
|
93 % \includegraphics[width=50mm]{./pic/treeVnc.pdf}
|
|
94 % \end{center}
|
|
95 % \caption{構成される木構造}
|
|
96 % \label{fig:tree}
|
|
97 %\end{figure}
|
|
98
|
|
99 \section{Continuation based C (CbC)}
|
|
100 CbC は 処理を Code Gear とした単位を用いて記述するプログラミング言語である。
|
|
101 Code Gear は入力と出力を持ち、CbC では引数が入出力となっている。
|
|
102 Code Gear から次の Code Gear へと goto による継続で遷移で処理を行い、引数として出力を与える。
|
|
103 図\ref{fig:cs}は Code Gear 間の処理の流れを表している。
|
|
104
|
|
105 \begin{figure}[htpb]
|
|
106 \begin{center}
|
|
107 \scalebox{0.5}{\includegraphics{pic/codesegment.pdf}}
|
|
108 \end{center}
|
|
109 \caption{goto による code gear 間の継続}
|
|
110 \label{fig:cs}
|
|
111 \end{figure}
|
|
112
|
|
113 \section{Gears OS}
|
|
114 Gears OS では並列実行するための Task を、実行する Code Gear 、実行に必要な Input Data Gear 、Output Data Gear の組で表現する。
|
|
115 Data Gear はデータの単位であり、int や文字列などの Primitive Type を持っている。
|
|
116 Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
|
|
117 また、接続された Data Gear 以外には参照を行わない。
|
|
118 処理やデータの構造が Code Gear、Data Gear に閉じているため、これにより実行時間、メモリ使用量などを予測可能なものにすることが可能になる。
|
|
119
|
|
120 Gears OS では Meta Computation を Meta Code Gear、Meta Data Gear で表現する。
|
|
121 Meta Code Gear は通常のCode Gear の直後に遷移され、Meta Computation を実行する。
|
|
122
|
|
123 CbC は Code Gear を処理の単位として用いたプログラミング言語であるため、Gears OS の Code Gear を記述するのに適している。
|
|
124
|
|
125 図\ref{fig:gearsos} に Gears OS の構成図を示す。
|
|
126
|
|
127 \begin{figure}[htpb]
|
|
128 \begin{center}
|
|
129 \scalebox{0.2}{\includegraphics{pic/gearsos.pdf}}
|
|
130 \end{center}
|
|
131 \caption{Gears OS の構成図}
|
|
132 \label{fig:gearsos}
|
|
133 \end{figure}
|
|
134
|
14
|
135 \section{Context}
|
|
136 Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear である。
|
|
137 Gears OS は必要な Code/Data Gear に参照したい場合、この Context を通す必要がある。
|
|
138 メインとなる Context と Worker 用の Context がある。
|
|
139 Temporal Data Gear のためのメモリ空間は Context 毎に異なり、互いに干渉することはできない。
|
10
|
140
|
14
|
141 Context は Task でもあり、TaskManager によって Context が生成され CPUWorker へ送られる。
|
|
142 Worker に渡された Task である Context の Input/Output Data Gear の依存関係が解決されたものから並列実行される。
|
10
|
143
|
14
|
144 \section{interface の記述}
|
|
145 interface を記述することで Context から Code Gear が呼び出せるようになった。
|
|
146 create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
|
|
147 return で interface を返し、その先で interface で指定した Code Gear へ継続できるようになった。
|
|
148
|
|
149 \section{Gearef、GearImpl}
|
|
150 Context には Allocation 等で生成した Data Gear へのポインタが格納されている。
|
|
151 Code Gear が Context にアクセスする際、ポインタを使用してデータを取り出すためコードが煩雑になってしまう。
|
|
152 そこで Code Gear がデータを参照するための Gearef というマクロを定義した。
|
|
153 Gearef に Context と型を渡すことでデータの参照が行える。
|
|
154 また impliment を参照する際も、ポインタでの記述が複雑になってしまうため 同様に GearImpl を定義した。
|
|
155 GearImpl は Context と interface 名、interface の変数名を指定して参照する。
|
|
156
|
|
157 \section{stub Code Gear}
|
|
158 Code Gear が必要とする Data Gear を取り出す際に Context を通す必要がある。
|
|
159 しかし、Context を直接扱うのはセキュリティ上好ましくない。
|
|
160 そこで Context から必要なデータを取り出して Code Gear に接続する stub Code Gear を定義し、これを介して間接的に必要な Data Gear にアクセスする。
|
|
161 stub Code Gear は Code Gear が Code Gear へと継続する間に挟まれる。
|
|
162 必要とする Data Gear を Context から取り出すという処理を行うものである。
|
|
163 stub Code Gear は Code Gear 毎に生成される。
|
|
164
|
|
165 \section{Context, stub の自動生成}
|
|
166 Gears OS では通常の Computation の他に Context や stub などの Meta Computation を記述する必要がある。
|
|
167 Gears OS を現在の CbC の機能のみを用いて記述すると Context や stub Code Gear の記述を行わなくてはならず、これには多くの労力を要する。
|
|
168 そのため、この記述を助けるために Context を生成する generate\_context と stub Code Gear を生成する generate\_stub を perl スクリプトで作成した。
|
10
|
169
|
|
170
|
|
171 \nocite{*}
|
|
172 \bibliographystyle{junsrt}
|
|
173 \bibliography{reference}
|
|
174 \end{document}
|