The dining philosophers is a classic synchronization and concurrency problem in computer science, formulated by Dijkstra in 1965. The problem is as follows:

• There are one or more philosophers at a dining table
• The philosophers will eat, sleep and think sequentially
• There are forks on the tables, equivalent to the number of philos
• Philosophers are required to pick up two forks to start eating
• Philosophers are not allowed to communicate with each other
• If a philo does not start eating within their assigned time to die, they die

This was a project completed in 42 school to learn about multithreading and mutexes. The goal is to implement and run a simulation in which philosophers can eat, sleep and think without race conditions and deadlocks.

What are POSIX threads (pthreads)?

Pthreads is a C library that allows for managing and running multiple threads concurrently. This allows for multiple tasks to run simultaneously; in the philosophers’ case, multiple philosophers can eat at the same time, while having a separate thread to monitor the philosophers’ statuses.

Here’s an example of a simple program using pthreads:

In this program, a thread is created and counts to hundred while printing its i-th value. The main runs a loop that prints “hello from main” a hundred times.

In sequential programming, instructions follow a single thread of execution, and are executed in the order they are specified; we would expect i to be printed one hundred times before “hello from main” starts printing. On the other hand, concurrent programming allows both threads to run functions concurrently. Hence, the output could be interspersed as such:

Data races – What are they?

Now that we have a base understanding of ptheads, let’s go over a common issue in multithreaded programming – data races. Data races occur when threads access and modify the same data simultaneously, which can lead to inaccurate results. Here are the conditions for data races:

• Multiple threads access the same memory location concurrently
• At least one thread is modifying the data
• Insufficient protection, resulting in unsynchronized access

Here’s an example of how data races can occur in the philosophers problem – A philosopher’s death flag is set to true, indicating that the philosopher has died. If the philosopher’s thread accesses its death flag before the modification, the simulation may continue running incorrectly. We can resolve this using mutex locks.

Preventing data races using mutex locks

Mutex locks (mutual exclusion locks) are synchronization functions that allow for locking and unlocking shared resources, to prevent other threads from accessing the data concurrently. When a mutex is locked, other threads will need to wait for it to be unlocked by the same thread.

The code below illustrates the use of mutexes; there are four threads updating a counter. A mutex is initialized. The mutex is locked before each thread increments the counter, and unlocked after incrementing. Hence, the mutex protection ensures that the final counter value will be 40,000. At the end of the program, the mutex is destroyed.

Avoiding deadlocks

Finally, let’s discuss deadlocks. Deadlocks occur when every philosopher picks up one fork and are waiting for the other fork; these four conditions create a deadlock.

1. Mutual exclusion – Fork can only be held by one philosopher at a time
2. Hold and wait – Philosopher holds one fork while waiting for the other
3. No preemption – Philosopher can only release fork voluntarily
4. Circular wait condition – Philosophers wait for the other fork that the next philo in the chain holds

My initial solution was to introduce a wait time to stagger the precedence in which philosophers pick up their forks. By doing this, odd-indexed philosophers pick up their forks and start eating before even-indexed philosophers. This aims to break the circular wait condition. However, the solution does not guarantee prevention of deadlocks throughout the runtime. Here are other potential (more effective) strategies:

• Introduce a server/arbitrator to manage the number of philosophers allowed to hold forks simultaneously
• Require philosophers to pick up both forks; if they are unable to pick up the second fork, they will need to drop the first fork and wait before re-trying
• Set a resource hierarchy such that philosophers do not pick up forks in a circular-dependent order

If you have any suggestions or alternative solutions, feel free to leave a comment (or drop me a slack if you’re a 42 student).

Hope this helps, and thanks for reading!

Resources

Introduction to PThreads
Mutex lock for Linux Thread Synchronization
Tutorialspoint: Mutex locks
Dining Philosophers Problem and Deadlock