Dining Philosophers

Goals

• Develop a deep understanding of the classic problem.

Credits

This lab was developed by CSCI 315 staff and modified by Prof. L. Felipe Perrone. Permission to reuse this material in parts or in its entirety is granted provided that this credits note is not removed. Additional files associated with this lab, as well as any existing solutions can be provided upon request by e-mail to perrone[at]bucknell[dot]edu

Set Up

In your git repo, create a directory for today’s lab called Lab6. In this directory, create a file called answers.txt, where you’ll write answers in text for some of the problems in this lab.

It goes without saying that you need to create a Makefile instrumented to build each and every one of the executables in this lab. Failing to do that will lose you 10 points for the lab.

Problem 1 (30 points)

The standard statement of Dining Philosophers is a resource allocation problem. As in the version for pre-lab problem, it consists of five philosophers sitting around a table and cycling through the states thinking, getting hungry, and eating.

Philosophers need chopsticks in order to eat. Between each pair of philosophers, there lies one single chopstick. When a philosopher wants to eat, s/he must acquire two chopsticks; that is, s/he must try to get exclusive access to the chopstick on the left and also to the one on the right. Effectively, this means that no two neighboring philosophers can ever eat at the same time. A complicating factor is that when a philosopher want to eat, s/he must request each chopstick separately, that is, one at a time.

For this problem, you will create a program called problem1.c, which implements your solution to the dining philosophers problem. In this program, you will use the mutex and semaphore constructs, which have used before. Each chopstick must be modeled by a mutex and each philosopher by a thread.

The Philosopher threads request chopsticks by doing two successive locks: one for the chopstick on the left and one for chopstick on the right. Once a  Philosopher passes through the wait on a mutex, it is assumed to have picked up the corresponding chopstick. Since a Philosopher must pick up both the left and the right chopsticks in order to be able to eat, you can think of the “eating” section as the critical section of the Philosopher‘s code.

Your implementation must follow the guidelines below, which are consistent with the solution in the SGG textbook:

• You must have an array chopsticks[] of five mutexes, which is visible to all Philosopher threads and correctly initialized.
• Modify your Philosopher thread so that it works with the chopsticks[] array of mutexes.
• Each Philosopher thread will make calls to pthread_mutex_lock and pthread_mutex_unlock to simulate picking up and putting down chopsticks. You should use the following scheme for numbering the chopsticks: the chopstick to the left of Philosopher i is numbered i, while the chopstick to the right is numbered (i+1)%5 (remember that Philosopher 0 is to the “right” of Philosopher 4).

Your solution to this week’s pre-lab may have been created to pass into each Philosopher thread a philosopher’s numeric id as a parameter to the thread function. This will allow the creator of the threads to assign the id of each thread when it invokes pthread_create for each individual philosopher. If your solution did not already incorporate this tactic, you should modify it before you start on this lab. When each philosopher knows its id, the messages it will print can include that id value and therefore you will be able to distinguish which messages come from which philosopher.

Compile and run the resulting program.

• Once your implementation is correct, you should observe that no two consecutive philosophers are eating at the same time. (20 points)
• At that point, redirect the output of your program to a file called problem1.out, as indicated below, let it run for a few seconds and terminate it with Ctrl-C. (Verify that the file contains enough output for one to see that your implementation works as expected.) In case you haven’t used I/O redirection in Unix, this is what you have to do to send the standard output of your program to a file:

./problem1 > problem1.out

Hint: When you look at your problem1.out file, you might not see any output. If that is the case, think about whether you are using buffered output. It could be that your program is writing to output buffers that are not being flushed and when you kill the program with Ctrl-C, the file turns out to be empty. Remember that you can force the buffers to be flushed in your program, which will avoid this issue.

By submitting your output file, you earn (4 points). Not submitting this file can potentially compromise the grader’s ability to assess your solutions, so don’t take any chances.

In your file answers.txt, include answers to the following questions:

1.1 Run your code for about 10 seconds. Do you observe any problems when your program runs? Report what you observe. (3 points)

1.2 Based on your understanding of the code, how could deadlock possibly happen? (Hint: reason through all the four conditions to deadlock occurrence and explain if they all apply.) (3 points)

When you are done with this, you need to:

• cd ~/csci315/Lab6
• git add Makefile
• git add problem1.c
• git add problem1.out
• git add answers.txt
• git commit -m “Lab6, problem 1 completed”
• git push

Problem 2 (20 points)

