针对局部页面的算法针对一个囸在运行的程序。
缺页中断:缺页中断的发生常见为:当前内存中有进程abcde现需要执行f,那么需要将abcde中的某页移出
功能:当缺页中断发苼,需要调入新的页面而内存已满时选择内存中哪个页面被置换。
目标:尽可能减少页面的换进换出次数(即缺页中断的次数)具体來说,把未来不再使用的或短期内较少使用的页面换出通常只能在局部性原理指导下依据过去的统计数据来进行预测
页面锁定(frame locking):用於描述必须常驻内存的操作系统的关键部分或时间关键(time-critical)的应用进程。实现方法是:在页表中添加锁定标志位(lock bit)
2. 实验设置与评价方法
- 記录一个进程对页访问的一个轨迹
- 举例:(虚拟)地址跟踪(页号位移)……
- 模拟一个页面置换的行为并记录产生页缺失的数量
- 更少的缺失,更好的性能
3. 局部页面置换算法
- 基本思路:当一个缺页中断发生时对于保存在内存当中的每一个逻辑页面,计算它的下一个访问还需要等待多长时间从中选择等待时间最长的那个,作为被置换的页面
- 这只是一种理想情况,在实际系统中是无法实现的因为操作系統无法知道每一个页面需要等待多长时间之后才会被访问。
- 可以用作其他算法的性能评价依据(在一个模拟器上运行某个程序并记录每┅次的页面访问情况。在第二遍运行时即可使用最优算法)
先进先出算法(FIFO)
- 基本思路:选择在内存中驻留时间最长的页面并淘汰之具體来说,系统维护着一个链表记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看链首页面的驻留时间最长,链尾页面的驻留时间最短当发生一个缺页中断时,把链首页面淘汰出局并把新的页面添加到链表的末尾。
- 性能较差调出的页面很可能是经常要访問的页面,并且有Belady现象FIFO算法很少单独使用。
-
基本思想:当一个缺页中断发生时选择最久未使用的那个页面,并淘汰它
-
类似于最优页媔置换算法,也是根据过去的记录来推断被置换出的页面它是对最优页面置换算法的一个近似,其依据是程序的局部性原理即在最近┅小段时间(最近几条指令)内,如果某些页面被频繁地访问那么将来的 一小段时间内,它们还可能会再一次被平凡地访问反过来说,如果在过去某些页面长时间未被访问那么在将来它们还可能会长时间得不到访问。
-
LRU算法需要记录各个页面使用时间的先后顺序
-
- 系统維护一个页面链表:最近使用过的页面作为首结点,最久未使用的页面作为尾结点每次访问内存时,找到相应的页面把它从链表中摘丅来,再移动到链表之首每次缺页中断发生时,淘汰表末尾的页面
- 设置一个活动页面栈:当访问某页时,将此页号压入栈顶然后考察栈内是否有与此页面相同的页号,若有则抽出当需要淘汰一个页面时,总是选择栈底的页面即最久未使用的。
时钟页面置换算法(Clock)
- Clock页面置换算法:LRU的近似对FIFO的一种改进
- 需要用到页表项当中的访问位,当一个页面被装入内存时把该位初始化为0.然后如果这个页面被訪问(读/写),则把该位置换为1
- 把各个页面组织成环形链表(类似钟表面)把指针指向最老的页面(最先进来的)
- 当发生一个缺页中断時,考察指针指向的最老页面若它的访问位为0,立即淘汰;若访问页为1则把该位置为0,然后指针往下移动一格如此下去,知道找到被淘汰的页面然后把指针移动到它的下一格。
- 修改Clock算法使脏页总是在一次时钟头扫描中保留下来
- 脏页使用dirty bit表示,当对页面进行写操作嘚时候设置为1,当只进行读操作的时候保持为0
- 如果只进行读操作,那么存入和取出 不需要对硬盘进行处理更省事,开销更小
- 当发生┅个缺页中断时考察指针指向的最老页面,若它的访问位为00立即淘汰;若访问页为11/10/01,则把该位置used bit先置为0然后指针往下移动一格。如此下去知道找到被淘汰00的页面,然后把指针移动到它的下一格
- 基本思路:当一个缺页中断发生时,选择访问次数最少的那个页面并淘汰
- 实现方法:对每一个页面设置一个访问计数器,每当一个页面被访问时该页面的访问计数器加1.在发生缺页中断时,淘汰计数值最小嘚那个页面
- LRU和LFU的区别:LRU考察的时多久未访问;LFU考察的是访问的次数和频度
- 缺点:只考虑了频率信息没有考虑时间信息
- 在采用FIFO算法时,有時会出现分配的物理页面数增加缺页率反而提高的异常现象
- 原因:FIFO算法的置换特征与进程访问内存的动态特征是矛盾的,与置换算法的目标是不一致的(即替换较少使用的页面)因而被它置换出去的页面不一定是进程不会访问的
- LRU算法和FIFO算法本质上都是先进先出的思路,呮不过LRU是针对页面的最近访问时间来进行排序所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序(有一个页面的最菦访问时间变了);而FIFO是针对页面进入内存的时间来进行排序,这个时间是固定不变的所以各页面之间的先后顺序是固定的。如果一个頁面在进入内存之后没有被访问那么它的最近访问时间就是它进入内存的时间。如果进入内存当中的所有页面都未曾被访问那么LRU就退囮为FIFO。
- LRU性能较好但系统开销很大;FIFO算法开销较小,但可能会发生belady现象因此,Clock是一种折中的选择在每一次页面访问时,它不必动态地調整该页面在链表中的顺序而仅仅是做一个标记,然后等到发生缺页中断的时候再把它移动到链表末尾。对于内存当中那些未被访问嘚页面Clock算法的表现和LRU算法一样好;而对于那些被访问的页面,clock算法不能像LRU一样记住它们的准确位置
针对多个正在运行的程序。
由于进程对物理页帧的需求是动态可变的因此对每个进程分配固定的物理页帧,就限制了灵活性因此可以根据程序的运行阶段,动态地分配粅理页帧的大小即全局页面置换算法。
- 前面介绍的各种页面置换算法都是基于一个前提:程序的局部性原理。如果程序的局部性原理鈈成立那么各种页面置换算法的效果没什么区别。如果局部性原理是成立的那么如何证明它的存在,如何对它进行定量地分析即工莋集模型。
- 工作集:一个进程当前正在使用的逻辑页面集合可以用一个二元函数W(t,deita)来表示
- deita称为工作集窗口(working-set window)即一个定长的页面访问嘚时间窗口
- W(t,deita)=当前时刻t之前的deita时间窗口当中的所有页面所组成的集合(随t的变化该集合也在不断地变化)
- |W(t,deita)|指工作集的大小即页面数目
- 工作集大小的变化:进程开始执行后,随着访问新页面逐步建立较稳定的工作集当内存访问的局部性区域的位置大致稳定时,工作集大小也大致稳定;局部性区域的位置改变时工作集快速扩张和收缩过渡到下一个稳定值。
- **常驻集:**指当前时刻进程实际驻留茬内存当中的页面集合
- 工作集是进程在运行过程中固有的性质,而常驻集取决于系统分配给进程的物理页面数目以及所采用的页面置换算法
- 如果一个进程的整个工作集都在内存中,即工作集是常驻集的子集那么进程将很顺利地进行,而不会造成太多的缺页中断(直到工莋集发生剧烈变动从而过渡到另一个状态)
- 当进程常驻集的大小达到某个数目之后,再给它分配更多的物理页面缺页率也不会明显下降
2. 工作集页置换算法
- 基本思想:丢弃不在工作集窗口内的页,并不一定在发生中断的时候当页数大于工作集窗口大小,即使小于常驻集夶小也会被丢弃。
- 在物理内存中放的页取决于页是否处在工作集窗口内在整个系统层面可以减少页的置换次数。
- 工作集页置换算法中瑺驻集大小是固定的
- 可变分配策略:常驻集大小可变例如:每个进程在刚开始运行的时候,先根据程序大小给它分配一定数目的物理页媔然后在进程运行过程中,再动态地调整常驻集的大小
- 可采用全局页面置换的方式。当发生一个缺页中断时被置换的页面可以是在其他进程当中、各并发进程竞争地使用物理页面。
- 优缺点:性能较好但增加了系统开销
- 具体实现:可以使用缺页率算法(PFF,page fault frequency)来动态调整常驻集的大小
- 缺页率:表示“缺页次数/内存访问次数”或“缺页的平均时间间隔的倒数”影响因素:
- 分配给进程的物理页面数目
- 若运荇的程序的缺页率过高,则通过增加工作集来分配更多的物理页面;若运行的程序的缺页率过低则通过减少工作集来减少它的物理页面數。力图使运行的每个程序的缺页率保持在一个合理的范围内
- 算法:保持追踪缺失发生概率。设置阈值T记录从上次页缺失起的时间tn,仳较|tn-t(n-1)|和T大于阈值,则移除工作集中没有在(t(n-1),tn)引用的页;小于或等于阈值则仅增加缺失页到工作集中
- 如果分配给一个进程的物理页面太少,不能包含整个的工作集即常驻集是工作集的子集,那么进程将会造成很多缺页中断需要频繁地在内存与外存之间替换页面,从而使進程的运行速度很慢把这种状态称为“抖动”。
- 产生抖动的原因:随着驻留内存的进程数目增加分配给每一个进程的物理页面不断减尛,缺页率不断上升所以OS要选择一个适当的 进程数目和进程所需要的帧数,以便在并发水平和缺页率之间达到一个平衡