文件系统基础

基本概念

数据项

文件系统中最低级的数据组织形式，可分为两种类型：

  1. 基本数据项

    用于描述一个对象某种属性的一个值。

    数据中可命名的最小逻辑数据单位（原子数据）。

  2. 组合数据项

    由多个基本数据项组成。

记录

一组相关的数据项的集合，用于描述一个对象在某方面的一系列属性。

文件

由创建者所定义的、具有文件名的一组相关元素的集合。

在用户进行的输入、输出中，以文件为基本单位。

文件的组成：数据、分类和索引的信息、关于访问权限的信息。

文件逻辑上可分为：

  1. 有结构文件/记录式文件

    文件由若干个相似的记录组成。

  2. 无结构文件/流式文件

    被视为一个字符流，比如一个二进制文件或字符文件。

虽然上面给出了结构化的表述，但实际上并无严格的定义。在操作系统中，通常将程序和数据组织成文件。文件可以是数字、字符或二进制代码，基本访问单元可以是字节或记录。

文件是以硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。文件可以长期存储在硬盘中，允许可控制的进程间共享访问，能够被组织成复杂的结构。

文件实际上是一种抽象数据类型，我们要研究它的逻辑结构、物理结构，以及关于它的一系列操作。

文件的属性

除了文件数据，操作系统还会保存与文件相关的信息，如所有人、创建时间等，这些附加信息称为文件属性或文件元数据。

文件属性在不同系统中差别很大，但通常都包括如下属性：

  • 名称。文件名称唯一，以容易读取的形式保存。
  • 标识符。对用户不可读。
  • 类型。被支持不同类型的的文件系统所使用。
  • 创建者。文件创建者的 ID。
  • 所有者。文件当前所有者的 ID。
  • 位置。指向设备和设备上文件的指针。
  • 大小。文件当前大小（用字节、字或块表示），也可包含文件允许的最大值。
  • 保护。对文件进行保护的访问控制信息。
  • 创建时间、最后一次修改时间、最后一次存取时间。文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。

操作系统通过文件控制块 FCB 来维护文件元数据。

文件的分类

下面是几种常见的文件分类方法：

  • 按性质和用途分类

    系统文件、用户文件、库文件。

  • 按文件中数据的形式分类

    源文件、目标文件、可执行文件。

  • 按存取控制属性分类

    可执行文件、只读文件、读/写文件。

  • 按组织形式和处理方式分类

    普通文件、目录文件、特殊文件。

特指系统中的各类 I/O 设备。为了便于统一管理，系统将所有的 I/O 设备都视为文件，并按文件方式提供给用户使用，如目录的检索、权限的验证等都与普通文件相似，只是对这些文件的操作将由设备驱动程序来完成。

文件管理系统

操作系统中负责管理和存储文件信息的软件机构。

由三部分组成：

  1. 与文件管理有关的软件
  2. 被管理文件
  3. 实施文件管理所需的数据结构

文件控制块和索引节点

文件控制块 FCB

用于存放控制文件需要的各种信息的数据结构，以实现 “按名存取”。

FCB 主要包含以下内容：

  1. 基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
  2. 存取控制信息：包括文件主的存取权限、核准用户的存取权限、一般用户的存取权限。
  3. 使用信息：文件建立时间、上次修改时间等。

FCB 的有序集合称为文件目录，一个 FCB 就是一个文件目录项。

通常，一个文件目录也被视为一个文件，称为目录文件。

索引节点

文件目录通常存放在磁盘，当文件很多时，文件目录会占用大量的盘块。检索目录要先将存放目录文件的第一个盘块中的目录调入内存，然后用给定的文件名逐一比较，若未找到指定文件，就还需要不断地将下一盘块中的目录项调入内存，逐一比较。

在检索过程只用到了文件名，仅当找到一个目录项（其中的文件名与要查找的文件名匹配）时，才需从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也没必要一起调入内存。

因此有的文件系统（如 UFS）便采用文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引节点的数据结构，简称 i 结点(inode)。这样文件目录项仅由文件名和相应的索引节点号（或 inode 的指针）构成。

UFS，即 Unix 文件系统 (Unix File System)，一种为 Unix 和许多类 Unix 操作系统所使用的文件系统。

FCB 变小，一个盘块就能存放更多的 FCB，从而使得查找文件的平均启动磁盘次数减少，节省了系统开销。

FAT 文件系统没有采用索引节点。

磁盘索引节点

存放在磁盘上的索引节点。每个文件都有一个唯一的磁盘索引节点。

主要内容：

  • 文件主标识符

    拥有该文件的个人或小组的标识符。

  • 文件类型

    普通文件、目录文件、特别文件。

  • 文件存取权限

    各类用户对该文件的存取权限。

  • 文件物理地址

    含 13 个地址项 iaddr(0) ~ iaddr(12)，以直接或间接方式给出数据文件所在盘块的编号（Unix）。

  • 文件长度

    单位字节。

  • 文件链接计数 / 引用计数

    在本文件系统中所有指向该文件的文件名的指针计数。

    在基于索引节点的共享方式（硬链接）中，用于表示链接到本索引节点上的用户目录项的数目。

    引用计数减为 0 时会删除该文件。

  • 文件存取时间

    最近被进程存取的时间、最近被修改的时间、索引节点最近被修改的时间。

内存索引节点

存放在内存中的索引节点。

文件被打开时要将磁盘索引节点复制到内存索引节点，便于以后使用。

在内存索引节点中增加了以下内容：

  • 索引节点编号

    用于标识内存索引节点。

  • 状态

    指示 inode 是否上锁或被修改。

  • 访问计数 / 打开计数

    正在访问此 inode 的进程数。

    每当有一进程要访问此 inode 时，计数加 1；访问结束计数减 1。减为 0 时会 close 该文件。

  • 逻辑设备号

    文件所属文件系统的逻辑设备号。

  • 链接指针

    设置分别指向空闲链表（大概是指向下一个空闲 inode）和散列队列（大概是指向下一个散列到同一地址的 inode）的指针。

文件操作

文件基本操作

文件属于抽象数据类型。为了正确地定义文件，需要考虑可以对文件执行的操作。

操作系统提供一系列的系统调用，实现对文件的创建、删除、读、写等操作。

创建文件

两个必要步骤：

  1. 为新文件分配必要的外存空间。
  2. 在目录中为新文件创建一个目录项，记录新文件名称、在外存中的地址及其他可能的信息。

删除文件

根据文件名查找目录，删除指定文件对应的目录项，然后回收该文件所占的存储空间（包括磁盘空间和内存缓冲区）。

目录项的删除通常是逻辑删除，使之成为空闲目录项。

读文件

根据文件名查找目录，找到指定文件的目录项后，从中得到被读文件在外存中的地址。

系统维护一个读位置的指针（在打开文件表中），每当发生读操作时更新读指针。

写文件

根据文件名查找目录，找到指定文件的目录项后，再利用目录中的写指针对文件进行写操作。

系统必须为该文件维护一个写位置的指针（在目录项中），每当发生写操作时更新写指针。

读和写操作可使用同一个指针，节省空间，降低系统复杂度。

文件的打开与关闭

文件的 “打开”

使用系统调用 open “打开” 文件：系统根据文件名搜索目录，将指明文件的属性（包括该文件在外存上的物理位置），从外存复制到内存打开文件表(file-open table)的一个表目中（如果采用了索引节点，则是从磁盘 inode 复制到内存 inode），并将该表目的编号（或称为索引号、文件描述符）返回给用户。当用户再次向系统发出文件操作请求时，可通过该索引在打开文件表中查到文件信息，从而节省再次搜索目录的开销。

许多文件操作都需要从检索目录开始。为了避免多次重复地检索目录，当用户第一次请求对某文件进行操作时，都会先 open 文件（大多数 OS 要求文件在使用前就要被显式 open）。open 完成以后再对该文件的任何操作，用户就只需提供索引，或者说系统只需使用索引。也就是说，⚠只有 open 使用的是文件名，其他文件操作使用的都是 open 返回的索引。

