页面置换算法
1. 总述
为提高内存利用率, 解决内存供不应求的问题, 更加合理的使用内存, 人们创造了分页式内存抽象. 同时有一个虚拟内存的概念, 是指将内存中暂时不需要的部分写入硬盘, 看上去硬盘扩展了内存的容量, 所以叫做 "虚拟" 内存. 使用虚拟内存, 应用程序可以使用比实际物理内存更大的内存空间. 可以认为这个更大的内存空间就在硬盘上, 只有将某一部分需要被用到时, 才被写入真实内存; 当它暂时不再被用到时, 又被写回硬盘. 分页式内存管理将物理内存分为等大的小块, 每块大小通常为 1K,2K,4K 等, 称为页帧; 逻辑内存 (使用虚拟内存技术扩大的内存, 可认为其位于硬盘上) 也被分为等大的小块, 称为页; 且页和页帧的大小一定是一样的, 它是写入真实内存和写回硬盘最小单位.
介绍另外几个概念:
使用位: 每个页帧都有一个使用位, 记录此页帧是否被使用.
修改位(脏位): 每个页帧都有一个脏位, 记录此页帧是否被更改. 调出真实内存时, 被更改过的页帧要写回硬盘, 未被更改过的页帧直接扔掉即可, 因为硬盘上此页帧的副本仍然有效.
逻辑地址: 使用虚拟内存技术扩大后的内存的地址.
物理地址: 真实内存的地址.
当然, 进程载入到真实内存才可以运行, 而进程代码使用的是逻辑地址, 所以牵扯到一个地址转换的问题, 将逻辑地址转换为物理地址. 逻辑地址可分为两段, 前半段代表页号, 后半段代表页内偏移, 物理地址也可分为两段, 前半段代表页帧号, 后半段代表页内偏移. 地址转换的方法即, 将逻辑地址的页号对应为物理地址的页帧号(对应关系记录在一张表中, 比如页号为 5, 对应到真实内存中页帧号为 3), 页内偏移不同变化(页和页帧的大小是一样的).
2. 介绍页面置换算法
假设某一时刻内存页帧已经被写满了, 但这时又需要将一个页写到物理内存中, 就需要将原本在物理内存中的某一页换出来. 如果置换不当, 就会导致刚刚被换出到硬盘的页又要被写回内存, 减慢系统运行的速度. 页面置换算法就是考虑将哪一页换出来以获得优良性能的方法.
2.1 Optimal 算法(最优算法)
首先介绍最优算法, 它需要知道以后要被用到的页, 然后将不会被用到的页换出内存; 如果所有页都会被用到, 就把需要使用时间离现在最长的页换出, 以尽量使不好的情况晚发生. 这种方法能使系统获得最佳性能, 但是, 它是不可能实现的...... 因为当前无法获知以后哪些页要被用到. 不过最优算法还是能够作为其他算法优秀程度的衡量.
2.2 FIFO(First-In First-Out, 先进先出)算法
FIFO 算法的思想很简单, 就是置换出当前已经待在内存里时间最长的那个页. FIFO 算法的运行速度很快, 不需要考虑其他的因素, 需要的开销很少. 但是正是由于没有考虑页面的重要性的问题, FIFO 算法很容易将重要的页换出内存.
2.3 Second Chance(第二次机会)算法
为了避免 FIFO 算法将重要的页换出内存, Second Chance 算法提供了一些改进. Second Chance 算法在将页面换出内存前检查其使用位(使用位前文有介绍), 如果其使用位为 1, 证明此页最近有被使用, 猜测它还可能被使用, 于是不把它置换出内存, 但是把其使用位置为 0, 随后检查下一个页面, 直到发现某页的使用位为 0, 将此页置换出内存.
2.4 Clock 算法(时钟轮转法)
为了节约 Second Chance 算法一个接着一个检查使用位的开销, 时钟轮转法又提出了改进. 时钟轮转法将所有的页组成一个圆, 圆心的指针指向下一个要被置换的页面, 置换前同样检查使用位, 如果使用位为 1, 同样将其使用位置为 0, 随后将顺指针旋转, 检查下一个页面, 直到发现某页的使用位为 0, 将此页置换出内存. 很容易理解此算法为什么叫 "时钟" 轮转法.
图示:
此时 2 号页是下一个要被置换出内存的页, 置换时如果发现其使用位为 1, 则将使用位置 0 后顺时针旋转指针检查 1 号页.
2.5 LRU(Least Recent Used, 最近最少使用)算法
为获得对最优算法的模拟, 提出了 LRU 算法. 由于当前时间之后需要用到哪些页无法提前获知, 于是记录当前时间之前页面的使用情况, 认为之前使用过的页面以后还会被用到. 在置换时, 将最近使用最少的页面换出内存. 此种方法的开销比较大.
2.6 NRU(Not Recent Used, 最近未使用)算法
前面提到修改位和使用位, NRU 算法利用这两个标志位将所有页帧分为 4 组:
第 0 组: 修改位和使用位都为 0;
第 1 组: 修改位为 0, 使用位为 1;
第 2 组: 修改位为 1, 使用位为 0;
第 3 组: 修改位和使用位都为 1.
NRU 算法从组数最小的一组中随机选择一个页面将其移出内存. 可能有人会发现第 2 组这种情况根本不会出现, 如果一个页帧被修改, 其修改位会被置 1, 同时它也被使用了, 其使用位也会被置 1; 即不会出现被修改但是没有被使用的情况. 真实情况是, 页帧的使用位会被定时清零, 这样第 3 组经过一次清零就会变成第 2 组. 这也符合 "最近" 未使用, 即很久以前被使用的页帧被清零了, 不在统计范围内, 只要 "最近" 没有被使用, 就很有可能被移出.
NRU 算法不是最好的, 但是它使用起来开销很小, 用较小的代价就得到了不错的效果, 不失为一种不错的算法.
操作系统原理(二)-- 内存管理之页面置换算法
来源: http://www.bubuko.com/infodetail-3070530.html