文件系统接口

一、文件概念

操作系统对存储设备的物理属性加以抽象，从而定义逻辑存储单位，即文件。文件是记录在外存上相关信息的命令组合，有不同类型，包括文本文件、源文件、可执行文件等。

1.1 文件属性

文件的属性因操作系统而异，但通常包括：

名称：符号化的文件名称是以人类可读形式来保存的唯一信息。
标识符：这种唯一标记（通常为数字）标识文件系统的文件，是非人类可读的名称。
类型：支持不同类型文件的系统需要这种信息。
位置：该信息为指向设备与设备上文件位置的指针。
大小：文件当前大小，以及可能允许的最大大小。
保护：访问控制信息确定谁能进行读取、写入、执行等。
时间戳和用户标识：文件创建、最后修改和最后使用的相关信息。

所有文件的信息都保存在目录结构中。通常，目录条目由文件的名称及其唯一标识符组成。根据标识符可以定位其他文件属性。

1.2 文件操作

文件是抽象数据类型。操作系统一般都会提供 7 种基本文件操作，包括：

创建文件：在文件空间中为文件找到空间 + 在目录中创建新文件的条目。
打开文件：调用 open() 将返回一个文件句柄，该句柄在其它调用中作为参数。
写文件：系统保留写指针，指向需要进行下次写操作的文件位置。每次写操作时，写指针都要更新。
读文件：系统保留读指针，指向需要进行下次读操作的文件位置。每次读操作时，读指针都要更新。
重新定位文件：打开文件的当前文件位置指针被重新定位到给定值。又叫文件定位。
删除文件：在目录中找到关联的目录条目，然后释放所有文件空间。
截断文件：截断功能可以将文件属性保留，重置为零长度，并释放文件空间。

操作系统为了避免不断的搜索，有一个打开文件表，用于维护所有打开文件的信息。由于不同的应用程序可能打开同一个文件，操作系统采用单个进程表和整个系统表。

如上图所示，单个进程表的每个条目相应地指向整个系统的打开文件表。系统表包含于进程无关的信息，如文件在磁盘上的位置、访问权限等。总而言之，打开文件需要以下关联信息：文件指针、文件打开计数、文件位置（保存在内存）、访问权限。

文件锁允许进程锁定文件。共享锁类似于读者锁，独占锁类似于作者锁。另外，操作系统提供强制或建议文件锁定机制。

强制：一旦进程获取独占锁，操作系统就阻止其他任何进程访问锁定文件。由操作系统确保锁定完整性。如 Windows。
建议：进程可以获取文件锁的状态。由软件开发人员确保是当地获取和释放锁。如 Unix。

1.3 文件类型

文件类型很多，权当了解即可。

1.4 文件结构与内部文件结构

文件类型也可用于指示文件的内部结构。例如：源文件和目标文件具有一定的结构，以便匹配读取程序的需求。有些操作系统会支持最小数量的文件结构。例如 UNIX 文件认为每个文件为 8 位字节序列。

而在文件内部，定位文件的偏移并不容易。所有磁盘 I/O 都以块位单位执行，而所有块的大小相同。因此，文件可以被看作块的序列，文件的最后一块的某些部分常常需要被浪费，产生内部碎片。块越大，内部碎片也就越大。

二、访问方法

一般来说，文件信息的方法方法包括顺序访问方式，直接访问方式和索引访问方式。

2.1 顺序访问方式

文件信息按顺序加以处理，如编辑器和编译器。这也是目前最常见的。

2.2 直接访问方式

文件有固定长度的逻辑记录组成，以允许程序按任意顺序快速读取和写入记录。有时，这种读取方式非常有效，比如数据库中就可以通过先计算出哪个块包含答案，然后直接读取相应块的信息。

我们要注意对于这种访问方式，用户提供给操作系统的块号通常是相对块号，从 0 开始，依次增加。假设逻辑记录长度为 L，则记录 N 的请求可转换为从文件位置 L * N 开始的 L 字节请求。由于逻辑记录是固定大小，所以也容易读、写和删除记录。

