《操作系统原理》课件第六章 文件系统.pptx

1、1.1.文件系统概念文件系统概念2.2.文件逻辑结构与存取方法文件逻辑结构与存取方法3.3.文件的物理结构与存储设备文件的物理结构与存储设备4.4.文件存储空间管理文件存储空间管理第第6章章 文件系统文件系统(外存管理）外存管理）5.5.文件目录管理文件目录管理6.6.文件存取控制文件存取控制7.7.文件使用文件使用8.8.文件系统层次模型文件系统层次模型第第6 6章章 文件系统文件系统(外存管理）外存管理）1、信息的存储单位信息的存储单位是文件；是文件；2、文件系统功能：、文件系统功能：负责信息的组织、存储和访问负责信息的组织、存储和访问；3、文件系统的特点、文件系统的特点 提供高效、快速和

2、方便的提供高效、快速和方便的信息存储信息存储和和访问功能访问功能。6.1 文件系统概念文件系统概念6.1.1 6.1.1 文件系统功能文件系统功能1 1、操作系统的软硬件管理操作系统的软硬件管理2 2、文件管理功能、文件管理功能 （1 1）方便用户对）方便用户对文件的访问和控制文件的访问和控制 （2 2）并发）并发文件访问和控制文件访问和控制 （3 3）统一）统一的用户接口的用户接口6.1.16.1.1文件系统功能文件系统功能2、文件管理功能、文件管理功能（4）设置多种文件访问）设置多种文件访问权限权限（5）优化性能：）优化性能：存储效率、检索性能、读写性能；存储效率、检索性能、读写性能；（6

3、）差错恢复）差错恢复：验证文件的正确性，具有一定的差错恢复能力。：验证文件的正确性，具有一定的差错恢复能力。2 2、文件管理的目的、文件管理的目的1.文件概念与文件名文件概念与文件名 文件是文件是具有名字的一段程序或数据的集合具有名字的一段程序或数据的集合，是相关，是相关字符流的集合字符流的集合或或相关记录的集合相关记录的集合。文件名是文件的标。文件名是文件的标识符号。识符号。6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念2、文件组成文件组成（1）文件体：）文件体：文件本身的信息文件本身的信息（2）文件说明：）文件说明：文件存储和管理信息文件存储和管理信息6.1.2

4、6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念对操作系统的文件系统而言,一个源程序、一批数据、一篇文章或一张图片等都可以被称为文件,只要它是()连续分布在一片磁盘区域中的信息集合A采用链接方式连接起来的多个磁盘块组成的信息集合B逻辑上具有完整意义的信息集合C属于同一个用户的一个信息集合D提交单选题1分3.3.文件系统基本概念文件系统基本概念文件系统文件系统是操作系统中是操作系统中管理文件的机构管理文件的机构，是与管理文件有，是与管理文件有关的关的软件以及数据软件以及数据的统称；它负责为用户的统称；它负责为用户建立、撤销、读建立、撤销、读写、修改和复制写、修改和复制文件，能提供文件

5、文件，能提供文件存储和访问存储和访问功能。功能。6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念4.4.文件系统特点文件系统特点（1 1）友好的用户界面；）友好的用户界面；（2 2）文件操作对用户透明：对文件按名存取；）文件操作对用户透明：对文件按名存取；（3 3）容易实现文件共享：文件可以被多个用户共享；）容易实现文件共享：文件可以被多个用户共享；（4 4）存储介质空间大、价格便宜。）存储介质空间大、价格便宜。6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念5 5、文件分类、文件分类（1 1）按存放时限按存放时限临时文件、永久文件和档案文件。临时文件、永久

6、文件和档案文件。（2 2）按设备类型按设备类型磁盘文件、磁带文件、卡片文件和打印文件等。磁盘文件、磁带文件、卡片文件和打印文件等。6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念5.5.文件分类文件分类（3 3）按文件的组织结构按文件的组织结构 文件的逻辑结构：文件的逻辑结构：流式文件流式文件和和记录式记录式文件。文件。文件的物理结构（物理文件）：文件的物理结构（物理文件）：顺序文件、链接文件顺序文件、链接文件和索引文件等。和索引文件等。6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念逻辑文件可以有_这几种形式。目录文件A永久文件B流式文件C文本

7、文件D记录式文件E提交多选题1分5 5、文件分类、文件分类（4）按文件的性质和用途划分按文件的性质和用途划分 系统文件。用户只能调用，不能修改；系统文件。用户只能调用，不能修改；库文件。允许用户读取和执行，不允许修改；库文件。允许用户读取和执行，不允许修改；用户文件。文件的建立者能够拥有所有的权限用户文件。文件的建立者能够拥有所有的权限6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念如果按文件的用途来分类,可将文件分为_。系统文件A永久文件B用户文件C逻辑文件D库文件E提交多选题1分5、文件分类、文件分类（5）按组织形式按组织形式 普通文件。包括系统文件、用户文件和库函

8、数文件普通文件。包括系统文件、用户文件和库函数文件和实用程序等；和实用程序等；目录文件。由目录信息构成的特殊文件；目录文件。由目录信息构成的特殊文件；特殊文件。所有输入、输出设备组成的文件特殊文件。所有输入、输出设备组成的文件6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念6 6、文件分类的原因、文件分类的原因 为了更好地管理和使用，不仅提高了文件的存为了更好地管理和使用，不仅提高了文件的存取速度，对文件的共享和保护也有利。取速度，对文件的共享和保护也有利。6.1.2 6.1.2 文件与文件系统的基本概念文件与文件系统的基本概念使用文件的用户需要记住的是()存储块的状况

9、,即已用还是空闲A文件在磁盘上的存储位置B文件中各个记录所在的块的块号C文件的名字D提交单选题1分磁盘设备驱动程序磁盘设备驱动程序磁带设备驱动程序磁带设备驱动程序基本文件系统基本文件系统基本基本I/O管理程序管理程序逻辑逻辑I/O堆堆顺序顺序索引顺序索引顺序索引索引哈希哈希用户程序用户程序1 1、文件系统结构图文件系统结构图6.1.3 6.1.3 文件系统的结构和功能元素文件系统的结构和功能元素2、文件系统结构组成、文件系统结构组成（1）设备驱动程序）设备驱动程序：负责启动该设备上的：负责启动该设备上的I/O操作，处理操作，处理I/O请求请求的完成；的完成；（2）基本文件系统（物理）基本文件系

10、统（物理I/O层）层）：处理与磁盘或磁带交换的数：处理与磁盘或磁带交换的数据块。据块。（3）基本）基本I/O管理程序管理程序：负责所有文件负责所有文件I/O的开始或结束、选择执的开始或结束、选择执行文件的行文件的I/O设备和外存的分配。设备和外存的分配。6.1.3 6.1.3 文件系统的结构和功能元素文件系统的结构和功能元素2、文件系统结构组成、文件系统结构组成（4）逻辑）逻辑I/O：使用户和应用程序能够访问到记录。使用户和应用程序能够访问到记录。物理物理I/O层处理的是数据块，逻辑层处理的是数据块，逻辑I/O处理的是文件记录。处理的是文件记录。（5）访问方法层）访问方法层：与用户最近的一层。

11、：与用户最近的一层。6.1.3 6.1.3 文件系统的结构和功能元素文件系统的结构和功能元素3.3.文件系统服务功能元素文件系统服务功能元素（1 1）文件访问：）文件访问：文件的创建、打开、关闭和读写；文件的创建、打开、关闭和读写；（2 2）目录管理：）目录管理：用于文件访问和控制的信息用于文件访问和控制的信息（3 3）文件结构管理：）文件结构管理：划分记录，包括顺序与索引结构划分记录，包括顺序与索引结构6.1.3 6.1.3 文件系统的结构和功能元素文件系统的结构和功能元素3.文件系统服务功能元素文件系统服务功能元素（4）访问控制：）访问控制：并发访问和用户权限；并发访问和用户权限；（5）限

12、额）限额(quota)：限制每个用户能够建立的文件数目、占用限制每个用户能够建立的文件数目、占用外存空间大小等；外存空间大小等；（6）审计）审计(auditing)：记录对指定文件的使用信息，保存在日记录对指定文件的使用信息，保存在日志中；志中；6.1.3 6.1.3 文件系统的结构和功能元素文件系统的结构和功能元素3.文件系统服务功能元素文件系统服务功能元素（7）文件的分块存储：）文件的分块存储：与外存的存储块相配合与外存的存储块相配合（8）I/O缓冲和调度：缓冲和调度：性能优化性能优化（9）文件定位：）文件定位：在外存上查找文件的各个存储块在外存上查找文件的各个存储块6.1.3 6.1.3

13、 文件系统的结构和功能元素文件系统的结构和功能元素3.文件系统服务功能元素文件系统服务功能元素（10）外存存储空间管理：）外存存储空间管理：如硬盘空间分配和释放；如硬盘空间分配和释放；（11）外存设备访问和控制：）外存设备访问和控制：包括由设备驱动程序支持的包括由设备驱动程序支持的各种基本文件系统如硬盘等。各种基本文件系统如硬盘等。6.1.3 6.1.3 文件系统的结构和功能元素文件系统的结构和功能元素文件系统应具有的功能包括()。实现“按名存取”外存上的文件A分配文件的存储空间B实现文件目录管理C提供合适的存取方法以适应各种不同的应用D实现文件的共享、保护和保密E提交多选题1分6.2 6.2

14、 文件的逻辑结构与存取方法文件的逻辑结构与存取方法 文件逻辑结构主要讨论文件逻辑结构主要讨论文件的内部逻辑结构文件的内部逻辑结构，主，主要考虑因素是文件要考虑因素是文件存储性能存储性能和和访问性能访问性能。6.2.1 6.2.1 文件的逻辑结构文件的逻辑结构1 1、文件的逻辑结构定义文件的逻辑结构定义是指文件内部信息的组织方式，即文件是指文件内部信息的组织方式，即文件内部的逻辑内部的逻辑结构结构，是用户可以直接处理的数据及其结构。它，是用户可以直接处理的数据及其结构。它独独立于在外存上的物理存储。立于在外存上的物理存储。6.2.1 6.2.1 文件的逻辑结构文件的逻辑结构2 2、文件逻辑结构的

15、设计要求文件逻辑结构的设计要求（1 1）访问性能：便于检索和修改；）访问性能：便于检索和修改；（2 2）存储性能：向物理存储转换方便、节省空间）存储性能：向物理存储转换方便、节省空间3 3、文件信息的不同组织层次：文件信息的不同组织层次：域、记录、文件域、记录、文件文件的逻辑结构是指()文件所在的设备的结构A文件在设备中的存储方式B文件目录的结构C文件的使用者组织文件中信息的方式D提交单选题1分4、文件的逻辑结构文件的逻辑结构分类分类（1）无结构文件）无结构文件 文件体为文件体为字节流字节流，不划分记录，顺序访问，每，不划分记录，顺序访问，每次读写访问可以指定任意数据长度；次读写访问可以指定任

16、意数据长度；当前操作系统中常用的文件组织。当前操作系统中常用的文件组织。6.2.1 6.2.1 文件的逻辑结构文件的逻辑结构 4、文件的逻辑结构文件的逻辑结构分类分类（2）有结构文件记录式文件）有结构文件记录式文件 记录概念：记录概念：一个具有特殊意义的完整的信息单位一个具有特殊意义的完整的信息单位6.2.1 6.2.1 文件的逻辑结构文件的逻辑结构图图6.2 6.2 记录组成记录组成典型记录的组成元素典型记录的组成元素4 4、文件的逻辑结构文件的逻辑结构分类分类（2 2）记录式结构文件分类记录式结构文件分类 连续结构连续结构 多重结构多重结构 转置结构转置结构 顺序结构顺序结构6.2.1 6

17、.2.1 文件的逻辑结构文件的逻辑结构 连续结构连续结构概念：把记录按生成的先后顺序连续排列的逻辑结构；概念：把记录按生成的先后顺序连续排列的逻辑结构；特点：记录的排列顺序与记录内容无关，有利于记录的追特点：记录的排列顺序与记录内容无关，有利于记录的追加和变更；加和变更；缺点：查找性能比较差。缺点：查找性能比较差。（2 2）记录式结构文件分类记录式结构文件分类6.2.1 6.2.1 文件的逻辑结构文件的逻辑结构多重结构多重结构概念：把记录按概念：把记录按关键字关键字和和记录名记录名排列成行列式结构，则一个排列成行列式结构，则一个包含包含n个记录名、个记录名、m个关键字个关键字的文件构成一的文件

18、构成一nm维行列式。维行列式。特点：能根据关键字和记录名快速定位某条记录特点：能根据关键字和记录名快速定位某条记录缺点：浪费空间，缺点：浪费空间，n条记录需要条记录需要n*m的空间的空间（2 2）记录式结构文件分类记录式结构文件分类多重结构多重结构 改进措施：采用多重队列。改进措施：采用多重队列。将行列式中为将行列式中为0的项去除，以关键字的项去除，以关键字ki为队首，以包含为队首，以包含关键字关键字ki的记录为队列元素构成一个记录队列。的记录为队列元素构成一个记录队列。M个关个关键字就构成了多个队列。键字就构成了多个队列。（2 2）记录式结构文件分类记录式结构文件分类多重结构及改进图多重结构

19、及改进图图图6.36.3文件的记录名和文件的记录名和关键字构成的行列式关键字构成的行列式图图6.46.4文件的多重结构文件的多重结构转置结构转置结构 把含有相同关键字的记录指针全部指向该关键字，即把把含有相同关键字的记录指针全部指向该关键字，即把所有与同一关键字对应的记录指针连续置于目录中该关所有与同一关键字对应的记录指针连续置于目录中该关键字位置，是对多重结构的变化。键字位置，是对多重结构的变化。（2 2）记录式结构文件分类记录式结构文件分类转置结构转置结构 图图6.56.5文件的转置结构文件的转置结构（2 2）记录式结构文件分类记录式结构文件分类顺序结构（索引结构）顺序结构（索引结构）概念

20、：按照某种关键字排序进行存放概念：按照某种关键字排序进行存放 优点：能够根据待查记录的关键字快速找到某个记录优点：能够根据待查记录的关键字快速找到某个记录（2 2）记录式结构文件分类记录式结构文件分类（1）累积文件）累积文件pile堆文件堆文件 文件体为文件体为无结构记录序列无结构记录序列，通过，通过分隔符分隔符来划分记录，各来划分记录，各记录大小和组成可变。新记录总是添加到文件末尾记录大小和组成可变。新记录总是添加到文件末尾。如。如日志日志log，或电子邮件的邮箱文件，或电子邮件的邮箱文件(mailbox)。检索必须检索必须从头开始。从头开始。是一种简单的文件组织方式，当数据难以组织时使用。

21、是一种简单的文件组织方式，当数据难以组织时使用。5、记录式文件结构具体实例、记录式文件结构具体实例（1）累积文件）累积文件pile堆文件堆文件5、记录式文件结构具体实例、记录式文件结构具体实例（2 2）顺序文件）顺序文件文件体为文件体为大小相同、格式固定大小相同、格式固定的的排序排序记录序列；记录序列；它由一个它由一个主文件主文件和一个和一个临时文件临时文件组成；组成；记录按某个关键字域记录按某个关键字域排序排序，存放在主文件中；，存放在主文件中；5、记录式文件结构具体实例、记录式文件结构具体实例（2 2）顺序文件）顺序文件新记录新记录暂时保存在日志或事务文件等临时文件中，暂时保存在日志或事务

22、文件等临时文件中，定期归并定期归并入主文件，并按正确顺序产生一个新文件；入主文件，并按正确顺序产生一个新文件；访问时可以采用访问时可以采用二分搜索二分搜索。5、记录式文件结构具体实例、记录式文件结构具体实例（2）顺序文件）顺序文件5、记录式文件结构具体实例、记录式文件结构具体实例（3）索引顺序文件）索引顺序文件在顺序文件的基础上，另外建立在顺序文件的基础上，另外建立索引索引和和溢出文件溢出文件；在索引文件中，可在索引文件中，可将关键字域中的取值划分若干个区间将关键字域中的取值划分若干个区间，每个区间对应一个索引项。每个区间对应一个索引项。新记录新记录暂时保存在溢出文件中，定期归并入主文件；暂时

23、保存在溢出文件中，定期归并入主文件；主文件中记录要求做到主文件中记录要求做到分块有序分块有序。5 5、记录式文件结构具体实例、记录式文件结构具体实例（3 3）索引顺序文件）索引顺序文件5、记录式文件结构具体实例、记录式文件结构具体实例关键字逻辑地址姓名其它属性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件顺序文件5 5、记录式文件结构具体实例、记录式文件结构具体实例（3）索引顺序文件）索引顺序文件（4）哈希文件或直接文件）哈希文件或直接文件 （记录逻辑地址通过关键字哈希之后直接获得）（记录逻辑地址通过关键字哈希之后直接获得）直接访问磁盘中

24、任何一个地址已知的块；直接访问磁盘中任何一个地址已知的块；由主文件和溢出文件组成；由主文件和溢出文件组成；记录位置由哈希函数确定。记录位置由哈希函数确定。访问速度快；访问速度快；5 5、记录式文件结构具体实例、记录式文件结构具体实例1 1、文件内容操作类型文件内容操作类型（1 1）读：存储介质）读：存储介质 内存内存 （2 2）写：内存）写：内存 存储介质存储介质6.2.2 6.2.2 文件的存取方法文件的存取方法2.2.文件存取方法文件存取方法（1 1）顺序存取法）顺序存取法:按照文件信息的逻辑顺序依次存取；按照文件信息的逻辑顺序依次存取；（2 2）随机存取法）随机存取法(直接存取）直接存取

25、）:可以按任意的次序对文件可以按任意的次序对文件进行读写操作；进行读写操作；（3 3）索引存取：）索引存取：对文件中的记录按某个数据项的值进行对文件中的记录按某个数据项的值进行排列，可根据键值来快速存取。排列，可根据键值来快速存取。6.2.2 6.2.2 文件的存取方法文件的存取方法3、记录搜索算法、记录搜索算法（1）线性搜索法线性搜索法（用在顺序文件）（用在顺序文件）（2）散列法散列法（用在哈希文件）（用在哈希文件）（3）二分搜索法二分搜索法（用在是有序文件）（用在是有序文件）6.2.2 文件的存取方法文件的存取方法3、记录搜索算法、记录搜索算法（1）线性搜索法）线性搜索法特点：从第一个记录

26、开发搜索，直到找到或在未找到情特点：从第一个记录开发搜索，直到找到或在未找到情况下搜索到最后一个记录结束。况下搜索到最后一个记录结束。缺点：搜索效率低。缺点：搜索效率低。6.2.2 6.2.2 文件的存取方法文件的存取方法3、记录搜索算法、记录搜索算法（2）散列法）散列法 定义：根据关键字值，采用相应的散列函数，得到定义：根据关键字值，采用相应的散列函数，得到某个记录在文件中的逻辑地址。某个记录在文件中的逻辑地址。特点：能够根据关键字快速定位相同关键字的记录，特点：能够根据关键字快速定位相同关键字的记录，在最理想情况下能够一次定位。在最理想情况下能够一次定位。6.2.2 文件的存取方法文件的存

27、取方法3 3、记录搜索算法、记录搜索算法（3 3）二分搜索法）二分搜索法 首先要根据关键字大小进行排序，每次取记录中间值和首先要根据关键字大小进行排序，每次取记录中间值和待查关键字进行比较，以此类推。待查关键字进行比较，以此类推。6.2.2 6.2.2 文件的存取方法文件的存取方法4、影响文件存取方法的因素影响文件存取方法的因素 （1）文件的使用文件的使用 文件的性质决定了文件的使用，也决定了文件的性质决定了文件的使用，也决定了存取存取方式的选方式的选择。例如，如源程序文件用择。例如，如源程序文件用顺序存取法顺序存取法、数据库文件用、数据库文件用随随机存取法机存取法6.2.2 6.2.2 文件

28、的存取方法文件的存取方法4 4、影响文件存取方法的因素影响文件存取方法的因素（2 2）存储介质的特性存储介质的特性 磁带：磁带：适合顺序存取。适合顺序存取。磁盘：磁盘：既可采用顺序存取方式，又可采用随机存既可采用顺序存取方式，又可采用随机存取方式。取方式。6.2.2 文件的存取方法文件的存取方法6.3 文件的物理结构与存储设备（重点）文件的物理结构与存储设备（重点）1、文件的物理结构、文件的物理结构2、文件的存储设备、文件的存储设备从文件在物理介质上的存放方式来研究文件。从文件在物理介质上的存放方式来研究文件。1.1.连续结构（顺序）连续结构（顺序）2.2.串联结构串联结构3.3.索引结构索引

29、结构(重点）重点）6.3.1 6.3.1 文件的物理结构文件的物理结构（1）一个文件的信息存放在若干连续物理块中。一个文件的信息存放在若干连续物理块中。目录文件名起始地址大小Hello.c22Zl.c95z.out21301516311、连续结构、连续结构(顺序结构顺序结构)（2）优点优点简单，适用于一次性写入的操作；简单，适用于一次性写入的操作；支持支持顺序存取和随机存取，速度快顺序存取和随机存取，速度快；所需的所需的磁盘寻道次数和寻道时间最少磁盘寻道次数和寻道时间最少。1 1、连续结构、连续结构(顺序顺序)（3）缺点缺点 文件不能动态增长（可能文件末尾处的空块已经分配给别文件不能动态增长（

30、可能文件末尾处的空块已经分配给别的文件）的文件）不利于文件插入和删除不利于文件插入和删除 外部碎片问题（反复增删文件后外部碎片问题（反复增删文件后）1 1、连续结构、连续结构(顺序顺序)文件文件A A第一个物理块号第一个物理块号文件长度（文件长度（4 4）文件说明信息文件说明信息1010131312121111.物理存储设备物理存储设备0 1 2 30 1 2 3物理块号物理块号逻辑块号逻辑块号1.1.连续结构连续结构(顺序顺序)类似于数组1.1.连续结构存储图示连续结构存储图示连续存储结构图连续存储结构图（1）概念概念 一个文件的信息存放在一个文件的信息存放在若干不连续的物理块若干不连续的物

31、理块中，各块之间通中，各块之间通过指针连接，前一个物理块指向下一个物理块。过指针连接，前一个物理块指向下一个物理块。2 2、串联结构、串联结构第一个物理块号第一个物理块号文件说明信息文件说明信息22221515物理存储设备物理存储设备0 1 2 30 1 2 3物理块号物理块号逻辑块号逻辑块号连接指针连接指针25250 020 15 22 2520 15 22 252、串联结构、串联结构2.2.串联结构串联结构图示图示链式存储结构图链式存储结构图2.2.串联结构串联结构优缺点优缺点（2 2）优点优点 提高了磁盘空间利用率提高了磁盘空间利用率,不存在外部碎片问题不存在外部碎片问题；有利于文件插入

32、和删除，但效率不高；有利于文件插入和删除，但效率不高；有利于文件动态扩充有利于文件动态扩充。（3）缺点缺点 存取速度慢，不适于随机存取；存取速度慢，不适于随机存取；可靠性问题，如指针出错；可靠性问题，如指针出错；更多的寻道次数和寻道时间更多的寻道次数和寻道时间；链接指针占用一定的空间。链接指针占用一定的空间。2.2.串联结构串联结构优缺点优缺点某文件共有4个记录L0L3,采用链接存储结构,每个记录及链接指针占用一个磁盘块,主存储器中的磁盘缓冲区的大小与磁盘块的大小相等。为了在L2和L3之间插入一个记录L2,需要进行的磁盘操作有()4次读盘和2次写盘A4次读盘和1次写盘B3次读盘和2次写盘C3次

33、读盘和1次写盘D提交单选题1分3 3、索引结构（、索引结构（重点）重点）主流的文件物理结构。主流的文件物理结构。（1）概念概念 一个文件的信息存放在若干一个文件的信息存放在若干不连续不连续物理块中，系统为物理块中，系统为每个每个文件文件建立一个专用数据结构建立一个专用数据结构-索引表索引表，并将这些块的块号，并将这些块的块号存放在一个索引表中存放在一个索引表中。（索引表类似于目录表索引表类似于目录表）（2）索引表索引表 一个索引表就是磁盘块地址数组一个索引表就是磁盘块地址数组,其中第其中第i个条目指向文件的第个条目指向文件的第i块。块。索引表每个条目是索引表每个条目是逻辑块号与物理块号的映射逻

34、辑块号与物理块号的映射，需要占据一定，需要占据一定的外存空间。的外存空间。（与内存管理中页表相似）（与内存管理中页表相似）3 3、索引结构、索引结构 思考思考 索引表的存放？索引表的存放？大文件如何处理？大文件如何处理？3 3、索引结构、索引结构 索引结构（一级索引）索引结构（一级索引）3 3、索引结构、索引结构3 3、图示、图示索引存储结构图索引存储结构图3.3.索引结构索引结构优缺点优缺点（3 3）优点：保持了链接结构的优点优点：保持了链接结构的优点,又解决了其缺点。又解决了其缺点。即能即能顺序存取顺序存取,又能随机存取又能随机存取 满足了满足了文件动态增长、插入删除的要求文件动态增长、插

35、入删除的要求（只要有空闲块）（只要有空闲块）能充分利用外存空间能充分利用外存空间能够实现离散存储和随机访问，能够实现离散存储和随机访问，综合了综合了连续存储（随机访连续存储（随机访问）问）和和链式存储（离散存储）链式存储（离散存储）的优点。的优点。（4 4）缺点缺点 较多的寻道次数和寻道时间较多的寻道次数和寻道时间，索引表本身带来了系索引表本身带来了系统开销统开销。如：内外存空间，存取时间。如：内外存空间，存取时间。3.3.索引结构索引结构优缺点优缺点文件在相应存储介质上的组织方式也有差异。通常文件的存储结构有_。流式结构A顺序结构B链接结构C记录式结构D索引结构E提交多选题1分4 4、索引表

36、组织索引表组织（1）索引表组织索引表组织 又称多级索引又称多级索引，除了除了最后一层索引表所指的物理块存放最后一层索引表所指的物理块存放文件信息文件信息以外，其它层次的索引表存放着下一层索引表以外，其它层次的索引表存放着下一层索引表的物理块地址。的物理块地址。多重索引结构多重索引结构图图6.11 6.11 多重索引（二级索引）结构多重索引（二级索引）结构案例：案例：UNIXUNIX文件系统采用的多级索引结构文件系统采用的多级索引结构Unix 多级索引存储结构图多级索引存储结构图分析：分析：每个文件的索引表为每个文件的索引表为1313个索引项，个索引项，每项每项2 2个字节个字节；直接寻址（一级

37、索引）直接寻址（一级索引）：前：前1010项直接登记存放文件信息的物项直接登记存放文件信息的物理块号理块号;一次间接寻址（二级索引）一次间接寻址（二级索引）：第：第11 11项指向一个物理块，该块项指向一个物理块，该块中最多可放中最多可放256256个文件物理块的块号；个文件物理块的块号；UNIX文件系统采用的是多级索引结构。文件系统采用的是多级索引结构。分析：分析：二次和三次间接寻址二次和三次间接寻址：分别为第：分别为第12和第和第13项；项；采用了采用了三级间接三级间接索引结构后，索引结构后，Unix文件最大可达文件最大可达16兆个兆个物理块（物理块（10+256+2562+2563）=（

38、10+256+216+224）UNIXUNIX文件系统采用的是多级索引结构文件系统采用的是多级索引结构 设文件索引节点中有7个地址项,其中4个地址项为直接地址索引,2个地址项是一级间接地址索引,1个地址项是二级间接地址索引,每个地址项大小为4字节,若磁盘索引块和磁盘数据块大小均为256字节,则可表示的单个文件的最大长度是()。33KBA519KBB1057KBC16513KBD提交单选题1分下列文件物理结构中,适合随机访问且易于文件扩展的是()。连续结构A索引结构B链式结构且磁盘块定长C链式结构且磁盘块变长D提交单选题1分某旅行社实行会员制,成为会员的游客的信息都登记在会员文件中。会员文件的主

39、要用途是存储、检索、增删和修改会员信息,每个会员占用文件中的一条记录。由于生意兴隆,会员文件的规模很大。为了快速完成对该文件的每一次操作,并充分利用存储该文件的设备的存储空间,适宜于该文件的存储结构是()记录结构A索引结构B链接结构C顺序结构D提交单选题1分 某文件系统采用索引文件结构，设文件索引表的每个表目占2个字节，磁盘块大小为512B。试问该文件系统采用直接、一次间接和二次间接索引能管理的最大磁盘空间为多少字节?作答正常使用主观题需2.0以上版本雨课堂主观题10分解答：解答：解：计算索引表项的大小，索引表项解：计算索引表项的大小，索引表项=512/2=256个个直接索引，每项对应一个物理

40、块，能管理的最大磁盘空间直接索引，每项对应一个物理块，能管理的最大磁盘空间=256*512B=217B=128KB二级索引，能管理的最大磁盘空间二级索引，能管理的最大磁盘空间=256*256*512B=216*512B=32MB三级索引，能管理的最大磁盘空间三级索引，能管理的最大磁盘空间=256*256*256*512B=224*512B=8GB4.4.存取设备、物理结构和存取方法之间的关系存取设备、物理结构和存取方法之间的关系存取设备存取设备 磁盘磁盘磁带磁带物理结构物理结构顺序结构顺序结构链接结构链接结构索引结构索引结构顺序结构顺序结构存取方法存取方法随机或顺序随机或顺序顺序顺序随机或顺序

41、随机或顺序顺序顺序文件长度文件长度固定固定可变，固定可变，固定可变，固定可变，固定固定固定文件的存储方法依赖于()。文件的物理结构A存放文件的存储设备的特性BA和B C文件的逻辑结构D提交单选题1分1 1、顺序存取设备顺序存取设备 只有在前面的物理块被访问过之后，才能存取后续只有在前面的物理块被访问过之后，才能存取后续的物理块的内容。如的物理块的内容。如 ：磁带：磁带6.3.2 6.3.2 文件的存储设备文件的存储设备2、直接（随机）存取设备：直接（随机）存取设备：存取磁盘上任一物理块存取磁盘上任一物理块的时间不依赖于该物理块所处的位置。如的时间不依赖于该物理块所处的位置。如：磁盘磁盘6.3.

42、2 6.3.2 文件的存储设备文件的存储设备2、直接（随机）存取设备直接（随机）存取设备磁盘分类：磁盘分类：固定头磁盘固定头磁盘：每个磁道设置一个磁头，变换磁道时不需：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高；要磁头的机械移动，速度快但成本高；移动头磁盘移动头磁盘：一个盘面只有一个磁头，变换磁道时需要一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低。移动磁头，速度慢但成本低。6.3.2 6.3.2 文件的存储设备文件的存储设备 1、磁带顺序存储设备图图6.12 磁带的结构磁带的结构影响磁带设备的存取速度或数据传输率因素：影响磁带设备的存取速度或数据传输率

43、因素：（1）信息密度）信息密度（2）磁带速度）磁带速度（3）块间间隙）块间间隙2 2、直接存储设备（随机存取）、直接存储设备（随机存取）图图6.136.13磁盘的结构磁盘的结构柱面柱面扇区扇区磁臂磁臂磁头磁头2 2、直接存储设备图示、直接存储设备图示磁盘存储相关专业名词：磁盘存储相关专业名词：（1 1）扇区：介质划分的最小单位；）扇区：介质划分的最小单位；（2 2）块）块(簇簇)：与内存交换数据的最小单位，由多个扇区组成，又：与内存交换数据的最小单位，由多个扇区组成，又 称为称为物理块物理块。（3 3）文件卷：一个独立的可装卸的文件存储介质。）文件卷：一个独立的可装卸的文件存储介质。（4 4）

44、柱面）柱面（5 5）磁道）磁道（6 6）物理地址形式：）物理地址形式：磁头号、磁道号、簇号（块号）磁头号、磁道号、簇号（块号）2 2、直接存储设备（随机存取）、直接存储设备（随机存取）磁盘上一物理块的位置可由参数()确定。字节号A柱面号B簇号C磁头号D缓存地址E提交多选题1分假设磁盘有256个柱面,4个磁头,每个磁道有8个簇(它们的编号均从0开始)。文件ABC在盘面上连续存放。如果ABC中的一个块放在5号柱面、1号磁头下的第7簇,那么ABC的下一块应该在()5号柱面、2号磁头下的第7簇A5号柱面、2号磁头下的第0簇B6号柱面、1号磁头下的第7簇C6号柱面、1号磁头下的第0簇D提交单选题1分2

45、2、直接存储设备、直接存储设备磁盘存取数据时间组成：磁盘存取数据时间组成：（1）寻道时间：寻道时间：磁头水平移动定位到指定磁道；磁头水平移动定位到指定磁道；（2）旋转延迟时间旋转延迟时间：等待指定扇区从磁头下旋转经过；：等待指定扇区从磁头下旋转经过；（3）数据传输时间数据传输时间：数据在磁盘与内存之间的实际传输。：数据在磁盘与内存之间的实际传输。2 2、直接存储设备（随机存取）、直接存储设备（随机存取）3.3.光盘光盘 （1 1）光盘容量大，速度快，价格便宜，但一般不可写；）光盘容量大，速度快，价格便宜，但一般不可写；（2 2）可读写光盘驱动器价格贵，写过程很麻烦；）可读写光盘驱动器价格贵，写

46、过程很麻烦；（3 3）光盘的空间结构与磁盘类似。）光盘的空间结构与磁盘类似。6.4 6.4 磁盘设备管理磁盘设备管理1.1.磁盘磁盘I/OI/O访问时间的组成访问时间的组成2.2.磁盘磁盘I/OI/O调度策略（重点）调度策略（重点）3.3.磁盘缓存置换算法磁盘缓存置换算法6.4 6.4 磁盘设备管理磁盘设备管理6.4 6.4 磁盘设备管理磁盘设备管理6.4.1 6.4.1 磁盘磁盘I/OI/O访问时间的组成访问时间的组成1、磁盘存取数据时间磁盘存取数据时间 磁道定位时间：磁道定位时间：磁头移动到指定磁道的机械运动时间磁头移动到指定磁道的机械运动时间 旋转延迟时间：旋转延迟时间：磁盘旋转到指定扇

47、区的机械运动时间；它磁盘旋转到指定扇区的机械运动时间；它与磁盘转速相关。与磁盘转速相关。数据传送时间：数据传送时间：从指定扇区读写数据的时间从指定扇区读写数据的时间2、影响磁盘存取时间因素影响磁盘存取时间因素 由于由于磁道定位时间磁道定位时间在访问时间中占主要部分，合理组织在访问时间中占主要部分，合理组织磁盘数据的存储位置可提高磁盘磁盘数据的存储位置可提高磁盘I/O性能。性能。6.4.1 6.4.1 磁盘磁盘I/OI/O访问时间的组成访问时间的组成例：读一个例：读一个128KB大小的文件大小的文件(1)文件由文件由8个连续磁道个连续磁道(每个磁道每个磁道32个扇区个扇区)上的上的256 个扇区

48、构个扇区构成：成：20ms*8+(7ms+16ms)*8=344ms;其中，磁道定位时间为其中，磁道定位时间为20ms，旋转延迟时间为，旋转延迟时间为7ms，每个每个扇区数据传输时间为扇区数据传输时间为0.5ms，32扇区数据传送时间为扇区数据传送时间为16ms；6.4.1 6.4.1 磁盘磁盘I/OI/O访问时间的组成访问时间的组成例：读一个例：读一个128KB大小的文件大小的文件(2)文件由文件由256个随机分布的扇区构成：个随机分布的扇区构成：(20ms+7ms+0.5ms)*256=7040ms;其中，其中，1扇区数据传送时间为扇区数据传送时间为0.5ms；随机分布时的访问时间为连续分

49、布时的随机分布时的访问时间为连续分布时的20倍。倍。6.4.1 6.4.1 磁盘磁盘I/OI/O访问时间的组成访问时间的组成6.4.2 6.4.2 磁盘磁盘I/OI/O调度策略调度策略（重点）（重点）1.问题的提出问题的提出 有若干个访问者请求磁盘执行输入输出操作，应先让哪一有若干个访问者请求磁盘执行输入输出操作，应先让哪一个访问者完成操作？个访问者完成操作？当多个访盘请求在等待时，采用一定的策略，对这些请求的当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、达到公平、高效高效2.2.磁盘调度策

50、略考虑的问题磁盘调度策略考虑的问题 根据移动臂的当前位置根据移动臂的当前位置使寻道时间尽可能小的那使寻道时间尽可能小的那个访问者优先得到服务个访问者优先得到服务。6.4.2 6.4.2 磁盘磁盘I/OI/O调度策略（重点）调度策略（重点）3.3.磁盘调度算法移臂调度磁盘调度算法移臂调度（1 1）先进先出算法）先进先出算法（2 2）优先级算法）优先级算法（3 3）后进先出算法）后进先出算法（4 4）短查找时间优先算法）短查找时间优先算法3.3.磁盘调度算法移臂调度磁盘调度算法移臂调度（5）扫描）扫描(SCAN)算法（重点）算法（重点）（6）循环扫描）循环扫描(C-SCAN)算法算法（7）N步扫描