操作系统原理电子教案.ppt

《操作系统原理电子教案.ppt》由会员分享，可在线阅读，更多相关《操作系统原理电子教案.ppt（85页珍藏版）》请在三一办公上搜索。

1、第6章 文 件 管 理,6.1 文件的概念6.2 文件目录6.3 文件和目录操作6.4 文件的逻辑结构6.5 文件的物理结构6.6 文件存储空间的分配6.7 文件存储空间的管理6.8 文件系统6.9 文件的共享和保护,6.1 文件的概念,文件系统的管理功能，就是通过把计算机保存的程序和数据组织成一系列文件的方法来实现的。文件是计算机系统中信息存放的一种组织形式。在现代操作系统中，几乎都是通过文件系统来组织和管理计算机保存的大量程序和数据。,6.1.1 文件及其分类,1.文件的定义 文件是计算机系统中信息存放的一种组织形式，是在逻辑上具有完整意义的信息集合，并且有一个名字以供标识。构成文件的基本

2、单位可以是字符流，也可以是记录。据此，文件有两种有代表性定义：(1)文件是具有标识符的相关字符流的集合。说明文件是由字节组成，这是一种无结构的文件，称为流式文件，目前UNIX操作系统，MS-DOS系统均采用这种文件形式。无结构的文件由于采用字符流方式，与源程序、目标代码等在形式上是一致的，因此，该方式适用于源程序、目标代码等文件。(2)文件是具有标识符的相关记录(一个有意义的信息单位)的集合。文件是由记录组成，这是一种有结构的文件。记录是由一组相关信息项组成。例如每个学生的档案表可以视为一个记录，它包括学生姓名、出生年月、性别、籍贯等信息项，所有学生档案表组成一个学生文件。记录式文件主要用于信

3、息管理。,6.1.1 文件及其分类,2.文件的命名 文件名由创建者给定，它是由字母或数字组成的一个字符串，用来标识该文件。不同的系统对文件命名有不同的要求。例如，有些系统规定必须是字母打头且允许一些其它符号出现在文件名的非打头部分；有些系统区分文件名中的大小写字母，如UNIX和Linux系统；而有些系统则不去区分文件名中的大小写，如MS-DOS。名字的长度因系统不同而异。如在有的系统中把名字规定为8个字符，而在有的系统中规定可用14个字符。,6.1.1 文件及其分类,2.文件的命名文件名由文件名和扩展名两部分组成，中间用“.”隔开，如program.c。它们都是由字母或数字组成的字母数字串。扩

4、展名也称文件后缀，利用扩展名可以区分文件的属性。,6.1.1 文件及其分类,3.文件的分类(1)按文件的用途分类系统文件：指由操作系统及其它系统程序和数据组成的文件。这种文件不对用户开放，仅供系统使用，用户只能通过操作系统提供的系统调用来使用它们，用户没有读权限和修改权限。库文件：指系统为用户提供的各种标准函数、标准过程和实用程序等。用户只能使用这些文件，而不允许对其进行修改。用户文件：指由用户的源代码、目标文件、可执行文件或数据等所构成的文件。这种文件的使用和修改权均属于用户。,6.1.1 文件及其分类,3.文件的分类(2)按文件的操作权限分类只读文件：只允许进行读操作，不能进行写操作的文件

5、。读写文件：允许文件属主和授权用户对其进行读或写操作的文件。只执行文件：该类文件只允许授权的用户调用执行，而不允许其修改或读出文件的内容。,6.1.1 文件及其分类,3.文件的分类(3)按文件的性质分类 普通文件：指一般的用户文件和系统文件，譬如一般用户建立的源程序文件、数据文件、目标代码文件及操作系统自身代码文件、库文件、实用程序文件等都是普通文件。普通文件通常分为ASCII文件和二进制文件，一般存放在外存储设备上。目录文件：由文件目录项组成，用来管理和实现文件系统功能的系统文件，通过目录文件可以对其它文件的信息进行检索。对目录文件可以进行与普通文件一样的各种文件操作。特殊文件：指系统中的各

6、类I/O设备。为了方便统一管理，系统将所有的I/O设备都视为文件，以文件方式提供给用户使用。根据设备数据交换单位的不同，又可将特殊文件分为块设备文件和字符设备文件。前者用于磁盘、光盘等块设备的I/O操作，而后者用于终端、打印机等字符设备的I/O操作。,6.1.1 文件及其分类,3.文件的分类(4)按文件中数据的形式分类 源文件。指由源程序和数据构成的文件。通常由终端或输入设备输入的源程序和数据所形成的文件都属于源文件。它通常由ASCII码或汉字组成。目标文件。指把源程序经过相应语言的编译程序编译过，但尚未经过链接程序链接的目标代码所构成的文件。它属于二进制文件。通常，目标文件使用的后缀名是“.

