基于王道计算机考研 操作系统。

笔记目录

第一章-计算机系统概述
第二章-进程与线程
第三章-内存管理
第四章-文件系统
第五章-输入/输出管理

第四章 文件系统

4.1 文件系统基础

4.1.1 文件的基本概念

文件是以硬盘为载体的存储在计算机上的信息集合，可以是文本文档、图片、程序等。

在系统运行时，计算机以进程为基本单位进行资源调度和分配；在用户进行的输入、输出中，则以文件为基本单位。大多数应用程序的输入和输出都是通过文件来实现的。

操作系统的文件系统用于实现用户对文件的管理要求。

文件的定义

文件包括一块存储空间中的数据，包含分类和索引的信息，不同用户对数据的访问权限不同，所以还包含关于访问权限的信息。

文件系统是操作系统的重要部分之一，用户关心的事如何命名、分类和查找，如何保证数据安全性以及能对文件进行哪些操作。

文件系统提供了与二级存储相关的资源的抽象，让用户能在不了解文件的各种属性、文件存储介质的特征以及文件在存储介质上的具体位置等情况下，方便的使用文件。

自底向上定义文件：

1. 数据项。是文件系统中最低级的数据组织形式，可分为基本数据项和组合数据项。
   基本数据项用于描述一个对象的某种属性的一个值，是数据中最小的逻辑单位。
   组合数据项由多个基本数据项组成。
2. 记录。是一组相关的数据项的集合，用于描述一个对象在某方面的属性。
3. 文件。由创建者定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。
   有结构文件中，文件由若干相似的记录组成；无结构文件被视为一个字符流。

操作系统中，通常将程序和数据组织成文件，文件可以是数字、字符或二进制代码，基本访问单元可以是字节或记录。文件可以长期存储在硬盘中，允许可控制的进程共享访问，能组成复杂的结构。

文件的属性

操作系统还会保存文件相关的信息，称为文件属性或文件元数据。通常包含以下属性：

1. 名称。
2. 类型。
3. 创建者。
4. 所有者。
5. 位置。指向设备和设备上文件的指针。
6. 大小。用字节、字或块表示，也可包含文件允许的最大值。
7. 保护。对文件进行保护的访问控制信息。
8. 创建时间、最后一次修改时间和最后一次存取时间。用于保护和跟踪文件的使用。

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

文件的分类

1. 按性质和用途分类，分为系统文件、用户文件、库文件。
2. 按文件中数据的形式分类，分为源文件、目标文件、可执行文件。
3. 按存取控制属性分类，分为可执行文件、只读文件、读/写文件。
4. 按组织形式和处理方式分类，分为普通文件、目录文件、特殊文件。

4.1.2 文件控制块和索引节点

文件控制块

文件控制块(FCB)用来存放控制文件需要的各种信息的数据结构，实现按名存取。文件与FCB一一对应，FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。

通常一个文件目录也被视为一个文件，称为目录文件。每创建一个新文件，系统就创建一个FCB。

FCB包含以下信息：

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

FCB最重要，最基本的还是文件名和文件存放的物理地址。

索引节点

文件很多时，文件目录会占用大量的盘快，查找目录时，要先将存放目录文件的第一个盘块调入内存，逐一比较文件名，未找到就要将下一盘块调入内存。

在检索过程中只用到了文件名，仅当找到一个目录项时才需要从中读出物理地址，不需要读取其他描述信息。因此有的系统采用文件名和文件描述信息分离的方法，使文件描述信息单独形成一个索引节点的数据结构，简称i节点。每个目录项仅由文件名和相应的索引节点号（或索引节点指针）构成。

• 磁盘索引节点

指存放在磁盘上的索引节点。每个文件名有一个唯一的磁盘索引节点，主要包括：

1. 文件主标识符，拥有该文件的个人或小组的标识符。
2. 文件类型，包括普通文件、目录文件和特别文件。
3. 文件存取权限，各类用户对该文件的存取权限。
4. 文件物理地址，每个索引节点中有13个地址项，即iaddr(0)-iaddr(12)，他们可以直接或间接地给出数据文件所在盘块的编号。
5. 文件长度。
6. 文件链接计数，文件系统中所有指向该文件的文件名的指针计数。
7. 文件存取时间。

