调度算法-内存页面置换算法

页面置换算法作用是什么？

缺页中断

缺页中断和普通中断区别

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

缺页中断处理流程

1. 当CPU执行一条load M指令的时候，CPU会去找M所对应的页表项；
2. 如果页表项的状态位时有效的，CPU可以直接去访问物理内存，如果状态位是无效的，CPU会发送缺页中断请求；
3. 操作系统收到缺页中断请求后，执行缺页中断处理程序，先查找该页面在磁盘中的页面的位置；
4. 找到磁盘中对应的页面后，把该页面换入到物理内存中，但是在换入之前需要在物理内存中找到空闲页
   • 如果找到空闲页，就把页面换入物理内存；
   • 如果没有找到空闲页，需要页面置换算法选择一个物理页，将其换出到磁盘，然后把正在访问的页面装入这个物理页；
5. 页面从磁盘换入到物理内存完成之后，把页表项中的状态位修改为有效的；
6. 最后，CPU重新执行导致缺页异常的指令；

页表项组成

页号+物理页号+状态位+访问字段+修改位+硬盘地址

• 状态位：用于表示该页是否有效，即是否在物理内存中；
• 访问字段：用于记录该页在一段时间内被访问的次数，用于页面置换算法参考；
• 修改位：记录该页是否被修改过，如果修改过置换时需要将其先写入磁盘，如果没有被修改过，可以直接将其替换掉；
• 硬盘地址：用于指出该页在硬盘上的地址，同行是物理块号；

页面置换算法

页面置换算法的功能是，当出现缺页异常的时候，需要调入新页面，但是当内存已满时，选择被置换的物理页面，即选哪个物理页面置换出去；

• 最佳页面置换算法
• 先进先出置换算法
• 最近最久未使用的置换算法
• 时钟页面置换算法
• 最不常用置换算法

最佳页面置换算法

置换掉在未来最长时间不访问的页面，比如一个页面假如我们知道它在未来很长一段时间都不会被访问到了，那就直接把它置换掉；

但现实是，我们很难预测一个页面在之后多久会被使用，多久不会被使用，因为程序访问页面是动态的；

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

最近最久未使用置换算法

选择最长时间没有被访问的页面进行置换（LRU），缺点是开销比较大，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的在表尾；每次访问内存时都需要更新整个链表，在链表中找到一个页面，删除它，然后把它移动到表头，非常耗时。