user/primes.c

   1 // Concurrent version of prime sieve of Eratosthenes.
   2 // Invented by Doug McIlroy, inventor of Unix pipes.
   3 // See http://plan9.bell-labs.com/~rsc/thread.html.
   4 // The picture halfway down the page and the text surrounding it
   5 // explain what's going on here.
   6 //
   7 // Since NENVS is 1024, we can print 1022 primes before running out.
   8 // The remaining two environments are the integer generator at the bottom
   9 // of main and user/idle.
  10
  11 #include <inc/lib.h>
  12
  13 unsigned
  14 primeproc(void)
  15 {
  16         int i, id, p;
  17         envid_t envid;
  18
  19         // fetch a prime from our left neighbor
  20 top:
  21         p = ipc_recv(&envid, 0, 0);
  22         cprintf("%d ", p);
  23
  24         // fork a right neighbor to continue the chain
  25         if ((id = fork()) < 0)
  26                 panic("fork: %e", id);
  27         if (id == 0)
  28                 goto top;
  29
  30         // filter out multiples of our prime
  31         while (1) {
  32                 i = ipc_recv(&envid, 0, 0);
  33                 if (i % p)
  34                         ipc_send(id, i, 0, 0);
  35         }
  36 }
  37
  38 void
  39 umain(void)
  40 {
  41         int i, id;
  42
  43         // fork the first prime process in the chain
  44         if ((id = fork()) < 0)
  45                 panic("fork: %e", id);
  46         if (id == 0)
  47                 primeproc();
  48
  49         // feed all the integers through
  50         for (i = 2; ; i++)
  51                 ipc_send(id, i, 0, 0);
  52 }
  53