CPSC 213: Assignment 9
Due Monday Nov 26 2012, 6pm
In this assignment you will gain experience in programming with
synchronization using C and the uthread package. You are
provided with spinlocks and an implementation of monitors. You will
implement reader-writer monitor and condition variables; you will then
use these abstractions to solve specific problems.
Task 1: Comment Existing uthread Spinlock and Monitor Code
You have already inspected the file uthread.c in the previous
assignment to understand its control flow for the creation and use of
threads. In this assignment, you are given an updated version of this
file. You will now inspect and comment the parts of the code (structs
and functions) that implement spinlocks and monitors (at the top and
bottom of the file, respectively). Do not comment every line of the
function; rather, provide a single comment for the whole function.
Your goal is to convince the reader of the comment that you understand
what is happening in that function.
Task 2: Implement Reader-Writer Monitor
Implement a multiple-reader, single-writer monitor. Recall that this
monitor can be in one of three states: (a) held exclusively by a
writer, (b) being read concurrently by one or more readers, or (c)
free. Writers enter the monitor using the
uthread_monitor_enter function and must wait for the monitor
to be in the free state before entering. Readers enter the monitor
using the new uthread_monitor_enter_read_only function and
can enter the monitor if it is in either the reader or free states
(i.e., (b) or (c) above), but must wait if the monitor is currently
held by a writer. You will implement the
uthread_monitor_enter_read_only and make small changes to the
monitor data structure and the existing monitor procedures. Use
uthread_monitor_enter as a guide;
uthread_monitor_enter_read_only will be almost identical. The
main difference is that uthread_monitor_enter_read_only does
not set the monitor holder field: you will need to indicate readers
are in the monitor some other way.
Task 3: Test Reader-Writer Monitor
Test your new monitor using the provided
reader_writer_test.c. The test consists of four reader
threads and one writer thread accessing two shared integers. It has
three modes of execution: non-synchronized, monitor-synchronized, and
reader-writer-monitor synchronized. For sufficiently large values of
the count command-line option, the nonsynchronized verion
will fail with read, write or end errors. Ensure the correctness of
your new monitor by ensuring that you do not get any of these errors
when you run it in the reader-writer mode.
Task 4: Implement Condition Variables
Implement condition variables. There are stubs in the code provided to
you, your task is to fill them in. The state of condition variables is stored in the struct
uthread_cv and they have four operations:
uthread_cv_notify, and uthread_cv_notify_all. Their
implementations will be quite similar to that of monitors in that, for
example, they will be implemented by a core data structure protected
by a spinlock and that they will block and unblock threads.
Task 5: Test and Use Condition Variables
First, test your implementation by using the uthread
single-processor mode: initialize with uthread_init(1). Write
a simple test program with two threads, one that waits and one that
notifies it. Name this program cv_test.c
Next, modify the provided bounded-buffer.c to synchronize
producers and consumers using monitors and condition variables. The
queue will be shared by producer and consumer threads, so use a
monitor to synchronize. The queue is fixed size and so it is possible
that an enqueue operation will find the queue full and thus
have no room for a new element. Use a condition variable to block an
enqueue on a full queue until a dequeue operation
frees space for the new element. Similarly, a dequeue
operation might find the queue empty. Use another condition variable
to block a dequeue on an empty queue until an
enqueue operation provides a new element.
Finally, test your modified bounded-buffer.c code with
different settings for the number of processors requested via
uthread_init. Create 4 threads: 2 producers that loop
enqueueing integers and 2 consumers that loop dequeueing
integers and printing them. First, test with 1 processor, to ensure
that your code performs correctly with deterministic and sequential
behavior. Then test with 2 processors to introduce nondeterminism.
Finally, test with 4 processors.
If you run your tests on a uniprocessor machine, the multiple kernel
threads created in uthread_init will be multiplexed across
the single processor by the operating system using its scheduling
policy to emulate a true multiprocessor. This emulation should be
sufficient for testing purposes, but you might see different behavior
on different uniprocessor platforms, and different behavior than if
you run on a true multiprocessor. (Note that the department Linux
servers are true multiprocessors.)
Use the handin program. The assignment directory is a9.
Please hand in exactly and only the following files with the specified names.
- README.txt that contains
- The first three lines should be your name, student number, and 4-character CS account
name, with each on a separate line, like:
- The statement "I have read and understood the plagiarism policies at
Of course, make sure that's true!
- Any additional assumptions or comments you would like to make.
Following the academic conduct guidelines, if you discussed the
assignment in detail with anybody besides the instructor or TAs, say
so explicitly and list their names here.
- Modified uthread.c containing your comments and additions
(reader-writer monitor and condition variables), as described above.
- Your cv_test.c simple test program.
- Modified bounded_buffer.c that uses the monitor and
condition variables to synchronized the shared queue and
enqueue and dequeue operations, as described above.
File Format Requirements
the section of the same name in the second assignment for the file format
requirements. All files you handin MUST be plain ASCII text, and all
source code MUST compile on the ugrad Linux x86 machines in order to
receive credit for it.
Last modified 2012-11-19 00:15