// Dining philosophers (swansons) using System V Semaphores // Original: http://www.lisha.ufsc.br/~guto/teaching/os/exercise/phil.html // Modified by Chris Kauffman // // Short random delays are added between each philosophers // thinking/eating cycle to generate some variance in execution order // // To see the multiple processes, run the following commands // > gcc -o philosophers philosophers.c // > philosophers > xxx & watch -d -n 0.1 'ps ux | grep philosophers' // Ctrl-c to stop the "watch" command (may screw up the terminal display) #include #include #include #include #include #include #include #include const int N_PHILOSOPHERS = 5; // Number of philosophers const int MEALS_TO_FINISH = 10; // Number of iterations before philosophers finish const int MAX_DELAY = 50000; // Maximum delay in nanos between meal iterations // Semaphore ids int utensils; // ID for array of IPC semaphores int not_at_table; // Start dinner when semaphore reaches 0 int philosopher(int n); // Defined after main() int main(){ setvbuf(stdout, NULL, _IONBF, 0); int i, status; pid_t phil[N_PHILOSOPHERS]; printf("The Dining Swansons (Philosophers) Problem\n"); // Parent process only: // // Allocate utensils: semaphores which are initially set to value // one. 5 utensils total in an array. Private semaphore array for // parent/children. utensils = semget(IPC_PRIVATE, N_PHILOSOPHERS, IPC_CREAT | 0600); for(i=0; i 0 phil[i] = pid; // parent tracks children } } // Parent waits on all children to finish for(i = 0; i < N_PHILOSOPHERS; i++) { waitpid(phil[i], &status, 0); } // Eliminate the utensils and table semaphores semctl(utensils, 0, IPC_RMID, 0); semctl(not_at_table, 0, IPC_RMID, 0); return 0; } // Code for dining philosopher child processes int philosopher(int n){ int i, j, first, second; struct sembuf op; // Used to perform semaphore operations op.sem_flg = 0; srand(time(NULL)); // Seed random number generator // Avoid deadlock via slightly different order of utensil requests // for last philospher // first utensil to get, most go for n first, last philospher goes for 0 first first = (n != N_PHILOSOPHERS-1)? n : 0; // second utensil to get, last philopher goes for n second second = (n != N_PHILOSOPHERS-1)? n + 1 : n; printf("Swanson %d wants utensils %d and %d\n",n,first,second); // Check in for dinner by decrementing the not_at_table value. op.sem_op = -1; op.sem_num = 0; semop(not_at_table, &op, 1); printf("Swanson %d at the table\n", n); // Wait for everyone to check in before start the meal. Passing 0 as // the sem_op means wait until the not_at_table counter is 0 to // proceed. op.sem_op = 0; op.sem_num = 0; semop(not_at_table, &op, 1); // Main loop of thinking/eating cycles for(i = 0; i < MEALS_TO_FINISH; i++) { int sleep_time = rand() % MAX_DELAY; usleep(sleep_time); // sleep for for a short time printf("%2d: Swanson %d is contemplating his awesomeness ...\n", i,n); // get first utensil op.sem_op = -1; op.sem_num = first; semop(utensils, &op, 1); printf("%2d: Swanson %d got utensil %d\n",i,n,first); // get second utensil op.sem_op = -1; op.sem_num = second; semop(utensils, &op, 1); printf("%2d: Swanson %d got utensil %d\n",i,n,second); printf("%2d: Swanson %d is eating an egg ...\n", i,n); // release first utensil op.sem_op = +1; op.sem_num = first; semop(utensils, &op, 1); // release second utensil op.sem_op = +1; op.sem_num = second; semop(utensils, &op, 1); } printf("Swanson %d leaving the diner\n",n); exit(n); }