From 90358a35a87125c84815fd1e82a30cb17d94d918 Mon Sep 17 00:00:00 2001 From: Stefan Zabka Date: Fri, 10 Jul 2020 14:24:46 +0200 Subject: Useless commit --- 04_exercise/main.c | 4 ++-- 04_exercise/quicksort.c | 26 +++++++++++++++++++++----- 04_exercise/slotmap.c | 16 +++++++++++----- 04_exercise/slotmap.h | 6 +++--- 04_exercise/threadpool.c | 8 ++++++-- 5 files changed, 43 insertions(+), 17 deletions(-) diff --git a/04_exercise/main.c b/04_exercise/main.c index 8c7b8db..8a57abb 100644 --- a/04_exercise/main.c +++ b/04_exercise/main.c @@ -8,7 +8,7 @@ static TASK(long, fib, long) long fib(long n) { if (n <= 1) return n; - + // fprintf(stderr, "Thread %ld: fib being called with %d \n", pthread_self(), n); fib_fut *a = fibAsync((fib_fut[]){fibFuture(n - 1)}); fib_fut *b = fibAsync((fib_fut[]){fibFuture(n - 2)}); @@ -20,7 +20,7 @@ int main() { if (tpInit(4) != 0) perror("Thread Pool initialization failed"), exit(-1); atexit(&tpRelease); - for (long i = 0; i <= 20; ++i) + for (long i = 25; i <= 50; ++i) printf("fib(%2li) = %li\n", i, fib(i)); return 0; diff --git a/04_exercise/quicksort.c b/04_exercise/quicksort.c index ade513b..7398282 100644 --- a/04_exercise/quicksort.c +++ b/04_exercise/quicksort.c @@ -4,17 +4,33 @@ #include #include #include +#include static size_t partition(int v[], size_t len); /* TODO: quicksort-Implementation parallelisieren */ -static void quicksort(int list[], size_t len) { - if (len <= 1) return; +typedef struct quicksort_param { + int *list; + size_t len; +} quicksort_param; + +TASK(int, quicksort, quicksort_param) + +int quicksort(quicksort_param param) { + int *list = param.list; + size_t len = param.len; + fprintf(stderr, "Thread %ld: quicksort being called with list %p and len %ld \n", pthread_self(), (void *) list, len); + if (len <= 1) return 0; size_t mid = partition(list, len); - quicksort(list, mid); - quicksort(list + mid + 1, len - mid - 1); + quicksort_fut fut1_t = quicksortFuture((quicksort_param){list, mid}); + quicksort_fut fut2_t = quicksortFuture((quicksort_param){list + mid + 1, len - mid - 1}); + quicksort_fut *fut1 = quicksortAsync(& fut1_t); + quicksort_fut *fut2 = quicksortAsync(& fut2_t); + quicksortAwait(fut1); + quicksortAwait(fut2); + return 0; } size_t partition(int v[], size_t len) { @@ -108,7 +124,7 @@ int main(int argc, const char *argv[]) { /* sort it and print the sorted list if it's not too long */ struct timespec start, end, dt; clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start); - quicksort(list, list_len); + quicksort((quicksort_param){list, list_len}); clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end); dt = time_diff(start, end); printf("---- Sortiert: %i ----\n", list_is_sorted(list, list_len)); diff --git a/04_exercise/slotmap.c b/04_exercise/slotmap.c index 57c4ef5..3c5a240 100644 --- a/04_exercise/slotmap.c +++ b/04_exercise/slotmap.c @@ -8,35 +8,41 @@ smHeader smInit(smEntry * slab, size_t size) { for (int i = 0; i < size; ++i) { slab[i].value = (intptr_t)NULL; } - return (smHeader){.slab = slab, .size=size}; + return (smHeader){.slab = slab, .size=size, .count = 0}; } -int smInsert(smHeader const * header, void * value) { +int smInsert(smHeader * header, void * value) { for (size_t i = 0; i< header->size; ++i ) { intptr_t ptr = atomic_load(&header->slab[i].value); if((void *)ptr == NULL) { intptr_t expected = (intptr_t) NULL; if(atomic_compare_exchange_strong(&header->slab[i].value, &expected, (intptr_t) value)){ + atomic_fetch_add(&header->count, 1); return 0; } } } return -1; } -void smDelete(smEntry * node) { +void smDelete(smHeader * header, smEntry * node) { intptr_t oldval = atomic_exchange(&node->value, (intptr_t)(NULL)); if((void *) oldval == NULL) { fprintf(stderr, "A Node has been double deleted"); } + atomic_fetch_sub(&header->count, 1); } -void smDeleteValue(smHeader const * header, void * value){ +void smDeleteValue(smHeader * header, void * value){ for (size_t i = 0; i< header->size; ++i ) { intptr_t ptr = atomic_load(&header->slab[i].value); if((void *)ptr == value) { - smDelete(&header->slab[i]); + smDelete(header, &header->slab[i]); } } } smEntry *smFindEntry(smHeader const * header, SearchFunction func){ + int count = atomic_load(&header->count); + if (count == 0) { + return NULL; + } for (size_t i = 0; i< header->size; ++i ) { void * value = (void *) atomic_load(&header->slab[i].value); diff --git a/04_exercise/slotmap.h b/04_exercise/slotmap.h index d4044d4..aa1a47f 100644 --- a/04_exercise/slotmap.h +++ b/04_exercise/slotmap.h @@ -16,14 +16,14 @@ typedef struct smNode { typedef struct smHeader { smEntry *slab; size_t size; + atomic_int count; } smHeader; typedef bool (*SearchFunction)(void const *); smHeader smInit(smEntry * slab, size_t size); -int smInsert(smHeader const * header, void * value); -void smDelete(smEntry * node); -void smDeleteValue(smHeader const * header, void * value); +int smInsert(smHeader * header, void * value); +void smDeleteValue(smHeader * header, void * value); /** * Returns a node whose value is accepted by the SearchFunction * @param header The header of the slotmap to be searched diff --git a/04_exercise/threadpool.c b/04_exercise/threadpool.c index d40b1da..f046235 100644 --- a/04_exercise/threadpool.c +++ b/04_exercise/threadpool.c @@ -54,8 +54,11 @@ bool tryDoingWork() { if (entry == NULL) { return false; } - Future * fut = (Future *) entry->value; + Future * fut = (Future *)atomic_load(&entry->value); // This will just return if some other thread was first + if(fut == NULL) { + return false; + } return tryRunningFuture(fut); } /** @brief worker function running in the threadpool @@ -66,7 +69,7 @@ _Noreturn void *poolWorkerFunc(void *v_index) { unsigned int backoffTime = 1; while (true) { if (!tryDoingWork()) { - backoffTime = 2 * backoffTime; + // backoffTime = 2 * backoffTime; fprintf(stderr, "Thread %zu: Found no work sleeping for %d seconds \n", index, backoffTime); sleep(backoffTime); @@ -114,6 +117,7 @@ void tpAsync(Future *future) { while (smInsert(&threadPool.header, (void *)future) < 0) { tryDoingWork(); } + sched_yield(); } void tpAwait(Future *future) { -- cgit v1.2.3-54-g00ecf