计算机操作系统(6)第6章文件管理

1、第六章第六章 文件管理文件管理n重点重点n文件系统的基本概念、文件的逻辑结构、文件、记录、文件系统的基本概念、文件的逻辑结构、文件、记录、数据项的基本概念。数据项的基本概念。n外存分配的连续分配、链接分配、索引分配方式。外存分配的连续分配、链接分配、索引分配方式。n目录管理、文件存储空间管理的功能。目录管理、文件存储空间管理的功能。n知识点知识点n掌握：文件的逻辑组织和物理组织的概念及不同的组掌握：文件的逻辑组织和物理组织的概念及不同的组织形式，文件的目录结构，文件和目录的主要操作。织形式，文件的目录结构，文件和目录的主要操作。n理解：文件的分类，文件的存取控制，理解：文件的分类，文件的存取控

2、制，UNIX文件系统文件系统的主要操作。的主要操作。n了解：文件系统的功能，文件存储空间的管理，文件了解：文件系统的功能，文件存储空间的管理，文件的后备和恢复，管理文件等。的后备和恢复，管理文件等。第六章文 件 管 理 6.1文件和文件系统文件和文件系统6.2文件的逻辑结构文件的逻辑结构6.3外存分配方式外存分配方式6.4空闲空闲空间空间的管理的管理6.5目录管理目录管理6.6文件共享与文件保护文件共享与文件保护6.7数据一致性控制数据一致性控制 第六章第六章 文件管理文件管理n在现代计算机系统中，用到大量的程序和数据，在现代计算机系统中，用到大量的程序和数据，由于内存容量和存储特性的限制，这

3、些内容必须由于内存容量和存储特性的限制，这些内容必须以文件的形式保存在外存。以文件的形式保存在外存。n操作系统必须提供操作系统必须提供对外存的文件管理对外存的文件管理的功能，即的功能，即构成文件系统。构成文件系统。n文件系统中包括文件文件系统中包括文件管理管理、文件、文件存取存取、共享共享和文和文件件保护。保护。n文件是具有文件名的若干文件是具有文件名的若干相关元素相关元素的的集合。集合。n文件系统的管理功能是通过把它所管理的程序和文件系统的管理功能是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。数据组织成一系列文件的方法来实现的。6.1 文件和文件系统文件和文件系统数据数据抽象抽

4、象加工加工信息信息生产生产生活生活组织组织数据结构数据结构处理处理数据库数据库存储存储文件系统文件系统传输传输计算机网络计算机网络6.1 文件和文件系统文件和文件系统n所有的计算机应用程序都要存储信息和检索信息所有的计算机应用程序都要存储信息和检索信息n三个基本要求三个基本要求n能够存储大量的信息能够存储大量的信息n长期保存信息长期保存信息n可以共享信息可以共享信息n解决方法：把信息以一种单元，即文件的形式存解决方法：把信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。储在磁盘或其他外部介质上。n文件是通过操作系统来管理的，包括：文件的结文件是通过操作系统来管理的，包括：文件的结构、命名

5、、存取、使用、保护和实现方法。构、命名、存取、使用、保护和实现方法。6.1 文件和文件系统文件和文件系统n文件管理任务文件管理任务n文件管理文件管理是软件（程序与数据集合）资源管理，是软件（程序与数据集合）资源管理，是涉及用户作业和内部硬件管理是涉及用户作业和内部硬件管理n任务任务：把存储、检索、共享和保护文件的手段：把存储、检索、共享和保护文件的手段提供给本身和用户，以方便用户及资源利用提供给本身和用户，以方便用户及资源利用n功能功能n分配与管理外存分配与管理外存n提供合适的存储方法提供合适的存储方法n文件共享，保护解决冲突文件共享，保护解决冲突6.1 文件和文件系统文件和文件系统n文件管理

6、功能文件管理功能n分配与管理外部存储器，用户以文件形式存放分配与管理外部存储器，用户以文件形式存放信息，信息，“按名存取按名存取”，文件的，文件的机内码机内码与磁盘、与磁盘、光盘等外存地址建立起相光盘等外存地址建立起相对应的联系。对应的联系。n提供合适的存储方法，例如，提供合适的存储方法，例如，鍵盘命令鍵盘命令以及程以及程序中使用序中使用系统调用系统调用控制。包括文件的创建控制。包括文件的创建(Create)(Create)、打开、打开(Open)(Open)、关闭、关闭(Close)(Close)、读写、读写(Read/Write)(Read/Write)、刪除、刪除(Delete, Era

7、se)(Delete, Erase)和重命和重命名或改名名或改名(Rename)(Rename)等。等。n文件的文件的共享与保护共享与保护，解决文件命名中的，解决文件命名中的冲突和冲突和存取权限存取权限的控制。的控制。6.1 文件和文件系统文件和文件系统n6.1.1 文件、记录和数据项文件、记录和数据项n6.1.2 文件类型和文件系统模型文件类型和文件系统模型n6.1.3 文件操作文件操作6.1.1 文件、记录和数据项文件、记录和数据项n数据项数据项n最低级的数据组织形式最低级的数据组织形式n基本数据项基本数据项。用于描述一个对象的某种属性的。用于描述一个对象的某种属性的字符集，是数据组织中可

8、以命名的最小逻辑数字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。据单位，即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。它的命名往往与其属性一致。n组合数据项组合数据项。由若干个基本数据项组成的，简。由若干个基本数据项组成的，简称组项。称组项。6.1.1 文件、记录和数据项文件、记录和数据项n记录记录n一组一组相关数据项的集合相关数据项的集合，用于描述一个对象在某，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于于需要描述对象的哪个方面。而一个对象，

