xv6 Lab: Utilities (3) primes

이 문제는 MIT의 xv6 수업에 출처가 있습니다.

출처 : Lab: Xv6 and Unix utilities (mit.edu)

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

출처:Bell Labs and CSP Threads (swtch.com)

첫번째 프로세스가 2~35까지 숫자가 적힌 파이프를 만든다.

이후 소수의 배수는 소수가 아니라는 성질을 사용한다.

소수를 출력한 뒤 자식 프로세스에게 그 것들의 배수를 제외한 나머지 숫자를 파이프라인으로 전달시키는 과정을 반복한다.

에라토스테네스의 채와 유사한 원리로 동작한다.

 

HINT

//출처:https://swtch.com/~rsc/thread/
p = get a number from left neighbor
print p
loop:
    n = get a number from left neighbor
    if (p does not divide n)
        send n to right neighbor

 

Solution

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

#define MAX 36

int gen_num(){
	int state;	//wait인수
	int p[2];	//2~35까지 담을 파이프라인
    pipe(p);	//파이프 라인 열기
    
    //child : 2~35까지 파이프라인에 쓰기 parent : 파이프라인에 적힌 파일 리턴
    if(!fork()){	//child
    	close(p[0]);	//파이프라인 읽기영역 닫기
    	for(int i = 2; i < MAX; i++){
        	write(p[1],&i,4);
        }
        close(p[1]);	//파이프라인 쓰기영역 닫기
     	exit(0):		//child 종료
    }
    //parent
    close(p[1]);		//파이프라인 쓰기영역 닫기
    wait(&state)		//child 종료까지 대기
    return p[0];		//2~35까지 적은 파일 리턴
}

int prm_filter(int fd,int prime){
	int n;				//fd에 담긴 숫자
    int state;			//wait()인수
    int p[2];			//리턴할 파이프라인
    
    pipe(p);			//파이프라인 열기
    
    //child : prime의 배수가 아닌 수들 파이프에 쓰기 parent: 파이프 읽고 리턴
    if(!fork()){		//child
   		close(p[0]);	//읽기라인 닫기
        while(read(fd,&n,4))){		//파일 끝까지 읽기
        	if(n%prime != 0){		//소수의 배수가 아니면 파이프에 적기
            	write(p[1],&n,4);
            }
        }
        close(fd);
        close(p[1]);
        exit(0);
	}
    close(p[1]);
    wait(&state);
    close(fd);
    return p[0];
}

int main(){
	int prime;
    int nums = gen_num():	//2~35 생성
    while(read(num,&prime,4)){			//파일 끝까지 읽기
    	printf("prime %d\n",prime);		//소수 출력
        num = prm_filter(num,prime):	//파일 새로 쓰기
    }
}