xv6 教材笔记 - 1. Operating system interfaces

• xv6 借鉴了 Unix 的基本接口和内部实现.
• Unix 的接口经过精心设计, 能够组合出丰富的功能. 其他后继者如 BSD, Linux, macOS, Solaris (甚至 Windows) 等都能从中看到 Unix 的影子.
• xv6 使用了传统的内核 (kernel) 的形式, 内核是一个特殊的程序, 用于运行其他程序, 并为其他程序提供系统服务.
• 当一个程序需要使用系统服务时, 它需要执行系统调用 (system call), 系统调用将进入内核, 执行服务, 然后从内核返回. 因此程序在用户空间 (user space) 和内核空间 (kernel space) 之间交替执行.
• 内核使用了由 CPU 提供的一种硬件保护机制来确保每个用户程序只能访问它们各自的内存空间. 内核自身则拥有特权 (privilege), 不收硬件保护机制的限制. 当用户程序请求系统调用时, 用户程序的特权等级将被提升以便执行内核中的预先编排好的系统程序.
• 内核所提供的系统调用就是用户程序所看到的一个操作系统暴露出的接口. xv6 提供了经典 Unix 系统所提供的服务和系统调用的一个子集.
• 相对于内核, shell 是一个代表用户与操作系统进行交互的命令行接口. shell 本质上就是一个普通的用户程序, 它读取用户输入的命令, 然后通过执行合适的系统调用来实现这些命令. 也正是由于 shell 与一般用户程序无异, 用户能够很容易地在不同的 shell 实现之间进行更换.
• xv6 实现的 shell 模仿的是 Unix Bourne shell (即 sh).

1.1 Processes and memory

• 系统调用 fork 用于父进程创建一个新的子进程. 子进程拥有和父进程一模一样的内存映像 (只是看上去一样, 实际上是两个物理地址不同的副本) 和文件描述符表. fork 子进程的 PID, 在子进程中为零.
  • 函数签名: int fork()
• 系统调用 exit 用于停止当前进程的运行并释放当前进程所拥有的所有资源. exit 接受一个整型参数表示退出状态 (exit status), 一般使用 0 表示成功, 使用 1 表示失败.
  • 函数签名: int exit(int status)
• 系统调用 wait 用于父进程等待某个子进程返回. wait 一般由一个父进程调用, 其返回值为一个由 exit 停止的 (或手动被 kill 掉的) 子进程的 PID, 并将子进程的退出状态复制到传入的地址中. 如果没有子进程退出, 那么 wait 将一直阻塞下去. 如果父进程没有任何子进程, 那么 wait 将立即返回 -1. 传入的地址可以是零指针, 表示父进程不关心子进程的退出状态.
  • 函数签名: int wait(int *status)
• 系统调用 exec 用于当前进程动态加载并执行另一个可执行文件. exec 使用硬盘上的某个文件中所存储的内存映像 (memory image) 替换当前正在执行的程序的内存映像 (注意并不替换文件描述符表). 这个文件必须具有某种可解释的格式以指明哪些内容是指令, 哪些又是数据, 程序应该从哪一条指令开始执行等等信息. xv6 使用的格式为 ELF 格式. 一般情况下这种文件是程序员通过编译一个程序的源文件得到的. exec 并不会返回, 而是顺着 ELF 文件中指明的程序起始地址在新程序中继续执行下去. exec 接受两个参数, 第一个是所要执行的可执行文件的名称, 第二个是存储着所要传入的字符串参数的数组.
  • 函数签名: int exec(char *file, char *argv[])
