MIT XV6 - 1.3 Lab: Xv6 and Unix utilities - primes

接上文 MIT XV6 - 1.2 Lab: Xv6 and Unix utilities - pingpong
  primes

继续实行，实行介绍和要求如下 (原文链接 译文链接) :
   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.
    Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.
    Some hints:
  

• Be careful to close file descriptors that a process doesn’t need, because otherwise your program will run xv6 out of resources before the first process reaches 35.
  
• Once the first process reaches 35, it should wait until the entire pipeline terminates, including all children, grandchildren, &c. Thus the main primes process should only exit after all the output has been printed, and after all the other primes processes have exited.
  
• Hint: read returns zero when the write-side of a pipe is closed.
  
• It’s simplest to directly write 32-bit (4-byte) ints to the pipes, rather than using formatted ASCII I/O.
  
• You should create the processes in the pipeline only as they are needed.
  
• Add the program to UPROGS in Makefile.
  

  大致意思呢，参考 Unix pipes的创造者，大佬Doug McIlroy的 Bell Labs and CSP Threads，基于多历程和管道来筛选一定范围内的素数.

什么意思呢，每个历程呢就像一个过滤器，把自己处理不了的数据扔给下一级，我是这么理解的啊，这样可能更符合这个实行？
地铁路上想好了怎么写，返来一遍过