• 内存索引节点

指存放在内存中的索引节点。文件被打开时，要将磁盘索引节点复制到内存的索引节点中，内容还增加了：

1. 索引节点号。
2. 状态，i节点是否上锁或被修改。
3. 访问计数。每当有一进程要访问i节点，计数+1；访问结束-1。
4. 逻辑设备号。文件所属文件系统的逻辑设备号。
5. 链接指针，分别指向空闲链表和散列队列的指针。

FCB或索引节点相当于索书号，通过索书号找到想要的书本。

4.1.3 文件的操作

文件的基本操作

文件属于抽象数据类型，操作系统定义了一系列系统调用。

1. 创建文件。为新文件分配外存空间，在目录中为之创建一个目录项，目录项记录了新文件名，文件在外存中的地址等信息。
2. 删除文件。根据文件名查找目录，删除指定文件对应的目录项和文件控制块，然后回收该文件所占用的存储空间（磁盘空间和内存缓冲区）。
3. 读文件。根据文件名查找目录，找到目录项，得到文件在外存中的地址；还有一个指针用于对文件进行读操作。
4. 写文件。根据文件名查找目录，找到目录项，利用目录项的写指针对文件进行写操作；每当发生写操作就更新写指针。

文件的打开与关闭

当用户首次对某文件发出操作请求时，需要利用系统调用open将其打开。系统维护一个包含所有打开文件信息的表，称为打开文件表。

打开指的是系统检索到指定文件的目录项后，将该目录项从外存复制到内存中的打开文件表的一个表目中，并将表目的索引号（也称文件描述符）返回给用户。当用户再次对文件发出操作请求时，可通过文件描述符在打开文件表中查找到文件信息，节省检索开销。

文件不再使用时，可利用系统调用close关闭它，系统会从打开文件表中删除这一表目。

在多个进程可以同时打开文件的系统中，通常采用两级表：整个系统表和每个进程表。整个系统的打开文件表包含和进程无关的信息，比如文件在磁盘上的位置，访问日期等；每个进程的打开文件表保存进程对文件的使用信息，比如文件的当前读写指针、文件访问权限，指向系统表中适当条目的指针。

一旦有一个进程打开了一个文件，系统表就包含该文件的条目。另一个进程执行open时，是在其打开文件表中增加一个条目，并指向系统表的相应条目。通常系统打开文件表会为每个文件关联一个打开计数器记录多少进程打开了该文件。

文件不再使用时，利用系统调用close关闭它，会删除单个进程打开文件表中的相应条目，打开计数器-1；当打开计数器为0时，表示该文件不再使用，可从系统表中删除相应条目。

文件名不必是打开文件表的一部分，一旦完成对FCB在磁盘上的定位，系统就不再使用文件名。对于访问打开文件表的索引号，UNIX称为文件描述符，Windows称为文件句柄。只要文件未关闭，所有文件操作都是通过文件描述符进行。

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

1. 文件指针。系统根据上次读写文质作为当前文件位置的指针，这种指针对打开文件的某个进程是唯一的，必须与磁盘文件属性分开保存。
2. 文件打开计数。计数器跟踪当前文件打开和关闭的数量，系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。
3. 文件磁盘位置。大多数文件要求操作系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中，以便系统为每个操作从磁盘上读取信息。
4. 访问权限。每个进程打开文件都要有一个访问模式（创建、只读、读写、添加等）。该信息保存在进程的打开文件表中，以便操作系统允许或拒绝后续的I/O请求。

4.1.4 文件保护

文件系统需要控制用户对文件的存取，可以通过口令保护、加密保护和访问控制等方式实现。口令和加密是为了防止文件被窃取，访问控制用于控制对文件的访问方式。

访问类型

• 读。
• 写。
• 执行。将文件装入内存并执行。
• 添加。将新信息添加到文件结尾部分。
• 删除。
• 列表清单。列出文件名和文件属性。

此外还可以对文件名进行重命名、复制、编辑等，这些高层功能通过系统程序调用低层系统调用实现。保护可以只在低层提供。

访问控制

最常用的方法是根据用户身份进行控制，为每个文件和目录增加一个访问控制列表(ACL)，以规定每个用户名及其所允许的访问类型。优点是可以使用复杂的访问方法，缺点是长度无法预计并且可能导致复杂的空间管理。

