第八章 磁盘存储器的管理

本章要点（1/5） 目标：掌握文件存储的基本概念和实现过程 连续分配、链接分配和索引分配 连续分配：连续分配是何种为文件分配存储块的方式？ 如何对连续分配的文件进行顺序访问或随机访问？这种 分配方式有何优缺点？ 链接分配：链接分配是何种为文件分配存储块的方式？ 隐式链接分配方式是为了解决什么问题而引入的，它有 何不足之处？显式链表结构是如何解决上述不足的，它 较适合用哪种场合？这两种分配方式是如何将多个离散 的盘块链成一个链表的。 索引分配：索引分配是何种为文件分配存储块的方式？ 为什么要引入索引分配方式，采用索引分配方式时应如 何对文件进行访问？当文件很大时又应如何处理？混合 索引分配方式是为了解决什么问题而引入的？此时，应 如何将文件的逻辑地址转换成物理地址？

本章要点（2/5） 位示图法和成组链接法 位示图法：位示图法的概念。使用位示图如何来 进行磁盘块的分配或回收，这种管理方式有何优 点？ 成组链接法：成组链接法的概念。它是如何将盘 块进行分组并将各个盘块组链成一个成组链的？ 它应如何进行盘块的分配和回收，这种管理方式 有什么优点？

本章要点（3/5） 磁盘容错技术 SFT-I：引入SFT-I的目的是什么？双份目录和双 份文件分配表措施主要是用来解决什么问题？热 修复重定向和写后读校验措施又是用来解决什么 问题，它们分别是如何解决上述问题？ SFT-II：引入SFT-II的目的是什么？磁盘镜像可 用来解决什么问题？它对磁盘I/O的速度有什么 影响？而磁盘双工是为了解决什么问题而引入的 ，它对磁盘I/O的速度又有哪些影响？

本章要点（4/5） 文件系统的数据一致性 事务：事务的概念。事务是如何保证数据的一致 性的？事务操作和原语操作之间存在着什么区别 ？在事物操作中引入检查点主要是为了解决什么 问题？为什么多个事务的执行具有顺序性？如何 实现事务的顺序性？ 盘块号的一致性检查：盘块一致性检查的目的是 什么？盘块号一致性检查软件应如何设置每个盘 块的空闲盘块号计数器和数据盘块号计数器的值 ，为什么这两个计数器的值必须互补？在检查过 程中可能出现哪些异常现象，分别应如何解决？

本章要点（5/5） 文件系统的数据一致性 链接计数的一致性检查：为什么要引入链接计数 的一致性检查？一致性检查软件是通过什么和文 件索引结点中的链接计数字段的比较来进行一致 性检查的？在检查过程中可能会出现哪些异常现 象，分别应如何解决？

本章内容 8.1 外存的组织方式 8.2 文件存储空间的管理 8.3 提高磁盘I/O速度的途径 8.4 提高磁盘可靠性的技术 8.5 数据一致性控制

8 磁盘存储器的管理 对磁盘存储器管理的主要任务和要求是： 有效地利用存储空间； 提高磁盘的I/O速度； 提高磁盘系统的可靠性。 8 磁盘存储器的管理 对磁盘存储器管理的主要任务和要求是： 有效地利用存储空间； 采用合理的文件分配方式 提高磁盘的I/O速度； 采用磁盘调整缓存等 提高磁盘系统的可靠性。 冗余措施 后备系统

8.1 外存的组织方式 9

8.1 外存的组织方式 常用的外存组织方式有： 连续组织方式 链接组织方式 索引组织方式 需要连续的磁盘空间 文件物理结构是顺序式的文件结构 8.1 外存的组织方式 常用的外存组织方式有： 连续组织方式 需要连续的磁盘空间 文件物理结构是顺序式的文件结构 链接组织方式 可以为文件分配不连续的磁盘空间，用链接指针链接 文件物理结构是链接式文件结构 索引组织方式 可以为文件分配不连续的磁盘空间，采用索引组织方式 文件物理结构是索引式文件结构

