======第六章文件管理======（3）https://developer.aliyun.com/article/1415866
6.5 文件存储空间的管理
6.5.1 空闲表法和空闲链表法
- 空闲表法
1) 空闲表 空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间，即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一 个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。 再将所有空闲区按其起始盘块号递增的次序排列，如图 6-21 所示。
2) 存储空间的分配与回收
空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算 法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项， 直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲 表。系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考 虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。
应该说明，在内存分配上，虽然很少采用连续分配方式，然而在外存的管理中，由于 这种分配方式具有较高的分配速度，可减少访问磁盘的 I/O 频率，故它在诸多分配方式中仍 占有一席之地。例如，在前面所介绍的对换方式中，对对换空间一般都采用连续分配方式。 对于文件系统，当文件较小(1～4 个盘块)时，仍采用连续分配方式，为文件分配相邻接的几 个盘块；当文件较大时，便采用离散分配方式。
空闲链表法
空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。
(1) 空闲盘块链。这是将磁盘上的所有空闲空间，以盘块为单位拉成一条链。当用户因 创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给 用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末 尾。这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘 块时，可能要重复操作多次。
(2) 空闲盘区链。这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条 链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块 数)的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收 盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提 高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张 链表。
6.5.2 位示图法
- 位示图
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为“0”时，表 示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志， 把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分 配两种情况。)磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的 位构成一个集合，称为位示图。通常可用 m × n 个位数来构成位示图，并使 m × n 等于磁盘 的总块数，如图 6-22 所示。
位示图也可描述为一个二维数组 map： Var map: array of bit；
盘块的分配 根据位示图进行盘块分配时，可分三步进行：
(1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。
(2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0” 的二进制位位于位示图的第 i 行、第 j 列，则其相应的盘块号应按下式计算：
b = n(i - 1) + j
式中，n 代表每行的位数。
(3) 修改位示图，令 map[i,j]=1。 3．盘块的回收 盘块的回收分两步：
(1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：
i = (b - 1)DIV n + 1
j = (b - 1)MOD n + 1
(2) 修改位示图。令 map[i,j] =0。
这种方法的主要优点是，从位示图中很容易找到一个或一组相邻接的空闲盘块。例如， 我们需要找到 6 个相邻接的空闲盘块，这只需在位示图中找出 6 个其值连续为“0”的位即 可。此外，由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行 盘区分配时，无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。因此， 位示图常用于微型机和小型机中，如 CP/M、Apple-DOS 等 OS 中。
6.5.3 成组链接法
空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。 在 UNIX 系统中采用的是成组链接法，这是将上述两种方法相结合而形成的一种空闲盘块 管理方法，它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。
1．空闲盘块的组织
(1) 空闲盘块号栈用来存放当前可用的一组空闲盘块的盘块号(最多含 100 个号)，以 及栈中尚有的空闲盘块号数 N。顺便指出，N 还兼作栈顶指针用。例如，当 N=100 时，它 指向 S.free(99)。由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一 把锁。图 6-23 左部示出了空闲盘块号栈的结构。其中，S.free(0)是栈底，栈满时的栈顶为 S.free(99)。
(2) 文件区中的所有空闲盘块被分成若干个组，比如，将每 100 个盘块作为一组。假定 盘上共有 10 000 个盘块，每块大小为 1 KB，其中第 201～7999 号盘块用于存放文件，即作 为文件区，这样，该区的最末一组盘块号应为 7901～7999；次末组为 7801～7900……；第 二组的盘块号为 301～400；第一组为 201～300，如图 6-23 右部所示。
(3) 将每一组含有的盘块总数 N 和该组所有的盘块号记入其前一组的第一个盘块的 S.free(0)～S.free(99)中。这样，由各组的第一个盘块可链成一条链。
(4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空 闲盘块号。
(5) 最末一组只有 99 个盘块，其盘块号分别记入其前一组的 S.free(1) ～S.free(99)中， 而在 S.free(0)中则存放“0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为 99， 不应是 100，因为这是指可供使用的空闲盘块，其编号应为(1～99)，0 号中放空闲盘块链的 结尾标志。)
空闲盘块的分配与回收
当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。该过程首先检 查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分 配给用户，然后将栈顶指针下移一格。若该盘块号已是栈底，即 S.free(0)，这是当前栈中最 后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此， 须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容， 并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲 区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减 1 并返回。
在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入 空闲盘块号栈的顶部，并执行空闲盘块数加 1 操作。当栈中空闲盘块号数目已达 100 时，表 示栈已满，便将现有栈中的 100 个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。
6.6 文件共享与文件保护
6.6.1基于索引结点的共享方式
在树型结构的目录中，当有两个(或多个)用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个(或多个)用户的目录中，才能方便地找到该文件，如图 6-24 所示。 此时该文件系统的目录结构已不再是树型结构，而是个有向非循环图 DAG(Directed Acyclic Graph)。
如何建立B目录与共享文件之间的链接呢？如果在文件目录中包含了文件的物理地址， 即文件所在盘块的盘块号，则在链接时，必须将文件的物理地址拷贝到 B 目录中去。但如 果以后 B 或 C 还要继续向该文件中添加新内容，也必然要相应地再增加新的盘块，这须由 附加操作 Append 来完成。而这些新增加的盘块，也只会出现在执行了操作的目录中。可见， 这种变化对其他用户而言是不可见的，因而新增加的这部分内容已不能被共享。
为了解决这个问题，可以引用索引结点，即诸如文件的物理地址及其它的文件属性等 信息，不再是放在目录项中，而是放在索引结点中。`在文件目录中只设置文件名及指向相 应索引结点的指针，如图 6-25 所示。此时，由任何用户对文件进行 Append 操作或修改， 所引起的相应结点内容的改变(例如，增加了新的盘块号和文件长度等)，都是其他用户可见 的，从而也就能提供给其他用户来共享。
在索引结点中还应有一个链接计数 count，用于表示链接到本索引结点(亦即文件)上的 用户目录项的数目。当 count=3 时，表示有三个用户目录项连接到本文件上，或者说是有三 个用户共享此文件。
当用户 C 创建一个新文件时，他便是该文件的所有者，此时将 count 置 1。当有用户 B 要共享此文件时，在用户 B 的目录中增加一目录项，并设置一指针指向该文件的索引结点， 此时，文件主仍然是 C，count=2。如果用户 C 不再需要此文件，是否能将此文件删除呢？ 回答是否定的。因为，若删除了该文件，也必然删除了该文件的索引结点，这样便会使 B 的指针悬空，而 B 则可能正在此文件上执行写操作，此时将因此半途而废。但如果 C 不删 除此文件而等待 B 继续使用，这样，由于文件主是 C，如果系统要记账收费，则 C 必须为 B 使用此共享文件而付账，直至 B 不再需要。图 6-26 示出了 B 链接到文件上的前、后 情况。
6.6.2 利用符号链实现文件共享
为使 B 能共享 C 的一个文件 F，可以由系统创建一个 LINK 类型的新文件，也取名为 F， 并将 F 写入 B 的目录中，以实现 B 的目录与文件 F 的链接。在新文件中只包含被链接文件 F 的路径名。这样的链接方法被称为符号链接(Symbolic Linking)。新文件中的路径名则只被 看作是符号链(Symbolic Link)，当 B 要访问被链接的文件 F 且正要读 LINK 类新文件时，此 要求将被 OS 截获，OS 根据新文件中的路径名去读该文件，于是就实现了用户 B 对文件 F 的共享。
在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的指针；而共 享该文件的其他用户则只有该文件的路径名，并不拥有指向其索引结点的指针。这样，也 就不会发生在文件主删除一共享文件后留下一悬空指针的情况。当文件的拥有者把一个共 享文件删除后，其他用户试图通过符号链去访问一个已被删除的共享文件时，会因系统找 不到该文件而使访问失败，于是再将符号链删除，此时不会产生任何影响。
然而符号链的共享方式也存在自己的问题: 当其他用户去读共享文件时，系统是根据给 定的文件路径名，逐个分量(名)地去查找目录，直至找到该文件的索引结点。因此，在每次 访问共享文件时，都可能要多次地读盘。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。此外，要为每个共享用户建立一条符号链，而由于该链实际上是一个文件，尽 管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间。
符号链方式有一个很大的优点，是它能够用于链接(通过计算机网络)世界上任何地方的 计算机中的文件，此时只需提供该文件所在机器的网络地址以及该机器中的文件路径即可。
上述两种链接方式都存在这样一个共同的问题，即每一个共享文件都有几个文件名。 换言之，每增加一条链接，就增加一个文件名。这在实质上就是每个用户都使用自己的路 径名去访问共享文件。当我们试图去遍历(traverse)整个文件系统时，将会多次遍历到该共享 文件。例如，当有一个程序员要将一个目录中的所有文件都转储到磁带上去时，就可能对 一个共享文件产生多个拷贝。
6.6.3 磁盘容错技术
在现代计算机系统中，通常都存放了愈来愈多的宝贵信息供用户使用，给人们带来了 极大的好处和方便，但同时也潜在着不安全性。影响文件安全性的主要因素有三：
(1) 人为因素，即由于人们有意或无意的行为，而使文件系统中的数据遭到破坏或丢失。
(2) 系统因素，即由于系统的某部分出现异常情况，而造成对数据的破坏或丢失。特别 是作为数据存储介质的磁盘，在出现故障或损坏时，会对文件系统的安全性造成影响；
(3) 自然因素，即存放在磁盘上的数据，随着时间的推移将可能发生溢出或逐渐消失。
为了确保文件系统的安全性，可针对上述原因而采取以下措施：
(1) 通过存取控制机制来防止由人为因素所造成的文件不安全性。
(2) 通过磁盘容错技术来防止由磁盘部分的故障所造成的文件不安全性。
(3) 通过“后备系统”来防止由自然因素所造成的不安全性。
本小节主要讨论磁盘容错技术，而存取控制机制将在系统安全性一章中介绍。
容错技术是通过在系统中设置冗余部件的办法，来提高系统可靠性的一种技术。磁盘 容错技术则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的 一种技术，即当磁盘系统的某部分出现缺陷或故障时，磁盘仍能正常工作，且不致造成数 据的丢失或错误。目前广泛采用磁盘容错技术来改善磁盘系统的可靠性。
磁盘容错技术往往也被人们称为系统容错技术 SFT。可把它分成三个级别：第一级是 低级磁盘容错技术；第二级是中级磁盘容错技术；第三级是系统容错技术，它基于集群技 术实现容错。
第一级容错技术 SFT-Ⅰ
第一级容错技术(SFT-Ⅰ)是最基本的一种磁盘容错技术，主要用于防止因磁盘表面缺陷 所造成的数据丢失。它包含双份目录、双份文件分配表及写后读校验等措施。
1) 双份目录和双份文件分配表
在磁盘上存放的文件目录和文件分配表 FAT，是文件管理所用的重要数据结构。为了 防止这些表格被破坏，可在不同的磁盘上或在磁盘的不同区域中，分别建立(双份)目录表和 FAT。其中一份为主目录及主 FAT；另一份为备份目录及备份 FAT。一旦由于磁盘表面缺陷 而造成主文件目录或主 FAT 的损坏时，系统便自动启用备份文件目录及备份 FAT，从而可 以保证磁盘上的数据仍是可访问的。
2) 热修复重定向和写后读校验
由于磁盘价格昂贵，当磁盘表面有少量缺陷时，则可采取某种补救措施后继续使用磁 盘。一般主要采取以下两个补救措施：
(1) 热修复重定向：系统将磁盘容量的一部分(例如 2%～3%)作为热修复重定向区，用 于存放当发现磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记，以便于以后 对数据进行访问。
(2) 写后读校验方式。为了保证所有写入磁盘的数据都能写入到完好的盘块中，应该在 每次从内存缓冲区向磁盘中写入一个数据块后，又立即从磁盘上读出该数据块，并送至另 一缓冲区中，再将该缓冲区内容与内存缓冲区中在写后仍保留的数据进行比较。若两者一 致，便认为此次写入成功，可继续写下一个盘块；否则，再重写。若重写后两者仍不一致， 则认为该盘块有缺陷，此时，便将应写入该盘块的数据，写入到热修复重定向区中。
第二级容错技术 SFT-Ⅱ
第二级容错技术主要用于防止由磁盘驱动器和磁盘控制器故障所导致的系统不能正常 工作，它具体又可分为磁盘镜像和磁盘双工。
1) 磁盘镜像(Disk Mirroring)
为了避免磁盘驱动器发生故障而丢失数据，便增设了磁盘镜像功能。为实现该功能， 须在同一磁盘控制器下再增设一个完全相同的磁盘驱动器，如图 6-27 所示。当采用磁盘镜像方式时，在每次向主磁盘写入数据后，都需要将数据再写到备份磁盘上，使两个磁盘上具有完 全相同的位像图。把备份磁盘看作是主磁盘的一 面镜子，当主磁盘驱动器发生故障时，由于有备份磁盘的存在，在进行切换后，使主机仍能正常工作。磁盘镜像虽然实现了容错功能，但未能使 服务器的磁盘 I/O 速度得到提高，却使磁盘的利用率降至仅为 50%。如图 6-27 所示。
2) 磁盘双工(Disk Duplexing)
如果控制这两台磁盘驱动器的磁盘控制器发生故障，或主机到磁盘控制器之间的通道 发生了故障，磁盘镜像功能便起不到数据保护的作用。因此，在第二级容错技术中，又增 加了磁盘双工功能，即将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘 机镜像成对，如图 6-28 所示。
在磁盘双工时，文件服务器同时将数据写到 磁盘 控制器 两个处于不同控制器下的磁盘上，使两者有完全相同的位像图。如果某个通道或控制器发生故障时，另一通道上的磁盘仍能正常工作，不会造成数据的丢失。在磁盘双工时，由于每一个磁盘都有自己的独立通道，故可同时(并行)地将数据写入磁盘，或读出数据。
3．基于集群技术的容错功能
进入 20 世纪 90 年代后，为了进一步增强服务器的并行处理能力和可用性，采用了多 台 SMP 服务器来实现集群系统服务器。所谓集群，是指由一组互连的自主计算机组成统一 的计算机系统，给人们的感觉是，它们是一台机器。利用集群系统不仅可提高系统的并行 处理能力，还可用于提高系统的可用性，它们是当前使用最广泛的一类具有容错功能的集 群系统。其主要工作模式有三种：
① 热备份模式；
② 互为备份模式；
③ 公用磁盘模式。
下面我们介绍如何利用集群系统来提高服务器的可用性。
1) 双机热备份模式
如图 6-29 所示，在这种模式的系统中，备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。平时主服务器运行，备份服务器则 时刻监视着主服务器的运行，一旦主服务器出现故障，备份服务器便立即接替主服务器的 工作而成为系统中的主服务器，修复后的服务器再作为备份服务器。
为使在这两台服务器间能保持镜像关系，应在这两台服务器上各装入一块网卡，并通 过一条镜像服务器链路 MSL(Mirrored Server Link)将两台服务器连接起来。两台服务器之间 保持一定的距离，其所允许的距离取决于所配置的网卡和传输介质。如果用 FDDI 单模光纤， 两台服务器间的距离可达到 20 公里。此外，还必须在系统中设置某种机制，来检测主服务 器中数据的改变。一旦该机制检测到主服务器中有数据变化，便立即通过通信系统将修改 后的数据传送到备份服务器的相应数据文件中。为了保证在两台服务器之间通信的高速性 和安全性，通常都选用高速通信信道，并有备份线路。
在这种模式下，一旦主服务器发生故障，系统能自动地将主要业务用户切换到备份服 务器上。为保证切换时间足够快(通常为数分钟)，要求在系统中配置有切换硬件的开关设备， 在备份服务器上事先建立好通信配置，并能迅速处理客户机的重新登录等事宜。
该模式是早期使用的一种集群技术，它的最大优点是提高了系统的可用性，易于实现， 而且主、备份服务器完全独立，可支持远程热备份，从而能消除由于火灾、爆炸等非计算 机因素所造成的隐患。该模式的主要缺点是从服务器处于被动等待状态，整个系统的使用 效率只有 50%。
2) 双机互为备份模式
在双机互为备份的模式中，平时，两台服务器均为在线服务器，它们各自完成自己的 任务，例如，一台作为数据库服务器，另一台作为电子邮件服务器。为了实现两者互为备 份，在两台服务器之间，应通过某种专线连接起来。如果希望两台服务器之间能相距较远， 最好利用 FDDI 单模光纤来连接两台服务器，在此情况下，最好再通过路由器将两台服务器 互连起来，作为备份通信线路。图 6-30 示出了双机互为备份系统的情况。
在互为备份的模式中，最好在每台服务器内都配置两台硬盘，一个用于装载系统程序 和应用程序，另一个用于接收由另一台服务器发来的备份数据，作为该服务器的镜像盘。 在正常运行时，镜像盘对本地用户是锁死的，这样就较易于保证在镜像盘中数据的正确性。 如果仅有一个硬盘，则可用建立虚拟盘的方式或分区方式来分别存放系统程序和应用程序， 以及另一台服务器的备份数据。
如果通过专线链接检查到某台服务器发生了故障，此时，再通过路由器去验证这台服 务器是否真的发生了故障。如果故障被证实，则由正常服务器向故障服务器的客户机发出 广播信息，表明要进行切换。连接到故障服务器上的客户机在切换过程中会感觉到网络服 务器的短暂停顿。在切换成功后，客户机无需重新登录便可继续使用网络提供的服务和访 问服务器上的数据。而对于接在非故障服务器上的客户机，则只会感觉到网络服务稍有减 慢而已，不会有任何影响。当故障服务器修复并重新连到网上后，已被迁移到无故障服务 器上的服务功能将被返回，恢复正常工作。
这种模式的优点是两台服务器都可用于处理任务，因而系统效率较高，现在已将这种 模式从两台机器扩大到 4 台、8 台、16 台甚至更多。系统中所有的机器都可用于处理任务， 当其中一台发生故障时，系统可指定另一台机器来接替它的工作。
3) 公用磁盘模式
为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公 共磁盘被划分为若干个卷。每台计算机使用一个卷。如果某台计算机发生故障，此时系统 将重新进行配置，根据某种调度策略来选择另一台替代机器，后者对发生故障的机器的卷 拥有所有权，从而来接替故障计算机所承担的任务。这种模式的优点是：消除了信息的复 制时间，因而减少了网络和服务器的开销。
6.7 数据一致性控制
6.7.1 事物
- 事务的定义
事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看做是一系列相关 读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，也可放在多个文件 中。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以 托付操作(Commit Operation)来终止事务。只要有一个读、写或修改操作失败，便须执行夭 折操作(Abort Operation)。读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导 致的。
一个夭折的事务，通常已执行了一些操作，因而可能已对某些数据做了修改。为使夭 折的事务不会引起数据的不一致性，须将该事务内刚被修改的数据项恢复成原来的情况， 使系统中各数据项与该事务未执行时的数据项内容完全相同。此时，可以说该事务“已被 退回”(rolled back)。不难看出，一个事务在对一批数据执行修改操作时，要么全部完成， 并用修改后的数据去代替原来的数据，要么一个也不修改。事务操作所具有的这种特性， 就是我们在第二章中曾讲过的“原子性”。
事务记录(Transaction Record)
为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现。这些数据 结构被放在稳定存储器中，用来记录在事务运行时数据项修改的全部信息，故又称为运行 记录(Log)。该记录中包括有下列字段:
· 事务名：用于标识该事务的惟一名字；
· 数据项名：指被修改数据项的惟一名字；
· 旧值：修改前数据项的值；
· 新值：修改后数据项将具有的值。
在事务记录表中的每一记录，描述了在事务运行中的重要事务操作，如修改操作、开 始事务、托付事务或夭折事务等。在一个事务 T i 开始执行时，〈T i 开始〉记录被写入事务记 录表中；在 T i 执行期间，在 T i 的任何写(修改)操作之前，便写一适当的新记录到事务记录 表中；当 T i 进行托付时，把一个〈T i 托付〉记录写入事务记录表中。
恢复算法
由于一组被事务 T i 修改的数据以及它们被修改前和修改后的值都能在事务记录表中找 到，因此，利用事务记录表，系统能处理任何故障而不致使故障造成非易失性存储器中信息的丢失。恢复算法可利用以下两个过程:
(1) undo〈Ti 〉。该过程把所有被事务 T i 修改过的数据恢复为修改前的值。
(2) redo〈Ti 〉。该过程把所有被事务 T i 修改过的数据设置为新值。
如果系统发生故障，系统应对以前所发生的事务进行清理。通过查找事务记录表，可 以把尚未清理的事务分成两类。一类是其所包含的各类操作都已完成的事务。确定为这一 类事务的依据是，在事务记录表中，既包含了〈T i 开始〉记录，又包含了〈T i 托付〉记录。 此时系统利用 redo〈Ti 〉过程，把所有已被修改的数据设置成新值。另一类是其所包含的 各个操作并未全部完成的事务。对于事务 Ti ，如果在 Log 表中只有〈T i 开始〉记录而无 〈T i 托付〉记录，则此 T i 便属于这类事务。此时，系统便利用 undo〈Ti 〉过程，将所有已 被修改的数据，恢复为修改前的值。
6.7.2 检查点
- 检查点(Check Points)的作用
如前所述，当系统发生故障时，必须去检查整个 Log 表，以确定哪些事务需要利用 redo〈Ti 〉过程去设置新值，而哪些事务需要利用 undo〈Ti 〉过程去恢复数据的旧值。由于 在系统中可能存在着许多并发执行的事务，因而在事务记录表中就会有许多事务执行操作 的记录。随着时间的推移，记录的数据也会愈来愈多。因此，一旦系统发生故障，在事务 记录表中的记录清理起来就非常费时。
引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化，即每隔一 定时间便做一次下述工作：首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所 有记录输出到稳定存储器中；其次是将驻留在易失性存储器中的所有已修改数据输出到稳 定存储器中；然后是将事务记录表中的〈检查点〉记录输出到稳定存储器中；最后是每当 出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用 redo 和 undo 过程 实现恢复功能。
如果一个事务 T i 在检查点前就做了托付，则在事务记录表中便会出现一个在检查点记 录前的〈T i 托付〉记录。在这种情况下，所有被 T i 修改过的数据，或者是在检查点前已写 入稳定存储器，或者是作为检查点记录自身的一部分写入稳定存储器中。因此，以后在系 统出现故障时，就不必再执行 redo 操作了。
新的恢复算法
在引入检查点后，可以大大减少恢复处理的开销。因为在发生故障后，并不需要对事 务记录表中的所有事务记录进行处理， 而只需对最后一个检查点之后的事务记录进行处 理。因此，恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务 Ti 。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例 程便从该检查点开始，返回搜索各个事务的记录，并利用 redo 和 undo 过程对它们进行 处理。
如果把所有在事务 T i 以后开始执行的事务表示为事务集 T，则新的恢复操作要求是: 对 所有在 T 中的事务 TK ，如果在事务记录表中出现了〈T K 托付〉记录，则执行 redo〈TK 〉 操作；反之，如果在事务记录表中并未出现〈T K 托付〉记录，则执行 undo〈TK 〉操作。
6.7.3 并发控制
- 利用互斥锁实现“顺序性”
实现顺序性的一种最简单的方法是， 设置一种用于实现互斥的锁， 简称为互斥锁 (Exclusive Lock)。在利用互斥锁实现顺序性时，应为每一个共享对象设置一把互斥锁。当一 事务 T i 要去访问某对象时，应先获得该对象的互斥锁。若成功，便用该锁将该对象锁住， 于是事务 T i 便可对该对象执行读或写操作；而其它事务由于未能获得该锁而不能访问该对 象。如果 T i 需要对一批对象进行访问，则为了保证事务操作的原子性，T i 应先获得这一批 对象的互斥锁，以将这些对象全部锁住。如果成功，便可对这一批对象执行读或写操作； 操作完成后又将所有这些锁释放。但如果在这一批对象中的某一个对象已被其它事物锁住， 则此时 T i 应对此前已被 T i 锁住的其它对象进行开锁，宣布此次事务运行失败，但不致引起 数据的变化。
利用互斥锁和共享锁实现顺序性
利用互斥锁实现顺序性的方法简单易行。目前有不少系统都是采用这种方法来保证事 务操作的顺序性，但这却存在着效率不高的问题。因为一个共享文件虽然只允许一个事务 去写，但却允许多个事务同时去读；而在利用互斥锁来锁住文件后，则只允许一个事务去 读。为了提高运行效率而又引入了另一种形式的锁——共享锁(Shared Lock)。共享锁与互斥 锁的区别在于: 互斥锁仅允许一个事务对相应对象执行读或写操作，而共享锁则允许多个事 务对相应对象执行读操作，不允许其中任何一个事务对对象执行写操作。
在为一个对象设置了互斥锁和共享锁的情况下，如果事务 T i 要对 Q 执行读操作，则只 需去获得对象 Q 的共享锁。如果对象 Q 已被互斥锁锁住，则 T i 必须等待；否则，便可获得 共享锁而对 Q 执行读操作。如果 T i 要对 Q 执行写操作，则 T i 还须去获得 Q 的互斥锁。若 失败，须等待；否则，可获得互斥锁而对 Q 执行写操作。利用共享锁和互斥锁来实现顺序 性的方法，非常类似于我们在第二章中所介绍的读者—写者问题的解法。
6.7.4 重复数据的数据一致性问题
- 重复文件的一致性
我们以 UNIX 类型的文件系统为例，来说明如何保证重复文件的一致性问题。对于通 常的 UNIX 文件目录，其每个目录项中含有一个 ASCII 码的文件名和一个索引结点号，后 者指向一个索引结点。当有重复文件时，一个目录项可由一个文件名和若干个索引结点号 组成，每个索引结点号都是指向各自的索引结点。图 6-31 示出了 UNIX 类型的目录和具有 重复文件的目录。
在有重复文件时，如果一个文件拷贝被修改，则必须也同时修改其它几个文件拷贝， 以保证各相应文件中数据的一致性。这可采用两种方法来实现：第一种方法是当一个文件 被修改后，可查找文件目录，以得到其它几个拷贝的索引结点号，再从这些索引结点中找 到各拷贝的物理位置，然后对这些拷贝做同样的修改；第二种方法是为新修改的文件建立 几个拷贝，并用新拷贝去取代原来的文件拷贝。
盘块号一致性的检查
为了描述盘块的使用情况，通常利用空闲盘块表(链)来记录所有尚未使用的空闲盘块的 编号。文件分配表 FAT 则是用于记录已分配盘块的使用情况。由于 OS 经常访问这些数据 结构，也对它们进行修改，而如果正在修改时，机器突然发生故障，此时也会使盘块数据 结构中的数据产生不一致性现象。因此，在每次启动机器时，都应该检查相应的多个数据 结构，看它们之间是否保持了数据的一致性。
为了保证盘块数据结构(中数据)的一致性，可利用软件方法构成一个计数器表，每个盘 块号占一个表项，可有 0，…，N-1 项，N 为盘块总数。每一个表项中包含两个计数器，分 别用作空闲盘块号计数器和数据盘块号计数器。计数器表中的表项数目等于盘块数 N。在对 盘块的数据结构进行检查时，应该先将计数器表中的所有表项初始化为 0，然后，用 N 个空 闲盘块号计数器所组成的第一组计数器来对从空闲盘块表(链)中读出的盘块号进行计数；再 用 N 个数据盘块号计数器所组成的第二组计数器去对从文件分配表中读出的、已分配给文 件使用的盘块号进行计数。如果情况正常，则上述两组计数器中对应的一对(计数器中的) 数据应该互补，亦即，若某个盘块号在被第一组计数器进行计数后，使该盘块号计数器为 1， 则在第二组计数器中相应盘块号计数器中的计数必为 0；反之亦然。但如果情况并非如此， 则说明发生了某种错误。
图 6-32(a)示出了在正常情况下，在第一组计数器和第二组计数器中的盘块号计数值是 互补的；而图 6-32(b)示出的则是一种不正常的情况，对盘块号 2 的计数值在两组计数器中 都未出现(即均为 0)。当检查出这种情况时，应向系统报告。该错误的影响并不大，只是盘 块 2 未被利用。其解决方法也较简单，只需在空闲盘块表(链)中增加一个盘块号 2。图 6-32© 中示出了另一种错误，即盘块号 4 在空闲盘块表(链)中出现了两次，其解决方法是从空闲盘 块表(链)中删除一个空闲盘块号 4。图 6-32(d)中所示出的情况是相同的数据盘块号 5 出现了 两次(或多次)，此种情况影响较严重，必须立即报告。
链接数一致性检查
在 UNIX 类型的文件目录中，其每个目录项内都含有一个索引结点号，用于指向该文 件的索引结点。对于一个共享文件，其索引结点号会在目录中出现多次。例如，当有 5 个 用户(进程)共享某文件时，其索引结点号会在目录中出现 5 次；另一方面，在该共享文件的 索引结点中有一个链接计数 count，用来指出共享本文件的用户(进程)数。在正常情况下这 两个数据应该一致，否则就会出现数据不一致性差错。
为了检查这种数据不一致性差错，同样要配置一张计数器表，此时应是为每个文件而不是为每个盘块建立一个表项，其中含有该索引结点号的计数值。在进行检查时，从根目 录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加 1。 当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件 索引结点中的链接计数 count 值加以比较，如果两者一致，表示是正确的；否则，便是产生 了链接数据不一致的错误。
如果索引结点中的链接计数 count 值大于计数器表中相应索引结点号的计数值，则即使 在所有共享此文件的用户都不再使用此文件时，其 count 值仍不为 0，因而该文件不会被删 除。这种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上，浪费了存储空间。当 然这种错误的性质并不严重。解决的方法是用计数器表中的正确的计数值去为 count 重新 赋值。
反之，如果出现 count 值小于计数器表中索引结点号计数值的情况时，就有潜在的危险。 假如有两个用户共享一个文件，但是 count 值仍为 1，这样，只要其中有一个用户不再需要 此文件时，count 值就会减为 0，从而使系统将此文件删除，并释放其索引结点及文件所占 用的盘块，导致另一共享此文件的用户所对应的目录项指向了一个空索引结点，最终是使 该用户再无法访问此文件。如果该索引结点很快又被分配给其它文件，则又会带来潜在的 危险。解决的方法是将 count 值置为正确值。