使用精简的访问列表可以解决这个问题。精简的访问控制列表可采用拥有者、组和其他三种用户类型。

1. 拥有者。创建文件的用户。
2. 组。一组需要共享文件且具有类似访问的用户。
3. 其他。系统内的其他用户。

口令和密码是另外两种控制访问方法。

口令指用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应口令，并告诉共享该文件的其他用户，用户请求访问时必须提供相应的口令。这种方法的时空开销不多，但是口令直接存在系统内部，不够安全。

密码指用户对文件加密，访问时需要使用密钥。这种方法保密性强，节省存储空间，但是编码和译码需要一定时间。

口令和密码都是防止用户文件被窃取，并没有控制用户对文件的访问类型。

目录操作和文件操作并不相同，对于多级目录，不仅要保护单个文件，还要保护子目录中的文件，需要提供目录保护机制。

4.1.5 文件的逻辑结构（一般不考）

文件的逻辑结构是从用户角度出发看到的文件的组织形式；文件的物理结构是将文件存储在外存上的存储组织形式，是用户看不见的。逻辑结构和存储介质特性无关，实际上指的是文件内部的数据在逻辑上是如何组织起来的。

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

无结构文件

无结构文件是最简单的文件组织形式，是由字符流构成的文件，又称为流式文件，长度以字节为单位。对流式文件的访问是通过读/写指针指出下一个要访问的字节的。

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

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

有结构文件

有结构文件指由一个以上的记录构成的文件，又称为记录式文件。各记录由相同或不同数目的数据项组成，根据各记录的长度是否相等，分为定长记录和变长记录。各个记录在物理上可以是顺序存储或链式存储。

1. 定长记录。文件中所有记录的长度是相同的，各数据项都在记录中的相同位置，具有相同的长度。检索记录的速度快，方便用户对文件进行处理，广泛应用在数据处理中。
2. 变长记录。文件中各记录的长度不一定相同。有可能是记录包含的数据项数目不同，也可能是数据项本身的长度不定。检索记录只能顺序查找，速度慢。

有结构文件按记录的组织形式可以分为顺序文件、索引文件、索引顺序文件。

• 顺序文件

文件中的记录顺序排列，可以是定长或变长记录。记录的排列有两种结构：串结构，各记录之间的顺序与关键字无关，通常按存入的先后时间排列，检索时必须从头查找；顺序结构，记录按关键字排序，对于定长记录的顺序文件可以采用折半查找。

对记录进行批量操作，顺序文件效率是所有逻辑文件中最高的，对于顺序存储设备（磁带），只有顺序文件才能被存储并有效地工作。在经常需要增删改查单个记录的场合，顺序文件的性能较差（串结构相对简单）。

• 索引文件

对于定长记录的顺序文件，要查找第i条记录，直接根据$A_i=i\times L$得到相对于第1条记录的地址。对于变长记录的顺序文件，必须顺序查询前i-1条记录，获得相应记录的长度L，从而计算出第i条记录的地址：
$$
A_i=\sum^{i-1}_{i=0}{L_i+1}
$$
变长记录的顺序文件只能顺序查找，效率较低，可以建立一张索引表，为主文件的每个记录在索引表设置索引表项，包含指向记录的指针和记录长度，索引表按关键字排序，因此本身也是一个定长记录的顺序文件。这样就将对变长记录顺序文件的顺序检索变成了对定长记录索引文件的随机检索，加快了检索速度。

索引文件需要配置索引表，且每个记录都要有一个索引项，因此增加了存储开销。

• 索引顺序文件

索引顺序文件是顺序文件和索引文件的结合。最简单的索引顺序文件只使用了一级索引，将变长记录顺序文件中的所有记录分为若干组，然后为文件建立一张索引表，并为每组的第一个记录建立一个索引项，其中包含了该记录的关键字和指向该记录的指针。（一组记录对应一个索引项）

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

• 直接文件或散列文件

给定记录值的键值通过散列函数转换的键值直接决定记录的物理地址。散列文件具有很高的存取速度，但可能会引起冲突（碰撞）。

4.1.6 文件的物理结构

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

一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理。

文件分配对应于文件的物理结构，指如何为磁盘分配物理块。常见的有三种：连续分配、链接分配和索引分配。

