1、第六章文 件 管 理 第六章文 件 管 理 6.1文件和文件系统文件和文件系统6.2文件的逻辑结构文件的逻辑结构6.3外存分配方式外存分配方式6.4目录管理目录管理6.5文件存储空间的管理文件存储空间的管理6.6文件共享与文件保护文件共享与文件保护6.7数据一致性控制数据一致性控制 第六章文 件 管 理 空闲表和空闲链表不适用于大型文件系统空闲表和空闲链表不适用于大型文件系统(表太长表太长)，UNIX系统将这两种方法相结合，系统将这两种方法相结合，将空闲将空闲盘盘块块分成组，分成组，每组第一块存一个空闲表成组链接起来，每组第一块存一个空闲表成组链接起来，兼二者之优点兼二者之优点克服了它们的缺点
2、。克服了它们的缺点。.6.5.3. 成组链接法成组链接法第六章文 件 管 理 1.1.空闲盘块的组织空闲盘块的组织: : (1)(1) 空闲空闲盘盘块块号号栈栈: : 此栈存储当前正在分配的一组此栈存储当前正在分配的一组空闲空闲盘盘块块号及本组尚有的空闲块总数号及本组尚有的空闲块总数N, NN, N兼作栈顶指针。兼作栈顶指针。如如: N=100, S.free(0)S.free(99): N=100, S.free(0)S.free(99)存储当前组存储当前组空闲空闲盘盘块块号号 (2)(2) 每组的第一块存储下一组空闲每组的第一块存储下一组空闲盘盘块块号号形成链。形成链。 (3)(3) 最末
3、组的最末组的空闲空闲盘盘块块号号栈栈存放在前一组的第一空闲存放在前一组的第一空闲块块中中, ,其中的其中的S.free(0)S.free(0)存放结束标志。存放结束标志。第六章文 件 管 理 图6-23空闲盘块的成组链接法 第六章文 件 管 理 2.空闲块的分配和回收空闲块的分配和回收: 利用空闲利用空闲盘盘块块号号栈栈。(1)分配分配: N=N-1; if(N0)分配分配S.free(N); else m=S.free(N);读入读入S.free(N);分配分配m;(2)回收回收: if(N=100) 写入回收块写入回收块; N=0 S.free(N)=回收块号回收块号; N=N+1;100
4、300299201N S.free(0)S.free(1) S.free(99)100400399301.990999901.第六章文 件 管 理 6.6 6.6 文件共享与文件保护文件共享与文件保护 文件共享指系统允许文件共享指系统允许多个用户多个用户(进程进程)使用同使用同一个文件一个文件( (或子或子目录目录) ) 。系统只需保留该共享文件的一份副本，。系统只需保留该共享文件的一份副本， 这样可以节省这样可以节省时间和存储空间时间和存储空间, , 减少了用户工作量。减少了用户工作量。当前常用两种文件共享方法：当前常用两种文件共享方法：6.6.1 6.6.1 基于索引结点的共享方式基于索引
5、结点的共享方式在树型结构的目录中，当有两个（或多个）用户要共享一个在树型结构的目录中，当有两个（或多个）用户要共享一个子目录或文件时，必须将共享文件或子目录连接到两个或多个子目录或文件时，必须将共享文件或子目录连接到两个或多个用户的目录中；用户的目录中；此时目录的结构已不再是树型结构而是一个有此时目录的结构已不再是树型结构而是一个有向非循环图。向非循环图。第六章文 件 管 理 如果文件的描述信息直接存储在用户的目录表中如果文件的描述信息直接存储在用户的目录表中，当某个用户，当某个用户对文件修改时这些描述信息的内容也可能发生变化，此时该文件对文件修改时这些描述信息的内容也可能发生变化，此时该文件
6、的其它共享者目录的对应信息并未随之改变，的其它共享者目录的对应信息并未随之改变，引起共享错误引起共享错误。第六章文 件 管 理 UFD(W) file1 UFD(Z) file2 count=2W/file1Z/file2索引结点索引结点 为了解决这一问题可以为了解决这一问题可以将目录表中文件的描述信息存储在将目录表中文件的描述信息存储在索引结点中索引结点中，而仅将文件名和指向索引结点的指针存放在目录，而仅将文件名和指向索引结点的指针存放在目录表中。索引结点中的表中。索引结点中的count用作共享计数用作共享计数(链接计数链接计数)。第六章文 件 管 理 D E FA B C I J K L
7、N G H B/I A/D/NB/KC/G 图中表示有向非循环图的目录结构，圆圈表示索引结点和图中表示有向非循环图的目录结构，圆圈表示索引结点和文件本身。文件本身。第六章文 件 管 理 UFD(C) owner=Ccount=1链接前链接前UFD(B)UFD(C)owner=Ccount=2链接后链接后UFD(B)owner=Ccount=1所有者删除后所有者删除后问题：删除文件时怎样考虑？当文件主删除文件时可能会发生问题：删除文件时怎样考虑？当文件主删除文件时可能会发生指针悬空。指针悬空。第六章文 件 管 理 6.6.2 利用符号链利用符号链(Symbolic Link)实现文件共享实现文件
8、共享 要使用户要使用户B能共享用户能共享用户C的文件的文件F，系统可建立一个，系统可建立一个类型为类型为LINK的新文件的新文件，如起名为，如起名为G(或仍为或仍为F)，放在，放在B的目录中，的目录中， 该该文件只包含被共享文件文件只包含被共享文件F的路径名的路径名。这种连接方法称为符号链这种连接方法称为符号链接接 (Symbolic Linking)，当，当B要访问要访问G文件时，被文件时，被OS截获截获, OS根根据据G的的LINK类型确定它是符号链，再按此符号链找到共享文类型确定它是符号链，再按此符号链找到共享文件件F。 当文件主当文件主C 删除文件删除文件F后，若后，若B试图通过文件试
9、图通过文件G 符号链访问符号链访问F, 则只会因找不到文件访问失败，不会发生指针悬空。则只会因找不到文件访问失败，不会发生指针悬空。 第六章文 件 管 理 图6-19多级目录结构 ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89第六章文 件 管 理 符号链的共享方式存在的符号链的共享方式存在的问题问题: 当其他用户去读共享文件时，系统是根据给定的文件路径名，当其他用户去读共享文件时，系统是根据给定的文件路径名，逐个分量逐个分量(名名)地去查找目录，直至找到该文件的索引结点。因此，地去查找目录，直至找到该文件的索引结点。因此，在在
10、每次访问共享文件时，都可能要多次地读盘每次访问共享文件时，都可能要多次地读盘。这使每次访问文。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。件的开销甚大，且增加了启动磁盘的频率。要为每个共享用户建立一条要为每个共享用户建立一条符号链符号链，该链实际上是一个文件，该链实际上是一个文件，要为它配置一个要为它配置一个索引结点索引结点，这也，这也要耗费一定的磁盘空间要耗费一定的磁盘空间。优点：优点：能够用于链接能够用于链接(通过计算机网络通过计算机网络)世界上任何地方的计算机世界上任何地方的计算机中的文件，此时只需提供该文件所在机器的网络地址以及该机器中的文件，此时只需提供该文件所在机器的网络地
11、址以及该机器中的文件路径即可。中的文件路径即可。 两种方法的共同两种方法的共同问题问题：遍历文件系统：遍历文件系统=共享文件的多次遍历；共享文件的多次遍历； 转存文件系统转存文件系统=共享文件的多个拷贝共享文件的多个拷贝第六章文 件 管 理 6.6.3 6.6.3 磁盘容错技术磁盘容错技术 磁盘容错技术磁盘容错技术：通过设置冗余的磁盘驱动器、磁盘控制器等部：通过设置冗余的磁盘驱动器、磁盘控制器等部件件, 来提高可靠性的技术。来提高可靠性的技术。 系统（磁盘）容错技术系统（磁盘）容错技术SFT：三级三级 SFT-1低级低级： SFT-2中级中级： SFT-3高级高级：1影响文件安全的因素影响文件
12、安全的因素：人为因素；系统因素；自然因素：人为因素；系统因素；自然因素2安全措施安全措施： 存取控制机制；磁盘容错技术；后备系统存取控制机制；磁盘容错技术；后备系统3容错技术容错技术：设置冗余部件，来提高系统的可靠性；：设置冗余部件，来提高系统的可靠性；第六章文 件 管 理 1. 第一级第一级 磁盘容错技术磁盘容错技术SFT-1 用于防止因磁盘表面缺陷造成的数据破坏或丢失，包括用于防止因磁盘表面缺陷造成的数据破坏或丢失，包括双份目录、双份文件分配表和写后读校验等措施。双份目录、双份文件分配表和写后读校验等措施。(1) 双份目录和双份文件分配表双份目录和双份文件分配表(2) 热修复重定向和写后读
13、校验热修复重定向和写后读校验 热修复重定向：热修复重定向：将磁盘的将磁盘的23%作为热修复重定向区作为热修复重定向区 写后读校验：写后读校验：写盘后立即读并与原数据校验写盘后立即读并与原数据校验第六章文 件 管 理 2. 第二级第二级 磁盘容错技术磁盘容错技术SFT-2防止磁盘驱动器和控制器故障导致的系统不正常；防止磁盘驱动器和控制器故障导致的系统不正常；(1) 磁盘镜像磁盘镜像 两个磁盘驱动器互为备份两个磁盘驱动器互为备份(2)磁盘双工磁盘双工 通道、磁盘控制器和磁盘驱动都为双份通道、磁盘控制器和磁盘驱动都为双份主主机机磁盘磁盘控制器控制器通道通道主主机机磁盘控制器磁盘控制器磁盘控制器磁盘控
14、制器通道通道通道通道第六章文 件 管 理 3.3.基于集群技术的容错功能基于集群技术的容错功能所谓集群，是指由一组互连的自主计算机组成统一的计所谓集群，是指由一组互连的自主计算机组成统一的计算机系统，给人们的感觉是，它们是一台机器。算机系统，给人们的感觉是，它们是一台机器。利用集利用集群系统不仅可提高系统的并行处理能力，还可用于提高群系统不仅可提高系统的并行处理能力，还可用于提高系统的可用性。系统的可用性。它包括三种工作模式：它包括三种工作模式：（1 1）双机热备份模式）双机热备份模式（2 2）双机互为备份模式）双机互为备份模式（3 3）公共磁盘模式）公共磁盘模式第六章文 件 管 理 数据数据
15、0数据数据1 1的备份的备份CPU磁盘磁盘0数据数据1数据数据0 0的备份的备份磁盘磁盘1块交错备份块交错备份第六章文 件 管 理 重点难点学习提示重点难点学习提示1、顺序文件、索引文件和索引顺序文件，、顺序文件、索引文件和索引顺序文件，各自优缺点和适用于的场合各自优缺点和适用于的场合2、连续分配、链接分配和索引分配、连续分配、链接分配和索引分配3、位示图法和成组链接法、位示图法和成组链接法4、目录管理、目录管理5、文件共享方式、文件共享方式第六章文 件 管 理 对于本章的知识点，文件存储空间的管理可以命制对于本章的知识点，文件存储空间的管理可以命制综合应用题，混合索引下计算文件实际占用磁盘空
16、间和最大综合应用题，混合索引下计算文件实际占用磁盘空间和最大文件、计算访问磁盘次数可以命制综合应用题，其它知识点文件、计算访问磁盘次数可以命制综合应用题，其它知识点可以命制单项选择题。可以命制单项选择题。20092009年联考所占分值为年联考所占分值为6 6分，分，20102010年联考所占分值为年联考所占分值为6 6分。分。第六章文 件 管 理 1. 1. 文件的顺序存取是（文件的顺序存取是（ ）。）。 【电子科大电子科大20032003】A.A.按终端号一次存取按终端号一次存取 B.B.按文件的逻辑号逐一存取按文件的逻辑号逐一存取C.C.按物理块号一次存取按物理块号一次存取 D.D.按文件
17、逻辑记录的大小逐一存取按文件逻辑记录的大小逐一存取2. 2. 如果文件系统中有两个文件重名，不应采用（如果文件系统中有两个文件重名，不应采用（ ）。）。 【南京理工南京理工20072007】A.A.单级目录结构单级目录结构 B.B.两级目录结构两级目录结构 C.C.树形目录结构树形目录结构 D.D.多级目录结构多级目录结构3. 3. 设文件设文件F1F1的当前引用计数值为的当前引用计数值为1 1，先建立，先建立F1F1的符号链接的符号链接（软链接）文件（软链接）文件F2F2，再建立，再建立F1F1的硬链接文件的硬链接文件F3F3，然后删除，然后删除F1F1。此时，此时，F2F2和和F3F3的引
18、用计数值分别是（的引用计数值分别是（ ）。）。A.0A.0、1 B.11 B.1、1 C.11 C.1、2 D.22 D.2、1 1BAB第六章文 件 管 理 4. 4. 下列关于打开文件下列关于打开文件openopen和关闭文件和关闭文件closeclose的叙述，只有（的叙述，只有（ ）是错误的。是错误的。【浙江大学浙江大学20062006】A.close()A.close()操作告诉系统，不再需要指定的文件了，可以丢弃它操作告诉系统，不再需要指定的文件了，可以丢弃它B.open()B.open()操作告诉系统，开始使用指定的文件操作告诉系统，开始使用指定的文件C.C.文件必须先打开，后使
19、用文件必须先打开，后使用D.D.目录必须先打开，后使用目录必须先打开，后使用第六章文 件 管 理 5. 考虑一个文件存放在考虑一个文件存放在100个数据块中。文件控制块、索个数据块中。文件控制块、索引块或索引信息都驻留内存。那么如果（引块或索引信息都驻留内存。那么如果（ ），不需要做任），不需要做任何磁盘何磁盘I/O操作。操作。 【浙江大学浙江大学2006】A.采用采用continuous allocation策略，将最后一个数据块搬到策略，将最后一个数据块搬到文件头部文件头部B.采用采用linked allocation策略，将最后一个数据块插入文件策略，将最后一个数据块插入文件头部头部C.
20、采用采用linked allocation策略，将第一个数据块插入文件尾策略，将第一个数据块插入文件尾部部D.采用采用single level indexed allocation策略，将最后一个数策略，将最后一个数据块插入文件头部据块插入文件头部D第六章文 件 管 理 6. 6. 逻辑文件的组织形式是由（逻辑文件的组织形式是由（ ）决定的。）决定的。A.A.存储介质特性存储介质特性 B.B.操作系统的管理方式操作系统的管理方式 C.C.用户用户 D.D.主存容量主存容量【分析分析】文件的逻辑结构是用户所观察到的文件组织形式，数文件的逻辑结构是用户所观察到的文件组织形式，数据组织形式取决于用户
21、需求，例如，登记操作日志记录导致顺据组织形式取决于用户需求，例如，登记操作日志记录导致顺序文件的产生；对数据库中结构化数据的存取导致随机访问文序文件的产生；对数据库中结构化数据的存取导致随机访问文件的产生。所以，逻辑文件的组织形式取决于用户，因此应该件的产生。所以，逻辑文件的组织形式取决于用户，因此应该选择选择C C。7. 7. 物理文件的组织方式是由（物理文件的组织方式是由（ ）确定的。）确定的。A.A.操作系统操作系统 B.B.主存容量主存容量 C.C.外存容量外存容量 D.D.应用程序应用程序【分析分析】文件的物理结构是指文件在外存上的存储组织形式，文件的物理结构是指文件在外存上的存储组
22、织形式，既与存储介质的存储性能有关，又与操作系统所采用的外存分既与存储介质的存储性能有关，又与操作系统所采用的外存分配方法有关。因此应该选择配方法有关。因此应该选择A A。第六章文 件 管 理 7. 7. 假定磁盘块的大小为假定磁盘块的大小为1K1K，对于，对于540M540M的硬盘，其文件分配的硬盘，其文件分配表表FATFAT需要占用多少存储空间？当硬盘容量为需要占用多少存储空间？当硬盘容量为1.2G1.2G时，时，FATFAT需要需要占用多少空间？占用多少空间？解：由题目所给条件可知，硬盘大小为解：由题目所给条件可知，硬盘大小为540M540M，磁盘块的大小，磁盘块的大小为为1K1K，所以
23、该硬盘共有盘块：，所以该硬盘共有盘块：540M / 1K = 540K540M / 1K = 540K（个）（个）又又 512K 540K 1024K512K 540K 1024K故故540K540K个盘块号要用个盘块号要用2020位二进制表示，即文件分配表的每个位二进制表示，即文件分配表的每个表目为表目为2.52.5个字节。个字节。FATFAT要占用的存储空间总数为：要占用的存储空间总数为：2.5 2.5 * * 540K 540K = 1350K= 1350K当硬盘大小为当硬盘大小为1.2G1.2G，硬盘共有盘块：，硬盘共有盘块：1.2G / 1K = 1.2M1.2G / 1K = 1.
24、2M（个）（个）又又1M 1.2M 2M1M 1.2M 2M故故1.2M1.2M个盘块号要用个盘块号要用2121位二进制表示。为方便文件分配表的位二进制表示。为方便文件分配表的存取，每个表目用存取，每个表目用2424位二进制表示，即位二进制表示，即FATFAT的每个表目大小为的每个表目大小为3 3个字节。个字节。FATFAT要占用的存储空间总数为：要占用的存储空间总数为：3 3 * * 1.2M = 3.6M 1.2M = 3.6M第六章文 件 管 理 8. 8. 假设计算机系统采用假设计算机系统采用CSCANCSCAN（循环扫描）磁盘调度策略，使（循环扫描）磁盘调度策略，使用用2KB2KB的
25、内存空间记录的内存空间记录16 38416 384个磁盘块的空闲状态。个磁盘块的空闲状态。 全国联考全国联考20102010（1 1）请说明在上述条件下如何进行磁盘块空闲状态的管理。）请说明在上述条件下如何进行磁盘块空闲状态的管理。（2 2）设某单面磁盘旋转速度为每分钟）设某单面磁盘旋转速度为每分钟60006000转，每个磁道有转，每个磁道有100100个扇区，相邻磁道间的平均移动时间为个扇区，相邻磁道间的平均移动时间为1ms1ms。若在某时刻，磁头。若在某时刻，磁头位于位于100100号磁道处，并沿着磁道号增大的方向移动（如下图所号磁道处，并沿着磁道号增大的方向移动（如下图所示），磁道号请求
26、队列为示），磁道号请求队列为5050、9090、3030、120120，对请求队列中的每，对请求队列中的每个磁道需读取个磁道需读取1 1个随机分布的扇区，则读完这个随机分布的扇区，则读完这4 4个扇区总共需要多个扇区总共需要多少时间？要求给出计算过程。随机分布的某扇区少时间？要求给出计算过程。随机分布的某扇区0 0号磁道磁头当号磁道磁头当前运动方向前运动方向100100号磁道号磁道（3 3）如果将磁盘替换为随机访问）如果将磁盘替换为随机访问FlashFlash半导体存储器（如半导体存储器（如U U盘、盘、SSDSSD等），是否有比等），是否有比CSCANCSCAN更高效的磁盘调度策略？若有，给
27、出磁更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。盘调度策略的名称并说明理由；若无，说明理由。第六章文 件 管 理 随机分布的某扇区0号磁道磁头当前运动方向100号磁道第六章文 件 管 理 解：（解：（1 1）2KB = 22KB = 2* *10241024* *8bit = 16384bit8bit = 16384bit。因此可以使用位图。因此可以使用位图法进行磁盘块空闲状态管理，每法进行磁盘块空闲状态管理，每1bit1bit表示一个磁盘块是否空表示一个磁盘块是否空闲。闲。（2 2）根据）根据CSCANCSCAN算法，被访问的磁道号顺序为算法，被访问的磁道号
28、顺序为100100、120120、3030、5050、9090，因此，寻道用去的总时间为：（，因此，寻道用去的总时间为：（20 + 90 + 20 + 4020 + 90 + 20 + 40）* * 1ms = 170ms1ms = 170ms；每分钟；每分钟60006000转，转一圈的时间为转，转一圈的时间为0.01s0.01s，一，一个扇区的读取时间为个扇区的读取时间为0.01/100=0.0001s0.01/100=0.0001s，一个扇区的平均旋，一个扇区的平均旋转延迟时间为（转延迟时间为（0+0.010+0.01）/2/2，总共要随机读取四个扇区，总，总共要随机读取四个扇区，总共用去
29、的旋转延迟时间和传输时间为：（共用去的旋转延迟时间和传输时间为：（0.010.01* *0.5 + 0.00010.5 + 0.0001）* *4 = 0.0204s = 20.4ms4 = 0.0204s = 20.4ms所以；读完这所以；读完这4 4个扇区总共需要个扇区总共需要 170ms + 20.4ms = 190.4ms170ms + 20.4ms = 190.4ms。第六章文 件 管 理 （3 3）若将磁盘换为）若将磁盘换为U U盘等，有比盘等，有比CSCANCSCAN更高效的磁更高效的磁盘调度策略。盘调度策略。U U盘的存储介质为电可擦除只读存盘的存储介质为电可擦除只读存储器储器
30、(EEPROM)(EEPROM)的变种，的变种，其寻址方式类似于内存的其寻址方式类似于内存的寻址方式，不涉及到磁盘的寻道、寻扇区等操作，寻址方式，不涉及到磁盘的寻道、寻扇区等操作，因此可采用先来先服务、优先级高者优先等算法。因此可采用先来先服务、优先级高者优先等算法。第六章文 件 管 理 9. 9. 在实现文件系统时，为加快文件目录的检索速度，可利用在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制块分解法文件控制块分解法”。假设目录文件存放在磁盘上，每个盘。假设目录文件存放在磁盘上，每个盘块块512512字节。文件控制块占字节。文件控制块占6464字节。其中文件名占字节。其中文件名
31、占8 8字节。通常字节。通常将文件控制块分解成两部分，第一部分占将文件控制块分解成两部分，第一部分占1010字节（包括文件名字节（包括文件名和文件内部号），第二部分占和文件内部号），第二部分占5656字节（包括文件内部号和文件字节（包括文件内部号和文件其它描述信息）。其它描述信息）。 【北京大学北京大学19971997】（1 1）假设某一目录文件共有）假设某一目录文件共有254254个文件控制块，试分别给出个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某一个文件控制采用分解法前和分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数。块的平均访问磁盘次数。（2 2）一般
32、地，若目录文件分解前占用）一般地，若目录文件分解前占用n n个盘块，分解后改用个盘块，分解后改用m m个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。少的条件。第六章文 件 管 理 【分析分析】目录文件也被看做一个文件，本身也需要一定目录文件也被看做一个文件，本身也需要一定数量的物理数据块。数量的物理数据块。设目录文件需要的物理数据块为设目录文件需要的物理数据块为n，在在单级目录中，对于线性检索法，检索某一个文件在目录文单级目录中，对于线性检索法，检索某一个文件在目录文件中的那部分控制块，最好的情况只需要件中的那部分控制块，
33、最好的情况只需要1次次I/O（即在第一（即在第一个物理数据块中），最坏的情况需要个物理数据块中），最坏的情况需要n次次I/O（即在最后一（即在最后一个物理数据块中）。个物理数据块中）。如果不采用分解法，则平均访问磁盘如果不采用分解法，则平均访问磁盘次数为（次数为（1+n）/2；如果采用分解法，还需读取一次磁盘以如果采用分解法，还需读取一次磁盘以找到文件控制块的所有内容，找到文件控制块的所有内容，设分解后目录文件占用设分解后目录文件占用m个盘个盘块，则平均访问磁盘次数为（块，则平均访问磁盘次数为（1+m）/2+1。所以，关键是计所以，关键是计算不采用分解法和采用分解法两种情况下目录文件本身所算不
34、采用分解法和采用分解法两种情况下目录文件本身所需的物理数据块。需的物理数据块。第六章文 件 管 理 解：解：（1）采用分解法前，目录所需的磁盘块数为（）采用分解法前，目录所需的磁盘块数为（64*254）/512=31.75，也就是，也就是32块。所以查找该目录文件中的某一个块。所以查找该目录文件中的某一个文件控制块的平均访问磁盘次数为（文件控制块的平均访问磁盘次数为（1+32）/2=16.5。采用分解法后，目录所需的磁盘块数为（采用分解法后，目录所需的磁盘块数为（10*254）/512=4.96，也就是也就是5块，块，检索目录文件后，还需读取一次磁盘以找到文检索目录文件后，还需读取一次磁盘以找
35、到文件控制块的所有内容。件控制块的所有内容。所以查找该目录文件中的某一个文件所以查找该目录文件中的某一个文件控制块的平均访问磁盘次数为（控制块的平均访问磁盘次数为（1+5）/2+1=4。（2）访问磁盘次数减少的条件是：）访问磁盘次数减少的条件是：(1+m)/2+1（1+n）/2，即，即mn-2。第六章文 件 管 理 10.10.某个系统采用成组链接法来管理磁盘空间，目前磁盘某个系统采用成组链接法来管理磁盘空间，目前磁盘的状态如图所示。的状态如图所示。（1 1）该磁盘中目前还有多少个空闲盘快？）该磁盘中目前还有多少个空闲盘快？（2 2）请简述磁盘块的分配过程。）请简述磁盘块的分配过程。（3 3）
36、在为某个文件分配）在为某个文件分配3 3个盘块后，系统要删除另一文件，个盘块后，系统要删除另一文件，并回收它所占的并回收它所占的5 5个盘块，它们的盘块号依次为个盘块，它们的盘块号依次为700700、711711、703703、788788、701701，请画出回收后的盘块链接情况。，请画出回收后的盘块链接情况。100300299N S.free(0)S.free(1) S.free(99)100400399301990599501.第六章文 件 管 理 11、有一文件系统如下图所示。图中的框表示目录，圈表、有一文件系统如下图所示。图中的框表示目录，圈表示普通文件。示普通文件。根目录常驻内存，
37、根目录常驻内存，目录文件组织成链接文件，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。不设文件控制块，普通文件组织成索引文件。目录表目指示目录表目指示下一级文件名及其磁盘地址下一级文件名及其磁盘地址(各占各占2个字节，共个字节，共4个字节个字节)。若。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后件磁盘块最后4个字节供链接使用。下级文件在上级目录文个字节供链接使用。下级文件在上级目录文件中的次序在图中为
38、自左至右。每个磁盘块有件中的次序在图中为自左至右。每个磁盘块有512字节，与字节，与普通文件的一页等长。普通文件的一页等长。第六章文 件 管 理 根目录ABCDHIPULEFGJKMNQRSTVW文件系统结构示意图文件系统结构示意图第六章文 件 管 理 普通文件的文件控制块组织如图所示普通文件的文件控制块组织如图所示 。其中，。其中，每个磁盘地每个磁盘地址占址占2个字节，前个字节，前10个地址直接指示该文件前个地址直接指示该文件前10页的地址。第页的地址。第11个地址指示一级索引表地址，一级索引表中每个磁盘地址指个地址指示一级索引表地址，一级索引表中每个磁盘地址指示一个文件页地址；第示一个文件
39、页地址；第12个地址指示二级索引表地址，二级索个地址指示二级索引表地址，二级索引表中每个地址指示一个一级索引表地址；第引表中每个地址指示一个一级索引表地址；第13个地址指示三个地址指示三级索引表地址，三级索引表中每个地址指示一个二级索引表地级索引表地址，三级索引表中每个地址指示一个二级索引表地址。址。问：问：(1)一个普通文件最多可有多少个文件页？一个普通文件最多可有多少个文件页？(2)若要读文件若要读文件J中某一页，最中某一页，最多多启动磁盘多少次？启动磁盘多少次？(3)若要读文件若要读文件W中的某一页，最中的某一页，最少少启动磁盘多少次？启动磁盘多少次？(4)就上一问而言，为最大限度减少启
40、动磁盘的次数，可采用就上一问而言，为最大限度减少启动磁盘的次数，可采用什么方法？此时，磁盘最多启动多少次？什么方法？此时，磁盘最多启动多少次？第六章文 件 管 理 该文件的有关描述信息磁盘地址磁盘地址磁盘地址磁盘地址磁盘地址12111213普通文件的文件控制块组织普通文件的文件控制块组织第六章文 件 管 理 第六章文 件 管 理 解：解：(1)(1)由题目中所给条件可知，磁盘块大小为由题目中所给条件可知，磁盘块大小为512512字节，字节，每个磁盘地址中每个磁盘地址中2 2个字节。因此，一个一级索引表可容纳个字节。因此，一个一级索引表可容纳256256个磁盘地址。同样地，一个二级索引表可容纳个
41、磁盘地址。同样地，一个二级索引表可容纳256256个一级索引个一级索引表地址，一个三级索引表可容纳表地址，一个三级索引表可容纳256256个二级索引表地址。这样，个二级索引表地址。这样，一个普通文件最多可有页数为：一个普通文件最多可有页数为：10+256+25610+256+256256+256256+256256256256=16 843 018256=16 843 018第六章文 件 管 理 (2)(2)从图中可以看出，目录文件从图中可以看出，目录文件A A和目录文件和目录文件D D中，目录项都中，目录项都只有两个，因此这两个目录文件都不需拉链。若要读文件只有两个，因此这两个目录文件都不需
42、拉链。若要读文件J J中的中的每一页，首先从内存的根目录中找到目录文件每一页，首先从内存的根目录中找到目录文件A A的磁盘地址，将的磁盘地址，将其读入内存其读入内存( (第第1 1次磁盘访问次磁盘访问) )。然后再从目录。然后再从目录A A中找出目录文件中找出目录文件D D的磁盘地址，并将其读入内存的磁盘地址，并将其读入内存( (第第2 2次磁盘访问次磁盘访问) )。从目录。从目录D D中找中找出文件出文件J J的的文件控制块地址文件控制块地址，将文件，将文件J J的文件控制块读入内存的文件控制块读入内存( (第第3 3次磁盘访问次磁盘访问) )。在最坏情况下在最坏情况下，要访问页的磁盘地址需
43、通过三，要访问页的磁盘地址需通过三级索引才能级索引才能找到，这时找到，这时要三次访问磁盘才能将三级索引表读入要三次访问磁盘才能将三级索引表读入内存内存(第第4、5、6次磁盘访问次磁盘访问)。最后读入文件。最后读入文件J中的相应页中的相应页(第第7次次访问磁盘访问磁盘)。由此可知，若要读文件由此可知，若要读文件J的某一页，的某一页，最多启动磁盘最多启动磁盘7次。次。第六章文 件 管 理 (3)从图中可以看出，目录文件从图中可以看出，目录文件C和目录文件和目录文件U中，目录项数目较中，目录项数目较多，若目录项数超过多，若目录项数超过127(512/4-1=127)，则目录文件的读入可能需，则目录文
44、件的读入可能需要多次磁盘读要多次磁盘读(因目录文件组织成链接文件因目录文件组织成链接文件)。在最好情况下，所找在最好情况下，所找的目录项都在目录文件的第一个磁盘块中的目录项都在目录文件的第一个磁盘块中。若要读文件。若要读文件W中的某一中的某一页，首先从内存的根目录中找到目录文件页，首先从内存的根目录中找到目录文件C的磁盘地址，将其读入的磁盘地址，将其读入内存内存(第第1次磁盘访问次磁盘访问)。在最好情况下，能从目录。在最好情况下，能从目录C的第一个磁盘块的第一个磁盘块中找出目录文件中找出目录文件I的磁盘地址，并将其读入内存的磁盘地址，并将其读入内存(第第2次磁盘访问次磁盘访问)。从目录从目录I
45、中找出目录文件中找出目录文件P的磁盘地址，将其读入内存的磁盘地址，将其读入内存(第第3次磁盘访次磁盘访问问)。从目录。从目录P中找到目录文件中找到目录文件U的磁盘地址，将其读入内存的磁盘地址，将其读入内存(第第4次次磁盘访问磁盘访问)。在最好情况下，能从目录。在最好情况下，能从目录U的第一个磁盘块中找出文件的第一个磁盘块中找出文件W的文件控制块地址，将文件的文件控制块地址，将文件W的文件控制块读入内存的文件控制块读入内存(第第5次磁盘次磁盘访问访问)。在最好情况下，要访问的页在前在最好情况下，要访问的页在前10页中页中，这时可直接得到，这时可直接得到该页的磁盘地址。最后读入文件该页的磁盘地址。
46、最后读入文件W中的相应页中的相应页(第第6次访问磁盘次访问磁盘)。由此可知，由此可知，若要读文件若要读文件W中的某一页，最少启动磁盘中的某一页，最少启动磁盘6次。次。第六章文 件 管 理 (4)由于通过文件控制块访问文件所需的访问磁盘次数无法由于通过文件控制块访问文件所需的访问磁盘次数无法改变，改变，要减少访问磁盘的次数，只有通过减少访问目录文件的要减少访问磁盘的次数，只有通过减少访问目录文件的次数来达到。次数来达到。为最大限度地减少启动磁盘的次数，可以将文件为最大限度地减少启动磁盘的次数，可以将文件W直接链接在根目录的最左端直接链接在根目录的最左端(或其目录项在根目录的前或其目录项在根目录的
47、前127个个项内项内)。这样，若要读文件。这样，若要读文件W中的某页时，首先从内存的根目录中的某页时，首先从内存的根目录中找到文件中找到文件W的文件控制块地址，将文件的文件控制块地址，将文件W的文件控制块读入的文件控制块读入内存内存(第第1次磁盘访问次磁盘访问)。在最坏情况下，要访问页的磁盘地址需。在最坏情况下，要访问页的磁盘地址需通过三级索引才能找到，这时要三次访问磁盘才能将三级索引通过三级索引才能找到，这时要三次访问磁盘才能将三级索引表读入内存表读入内存(第第2、3、4次磁盘访问次磁盘访问)。最后读入文件。最后读入文件W中的相应中的相应页页(第第5次访问磁盘次访问磁盘)。由此可知，。由此可知，若将文件若将文件W直接链接在根目录直接链接在根目录的最左端，要读文件的最左端，要读文件J中的某一页，最多启动磁盘中的某一页，最多启动磁盘5次。次。
