操作系统从入门到入土④：文件系统
文件是进程创建的信息逻辑单元，每个文件是独立于其他文件的，是对磁盘的建模，而非对 RAM 的建模。
如果能把每个文件看成一个地址空间，那么就能理解文件的本质了。
1. 文件
文件是一种抽象机制，它提供了一种在磁盘上保存信息而且方便以后读取的方法。这种方法可以使用户不必了解存储信息的方法、位置和实际磁盘工作方式等有关细节。
1.1. 文件结构
字节序列：
操作系统所见到的就是字节。把文件看成字节序列为操作系统提供了最大的灵活性。用户程序可以向文件中加入任何内容，并以任何方便的形式命名。
记录序列：
文件是具有固定长度记录的序列，每个记录都有其内部结构。
读操作返回一个记录，而写操作重写或追加一个记录。
树：
按 key 排序，可对特定 key 进行快速查找。
1.2. 文件访问
顺序访问（sequential access）：
进程在这些系统中可从头按顺序读取文件的全部字节或记录，但不能跳过某一些内容。
顺序访问文件是可以返回到起点的，需要时可多次读取该文件。在存储介质是磁带而不是磁盘时，顺序访问文件是很方便的。
随机访问（random access file）：
当用磁盘来存储文件时，可以不按顺序读取文件，或者也可以按照关键字来访问记录。这种能够以任何次序读取其中字节或记录的文件称作随机访问文件。
如订票程序必须能直接访问该航班记录，而不必先读出其他航班的成千上万个记录。有两种方法可以指示从何处开始读取文件。
- 一种是每次 read 操作都给出开始读文件的位置。
- 另种是用一个特殊的 seek 操作设置当前位置，在 seek 操作后，从这个当前位置顺序地开始读文件。
2. 文件系统的实现
主引导记录（Master Boot Record, MBR）：
文件系统存放在磁盘上，划分为多个分区，每个分区中都有独立的文件系统。
磁盘的 0 号扇区称为主引导记录，用来引导计算机。
分区表：
在 MBR 的结尾是分区表。该表给出了每个分区的起始和结束地址。表中的一个分区被标记为活动分区。
引导块（boot block）：
在计算机被引导时，BIOS 读入并执行 MBR。MBR 做的第一件事是确定活动分区，读入它的第一个块，称为引导块，并执行之。引导块中的程序将装载该分区中的操作系统。
为统一起见， 每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统。不过，未来这个分区也许会有一个操作系统的。
超级块（superblock）：
超级块包含文件系统的所有关键参数，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。
超级块中的信息包括：确定文件系统类型用的魔数、文件系统中块的数量等
2.1. 文件的实现
文件存储实现的关键问题是：如何记录文件用到哪些磁盘块。
2.1.1. 连续分配
把每个文件作为一串连续数据块存储在磁盘上。
在块大小为 1KB 的磁盘上，50KB 的文件要分配 50 个连续的块。
在块大小为 2KB 的磁盘上，50KB 的文件要分配 25 个连续的块。
初始状态下，磁盘是空的。接着，从磁盘开始处（块 0）开始写入长度为 4 块的文件 A。紧接着，在文件 A 的结尾开始写入一个 3 块的文件 B。
每个文件都从一个新的块开始，这样如果文件 A 实际上只有 3.5 块，那么其最后一块的结尾会浪费一些空间。
缺点：
随着时间的推移，磁盘会变得零碎。
假设删除 D 和 F，会在磁盘上留下一堆空闲块。磁盘不会填充空闲块，因为会涉及之后的所有文件。
磁盘被充满后，要么压缩磁盘，要么重新使用空洞所在的空闲空间。前者由于代价太高而不可行。后者需要维护一个空洞列表，但是在当创建一个新的文件时，就必须得知道该文件的最终大小，这是不可理喻的。
但这个办法在 CD-ROM 上是可行的并被广泛使用。在 CD-ROM 上所有文件的大小都是已知的，并在后续使用中它们的大小也不会改变。
所以如果文件的大小已知且不会改变，那么连续分配是一种好方法。
2.1.2. 链表分配
每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。
优点：
- 链表分配可以充分利用每个磁盘块。不会因为磁盘碎片而浪费存储空间。
- 在目录项中，只需要存放第一块的磁盘地址，文件的其他块就可以从这个首块地址查找到。
缺点：
- 随机访问相当缓慢。要获得块 n，操作系统每一次都必须从头开始，并且要先读前面的 n - 1 块。
- 由于指针占去了一些字节，每个磁盘块存储数据的字节数不再是 2 的整数次幂。怪异的大小降低了系统的运行效率，因为许多程序都是以长度为 2 的整数次幂来读写磁盘块的。
由于每个块的前几个字节被指向下一个块的指针所占据，所以要读出完整的一个块大小的信息，就需要从两个磁盘块中获得和拼接。
2.1.3. 采用内存中的表进行链表分配
如果取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决使用链表的两个不足。
内存中的这样一个表格称为 文件分配表（File Allocation Table, FAT）。
- 文件 A 依次使用了磁盘块 4、7、2、10、12。
- 文件 B 依次使用了磁盘块 6、3、11、14。
- 这两个链都以一个不属于有效磁盘编号的特殊标记 -1 结束。
因为整个链都存放在内存中，所以不需要任何磁盘引用，随机访问变得也容易了。
缺点：
必须把整个表都存放在内存中。
若磁盘大小为 1TB，块大小为 1KB，那么这张表需要有 10 亿项。每项至少 3 个字节，为了提高查找速度，有时需要 4 个字节。根据系统对空间或时间的优化方案，这张表要占用 3GB 或 2.4GB 内存。
上述方法并不实用，FAT 的管理方式不能较好地扩展并应用于大型磁盘中。
2.1.4. i 节点
给每个文件赋予一个称为 i 节点的数据结构。其中列出了文件属性和文件块的磁盘地址。所以只要有 i 节点，就能找到文件的所有块。
相比于 FAT，i 节点只在对应文件打开时才在内存中。而 FAT 需保留所有磁盘块的关系链表。
当一个文件所含的磁盘块的数目超出了 i 节点所能容纳的数目怎么办？
一个方案是最后一个地址指向另一个用于存储额外地址的块。
2.2. 文件属性的存储位置
每个文件系统维护文件的文件属性，它们必须存储在某个地方。
存至目录项：
一种方法是把文件属性直接存放在目录项中。目录中有一个固定大小的目录项列
表，每个文件对应一项，其中包含一个文件名、一个文件属性的结构体以及用以说明磁盘块位置的一个或多个磁盘地址。
存至 i 节点：
对于采用 i 节点的系统，还存在另一种方法，即把文件属性存放在 i 节点中而不是目录项中。目录项会只有文件名和 i 节点号。
2.3. 目录的实现
打开文件时，操作系统利用路径名找到相应目录项。目录项中提供了查找文件磁盘块所需要的信息。
2.3.1. 实现可变长度的长文件名
简单固定长度：
最简单的方法是给予文件名一个长度限制，典型值为 255 个字符，并为每个文件名保留 255 个字符空间。这种处理很简单，但是浪费了大量的目录空间。
文件名分散在各自文件中：
一种替代方案是每个目录项分为两部分。
- 固定部分：以目录项的长度开始，后面是固定格式的数据，通常包括所有者、创建时间、保护信息以及其他属性。
- 任意长度的实际文件名。
如上图，有三个文件，project budget、personnel 和 foo，每个文件名以一个特殊字符（通常是 0）结束。
缺点：
- 当移走文件后就引入了一个长度可变的空隙，下一个进来的文件不一定正好适合这个空隙。
- 一个目录项可能会分布在多个页面上，在读取文件名时可能发生缺页中断。
文件名集中在一起：
另一种方法是，使目录项自身都有固定长度，而将文件名放置在目录后面的堆中。
优点：
- 当一个文件目录项被移走后，另一个文件的目录项总是可以适合这个空隙。当然，必须要对堆进行管理。而在处理文件名时缺页中断仍旧会发生。
- 文件名不再需要从字的边界开始，每个文件名后面就不需要用于凑整的填充字符了。
2.3.2. 加快文件查找速度
散列表：
对于非常长的目录，线性查找就太慢了。加快查找速度的一个方法是在每个目录中使用散列表。
添加一个文件时，对散列表中对应的表项进行检查。
如果该表项没有被使用，就将一个指向文件目录项的指针放入。
如果该表项被使用了，就构造一个链表，该链表的表头指针存放在该表项中，并链接所有具有相同散列值的文件目录项。
查找文件按照相同的过程进行。散列处理文件名，以便选择一个散列表项。
检查链表头在该位置上的链表的所有表项，查看要找的文件名是否存在。如果名字不在该链上，该文件就不在这个目录中。
使用散列表的优点是查找非常迅速。其缺点是需要复杂的管理。只有在预计系统中的目录经常会有成百上千个文件时，才把散列方案真正作为备用方案考虑。
高速缓存：
另一种加快大型目录查找速度的方法是，将查找结果存入高速缓存。
在开始查找之前，先查看文件名是否在高速缓存中。如果是，该文件可以立即定位。当然，只有在查询目标集中在相对小范围的文件集合的时候，高速缓存的方案才有效果。
2.4. 日志结构文件系统
技术背景：
磁盘高速缓存迅速地增加，这使得来自文件系统高速缓存的大部分读请求不需要磁盘访问操作。
未来多数的磁盘访问是写操作，但是在一些文件系统中使用的提前读机制（需要读取数据之前预取磁盘块），并不能获得更好的性能。
在大多数文件系统中，写操作往往都是零碎的。
一个 50us 的磁盘写操作之前通常需要 10ms 的寻道时间和 4ms 的旋转延迟时间。
在 UNIX 文件系统上创建一个新文件。为了写这个文件，必须写该文件目录的节点、目录块、文件的 i 节点以及文件本身。
这些写操作有可能被延迟，如果在写操作完成之前发生死机，就可能在文件系统中造成不一致。所以 i 节点的写操作一般是立即完成的。
原理：
LFS 系统即使面对一个大部分由零碎的随机写操作组成的任务，同样能够充分利用磁盘的带宽。
所有的写操作最初都被缓冲在内存中，然后周期性地把所有已缓冲的写作为一个单独的段，在日志的末尾处写入磁盘。段可能会包括 i 节点、目录块、数据块。
i 节点分散在整个日志中，而不是放在磁盘的某一个固定位置。维护一个由节点编号索引组成的节点图。
要打开一个文件，则首先需要从 i 节点图中找到文件的节点。一旦节点定位之后就可以找到相应的块的地址。所有的块都放在段中，在日志的某个位置上。
清理线程：
实际的硬盘空间是有限的，最终日志将会占用整个磁盘。LFS 有一个清理线程，会程周期地扫描日志进行磁盘压缩。
- 首先读日志中的第一个段的摘要，检查有哪些 i 节点和文件。
- 然后查看当前节点图，判断该 i 节点是否有效以及文件块是否仍在使用中。
- 如果没有使用，则该信息被丢弃。
- 如果仍然使用，那么 i 节点和块就进入内存等待写回到下一个段中。
当一个文件块被写回到一个新段的时候，该文件的 i 节点必须首先要定位、更新，然后放到内存中准备写回到下一个段中。i 节点图接着必须更新以指向新的位置。
- 接着，原来的段被标记为空闲。整个磁盘成为一个大的环形的缓冲区，写线程将新的段写到前面，而清理线程则将旧的段从后面移走。
性能：
LFS 在处理大量的零碎的写操作时性能上比 UNIX 好上一个数量级，在读和大块写操作的性能方面并不比 UNIX 文件系统差，甚至更好。
2.5. 日志文件系统
日志文件系统：
保存一个用于记录系统下一步将要做什么的日志。这样当系统在任务中崩溃，重新启动后，可以查看日志获取崩溃前计划完成的任务。
系统崩溃带来的问题：
以移除文件操作举例，移除文件操作步骤如下：
- 在目录中删除文件；
- 释放 i 节点到空闲节点池；
- 将所有磁盘块归还空闲磁盘块池。
假如在第一步完成后系统崩溃。i 节点和文件块将不会被任何文件获得，也不会被再分配，它们只存在于废物池中的某个地方。
如果崩溃发生在第二步后，那么只有磁盘块会丢失。
日志事务：
日志文件系统先写一个日志项，列出三个将要完成的动作，然后日志项被写入磁盘。只有当日志项已经被写人，不同的操作才可以进行。当所有的操作成功完成后，擦除日志项。
如果系统这时崩溃，系统恢复后，文件系统可以通过检查日志来查看是不是有未完成的操作。如果有，可以重新运行所有未完成的操作，直到文件被正确地删除。
这要求被写入日志的操作必须是幂等的。
保证中间件的可靠性也可以用这种方法
为了增加可靠性，一个文件系统可以引入数据库中原子事务 (atomic transaction) 的概念。使用这个概念，一组动作可以被界定在开始事务和结束事务操作之间。
这样，文件系统就会知道它或者必须完成所有被界定的操作，或者什么也不做。
2.6. 虚拟文件系统
即使在同一个操作系统下，也会使用很多不同的文件系统。
2.6.1. Windows 处理多文件系统
Windows 通过指定不同的盘符来处理这些不同的文件系统。当一个进程打开一个文件，盘符是显式或者隐式存在的。
所以 Windows 知道向哪个文件系统传递请求，不需要尝试将不同类型文件系统整合为统一的模式。
2.6.2. Unix 处理多文件系统
相比之下，所有现代的 UNIX 系统做了一个很认真的尝试，即将多种文件系统整合到一个统一的结构中。
一个 Linux 系统可以用 ext2 作为根文件系统，ext3 分区装载在 /usr 下，另一块采用 ReiserFS 文件系统的硬盘装载在 /home 下，以及一个 ISO 9660 的 CD-ROM 临时装载在 /mnt 下。
从用户的观点来看，只有一个文件系统层级。它们事实上是多种文件系统，对于用户和进程是不可见的。
2.6.3. 虚拟文件系统（Virtual File System, VFS）
虚拟文件系统尝试将多种文件系统统一成一个有序的结构。
其关键思想是抽象出所有文件系统共有的部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来具体管理数据。
VFS 交互接口：
- 上层接口：被用户进程调用，是标准的 POSIX 系统调用，比如 open. read、 write 和 lseek 等。
- 下层接口：调用下层实际文件系统。VFS 接口包含许多功能调用。所以当创造一个新的文件系统和 VFS 一起工作时，设计者就必须确定它提供 VFS 所需要的功能调用。
用虚拟文件系统进行读操作过程：
- _装载文件系统：_文件系统在 VFS 中注册，提供一个包含 VFS 所需要的函数地址列表。VFS 知道如何执行实际文件系统提供的每一个功能。
- _创建 v 节点：_如果一个文件系统装载在 /usr 并且一个进程调用 open (“/usr/lnclude/unistd.h”, O_RDONLY)
VFS 会找到它所装载的文件的根目录，在那里查找路径 include/unistd.h，然后创建一个 v 节点并调用实际文件系统，从而返回文件 i 节点中的所有信息，并和其他信息一起复制到 v 节点中。
- VFS 在文件描述符表中创建一个表项，并且将它指向新的 v 节点。
- VFS 向调用者返回文件描述符，调用者可以用它去读、写或者关闭文件。
- 当进程用文件描述符进行一个读操作，VFS 通过进程表和文件描述符表确定 v 节点的位置，并跟随指针指向函数表，运行在实际文件系统中的代码。
联想：VFS 类似一个面向用户的统一接口，具体实现由下层文件系统实现
3. 文件系统管理及优化
3.1. 磁盘空间管理
按连续字节序列存储文件有一个明显问题，当文件扩大时，有可能需要在磁
盘上移动文件。因此，几乎所有的文件系统都把文件分割成固定大小的块来存储。
3.1.1. 块大小
块尺寸设的过大会导致很小的文件也会占用大量的磁盘空间。
块尺寸设的过小会导致大多数文件会跨越多个块，因此需要多次寻道与旋转延迟才能读出它们，从而降低了性能。
3.1.2. 记录空闲块
采用磁盘块链表：
链表的每个块中包含尽可能多的空闲磁盘块号。对于 1KB 大小的块和 32 位的磁盘块号，空闲表中每个块包含有 255 个空闲块的块号（需要有一个位置存放指向下一个块的指针）。
采用位图：
另一种空闲磁盘空间管理的方法是采用位图。
n 个块的磁盘需要 n 位位图。空闲块用 1 表示，已分配块用 0 表示（或者相反）。位图方法所需空间较少，因为每块只用一个二进制位标识，而在链表方法中，每一块要用到 32 位。
3.2. 文件系统性能
访问磁盘比访问内存慢得多。读内存中一个 32 位字大概要 10ns。从硬盘上读的速度大约为 100MB/s，对每 32 位字来说，大约要慢 4 倍，还要加上 5~10ms 寻道时间，并等待所需的扇面抵达磁头下。
3.2.1. 磁盘高速缓存
高速缓存指的是一系列的块， 它们在逻辑上属于磁盘，但实际上基于性能的考虑被保存在内存中。
最常用的减少磁盘访问次数技术是 块高速缓存（block cache）或者 缓冲区高速缓存（buffer cache）。
散列表：高速缓存使用散列表结构，方便快速查找所需要的块。
LRU：
使用双向链表把块以先后使用顺序链接起来。最近使用最少的块在链表的前端，最近使用最多的块在该链表的后端。
如果一个关键块（如 i 节点块）读进了高速缓存并做过修改，在写回磁盘前系统崩溃了，导致文件系统的不一致。如果把 i 节点块放在 LRU 链的尾部，在它到达链首并写回磁盘前，需要相当长的一段时间。
置换策略：
如果高速缓存已满，此时需要调入新的块，则要把原来的某一块调出高速缓存，如果要调出的块在上次调入以后修改过，则要把它写回磁盘。
与分页相似，常用的页面置换算法适用于高速缓存。
同步 / 异步写回：
我们不希望数据块在告诉缓存放很久之后才写回磁盘，这样十分容易丢失数据。为此操作系统采取了策略。
- 异步定时写回：UNIX 系统启动时会在后台运行 update 程序，每隔 30s 就执行 sync 调用。
- 同步写回： Windows 执行 FlushFileBuffers 系统调用。只要被写入高速缓存，就把每个被修改的块写回磁盘，但这样需要更多的磁盘 I/O。
3.2.2. 块提前读
在需要用到块之前，提前将其写入高速缓存，从而提高命中率。
许多文件都是顺序读的，如果请求文件系统在某个文件中生成块 k，文件系统执行相关操作且在完成之后，会检查块 k+1 是否已经在高速缓存。如果还不在，文件系统会为块 k+1 安排一个预读。
块提前读策略只适用于实际顺序读取的文件。对随机访问文件，提前读丝毫不起作用。文件系统通过跟踪每一个打开文件的访问方式来确定时候是顺序访问。
在最初不能确定文件属于哪种存取方式时，先将该位设置成顺序访问方式，查找一完成就将该位清除。这样即便弄错了一次也只是浪费一小段磁盘的带宽而已。
3.2.3. 减少磁盘臂运动
把有可能顺序访问的块放在一起，最好是在同一个柱面上，从而减少磁盘臂的移动次数。