• xv6 shell 就是通过使用 exec 系统调用实现代替用户执行程序的功能的. xv6 shell 程序的主要逻辑是一个 loop 循环, 每次循环都先读取用户的输入, 然后调用 fork 创建子进程, 子进程将负责调用 exec 执行用户想要执行的程序, 而父进程负责调用 wait 等待子进程退出.
  • 初看上去似乎 fork 和 exec 完全可以合并为一个单独的系统调用, 但此后将会了解到 shell 在实现它的 I/O 重定向功能时正是利用了 fork 和 exec 的分离设计.
  • 为了避免 fork 出一个子进程并分配好所有内存之后又立即调用 exec 使用另一个程序的内存映像将其替换掉带来的巨大浪费, 内核使用一种称为写时复制 (copy-on-write) 的虚拟内存技术来优化 fork 的实现.
• 系统调用 sbrk 用于程序 (例如 malloc) 在运行时动态向系统申请内存. sbrk 接受一个整型参数, 表示要申请的字节数. 其返回值为所申请内存块的起始地址.
  • 函数签名: char *sbrk(int n)

1.2 I/O and File descriptors

• 一个文件描述符就是一个整数, 这个整数代表了一个由内核管理的, 能够由进程读取或写入的文件对象. 文件描述符可以通过打开一个文件, 目录或设备 (device) 来获得, 也可以通过创建一个管道 (pipe), 或者通过复制一个已存在的文件描述符来获得. 文件描述符的最大作用是对不同的文件, 管道以及设备进行抽象, 使得它们个个看起来都像是字节流.
• xv6 内部为每个进程单独维护一个表格, 并使用文件描述符充当下标对表格中的文件对象进行索引, 这样每个进程都拥有一组互不相关的文件描述符. 依照惯例, 一个进程从文件描述符 0 读取输入 (此即标准输入 (stdin)), 向文件描述符 1 写入输出 (此即标准输出 (stdout)), 并向文件描述符 2 写入错误信息 (此即标准错误 (stderr)).
• 系统调用 read 用于从由文件描述符索引的文件对象中读取数据. 执行 read(fd, buf, n) 将从文件描述符 fd 中读取至多 (注意不一定刚好) n 个字节至缓冲区 buf 中, 并返回真实读取的字节数. read 读取的字节数少于 n 当且仅当执行过程中出错. 每个文件通过一个偏移 (offset) 标识当前已读取内容的位置, 调用 read 将读取并向前移动这个偏移, 因此本次 read 的结束位置将是下一次 read 的起始位置.
  • 函数签名: int read(int fd, char *buf, int n)
• 系统调用 write 用于向由文件描述符索引的文件对象中写入数据. 执行 write(fd, buf, n) 将从=向文件描述符 fd 中写入至多 (注意不一定刚好) n 个字节至缓冲区 buf 中, 并返回真实写入的字节数. write 写入的字节数少于 n 当且仅当执行过程中出错. 和 read 类似, 每个文件通过另一个偏移标识当前已写入内容的位置, 调用 write 将读取并向前移动这个偏移, 因此本次 write 的结束位置将是下一次 write 的起始位置.
  • 函数签名: int write(int fd, char *buf, int n)
• 系统调用 close 用于释放一个文件描述符, 以便所释放的描述符能够被后续的 open, pipe, 以及 dup 等系统调用重新使用. 新分配的文件描述符总是当前未使用的文件描述符中序号最小的那一个.
  • 函数签名: int close(int fd)
• 由于 exec 仅替换内存映像, 不替换文件表, shell 实现 I/O 重定向的方法是在 fork 和 exec 之间 (即子进程创建但还未开始执行用户所指定的程序时) 对标准输入所关联的文件进行更换, 这样在执行 exec 后新程序虽仍然从标准输入进行读取, 但读取的文件已经从终端变为了所重定向至的文件.
  • 题外话. Unix 的设计哲学就是解耦, 以最少的基础部件组合出最丰富的功能, 有点类似于数学中的公理系统. 如果不将 fork 和 exec 实现为两个独立的系统调用, 而是一个统一的 (例如) 称为 forkexec 的调用, 那么虽然 shell 仍然能够实现 I/O 重定向, 但是它只能要么在调用 forkexec 前将父进程和子进程的标准输入同时改掉 (并在子进程返回后再改回来), 要么将重定向的要求以参数形式传入 forkexec, 要么必须在 shell 的文档中加上这么一句话: "所有要写给 shell 调用的程序都必须自己实现 I/O 重定向", 三个选项一个比一个奇怪.
