Project 2: User Programs #

实验环境配置和运行 #

实验开始之前，同学们需要检查 src/userprog/Make.vars 中最后一行代码，看看其调用的是否是 bochs，需要将其改为：SIMULATOR = --bochs 。（如本就是使用的是 qemu 则不用改）

建议用一个空白的 Pintos 系统来实现，以防止 Project 1 对 Project 2 的影响。

本次实验建议使用 huahuaxiaomuzhu 开发的 debug-my-pintos 工具。可在 VS Code 里可视化设置断点并调试。

实验的意义探究 #

我们知道，Pintos 实验旨在通过补充代码，实现一个小型的操作系统。那么这个操作系统，到底是什么级别的系统呢？

这个需要从 Intel 公司的 80x86 系列处理器说起。通过之前计组和系统编程已经学习到的知识，大家应该都知道 8086 处理器是一个 16 位处理器，系统总线 20 根，可寻址最大内存空间达 1MB，范围是 00000H-FFFFFH，但其内部的寄存器和 ALU 都只有 16 位，所以在寻址时，需要将段地址乘以 16，再加上偏移地址，以此来实现 20 位的寻址。这都是后话，最主要的是，在 8086 时代，用户可以直接寻址到内存空间的任何位置，这就有可能导致用户错误地修改某些地址值，导致系统崩溃。

由于技术的进步以及人们对多用户操作同一台电脑的需求，在 80386 时代，终于将系统的工作方式给分离了，80386 具有实模式、保护模式和 v68 模式这三种工作模式。其中，实模式其实算是 8086 体系的延续，在该模式下的寻址方式和 8086 无异，这个模式也是为了兼容 16 位体系下的程序。而用户一般所处的状态就是保护模式，在这个模式下可以使用 386 系统的 32 根主线，寻址模式发生根本性的变化，最主要的是引入了特权级的概念，由于我们知道在 8086 时代，随意的内存修改可能导致系统崩溃，而想要避免这种崩溃，就需要把系统内核给保护起来，为此，386 有个 4 个特权级 r0-3，我们的系统内核在最高级别 r0 中，特权级所处的内存空间分置，允许高特权级访问低特权级内存空间，而不允许反向地访问。那么这样一来，确实避免了随意对内存空间的修改，可又引出了一些新的问题，比如系统对外设端口的调用，是通过中断的方式进行的；比如创建新的进程等，这些函数都被内核给把持着，当一个用户想要手动开启这些功能的时候，就遇到了无法访问的问题，这个时候，就需要让低特权级向高特权级发起一个建议，这个建议我们把他叫做系统调用，使用系统调用，就可以让用户在低特权级下使用高特权级的功能。

而这，就是我们第二次实验所要完成的事情。

实验思路讲解 #

在本次实验的主线是实现 13 个系统调用，我们可以大致将这 13 个系统调用分为两部分：与进程有关的（exec, wait, exit）系统调用和其他系统调用。

与进程相关的系统调用实现会略为复杂：

• exec 中需要我们实现参数的分离与传递
• wait 中需要我们实现进程之间的等待，并能够处理异常输入
• exit 中需要我们能够完整的回收进程所使用的资源。

其中，exec 单独作为 任务 1 参数分离出现，任务 2 则是要完成全部 13 个系统调用

对于栈区的理解 -> 拓展阅读

PintOS 中使用了与 8086 处理器 相同的函数调用规则：

1. 调用者需要先将函数所需的参数按照从右到左的顺序依次入栈（堆栈是向下增长的，用 C 语言的形式来描述，每一次入栈操作都形同于 *--sp = value）
2. 调用者使用 call 指令完成如下两件事：
   • 将调用者的下一条指令地址入栈 （return address）
   • 将指令寄存器指向被调用者的第一条指令
3. 被调用者执行时，栈寄存器指向的是 return address。
4. 如果被调用者有返回值，将会存至寄存器 eax 中
5. 返回时，被调用者使用 ret 指令完成如下两件事：
   • 将返回地址出栈
   • 将指令寄存器指向刚出栈的地址。
6. 返回后，调用者将参数依次从栈中弹出，继续运行。

在实验过程中，我们将在两个地方考察对栈的理解：

1. 系统调用本身也可以理解为一次函数调用，我们需要通过栈寄存器 esp 获得系统调用的参数
2. 在系统调用 exec 中，PintOS 将通过模拟 ret 指令来运行用户程序并给用户程序传递参数，为此，我们需要在返回之前，将栈区模拟为即将返回的状态（即当前的栈寄存器指向 return address，其上包含用户程序的全部参数。）

评测的一些细节

在评测的过程中，实际上是运行了一个用户程序(userprog)，并通过用户程序的输出来判断测试点是否通过。因此，在实现 exec , write 等系统调用之前，是无法正常评测的。