9、由于他所处的环境不同可把他作为不同的对象。他所处的环境不同可把他作为不同的对象。n在诸多记录中，为了能惟一地标识一个记录，必在诸多记录中，为了能惟一地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几须在一个记录的各个数据项中，确定出一个或几个数据项，把它们的集合称为个数据项，把它们的集合称为关键字关键字(key)。或者。或者说，关键字是惟一能标识一个记录的数据项。通说，关键字是惟一能标识一个记录的数据项。通常，只需用一个数据项作为关键字。常，只需用一个数据项作为关键字。6.1.1 文件、记录和数据项文件、记录和数据项n文件文件n由创建者所定义的、具有文件名的一组相关元由创建者所定义的

10、、具有文件名的一组相关元素的集合。素的集合。n有结构文件：由若干个相关记录组成；有结构文件：由若干个相关记录组成；n无结构文件：由字符流构成。无结构文件：由字符流构成。n文件在文件系统中是一个最大的数据单位，它文件在文件系统中是一个最大的数据单位，它描述了一个对象集。描述了一个对象集。n文件的属性：文件的属性：n文件类型。文件类型。n文件长度。文件长度。n文件的物理位置。文件的物理位置。n文件的建立、修改、访问时间。文件的建立、修改、访问时间。6.1.1 文件、记录和数据项文件、记录和数据项n文件控制块（文件控制块（FCB）n用于描述和控制文件的数据结构；用于描述和控制文件的数据结构；n文件管

11、理程序可借助文件管理程序可借助FCB中的信息对文件施以中的信息对文件施以各种操作。各种操作。n文件控制块中的信息文件控制块中的信息n基本信息类基本信息类n文件名文件名n文件的物理位置文件的物理位置 n文件的逻辑结构文件的逻辑结构 n文件的物理结构文件的物理结构 6.1.1 文件、记录和数据项文件、记录和数据项n文件控制块中的信息文件控制块中的信息n文件控制信息类文件控制信息类n文件拥有者权限文件拥有者权限n核准用户权限核准用户权限n一般用户权限一般用户权限n使用信息类使用信息类n文件建立日期文件建立日期n文件修改日期文件修改日期6.1.1 文件、记录和数据项文件、记录和数据项n文件控制块中的信

12、息文件控制块中的信息n例，例，MS-DOS中的文件控制块，其中含有文件中的文件控制块，其中含有文件名、文件所在的第一个盘块号、文件属性、名、文件所在的第一个盘块号、文件属性、文件建立日期和时间及文件长度等。文件建立日期和时间及文件长度等。FCB的的长度为长度为32个字节，对个字节，对360KB的软盘，总共可包的软盘，总共可包含含112个个FCB，共占，共占4KB的存储空间。的存储空间。文件文件名名扩展扩展名名属性属性备用备用时间时间日期日期第一第一块号块号盘块盘块数数6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件类型文件类型n文件的分类是为了更好地管理和使用，要科学地分门文件的

13、分类是为了更好地管理和使用，要科学地分门别类，对不同的文件进行不同的管理。这样，不仅提别类，对不同的文件进行不同的管理。这样，不仅提高了文件的存取速度，对文件的共享和保护也有利高了文件的存取速度，对文件的共享和保护也有利n一般系统级与用户级要进行不同的管理，例如，一个一般系统级与用户级要进行不同的管理，例如，一个系统文件工作时要读入内存，放在内存的某一固定区，系统文件工作时要读入内存，放在内存的某一固定区，有较高的保护级别，一般用户不允许进入。而一般用有较高的保护级别，一般用户不允许进入。而一般用户的用户文件是在另外管辖的可用区有空闲时才能被户的用户文件是在另外管辖的可用区有空闲时才能被调入指

14、定的内存用户区。调入指定的内存用户区。n许多许多OS中都把文件类型作为扩展名而缀在文件名的后中都把文件类型作为扩展名而缀在文件名的后面，在文件名和扩展名之间用面，在文件名和扩展名之间用“.”号隔开。号隔开。常见的文件类型常见的文件类型6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件类型文件类型n按文件的性质和用途按文件的性质和用途n系统文件。系统文件。n用户文件。用户文件。n库文件。库文件。n 按文件中数据的形式按文件中数据的形式n源文件。源文件。n目标文件。目标文件。n可执行文件可执行文件。6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件类型文件类型n按系统管理员

15、或用户所规定的存取控制属性按系统管理员或用户所规定的存取控制属性n只执行文件。只执行文件。n只读文件。只读文件。n读写文件。读写文件。n按文件的组织形式和系统对其的处理方式按文件的组织形式和系统对其的处理方式n普通文件。普通文件。n目录文件。目录文件。n特殊文件。特殊文件。6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件类型文件类型n按使用情况按使用情况n临时文件。临时文件。n永久文件。永久文件。n档案文件。档案文件。n按存取的物理结构按存取的物理结构n顺序（连续）文件。顺序（连续）文件。n链接文件。链接文件。n索引文件。索引文件。6.1.2 文件类型和文件系统模型文件类型和文件

