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

2024-01-20 10:20

本文主要是介绍大数据算法课程笔记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 次请求ri造成了一次page fault,对于cache中的每个元素 cj ,定义 fj=argmink{rk==cjk>i} ,则选择cache中的第 j=argmaxkfk 个元素 cj 进行替换。

例子

request|cache elements|page fault|evicted item|
a-,-,-True-
ba,-,-True-
ca,b,-True-
da,b,cTruec
aa,b,dFalse
ea,b,dTrued
ba,b,eFalse
aa,b,eFalse
ca,b,eTruea
ec,b,eFalse
dc,b,eTruec
bd,b,eFalse

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,我们需要证明 #fetches(SFF)#fetches(S) 。所谓schedule,记录了算法的所有操作,例如insert a、evict b,通常一个page fault对应于一对insert和evict。 schedule 的一个子集是reduced schedule,即lazy schedule,只有当request某元素的时候才会insert该元素。一个事实是:对于任意schedule S , 永远存在一个reduced schedule S,满足 #fetches(S)#fetches(S)

reducedbiji

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

目标 S,#fetches(SFF)#fetches(S) ,即对于所有可以满足request的reduced schedule S ,均满足硬盘读取数不小于SFF的读取数。

归纳法的假设 Sj , such that Sj makes the same decisions as SFF for requests from r1 to rj , and #fetches(Sj)#fetches(S) .

Base Case: 令 S0=S , 则有 #fetches(S0)#fetches(S) ,并且 S0=SFF for requests from r1 to r0 (NULL)

假设存在 Sk 满足 Sk makes the same decisions as SFF for requests from r1 to rk , and #fetches(Sk)#fetches(S) .

我们从 Sk 构造 Sk+1 ,使得 Sk+1 makes the same decisions as SFF for requests from r1 to rk+1 , and #fetches(Sk+1)#fetches(S) . 方法如下:

  1. rk+1 in cache,则 Sk SFF 均不会进行任何操作(SFF基于FIF算法, Sk 基于reduced),所以 Sk+1=Sk
  2. rk+1 misses, and Sk and SFF evict the same element, 则有 Sk rk+1 处的决策和 SFF 一致,所以 Sk+1=Sk
  3. rk+1 misses, and Sk and SFF evict different elements, suppose Sk evicts ci and SFF evicts cj . 即两者分别替换的不同元素,从而有两个元素 ci,cj 参与讨论,而对于两个元素分别有request以及evict两种可能操作。我们对 rk+1 之后 Sk 首次涉及 ci,cj 的操作进行分情况讨论:
    1. Next there is a request rd to ck , and Sk evicts cj , 即 Sk 需要替换 cj 了。调换两者的删除位置,使得 Sk+1 在第 rk+1 处与 SFF 一样删除 cj ,而在 rd 处删除 ck ,同样满足请求序列,并且 #fetches(Sk+1)=#fetches(Sk)#fetches(SFF)
    2. Next, there is a request rd to ci , and Sk evicts cj . 即 Sk 删除 ci 之后,在请求序列里又遇到了 ci ,而且这次删除了 cj 。我们使得 Sk+1 rk+1 处删除 cj ,而在 rd 处即不需要进行任何操作,同样满足请求序列,并且 #fetches(Sk+1)=#fetches(Sk)1>#fetches(SFF)
    3. Next, there is a request rd to ci and Sk evicts c . 即 Sk 删除 ci 之后,在请求序列里又遇到了 ci ,这次删除了一个非 cj 的元素。注意到此次构造 Sk+1 需要满足 cj 不被删除、所以我们同样使得 Sk+1 在第 rk+1 处与 SFF 一样删除 cj ,而在 rd 处与 Sk 一样删除 c ,而插入 cj 。这样构造的 Sk+1 不是reduced,需要基于上诉Fact转化为reduced schedule Sk+1 ,并且满足 Sk+1 makes the same decisions as SFF for requests from r1 to rk+1 , and #fetches(Sk+1)#fetches(Sk+1)=#fetches(Sk)#fetches(S) .
    4. Next, there is a request to cj , which is not possible, since fj>fi .

综上,基于归纳原则,我们证明了 Sn , such that Sn makes the same decisions as SFF for requests from r1 to rn , 从而 Sn=SFF 而且 #fetches(SFF)=#fetches(Sn)#fetches(S) .

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

