Part I: Evaluating primality

For the first part of the assignment, we are interested simply in determining whether or not the input integer is a prime number. To do so, divide the list of potential prime factors into sets of no more than eight numbers per set. Using the fork(2), exit(2), and wait(2) system calls, distribute among a number of processes the task of checking each of these sets for prime factors of the input integer. If a factor is found, then we can conclude that the number is not prime.

Your program must obey the following rules:

• reads from stdin a single argument representing the candidate prime number, n
• writes on stdout any header information you wish, followed by a blank line, followed by the result
• depending on the primality of n, the result is either
  • the text, "n is prime"
  • the text, "n is not prime" where n is the number entered on stdin

Part I Bonus

Without making use of any additional system calls, provide the initial process with the identity of all of the prime factors found. (Hint: the exit(2) call returns a value to the waiting parent. However, it is not acceptable to ask each process to test only a single possible prime factor.)

Your bonus program must obey the following rules:

• reads from stdin a single argument representing the candidate prime number, n
• writes on stdout any header information you wish, followed by a blank line, followed by the result
• depending on the primality of n, the result is either
  • a list of prime factors, one per line, with no leading whitespace
  • the text "n is prime", where n is the number entered on stdin

Part II: Evaluating primality

One of the obvious shortcomings of our first approach was the large number of processes that were required. Therefore, we will now allow each process to test up to 20 prime factors. However, if you worked through the bonus section of part I, you'll recognize that we can no longer use the exit(2) value to return the identity of that many prime factors. In any case, that was a dirty trick (a.k.a. "hack") we employed; the exit(2) value is intended to provide information about the terminating status of the process, such as whether or not a fatal error was encountered.

For this part of the assignment, the processes will send the prime factors found (if any) back to the parent using interprocess channels of communication provided by the pipe(2) system call. Your output must obey the same rules as those described above for the bonus section of part I.

Part II Bonus

For a distributed computing problem of more realistic complexity, processes may take more than a few milliseconds to complete. In such a case, the invoking process should not wait around for the results of a slow computation when other results may be ready. Use the select(2) function to poll for those pipes with pending data so that results will be read as they become available. (Hint: Each process should let the parent know when it is finished its work so that the parent can close the pipe for that child.)

Introduce a five second delay in the process handling the first set of prime factors and verify that your program doesn't block while waiting for the first set of results.

Helper Code

You may wish to make use of this simple prime number generator, based on the Sieve of Erastosthenes (276 - 196 B.C.), the famed Cyrenese scholar who served as the director of the library at Alexandria and whose other accomplishments include computing the circumference and diameter of the earth to an accuracy of 50 miles!

#include <stdio.h>	

/*
 * Generate a list of primes over the first n integers
 * using the simple Sieve of Eratosthenes method.
 * Creates storage for *pprimes (the list of generated primes) 
 * including space for one additional entry that is initialized
 * to zero (automatically by calloc) to indicate the end of list.
 * Returns the number of primes generated.
 */
int Eratosthenes (int n, int **pprimes) {
	int i, j;
	char *sieve;
	int *primes;
	int nonprimes;

	/* create storage for the sieve and initialize to zero */
	sieve = (char *)calloc(n+1, sizeof(char));
	if (NULL == sieve) {
		perror ("calloc of sieve");
		exit(-1);
	}

	/* keep a count of numbers removed from the sieve */
	nonprimes = 1;	/* since 1 is not a prime */

	/* perform the sieve */
	for (i = 2; i <= n; i++) {
		if (!sieve[i]) {
			for (j = 2*i; j =< n; j+=i) {
				if (!sieve[j]) {
					sieve[j] = 1;
					nonprimes++;
				}
			}
		}
	}

	/* create storage for the list of primes (+1 for end of list) */
	*pprimes = primes = (int *)calloc((n - nonprimes + 1), sizeof(int));
	if (NULL == primes) {
		perror ("calloc of primes");
		exit(-1);
	}

	/* now scan through sieve for zero-marked entries */
	for (i = 2; i <= n; i++) {
		if (!sieve[i]) {
			*primes++ = i;
		}
	}

	/* be nice and release the allocated memory */
	free ((void *)sieve);

	return (n - nonprimes);
}

In addition to the hardcopy submission, you must provide an electronic version of your assignment in UNIX tar(8) format, encoded with uuencode(1). The electronic submission will be compiled and tested automatically on the Linux systems in the ECE undergraduate lab. Therefore, regardless of what machines you use to write your programs, make sure that they also compile and execute correctly on the ECE Linux systems. The electronic submission must contain:

• all of the source code ready to be compiled (or executed, in the case of interpreter scripts) under the Linux systems in the ECE undergraduate lab
• a Makefile (see make(1)) for compiling any source code as necessary: since your executables will be run by an automated shell script, they must be named as follows:
  • part1 (for part I)
  • part1b (for the bonus component of part I)
  • part2 (for part II)
  • part2b (for the bonus component of part II)

Your message must be sent by September 29, 16:00. Assignments will not be considered complete if they have not been submitted both in hardcopy and electronically or if the two versions of the source code differ. Incomplete submissions will not be marked. The hardcopy and electronic versions may be submitted at different times within the assigned deadline.

In order to allow for automatic processing, your submission message must be formatted as specified in the following paragraphs. An unproperly formatted message will be automatically bounced back to the sender and the submission will not be considered complete. You may then correct the errors and resubmit. However, you may not resubmit after a properly formatted message has been accepted: please make sure that your files contain exactly what you wish to submit.

The "Subject:" field of your email message must have the following format: 427-A1-YOUR_STUDENT_ID, with the digits of your student ID number in place of YOUR_STUDENT_ID; do not write anything else in the subject; do not write anything in the message other than the tar file.

The tar file must create, when opened, a directory named with your student ID, containing all the source files (there may be subdirectories, if needed) and the Makefile as described above. An optional file named README may be included, containing instructions for the correct compilation and execution of the programs, and for the interpretation of the produced data files. (This is more a point of good style rather than a requirement for the assignment.) Do not include any non-text files (e.g. compiled executables, relocatable objects), since they may be handled improperly by the email software, causing corruption of the entire tar file. Make sure that all files are in UNIX text format (lines terminated by a line-feed character, ASCII 10): use a converter if you edit them on a PC under MS-DOS/Windows.

An example sequence of UNIX shell commands that creates and sends a tar file as specified follows [comments in square brackets]:

[Create the source directory for student with id 952334.]
   % mkdir ./952334

[Copy all the sources in it.]
   % cp foo.c bar.c baz.c flop.c README ./952334

[Create the tar file with the directory content.]
   % tar cvf 427-A1-952334.tar ./952334

[Uuencode the tar file]
   % uuencode 427-A1-952334.tar 427-A1-952334.tar > 427-A1-952334.tar.uu

[Send it with the proper subject field.]
   % mail -s "427-A1-952334"  < 427-A1-952334.tar.uu

If the submission is correct, you will receive an automatic acknowledgement in reply. Otherwise, the message will be refused, and an explanatory error message will be sent to you.