8.1.1 连续组织方式 连续分配方式（磁带，磁盘都可采用） 每个文件分配一组相邻盘块，通常位于一条磁道上。 文件结构：顺序文件结构 8.1.1 连续组织方式 连续分配方式（磁带，磁盘都可采用） 每个文件分配一组相邻盘块，通常位于一条磁道上。 文件结构：顺序文件结构 物理文件：顺序文件 文件对应目录项（属性）中包含： 始址、总块数、最后一块字节数。 优点： 顺序访问容易；访问速度快 缺点： 要求连续空间，一段时间后需利用紧凑消除磁盘碎片 必须事先知道文件长度，文件不易动态增长； 为保持有序性，文件不能灵活地删除和插入记录。

连续分配方式 图 8-1 磁盘空间的连续组织方式

连续分配方式 图 8-1 磁盘空间的连续组织方式 （紧凑之后）

8.1.2 链接组织方式 链接组织方式 优点： 缺点： 将一个文件放在不连续的物理块中，每个物理块通过指针链接起来。 8.1.2 链接组织方式 链接组织方式 将一个文件放在不连续的物理块中，每个物理块通过指针链接起来。 优点： 消除了外部碎片，提高了外存利用率； 方便对文件进行插入、删除和修改记录操作。 无须事先知道文件长度，根据文件当前需要分配必须的盘块；动态增长时可再分配盘块； 缺点： 不能支持高效地直接存取

1、隐式链接 链接方式又可分为以下两种： 文件目录的每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针。 特点 ： 隐式链接 显式链接 文件目录的每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针。 特点 ： 只适合顺序访问，对随机访问效率极低； 只通过链接指针来将一大批离散的盘块链接起来，可靠性较差。 1、隐式链接

1、隐式链接 图 8-2 磁盘空间的链接式分配 1 2 3 4 块号 下一页 下一页的指针 （块号） 9 1 16 2 3 10 4 25 无 -1 页 1 2 3 4 图 8-2 磁盘空间的链接式分配

2、显式链接 把用于链接的指针显式存放在内存的一张表(FAT)中，查找在内存中进行。 利用文件分配表FAT，记录文件的盘块号。 图 8-3 显式链接结构

8.1.3 FAT技术 微软公司早、中期推出的操作系统都是采用FAT技术 FAT MSDOS：FAT12、FAT16 Windows95、Windows98：FAT32 Windows NT/2000/XP：NTFS FAT 引入了卷； 支持将一个物理磁盘分成四个逻辑磁盘，每个逻辑磁盘就是一个卷（也称分区）； 一个卷中包含了文件信息、一组文件以及空闲空间； 每个卷专门有一个单独的区存放目录、FAT表和逻辑驱动器字母。

1、FAT12 早期的FAT12文件系统 以盘块为基本分配单位 每个分区都配有两张相同的文件分配表FAT1和FAT2 文件的第一个盘块号放在文件的FCB中 每个FAT表项为12位，最多允许有4096个表项，假定每个盘块为512B，每个磁盘分区的容量为2MB，一个物理磁盘最大的容量为8MB 图 8-4 MS-DOS的文件物理结构

1、FAT12 以簇为单位的FAT12文件系统 簇(cluster)是一组相邻的扇区，为一个虚拟扇区； 以簇作为盘块分配的基本单位； 簇的大小一般是2n个盘块 MS-DOS中簇的容量：1、2、4、8个扇区 优点： FAT表占用的存储空间减少； 减少访问FAT表的存取开销。 缺点： 簇内碎片增大； 磁盘容量受限，通常只能为数十MB 只支持短文件名（8+3）。 答案为：最大分区空间为212*8* 512B=16MB；物理磁盘最大容量为64MB 如果簇的容量为8个扇区，则一个物理磁盘最大的容量为?

2、FAT16 3、FAT32 每个FAT表项为16位，最多允许有65536(64K)个表项 簇的容量：4、8、…、64个扇区 可以管理的最大分区空间：64KB*64*512B=2GB 3、FAT32 每个FAT表项为32位，每一簇在表项中占4字节 簇的容量：4KB~32KB（即8~64个扇区） 可以管理的最大分区空间：232-4*4KB=1TB（设簇的容量为4KB） 缺点： 文件分配表的扩大，使得运行速度慢于FAT32； FAT32有最小管理空间的限制(4KB)，不支持容量小于512MB的分区； 单个文件的长度不能大于4GB； 不能保持向下兼容。

