计算机操作系统教程_第四版_第8章 文件系统

《计算机操作系统教程_第四版_第8章 文件系统》由会员分享，可在线阅读，更多相关《计算机操作系统教程_第四版_第8章 文件系统（101页珍藏版）》请在金锄头文库上搜索。

1、第第7章章 文件系统文件系统7.1 文件系统的概念文件系统的概念7.2 文件的逻辑结构与存取方法文件的逻辑结构与存取方法7.3 文件的物理结构与存储设备文件的物理结构与存储设备7.4 文件存储空间管理文件存储空间管理7.5 文件目录管理文件目录管理7.6 文件存取控制文件存取控制7.7 文件的使用文件的使用7.8 文件系统的层次模型文件系统的层次模型本章小结本章小结习题习题对大多数用户来说，文件系统是操作系统中最直接可对大多数用户来说，文件系统是操作系统中最直接可见的部分。计算机的重要作用之一就是能快速处理见的部分。计算机的重要作用之一就是能快速处理大量信息大量信息,从而从而,信息的组织、存取

2、和保管就成为一信息的组织、存取和保管就成为一个极为重要的内容。文件系统是计算机组织、存取个极为重要的内容。文件系统是计算机组织、存取和保存信息的重要手段。本章主要讨论文件的组织和保存信息的重要手段。本章主要讨论文件的组织结构、存取结构、保护以及文件系统空间管理等问结构、存取结构、保护以及文件系统空间管理等问题。题。7.1 文件系统的概念文件系统的概念1. 文件系统的引入文件系统的引入操作系统对计算机的管理包括两个方面：硬件资源的操作系统对计算机的管理包括两个方面：硬件资源的管理和软件资源的管理。硬件资源的管理包括管理和软件资源的管理。硬件资源的管理包括CPU 的管理、存储器的管理、设备管理等，

3、主要解决硬的管理、存储器的管理、设备管理等，主要解决硬件资源的有效和合理利用问题。软件资源的管理则件资源的有效和合理利用问题。软件资源的管理则包括对各种系统程序（包括操作系统本身的程序）、包括对各种系统程序（包括操作系统本身的程序）、系统应用程序或工具（例如编辑程序、编译程序等）系统应用程序或工具（例如编辑程序、编译程序等）、库函数及各种用户程序和数据的管理。图、库函数及各种用户程序和数据的管理。图7.1给出给出了资源管理的分类图。了资源管理的分类图。图图7.1 操作系统的软硬件管理操作系统的软硬件管理显然，用户使用计算机来完成自己的某件任务时，要显然，用户使用计算机来完成自己的某件任务时，要

4、碰到下列问题：碰到下列问题：(1) 使用现有的软件资源来协助完成自己的任务。使用现有的软件资源来协助完成自己的任务。 例例如，如， 编辑、编辑、 编译及链接程序来生成目标代码；编译及链接程序来生成目标代码； 利利用系统调用库函数与实用程序来减少编程工作用系统调用库函数与实用程序来减少编程工作, 避避开与硬件有关的部分等。开与硬件有关的部分等。(2) 编制完成的或未完成的程序存放在什么地方编制完成的或未完成的程序存放在什么地方,需需要访问的数据存放在什么地方，从而使得人们可以要访问的数据存放在什么地方，从而使得人们可以再利用已有的软件资源。再利用已有的软件资源。事实上，这两个问题是一个怎样对软件

5、资源（程序和事实上，这两个问题是一个怎样对软件资源（程序和数据）进行透明存放，并能令这些程序和数据做到数据）进行透明存放，并能令这些程序和数据做到召之即来的问题。在早期的计算机系统中，由于硬召之即来的问题。在早期的计算机系统中，由于硬件资源的限制，只能用卡片或纸带来存放程序或数件资源的限制，只能用卡片或纸带来存放程序或数据。这些卡片和纸带都分别编号存放，当用户需要据。这些卡片和纸带都分别编号存放，当用户需要使用它们时，再把这些卡片和纸带放在读卡机上输使用它们时，再把这些卡片和纸带放在读卡机上输入计算机。入计算机。显然，这些人工干预的控制和保存软件资源的方法不显然，这些人工干预的控制和保存软件资

6、源的方法不可能做到透明存取，极大地限制了计算机的处理能可能做到透明存取，极大地限制了计算机的处理能力和力和 CPU等计算机硬件的利用率。等计算机硬件的利用率。大容量直接存取的磁盘存储器以及顺序存取的磁带存大容量直接存取的磁盘存储器以及顺序存取的磁带存储器等的出现，为程序和数据等软件资源的透明存储器等的出现，为程序和数据等软件资源的透明存取提供了物质基础。这导致了对软件资源管理质的取提供了物质基础。这导致了对软件资源管理质的飞跃飞跃文件系统的出现。文件系统把相应的程序文件系统的出现。文件系统把相应的程序和数据看作文件，并把它们存放在磁盘或磁带等大和数据看作文件，并把它们存放在磁盘或磁带等大容量存

7、储介质上，从而做到对程序和数据的透明存容量存储介质上，从而做到对程序和数据的透明存取。这里，透明存取是指不必了解文件存放的物理取。这里，透明存取是指不必了解文件存放的物理结构和查找方法等与存取介质有关的部分，只需给结构和查找方法等与存取介质有关的部分，只需给定一个代表某段程序或数据的文件名，文件系统就定一个代表某段程序或数据的文件名，文件系统就会自动地完成对与给定文件名相对应文件的有关操会自动地完成对与给定文件名相对应文件的有关操作。作。文件系统必须完成下列工作：文件系统必须完成下列工作：(1) 为了合理的存放文件，必需对磁盘等辅助存储器为了合理的存放文件，必需对磁盘等辅助存储器空间空间 (或

8、称文件空间或称文件空间) 进行统一管理。在用户创建进行统一管理。在用户创建新文件时为其分配空闲区，而在用户删除或修改某新文件时为其分配空闲区，而在用户删除或修改某个文件时个文件时,回收和调整存储区。回收和调整存储区。(2) 为了实现按名存取，需要有一个用户可见的文件为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进逻辑结构，用户按照文件逻辑结构所给定的方式进行信息的存取和加工。这种逻辑结构是独立于物理行信息的存取和加工。这种逻辑结构是独立于物理存储设备的。存储设备的。(3) 为了便于存放和加工信息，文件在存储设备上应为了便于存放和加工信息，文件在存储设备上应

9、按一定的顺序存放。这种存放方式被称为文件的物按一定的顺序存放。这种存放方式被称为文件的物理结构。理结构。(4) 完成对存放在存储设备上的文件信息的查找。完成对存放在存储设备上的文件信息的查找。(5) 完成文件的共享和提供保护功能。完成文件的共享和提供保护功能。2. 文件与文件系统的概念文件与文件系统的概念(1) 文件文件 上面已说过，文件是一段程序或数据的集合。这是一上面已说过，文件是一段程序或数据的集合。这是一种较为模糊的说法。在计算机系统中，文件被解释种较为模糊的说法。在计算机系统中，文件被解释为一组赋名的相关联字符流的集合，或者是相关联为一组赋名的相关联字符流的集合，或者是相关联记录记录

10、( 一个有意义的信息单位一个有意义的信息单位 )的集合。的集合。文件的两种解释定义了两种文件形式。赋名的字符流文件的两种解释定义了两种文件形式。赋名的字符流文件是一种无结构文件或流式文件。目前常用的操文件是一种无结构文件或流式文件。目前常用的操作系统，例如作系统，例如 UNIX 操作系统，操作系统，MS-DOS等均采用等均采用无结构文件形式。无结构文件由于采用字符流方式，无结构文件形式。无结构文件由于采用字符流方式，与源程序、目标代码等在形式上是一致的，因此，与源程序、目标代码等在形式上是一致的，因此，该方式适用于源程序、目标代码等文件。由相关联该方式适用于源程序、目标代码等文件。由相关联记录

11、组成的文件中的有些基本信息单位是记录。记记录组成的文件中的有些基本信息单位是记录。记录是由录是由 N (N 1) 个字节组成的具有特定意义的信息个字节组成的具有特定意义的信息单位。记录式文件主要用于信息管理。单位。记录式文件主要用于信息管理。在有些操作系统中，从字符流文件的角度出发，设备在有些操作系统中，从字符流文件的角度出发，设备也被看作是赋予特殊文件名的文件。从而，系统可也被看作是赋予特殊文件名的文件。从而，系统可以对设备和文件实施统一管理，以致大大简化设备以对设备和文件实施统一管理，以致大大简化设备管理程序和文件系统的接口设计。管理程序和文件系统的接口设计。用户文件名由用户给定，它是一个

12、字母数字串，有些用户文件名由用户给定，它是一个字母数字串，有些系统规定必须是英文字母打头且允许一些其他的符系统规定必须是英文字母打头且允许一些其他的符号出现在文件名的非打头部分。例如号出现在文件名的非打头部分。例如a.out，ccdos.exe均为合法文件名。均为合法文件名。(2) 文件系统文件系统 操作系统中与管理文件有关的软件和数据称为文件系操作系统中与管理文件有关的软件和数据称为文件系统。它负责为用户建立文件，撤消、读写、修改和统。它负责为用户建立文件，撤消、读写、修改和复制文件，还负责完成对文件的按名存取和进行存复制文件，还负责完成对文件的按名存取和进行存取控制。取控制。文件系统具有以

13、下特点：文件系统具有以下特点： 友好的用户接口，用户只对文件进行操作，而不友好的用户接口，用户只对文件进行操作，而不管文件结构和存放的物理位置。管文件结构和存放的物理位置。 对文件按名存取，对用户透明。对文件按名存取，对用户透明。 某些文件可以被多个用户或进程所共享。某些文件可以被多个用户或进程所共享。 文件系统大都使用磁盘、磁带和光盘等大容量存文件系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质，因此，可存储大量信息。储器作为存储介质，因此，可存储大量信息。3. 文件的分类文件的分类在文件系统中，为了有效、方便地管理文件，常常把在文件系统中，为了有效、方便地管理文件，常常把文件按其性质

14、和用途等进行分类。文件按其性质和用途等进行分类。按文件的性质和用途可以分为三类：按文件的性质和用途可以分为三类：(1) 系统文件系统文件该类文件只允许用户通过系统调用来执行它们，而不该类文件只允许用户通过系统调用来执行它们，而不允许对其进行读写和修改。允许对其进行读写和修改。 这些文件主要由操作系这些文件主要由操作系统核心和各种系统应用程序和数据所组成。统核心和各种系统应用程序和数据所组成。(2) 库文件库文件该类文件允许用户对其进行读取、执行，该类文件允许用户对其进行读取、执行， 但不允许但不允许对其进行修改。库文件主要由各种标准子程序库组对其进行修改。库文件主要由各种标准子程序库组成。如成

15、。如 C 语言子程序库、语言子程序库、FORTRAN子程序库等。子程序库等。 (3) 用户文件用户文件用户文件是用户委托文件系统保存的文件。这类文件用户文件是用户委托文件系统保存的文件。这类文件只由文件的所有者或所有者授权的用户才能使用。只由文件的所有者或所有者授权的用户才能使用。用户文件主要由源程序、目标程序、用户数据库等用户文件主要由源程序、目标程序、用户数据库等组成。组成。另外，按组织形式，文件又可被画分为以下三类：另外，按组织形式，文件又可被画分为以下三类：(1) 普通文件普通文件普通文件既包括系统文件，也包括用户文件和库函数普通文件既包括系统文件，也包括用户文件和库函数文件、实用程序

16、文件。普通文件主要是指组织格式文件、实用程序文件。普通文件主要是指组织格式为系统中所规定的最一般格式的文件，例如由字符为系统中所规定的最一般格式的文件，例如由字符流组成的文件。流组成的文件。(2) 目录文件目录文件目录文件是由文件的目录信息构成的特殊文件。即该目录文件是由文件的目录信息构成的特殊文件。即该文件的内容不是各种程序或应用数据，而是用来检文件的内容不是各种程序或应用数据，而是用来检索普通文件的目录信息。索普通文件的目录信息。(3) 特殊文件特殊文件在在 UNIX 系统中，所有的输入、输出设备都被看作特系统中，所有的输入、输出设备都被看作特殊文件。这组特殊文件在使用形式上与普通文件相殊

