6.S081 Lab: Xv6 and Unix utilities

2026-09-15

我使用 MIT 6.S081 系列课程学习有关操作系统内核的内容，使用的环境为 WSL-Ubuntu 。第一个任务 Boot xv6 就不单开一个板块了，将 xv6 的代码从远程仓库 pull 到本地后，使用 make qemu 一般就能直接启动模拟的内核环境。如果 make 失败可能是没有安装 RISC-V 架构的工具链，MIT 官方也有自己的手册指导工具的安装。
https://github.com/mit-pdos/xv6-riscvhttps://pdos.csail.mit.edu/6.S081/2020/tools.html

Lab-1 的主要任务是在 /user 目录下编写用户态程序，这些程序会和操作系统内核一起被编译，可以直接在 shell 中调用，平时使用 Linux 系统调用的各种命令比如 ls 、ps 其实也都是一个可执行的程序。在理解这个前提后，才能知道实验具体在做什么。

[easy] sleep

这一节要为操作系统实现一个 sleep 的用户程序，以下为实验给出的核心提示和要求。

为 xv6 实现 UNIX 程序 sleep；你的 sleep 应暂停用户指定的若干个 tick。一个 tick 是 xv6 内核定义的时间概念，即定时器芯片两次中断之间的时间。你的解答应放在文件 user/sleep.c 中。
查看 user/ 目录下的一些其他程序（例如 user/echo.c、user/grep.c 和 user/rm.c），了解如何获取传递给程序的命令行参数。
如果用户忘记传递参数，sleep 应打印一条错误信息。
命令行参数以字符串形式传入；你可以使用 atoi 将其转换为整数（参见 user/ulib.c）。
使用 sleep 系统调用。
查看 kernel/sysproc.c 中实现 sleep 系统调用的 xv6 内核代码（查找 sys_sleep），user/user.h 中可从用户程序调用的 sleep 的 C 定义，以及 user/usys.S 中从用户代码跳入内核以执行 sleep 的汇编代码。
确保 main 调用 exit() 以退出你的程序。
将你的 sleep 程序添加到 Makefile 的 UPROGS 中；完成之后，make qemu 将编译你的程序，你就可以从 xv6 shell 中运行它。

这里 pull 下来的 xv6 内核对应 sys_sleep 的系统调用被命名为了 sys_pause ，但内部实现区别不大。

由于课程的实验是使用 MIT 研发的小型操作系统内核，用户程序都是独立编译的，自然就没有 C 标准库（如 stdio.h ）给我们使用了，现在只能使用项目名目录下声明好的头文件来构架用户程序，所以有必要了解内核提供的各个头文件都有什么用处。

kernel/types.h 定义了基本的数据类型，当我们在用户程序中声明各种数据类型的变量，使用 int 、double、char 等词的时候就需要引入该头文件。

typedef unsigned int uint;
typedef unsigned short ushort;
typedef unsigned char uchar;

typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned int uint32;
typedef unsigned long uint64;

typedef uint64 pde_t;

user/user.h 声明了所有用户程序可以调用的函数，包括系统调用和用户库函数。可以说就是 xv6 用户程序的“标准头文件”，替代了 Linux 下的 stdio.h、stdlib.h、string.h、unistd.h 等的功能。

#define SBRK_ERROR ((char *)-1)

struct stat;

// system calls
int fork(void);
int exit(int) __attribute__((noreturn));
int wait(int *);
int pipe(int *);
int write(int, const void *, int);
int read(int, void *, int);
int close(int);
int kill(int);
int exec(const char *, char **);
int open(const char *, int);
int mknod(const char *, short, short);
int unlink(const char *);
int fstat(int fd, struct stat *);
int link(const char *, const char *);
······

现在要实现一个 sleep 的用户程序，该程序接受一个参数表示等待的中断次数，该程序需要使用 sys_pause 这个系统调用，查看它的实现可以发现该系统调用接受的就是中断次数，并且有两种可能返回的值：0 代表系统成功等待了传入的中断次数的时间， -1 表示当前进程由于被杀死而提前结束了。

uint64
sys_pause(void)
{
  int n;
  uint ticks0;

  argint(0, &n);                    //取出第 0 个参数赋值给 n
  if (n < 0)                        //传入的等待次数为负数则修正为 0
    n = 0;
  acquire(&tickslock);
  ticks0 = ticks;
  while (ticks - ticks0 < n) {
    if (killed(myproc())) {
      release(&tickslock);
      return -1;
    }
    sleep_prepare(&ticks);
    release(&tickslock);
    sleep();
    acquire(&tickslock);
  }
  release(&tickslock);
  return 0;
}

