最佳置换算法

来自计算思维百科
跳转至: 导航搜索
最佳置换算法.png

计算机的内存是用来存放数据的,就好像你随身会有一个背包,可以存放经常使用的东西。从背包里取东西就是从内存取数据,往背包里放东西就是向内存写数据。为了保证背包中总是存放一些经常用的东西,就要把背包中长时间不用的东西拿出来,把常用的东西放进去,这种做法就是最佳置换算法的思想。最佳页面置换算法是Belady于1966年提出的一种理论上的算法,是计算机存储器管理中保证最少的缺页率的理想化算法。

基本概念

最佳置换算法,是计算机操作系统存储器管理中的一种方法。这个算法的思想就是把一些不常用的数据淘汰掉,这个淘汰是怎么完成的?其实很简单,就是把新的数据替换进来就行了。那么每次可以把多少不用的数据取出来,这个需要一个大小度量,在内存中,这个大小就是页。页,是程序和数据存储的基本单位,对应同等大小的物理内存块。缺页,就是缺少所需的程序和数据。

被淘汰页面一般都是以后都不再访问或者未来很长时间内不再访问的页面,然后将新页面移进内存中,这样通常可以保证最低的缺页率。

应用范围

最佳置换算法可应用于生活、学习和工作中有限空间内物品的选择管理,如书桌放置物品的选择、衣柜放置物品的选择、档案馆档案位置的选择等。

使用方法及步骤

  1. 选出以后永远不使用或未来很长一段时间都不需要使用的存储对象
  2. 将步骤1选出的存储对象移出存储空间
  3. 将最近需要的存储对象移进存储空间

应用案例

应用1- 冬天来临前衣柜冬夏衣服交换

案例:在衣柜存储空间有限的情况下,衣柜只能放置需要的衣服。根据生活经验,由于是秋季尾,在未来几个月内都不需要夏天的衣服,这时候就可以把夏天衣服拿出衣柜,把冬天的衣服放进衣柜。

在这个案例中,衣柜就是内存,衣柜中的衣服就是存放的数据,长时间不穿的衣服就是淘汰页。通过这种置换,就可以不断更新衣柜中的衣物,保证你随时都可以找到需要的衣服,而不是在一大堆不会穿的衣服中浪费时间。

应用2- 书桌物品的选择整理

案例:书桌的设计通常都是只够放几本书和作业本,为了有效地利用书桌桌面,节省频繁拿书的时间,可以选择把当前想要完成的作业需要的书、笔还有作业本放在书桌上,其他的书先放起来,等到作业写完再去拿其他需要的东西。

在这个案例中,书桌的桌面就是内存,桌面上放的书就是数据,不常用的书被拿走,就是淘汰的页面被置换。这样可以保证你很容易找到想用的书。

可以体现的计算思维

最佳置换算法将未来很长时间或永远不会使用到的存储对象移出存储空间,提高了存储空间的利用率,体现了计算思维的优化思想。