第8章 磁盘存储管理

1、12021-11-21阜阳师范学院计算机与信息学院o 8.1 外存的组织方式o 8.2 文件存储空间的管理o 8.3 提高磁盘I/O速度的途径o 8.4 提高磁盘可靠性的技术o 8.5 数据一致性控制 主要任务和要求是： 有效地利用存储空间 提高磁盘的I/O速度 提高磁盘系统的可靠性第8章 磁盘存储器的管理22021-11-21阜阳师范学院计算机与信息学院文件的物理结构和外存分配方法有关连续分配方式 顺序式结构链接分配方式 链接式结构索引分配方式 索引式结构 8.1.1 连续分配8.1.2 链接分配8.1.3 索引分配 32021-11-21阜阳师范学院计算机与信息学院优点：顺序访问容易，支持

2、随机存取；存取速度很快缺点：分配连续的外存空间；事先知道文件的长度42021-11-21阜阳师范学院计算机与信息学院o 属于离散分配方式o 采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的文件称为链接文件。o 链接方式又可分为隐式链接和显式链接两种形式。52021-11-21阜阳师范学院计算机与信息学院隐式链接缺点：可靠性较差；不适合随机访问62021-11-21阜阳师范学院计算机与信息学院显式链接72021-11-21阜阳师范学院计算机与信息学院链式分配的优缺点o 离散分配方式o 消除了外部碎片o 提高了外存空间利用率o 便于文件

3、动态增长o 方便文件的增、删、改o 不能支持高效的直接存取o FAT需占用较大的内存空间优点：缺点：82021-11-21阜阳师范学院计算机与信息学院8.1.5 索引组织方式o每个文件一个索引块o不利于小文件（常采用链式）92021-11-21阜阳师范学院计算机与信息学院outer-index外部索引index table索引表File文件102021-11-21阜阳师范学院计算机与信息学院o直接地址o一次间接地址o多次间接地址112021-11-21阜阳师范学院计算机与信息学院122021-11-21阜阳师范学院计算机与信息学院例题1o 设文件索引节点中有7个地址项，其中4个地址项为直接地址

4、索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件的最大长度是：（ ）1057KB132021-11-21阜阳师范学院计算机与信息学院例题2 o 若某文件系统索引结点（inode）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）A. 索引结点的总数B. 间接地址索引的级数C. 地址项的个数D. 文件块大小A142021-11-21阜阳师范学院计算机与信息学院例题3o 下列文件物理结构中，适合随机访问且易于文件扩展的是：A. 连续结构B. 索引结构 C. 链式结构 D.

5、 顺序结构B152021-11-21阜阳师范学院计算机与信息学院8.2 文件存储空间的管理8.2.1 空闲表法和空闲链表法8.2.2 位示图法8.2.3 成组链接法162021-11-21阜阳师范学院计算机与信息学院8.2.1 空闲表法和空闲链表法序号第一空闲盘块号空闲盘块数12429331554172021-11-21阜阳师范学院计算机与信息学院存储空间的分配与回收o 与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等o 内存管理中虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地182021-

6、11-21阜阳师范学院计算机与信息学院空闲链表法o 空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：（1）空闲盘块链（2）空闲盘区链192021-11-21阜阳师范学院计算机与信息学院1101010000011000110111000011010100111 2 3 4 5 6 7 8 9 10 11 12123128.2.2 位示图法位示图o 位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。p 0表示盘块空闲，1表示已分配。p 磁盘上所有盘块所对应的位构成一个集合，称为位示图。p 通常可用m*n个位数来构成位示图，并使m*n等于磁盘的总块

7、数。p 如图,可看成是二维数组map(m,n)。202021-11-21阜阳师范学院计算机与信息学院盘块的分配和回收1)顺序扫描位示图，找到0二进制位。2)将所找到的一个或一组二进制位，转换成与之对应的盘块号。 盘块号=列数*（i-1）+j; （ i,j,b（盘块号）都从1开始） 盘块号=列数*i+j+1; （ i,j从0开始，b从1开始） 盘块号=列数*i+j; （ i,j从0开始，b从0开始）3) 修改位示图,令map(i,j)=1分配过程：1）将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为: i=(盘块号-1)div列数+1 j=(盘块号-1)mod列数+1（ i,j,b（盘块

