[系统运维]======第六章文件管理======

6.1 文件和文件系统

??在现代 OS 中，几乎毫无例外地是通过文件系统来组织和管理在计算机中所存储的大量程序和数据的；或者说，文件系统的管理功能，是通过把它所管理的程序和数据组织成一 系列文件的方法来实现的。而文件则是指具有文件名的若干相关元素的集合。元素通常是记录，而记录又是一组有意义的数据项的集合。可见，基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。

6.1.1 文件、记录和数据项

1. 数据项

??(1) 基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名 的最小逻辑数据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。 例如，用于描述一个学生的基本数据项有学号、姓名、年龄、所在班级等。
??(2) 组合数据项。它是由若干个基本数据项组成的，简称组项。例如，经理便是个组项， 它由正经理和副经理两个基本项组成。又如，工资也是个组项，它可由基本工资、工龄工 资和奖励工资等基本项所组成。
??基本数据项除了数据名外，还应有数据类型。因为基本项仅是描述某个对象的属性， 根据属性的不同，需要用不同的数据类型来描述。例如，在描述学生的学号时，应使用整 数；描述学生的姓名则应使用字符串(含汉字)；描述性别时，可用逻辑变量或汉字。可见， 由数据项的名字和类型两者共同定义了一个数据项的“型”。而表征一个实体在数据项上的 数据则称为“值”。例如，学号/30211、姓名/王有年、性别/男等。

2. 记录

??记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含 哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把 他作为不同的对象。例如，一个学生，当把他作为班上的一名学生时，对他的描述应使用 学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。但 若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出 生年月、身高、体重、血压及病史等项。
??在诸多记录中，为了能惟一地标识一个记录，必须在一个记录的各个数据项中，确定 出一个或几个数据项，把它们的集合称为关键字(key)。或者说，关键字是惟一能标识一个 记录的数据项。通常，只需用一个数据项作为关键字。例如，前面的病历号或学号便可用 来从诸多记录中标识出惟一的一个记录。然而有时找不到这样的数据项，只好把几个数据 项定为能在诸多记录中惟一地标识出某个记录的关键字。

3. 文件

??文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件 和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被 看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例 如，可以将一个班的学生记录作为一个文件。一个文件必须要有一个文件名，它通常是由 一串 ASCII 码或(和)汉字构成的，名字的长度因系统不同而异。如在有的系统中把名字规定 为 8 个字符，而在有的系统中又规定可用 14 个字符。用户利用文件名来访问文件。
??此外，文件应具有自己的属性，属性可以包括：
????(1) 文件类型。可以从不同的角 度来规定文件的类型，如源文件、目标文件及可执行文 件等。
????(2) 文件长度。文件长度指文件的当前长度，长度的单位可以是字节、字或块，也可能 是最大允许的长度。
????(3) 文件的物理位置。该项属性通常是用于指示文件在哪一个设备上及在该设备的哪个 位置的指针。
????(4) 文件的建立时间。这是指文件最后一次的修改时间等。 图 6-1 示出了文件、记录和数据项之间的层次关系。

6.1.2 文件类型和文件系统模型

1. 文件类型
   1)按用途分类

??(1) 系统文件。这是指由系统软件构成的文件。大多数的系统文件只允许用户调用，但 不允许用户去读，更不允许修改；有的系统文件不直接对用户开放。
??(2) 用户文件。指由用户的源代码、目标文件、可执行文件或数据等所构成的文件。用 户将这些文件委托给系统保管。
??(3) 库文件。这是由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用， 但不允许修改。

?2)按文件中数据的形式分类

??(1) 源文件。这是指由源程序和数据构成的文件。通常由终端或输入设备输入的源程序 和数据所形成的文件都属于源文件。它通常是由 ASCII 码或汉字所组成的。
??(2) 目标文件。这是指把源程序经过相应语言的编译程序编译过，但尚未经过链接程序 链接的目标代码所构成的文件。它属于二进制文件。 通常，目标文件所使用的后缀名是 “.obj”。
??(3) 可执行文件。这是指把编译后所产生的目标代码再经过链接程序链接后所形成的 文件。

?3)按存取控制属性分类

??(1) 只执行文件。该类文件只允许被核准的用户调用执行，既不允许读，更不允许写。
??(2) 只读文件。该类文件只允许文件主及被核准的用户去读，但不允许写。
??(3) 读写文件。这是指允许文件主和被核准的用户去读或写的文件。
??4) 按组织形式和处理方式分类

根据文件的组织形式和系统对其的处理方式，可将文件分为三类：

??(1) 普通文件：由 ASCII 码或二进制码组成的字符文件。一般用户建立的源程序文件、 数据文件、目标代码文件及操作系统自身代码文件、库文件、实用程序文件等都是普通文 件，它们通常存储在外存储设备上。
??(2) 目录文件：由文件目录组成的，用来管理和实现文件系统功能的系统文件，通过目 录文件可以对其它文件的信息进行检索。由于目录文件也是由字符序列构成，因此对其可 进行与普通文件一样的种种文件操作。
??(3) 特殊文件：特指系统中的各类 I/O 设备。 为了便于统一管理， 系统将所有的输入/输出设备都视为文件，按文件方式提供给用户使用，如目录的检索、权限的验证等都 与普通文件相似，只是对这些文件的操作是和设备驱动程序紧密相连的，系统将这些操作 转为对具体设备的操作。根据设备数据交换单位的不同，又可将特殊文件分为块设备文件 和字符设备文件。前者用于磁盘、光盘或磁带等块设备的 I/O 操作，而后者用于终端、打 印机等字符设备的 I/O 操作。

2. 文件系统模型

??图 6-2 示出了文件系统的模型。可将该模型分为三个层次，其最底层是对象及其属性； 中间层是对对象进行操纵和管理的软件集合；最高层是文件系统提供给用户的接口。

??1) 对象及其属性
??文件管理系统管理的对象有：
????① 文件。它作为文件管理的直接对象。
????② 目录。为了 方便用户对文件的存取和检索，在文件系统中必须配置目录，每个目录项中，必须含有文 件名及该文件所在的物理地址(或指针)。对目录的组织和管理是方便用户和提高对文件存取 速度的关键。
????③ 磁盘(磁带)存储空间。文件和目录必定占用存储空间，对这部分空间的有 效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。
??2) 对对象操纵和管理的软件集合
??这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括: 对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、 对文件读和写的管理，以及对文件的共享与保护等功能。
??3) 文件系统的接口
??为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口:
??(1) 命令接口。 这是指作为用户与文件系统交互的接口。 用户可通过键盘终端键入命 令，取得文件系统的服务。
??(2) 程序接口。这是指作为用户程序与文件系统的接口。用户程序可通过系统调用来取 得文件系统的服务。

6.1.3 文件操作

1. 最基本的文件操作

??(1) 创建文件。在创建一个新文件时，系统首先要为新文件分配必要的外存空间，并在 文件系统的目录中，为之建立一个目录项。目录项中应记录新文件的文件名及其在外存的 地址等属性。
??(2) 删除文件。当已不再需要某文件时，可将它从文件系统中删除。在删除时，系统应 先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。
??(3) 读文件。在读一个文件时，须在相应系统调用中给出文件名和应读入的内存目标地 址。此时，系统同样要查找目录，找到指定的目录项，从中得到被读文件在外存中的位置。 在目录项中，还有一个指针用于对文件的读/写。
??(4) 写文件。在写一个文件时，须在相应系统调用中给出该文件名及该文件在内存中的 (源)地址。为此，也同样须先查找目录，找到指定文件的目录项，再利用目录中的写指针进 行写操作。
??(5) 截断文件。如果一个文件的内容已经陈旧而需要全部更新时，一种方法是将此文件 删除，再重新创建一个新文件。但如果文件名及其属性均无改变时，则可采取另一种所谓的截 断文件的方法，此即将原有文件的长度设置为 0，或者说是放弃原有的文件内容。
??(6) 设置文件的读/写位置。前述的文件读/写操作都只提供了对文件顺序存取的手段， 即每次都是从文件的始端读或写。设置文件读/写位置的操作，用于设置文件读/写指针的位 置，以便每次读/写文件时，不是从其始端而是从所设置的位置开始操作。也正因如此，才 能改顺序存取为随机存取。

2. 文件的“打开”和“关闭”操作

??当前 OS 所提供的大多数对文件的操作，其过程大致都是这样两步: 第一步是通过检索文 件目录来找到指定文件的属性及其在外存上的位置；第二步是对文件实施相应的操作，如读 文件或写文件等。当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录 开始。为了避免多次重复地检索目录，在大多数 OS 中都引入了“打开”(open)这一文件系统 调用，当用户第一次请求对某文件进行操作时，先利用 open 系统调用将该文件打开。
?? 所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷 贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当 用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请 求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次 检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已 不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS 将会把该文件从打开文件表中的表目上删除掉。

3. 其他文件操作

?? 为了方便用户使用文件，通常，OS 都提供了数条有关文件操作的系统调用，可将这些 调用分成若干类: 最常用的一类是有关对文件属性进行操作的，即允许用户直接设置和获得 文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权， 以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另一类是有关 目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。
?? 值得说明的是，有许多文件操作都可以利用上述基本操作加以组合来实现。例如，创 建一个文件拷贝的操作，可利用两条基本操作来实现。其第一步是利用创建文件的系统调 用来创建一个新文件；第二步是将原有文件中的内容写入新文件中。

6.2 文件的逻辑结构

通常，文件是由一系列的记录组成的。文件系统设计的关键要素，是指将这些记录构 成一个文件的方法，以及将一个文件存储到外存上的方法。事实上，对于任何一个文件， 都存在着以下两种形式的结构:

??(1) 文件的逻辑结构(File Logical Structure)。这是从用户观点出发所观察到的文件组织 形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织(File Organization)。
??(2) 文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。 无论是文件的逻辑结构，还是其物理结构，都会影响对文件的检索速度。本节只介绍 文件的逻辑结构。 对文件逻辑结构所提出的基本要求，首先是能提高检索速度，即在将大批记录组成文 件时，应有利于提高检索记录的速度和效率；其次是便于修改，即便于在文件中增加、删 除和修改一个或多个记录；第三是降低文件的存储费用，即减少文件占用的存储空间，不要求大片的连续存储空间。

