操作系统原理之文件系统 #

目录 #

文件系统简介 #

文件 #

文件（file）是记录在二级存储（secondary storage）上的相关信息的集合（collection）。或者说文件是逻辑上相关实体（logically related entities）的集合。从用户的角度来看，一个文件是逻辑二级存储的最小分配量（smallest allotment）。

文件的名称分为两部分，如下图所示：

• 名称
• 扩展名（extension），用英文句号 . 隔开。

文件属性和它的操作：

文件目录 #

文件的集合就是一个文件目录（file directory）。该目录包含有关文件的信息，包括属性（attributes）、位置（location）和所有权（ownership）。这些信息中的大部分，特别是与存储有关的信息，由操作系统管理。目录本身就是一个文件，可由各种文件管理程序（file management routines）访问。

设备目录中包含的信息有：

• 名称（Name）
• 类型（Type）
• 地址（Address）
• 当前长度（Current length）
• 最大长度（Maximum length）
• 最后访问日期（Date last accessed）
• 最后更新日期（Date last updated）
• 业主身份（Owner id）
• 保护信息（Protection information）

对目录进行的操作是：

• 搜索文件（Search for a file）
• 创建文件（Create a file）
• 删除文件（Delete a file）
• 列出目录（List a directory）
• 重命名文件（Rename a file）
• 遍历文件系统（Traverse the file system）

维护目录的优势在于：

• 效率。可以更快找到文件。
• 命名。它为用户提供了方便，因为两个用户可以为不同的文件使用相同的名称，也可以为同一个文件使用不同的名称。
• 分组。文件的逻辑分组可以通过属性来完成，例如，所有的 java 程序，所有的游戏等。

单层目录（SINGLE-LEVEL DIRECTORY）：为所有用户维护的一个单一的目录。

• 命名问题（Naming problem）：用户不能对两个文件使用相同的名字。
• 分组问题（Grouping problem）：用户不能根据他们的需要对文件进行分组。

双层目录：每个用户都有单独的目录被维护。

• 路径名称：由于两级目录，每个文件都有一个路径名称来定位该文件。
• 可以为不同的用户提供相同的文件名。
• 搜索是高效的。

树状结构的目录：目录是以树状形式维护的。搜索高效，也有分组的能力。我们对一个文件有绝对或相对的路径（absolute or relative path）名称。

文件分配方法 #

连续分配（Continuous Allocation） #

在创建文件时，为文件分配一套单一的连续块（single continuous set of blocks）。因此，这是一种预分配策略（pre-allocation strategy），使用可变大小的分区（variable size portions）。文件分配表（file allocation table）对每个文件只需要一个条目，显示起始块（ starting block）和文件的长度。从单个顺序文件的角度来看，这种方法是最好的。一次可以读入多个块，以提高顺序处理（sequential processing）的 I/O 性能。检索单个块也很容易。例如，如果一个文件从 b 块开始，想要该文件的第 i 个块，它在二级存储中的位置只是 b+i-1 。

劣势：

• 会出现外部碎片（External fragmentation），使其难以找到足够长度的连续空间块。将有必要采用压缩算法（Compaction algorithm）来释放磁盘上的额外空间。
• 在预分配（pre-allocation）的情况下，有必要在创建时声明文件的大小。

链接分配（Linked Allocation） #

链接分配（Linked Allocation），即非连接分配（Non-contiguous allocation）。分配是在单个块的基础上进行的。每个区块都包含一个指向链中下一个区块的指针。同样，文件表（file table）对每个文件只需要一个条目，显示起始块和文件的长度。尽管预分配是可能的，但更常见的是根据需要分配块。任何空闲的块都可以被添加到链上，且这些块不需要是连续的。如果有可用的磁盘块，增加文件大小总是可能的。没有外部碎片，因为每次只需要一个块，但可能有内部碎片（internal fragmentation），但它只存在于文件的最后一个磁盘块。

缺点：

• 内部碎片存在于文件的最后一个磁盘块中。
• 维护每个磁盘块的指针是一种开销。
• 如果任何磁盘块的指针丢失，文件将被截断 (truncated)。
• 它只支持文件的顺序访问（sequential access）。

索引式分配（Indexed Allocation） #

