分页（在线缓存）
前言
而不是从正式定义开始，目标是通过一系列示例来处理这些主题，并在此过程中引入定义。备注部分理论将包含所有定义，定理和命题，以便为你提供更快速查找特定方面的所有信息。
备注部分来源包括用于该主题的基础材料和用于进一步阅读的附加信息。此外，你还可以找到示例中的完整源代码。请注意，为了使示例的源代码更具可读性和更短，它会避免错误处理等问题。它还会传递一些特定的语言功能，这些功能会模糊示例的清晰度，如广泛使用高级库等。
分页
寻呼问题源于有限空间的限制。我们假设我们的缓存 C 有 k 页面。现在我们要处理一系列 m 页面请求，这些请求必须在处理之前放入缓存中。当然，如果 m<=k 然后我们只是将所有元素放在缓存中它会起作用，但通常是 m>>k。
我们说当页面已经在缓存中时，请求是缓存命中，否则，它被称为缓存未命中。在这种情况下，我们必须将请求的页面带入缓存并逐出另一个，假设缓存已满。目标是一种驱逐计划，可以最大限度地减少驱逐次数。
这个问题有很多策略，让我们来看看：
- 先进先出（FIFO） ：最旧的页面被逐出
- 最后，先出（LIFO） ：最新页面被逐出
- 最近最少使用（LRU） ：最近访问最早的 Evict 页面
- 最少使用（LFU） ：最不常请求的 Evict 页面
- 最长前向距离（LFD） ：缓存中的 Evict 页面，直到将来最远才会请求。
- 完全刷新（FWF） ：一旦发生缓存未命中，就清除缓存完成
有两种方法可以解决这个问题：
- 离线 ：提前知道页面请求的顺序
- 在线 ：提前查询页面请求的顺序
离线方法
对于第一种方法，请查看 “贪婪技术的应用 ”主题。这是第三个示例离线缓存考虑了上面的前五个策略，为你提供了以下的良好切入点。
示例程序通过 FWF 策略进行了扩展 ：
class FWF : public Strategy {
public:
FWF() : Strategy("FWF")
{
}
int apply(int requestIndex) override
{
for(int i=0; i<cacheSize; ++i)
{
if(cache[i] == request[requestIndex])
return i;
// after first empty page all others have to be empty
else if(cache[i] == emptyPage)
return i;
}
// no free pages
return 0;
}
void update(int cachePos, int requestIndex, bool cacheMiss) override
{
// no pages free -> miss -> clear cache
if(cacheMiss && cachePos == 0)
{
for(int i = 1; i < cacheSize; ++i)
cache[i] = emptyPage;
}
}
};
完整的源代码可在此处获得 。如果我们重用主题中的示例，我们将得到以下输出：
Strategy: FWF
Cache initial: (a,b,c)
Request cache 0 cache 1 cache 2 cache miss
a a b c
a a b c
d d X X x
e d e X
b d e b
b d e b
a a X X x
c a c X
f a c f
d d X X x
e d e X
a d e a
f f X X x
b f b X
e f b e
c c X X x
Total cache misses: 5
尽管 LFD 是最佳的，但 FWF 具有较少的缓存未命中。但主要目标是尽量减少驱逐的次数，而对于 FWF 的五次失误意味着 15 次驱逐，这使得它成为这个例子中最贫穷的选择。
在线方法
现在我们想要解决分页的在线问题。但首先我们需要了解如何做到这一点。显然，在线算法不能优于最优离线算法。但它有多糟糕？我们需要正式的定义来回答这个问题：
定义 1.1： 一个优化问题 Π由一组的情况下， ＆Sigma; Π 。对于每一个实例σ∈Σ Π 有一组Ζ σ 的解决方案和一个目标函数 ˚F σ ：Ζ σ →交通ℜ ≥0 其中分配 apositive 真实值的每一个的解决方案。
我们说 OPT（σ）是最优解的值，A（σ）是算法 A 对于问题Π和 w A （σ）= fσ （A（σ））其值的解。
定义 1.2： 用于最小化问题的在线算法 A 如果存在常数τ∈ℜ，则竞争比率 r≥1
w A （σ）= fσ （A（σ））≤r·OPT（σ）+τ
所有实例σ∈Σ Π 。A 称为 r 竞争在线算法。甚至
w A （σ）≤r⋅OPT（σ）
所有实例σ∈Σ Π 则称 A 是一个严格的 R-竞争力的在线算法。
所以问题是我们的在线算法与最优离线算法相比具有多大的竞争力。在着名的书中， Allan Borodin 和 Ran El-Yaniv 使用另一种方案来描述在线分页情况：
有一个邪恶的对手知道你的算法和最优的离线算法。在每一步中，他都会尝试请求最适合你的页面，同时最适合离线算法。算法的竞争因素是你的算法对对手的最佳离线算法有多么糟糕的因素。如果你想成为对手，你可以尝试对手游戏 （尝试击败分页策略）。
标记算法
我们不是单独分析每个算法，而是查看一个特殊的在线算法系列，用于称为标记算法的分页问题。
令σ=（σ 1 ，…，σ p ）的实例为我们的问题和 k 我们的高速缓存大小，比σ可以分为几个阶段：
- 阶段 1 是从开始到最大 k 请求不同页面的σ的最大子序列
- 阶段 i≥2 是从 pase i-1 结束到最大 k 请求不同页面的σ的最大子序列
例如，k = 3：
标记算法（隐式或显式）维护页面是否被标记。在每个阶段的开始都是未标记的所有页面。是否在标记的阶段期间请求页面。算法是一种标记算法，如果它永远不会从缓存中驱逐标记的页面。这意味着在一个阶段使用的页面将不会被驱逐。
命题 1.3： LRU 和 FWF 是标记算法。
证明： 在每个阶段的开始（第一个阶段除外）， FWF 具有缓存未命中并清除缓存。这意味着我们有 k 个空页面。在每个阶段都要求最多 k 个不同的页面，因此在阶段期间将会出现逐出的情况。所以 FWF 是一种标记算法。
假设 LRU 不是标记算法。然后有一个实例σ，其中 LRU 在阶段 i 中被标记的页面 x 被驱逐。让σ 吨 在阶段 I，其中 x 被逐出该请求。由于 x 被标记，因此在同一阶段中 x 必须有较早的请求σt * ，因此 t * <t。T *之后，x 是最新的缓存页面，所以要在 t 序列σ得到了拆迁户 T * + 1 ，…，σ ŧ 必须从 x 个不同的页面请求至少 k。这意味着阶段 i 已经请求至少 k + 1 个不同的页面，这与阶段定义相矛盾。因此 LRU 必须是标记算法。
命题 1.4： 每个标记算法都是严格的 k 竞争性。
证明： 设σ是寻呼问题的实例和σ的相位数。当 l = 1 则则每个标记算法都是最优的并且最优离线算法不能更好。
我们假设 l≥2。每个标记算法的成本，例如，σ从上面用 l·k 限制，因为在每个阶段中，标记算法不能驱逐超过 k 个页面而不驱逐一个标记页面。
现在我们试图表明，最优离线算法在第一阶段中为σ，k 驱逐了至少 k + 1-2 页，并且除了最后一阶段之外每个后续阶段至少有一个。为了证明，我们定义σ的 l-2 析取子序列。子序列 i∈{1，…，l-2}从阶段 i + 1 的第二个位置开始，并以阶段 i + 2 的第一个位置结束。
设 x 为阶段 i + 1 的第一页。在子序列 i 的开始处，在最佳离线算法高速缓存中存在页面 x 和至多 k-1 个不同页面。在子序列中，我的 k 页面请求与 x 不同，因此最佳离线算法必须为每个子序列驱逐至少一页。由于在阶段 1 开始缓存仍为空，因此最佳离线算法在第一阶段期间导致 k 驱逐。这表明了这一点
w A （σ）≤l⋅k≤（k + l-2）k≤OPT（σ）·k
推论 1.5： LRU 和 FWF 是严格 K-竞争力。
练习： 表明 FIFO 不是标记算法，但严格来说是 k 竞争性的。
对于在线算法 A 是否具有竞争力，我们称之为 A 不具有竞争力
命题 1.6： LFU 和后进先出法是没有竞争力。
证明： 设 l≥2 常数，k≥2 缓存大小。不同的缓存页面是 nubered 1，…，k + 1。我们看看以下顺序：
第一页 1 被请求 l 次而不是第 2 页，因此一次。最后，对页面 k 和 k + 1 存在（l-1）交替请求。
LFU 和 LIFO 用 1-k 页填充缓存。当请求页面 k + 1 时，页面 k 被逐出，反之亦然。这意味着子序列（k，k + 1） l-1 的 每个请求都会驱逐一页。此外，它们是第一次使用第 1-（k-1）页时的 k-1 缓存未命中。所以 LFU 和 LIFO 逐出大致的 k-1 + 2（l-1）页面。
现在我们必须证明，对于每个常数τ∈ℜ和每个常数 r≤1，都存在 l
等于
为了满足这种不相等，你必须选择足够大的。因此 LFU 和 LIFO 没有竞争力。
命题 1.7： 有没有 R-中的竞争与寻呼确定性在线算法 [R <K 。
最后一个命题的证明相当长，并且基于 LFD 是最优离线算法的陈述。感兴趣的读者可以在 Borodin 和 El-Yaniv 的书中查阅（参见下面的资料）。
问题是我们能否做得更好。为此，我们必须将确定性方法抛在脑后，开始随机化我们的算法。显然，如果算法是随机的，那么攻击者就更难以惩罚你的算法。
随机分页将在下一个例子中讨论……