90 lines
3.3 KiB

This homework lets you play around with a number of ways to implement a small,
deadlock-free vector object in C. The vector object is quite limited (e.g., it
only has add() and init() functions) but is just used to illustrate different
approaches to avoiding deadlock.
Some files that you should pay attention to are as follows. They, in
particular, are used by all the variants in this homework.
- mythreads.h
The usual wrappers around many different pthread (and other) library calls,
so as to ensure they are not failing silently
- vector-header.h
A simple header for the vector routines, mostly defining a fixed vector size
and then a struct that is used per vector (vector_t)
- main-header.h
A number of global variables common to each different program
- main-common.c
Contains the main() routine (with arg parsing) that initializes two vectors,
starts some threads to access them (via a worker() routine), and then waits
for the many vector_add()'s to complete
The variants of this homework are found in the following files. Each takes a
different approach to dealing with concurrency inside a "vector addition"
routine called vector_add(); examine the code in these files to get a sense of
what is going on. They all use the files above to make a complete runnable
- vector-deadlock.c
This version blithely grabs the locks in a particular order (dst then
src). By doing so, it creates an "invitation to deadlock", as one thread
might call vector_add(v1, v2) while another concurrently calls
vector_add(v2, v1).
- vector-global-order.c
This version of vector_add() grabs the locks in a total order, based on
address of the vector.
- vector-try-wait.c
This version of vector_add() uses pthread_mutex_trylock() to attempt to grab
locks; when the try fails, the code releases any locks it may hold and goes
back to the top and tries it all over again.
- vector-avoid-hold-and-wait.c
This version of vector_add() ensures it can't get stuck in a hold and wait
pattern by using a single lock around lock acquisition.
- vector-nolock.c
This version of vector_add() doesn't even use locks; rather, it uses an
atomic fetch-and-add to implement the vector_add() routine. Its semantics
(as a result) are slightly different.
Type "make" (and read the Makefile) to build each of five executables.
prompt> make
Then you can run a program by simply typing its name:
prompt> ./vector-deadlock
Each program takes the same set of arguments (see main-common.c for details):
This flag turns on the ability for threads to deadlock.
When you pass -d to the program, every other thread calls vector_add()
with the vectors in a different order, e.g., with two threads, and -d enabled,
Thread 0 calls vector_add(v1, v2) and Thread 1 calls vector_add(v2, v1)
This flag gives each thread a different set of vectors to call add()
upon, instead of just two vectors. Use this to see how things perform
when there isn't contention for the same set of vectors.
-n num_threads
Creates some number of threads; you need more than one to deadlock.
-l loops
How many times should each thread call vector_add()?
Verbose flag: prints out a little more about what is going on.
Turns on timing and shows how long everything took.