交通923、927操作系统电子课件zgsosjiaoan

117二月2023北京交通大学计算机学院翟高寿主讲教师：翟高寿（副教授）联系电话：(办)电子邮件：制作人：翟高寿制作单位：北京交通大学计算机学院《操作系统》217二月2023北京交通大学计算机学院翟高寿第六章文件管理6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4文件存储空间管理6.5目录管理6.6文件共享与保护6.7数据一致性控制317二月2023北京交通大学计算机学院翟高寿6.3外存分配方式6.3.1文件物理结构与外存分配6.3.2连续分配6.3.3链接分配6.3.4索引分配417二月2023北京交通大学计算机学院翟高寿文件物理结构与外存分配文件物理结构（存储结构）文件在外存上的存储组织形式外存空间分配方法设计目标空间利用及文件访问速度外存分配方式与文件物理结构连续分配<=>顺序文件结构链接分配<=>链接式文件结构索引分配<=>索引式文件结构517二月2023北京交通大学计算机学院翟高寿6.3外存分配方式6.3.1文件物理结构与外存分配6.3.2连续分配6.3.3链接分配6.3.4索引分配617二月2023北京交通大学计算机学院翟高寿连续分配示意图filestartlengthcount02tr143mail196list284f62文件目录048121620242815913172125292610141822263037111519232731counttrmaillistf717二月2023北京交通大学计算机学院翟高寿连续分配评析外部碎片问题磁盘空间分割后形成的较小的无法存储文件的连续区紧凑方法主要优点顺序访问容易且速度快支持直接存取主要缺点要求有连续的存储空间，空间利用率低必须事先知道文件的长度817二月2023北京交通大学计算机学院翟高寿6.3外存分配方式6.3.1文件物理结构与外存分配6.3.2连续分配6.3.3链接分配6.3.4索引分配917二月2023北京交通大学计算机学院翟高寿链接分配基本思想支持离散分配方式，通过盘块上的指针实现同一文件多个离散盘块的链接优点评析消除了外部碎片，外存空间利用率高按需分配，且无需事先知道文件长度支持文件动态增长，方便文件增删改链接方式隐式链接/显式链接1017二月2023北京交通大学计算机学院翟高寿隐式链接示意图filestartendjeep925文件目录1625-11010481216202428159131721252926101418222630371115192327311117二月2023北京交通大学计算机学院翟高寿隐式链接问题及对策主要问题只适合顺序访问，对随机存取极其低效仅通过链接指针实现离散各盘块的链接，只要其中任何一个指针出现问题，都会导致整条链的断开，所以可靠性较差为了提高检索速度和减少指针所占用的存储空间，可将几个盘块组成一个簇，以簇为单位进行盘块分配缺点：内部碎片增大1217二月2023北京交通大学计算机学院翟高寿显式链接与文件分配表FAT6EOF11105EOF…4……9…01234567891011FCBAFCBB盘块号文件分配表FAT物理地址物理地址1317二月2023北京交通大学计算机学院翟高寿文件分配表空间开销计算设定盘块大小为1KB对于1.2MB的软盘，共有盘块1.2MB/1KB=1.2K∈（28,212）故文件分配表表项取12位即1.5B

所以FAT共需空间1.2K×1.5B=1.8KB对于200MB的硬盘，共有盘块200MB/1KB=200K∈（216,220）故文件分配表表项取20位即2.5B