• 系统调用 open 用于打开一个文件并返回内核为该文件分配的文件描述符. open 接受两个参数, 一个是文件路径, 另一个是文件的打开模式. 所有可用的打开模式均定义在 kernel/fcntl.h (file control) 头文件中. 共有 5 个不同的打开模式, 分别是 O_RDONLY, O_WRONLY, O_RDWR, O_CREATE, 以及 O_TRUNC. 它们的意义分别是 "只读", "只写", "既读又写", "如果文件不存在则创建", 以及 "打开时将文件长度截断为 0".
• 尽管 fork 会复制父进程的文件描述符表给子进程, 底层的文件偏移却是在父进程和子进程之间共享的, 这就为 shell 顺序执行多个程序并顺序输出各个程序的执行结果至同一个文件中提供了设计空间 (例如考虑像 (echo hello; echo world) >output.txt 这样的命令).
• 系统调用 dup 用于复制一个给定的文件描述符, 并返回一个新的文件描述符, 新描述符与原描述符共享同一个底层文件对象 (也因此共享文件的偏移), 这一点类似于 fork, 只不过 fork 是在父进程和子进程之间复制文件描述符. dup 允许 shell 实现类似于 2>&1 这样的重定向, 其原理是关闭文件描述 2 并复制文件描述符 1, 这样文件描述符 2 将自动分配至文件描述符 1 所指向的文件.
  • 函数签名: int dup(int fd)
• 除非使用 fork 和 dup 进行文件描述符的复制, 其他任何方式得到的文件描述符都不共享底层的文件偏移, 即使是像 open 这样的系统调用也不是 (即连续两次调用 open 将打开两个独立的文件描述符).
• 文件描述符最大的作用就是向程序员提供了对文件, 设备 (例如控制台 (console)) 以及管道等等不同的概念的高级抽象.

1.3 Pipes

• 一个管道 (pipe) 是由内核临时创建并维护的一个缓冲区, 并暴露给用户程序两个与之相连的文件描述符, 一个用于从缓冲区中读取, 另一个用于向缓冲区中写入. 由于两个文件描述符与同一个底层缓冲区相关联, 通过写入端向管道中写入数据将使得数据在读取端可见. 管道实际上提供了一种进程间通信的方式.
• 系统调用 pipe 用于创建一个管道, 与管道相连的两个文件描述符将存储于传入的整型数组中 (数组长度一般设为 2, 例如 int p[2]), 并且读描述符总是在前. 由于管道创建时总是伴随着读和写两个描述符, 而父进程或子进程一般只需要读描述符或者写描述符, 因此在使用 fork 创建子进程后, 父进程和子进程应该视情况将不需要的文件描述符关闭, 以避免不必要的文件描述符泄露或程序漏洞.
  • 函数签名: int pipe(int p[])
