一、文件系统结构 #

磁盘的逻辑单元为块，内存和磁盘之间的 I/O 传输以块为单位执行。

磁盘的特点 #

1. 可以原地重写，可以从磁盘上读一块儿，修改该块，并将它写回到原来的位置。
2. 可以直接访问磁盘上的任意一块。因此，可以方便地按顺序或随机访问文件。

文件系统需要提供高效快捷磁盘访问，以便轻松存储、定位、提取数据。即存储文件、访问文件。

文件系统有两个不同的设计问题：

1. 访问问题：如何定义文件系统对用户的接口。
2. 存储问题：创建数据结构和算法，把逻辑文件系统映射到物理外存设备。

文件系统本身通常由许多不同层组成。每层实际利用更低层功能，创建新的功能，以用于更高层的服务。

设备驱动程序可以作为翻译器，他的输入作为高级指令，输出由底层的、硬件特定指令组成。基础文件系统只需向适当设备驱动程序发送命令。逻辑文件系统通过文件控制块维护文件结构。

文件控制块（FCB）包含有关文件的信息，包括所有者、权限、文件内容的位置等。

大多数操作系统支持多种不同的文件系统，举例：

• CD-ROM ISO9660 文件格式
• Unix 文件系统（Unix File System）
• Windows 文件系统：FAT（File Allocation Table），FAT32, FAT64, NTFS（Windows NT File System）
• Linux 文件系统：可扩展文件系统（Extended file system），分布式文件系统（Distributed File System）

二、文件系统实现 #

1. 概述 #

在磁盘上，文件系统包括的信息有：

1. 如何启动存储在那里操作系统
2. 总的块数
3. 空闲块的数目和位置
4. 目录结构
5. 各个具体文件等

上述许多结构会在之后详细讲述。这里简述如下：

• 引导控制块（每个卷）：可以包含从该卷引导操作系统的所需信息。如果磁盘不包括操作系统，则这块的内容为空。UFS 称为引导块（boot block），NFS 称为分区引导扇区（partition boot sector）。
• 卷控制块（每个卷）：包括卷的详细信息（分区的块数、块的大小、空闲块的数量和指针、空闲 FCB 的数量和指针等）。UFS 称为超级块（super block），NTFS 主控文件表（master boot sector）。
• 每个文件的 FCB 包含该文件的许多详细信息。他有一个唯一的标识号，以便与目录条目相关联。
• 每个文件系统的目录结构用于组织文件。

内存中的信息用于管理文件系统并通过缓存来提高性能，这些数据在安装文件装系统时被加载，在文件系统操作期间被更新，在卸载是被卸载。这些结构类型包括：

1. 每个进程的打开文件表：包括一个指向系统的打开文件表中合适条目的指针和其他信息。
2. 整个系统的打开文件表：包括每个打开文件的 FCB 副本和其他信息。

创建一个新文件：

1. 应用程序调用逻辑文件系统。逻辑文件系统指导目录结构的格式，它会分配一个新的 FCB。
2. 系统将相应的目录信息读入内存。
3. 更新目录结构和 FCB。
4. 将结果写回磁盘。

一旦文件被创建，就能用于 I/O，不过，首先他要被打开。系统调用 open() 将文件名传到逻辑文件系统，系统调用 open()：

1. 首先搜索整个系统的打开文件表，查看是否已经被打开，如果是，则在该进程的打开文件表创建一个条目，并指向现有整个系统的打开文件表。
2. 否则，根据文件名搜索目录结构。
3. 找到后，它的 FCB 会复制到内存的整个系统的开放文件表中（该表还存放着打开该文件的进程数量），接下来，在该进程的打开文件表创建一个条目，并指向现有整个系统的打开文件表。

open() 返回值：文件描述符是一个非负整数。它是一进程打开文件表的索引值，指向系统范围内打开文件表相应条目。

2. 虚拟文件系统 #

操作系统如何才能将多个类型的文件系统集成到目录结构中？用户如何在访问文件系统空间时，可以无缝地在文件系统类型间迁移？大多数操作系统采用面向对象的技术来简化、组织、模块化实现。

数据结构和程序用于隔离基本的操作系统调用的功能与实现细节。因此，文件系统的实现有三个主要层构成。

第一层为文件系统接口。

第二层为虚拟文件系统（VFS），把文件系统的通用操作和具体实现分开，虚拟文件系统提供了在唯一标识一个文件的机制。VFS 基于 vnode 的文件表示结构，它包含了一个数值标识符来唯一表示网络上的一个文件。

1. VFS 能区分不同本地文件系统。
2. VFS 能区分本地文件系统和远程文件系统。

三、目录实现 #

1. 线性列表 #

采用文件名称和数据块指针的线性列表。

• 优点：编程简单。
• 缺点：因为需要搜索，运行较为费时。

2. 哈希表 #

哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。

• 优点：减少目录搜索时间。
• 缺点：两个文件名哈希到相同的位置时可能发生冲突；因哈希表固定大小，创建文件需要哈希表重建时，比较麻烦。

四、磁盘空间的分配方法 #

1. 连续分配 #

每个文件在磁盘上占有一组连续的块。文件的连续分配可以用文件第一块的磁盘地址和连续块的数量（即长度）来定义。

连续分配支持顺序访问和直接访问。