在多个不同进程可以同时打开文件的操作系统中，通常采用两级表：

  1. 整个系统的打开文件表

    每个表项即为外存 FCB 在内存中的副本以及其他信息。

    若是采用了索引节点的文件系统，则可以仅把已打开文件的目录项视为系统打开文件表项，每个表项关联一个内存索引节点。

  2. 每个进程的打开文件表

    包含指向系统表中合适条目的指针以及进程对文件的使用信息，如文件的当前读写指针、文件访问权限。

文件名不必是打开文件表的一部分，因为一旦完成对 FCB 在磁盘上的定位，系统就不再使用文件名。再次强调，对于进程而言，只要完成了文件打开 open() 系统调用，后面再使用 read()、write()、Lseek()、close() 等文件操作的系统调用，就不再使用文件名，而使用文件描述符。

对于访问（进程）打开文件表的索引，UNIX 称之为文件描述符 fd (file description)，Windows 称之为文件句柄(file handle)。因此，只要文件未被关闭，所有文件操作都是通过文件描述符来进行。

Windows 中的句柄逻辑上类似于 “指针的指针”。

通常系统打开文件表为每个打开文件关联一个文件打开计数器(open count)，以记录有多少进程打开了该文件（即位于内存索引节点的访问计数）。open 加一，close 减一。一旦有进程打开了一个文件，系统表就包含该文件的条目，当另一个进程执行系统调用 open 时，只不过是在其打开文件表中增加一个条目，并指向系统表的相应条目，以及系统表相应打开计数器 +1。

基于采用 inode 的文件系统的文件打开过程的描述

① 检索目录，要求打开的文件应是已创建的文件，它应登记在文件目录中，否则会出错。在检索到指定文件后，就将其磁盘 inode 复制到活动 inode 表中。
② 将参数 mode 所给出的打开方式与活动 inode 中在创建文件时所记录的文件访问权限相比较，如果合法，则此次打开操作成功。
③ 当打开合法时，为文件分配用户打开文件表表项和系统打开文件表表项，并为后者设置初值，通过指针建立表项与活动 inode 之间的联系，再将文件描述符 fd 返回给调用者。

文件的 “关闭”

使用系统调用 close “关闭” 文件，终止索引与其对应文件的联系：删除该进程的打开文件表中的相应条目，系统中的相应打开计数器 -1。当打开计数器为 0 时，表示该文件不再被使用，系统将回收分配给其的资源，从系统打开文件表中删除相应条目，并且任何更新的元数据将复制到磁盘的目录结构中。

打开文件的关联信息

每个打开文件都具有如下关联信息：

  1. 文件指针（进程打开文件表）

    系统跟踪上次的读写位置作为当前文件位置的指针。

    对打开文件的某个进程而言是唯一的，因此必须与磁盘文件属性分开保存。

  2. 文件打开计数（系统打开文件表/内存索引节点）

  3. 文件磁盘位置（系统打开文件表/内存索引节点）

  4. 访问权限（进程打开文件表）

    每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等）。该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的 I/O 请求。

Linux 系统中的打开文件表

文件描述符是一个较小的非负整数，并且 0、1、2 三个描述符总是默认分配给标准输入、标准输出和标准错误。

每个进程会在其 PCB⚠ 内维护属于自己的文件描述符表(file descriptor table)。表中每个条目包含两个域：一是控制该描述符的标记域(flags)，二是指向打开文件表中对应条目的指针。

文件描述符表、打开文件表、inode 表之间的关系可以用下图来表示（图中的 fd 0、1、2…表示下标，不代表三个标准描述符）。

进程 A 的 fd1 和 fd20 指向同一个打开文件句柄，很可能是通过调用 dup() 系列函数形成的。

进程 A 的 fd2 和进程 B 的 fd2 指向同一个打开文件句柄，可能是由于调用 fork() 后出现的（即 A 、B 是父子进程关系），属于文件的动态共享。

进程 A 的 fd0 和进程 B 的 fd3 分别指向不同的打开文件表项，但这些表项均指向 i-node 表的同一个条目（下标为 1976）。换言之，它们指向了同一个文件。发生这种情况是因为每个进程各自对同一个文件发起了 open() 调用。同一个进程两次打开同一个文件，也会发生类似情况。

上图打开文件表虽然是系统范围的，但实际上是所有进程共同使用的一张进程打开文件表。右边的内存索引节点表可以视为系统打开文件表。

Linux 中 task_struct 和文件系统的关系

一个进程本身的文件位置由 fs_struct 描述，进程的打开文件表/文件描述符表由 files_struct 描述，文件由 file 描述，系统的打开文件表项或者说目录项由 dentry (directory entry) 描述，dentry 包含指向对应 inode 的指针。搭配后面虚拟文件系统知识点食用风味更佳。

fs_struct 中的 root 所指向的 dentry 结构代表着本进程所在的根目录， 也就是在用户登录进入系统时所看到的根目录；pwd 指向进程当前所在的目录；另外还有 altroot 是为用户设置的替换根目录。实际运行时，这三个目录不一定都在同一个文件系统中。例如，进程的根目录通常是安装于 “/” 节点上的 Ext2 文件系统，而当前工作目录可能是安装于 /msdos 的一个 DOS 文件系统。

open 系统调用打开文件的背后过程 / 文件系统在内存中的结构

下图描述的 open 过程使用了目录项缓存，用于对文件目录结构的加速访问，还可以省去每次 open 文件都重新访问元数据服务的开销，减少对块设备的 I/O 操作。缺点就是需要多一次的内存复制，以及需要解决数据一致性问题。

其他操作

实际上，一般的 OS 都提供了更多对文件操作的系统调用。

其中最常用的一类是有关对文件属性的操作，即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有者（文件主）、改变对文件的访问权，以及查询文件的状态（包括文件类型、大小和拥有者以及对文件的访问权等）。

另一类是有关目录的操作，如创建一个目录、删除一个目录、改变当前目录和工作目录等。

此外，还有用于实现文件共享的系统调用，以及用于对文件系统进行操作的系统调用等。

重新定位文件/文件定位

搜索目录以找到适当的条目，并将进程当前文件位置指针重新定位到给定值。

重新定位文件不涉及读写文件。

截断文件

只删除文件内容，将其长度置为 0 后并释放其空间。

文件保护

防止多用户间的文件共享可能会导致的文件被破坏或非法访问，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。

文件保护通过访问控制、口令保护、加密保护等方式实现。其中，口令、加密是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。

对于多级目录结构而言，不仅需要保护单个文件，还需要保护子目录内的文件，即需要提供目录保护机制。目录操作与文件操作并不相同，因此需要不同的保护机制，这里不作讨论。

访问类型

可加以控制的访问类型主要有：

  • 读

  • 写

  • 执行（装入内存并执行）

  • 添加（将新信息添加到文件结尾部分）

  • 列表清单（列出文件名和文件属性）

此外，重命名、复制、编辑等高层功能可以通过系统程序调用底层系统调用来实现，所以保护可以只在上述的底层操作提供。例如，复制文件可利用一系列的读请求来完成，这样具有读访问权限的用户同时也就具有了复制和打印权限。

访问控制

解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是，为每个文件和目录增加一个访问控制列表，以规定每个用户名及其所允许的访问类型。这种方法的优点是可以使用复杂的访问方法，缺点是长度无法预计并且可能导致复杂的空间管理，使用精简的访问列表可以解决这个问题。

访问权

对某对象具有的访问类型集合。

保护域

对一组对象访问权的集合，简称 “域”。

进程和域之间的联系

  1. 静态联系

    进程和域之间一一对应，即在进程的整个生命周期中，其可用资源是固定的。

  2. 动态联系

    进程和域之间是一对多的关系。进程的运行分为若干个阶段，每个阶段联系着一个域

访问矩阵

描述系统的访问控制的矩阵，行代表域，列代表对象（即文件）。

