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.
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.
Make sure it is okay to sit (check with bouncer).
Pick up the fork on the left.
Pick up the fork on the right.
Release the fork on the left.
Release the fork on the right.
Socrates picks up the left fork.
Socrates picks up the right fork.
Plato picks up the left fork.
Socrates releases the left fork.
Socrates releases the right fork.
Aristotle picks up the left fork.
Plato picks up the right fork.
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.
Don't allow any other philosophers to enter the lounge.
After all have left, allow philosophers to enter again.
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.
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).
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.