Project #3

Assigned: March 10
Due: March 31, 3:00pm

This project consists of the following three problems:
  1. (40 points) [OSCJ] project 3 on p. 310 (or exercises 6.30 and 6.31 on p. 271 of the 7th ed). In class we presented an outline of a monitor solution to the dinning philoshopers problem. This problem requires you to implement that solution in Java using condition variables. Start by creating 5 philosopher threads, each identified by a number 0..4, which alternate between thinking and eating. When a philosopher gets hungry, the philosopher thread invokes the method pickupForks (int id). When a philosopher finishes eating, the philosopher calls the releaseForks (int id) method. Therefore, your monitor must implement the DiningServer interface. Your implementation of this interface must follow the outline of the monitor solution presented in class. Use Java condition variables to synchronize the activity of the philosophers and prevent deadlock.

    Recall, the monitor solution presented in class does not prevent a philosopher from starving. For instance, philosopher 1 and 3 could alternate eating and thinking in such a way that philosopher 2 could never eat. Modify the solution presented in class so to prevent starvation as well. In summary, your monitor solution to this problem must follow the outline of the monitor solution presented in class, but must also prevent the possibility of deadlock and starvation.

  2. (20 points) [OSCJ] exercise 6.41 on pp. 307-308 (or exercise 6.25 on p. 268 of the 7th ed). A barrier is a thread-synchronization mechanism which allows several threads to run for a period but then forces all threads to wait until all other threads have reached a certain point. Once all threads have reached this point (the barrier), they may all continue.

    The following code segment establishes a barrier and creates ten threads which synchronize according to the barrier:

    static final int NUM_WORKERS = 10;
Barrier wall = new Barrier(NUM_WORKERS);

for (int i=0; i < NUM_WORKERS; i++) {
   (new Thread (new Worker (i, wall))).start();

    Note that the barrier must be initialized to the number of threads to be synchronized and that each thread has a reference to the same barrier object wall.

    Each Worker runs as follows:

    // all threads have shared access to this barrier
Barrier wall;

// do some work for a while
work();

// now wait for others
barrier.waitForOthers();

// now do some more work
work();

    When a thread invokes the waitForOthers() method, it blocks until all threads have reached this method (the barrier). Once all threads have reached this method, they may all proceed with the remainder of their work.

    Implement a Barrier class, using Java synchronization, which provides definitions for only a constructor and the waitForOthers() method. Your Barrier class must work with the Worker and Factory classes.

  3. (40 points) Matrix multiplication is a textbook example for concurrency. To multiply a M x K matrix by a K x N matrix, start MN concurrent threads which each compute one of the MN entries in the resulting M x N product matrix, since each of these computations is independent of any other. The main thread waits for all worker threads to complete before outputting the values of the product matrix in some reasonable and readable format.

    Implement multi-threaded matrix multiplication, and use a Barrier object developed in the problem above to enable the main thread to wait for all others threads to finish. You may assume that each of the matrices to be multiplied will have no more than 10 rows or columns. To avoid input, you may also assume that the two matrices to be multiplied are hardcoded into the program as two-dimensional arrays:

    double maxtrixA[][] = {{1.0, 0.0, 2.0}, {-1.0, 3.0, 1.0}};
double maxtrixA[][] = {{3.0, 1.0}, {2.0, 1.0}, {1.0, 0.0}};

How to submit

Note: All directory and filenames below are case-sensitive. You must use the directory and filenames exactly as shown below (i.e., all lower case).

Prepare your submission file as /home/<logname>/projects/p3/p3.tar. Only the file /home/<logname>/projects/p3/p3.tar will be electronically collected from your account on the deadline. Organize your source code to each problem in the directories DiningPhilosophersMonitor, Barrier, and MatrixMultiplication.

Failure to follow these submission requirements will result in a 10% penalty.

Evaluation

Ninety percent of your score will come from correctness and 10% of your score will come from following our programming style guide. Applicable submission penalties will then be applied.

Return Home