16、系统模型n文件系统文件系统n负责管理和存取文件信息的软件机构，它是由负责管理和存取文件信息的软件机构，它是由管理文件所需的数据结构和相应的管理软件以管理文件所需的数据结构和相应的管理软件以及访问文件的一组操作组成。及访问文件的一组操作组成。n从从系统的角度系统的角度看看：一个负责文件存储空间管理：一个负责文件存储空间管理的机构。的机构。n从从用户的角度用户的角度看看：用户在计算机上存储信息、：用户在计算机上存储信息、使用信息的接口。使用信息的接口。6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件系统文件系统n文件系统功能文件系统功能n用户角度用户角度：实现实现“按名存取按名存取”

17、n系统角度系统角度：对文件存储器的存储空间进行组对文件存储器的存储空间进行组织、分配、负责文件的存储并对存入的文件织、分配、负责文件的存储并对存入的文件实施保护、检索的一组软件的集合实施保护、检索的一组软件的集合n文件系统具体功能文件系统具体功能n统一管理文件的存储空间，实施存储空间的分配与统一管理文件的存储空间，实施存储空间的分配与回收回收n实现文件的按名存取实现文件的按名存取 名字空间名字空间 映射映射 存储空间存储空间6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件系统文件系统n文件系统具体功能文件系统具体功能n实现文件信息的共享，并提供文件的保护和保实现文件信息的共享，并

18、提供文件的保护和保密措施密措施n向用户提供一个方便使用的接口（提供对文件向用户提供一个方便使用的接口（提供对文件系统操作命令，以及提供对文件的操作命令：系统操作命令，以及提供对文件的操作命令：信息存取、加工等）信息存取、加工等）n系统维护及向用户提供有关信息系统维护及向用户提供有关信息n提供与提供与I/OI/O的统一接口。的统一接口。6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件系统文件系统n文件系统的优点文件系统的优点n使用方便，灵活，用户按名存取使用方便，灵活，用户按名存取n安全可靠，安全可靠， 保护系统和用户保护系统和用户n提供保密与共享提供保密与共享n文件系统必须解决的

19、问题文件系统必须解决的问题n如何有效地分配文件存储器的存储空间如何有效地分配文件存储器的存储空间n提供合适的存取方法提供合适的存取方法n命名的冲突和文件的共享命名的冲突和文件的共享6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件系统文件系统n理想文件系统的特征理想文件系统的特征n有效地分配文件存储器的存储空间有效地分配文件存储器的存储空间n文件结构和存取的灵活性和多样性文件结构和存取的灵活性和多样性n具有对用户来说尽可能是透明的机制具有对用户来说尽可能是透明的机制n尽可能达到文件存储装置的独立性尽可能达到文件存储装置的独立性n存储在文件中的信息的安全存储在文件中的信息的安全n能方

20、便的共享公用的文件能方便的共享公用的文件n有效地实现各种文件操作的命令有效地实现各种文件操作的命令6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件系统模型文件系统模型6.1.2 文件类型和文件系统模型文件类型和文件系统模型n文件系统模型文件系统模型n对象及其属性对象及其属性n文件文件n目录目录n磁盘磁盘(磁带磁带)存储空间存储空间n对对象操纵和管理的软件集合对对象操纵和管理的软件集合n对文件存储空间的管理对文件存储空间的管理n对文件目录的管理对文件目录的管理n用于将文件的逻辑地址转换为物理地址的机制用于将文件的逻辑地址转换为物理地址的机制n对文件读和写的管理对文件读和写的管理n对

21、文件的共享与保护等功能对文件的共享与保护等功能n文件系统接口文件系统接口n命令接口命令接口n程序接口程序接口6.1.3 文件操作文件操作n对文件的操作可分成两大类：对文件的操作可分成两大类：，创建一个新文件、，创建一个新文件、删除一个老文件、拷贝一个文件、为文件改名删除一个老文件、拷贝一个文件、为文件改名等；等；，检索一个文件中的所，检索一个文件中的所有记录、检索一个文件中的单个记录等。有记录、检索一个文件中的单个记录等。6.1.3 文件操作文件操作n对记录的操作对记录的操作。检索一个文件中的所有记录，这种。检索一个文件中的所有记录，这种操作主要用于检索时需要涉及到文件中所有记录中的操作主要用

22、于检索时需要涉及到文件中所有记录中的信息情况。信息情况。仅检索一个文件中的某个记录。这种。仅检索一个文件中的某个记录。这种操作主要用于面向事务处理的应用中。操作主要用于面向事务处理的应用中。将一个新记录插入到一个含有若干个。将一个新记录插入到一个含有若干个记录的文件中的适当位置。记录的文件中的适当位置。从文件中检索到一个指定记录后，便。从文件中检索到一个指定记录后，便可对其中的一个或多个数据项进行修改，然后将修改可对其中的一个或多个数据项进行修改，然后将修改后的记录在写回文件中。后的记录在写回文件中。从已存文件中的删除一个记录。从已存文件中的删除一个记录。6.1.3 文件操作文件操作n最基本的

23、文件操作最基本的文件操作n创建文件创建文件n删除文件删除文件n读文件读文件n写文件写文件n截断文件截断文件n设置文件的读设置文件的读/写位置写位置6.1.3 文件操作文件操作n文件的文件的 “打开打开”和和 “关闭关闭”操作操作n所谓所谓“打开打开”OPEN，是指系统将指名文件的，是指系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的中，并将该表目的编号编号(或称为或称为索引索引)返回给用返回给用户户n当用户再要求对该文件进行相应的操作时，便当用户再要求对该文件进行相应的操作时，便可利用系统所返回的可利用系统所返回的索引号索引号向系

