# HG changeset patch
# User mir3636
# Date 1523598040 -32400
# Node ID e23c914e27b4d4163951a7048ec688db2f1bd31e
# Parent  75ef5a43fb0505f41ffca7b7ebe2bd39aa96a77f
update

diff -r 75ef5a43fb05 -r e23c914e27b4 Paper/sigos.tex
--- a/Paper/sigos.tex	Thu Apr 12 21:53:46 2018 +0900
+++ b/Paper/sigos.tex	Fri Apr 13 14:40:40 2018 +0900
@@ -105,7 +105,7 @@
 
 \section{OS の拡張性と信頼性の両立}
 
-さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。OS の信頼性を保証する事自体が難しいが、時代とともに進歩する。
+さまざまなコンピュータの信頼性の基本はメモリなどの資源管理を行う OS である。OS の信頼性を保証する事自体が難しいが、時代とともに進歩する
 ハードウェア、サービスに対応して OS 自体が拡張される必要がある。
 OS は非決定的な実行を持ち、その信頼性を保証するには、従来のテストとデバッグでは不十分であり、テストしきれない部分が残ってしまう。
 これに対処するためには、証明を用いる方法とプログラムの可能な実行をすべて数え上げるモデル検査を用いる方法がある。
@@ -305,9 +305,10 @@
 
 Context は Task でもあり、Taskは通常のOSのスレッドに対応する。
 Task は実行する Code Gear と Data Gear をすべて持っている。
-TaskManager によって Context が生成され TaskQueue へ挿入する。
+TaskManager は Task を実行する Worker の生成、管理、Task の送信を行う。
 Gears OS における Task Queue は Synchronized Queue で実現される。
-Worker は TaskQueue から Task である Context を取得し、 Input/Output Data Gear の依存関係が解決されたものから並列実行される。
+Worker は TaskQueue から Task である Context を取得し、Task の Code Gear を実行し、Output Data Gear の書き出しを行っている。
+Input/Output Data Gear の依存関係が解決されたものから並列実行される。
 
 \section{Interface}
 Interface は呼び出しの引数になる Data Gear の集合であり、そこで呼び出される Code Gear のエントリである。
@@ -372,6 +373,44 @@
 
 \lstinputlisting[label=init_context, caption=Perlスクリプトで生成されたinitContext]{./src/gencontext.c}
 
+\section{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 を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。
+異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。
+%CAS のコード
+
+%\section{依存関係の解決}
+
+\section{並列構文}
+Gears OS の並列構文は par goto文で用意されている。
+par goto の引数には Input/Output Data Gear と 実行後に継続する \_\_exit を渡す。
+par goto で生成された Task は \_\_exit に継続することで終了する。
+Gears OS の Task は Output Data Gear を生成した時点で終了するので、par goto では直接 \_\_exit に継続するのではなく、
+Output Data Gear への書き出し処理(Commit)に継続される。
+
+書き出し処理は Data Gear の Queue から、依存関係にある Task を参照する。
+参照した Task が持つは実行に必要な Input Data Gear カウンタのデクリメントを行う。
+カウンタが0になると Task が待っている Input Data Gear が揃ったことになり、
+その Task を TaskManager 経由で 実行される Worker に送信する。
+
+この par goto 文は通常のプログラミングの関数呼び出しのように扱うことができる。
+
+
 \section{比較}
 
 従来のプログラミングスタイルとの比較。