大数据算法课程笔记8a：page replacement algorithm

本节课主要是介绍page replacement algorithm的相关算法，包括offline和online。

1. 问题简介

这个是体系结构里面的经典问题，内存小、硬盘大，内存快、硬盘慢。所以CPU从内存中读取数据，而内存从硬盘中读取数据。那我们希望内存读取硬盘的次数尽量减少，这样可以减少程序的运行时间，而减少次数的算法主要依赖于page replacement algorithm。

所谓page fault，即内存中不存在所需数据而引入的错误，为了解决这个错误就需要从硬盘中读取数据到内存中。所以每个page fault都对应于一次硬盘读取，耗费大量时间。读到的数据需要覆盖内存中的某些现有数据，如何选择被替代的内存中的数据就是page replacement algorithm处理的问题。

（内存和硬盘的关系和cache与内存的关系一样，都是使用类似的思想）

2. Clairvoyant/offline algorithm

算法可以使用未来信息，即可以知道整个请求序列。（这个要求难以在实际中满足）

clairvoyant 算法的最优结果也是所有算法所能满足的最优算法，定义：Given a page arrival sequence $z$, $OPT(z)$ represents the minimum number of page faults by the best clairvoyant algorithm knowing the sequence $z$ of page arrivals.

2.1. Furthest in the future

FIF算法是一种clairvoyant 算法，并且满足$Cost(FIF,z)=OPT(z)$，即FIF算法的结果是最优的。

算法简介：每次选取最晚被请求的元素进行替换。具体地，设第$i$次请求$r_i$造成了一次page fault，对于cache中的每个元素$c_j$，定义$f_j=\arg\min_k\{r_k==c_j\wedge k>i\}$，则选择cache中的第$j=\arg\max_kf_k$个元素$c_j$进行替换。

例子：

2.2. FIF 最优性的证明

参考资料：

https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-farthest-in-future-optimal-caching-algorithm/

https://cseweb.ucsd.edu/classes/wi12/cse202-a/lecture4-final.pdf

基本思想：大框架是归纳法，结合分类讨论法。

