1. Introduction to producer and consumer model

Dining philosopher problem is a model to schedule how concurrent processes and threads as much as possible while avoid the deadlock. It contains:

5 Philosophers: represent processes or threads that consume the hardware resource

5 Chopsticks: represent 5 unit of the resources

Other concepts involved in our project:

POSIX thread: threads mechanism that satisfies POSIX standard (most operating system)

Mutex: a "lock" that guarantee that only one person has access.

Semaphore: represent one type of resource "capacity"

The mutex only has 1 capacity, 0 or 1, but Semaphore can have more than one capacity.

In this project, we use POSIX threads. The "pthread" is a POSIX thread library written in C and provides the basic functions. To avoid conflicts, we use C only in this project.

Description: There are 5 philosophers sitting around a table and try to eat from the center of the table. 5 chopsticks also lay on the table. Let us call the 5 philosophers in clockwise P1, P2, ...P5. There also 5 chopsticks clockwise S1, S2, ..., S5 on the table. There are only one chopstick between every two philosophers. Every right hand chopstick will have the same index as the philosopher. For example, on the right hand side of P1, the chopstick is called S1. And every left hand side chopstick number is 1+number of the philosopher. For example, the left hand side of P1 is the chopstick S2.

A philosopher spend random time to think, then he feel hungry and try to eat.

The middle dish can provide enough food for everyone at the same time.

But a philosopher only can start to eat when he picked up two chopsticks from left hand side and right hand side to form a pair of chopsticks.

If a philosopher take one chopsticks, he will try to fight with neighbours to get another one, and never back off to put down the one in his hand.

Once the philosopher is eating, you can not interrupt him.

Here comes the deadlock problem: when all the 5 philosophers start to pick up the right hand side chopsticks at the same time, they get stuck.

We use a mutex, every time whenever one philosor start to pick chopsticks, he lock the mutex, and he is the only guy can pick chopsticks. After he get two chopsticks, he unlock the mutex.

Notice the red lines. Between the philosopher 0 pick up chopstick 0 and 1, no other philosophers can picking up any chopstick, because the mutex is locked.

This screenshot is my result, your result may differ due to randomness.

Of course, this is not a good enough, because the food is enough for everyone. We try to make as many as possible philosophers to eat at the same time

Since the five philosopher form a cycle, to break it, we can allow only 4 philosophers at most to pick chopsticks at the same time. 4 philosophers can never form a cycle so no deadlock will happen.