磁盘中的存储单元被分为一个个的块，称为磁盘块，大小通常和内存的页面大小相同。磁盘和内存之间的数据交换都是以块为单位进行的。文件的逻辑地址空间也被分为一个个块，逻辑地址可以表示为（逻辑块号，块内地址）的形式。

连续分配

连续分配要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序，这种排序使进程访问磁盘时需要的寻道数和寻道时间最小。

采用连续分配时，逻辑文件中的记录也顺序存储在相邻的物理块中。一个文件的目录项应该记录该文件的第一个磁盘块号和块号占用的块数。

如果文件长n块，并从位置b开始，则该文件将占有块b,b+1,b+2,…,b+n-1，要访问文件的第i块，可以直接访问块b+i-1。

连续分配的优点：

1. 支持顺序访问和直接访问（即随机访问）。
2. 顺序访问简单且速度快，文件占用的块可能位于一条或几条相邻的磁道上，磁头的移动距离最小。

缺点：

1. 要为一个文件分配连续的存储空间，会产生很多外部碎片。可以用紧凑来处理碎片，但是要耗费很大的时间代价。
2. 必须事先知道文件的长度，无法满足文件动态增长的要求，否则会覆盖物理上相邻的后续文件。
3. 为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动。

链接分配

链接分配采用离散分配。

优点：

1. 消除了磁盘的外部碎片，提高了磁盘的利用率。
2. 便于动态分配盘块，无需事先知道文件的大小。
3. 文件的插入、删除和修改十分方便。

链接分配又可以分为隐式链接和显式链接两种形式。

• 隐式链接

隐式链接的目录项中含有文件第一块的指针和最后一块的指针。每个文件对应一个磁盘块的链表，磁盘块分布在磁盘的任何地方。除了头尾盘块，每个盘块都存有指向下一个盘块的指针，这些指针对用户是透明的。

隐式链接的缺点：

1. 只支持顺序访问，随机访问效率很低。
2. 稳定性问题，任何一个指针出错都会导致文件数据的丢失。
3. 指针也要耗费一定的存储空间。

为了提高查找速度，同时减少指针存储空间，可以将几个盘块组成一个簇，按簇而不按块来分配，这样可以大幅减少查找时间，也可以改善许多算法的磁盘访问时间。代价是增加了内部碎片。

• 显式链接

显式链接将用于链接各物理块的指针，显式存放在内存的一张链接表中，该表在整个磁盘中仅设置一张，称为文件分配表(FAT)。每个表项中存放指向下一个盘块的指针。

文件目录只需记录该文件的起始块号，后续块号通过查FAT得到。

FAT的表项和磁盘块一一对应，通过特殊的数字（例如负数）表示磁盘块是空闲的。操作系统可以通过FAT对磁盘空闲空间进行管理。某进程请求分配磁盘块时，只需要从FAT中找到负数的表项，分配给该进程即可。一个磁盘仅设置一张FAT，在启动时读入内存，并常驻内存。

显式链接的优点：

1. 支持顺序访问，也支持直接访问，要访问第i块，无需访问前i-1块。
2. FAT在系统启动时就读入内存，检索记录也在内存中进行，显著提高检索速度，减少了访问磁盘的次数。

缺点：FAT需要一定的内存空间。

索引分配

• 单级索引分配方式

打开文件时，只需要将对应盘号的编号调入内存即可，不需要调入整个FAT。应该将文件的所有盘块号集中放在一起，当访问到某个文件，将该文件对应的盘块号一起调入内存。这就是索引分配。

索引分配为每个文件分配一个索引块(表)，将分配给该文件的所有盘块号记录在索引块中。

索引分配的优点是支持直接访问，要访问第i块时，索引块的第i个条目指向的便是文件的第i个块。索引分配也不会产生外部碎片。缺点是增加了额外的存储空间开销。

索引块的主要问题是每个文件必须有一个索引块，当文件很小时，仍然会分配一个索引块，导致利用率较低；当文件很大时，盘块号占用若干索引块，此时需要通过链指针将各索引块连起来，但是很低效。

• 多级索引分配方式

当文件太大而导致索引块太多时，应该为这些索引块再建立一级索引，称为主索引。这样便形成了二级索引分配方式，类似多级页表。各层索引的大小不能超过一个磁盘块。

