Lesser Program IV - Dining Philosophers

From Maryville College CS Wiki
< Os‎ | spring2019
Jump to: navigation, search

Take the following implementation and improve upon. Accolades shall be given to whoever keeps their philosophers alive for the longest!

(You are not allowed to alter the computation of how long each philosopher thinks or eats, nor are you allow to change their starvation time.)

// compile with -pthread option
#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

sem_t chopsticks[5];       //five chopsticks
pthread_t philosophers[5]; //five philosophers
int chopstick_holder[5];   //who has the chopstick

enum philosopher_status_t {THINKING,HUNGRY,EATING,DEAD};
enum philosopher_status_t state[5]; 

int
take_chopstick(int i, int p)
{
    if(!sem_trywait(chopsticks + i)) {
        chopstick_holder[i] = p;
        return 1;
    }

    return 0;
}


int
place_chopstick(int i, int p)
{
    sem_post(chopsticks+i);
    chopstick_holder[i] = -1;
}


//philosopher function
void *philosophize(void *arg)
{
    enum philosopher_status_t *mystate = arg;
    int starved = 0;
    time_t hunger_time;
    int have_left=0, have_right=0; //ownership of the chopsticks
    int i = mystate - state;
    

    //random flip 
    if(rand() % 2) {
        *mystate = THINKING;
    } else {
        *mystate = HUNGRY;
        hunger_time = time(0);
    }
    
    while(!starved) {
        switch(*mystate) {
        case THINKING:
            usleep(rand()%1000000);
            *mystate = HUNGRY;
            hunger_time = time(0);
            break;
        case HUNGRY:
            if(time(0) - hunger_time >= 1) {
                starved = 1;
            }

            //get the right chopstick
            usleep(900000);
            if(!have_right) {
                have_right = take_chopstick(i, i);
            }
            if(!have_left && have_right) {
                have_left = take_chopstick((i+1)%5, i);
                if(!have_left) {
                    place_chopstick(i, i);
                    have_right=0;
                }
            }
            if(have_left && have_right) {
                *mystate = EATING;
            } 
            break;
        case EATING:
            usleep(rand()%1000000);
            place_chopstick(i, i);
            place_chopstick((i+1)%5, i);
            have_left = 0;
            have_right= 0;
            *mystate=THINKING;
            break;
        }
    }

    //save the others!
    if(have_right) {
        place_chopstick(i, i);
    } 
    if(have_left) {
        place_chopstick((i+1)%5, i);
    }
    *mystate = DEAD;
}


int main()
{
    int alive;
    int i;

    //seed the random number generator
    srand(time(0));
    
    //create the chopsticks
    for(i=0; i<5; i++) {
        sem_init(chopsticks+i, 0, 1);
        chopstick_holder[i] = -1;
    }
    
    //create the philosophers
    for(int i=0; i<5; i++) {
        pthread_create(philosophers+i, NULL, philosophize, state+i);
    }

    //watch them go
    do {
        alive = 0; //we assume they are dead
        for(i=0; i<5; i++) {
            //draw the chopstick
            if(chopstick_holder[i] == -1) {
                putchar('|');
            } else {
                putchar(' ');
            }

            //draw the philosopher
            switch(state[i]) {
            case THINKING:
                putchar('T');
                break;
            case EATING:
                putchar('E');
                break;
            case HUNGRY: 
                putchar('S');
                break;
            case DEAD:
                putchar('X');
            }

            //count the living
            if(state[i] != DEAD) {
                alive++;
            }
        }
        putchar('\n');
        usleep(500000);
    } while(alive != 0);
    
    for(i=0; i<5; i++) {
        pthread_join(philosophers[i], NULL);
    }
    printf("ALL THE PHILOSOPHER ARE DEAD!\n");
}