You must not leave processes lying around on any of the machines you work on, or the machines will eventually become unusable. Always, before you log out, and frequently while you are working, use ps -aux | grep <username> or top to check if you have any stray processes still running. Use kill to kill them. You may find killall psieve on Linux to be useful.
Be extra careful in the early stages of developing your program. Do not test large values of n until you are confident that your program is working.
If you notice that students leave processes around for a long time, please post a note to the newsgroup with their user names, asking them politely to clean up their processes.
In part 1 of the assignment you will use Unix processes and pipes to write a parallel program in C that computes all the prime numbers between 2 and n, where n is a command-line argument.
The sequential (single-process) algorithm given below comes from a webpage from the University of Utah.
A prime number is a natural number greater than 1 that can be divided without remainder only by itself and by 1. Natural numbers n that can be divided by a number less than n and greater than 1 are composite numbers. The Sieve of Eratosthenes identifies all prime numbers up to a given number n as follows:
2m, 3m, 4m, ...as composite. (Thus in the first run we mark all even numbers greater than 2. In the second run we mark all multiples of 3 greater than 3.)
The parallel algorithm that you will write creates a new process for each new value of m (i.e., each prime number found that is less than the square root of n). A process sends each number in sequence to its child. The first number a process receives is its value of m, which it prints out to a file. If the number is a multiple of the process's m value then the number is discarded. If the number is not a multiple of m, the number is passed on to the next process in the chain (or pipeline). Please see the accompanying diagram.
A new process is created whenever a number reaches the end of the chain of processes and it not a multiple of any of the previously discovered primes. If the number received by the new process is greater than the square root of n, then the new process knows it must report each of the remaining numbers as prime numbers and no new processes will be created.
Note that the parallel algorithm differs from the sequential algorithm in that you do not need to "mark" numbers as composite. These number are simply discarded. Each child prints out the prime number or numbers that it found.
Your program will be called psieve and will take two optional arguments: -n <upper limit>, and -f <filename>. Upper limit is an integer that marks the end of the sequence of numbers (n) that psieve checks, and filename is the name of the file that the children will write their prime numbers to.
The termination code or exit code of each process will be one plus the number of stages (i.e., processes) that follow it in the pipeline. Referring to the diagram part c), if n equals 9, then the process whose m value is 3 will print out all the numbers that it receives, and its termination code will be 1. The termination code of the process whose m value is 2 will be 2. Before terminating the master process, will print to standard error the number of processes (not including itself) that were created to solve the problem. In our example, the master process prints "Number of processes = 2".
Since we have multiple processes writing to the same file, do we need to synchronize access to the file? Explain your answer.
Write a paragraph answering this question, and submit it in a file called answer. The file must contain plain text (no word processor, or html formatting, and must be called answer with no extensions. I.e., the file must not be called answer.txt or Answer.
You must use getopt to read in the parameters. (You don't need to use getopt_long.)
You must use pipes to communicate between processes.
Remember to close the ends of pipes you don't need, and remember to close the pipes when they are no longer needed. If your program appears to be stuck or hung, chances are that a processes is waiting to read from a pipe that will never be written to.
You should be writing integers to a pipe rather than strings, so you will be using the read and write system calls.
My solution with reasonable comments, and fairly complete error checking is 160 lines.
The idea for this part of the assignment is inspired by our auto-testing software. If a student's program has an infinite loop in it, we need a way to notice, and to stop the program.
You will write a C program called runprog that will execute another program. It will kill the program if it runs beyond a certain time limit using a signal that the program cannot catch. It will also redirect the program's standard output to a file, so that we can look at it later. Finally it will report the termination status (to stderr) of the child including the signal that caused it to terminate. runprog takes two optional arguments: -t <timelimit> and -o <output file> where timelimit is the amount of time to wait before killing the process, and output file is the name of the output file to redirect the standard output of the program. The remaining arguments are the name of the program to execute and its arguments. The default value of timelimit should be 10 seconds.
For example, suppose I have an executable called wastetime in my current working directory, then I can run it from runprog as follows:
runprog -t 5 -o junk wastetimeIf wastetime takes longer than 5 seconds runprog will kill it. Anything wastetime has written to standard out will be in the file called junk.
You will want to write at least one program to help you test runprog. You do not need to hand this program in.
Part 2 of the assignment is not meant to be difficult, and will be worth approximately 25% of the assignment. My solution is less than 100 lines of code including all the getopt stuff. The sole purpose is to give you more practice using signals and processes.