The following program, which can DOWNLOAD
HERE, is a working implementation of the semaphores
example from your textbook. Get it working in Linux (not Minix) by using
the following:
gcc prod_cons.c
./a.out
You should actually run this program many times (a few
dozen) and note how it occasionally lets the producer have a long run
followed by a long run for the consumer. Here is a hardcopy of the code:
/* Example: Three semaphores used to solve the Producer-Consumer Problem */
/*
This program was mostly written by Marcus Fink and displayed at his
website: http://www.marcus.fink.dk/index.html for general usage.
Michael Rieck made a few alterations, reorganizing the code and adding
another semaphore (Mutex). This is a working implementation of the
example in Figure 2-14 (page 80) of Tannenbaum and Woodhull (3rd ed.),
using the System V (Unix) IPC facilities (in "linux" directory here).
*/
#include < stdlib.h>
#include < stdio.h>
#include < unistd.h>
#include < sys/types.h>
#include < sys/ipc.h>
#include < sys/sem.h>
#include < sys/shm.h>
/* NOTE: Need to remove excess spaces in between angle brackets in the above. */
#define NUM_ELEM 10 /* Number of elements in shared memory buffer */
#define SEM_MUTEX 0
#define SEM_EMPTY 1
#define SEM_FULL 2
int rc, semID, shmID, status, i;
char elem;
union semun
{
int val;
struct semid_ds *buf;
ushort *array;
} seminfo;
struct sembuf WaitMutex={SEM_MUTEX, -1, 0};
struct sembuf SignalMutex={SEM_MUTEX, 1, 0};
struct sembuf WaitEmpty={SEM_EMPTY, -1, 0};
struct sembuf SignalEmpty={SEM_EMPTY, 1, 0};
struct sembuf WaitFull={SEM_FULL, -1, 0};
struct sembuf SignalFull={SEM_FULL, 1, 0};
struct shmid_ds shminfo;
char *shmPtr;
void initialize();
void producer();
void consumer();
main()
{
/* Initialize shared memory and semaphores */
initialize();
/* Start a child process and proceed accordingly*/
if (fork()==0)
{
/* Child becomes the consumer */
consumer();
/* Child quits after consuming 26 characters */
exit(0);
}
else
{
/* Parent becomes the producer */
producer();
/* Returns after producing 26 characters */
/* Wait for child to finish */
wait(&status);
/* Remove shared memory */
shmctl(shmID, IPC_RMID, &shminfo);
/* Remove semaphores */
semctl(semID, SEM_MUTEX, IPC_RMID, seminfo);
/* Parent is done cleaning up, so now quits */
exit(0);
}
}
void initialize()
{
/* Init semaphores */
/* Three semaphores (Empty, Full, Mutex) are created in one set */
semID=semget(IPC_PRIVATE, 3, 0666 | IPC_CREAT);
/* Init Mutex to one, allowing access to critical section */
seminfo.val=1;
semctl(semID, SEM_MUTEX, SETVAL, seminfo);
/* Init Empty to number of elements in shared memory (circular buffer) */
seminfo.val=NUM_ELEM;
semctl(semID, SEM_EMPTY, SETVAL, seminfo);
/* Init Full to zero, no elements are produced yet */
seminfo.val=0;
semctl(semID, SEM_FULL, SETVAL, seminfo);
/* Init Shared memory */
shmID=shmget(IPC_PRIVATE, NUM_ELEM, 0666 | IPC_CREAT);
}
void producer()
{
/* attach shared memory to process */
shmPtr=(char*)shmat(shmID, 0, SHM_W);
for(i=0; i < 26; i++)
{
/* Wait(Empty) - pause if no empty spots in circular buffer (i.e. all filled) */
semop(semID, &WaitEmpty, 1);
/* Produce element. Example element are chars 'a'-'z' */
elem='a'+i;
printf("Produced elem '%c'\n", elem);
/* Wait(Mutex) - don't touch shared memory while consumer is using it */
semop(semID, &WaitMutex, 1);
/* Put element into shared memory buffer (circular buffer) */
*(shmPtr + (i%NUM_ELEM))=elem;
/* Signal(Mutex) - allow consumer to access shared memory now */
semop(semID, &SignalMutex, 1);
/* Signal(Full) - record one more filled spot in circular buffer */
semop(semID, &SignalFull, 1);
}
}
void consumer()
{
/* attach shared memory to process */
shmPtr=(char*)shmat(shmID, 0, SHM_R);
for(i=0; i < 26; i++)
{
/* Wait(Full) - pause if no filled spots in circular buffer (i.e. all empty) */
semop(semID, &WaitFull, 1);
/* Wait(Mutex) - don't touch shared memory while producer is using it */
semop(semID, &WaitMutex, 1);
/* Get element from the shared memory buffer (circular buffer) */
elem=*(shmPtr + (i%NUM_ELEM));
/* Signal(Mutex) - allow producer to access shared memory now */
semop(semID, &SignalMutex, 1);
/* Display character */
printf(" Consumed elem '%c'\n", elem);
/* Signal(Empty) - record one more empty spot in circular buffer */
semop(semID, &SignalEmpty, 1);
}
}
Implement the solution to the Sleeping Barber problem (see handout) using a
single barber, NUM_CUSTOMERS customers and NUM_CHAIRS chairs. Actually, implement a
slight enhancement using four semaphores as in the following pseudocode:
#define NUM_CUSTOMERS 10
#define NUM_CHAIRS 2
semaphore mutex = 1; // control access to shared variable
semaphore customers = 0; // count number customers waiting
semaphore barberReady = 0; // is barber ready to cut somebody's hair?
semaphore haircutDone = 0; // is barber done cutting somebody's hair?
int numberWaiting = 0; // shared variable
// (called "waiting" in book)
// (same as customers's value)
void barber()
{
for(i=0; i < NUM_CUSTOMERS; i++) {
wait(customers);
wait(mutex);
numberWaiting--;
signal(mutex);
signal(barberReady);
sleep(2); // pretend to cut hair for a while
signal(haircutDone);
}
}
void customer(int cid) // pass customer ID (1,2,3,...)
{
int gotHaircut = 0;
srand(cid); // seed for random number generator
do {
sleep(rand()%10) // wait before seeking haircut
wait(mutex)
if (waiting < NUM_CHAIRS) {
waiting++;
signal(mutex);
signal(customers);
wait(barberReady);
// will be getting a haircut now
wait(haircutDone);
gotHaircut = 1;
} else {
signal(mutex);
}
} while (!gotHaircut)
}
When testing your program, define NUM_CHAIRS to be two, and NUM_CUSTOMERS to be ten.
Notice in the Sleeping Barber problem, apart from semaphores, only a single integer variable
(waiting in the pseudocode) needs to be shared among the process.
This can be initialized in the actual code as follows:
shmID=shmget(IPC_PRIVATE, sizeof(int), 0666 | IPC_CREAT);
waitingPtr=(int*)shmat(shmID, 0, SHM_R | SHM_W);
*waitingPtr = 0; // initialize "waiting" counter
Note that *waitingPtr in the actual code takes the place of waiting in the
pseudocode. Also note that SHM_R | SHM_W is used to make it possible to read from and
write to the shared variable *waitingPtr.
The original process should serve as the barber here, and it should spawn
NUM_CUSTOMERS child processes to serve as customers. This can
be accomplished by making your main function look like so:
...
for (i = 0; i < NUM_CUSTOMERS; i++)
if ((pid=fork()) == 0) break;
if (pid == 0)
{
customer(i+1);
exit(0);
} else {
barber()
...
}
Just before terminating, the parent process should use a loop to execute wait
(see example in first part of this assignment), in order to wait on a child process to
terminate, NUM_CUSTOMERS times.
Lastly, you should include several print statements, judiciously placed, to show how
the simulation is proceeding. The following is a sample run from my Sleeping Barber
program. Yours should behave in a similar way. (Notice what happens to poor Customer 8.
I'm sure I've had this experience somewhere sometime myself.) Statements about the
barber should be printed by the parent process. Statements about a customer should be
printed by a child process.
Customer 2 waiting (1 customers waiting)
Barber ready
Customer 2 starting haircut
Barber cutting
Customer 4 waiting (1 customers waiting)
Customer 6 waiting (2 customers waiting)
Customer 2 got haircut
Barber ready
Customer 4 starting haircut
Barber cutting
Customer 1 waiting (2 customers waiting)
Customer 4 got haircut
Barber ready
Customer 6 starting haircut
Barber cutting
Customer 5 waiting (2 customers waiting)
Customer 9 will come back later
Customer 10 will come back later
Customer 3 will come back later
Customer 8 will come back later
Customer 6 got haircut
Barber ready
Customer 1 starting haircut
Barber cutting
Customer 7 waiting (2 customers waiting)
Customer 1 got haircut
Barber ready
Customer 5 starting haircut
Barber cutting
Customer 9 waiting (2 customers waiting)
Customer 8 will come back later
Customer 5 got haircut
Barber ready
Customer 7 starting haircut
Barber cutting
Customer 3 waiting (2 customers waiting)
Customer 8 will come back later
Customer 7 got haircut
Barber ready
Barber cutting
Customer 9 starting haircut
Customer 10 waiting (2 customers waiting)
Barber ready
Customer 9 got haircut
Customer 3 starting haircut
Barber cutting
Customer 3 got haircut
Barber ready
Barber cutting
Customer 10 starting haircut
Customer 10 got haircut
Customer 8 waiting (1 customers waiting)
Barber ready
Barber cutting
Customer 8 starting haircut
Customer 8 got haircut
Barber is going home