Problem DescriptionThe dining philosophers problem is an example problem
often used in concurrent algorithm design to illustrate
synchronization issues and techniques for resolving them. Five
silent philosophers sit at a round table with bowls of spaghetti.
Forks are placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. However, a
philosopher can only eat spaghetti when he has both left and
right forks. Each fork can be held by only one philosopher and so
a philosopher can use the fork only if it is not being used by
another philosopher. After he finishes eating, he needs to put
down both forks so they become available to others. A
philosopher can take the fork on his right or the one on his left as
they become available, but cannot start eating before getting
both of them.
The problem is how to design a concurrent algorithm such that no
philosopher will starve; i.e., each can forever continue to alternate
between eating and thinking, assuming that no philosopher can
know when others may want to eat or think.
Given5 philosophers, 6 forks, no. of meals. (no. of times a
philosopher eats).
Code#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define NUM_PHIL 5
#define MEALS 100
static omp_lock_t chopsticks[NUM_PHIL];
void philosopher()
{
#pragma omp barrier
int id = omp_get_thread_num();
int right_chopstick;
int left_chopstick;
if(id < NUM_PHIL -1)
{
right_chopstick = id;
left_chopstick = id+1;
}
else
{
right_chopstick = 0;
left_chopstick = id;
}
int i;
for(i = 0; i < MEALS; i++)
{
omp_set_lock(&chopsticks[left_chopstick]);
omp_set_lock(&chopsticks[right_chopstick]);
printf("philosopher %d is eating\n", id);
usleep(100);
omp_unset_lock(&chopsticks[left_chopstick]);
omp_unset_lock(&chopsticks[right_chopstick]);
}
}
int main(int argc, char ** argv)
{
int i;
for(i = 0; i < NUM_PHIL; i++)
omp_init_lock(&chopsticks[i]);
#pragma omp parallel num_threads(NUM_PHIL)
{
philosopher();
}
for(i = 0; i < NUM_PHIL; i++)
omp_destroy_lock(&chopsticks[i]);
return 0;
}
Explanation of code: 1. Locks to represent chopsticks
static omp_lock_t chopsticks[NUM_PHIL]
2. Wait for all threads to start
#pragma omp barrier
3. Acquire chopsticks (semaphores), eat, wait for 100
microseconds, then release chopsticks (semaphores).
ACQUIRING CHOPSTICKS:
omp_set_lock(&chopsticks[left_chopstick]);
omp_set_lock(&chopsticks[right_chopstick]);
RELEASING CHOPSTICKS:
omp_unset_lock(&chopsticks[left_chopstick]);
omp_unset_lock(&chopsticks[right_chopstick]);
4. Initialize locks:
for(i = 0; i < NUM_PHIL; i++)
omp_init_lock(&chopsticks[i]);
5. Create and start philosopher threads.:
#pragma omp parallel num_threads(NUM_PHIL)
{
philosopher();
}
6. Wait for philosophers to finish then destroy locks.
for(i = 0; i < NUM_PHIL; i++)
omp_destroy_lock(&chopsticks[i])
OUTPUT:
The following screenshot describes the working of the program
when: a) When each philosopher is eating twice.
b) When each philosopher is eating once.
(Hence this program can be executed even for when each
philosopher eats n times.)
