《现代操作系统》读书笔记（四）——文件系统

4.1 文件

操作系统中处理文件的部分称为文件系统（file system）。
文件是进程创建的信息逻辑单元。

4.1.1 文件命名

文件是一种抽象机制，它提供了一种在磁盘上保留信息而且方便以后读取的方法。
文件名用圆点隔开分为两部分，圆点后面的部分称为文件扩展名（file extension），文件扩展名通常表示文件的一些信息。

4.1.2 文件结构

三种常见的文件结构：1)字节序列，2)记录序列，3)树。

4.1.3 文件类型

普通文件（regular file）中包含有用户信息，目录（directory）是管理文件系统结构的系统文件，字符特殊文件（character special file）和输入/输出有关用于串行I/O设备如终端、打印机、网络等，块特殊文件（block special file）用于磁盘类设备。
普通文件一般分为ASCII文件和二进制文件。
ASCII文件由多行正文组成，每行用回车符、换行符结束，各行的长度不一定相同，最大优势是可以显示和打印，可以用任何文本编辑器进行编辑。
二进制文件有一定的内部结构，打印出来是无法理解的。

4.1.4 文件存取

顺序存取（sequential access）：进程可在系统中从头顺序读取文件的全部字节或记录，但不能跳过某一些内容，也不能不按顺序读取。
随机存取文件（random access file）：可以不按顺序读取字节或记录或者按照关键字而不是位置来存取记录，这种能够以任何次序读取其中字节或记录的文件。

4.1.5 文件属性

文件都有文件名和数据，另外，操作系统还会保存其他与文件相关的信息，这些附加信息称为文件属性（attribute）或元数据（metadata）。

4.1.6 文件操作

使用文件的目的是存储信息并方便以后的检索。
一些常用的与文件有关的系统调用：

create：创建不包含任何数据的文件，并设置文件的一些属性；
delete：删除文件以释放磁盘空间；
open：打开文件（把文件属性和磁盘地址表装入内存）；
close：关闭文件（释放内存中文件属性和磁盘地址表空间）；
read：在文件中读取数据（必须明确需要读取多少数据，并且提供存放这些数据的缓冲区）；
write：向文件写数据；
append：为write的限制形式（只能在文件末尾添加数据）；
seek：定位文件中下次read或write的初始位置；
get attributes：查找文件属性；
set attributes：设置文件属性；
rename：重命名文件。

4.1.7 使用文件系统调用的一个示例程序

4.2 目录

文件系统通常提供目录或文件夹用于记录文件。

4.2.1 一级目录系统

一级目录系统最简单形式是在一个目录中包含所有的文件，称为根目录。

4.2.2 层次目录系统

通过层次结构目录（目录树）系统，可以用很多目录把文件以自然地方式分组。一个目录中可含有任意数量的文件与子目录。

4.2.3 路径名

每个文件都赋予一个绝对路径名（absolute path name），它由从根目录到文件的路径组成。
文件也可以使用一个相对路径名（relative path name），常和工作目录（working directory，也称作当前目录（current directory））一起使用，用户可以指定一个目录作为当前目录，由从工作目录到文件的路径组成。

4.2.4 目录操作

create：创建目录；
delete：删除目录；
opendir：打开目录（读其中全部文件的文件名）；
closedir：关闭目录（释放内部表空间）；
readdir：打开目录的下一个目录项；
rename：重命名目录；
link：制定一个存在的文件和一个路径名，并建立从该文件到路径所指名字的连接；
unlink：若解除连接的文件出现在多个目录中则只删除指定路径名的连接，若解除连接的文件只出现在一个目录中则直接删除文件。

4.3 文件系统的实现

4.3.1 文件系统布局

磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。磁盘的0号扇区称为主引导记录（Master Boot Record，MBR），用来引导计算机。在MBR的结尾是分区表，该表给出了每个分区的起始和结束地址，表中的一个分区被标记为活动分区。在计算机被引导时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入它的第一个块，称为引导块（boot block），并执行之。每个磁盘分区中都有引导块、超级块（superblock）、空闲空间管理、i节点、根目录、文件和目录。超级块中包括：确定文件系统类型用的魔数、文件系统中数据块的数量以及其他重要的管理信息。

4.3.2 文件的实现

