CS201J: Problem Set 5: Philosophers and Their Chopsticks

University of Virginia, Department of Computer Science
CS201J: Engineering Software, Fall 2003

Problem Set 5: Distributed Simulations
Subtyping, Inheritance and Concurrency Out: 21 October 2003
Part 1 Due: Thursday, 30 October (12:31)
Part 2 Due: Tuesday, 11 November (12:31)

Collaboration Policy (read carefully)
For questions 1-8 of this problem set, you should work alone and turn in your own solution. You may discuss your work with other students in the class, but the work you turn in should be your own. For questions 9 and 10 you may choose any number of students with whom to work. The scope and quality of your work should scale approximately as the square root of the number of students working together (e.g., a group of 2 students should do something 1.4 times as impressive as a student working alone; a group of 4 students should do something twice as impressive).

Reading: Chapters 7 and 8, and Bertrand Meyer's Static Typing and Other Mysteries of Life.

Purpose

Learn to use subtyping in a safe and useful way.
Learn to design using inheritance.
Understand race conditions and deadlocks.
Learn to write concurrent programs.
In the first part of this assignment (question 1-9), you will do some exercises that develop your understanding of type hierarchies and concurrent programming. In the second part, you will develop a distributed simulation.

Subtyping

Liskov's Chapter 7 and Meyer's Static Typing and Other Mysteries of Life describe very different rules for subtypes.
Liskov's substitution principle requires that the subtype specification supports reasoning based on the supertype specification. When we reasoned about a call to a supertype method, we reasoned that if a callsite satisfies the preconditions in the requires clause, it can assume the state after the call satisfies the postconditions in the effects clause. This means the subtype replacement for the method cannot make the precondition stronger since then our reasoning about the callsite may no longer hold (that is, the callsite may not satisfy the stronger precondition). Hence, the type of the return value of the subtype method must be a subtype of the type of the return value for the supertype method; the types of the parameters of the subtype method must be supertypes of the types of the parameters of the supertype method. This is known as contravariant typing.
Bertrand Meyer prefers covariant typing: the subtype replacement method parameter types must be subtypes of the types of the parameters of the supertype method. We will generalize his rules to apply to preconditions and postconditions also: the subtype method preconditions must be stronger than the supertype method precondition (pre_sub => pre_super) and the subtype postconditions must be stronger than the supertype postconditions (post_sub => post_super). Note that unlike the corresponding Liskov substitution rule, (pre_super && post_sub) => post_super, there is no need for pre_super in the covariant rule since post_sub => post_super.
The signature rule in Java is stricter: subtype methods must have the exact same return and parameter types of the method they override, although they may throw fewer exception types. Java does not place constraints on the behavior of methods, however, since the compiler is not able to check this.
Consider the minimal Tree class specified below (Tree.spec):
public class Tree {
    // OVERVIEW: A Tree is a mutable tree where the nodes are int values.
    //    A typical Tree is < value, [ children ] > 
    //       where value is the int value of the root of the tree
    //         and children is a sequence of zero or more Tree objects
    //            that are the children of this tree node.
    //    A Tree may not contain cycles, and may not contain the same
    //    Tree object as a sub-tree in more than one place.

    public Tree (int val) {
	// EFFECTS: Creates a tree with value val and no children: < value, [] >
    }

    public void addChild (Tree t) {
	// REQUIRES: t is not contained in this.
	// MODIFIES: this
	// EFFECTS: Adds t to the children of this, as the rightmost child:
	//    this_post = < this_pre.value, children > 
	//      where children = [ this_pre.children[0], this_pre.children[1], ..., 
	//                         this_pre.children[this_pre.children.length - 1], t ]
	//    NOTE: the rep is exposed!
    }

    public Tree getChild (int n) {
	// REQUIRES: 0 <= n < children.length
        // EFFECTS: Returns the Tree that is the nth leftmost child 
	//    of this.
	//    NOTE: the rep is exposed!
    }
}
and its BinaryTree subtype:
public class BinaryTree extends Tree {
    // OVERVIEW: A BinaryTree is a mutable tree where the nodes are int values
    //    and each node has zero, one or two children.
    //
    //    A typical BinaryTree is < value, [ children ] > 
    //       where value is the int value of the root of the tree
    //         and children is a sequence of zero, one or two BinaryTree objects
    //            that are the children of this tree node.
    //    A BinaryTree may not contain cycles, and may not contain the same
    //    BinaryTree object as a sub-tree in more than one place.

