Dining Philosopher Problem. There is a dining room containing a circular table with five chairs. At each chair is a plate, and between each plate is a single chopstick. In the middle of the table is a bowl of spaghetti. Near the room are five philosophers who spend most of their time thinking, but who occasionally get hungry and need to eat so they can think some more. In order to eat, a philosopher must sit at the table, pick up the two chopsticks to the left and right of a plate, then serve and eat the spaghetti on the plate. A philosopher may THINK indefinately. Every philosopher who EATs will eventually finish. Philosophers may PICKUP and PUTDOWN their chopsticks in either order, or nondeterministically, but these are atomic actions, and, of course, two philosophers cannot use a single CHOPSTICK at the same time. The problem is to 1 design a protocol to satisfy the liveness condition: any philosopher who tries to EAT, eventually does. Instructions. •

Task 1 (50 pts). Eliminate the deadlock by avoiding circular waiting. (Hint: change the order to access chopsticks for some philosophers.)

• Task 2 (50 pts). Eliminate the deadlock by avoiding hold and wait. In other words, if a philosopher is not able to obtain the right chopstick, he/she will release the left chopstick immediately. (Hint: Use Pthread Mutex to solve the problem.)

• Task 3 (50 pts extra credit). Eliminate the deadlock by limiting that at most 3 philosophers are able to compete for the chopsticks at the same time. (Hint: Use Pthread Conditional Variable to solve the problem.)

Skeleton Code: #include #include #include #include #include #define NUMP 5 pthread_mutex_t fork_mutex[NUMP]; int main(int argc, char* argv[]) { int i; pthread_t diner_thread[NUMP]; int dn[NUMP]; void *diner(); for (i=0;i