贪心算法在计算机体系结构中的应用

2023-11-08

一.前言

二.离线缓存(Offline caching)

1.高速缓存技术的简要介绍

（2）反证法证明（“cut-paste”法）

一.前言

大二已经修过“计算机组成原理"、“操作系统”两门课程。最近“算法导论”课程也已经结束，复习算法时参看了算法巨著——《Introduction to Algorithm》（算法导论第3版）。又得知了该书已经出了第四版，但是还没有汉译版本，于是找到了英文版的电子版，看了看相比第三版的调整，贪心算法章节将第三版的课后题“离线缓存”单独拿出来作为一节，大概看了看是介绍贪心算法在缓存中的应用，于是又联想到计组中的cache内容和操作系统中的作业调度和页面置换，似乎一脉相承，异曲同工，都是贪心算法的应用，于是想到总结一下，遂产此文。

二.离线缓存(Offline caching)

该部分会对《算法导论》第四版该章节全篇翻译分析，解释贪心算法如何解决此问题。

1.高速缓存技术的简要介绍

计算机系统可以通过将主存的子集（部分数据）存入缓存来减少访问数据的时间，一个“小而快”的存储器，同时介绍了缓存块的典型配置，并且提到了主存也可看作磁盘的高速缓存，因为主存也是存储磁盘的常驻数据，体现了计算机存储结构的一种逐层缓存的思想。

对于“缓存”这种技术与思想可以参看作者另一篇文章，其中对高速缓存思想进行了十分详细的介绍和剖析。

大话局部性原理__坐看云起时_的博客-CSDN博客_局部性原理的应用局部性原理在计算机科学多领域的具体体现以及优化程序的策略https://blog.csdn.net/qq_53162179/article/details/125004093

2.问题引入

这段介绍了我们要解决的问题：

有一个计算机程序作出一系列的内存请求，假设有n次内存请求，有n个内存块: $b_{1},b_{2},b_{3}...,b_{n}$ ，在一个访问序列中，同一内存块可能被访问多次。缓存的缓存块数是固定的，有k个，在第一次访问之前，缓存是空的，每次请求都至多有一个块从主存进入缓存或者被从缓存淘汰到主存。在一次访问中，对于一个块 $b_{i}$ ，有以下三种情况：

（1）所要访问的内存块 $b_{i}$ 已经在缓存中，此时称作“缓存命中”。

（2）所要访问的内存块 $b_{i}$ 不在缓存中，此时缓存还未装满，要从内存中找到这个块放入缓存。

（3）所要访问的内存块 $b_{i}$ 不在缓存中，此时缓存已经装满，要从缓存中淘汰一个块，把这次要访问的块从内存中找到移入缓存。

那么我们要解决的问题就是：（3）中，要淘汰缓存中的哪个块最合适？

3.精确问题，寻找思路

上面（2）与（3）出现的所要访问的内存块不在缓存中叫做“缓存未命中”。

我们的目标是：减少缓存未命中次数，提高缓存命中率。

如果是第一次访问缓存cache，那么缓存是从空的开始填充，此时未命中叫作“强制未命中”，我们要讨论的是缓存已满情况下发生的缓存未命中。那么淘汰哪个块最合适呢？

淘汰哪个缓存块最理想的选择是：该选择应保证在整个未来的请求序列中，可能发生的缓存未命中次数最少。

通常情况下，缓存是一个在线问题，因为计算机要在不知道未来的请求序列的情况下决定保留哪个块，我们假设这个问题变成离线问题，就是提前知道整个请求序列。

4.引入贪心算法

书中提供了一种“将来最远” 的贪心策略。就是淘汰请求序列中下一次访问距离最远的数据，但是要证明该问题满足贪心策略的使用前提：（1）最优子结构（2）贪心选择性质。

然后书中又阐述了为什么这种离线的假设是合理的，因为主存也可看做是磁盘的缓存，会有其他的算法来确定出要做的全部读写操作（整个序列是可预知的，不用在线），这就为我们研究离线缓存提供了合理性。

