jrp@rducky.UUCP (Jim Pickering) (04/03/88)
Submitted-By: "Jim Pickering" <jrp@rducky.UUCP>
Archive-Name: phil
comp.sources.misc: Volume 2, Issue 85
Submitted-By: "Jim Pickering" <jrp@rducky.UUCP>
Archive-Name: phil
[An example of the "dining philosophers" problem in process synchronization,
implemented via System V semaphores. Should be educational both with regard
to process synchronization and to semaphore usage. ++bsa]
#--------------------------------CUT HERE-------------------------------------
#! /bin/sh
#
# This is a shell archive. Save this into a file, edit it
# and delete all lines above this comment. Then give this
# file to sh by executing the command "sh file". The files
# will be extracted into the current directory owned by
# you with default permissions.
#
# The files contained herein are:
#
# -rw-r--r-- 1 jrp users 27897 Apr 2 15:14 phil.c
#
echo 'x - phil.c'
if test -f phil.c; then echo 'shar: not overwriting phil.c'; else
sed 's/^X//' << '________This_Is_The_END________' > phil.c
X/***********************************************************************/
X/** PHIL.C **/
X/** **/
X/** (c) COPYRIGHT 1988 **/
X/** JAMES R. PICKERING **/
X/** ALL RIGHTS RESERVED **/
X/** **/
X/** Jim Pickering || (n) ..csustan!polyslo!rducky!jrp **/
X/** || (s) ..sdsu!polyslo!rducky!jrp **/
X/** Arroyo Grande, CA 93420 || jrp@rducky.UUCP **/
X/** (805) 473-1037 **/
X/** **/
X/** DESCRIPTION: This file contains a program which demonstrates **/
X/** Dijkstra's Dining Philosophers Problem (see "Cooperating **/
X/** Sequential Processes," Technical Report EWD-123, Technological **/
X/** University, Eindhoven, The Netherlands, (1965)). It is con- **/
X/** sidered a classic process synchronization problem. It is **/
X/** implemented using SVR2 semaphores and curses. With this as an **/
X/** example, you may be able to figure out how to use SV semaphores.**/
X/** **/
X/** PROBLEM DESCRIPTION: Five philosophers spend their lives **/
X/** thinking and eating. They share a common table. Each has his/ **/
X/** her own chair. At the center of the table is a bowl of rice. **/
X/** The table is laid with five chopsticks (see figure below). When**/
X/** a philosopher thinks, he/she (the hell with this he/she crap ...**/
X/** all philosophers referenced furthur are hermaphrodites and will **/
X/** be refered to as 'he') does not eat, and vice versa. When a **/
X/** philosopher is hungry he tries to pick up the two chopsticks **/
X/** that are closest to him. He may only pick up one stick at a **/
X/** time. When he has both chopsticks, he eats without releasing **/
X/** his chopsticks. When he is finished eating, he puts down both **/
X/** chopsticks and starts thinking. **/
X/** **/
X/** PHIL1 | PHIL2 **/
X/** \ / **/
X/** **/
X/** PHIL5 (rice) PHIL3 **/
X/** **/
X/** **/
X/** / PHIL4 \ **/
X/** **/
X/** COMPILE: cc -O -s -o phil phil.c -lcurses **/
X/***********************************************************************/
X/** FUNCTIONS: **/
X/** void clean_die() **/
X/** void die() **/
X/** void sleeper() **/
X/** void hungry(p_num) **/
X/** int p_num; **/
X/** void thinking(p_num) **/
X/** int p_num; **/
X/** void eating(p_num) **/
X/** int p_num; **/
X/** void killit(semid,array_ptr) **/
X/** int semid, *array_ptr; **/
X/** void cleanup() **/
X/** void printit(p_num,action) **/
X/** int p_num, action; **/
X/** bool V_semaphore(sem_num) **/
X/** int sem_num; **/
X/** bool P_semaphore(sem_num,block) **/
X/** int sem_num; **/
X/** bool block; **/
X/***********************************************************************/
X
Xstatic char philc[] = "@(#)phil1.c 1.1 JAMES R. PICKERING 3/23/88";
X
X#include <sys/types.h>
X#include <sys/ipc.h>
X#include <sys/sem.h>
X#include <curses.h>
X#include <signal.h>
X#include <errno.h>
X
X#define NUM_CHILDREN 5 /* number of dining philosophers */
X /* don't change this!!!!!!!!!!!! */
X /* the display routines depend on */
X /* this. */
X
X#define SLEEP_TIME 10 /* maximum amount of time (minus 1)
X in seconds the child processes
X eat and think. */
X
X#define EATING 1
X#define THINKING 2
X#define HAS_ONE 3
X#define HUNGRY 4
X
Xvoid die();
Xvoid clean_die();
Xvoid sleeper();
Xvoid hungry();
Xvoid thinking();
Xvoid eating();
Xvoid killit();
Xvoid cleanup();
Xvoid printit();
Xbool V_semaphore();
Xbool P_semaphore();
X
Xint semid; /* the semaphore set id */
Xint pid_array[NUM_CHILDREN]; /* array of children's pids */
X
Xmain()
X{
X
X /************************************************/
X /*variable declarations for semaphore definition*/
X /************************************************/
X
X key_t key;
X int opperm, nsems;
X int opperm_flags;
X
X /****************************************************/
X /*variable declarations for semaphore initialization*/
X /****************************************************/
X
X struct semid_ds semid_ds;
X int i, length;
X int retrn;
X union semnum
X {
X int val;
X struct semid_ds *buf;
X ushort array[25];
X } arg;
X
X
X /*******************************************************/
X /*variable declarations for dining philosophers problem*/
X /*******************************************************/
X
X int p_num;
X
X /***********************************/
X /*get a semaphore set from the O.S.*/
X /***********************************/
X
X key = IPC_PRIVATE;
X opperm = 0600;
X opperm_flags = (opperm | IPC_CREAT | IPC_EXCL);
X nsems = NUM_CHILDREN;
X if((semid = semget(key,nsems,opperm_flags)) == -1)
X {
X perror("The semget call failed with semget(key,nsems,opperm_flags).");
X exit(0);
X }
X
X /************************************************/
X /*initialize the five semaphores in the set to 1*/
X /************************************************/
X
X arg.buf = &semid_ds;
X if ((retrn = semctl(semid,0,IPC_STAT,arg.buf)) == -1)
X {
X perror("The semctl call failed on finding the number of semaphores with semctl(semid,0,IPC_STAT,arg.buf).");
X exit(0);
X }
X length = arg.buf -> sem_nsems;
X for (i=0; i<length; i++)
X arg.array[i] = 1;
X if ((retrn = semctl(semid,0,SETALL,arg.array)) == -1)
X {
X perror("The semctl call failed on initializing the semaphores with semctl(semid,0,SETALL,arg.array).");
X exit(0);
X }
X
X /**********************************************/
X /*fork off five dining philosophers (children)*/
X /**********************************************/
X
X for (i=1; i<=NUM_CHILDREN; i++)
X {
X if ((pid_array[i-1] = fork()) == 0)
X {
X initscr();
X (void)signal(SIGHUP,clean_die);
X (void)signal(SIGQUIT,clean_die);
X (void)signal(SIGINT,clean_die);
X refresh();
X (void)sleep(2);
X srand((unsigned)time((long *)0));
X p_num = i;
X
X /**************************************************************/
X /*philosopher (child) thinks, becomes hungry, eats, thinks ...*/
X /**************************************************************/
X
X while(TRUE)
X {
X thinking(p_num);
X hungry(p_num);
X eating(p_num);
X }
X }
X }
X /****************************/
X /*parent waits for interrupt*/
X /****************************/
X (void)signal(SIGHUP,die);
X (void)signal(SIGINT,die);
X (void)signal(SIGQUIT,die);
X while(TRUE)
X ;
X}
X
X
X/**********************************************************************/
X/**FUNCTION: clean_die() **/
X/** **/
X/**DESCRIPTION: This function calls cleanup (ends curses) and exits.**/
X/** It only is called by the children. **/
X/** **/
X/**GLOBAL VARIABLES: none @ **/
X/** **/
X/**GLOBAL CONSTANTS: none **/
X/** **/
X/**CALLS: cleanup() **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid clean_die()
X{
X cleanup();
X exit(0);
X}
X
X
X/**********************************************************************/
X/**FUNCTION: die() **/
X/** **/
X/**DESCRIPTION: This function is called by the parent and sends its **/
X/** children a signal through killit and then exits. **/
X/** **/
X/**GLOBAL VARIABLES: semid, pid_array **/
X/** **/
X/**GLOBAL CONSTANTS: none **/
X/** **/
X/**CALLS: killit() **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid die()
X{
X killit(semid,pid_array);
X exit(0);
X}
X
X
X/**********************************************************************/
X/**FUNCTION: sleeper() **/
X/** **/
X/**DESCRIPTION: This function randomly sleeps from 0 to **/
X/** (SLEEP_TIME-1) seconds. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: SLEEP_TIME **/
X/** **/
X/**CALLS: none **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid sleeper()
X{
X (void)sleep(rand() % SLEEP_TIME);
X}
X
X
X/**********************************************************************/
X/**FUNCTION: hungry() **/
X/** **/
X/**DESCRIPTION: This function is representative of a philosopher **/
X/** being hungry. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: HUNGRY **/
X/** **/
X/**CALLS: printit() **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid hungry(p_num)
X int p_num;
X{
X printit(p_num,HUNGRY);
X}
X
X
X/**********************************************************************/
X/**FUNCTION: thinking() **/
X/** **/
X/**DESCRIPTION: This function is representative of a philosopher **/
X/** thinking for a random amount of time. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: THINKING **/
X/** **/
X/**CALLS: printit(), sleeper(), **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid thinking(p_num)
X int p_num;
X{
X printit(p_num,THINKING);
X sleeper();
X}
X
X
X/**********************************************************************/
X/**FUNCTION: eating() **/
X/** **/
X/**DESCRIPTION: This function is representative of a philosopher **/
X/** eating for a random amount of time. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: NUM_CHILDREN, EATING, HAS_ONE **/
X/** **/
X/**CALLS: printit(), P_semaphore(), V_semaphore(), sleeper(), **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid eating(p_num)
X int p_num;
X{
X int n = NUM_CHILDREN;
X
X if (!(p_num % 2))
X
X /************************************************/
X /*even philosopher--choose right chopstick first*/
X /* to prevent deadlock */
X /************************************************/
X
X {
X
X /******************************/
X /*P(right chopstick) operation*/
X /******************************/
X
X if (!P_semaphore(p_num-1,TRUE))
X {
X exit(0);
X }
X printit(p_num,HAS_ONE);
X
X /*****************************/
X /*P(left chopstick) operation*/
X /*****************************/
X
X if (!P_semaphore(p_num%n,TRUE))
X {
X (void)V_semaphore(p_num-1);
X exit(0);
X }
X
X /***************************************/
X /*philosopher's critical section begins*/
X /***************************************/
X
X printit(p_num,EATING);
X sleeper();
X
X /*************************************/
X /*Philosopher's critical section ends*/
X /*************************************/
X
X
X /******************************/
X /*V(right chopstick) operation*/
X /******************************/
X
X if(!V_semaphore(p_num-1))
X {
X (void)kill(getppid(),SIGHUP);
X exit(0);
X }
X
X /*****************************/
X /*V(left chopstick operation)*/
X /*****************************/
X
X if(!V_semaphore(p_num%n))
X {
X (void)kill(getppid(),SIGHUP);
X exit(0);
X }
X }
X else
X
X /**********************************************/
X /*odd philosopher--choose left chopstick first*/
X /* to prevent deadlock */
X /**********************************************/
X
X {
X
X /*****************************/
X /*P(left chopstick operation)*/
X /*****************************/
X
X if (!P_semaphore(p_num%n,TRUE))
X {
X exit(0);
X }
X printit(p_num,HAS_ONE);
X
X /*****************************/
X /*P(right chopstick operation*/
X /*****************************/
X
X if (!P_semaphore(p_num-1,TRUE))
X {
X (void)V_semaphore(p_num%n);
X exit(0);
X }
X
X /***************************************/
X /*philosopher's critical section begins*/
X /***************************************/
X
X printit(p_num,EATING);
X sleeper();
X
X /*************************************/
X /*philosopher's critical section ends*/
X /*************************************/
X
X
X /*****************************/
X /*V(left chopstick) operation*/
X /*****************************/
X
X if(!V_semaphore(p_num%n))
X {
X (void)kill(getppid(),SIGHUP);
X exit(0);
X }
X
X /*****************************/
X /*V(right chopstick) operation*/
X /*****************************/
X
X if(!V_semaphore(p_num-1))
X {
X (void)kill(getppid(),SIGHUP);
X exit(0);
X }
X }
X}
X
X
X/**********************************************************************/
X/**FUNCTION: killit() **/
X/** **/
X/**DESCRIPTION: This function is used by the parent to kill its **/
X/** children and remove the semaphore set. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: NUM_CHILDREN **/
X/** **/
X/**CALLS: none **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid killit(semid,array_ptr)
X int semid, *array_ptr;
X{
X int i;
X
X for (i=0; i<NUM_CHILDREN; i++)
X (void)kill(array_ptr[i],SIGHUP);
X (void)semctl(semid,0,IPC_RMID,0);
X}
X
X
X/**********************************************************************/
X/**FUNCTION: cleanup() **/
X/** **/
X/**DESCRIPTION: This function cleans up curses for the children. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: none **/
X/** **/
X/**CALLS: none **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid cleanup()
X{
X endwin();
X}
X
X
X/**********************************************************************/
X/**FUNCTION: printit() **/
X/** **/
X/**DESCRIPTION: This function print the childrens' actions. **/
X/** **/
X/**GLOBAL VARIABLES: none **/
X/** **/
X/**GLOBAL CONSTANTS: EATING, THINKING, HAS_ONE, HUNGRY **/
X/** **/
X/**CALLS: none **/
X/** **/
X/**RETURNS: none **/
X/**********************************************************************/
Xvoid printit(p_num,action)
X int p_num, action;
X{
X int x, y;
X char string[128];
X
X switch(action)
X {
X case EATING : (void)sprintf(string,"Philosopher %d is eating...",p_num);
X break;
X case THINKING : (void)sprintf(string,"Philosopher %d is thinking...",p_num);
X break;
X case HAS_ONE : if(!(p_num % 2))
X (void)sprintf(string,"Philosopher %d is hungry & has right chopstick...",p_num);
X else
X (void)sprintf(string,"Philosopher %d is hungry & has left chopstick...",p_num);
X break;
X case HUNGRY : (void)sprintf(string,"Philosopher %d is hungry...",p_num);
X break;
X default : return;
X }
X switch(p_num)
X {
X case 1: y = 2;
X x = 6;
X break;
X case 2 : y = 3;
X x = COLS - strlen(string) - 6;
X break;
X case 3 : y = LINES/2;
X x = COLS - strlen(string) - 2;
X break;
X case 4 : y = LINES - 2;
X x = COLS/2 - strlen(string)/2;
X break;
X case 5 : y = LINES/2 - 1;
X x = 2;
X break;
X default : return;
X }
X move(0,0);
X refresh();
X move(y,0);
X clrtoeol();
X mvaddstr(y,x,string);
X refresh();
X}
X
X
X/*************************************************************************/
X/**FUNCTION: V_semaphore() **/
X/** **/
X/**DESCRIPTION: This function releases the named semaphore in the set.**/
X/** It is called after a process leaves its critical section which is **/
X/** associated with 'sem_num'. **/
X/** **/
X/**GLOBAL VARIABLES: semid **/
X/** **/
X/**GLOBAL CONSTANTS: NUM_CHILDREN **/
X/** **/
X/**CALLS: cleanup() **/
X/** **/
X/**RETURNS: TRUE on success, otherwise FALSE. **/
X/*************************************************************************/
Xbool V_semaphore(sem_num)
X int sem_num;
X{
X int retrn;
X struct sembuf sembuf[NUM_CHILDREN], *sops;
X unsigned nsops = 1;
X
X sops = sembuf;
X sops->sem_num = sem_num;
X sops->sem_op = 1;
X sops->sem_flg = 0;
X if((retrn = semop(semid, sops, nsops)) == -1)
X {
X cleanup();
X perror("error with semop(semid,sops,nsops) in V_semaphore()");
X return(FALSE);
X }
X return(TRUE);
X}
X
X
X/*************************************************************************/
X/**FUNCTION: P_semaphore() **/
X/** **/
X/**DESCRIPTION: This function waits on the named semaphore in the set.**/
X/** It either blocks or not depending on 'block'. It is called **/
X/** before a process enters its critical section which is associated **/
X/** with 'sem_num'. **/
X/** **/
X/**GLOBAL VARIABLES: semid **/
X/** **/
X/**GLOBAL CONSTANTS: NUM_CHILDREN **/
X/** **/
X/**CALLS: cleanup() **/
X/** **/
X/**RETURNS: TRUE on success, FALSE otherwise--if block; TRUE if got **/
X/** semaphore, FALSE if not or error--if !block. **/
X/*************************************************************************/
Xbool P_semaphore(sem_num,block)
X int sem_num;
X bool block;
X{
X int retrn, flags = IPC_NOWAIT;
X struct sembuf sembuf[NUM_CHILDREN], *sops;
X unsigned nsops = 1;
X extern int errno;
X
X sops = sembuf;
X if(block)
X flags = 0;
X else
X errno = 0;
X sops->sem_num = sem_num;
X sops->sem_op = -1;
X sops->sem_flg = flags;
X if((retrn = semop(semid, sops, nsops)) == -1)
X {
X if(errno == EAGAIN) /* !block && didn't get semaphore */
X return(FALSE);
X cleanup();
X perror("error with semop(semid,sops,nsops) in P_semaphore()");
X return(FALSE);
X }
X return(TRUE);
X}
X
X
________This_Is_The_END________
if test `wc -l < phil.c` -ne 645; then
echo 'shar: phil.c was damaged during transit (should have been 645 bytes)'
fi
fi ; : end of overwriting check
exit 0