CSE 451

Introduction to Operating Systems

Spring 1999

Program 1   Concurrency and Java Warm-Up

The goals of this program are to learn some Java, to practice designing and using threads and monitors, and to build some basic operating systems functions and data structures.

Your program should have three threads, named Reader, Writer, and Reader_Writer, and two monitors, RW_Manager and Binary_Sem.  The threads access a common ready list RL that is controlled by the RW_Manager.  RL is a queue of process nodes, where each node contains a process name (a string of length less than 8 characters) and a time field. Implement RL as a doubly-linked list. The RL header should store the length of the list and an integer np giving the number of processors (Imagine RL as the ready list for a multiprocessor system).

The threads perform the following functions:

• Reader: Displays the current RL. Each cycle of the Reader is activated through the Binary_Sem monitor by the Writer and Reader_Writer threads.

• Writer: Reads commands from the keyboard and interprets them. Commands exist to add a process to RL, to delete a named process from RL, to change np, or to terminate a run. Writer triggers (activates) Reader after every command, through Binary_Sem.

• Reader_Writer: Loops through two phases, a read phase and a write phase. During its read phase, it maintains an approximate history of RL by storing the length and np values and the current (real) clock time in a table. The table is displayed when the run terminates.  During the write phase, the first np processes on RL have their time fields incremented by 1 and are moved to the end of RL (The first np processes on RL are considered to be running; RL is round robin scheduled).  Reader is triggered by this thread at the end of each two phase loop.

• RW_Manager: Implements the standard readers-writers constraints, with possible writer starvation. It should have four methods, start_read, end_read, start_write, and end_write.

• Binary_Sem: Defines a binary semaphore, with semaphore wait and signal methods (Call them P and V, respectively, to avoid confusion with the Java monitor methods.).

Turn in a copy of your program and traces of several test runs that illustrate all of the required and interesting features of your program. Also give a brief discussion and evaluation of your results.

Grading will be based on program style, correctness, efficiency, documentation, test case selection, and any interesting insights that you can offer on your design and results.  For example, can you deduce the thread scheduling policy underlying your Java system?  What happens as the sleep() parameter varies from zero upwards in each thread?  Can you starve the writers?