多级索引的优点：极大加快了对大型文件的查找速度。缺点：访问一个盘块时，其所要启动磁盘的次数随着索引次数的增加而增多，即使是对数量较多的小文件也是如此。所以仅采用多级索引，效果并不理想。

• 混合索引分配方式

为了全面照顾小、中、大型文件，可采用混合索引分配方式。

对于小文件，最好将它们的每个盘块地址放入FCB，可以直接从FCB获得盘块地址，称为直接寻址。

对于中型文件，可以采用单级索引分配，从FCB中找到该文件的索引表，获得盘块地址，即一次间址。

对于大型或特大型文件，可以采用多级索引分配，UNIX系统采用的就是这种分配方式。

1. 直接地址。为了提高小文件的检索速度，在索引节点中设置10个直接地址项，用i.addr(0)~i.addr(9)来存放直接地址，即文件数据块的盘块号。假如每个盘块大小为4KB，当文件不大于40KB时可以直接读出全部的盘块号。
2. 一次间接地址。对于中、大型文件，可以利用索引节点中的i.addr(10)来提供一次间址，即一级索引分配。一次间址记录了文件的一次间址块号（索引块号）。索引块存放1024个盘块号，可以表示1K$\times$4KB=4MB大小的文件。因此，同时采用直接地址和一次间址，允许的最大长度为4MB+40KB。
3. 多次间接地址。当文件长度大于4MB+40KB时，还需要利用i.addr(11)来提供二次间址，可以表示1K$\times$1K$\times$4KB=4GB大小的文件，最大长度为4GB+4MB+40KB。同理利用i.addr(12)来提供三次间址，允许的最大长度为4TB+4GB+4MB+40KB。

4.2 目录

4.2.1 目录的基本概念

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

目录管理的基本要求：

从用户的角度，目录在用户需要的文件名和文件之间提供一种映射，所以要实现按名存取；目录存取的效率影响系统性能，要提高对目录的检索速度；在多用户系统中，应该允许多个用户共享一个文件，还需要提供用于控制访问文件的信息。此外，还要允许不同用户对不同文件采用相同的名字，通过树形结构实现目录管理。

4.2.2 目录结构

单级目录结构

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

建立一个新文件时，必须检索所有目录项，保证没有重名的情况。然后再该目录新增一项，将新文件的属性信息填入该项。

当访问一个文件时，先按文件名在该目录查找到相应的FCB，经合法性检查后执行相应的操作。

删除一个文件时，先从该目录找到该文件的目录项，回收该文件占用的存储空间，然后清除该目录项。

单级目录实现了按名存取，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统显然是不适用的。

两级目录结构

可以采用两级方案，将文件目录分成主文件目录(MFD)和用户文件目录(UFD)。

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

当某用户想要访问时，只需要搜索用户对应的UFD，这样解决了不同用户文件的重名问题，也保证了文件的安全。

两级目录结构提高了检索的速度，解决了多用户之间的重名问题，文件系统可以在目录上实现访问限制，但是缺乏灵活性，不能对文件分类。

树形目录结构

将两级目录结构加以推广，就形成了树形目录结构。树形目录结构可以明显提高对目录的检索速度和文件系统的性能。

用户访问文件时，用文件的路径名表示文件，文件路径名是个字符串，从根目录出发的路径称为绝对路径，由当前目录出发的路径称为相对路径。层次较多时，每次从根目录查询会浪费时间（多级磁盘I/O），所以可以为每个进程设置一个当前目录（又称工作目录）。

通常每个用户都有各自的当前目录，登录后自动进入该用户的当前目录。操作系统提供一个专门的系统调用，供用户随时改变当前目录。

树形目录结构可以方便地对文件进行分类，层次结构清晰，也能更有效地进行文件管理和保护。在树形目录中，不同性质、不同用户的文件，可以分别呈现在系统目录树的不同层次或不同子树中，很容易赋予不同的存储权限。

但是，在树形目录查找一个文件，需要按路径逐级访问中间节点，增加了磁盘访问次数，影响查询速度。

现在大多数操作系统都采用了树形目录结构。

无环图目录结构