图 8-5 FAT中簇的大小与最大分区的对应关系 扇区容量 扇区数 （盘块数） FAT12 FAT16 FAT32 0.5KB 1 2MB 1KB 2 4MB 2KB 4 8MB 128MB 4KB 8 16MB 256MB 1TB 8KB 16 512MB 2TB 16KB 32 1024MB（1GB） 32KB 64 2048MB（2GB） 图 8-5 FAT中簇的大小与最大分区的对应关系

8.1.4 NTFS的文件组织方式 1、NTFS新特征 使用64位磁盘地址； 支持长文件名： 具有系统容错功能； 能保证系统中数据一致性； 单个文件名255个字符以内； 全路径名为32767个字符。 具有系统容错功能； 能保证系统中数据一致性； 提供了对文件加密、压缩等功能。

2、磁盘组织 以簇作为磁盘空间分配和回收的基本单位 簇的定位采用逻辑簇号(LCN)或虚拟簇号(VCN) 卷上簇的大小也称为“卷因子”，由格式化命令指定； 簇的大小可以为：512B、1KB、…、64KB； ≤512MB的小磁盘，默认簇大小为512字节； 1GB的磁盘，默认簇大小为1KB 2GB的磁盘，默认簇大小为4KB 簇的定位采用逻辑簇号(LCN)或虚拟簇号(VCN) LCN以卷为单位，整个卷中所有的簇按顺序编号 VCN以文件为单位，属于某个文件的簇按顺序编号

3、文件组织 以卷为单位，卷中所有文件信息、目录信息及可用的未分配空间信息，均以记录的形式存储在MFT中。 主控文件表(MFT) 每个文件一条记录； MFT本身占有一条记录； 每条记录固定为1KB； 每条记录称为一个文件的元数据，也称文件控制字； 每个元数据都将其对应文件的所有信息（包括文件的内容等）组织在所对应文件的一组属性中： 文件小，属性直接记录在元数据中； 文件大，元数据中只记录文件的一部分属性，其余的保存在其他簇中，将链接指针存在元数据中。

8.1.5 索引组织方式 1、单级索引组织方式 链接组织方式存在的问题： 解决方案：为每个文件分配一个索引块，记录文件的所有盘块号。 特点： 8.1.5 索引组织方式 1、单级索引组织方式 链接组织方式存在的问题： 不能高效直接存取； FAT需占较大的内存。 解决方案：为每个文件分配一个索引块，记录文件的所有盘块号。 特点： 支持直接访问：文件较大时有利；文件较小时浪费外存空间（还需为小文件建索引块）

1、单级索引组织方式 图 8-6 索引分配方式

2、多级索引组织方式 单级索引组织方式存在的问题：当文件较大时，索 引块太多，查找速度减慢 解决方案：当索引太大时，则需建立多级索引 设一个盘块大小为1KB，每个盘块号占4byte。则2级索引存 放的文件的盘块号总数为：256×256=64K，故文件的最大 长度为64K× 1KB =64MB 设一个盘块大小为4KB，每个盘块号占4byte。则2级索引存 放的文件的盘块号总数为：1KB×1KB=1MB，故文件的最 大长度为1M × 4KB =4GB

2、多级索引组织方式 图 8-7 两级索引分配

3、增量式索引组织方式 增量式索引组织式的基本思想 增量式索引组织方式： 直接寻址：对于小文件（最多占10个盘块），将文件的 每一个盘块地址都直接放到FCB（或索引结点）中； 一次间址：对中等文件，采用单级索引组织方式，FCB 中存放的是文件的索引表； 二次/三次间址：对大型和特大型文件，采用两级和三级 索引组织方式。 增量式索引组织方式： 又称为混合组织方式，既采用了直接寻址方式，又采用 了单级和多级索引组织方式（间接寻址）。 UNIX系统中采用了这种组织方式。

3、增量式索引组织方式 UNIX System V的组织方式 索引结点设有13个地址项， iaddr(0)~iaddr(12)； 设每个盘块大小为4KB，一索引项占4字节； 直接地址：用iaddr(0)~iaddr(9)来存放直接地址，称为直 接盘块号，小文件（<40K)可直接从索引结点读出文件 的全部盘块。 一次间接地址：利用索引结点中的地址项iaddr(10)来提 供一次间址，一次间址块可存放1K个盘块号，允许文件 长达4 MB。 多次间接地址：当文件长度大于4 MB+40 KB时，用地址 项iaddr(11)提供二次间址，文件最大长度可达4 GB。地 址项iaddr(12)作为三次间接地址，其所允许的文件最大 长度可达4 TB。

