Erastothene sieve using processes

This code computes all prime numbers using multiple processes. It illustrates the use of the pipe and the fork system calls. Note that this is by no mean an efficient approach.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int pid = 0;
int i;
int n;
int first = 1;
int filter(int fd_in)
{
    int pipe_fd[2];
    int smallest = -1;
    int pid = 0;
    
    /* print the first valid number ... */
    read(fd_in, &n, sizeof(int));
    if (n < 0) {
        perror("Error : no valid number in that list :");
        return -1;
    }
    printf("%d\n", n);
    /* to avoid crappy fork side effects as it does not flush the
  * cache for files IO ... weird but needed */
    fflush(stdout);
    smallest = n;
    first = 1;
    while (read(fd_in, &n, sizeof(int)) == sizeof(int) && (n != -1)) {
        /* transmit all other non multiple numbers */
        if (n % smallest != 0) {
            /* start a new filter if this is the first prime */
            if (first) {
                first = 0;
                if (pipe(pipe_fd) < 0) {
                    perror("Pipe failed :");
                    exit(-1);
                }
                pid = fork();
                if (pid < 0) {
                    perror("Fork failed ... halting !");
                    exit(-1);
                }
                if (pid == 0) {
                    /* the child does not need those fd
                  * anymore : thus free them no to get
                  * a EMFILE */
                    close(fd_in);
                    close(pipe_fd[1]);
                    /* child will execute a new filter */
                    filter(pipe_fd[0]);
                    /* should not be reached !*/
                    printf("Error !\n");
                    exit(-1);
                }
            }
            
            if (write(pipe_fd[1], &n, sizeof(int)) < 0) {
                perror("Write failed :");
            }
        }
    }
    /* the list must end by a -1 and there is no more possible
  * prime to be given to the child */
    if (!first) {
        i = -1;
        write(pipe_fd[1], &i, sizeof(int));
    }
    /* wait for the created child to end, if any */
    if (pid)
        waitpid(pid, NULL, 0);
    close(pipe_fd[0]);
    close(fd_in);
    /* that process will die now ... */
    exit(0);
}
int main(int argc, char *argv[])
{
    int n = 100;
    int i;
    int pipe_fd[2];
    /* if there is an argument, then this is the number n */
    if (argc == 2) {
        n = atoi(argv[1]);
    }
    pipe(pipe_fd);
    pid = fork();
    if (pid < 0) {
        printf("Fork failed ... halting !\n");
        exit(-1);
    }
    if (!pid) {
        filter(pipe_fd[0]);
        printf("Error !\n");
    }
    for (i=2 ; i<n ; i++) {
        write(pipe_fd[1], &i, sizeof(int));
    }
    i = -1;
    write(pipe_fd[1], &i, sizeof(int));
    waitpid(pid, NULL, 0);
    return 0;
}

, ,

Comments are closed.