简述

​ 再聊今天的页面置换算法前,我们首先要考虑一个问题,什么情况下,才会出现页面换,自然是在发生缺页中断的时候。因为我们现代操作系统,通常是采用虚拟内存进行内存管理,当我们所访问的逻辑地址在页表或段表中找不到对应的物理地址时,就会发生缺页中断,请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于:

  • 缺页中断在指令执行「期间」产生和处理中断信号,而一般中断在一条指令执行「完成」后检查和处理中断信号。
  • 缺页中断返回到该指令的开始重新执行「该指令」,而一般中断返回回到该指令的「下一个指令」执行。

image-20210322191758932

流程简述

  1. 在 CPU 里访问一条 Load M 指令,然后 CPU 会去找 M 所对应的页表项。
  2. 如果该页表项的状态位是「有效的」,那 CPU 就可以直接去访问物理内存了,如果状态位是「无效的」,则 CPU 则会发送缺页中断请求。
  3. 操作系统收到了缺页中断,则会执行缺页中断处理函数,先会查找该页面在磁盘中的页面的位置。
  4. 找到磁盘中对应的页面后,需要把该页面换入到物理内存中,但是在换入前,需要在物理内存中找空闲页,如果找到空闲页,就把页面换入到物理内存中。
  5. 页面从磁盘换入到物理内存完成后,则把页表项中的状态位修改为「有效的」。
  6. 最后,CPU 重新执行导致缺页异常的指令。

上面所说的过程,第 4 步是能在物理内存找到空闲页的情况,那如果找不到呢?

找不到空闲页的话,就说明此时内存已满了,这时候,就需要「页面置换算法」选择一个物理页,如果该物理页有被修改过(脏页),则把它换出到磁盘,然后把该被置换出去的页表项的状态改成「无效的」,最后把正在访问的页面装入到这个物理页中。

虚拟内存,地址映射过程

image-20210322191758932

页面置换算法的功能

当出现缺页异常,需调入新页面而内存已满时,选择被置换的物理页面,也就是说选择一个物理页面换出到磁盘,然后把需要访问的页面换入到物理页。

最佳页面置换算法(OPT)

​ 最佳页面置换算法基本思路是,置换在「未来」最长时间不访问的页面

​ 所以,该算法实现需要计算内存中每个逻辑页面的「下一次」访问时间,然后比较,选择未来最长时间不访问的页面。

​ 这很理想,但是实际系统中无法实现,因为程序访问页面时是动态的,我们是无法预知每个页面在「下一次」访问前的等待时间。

​ 所以,最佳页面置换算法作用是为了衡量你的算法的效率,你的算法效率越接近该算法的效率,那么说明你的算法是高效的。

先进先出置换算法

​ 既然我们无法预知页面在下一次访问前所需的等待时间,那我们可以选择在内存驻留时间很长的页面进行中置换,这个就是「先进先出置换」算法的思想。

最近最久未使用的置换算法

最近最久未使用(LRU)的置换算法的基本思路是,发生缺页时,选择最长时间没有被访问的页面进行置换,也就是说,该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

这种算法近似最优置换算法,最优置换算法是通过「未来」的使用情况来推测要淘汰的页面,而 LRU 则是通过「历史」的使用情况来推测要淘汰的页面。

虽然 LRU 在理论上是可以实现的,但代价很高。为了完全实现 LRU,需要在内存中维护一个所有页面的链表,最近最多使用的页面在表头,最近最少使用的页面在表尾。

困难的是,在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常费时的操作。

所以,LRU 虽然看上去不错,但是由于开销比较大,实际应用中比较少使用。

时钟页面置换算法

时钟页面置换算法就可以两者兼得,它跟 LRU 近似,又是对 FIFO 的一种改进。

该算法的思路是,把所有的页面都保存在一个类似钟面的「环形链表」中,一个表针指向最老的页面。

当发生缺页中断时,算法首先检查表针指向的页面:

  • 如果它的访问位位是 0 就淘汰该页面,并把新的页面插入这个位置,然后把表针前移一个位置;
  • 如果访问位是 1 就清除访问位,并把表针前移一个位置,重复这个过程直到找到了一个访问位为 0 的页面为止;

image-20210322193045641

image-20210322193125919