树形目录结构便于实现文件分类，但不便于实现文件共享。为此在树形目录结构的基础上添加一些指向同一节点的有向边，使目录称为一个有向无环图。这种结构允许目录共享子目录或文件，同一个文件或子目录可以出现在两个或多个目录中。

为每个共享节点设置一个共享计数器，仅当计数器为0时删除该节点，否则仅删除请求用户的共享链。

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

4.2.3 目录的操作

1. 搜索。
2. 创建文件。
3. 删除文件。
4. 创建目录。
5. 删除目录。有两种方式：不删除非空目录，删除时要先删除目录中的所有文件，并递归删除子目录；可删除非空目录，目录中的文件和子目录同时被删除。
6. 移动目录。
7. 显示目录。
8. 修改目录。

4.2.4 目录实现

实现目录的目的是为了查找，有线性列表和哈希表两种方式。

线性列表

采用文件名和数据块指针的线性列表。需要重用目录项时可以选择将目录项标记为不再使用，也可以加到空闲目录项的列表上，还可以将目录的最后一个目录项复制到空闲位置，并减少目录的长度。

实现比较简单，但是查找比较费时。采用链表结构可以减少删除文件的时间。

哈希表

可以采用哈希表，根据文件名得到一个值，并返回指向线性列表的指针。查找非常迅速，插入和删除比较简单，但是要采取措施避免冲突。

目录查询是在磁盘上反复搜索完成的，需要不断地I/O操作，开销较大。为此需要将当前使用的文件目录复制到内存。

4.2.5 文件共享

基于索引节点的共享方式

硬链接是基于索引节点的共享方式，将文件的物理地址和属性等信息不再放在目录项中，而是放在索引节点中，在文件目录中只设置文件名和指向索引节点的指针。count=2时表示有两个用户目录项链接到本文件上。

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

为了使用户B能共享用户A的一个文件F，可以由系统创建一个LINK类型的新文件L，并将文件L写进用户B的目录，实现B的目录与F的链接。文件L只含有F的路径名，这种方法被称为符号链接或软链接。当B访问L，操作系统看到文件类型属于LINK，根据其中记录的路径查询文件F，实现文件共享。

使用符号链方式共享文件时，只有文件主才拥有指向其索引节点的指针。共享该文件的其他用户只有该文件的路径名，这样就不会发生文件主删除共享文件后留下悬空指针的问题。如果删除共享文件，其他用户只会访问失败，然后将符号链删除。

其他用户读共享文件时，系统根据路径名查找目录，直到找到该文件的索引节点。每次访问共享链接可能需要多次读盘，增大了访问开销；符号链接也是一个文件，其索引节点也需要耗费一定的磁盘空间。

利用符号链使用网络文件共享时，只需提供该文件所在机器的网络地址以及文件路径名。

硬链接就是多个指针指向一个索引节点，保证只要还有一个指针指向索引节点，节点就不能删除。

软链接就是将到达共享文件的路径保存下来，当要访问文件时，根据路径寻找文件。

硬链接的查找速度要比软链接快。

4.3 文件系统

4.3.1 文件系统结构（不考察）

文件系统有两个不同的设计问题。第一是定义文件系统的用户接口，涉及定义文件及其属性、所允许的文件操作、如何组织文件的目录结构。第二个问题是创建算法和数据结构。以便映射逻辑文件系统到物理外存设备。

不同操作系统的文件系统层次结构也不尽相同。

• I/O控制层

包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息。设备驱动程序将输入命令翻译成底层硬件指令，硬件控制器利用指令与系统交互。设备驱动程序告诉I/O控制器对设备的什么位置做什么。

• 基本文件系统

向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块。每个物理块由磁盘地址标识。该层也管理内存缓冲区，并保存各种文件系统、目录和数据块的缓存。在进行磁盘块传输前，分配合适的缓冲区，并对缓冲区进行管理。

• 文件组织模块

组织文件及其逻辑块和物理块。文件组织模块可以将文件的逻辑块地址转换为物理块地址，每个文件的逻辑块从0到N编号，它与数据的物理块不匹配，需要通过转换来定位。文件组织模块还包括空闲空间管理器，以跟踪未分配的块，根据需求提供给文件组织模块。

• 逻辑文件系统