24、统提出操作请向系统提出操作请求。系统这时便可直接利用该索引号到打开文求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检件表中去查找，从而避免了对该文件的再次检索索n“关闭关闭”(CLOSE)系统调用来关闭此文件，系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉将会把该文件从打开文件表中的表目上删除掉6.1.3 文件操作文件操作n其它文件操作其它文件操作n文件属性操作文件属性操作n改名改名n改变拥有者改变拥有者n修改权限修改权限n查询状态查询状态n有关目录操作有关目录操作n创建目录创建目录n删除目录删除目录n改变当前目录改变当前目录n实现文件共享的

25、系统调用实现文件共享的系统调用n用于对文件系统进行操作的系统调用用于对文件系统进行操作的系统调用6.2 文件的逻辑结构文件的逻辑结构n6.2.1 文件逻辑结构的类型文件逻辑结构的类型n6.2.2 顺序文件顺序文件n6.2.3 索引文件索引文件n6.2.4 索引顺序文件索引顺序文件n6.2.5 直接文件和哈希文件直接文件和哈希文件6.2.1 文件逻辑结构的类型文件逻辑结构的类型n文件组织的两种观点文件组织的两种观点n用户观点用户观点（逻辑结构）：研究的是用户思维中的抽（逻辑结构）：研究的是用户思维中的抽象文件，也叫逻辑文件。其目的是为用户提供一种象文件，也叫逻辑文件。其目的是为用户提供一种结构清

26、晰、使用简便的逻辑组织。用户按此去存储、结构清晰、使用简便的逻辑组织。用户按此去存储、检索和加工处理有关文件信息。检索和加工处理有关文件信息。n实现观点实现观点（物理结构）：研究的是存储在物理设备（物理结构）：研究的是存储在物理设备介质上的实际文件，即物理文件。其目的是选择一介质上的实际文件，即物理文件。其目的是选择一些性能良好、设备利用率高的物理结构。系统按此些性能良好、设备利用率高的物理结构。系统按此和外部设备打交道，控制信息的传输。和外部设备打交道，控制信息的传输。n对逻辑结构的要求对逻辑结构的要求n提高检索速度提高检索速度n便于修改便于修改n降低文件的存储费用降低文件的存储费用6.2.

27、1 文件逻辑结构的类型文件逻辑结构的类型n有结构文件有结构文件记录式文件记录式文件n按记录长度分按记录长度分n定长记录定长记录n变长记录变长记录n根据用户和系统管理需要分根据用户和系统管理需要分n顺序文件顺序文件n索引文件索引文件n索引顺序文件索引顺序文件n无结构文件无结构文件n流式文件流式文件 其长度以字节为单位其长度以字节为单位n采用读写指针来指出下一个要访问的字符采用读写指针来指出下一个要访问的字符n如如 源程序、源程序、 可执行文件、可执行文件、 库函数库函数等等文件的长度用文件的长度用记录数目表示。记录数目表示。处理方便、开处理方便、开销小，被广泛销小，被广泛用于数据处理用于数据处理

28、中中可以有效节可以有效节省存储空间省存储空间由一系列记录按某由一系列记录按某种顺序排列。其中种顺序排列。其中的记录通常是定长的记录通常是定长记录，因而能用较记录，因而能用较快的速度查找文件快的速度查找文件中的记录。中的记录。当记录为可变长度当记录为可变长度时，通常为之建立时，通常为之建立一张索引表，并为一张索引表，并为每个记录设置一个每个记录设置一个表项，以加快对记表项，以加快对记录检索的速度。录检索的速度。上述两种文件构成上述两种文件构成方式的结合。它为方式的结合。它为文件建立一张索引文件建立一张索引表，为每一组记录表，为每一组记录中的第一个记录设中的第一个记录设置一个表项。置一个表项。6.

29、2.1 文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构文件逻辑结构有结构文件有结构文件（记录式）（记录式）无结构文件无结构文件（流式）（流式）定长记录定长记录变长记录变长记录顺序文件顺序文件索引文件索引文件索引顺序文件索引顺序文件6.2.2 顺序文件顺序文件n逻辑记录的排序逻辑记录的排序n串结构串结构n各记录之间的顺序与关键字无关各记录之间的顺序与关键字无关n通常由时间来决定通常由时间来决定n存在问题存在问题n顺序结构顺序结构n文件中的所有记录按关键字文件中的所有记录按关键字(词词)排列排列记录号记录号学号学号姓名姓名性别性别出生时间出生时间11赵赵23钱钱34孙孙45李李56周周620吴吴

30、6.2.2 顺序文件顺序文件n对对顺序文件顺序文件(Sequential File)的读的读/写操作写操作n定长记录顺序文件的读定长记录顺序文件的读/写操作写操作n在读一个文件时，可设置一个读指针在读一个文件时，可设置一个读指针Rptr，令它指，令它指向下一个记录的首地址，每当读完一个记录时，执向下一个记录的首地址，每当读完一个记录时，执行行Rptr:=Rptr + L n在写一个文件时，也应设置一个写指针在写一个文件时，也应设置一个写指针Wptr，使之，使之指向要写的记录的首地址。在每写完一个记录时，指向要写的记录的首地址。在每写完一个记录时，执行执行Wptr:=Wptr + L6.2.2

