接上文 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，基于多進程和管道來篩選一定范圍內的素數.

什么意思呢，每個進程呢就像一個過濾器，把自己處理不了的數據扔給下一級，我是這么理解的啊，這樣可能更符合這個實驗？

地鐵路上想好了怎么寫，回來一遍過

/** Prime Number Sieve using Pipes* * This program implements the Sieve of Eratosthenes algorithm using pipes and processes* to find prime numbers concurrently. The algorithm works as follows:* * 1. Each process represents a prime number and filters out its multiples* 2. Numbers are passed through pipes between processes* 3. Each process reads numbers from its left pipe and writes non-multiples to its right pipe* * Process Communication Flow:* * Process 1 (2) -> Process 2 (3) -> Process 3 (5) -> Process 4 (7) -> ...*    [pipe1]         [pipe2]         [pipe3]          [pipe4]* * Each process:* 1. Reads numbers from left pipe* 2. If number is not divisible by its prime, passes it to right pipe* 3. Creates new child process for first number it receives* * Example flow for numbers 2-10:* * Time   Process 1    Process 2    Process 3    Process 4* ---------------------------------------------------------* t0      reads 2      -            -            -* t1      sends 3      reads 3      -            -* t2      sends 5      sends 5      reads 5      -* t3      sends 7      sends 7      sends 7      reads 7* t4      sends 9      reads 9      -            -* * Note: Numbers 4, 6, 8, 10 are filtered out by Process 1 (multiples of 2)*       Numbers 9 is filtered out by Process 2 (multiple of 3)*       Only prime numbers reach their corresponding processes*/#include "kernel/types.h"
#include "user/user.h"// Constants for prime number calculation
#define START_PRIME 2        // First prime number to start with
#define MAX_PRIMES 35       // Maximum number to check for primes// Pipe file descriptor constants
#define PIPE_INVALID -1      // Invalid pipe descriptor
#define PIPE_READ 0          // Read end of pipe
#define PIPE_WRITE 1         // Write end of pipe/*** Prints a prime number to the console* @param n The prime number to print*/
void print_prime(int n) { printf("prime %d\n", n); }/*** Safely closes a pipe file descriptor if it's valid* @param p The pipe file descriptor to close*/
void close_pipe_if_valid(int p) {if (p != PIPE_INVALID) {close(p);}
}/*** Delivers a number through the pipe system and creates new processes for primes* @param n The number to process* @param pipe_left The left pipe for receiving numbers*/
void deliver_prime(int n, int pipe_left[2]) {// If pipe is not initialized, create it and fork a new processif (pipe_left[PIPE_WRITE] == PIPE_INVALID) {int ret = pipe(pipe_left);if (ret < 0) {exit(1);}ret = fork();if (ret == 0) {// Child processclose_pipe_if_valid(pipe_left[PIPE_WRITE]);// Print the prime number this process representsprint_prime(n);// Initialize right pipe for passing numbers to next processint pipe_right[2] = {PIPE_INVALID, PIPE_INVALID};int received_number = 0;// Read numbers from left pipe and filter themwhile (read(pipe_left[PIPE_READ], &received_number,sizeof(received_number)) > 0) {// Skip numbers that are multiples of current primeif (received_number % n == 0) {continue;}// Pass non-multiples to next processdeliver_prime(received_number, pipe_right);}// Clean up pipesclose_pipe_if_valid(pipe_left[PIPE_READ]);close_pipe_if_valid(pipe_right[PIPE_READ]);close_pipe_if_valid(pipe_right[PIPE_WRITE]);// Wait for child process to completewait(0);exit(0);} else if (ret > 0) {// Parent process continues} else {printf("fork error, current index: %d\n", n);exit(1);}} else {// printf("deliver_prime: %d\n", n);// Write number to pipeif (write(pipe_left[PIPE_WRITE], &n, sizeof(n)) <= 0) {exit(1);}}
}/*** Main function that initiates the prime number calculation* @param argc Number of command line arguments* @param argv Command line arguments* @return 0 on successful execution*/
int main(int argc, char *argv[]) {// Initialize pipe for first processint p[2] = {PIPE_INVALID, PIPE_INVALID};// Print the first prime numberprint_prime(START_PRIME);// Process numbers from START_PRIME + 1 to MAX_PRIMESfor (int i = START_PRIME + 1; i <= MAX_PRIMES; i++) {// Skip multiples of START_PRIMEif (i % START_PRIME == 0) {continue;}// Process the number through the pipe systemdeliver_prime(i, p);}// Clean up pipesclose(p[PIPE_READ]);close(p[PIPE_WRITE]);// Wait for child process to completewait(0);return 0;
}

實驗結果

make qemu
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.0xv6 kernel is bootinghart 1 starting
hart 2 starting
init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31

他實驗中提到一點 Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.，于是我把 MAX_PRIMES改成了100并加了一些錯誤日志，試一下什么時候會"資源耗盡"。

make qemu
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.0xv6 kernel is bootinghart 2 starting
hart 1 starting
init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
prime 37
prime 41
pipe error, current index: 43
$ 

為什么是43？留個坑吧…