1、第六章文 件 管 理 第六章文 件 管 理 6.1文件和文件系统文件和文件系统6.2文件的逻辑结构文件的逻辑结构6.3外存分配方式外存分配方式6.4目录管理目录管理6.5文件存储空间的管理文件存储空间的管理6.6文件共享与文件保护文件共享与文件保护6.7数据一致性控制数据一致性控制 第六章文 件 管 理 6.1文件和文件系统文件和文件系统 6.1.16.1.1文件、记录和数据项文件、记录和数据项1 1数据项数据项在文件系统中，数据项是最低级的数据组织形式，可把它分成以下两种类型:(1)基本数据项。这是用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为
2、数据元素或字段。它的命名往往与其属性一致。例如，用于描述一个学生的基本数据项有学号、姓名、年龄、所在班级等。第六章文 件 管 理(2)组合数据项。它是由若干个基本数据项组成的，简称组项。例如，经理便是个组项，它由正经理和副经理两个基本项组成。又如，工资也是个组项，它可由基本工资、工龄工资和奖励工资等基本项所组成。基本数据项除了数据名外，还应有数据类型。因为基本项仅是描述某个对象的属性，根据属性的不同，需要用不同的数据类型来描述。例如，在描述学生的学号时，应使用整数；描述学生的姓名则应使用字符串(含汉字)；描述性别时，可用逻辑变量或汉字。可见，由数据项的名字和类型两者共同定义了一个数据项的“型”
3、。而表征一个实体在数据项上的数据则称为“值”。例如，学号/30211、姓名/王有年、性别/男等。第六章文 件 管 理 2 2记录记录记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把他作为不同的对象。例如，一个学生，当把他作为班上的一名学生时，对他的描述应使用学号、姓名、年龄及所在系班，也可能还包括他所学过的课程的名称、成绩等数据项。但若把学生作为一个医疗对象时，对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项。第六章文 件 管 理 在诸多记录中，为了能惟一
4、地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为关键字(key)。或者说，关键字是惟一能标识一个记录的数据项。通常，只需用一个数据项作为关键字。例如，前面的病历号或学号便可用来从诸多记录中标识出惟一的一个记录。然而有时找不到这样的数据项，只好把几个数据项定为能在诸多记录中惟一地标识出某个记录的关键字。第六章文 件 管 理 3 3文件文件文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成；而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象
5、集。例如，可以将一个班的学生记录作为一个文件。一个文件必须要有一个文件名，它通常是由一串ASCII码或(和)汉字构成的，名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中又规定可用14个字符。用户利用文件名来访问文件。第六章文 件 管 理 此外，文件应具有自己的属性，属性可以包括：(1)文件类型。可以从不同的角度来规定文件的类型，如源文件、目标文件及可执行文件等。(2)文件长度。文件长度指文件的当前长度，长度的单位可以是字节、字或块，也可能是最大允许的长度。(3)文件的物理位置。该项属性通常是用于指示文件在哪一个设备上及在该设备的哪个位置的指针。(4)文件的建立时间。
6、这是指文件最后一次的修改时间等。第六章文 件 管 理 图6-1文件、记录和数据项之间的层次关系 文件记录1记录2记录n数据项1数据项2数据项n第六章文 件 管 理 6.1.26.1.2文件类型和文件系统模型文件类型和文件系统模型1 1文件类型文件类型为了便于管理和控制文件而将文件分成若干种类型。由于不同系统对文件的管理方式不同，因而它们对文件的分类方法也有很大差异。为了方便系统和用户了解文件的类型，在许多OS中都把文件类型作为扩展名而缀在文件名的后面，在文件名和扩展名之间用“.”号隔开。下面是常用的几种文件分类方法。第六章文 件 管 理 1)按用途分类根据文件的性质和用途的不同，可将文件分为三
7、类:(1)系统文件。这是指由系统软件构成的文件。大多数的系统文件只允许用户调用，但不允许用户去读，更不允许修改；有的系统文件不直接对用户开放。(2)用户文件。指由用户的源代码、目标文件、可执行文件或数据等所构成的文件。用户将这些文件委托给系统保管。(3)库文件。这是由标准子例程及常用的例程等所构成的文件。这类文件允许用户调用，但不允许修改。第六章文 件 管 理 2)按文件中数据的形式分类按这种方式分类，也可把文件分为三类：(1)源文件。这是指由源程序和数据构成的文件。通常由终端或输入设备输入的源程序和数据所形成的文件都属于源文件。它通常是由ASCII码或汉字所组成的。(2)目标文件。这是指把源
8、程序经过相应语言的编译程序编译过，但尚未经过链接程序链接的目标代码所构成的文件。它属于二进制文件。通常，目标文件所使用的后缀名是“.obj”。(3)可执行文件。这是指把编译后所产生的目标代码再经过链接程序链接后所形成的文件。第六章文 件 管 理 3)按存取控制属性分类根据系统管理员或用户所规定的存取控制属性，可将文件分为三类：(1)只执行文件。该类文件只允许被核准的用户调用执行，既不允许读，更不允许写。(2)只读文件。该类文件只允许文件主及被核准的用户去读，但不允许写。(3)读写文件。这是指允许文件主和被核准的用户去读或写的文件。第六章文 件 管 理 4)按组织形式和处理方式分类根据文件的组织
9、形式和系统对其的处理方式，可将文件分为三类：(1)普通文件：由ASCII码或二进制码组成的字符文件。一般用户建立的源程序文件、数据文件、目标代码文件及操作系统自身代码文件、库文件、实用程序文件等都是普通文件，它们通常存储在外存储设备上。(2)目录文件：由文件目录组成的，用来管理和实现文件系统功能的系统文件，通过目录文件可以对其它文件的信息进行检索。由于目录文件也是由字符序列构成，因此对其可进行与普通文件一样的种种文件操作。第六章文 件 管 理(3)特殊文件：特指系统中的各类I/O设备。为了便于统一管理，系统将所有的输入/输出设备都视为文件，按文件方式提供给用户使用，如目录的检索、权限的验证等都
10、与普通文件相似，只是对这些文件的操作是和设备驱动程序紧密相连的，系统将这些操作转为对具体设备的操作。根据设备数据交换单位的不同，又可将特殊文件分为块设备文件和字符设备文件。前者用于磁盘、光盘或磁带等块设备的I/O 操作，而后者用于终端、打印机等字符设备的I/O 操作。第六章文 件 管 理 2 2文件系统模型文件系统模型图6-2示出了文件系统的模型。可将该模型分为三个层次，其最底层是对象及其属性；中间层是对对象进行操纵和管理的软件集合；最高层是文件系统提供给用户的接口。第六章文 件 管 理 图6-2文件系统模型 第六章文 件 管 理 1)对象及其属性文件管理系统管理的对象有：文件。它作为文件管理
11、的直接对象。目录。为了方便用户对文件的存取和检索，在文件系统中必须配置目录，每个目录项中，必须含有文件名及该文件所在的物理地址(或指针)。对目录的组织和管理是方便用户和提高对文件存取速度的关键。磁盘(磁带)存储空间。文件和目录必定占用存储空间，对这部分空间的有效管理，不仅能提高外存的利用率，而且能提高对文件的存取速度。第六章文 件 管 理 2)对对象操纵和管理的软件集合这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的，其中包括:对文件存储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制、对文件读和写的管理，以及对文件的共享与保护等功能。第六章文 件 管 理
12、3)文件系统的接口为方便用户使用文件系统，文件系统通常向用户提供两种类型的接口:(1)命令接口。这是指作为用户与文件系统交互的接口。用户可通过键盘终端键入命令，取得文件系统的服务。(2)程序接口。这是指作为用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。第六章文 件 管 理 6.1.36.1.3文件操作文件操作1 1最基本的文件操作最基本的文件操作(1)创建文件。在创建一个新文件时，系统首先要为新文件分配必要的外存空间，并在文件系统的目录中，为之建立一个目录项。目录项中应记录新文件的文件名及其在外存的地址等属性。(2)删除文件。当已不再需要某文件时，可将它从文件系统中删除
13、。在删除时，系统应先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。第六章文 件 管 理(3)读文件。在读一个文件时，须在相应系统调用中给出文件名和应读入的内存目标地址。此时，系统同样要查找目录，找到指定的目录项，从中得到被读文件在外存中的位置。在目录项中，还有一个指针用于对文件的读/写。(4)写文件。在写一个文件时，须在相应系统调用中给出该文件名及该文件在内存中的(源)地址。为此，也同样须先查找目录，找到指定文件的目录项，再利用目录中的写指针进行写操作。第六章文 件 管 理(5)截断文件。如果一个文件的内容已经陈旧而需要全部更新时，一种方法是将此文件删除，再重新
14、创建一个新文件。但如果文件名及其属性均无改变时，则可采取另一种所谓的截断文件的方法，此即将原有文件的长度设置为0，或者说是放弃原有的文件内容。(6)设置文件的读/写位置。前述的文件读/写操作都只提供了对文件顺序存取的手段，即每次都是从文件的始端读或写。设置文件读/写位置的操作，用于设置文件读/写指针的位置，以便每次读/写文件时，不是从其始端而是从所设置的位置开始操作。也正因如此，才能改顺序存取为随机存取。第六章文 件 管 理 2 2文件的文件的“打开打开”和和“关闭关闭”操作操作当前OS所提供的大多数对文件的操作，其过程大致都是这样两步:第一步是通过检索文件目录来找到指定文件的属性及其在外存上
15、的位置；第二步是对文件实施相应的操作，如读文件或写文件等。当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在大多数OS中都引入了“打开”(open)这一文件系统调用，当用户第一次请求对某文件进行操作时，先利用open系统调用将该文件打开。第六章文 件 管 理 所谓“打开”，是指系统将指名文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。以后，当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查
16、找，从而避免了对该文件的再次检索。这样不仅节省了大量的检索开销，也显著地提高了对文件的操作速度。如果用户已不再需要对该文件实施相应的操作时，可利用“关闭”(close)系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉。第六章文 件 管 理 3 3其它文件操作其它文件操作为了方便用户使用文件，通常，OS都提供了数条有关文件操作的系统调用，可将这些调用分成若干类:最常用的一类是有关对文件属性进行操作的，即允许用户直接设置和获得文件的属性，如改变已存文件的文件名、改变文件的拥有者(文件主)、改变对文件的访问权，以及查询文件的状态(包括文件类型、大小和拥有者以及对文件的访问权等)；另
17、一类是有关目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。第六章文 件 管 理 6.2文件的逻辑结构文件的逻辑结构 6.2.16.2.1文件逻辑结构的类型文件逻辑结构的类型1 1有结构文件有结构文件在记录式文件中，每个记录都用于描述实体集中的一个实体，各记录有着相同或不同数目的数据项。记录的长度可分为定长和不定长两类。(1)定长记录。这是指文件中所有记录的长度都是相同的，所有记录中的各数据项都处在记录中相同的位置，具有相同的顺序和长度。文件的长度用记录数目表示。对定长记录的处理方便、开销小，所以这是目前较
18、常用的一种记录格式，被广泛用于数据处理中。第六章文 件 管 理(2)变长记录。这是指文件中各记录的长度不相同。产生变长记录的原因，可能是由于一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等；也可能是数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。不论是哪一种，在处理前，每个记录的长度是可知的。根据用户和系统管理上的需要，可采用多种方式来组织这些记录，形成下述的几种文件：(1)顺序文件。这是由一系列记录按某种顺序排列所形成的文件。其中的记录通常是定长记录，因而能用较快的速度查找文件中的记录。第六章文 件 管 理(2)索引文件。当记录为可变长度时，通
19、常为之建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。(3)索引顺序文件。这是上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。第六章文 件 管 理 2 2无结构文件无结构文件如果说大量的数据结构和数据库是采用有结构的文件形式的话，则大量的源程序、可执行文件、库函数等，所采用的就是无结构的文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读/写指针来指出下一个要访问的字符。可以把流式文件看做是记录式文件的一个特例。在UNIX系统中，所有的文件都被看做是流式文件，即使是有结构文件，也被视为流式文件，系统不对文件进行格式
20、处理。第六章文 件 管 理 6.2.26.2.2顺序文件顺序文件1 1逻辑记录的排序逻辑记录的排序文件是记录的集合。文件中的记录可以是任意顺序的，因此，它可以按照各种不同的顺序进行排列。一般地，可归纳为以下两种情况：第一种是串结构，各记录之间的顺序与关键字无关。通常的办法是由时间来决定，即按存入时间的先后排列，最先存入的记录作为第一个记录，其次存入的为第二个记录，依此类推。第六章文 件 管 理 第二种情况是顺序结构，指文件中的所有记录按关键字(词)排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。对顺序结构文件可有更高的检索效率，因为在检索串结构文件时，每次都必
21、须从头开始，逐个记录地查找，直至找到指定的记录，或查完所有的记录为止。而对顺序结构文件，则可利用某种有效的查找算法，如折半查找法、插值查找法、跳步查找法等方法来提高检索效率。第六章文 件 管 理 2 2对顺序文件对顺序文件(Sequential File)(Sequential File)的读的读/写操作写操作顺序文件中的记录可以是定长的，也可以是变长的。对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。在读一个文件时，可设置一个读指针Rptr，令它指向下一个记录的首地址，每当读完一个记录时，便执行Rptr:=Rptr+L 第六章文 件 管 理 操作，使之指
22、向下一个记录的首地址，其中的L为记录长度。类似地，在写一个文件时，也应设置一个写指针Wptr，使之指向要写的记录的首地址。同样，在每写完一个记录时，又须执行以下操作:Wptr:=Wptr+L对于变长记录的顺序文件，在顺序读或写时的情况相似，但应分别为它们设置读或写指针，在每次读或写完一个记录后，须将读或写指针加上Li。Li是刚读或刚写完的记录的长度。图6-3所示为定长和变长记录文件。第六章文 件 管 理 图6-3定长和变长记录文件 R0R1R2R3RiLLLLLL2L3L4LiL(i1)LRptr(a)定长记录文件L0R0L1R1RiWptr(b)变长记录文件Li00L0L01L1L0L12L
23、i(Lk1)i1k0(Lk1)ik0第六章文 件 管 理 3 3顺序文件的优缺点顺序文件的优缺点顺序文件的最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录时。此时，对顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。第六章文 件 管 理 在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。这时，顺序文件所表现出来的性能就可能很差，尤其是当文件较大时，情况更为严重。例如，有一个含有104个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则平均需要查找5103个记录；如果是可变长记录的顺
24、序文件，则为查找一个记录所需付出的开销将更大，这就限制了顺序文件的长度。第六章文 件 管 理 顺序文件的另一个缺点是，如果想增加或删除一个记录都比较困难。为了解决这一问题，可以为顺序文件配置一个运行记录文件(Log File)，或称为事务文件(Transaction File)，把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，例如4小时，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序的新文件。第六章文 件 管 理 6.2.36.2.3索引文件索引文件对于定长记录文件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i L 然而，对
25、于可变长度记录的文件，要查找其第i个记录时，须首先计算出该记录的首地址。为此，须顺序地查找每个记录，从中获得相应记录的长度Li，然后才能按下式计算出第i个记录的首址。假定在每个记录前用一个字节指明该记录的长度，则 10iiiiiLA第六章文 件 管 理 可见，对于定长记录，除了可以方便地实现顺序存取外，还可较方便地实现直接存取。然而，对于变长记录就较难实现直接存取了，因为用直接存取方法来访问变长记录文件中的一个记录是十分低效的，其检索时间也很难令人接受。为了解决这一问题，可为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中设有一个相应的表项，用于记录该记录的长度L及指向该记录的指针
26、(指向该记录在逻辑地址空间的首址)。由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而也就可以方便地实现直接存取。图6-4示出了索引文件(Index File)的组织形式。第六章文 件 管 理 图6-4索引文件的组织 索引号0长度 m指针 ptrm01m1imi索引表R0R1Ri逻辑文件第六章文 件 管 理 6.2.46.2.4索引顺序文件索引顺序文件索引顺序文件(Index Sequential File)可能是最常见的一种逻辑文件形式。它有效地克服了变长记录文件不便于直接存取的缺点，而且所付出的代价也不算太大。前已述及，它是顺序文件和索引文件相结合的产物。它将顺序文
27、件中的所有记录分为若干个组(例如，50个记录为一个组)；为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的指针。索引顺序文件如图6-5所示。第六章文 件 管 理 图6-5索引顺序文件 键An QiBao RongChen Lin逻辑地址姓 名An QiAn Kang其它属性Bao Rong逻辑文件第六章文 件 管 理 6.2.56.2.5直接文件和哈希文件直接文件和哈希文件1 1直接文件直接文件采用前述几种文件结构对记录进行存取时，都须利用给定的记录键值，先对线性表或链表进行检索，以找到指定记录的物理地址。然而对于直接文件，则可根据给定的
28、记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Key to address transformation)。组织直接文件的关键，在于用什么方法进行从记录值到物理地址的转换。第六章文 件 管 理 2 2哈希哈希(Hash)(Hash)文件文件这是目前应用最为广泛的一种直接文件。它利用Hash函数(或称散列函数)，可将记录键值转换为相应记录的地址。但为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块，如图6-6所示
29、。例如，若令K为记录键值，用A作为通过Hash函数H的转换所形成的该记录在目录表中对应表目的位置，则有关系A=H(K)。通常，把Hash函数作为标准函数存于系统中，供存取文件时调用。第六章文 件 管 理 图6-6Hash文件的逻辑结构 fHash函数目录表键值第六章文 件 管 理 6.3外存分配方式外存分配方式 6.3.16.3.1连续分配连续分配1 1连续分配方式连续分配方式连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2。通常
30、，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。第六章文 件 管 理 在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图6-7 示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count文件的第一个盘块
31、号是0，文件长度为2，因此是在盘块号为0和1的两盘块中存放文件1的数据。第六章文 件 管 理 图6-7磁盘空间的连续分配 1230567491011813141512171819162122232025262724list29303128mailcountfilestart lengthcount 02tr153mail216list293f72目录trf第六章文 件 管 理 如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把
32、所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(repack routine)，由它将磁盘A上的大量文件拷贝到一张软盘B或几张软盘(C，D，)上，并释放原来的A盘，使之成为一个空闲盘。然后再将软盘B(C，D，)上的文件拷回A盘上。这种方法能将含有多个文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。第六章文 件 管 理 2连续分配的主要优缺点连续分配的主要优缺点连续分配的主要优点如下：(1)顺序访问容易。访问一个占有连续空间的文件非常容易。系统可从目录中找到该顺序文件所在的第一个
33、盘块号，从此开始顺序地、逐个盘块地往下读/写。连续分配也支持直接存取。例如，要访问一个从b块开始存放的文件中的第i个盘块的内容，就可直接访问b+i号盘块。(2)顺序访问速度快。因为由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，这时，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。第六章文 件 管 理 连续分配的主要缺点如下：(1)要求有连续的存储空间。要为每一个文件分配一段连续的存储空间，这样，便会产生出许多外部碎片，严重地降低了外存空间的利用率。如果是定期地利用紧凑方法来消除碎片，则又需花费大量的机器时间。第六章文 件 管 理(2)
34、必须事先知道文件的长度。要将一个文件装入一个连续的存储区中，必须事先知道文件的大小，然后根据其大小，在存储空间中找出一块其大小足够的存储区，将文件装入。在有些情况下，知道文件的大小是件非常容易的事，如可拷贝一个已存文件。但有时却很难，在此情况下，只能靠估算。如果估计的文件大小比实际文件小，就可能因存储空间不足而中止文件的拷贝，须再要求用户重新估算，然后再次执行。这样，显然既费时又麻烦。这就促使用户往往将文件长度估得比实际的大，甚至使所计算的文件长度比实际长度大得多，显然，这会严重地浪费外存空间。对于那些动态增长的文件，由于开始时文件很小，在运行中逐渐增大，比如，这种增长要经历几天、几个月。在此
35、情况下，即使事先知道文件的最终大小，在采用预分配存储空间的方法时，显然也将是很低效的，即它使大量的存储空间长期地空闲着。第六章文 件 管 理 6.3.26.3.2链接分配链接分配1 1隐式链接隐式链接在采用隐式链接分配方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。图6-8 中示出了一个占用5个盘块的链接式文件。在相应的目录项中，指示了其第一个盘块号是9，最后一个盘块号是25。而在每个盘块中都含有一个指向下一个盘块的指针，如在第一个盘块9中设置了第二个盘块的盘块号是16；在16号盘块中又设置了第三个盘块的盘块号1。如果指针占用4个字节，对于盘块大小为512
36、字节的磁盘，则每个盘块中只有508个字节可供用户使用。第六章文 件 管 理 图6-8磁盘空间的链接式分配 25123056749101181314151217181916212223202526272429303128filestartendjeep925目录101-116第六章文 件 管 理 隐式链接分配方式的主要问题在于：它只适合于顺序访问，它对随机访问是极其低效的。如果要访问文件所在的第i个盘块，则必须先读出文件的第一个盘块，就这样顺序地查找直至第i块。当i=100时，须启动100次磁盘去实现读盘块的操作，平均每次都要花费几十毫秒。可见，随机访问的速度相当低。此外，只通过链接指针来将一大
37、批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。第六章文 件 管 理 2 2显式链接显式链接这是指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，如图6-9所示。表的序号是物理盘块号，从0开始，直至N-1；N为盘块总数。在每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某一文件的第一个盘块号，或者说是每一条链的链首指针所对应的盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。由于分配给文件
38、的所有盘块号都放在该表中，故把该表称为文件分配表FAT(File Allocation Table)。第六章文 件 管 理 图6-9显式链接结构 012345物理块号2FCBFAT0451第六章文 件 管 理 6.3.3 FAT6.3.3 FAT和和NTFSNTFS技术技术1 1FAT12FAT121)以盘块为基本分配单位 早期MS-DOS操作系统所使用的是FAT12文件系统，在每个分区中都配有两张文件分配表FAT1和FAT2，在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。第六章文
39、件 管 理 图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-10MS-DOS的文件物理结构 6EOF11105EOF0123456789FATFCB A4FCB B9第六章文 件 管 理 现在我们来计
40、算以盘块为分配单位时，所允许的最大磁盘容量。由于每个FAT表项为12位，因此，在FAT表中最多允许有4096个表项，如果采用以盘块作为基本分配单位，每个盘块(也称扇区)的大小一般是512字节，那么，每个磁盘分区的容量为2 MB(4096512 B)。同时，一个物理磁盘支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8 MB。这对最早时期的硬盘还可应付，但很快磁盘的容量就超过了8 MB，FAT12是否还可继续用呢，回答虽是肯定的，但需要引入一个新的分配单位簇。第六章文 件 管 理 2)簇的基本概念为了适应磁盘容量不断增大的需要，在进行盘块分配时，不再以盘块而是以簇(cluster)为基本单位。簇
41、是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n(n为整数)个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区(1 KB)、四个扇区(2 KB)、八个扇区(4 KB)等。一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为8 MB；当一个簇包含两个扇区时，磁盘的最大容量可以达到16 MB；当一个簇包含了八个扇区时，磁盘的最大容量便可达到64 MB。第六章文 件 管 理 由上所述可以看出，以簇作为基本的分配单位所带来的最主要的好处是，能适应磁盘容量不断增大的情况。值得注意的是，使用簇作为基本的分配单位
42、虽可减少FAT表中的项数(在相同的磁盘容量下，FAT表的项数是与簇的大小成反比的)。这一方面会使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。第六章文 件 管 理 3)FAT12存在的问题尽管FAT12曾是一个不错的文件系统，但毕竟已老化，已不能满足操作系统发展的需要，其表现出来的主要问题是，对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只能支持8+3格式的文件名。第
43、六章文 件 管 理 2 2FAT16FAT16对FAT12所存在的问题进行简单的分析即可看出，其根本原因在于，FAT12表最多只允许4096个表项，亦即最多只能将一个磁盘分区分为4096个簇。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。由此可以得出解决方法，那就是增加FAT表的表项数，亦即应增加FAT表的宽度，如果我们将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65 536(216)个簇。我们把具有16位表宽的FAT表称为FAT16。在FAT16的每个簇中可以有的盘块数为4、8、16、32直到64，由此得出FAT16可以管理的最大分
44、区空间为216 64 512=2048 MB。第六章文 件 管 理 由上述分析不难看出，FAT16对FAT12的局限性有所改善，但改善很有限。当磁盘容量迅速增加时，如果再继续使用FAT16，由此所形成的簇内碎片所造成的浪费也越大。例如，当要求磁盘分区的大小为8 GB时，则每个簇的大小达到128 KB，这意味着内部零头最大可达到128 KB。一般而言，对于14 GB的硬盘来说，大约会浪费1020的空间。为了解决这一问题，微软推出了FAT32。第六章文 件 管 理 3 3FAT32FAT32如同存储器管理中的分页管理，所选择的页面越大，可能造成的页内零头也会越大。为减少页内零头就应该选择适当大小的
45、页面。在这里，为了减小磁盘的簇内零头，也就应当选择适当大小的簇。问题是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个盘块，每个盘块仍
46、为512字节，FAT32分区格式可以管理的单个最大磁盘空间大到4 KB232=2 TB。三种FAT类型的最大分区以及所对应的块的大小如图6-11所示。第六章文 件 管 理 图6-11 FAT中簇的大小与最大分区的对应关系 块大小/KB FAT12/MB FAT16/MB FAT32/TB 0.5 2 1 4 2 8 128 4 16 256 1 8 512 2 16 1024 2 32 2048 2 第六章文 件 管 理 4 4NTFSNTFS1)NTFS新特征NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Win
47、dows 2000/XP/2003。NTFS具有许多新的特征：首先，它使用了64位磁盘地址，理论上可以支持2的64次方字节的磁盘分区；其次，在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32 767个字符；第三，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行，这一点我们将在6.6节中介绍；第四，提供了数据的一致性，这是一个非常有用的功能，我们将在本章的最后一节介绍；此外，NTFS还提供了文件加密、文件压缩等功能。第六章文 件 管 理 2)磁盘组织同FAT文件系统一样，NTFS也是以簇作为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个
48、簇只属于一个文件。通过簇来间接管理磁盘，可以不需要知道盘块(扇区)的大小，使NTFS具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是512字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。第六章文 件 管 理 在NTFS文件系统中，把卷上簇的大小称为“卷因子”，卷因子是在磁盘格式化时确定的，其大小同FAT一样，也是物理磁盘扇区的整数倍，即一个簇包含2n(n为整数)个盘块，簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为512 B、1 KB、2 KB，最大可达64 KB。对于小磁盘(512 MB)，默认簇大小为512字节；对于1 GB磁盘，默认簇大小为1
49、KB；对于2 GB磁盘，则默认簇大小为4 KB。事实上，为了在传输效率和簇内碎片之间进行折中，NTFS在大多数情况下都是使用4 KB。第六章文 件 管 理 对于簇的定位，NTFS是采用逻辑簇号LCN(Logical Cluster Number)和虚拟簇号VCN(Virtual Cluster Number)进行的。LCN是以卷为单位，将整个卷中所有的簇按顺序进行简单的编号，NTFS在进行地址映射时，可以通过卷因子与LCN的乘积，便可算出卷上的物理字节偏移量，从而得到文件数据所在的物理磁盘地址。为了方便文件中数据的引用，NTFS还可以使用VCN，以文件为单位，将属于某个文件的簇按顺序进行编号。
50、只要知道了文件开始的簇地址，便可将VCN映射到LCN。第六章文 件 管 理 3)文件的组织在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中。该表是NTFS 卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT 表中占有一行，其中还包括MFT 自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。第六章文 件 管 理 在MFT表中，每个元数据将其所对应文件的所有信息，包括文件的内容等，都被组织在所对应文件的一组属