用于管理文件系统中的元数据信息。元数据包括文件系统的所有结构，而不包括实际数据（或文件内容）。逻辑文件系统管理目录结构，以便根据给定文件名为文件组织模块提供所需要的信息。它通过文件控制块来维护文件结构。逻辑文件系统还负责文件保护。

4.3.2 文件系统布局

文件系统在磁盘中的结构

文件系统存放在磁盘上，磁盘有多个分区，每个分区有一个独立的文件系统，可能包含以下信息：启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。

一个可能的文件系统布局简单描述如下：

1. 主引导记录(MBR)，位于磁盘的0号扇区，用于引导计算机，MBR后面是分区表，该表给出每个分区的起始和结束地址。第一个分区被标记为活动分区。计算机启动时，BIOS读入并执行MBR。MBR做的第一件事就是确定活动分区，读入它的第一块，即引导块。
2. 引导块，MBR执行引导块的程序后，该程序启动该分区中的操作系统。每个分区都是统一从一个引导块开始，即使它不含有一个可启动的操作系统，不排除以后会在该分区装一个操作系统。Windows统称之为分区引导扇区。
3. 超级块，包含文件系统的所有关键信息，在计算机启动时，或者在文件系统首次使用时，超级块会被读入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等。
4. 文件系统中空闲块的信息，可以用位示图或指针链接的形式给出。后面也许跟的是一组i节点，每个文件对应一个节点。接着可能是根目录。
5. 最后磁盘的其他部分存放了其他所有的目录和文件。

文件系统在内存中的结构

内存中的数据在安装文件系统时被加载，在文件系统操作时被更新，在卸载时被丢弃。他们可能包括：

1. 内存中的安装表，包含每个已安装文件系统分区的有关信息。
2. 内存中的目录结构的缓存，包含最近访问目录的信息。
3. 整个系统的打开文件表，包含每个打开文件的FCB副本、打开计数和其他信息。
4. 每个进程的打开文件表，包含进程打开文件的文件描述符（文件句柄）和指向整个系统的打开文件表中对应表项的指针。

4.3.3 外存空闲空间管理

包含文件系统的分区通常称为卷(volume)。卷可以是磁盘的一个部分，也可以是整个磁盘，还可以是多个磁盘组成RAID集。

在一个卷中，存放文件数据的空间（文件区）和FCB的空间（目录区）是分离的。操作系统中一般都有很多不同的文件管理模块，通过它们可以访问不同格式的卷中的文件。

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

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

空闲表法

空闲表法属于连续分配方式，与内存的动态分区类似，为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，包含表项序号、空闲区的第一个空闲盘块号、空闲盘块数等信息，将所有空闲区按其起始盘块号递增的次序排列。

盘块的分配：

采用首次适应算法、最佳适应算法等。例如，为某新创建的文件分配空闲块时，先顺序检索空闲盘块表的各表项，直到找到第一个能满足要求的空闲区，再将盘区分配给用户，然后修改空闲盘块表。

盘块的回收：

在对用户所释放的存储空间进行回收时，也采取类似于内存回收的办法，考虑回收区是否与空闲盘块表的插入点前区和后区邻接，与相邻的合并。

空闲表法的优点是具有较高的分配速度，可以减少磁盘的I/O频率，对于较小的文件，可以采用连续分配的方式为文件分配几个相邻的盘块。

空闲链表法

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

• 空闲盘块链

空闲盘块链是指将磁盘上的所有空闲空间以盘块为单位拉成一条链，每个盘块都有指向下一个空闲盘块的指针。

用户请求分配时，从链头开始依次取下适当数目的空闲盘块；用户释放存储空间时，依次将盘块分配到链表尾。

空闲盘块链的优点是分配和回收一个盘块的过程非常简单。缺点是为一个文件分配盘块需要重复操作很多次，效率比较低；而且以盘块为单位，空闲盘块链比较长。

• 空闲盘区链

空闲盘区链是指将是所有空闲盘区拉成一条链，每个盘区包含若干相邻的盘块。每个盘区含有下一个盘区的指针和本盘区的盘块数。分配盘区的方法和内存动态分区分配类似，通常采用首次适应算法。回收盘区时也要和相邻盘区合并。

空闲盘区链的优点和空闲盘块链相反，优点是分配和回收效率比较高，且空闲盘区链较短；缺点是分配和回收的过程比较复杂。