The standard solution for dining philosopher can potentially run into deadlock. In this problem, you will try to simulate deadlock to verify first-hand what happens.

Look closely at the code in problem1.c and identify where deadlock might occur. Keep in mind that deadlock is not so much related to some static sequence of statements in the code; it is due to the manifestation of a sequence of events observed at run time.

Copy your program problem1.c, to a new file called problem2.c. Remember the napping() function you created for your prelab assignment? In your Philosopher function, add calls to napping() to try to encourage deadlock to occur. Feel free to modify the list of arguments of your napping() function as you see fit, but add comments to the function explaining what each parameter is for. Some students, for instance, have chosen to pass into napping() a pointer to the variable that stores the random number generator seed for the specific thread that is calling this function.

Experiment with where to insert these calls and also with the lengths of naps until you do observe deadlock in your test runs. (12 points)

So that you can see the behavior of Philosophers at run time, after each pthread_mutex_lock call, add a message saying:

“Philosopher i picking up chopstick j”

Similarly, after each pthread_mutex_unlock, add a message saying:

“Philosopher i putting down chopstick j”

Note: Once you can cause deadlock to happen, it’s a good idea to run the program again a number of times to see if the behavior might change. With good choices of when to nap and of the length of naps, you will see that sometimes your program deadlocks quickly and sometimes it will run for a while without deadlocking. This will serve as proof that deadlock is the result of a particular sequence of events: having the potential for deadlock in your code is not a guarantee that it will occur. The non-deterministic nature of deadlock occurrence can make debugging really difficult.

When your program runs into deadlock, save its execution to a file called problem2.out. You can do this with cutting and pasting the output to a file, or alternatively, take your chances and use I/O redirection (just make sure that the file you generate does show deadlock!)

Your submission of the program’s output earns you (4 points). Not submitting this file could potentially compromise the grader’s ability to assess your solutions, so don’t take any chances.

In your file answers.txt, include the answer to the following question:

When you are done with this, you need to:

• cd ~/csci315/Lab6
• git add problem2.c
• git add Makefile
• git add problem2.out
• git add answers.txt
• git commit -m “Lab6, problem 2 completed”
• git push

Problem 3 (20 points)

If the behavior of Philosphers is perfectly symmetrical, it is quite likely that you will observe deadlock. In general, symmetric behavior occurs when similar threads consistently make the same choices. While in some cases this isn’t a problem, in other cases it will lead to deadlock.

Problems with symmetrical behavior are common in computer science. Parallel algorithms where multiple processes or threads act on a set of common resources tend to exhibit this kind of behavior. For this reason, it is important to develop strategies to break symmetry.

In parallel algorithms, a common technique is to apply randomness at the point of symmetry. For example, individual processes can each flip a coin (or the computational equivalent), then decide what to do based on the result. We could do this in the Dining Philosophers solution, and greatly decrease the probability of deadlock occurrence. (In this case, each Philosopher thread could sample a random number to decide which chopstick to pick up first.) Unfortunately, the use of randomness only reduces the probability of symmetric behavior; it does not eliminate it altogether. We need to be extra careful with the possibility of deadlock.

One way to break symmetry in the Dining Philosophers is to make different Philosopher threads behave differently. There are a couple of obvious possibilities:

1. Each Philosopher thread can pick up its right chopstick first, if its id number is odd, otherwise it picks up its left chopstick first. Copy your problem2.c to a file called problem3-1.c, where you will implement this solution. (8 points)
2. Each Philosopher thread picks the lowest-numbered chopstick it needs first. Copy your problem2.c to a file called problem3-2.c, where you will implement this solution. (8 points)

In both of the new implementations above, make sure to leave in the napping() calls that produced the deadlock in your Problem 2 solution. Compile and run each of your solutions until you convince yourself that they run without deadlocking.

In your file answers.txt, include the answer to the following question:

3.1 Discuss whether these solutions eliminate all the potential causes of deadlock. If you conclude that they don’t, indicate what problem(s) can still occur. (4 points)

When you are done with this, you need to:

• git add problem3-1.c
• git add problem3-2.c
• git add Makefile
• git add answers.txt
• git commit -m “Lab6, problem 3 completed”
• git push

Hand In

Before turning in your work for grading, create a text file in your Lab 7 directory called submission.txt. In this file, provide a list to indicate to the grader, problem by problem, if you completed the problem and whether it works to specification. Wrap everything up by turning in this file:

• git add ~/csci315/Labs/Lab6/submission.txt
• git commit -m “Lab 6 completed”
• git push