    public BinaryTree (int val) {
	// EFFECTS: Creates a tree with value val and no children: < value, null, null >
    }

    public void addChild (BinaryTree t) {
	// REQUIRES: t is not contained in this and this has zero or one children.
	// MODIFIES: this
	// EFFECTS (same as supertype):
	//    Adds t to the children of this, as the rightmost child:
	//    this_post = < this_pre.value, children > 
	//      where children = [ this_pre.children[0], this_pre.children[1], ..., 
	//                         this_pre.children[this_pre.children.length - 1], t ]
	// 
    }

    public BinaryTree getChild (int n) 
    {
	// REQUIRES: 0 <= n < 2 
	// EFFECTS: If this has n children, returns a copy of the BinaryTree 
	//    that is the nth leftmost child of this.  Otherwise, returns null.
    }
}
The Java compiler will not allow the getChild method of BinaryTree. Here is the error message:
BinaryTree.java:29: getChild(int) in BinaryTree cannot override getChild(int) in Tree; attempting to use incompatible return type
found   : BinaryTree
required: Tree
1. (10) Does the getChild method in BinaryTree satisfy the Liskov substitution principle? Explain why or why not.
2. (10) Does the addChild method in BinaryTree satisfy the Liskov substitution principle? Explain why or why not.
3. (10) Does the getChild method in BinaryTree satisfy the Eiffel subtyping rules? Explain why or why not.
4. (10) Does the addChild method in BinaryTree satisfy the Eiffel subtyping rules? Explain why or why not.

Note that the Java compiler will allow the addChild method, but it overloads instead of overrides the supertype addChild method. That is, according to the Java rules the BinaryTree class now has two addChild methods — one is the addChild (Tree) method inherited from Tree, and the other is the addChild (BinaryTree) method implemented by BinaryTree. This can be quite dangerous since the overloaded methods are resolve based on apparent types, not actual types. For example, try this program:
static public void main (String args[]) {
  Tree t = new BinaryTree (3);
  BinaryTree bt = new BinaryTree (4);

  t.addChild (bt);                   // Calls the addChild(Tree) method
  bt.addChild (new BinaryTree (5));  // Calls the addChild (BinaryTree) method
  bt.addChild (new Tree (12));       // Calls the addChild (Tree) method
}
Note that the first call uses the inherited addChild(Tree) because the apparent type of t is Tree, even though its actual type is BinaryTree.

Concurrency

Directions:

Download this file to your machine: ps5.zip
Save it to c:\localdata as you did with Problem Set 2.
Log into your Home Directory.
Open Eclipse by selecting Start | SEAS | Java Apps | Eclipse 2.1 | Eclipse CS201J (from the Windows Start menu)
Inside Eclipse (as with Problem Set 3):

Click on File | New | Project
Select the default option: Java->Java Project
Type in ps5 as the project name and click Finish.
Click Yes when Eclipse asks you if you want to switch to the Java perspective
Then, in Eclipse's Package Explorer, right click on ps3 and select Import.
Select Zip file as the import source.
Type c:\localdata\ps5.zip into the "From zip file" box. Hit tab. Then click Finish.

Now, set up your project to run ESC/Java on the source code files.

Click on Project | Properties.
Click on the ESC/Java option on the left.
Click on Enable ESC/Java.
Click Ok.

The ps5.zip file contains an implementation of a grid simulator similar to the cellular automata simulator from Problem Set 1. The important difference is this simulator runs each object in a separate thread. In the cellular automata simulator, there was only one thread, which called the getNextState method of each Cell object in the grid in turn and then updated all the cells. In the distributed simulator, each simulated object runs in a separate thread. This means several objects may be taking steps at the same time. (If we are running on a single processor machine, then the machine can only execute one instruction at a time, but we get the illusion of multiple things happening at once by interleaving the instructions from different threads.)
(The ps5.zip file also includes java/lang/Thread.spec with fixes a problem in the Thread specification included in the ESC/Java library. You should not need to edit or look at this file.)
Objects in the simulator are subtypes of the SimObject type, specified below: [an error occurred while processing this directive] Note that SimObject is an abstract class — we cannot instantiate objects of type SimObject. The abstract method executeTurn must be implemented by subtypes.
SimObject implements the Runnable interface (that is, it is a subtype of Runnable) which requires it to implement the run method. A Runnable object can be used to create a new thread using the Thread (Runnable) constructor.
For example, here is the code in the init method of SimObject.java that starts a thread for each simulated object:
   Thread thread = new Thread(this);
   thread.start();