8、号）都从1开始） i=(盘块号-1)div列数 j=(盘块号-1)mod列数 （i,j从0开始，b从1开始） i=盘块号div列数 j=盘块号mod列数 （i,j从0开始，b从0开始）2）修改位示图,令map(i,j)=0回收过程：212021-11-21阜阳师范学院计算机与信息学院例题4o 假定一个盘组共有100个盘面,每个盘面上有16个磁道,每个磁道分成4个扇区,问:(1) 整个磁盘空间共有多少个存储块？(2) 如果用字长32位的单元来构造位示图,共需多少个字？(3) 位示图中第18个字的第16位对应的块号是多少？ 分析：(1) 4*16*100=6400(2) 6400/32=200(3

9、) (18-1)*32+16=560222021-11-21阜阳师范学院计算机与信息学院8.2.3 成组链接法o 空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。o 在UNIX系统中采用的是成组链接法o 是将上述两种方法结合而形成的一种空闲盘块管理方法，它兼备了上述方法的优点而克服了表太长的缺点。232021-11-21阜阳师范学院计算机与信息学院空闲盘块的成组链接法示意图S.free(0)是栈底栈满时栈顶为S.free(99)242021-11-21阜阳师范学院计算机与信息学院空闲盘块的组织o 空闲盘块号栈n 用来存放当前可用的一组空闲盘块的盘块号（最多含100个

10、号），以及栈中尚有的空闲盘块号数No N还兼作栈顶指针n 例如：当N=100时，它指向S.free(99)，S.free(0)是栈底，栈满时栈顶为S.free(99)。252021-11-21阜阳师范学院计算机与信息学院空闲盘块的组织o 文件中的所有空闲盘块，被分成若干个组。o 将每一组含有的盘块总数N和该组的盘块号，记入其前一组的第一个盘块的S.free(0)S.free(99)中。这样由各组的第一个盘块形成了一条链。o 将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。o 最末一组只有99个盘块，在S.free(0)中则存放0，作为空闲盘块链的结束标志。8

11、.3 提高磁盘I/O速度的途径o 磁盘高速缓存(Disk Cache)o 提高磁盘I/O速度的其它方法o 廉价磁盘冗余阵列 (RAID)262021-11-21阜阳师范学院计算机与信息学院272021-11-21阜阳师范学院计算机与信息学院 指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，它是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。8.3.1 磁盘高速缓存(Disk Cache)1. 磁盘高速缓存的形式 指将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式，将数据交付给请求进程： (1) 数据交付 (2) 指针交付2. 数据交付方式282021-11

12、-21阜阳师范学院计算机与信息学院 磁盘缓存的调度算法很类似存储调度算法，但由于磁盘的区别，通常比虚拟存储复杂。除了考虑到最近最久未使用这一原则外，还考虑了以下几点： 访问频率、 可预见性、数据的一致性。3. 置换算法4. 周期性地写回磁盘8.3.1 磁盘高速缓存(Disk Cache)292021-11-21阜阳师范学院计算机与信息学院1. 提前读(Read-Ahead) 2. 延迟写 3. 优化物理块的分布 4. 虚拟盘 8.3.2 提高磁盘I/O速度的其它方法302021-11-21阜阳师范学院计算机与信息学院8.3.3 廉价磁盘冗余阵列 (RAID)1. 并行交叉存取是利用一台磁盘阵列

13、控制器，来统一管理和控制一组磁盘驱动器，从而组成一个高度可靠的快速的大容量磁盘系统。OS将RAID中一组物理磁盘驱动器看作是一个单个的逻辑磁盘驱动器，用户和系统数据可分布在阵列的所有磁盘中，并可采取并行传输方式。2. RAID的分级RAID的另一特点是高可靠性，可分成RAID0 RAID7几级，除了RAID0外，其它各级都采用了容错技术。312021-11-21阜阳师范学院计算机与信息学院影响文件安全性的主要因素及采取的措施：1)人为因素：采取存取控制机制2)系统因素：通过磁盘容错技术3)自然因素：通过后备系统8.4 提高磁盘可靠性的技术322021-11-21阜阳师范学院计算机与信息学院容错