访问控制列表 ACL (Access Control List)

访问矩阵按列（对象）划分，为每一列建立一张访问控制表。

访问控制表的行数即域的数量，按前面的描述，一个进程就有可能对应一个或多个域，这使得访问控制列表长度无法预计并且可能导致复杂的空间管理。

精简的访问列表采用拥有者、组、其他三种用户类型（域）：

  1. 拥有者（创建文件的用户）

  2. 组（一组需要共享文件且具有类似访问的用户）

  3. 其他（系统内的所有其他用户）

上图是一个访问控制表的实例，每项占用一个二进制位，这样只需用 3×4 位的矩阵即可描述这三类用户的访问权限。在创建文件时，系统将文件主的用户名、所属组名列在该文件的 FCB 中。用户访问该文件时，若用户是文件主，按照文件主所拥有的权限访问文件；若用户和文件主在同一个用户组，则按照同组权限访问，否则只能按其他用户权限访问。

访问权限表

访问矩阵按行（域）划分，便可由每一行构成一张访问权限表，即一个域对每一个对象具有的访问类型所构成的一张表。

现代操作系统常用的保护方法是，将访问控制列表与访问权限表一起组合使用。换言之，对一个文件的访问，常由文件属性（控制信息）和用户访问权限共同限制。

口令保护

用户在创建文件时提供口令，系统为其建立 FCB 时附上相应口令，同时告诉允许访问该文件的其他用户。用户请求访问时必须提供相应的口令。

这种方法时间和空间的开销不多，缺点是口令直接存在系统内部，不够安全。

加密保护

用户对文件进行加密，文件被访问时需要使用密钥。

这种方法保密性强，节省了存储空间，但编码和译码需要花费一定时间。

👊访问控制 vs 加密

相对于加密保护机制，访问控制机制的安全性较差，访问控制的级别和保护力度较小，不过灵活性相对较高。

访问控制机制必须由系统实现，加密保护机制必须由用户实现。若访问控制不由系统实现，则系统本身的安全性就无法保证。加密机制若由系统实现，则加密方法将无法拓展。

文件逻辑结构

文件的逻辑结构是指从用户观点出发看到的文件的组织形式。

文件的逻辑结构与存储介质无关，它实际是指在文件内部，数据在逻辑上是如何组织起来的，组织形式取决于用户需求。

文件的物理结构（又称存储结构）是指将文件存储在外存上的存储组织形式，是用户所看不见的。

按逻辑结构，文件可划分为无结构文件和有结构文件两大类。

无结构文件（流式文件）

最简单的文件组织形式。

将数据按顺序组织成记录并累积、保存。

是有序相关信息项的集合，以字节为单位。

对流式文件的访问，是通过读/写指针来指出下一个要访问的字节的。

由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，因此这种文件形式对大多数应用不适用。

可以把流式文件看作是记录式文件的一个特例：一个记录仅有一个字节。

在系统中运行的大量源程序、可执行文件、库函数等，所采用的就是无结构文件。

有结构文件（记录式文件）

有结构文件是指由一个以上的记录构成的文件，所以又称记录式文件。

在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。

根据各记录的长度是否相等，可分为定长记录和变长记录两种：

  • 定长记录

    文件中所有记录的长度都是相同的，各数据项都在记录中的相同位置，具有相同的长度。

    检索记录的速度快，方便用户对文件进行处理，广泛应用于数据处理中。

  • 变长记录

    文件中各记录的长度不一定相同，原因可能是记录中所包含的数据项数目不同，也可能是数据项本身的长度不定。

    检索记录只能顺序查找，速度慢。

有结构文件按记录的组织形式可分为三类：

  • 顺序文件

    由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长记录或可变长记录。

  • 索引文件

    为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。

  • 索引顺序文件

    顺序文件和索引文件相结合的产物、为每个文件建立一张索引表时，并不是为每一个记录建立一个索引表项，而是为一组记录中的第一个记录建立一个索引表项。

顺序文件

记录顺序排列。记录可以是定长记录或变长记录。

顺序文件中记录的排列有两种结构：

  1. 串结构：记录顺序与关键字无关，通常按存入的先后时间排，检索时必须从头开始顺序依次查找，比较费时。

  2. 顺序结构：所有记录按关键字顺序排列。对于定长记录的顺序文件，检索时可采用折半查找，效率较高。

顺序文件批量操作记录的效率是所有逻辑文件中最高的。

对于顺序存储设备（如磁带），也只有顺序文件才能被存储并能有效地工作。

对单条记录增删改查的性能比较差，如果顺序文件中是可变长记录，则需付出的开销将更大。

为解决增删改记录困难的问题，可以为顺序文件配置一个运行记录文件(Log File)或称为事务文件(Transaction File)，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间（例如 4 小时），将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。

索引文件

为变长记录⚠顺序文件建立一张索引表，每个记录在索引表中分别设置一个索引表项（按关键字建立索引），表项包含指向记录的指针（逻辑起始地址⚠）和记录长度。

索引表按关键字排序，因此其本身也是一个定长记录的顺序结构的顺序文件⚠。​

由于是按关键字建立的索引，所以在对索引文件进行检索时，可以根据用户（程序）提供的关键字利用折半查找法去检索索引表，从中找到相应的表项。再利用该表项中给出的指向记录的指针值去访问所需的记录。

把对变长记录顺序文件的顺序检索转变成为对定长记录索引文件的随机检索，从而加快了记录的检索速度，实现直接存取。

索引文件由于需要配置索引表，且每个记录都要有一个索引项，因此增加了存储开销。另外每当在索引文件中增删记录时，还须对索引表进行相应修改。

索引顺序文件

索引顺序文件是对顺序文件的一种改进，它基本上克服了变长记录的顺序文件不能随机访问，以及不便于记录的删除和插入的缺点。但它仍保留了顺序文件的关键特征，即记录是按关键字的顺序组织起来的。它又增加了两个新特征：一个是引入了文件索引表，通过该表可以实现对索引顺序文件的随机访问； 另一个是增加了 溢出(overflow)文件，用它来记录新增加的、删除的和修改的记录。可见，索引顺序文件是顺序文件和索引文件相结合的产物，能有效地克服变长记录文件的缺点，而且所付出的代价也不算太大。

最简单的索引顺序文件只使用了一级索引，先将变长记录顺序文件中的所有记录分为若干组，在索引表中为每组的第一条记录建立一个索引项，其中包含该记录的关键字和指向该记录的指针。

主文件中记录要分组排列，组内关键字可以无需无序，但组间关键字必须有序。检索时，先顺序查找索引表，找该记录所在的组，然后在该组中顺序查找。

这种方式就是数据结构中的分块查找。故最好情况是，$n$ 条记录分为 $\sqrt{n}$ 组，每组 $\sqrt{n}$ 条记录，组内和组间均采用顺序查找时 ASL = $\sqrt{n}$（常忽略 + 1）。

在操作系统教材中，顺序查找的平均查找长度通常描述为 “总长度/2”；而在数据结构教材中，平均查找长度通常描述为 “(1+总长度)/2”。相对而言后者更为严谨。

若记录数很多，则可采用两级或多级索引。

索引文件和索引顺序文件都提高了查找速度，但都因配置索引表而增加了存储空间。

直接文件或散列文件 Hash File

采用前述几种文件结构对记录进行存取时，都须利用给定的记录键值，先对线性表或链表进行检索，以找到指定记录的物理地址。然而对于直接文件，则可根据给定的关键字直接获得指定记录的物理地址。换而言之，关键字本身就决定了记录的物理地址。这种由关键字到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直接文件的关键在于用什么方法进行从记录值到物理地址的转换。

哈希文件是目前应用最为广泛的一种直接文件。它利用 Hash 函数（或称散列函数）可将关键字转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由 Hash 函数所求得的并非是相应记录的地址，而是指向某一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。通常把 Hash 函数作为标准函数存于系统中，供存取文件时调用。

文件物理结构

文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。