The this object passed to Thread is a SimObject (or a subtype of SimObject). When the thread starts, it will call the run method of this object.
Race Conditions
Try running the walker simulator now. You can run the simulator by selecting Run | Run... in Eclipse, select Java Application and New. For the Main Class select WalkerSimulator. Place several RandomWalkers in the grid and click "Start". The RandomWalker is a subtype of MobleSimObject which is a subtype of SimObject.
If you start with enough objects (or are lucky), you will get some RuntimeExceptions in the Console like this:
java.lang.RuntimeException: BUG: SimObject.setLocation - row: 22 col: 27 already occupied.
	at MobileSimObject.setLocation(MobileSimObject.java:15)
	at RandomWalker.executeTurn(RandomWalker.java:47)
	at SimObject.run(SimObject.java:80)
	at java.lang.Thread.run(Thread.java:536)
Our grid allows only one object in each square, but we are getting exceptions in setLocation when a MobileSimObject attempts to wander into a cell that is already occupied. Each unhandled exception terminates the tread raising the exception, but does not shut down the application. The other threads keep executing normally.
What's going on here? A first guess might be that the RandomWalker method for executeTurn does not check if the new square is empty before moving into it. Looking at the code, however, we see that that is not the case:
public void executeTurn() throws RuntimeException
// EFFECTS: Picks a random direction and tries to move that way. 
//          If the move is successful, return true. If the move fails
//          because the spot being attempted to move into is already
//          occupied then return false.
{
    Direction dir = Direction.randomDirection();
    int newy = getY() + dir.northerlyDirection();
    int newx = getX() + dir.easterlyDirection();

    if (getGrid().validLocation(newx, newy)) {
	if (getGrid().isSquareEmpty(newx, newy)) {
	    setLocation(newx, newy);
	}
    }
}
(Note: the actual code is slightly different from this to increase the chances of observing the race condition. There is a delay before the call to setLocation.)
The code calls getGrid().isSquareEmpty (newrow, newcol) to check if the square is empty, and then setLocation (newrow, newcol) to move into the new square. But, what happens if another object moves into that square in the time between this object's isSquareEmpty test and the call to setLocation?
This is an example of a race condition — two threads are reading and writing to the same data (in this case, the Grid object square). Depending on the order in which the threads execute, the result may be different.
The way to prevent race conditions is to use locks to prevent two threads from executing critical regions of code at the same time. We would like to know that between the time this object's thread calls isSquareEmpty and the completion of the setLocation call, no other thread can alter the state of the grid. In Java, we do this using a synchronized statement:
   synchronized (expr) {
      statements
    }
The expr must evaluate to an Object reference. There is a lock associated with each object. When a synchronized statement is reached, the executing thread will evaluate expr and attempt to acquire the lock for the object it evaluates to. If the lock is available (that is, on other thread has acquired it), this thread will acquire the lock and hold it until the end of the synchronized block. Hence, any other thread that synchronizes on the same object will stall until this thread releases the lock.
Using synchronized in the method header is a short cut for synchronizing on this. So,
   synchronized public int f () { ... }
means the same thing as:
   public int f () { synchronized (this) { ... } }
5. (10) Fix the code for RandomWalker.executeTurn so that two MobileSimObjects will never go into the same square. After your fix, you should be able to run the simulation for as long as you want without ever getting an exception for two objects entering the same square.
Deadlocks
The problem with using locks to prevent race conditions, is that if there are too many locks we can have deadlock instead. The most famous toy problem used to illustrate deadlocks is the dining philosophers problem invented by Edsger W. Dijkstra. The problem involves a group of philosophers sitting around a circular table. Each philosopher has a plate of General Tso's chicken, and there is a single chopstick between each pair of philosophers. In order to eat, a philosopher must have two chopsticks. If each philosopher immediately grabs the chopstick to her right, then they will all have one chopstick but no one will be able to eat. This is a deadlock problem, since the philosophers will not put down the chopsticks until they have had a chance to eat. Hence, the philosophers sit around the table and starve.
In our experience, we find philosophers perfer not to share chopsticks, but they do like to philosophize and argue. Consider the Philosopher class shown next.
// Loosely based on Arnold, Gosling, Holmes p. 252

class PhilosopherThread implements Runnable {
	private Philosopher philosopher;
        //@invariant philosopher != null

        //@requires p != null
	public PhilosopherThread(Philosopher p) {
		philosopher = p;
	}

	public void run() {
		philosopher.philosophize();
	}
}

public class Philosopher {
	private Philosopher colleague;
	private String name;
	private String quote;