6.2.1 文件逻辑结构的类型

1. 有结构文件

??(1) 定长记录。这是指文件中所有记录的长度都是相同的，所有记录中的各数据项都处 在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录 的处理方便、开销小，所以这是目前较常用的一种记录格式，被广泛用于数据处理中。
??(2) 变长记录。这是指文件中各记录的长度不相同。产生变长记录的原因，可能是由于 一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等；也可能是 数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。不 论是哪一种，在处理前，每个记录的长度是可知的。 根据用户和系统管理上的需要， 可采用多种方式来组织这些记录，形成下述的几种 文件：
????(1) 顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定 长记录，因而能用较快的速度查找文件中的记录。
????(2) 索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一 个表项，以加快对记录检索的速度。
????(3) 索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为 每一组记录中的第一个记录设置一个表项。

2. 无结构文件
   ??如果说大量的数据结构和数据库是采用有结构的文件形式的话，则大量的源程序、可 执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单 位。对流式文件的访问，则是采用读/写指针来指出下一个要访问的字符。可以把流式文件 看做是记录式文件的一个特例。在 UNIX 系统中，所有的文件都被看做是流式文件，即使 是有结构文件，也被视为流式文件，系统不对文件进行格式处理。

6.2.2 顺序文件

1. 逻辑记录的排列

??文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的 顺序进行排列。一般地，可归纳为以下两种情况：
????第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即 按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录……， 依此类推。
????第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短 从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。
??对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必须从头开 始，逐个记录地查找，直至找到指定的记录，或查完所有的记录为止。而对顺序结构文件， 则可利用某种有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法来提高检 索效率。

2. 对顺序文件的 读/写操作

??顺序文件中的记录可以是定长的，也可以是变长的。 对于定长记录的顺序文件，如 果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。 在读一个文件时， 可设置一个读指针 Rptr， 令它指向下一个记录的首地址， 每当读完一个记录时， 便 执行
??Rptr:=Rptr + L 操作，使之指向下一个记录的首地址，其中的 L 为记录长度。类似地，在写一个文件时， 也应设置一个写指针 Wptr，使之指向要写的记录的首地址。同样，在每写完一个记录时， 又须执行以下操作:
??Wptr:=Wptr + L
??对于变长记录的顺序文件，在顺序读或写时的情况相似，但应分别为它们设置读或写指针，在每次读或写完一个记录后，须将读或写指针加上 Li 。L i 是刚读或刚写完的记录的 长度。图 6-3 所示为定长和变长记录文件。

3. 顺序文件的优缺点

??顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录 时。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能 存储在磁带上，并能有效地工作。
??在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地 查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况 更为严重。例如，有一个含有 10 4 个记录的顺序文件，如果对它采用顺序查找法去查找一个 指定的记录，则平均需要查找 5×10 3 个记录；如果是可变长记录的顺序文件，则为查找一 个记录所需付出的开销将更大，这就限制了顺序文件的长度。
??顺序文件的另一个缺点是，如果想增加或删除一个记录都比较困难。为了解决这一问 题， 可以为顺序文件配置一个运行记录文件(Log File)，或称为事务文件(Transaction File)， 把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如 4 小时，将运行记 录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。

6.2.3 索引文件

??对于定长记录文件，如果要查找第 i 个记录，可直接根据下式计算来获得第 i 个记录相 对于第一个记录首址的地址：
??A i = i × L
??然而，对于可变长度记录的文件，要查找其第 i 个记录时，须首先计算出该记录的首地 址。为此，须顺序地查找每个记录，从中获得相应记录的长度 Li ，然后才能按下式计算出 第 i 个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则
??可见，对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。 然而，对于变长记录就较难实现直接存取了，因为用直接存取方法来访问变长记录文件中 的一个记录是十分低效的，其检索时间也很难令人接受。为了解决这一问题，可为变长记 录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于 记录该记录的长度 L 及指向该记录的指针(指向该记录在逻辑地址空间的首址)。由于索引表 是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地 实现直接存取。图 6-4 示出了索引文件(Index File)的组织形式。

??在对索引文件进行检索时，首先是根据用户(程序)提供的关键字，并利用折半查找法去 检索索引表，从中找到相应的表项；再利用该表项中给出的指向记录的指针值，去访问所 需的记录。而每当要向索引文件中增加一个新记录时，便须对索引表进行修改。由于索引 文件可有较快的检索速度，故它主要用于对信息处理的及时性要求较高的场合，使用索引文件的主要问题是，它除了有主文件外，还须配置一张索引表，而 且每个记录都要有一个索引项，因此提高了存储费用。

6.2.4 索引顺序文件

??索引顺序文件可能是最常见的一种逻辑文件形式。它有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。前已述及，它是顺序文件和索引文件相结合的产物。它将顺序文件中的所有记录分为若干个组(例如，50 个 记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个 索引项，其中含有该记录的键值和指向该记录的指针。索引顺序文件如图 6-5 所示。
??在对索引顺序文件进行检索时，首先也是利用用户(程序)所提供的关键字以及某种查 找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第 一个记录在主文件中的位置；然后，再利用顺序查找法去查找主文件，从中找到所要求的 记录。
??如果在一个顺序文件中所含有的记录数为 N，则为检索到具有指定关键字的记录，平均 须查找 N/2 个记录；但对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只 要查找 N 个记录数，因而其检索效率 S 比顺序文件约提高 N /2 倍。例如，有一个顺序 文件含有 10 000 个记录，平均须查找的记录数为 5000 个。但对于索引顺序文件，则平均只 须查找 100 个记录。可见，它的检索效率是顺序文件的 50 倍。
??但对于一个非常大的文件，为找到一个记录而须查找的记录数目仍然很多，例如，对 于一个含有 10 6 个记录的顺序文件，当把它作为索引顺序文件时，为找到一个记录，平均须 查找 1000 个记录。为了进一步提高检索效率，可以为顺序文件建立多级索引，即为索引文 件再建立一张索引表，从而形成两级索引表。例如，对于一个含有 10 6 个记录的顺序文件， 可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表应含有 10 4 个表项， 而每个表项中存放顺序文件中每个组第一个记录的记录键值和指向该记录的指针，然后再 为低级索引表建立一张高级索引表。这时，也同样是每 100 个索引表项为一组，故具有 102 个表项。这里的每个表项中存放的是低级索引表每组第一个表项中的关键字和指向该表项 的指针。此时，为找到一个具有指定关键字的记录，所须查找的记录数平均为 50+50+50=150， 或者可表示为(3/2) 3 N 。其中，N 是顺序文件中记录的个数。注意，在未建立索引文件时所 需查找的记录数平均为 50 万个；对于建立了一级索引的顺序索引文件，平均需查找 1000 次；建立两级索引的顺序索引文件，平均只需查找 150 次。

6.5.2 直接文件和哈希文件

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

2. 哈希文件

??这是目前应用最为广泛的一种直接文件。它利用 Hash 函数(或称散列函数)，可将记录 键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由 Hash 函数所 求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相 应记录所在的物理块，如图 6-6 所示。例如，若令 K 为记录键值，用 A 作为通过 Hash 函数 H 的转换所形成的该记录在目录表中对应表目的位置，则有关系 A=H(K)。通常，把 Hash 函数作为标准函数存于系统中，供存取文件时调用。

6.3 外存分配方式

6.3.1 连续分配

1. 连续分配方式

??连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的 地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为 b，则第二个盘块的地址为 b+1，第三个盘块的地址为 b+2……。通常，它们都位于一条磁道上，在进行读/写时，不必 移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连 续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的 各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。 这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为 使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一 个记录所在的盘块号和文件长度(以盘块数进行计量)。图 6-7 示出了连续分配的情况。图中 假定了记录与盘块的大小相同。Count 文件的第一个盘块号是 0，文件长度为 2，因此是在 盘块号为 0 和 1 的两盘块中存放文件 1 的数据。
如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收， 将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎 片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼 接成一大片连续的存储空间。例如，可以运行一个再装配例程(repack routine)，由它将磁盘 A 上的大量文件拷贝到一张软盘 B 或几张软盘(C，D，…)上，并释放原来的 A 盘，使之成 为一个空闲盘。然后再将软盘 B(C，D，…)上的文件拷回 A 盘上。这种方法能将含有多个 文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲 空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。

2. 连续分配的主要优缺点
   连续分配的主要优点如下：

??(1) 顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺 序文件所在的第一个盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直 接存取。例如，要访问一个从 b 块开始存放的文件中的第 i 个盘块的内容，就可直接访问 b+i 号盘块。
??(2) 顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条 或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种 存储空间分配方式中最高的一种。

连续分配的主要缺点如下：

??(1) 要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产 生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除 碎片，则又需花费大量的机器时间。
??(2) 必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道 文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。 在有些情况下，知道文件的大小是件非常容易的事，如可拷贝一个已存文件。但有时却很 难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的拷贝，须再要求用户重新估算，然后再次执行。这样，显然既费时又麻烦。 这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得 多，显然，这会严重地浪费外存空间。对于那些动态增长的文件，由于开始时文件很小， 在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此情况下，即使事先知道文 件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存 储空间长期地空闲着。

6.3.2 链接分配

1. 隐式链接

??在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第 一个盘块和最后一个盘块的指针。图 6-8 中示出了一个占用 5 个盘块的链接式文件。在相 应的目录项中，指示了其第一个盘块号是 9，最后一个盘块号是 25。而在每个盘块中都含 有一个指向下一个盘块的指针，如在第一个盘块 9 中设置了第二个盘块的盘块号是 16；在 16 号盘块中又设置了第三个盘块的盘块号 1。如果指针占用 4 个字节，对于盘块大小为 512 字节的磁盘，则每个盘块中只有 508 个字节可供用户使用。
??隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效 的。如果要访问文件所在的第 i 个盘块，则必须先读出文件的第一个盘块……，就这样顺序 地查找直至第 i 块。当 i=100 时，须启动 100 次磁盘去实现读盘块的操作，平均每次都要花 费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘 块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的 断开。
??为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)。 比如，一个簇可包含 4 个盘块，在进行盘块分配时，是以簇为单位进行的。在链接文件中 的每个元素也是以簇为单位的。这样将会成倍地减小查找指定块的时间，而且也可减小指 针所占用的存储空间，但却增大了内部碎片，而且这种改进也是非常有限的。

