1.3 文件缓存管理

功能总述

在上一节中我们已经拥有了页式文件系统的底层支持，但单有它还不足以称作一个完整的系统设计，因为在现有接口下我们只是一次读取一页（如果有需要的话）再写回，频繁地文件操作仍然会带来高昂的成本。现在到了该给系统设计一个缓存的时候了！

我们的缓存本身需要能存储若干页，在参考实现中取的 60000 页，这里我们沿用这一设定，但我强烈建议把它放在某个可以方便地配置的位置（编译时或运行时皆可），以便将来有需要时调整大小。尽管还没有讲细节，但你应该意识到，在一定范围内，缓存准备的页数越多，理论上性能会越高。

我们的缓存系统需要供上层系统直接访存读写指定页用，上层系统需要读写一页时它需要提供以下功能：

需要目标页是否在缓存中：
目标页在缓存中，直接读写内存中的副本
目标页不在缓存中，需判断是否仍有空闲页：
- 若有空闲页，从文件中获取一页并置入一个空闲页，然后在内存完成读写
- 若无空闲页，则需先舍弃缓存中一页，再从文件中获取一页并置入刚刚舍弃出的空位，然后在内存完成读写

这里涉及到两个问题，写入时机与置换策略。

写入时机

文件读取不会改变文件自身，因此并不复杂，但是涉及到写入时数据会发生双向流动：从文件到缓存，再从缓存到文件。后者的操作时机是一个值得斟酌的问题。

1. 写直达 (Write-Through)

我们可以只用内存来缓存读取，所有的写入均直接写到磁盘上，这种策略称作写直达，它的性能比不上下面介绍的写回，但是它的实现相对简单，在某些特殊的硬件缓存上可能会考虑这一策略来保证硬件逻辑的简洁性。但是在我们这种内存与磁盘性能差异以及 CPU 性能下，一般不会考虑这一策略，尤其是对局部数据频繁 UPDATE 或先 DELETE 再 INSERT 时它的性能会非常差。

2. 写回 (Write-Back)

写回策略在更多缓存系统中被使用，它一般配合 Dirty 位一并使用。无论是读还是写，我们总是需要先从文件中获取该页数据到内存，然后所有写入均在内存中直接操作，当该页缓存被舍弃（或者文件被关闭等）时再将缓存中的变化写回到文件中。

出于性能考虑，我们不应该将所有被舍弃的页均写回文件，因为其中可能有很多页只发生了读，没有被写过。为了区分被写过的页，我们引入 Dirty 标记位，当一页缓存被写入时，我们将对应的 Dirty 标记置为 True（一般将这种页面称作“脏页”），当该页被舍弃时，可以根据 Dirty 判断是否需要将写回文件。

置换策略

当缓存页被占满时，我们为了新的缓存页不得不放弃原有的一页，此时需要一个策略来决定放弃哪一页。

在介绍置换策略时，这些策略并非针对页式文件系统，而是这类缓存置换问题的通用算法，因此下面介绍算法时将不再提到“页”，而是直接用“数据项”来指代任何缓存系统中的目标数据。

决策内容的思考

除了占满时决定放弃谁外，即使缓存没被占满，我们或许也需要一个策略来判断应该用哪一个空位。这个问题或许并不重要，因为对多数策略来说用哪一个缓存页是无关紧要的。但如果再考虑到 CPU 本身的缓存，选择一些近期刚被舍弃的缓存页可能会给性能带来一定幅度的提升。

下面介绍几种基础的缓存置换算法（推荐使用 LRU，实现简单且有不错的性能，你也可以选择自己喜欢的策略）。

1. LRU

LRU (Least-Recently-Used) 即最近最少使用算法，是一种非常常见的缓存置换算法。它按照使用次序，将最后使用时间较久远的数据先替换掉。

LRU 名字解读

“最近最少使用” 对部分同学来说可能有些拗口，可以根据英文这样来理解它：

Recently Used 为我们的数据定义了一个顺序，按照最近被使用的时间排序，最近使用的一项为首项 (first)
Last 指上述排序后末尾的一项，也即使用时机距今最远的一项

例如，假设我们有一个容量为 3 的存储整数的缓存，我们依次访问数据序列 1 2 3 3 3 1 4 4 4 2 1，那么缓存的变化如下所示：

