/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/Makefile |
---|
0,0 → 1,22 |
# |
# Treat warnings as errors. This seems to be the only way to |
# convince some students of the importance of ensuring that |
# their code compiles without warnings before starting to debug. |
# |
# Do not change this line. We will not use your copy of the Makefile |
# we will use *this* Makefile to run check.py when grading. |
# |
#CFLAGS=-Wall -O3 -Werror |
CFLAGS=-Wall -O1 -g -Werror |
LDLIBS=-lpthread |
# Use make's default rules |
all: threadpool_test quicksort |
threadpool_test: threadpool_test.o threadpool.o list.o |
quicksort: quicksort.o threadpool.o list.o |
clean: |
rm -f *.o threadpool_test quicksort |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/Quicksort Results |
---|
0,0 → 1,144 |
Random seed fixed at 42 |
n d Result |
1 1 43.333 |
1 2 43.371 |
1 3 43.415 |
1 4 43.347 |
1 5 43.332 |
1 6 43.376 |
1 7 43.342 |
1 8 43.335 |
1 9 43.492 |
1 10 43.425 |
1 11 43.605 |
1 12 43.688 |
1 13 44.008 |
1 14 45.127 |
1 15 49.349 |
1 16 63.771 |
2 1 37.443 |
2 2 37.961 |
2 3 26.687 |
2 4 26.862 |
2 5 26.323 |
2 6 24.899 |
2 7 24.191 |
2 8 24.845 |
2 9 23.996 |
2 10 22.953 |
2 11 23.297 |
2 12 22.297 |
2 13 22.446 |
2 14 22.835 |
2 15 24.472 |
2 16 30.110 |
2 17 51.941 |
4 1 37.582 |
4 2 36.865 |
4 3 25.053 |
4 4 24.860 |
4 5 24.458 |
4 6 19.151 |
4 7 15.196 |
4 8 14.914 |
4 9 13.242 |
4 10 12.653 |
4 11 13.268 |
4 12 12.049 |
4 13 11.934 |
4 14 12.016 |
4 15 12.494 |
4 16 14.625 |
4 17 23.833 |
6 1 37.435 |
6 2 37.121 |
6 3 25.013 |
6 4 24.881 |
6 5 23.774 |
6 6 18.133 |
6 7 12.557 |
6 8 13.941 |
6 9 11.870 |
6 10 10.354 |
6 11 10.104 |
6 12 9.497 |
6 13 9.208 |
6 14 9.537 |
6 15 9.435 |
6 16 10.667 |
6 17 18.836 |
8 1 37.371 |
8 2 36.960 |
8 3 25.094 |
8 4 24.944 |
8 5 24.013 |
8 6 18.084 |
8 7 12.462 |
8 8 12.685 |
8 9 10.481 |
8 10 9.101 |
8 11 8.582 |
8 12 8.530 |
8 13 7.900 |
8 14 8.109 |
8 15 8.155 |
8 16 8.674 |
8 17 18.586 |
12 1 37.552 |
12 2 37.150 |
12 3 25.115 |
12 4 24.963 |
12 5 23.714 |
12 6 18.317 |
12 7 12.542 |
12 8 12.036 |
12 9 10.059 |
12 10 8.842 |
12 11 8.045 |
12 12 7.949 |
12 13 7.367 |
12 14 7.347 |
12 15 7.216 |
12 16 7.784 |
12 17 17.336 |
16 1 37.329 |
16 2 37.183 |
16 3 25.113 |
16 4 25.043 |
16 5 23.775 |
16 6 17.906 |
16 7 12.461 |
16 8 11.927 |
16 9 9.734 |
16 10 8.661 |
16 11 7.858 |
16 12 7.864 |
16 13 6.997 |
16 14 6.906 |
16 15 6.945 |
16 16 8.310 |
16 17 17.889 |
20 1 37.342 |
20 2 37.200 |
20 3 25.084 |
20 4 24.964 |
20 5 23.730 |
20 6 18.097 |
20 7 12.541 |
20 8 12.029 |
20 9 9.780 |
20 10 8.665 |
20 11 7.762 |
20 12 7.964 |
20 13 6.943 |
20 14 6.996 |
20 15 6.800 |
20 16 8.541 |
20 17 21.731 |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/auto-benchmarker |
---|
0,0 → 1,7 |
#!/bin/bash |
clear |
for i in {1..17} |
do |
./quicksort -q -s 42 -n $1 -d $i 300000000 | grep -A 1 "Using" |
done |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/check.py |
---|
0,0 → 1,165 |
#!/usr/bin/python |
# |
# Check that build and output of threadpool exercise match expected output |
# |
# Written for CS3214 Fall 2009 by G. Back (godmar@gmail.com) |
# Last Updated Fall 2011 |
# |
import re, os, sys, subprocess, operator, signal |
exe = "./threadpool_test" |
helgrind = ["/home/courses/cs3214/valgrind-3.7.0-install/bin/valgrind", "--tool=helgrind"] |
print "Checking correctness of threadpool exercise." |
print "Compiling..." |
if os.system("make clean " + exe): |
raise Exception("make failed, run 'make clean " + exe + "' to see why") |
if not os.access(exe, os.X_OK): |
raise Exception(exe + " did not build") |
print "Ok." |
hex = "[0-9A-Fa-f]{8,16}" |
print "Checking that threadpool.o does not use global variables...", |
allowedsymbols = [ "future_free", "future_get", \ |
"thread_pool_new", "thread_pool_shutdown", |
"thread_pool_submit" ] |
symbols = subprocess.Popen(["nm", "threadpool.o"], stdout=subprocess.PIPE)\ |
.communicate()[0].split("\n") |
for sym in symbols: |
if sym == "" or re.match("\s+U (\S+)", sym): |
continue |
m = re.match(hex + " (\S) (\S+)", sym) |
if not m: |
raise Exception("unexpected line in nm:\n" + sym) |
if m.group(1) == "t": |
continue |
# ignore symbols produced by 'assert()' |
if m.group(1) == "r" and m.group(2).startswith("__PRETTY_FUNCTION__"): |
continue |
if m.group(1) == "T": |
if m.group(2) in allowedsymbols: |
continue |
raise Exception("threadpool.o defines global function '" + m.group(2) |
+ "'\nallowed functions are: " + str(allowedsymbols)); |
raise Exception("threadpool.o must not define any global or " |
+ "static variables, but you define: " + m.group(2)) |
print "Ok." |
# test scenarios (#threads, #tasks) |
threads2tasks = [ (4, 4), (4, 2), (4, 1), \ |
(4, 8), (4, 12), \ |
(2, 2), (2, 4), (2, 8), \ |
(1, 2), (1, 4), (1, 8), \ |
(3, 1), (3, 2), (3, 3), (3, 4), (3, 5) \ |
] |
for (threads, tasks) in threads2tasks: |
print "Testing", threads, "threads and", tasks, "tasks" |
sp = subprocess.Popen([exe, str(threads), str(tasks)], |
stdout=subprocess.PIPE) |
output = sp.communicate()[0] |
if sp.returncode < 0: |
signames = dict((k, v) for v, k in signal.__dict__.iteritems() if v.startswith('SIG')) |
signum = -sp.returncode |
raise Exception("Program terminated with signal %d (%s)\n" % (signum, signames[signum])) |
match = re.match("Main thread: 0x("+hex+")\n(.*)\n"\ |
"Done\.", output, re.MULTILINE | re.DOTALL) |
if not match: |
raise Exception("Output did not match expected format:\n" + output) |
mainthread = match.group(1) |
futures = [] |
for future in match.group(2).split("\n"): |
m = re.match("Future #(\d+) Thread #0x("+hex+") "\ |
"start=(\d+)\.(\d+) end=(\d+)\.(\d+)", future) |
if not m: |
raise Exception("Future did not match expected format:\n" + future) |
futures.append((m.group(1), m.group(2), |
float(m.group(3)) + float(m.group(4)) / 1e6, |
float(m.group(5)) + float(m.group(6)) / 1e6)) |
# print futures |
# consistency checks |
# Futures should be printed in increasing order |
print "Checking correct order of futures...", |
# all is available only in Python 2.5 and up |
def all(l): |
return reduce(lambda x, y: x and y, l, True) |
if not all([ int(futures[i][0]) < int(futures[i+1][0]) \ |
for i in range(len(futures)-1) ]): |
raise Exception("Futures are out of order:\n" + output) |
print "Ok." |
print "Checking that correct number of threads were used...", |
threadsused = len(set([ f[1] for f in futures ] + [ mainthread ])) |
threadsexpected = min(threads, tasks) + 1 |
if threadsexpected != threadsused: |
raise Exception("Thread pool used " + str(threadsused) |
+ " distinct threads including the main thread, should have used " |
+ str(threadsexpected) + ":\n" + output) |
print "Ok." |
# each pair within each 'threads'-sized chunk of tasks |
# should have executed in parallel. |
print "Checking tasks were executed in parallel...", |
def inparallel((start0, end0), (start1, end1)): |
return start1 < end0 and start0 < end1 |
def allpairs(l): |
return reduce(operator.add, [ [(l[i], e) for e in l[i+1:]] \ |
for i in range(len(l)-1) ], []) |
for i in range(0, len(futures), threads): |
for (f1, f2) in allpairs(futures[i:i+threads]): |
if not inparallel(f1[2:4], f2[2:4]): |
raise Exception("Future #" + f1[0] + " and #" + f2[0] |
+ " did not run in parallel:\n" + output) |
print "Ok." |
print "You have met minimum requirements.\n" |
print "Now checking for race conditions using helgrind" |
for (threads, tasks) in threads2tasks: |
cmd = helgrind + [exe, str(threads), str(tasks)] |
print "Running", " ".join(cmd), "...", |
sp = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE) |
stderr = sp.communicate()[1] |
if not re.search("ERROR SUMMARY: 0 errors from 0 contexts", stderr): |
raise Exception("Your program contains race conditions:\n" + stderr) |
print "Ok." |
print "Congratulations, you've passed the race condition checker tests.\n" |
print "Testing whether your thread pool implementation runs Quicksort" |
quicksort = "quicksort" |
if os.system("make clean " + quicksort): |
print "make failed, run 'make clean " + quicksort + "' to see why" |
sys.exit(1) |
sp = subprocess.Popen("./quicksort -q -s 1 1000000".split(" "), stdout=subprocess.PIPE, stderr=subprocess.PIPE) |
stdout = sp.communicate()[0] |
if not re.search("Processed 14 segments of sizes: 6316 19753 62328 62520 68838 82083 104576 141938 152189 256767 325607 450365 592305 674390", stdout): |
print "Quicksort did not produce the expected result." |
else: |
print "Quicksort appears to work, you can now start measuring parallel speedup." |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/id.txt |
---|
0,0 → 1,0 |
group244,klee482 |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/list.c |
---|
0,0 → 1,532 |
#include "list.h" |
#include <assert.h> |
/* Our doubly linked lists have two header elements: the "head" |
just before the first element and the "tail" just after the |
last element. The `prev' link of the front header is null, as |
is the `next' link of the back header. Their other two links |
point toward each other via the interior elements of the list. |
An empty list looks like this: |
+------+ +------+ |
<---| head |<--->| tail |---> |
+------+ +------+ |
A list with two elements in it looks like this: |
+------+ +-------+ +-------+ +------+ |
<---| head |<--->| 1 |<--->| 2 |<--->| tail |<---> |
+------+ +-------+ +-------+ +------+ |
The symmetry of this arrangement eliminates lots of special |
cases in list processing. For example, take a look at |
list_remove(): it takes only two pointer assignments and no |
conditionals. That's a lot simpler than the code would be |
without header elements. |
(Because only one of the pointers in each header element is used, |
we could in fact combine them into a single header element |
without sacrificing this simplicity. But using two separate |
elements allows us to do a little bit of checking on some |
operations, which can be valuable.) */ |
static bool is_sorted (struct list_elem *a, struct list_elem *b, |
list_less_func *less, void *aux); |
/* Returns true if ELEM is a head, false otherwise. */ |
static inline bool |
is_head (struct list_elem *elem) |
{ |
return elem != NULL && elem->prev == NULL && elem->next != NULL; |
} |
/* Returns true if ELEM is an interior element, |
false otherwise. */ |
static inline bool |
is_interior (struct list_elem *elem) |
{ |
return elem != NULL && elem->prev != NULL && elem->next != NULL; |
} |
/* Returns true if ELEM is a tail, false otherwise. */ |
static inline bool |
is_tail (struct list_elem *elem) |
{ |
return elem != NULL && elem->prev != NULL && elem->next == NULL; |
} |
/* Initializes LIST as an empty list. */ |
void |
list_init (struct list *list) |
{ |
assert (list != NULL); |
list->head.prev = NULL; |
list->head.next = &list->tail; |
list->tail.prev = &list->head; |
list->tail.next = NULL; |
} |
/* Returns the beginning of LIST. */ |
struct list_elem * |
list_begin (struct list *list) |
{ |
assert (list != NULL); |
return list->head.next; |
} |
/* Returns the element after ELEM in its list. If ELEM is the |
last element in its list, returns the list tail. Results are |
undefined if ELEM is itself a list tail. */ |
struct list_elem * |
list_next (struct list_elem *elem) |
{ |
assert (is_head (elem) || is_interior (elem)); |
return elem->next; |
} |
/* Returns LIST's tail. |
list_end() is often used in iterating through a list from |
front to back. See the big comment at the top of list.h for |
an example. */ |
struct list_elem * |
list_end (struct list *list) |
{ |
assert (list != NULL); |
return &list->tail; |
} |
/* Returns the LIST's reverse beginning, for iterating through |
LIST in reverse order, from back to front. */ |
struct list_elem * |
list_rbegin (struct list *list) |
{ |
assert (list != NULL); |
return list->tail.prev; |
} |
/* Returns the element before ELEM in its list. If ELEM is the |
first element in its list, returns the list head. Results are |
undefined if ELEM is itself a list head. */ |
struct list_elem * |
list_prev (struct list_elem *elem) |
{ |
assert (is_interior (elem) || is_tail (elem)); |
return elem->prev; |
} |
/* Returns LIST's head. |
list_rend() is often used in iterating through a list in |
reverse order, from back to front. Here's typical usage, |
following the example from the top of list.h: |
for (e = list_rbegin (&foo_list); e != list_rend (&foo_list); |
e = list_prev (e)) |
{ |
struct foo *f = list_entry (e, struct foo, elem); |
...do something with f... |
} |
*/ |
struct list_elem * |
list_rend (struct list *list) |
{ |
assert (list != NULL); |
return &list->head; |
} |
/* Return's LIST's head. |
list_head() can be used for an alternate style of iterating |
through a list, e.g.: |
e = list_head (&list); |
while ((e = list_next (e)) != list_end (&list)) |
{ |
... |
} |
*/ |
struct list_elem * |
list_head (struct list *list) |
{ |
assert (list != NULL); |
return &list->head; |
} |
/* Return's LIST's tail. */ |
struct list_elem * |
list_tail (struct list *list) |
{ |
assert (list != NULL); |
return &list->tail; |
} |
/* Inserts ELEM just before BEFORE, which may be either an |
interior element or a tail. The latter case is equivalent to |
list_push_back(). */ |
void |
list_insert (struct list_elem *before, struct list_elem *elem) |
{ |
assert (is_interior (before) || is_tail (before)); |
assert (elem != NULL); |
elem->prev = before->prev; |
elem->next = before; |
before->prev->next = elem; |
before->prev = elem; |
} |
/* Removes elements FIRST though LAST (exclusive) from their |
current list, then inserts them just before BEFORE, which may |
be either an interior element or a tail. */ |
void |
list_splice (struct list_elem *before, |
struct list_elem *first, struct list_elem *last) |
{ |
assert (is_interior (before) || is_tail (before)); |
if (first == last) |
return; |
last = list_prev (last); |
assert (is_interior (first)); |
assert (is_interior (last)); |
/* Cleanly remove FIRST...LAST from its current list. */ |
first->prev->next = last->next; |
last->next->prev = first->prev; |
/* Splice FIRST...LAST into new list. */ |
first->prev = before->prev; |
last->next = before; |
before->prev->next = first; |
before->prev = last; |
} |
/* Inserts ELEM at the beginning of LIST, so that it becomes the |
front in LIST. */ |
void |
list_push_front (struct list *list, struct list_elem *elem) |
{ |
list_insert (list_begin (list), elem); |
} |
/* Inserts ELEM at the end of LIST, so that it becomes the |
back in LIST. */ |
void |
list_push_back (struct list *list, struct list_elem *elem) |
{ |
list_insert (list_end (list), elem); |
} |
/* Removes ELEM from its list and returns the element that |
followed it. Undefined behavior if ELEM is not in a list. |
It's not safe to treat ELEM as an element in a list after |
removing it. In particular, using list_next() or list_prev() |
on ELEM after removal yields undefined behavior. This means |
that a naive loop to remove the elements in a list will fail: |
** DON'T DO THIS ** |
for (e = list_begin (&list); e != list_end (&list); e = list_next (e)) |
{ |
...do something with e... |
list_remove (e); |
} |
** DON'T DO THIS ** |
Here is one correct way to iterate and remove elements from a |
list: |
for (e = list_begin (&list); e != list_end (&list); e = list_remove (e)) |
{ |
...do something with e... |
} |
If you need to free() elements of the list then you need to be |
more conservative. Here's an alternate strategy that works |
even in that case: |
while (!list_empty (&list)) |
{ |
struct list_elem *e = list_pop_front (&list); |
...do something with e... |
} |
*/ |
struct list_elem * |
list_remove (struct list_elem *elem) |
{ |
assert (is_interior (elem)); |
elem->prev->next = elem->next; |
elem->next->prev = elem->prev; |
return elem->next; |
} |
/* Removes the front element from LIST and returns it. |
Undefined behavior if LIST is empty before removal. */ |
struct list_elem * |
list_pop_front (struct list *list) |
{ |
struct list_elem *front = list_front (list); |
list_remove (front); |
return front; |
} |
/* Removes the back element from LIST and returns it. |
Undefined behavior if LIST is empty before removal. */ |
struct list_elem * |
list_pop_back (struct list *list) |
{ |
struct list_elem *back = list_back (list); |
list_remove (back); |
return back; |
} |
/* Returns the front element in LIST. |
Undefined behavior if LIST is empty. */ |
struct list_elem * |
list_front (struct list *list) |
{ |
assert (!list_empty (list)); |
return list->head.next; |
} |
/* Returns the back element in LIST. |
Undefined behavior if LIST is empty. */ |
struct list_elem * |
list_back (struct list *list) |
{ |
assert (!list_empty (list)); |
return list->tail.prev; |
} |
/* Returns the number of elements in LIST. |
Runs in O(n) in the number of elements. */ |
size_t |
list_size (struct list *list) |
{ |
struct list_elem *e; |
size_t cnt = 0; |
for (e = list_begin (list); e != list_end (list); e = list_next (e)) |
cnt++; |
return cnt; |
} |
/* Returns true if LIST is empty, false otherwise. */ |
bool |
list_empty (struct list *list) |
{ |
return list_begin (list) == list_end (list); |
} |
/* Swaps the `struct list_elem *'s that A and B point to. */ |
static void |
swap (struct list_elem **a, struct list_elem **b) |
{ |
struct list_elem *t = *a; |
*a = *b; |
*b = t; |
} |
/* Reverses the order of LIST. */ |
void |
list_reverse (struct list *list) |
{ |
if (!list_empty (list)) |
{ |
struct list_elem *e; |
for (e = list_begin (list); e != list_end (list); e = e->prev) |
swap (&e->prev, &e->next); |
swap (&list->head.next, &list->tail.prev); |
swap (&list->head.next->prev, &list->tail.prev->next); |
} |
} |
/* Returns true only if the list elements A through B (exclusive) |
are in order according to LESS given auxiliary data AUX. */ |
static bool |
is_sorted (struct list_elem *a, struct list_elem *b, |
list_less_func *less, void *aux) |
{ |
if (a != b) |
while ((a = list_next (a)) != b) |
if (less (a, list_prev (a), aux)) |
return false; |
return true; |
} |
/* Finds a run, starting at A and ending not after B, of list |
elements that are in nondecreasing order according to LESS |
given auxiliary data AUX. Returns the (exclusive) end of the |
run. |
A through B (exclusive) must form a non-empty range. */ |
static struct list_elem * |
find_end_of_run (struct list_elem *a, struct list_elem *b, |
list_less_func *less, void *aux) |
{ |
assert (a != NULL); |
assert (b != NULL); |
assert (less != NULL); |
assert (a != b); |
do |
{ |
a = list_next (a); |
} |
while (a != b && !less (a, list_prev (a), aux)); |
return a; |
} |
/* Merges A0 through A1B0 (exclusive) with A1B0 through B1 |
(exclusive) to form a combined range also ending at B1 |
(exclusive). Both input ranges must be nonempty and sorted in |
nondecreasing order according to LESS given auxiliary data |
AUX. The output range will be sorted the same way. */ |
static void |
inplace_merge (struct list_elem *a0, struct list_elem *a1b0, |
struct list_elem *b1, |
list_less_func *less, void *aux) |
{ |
assert (a0 != NULL); |
assert (a1b0 != NULL); |
assert (b1 != NULL); |
assert (less != NULL); |
assert (is_sorted (a0, a1b0, less, aux)); |
assert (is_sorted (a1b0, b1, less, aux)); |
while (a0 != a1b0 && a1b0 != b1) |
if (!less (a1b0, a0, aux)) |
a0 = list_next (a0); |
else |
{ |
a1b0 = list_next (a1b0); |
list_splice (a0, list_prev (a1b0), a1b0); |
} |
} |
/* Sorts LIST according to LESS given auxiliary data AUX, using a |
natural iterative merge sort that runs in O(n lg n) time and |
O(1) space in the number of elements in LIST. */ |
void |
list_sort (struct list *list, list_less_func *less, void *aux) |
{ |
size_t output_run_cnt; /* Number of runs output in current pass. */ |
assert (list != NULL); |
assert (less != NULL); |
/* Pass over the list repeatedly, merging adjacent runs of |
nondecreasing elements, until only one run is left. */ |
do |
{ |
struct list_elem *a0; /* Start of first run. */ |
struct list_elem *a1b0; /* End of first run, start of second. */ |
struct list_elem *b1; /* End of second run. */ |
output_run_cnt = 0; |
for (a0 = list_begin (list); a0 != list_end (list); a0 = b1) |
{ |
/* Each iteration produces one output run. */ |
output_run_cnt++; |
/* Locate two adjacent runs of nondecreasing elements |
A0...A1B0 and A1B0...B1. */ |
a1b0 = find_end_of_run (a0, list_end (list), less, aux); |
if (a1b0 == list_end (list)) |
break; |
b1 = find_end_of_run (a1b0, list_end (list), less, aux); |
/* Merge the runs. */ |
inplace_merge (a0, a1b0, b1, less, aux); |
} |
} |
while (output_run_cnt > 1); |
assert (is_sorted (list_begin (list), list_end (list), less, aux)); |
} |
/* Inserts ELEM in the proper position in LIST, which must be |
sorted according to LESS given auxiliary data AUX. |
Runs in O(n) average case in the number of elements in LIST. */ |
void |
list_insert_ordered (struct list *list, struct list_elem *elem, |
list_less_func *less, void *aux) |
{ |
struct list_elem *e; |
assert (list != NULL); |
assert (elem != NULL); |
assert (less != NULL); |
for (e = list_begin (list); e != list_end (list); e = list_next (e)) |
if (less (elem, e, aux)) |
break; |
return list_insert (e, elem); |
} |
/* Iterates through LIST and removes all but the first in each |
set of adjacent elements that are equal according to LESS |
given auxiliary data AUX. If DUPLICATES is non-null, then the |
elements from LIST are appended to DUPLICATES. */ |
void |
list_unique (struct list *list, struct list *duplicates, |
list_less_func *less, void *aux) |
{ |
struct list_elem *elem, *next; |
assert (list != NULL); |
assert (less != NULL); |
if (list_empty (list)) |
return; |
elem = list_begin (list); |
while ((next = list_next (elem)) != list_end (list)) |
if (!less (elem, next, aux) && !less (next, elem, aux)) |
{ |
list_remove (next); |
if (duplicates != NULL) |
list_push_back (duplicates, next); |
} |
else |
elem = next; |
} |
/* Returns the element in LIST with the largest value according |
to LESS given auxiliary data AUX. If there is more than one |
maximum, returns the one that appears earlier in the list. If |
the list is empty, returns its tail. */ |
struct list_elem * |
list_max (struct list *list, list_less_func *less, void *aux) |
{ |
struct list_elem *max = list_begin (list); |
if (max != list_end (list)) |
{ |
struct list_elem *e; |
for (e = list_next (max); e != list_end (list); e = list_next (e)) |
if (less (max, e, aux)) |
max = e; |
} |
return max; |
} |
/* Returns the element in LIST with the smallest value according |
to LESS given auxiliary data AUX. If there is more than one |
minimum, returns the one that appears earlier in the list. If |
the list is empty, returns its tail. */ |
struct list_elem * |
list_min (struct list *list, list_less_func *less, void *aux) |
{ |
struct list_elem *min = list_begin (list); |
if (min != list_end (list)) |
{ |
struct list_elem *e; |
for (e = list_next (min); e != list_end (list); e = list_next (e)) |
if (less (e, min, aux)) |
min = e; |
} |
return min; |
} |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/list.h |
---|
0,0 → 1,170 |
#ifndef __LIST_H |
#define __LIST_H |
/* This code is taken from the Pintos education OS. |
* For copyright information, see www.pintos-os.org */ |
/* Doubly linked list. |
This implementation of a doubly linked list does not require |
use of dynamically allocated memory. Instead, each structure |
that is a potential list element must embed a struct list_elem |
member. All of the list functions operate on these `struct |
list_elem's. The list_entry macro allows conversion from a |
struct list_elem back to a structure object that contains it. |
For example, suppose there is a needed for a list of `struct |
foo'. `struct foo' should contain a `struct list_elem' |
member, like so: |
struct foo |
{ |
struct list_elem elem; |
int bar; |
...other members... |
}; |
Then a list of `struct foo' can be be declared and initialized |
like so: |
struct list foo_list; |
list_init (&foo_list); |
Iteration is a typical situation where it is necessary to |
convert from a struct list_elem back to its enclosing |
structure. Here's an example using foo_list: |
struct list_elem *e; |
for (e = list_begin (&foo_list); e != list_end (&foo_list); |
e = list_next (e)) |
{ |
struct foo *f = list_entry (e, struct foo, elem); |
...do something with f... |
} |
You can find real examples of list usage throughout the |
source; for example, malloc.c, palloc.c, and thread.c in the |
threads directory all use lists. |
The interface for this list is inspired by the list<> template |
in the C++ STL. If you're familiar with list<>, you should |
find this easy to use. However, it should be emphasized that |
these lists do *no* type checking and can't do much other |
correctness checking. If you screw up, it will bite you. |
Glossary of list terms: |
- "front": The first element in a list. Undefined in an |
empty list. Returned by list_front(). |
- "back": The last element in a list. Undefined in an empty |
list. Returned by list_back(). |
- "tail": The element figuratively just after the last |
element of a list. Well defined even in an empty list. |
Returned by list_end(). Used as the end sentinel for an |
iteration from front to back. |
- "beginning": In a non-empty list, the front. In an empty |
list, the tail. Returned by list_begin(). Used as the |
starting point for an iteration from front to back. |
- "head": The element figuratively just before the first |
element of a list. Well defined even in an empty list. |
Returned by list_rend(). Used as the end sentinel for an |
iteration from back to front. |
- "reverse beginning": In a non-empty list, the back. In an |
empty list, the head. Returned by list_rbegin(). Used as |
the starting point for an iteration from back to front. |
- "interior element": An element that is not the head or |
tail, that is, a real list element. An empty list does |
not have any interior elements. |
*/ |
#include <stdbool.h> |
#include <stddef.h> |
#include <stdint.h> |
/* List element. */ |
struct list_elem |
{ |
struct list_elem *prev; /* Previous list element. */ |
struct list_elem *next; /* Next list element. */ |
}; |
/* List. */ |
struct list |
{ |
struct list_elem head; /* List head. */ |
struct list_elem tail; /* List tail. */ |
}; |
/* Converts pointer to list element LIST_ELEM into a pointer to |
the structure that LIST_ELEM is embedded inside. Supply the |
name of the outer structure STRUCT and the member name MEMBER |
of the list element. See the big comment at the top of the |
file for an example. */ |
#define list_entry(LIST_ELEM, STRUCT, MEMBER) \ |
((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next \ |
- offsetof (STRUCT, MEMBER.next))) |
void list_init (struct list *); |
/* List traversal. */ |
struct list_elem *list_begin (struct list *); |
struct list_elem *list_next (struct list_elem *); |
struct list_elem *list_end (struct list *); |
struct list_elem *list_rbegin (struct list *); |
struct list_elem *list_prev (struct list_elem *); |
struct list_elem *list_rend (struct list *); |
struct list_elem *list_head (struct list *); |
struct list_elem *list_tail (struct list *); |
/* List insertion. */ |
void list_insert (struct list_elem *, struct list_elem *); |
void list_splice (struct list_elem *before, |
struct list_elem *first, struct list_elem *last); |
void list_push_front (struct list *, struct list_elem *); |
void list_push_back (struct list *, struct list_elem *); |
/* List removal. */ |
struct list_elem *list_remove (struct list_elem *); |
struct list_elem *list_pop_front (struct list *); |
struct list_elem *list_pop_back (struct list *); |
/* List elements. */ |
struct list_elem *list_front (struct list *); |
struct list_elem *list_back (struct list *); |
/* List properties. */ |
size_t list_size (struct list *); |
bool list_empty (struct list *); |
/* Miscellaneous. */ |
void list_reverse (struct list *); |
/* Compares the value of two list elements A and B, given |
auxiliary data AUX. Returns true if A is less than B, or |
false if A is greater than or equal to B. */ |
typedef bool list_less_func (const struct list_elem *a, |
const struct list_elem *b, |
void *aux); |
/* Operations on lists with ordered elements. */ |
void list_sort (struct list *, |
list_less_func *, void *aux); |
void list_insert_ordered (struct list *, struct list_elem *, |
list_less_func *, void *aux); |
void list_unique (struct list *, struct list *duplicates, |
list_less_func *, void *aux); |
/* Max and min. */ |
struct list_elem *list_max (struct list *, list_less_func *, void *aux); |
struct list_elem *list_min (struct list *, list_less_func *, void *aux); |
#endif /* list.h */ |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/quicksort.c |
---|
0,0 → 1,317 |
/* |
* Parallel Quicksort. |
* |
* Demo application that shows how one might use threadpools/futures |
* in an application. |
* |
* Requires threadpool.c/threadpool.h |
* |
* Written by Godmar Back gback@cs.vt.edu for CS3214 Fall 2010. |
*/ |
#include <stdlib.h> |
#include <stdbool.h> |
#include <stdint.h> |
#include <stdio.h> |
#include <string.h> |
#include <unistd.h> |
#include <sys/time.h> |
#include <pthread.h> |
#include <assert.h> |
#include <getopt.h> |
#include "threadpool.h" |
typedef void (*sort_func)(int *, int); |
/* Return true if array 'a' is sorted. */ |
static bool |
check_sorted(int a[], int n) |
{ |
int i; |
for (i = 0; i < n-1; i++) |
if (a[i] > a[i+1]) |
return false; |
return true; |
} |
/* ------------------------------------------------------------- |
* Built-in qsort. |
*/ |
static int cmp_int(const void *a, const void *b) |
{ |
return *(int *)a - *(int *)b; |
} |
static void builtin_qsort(int *a, int N) |
{ |
qsort(a, N, sizeof(int), cmp_int); |
} |
/* ------------------------------------------------------------- |
* Quicksort utility routines. |
*/ |
/* Swap two elements */ |
static inline void swap(int *a, int *b) |
{ |
int tmp = *a; |
*a = *b; |
*b = tmp; |
} |
/* Partitioning using middle element as pivot */ |
static int |
qsort_partition(int * array, int left, int right) |
{ |
int middle = left + (right-left)/2; |
// left <=> middle |
swap(array + left, array + middle); |
int current, last = left; |
for (current = left + 1; current <= right; ++current) { |
if (array[current] < array[left]) { |
++last; |
// last <=> current |
swap(array + last, array + current); |
} |
} |
// left <=> last |
swap(array + left, array + last); |
return last; |
} |
/* ------------------------------------------------------------- |
* Serial implementation. |
*/ |
static void |
qsort_internal_serial(int *array, int left, int right) |
{ |
if (left >= right) |
return; |
int split = qsort_partition(array, left, right); |
qsort_internal_serial(array, left, split - 1); |
qsort_internal_serial(array, split + 1, right); |
} |
static void |
qsort_serial(int *array, int N) |
{ |
qsort_internal_serial(array, 0, N - 1); |
} |
/* ------------------------------------------------------------- |
* Parallel implementation. |
*/ |
static struct thread_pool * threadpool; |
/* qsort_task describes a unit of parallel work */ |
struct qsort_task { |
int *array; |
int left, right, depth; |
struct future *future; |
struct qsort_task *next; |
} * tasks; /* list of outstanding tasks, protected by task_lock */ |
static pthread_mutex_t task_lock = PTHREAD_MUTEX_INITIALIZER; |
/* Create a qsort_task instance */ |
static struct qsort_task * |
create_qsort_task(int * array, int left, int right, int depth) |
{ |
struct qsort_task * task = calloc(sizeof(struct qsort_task), 1); |
task->array = array; |
task->left = left; |
task->right = right; |
task->depth = depth; |
return task; |
} |
/* Add a qsort_task instance to list of outstanding tasks */ |
static void |
add_qsort_task(struct qsort_task * task) |
{ |
pthread_mutex_lock(&task_lock); |
assert(task->future); |
task->next = tasks; |
tasks = task; |
pthread_mutex_unlock(&task_lock); |
} |
#define MAX_SEGMENTS 1024 |
static int qsegment_size [MAX_SEGMENTS]; |
static int qsegment_n = 0; |
/* Wait for all outstanding tasks. */ |
static void |
wait_for_tasks () |
{ |
qsegment_n = 0; |
for (;;) { |
struct qsort_task * head = NULL; |
pthread_mutex_lock(&task_lock); |
head = tasks; |
if (head) |
tasks = head->next; |
pthread_mutex_unlock(&task_lock); |
if (!head) |
break; |
intptr_t size = (intptr_t) future_get(head->future); |
future_free(head->future); |
if (qsegment_n < MAX_SEGMENTS) |
qsegment_size[qsegment_n++] = size; |
free(head); |
} |
} |
static void |
report_stats() |
{ |
builtin_qsort(qsegment_size, qsegment_n); |
int i; |
printf("Processed %d segments of sizes: ", qsegment_n); |
for (i = 0; i < qsegment_n; i++) |
printf("%d ", qsegment_size[i]); |
printf("\n"); |
} |
/* Parallel qsort - returns size of segment sorted */ |
static int |
qsort_internal_parallel(struct qsort_task * s) |
{ |
int * array = s->array; |
int left = s->left; |
int right = s->right; |
int depth = s->depth; |
if (left >= right) |
return 0; |
int split = qsort_partition(array, left, right); |
if (depth < 1) { |
qsort_internal_serial(array, left, split - 1); |
qsort_internal_serial(array, split + 1, right); |
} else { |
struct qsort_task * qleft = create_qsort_task(array, left, split-1, depth-1); |
qleft->future = thread_pool_submit(threadpool, |
(thread_pool_callable_func_t) qsort_internal_parallel, |
qleft); |
add_qsort_task(qleft); |
struct qsort_task * qright = create_qsort_task(array, split+1, right, depth-1); |
qright->future = thread_pool_submit(threadpool, |
(thread_pool_callable_func_t) qsort_internal_parallel, |
qright); |
add_qsort_task(qright); |
} |
return right - left; |
} |
// maximum depth to which each recursive call is executed in parallel |
static int depth = 3; |
static void |
qsort_parallel(int *array, int N) |
{ |
struct qsort_task * top = create_qsort_task(array, 0, N-1, depth); |
qsort_internal_parallel(top); |
wait_for_tasks(); |
free(top); |
} |
/* |
* Benchmark one run of sort_func sorter |
*/ |
static void |
benchmark(const char *benchmark_name, sort_func sorter, int *a0, int N) |
{ |
struct timeval start, end, diff; |
int *a = malloc(N * sizeof(int)); |
memcpy(a, a0, N * sizeof(int)); |
gettimeofday(&start, NULL); |
sorter(a, N); |
gettimeofday(&end, NULL); |
if (!check_sorted(a, N)) { |
fprintf(stderr, "Sort failed\n"); |
abort(); |
} |
timersub(&end, &start, &diff); |
printf("%-20s took %.3f sec.\n", benchmark_name, diff.tv_sec + diff.tv_usec / 1.0e6); |
free(a); |
} |
static void |
usage(char *av0, int depth, int nthreads) |
{ |
fprintf(stderr, "Usage: %s [-d <n>] [-n <n>] [-b] [-q] [-s <n>] <N>\n" |
" -d parallel recursion depth, default %d\n" |
" -n number of threads in pool, default %d\n" |
" -b run built-in qsort\n" |
" -s specify srand() seed\n" |
" -q don't run serial qsort\n" |
, av0, depth, nthreads); |
exit(0); |
} |
int |
main(int ac, char *av[]) |
{ |
int nthreads = 4; |
int c; |
bool run_builtin_qsort = false; |
bool run_serial_qsort = true; |
while ((c = getopt(ac, av, "d:n:bhs:q")) != EOF) { |
switch (c) { |
case 'd': |
depth = atoi(optarg); |
break; |
case 'n': |
nthreads = atoi(optarg); |
break; |
case 's': |
srand(atoi(optarg)); |
break; |
case 'b': |
run_builtin_qsort = true; |
break; |
case 'q': |
run_serial_qsort = false; |
break; |
case 'h': |
usage(av[0], depth, nthreads); |
} |
} |
if (optind == ac) |
usage(av[0], depth, nthreads); |
int N = atoi(av[optind]); |
int i, * a0 = malloc(N * sizeof(int)); |
for (i = 0; i < N; i++) |
a0[i] = random(); |
if (run_builtin_qsort) |
benchmark("Built-in qsort", builtin_qsort, a0, N); |
if (run_serial_qsort) |
benchmark("qsort serial", qsort_serial, a0, N); |
threadpool = thread_pool_new(nthreads); |
printf("Using %d threads, recursive parallel depth=%d\n", nthreads, depth); |
sleep(1); |
benchmark("qsort parallel", qsort_parallel, a0, N); |
report_stats(); |
thread_pool_shutdown(threadpool); |
return 0; |
} |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/speedup.docx |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/speedup.docx |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/speedup.pdf |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/speedup.pdf |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool-handout.pdf |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool-handout.pdf |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool.c |
---|
0,0 → 1,118 |
#include "threadpool.h" |
#include "list.h" |
#include <stdlib.h> |
#include <semaphore.h> |
#include <pthread.h> |
struct future { |
sem_t finished; |
struct list_elem elem; |
thread_pool_callable_func_t callable; |
void * callable_data; |
void * result; |
}; |
struct thread_pool { |
pthread_mutex_t mutex_lock; |
pthread_cond_t condition_var; |
struct list future_list; |
bool shutting_down; |
int thread_list_length; |
pthread_t * thread_list; |
}; |
static void * thread_func(void * arg) { |
struct thread_pool *t_pool = arg; |
pthread_mutex_lock(&t_pool->mutex_lock); |
while(1) { |
// Get lock and wait for signal while there are no jobs queued |
while (list_size(&t_pool->future_list) == 0) { |
pthread_cond_wait(&t_pool->condition_var,&t_pool->mutex_lock); |
if (t_pool->shutting_down) { |
pthread_mutex_unlock(&t_pool->mutex_lock); |
return NULL; |
} |
} |
// Retreive and remove the first future in the list |
struct list_elem *e = list_pop_front(&t_pool->future_list); |
pthread_mutex_unlock(&t_pool->mutex_lock); |
struct future *f_entry = list_entry(e, struct future, elem); |
// Store results of the function |
f_entry->result = f_entry->callable(f_entry->callable_data); |
// Signal completion of the future |
sem_post(&f_entry->finished); |
pthread_mutex_lock(&t_pool->mutex_lock); |
if (t_pool->shutting_down) |
return NULL; |
} |
} |
/* Create a new thread pool with n threads. */ |
struct thread_pool * thread_pool_new(int nthreads) { |
// Allocate a new thread pool structure |
struct thread_pool *t_pool = malloc(sizeof(struct thread_pool)); |
// Initialize the thread pool variables |
pthread_mutex_init(&t_pool->mutex_lock,NULL); |
pthread_cond_init(&t_pool->condition_var,NULL); |
list_init(&t_pool->future_list); |
t_pool->shutting_down = false; |
t_pool->thread_list_length = nthreads; |
// Allocate and start each thread in the thread pool |
t_pool->thread_list = malloc(nthreads * sizeof(pthread_t)); |
int i; |
for (i = 0; i < nthreads; i++) |
pthread_create(t_pool->thread_list + i, NULL, thread_func, t_pool); |
return t_pool; |
} |
/* Shutdown this thread pool. May or may not execute already queued tasks. */ |
void thread_pool_shutdown(struct thread_pool * t_pool) { |
// Set the shutdown flag and notify all worker threads |
pthread_mutex_lock(&t_pool->mutex_lock); |
t_pool->shutting_down = true; |
pthread_cond_broadcast(&t_pool->condition_var); |
pthread_mutex_unlock(&t_pool->mutex_lock); |
// Wait for all worker threads to join before returning |
int i; |
for (i = 0; i < t_pool->thread_list_length; i++) |
pthread_join(t_pool->thread_list[i],NULL); |
free(t_pool->thread_list); |
free(t_pool); |
} |
/* Submit a callable to thread pool and return future. |
* The returned future can be used in future_get() and future_free() */ |
struct future * thread_pool_submit(struct thread_pool * t_pool, |
thread_pool_callable_func_t callable, void * callable_data) { |
// Allocate and initialize the new future |
struct future *f_entry = malloc(sizeof(struct future)); |
sem_init(&f_entry->finished,0,0); |
f_entry->callable = callable; |
f_entry->callable_data = callable_data; |
// Get the lock on the thread pool and enqueue the future to the end of the work queue |
pthread_mutex_lock(&t_pool->mutex_lock); |
list_push_back(&t_pool->future_list,&f_entry->elem); |
// Notify one worker thread to process the future |
pthread_cond_signal(&t_pool->condition_var); |
pthread_mutex_unlock(&t_pool->mutex_lock); |
return f_entry; |
} |
/* Make sure that thread pool has completed executing this callable, then return result. */ |
void * future_get(struct future * f_entry) { |
sem_wait(&f_entry->finished); |
return f_entry->result; |
} |
/* Deallocate this future. Must be called after future_get() */ |
void future_free(struct future * f_entry) { |
free(f_entry); |
} |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool.h |
---|
0,0 → 1,23 |
/* Create a new thread pool with n threads. */ |
struct thread_pool * thread_pool_new(int nthreads); |
/* Shutdown this thread pool. May or may not execute already queued tasks. */ |
void thread_pool_shutdown(struct thread_pool *); |
/* A function pointer representing a 'callable' */ |
typedef void * (* thread_pool_callable_func_t) (void * data); |
/* Submit a callable to thread pool and return future. |
* The returned future can be used in future_get() and future_free() |
*/ |
struct future * thread_pool_submit( |
struct thread_pool *, |
thread_pool_callable_func_t callable, |
void * callable_data); |
/* Make sure that thread pool has completed executing this callable, |
* then return result. */ |
void * future_get(struct future *); |
/* Deallocate this future. Must be called after future_get() */ |
void future_free(struct future *); |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool_test |
---|
Cannot display: file marked as a binary type. |
svn:mime-type = application/octet-stream |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool_test |
---|
Property changes: |
Added: svn:mime-type |
+application/octet-stream |
\ No newline at end of property |
/Classwork/CS3214 - Computer Systems/Project 4 - Threadpool/threadpool_test.c |
---|
0,0 → 1,168 |
/* |
* Thread pool test program. |
* |
* This program creates a thread pool with a configurable number |
* of threads and then submits a configurable number of tasks. |
* Each task reports which thread executed it. |
* |
* An associated Python script (check.py) parses the output and |
* checks that 'nthreads' tasks are executing in parallel. |
* |
* This program makes idealizing and simplifying assumptions. |
* |
* First, it assumes that there are enough physical CPUs available |
* so that in fact 'nthreads' threads can execute. This may not |
* be true on a heavily loaded machine; test results will not be |
* reliable under these circumstances. |
* |
* Second, the specification does not require that all threads |
* have reached the point where they wait on the pool's condition |
* variable. To increase the likelihood that this is the case, |
* the test script pauses for 1 second before submitting tasks. |
* |
* Written by G. Back for CS3214 Spring 2010. |
*/ |
#include <assert.h> |
#include <pthread.h> |
#include <stdio.h> |
#include <string.h> |
#include <stdlib.h> |
#include <unistd.h> |
#include <sys/time.h> |
#include <sys/resource.h> |
#include <time.h> |
#include "threadpool.h" |
// helper function to count number of threads in this process |
static int count_number_of_threads(void); |
/* Data to be passed to callable. */ |
struct callable_data { |
int number; |
}; |
/* |
* A callable. |
* |
* Returns a string that reports its number, which thread |
* executes the task, and the start and end time of the |
* task's execution. |
*/ |
static void * |
callable_task(struct callable_data * callable) |
{ |
char buf[1024]; |
struct timeval start, end; |
assert(gettimeofday(&start, NULL) == 0); |
struct timespec t = { .tv_sec = 0, .tv_nsec = 5000000 }; |
assert(nanosleep(&t, NULL) == 0); |
assert(gettimeofday(&end, NULL) == 0); |
snprintf(buf, sizeof buf, |
"Future #%d Thread #%p start=%ld.%ld end=%ld.%ld", |
callable->number, (void *)pthread_self(), |
start.tv_sec, start.tv_usec, |
end.tv_sec, end.tv_usec); |
return strdup(buf); |
} |
int |
main(int ac, char *av[]) |
{ |
assert (ac > 2 || !!!"Usage: threadpool_test <nthreads> <ntasks>"); |
int nthreads = atoi(av[1]); |
int ntasks = atoi(av[2]); |
struct thread_pool * ex = thread_pool_new(nthreads); |
const int N = ntasks; |
struct future * f[N]; |
// sleep .5 seconds to give threads time to start up |
struct timespec sleep_for = { .tv_sec = 0, .tv_nsec = 5*1e8 }; |
nanosleep(&sleep_for, NULL); |
int threadsstarted = count_number_of_threads() - 1; |
if (threadsstarted != nthreads) { |
printf("The thread pool started %d instead of %d threads.\n", |
threadsstarted, nthreads); |
return EXIT_FAILURE; |
} |
// check for busy-waiting implementation |
struct rusage usage; |
int rc = getrusage(RUSAGE_SELF, &usage); |
if (rc == -1) |
perror("getrusage"), exit(-1); |
if (usage.ru_utime.tv_sec > 0 || usage.ru_utime.tv_usec > 400000) { |
printf("Thread pool is consuming excessive CPU time without running any jobs\n"); |
return EXIT_FAILURE; |
} |
// submit N tasks and record futures obtained in return |
int i; |
for (i = 0; i < N; i++) { |
struct callable_data * callable_data = malloc(sizeof *callable_data); |
callable_data->number = i; |
f[i] = thread_pool_submit(ex, |
(thread_pool_callable_func_t) callable_task, |
callable_data); |
} |
printf("Main thread: %p\n", (void *)pthread_self()); |
// wait for each future |
for (i = 0; i < N; i++) { |
printf("%s\n", (char *) future_get(f[i])); |
} |
// check that no pool thread shut down prematurely |
threadsstarted = count_number_of_threads() - 1; |
if (threadsstarted != nthreads) { |
printf("Only %d thread pool threads are left, should be %d threads.\n", |
threadsstarted, nthreads); |
return EXIT_FAILURE; |
} |
thread_pool_shutdown(ex); |
// sleep .3 seconds to give threads time to shut down |
// pthread_join() is not atomic with respect to the number |
// of tasks reported by /proc/self/status |
sleep_for.tv_nsec = 3*1e8; |
nanosleep(&sleep_for, NULL); |
int threadsleft = count_number_of_threads(); |
if (threadsleft != 1) { |
printf("The thread pool did not correctly shut down" |
", there are %d threads left.\n", threadsleft); |
return EXIT_FAILURE; |
} |
printf("Done.\n"); |
return EXIT_SUCCESS; |
} |
/** |
* Count number of threads by scanning /proc/self/status |
* for the Threads: ... line |
*/ |
static int |
count_number_of_threads(void) |
{ |
FILE * p = fopen("/proc/self/status", "r"); |
while (!feof(p)) { |
int threadsleft; |
char buf[128]; |
fgets(buf, sizeof buf, p); |
if (sscanf(buf, "Threads: %d\n", &threadsleft) != 1) |
continue; |
fclose(p); |
return threadsleft; |
} |
printf("Internal error, please send email to gback@cs.vt.edu\n"); |
abort(); |
} |