连续分配
最简单的分配方式即连续分配，就是把每个文件作为一连串连续数据块存储在磁盘上。连续分配有两大优势：1)实现简单，记录每个文件用到的磁盘块简化为只需记住两个数字即可：第一个磁盘块地址和文件的块数；2)读操作性能较好，因为在单个操作中就可以从磁盘上读出整个文件，只需要一次寻找（对第一个块），之后不再需要寻道和旋转延迟，所以数据以磁盘全带宽的速率输入。这一方***导致出现很多磁盘碎片。随着CD-ROM、DVD以及其他一次性写光学介质的出现，连续分配又成为一个好主意。
链表分配
可以为每个文件构造磁盘块链表，每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。这一方法可以充分利用每个磁盘块，不会因为磁盘碎片而浪费存储空间。这一方法虽然顺序读文件非常方便，但是随机存取却相当缓慢。
在内存中采用表的链表分配
取出每个磁盘块的指针字，把它放在内存的一个表中，这样的一个表格称为文件分配表（File Allocation Table，FAT）。这一方法随机存取容易得多，但是对于大磁盘而言不太合适，因为这样FAT会很大。
i节点
最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为i节点（index-node）的数据结构，其中列出了文件属性和文件块的磁盘地址。通常为了打开文件而保留的i节点的数组所占据的空间比FAT所占据的空间要少。

4.3.3 目录的实现

可以把文件属性直接存放在目录项中，还可以把文件属性存放在i节点中而不是目录项中。
支持长文件名的一种方法是给予其一个长度限制，但是这样会浪费大量目录空间，替代方案是每个目录项大小不一，但是这样会产生很多磁盘碎片；另一种方式是每个文件名都由一个指针指向堆中的文件名来实现。
查找文件名可以用线性查找，但是这样太慢；也可以用散列表加速查找，但是这样管理比较复杂；还可以将查找结果存入高速缓存来加速查找。

4.3.4 共享文件

使一个目录下的一个文件出现在另一个目录下，这个另一个目录和这个共享文件的联系称为一个连接（link）。这样，文件系统本身是一个有向无环图（Directed Acyclic Graph，DAG）而不是一棵树。
有两种实现共享文件的方法，一种方法（硬连接）是将磁盘块列入一个与文件本身关联的小型数据结构中，目录将指向这个小型数据结构，i节点中进行连接者的计数，这种方法导致一旦文件删除则i节点可能被分配给其他文件导致连接至错误的文件；另一种方法（软连接）是将文件路径名存入新目录下连接的文件中，从而可以去寻找原文件，只有文件所有者目录中的目录项才会指向其i节点，这种方法开销会比较大。

4.3.5 日志结构文件系统

为解决磁盘寻道时间较长的问题而设计了日志结构文件系统（Log-structured File System，LFS）。UNIX文件系统的基本思想是将整个磁盘结构化为一个日志，每隔一段时间或是有特殊需要，被缓冲在内存中的所有未决的写操作都被放到一个单独的段中，作为在日志末尾的一个邻接段写入磁盘，一个单独的段可能会包括i节点、目录块、数据块或者都有，每一个段的开始都是该段的摘要，说明该段中都包含哪些内容。LFS的i节点分散在整个日志中而不是放在磁盘的某一个固定位置，为了能够找到i节点，必须维护一个由i节点编号索引组成的i节点图保存在磁盘上也保存在高速缓存中，但是磁盘空间有限，需要一个清理线程周期地扫描日志进行磁盘压缩。

4.3.6 日志文件系统

LFS和现有的文件系统不相匹配，，所以还没有被广泛应用，但是其内在的一个思想，即面对出错的鲁棒性，却可以被其他文件系统所借鉴，这里的基本思想是保存一个用于记录系统下一步将要做什么的日志，这样当系统在完成它们即将完成的任务前崩溃时，重新启动后，可以通过查看日志，获取崩溃前计划完成的任务，并完成它们，这样的文件系统被称为日志文件系统（Journaling File System，JFS），并已被实际应用。
移除文件需要在目录中删除文件、释放i节点到空闲i节点池、将所有磁盘块归还空闲磁盘块池，但是一旦系统崩溃，崩溃前执行到不同步骤会导致不同问题，需要用日志去记录。为了增加可信性，一个文件系统可以引入数据库中原子事务（atomic transaction）的概念，使用这个概念，一组动作可以被界定在开始事务和结束事务操作之间，这样，文件系统就会知道它必须完成所有被界定的操作，或者什么也不做，但是没有其他的选择。

4.3.7 虚拟文件系统

虚拟文件系统（Virtual File Sytstem，VFS）尝试将多种文件系统统一成一个有序的框架，关键的思想就是抽象出所有文件系统都共有的部分，并且将这部分代码放在单独的一层，该层调用底层的实际文件系统来具体管理数据。

4.4 文件系统管理和优化

4.4.1 磁盘空间管理