可以从两方面回答：

  1. 文件的分配方式——对磁盘非空闲块的管理
  2. 文件存储空间管理——对磁盘空闲块的管理

常用的文件分配方式有三种：连续分配、链接分配、索引分配（注意与文件的逻辑结构区分）。有的系统（如 RDOS）对三种方法都支持，但更普遍的是一个系统只支持一种方法。

类似于内存分页，磁盘中的存储单元也被分为一个个的块，称为磁盘块，其大小通常与内存的页面大小相同。内存与磁盘之间的数据交换（磁盘 I/O）都是以块为单位进行的。

连续分配

每个文件在磁盘上占有一组连续的块。

磁盘地址定义了磁盘上的一个线性排序，这种排序使进程访问磁盘时需要的寻道数和寻道时间最小。

采用连续分配时，逻辑文件中的记录也顺序存储在相邻的物理块中。

一个文件的目录项中（“文件物理地址” 字段）应包括起始块地址和所分配的块数。

优点：

  • 支持顺序访问和随机访问。
  • 顺序访问容易且速度快，文件所占用的块可能位于一条或几条相邻的磁道上，磁头的移动距离小。

缺点：

  • 必须事先知道文件的长度（块数），无法满足文件动态增长的要求，否则会覆盖物理上相邻的后续文件。

  • 不能灵活地增删记录（顺序存储的通病，另外还可能改变文件长度），为保持文件的有序性，增删记录时需要对相邻的记录做物理上的移动。

  • 与内存分配类似，为文件分配连续的存储空间会产生很多外部碎片。

很难确定一个文件需要的空间大小，因而连续分配只适用于长度固定的文件。

链接分配

链接分配是一种采用离散分配的方式。

链式分配的优点：

  • 消除了磁盘外部碎片，提高了磁盘利用率。
  • 便于动态地为文件分配盘块，因此无须事先知道文件的大小。
  • 对文件的增删改也非常方便。

链接分配可分为隐式链接、显式链接两种形式。

隐式链接

每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方。用于链接盘块的指针隐式地放在每个盘块中（最后一个盘块除外），这些指针对用户透明。

目录项中含有文件第一块的指针（盘块号）和最后一块的指针。

缺点：

  • 只能从第一块开始顺序访问。

  • 盘块指针会消耗一定的存储空间。

  • 不够稳定，文件盘块中任何一个指针丢失或损坏都会导致文件数据的丢失。

为提高查找速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)，按簇而不按盘块分配，可以大幅减少查找时间，也可以改善许多算法的磁盘访问时间。指针所占的磁盘空间比例也要小得多。代价是增加了内部碎片。

显式链接

用于链接文件各物理块的指针显式存放在内存的一张链接表中，每个表项存放指向下一个盘块的指针。

整个磁盘仅设置一张链接表，称为文件分配表 FAT (File Allocation Table)。FAT 在系统启动时就会被读入内存⚠。

目录项（FCB）的物理地址字段只需记录该文件的起始块号，后续块号可通过查 FAT 找到。

FAT 表项与全部磁盘块一一对应，并用一个特殊的数字 -1 表示文件的最后一块。

FAT 不仅记录文件各块之间的先后链接关系，同时还能标记空闲的磁盘块（上图用 -2 表示），因此操作系统可以通过 FAT 对磁盘空闲磁盘空间进行管理。

优点：

  • 支持顺序访问，也支持直接访问（即要访问第 i 块，无须依次访问前 i - 1 块）。
  • FAT 在系统启动时就被读入内存，检索记录只需在内存中进行，因而不仅显著提高了检索速度，而且明显减少了访盘次数。

缺点：

  • FAT 需要占用一定的内存空间。
  • 可靠性差，任何一个盘块的指针错误会导致后面盘块的位置丢失。

采用连续分配和索引分配都支持随机存取，采用链接分配的文件不支持随机存取。

索引分配

单级索引分配

打开某文件时，只需要将该文件对应盘块的编号调入内存即可，没必要将整个 FAT 调入内存。

索引分配为每个文件分配一个索引块（表），将分配给该文件的所有盘块号都记录在该索引块中。当访问到某个文件时，将该文件对应的索引块一起调入内存。

索引块是一个盘块地址的数组，其第 i 个条目指向文件的第 i 个块。

索引块自身的盘块号记录在目录项（PCB）中。

优点：

  • 支持随机访问。当要访问第 i 块时，索引块的第 i 个条目指向的便是文件的第 i 块。
  • 不会产生外部碎片。

缺点：索引块增加了额外的存储空间开销。

由于每个文件都有一个索引块，因此索引块应尽可能小，同时提高小文件索引块的利用率；但太小就无法支持大文件。可采用链接方案将多个索引块链接起来，目录项记录索引块起始盘块号，但这种方案是低效的。还可以采用多级索引分配或混合索引分配。

多级索引分配

可根据文件大小调整级数，目录项记录顶级索引块盘块号。

优点：极大加快了对大型文件的查找速度。

缺点：当访问一个盘块时，其所要启动磁盘的次数随着索引级数的增加而增多，即使是对数量众多的小文件也是如此。

如果在文件系统中仅采用了多级索引组织方式，那么并不能获得理想的效果。

混合索引分配

能较全面地照顾到小型、中型、大型和特大型文件。

UNIX 系统采用的就是混合索引分块，在其 inode 中，共设有 13 个地址项：i.addr(0)~i.addr(12)。

  • 直接地址 i.addr(0) ~ i.addr(9)

    存放直接地址，即文件数据盘块的盘块号。

  • 一次间接地址 i.addr(10)

    实质是一级索引分配方式，一级间址块就是索引块，其中记录了文件数据块的盘块号。

  • 多次间接地址

    二次间接地址 i.addr(11)，二级索引分配方式。

    三次间接地址 i.addr(12)，三级索引分配方式。

👯逻辑结构与物理结构

文件结构包括逻辑结构和物理结构。逻辑结构是用户组织数据的结构形式，数据组织形式来自用户需求，而物理结构是操作系统组织物理存储块的组织形式。

因此说，逻辑文件的组织形式取决于用户，物理结构的选择取决于文件系统设计者针对硬件结构所采取的策略。

单个文件的逻辑结构和物理结构之间虽无明显的制约或关联关系，但是如果物理结构选择不慎，也很难体现出逻辑结构的特点。比如一个逻辑结构是顺序结构，而物理结构是隐式链接结构的文件，即使理论上可以很快找出某条记录的地址，而实际上仍需在磁盘上一块一块地找。又比如，磁带是一种顺序存储设备，用它存储文件时只能采用顺序存储结构（不过若允许磁带来回倒带，也可组织为其他文件形式）。

文件的逻辑结构和物理结构都有索引的概念，但引入逻辑索引和物理索引的目的是截然不同的。逻辑索引的目的是加快文件数据的定位，是从用户角度出发的，而物理索引的主要目的是管理不连续的物理块，是从系统管理的角度出发的。一般说索引表是指逻辑结构，索引块是指物理结构⚠。

记录成组技术

指将若干逻辑记录存入一个盘块，一个逻辑记录不能跨越两个盘块。

目录

目录管理的基本要求：

  1. 文件名和文件之间提供一种映射，实现 “按名存取”（用户/应用程序角度）。
  2. 目录存取的速度直接影响到系统性能，所以目录检索速度要快（系统角度）。
  3. 允许多用户共享一个文件，因此需要提供用于控制访问文件的信息（多用户系统角度）。
  4. 允许不同用户对不同文件采用相同的名字（用户/应用程序角度）。

目录操作

  • 搜索（目录项）

  • 创建文件（文件目录项）

  • 删除文件（文件目录项）

  • 创建目录（目录文件）

    在树形目录结构中，用户可创建自己的用户文件目录，并可再创建子目录。

  • 删除目录（目录文件）

    有两种方式：

    1）不删除非空目录，删除时要先删除目录中的所有文件，并递归地删除子目录。

    2）可删除非空目录，目录中的文件和子目录同时被删除。

  • 移动目录（文件目录项）

    将文件或子目录在不同的父目录之间移动，文件的路径名也会随之改变。

  • 修改目录（文件目录项）

    某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。

  • 显示目录（目录文件）

    用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性。

