[操作系统]第六课

浅浅的花香味﹌ 2022-04-23 07:58 290阅读 0赞

> 课程来源《操作系统\_清华大学(向勇、陈渝)》

局部页面置换算法：最优页面置换算法OPT、先进先出算法FIFO、最近最久未使用算法LRU、时钟页面置换算法Clock、最不常用算法LFU、Belady现象、LRU和FIFO和Clock的比较

全局页面置换算法：局部页替换算法的问题、工作集模型、工作集页置换算法、缺页率置换算法、抖动问题

**1.最优页面置换算法**

功能：当缺页中断发生时，需要调入新的页面而内存已满时，需要选择哪个物理页面被置换？  
目标：尽可能减少缺页中断（页面的换入换出）次数。具体来说，把未来不再使用的或短期内较少使用的页面换出，通常只能在局部性原理下根据过去的数据统计进行预测。

页面锁定（frame locking）：用于描述必须常驻内存的操作系统的关键部分，或时间关键的应用进程（time-critical）。实现方法：需要在页表中添加锁定标志位（lock bit）。

比较不同的页面置换算法：  
设置一个实验环境，记录一个进程对页访问的轨迹。  
虚拟地址跟踪（3，0） （1，9） （4，1）……  
偏移可忽略，只用页号生成页面轨迹3，1，4 ……  
模拟一个页面置换的行为并且记录产生缺页的数量，越少越好

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]

**最优页面置换算法**

基本思路：当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需要等待多长时间从中选择等待时间最长的那个，作为被置换的页面。

这只是一种理想情况，在实际系统中是无法实现的，因为操作系统无从知道每一个页面要等待多长时间才会再次被访问。

可用作其他算法的性能评价的依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可使用最优算法）。

**2.先进先出算法**

先进先出算法（First-In First-Out，FIFO）；

基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说，系统维护者一个链表，记录着所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首页面淘汰出局，并把新的页面添加到链表的末尾。

性能较差，调出的页面有可能是要经常访问的页面（（驻留时间长，本身就说明可能常用）），并且有Belady现象（（给的物理页帧越多反而缺页越频繁））。FIFO算很少单独使用。

FIFO belady现象：分配的物理页数增加，缺页率反而提高，原因是FIFO忽视了进程访问的动态特征。多次访问的不要走。尤其是最坏情况发生时，易高缺页率。

**3.最近最久未使用算法**

最近最久未使用算法（Least RecentlynUsed，LRU）；

基本思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。

是对最优置换算法的近似，以过去推未来。根据程序的局部性原理，如果最近一段时间内某些页面被频繁访问，那么在将来还可能被频繁访问。反之，未被访问的将来也不会被访问。

程序应具有较好的局部性。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]

需要记录各个页面使用时间的先后顺序，开销大。  
两种可能的实现方法：  
系统维护一个页面链表，最近刚使用的页面最为首节点，最久未使用的页面作为尾节点，每次访问内存动态更新头结点。缺页中断时 ，淘汰末位的页面。  
活动页面堆栈：访问某页时，将此页号入栈，并去除栈内的重复页。淘汰栈底的页面。（栈是先进后出，只有栈顶开口，怎么push栈底？）

动态更新（插，删，内部调整）堆栈和链表要开销，注意平衡—不是最有效

**4.时钟页面置换算法**

**基本思路：**  
1.用到页表项的访问位（access bit），当一个页面被装入内存时，把该位初始化为0，被访问（读/写）时，硬件把它置为1. 而OS会定期清0。（1—最近被访问，0—-未访问）  
2.把各个页面组成环形链表类似一个clock，指针指向最老的页面。  
3.当发生一个缺页中断时，考察指针所指的最老页面，访问位是0则淘汰，如果是1（最近被访问）则置为0，然后指针向下移动一格。如此下去直到淘汰某页。

维持一个环形页面链表保存在内存中：  
1.用一个时钟（或者使用/引用）位来标记一个页面是否经常被访问  
2.当一个页面被引用的时候，这个位被设置为1

时钟头扫遍页面寻找一个带有used bit=0：  
1.替换在一个周转内没有被引用过的页面

在内存中维持一个环形页面链表，更新并删除used bit=0的页面

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]

**5.二次机会算法**

Dirty bit是指CPU cache/内存单元中的一种存储位状态，当处理器修改了某个cache/内存单元中的数据时，这个单元就会被标为“dirty bit"，代表此单元的数据已经被修改且没有被写到外部存储里。

区分读和写，enhanced clock algorithm。

读和写都是访问，dirty bit是写位，如果写，为1，否则是0。同时使用脏位和使用位。

修改clock算法，使它允许脏页总是在一次时钟头扫描时保留下来，以减少写回硬盘的操作（仅读的页可以直接释放）

