其他篇之操作系统——文件管理

操作系统之文件管理

文件管理是操作系统的功能之一，由于系统的内存有限并且不能长期存储，故平时总是把数据以文件的形式存储在外存中，需要时再将其调入内存。文件管理的主要内容有：

（1）文件系统基础：包括基本概念、文件操作、文件的逻辑结构、目录结构、文件共享和文件保护；

（2）文件系统实现：包括文件系统层次结构、目录实现、文件实现；

（3）磁盘组织与管理：包括磁盘的结构、磁盘调度与管理。

现代OS几乎都是通过文件系统来组织和管理在计算机中所存储的大量程序和数据的，文件系统的管理功能是通过把他所管理的程序和数据组织成一系列文件的方法实现的。在系统运行时，操作系统以进程为单位进行资源的调度和分配，而在用户的输入、输出中，则是以文件为单位。文件是指具有文件名的若干相关元素的集合，元素通常是记录，而记录是一些有意义的数据项的集合。

（1）数据项：数据项是文件系统中最低级的数据组织形式，包括：

·基本数据项：用于描述一个对象的某个属性的字段，是数据中可命名的最小逻辑数据单位，即原子数据；

·组合数据项：由多个基本数据项组成。

（2）记录：记录是一组相关的数据项的集合，用于描述一个对象的某方面的属性信息，为了能够唯一标识一个记录，需要在记录中确定一个数据项或集合数据项作为关键字，以此来唯一标识一个记录。

（3）文件：文件是指具有文件名的一组相关元素的集合，文件是文件系统的最大数据单位，逻辑上可分为：

·有结构文件：由一组相关记录组成，又称记录式文件；

·无结构文件：可看作一个字符流，比如一个二进制文件或字符文件，又称流式文件。

文件有自己的属性，这根据系统的不同而有所不同，但通常具有以下属性：

（1）名称：文件名称唯一，以容易读取的形式保存；

（2）标识符：标识文件系统内文件的唯一标签，通常为数字，是对用户不可读的一种内部名称；

（3）类型：被支持不同类型的文件系统所使用；

（4）位置：指向设备和设备上文件的指针；

（5）大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值；

（6）保护：对文件进行保护的访问控制信息；

（7）时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。

总述，所有文件的信息都保存在目录结构中，而目录结构也保存在外存上，文件及其相关信息在需要时再调入内存，通常，目录条目包括文件名称及其唯一标识符，而标识符定位其他属性的信息。

（1）创建文件：创建文件有两个必要步骤，一是文件系统为新文件分配必要的外存空间；二是在文件系统中为新文件建立一个目录项，记录新文件的文件名和在外存中的地址等相关信息。

（2）删除文件：当不再需要某文件时，则将其从文件系统中删除，在删除时，先从目录中找到该文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。

（3）读文件：读取文件内容时，执行一个系统调用，需指明文件名和要读入的文件块的内存地址，然后系统查找目录，找到指定目录项，从中得到被读文件在外存中的地址。在目录项中，还有一个指针用于对文件进行读/写，每次发生读/写操作时，更新读/写指针。

（4）写文件：在文件中写入内容时，执行一个系统调用，需指明文件名和要写入的文件块的内存地址，然后系统查找目录，找到指定目录项，从中得到写文件在外存中的地址，再利用写指针进行写操作。

（5）截断文件：如果一个文件的内容已经陈旧需要全部更新时，一种方法是删除此文件然后新建，另一种方法则是截断文件，即允许文件名和所有属性不变时，可将原有文件的长度设为0，放弃原有文件的内容，并释放其空间。

（6）文件重定位（文件寻址）：按某条件搜索目录，将当前文件位置设置为给定值，但不会读、写文件。

当用户要求对一个文件进行多次读/写或其他操作时，每次都要从检索目录开始，为了避免多次重复地检索目录，在大多数OS中都引入了“打开”这一系统调用。即在用户首次使用某文件时，使用系统调用open，将指定文件的属性（包括在外存上的物理地址）从外存拷贝到内存打开文件目录表（open-file table）的条目中，并将该文件的编号（又称索引）返回给用户。

