Pre-lab 6

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

Read Section 5.7.3 of your textbook (SGG), which discusses the Dining Philosophers Problem. In this problem, five philosophers are sitting around a circular table. They spend their time alternating between thinking and eating. The problem comes in how to allocate the eating utensils to the philosophers (there are 5 utensils and each philosopher needs two to eat). More on the Dining Philosophers can be found in 5.8 and Project 2 of Chapter 5.

Problem

Before going on to the most important problems in this lab, you will write a multi-threaded C program called dp.c that simulates the unconstrained version of this problem, that is, the situation in which the philosophers need no utensils to eat, as in a pie-eating contest.

You will need to two types of threads:

A) Philosopher. (15 points) Each Philosopher must be associated with one integer variable that indicates its ID. As Philosopher threads are created, they receive the ID value as a parameter in the function call. As Philosophers are prone to do, they execute a loop in which they transition across the states thinking, hungry, and eating. The Philosopher invokes a function called napping(int t) (accepts an integer parameter t), which you are going to define and which causes the thread to sleep for a random amount of time sampled in the continuous interval (0, t] — that is between 0 and t seconds (Hint: you cannot get that to happen by calling sleep(2)). Remember that once more you are working with a multi-threaded program and that you must use thread-safe functions for pseudo-random number generation.

The body of the Philosopher function should be as follows:

  • Prints message: “Philosopher ID is thinking.
  • Calls napping(2).
  • Prints message: “Philosopher ID is hungry.
  • Prints message: “Philosopher ID is starting to eat.
  • Calls napping(1).
  • Prints message: “Philosopher i is done eating.

B) Main. (15 points) This thread creates five Philosopher threads with ids numbered 0 through 4. Note that you can use a loop to start each Philosopher thread.

Hint: In order to meet the requirement of the Pthread library, your Philosopher code needs to be encapsulated in a function with the following prototype:

void * Philosopher (void *id)

Remember the function argument must be sent as a void *, even though you’re trying to send an integer. If you are working on a 64-bit machine (such as those in our labs), you may not be able to simply cast an int id variable to (void *) when you call the Philosopher function because these data type differ in bit sizes. You may have to use an integer data type that matches the bit length of the addresses (pointers) in your architecture: long long might do the trick (you should verify this by using the sizeof operator to see how many bytes are occupied by a long long).  Or, as discussed during Chapter 4 coverage, you can use struct threadarg form discussed (see “Passing Parameters to Each Thread” in programming Project 1 of Chapter 4).

Don’t forget to create a Makefile with rules to generate your executable!

When you are done with this, you need to:

  • cd ~/csci315/Labs/Lab6
  • git add Makefile
  • git add dp.c
  • git commit -m “Pre-lab 6 completed”
  • git push
Print Friendly