操作系统第6章文件管理(5).ppt

第六章 文件管理 文件和文件系统 文件的逻辑结构 外存分配方式 目录管理 文件存储空间的管理 文件共享与文件保护 数据一致性控制 文件存储空间的管理 空闲表法和空闲链表法 位示图法 成组链接法 空闲表法和空闲链表法 文件存储空间管理的基本分配单位是盘块 空闲表法 空闲表属于连续分配方式，与内存的动态分配方式雷同，为每个文件分配一个连续的存储空间 为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个闲表项，将所有空闲区按起始盘块号递增的顺序排列 存储空间的分配与回收可采用首次适应算法、循环首次适应算法等 如对换方式中对对换空间的分配就采用连续分配，主要目的是提高速度，p113 系统中的较小文件也采用连续分配方式，如“簇” 空闲表法和空闲链表法 存储空间的分配与回收 空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等 在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并 文件存储空间的管理 空闲表法和空闲链表法 位示图法 成组链接法 位示图法 位示图 用二进制的一位来表示磁盘中一个盘块的使用情况 0表示盘块空闲，1表示盘块已分配 由所有盘块所对应的二进制位构成的一个集合称为位示图，通常可用m*n个位数来构成位示图，并使m*n等于磁盘总块数 位示图法 位示图法 盘块的分配 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时) 将所找到的一个或一组二进制位， 转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示的第i行、第j列，则其相应的盘块号应按下式计算 b = n(i - 1) + j 修改位示图， 令map[i,j]=1 位示图法 盘块的回收 将回收盘块的盘块号转换成位示图中的行号和列号。 转换公式为 i = (b - 1) DIV n + 1 j = (b - 1) MOD n + 1 修改位示图， 令map [i,j]=0 （当“0”表示盘块空闲时） 如上例中，第16号物理块，可计算得 i = (16 - 1) DIV 16 + 1 = 1 j = (16 - 1) MOD 16 + 1 = 16 同理，第17块可计算得 i = (17 - 1) DIV 16 + 1 = 2 j = (17 - 1) MOD 16 + 1 = 1 文件存储空间的管理 空闲表法和空闲链表法 位示图法 成组链接法 成组链接法 在大型文件系统中，空闲表或空闲链表太长，在UNIX系统中，两种方法结合形成成组链接法 空闲盘块的组织 将空闲表和空闲链表结合形成的空闲盘块管理方法 空闲盘块号栈 用来存放当前可用的一组空闲盘块号以及栈中尚有的空闲盘块数N 文件区中的所有空闲盘块被分成若干个组，如100块/组 将每组含的有盘块数和该组所有盘块号记入前一组第一个盘块中 将第一组的空闲盘块数和所有盘块号记入空闲盘块号栈 成组链接法 成组链接法 设每100盘块为1组，系统共10000个盘块，从201至7999用于文件区，则第1组为盘块号201-300，第2组为301-400，...，最后一组为7901-7999 每一组的盘块总数N和盘块号记入前一组的第一个盘块S.free(0)~S.free(99) 将第一组盘块总数和盘块号记入空闲盘块号栈 最末一组的S.free(0)为“0”，表示空闲盘块链结束 成组链接法 空闲盘块的分配与回收 分配 检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格 若该盘块号已是栈底， 即S.free(0)，这是当前栈中最后一个可分配的盘块号 调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去 分配一相应的缓冲区 把栈中的空闲盘块数减1并返回 成组链接法 空闲盘块的分配与回收 回收 将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作 当栈已满时，记入新回收的盘块中，再将其盘块号作为新栈底 第六章 文件管理 文件和文件系统 文件的逻辑结构 外存分配方式 目录管理 文件存储空间的管理 文件共享与文件保护 数据一致性控制 文件共享与文件保护 基于索引结点的共享方式 利用符号链实现文件共享 文件的保护机制 磁盘容错技术 基于索引结点的共享方式 文件共享形式与目的 定义：系统应允许多个用户共享同一份文件，在系统中只保留一份共享文件的备份 共享形式 被多个用户使用，由存取权限控制 被多个程序使用