MC78 Homework 1 (Fall 1996)

Due: September 19, 1996

1. Do problem 7 from chapter 2 of the textbook; it is on page 71.
2. The readers/writers problem (described in section 2.3.2 of the textbook, page 58, and solved there using semaphores) is easy to solve using monitors and condition variables. The monitor simply has to keep counts of how many readers and writers are active, and only allow in a new reader if the count of writers is zero and only allow in a new writer if the counts of readers and writers are both zero. By using condition variables signaled when the last reader or last writer relinquishes access, waiting readers or writers who were not initially able to acquire access can be notified when it becomes possible.

   The file Rw.java contains a Java program that implements this approach (using Java's variant of condition variables). This program provides a control panel with two buttons, one of which spawns a Reader thread and the other of which spawns a Writer thread. The output from the threads goes to the terminal window you ran Java from. Each thread outputs a message upon creation, another upon acquiring the access it needs, then sleeps for one to five seconds, and then outputs another message indicating that it is done reading or writing and releases the access right.

   The only problem (as indicated by a comment in the code) is that the acquireWriteAccess() method has been designed in such a way that a writer can wind up being delayed indefinitely by a steady stream of overlapping readers, even though the writer can have arrived on the scene before all but the first of the readers. (This is known as ``starvation.'') Your assignment is to replace this method with one that is starvation-free, so that the writer waits for any existing readers to finish, but no new readers can start until after the writer is done. This can be done without any changes outside that one method, and with the new version of the method only being a few lines of code longer than the old. Of course, your version must in addition to being starvation free still ensure the basic readers/writers condition, that if any thread has write access, there can be no other thread with either read or write access.

   There is no requirement that you actually try out the demo program before and after your modification (this is a homework, not a lab). However, I would encourage you to do so. You can quite easily and vividly see starvation happening in the unmodified program, as well as seeing the otherwise correct readers/writers behavior. You'll also be able to test the successfulness of your modification. See the lab 1 handout for more on compiling and running Java if you choose to try the program out. (Note that I didn't bother putting it into a package, so it doesn't need to be buried down a bunch of subdirectory levels like in the lab.) Ask if you need help with this.

Instructor: Max Hailperin