CSCI.4430/6969 Programming Languages Spring 2005
Programming Assignment #4

This project is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TAs or the instructor. You are encouraged to use the WebCT Discussions page to post problems so that other students can also answer/see the answers.

The goal of this assignment is to become knowledgeable with concurrent and distributed programming issues using the SALSA programming language.

Part 1 - Dining Philosophers Problem

Consider the famous Dinning Philosophers problem. A round table holds n forks and a bowl of spaghetti. Each fork is placed between two seats. The table seats n philosophers, each of whom eats for a while, then thinks for a while, then eats and so on. Each philosopher requires two forks-the ones on the left and right- to eat, but releases them when thinking. The main problem is that without some kind of coordination the philosophers could starve when they pick up their left forks and then block forever trying to pick up the right forks which are being held by other philosophers.

A solution described by Hoare adds the requirement that at most n-1 philosophers are allowed to be seated at once.  This ensures that at all times, at least one philosopher can eat, so there are no deadlocks. One way to implement this solution is to assume that there is a bouncer that does not allow a philosopher to sit if there are already n-1 philosophers sitting.

Algorithm for philosopher:

Loop forever {
  Make sure it is okay to sit (check with bouncer).
  Sit.
  Pick up the fork on the left.
  Pick up the fork on the right.
  Eat.
  Release the fork on the left.
  Release the fork on the right.
  Stand.
  Think.
}
When your program is run, it should be given the philosopher names (for n > 1 philosophers) as command line arguments and generate verbose output explaining what is happening, for example:
--> salsa Party Plato Socrates Aristotle Demosthenes
Plato sits.
Socrates sits.
Aristotle sits.
Socrates picks up the left fork.
Socrates picks up the right fork.
Plato picks up the left fork.
Socrates eats.
Socrates releases the left fork.
Socrates releases the right fork.
Aristotle picks up the left fork.
Socrates stands up.
Demosthenes sits.
Socrates thinks.
Plato picks up the right fork.
...

Part 2 - Nomad Dining Philosophers

The second part of the assignment deals with distributed programming.   The nomad dining philosophers use multiple different lounges to eat and think.  We assume that there is a main dining lounge containing the table; other locations are thinking lounges.  Philosophers may only eat at the dining lounge, and may only think in a thinking lounge.  The bouncer stands at the door of the dining lounge, and has a number of jobs:

Extra Credit - Lounge Failures (10% bonus if working individually, required for full credit if working in a pair.)

The last part of the assignment (extra-credit) deals with failures.  Lounges can be sent soft-failures and hard-failures. You will need a manager for each lounge to receive these failure messages.  The following pseudo-code provides potential algorithms to model failures:
softFailure()
  Don't allow any other philosophers to enter the lounge.
  For each philosopher p in the room
    Tell p to leave.
  After all have left, allow philosophers to enter again.
hardFailure()
  Don't allow any other philosophers to enter the lounge.
  For each philosopher p in the room
    Kill p.
  After all have been killed, allow philosophers to enter again.
The bouncer should then check periodically if all philosophers are still alive (using a heart-beating protocol). If not, he/she should generate new philosophers so that there are always n philosophers in the system.

You may also want to give a time argument to these failures, so that the failure (or time-bomb) does not happen until that time has elapsed.

Other Possible Extensions


Due Date:
 
Received Time Grade Modification
before Monday, May 2, 11:59PM +10%
before Tuesday, May 3rd, 11:59PM no modification (on time)
before Wednesday, May 4th, 11:59PM -10%
from Thursday, May 5th, 12:00AM to 
Friday, May 6th, 11:59PM
-25%
after Saturday, May 7th, 12:00AM not accepted

Grading: The programs will be tested on the CS network version of SALSA. The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!).  See the professor or TAs, if you have ideas for other extensions for this assignment and would like extra credit for implementing them.

Submission Requirements: Please submit a ZIP file with your code, including a README file. In the README file, place the names of each group member (up to two). The README should also clearly describe how to compile and run the code, as well as explaining your architecture and any design decisions made. Your code will be tested on the CS machines, so make sure it works there.  Your ZIP file should be named with your WebCT user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair via WebCT.