发现到这个系统调用其实是需要参数的，但是在函数签名中的参数条目却是 void 。这是因为系统调用不接受 C 语言层面的参数，而是从当前进程的 trapframe 结构体中获得参数，上面的 argint(0, &n) 含义就是从 trapframe 结构体的 a0 字段取出参数。

trapframe 位于进程的一块内存页中，由内核在创建进程时分配，用来保存用户态陷入内核时的寄存器现场。
struct trapframe { /* 0 */ uint64 kernel_satp; // kernel page table /* 8 */ uint64 kernel_sp; // top of process's kernel stack /* 16 */ uint64 kernel_trap; // usertrap() /* 24 */ uint64 epc; // saved user program counter /* 32 */ uint64 kernel_hartid; // saved kernel tp /* 40 */ uint64 ra; /* 48 */ uint64 sp; /* 56 */ uint64 gp; /* 64 */ uint64 tp; /* 72 */ uint64 t0; /* 80 */ uint64 t1; /* 88 */ uint64 t2; /* 96 */ uint64 s0; /* 104 */ uint64 s1; /* 112 */ uint64 a0; /* 120 */ uint64 a1; /* 128 */ uint64 a2; /* 136 */ uint64 a3; /* 144 */ uint64 a4; /* 152 */ uint64 a5; /* 160 */ uint64 a6; /* 168 */ uint64 a7; /* 176 */ uint64 s2; /* 184 */ uint64 s3; /* 192 */ uint64 s4; /* 200 */ uint64 s5; /* 208 */ uint64 s6; /* 216 */ uint64 s7; /* 224 */ uint64 s8; /* 232 */ uint64 s9; /* 240 */ uint64 s10; /* 248 */ uint64 s11; /* 256 */ uint64 t3; /* 264 */ uint64 t4; /* 272 */ uint64 t5; /* 280 */ uint64 t6; };
从 40 偏移之后代表的都是各个寄存器，这些字段用于保存程序在陷入内核态前寄存器的状态。当然一些寄存器的值是有特殊作用的，比如 a0 就是传递给系统调用的第 0 个参数， ra 是返回地址用于指向系统调用执行完后需要执行的下一条指令， a7 存储了系统调用号，等等。
前面 5 个字段表示内核元数据， kernel_satp 表示内核页表的 satp 值，用于定位内核空间。
kernel_sp 代表当前进程的内核栈顶，陷入内核后，内核代码用这个栈。
kernel_trap 表示 usertrap() 的地址，为进入内核态的入口。
epc 为用户态的程序计数器，可以视为 trap 层面的返回地址。
kernel_hartid 为当前 CPU 核心的 hartid ，告诉内核当前进程运行在哪个 CPU 核心上。

在这个任务中，只要能够读取用户输入的参数并调用对应的 sys_pause 系统调用就能实现基本功能了。由于这个程序只接受一个参数，所以可以对用户不输入参数和输入过多参数的情况进行处理。最后程序的代码如下：

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

int
main(int argc, char *argv[])
{
    int ticks;

    if(argc < 2) {
        fprintf(2, "sleep: need an argument\n");
        exit(1);
    }

    if(argc > 2) {
        fprintf(2, "sleep: too many arguments\n");
        exit(1);
    }

    ticks = atoi(argv[1]);
    if(pause(ticks) == -1) {
        fprintf(2, "sleep: current process has been killed\n");
        exit(1);
    }
    exit(0);
}

这里的 exit 函数是一定要写的。平时写的 C 程序， main 函数其实是从 _start 函数调用的，所以在 main 执行完毕后 _start 会帮你调用 exit ，而在 xv6 中 main 就是程序运行的入口，如果不显示调用程序就会一直执行到未定义代码的内存区域，触发崩溃。

[easy] pingpong

这一节需要在用户态实现一个 pingpong 用户程序，核心逻辑是使用 pipe 系统调用创建管道，让父进程和子进程之间相互发送一个字节，并打印相关信息。

编写一个程序，使用 UNIX 系统调用在两个进程之间通过一对管道“乒乓”传递一个字节，每个方向一个管道。父进程应向子进程发送一个字节；子进程应打印 "<pid>: received ping"，其中 <pid> 是它的进程 ID，然后将该字节写入管道传给父进程，并退出；父进程应从子进程读取该字节，打印 "<pid>: received pong"，并退出。你的解答应放在文件 user/pingpong.c 中。
使用 pipe 创建一个管道。
使用 fork 创建一个子进程。
使用 read 从管道读取，使用 write 向管道写入。
使用 getpid 获取调用进程的进程 ID。
将该程序添加到 Makefile 中的 UPROGS。
xv6 上的用户程序可用的库函数有限。你可以在 user/user.h 中查看列表；源代码（系统调用除外）在 user/ulib.c、user/printf.c 和 user/umalloc.c 中。

pipe 系统调用在 Unix 系统中也存在，其作用是创建一个匿名管道。该系统调用期待传入长度为 2 的整型数组，调用成功后该数组的前两个元素会被写入两个文件描述符，其中第零个元素为读端，第一个为写端。

管道是内核中的一个环形缓冲区，数据从哪个写端写入，从读端读出，所以存取原则为先入先出。管道没有名字，只存在于内存中，所以只有两个进程共用一套文件描述符才能进行通信，也就是只能在父子进程之间使用。
管道的行为有以下特点。
当读端存在但管道内部没有数据时，read 会堵塞，直到有数据写入；当写端存在但管道内部已满时，write 会堵塞直到管道内部有空间；当写端关闭时 read 返回 0；当写端关闭时 write 会触发 SIGPIPE 信号，默认终止进程。

当一个管道被创建后，父子进程同时持有一个管道的两个文件描述符，在内核中记录的写入端和读取端的个数都为 2 ，只有当内核记录的写入端或读取端个数为 0 时，才会认为这个管道的某个端口被关闭了。所以如果子进程只负责读取却没有关闭不需要的写入端，哪怕父进程在写入后关闭了，内核中记录的活跃写入端仍为 1 ，read 判定这个写入端还在被使用，导致一直堵塞。所以进程要及时关闭不需要的管道端口。

在 kernel/pipe.c 中的 pipe 结构体中，readopen 和 writeopen 字段就记录了已打开的读入端和写入端数量。
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 };

