% Todo
% 並列処理 の全体的な説明
% 構成のセクションいるかしら?
% par goto をコンパイルタイミングでflowを解析し(モデル検査で)処理が軽い場合は並列ではなく call にするみたいな最適化
% taskManager の初期化のコードはいらない

\chapter{Gears OSの並列処理}
Gears OS では実行の Task を Code Gear と Input/Output Data Gear の組で表現する。
Input/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う。
Gears OS では 並列実行する Task を Context で表現する。
Context には Task 用の情報として、実行される Code Gear、Input/Output Data Gear の格納場所、待っている Input Data Gear のカウンタ等を持っている
Task の Input Data Gear が揃っているかを TaskManager で判断し、 実行可能な Task を Worker に送信する。
Worker は送信された Task が指定した Code Gear を実行し、Output Data Gear を書き出す。

\section{SynchronizedQueue}
SynchronizedQueue は Worker の Queue として使用される。
Worker の Queue は TaskManager を経由して Task を送信するスレッドと Task を取得する Worker 自身のスレッドで扱われる。
そのため SynchronizedQueue はマルチスレッドでもデータの一貫性を保証する Queue を実装する必要がある。

データの一貫性を保証する解決例としての 1 つとしてロックを使った解決方法がある。
しかし、ロックを行ってデータを更新した場合、同じ Queue に対して操作を行う際に待ち合わせが発生し、全体の並列度が下がってしまう。
そこで、Gears OS ではデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue を実装している。
CAS は値の比較、更新をアトミックに行う命令である。
CAS を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。
異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。

Gears OS ではこの CAS を行うための Interface を定義している(Code\ref{atomicInterface})。
この Interface では、Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義して
いる(Code\ref{atomicInterface} 6行目)。

\lstinputlisting[label=atomicInterface, caption=AtomicInterface]{./src/atomicInterface.h}

AtomicInterface での CAS の実際の実装を Code\ref{atomicImpl} に示す。
実際の実装では \_\_sync\_bool\_compare\_and\_swap 関数を呼び出すことで CAS を行う(Code\ref{atomicImpl} 2行目)。
この関数は第一引数に渡されたアドレスに対して第二引数の値から第三引数の値ヘ CAS を行う。
CAS に成功した場合、true を返し、失敗した場合は false を返す。
Code\ref{atomicImpl} では CAS に成功した場合と失敗した場合それぞれに対応した Code Gear へ継続する。

\lstinputlisting[caption=CAS の実装, label=atomicImpl]{./src/atomicImpl.cbc}

SynchronizedQueue の Data Gear の定義を Code\ref{synchronizedQueue} に示す。
SynchronizedQueue はデータのリストの先頭と、終端のポインタを持っている。
Queue を操作する際はこのポインタに対して CAS をすることでデータの挿入と取り出しを行う。

\lstinputlisting[caption=SynchronizedQueue の定義, label=synchronizedQueue]{./src/synchronizedQueue.h}

\section{並列構文}
Gears OS の並列構文は par goto文で用意されている(Code\ref{pargoto})。
\lstinputlisting[caption=par goto による並列実行, label=pargoto]{./src/parGotoCreateTask.cbc}
par goto の引数には Input/Output Data Gear と 実行後に継続する \_\_exit を渡す。
par goto で生成された Task は \_\_exit に継続することで終了する。

この par goto 文は通常のプログラミングの関数呼び出しのように扱うことができる。

Code\ref{perlpargoto} は par goto である Code\ref{pargoto} を perl スクリプトによって変換が行われたコードである。
\lstinputlisting[caption=perl スクリプトによる par goto の変換, label=perlpargoto]{./src/parGotoCreateTask.c}

par goto文でも 通常の goto 文と同様にメタへの goto 文へ置き換えられるが、par goto 文では通常の goto 文とは異なるメタへと継続する。
Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、
Output Data Gear への書き出し処理(Commit)に継続される。

Code Gear は Input に指定した Data Gear が全て書き込まれると実行され、実行した結果を Output に指定した Data Gear に書き出しを行う。
Code Gear の引数である\_\_next が持つ引数の Data Gear が Output Data Gear となる。

書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。
参照した Task が持つ実行に必要な Input Data Gear カウンタのデクリメントを行う。
カウンタが0になると Task が待っている Input Data Gear が揃ったことになり、
その Task を TaskManager 経由で 実行される Worker に送信する。