当物理内存满了，就需要「页面置换算法」选择一个物理页。

当产生缺页中断后，由操作系统进行处理，此时判断内存是否有空闲块

  • 如果有，直接装入
  • 如果没有，根据页面置换算法决定淘汰替换哪些页

常见的页面置换算法有如下几种：

  • 最佳页面置换算法（OPT）:置换在「未来」最长时间不访问的页面。(但是只有在进程执行过程中才知道接下来会访问哪个页面，而操作系统是无法提前预判页面访问序列的，所以这是个理想化的算法)
  • 先进先出置换算法（FIFO）：选择在内存驻留时间很长的页面进行中置换，该算法性能差
  • 最近最久未使用的置换算法（LRU）：选择最近最久时间没有被访问的页面进行置换，该算法性能好，但是实现困难
  • 最不常用置换算法（LFU）：当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰
  • 时钟页面置换算法（cLock）：时钟页面置换算法就可以两者兼得，它跟 LRU 近似，又是对 FIFO 的一种改进。

时钟页面置换算法

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

  1. 如果它的访问位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；
  2. 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；
  3. 未改进的时钟置换算法最多经过两轮扫描找到淘汰页面


改进型的时钟置换算法：

  • 除了考虑页面有没有被访问过之外，还需考虑是否被修改过，在其他条件都相同时，优先淘汰没被修改的页面，这可以避免IO操作
  • 改进后的时钟置换算法最多经过四轮扫描找到淘汰页面

页面分配策略