持久化

本章开始学习操作系统中的持久化概念，将数据“永久”保存到真实世界中，而不会像存储在内存那样一旦断电数据就永久丢失了。

磁盘系统¶

本部分我们学习设备中的磁盘模块。一般而言，设备就是 I/O 设备，即输入输出设备/外设。可以根据数据的传输方向将 I/O 设备分为三大类：输入设备（键盘、鼠标、扫描仪）、输出设备（显示器、打印机）和输入输出设备（磁盘、网卡）。设备管理的概念已在计算机组成原理中详细介绍，这里不再赘述。


磁盘（立体图）	磁盘（截面图）

如上两图所示，一个磁盘设备主要由三部分组成：柱面、磁头和扇区。其中磁头可以平移，柱面可以旋转，每次都是通过两者的协同让磁头可以正确的读取到扇区的数据。

地址转换¶

逻辑块号和物理块号有一个简单的映射关系，一般按照柱面、磁头和扇区顺序编号。对于柱面、磁头和扇区都从 \(0\) 开始编号的情况，假设一个磁盘中有 \(m\) 个磁头，每个磁头有 \(k\) 个扇区，逻辑块号 \(x\) 对应的柱面号为 \(a\)，磁头号为 \(b\)，扇区号为 \(c\)，则有以下转换公式：

\[ \begin{aligned} x &= m \times k \times a + k \times b + c\\ a &= \frac{x}{m \times k}\\ b &= \frac{x \% (m\times k)}{k} \\ c &= x \% (m\times k) \% k \\ \end{aligned} \]

如果有不是从 \(0\) 开始编号的，就用换元法将上述对应的变量替换掉即可，例如假设磁头和扇区都从 \(1\) 开始编号，那么就将 \(c'=c-1,x'=x-1\) 代入上式即可。

移臂调度¶

通过移动臂的平移，读出合适的柱面信息，为了降低移动臂的移动时间开销，面对大量 I/O 请求时，需要设计一个合理的移动算法。用一个例子来说明就再清晰不过了，假设当前移动臂所在柱面为 53 号，柱面的取值范围为 0-199，现在有一个柱面请求序列为 98, 183, 37, 122, 14, 124, 65, 67，五种调度算法如下所示：

5 种移臂调度算法示例

旋转调度¶

对于同一个柱面，我们希望在尽可能少的旋转圈数内完成所有请求扇区的读写，有两种策略：

循环排序。即优化扇区请求序列的顺序，这个可以从软件上实现；
优化分布。即优化扇区的数据分布，这需要从硬件上实现，即需要根据磁盘转速和数据处理速度两者联合定夺扇区的数据分布。

给优化分布举个例子。假设旋转一周时间为 20ms，读出每个扇区后的处理时间为 4ms，则右边的优化分布能提高信息处理速度：

优化分布实例

文件系统¶

知道了数据在物理设备上的读写方式，接下来讲讲逻辑数据与物理设备的交互方式，也就是文件系统的事。

文件的定义¶

在类 Unix 操作系统中，文件由「索引结点」和「文件数据」两部分组成。具体地：

索引结点 inode 用来存储「文件的元数据」和「文件的数据所在物理存储块指针」。可以简单理解为如下数据结构：

C

// 直接索引块数目
#define CNT 12

// 定义文件系统的块
typedef char block_t[4096];

// 定义文件元数据的结构
typedef struct {
    uint32_t mode;   // 文件权限
    uint32_t size;   // 文件大小
    uint32_t uid;    // 文件拥有者
    uint32_t atime;  // 最后访问时间
    uint32_t mtime;  // 最后修改时间
} finfo_t;

// 定义索引结点的结构
struct inode {
    finfo_t file_info;         // 文件元数据
    block_t* direct[CNT];      // 直接索引（最多 CNT 个）
    block_t* single_indirect;  // 一次间接索引
    block_t* double_indirect;  // 二次间接索引
    block_t* triple_indirect;  // 三次间接索引
};

文件数据 data 就是文件的原始信息。其中的索引都是指向具体物理存储块的指针：

对于直接索引。其指向的物理存储块存储的就是文件数据；
对于间接索引。其指向的物理存储块存储的都是指针，只不过其中存储的不是文件信息，而是「索引指针」，而由于一个物理块的存储空间对应存储的指针个数远大于一个结点中存储的直接指针个数，因此可以通过间接索引的方式极大的提升文件的存储空间。

因此文件系统管理文件的方式，就可以通过管理每一个文件的 inode 来实现。更一般地，inode 就是文件控制块 (File Control Block, FCB) 的具体实现。可以发现操作系统中的文件管理系统对于文件的管理并非针对一整个文件，而是将每一个文件抽象为一个 FCB，并基于此进行管理。

读到这里可以发现，文件管理的 FCB 和进程管理的 PCB 有着异曲同工之妙，均将独立的对象（文件、进程）抽象「地址」和「数据」两个部分，然后设计相关的软件算法来操作「地址」信息。区别在于，文件是在外存，而进程是在内存。

目录的定义¶

当文件数量较多以后，平铺在一起难免会冗余繁杂，Unix 创始人就设计了树形结构（准确地说是有向无环图，具体见文件共享）的「目录」来管理和组织文件。目录结构允许用户对文件进行分级、分类管理，并且在不同的子目录下，用户可以取相同名称的文件。与此同时，不同的子目录存储的数据可以被划分到不同的硬件存储器中，便于用户从物理意义上对数据进行管理。

与每个文件有一个 inode 一样，每个目录也有一个 inode（目录本质上也是一个文件，即目录文件）。目录中的每一个文件或子目录被称为目录项。从根目录开始，每一个目录的 inode 都存储着其目录项的 inode_id，包括指向自己的（即 . 符号）和指向父目录的（即 .. 符号）。每一个目录中存储的目录项的 inode_id 都意味着一条从目录指向目录项的有向边，由于 . 和 .. 并非用户创建的硬链接，所以目录指向自己的边以及目录之间相互指向的边不被考虑在文件树的边集中。下图展示了不同视角下的目录树信息：

用户角度的目录结构 vs. 系统角度的目录结构

文件共享¶

文件共享是一个概念，其宗旨是：在尽可能减少存储开销的情况下获得更多访问文件的入口。实现上用到的是「文件链接」技术。

在类 Unix 操作系统上，链接的方式有如下两种：

硬链接，即拷贝文件的 inode 而非拷贝文件，使多个指针指向同一块硬盘区域。考虑到一个文件存储开销最大的是数据部分，而数据又被指针索引，所以复制指针是明智的选择。当最后一个 inode 被删除，文件才会真正消失。
软链接，即新建一个文件，保存目标文件/目录的路径（字符串格式），所以也叫符号链接。当目标文件/目录被删除后，所有的软链接都会失效。

Warning

目录无法使用硬链接。对于一棵目录树而言，硬链接就是创建了一条从源到目标的有向边。对于硬链接文件，由于文件在目录树中是叶子结点，所以新增的边会让目录树变为有向无环图，不会破坏拓扑结构。但如果硬链接了一个目录，特别是当目标目录为源结点的祖宗结点时，就产生了一条回路，这违背了类 Unix 系统「目录只有一个父结点」的设计原则，从而让很多基于拓扑结构的算法失效。

下图给出了创建软硬链接后的文件列表：

文件的软硬链接示例

简单分析一下：

创建了一份名为 origin.txt 的原始文件，占用 \(4502\) 个字节，其对应的 inode_id 为 \(1047884\)；
使用「两次硬链接」分别创建了 file_hard.txt 和 file_hard2.txt，可以看到 inode_id 均为 \(1047884\) 并且 inode 的计数变成了 \(3\)；
使用「一次软链接」创建了 file_symbol.txt 文件，其 inode_id 发生了变化（递增为 \(3\) 可以表明当前系统可能是增量使用 inode_id 的，并且此时没有产生额外的文件）。与此同时，其文件内容变成了一个路径指向。

Note

inode_id (inode number) 是文件系统为每个 inode 分配的唯一整数标识符，用来在目录项中引用对应的 inode，从而定位和访问文件/目录的元信息和数据。每个文件/目录在同一文件系统内有唯一的 inode_id。可以使用 ls -i 命令查看目录项的 inode_id 值。

文件加载¶

下面详细介绍在类 Unix 系统中，文件加载的逻辑：

用户或程序向操作系统发送字符串形式的文件路径。例如 '/home/learn/file.txt'；
操作系统会将上述的字符串进行解析并从根目录开始逐层向下匹配文件名（在拥有权限的情况下）；
若匹配失败，则直接报错并终止加载。若匹配成功，则获得对应文件的 inode_id，然后根据 inode_id 在 inode 表中查出对应文件的 inode；
最后操作系统根据 inode 中的索引指针将外存中的数据加载到内存。

至此一个文件就被成功打开了。