它解决了许多连续和链式分配的问题。在这种情况下，文件分配表（file allocation table）为每个文件包含一个单独的单级索引（one-level index）。该索引对分配给文件的每个块都有一个条目。分配可能是基于固定大小的块或可变大小的块。按块分配消除了外部碎片，而按可变大小的块（variable-size blocks）分配则提高了位置灵活性（locality）。这种分配技术同时支持对文件的顺序和直接访问，因此是最流行的文件分配形式。

磁盘空闲空间管理:

正如必须对分配给文件的空间进行管理一样，也必须对当前未分配给任何文件的空间进行管理。为了执行任何文件分配技术，有必要知道磁盘上有哪些块是可用的。因此，除了文件分配表（file allocation table）之外，我们还需要一个磁盘分配表（disk allocation table）。以下是用于空闲空间管理的方法：

• 位表（Bit Tables）：这种方法使用一个向量，包含磁盘上每个块的一个比特。0 对应于一个空闲块，1 对应于一个正在使用的块。例如：00011010111100110001，在这个向量中，每一个比特都对应于一个特定的块，0 意味着该特定的块是空闲的，1 意味着该块已经被占用。位表的优点是比较容易找到一个或一组连续的空闲块。因此，位表与任何一种文件分配方法都能很好地工作。另一个优点是它足够的小。
• 空闲区块列表（Free Block List）：在这种方法中，每个区块都被按顺序分配一个号码，所有空闲区块的号码列表被保存在磁盘的一个保留区（reserved block）中。

操作系统中的目录结构 #

目录（directory）是一个容器，用于包含文件夹（folders）和文件。它以分层（hierarchical）的方式组织文件和文件夹。

一个目录有几种逻辑结构，下面给出了这些结构：

单层目录 #

单层目录（Single-level directory）是最简单的目录结构。所有的文件都包含在同一个目录中，这使得它很容易支持和理解。然而，当文件数量增加或系统有一个以上的用户时，单级目录有一个显著的限制。由于所有的文件都在同一个目录中，它们必须有一个唯一的名字。如果两个用户使用了相同的文件名字，那么就违反了唯一的名字规则。

优势：

• 由于它是一个单一的目录，所以它的实现非常容易。
• 如果文件的大小较小，搜索将变得更快。
• 在这样的目录结构中，像文件的创建、搜索、删除、更新等操作都非常容易。

缺点：

• 有可能出现名称冲突，因为两个文件可能有相同的名称。
• 如果目录很大，搜索将变得很费时。
• 它不能将相同类型的文件分组。

双层目录 #

正如我们所看到的，单层目录经常导致不同用户之间文件名称的混淆。这个问题的解决方案是为每个用户创建一个单独的目录。

在双层目录结构（Two-level directory ）中，每个用户都有自己的用户文件目录（UFD，user files directory ）。UFD 有类似的结构，但每个都只列出一个用户的文件。系统的主文件目录（MFD，master file directory）每当有新的用户 id=s 登录时就会被搜索。MFD 是按用户名或帐号索引的，每个条目都指向该用户的 UFD。

优势：

• 我们可以给出完整的路径，如 /用户名/目录名/ 。
• 不同的用户可以拥有相同的目录和文件名。
• 由于路径名和用户分组（user-grouping），文件的搜索变得更容易。

缺点:

• 一个用户不允许与其他用户共享文件。
• 它的可扩展性不强，两个相同类型的文件不能在同一个用户中分组。

树结构目录 #

一旦我们把两级目录看作是高度为 2 的树，自然的概括就是把目录结构扩展为任意高度（arbitrary height）的树。这种泛化允许用户创建他们自己的子目录，并相应地组织他们的文件。

树状结构是最常见的目录结构。树有一个根目录，系统中的每个文件都有一个唯一的路径。

优点：

• 非常普遍，因为可以给出完整的路径名。
• 可扩展性很强，名称碰撞（name collision）的概率较小。
• 搜索变得非常容易，我们既可以使用绝对路径，也可以使用相对路径。

缺点：

• 每个文件都不适合分层模型（hierarchical model），文件可能被保存在多个目录中。
• 我们不能共享文件。
• 它的效率很低，因为访问一个文件可能要经过多个目录。

无环图目录（Acyclic graph directory） #

无环图（acyclic graph）是一个没有环的图，允许我们共享子目录和文件。相同的文件或子目录可能在两个不同的目录中。它是树状结构目录的一个自然扩展。

