第四部分 存储管理 文件系统
第十章 文件系统
这部分主要是一些较高层的策略问题，主要是面向上层开发人员，而不涉及太多具体实现。
1. 文件操作
1.1 基本操作集合
文件为抽象数据类型。操作系统提供 6 个系统调用构成操作文件的最小集合，包括
- 创建 create，首先在文件系统中为文件找到空间，其次，在目录中创建新文件的条目
- 写入 write，指定文件名称和要写入文件的信息，系统根据文件名称搜索目录已查找文件位置。系统应维护写指针，用于指向需要进行下次写操作的文件位置。写的时候同时更新写指针。
- 读取 read，指明文件名称和文件的内容应读到哪里。系统根据文件名称定位文件内容，同时需要维护一个读指针，指向要进行下一次读取操作的文件位置。同样，读操作需要同时更新读指针。
读写操作可以使用相同的指针。称为 当前文件位置指针。这个指针的初始化受文件访问模式影响，APPEND 会置于末尾，否则是文件头。
- 重新定位 seek，移动当前文件位置指针到指定位置，不涉及实际 I/O 操作。
- 删除 delete， 搜索给定文件名，找到对应的目录条目，释放占用的文件空间，并删除对应条目。
- 截断 truncate 文件。用户可能想删除文件的内容，但保留它的属性。实际上就是只改动文件长度属性。
1.2 打开文件表
以上操作大多涉及搜索目录，得到文件的相关条目，为了避免这种搜索，OS 一般要求访问文件前需要先 open()。OS 有个打开文件表，维护所有打开文件的信息。如果不用了再 close()。create/delete 操作的是未 open() 的。
open() 函数返回一个文件句柄 (Windows) 或者称为文件描述符 (UNIX-like)，后续操作都以这个值作为指针，避免重复搜索。同时，open() 一般也支持访问模式信息，如 CREATE, APPEND 等。OS 会根据文件系统的权限子系统检查 open() 是否合法。
文件系统的设计哲学显然是一种 “有状态” 通信。有状态和无状态的区别主要是是否单次操作需要携带所有必要信息。如果是无状态，那么每次都要指定文件名、访问模式、当前文件指针等等，NFS 就是这么设计的；有状态就得把状态维护起来，放在一个数据结构里，每次操作只需要携带一个指针以让系统知道操作的是哪个项。这两种设计哲学广泛分布于计算机领域，如 TCP 和 UDP，TCP 有状态，每条链接的状态信息由 OS 维护，而 UDP 每次读写数据互不干扰，OS 并没有 UDP 的状态信息（可能需要维护其它信息，如端口信息）
通常，OS 采用两级内部表：单独进程表 和 系统总表。
- 单独进程表跟踪进程打开的所有文件，存储了当前文件位置指针、权限、访问模式等信息。
- 系统表包含与进程无关的信息，如文件在磁盘上的位置，mtime/ctime/atime，文件大小等。一旦进程打开了一个文件就会产生一个条目，如后续再有进程 open()，只需要在打开计数上加 1 即可。每次 close() 会减 1，OS 会回收计数为 0 的条目。所以 open() 后的文件不用了一定要 close()。
1.3 同步
OS 可以提供强制 (Windows) 或建议(UNIX-like) 的文件锁定机制。强制锁会要求文件操作的所有 API 都检查锁，也即一个进程加了锁，OS 会确保其它进程调用 open() 这类函数的时候会被阻塞。这是一个内核级别的实现。而建议锁是指，一个进程加了锁，其它进程需要主动去检查这个锁的状态，再决定是否操作文件。Linux 文件锁 的实现可以参考这篇文章。
Java 实现文件互斥访问时通过要访问文件的 FileChannel 的 lock() 取得 FileLock 来做得。FileLock 支持共享和非共享，同时支持字节级别的锁定。
public abstract FileLock lock(long position, long size, boolean shared)
throws IOException;
2. 文件类型与结构
实现文件类型的常见技术是将类型作为文件名的一部分，即放在扩展名里。UNIX 系统采用位于某些文件开始部分的魔数（magic number）大致表明文件类型，但不是所有文件都有魔数。Linux 的可执行文件是依赖于其执行权限而不是拓展名。所以综上，文件类型的区分方法千奇百怪。
文件类型决定文件结构。OS 必须支持至少一种结构，即可执行文件的结构，以便系统能加载和运行程序。但是，OS 一般也不应该规定太多文件结构，谁支持谁就得负责，这个让 OS 来做 OS 就很亏。
Linux 大致有这些文件类型：普通文件、目录、字符设备、块设备、套接字、符号链接
3. 访问方法
- 顺序访问
文件信息按顺序加以处理，编辑器和编译器通常以这种方式访问文件。适合磁带 - 直接访问
文件由固定长度的逻辑记录组成，以允许程序按任意顺序进行随机访问。数据库通常是这种类型的。直接访问可以由顺序访问进行模拟，但是效率低下。适合磁盘等。 - 其它访问方法
其它访问方法通常建立在直接访问之上，并涉及建立文件索引。现代通用 OS 都是这种。
4. 目录与磁盘的结构
文件系统底层是磁盘，向上提供前面提到的 API，那么必须维护目录来组织这些文件。
4.1 一些概念
- 磁盘 磁盘是一块单独的物理设备
- 分区 磁盘格式化后才能使用，格式化实际上就是对磁盘进行分区，分为不同的部分，每个部分有些元数据表明物理存储的一些信息，也就是文件系统的元数据。按传统分区技术，分区一般分为主分区和扩展分区；分区表格式有主引导分区（Master Boot Record, MBR，已逐渐淘汰) 和 GPT（GUID Partition Table) 分区。比如 Windows 的 C 盘、D 盘就是分完区后的结果。详见鸟哥的 Linux 私房菜磁盘部分
- 文件系统 文件系统和分区不是一个概念，分区一般说的是物理存储设备，文件系统是描述存储设备的内容格式。
- LVM Logical Volume Manager Linux 下的逻辑卷管理器，向上屏蔽掉底层物理磁盘的细节。实际上就是让 OS 能操作多块磁盘以及支持扩容、缩容等操作。传统分区有很多限制。
LVM
PV(Physical Volume)：物理卷，处于LVM最底层，可以是物理硬盘或者分区。
PE(Physical Extend)：物理区域，PV中可以用于分配的最小存储单元，可以在创建PV的时候制定（默认为4MB），如1M, 2M, 4M, 8M, 32M, 64M…组成同一VG中所有PV的PE大小应该相同。
VG(Volume Group)：卷组，建立在PV之上，可以含有一个到多个PV。
LV(Logical Volume)：逻辑卷，建立在VG之上，相当于原来分区的概念。不过大小可以动态改变。
- VFS Linux 支持多种文件系统，为了屏蔽底层细节，VFS 扮演了中间层的角色
4.2 目录
目录（directory）可以理解为一个字典，记录的是文件名到磁盘存储位置的映射。目录可以分为单级目录、两级目录、树形目录（主流目录结构）、无环图目录（为了共享子目录）。
UNIX-Like 既支持基于软链接的共享，这个时候文件系统并不把软连解当作实际节点，删了之后也依然保留，需要程序员自己意识到被删了；也支持基于硬链接的共享，后者修改了 inode 的内容，会由文件系统管理节点。详见相关博客。
4.3 文件系统挂载
文件系统在使用前得先挂在到某个目录，挂载位置称为挂载点，被挂载的称为设备。比如, Linux 中，/home 一般是个单独的分区，内核会在启动的时候将其挂载到根目录下的 /home 处。然后我们才可以通过 /home/test.c 直接访问 test.c 文件。
Linux 默认只有一个分区，即 /，这个分区上运行着发行版默认的文件系统。这个 / 里面可以装文件，也可以挂载其它文件系统。这里首先得认识到 OS 目录树和文件系统不是一个概念。你可以在 /test1 挂载一个 ext3 文件系统，可以在 /test2 挂载一个 xfs 文件系统，可以在 /test3 放一个普通文件。挂载可以看作根目录的某个节点被另外一颗树替代。Windows 会在启动时自动安装所有文件系统（卷 C, D...)，如果我们插入 U 盘，Windows 会识别并把 U 盘挂载到目录树上，只不过这个目录树是两级的。Linux 的挂载点一般可以是任何位置，Windows 的新版本似乎也可以，但不清楚。
4.4 保护
UNIX-like 文件系统的一般权限 和 SUID, SGID, SBIT等
第十一章 文件系统实现
1. 文件系统的结构
文件系统一般分层实现，从上往下：
- 逻辑文件系统。管理元数据信息，包括文件系统的所有结构，但不包括实际数据。通过文件控制块（File Control Block, FCB) 包含文件的信息，如权限、位置等
- 文件组织模块。负责映射文件的逻辑块到物理块地址。每个文件的逻辑块是连续编号的，但是物理块不是。
- 基本文件系统。负责向设备驱动程序发送命令，读写物理块，维护缓存等。
- I/O 控制。负责底层硬件通信
内存和磁盘之间的 I/O 以块 (block) 为单位，块的大小与磁盘扇区大小无关。同时，上述模块在实际实现中可能揉在一起。
2. 文件系统的实现
2.1 元数据
首先考虑一下文件系统需要维护哪些信息。分别从磁盘上和内存中来考虑（下述不区分卷和分区的概念，因为卷实际上就是个逻辑分区）:
2.1.1 磁盘上
- 每个分区的引导控制块 (boot control block)。如果分区不包含 OS，则这块为空，也即一个 OS 有多个分区。它通常为卷的第一块，有自己的格式。因为在引导式系统没有加载文件系统代码，不能解释文件系统的格式。每个分区都可以有引导控制块，这是多重引导，即多系统的基础。个人感觉这部分不属于文件系统的一部分。
BIOS/UEFI 是启动检测程序。他们运行后，会去读 MBR/GPT 分区，然后 MBR/GPT 分区可以直接加载内核文件来启动 OS，也可以将控制流转到其它引导控制块。
- 分区控制块。存储了分区内的详细信息，如分区内的块的数量、大小、空闲块和指针、空闲的 FCB 数量和指针等。也即 UNIX-like 中的超级块 (superblock)
- 目录结构。在 Linux 中，包括文件名和 inode 号码。
- 每个文件的 FCB 包括该文件的许多详细信息。也即 Linux 中的 inode。
2.1.2 内存中
- 挂载表。包含设备的挂载信息，条目包括一个指向该设备的文件系统超级块的指针。
- 目录结构缓存。
- 系统打开文件表。
- 进程打开文件表。
- 缓冲区。保存文件系统的块。
2.2 操作函数
2.2.1 创建文件/文件夹
创建文件时，应用程序调用逻辑文件系统，由其分配一个新的 FCB。如果文件系统的实现在文件系统创建时（格式化的时候）已经创建了所有 FCB，如 ext 文件系统，则可从空闲的 FCB 集合中分配一个可用的 FCB。然后逻辑文件系统用文件名和新的 FCB 去更新其对应的目录文件，并写回磁盘，这个过程会调用下面的文件组织模块。
UNIX 不区分文件和文件目录的处理，而 Windows 提供两套系统调用。
2.2.2 打开文件
文件使用前需要先打开。open() 首先需要搜索系统打开文件表查询是否已经打开，如是，直接在进程打开文件表中新建条目并指向系统打开表中的条目，同时更新计数；否则，需要搜索文件所在目录，这个通常缓存在内存中，找到文件后，将其 FCB 复制到系统打开文件表，并在进程打开文件表中重复前面相同的动作。
进程打开文件表中的条目一般包含一个指针指向系统表，所有文件操作通过这个指针进行，所以文件表不需要包含文件名，因为可以通过指针访问 FCB。这个在 UNIX 中称为 文件描述符（file descriptor)，在 Windows 中称为 文件句柄 (file handle)。
2.2.3 读写文件
读文件需要指定文件描述符，然后内核访问进程的打开文件表，获取系统打开文件表的索引，再根据系统文件表中存储的 FCB（可能在内存中也可能是一个指向磁盘的指针），然后获取文件的元数据，包括数据存储位置、当前位置指针等。然后向下发送读取指令，最后由 I/O 设备完成读取。读到的内容放入指定的缓冲中。
写文件类似，只不过一般都是写缓冲，落盘的策略一般由文件系统自行安排或者应用程序手动调用 fsync。
2.2.4 关闭文件
关闭文件需要删除进程打开文件表中的条目，并递减系统打开文件表中的计数。当所有打开该文件的用户关闭它时，任何更新的元数据落盘，并且删除系统表中的条目。
2.3 分区与挂载
分区并不一定得有文件系统，没有格式化的分区也可以使用，称为裸盘，原始磁盘 (raw disk)。例如，UNIX 的交换空间就是使用的裸盘，数据库也经常使用。
根分区，包括 OS 内核和其它系统文件在启动时挂载。其它卷可以在引导时自动挂载或在启动后手动挂载，取决于 OS。
挂载的实现一般时标记某个 FCB 为挂载点，同时在其里写入安装表中条目的指针，即完成挂载。
2.4 虚拟文件系统
VFS 实际上就是 OOP 技术的一种体现，通过中间层来屏蔽底层多种实现。
3. 目录实现
- 线性表。主要是复杂度偏高
- 哈希表。主要是扩容，可能需要借助一致性哈希算法
- 平衡树。
4. 分配方法
4.1 连续分配
连续分配的好处是，简单，支持顺序访问和直接访问，对于磁盘结构，读取效率高。缺点是，本质上是一个动态存储分配问题，也就存在这类型问题的所有问题，如外部碎片，如何快速找到一个最好的可用分配，文件增大怎么做。
外部碎片可以通过复制-整理算法来做，这个技术在垃圾回收算法中常用。存在 STW 问题，而且需要额外存储空间来做整理。文件增大一般通过扩展来解决，即一开始先分配一块，如果增大，再分配一块，第一块链接到后一块上。
4.2 链接分配
链接分配解决了上述所有问题，但是不能有效支持文件的随机访问。顺序访问的情况下，与索引分配一样，对于磁盘结构，可能效率低下，因为要不停旋转磁盘头。同时，因为链接指针需要空间，所以有效存储率变低了。
链接分配的一个重要变种就是文件分配表（File Allocation Table, FAT)，广泛用于 MS-DOS。每个卷的开头部分的磁盘存储一张表，表里存储了卷上的所有块的指针，从而解决随机访问的问题。
4.3 索引分配
索引分配将所有指针放在一起形成索引块，解决随机访问的问题。每个 FCB 里存储了各自的索引块。
UNIX 文件系统使用一种组合策略来优化索引的存储，inode 的前12 个指针是直接索引，直接指向文件的数据块的地址；接下来的 3 个指针指向间接块，分别是一级间接块、二级间接块、三级间接块，对应二级、三级、四级索引。
5. 空闲空间管理
为了跟踪空闲磁盘空间，需要维护一个空闲空间列表。创建和删除文件块都需要修改这个空闲空间列表。一般通过位图来实现，例如 UNIX；也可以通过链表等。
后面还包括对效率、性能、恢复、一致性、NFS 的讨论，这里不再总结。
