三网合一网站模板,京东的网站建设分析,企业宣传标语,石家庄网站系统建设在了解内存页面置换算法前#xff0c;我们得先了解 缺页异常#xff08;缺页中断#xff09;。
当 CPU 访问的页面不在物理内存中时#xff0c;便会产生一个缺页中断#xff0c;请求操作系统将缺页调入到物理内存。那它与一般的中断主要区别在于:
缺页中断在指令执行 [期…在了解内存页面置换算法前我们得先了解 缺页异常缺页中断。
当 CPU 访问的页面不在物理内存中时便会产生一个缺页中断请求操作系统将缺页调入到物理内存。那它与一般的中断主要区别在于:
缺页中断在指令执行 [期间] 产生和处理中断信号而一般中断在一条指令执行 [完成后] 检查和处理中断信号。缺页中断返回到 [该指令] 的开始重新执行该指令而一般中断返回回到该指令的 [下一个指令] 执行
完整的缺页中断处理流程如下图 在 CPU 里访问一条 Load M 指令然后 CPU 会去找 M 所对应的页表项如果该页表项的状态位是 [有效的] ,那 CPU 就可以直接去访问物理内存了如果状态位是 [无效的] 那 CPU 则会发送缺页中断请求操作系统收到了缺页中断则会执行缺页中断处理函数先会查找该页面在磁盘中的页面的位置找到磁盘中对应的页面后需要把该页面换入到物理内存中但是在换入前需要在物理内存中找空闲页就把页面换入到物理内存中页面从磁盘换入到物理内存完成后则把页面表项中的状态位修改为 [有效的]最后 CPU 重新执行导致缺页异常的指令。
上面说的过程第四步是能在物理内存找到空闲页的情况下。如果找不到空闲页的话
如果找不到空闲页就说明此时内存已经满了这时候就需要 [页面置换算法] 选择一个物理页如果该物理页有被修改过脏页则把它换出到磁盘然后把该被置换出去的页表项的状态改成 [无效的] 最后把正在访问的页面装入到这个物理页中。
页表项通常有以下字段 其中
状态位用于表示该页是否有效也就是说是否在物理内存中供程序访问时参考访问字段用于记录该页在一段时间被访问的次数供页面置换算法选择出页面时参考修改位表示该页在调入内存后是否有被修改过由于内存中的每一页都在磁盘上保留一份副本因此如果没有被修改在置换该页时就不需要将该页写回到磁盘上以减少系统的开销如果已经被修改则将该页重写到磁盘上以保证此案中所保留的始终是最新的副本硬盘地址用于指出该页在硬盘上的地址通常是物理块号供调入该页时使用
虚拟内存的管理整个流程 所以页面置换算法的功能是当出现缺页异常需调入新页面而内存已满时选择被置换的物理页面也就是说选择一个物理页面换出到磁盘然后把需要访问的页面换入到物理页。
那其算法目标则是尽可能减少页面的换入换出的次数常见的页面置换算法有如下几种
最佳页面置换算法OPT先进先出置换算法FIFO最近最久未使用的置换算法LRU时钟页面置换算法Lock最不常用置换算法LFU 最佳页面置换算法
最佳页面置换算法的基本思路是置换在 [未来] 最长时间内不访问的页面
所以该算法实现需要计算内存中每个逻辑页面的 [下一次] 访问时间然后比较选择未来最长时间不访问的页面。
我们举个例子假设一开始有 3 个空闲的物理页然后有请求的页面序列那它置换的过程如下图 在这个请求的页面序列中缺页共发生了 7 次空闲页换入 3 次 最优页面置换 4 次页面置换共发生了 4 次。
这很理想但是实际系统中无法实现因为程序访问页面时是动态的我们是无法预知每个页面在 [下一次] 访问前的等待时间。
所以最佳页面置换算法作用是为了衡量你的算法的效率你的算法效率越接近该算法的效率那么说明你的算法是高效的。 先进先出置换算法
既然我们无法预知页面在下一次访问前所需的等待时间那我们可以选择在内存驻留时间最长的页面中进行置换这个就是 [先进先出置换] 算法的思想。
还是以前面的请求的页面序列作为例子假设使用先进先出置换算法则过程如下 在这个请求的页面序列中缺页共发生了 10 次页面置换共发生了 7 次根最佳页面置换比较起来性能明显差了很多。 最近最久未使用的置换算法
最近最久未使用LRU的置换算法基本思路是发生缺页时选择最长时间没有被访问的页面进行置换也就是说该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
这种算法近似最优置换算法最优置换算法是通过 [未来] 的使用情况来推测要淘汰的页面而 LRU 则是通过 [历史] 的使用情况来推测要淘汰的页面。
还是以前的请求的页面序列作为例子假设使用最近最久未使用的置换算法则过程如下图 在这个请求的页面序列中缺页共发生了 9 次页面置换共发生了 6 次跟先进先出置换算法比较起来性能提高了一些。
虽然 LRU 在理论上是可以实现的但代价很高。为了完全实现 LRU 需要在内存中维护一个所有页面的链表最近最多使用的页面在表头最近最少使用的页面在表尾。
困难的是在每次访问内存的时候都必须要更新 [整个链表]。在链表中找到一个页面删除它然后把它移动到表头是一个非常耗时的操作。
所以 LRU 虽然看上去不错但是由于开销比较大实际应用中比较少使用。 时钟页面置换算法
时钟页面置换算法即能优化置换的次数又能方便地实现。它跟 LRU 近似又是对 FIFO 的一种改进。
该算法的思路是把所有的页面都保存在一个类似时钟面的 [环形链表] 中一个表针指向最老的页面。
当缺页中断时算法首先检查表针指向的页面
如果它的访问位是 0 就淘汰该页面并把新的页面插入这个位置然后把表针前移一个位置如果它访问的是 1 就清除访问位并把表针前移一个位置重复这个过程直到找到一个访问位为 0 的页面为止。 了解了这个算法的工作方式就明白为什么它被称为时钟Clock算法了 最不常用算法
最不常用LFU算法它的意思不是指这个算法不常用而是当发生缺页中断时选择 [访问次数] 最少的那个页面并将其淘汰。
实现方式对每个页面设置一个 [访问计数器] 每当一个页面被访问时该页面的访问计数器就累加 1 。发生缺页中断时淘汰计数器值最小的那个页面。
看起来很简单每个页面加一个计数器就可以实现了但是在操作系统中实现的时候我们需要考虑效率和硬件成本的。
要增加一个计数器来实现这个硬件成本是比较高的另外如果要对这个计数器查找哪个页面访问次数最小查找链表本身如果链表长度很大是非常耗时的效率不高。
还有个问题LFU 算法只考虑了频率问题没考虑时间的问题比如有些页面在过去时间里访问的频率很高但是现在已经没有访问了而当前频繁访问的页面由于没有这些页面访问的次数高在发生缺页中断时就会可能会误伤当前刚开始频繁访问但访问次数还不高的页面。
那这个问题的解决的办法还是有的可以定期减少访问的次数比如当发生时间中断时把过去时间访问的页面的访问次数除以 2也就说随着时间的流失以前的高访问次数的页面会慢慢减少相当于加大了被置换的概率。
