资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,第六章文 件 管 理,第六章文 件 管 理,6.1,文件和文件系统,6.2,文件的逻辑结构,6.3,外存分配方式,6.4,目录管理,6.5,文件存储空间的管理,6.6,文件共享与文件保护,6.7,数据一致性控制,第六章文 件 管 理 6.1文件和文件系统,1,空闲表和空闲链表不适用于大型文件系统,(,表太长,),,,UNIX,系统将这两种方法相结合,,将空闲,盘,块,分成组,每组第一块存一个空闲表成组链接起来,,兼二者之优点克服了它们的缺点。,.,6.5.3.,成组链接法,空闲表和空闲链表不适用于大型文件系统(表太长),,2,1.,空闲盘块的组织,:,(1),空闲,盘,块,号,栈:此栈存储当前正在分配的一组,空闲,盘,块,号及本组尚有的空闲块总数,N,N,兼作栈顶指针。,如,:N=100,S.free(0)S.free(99),存储当前组,空闲,盘,块,号,(2),每组的第一块存储下一组空闲,盘,块,号,形成链。,(3),最末组的,空闲,盘,块,号,栈,存放在前一组的第一空闲,块,中,其中的,S.free(0),存放结束标志。,1.空闲盘块的组织:,3,图,6-23,空闲盘块的成组链接法,图6-23空闲盘块的成组链接法,4,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,300,299,201,N,S.free(0),S.free(1),S.free(99),100,400,399,301,.,99,0,999,901,.,.,.,.,2.空闲块的分配和回收:100N 100.99.,5,6.6,文件共享与文件保护,文件共享指系统允许,多个用户,(,进程,),使用同,一个文件,(,或子目录,),。系统只需保留该共享文件的一份副本,,这样可以节省时间和存储空间,减少了用户工作量。,当前常用两种文件共享方法:,6.6.1,基于索引结点的共享方式,在树型结构的目录中,当有两个(或多个)用户要共享一个子目录或文件时,必须将共享文件或子目录连接到两个或多个用户的目录中;,此时目录的结构已不再是树型结构而是一个有向非循环图。,6.6 文件共享与文件保护 文件共享指系统允许多个用户(进,6,如果文件的描述信息直接存储在用户的目录表中,,当某个用户对文件修改时这些描述信息的内容也可能发生变化,此时该文件的其它共享者目录的对应信息并未随之改变,,引起共享错误,。,如果文件的描述信息直接存储在用户的目录表中,当某个用户对文件,7,UFD(W),file1,UFD(Z),file2,count=2,W/file1,Z/file2,索引结点,为了解决这一问题可以,将目录表中文件的描述信息存储在索引结点中,,而仅将文件名和指向索引结点的指针存放在目录表中。索引结点中的,count,用作共享计数,(,链接计数,),。,UFD(W)UFD(Z)W/file1Z/fil,8,D E F,A B C,I J K,L N,G H,B/I,A/D/N,B/K,C/G,图中表示有向非循环图的目录结构,圆圈表示索引结点和文件本身。,D E FA B C I J K L N,9,UFD(C),owner=C,count=1,链接前,UFD(B),UFD(C),owner=C,count=2,链接后,UFD(B),owner=C,count=1,所有者删除后,问题:删除文件时怎样考虑?当文件主删除文件时可能会发生指针悬空。,UFD(C)owner=C链接前UFD(B),10,6.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,则只会因找不到文件访问失败,不会发生指针悬空。,6.6.2 利用符号链(Symbolic Link)实现文件,11,图,6-19,多级目录结构,图6-19多级目录结构,12,符号链的共享方式存在的,问题,:,当其他用户去读共享文件时,系统是根据给定的文件路径名,逐个分量,(,名,),地去查找目录,直至找到该文件的索引结点。因此,在,每次访问共享文件时,都可能要多次地读盘,。这使每次访问文件的开销甚大,且增加了启动磁盘的频率。,要为每个共享用户建立一条,符号链,,该链实际上是一个文件,要为它配置一个,索引结点,,这也,要耗费一定的磁盘空间,。,优点:,能够用于链接,(,通过计算机网络,),世界上任何地方的计算机中的文件,此时只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。,两种方法的共同,问题,:遍历文件系统,=,共享文件的多次遍历;,转存文件系统,=,共享文件的多个拷贝,符号链的共享方式存在的问题:,13,6.6.3,磁盘容错技术,磁盘容错技术,:通过设置冗余的磁盘驱动器、磁盘控制器等部件,来提高可靠性的技术。,系统(磁盘)容错技术,SFT,:,三级,SFT-1,低级,:,SFT-2,中级,:,SFT-3,高级,:,1,影响文件安全的因素,:人为因素;系统因素;自然因素,2,安全措施,:存取控制机制;磁盘容错技术;后备系统,3,容错技术,:设置冗余部件,来提高系统的可靠性;,6.6.3 磁盘容错技术 磁盘容错技术:通过设置冗,14,1.,第一级 磁盘容错技术,SFT-1,用于防止因磁盘表面缺陷造成的数据破坏或丢失,包括双份目录、双份文件分配表和写后读校验等措施。,(1),双份目录和双份文件分配表,(2),热修复重定向和写后读校验,热修复重定向:,将磁盘的,23%,作为热修复重定向区,写后读校验:,写盘后立即读并与原数据校验,1.第一级 磁盘容错技术SFT-1,15,2.,第二级 磁盘容错技术,SFT-2,防止磁盘驱动器和控制器故障导致的系统不正常;,(1),磁盘镜像,两个磁盘驱动器互为备份,(2),磁盘双工,通道、磁盘控制器和磁盘驱动都为双份,主,机,磁盘,控制器,通道,主,机,磁盘控制器,磁盘控制器,通道,通道,2.第二级 磁盘容错技术SFT-2主磁盘通道主磁盘控制器磁,16,3.,基于集群技术的容错功能,所谓集群,是指由一组互连的自主计算机组成统一的计算机系统,给人们的感觉是,它们是一台机器。,利用集群系统不仅可提高系统的并行处理能力,还可用于提高系统的可用性。,它包括三种工作模式:,(,1,)双机热备份模式,(,2,)双机互为备份模式,(,3,)公共磁盘模式,3.基于集群技术的容错功能,17,数据,0,数据,1,的备份,CPU,磁盘,0,数据,1,数据,0,的备份,磁盘,1,块交错备份,数据0数据1CPU磁盘0数据1数据0磁盘1块交错备份,18,重点难点学习提示,1,、顺序文件、索引文件和索引顺序文件,各自优缺点和适用于的场合,2,、连续分配、链接分配和索引分配,3,、位示图法和成组链接法,4,、目录管理,5,、文件共享方式,重点难点学习提示1、顺序文件、索引文件和索引顺序文件,各自优,19,对于本章的知识点,文件存储空间的管理可以命制综合应用题,混合索引下计算文件实际占用磁盘空间和最大文件、计算访问磁盘次数可以命制综合应用题,其它知识点可以命制单项选择题。,2009,年联考所占分值为,6,分,,2010,年联考所占分值为,6,分。,对于本章的知识点,文件存储空间的管理可以命制综合应用,20,1.,文件的顺序存取是()。,【,电子科大,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,、,1,B,A,B,1.文件的顺序存取是()。【电子科大2003】,21,4.,下列关于打开文件,open,和关闭文件,close,的叙述,只有()是错误的。,【,浙江大学,2006】,A.close(),操作告诉系统,不再需要指定的文件了,可以丢弃它,B.open(),操作告诉系统,开始使用指定的文件,C.,文件必须先打开,后使用,D.,目录必须先打开,后使用,4.下列关于打开文件open和关闭文件close的叙述,只,22,5.,考虑一个文件存放在,100,个数据块中。文件控制块、索引块或索引信息都驻留内存。那么如果(),不需要做任何磁盘,I/O,操作。,【,浙江大学,2006】,A.,采用,continuous allocation,策略,将最后一个数据块搬到文件头部,B.,采用,linked allocation,策略,将最后一个数据块插入文件头部,C.,采用,linked allocation,策略,将第一个数据块插入文件尾部,D.,采用,single level indexed allocation,策略,将最后一个数据块插入文件头部,D,5.考虑一个文件存放在100个数据块中。文件控制块、索引块,23,6.,逻辑文件的组织形式是由()决定的。,A.,存储介质特性,B.,操作系统的管理方式,C.,用户,D.,主存容量,【,分析,】,文件的逻辑结构是用户所观察到的文件组织形式,数据组织形式取决于用户需求,例如,登记操作日志记录导致顺序文件的产生;对数据库中结构化数据的存取导致随机访问文件的产生。所以,逻辑文件的组织形式取决于用户,因此应该选择,C,。,7.,物理文件的组织方式是由()确定的。,A.,操作系统,B.,主存容量,C.,外存容量,D.,应用程序,【,分析,】,文件的物理结构是指文件在外存上的存储组织形式,既与存储介质的存储性能有关,又与操作系统所采用的外存分配方法有关。因此应该选择,A,。,6.逻辑文件的组织形式是由()决定的。,24,7.,假定磁盘块的大小为,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.6M,7.假定磁盘块的大小为1K,对于540M的硬盘,其文件分配,25,8.,假设计算机系统采用,CSCAN,(循环扫描)磁盘调度策略,使用,2KB,的内存空间记录,16 384,个磁盘块的空闲状态。,全国联考,2010,(,1,)请说明在上述条件下如何进行磁盘块空闲状态的管理。,(,2,)设某单面磁盘旋转速度为每分钟,6000,转,每个磁道有,100,个扇区,相邻磁道间的平均移动时间为,1ms,。若在某时刻,磁头位于,100,号磁道处,并沿着磁道号增大的方向移动(如下图所示),磁道号请求队列为,50,、,90,、,30,、,120,,对请求队列中的每个磁道需读取,1,个随机分布的扇区,则读完这,4,个扇区总共需要多少时间?要求给出计算过程。随机分布的某扇区,0,号磁道磁头当前运动方向,100,号磁道,(,3,)如果将磁盘替换为随机访问,Flash,半导体存储器(如,U,盘、,SSD,等),是否有比,CSCAN,更高效的磁盘调度策略?若有,给出磁盘调度策略的名称并说明理由;若无,说明理由。,8.假设计算机系统采用CSCAN(循环扫描)磁盘调度策略,,26,随机分布的某扇区,0,号磁道,磁头当前运动方向,100,号磁道,随机分布的某扇区0号磁道磁头当前运动方向100号磁道,27,解:(,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,。,解:(1)2KB=2*1024*8bit=16384,28,(,3,)若将磁盘换为,U,盘等,有比,CSCAN,更高效的磁盘调度策略。,U,盘的存储介质为电可擦除只读存储器,(EEPROM),的变种,,其寻址方式类似于内存的寻址方式,不涉及到磁盘的寻道、寻扇区等操作,因此可采用先来先服务、优先级高者优先等算法。,(3)若将磁盘换为U盘等,有比CSCAN更高效的磁盘调度策略,29,9.,在实现文件系统时,为加快文件目录的检索速度,可利用“文件控制块分解法”。假设目录文件存放在磁盘上,每个盘块,512,字节。文件控制块占,64,字节。其中文件名占,8,字节。通常将文件控制块分解成两部分,第一部分占,10,字节(包括文件名和文件内部号),第二部分占,56,字节(包括文件内部号和文件其它描述信息)。,【,北京大学,1997】,(,1,)假设某一目录文件共有,254,个文件控制块,试分别给出采用分解法前和分解法后,查找该目录文件的某一个文件控制块的平均访问磁盘次数。,(,2,)一般地,若目录文件分解前占用,n,个盘块,分解后改用,m,个盘块存放文件名和文件内部号部分,请给出访问磁盘次数减少的条件。,9.在实现文件系统时,为加快文件目录的检索速度,可利用“文,30,【,分析,】,目录文件也被看做一个文件,本身也需要一定数量的物理数据块。,设目录文件需要的物理数据块为,n,,,在单级目录中,对于线性检索法,检索某一个文件在目录文件中的那部分控制块,最好的情况只需要,1,次,I/O,(即在第一个物理数据块中),最坏的情况需要,n,次,I/O,(即在最后一个物理数据块中)。,如果不采用分解法,则平均访问磁盘次数为(,1+n,),/2,;,如果采用分解法,还需读取一次磁盘以找到文件控制块的所有内容,,设分解后目录文件占用,m,个盘块,则平均访问磁盘次数为(,1+m,),/2+1,。,所以,关键是计算不采用分解法和采用分解法两种情况下目录文件本身所需的物理数据块。,【分析】目录文件也被看做一个文件,本身也需要一定数量的物理数,31,解:,(,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,,即,mn-2,。,解:,32,10.,某个系统采用成组链接法来管理磁盘空间,目前磁盘的状态如图所示。,(,1,)该磁盘中目前还有多少个空闲盘快?,(,2,)请简述磁盘块的分配过程。,(,3,)在为某个文件分配,3,个盘块后,系统要删除另一文件,并回收它所占的,5,个盘块,它们的盘块号依次为,700,、,711,、,703,、,788,、,701,,请画出回收后的盘块链接情况。,100,300,299,N,S.free(0),S.free(1),S.free(99),100,400,399,301,99,0,599,501,.,.,.,.,10.某个系统采用成组链接法来管理磁盘空间,目前磁盘的状态如,33,11,、有一文件系统如下图所示。图中的框表示目录,圈表示普通文件。,根目录常驻内存,,目录文件组织成链接文件,不设文件控制块,普通文件组织成索引文件。,目录表目指示下一级文件名及其磁盘地址,(,各占,2,个字节,共,4,个字节,),。若下级文件是目录文件,指示其第一个磁盘块地址。若下级文件是普通文件,指示其文件控制块的磁盘地址。每个目录文件磁盘块最后,4,个字节供链接使用。下级文件在上级目录文件中的次序在图中为自左至右。每个磁盘块有,512,字节,与普通文件的一页等长。,11、有一文件系统如下图所示。图中的框表示目录,圈表示普通文,34,根目录,A,B,C,D,H,I,P,U,L,E,F,G,J,K,M,N,Q,R,S,T,V,W,文件系统结构示意图,根目录ABCDHIPULEFGJKMNQRSTVW,35,普通文件的文件控制块组织如图所示。其中,,每个磁盘地址占,2,个字节,前,10,个地址直接指示该文件前,10,页的地址。第,11,个地址指示一级索引表地址,一级索引表中每个磁盘地址指示一个文件页地址;第,12,个地址指示二级索引表地址,二级索引表中每个地址指示一个一级索引表地址;第,13,个地址指示三级索引表地址,三级索引表中每个地址指示一个二级索引表地址。,问:,(1),一个普通文件最多可有多少个文件页?,(2),若要读文件,J,中某一页,最,多,启动磁盘多少次?,(3),若要读文件,W,中的某一页,最,少,启动磁盘多少次?,(4),就上一问而言,为最大限度减少启动磁盘的次数,可采用什么方法?此时,磁盘最多启动多少次?,普通文件的文件控制块组织如图所示。其中,每个磁盘地址占2个,36,该文件的有关描述信息,磁盘地址,磁盘地址,磁盘地址,磁盘地址,磁盘地址,1,2,11,12,13,普通文件的文件控制块组织,该文件的有关描述信息磁盘地址磁盘地址磁盘地址磁盘地址磁盘,37,38,解:,(1),由题目中所给条件可知,磁盘块大小为,512,字节,每个磁盘地址中,2,个字节。因此,一个一级索引表可容纳,256,个磁盘地址。同样地,一个二级索引表可容纳,256,个一级索引表地址,一个三级索引表可容纳,256,个二级索引表地址。这样,一个普通文件最多可有页数为:,10+256+256,256+256,256,256=16 843 018,解:(1)由题目中所给条件可知,磁盘块大小为512字节,每个,39,(2),从图中可以看出,目录文件,A,和目录文件,D,中,目录项都只有两个,因此这两个目录文件都不需拉链。若要读文件,J,中的每一页,首先从内存的根目录中找到目录文件,A,的磁盘地址,将其读入内存,(,第,1,次磁盘访问,),。然后再从目录,A,中找出目录文件,D,的磁盘地址,并将其读入内存,(,第,2,次磁盘访问,),。从目录,D,中找出文件,J,的,文件控制块地址,,将文件,J,的文件控制块读入内存,(,第,3,次磁盘访问,),。,在最坏情况下,,要访问页的磁盘地址需通过三级索引才能,找到,这时,要三次访问磁盘才能将三级索引表读入内存,(,第,4,、,5,、,6,次磁盘访问,),。最后读入文件,J,中的相应页,(,第,7,次访问磁盘,),。,由此可知,若要读文件,J,的某一页,,最多启动磁盘,7,次。,(2)从图中可以看出,目录文件A和目录文件D中,目录项都只有,40,(3),从图中可以看出,目录文件,C,和目录文件,U,中,目录项数目较多,若目录项数超过,127(512/4-1=127),,则目录文件的读入可能需要多次磁盘读,(,因目录文件组织成链接文件,),。,在最好情况下,所找的目录项都在目录文件的第一个磁盘块中,。若要读文件,W,中的某一页,首先从内存的根目录中找到目录文件,C,的磁盘地址,将其读入内存,(,第,1,次磁盘访问,),。在最好情况下,能从目录,C,的第一个磁盘块中找出目录文件,I,的磁盘地址,并将其读入内存,(,第,2,次磁盘访问,),。从目录,I,中找出目录文件,P,的磁盘地址,将其读入内存,(,第,3,次磁盘访问,),。从目录,P,中找到目录文件,U,的磁盘地址,将其读入内存,(,第,4,次磁盘访问,),。在最好情况下,能从目录,U,的第一个磁盘块中找出文件,W,的文件控制块地址,将文件,W,的文件控制块读入内存,(,第,5,次磁盘访问,),。,在最好情况下,要访问的页在前,10,页中,,这时可直接得到该页的磁盘地址。最后读入文件,W,中的相应页,(,第,6,次访问磁盘,),。,由此可知,,若要读文件,W,中的某一页,最少启动磁盘,6,次。,(3)从图中可以看出,目录文件C和目录文件U中,目录项数目较,41,(4),由于通过文件控制块访问文件所需的访问磁盘次数无法改变,,要减少访问磁盘的次数,只有通过减少访问目录文件的次数来达到。,为最大限度地减少启动磁盘的次数,可以将文件,W,直接链接在根目录的最左端,(,或其目录项在根目录的前,127,个项内,),。这样,若要读文件,W,中的某页时,首先从内存的根目录中找到文件,W,的文件控制块地址,将文件,W,的文件控制块读入内存,(,第,1,次磁盘访问,),。在最坏情况下,要访问页的磁盘地址需通过三级索引才能找到,这时要三次访问磁盘才能将三级索引表读入内存,(,第,2,、,3,、,4,次磁盘访问,),。最后读入文件,W,中的相应页,(,第,5,次访问磁盘,),。由此可知,,若将文件,W,直接链接在根目录的最左端,要读文件,J,中的某一页,最多启动磁盘,5,次。,(4)由于通过文件控制块访问文件所需的访问磁盘次数无法改变,,42,
展开阅读全文