2. 显示链接

??这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在 整个磁盘仅设置一张，如图 6-9 所示。表的序号是物理盘块号，从 0 开始，直至 N-1；N 为 盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件 的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入 相应文件的 FCB 的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不 仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件的所有盘块 号都放在该表中，故把该表称为文件分配表 FAT(File Allocation Table)。

6.3.3 FAT 和 NTFS 技术

1．FAT12

??1) 以盘块为基本分配单位
??早期 MS-DOS 操作系统所使用的是 FAT12 文件系统，在每个分区中都配有两张文件分 配表 FAT1 和 FAT2，在 FAT 的每个表项中存放下一个盘块号，它实际上是用于盘块之间的 链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放 在自己的 FCB 中。图 6-10 示出了 MS-DOS 的文件物理结构，这里示出了两个文件，文件 A 占用三个盘块，其盘块号依次为 4、6、11；文件 B 则依次占用 9、10 及 5 号三个盘块。 每个文件的第一个盘块号放在自己的 FCB 中。整个系统有一张文件分配表 FAT。在 FAT 的 每个表项中存放下一个盘块号。对于 1.2 MB 的软盘，每个盘块的大小为 512 B，在每个 FAT 中共含有 2.4 K 个表项，由于每个 FAT 表项占 12 位，故 FAT 表占用 3.6 KB 的存储空间。
??现在我们来计算以盘块为分配单位时，所允许的最大磁盘容量。由于每个 FAT 表项为 12 位，因此，在 FAT 表中最多允许有 4096 个表项，如果采用以盘块作为基本分配单位， 每个盘块(也称扇区)的大小一般是 512 字节， 那么， 每个磁盘分区的容量为 2 MB (4096×512 B)。同时，一个物理磁盘支持 4 个逻辑磁盘分区，所以相应的磁盘最大容量仅 为 8 MB。这对最早时期的硬盘还可应付，但很快磁盘的容量就超过了 8 MB，FAT12 是否 还可继续用呢，回答虽是肯定的，但需要引入一个新的分配单位——簇。

??2) 簇的基本概念
??为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster) 为基本单位。簇是一组连续的扇区，在 FAT 中它是作为一个虚拟扇区，簇的大小一般是 2n (n 为整数)个盘块，在 MS-DOS 的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个 扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。一个簇应包含扇区的数量与磁盘容量的 大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为 8 MB；当一个簇包含 两个扇区时，磁盘的最大容量可以达到 16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到 64 MB。 由上所述可以看出，以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘 容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位虽可减少 FAT 表中的项 数(在相同的磁盘容量下，FAT 表的项数是与簇的大小成反比的)。这一方面会使 FAT 表占用 更少的存储空间，并减少访问 FAT 表的存取开销，提高文件系统的效率；但这也会造成更 大的簇内零头(它与存储器管理中的页内零头相似)。

??3) FAT12 存在的问题
??尽管 FAT12 曾是一个不错的文件系统，但毕竟已老化，已不能满足操作系统发展的需 要，其表现出来的主要问题是，对所允许的磁盘容量存在着严重的限制，通常只能是数十 兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘 容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只能支持 8+3 格式的文件名。

2. FAT16

??对 FAT12 所存在的问题进行简单的分析即可看出，其根本原因在于，FAT12 表最多只 允许 4096 个表项，亦即最多只能将一个磁盘分区分为 4096 个簇。这样，随着磁盘容量的 增加，必定会引起簇的大小和簇内碎片也随之增加。由此可以得出解决方法，那就是增加 FAT 表的表项数，亦即应增加 FAT 表的宽度，如果我们将 FAT 表的宽度增至 16 位，最大表 项数将增至 65536 个，此时便能将一个磁盘分区分为 65 536(216 )个簇。我们把具有 16 位表 宽的 FAT 表称为 FAT16。在 FAT16 的每个簇中可以有的盘块数为 4、8、16、32 直到 64， 由此得出 FAT16 可以管理的最大分区空间为 2 16 × 64 × 512 = 2048 MB。
??由上述分析不难看出，FAT16 对 FAT12 的局限性有所改善，但改善很有限。当磁盘容 量迅速增加时，如果再继续使用 FAT16，由此所形成的簇内碎片所造成的浪费也越大。例 如，当要求磁盘分区的大小为 8 GB 时，则每个簇的大小达到 128 KB，这意味着内部零头 最大可达到 128 KB。一般而言，对于 1～4 GB 的硬盘来说，大约会浪费 10％～20％的空间。 为了解决这一问题，微软推出了 FAT32。
??另外，由于 FAT12 和 FAT16 都不支持长文件名，文件名受到了 8 个字符文件名和 3 个 字符文件扩展名的长度限制，为了满足用户通过文件名更好地描述文件内容的需求， 在 Windows 95 以后的系统中，对 FAT16 进行了扩展，通过一个长文件名占用多个目录项的方 法，使得文件名的长度可以长达 255 个字符，这种扩展的 FAT16 也称为 VFAT。

3. FAT32

??如同存储器管理中的分页管理，所选择的页面越大，可能造成的页内零头也会越大。 为减少页内零头就应该选择适当大小的页面。在这里，为了减小磁盘的簇内零头，也就应 当选择适当大小的簇。问题是 FAT16 表的长度只有 65 535 项，随着磁盘容量的增加，簇的 大小也必然会随之增加，为了减少簇内零头，也就应当增加 FAT 表的长度。为此，需要再 增加 FAT 表的宽度，这样也就由 FAT16 演变为 FAT32。
??FAT32 是 FAT系列文件系统的最后一个产品。每一簇在 FAT表中的表项占据4 字节(232 )， FAT 表可以表示 4 294 967 296 项，即 FAT32 允许管理比 FAT16 更多的簇。这样就允许在 FAT32 中采用较小的簇，FAT32 的每个簇都固定为 4 KB，即每簇用 8 个盘块代替 FAT16 的 64 个盘块，每个盘块仍为 512 字节，FAT32 分区格式可以管理的单个最大磁盘空间大到4 KB×2 32 = 2 TB。三种 FAT 类型的最大分区以及所对应的块的大小如图 6-11 所示。
??FAT32 比 FAT16 支持更小的簇和更大的磁盘容量，这就大大减少了磁盘空间的浪费， 使得 FAT32 分区的空间分配更有效率，例如，两个磁盘容量都为 2 GB，一个磁盘采用了 FAT16 文件系统，另一个磁盘采用了 FAT32 文件系统，采用 FAT16 磁盘的簇大小为 32 KB， 而 FAT32 磁盘簇只有 4 KB 的大小，这样，FAT32 磁盘碎片减少，比 FAT16 的存储器利用 率要高很多，通常情况下可以提高 15%。FAT32 主要应用于 Windows 98 及后续 Windows 系统，它可以增强磁盘性能，并增加可用磁盘空间，同时也支持长文件名；它不存在最小 存储空间问题，能够有效地节省硬盘空间。
??FAT32 仍然有着明显的不足之处：首先，由于文件分配表的扩大，运行速度比 FAT16 格式要慢；其次，FAT32 有最小管理空间的限制，FAT32 卷必须至少有 65 537 个簇，所以 FAT32 不支持容量小于 512 MB 的分区，因此对于小分区，则仍然需要使用 FAT16 或 FAT12； 再之，FAT32 的单个文件的长度也不能大于 4 GB；最后，FAT32 最大的限制在于兼容性方 面，FAT32 不能保持向下兼容。

4. NTFS

??1) NTFS 新特征
??NTFS(New Technology File System)是一个专门为 Windows NT 开发的、全新的文件系 统，并适用于 Windows 2000/XP/2003。NTFS 具有许多新的特征：首先，它使用了 64 位磁 盘地址，理论上可以支持 2 的 64 次方字节的磁盘分区；其次，在 NTFS 中可以很好地支持 长文件名，单个文件名限制在 255 个字符以内，全路径名为 32 767 个字符；第三，具有系 统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行，这一点我们将在 6.6 节 中介绍；第四，提供了数据的一致性，这是一个非常有用的功能，我们将在本章的最后一 节介绍；此外，NTFS 还提供了文件加密、文件压缩等功能。
??2) 磁盘组织
??同 FAT 文件系统一样，NTFS 也是以簇作为磁盘空间分配和回收的基本单位。一个文件 占用若干个簇，一个簇只属于一个文件。通过簇来间接管理磁盘，可以不需要知道盘块(扇 区)的大小，使 NTFS 具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是 512 字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。
在 NTFS 文件系统中，把卷上簇的大小称为“卷因子”，卷因子是在磁盘格式化时确定 的，其大小同 FAT 一样，也是物理磁盘扇区的整数倍，即一个簇包含 2n(n 为整数)个盘块， 簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为 512 B、1 KB、 2 KB……，最大可达 64 KB。对于小磁盘(≤512 MB)，默认簇大小为 512 字节；对于 1 GB 磁盘，默认簇大小为 1 KB；对于 2 GB 磁盘，则默认簇大小为 4 KB。事实上，为了在传输 效率和簇内碎片之间进行折中，NTFS 在大多数情况下都是使用 4 KB。
??对于簇的定位， NTFS 是采用逻辑簇号 LCN(Logical Cluster Number)和虚拟簇号 VCN(Virtual Cluster Number)进行的。LCN 是以卷为单位，将整个卷中所有的簇按顺序进行 简单的编号，NTFS 在进行地址映射时，可以通过卷因子与 LCN 的乘积，便可算出卷上的 物理字节偏移量，从而得到文件数据所在的物理磁盘地址。为了方便文件中数据的引用， NTFS 还可以使用 VCN，以文件为单位，将属于某个文件的簇按顺序进行编号。只要知道 了文件开始的簇地址，便可将 VCN 映射到 LCN。
??3) 文件的组织
??在 NTFS 中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配 空间信息，都以文件记录的方式记录在一张主控文件表 MFT(Master File Table)中。该表是 NTFS 卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在 MFT 表中占有一行， 其中还包括 MFT 自己的这一行。每行大小固定为 1 KB，每行称为该行所对应文件的元数 据(metadata)，也称为文件控制字。
??在 MFT 表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织 在所对应文件的一组属性中。由于文件大小相差悬殊，其属性所需空间大小也相差很大， 因此，在 MFT 表中，对于元数据的 1 KB 空间，可能记录不下文件的全部信息。所以当文 件较小时，其属性值所占空间也较小，可以将文件的所有属性直接记录在元数据中。而当 文件较大时，元数据仅记录该文件的一部分属性，其余属性，如文件的内容等，可以记录 到卷中的其它可用簇中，并将这些簇按其所记录文件的属性进行分类，分别链接成多个队 列，将指向这些队列的指针保存在元数据中。
??例如对于一个文件的真正数据，即文件 DATA 属性，如果很小，就直接存储在 MFT 表 中对应的元数据中，这样对文件数据的访问，仅需要对 MFT 表进行即可，减少了磁盘访问 次数，较大地提高了对小文件存取的效率。如果文件较大，则文件的真正数据往往保存在 其它簇中。此时通过元数据中指向文件 DATA 属性的队列指针，可以方便地查找到这些簇， 完成对文件数据的访问。
??实际上，文件在存储过程中，数据往往连续存放在若干个相邻的簇中，仅用一个指针 记录这几个相邻的簇即可，而不是每个簇需要一个指针，从而可以节省指针所耗费的空间。 一般地，采用上述的方式，只需十几个字节就可以含有 FAT32 所需几百个 KB 才拥有的信 息量。
??NTFS 的不足之处在于，它只能被 Windows NT 所识别。NTFS 文件系统可以存取 FAT 等文件系统的文件，但 NTFS 文件却不能被 FAT 等文件系统所存取，缺乏兼容性。Windows 的 95/98/98SE 和 Me 版本都不能识别 NTFS 文件系统。

