Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/compsrcs/misc/volume02/phil

Internet Message Format | 1991-08-27 | 29.6 KB

From mipos3!omepd!littlei!uunet!husc6!necntc!ncoast!allbery Sat Apr  9 16:59:52 PDT 1988
Article 338 of comp.sources.misc:
Path: td2cad!mipos3!omepd!littlei!uunet!husc6!necntc!ncoast!allbery
From: [e-mail] (Jim Pickering)
Newsgroups: comp.sources.misc
Subject: v02i085: phil -- Example of the "Dining Philosophers" problem (System V)
Message-ID: <[e-mail]>
Date: 3 Apr 88 06:18:38 GMT
Sender: [e-mail]
Reply-To: [e-mail] (Jim Pickering)
Lines: 675
Approved: [e-mail]
comp.sources.misc: Volume 2, Issue 85
Submitted-By: "Jim Pickering" <[e-mail]>
Archive-Name: phil

comp.sources.misc: Volume 2, Issue 85
Submitted-By: "Jim Pickering" <[e-mail]>
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     ||       [e-mail]              **/
X/** [phone]                                                    **/
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