图 8-8 混合索引方式

8.2 文件存储空间的管理 33

8.2 文件存储空间的管理 为文件分配磁盘时，需要的数据结构包括： 磁盘空间的基本分配单位： 文件存储空间的管理方法： 文件分配表（FAT） 8.2 文件存储空间的管理 为文件分配磁盘时，需要的数据结构包括： 文件分配表（FAT） 磁盘分配表（DAT） 磁盘空间的基本分配单位： 磁盘块 文件存储空间的管理方法： 空闲表法和空闲链表法 位示图法 成组链接法

8.2.1 空闲表法和空闲链表法 1、空闲表法（属于连续分配方式） 分配：首次/循环首次/最佳/最坏 回收：判断是否合并。 由于连续分配比较快，因此对对换空间及小文件的 管理适用。 序号 第一空闲盘块号 空闲盘块数 1 2 4 9 3 15 5 — 图 8-9 空闲盘块表

2、空闲链表法 空闲盘块链 空闲盘区链 将磁盘上的所有空闲空间以盘块为单位串成一条链，每一 个盘块都有指向后继盘块的指针。 优点：用于分配和回收一个盘块的过程非常简单 缺点：可能该链很长，在为一个文件分配盘块时，可能要 重复操作多次，分配和回收效率很低。 空闲盘区链 将磁盘上的所有空闲盘区串成一条链，每个盘区含有：用 于指示下一个空闲盘区的指针、指明本盘区大小的信息 一个盘区含多个盘块，类似于内存分区分配与回收(合并) 分配通常采用首次适应算法，为了提高对空闲盘区的检索 速度，可采用显式链接方法。

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

2、盘块的分配： 3、盘块的回收： 特点：易于访问；占空间少，可放入内存，查找速 度快。 顺序扫描，找一个或一组=0的块； 根据找到的行/列得以盘块号。b=n(i-1)+j；( n代表每行 的位数) 修改位图，令map[i, j]=1。 3、盘块的回收： 由磁块号得(i,j) i= (b-1) div (n +1) j= (b-1) mod (n +1) 修改位图：令map[i, j]=0 特点：易于访问；占空间少，可放入内存，查找速 度快。

8.2.3 成组链接法 空闲表法和空闲链表法都不适用于大型文件系统。 UNIX系统中采用的是成组链接法，将上述两种方法相结合形成一种空闲盘块管理方法。 s-nfree :空闲块数 s_free[100]：空闲块块号 s_flock：锁位

1、空闲盘块的组织 空闲盘块号栈 文件区中的所有空闲盘块，被分成若干个组 将每一组含有的盘块总数N和该组所有的盘块号，记入其前一组的第一个盘块的S.free(0)~S.free(99)中。 将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。 最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)~S.free(99)中。

1、空闲盘块的组织 图 8-11 空闲盘块的成组链接法

2、空闲盘块的分配与回收 1）分配 首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出 一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶 指针下移一格。 若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个 可分配的盘块号。由于在该盘块号所对应的盘块中记有下一 组可用的盘块号，因此，须调用磁盘读过程，将栈底盘块号 所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并 把原栈底对应的盘块分配出去。 然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后 ，把栈中的空闲盘块数减1并返回。

2、空闲盘块的分配与回收 2）回收 将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲 盘块数加1操作。 当栈中空闲盘块号数目已达100时， 表示栈已满，便将现有 栈中的100个盘块号， 记入新回收的盘块中，再将其盘块号 作为新栈底。

8.3 提高磁盘I/O速度的途径 44

8.3 提高磁盘I/O速度的途径 提高对文件的访问速度，有三种途径： 改进文件的目录结构以及检索目录的方法，以减少对目录的查找时间； 选取好的文件存储结构，以提高对文件的访问速度； 提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中。 最主要的技术是采用磁盘高速缓存。

