Mercurial > hg > Papers > 2022 > ikki-master

changeset 2:a2da5ed4a3b3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add about Context etc
author ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
date Sat, 08 Jan 2022 11:59:24 +0900
parents 853d7c65f524
children e655f81a0c76
files Paper/chapter/2-CbC.tex Paper/chapter/3-GearsOS.tex Paper/master_paper.pdf Paper/src/SynchronizedQueue.cbc Paper/src/SynchronizedQueue.h
diffstat 5 files changed, 154 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/Paper/chapter/2-CbC.tex	Thu Jan 06 22:50:45 2022 +0900
+++ b/Paper/chapter/2-CbC.tex	Sat Jan 08 11:59:24 2022 +0900
@@ -11,8 +11,8 @@
 CbCにはCodeGearとDataGearという二つのプログラミング概念が存在する。
 CodeGearは関数に代わり宣言されるプログラミング単位と呼べる。
 CbCプログラミングでは連続したCodeGear間を遷移していくことで構成される。
-CodeGearはgotoという命令で遷移をしていくが、その際にDataGearと呼ばれる変数データを次のCodeGearへ引き渡していく。
-DataGearはCodeGearが処理の際に参照する専用の変数データであると言える。
+CodeGearはgotoという命令で遷移をしていくが、その際にDataGearと呼ばれる任意の型を設定した変数データを次のCodeGearへ引き渡していく。
+そのため、DataGearはCodeGearが処理の際に参照する専用の変数データであると言える。
 特に、CodeGear実行の際に入力されるDataGearをInputDataGear、CodeGearの処理後に出力されるDataGearをOutputDataGearと呼ぶ。
 CodeGearはInputDataGearを参照しながら処理を実行し、OutputDataGearとして次のCodeGearへ必要なデータを出力する。
 CodeGearとDataGearの関係を図\ref{fig:cgdg}に示す。
@@ -26,10 +26,11 @@
 \end{figure}
 
 
-CodeGearは関数呼び出しのようにスタックを持たないため、
+CodeGearは通常の関数呼び出しのようにスタックを持たないため、
 一度CodeGearから別のCodeGearへ継続した場合、元の処理へ戻ってくることができない。
 言い換えると、CodeGearから別のCodeGearへgotoで遷移した際、元のCodeGear内で使用されていた変数データなどの環境は全て破棄される。
-この点からGearsOSのループ処理はCodeGearの再帰呼び出しで実装することが望ましい。
+この点からGearsOSのループ処理はCodeGearの再帰呼び出しで実装することが望ましく、
+またgotoで遷移をした際、gotoより後に記述した処理は実行されることなく次の処理へ移るため、これを意識したプログラミングが必要となる。
 
 
 \section{CbCの例題}
@@ -40,7 +41,8 @@
 
 今回のソースコードでは、
 mainから二つのint型のDataGearの入力と共にCG1へgotoで遷移、
-続いてCG2へCG1での処理結果をDataGearとして引き渡し遷移する流れとなっている。
+続いてCG2へCG1での処理結果をDataGearとして引き渡し遷移、
+最後にexitをするという流れとなる。
 
 \lstinputlisting[label=src:cbc_sample, caption=CbCの例題]{src/CbC_sample.cbc}
 
@@ -52,8 +54,8 @@
 メタレベルを考慮した上でCbCのCodeGear, DataGearの遷移を図式化すると図\ref{fig:meta-cgdg}の下段のように表現できる。
 CbCではCodeGearの遷移に必要な遷移先のCodeGearへのDataGearの受け渡しやデータの整合性の確認などは
 CodeGearごとに準備されたMetaCodeGearと呼ばれるメタなCodeGearで行われ、
-またMetaCodeGearで使用されるDataGearをMetaDataGearと呼ぶ。
-特に、CodeGearの実行直前に呼び出されるMetaCodeGearを特にStubCodeGearと呼ぶ。
+MetaCodeGearで使用されるDataGearをMetaDataGearと呼ぶ。
+また、CodeGearの実行直前に呼び出されるMetaCodeGearを特にStubCodeGearと呼ぶ。
 
 MetaCodeGearとMetaDataGearはプログラマが直接実行するのではなく、
 ビルド時に実行される、Perlスクリプトによって実装されたトランスコンパイラによって自動的に生成される。
