Dining Philosopher

diners.c

#include	<sys/types.h>
#include	<sys/ipc.h>
#include	<sys/sem.h>
#include	<sched.h>
#include	<stdio.h>
#include	<errno.h>

#include "simp_sem.h"
#include "diners.h"
/*
 * Taken from "Operating Systems - Design and Implementation" by Tanenbaum
 * Section 2.3, page 91, Figure 2-10
 */
#define LEFT 		(i + N - 1) % N	/* i's left neighbor */
#define RIGHT 		(i + 1) % N	/* i's right neighbor */
#define THINKING	0		/* philosopher states */
#define HUNGRY		1
#define EATING		2

int state[N];
semaphore s[N];
semaphore mutex;


void take_forks (int);
void put_forks (int);
void test (int);

void think (int);
void eat (int);

void philosopher (void* i)
{
	int *phil = (int*)i;
	int awhile = 5;

	while (awhile--)
	{
		think(*phil);
		take_forks(*phil);
		eat(*phil);
		put_forks (*phil);
	}
}

void
take_forks (int i)
{
	sem_wait (mutex);
	state[i] = HUNGRY;
	test(i);
	sem_signal (mutex);
	sem_wait (s[i]);
}

void
put_forks (int i)
{
	sem_wait (mutex);
	state[i] = THINKING;
	test(LEFT);
	test(RIGHT);
	sem_signal (mutex);
}

void
test (int i)
{
	if (state[i] == HUNGRY &&
		state[LEFT] != EATING &&
		state[RIGHT] != EATING)
	{
		state[i] = EATING;
		sem_signal (s[i]);
	}
}

void think (int i)
{
	printf ("Philosopher %d thinking\n", i);
	sleep (2);
	printf ("Philosopher %d done thinking\n", i);
}

void eat (int i)
{
	printf ("Philosopher %d eating (%d, %d)\n", i, state[LEFT], state[RIGHT]);
	sleep (1);
	printf ("Philosopher %d done eating\n", i);
}

diners.h

/*
 * Header file for the diners.  Note that the semaphore variables are defined
 * here as global variables.
 */
#include	<sys/types.h>
#include	<sys/ipc.h>
#include	<sys/sem.h>
#include	<sched.h>
#include	<stdio.h>
#include	<errno.h>
#include 	<unistd.h>
#include "simp_sem.h"

#define N 		5		/* number of philosophers */

typedef int semaphore;
extern semaphore mutex;
extern semaphore s[N];

void philosopher (void*);

Dining_Philosopher.c

/*
 ============================================================================
 Name        : Dining_Philosopher.c
 Author      : 
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include "simp_sem.h"
#include "diners.h"

int main(void)
{

	puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */

	pthread_t thread_id[N];
	int phils[N];

	mutex = sem_create( 105, 0);
	sem_signal(mutex);

	int i = 0;
	for(i = 0; i < N; i++)
		if( (s[i] = sem_create( (105 + i)  , 0)) < 0 )
			return EXIT_FAILURE;

	for(i = 0; i < N; i++)
	{
		phils[i] = i;
		pthread_create(&thread_id[i], NULL, (void*)philosopher, &phils[i]);
	}

	for(i = 0; i < N; i++)
		pthread_join(thread_id[i], 0);

	return EXIT_SUCCESS;
}

simp_sem.c

/*
 * Provide a simpler and easier to understand interface to the System V
 * semaphore system calls.  There are 7 routines available to the user:
 *
 *	id = sem_create(key, initval);	# create with initial value or open
 *	id = sem_open(key);		# open (must already exist)
 *	sem_wait(id);			# wait = P = down by 1
 *	sem_signal(id);			# signal = V = up by 1
 *	sem_op(id, amount);		# wait   if (amount < 0)
 *					# signal if (amount > 0)
 *	sem_close(id);			# close
 *	sem_rm(id);			# remove (delete)
 *
 * We create and use a 3-member set for the requested semaphore.
 * The first member, [0], is the actual semaphore value, and the second
 * member, [1], is a counter used to know when all processes have finished
 * with the semaphore.  The counter is initialized to a large number,
 * decremented on every create or open and incremented on every close.
 * This way we can use the "adjust" feature provided by System V so that
 * any process that exit's without calling sem_close() is accounted
 * for.  It doesn't help us if the last process does this (as we have
 * no way of getting control to remove the semaphore) but it will 
 * work if any process other than the last does an exit (intentional
 * or unintentional). 
 * The third member, [2], of the semaphore set is used as a lock variable
 * to avoid any race conditions in the sem_create() and sem_close()
 * functions.
 */

#include	<sys/types.h>
#include	<sys/ipc.h>
#include	<sys/sem.h>

#include "simp_sem.h"
void err_sys (char *);
void err_dump (char *);
#include        <stdio.h>

#include	<errno.h>
extern int	errno;