• 当使用 read 系统调用从管道中读取时, 进程将一直阻塞直到有数据写入管道, 或者所有与管道写端相连的文件描述符全部关闭为止. 在后一种情况下 read 将返回 0, 等价于遇到了 EOF. 正是由于 read 的这一阻塞性质, 子进程更加应该记得关闭无用的写描述符, 否则将因为 read 永远读不到 EOF 而导致程序卡死.
• xv6 shell 实现了管道运算符 |. 对于每个形如 command_a | command_b 的命令, 父进程首先使用 fork 创建子进程, 然后子进程负责调用 pipe 创建一个连接 command_a 和 command_b 的管道, 接着子进程再分别 fork 出它自己的两个子进程, 一个负责执行 command_a, 另一个负责执行 command_b, 两个子进程之间按照期望通过这个管道进行进程间通信. 注意到 command_b 自己本身也可能是一个形如 command_ba | command_bb 的命令, 因此使用这种方法可以很容易地实现多个管道运算符串联的命令语法. 在这种情况下 shell 将创建出一整个进程树, 其中叶结点为实际执行任务的进程, 而每个内部结点都使用一个管道连接左右子树并等待它们返回.
• 相较于直接使用一个临时文件 (temporary file) 结合 I/O 重定向进行不同程序间的流水线作业, 管道的方式体现出了三个优势. 首先管道的底层缓冲区由内核进行管理, 程序执行完毕后将自动由内核清除, 而临时文件则需要程序员手动删除. 其次管道内部可以使用如环形缓冲区等数据结构进行设计, 使得程序员无需考虑数据流的可能大小, 而临时文件则受可用外部存储空间的限制. 最后管道机制允许两个进程并行执行, 而在临时文件的情况下后一个进程必须等到前一个进程的写入结束才能开始读取.

1.4 File system

• xv6 的文件系统提供了数据文件和目录两种类型的文件. 一个数据文件就是一个由字节构成的数组, 一个目录则存储着指向数据文件和其他目录的引用. 所有目录通过它们之间的引用构成一棵目录树, 目录树的根即为根目录 (root), 以单独一个斜杠 / 表示. 一个路径 (path) 形如 /a/b/c, 相邻部分之间的斜杠 / 表示这两个部分的引用关系. 一个路径可以以斜杠 / 开始也可以不以斜杠开始. 以斜杠开始的路径称为绝对路径, 绝对路径从根目录开始解析. 不以斜杠开始的路径称为相对路径, 相对路径从进程的当前目录 (current directory) 开始解析.
• 系统调用 chdir 用于更改进程的当前目录. chdir 接受一个字符串参数, 表示要切换至的目标目录, 并且区分绝对路径与相对路径.
  • 函数签名: int chdir(char *dir)
• 系统调用 mkdir 用于创建新目录. mkdir 接受一个字符串参数, 表示要创建的新目录的名称.
  • 函数签名: int mkdir(char *dir)
• 系统调用 mknod 用于创建新的设备文件. mknod 接受三个参数, 第一个是要打开的设备文件的路径, 第二个是主设备号 (major device number), 第三个是副设备号 (minor device number). 尽管文件描述符将设备文件与普通文件的接口统一了起来, 真正要对设备文件执行 read 或 write 系统调用时内核还是会将调用交给设备专有的实现, 而不是交给文件系统.
  • 函数签名: int mknod(char *file, int, int)
• 一个目录文件中存储着多个条目, 这些条目称为链接 (link). 每个链接又由一个代表文件名称的字符串和一个指向所谓的 "索引结点" (inode) 的引用构成. 一个索引结点包含着其所代表的文件的元数据 (metadata), 例如文件类型, 文件大小, 文件在硬盘上的具体位置, 以及指向该文件的所有链接的具体数量等等. 因此链接与索引结点之间是多对一的映射关系, 而索引结点与实际文件之间则是一对一的映射关系.
  • 需要注意的是文件描述符与链接之间没有映射关系. 内核通过链接获取文件在磁盘上的实际位置并为其在当前进程中打开一个文件对象, 然后将一个文件描述符分配给该文件对象. 一个文件对象存储着的信息包括文件当前的读取或写入偏移等. 内核为每个进程维护一个私有的打开文件表, 打开文件表中存储着该进程当前打开的所有文件对象, 文件描述符充当的是打开文件表的下标的角色, 负责索引其中的文件对象. 因此文件描述符与文件对象之间是一对一的关系, 而文件对象与索引结点, 进而与实际文件之间则是多对一的关系 (这也是连续执行 open 系统调用打开同一个文件得到的文件描述符能够拥有各自独立的偏移的原因).

