Need this assignment completed by midnight on thursday
CSCI 4100 – Assignment 4 CSCI 4100 – Assignment 4 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. See the slides for Section 6.5-6.6 for a description of the problem. 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 monitor- like 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: a. think b. grab the forks c. eat d. 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: a. Display the headings and the philosophers’ initial states. b. Start the thread for each philosopher. c. Wait for each philosopher’s thread to complete. • void grab_forks(dining_room *room, int phil) - simulates a philosopher picking up forks: a. Acquire the table lock. b. Set the state for phil to HUNGRY. c. Display the current states of the philosophers. d. Until it is safe to eat, wait on the condition variable for phil in the safe_to_eat array. e. Set the state for phil to EATING. f. Display the current states of the philosophers. g. Release the table lock. • void release_forks(dining_room *room, int phil) - simulates a philosopher putting down forks: a. Acquire the table lock. b. Set the state for phil to THINKING. c. Display the current states of the philosophers. d. Test to see if it is safe for each of phil’s neighbors to eat. e. If it is, notify the philosopher using the appropriate condition variable in the safe_to_eat array. f. Release the table lock. • int test_phil(dining_room *room, int phil) - checks to see if it is safe for a philosopher to eat: a. If the state for phil is HUNGRY and neither of her neighbors is in the EATING state return true (1). b. Otherwise return false (0). c. The table lock must be acquired before this function is called. d. 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.) What to Hand In Your source file should have comments at the top listing your name, CSCI 4100, Assignment 4, and a brief explanation of what the program does. Upload dining_room.c to the D2L dropbox for Assignment 4. Instructions Dijkstra’s Solution The Dining Room Starting a Simulation Compiling and Running Your Code What to Hand In files/dining_room.h // CSCI 4100 // Programming Assignment 4 // Header file for Dining Philosophers simulation #ifndef __DINING_ROOM_H__ #define __DINING_ROOM_H__ #define MAX_PHILS 20 #include
#include #include #include #include #include enum p_state {THINKING, HUNGRY, EATING}; struct dining_room; // Structure used to pass arguments to start_philosopher function struct p_args { int phil_num; int num_cycles; struct dining_room *room; }; // The dining_room struct acts as a monitor for the simulation struct dining_room { int num_phils; int num_cycles; pthread_mutex_t table_lock; enum p_state phil_state[MAX_PHILS]; pthread_cond_t safe_to_eat[MAX_PHILS]; pthread_t phil_threads[MAX_PHILS]; struct p_args phil_args[MAX_PHILS]; }; // Tests to see if it is safe for the philosopher with the ID provided to eat // If it is safe, it changes the philosopher's state to EATING and returns // true, if not it returns false. // This function must only be called after table_lock has been acquired int test_phil(struct dining_room *room, int phil); // Starts a dining philosopher simulation void run_simulation(struct dining_room *room); // Simulates a philosopher