Programming Assignment IV

Due on Wednesday, November 11, 2009 @ 11pm

70 points

Quicksort with Unix Shared Memory

We know that quicksort can be implemented with threads as discussed here. Due to the similarity between processes and threads, quicksort can also be implemented with processes. Given an array section a[L..R], a quicksort algorithm partitions it into two subsections with an array index M such that all elements in a[L..M-1] are smaller than or equal to a[M], and all elements in a[M+1..R] are greater than or equal to a[M]. This is shown below:

Since a[L..M-1] and a[M+1..R] can be sorted independently, we can use two processes, one for each array section as shown below. This is the merit of this programming assignment.

Program Specification

Write two programs main and compute. The former does not require any command line arguments and the latter takes at least two command line arguments Left and Right. The job for program main to do consists of the following:

Program main reads an input array a[ ] of distinct integers into a shared memory. Let the number of elements of this array be n.
main prints out the input array.
Then, main creates a child process to run program compute using the execvp() system call and passes the assigned Left, Right and other needed information to program compute. Initially, Left and Right are 0 and n-1, respectively.
Program main waits for the completion of its only child process and then prints out the sorted result.

The job for program compute to do is the following:

When program compute runs, it receives the left and right section indices Left and Right from its command line arguments.
Then, it partitions the array section a[Left..Right] into two at element a[M]. See your data structures and/or algorithms textbooks for this partitioning procedure. After the partition is obtained, two child processes are created, each of which runs compute using system call execvp. The first child receives Left and M-1, while the second receives M+1 and Right. The parent then waits until both child processes complete their job.
After this, program compute exits.

Important Notes

You should only use shared memory and execvp() to solve this problem.

The process structure must be identical as specified. Otherwise, you will receive no point.

Input and Output

The input to program main is in a file with the following format:

n           <--------------------- the number of elements of array a[ ]
a[0]  a[1]  a[2] ..... a[n-1] <--- elements of array a[ ]

You can assume the following:

The value of n is an integer larger than or equal to 5.
The values for array a[ ] are distinct integers.

The following shows a possible program output:

Quicksort with multiple processes:

*** MAIN: shared memory key = 1627930027
*** MAIN: shared memory created
*** MAIN: shared memory attached and is ready to use

Input array has 8 elements:
    4  7  2  9  3  5  8  6
    
*** MAIN: about to spawn processes
   ### PROC(4913): entering with a[0..7]
       ..........
   ### PROC(3717): entering with a[3..6]
       XX  XX  XX  XX <---------------------- elements of a[3] to a[6]
       ..........
   ### PROC(3717): partition position is a[4] = XX 
       ..........
   ### PROC(3717): section a[3..6] sorted
       YY  YY  YY  YY
       ..........
   ### PROC(3717): exits 
       ..........
*** MAIN: sorted array:
     2  3  4  5  6  7  8
*** MAIN: shared memory successfully detached
*** MAIN: shared memory successfully removed

The output lines from main always starts with *** MAIN:. Program main first prints out the shared memory key being used, followed by messages indicating the shared memory being created and attached. Then, main prints out the input array.

Messages from a child process have an indentation of three spaces. The first message below indicates that the child process with process ID 3717 receives Left = 3 and Right = 6, and the current content of this array section. The second message below shows the partition element a[4] and its value. The third message shows the sorted array section of a[3..6]. Finally, the fourth message indicates that this process exits.

   ### PROC(3717): entering with a[3..6]
       XX  XX  XX  XX <---------------------- elements of a[3] to a[6]
       ..........
   ### PROC(3717): partition position is a[4] = XX 
       ..........
   ### PROC(3717): section a[3..6] sorted
       YY  YY  YY  YY
       ..........
   ### PROC(3717): exits

Submission Guidelines

