6.S081 学习笔记 - Lab-Utilities

xv6 系统调用

系统调用 描述
int fork() 创建一个进程，返回子进程的 PID
int exit(int status) 终止当前进程，并将状态报告给 wait() 函数。无返回
int wait(int *status) 等待一个子进程退出；将退出状态存入 *status; 返回子进程 PID。
int kill(int pid) 终止对应 PID 的进程，返回 0，或返回 -1 表示错误
int getpid() 返回当前进程的 PID
int sleep(int n) 暂停 n 个时钟节拍
int exec(char *file, char *argv[]) 加载一个文件并使用参数执行它；只有在出错时才返回
char *sbrk(int n) 按 n 字节增长进程的内存。返回新内存的开始
int open(char *file, int flags) 打开一个文件；flags 表示 read/write；返回一个 fd（文件描述符）
int write(int fd, char *buf, int n) 从 buf 写 n 个字节到文件描述符 fd; 返回 n
int read(int fd, char *buf, int n) 将 n 个字节读入 buf；返回读取的字节数；如果文件结束，返回 0
int close(int fd) 释放打开的文件 fd
int dup(int fd) 返回一个新的文件描述符，指向与 fd 相同的文件
int pipe(int p[]) 创建一个管道，把 read/write 文件描述符放在 p[0] 和 p[1] 中
int chdir(char *dir) 改变当前的工作目录
int mkdir(char *dir) 创建一个新目录
int mknod(char *file, int, int) 创建一个设备文件
int fstat(int fd, struct stat *st) 将打开文件 fd 的信息放入 *st
int stat(char *file, struct stat *st) 将指定名称的文件信息放入 *st
int link(char *file1, char *file2) 为文件 file1 创建另一个名称 file2
int unlink(char *file) 删除一个文件

除非另外声明，这些系统调用返回 0 表示无误，返回 -1 表示出错

fork()

  • fork() 在父进程返回子进程 pid，在子进程返回 0
  • 子进程会从 fork() 后开始执行代码
  • 父进程和子进程拥有相同且独立的内存空间（修改一个进程的变量不影响另一个进程）
  • 父进程和子进程拥有相同且独立的文件描述符表，但因 fork() 在子进程生成的描述符与父进程是共享偏移量的

exit () 和 wait ()

  • exit(int status) 会结束当前进程，释放所有资源。通常 status 为 0 表示成功，为 1 表示失败
  • int wait(int *status) 会等待直到一个子进程退出，返回对应的子进程 PID。子进程的退出状态会复制到 status 所指向的地址
  • 如果有多个子进程，wait() 只会等待第一个退出的子进程
  • 如果没有子进程，wait() 立即返回 -1。因此如果子进程先于父进程 wait() 退出，父进程会一直等待。
  • 如果不关心子进程的退出状态，可以将 0 作为 wait() 的参数

exec()

  • int exec(char *file, char *argv[]) 会执行 file 路径的程序，并以 argv[] 作为执行该程序的参数
  • 如果执行成功，则原程序的内存映像完全被新运行的程序替换
  • 只有在执行失败时才会返回原程序继续执行
  • argv[0] 往往是所执行程序的名称，所以有效的参数一般从 argv[1] 开始，最后一个参数是 0

read () 和 write ()

  • 一般 0，1，2 分别代表标准输入，标准输出和标准错误
  • int read(int fd, char *buf, int n) 从 fd 读取最多 n 字节存入 buf 并返回读取的字节数
  • read() 会使 fd 的偏移量前进读取的字节数，下一次从此处继续读取。但每次都是从 buf[0] 开始写入读取的数据
  • 当没有字节可读时，read() 返回 0
  • int write(int fd, char *buf, int n) 将 buf 中的 n 字节写入 fd 并返回写入的字节数
  • 只有发生错误时 write() 才会写入小于 n 字节的数据
  • write() 会使 fd 的偏移量前进写入的字节数，下一次从此处继续写入

与管道的行为

  • 读取管道时，如果没有数据 read() 会一直等待，直到有新数据到达或所有写入端关闭。所有写入端关闭时，read() 返回 0（因为没有字节可读了）。
  • 向管道写入数据后，在读取前关闭写入端，依然可以从读取端读取数据。读取完毕时 read() 返回 0
  • fork() 时会使管道的描述符增多，因此需要注意关闭不需要的描述符

close ()，open () 和 dup ()

  • 文件描述符本质是一个小整数
  • close(int fd) 会释放文件描述符 fd
  • 新创建的文件描述符总是使用可用的最小整数

  • open(char *file, int flags) 以 flags 指定的标志打开 file 路径的文件，返回其文件描述符

    宏定义 功能说明
    O_RDONLY 只读
    O_WRONLY 只写
    O_RDWR 可读可写
    O_CREATE 如果文件不存在则创建文件
    O_TRUNC 将文件截断为零长度
  • 以上标志可以组合，如 O_CREATE | O_WRONLY
  • dup(int fd) 返回一个新的文件描述符，指向与 fd 相同的文件，偏移量与原描述符的相同

  • 只有 fork() 和 dup() 创建的同一文件的新描述符才和原描述符共享偏移量，因此即使对同一文件 open() 两次，两个描述符也不共享偏移量