为了能够帮助大家更快的上手 Project2 ，这里提供一个实现参考顺序：

1. 在 setup_stack() 函数中，令 *esp = PHYS_BASE - 12 ，这一步实际上是放弃了参数的传递（减去的 12 其实分别对应 argv , argc ，return address ），这样可以让我们的 OS 能够执行不含参数的测试点。

2. 搭建系统调用的框架并实现 exit 和 write 调用，让用户程序可以正常的输出字符串并退出。随后，在 process_wait 中额外增加一句 sleep 确保会在子线程执行结束后返回（正确的实现方式是在子线程结束后立即返回，这里为了确保子线程结束，请把 sleep 等待的时间写的稍微长一点）

   其实只要实现 fd=1 时的 write 函数就已经可以让用户程序输出了。在这里可以选择只实现这一部分的 write，完整版的 write 在写完参数传递后在接着完成。

前置任务：打印进程退出信息 #

Pintos 要求每一次退出时都打印退出代码，没有这个打印行为，几乎所有的点都无法通过，但其本身没有点。首先我们需要在 threads/thread.h 函数中修改 thread 结构体，为其添加退出码这个值，其次我们在系统调用 exit 时，需要将退出码存储在结构体中，最后在 userprog/process.c 中 process_exit() 函数中按文档所给的格式（见 3.3.2）打印退出码。（这里需要解释一点，Pintos 实验做到这里时，仍没有区分线程和进程的概念，一定程度上可以混用）。

任务 1：参数分离 #

上表是该任务对应的点以及分别在考察什么。

第一个任务，实际上较为复杂，我们需要观察进程的创建过程，在 process.c 的 process_execute 即为我们的线程创建函数。其中 file_name 就是我们传递进来的参数，但是它不仅包含了我们要执行的函数，也包括了后面的参数，所以这里需要进行字符串分割。幸运的是，Pintos 已经为我们提供了一个字符串分割的函数，声明在 lib/string.h 中。

分割完参数后，可以看到进程拉起了一个线程，我们需要在线程的创建函数中 start_process 中，将参数放置于 esp 的对应位置。堆栈结构请参照 3.5.1。

同学们可参照压栈图，将分割出的参数压栈到中断现场的合适位置。

任务 2：系统调用 #

调用参数所处内存地址 #

该任务的目的是，检查我们传递的参数的内存地址，正如我们在实验目的里阐述的，使用特权级的目的是保护内存，这里也是一样，Pintos 将 kernel 和用户内存空间分成了两部分，如下图所示，BASE 以上是内存空间，08048000-BASE 之间，才是用户进程空间，如果一个指针，指向了没有权限的位置，就应该直接以 -1 退出。文档的 3.1.5 部分给我们提供了两种思路，一种是 userprog/pagedir.c 和在 threads/vaddr.h 中的相关函数 pagedir_get_page，来验证地址范围，一种是通过访问该地址，来造成 page_fault，在 page_fault 处理函数中，再退出。

PHYS_BASE +----------------------------------+
            |            user stack            |
            |                 |                |
            |                 |                |
            |                 V                |
            |          grows downward          |
            |                                  |
            |                                  |
            |                                  |
            |                                  |
            |           grows upward           |
            |                 ^                |
            |                 |                |
            |                 |                |
            +----------------------------------+
            | uninitialized data segment (BSS) |
            +----------------------------------+
            |     initialized data segment     |
            +----------------------------------+
            |           code segment           |
0x08048000 +----------------------------------+
            |                                  |
            |                                  |
            |                                  |
            |                                  |
            |                                  |
        0 +----------------------------------+

Tip 2：

这里一定要记得，参数的地址不一定是连续的，而且每个参数的地址都是 4 个 byte，注意有可能一个参数地址一半跨越界限，一半不跨越的情况。

打开关闭文件 #

这一块是过点的集中地，很容易写完后过许多点，收获做实验的满足感。

相信做过 Project 1 的同学们对 Pintos 中的链表结构都不陌生了，我们可以使用链表（如果愿意的话你也可以使用数组）来维护打开的文件列表，同时按我们已有的知识，，每一个打开的文件都需要有一个文件描述符 fd，且 fd 在不同进程中不共享，所以可见是由进程维护描述符，同时，0，1，2 三个描述符已经默认分配，所以我们必须从 3 开始为新打开的文件分配描述符。

Tip 3：

实验过点的文件不会打开很多，所以不需要考虑关闭文件后，描述符的重新利用。

同理，打开一个文件需要文件地址，这个地址，也是需要我们进行地址判断，防止其越界。到了这里，我们就可以使用 filesys/filesys.c 中定义的 filesys_open 来完成 open 的系统调用了。同时也要在进程中维护打开的文件列表。

