nullnull第六章 文 件 管 理 6.1 文件和文件系统
6.2 文件的逻辑结构
6.3 外存分配方式
6.4 目录管理
6.5 文件存储空间的管理
6.6 文件共享与文件保护
6.7 数据一致性控制 6.5.3. 成组链接法6.5.3. 成组链接法 空闲表和空闲链表不适用于大型文件系统(表太长),UNIX系统将这两种方法相结合,将空闲盘块分成组,每组第一块存一个空闲表成组链接起来,兼二者之优点克服了它们的缺点。null1.空闲盘块的组织:
(1) 空闲盘块号栈: 此栈存储当前正在分配的一组空闲盘块号及本组尚有的空闲块总数N, N兼作栈顶指针。
如: N=100, S.free(0)—S.free(99)存储当前组空闲盘块号
(2) 每组的第一块存储下一组空闲盘块号形成链。
(3) 最末组的空闲盘块号栈存放在前一组的第一空闲块中,其中的S.free(0)存放结束标志。null图6-23 空闲盘块的成组链接法 null2.空闲块的分配和回收:
利用空闲盘块号栈。
(1)分配: N=N-1;
if(N>0)分配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
300
299
…
201N
S.free(0)
S.free(1)
…
S.free(99)100
400
399
…
301............6.6 文件共享与文件保护6.6 文件共享与文件保护 文件共享指系统允许多个用户(进程)使用同一个文件(或子目录) 。系统只需保留该共享文件的一份副本, 这样可以节省时间和存储空间, 减少了用户工作量。
当前常用两种文件共享方法:
6.6.1 基于索引结点的共享方式
在树型结构的目录中,当有两个(或多个)用户要共享一个子目录或文件时,必须将共享文件或子目录连接到两个或多个用户的目录中;此时目录的结构已不再是树型结构而是一个有向非循环图。null如果文件的描述信息直接存储在用户的目录表中,当某个用户对文件修改时这些描述信息的内容也可能发生变化,此时该文件的其它共享者目录的对应信息并未随之改变,引起共享错误。null 为了解决这一问
可以将目录表中文件的描述信息存储在索引结点中,而仅将文件名和指向索引结点的指针存放在目录表中。索引结点中的count用作共享计数(链接计数)。null 图中表示有向非循环图的目录结构,圆圈表示索引结点和文件本身。null问题:删除文件时怎样考虑?当文件主删除文件时可能会发生指针悬空。null6.6.2 利用符号链(Symbolic Link)实现文件共享
要使用户B能共享用户C的文件F,系统可建立一个类型为LINK的新文件,如起名为G(或仍为F),放在B的目录中, 该文件只包含被共享文件F的路径名。这种连接方法称为符号链接 (Symbolic Linking),当B要访问G文件时,被OS截获, OS根据G的LINK类型确定它是符号链,再按此符号链找到共享文件F。
当文件主C 删除文件F后,若B试图通过文件G 符号链访问F, 则只会因找不到文件访问失败,不会发生指针悬空。
null图6-19 多级目录结构 null符号链的共享方式存在的问题:
当其他用户去读共享文件时,系统是根据给定的文件路径名,逐个分量(名)地去查找目录,直至找到该文件的索引结点。因此,在每次访问共享文件时,都可能要多次地读盘。这使每次访问文件的开销甚大,且增加了启动磁盘的频率。
要为每个共享用户建立一条符号链,该链实际上是一个文件,要为它配置一个索引结点,这也要耗费一定的磁盘空间。
优点:能够用于链接(通过计算机网络)世界上任何地方的计算机中的文件,此时只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。
两种方法的共同问题:遍历文件系统=〉共享文件的多次遍历;
转存文件系统=〉共享文件的多个拷贝null6.6.3 磁盘容错技术 磁盘容错技术:通过设置冗余的磁盘驱动器、磁盘控制器等部件, 来提高可靠性的技术。
系统(磁盘)容错技术SFT:三级
SFT-1低级:
SFT-2中级:
SFT-3高级:1.影响文件安全的因素:人为因素;系统因素;自然因素2.安全措施: 存取控制机制;磁盘容错技术;后备系统3.容错技术:设置冗余部件,来提高系统的可靠性;null1. 第一级 磁盘容错技术SFT-1
用于防止因磁盘表面缺陷造成的数据破坏或丢失,包括双份目录、双份文件分配表和写后读校验等措施。
(1) 双份目录和双份文件分配表
(2) 热修复重定向和写后读校验
热修复重定向:将磁盘的2~3%作为热修复重定向区
写后读校验:写盘后立即读并与原数据校验null2. 第二级 磁盘容错技术SFT-2
防止磁盘驱动器和控制器故障导致的系统不正常;
(1) 磁盘镜像
两个磁盘驱动器互为备份
(2)磁盘双工
通道、磁盘控制器和磁盘驱动都为双份null3.基于集群技术的容错功能
所谓集群,是指由一组互连的自主计算机组成统一的计算机系统,给人们的感觉是,它们是一台机器。利用集群系统不仅可提高系统的并行处理能力,还可用于提高系统的可用性。它包括三种工作模式:
(1)双机热备份模式
(2)双机互为备份模式
(3)公共磁盘模式
null块交错备份重点难点学习提示重点难点学习提示1、顺序文件、索引文件和索引顺序文件,各自优缺点和适用于的场合
2、连续分配、链接分配和索引分配
3、位示图法和成组链接法
4、目录管理
5、文件共享方式null 对于本章的
,文件存储空间的管理可以命制综合应用题,混合索引下计算文件实际占用磁盘空间和最大文件、计算访问磁盘次数可以命制综合应用题,其它知识点可以命制单项选择题。
2009年联考所占分值为6分,2010年联考所占分值为6分。null1. 文件的顺序存取是( )。 【电子科大2003】
A.按终端号一次存取 B.按文件的逻辑号逐一存取
C.按物理块号一次存取 D.按文件逻辑
的大小逐一存取
2. 如果文件系统中有两个文件重名,不应采用( )。 【南京理工2007】
A.单级目录结构 B.两级目录结构
C.树形目录结构 D.多级目录结构
3. 设文件F1的当前引用计数值为1,先建立F1的符号链接(软链接)文件F2,再建立F1的硬链接文件F3,然后删除F1。此时,F2和F3的引用计数值分别是( )。
A.0、1 B.1、1 C.1、2 D.2、1BABnull4. 下列关于打开文件open和关闭文件close的叙述,只有( )是错误的。【浙江大学2006】
A.close()操作告诉系统,不再需要指定的文件了,可以丢弃它
B.open()操作告诉系统,开始使用指定的文件
C.文件必须先打开,后使用
D.目录必须先打开,后使用null5. 考虑一个文件存放在100个数据块中。文件控制块、索引块或索引信息都驻留内存。那么如果( ),不需要做任何磁盘I/O操作。 【浙江大学2006】
A.采用continuous allocation策略,将最后一个数据块搬到文件头部
B.采用linked allocation策略,将最后一个数据块插入文件头部
C.采用linked allocation策略,将第一个数据块插入文件尾部
D.采用single level indexed allocation策略,将最后一个数据块插入文件头部Dnull6. 逻辑文件的组织形式是由( )决定的。
A.存储介质特性 B.操作系统的管理方式 C.用户 D.主存容量
【分析】文件的逻辑结构是用户所观察到的文件组织形式,数据组织形式取决于用户需求,例如,登记操作日志记录导致顺序文件的产生;对数据库中结构化数据的存取导致随机访问文件的产生。所以,逻辑文件的组织形式取决于用户,因此应该选择C。
7. 物理文件的组织方式是由( )确定的。
A.操作系统 B.主存容量 C.外存容量 D.应用程序
【分析】文件的物理结构是指文件在外存上的存储组织形式,既与存储介质的存储性能有关,又与操作系统所采用的外存分配方法有关。因此应该选择A。null7. 假定磁盘块的大小为1K,对于540M的硬盘,其文件分配表FAT需要占用多少存储空间?当硬盘容量为1.2G时,FAT需要占用多少空间?
解:由题目所给条件可知,硬盘大小为540M,磁盘块的大小为1K,所以该硬盘共有盘块:
540M / 1K = 540K(个)
又 512K < 540K < 1024K
故540K个盘块号要用20位二进制表示,即文件分配表的每个表目为2.5个字节。FAT要占用的存储空间总数为:2.5 * 540K = 1350K
当硬盘大小为1.2G,硬盘共有盘块:1.2G / 1K = 1.2M(个)
又1M < 1.2M < 2M
故1.2M个盘块号要用21位二进制表示。为方便文件分配表的存取,每个表目用24位二进制表示,即FAT的每个表目大小为3个字节。
FAT要占用的存储空间总数为:3 * 1.2M = 3.6Mnull8. 假
算机系统采用CSCAN(循环扫描)磁盘调度策略,使用2KB的内存空间记录16 384个磁盘块的空闲状态。[全国联考2010]
(1)请说明在上述条件下如何进行磁盘块空闲状态的管理。
(2)设某单面磁盘旋转速度为每分钟6000转,每个磁道有100个扇区,相邻磁道间的平均移动时间为1ms。若在某时刻,磁头位于100号磁道处,并沿着磁道号增大的方向移动(如下图所示),磁道号请求队列为50、90、30、120,对请求队列中的每个磁道需读取1个随机分布的扇区,则读完这4个扇区总共需要多少时间?要求给出计算过程。随机分布的某扇区0号磁道磁头当前运动方向100号磁道
(3)如果将磁盘替换为随机访问Flash半导体存储器(如U盘、SSD等),是否有比CSCAN更高效的磁盘调度策略?若有,给出磁盘调度策略的名称并说明理由;若无,说明理由。nullnull解:(1)2KB = 2*1024*8bit = 16384bit。因此可以使用位图法进行磁盘块空闲状态管理,每1bit表示一个磁盘块是否空闲。
(2)根据CSCAN算法,被访问的磁道号顺序为100、120、30、50、90,因此,寻道用去的总时间为:(20 + 90 + 20 + 40)* 1ms = 170ms;每分钟6000转,转一圈的时间为0.01s,一个扇区的读取时间为0.01/100=0.0001s,一个扇区的平均旋转延迟时间为(0+0.01)/2,总共要随机读取四个扇区,总共用去的旋转延迟时间和传输时间为:(0.01*0.5 + 0.0001)*4 = 0.0204s = 20.4ms所以;读完这4个扇区总共需要 170ms + 20.4ms = 190.4ms。null(3)若将磁盘换为U盘等,有比CSCAN更高效的磁盘调度策略。U盘的存储介质为电可擦除只读存储器(EEPROM)的变种,其寻址方式类似于内存的寻址方式,不涉及到磁盘的寻道、寻扇区等操作,因此可采用先来先服务、优先级高者优先等算法。null9. 在实现文件系统时,为加快文件目录的检索速度,可利用“文件控制块分解法”。假设目录文件存放在磁盘上,每个盘块512字节。文件控制块占64字节。其中文件名占8字节。通常将文件控制块分解成两部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其它描述信息)。 【北京大学1997】
(1)假设某一目录文件共有254个文件控制块,试分别给出采用分解法前和分解法后,查找该目录文件的某一个文件控制块的平均访问磁盘次数。
(2)一般地,若目录文件分解前占用n个盘块,分解后改用m个盘块存放文件名和文件内部号部分,请给出访问磁盘次数减少的条件。null【分析】目录文件也被看做一个文件,本身也需要一定数量的物理数据块。设目录文件需要的物理数据块为n,在单级目录中,对于线性检索法,检索某一个文件在目录文件中的那部分控制块,最好的情况只需要1次I/O(即在第一个物理数据块中),最坏的情况需要n次I/O(即在最后一个物理数据块中)。如果不采用分解法,则平均访问磁盘次数为(1+n)/2;如果采用分解法,还需读取一次磁盘以找到文件控制块的所有内容,设分解后目录文件占用m个盘块,则平均访问磁盘次数为(1+m)/2+1。所以,关键是计算不采用分解法和采用分解法两种情况下目录文件本身所需的物理数据块。null解:
(1)采用分解法前,目录所需的磁盘块数为(64*254)/512=31.75,也就是32块。所以查找该目录文件中的某一个文件控制块的平均访问磁盘次数为(1+32)/2=16.5。
采用分解法后,目录所需的磁盘块数为(10*254)/512=4.96,也就是5块,检索目录文件后,还需读取一次磁盘以找到文件控制块的所有内容。所以查找该目录文件中的某一个文件控制块的平均访问磁盘次数为(1+5)/2+1=4。
(2)访问磁盘次数减少的条件是:(1+m)/2+1<(1+n)/2,即m