3. Non-Clairvayant/Online algorithm

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

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

3.1. 评价函数 Metric

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

使用 Cost(A,z)OPT(z) 评价算法 A 在给定z上的表现,进而有最差情况 maxzCost(A,z)OPT(z) (competitve ratio)以及平均情况 zuCost(A,z)OPT(z)

3.2. least recently used algorithm (LRU)

算法简介:如名字所述,每次选择最不近使用的元素进行替换。具体地,设第 i 次请求ri造成了一次page fault,对于cache中的每个元素 cj ,定义 lj=argmaxk{rk==cjk<i} ,则选择cache中的第 j=argminklk 个元素 cj 进行替换。

例子

request|cache elements|page fault|evicted item|
a-,-,-True-
ba,-,-True-
ca,b,-True-
da,b,cTruea
ad,b,cTrueb
ed,a,cTruec
bd,a,eTrued
ab,a,eFalse
cb,a,eTruee
eb,a,cTrueb
de,a,cTruea
be,d,cTruec

性能分析

lru

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

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

所以LRU的competitive ratio k ,其中 k 为cache size。

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

Claim:对于所有determinisitic online page replacement algorithm A, z,Cost(A,z)OPT(z)=k

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

这篇关于大数据算法课程笔记8a:page replacement algorithm的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/625682

相关文章

大数据spark3.5安装部署之local模式详解

《大数据spark3.5安装部署之local模式详解》本文介绍了如何在本地模式下安装和配置Spark,并展示了如何使用SparkShell进行基本的数据处理操作,同时,还介绍了如何通过Spark-su... 目录下载上传解压配置jdk解压配置环境变量启动查看交互操作命令行提交应用spark,一个数据处理框架

通过ibd文件恢复MySql数据的操作方法

《通过ibd文件恢复MySql数据的操作方法》文章介绍通过.ibd文件恢复MySQL数据的过程,包括知道表结构和不知道表结构两种情况,对于知道表结构的情况,可以直接将.ibd文件复制到新的数据库目录并... 目录第一种情况:知道表结构第二种情况:不知道表结构总结今天干了一件大事,安装1Panel导致原来服务

Jmeter如何向数据库批量插入数据

《Jmeter如何向数据库批量插入数据》:本文主要介绍Jmeter如何向数据库批量插入数据方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Jmeter向数据库批量插入数据Jmeter向mysql数据库中插入数据的入门操作接下来做一下各个元件的配置总结Jmete

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL InnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据

《MySQLInnoDB引擎ibdata文件损坏/删除后使用frm和ibd文件恢复数据》mysql的ibdata文件被误删、被恶意修改,没有从库和备份数据的情况下的数据恢复,不能保证数据库所有表数据... 参考:mysql Innodb表空间卸载、迁移、装载的使用方法注意!此方法只适用于innodb_fi

mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据

《mysql通过frm和ibd文件恢复表_mysql5.7根据.frm和.ibd文件恢复表结构和数据》文章主要介绍了如何从.frm和.ibd文件恢复MySQLInnoDB表结构和数据,需要的朋友可以参... 目录一、恢复表结构二、恢复表数据补充方法一、恢复表结构(从 .frm 文件)方法 1:使用 mysq

mysql8.0无备份通过idb文件恢复数据的方法、idb文件修复和tablespace id不一致处理

《mysql8.0无备份通过idb文件恢复数据的方法、idb文件修复和tablespaceid不一致处理》文章描述了公司服务器断电后数据库故障的过程,作者通过查看错误日志、重新初始化数据目录、恢复备... 周末突然接到一位一年多没联系的妹妹打来电话,“刘哥,快来救救我”,我脑海瞬间冒出妙瓦底,电信火苲马扁.

golang获取prometheus数据(prometheus/client_golang包)

《golang获取prometheus数据(prometheus/client_golang包)》本文主要介绍了使用Go语言的prometheus/client_golang包来获取Prometheu... 目录1. 创建链接1.1 语法1.2 完整示例2. 简单查询2.1 语法2.2 完整示例3. 范围值

javaScript在表单提交时获取表单数据的示例代码

《javaScript在表单提交时获取表单数据的示例代码》本文介绍了五种在JavaScript中获取表单数据的方法:使用FormData对象、手动提取表单数据、使用querySelector获取单个字... 方法 1:使用 FormData 对象FormData 是一个方便的内置对象,用于获取表单中的键值

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为