7、obj”。可执行文件。指把编译后产生的目标代码再经过链接程序链接后所形成的文件。,6.1.2 文件的属性,为了对文件进行控制和管理，大多数操作系统都用一组信息来指定文件的类型、操作特性和存取保护等，这组信息称为文件的属性。文件的基本属性：文件的名称、文件的所有者、文件的授权者、文件的长度等。文件的类型属性：如普通文件、目录文件、系统文件、隐含文件、设备文件等。也可以按文件信息分为ASCII码文件、二进制码文件等。文件的保护属性：如可读、可写、可执行、可更新、可删除等，可改变保护以及档案属性。文件的管理属性：如文件的建立时间、最后存取时间、最后修改时间等。文件的控制属性：逻辑记录长、文件的大小、

8、文件的最大长度以及允许的存取方式标志、关键字的位置、关键字长度等。所有文件的信息都保存在目录结构中，而目录结构保存在外存中。通常，目录条目包括文件名称及其唯一标识符，而这些标识符又定位其它属性信息。一个文件的属性信息大概需要1KB。,6.2 文件目录,文件目录是一种数据结构，用来标识文件系统中的文件及其物理地址，供检索时使用。对文件目录管理的功能要求如下：(1)实现按名存取。(2)提高对目录的检索速度。(3)文件共享。(4)允许文件重名。,6.2.1 文件控制块和文件目录,一个文件包括两部分：文件说明和文件体。文件体是指文件本身的信息，它可以是记录式文件或字符流文件。文件说明也叫文件控制块(f

9、ile control block，FCB)，它是操作系统为管理文件而设置的数据结构，存放管理文件所需的所有有关信息(文件属性)，文件控制块是文件存在的标志。,6.2.1 文件控制块和文件目录,1.文件控制块 文件控制块通常包含三类信息:(1)基本信息文件名：用于标识一个文件的符号名。在每个系统中，每个文件都必须有唯一的名字，用户利用该名字进行访问。文件类型：指明文件属性是普通文件，还是目录文件或特殊文件，是系统文件还是用户文件等。文件物理位置：指文件在外存上的存储位置，如存放文件的设备名、文件在外存的起始盘块号、文件占用的盘块数或字节数。文件大小：当前文件的大小(以字节、字或块为单位)和允许

10、的最大长度。(2)存取控制信息 存取控制信息包括：文件属主的存取权限、标准用户的存取权限以及一般用户的存取权限。(3)使用信息时间和日期：反映文件创建和最后修改的日期和时间。最后使用情况：包括文件是否被其它进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上等。这些信息可用于对文件实施保护和监控等。使用计数：表示当前有多少个进程正在使用或打开该文件。,6.2.1 文件控制块和文件目录,2.文件目录文件与文件控制块一一对应，文件控制块的有序集合称为文件目录，一个文件控制块就是一个文件目录项。为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存上，这个文件就叫目录文件。MS-DOS目录项示

11、意图:,6.2.1 文件控制块和文件目录,3.索引节点为了减少检索文件的时间，在有的系统中，如UNIX/Linux系统，采用把文件名和文件描述信息分开的方法，使文件描述信息单独形成一个定长的数据结构，称为索引节点，简称为i结点。这样，在文件目录中的每个目录项仅由文件名和指向该文件对应的i结点的指针所构成。在UNIX系统中一个目录仅占16个字节，其中14个字节是文件名，2个字节为i结点指针。在1KB的盘块中可保存64个目录项，这样，为找到一个文件，可使平均启动磁盘次数减少到原来的1/4，大大节省了系统开销。Unix系统的文件目录项示意图如下。,6.2.2 文件目录结构,1.单级目录 在整个文件系

12、统中只建立一张目录表，每个文件占一个目录项，目录项中包含文件名、文件扩展名、文件类型、文件长度、文件物理地址以及其它文件属性。,6.2.2 文件目录结构,1.单级目录单级目录的优点是简单、易于实现，实现了目录管理的基本功能按名存取，但却存在以下一些缺点：(1)查找速度慢。(2)不允许重名。(3)不便于文件的共享。,6.2.2 文件目录结构,2.两级目录为每一个用户建立一个单独的用户文件目录UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块组成。系统再建立一个主文件目录MFD(Master File Directory)，在主文件目录中，每