31、顺序文件顺序文件n对对顺序文件顺序文件(Sequential File)的读的读/写操作写操作n变长记录顺序文件的读变长记录顺序文件的读/写操作写操作n在顺序读或写时的情况相似，但应分别为它们设置在顺序读或写时的情况相似，但应分别为它们设置读或写指针，在每次读或写完一个记录后，须将读读或写指针，在每次读或写完一个记录后，须将读或写指针加上或写指针加上Li。Li是刚读或刚写完的记录的长度。是刚读或刚写完的记录的长度。6.2.2 顺序文件顺序文件记录长度记录长度记录记录起始地址起始地址6.2.2 顺序文件顺序文件n顺序文件的优缺点顺序文件的优缺点n优点优点n结构简单，容易实现结构简单，容易实现n顺

32、序文件的最佳应用场合，是在对诸记录进行顺序文件的最佳应用场合，是在对诸记录进行批量批量存取存取时，即每次要读或写一大批记录时，即每次要读或写一大批记录n只有顺序文件才能存储在磁带上，并能有效地工作只有顺序文件才能存储在磁带上，并能有效地工作n缺点缺点n如果用户如果用户(程序程序)要求要求查找或修改查找或修改单个记录，单个记录， 顺序文顺序文件所表现出来的件所表现出来的性能就可能很差性能就可能很差n如果想如果想增加或删除增加或删除一个记录，一个记录， 都比较困难（需都比较困难（需移动移动大量数据）大量数据）n创建文件必须给出大小，不利于动态增长创建文件必须给出大小，不利于动态增长配置一个运行记录

33、文件配置一个运行记录文件(Log File)，或称为事务文件，或称为事务文件(Transaction File)，把试图，把试图增加、删除或修改的信息记增加、删除或修改的信息记录于其中，每隔一定时间，录于其中，每隔一定时间，将运行记录文件与原来的主将运行记录文件与原来的主文件加以合并，产生一个按文件加以合并，产生一个按关键字排序的新文件。关键字排序的新文件。6.2.3 索引文件索引文件n对对定长记录定长记录文件，如果要查找第文件，如果要查找第i个记录，个记录， 可直可直接根据下式计算来获得第接根据下式计算来获得第i个记录相对于第一个个记录相对于第一个记录首址的地址记录首址的地址Ai = iLn

34、对于对于可变长度记录可变长度记录的文件，要查找其第的文件，要查找其第i个记录个记录时，需顺序查找出每个记录的长度（时，需顺序查找出每个记录的长度（Li），才能），才能计算出该记录的首地址计算出该记录的首地址10iiiiiLA6.2.3 索引文件索引文件索引本身是一个定长记录的顺序文件，主文件中每个记录在索引本身是一个定长记录的顺序文件，主文件中每个记录在索引表中占一个表项，可采用快速查找算法，如字典索引表中占一个表项，可采用快速查找算法，如字典6.2.3 索引文件索引文件n索引文件的检索步骤索引文件的检索步骤n根据用户提供的关键字，从索引表中找到相应的表项；根据用户提供的关键字，从索引表中找到

35、相应的表项；n再利用该表项中给出的指向记录的指针值，去访问所再利用该表项中给出的指向记录的指针值，去访问所需记录。需记录。n向索引文件中增加一个记录，需对索引表进行修向索引文件中增加一个记录，需对索引表进行修改。改。n优点优点n检索速度快，主要用于对信息处理的及时性要求较高检索速度快，主要用于对信息处理的及时性要求较高的场合。的场合。n缺点缺点n存储费用高，因为除了主文件外，还需配置一张索引存储费用高，因为除了主文件外，还需配置一张索引表，且每个记录都有一个索引项。表，且每个记录都有一个索引项。6.2.4 索引顺序文件索引顺序文件n索引顺序文件（索引顺序文件（Index Sequential

36、File）是是最常见的一种逻辑文件组织形式，是最常见的一种逻辑文件组织形式，是顺序顺序文件与索引文件的结合。文件与索引文件的结合。n克服了变长记录文件不便于直接存取的缺克服了变长记录文件不便于直接存取的缺点，代价也不太大。点，代价也不太大。n将顺序文件中的所有记录分为若干个将顺序文件中的所有记录分为若干个组组，为为每组中的第一个记录每组中的第一个记录建立索引项，其中建立索引项，其中含有该记录的键值及指向该记录的指针。含有该记录的键值及指向该记录的指针。6.2.4 索引顺序文件索引顺序文件6.2.4 索引顺序文件索引顺序文件n文件检索速度文件检索速度n对顺序文件检索对顺序文件检索n若记录数据为若

37、记录数据为N，则检索一条记录时，最好的，则检索一条记录时，最好的情况是第一条记录即为所求；最坏的情况是最情况是第一条记录即为所求；最坏的情况是最后一条记录为所求；平均检索后一条记录为所求；平均检索N/2条记录条记录n对索引文件检索对索引文件检索n可采用折半查找等方法，平均查找可采用折半查找等方法，平均查找 条记录条记录n对索引顺序文件检索对索引顺序文件检索n索引文件与顺序文件的结合索引文件与顺序文件的结合N6.2.4 索引顺序文件索引顺序文件n例子例子n例例1 1：1000010000个记录个记录n顺序文件：顺序文件：50005000次查找查到。次查找查到。n索引顺序文件，设索引顺序文件，设1

38、00100个记录一组，索引表个记录一组，索引表的找法设为顺序法的情况下，则查找次数为的找法设为顺序法的情况下，则查找次数为50+50=10050+50=100。n例例2 2：10000001000000个纪录个纪录n低级索引：（低级索引：（100100个纪录一组）：个纪录一组）：1000010000。n高级索引：高级索引：100100n查找次数：查找次数：50+50+50=15050+50+50=1506.2.5 直接文件和哈希文件直接文件和哈希文件n键值转换键值转换(Key to address transformation)n由记录键值到记录物理地址的转换由记录键值到记录物理地址的转换n直

