This assignment is intended to continue work on process coordination by considering the problem of resource allocation and the potential for deadlock. You will again use facilities of the Unix Operating System including semaphore and shared memory primitives.
The assignment is motivated by the dining philosophers problem. You will be implementing various approaches to solving this problem and testing their potential for deadlock.
The basic idea of this assignment is to create a number of processes (philosophers) with a resource (chopstick) ``between'' each process. As discussed in class each philosopher needs two chopsticks to eat. The goal of this assignment is to explore solutions to the dining philosophers problem that avoid deadlock and starvation (literally!). Figure 1 shows a picture of this problem where each philosopher will be represented by a Unix process.
Figure: Dining Philosophers Problem
Similar to the previous assignment the parent process will create semaphores and shared memory then fork off the needed number of processes. The maximum number of philosopher processes (MAXPHIL) will be five, however the number of philosophers for a particular run of the program will be controlled on the command line. The number of chopsticks will be equivalent to the number of philosophers.
The basic objective of the project is to implement two resource allocation policies for allocation of chopsticks to philosopher processes:
A sketch of the algorithm that each philosopher process should follow for the lr policy is given below. Each chopstick should be represented by a semaphore, which must be waited upon by a process to obtain it. Thinking, eating and pausing are just time delays.
Philosopher(which)
int which; /* index of philosopher */
Resource LeftChopstick, RightChopstick;
{
while (1) {
Think; /* delay for one second */
GetResource(LeftChopstick);
/* pause for 1/10 second between picking up chopsticks */
GetResource(RightChopstick);
Eat; /* delay for one second */
ReleaseResource(LeftChopstick);
/* pause for 1/10 second between putting down chopsticks */
ReleaseResource(RightChopstick);
}
}
You can introduce time delays using the routine sleepms(), which sleeps the given number of milliseconds. Thus sleepms(100) sleeps for one-tenth of a second. The routine and code is in /cs/cs3013/public/lib/sleepms.o.
You will be using shared memory to store and monitor the status of the philosophers and their chopsticks. You should create an array for the status of the philosophers and an array for the status of the chopsticks. Each array element only needs to store a character. Hence if the number of philosophers is stored in cntPhil then the statements to create the shared status memory are (minus error checking):
char *rgPhil, *rgStick; rgPhil = (struct char *)shmcreate(cntPhil); rgStick = (struct char *)shmcreate(cntPhil);
Consequently, rgPhil[0] would access the current status of Philosopher A (process 0), rgPhil[1] for Philosopher B and rgStick[1] for the Chopstick 1. A philosopher can be in one of five states: eating, thinking, trying to acquire a chopstick, between picking up chopsticks and between releasing chopsticks. You should use the following characters to represent these states.
#define EAT 'E' #define THINK 'T' #define PICKUP 'P' #define RELEASE 'R'
For the fifth state (trying to acquire a chopstick), you should store the actual number of the chopstick (0..cntPhil-1) that the philosopher is trying to acquire.
The chopsticks can be in one of two states: free and in use. You should use the FREE state if a chopstick is unused and store the identifier of the philosopher that has acquired the chopstick if it is in use (0 for Philosopher A, 1 for Philosopher B, etc). The definition for FREE is
#define FREE -1
Your philosopher processes should continually update the status of the processes and of the chopsticks by updating the arrays in shared memory. Each process will initially be in the THINK state then just before it goes to acquire its left chopstick you should change the state in the status array to the chopstick being acquired. After it has obtained the first chopstick, change the state to PICKUP while it delays before picking up the second chopstick. When a process has obtained a chopstick, the stick status array should also be updated.
After the parent process has created all philosopher processes it should
monitor and display the status of the philosophers. To do so it will print
out on a line the current time followed by a visual representation of the
state of the system. You can obtain the current time in seconds and
microseconds by calling the Unix routine gettimeofday(). The
visual display will alternate between philosophers and chopsticks (always
represented by a `|'). When printing out the status of a
philosopher, either print the letter corresponding to the current state or
if the philosopher is trying to acquire a chopstick then print the number
of the chopstick that the philosopher is trying to acquire.
The status of Philosopher A should be printed first followed by two spaces
then a vertical bar for Chopstick 0 then two spaces and the status of
Philosopher B and so on. As an aid in the visualization, you should show a
resource graph with the philosophers and chopsticks using these two spaces
for arrows. If a philosopher has obtained a chopstick then there should be
an arrow (either `->' or `<-') from the chopstick to the
philosopher. If a philosopher is trying to acquire a chopstick then there
should be an arrow from the philosopher to the chopstick. See the sample
output for examples of printing the status.
Your parent process should print out the current status, delay for a half-second and then loop and repeat. Your parent process should print no more than 10*cntPhil number of lines. So for two philosophers you should print no more than 20 lines and no more than 50 lines for five philosophers.
In addition to simply checking the status your parent process should do deadlock detection on each loop by checking for a cycle in the resource graph. If the parent process detects deadlock then it should print that deadlock has occurred and terminate the system as described below.
Based on the discussion, here is sample output for an example of using each resource allocation policy. The command line to your program should contain the number of philosophers (2-MAXPHIL) and the resource allocation policy to use. Printing of the status is timing dependent and your output may not exactly match this output.
% dinphil 2 lr 842294804.298665 T | T | 842294804.828032 T | T | 842294805.347508 P<-| P<-| 842294805.868488 <-1<-|<-0<-| Deadlock!
% dinphil 2 hier 842294804.298665 T | T | 842294804.828032 T | T | 842294805.347508 P<-|<-0 | 842294805.868488 ->E<-|<-0 | 842294806.388581 ->E<-|<-0 | 842294806.908456 T |->E<-| 842294807.428525 T |->E<-| 842294807.958467 ->E<-| T | 842294808.478695 ->E<-| T | 842294808.998523 R<-|<-0 | ...
When the parent process has determined that the simulation has ended (either it has run long enough or deadlock has been detected), it should terminate each philosopher process by sending it a SIGINT signal using the kill() system call. In order to terminate the philosopher processes your parent process will need to remember the Unix process ids returned from CreateProcess() during process creation. After sending each termination signal, the parent process should use the wait() system call to wait for the process to exit. When all philosopher processes have been killed then the parent process should clean up semaphores and shared memory.
Satisfactory completion of the basic objective of this assignment is worth 26 of the 30 points. For four additional points, you can implement two additional resource allocation policies:
You may need to use a different number of semaphores or use them in a different way for these policies. You should retain the delays built in to the basic assignment--there is a one-tenth of a second delay between picking up the two chopsticks and between putting down the two chopsticks.