Complete the following program in C:

activity.c:

#include "activity.h" #include #include #include #include #include #include

void doActivity(int activity,Philosopher* p,unsigned* seed) { if (activity == THINK) assert(p->state == EAT); if (activity == HUNGRY) assert(p->state == THINK); if (activity == EAT) assert(p->state == HUNGRY); p->state = activity; if (p->state == HUNGRY) return; else { double v = ((double)rand_r(seed)) / RAND_MAX * MICROSEC; if (p->state == EAT) assert(p->left->user == p->right->user && p->left->user == p->pid && p->left->user != -1); printf("philo [%d] is eating... ",p->pid); usleep(v); if (p->state == EAT) assert(p->left->user == p->right->user && p->left->user == p->pid && p->left->user != -1); } }

activity.h:

#ifndef __ACTIVITY_H #define __ACTIVITY_H

#include

#define MICROSEC 5.0 #define THINK 0 #define HUNGRY 1 #define EAT 2

typedef struct ForkTag { pthread_mutex_t mtx; int fid; int user; } Fork;

typedef struct PhiloTag { int pid; int state; int cycle; Fork* left; Fork* right; } Philosopher;

void doActivity(int activity,Philosopher* p,unsigned* seed);

#endif

philo.c(main):

#include #include #include #include #include #include "activity.h"

/* * A simple function to initialize a "Fork" ADT instance. * It receives a pointer to the fork to initialize as well * as an integer `forkID` to number the forks. */ void initFork(Fork* f,int forkID) { f->user = -1; f->fid = forkID; pthread_mutex_init(&f->mtx,NULL); } /* * A simple function to 'pickup' a fork. It takes as input * the 'name' of the philosopher picking up the fork and a \ * pointer to the fork being picked up */ void pickupFork(int philosopher,Fork* f) { pthread_mutex_lock(&f->mtx); f->user = philosopher; } /* * A simple function to 'drop' a fork. It takes as input * the 'name' of the philosopher dropping the fork as well as * a pointer to the fork being dropped. It also checks that whomever * drops the fork is the same individual who picked it up. */ void dropFork(int philosopher,Fork* f) { assert(f->user == philosopher); f->user = -1; pthread_mutex_unlock(&f->mtx); }

/** * Feel free to add as many functions as you see fit * */

/** * This is the entry point of your program * Input: * - n : the number of philosopher seated at the table * - c : the number of THINKING -> HUNGRY -> EATING cycles that each philosopher * must go through */ int main(int argc,char* argv[]) { int n = atoi(argv[1]); int c = atoi(argv[2]); // TODO return 0; }

Exercise 6. (30 points) The dining philosophers is a classic synchronization problem often discussed in an operating system class. The problem is the following. There are n philosophers seated at a round table. In front of each philosopher one can find a dining plate with one fork on either side Clearh, a table seating n philosophers has n forks (not 2 n!) Each philosopher engages in one of three activities THINKING He either sits back in deep thoughts HUNGRY He is grabbing forks on either side of his plate as he wishes to eat EATING He has two forks and can eat. When he's done he puts back the forks (which are now available to his neighbors) The table arrangement is shown below for 5philosophers where philosophers are numbered clockwise from the top {0, 1,2,3,4) with 0 at the "noon" position. All philosophers behave in exactly the same way, they grab one fork, then the other and only start eating once they bold both. Ifa philosopher can't grab the second fork (ecause his neighbor on that side is eating) he simply waits until his neighbor is done and then grabs the fork (he does not release the one he acquired). Without further care, this can lead to starvation! Simply consider the scenario where all philosophers grab the fork to their right and then grab the fork to their left. You will quickly realize that no one will eat and no one will progress. There is a very simple fix where the order in which philosopher i grabs his forks depends on the parity of i. Ifi is odd the philosopher elects to pick right then left and in the opposite order if i is even. Your task is to write a multi-threaded simulator for the dining philosopher problem. The simulator takes two argu ments on its command line k The number of philosophers c The number o cycles THINKING ? HUNGRY ? EATING that each philosopher must go through. Each philosopher is simulated by a thread that goes through c cycles. A cycle starts in the thinking state and transitions to the hungry state. The philosopher must grab his forks correctly and then eat (for a random number of micro-seconds) When he is done, he returns the forks and resumes thinking for a random number of micro-seconds. That completes one cycle. To implement the random delay in a philosopher activity, use the following C function 1 #define MICROSEC 5.0 2 typedef struct PhiloTag state 4.. . . I/ some other stuff you might wish to have 5 Philosopher; 6 void doActivity(int activity, Philosopher* p, unsigned* seed) f p->state -activity; ((doub le ) rand-r(seed)) / 8 double = 9usleep (v); 10 RAND-MAX * MICROSEC; Note that the rand_r function is available in stdlib.h Your program should terminate when the last philosopher completes his last cycle. Exercise 6. (30 points) The dining philosophers is a classic synchronization problem often discussed in an operating system class. The problem is the following. There are n philosophers seated at a round table. In front of each philosopher one can find a dining plate with one fork on either side Clearh, a table seating n philosophers has n forks (not 2 n!) Each philosopher engages in one of three activities THINKING He either sits back in deep thoughts HUNGRY He is grabbing forks on either side of his plate as he wishes to eat EATING He has two forks and can eat. When he's done he puts back the forks (which are now available to his neighbors) The table arrangement is shown below for 5philosophers where philosophers are numbered clockwise from the top {0, 1,2,3,4) with 0 at the "noon" position. All philosophers behave in exactly the same way, they grab one fork, then the other and only start eating once they bold both. Ifa philosopher can't grab the second fork (ecause his neighbor on that side is eating) he simply waits until his neighbor is done and then grabs the fork (he does not release the one he acquired). Without further care, this can lead to starvation! Simply consider the scenario where all philosophers grab the fork to their right and then grab the fork to their left. You will quickly realize that no one will eat and no one will progress. There is a very simple fix where the order in which philosopher i grabs his forks depends on the parity of i. Ifi is odd the philosopher elects to pick right then left and in the opposite order if i is even. Your task is to write a multi-threaded simulator for the dining philosopher problem. The simulator takes two argu ments on its command line k The number of philosophers c The number o cycles THINKING ? HUNGRY ? EATING that each philosopher must go through. Each philosopher is simulated by a thread that goes through c cycles. A cycle starts in the thinking state and transitions to the hungry state. The philosopher must grab his forks correctly and then eat (for a random number of micro-seconds) When he is done, he returns the forks and resumes thinking for a random number of micro-seconds. That completes one cycle. To implement the random delay in a philosopher activity, use the following C function 1 #define MICROSEC 5.0 2 typedef struct PhiloTag state 4.. . . I/ some other stuff you might wish to have 5 Philosopher; 6 void doActivity(int activity, Philosopher* p, unsigned* seed) f p->state -activity; ((doub le ) rand-r(seed)) / 8 double = 9usleep (v); 10 RAND-MAX * MICROSEC; Note that the rand_r function is available in stdlib.h Your program should terminate when the last philosopher completes his last cycle