8.3.1 磁盘高速缓存(Disk Cache) 磁盘高速缓存 设计磁盘高速缓存时需要考虑的问题： 是指在内存中为磁盘盘块设置的一个缓冲区，在缓冲区中保存了某些盘块的副本； 逻辑上是磁盘、物理上是驻留在内存中的盘块； 固定大小和可变大小。 设计磁盘高速缓存时需要考虑的问题： 如何将磁盘高速缓存中的数据传送给请求进程； 采用什么样的置换策略； 已修改的盘块数据在何时被写回磁盘。

1、数据交付方式 2、置换算法 数据交付：指将磁盘高速缓存中的数据传送给请求者进程 数据交付方式： 常用算法： 数据交付：直接将高速缓存中的数据传送到请求者进程的内存工作区中。 指针交付：只将指向高速缓存中某区域的指针交付给请求者进程。 常用算法： 最近最久未使用算法LRU 最近未使用算法NRU 最少使用算法LFU 2、置换算法

2、置换算法 3、周期性地写回磁盘 置换时需考虑的因素： 置换的策略： 访问频率； 可预见性； 数据的一致性。 置换的策略： 对于会严重影响到数据一致性的盘块数据和很久都可能不再使用的盘块数据，都放在LRU链的头部，使它们优先写回磁盘。 经常被访问的盘块一直保留在调整缓存中，会移至LRU的链尾；一直未被访问的元素有可能移到链首，会被写回磁盘。在UNIX中用系统调用SYNC实现 3、周期性地写回磁盘

8.3.2 提高磁盘I/O速度的其它方法 提前读 延迟写 优化物理块的分布 虚拟盘 访问频率高的磁盘块放在替换队列的尾部，减少回写次数 目的是减小磁头移动距离 簇分配方式：一个簇为多个连续的块 虚拟盘 虚拟盘：利用内存空间仿真磁盘，又称为RAM盘 虚拟盘可以接受所有标准的磁盘操作，常用于存放临时文件 和磁盘高速缓存区别：虚拟盘由用户控制；磁盘高速缓存由系统控制。

8.3.3 廉价磁盘冗余阵列 廉价磁盘冗余阵列RAID（Redundant Arrays of Inexpensive Disk）：是利用一台磁盘阵列控制器，来统一管理和控制一组（几台到几十台）磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统 1、并行交叉存取 图 8-12 磁盘并行交叉存取方式

2、RAID的分级 通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能。 通过把数据分成多个数据块，并行写入/读出多个磁盘，以提高访问磁盘的速度。 通过镜像或校验操作，提供容错能力。 RAID0 仅提供并行交叉存取。具有并行读写功能，提高了磁盘的I/O速度，但无冗余校验功能。 RAID1 提供磁盘镜像功能。具有并行读写功能，提高了磁盘的I/O速度，但磁盘的利用率仅50%。 RAID3 具有并行传输功能的磁盘阵列。用一台奇偶校验盘容错。 RAID5 具有独立传输功能的磁盘阵列。每个驱动区有自己独立的数据通道。无专门的校验盘，校验信息以螺旋方式分布在每个盘上。 RAID6 RAID7 RAID6设有一个专用的、快速访问的异步校验盘。 RAID7是对RAID6的改进。所有盘都有较高的传输率及优异的性能

提供并行交叉存取； 能有效提高磁盘I/O速度； 无冗余校验功能，磁盘系统的可靠性差。

RAID0中逻辑磁盘与物理磁盘间的映射关系

具有镜像功能； 具有并行读写功能，提高了磁盘的I/O速度，但磁盘的利用率仅50%。

采用了早期的错误检测与修正技术----汉明码（Hamming Code ）校验技术进行即时数据校验，冗错性较好； 一个硬盘在一个时间只存取一位的信息，但具有极高的数据传输率； RAID 2 中的硬盘数量取决于所设定的数据存储宽度； 系统成本极高，对冗余的数据传输率要求较高。 注：汉明码的数量与数据位的数量之间比例公式为，2P≥P+D+1，P 代表汉明码的个数，D 代表数据位的个数

具有并行传输功能的磁盘阵列； 用一台奇偶校验盘容错； 磁盘利用率为（N-1）/N； 常用于科学计算和图像处理。