目录结构

单级目录

在整个文件系统中只建立一张目录表，每个文件占一个目录项。

当建立一个新文件时，必须先检索所有目录项，以确保没有 “重名” 的情况，然后在该目录中增设一项，将新文件的属性信息填入该项。当访问一个文件时，先按文件名在该目录中查找到相应的 FCB，经合法性检查后执行相应的操作。当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后清除该目录项。

评价：实现了 “按名存取”，但是存在查找速度慢（暴力遍历）、文件不允许重名、不便于文件共享等缺点，不适用于多用户操作系统。

两级目录结构

将文件目录分为主文件目录 MFD (Master File Directory) 和用户文件目录 UFD (User File Directory) 两级：

主文件目录项记录用户名及相应用户文件目录所在的存储位置，用户文件目录记录该用户所有文件的 FCB。

当某用户欲对其文件进行访问时，只需搜索该用户对应的 UFD。

优点：既解决了不同用户文件的 “重名” 问题，又在一定程度上保证了文件的安全，可以在目录上实现访问控制，同时也提高了检索的速度。

缺点：缺乏灵活性，不能对文件进行分类，共享不方便。

树形目录结构

将两级文件目录加以推广，就形成了树形目录结构。

用文件的路径名标识文件。文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符 “/” 链接而成。

方框代表目录文件，圆圈代表数据文件。

绝对路径：从根目录出发的路径。系统中的每个文件都有唯一的绝对路径名。

当前目录(Current Directory)：由于一个进程在运行时，其所访问的文件大多局限于某个范围，当层次较多时，每次从根目录查询会浪费时间，于是可为每个进程设置一个当前目录（又称工作目录），此时进程对各文件的访问都只需相对于当前目录而进行。

相对路径：从当前目录出发的路径。

如 “/dev/hda” 就是一个绝对路径。若当前目录为 “/dev”，则 “./hda” 就是 “/dev/hda” 对应的相对路径，其中符号 “.” 表示当前目录。

通常每个用户都有各自的 “当前目录”，登录后自动进入该用户的默认 “当前目录”。操作系统提供一条专门的系统调用，供用户随时改变 “当前目录”（cd 命令）。

优点：查询速度更快，结构层次更加清晰，便于实现文件分类，能够更加有效地进行文件的管理和保护。在树形目录中，不同性质、不同用户的文件，可以分别呈现在系统目录树的不同层次或不同子树中，很容易地赋予不同的存取权限。

缺点：查找文件时需按路径名逐级访问中间结点，增加了磁盘访问次数，影响查询速度；仍不便于实现文件共享。

目前，大多数操作系统如 UNIX、Linux 和 Windows 系统都采用了树形文件目录。

无环图目录结构

树形目录结构能便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。

这种结构允许目录共享子目录或文件，同一个文件或子目录可以出现在两个或多个目录中，即允许一个文件可以有多个父目录。

当某用户要求删除一个共享节点时，若系统只是简单地将它删除，则当另一共享用户需要访问时，会因无法找到这个文件而发生错误。为此，可为每个共享节点设置一个共享计数器，每当图中增加对该节点的共享链时，计数器加 1；每当某用户提出删除该节点时，计数器减 1。仅当共享计数器为 0 时才真正删除该结点，否则仅删除请求用户的共享链。

共享文件不同于文件拷贝，它只存在一个真正的文件，任何改变都会为其他用户所见。

无环图目录结构方便地实现了文件共享，但使得系统的管理变得更加复杂。

目录实现

个人理解：上一节 “目录结构” 着眼于整个文件系统目录的逻辑组织形式，本节则是讨论单个目录文件的数据结构（即目录文件中目录项的逻辑组织形式）及其对应的查找方法。

在访问一个文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。

线性列表

最简单的目录实现方法是，采用文件名和数据块指针的线性列表。

当创建新文件时，必须首先搜索目录以确定没有同名的文件存在，然后在目录中增加一个新的目录项；当删除文件时，则根据给定的文件名搜索目录，删除对应目录项，然后释放分配给它的空间。

前面说过目录项的删除通常是逻辑删除。逻辑删除或者说重用目录项有许多种方法：可以将目录项标记为不再使用，或将它加到空闲目录项的列表上。如在 FAT 文件系统中，在文件被删除后，它所对应的目录项的第一个字节会被置为 0xE5，表明目录项空闲和未使用（这就是为什么有的 FAT 数据恢复工具需要用户自己输入文件名的第一个字符的原因）。

若是物理删除目录项，则用链表结构可减少删除文件的时间。

线性列表的优点在于实现简单，不过由于线性表的特殊性，查找比较费时。

可以使用目录项缓存来快速访问此前的查找操作的结果（同时还能减少 I/O 操作），也可以将目录最后一个目录项复制到空闲位置并减少目录长度等。

线性检索法/顺序检索法

其查找过程说明如下：

首先，系统应先读入第一个文件分量名 usr，用它与根目录文件中各目录项中的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引节点号 6，再从 6 号索引节点中得知 usr 目录文件放在 132 号盘块中，将该盘块内容读入内存。

其次，系统再将路径名中的第二个分量名 ast 读入，用它与放在 132 号盘块中的第二级目录文件中各目录项的文件名顺序进行比较，又找到匹配项，从中得到 ast 的目录文件放在 26 号索引节点中，再从 26 号索引节点中得知 /usr/ast 存放在 496 号盘块中，再读入 496 号盘块。

然后，系统又将该文件的第三分量名 mbox 读入，用它与第三级目录文件 /usr/ast 中各目录项中的文件名进行比较，最后得到 /usr/ast/mbox 的索引节点号为 60 ，即在 60 号索引节点中存放了指定文件的物理地址。目录查询操作到此结束。

如果在顺序查找过程中，发现有一个文件分量名未能找到，则应停止查找，并返回 “文件未找到” 信息。

若将文件名按序排列，则使用折半查找法可以降低平均查找时间，但建立新文件时会增加维护线性表的开销。

哈希表

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

优点是查找非常迅速，插入和删除也较简单，不过需要一些措施来避免冲突。

顺便指出，在现代操作系统中，通常都提供了模式匹配功能，即在文件名中使用了通配符 “*”、“?” 等。对于使用了通配符的文件名，此时系统便无法利用 Hash 法检索目录，因此系统还是需要利用线性查找法查找目录。

文件共享

注意​，​本节​​的​​文件共享特指静态共享，而动态共享是指两个进程同时对同一个文件进行操作。

文件共享（静态共享）使多个用户共享同一个文件，系统中只需保留该文件的一个副本。若系统不能提供共享功能，则每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。

基于有向无环图实现文件共享

前面介绍了无环图目录，基于该结构可以实现文件共享。

当有多个用户要共享一个子目录或文件时，必须将共享文件或子目录链接到多个用户的父目录中，才能方便地找到该文件。当建立链接关系时，必须将被共享文件的物理地址（盘块号）复制到相应的目录。

这种共享方式存在数据一致性问题：如果某个用户向共享文件添加新数据，且需要增加新盘块，那么这些新增的盘块只会出现在执行了操作的目录中。可见，这种变化对其他用户而言是不可见的，因而新增加的这部分数据已不能被共享。

基于索引节点的共享方式（硬链接）

在引入了索引节点的文件系统中，文件目录即目录项中只设置文件名及指向相应索引节点的指针。因此，在多个用户需要共享某个文件时，只需在各自的文件目录中设置指向该共享文件的索引节点的指针即可。

此时，由任何用户对共享文件进行的写入或修改操作，都将引起其相应索引节点内容的改变（如增加了新的盘块号和文件长度等），这些改变是其他用户可见的，从而也就能提供给其他用户来共享。

