第8章磁盘存储管理

12023/2/6阜阳师范学院计算机与信息学院8.1外存的组织方式8.2文件存储空间的管理8.3提高磁盘I/O速度的途径8.4提高磁盘可靠性的技术8.5数据一致性控制

主要任务和要求是：有效地利用存储空间提高磁盘的I/O速度提高磁盘系统的可靠性第8章磁盘存储器的管理22023/2/6阜阳师范学院计算机与信息学院文件的物理结构和外存分配方法有关连续分配方式顺序式结构链接分配方式链接式结构索引分配方式索引式结构

8.1.1连续分配8.1.2链接分配8.1.3索引分配8.1外存组织方式32023/2/6阜阳师范学院计算机与信息学院8.1.1连续分配优点：顺序访问容易，支持随机存取；存取速度很快缺点：分配连续的外存空间；事先知道文件的长度42023/2/6阜阳师范学院计算机与信息学院8.1.2链接分配属于离散分配方式采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的文件称为链接文件。链接方式又可分为隐式链接和显式链接两种形式。52023/2/6阜阳师范学院计算机与信息学院隐式链接缺点：可靠性较差；不适合随机访问62023/2/6阜阳师范学院计算机与信息学院显式链接72023/2/6阜阳师范学院计算机与信息学院链式分配的优缺点离散分配方式消除了外部碎片提高了外存空间利用率便于文件动态增长方便文件的增、删、改不能支持高效的直接存取FAT需占用较大的内存空间优点：缺点：82023/2/6阜阳师范学院计算机与信息学院单级索引方式8.1.5索引组织方式每个文件一个索引块不利于小文件（常采用链式）92023/2/6阜阳师范学院计算机与信息学院outer-index外部索引indextable索引表File文件多级索引方式102023/2/6阜阳师范学院计算机与信息学院混合索引方式直接地址一次间接地址多次间接地址112023/2/6阜阳师范学院计算机与信息学院122023/2/6阜阳师范学院计算机与信息学院例题1设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件的最大长度是：（）1057KB132023/2/6阜阳师范学院计算机与信息学院例题2若某文件系统索引结点（inode）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（）索引结点的总数间接地址索引的级数地址项的个数文件块大小A142023/2/6阜阳师范学院计算机与信息学院例题3下列文件物理结构中，适合随机访问且易于文件扩展的是：连续结构索引结构链式结构顺序结构B152023/2/6阜阳师范学院计算机与信息学院8.2文件存储空间的管理8.2.1空闲表法和空闲链表法8.2.2位示图法8.2.3成组链接法162023/2/6阜阳师范学院计算机与信息学院8.2.1空闲表法和空闲链表法序号第一空闲盘块号空闲盘块数12429331554——172023/2/6阜阳师范学院计算机与信息学院存储空间的分配与回收与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等内存管理中虽然很少采用连续分配方式，然而在外存的管理中，由于它具有较高的分配速度，可减少访问磁盘的I/O频率，故它在诸多分配方式中仍占有一席之地182023/2/6阜阳师范学院计算机与信息学院空闲链表法空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：（1）空闲盘块链（2）空闲盘区链192023/2/6阜阳师范学院计算机与信息学院110101000001100011011100001101010011123456789101112123………128.2.2

位示图法——位示图位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。0表示盘块空闲，1表示已分配。

磁盘上所有盘块所对应的位构成一个集合，称为位示图。通常可用m*n个位数来构成位示图，并使m*n等于磁盘的总块数。如图,可看成是二维数组map(m,n)。202023/2/6阜阳师范学院计算机与信息学院盘块的分配和回收顺序扫描位示图，找到0二进制位。将所找到的一个或一组二进制位，转换成与之对应的盘块号。盘块号=列数*（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列数+1j=(盘块号-1)mod列数+1（i,j,b（盘块号）都从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回收过程：212023/2/6阜阳师范学院计算机与信息学院例题4假定一个盘组共有100个盘面,每个盘面上有16个磁道,每个磁道分成4个扇区,问:(1)整个磁盘空间共有多少个存储块？(2)如果用字长32位的单元来构造位示图,共需多少个字？(3)位示图中第18个字的第16位对应的块号是多少？

分析：(1)4*16*100=6400(2)6400/32=200(3)(18-1)*32+16=560222023/2/6阜阳师范学院计算机与信息学院8.2.3成组链接法空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。在UNIX系统中采用的是成组链接法是将上述两种方法结合而形成的一种空闲盘块管理方法，它兼备了上述方法的优点而克服了表太长的缺点。232023/2/6阜阳师范学院计算机与信息学院空闲盘块的成组链接法示意图S.free(0)是栈底栈满时栈顶为S.free(99)242023/2/6阜阳师范学院计算机与信息学院空闲盘块的组织空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号（最多含100个号），以及栈中尚有的空闲盘块号数NN还兼作栈顶指针例如：当N=100时，它指向S.free(99)，S.free(0)是栈底，栈满时栈顶为S.free(99)。252023/2/6阜阳师范学院计算机与信息学院空闲盘块的组织文件中的所有空闲盘块，被分成若干个组。将每一组含有的盘块总数N和该组的盘块号，记入其前一组的第一个盘块的S.free(0)~S.free(99)中。这样由各组的第一个盘块形成了一条链。将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。最末一组只有99个盘块，在S.free(0)中则存放0，作为空闲盘块链的结束标志。8.3提高磁盘I/O速度的途径磁盘高速缓存(DiskCache)提高磁盘I/O速度的其它方法廉价磁盘冗余阵列(RAID)262023/2/6阜阳师范学院计算机与信息学院272023/2/6阜阳师范学院计算机与信息学院