All programs must be written in ANSI C. No C++ please. If you use C++, you will rick low to very low score.
Use the submit command to submit your work. You can submit as many times as you want, but only the last one will be graded. A makefile is required. Name your executables main and compute.
I will use the following approach to compile and test your programs:
```
make             <-- make your program
main < data.in   <-- run your program with data file data.in
```
I will repeat the above a number of times with identical or different input files to test if your program performs correctly. The input file name does not have to be data.in as shown above. It could be any name.
Your implementation should fulfill the program specification as stated. Any deviation from the specification will cause you to receive zero point.
You should aim for maximum parallelism. That is, implement the solution as stated and make sure all required processes will run simultaneously. Without doing so, you risk very low grade.
No late submission will be graded.
My rule of grading is subtraction based. I assume you always receive 100%. If you missed something, some points will be taken off based on the following rules. Click here to see how your program will be graded.

Your programs must contain enough comments. Programs without comments or with insufficient comments will cost you 30%.

For each program, the first piece should be a program header to identify yourself like this:

// ----------------------------------------------------------- 
// NAME : John Smith                         User ID: xxxxxxxx 
// DUE DATE : mm/dd/yyyy                                       
// PROGRAM ASSIGNMENT #                                        
// FILE NAME : xxxx.yyyy.zzzz (your unix file name)            
// PROGRAM PURPOSE :                                           
//    A couple of lines describing your program briefly        
// -----------------------------------------------------------

For each function in your program, include a simple description like this:

// ----------------------------------------------------------- 
// FUNCTION  xxyyzz : (function name)                          
//     the purpose of this function                            
// PARAMETER USAGE :                                           
//    a list of all parameters and their meaning               
// FUNCTION CALLED :                                           
//    a list of functions that are called by this one          
// -----------------------------------------------------------

Bad programming style and missing headers will cost you 30%.

Submit a one-page description of your solution, discussing the following issues:
- The logic of your program
- Why does your program work?
- Are there potential race conditions in your program and in the program specification?
- How do you construct an argument list that is passed from program main to program compute?
Name this file README rather than readme or Readme. Spell check this file; otherwise, you may risk lower grade.
Missing README costs you 50%, poorly written README costs you 30%, and submitting a non-text file costs you 30%.
Not-compile programs receive 0 point. By not-compile, I mean any reason that could cause an unsuccessful compilation, including missing files, syntax errors, incorrect makefile and so on. Double check your files before you submit, since I will not change your program to make it work.
Compile-but-not-run programs receive no more than 50%. Compile-but-not-run means you have attempted to solve the problem to certain extent but you failed to make it work properly. A meaningless or vague program receives no credit even though it compiles successfully. Another common problem is that your makefile could successfully process your source files (i.e., compiled successfully); but, your makefile does not generate an executable file with the desired filename (i.e., main in this assignment). If this happens, I will consider your submission as compile-but-not-run.
Programs delivering incorrect result, incomplete result, or incompatible output receive no more than 70%.
You must only use shared memory to hold the input and result matrices, and use execvp() to run program compute. Otherwise, you will receive no credit. Note also that no threads should be used.
Make sure your program will remove all processes and shared memory segments, even though it may end abnormally. Each unremoved process or shared memory costs you 10%.
All deductions mentioned above are cumulative! This means that even though you have turned in a correct program, you could get very low grade. For example, if your submission does not have the necessary program and function headings (30% off), does not have enough comments (30% off), compiles but not runs correctly (30% off) and has a shared memory left after your program exits (10% off), then you will receive 60×(100-30-30-30-10)%=0 points.
Your submission should include the following files:
1. File main.c contains the program for the main process.
2. File compute.c contains the program for the compute process.
3. File Makefile is a makefile that compiles the above files and generates the executable files main and compute.
4. File README.
Programs submitted to a wrong class and/or a wrong section will not be graded.
Always start early, because I will not grant any extension if your home machine, your phone line or the department machine crashes in the last minute.

Since the rules are all clearly stated above, no leniency will be given. So, if you have anything in doubt, please ask for clarifications.
Click here to see how your program will be graded.