Question

Code in C

Instructions
For this programming assignment you are going to implement a simulation of Dijkstra’s
solution to the Dining Philosophers problem using threads, locks, and condition variables.

Dijkstra’s Solution
Edsgar Dijkstra’s original solution to the Dining Philosophers problem used semaphores,
but it can be adapted to use similar mechanisms:
• Each philosopher is in one of three states: THINKING, HUNGRY, or EATING.
• Every philosopher starts out in the THINKING state.
• When a philosopher is ready to eat, her state is changed to HUNGRY.
• Before she can eat, she must test to see if it is safe to do so. If either of her neighbors is
in the EATING state, it is not safe for her to eat and she must wait until the situation
changes, at which point her state is changed to EATING.
• When a philosopher is done eating, her state is changed to THINKING and she must test
to see if either of her neighbors is in the HUNGRY state and it is now safe for them to eat.
If it is, she must notify that philosopher that it is now safe to start eating.
Note that the same test is used to assure two different requirements of the problem:
1. Safety: a philosopher only eats if it is safe to do so.
2. Liveness: no philosopher should go hungry if it is safe to eat.

The Dining Room
I have implemented a structure called dining_room that can be used to create a monitorlike
object that manages a simulation of the Dining Philosophers problem.

It contains the following fields:
• num_phils - an integer representing the number of philosophers.
• num_cycles - an integer representing how many times each philosopher tries to eat.
• phil_state - an array of values indexed by philosopher ID of type p_state, one for
each philosopher, each of which has a value of THINKING, HUNGRY, or EATING depending
on the state of that philosopher.
• table_lock - a lock to control access to the shared data in phil_state.
• safe_to_eat - an array of condition variables indexed by philosopher ID, each of which corresponds to the event when it is safe for that philosopher to eat.
• phil_threads - an array of threads indexed by philosopher ID.
• phil_args - an array of structures of type p_args, indexed by philosopher ID, each of which contains three fields:
– phil_num - the ID of the philosopher.
– num_cycles - the number of times that philosopher should try to eat.
– room - a pointer to the dining_room structure to use as a monitor.

I have implemented the following utility functions in the diningRoom.c file:
• init_dining_room - takes a pointer to an existing dining_room structure, and parameters representing the number of philosophers and the number of cycles and initializes the fields of the structure.
• left_neighbor - returns the ID of the left neighbor of a philosopher.
• right_neighbor - returns the ID of the right neighbor of a philosopher.
• display_headings - displays column headings for a table of state changes.
• display_states - displays the current state of each philosopher for a table of state changes.
• think - simulates the philosopher thinking.
• eat - simulates the philosopher eating.
• start_philosopher - the function to be used to start a philosopher thread. It uses information passed in a p_args structure to repeatedly do the following:
1. think
2. grab the forks
3. eat
4. release the forks

You must implement the following functions in the dining_room.c file:
• void run_simulation(dining_room *room) - starts a simulation of the Dining Philosophers problem:
1. Display the headings and the philosophers’ initial states.
2. Start the thread for each philosopher.
3. Wait for each philosopher’s thread to complete.
• void grab_forks(dining_room *room, int phil) - simulates a philosopher picking up forks:
1. Acquire the table lock.
2. Set the state for phil to HUNGRY.
3. Display the current states of the philosophers.
4. Until it is safe to eat, wait on the condition variable for phil in the safe_to_eat array.
5. Set the state for phil to EATING.
6. Display the current states of the philosophers.
7. Release the table lock.
• void release_forks(dining_room *room, int phil) - simulates a philosopher putting down forks:
1. Acquire the table lock.
2. Set the state for phil to THINKING.
3. Display the current states of the philosophers.
4. Test to see if it is safe for each of phil’s neighbors to eat.
5. If it is, notify the philosopher using the appropriate condition variable in the safe_to_eat array.
6. Release the table lock.
• int test_phil(dining_room *room, int phil) - checks to see if it is safe for a philosopher to eat:
1. If the state for phil is HUNGRY and neither of her neighbors is in the EATING state return true (1).
2. Otherwise return false (0).
3. The table lock must be acquired before this function is called.
4. This function should not do anything with locks or condition variables.

Starting a Simulation
I have also provided the file dpsim.c, which contains a main function. This function takes two command line arguments, creates a dining_room structure using those values, and calls the run_simulation member function to start a simulation. See the Compiling and Running Your Code section below for more information.