索引节点中还应有一个链接计数 count，也称引用计数，用于表示链接到本索引节点（即文件）上的用户目录项的数目。

⚠注意将引用计数与内存索引节点/系统打开文件表中的打开计数区分开来：引用计数关系到文件的存在，引用计数为 0 导致文件删除；打开计数表示文件的访问情况，打开计数为 0 导致文件 close。

共享文件的删除：某用户对某共享文件进行删除操作时，先将该文件索引节点中的 count 减 1，然后删除该用户自己目录中的相应目录项。当 count = 0 时，表示没有用户使用该文件，才会真正删除文件，以避免其他共享此文件的用户的目录中的索引节点指针悬空。

利用符号链实现文件共享（软链接）

LINK 类型文件：内容只包含被共享文件的路径名。它类似于 Windows 系统中的快捷方式。

为使用户 B 能共享用户 A 的一个文件 F，可由系统创建一个 LINK 类型的新文件 L，L 中只含有被链接文件 F 的路径名。将文件 L 写入用户 B 的目录，这样就实现了 B 的目录与文件 F 的链接。这种链接方法称为符号链接或软链接。

当用户 B 访问文件 L 时，操作系统看到要读的文件属于 LINK 类型，则根据其中记录的路径名再去查询文件 F，然后对 F 进行读/写操作，从而实现用户 B 对文件 F 的共享。

L 的引用计数值设置为 1，不管建立软链接时 F 的引用计数值是多少，也不管 F 的引用计数值之后如何变化，L 的引用计数值始终为 1，保持不变。

TODO：对 Link 文件建立硬链接也不会改变其 count 值吗？不过前提是允许对 Link 文件建立硬链接。

对 Link 文件再建立软链接貌似是不被允许的操作，至少在 win 上对快捷方式再建立快捷方式是不被允许的：

下图中的虚线为软链接。父目录分为主父目录（实线）和链接父目录（虚线），如此属主结构（用实线连接起来的结构）仍是简单树，这对文件的删除、查找等都更为方便。

优点：

  1. 只有文件主才拥有指向共享文件索引节点的指针，其他用户只有该文件的路径名，从而避免了留下悬空指针的情况。

    当文件主将一个共享文件删除后，若其他用户又试图通过符号链去访问它时，则会访问失败，于是再将符号链删除，此时不会产生任何影响。

  2. 可以通过网络链接实现网络共享。只需提供该文件所在机器的网络地址及该机器中的文件路径名。

缺点：

  1. 多次读盘。其他用户读共享文件时，系统根据符号链存储的共享文件的路径逐个查找目录，直到找到共享文件的索引节点。显然硬链接查找速度比软链接快。

  2. 符号链本身也是文件，也要配置索引节点，耗费一定的磁盘空间。

  3. 软硬链接共有问题：每一个共享文件都有几个文件名（每增加一条链接就增加一个文件名/路径名）。实质上是每个用户都使用自己的路径名去访问共享文件，当我们试图遍历整个文件系统时，将会多次遍历到该共享文件。

注意，对于文件本身，硬链接方式是允许其有多个路径的；而软链接方式中，每个文件只有一个路径。

💁文件共享，“软” “硬” 兼施。硬链接就是多个指针指向一个索引节点，保证只要还有一个指针指向索引节点，索引节点就不能删除；软链接就是将到达共享文件的路径保存下来，当要访问文件时，根据路径寻找文件。可见，硬链接的查找速度要比软链接的快。

文件系统

用户 ↔ 文件系统 ↔ 物理外存设备

文件系统结构

文件系统设计问题

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

  1. 定义文件系统的接口，它涉及定义文件及其属性、所允许的文件操作、如何组织文件的目录结构。
  2. 创建算法和数据结构，以便映射逻辑文件系统到物理外存设备。

文件系统层次结构

现代操作系统有多种文件系统类型，因此文件系统的层次也不尽相同，无法判断命题组出题人会以哪种分层方式为准。下面给出两种常见的层次结构。

下图是参考国内教材（包括本章笔记内容）给出的文件系统层次结构：

对应本章知识点为：文件操作—目录管理—文件保护—文件逻辑结构—文件物理结构—文件分配、磁盘空闲块管理。

索引文件的索引表就在文件信息缓冲区。

下面的分层结构主要参考国外教材：

文件系统布局

文件系统在磁盘中的结构

文件系统存放在磁盘上，多数磁盘划分为一个或多个分区，每个分区中都可以有一个独立的文件系统。包含文件系统的分区通常称为卷(volume)。

TODO：下图存在一处错误，即分区不属于逻辑格式化。

主引导记录 MBR (Master Boot Record)

位于磁盘的 0 号扇区，也被称为主引导扇区，存有引导代码，其主要作用是告诉 CPU 去硬盘的哪个主分区去找操作系统。

由于历史原因，磁盘 0 号扇区大小是 512 字节，包含最多 446 字节的启动代码、4 个磁盘分区表 DPT 表项（每个表项 16 字节）以及 2 个签名字节（0x55、0xAA）。在深入讨论主引导扇区内部结构时，有时也将其开头的 446 字节内容特指为主引导记录。

磁盘分区表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区，当计算机启动时，BIOS 读入并执行 MBR。MBR 做的第一件事是确定活动分区，读入它的引导块。

引导块(boot block)

又叫启动块、分区引导记录 PBR，win 系统又称之为分区引导扇区。

包含引导程序（启动管理器），负责启动该分区中的操作系统。

每个分区都从一个引导块开始，即使它现在不包含有一个可启动的操作系统。

分区剩余部分的布局随文件系统的不同而变化。

分区可以是原始的，可以没有文件系统。当没有合适的文件系统时，可以使用原始磁盘。

超级块(super block)

包含文件系统的所有关键信息。在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存，并且经常保持主存超级块和磁盘卷中超级块的一致性。

超级块中的典型信息包括：文件系统的类型、分区的块的数量、块的大小、卷中的目录区和文件区划分信息、空闲块的数量和指针，空闲的 FCB 数量和 FCB 指针等。

文件系统中空闲块的信息

文件系统中空闲块的信息，可以使用位示图或指针链接等形式给出。

位示图和超级块都保存有空闲块的信息，功能上有一定重合，主要区别是利用位示图可以迅速地判断某一个特定的盘块是否空闲，而超级块的作用是要迅速地找到若干个空闲的盘块。

文件系统在内存中的结构

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

这些结构的类型可能包括：

  1. 内存中的安装表/挂载表(mounting table)

    包含每个已安装文件系统分区的有关信息，包括文件系统类型、容量大小等。

  2. 内存中的目录结构的缓存

    包含最近访问目录的信息。

  3. 整个系统的打开文件表

    包含每个打开文件的 FCB 副本及其他信息（如打开计数）。

  4. 每个进程的打开文件表（PCB 内维护）

    包含进程打开文件的文件描述符（win 称之为文件句柄）和指向整个系统的打开文件表中对应表项额度指针，以及其他信息（如读写指针、访问权限/打开方式）。

外存空闲空间管理

一个存储设备可以按整体用于文件系统，也可以细分。

例如，一个磁盘可以划为若干分区，每个分区都可以单独的文件系统，包含文件系统的分区通常称为卷(volume)。卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成 RAID 集。

在一个卷中，存放文件数据的空间（文件区）和 FCB 的空间（目录区）是分离的。目录区主要存放文件目录信息（FCB），用于磁盘存储空间管理的信息，而文件区用于存放文件数据。

卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块。

由于存在很多种类的文件表示和存放格式，所以现代操作系统中一般都有很多不同的文件管理模块，通过它们可以访问不同格式的卷中的文件。

文件存储设备分成许多大小相同的物理块，并以块为单位交换信息。因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。

空闲表法

属于连续分配方式，与内存的动态分区分配方式类似，为每个文件分配一块连续的存储空间。

系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项。将所有空闲区按其起始盘块号递增的次序排列。

空闲盘块的分配与内存的动态分区分配类似，同样可以采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