14、技术：v 通过在系统中设置冗余部件的办法，提高系统可靠性的一种技术。v磁盘容错技术（系统容错技术SFTSystem Fault Tolerance）则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的一种技术。8.4 提高磁盘可靠性的技术332021-11-21阜阳师范学院计算机与信息学院磁盘容错技术： n SFT-1：低级磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢失； n SFT-2：中级磁盘容错技术，主要用于防止磁盘驱动器和磁盘控制器故障引起的系统不能正常工作； n SFT-3：高级磁盘容错技术，它基于集群技术实现容错。8.4 提高磁盘可靠性的技术34202

15、1-11-21阜阳师范学院计算机与信息学院第一级容错技术(SFT-1)常用的措施有： 双份目录和双份文件分配表（FAT）n 在不同的磁盘上或磁盘的不同区域中，分别建立两份目录表和FAT 热修复重定向和写后读校验n 热修复重定向n 写后读校验352021-11-21阜阳师范学院计算机与信息学院 第二级容错技术(SFT-2)o 磁盘镜像（Disk Mirroring）o 磁盘双工（Disk Duplexing）362021-11-21阜阳师范学院计算机与信息学院主 机磁 盘 控 制 器通道磁盘驱动器磁盘镜像（Disk Mirroring）磁盘驱动器故障的容错p 在同一磁盘控制器控制下，增设一个完全

16、相同的磁盘驱动器,如下图。p 每次将数据写主磁盘时，都需要采用写后检验方式，同时将数据也写入到备份磁盘。p 主磁盘驱动器发生故障时，则启动备份驱动器，并立即发出警告，尽快修复。不足之处：磁盘利用率为50%372021-11-21阜阳师范学院计算机与信息学院磁盘双工（Disk Duplexing）主 机通道磁盘驱动器 磁 盘控制器通道 磁 盘控制器p 磁盘控制器或控制器与CPU之间的通道故障的容错。p 将两台磁盘驱动器分别接到两个磁盘控制器上,如下图。p 两个磁盘上的数据完全相同。p 每个磁盘都有自己的独立通道382021-11-21阜阳师范学院计算机与信息学院8.5 数据一致性控制 8.5.1

17、 事务8.5.2 检查点8.5.3 并发控制392021-11-21阜阳师范学院计算机与信息学院8.5.1 事务1、事务（Transaction）的定义 o 当一个数据被分散地存放在一个文件的不同记录或多个文件中，可采用事务来保证该数据的一致性o 事务是用于访问和修改各种数据项的一个程序单位。o 只有对分布在不同位置的同一个数据所进行的读和写（含修改）操作全部完成时，才执行托付操作。o 只要有一读、写或修改操作失败，便执行夭折操作，须将事务内刚被修改的数据项恢复成原来的情况。o 事务具有原子性：事务的操作要么全部完成，要么一个也不做。402021-11-21阜阳师范学院计算机与信息学院2、 事

18、务记录o 事务操作的原子性须借助于存放在稳定存储器中的事务记录表来实现o 记录事务运行时所有对数据项的修改信息又称运行日志（Log）。o 该记录包括：事务名（事务的唯一标识）、数据项名（被修改的数据项标识）、旧值、新值p 当一个事务提交时，将一个提交记录也写入事务记录表中。412021-11-21阜阳师范学院计算机与信息学院3、 恢复算法o 当系统发生故障后，利用事务记录进行故障恢复。o 搜索整个事务记录表：o 对于已经提交了的事务，若在事务记录表中既包括，又包括记录，则执行redo 操作，设置为新值o 对于未提交事务，只有，而无记录，执行undo 操作422021-11-21阜阳师范学院计算机与信息学院8.5.2 检查点1、检查点 （Check points）的作用n系统每隔一段时间便写一条检查点记录到事务记录表，并进行恢复工作，即：对已经提交的事务执行redo，未提交的事务执行undo。 n这样在检查点这个时刻，系统中数据的一致性和完整性肯定能得到保证。2、新的恢复算法n 在引入检查点后，当发生故障后，只需对最后一个检查点以后开始的事务执行恢复工作。432021-11-21阜阳师范学院计算机与信息学院8.5.3 并发控制o 在多进程或多用户系统中，可能有多个事务在并发执行，由于事务具有原子性，使得这些事务对数据的