The UNIX Time-Sharing System

Course-Related
,

[OSDI’ 73] The UNIX Time-Sharing System

0. Word Bank

单词 中文释义 单词 中文释义
demountable 可卸下的 compatible 可兼容的
asynchronous 异步的 allotment 份额
baud 波特（专） miscellaneous 五花八门的
preponderance 数量众多 reentrant 可自进入的
demarcated 被区分 general-purpose 多用途的
overhead 延迟 bootstrap 创造
mesh 网格 antagonistic 敌对的

1. Abstract/Introduction

UNIX 是一个多用途/多用户/可交互的操作系统。它有很多优秀且独特的特点：

  • 一个有级别的文件系统，其中有可拆卸的部分 (mount)
  • 可兼容文件/设备/进程间I/O(pipe)
  • 可启动异步进程
  • 用户可通过命令行来操作系统
  • 用很多子系统、十几种语言（例如一个 C 编译器、文本编辑、汇编器……）
  • 非常便携

UNIX 在当时的时代最主要的成就是在性能优异、功能丰富的同时减少了开销。不仅于此，UNIX系统也非常优雅、简洁。于是我们可以开始看接下来的内容了。

2. Hardware and Software Environment

这里直接引用 @王浩然 的 slides，我觉得已经说的很精确了。

  • 最早的版本运行在 Digital 公司的 PDP-7 和 PDP-9 计算机上。论文讨论的是 PDP-11 / 40和 PDP-45 系统，运行的 UNIX 更成熟。
  • PDP-11/45 有 16 位字长 (16bit)，具有 144kb 的核心内存。实际运行 UNIX 最小只需要 50kb 字节的内核。
  • 1973 年以后，UNIX 用 C 语言重写了一遍，更易于理解与修改，包括了许多函数的改进。（因为已经有比较好

3. The File System

文件主要分为三种，正常磁盘文件，目录和特殊文件。注意，特殊文件实际上就是 I/O 设备等，这样的抽象能方便兼容性，也能统一管理。

3.1 普通文件

普通文件中，信息按照顺序地被存储，最后有结束标志。而二进制文件则是其它存储信息的方式，这些信息可能在开机时被读入主存。

例如，如果我要存储 $3.1415927$，在文本文件中就需要存储这 9 个字符，需要 9 个 $\text{ASCII}$ 值，而二进制文件只需要 4 个字节（$DB\ 0F\ 49\ 40$）。

3.2 目录和文件结构

目录给文件系统提供了结构。它也可以被看作一个普通文件，有权限的人才能进入之或在其中进行修改（相当于读写文件）。

UNIX 文件系统的根是 root 目录，另外也会把一些指令以文件的形式存在系统目录中。

文件有同一的命名标准，也有 cd 的方式（包括 ./.. 这类），这些不再赘述。

值得注意的是 UNIX 中的 linking 特性：同一个文件可以在不同目录下以不同文件名存在。本质而言，这是因为 UNIX

关于文件结构，我们选择严格遵循有根树结构。这样可以简化目录遍历，维护层级一致性，简化管理。更重要的是，如果允许目录间链接，可能会出现循环和孤立的目录，导致资源管理和垃圾回收的问题。

3.3 特殊文件

这是 UNIX 文件系统最特殊的功能。本质而言，每个 I/O 设备都与至少一个这样的文件想管来奶。特殊文件有这样一些一些性质：

  • 特殊文件的读取和写入从接口上而言和普通文件一致，但会激活关联设备
  • 条目位于 /dev 中

这种设备->文件的抽象有三重优势：可以调用文件读写来进行 I/O/文件名和设备名名称语法和含义相同，因而方便传参/保护机制相同

3.4 可移除的文件系统

事实上，我们并不需要整个文件系统都储存在这台设备上，文件当然可以被存在 DVD 等被插入的设备上。mount 指令可以帮我们解决：

