Exercise 1-3. 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 280 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 280.

 

 

 

1. kernel/pipe.c에서 pipe buffer의 길이를 512 -> 0x800(2048)로 수정했다.

2~280까지의 int를 pipe에 적으려면 총 4*279 bytes(==1116 bytes)가 필요하다. 이렇게 편법을 쓰는 건 좋지 않지만, 왜 메모리가 넉넉한 2024년도에 pipe buffer의 크기가 512인 채로 해당 과제를 수행해야 하는지 납득이 가지 않았다.

 

따라서 아래의 kernel/pipe.c 코드에서 #define PIPESIZE의 크기를 2048 bytes로 수정하였다.

// kernel/pipe.c

#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "param.h"
#include "spinlock.h"
#include "proc.h"
#include "fs.h"
#include "sleeplock.h"
#include "file.h"

#define PIPESIZE 0x800

struct pipe {
  struct spinlock lock;
  char data[PIPESIZE];
  uint nread;     // number of bytes read
  uint nwrite;    // number of bytes written
  int readopen;   // read fd is still open
  int writeopen;  // write fd is still open
};

int
pipealloc(struct file **f0, struct file **f1)
{
  struct pipe *pi;

  pi = 0;
  *f0 = *f1 = 0;
  if((*f0 = filealloc()) == 0 || (*f1 = filealloc()) == 0)
    goto bad;
  if((pi = (struct pipe*)kalloc()) == 0)
    goto bad;
  pi->readopen = 1;
  pi->writeopen = 1;
  pi->nwrite = 0;
  pi->nread = 0;
  initlock(&pi->lock, "pipe");
  (*f0)->type = FD_PIPE;
  (*f0)->readable = 1;
  (*f0)->writable = 0;
  (*f0)->pipe = pi;
  (*f1)->type = FD_PIPE;
  (*f1)->readable = 0;
  (*f1)->writable = 1;
  (*f1)->pipe = pi;
  return 0;

 bad:
  if(pi)
    kfree((char*)pi);
  if(*f0)
    fileclose(*f0);
  if(*f1)
    fileclose(*f1);
  return -1;
}

void
pipeclose(struct pipe *pi, int writable)
{
  acquire(&pi->lock);
  if(writable){
    pi->writeopen = 0;
    wakeup(&pi->nread);
  } else {
    pi->readopen = 0;
    wakeup(&pi->nwrite);
  }
  if(pi->readopen == 0 && pi->writeopen == 0){
    release(&pi->lock);
    kfree((char*)pi);
  } else
    release(&pi->lock);
}

int
pipewrite(struct pipe *pi, uint64 addr, int n)
{
  int i;
  char ch;
  struct proc *pr = myproc();

  acquire(&pi->lock);
  for(i = 0; i < n; i++){
    while(pi->nwrite == pi->nread + PIPESIZE){  //DOC: pipewrite-full
      if(pi->readopen == 0 || pr->killed){
        release(&pi->lock);
        return -1;
      }
      wakeup(&pi->nread);
      sleep(&pi->nwrite, &pi->lock);
    }
    if(copyin(pr->pagetable, &ch, addr + i, 1) == -1)
      break;
    pi->data[pi->nwrite++ % PIPESIZE] = ch;
  }
  wakeup(&pi->nread);
  release(&pi->lock);
  return i;
}

int
piperead(struct pipe *pi, uint64 addr, int n)
{
  int i;
  struct proc *pr = myproc();
  char ch;

  acquire(&pi->lock);
  while(pi->nread == pi->nwrite && pi->writeopen){  //DOC: pipe-empty
    if(pr->killed){
      release(&pi->lock);
      return -1;
    }
    sleep(&pi->nread, &pi->lock); //DOC: piperead-sleep
  }
  for(i = 0; i < n; i++){  //DOC: piperead-copy
    if(pi->nread == pi->nwrite)
      break;
    ch = pi->data[pi->nread++ % PIPESIZE];
    if(copyout(pr->pagetable, addr + i, &ch, 1) == -1)
      break;
  }
  wakeup(&pi->nwrite);  //DOC: piperead-wakeup
  release(&pi->lock);
  return i;
}

 

 

2. primes.c

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

__attribute__((noreturn)) void send_sieved(int* p, int limit){
    int pp[2];
    int prime;
    int n;

    if(!read(p[0], &prime, sizeof(int))){
        exit(0);
    }

    printf("prime %d\n", prime);
    if(prime > limit/2){
        while(read(p[0], &prime, sizeof(int))){
            printf("prime %d\n", prime);
        }
        exit(0);
    }

    pipe(pp);


    while(read(p[0], &n, sizeof(int))){
        if(n % prime != 0){
            write(pp[1], &n, sizeof(int));
        }
    }

    close(p[0]);
    close(pp[1]);

    if(!fork()){ // child
        send_sieved(pp, limit);
    }
    else{ // parent
        wait(0);
        exit(0);
    }
}

void prime(int a, int b){
    int p[2];

    pipe(p);
    for(uint i = a; i <= b; i++){
        write(p[1], &i, sizeof(i));
    }

    close(p[1]);

    if(!fork()){ // child
        send_sieved(p, b);
    }
    else{ // parent
        wait(0);
        exit(0);
    }
}

int main(){
    prime(2, 280);

    exit(0);
}