CSCI 6500 PA4

CSCI.6500 Distributed Computing over the Internet

Spring 2006

Programming Assignment #4

This assignment 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. While you may get help directly from the instructor, you are encouraged to use the WebCT 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 JOCAML 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.

Part 0 - Dining Philosophers Problem

You are to create a program in Jocaml that demonstrates 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 forks.

Algorithm for philosopher:

Loop forever {
  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.
  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 Jocaml.

Extra Credit - Lounge Failures (Required if working in a pair)

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/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

Provide an additional solution to deadlock (other than Hoare's solution).
Write a mobile ambients implementation of the dining philosophers using the Ambient calculus implementation provided in the Jocaml distribution.
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 April 19th, 2006, 11:55pm EST. You should use the assignments drop-off box located at the course's WebCT page. Upload a ZIP file containing all the relevant documented Jocaml 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 April 22th, 2006.