	public Philosopher(String name, String quote) {
		this.name = name;
		this.quote = quote;
	}

	public synchronized void setColleague(Philosopher p) { //@nowarn Deadlock
		colleague = p;
	}

	public synchronized void philosophize() { //@nowarn Deadlock
		System.err.println(
			name
				+ "[Thread "
				+ Thread.currentThread().getName()
				+ "] says "
				+ quote);

		if (colleague != null) { // Need a colleague to start and argument.
			colleague.argue();
		}
	}

	public synchronized void argue() { //@nowarn Deadlock
		System.err.println(
			name
				+ "[Thread "
				+ Thread.currentThread().getName()
				+ "] argues: No! "
				+ quote);
	}

	public static void main(String[] args) {
		Philosopher descartes =
			new Philosopher("Descartes", "I think, therefore I am.");
		Philosopher plato =
			new Philosopher(
				"Plato",
				"The life which is unexamined is not worth living.");

		descartes.setColleague(plato);
		plato.setColleague(descartes);

		Thread dthread = new Thread(new PhilosopherThread(descartes));
		Thread pthread = new Thread(new PhilosopherThread(plato));

		dthread.start();
		pthread.start();
	}
}
What happens when both philosophers start philsophizing at the same time?
Suppose the descartes thread runs first an invokes the philosophize method. Since it is declared with synchronized, before the method begins executing it must acquire the lock on its this object (in this case, that is the Philosopher object descartes). Then it calls the colleague.argue method. The argue method is also declared to be synchronized, so it must acquire a lock on its this object before proceeding. Here, argue is invoked on the object referenced by colleague (which is the plato object in the example). After the argue method finished, it releases the lock on plato. Then, the caller, and philosophize releases its lock on descartes.
But, what would happen if the threads executed in a different order? Suppose the descartes thread runs first and invokes the philosophize method, and then the plato thread invokes its philosophize method before the descartes thread calls colleague.argue. This is called a deadlock.
6. (10) Explain why the execution would get stuck if the threads executed in the order described.
You may want to try running the code to see what is happening more closely. To increase the chances of seeing the deadlock, insert a delay before the call to colleague.argue:
	try {
	    Thread.sleep (500); // Pause for 500 ms.
	} catch (InterruptedException ie) {
	    ;
	}
Producing multithreaded code that does not have races or deadlocks is very tricky. It is especially difficult since even if the program is tested thoroughly, the problem may appear and disapper based on what other processes running on the mahine are doing.
One way to prevent deadlocks is to follow a locking discipline. If locks are always acquired in the same order, then we know deadlock can not occur. For the Philosopher example, we could require that the lock associated with the alphabetically first philosopher is always acquired first (note that we have removed the synchronized from the method header):
    public void philosophize () {
	Object lock1, lock2;

	if (colleague != null) { // Need a colleague to start and argument.
	    // Always grab the lock for whichever name is alphabetically first
	    if (name.compareTo (colleague.name) < 0) {
		lock1 = this;
		lock2 = colleague;
	    } else {
		lock1 = colleague;
		lock2 = this;
	    }
	    
	    synchronized (lock1) {
		synchronized (lock2) {
		    System.err.println (name + "[Thread " + Thread.currentThread().getName () + "] says " + quote);
		    colleague.argue ();
		} 
	    }
	}
    }
