Code
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#define N 5
#define THINKING 2
#define HUNGRY 1
#define EATING 0
#define LEFT (phnum + 4) % N
#define RIGHT (phnum + 1) % N
int state[N];
int phil[N] = { 0, 1, 2, 3, 4 };
std::mutex mutex;
std::condition_variable S[N];
void test(int phnum)
{
if (state[phnum] == HUNGRY
&& state[LEFT] != EATING
&& state[RIGHT] != EATING) {
// state that eating
state[phnum] = EATING;
std::this_thread::sleep_for(std::chrono::milliseconds(2000));
std::cout << "Philosopher " << phnum + 1 << " takes fork " << LEFT + 1 << " and " << phnum + 1 << std::endl;
std::cout << "Philosopher " << phnum + 1 << " is Eating" << std::endl;
// notify the philosopher that he can start eating
S[phnum].notify_all();
}
}
// take up chopsticks
void take_fork(int phnum)
{
std::unique_lock<std::mutex> lock(mutex);
// state that hungry
state[phnum] = HUNGRY;
std::cout << "Philosopher " << phnum + 1 << " is Hungry" << std::endl;
// eat if neighbours are not eating
test(phnum);
// if unable to eat wait to be signalled
S[phnum].wait(lock);
std::this_thread::sleep_for(std::chrono::milliseconds(1000));
}
// put down chopsticks
void put_fork(int phnum)
{
std::unique_lock<std::mutex> lock(mutex);
// state that thinking
state[phnum] = THINKING;
std::cout << "Philosopher " << phnum + 1 << " putting fork " << LEFT + 1 << " and " << phnum + 1 << " down" << std::endl;
std::cout << "Philosopher " << phnum + 1 << " is thinking" << std::endl;
test(LEFT);
test(RIGHT);
}
void philosopher(int num)
{
while (true) {
take_fork(num);
put_fork(num);
}
}
int main()
{
std::thread threads[N];
for (int i = 0; i < N; i++) {
threads[i] = std::thread(philosopher, i);
std::cout << "Philosopher " << i + 1 << " is thinking" << std::endl;
}
for (int i = 0; i < N; i++)
threads[i].join();
return 0;
}
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#define N 5
#define THINKING 2
#define HUNGRY 1
#define EATING 0
#define LEFT (phnum + 4) % N
#define RIGHT (phnum + 1) % N
int state[N];
int phil[N] = { 0, 1, 2, 3, 4 };
sem_t mutex;
sem_t S[N];
void test(int phnum)
{
if (state[phnum] == HUNGRY
&& state[LEFT] != EATING
&& state[RIGHT] != EATING) {
// state that eating
state[phnum] = EATING;
sleep(2);
printf("Philosopher %d takes fork %d and %d\n",
phnum + 1, LEFT + 1, phnum + 1);
printf("Philosopher %d is Eating\n", phnum + 1);
// sem_post(&S[phnum]) has no effect
// during takefork
// used to wake up hungry philosophers
// during putfork
sem_post(&S[phnum]);
}
}
// take up chopsticks
void take_fork(int phnum)
{
sem_wait(&mutex);
// state that hungry
state[phnum] = HUNGRY;
printf("Philosopher %d is Hungry\n", phnum + 1);
// eat if neighbours are not eating
test(phnum);
sem_post(&mutex);
// if unable to eat wait to be signalled
sem_wait(&S[phnum]);
sleep(1);
}
// put down chopsticks
void put_fork(int phnum)
{
sem_wait(&mutex);
// state that thinking
state[phnum] = THINKING;
printf("Philosopher %d putting fork %d and %d down\n",
phnum + 1, LEFT + 1, phnum + 1);
printf("Philosopher %d is thinking\n", phnum + 1);
test(LEFT);
test(RIGHT);
sem_post(&mutex);
}
void* philosopher(void* num)
{
while (1) {
int* i = num;
sleep(1);
take_fork(*i);
sleep(0);
put_fork(*i);
}
}
int main()
{
int i;
pthread_t thread_id[N];
// initialize the semaphores
sem_init(&mutex, 0, 1);
for (i = 0; i < N; i++)
sem_init(&S[i], 0, 0);
for (i = 0; i < N; i++) {
// create philosopher processes
pthread_create(&thread_id[i], NULL,
philosopher, &phil[i]);
printf("Philosopher %d is thinking\n", i + 1);
}
for (i = 0; i < N; i++)
pthread_join(thread_id[i], NULL);
}
Note – The below program may compile only with C compilers with semaphore and thread library.
The Dining Philosopher Problem is a classic synchronization problem in computer science that involves multiple processes (philosophers) sharing a limited set of resources (forks) in order to perform a task (eating). In order to avoid deadlock or starvation, a solution must be implemented that ensures that each philosopher can access the resources they need to perform their task without interference from other philosophers.
One common solution to the Dining Philosopher Problem uses semaphores, a synchronization mechanism that can be used to control access to shared resources. In this solution, each fork is represented by a semaphore, and a philosopher must acquire both the semaphore for the fork to their left and the semaphore for the fork to their right before they can begin eating. If a philosopher cannot acquire both semaphores, they must wait until they become available.
The steps for the Dining Philosopher Problem solution using semaphores are as follows
1. Initialize the semaphores for each fork to 1 (indicating that they are available).
2. Initialize a binary semaphore (mutex) to 1 to ensure that only one philosopher can attempt to pick up a fork at a time.
3. For each philosopher process, create a separate thread that executes the following code:
- While true:
- Think for a random amount of time.
- Acquire the mutex semaphore to ensure that only one philosopher can attempt to pick up a fork at a time.
- Attempt to acquire the semaphore for the fork to the left.
- If successful, attempt to acquire the semaphore for the fork to the right.
- If both forks are acquired successfully, eat for a random amount of time and then release both semaphores.
- If not successful in acquiring both forks, release the semaphore for the fork to the left (if acquired) and then release the mutex semaphore and go back to thinking.
4. Run the philosopher threads concurrently.
By using semaphores to control access to the forks, the Dining Philosopher Problem can be solved in a way that avoids deadlock and starvation. The use of the mutex semaphore ensures that only one philosopher can attempt to pick up a fork at a time, while the use of the fork semaphores ensures that a philosopher can only eat if both forks are available.
Overall, the Dining Philosopher Problem solution using semaphores is a classic example of how synchronization mechanisms can be used to solve complex synchronization problems in concurrent programming.
Implementation of the Dining Philosopher Problem solution using semaphores in Python
import threading
import time
import random
# Define the number of philosophers and forks
num_philosophers = 5
num_forks = num_philosophers
# Define semaphores for the forks and the mutex
forks = [threading.Semaphore(1) for i in range(num_forks)]
mutex = threading.Semaphore(1)
# Define the philosopher thread function
def philosopher(index):
while True:
print(f"Philosopher {index} is thinking...")
time.sleep(random.randint(1, 5))
mutex.acquire()
left_fork_index = index
right_fork_index = (index + 1) % num_forks
forks[left_fork_index].acquire()
forks[right_fork_index].acquire()
mutex.release()
print(f"Philosopher {index} is eating...")
time.sleep(random.randint(1, 5))
forks[left_fork_index].release()
forks[right_fork_index].release()
# Create a thread for each philosopher
philosopher_threads = []
for i in range(num_philosophers):
philosopher_threads.append(threading.Thread(target=philosopher, args=(i,)))
# Start the philosopher threads
for thread in philosopher_threads:
thread.start()
# Wait for the philosopher threads to complete
for thread in philosopher_threads:
thread.join()
Output:
Philosopher 0 is thinking...
Philosopher 1 is thinking...
Philosopher 2 is thinking...
Philosopher 3 is thinking...
Philosopher 4 is thinking...
Philosopher 1 is eating...
Philosopher 2 is eating...
Philosopher 0 is eating...
Philosopher 4 is eating...
Philosopher 3 is eating...
Philosopher 1 is thinking...
Philosopher 2 is thinking...
Philosopher 3 is thinking...
Philosopher 4 is thinking...
Philosopher 0 is thinking...
Philosopher 3 is eating...
Philosopher 4 is eating...
Philosopher 0 is eating...
Philosopher 1 is eating...
Philosopher 2 is eating...
Philosopher 0 is thinking...
Philosopher 1 is thinking...
Philosopher 2 is thinking...
Philosopher 3 is thinking...
Philosopher 4 is thinking...
As you can see from the output, each philosopher takes turns thinking and eating, and there is no deadlock or starvation.
Dining Philosopher Problem Using Semaphores
The Dining Philosopher Problem states that K philosophers are seated around a circular table with one chopstick between each pair of philosophers. There is one chopstick between each philosopher. A philosopher may eat if he can pick up the two chopsticks adjacent to him. One chopstick may be picked up by any one of its adjacent followers but not both.
Dining Philosopher