--- a/Paper/chapter/3-GearsOS.tex	Thu Jan 06 22:50:45 2022 +0900
+++ b/Paper/chapter/3-GearsOS.tex	Sat Jan 08 11:59:24 2022 +0900
@@ -3,26 +3,28 @@
 GearsOSはContinuation based Cを用いることにより、ノーマルレベルとメタレベルの分離を行い、
 プログラマが記述したノーマルレベルのコードをメタレベルから信頼性の検査を行えるような仕組みを作ることにより、
 OS自身の信頼性の向上を目指している。
-メタレベルのプログラムはPerlスクリプトによるトランスコンパイラにて実装されており、
-基本的にユーザーはノーマルレベルのプログラムの記述によりメタレベル分離の恩恵を受けられる仕組みとなっている。
+メタレベルのプログラムはPerlスクリプトによるトランスコンパイラにて自動生成されるように構成されており、
+基本的にユーザーはノーマルレベルのプログラムの記述のみ行うことで、メタレベル分離の恩恵を受けられる仕組みとなっている。
+プログラマは.cbcファイルに対して記述を行うことでプログラムの構成を行うが、
+実際に動作するプログラムはトランスコンパイラによりmeta部分の記述が行われた純粋な.cファイルが動作する。
 
 現状ではCbCの言語フレームワークとして実装されており、OSとして実際に起動するためには実装が必要となる機能が多く存在している。
 必要な機能をCbCによる記述により実装していくことでOSの完成を目指す。
 
 \section{Interface}
 GearsOSの重要な仕様としてInterfaceが存在する。
-Interfaceの一つ目の役割として、通常のプログラミングにおけるモジュール化の仕組みと同様の役割を持つ。
-GearsOSに実装されているQueueのInterfaceをソースコード\ref{src:cbc_sample}に示す。
+Interfaceの役割の一つとして、通常のプログラミングにおけるモジュール化の仕組みと同様の役割を持つ。
+GearsOSに実装されているQueueのInterfaceをソースコード\ref{src:Queue.h}に示す。
 
-\lstinputlisting[label=src:Queue.h, caption=CbCの例題]{src/Queue.h}
+\lstinputlisting[label=src:Queue.h, caption=Queueのインターフェース]{src/Queue.h}
 
-GearsOSにおけるInterfaceにはプログラム内で使われるCodeGearとそのCodeGearに入出力されるDataGearを記述する。
+GearsOSにおけるInterfaceは、ヘッダファイルへプログラム内で使われるCodeGearとそのCodeGearに入出力されるDataGearを記述する。
 5から10行目にはAPIとなるCodeGearが宣言されている。
 また、2, 3行目のunion Data型の変数はAPIのCodeGearで使用されるDataGearである。
 
 コード内のCodeGearの第1引数はImpl*型の変数となっており、Interfaceを引き継いだImplementのポインタとなる。
-これはCbCはスタックを持たず、CodeGearの遷移の際に必要な情報はDataGearとして持ち運ぶ必要があるため、
-DataGearとして構造体のポインタを設定している。
+これはCbCはスタックを持たず、複数のCodeGear間をまたいで必要な情報はDataGearとして持ち運ぶ必要があるため、
+DataGearとしてImplementのポインタを設定している。
 また、このImplementのポインタはgotoでの遷移の際はトランスコンパイラによる補完により、gotoの引数として記述する必要はない。
 
 \texttt{\_\_code next(...)}は
@@ -30,4 +32,95 @@
 そのAPIのCodeGearの処理後の遷移先のCodeGearを指定することができる。
 \texttt{\_\_code whenEmpty(...)}も同様に別CodeGearへのポインタである。
 9行目のCodeGearではnextとWhenEmptyと二つのCodeGearのポインタを入力することにより、
-処理の結果により別れる二つの遷移先を用意している。
+処理の結果に応じた複数の遷移先を用意するように構成している。
+
+Interfaceに加え、ImplementationはDataGearとみなすことができる。
+また、GearsOSでは後述のContextと呼ばれる環境内に全てのDataGearとCodeGearが保持されている。
+Context内ではInterfaceやImplementで定義されたAPIと変数は構造体として記録され、
+またそれら全ての構造体は共用体(union)のData型に登録されている。
+
+\section{Implementation}
+GearsOSはInterfaceの実装となるImplementの形定義ファイルが実装されている。
+Implementの定義にはInterfaceと同様にヘッダファイルを記述する。
+ソースコード\ref{src:SynchronizedQueue.h}にQueueインターフェースの実装の型定義となるSynchronizedQueue.hを示す。
+Implementは実装元のInterfaceを必ず決定する必要があるため、1行目のようにimpl名の後に実装元のInterface名を記述する必要がある。
+
+作成したImplementは実装元のInterface名のImpl型として使用することが可能となり、
+Impl内で記述した変数は後述のコンストラクタで行われる処理によって、プログラム上でimpl*型変数\texttt{->}変数名で参照が行えるようになる。
+また、GearsOSは全てのInterface, Implの情報を構造体としてコンパイルする際にContextに記録するため、
+ソースコード中2,3,4行ではImplに別のInterfaceを構造体として記述することで、
+プログラム内で他のInterfaceを実装したプログラム、もしくはInterfaceを純粋な構造体としてを呼び出すことができる。
+
+\lstinputlisting[label=src:SynchronizedQueue.h, caption=Queue.hの実装となるSynchronizedQueue.h]{src/SynchronizedQueue.h}
+
+\section{GearsOSのプログラム例}
+GearsOSのプログラムの一例として先述したソースコード\ref{src:Queue.h}、\ref{src:SynchronizedQueue.h}の実装となる
+SynchronizedQueue.cbcの一部分をソースコード\ref{src:SynchronizedQueue.cbc}に示す。
+GearsOSにはImplementが記述されたヘッダファイルから、cbcファイルの雛形を自動生成するimpl2cbc.plが導入されている。
+雛形には7行目のQueue*を返すcreateSychronizedQueueとその中の処理、
+加えて22行目のputSynchronizedQueueのようなInterfaceのヘッダファイル内で記述されたCodeGearが用意されている。
+
+プログラム内で呼び出したいInterfaceは2,3行目のような記述が必要となる。
+7から20行目に記述されているcreateSynchronizedQueueはQueueインターフェースをSynchronizedQueueで実装する際のコンストラクタであると言える。
+関数呼び出しで実装されており、返り値はInterfaceのポインタである。
+
+コンストラクタ内の記述を解説すると、8,9行目にてQueueとSynchronizedQueueのアロケーションを行い、
+14行目の記述にてQueueInterface内のDataGearであるqueueへSynchronizedQueueへのポインタを格納している。
+8, 10行目でnew演算子が使われているがこれはGearsOS独自のシンタックスの一つである。
+コンパイル時に後述のContextが持つDataGearのヒープ領域のアロケーションを行うマクロへ置き換えられる。
+10から13行目の記述では初期はImplementの型定義ファイルに記述された変数の宣言が行われている。
+当然プログラマは、宣言した変数に任意の状態が設定されるように変更することができる。
+13行目ではatomic型のinterfaceをAtomicReference型で実装を行っている。
+15から18行目はInterfaceの定義にて記述されたAPIとcbcプログラム内のCodeGearの紐付けを行っている。
+現状では必ずC\texttt{\_} + API名 + Impl名;と記述する必要がある。
+
+\lstinputlisting[label=src:SynchronizedQueue.cbc, caption=SynchronizedQueue.cbcの記述の一部]{src/SynchronizedQueue.cbc}
+
+22行目から38行目はInterfaceで宣言されたputAPIの実装部分である。
+Interfaceで宣言されたAPIと対応するCodeGearは.cbcファイル上ではAPI名 + Impl名で宣言する必要がある。
+コンストラクタ内13行目にてatopmiReferenceの実装を行っているが、atomicInterfaceへのポインタは最終的に返り値のqueueポインタが保持するため、
+atomicInterfaceで定義されたAPIのCodeGearへ遷移することができるようになる。
+現状のGearsOSでは一度、Interfaceのポインタ型をプログラム内で宣言し、コンストラクタで生成した実装のポインタを代入、
+そしてgoto文を用いて遷移するという冗長な記述が必要となっているため、トランスコンパイラにより改善するといった手段が考えられる。
+
+
+\section{Context}
+ContextとはGearsOSにおける従来のOSのプロセスに相当する概念であるとされる。
+英単語としてのcontextは意味として前後関係や状況、環境を意味し、
+軽量継続を主体として処理が行われるGearsOSにおいて、Contextは継続に必要なデータ(CodeGear, DataGear)を全て保持している。
+GearsOSではCodeGearの遷移の際にこのContextに対してDataGearの一時的な書き込みや、遷移先のポインタなどの情報を書き込み、
+Contextを持ち運ぶことにより処理の整合性を保っている。
+ノーマルレベルのプログラム上では意識することは少ないが、
+メタレベルでは全てのCodeGearは必ずContextをDataGearとして呼び出す仕組みとなっている。
+そのためContextはGear概念で言うとMetaDataGearに相当する。
+
+図\ref{fig:context}にCodeGearが遷移する際のContextに対するDataGearの書き込みまたは呼び出しの形を示す。
+CodeGearが遷移する際にOutputDataGearをContextに対して書き込みを行う。
+続いて遷移先のstubCodeGearがContextから遷移先CodeGearが必要とするInputDataGer
+と出力する必要があるOutputDataGearを参照する。
+stubCodeGearでDataGearの準備が完了したあと、本体のCodeGearへ遷移し処理により出力されたデータをOutPutDataGearとして書き出す。
+以上の手順で軽量継続の際にContextの参照が行われる。
+
+Contextはノーマルレベルから直接参照を行わない。
+Contextをユーザーが任意の操作することはノーマルレベルとメタレベルの分離した意味が無くなってしまうためである。
+Contextに対するDataGearの操作はstubCodeGearのみならずCodeGear内でも行われるが、それらの記述はトランスコンパイラの自動生成により行われる。
+先述のnew演算子がその一例として挙げられる。
+もしnew演算子でなく、Contextが保持するDataGearに対してAllocate操作が行えてしまうと、
+並行に動作している他のUser Contextの中身を書き換えるなどプログラム処理に支障が出るような不正な改ざんが行えてしまう。
+
+\begin{figure}[tb]
+    \begin{center}
+        \includegraphics[width=150mm]{./images/Context_ref.pdf}
+    \end{center}
+    \caption{CodeGearの遷移にて行われるContextに対するDataGear参照}
+    \label{fig:context}
+\end{figure}
+
+Contextはプロセスに相当するため、ユーザープログラムごとにContextが存在する。
+このContextをUser Contextと呼ぶ。
+また実行されているGPUやCPUごとにもContextが必要となり、これをCPU Contextと呼ぶ。
+加えてOSとしてUser ContextやCPU Contextを含めた、全体を管理するためのContextも必要となる。
+これはKernel ContextやKContextと呼ばれている。
+これらのContextは特に、GearsOSに実装されているpar gotoと呼ばれる並列処理用の構文の内部構成などのメタレベルのプログラミングの際に強く意識されている。
+GearsOSではKernelContextが複数のUser ContextとCPU Contextを管理し、
+ノーマルレベルのプログラムに応じてWorkerに対してTaskを割り振ることで分散処理の機構が実現されている。
Binary file Paper/master_paper.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/SynchronizedQueue.cbc	Sat Jan 08 11:59:24 2022 +0900
@@ -0,0 +1,38 @@
+#include "../context.h"
+#interface "Queue.h"
+#interface "Atomic.h"
+#include <stdio.h>
+
+
+Queue* createSynchronizedQueue(struct Context* context) {
+    struct Queue* queue = new Queue();
+    struct SynchronizedQueue* synchronizedQueue = new SynchronizedQueue();
+    synchronizedQueue->top = new Element(); // allocate a free node
+    synchronizedQueue->top->next = NULL;
+    synchronizedQueue->last = synchronizedQueue->top;
+    synchronizedQueue->atomic = createAtomicReference(context);
+    queue->queue = (union Data*)synchronizedQueue;
+    queue->take  = C_takeSynchronizedQueue;
+    queue->put  = C_putSynchronizedQueue;
+    queue->isEmpty = C_isEmptySynchronizedQueue;
+    queue->clear = C_clearSynchronizedQueue;
+    return queue;
+}
+
+__code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) {
+    Element* element = new Element();
+    element->data = data;
+    element->next = NULL;
+    Element* last = queue->last;
+    Element* nextElement = last->next;
+    if (last != queue->last) {
+        goto putSynchronizedQueue();
+    }
+    if (nextElement == NULL) {
+        struct Atomic* atomic = queue->atomic;
+        goto atomic->checkAndSet(&last->next, nextElement, element, next(...), putSynchronizedQueue);
+    } else {
+        struct Atomic* atomic = queue->atomic;
+        goto atomic->checkAndSet(&queue->last, last, nextElement, putSynchronizedQueue, putSynchronizedQueue);
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/SynchronizedQueue.h	Sat Jan 08 11:59:24 2022 +0900
@@ -0,0 +1,5 @@
+typedef struct SynchronizedQueue <> impl Queue {
+  struct Element* top;
+  struct Element* last;
+  struct Atomic* atomic;
+} SynchronizedQueue;