Dining Philosophers Problem in Operating System (OS)
Dining Philosophers in Operating System
Dining Philosophers in operating system essentially is a process synchronization example and helps understand how we can simultaneously utilise common resources of multiple processes together.Entities –
- Noodles/Rice
- Chopsticks
- Philosophers
At any given instance, a philosopher will do –
- Thinking
- Eating
- Whenever the philosophers want to eat. He obviously will use two chopsticks together.
- So to eat both chopsticks on his right and left must be free.
- Whenever he is thinking
- He must put down both the chopsticks back at the table.
In this case they will wait indefinitely for their 2nd chopstick(right chopstick) and the deadlock will be there forever.
Rules and Solution
If a philosopher decides to eat
- He first will wait for the chopstick on his left to be free.
- If the left chopstick is already free he will pick that up.
- Then he will wait for the chopstick on his right
- And once the right chopstick is also free he will pick that up too and do the eating.
Some of the ways to avoid deadlock are as follows:
Four Philosopher
There should be at most four philosophers on the table. In this way one chopstick will be extra if all decide to eat together. This one chopstick then can be used by one of our philosopher and he will finish his eating and then two chopsticks are available then 1 more can eat and so on…
Even Odd
Solving with even and odd techniques, even philosopher must pick his right and off must pick his left.
Coordination
Only and only if both chopsticks are available at the same time for a philosopher then only he should pick them up,
Algorithm
while(TRUE) {
// mod is used because if i=5,
// next chopstick is 1 (dining table is circular)
wait(stick[i]); wait(stick[(i+1) % 5]); /* eat */
signal(stick[i]); signal(stick[(i+1) % 5]);
/* think */ }
Code in C
#include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <semaphore.h> #define num_philopsophers 5 #define num_chopsticks 5 void dine(int n); pthread_t philosopher[num_philopsophers]; pthread_mutex_t chopstick[num_chopsticks]; int main() { // Define msg and status_message int status_message; void *msg; // Initialise the semaphore array for (int i = 1; i <= num_chopsticks; i++) { status_message = pthread_mutex_init(&chopstick[i], NULL); // Checking if the mutex was initialised successfully if (status_message == -1) { printf("\n Mutex initialization failed"); exit(1); } } // Run the philosopher Threads using *dine() function for (int i = 1; i <= num_philopsophers; i++) { status_message = pthread_create(&philosopher[i], NULL, (void *)dine, (int *)i); if (status_message != 0) { printf("\n Thread creation error \n"); exit(1); } } // Wait for all philosophers threads to complete executing // (finish dining) before closing the program for (int i = 1; i <= num_philopsophers; i++) { status_message = pthread_join(philosopher[i], &msg); if (status_message != 0) { printf("\n Thread join failed \n"); exit(1); } } // Destroy the chopstick Mutex array for (int i = 1; i <= num_chopsticks; i++) { status_message = pthread_mutex_destroy(&chopstick[i]); if (status_message != 0) { printf("\n Mutex Destroyed \n"); exit(1); } } return 0; } // dine method void dine(int n) { printf("\nPhilosopher % d is thinking ", n); // picking up the left chopstick (wait) pthread_mutex_lock(&chopstick[n]); // picking up the right chopstick (wait) pthread_mutex_lock(&chopstick[(n + 1) % num_chopsticks]); // both chopstick picked now starts eating printf("\nPhilosopher % d is eating ", n); sleep(3); // places the left chopstick down (signal) pthread_mutex_unlock(&chopstick[n]); // places the the right chopstick down (signal) pthread_mutex_unlock(&chopstick[(n + 1) % num_chopsticks]); // eating finishes printf("\nPhilosopher % d Finished eating ", n); }
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment