跳转至

持久化

设备管理

本章开始学习设备。一般而言，设备就是 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 种移臂调度算法示例

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

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

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

优化分布实例

文件系统

文件定义

索引文件。在类 Unix 操作系统中，文件由「索引结点」和「文件数据」两部分组成。具体的，索引结点 inode 用来存储「文件的元数据」和「文件的数据所在物理存储块指针」，而文件数据就是文件的原始信息。可以简单的理解为如下的结构体：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 直接索引块数目
#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;  // 三次间接索引
};

其中的索引都是指向具体物理存储块的指针：

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

因此文件系统管理文件的方式，就可以通过管理每一个文件的 inode 来实现。更一般的来说，inode 就是文件控制块 (File Control Block, FCB) 的具体实现。可以发现操作系统中的文件管理系统对于文件的管理并非针对一整个文件，而是将每一个文件抽象为一个 FCB，并基于此进行管理。读到这里其实就和前面的进程管理串上了，操作系统中的进程管理也是将进程抽象为 PCB，并基于此进行管理。两者的区别就在于，文件是在外存中，而进程是在内存中，但是管理的方式都是类似的，均采用相关的软件算法来实现。

文件组织

文件目录。大量的文件需要我们进行合理的管理，以树形文件目录为例。为了便于管理，设计者将每一个 inode 进行唯一性编号（记作 inode_id），这样用户打开一个文件其实是发送一个 inode_id 给操作系统，操作系统会根据 inode_id 查询到对应的 inode 并基于此 inode 将对应的文件加载到内存。

所以为什么要把目录设置成树形结构？从开发者角度来说，树形目录没有任何作用，他们只需要关心什么 inode_id，别的都不操心。但是从用户角度来说，树形目录的意义就很大了。具体的，对于用户来说，树形目录可以让我们分级分类管理多而杂的文件，并且在不同的树路径下，我们可以取相同名称的文件。与此同时，不同的子树存储的数据可以被划分到不同的硬件存储器中，这就方便了用户从物理意义上将数据进行迁移。下面展示一个可重名的树形文件目录在不同视角下存储的信息：

用户角度的目录结构 VS 系统角度的目录结构

文件共享。下面介绍两种文件链接以达到共享目的的方式：

  • 硬链接。可以理解为拷贝文件的 inode 而非拷贝文件；
  • 软链接。也可以称为符号链接，可以理解为创建一个新的文件，只不过这个文件存储的是被链接文件的路径。

文件的软硬链接示例

对于上图的示例：

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

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

  1. 发送。用户或程序需要向操作系统发送字符串形式的文件路径。例如 '/home/learn/file.txt'；
  2. 解析。操作系统会将上述的字符串进行解析并从根目录开始向下查找。每一层目录其实就是一个目录文件，目录文件存储了其下所有的目录项以及访问权限，只有当前用户具备访问权限的前提下才能继续访问，查找逻辑就是匹配解析出来的字符串；
  3. 递归。重复 2 中的匹配直到异常终止或者匹配到最终的文件名；
  4. 获取 inode 编号。匹配成功后就可以拿到当前目录文件中对应文件的 inode 编号信息；
  5. 打开文件。操作系统根据第 4 步的 inode 编号加载对应的文件数据到内存中供后续操作。至此一个文件就被成功打开并加载到内存中了。