整个系统表包含进程相关信息，如文件在磁盘的位置、访问日期和大小，一个进程打开一个文件，系统打开文件表就会为打开的文件增加相应的条目。通常，系统打开文件表的每个文件时，还用一个文件打开计数器（Open Count），来记录有多少个进程打开了该文件，每个关闭操作close则使count递减，当打开计数器为0时表示该文件不再被使用，系统将回收分配给该文件的内存空间等资源。若文件被修改过，则将其写回外存，并且删除打开文件表中的相应条目，最后释放文件的文件控制块（File-Control-Block,FCB）。

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

（1）文件指针：系统跟踪上次读写位置作为当前文件位置指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存；

（2）文件打开计数：因为多个进程可能打开同一文件，所以系统在删除打开文件表中的条目时，必须等待最后一个进程关闭该文件，即打开计数器为0时，系统关闭该文件，删除表中相应条目；文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间会不够用；

（3）文件磁盘位置：该信息保存在内存中以免每个操作都从磁盘中读取；

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

所谓逻辑结构，是从用户角度出发观察到的文件组织形式，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称文件组织；物理结构是指文件在外存上的存储组织形式，与存储介质和外存分配方式有关。

1.无结构文件（流式文件）

无结构文件是最简单的文件组织形式，其长度以字节（Byte）为单位。由于没有结构，因而对记录的访问只能通过穷举搜索的方式，故对大多数应用不适用，但字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于釆用字符流的无结构方式，如源程序文件、可执行文件、库函数等。

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

有结构文件是由一个以上的记录构成的文件，故又称记录式文件。每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项，记录分为定长记录（文件中所有记录的长度都是相同的，所有记录中的各数据项都处在记录中相同的位置，具有相同的顺序和长度）和变长记录（文件中个记录的长度不相同，可能由于一个记录中所包含的数据项目并不相同）。按记录的组织形式可分为：

（1）顺序文件

顺序文件有两种结构：

·串结构：记录之间的顺序与关键字无关，通常按存入的时间先后顺序进行排列，最先存入的作为第1个记录，其次为第2个记录，以此类推；

·顺序结构：即文件中的记录按关键字顺序进行排列；顺序记录的最佳应用场合是对记录进行批量操作时，此外只有顺序文件才能存储在磁带上，并能有效工作，但对顺序文件进行增加或删除单个记录操作比较困难。

（2）索引文件

对于定长记录文件，可以方便的实现顺序存取和直接存取，然而对于变长记录就很难实现，因此，可为变长记录文件建立一张索引表，对于主文件中的每个记录，在索引表中设有一个表项用来存储该记录的长度m及指向该记录的指针ptr（指向逻辑地址空间的首址）。由于索引表是按记录键排序的，因此索引表本身是一个定长记录的顺序文件。

如下图所示，

图-6.1

对于定长记录文件，如果要查找第 i 个记录，可直接根据下式计算来获得第 i 个记录相对于第一个记录的地址：

附-图

然而，对于可变长记录的文件，要查找第 i 个记录时，必须顺序地查找前 i - 1 个记录，从而获得相应记录的长度 L，然后才能按下式计算出第 i 个记录的首址：

附-图

注：假定每个记录前用一个字节指明该记录的长度。

在对索引文件进行检索时，首先根据用户提供的关键字，利用折半查找检索索引表，找到相应的表项，再利用该表项给出的指向记录的指针值，访问所需的记录。每当要向索引文件中增加一个新纪录时，便须对索引表进行修改。索引表的问题在于除了有主文件外，还需要配置一张索引表，每个记录需要有一个索引项，因此提高了存储费用。

（3）索引顺序文件

索引顺序文件是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第1个记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。

如下图所示，主文件名包含姓名和其他数据项。姓名为关键字，索引表中为每组的第一个记录（不是每个记录）的关键字值，用指针指向主文件中该记录的起始位置。索引表只包含关键字和指针两个数据项，所有姓名关键字递增排列。主文件中记录分组排列，同一个组中关键字可以无序，但组与组之间关键字必须有序。查找一个记录时，通过索引表找到其所在的组，然后在该组中使用顺序查找就能很快地找到记录。

图-6.2

（4）直接文件和散列文件（又称哈希文件，Hash File）

