第六章 文 件 管 理 6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 第六章　文 件 管 理 6.1　文件和文件系统 6.2　文件的逻辑结构 6.3　外存分配方式 6.4　目录管理 6.5　文件存储空间的管理 6.6　文件共享与文件保护 6.7　数据一致性控制

6.1 文件和文件系统 6.1.1 文件、记录和数据项 1．数据项 在文件系统中，数据项是最低级的数据组织形式，可把它分成以下两种类型: 6.1　文件和文件系统 6.1.1　文件、记录和数据项 　　1．数据项 　　在文件系统中，数据项是最低级的数据组织形式，可把它分成以下两种类型: 　　(1) 基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。例如，用于描述一个学生的基本数据项有学号、姓名、年龄、所在班级等。

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

　　2．记录 　　记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把他作为不同的对象。例如，一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。但若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项。

　　在诸多记录中，为了能惟一地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字(key)。或者说，关键字是惟一能标识一个记录的数据项。通常，只需用一个数据项作为关键字。例如，前面的病历号或学号便可用来从诸多记录中标识出惟一的一个记录。然而有时找不到这样的数据项，只好把几个数据项定为能在诸多记录中惟一地标识出某个记录的关键字。

　　3．文件 　　文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。例如，可以将一个班的学生记录作为一个文件。一个文件必须要有一个文件名，它通常是由一串ASCII码或(和)汉字构成的，名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中又规定可用14个字符。用户利用文件名来访问文件。

　　此外，文件应具有自己的属性，属性可以包括： 　　(1) 文件类型。可以从不同的角度来规定文件的类型，如源文件、目标文件及可执行文件等。 　　(2) 文件长度。文件长度指文件的当前长度，长度的单位可以是字节、字或块，也可能是最大允许的长度。 　　(3) 文件的物理位置。该项属性通常是用于指示文件在哪一个设备上及在该设备的哪个位置的指针。 　　(4) 文件的建立时间。这是指文件最后一次的修改时间等。

图6-1　文件、记录和数据项之间的层次关系

6.1.2　文件类型和文件系统模型 　　1．文件类型 　　为了便于管理和控制文件而将文件分成若干种类型。由于不同系统对文件的管理方式不同，因而它们对文件的分类方法也有很大差异。为了方便系统和用户了解文件的类型，在许多OS中都把文件类型作为扩展名而缀在文件名的后面，在文件名和扩展名之间用“.”号隔开。下面是常用的几种文件分类方法。

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

图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 文件的逻辑结构 6.2.1 文件逻辑结构的类型 1．有结构文件 6.2　文件的逻辑结构 6.2.1　文件逻辑结构的类型 　　1．有结构文件 　　在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。 　　(1) 定长记录。这是指文件中所有记录的长度都是相同的，所有记录中的各数据项都处在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录的处理方便、开销小，所以这是目前较常用的一种记录格式，被广泛用于数据处理中。

　　(2) 变长记录。这是指文件中各记录的长度不相同。产生变长记录的原因，可能是由于一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等；也可能是数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。不论是哪一种，在处理前，每个记录的长度是可知的。 　　根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件： 　　(1) 顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。

　　(2) 索引文件。当记录为可变长度时，通常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。 　　(3) 索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。

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

6.2.2　顺序文件 　　1．逻辑记录的排序 　　文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的顺序进行排列。一般地，可归纳为以下两种情况： 　　第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录……， 依此类推。

　　第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。 　　对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必须从头开始，逐个记录地查找，直至找到指定的记录，或查完所有的记录为止。而对顺序结构文件，则可利用某种有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法来提高检索效率。

　　2．对顺序文件(Sequential File)的读/写操作 　　顺序文件中的记录可以是定长的，也可以是变长的。对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。在读一个文件时，可设置一个读指针Rptr，令它指向下一个记录的首地址，每当读完一个记录时，便执行 　　Rptr:=Rptr + L

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

图6-3　定长和变长记录文件

　　3．顺序文件的优缺点 　　顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录时。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。

　　在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。例如，有一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5×103个记录；如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。

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

6.2.3　索引文件 　　对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址： Ai = i × L 　　然而，对于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则 　

　　可见，对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。然而，对于变长记录就较难实现直接存取了，因为用直接存取方法来访问变长记录文件中的一个记录是十分低效的，其检索时间也很难令人接受。为了解决这一问题，可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于记录该记录的长度L及指向该记录的指针(指向该记录在逻辑地址空间的首址)。由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地实现直接存取。图6-4示出了索引文件(Index File)的组织形式。

