# HG changeset patch # User Shohei KOKUBO # Date 1432025242 -32400 # Node ID 3214ac1f9e8d6743a9000bba0e4cccc04217ff72 # Parent 348148d8fdb194e8dc33dc98d25d5f6bce146d96# Parent 2e7e66ccb3db74d2ab8849cd3e8b2cb0c264cdf1 merge diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/CMakeLists.txt --- a/src/synchronizedQueue/CMakeLists.txt Tue May 19 17:46:41 2015 +0900 +++ b/src/synchronizedQueue/CMakeLists.txt Tue May 19 17:47:22 2015 +0900 @@ -9,3 +9,8 @@ synchronizedQueueForCas.c synchronizedQueueContext.c ) + +add_executable(synchronizedQueueForSem + synchronizedQueueForSem.c + synchronizedQueueForSemContext.c +) diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/synchronizedQueue.c --- a/src/synchronizedQueue/synchronizedQueue.c Tue May 19 17:46:41 2015 +0900 +++ b/src/synchronizedQueue/synchronizedQueue.c Tue May 19 17:47:22 2015 +0900 @@ -124,7 +124,7 @@ if (context->data[Queue]->queue.count == 0) { printf("queue is empty\n"); pthread_mutex_unlock(&context->data[Queue]->queue.mutex); - goto meta(context, Receiver); + goto (context->code[next])(context); } else { printf("Get %d\n\n", context->data[Queue]->queue.first->element.value); context->data[Queue]->queue.first = (context->data[Queue]->queue.first->element.next) ? context->data[Queue]->queue.first->element.next : 0; diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/synchronizedQueueContext.h --- a/src/synchronizedQueue/synchronizedQueueContext.h Tue May 19 17:46:41 2015 +0900 +++ b/src/synchronizedQueue/synchronizedQueueContext.h Tue May 19 17:47:22 2015 +0900 @@ -1,4 +1,4 @@ -/* Context definition for list example */ +/* Context definition for synchronized queue example */ #include #define ALLOCATE_SIZE 1000 diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/synchronizedQueueForCas.c --- a/src/synchronizedQueue/synchronizedQueueForCas.c Tue May 19 17:46:41 2015 +0900 +++ b/src/synchronizedQueue/synchronizedQueueForCas.c Tue May 19 17:47:22 2015 +0900 @@ -67,10 +67,6 @@ last_ds = context->data[Queue]->queue.last; new_ds = context->data[context->dataNum]; new_ds->element.next = 0; - - int old_count, new_count; - old_count = context->data[Queue]->queue.count; - new_count = old_count + 1; if(__sync_bool_compare_and_swap(&context->data[Queue]->queue.last, last_ds, new_ds)) { if(context->data[Queue]->queue.first) { last_ds->element.next = new_ds; @@ -119,9 +115,6 @@ union Data *first_ds, *new_ds; first_ds = context->data[Queue]->queue.first; new_ds = first_ds? first_ds->element.next : 0; - int old_count, new_count; - old_count = context->data[Queue]->queue.count; - new_count = old_count == 0 ? 0 : old_count - 1; if(__sync_bool_compare_and_swap(&context->data[Queue]->queue.first, first_ds, new_ds)) { if (first_ds == new_ds) { printf("queue is empty\n"); @@ -181,5 +174,4 @@ pthread_join(thread2, NULL); pthread_join(thread3, NULL); pthread_join(thread4, NULL); - printf("Count %d\n\n", context1->data[Queue]->queue.count); } diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/synchronizedQueueForSem.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/synchronizedQueue/synchronizedQueueForSem.c Tue May 19 17:47:22 2015 +0900 @@ -0,0 +1,194 @@ +#include +#include + +#include "synchronizedQueueForSemContext.h" + +#include "allocate.h" +#include "origin_cs.h" + +#ifdef CLANG +#define _CbC_retrun __return +#define _CbC_environment __environment +#endif + +#define NUM 10 + +extern __code initSynchronizedQueueContext(struct Context* context); + +//__code code1(struct Context* context) { +// context->data[Allocate]->allocate.size = sizeof(struct Element); +// context->data[Allocate]->allocate.next = Code2; +// goto meta(context, Allocator); +//} + +__code meta(struct Context* context, enum Code next) { + goto (context->code[next])(context); +} + +//__code code2(struct Context* context) { +// context->data[Allocate]->allocate.after_put = Code3; +// context->data[context->dataNum] -> element.value = 1024; +// goto meta(context, Sender); +//} + +__code code1(struct Context* context) { + context->data[Allocate]->allocate.size = sizeof(long); + context->data[Allocate]->allocate.next = Code2; + goto meta(context, Allocator); +} + +__code code2(struct Context* context) { + context->data[Counter] -> count = 0; + goto meta(context, Code3); +} + +__code code3(struct Context* context) { + long loop = context->data[Counter]->count; + if(loop == NUM) { + goto meta(context, ThreadExit); + } + context->data[Allocate]->allocate.size = sizeof(struct Element); + context->data[Allocate]->allocate.next = Code4; + goto meta(context, Allocator); +} + +__code code4(struct Context* context) { + context->data[Allocate]->allocate.after_put = Code3; + context->data[context->dataNum] -> element.value = context->data[Counter]->count++; + goto meta(context, Sender); +} + +__code meta_sender(struct Context* context, enum Code next) { + goto (context->code[next])(context); +} + +__code sender(struct Context* context) { + goto meta_sender(context, Put); +} + +__code meta_put(struct Context* context, enum Code next) { + // sem_p + pthread_mutex_lock(&context->data[Queue]->queue.queue_remain->mutex); + while(context->data[Queue]->queue.queue_remain->value == 0) { + pthread_cond_wait(&context->data[Queue]->queue.queue_remain->cond, &context->data[Queue]->queue.queue_remain->mutex); + } + context->data[Queue]->queue.queue_remain->value--; + pthread_mutex_unlock(&context->data[Queue]->queue.queue_remain->mutex); + + // put + if(context->data[Queue]->queue.first) { + context->data[Queue]->queue.last->element.next = context->data[context->dataNum]; + context->data[Queue]->queue.last = context->data[Queue]->queue.last->element.next; + } else { + context->data[Queue]->queue.first = context->data[context->dataNum]; + context->data[Queue]->queue.last = context->data[Queue]->queue.first; + } + context->data[Queue]->queue.last->element.next = 0; + printf("Put %d\n\n", context->data[Queue]->queue.last->element.value); + + // sem_v + pthread_mutex_lock(&context->data[Queue]->queue.queue_count->mutex); + context->data[Queue]->queue.queue_count->value++; + pthread_cond_signal(&context->data[Queue]->queue.queue_count->cond); + pthread_mutex_unlock(&context->data[Queue]->queue.queue_count->mutex); + + goto (context->code[next])(context); +} + +__code put(struct Context* context) { + goto meta_put(context, context->data[Allocate]->allocate.after_put); +} + +__code code5(struct Context* context) { + context->data[Allocate]->allocate.size = sizeof(long); + context->data[Allocate]->allocate.next = Code6; + goto meta(context, Allocator); +} + +__code code6(struct Context* context) { + context->data[Counter] -> count = 0; + goto meta(context, Code7); +} + +__code code7(struct Context* context) { + long loop = context->data[Counter]->count; + if(loop == NUM) { + goto meta(context, ThreadExit); + } + context->data[Counter]->count++; + context->data[Allocate]->allocate.after_get = Code7; + goto meta(context, Receiver); +} + +__code meta_receiver(struct Context* context, enum Code next) { + goto (context->code[next])(context); +} + +__code receiver(struct Context* context) { + goto meta_receiver(context, Get); +} + +__code meta_get(struct Context* context, enum Code next) { + // sem_p + pthread_mutex_lock(&context->data[Queue]->queue.queue_count->mutex); + while(context->data[Queue]->queue.queue_count->value == 0) { + pthread_cond_wait(&context->data[Queue]->queue.queue_count->cond, &context->data[Queue]->queue.queue_count->mutex); + } + context->data[Queue]->queue.queue_count->value--; + pthread_mutex_unlock(&context->data[Queue]->queue.queue_count->mutex); + + printf("Get %d\n\n", context->data[Queue]->queue.first->element.value); + context->data[Queue]->queue.first = (context->data[Queue]->queue.first->element.next) ? context->data[Queue]->queue.first->element.next : 0; + + // sem_v + pthread_mutex_lock(&context->data[Queue]->queue.queue_remain->mutex); + context->data[Queue]->queue.queue_remain->value++; + pthread_cond_signal(&context->data[Queue]->queue.queue_remain->cond); + pthread_mutex_unlock(&context->data[Queue]->queue.queue_remain->mutex); + + goto (context->code[next])(context); +} + +__code get(struct Context* context) { + goto meta_get(context, context->data[Allocate]->allocate.after_get); +} + +__code thread_exit(struct Context* context) { + free(context->code); + free(context->data); + free(context->heap_start); + pthread_exit(0); +} + +void* thread_func(void* context) { + goto start_code((struct Context*)context, Code1); + return 0; +} + +void* thread_func2(void* context) { + goto start_code((struct Context*)context, Code5); + return 0; +} + +int main() { + struct Context* context1 = (struct Context*)malloc(sizeof(struct Context)); + initSynchronizedQueueContext(context1); + struct Context* context2 = (struct Context*)malloc(sizeof(struct Context)); + initSynchronizedQueueContext(context2); + struct Context* context3 = (struct Context*)malloc(sizeof(struct Context)); + initSynchronizedQueueContext(context3); + struct Context* context4 = (struct Context*)malloc(sizeof(struct Context)); + initSynchronizedQueueContext(context4); + context2->data[Queue] = context1->data[Queue]; + context3->data[Queue] = context1->data[Queue]; + context4->data[Queue] = context1->data[Queue]; + pthread_t thread1, thread2, thread3, thread4; + pthread_create(&thread1, NULL, thread_func, (void *)context1); + pthread_create(&thread2, NULL, thread_func, (void *)context2); + pthread_create(&thread3, NULL, thread_func2, (void *)context3); + pthread_create(&thread4, NULL, thread_func2, (void *)context4); + pthread_join(thread1, NULL); + pthread_join(thread2, NULL); + pthread_join(thread3, NULL); + pthread_join(thread4, NULL); +} diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/synchronizedQueueForSemContext.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/synchronizedQueue/synchronizedQueueForSemContext.c Tue May 19 17:47:22 2015 +0900 @@ -0,0 +1,63 @@ +#include + +#include "synchronizedQueueForSemContext.h" + +extern __code code1(struct Context*); +extern __code code2(struct Context*); +extern __code code3(struct Context*); +extern __code code4(struct Context*); +extern __code code5(struct Context*); +extern __code code6(struct Context*); +extern __code code7(struct Context*); +extern __code meta(struct Context*); +extern __code allocate(struct Context*); +extern __code sender(struct Context*); +extern __code put(struct Context*); +extern __code receiver(struct Context*); +extern __code get(struct Context*); +extern __code exit_code(struct Context*); +extern __code thread_exit(struct Context*); + +__code initSynchronizedQueueContext(struct Context* context) { + context->dataSize = sizeof(union Data)*ALLOCATE_SIZE; + context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); + context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE); + context->heap_start = malloc(context->dataSize); + + context->codeNum = Exit; + context->code[Code1] = code1; + context->code[Code2] = code2; + context->code[Code3] = code3; + context->code[Code4] = code4; + context->code[Code5] = code5; + context->code[Code6] = code6; + context->code[Code7] = code7; + context->code[Allocator] = allocate; + context->code[Sender] = sender; + context->code[Put] = put; + context->code[Receiver] = receiver; + context->code[Get] = get; + context->code[Exit] = exit_code; + context->code[ThreadExit] = thread_exit; + + context->heap = context->heap_start; + + context->data[Allocate] = context->heap; + context->heap += sizeof(struct Allocate); + + context->data[Queue] = context->heap; + context->heap += sizeof(struct Queue); + context->data[Queue]->queue.first = 0; + context->data[Queue]->queue.queue_remain = malloc(sizeof(struct Sem)); + pthread_mutex_init(&context->data[Queue]->queue.queue_remain->mutex, NULL); + pthread_cond_init(&context->data[Queue]->queue.queue_remain->cond, NULL); + context->data[Queue]->queue.queue_remain->value = 10; + + context->data[Queue]->queue.queue_count = malloc(sizeof(struct Sem)); + pthread_mutex_init(&context->data[Queue]->queue.queue_count->mutex, NULL); + pthread_cond_init(&context->data[Queue]->queue.queue_count->cond, NULL); + context->data[Queue]->queue.queue_count->value = 0; + + + context->dataNum = Queue; +} diff -r 348148d8fdb1 -r 3214ac1f9e8d src/synchronizedQueue/synchronizedQueueForSemContext.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/synchronizedQueue/synchronizedQueueForSemContext.h Tue May 19 17:47:22 2015 +0900 @@ -0,0 +1,63 @@ +/* Context definition for synchronized queue for sem example */ + +#include +#define ALLOCATE_SIZE 1000 + +enum Code { + Code1, + Code2, + Code3, + Code4, + Code5, + Code6, + Code7, + Allocator, + Sender, + Put, + Receiver, + Get, + Exit, + ThreadExit, +}; + +enum UniqueData { + Allocate, + Queue, + Counter, +}; + +struct Context { + int codeNum; + __code (**code) (struct Context *); + void* heap_start; + void* heap; + long dataSize; + int dataNum; + union Data* head; + union Data** data; +}; + + +union Data { + long count; + struct Queue { + union Data* first; + union Data* last; + struct Sem { + volatile int value; + pthread_mutex_t mutex; + pthread_cond_t cond; + + } *queue_remain, *queue_count; + } queue; + struct Element { + int value; + union Data* next; + } element; + struct Allocate { + long size; + enum Code next; + enum Code after_put; + enum Code after_get; + } allocate; +};