17、文件。这组特殊文件在使用形式上与普通文件相同，如查找目录、存取操作等。同，如查找目录、存取操作等。除了按文件的用途和组织形式来分类外，还可以按文除了按文件的用途和组织形式来分类外，还可以按文件中的信息流向或文件的保护级别等分类。例如，件中的信息流向或文件的保护级别等分类。例如，按信息流向可把文件分为：输入文件、输出文件、按信息流向可把文件分为：输入文件、输出文件、以及输入以及输入/ 输出文件等。按文件的保护级别又可分输出文件等。按文件的保护级别又可分为：只读文件、读写文件、可执行文件和不保护文为：只读文件、读写文件、可执行文件和不保护文件等。件等。文件的分类主要是便于系统对不同的文件进行不同的

18、文件的分类主要是便于系统对不同的文件进行不同的管理，从而提高处理速度和起到保护与共享的作用。管理，从而提高处理速度和起到保护与共享的作用。例如，一个系统文件在读入内存时将被放在内存的例如，一个系统文件在读入内存时将被放在内存的某一固定区且享受高的保护级别，从而不必像一般某一固定区且享受高的保护级别，从而不必像一般的用户文件那样只有在内存用户可用区分得相应的的用户文件那样只有在内存用户可用区分得相应的空闲区之后才能被调入内存。空闲区之后才能被调入内存。7.2 文件的逻辑结构与存取方法文件的逻辑结构与存取方法7.2.1 逻辑结构逻辑结构文件的逻辑结构是用户可见结构。文件的逻辑结构可文件的逻辑结构是

19、用户可见结构。文件的逻辑结构可分为两大类：字符流式的无结构文件和记录式的有分为两大类：字符流式的无结构文件和记录式的有结构文件。在文件系统设计时，选择何种逻辑结构结构文件。在文件系统设计时，选择何种逻辑结构才能更有利于用户对文件信息的操作呢？一般情况才能更有利于用户对文件信息的操作呢？一般情况下，选取文件的逻辑结构应遵循下述原则：下，选取文件的逻辑结构应遵循下述原则：(1) 当用户对文件信息进行修改操作时，给定的逻辑当用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。结构应能尽量减少对已存储好的文件信息的变动。(2) 当用户需要对文件信息进行操作时，给定的逻辑

20、当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统在尽可能短的时间内查找到需要结构应使文件系统在尽可能短的时间内查找到需要查找的记录或基本信息单位。查找的记录或基本信息单位。(3) 应使文件信息占据最小的存储空间。应使文件信息占据最小的存储空间。(4) 应是便于用户进行操作的。应是便于用户进行操作的。显然，对于字符流的无结构文件来说，查找文件中的显然，对于字符流的无结构文件来说，查找文件中的基本信息单位，例如某个单词，是比较困难的。但基本信息单位，例如某个单词，是比较困难的。但反过来，字符流的无结构文件管理简单，用户可以反过来，字符流的无结构文件管理简单，用户可以方便地对其进行操作。所

21、以，那些对基本信息单位方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，操作不多的文件较适于采用字符流的无结构方式，例如，源程序文件、目标代码文件等。例如，源程序文件、目标代码文件等。除了字符流的无结构方式外，记录式的有结构文件可除了字符流的无结构方式外，记录式的有结构文件可把文件中的记录按各种不同的方式排列，构成不同把文件中的记录按各种不同的方式排列，构成不同的逻辑结构，以便用户对文件中的记录进行修改、的逻辑结构，以便用户对文件中的记录进行修改、追加、查找和管理等操作。追加、查找和管理等操作。记录是一个具有特定意义的信息单位，它由该记录在记录是一个具有特

22、定意义的信息单位，它由该记录在文件中的逻辑地址文件中的逻辑地址(相对位置相对位置) 与记录名所对应的一与记录名所对应的一组键、属性及其属性值所组成。图组键、属性及其属性值所组成。图7.2是一个记录的是一个记录的组成例。组成例。图图7.2 记录组成例记录组成例图中，图中，1296是名为是名为R 的记录在文件中的逻辑地址，的记录在文件中的逻辑地址，姓名姓名 : A 是该记录的键，而是该记录的键，而 性别性别，出生出生年月年月，工资工资 等是该记录的属性，紧跟在这些等是该记录的属性，紧跟在这些后面的是属性值。一个记录可以有多个键名，每个后面的是属性值。一个记录可以有多个键名，每个键名可对应于多项属性

23、。再者，根据各系统设计的键名可对应于多项属性。再者，根据各系统设计的要求不一样，记录既可以是定长的，也可以是变长要求不一样，记录既可以是定长的，也可以是变长的。记录的长度可以短到一个字符，也可以长到一的。记录的长度可以短到一个字符，也可以长到一个文件，这要由系统设计人员确定。个文件，这要由系统设计人员确定。常用的记录式结构文件有以下几种常用的记录式结构文件有以下几种:(1) 连续结构；连续结构； (2) 多重结构；多重结构； (3) 转置结构；转置结构； (4) 顺序结构。顺序结构。下面分别介绍这几种结构。下面分别介绍这几种结构。(1) 连续结构连续结构连续结构是一种把记录按生成的先后顺序连续

24、排列的连续结构是一种把记录按生成的先后顺序连续排列的逻辑结构。连续结构的特点是适用性强，可用于所逻辑结构。连续结构的特点是适用性强，可用于所有文件有文件 ，且记录的排列顺序与记录的内容无关。这，且记录的排列顺序与记录的内容无关。这有利于记录的追加与变更。但是，连续结构文件的有利于记录的追加与变更。但是，连续结构文件的搜索性能较差，例如要找出某个指定键的记录时，搜索性能较差，例如要找出某个指定键的记录时，系统必须对文件全体进行搜索。系统必须对文件全体进行搜索。(2) 多重结构多重结构 如果把记录按键和记录名排列成行列式结构，则一个如果把记录按键和记录名排列成行列式结构，则一个包含包含n个记录名、

25、个记录名、m个个(mn)个键的文件构成一个键的文件构成一m*n维行列式维行列式(如图如图7.3)。其中，如果第。其中，如果第i(1im) 行行和第和第j(1jn) 列所对应的位置上为列所对应的位置上为1，则表示键，则表示键Ki在记录在记录 R中中; 反之反之,则表示键则表示键Ki不在记录不在记录 Rj 中。另中。另外，同一个键也可以同时属于不同记录。外，同一个键也可以同时属于不同记录。图图7.3 文件的记录名和键构成的行列式文件的记录名和键构成的行列式显然，如果只按行列式结构来排列记录，将会浪费较显然，如果只按行列式结构来排列记录，将会浪费较多的存储空间。从而，我们把行列式中那些为零的多的存储

26、空间。从而，我们把行列式中那些为零的项去掉，并以键项去掉，并以键Ki为队首，以包含键为队首，以包含键Ki的记录为队的记录为队列元素来构成一个记录队列。对于一个有列元素来构成一个记录队列。对于一个有m个键的个键的队列来说，这样的队列有队列来说，这样的队列有m个。这个。这m个队列构成了个队列构成了该文件的多重结构该文件的多重结构(multi_list)。如图如图7.4所示。所示。(3) 转置结构转置结构 在图在图7.4的多重结构中，每个队列中和键直接相连的的多重结构中，每个队列中和键直接相连的只有一个记录。这种结构虽然在探索时要优于连续只有一个记录。这种结构虽然在探索时要优于连续结构，但在探索某一

27、特定记录时，必须在找到该记结构，但在探索某一特定记录时，必须在找到该记录所对应的键之后，再在该键所对应的队列中顺序录所对应的键之后，再在该键所对应的队列中顺序查找。与此相反，转置结构把含有相同键的记录指查找。与此相反，转置结构把含有相同键的记录指针全部指向该键，也就是说，把所有与同一键对应针全部指向该键，也就是说，把所有与同一键对应的记录的指针连续地置于目录中该键的位置下的记录的指针连续地置于目录中该键的位置下(图图7.5)。转置结构最适合于给定键后的记录搜索。转置结构最适合于给定键后的记录搜索。图图7.4 文件的多重结构文件的多重结构 图图7.5 文件的转置结构文件的转置结构(4) 顺序结构

28、顺序结构如果系统要求按某种优先顺序来搜索或追加、删除记如果系统要求按某种优先顺序来搜索或追加、删除记录，则最好采用顺序结构。如果给定了顺序规定录，则最好采用顺序结构。如果给定了顺序规定(例如按字母顺序例如按字母顺序)，则把文件中的键按规定的顺序，则把文件中的键按规定的顺序排列起来就形成了顺序结构文件。例如，把人民日排列起来就形成了顺序结构文件。例如，把人民日报上登载的新闻按年月日为键做成记录放入文件中，报上登载的新闻按年月日为键做成记录放入文件中，并以时间先后顺序组成文件。这样，如果要处理某并以时间先后顺序组成文件。这样，如果要处理某段时间内所发生的大事等问题，就会变得非常简单。段时间内所发生

29、的大事等问题，就会变得非常简单。例如用户想了解两伊战争的情况，则只要把例如用户想了解两伊战争的情况，则只要把1990年年8 月月19日开始的两个月内的有关记录搜索到就行了。日开始的两个月内的有关记录搜索到就行了。7.2.2 存取方法存取方法用户通过对文件的存取来完成对文件的修改、追加和用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。常用的存取方法有三种：搜索等操作。常用的存取方法有三种：(1) 顺序存取法顺序存取法(2) 随机存取法随机存取法(直接存取法直接存取法)(3) 按键存取法按键存取法 顺序存取是按照文件的逻辑地址顺序存取。在记录式顺序存取是按照文件的逻辑地址顺序存取。在记录

30、式文件中，这反映为按记录的排列顺序来存取，例如，文件中，这反映为按记录的排列顺序来存取，例如，若当前读取的记录为若当前读取的记录为Ri，则下一次读取的记录被自则下一次读取的记录被自动地确定为动地确定为Ri的下一个相邻的记录的下一个相邻的记录Ri+1。在无结构在无结构的字符流文件中，顺序存取反映当前读写指针的变的字符流文件中，顺序存取反映当前读写指针的变化。在存取完一段信息之后，读写指针自动加或减化。在存取完一段信息之后，读写指针自动加或减去该段信息长度，以便指出下次存取时的位置。去该段信息长度，以便指出下次存取时的位置。随机存取法允许用户根据记录的编号来存取文件的任随机存取法允许用户根据记录的

31、编号来存取文件的任一记录，或者是根据存取命令把读写指针移到欲读一记录，或者是根据存取命令把读写指针移到欲读写处来读写。写处来读写。UNIX系统以及系统以及MS-DOS等操作系统等操作系统都采用顺序存取和随机存取等两种方法。都采用顺序存取和随机存取等两种方法。按键存取是一种用在复杂文件系统，特别是数据库管按键存取是一种用在复杂文件系统，特别是数据库管理系统中的存取方法。文件的存取是根据给定的键理系统中的存取方法。文件的存取是根据给定的键或记录名进行的。按键存取法首先搜索到要进行存或记录名进行的。按键存取法首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地取的记录的逻辑位置，再将其转换

32、到相应的物理地址后进行存取。下面，介绍按键存取的搜索方法。址后进行存取。下面，介绍按键存取的搜索方法。对文件进行搜索的目的是要查找出特定记录所对应的对文件进行搜索的目的是要查找出特定记录所对应的逻辑地址，以便将其转换为相应的物理地址，实现逻辑地址，以便将其转换为相应的物理地址，实现对文件的操作。对文件的操作。对文件的搜索包括两种：键的搜索和记录的搜索。对对文件的搜索包括两种：键的搜索和记录的搜索。对键的搜索是在用户给定所要搜索的键名和记录之后，键的搜索是在用户给定所要搜索的键名和记录之后，确定该键名在文件中的位置；而记录的搜索则是在确定该键名在文件中的位置；而记录的搜索则是在搜索到所要查找的键

33、之后，在含有该键的所有记录搜索到所要查找的键之后，在含有该键的所有记录中查找出所需要的记录。显然，对于不同的逻辑结中查找出所需要的记录。显然，对于不同的逻辑结构的文件，其搜索方法和搜索效率都是不一样的。构的文件，其搜索方法和搜索效率都是不一样的。对指定记录对指定记录Ri的搜索过程如图的搜索过程如图7.6所示。所示。对于给定的对于给定的Ri,首先首先,系统确定系统确定Ri所对应键名的记录队所对应键名的记录队列。如果在所查找的文件中不存在这样的队列，则列。如果在所查找的文件中不存在这样的队列，则搜索算法结束返回，从而无法搜索到搜索算法结束返回，从而无法搜索到Ri。如果找到如果找到Ri，则返回其所对