39、接文件直接文件 n根据给定的记录键值，直接获得指定记录的物根据给定的记录键值，直接获得指定记录的物理地址。理地址。n哈希哈希(Hash)文件文件 n利用哈希函数将记录键值转换为相应记录的地利用哈希函数将记录键值转换为相应记录的地址。址。6.2.5 直接文件和哈希文件直接文件和哈希文件6.3 外存分配方式外存分配方式n对于任何一个文件，都存在着以下两种形对于任何一个文件，都存在着以下两种形式的结构：式的结构：n文件的逻辑结构文件的逻辑结构(File Logical Structure)。n文件的物理结构，文件的物理结构， 又称为文件的存储结构，又称为文件的存储结构， 是指文件在外存上的存储组织形

40、式。是指文件在外存上的存储组织形式。n 问题问题n如何才能有效地利用外存空间如何才能有效地利用外存空间?n如何提高对文件的访问速度如何提高对文件的访问速度?6.3 外存分配方式外存分配方式n外存的特点外存的特点n容量大，断电后仍可保存信息，速度较慢，成容量大，断电后仍可保存信息，速度较慢，成本较低本较低n两部分组成：驱动部分两部分组成：驱动部分+ +存储介质存储介质n种类很多种类很多n外存空间组织与地址与存取方式非常复杂外存空间组织与地址与存取方式非常复杂nI/O过程方式非常复杂过程方式非常复杂6.3 外存分配方式外存分配方式n用户对外存的要求用户对外存的要求n使用：读写外存数据使用：读写外存

41、数据n要求：方便、效率、安全要求：方便、效率、安全n在读写外存时不涉及硬件细节，使用逻辑地址和逻辑在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作。操作。n存取速度尽可能快，容量大且空间利用率高存取速度尽可能快，容量大且空间利用率高n外存上存放的信息安全可靠，防止来自硬件的故障和外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权。他人的侵权。n方便地共享，动态扩缩，携带拆卸，了解存储情况和方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况。使用情况。n以尽可能小的代价完成上述要求。以尽可能小的代价完成上述要求。6.3 外存分配方式外存分配方式n文件的物理结构文件的物理结构n指逻辑文

42、件指逻辑文件在存储设备在存储设备（外存）上的（外存）上的存储组织形式存储组织形式，它与存储介，它与存储介质的存储特性有关质的存储特性有关n一个文件存储介质，格式化后就分成许多大小相等的单一个文件存储介质，格式化后就分成许多大小相等的单位位存储块（物理盘块），一般来说，每个物理块是一存储块（物理盘块），一般来说，每个物理块是一个磁盘的扇区，个磁盘的扇区，512B。并给每个存储块有个编号，称为。并给每个存储块有个编号，称为物理块号。物理块号。n物理块是物理块是分配和传输分配和传输信息的信息的基本单位基本单位，其与外存设备有关，其与外存设备有关，但与逻辑记录大小无关，如但与逻辑记录大小无关，如扇区、

43、簇。扇区、簇。n文件在逻辑上都可看作是连续的，但在物理设备上存放时文件在逻辑上都可看作是连续的，但在物理设备上存放时却有不同的方式，如却有不同的方式，如连续结构（顺序结构）、链接结构连续结构（顺序结构）、链接结构（串联结构）、索引结构、（串联结构）、索引结构、HASH文件文件等等6.3 外存分配方式外存分配方式。把逻辑文件中的记录顺序地存储到。把逻辑文件中的记录顺序地存储到连续的物理盘块中。连续的物理盘块中。文件中的各个记录可以存放在不相。文件中的各个记录可以存放在不相邻接的各个物理盘块中，通过物理块中的链接邻接的各个物理盘块中，通过物理块中的链接指针，将它们连接成一个链表。指针，将它们连接成

44、一个链表。文件中的各个记录可存储在不相邻。文件中的各个记录可存储在不相邻接的各个物理块中。接的各个物理块中。6.3 外存分配方式外存分配方式n6.3.1 连续分配连续分配n6.3.2 链接分配链接分配n6.3.3 FAT和和NTFS技术技术n6.3.4 索引分配索引分配6.3.1 连续分配连续分配n连续分配连续分配(Continuous Allocation)要求为每要求为每一个文件分配一个文件分配一组相邻接的盘块一组相邻接的盘块。一组盘。一组盘块定义了磁盘上的一段线性地址。块定义了磁盘上的一段线性地址。n在采用连续分配方式时，可把逻辑文件中在采用连续分配方式时，可把逻辑文件中的记录顺序地存储

45、到邻接的各物理盘块中，的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为这样所形成的文件结构称为顺序文件结构顺序文件结构，此时的物理文件称为此时的物理文件称为顺序文件。顺序文件。6.3.1 连续分配连续分配6.3.1 连续分配连续分配n连续分配的主要优缺点连续分配的主要优缺点n优点优点n结构简单，容易实现。结构简单，容易实现。n支持顺序存取和随机存取。支持顺序存取和随机存取。n顺序存取速度快。顺序存取速度快。n所需的磁盘寻道次数和寻道时间最少。所需的磁盘寻道次数和寻道时间最少。n缺点缺点n要求有连续的存储空间，不利于动态扩充。要求有连续的存储空间，不利于动态扩充。n容易形成容易形成

