This assignment is intended to help you put into practice the concepts of process coordination and resource sharing by building a rudimentary message passing mechanism between multiple processes. For this assignment you will again use facilities of the Unix Operating System. In particular you will use semaphore and shared memory primitives.
The assignment is motivated by a common technique used in parallel and distributed computing to distribute a large computation among many processes (ideally on different processors) and then combining the results. In this project you will be using multiple processes in different ways to sum together all the integers in a given range. The processes will communicate with each other using the message passing mechanism you build.
The basic idea of this assignment is to create a number of processes and to associate with each process a ``mailbox'' where a single message for each process can be stored. Because one process may be trying to store a message in another's mailbox that already contains a message, you will need to use semaphores in order to control access to each process' mailbox. The total number of processes in your program should be controlled by a #define statement at the beginning of your program. You should use the constant NUMPROC to designate the total number of processes. So as to not use too many system resources you should use
#define NUMPROC 4This constant is the total number of processes your program will have (this number includes the parent process). Your program must work for any number of processes as defined by NUMPROC. The parent process in your program will be known as ``process 0'' with processes 1 to NUMPROC-1 being child processes forked off by the parent process using the UNIX system call fork(). You should create a routine CreateProcess() that is similar to the version discussed in class with an additional parameter to be passed to the routine. You might call the routine executed by the child adder() because it will add numbers. Thus to create the ith child process you would use
CreateProcess(adder, i); /* need to add error checking */
Associated with each process is a mailbox. A mailbox contains a message that is defined by the following C structure:
struct msg {
int iFrom; /* who sent the message */
int wType; /* 0=request, 1=result, -1=termination */
int wVal1; /* initial value in range */
int wVal2; /* final value in range */
int wTotal; /* total of all numbers in range */
};
Because each process has one mailbox associated with it, you should create an array of mailboxes (of length NUMPROC) to store one message for each process. Because mailboxes must be shared by all processes these mailboxes must be created as shared memory by the parent process before it forks off any child processes. Shared memory is created with the library routine shmcreate() (see below), which is available for this assignment. If the array of mailboxes is declared as
struct msg *rgpMsg[NUMPROC]; /* array of message pointers */where rgpMsg is an array of pointers to messages then the statement
rgpMsg[i] = (struct msg *)shmcreate(sizeof(struct msg));could be used to create shared memory for the ith mailbox. The C sizeof operator returns the size (in bytes) of the given structure. The use of (struct msg *) casts the value returned by shmcreate() to be a message pointer (as required for rgpMsg[i]). To access the first value field of this message the expression rgpMsg[i]->wVal1 would be used (remember rgpMsg[i] is a pointer to a structure not an actual structure thus the use of ``->'' rather than ``.'').
Similarly, semaphores should be created to control access to each mailbox. These semaphores should be created using the routine screate() that is supplied for this assignment (see below). These semaphores should also be created by the parent process before it forks the children. All creation of shared memory and semaphores for the mailboxes should be done in the routine InitMailbox(), which you need to write.
To handle access to each process' mailbox you must write two procedures: SendMsg() and RecvMsg(). These procedures have the following interfaces
SendMsg(int iTo, struct msg *pMsg) /* iTo - mailbox to send to */ /* pMsg - message to be sent */ RecvMsg(int iFrom, struct msg *pMsg) /* iFrom - mailbox to receive from */ /* pMsg - message structure to fill in with received message */The index of a process is simply its number so the index of the parent process is zero, the first child process is one, etc. Each process must have its own index. The SendMsg() routine should block if another message is already in the recipient's mailbox. Similarly, the RecvMsg() routine should block if no message is available in the mailbox.
After creating all shared memory, semaphores, and forking off the child processes your program will use three command line arguments (all integers) to determine how it functions. The first and second values determine a range of integers your program is to sum together for its output. The last value is the maximum number (maxrange) of integers that a single process can sum together at a time.
The parent process controls all the other processes by sending them ``work'' in the form of a range of numbers to add together (no range can be larger than maxrange). Thus if the range of numbers is 1-95 and maxrange is 10 then the parent process initially sends range 1-10 to process 1, 11-20 to process 2 and 21-30 to process 3. Whenever a worker process sends backs its result and more numbers need to be added then the parent process sends the next range of numbers (in this case 31-40) to the newly available process. This distribution of work continues until the parent has come to the end of its range at which time it sends out no more requests.
When the parent process has received back all results and printed out the sum of all integers in its range, it should send a termination message (message with wType of -1) to each child process. After sending a termination message it should wait for as many messages as there are children. Each child should send back a message indicating the number of integers it added together and then terminate itself. The final task of the parent process is to cleanup all resources (shared memory and semaphores) using the routine CleanupResources() that you must write. This routine should be called before the parent processes exits. The routine should use shmdelete() and sdelete() to cleanup resources.
Each child process should sum up range of numbers that it receives. It uses the routine RecvMsg() to wait for messages. For example, the ith process would use RecvMsg(i, &msg) where message is declared as
struct msg msg; /* message structure to contain received message */If the type of a message is a request then the child process adds the given range of numbers and sends the result back to the parent then waits for the next request. To simulate processors of different speed each process should delay before sending the result back to the parent process (using Unix library call sleep(3)). Each process should delay the number of seconds corresponding to its identifier (i.e. 1 second for process 1, 2 seconds for process 2 and 3 seconds for process 3). If the type of a received message is -1 then the child process quits receiving messages and immediately (it does not sleep here) sends the total number of integers it has added together back to the parent (process 0). The child process then exits.
Sample output of the program for a range of 1-95 and maxrange of 10 would be as below (the order of the lines may vary depending on the order of messages received by the parent).
% mailbox 1 95 10 Process 0 sending 1-10 to Process 1 Process 0 sending 11-20 to Process 2 Process 0 sending 21-30 to Process 3 Process 0 receives 1-10 from Process 1 (55) Process 0 sending 31-40 to Process 1 Process 0 receives 11-20 from Process 2 (155) Process 0 sending 41-50 to Process 2 Process 0 receives 31-40 from Process 1 (355) Process 0 sending 51-60 to Process 1 Process 0 receives 21-30 from Process 3 (255) Process 0 sending 61-70 to Process 3 Process 0 receives 51-60 from Process 1 (555) Process 0 sending 71-80 to Process 1 Process 0 receives 41-50 from Process 2 (455) Process 0 sending 81-90 to Process 2 Process 0 receives 71-80 from Process 1 (755) Process 0 sending 91-95 to Process 1 Process 0 receives 91-95 from Process 1 (465) Process 0 receives 61-70 from Process 3 (655) Process 0 receives 81-90 from Process 2 (855) Total of the range 1-95 is 4560 Process 1 added 45 integers Process 2 added 30 integers Process 3 added 20 integers
In summary, the routines you must write with the given interface:
For the program, you should proceed by initially fixing NUMPROC to two so there is just one producer of messages (the parent) and just one consumer (a child). After getting your program to work then increase the value NUMPROC to four. If your program is written correctly then you will only need to change the #define statement. Access to a mailbox is just a producer/consumer problem. Your implementation of SendMsg() and RecvMsg() should be similar to implementations of this problem that we have looked at in class.
Satisfactory completion of the basic objective of this assignment is worth 27 of the 30 points. For three additional points, you need to implement a revised method of distributing the work. In this approach assume that the parent process a priori only knows about Process 1. When given a range of numbers to add together it should send 2/3 of the range to Process 1 to sum and keep 1/3 itself to sum. When Process 1 receives a range to sum it should send 2/3 of its range to Process 2 and keep 1/3 of the range for itself. Similarly, Process 2 should keep 1/3 of its range and send 2/3 of the range to Process 3. Since there are no more processes, Process 3 must sum all the integers it receives.
As in the basic part of the assignment each process can sum no more than maxrange integers together and then it must delay (assume there are no delays when summing integers in the parent process). When a process finishes with a summation then it should send the result to Process 0. When the parent process has received all range summations (note: the parent process will need to keep track of which ranges it has received because it does not know the total number of result messages to expect) then it sends a termination message to Process 1. Process 1 propagates the message to Process 2 and Process 2 propagates to Process 3. All processes report the number of integers they summed as in the basic part.
The main program should use this method for distribution if the command line has four arguments and the last argument is ``add.'' The output you should receive for this portion of the project with the following command line is:
% mailbox 1 95 10 add Process 0 sending 1-63 to Process 1 Process 0 added 64-95 (2544) Process 1 sending 1-42 to Process 2 Process 2 sending 1-28 to Process 3 Process 0 receives 43-52 from Process 1 (475) Process 0 receives 29-38 from Process 2 (335) Process 0 receives 53-62 from Process 1 (575) Process 0 receives 1-10 from Process 3 (55) Process 0 receives 63-63 from Process 1 (63) Process 0 receives 39-42 from Process 2 (162) Process 0 receives 11-20 from Process 3 (155) Process 0 receives 21-28 from Process 3 (196) Total of the range 1-95 is 4560 Process 1 added 21 integers Process 2 added 14 integers Process 3 added 28 integers
To simplify use of shared memory and semaphores in this assignment, library routines to create and manipulate underlying Unix primitives have been provided. The semaphore routines are modeled on the Xinu semaphore routines with our version of signal() and wait() called ssignal() and swait() to avoid interference with the Unix system calls by these names. The object file containing these primitives is /cs/cs3013/public/lib/sem.o available on the CCC DECstations. A header file containing prototype definitions for the routines is /cs/cs3013/public/lib/sem.h. The makefile in /cs/cs3013/public/lib/Makefile can be used to make the executable file mailbox using the public version of sem.o. You should copy this makefile to your directory (more on makefiles shortly). You SHOULD NOT copy the file sem.o. The routines provided in sem.o are:
/* * swait() - wait on the given semaphore. Return -1 on error, zero on * success. */ swait(int sem) /* * swaitn() - wait on the given semaphore for the given count. Return -1 on * error, zero on success. */ swaitn(int sem, int cnt) /* * ssignal() - signal the given semaphore. Returns -1 on failure. */ ssignal(int sem) /* * ssignaln() - signal the given semaphore, the given number of times. Returns * -1 on failure. */ ssignaln(int sem, int cnt)
/* * screate() - create a semaphore with the given initial count. Returns -1 * on failure, a semaphore id on success. We have imposed a limit of 15 * semaphores that can be created. */ screate(int cnt) /* * sdelete() - delete the semaphore corresponding to the given sem id. Returns * -1 on failure, zero on success. */ sdelete(int sem) /* * scount() - return the count of the given sem id. -1 on failure. */ scount(int sem) /* * sreset() - reset the count of the given sem id. Return -1 on failure, * zero on success. */ sreset(int sem, int cnt) /* * shmcreate() - create the given amount of shared memory and return the * pointer to this memory on success. Return -1 on failure. We have * imposed a limit of 1024 bytes for the total amount of shared memory * created. */ char *shmcreate(int cnt) /* * shmdelete() - delete the shared memory associated with the given address. * Return -1 on failure, zero on success. */ shmdelete(char *sbShm)
There is a fixed limit on the number of semaphores and shared memory segments that can be allocated on the system. These resources DO NOT automatically get cleaned up when a process exits abnormally. It is expected that your program will cleanup semaphore and shared memory segments that your program has allocated before it exits (using your routine CleanupMailbox()). To determine if your program terminates without cleaning up resources use the command ipcs -b. This command will list all message queues (not used by us), shared memory, and semaphore resources that have been allocated. To cleanup your resources use the command ipcrm -m memid -s semid .... The following example illustrates use of these commands.
% ipcs -b IPC status as of Thu Aug 29 19:52:24 1996 T ID KEY MODE OWNER GROUP QBYTES Message Queues: T ID KEY MODE OWNER GROUP SEGSZ Shared Memory: m 4224 0x278a0000 --rw-rw---- cew 10122 1024 T ID KEY MODE OWNER GROUP NSEMS Semaphores: s 2800 0x278a0000 --ra-ra---- cew 10122 15 % ipcrm -m 4224 -s 2800 % ipcs -b IPC status as of Thu Aug 29 19:52:47 1996 T ID KEY MODE OWNER GROUP QBYTES Message Queues: T ID KEY MODE OWNER GROUP SEGSZ Shared Memory: T ID KEY MODE OWNER GROUP NSEMS Semaphores:
Also be aware that if there is a problem with your program it may be that forked off child processes do not exit correctly. You can check this condition by using the Unix command ps, which prints all executing processes that you have. To terminate processes use the command kill as shown in the following example.
% ps -aux | grep cew cew 31954 82.01 2.98 240 180 p9 R 0:00 ps cew 1133 28.84 0.46 40 28 p9 S 0:00 grep cew 779 0.65 15.05 2260 908 ua E 39:00 gnu-emacs cew 19427 0.00 0.07 44 4 p9 S 0:00 mailbox cew 25530 0.00 0.07 44 4 p9 S 0:00 mailbox cew 5330 0.00 0.13 244 8 ? E 0:00 tcsh % kill 19427 25530 % ps -aux | grep cew cew 15878 78.15 2.98 240 180 p9 R 0:00 ps cew 30796 26.42 0.46 40 28 p9 S 0:00 grep cew 779 0.66 14.32 2260 864 ua R 39:20 gnu-emacs cew 5330 0.00 0.13 244 8 ? E 0:00 tcsh
A useful program for maintaining large programs that have been broken into many software modules is make. The program uses a file, usually named Makefile, that resides in the same directory as the source code. This file describes how to ``make'' a number of targets specified. The following sample Makefile describes two targets--mailbox and lint. Typing make mailbox causes the binary file mailbox to be created. Typing make lint causes the lint program to be run on the source files. Lint is useful for finding inconsistencies and bugs in C programs. Its output can be a bit verbose.
You should copy the file /cs/cs3013/public/lib/Makefile into your directory and use it. A copy of the file is shown below.
As a matter of explanation the first three lines simply define and give values to make variables. If additional files are used then they are added to the SRCS and OBJECTS list. The CFLAGS variable specifies the compile flags to use. The ``-g'' flag causes additional symbolic information to be saved for debugging.
The ``.c.o'' target is a default specification for mapping a source file ``.c'' to an object file ``.o''. The remaining text describes how to make the targets ``run'' and ``lint''. WARNING: The operation line(s) for a target MUST begin with a TAB (do not use spaces). See the man page for make and gcc for additional information.
SRCS = mailbox.c
OBJECTS = mailbox.o /cs/cs3013/public/lib/sem.o
CFLAGS = -g
.c.o:
gcc -c $(CFLAGS) $*.c
mailbox: $(OBJECTS)
gcc $(CFLAGS) $(OBJECTS) -o mailbox