指利用内存中的存储空间，来暂存从磁盘中读出的一系列盘块中的信息。因此，它是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。8.3.1磁盘高速缓存(DiskCache)1.磁盘高速缓存的形式

指将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式，将数据交付给请求进程：

(1)数据交付(2)指针交付2.数据交付方式282023/2/6阜阳师范学院计算机与信息学院

磁盘缓存的调度算法很类似存储调度算法，但由于磁盘的区别，通常比虚拟存储复杂。除了考虑到最近最久未使用这一原则外，还考虑了以下几点：访问频率、可预见性、数据的一致性。3.置换算法4.周期性地写回磁盘8.3.1磁盘高速缓存(DiskCache)292023/2/6阜阳师范学院计算机与信息学院1.提前读(Read-Ahead)2.延迟写3.优化物理块的分布4.虚拟盘8.3.2提高磁盘I/O速度的其它方法302023/2/6阜阳师范学院计算机与信息学院8.3.3廉价磁盘冗余阵列(RAID)1.并行交叉存取是利用一台磁盘阵列控制器，来统一管理和控制一组磁盘驱动器，从而组成一个高度可靠的快速的大容量磁盘系统。OS将RAID中一组物理磁盘驱动器看作是一个单个的逻辑磁盘驱动器，用户和系统数据可分布在阵列的所有磁盘中，并可采取并行传输方式。2.RAID的分级RAID的另一特点是高可靠性，可分成RAID0－RAID7几级，除了RAID0外，其它各级都采用了容错技术。312023/2/6阜阳师范学院计算机与信息学院影响文件安全性的主要因素及采取的措施：人为因素：——采取存取控制机制系统因素：——通过磁盘容错技术自然因素：——通过后备系统8.4提高磁盘可靠性的技术322023/2/6阜阳师范学院计算机与信息学院容错技术：通过在系统中设置冗余部件的办法，提高系统可靠性的一种技术。磁盘容错技术（系统容错技术SFT——SystemFaultTolerance）则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的一种技术。8.4提高磁盘可靠性的技术332023/2/6阜阳师范学院计算机与信息学院磁盘容错技术：

SFT-1：低级磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢失；

SFT-2：中级磁盘容错技术，主要用于防止磁盘驱动器和磁盘控制器故障引起的系统不能正常工作；

SFT-3：高级磁盘容错技术，它基于集群技术实现容错。8.4提高磁盘可靠性的技术342023/2/6阜阳师范学院计算机与信息学院第一级容错技术(SFT-1)常用的措施有：双份目录和双份文件分配表（FAT）在不同的磁盘上或磁盘的不同区域中，分别建立两份目录表和FAT热修复重定向和写后读校验热修复重定向写后读校验352023/2/6阜阳师范学院计算机与信息学院

第二级容错技术(SFT-2)磁盘镜像（DiskMirroring）磁盘双工（DiskDuplexing）362023/2/6阜阳师范学院计算机与信息学院主机磁盘控制器通道磁盘驱动器磁盘镜像（DiskMirroring）磁盘驱动器故障的容错在同一磁盘控制器控制下，增设一个完全相同的磁盘驱动器,如下图。每次将数据写主磁盘时，都需要采用写后检验方式，同时将数据也写入到备份磁盘。主磁盘驱动器发生故障时，则启动备份驱动器，并立即发出警告，尽快修复。不足之处：磁盘利用率为50%372023/2/6阜阳师范学院计算机与信息学院磁盘双工（DiskDuplexing）主机通道磁盘驱动器

磁盘控制器通道

磁盘控制器

磁盘控制器或控制器与CPU之间的通道故障的容错。将两台磁盘驱动器分别接到两个磁盘控制器上,如下图。两个磁盘上的数据完全相同。每个磁盘都有自己的独立通道382023/2/6阜阳师范学院计算机与信息学院8.5数据一致性控制

8.5.1事务8.5.2检查点8.5.3并发控制392023/2/6阜阳师范学院计算机与信息学院8.5.1事务1、事务（Transaction）的定义当一个数据被分散地存放在一个文件的不同记录或多个文件中，可采用事务来保证该数据的一致性事务是用于访问和修改各种数据项的一个程序单位。只有对分布在不同位置的同一个数据所进行的读和写（含修改）操作全部完成时，才执行托付操作。只要有一读、写或修改操作失败，便执行夭折操作，须将事务内刚被修改的数据项恢复成原来的情况。事务具有原子性：事务的操作要么全部完成，要么一个也不做。402023/2/6阜阳师范学院计算机与信息学院2、事务记录事务操作的原子性须借助于存放在稳定存储器中的事务记录表来实现记录事务运行时所有对数据项的修改信息——又称运行日志（Log）。该记录包括：事务名（事务的唯一标识）、数据项名（被修改的数据项标识）、旧值、新值当一个事务提交时，将一个提交记录<Ti托付>也写入事务记录表中。412023/2/6阜阳师范学院计算机与信息学院3、恢复算法当系统发生故障后，利用事务记录进行故障恢复。搜索整个事务记录表：对于已经提交了的事务，若在事务记录表中既包括<Ti开始>，又包括<Ti托付>记录，则执行redo<Ti>操作，设置为新值对于未提交事务，只有<Ti开始>，而无<Ti