它被用于像两个程序员在一个联合项目上工作，他们需要访问文件的情况。相关的文件被存储在一个子目录中，将它们与其他项目和其他程序员的文件分开，因为他们在一个联合项目上工作，所以他们希望子目录进入自己的目录。共同的子目录应该是共享的。所以在这里我们使用 Acyclic directories。

需要注意的是，共享文件和复制文件是不一样的。如果任何程序员在子目录中做了一些改变，它将影响到两个子目录。

优势：

• 可以共享文件。
• 由于有不同的路径，搜索起来很容易。

劣势：

• 通过链接（linking）共享文件，如果删除它可能会产生问题。
• 如果链接是一个软链接（soft link），那么在删除文件后，我们就会留下一个悬空的指针（dangling pointer）。
• 在硬链接（hard link）的情况下，要删除一个文件，我们必须删除与之相关的所有引用。

通用图目录（General graph directory） #

在通用图目录结构中，允许在一个目录结构中出现循环（cycles），其中多个目录可以从一个以上的父目录中衍生出来。这种目录结构的主要问题是计算文件和目录所占用的总大小或空间比较复杂。

如果图中允许循环，那么就会出现几个问题：

• 搜索算法可以进入无限循环（infinite loops）。一个解决方案是在搜索算法中不跟随链接。(或者不跟踪符号链接（symbolic links），而只允许符号链接指向目录）。
• 子树可以与树的其他部分断开连接，但它们的引用计数仍然没有减少到零。需要定期的垃圾收集来检测和解决这个问题。(DOS 中的 chkdsk 和 UNIX 中的 fsck 会搜索这些问题，以及其他问题，尽管在这两个系统中循环是不应该被允许的。没有被标记为空闲的磁盘块被重新添加到文件系统中，并使用新的文件名，通常可以安全地被删除。)

优势：

• 它允许循环。
• 它比其他目录结构更灵活。

缺点：

• 它比其他结构的成本高。
• 它需要垃圾收集（garbage collection）。

操作系统中的文件分配方法 #

分配方法定义了文件如何存储在磁盘块中。有三种主要的磁盘空间或文件分配方法：

• 连续分配（Contiguous Allocation）
• 链接分配（Linked Allocation）
• 索引式分配（Indexed Allocation）

这些方法的主要目标是：

• 有效地利用磁盘空间。
• 对文件块的快速访问。

所有这三种方法都有各自的优点和缺点，如下所述。

连续分配 #

在这个方案中，每个文件在磁盘上占用一组连续的块。例如，如果一个文件需要 n 个块，并被赋予一个块 b 作为起始位置，那么分配给文件的块将是： b，b+1，b+2,......b+n-1 。这意味着，给定起始区块地址和文件的长度（以所需区块计算），我们可以确定文件所占用的区块。

一个连续分配的文件的目录实体（directory entry）包括：

• 起始块的地址
• 分配部分的长度

下图中的文件 "邮件" 从 19 号块开始，长度 = 6 个块。因此，它占用了 19、20、21、22、23、24 块。

优势：

• 顺序（Sequential）访问和直接（Direct）访问都被支持。对于直接访问，从 b 块开始的文件的第 k 块的地址可以很容易地得到（b+k）。
• 由于文件块的连续分配，寻道（seeks）的次数很少，所以速度非常快。

缺点：

• 这种方法同时受到内部和外部碎片的影响。这使得它在内存利用方面的效率很低。
• 增加文件大小是很困难的，因为它取决于在一个特定实例中是否有连续的内存。

链接分配 #

在这个方案中，每个文件是一个磁盘块的链表，这些磁盘块不需要是连续的。磁盘块可以散布在磁盘的任何地方。目录条目包含一个指向开始和结束文件块的指针。每个块都包含一个指向该文件所占用的下一个块的指针。

下图中的文件 "jeep" 显示了块是如何随机分布的。最后一个块（25）包含 - 1，表示一个空指针，不指向任何其他块。

优势：

• 这在文件大小方面非常灵活。由于系统不需要寻找连续的内存块，所以文件大小可以很容易地增加。
• 这种方法不受外部碎片的影响。这使得它在内存利用率方面相对更好。

缺点：

• 因为文件块在磁盘上是随机分布的，需要大量的搜索来单独访问每个块。这使得链接分配速度较慢。
• 它不支持随机或直接访问。我们不能直接访问一个文件的块。一个文件的区块 k 可以通过区块指针从文件的起始区块依次遍历 k 个区块来访问（顺序访问）。
• 在链接分配中需要的指针会产生一些额外的开销。

索引分配 #

在这个方案中，一个被称为索引块（Index block）的特殊块包含了一个文件所占用的所有块的指针。每个文件都有自己的索引块。索引块中的第 1 个条目包含第 1 个文件块的磁盘地址。目录条目包含索引块的地址，如图所示。

优势：

• 这支持直接访问文件所占用的块，因此提供了对文件块的快速访问。
• 它克服了外部碎片化的问题。

缺点：

• 索引式分配的指针开销比链接式分配大。
• 对于非常小的文件，例如只扩展了 2-3 个块的文件，索引式分配将为指针保留一整个块（索引块），这在内存利用方面是低效的。然而，在链接分配中，我们失去了每个块只有 1 个指针的空间。对于非常大的文件，单个索引块可能无法容纳所有的指针。

以下机制可以用来解决这个问题：

• 链接方案（Linked scheme）。这种方案将两个或更多的索引块链接在一起，以保存指针。然后，每个索引块将包含一个指针或到下一个索引块的地址。
• 多级索引（Multilevel index）。在这种策略中，第一级索引块用来指向第二级索引块，而第二级索引块又指向文件所占用的磁盘块。这可以扩展到 3 个或更多级别，取决于最大文件大小。
• 组合方案（Combined Scheme）。在这个方案中，一个叫做 Inode（信息节点）的特殊块包含了所有关于文件的信息，如名称、大小、权限等，Inode 的剩余空间用来存储包含实际文件的磁盘块地址，如下图所示。Inode 中的前几个指针指向直接块（direct blocks），即这些指针包含了包含文件数据的磁盘块的地址。接下来的几个指针则指向间接块（indirect blocks）。间接块可以是单间接块、双间接块或三间接块。单间接块（Single Indirect block）是不包含文件数据的磁盘块，但包含文件数据的磁盘块地址。同样，双间接块（double indirect blocks）也不包含文件数据，而是包含含有文件数据的区块地址的磁盘块的磁盘地址。

空闲空间管理 #

系统会对空闲的磁盘块进行跟踪，以便在文件创建时为其分配空间。此外，为了重新利用删除文件所释放的空间，空闲空间管理变得至关重要。系统维护一个空闲空间列表（free space list），跟踪未分配给某些文件或目录的磁盘块。空闲空间列表主要可以实现为：

位图或位向量法（Bitmap or Bit vector） #

位图或位向量是一系列位（bits）的集合，每个位对应一个磁盘块。该位可以取两个值。0 和 1：0 表示该块已被分配，1 表示一个空闲块。图中磁盘上给定的磁盘块实例（其中绿色块被分配）可以用 16 位的位图表示为： 0000111000000110 。

优势：

• 简单易懂。
• 找到第一个空闲块是很有效的。它需要扫描位图中的字（一组 8 位），以寻找一个非零的字。(一个 0 值字的所有位都是 0)。然后通过扫描非零字中的第一个 1 比特来找到第一个空闲块。块数可以计算为：(每个字的位数）*（0 值字的数量）+ 非零字中第一个 1 位的偏移。

链表法（Linked List） #

在这种方法中，空闲的磁盘块被链接在一起，即一个空闲块包含一个指向下一个空闲块的指针。第一个磁盘区块的区块号被存储在磁盘上的一个单独位置，同时也被缓存在内存中。

在图中，空闲空间列表的头部指向第 5 块，第 5 块指向第 6 块，即下一个空闲块，以此类推。最后一个空闲块将包含一个空指针，表示空闲列表的结束。

这种方法的一个缺点是空闲空间列表遍历需要 I/O 成本。

分组法（Grouping） #

这种方法将空闲块的地址存储在第一个空闲块中。第一个空闲区块存储了所有，例如 n 个空闲块的地址。在这 n 个块中，前 n-1 个块实际上是空闲的，最后一个块包含下一批空闲的 n 个块的地址。

这种方法的一个优点是可以很容易地找到一组空闲磁盘块的地址。

计数法（Counting） #

这种方法存储了第一个空闲磁盘块的地址，以及在第一个磁盘块之后的 n 个空闲磁盘块。列表中的每个条目都会包含：第一个空闲磁盘块的地址、一个数字 n。