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

大数据算法课程笔记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 $z$, OPT(z)$OPT(z)$ represents the minimum number of page faults by the best clairvoyant algorithm knowing the sequence z $z$ of page arrivals.

2.1. Furthest in the future

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

算法简介：每次选取最晚被请求的元素进行替换。具体地，设第 i $i$次请求ri$r_i$造成了一次page fault，对于cache中的每个元素 cj $c_j$，定义 fj=argmink{rk==cj∧k>i} $f_j=argmin_k{r_k==c_jwedge k>i}$，则选择cache中的第 j=argmaxkfk $j=argmax_kf_k$个元素 cj $c_j$进行替换。

例子：

2.2. FIF 最优性的证明

参考资料：

/

.pdf

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

设FIF的replacement schedule为SFF，而对于任意满足请求序列的schedule S，我们需要证明 #fetches(SFF)≤#fetches(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 $S$, 永远存在一个reduced schedule S∗$S^*$，满足 #fetches(S∗)≤#fetches(S) $text{#fetches}(S^*)le text{#fetches}(S)$。

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

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

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

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

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

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

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

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

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

3. Non-Clairvayant/Online algorithm

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

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

3.1. 评价函数 Metric

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

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

3.2. least recently used algorithm (LRU)

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

例子：

性能分析：

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

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

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

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

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

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