【OS】第六部分：页面置换算法

【OS】第六部分：页面置换算法
视频：B站清华大学 向勇、陈渝老师
链接: https://www.bilibili.com/video/BV1js411b7vg?p=11

6.1 最优页面置换算法

本部分结构以及相应算法：

(1)功能目标
功能：当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。
目标：尽可能减少页面的换入换出次数(即缺页中断的次数)。把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理的指导下依据过去的统计数据来进行预测。
页面锁定(frame locking)：用于描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法是，在页表中添加锁定标志位(lock bit)。

只考虑页就好 因为只有当一个页不存在的时候才会产生缺页中断

(2)最优页面置换算法
基本思路：当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。
不过，这只是一种理想情况，在实际中无法实现，因为操作系统无法知道每一个页面要等待多长时间以后才会被再次访问。
可用作其它算法的性能评价的依据(在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法)。


其余算法 产生的缺页中断数 逼近最优页面置换算法可以称得上是一个比较好的算法

6.2 先进先出算法

先进先出算法(First- In First-Out, FIFO) ;
基本思路:选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当
发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。
性能较差，调出的页面有可能是经常要访问的页面，并且有Belady现象。FIF0算法很少单独使用。

Belady现象是指：在分页式虚拟存储器管理中，发生缺页时的置换算法采用FIFO（先进先出）算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

6.3 最近最久未使用算法

-最近最久未使用算法(Least Recently Used, LRU) ;
-基本思路:当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。
-它是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间(最近几条指令)内，如果某些页面被频繁地访问，那么在将来的一小段时间内，它们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来它们]还可能会长时间地得不到访问。
-LRU是根据历史推测未来 最优置换算法根据未来来推测未来

Least Recent ly Used (LRU) Page Replacement
LRU算法需要记录各个页面使用时间的先后顺序，
开销比较大。两种可能的实现方法是:
-系统维护一个页面链表，最近刚刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。
-设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有 与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，它就是最久未使用的。

6.4 时钟页面置换算法

◆Clock页面置换算法，LRU的近似，对FIF0的一 种改进;
基本思路:
-需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问(读/写)， 则把该位置为1;
-把各个页面组织成环形链表(类似钟表面) ,把指针指向最老的页面(最先进来) ;
-当发生一个缺页中断时， 考察指针所指向的最老页面， 若它的访问位为0,立即淘汰;若访问位为1,则把该位置为0,然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

5个页帧 8个虚拟页
第一位 是否存在 为1 在物理内存中存在 映射关系正常
第二位 为1 当前页已被访问过（硬件给置1）
第三位 页帧号

6.5 二次机会法

区分读和写，enhanced clock algorithm
读和写都是访问，dirty bit是写位，如果写，为1，否则是0。同时使用脏位和使用位。
修改clock算法，使它允许脏页总是在一次时钟头扫描时保留下来，以减少写回硬盘的操作（仅读的页可以直接释放）
需要替换的页，其访问位和脏位都是0，如果都是 1，则有两次机会才被淘汰。从而让更多使用频率的页有更多的机会留在内存中。
较为接近LRU算法，尽量保存dirty page，更好地减少了访问外存

如果是一次写操作，dirty bit会设置为1.说明内存访问这部分数据时是有写入操作的，和硬盘上原数据不一样，所以要写入硬盘，如果是0，对这部分内存没有写操作，那么说明内存和硬盘上内容是一样的，直接丢掉即可。
目的就是减少对硬盘的写操作。
如果used和dirty bit都是0，那么替换掉；如果其中一个是1，那么把这一位设置为0，指针往下走；如果都是1，那先把used换为0，说明有2次机会。

6.6 最不常用算法