6.3.4 索引分配

1. 单级索引分配
   链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题：

??(1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在 FAT 中顺 序地查找许多盘块号。
??(2) FAT 需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在 FAT 中的，因而只有将整个 FAT 调入内存，才能保证在 FAT 中找到一个文件的所有盘块号。 当磁盘容量较大时，FAT 可能要占用数兆字节以上的内存空间，这是令人难以接受的。 事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没 有必要将整个 FAT 调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引 分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再 把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块 号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图 6-12 示出了磁盘空间的索引分配图。
??索引分配方式支持直接访问。当要读文件的第 i 个盘块时，可以方便地直接从索引块中 找到第 i 个盘块的盘块号；此外，索引分配方式也不会产生外部碎片。当文件较大时，索引 分配方式无疑要优于链接分配方式。

索引分配方式的主要问题是：

??可能要花费较多的外存空间。每当建立一个文件时，便 须为之分配一个索引块，将分配给该文件的所有盘块号记录于其中。但在一般情况下，总 是中、小型文件居多，甚至有不少文件只需 1～2 个盘块，这时如果采用链接分配方式，只 需设置 1～2 个指针。如果采用索引分配方式，则同样仍须为之分配一索引块。通常是采用 一个专门的盘块作为索引块，其中可存放成百个、甚至上千个盘块号。可见，对于小文件 采用索引分配方式时，其索引块的利用率将是极低的。

2. 多级索引分配

??当 OS 为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS 便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。 依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时， 这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再 分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填 入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四 级索引分配方式。
??图6-13示出了两级索引分配方式下各索引块之间的链接情况。如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时，最多可包含的存放文件的盘块的盘块号总数N= 256x256= 64K个盘块号。由此可得出结论：采用两级索引时，所允许的文件最大长度为64 MB。倘若盘块的大小为4 KB,在采用单级索引时所允许的最大文件长度为4 MB;而在采用两级索引时所允许的最大文件
长度可达4 GB。

3. 混合索引分配方式

??所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一-种分配方式。 例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIX SystemV的索引结点中,共设置了13 个地址项,即iaddr(0)~ iaddr(12),如图6- 14所示。在BSD UNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。
??1) 直接地址
??为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即用 iaddr(0)～ iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据所在盘块的盘块 号。假如每个盘块的大小为 4 KB，当文件不大于 40 KB 时，便可直接从索引结点中读出该 文件的全部盘块号。
??2) 一次间接地址
??对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址 项 iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次间 址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放 1 K 个盘块号，因而允许文件长达 4 MB。
??3) 多次间接地址
??当文件长度大于 4 MB + 40 KB 时(一次间址与 10 个直接地址项)，系统还须采用二次间 址分配方式。这时，用地址项 iaddr(11)提供二次间接地址。该方式的实质是两级索引分配 方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时， 文件最大长度可达 4 GB。同理，地址项 iaddr(12)作为三次间接地址，其所允许的文件最大 长度可达 4 TB。

6.4 目录管理

??通常，在现代计算机系统中，都要存储大量的文件。为了能对这些文件实施有效的管 理，必须对它们加以妥善组织，这主要是通过文件目录实现的。文件目录也是一种数据结 构，用于标识系统中的文件及其物理地址，供检索时使用。对目录管理的要求如下：

??(1) 实现“按名存取”，即用户只须向系统提供所需访问文件的名字，便能快速准确地 找到指定文件在外存上的存储位置。这是目录管理中最基本的功能，也是文件系统向用户 提供的最基本的服务。
??(2) 提高对目录的检索速度。通过合理地组织目录结构的方法，可加快对目录的检索速 度，从而提高对文件的存取速度。这是在设计一个大、中型文件系统时所追求的主要目标。
??(3) 文件共享。在多用户系统中，应允许多个用户共享一个文件。这样就须在外存中只 保留一份该文件的副本，供不同用户使用，以节省大量的存储空间，并方便用户和提高文 件利用率。
??(4) 允许文件重名。系统应允许不同用户对不同文件采用相同的名字，以便于用户按照 自己的习惯给文件命名和使用文件。

6.4.1 文件控制块和索引结点

1. 文件控制块
   ??为了能对系统中的大量文件施以有效的管理，在文件控制块中，通常应含有三类信息， 即基本信息、存取控制信息及使用信息。

??1) 基本信息类
??基本信息类包括:
????① 文件名，指用于标识一个文件的符号名。在每个系统中，每一个 文件都必须有惟一的名字，用户利用该名字进行存取。
????② 文件物理位置，指文件在外存上 的存储位置，它包括存放文件的设备名、文件在外存上的起始盘块号、指示文件所占用的 盘块数或字节数的文件长度。
????③ 文件逻辑结构，指示文件是流式文件还是记录式文件、记 录数；文件是定长记录还是变长记录等。
????④ 文件的物理结构，指示文件是顺序文件，还是 链接式文件或索引文件。
??2) 存取控制信息类
??存取控制信息类包括：文件主的存取权限、核准用户的存取权限以及一般用户的存取 权限。
??3) 使用信息类
??使用信息类包括: 文件的建立日期和时间、文件上一次修改的日期和时间及当前使用信 息(这项信息包括当前已打开该文件的进程数、是否被其它进程锁住、文件在内存中是否已 被修改但尚未拷贝到盘上)。应该说明，对于不同 OS 的文件系统，由于功能不同，可能只 含有上述信息中的某些部分。
??图 6-15 示出了 MS-DOS 中的文件控制块，其中含有文件名、文件所在的第一个盘块号、 文件属性、文件建立日期和时间及文件长度等。FCB 的长度为 32 个字节，对于 360 KB 的 软盘，总共可包含 112 个 FCB，共占 4 KB 的存储空间。

2. 索引结点

??1) 索引结点的引入 文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块。 在查找目录的过程中，先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所 给定的文件名与目录项中的文件名逐一比较。若未找到指定文件，便再将下一个盘块中的 目录项调入内存。设目录文件所占用的盘块数为 N，按此方法查找，则查找一个目录项平均 需要调入盘块(N+1)/2 次。假如一个 FCB 为 64 B，盘块大小为 1 KB，则每个盘块中只能存 放 16 个 FCB；若一个文件目录中共有 640 个 FCB，需占用 40 个盘块，故平均查找一个文 件需启动磁盘 20 次。 稍加分析可以发现，在检索目录文件的过程中，只用到了文件名，仅当找到一个目录 项(即其中的文件名与指定要查找的文件名相匹配)时，才需从该目录项中读出该文件的物理 地址。而其它一些对该文件进行描述的信息，在检索目录时一概不用。显然，这些信息在 检索目录时不需调入内存。为此，在有的系统中，如 UNIX 系统，便采用了把文件名与文 件描述信息分开的办法，亦即，使文件描述信息单独形成一个称为索引结点的数据结构， 简称为 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针 所构成。在 UNIX 系统中一个目录仅占 16 个字节，其中 14 个字节是文件名，2 个字节为 i 结点指针。在 1 KB 的盘块中可做 64 个目录项，这样，为找到一个文件，可使平均启动磁 盘次数减少到原来的 1/4，大大节省了系统开销。图 6-16 示出了 UNIX 的文件目录项。
??2) 磁盘索引结点
??这是存放在磁盘上的索引结点。每个文件有惟一的一个磁盘索引结点，它主要包括以 下内容：
????(1) 文件主标识符，即拥有该文件的个人或小组的标识符。
????(2) 文件类型，包括正规文件、目录文件或特别文件。
????(3) 文件存取权限，指各类用户对该文件的存取权限。
????(4) 文件物理地址，每一个索引结点中含有 13 个地址项，即 iaddr(0)～iaddr(12)，它们 以直接或间接方式给出数据文件所在盘块的编号。
????(5) 文件长度，指以字节为单位的文件长度。
????(6) 文件连接计数，表明在本文件系统中所有指向该(文件的)文件名的指针计数。
????(7) 文件存取时间，指本文件最近被进程存取的时间、最近被修改的时间及索引结点最 近被修改的时间。
??3) 内存索引结点
??这是存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点拷贝到内存的索 引结点中，便于以后使用。在内存索引结点中又增加了以下内容：
????(1) 索引结点编号，用于标识内存索引结点。
????(2) 状态，指示 i 结点是否上锁或被修改。
????(3) 访问计数，每当有一进程要访问此 i 结点时，将该访问计数加 1，访问完再减 1。
????(4) 文件所属文件系统的逻辑设备号。
????(5) 链接指针。设置有分别指向空闲链表和散列队列的指针。