这个任务中，需要实现两个进程分别向对方发送一个字节的数据，可以创建两个单向管道用于传输，最后代码如下：

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

int
main(int argc, char *argv[])
{
    char byte;

    if(argc != 1) {
        fprintf(2, "pingpong: no argument needed\n");
        exit(1);
    }

    int parent_child[2];
    int child_parent[2];
    pipe(parent_child);
    pipe(child_parent);

    int pid = fork();
    if(pid == 0) {
        close(parent_child[1]);
        close(child_parent[0]);

        read(parent_child[0], &byte, 1);
        if(byte == 'P') printf("%d: received ping\n", getpid());
        byte = 'C';
        write(child_parent[1], &byte, 1);

        close(parent_child[0]);
        close(child_parent[1]);

        exit(0);
    }
    else{
        close(parent_child[0]);
        close(child_parent[1]);

        byte = 'P';
        write(parent_child[1], &byte, 1);
        read(child_parent[0], &byte, 1);
        if(byte == 'C') printf("%d: received pong\n", getpid());

        close(parent_child[1]);
        close(child_parent[0]);

        wait(0);
        exit(0);
    }
}

[moderate/hard] primes

这一节需要实现一个素数筛，并使用流水线的方式进行筛选，任务的描述如下：

使用管道编写一个并发版本的素数筛。这个思路来自 Doug McIlroy —— Unix 管道的发明者。页面中间的那张图以及周围的文字解释了如何实现它。你的解答应当放在 user/primes.c 文件中。
注意关闭进程不需要的文件描述符，否则你的程序会在第一个进程数到 35 之前就把 xv6 的资源耗尽。
一旦第一个进程数到 35，它应当等待整条流水线终止，包括所有子进程、孙进程等等。
因此，主 primes 进程应当只在所有输出都已打印、且所有其他 primes 进程都已退出之后才退出。
提示：当管道的写端被关闭时，read 返回 0
最简单的方式是直接向管道写入 32 位（4 字节）的 int，而不是使用带格式的 ASCII I/O。
你应当按需创建流水线中的进程。
把这个程序添加到 Makefile 的 UPROGS 中。

经过研究，这个算法计算素数的方法是埃拉托斯特尼筛法，它从最小的整数开始，划掉该整数的所有倍数，然后从后面遍历最近的未划掉的数字，这就是一个素数。这个方法其实就是通过遍历把所有可能的约数都去除了，最后留下的数不能被前面任何素数整除。