13、个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针。,6.2.2 文件目录结构,2.两级目录两级目录结构基本克服了单级目录的缺点，具有以下优点：(1)解决文件名冲突。(2)提高目录检索速度。(3)不同用户可使用不同的文件名来访问系统中的同一个共享文件。两级目录仍然存在一些问题。这种结构有效地对用户加以隔离，这种隔离在各用户之间完全无关时是优点，但是当用户需要在某个任务上进行合作，且一用户又需要访问其它用户的文件时，这种隔离就是个缺点，因为有的系统不允许本地用户文件被其它用户访问。,6.2.2 文件目录结构,3.多级目录 多级目录结构是一棵倒向的有根树，树根是根目录；

14、从根向下，每一个树枝是一个子目录，而树叶则是文件。树形目录有许多优点：它较好地反映了现实世界中具有层次关系的数据集合和较确切地反映系统内部文件的分支结构，不同的文件可以重名，只要它们不位于同一子目录中即可，易于规定不同层次或子树中文件的不同存取权限，便于文件的保护、保密和共享等。,6.2.2 文件目录结构,在树形目录结构中，文件的全名包括从根目录开始到文件为止的所有子目录路径。各个子目录名之间用正斜线“/”或反斜线“”隔开。子目录名组成的部分又称为路径名。系统内的每个文件都有唯一的路径名，路径名是从根经过所有子目录再到指定文件的路径。绝对路径名从根目录开始并给出路径上的目录名直到指定的文件。相

15、对路径名则从当前目录开始定义一个路径。,6.2.3 目录的实现,1.线性列表目录文件是由目录项构成的一个线性表，每个目录项包括文件名和指向数据块的指针。当需要创建一个新文件时，系统必须首先搜索目录文件以确定有没有同名的文件存在，然后把新文件的目录项添加到目录末尾。当删除一个文件时，系统根据给定的文件名来搜索文件目录。找到该文件所在目录项后，释放分配给该文件的磁盘空间，并将相应的目录项删除。,6.2.3 目录的实现,2.哈希表哈希表是实现文件目录的另一种数据结构。采用这种方法时，除了使用线性列表来存放目录项以外，还使用了哈希表。哈希表将根据文件名计算出一个哈希值，并返回一个指向线性列表中元素的指

16、针。因此，它大大降低了目录搜索时间，插入和删除也很方便，不过需要一些措施来避免冲突(两个不同的文件名具有相同的哈希值)。哈希表的最大困难在于其大小通常是固定的，而且哈希函数也依赖于哈希表的大小。,6.3 文件和目录操作,6.3.1 文件操作 用户通过文件系统提供的系统调用对文件进行操作。1.基本的文件操作(1)创建文件。(2)删除文件。(3)读文件。(4)写文件。(5)文件定位。(6)截短文件。,6.3.1 文件操作,2.文件的“打开”和“关闭”操作为了避免多次重复地检索目录，大多数操作系统都引入“打开(open)”这一文件系统调用，当用户第一次请求对某文件进行操作时，先利用open系统调用显

17、式地将该文件打开。操作系统维护一个包含所有打开文件的信息表(打开文件表，open file table)。当需要进行一个文件操作时，可以通过打开文件表的一个索引来指定文件，而不需要搜索整个文件目录。当文件不再使用时，进程可以关闭它，操作系统随即从打开文件表中删除这一条目。,6.3.2 目录操作,1.创建目录创建的新目录除了目录项“.”(表示该目录本身)和“.”(表示父目录)以外，其内容为空。2.删除目录 删除目录时，系统首先进行目录检索，在父目录中找到该目录的目录项，然后验证用户的操作权限，如果具有删除权限，就执行相应的删除操作。在删除目录时，不同的系统有不同的限制。有的系统限制只能删除空目录

18、，因此，当被删除目录下有子目录或文件时，将不能删除目录，如MS-DOS就是采用这种目录删除方式。而另外有些系统则不管目录是否为空都可以执行删除操作，如果目录非空，系统会自动将它下面的文件或子目录一并删除。3.检索目录 检索目录是根据用户给定的文件路径名，从高层到底层顺序地查找各级文件目录，寻找指定文件的相关信息。,6.4 文件的逻辑结构,对于文件组织形式的研究有两种不同的观点，即用户观点和实现观点。用户观点的目的是研究用户“思维”中的抽象文件，也称逻辑文件。研究的侧重点是为用户提供一种逻辑结构清晰、使用简便的逻辑文件形式。用户按照这种形式去存储和访问有关文件中的信息。实现观点的目的是研究保存在