6.4.2 目录结构

1. 单级目录结构

??这是最简单的目录结构。在整个文件系统中只建立一张目录表，每个文件占一个目录 项，目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件 属性。此外，为表明每个目录项是否空闲，又设置了一个状态位。单级目录如图 6-17 所示。
??每当要建立一个新文件时，必须先检索所有的目录项，以保证新文件名在目录中是惟 一的。然后再从目录表中找出一个空白目录项，填入新文件的文件名及其它说明信息，并 置状态位为 1。删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空 间，然后再清除该目录项。
??单级目录的优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一 些缺点：
????(1) 查找速度慢。对于稍具规模的文件系统，会拥有数目可观的目录项，致使为找到一 个指定的目录项要花费较多的时间。对于一个具有 N 个目录项的单级目录，为检索出一个 目录项，平均需查找 N/2 个目录项。
????(2) 不允许重名。在一个目录表中的所有文件，都不能与另一个文件有相同的名字。然 而，重名问题在多道程序环境下却又是难以避免的；即使在单用户环境下，当文件数超过数百个时，也难于记忆。
????(3) 不便于实现文件共享。通常，每个用户都有自己的名字空间或命名习惯。因此，应 当允许不同用户使用不同的文件名来访问同一个文件。然而，单级目录却要求所有用户都 用同一个名字来访问同一文件。简言之，单级目录只能满足对目录管理的四点要求中的第 一点， 因而，它只能适用于单用户环境。

2. 两级目录

??为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目录 UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块 组成。此外，在系统中再建立一个主文件目录 MFD(Master File Directory)；在主文件目录中， 每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指 针。如图 6-18 所示，图中的主目录中示出了三个用户名，即 Wang、Zhang 和 Gao。
??在两级目录结构中，如果用户希望有自己的用户文件目录 UFD，可以请求系统为自己 建立一个用户文件目录；如果自己不再需要 UFD，也可以请求系统管理员将它撤消。在有 了 UFD 后，用户可以根据自己的需要创建新文件。每当此时，OS 只需检查该用户的 UFD， 判定在该 UFD 中是否已有同名的另一个文件。若有，用户必须为新文件重新命名；若无， 便在 UFD 中建立一个新目录项，将新文件名及其有关属性填入目录项中，并置其状态位为 “1”。当用户要删除一个文件时，OS 也只需查找该用户的 UFD，从中找出指定文件的目录 项， 在回收该文件所占用的存储空间后，将该目录项删除。
??两级目录结构基本上克服了单级目录的缺点，并具有以下优点：
????(1) 提高了检索目录的速度。如果在主目录中有 n 个子目录，每个用户目录最多为 m 个 目录项，则为查找一指定的目录项，最多只需检索 n + m 个目录项。但如果是采用单级目录 结构，则最多需检索 n × m 个目录项。假定 n = m，可以看出，采用两级目录可使检索效率 提高 n/2 倍。
????(2) 在不同的用户目录中，可以使用相同的文件名。只要在用户自己的 UFD 中，每一 个文件名都是惟一的。例如，用户 Wang 可以用 Test 来命名自己的一个测试文件；而用户 Zhang 则可用 Test 来命名自己的一个并不同于 Wang 的 Test 的测试文件。
????(3) 不同用户还可使用不同的文件名来访问系统中的同一个共享文件。采用两级目录结 构也存在一些问题。该结构虽然能有效地将多个用户隔开，在各用户之间完全无关时，这种 隔离是一个优点；但当多个用户之间要相互合作去完成一个大任务，且一用户又需去访问其 他用户的文件时，这种隔离便成为一个缺点，因为这种隔离会使诸用户之间不便于共享文件。

3. 多级目录结构

??1) 目录结构
??对于大型文件系统，通常采用三级或三级以上的目录结构，以提高对目录的检索速度 和文件系统的性能。多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把 数据文件称为树叶，其它的目录均作为树的结点。图 6-19 示出了多级目录结构。图中，用 方框代表目录文件，圆圈代表数据文件。在该树型目录结构中，主(根)目录中有三个用户的 总目录项 A、B 和 C。在 B 项所指出的 B 用户的总目录 B 中，又包括三个分目录 F、E 和 D， 其中每个分目录中又包含多个文件。如 B 目录中的 F 分目录中，包含 J 和 N 两个文件。为 了提高文件系统的灵活性，应允许在一个目录文件中的目录项既是作为目录文件的 FCB， 又是数据文件的 FCB，这一信息可用目录项中的一位来指示。例如，在图 6-19 中，用户 A 的总目录中，目录项 A 是目录文件的 FCB，而目录项 B 和 D 则是数据文件的 FCB。??2) 路径名
??在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。在该路径上 从树的根(即主目录)开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构 成该数据文件的路径名(path name)。系统中的每一个文件都有惟一的路径名。例如，在图 6-19 中用户 B 为访问文件 J，应使用其路径名/B/F/J 来访问。
??3) 当前目录(Current Directory)
??当一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶(数据 文件)为止的、包括各中间节点(目录)名的全路径名。这是相当麻烦的事，同时由于一个进 程运行时所访问的文件大多仅局限于某个范围，因而非常不便。基于这一点，可为每个进 程设置一个“当前目录”，又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。此时各文件所使用的路径名，只需从当前目录开始，逐级经过中间的目录文件， 最后到达要访问的数据文件。把这一路径上的全部目录文件名与数据文件名用“/”连接形 成路径名。如用户 B 的当前目录是 F，则此时文件 J 的相对路径名仅是 J 本身。这样，把从 当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relative path name)；而 把从树根开始的路径名称为绝对路径名(absolute path name)。
??就多级目录较两级目录而言，其查询速度更快，同时层次结构更加清晰，能够更加有 效地进行文件的管理和保护。在多级目录中，不同性质、不同用户的文件可以构成不同的 目录子树，不同层次、不同用户的文件分别呈现在系统目录树中的不同层次或不同子树中， 可以容易地赋予不同的存取权限。
??但是在多级目录中查找一个文件，需要按路径名逐级访问中间节点，这就增加了磁盘 访问次数，无疑将影响查询速度。
??目前，大多数操作系统如 UNIX、Linux 和 Windows 系列都采用了多级目录结构。

4. 增加和删除目录

??在树型目录结构中，用户可为自己建立 UFD，并可再创建子目录。在用户要创建一个 新文件时，只需查看在自己的 UFD 及其子目录中有无与新建文件相同的文件名。若无，便 可在 UFD 或其某个子目录中增加一个新目录项。
??在树型目录中，对于一个已不再需要的目录，应如何删除其目录项，须视情况而定。 这时，如果所要删除的目录是空的，即在该目录中已不再有任何文件，就可简单地将该目 录项删除，使它在其上一级目录中对应的目录项为空；如果要删除的目录不空，即其中尚 有几个文件或子目录，则可采用下述两种方法处理：
????(1) 不删除非空目录。当目录(文件)不空时，不能将其删除，而为了删除一个非空目录， 必须先删除目录中的所有文件，使之先成为空目录，然后再予以删除。如果目录中还包含 有子目录，还必须采取递归调用方式来将其删除，在 MS-DOS 中就是采用这种删除方式。
????(2) 可删除非空目录。当要删除一个目录时，如果在该目录中还包含有文件，则目录中 的所有文件和子目录也同时被删除。 上述两种方法实现起来都比较容易，第二种方法则更为方便，但比较危险。因为整个 目录结构虽然用一条命令即能删除，但如果是一条错误命令，其后果则可能很严重。

6.4.3 目录查询技术

1. 线性检索法

??线性检索法又称为顺序检索法。在单级目录中，利用用户提供的文件名，用顺序查找 法直接从文件目录中找到指名文件的目录项。在树型目录中，用户提供的文件名是由多个 文件分量名组成的路径名， 此时须对多级目录进行查找。 假定用户给定的文件路径名是 /usr/ast/mbox，则查找/usr/ast/mbox 文件的过程如图 6-20 所示。
??具体查找过程说明如下： 首先，系统应先读入第一个文件分量名 usr，用它与根目录文件(或当前目录文件)中各 目录项中的文件名顺序地进行比较，从中找出匹配者，并得到匹配项的索引结点号 6，再从 6 号索引结点中得知 usr 目录文件放在 132 号盘块中，将该盘块内容读入内存。
??接着，系统再将路径名中的第二个文件分量名 ast 读入，用它与放在 132 号盘块中的第二 级目录文件中各目录项的文件名顺序进行比较，又找到匹配项，从中得到 ast 的目录文件放在 26 号索引结点中，再从 26 号索引结点中得知/usr/ast 是存放在 496 号盘块中，再读入 496 号盘块。
??然后，系统又将该文件的第三个分量名 mbox 读入，用它与第三级目录文件/usr/ast 中各 目录项中的文件名进行比较，最后得到/usr/ast/mbox 的索引结点号为 60，即在 60 号索引结 点中存放了指定文件的物理地址。目录查询操作到此结束。如果在顺序查找过程中发现有 一个文件分量名未能找到，则应停止查找，并返回“文件未找到”信息。

2. Hash 方法

