3
文件系统的实现
在对文件有了基本认识之后，现在是时候把目光转移到文件系统的实现上了。之前用户关心的一直都是文件是怎样命名的、可以进行哪些操作、目录树是什么，如何找到正确的文件路径等问题。而设计人员关心的是文件和目录是怎样存储的、磁盘空间是如何管理的、如何使文件系统得以流畅运行的问题，下面我们就来一起讨论一下这些问题。
3.1
文件系统布局
文件系统存储在磁盘中。大部分的磁盘能够划分出一到多个分区，叫做磁盘分区(disk partitioning)或者是磁盘分片(disk slicing)。每个分区都有独立的文件系统，每块分区的文件系统可以不同。磁盘的 0 号分区称为主引导记录(Master Boot Record, MBR)，用来引导(boot)计算机。在 MBR 的结尾是分区表(partition table)。每个分区表给出每个分区由开始到结束的地址。系统管理员使用一个称为分区编辑器的程序来创建，调整大小，删除和操作分区。这种方式的一个缺点是很难适当调整分区的大小，导致一个分区具有很多可用空间，而另一个分区几乎完全被分配。
MBR 可以用在 DOS 、Microsoft Windows 和 Linux 操作系统中。从 2010 年代中期开始，大多数新计算机都改用 GUID 分区表（GPT）分区方案。
下面是一个用GParted进行分区的磁盘，表中的分区都被认为是活动的(active)。
当计算机开始引导 boot 时，BIOS 读入并执行 MBR。
引导块
MBR 做的第一件事就是确定活动分区，读入它的第一个块，称为引导块(boot block)并执行。引导块中的程序将加载分区中的操作系统。为了一致性，每个分区都会从引导块开始，即使引导块不包含操作系统。引导块占据文件系统的前 4096 个字节，从磁盘上的字节偏移量 0 开始。引导块可用于启动操作系统。
在计算机中，引导就是启动计算机的过程，它可以通过硬件（例如按下电源按钮）或者软件命令的方式来启动。开机后，电脑的 CPU 还不能执行指令，因为此时没有软件在主存中，所以一些软件必须先被加载到内存中，然后才能让 CPU 开始执行。也就是计算机开机后，首先会进行软件的装载过程。
重启电脑的过程称为重新引导(rebooting)，从休眠或睡眠状态返回计算机的过程不涉及启动。
除了从引导块开始之外，磁盘分区的布局是随着文件系统的不同而变化的。通常文件系统会包含一些属性，如下
超级块
紧跟在引导块后面的是超级块(Superblock)，超级块 的大小为 4096 字节，从磁盘上的字节偏移 4096 开始。超级块包含文件系统的所有关键参数
文件系统的大小
文件系统中的数据块数
指示文件系统状态的标志
分配组大小
在计算机启动或者文件系统首次使用时，超级块会被读入内存。
空闲空间块
接着是文件系统中空闲块的信息，例如，可以用位图或者指针列表的形式给出。
BitMap 位图或者 Bit vector 位向量
位图或位向量是一系列位或位的集合，其中每个位对应一个磁盘块，该位可以采用两个值：0 和 1，0 表示已分配该块，而 1 表示一个空闲块。下图中的磁盘上给定的磁盘块实例（分配了绿色块）可以用 16 位的位图表示为：0000111000000110。
使用链表进行管理
在这种方法中，空闲磁盘块链接在一起，即一个空闲块包含指向下一个空闲块的指针。第一个磁盘块的块号存储在磁盘上的单独位置，也缓存在内存中。
碎片
这里不得不提一个叫做碎片(fragment)的概念，也称为片段。一般零散的单个数据通常称为片段。磁盘块可以进一步分为固定大小的分配单元，片段只是在驱动器上彼此不相邻的文件片段。如果你不理解这个概念就给你举个例子。比如你用 Windows 电脑创建了一个文件，你会发现这个文件可以存储在任何地方，比如存在桌面上，存在磁盘中的文件夹中或者其他地方。你可以打开文件，编辑文件，删除文件等等。你可能以为这些都在一个地方发生，但是实际上并不是，你的硬盘驱动器可能会将文件中的一部分存储在一个区域内，另一部分存储在另外一个区域，在你打开文件时，硬盘驱动器会迅速的将文件的所有部分汇总在一起，以便其他计算机系统可以使用它。
inode
然后在后面是一个inode(index node)，也称作索引节点。它是一个数组的结构，每个文件有一个 inode，inode 非常重要，它说明了文件的方方面面。每个索引节点都存储对象数据的属性和磁盘块位置
有一种简单的方法可以找到它们ls -lai命令。让我们看一下根文件系统：
inode 节点主要包括了以下信息
模式/权限（保护）
所有者 ID
组 ID
文件大小
文件的硬链接数
上次访问时间
最后修改时间
inode 上次修改时间
文件分为两部分，索引节点和块。一旦创建后，每种类型的块数是固定的。你不能增加分区上 inode 的数量，也不能增加磁盘块的数量。
紧跟在 inode 后面的是根目录，它存放的是文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。
3.2
文件的实现
最重要的问题是记录各个文件分别用到了哪些磁盘块。不同的系统采用了不同的方法。下面我们会探讨一下这些方式。分配背后的主要思想是有效利用文件空间和快速访问文件，主要有三种分配方案
连续分配
链表分配
索引分配
连续分配
最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。因此，在具有 1KB 块的磁盘上，将为 50 KB 文件分配 50 个连续块。
上面展示了 40 个连续的内存块。从最左侧的 0 块开始。初始状态下，还没有装载文件，因此磁盘是空的。接着，从磁盘开始处（块 0 ）处开始写入占用 4 块长度的内存 A 。然后是一个占用 6 块长度的内存 B，会直接在 A 的末尾开始写。
注意每个文件都会在新的文件块开始写，所以如果文件 A 只占用了3 又 1/2个块，那么最后一个块的部分内存会被浪费。在上面这幅图中，总共展示了 7 个文件，每个文件都会从上个文件的末尾块开始写新的文件块。
连续的磁盘空间分配有两个优点。
第一，连续文件存储实现起来比较简单，只需要记住两个数字就可以：一个是第一个块的文件地址和文件的块数量。给定第一个块的编号，可以通过简单的加法找到任何其他块的编号。
第二点是读取性能比较强，可以通过一次操作从文件中读取整个文件。只需要一次寻找第一个块。后面就不再需要寻址时间和旋转延迟，所以数据会以全带宽进入磁盘。
因此，连续的空间分配具有实现简单、高性能的特点。
不幸的是，连续空间分配也有很明显的不足。随着时间的推移，磁盘会变得很零碎。下图解释了这种现象
这里有两个文件 D 和 F 被删除了。当删除一个文件时，此文件所占用的块也随之释放，就会在磁盘空间中留下一些空闲块。磁盘并不会在这个位置挤压掉空闲块，因为这会复制空闲块之后的所有文件，可能会有上百万的块，这个量级就太大了。
刚开始的时候，这个碎片不是问题，因为每个新文件都会在之前文件的结尾处进行写入。然而，磁盘最终会被填满，因此要么压缩磁盘、要么重新使用空闲块的空间。压缩磁盘的开销太大，因此不可行；后者会维护一个空闲列表，这个是可行的。但是这种情况又存在一个问题，为空闲块匹配合适大小的文件，需要知道该文件的最终大小。
想象一下这种设计的结果会是怎样的。用户启动 word 进程创建文档。应用程序首先会询问最终创建的文档会有多大。这个问题必须回答，否则应用程序就不会继续执行。如果空闲块的大小要比文件的大小小，程序就会终止。因为所使用的磁盘空间已经满了。那么现实生活中，有没有使用连续分配内存的介质出现呢？
CD-ROM就广泛的使用了连续分配方式。
CD-ROM（Compact Disc Read-Only Memory）即只读光盘，也称作只读存储器。是一种在电脑上使用的光碟。这种光碟只能写入数据一次，信息将永久保存在光碟上，使用时通过光碟驱动器读出信息。
然而 DVD 的情况会更加复杂一些。原则上，一个90 分钟的电影能够被编码成一个独立的、大约 4.5 GB 的文件。但是文件系统所使用的UDF(Universal Disk Format)格式，使用一个 30 位的数来代表文件长度，从而把文件大小限制在 1 GB。所以，DVD 电影一般存储在 3、4 个连续的 1 GB 空间内。这些构成单个电影中的文件块称为扩展区(extends)。
就像我们反复提到的，历史总是惊人的相似，许多年前，连续分配由于其简单和高性能被实际使用在磁盘文件系统中。后来由于用户不希望在创建文件时指定文件的大小，于是放弃了这种想法。但是随着 CD-ROM 、DVD、蓝光光盘等光学介质的出现，连续分配又流行起来。从而得出结论，技术永远没有过时性，现在看似很老的技术，在未来某个阶段可能又会流行起来。
链表分配
第二种存储文件的方式是为每个文件构造磁盘块链表，每个文件都是磁盘块的链接列表，就像下面所示
每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。如果上面这张图你看的不是很清楚的话，可以看看整个的链表分配方案
与连续分配方案不同，这一方法可以充分利用每个磁盘块。除了最后一个磁盘块外，不会因为磁盘碎片而浪费存储空间。同样，在目录项中，只要存储了第一个文件块，那么其他文件块也能够被找到。
另一方面，在链表的分配方案中，尽管顺序读取非常方便，但是随机访问却很困难（这也是数组和链表数据结构的一大区别）。
还有一个问题是，由于指针会占用一些字节，每个磁盘块实际存储数据的字节数并不再是 2 的整数次幂。虽然这个问题并不会很严重，但是这种方式降低了程序运行效率。许多程序都是以长度为 2 的整数次幂来读写磁盘，由于每个块的前几个字节被指针所使用，所以要读出一个完成的块大小信息，就需要当前块的信息和下一块的信息拼凑而成，因此就引发了查找和拼接的开销。
使用内存表进行链表分配
由于连续分配和链表分配都有其不可忽视的缺点。所以提出了使用内存中的表来解决分配问题。取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决上述链表的两个不足之处。下面是一个例子
上图表示了链表形成的磁盘块的内容。这两个图中都有两个文件，文件 A 依次使用了磁盘块地址4、7、 2、 10、 12，文件 B 使用了6、3、11 和 14。也就是说，文件 A 从地址 4 处开始，顺着链表走就能找到文件 A 的全部磁盘块。同样，从第 6 块开始，顺着链走到最后，也能够找到文件 B 的全部磁盘块。你会发现，这两个链表都以不属于有效磁盘编号的特殊标记（-1）结束。内存中的这种表格称为文件分配表(File Application Table,FAT)。
使用这种组织方式，整个块都可以存放数据。进而，随机访问也容易很多。虽然仍要顺着链在内存中查找给定的偏移量，但是整个链都存放在内存中，所以不需要任何磁盘引用。与前面的方法相同，不管文件有多大，在目录项中只需记录一个整数（起始块号），按照它就可以找到文件的全部块。
这种方式存在缺点，那就是必须要把整个链表放在内存中。对于 1TB 的磁盘和 1KB 的大小的块，那么这张表需要有 10 亿项。。。每一项对应于这 10 亿个磁盘块中的一块。每项至少 3 个字节，为了提高查找速度，有时需要 4 个字节。根据系统对空间或时间的优化方案，这张表要占用 3GB 或 2.4GB 的内存。FAT 的管理方式不能较好地扩展并应用于大型磁盘中。而这正是最初 MS-DOS 文件比较实用，并仍被各个 Windows 版本所安全支持。
inode
最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为inode(索引节点)的数据结构，每个文件都与一个inode进行关联，inode 由整数进行标识。
下面是一个简单例子的描述。
给出 inode 的长度，就能够找到文件中的所有块。
相对于在内存中使用表的方式而言，这种机制具有很大的优势。即只有在文件打开时，其 inode 才会在内存中。如果每个 inode 需要 n 个字节，最多 k 个文件同时打开，那么 inode 占有总共打开的文件是 kn 字节。仅需预留这么多空间。
这个数组要比我们上面描述的FAT(文件分配表)占用的空间小的多。原因是用于保存所有磁盘块的链接列表的表的大小与磁盘本身成正比。如果磁盘有 n 个块，那么这个表也需要 n 项。随着磁盘空间的变大，那么该表也随之线性增长。相反，inode 需要节点中的数组，其大小和可能需要打开的最大文件个数成正比。它与磁盘是 100GB、4000GB 还是 10000GB 无关。
inode 有一个问题是如果每个节点都会有固定大小的磁盘地址，那么文件增长到所能允许的最大容量外会发生什么？一个解决方案是最后一个磁盘地址不指向数据块，而是指向一个包含额外磁盘块地址的地址，如上图所示。一个更高级的解决方案是：有两个或者更多包含磁盘地址的块，或者指向其他存放地址的磁盘块的磁盘块。Windows 的 NTFS 文件系统采用了相似的方法，所不同的仅仅是大的 inode 也可以表示小的文件。
NTFS 的全称是New Technology File System，是微软公司开发的专用系统文件，NTFS 取代 FAT(文件分配表) 和HPFS(高性能文件系统)，并在此基础上进一步改进。例如增强对元数据的支持，使用更高级的数据结构以提升性能、可靠性和磁盘空间利用率等。
3.3
目录的实现
文件只有打开后才能够被读取。在文件打开后，操作系统会使用用户提供的路径名来定位磁盘中的目录。目录项提供了查找文件磁盘块所需要的信息。根据系统的不同，提供的信息也不同，可能提供的信息是整个文件的磁盘地址，或者是第一个块的数量（两个链表方案）或 inode 的数量。不过不管用那种情况，目录系统的主要功能就是将文件的 ASCII 码的名称映射到定位数据所需的信息上。
与此关系密切的问题是属性应该存放在哪里。每个文件系统包含不同的文件属性，例如文件的所有者和创建时间，需要存储的位置。一种显而易见的方法是直接把文件属性存放在目录中。有一些系统恰好是这么做的，如下。
在这种简单的设计中，目录有一个固定大小的目录项列表，每个文件对应一项，其中包含一个固定长度的文件名，文件属性的结构体以及用以说明磁盘块位置的一个或多个磁盘地址。
对于采用 inode 的系统，会把 inode 存储在属性中而不是目录项中。在这种情况下，目录项会更短：仅仅只有文件名称和 inode 数量。这种方式如下所示
到目前为止，我们已经假设文件具有较短的、固定长度的名字。在 MS-DOS 中，具有 1 - 8 个字符的基本名称和 1 - 3 个字符的可拓展名称。在 UNIX 版本 7 中，文件有 1 - 14 个字符，包括任何拓展。然而，几乎所有的现代操作系统都支持可变长度的扩展名。这是如何实现的呢？
最简单的方式是给予文件名一个长度限制，比如 255 个字符，然后使用上图中的设计，并为每个文件名保留 255 个字符空间。这种处理很简单，但是浪费了大量的目录空间，因为只有很少的文件会有那么长的文件名称。所以，需要一种其他的结构来处理。
一种可选择的方式是放弃所有目录项大小相同的想法。在这种方法中，每个目录项都包含一个固定部分，这个固定部分通常以目录项的长度开始，后面是固定格式的数据，通常包括所有者、创建时间、保护信息和其他属性。这个固定长度的头的后面是一个任意长度的实际文件名，如下图所示
上图是 SPARC 机器使用正序放置。
处理机中的一串字符存放的顺序有正序(big-endian)和逆序(little-endian)之分。正序存放的就是高字节在前低字节在后，而逆序存放的就是低字节在前高字节在后。
这个例子中，有三个文件，分别是project-budget、personnel和foo。每个文件名以一个特殊字符（通常是 0 ）结束，用矩形中的叉进行表示。为了使每个目录项从字的边界开始，每个文件名被填充成整数个字，如下图所示
这个方法的缺点是当文件被移除后，就会留下一块固定长度的空间，而新添加进来的文件大小不一定和空闲空间大小一致。
这个问题与我们上面探讨的连续磁盘文件的问题是一样的，由于整个目录在内存中，所以只有对目录进行紧凑拼接操作才可节省空间。另一个问题是，一个目录项可能会分布在多个页上，在读取文件名时可能发生缺页中断。
处理可变长度文件名字的另外一种方法是，使目录项自身具有固定长度，而将文件名放在目录末尾的堆栈中。如上图所示的这种方式。这种方法的优点是当目录项被移除后，下一个文件将能够正常匹配移除文件的空间。当然，必须要对堆进行管理，因为在处理文件名的时候也会发生缺页异常。
到目前为止的所有设计中，在需要查找文件名时，所有的方案都是线性的从头到尾对目录进行搜索。对于特别长的目录，线性搜索的效率很低。提高文件检索效率的一种方式是在每个目录上使用哈希表(hash table)，也叫做散列表。我们假设表的大小为 n，在输入文件名时，文件名被散列在 0 和 n - 1 之间，例如，它被 n 除，并取余数。或者对构成文件名字的字求和或类似某种方法。
无论采用哪种方式，在添加一个文件时都要对与散列值相对 应的散列表进行检查。如果没有使用过，就会将一个指向目录项的指针指向这里。文件目录项紧跟着哈希表后面。如果已经使用过，就会构造一个链表（这种构造方式是不是和 HashMap 使用的数据结构一样？），链表的表头指针存放在表项中，并通过哈希值将所有的表项相连。
查找文件的过程和添加类似，首先对文件名进行哈希处理，在哈希表中查找是否有这个哈希值，如果有的话，就检查这条链上所有的哈希项，查看文件名是否存在。如果哈希不在链上，那么文件就不在目录中。
使用哈希表的优势是查找非常迅速，缺点是管理起来非常复杂。只有在系统中会有成千上万个目录项存在时，才会考虑使用散列表作为解决方案。
另外一种在大量目录中加快查找指令目录的方法是使用缓存，缓存查找的结果。在开始查找之前，会首先检查文件名是否在缓存中。如果在缓存中，那么文件就能立刻定位。当然，只有在较少的文件下进行多次查找，缓存才会发挥最大功效。
3.4
共享文件
当多个用户在同一个项目中工作时，他们通常需要共享文件。如果这个共享文件同时出现在多个用户目录下，那么他们协同工作起来就很方便。下面的这张图我们在上面提到过，但是有一个更改的地方，就是C 的一个文件也出现在了 B 的目录下。
如果按照如上图的这种组织方式而言，那么 B 的目录与该共享文件的联系称为链接(link)。那么文件系统现在就是一个有向无环图(Directed Acyclic Graph, 简称 DAG)，而不是一棵树了。
在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图，我们不会在此着重探讨关于图论的东西，大家可以自行 google。
将文件系统组织成为有向无环图会使得维护复杂化，但也是必须要付出的代价。
共享文件很方便，但这也会带来一些问题。如果目录中包含磁盘地址，则当链接文件时，必须把 C 目录中的磁盘地址复制到 B 目录中。如果 B 或者 C 随后又向文件中添加内容，则仅在执行追加的用户的目录中显示新写入的数据块。这种变更将会对其他用户不可见，从而破坏了共享的目的。
有两种方案可以解决这种问题。
第一种解决方案，磁盘块不列入目录中，而是会把磁盘块放在与文件本身相关联的小型数据结构中。目录将指向这个小型数据结构。这是UNIX中使用的方式（小型数据结构就是 inode）。
在第二种解决方案中，通过让系统建立一个类型为LINK的新文件，并把该文件放在 B 的目录下，使得 B 与 C 建立链接。新的文件中只包含了它所链接的文件的路径名。当 B 想要读取文件时，操作系统会检查 B 的目录下存在一个类型为 LINK 的文件，进而找到该链接的文件和路径名，然后再去读文件，这种方式称为符号链接(symbolic linking)。
上面的每一种方法都有各自的缺点，在第一种方式中，B 链接到共享文件时，inode 记录文件的所有者为 C。建立一个链接并不改变所有关系，如下图所示。
第一开始的情况如图 a 所示，此时 C 的目录的所有者是 C ，当目录 B 链接到共享文件时，并不会改变 C 的所有者关系，只是把计数 + 1，所以此时系统知道目前有多少个目录指向这个文件。然后 C 尝试删除这个文件，这个时候有个问题，如果 C 把文件移除并清除了 inode 的话，那么 B 会有一个目录项指向无效的节点。如果 inode 以后分配给另一个文件，则 B 的链接指向一个错误的文件。系统通过 inode 可知文件仍在被引用，但是没有办法找到该文件的全部目录项以删除它们。指向目录的指针不能存储在 inode 中，原因是有可能有无数个这样的目录。
所以我们能做的就是删除 C 的目录项，但是将 inode 保留下来，并将计数设置为 1 ，如上图 c 所示。c 表示的是只有 B 有指向该文件的目录项，而该文件的前者是 C 。如果系统进行记账操作的话，那么 C 将继续为该文件付账直到 B 决定删除它，如果是这样的话，只有到计数变为 0 的时刻，才会删除该文件。
对于符号链接，以上问题不会发生，只有真正的文件所有者才有一个指向 inode 的指针。链接到该文件上的用户只有路径名，没有指向 inode 的指针。当文件所有者删除文件时，该文件被销毁。以后若试图通过符号链接访问该文件将会失败，因为系统不能找到该文件。删除符号链接不会影响该文件。
符号链接的问题是需要额外的开销。必须读取包含路径的文件，然后要一个部分接一个部分地扫描路径，直到找到 inode 。这些操作也许需要很多次额外的磁盘访问。此外，每个符号链接都需要额外的 inode ，以及额外的一个磁盘块用于存储路径，虽然如果路径名很短，作为一种优化，系统可以将它存储在 inode 中。符号链接有一个优势，即只要简单地提供一个机器的网络地址以及文件在该机器上驻留的路径，就可以连接全球任何地方机器上的文件。
还有另一个由链接带来的问题，在符号链接和其他方式中都存在。如果允许链接，文件有两个或多个路径。查找一指定目录及其子目录下的全部文件的程序将多次定位到被链接的文件。例如，一个将某一目录及其子目录下的文件转存到磁带上的程序有可能多次复制一个被链接的文件。进而，如果接着把磁带读入另一台机器，除非转出程序具有智能，否则被链接的文件将被两次复制到磁盘上，而不是只是被链接起来。
3.5
日志结构文件系统
技术的改变会给当前的文件系统带来压力。这种情况下，CPU 会变得越来越快，磁盘会变得越来越大并且越来越便宜（但不会越来越快）。内存容量也是以指数级增长。但是磁盘的寻道时间（除了固态盘，因为固态盘没有寻道时间）并没有获得提高。
这些因素结合起来意味着许多系统文件中出现性能瓶颈。为此，Berkeley设计了一种全新的文件系统，试图缓解这个问题，这个文件系统就是日志结构文件系统(Log-structured File System, LFS)。
日志结构文件系统由Rosenblum和Ousterhout于 90 年代初引入，旨在解决以下问题。
不断增长的系统内存
顺序 I/O 性能胜过随机 I/O 性能
现有低效率的文件系统
文件系统不支持 RAID（虚拟化）
另一方面，当时的文件系统不论是 UNIX 还是 FFS，都有大量的随机读写（在 FFS 中创建一个新文件至少需要 5 次随机写），因此成为整个系统的性能瓶颈。同时因为Page cache的存在，作者认为随机读不是主要问题：随着越来越大的内存，大部分的读操作都能被 cache，因此 LFS 主要要解决的是减少对硬盘的随机写操作。
在这种设计中，inode 甚至具有与 UNIX 中相同的结构，但是现在它们分散在整个日志中，而不是位于磁盘上的固定位置。所以，inode 很定位。为了能够找到 inode ，维护了一个由 inode 索引的inode map(inode 映射)。表项 i 指向磁盘中的第 i 个 inode 。这个映射保存在磁盘中，但是也保存在缓存中，因此，使用最频繁的部分大部分时间都在内存中。
日志结构文件系统主要使用四种数据结构：Inode、Inode Map、Segment、Segment Usage Table。
到目前为止，所有写入最初都缓存在内存中，并且追加在日志末尾，所有缓存的写入都定期在单个段中写入磁盘。所以，现在打开文件也就意味着用映射定位文件的索引节点。一旦 inode 被定位后，磁盘块的地址就能够被找到。所有这些块本身都将位于日志中某处的分段中。
真实情况下的磁盘容量是有限的，所以最终日志会占满整个磁盘空间，这种情况下就会出现没有新的磁盘块被写入到日志中。幸运的是，许多现有段可能具有不再需要的块。例如，如果一个文件被覆盖了，那么它的 inode 将被指向新的块，但是旧的磁盘块仍在先前写入的段中占据着空间。
为了处理这个问题，LFS 有一个清理(clean)线程，它会循环扫描日志并对日志进行压缩。首先，通过查看日志中第一部分的信息来查看其中存在哪些索引节点和文件。它会检查当前 inode 的映射来查看 inode 是否在当前块中，是否仍在被使用。如果不是，该信息将被丢弃。如果仍然在使用，那么 inode 和块就会进入内存等待写回到下一个段中。然后原来的段被标记为空闲，以便日志可以用来存放新的数据。用这种方法，清理线程遍历日志，从后面移走旧的段，然后将有效的数据放入内存等待写到下一个段中。由此一来整个磁盘会形成一个大的环形缓冲区，写线程将新的段写在前面，而清理线程则清理后面的段。
3.6
日志文件系统
虽然日志结构系统的设计很优雅，但是由于它们和现有的文件系统不相匹配，因此还没有广泛使用。不过，从日志文件结构系统衍生出来一种新的日志系统，叫做日志文件系统，它会记录系统下一步将要做什么的日志。微软的NTFS文件系统、Linux 的ext3就使用了此日志。OS X将日志系统作为可供选项。为了看清它是如何工作的，我们下面讨论一个例子，比如移除文件，这个操作在 UNIX 中需要三个步骤完成：
在目录中删除文件
释放 inode 到空闲 inode 池
将所有磁盘块归还给空闲磁盘池。
在 Windows 中，也存在类似的步骤。不存在系统崩溃时，这些步骤的执行顺序不会带来问题。但是一旦系统崩溃，就会带来问题。假如在第一步完成后系统崩溃。inode 和文件块将不会被任何文件获得，也不会再分配；它们只存在于废物池中的某个地方，并因此减少了可利用的资源。如果崩溃发生在第二步后，那么只有磁盘块会丢失。日志文件系统保留磁盘写入期间对文件系统所做的更改的日志或日志，该日志可用于快速重建可能由于系统崩溃或断电等事件而发生的损坏。
一般文件系统崩溃后必须运行fsck（文件系统一致性检查）实用程序。
为了让日志能够正确工作，被写入的日志操作必须是幂等的(idempotent)，它意味着只要有必要，它们就可以重复执行很多次，并不会带来破坏。像操作更新位表并标记 inode k 或者块 n 是空闲的可以重复执行任意次。同样地，查找一个目录并且删除所有叫foobar的项也是幂等的。相反，把从 inode k 新释放的块加入空闲表的末端不是幂等的，因为它们可能已经被释放并存放在那里了。
为了增加可靠性，一个文件系统可以引入数据库中原子事务(atomic transaction)的概念。使用这个概念，一组动作可以被界定在开始事务和结束事务操作之间。这样，文件系统就会知道它必须完成所有的动作，要么就一个不做。
3.7
虚拟文件系统
即使在同一台计算机上或者在同一个操作系统下，都会使用很多不同的文件系统。Windows 中的主要文件系统是NTFS 文件系统，但不是说 Windows 只有 NTFS 操作系统，它还有一些其他的例如旧的FAT -32或FAT -16驱动器或分区，其中包含仍需要的数据，闪存驱动器，旧的 CD-ROM 或 DVD（每个都有自己的独特文件系统）。Windows 通过指定不同的盘符来处理这些不同的文件系统，比如C:，D:等。盘符可以显示存在也可以隐式存在，如果你想找指定位置的文件，那么盘符是显示存在；如果当一个进程打开一个文件时，此时盘符是隐式存在，所以 Windows 知道向哪个文件系统传递请求。
相比之下，UNIX 采用了一种不同的方式，即 UNIX 把多种文件系统整合到一个统一的结构中。一个 Linux 系统可以使用ext2作为根文件系统，ext3分区装载在/usr下，另一块采用Reiser FS文件系统的硬盘装载到/home下，以及一个 ISO 9660 的 CD - ROM 临时装载到/mnt下。从用户的观点来看，只有一个文件系统层级，但是事实上它们是由多个文件系统组合而成，对于用户和进程是不可见的。
UNIX 操作系统使用一种虚拟文件系统(Virtual File System, VFS)来尝试将多种文件系统构成一个有序的结构。关键的思想是抽象出所有文件系统都共有的部分，并将这部分代码放在一层，这一层再调用具体文件系统来管理数据。下面是一个 VFS 的系统结构
还是那句经典的话，在计算机世界中，任何解决不了的问题都可以加个代理来解决。所有和文件相关的系统调用在最初的处理上都指向虚拟文件系统。这些来自用户进程的调用，都是标准的POSIX 系统调用，比如 open、read、write 和 seek 等。VFS 对用户进程有一个上层接口，这个接口就是著名的 POSIX 接口。
VFS 也有一个对于实际文件的下层接口，就是上图中标记为 VFS 的接口。这个接口包含许多功能调用，这样 VFS 可以使每一个文件系统完成任务。因此，要创建一个可以与 VFS 一起使用的新文件系统，新文件系统的设计者必须确保它提供了 VFS 要求的功能。一个明显的例子是从磁盘读取特定的块，然后将其放入文件系统的缓冲区高速缓存中，然后返回指向该块的指针的函数。因此，VFS 具有两个不同的接口：上一个到用户进程，下一个到具体文件系统。
当系统启动时，根文件系统在 VFS 中注册。另外，当装载其他文件时，不管在启动时还是在操作过程中，它们也必须在 VFS 中注册。当一个文件系统注册时，根文件系统注册到 VFS。另外，在引导时或操作期间挂载其他文件系统时，它们也必须向 VFS 注册。当文件系统注册时，其基本作用是提供 VFS 所需功能的地址列表、调用向量表、或者 VFS 对象。因此一旦文件系统注册到 VFS，它就知道从哪里开始读取数据块。
装载文件系统后就可以使用它了。比如，如果一个文件系统装载到/usr并且一个进程调用它：
open("/usr/include/unistd.h",O_RDONLY)
当解析路径时， VFS 看到新的文件系统被挂载到/usr，并且通过搜索已经装载文件系统的超级块来确定它的超块。然后它找到它所转载的文件的根目录，在那里查找路径include/unistd.h。然后 VFS 创建一个 vnode 并调用实际文件系统，以返回所有的在文件 inode 中的信息。这个信息和其他信息一起复制到 vnode （内存中）。而这些其他信息中最重要的是指向包含调用 vnode 操作的函数表的指针，比如 read、write 和 close 等。
当 vnode 被创建后，为了进程调用，VFS 在文件描述符表中创建一个表项，并将它指向新的 vnode，最后，VFS 向调用者返回文件描述符，所以调用者可以用它去 read、write 或者 close 文件。
当进程用文件描述符进行一个读操作时，VFS 通过进程表和文件描述符确定 vnode 的位置，并跟随指针指向函数表，这样就调用了处理 read 函数，运行在实际系统中的代码并得到所请求的块。VFS 不知道请求时来源于本地硬盘、还是来源于网络中的远程文件系统、CD-ROM 、USB 或者其他介质，所有相关的数据结构如下图所示
从调用者进程号和文件描述符开始，进而是 vnode，读函数指针，然后是对实际文件系统的访问函数定位。
网友评论