这里的并发流水线大致遵循了该算法的核心过程，第一条流水线输出当前最小的素数 2 ，然后将剩下 3~35 所有 2 的倍数划去，将剩下的数全部传递给第二条流线。对于第二条流水线而言得到的最小的数（也是第一个取出的元素）为 3 ，这是一个素数直接输出，然后重复前面的过程，直到最后一个流水线无法从 pipe 中读取任何值，直接退出。

可以发现，每个流水线进行的操作逻辑是几乎相同的，这种情况使用递归函数进行就非常适合了。需要注意的是要及时关闭每一个进程用不到的 pipe 端口，首先 xv6 中能够分配的文件描述符资源有限，每个进程保留无用的文件描述符会极大浪费内核资源。其次，如果父进程在写入完数据后没有及时关闭，子进程 read 就会一直堵塞，导致程序永远无法结束。

void
recurrence(int readPort)
{
    int currentPrime, i;

    if(read(readPort, &currentPrime, sizeof(int)) == 0) {
        //最后一个子进程发现 pipe 内没有元素，直接关闭 readPort 并退出
        close(readPort);
        exit(0);
    }
    printf("prime %d\n", currentPrime);

    int primePipe[2];
    pipe(primePipe);

    if(fork() == 0) {
        //子进程不需要 pipe 的写入端和父进程的 readPort
        close(primePipe[1]);
        close(readPort);

        recurrence(primePipe[0]);
    }

    //父进程不需要 pipe 的读入端
    close(primePipe[0]);
    while(read(readPort, &i, sizeof(int)) != 0) {
        if(i % currentPrime == 0)
            continue;
        write(primePipe[1], &i, sizeof(int));
    }

    //父完成读取和筛选后关闭 readPort 和 pipe 输出端
    close(readPort);
    close(primePipe[1]);

    //等待子进程退出
    wait(0);
    exit(0);
}

后续在 main 函数中第一个 pipe ，传入所有的待筛选数据即可。

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

void
recurrence(int readPort)
{
    ······
}

int
main(int argc, char *argv[])
{
    if(argc != 1) {
        fprintf(2, "primes: no argument needed\n");
        exit(1);
    }

    int i = 2;

    int firstPipe[2];
    pipe(firstPipe);

    if(fork() == 0) {
        close(firstPipe[1]);
        recurrence(firstPipe[0]);
    }

    close(firstPipe[0]);
    for(; i<=35; i++) {
        write(firstPipe[1], &i, sizeof(int));
    }

    close(firstPipe[1]);

    wait(0);
    exit(0);
}

[moderate] find

本节需要实现用户态的 find 程序。

写一个简化版的 UNIX find 程序：在一棵目录树中找到所有指定名字的文件。你的解答应放在 user/find.c。
看看 user/ls.c，了解如何读取目录。
用递归让 find 能进入子目录。
不要递归进入 . 和 ..。
文件系统的改动会在多次 qemu 运行之间保留；要得到干净的文件系统，先运行 make clean，再 make qemu。
你需要使用 C 字符串。可以参考 K&R（C 语言书），比如 5.5 节。
注意 == 不像 Python 那样比较字符串。要用 strcmp()。
把该程序加入 Makefile 中的 UPROGS。

可以先观察 ls 的实现，学习操作系统是如何进入不同的目录的。大致阅览过后发现主要使用 open 这个系统调用，获得对应的文件描述符后，使用 fstat 系统调用可以获得该文件的元数据，为一个 stat 结构体。stat 结构体内的 type 字段说明了该 fd 指向的文件的文件类型。是接下来通过文件类型判断是否递归的重要依据。

struct stat {
  int dev;     // File system's disk device
  uint ino;    // Inode number
  short type;  // Type of file
  short nlink; // Number of links to file
  uint64 size; // Size of file in bytes
};

find 程序还需知道文件的名字才能与需要查找的文件进行比较，文件名字存储在 dirent 结构体中。如果是一个目录被抽象成了 fd，那么 fd 中就是所有文件 dirent 结构体。需要注意的是这个结构体存储的文件名字符串不以空字节结尾，不能直接与标准的 C 字符串进行比较。

// The name field may have DIRSIZ characters and not end in a NUL
// character.
struct dirent {
  ushort inum;
  char name[DIRSIZ] __attribute__((nonstring));
};

inum 字段可以视为文件的一个唯一编号，哟关于定位文件系统中真正描述文件的 inode 。值为 0 代表文件被删除了。