pipe()

  • pipe(int p[]) 创建一对管道，将读和写描述符分别存入 p[0] 和 p[1]

文件系统

stat 结构体包含文件的类型，大小等信息

1
2
3
4
5
6
7
8
9
10
11
#define T_DIR     1   // 目录
#define T_FILE    2   // 文件
#define T_DEVICE  3   // 设备

struct stat {
    int dev;     // 文件系统的磁盘设备
    uint ino;    // Inode 编号
    short type;  // 文件类型
    short nlink; // 文件的链接数
    uint64 size; // 文件大小（字节）
};

dirent 结构体包含目录中的文件名和 inode 编号

1
2
3
4
5
#define DIRSIZ 14 // 文件名的最大长度
struct dirent {
    ushort inum;
    char name[DIRSIZ];
};
  • 通过 stat 和 fstat 可以获取文件的 stat 信息
  • 可以用 read 读取文件描述符的信息到 dirent 结构体中

题解

sleep

直接使用系统调用 sleep() 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int
main(int argc, char *argv[])
{
  if(argc != 2 ){
    fprintf(2, "Usage: sleep ticks...\n");
    exit(1);
  }

  int n = atoi(argv[1]);
  sleep(n);
  exit(0);
}
  • argc 是参数个数，argv 是参数列表。第一个参数是程序名，所以有效的参数从 argv[1] 开始
  • fprintf 类似 printf，不过是向指定的文件描述符打印
  • atoi 即 "ASCII to Integer"，将字符串转换为整数

pingpong

创建两对管道分别供父子进程读写来传递消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int
main(int argc, char *argv[])
{
    // 父进程到子进程的管道
    int p1[2];
    // 子进程到父进程的管道
    int p2[2];
    pipe(p1);
    pipe(p2);

    char buf;

    if(fork()==0) {
        read(p1[0], &buf, 1);
        int pid = getpid();
        printf("%d: received ping\n", pid);
        write(p2[1], "B", 1);
    } else {
        write(p1[1], "A", 1);
        read(p2[0], &buf, 1);
        int pid = getpid();
        printf("%d: received pong\n", pid);
    }
    exit(0);
}

primes

本题要求利用管道实现质数筛法，找到 2-35 中的所有质数。即从 2 开始的整数序列中筛除质数的倍数，直到所有数字被处理。

示意图
示意图

如图所示，第一个进程读取从 2 开始的整数，2 为质数，筛除 2 的倍数，将剩余数字传给下一个进程。

后续进程接收到的第一个数为质数，筛除该数的倍数，继续将剩余数字传给下一个进程。如此重复直到所有数字被处理。

算法伪代码如下：

1
2
3
4
5
6
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

思路：

  • 进程需要和左右两个进程通信，因此需要两对管道
  • 进程从左侧管道读取数字，筛除质数的倍数，将剩余数字传给右侧管道
  • 进程读取到的第一个数必是质数
  • 进程的处理逻辑一致，想到可以用递归实现
  • 递归的终止条件是进程读取不到数据
  • 第一个进程没有左侧进程，因此需要手动写入数字
  • 创建子进程的时机应该在读取到数字后，写入数字前

网上的解法大多使用递归实现，这里利用 fork() 的特性迭代实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int
main(int argc, char *argv[])
{
    int prime; // 接收到的第一个数必是质数
    int num; // 缓冲区
    int p1[2]; // 和左侧的管道
    int p2[2]; // 和右侧的管道
    pipe(p1);
    pipe(p2);

    for(int i = 2; i < 36; i++){
        write(p1[1], &i, sizeof(i));
    }
    close(p1[1]);

    prime = 2;
    // 父进程不会执行，子进程会执行一次
    while(fork()==0) {
        // 在子进程中将左侧的管道替换为父进程右侧的管道
        p1[0] = p2[0];
        p1[1] = p2[1];
        close(p2[1]);  // 替换掉的文件描述符依然存在，需要先手动关闭
        pipe(p2);

        // 读取父进程传来的质数
        if(read(p1[0], &num, sizeof(num))){
            prime = num;
            printf("prime %d\n", prime);
        } 
        // 最后一个进程读不到数据，直接退出
        else {
            exit(0);
        }
    }

    // 读取剩下的数字，筛除质数的倍数
    while(read(p1[0], &num, sizeof(num))){
        if (num % prime != 0){
            write(p2[1], &num, sizeof(num));
        }    
    }
    
    close(p2[1]);
    wait(0);
    exit(0);
}
  • 由于 fork() 的特点，每个子进程只会执行一次 while 循环，并在退出循环时创建新的子进程。
  • xv6 的文件描述符资源有限，需及时关闭不用的文件描述符，否则会耗尽资源

find

本题要求实现一个简单的 find 命令，在指定目录及其子目录下查找指定文件，用法如下：

1
find path filename