系统在对用户所释放的存储空间进行回收时，也采取类似于内存动态分区回收的方法，同样需要注意表项的合并问题，即需要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接（四种情况），对相邻接者应予以合并。

空闲链表法

将所有空闲盘区拉成一条空闲链。

根据构成链所用基本元素不同，分为两种形式：

空闲盘块链

以盘块为单位拉成一条链。

每个空闲盘块都有指向下一个空闲盘块的指针。

操作系统保存链首、链尾指针。

从链首开始分配（依次摘下适当数目的空闲盘块），回收则加在链尾。

优点：分配和回收一个盘块的过程非常简单。

缺点：为一个文件分配盘块时可能要重复操作多次，效率较低；空闲盘块链会很长。

适用于离散分配的物理结构。

空闲盘区链

以盘区为单位拉成一条链，每个盘区包含若干相邻的盘块。

每个空闲盘区都有指向下一个空闲盘区的指针，以及本盘区的盘块数。

分配和回收也与内存的动态分区分配方式类似。分配通常采用首次适应算法，回收盘区时同样也要将回收区与相邻接的空闲盘区合并。

优点：分配与回收的效率较高，且空闲盘区链较短。

缺点：分配和回收的过程比较复杂。

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太大。

位示图法

利用二进制的一位来表示磁盘中一个盘块的使用情况（下图以 “0” 代表盘块空闲，以 “1” 代表盘块已分配）。磁盘上所有的盘块都有一个二进制位与之对应，所有盘块所对应的位构成一个集合，称为位示图。

位示图可描述为一个二维数组 map，一个 m×n 位组成的位示图就可用来表示 m×n 个盘块的使用情况：

位示图一般用连续的 “字” 来表示，如上图中一个字的字长是 16 位，字中的每一位对应一个盘块，因此可以用 (字号, 位号) 对应一个盘块号。当然有的题目中也描述为 (行号, 列号)。

💥要能自己推出盘块号与 (字号, 位号) 相互转换的公式。需要注意题目条件，首先确定盘块号、行号/字号、列号/位号的起始编号是 0 还是 1。

如何分配（若文件需要 K 个块）：

  1. 顺序扫描位示图，找到 K 个相邻（连续分配）或不相邻（离散分配）的 “0”；
  2. 根据字号、位号算出对应的盘块号，将相应盘块分配给文件；
  3. 将位示图相应位设置为 “1”。

如何回收：

  1. 根据回收的盘块号计算出对应的字号、位号；
  2. 将位示图相应位设置为 “0”。

优点：很容易找到一个或一组相邻接的空闲盘块；位示图很小，可以常驻内存，从而节省许多磁盘启动的开销。

缺点：位示图大小会随着磁盘容量的增大而增大，因此常用于小型计算机。

位示图对于连续分配和离散分配都适用。

成组链接法

UNIX 系统中采用了成组链接法，这种方法结合了空闲表和空闲链表两种方法的思想，具有两种方法的优点，同时克服了两种方法均有的表太长的缺点。

成组链接法的思想：将空闲盘块分成若干组，如 100 个空闲盘块作为一组，每组的第一个空闲盘块（作为索引块，称为成组链块）记录下一组的空闲盘块总数和空闲盘块号。这样由各组的第一个空闲盘块可以链接成一条链。

第一组的空闲盘块总数和空闲盘块号保存在内存⚠的专用栈中，称为空闲盘块号栈。空闲盘块号栈保存在磁盘卷头位置的超级块中。在对卷中的文件进行操作前，超级块要预先读入内存，并且经常保持主存超级块与磁盘卷中超级块的一致性。

成组链块记录的空闲盘块号数 N 可兼作栈顶指针用，例如当 N = 100 时，它指向 S.free(99)。

空闲盘块的分配

首先检查空闲盘块号栈是否上锁，如未上锁，则从栈顶开始分配。

若分配进行到栈底，即 S.free(0)，其对应的盘块（成组链块）记有下一组可用的盘块号。因此须调用磁盘读过程，将该成组链块的内容读入栈中，作为空闲盘块号栈（超级块）的新内容，并把该成组链块本身分配出去。

空闲盘块的回收

将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加 1 操作（同时也移动了栈顶指针）。当栈中空闲盘块号数目已达 100 时，表示栈已满，便将栈中的 100 个空闲盘块号记入下一个新回收的盘块，并将新回收的盘块号作为新栈底，再将栈中的空闲盘块数置为 1。

虚拟文件系统 VFS

虚拟文件系统 VFS 屏蔽了不同文件系统的差异和操作细节，向上为用户提供了文件系统操作的统一接口，用户可以通过 VFS 提供的统一调用函数来操作不同文件系统的文件，而无须考虑具体的文件系统和实际的存储介质。

VFS 并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间中。VFS 在系统启动时建立，在系统关闭时消亡。

VFS 模型及其对象类型

VFS 采用了面向对象的思想，抽象出一个通用的文件系统模型，定义了通用文件系统都支持的接口，新的文件系统只要支持并实现这些接口，即可安装和使用。

Linux VFS 主要抽象了四种对象类型，每个对象都包含数据和函数指针，这些函数指针指向操作这些数据的文件系统的实现函数。这四种对象类型如下：

  1. 文件对象（表示一个与进程相关的已打开文件）

    可以通过 open() 打开一个文件，通过调用 close() 关闭一个文件。

    文件对象和物理文件的关系类似于进程和程序的关系，文件对象仅是进程视角上代表已打开的文件，它反过来指向其索引节点。

    文件对象包含与该文件相关的目录项对象，包含该文件的文件系统、文件指针等，还包含在该文件对象上调用的一系列操作函数。

    由于多个进程可以打开和操作同一文件，所以同一文件在内存中可能存在多个对应的文件对象，但对应的索引节点和目录项是唯一的。

    多个进程指向同一个文件对象属于文件的动态共享。

  2. 目录项对象（表示一个特定的目录项）

    目录项对象 dentry 代表一个独立的文件路径，主要是用来保存文件路径和 inode 之间的映射。不同于前面两个对象，目录项对象在磁盘上没有对应的数据结构，而是 VFS 在遍历路径的过程中，将它们逐个解析成目录项对象的。

    目录项对象包含指向关联索引节点的指针，以及指向父目录和指向子目录的指针。

    VFS 维护了一个目录项缓存 dentry cache，用来保存最近使用的 dentry，加速查询操作。当调用 open() 函数打开一个文件时，内核会第一时间根据文件路径到 dentry cache 里面寻找相应的 dentry，找到了就直接构造一个 file 对象并返回。如果该文件不在缓存中，那么 VFS 会根据找到的最近目录一级一级地向下加载，直到找到相应的文件。期间 VFS 会缓存所有被加载生成的 dentry。

    多个文件对象指向同一个目录项对象属于同一个文件被多次 open 的情况。

  3. 索引节点对象（表示一个特定的文件）

    可以视作内存索引节点的抽象。因为不同文件系统，表示文件数据结构各不相同，打开文件后，其在内存中的表示就不同。比如 UFS 文件系统的目录项是文件名和 inode 索引构成，而 FAT 文件系统就没有将目录项分离出 inode。于是 VFS 就抽象出索引节点对象（位于内存），即下图中的 vnode。⚠注意，vnode 只存在于主存中，而 inode 既会被调入主存，也会在外存中存储。

文件打开后，vnode 除了复制磁盘索引节点包含的一些文件信息，还设置了许多操作接口，即操作方法/函数功能指针。索引节点对象提供许多操作函数，如创建新文件（即为目录项对象创建一个新的索引节点）、创建新目录（类似创建新文件，只不过该文件是目录文件）、创建硬链接（即将一个已存在的索引节点关联到一个指定的新目录项对象）、对文件或目录进行重命名、根据给定路径查找并返回对应的文件或目录的索引节点等。显然这些操作属于文件/目录操作，具体实现由具体的文件系统提供。注意，这里的索引节点均为内存索引节点，要与下面超级块对象上的操作函数区分开。

