SE 552: Homework

Deadline: 5.30pm, Tuesday 27 April, 2004.

Homework

This homework is to provide two fixed versions of the Dining Philosophers problem, as discussed in class.

Download the source archive, and compile and run ajeffrey.teaching.test.TestPhilosopher. You should be able to get this class to deadlock.

1. Implement a resource ordering solution to the problem.

For this solution, you should save a copy of DeadlockingPhilosopher.java as OrderedPhilosopher.java, and edit it. You should make sure that the forks are picked up in order. You should do this by using Comparable objects rather than Object for the locks, then using the compareTo method to compare the locks for order. This ensures there will be no deadlock, as discussed in class and in Lea 2.2.6).

2. Implement a token-based solution to the problem.

For this solution, you should save a copy of DeadlockingPhilosopher.java as TokenPhilosopher.java, and edit it to use a token pool object to control access to the table. The main loop for each philosopher will now be:

  while (true) {
    delay ();
    Token t = pool.getToken ();
    ... as before ...
    pool.putToken (t);
  }

The token pool should keep a counter, and make sure that all of the philosophers do not sit down at once.

Your implementation of the PhilosopherFactory should keep a pointer to a token pool, plus a count of how many philosophers have been built so far. After the first philosopher is built, you can add a token to the token pool for each subsequent philosoher.

  public interface TokenPool {
    public void addNewToken ();
    public Token getToken () throws InterruptedException;
    public void putToken (Token t);
  }
  public interface Token {}

You should implement the token pool interface using wait/notify.

Using a token pool object, we can never reach a state where all of the philosophers are eating simultaneously, and so the system cannot deadlock, as discussed in class, and in Lea 2.3.4.

Submit your homework as a zip archive using Courses OnLine.