1. 内存页面置换算法⚓

1.1 缺页中断⚓

当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断(缺页异常)，请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于：

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

页表项通常有如下图的字段：

状态位，表示该页是否有效，即是否在物理内存中，供程序访问时参考
访问字段，记录该页在一段时间内被访问的次数，供页面置换算法选择出页时参考
修改位，表示该页在调入内存后是否有被修改过。由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，置换该页时就不需要写回到磁盘；否则将该页写回到磁盘，更新磁盘中保留的副本
硬盘地址，指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用

虚拟内存映射到物理内存流程：

置换在未来最长时间不会被访问的页面。

该算法实现需要计算内存中每个逻辑页面的「下一次」访问时间，然后比较，选择时间最长的那个页面，将其置换掉。

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

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

选择在内存驻留时间很长的页面中置换。

跟最佳页面置换算法比较起来，性能明显差了很多。

选择最长时间没有被访问的页面进行置换。

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

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

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

时钟页面置换算法跟 LRU 近似，（Clock Page Replacement Algorithm），也称为最近未使用（NRU）算法，又是对 FIFO 的一种改进。

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

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

时钟页面置换算法简单且高效，它解决了"FIFO"（先进先出）页面置换算法导致的不公平问题，因为它考虑了页面是否被访问过的情况。

选择「访问次数」最少的那个页面，并将其淘汰。

它的实现方式是，对每个页面设置一个「访问计数器」，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。

要增加一个计数器来实现，硬件成本是比较高，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。

还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。

这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。