1、 文件系统概念文件系统概念 文件逻辑结构与存取方法文件逻辑结构与存取方法 文件的物理结构与存储设备文件的物理结构与存储设备 文件存储空间管理文件存储空间管理 文件目录管理文件目录管理 文件存取控制文件存取控制 文件使用文件使用 文件系统层次模型文件系统层次模型第第8 8章章 文件系统文件系统( (外存管理）外存管理） 信息信息是计算机系统中的是计算机系统中的重要资源。重要资源。文件文件系统是系统是操作系统中的一个重要组成部分，负操作系统中的一个重要组成部分，负责责信息的组织、存储和访问。信息的组织、存储和访问。 文件系统的功能就是提供文件系统的功能就是提供高效、快速和高效、快速和方便的信息存储
2、和访问功能。方便的信息存储和访问功能。本章的主要内本章的主要内容就是容就是信息的组织信息的组织。8.1 8.1 文件系统概念文件系统概念图图8.18.1操作系统的软硬件管理操作系统的软硬件管理8.1.18.1.1、文件系统的引入、文件系统的引入方便方便的文件访问和控制：以符号名称作为文件标识，的文件访问和控制：以符号名称作为文件标识，便于用户使用；便于用户使用；并发并发文件访问和控制：在多道程系统中支持对文件文件访问和控制：在多道程系统中支持对文件的并发访问和控制；的并发访问和控制；统一统一的用户接口：在不同设备上提供同样的接口，的用户接口：在不同设备上提供同样的接口，方便用户操作和编程；方便
3、用户操作和编程；多种文件访问多种文件访问权限权限：在多用户系统中的不同用户对：在多用户系统中的不同用户对同一文件会有不同的访问权限；同一文件会有不同的访问权限；优化性能优化性能：存储效率、检索性能、读写性能；：存储效率、检索性能、读写性能；差错恢复差错恢复：能够验证文件的正确性，并具有一定的：能够验证文件的正确性，并具有一定的差错恢复能力；差错恢复能力；1 1、文件管理的目的、文件管理的目的1. 1. 文件概念文件概念文件体文件体：文件本身的信息：文件本身的信息文件说明文件说明：文件存储和管理信息；如：文件：文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访问权名、文件内部标识、文
4、件存储地址、访问权限、访问时间等限、访问时间等文件文件是具有是具有名字名字的一段程序或的一段程序或数据的集合，数据的集合，是相关字符流的集合或相关记录的集合是相关字符流的集合或相关记录的集合 。文文件名件名是文件的标识符号。文件包括两部分：是文件的标识符号。文件包括两部分：8.1.2 8.1.2 文件与文件系统的基本概念文件与文件系统的基本概念文件系统文件系统是操作系统中是操作系统中管理文件的机管理文件的机构构，是与管理文件有关的软件以及数，是与管理文件有关的软件以及数据的统称，它负责为用户建立、撤销、据的统称，它负责为用户建立、撤销、读写、修改和复制文件，能提供文件读写、修改和复制文件，能提
5、供文件存储和访问存储和访问功能。功能。2. 2. 文件系统基本概念文件系统基本概念3 3、文件系统特点、文件系统特点n友好的用户界面，用户只对文件操作，不友好的用户界面，用户只对文件操作，不管文件结构和存放的物理位置管文件结构和存放的物理位置n对文件按名存取，对用户透明对文件按名存取，对用户透明n某些文件可以被多个用户或进程共享某些文件可以被多个用户或进程共享n使用磁盘、磁带或光盘等大容量存储器存使用磁盘、磁带或光盘等大容量存储器存储信息储信息按存放时限分类按存放时限分类根据系统保留文件的时间：临时文件、永久文件根据系统保留文件的时间：临时文件、永久文件和档案文件。和档案文件。按设备类型分类按
6、设备类型分类根据文件存储介质的设备类型：磁盘文件、磁带根据文件存储介质的设备类型：磁盘文件、磁带文件、卡片文件和打印文件等。文件、卡片文件和打印文件等。按文件的组织结构分类按文件的组织结构分类文件的逻辑结构：流式文件和记录式文件。文件的逻辑结构：流式文件和记录式文件。文件的物理结构（物理文件）：顺序文件、链接文件的物理结构（物理文件）：顺序文件、链接文件和索引文件等。文件和索引文件等。4 4、文件分类、文件分类按文件的性质和用途划分按文件的性质和用途划分n系统文件。用户只能调用，不能修改系统文件。用户只能调用，不能修改n库文件。允许用户读取和执行，不允许库文件。允许用户读取和执行，不允许修改修
7、改n用户文件。文件的建立者能够拥有所有用户文件。文件的建立者能够拥有所有的权限的权限4 4、文件分类（续）、文件分类（续）按组织形式，文件划分为按组织形式，文件划分为n普通文件。包括系统文件、用户文件和普通文件。包括系统文件、用户文件和库函数文件和实用程序等库函数文件和实用程序等n目录文件。由目录信息构成的特殊文件。目录文件。由目录信息构成的特殊文件。n特殊文件。所有输入、输出设备组成的特殊文件。所有输入、输出设备组成的文件，系统在对这些设备处理时，将其文件，系统在对这些设备处理时，将其看成文件处理。看成文件处理。4 4、文件分类（续）、文件分类（续）文件的分类是为了文件的分类是为了更好地管理
8、和使用更好地管理和使用，这样，这样，不不仅提高了文件的存取速度，对文件的仅提高了文件的存取速度，对文件的共享和保护共享和保护也有利也有利一般系统级与用户级要进行不同的管理，例如，一般系统级与用户级要进行不同的管理，例如，一个系统文件工作时要读入内存，放在内存的某一个系统文件工作时要读入内存，放在内存的某一固定区，有较高的保护级别，一般用户不允许一固定区，有较高的保护级别，一般用户不允许进入。而一般用户的用户文件是在另外管辖的可进入。而一般用户的用户文件是在另外管辖的可用区有空闲时才能被调入指定的内存用户区用区有空闲时才能被调入指定的内存用户区5 5、文件分类的原因、文件分类的原因8.1.3 8
9、.1.3 文件系统的结构和功能元素文件系统的结构和功能元素磁盘设备驱动程序磁盘设备驱动程序 磁带设备驱动程序磁带设备驱动程序基本文件系统基本文件系统基本基本I/O管理程序管理程序逻辑逻辑I/O堆堆顺序顺序 索引顺序索引顺序 索引索引哈希哈希用户程序用户程序1 1、 文件系统的结构文件系统的结构启动该设备上的启动该设备上的I/OI/O操作，处理操作，处理I/OI/O请求请求处理与磁盘或磁带交换的数据块。处理与磁盘或磁带交换的数据块。负责所有文件负责所有文件I/OI/O的开始或结束。选的开始或结束。选择执行文件的择执行文件的I/OI/O设备，外存的分配；设备，外存的分配；使用户和应用程序能够访问到
10、记录。使用户和应用程序能够访问到记录。逻辑逻辑I/OI/O处理的是文件记录。处理的是文件记录。在应用程序和文件系统及保存数据在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。的设备之间提供了一种标准接口。设备驱动程序设备驱动程序：负责启动该设备上的：负责启动该设备上的I/OI/O操作，操作，处理处理I/OI/O请求的完成。请求的完成。基本文件系统（物理基本文件系统（物理I/OI/O层）层）：处理与磁盘或：处理与磁盘或磁带交换的数据块。磁带交换的数据块。基本基本I/OI/O管理程序管理程序：负责所有文件负责所有文件I/OI/O的开始的开始或结束。选择执行文件的或结束。选择执行文件的I/
11、OI/O设备，外存的分设备，外存的分配。配。2 2、文件系统结构元素、文件系统结构元素逻辑逻辑I/OI/O：使用户和应用程序能够访问到记录。使用户和应用程序能够访问到记录。 物理物理I/OI/O层处理的是数据块，逻辑层处理的是数据块，逻辑I/OI/O处理的是处理的是文件记录。它提供一种通用的记录文件记录。它提供一种通用的记录I/OI/O的能力。的能力。访问方法层访问方法层 ：与用户最近的一层。在应用程与用户最近的一层。在应用程序和文件系统及保存数据的设备之间提供了一序和文件系统及保存数据的设备之间提供了一种标准接口。种标准接口。不同的访问方法反映出不同的文件结构和访不同的访问方法反映出不同的文
12、件结构和访问数据的不同方法。问数据的不同方法。2 2、文件系统结构元素（续）、文件系统结构元素（续）文件访问文件访问：文件的创建、打开和关闭，文件的读：文件的创建、打开和关闭，文件的读写；写；目录管理目录管理：用于文件访问和控制的信息，不包括：用于文件访问和控制的信息，不包括文件内容文件内容文件结构管理文件结构管理：划分记录，顺序，索引：划分记录，顺序，索引访问控制访问控制：并发访问和用户权限：并发访问和用户权限限额限额(quota)(quota)：限制每个用户能够建立的文件数目、：限制每个用户能够建立的文件数目、占用外存空间大小等占用外存空间大小等审计审计(auditing)(auditin
13、g)：记录对指定文件的使用信息（如：记录对指定文件的使用信息（如访问时间和用户等），保存在日志中访问时间和用户等），保存在日志中3. 3. 文件系统服务功能元素文件系统服务功能元素4. 4. 文件系统实现的功能模块文件系统实现的功能模块文件的分块存储文件的分块存储：与外存的存储块相配合：与外存的存储块相配合I/OI/O缓冲和调度缓冲和调度：性能优化：性能优化文件定位文件定位：在外存上查找文件的各个存储块：在外存上查找文件的各个存储块外存存储空间管理外存存储空间管理：如分配和释放。主要针对可：如分配和释放。主要针对可改写的外存如磁盘。改写的外存如磁盘。外存设备访问和控制外存设备访问和控制：包括由
14、设备驱动程序支持：包括由设备驱动程序支持的各种基本文件系统如硬盘，软盘，的各种基本文件系统如硬盘，软盘，CD ROMCD ROM等等8.2 8.2 文件的逻辑结构与存取方法文件的逻辑结构与存取方法 文件组织讨论文件组织讨论文件的内部逻辑结构文件的内部逻辑结构，主要，主要考虑因素是文件考虑因素是文件存储性能存储性能和和访问性能访问性能。8.2.1 8.2.1 文件的逻辑结构文件的逻辑结构文件逻辑结构的文件逻辑结构的设计要求设计要求：访问性能：便于检索；便于修改访问性能：便于检索；便于修改存储性能：向物理存储转换方便，节省空间，存储性能：向物理存储转换方便，节省空间，可靠性，维护简单可靠性，维护简
15、单文件的文件的不同组织层次不同组织层次：域、记录、文件：域、记录、文件文件的逻辑结构文件的逻辑结构是指从是指从用户观点用户观点出发讨论文件出发讨论文件内部的逻辑内部的逻辑结构结构(logical structure)(logical structure)或或用户访问模式用户访问模式；它可；它可以以独立于在外存上的物理存储。独立于在外存上的物理存储。是用户可以是用户可以直接处理的数据及其结构。直接处理的数据及其结构。（1 1）无结构文件）无结构文件文件体为文件体为字节流字节流，不划分记录，顺序访问，不划分记录，顺序访问，每次读写访问可以指定任意数据长度。每次读写访问可以指定任意数据长度。当前操作
16、系统中常用的文件组织。当前操作系统中常用的文件组织。1 1、文件逻辑结构分类、文件逻辑结构分类n概念：把文件中的记录按照各种不同的方概念：把文件中的记录按照各种不同的方式排列，构成不同的逻辑结构，方便用户式排列，构成不同的逻辑结构，方便用户对文件的各种操作。对文件的各种操作。n记录：一个具有特殊意义的信息单位，由记录：一个具有特殊意义的信息单位，由该记录在文件中的逻辑地址（相对位置）该记录在文件中的逻辑地址（相对位置）与记录名所对应的一组关键字、属性及属与记录名所对应的一组关键字、属性及属性值组成。性值组成。（2 2）、有结构文件记录式文件）、有结构文件记录式文件图图8.28.2记录组成记录组
17、成典型记录的组成元素典型记录的组成元素n连续结构n多重结构n转置结构2 2、记录式结构文件分类、记录式结构文件分类n概念：把记录按生成的先后顺序连续排列概念：把记录按生成的先后顺序连续排列的逻辑结构。的逻辑结构。n特点：适用性强，可用于所有文件，记录特点：适用性强，可用于所有文件，记录的排列顺序与记录内容无关，有利于记录的排列顺序与记录内容无关，有利于记录的追加和变更。的追加和变更。n缺点：查找性能比较差缺点：查找性能比较差（1 1）连续结构）连续结构n概念概念n把记录按关键字和记录名排列成行列式结构，则一个包把记录按关键字和记录名排列成行列式结构，则一个包含含n n个记录名、个记录名、 mm
18、个关键字的文件构成一个关键字的文件构成一mmn n维行列式。维行列式。n特点特点n能根据关键字和记录名快速定位某条记录能根据关键字和记录名快速定位某条记录n缺点缺点n浪费空间，浪费空间，n n条记录需要条记录需要mm* *n n的空间的空间n改进措施：采用多重队列。改进措施：采用多重队列。 将行列式中为将行列式中为0 0的项去除，以关键字的项去除，以关键字ki ki为队首，以包含关键为队首，以包含关键字字ki ki的记录为队列元素构成一个记录队列。的记录为队列元素构成一个记录队列。MM个关键字就构个关键字就构成了多个队列。成了多个队列。（2 2）多重结构）多重结构文件记录式结构之多重结构及改进
19、图文件记录式结构之多重结构及改进图图图8.38.3文件的记录名和文件的记录名和关键字构成的行列式关键字构成的行列式图图8.48.4文件的多重结构文件的多重结构n概念概念n把含有相同关键字的记录指针全部指向该关键字，把含有相同关键字的记录指针全部指向该关键字，即把所有与同一关键字对应的记录指针连续置于即把所有与同一关键字对应的记录指针连续置于目录中该关键字位置，是对多重结构的变化目录中该关键字位置，是对多重结构的变化图图8.58.5文件的转置结构文件的转置结构（3 3）转置结构）转置结构4 4、顺序结构（索引结构）、顺序结构（索引结构）n概念：按照某种关键字排序进行存放概念：按照某种关键字排序进
20、行存放n优点：能够根据待查记录的关键字快速找优点：能够根据待查记录的关键字快速找到某个记录到某个记录（1 1）累积文件）累积文件pilepile堆文件堆文件文件体为文件体为无结构记录无结构记录序列序列，通过，通过分隔符分隔符来来划分记录，各划分记录，各记录大记录大小和组成可变。新记小和组成可变。新记录总是添加到文件末录总是添加到文件末尾尾。如日志。如日志loglog，或电，或电子邮件的邮箱文件子邮件的邮箱文件(mailbox)(mailbox)。检索必须检索必须从头开始。从头开始。是一种简单是一种简单的文件组的文件组织方式，当数据难以织方式，当数据难以组织时使用。组织时使用。4 4、记录式文件
21、结构具体实例、记录式文件结构具体实例2 2、顺序文件、顺序文件文件体为文件体为大小相同、格式固定大小相同、格式固定的的排序排序记录序列。记录序列。它由一个它由一个主文件主文件和一个和一个临时文临时文件件组成。组成。记录按某个关键字域记录按某个关键字域(key field)(key field)排序排序，存放在主文件，存放在主文件(master (master file)file)中。中。新记录新记录暂时保存在日志或事务暂时保存在日志或事务文件等临时文件中文件等临时文件中(log file or (log file or transaction file)transaction file)，定期
22、归并定期归并入入主文件，并按正确顺序产生一主文件，并按正确顺序产生一个新文件。个新文件。访问时可以采用二分搜索访问时可以采用二分搜索。在顺序文件（主文件在顺序文件（主文件main main filefile）的基础上，另外建）的基础上，另外建立立索引索引(index)(index)和和溢出文件溢出文件( (overflow file)overflow file)。这样做的这样做的目的是加快顺序文件的目的是加快顺序文件的检检索速度索速度。在索引文件中，可在索引文件中，可将关键将关键字域中的取值划分若干个字域中的取值划分若干个区间区间（如（如AZAZ可以划分为可以划分为A A到到Z Z共共2828
23、个区间），每个区间），每个区间对应一个索引项，个区间对应一个索引项，后者指向该区间的开头记后者指向该区间的开头记录。录。新记录新记录暂时保存在溢暂时保存在溢出文件中，定期归并入主出文件中，定期归并入主文件。文件。主文件中记录要求做到分主文件中记录要求做到分块有序块有序3 3、索引顺序文件、索引顺序文件3 3、索引顺序文件、索引顺序文件关键字逻辑地址姓名其它属性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件顺序文件索引顺序文件特点索引顺序文件特点特点特点通过划分层次，在记录数量较大时，比顺序文件通过划分层次，在记录数量较大时，比顺序文件大大
24、缩短检索时间。大大缩短检索时间。顺序文件是顺序文件是N/2(N/2(这时可使用折半查找这时可使用折半查找) )，而索引顺序文件（一级索引）是而索引顺序文件（一级索引）是i/2 + N/(2i/2 + N/(2* *i) i)，其中其中i i为索引长度。索引还可以是多级的。如：为索引长度。索引还可以是多级的。如：有有1000,0001000,000条记录的顺序文件的平均检索长度条记录的顺序文件的平均检索长度为为500,000500,000，而在添加一个有，而在添加一个有10001000条索引项的条索引项的索引文件后，平均检索长度为索引文件后，平均检索长度为10001000。索引顺序文件限制：索引
25、顺序文件限制：基于文件的一个关键字域基于文件的一个关键字域（属性）进行处理。当需要基于其他域（属性）进行处理。当需要基于其他域而不是关而不是关键字域进行搜索一个记录时，将会受到限制；键字域进行搜索一个记录时，将会受到限制；直接访问磁盘中任何一个地址已知的块。直接访问磁盘中任何一个地址已知的块。记录大小相同。记录大小相同。由主文件和溢出文件组成。由主文件和溢出文件组成。记录位置由哈希函数确定。记录位置由哈希函数确定。检索时给出记录编号，通过哈希函数计算检索时给出记录编号，通过哈希函数计算出该记录在文件中的相对位置。出该记录在文件中的相对位置。访问速度快访问速度快， 通常一次只访问一条记录。通常一
26、次只访问一条记录。5 5、哈希文件或直接文件、哈希文件或直接文件用户在一个文件上的操作：用户在一个文件上的操作：“读读”和和“写写”。 写：存储介质写：存储介质 内存内存 读：内存读：内存 存储介质存储介质顺序存取法顺序存取法: : 按照文件信息的逻辑顺序依次存取。按照文件信息的逻辑顺序依次存取。按记录的排列顺序来存取。如：为了存取记录按记录的排列顺序来存取。如：为了存取记录R Ri i , , 必须先通过记录必须先通过记录R R1 1 R R2 2 R Ri-1i-1 随机存取法随机存取法( (直接存取）直接存取）: :可以按任意的次序对文件可以按任意的次序对文件进行读写操作。如可根据记录的
27、编号来直接存取进行读写操作。如可根据记录的编号来直接存取文件中的任意一个记录文件中的任意一个记录 索引存取：索引存取：对文件中的记录按某个数据项的值进对文件中的记录按某个数据项的值进行排列，从而可以根据键值来快速存取。行排列，从而可以根据键值来快速存取。8.2.2 8.2.2 文件的存取方法文件的存取方法n概念概念n又称索引存取，根据关键字来快速定位又称索引存取，根据关键字来快速定位记录在文件中的位置，从而进行文件内记录在文件中的位置，从而进行文件内容的修改。容的修改。n在具体的查找过程中，分为关键字搜索、在具体的查找过程中，分为关键字搜索、记录的搜索或二者的结合搜索（见下图）记录的搜索或二者
28、的结合搜索（见下图）1 1、关键字存取法、关键字存取法对指定记录对指定记录R Ri i的搜索过程如下：的搜索过程如下：n对文件中的内容进行存取，对文件中的内容进行存取，根据记录是否根据关键根据记录是否根据关键字进行排序字进行排序，可划分为，可划分为n线性搜索法线性搜索法n散列法散列法n二分搜索法二分搜索法（1 1）线性搜索法）线性搜索法特点：最简单、最直观的搜索法。从第一个记录开特点：最简单、最直观的搜索法。从第一个记录开发搜索，直到找到或在未找到情况下搜索到最后发搜索，直到找到或在未找到情况下搜索到最后一个记录结束。搜索时间复杂度和文件中记录长一个记录结束。搜索时间复杂度和文件中记录长度成正
29、比。度成正比。缺点：搜索效率低缺点：搜索效率低。2 2、记录搜索算法、记录搜索算法n定义：根据关键字，采用相应的散列函数，定义：根据关键字，采用相应的散列函数，得到某个记录在文件中的逻辑地址。如果得到某个记录在文件中的逻辑地址。如果有两个关键字对应的地址相同，则采用再有两个关键字对应的地址相同，则采用再散列或其他方法来解决地址冲突问题。散列或其他方法来解决地址冲突问题。n特点：能够根据关键字快速定位相同关键特点：能够根据关键字快速定位相同关键字的记录，在最理想情况下能够一次定位。字的记录，在最理想情况下能够一次定位。（2 2）散列法）散列法n概念：首先要根据关键字大小进行排序，概念：首先要根据
30、关键字大小进行排序，每次取记录中间值和待查关键字进行比每次取记录中间值和待查关键字进行比较，以此类推。较，以此类推。（3 3）二分搜索法）二分搜索法文件的使用文件的使用: :文件的性质决定了文件的使用，文件的性质决定了文件的使用，也决定了也决定了存取存取方式的选择。例如，如源程序文方式的选择。例如，如源程序文件用件用顺序存取法顺序存取法、数据库文件用、数据库文件用随机存取法随机存取法存储介质的特性存储介质的特性 磁带：磁带：适合顺序存取。总是从磁头的当前位适合顺序存取。总是从磁头的当前位置开始读写磁带上的信息。置开始读写磁带上的信息。磁盘：磁盘：既可采用顺序存取方式，又可采用随既可采用顺序存取
31、方式，又可采用随机存取方式。机存取方式。3 3、文件存取方法的相关因素、文件存取方法的相关因素从文件在物理介质上的存放方式来研究文件。从文件在物理介质上的存放方式来研究文件。连续结构（顺序）连续结构（顺序）串联结构串联结构索引结构索引结构8.3 8.3 文件的物理结构与存储设备文件的物理结构与存储设备一个文件的信息存放在一个文件的信息存放在若干连续物理块中若干连续物理块中 优点优点: :简单，适用于一次性简单，适用于一次性写入的操作写入的操作 支持顺序存取和随机支持顺序存取和随机存取，顺序存取速度存取，顺序存取速度快快 所需的磁盘寻道次数所需的磁盘寻道次数和寻道时间最少（因和寻道时间最少（因为
32、由于空间的连续性，为由于空间的连续性，当访问下一个磁盘块当访问下一个磁盘块时，一般无需移动磁时，一般无需移动磁头）头）目录文件名起始地址大小Hello.c22Zl.c95z.out21301518311 1、连续结构、连续结构( (顺序顺序) )缺点缺点: :文件不能动态增长（可能文件末尾处的空块已经文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）分配给别的文件）不利于文件插入和删除不利于文件插入和删除外部碎片问题（反复增删文件后）外部碎片问题（反复增删文件后）文件文件A A第一个物理块号第一个物理块号文件长度（文件长度（4 4）文件说明信息文件说明信息10131211.物理存储设备
33、物理存储设备0 1 2 3物理块号物理块号逻辑块号逻辑块号1. 1.连续结构连续结构( (顺序顺序) )（续）（续）类似于数组类似于数组1. 1.连续结构存储图示连续结构存储图示n概念概念 一个文件的信息存放在若干不连续的物理块中，各块之间通一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。过指针连接，前一个物理块指向下一个物理块。第一个物理块号第一个物理块号文件说明信息文件说明信息2215物理存储设备物理存储设备0 1 2 3物理块号物理块号逻辑块号逻辑块号连接指针连接指针25020 15 22 25思考：如何实现逻辑块号到物理块号的转换？思考：如
34、何实现逻辑块号到物理块号的转换？2 2、串联结构、串联结构类似于链表类似于链表2.2.串联结构图示串联结构图示2.2.串联结构优缺点串联结构优缺点优点优点 提高了磁盘空间利用率提高了磁盘空间利用率, ,不存在外部碎片问题不存在外部碎片问题 有利于文件插入和删除，但效率不高有利于文件插入和删除，但效率不高 有利于文件动态扩充有利于文件动态扩充缺点缺点 存取速度慢，不适于随机存取存取速度慢，不适于随机存取 可靠性问题，如指针出错可靠性问题，如指针出错 更多的寻道次数和寻道时间更多的寻道次数和寻道时间 链接指针占用一定的空间链接指针占用一定的空间3 3、索引结构（考试重点）、索引结构（考试重点）n概
35、念概念 一个文件的信息存放在若干不连续物理块中，一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构系统为每个文件建立一个专用数据结构- -索索引表，并将这些块的块号存放在一个索引表引表，并将这些块的块号存放在一个索引表中中. .3.3.索引结构存储图索引结构存储图一个索引表就是磁盘块地址数组一个索引表就是磁盘块地址数组, ,其中第其中第i i个条目指向个条目指向文件的第文件的第i i块。（每个条目是逻辑块号与物理块号块。（每个条目是逻辑块号与物理块号的映射，需要占据一定的外存空间）的映射，需要占据一定的外存空间） 思考思考 索引表的存放？索引表的存放？ 大文件如何处理？
36、大文件如何处理？3.3.索引结构图示索引结构图示3.3.索引结构优缺点索引结构优缺点优点：优点：保持了链接结构的优点保持了链接结构的优点, ,又解决了其缺点又解决了其缺点即能顺序存取即能顺序存取, ,又能随机存取又能随机存取满足了文件动态增长、插入删除的要求满足了文件动态增长、插入删除的要求（只要有空闲块）（只要有空闲块）能充分利用外存空间能充分利用外存空间缺点：缺点：较多的寻道次数和寻道时间较多的寻道次数和寻道时间. .索引表本身索引表本身带来了系统开销带来了系统开销. .如：内外存空间，存取时间如：内外存空间，存取时间3.3.索引结构索引表组织（考试重点）索引结构索引表组织（考试重点）索引
37、表组织索引表组织多级索引多级索引: :将一个大文件的所有索引表（二级将一个大文件的所有索引表（二级索引索引) )的地址放在另一个索引表（一级索引的地址放在另一个索引表（一级索引) )中。中。多重索引结构多重索引结构图图8.11 8.11 多重索引结构多重索引结构每个文件的索引表为每个文件的索引表为1313个索引个索引项，每项项，每项2 2个字节。个字节。前前1010项直接登记存放文件信息项直接登记存放文件信息的物理块号（直接寻址）的物理块号（直接寻址）; ;第第11 11项指向一个物理块，该块项指向一个物理块，该块中最多可放中最多可放256256个文件物理块个文件物理块的块号（一次间接寻址）。
38、的块号（一次间接寻址）。第第1212和第和第1313项作为二次和三次项作为二次和三次间接寻址间接寻址; ;UNIXUNIX中采用了中采用了三级三级索引结构索引结构后，文件最大可达后，文件最大可达1616兆个物理兆个物理块（块（10+256+25610+256+2562 2+256+2563 3）UNIXUNIX文件系统采用的是多级索引结构文件系统采用的是多级索引结构( (综合模式综合模式) )。作业思考题作业思考题1、 文件系统采用多重索引结构搜索文件内容。文件系统采用多重索引结构搜索文件内容。设块长为设块长为512字节，每个块号长字节，每个块号长3字节，如字节，如果不考虑逻辑块号在物理块中所
39、占的位置，果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件分别求二级索引和三级索引时可寻址的文件最大长度。最大长度。 4.4.存取设备、存取方法和物理结构之间的关系存取设备、存取方法和物理结构之间的关系存取设备存取设备 磁盘磁盘磁带磁带物理结构物理结构 顺序结构顺序结构链接结构链接结构索引结构索引结构顺序结构顺序结构存取方法存取方法 直接或顺序直接或顺序顺序顺序直接或顺序直接或顺序顺序顺序文件长度文件长度 固定固定可变，固可变，固定定可变，固定可变，固定固定固定顺序存取设备：顺序存取设备：只有在前面的物理块被访问过只有在前面的物理块被访问过之后，才能存取后续的物理块
40、的内容。如之后，才能存取后续的物理块的内容。如 ：磁带：磁带直接（随机）存取设备：直接（随机）存取设备：存取磁盘上任一物理块存取磁盘上任一物理块的时间不依赖于该物理块所处的位置，如的时间不依赖于该物理块所处的位置，如 ：磁盘磁盘固定头磁盘固定头磁盘：每个磁道设置一个磁头，变换每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本磁道时不需要磁头的机械移动，速度快但成本高高移动头磁盘移动头磁盘：一个盘面只有一个磁头，变换一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低磁道时需要移动磁头，速度慢但成本低8.3.2 8.3.2 文件的存储设备文件的存储设备1 1、磁带顺序存储
41、设备、磁带顺序存储设备图8.12磁带的结构n影响磁带设备的存取速度或数据传输率因素影响磁带设备的存取速度或数据传输率因素n信息密度信息密度n磁带速度磁带速度n块间间隙块间间隙2 2、直接存储设备（随机存取）、直接存储设备（随机存取）图图8.138.13磁盘的结构磁盘的结构柱面柱面扇区扇区磁臂磁臂磁头磁头扇区扇区SectorSector：介质划分的介质划分的最小单位最小单位块块( (簇簇)Block)Block：与内存交换与内存交换数据的最小单位数据的最小单位文件卷（文件卷（VolumeVolume）：）：一个一个独立的可装卸的文件存储独立的可装卸的文件存储介质。一个卷被分成几个介质。一个卷被分
42、成几个部分：部分：如卷控制区、目录如卷控制区、目录表区、文件存储区，卷资表区、文件存储区，卷资源表源表柱面柱面CyclinderCyclinder磁道磁道tracktrack物理地址形式：物理地址形式：磁头号、磁头号、磁道号、扇区号磁道号、扇区号2 2、直接存储设备（随机存取）图示介绍、直接存储设备（随机存取）图示介绍2 2、直接存储设备（随机存取）、直接存储设备（随机存取） 磁盘完成过程由磁盘完成过程由三个动作三个动作组成：组成：寻道（时间）寻道（时间）：磁头移动定位到指定磁道。：磁头移动定位到指定磁道。旋转延迟（时间）旋转延迟（时间）：等待指定扇区从磁头下旋转经过：等待指定扇区从磁头下旋转
43、经过数据传输（时间）数据传输（时间）：数据在磁盘与内存之间的实际传输：数据在磁盘与内存之间的实际传输 光盘光盘 光盘容量大，速度快，价格便宜，但一般不可写光盘容量大，速度快，价格便宜，但一般不可写 可读写光盘驱动器价格贵，写过程很麻烦可读写光盘驱动器价格贵，写过程很麻烦 光盘的空间结构与磁盘类似光盘的空间结构与磁盘类似 磁带磁带预分配预分配(preallocation(preallocation) )：创建时：创建时( (这时已知文件长度这时已知文件长度) )一次分配指定的存储空间，如文件复制时的目标文一次分配指定的存储空间，如文件复制时的目标文件。件。动态分配动态分配(dynamic all
44、ocation)(dynamic allocation)：需要存储空间时才：需要存储空间时才分配（创建时无法确定文件长度），如写入数据到分配（创建时无法确定文件长度），如写入数据到文件。文件。1. 1. 新创建文件的存储空间（文件长度）分配方法新创建文件的存储空间（文件长度）分配方法8.4 8.4 文件存储空间管理文件存储空间管理( (分配与回收）分配与回收）2. 2. 文件存储单位文件存储单位: : 簇（簇（clustercluster）簇的大小簇的大小簇较大簇较大：提高：提高I/OI/O访问性能访问性能，减小，减小管理开销管理开销；但；但簇内碎片浪费簇内碎片浪费问题较严重；问题较严重；簇较
45、小簇较小：簇内的碎片浪费较小，特别是：簇内的碎片浪费较小，特别是大量小大量小文件文件时有利；但存在时有利；但存在簇编号空间不够簇编号空间不够的问题的问题（如如FAT12FAT12、1616、3232）；）；文件的存储空间通常由多个分立的文件的存储空间通常由多个分立的簇簇组成，而每个簇包组成，而每个簇包含若干个含若干个连续的扇区连续的扇区(sector)(sector)。2. 2. 文件存储单位文件存储单位: : 簇（簇（clustercluster） 簇的分配方法：簇的分配方法：两种两种簇大小可变，其上限较大簇大小可变，其上限较大：I/OI/O访问性能较好，访问性能较好，文件存储空间的管理困难
46、（类似于动态分区文件存储空间的管理困难（类似于动态分区存储管理）存储管理）簇大小固定，较小：簇大小固定，较小：文件存储空间使用灵活，文件存储空间使用灵活，但但I/OI/O访问性能下降，文件管理所需空间开销访问性能下降，文件管理所需空间开销较大较大3. 3. 文件存储空间管理方法文件存储空间管理方法连续分配连续分配(contiguous)(contiguous)：只需记录：只需记录第一个簇第一个簇的位置的位置，适用于预分配方法。，适用于预分配方法。链式分配链式分配(chained)(chained)：在每个簇中有：在每个簇中有指向下指向下一个簇的指针。一个簇的指针。索引分配索引分配(indexe
47、d)(indexed)：文件的第一个簇中记：文件的第一个簇中记录了该文件的录了该文件的其他簇的位置其他簇的位置。3 3、磁盘空闲空间管理方法、磁盘空闲空间管理方法位示图位示图(bitmap) : (bitmap) : 块寻址算法块寻址算法空闲空间链接空闲空间链接(chained free space)(chained free space)： 扩展：扩展：成组链接法成组链接法空闲文件目录空闲文件目录：在一个空闲簇中记录其他几个：在一个空闲簇中记录其他几个空闲簇的位置。空闲簇的位置。返回 磁盘空闲空间管理的数据结构通常称为磁盘空闲空间管理的数据结构通常称为磁盘分配表磁盘分配表， 分配的基本单位是
48、簇。分配的基本单位是簇。 空闲空间的三种管理方法：空闲空间的三种管理方法：可以上述方法结合，应用于不同的场合。如：位示图应用于索可以上述方法结合，应用于不同的场合。如：位示图应用于索引结点表格，链接和索引结合应用于文件区的空闲空间。引结点表格，链接和索引结合应用于文件区的空闲空间。1. 1.空闲文件目录空闲文件目录将文件存储设备上的每个连续空闲区看作将文件存储设备上的每个连续空闲区看作一个空白文一个空白文件件，系统为所有空白文件单独建立，系统为所有空白文件单独建立一个目录一个目录。每个空。每个空白文件在这个目录中占用一个表目。白文件在这个目录中占用一个表目。表目的内容包括第一个空白块的地址（物
49、理块号），表目的内容包括第一个空白块的地址（物理块号），空白块的数目。如：空白块的数目。如：分配和回收过程：扫描目录，找到符合条件的分配和回收过程：扫描目录，找到符合条件的项。项。序号第一个空白块号空白块个数备注：物理块号153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-思考：空闲文件目录存储在哪里？思考：空闲文件目录存储在哪里？2.2.空闲块链空闲块链在每个空白块中建立一个链接指针，指向下一个空白在每个空白块中建立一个链接指针，指向下一个空白块的位置，从而将所有空白块链接在一起，设置一个块的位置，从而将所有空白块链接在一起，设置一个
50、头指针指向空白块链的第一个物理块。头指针指向空白块链的第一个物理块。分配时，从头指针的位置依次取下几块空白块分配给分配时，从头指针的位置依次取下几块空白块分配给文件，当撤消文件时，回收。文件，当撤消文件时，回收。内存消耗少，但遍历的效率低，内存消耗少，但遍历的效率低，I/OI/O负担重。改进的负担重。改进的方法是成组链法。方法是成组链法。YWZ 首指针首指针X XXYWZ改进：一块中存放多个空闲块的块号，成组块链法？改进：一块中存放多个空闲块的块号，成组块链法？（1 1）空闲块链链接方法）空闲块链链接方法n按空闲区大小顺序链接按空闲区大小顺序链接n按释放顺序链接按释放顺序链接n以上两种链接方法