图6-4　索引文件的组织

6.2.4　索引顺序文件 　　索引顺序文件(Index Sequential File)可能是最常见的一种逻辑文件形式。它有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。前已述及，它是顺序文件和索引文件相结合的产物。它将顺序文件中的所有记录分为若干个组(例如，50个记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。索引顺序文件如图6-5所示。

图6-5　索引顺序文件

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

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

图6-6　Hash文件的逻辑结构

6.3　外存分配方式 6.3.1　连续分配 　　1．连续分配方式 　　连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2……。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。

　　在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图6-7 示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count文件的第一个盘块号是0，文件长度为2，因此是在盘块号为0和1的两盘块中存放文件1的数据。

图6-7　磁盘空间的连续分配

　　如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(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个字节可供用户使用。

图6-8　磁盘空间的链接式分配

　　隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块……，就这样顺序地查找直至第i块。当i=100时，须启动100次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。

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

图6-9　显式链接结构

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的存储空间。

图6-10　MS-DOS的文件物理结构

　　现在我们来计算以盘块为分配单位时，所允许的最大磁盘容量。由于每个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可以管理的最大分区空间为216 × 64 × 512 = 2048 MB。 　　

　　由上述分析不难看出，FAT16对FAT12的局限性有所改善，但改善很有限。当磁盘容量迅速增加时，如果再继续使用FAT16，由此所形成的簇内碎片所造成的浪费也越大。例如，当要求磁盘分区的大小为8 GB时，则每个簇的大小达到128 KB，这意味着内部零头最大可达到128 KB。一般而言，对于1～4 GB的硬盘来说，大约会浪费10％～20％的空间。为了解决这一问题，微软推出了FAT32。

　　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×232 = 2 TB。三种FAT类型的最大分区以及所对应的块的大小如图6-11所示。

图6-11 FAT中簇的大小与最大分区的对应关系

　　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空间，可能记录不下文件的全部信息。所以当文件较小时，其属性值所占空间也较小，可以将文件的所有属性直接记录在元数据中。而当文件较大时，元数据仅记录该文件的一部分属性，其余属性，如文件的内容等，可以记录到卷中的其它可用簇中，并将这些簇按其所记录文件的属性进行分类，分别链接成多个队列，将指向这些队列的指针保存在元数据中。

6.3.4　索引分配 　　1．单级索引分配 　　链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题： 　　(1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。

　　(2) FAT需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。当磁盘容量较大时，FAT可能要占用数兆字节以上的内存空间，这是令人难以接受的。 　　事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个FAT调入内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图6-12 示出了磁盘空间的索引分配图。

图6-12　索引分配方式

　　2．多级索引分配 　　当OS为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS便为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。

　　图6-13示出了两级索引分配方式下各索引块之间的链接情况。如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。这样，在两级索引时， 最多可包含的存放文件的盘块的盘块号总数N = 256 × 256 = 64 K个盘块号。由此可得出结论: 采用两级索引时，所允许的文件最大长度为64 MB。倘若盘块的大小为4 KB，在采用单级索引时所允许的最大文件长度为4 MB；而在采用两级索引时所允许的最大文件长度可达4 GB。

图6-13　两级索引分配

　　3．混合索引分配方式 　　所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。这种混合索引分配方式已在UNIX系统中采用。在UNIX System Ⅴ的索引结点中，共设置了13个地址项，即iaddr(0)～iaddr(12)，如图6-14所示。在BSD UNIX的索引结点中，共设置了13个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。

图6-14　混合索引方式

　　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的存储空间。

图6-15　MS-DOS的文件控制块

　　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的文件目录项。

0　　　　  13  14　　　　 　 15 图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所示。

图6-17　单级目录

　　每当要建立一个新文件时，必须先检索所有的目录项，以保证新文件名在目录中是惟一的。然后再从目录表中找出一个空白目录项，填入新文件的文件名及其它说明信息，并置状态位为1。删除文件时，先从目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。 　　单级目录的优点是简单且能实现目录管理的基本功能——按名存取，但却存在下述一些缺点： 　　(1) 查找速度慢。对于稍具规模的文件系统，会拥有数目可观的目录项，致使为找到一个指定的目录项要花费较多的时间。对于一个具有N个目录项的单级目录，为检索出一个目录项，平均需查找N/2个目录项。

　　(2) 不允许重名。在一个目录表中的所有文件，都不能与另一个文件有相同的名字。然而，重名问题在多道程序环境下却又是难以避免的；即使在单用户环境下，当文件数超过数百个时，也难于记忆。 　　(3) 不便于实现文件共享。通常，每个用户都有自己的名字空间或命名习惯。因此，应当允许不同用户使用不同的文件名来访问同一个文件。然而，单级目录却要求所有用户都用同一个名字来访问同一文件。简言之，单级目录只能满足对目录管理的四点要求中的第一点， 因而，它只能适用于单用户环境。

　　2．两级目录 　　为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目录UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块组成。此外，在系统中再建立一个主文件目录MFD(Master File Directory)；在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针。如图6-18 所示，图中的主目录中示出了三个用户名，即Wang、Zhang和Gao。

图6-18　两级目录结构

　　在两级目录结构中，如果用户希望有自己的用户文件目录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。

图6-19　多级目录结构

　　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所示。

图6-20　查找/usr/ast/mbox的步骤

　　具体查找过程说明如下： 　　首先，系统应先读入第一个文件分量名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值，即出现了所谓的“冲突”。一种处理此“冲突”的有效规则是: 　　(2) 如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。 　　(3) 如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值，再返回到第一步重新开始查找。

6.5 文件存储空间的管理 6.5.1 空闲表法和空闲链表法 1．空闲表法 1) 空闲表 6.5　文件存储空间的管理 6.5.1　空闲表法和空闲链表法 　　1．空闲表法 　　1) 空闲表 　　空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，如图6-21所示。

图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；

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 图6-22　位示图

b = n(i - 1) + j 2．盘块的分配 根据位示图进行盘块分配时，可分三步进行： 　　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　成组链接法 　　1．空闲盘块的组织 　　(1) 空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块号数N。顺便指出，N还兼作栈顶指针用。例如，当N=100时，它指向S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。图6-23左部示出了空闲盘块号栈的结构。其中，S.free(0)是栈底，栈满时的栈顶为S.free(99)。

图6-23　空闲盘块的成组链接法

　　(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.6　文件共享与文件保护 6.6.1　基于索引结点的共享方式 　　在树型结构的目录中，当有两个(或多个)用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个(或多个)用户的目录中，才能方便地找到该文件，如图6-24 所示。此时该文件系统的目录结构已不再是树型结构，而是个有向非循环图DAG(Directed Acyclic Graph)。

图6-24　包含有共享文件的文件系统

　　如何建立B目录与共享文件之间的链接呢？如果在文件目录中包含了文件的物理地址，即文件所在盘块的盘块号，则在链接时，必须将文件的物理地址拷贝到B目录中去。但如果以后B或C还要继续向该文件中添加新内容，也必然要相应地再增加新的盘块，这须由附加操作Append来完成。而这些新增加的盘块，也只会出现在执行了操作的目录中。可见，这种变化对其他用户而言是不可见的，因而新增加的这部分内容已不能被共享。

　　为了解决这个问题，可以引用索引结点，即诸如文件的物理地址及其它的文件属性等信息，不再是放在目录项中，而是放在索引结点中。`在文件目录中只设置文件名及指向相应索引结点的指针，如图6-25所示。此时，由任何用户对文件进行Append操作或修改，所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见的，从而也就能提供给其他用户来共享。

图6-25　基于索引结点的共享方式

　　在索引结点中还应有一个链接计数count，用于表示链接到本索引结点(亦即文件)上的用户目录项的数目。当count=3时，表示有三个用户目录项连接到本文件上，或者说是有三个用户共享此文件。

　　当用户C创建一个新文件时，他便是该文件的所有者，此时将count置1。当有用户B要共享此文件时，在用户B的目录中增加一目录项，并设置一指针指向该文件的索引结点，此时，文件主仍然是C，count=2。如果用户C不再需要此文件，是否能将此文件删除呢？回答是否定的。因为，若删除了该文件，也必然删除了该文件的索引结点，这样便会使B的指针悬空，而B则可能正在此文件上执行写操作，此时将因此半途而废。但如果C不删除此文件而等待B继续使用，这样，由于文件主是C，如果系统要记账收费，则C必须为B使用此共享文件而付账，直至B不再需要。图6-26示出了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的共享。

　　在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共享文件删除后，其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。

　　然而符号链的共享方式也存在自己的问题: 当其他用户去读共享文件时，系统是根据给定的文件路径名，逐个分量(名)地去查找目录，直至找到该文件的索引结点。因此，在每次访问共享文件时，都可能要多次地读盘。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而由于该链实际上是一个文件，尽管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间。 　　符号链方式有一个很大的优点，是它能够用于链接(通过计算机网络)世界上任何地方的计算机中的文件，此时只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。

6.6.3　磁盘容错技术 　　在现代计算机系统中，通常都存放了愈来愈多的宝贵信息供用户使用，给人们带来了极大的好处和方便，但同时也潜在着不安全性。影响文件安全性的主要因素有三： 　　(1) 人为因素，即由于人们有意或无意的行为，而使文件系统中的数据遭到破坏或丢失。 　　(2) 系统因素，即由于系统的某部分出现异常情况，而造成对数据的破坏或丢失。特别是作为数据存储介质的磁盘，在出现故障或损坏时，会对文件系统的安全性造成影响； 　　(3) 自然因素，即存放在磁盘上的数据，随着时间的推移将可能发生溢出或逐渐消失。

　　为了确保文件系统的安全性，可针对上述原因而采取以下措施： 　　(1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。 　　(2) 通过磁盘容错技术来防止由磁盘部分的故障所造成的文件不安全性。 　　(3) 通过“后备系统”来防止由自然因素所造成的不安全性。

　　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所示。

图6-27　磁盘镜像示意

　　2) 磁盘双工(Disk Duplexing) 　　如果控制这两台磁盘驱动器的磁盘控制器发生故障，或主机到磁盘控制器之间的通道发生了故障，磁盘镜像功能便起不到数据保护的作用。因此，在第二级容错技术中，又增加了磁盘双工功能，即将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘机镜像成对，如图6-28所示。 　　在磁盘双工时，文件服务器同时将数据写到两个处于不同控制器下的磁盘上，使两者有完全相同的位像图。如果某个通道或控制器发生故障时，另一通道上的磁盘仍能正常工作，不会造成数据的丢失。在磁盘双工时，由于每一个磁盘都有自己的独立通道，故可同时(并行)地将数据写入磁盘，或读出数据。

图6-28 磁盘双工示意

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

　　1) 双机热备份模式 　　如图6-29所示，在这种模式的系统中，备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。平时主服务器运行，备份服务器则时刻监视着主服务器的运行，一旦主服务器出现故障，备份服务器便立即接替主服务器的工作而成为系统中的主服务器，修复后的服务器再作为备份服务器。

图6-29 双机热备份模式

　　2) 双机互为备份模式 　　在双机互为备份的模式中，平时，两台服务器均为在线服务器，它们各自完成自己的任务，例如，一台作为数据库服务器，另一台作为电子邮件服务器。为了实现两者互为备份，在两台服务器之间，应通过某种专线连接起来。如果希望两台服务器之间能相距较远，最好利用FDDI单模光纤来连接两台服务器，在此情况下，最好再通过路由器将两台服务器互连起来，作为备份通信线路。图6-30示出了双机互为备份系统的情况。

图6-30 双机互为备份系统的示意图

　　在互为备份的模式中，最好在每台服务器内都配置两台硬盘，一个用于装载系统程序和应用程序，另一个用于接收由另一台服务器发来的备份数据，作为该服务器的镜像盘。在正常运行时，镜像盘对本地用户是锁死的，这样就较易于保证在镜像盘中数据的正确性。如果仅有一个硬盘，则可用建立虚拟盘的方式或分区方式来分别存放系统程序和应用程序，以及另一台服务器的备份数据。

　　如果通过专线链接检查到某台服务器发生了故障，此时，再通过路由器去验证这台服务器是否真的发生了故障。如果故障被证实，则由正常服务器向故障服务器的客户机发出广播信息，表明要进行切换。连接到故障服务器上的客户机在切换过程中会感觉到网络服务器的短暂停顿。在切换成功后，客户机无需重新登录便可继续使用网络提供的服务和访问服务器上的数据。而对于接在非故障服务器上的客户机，则只会感觉到网络服务稍有减慢而已，不会有任何影响。当故障服务器修复并重新连到网上后，已被迁移到无故障服务器上的服务功能将被返回，恢复正常工作。

　　这种模式的优点是两台服务器都可用于处理任务，因而系统效率较高，现在已将这种模式从两台机器扩大到4台、8台、16台甚至更多。系统中所有的机器都可用于处理任务，当其中一台发生故障时，系统可指定另一台机器来接替它的工作。

　　3) 公用磁盘模式 　　为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公共磁盘被划分为若干个卷。每台计算机使用一个卷。如果某台计算机发生故障，此时系统将重新进行配置，根据某种调度策略来选择另一台替代机器，后者对发生故障的机器的卷拥有所有权，从而来接替故障计算机所承担的任务。这种模式的优点是：消除了信息的复制时间，因而减少了网络和服务器的开销。

6.7　数据一致性控制 6.7.1　事务 　　1．事务的定义 　　事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看做是一系列相关读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，也可放在多个文件中。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以托付操作(Commit Operation)来终止事务。只要有一个读、写或修改操作失败，便须执行夭折操作(Abort Operation)。读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导致的。

　　一个夭折的事务，通常已执行了一些操作，因而可能已对某些数据做了修改。为使夭折的事务不会引起数据的不一致性，须将该事务内刚被修改的数据项恢复成原来的情况，使系统中各数据项与该事务未执行时的数据项内容完全相同。此时，可以说该事务“已被退回”(rolled back)。不难看出，一个事务在对一批数据执行修改操作时，要么全部完成，并用修改后的数据去代替原来的数据，要么一个也不修改。事务操作所具有的这种特性，就是我们在第二章中曾讲过的“原子性”。

　　2．事务记录(Transaction Record) 　　为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现。这些数据结构被放在稳定存储器中，用来记录在事务运行时数据项修改的全部信息，故又称为运行记录(Log)。该记录中包括有下列字段: · 事务名：用于标识该事务的惟一名字； · 数据项名：指被修改数据项的惟一名字； · 旧值：修改前数据项的值； · 新值：修改后数据项将具有的值。

　　在事务记录表中的每一记录，描述了在事务运行中的重要事务操作，如修改操作、开始事务、托付事务或夭折事务等。在一个事务Ti开始执行时，〈 Ti开始〉记录被写入事务记录表中；在Ti执行期间，在Ti的任何写(修改)操作之前，便写一适当的新记录到事务记录表中；当Ti进行托付时，把一个〈 Ti托付〉记录写入事务记录表中。

　　3．恢复算法 　　由于一组被事务Ti修改的数据以及它们被修改前和修改后的值都能在事务记录表中找到，因此，利用事务记录表，系统能处理任何故障而不致使故障造成非易失性存储器中信息的丢失。恢复算法可利用以下两个过程: 　　(1) undo〈Ti〉。该过程把所有被事务Ti修改过的数据恢复为修改前的值。 　　(2) redo〈Ti〉。该过程把所有被事务Ti修改过的数据设置为新值。

　　如果系统发生故障，系统应对以前所发生的事务进行清理。通过查找事务记录表，可以把尚未清理的事务分成两类。一类是其所包含的各类操作都已完成的事务。确定为这一类事务的依据是，在事务记录表中，既包含了〈Ti开始〉记录，又包含了〈Ti托付〉记录。此时系统利用redo〈Ti〉过程，把所有已被修改的数据设置成新值。另一类是其所包含的各个操作并未全部完成的事务。对于事务Ti，如果在Log表中只有〈Ti开始〉记录而无〈Ti托付〉记录，则此Ti便属于这类事务。此时，系统便利用undo〈Ti〉过程，将所有已被修改的数据，恢复为修改前的值。

6.7.2　检查点 　　1．检查点(Check Points)的作用 　　如前所述，当系统发生故障时，必须去检查整个Log表，以确定哪些事务需要利用redo〈Ti〉过程去设置新值，而哪些事务需要利用undo〈Ti〉过程去恢复数据的旧值。由于在系统中可能存在着许多并发执行的事务，因而在事务记录表中就会有许多事务执行操作的记录。随着时间的推移，记录的数据也会愈来愈多。因此，一旦系统发生故障，在事务记录表中的记录清理起来就非常费时。

　　引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化，即每隔一定时间便做一次下述工作：首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录输出到稳定存储器中；其次是将驻留在易失性存储器中的所有已修改数据输出到稳定存储器中；然后是将事务记录表中的〈检查点〉记录输出到稳定存储器中；最后是每当出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。

　　如果一个事务Ti在检查点前就做了托付，则在事务记录表中便会出现一个在检查点记录前的〈Ti托付〉记录。在这种情况下，所有被Ti修改过的数据，或者是在检查点前已写入稳定存储器，或者是作为检查点记录自身的一部分写入稳定存储器中。因此，以后在系统出现故障时，就不必再执行redo操作了。

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

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

　　2．利用互斥锁和共享锁实现顺序性 　　利用互斥锁实现顺序性的方法简单易行。目前有不少系统都是采用这种方法来保证事务操作的顺序性，但这却存在着效率不高的问题。因为一个共享文件虽然只允许一个事务去写，但却允许多个事务同时去读；而在利用互斥锁来锁住文件后，则只允许一个事务去读。为了提高运行效率而又引入了另一种形式的锁——共享锁(Shared Lock)。共享锁与互斥锁的区别在于: 互斥锁仅允许一个事务对相应对象执行读或写操作，而共享锁则允许多个事务对相应对象执行读操作，不允许其中任何一个事务对对象执行写操作。

　　在为一个对象设置了互斥锁和共享锁的情况下，如果事务Ti要对Q执行读操作，则只需去获得对象Q的共享锁。如果对象Q已被互斥锁锁住，则Ti必须等待；否则，便可获得共享锁而对Q执行读操作。如果Ti要对Q执行写操作，则Ti还须去获得Q的互斥锁。若失败，须等待；否则，可获得互斥锁而对Q执行写操作。利用共享锁和互斥锁来实现顺序性的方法，非常类似于我们在第二章中所介绍的读者—写者问题的解法。

6.7.4　重复数据的数据一致性问题 　　1．重复文件的一致性 　　我们以UNIX类型的文件系统为例，来说明如何保证重复文件的一致性问题。对于通常的UNIX文件目录，其每个目录项中含有一个ASCII码的文件名和一个索引结点号，后者指向一个索引结点。当有重复文件时，一个目录项可由一个文件名和若干个索引结点号组成，每个索引结点号都是指向各自的索引结点。图6-31 示出了UNIX类型的目录和具有重复文件的目录。

图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(c)中示出了另一种错误，即盘块号4在空闲盘块表(链)中出现了两次，其解决方法是从空闲盘块表(链)中删除一个空闲盘块号4。图 6-32(d)中所示出的情况是相同的数据盘块号5出现了两次(或多次)，此种情况影响较严重，必须立即报告。

(a) 正常情况盘块号 (b) 丢失了盘块盘块号 图6-32　检查盘块号一致性情况

(c) 空闲盘块号重复出现盘块号 (d) 数据盘块号重复出现

　　3．链接数一致性检查 　　在UNIX类型的文件目录中，其每个目录项内都含有一个索引结点号，用于指向该文件的索引结点。对于一个共享文件，其索引结点号会在目录中出现多次。例如，当有5个用户(进程)共享某文件时，其索引结点号会在目录中出现5次；另一方面，在该共享文件的索引结点中有一个链接计数count，用来指出共享本文件的用户(进程)数。在正常情况下这两个数据应该一致，否则就会出现数据不一致性差错。

　　为了检查这种数据不一致性差错，同样要配置一张计数器表，此时应是为每个文件而不是为每个盘块建立一个表项，其中含有该索引结点号的计数值。在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较，如果两者一致，表示是正确的；否则，便是产生了链接数据不一致的错误。

　　如果索引结点中的链接计数count值大于计数器表中相应索引结点号的计数值，则即使在所有共享此文件的用户都不再使用此文件时，其count值仍不为0，因而该文件不会被删除。这种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上，浪费了存储空间。当然这种错误的性质并不严重。解决的方法是用计数器表中的正确的计数值去为count重新赋值。

　　反之，如果出现count值小于计数器表中索引结点号计数值的情况时，就有潜在的危险。假如有两个用户共享一个文件，但是count值仍为1，这样，只要其中有一个用户不再需要此文件时，count值就会减为0，从而使系统将此文件删除，并释放其索引结点及文件所占用的盘块，导致另一共享此文件的用户所对应的目录项指向了一个空索引结点，最终是使该用户再无法访问此文件。如果该索引结点很快又被分配给其它文件，则又会带来潜在的危险。解决的方法是将count值置为正确值。