1. /*
2. * Prime Number Sieve using Pipes
3. *
4. * This program implements the Sieve of Eratosthenes algorithm using pipes and processes
5. * to find prime numbers concurrently. The algorithm works as follows:
6. *
7. * 1. Each process represents a prime number and filters out its multiples
8. * 2. Numbers are passed through pipes between processes
9. * 3. Each process reads numbers from its left pipe and writes non-multiples to its right pipe
10. *
11. * Process Communication Flow:
12. *
13. * Process 1 (2) -> Process 2 (3) -> Process 3 (5) -> Process 4 (7) -> ...
14. *    [pipe1]         [pipe2]         [pipe3]          [pipe4]
15. *
16. * Each process:
17. * 1. Reads numbers from left pipe
18. * 2. If number is not divisible by its prime, passes it to right pipe
19. * 3. Creates new child process for first number it receives
20. *
21. * Example flow for numbers 2-10:
22. *
23. * Time   Process 1    Process 2    Process 3    Process 4
24. * ---------------------------------------------------------
25. * t0      reads 2      -            -            -
26. * t1      sends 3      reads 3      -            -
27. * t2      sends 5      sends 5      reads 5      -
28. * t3      sends 7      sends 7      sends 7      reads 7
29. * t4      sends 9      reads 9      -            -
30. *
31. * Note: Numbers 4, 6, 8, 10 are filtered out by Process 1 (multiples of 2)
32. *       Numbers 9 is filtered out by Process 2 (multiple of 3)
33. *       Only prime numbers reach their corresponding processes
34. */
36. #include "kernel/types.h"
37. #include "user/user.h"
39. // Constants for prime number calculation
40. #define START_PRIME 2        // First prime number to start with
41. #define MAX_PRIMES 35       // Maximum number to check for primes
43. // Pipe file descriptor constants
44. #define PIPE_INVALID -1      // Invalid pipe descriptor
45. #define PIPE_READ 0          // Read end of pipe
46. #define PIPE_WRITE 1         // Write end of pipe
48. /**
49. * Prints a prime number to the console
50. * @param n The prime number to print
51. */
52. void print_prime(int n) { printf("prime %d\n", n); }
54. /**
55. * Safely closes a pipe file descriptor if it's valid
56. * @param p The pipe file descriptor to close
57. */
58. void close_pipe_if_valid(int p) {
59.   if (p != PIPE_INVALID) {
60.     close(p);
61.   }
62. }
64. /**
65. * Delivers a number through the pipe system and creates new processes for primes
66. * @param n The number to process
67. * @param pipe_left The left pipe for receiving numbers
68. */
69. void deliver_prime(int n, int pipe_left[2]) {
70.   // If pipe is not initialized, create it and fork a new process
71.   if (pipe_left[PIPE_WRITE] == PIPE_INVALID) {
72.     int ret = pipe(pipe_left);
73.     if (ret < 0) {
74.       exit(1);
75.     }
77.     ret = fork();
78.     if (ret == 0) {
79.       // Child process
80.       close_pipe_if_valid(pipe_left[PIPE_WRITE]);
82.       // Print the prime number this process represents
83.       print_prime(n);
85.       // Initialize right pipe for passing numbers to next process
86.       int pipe_right[2] = {PIPE_INVALID, PIPE_INVALID};
87.       int received_number = 0;
89.       // Read numbers from left pipe and filter them
90.       while (read(pipe_left[PIPE_READ], &received_number,
91.                   sizeof(received_number)) > 0) {
92.         // Skip numbers that are multiples of current prime
93.         if (received_number % n == 0) {
94.           continue;
95.         }
97.         // Pass non-multiples to next process
98.         deliver_prime(received_number, pipe_right);
99.       }
101.       // Clean up pipes
102.       close_pipe_if_valid(pipe_left[PIPE_READ]);
103.       close_pipe_if_valid(pipe_right[PIPE_READ]);
104.       close_pipe_if_valid(pipe_right[PIPE_WRITE]);
106.       // Wait for child process to complete
107.       wait(0);
108.       exit(0);
109.     } else if (ret > 0) {
110.       // Parent process continues
111.     } else {
112.       printf("fork error, current index: %d\n", n);
113.       exit(1);
114.     }
115.   } else {
116.     // printf("deliver_prime: %d\n", n);
117.     // Write number to pipe
118.     if (write(pipe_left[PIPE_WRITE], &n, sizeof(n)) <= 0) {
119.       exit(1);
120.     }
121.   }
122. }
124. /**
125. * Main function that initiates the prime number calculation
126. * @param argc Number of command line arguments
127. * @param argv Command line arguments
128. * @return 0 on successful execution
129. */
130. int main(int argc, char *argv[]) {
131.   // Initialize pipe for first process
132.   int p[2] = {PIPE_INVALID, PIPE_INVALID};
134.   // Print the first prime number
135.   print_prime(START_PRIME);
137.   // Process numbers from START_PRIME + 1 to MAX_PRIMES
138.   for (int i = START_PRIME + 1; i <= MAX_PRIMES; i++) {
139.     // Skip multiples of START_PRIME
140.     if (i % START_PRIME == 0) {
141.       continue;
142.     }
144.     // Process the number through the pipe system
145.     deliver_prime(i, p);
146.   }
148.   // Clean up pipes
149.   close(p[PIPE_READ]);
150.   close(p[PIPE_WRITE]);
152.   // Wait for child process to complete
153.   wait(0);
155.   return 0;
156. }

复制代码

实行结果

1. make qemu
2. qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -global virtio-mmio.force-legacy=false -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0
4. xv6 kernel is booting
6. hart 1 starting
7. hart 2 starting
8. init: starting sh
9. $ primes
10. prime 2
11. prime 3
12. prime 5
13. prime 7
14. prime 11
15. prime 13
16. prime 17
17. prime 19
18. prime 23
19. prime 29
20. prime 31

复制代码

他实行中提到一点 Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.，于是我把 MAX_PRIMES改成了100并加了一些错误日记，试一下什么时间会"资源耗尽"。

1. make qemu
2. qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -global virtio-mmio.force-legacy=false -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0
4. xv6 kernel is booting
6. hart 2 starting
7. hart 1 starting
8. init: starting sh
9. $ primes
10. prime 2
11. prime 3
12. prime 5
13. prime 7
14. prime 11
15. prime 13
16. prime 17
17. prime 19
18. prime 23
19. prime 29
20. prime 31
21. prime 37
22. prime 41
23. pipe error, current index: 43
24. $

复制代码

为什么是43？留个坑吧…

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告