Compiling and Running Your Code
To create an executable file called dpsim use the following command:
gcc -o dpsim dpsim.c dining_room.c -lpthread

To run your code with 5 philosophers that try to eat 10 times, type:
./dpsim 5 10

If it is working correctly it should display a table showing the current state of each philosopher each time any philosopher’s state changes.

$ ./dpsim 5 2

PHIL 0 PHIL 1 PHIL 2 PHIL 3 PHIL 4

THINKING THINKING THINKING THINKING THINKING

THINKING THINKING THINKING THINKING HUNGRY

THINKING THINKING THINKING THINKING EATING

THINKING THINKING THINKING HUNGRY EATING

HUNGRY THINKING THINKING HUNGRY EATING

HUNGRY THINKING THINKING HUNGRY THINKING

EATING THINKING THINKING HUNGRY THINKING

EATING THINKING THINKING EATING THINKING

EATING THINKING THINKING EATING HUNGRY

THINKING THINKING THINKING EATING HUNGRY

THINKING THINKING THINKING THINKING HUNGRY

THINKING THINKING THINKING THINKING EATING

THINKING THINKING HUNGRY THINKING EATING

THINKING THINKING EATING THINKING EATING

THINKING HUNGRY EATING THINKING EATING

THINKING HUNGRY EATING THINKING THINKING

HUNGRY HUNGRY EATING THINKING THINKING

EATING HUNGRY EATING THINKING THINKING

EATING HUNGRY EATING HUNGRY THINKING

EATING HUNGRY THINKING HUNGRY THINKING

EATING HUNGRY THINKING EATING THINKING

THINKING HUNGRY THINKING EATING THINKING

THINKING EATING THINKING EATING THINKING

THINKING EATING HUNGRY EATING THINKING

THINKING EATING HUNGRY THINKING THINKING

THINKING THINKING HUNGRY THINKING THINKING

THINKING THINKING EATING THINKING THINKING

THINKING HUNGRY EATING THINKING THINKING

THINKING HUNGRY THINKING THINKING THINKING

THINKING EATING THINKING THINKING THINKING

THINKING THINKING THINKING THINKING THINKING

A correct implementation should satisfy the safety and liveness conditions described above (remember the first and last philosophers are neighbors too.)

File Orginization
dining_room.c

Answer 1

SOLUTION :

the djkstras it is an synchronization and interprocess communication problem the philospher should use its available resources(ie forks and chopsticks) to keep working and eat to satisfy its hunger

Note : please write your name in the name section

// name

// university roll no

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

#define N 5
#define THINKiNG_turn 2
#define HUNGRY 1
#define eating_turn 0
#define left_side (phnum + 4) % N
#define right_side (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_side] != eating_turn
&& state[right_side] != eating_turn) {
// the turn in which eating_turn takes place
state[phnum] = eating_turn;

sleep(2);

printf("philosphr %d takes fork %d and %d\n",
phnum + 1, left_side + 1, phnum + 1);

printf("philosphr %d is eating_turn\n", phnum + 1);

sem_post(&S[phnum]);
}
}

// taking up chopsticks
void take_fork(int phnum)
{

sem_wait(&mutax);

// state that hungry
state[phnum] = HUNGRY;

printf("philosphr %d is Hungry\n", phnum + 1);

// eat if neighbor are not eating_turn
test(phnum);

sem_post(&mutex);

sem_wait(&S[phnum]);

sleep(1);
}

// keep down chopstick
void put_fork(int phnum)
{

sem_wait(&mutex);

// state that THINKiNG_turn
state[phnum] = THINKiNG_turn;

printf("philosphr %d putting fork %d and %d down\n",
phnum + 1, left_side + 1, phnum + 1);
printf("philosphr %d is THINKiNG_turn\n", phnum + 1);

test(left_side);
test(right_side);

sem_post(&mutex);
}

void philosphr(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];

// initiate 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++) {

pthread_create(&thread_id[i], NULL,
philosphr, &phil[i]);

printf("philosphr %d is THINKiNG_turn\n", i + 1);
}

for (i = 0; i < N; i++)

pthread_join(thread_id[i], NULL);
}

// name the file as dining_room.c and upload to the dropbox