Solving the Dining Philosophers Problem with Mutex Locks and C Programming
Introduction
The Dining Philosophers Problem, originating from Edsger Dijkstra as a thought experiment in 1965 is one of computer science’s enduring challenges. It is often used to illustrate the challenges of allocating limited resources among multiple processes in a concurrent system. It provides a vivid scenario to explore the fundamentals of process synchronization and concurrency within computer science.
Understanding the Problem
Description: X amount of philosophers sit at a round table with bowl of food. Forks are placed in front of each philosopher. There are as many forks as philosophers. All day the philosophers take turns eating, sleeping, and thinking. A philosopher must have two forks in order to eat, and each fork may only be used by one philosopher at a time. At any time a philosopher can pick up or set down a fork, but cannot start eating until picking up both forks. The philosophers alternatively eat, sleep, or think. While they are eating, they are not thinking nor sleeping, while thinking, they are not eating nor sleeping, and, of course, while sleeping, they are not eating nor thinking.
Challenges Faced: The challenge is to design a system where each philosopher can think, eat and sleep without starvation. The main challenges include deadlock, where philosophers wait on each other indefinitely for forks, and starvation, where a philosopher never gets enough resources to eat. Race conditions can also occur, complicating the synchronization of thread operations.
Technical Setup
Tools and Technologies Used: This solution was implemented in C as part of 42 Projects, using POSIX threads (pthreads) for handling multiple philosophers simultaneously and mutexes for managing access to the forks.
Environment Setup: The solution is developed on a Linux system, utilizing GCC for compilation with flags for thread safety and performance optimization.
Before getting into the implementation details let us look at the basis of programming to understand what a process, thread is.
Process vs Thread
Building a house is a process, but the people doing the work to install the pipes, paint the walls and do the electrical work are all the working threads within the process of building the house.
I like to use threads synonymously with “unit of work” or “thing that executes a specific piece of work / action for the process to complete successfully.
So if I run chrome, and have 10 tabs open, I will have 10 processes running. Within each process are 1 or many units of work (called threads) responsible for memory management, access, logic, etc.
Processes are isolated executable files in memory, while threads are units of execution within those processes sharing memory space.
Summary
🖥️ Program Definition: A program is an executable file containing processor instructions. Recognizing that a program is merely a file until executed helps clarify the transition to processes, emphasizing the importance of execution context.
🚀 Process Creation: When a program is executed, it becomes a process and requires resources managed by the OS.
🔒 Process Isolation: Each process has its own memory address space, preventing corruption by other processes.
🧵 Thread Function: A thread is a unit of execution within a process, with its own stack but sharing memory space with other threads.
⚙️ Context Switching: The OS uses context switching to manage process and thread execution on the CPU, which is resource-intensive.
⏩ Efficiency of Threads: Context switching is faster between threads than processes due to shared memory, reducing overhead.
🔄 Alternative Scheduling: Mechanisms like fibers and coroutines minimize context switching costs by allowing applications to manage scheduling.
🔗 Memory Protection: Process isolation is vital for system stability, particularly in multi-process applications like web browsers, which utilize this to enhance user experience.
🧩 Threads vs. Processes: Understanding that threads share memory space while processes don’t is key for developers in designing efficient applications and managing data.
Common Issues in Thread Programming
When working with threads in C, there are several common issues that programmers may encounter. These include:
- Race Conditions: A race condition occurs when two or more threads can access shared data and they try to change it at the same time. Because the thread scheduling algorithm can swap between threads at any time, you don’t know the order in which the threads will attempt to access the shared data. Therefore, the result of the change in data is dependent on the thread scheduling algorithm, i.e. both threads are “racing” to access/change the data.
- Deadlocks: Improper handling of resource acquisition and release can lead to deadlocks, where threads are stuck indefinitely waiting for each other. Deadlocks happen when we lock the same mutex twice or more or more often due to the order in which the mutexes are locked and unlocked.
- Resource Management: Managing shared resources such as memory or file handles among multiple threads requires careful coordination to avoid conflicts and corruption.
- Synchronization: Coordinating the execution of multiple threads to ensure correct program behaviour often involves the use of synchronization primitives like mutexes, semaphores, and condition variables.
- Performance Overhead: Creating and managing threads can introduce overhead in terms of memory and CPU usage, impacting the overall performance of the application if not managed efficiently.
- Debugging Challenges: Debugging multi-threaded programs can be challenging due to the non-deterministic nature of thread execution and timing-dependent bugs.
- Platform Dependency: Thread behaviour may vary across different operating systems and platforms, requiring platform-specific considerations for thread programming.
Key Implementation Details
- Thread Management: Each philosopher is represented as a thread. This parallelism simulates the simultaneous actions of thinking, eating, and sleeping.
- Mutex Usage: Mutex locks are crucial. Each fork has an associated mutex to ensure that no two philosophers can hold the same fork at the same time, thus preventing deadlock.
- State Management: I maintained the state of each philosopher (eating, thinking, sleeping) using shared variables protected by mutexes, ensuring that changes in state were mutually exclusive among threads.
- Monitoring and Control: A separate monitoring thread checks continuously to ensure no philosopher is starved and the program can terminate correctly once all philosophers have eaten sufficiently or when one of the philosopher dies.
🔑 Simulating Deadlocks: Introducing delays can help demonstrate deadlocks in a controlled manner, useful for educational purposes and debugging.
🔑 Preventive Measures: Standardizing lock acquisition order across threads can significantly reduce the risk of deadlocks in complex applications.
Core Functions Explained
- Checking Philosophers’ Status
char control_simu(t_rcs *data)
{
int i;
i = 0;
pthread_create(&data->monitor, NULL, monitor_routine, (void *)data);
while (i < data->num_philo)
{
if (pthread_create(&data->philos[i].thread, NULL, philo_routine,
(void *)&data->philos[i]) != 0)
{
printf("\\033[0;31mFailed to create philosopher thread\\033[0m \\n");
return (0);
}
i++;
}
join_threads(data);
return (1);
}It begins by creating a monitoring thread that oversees the entire simulation, ensuring conditions like starvation or task completion are appropriately handled. Then, individual threads for each philosopher are spawned, each executing a routine that simulates the philosopher’s activities such as eating, thinking, and sleeping. If any thread fails to initiate, an error is reported, and the function exits with failure. After initializing all philosopher threads and the monitor thread, join_threads(data) is called to ensure that the main thread (typically the one running main()) waits for all other threads to complete before proceeding. This is essential to prevent the program from exiting prematurely and to ensure all resources are properly released.
2. Action: Eating
void eating(t_philo *philo)
{
if (philo->id % 2)
{
pthread_mutex_lock(philo->right_fork);
log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
pthread_mutex_lock(philo->left_fork);
log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
}
else
{
pthread_mutex_lock(philo->left_fork);
log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
pthread_mutex_lock(philo->right_fork);
log_action("has taken a fork", philo->id, philo->s_data, "\\033[0;32m");
}
ft_start_eating(philo);
log_action("is eating", philo->id, philo->s_data, "\\033[0;34m");
precise_sleep(philo->eat_time);
pthread_mutex_unlock(philo->left_fork);
pthread_mutex_unlock(philo->right_fork);
pthread_mutex_lock(&philo->s_data->meal_lock);
philo->eating = 0;
philo->meals_eaten++;
pthread_mutex_unlock(&philo->s_data->meal_lock);
}
Philosophers with odd IDs first pick up the right fork and then the left, while those with even IDs do the opposite, preventing a circular wait condition that could lead to deadlock. Once both forks are secured, the philosopher is logged as eating, and the action is timed to simulate the duration of the meal. After eating, the forks are released in the opposite order they were picked up to further minimize potential deadlocks. Finally, the meal’s completion is recorded under the protection of a meal_lock mutex to safely update the shared state variables eating and meals_eaten, ensuring that these critical sections are not accessed concurrently by other threads, thus maintaining data integrity throughout the simulation.
3. Logging Actions
void log_action(char *action, int i, t_rcs *data, char *color)
{
unsigned long timestamp;
pthread_mutex_lock(&data->logging);
timestamp = get_time_ms() - data->philos[i -1].start_time;
pthread_mutex_lock(&data->death_lock);
if (data->dead != 1)
{
printf("%lu %s%d %s\\033[0m\\n", timestamp, color, i, action);
}
pthread_mutex_unlock(&data->death_lock);
pthread_mutex_unlock(&data->logging);
}The function first locks the logging mutex to prevent other threads from writing simultaneously, ensuring that log entries are not interleaved and remain readable. It then calculates the time elapsed since the start of the simulation for that particular philosopher. Another lock, death_lock, is used to check if the simulation is still active before logging the action. This dual-lock mechanism ensures that actions are only logged when the philosopher is active and the simulation has not been terminated.
4. Precise Timing
This function marks the start time and continuously checks against the current time until the desired duration has passed, pausing execution in very short intervals (0.5 milliseconds) to prevent the thread from monopolizing CPU resources.
void precise_sleep(unsigned long duration)
{
unsigned long start;
start = get_time_ms();
while (get_time_ms() - start < duration)
{
usleep(500);
}
}
Challenges and Solutions
Challenge 1: Circular Wait Condition
- Problem Faced: The circular wait condition arose when each philosopher attempted to pick up the left and right forks in no particular order. This issue could lead to a deadlock, where all philosophers hold one fork and wait indefinitely for the other, preventing any philosopher from eating.
- Solution Implemented: To prevent this deadlock scenario, a strict order was enforced in which philosophers pick up their forks. Philosophers with odd IDs first pick up the right fork and then the left, while those with even IDs do the opposite. This strategy breaks the cycle of circular wait and effectively prevents deadlock.
Challenge 2: Favouritism in Fork Acquisition
- Problem Faced: Some philosophers were favoured in terms of accessing forks due to their position at the table or the sequence of actions, leading to unfair resource allocation where some philosophers would always pick up the fork first, they would finish eating and then pick up the fork to eat again immediately.
- Solution Implemented: The solution involved implementing an algorithm that considers fairness; each philosopher must put down their forks and wait a random minimal duration before attempting to pick them up again if they were not successful in their first attempt. This randomized delay reduces the chance of favoritism and ensures that all philosophers get an equal opportunity to eat.
Challenge 3: Delayed Death Logging
- Problem Faced: The simulation had an issue where a philosopher’s death would only be logged after they had completed their full sleep cycle or finished eating, which could misleadingly suggest that the philosopher was alive for longer than actually was the case.
- Solution Implemented: To address this, the monitoring system was refined to check the status of philosophers more frequently and independently of their eating or sleeping cycles. The implementation of a dedicated monitoring thread allowed for immediate recognition and logging of a philosopher’s death, thus ensuring that death events are recorded and handled promptly and accurately.
Running the program
Check and run the code
git clone
make
./philo 5 610 200 200 3
or
valgrind --tool=helgrind ./philo 5 610 200 200*All time in milliseconds
./philo [number_of_philosophers] [time_to_die] [time_to_eat] [time_to_sleep] [number_of_times_each_philosopher_must_eat(optional)]
**Helgrind is a Valgrind tool for detecting synchronisation errors in C, C++ and Fortran programs that use the POSIX pthreads threading primitives.
Mood Check
- What is a thread even?😲
- Deadlocks! 😣
- Finally they follow a routine 😴🍽️🤔
Reflections
The real-world applications of such a solution are vast, particularly in operating systems and database transaction systems, where resource allocation must be managed meticulously to prevent deadlocks and ensure fairness.
Feel free to share your thoughts, experiences, or any questions in the comments below! Whether you are a student grappling with similar problems or an experienced developer with insights to share, I look forward to your feedback and discussion.
References and tools
Play and try: Interactive Explanation
Visualizer : visualizer
