lab utilsleep

介绍：主要用来熟悉下环境以及代码结构。

See kernel/sysproc.cfor the xv6 kernel code that implements the sleepsystem call (look for sys_sleep), user/user.hfor the C definition of sleepcallable from a user program, and user/usys.Sfor the assembler code that jumps from user code into the kernel for sleep.

代码：

(资料图片仅供参考)

#include "kernel/types.h"#include "user/user.h"int main(int argc, char *argv[]){  if (argc <= 1) {    fprintf(2, "usage: sleep `time`...\n");  }    int tick_num = atoi(argv[1]);  sleep(tick_num);    exit(0);}

pingpong

单个管道一般用于单向通信，父子进程可通过两个管道进行双向通信。（管道详细行为参考 primes实验部分）

代码：

#include "kernel/types.h"#include "user/user.h"#define BUFFSIZE 128void perror_exit(char* err_msg) {  fprintf(2, "%s\n", err_msg);  exit(-1);}int main(int argc, char *argv[]){  int toson_fd[2];  int toparent_fd[2];  int ret1 = pipe(toson_fd);  int ret2 = pipe(toparent_fd);  if (ret1 == -1 || ret2 == -1) {    perror_exit("pipe error");  }    int pid = fork();  if (pid == -1) { //     perror_exit("fork error");  } else if (pid == 0) { // child process    close(toson_fd[1]);    close(toparent_fd[0]);    // read from the pipe1    char buf[BUFFSIZE];    int rbytes = read(toson_fd[0], buf, sizeof(buf));    if (rbytes == -1) {      perror_exit("read error");    }    buf[rbytes] = "\0";        // print the msg from parent    fprintf(1, "%d: received %s\n", getpid(), buf);    // write response to parent (to pipe2)    char resp[4] = "pong";    int ret = write(toparent_fd[1], resp, sizeof(resp));    if (ret == -1) {      perror_exit("write error");    }  } else { // parent process    close(toson_fd[0]);    close(toparent_fd[1]);    // write to son    char msg[4] = "ping";    int ret = write(toson_fd[1], msg, sizeof(msg));    if (ret == -1) {      perror_exit("write error");    }    // read from son    char buf[BUFFSIZE];    int rbytes = read(toparent_fd[0], buf, sizeof(buf));    if (rbytes == -1) {      perror_exit("read");    }    buf[rbytes] = "\0";    // print the resp from son    fprintf(1, "%d: received %s\n", getpid(), buf);  }  exit(0);}

primes介绍

实验要求通过 fork 和 pipe 系统调用建立起如下素数筛的 pipeline.

p = get a number from left neighborprint ploop:    n = get a number from left neighbor    if (p does not divide n)        send n to right neighbor

思路

CSP 的关键点在于：单个步骤内部操作是串行的，所有步骤之间是并发的。步骤之间的通信通过特定的 channel 完成，这里通过 pipe完成。

如上图，除去第一个进程和最后一个进程，每个进程有两种身份（父/子）。

分析上述 pipeline, 每个进程需做如下事情：

从 left-side-pipe 中读取数据，尝试打印素数 prime。

如果 left-side-pipe 的写端关闭且没读到数据，代表没有数据到达。本进程任务结束，正常 exit.

建立一个新的 right-side-pipe, fork 出一个子进程, 自身即作为“父身份”根据第一步得出的 prime 进行 filter, 将过滤后的数据传入 right-side-pipe. wait 子进程，等待子进程打印结束。

进程 p0 由 shell fork 创建，如果 p0 不 wait 子进程，父进程 p0 可能在所有子进程打印完成前结束，此时 shell 会向终端输出提示符$，造成 $穿插在打印结果中的现象。不 wait:子进程还在运行，父进程结束 -> 孤儿进程 -> 由 init 收养。缺点：原父进程得不到子进程的状态。父进程还在运行，子进程结束 -> 僵尸进程。缺点：占用资源得不到释放 (task_struct)。

notes: fork 出来的子进程重复上述操作。

注意点注意 close(pipe) 的时机，最保险的做法是尽可能早关闭不需要的读写端。wait 操作。错误处理。代码