??在 6.2.5 节中曾介绍了 Hash 文件。如果我们建立了一张 Hash 索引文件目录，便可利用 Hash 方法进行查询，即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利 用该索引值到目录中去查找，这将显著地提高检索速度。
??顺便指出，在现代操作系统中，通常都提供了模式匹配功能，即在文件名中使用了通 配符“*”、“？”等。对于使用了通配符的文件名，系统此时便无法利用 Hash 方法检索目 录，因此，这时系统还是需要利用线性查找法查找目录。
??在进行文件名的转换时，有可能把 n 个不同的文件名转换为相同的 Hash 值，即出现了 所谓的“冲突”。一种处理此“冲突”的有效规则是:
????(1) 在利用 Hash 法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统 中并无指定文件。
????(2) 如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件 所对应的目录项，故而可从中找到该文件所在的物理地址。
????(3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲 突”，此时须将其 Hash 值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值，再返回到第一步重新开始查找。

6.5 文件存储空间的管理

6.5.1 空闲表法和空闲链表法

1. 空闲表法

??1) 空闲表
??空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一 个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。 再将所有空闲区按其起始盘块号递增的次序排列，如图 6-21 所示。
??2) 存储空间的分配与回收
??空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算 法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项， 直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲 表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考 虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。
??应该说明，在内存分配上，虽然很少采用连续分配方式，然而在外存的管理中，由于 这种分配方式具有较高的分配速度，可减少访问磁盘的 I/O 频率，故它在诸多分配方式中仍 占有一席之地。例如，在前面所介绍的对换方式中，对对换空间一般都采用连续分配方式。 对于文件系统，当文件较小(1～4 个盘块)时，仍采用连续分配方式，为文件分配相邻接的几 个盘块；当文件较大时，便采用离散分配方式。

2. 空闲链表法

??空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。

??(1) 空闲盘块链。这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因 创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给 用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末 尾。这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘 块时，可能要重复操作多次。
??(2) 空闲盘区链。这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条 链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块 数)的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收 盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提 高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张 链表。

6.5.2 位示图法

1. 位示图

??位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表 示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志， 把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分 配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的 位构成一个集合，称为位示图。通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘 的总块数，如图 6-22 所示。
??位示图也可描述为一个二维数组 map： Var map: array of bit；

2. 盘块的分配 根据位示图进行盘块分配时，可分三步进行：