直接文件是根据给定的记录键值，直接获得指定记录的物理地址，即记录键值本身就决定了记录的物理地址，这种由记录键值到记录物理地址的转换被称为键值转换；

哈希文件是利用Hash函数将记录键值转换为相应的记录地址，为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。

注：直接文件和散列文件这种映射结构不同于顺序文件和索引文件，没有顺序的特性。

1.文件控制块

同进程管理一样，为了实现目录管理，操纵系统引入了文件控制块的数据结构。文件控制块（FCB）是用来存放控制文件所需的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项，为了创建一个新文件，系统将分配一个FCB并存放在文件目录中，成为目录项。FCB主要包含以下信息：

（1）基本信息：如文件名、文件的物理位置、文件的逻辑结构（指示文件是流式文件还是记录式文件、记录数，文件是定长还是变长记录）、文件的物理结构等（指示文件是顺序文件、链式文件还是索引文件）；

（2）存取控制信息：包括文件主的存取权限、核准用户的存取权限及一般用户的存取权限；

（3）使用信息：如文件建立时间、修改时间等。

2.索引结点

在检索目录文件的过程中，只用到了文件名，仅当找到一个目录项（查找文件名与目录项中文件名匹配）时，才需要从该目录项中读出该文件的物理地址。也就是说，在检索目录时，文件的其他描述信息不会用到，也不需调入内存，因此，有的系统（如UNIX，见下表）釆用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称为 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针构成。

一个FCB的大小是64字节，盘块大小是1KB，则在每个盘块中可以存放16个FCB（注意，FCB必须连续存放）。而在UNIX系统中一个目录项仅占16字节，其中14字节是文件名，2字节是 i 结点指针。在1KB的盘块中可存放64个目录项。这样，可使查找文件时平均启动磁盘次数减少到原来的1/4，大大节省了系统开销。存放在磁盘上的索引结点称为磁盘索引结点，UNIX中的每个文件都有一个唯一的磁盘索引结点，主要包括以下几个方面：

（1）文件主标识符：拥有该文件的个人或小组的标识符；

（2）文件类型：普通文件、目录文件或特殊文件；

（3）存取权限：各类用户对该文件的存取权限；

（4）文件物理地址：每个索引结点中含有13个地址项，即 iaddr(0) ~ iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号；

（5）文件长度：以字节为单位；

（6）文件链接计数：在本文件系统中所有指向该文件的文件名的指针计数；

（7）文件存取时间：本文件最近被进程存取的时间、最近被修改的时间以及索引结点最近被修改的时间。

文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用。在内存索引结点中又增加了以下内容：

（1）索引结点编号：用于标识内存索引结点；

（2）状态：指示 i 结点是否上锁或被修改；

（3）访问计数：每当有进程访问 i 结点时，访问计数加1，访问结束时减1；

（4）逻辑设备号：文件所属文件系统的逻辑设备号；

（5）链接指针：设置分别指向空闲链表和散列队列的指针。

文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块，在查找的过程中，先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所给定的文件名和目录项中的文件名逐一对比。若未找到指定文件，则再将下一个盘块中的目录项调入内存。文件的目录结构类型有：单级、两级、多级（树形）、无环图。对目录的管理要求如下：

（1）实现按名存取：即用户只须向系统提供所需访问的文件的名字，便能够快速准确地找到指定文件在外存上的存储位置，这是目录管理中最基本的功能；

（2）提高目录检索速度：通过合理地组织目录结构的方法，可加快对目录的检索速度，从而提高对文件的存取速度；

（3）文件共享：在多用户系统中，应该允许用户共享一个文件；

（4）允许文件重名：系统应允许不同用户对不同文件采用相同的名字，以便用户按照自己的习惯给文件命名和使用文件。

1.单级目录结构

在整个系统中只建立一张目录表，每个文件占一个目录项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址、状态位（表示目录项是否空闲）等。

图-8.1

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

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

2.两级目录结构

单级目录不允许文件“重名”，可以考虑釆用两级方案，将文件目录分成主文件目录(Master-Fill-Directory, MFD)和用户文件目录（User-File-Directory, UFD)两级，如下图所示。

图-8.2

说明：

主文件目录项记录用户名及相应用户文件目录所在的存储位置；

