资源描述
单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,北京交通大学计算机学院,1,操作系统（,A,）,北京交通大学计算机学院,何永忠 副教授,第五章：设备管理,02 十月 2024,北京交通大学计算机学院,2,02 十月 2024,北京交通大学计算机学院,第六章 文件管理,6.1,文件和文件系统,6.2,文件的逻辑结构,6.3,外存分配方式,6.4,文件（空闲）存储空间管理,6.5,目录管理,6.6,文件共享与保护,6.7,数据一致性控制,3,02 十月 2024,北京交通大学计算机学院,6.4,文件（空闲）存储空间管理,6.4.1,管理目标与技术要领,6.4.2,空闲表法,6.4.3,空闲链表法,6.4.4,位示图法,6.4.5,成组链接法,4,02 十月 2024,北京交通大学计算机学院,管理目标与技术要领,文件存储空间管理目标,外存空间利用与文件访问速度,文件存储空间管理技术要领,连续分配与离散分配优劣各异,文件物理结构与存储组织方式,分配以掌握空间使用情况为前提,存储空间使用情况数据结构,存储空间的分配与回收,基本分配单位为磁盘块,5,02 十月 2024,北京交通大学计算机学院,6.4,文件存储空间管理,6.4.1,管理目标与技术要领,6.4.2,空闲表法,6.4.3,空闲链表法,6.4.4,位示图法,6.4.5,成组链接法,6,02 十月 2024,北京交通大学计算机学院,空闲表法,属于连续分配方式,空闲盘区的分配,首次适应算法,循环首次适应算法,最佳适应算法,最坏适应算法,空闲盘区的回收,考虑回收区域插入点前后盘块区是否相邻接，相邻则予合并,序号,第一空闲盘块号,空闲,盘块数,0,3,3,1,8,5,2,16,2,3,空闲盘块（区）表,适用场合,？,7,02 十月 2024,北京交通大学计算机学院,6.4,文件存储空间管理,6.4.1,管理目标与技术要领,6.4.2,空闲表法,6.4.3,空闲链表法,6.4.4,位示图法,6.4.5,成组链接法,8,02 十月 2024,北京交通大学计算机学院,空闲链表法,将所有空闲盘块区拉成一条空闲链,空闲盘块链,以盘块为基本元素链接,分配与回收,空闲盘区链,以盘区为基本元素链接，且每个盘区除含有指示下一个盘块区的指针外，还应标有指明本盘区大小的信息,分配与回收,为提高对空闲盘区的检索速度，可采用显式链接方式,9,02 十月 2024,北京交通大学计算机学院,6.4,文件存储空间管理,6.4.1,管理目标与技术要领,6.4.2,空闲表法,6.4.3,空闲链表法,6.4.4,位示图法,6.4.5,成组链接法,10,02 十月 2024,北京交通大学计算机学院,位示图,利用位示图（即二维数组,Mapm,n,）的一位（,0/1,）来表示磁盘中一个盘块的使用情况，磁盘上所有盘块都与一个二进制位相对应,1 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0,1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1,1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0,1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0,1 2 3 4 5 6 7 8 9,10 11 12 13 14 15 16,1,2,3,16,11,02 十月 2024,北京交通大学计算机学院,盘块的分配,Var,Map:array 1.m,1.n of bit;,顺序扫描位示图，找出一个或一组其值均为空闲的二进制位,将所找到的一个或一组二进制位,Mapi,j,的行,/,列号转换为与之对应的盘块号,b,：,b=n(i-1)+j-1,按盘块号分配盘块，同时修改位示图,12,02 十月 2024,北京交通大学计算机学院,盘块的回收,将回收盘块的盘块号,b,转换为位示图中的行号,i,和列号,j,：,i=b DIV n+1;,j=b MOD n+1;,按盘块号回收盘块,根据回收盘块对应二进制位的行,/,列号修改位示图,13,02 十月 2024,北京交通大学计算机学院,6.4,文件存储空间管理,6.4.1,管理目标与技术要领,6.4.2,空闲表法,6.4.3,空闲链表法,6.4.4,位示图法,6.4.5,成组链接法,14,02 十月 2024,北京交通大学计算机学院,成组链接法,100,300,299,202,201,0,1,98,99,空闲盘块号栈,S.free,100,400,399,301,100,500,499,401,100,0,7999,7901,201#,299#,300#,399#,400#,7900#,7899#,7999#,301#,7801#,7901#,15,02 十月 2024,北京交通大学计算机学院,空闲盘块的分配,检查空闲盘块号栈是否上锁：,如未上锁，则从栈顶取出一空闲盘块号，,若其不是栈底,S.free(0),即空闲盘块号数,N,1,，则将其对应盘块分配给用户，然后将栈顶指针下移一格，亦即做,N,的减,1,操作,若其是栈底,S.free(0),即,N,=1,且其值为,0,，则分配失败返回；否则调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中作为新的空闲盘块号栈的内容，同时将该盘块号对应的盘块分配给用户,如上锁，则等待,分配盘块缓冲，然后返回,16,02 十月 2024,北京交通大学计算机学院,空闲盘块的回收,检查空闲盘块号栈，若未上锁：,若栈中空闲盘块号数,N100,即栈未满，则执行空闲盘块号数,N,的加,1,操作，并将回收盘块的盘块号记入空闲盘块号栈的栈顶,否则，若栈中空闲盘块号数,N,已达,100,即栈已满，应将空闲盘块号栈的当前内容包括盘块数及所有盘块号记入新回收的盘块中，同时将新回收盘块的盘块号作为,S.free(0),即栈底，并置空闲盘块号栈的空闲盘块数,N,为,1,返回,否则已上锁，等待,17,02 十月 2024,北京交通大学计算机学院,6.4,文件存储空间管理,6.4.1,管理目标与技术要领,6.4.2,空闲表法,6.4.3,空闲链表法,6.4.4,位示图法,6.4.5,成组链接法,18,02 十月 2024,北京交通大学计算机学院,第六章 文件管理,6.1,文件和文件系统,6.2,文件的逻辑结构,6.3,外存分配方式,6.4,文件存储空间管理,6.5,目录管理,6.6,文件共享与保护,6.7,数据一致性控制,19,02 十月 2024,北京交通大学计算机学院,6.5,目录管理,6.5.1,目录管理基本要求,6.5.2,文件控制块,6.5.3,索引结点,6.5.4,目录结构,6.5.5,目录查询技术,20,02 十月 2024,北京交通大学计算机学院,目录管理功能及要求,目录引入理由,文件的有效管理与组织要求基于文件名便能快速、准确地找到指定文件,文件目录管理的功能及要求,实现“按名存取”（文件名,外存地址）,提高目录检索速度及文件存取速度,文件共享（外存保留一份文件副本）,允许文件重名，以便于文件使用,21,02 十月 2024,北京交通大学计算机学院,6.5,目录管理,6.5.1,目录管理基本要求,6.5.2,文件控制块,6.5.3,索引结点,6.5.4,目录结构,6.5.5,目录查询技术,22,02 十月 2024,北京交通大学计算机学院,文件控制块,基本概念,文件,文件控制块文件目录项,文件目录,文件控制块有序集合目录文件,主要信息内容,基本信息（文件名、物理位置、结构类型）,存取控制信息（各类用户存取权限）,使用信息（建立,/,上次修改日期及时间）,当前使用信息（当前已打开该文件的进程数、是否被其它进程锁住、文件在内存是否已修改但尚未拷贝到盘上）,23,02 十月 2024,北京交通大学计算机学院,MS-DOS,文件控制块内容一览,文件控制块长度为,32,字节,文件名及文件扩展名共,11,个字符,对于,360KB,的软盘，总共含有,112,个,FCB,，故占有,4KB,的存储空间,文件名,文 件扩展名,文件属性,备 用,文件建立时 间,文件建立日 期,文件所在,第一盘块号,文件长度,(,盘块数,),24,02 十月 2024,北京交通大学计算机学院,6.5,目录管理,6.5.1,目录管理基本要求,6.5.2,文件控制块,6.5.3,索引结点,6.5.4,目录结构,6.5.5,目录查询技术,25,02 十月 2024,北京交通大学计算机学院,索引结点的引入,必要性,文件目录存放在磁盘上，且可能要占用大量盘块,N,，检索开销很大（,盘块调入次数,N+,1/2,）,可行性,只有文件名对目录检索有用,文件名,索引结点编号,文件名,1,文件名,2,文件名,3,文件描述控制信息,索引结点（,i,结点）集合,UNIX,文件目录,26,02 十月 2024,北京交通大学计算机学院,索引结点检索开销分析,举例说明,盘块大小,1KB,，文件目录共,3200,个,FCB,引入索引结点前,FCB,占,64B,，每盘块包含,16,个,FCB,，文件目录共需占用,200,个盘块，故查找一个文件平均需启动磁盘,100.5,次,引入索引结点后,目录项仅占,16B,（文件名和索引结点指针分别占用,14B,和,2B,），每盘块包含,64,个目录项，文件目录共需占用,50,个盘块，故查找一个文件平均需启动磁盘,25.5,+1,次,27,02 十月 2024,北京交通大学计算机学院,磁盘索引结点与内存索引结点,磁盘索引结点,文件,磁盘索引结点,主要内容（文件主标识、文件类型、文件存取权限、文件长度、文件存取时间、文件物理地址、文件连接计数）,内存索引结点,文件打开时对磁盘索引结点在内存的拷贝,专有内容（索引结点编号、索引结点状态、索引结点访问计数、文件所述文件系统逻辑设备号、空闲链表,/,散列队列指针）,28,02 十月 2024,北京交通大学计算机学院,6.5,目录管理,6.5.1,目录管理基本要求,6.5.2,文件控制块,6.5.3,索引结点,6.5.4,目录结构,6.5.5,目录查询技术,29,02 十月 2024,北京交通大学计算机学院,单级目录结构,文件创建,目录检索,申请空目录项属性设置,文件删除,目录检索,外存空间回收目录项回收,缺点,查找速度慢、不允许重名、不便于文件共享,文件名,状态位,物理地址,文件其它属性,Alpha.wps,Report.ppt,Text.dat,30,02 十月 2024,北京交通大学计算机学院,两级目录结构示意图,用户名,指向用户子目录的指针,Zhai,Gao,Shou,Alpha,Test,Zhai,用户目录,Report,Test,Gao,用户目录,Beta,Device,Misx,Shou,用户目录,Alpha,Test,Beta,Device,Misx,Report,Test,主文件目录,MFD,31,02 十月 2024,北京交通大学计算机学院,两级目录结构评析,优点,提高了目录检索速度,MFD,含,n,个,UFD,，,UFD,最多有,m,个目录项，则为找到指定文件最多需检索,n+m,个目录项；对于单级目录结构，最多需检索,n,m,个目录项,不同用户目录可使用相同的文件名,不同,用户可用不同名称访问同一共享文件,缺点,用户隔离不便于文件共享和用户间协作,32,02 十月 2024,北京交通大学计算机学院,树型目录结构示意图,A,B,C,1,6,D,E,F,2,F,E,D,3,4,G,H,5,I,C,J,N,K,12,L,M,N,13,O,H,P,14,7,8,9,10,11,15,16,18,19,21,22,20,17,23,33,02 十月 2024,北京交通大学计算机学院,树型目录结构实现机制及评析,路径名（绝对路径名）,从根目录到各数据文件之间只有唯一的通路，该路径上的全部目录文件名与数据文件名用“,/”,连接形成特定数据文件的路径名,相对路径名,当前目录,（工作目录）,从当前目录开始逐级通过中间目录文件最后到达所访问数据文件的路径名称为相对路径名,目录
展开阅读全文