19、设备介质中的实际文件，也称物理文件。研究的侧重点是如何选择工作性能良好、设备利用率高的物理文件形式。,6.4 文件的逻辑结构,对应于用户观点的逻辑文件和实现观点的物理文件，任何一个文件都存在两种形式的结构：逻辑结构和物理结构。(1)文件的逻辑结构。这是从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及结构，它独立于文件的物理特性。(2)文件的物理结构。又称为文件的存储结构，是指文件在外存上的存储组织形式。这不仅与存储介质的存储性能有关，而且与所采用的外存分配方式有关。操作系统对文件逻辑结构提出的基本要求包含以下三个方面：高检索速度。在将大批记录组成文件时，应有利于提高检索记录的速

20、度和效率。便于修改。要便于在文件中增加、删除和修改一个或多个记录。低存储费用。减少文件占用的存储空间，不要求大片的连续存储空间。,6.4.1 文件逻辑结构的类型,文件的逻辑结构可分为两大类：有结构文件和无结构文件。1.有结构文件有结构文件又称记录式文件，它在逻辑上可以看成是一组连续记录的集合，即文件由若干条相关记录组成，且对每个记录编上号码，依次为记录1、记录2、记录n。每个记录是一组相关的数据集合，用于描述一个对象的某个方面的属性，如年龄、姓名、职务、工资等。通常数据结构和数据库都是采用有结构的文件形式。,6.4.1 文件逻辑结构的类型,有结构文件按照记录长度是否相同，又可分为定长记录文件和

21、不定长记录文件两种。(1)定长记录：定长记录文件中所有记录的长度相等。定长记录处理方便，开销小，被广泛用于数据处理中。(2)变长记录文件：变长记录文件中的记录长度不相等。产生变长记录的原因，可能是由于一个记录中所包含的数据项数目并不相同，如书的著作者、论文中的关键词等；也可能是数据项本身的长度不定，例如，病历记录中的病因、病史；科技情报记录中的摘要等。,6.4.1 文件逻辑结构的类型,为了方便用户使用和系统管理，可采用多种方式来组织这些记录，形成以下几种文件：(1)顺序文件。由一系列记录按某种顺序排列形成的文件。其中的记录通常是定长记录，能用较快的速度查找文件中的记录。(2)索引文件。主要针对

22、变长记录的文件，为之建立一张索引表，每个记录占用一个表项，以加快对记录检索的速度。(3)索引顺序文件。这是上述两种文件构成方式的组合。,6.4.1 文件逻辑结构的类型,2.无结构的文件 无结构文件是由一组相关信息组成的有序字符流，即流式文件。大量的源程序、可执行程序、库函数等均采用无结构的文件形式。Windows系统中，所有的文件都被看成是流式文件，即使是有结构文件，也被视为流式文件，系统不对文件进行格式处理。把文件看作字节流，为操作系统带来了很大的灵活性。用户可以根据需要在自己的文件中加入任何内容，而不用操作系统提供任何额外帮助。由于记录式文件的使用很不方便，尤其是变长记录文件，另外在文件中

23、还要有说明记录长度的信息，这就浪费了一部分存储空间。因此许多现代计算机操作系统，如UNIX操作系统等都取消了记录式文件。,6.4.2 顺序文件,1.文件记录的排序 顺序文件是一系列记录按某种顺序排列形成的文件。通常可归纳为以下两种情况：(1)时间顺序结构。各记录之间的顺序与关键字无关。记录按存入时间的先后顺序排列。(2)关键字顺序结构。各记录按关键字(词)排列。可以按关键字(词)的长短从小到大或从大到小排列，或按其英文字母顺序排序。对时间顺序结构文件，在每次检索文件时，每次都必须从头开始，逐个记录查找，直至找到指定的记录，或查完所有的记录为止。对关键字顺序结构文件，可采用一些有效的查找算法，如

24、折半查找法、插值查找法、跳步查找法等来提高检索效率。,6.4.2 顺序文件,2.顺序文件的读/写操作对于定长记录的顺序文件，如果已知当前记录的逻辑地址，可很容易确定下一个记录的逻辑地址。在读/写一个文件时，可设置一个读/写指针Rptr/Wptr，令它指向下一个记录的首地址，每当读/写完一个记录时，便执行下式 Rptr/Wptr:=Rptr/Wptr+L 使之指向下一个记录的首地址，其中的L为记录长度。对于变长记录的顺序文件，在顺序读/写时与定长记录顺序文件相似，不同的是在每次读/写完一个记录后，须将读/写指针加上Li，Li是刚读/写完的记录的长度。,6.4.2 顺序文件,3.顺序文件的优缺点

