目录管理和文件存储空间的管理.ppt

第六章文件管理,6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制,6.4目录管理,目录管理的基本要求:实现按名存取提高对目录的检索速度允许文件共享允许文件重名6.4.1文件控制块和索引结点1.文件控制块(FCB):是操作系统为管理文件而设置的用于描述和控制文件的数据结构,存放了为管理文件所需的所有有关信息。文件和FCB一一对应,FCB的有序集称为文件目录,一个FCB就是一个目录项,为实现对文件目录的管理,通常将文件目录以文件的形式保存在外存上,这个文件就叫目录文件。,文件控制块的内容：基本信息:文件名：扩展名,文件主名文件物理地址:存放设备名,起始盘块号,文件长度文件逻辑结构:流式或记录文件,记录数，定长或变长文件物理结构:顺序、链接式、索引文件存取控制信息:文件主、核准用户和一般用户的存取权限使用信息:文件的建立日期,最后修改日期,最后访问日期,当前使用信息(共享计数,是否被锁住,已被修改是否存盘),2.索引结点(i结点)(1)索引结点的引入当目录中文件很多时,文件目录要占用大量的盘块,查找目录时需要将这些盘块逐块调入内存,将给定的文件名与目录中的文件名逐一比较;假如一个FCB为64B,1KB的盘块只能存16个FCB,一个目录有640个FCB,需占用40个盘块,查找一个目录平均要启动磁盘20次。检索目录时只用到了文件名,如果将FCB中的文件名和描述信息分开存储,就可以增加目录的每个盘块中的文件数,减少访盘次数,加快检索速度;UNIX系统中就采用这种方法,将文件描述信息单独存放在索引结点中(简称i结点),目录项仅由文件名和指向该文件对应的i结点的指针构成。,UNIX的文件目录,UNIX的目录项仅占16B,1KB的盘块能存64个目录项访盘次数降到原来的1/4。,(2)磁盘索引结点存放在磁盘上的索引结点，每个文件有唯一的一个,modeownerstimestampssizeblockcounti.addr(0)i.addr(1)i.addr(9)i.addr(10)i.addr(11)i.addr(12),（1）文件主标识符：拥有该文件的个人或者小组的标识符；（2）文件类型：正规文件，目录文件或者特别文件；（3）文件存取权限：指各类用户对文件的存取权限；（4）文件物理地址：以直接或者间接方式给出数据文件所在盘块的编号；（5）文件长度：以字节为单位的文件长度；（6）文件连接计数：指向该文件的文件名的指针计数；（7）文件存取时间：文件最近被进程存取的时间、修改时间等。,(3)内存索引结点存放在内存上的索引结点，文件打开时将磁盘索引结点拷贝到内存的索引结点中，并增加以下几项当前正使用的内容。,(1)索引结点编号:用来标识内存索引结点(2)状态:i结点是否上锁或被修改(3)访问计数:正在访问此i结点的进程数(4)文件所属文件系统的逻辑设备号(5)链接指针:指向空闲链表和散列队列的指针,6.4.2.目录结构,1.单级目录结构最简单的目录结构，整个系统中只建立一张目录表，每个文件占用一个目录项；目录项中含有文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其他文件属性，此外还包括状态位，表示目录项是否空闲。,根目录,file1,file2,file3,单级目录,单级文件目录的优缺点优点：简单且能实现目录管理的基本功能-按名存取；缺点：（1）查找速度慢（2）不允许重名（3）不便于实现文件共享,只适用于单用户环境,2.两级目录结构为改变一级目录文件目录命名冲突,而改进,可用不同文件名共享同一文件。目录分为两级:一级称为主文件目录MFD,给出用户名,用户子目录所在的物理位置;二级称为用户文件目录UFD(用户子目录),给出该用户所有文件的FCB。目录项中含有文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其他文件属性，此外还包括状态位，表示目录项是否空闲。,MFD,用户名指针ZhangWangLi.,UFD(Z),FCB(fz1)FCB(fz2)FCB(fz3).,fz1fz2fz3,.,UFD(W),FCB(fw1)FCB(fw2).,fw1fw2,.,UFD(L),FCB(fl1)FCB(fl2).,fl1fl2,.,二级目录结构,根目录,root,Liu,Wan,file1,file2,a,a,b,二级目录,两级文件目录的优点提高了检索目录的速度；不同用户目录中可以使用相同的文件名；不同用户可以使用不同文件名来访问系统中的同一个共享文件。缺点：增加了系统空间开销,3.多级目录结构1）目录结构适用于大型文件系统，可以提高对目录的检索速度和文件系统性能；又称为树形目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其他目录作为树的结点。,2）路径名在树型目录结构,从根目录到各文件,用经历的全部目录名和文件名表示唯一的路径名。3）当前目录可为每个进程设置一个“当前目录”,又称为“工作目录”。进程对文件的访问都相对于“当前目录”进行。把从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名(relativepathname)；而把从树根开始的路径名称为绝对路径名(absolutepathname)。优点：层次结构清晰,便于管理和保护,解决重名问题,文件共享问题,查找速度加快。缺点：增加了系统空间开销,查找一个文件按路径名逐层检查,由于每个文件都放在外存,级数太多时访盘次数增多影响速度。,4.增加和删除目录目录的增加：用户可为自己建立UFD，并可再创建子目录。用户要创建一个新文件时，需检查所在目录中有无重名文件目录的删除：空目录可直接删除，并使其在上一级目录中对应的目录项为空。非空目录的处理：不可删非空目录（DOS）；可删非空目录（windows等）,6.4.3目录查询技术1.线性检索法单级目录：用户给出文件名,按名顺序查找目录项多级目录根据路径名顺序查找各级目录：全路径名：从根开始相对路径：从当前路径各级目录未查到时应停止查询,返回文件未找到,查到则根据盘块号指针读入下级目录继续查。,2.Hash方法建立一张Hash索引文件目录,利用Hash函数直接将文件名转换为索引值直接查找,解决冲突的规则:(1)该目录项为空则未找到(2)文件名(或子目录名)匹配则找到(3)该目录项非空则发生冲突,将Hash值加一常数(与目录长度互质)继续查找,为文件分配存储空间和内存分配比较类似，同样采取连续分配和离散分配，前者具有较高的文件访问速度，但容易产生零头；后者能有效利用外存空间，但访问速度较慢。,6.5文件存储空间管理,6.5文件存储空间的管理,6.5.1空闲表法和空闲链表法,1.空闲表法连续分配,6.5.2位示图法：CP/M、Apple-Dos,6.5.3成组链接法：UNIX,空闲表：记录空区信息（表项序号；首盘号；盘块数）分配和回收：似动态分区,首次适应，循环特点：具有较高的分配速度，可减少访问磁盘的频率常用：对换区；文件区：簇小文件连续（大文件离散）,2.空闲链表法,空闲盘块链：将磁盘所有的空闲空间，以盘块为单位拉成一条链；空闲盘区链：将所有的空闲盘区（包括若干个盘块）拉成一条链,每个空闲区含指向下一空闲区指针和空闲块数。,6.5.2.位示图法,位示图：利用二进制的一位来表示磁盘中一个盘块的使用情况，“0”表示对应的盘块空闲，“1”表示已分配。磁盘上的所有盘块都有一个二进制位与之对应，由所有盘块所对应的位构成一个集合，称为位示图。通常可用mn个位数来构成位示图，并使mn等于磁盘的总块数,位示图也可描述为一个二维数组map：Varmap:arrayofbit；,盘块的分配（1）顺序扫描位示图，找出一个或一组“0”的二进制位；（2）将找到的二进制位转换成相应的盘块号b=n(i-1)+j（3）修改位示图，令mapi,j=1。,盘块的回收（1）将回收的盘块号转换成位示图中的行号和列号，i=(b-1)DIVn+1,j=(b-1)MODn+1；（2）修改位示图，令mapi,j=0。,优点：从位示图中很容易找到一个或一组相邻接的空闲盘块。位示图很小，占用空间少，因而可将它保存在内存中，节省了许多磁盘的启动操作。,1.位示图（bitmap）可用于磁盘空间的管理。设某系统磁盘共有500块，块号从0到499，第0字的第0位表示第0块，第0字的第1位表示第1块，依此类推。若用位示图管理这500块的盘空间，当字长为32位时，第i个字节第j位对应的块号是（）。【浙江大学2004】A.32i+jB.32i+j-1C.32i+j-32D.32i+j-32-12.若8个字（字长32位）组成的位示图管理内存，假定用户归还一个块号为100的内存块时，它对应位示图的位置为（）。【北京理工2002】A.字号为3，位号为5B.字号为4，位号为4C.字号为3，位号为4D.字号为4，位号为5【注】假定字号、位号、块号均从1开始算起，而不是从0开始。,A,B,空闲表和空闲链表不适用于大型文件系统(表太长)，UNIX系统将这两种方法相结合，将空闲盘块分成组，每组第一块存一个空闲表成组链接起来，兼二者之优点克服了它们的缺点。,6.5.3.成组链接法,1.空闲盘块的组织:(1)空闲盘块号栈:此栈存储当前正在分配的一组空闲盘块号及本组尚有的空闲块总数N,N兼作栈顶指针。如:N=100,S.free(0)S.free(99)存储当前组空闲盘块号(2)每组的第一块存储下一组空闲盘块号形成链。(3)最末组的空闲盘块号栈存放在前一组的第一空闲块中,其中的S.free(0)存放结束标志。,