最近最久未使用置换算法

来自计算思维百科
跳转至: 导航搜索
最近最久未使用置换算法1.png

计算机的内存是用来存放数据的,就好像你随身会有一个背包,可以存放经常使用的东西。从背包里取东西就是从内存取数据,往背包里放东西就是向内存写数据。背包里总是想存放一些经常用的东西,可以经常用的东西比较多,背包放不下,你就要选择把一些相对不常用的东西拿出来,这种做法就是最近最久未使用置换算法的思想。最近最久未使用置换算法是计算机存储器管理中的一种算法,由于无法预测内存中各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似来淘汰页面,以换取足够的内存空间。

基本概念

最近最久未使用,是利用“最近的过去”作为“最近的将来”的近似来淘汰页面,算法赋予每一个内存中的页面一个访问字段,用来记录一个页面从上次被访问以来所经历的时间t,这个时间越长,表示越久没有使用,当需要选择淘汰一个页面时,就选择t值最大的淘汰。

应用范围

最近最久未使用算法可应用于工作、生活中没有足够的目标存储空间的管理,例如菜单的更新、键盘的设计等

使用方法及步骤

  1. 设置一个表格记录每个存储对象从上一个访问以来所经历的时间t
  2. 如果没有足够的存储空间,需要淘汰页面,则选择t值最大的淘汰

应用案例

应用1- 小吃店菜单的更新

案例:某小吃店菜单有川香鸡柳、经典盐酥鸡、培根鸡肉卷、手抓饼、甜不辣这些小吃,为了保证菜单上的小吃能够使小吃店持续获利,小吃店可能隔一阵子就会换掉几样小吃。请问小吃店换掉哪些小吃,要怎么操作做才能找到最应该被替换掉的小吃?

解决步骤:

  1. 从小吃菜单上菜单开始售卖起,记录每样小吃被成功点单的次数为n;
  2. 找到n值最小的,把它从菜单上撤下来,换上新的流行小吃。

在这个案例中,小吃店能提供的菜有限,这就是内存空间有限,哪些菜能出现在菜单上,就是哪些数据能放在内存中。在对这些菜的选择上,就根据点菜的次数,这时,点菜的次数就记录了最近最久未用的时间,点菜越多,这个时间越少,这样就可以确定哪些菜经常下单,这些菜就可以保留在菜单上。

应用2-电脑键盘的设计

案例:用过电脑键盘的人都知道,键盘上的26个字母不是按照字母表的顺序来设计顺序的,而是QWERTYUIOP ASDFGHJKL ZXCVBNM 这样的排列顺序,这是因为当初人们在使用过程中,发现有些字母的使用频率比另一些字母的使用频率高,而离手越近,输入的速度越快,于是使用频率越高的字母越在中间,使用频率越低的字母越在离手远的地方。如图:

最近最久未使用置换算法2.png

在这个案例中,键盘就是内存,可以提供的位置有限,这些按键可以理解为内存中的数据,按键的摆放位置根据使用的频率决定,越频繁使用的放在离手越近的地方,远处的按键可以理解为最久未使用的数据。

可以体现的计算思维

最近最久未使用算法利用“最近的过去”作为“最近的将来”的近似来淘汰页面,换取足够的内存空间,提高了空间利用率,体现了计算思维的优化特点。