34、应的逻辑地址。如果找不到则返回其所对应的逻辑地址。如果找不到Ri，则返回无法找到则返回无法找到Ri的有关信息。的有关信息。图图7.6 记录记录 Ri的搜索过程的搜索过程对键或记录的搜索与其他数据搜索问题一样，都属于对键或记录的搜索与其他数据搜索问题一样，都属于表格搜索问题表格搜索问题。有许多搜索算法用来解决表格搜索有许多搜索算法用来解决表格搜索问题。这些算法可以大致分为三种类型。即，问题。这些算法可以大致分为三种类型。即，(1) 线性搜索法线性搜索法(linear search)，(2) 散列法散列法(hash coding)，(3) 二分搜索法二分搜索法(binary search algo

35、rithm)。下面分别简单地介绍这几种搜索算法。下面分别简单地介绍这几种搜索算法。(1) 线性搜索法线性搜索法它从第一个键或记录开始，依次和所要搜索的键或记它从第一个键或记录开始，依次和所要搜索的键或记录相比较，直到找到所需要的记录为止。线性搜索录相比较，直到找到所需要的记录为止。线性搜索法所需要的搜索时间与所搜索的表格大小的法所需要的搜索时间与所搜索的表格大小的 1/2成成正比。这是因为找到一个所需要的记录平均要和表正比。这是因为找到一个所需要的记录平均要和表中登记的总项数的中登记的总项数的1/2项比较后才能得到。项比较后才能得到。线性搜索法的搜索效率较低，在文件中记录个数较多线性搜索法的搜

36、索效率较低，在文件中记录个数较多时不宜采用。时不宜采用。(2) 散列法散列法散列搜索法被被广泛用于现代操作系统的数据查找。散列搜索法被被广泛用于现代操作系统的数据查找。散列法的核心思想是定义一个散列函数散列法的核心思想是定义一个散列函数h(k)，使得使得对于给定的键对于给定的键k，散列函数散列函数h(k)将其变换为将其变换为 k所对应所对应的逻辑地址。的逻辑地址。在使用散列函数进行搜索时，有时会出现两个不同的在使用散列函数进行搜索时，有时会出现两个不同的输入值变换到同一地址的问题。即对于输入值变换到同一地址的问题。即对于k1!=k2，有，有h(k1)=h(k2)=A。显然，显然，k1和和k2

37、中，至少有一个与中，至少有一个与 A中的内容不一致。也就是说，由散列变换得到的结中的内容不一致。也就是说，由散列变换得到的结果并不是所要搜索的键。这种问题称为散列冲突。果并不是所要搜索的键。这种问题称为散列冲突。解决散列冲突的方法是采用多次散列探索。例如，解决散列冲突的方法是采用多次散列探索。例如，设设第第i 次散列变换的结果为次散列变换的结果为hi(k)，i=2,3，则可令则可令hi(k) =(h1(k) +di)(mod t)这里，这里，t 为被搜索表格长度，为被搜索表格长度，di为第为第i 次搜索所得地址次搜索所得地址与第与第1次搜索所得地址之间的距离。次搜索所得地址之间的距离。di的取

38、值方法很的取值方法很多，最简单的方法是设多，最简单的方法是设di为为i的线性函数，即的线性函数，即di=a*i(a为一大于零的常数为一大于零的常数)。这种方法称线性散列法。这种方法称线性散列法。但是，使用线性散列法并不能完全解决散列冲突问但是，使用线性散列法并不能完全解决散列冲突问题。例如，对于题。例如，对于i!=j，k=1,2，如果如果 hi(k1)=hj(k2)，则存在则存在 hi+k(k1)=hj+k(k2)。解决散列冲解决散列冲突的另一个方法是生成一组随机数突的另一个方法是生成一组随机数r1,r2，rn，且令且令di=ri。显然，除了显然，除了 h1(k1)=h1(k2)可能存在之可能