25、当对记录文件进行批量存取操作时，即每次要读写一大批记录时，此时，对顺序文件的存取效率是所有逻辑文件中最高的。在交互应用场合，用户(程序)需要查找或修改单个记录，为此系统需要逐个查找诸记录。这时，顺序文件表现出来的性能就可能很差，当文件较大时，情况更为严重。例如，一个含有104个记录的顺序文件，如果对它采用顺序查找去查找一个指定的记录，则平均需要查找5103个记录。如果是可变长记录的顺序文件，则为查找一个记录所需付出的开销将更大。顺序文件的另一个缺点是，增加或删除一个记录比较困难。,6.4.3 索引文件,在变长记录文件中引入索引表，即为变长记录文件建立一张索引表，对主文件中的每个记录，在索引表中

26、建立一个对应的表项，记录该文件记录的长度L及指向该记录的指针(该记录在逻辑地址空间的首址)。由于索引表是按记录键排序的，因此，索引表本身是一个定长记录的顺序文件，从而可以方便地实现直接存取。在对索引文件进行检索时，首先根据用户(程序)提供的关键字，并利用折半查找法去检索索引表，从中找到对应的表项，再利用该表项中给出的指向记录的指针值，去访问所需的记录。,6.4.4 索引顺序文件,索引顺序文件是顺序文件和索引文件相结合的产物，是最常见的一种逻辑文件形式。它将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项，其中含有该记录的键值和指向该记录的

27、指针。在对索引顺序文件进行检索时，首先利用用户(程序)提供的关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置；然后，再利用顺序查找法去查找主文件，从中找到所要访问的记录。如果在一个顺序文件中包含的记录数为N，则为检索到具有指定关键字的记录，平均须查找N/2个记录；但对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只要查找个记录数。,6.5 文件的物理结构,文件的物理结构指文件在外存上的存储组织形式，表示一个文件在外存上的安置、链接和编目的方法。它和文件的逻辑结构以及外存设备的特性等都有密切的关系。因此，在确定一个文件

28、的物理结构时，必须考虑文件的大小、记录是否定长、访问的频繁程度和存取方法等。磁盘的结构允许文件管理系统按三种不同的方式组织文件：连续文件、链接文件、随机文件。,6.5.1 连续文件,连续文件结构是由一组分配在磁盘连续区域的物理块组成的。文件中的每一个记录有一个序号，序号为i+1的记录，其物理位置一定紧跟在i号记录之后。,连续文件结构的优点有：(1)存取简单。若给定记录号为r，记录长度为l，物理块大小为size，则相对块号计算为：(2)存取速度较快。如果文件中第n个记录刚被存取过，而下一个要存取的是第n+1个记录，则这个存取操作会很快完成。,6.5.1 连续文件,连续文件结构的缺点是：如果是直接

29、存取设备(或称多路存储设备，如磁盘)，在多道程序情况下，由于其他用户可能驱使磁头移向其它柱面，因而就会降低连续文件的优越性。连续文件结构对于变化少、可以作为一个整体处理的大量数据段较为方便，而对那些变化频繁的少量记录不宜采用。对于连续文件结构来说，其文件长度一经固定便不易改变，因而不利于文件的增长和扩充。,6.5.2 链接文件,链接文件结构是按顺序由串联的块组成的，即文件的信息按存储介质的物理特性存于若干块中，一块中可包含一个逻辑记录或多个逻辑记录，或者一个逻辑记录占有多个物理块。每个物理块的最末一个字(或第一个字)作为链接字，它指向后继块的物理地址。文件的最后一块的链接字为结束标记(例如“”

30、)，它表示文件至本块结束。,6.5.2 链接文件,链接文件采用的是一种非连续的存储结构，文件的逻辑记录可以存放到不连续的物理块中，能较好地利用外存空间。另外，还易于对文件进行扩充，即只要修改链接字就可以将记录插入到文件中间或从文件中删除若干记录。对于链接文件而言，为了找到一个记录，文件必须从文件头开始一块一块查找，直到所需的记录被找到。链接文件可以是单链结构，也可以是双链结构。在双链结构中，在每个相应的物理块中增加一个后向指针，令它指向上一个记录所在的物理块，链接文件能反向顺序存取。链接文件虽比较易于修改，但由于存放链指针，所以需要消耗一定的存储空间。链接文件只适用于顺序存取方式，不适用于直接

31、存取方式。,6.5.3 随机文件,随机文件结构是实现非连续分配的另一种方式。在随机文件结构中，文件的数据记录存放在直接存取型存储设备上，数据记录的关键字和其地址之间建立某种对应关系，并利用这种关系进行存取。通常有三种形式的随机文件结构：直接地址结构、索引结构和散列结构。1.直接地址结构 如果知道某个记录的地址时，可直接使用这个地址进行存取。这就意味着，用户必须知道每个记录的具体地址，这是很不方便的。因此，直接地址结构并不常用。当然直接地址结构的存取效率最高，因为不需要进行任何“查找”。,6.5.3 随机文件,2.索引结构 索引结构将逻辑文件顺序地划分成长度与物理存储块长度相同的逻辑块，然后为每

