Process 8 Activity

The sieve of Eratosthenes is an ancient procedure for generating prime numbers (integers greater than 1 whose only divisors are themselves and 1). The sieve is initialized with a list of all integers greater than 1. Then, repeatedly, you:

1. Pick the smallest non-crossed-out integer, n. This is the next-largest prime.
2. Cross out all multiples of n.
3. Repeat.

The result “sieves” out the primes.

Let’s model this with pipes!

Tasks

1. Write a shell command that writes to standard output all integers greater than 1, one per line. You may write a C++ program if you can’t find an appropriate shell utility. (This is the initialization step.)

2. Write a shell command that reads a list of integers on standard input, one per line, and writes to standard output those integers that are not multiples of n, a number specified on the command line. You may write a C++ program if you can’t find an appropriate shell utility. (This is the crossing-out step.)

Hint: Check out the awk program, and especially its -v argument.

3. Your goal is to write a program, primesieve, that uses your answers to #1 and #2 and pipes to create a sieve of Eratosthenes. First, draw some pictures of the sieve in different stages—for instance, after the initialization step; after the first crossing-out step; and after three crossing-out steps.

4. Write C++ code to add another filter (i.e., crossing-out step) to the sieve.

5. Write the sieve!

Solutions

Our solutions for filtermultiples and primesieve are stored in cs61-lectures/process8/sol/filtermultiples.cc and cs61-lectures/process8/sol/primesieve.cc. After trying to do this problem yourself, check out our solutions:

$ cd cs61-lectures/process8
$ cp sol/* .
$ make
$ ./primesieve | less

Read the code too. It’s very important that ./primesieve not buffer its standard input; why?

This will create a huge number of helper processes; for example:

$ ./primesieve
2
3
5
7
11
...
[after running a while]...
$ pstree -p
bash─┬─primesieve─┬─168*[filtermultiples]
     │            └─seq
     └─pstree

But if you kill primesieve, all the helper processes will die too!

$ killall -9 primesieve
Terminated
$ pstree
bash───pstree

Why? Because of SIGPIPE, the signal delivered when a program writes to a pipe with no open read ends. After primesieve is terminated, the previous filtermultiples (here, filtermultiples 997) will eventually make a write system call to its standard output. The operating system responds with SIGPIPE because the corresponding pipe’s read end is closed. Then filtermultiples 997 is terminated. That closes the read end of the previous pipe, so eventually the previous filtermultiples 991 is terminated in a similar way. The terminations ripple back all the way through the pipeline and everything cleans itself up.