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: jrp@rducky.UUCP (Jim Pickering) Newsgroups: comp.sources.misc Subject: v02i085: phil -- Example of the "Dining Philosophers" problem (System V) Message-ID: <8804030618.AA28087@csun.edu> Date: 3 Apr 88 06:18:38 GMT Sender: allbery@ncoast.UUCP Reply-To: jrp@rducky.UUCP (Jim Pickering) Lines: 675 Approved: allbery@ncoast.UUCP comp.sources.misc: Volume 2, Issue 85 Submitted-By: "Jim Pickering" Archive-Name: phil comp.sources.misc: Volume 2, Issue 85 Submitted-By: "Jim Pickering" 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 X#include X#include X#include X#include X#include 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; isem_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