操作系统的虚拟内存管理技术中页面置换算法
页面置换算法
- 功能与目标
- 实验设置与评价方法
局部页面置换算法- 最优页面置换算法（OPT，optimal）
- 先进先出算法（FIFO）
- 最近最久未使用算法（LRU,Least Recently Used）
- 时钟页面置换算法（Clock）
- 最不常用算法（LFU, Least Frequently Used）
- Belady现象
全局页面置换算法- 工作集模型
- 工作集页置换算法
- 缺页率置换算法
1. 功能与目标
功能
- 当缺页中断发生, 需要调入新的页面而内存已满时, 选择内存当中哪个物理页面被置换.
目标
尽可能地减少页面的换进换出次数(即缺页中断的次数). 具体来说, 把未来不再使用的或短期内较少使用的页面换出, 通常只能在局部性原理指导下依据过去的统计数据来进行预测.
页面锁定
- 用于描述必须
常驻内存的操作系统的关键部分或时间关键的应用进程.实现的方式是 : 在页表中添加锁定标记位(lock bit).例如操作系统的代码和程序是随时要访问的，它属于常驻内存，通过锁定技术，锁在内存中，使得这些页在做页面置换算法时不会被置换出去，确保OS随时能正常工作
2. 实验设置与评价方法
3. 局部页面置换算法
3.1 最优页面置换算法
基本思路
当一个缺页中断发生时, 对于保存在内存当中的每一个逻辑页面, 计算在它的下一次访问之前, 还需等待多长时间, 从中选择等待时间最长的那个, 作为被置换的页面.- 这是一种理想情况, 在实际系统中是无法实现的, 因为操作系统无法知道每一个页面要等待多长时间以后才会再次被访问.
- 可用作其他算法的性能评价的依据.(在一个模拟器上运行某个程序, 并记录每一次的页面访问情况, 在第二遍运行时即可使用最优算法)
实例
3.2 先进先出算法（FIFO）
基本思路
选择在内存中驻留时间最长的页面淘汰. 具体来说, 系统维护着一个链表, 记录了所有位于内存当中的逻辑页面. 从链表的排列顺序来看, 链首页面的驻留时间最长, 链尾页面的驻留时间最短. 当发生一个缺页中断时, 把链首页面淘汰出去, 并把新的页面添加到链表的末尾.- 性能较差, 调出的页面有可能是经常要访问的页面. 并且有
belady现象. FIFO算法很少单独使用. Belay现象：当分配给一个运行程序更多的物理页后，按理是缺页的现象变少了，但是如果使用FIFO算法，可能会导致缺页现象变多
实例
- FIFO实现简单，只需要链表，但是产生的缺页次数多
3.3 最近最久未使用算法（LRU(Least Recently Used)）
基本思路
- 当一个缺页中断发生时, 选择最久未使用的那个页面, 并淘汰.
- 当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。
LRU与FIFO区别
LRU：最久未被使用，FIFO：最长驻留时间- 最长驻留时间是存在那里很久，但是它最近可能被访问过
- 最久未被使用，它很长时间都没有被访问过
LRU与最优页面置换算法
- LRU是根据过去，来推测具体换出哪一页（根据历史推测未来）
- 最优页面置换算法，替换将来最远都没有使用的页面（根据未来推测未来）
依据原理
- 它是对最优页面置换算法的一个近似, 其依据是程序的局部性原理, 即在最近一小段时间(最近几条指令)内, 如果某些页面被频繁地访问, 那么再将来的一小段时间内, 他们还可能会再一次被频繁地访问. 反过来说, 如果过去某些页面长时间未被访问, 那么在将来它们还可能会长时间地得不到访问.
实例
LRU算法需要记录各个页面使用时间的先后顺序,需要遍历整个链表和栈，开销比较大
`两种可能的实现方法是
:`
- 系统维护一个页面链表, 最近刚刚使用过的页面作为首节点, 最久未使用的作为尾结点. 再一次访问内存时, 找出相应的页面, 把它从链表中摘下来, 再移动到链表首. 每次缺页中断发生时, 淘汰链表末尾的页面.
- 设置一个活动页面栈, 当访问某页时, 将此页号压入栈顶, 然后, 考察栈内是否有与此页面相同的页号, 若有则抽出. 当需要淘汰一个页面时, 总是选择栈底的页面, 它就是最久未使用的.
实例
- 每次访问，都需要查找这个栈，当物理页帧比较多的情况下，开销很大
3.4 时钟页面置换算法
- Clock 页面置换算法，LRU的近似，对FIFO的一种改进
基本思路
- 需要用到页表项的访问位, 当一个页面被装入内存时, 把该位初始化为0. 然后如果这个页面被访问, 则把该位置设为1;
- 把各个页面组织成环形链表(类似钟表面), 把指针指向最老的页面(最先进来);
- 当发生一个缺页中断时, 考察指针所指向的最老页面, 若它的访问位为0, 立即淘汰; 若访问位为0, 然后指针往下移动一格. 如此下去, 直到找到被淘汰的页面, 然后把指针移动到下一格.
具体流程
实例
- 时钟置换相比LRU差一些，与FIFO差不多，因为给的物理页短，实际上，
时钟置换与LRU产生中断缺页次数接近的，他用了一个bit模拟了整个List信息，它不精确，它达不到LRU最佳的效果，但是可以接近
3.5 二次机会法
- 因为考虑到时钟页面置换算法, 有时候会把一些 dirty bit 为1(有过写操作)的页面进行置换, 这样的话, 代价会比较大. 因此, 可以结合访问位和脏位一起来决定应该置换哪一页.
相当于说, 替换的优先级, 没有读写也没写过, 那么直接走, 如果写过或者访问过, 那么给你一次机会, 如果又写过, 又访问过, 那么久给你两次机会.
实例
- 和之前相比，区分出某一页是读还是写
优先换出只读的页，对于可写页多给一次机会,减少硬盘的读写次数
3.6 最不常用算法（Least Frequently used, LFU）
基本思路
- 当一个缺页中断发生时, 选择访问次数最少的那个页面, 并淘汰.
实现方法
- 对每一个页面设置一个访问计数器, 每当一个页面被访问时, 该页面的访问计数器加1. 当发生缺页中断时, 淘汰计数值最小的那个页面.
LFU和LRU区别
LRU考察的是多久未访问, 时间越短越好. 而LFU考察的是访问的次数和频度, 访问次数越多越好.
问题
- 一个页面在进程开始是使用得很多，但以后就不使用了。实现也费时费力
解决办法
- 定期把次数寄存器右移一位
实例
3.7 Belady现象
局部页面置换算法
- 针对一个运行的程序，访问的内存（页）的情况，来决定到底采取什么样的策略，用什么样算法，把相应的页替换出去，它站在了算法本身这个角度考虑具体换入换出那个页
Belady现象
- 在采用FIFO算法时, 有时会出现分配的物理页面数增加, 缺页率反而提高的异常现象;
Belady现象的原因
- FIFO算法的置换特征与进程访问内存的动态特征是矛盾的, 与置换算法的目标是不一致的(即替换较少使用的页面), 因此, 被他置换出去的页面不一定是进程不会访问的.
Belady现象实例
- 发现随着物理页的增多，产生的缺页次数更多了
为什么LRU没有Belady现象
- LRU符合栈算法的特点，意味着他可以满足这个属性，物理页帧越多，缺失数越少而FIFO不满足栈算法特点，就会产生Belady现象
3.8 LRU、FIFO、Clock比较
- FIFO和LRU都可用链表和栈来表示访问的次序
LRU考虑驻留时间和最近访问时间,考虑页的位置时，如果该页被访问到了，则从栈或者链表中取出来，放到头部去，但是FIFO没有这个过程- Clock只是对LRU算法的一个近似，Clock只用了一个bit或者俩个bit来表示访问时间，很明显用一个bit不可能表示一段时间的不同页面的访问顺序，它只是近似（Clock使用了硬件的一些bit，模拟访问时间和先后顺序）
注意
为了有效的减少缺页次数，除了算法本身，还有一个最重要的是本身的访问序列有一定要求，它最好具有局部性特征，才会使得这些算法能够发挥效果
4. 全局页面置换算法
4.1 局部页替换算法的问题、工作模型
- 局部页面算法只针对一个运行的程序
局部算法
- 只对一个运行的程序分配固定的物理页帧，就限制了程序产生缺页的特点
（因为程序在运行的过程中有阶段性，可能最开始可能访问多，需要很多内存，中间一段可能需要很少，在结束时又需要很多,它是动态的过程，物理页帧的需求是不断变化的） - 前面的算法都假定只对一个运行程序分配固定的物理页帧
全局算法
- 根据程序不同的运行阶段，动态的调整物理页帧的大小
4.1 工作集模型
4.2 工作集
例子
- t2的整体局部性强，频繁访问3,4，而t1整体局部性不强，但是有一定局部性
4.3 常驻集
常驻集是指在当前时刻, 进程实际驻留在内存当中的页面集合.- 工作集是进程在运行过程中固有的性质, 而常驻集取决于系统分配给进程的物理页面数目, 以及所采用的页面置换算法;
- 如果一个进程的整个工作集都在内存当中, 即常驻集 包含 工作集, 那么进程将很顺利地运行, 而不会造成太多的缺页中断(直到工作集发生剧烈变动, 从而过渡到另一个状态);
- 当进程常驻集的大小达到某个数目之后, 再给它分配更多的物理页面, 缺页率也不会明显下降.
工作集和常驻集区别
- 工作集：体现运行程序，在运行过程中，他对页面访问的一个属性，是程序本身固有的属性
- 常驻集：操作系统和计算机系统给应用程序分配的物理页的大小，以及采取页面置换算法来决定，应该把哪些页面放到内存中
理解：常驻集是当前运行的程序，需要访问的页哪些在内存中，而工作集是当程序运行过程中它所需要访问的页有哪些，可能在内存中也可能没在内存中
4.4 工作集页置换算法
思想
- 工作集有一个窗口，这个窗口有一个起始时间和size，窗口里面的页代表当前这段时间内被访问到的页，如果某个页要替换时需要替换1. 不在工作集的页，2. 随着程序执行，窗口在移动，如果某个页不在这个窗口之内，这个页也会被丢掉（并不是等待缺页的时候进行丢弃）
当工作集窗口在滑动过程中, 如果页面不在集合中, 那么就会直接丢失这个不在窗口中页面, 而不会等待缺页中断再丢弃.
与局部页面相比
- `在物理内存中放哪些页，取决于是否在这个工作集窗口之内，如果工作集窗口设置为4，那么超出4的窗口的那些老的页都会被换出去，这样可以确保物理内存中始终有足够多的页存在，可以给
其他运行的程序提供更多的内存，从而进一步减少页面置换的次数`
在整个系统层面（多个程序，不是一个程序）确保缺页次数会降低
4.5 缺页率置换算法
缺页率
- 表示 "缺页次数 / 内存访问次数"
影响因素
- 页面置换算法, 分配给进程的物理页面数目, 页面本身的大小, 程序的编写方法.
缺页率算法
- 一开始运行的程序缺页率比较高，会增加工作集（也就是访问的页尽量在内存中）
方法
- 增加工作集就是增加σ,之前σ默认为4，也就是窗口大小，此时工作集的窗口可以进行变化
例如阈值t = 2，当前产生中断的时刻和上一次产生中断的时刻，差值大于2，那就把不在这个时间内访问的那些页全都清出这个工作集，但是如果当前中断访问时刻和上次中断访问时刻小于2等于，就会把当前缺的页加入到工作集中
实例
例如阈值t = 2，当前产生中断的时刻和上一次产生中断的时刻，差值大于2，那就把不在这个时间内访问的那些页全都清出这个工作集，但是如果当前中断访问时刻和上次中断访问时刻小于2等于，就会把当前缺的页加入到工作集中
工作集页面置换算法和缺页率置换算法区别
对页的调整时机不一样
- 工作集页面算法是在访问每一个页时都会判断是否需要把这个页清除出去还是添加进来，而缺页率置换只是在中断时刻才做这个判断
全局页算法和局部页算法不一样
全局页算法根据工作集和缺页率来动态调整整个内存需要置换的物理页局部页算法只是在满的情况下进行调整，全局页算法即使没有满也会进行置换- 整体上使得频繁访问的页驻留在内存中，对于OS而言要应对多个运行的程序采取全局页面算法效果好于局部页面算法
4.6 抖动问题
- 工作集：体现程序在执行过程中本身对内存访问的固有属性
- 常驻集：体现操作系统把当前运行的程序需要访问的哪些页面放到内存中来