这样，我们就能把 mount 到的 ordinary file 重定向到新文件系统的根目录，即把原文件树的叶结点换成了一个新树。之后就可以直接通过挂载的目录来修改原可移动卷 (removable volume) 上的文件。唯一要注意的是两个不同的文件系统之间不能有链接。如果允许，在卸下可移动卷的时候，需要解除所有的链接，这是很繁琐的。

3.5 保护

对于每个文件来说，有创建用户/组内其他用户/其他用户三类用户。当用户创建文件时，将会在其中以自己独特的 UID 进行标记。文件保护码是 10 位，9 位代表该用户/组内其他用户/其他用户的读写执行权限。

第 10 位是 set-user-ID 位，假设只有 A 程序的创建者 him 拥有读写它自己的权限，但它的这一位被设置，用户 me 运行的 B 程序就可以在执行 A 程序的时候进行对它自己的读写。这是因为在执行时，检测到 A 的 set-user-ID bit is on，然后就会在执行时暂时地将 me 的 UID 改为 him，这样就能执行了。这一设计可用于允许用户执行精心编写的调用特权系统条目的命令，并提供特权程序。

整个系统有一个 super-user，它可以进行所有的操作。

3.6 I/O 调用

我们主要有如下 I/O 操作（用 C 语言描述）：

1
2
3
4
filep = open(name, flag);
n = read(filep, buffer, count);
n = write(filep, buffer, count);
location = lseek(filep, offset, base);

name 代表文件名，flag 代表我们要进行的操作（读/写/都有），filep 代表 **文件描述符(file descriptor)**，是一个用来表征文件的整数，可以通过该参数来表示操作哪个文件。count 代表想要读写的字节数，如果读到末尾了返回值就小于 count，否则就会返回 count（除非有错误）。write 是覆盖式的，且在末尾写的时候会让文件变大。而 lseek 顾名思义，是把 filep 的指针移动，其中 offset 可能为负。当然，对于一个打印机，你进行 lseek 操作是无意义的。

关于 I/O 还有一些操作，诸如关闭文件/获取文件状态/改变保护形式/改变所有者……

关于锁，UNIX 系统认为用户不需要管一致性，因为管了也没用。

非必要性：不会有大的单文件被多进程维护的情形。

非充分性：在两个用户同时在编辑文件的时候，文本编辑器本质上是创造了文件的两个拷贝，所以加了锁也没用。

4. Implementation of the File System

提到目录内维护的是指向文件的指针 i-number。访问文件时，i-number 作索引找到 i-node，i-node 由若干描述组成，比如所有者、保护位、文件内容的物理磁盘地址或磁带地址、被引用的次数、指示文件是否为目录、特殊文件、“大”还是“小”。这个表被存在一个系统已知的地方。

当创造文件的时候，就会分配一个 i-node 给该文件，并在目录中维护 name -> i-number 的新表项。link 的时候就相当于增加该表表项，并复制源文件的 i-number，并增加 i-node 的 link-count（这样决定啥时候释放 i-node 的空间）。

关于磁盘上的空间分配：我们把磁盘分成 512b 的一些块。每个 in-node 对应的地址空间里含有 13 份地址。对普通文件，前 10 份是指向前 10 个块。如果数据比 10 块大，第 11 份便指向一个中继块，其中有 128 个额外块的地址。第 12、13 位依此类推，最多可存 $512\cdot (10 + 128 + 128^2 + 128^3)$ bytes。

特殊文件的 i-node：最后 12 个设备地址不重要，仅解释为两个字节，分别指定设备类型和子设备号，这两个字节合称为设备名。

mount 的实现：当要挂载时，mount 指令维护一个系统表，为一个普通文件 i-number+设备名到特殊文件设备名的映射。
比如根目录中有 ABC 三个文件，分别挂载了三个可移动磁盘，现在访问 /B/123，则在匹配 B 的时候在系统表里面查找到映射，i-number 被替换成 1（这是所有文件系统上根目录的 i-number），设备名被替换成映射对应的值，即特殊文件设备名。

