Mercurial > hg > Papers > 2018 > parusu-master

Binary file paper/fig/putSynchronizedQueue1.graffle has changed
Binary file paper/fig/putSynchronizedQueue1.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/fig/putSynchronizedQueue1.xbb	Wed Jan 24 02:43:02 2018 +0900
@@ -0,0 +1,8 @@
+%%Title: fig/putSynchronizedQueue1.pdf
+%%Creator: extractbb 20170318
+%%BoundingBox: 0 0 809 301
+%%HiResBoundingBox: 0.000000 0.000000 809.000000 301.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Jan 23 18:39:37 2018
+
Binary file paper/fig/putSynchronizedQueue2.graffle has changed
Binary file paper/fig/putSynchronizedQueue2.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/fig/putSynchronizedQueue2.xbb	Wed Jan 24 02:43:02 2018 +0900
@@ -0,0 +1,8 @@
+%%Title: fig/putSynchronizedQueue2.pdf
+%%Creator: extractbb 20170318
+%%BoundingBox: 0 0 870 391
+%%HiResBoundingBox: 0.000000 0.000000 870.000000 391.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Wed Jan 24 02:38:57 2018
+
Binary file paper/fig/takeSynchronizedQueue1.graffle has changed
Binary file paper/fig/takeSynchronizedQueue1.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/fig/takeSynchronizedQueue1.xbb	Wed Jan 24 02:43:02 2018 +0900
@@ -0,0 +1,8 @@
+%%Title: fig/takeSynchronizedQueue1.pdf
+%%Creator: extractbb 20170318
+%%BoundingBox: 0 0 571 202
+%%HiResBoundingBox: 0.000000 0.000000 571.000000 202.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Jan 23 17:23:41 2018
+
Binary file paper/fig/takeSynchronizedQueue2.graffle has changed
Binary file paper/fig/takeSynchronizedQueue2.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/fig/takeSynchronizedQueue2.xbb	Wed Jan 24 02:43:02 2018 +0900
@@ -0,0 +1,8 @@
+%%Title: fig/takeSynchronizedQueue2.pdf
+%%Creator: extractbb 20170318
+%%BoundingBox: 0 0 660 202
+%%HiResBoundingBox: 0.000000 0.000000 660.000000 202.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Tue Jan 23 17:23:41 2018
+
Binary file paper/master_paper.pdf has changed
--- a/paper/parallelism_gears.tex	Tue Jan 23 17:22:30 2018 +0900
+++ b/paper/parallelism_gears.tex	Wed Jan 24 02:43:02 2018 +0900
@@ -60,7 +60,9 @@
 Worker の Queue は TaskManager を経由して Task を送信するスレッドと Task を取得する Worker 自身のスレッドで扱われる。
 そのため SynchronizeQueue はマルチスレッドでもデータの一貫性を保証する Queue を実装する必要がある。

-Gears OS では マルチスレッドでもデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue\cite{queue} を実装している。
+データの一貫性を保証する解決例としての1つとしてロックを使った解決方法がある。
+しかし、ロックを行ってデータを更新した場合、同じ Queue に対して操作を行う際に待ち合わせが発生し、全体の並列度が下がってしまう。
+そこで、Gears OS ではデータの一貫性を保証するために CAS(Check and Set、Compare and Swap) を利用した Queue\cite{queue} を実装している。
 CAS は値の比較、更新をアトミックに行う命令である。
 CAS を使う際は更新前の値と更新後の値を渡し、渡された更新前の値を実際に保存されているメモリ番地の値と比較し、同じならデータ競合がないため、データの更新に成功する。
 異なる場合は他に書き込みがあったとみなされ、値の更新に失敗する。
@@ -79,17 +81,62 @@
 \lstinputlisting[caption=CAS の実装, label=code:atomicImpl]{./src/atomicImpl.cbc}

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

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

