# HG changeset patch
# User mir3636
# Date 1523607324 -32400
# Node ID 48561c7a20366ca1e0ee178145f871d6f2a579dd
# Parent  6076ec5e33dec9d926b6f9744298f1d5cfc918d5
add src

diff -r 6076ec5e33de -r 48561c7a2036 Paper/sigos.tex
--- a/Paper/sigos.tex	Fri Apr 13 15:07:19 2018 +0900
+++ b/Paper/sigos.tex	Fri Apr 13 17:15:24 2018 +0900
@@ -75,7 +75,7 @@
     システムやアプリケーションを記述するためにCode Gear と Data Gear を柔軟に再利用する必要がある。
     このときに機能を接続するAPIと実装の分離が可能であることが望ましい。
     Gears OS の信頼性を保証するために、形式化されたモジュールシステムを提供する必要がある。
-    本論文では、Interface を用いたモジュールシステムの説明とその応用としての並列APIについて考察する。
+    本論文では、Interface を用いたモジュールシステムの説明とその応用としての並列 API について考察する。
     並列APIは継続を基本とした関数型プログラミングと両立する必要がある。
     ここでは、CbC の goto 文を拡張したpar goto 文を導入する。
     par goto では並列実行のための実行 Context を生成し、TaskScheduler に登録する。
@@ -394,7 +394,27 @@
 異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。
 %CAS のコード
 
-%\section{依存関係の解決}
+Gears OS ではこの CAS を行うための Interface を定義している(\coderef{atomicInterface})。
+この Interface では、Data Gear 全てを内包している Data 共用体のポインタの値を更新する CAS を定義して
+いる(\coderef{atomicInterface} 6行目)。
+
+\lstinputlisting[caption=AtomicInterface, label=code:atomicInterface]{./src/atomicInterface.h}
+
+AtomicInterface での CAS の実際の実装を \coderef{atomicImpl} に示す。
+実際の実装では \_\_sync\_bool\_compare\_and\_swap 関数を呼び出すことで CAS を行う(\coderef{atomicImpl} 2行目)。
+この関数は第一引数に渡されたアドレスに対して第二引数の値から第三引数の値ヘ CAS を行う。
+CAS に成功した場合、true を返し、失敗した場合は false を返す。
+\coderef{atomicImpl} では CAS に成功した場合と失敗した場合それぞれに対応した Code Gear へ継続する。
+
+\lstinputlisting[caption=CAS の実装, label=code:atomicImpl]{./src/atomicImpl.cbc}
+
+SynchronizedQueue の Data Gear の定義を \coderef{synchronizedQueue} に示す。
+SynchronizedQueue はデータのリストの先頭と、終端のポインタを持っている。
+Queue を操作する際はこのポインタに対して CAS をすることでデータの挿入と取り出しを行う。
+
+\lstinputlisting[caption=SynchronizedQueue の定義, label=code:synchronizedQueue]{./src/synchronizedQueue.h}
+
+%\section{依存関係の解決} 
 
 \section{並列構文}
 Gears OS の並列構文は par goto文で用意されている。
diff -r 6076ec5e33de -r 48561c7a2036 Paper/src/atomicImpl.cbc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/atomicImpl.cbc	Fri Apr 13 17:15:24 2018 +0900
@@ -0,0 +1,6 @@
+__code checkAndSetAtomicReference(struct AtomicReference* atomic, union Data** ptr, union Data* oldData, union Data* newData, __code next(...), __code fail(...)) {
+    if (__sync_bool_compare_and_swap(ptr, oldData, newData)) {
+        goto next(...);
+    }
+    goto fail(...);
+}
diff -r 6076ec5e33de -r 48561c7a2036 Paper/src/atomicInterface.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/atomicInterface.h	Fri Apr 13 17:15:24 2018 +0900
@@ -0,0 +1,9 @@
+typedef struct Atomic<Impl>{
+    union Data* atomic;
+    union Data** ptr;
+    union Data* oldData;
+    union Data* newData;
+    __code checkAndSet(Impl* atomic, union Data** ptr, union Data* oldData, union Data* newData, __code next(...), __code fail(...));
+    __code next(...);
+    __code fail(...);
+} Atomic;
diff -r 6076ec5e33de -r 48561c7a2036 Paper/src/synchronizedQueue.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/src/synchronizedQueue.h	Fri Apr 13 17:15:24 2018 +0900
@@ -0,0 +1,11 @@
+struct SynchronizedQueue {
+    struct Element* top;
+    struct Element* last;
+    struct Atomic* atomic;
+};
+
+// Singly Linked List element
+struct Element {
+    union Data* top;
+    struct Element* next;
+};