用户文件目录项记录该用户文件的FCB信息。

两级目录克服了单级目录的缺点，具有如下优点：

（1）提高检索速度（如果在主目录中有 n 个子目录，每个用户目录最多为 m 个目录项，则查找一个指定的目录项时，最多只需要检索 n + m 个目录项）；

（2）在不同的用户目录中，可以使用相同的文件名（只要在用户自己的UFD中，每个文件名都是唯一的即可）；

（3）将不同用户的文件目录分离，也在一定程度上保证了文件的安全性；

但是，两级目录结构缺乏灵活性，不能对文件进行分类。

3.多级目录结构（树形目录结构）

对于大型文件系统，通常采用三级或三级以上的目录结构，以提高对目录的检索速度和文件系统的性能。多级目录结构又称为树形目录结构，主目录被称为根目录，把数据文件称为树叶，其他的目录均作为树的结点。

图-8.3

说明：

（1）方框代表目录文件，圆圈代表数据文件；

（2）主目录中有三个用户总目录A、B、C，在B用户的总目录B中，又包括三个分目录F、E、D，其中每个分目录中又包含多个文件；

（3）为提高系统的灵活性，应该允许在一个目录文件中的目录项既可以是作为目录文件的FCB，也可以是数据文件的FCB，这一信息可用目录项中的一位来指示。如用户A总目录中，目录项A是目录文件FCB，而目录项B和D则是数据文件的FCB。

在树形目录结构中，从根目录到任何数据文件，都只有一条唯一的通路，在该路径上从树的根开始，把全部目录文件名和数据文件名依次用"/"连接起来，即构成该数据文件的路径名，系统中的每个文件都有唯一的路径名。例如，用户B访问文件J，则使用路径名“/B/F/J”来访问。

当一个文件系统含有很多级时，每访问一个文件，都要使用从树根开始直到树叶（数据文件）为止的、包含各中间节点（目录）的全路径名，这非常麻烦，可以为每个进程设置一个当前目录，又称为工作目录，进程对各文件的访问都相对于当前目录进行。把从当前目录开始直到数据文件为止所构成的路径名称为相对路径名，而把从树根开始的路径名称为绝对路径名。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，在树形目录中查找一个文件，需要按路径名逐级访问中间结点，这就增加了磁盘访问次数，无疑将影响查询速度。

4.无环图目录结构

树形目录结构可便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上增加了一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享，如下图所示：

图-8.4

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

说明：

共享文件（或目录）不同于文件拷贝（副本），例如有两个文件拷贝，每个程序员看到的是拷贝而不是原件；如果其中一个文件拷贝被修改，另一个程序员的拷贝也不会有改变。而对于共享文件，只存在一个真正文件，任何改变都会为其他用户所见。无环图目录结构方便地实现了文件的共享,但使得系统的管理变得更加复杂。

当用户要访问一个已存在的文件时，系统首先利用用户提供的文件名对目录进行检索，找出该文件的文件控制块或对应索引结点，然后，根据FCB或索引结点中所记录的文件物理地址（盘块号），换算出文件在磁盘上的物理位置，最后，再通过磁盘驱动程序，将所需文件读入内存。目前常用的方式有线性检索法和Hash方法。

1.线性检索法

其又称为顺序检索法，在树形目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找，假定用户给定的文件路径名为“/usr/ast/mbox”，则查找过程如下：

图-9.1

说明：

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

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

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

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

2.Hash方法

系统利用用户提供的文件名将其转换为文件目录的索引值，再利用该索引值到目录中去查找，由此提高了检索速度。

文件共享使多个用户（进程）共享同一份文件，系统中只需保留该文件的一份副本。如果系统不能提供共享功能，那么每个需要该文件的用户都要有各自的副本，会造成对存储空间的极大浪费。随着计算机技术的发展，文件共享的范围已由单机系统发展到多机系统，进而通过网络扩展到全球，这些文件的分享是通过分布式文件系统、远程文件系统、分布式信息系统实现的。这些系统允许多个客户通过C/S模型共享网络中的服务器文件。

文件共享的方法有：

1.绕道法

在这种情况下需要访问共享文件都要从当前文件位置出发找到共享文件，如果当前目录下没有共享文件，就会回溯到与共享文件交叉的目录下，具体过程可按下图理解：

