Subversion Repositories Code-Repo

Compare Revisions

No changes between revisions

Ignore whitespace Rev 140 → Rev 141

/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();
}