141 lines
4.4 KiB
C
141 lines
4.4 KiB
C
// 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 <unistd.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <sys/types.h>
|
|
#include <sys/wait.h>
|
|
#include <sys/ipc.h>
|
|
#include <sys/sem.h>
|
|
#include <time.h>
|
|
|
|
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<N_PHILOSOPHERS; i++){
|
|
semctl(utensils, i, SETVAL, 1);
|
|
}
|
|
not_at_table = semget(IPC_PRIVATE, 1, IPC_CREAT | 0600);
|
|
|
|
// Prevent children from starting to eat until all have checked
|
|
// in. Each child decreases the not_at_table counter by one then
|
|
// wait until it reaches 0 to start eating.
|
|
semctl(not_at_table, 0, SETVAL, 5);
|
|
|
|
// Parent generates child processes
|
|
for(i=0; i < N_PHILOSOPHERS; i++){
|
|
int pid = fork();
|
|
if(pid == 0){ // child has pid 0
|
|
int ret = philosopher(i); // child acts as philosopher
|
|
exit(ret); // then exits
|
|
}
|
|
else{ // parent gets pid > 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);
|
|
}
|