-\figref{takeSynchornizedQueue} はデータの取り出し(dequeue) をする際のポインタの動きである。
-データを取り出す際はList の先頭を次の要素のポインタへ CAS することででデータを取得する。
-この Queue では先頭に挿しているポインタはダミー扱いとする。 その為、実際に取り出される値は CAS に成功した後の先頭の値となる。
+\figref{takeSynchronizedQueue1} は要素の取り出し(dequeue) を行った流れを示している。
+データを取り出す際はリストの先頭を次の要素へ CAS することででデータを取得する。
+この Queue では先頭に挿している要素はダミー扱いとする。
+その為、実際に取り出される値は CAS に成功した後の先頭の値となる。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[scale=0.6]{./fig/takeSynchronizedQueue1.pdf}
+    \end{center}
+    \caption{SynchronizedQueueによる要素の取り出し}
+    \label{fig:takeSynchronizedQueue1}
+\end{figure}
+
+\figref{putSynchronizedQueue1} は要素の挿入(inqueue) を行った流れを示している。
+データを挿入する際は2度の CAS を行う。
+まず、末尾の要素の次の要素を新しい要素に CAS を行う。
+その後、末尾の要素が差している要素を挿入に成功した新しい要素に CAS を行う。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[scale=0.6]{./fig/putSynchronizedQueue1.pdf}
+    \end{center}
+    \caption{SynchronizedQueueによる要素の挿入}
+    \label{fig:putSynchronizedQueue1}
+\end{figure}

-\lstinputlisting[caption=SynchronizedQueue の定義, label=code:synchronizedQueue]{./src/synchronizedQueue.h}
+しかし、データの挿入する際は2度の CAS の間に他のスレッドの操作が入り、Queueの構造が破綻する場合がある。
+例えば\figref{putSynchronizedQueue2} に示すように、あるスレッドが末尾を更新した際に、他のスレッドが更新処理を行うとQueue が破綻する。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[scale=0.6]{./fig/putSynchronizedQueue2.pdf}
+    \end{center}
+    \caption{SynchronizedQueue によるデータの挿入時の破綻例}
+    \label{fig:putSynchronizedQueue2}
+\end{figure}
+
+\figref{putSynchronizedQueue2}は2つのスレッドが以下の順番で処理を行っている。

+\begin{enumerate}
+    \item threadA: 末尾の要素(data3)の次の要素を新しい要素(data4)に CAS を実行する
+    \item threadB: threadA での末尾更新をする前に末尾の要素(data3)の次の要素を新しい要素(data5)にCASを実行する。
+          この時の末尾が指す要素は、threadA が要素挿入を行う前の状態と同じなため、この操作を行うとリストが破綻する。
+    \item threadA: 末尾の要素(data3)を挿入に成功した要素(data4)に CAS を行う。
+    \item threadB: 末尾の要素(data3)を挿入に成功した要素(data5)に CAS を行う。
+          threadB が挿入の操作を行ったときの末尾はthreadA が末尾更新する前の末尾要素なので、このCAS は失敗する。
+\end{enumerate}
+
+この破綻は末尾の要素が必ず末尾を示していると仮定しているためである。
+しかし、データ挿入の際は2度の CAS の間に他のスレッドが割り込む場合がある。
+そこで、末尾の要素は必ず末尾を示す
 \section{依存関係の解決}
 \section{並列処理の記述}
 \section{Iterator}
--- a/paper/src/singleLinkedQueue.cbc	Tue Jan 23 17:22:30 2018 +0900
+++ b/paper/src/singleLinkedQueue.cbc	Wed Jan 24 02:43:02 2018 +0900
@@ -27,22 +27,4 @@
     goto next(...);
 }

-__code takeSingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(union Data* data, ...)) {
-    struct Element* top = queue->top;
-    struct Element* nextElement = top->next;
-    if (nextElement == NULL) {
-        data = NULL;
-    } else {
-        queue->top = nextElement;
-        data = nextElement->data;
-    }
-    goto next(data, ...);
-}
-
-__code isEmptySingleLinkedQueue(struct SingleLinkedQueue* queue, __code next(...), __code whenEmpty(...)) {
-    struct Element* nextElement = top->next;
-    if (nextElement == NULL)
-        goto whenEmpty(...);
-    else
-        goto next(...);
-}
+.....