#include "kernel/types.h"#include "user/user.h"#define NULL 0void perror_exit(char* err_msg) {  fprintf(2, "%s\n", err_msg);  exit(-1);}void child_processing(int left_pipe[2]) {  // every process do things below：  // 0. read from left-side pipe, and try to print a prime.  // 1. create a new right-side pipe, do fork, pass the filtered data to right-side pipe.  // notes: The new child processes forked will recursively do the above tasks.  close(left_pipe[1]);  int prime;  int rbytes = read(left_pipe[0], &prime, sizeof(prime));  if (rbytes == -1) {    close(left_pipe[0]);    perror_exit("read error");  } else if (rbytes == 0) {    // No more data reaches here    close(left_pipe[0]);    exit(0);  } else {    fprintf(1, "prime %d\n", prime);  }  int right_pipe[2];  int ret = pipe(right_pipe);  if (ret == -1) {    perror_exit("pipe error");  }  ret = fork();  if (ret == -1) {    perror_exit("fork error");  } else if (ret > 0) { // parent/current process    close(right_pipe[0]);    // do filtering, write data into the right-side pipe    int num;    while ((rbytes = read(left_pipe[0], &num, sizeof(num))) != 0) {      if (rbytes == -1) {        perror_exit("read error");      }      if (num % prime != 0) {        write(right_pipe[1], &num, sizeof(num));      }    }    // if rbytes == 0, no more data reaches. the job of this process is done    close(left_pipe[0]);    close(right_pipe[1]);        wait(NULL);    exit(0);  } else if (ret == 0) { // child process    child_processing(right_pipe);  }} int main(int argc, char* argv[]){  int pipe_fds[2];  int ret = pipe(pipe_fds);  if (ret == -1) {    perror_exit("pipe error");  }  // create child process  int pid = fork();  if (pid == -1) {    perror_exit("fork error");  } else if (pid == 0) {  // child process    // read from pipe, do filtering and pass the data to next stage    child_processing(pipe_fds);  } else {  // parent process    close(pipe_fds[0]);        const int MAX = 35;    for (uint32 i = 2; i <= MAX; ++ i) {      write(pipe_fds[1], &i, sizeof(i));    }    close(pipe_fds[1]);    wait(NULL);  }  exit(0);}

知识点多个写者向同一管道写数据时，可以确保写入不超过 PIPE_BUF 字节的操作是原子的。即假设 A 写入数据 aa; B 写入数据 bb. 可以保证管道内数据必是 aabb 或者 bbaa，不会出现 abab 此类交叉的情况。如果写入数据量超过限制，内核会将其切分成若干个片段进行传输，write()调用会阻塞直到所有数据都被写入管道位置（此时便可能出现数据交叉的情况）。如果管道的写端被关闭，从读端读数据的进程读完所有剩余数据后，将会看到文件结束，read()返回 0.管道容量是有限的，非特权进程可以通过 fctnl(fd, F_SETPIPE_SIZE, size)进行修改，修改范围为 pagesize 和 /proc/sys/fs/pipe-max-size 之间。更大的管道容量意味着更少的上下文切换。管道用于单向通信，即某进程在一端读，另一进程在一端写。如果允许父子进程都能够读/写同一管道，那么会发生竞争，需要额外的同步机制。如果需要双向通信，分别在两个方向上各设立一个管道即可。关闭未使用管道 fd.如果读进程没有关闭管道的写端，那么在其他进程关闭了写入文件描述符后，读者也不会看到文件结束，因为内核知道至少还存在一个管道的写入描述符打开着，即读取进程自己。如果写进程没有关闭管道的读端，那么即使其他进程已经关闭了读端文件描述符，写进程仍然能够向管道中写入数据，最后管道被写满，后续的写入请求会被永远阻塞。当进程尝试向一个管道写入数据，但是没有进程占用该管道读端时，内核会向进程发送 SIGPIPE信号，默认处理会杀死进程。find

思路：查找待查找目录下所有条目：

如果是目录，递归查找如果是普通文件，比对文件名，输出

实现：参考 ls.c实现。目录文件本质也是一个文件，不过文件内容是一个个 directory entry. 因此对于目录，读取其文件内容至 dir_entry 中，判断其类型，进行相应处理。

代码：

#include "kernel/types.h"#include "kernel/stat.h"#include "kernel/fs.h"#include "user/user.h"char* fmtname(char *path) {  static char buf[DIRSIZ+1];  char *p;  // Find first character after last slash.  for (p = path + strlen(path); p >= path && *p != "/"; p--)    ;  p++;  // Return blank-padded name.  if (strlen(p) >= DIRSIZ)    return p;  memmove(buf, p, strlen(p));  memset(buf+strlen(p), " ", DIRSIZ-strlen(p));  return buf;}void find(char* path, char* file_name) {  int fd = open(path, 0);  if (fd < 0) {    fprintf(2, "find: cannot open %s\n", path);    goto clean;  }  int ret;  struct stat st;  ret = fstat(fd, &st);  if (ret < 0) {    fprintf(2, "find: cannot stat %s\n", path);    goto clean;  }  if (st.type != T_DIR) {    fprintf(2, "find: the first param should be directory\n");    goto clean;  }  char buf[512];  if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {    fprintf(2, "find: path too long\n");    goto clean;  }    strcpy(buf, path);  char* p = buf + strlen(buf);  *p++ = "/";  struct dirent de;  while (read(fd, &de, sizeof(de)) == sizeof(de)){    if (de.inum == 0)      continue;    memmove(p, de.name, DIRSIZ);    p[DIRSIZ] = "\0";        if (stat(buf, &st) < 0) {      printf("find: cannot stat %s\n", buf);      continue;    }        switch (st.type) {      case T_FILE:          if (strcmp(file_name, de.name) == 0) {          fprintf(1, "%s\n", buf);        }        break;      case T_DIR:        if (strcmp(".", de.name) != 0 && strcmp("..", de.name) != 0) {          find(buf, file_name);        }        break;      case T_DEVICE:        break;    }  }clean:  close(fd);  return;}int main(int argc, char *argv[]){  if (argc != 3) {    fprintf(2, "Usage: %s  \n", argv[0]);    exit(1);  }  find(argv[1], argv[2]);    exit(0);}