图-10.1

这样查找共享文件的弊端就是每次我们访问共享文件可能需要回溯多级目录，搜索速度较慢。

2.链接法

有一个根目录用来记录用户的信息，每个用户都有自己的文件夹，当一个用户有共享文件的时候，其他用户需要共享该文件时只需要把对应目录的指针指向该共享文件的目录即可，如下图所示：

图-10.2

3.基于索引结点的共享方式（硬链接）

在这种情况下，文件的属性和文件的地址不再放在文件的目录中，而是存在索引中，文件目录中存放着文件名和指向索引的指针。Linux操作系统中把这种索引的结点称为 Inode 结点。在索引的结点中还有一个计数器，用来统计文件被多少用户访问。如下图所示：

图-10.3

当 count = 1 时候，创建文件的用户才能删除文件，否则不能删除文件，这是在这种共享文件系统下系统的规定，因为如果建立共享文件的用户删除了共享文件，系统又在共享的位置建立了新的文件，这样其他用户在共享文件的时候就会访问成了其他文件，失去了共享文件的意义。

因此，创建共享文件的用户在不再需要此文件时，不能直接删除，只是将该文件的 count 减1，然后删除自己目录中的相应目录项。其他用户仍可以使用该共享文件，当 count = 0 时，表示没有用户使用该文件，系统将负责删除该文件。由此引出了下一种文件共享方式。

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

当用户需要访问共享文件的时候，由系统生成一个链接的文件，用来指向共享文件的目录，其他用户根据这个链接文件来访问共享文件，这时候如果文件所有者删除了文件或者修改了文件，就需要其他用户重新生成链接文件，原来的链接就会失效。如下图所示：

图-10.4

在利用符号链方式实现文件共享时，只有文件的拥有者才拥有指向其索引结点的指针。而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，就不会发生在文件主删除一共享文件后留下悬空指针的情况。

符号链方式有一个很大的优点，即网络共享只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。但也仍然存在问题，例如：一个文件釆用符号链方式共享，当文件拥有者将其删除，而在共享的其他用户使用其符号链接访问该文件之前，又有人在同一路径下创建了另一个具有同样名称的文件，则该符号链将仍然有效，但访问的文件已经改变，从而导致错误。

5.基本文件目录

图-10.5

可以看到wang用户的符号目录中的tt.c指向了用户zhang的b.c文件，此时用户zhang删除了6号对应的b.c文件之后，用户wang再去访问的时候就会发现id为6的地址发生了变化，就会重新更新tt.c对应的id，这种检索方式不仅效率高，而且占用的内存小。

由于磁盘具有可直接访问的特性，故用磁盘来存放文件时，具有很大的灵活性，而文件的物理结构与外存分配方式有关，在采用连续分配方式时的文件物理结构是顺序式的文件结构，在采用链接分配方式将形成链接式文件结构，而索引分配方式将形成索引式文件结构。

1.连续分配

连续分配要求为每个文件分配一组相邻接的盘块，一组盘块地址定义了磁盘上的一段线性地址。采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。如下图所示：

图-11.1

如同动态分配分区分配一样，随着文件建立时空间的分配和文件删除时的空间回收，将使磁盘空间被分割成许多小块，这些小块的连续区已难以存储文件，此即外存的碎片，同样，可以使用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼成一大片连续的存储空间。

（1）连续分配的优点有：

> 顺序访问速度快：因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头移动距离最少，这种对文件访问的速度是几种存储空间分配方式中最高的一种。

（2）连续分配的缺点：

> 要求有连续的存储空间，要为每个文件分配一段连续的存储空间，这样，便会产生许多外存碎片，严重地降低了外存空间利用率，定期紧凑会花费大量的机器时间。

> 必须事先知道文件的长度，然后根据其大小，在存储空间中找出一块大小足够的存储区，将文件装入，对于动态增长的文件非常低效。

2.链接分配

如果将一个逻辑文件存储到外存上，并不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块中，这样就可以消除连续分配的缺点。采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散盘块链接成一个链表，把这样形成的物理文件称为链接文件。链接分配采取离散分配方式，消除了外部碎片，故而显著地提高了外存空间的利用率，并且对文件的增、删、改、查十分方便，链接方式可分为隐式链接和显示链接两种形式。