关闭也是同理，我们需要将维护的文件及其描述符从进程的文件列表中移除，并使用 file_close 关闭该文件。

Tip 4：

在维护打开文件元素时，使用了 malloc 的话，记得一定要在关闭时释放，这一点对于后面的某个点至关重要。同时注意，在一个进程退出时，也应该关闭其打开的所有文件。

创建移除文件 #

这一部分较为简单，创建文件调用 filesys/filesys.c 中定义的 filesys_create 即可，移除调用 filesys/filesys.c 中定义的 filesys_remove。

读写文件 #

和创建移除一样，比较简单，参照 3.3.4 的参数格式，同时对于 write，我们已经实现了向终端写入。read 会用到 input_getc()与 file_read()，write 会用到 file_write()与 putbuf()。

Tip 5：

这里除了注意参数是否和法外，还需要判断缓冲区是否合法。

执行与等待 #

该部分为创建子进程和父进程等待子进程并回收，也是一个难点。

这里我们还需要提到前面讲过的一点，Pintos 在这里还没有特别区分进程和线程的概念，可以理解为一个线程就是一个进程，所以其 ID 可以一一映射。该部分的重点在于父进程需要维护创建的子进程列表。子进程的创建过程其实就是我们前面修改过的 process_execute() 函数。注意到在该函数的 thread_create 函数执行后，其实子进程就已经转移到 start_process 中开始运行或者加入就绪队列了。这里我们要保证子进程一定成功创建，就需要实现一个同步锁，来保证子进程 load 成功才接着执行父进程，子进程一旦创建失败，说明该该调用失败了。

而对于 wait 操作，很明显也需要一个锁，保证父进程在子进程执行期间无法进行任何操作，等待子进程退出后，父进程获取子进程退出码，并回收资源。这里的锁的设计非常精妙，要保证父进程 wait 时，无法执行任何操作，子进程退出时，需要立刻通知父进程，但不能直接销毁，而要等待父进程来回收资源获取返回码等，然后才可以正常销毁。需要几个锁来完成这个操作，同学们可以好好考虑。

multi #

这一部分几乎没有需要多写的，只需要完成 filesize 这个系统调用。

filesize 在文档中的声明为：int filesize (int fd);

所以需要我们用 fd 去寻找打开的文件。实现时调用 file_length 就行。

rox #

这一部分旨在防止进程修改正在运行的可执行文件，详见文档中的 3.3.5

可执行文件在 Pintos 中的定义为用来创建进程的文件，即创建进程时打开的那一个文件。filesys/file.c 文件中定义了函数 file_deny_write()，该函数可以禁止对文件的写操作。我们需要在 load 时，禁止对该文件的写操作，在退出时回复。

同时这一块需要实现 seek 调用。需要用到 file_seek() 函数。

bad #

这一部分，理论上要是做到了前面的每个地址访问都验证地址合法性，是可以直接通过的。如果有不通过，除了补充前面的不足外，由于访问非法地址会引起 page_fault，所以我们可以在 exception.c 中对 page_fault()进行修改，在 kill 时结束进程，返回 -1.

资源释放 #

该部分旨在探究同学们编码过程中，对于资源的合理理由，务必要做到每一个资源申请后，都会有释放。包括前面提到的文件的退出，消除开辟的内存空间，同时注意到进程退出时，关闭所有打开的文件，以及 open、close、create、remove、execute、wait 等所有过程中开辟的空间都需要关闭。

正常分支流（新进程会从 2 开始）：

• 创建第 0 号进程（根进程），参数为 RECURSE
• 如果进程的参数是 CRASH，跳转到崩溃分支流执行
• 如果进程号是 0，执行 10 次以下的操作，否则只执行 1 次以下的操作：
  • 如果进程号大于 15，创建 n+1 号进程，参数为 CRASH
  • 验证子进程返回值是否为 -1
  • 创建 n+1 号进程，参数为 RECURSE，如果创建失败则返回 n（此处失败是因为资源不够了），否则等待子进程返回值
  • 比对每次子进程的返回值，观察是否都相同（不相同则会 FAIL）
• 疯狂打开文件直到不能打开或打开超过了 126 个文件
• 如果是 0 号进程，验证下递归打开的进程层数是不是不小于 30，不是的话报错
• 返回子进程返回值

崩溃分支流

• 疯狂打开文件指定不能打开或打开超过了 126 个文件
• 从 bad-write、bad-read、bad-write2、bad-read2、open-bad-ptr 中随机选择一种方式来触发异常然后退出

文件系统 #

其中 74-76 涉及到了文件的锁，我们需要对文件系统设计一个锁，在所有用到的操作中，操作前都上锁，操作后都去除锁，基本上就可以实现。这一部分的修改在 filesys.h 和 filesys.c 中完成。