访问数据	缓存命中	舍弃缓存项	（访问后）缓存内容
1	F	_	[ 1 ? ? >
2	F	_	[ 2 1 ? >
3	F	_	[ 3 2 1 >
3	T	_	[ 3 2 1 >
3	T	_	[ 3 2 1 >
1	T	_	[ 1 3 2 >
4	F	2	[ 4 1 3 >
4	T	2	[ 4 1 3 >
4	T	2	[ 4 1 3 >
2	F	3	[ 2 4 1 >
1	T	_	[ 1 2 4 >

共计访存命中 6 次（如果用下面的 LFU 则是 5 次）。

为了高效实现这样的效果，可以考虑使用一个环形链表，将所有数据项在缓存中的编号连成一个链表。当某项被访问时将对应结点置为首项；当需要将新的数据项置入缓存时总是置入链表尾项结点对应的编号项并将其置为首项，如果该项已被占用则需先舍弃原来的数据项并处理可能的写回。在这种策略下，置换策略的相关操作复杂度均为 O(1)。

2. LFU

LFU (Least-Frequently-Used) 即最不经常使用法，这个方法需要记录所有数据项的访问频率（频次），将访问最少的数据项舍弃。

这里给出一个简单的例子，使得 LFU 性能比 LRU 好。仍然假设容量为 3 的存储整数的缓存，我们依次访问数据序列 1 1 2 3 4 1 5 6 7 1，缓存变化如下所示：

访问数据	缓存命中	舍弃缓存项	（访问后）缓存内容
1	F	_	1(1) ?(0) ?(0)
1	T	_	1(2) ?(0) ?(0)
2	F	_	1(2) 2(1) ?(0)
3	F	_	1(2) 2(1) 3(1)
4	F	2	1(2) 4(1) 3(1)
1	T	_	1(3) 4(1) 3(1)
5	F	3	1(3) 4(1) 5(1)
6	F	4	1(3) 6(1) 5(1)
7	F	5	1(3) 6(1) 7(1)
1	T	_	1(4) 6(1) 7(1)

注意到后 3 次访问 1 均会命中缓存，但若用 LRU 则只能命中一次缓存。

这种方法会维护全局计数信息，某些情况下效果确实不错，但是也有一些显著问题：

可能需要维护斐波那契堆之类的较复杂结构来支持访问最小项以及任意项更新
当有多个低频次并列时，算法本身并没有给出确定性的替换对象，而这种 case 可能被一些特定的场景放大导致它无法起到预想的作用
算法没有“局部性”，全局的频次统计可能导致某小段内被大量访问的数据可能被长久记忆——即使这些数据早已无人问津

因此这一策略在实际应用中并不常见。

3. FIFO

FIFO (First-In-First-Out) 即先进先出，只需要维护一个队列，只考虑数据项入队的时间，当队列满时将最早入队的元素出队。

下面构造一种简单情况使得 FIFO 的性能比 LRU 和 LFU 好。同样假设容量为 3 的存储整数的缓存，我们依次访问数据序列 1 2 3 1 4 5 3，缓存变化如下所示：

访问数据	命中缓存	舍弃缓存项	（访问后）缓存内容
1	F	_	[ 1 ? ? >
2	F	_	[ 1 2 ? >
3	F	_	[ 1 2 3 >
1	T	_	[ 1 2 3 >
4	F	1	[ 2 3 4 >
5	F	2	[ 3 4 5 >
3	T	_	[ 3 4 5 >

共计缓存命中 2 次，如果用 LRU 或者 LFU 均只能命中一次。

FIFO 实现简单，只需要一个最基本的队列，但是可能会导致频繁访问项被舍弃，并且存在 Belady 现象，实际应用并不广泛。

Belady现象

使用 FIFO 等算法时，可能出现在相同的访存序列下，缓存容量增大后，缓存缺失次数反而升高的异常现象。

感兴趣的同学可以自行构造这样的例子，《操作系统》课程中也会讲到相关知识。

系统组装

有了上述基础，我们下面完成一个缓存管理器（参考实现的 BufPageManager）只需要一些组装。它底层依赖一个页式文件系统管理器（参考实现的 FileManager）和一个缓存置换器（参考实现的 FindReplace）。

它对外提供的接口与页式文件系统基本一致，只是需要考虑是真的要调用文件系统，还是直接进行内存操作。注意写操作可能有两种实现办法：

不提供单独的写入接口，对外的读取接口返回缓存的引用，外部修改时需要手动调用缓存管理器的接口将对应页标记为 dirty
提供单独的写入接口，对外的读取接口返回的是一页的拷贝，缓存中给的数据独此一份，调用写接口时会用传进来的数据覆盖原有的缓存页并标记 dirty

前一种实现性能更高，但是用起来也有更高的风险；后一种更直观，但是会引入拷贝一页的成本。无论是哪一种实现，均是基于写回策略。

在参考实现中，采用的上述第一种方案，因此它还为缓存管理器提供了以下接口：

close: 关闭管理器，将所有脏页写回文件（个人建议写入析构函数）
writeBack: 将指定页面写回并舍弃
release: 将指定页面舍弃，即使是脏页也不写回
access: 标记一页被访问过
markDirty: 标记一页为脏页
allocPage: 越过查找缓存直接进行文件 IO，需要调用方保证该页不在缓存

Authors: Congyuan Rao