This project is to be done individually or in pairs. Do not show your code to any other student/group and do not look at any other student/group's code. Do not put your code in a public directory or otherwise make it public. You are encouraged to use the LMS Discussions page to post problems so that other students can also answer and see the answers.

The goal of this assignment is to practice concurrent and distributed programming using the SALSA programming language.

Consider the famous Dinning Philosophers problem. A round table holds n chopsticks and a bowl of spaghetti. Each chopstick 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 chopsticks-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 chopsticks and then block forever trying to pick up the right chopsticks which are being held by other philosophers.

Part 0 - Dining Philosophers Problem

You are to create a program in SALSA that will demonstrate that deadlock may occur.  That is, you are to create a program in which philosophers will eventually starve to death after all picking up their left chopsticks.

Algorithm for philosopher:

Loop forever {
  Pick up the chopstick on the left.
  Pick up the chopstick on the right.
  Eat.
  Release both chopsticks.
  Think.
}

Part 1 - Dining Philosophers Solution

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. This solution assumes there is a bouncer that does not allow a philosopher to sit if there are already n-1 philosophers sitting.  You are to write a program simulating this solution.  Your program should generate verbose output explaining what is happening.

Part 2 - Nomad Dining Philosophers

The last 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:

• When a philosopher wants to enter the dining lounge and there are less than n-1 philosophers in the room, the philosopher is let in and may sit in the table.
• When a philosopher wants to enter the dining lounge and there are already n-1 philosophers in the room, the bouncer chooses a thinking lounge at random for the philosopher to go to.
• When a philosopher leaves the dining lounge, the philosophers checks out with the bouncer and the bouncer chooses a random thinking lounge for the philosopher to go to.

You are to write a simulation of the nomad dining philosophers in SALSA.

Extra Credit - Lounge Failures

The extra-credit part of the assignment 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 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

• Provide an additional solution to deadlock (other than Hoare's solution).
• Prove or disprove that your solution is fair (that is, all philosophers get to eat and think periodically).

Submission:

The due date for this project is November 11, 2009, 11:59pm EST. You should use the assignments drop-off box located at the course's LMS page. Upload a ZIP file containing all the relevant documented SALSA files, along with a README file describing the project and its usage.  24-hour late submissions will receive a 10% grade penalty, 3-day late submissions will receive a 25% penalty.  Assignments will not be received after November 14th, 2009.