06-页面置换算法
一、功能与目标
功能： 当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换
目标： 尽可能地减少页面的换进换出次数（即缺页中断的次数）。具体来书，把未来不再使用的活短期内较少使用的页面换出，荣昌只能在局部性原理指导下依据过去的统计数据来进行预测
页面锁定（frame locking）：用于描述必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用进程。 实现的方法是：在页表中添加锁定标志位（lock bit）
二、实验设置与评价方法
三、局部页面置换算法
1.最优页面置换算法（OPT, optimal）
基本思路：当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之间，还需要等待多长时间，从中选择等待时间最长的哪个，作为被置换的页面
这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间以后才会再次被访问。
可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）。
2.先进先出算法 （FIFO，First-In First-Out）
基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾
性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象。FIFO算法很少单独使用
Belady现象：增加内存大小时，理论上换入换出次数应该减少，但是使用先进先出算法反而会增加换入换出次数
3.最近最久未使用算法（LRU, Least Recently Used）
基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。
它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还有可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们还可能会长时间地得不到访问。
LRU算法需要记录各个页面使用时间的先后顺序，开销比较大。两种可能的实现方法是：
- 系统维护一个页面链表，最近刚刚使用过的页面作为首节点，最久未使用的页面作为尾节点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。
- 设置一个活动页面栈，当访问某页时，将此页压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的
4.时钟页面置换算法（Clock）
Clock页面置换算法，LRU的近似，对FIFO的一种改进
基本思路：
- 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0，然后如果这个页面被访问（读/写），则把该位置为1；
- 把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）
- 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到他的下一格。
二次机会法（也叫Enhanced Clock algorithm 增强的时钟算法）：
二次机会法是时钟页面置换算法的改进，页表项中还有一个dirty bit位，表示这个页面被写过，二次机会法的核心是如果页面被写过，再给他一次机会保留
access bit 表示访问位 dirty bit表示写入位
在访问环形列表的过程中
00 直接替换该页面
01 改为00 指针往下移动
10 改为00 指针往下移动
11 改为01 指针往下移动
5.最不常用算法（LFU, Least Frequently Used）
最不常用算法（Least Frequently Used）
基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。
实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数器值最小的那个页面
LRU和LFU的区别：LRU考察的是多久未访问，时间越短越好；LFU考察的是访问的次数或频度，访问次数越多越好
LFU的问题：一个页面在进程开始时使用得很多，但以后就不使用了。实现也费时费力。
解决方法：定期把寄存器右移一位。
6.Belady现象
Belady现象：采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象
原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此，被它置换出去的页面并不一定是进程不会访问的
7.LRU,FIFO和Clock的比较
LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（有一个页面的最近访问时间变了）；而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以个页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中所有的页面都未曾访问过，那么LRU算法就退化为了FIFO算法
LRU算法性能较好，但系统开销大；FIFO算法系统开销较小，但可能会发生Belady现象。因此，折中的办法是Clock算法，在每一次页面访问时，它不必去动态地调整页面在链表当中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动
四、全局页面置换算法
工作集模型
前面介绍的各种页面置换算法，都是基于一个前提，即程序的局部性原理。但是此原理是否成立？
如果程序局部性原理不成立，那么各种页面置换算法就没有什么分别，也没有什么意义。例如：假设进程对逻辑页面的访问顺序1、2、3、4、5、6...,即单调递增，那么在物理页面数优先的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。
如果局部性原理是成立的，那么如何来证明它的存在，如何来对它进行定量地分析？这就是工作集模型！
工作集：一个进程当前正在使用的逻辑页面集合
可以用一个二元函数$W(t, △)$来表示：
- t是当前的执行时刻
- △称为工作集窗口（working-set window）,即一个定长的页面访问的时间窗口
- $W(t, △)$=在当前时刻t之前的△时间窗口当中的所有页面锁组成的集合（随着t的变化，该集合也在不断地变化）
- $|W(t, △)|$指工作集的大小，即页面数目。
工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。
常驻集是指在当前时刻，进程实际驻留在内存当中的页面集合。
工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法；
如果一个进程的整个工作集都在内存当中，即常驻集包含工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）
当进程常驻集的大小达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降
工作集页面置换算法
原理：有一个滑动时间窗口大小为t
工作集仅保存滑动时间窗口内访问的页面，将工作集内在滑动时间窗口外的访问的页面从内存中置换出去
缺页率页面置换算法
可变分配策略：常驻集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小
- 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其他进程当中，各个并发进程竞争地使用物理页面。
- 优缺点：性能较好，但增加了系统开销
- 具体实现：可以使用缺页率算法（PFF, page fault frequency）来动态调整常驻集的大小
缺页率：
缺页率表示“缺页次数、内存访问次数”比率或“缺页的平均时间间隔的倒数”。影响缺页率的因素：
- 页面置换算法
- 分配给进程的物理页面数目
- 页面本身的大小
- 程序的便携方法
缺页率算法的核心思想：
如果运行的程序的缺页率过高，则通过增加工作集来分配更多的物理页面；若运行的程序缺页率过低，则通过减少工作集来减少它的物理页面数，力图使运行的每个程序的缺页率保持在一个合理的范围内。
一个交替的工作集计算明确的视图最小化页缺失
- 当缺页率高的时候-增加工作量
- 当缺页率低的时候-减少工作量
算法：
保持追踪缺失发生概率
当缺页发生时，从上次页缺失起计算这个时间记录这个时间，t_last是上次的页缺失的时间
如果发生页缺失之间的时间是大的，之后减少工作集
如果t_current-t_last>T,之后从内存中移除所有在[t_last,t_current]时间内没有被引用的页。
如果这个发生页缺失的时间是小的，之后增加工作集
如果t_current-t_last<T, 之后增加缺失页到工作集中
五、抖动问题（thrashing）
如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集包含于工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间进行替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”
产生抖动的原因：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以OS要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡
抖动问题可能会被本地的页面置换改善
更好的规则为加载控制：调整MPL
- 平均缺页时间（mean time between page faults MTBF）=页缺失服务时间（page fault service time PFST）
- 所有进程使用内存的和=内存的大小