CPSC 213: Assignment 9

Due Monday Nov 26 2012, 6pm

Goal

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_create, uthread_cv_wait, 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.)

Provided Materials

Handing In

Use the handin program. The assignment directory is a9. Please hand in exactly and only the following files with the specified names.

  1. README.txt that contains
  2. Modified uthread.c containing your comments and additions (reader-writer monitor and condition variables), as described above.
  3. Your cv_test.c simple test program.
  4. 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

Refer to 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