（1）隐式链接：在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。如下图所示：

图-11.2.1

说明：第9个盘块指向第16个盘块，第16个盘块指向第1个盘块，第1个盘块指向第10个盘块，第10个盘块指向第25个盘块（结束块）。

隐式链接分配的主要问题在于：其只适合于顺序访问，对随机访问的效率及其低效。此外，其可靠性较差，任何一个指针出现问题，都会导致整个链的断开。可以将几个盘块组成一个簇，然后以簇为单位进行分配，会减少查找指定块的时间，但是会增加内部碎片。

（2）显式链接：把用于链接文件各物理块的指针，显式的放在内存的一张链接表中，该表在整个磁盘仅设置一张。如下图所示：

图-11.2.2

说明：表的序号从0开始，直至N - 1，N为盘块总数，在每个表项中存放链接指针，即下一个盘块号，在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应的文件的FCB(File Control Block)的物理地址字段中，由于查找记录的过程是在内存中进行的，因而提高了检索速度，减少了访问磁盘的次数，由于分配给文件的所有盘块号都在该表中，故把该表称为文件分配表FAT（File Allocation Table）。

综述，链接分配的问题有：

> 不能支持高效的直接存储（要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找很多盘块号）；

> FAT需要占用较大的内存空间（由于一个文件所占用的盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证FAT中找到一个文件的所有盘块号，当磁盘容量较大时，FAT占用的容量更大）。

3.索引分配

事实上，在打开某个文件时，只需要把该文件占用的盘块号的编号调入内存即可，完全没有必要把整个FAT调入内存，为此，应该将每个文件所对应的盘块号集中地放在一起，索引分配方式就是基于这种想法所形成的一种分配方式。其为每个文件分配一个索引块（表），再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多磁盘块号的数组。在建立一个文件时，只需要在为之建立的目录项中填上指向该索引块的指针（单级索引）。如下图所示：

图-11.3.1

说明：索引方式支持直接访问，可在索引块中找到第 i 个盘块，索引方式也不会产生外部碎片，当文件较大时，索引分配方式要优于链接分配方式。其主要问题在于：可能需要花费较多的外存空间，每当建立一个文件时，便须为之分配一个索引块，将分配给该文件的所有盘块号记录其中。对于小文件而言，索引块的利用率非常低。

当OS为一个大文件分配磁盘空间时，如果所分配的盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中，以此类推，然后再通过链指针将各索引块按序链接起来，当文件太大时，索引块太多，效率是低效的。此时，应该为这些索引块再建立一级索引，称为第一级索引，还可再建立索引，称为第二级索引等等，称为多级索引分配。如下图所示：

图-11.3.2

4.混合索引分配

简单说，就是将多种索引分配方式相结合而形成的一种分配方式，即根据文件所占空间大小选择适当的分配方式。

例如：直接地址（在索引结点中设置10个直接地址项，每项中所存放的是该文件数据所在盘块的盘块号，假如每个盘块大小为4KB，当文件不大于40KB时，可以直接从索引结点中读出该文件的全部盘号）；一次间接地址（利用索引结点中的地址项来提供一次间接地址，其实质就是一级索引分配方式，在一次间址块中可存放1K个盘块号，允许最大文件为4MB）；多次间接地址（当文件大于4MB + 40KB时，系统采用二次间址分配方式，其实质是两级索引分配方式，采用二次间址的最大文件大小为4GB，同理，可采用三次间接地址，允许文件最大大小为4TB）。如下图所示：

图-11.4

1.空闲表法

空闲表法属于连续分配方式，与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项。其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等，然后将所有空闲区按其起始盘块号递增排列。如下表所示：

图-12.1

空闲盘区的分配与内存的动态分配类似，同样采用首次适应算法、循环首次适应算法等。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应该予以合并。当文件较小时，采用连续分配方式；当文件较大时，可采用离散分配方式。

2.空闲链表法

空闲链表法是将所有空闲盘区拉成一条空闲链，把链表分成两种形式：空闲盘块链和空闲盘区链。