46、碎片，空间利用不充分。碎片，空间利用不充分。n必须事先知道文件的长度，用户不方便。必须事先知道文件的长度，用户不方便。6.3.2 链接分配链接分配n链接分配（链接分配（Chained Allocation）n可通过在每个盘块上的链接指针，将同属于一可通过在每个盘块上的链接指针，将同属于一个文件的多个个文件的多个离散的离散的盘块链接成一个盘块链接成一个链表链表，把，把这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件n这种文件结构这种文件结构不要求连续存放不要求连续存放n对于记录式文件一块中可包含一个或多个逻辑记对于记录式文件一块中可包含一个或多个逻辑记录，也可以若干物理块包含一个逻辑

47、记录。录，也可以若干物理块包含一个逻辑记录。n链接方式链接方式n隐式链接隐式链接n显式链接显式链接6.3.2 链接分配链接分配n隐式链接隐式链接文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录01234567891011121314151617181920212223242526272829303111016-1256.3.2 链接分配链接分配n隐式链接隐式链接n每个物理块的最末一个字每个物理块的最末一个字(或第一个字或第一个字)作为链作为链接字，它指出后继块的物理地址。链首指针存接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为放在该文件目录中。

48、文件的结尾块的指针为“”。n优点优点n离散存储，空间利用率高；离散存储，空间利用率高；n顺序存取效率高。顺序存取效率高。n缺点缺点n随机存取效率太低，若要访问第随机存取效率太低，若要访问第i个物理块，个物理块，必须读出前必须读出前i-1个。个。6.3.2 链接分配链接分配n显式链接显式链接n为了克服链接文件的存取效率太低的问题，提为了克服链接文件的存取效率太低的问题，提出出文件映照的技术文件映照的技术，即把链接文件中的链接字，即把链接文件中的链接字集中在一结构中，集中在一结构中，这样既保持了链接文件的优这样既保持了链接文件的优点，也克服了其缺点点，也克服了其缺点，DOS、WINDOWS系统系统

49、就采用了这样结构。就采用了这样结构。n文件分配表（文件分配表（File Allocation Table, FAT）n在在FAT中每个物理块占一个表项，增加一个指中每个物理块占一个表项，增加一个指针指向下一个物理块，最末一个物理块的指针针指向下一个物理块，最末一个物理块的指针为为“”。6.3.2 链接分配链接分配n显式链接显式链接6.3.2 链接分配链接分配n主要优缺点主要优缺点n优点优点n消除了外部碎片，提高外存利用率；消除了外部碎片，提高外存利用率；n文件动态增长时，可动态地为它分配盘块；文件动态增长时，可动态地为它分配盘块；n文件的增删改方便，不需事先知道文件长。文件的增删改方便，不需事

50、先知道文件长。n缺点缺点n存取速度慢；存取速度慢；n只适于只适于顺序存取顺序存取，不适于随机存取；不适于随机存取；n可靠性差，若某一块可靠性差，若某一块指针指针出错，则链断开；出错，则链断开；n更多的寻道次数和寻道时间；更多的寻道次数和寻道时间；n链接指针占用一定的空间。链接指针占用一定的空间。6.3.3 FAT和和NTFS技术技术n文件分配表（文件分配表（File Allocation Table, FAT）n磁盘格式化后建立，从磁盘的第二个开始，有磁盘格式化后建立，从磁盘的第二个开始，有两个相同的两个相同的FAT。n用于记录外存分配状况，每个盘块（或簇）占用于记录外存分配状况，每个盘块（或

51、簇）占一项，放在内存中，整个系统一张一项，放在内存中，整个系统一张FAT。n表的序号为物理盘块号或簇号，从表的序号为物理盘块号或簇号，从0至至N-1。n分配给一个文件的所有物理块都在该表中标出，分配给一个文件的所有物理块都在该表中标出，文件的第一个盘块号记入文件的文件的第一个盘块号记入文件的FCB中。中。6.3.3 FAT和和NTFS技术技术6.3.3 FAT和和NTFS技术技术区名区名内容内容 软盘软盘 占扇区数占扇区数 扇区号扇区号保留区保留区引导记录与磁引导记录与磁盘参数表盘参数表 1 0控制区控制区FAT1文件分文件分配表配表 2 12FAT2 2 34FDT文件目录文件目录表表 7

52、511文件区文件区 文件内容文件内容 余下部分余下部分 126.3.3 FAT和和NTFS技术技术nDOSDOS磁盘访问操作流程磁盘访问操作流程6.3.3 FAT和和NTFS技术技术nFAT12n簇的基本概念簇的基本概念n簇是一组连续的扇区，在簇是一组连续的扇区，在FAT中它是作为一个虚拟中它是作为一个虚拟扇区，簇的大小一般是扇区，簇的大小一般是2n (n为整数为整数)个盘块，在个盘块，在MS-DOS的实际运用中，簇的容量可以仅有一个扇区的实际运用中，簇的容量可以仅有一个扇区(512 B)、两个扇区、两个扇区(1 KB)、四个扇区、四个扇区(2 KB)、八个、八个扇区扇区(4 KB)等。等。n

53、一个簇应包含扇区的数量与磁盘容量的大小直接有一个簇应包含扇区的数量与磁盘容量的大小直接有关。例如，当一个簇仅有一个扇区时，磁盘的最大关。例如，当一个簇仅有一个扇区时，磁盘的最大容量为容量为8 MB；当一个簇包含两个扇区时，磁盘的最；当一个簇包含两个扇区时，磁盘的最大容量可以达到大容量可以达到16 MB；当一个簇包含了八个扇区；当一个簇包含了八个扇区时，磁盘的最大容量便可达到时，磁盘的最大容量便可达到64 MB。6.3.3 FAT和和NTFS技术技术nFAT12nFAT12存在的问题存在的问题n对所允许的磁盘容量存在着严重的限制，通对所允许的磁盘容量存在着严重的限制，通常只能是数十兆字节，虽然可