需要替换的页，其访问位和脏位都是0，如果都是 1，则有两次机会才被淘汰。从而让更多使用频率的页有更多的机会留在内存中。（如果两个都是1那么有两次经过的机会，经过1次置换1个为0，如果只有一个是1，那么下次经过两个都为0了，脏位就是为了减少硬盘访问次数，11比起01和10多了一次机会）

较为接近LRU算法，尽量保存dirty page，更好地减少了访问外存

意思是一旦曾经有过写操作，内容就改变了，以后再交换页的时候就要就要向硬盘些新的内容了.

**6.最不常用算法**

最不常用算法（least frequently used）LFU

基本思路：当一个缺页中断发生时，选择置换访问次数最少的那个页面，并淘汰之。

实现方法：对每个页面设置访问计数器，每当一个页面被访问时，该页面的访问计数器加1.在发生缺页中断时，淘汰计数值最小的那个页面。

我们要考虑硬盘的计数器空间开销，排序查找时间开销；

LRU/LFU区别：LRU考察的是多久未访问，时间越短越值得留在内存，LFU是访问次数/频度，次数越多越好。  
反例：一个页面在进程开始时使用的很多，但以后就不使用了。此时LFU就不适用了（LFU访问次数是很多，但是后面逐渐不用了，总体也是费时费力）。  
解决方法：把时间也考虑进去，在一段时间内考察LFU。比如，定期把次数寄存器右移一位（相当于定期把使用次数除以2）。

**7.Belady现象、LRU、FIFO、Clock的比较**

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

Belady现象：在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的异常现象；

Belay现象的原因：FIFO算法的置换特征与进程访问内存的动态特征时矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此，被它置换出去的页面并不一定是进程不会访问的。

LRU和FIFO本质都是先进先出，但LRU是页面的最近访问时间进行排序而不是进入内存的时间，有动态调整，符合栈算法的特性，空间越大缺页越少。如果程序局部性，则LRU会很好。如果内存中所有页面都没有被访问过会退化为FIFO。

Clock 和enhanced clock也是类似于FIFO的算法，但用了硬件的BIT（bit）来模拟了访问时间和顺序，近似了LRU，综合起来较好，但也会退化为FIFO。

都对程序的访问次序有局部性的要求，不然都会退化。

LRU算法性能较好，但系统开销较大；FIFO算法系统开销较小，但可能会发生Belady现象。因此，折衷的办法就是Clock算法，在每一次页面访问时，它不必去动态调整页面在链表当中的顺序，而仅仅时做一个标记，然后等到发生缺页中断的时候，再把它移动到链表末尾。对于内存当中那些未被访问的页面，Clock算法的表现和LRU算法一样好；而对于那些曾经被访问过的页面，它不能像LRU算法那样，记住它们的准确位置。

开销上，LRU开销大，FIFO开销小但BELADY，折中的是clock算法，开销较小，对内存中还未被访问的页面，效果等同LRU。对曾经被访问过的则不能记住其准确位置。

**8.局部页替换算法的问题、工作集模型**

前面介绍的各种页面置换算法，都是基于一个前提，即程序的局部性原理。但是此原理是否成立？

如果局部性原理不成立，那么各种页面置换算法就没有什么区别，也没有什么意义。  
如果局部性原理是成立的，那么如何来证明它的存在，如何来对它进行定量地分析，这就是工作集模型。

工作集模型，工作集：一个进程当前正在使用的逻辑页面集合。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]  
常驻集：在当前时刻，进程实际驻留在内存当中的页面集合。

工作集是固有性质，常驻集取决于系统分配给进程的物理页面数目和所采用的置换算法。如果一个进程的常驻集与工作集尽量重叠，则不会造成太多缺页中断。当常驻集大小达到某个数目后，再分配物理页帧也不会有明显下降的缺页率——可以把多出来的物理页帧分给其他程序了。

**9.两个全局置换算法**

工作集缺页置换算法、缺页率页面置换算法

**10.抖动问题**

如果分配给一个进程的物理页面太少，常驻集远小于工作集，则缺页率会很大，频繁在内外存之间替换页面，使进程的运行慢，这种状态成为”抖动”。

随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减少，缺页率上升。因此OS要选择一个适当的进程数目和进程需要的帧数，在并发水平和缺页率中达到平衡。

抖动问题可能被本地的页面置换改善。

程序开的多，OS忙于换进换出的I/O操作，用于运行程序的cpu少了。找到交汇点，此时可以并发执行的程序个数和cpu利用率都较好，总体达到平衡。另一方面，如果仅有一个程序，但它很大，也会导致抖动。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220322/493881df2e5040c9b6a09ccfa23043c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220322/2ab32c6eeb5e4cc696af75586b3c7101.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 2]: /images/20220322/0bef3fa297a84296a7db85891f416b97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 3]: /images/20220322/b7b6d068cb8149498f94ce2ec6d0a328.png