还举了一个现实中的应用该模型的例子，就是你有一个固定的日程表，里面给出了未来一段时间你要去某些地方做事，这些地方你也是知道的，而且有的地方不只去一次。你可以在这些地方设置代理，但是代理的数量是有限的，要小于所要去的地点的总数，那么当你要去的地方没有代理，办完事后就要改变代理的布置，要从原来的代理集合中淘汰一个，再换上刚才办事没有代理的那个地方，那么每次拿走哪个地方的代理，能够让“去办事发现当地没有代理”这种情况发生的最少。

其中代理就相当于cache块，要办的事就相当于请求，更换一次代理布置就意味着一次缓存未命中。

5.最优子结构性质的证明

（1）变量准备

定义了一个表示子问题的量（C，i ) ，C代表缓存当前的配置，这里“配置”指的是cache中存了哪些块的情况，相当于一个“目录”，i代表请求序列中 $b_{i},b_{i+1},...,b_{n}$ 的部分，解决子问题（C，i）就是要作出一系列决定来明确在处理请求序列 $b_{i},b_{i+1},...,b_{n}$ 的过程中每次淘汰哪个块，对子问题（C，i）的最优解就是在最小化该子部分的缓存未命中次数。

（2）反证法证明（“cut-paste”法）

假设S是子问题（C，i）的最优解，让 $C^{'}$ 代表在S作为最优解的情况下，每次访问后cache的目录，目录可能更新，也可能不经过处理（取决于是否命中和淘汰），我们现在认为 $S^{'}$ 是问题（C，i）的子问题（ $C^{'}$ ，i+1）的最优解，我们假设我们之前的“认为”是错误的，它不是最优解，有一个解 $S^{''}$ 比它更优，那么我们可以把 $S^{'}$ 从S中“cut”掉，把 $S^{''}$ “paste"上，这样就得到了一个新解 $S^{*}$ ，是问题（C，i）的最优解，与之前的假设：S是最优解相矛盾，这样 $S^{*}$ 必不存在，那么之前的 $S^{''}$ 也必然不存在，显然我们之前的”认为“是正确的。

6.递推表达式设计

定义一个集合 $R_{C,i}$ 来跟踪cache目录表的变化，分为三种情况：

（1）如果缓存命中，cache目录保持不变，那么 $R_{C,i}$ ={C}。

（2）如果缓存未命中，cache还未装满（|C|<k)，那么就把 $b_{i}$ 装入内存， $R_{C,i}$ ={C $\cup$ $b_{i}$ }

（3）如果缓存未命中，cache已经装满（|C|=k)，那么此时 $R_{C,i}$ 包含了k种可能性，C中的每一个块都有被淘汰并且替换成 $b_{i}$ 的可能，这种情况下， $R_{C,i}$ ={(C-{x}) $\cup$ { $b_{i}$ } }。

让miss（C,i）表示对于子问题（C，i）的一个解的最小未命中次数，图中给出了递推式。

第一种情况（i=n and $b_{n}\in C$ )，此时只访问 $b_{n}$ 一个缓存块，且该块已经在缓存内，所以未命中次数为0，第二种情况就是它不在，那就为1。

第三种情况就是 $b_{i}$ 在访问序列中，同时也在缓存中，那么必命中，于是访问 $b_{i}$ 前后总的未命中次数没有改变，miss（C，i）=miss（C，i+1）。

第四种就是 $b_{i}$ 在访问序列中，但不在缓存中，那么该序列至少有一次缓存未命中，那么就要淘汰缓存中一个块换进来 $b_{i}$ ，C就变成 $C^{'}$ ，于是（C，i）整体的最小未命中次数就等于（1+min{ miss( $C^{'}$ ，i+1）}。

7.贪心性质的证明（很麻烦）

这里作者就提出了他那个贪心选择——“Farthest-in-future”，淘汰将来最远访问的那个，把那个块作为z= $b_{m}$ ,并且添加一个对该块的虚拟的请求到序列最后（ $b_{m}=b_{n+1}$ ）。

下面引用Kleinberg J., Tardos E.，Algorithm Design的ppt说明以下：

f就是将来最远访问的那个。