最不常用算法(Least Frequently Used, LFU) ;
基本思路:当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。
实现方法:对每个页面设置一个访问计数器， 每当一个页面被访问时，该页面的访问计数器加1。 在发生缺页中断时，淘汰计数值最小的那个页面。
LRU和LFU的区别: LRU考察的是多久未访问，时间越短越好;而LFU考察的是访问的次数或频度，访问次数越多越好。
反例：一个页面在进程开始时使用的很多，但以后就不使用了。此时LFU就不适用了。
缺点：初始化时访问次数多，而正常时访问次数少的帧。
问题:一个页面在进程开始时使用得很多，但以后就不使用了。实现也费时费力。
解决方法:定期把次数寄存器右移一位。

6.7 Belady现象，LRU，FIFO，Clock的比较

◆Belady现象: 在采用FIF0算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象;
Belady现象的原因: FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的(即替换较少使用的页面)，因此，被它置换出去的页面并不一定是进程不会访问的。



LRU、FIF0和Clock的比较
LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序(有一个页面的最近访问时间变了) ;而FIFO是针对页面进入内存的时间来进行排序，这个时间是固定不变的，所以各页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么LRU算法就退化为FIF0算法。例如:给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3…
要有局部性
LRU算法性能较好，但系统开销较大; FIF0算法系统开销较小，但可能会发生Belady现象。因此，折衷的办法就是Clock算法，在每一次页面访问时，它不必去动态地调整该页面在链表当中的顺序，而仅仅是做一个标记，然后等到发生缺页中断的时候，再把它移动到链表末尾。对于内存当中那些未被访问的页面，Clock算法的表现和LRU算法样好; 而对于那些曾经被访问过的页面，它不能象LRU算法那样，记住它们的准确位置。

综合比较局部页替换算法
都是 针对一个程序 站在算法角度本身考虑

LRU和FIFO本质都是先进先出，但LRU是页面的最近访问时间而不是进入内存的时间，有动态调整，符合栈算法的特性，空间越大缺页越少。如果程序局部性，则LRU会很好。如果内存中所有页面都没有被访问过会退化为FIFO。
Clock 和enhanced clock也是类似于FIFO的算法，但用了硬件的BIT来模拟了访问时间和顺序，近似了LRU，综合起来较好，但也会退化为FIFO。
都对程序的访问次序有局部性的要求，不然都会退化。
开销上，LRU开销大，FIFO开销小但BELADY，折中的是clock算法，开销较小，对内存中还未被访问的页面，效果等同LRU。对曾经被访问过的则不能记住其准确位置。

6.8 局部页替换算法的问题，工作集模型

局部页替换算法的问题、工作集模型
分配的物理页帧的数目对置换算法的效果有很大的影响。
程序的运行具有阶段性，是动态变化的过程，开头结尾较多，中间较少，都分配固定的物理页帧则失去了灵活性。

工作集模型
前面介绍的各种页面置换算法，都是基于一个前提，
即程序的局部性原理。但是此原理是否成立?
-如果局部性原理不成立，那么各种页面置换算法就没有什么分别，也没有什么意义。例如:假设进程对逻辑页面的访问顺序是1、2、3、4、5、6、7、8、9…, 即单调递增，那么在物理页面数有限的前提下，不管采用何种置换算法，每次的页面访问都必然导致缺页中断。
-如果局部性原理是成立的，那么如何来证明它的存在，如何来对它进行定量地分析?这就是工作集模型!



常驻集

6.9 两个全局页面置换算法

(1)工作集页置换算法

(2)缺页率页面置换算法

根据缺页率的变化来调整常驻集的大小。



与工作集置换算法的区别
-对页的调整时机不一样。这个方法只在缺页中断时判断是否更改，而后者是在每次换入换出时都做判断。
-都与局部页置换算法不一样。这两种涉及到工作集大小的调整。而局部只是在工作集满了之后才考虑换入换出。
-全局页置换算法效果比局部页置换算法要好。

6.10 抖动问题

抖动问题(thrashing)
如果分配给个进程的物理页面太少， 不能包含整个的工作集，即常驻集C工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种状态称为“抖动”。
-产生抖动的原因:随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升。所以OS要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。

X轴 程序个数 Y轴 CPU利用率
两个缺页产生的平均时间 = 完成一次缺页中断服务的时间