功能与目标
功能：当缺页中断发生，需要调入新的页面，但是此时内存已满，需要选择内存中哪个物理页面被置换
目标：尽可能的减少页面的换进换出次数（即缺页中断的次数）。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测
页面锁定（frame locking）：用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用进程。实现的方法：在页表中添加锁定标志位（lock bit）
实验设置与评价方法
记录一个进程对页访问的一个轨迹
举例：（虚拟）地址跟踪 (页号，位移)
(3,0), (1,9), (4,1), (2,1), (5,3), (2,0), (1,9), (2,4), (3,1), (4,8)
第三个页面的第0个offset
生成页面轨迹
3, 1, 4, 2, 5, 2, 1, 2, 3, 4（替换如c ,a, d, b, e, b, a, b, c, d）
模拟一个页面置换的行为并且记录产生页缺失数的数量
更少的缺失，更好的性能
局部页面置换算法
最优页面置换算法（OPT，optimal）
基本思路：当一个缺页中断产生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面
这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会再次被访问
可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）
Time：时间轴（1,2,3,4,5,6）
Requests：访问页（a,b,c,d,e）
比如上图，在1时刻访问的是c页，在2时刻访问的是a页
Page Frames（页帧）：当前操作系统给该程序分配了4个物理页帧
虽然总共分配了4个物理页帧，但是需要访问的页有5个，这种情况就会产生物理页不够的情况，就会产生页替换
在0时刻的时候，物理页帧已经存了a,b,c,d四个逻辑页，在1,2,3,4这个四个时刻，访问c,a,d,b时，此时物理页中已经存放了a,b,c,d这四个逻辑页，所以在这四个时刻的访问不会产生缺页中断
在5时刻，需要访问e逻辑页，此时物理帧中没有，产生缺页中断，然后根据最优置换算法，置换的页面是在将来最长时间不需要的页面，a页面在第7个时刻需要访问，b在第6个时刻需要访问，c在第7个时刻需要访问，d在第10个时刻需要访问，所以d页是将来最长时间不需要访问的页面，把d给置换掉，把e页填入
先进先出算法（First-In First-Out, FIFO）
基础思路：选择在内存中驻留时间最长的页面并淘汰。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。
性能较差，调出的页面有可能是经常要访问的页面。并且有Belady现象（分配的物理页帧越多，产生缺页中断次数越多（正常情况应该越少才对））。FIFO算法很少单独使用
最近最久未使用算法（LRU，Least recently used）
基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰
它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁的访问，那么在将来的一小段时间内，它们还可能会再一次被频繁的访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问
LRU算法需要记录各个页面使用时间的先后顺序，开销较大，两种可能的实现方法：
1.系统维护一个页面链表，最近刚刚使用过的页面作为首节点，最久未使用的页面作为尾节点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面
2.设置一个活动页面栈，当访问某页时，将此页压入栈顶，然后考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的
时钟页面置换算法（Clock）
LRU的近似，对FIFO的一种改进
基本思路：
1.需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写），则把该位置为1
2.把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）
3.当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针下移一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格
维持一个环形页面链表保存在内存中
1.用一个时钟（或者使用/引用）位来标记一个页面是否经常被访问
2.当一个页面被引用的时候，这个位被置为1
时钟头扫遍页面寻找一个带有used bit=0
1.替换在一个周转内没有被引用过的页面
如图，总共有5个物理页帧，有8个虚拟页，目前7,4,9,3,1这五个虚拟页是放到物理内存中的
最左边的一位是代表是否存在于物理内存中，如果置1表示存在于物理内存中，虚拟页和物理页映射关系是正常的
第二位是代表该页是否被访问过，如果置为1表示该页被访问过
第三位是代表该虚拟页对应的物理页号
如果发生了缺页中断，需要调度新的页面进来，但是物理页面只有5个，所以需要置换，从当前指针指向的页目录项开始寻找，当前指针指向的是逻辑页为0的页面，首先查看它的used bit，发现它为1，代表它最近被访问过，此时需要先把该页的Used bit清零，然后指针顺时针向下挪一格，然后依次往复，直到指针移到虚拟页1，它的used bit为0，该页就会被替换出去，然后指针再顺时针向下挪一格
如果没有发生缺页中断，那指针位置不动，只是把当前访问的页的used bit置为1
这里有一个巨大的代价来替换“脏”页
修改clock算法，使它允许脏页总是在一次时钟头扫描中保留下来
1.同时使用脏位和使用位来指导置换（dirty bit脏位表示写位，只有该页被写的时候才会置1，如果该页仅是被读，该页不会被置1，但是不管读写，used bit都会被置1）
二次机会法
如果某一页被从硬盘置换到内存中之后，程序只是对该页进行读操作，并没有写操作，那此时内存中的页和硬盘上的内容是相同的，那在发生置换的时候就不需要再把该页写回到硬盘中，直接把该页释放即可，因为内容是一样的
如果某一页被程序写过，那内存中的数据和硬盘中的数据不一致，如果发生置换时，必须把内存中的数据写回到硬盘中
如果可以通过dirty bit来判断该页是否被写过，来减少写硬盘的次数
置换原则：
1.如果dirty bit和used bit都为0，那么就会被立即替换出去
2.如果used bit为0，dirty bit为1，则把dirty bit置为0，同时把指针顺时针下移一格
3.如果used bit为1，dirty bit为0，则把used bit置为0，同时把指针顺时针下移一格
4.如果used bit为1，dirty bit也为1，则把used bit置为0，dirty bit不变，同时把指针顺时针下移一格
最不常用算法（LFU，Least Frequently Uesed）
基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰
实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数值最小的那个页面
LRU和LFU的区别：LRU考察的是多久未访问，时间越短越好；而LFU考察的是访问的次数或频度，访问次数越多越好
Belady现象
LRU、FIFO和Clock的比较
全局页面置换算法
工作模型
工作集页面置换算法
缺页率置换算法
原文：https://www.cnblogs.com/xyz2b/p/10544352.html