我们很轻松地在顺序访问文件上模拟直接访问，如下图所示，但这非常低效。

2.3 索引访问方式

为了提高搜索时间并减少 I/O，在文件中查找记录，首先搜索索引，然后根据指针直接访问文件并且找到所需记录。

对于大文件，索引文件本身可能变得太大而无法保存在内存中。一种解决方法是为索引文件创建索引。主索引文件包含指向辅助索引文件的指针，而辅助索引文件包含指向实际数据项的指针。

三、目录结构

目录可视为符号表，以文件名称转成目录条目。这种组织允许我们插入条目、删除条目、搜索命令条目以及列出所有目录条目等。

3.1 单级目录

最简单的目录结构是单级目录。所有文件都包含在同一目录中，这很容易支持和理解。

但是当文件变多时，搜索文件会变得很慢。同时，因为所有文件位于同一目录下，所以不能有一样的名称。因此命名变得非常不方便。

3.2 两级目录

单级目录常常导致混乱的文件名。标准的解决方案是为每个用户创建一个单独的目录。

每个用户都有自己的用户文件目录（UFD）。当用户作业开始时，搜索系统的主文件目录（MFD）。每个主文件目录仅对应于自己的用户。因此，不同用户可能拥有相同名称的文件，但同一用户的所有文件名称不同。

3.3 树形目录

上面所说的两级目录可以认为是一个特殊的树形目录，高度为 2。树根是 MFD，MFD 的直接后代为 UFD，UFD 的后代为文件本身。明白了这个，我们自然可以将目录结构扩展到任意高度的树。这种推广允许用户创建自己的子目录并相应地组织文件。

当引用的文件不再当前目录中时，就需要通过指定目录名来访问文件。路径名可有两种形式：绝对路径名和相对路径名。绝对路径名从根开始，遵循一个路径到指定文件，并给出路径上的目录名。相对路径名从当前目录开始定义一个路径。

树形目录中，用户除了可以访问自己的文件外，还可以访问其他用户的文件，只需要指定路径名即可。这就是树形目录的特点。

3.4 无环图目录

有时，同一个项目中的文件需要由多个人进行编辑操作。此时，我们就需要共享文件。但树形目录只能访问文件，不能共享同一个文件。于是，人们想出了无环图目录：让每个团队成员的 UFD 将共享文件的这个目录作为子目录。

共享文件和目录的实现方法之一是创建一个名为链接的新目录条目。链接实际上是另一个文件或子目录的指针。其中保存了真实文件的名称等信息。通过解析链接，就可以定位真实文件。

上面的链接叫做符号链接。它是一个独立的文件，可以存储目标文件或目录的路径。当删除源文件后，符号链接会变成“悬空链接”，指向一个不存在的位置。

还有一种链接叫做硬链接。它本质上是同一个文件的不同名字，当删除源文件时，只要还有硬链接存在，文件数据就不会被删除。

3.5 通用图目录

采用无环图结构的主要优点是，有相对简单的算法以遍历图并确定何时没有更多的文件引用。但有时，目录中不得不出现环，如果算法不当，可能会无限搜索环而无法终止。一种解决方案是可以限制在搜索时访问目录的数量。

还有一种方法是使用垃圾收集方案。可以采用引用计数法、标记 - 清除算法等常见的垃圾回收算法。对于文件系统，还可以结合文件访问时间、文件大小等因素来判断是否为垃圾文件。

当然，总而言之，我们解决保证无循环问题可以有以下两种思路：

限制链接类型：只允许链接到文件，这样可以从根本上避免目录间形成循环链接。
添加链接时检测：每次添加新链接时，使用循环检测算法来判断是否会形成循环。例如可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法，从新链接的起始点开始搜索，看是否会回到起始点，如果会则说明会形成循环，不允许添加该链接。