操作系统复习 MITS6.1810 lab util 记录

lab util

sleep

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

    • See kernel/sysproc.c for the xv6 kernel code that implements the sleep system call (look for sys_sleep), user/user.h for the C definition of sleep callable from a user program, and user/usys.S for the assembler code that jumps from user code into the kernel for sleep.
  2. 代码:

    #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

  1. 单个管道一般用于单向通信,父子进程可通过两个管道进行双向通信。(管道详细行为参考 primes 实验部分)

  2. 代码:

    #include "kernel/types.h"
    #include "user/user.h"
    
    #define BUFFSIZE 128
    
    void 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 neighbor
print p
loop:
    n = get a number from left neighbor
    if (p does not divide n)
        send n to right neighbor

思路

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

如上图,除去第一个进程和最后一个进程,每个进程有两种身份(父/子)。

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

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

    • 如果 left-side-pipe 的写端关闭且没读到数据,代表没有数据到达。本进程任务结束,正常 exit.
  2. 建立一个新的 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 0

void 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);
}

知识点

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

find

  1. 思路:查找待查找目录下所有条目:

    • 如果是目录,递归查找
    • 如果是普通文件,比对文件名,输出
  2. 实现:参考 ls.c 实现。目录文件本质也是一个文件,不过文件内容是一个个 directory entry. 因此对于目录,读取其文件内容至 dir_entry 中,判断其类型,进行相应处理。

  3. 代码:

#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 <directory> <filename>\n", argv[0]);
    exit(1);
  }
  find(argv[1], argv[2]);
  
  exit(0);
}

热门相关:亿万盛宠只为你   诱人的乡下姑娘   成人用品店打工妹:亲身体验   年轻嫂子   裙上之臣