什么是页面置换算法-创新互联

这篇文章主要为大家展示了什么是页面置换算法，内容简而易懂，希望大家可以学习一下，学习完之后肯定会有收获的，下面让小编带大家一起来看看吧。

页面置换算法：本质是为了让有限内存能满足无线进程。

先说明一下处理缺页错误的过程：

分页硬件在通过页表转换地址时会注意到无效位被设置，从而陷入操作系统，这种陷阱是因为操作系统未能将所需要的页面调入内存引起的。

处理缺页错误：

1、检查这个进程的内部表，确定该引用是否为有效的内存访问（可以理解为这个内存能被当前进程使用），如果无效那么直接终止进程；如果有效但是尚未调入页面，就将该页面调入内存。

2、然后从空闲帧链表上找到一个空闲帧。

3、调度磁盘将进程所需要的内存读入页帧中，

4、磁盘读取完成，修改页表，使空闲帧对应到该页号上。并且修改页表有效-无效位 为有效。

注意页表中的一些标志位：

修改位：如果有效为位1，表明被修改，那么替换页面时需要将内存写入磁盘中；如果为0，表明未被修改，那么使用页面替换算法直接释放

保护位：可以标记为只读，写。

有效-无效位：i：表示逻辑页号不对应物理页帧，为V表示有对应的物理页帧

页面替换算法：

FIFO:算法

操作系统总时替换出在内存中停留时间最久的页面，可以用一个指针来指向这个位置（开销很小，可以使用一个队列来实现，每次缺页时移出末尾的页面，再队列头添加新的页面，未发生缺页错误就不需要对队列进行操作）

LRU算法：操作系统总时替换在内存中最久没有使用的页面：我么可以使用链表来实现这个算法，表头表示的是最近被使用的页面，表尾表示最久没被使用的页面，每一次不管是否发生缺页，都需要对这个链表进行从新增删改查，来保证每一次的链表都是我们需要的（开销太大）

近似LRU算法：我们在页表中添加一个引用位clock，当clock为1时，不能移出，当clock为0时，表明可以移除

procedure t: {
  指针p：指向当前的页面
  p = 0;//指向初始位置
  boolean ：标志位clock
  进程包含的所有页面组成的循环链表：linklist//当进程在运行时，链表存在，进程结束时，链表也消失
  while(进程运行){
    
    if(p.clock == 1){
      p.clock = 0;
      p++;//指针指向下一个
    }
    if(p.clock == 0){
      删除p指向的页面并且在p处添加新的页面；
      p.clock = 1;
      p++;
    }
  }
}