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

Updated for 10th edition, Stough 10/19

Set Up

Read Section 7.1.3 of your textbook (SGG, 10th edition) (5.7.3 in 9th edition), 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 — like chopsticks). More on the Dining Philosophers can be found in 7.1.3.2 (5.8) and Project 2 of Chapter 5 in 9th edition, found at the bottom of this page.

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 uniformly sampled in the continuous interval [0, t) — that is between 0 and t seconds (Hint: you cannot get that to happen by calling sleep(3), which sleeps in whole second increments, and you cannot get that to happen through usleep(3), which sleeps in microseconds up to only one second; Hint 2: napping may additionally require an unsigned int * parameter that seeds the random number generation). 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 loop inside 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, also found at the bottom of this page).

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

Grading Rubric

Problem A: The Philosopher [15 points total]

• [8 points] Set up the loop for the Philosophers correctly who transitions among the states of Thinking, Hungry, and Eating;
• [3 points] Create the napping() function correctly using seed and thread-safe random number generators;
• [4 points] Pass and reconstruct the parameter to the Philosopher() function properly.

Problem B: The main() function [15 points total]

• [8 points] Create the threads correctly by passing the right parameters to the pthread_create() function, including the parameter to the Philosopher() function;
• [4 points] Call the rest of the pthread function(s) properly;
• [3 points] Create a Makefile that can compile the programs into proper executable.

More Dining Philosophers Discussion

The following materials are excerpts from SGG book projects. They may be helpful in thinking about Dining Philosophers, including condition variables and struct parameter passing.

Project 2, Chapter 5 of 9th edition

In Section 5.7.3 (7.1.3.2 10th), we provide an outline of a solution to the dining-philosophers problem using monitors. This problem will require implementing a solution using Pthreads mutex locks and condition variables.
The Philosophers
Begin by creating five philosophers, each identified by a number 0 . . 4. Each
philosopher will run as a separate thread. Thread creation using Pthreads is
covered in Section 4.4.1. Philosophers alternate between thinking and eating. To simulate both activities, have the thread sleep for a random period between one and three seconds. When a philosopher wishes to eat, she invokes the function

pickup forks(int philosopher_number)

where philosopher number identifies the number of the philosopher wishing
to eat. When a philosopher finishes eating, she invokes

return forks(int philosopher_number)

Pthreads Condition Variables
Condition variables in Pthreads behave similarly to those described in Section 5.8 (6.7.1 10th). However, in that section, condition variables are used within the context of a monitor, which provides a locking mechanism to ensure data integrity. Since Pthreads is typically used in C programs—and since C does not have a monitor— we accomplish locking by associating a condition variable with a mutex lock. Pthreads mutex locks are covered in Section 5.9.4 (7.3.1 10th). We cover Pthreads condition variables here (and 7.3.3 10th).

Condition variables in Pthreads use the pthread_cond_t data type and
are initialized using the pthread_cond_init() function. The following code
creates and initializes a condition variable as well as its associated mutex lock:

pthread_mutex_t mutex;
pthread_cond_t cond_var;

pthread_mutex_init(&mutex,NULL);
pthread_cond_init(&cond_var,NULL);

The pthread_cond_wait() function is used for waiting on a condition
variable. The following code illustrates how a thread can wait for the condition a == b to become true using a Pthread condition variable:

pthread_mutex_lock(&mutex);
while (a != b)
    pthread_cond_wait(&mutex, &cond_var);

pthread_mutex_unlock(&mutex);

The mutex lock associated with the condition variable must be locked
before the pthread_cond_wait() function is called, since it is used to protect
the data in the conditional clause from a possible race condition. Once this
lock is acquired, the thread can check the condition. If the condition is not true, the thread then invokes pthread_cond_wait(), passing the mutex lock and the condition variable as parameters. Calling pthread_cond_wait() releases the mutex lock, thereby allowing another thread to access the shared data and possibly update its value so that the condition clause evaluates to true. (To protect against program errors, it is important to place the conditional clause within a loop so that the condition is rechecked after being signaled.)

A thread that modifies the shared data can invoke the pthread_cond_signal() function, thereby signaling one thread waiting on the condition variable. This is illustrated below:

pthread_mutex_lock(&mutex);
a = b;
pthread_cond_signal(&cond_var);
pthread_mutex_unlock(&mutex);

It is important to note that the call to pthread_cond_signal() does not
release the mutex lock. It is the subsequent call to pthread_mutex_unlock()
that releases the mutex. Once the mutex lock is released, the signaled thread
becomes the owner of the mutex lock and returns control from the call to
pthread_cond_wait().

Passing Parameters to Each Thread (part of Project 1, Chapter 4, 9th edition)

The parent thread will create the worker threads, passing each worker the
location that it must check in the Sudoku grid. This step will require passing
several parameters to each thread. The easiest approach is to create a data
structure using a struct . For example, a structure to pass the row and column where a thread must begin validating would appear as follows:

/* structure for passing data to threads */
typedef struct
{
   int row;
   int column;
} parameters;

Both Pthreads and Windows programs will create worker threads using a
strategy similar to that shown below:

parameters *data = (parameters *) malloc(sizeof(parameters));
data->row = 1;
data->column = 1;
/* Now create the thread passing it data as a parameter */

The data pointer will be passed to either the pthread_create() (Pthreads)
function or the CreateThread() (Windows) function, which in turn will pass
it as a parameter to the function that is to run as a separate thread.