思路：

  • 首先检查参数个数是否正确
  • 判断 path 是否是目录，如果不是则报错
  • 遍历 path 目录下的文件，判断文件类型 (stat 中)
  • 如果是文件，比较文件名 (dirent 中) 是否与 filename 相同
  • 如果是目录，递归调用 find
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/fcntl.h"
#include "kernel/fs.h"
#include "user/user.h"

// 在 path 目录及其子目录下查找名为 filename 的文件
void 
find(char* path, char* filename) 
{
  char buf[512], *p;
  int fd;
  struct dirent de;
  struct stat st;

  if ((fd = open(path, O_RDONLY)) < 0) {
    fprintf(2, "find: cannot open %s\n", path);
    return;
  }

  if(fstat(fd, &st) < 0){
    fprintf(2, "find: cannot stat %s\n", path);
    close(fd);
    return;
  }

  switch (st.type)
  {
  case T_FILE:
    fprintf(2, "find: path must be a directory\n");
    return;
  
  case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("find: path too long\n");
      break;
    }
    // 在原路径后加上/，准备目录下的文件路径
    strcpy(buf, path);
    p = buf+strlen(buf);
    *p++ = '/';
    // 读取目录下的文件信息
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0){
        continue;
      }
      // DIRSIZ是目录名称的最大长度
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;  // 在目录名超过限制时截断
      if(stat(buf, &st) < 0){
        printf("find: cannot stat %s\n", buf);
        continue;
      }

      // 是文件则比较文件名
      if (st.type == T_FILE && strcmp(de.name, filename) == 0){
        printf("%s\n", buf);
      }
      // 是目录则递归搜索，不递归 . 和 ..
      else if(st.type == T_DIR){
        if(strcmp(de.name, ".") != 0 && strcmp(de.name, "..") != 0){
          find(buf, filename);
        }
      }
    }
    break;
  }
  close(fd);
}

int
main(int argc, char *argv[])
{
  // 默认在当前目录找
  if (argc == 2) {
    find(".", argv[1]);
  }
  // 在指定目录找
  else if(argc == 3) {
    find(argv[1], argv[2]);
  } else {
    fprintf(2, "Usage: find path filename\n");
  }
  exit(0);
}

xargs

本题要求实现一个简单的 xargs 命令，读取标准输入，将其作为原命令的额外参数执行。如果有多行输入，则对每一行执行一次命令。用法如下：

1
2
3
4
5
xargs command initial-args

# 使用示例，等同于执行 echo hello world
$ echo world | xargs echo hello
$ hello world

思路：

  • 结合 fork 和 exec 在子进程中执行命令，关键是构造新的参数列表
  • 先将 command 和 initial-args 写入参数列表
  • 读取标准输入，遇到空格说明一个参数读取完毕，存入参数列表
  • 遇到换行符说明所有参数读取完毕，将最后一个参数存入参数列表，并执行命令
  • 执行完成后重置参数列表，以便执行下一行
  • 注意避免写入空参数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[])
{
  if (argc < 2)
  {
    fprintf(2, "Usage: xargs command initial-args\n");
    exit(1);
  }

  char c;               // read读取的缓冲区
  char buf[100];        // 参数缓冲区
  char *args[MAXARG];   // 新参数列表
  int bufn = 0;         // 指示buf的末尾
  int argsn = argc - 1; // 指向参数列表的末尾

  // 先将 command 和 initial-args 写入参数列表，最后一个初始参数的位置是args[argc-2]
  for (int i = 0; i + 1 < argc; i++)
  {
    args[i] = argv[i + 1];
  }

  // 从标准输入读取参数，并执行命令
  while (read(0, &c, 1))
  {
    // 如果读到'\n'，说明所有参数已读取完毕，应该执行命令
    if (c == '\n')
    {
      // 避免写入空参数
      if (bufn > 0)
      {
        // 最后一个参数存入参数列表
        buf[bufn] = '\0';
        args[argsn] = (char *)malloc(sizeof(buf));
        strcpy(args[argsn], buf);
        argsn++;
        bufn = 0;
      }
      args[argsn++] = 0; // 标志参数列表结束

      if (fork() == 0)
      {
        exec(args[0], args);
        printf("exec failed\n");
        exit(1);
      }
      else
      {
        wait(0);
        // 执行完成后重置参数列表，以便执行下一行
        memset(args + argc - 1, 0, argsn);
        argsn = argc - 1;
      }
    }
    // 如果读到空格，则当前参数读取完毕，存入参数列表，将buf重置
    else if (c == ' ')
    {
      // 跳过连续空格
      if (bufn > 0)
      {
        buf[bufn] = '\0';
        args[argsn] = (char *)malloc(sizeof(buf));
        strcpy(args[argsn], buf);
        argsn++;
        bufn = 0;
      }
    }
    else
    {
      buf[bufn++] = c;
    }
  }
  exit(0);
}
操作系统
#6.S081
6.S081 学习笔记 - Lab-Utilities
http://blog.qzink.me/posts/6.S081学习笔记-Lab-Utilities/
作者
Qzink
发布于
2025年1月4日
许可协议