关于 I/O 的实现：尽管对于用户而言是可以立刻进行的，但实际上并不是，我们会维护一个缓冲区。写的时候先查看缓冲区，如果在其中就进行标记，而真正的 I/O 操作会延迟。

另外，当认为程序在进行顺序读写的时候，会异步地提前读取下一个块，这样可以大大地减少运行时间，而增加少许开销。

5. Processes and Images

映像 (image) 是指计算机的运行环境，包括内存映像、寄存器值、开关文件信息、目前环境等。对于每个进程来说，这就是它全部的信息。

进程 (process) 是一个映像的执行。当它被执行时，映像必须在主存中，除非有一个活跃的/高优先级的进程迫使其回到磁盘。

进程映像的内存部分分为三段：第一是正文段（如程序代码），这个是写保护的，根，它可以在备份间共享；第二是数据段，它是可写的，在最下面，向上增长；第三是堆栈段，它会随着栈指针的移动向下增长。

5.1 进程

除了第一个系统启动的进程，剩下的只需要用 fork 来产生。

1
processid = fork();

每个进程有自己独特的 processid，然后一开始拥有相同的内存映像、打开文件……两者的不同在于，在父进程中，processid 不为 0，子进程的 pid，而在子进程中，该值为 0。

5.2 管道

管道是 UNIX 中的一个很棒的设计。调用管道通过：

1
filep = pipe();

这时候就可以用 filep 来调用管道。管道的一个特性是，你在其中的每个读都会等到另一个使用管道的进程写完之后操作。

在我看来，它的精彩在于结合了进程间通信和文件读写，而不需要共享内存映像啥的，并且在使用上也只需要用 |。

5.3 程序的执行

使用 execute(file, arg1, ..., argn)，我们能把 file 中的代码和数据全部替换，使这个新进程做我们想做的事。然而，打开文件，环境，进程间关系无法改变，因而这些一般需要在 fork/execute 之间做。

5.4 进程间同步

有的时候，父进程需要等子进程退出。这可能是因为要避免“僵尸进程”，也有可能是为了时序。总之有这样两种指令：

1
2
pid_t p = wait(int *stat_loc);
pid_t q = waitpid(pid_t pid, int* stat_loc, int options);

前者会阻塞进程直到某个子进程结束，并返回其 pid，将返回状态存入 stat_loc。后者可以等待特定子进程结束，当 pid 为 -1 时则等待任意一个。同时，如果 options = WNOHANG，则这个过程是非阻塞的。另外，如果子进程不存在或意外终止，则返回 0。我们可以这样等待所有子进程结束：

1
2
3
4
5
6
7
8
9
#include "unp.h"

int main() {
  pid_t pid;
  int stat, i = 0;
  while ((pid = waitpid(-1, &stat, WHOHANG)) > 0) {
    printf("i = %d\tchild %d termininated\n", ++i, pid);
  }
}

6. Shell

基本的功能不再赘述，我们可以看看 shell 是如何实现的。

我们可以基本构想它是如何运作的：首先我们运行一个进程来等用户输入一行指令，一旦这样，我们解析指令并进行 fork。子进程再根据参数进行 execute，最后父进程等待子进程退出，并输出结果，等待键盘的新输入。

当然，如果指令后有 &，shell 会用一个线程来在后台运行这条指令，同时直接等输入。

关于重定向流，这是在 fork/execute 之间进行的。我们看到 >/< 的时候会会把所有到 stdin/stdout（即描述符 0/1） 的内容重定向到给定文件的描述符。

对于 sh < file，就相当于 fork 自己并以 file 作为输入。

7. UNIX 的思想和意义

The basic idea of the Unix philosophy is to build simple, clear, concise, modular code that is easy to extend and maintain.

  • 简洁，mount/link 的抽象都是为了在形式上更加统一，也更加方便管理
  • 交互式的 shell 让交互式系统有了比非交互式系统更多的功能
  • 在设计上从小的功能入手，可以减轻读代码的压力，并方便 debug
  • 从单一的功能入手，便于代码复用
  • ……

8. reference

  1. the-UNIX-philosophy