位示图法（最常考）

位示图利用二进制的一位来表示磁盘中的一个盘块使用的情况，每个盘块都有一位对应，为0时表示空闲，为1时表示已分配。

盘块的分配：

1. 顺序扫描位示图，找出一个或一组为0的盘块。
2. 计算对应盘块号：(n为每行位数)
   $$
   b=n(i-1)+j
   $$
3. 修改位示图，令map[i,j] = 1。

盘块的回收：

1. 将回收的盘块号转换成行号和列号：
   $$
   i=(b-1) DIV\space n+1 \
   j=(b-1) MOD\space n+1
   $$
2. 令map[i,j] = 0。

位示图法的优点时很容易在图中找到一个或一组邻接的空闲盘块，位示图比较小，可以保存在内存中，节省磁盘启动的开销。

位示图法的问题是位示图大小会随着磁盘容量的增加而增大，常用于小型计算机。

成组链接法

空闲表法和空闲链表法都不适合大型文件系统。

成组链接法的思想是：将空闲盘块分为若干组，每组的第一个盘块记录下一组的空闲盘块总数和本组的空闲盘块号，由各组的第一个盘块链接成一条链。第一组的空闲盘块总数和空闲盘块号保存在内存的专用栈中，称为空闲盘块号栈。

每组的第一块作为索引块，然后将这些索引块链接起来。

盘块的分配：

根据空闲盘块号的指针，将对应的盘块分配给用户，同时移动指针，如果指针指向栈底的盘块号，由于该盘块号对应盘块保存的是下一组的空闲盘块号，则将该盘块的内容读入栈中，作为新的空闲盘块号的内容，并将原栈底盘块号对应的盘块分配出去，最后将栈中的空闲盘块数-1。

盘块的回收：

将回收的盘块存入空闲盘块号栈的内部，同时移动指针，将栈中的空闲盘块数+1。当空闲数到达100时，表示栈已满，将现有的100个空闲盘块号存入新回收的盘块，并将新回收的盘块作为新栈底，并将空闲盘块数置为1。

表示空闲空间的位向量表或空闲盘块号栈，以及卷中的目录区、文件区划分信息都要存放在磁盘中，一般在卷头位置，在UNIX中称为超级块。对卷中的文件进行操作前，超级块要先读入内存，并且经常保持主存超级块和磁盘卷中超级块的一致性。

4.3.4 虚拟文件系统

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

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

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

• 超级块对象

表示一个已安装（或者称挂载）的特定文件系统。超级块对象对应于磁盘上特定扇区的文件系统超级块，用于存储已安装文件系统的元信息。操作方法包含一系列在超级块对象上调用的函数，主要有分配inode、销毁inode、读inode、写inode等。

• 索引节点对象

表示一个特定的文件，索引节点和文件是一对一的关系，只有文件被访问时才会在内存中创建索引节点对象。每个索引节点都会复制磁盘索引节点的数据，还提供许多操作函数，比如创建新索引节点、创建硬链接、创建新目录等。

• 目录项对象

表示一个特定的目录项，目录项对象是一个路径的组成部分，包含指向关联索引节点的指针，指向父目录和子目录的指针。目录项对象在磁盘上没有对应的数据结构，而是在VFS遍历路径的过程中，将他们逐个解析成目录项对象的。

• 文件对象

表示一个与进程相关的已打开文件。文件对象仅是进程视角上代表已打开的文件，它反过来指向其索引节点，还包含该文件相关联的目录项对象，包含该文件的文件系统、文件指针等，还有一系列操作函数。

当进程发起一个面向文件的系统调用时，操作系统调用VFS的一个函数，该函数调用目标文件系统的相应函数，将文件系统请求转换为面向设备的指令。

对用户来说，不必关心不同文件系统的具体实现细节，只需要对一个虚拟的文件操作界面进行操作。VFS对每个文件系统的所有细节进行抽象，使之在进程中看起来都是相同的。（通过将文件复制到vnode节点实现）

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

4.3.5 文件系统挂载

文件系统在使用前必须先安装，也称挂载(Mounting)。将设备中的文件系统挂载到某个目录后，就可以通过这个目录访问设备上的文件。设备指的是逻辑上的设备，一个磁盘的不同分区都可视为不同的设备。