Programming Assignment 1

This assignment is to be done individually. Do not show your code to others and do not look at other students' code. Prevent other students from accessing your code (do not put it in a public directory). However, you are free to use any tools you like (library, search engines), to discuss problems with others, and to seek the help of the TA or the instructor.

Objective

The objective of this assignment is to familiarize yourself with the Unix environment, programming tools, process management and inter-process communication mechanisms. The assignment can be performed using C or C++, no other language will be accepted.

Assignment: Processes and shared memory

The idea is to create a number of processes and associate with each process a 'mailbox' where a single message for each process can be stored. You will use semaphores to ensure that at most one message is in each mailbox. The number of processes should be controlled by the first command line parameter ('numproc'). In your programm, limit the total number of processes to 100 (define a constant NUMPROC with that value and check the input parameter so that it does not exceed this value). In your parent process, use the fork() system call to create NUMPROC-1 child processes. Associated with each process is a mailbox, containing a message that is defined by the following C structure:

struct msg {
      int from;       /* sender index */
      int type;       /* 0=request, 1=response, -1=termination */
      int val1;       /* beginning of range */
      int val2;       /* end of range */
      int total;      /* sum of numbers */
};

Create an array of mailboxes (of length NUMPROC) to store at most one message for each mailbox. These mailboxes are shared, so you have to create these mailboxes as shared memory, so that all processes can access them. Similarly, semaphores must be created to control access to each mailbox. Further, write two procedures, sendmsg and recvmsg, with the following interfaces:

sendmsg(int to, struct msg *pmsg);

recvmsg(int from, struct msg *pmsg);

The index of a process is its number so the index of the parent process is zero, the first child process is one, etc. Each process must have its own unique index. The sendmsg call should block if somebody is currently writing into a mailbox and recvmsg should block if a mailbox is empty.

After creating the processes and mailboxes, your program will use three command line arguments (integers) to determine how it works. The first and second values ('begin' and 'end') determine a range of integers your program is to sum together for its output. The last value ('maxrange') is the maximum number of integers a single process is allowed to sum together at a time.

The parent process distributes the work load to all other processes in the form of a range of numbers to add together, where no range can be larger than maxrange. For example, if the range of numbers is 1-100 and maxrange is 5, then the parent process sends range 1-5 to process 1, 6-10 to process 2 and 11-15 to process 3, etc. Whenever a process sends back a result and more numbers need to be added, the parent sends the next range of numbers to the newly available process. This continues until the parent has finished the range of numbers. When the parent has received back all the results, it prints out the total. It further sends a termination message to each child process and after that it should wait for as many messages as there are children. Each child should send back a message indicating the numbers of integers it added together and then terminate itself. The parent has to clean up all the resources and then exits.

Each child waits for messages in the mailbox, then adds up the ranges of integers and returns the total. To simulate processors of different speed, each child should delay the response for a number of seconds corresponding to its identifier (1 second for process 1, 2 seconds for process 2, etc.). If the message type received is -1, the child stops receiving messages, immediately (no delay) returns the total number of integers it has added together to the parent and exits. The program should be started as follows:

./mailbox numproc begin end maxrange

The parent process will write a line to stdout each time it has sent a range to a child process or when it has received a response from a child process. Here is a sample output:

./mailbox 4 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 receiving 1-10 from Process 1 (55)
Process 0 sending 31-40 to Process 1
Process 0 receiving 11-20 from Process 2 (155)
Process 0 sending 41-50 to Process 2
Process 0 receiving 31-40 from Process 1 (355)
Process 0 sending 51-60 to Process 1
Process 0 receiving 21-30 from Process 3 (255)
Process 0 sending 61-70 to Process 3
Process 0 receiving 51-60 from Process 1 (555)
Process 0 sending 71-80 to Process 1
Process 0 receiving 41-50 from Process 2 (455)
Process 0 sending 81-90 to Process 2
Process 0 receiving 71-80 from Process 1 (755)
Process 0 sending 91-95 to Process 1
Process 0 receiving 91-95 from Process 1 (465)
Process 0 receiving 61-70 from Process 3 (655)
Process 0 receiving 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

Hint: start with a fixed number of processes, e.g., numproc = 2 (one producer of messages and one consumer). After getting this to work, increase numproc.

Don't forget error handling, resource cleanup, and commenting your code. If your program crashes, you can check for resources using the ipcs command and remove them with ipcrm. With ps can you check for children that have not terminated correctly. Write a makefile that resides in the same directory as the source code.

Evaluation

Run your program for the following scenarios:

./mailbox 4 1 95 10
./mailbox 3 1 95 5
./mailbox 3 1 100 3
./mailbox 3 1 100 50
./mailbox 5 12 28 1
./mailbox 4 3 33 8

Write a document (ps, pdf, ascii) and add the output of these scenarios to the evaluation part of the document. Run the first scenario for at least ten times. Argue in your evaluation part if or if not your output differs (sometimes) from the output given above and if so, explain. If multiple runs of the same command lines result in different outputs, explain why. The document should further address your solution approach, any encountered problems and their solutions, explain how to run the code, etc. The page limit is 2 pages (this excludes the outputs from the test cases).

Grading

The grading will be according to the grading policy on the course webpage. Remember that documentation and exception handling are each worth 20% of the assignment's grade!

Submission

The due date for this assignment is January 31st, 2005, 11.59pm EST. You will use the drop-off boxes (you will find a box with your login name). Make a directory called "project1" and place all required files into this directory (either individually or as one tar file). The required files are: all source files, a Makefile, run scripts for all required test cases, and a document called README (ASCII file) or readme.ps or readme.pdf (postscript file), which describes a project summary, your solution approach, any encountered problems and how you solved them, any unresolved issues, an evaluation with the output of the program for the test cases mentioned above, and a usage explanation. The document should be not more than 2 pages (plus the outputs from the test cases).
Late submissions: 25% penalty after the deadline and another 25% for every 24h after the deadline.