• 系统调用 fstat 用于通过文件描述符获取对应文件的索引结点中存储着的元数据. fstat 接受一个 struct stat 结构的指针类型的参数, 并将元数据填入该指针指向的变量中. struct stat 类型的定义可以在头文件 kernel/stat.h 中找到, 其成员包括文件所在的硬盘设备号, 文件的索引结点号 (inode number), 文件的类型, 指向该文件的链接的数量, 以及文件的大小.
  • 函数签名: int fstat(int fd, struct stat *st)
• 系统调用 link 用于为一个索引结点创建新的链接. link 接受两个字符串参数, 一个是已存在的文件的名称, 另一个是要创建的新链接的名称. link 以目录-链接-索引结点的形式运作, 与文件描述符和打开文件表无关.
  • 函数签名: int link(char *file1, char *file2)
• 系统调用 unlink 用于删除一个现有链接. unlink 接受一个字符串参数, 表示要删除的链接的名称. 一个文件的索引结点和该文件在硬盘上的所占的物理空间被释放当且仅当所有链接和文件描述符均被删除或释放. 由于这一点, 如果一个进程创建了一个临时文件, 保存了该文件的唯一文件描述符并删除了该文件的唯一链接, 只要进程退出或是显式释放了唯一文件描述符, 那么该文件将会被自动删除. 这也是创建临时文件的一种惯用方法.
  • 函数签名: int unlink(char *file)
• Unix 将对文件系统的操作实现为一组能够通过 shell 运行的用户级程序, 如 mkdir, ln, 以及 rm 等等. 与之相对地, 与 Unix 同时期的操作系统则一般将这些功能实现为它们的 shell 的内置命令 (并进一步将 shell 内置于 kernel 中). 唯一的例外是 cd, 因为 cd 需要修改 shell 自身的工作目录, 而 shell 一般是通过创建子进程来执行程序的, 如果在子进程中执行 cd 则修改的是子进程自己的工作目录, 并不能影响 shell 自身, 因此 Unix shell 必须将 cd 实现为它的一个内置命令.

1.5 Real world

• Unix 系统接口的模块化的设计哲学为编写通用目的可重用程序带来了极大的便利, Unix shell 也因此成为首个所谓的脚本语言 (scripting language).
• Unix 系统接口已标准化为符合 POSIX (Portable Operating System Interface) 标准. 需要注意的是 xv6 并不是 POSIX 兼容 (POSIX compliant) 的, 因为 xv6 并未实现全部的系统调用, 并且已实现的系统调用也并不完全符合标准. 现代内核提供了许多 xv6 没有的内核服务, 例如网络通讯, 窗口系统, 用户级线程, 以及丰富的设备驱动等等.
• 不同于 Unix 下使用文件描述符对文件系统进行抽象的做法, Unix 的前身 Multics 将文件系统抽象成类似内存的形式, 提供了另一组风格不同的接口. Multics 的复杂性正是催生 Unix 的因素之一.
• Unix 还提供了用户权限机制, 例如 root 用户和普通用户等等. 而 xv6 则没有实现这一机制, 换句话说所有进程在 xv6 下均以 root 用户权限运行.
• 任何操作系统都绕不开在底层硬件上复用多个进程, 在不同进程间进行隔离, 以及提供受控的进程间通信机制等方面的考虑. 之后会看到 xv6 背后的设计思想将同样出现在其他更加高级, 更加复杂的操作系统中.

Remaining system calls

• 系统调用 kill 用于停止指定 PID 代表的进程.
  • 函数签名: int kill(int pid)
• 系统调用 getpid 用于获取当前进程的 PID.
  • 函数签名: int getpid()
• 系统调用 sleep 用于阻塞当前进程, 直至经过指定的时钟 (clock tick) 数.
  • 函数签名: int sleep(int n)
• 系统调用 stat 用于通过文件路径获取对应文件的索引结点中存储着的元数据, 其功能类似于系统调用 fstat.
  • 函数签名: int stat(char *file, struct stat *st)