页面置换算法的概念
功能：当出现缺页异常，需调入新页面而内存已满时，置换算法选择被置换的物理页面 目标：尽可能减少页面的调入调出次数，了解程序内存访问特征。把未来不再访问或短期内不访问的页面调出。 页面锁定：必须在内存里的重要的逻辑页面 - os中的关键代码 - 响应速度要求快的数据和代码 - 页表加上标志 评价方法： 统计测试用例，记录进程访问内存的页面轨迹。序列。 模拟置换算法行为，记录缺页次数，越少越好 分类： 局部，置换页面的选择范围 分配给一个进程的物理页面数，仅限于当前进程； 最优 预测未来 理论最好，先进先出 未知未来 按进来的先后顺序，最近最久未使用算法 统计过去→近似：时钟 最不常用算法； 全局：不关心当前换的页面属于哪个进程，选择范围时所有可换出的物理页面 工作集算法、缺页率算法
局部页面置换算法 区分页面属于哪个进程
给一个进程的物理页面数已经确定了
最优置换算法 optimal
基本思路：置换未来最长时间不访问的页面 算法实现：缺页时，计算内存中每个逻辑页面下一次的访问时间，（内存当中页面排序依据）未来最长时间不访问的页面就是要置换的页面。 算法特征：缺页最少，理想情况；无法实现；无法预知；作为其他算法性能评测的依据。 第一次 运行，第二次运行使用最优算法。
先进先出 FIFO
思路：按照进来的顺序排，先来后到。内存驻留时间最长，第一个进来，最后一个进来 实现： 维护一个记录所有位于内存中的逻辑页面链表，链表元素按驻留内存的时间排序，链首最长，链尾最短，出现缺页时，选择链首页面进行置换，新页面加到链尾 特征： 实现简单，性能较差，调出的页面可能是经常访问的；进程分配物理页面数增加时，缺页并不一定减少(Belady现象)；很少单独使用 示例看视频。
最近最久未使用算法least recently used
思路：选择最长时间没有被引用的页面进行置换。统计过去的情况。依据过去预测未来。 实现：缺页时，计算内存中每个逻辑页面的上一次访问时间，选择上一次时用到当前时间最长的页面 特征：最优置换算法的一种近似。往前考察。 可能实现方法： 页面链表： 系统维护一个按最近一次访问时间排序的页面链表，首节点最近刚刚使用过的页面，尾节点最久未使用的页面；访问内存时，找到相应的页面，并把它移到链表之首，缺页时，置换链表尾节点的页面。 落实到 平时。。 活动页面栈： 访问页面时，压入页号，抽出栈内相同的页号放入栈顶；缺页时，置换栈底的页面 特征：平时的开销大
时钟页面置换算法 clock fifo 与lru之间的折衷
思路：仅对页面访问情况进行大致统计，lru由于过于详细 开销大； 数据结构：页表项增加访问位，描述页面在过去一段时间内的访问情况。 各页面组织成环形链表，指针指向最先调入的页面 算法：访问页面时，在页表项记录页面访问情况，设置1；缺页时，从指针开始顺序查找未被访问的页面进行置换，上一次到现在扫描 特征：lru和fifo折中，对过去有考虑，但是考虑得不是很详细，如果都没有访问，退化成fifo了 实现： 页面装入内存时，访问位初始化为0；访问页面时（读/写），访问位置1；缺页时，从指针当前位置顺序检查环形链表：访问位为0,置换；访问位为1,则改为0 清零,也就是从这一点开始 开始新的一轮计时，并且将指针移动到下一个页面，直到找到可置换的页面。
图示
增强时钟算法
思路：减少修改页的缺页处理开销，写回， 算法：在页面中增加修改位，并在访问时进行相应修改，缺页时，修改页面标志位，以跳过有修改的页面，图 指针扫描前 扫描后
| 指针扫前 | 指针扫后 |
|---|---|
| 使用位 修改位 | 使用位 修改位 |
| 00 | 置换 |
| 01 | 00 写回 |
| 10 | 00 |
| 11 | 01到第二个状态 |
最不常用算法 Least Frequently Used LFU
思路：缺页时，置换访问次数最少的页面。 LRU&LFU:一个关注多久访问，时间越短越好，一个关注访问次数，次数越多越好
上述两种算法都是对LRU某种程度上的简化，简化后开销小，但是统计的精度下降。近似的程度与准确度。硬件方便实现使得。为什么有lfu 如果它的硬件开销大。存储的访问？不仅有cpu到内存，读硬盘的存储访问，时间长一些，这些算法就可以用。
Belady现象
采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象。
原因：
- FIFO算法的置换特征与进程访问内存的动态特征矛盾 预测不合理。
- 被它置换出去的页面并不一定是进程近期不会访问的
lru没有belady现象。栈的做法，从地下抽上来的方法。 时钟/改进的时钟 ？ todo
LRU FIFO Clock的比较
相关性： 算法都有排序， LRU和FIFO本质上都是先进先出的思路 LRU依据页面的最近访问时间排序； LRU 需要动态调整顺序 每次维护栈的顺序 FIFO 加载时 依据页面进入内存的时间排序 不需动态调整 LRU可退化为FIFO 如果页面只访问一次，第一次，没有任何的历史可以借鉴。页面进入内存后没有被访问，最近访问时间与进入内存的时间相同。 视频信息 播放 从头到尾播一遍。
LRU 算法性能好，但系统开销较大 FIFO算法系统开销较小，但是会发生Belady现象 Clock算法是它们的折中 访问页面时，做标记(改页表项) 比啥事情也不干的fifo好，但是不动态调整页面在链表中的顺序（开销大） 缺页时，去扫描，顺序调整。直接蹦过 再把它移动到链表末尾。 对于未被访问的页面 Clock=LRU=FIFO 没有可以借用的信息了 对于被访问过的页面 FIFO<Clock<LRU 排序的指标与开销
全局置换算法
考虑到不同的进程之间对内存需求量的差异性 思路：给进程分配可变数目的物理页面 可变的依据：进程需求的量。需求量是不同的。如何度量需求？先对进程的内存访问特征做某种程度分析，不同阶段需求量不同。排序程序，读入 ，排序，输出 三个阶段。算法确定分配多少物理页面数。
cpu 利用率与并发进程数的关系
先高后低，两者 相互促进（前）和制约（后）的关系，
- 进程数少，提高并发进程数，可提高cpu利用率 前半段
- 并发进程导致内存访问增加
- 并发进程的内存访问会降低了访存的局部性特征，更换进程
- 局部性特征的下降会导致缺页率上升和cpu利用率下降
工作集置换算法
最优算法在全局中的体现
工作集的概念： 一个进程当前正在使用的逻辑页面集合，可表示为 二元函数W（t，）； 当前？诡异。近似。 t 当前的执行时刻。三角形：工作集窗口，即一个定长的页面访问时间窗口 不同的时间段访问的页面数不一样
工作集变化的规律：数据采集→数据处理→数据输出，在做不同事情 需要的内存量 工作集大小不一样
- 进程开始执行后，随着访问新页面逐步建立比较稳定的工作集
- 稳定阶段：当内存访问的局部性区域的位置大致稳定的时候，系统正在做一某件事情，工作集大小也大致稳定。
- 切换的时候，工作集有快速扩张和收缩的过程。
常驻集
常驻集：在当前时刻，进程实际驻留在内存当中的页面集合。 近似 工作集 工作集与常驻集的关系 - 工作集是进程在运行过程中固有的性质，特征；- 常驻集取决于系统分配给进程的物理页面数目和页面置换算法 缺页率与常驻集的关系
通过控制常驻集来影响缺页率
- 常驻集包含工作集，即工作集中访问的页面都在内存里，缺页较少
- 工作集发生剧烈变动时 ，过渡，缺页较多
- 进程常驻集大小达到一定数目后，缺页率也不会明显下降
思路 - 换出不在工作集的页面，与局部相比，并不是在缺页的时候才换。 窗口大小 - 当前时刻前个内存访问的页引用是工作集，被称为窗口大小 实现方法 - 访存链表：维护窗口内的访存页面链表，与LRU的栈类似 - 访存时，换出不在工作集的页面；更新访存链表 （开销大，复杂麻烦的地方）- 缺页时，换入页面；更新访存链表。这里反而比局部简单了
缺页率置换算法
依据缺页之间的间隔来调整哪些页面放到内存里头，哪些被置换
缺页率的定义：缺页次数/内存访问次数 或缺页平均时间间隔的倒数
影响缺页率的因素：- 页面置换算法 目前可以控制的 - 分配给进程的物理页面数目 - 页面大小 - 程序的编写方法
PFF page-fault-frequency 思路： 通过调节常驻集大小，使每个进程的缺页率保持在一个合理的范围内 - 进程缺页率过高，增加常驻集 以分配更多物理页面 - 缺页率过低，并发度降低，cpu利用率降低，减少常驻集以减少物理页面 实现：- 访存时，设置引用位标志 - 缺页时，计算从上次缺页时间到现在时间的时间间隔 - 如果>T这段时间隔得比较长，缺页率低，置换所有在tlast,tcurrent时间内没有被引用的页。- 小于等于T 直接增加缺失页到常驻集中 示例
常驻集大小变化自动调节，物理页面数， 置换放到缺页里来算。
抖动和负载控制 多个进程
抖动
- 系统里的进程数目太多，每个进程分配的物理页面减少，不能包含工作集
- 造成大量缺页，频繁置换
- 进程运行速度变慢
产生抖动原因：驻留内存的进程数目增加，分配给每个进程的物理页面数不断建校，缺页率不断上升
操作系统需要在并发水平与缺页率之间达到一个平衡 - 选择一个适当的进程数目与进程需要的物理页面数
负载控制
调节并发进程数 图