#define BIGCOUNT	10000		/* initial value of process counter
*/

/*
 * Define the semaphore operation arrays for the semop() calls.
 */

static struct sembuf	op_lock[2] = {
	{2, 0, 0},	/*wait for [2] (lock) to equal 0 */
	{2, 1, SEM_UNDO}	/*then increment [2] to 1 - this locks it */
			/*UNDO to release the lock if processes exits
			  before explicitly unlocking */
};

static struct sembuf	op_endcreate[2] = {
	{1, -1, SEM_UNDO},/* decrement [1] (proc counter) with undo on exit */
			/* UNDO to adjust proc counter if process exits
			   before explicitly calling sem_close() */
	{2, -1, SEM_UNDO}	/* then decrement [2] (lock) back to 0 */
};

static struct sembuf	op_open[1] = {
	{1, -1, SEM_UNDO}	/* decrement [1] (proc counter) with undo on exit */
};

static struct sembuf	op_close[3] = {
	{2, 0, 0},	/* wait for [2] (lock) to equal 0 */
    {2, 1, SEM_UNDO},	/* then increment [2] to 1 - this locks it */
	{1, 1, SEM_UNDO}	/* then increment [1] (proc counter) */
};

static struct sembuf	op_unlock[1] = {
	{2, -1, SEM_UNDO}	/* decrement [2] (lock) back to 0 */
};

static struct sembuf	op_op[1] = {
	{0, 99, SEM_UNDO}	/* decrement or increment [0] with undo on exit */
			/* the 99 is set to the actual amount to add
			   or subtract (positive or negative) */
};

/********************************************************************
 * Create a semaphore with a specified initial value.
 * If the semaphore alread exists, we don't initialize it (of course).
 * We return the semaphore ID if all OK, else -1.
 */

int
sem_create (key_t key, int initval)
{
	register int	id, semval;
	union semun {
		int		val;
		struct semid_ds	*buf;
		ushort		*array;
	} semctl_arg;

	if (key == IPC_PRIVATE)
		return (-1);	/* not intended for private semaphores */

	else if (key == (key_t) -1)
		return (-1);	/* probably an ftok () error by caller */

again:
	if ( (id = semget (key, 3, 0666 | IPC_CREAT)) < 0)
		return (-1);	/* permission problem or tables full */

	/*
	 * When the semaphore is created, we know that the value of all
	 * 3 members is 0.
	 * Get a lock on th esemaphore by waiting for [2] to equal 0,
	 * then increment it.
	 *
	 * There is a race comdition here.  There is a possibililty that
	 * between the semget() above and the semop() below, another
	 * process can call our sem_close () function which can remove the
	 * semaphore if that process is the last one using it.
	 * Therefore, we handle the error condition of an invalid
	 * semaphore ID specially below, and if it does happen, we
	 * just go back and create it again.
	 */
	
	if (semop (id, &op_lock[0], 2) < 0) {
		if (errno == EINVAL)
			goto again;
		err_sys ("can't lock");
	}

	/*
	 * Get the value of the process counter.  If it equals 0,
	 * then no one has initialized the semaphore yet.
	 */

	if ( (semval = semctl (id, 1, GETVAL, 0)) < 0)
		err_sys ("can't GETVAL");

	if (semval == 0)
	{	/* We could initialize by doibng a SETALL, but that
		 * would clear the adjust value that we set when we
		 * locked the semaphore above.  Instead, we'll do 2
		 * system calls to initialize [0] and [1].
		 */

		semctl_arg.val = initval;
		if (semctl (id, 0, SETVAL, semctl_arg) < 0)
			err_sys ("can't SETVAL[0]");

		semctl_arg.val = BIGCOUNT;
		if (semctl (id, 1, SETVAL, semctl_arg) < 0)
			err_sys ("can't SETVAL[1]");
	}

	/*
	 * Decrement the process counter and release the lock
	 */

	if (semop (id, &op_endcreate[0], 2) < 0)
		err_sys ("can't end create");

	return (id);
}

/********************************************************************
 * Open a semaphore that must already exist.
 * This function should be used, instead of sem_create(), if the caller
 * knows that the semaphore msust already exist.  For example a client
 * from a client-server pair would use this, if its the server's
 * responsibility to create the semaphore.
 * We return the semaphore ID if all OK, else -1.
 */

int
sem_open (key_t key)
{
	register int	id;

	if (key == IPC_PRIVATE)
		return (-1);	/* not intended for private semaphores */

	else if (key == (key_t) -1)
		return (-1);	/* probably an ftok () error by caller */

	if ( (id = semget (key, 3, 0)) < 0)
		return (-1);	/* doesn't exist, or tables full */

	/*
	 * Decrement the process counter.  We don't need a lock
	 * to do this.
	 */
	
	if (semop (id, &op_open[0], 1) < 0)
		err_sys ("can't open");

	return (id);
}