在核心的逻辑中，传入的参数应该是一个路径或文件。如果是文件直接和需要查找的文件名对比即可，如果是路径就需要找出路径对应目录的 fd ，然后遍历该目录 dirent 结构体，将每个结构体里面的文件名接在初始传入的路径上，然后递归这个逻辑。因为这个逻辑一开始就对文件的类型进行了分支判断，后面的逻辑只管拼接出目录下每个条目的绝对路径就好了。

上面的过程会类似这样：

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_DEVICE:
    case T_FILE:
        if (strcmp(fmtname(path), filename) == 0)
            printf("%s\n", path);
        break;

    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;
            if (strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                continue;

            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;

            find(buf, filename);
        }
    }
    close(fd);
}

fmtname 代码根据 ls 程序的同名函数小改一下即可，完整的代码：

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"
#include "kernel/fcntl.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));
  buf[strlen(p)] = '\0';
  return buf;
}

void
find(char *path, char *filename)
{
    ······
}

int
main(int argc, char *argv[])
{
    if(argc != 3) {
        fprintf(2, "find: wrong argument amount\n");
        exit(1);
    }

    find(argv[1], argv[2]);
    exit(0);
}

[moderate] xargs

本节中需要实现一个简易版的 xargs 用户程序，该程序的配合管道符 | 使用，会将管道符左侧命令执行的输出作为右侧的输入。 xargs 会将左侧的结果作为附加参数添加在右侧的命令中。

比如下面的命令

echo world | xargs echo hello

管道符左侧的命令 echo hello 原本输出为 world ，现在这个输出会传递给右边， xargs 负责接收这个输出将其作为右侧 echo 的附加参数，最后执行的是：

echo hello world

本节的任务要求和提示如下：

编写一个简化版的 UNIX xargs 程序：从标准输入读取每一行，对每一行运行一条命令，把该行内容作为参数传给这条命令。你的解答应放在文件 user/xargs.c 中。
使用 fork 和 exec 对输入的每一行调用命令。在父进程中用 wait 等待子进程完成该命令。
要读取输入的每一行，可以一次读一个字符，直到出现换行符（'\n'）。
kernel/param.h 中声明了 MAXARG，如果你需要声明一个 argv 数组，它可能会有用。
把该程序加入 Makefile 中的 UPROGS。
对文件系统的修改会在多次 qemu 运行之间保留；要获得一个干净的文件系统，先运行 make clean，再运行 make qemu。

首要任务是读取上一个任务的输出，但是管道符会自动将上一命令的输出作为下一条命令的标准输入，所以在调用 read 时使用的文件描述符还是 0 。

核心任务是读取上一个命令的输出，并使用空格来区分每一个参数，如果上一条命令是多行输出，对于每一行输出都要执行一次 xargs ，所以还需要将换行符作为区分依据之一。

我采用了类似 ELF 中字符串表的形式，将所有的字符串存入一个大的缓冲区 buf ，当读取到空格时则写入空字节作为结束符，参数列表是一个字符串指针数组，每个元素都是对应字符串在大缓冲区中的偏移。

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

int
main(int argc, char *argv[])
{
    int i = 0;
    char *totalArgs[MAXARG];
    char arg[512];
    int base;

    for(; i < argc -1; i++) totalArgs[i] = argv[i+1];
    base = i;

    totalArgs[i] = arg;

    int c = 0;
    for(; read(0, &arg[c], 1) != 0; ) {
        if(arg[c] == ' ') {
            if(i + 1 > MAXARG) {
                fprintf(2, "xargs: too many arguments\n");
                exit(1);
            }

            arg[c] = 0;
            totalArgs[i] = &arg[c+1];
            c++;
            continue;
        }
        if(arg[c] == '\n') {
            arg[c] = 0;
            totalArgs[i+1] = 0;

            if(fork() == 0) {
                exec(totalArgs[0], totalArgs);
                fprintf(2, "xargs: exec failed\n");
                exit(1);
            }

            wait(0);

            i = base;
            totalArgs[i] = arg;
            c = 0;
            continue;
        }
        if (c < sizeof(arg) - 1) c++;
    }

    if (c > 0) {
        arg[c] = 0;
        i++;
        totalArgs[i] = 0;

        if (fork() == 0) {
            exec(totalArgs[0], totalArgs);
            fprintf(2, "xargs: exec failed\n");
            exit(1);
        }

        wait(0);
    }

    exit(0);
}

操作系统