在这里插播一个：就是你可能会考虑到这样一个问题：我们可不可以在还没发生未命中的时候就替换块，也许这时候cache已满，访问的块还正好在cache中，按照我们以前的思路是不用替换，那么我们替换的话会不会产生什么更好的效果，答案是不会，我们大可不必随时替换块，只要在发生未命中且cache已满的情况下替换就行，得到的效果肯定不比所谓的“未雨绸缪”差。

reduced schedule定义为：一个schedule，他只在miss的时候进行数据替换。我们可以证明任意一个unreduced schedule，均可以变换成一个reduced schedule ，而不增加替换(未命中)次数。

证明过程：

这里面S就是unreduced schedule, $S^{'}$ 就是reduced schedule。先看case1:

开始时候c在缓存内，且缓存已满，这时候下一个访问应该是e，而不是d，S就想耍小聪明，它遵循着随时可以替换的原则，想提前把d拎进来，但是当拿进来之后， $t^{'}$ 时候访问了e，这时候不得不把d换掉，把e装进来，而reduced schedule的 $S^{'}$ 就是等需要替换的时候再说，不用提前替换，这样在t~ $t^{'}$ 时间内就省下一次不必要操作。

case2：case1你可能不服，认为下一个来的是e不是d，如果 $t^{'}$ 时候访问了d，S不用再替换了，那么到发生下次访问之前，S总共做了一次替换，就是把d提前换进来，扔掉c，再看 $S^{'}$ ，保持原状不动，直到 $t^{'}$ 时候访问了d，发生未命中，才把d换进来，那么到发生下次访问之前，也总共做了一次替换，所以劳动量都是一样的。

下面正式证明贪心选择“Farthest-in-future”的合理性

这部分内容《算法导论》第四版给了大段的英文描述，本文作者英文阅读能力有限，将这些论证翻译过来并用易理解的汉语阐述需要一定的时间，所以打算用Kleinberg J., Tardos E.，Algorithm Design的ppt来讲，《算法导论》的原文后面会给。

这里的 $S_{FF}$ 就表示用贪心选择“Farthest-in-future”的解决方法，我们要证明这个贪心选择是最优的，那么我们可以假设一个最优的选择叫S，如果S可以经过一些变换（等价的）替换成 $S_{FF}$ ，那么就可以说明 $S_{FF}$ 也是最优解。

这个S也是reduced schedule，并且满足对于前j个访问作出的淘汰选择都与 $S_{FF}$ 相同，我们再定义一个 $S^{'}$ ，这个 $S^{'}$ 满足对于前j+1个访问作出的淘汰选择都相同，如果我们能证明 $S^{'}$ 与S是等价的或者更优于S，那么经过迭代，最后就能推出S与 $S_{FF}$ 也相同（再弄个 $S^{''}$ 前j+2个都与 $S_{FF}$ 相同，且证明与 $S^{'}$ 等价，链式递推。。。）

因为S 满足对于前j个访问作出的淘汰选择都与 $S_{FF}$ 相同，那么j+1访问之前，它们两个的cache目录也是相同的，因为做的操作都一样。

假设第j+1步的时候，访问了d，可能有以下四种情况：

（1）d既在S的cache内，也在 $S_{FF}$ 的cache内，此时保持原状不变，那么 $S^{'}$ 与S也等价，因为大家都没变，所以三者都相等，假设成立， $S_{FF}$ 的选择就是最优的。

（2）d不在S和 $S_{FF}$ 的cache内，且二者淘汰的块相同，那么S就变成前j+1步也与 $S_{FF}$ 相同了，就变成 $S^{'}$ 了，三者又相同，最后能推出 $S_{FF}$ 就是最优解。

（3）d不在S和 $S_{FF}$ 的cache内，且二者淘汰的块不同

d不在S和 $S_{FF}$ 的cache内，且二者淘汰的块不同， $S_{FF}$ 淘汰的是e，S淘汰的是f，第j次访问结束之后，S、 $S_{FF}$ 、 $S^{'}$ 三者的组成是等价的，j+1次访问后，我们让 $S^{'}$ 淘汰块e，与 $S_{FF}$ 一样，这样S与 $S^{'}$ 就产生区别了。

这个时候 S与 $S^{'}$ 的构成可以表示为：

之后我们继续进行访问，二者（S与 $S^{'}$ ）的操作可能相同也可能不同

当S与 $S^{'}$ 在j+1之后第一次做出不同动作时，我们让那次为 $j^{'}$ ，且那次要访问的块是g，那么就可能发生三种情况

g=e，这种情况不可能发生，因为贪心选择“Farthest-in-future”在j+1那次访问中淘汰了e，那个时候cache里面还有f，这就说明e在未来的访问序列中一定比f要远，那么在访问e之前必先访问f，那就不是第一次二者做出不同选择，所以g不可能为e。
g=f，因为f不在S中，所以S未命中，要淘汰一个块，这就又出现了两种可能：

第一种，S淘汰块e，换上f，这时候 $S^{'}$ 命中，因为一直就有f，那么此时你会发现S与 $S^{'}$

相同了。

第二种，S淘汰的不是e，是 $e^{'}$ （包含在两个cache的same里），那么这时候S就与 $S^{'}$ 有两个不同，一个是刚才S淘汰的那个， $S^{'}$ 还有，另一个区别是S和 $S^{'}$ 之前的区别（e和f)，这时候我们之前证的那个结论就有用了，因为 $S^{'}$ 已经访问过f了，那么将来肯定要访问e，因为e是“Farthest-in-future”，那么我们可以提前刷小聪明，把e先换进来，这之前证明过了，和以后再换进来效果是一样的，那么 $S^{'}$ 可以同样换掉 $e^{'}$ ，然后把e换进来，这时候S与 $S^{'}$ 又相同了。

g既不是e也不是f

这时候二者都需要淘汰，那就S淘汰e， $S^{'}$ 淘汰f，这样二者都换进来g，又等价了。

（4）d在S内，但不在 $S^{'}$ 内，这时候S命中， $S^{'}$ 未命中，一定有结论：在这次访问之前或者之后，一定有一次“补偿”，让S未命中， $S^{'}$ 命中，这里不做证明，可以去看《算法导论》

上述论证了S与 $S^{'}$ 在一系列动作之后是可以转换成有相同cache组成的，那么从组成相同时候开始， $S^{'}$ 就可以在后续的步骤中模仿S，因为S是最优解，且替换次数不大于S，这样反复，就可以推出S与 $S_{FF}$ 是等价的，也就是说我们的贪心选择“Farthest-in-future”是可以得到最优解的。

三.贪心策略在计算机底层的其他应用

这里谈一下操作系统，在通用操作系统中，对于问题的处理通常没有具体的界限，操作系统一般不从局部或者整体的角度来讨论具体的算法，这些算法也都有各自的适应性和优缺点。而贪心算法需要有明确的问题范围，然后在该范围内做出一个贪心选择，分出一个子问题，再做每一步的贪心，目的是求一个整体问题的优化目标，所以我们下面介绍的算法只能说是借鉴了“贪心算法”的思想。

1.进程调度算法

进程调度算法中的短作业优先（SJF），每次选取的都是以到达的且运行时间最短的进程，实际上就是一种直观地认为先做执行时间短的进程会缩短平均周转时间，相当于一种贪心的思想。

2.磁盘调度算法

其中“ 最短时间寻找优先（SSTF）”就是采用了贪心的思想，该算法优先处理的磁道是离磁头最近的磁道，可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短，这就是选择眼前最优但做不到整体最优。

3.页面置换算法

页面置换算法中的” 最佳置换算法（OPT）“就采用了我们上面在”离线缓存“问题中采用的“Farthest-in-future”，每次置换掉的内存页都是最长时间内不会被访问或者不再被访问的页，这实际上与离线缓存所用的解决思想基本相同：

参考文献：

[1]《Introduction to Algorithms》Fourth edition

[2]Algorithm Design [ Amazon · Pearson] by Jon Kleinberg and Éva Tardos

04greedy.ppt (princeton.edu)https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms.pdf[3]王道考研操作系统ppt

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)