??(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
??(2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0” 的二进制位位于位示图的第 i 行、第 j 列，则其相应的盘块号应按下式计算：
????????????b = n(i - 1) + j
式中，n 代表每行的位数。
??(3) 修改位示图，令 map[i,j]=1。 3．盘块的回收 盘块的回收分两步：
????(1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
??????????i = (b - 1)DIV n + 1
??????????j = (b - 1)MOD n + 1
????(2) 修改位示图。令 map[i,j] =0。
??这种方法的主要优点是，从位示图中很容易找到一个或一组相邻接的空闲盘块。例如， 我们需要找到 6 个相邻接的空闲盘块，这只需在位示图中找出 6 个其值连续为“0”的位即 可。此外，由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行 盘区分配时，无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。因此， 位示图常用于微型机和小型机中，如 CP/M、Apple-DOS 等 OS 中。

6.5.3 成组链接法

??空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。 在 UNIX 系统中采用的是成组链接法，这是将上述两种方法相结合而形成的一种空闲盘块 管理方法，它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。

1．空闲盘块的组织

??(1) 空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号(最多含 100 个号)，以 及栈中尚有的空闲盘块号数 N。顺便指出，N 还兼作栈顶指针用。例如，当 N=100 时，它 指向 S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一 把锁。图 6-23 左部示出了空闲盘块号栈的结构。其中，S.free(0)是栈底，栈满时的栈顶为 S.free(99)。
??(2) 文件区中的所有空闲盘块被分成若干个组，比如，将每 100 个盘块作为一组。假定 盘上共有 10 000 个盘块，每块大小为 1 KB，其中第 201～7999 号盘块用于存放文件，即作 为文件区，这样，该区的最末一组盘块号应为 7901～7999；次末组为 7801～7900……；第 二组的盘块号为 301～400；第一组为 201～300，如图 6-23 右部所示。
??(3) 将每一组含有的盘块总数 N 和该组所有的盘块号记入其前一组的第一个盘块的 S.free(0)～S.free(99)中。这样，由各组的第一个盘块可链成一条链。
??(4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空 闲盘块号。
??(5) 最末一组只有 99 个盘块，其盘块号分别记入其前一组的 S.free(1) ～S.free(99)中， 而在 S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为 99， 不应是 100，因为这是指可供使用的空闲盘块，其编号应为(1～99)，0 号中放空闲盘块链的 结尾标志。)

2. 空闲盘块的分配与回收

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

6.6 文件共享与文件保护

6.6.1基于索引结点的共享方式

??在树型结构的目录中，当有两个(或多个)用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个(或多个)用户的目录中，才能方便地找到该文件，如图 6-24 所示。 此时该文件系统的目录结构已不再是树型结构，而是个有向非循环图 DAG(Directed Acyclic Graph)。
??如何建立B目录与共享文件之间的链接呢？如果在文件目录中包含了文件的物理地址， 即文件所在盘块的盘块号，则在链接时，必须将文件的物理地址拷贝到 B 目录中去。但如 果以后 B 或 C 还要继续向该文件中添加新内容，也必然要相应地再增加新的盘块，这须由 附加操作 Append 来完成。而这些新增加的盘块，也只会出现在执行了操作的目录中。可见， 这种变化对其他用户而言是不可见的，因而新增加的这部分内容已不能被共享。
??为了解决这个问题，可以引用索引结点，即诸如文件的物理地址及其它的文件属性等 信息，不再是放在目录项中，而是放在索引结点中。`在文件目录中只设置文件名及指向相 应索引结点的指针，如图 6-25 所示。此时，由任何用户对文件进行 Append 操作或修改， 所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见 的，从而也就能提供给其他用户来共享。
??在索引结点中还应有一个链接计数 count，用于表示链接到本索引结点(亦即文件)上的 用户目录项的数目。当 count=3 时，表示有三个用户目录项连接到本文件上，或者说是有三 个用户共享此文件。
??当用户 C 创建一个新文件时，他便是该文件的所有者，此时将 count 置 1。当有用户 B 要共享此文件时，在用户 B 的目录中增加一目录项，并设置一指针指向该文件的索引结点， 此时，文件主仍然是 C，count=2。如果用户 C 不再需要此文件，是否能将此文件删除呢？ 回答是否定的。因为，若删除了该文件，也必然删除了该文件的索引结点，这样便会使 B 的指针悬空，而 B 则可能正在此文件上执行写操作，此时将因此半途而废。但如果 C 不删 除此文件而等待 B 继续使用，这样，由于文件主是 C，如果系统要记账收费，则 C 必须为 B 使用此共享文件而付账，直至 B 不再需要。图 6-26 示出了 B 链接到文件上的前、后 情况。

6.6.2 利用符号链实现文件共享

??为使 B 能共享 C 的一个文件 F，可以由系统创建一个 LINK 类型的新文件，也取名为 F， 并将 F 写入 B 的目录中，以实现 B 的目录与文件 F 的链接。在新文件中只包含被链接文件 F 的路径名。这样的链接方法被称为符号链接(Symbolic Linking)。新文件中的路径名则只被 看作是符号链(Symbolic Link)，当 B 要访问被链接的文件 F 且正要读 LINK 类新文件时，此 要求将被 OS 截获，OS 根据新文件中的路径名去读该文件，于是就实现了用户 B 对文件 F 的共享。
??在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共 享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也 就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共 享文件删除后，其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找 不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。
??然而符号链的共享方式也存在自己的问题: 当其他用户去读共享文件时，系统是根据给 定的文件路径名，逐个分量(名)地去查找目录，直至找到该文件的索引结点。因此，在每次 访问共享文件时，都可能要多次地读盘。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而由于该链实际上是一个文件，尽 管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间。
??符号链方式有一个很大的优点，是它能够用于链接(通过计算机网络)世界上任何地方的 计算机中的文件，此时只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。
??上述两种链接方式都存在这样一个共同的问题，即每一个共享文件都有几个文件名。 换言之，每增加一条链接，就增加一个文件名。这在实质上就是每个用户都使用自己的路 径名去访问共享文件。当我们试图去遍历(traverse)整个文件系统时，将会多次遍历到该共享 文件。例如，当有一个程序员要将一个目录中的所有文件都转储到磁带上去时，就可能对 一个共享文件产生多个拷贝。

6.6.3 磁盘容错技术

??在现代计算机系统中，通常都存放了愈来愈多的宝贵信息供用户使用，给人们带来了 极大的好处和方便，但同时也潜在着不安全性。影响文件安全性的主要因素有三：

??(1) 人为因素，即由于人们有意或无意的行为，而使文件系统中的数据遭到破坏或丢失。
??(2) 系统因素，即由于系统的某部分出现异常情况，而造成对数据的破坏或丢失。特别 是作为数据存储介质的磁盘，在出现故障或损坏时，会对文件系统的安全性造成影响；
??(3) 自然因素，即存放在磁盘上的数据，随着时间的推移将可能发生溢出或逐渐消失。

??为了确保文件系统的安全性，可针对上述原因而采取以下措施：

??(1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。
??(2) 通过磁盘容错技术来防止由磁盘部分的故障所造成的文件不安全性。
??(3) 通过“后备系统”来防止由自然因素所造成的不安全性。

??本小节主要讨论磁盘容错技术，而存取控制机制将在系统安全性一章中介绍。
??容错技术是通过在系统中设置冗余部件的办法，来提高系统可靠性的一种技术。磁盘 容错技术则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的 一种技术，即当磁盘系统的某部分出现缺陷或故障时，磁盘仍能正常工作，且不致造成数 据的丢失或错误。目前广泛采用磁盘容错技术来改善磁盘系统的可靠性。
??磁盘容错技术往往也被人们称为系统容错技术 SFT。可把它分成三个级别：第一级是 低级磁盘容错技术；第二级是中级磁盘容错技术；第三级是系统容错技术，它基于集群技 术实现容错。

1. 第一级容错技术 SFT-Ⅰ

??第一级容错技术(SFT-Ⅰ)是最基本的一种磁盘容错技术，主要用于防止因磁盘表面缺陷 所造成的数据丢失。它包含双份目录、双份文件分配表及写后读校验等措施。

??1) 双份目录和双份文件分配表
??在磁盘上存放的文件目录和文件分配表 FAT，是文件管理所用的重要数据结构。为了 防止这些表格被破坏，可在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和 FAT。其中一份为主目录及主 FAT；另一份为备份目录及备份 FAT。一旦由于磁盘表面缺陷 而造成主文件目录或主 FAT 的损坏时，系统便自动启用备份文件目录及备份 FAT，从而可 以保证磁盘上的数据仍是可访问的。
??2) 热修复重定向和写后读校验
??由于磁盘价格昂贵，当磁盘表面有少量缺陷时，则可采取某种补救措施后继续使用磁 盘。一般主要采取以下两个补救措施：
????????(1) 热修复重定向：系统将磁盘容量的一部分(例如 2%～3%)作为热修复重定向区，用 于存放当发现磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记，以便于以后 对数据进行访问。
????????(2) 写后读校验方式。为了保证所有写入磁盘的数据都能写入到完好的盘块中，应该在 每次从内存缓冲区向磁盘中写入一个数据块后，又立即从磁盘上读出该数据块，并送至另 一缓冲区中，再将该缓冲区内容与内存缓冲区中在写后仍保留的数据进行比较。若两者一 致，便认为此次写入成功，可继续写下一个盘块；否则，再重写。若重写后两者仍不一致， 则认为该盘块有缺陷，此时，便将应写入该盘块的数据，写入到热修复重定向区中。

2. 第二级容错技术 SFT-Ⅱ
   ??第二级容错技术主要用于防止由磁盘驱动器和磁盘控制器故障所导致的系统不能正常 工作，它具体又可分为磁盘镜像和磁盘双工。

??1) 磁盘镜像(Disk Mirroring)
??为了避免磁盘驱动器发生故障而丢失数据，便增设了磁盘镜像功能。为实现该功能， 须在同一磁盘控制器下再增设一个完全相同的磁盘驱动器，如图 6-27 所示。当采用磁盘镜像方式时，在每次向主磁盘写入数据后，都需要将数据再写到备份磁盘上，使两个磁盘上具有完 全相同的位像图。把备份磁盘看作是主磁盘的一 面镜子，当主磁盘驱动器发生故障时，由于有备份磁盘的存在，在进行切换后，使主机仍能正常工作。磁盘镜像虽然实现了容错功能，但未能使 服务器的磁盘 I/O 速度得到提高，却使磁盘的利用率降至仅为 50%。如图 6-27 所示。
??2) 磁盘双工(Disk Duplexing)
??如果控制这两台磁盘驱动器的磁盘控制器发生故障，或主机到磁盘控制器之间的通道 发生了故障，磁盘镜像功能便起不到数据保护的作用。因此，在第二级容错技术中，又增 加了磁盘双工功能，即将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘 机镜像成对，如图 6-28 所示。
??在磁盘双工时，文件服务器同时将数据写到 磁盘 控制器 两个处于不同控制器下的磁盘上，使两者有完全相同的位像图。如果某个通道或控制器发生故障时，另一通道上的磁盘仍能正常工作，不会造成数据的丢失。在磁盘双工时，由于每一个磁盘都有自己的独立通道，故可同时(并行)地将数据写入磁盘，或读出数据。

3．基于集群技术的容错功能

??进入 20 世纪 90 年代后，为了进一步增强服务器的并行处理能力和可用性，采用了多 台 SMP 服务器来实现集群系统服务器。所谓集群，是指由一组互连的自主计算机组成统一 的计算机系统，给人们的感觉是，它们是一台机器。利用集群系统不仅可提高系统的并行 处理能力，还可用于提高系统的可用性，它们是当前使用最广泛的一类具有容错功能的集 群系统。其主要工作模式有三种：
??① 热备份模式；
??② 互为备份模式；
??③ 公用磁盘模式。

下面我们介绍如何利用集群系统来提高服务器的可用性。

??1) 双机热备份模式
??如图 6-29 所示，在这种模式的系统中，备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。平时主服务器运行，备份服务器则 时刻监视着主服务器的运行，一旦主服务器出现故障，备份服务器便立即接替主服务器的 工作而成为系统中的主服务器，修复后的服务器再作为备份服务器。
??为使在这两台服务器间能保持镜像关系，应在这两台服务器上各装入一块网卡，并通 过一条镜像服务器链路 MSL(Mirrored Server Link)将两台服务器连接起来。两台服务器之间 保持一定的距离，其所允许的距离取决于所配置的网卡和传输介质。如果用 FDDI 单模光纤， 两台服务器间的距离可达到 20 公里。此外，还必须在系统中设置某种机制，来检测主服务 器中数据的改变。一旦该机制检测到主服务器中有数据变化，便立即通过通信系统将修改 后的数据传送到备份服务器的相应数据文件中。为了保证在两台服务器之间通信的高速性 和安全性，通常都选用高速通信信道，并有备份线路。
??在这种模式下，一旦主服务器发生故障，系统能自动地将主要业务用户切换到备份服 务器上。为保证切换时间足够快(通常为数分钟)，要求在系统中配置有切换硬件的开关设备， 在备份服务器上事先建立好通信配置，并能迅速处理客户机的重新登录等事宜。
??该模式是早期使用的一种集群技术，它的最大优点是提高了系统的可用性，易于实现， 而且主、备份服务器完全独立，可支持远程热备份，从而能消除由于火灾、爆炸等非计算 机因素所造成的隐患。该模式的主要缺点是从服务器处于被动等待状态，整个系统的使用 效率只有 50%。
??2) 双机互为备份模式
??在双机互为备份的模式中，平时，两台服务器均为在线服务器，它们各自完成自己的 任务，例如，一台作为数据库服务器，另一台作为电子邮件服务器。为了实现两者互为备 份，在两台服务器之间，应通过某种专线连接起来。如果希望两台服务器之间能相距较远， 最好利用 FDDI 单模光纤来连接两台服务器，在此情况下，最好再通过路由器将两台服务器 互连起来，作为备份通信线路。图 6-30 示出了双机互为备份系统的情况。

??在互为备份的模式中，最好在每台服务器内都配置两台硬盘，一个用于装载系统程序 和应用程序，另一个用于接收由另一台服务器发来的备份数据，作为该服务器的镜像盘。 在正常运行时，镜像盘对本地用户是锁死的，这样就较易于保证在镜像盘中数据的正确性。 如果仅有一个硬盘，则可用建立虚拟盘的方式或分区方式来分别存放系统程序和应用程序， 以及另一台服务器的备份数据。
??如果通过专线链接检查到某台服务器发生了故障，此时，再通过路由器去验证这台服 务器是否真的发生了故障。如果故障被证实，则由正常服务器向故障服务器的客户机发出 广播信息，表明要进行切换。连接到故障服务器上的客户机在切换过程中会感觉到网络服 务器的短暂停顿。在切换成功后，客户机无需重新登录便可继续使用网络提供的服务和访 问服务器上的数据。而对于接在非故障服务器上的客户机，则只会感觉到网络服务稍有减 慢而已，不会有任何影响。当故障服务器修复并重新连到网上后，已被迁移到无故障服务 器上的服务功能将被返回，恢复正常工作。
??这种模式的优点是两台服务器都可用于处理任务，因而系统效率较高，现在已将这种 模式从两台机器扩大到 4 台、8 台、16 台甚至更多。系统中所有的机器都可用于处理任务， 当其中一台发生故障时，系统可指定另一台机器来接替它的工作。
??3) 公用磁盘模式
??为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公 共磁盘被划分为若干个卷。每台计算机使用一个卷。如果某台计算机发生故障，此时系统 将重新进行配置，根据某种调度策略来选择另一台替代机器，后者对发生故障的机器的卷 拥有所有权，从而来接替故障计算机所承担的任务。这种模式的优点是：消除了信息的复 制时间，因而减少了网络和服务器的开销。

6.7 数据一致性控制

6.7.1 事物

1. 事务的定义

??事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看做是一系列相关 读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，也可放在多个文件 中。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以 托付操作(Commit Operation)来终止事务。只要有一个读、写或修改操作失败，便须执行夭 折操作(Abort Operation)。读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导 致的。
??一个夭折的事务，通常已执行了一些操作，因而可能已对某些数据做了修改。为使夭 折的事务不会引起数据的不一致性，须将该事务内刚被修改的数据项恢复成原来的情况， 使系统中各数据项与该事务未执行时的数据项内容完全相同。此时，可以说该事务“已被 退回”(rolled back)。不难看出，一个事务在对一批数据执行修改操作时，要么全部完成， 并用修改后的数据去代替原来的数据，要么一个也不修改。事务操作所具有的这种特性， 就是我们在第二章中曾讲过的“原子性”。

2. 事务记录(Transaction Record)

??为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现。这些数据 结构被放在稳定存储器中，用来记录在事务运行时数据项修改的全部信息，故又称为运行 记录(Log)。该记录中包括有下列字段:
??· 事务名：用于标识该事务的惟一名字；
??· 数据项名：指被修改数据项的惟一名字；
??· 旧值：修改前数据项的值；
??· 新值：修改后数据项将具有的值。
??在事务记录表中的每一记录，描述了在事务运行中的重要事务操作，如修改操作、开 始事务、托付事务或夭折事务等。在一个事务 T i 开始执行时，〈T i 开始〉记录被写入事务记 录表中；在 T i 执行期间，在 T i 的任何写(修改)操作之前，便写一适当的新记录到事务记录 表中；当 T i 进行托付时，把一个〈T i 托付〉记录写入事务记录表中。

3. 恢复算法

??由于一组被事务 T i 修改的数据以及它们被修改前和修改后的值都能在事务记录表中找 到，因此，利用事务记录表，系统能处理任何故障而不致使故障造成非易失性存储器中信息的丢失。恢复算法可利用以下两个过程:
????(1) undo〈Ti 〉。该过程把所有被事务 T i 修改过的数据恢复为修改前的值。
????(2) redo〈Ti 〉。该过程把所有被事务 T i 修改过的数据设置为新值。
??如果系统发生故障，系统应对以前所发生的事务进行清理。通过查找事务记录表，可 以把尚未清理的事务分成两类。一类是其所包含的各类操作都已完成的事务。确定为这一 类事务的依据是，在事务记录表中，既包含了〈T i 开始〉记录，又包含了〈T i 托付〉记录。 此时系统利用 redo〈Ti 〉过程，把所有已被修改的数据设置成新值。另一类是其所包含的 各个操作并未全部完成的事务。对于事务 Ti ，如果在 Log 表中只有〈T i 开始〉记录而无 〈T i 托付〉记录，则此 T i 便属于这类事务。此时，系统便利用 undo〈Ti 〉过程，将所有已 被修改的数据，恢复为修改前的值。

6.7.2 检查点

1. 检查点(Check Points)的作用

??如前所述，当系统发生故障时，必须去检查整个 Log 表，以确定哪些事务需要利用 redo〈Ti 〉过程去设置新值，而哪些事务需要利用 undo〈Ti 〉过程去恢复数据的旧值。由于 在系统中可能存在着许多并发执行的事务，因而在事务记录表中就会有许多事务执行操作 的记录。随着时间的推移，记录的数据也会愈来愈多。因此，一旦系统发生故障，在事务 记录表中的记录清理起来就非常费时。
??引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化，即每隔一 定时间便做一次下述工作：首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所 有记录输出到稳定存储器中；其次是将驻留在易失性存储器中的所有已修改数据输出到稳 定存储器中；然后是将事务记录表中的〈检查点〉记录输出到稳定存储器中；最后是每当 出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用 redo 和 undo 过程 实现恢复功能。
??如果一个事务 T i 在检查点前就做了托付，则在事务记录表中便会出现一个在检查点记 录前的〈T i 托付〉记录。在这种情况下，所有被 T i 修改过的数据，或者是在检查点前已写 入稳定存储器，或者是作为检查点记录自身的一部分写入稳定存储器中。因此，以后在系 统出现故障时，就不必再执行 redo 操作了。

2. 新的恢复算法

??在引入检查点后，可以大大减少恢复处理的开销。因为在发生故障后，并不需要对事 务记录表中的所有事务记录进行处理， 而只需对最后一个检查点之后的事务记录进行处 理。因此，恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务 Ti 。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例 程便从该检查点开始，返回搜索各个事务的记录，并利用 redo 和 undo 过程对它们进行 处理。
??如果把所有在事务 T i 以后开始执行的事务表示为事务集 T，则新的恢复操作要求是: 对 所有在 T 中的事务 TK ，如果在事务记录表中出现了〈T K 托付〉记录，则执行 redo〈TK 〉 操作；反之，如果在事务记录表中并未出现〈T K 托付〉记录，则执行 undo〈TK 〉操作。

6.7.3 并发控制

1. 利用互斥锁实现“顺序性”

??实现顺序性的一种最简单的方法是， 设置一种用于实现互斥的锁， 简称为互斥锁 (Exclusive Lock)。在利用互斥锁实现顺序性时，应为每一个共享对象设置一把互斥锁。当一 事务 T i 要去访问某对象时，应先获得该对象的互斥锁。若成功，便用该锁将该对象锁住， 于是事务 T i 便可对该对象执行读或写操作；而其它事务由于未能获得该锁而不能访问该对 象。如果 T i 需要对一批对象进行访问，则为了保证事务操作的原子性，T i 应先获得这一批 对象的互斥锁，以将这些对象全部锁住。如果成功，便可对这一批对象执行读或写操作； 操作完成后又将所有这些锁释放。但如果在这一批对象中的某一个对象已被其它事物锁住， 则此时 T i 应对此前已被 T i 锁住的其它对象进行开锁，宣布此次事务运行失败，但不致引起 数据的变化。

2. 利用互斥锁和共享锁实现顺序性

??利用互斥锁实现顺序性的方法简单易行。目前有不少系统都是采用这种方法来保证事 务操作的顺序性，但这却存在着效率不高的问题。因为一个共享文件虽然只允许一个事务 去写，但却允许多个事务同时去读；而在利用互斥锁来锁住文件后，则只允许一个事务去 读。为了提高运行效率而又引入了另一种形式的锁——共享锁(Shared Lock)。共享锁与互斥 锁的区别在于: 互斥锁仅允许一个事务对相应对象执行读或写操作，而共享锁则允许多个事 务对相应对象执行读操作，不允许其中任何一个事务对对象执行写操作。
??在为一个对象设置了互斥锁和共享锁的情况下，如果事务 T i 要对 Q 执行读操作，则只 需去获得对象 Q 的共享锁。如果对象 Q 已被互斥锁锁住，则 T i 必须等待；否则，便可获得 共享锁而对 Q 执行读操作。如果 T i 要对 Q 执行写操作，则 T i 还须去获得 Q 的互斥锁。若 失败，须等待；否则，可获得互斥锁而对 Q 执行写操作。利用共享锁和互斥锁来实现顺序 性的方法，非常类似于我们在第二章中所介绍的读者—写者问题的解法。

6.7.4 重复数据的数据一致性问题

1. 重复文件的一致性

??我们以 UNIX 类型的文件系统为例，来说明如何保证重复文件的一致性问题。对于通 常的 UNIX 文件目录，其每个目录项中含有一个 ASCII 码的文件名和一个索引结点号，后 者指向一个索引结点。当有重复文件时，一个目录项可由一个文件名和若干个索引结点号 组成，每个索引结点号都是指向各自的索引结点。图 6-31 示出了 UNIX 类型的目录和具有 重复文件的目录。??在有重复文件时，如果一个文件拷贝被修改，则必须也同时修改其它几个文件拷贝， 以保证各相应文件中数据的一致性。这可采用两种方法来实现：第一种方法是当一个文件 被修改后，可查找文件目录，以得到其它几个拷贝的索引结点号，再从这些索引结点中找 到各拷贝的物理位置，然后对这些拷贝做同样的修改；第二种方法是为新修改的文件建立 几个拷贝，并用新拷贝去取代原来的文件拷贝。

2. 盘块号一致性的检查

??为了描述盘块的使用情况，通常利用空闲盘块表(链)来记录所有尚未使用的空闲盘块的 编号。文件分配表 FAT 则是用于记录已分配盘块的使用情况。由于 OS 经常访问这些数据 结构，也对它们进行修改，而如果正在修改时，机器突然发生故障，此时也会使盘块数据 结构中的数据产生不一致性现象。因此，在每次启动机器时，都应该检查相应的多个数据 结构，看它们之间是否保持了数据的一致性。
??为了保证盘块数据结构(中数据)的一致性，可利用软件方法构成一个计数器表，每个盘 块号占一个表项，可有 0，…，N-1 项，N 为盘块总数。每一个表项中包含两个计数器，分 别用作空闲盘块号计数器和数据盘块号计数器。计数器表中的表项数目等于盘块数 N。在对 盘块的数据结构进行检查时，应该先将计数器表中的所有表项初始化为 0，然后，用 N 个空 闲盘块号计数器所组成的第一组计数器来对从空闲盘块表(链)中读出的盘块号进行计数；再 用 N 个数据盘块号计数器所组成的第二组计数器去对从文件分配表中读出的、已分配给文 件使用的盘块号进行计数。如果情况正常，则上述两组计数器中对应的一对(计数器中的) 数据应该互补，亦即，若某个盘块号在被第一组计数器进行计数后，使该盘块号计数器为 1， 则在第二组计数器中相应盘块号计数器中的计数必为 0；反之亦然。但如果情况并非如此， 则说明发生了某种错误。
??图 6-32(a)示出了在正常情况下，在第一组计数器和第二组计数器中的盘块号计数值是 互补的；而图 6-32(b)示出的则是一种不正常的情况，对盘块号 2 的计数值在两组计数器中 都未出现(即均为 0)。当检查出这种情况时，应向系统报告。该错误的影响并不大，只是盘 块 2 未被利用。其解决方法也较简单，只需在空闲盘块表(链)中增加一个盘块号 2。图 6-32? 中示出了另一种错误，即盘块号 4 在空闲盘块表(链)中出现了两次，其解决方法是从空闲盘 块表(链)中删除一个空闲盘块号 4。图 6-32(d)中所示出的情况是相同的数据盘块号 5 出现了 两次(或多次)，此种情况影响较严重，必须立即报告。

3. 链接数一致性检查

??在 UNIX 类型的文件目录中，其每个目录项内都含有一个索引结点号，用于指向该文 件的索引结点。对于一个共享文件，其索引结点号会在目录中出现多次。例如，当有 5 个 用户(进程)共享某文件时，其索引结点号会在目录中出现 5 次；另一方面，在该共享文件的 索引结点中有一个链接计数 count，用来指出共享本文件的用户(进程)数。在正常情况下这 两个数据应该一致，否则就会出现数据不一致性差错。
??为了检查这种数据不一致性差错，同样要配置一张计数器表，此时应是为每个文件而不是为每个盘块建立一个表项，其中含有该索引结点号的计数值。在进行检查时，从根目 录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加 1。 当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件 索引结点中的链接计数 count 值加以比较，如果两者一致，表示是正确的；否则，便是产生 了链接数据不一致的错误。
??如果索引结点中的链接计数 count 值大于计数器表中相应索引结点号的计数值，则即使 在所有共享此文件的用户都不再使用此文件时，其 count 值仍不为 0，因而该文件不会被删 除。这种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上，浪费了存储空间。当 然这种错误的性质并不严重。解决的方法是用计数器表中的正确的计数值去为 count 重新 赋值。
??反之，如果出现 count 值小于计数器表中索引结点号计数值的情况时，就有潜在的危险。 假如有两个用户共享一个文件，但是 count 值仍为 1，这样，只要其中有一个用户不再需要 此文件时，count 值就会减为 0，从而使系统将此文件删除，并释放其索引结点及文件所占 用的盘块，导致另一共享此文件的用户所对应的目录项指向了一个空索引结点，最终是使 该用户再无法访问此文件。如果该索引结点很快又被分配给其它文件，则又会带来潜在的 危险。解决的方法是将 count 值置为正确值。