54、以用继续增加常只能是数十兆字节，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。片也将随之成倍地增加。n它只能支持它只能支持8+3格式的文件名。格式的文件名。 6.3.3 FAT和和NTFS技术技术nFAT16n将将FAT表的宽度增至表的宽度增至16位，最大表项数将增至位，最大表项数将增至65536个，此时便能将一个磁盘分区分为个，此时便能将一个磁盘分区分为65 536(216)个簇。把具有个簇。把具有16位表宽的位表宽的FAT表称为表称为FAT16。

55、在。在FAT16的每个簇中可以有的盘块数的每个簇中可以有的盘块数为为4、8、16、32直到直到64，由此得出，由此得出FAT16可以可以管理的最大分区空间为管理的最大分区空间为 216 64 512 = 2048 MB。6.3.3 FAT和和NTFS技术技术nFAT32n每一簇在每一簇在FAT表中的表项占据表中的表项占据4字节字节(232)，FAT表可以表示表可以表示4 294 967 296项，即项，即FAT32允许管允许管理比理比FAT16更多的簇。这样就允许在更多的簇。这样就允许在FAT32中中采用较小的簇，采用较小的簇，FAT32的每个簇都固定为的每个簇都固定为4 KB，即每簇用即每簇

56、用8个盘块代替个盘块代替FAT16的的64个盘块，每个个盘块，每个盘块仍为盘块仍为512字节，字节，FAT32分区格式可以管理的分区格式可以管理的单个最大磁盘空间大到单个最大磁盘空间大到 4 KB232 = 16 TB（实际（实际2TB）6.3.3 FAT和和NTFS技术技术nFAT中簇的大小与最大分区的对应关系中簇的大小与最大分区的对应关系6.3.3 FAT和和NTFS技术技术nNTFSnNTFS (New Technology File System)新特征新特征n专门为专门为Windows NT开发的、全新的文件系统，并适用开发的、全新的文件系统，并适用于于Windows 2000/XP

57、/2003。n 使用使用64位磁盘地址，理论上可以支持位磁盘地址，理论上可以支持264字节的字节的磁盘分区；磁盘分区； n 可以很好地支持长文件名，单个文件名限制在可以很好地支持长文件名，单个文件名限制在255个字符以内，全路径名为个字符以内，全路径名为32 767个字符；个字符； n 具有系统容错功能，即在系统出现故障或差错时，具有系统容错功能，即在系统出现故障或差错时，仍能保证系统正常运行；仍能保证系统正常运行； n 提供了数据的一致性功能；提供了数据的一致性功能；n 提供了文件加密、文件压缩等功能提供了文件加密、文件压缩等功能。6.3.3 FAT和和NTFS技术技术nNTFSn磁盘组织磁

58、盘组织n以簇作为磁盘空间分配和回收的基本单位。以簇作为磁盘空间分配和回收的基本单位。n一个文件占用若干个簇，一个簇只属于一个文件。一个文件占用若干个簇，一个簇只属于一个文件。n通过簇来间接管理磁盘，可以不需要知道盘块通过簇来间接管理磁盘，可以不需要知道盘块(扇区扇区)的大小，使的大小，使NTFS具有了与磁盘物理扇区大小无关具有了与磁盘物理扇区大小无关的独立性，很容易支持扇区大小不是的独立性，很容易支持扇区大小不是512字节的非字节的非标准磁盘，从而可以根据不同的磁盘选择匹配的簇标准磁盘，从而可以根据不同的磁盘选择匹配的簇大小。大小。6.3.3 FAT和和NTFS技术技术nNTFSn卷因子卷因子

59、n卷中簇的大小。在磁盘格式化时确定的，一个簇包含卷中簇的大小。在磁盘格式化时确定的，一个簇包含2n(n为整数为整数)个盘块。个盘块。n簇的大小可由格式化命令或格式化程序按磁盘容量和簇的大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以为应用需求来确定，可以为512 B、1 KB、2 KB，最，最大可达大可达64 KB。对于小磁盘。对于小磁盘(512 MB)，默认簇大小为，默认簇大小为512字节；对于字节；对于1 GB磁盘，默认簇大小为磁盘，默认簇大小为1 KB；对于；对于2 GB磁盘，则默认簇大小为磁盘，则默认簇大小为4 KB。事实上，为了在传输。事实上，为了在传输效率和簇内碎片之

60、间进行折中，效率和簇内碎片之间进行折中，NTFS在大多数情况下在大多数情况下都是使用都是使用4 KB。6.3.3 FAT和和NTFS技术技术nNTFSn簇的定位：簇的定位：n逻辑簇号逻辑簇号LCN(Logical Cluster Number)：以卷为单：以卷为单位，将整个卷中所有的簇按顺序进行简单的编号。位，将整个卷中所有的簇按顺序进行简单的编号。n地址映射过程：通过卷因子与地址映射过程：通过卷因子与LCN的乘积，便可算的乘积，便可算出卷上的物理字节偏移量，从而得到文件数据所在出卷上的物理字节偏移量，从而得到文件数据所在的物理磁盘地址。的物理磁盘地址。n虚拟簇号虚拟簇号VCN(Virtual