问题：当文件需要扩展，文件大小变大时会无法扩展。

解决：找更大的连续空间，复制过去。

基于扩展的连续分配方案用以下参数来定义文件：

1. 开始地址
2. 块数
3. 指向下一个扩展块的指针（扩展块可以是多个）

定义格式：文件【开始地址，块数，指向下一个扩展块的指针】

2. 链接分配 #

每个文件是磁盘块的链表，磁盘块分布在磁盘的任何地方，文件有起始块和结束块来定义。

定义格式：【起始块，结束块】

同时，每个磁盘块都有指向下一个磁盘块的地址。

优点：没有磁盘空间浪费。

缺点：

1. 不支持文件的直接访问。
2. 需要更多的磁盘空间（来记录指针）。

链接分配的一个重要变种是文件分配表。

每个卷的开始部分用于存储文件分配表（File Allocation Table），表中每个磁盘块都有一个 FAT 条目，并可通过块号索引。（未使用的块为 0，使用的块包含下一个块号）

目录条目含有文件首块号码，通过这个块号索引的 FAT 条目包含文件下一块的号码，这个链会继续下去，直到最后一块，最后一块的表条目值为文件结束值。

3. 索引分配 #

通过将所有指针放在一起，即索引块。

文件用索引块来定义，每个文件有其索引块。

这里有一个问题，索引块应为多大？

每个文件必须有一个索引块，因此索引块应尽可能小，然而不能太小，否则放不下足够多的指针，为处理这个问题，有如下一些机制：

1. 链接方案：为了处理大文件，可以将多个索引块链接起来。
2. 多层次索引：用第一层索引块指向一组第二层的索引块，第二层索引块再指向文件块。
3. 组合方案：用于基于 UNIX 的文件系统，将索引块的前 15 个指针存储在文件的 i-node 中。其中，前 12 个指针指向直接块，剩下 3 个指针指向间接块。

五、磁盘空闲空间的管理 #

1. 位向量 #

空闲空间表实现为位图，或位向量，每块用一位（bit）表示。1 表示块空闲；0 表示块已分配。

2. 链表 #

所有空闲块用链表链接起来，并将指向第一个空闲块的指针保存在特殊位置，同时缓存在内存。

每个块含有下一个块的指针。

3. 组 #

将 n 个空闲块的地址保存在第一个空闲块中。

这些空闲块中的前 n－1 个为空，而最后一块包含另外 n 个空闲块的地址。

比链表好的是空闲块的地址可以很快找到，而且可以明确一段连续空闲块空间。

例：n=3

4. 计数 #

基于以下事实：

通常有多个连续块需要同时分配或释放，尤其是在使用连续分配时。因此记录：

• 记录第一块的地址和紧跟第一块的连续的空闲块的数量。
• 空闲空间表的每个条目包括磁盘地址和数量。

例：

六、文件系统的性能和效率 #

磁盘空间的有效使用（效率），取决于：

• 磁盘分配和目录管理算法
• 保留在文件目录条目中的数据类型

改善性能的方法：缓存

1. 缓冲区缓存：一块独立内存，位于其中的块是马上需要使用的。
2. 页面缓存：将文件数据作为页而不是块来缓存。页面缓存使用虚拟内存技术，将文件数据作为页来缓存，比采用物理磁盘块来缓存更高效。
3. 板载高速缓存

如果没有统一缓存，则会由下图情况发生：

系统调用 read() 和 write() 会通过缓冲区缓存，然而，内存映射调用需要使用两个缓存，即页面缓存和缓冲区缓存。内存映射先从文件系统中读入磁盘块，并放入缓冲区缓存，由于虚拟内存系统没有缓冲区缓存接口，缓冲缓存内的文件必须复制到页面缓存中。

采用统一缓冲缓存：

统一缓冲缓存：统一使用缓冲器缓存来缓存进程页和文件数据。

无论是缓存块还是页面都有置换问题，文件的读入或写出一般是按顺序进行。所以，不适合采用 LRU 算法，因为最近使用的页面最后才会用甚至根本不会再用。

顺序访问可以通过马上释放和预先读取来加以优化：

1. 马上释放（free-behind）：请求下一页时，马上释放上一页。
2. 预先读取（read-ahead）：请求页之后的下一个页也一起读入。

七、文件系统的恢复 #

目录信息一般事先保存在内存中以加快访问，有时会导致目录结构中的数据和磁盘块中的数据不一致。

解决：

1. 一致性检查：比较目录结构中的数据和磁盘块中的数据，尝试着去修正不一致。
2. 备份 & 恢复：
   • 备份（backup）：利用系统程序来备份数据到其他的存储设备。软盘，磁带。
   • 恢复（recovery）：通过从备份来恢复丢失的文件或磁盘。

基于日志结构的文件系统：

• 文件创建涉及到目录结构修改，FCB 分配，数据块分配等。
• 所有元数据（meta data）的变化写入日志上，一旦这些修改写到日志，就认为已经提交了。
• 提交了的事务，并不一定马上完成操作。
• 当整个提交的事务已经完成时，就从日志中删除事务条目。
• 如果系统崩溃，日志文件可能还存在事务，它包含的任何事务虽然已经由操作系统提交了，但还没有完成到文件系统，必须重新执行。

文章来源于网络，好久之前整理的了，找不到出处了，如果侵权，请联系我删除。