独立的数据硬盘与共享的校验硬盘； 按数据块为单位进行存储； 在不同硬盘上的同级数据块也都通过XOR 进行校验，结果保存在单独的校验盘； 相对较高的读取传输率，极差的写入传输率（在写入时要等一个硬盘写完后才能写一下个，并且还要写入校验数据）。

具有独立传输功能的磁盘阵列； 每个驱动区有自己独立的数据通道； 无专门的校验盘，校验信息以螺旋方式分布在每个盘上； 常用于I/O较频繁的事务处理。

设置了一个专用的、可快速访问的异步校验盘； 具有独立的数据访问通道； 具有比RAID 3级及RAID 5级更好的性能，但性能改进很有限； 价格昂贵。

3、RAID的优点 可靠性高。 (2) 磁盘I/O速度高。 (3) 性能/价格比高。

8.4 提高磁盘可靠性的技术 61

8.4 提高磁盘可靠性的技术 确保文件系统安全性措施： 容错技术：通过在系统中设置冗余部件的办法， 提高系统可靠性的一种技术。 8.4 提高磁盘可靠性的技术 确保文件系统安全性措施： 存取控制机制：防止人为因素 系统容错技术：防止系统因素 后备系统：防止自然因素 容错技术：通过在系统中设置冗余部件的办法， 提高系统可靠性的一种技术。 磁盘容错技术：通过增加冗余的磁盘驱动器、磁 盘控制器等，来提高磁盘系统的可靠性的一种技 术。 磁盘容错技术分为三级： SFT-I是低级磁盘容错技术 SFT-II是中级磁盘容错技术 SFT-III是系统高级容错技术

8.4.1 第一级容错技术SFT-I 1、双份目录和双份文件分配表 2、热修复重定向和写后读校验 热修复重定向：系统将磁盘容量的很小一部分（2%~3%） 作为热修复重定向，用于存放当发现磁盘有缺陷时的待写 数据。 写后读校验方式。

8.4.2 第二级容错技术SFT-II 1、磁盘镜像(Disk Mirroring) 图 8-13 磁盘镜像示意

2、磁盘双工(Disk Duplexing) 图 8-14 磁盘双工示意

8.4.4 基于集群技术的容错功能 集群：是一组相互独立的、通过高速网络互联的计算 机，它们构成统一的计算机系统，并以单一系统的模 式加以管理。一个客户与集群相互作用时，集群像是 一个独立的服务器。 集群系统的工作模式有： 热备份模式 互为备份模式 公用磁盘模式

1、双机热备份模式 两台完全相同的服务器，一主一从，各装入一块网卡，通过 一条镜像服务器链路MSL连接。平时主服务器运行，备份服 务器监视。主服务器出现故障，备份服务器自动切换成主服 务器。 如果采用FDDI单模光纤，两台服务器间的距离可达20公里。 系统中必须设置某种机制检测主服务器中数据的改变。 优点：提高了可用性，易于实现，支持远程热备。 缺点：系统使用效率只有50%。 图 8-15 双机热备份模式

2、双机互为备份模式 两台服务器均为在线服务器，各自完成自己的任务，它们之 间通过某种专线连接； 服务器上的两台硬盘，一个用于装载系统程序和应用程序， 另一个用于接收另一台服务器发来的备份数据。 优点：两台服务器都可处理任务，系统效率高。 图 8-16 双机热备份模式

3、公用磁盘模式 将多台计算机连接到一台公共的磁盘系统上，每台计算机使 用磁盘的一个卷。 某台计算机发生故障，系统将重新进行配置，根据某种策略 选择另一台替代机器，替代机器对发生故障的机器的卷拥有 所有权，可接替故障计算机所承担的任务。 优点：消除了信息复制的时间，减少了网络和服务器的开销

8.4.5 后备系统 配备后备系统的原因： 后备系统的常用设备： 磁盘系统不够大，无法容纳系统运行过程中所有的数据； 8.4.5 后备系统 配备后备系统的原因： 磁盘系统不够大，无法容纳系统运行过程中所有的数据； 措施：把暂时不需要但仍然有用的数据存放在后备系统中。 防止系统发生故障或病毒。 措施：将比较重要的数据存放在后备系统中。 后备系统的常用设备： 磁带机 硬盘 光盘驱动器

8.5 数据一致性控制 71

