Mercurial > hg > Papers > 2018 > parusu-master

Binary file paper/master_paper.pdf has changed
--- a/paper/parallelism_gears.tex	Wed Jan 24 03:27:17 2018 +0900
+++ b/paper/parallelism_gears.tex	Wed Jan 24 03:52:00 2018 +0900
@@ -137,13 +137,13 @@
 この破綻は末尾の要素が必ず末尾を示していると仮定しているためである。
 しかし、データ挿入の際は2度の CAS の間に他のスレッドが割り込む場合がある。
 そこで、末尾の要素は必ずしも末尾を示さないと仮定して要素の取出しと挿入の処理を記述する。
-\refcode{takeSynchronizedQueue} が要素の挿入の処理の一部である。
-末尾の要素が末尾を示さない場合の処理は\refcode{takeSynchronizedQueue} の 45-48 行目に記述している。
+\coderef{putSynchronizedQueue} が要素の挿入の処理の一部である。
+末尾の要素が末尾を示さない場合の処理は\coderef{putSynchronizedQueue} の 13-16 行目に記述している。
 変数 nextElement は 末尾要素の次の要素を示しており、NULL ではない場合は末尾を差していない状態ということになる。
 その場合は、末尾の要素をnextElement に CAS を行う。
 この処理は要素の取り出しを行う際にも行われる。

-\lstinputlisting[caption=SynchronizedQueue による要素の挿入, label=code:takeSynchronizedQueue]{./src/takeSynchronizedQueue.cbc}
+\lstinputlisting[caption=SynchronizedQueue による要素の挿入, label=code:putSynchronizedQueue]{./src/putSynchronizedQueue.cbc}

 \section{依存関係の解決}
 \section{並列処理の記述}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/putSynchronizedQueue.cbc	Wed Jan 24 03:52:00 2018 +0900
@@ -0,0 +1,17 @@
+__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 { // wrong last element
+        struct Atomic* atomic = queue->atomic;
+        goto atomic->checkAndSet(&queue->last, last, nextElement, putSynchronizedQueue, putSynchronizedQueue);
+    }
+}
--- a/paper/src/takeSynchronizedQueue.cbc	Wed Jan 24 03:27:17 2018 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,97 +0,0 @@
-
-#include "../context.h"
-#interface "Queue.h"
-#interface "Atomic.h"
-
-#include <stdio.h>
-
-/*
- * Non-blocking queue of Paper: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms(https://www.research.ibm.com/people/m/michael/podc-1996.pdf).
- */
-
-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 clearSynchronizedQueue(struct SynchronizedQueue* queue, __code next(...)) {
-    struct Element* top = queue->top;
-    struct Atomic* atomic = queue->atomic;
-    goto atomic->checkAndSet(&queue->top, top, NULL, next(...), clearSynchronizedQueue);
-}
-
-__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 { // wrong last element
-        struct Atomic* atomic = queue->atomic;
-        goto atomic->checkAndSet(&queue->last, last, nextElement, putSynchronizedQueue, putSynchronizedQueue);
-    }
-}
-
-__code takeSynchronizedQueue(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) {
-    struct Element* top = queue->top;
-    struct Element* last = queue->last;
-    struct Element* nextElement = top->next;
-    if (top != queue->top) {
-        goto takeSynchronizedQueue();
-    }
-    if (top == last) {
-        if (nextElement != NULL) {
-            struct Atomic* atomic = queue->atomic;
-            goto atomic->checkAndSet(&queue->last, last, nextElement, takeSynchronizedQueue, takeSynchronizedQueue);
-        }
-    } else {
-        struct Atomic* atomic = queue->atomic;
-        goto atomic->checkAndSet(&queue->top, top, nextElement, takeSynchronizedQueue1, takeSynchronizedQueue);
-    }
-    goto takeSynchronizedQueue();
-}
-
-__code takeSynchronizedQueue1(struct SynchronizedQueue* queue, __code next(union Data* data, ...), struct Element* nextElement) {
-    data = nextElement->data;
-    goto next(data, ...);
-}
-
-__code takeSynchronizedQueue1_stub(struct Context* context) {
-	SynchronizedQueue* queue = (SynchronizedQueue*)GearImpl(context, Queue, queue);
-	enum Code next = Gearef(context, Queue)->next;
-	Data** O_data = &Gearef(context, Queue)->data;
-	goto takeSynchronizedQueue1(context,
-                                queue,
-                                next,
-                                O_data,
-                                (struct Element*)Gearef(context, Atomic)->newData);
-}
-
-__code isEmptySynchronizedQueue(struct SynchronizedQueue* queue, __code next(...), __code whenEmpty(...)) {
-    struct Element* top = queue->top;
-    struct Element* last = queue->last;
-    struct Element* nextElement = top->next;
-    if (top != queue->top) {
-        goto isEmptySynchronizedQueue();
-    }
-    if (top == last && nextElement == NULL) {
-        goto whenEmpty(...);
-    }
-    goto next(...);
-}