32、个文件分别建立逻辑块号与物理块号的映射表。这张表称为该文件的索引表。用这种方法构造的文件称为索引文件。索引文件的索引项按文件逻辑块号顺序排列。,6.5.3 随机文件,索引文件在存储区中占两个区：索引区和数据区。索引区存放索引表。数据区存放数据文件本身。访问索引文件需要两步操作。第一步是查文件索引，由逻辑块号查得物理块号；第二步是由此物理块号获得所要求的信息。因此，需要两次访问文件存储器。如果文件索引表已经预先调入主存，则只需访问一次。索引文件的优点是可以直接访问任意记录，而且便于文件的增删。当增加或删除记录时，需要对索引表及时加以修改。由于每次存取都涉及到索引表的查找，因此，所采用的查找策略对

33、文件系统的效率有很大的影响。通常采用的查找策略有两种：二分查找和顺序查找。,6.5.3 随机文件,3.散列结构 在散列结构中，文件中记录的关键字经过散列计算处理，转换成相应的物理块地址，并进行访问，利用这种散列关系实现记录存取的文件叫做散列文件。由于通常地址的总数比可能的关键字的值的总数要小得多，即不会是一对一的关系，因此不同的关键字在散列计算之后，可能会得出相同的地址，称为“冲突”。一种散列算法是否成功的一个重要标志，是看其将不同的关键字映射到同一地址的几率有多大，如果几率越小，则该散列算法的性能就越好。即“冲突”产生的几率越小越好。散列算法的基本思想是根据关键字来计算相应记录的地址，所以必

34、须解决好如下两个问题：(1)寻找一个散列函数h(k)实现关键字到地址的转换。(2)确定解决冲突的方法。,6.5.4 文件物理结构比较,连续文件的优点是不需要额外的空间开销，只要在目录中指出起始块号和文件长度，就可以对文件进行访问，且一次可以读出整个文件。对于固定不变且要长期使用的文件(比如系统文件)，这是一种较为节省的方法。其缺点是：(1)不能动态增长。因为在它后面如果已经记录了别的文件，则这一文件增长就可能破坏后边的文件。如果后移下一个文件，则系统开销太大，甚至不可能。(2)一开始就提出文件长度要求，而要用户预先知道文件长度不是太容易。(3)一次要求比较大的连续存储空间，不一定好找。因为，如

35、果外存上只有许多小的自由空间，虽然其总容量大于文件的要求，但由于不连续，因而这些空间可能被浪费。链接文件可以克服连续文件的上述缺点，然而它也存在如下缺点：(1)由于在处理文件的一部分时必须得顺序访问，因而访问速度较慢，时间上比较浪费。(2)对块链接而言，每个块中都要有链接字。所以，要占用一定的存储空间。相比之下，随机文件是一种比较好的结构，便于直接存取。但问题是，对于索引文件应考虑如何有效地存储和访问索引表，对于散列文件应寻找一个较好的散列算法和确定解决冲突的办法。,6.6 文件存储空间的分配,磁盘具有随机访问的特性，因此利用磁盘来存放文件时，具有很大的灵活性。在为文件分配外存空间时需要考虑的

36、主要问题是：如何才能有效地提高外存空间利用率和加快文件访问速度？目前常用的外存分配方法有连续分配、链接分配和索引分配3种，每种方法都有其优缺点。有的系统对3种方法都支持，但通常在一个系统中，仅采用其中的一种方法来为文件分配外存空间。文件的物理结构与外存分配方式有紧密关系。在采用不同的分配方式时，将形成不同的文件物理结构。例如：在采用连续分配方式时的文件物理结构，将是连续式的文件结构；链接分配方式将形成链接式文件结构；而索引分配方式则形成索引式文件结构。,6.6.1 连续分配,连续分配方法要求每个文件在磁盘上占用一组连续的块。文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。连续分配的主

37、要问题就是从一个空闲块列表中寻找一个满足请求要求的连续空闲区域。最常用的策略就是首次适应法和最佳适应法。,6.6.1 连续分配,连续分配的主要优点如下：(1)顺序访问速度快。(2)顺序访问容易。连续分配的主要缺点如下：(1)要求连续的存储空间。(2)要求事先知道文件的长度。(3)不便于文件的动态扩充。,6.6.2 链接分配,连续分配存在的问题在于：必须为一个文件分配连续的磁盘空间。如果将一个逻辑文件分散装到多个离散的物理盘块中，而不是为整个文件寻找一块连续的空间，即可消除连续分配的缺点。采用链接分配时，一个文件被离散地分配到多个非连续的物理盘块上，这些非连续的物理块分布在磁盘的任何地方，它们之