设FIF的replacement schedule为SFF，而对于任意满足请求序列的schedule S，我们需要证明$\text{#fetches}(SFF)\le \text{#fetches}(S)$。所谓schedule，记录了算法的所有操作，例如insert a、evict b，通常一个page fault对应于一对insert和evict。 schedule 的一个子集是reduced schedule，即lazy schedule，只有当request某元素的时候才会insert该元素。一个事实是：对于任意schedule $S$, 永远存在一个reduced schedule $S^*$，满足$\text{#fetches}(S^*)\le \text{#fetches}(S)$。

基于以上的定义以及事实，我们开始证明FIF的最优性。明确目标以及归纳法的假设：

目标：$\forall S, \text{#fetches}(SFF)\le \text{#fetches}(S)$，即对于所有可以满足request的reduced schedule $S$，均满足硬盘读取数不小于$SFF$的读取数。

归纳法的假设：$\exists S_j$, such that $S_j$ makes the same decisions as $SFF$ for requests from $r_1$ to $r_j$, and $\text{#fetches}(S_j)\le \text{#fetches}(S)$.

Base Case: 令$S_0=S$, 则有$\text{#fetches}(S_0)\le \text{#fetches}(S)$，并且$S_0=SFF$ for requests from $r_1$ to $r_0$ (NULL)

假设存在$S_k$满足 $S_k$ makes the same decisions as $SFF$ for requests from $r_1$ to $r_k$, and $\text{#fetches}(S_k)\le \text{#fetches}(S)$.

我们从$S_k$构造$S_{k+1}$，使得 $S_{k+1}$ makes the same decisions as $SFF$ for requests from $r_1$ to $r_{k+1}$, and $\text{#fetches}(S_{k+1})\le \text{#fetches}(S)$. 方法如下：

1. 若$r_{k+1}$ in cache，则$S_k$和$SFF$均不会进行任何操作（SFF基于FIF算法，$S_k$基于reduced），所以$S_{k+1}=S_k$
2. 若$r_{k+1}$ misses, and $S_k$ and $SFF$ evict the same element, 则有$S_k$在$r_{k+1}$处的决策和$SFF$一致，所以$S_{k+1}=S_k$。
3. 若$r_{k+1}$ misses, and $S_k$ and $SFF$ evict different elements, suppose $S_k$ evicts $c_i$ and $SFF$ evicts $c_j$. 即两者分别替换的不同元素，从而有两个元素$c_i,c_j$参与讨论，而对于两个元素分别有request以及evict两种可能操作。我们对$r_{k+1}$之后$S_k$首次涉及$c_i,c_j$的操作进行分情况讨论：
   
   1. Next there is a request $r_d$ to $c_k$, and $S_k$ evicts $c_j$,　即$S_k$需要替换$c_j$了。调换两者的删除位置，使得$S_{k+1}$在第$r_{k+1}$处与$SFF$一样删除$c_j$，而在$r_d$处删除$c_k$，同样满足请求序列，并且$\text{#fetches}(S_{k+1})=\text{#fetches}(S_k)\ge \text{#fetches}(SFF)$。
   2. Next, there is a request $r_d$ to $c_i$, and $S_k$ evicts $c_j$. 即$S_k$删除$c_i$之后，在请求序列里又遇到了$c_i$，而且这次删除了$c_j$。我们使得$S_{k+1}$在$r_{k+1}$处删除$c_j$，而在$r_d$处即不需要进行任何操作，同样满足请求序列，并且$\text{#fetches}(S_{k+1})=\text{#fetches}(S_k)-1> \text{#fetches}(SFF)$
   3. Next, there is a request $r_d$ to $c_i$ and $S_k$ evicts $c'$. 即$S_k$删除$c_i$之后，在请求序列里又遇到了$c_i$，这次删除了一个非$c_j$的元素。注意到此次构造$S_{k+1}$需要满足$c_j$不被删除、所以我们同样使得$S_{k+1}$在第$r_{k+1}$处与$SFF$一样删除$c_j$，而在$r_d$处与$S_k$一样删除$c'$，而插入$c_j$。这样构造的$S_{k+1}$不是reduced，需要基于上诉Fact转化为reduced schedule $S^*_{k+1}$，并且满足$S^*_{k+1}$ makes the same decisions as $SFF$ for requests from $r_1$ to $r_{k+1}$, and $\text{#fetches}(S^*_{k+1})\le \text{#fetches}(S_{k+1})=\text{#fetches}(S_{k})\le \text{#fetches}(S)$.
   4. Next, there is a request to $c_j$, which is not possible, since $f_j>f_i$.

综上，基于归纳原则，我们证明了$\exists S_n$, such that $S_n$ makes the same decisions as $SFF$ for requests from $r_1$ to $r_n$, 从而$S_n=SFF$ 而且 $\text{#fetches}(SFF) = \text{#fetches}(S_n)\le \text{#fetches}(S)$.

基于上诉结论，我们最终证明了FIF的最优性。

3. Non-Clairvayant/Online algorithm

在线算法只能基于过去的信息进行决策。例如经典算法中常会使用出现的时间、出现的频率、最近出现的密度等等，各种算法在平均page fault number以及使用空间、时间之间做平衡，基于不同的请求序列分布以及权衡可以得到不同的算法。

这里主要介绍一种最简单的在线算法，然后对其进行分析。进而讨论所有在线算法的下界。

3.1. 评价函数 Metric

任意算法$A$对于给定的请求序列$z$的page fault数目用$Cost(A,z)$表示。而$OPT(z)=\min_A Cost(A,z)$，即最优算法（包括offline algorithm）的page fault数目。

使用$\frac {Cost(A,z)}{OPT(z)}$评价算法$A$在给定$z$上的表现，进而有最差情况$\max_z\frac {Cost(A,z)}{OPT(z)}$(competitve ratio)以及平均情况$\sum_{z\in u}\frac {Cost(A,z)}{OPT(z)}$。

3.2. least recently used algorithm (LRU)

算法简介：如名字所述，每次选择最不近使用的元素进行替换。具体地，设第$i$次请求$r_i$造成了一次page fault，对于cache中的每个元素$c_j$，定义$l_j=\arg\max_k\{r_k==c_j\wedge k<i\}$，则选择cache中的第$j=\arg\min_kl_k$个元素$c_j$进行替换。

例子：

性能分析：

首先将请求序列分为$b$个区块，每个区块内最多有$k$个元素，并且使得$b$尽可能小。

那么LRU对于每个区块最多遇到$k$个page fault，从而整体而言最多$bk$个page fault。而对于最优算法，至少遇到$b$个page fault，因为每次跳跃区块的时候都会遇到一个前一区块从未遇过的第$k+1$个元素，从而引入page fault。

所以LRU的competitive ratio $\le k$，其中$k$为cache size。

3.3. 所有确定性online page replacement algorithm的competitive ratio下界

Claim:对于所有determinisitic online page replacement algorithm $A$, $\exists z, \frac {Cost(A,z)}{OPT(z)}=k$。

证明方法很简单，构造一个只包含$k+1$个元素的请求序列，每次都使得$z$请求cache中不存在的元素（可以实现，因为算法只基于过去信息，而且是确定性的），那么$Cost(A,z)=n$，而$Cost(FIF,z)=n/k$，进而$\frac {Cost(A,z)}{OPT(z)}=k$。