所以FAT共需空间200K×2.5B=500KB1417二月2023北京交通大学计算机学院翟高寿6.3外存分配方式6.3.1文件物理结构与外存分配6.3.2连续分配6.3.3链接分配6.3.4索引分配1517二月2023北京交通大学计算机学院翟高寿索引分配的引入及基本思想链接分配方式的缺陷不能支持高效地直接存取若对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号FAT占用内存空间较大及文件所占盘块号随机基本思想文件打开仅须把该文件所占用盘块编号调入内存即可，故可将每个文件所对应的盘块号集中地存放一个所谓的索引块中，形成一个索引表索引块文件文件目录项索引块指针对于小文件，索引块利用率极低1617二月2023北京交通大学计算机学院翟高寿索引分配示意图file序号jeep19文件目录04812162024281591317212529261014182226303711151923273191610251-1-119索引块1717二月2023北京交通大学计算机学院翟高寿两/多级索引分配基本思想对于太大的文件和索引块太多时，直接用链接指针来链接索引块的方法显然是低效的，为此应引入多级索引分配方式允许文件最大长度两级索引、盘块大小1KB、盘块号占4B则一个索引块可含1KB/4B=256个盘块号，于是两级索引最多可含256×256=64K个盘块号，允许文件最大长度为64MB1817二月2023北京交通大学计算机学院翟高寿混合分配方式示意图modeowners(2)timestamp(3)sizeblockcounti.addr(0)i.addr(1)…i.addr(9)i.addr(10)i.addr(11)i.addr(12)Data…DataDataDataData………DataData……DataData………DataData……DataData………DataData……DataData………1917二月2023北京交通大学计算机学院翟高寿混合分配方式(UNIX系统)直接寻址直接地址项存放对应文件数据的盘块的盘块号盘块大小4KB、盘块号占4B，则支持长度在4KB×10=40KB以内的文件一次间接寻址i.addr(10)指向对应文件的一级索引块一级索引块可含4KB/4B=1K个盘块号，故支持长度在(4KB×1K=4MB)+40KB以内的文件多次间接寻址i.addr(11)、i.addr(12)分别指向对应文件的两级索引块和三级索引块，所以支持文件长度可达(4KB×1K×1K×1K=4TB)+(4KB×1K×1K=4GB)+4MB+40KB2017二月2023北京交通大学计算机学院翟高寿6.3外存分配方式6.3.1文件物理结构与外存分配6.3.2连续分配6.3.3链接分配6.3.4索引分配2117二月2023北京交通大学计算机学院翟高寿第六章文件管理6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4文件存储空间管理6.5目录管理6.6文件共享与保护6.7数据一致性控制2217二月2023北京交通大学计算机学院翟高寿6.4文件存储空间管理6.4.1管理目标与技术要领6.4.2空闲表法6.4.3空闲链表法6.4.4位示图法6.4.5成组链接法2317二月2023北京交通大学计算机学院翟高寿管理目标与技术要领文件存储空间管理目标外存空间利用与文件访问速度文件存储空间管理技术要领连续分配与离散分配优劣各异文件物理结构与存储组织方式分配以掌握空间使用情况为前提存储空间使用情况数据结构存储空间的分配与回收基本分配单位为磁盘块2417二月2023北京交通大学计算机学院翟高寿6.4文件存储空间管理6.4.1管理目标与技术要领6.4.2空闲表法6.4.3空闲链表法6.4.4位示图法6.4.5成组链接法2517二月2023北京交通大学计算机学院翟高寿空闲表法属于连续分配方式空闲盘区的分配首次适应算法循环首次适应算法最佳适应算法最坏适应算法空闲盘区的回收考虑回收区域插入点前后盘块区是否相邻接，相邻则予合并序号第一空闲盘块号空闲盘块数03318521623……空闲盘块（区）表适用场合？2617二月2023北京交通大学计算机学院翟高寿6.4文件存储空间管理6.4.1管理目标与技术要领6.4.2空闲表法6.4.3空闲链表法6.4.4位示图法6.4.5成组链接法2717二月2023北京交通大学计算机学院翟高寿空闲链表法将所有空闲盘块区拉成一条空闲链空闲盘块链以盘块为基本元素链接分配与回收空闲盘区链以盘区为基本元素链接，且每个盘区除含有指示下一个盘块区的指针外，还应标有指明本盘区大小的信息分配与回收为提高对空闲盘区的检索速度，可采用显式链接方式2817二月2023北京交通大学计算机学院翟高寿6.4文件存储空间管理6.4.1管理目标与技术要领6.4.2空闲表法6.4.3空闲链表法6.4.4位示图法6.4.5成组链接法2917二月2023北京交通大学计算机学院翟高寿位示图利用位示图（即二维数组Map[m,n]）的一位（0/1）来表示磁盘中一个盘块的使用情况，磁盘上所有盘块都与一个二进制位相对应110001001010011010010001010011111101100101001010

……110100101010001012345678910111213141516123…163017二月2023北京交通大学计算机学院翟高寿盘块的分配VarMap:array[1..m,1..n]ofbit;顺序扫描位示图，找出一个或一组其值均为空闲的二进制位将所找到的一个或一组二进制位Map[i,j]的行/列号转换为与之对应的盘块号b：b=n(i-1)+j-1按盘块号分配盘块，同时修改位示图3117二月2023北京交通大学计算机学院翟高寿盘块的回收将回收盘块的盘块号b转换为位示图中的行号i和列号j：i=bDIVn+1;j=bMODn+1;按盘块号回收盘块根据回收盘块对应二进制位的行/列号修改位示图3217二月2023北京交通大学计算机学院翟高寿6.4文件存储空间管理6.4.1管理目标与技术要领6.4.2空闲表法6.4.3空闲链表法6.4.4位示图法6.4.5成组链接法3317二月2023北京交通大学计算机学院翟高寿成组链接法100300299…202201019899空闲盘块号栈S.free100400399…301100500499…4019907999…7901201#299#300#…399#…400#7900#7899#…7999#…301#7801#7901#………3417二月2023北京交通大学计算机学院翟高寿空闲盘块的分配检查空闲盘块号栈是否上锁：如