38、间并没有顺序关系，其中每个物理块都设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。采用链接分配形成的物理文件称为链接文件或串联文件。链接分配的优点：采用离散分配方式，消除了外部碎片，提高了外存空间的利用率；根据文件的当前需要，为其分配必需的盘块，当文件动态增长时，可动态地再为它分配盘块，因此无需提前知道文件的大小。对文件的增、删、改十分方便。链接方式可分为隐式链接和显式链接两种形式。,6.6.2 链接分配,1.隐式链接在隐式链接分配方式下，在文件目录的每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针。,6.6.2 链接分配,隐式链接分配

39、方式的主要问题在于：首先，它只适合顺序访问，不适宜随机访问。另外，隐式链接分配的可靠性差，由于文件物理块是通过指针链接的，而指针是分布在整个磁盘上，操作系统软件的bug或磁盘硬件的故障可能会导致程序获得一个错误指针。最后，指针也需要空间。对隐式链接分配存在问题的解决方法是将多个块组成簇(cluster)，并按簇而不是按块进行分配。例如，文件系统可能定义一个簇为4块，并以簇为单位来操作。这样，指针占用的磁盘空间就会更少，也会成倍地减小查找指定块的时间。但这种方法增加了内部碎片。,6.6.2 链接分配,2.显式链接 使用文件分配表(File Allocation Table，FAT)。每个磁盘分区

40、的开始部分用于存储FAT表。磁盘上的每个块都在该表中登记，并占用一个表项，FAT表可以通过块的编号来索引，FAT的每个表项含有文件的下一块的块号，这样FAT就可以像链表一样使用。系统首先根据目录文件中的第一块的块号去检索FAT表，从中得到文件的下一个盘块号，以此类推，直到该文件的最后一块，该块对应FAT表的值为文件结束标志。在FAT表中，未使用的块用0表示，因此，当一个文件需要分配新的存储空间时，就在FAT表中查找第一个标志为0的块，用新分配块的块号替换该条目的值，并把该块链接到文件的尾部。,6.6.2 链接分配,采用FAT分配方案可能导致大量的磁头寻道时间，因为磁头必须移到分区的开始位置以便

41、读入FAT，寻找所需块的位置，接着再移到块本身的位置。在最坏的情况下，每块都需要两次移动。但是，通过读入FAT的信息，磁头能找到任何块的位置，所以，FAT分配方案改善了随机访问时间。通常，可以把FAT装入内存，不仅显著地提高检索速度，而且大大减少访问磁盘的次数和磁头的寻道时间，但相应地减少可用内存的数量。,6.6.2 链接分配,3.FAT和NTFS技术(1)FAT12 早期MS-DOS操作系统使用的是FAT12文件系统，主要用于软盘驱动器。FAT12采用12位文件分配表。簇是一组连续的扇区，在FAT中把簇作为一个虚拟扇区，簇的大小一般是2n(n为整数)个盘块，在MS-DOS的实际运用中，簇的容

42、量可以仅有一个扇区(512B)、两个扇区(1KB)、四个扇区(2KB)、八个扇区(4KB)等。一个簇所包含扇区的数量与磁盘容量的大小直接相关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为8MB；当一个簇包含两个扇区时，磁盘的最大容量可达16MB；当一个簇包含八个扇区时，磁盘的最大容量可达64MB。以簇作为基本分配单位可以减少FAT表中的项数(在相同的磁盘容量下，FAT表的项数与簇的大小成反比)，这一方面会减少FAT表占用的存储空间，减少访问FAT表的存取开销，提高文件系统的效率；另一方面能适应磁盘容量的不断增大。但也会造成更大的簇内零头(它与存储器管理中的页内零头相似)。FAT12对所允许的

43、磁盘容量存在着严重的限制，虽然可以通过增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。此外，它只支持8.3格式的文件名。,6.6.2 链接分配,(2)FAT16 FAT16字长为16位，可以使用的簇总数增加到了65 536，此时便能将一个磁盘分区分为65 536(216)个簇。在FAT16的每个簇中可以有的盘块数为4、8、16、32、64，由此可计算出FAT16可以管理的最大分区空间为21664512=2048MB。FAT16只支持8.3格式的文件名，也不支持长文件名。在Windows 95以后的系统中，对FAT16进行了扩展，通过一个长文

