内存页面置换

什么是缺页中断？

CPU在访问的页面不在物理内存时，便会产生缺页中断，请求操作系统将所缺页调入到物理内存。

缺页中断与其他中断的区别？

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

缺页中断的处理流程

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

页面置换算法用来做什么？

页面置换算法就是在物理内存无法找到空闲页的时候，将现有物理内存中合适的页换出到磁盘，然后把需要访问的页面装入到物理内中。页面算法的目标是尽可能的减少页面的换入和换出次数。

页面置换算法有哪几种？

• 最佳页面置换算法（OPT）
• 先进先出置换算法（FIFO）
• 最近最久未使用的置换算法（LRU）
• 时钟页面置换算法（LOCK）
• 最不常用置换算法（LFU）

页面置换算法核心是置换在未来最长时间不访问的页面。

这种算法是最理想的算法，但是无法实现，因为程序在访问页面是动态，我们无法预知每个页面下一次的访问时间。因此该算法只是为了衡量其他的页面置换算法的效率，如果算法效率越接近该算法的效率，说明算法越高效。

先进先出置换算法是选择在内存驻留时间很长的页面进行置换。

该算法的核心是选择最长时间没有被访问的页面进行置换。

为了实现这种LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少的在表尾，每次访问内存时都需要更新该链表，需要在链表中找到一个页面，删除它，然后把它移动到表头是一个比较耗时的操作。

时钟页面置换算法结合了LRU和FIFO，该算法把所有的页面保存在一个环形列表中，一个表指针指向最老的页面。

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

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

该算法就是选择访问次数最少的那个页面将其淘汰。

实现方式就是对每个页面增设一个访问计数器，每当一个页面被访问时，该页面的访问计数器就加1。