7. (Tricky, extra credit if you can answer this) Our new Philosopher class now has a race condition that could lead to a deadlock or run-time exception (but it would never be apparent from our current main class). Explain what the race condition is, and construct code that reveals it. Feel free to insert sleep pauses as necessary to make it easier to reveal.
The provided code includes a DrunkPhilosopher class that is a subtype of the RandomWalker type from question 5. A DrunkPhilosopher object wanders around until she finds a colleague, and then starts philosophizing. Our DrunkPhilosopher suffers from a similar deadlock problem to the Philosopher code above. Try running java PhilosopherSimulator and observe what happend when two DrunkPhilosopher objects encounter each other and deadlock.
8. (10) Fix the DrunkPhilosopher class to avoid the deadlock. (Your fix should not involve removing or changing the delay calls to make the deadlock less likely.
Distributed Simulation
For the rest of this assignment, your goal is to develop an interesting distributed simulation. You can simulate anything you want.
Be creative! A good simulation will demonstrate some interesting phenomenon or help answer an important social or scientific question. You may with alone, or with any number of students of your choosing (if you can convince people not in CS201J to also contribute to your program, that is fine also, so long as you clearly document what you did).
Listed below are a few ideas for things to simulate, but you are encouraged to think of your own. The number after each idea indicates approximately how many people your team should have for it to be a reasonable project choice.

Colliding balls (1) — a few different kinds of balls bounce around the grid, and behave in interesting ways when they collide.
Epidemic (2) — create a simulation that demonstrates how a communicable disease spreads through a society.
The Lawn on a summer day (1-3) — Simulate the Lawn on a summer day. What happens when wandering students, professors, frisbee players, dogs and guided tours interact?
Pong (4) — implement the classic video game. You will need to figure out how to make object's whose behavior is controlled by the user.
Trick-or-treating (4) — simulate trick or treating on the Lawn, and determine the best strategy for maximizing the amount of candy obtained. (You can test out your strategy in the real world and compare the results.)
Traffic jam (6) — simulate traffic on I-66 (see John Calandrino's fourth year thesis)
Pacman (8)
Stock Market (20) — simulate different types buyers and sellers trading stocks. A useful simulation will provide enough information to predict future price movements in actual stocks.
Birth of the Universe (1000000) — simulate the first few nanoseconds of the Big Bang at the sub-atomic level to discover a new unifying theory of physics.
Here are some examples from last year's students:

Astrosmash by John Franchak — play the classic video game
Battle by Brian Barrett, Tucker Croft and Darnell Eaton — test your wits in this battle strategy simulator
Hunter by Spencer Stockdale — try not to starve, but beware the stalkers
Massive Epidemic by Sherlynn Hoon — will the plague destroy society?
Saturday Night by Scott Geyer — will our lonely students find their dates?
Turtles and Frogs by Joyce Lin
Have fun playing the games...but don't get too distracted from doing your own work!
9. (20) Describe what your simulation will do and your preliminary design. Include:

A short description of what your simulation will do.
A modular dependency diagram showing your design (that also shows the subtype relationships).
A brief description of your implementation and testing strategy.

Turn this in with part I. If you are working with partners, exactly one of you should turn in the full description, and the others should identify who your partners are in your answer instead.

Part 2

10. (100) Implement the simulation you described in question 9. Turn in:

A modular dependency diagram (that also shows subtype relationships) updated from what you submitted for question 9.
All the code you wrote.
A description of your implementation and testing strategy.
Hopefully your simulation will be interesting enough that you will want to share it with your friends and family! You could try and teach them to install and run the Java virtual machine, but they will be much happier if you just point them to a web page. To do this, you need to turn your application into an applet and make a web page that contains it. This is optional, but quite easy to do (see the description below). The best simulations will be presented on the CS201J web site.

Applets
So far, all the Java programs you've worked on have been applications — programs designed to run as standalone applications. It is also possible to create programs that run inside other applications, for example, inside a web browser. Java calls these applets. For a quick example, look at the PhilosopherApplet.java class to see how we turned our PhilosopherSimulator into an applet. A web page that incorporates our applet is here. To create an applet, you need to create a subtype of the java.applet.Applet type. The Applet type is a subtype of java.awt.Panel, which is a subtype of java.awt.Container, which is a subtype of java.awt.Component, which is a subtype of java.lang.Object.
If you look at the API spec for java.applet.Applet, you will see that it inherits methods from Panel (1 method), Container (47 methods), Component (56 methods) and Object (10 methods), as well as defining 25 new methods itself. So, there are 139 Applet methods! Fortunately, you can make useful applets only using a few of them directly.
In your Applet subtype, you will define replacement methods for some of the Applet methods:

public void init() — this will be called by the browser to initialize the applet.
public void start() — this will be called by the browser when the applet should start executing
public void stop() — this will be called by the browser when the applet should stop executing
public void destroy() — this will be called by the browser when the applet should perform final clean up
public void paint(Graphics g) — called when the applet display should be painted
An applet can be embedded in a web page using applet:
<html>
<body>
<applet code="MyApplet.class" width="300" height="400"></applet>
</body>
</html>
where MyApplet.class is a class that is a subtype of Applet.
(We won't cover any more HTML in this class. If you want to incorporate your applets into fancier web pages, a guide to HTML is available here: http://www.cs.virginia.edu/cs200/problem-sets/ps8/html-guide.html.)
Credits: This problem set was developed by Mike Peck and David Evans for UVA CS 2001J Fall 2002, and revised for Fall 2003 by Joyce Lin and David Evans.

University of Virginia
Department of Computer Science
CS 201J: Engineering Software

Sponsored by the
National Science Foundation

cs201j-staff@cs.virginia.edu