8.5.1 事务 1. 事务的定义 事务是用于访问和修改各种数据项的一个程序单位。 事务也可以被看作是一系列相关读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，也可放在多个文件中。 只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以托付操作(Commit Operation)来终止事务。 只要有一个读、写或修改操作失败，便须执行夭折操作(Abort Operation)。 读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导致的。 事务操作具有“原子性”。

2、事务记录(Transaction Record) 事务记录存储在稳定存储器中，用来记录在事务运 行时数据项修改的全部信息，又称为运行记录（ log）。 记录包含下列字段： 事务名： 用于标识该事务的惟一名字； 数据项名： 它是被修改数据项的惟一名字； 旧值： 修改前数据项的值； 新值： 修改后数据项将具有的值。 事务记录表中的每一记录，描述了在事务运行中的 重要事务操作：修改操作、开始事务、托付事务、 夭折事务等

3、恢复算法 恢复算法可利用以下两个过程： (1) undo〈Ti〉。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。 (2) redo〈Ti〉。该过程能把所有被事务Ti修改过的数据，设置为新值。 如果系统发生故障， 系统应对以前所发生的事务进行清理。

8.5.2 检查点 1、检查点(Check Points)的作用 引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化。 8.5.2 检查点 1、检查点(Check Points)的作用 引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化。 事务记录清理工作的步骤： 首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中； 将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中； 将事务记录表中的〈检查点〉记录，输出到稳定存储器中； 每当出现一个〈检查点〉记录时，系统便执行恢复操作，利用redo和undo过程实现恢复功能。

2、新的恢复算法 恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。 如果把所有在事务Ti以后开始执行的事务表示为事务集T， 则新的恢复操作要求是：对所有在T中的事务TK, 如果在事务记录表中出现了〈TK托付〉记录，则执行redo〈TK〉操作； 反之，如果在事务记录表中并未出现〈TK托付〉记录，则执行undo〈TK〉操作。

8.5.3 并发控制 顺序性：事务具有原子性，多用户执行的各个事务 的执行必然按某种次序依次执行，只有一个事务执 行完后才允许执行另一个事务，即各事务对数据项 的修改是互斥的。这种特性称为顺序性（ Serializability）。 并发控制（Concurrent Control）：把用于实现事 务顺序性的技术称为~。

1、利用互斥锁实现“顺序性” 2、利用互斥锁和共享锁实现顺序性 应为每一个共享对象设置一把互斥锁（Exclusive Lock）。当一事务Ti要去访问某对象时，应先获得该对象的互斥锁。 特点：简单易行，但效率不高。 2、利用互斥锁和共享锁实现顺序性 互斥锁仅允许一个事务对相应对象执行读或写操作； 共享锁允许多个事务对相应对象执行读操作。

8.5.4 重复数据的数据一致性问题 1、重复文件的一致性 图 8-18 UNIX类型的目录 (a)不允许有重复文件的目录 (b)允许有重复文件的目录 图 8-18 UNIX类型的目录

2、盘块号一致性检查 两组计数器的值互补。 盘块2未被利用。将其连结到空闲块链中即可。 图 8-19 检查链接数一致性情况

盘块2被2次连结到空闲块链中，删除一个即可。 严重错误，向系统报告。 图 8-19 检查盘块号一致性情况

3、链接数一致性检查 为每个盘块建立一个表项，其中含有该索引结点号的计数值。 在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较，如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。

如果索引结点中的链接计数count值大于计数器表中相应索引结点号的计数值，则即使在所有共享此文件的用户都不再使用此文件时，其count值仍不为0，因而该文件不会被删除。这种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上，浪费了存储空间。解决的方法是用计数器表中的正确的计数值去为count重新赋值。 反之，如果出现count值小于计数器表中索引结点号计数值的情况时，就有潜在的危险。假如有两个用户共享一个文件，但是count值仍为1，这样，只要其中有一个用户不再需要此文件时， count值就会减为0，从而使系统将此文件删除，并释放其索引结点及文件所占用的盘块，导致另一共享此文件的用户所对应的目录项，指向了一个空索引结点，最终是使该用户再无法访问此文件。如果该索引结点很快又被分配给其它文件，则又会带来潜在的危险。解决的方法是将count值置为正确值。