39、存在之外，外，h1(k1)=h1+k(k2)的可能性很小，不过，使用随的可能性很小，不过，使用随机数的方法需要占用一定的存储空间来生成和存放机数的方法需要占用一定的存储空间来生成和存放随机数组。随机数组。还有一个解决散列冲突的方法是采用平方散列函数方还有一个解决散列冲突的方法是采用平方散列函数方法。即令：法。即令：hi(k) =(h1(k)+c*(i*i)(mod t) 这里，这里，t是一个表示被搜索表格长度的素数，是一个表示被搜索表格长度的素数，c 是一个是一个大于零的常数。可以证明，对于大于零的常数。可以证明，对于j1(mod t)，即使即使有有 h1(k1)=hj(k2)，那么，对于那么

40、，对于i=1,2，t-1，有有 hi(k1)!=hj+i(k2)。(3) 二分搜索法二分搜索法 对于顺序结构排列的键或记录来说，二分搜索法具有对于顺序结构排列的键或记录来说，二分搜索法具有较高的搜索效率。较高的搜索效率。设键设键K0,K1,K2，Kn(n1)按键间距按键间距d排列，如果排列，如果K0的逻辑位置的逻辑位置为为a0，则有则有Ki的逻辑位置为的逻辑位置为a0+i*d。二分搜索法首先把所要搜的键与队列的首尾键相比较二分搜索法首先把所要搜的键与队列的首尾键相比较,如果和其中之一相等，则返回所搜索到的键的逻辑如果和其中之一相等，则返回所搜索到的键的逻辑位置。否则，再与队列位置。否则，再与队

41、列1/2处的键比较，如果所要处的键比较，如果所要搜索的键正好等于该键的话搜索的键正好等于该键的话,则返回该键的逻辑地则返回该键的逻辑地址；否则，如果所要搜索的键址；否则，如果所要搜索的键K 小于位于队列中央小于位于队列中央的键的话，则继续搜索左边的半个队列。如果所要的键的话，则继续搜索左边的半个队列。如果所要搜索的键搜索的键K大于位于队列中央的键的话大于位于队列中央的键的话,则继续搜则继续搜索右边的半个队列。这样，每次用以中央键画分的索右边的半个队列。这样，每次用以中央键画分的部分组成新的队列反复进行上述搜索操作，直到找部分组成新的队列反复进行上述搜索操作，直到找到为止。这一搜索过程如图到为止

42、。这一搜索过程如图7.7所示。所示。二分搜索法的好处是搜索效率高。与线性搜索法相比，二分搜索法的好处是搜索效率高。与线性搜索法相比，当当 n(表长表长)=16时时,它比线性搜索法约快二倍它比线性搜索法约快二倍; 当当 n=1 024 时，其平均搜索速度要快时，其平均搜索速度要快50倍。不过，二倍。不过，二分搜索法需要事先把搜索对象按一定顺序排列。分搜索法需要事先把搜索对象按一定顺序排列。图图7.7 二分搜索法的搜索过程二分搜索法的搜索过程7.3 文件的物理结构与存储设备文件的物理结构与存储设备文件系统采用哪种存取方法和逻辑结构，实际上是和文件系统采用哪种存取方法和逻辑结构，实际上是和物理存储介

43、质有关的。因此，本节介绍文件的物理物理存储介质有关的。因此，本节介绍文件的物理结构，同时也介绍常用的文件存储设备。结构，同时也介绍常用的文件存储设备。7.3.1 文件的物理结构文件的物理结构在文件系统中，文件的存储设备通常画分为若干个大在文件系统中，文件的存储设备通常画分为若干个大小相等的物理块，每块长为小相等的物理块，每块长为 512 或或 1024字节。与此字节。与此相对应，为了有效地利用存储设备和便于系统管理相对应，为了有效地利用存储设备和便于系统管理,一般把文件信息也画分为与物理存储设备的物理块一般把文件信息也画分为与物理存储设备的物理块大小相等的逻辑块。从而，以块作为分配和传送信大小

44、相等的逻辑块。从而，以块作为分配和传送信息的基本单位。显然，对于字符流的无结构文件来息的基本单位。显然，对于字符流的无结构文件来说，每一个物理块中存放长度相等的文件信息说，每一个物理块中存放长度相等的文件信息(存存储文件尾部信息的物理块除外储文件尾部信息的物理块除外)。但是，对于记录。但是，对于记录式文件来说，由于记录长度既可以是固定的，也可式文件来说，由于记录长度既可以是固定的，也可以是可变的，而且其长度不一定刚好等于其物理块以是可变的，而且其长度不一定刚好等于其物理块的长度，从而给由记录的逻辑地址到物理地址的变的长度，从而给由记录的逻辑地址到物理地址的变换带来了额外的负担。换带来了额外的负

45、担。这里，为了简单起见，假设文件系统中每个记录的长这里，为了简单起见，假设文件系统中每个记录的长度是固定的，且其长度正好等于物理块的长度。从度是固定的，且其长度正好等于物理块的长度。从而，对于记录式文件来说，利用上节讨论的搜索算而，对于记录式文件来说，利用上节讨论的搜索算法得到的逻辑地址正好与文件的逻辑块号一一对应，法得到的逻辑地址正好与文件的逻辑块号一一对应，这就简化了所讨论问题的条件。这就简化了所讨论问题的条件。文件的物理结构是指文件在存储设备上的存放方法。文件的物理结构是指文件在存储设备上的存放方法。事实上，由于文件的物理结构决定了文件信息在存事实上，由于文件的物理结构决定了文件信息在存

46、储设备上的存储位置，因此，文件信息的逻辑块号储设备上的存储位置，因此，文件信息的逻辑块号(逻辑地址逻辑地址) 到物理块号到物理块号(物理地址物理地址) 的变换也是由的变换也是由文件的物理结构决定的。文件的物理结构决定的。常用的文件物理结构如下：常用的文件物理结构如下：(1) 连续文件连续文件连续文件是一种最简单的物理文件结构，它把一个在连续文件是一种最简单的物理文件结构，它把一个在逻辑上连续的文件信息依次存放到物理块中。逻辑上连续的文件信息依次存放到物理块中。在图在图7.8中，一个逻辑块号为中，一个逻辑块号为 0,1,2,3的文件依次存放的文件依次存放在物理块在物理块 10,11,12,13中

47、。中。连续文件结构的优点是一旦知道了文件在文件存储设连续文件结构的优点是一旦知道了文件在文件存储设备上的起址和文件长度，就能很快地进行存取。这备上的起址和文件长度，就能很快地进行存取。这是因为文件的逻辑块号到物理块号的变换可以非常是因为文件的逻辑块号到物理块号的变换可以非常简单地完成。但是连续文件结构在建立文件时必须简单地完成。但是连续文件结构在建立文件时必须在文件说明信息中确定文件信息长度，且以后不能在文件说明信息中确定文件信息长度，且以后不能动态增长。而且在文件进行某些部分的删除后，又动态增长。而且在文件进行某些部分的删除后，又会留下无法使用的零头空间。因此，连续文件结构会留下无法使用的零

48、头空间。因此，连续文件结构不宜用来存放用户文件、数据库文件等经常被修改不宜用来存放用户文件、数据库文件等经常被修改的文件。的文件。图图7.8 连续文件结构连续文件结构(2) 串联文件串联文件克服连续文件的缺点的办法之一是采用串联文件结构。克服连续文件的缺点的办法之一是采用串联文件结构。串联文件结构用非连续的物理块来存放文件信息。串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系，其中每个这些非连续的物理块之间没有顺序关系，其中每个物理块设有一个指针，指向其后续连接的另一个物物理块设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个理块，

49、从而使得存放同一文件的物理块链接成一个串联队列。图串联队列。图7.9给出了串联文件的物理结构。给出了串联文件的物理结构。显然，使用串联文件结构时，不必在文件说明信息中显然，使用串联文件结构时，不必在文件说明信息中指明文件的长度，只需指明该文件的第一个块号就指明文件的长度，只需指明该文件的第一个块号就行了。串联文件结构的另一个特点是文件长度可以行了。串联文件结构的另一个特点是文件长度可以动态地增长，只要调整连接指针就可在任何一个信动态地增长，只要调整连接指针就可在任何一个信息块之间插入或删除一个信息块。息块之间插入或删除一个信息块。图图7.9 串联文件的物理结构串联文件的物理结构用串联文件结构时

50、，逻辑块到物理块的转换由系统沿用串联文件结构时，逻辑块到物理块的转换由系统沿串联队列查找与逻辑块号对应的物理块号的办法完串联队列查找与逻辑块号对应的物理块号的办法完成。例如，在图成。例如，在图7.9的文件结构中，如果用户所要进的文件结构中，如果用户所要进行操作的逻辑块号为行操作的逻辑块号为2，则系统从第一个物理块，则系统从第一个物理块20开始，一直沿串联队列搜索到队列中逻辑块号为开始，一直沿串联队列搜索到队列中逻辑块号为2的第三块时，得到其所对应的物理块号为的第三块时，得到其所对应的物理块号为22。由于串联文件结构只能按队列中的串联指针顺序搜索，由于串联文件结构只能按队列中的串联指针顺序搜索，

51、因此，串联文件结构的搜索效率较低。串连文件结因此，串联文件结构的搜索效率较低。串连文件结构一般只适用于逻辑上连续的文件，且存取方法应构一般只适用于逻辑上连续的文件，且存取方法应该是顺序存取的。否则，为了读取某个信息块而造该是顺序存取的。否则，为了读取某个信息块而造成的磁头大幅度移动将花去较多的时间。因此，串成的磁头大幅度移动将花去较多的时间。因此，串联文件结构不适宜随机存取。联文件结构不适宜随机存取。(3) 索引文件索引文件第三种文件物理结构是索引结构。索引结构要求系统第三种文件物理结构是索引结构。索引结构要求系统为每个文件建立一张索引表，表中每一栏目指出文为每个文件建立一张索引表，表中每一栏

52、目指出文件信息所在的逻辑块号和与之对应的物理块号。索件信息所在的逻辑块号和与之对应的物理块号。索引表的物理地址则由文件说明信息项给出。索引结引表的物理地址则由文件说明信息项给出。索引结构如图构如图7.10所示。所示。索引文件结构既可以满足文件动态增长的要求，又可索引文件结构既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取。因为有关逻辑以较为方便和迅速地实现随机存取。因为有关逻辑块号和物理块号的信息全部放在一个集中的索引表块号和物理块号的信息全部放在一个集中的索引表中，而不是像串联文件结构那样分散在各个物理块中，而不是像串联文件结构那样分散在各个物理块中。中。图图7.10 索引文

53、件示意图索引文件示意图在很多情况下，有的文件很大，文件索引表也就较大。在很多情况下，有的文件很大，文件索引表也就较大。如果索引表的大小超过了一个物理块，那么我们必如果索引表的大小超过了一个物理块，那么我们必须象处理其他文件的存放那样决定索引表的物理存须象处理其他文件的存放那样决定索引表的物理存放方式，但这不利于索引表的动态增加；索引表也放方式，但这不利于索引表的动态增加；索引表也可按串联方式存放，但这却增加了存放索引表的时可按串联方式存放，但这却增加了存放索引表的时间开销。一种较好的解决办法是采用间接索引间开销。一种较好的解决办法是采用间接索引(多多重索引重索引)，也就是在索引表所指的物理块中

54、存放的，也就是在索引表所指的物理块中存放的不是文件信息，而是装有这些信息的物理块地址。不是文件信息，而是装有这些信息的物理块地址。这样，如果一个物理块可装下这样，如果一个物理块可装下n个物理块地址的话，个物理块地址的话，则经过一级间接索引，可寻址的文件长度将变为则经过一级间接索引，可寻址的文件长度将变为 n*n 块。如果文件长度还大于块。如果文件长度还大于 n*n块的话，还可以块的话，还可以进行类似的扩充，即二级间接索引。其原理如图进行类似的扩充，即二级间接索引。其原理如图7.11。图图7.11 多重索引结构多重索引结构不过，大多数文件不需要进行多重索引，也就是说，不过，大多数文件不需要进行多

55、重索引，也就是说，这些文件所占用的物理块数的块号可以放在一个物这些文件所占用的物理块数的块号可以放在一个物理块内。如果对这些文件也采用多重索引，则显然理块内。如果对这些文件也采用多重索引，则显然会降低文件的存取速度。因此，在实际系统中，总会降低文件的存取速度。因此，在实际系统中，总是把索引表的头几项设计成直接寻址方式，也就是是把索引表的头几项设计成直接寻址方式，也就是这几项所指的物理块中存放的是文件信息；而索引这几项所指的物理块中存放的是文件信息；而索引表的后几项设计成多重索引，也就是间接寻址方式。表的后几项设计成多重索引，也就是间接寻址方式。在文件较短时，就可利用直接寻址方式找到物理块在文件

56、较短时，就可利用直接寻址方式找到物理块号而节省存取时间。号而节省存取时间。索引结构既适用于顺序存取，也适用于随机存取。索索引结构既适用于顺序存取，也适用于随机存取。索引结构的缺点是由于使用了索引表而增加了存储空引结构的缺点是由于使用了索引表而增加了存储空间的开销。另外，在存取文件时需要至少访问存储间的开销。另外，在存取文件时需要至少访问存储器二次以上。其中，一次是访问索引表，另一次是器二次以上。其中，一次是访问索引表，另一次是根据索引表提供的物理块号访问文件信息。由于文根据索引表提供的物理块号访问文件信息。由于文件在存储设备的访问速度较慢，因此，如果把索引件在存储设备的访问速度较慢，因此，如果

57、把索引表放在存储设备上，势必大大降低文件的存取速度。表放在存储设备上，势必大大降低文件的存取速度。一种改进的方法是，当对某个文件进行操作之前，一种改进的方法是，当对某个文件进行操作之前，系统预先把索引表放入内存。这样，文件的存取就系统预先把索引表放入内存。这样，文件的存取就可直接在内存通过索引表确定物理地址块号，而访可直接在内存通过索引表确定物理地址块号，而访问磁盘的动作只需要一次。问磁盘的动作只需要一次。7.3.2 文件存储设备文件存储设备常用的存储设备有磁盘、光盘、磁带等。其中磁盘又常用的存储设备有磁盘、光盘、磁带等。其中磁盘又可分为硬盘和软盘。由于存储设备的特性决定了文可分为硬盘和软盘。

58、由于存储设备的特性决定了文件的存取设备和方法，因此，这里介绍以磁带为代件的存取设备和方法，因此，这里介绍以磁带为代表的顺序存储设备和以磁盘为代表的直接存储设备表的顺序存储设备和以磁盘为代表的直接存储设备的特性及有关存取方法。的特性及有关存取方法。1. 顺序存取设备顺序存取设备磁带是一种最典型的顺序存取设备。顺序存取设备只磁带是一种最典型的顺序存取设备。顺序存取设备只有在前面的物理块被存取访问过之后，才能存取后有在前面的物理块被存取访问过之后，才能存取后续的物理块的内容。而且，为了在存取一个物理块续的物理块的内容。而且，为了在存取一个物理块时让磁带机提前加速和不停止在下一个物理块的位时让磁带机提

59、前加速和不停止在下一个物理块的位置上，磁带的两相邻的物理块之间设计有一个间隙置上，磁带的两相邻的物理块之间设计有一个间隙将它们隔开将它们隔开(图图7.12)。图图7.12 磁带的结构磁带的结构磁带设备的存取速度或数据传输率与下列因素有关：磁带设备的存取速度或数据传输率与下列因素有关：(1) 信息密度信息密度(字符数字符数/英寸英寸)(2) 磁带带速磁带带速(英寸英寸/秒秒)(3) 块间间隙块间间隙 如果带速高，信息密度大，且所需块间隙如果带速高，信息密度大，且所需块间隙(磁头启动磁头启动和停止时间和停止时间) 小的话，则磁带存取速度和数据传输小的话，则磁带存取速度和数据传输率高，反之亦然。率高

60、，反之亦然。另外，由磁带的读写方式可知，只有当第另外，由磁带的读写方式可知，只有当第i块被存取块被存取之后，才能对第之后，才能对第i+1块进行存取操作。因此，某个块进行存取操作。因此，某个特定记录或物理块的存取访问与该物理块到磁头当特定记录或物理块的存取访问与该物理块到磁头当前位置的距离有很大关系。如果相距甚远，则要花前位置的距离有很大关系。如果相距甚远，则要花费很长的存取时间来移动磁头。因此，如果按随机费很长的存取时间来移动磁头。因此，如果按随机方式或按键存取方式存取磁带上的文件信息的话，方式或按键存取方式存取磁带上的文件信息的话，其效率不会很高。但是，磁带存取设备具有容量大，其效率不会很高

61、。但是，磁带存取设备具有容量大，顺序存取方式时存取速度高等优点。因此，磁带存顺序存取方式时存取速度高等优点。因此，磁带存取设备获得了较为广泛的应用。取设备获得了较为广泛的应用。2. 直接存取设备直接存取设备 磁盘是最典型的直接存取设备。磁盘设备允许文件系磁盘是最典型的直接存取设备。磁盘设备允许文件系统直接存取磁盘上的任意物理块。为了存取一个特统直接存取磁盘上的任意物理块。为了存取一个特定的物理块，磁头将直接移动到所要求的位置上，定的物理块，磁头将直接移动到所要求的位置上，而不需要像顺序存取那样事先存取其他的物理块。而不需要像顺序存取那样事先存取其他的物理块。磁盘机一般由一些磁盘片组成的磁盘组组

62、成。其中每磁盘机一般由一些磁盘片组成的磁盘组组成。其中每个磁盘片对应一个装有个磁盘片对应一个装有 读读/写写 磁头的磁头臂，磁头磁头的磁头臂，磁头臂上的两个读臂上的两个读/写磁头分别对磁盘片的上下两面进写磁头分别对磁盘片的上下两面进行读写。系统在对磁盘进行初始化处理时，把每个行读写。系统在对磁盘进行初始化处理时，把每个磁盘片分割成一些大小相等的扇区。在磁盘转动时磁盘片分割成一些大小相等的扇区。在磁盘转动时经过读经过读/写写 磁头所形成的圆形轨迹称为磁道。由于磁头所形成的圆形轨迹称为磁道。由于磁头臂可沿半径方向移动，因此，磁盘上有多条磁磁头臂可沿半径方向移动，因此，磁盘上有多条磁道。道。另外，人

63、们通常把所有磁盘片的相同磁道称为一个柱另外，人们通常把所有磁盘片的相同磁道称为一个柱面，因此，磁盘上每个物理块的位置可用柱面号、面，因此，磁盘上每个物理块的位置可用柱面号、磁头号和扇区号表示，这些地址和物理块号一一对磁头号和扇区号表示，这些地址和物理块号一一对应。磁盘的结构如图应。磁盘的结构如图7.13所示。所示。图图7.13 磁盘的结构磁盘的结构7.4 文件存储空间管理文件存储空间管理存储空间管理是文件系统的重要任务之一。只有有效存储空间管理是文件系统的重要任务之一。只有有效地进行存储空间管理，才能保证多个用户共享文件地进行存储空间管理，才能保证多个用户共享文件存储设备和得以实现文件的按名存

64、取。由于文件存存储设备和得以实现文件的按名存取。由于文件存储设备是分成若干个大小相等的物理块，并以块为储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，文件存储空间的管理实单位来交换信息的，因此，文件存储空间的管理实质上是一个空闲块的组织和管理问题，它包括空闲质上是一个空闲块的组织和管理问题，它包括空闲块的组织，空闲块的分配与空闲块的回收等几个问块的组织，空闲块的分配与空闲块的回收等几个问题。题。有下述有下述3种不同的空闲块管理方法。它们是：种不同的空闲块管理方法。它们是：(1) 空闲文件目录空闲文件目录(2) 空闲块链空闲块链(3) 位示图位示图(1) 空闲文件目录空闲文件

65、目录最简单的空闲块管理方法就是把文件存储设备中的空最简单的空闲块管理方法就是把文件存储设备中的空闲块的块号统一放在一个称为空闲文件目录的物理闲块的块号统一放在一个称为空闲文件目录的物理块中。其中空闲文件目录的每个表项对应一个由多块中。其中空闲文件目录的每个表项对应一个由多个空闲块构成的空闲区，它包括空闲块个数，空闲个空闲块构成的空闲区，它包括空闲块个数，空闲块号和第一个空闲块号等。块号和第一个空闲块号等。在系统为某个文件分配空闲块时，首先扫描空闲文件在系统为某个文件分配空闲块时，首先扫描空闲文件目录项，如找到合适的空闲区项，则分配给申请者，目录项，如找到合适的空闲区项，则分配给申请者，并把该项

66、从空白文件目录中去调。如果一个空闲区并把该项从空白文件目录中去调。如果一个空闲区项不能满足申请者要求，则把目录中另一项分配给项不能满足申请者要求，则把目录中另一项分配给申请者申请者(连续文件结构除外连续文件结构除外)。如果一个空闲区项所。如果一个空闲区项所含块数超过申请者要求，则为申请者分配了所要的含块数超过申请者要求，则为申请者分配了所要的物理块之后，再修改该表项。物理块之后，再修改该表项。当一个文件被删除，释放存储物理块时，系统则把被当一个文件被删除，释放存储物理块时，系统则把被释放的块号、长度以及第一块块号置入空白目录文释放的块号、长度以及第一块块号置入空白目录文件的新表项中。件的新表项

67、中。显然，在内存管理时讨论过有关空闲连续区分配和释显然，在内存管理时讨论过有关空闲连续区分配和释放算法。只要稍加修改就可用于空闲文件项的分配放算法。只要稍加修改就可用于空闲文件项的分配和回收。和回收。空闲文件项方法适用于连续文件结构的文件存储区的空闲文件项方法适用于连续文件结构的文件存储区的分配与回收。分配与回收。(2) 空闲块链空闲块链空闲块链是一种较常用的空闲块管理方法。空闲块链空闲块链是一种较常用的空闲块管理方法。空闲块链把文件存储设备上的所有空闲块链接在一起，当申把文件存储设备上的所有空闲块链接在一起，当申请者需要空闲块时，分配程序从链头开始摘取所需请者需要空闲块时，分配程序从链头开始

68、摘取所需要的空闲块，然后调整链首指针。反之，当回收空要的空闲块，然后调整链首指针。反之，当回收空闲块时，把释放的空闲块逐个插入链尾上。闲块时，把释放的空闲块逐个插入链尾上。空闲块链的链接方法因系统而异，常用的链接方法有空闲块链的链接方法因系统而异，常用的链接方法有按空闲区大小顺序链接的方法；按释放先后顺序链按空闲区大小顺序链接的方法；按释放先后顺序链接的方法；以及按成组链接法。其中成组链接法可接的方法；以及按成组链接法。其中成组链接法可被看作空闲块链的链接法的扩展。被看作空闲块链的链接法的扩展。按空闲区大小顺序链接和按释放先后顺序链接的空闲按空闲区大小顺序链接和按释放先后顺序链接的空闲块管理在

69、增加或移动空闲块时需对空闲块链做较大块管理在增加或移动空闲块时需对空闲块链做较大的调整，因而需耗去一定的系统开销。成组链法在的调整，因而需耗去一定的系统开销。成组链法在空闲块的分配和回收方面要优于上述两种链接法。空闲块的分配和回收方面要优于上述两种链接法。成组链法首先把文件存储设备中的所有空闲块按成组链法首先把文件存储设备中的所有空闲块按50块块画分为一组。组的画分为从后往前顺次画分画分为一组。组的画分为从后往前顺次画分(如图如图7.14)。其中，每组的第一块用来存放前一组中各块。其中，每组的第一块用来存放前一组中各块的块号和总块数。由于第一组的前面已无其他组存的块号和总块数。由于第一组的前面

70、已无其他组存在，因此，第一组的块数为在，因此，第一组的块数为49块。不过，由于存储块。不过，由于存储设备的空间块不一定正好是设备的空间块不一定正好是50的整倍数，因而最后的整倍数，因而最后一组将不足一组将不足50块，且由于该组后面已无另外的空闲块，且由于该组后面已无另外的空闲块组，所以，该组的物理块号与总块数只能放在管块组，所以，该组的物理块号与总块数只能放在管理文件存储设备用的文件资源表中。理文件存储设备用的文件资源表中。图图7.14 成组链法的组织成组链法的组织在成组链法对文件设备进行了上述分组之后，系统可在成组链法对文件设备进行了上述分组之后，系统可根据申请者的要求进行空闲块的分配，并在

71、释放文根据申请者的要求进行空闲块的分配，并在释放文件时回收空闲块。下面我们介绍成组链法的分配和件时回收空闲块。下面我们介绍成组链法的分配和释放过程。释放过程。首先，系统在初启时把文件资源表复制到内存，从而首先，系统在初启时把文件资源表复制到内存，从而使文件资源表中放有最后一组空闲块块号与总块数使文件资源表中放有最后一组空闲块块号与总块数的堆栈进入内存，并使得空闲块的分配与释放可在的堆栈进入内存，并使得空闲块的分配与释放可在内存进行。减少了启动内存进行。减少了启动 I/O设备的压力。设备的压力。与空闲块块号及总块数相对应，用于空闲块分配与回与空闲块块号及总块数相对应，用于空闲块分配与回收的堆栈有

72、栈指针收的堆栈有栈指针 Ptr，且且 Ptr的初值等于该组空闲的初值等于该组空闲块的总块数。当申请者提出空闲块要求块的总块数。当申请者提出空闲块要求 n时，按照时，按照后进先出的原则，分配程序在取走后进先出的原则，分配程序在取走Ptr 所指的块号所指的块号之后，再做之后，再做PtrPtr-1 的操作。这个过程一直持续的操作。这个过程一直持续到所要求的到所要求的n块都已分配完毕或堆栈中只剩下最后块都已分配完毕或堆栈中只剩下最后一个空闲块的块号。当堆栈中只剩下最后一个空闲一个空闲块的块号。当堆栈中只剩下最后一个空闲块号时，系统启动设备管理程序，将该块中存放的块号时，系统启动设备管理程序，将该块中存

73、放的下一组的块号与总块数读入内存之后将该块分配给下一组的块号与总块数读入内存之后将该块分配给申请者。然后，系统重新设置申请者。然后，系统重新设置Ptr指针，并继续为申指针，并继续为申请者进程分配空闲块。请者进程分配空闲块。文件存储设备的最后一个空闲块中设置有尾部标识，文件存储设备的最后一个空闲块中设置有尾部标识，以指示空闲块分配完毕。以指示空闲块分配完毕。如果用户进程不再使用有关文件并删除这些文件时，如果用户进程不再使用有关文件并删除这些文件时，回收程序回收装有这些文件的物理块。成组链法的回收程序回收装有这些文件的物理块。成组链法的回收过程仍利用文件管理堆栈进行回收。在回收时，回收过程仍利用文

74、件管理堆栈进行回收。在回收时，回收程序先做回收程序先做PtrPtr+1操作，然后把回收的物理操作，然后把回收的物理块号放入当前指针块号放入当前指针Ptr所指的位置。如果所指的位置。如果 Ptr等于等于50，则表示该组已经回收结束。此时，如果还有新的，则表示该组已经回收结束。此时，如果还有新的物理块需要回收的话，回收该块并启动物理块需要回收的话，回收该块并启动I/O设备管设备管理程序，把回收的理程序，把回收的50个块号与块数写入新回收的块个块号与块数写入新回收的块中。然后，将中。然后，将Ptr重新置重新置1另起一个新组。另起一个新组。显然，对空闲块的分配和释放必须互斥进行，否则将显然，对空闲块的

75、分配和释放必须互斥进行，否则将会发生数据混乱。会发生数据混乱。(3) 位示图位示图空闲文件目录和空闲块链法在分配和回收空闲块时，空闲文件目录和空闲块链法在分配和回收空闲块时，都需在文件存储设备上查找空闲文件目录项或链接都需在文件存储设备上查找空闲文件目录项或链接块号，这必须经过设备管理程序启动外设才能完成。块号，这必须经过设备管理程序启动外设才能完成。为提高空闲块的分配回收速度，用位示图进行管理。为提高空闲块的分配回收速度，用位示图进行管理。系统首先从内存中画出若干个字节，为每个文件存储系统首先从内存中画出若干个字节，为每个文件存储设备建立一张位示图。这张位示图反映每个文件存设备建立一张位示图

76、。这张位示图反映每个文件存储设备的使用情况。在位示图中，每个文件存储设储设备的使用情况。在位示图中，每个文件存储设备的物理块都对应一个比特位。如果该位为备的物理块都对应一个比特位。如果该位为“0”，则表示所对应的块是空闲块；反之，如果该位为，则表示所对应的块是空闲块；反之，如果该位为“1”，则表示所对应的块已被分配出去。，则表示所对应的块已被分配出去。利用位示图来进行空闲块分配时，只需查找图中的利用位示图来进行空闲块分配时，只需查找图中的“ 0”位，并将其置为位，并将其置为“1”位。反之，利用位示图回位。反之，利用位示图回收时只需把相应的比特位由收时只需把相应的比特位由“ 1”改为改为“ 0”

77、即即 可。可。 7.5 文件目录管理文件目录管理为了实现对文件的按名存取，首先，每个文件必须有为了实现对文件的按名存取，首先，每个文件必须有一个文件名与其对应。一般用户文件名由用户指定，一个文件名与其对应。一般用户文件名由用户指定，系统文件和特殊文件在系统设计时指定。系统文件和特殊文件在系统设计时指定。必须把文件名及其结构信息等按一定的组织结构排列，必须把文件名及其结构信息等按一定的组织结构排列，以方便文件的搜索。把文件名和对该文件实施控制以方便文件的搜索。把文件名和对该文件实施控制管理的控制管理信息称为该文件的文件说明，并把管理的控制管理信息称为该文件的文件说明，并把一个文件说明按一定的逻辑

78、结构存放到物理存储块一个文件说明按一定的逻辑结构存放到物理存储块的一个表目中。利用文件说明信息，可以完成对文的一个表目中。利用文件说明信息，可以完成对文件的创建、检索以及维护作用。因此，把一个文件件的创建、检索以及维护作用。因此，把一个文件的文件说明信息称为该文件的目录。对文件目录的的文件说明信息称为该文件的目录。对文件目录的管理就是对文件说明信息的管理。管理就是对文件说明信息的管理。文件目录的管理要解决存储空间的有效利用，还要解文件目录的管理要解决存储空间的有效利用，还要解决快速搜索、文件命名冲突、以及文件共享问题。决快速搜索、文件命名冲突、以及文件共享问题。7.5.1 文件的组成文件的组成

79、从文件管理角度看，一个文件包括两部分：文件说明从文件管理角度看，一个文件包括两部分：文件说明和文件体。和文件体。文件体指文件本身的信息，它可能是前面各节讨论的文件体指文件本身的信息，它可能是前面各节讨论的记录式文件或字符流式文件。记录式文件或字符流式文件。文件说明有时也叫文件控制块文件说明有时也叫文件控制块(FCB)，它至少包括文它至少包括文件名、与件名、与(物理结构是连续结构时物理结构是连续结构时)文件名相对应的文件名相对应的文件内部标识以及文件信息在文件存储设备上第一文件内部标识以及文件信息在文件存储设备上第一个物理块的地址（物理结构是边连续结构时）。另个物理块的地址（物理结构是边连续结构

80、时）。另外，根据系统要求不同，它还包括关于文件逻辑结外，根据系统要求不同，它还包括关于文件逻辑结构、物理结构、存取控制和管理信息等。这里的管构、物理结构、存取控制和管理信息等。这里的管理信息主要指访问时间、以及记账信息等。理信息主要指访问时间、以及记账信息等。文件说明组成目录文件。文件系统利用目录文件完成文件说明组成目录文件。文件系统利用目录文件完成按名存取和对文件信息的共享与保护。按名存取和对文件信息的共享与保护。7.5.2 文件目录文件目录文件目录可分为单级目录、二级目录和多级目录。文件目录可分为单级目录、二级目录和多级目录。单级目录是一种最简单、最原始的目录结构。如果文单级目录是一种最简

81、单、最原始的目录结构。如果文件系统为存储设备的所有文件建立一张目录表，每件系统为存储设备的所有文件建立一张目录表，每个文件在其中占有一项用来存放文件说明信息。该个文件在其中占有一项用来存放文件说明信息。该目录表存放在存储设备的某固定区域，在系统初启目录表存放在存储设备的某固定区域，在系统初启时或需要时，系统将其调入内存，时或需要时，系统将其调入内存，(或部分调入内或部分调入内存存)。文件系统通过对该表提供的信息对文件进行。文件系统通过对该表提供的信息对文件进行创建、搜索、删除等操作。创建、搜索、删除等操作。利用单级目录，文件系统就可实现对文件系统空间的利用单级目录，文件系统就可实现对文件系统空

82、间的自动管理和按名存取。单级目录时的文件系统读写自动管理和按名存取。单级目录时的文件系统读写处理过程如图处理过程如图7.15。图图7.15 单级目录的读写处理过程单级目录的读写处理过程不过，由于在单级目录表中，各文件说明项都处于平不过，由于在单级目录表中，各文件说明项都处于平等地位，只能按连续结构或顺序结构存放。如果两等地位，只能按连续结构或顺序结构存放。如果两个不同的文件重名的话，则系统将把它们视为同一个不同的文件重名的话，则系统将把它们视为同一文件。另外，由于单级目录必须对单级目录表中所文件。另外，由于单级目录必须对单级目录表中所有文件信息项进行搜索，因而，搜索效率也较低。有文件信息项进行

83、搜索，因而，搜索效率也较低。为了改变单级目录中文件命名冲突问题和提高对目录为了改变单级目录中文件命名冲突问题和提高对目录表的搜索速度，单级目录被扩充成二级目录。表的搜索速度，单级目录被扩充成二级目录。二级目录结构中，各个文件的说明信息被组织成目录二级目录结构中，各个文件的说明信息被组织成目录文件，且以用户为单位把各自的文件说明画分为不文件，且以用户为单位把各自的文件说明画分为不同的组。然后，这些不同的组名有关存取控制信息同的组。然后，这些不同的组名有关存取控制信息存放在存放在OK主目录主目录(MFD)的目录项中。与主目录的目录项中。与主目录 MFD相对应，用户文件的文件说明所组成的目录相对应，

84、用户文件的文件说明所组成的目录文件被称为用户文件目录文件被称为用户文件目录(UFD)。这样，由这样，由MFD和和UFD就形成二级目录。二级目录的结构如图就形成二级目录。二级目录的结构如图7.16。图图7.16 二级目录结构二级目录结构当用户要对一个文件进行存取操作或创建、删除一个当用户要对一个文件进行存取操作或创建、删除一个文件时，首先从文件时，首先从 MFD找到对应的目录名，并从用找到对应的目录名，并从用户名查找到该用户的户名查找到该用户的 MFD。余下的操作与单级目余下的操作与单级目录时相同。录时相同。使用二级目录可以解决文件重名和文件共享问题，并使用二级目录可以解决文件重名和文件共享问题

85、，并可获得较高的搜索速度。由于二级目录时首先从主可获得较高的搜索速度。由于二级目录时首先从主目录目录 MFD开始搜索，因此，从系统管理的角度来开始搜索，因此，从系统管理的角度来看，文件名已演变成为用户名看，文件名已演变成为用户名 /用户文件名。从而，用户文件名。从而，即使两个不同的用户具有同名文件，系统也会把它即使两个不同的用户具有同名文件，系统也会把它们区别开来。再者，利用二级目录，也可以方便地们区别开来。再者，利用二级目录，也可以方便地解决不同用户间的文件共享问题，这只要在被共享解决不同用户间的文件共享问题，这只要在被共享的文件说明信息中增加相应的共享管理项和把共享的文件说明信息中增加相应

86、的共享管理项和把共享文件的文件说明项指向被共享文件的文件说明项即文件的文件说明项指向被共享文件的文件说明项即可。可。另外，与单级目录相比，如果单级目录表的长度为另外，与单级目录相比，如果单级目录表的长度为 n的话，则单级目录时的搜索时间与的话，则单级目录时的搜索时间与 n成正比成正比; 在二在二级目录时，由于的目录已被画分为个子集，则级目录时，由于的目录已被画分为个子集，则二级目录的搜索时间是与成正比的。这里的二级目录的搜索时间是与成正比的。这里的是用户个数，是每个用户的文件的个数。一般是用户个数，是每个用户的文件的个数。一般有有，从而二级目录的搜索时间要快于单，从而二级目录的搜索时间要快于单

87、级目录。级目录。把二级目录的层次关系加以推广，就形成了多级目录。把二级目录的层次关系加以推广，就形成了多级目录。在多级目录结构中，除了最低一级的物理块中装有在多级目录结构中，除了最低一级的物理块中装有文件信息外，其他每一级目录中存放的都是下一级文件信息外，其他每一级目录中存放的都是下一级目录或文件的说明信息。由此形成层次关系，最高目录或文件的说明信息。由此形成层次关系，最高层为根目录，最低层为文件。多级目录构成树形结层为根目录，最低层为文件。多级目录构成树形结构，如图构，如图7.17所示。所示。图图7.17 文件系统的树形结构文件系统的树形结构树形结构多级目录结构具有下列特点：树形结构多级目录

88、结构具有下列特点：(1) 层次清楚。由于分支结构，不同性质、不同用户层次清楚。由于分支结构，不同性质、不同用户的文件可以构成不同的子树，便于管理。不同层次、的文件可以构成不同的子树，便于管理。不同层次、不同用户的文件可以被赋予不同的存取权限，有利不同用户的文件可以被赋予不同的存取权限，有利于文件的保护。于文件的保护。(2) 解决了文件重名问题。文件在系统中的搜索路径解决了文件重名问题。文件在系统中的搜索路径是从根开始到文件名为止的各文件名组成，因此，是从根开始到文件名为止的各文件名组成，因此，只要在同一子目录下的文件名不发生重复，就不会只要在同一子目录下的文件名不发生重复，就不会由文件重名而引

89、起混乱。由文件重名而引起混乱。(3) 查找搜索速度快。在查找搜索速度快。在7.2节讨论的对文件中键名的节讨论的对文件中键名的各种搜索方法各种搜索方法,例如线性搜索法例如线性搜索法,散列法以及二分搜散列法以及二分搜索法都可用来对各级目录进行查找。由于对多级目索法都可用来对各级目录进行查找。由于对多级目录的查找每次只查找目录的一个子集，因此，其搜录的查找每次只查找目录的一个子集，因此，其搜索速度较单级、二级目录时更快。索速度较单级、二级目录时更快。7.5.3 便于共享的文件目录便于共享的文件目录文件系统的一个重要任务就是为用户提供共享文件信文件系统的一个重要任务就是为用户提供共享文件信息的手段。这

90、是因为对于某一个公用文件来说，如息的手段。这是因为对于某一个公用文件来说，如果每个用户都在文件系统内保留一份该文件的副本，果每个用户都在文件系统内保留一份该文件的副本，这将极大地浪费存储空间。如果系统提供了共享文这将极大地浪费存储空间。如果系统提供了共享文件信息的手段，则在文件存储设备上只需存储一个件信息的手段，则在文件存储设备上只需存储一个文件副本，共享该文件的用户以自己的文件名去访文件副本，共享该文件的用户以自己的文件名去访问该文件的副本就可以了。问该文件的副本就可以了。从系统管理的观点看，有三种方法可以实现文件共享。从系统管理的观点看，有三种方法可以实现文件共享。即：即：(1) 绕道法绕

91、道法(2) 链接法链接法(3) 基本文件目录表基本文件目录表 BFD绕道法要求每个用户处在当前目录下工作，用户对所绕道法要求每个用户处在当前目录下工作，用户对所有文件的访问都是相对于当前目录进行的。用户文有文件的访问都是相对于当前目录进行的。用户文件的固有名件的固有名(为了访问某个文件而必须访问的各个为了访问某个文件而必须访问的各个目录和文件的目录名与文件名的顺序连接称为固有目录和文件的目录名与文件名的顺序连接称为固有名名) 是由当前目录到信息文件通路上所有各级目录是由当前目录到信息文件通路上所有各级目录的目录名加上该信息文件的符号名组成。使用绕道的目录名加上该信息文件的符号名组成。使用绕道法

92、进行文件共享时，用户从当前目录出发向上返回法进行文件共享时，用户从当前目录出发向上返回到与所要共享文件所在路径的交叉点，再顺序下访到与所要共享文件所在路径的交叉点，再顺序下访到共享文件。绕道法需要用户指定所要共享文件的到共享文件。绕道法需要用户指定所要共享文件的逻辑位置或到达被共享文件的路径。绕道法的原理逻辑位置或到达被共享文件的路径。绕道法的原理如图如图7.18所示。所示。图图7.18 绕道法绕道法绕道法要绕弯路访问多级目录，搜索效率不高。为了绕道法要绕弯路访问多级目录，搜索效率不高。为了提高共享其它目录中文件的速度，另一种共享的办提高共享其它目录中文件的速度，另一种共享的办法是在相应目录表

93、之间进行链接。即将一个目录中法是在相应目录表之间进行链接。即将一个目录中的链指针直接指向被共享文件所在的目录。链接法的链指针直接指向被共享文件所在的目录。链接法仍然需要用户指定被共享的文件和被链接的目录。仍然需要用户指定被共享的文件和被链接的目录。实现文件共享的一种有效方法是采用基本文件目录表实现文件共享的一种有效方法是采用基本文件目录表 BFD的方法。该方法把所有文件目录的内容分成两的方法。该方法把所有文件目录的内容分成两部分：一部分包括文件的结构信息、物理块号、存部分：一部分包括文件的结构信息、物理块号、存取控制和管理信息等，并由系统赋予唯一的内部标取控制和管理信息等，并由系统赋予唯一的内

94、部标识符来标识；另一部分则由用户给出的符号名和系识符来标识；另一部分则由用户给出的符号名和系统赋给文件说明信息的内部标识符组成。这两部分统赋给文件说明信息的内部标识符组成。这两部分分别称为符号文件目录表分别称为符号文件目录表(SFD)和基本文件目录表和基本文件目录表(BFD)。SFD中存放文件名和文件内部标识符，中存放文件名和文件内部标识符，BFD中存放除了文件名之外的文件说明信息和文件中存放除了文件名之外的文件说明信息和文件的内部标识符。这样组成的多级目录结构如图的内部标识符。这样组成的多级目录结构如图7.19。图图7.19 采用基本文件目录的多级目录结构采用基本文件目录的多级目录结构在图在

95、图7.19中，为了简单起见，未在中，为了简单起见，未在 BFD表项中列出结表项中列出结构信息、存取控制信息和管理控制信息等。另外，构信息、存取控制信息和管理控制信息等。另外，在文件系统中，系统通常预先规定赋予基本文件目在文件系统中，系统通常预先规定赋予基本文件目录、空白文件目录、主目录录、空白文件目录、主目录 MFD的符号文件目录的符号文件目录固定不变的唯一标识符，在图中它们分别为固定不变的唯一标识符，在图中它们分别为 0,1,2。采用基本文件目录方式可较方便地实现文件共享。如采用基本文件目录方式可较方便地实现文件共享。如果用户要共享某个文件，则只需给出被共享的文件果用户要共享某个文件，则只需

96、给出被共享的文件名，系统就会自动在名，系统就会自动在SDF的有关文件处生成与被共的有关文件处生成与被共享文件相同的内部标识符享文件相同的内部标识符id,例如在图例如在图7.19中，用户中，用户Wang和和Zhang共享标识符为共享标识符为6的文件，对于系统来的文件，对于系统来说，标识符说，标识符6指向同一个文件；而对指向同一个文件；而对Wang和和Zhang两用户来说两用户来说,则对应于不同的文件名则对应于不同的文件名b.c和和f.c。7.5.4 目录管理目录管理存放文件说明信息或目录管理说明信息的目录项构成存放文件说明信息或目录管理说明信息的目录项构成目录文件，这些文件同样存放在文件存储设备

97、中。目录文件，这些文件同样存放在文件存储设备中。在存取一个文件时，必须访问多级目录。如果访问在存取一个文件时，必须访问多级目录。如果访问每级目录时都必须到文件存储设备上去搜索，浪费每级目录时都必须到文件存储设备上去搜索，浪费CPU处理时间、降低了处理速度，给输入输出设备处理时间、降低了处理速度，给输入输出设备增加了负担。一种解决办法是在系统初启时，把所增加了负担。一种解决办法是在系统初启时，把所有的目录文件读入内存，由文件系统在内存完成对有的目录文件读入内存，由文件系统在内存完成对各级目录的搜索。这种方法需要大量的内存支持。各级目录的搜索。这种方法需要大量的内存支持。显然是不可取的。另一种折中

98、的方法是：把当前正显然是不可取的。另一种折中的方法是：把当前正在使用的那些文件的目录表目复制到内存中。为此，在使用的那些文件的目录表目复制到内存中。为此，系统提供两种特殊的操作把有关的目录文件复制到系统提供两种特殊的操作把有关的目录文件复制到内存的指定区；以及当用户不再访问有关信息文件内存的指定区；以及当用户不再访问有关信息文件时删去有关目录文件的内存副本。时删去有关目录文件的内存副本。把文件存储设备上的目录文件复制到内存的操作称为把文件存储设备上的目录文件复制到内存的操作称为打开文件打开文件(fopen)，而把删除文件的内存副本的操而把删除文件的内存副本的操作称为关闭文件作称为关闭文件(fc

99、lose)。这两个操作一般以系统这两个操作一般以系统调用的方式提供。对于按调用的方式提供。对于按BDF和和SDF方式排列的多方式排列的多级文件目录来说，系统按以下方式打开一个文件。级文件目录来说，系统按以下方式打开一个文件。(1) 把主目录把主目录 MFD中的相应表目，也就是与待打开中的相应表目，也就是与待打开文件相联系的有关表目复制到内存。例如，若准备文件相联系的有关表目复制到内存。例如，若准备打开图打开图7.19中的文件中的文件a.c，则将则将 MFD中的第一项中的第一项(Wang)复制到内存。复制到内存。(2) 根据根据(1)所复制得到的标识符，再复制此标识符所复制得到的标识符，再复制此

100、标识符所指明的基本文件目录表所指明的基本文件目录表BDF 的有关表目。例如图的有关表目。例如图7.19中的中的id=3的的BDF中表目项。这个表目中包括有中表目项。这个表目中包括有存取控制信息、结构信息以及下级目录的物理块号存取控制信息、结构信息以及下级目录的物理块号等。等。(3) 根据根据(2)所得到的子目录说明信息搜索所得到的子目录说明信息搜索SFD，以以找到与待打开文件相对应的目录表项。如果找到的找到与待打开文件相对应的目录表项。如果找到的表目仍然是子目录名，则系统将根据其对应的标识表目仍然是子目录名，则系统将根据其对应的标识符符id，继续上述复制过程，直到所找到的表目是待继续上述复制过

101、程，直到所找到的表目是待打开的文件名。例如在图打开的文件名。例如在图7.19中文件名中文件名a.c。(4) 根据根据(3)所搜索到的文件名所对应的标识符所搜索到的文件名所对应的标识符id，把相应的把相应的BDF 的表目项复制到内存。这样，待打开的表目项复制到内存。这样，待打开文件的说明信息就已复制到了内存中。由复制的文文件的说明信息就已复制到了内存中。由复制的文件说明，系统显然可以方便地得到文件的有关物理件说明，系统显然可以方便地得到文件的有关物理块号。从而，系统可对文件进行有关操作。块号。从而，系统可对文件进行有关操作。在完成了上述个步骤之后，就说文件是被打开的了。在完成了上述个步骤之后，就

102、说文件是被打开的了。称这样的文件为打开的文件或活动文件。而且，把称这样的文件为打开的文件或活动文件。而且，把内存中存放活动文件的内存中存放活动文件的 SFD表目的表称为活动名字表目的表称为活动名字表，这个表每个用户一张。另外，把内存中存放活表，这个表每个用户一张。另外，把内存中存放活动文件的动文件的 BFD表目的表称为活动文件表，这个表整表目的表称为活动文件表，这个表整个系统一张。个系统一张。7.6 文件存取控制文件存取控制 本节介绍文件的存取控制问题。文件的存取控制是本节介绍文件的存取控制问题。文件的存取控制是和文件的共享、保护和保密三个不同而又相互联系和文件的共享、保护和保密三个不同而又相

103、互联系的问题紧密相关的。的问题紧密相关的。文件的共享是指不同的用户共同使用一个文件。文件的共享是指不同的用户共同使用一个文件。文件保护则指文件本身需要防止文件的拥有者本人或文件保护则指文件本身需要防止文件的拥有者本人或其他用户破坏文件内容。其他用户破坏文件内容。文件保密指未经文件拥有者许可，任何用户不得访问文件保密指未经文件拥有者许可，任何用户不得访问该文件。该文件。这三个问题实际上是一个用户对文件的使用权限，即这三个问题实际上是一个用户对文件的使用权限，即读、写、执行的许可权问题。读、写、执行的许可权问题。具体地说，文件系统的存取控制部分应做到：具体地说，文件系统的存取控制部分应做到：(1)

104、 对于拥有读、写或执行权限的用户，应让其对文对于拥有读、写或执行权限的用户，应让其对文件进行相应的操作。件进行相应的操作。(2) 对于没有读、写或执行权限的用户，应禁止他们对于没有读、写或执行权限的用户，应禁止他们对文件进行相应的操作。对文件进行相应的操作。(3) 应防止一个用户冒充其他用户对文件进行存取。应防止一个用户冒充其他用户对文件进行存取。(4) 应防止拥有存取权限的用户误用文件。应防止拥有存取权限的用户误用文件。这些功能是由一组称为存取控制验证模块的程序提供这些功能是由一组称为存取控制验证模块的程序提供的。它们分三步验证用户的存取操作。的。它们分三步验证用户的存取操作。(1) 审定用

105、户的存取权限。审定用户的存取权限。(2) 比较用户权限的本次存取要求是否一致。比较用户权限的本次存取要求是否一致。(3) 将存取要求和被访问文件的保密性比较，看是否将存取要求和被访问文件的保密性比较，看是否有冲突。有冲突。可有下述个方式来验证用户的存取操作可有下述个方式来验证用户的存取操作,它们是：它们是：(1) 存取控制矩阵存取控制矩阵;(2) 存取控制表存取控制表;(3) 口令口令;(4) 密码术。密码术。系统设计人员根据需要选择其中一种或几种并将相应系统设计人员根据需要选择其中一种或几种并将相应的数据结构置于文件说明的数据结构置于文件说明(BFD等等)中，在用户访问中，在用户访问存取文件

106、时，对用户的存取权限、存取要求的一致存取文件时，对用户的存取权限、存取要求的一致性以及保密性等进行验证。性以及保密性等进行验证。(1) 存取控制矩阵存取控制矩阵存取控制矩阵方式以一个二维矩阵来进行存取控制。存取控制矩阵方式以一个二维矩阵来进行存取控制。二维矩阵的一维是所有的用户，另一维是所有的文二维矩阵的一维是所有的用户，另一维是所有的文件。对应的矩阵元素则是用户对文件的存取控制权，件。对应的矩阵元素则是用户对文件的存取控制权，包括读，写，和执行。如图包括读，写，和执行。如图7.20所示。所示。图图7.20 存取控制矩阵存取控制矩阵当用户向文件系统提出存取要求时，由存取控制验证当用户向文件系统

107、提出存取要求时，由存取控制验证模块根据该矩阵内容对本次存取要求进行比较，如模块根据该矩阵内容对本次存取要求进行比较，如果不匹配的话，系统拒绝执行。果不匹配的话，系统拒绝执行。当文件和用户较多时，存取控制矩阵将变得非常庞大，当文件和用户较多时，存取控制矩阵将变得非常庞大，这无论是在占用内存空间的大小上，还是在为使用这无论是在占用内存空间的大小上，还是在为使用文件而对矩阵进行扫描的时间开销上都是不合适的。文件而对矩阵进行扫描的时间开销上都是不合适的。因此，在实现时往往采取某些辅助措施以减少时间因此，在实现时往往采取某些辅助措施以减少时间和空间的开销。和空间的开销。(2) 存取控制表存取控制表存取控

108、制表以文件为单位，把用户按某种关系画分为存取控制表以文件为单位，把用户按某种关系画分为若干组，同时规定每组的存取权限。这样，所有用若干组，同时规定每组的存取权限。这样，所有用户组对文件权限的集合就形成了该文件的存取控制户组对文件权限的集合就形成了该文件的存取控制表，如图表，如图7.21所示。所示。图图7.21 存取控制表存取控制表每个文件都有一张存取控制表。在实现时，该表存放每个文件都有一张存取控制表。在实现时，该表存放在文件说明中，也就是在文件说明中，也就是BFD 的有关表目中。文件被的有关表目中。文件被打开时打开时,由于存取控制表也相应地被复制到了内存由于存取控制表也相应地被复制到了内存活

109、动文件中活动文件中,因此因此,存取控制验证能高效进行。存取控制验证能高效进行。(3) 口令方式口令方式口令方式有两种。一种是当用户进入系统，为建立终口令方式有两种。一种是当用户进入系统，为建立终端进程时获得系统使用权的口令。另一种口令方式端进程时获得系统使用权的口令。另一种口令方式是，每个用户在创建文件时，为每一个创建的文件是，每个用户在创建文件时，为每一个创建的文件设置一个口令，且将其置于文件说明中。显然，口设置一个口令，且将其置于文件说明中。显然，口令只有设置者自己知道，若允许其他用户使用自己令只有设置者自己知道，若允许其他用户使用自己的文件，口令设置者可将口令赋予其他用户。这样，的文件，

110、口令设置者可将口令赋予其他用户。这样，既可以做到文件共享，又可做到保密。而且，由于既可以做到文件共享，又可做到保密。而且，由于口令较为简单，占用的内存单元以及验证口令所费口令较为简单，占用的内存单元以及验证口令所费时间都将非常少。不过，相对来说，口令方式保密时间都将非常少。不过，相对来说，口令方式保密性能较差。再者，当要修改某个用户的存取权限时，性能较差。再者，当要修改某个用户的存取权限时，文件主必须修改口令，这样，所有共享该文件的用文件主必须修改口令，这样，所有共享该文件的用户的存取权限都被取消，除非文件主将新的口令通户的存取权限都被取消，除非文件主将新的口令通知用户。知用户。(4) 密码方

111、式密码方式防止文件泄密以及控制存取访问的的另一种方法是密防止文件泄密以及控制存取访问的的另一种方法是密码方式。密码方式在用户创建源文件并将其写入存码方式。密码方式在用户创建源文件并将其写入存储设备时对文件进行编码加密，在读出文件时对其储设备时对文件进行编码加密，在读出文件时对其进行译码解密。显然，只有能够进行译码解密的用进行译码解密。显然，只有能够进行译码解密的用户才能读出被加密的文件信息，从而起到文件保密户才能读出被加密的文件信息，从而起到文件保密的作用。的作用。文件的加密和解密都需要用户提供一个代码键文件的加密和解密都需要用户提供一个代码键(KEY)。加密程序根据这一代码键对用户文件进行编

112、码变换，加密程序根据这一代码键对用户文件进行编码变换，然后将其写入存储设备。在读取文件时，只有用户然后将其写入存储设备。在读取文件时，只有用户给定的代码键与加密时的代码键相一致时，解密程给定的代码键与加密时的代码键相一致时，解密程序才能对加密文件进行解密，将其还原为源文件。序才能对加密文件进行解密，将其还原为源文件。加密处理过程如图加密处理过程如图7.22所示。所示。图图7.22 加密解密过程加密解密过程加密方式具有保密性强的优点，因为与口令不同，进加密方式具有保密性强的优点，因为与口令不同，进行编码解码的代码键没有存放在系统中，而是由用行编码解码的代码键没有存放在系统中，而是由用户自己掌握的

113、。但是，由于编码解码工作要耗费大户自己掌握的。但是，由于编码解码工作要耗费大量的处理时间，因此，加密技术是以牺牲系统开销量的处理时间，因此，加密技术是以牺牲系统开销为代价的。为代价的。7.7 文件的使用文件的使用本节讨论文件系统对用户的接口。本节讨论文件系统对用户的接口。文件系统以系统调用方式或命令方式为用户提供下列文件系统以系统调用方式或命令方式为用户提供下列几类服务：几类服务：(1) 关于设置和修改用户对文件的存取权限的服务关于设置和修改用户对文件的存取权限的服务;(2) 关于建立、改变和删除目录的服务关于建立、改变和删除目录的服务;(3) 关于文件共享、设置访问路径的服务关于文件共享、设

114、置访问路径的服务;(4) 创建、打开、读写、关闭，及撤消文件的服务。创建、打开、读写、关闭，及撤消文件的服务。这些服务的调用名和参数都因系统不同而异。这些服务的调用名和参数都因系统不同而异。有关对文件操作的命令都基于操作系统提供的系统调有关对文件操作的命令都基于操作系统提供的系统调用。这些系统调用包括建立文件用的用。这些系统调用包括建立文件用的 creat，读文读文件用的件用的 read，关闭文件用的关闭文件用的close以及撤消文件用的以及撤消文件用的 delete 等。等。其中其中，creat 调用将根据用户提供的文件名和属性调用将根据用户提供的文件名和属性,在在指定的文件存储设备上建立一

115、个文件并把文件标识指定的文件存储设备上建立一个文件并把文件标识符返回给用户。而符返回给用户。而open调用则把在文件存储设备上调用则把在文件存储设备上的有关文件说明信息复制到内存的活动文件目录表的有关文件说明信息复制到内存的活动文件目录表中。中。write 调用将把从内存中某个位置开始的一段调用将把从内存中某个位置开始的一段字节长字节长(字符流文件时字符流文件时) 信息或个记录经设备管信息或个记录经设备管理程序写入文件存储设备。理程序写入文件存储设备。read调用的功能与调用的功能与 write相反，它把指定文件的几个字节或记录读入内相反，它把指定文件的几个字节或记录读入内存中指定地区。若文件

116、暂时不用时，系统调用存中指定地区。若文件暂时不用时，系统调用 close关闭该文件。关闭该文件。close 调用撤消活动文件表中相调用撤消活动文件表中相应表目。应表目。delete调用则在一个文件不再被访问时，调用则在一个文件不再被访问时，删除该文件在文件存储设备上的有关说明信息，并删除该文件在文件存储设备上的有关说明信息，并释放该文件所占据的全部存储空间。释放该文件所占据的全部存储空间。7.8 文件系统的层次模型文件系统的层次模型这一节将介绍文件系统的一般层次模型。这一节将介绍文件系统的一般层次模型。操作系统的层次结构的设计方法是操作系统的层次结构的设计方法是Dijkstra于于1967年年

117、提出的，提出的，1968年年Madnick将这一思想引入了文件系将这一思想引入了文件系统。层次结构法的优点是，可以按照系统所提供的统。层次结构法的优点是，可以按照系统所提供的功能来画分为各种不同的层次，下层为上层提供服功能来画分为各种不同的层次，下层为上层提供服务，上层使用下层的功能。这样，上下层之间彼此务，上层使用下层的功能。这样，上下层之间彼此无需了解对方的内部结构和实现方法，而只关心二无需了解对方的内部结构和实现方法，而只关心二者的接口。从而，一个看上去十分复杂的系统将会者的接口。从而，一个看上去十分复杂的系统将会由于层次的画分而变得易于设计、易于理解和易于由于层次的画分而变得易于设计、

118、易于理解和易于实现。而且，当系统出现错误时，也容易进行查错实现。而且，当系统出现错误时，也容易进行查错和调整。因此，层次化设计方法也使得系统的管理和调整。因此，层次化设计方法也使得系统的管理和维护更加容易。和维护更加容易。层次的画分是一个十分复杂的问题。如果层次画分太层次的画分是一个十分复杂的问题。如果层次画分太少，分层的意义不明显。若层次画分太多，则各层少，分层的意义不明显。若层次画分太多，则各层之间传递的参数会急剧增加，而且每一层的处理会之间传递的参数会急剧增加，而且每一层的处理会占去一定的系统开销，从而影响系统效率。因此，占去一定的系统开销，从而影响系统效率。因此，层次的画分要根据实际需

119、要仔细地考虑。层次的画分要根据实际需要仔细地考虑。Madnick 把文件系统画分为把文件系统画分为8层，如图层，如图7.23所示。所示。在图在图7.23中，第中，第1层是用户接口，该层根据用户对文层是用户接口，该层根据用户对文件的存取要求，把不同的系统调用加工改造成不同件的存取要求，把不同的系统调用加工改造成不同的内部调用格式。的内部调用格式。第第2层符号文件系统层。该层完成第层符号文件系统层。该层完成第1层所提供的功能，层所提供的功能，并把第并把第1层所提供的参数层所提供的参数用户文件名转换成系用户文件名转换成系统内部的唯一标识符统内部的唯一标识符fd，该层的主要工作是搜索文该层的主要工作是

120、搜索文件目录，也就是搜索件目录，也就是搜索 SFD，以找到相应文件名的表以找到相应文件名的表目以找到目以找到fd。然后，然后，fd将作为参数传给第将作为参数传给第3层。层。图图7.23 文件系统的层次模型文件系统的层次模型第第3层是基本文件系统层。该层根据第层是基本文件系统层。该层根据第2层的调用参数层的调用参数fd，找到文件的说明信息，包括存取控制表、文件找到文件的说明信息，包括存取控制表、文件逻辑结构、物理结构以及第一个物理块地址等。逻辑结构、物理结构以及第一个物理块地址等。第第4层是存取控制验证层。该层的主要功能是根据存层是存取控制验证层。该层的主要功能是根据存取控制信息和用户访问要求，

121、检验文件访问的合法取控制信息和用户访问要求，检验文件访问的合法性，从而实现文件的共享、保护和保密。性，从而实现文件的共享、保护和保密。第第5层是逻辑文件系统层。该层的主要功能是根据文层是逻辑文件系统层。该层的主要功能是根据文件的逻辑结构，找到所要进行操作的数据或记录的件的逻辑结构，找到所要进行操作的数据或记录的相对块号。对于字符流的无结构文件来说，只要把相对块号。对于字符流的无结构文件来说，只要把用户指定的逻辑地址按块长换算成相对块号就可以用户指定的逻辑地址按块长换算成相对块号就可以了。但是，对于记录式有结构文件来说，由于用户了。但是，对于记录式有结构文件来说，由于用户有时指定的是键名或记录名

122、，因此，需首先由键名有时指定的是键名或记录名，因此，需首先由键名(或记录名或记录名) 搜索到相应的记录并得到对应的逻辑地搜索到相应的记录并得到对应的逻辑地址之后，再将其转换为相对块号。址之后，再将其转换为相对块号。第第6层是物理文件系统层。该层把相对块号根据文件层是物理文件系统层。该层把相对块号根据文件的物理结构转换成物理地址。的物理结构转换成物理地址。第第7层是文件存储设备分配模块和设备策略模块。文层是文件存储设备分配模块和设备策略模块。文件存储设备分配模块实现对空闲存储块的管理，包件存储设备分配模块实现对空闲存储块的管理，包括分配、释放和组织。设备策略模块主要是把物理括分配、释放和组织。设

123、备策略模块主要是把物理块号转换成相应文件存储设备所要求的地址格式，块号转换成相应文件存储设备所要求的地址格式，例如磁盘的柱面号、磁道号、盘区号等。然后，根例如磁盘的柱面号、磁道号、盘区号等。然后，根据具体的操作要求及必要的参数，准备启动输入输据具体的操作要求及必要的参数，准备启动输入输出设备的命令。出设备的命令。 第第8层是启动输入输出层。由设备层是启动输入输出层。由设备处理程序执行具体的读或写文件操作。处理程序执行具体的读或写文件操作。第第7层和第层和第8层是文件系统和设备管理程序的接口层。层是文件系统和设备管理程序的接口层。本本 章章 小小 结结文件系统为用户提供了按名存取的功能，以使得用

124、户文件系统为用户提供了按名存取的功能，以使得用户能透明地存储访问文件。为了实现按名存取，文件能透明地存储访问文件。为了实现按名存取，文件需要对文件存储设备进行合理的组织、分配和管理；需要对文件存储设备进行合理的组织、分配和管理；对存储在文件存储设备上的文件进行保护、保密和对存储在文件存储设备上的文件进行保护、保密和提供共享的手段。另外，文件系统还要提供检索文提供共享的手段。另外，文件系统还要提供检索文件或文件中记录的手段。文件系统就是完成上述功件或文件中记录的手段。文件系统就是完成上述功能的一组软件和数据结构的集合。能的一组软件和数据结构的集合。本章主要讨论了文件、文件系统的基本概念。文件是本

125、章主要讨论了文件、文件系统的基本概念。文件是一组赋名的字符流的集合或一组相关联的记录的集一组赋名的字符流的集合或一组相关联的记录的集合。一个记录是有意义的信息的基本单位，它有定合。一个记录是有意义的信息的基本单位，它有定长和变长两种基本格式。本章在定长的假定下讨论，长和变长两种基本格式。本章在定长的假定下讨论，但其结果也可以扩展到变长格式的情况。但其结果也可以扩展到变长格式的情况。文件按一定的逻辑结构组成逻辑文件，逻辑文件是用文件按一定的逻辑结构组成逻辑文件，逻辑文件是用户可见的抽象文件。文件的逻辑结构可分为字符流户可见的抽象文件。文件的逻辑结构可分为字符流式无结构的连续文件、记录式有结构文件

126、两大类。式无结构的连续文件、记录式有结构文件两大类。其中记录式文件又可分为连续结构、多重结构、转其中记录式文件又可分为连续结构、多重结构、转置结构及顺序结构文件等。对于记录式文件来说，置结构及顺序结构文件等。对于记录式文件来说，如果用户在存取操作时指定的参数是键名或记录名如果用户在存取操作时指定的参数是键名或记录名的话的话(按键存取按键存取)，有三种常用的方法可用来检索文，有三种常用的方法可用来检索文件，它们是：线性检索法、散列法和二分搜索法。件，它们是：线性检索法、散列法和二分搜索法。一个文件在存储设备上按一定的物理方式存放。文件一个文件在存储设备上按一定的物理方式存放。文件的物理结构受设备

127、类型的影响。例如，磁带设备只的物理结构受设备类型的影响。例如，磁带设备只适合于连续存放和顺序存取，而磁盘设备既适合于适合于连续存放和顺序存取，而磁盘设备既适合于连续存放，也适合于串联存放和索引存放。磁盘设连续存放，也适合于串联存放和索引存放。磁盘设备上的文件既可以是顺序存取的，也可以是直接存备上的文件既可以是顺序存取的，也可以是直接存取或按键存取的。取或按键存取的。当用户创建一个文件时，首先要给该文件分配足够的当用户创建一个文件时，首先要给该文件分配足够的存储空间。存储空间的管理方法有空白文件目录、存储空间。存储空间的管理方法有空白文件目录、空闲块链和位示图法。比较有影响的存储空间管理空闲块链

128、和位示图法。比较有影响的存储空间管理方法是空闲块链中的成组链法。方法是空闲块链中的成组链法。文件名或记录名与物理地址之间的转换通过文件目录文件名或记录名与物理地址之间的转换通过文件目录来实现。有单级目录、二级目录和多级目录几种目来实现。有单级目录、二级目录和多级目录几种目录结构。二级目录和多级目录是为了解决文件的重录结构。二级目录和多级目录是为了解决文件的重名问题和提高搜索速度而提出来的。多级目录构成名问题和提高搜索速度而提出来的。多级目录构成文件树形结构。另外，为了便于共享，把目录项中文件树形结构。另外，为了便于共享，把目录项中存放的文件说明信息画分为两部分：文件内部标识存放的文件说明信息画

129、分为两部分：文件内部标识符和文件名与存取控制信息以及结构信息等文件说符和文件名与存取控制信息以及结构信息等文件说明信息部分。前者的集合称为符号文件表明信息部分。前者的集合称为符号文件表SFD,后者后者的集合称为基本文件表的集合称为基本文件表 BFD。对文件的存取控制是和文件共享、保护和保密紧密相对文件的存取控制是和文件共享、保护和保密紧密相关的。存取控制可采用存取控制矩阵、存取控制表、关的。存取控制可采用存取控制矩阵、存取控制表、口令和密码的方法进行存取验证，以确定用户权限。口令和密码的方法进行存取验证，以确定用户权限。最后，在本章中介绍了文件系统的使用方法和文件系最后，在本章中介绍了文件系统的使用方法和文件系统的层次模型。统的层次模型。UNIX系统使用索引文件方式存储文件，文件物理结构系统使用索引文件方式存储文件，文件物理结构如下图所示，设每块大小为如下图所示，设每块大小为1KB,每块地址用每块地址用4B表示，表示，B字节。问该文件系统管理的最大文件是多大？字节。问该文件系统管理的最大文件是多大？