块大小
拥有大的块尺寸意味着小的文件会浪费大量磁盘空间；小的块尺寸意味着大多数文件会跨越多个块，即需要多次寻道与旋转延迟才能读出它们，浪费了时间。
记录空闲块
可以用将所有空闲块号存放在一个链表中，也可以用位图（每个磁盘块用一个二进制标识符记录其是否为空闲磁盘块）的方式管理所有磁盘块。
磁盘配额
提供一种强制性磁盘配额机制，其思想是系统管理员分给每个用户拥有文件和块的最大数量，操作系统确保每个用户不超过分给他们的配额。

4.4.2 文件系统备份

物理转储
从磁盘的第0块开始，将全部的磁盘块按需输出，直到最后一块复制完毕。对于未使用的磁盘块不需要备份，如果转储程序能够访问管理空闲块的数据结构，就可以避免备份未使用的磁盘块。要注意的是原磁盘和得到备份的磁盘块并不是一一对应的，所以应该在每个磁盘块前写上磁盘块号码。另一方面需要关注的是坏块的转储。可以通过建立一个包含所有坏块的“文件”来解决，以确保这些坏块不会被使用和分配。所以在转储时，需要跳过这些块。物理存储的优点是简单，快速，但是不能跳过选定的目录，也不能增量转储。
逻辑转储
从一个或几个指定的目录开始，递归地转储其自给定基准日期（如最近一次转储的日期）后所更改的全部文件和目录。在逻辑存储中，得到转储的磁盘会有一连串被标识过得目录和文件，可以按要求恢复特定文件或目录。

4.4.3 文件系统的一致性

一致性检查分为两种：块的一致性检查和文件的一致性检查。
检查块的一致性时，程序构造两张表，每张表为每一个块设立一个计数器，初始为0，第一个表中的计数器跟踪该块在文件中出现的次数，第二个表中的计数器跟踪该块在空闲表中出现的次数。接着检验程序使用原始设备读取全部i节点，从0开始。由i节点开始，可以建立相应文件中采用的全部块的块号表。每当读到一个块时，该块在第一个表中计数器加1。然后，程序检查空闲表或空闲位图，每当一个块未使用时，在第二张表中加1。检查完成后可能出现结果：一致，即每一块要么在第一个表计数器为1，要么在第二个表计数器为1；如果一个磁盘块在任何一张表中都是0，那么就称该块块丢失，解决方法是，检验程序将该块加入到空闲表中；一个块在空闲表中出现了两次，即一个块在第二张表中数字为2，解决方法是，重新建立空闲表；两个或多个文件中出现同一个数据块，即一个块在第一张表中数字为2，解决方法是，先分配一空闲块，将这个重复块的内容复制到空闲块中，然后把它插入到其中一个文件中。
检查文件的一致性时，检验程序检查目录系统，同样创建一张计数表，但每个文件而不是一个块对应一个计数器。程序从根目录开始检验，沿着目录树递归，检查文件系统中的每个目录。对每个目录中的每个文件，将文件使用计数器加1。遇到硬连接，同样加一，但是符号连接不计数。检验完成后，会得到一张由i节点号索引的表，说明每个文件被多少个目录包含。然后，检验程序将这些数字与存储在文件i节点中的连接数目比较。检查完成后可能出现结果：i节点连接数与计数器相等，则说明文件系统一致；i节点连接数大于计数器个数，说明即使所有该文件都被删除，计数仍是非0，i节点不会被删除，解决方法是，将i节点的值更新为计数器的值；i节点连接数小于计数器个数，可能导致一个目录指向错误i节点，解决方法同样是更新i节点值。

4.4.4 文件系统性能

高速缓存
常用算法为检查全部读请求，并检查高速缓存中是否有所需要的块。如果存在，可以直接执行读操作而无需访问磁盘。如果不存在，则将它读入到高速缓存，然后再复制到所需地方。为了快速确定所需块是否存在，通常使用散列表将设备和磁盘地址散列。为避免一致性遭到破坏（如一个块读进了高速缓存并进行过修改，但是在崩溃前没有写回磁盘），如果一个块关系到文件系统一致性且被修改，那应该立即将该块写回磁盘。该方法被称为通写高速缓存。
块提前读
在需要用到块之前，提前将其写入高速缓存。对于许多顺序读的文件，预读操作很适合。但是对于随机存取文件，提前读策略并不好。
减少磁盘臂运动
把有可能顺序存取的块放在一起，最好是一个柱面上，以减少磁盘臂的移动次数。对于位图保存空闲块的系统来说，可以很简单的找到最近的空闲块。对于使用空闲表的系统，需要使用块簇技术，即不用块，而是连续块簇来跟踪存储区。