多个目录项对象指向同一索引节点属于文件静态共享的硬链接方式。

  1. 超级块对象（表示一个已安装/挂载的特定文件系统）

    超级块对象对应于磁盘上特定分区的文件系统超级块，用于存储已安装文件系统的元信息。

    元信息包含文件系统的基本属性信息，如文件系统类型、文件系统基本块的大小、文件系统所挂载的设备、操作方法/函数等。

    其操作方法包含一系列可在超级块对象上调用的操作函数，主要有分配 inode（分配 inode 内存并进行 inode 结构初始化）、销毁 inode（释放 inode 分配的资源）、读 inode（磁盘索引节点 → 内存索引节点）、写 inode（内存索引节点 → 磁盘索引节点）等。

面向文件的系统调用的过程

当进程发起一个面向文件的系统调用时，内核调用 VFS 中的一个函数，该函数调用目标文件系统中的相应函数，将文件系统请求转换到面向设备的指令。以在用户空间调用 write() 为例，它在 VFS 中通过 sys_write() 函数处理, sys_write() 找到具体文件系统提供的写方法，将控制权交给该文件系统，最后由该文件系统与物理介质交互并写入数据。

文件系统挂载

如文件在使用前必须打开一样，文件系统在进程使用前必须先安装，也称挂载(mounting)。将设备中的文件系统挂载到某个目录后，就可通过这个目录来访问设备上的文件。注意这里的设备指的是逻辑上的设备⚠，如一个磁盘上的不同分区都可视为不同的设备。

如何将一个文件系统挂载到操作系统中？

挂载过程大致如下：

  1. 在 VFS 中注册新挂载的文件系统

    内存中的挂载表(mount table)包含每个文件系统的相关信息，包括文件系统类型、容量大小等。

  2. 新挂载的文件系统，要向 VFS 提供一个函数地址列表。

  3. 将新文件系统加到挂载点(mount point)，也就是将新文件系统挂载在某个父目录下。

Windows 的挂载

win 系统维护一个扩展的两级目录结构，用驱动器字母表示设备和卷。卷具有常规树结构的目录，与驱动器号相关联，还含有指向已安装文件系统的指针。特定文件的路径形式为 driver-letter:\path\to\file，操作系统找到相应文件系统的指针，并遍历该设备的目录结构，以查找指定的文件。

新版本的 win 允许文件系统安装在目录树下的任意位置，就像 UNIX 一样。在启动时 win 系统自动发现所有设备，并且安装所有找到的文件系统。

UNIX 的挂载

UNIX 使用系统的根文件系统，它是在系统启动时（引导阶段）直接安装的，也是内核映像所在的文件系统。

除了根文件系统，所有其他文件系统都要先挂载到根文件系统中的某个目录后才能访问。

其他文件系统要么在系统初始化时自动安装，要么由用户挂载在已安装文件系统的目录下。

安装文件系统的目录称为安装点，安装就是将磁盘分区挂载到该安装点下，进入该目录就可以读取该分区的数据。已安装文件系统属于安装点目录的一个子文件系统。作为一个目录树，每个文件系统都拥有自己的根目录。

⚠同一个设备可以有多个安装点，但同一个安装点同时只能挂载一个设备。

mount 命令 mount -t ext2 /dev/fd0 /flp 将存放在磁盘 /dev/fd0 上的 ext2 文件系统安装到 /flp。如需卸载该文件系统，可以使用 umount 命令。

挂载的实现是在目录 inode 的内存副本上加上一个标志，表示该目录是安装点，另外还有一个域指向安装表的条目，表示哪个设备安装在哪里（这个条目还包括该设备的文件系统超级块的一个指针）。

可以这么理解：UNIX 本身是一个固定的目录树，只要系统安装就有，但若不给它分配存储空间，就不能对它进行操作，所以首先要给根目录分配空间，这样才能操作这个目录树。

刷题笔记

  • 容易混，要记清：

  • 无论是顺序存取还是随机存取，顺序文件 + 连续结构通常是速度最快的。

  • 系统打开文件表只有在文件实体第一次被打开时才增加一个表目，也才会通过文件 I/O 将对应的索引节点从磁盘读入内存。

  • open 调用的参数的文件名不同时，必然会打开不同的文件实体❌

    当 open 调用的不同文件互为硬链接时，所打开的文件实体是一样的。

  • read 系统调用

    参数：文件描述符 fd、buf 缓冲区首址、传送的字节数 $n$。

    功能：从 fd 所指示的文件中读入 $n$ 个字节的数据，并将它们送至由指针 buf 所指示的缓冲区中。

  • 读文件操作的步骤

    1. 按文件描述符在打开文件表中找到该文件的目录项；
    2. 按存取控制说明检查访问的合法性；
    3. 根据目录项中该文件的逻辑和物理组织形式，将用户提供的记录号先转换为逻辑地址再转换成物理块号；
    4. 向设备驱动程序发出 I/O 请求，完成数据交换工作。

  • 采用连续分配和索引分配都支持随机存取，采用链接分配的文件不支持随机存取。

  • 描述文件权限的位数，是指访问矩阵的 “格子” 数。

  • 文件系统性能取决于磁盘 I/O（次数、快慢）。

  • 目录项、索引块需要先从磁盘读入内存的，如果题目没说它们已经被调入内存时，在计算磁盘 I/O 次数时需要加上。

  • 若需要在文件中增加一个盘块，则连续分配的磁盘 I/O 次数最多，其次是隐式链接分配。

    在第 n 块（从 1 开始）后增加一块，隐式链接文件需要读盘 n 次、写盘 2 次；连续分配其实是不确定的，因为可以把前 n 块往前移，也可以把第 n 块之后的往后移，如果题目没说明方向的话，应该是按移动盘块最少的方向移动。移动 m 块，需要先读写各 m 次，然后再写 1 次，共 2m+1 次。

  • 提高文件访问速度（磁盘 I/O）的方法

    1. 提前读

      先将数据从外存写入内存缓冲区（在读磁盘当前块时，把下一磁盘块也读入内存缓冲区），需要时直接从缓冲区中读取。

    2. 延迟写

      先将数据从内存写入缓冲区。仅在缓冲区首部设置延迟写标志，然后释放此缓冲区并将其链入空闲缓冲区链表的尾部，当有其他进程申请到此缓冲区时，才真正把缓冲区信息写入磁盘。

    3. 采用磁盘高速缓存

    4. 虚拟盘

      指用内存空间去仿真磁盘，又叫 RAM 盘。

      虚拟盘属于易失性存储器，常用于存放临时文件。

    5. 优化文件物理块的分布

      如为文件分配连续的簇，可以减少寻道时间与延迟时间。

    6. 重排 I/O 请求次序

      即选择合适的磁盘调度算法进行 I/O 调度，使进程之间公平地共享磁盘访问，减少 I/O 完成所需要的平均等待时间。

  • 根据文件分配表、页表和中断向量表的应用原理，它们都有一个要求，就是要能随机访问表中的任一元素，即随机访问，因此只能用数组实现。

  • 文件数据在物理存储设备上的分布和组织

    1）文件的分配方式——对磁盘非空闲块的管理

    2）文件存储空间管理——对磁盘空闲块的管理

  • 对外存文件区的管理以提高存储空间的利用率为目标。

  • 一个文件系统可以存放的文件数量受限于文件控制块的数量

    UFS 中每个 inode 的大小一般是 128 字节或 256 字节。inode 节点的总数，在格式化时就给定（现代 OS 可以动态变化），一般每 2KB 就设置一个 inode。一般文件系统中很少有文件小于 2KB 的，所以预定按照 2KB 分，在磁盘空间用完之前，一般 inode 是用不完的。

  • 单个文件的大小不仅受磁盘剩余空间大小的限制，而且受 FCB（物理地址字段，如直接地址数量、间接地址种类和数量）、FAT 表容量、盘块/簇大小、块地址位数等的限制。