44、件名占用多个目录项的方法，使得文件名的长度可以达到255个字符，这种扩展的FAT16称为VFAT。FAT16分区格式存在严重的缺点：大容量磁盘利用效率低。在微软的DOS和Windows系列中，磁盘文件的分配以簇为单位，一个簇只分配给一个文件使用，不管这个文件占用整个簇容量的多少。这样，即使一个很小的文件也要占用一个簇，剩余的簇空间便全部闲置，造成磁盘空间的浪费。由于分区表容量的限制，FAT16分区创建的越大，磁盘上每个簇的容量也越大，从而造成的浪费也越大。,6.6.2 链接分配,(3)FAT32 FAT32文件系统是FAT系列文件系统的最后一个产品。它采用32位的文件分配表，FAT32可以表示

45、4 294 967 296(232)项，FAT32允许管理比FAT16更多的簇，这样就允许FAT32中采用较小的簇，从而可以减少簇内零头，提高磁盘利用率。FAT32的每个簇都固定为4KB，即每簇用8个盘块代替FAT16的64个盘块，每个盘块仍为512字节，FAT32分区格式可以管理的单个最大磁盘空间可达到4KB232=2TB。FAT32比FAT16支持更小的簇和更大的磁盘容量，这就大大减少了磁盘空间的浪费，使得FAT32分区的空间分配更有效率，例如，两个磁盘容量都为2GB，一个磁盘采用FAT16文件系统，另一个磁盘采用FAT32文件系统，采用FAT16磁盘的簇大小为32KB，而FAT32磁盘簇

46、只有4KB的大小，这样，FAT32磁盘碎片减少，比FAT16的磁盘利用率要高得多，通常情况下可以提高15%。FAT32主要应用于Windows 98及后续Windows系统，另外，FAT32支持长文件名。,6.6.2 链接分配,(3)FAT32FAT32仍然存在以下几个方面的不足：由于文件分配表的扩大，运行速度比FAT16格式要慢；FAT32存在最小管理空间的限制，FAT32分区必须至少有65 537个簇，所以FAT32不支持容量小于512MB的分区，因此对于小分区，则仍然需要使用FAT16或FAT12；FAT32的单个文件的长度不能大于4GB；FAT32最大的限制在于兼容性方面，FAT32不

47、能保持向下兼容。,6.6.2 链接分配,(4)NTFSNTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows2000/XP/2003。NTFS具有许多新的特性：首先，它使用64位磁盘地址，理论上可以支持264字节的磁盘分区；其次，在NTFS中可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为32 767个字符；第三，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行；第四，提供了数据的一致性、文件加密、文件压缩等功能。NTFS的不足之处在于，它只能被Windows NT识别。

48、NTFS文件系统可以存取FAT等文件系统的文件，但NTFS文件却不能被FAT等文件系统所存取，缺乏兼容性。Windows 95/98/98SE和Me版本都不能识别NTFS文件系统。,6.6.3 索引分配,1.单级索引分配 链接分配解决了连续分配的外部碎片和大小声明问题，但是，链接分配又出现了如下两个问题：(1)不能有效地支持直接访问。(2)FAT需占用较大的内存空间。索引分配则解决了这个问题，索引分配要求系统为每个文件建立一张索引表，表中的每一栏目指出文件信息所在的逻辑块号和与之对应的物理块号。索引表的物理地址则由文件目录对应的表项给出，这种物理结构形式的文件称为索引文件。,6.6.3 索引分

49、配,索引文件既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取。索引分配方式不会产生外部碎片。索引结构既适用于顺序存取，也适用于随机存取。索引结构的缺点是由于使用索引表而增加了存储空间的开销。另外，在存取文件时需要至少访问存储器两次以上。一种改进的方法是：当对某个文件进行操作之前，系统预先把索引表放入内存。,6.6.3 索引分配,2.多级索引分配 多重索引是在索引表所指的物理块中存放的不是文件信息，而是装有这些信息的物理块地址。这样，如果一个物理块可以装下n个物理块地址的话，则经过一级间接索引，可寻址的文件长度将变为 nn块。如果文件长度还大于nn块的话，还可以进行类似的扩充，即

50、二级间接索引。,6.6.3 索引分配,3.混合索引分配方式 混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。混合索引分配方式把索引表的头几项设计成直接寻址方式，也就是在这几项所指的物理块中存放的是文件信息；而索引表的后几项则设计成多重索引，也就是间接寻址方式。在文件较短时，就可以利用直接寻址方式找到物理块号而节省存取时间。UNIX操作系统就是采用这种索引文件结构，从而使它可以访问数千G字节的文件。,6.7 文件存储空间的管理,文件存储设备是分成若干个大小相等的物理块，并以块为单位进行信息交换，因此，文件存储空间的管理实质上是一个空闲块的组织和管理问题，包括空闲块组织、空闲块