/********************************************************************
 * Remove a semaphore.
 * This call is intended to be called by a server, for example,
 * when it is being shut down , as we do an IPC_RMID on the semaphore,
 * regardless whether other process may be using it or not.
 * Most other processes should use sem_close() below.
 */

void
sem_rm (int id)
{
	if (semctl (id, 0, IPC_RMID, 0) < 0)
		err_sys ("can't IPC_RMID");
}

/********************************************************************
 * Close a semaphore.
 * Unlike the remove function above, this function is for a process
 * to call before it exits, when it is done with the semaphore.
 * We "decrement" the counter of processes using the semaphore, and
 * if this was the last one, we can remove the semaphore.
 */

void
sem_close (int id)
{
	register int	semval;

	/*
	 * The following semop() first gets a lock on the semaphore,
	 * then increments [1] - the process counter.
	 */

	if (semop (id, &op_close[0], 3) < 0)
		err_sys ("can't semop");
	
	/*
	 * Now that we have a lock, read the value of the process
	 * counter to see if this is the last reference to the
	 * semaphore.
	 * There is a race condition here - see the comments in
	 * sem_create().
	 */

	if ( (semval = semctl (id, 1, GETVAL, 0)) < 0)
		err_sys ("can't GETVAL");
	
	if (semval > BIGCOUNT)
		err_dump ("sem[1] > BIGCOUNT");
	else if (semval == BIGCOUNT)
		sem_rm(id);
	else
		if (semop (id, &op_unlock[0], 1) < 0)
			err_sys ("can't unlock");	/* unlock */
}

/********************************************************************
 * Wait until a semaphore's value is greater than 1, then decrement
 * it by 1 and return.
 * Dijkstra's P operation.  Tannenbaum's DOWN operation.
 */

void
sem_wait (int id)
{
	sem_op (id, -1);
}

/********************************************************************
 * Increment a semaphore by 1.
 * Dijkstra's V operation.  Tannenbaum's UP operation.
 */

void
sem_signal (int id)
{
	sem_op (id, 1);
}

/********************************************************************
 * General semaphore operation.  Increment or decrement by a user-specified
 * amount (positive or negative; can't be zero).
 */

void
sem_op (int id, int value)
{
	if ( (op_op[0].sem_op = value) == 0)
		err_sys ("can't have value == 0");

	if (semop (id, &op_op[0], 1) < 0)
		err_sys ("sem_op error");
}

void err_sys (char *msg)
{
	perror (msg);
	exit (-1);
}
void err_dump (char *msg)
{
	fprintf (stderr, "%s", msg);
	exit (-1);
}

simp_sem.h

#include <stdlib.h>
#include <sys/types.h>
/*
 * Provide a simpler and easier to understand interface to the System V
 * semaphore system calls.  There are 7 routines available to the user:
 *
 *	id = sem_create(key, initval);	# create with initial value or open
 *	id = sem_open(key);		# open (must already exist)
 *	sem_wait(id);			# wait = P = down by 1
 *	sem_signal(id);			# signal = V = up by 1
 *	sem_op(id, amount);		# wait   if (amount < 0)
 *					# signal if (amount > 0)
 *	sem_close(id);			# close
 *	sem_rm(id);			# remove (delete)
 *
 */


int
sem_create (key_t key, int initval);

/********************************************************************
 * Open a semaphore that must already exist.
 * This function should be used, instead of sem_create(), if the caller
 * knows that the semaphore msust already exist.  For example a client
 * from a client-server pair would use this, if its the server's
 * responsibility to create the semaphore.
 * We return the semaphore ID if all OK, else -1.
 */

int
sem_open (key_t key);

/********************************************************************
 * Remove a semaphore.
 * This call is intended to be called by a server, for example,
 * when it is being shut down , as we do an IPC_RMID on the semaphore,
 * regardless whether other process may be using it or not.
 * Most other processes should use sem_close() below.
 */

void
sem_rm (int id);


/********************************************************************
 * Close a semaphore.
 * Unlike the remove function above, this function is for a process
 * to call before it exits, when it is done with the semaphore.
 * We "decrement" the counter of processes using the semaphore, and
 * if this was the last one, we can remove the semaphore.
 */

void
sem_close (int id);

/********************************************************************
 * Wait until a semaphore's value is greater than 1, then decrement
 * it by 1 and return.
 * Dijkstra's P operation.  Tannenbaum's DOWN operation.
 */
void
sem_wait (int id);

/********************************************************************
 * Increment a semaphore by 1.
 * Dijkstra's V operation.  Tannenbaum's UP operation.
 */

void
sem_signal (int id);

/********************************************************************
 * General semaphore operation.  Increment or decrement by a user-specified
 * amount (positive or negative; can't be zero).
 */

void
sem_op (int id, int value);