Code in C
Instructions
For this programming assignment you are going to implement asimulation 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 Philosophersproblem used semaphores,
but it can be adapted to use similar mechanisms:
• Each philosopher is in one of three states: THINKING, HUNGRY, orEATING.
• Every philosopher starts out in the THINKING state.
• When a philosopher is ready to eat, her state is changed toHUNGRY.
• 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 mustwait until the situation
changes, at which point her state is changed to EATING.
• When a philosopher is done eating, her state is changed toTHINKING and she must test
to see if either of her neighbors is in the HUNGRY state and it isnow safe for them to eat.
If it is, she must notify that philosopher that it is now safe tostart eating.
Note that the same test is used to assure two differentrequirements 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 toeat.
The Dining Room
I have implemented a structure called dining_room that can be usedto create a monitorlike
object that manages a simulation of the Dining Philosophersproblem.
It contains the following fields:
• num_phils - an integer representing the number ofphilosophers.
• num_cycles - an integer representing how many times eachphilosopher tries to eat.
• phil_state - an array of values indexed by philosopher ID of typep_state, one for
each philosopher, each of which has a value of THINKING, HUNGRY, orEATING depending
on the state of that philosopher.
• table_lock - a lock to control access to the shared data inphil_state.
• safe_to_eat - an array of condition variables indexed byphilosopher ID, each of which corresponds to the event when it issafe for that philosopher to eat.
• phil_threads - an array of threads indexed by philosopherID.
• phil_args - an array of structures of type p_args, indexed byphilosopher ID, each of which contains three fields:
– phil_num - the ID of the philosopher.
– num_cycles - the number of times that philosopher should try toeat.
– room - a pointer to the dining_room structure to use as amonitor.
I have implemented the following utility functions in thediningRoom.c file:
• init_dining_room - takes a pointer to an existing dining_roomstructure, and parameters representing the number of philosophersand the number of cycles and initializes the fields of thestructure.
• left_neighbor - returns the ID of the left neighbor of aphilosopher.
• right_neighbor - returns the ID of the right neighbor of aphilosopher.
• display_headings - displays column headings for a table of statechanges.
• display_states - displays the current state of each philosopherfor a table of state changes.
• think - simulates the philosopher thinking.
• eat - simulates the philosopher eating.
• start_philosopher - the function to be used to start aphilosopher thread. It uses information passed in a p_argsstructure 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.cfile:
• void run_simulation(dining_room *room) - starts a simulation ofthe 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 aphilosopher 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 philin 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 aphilosopher 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 toeat.
5. If it is, notify the philosopher using the appropriate conditionvariable in the safe_to_eat array.
6. Release the table lock.
• int test_phil(dining_room *room, int phil) - checks to see if itis safe for a philosopher to eat:
1. If the state for phil is HUNGRY and neither of her neighbors isin the EATING state return true (1).
2. Otherwise return false (0).
3. The table lock must be acquired before this function iscalled.
4. This function should not do anything with locks or conditionvariables.
Starting a Simulation
I have also provided the file dpsim.c, which contains a mainfunction. This function takes two command line arguments, creates adining_room structure using those values, and calls therun_simulation member function to start a simulation. See theCompiling and Running Your Code section below for moreinformation.
Compiling and Running Your Code
To create an executable file called dpsim use the followingcommand:
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 thecurrent state of each philosopher each time any philosopher’s statechanges.
$ ./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 livenessconditions described above (remember the first and lastphilosophers are neighbors too.)
File Orginization
dining_room.c