（1）空闲盘块链：这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链，当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户；当删除文件而释放空间时，系统将回收的盘块依次插入空闲盘块链的末尾。其优点是用于分配和回收一个盘块的过程简单，但在为文件分配盘块时，可能要重复操作多次。

（2）空闲盘区链：这是将磁盘上的所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链，在每个盘区上除了含有指向下一个空闲盘区的指针外，还应有能指明本盘区大小（盘块数）的信息。盘区分配与内存的动态分配类似，可采用首次适应算法，在回收盘区时，同样也要将回收区和相邻接的空闲盘区相合并，在采用首次适应算法时，可以采用显式链接法提高检索速度，在内存中为空闲盘区建立一张链表。

补充说明：

（1）首次适应算法：首次适应算法从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

（2）循环首次适应算法：该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀。

3.位示图法

利用二进制的一位表示磁盘中的一个盘块的使用情况，当其值为 0 时，表示对应的盘块空闲；为 1 时，表示已经分配。磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图，通常可用 m * n 个位数来构成位示图，并使 m * n 等于磁盘的总块数。如下图所示：

图-12.2

（1）对盘块的分配步骤：

>A.顺序扫描位示图，从找找出一个或一组值为 0 的二进制位；

>B.将找到的一个或一组二进制位转换成对应的盘块号；

>C.修改位示图。

（2）对盘块的回收步骤：

>A.将回收盘块的盘块号转换成位示图中的行号和列号；

>B.修改位示图。

此方法的优点在于从位示图中很容易找到一个或一组相邻接的空闲盘块，此外，由于位示图很小，占用空间少，因而可将其保存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，节省磁盘启动时间。

4.成组链接法

空闲表法和空闲链表法都不适用于大型系统，因为这会使空闲表或空闲链表很长，在UNIX中采用的成组链接法，结合了这两种方法。

（1）空闲盘块的组织：空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号（最多含100个号），以及栈中尚有的空闲盘块数N，顺便指出，N兼做栈顶指针使用，栈是临界资源，系统设置一把锁供进程互斥访问。其中，S.free(0)是栈底，栈满时栈顶为S.free(99)。

（2）文件区中的所有空闲盘块被分成若干个组，如每100个盘块为一组。

（3）将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块S.free(0)~S.free(99)中，这样，由各组的第一个盘块可链接成一条链。

（4）将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。

（5）最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)~S.free(99)中，而在S.free(0)中则存放0，作为空闲盘块链的结束。

如下图所示：

图-12.3

当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减1并返回。

　　在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件等问题，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。

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

1.访问类型

对文件的保护可以从限制对文件的访问类型中出发，可加以控制的访问类型主要有以下几种：

（1）读：从文件中读；

（2）写：向文件中写；

（3）执行：将文件装入内存并执行；

（4）添加：将新内容添加到文件尾部；

（5）删除：删除文件，释放空间；

（6）列表清单：列出文件名和文件属性。

2.访问控制

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

（1）拥有着：创建文件的用户；

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

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

这样只需用三个域列出访问表中这三类用户的访问权限即可。文件拥有者在创建文件时，说明创建者用户名及所在的组名，系统在创建文件时也将文件主的名字、所属组名列在该文件的FCB中。用户访问该文件时，按照拥有者所拥有的权限访问文件，如果用户和拥有者在同一个用户组则按照同组权限访问，否则只能按其他用户权限访问。UNIX操作系统即釆用此种方法。

口令和密码是另外两种访问控制方法。这两种方法都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型。

（1）口令保护：口令指用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应口令，同时告诉允许共享该文件的其他用户，请求访问时必须提供相应口令。这种方法时间和空间的开销不多，缺点是口令直接存在系统内部，不够安全。

（2）加密保护：密码指用户对文件进行加密，文件被访问时需要使用密钥。这种方法保密性强，节省了存储空间，不过编码和译码要花费一定时间。

注意：

（1）现代操作系统常用的文件保护方法，是将访问控制列表与用户、组和其他成员访问控制方案一起组合使用。

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

1.https://www.cnblogs.com/peterYong/p/6556614.html#_label5

2.https://www.cnblogs.com/leesf456/p/5626339.html

3.https://cloud.tencent.com/developer/news/372307