I am trying to solve the following from .1810/2023/labs/util.html:
Write a concurrent prime sieve program for xv6 using pipes and the design illustrated in the picture halfway down this page and the surrounding text. This idea is due to Doug McIlroy, inventor of Unix pipes. Your solution should be in the file user/primes.c.
Here is a diagram showing how it's meant to work (from /), rectangles are processes, receiving and forwarding numbers
And I am mostly successful with the following code,
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#define PROCESS_MAX (int) 35
void extend_pipeline(int* pipe);
int main(int argc, char *argv[]) {
int pipefd[2];
pipe(pipefd);
// this is the generating process
for (int i = 2; i <= PROCESS_MAX; i++) {
write(pipefd[1], &i, sizeof(int));
}
extend_pipeline(pipefd);
exit(0);
}
void extend_pipeline(int* pipe_parent) {
int cpid;
int pipe_child[2];
pipe(pipe_child);
int p = 0;
int n = 0;
close(pipe_parent[1]);
int iteration = 0;
while (read(pipe_parent[0], &n, sizeof(int)) > 0) {
iteration++;
if (iteration == 1) {
p = n;
sleep(1);
printf("prime %d\n", p);
}
if (n % p != 0) {
write(pipe_child[1], &n, sizeof(int));
}
}
if (iteration == 1) {
exit(0);
}
if ((cpid = fork()) == 0) { // child
extend_pipeline(pipe_child);
exit(0);
}
}
However, the program doesn't terminate. I have to enter a newline before the shell prompts for user input. Therefore, I fail the tests.
The output of my code is:
$ ./primes
prime 2
$ prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
When it should be:
$ ./primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
$
Why doesn't the program terminate? I believe I need to add a wait
call somewhere, but I am not sure.
I have tried putting a wait
in the main
function, but that only prints out primes 2, and 3 before hanging.