精华内容
下载资源
问答
  • Belady现象:在采用FIFO算法时,有时会出现分配的物理页数增加,缺页率反而提高的异常现象。 Belady现象的原因:FIFO算法的置换特征与进程访问内+存的动态特征是矛盾的。与置换算法的目标是不一致的(即替换较少使用...

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

    Belady现象的原因:FIFO算法的置换特征与进程访问内+存的动态特征是矛盾的。与置换算法的目标是不一致的(即替换较少使用的页面)。因此,被它置换出去的页面并不一定是进程不会访问的。

    为什么FIFO算法会产生Belady现象,而LRU算法不会产生Belady现象:

    解答:因为LRU算法符合栈算法的特点,而FIFO算法不符合栈算法的特点。栈算法的特点是给与的物理页帧越多,所产生的缺页中断的次数就越少。

    思考:Clock algorithm 和 Enhanced Clock algorithm 是否会产生Belady现象?


    LRUFIFO和Clock的比较:

    • LRU算法和FIFO算法本质上都是先进先出的思路。只不过LRU针对页面最近访问的时间来进行排序。所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序(有一个页面最近访问的时间变了);而FIFO是针对页面进入内存的时间来进行排序,这个时间是固定不变的。所以页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问。那么它最近访问的时间就是它进入内存的时间。换句话说,如果内存当中所有的页面都未曾访问过,那么LRU算法就退化为FIFO算法。

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


    前言:之前介绍的各种页面置换算法,都是基于一个前提。即程序的局部性原理。但考虑此原理是否成立?就存在以下两种情况:

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

    工作集:一个进程当前正在使用的逻辑页面的集合。可以用一个二元函数 W(t,^)来表示:

    • t是当前的执行时刻
    • ^称为工作集窗口(working-set window),即一个定长的页面访问的时间窗口(^是不变的)
    • w(t,^)=在当前的时刻t之前的 ^时间窗口当中的所有页面所组成的集合(随着t的变化,该集合也在不断地变化);
    • | W(t,^) |,值工作集的大小,集页面的数目;

    工作集大小的变化:进程开始执行后,随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时,工作集的大小也大致稳定;局部性区域的位置改变时,工作集快速的扩张和收缩过渡到下一个稳定值。

    常驻集是指在当前时刻,进程实际驻留在内存当中的页面集合。

    • 工作集是进程在运行过程中固有的性质,而常驻集取决于系统分配给进程的物理页面的数目,以及所采用的页面置换算法;
    • 如果一个进程的整个工作集都在内存当中,即常驻集包含或者等于工作集,那么进程将很顺利地进行,而不会产生太多的缺页中断(直到工作集发生剧烈的变动,从而过渡到另外一个状态);
    • 当进程常驻集的大小达到某个数目以后,再给它分配更多的物理页面,缺页率也不会明显的下降。

    提示:为了更好的理解知识点,博主在微信公众号中将操作系统知识进行了重新排版和插入图片。感兴趣的朋友可以扫码进行关注。

    在这里插入图片描述

    展开全文
  • 一、页面置环算法的概念 1、页面置环算法的概念 ...③页面锁定(frame locking):用于描述必须常驻内存的内存的逻辑页面;操作系统的关键部分,或时间关键的应用进程(time-critical)。需要在页表中添加...

    一、页面置环算法的概念

    1、页面置环算法的概念

    ①功能:当缺页中断发生时,需要调入新的页面而内存已满时,置环算法选择被置换的物理页面

    ②目标:尽可能减少缺页中断(页面的换入换出)次数。在局部性原理下根据过去的数据统计预测。

    ③页面锁定(frame locking):用于描述必须常驻内存的内存的逻辑页面;操作系统的关键部分,或时间关键的应用进程(time-critical)。需要在页表中添加锁定标志位(lock bit)

    ④置环算法的评价方法

    模拟页面置换行为,记录产生缺页的次数,更少的缺页,更好的性能。

    2、局部页面置环算法

    ①最优页面置环算法(OPT optimal)②先进先出算法(FIFO)③最近最久未使用算法(LRU,Least Recently Used)④时钟页面置换算法(Clock)⑤最不常用算法(LFU,Least Frequently Used)⑥Belady算法

    3、全局页面置环算法

    ①工作集置换算法②缺页率置换算法③抖动和负载控制

    二、最优算法、先进先出算法和最近最久未使用算法

    1、最优界面置换算法: 

    ①基本思路:选择内存中等待时间最长(未来最长时间不访问)的页作为置换页面。 

    ②算法实现:缺页时,计算内存中每个逻辑页面的下一次访问时间;选择未来最长时间不访问的页面。

    ③算法特征:只能是理想情况,OS无法实现(不知道未来情况)。 

    可以作为最佳的标准,在第二遍运行时利用第一次的访问轨迹使用最优算法。其他算法应尽量逼近。

    2、先进先出算法( first-in first-out FIFO)

    ①思路:选择在内存中驻留时间最长的页面并淘汰之。OS维护着一个队列链表,淘汰首位,添加末位。

    ②实现:维护一个记录所有位于内存中的逻辑页面;链表元素按驻留内存时间排序,链首最长,链尾最短;出现缺页时,选择链首页面进行置环,新页面加到链尾。

    ③特征:性能较差,调出的页面可能是常用页面(驻留时间长,本身就说明可能常用),有belady现象(给的物理页帧越多反而缺页越频繁)。

    3、最近最久未使用算法(least recently used LRU)

    ①思路:选择最久未使用的那个页面淘汰掉。

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

    ②实现:缺页时,计算内存中每个逻辑页面上一次访问时间;选择上一次使用到当前时间最长的页面

    ③两种可能的实现方法:

    Ⅰ、页面链表:系统维护一个页面链表,最近刚使用的页面最为首节点,最久未使用的页面作为尾节点,每次访问内存动态更新头结点。缺页中断时,淘汰末位的页面。

     

    Ⅱ、活动页面堆栈:访问某页时,将此页号入栈,并去除栈内的重复页。淘汰栈底的页面。(栈是先进后出,只有栈顶开口,怎么push栈底?)

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

     

    三、时钟置环算法和最不常用算法

    1、时钟页面置换算法 clock ——LRU的近似,FIFO的改进

    ①思路:用到页表项的访问位(access bit),当一个页面被装入内存时,把该位初始化为0,被访问(读/写)时,硬件把它置为1. 而OS会定期清0。(1—最近被访问,0—-未访问)

    把各个页面组成环形链表类似一个clock,指针指向最老的页面。

    ②算法:当发生一个缺页中断时,考察指针所指的最老页面,访问位是0则淘汰,如果是1则置为0,然后指针向下移动一格。如此下去直到淘汰某页。

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

    ③算法实现:页面装入内存时,访问位初始化为0;访问页面(读/写)时,访问位置1;缺页时,从指针当前位置顺序检查环形链表【访问位为0,则置环该页;访问位为1,则访问位置0,并指针移动到下一个页面,直到找到可置换得页面】

     

    2、改进的Clock算法

    ①思路:减少修改页得缺页处理开销

    ②算法:在页面增加修改位,并在访问时进行相应修改;缺页时,修改页面标志位,以跳过有修改得页面

    3、最不常用算法(least frequently used)LFU 

    ①思路:选择置换访问次数最少的那个页面 

    ②实现:对每个页面设置访问计数器,当一个页面被访问时++。淘汰数值最小的那个。 

    ③特征:硬盘计数器空间开销,排序查找时间开销;

     

    4、LRU/LFU区别:LRU考察的是多久未访问,时间越短越值得留在内存,LFU是访问次数/频率,次数越多越好。

    反例:一个页面在进程开始时使用的很多,但以后就不使用了。此时LFU就不适用了。

    把时间也考虑进去,在一段时间内考察LFU。比如,定期把次数寄存器右移一位。

     

     

    四、Belady现象和局部置环算法

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

    原因:FIFO算法的置换特征与进程访问内存的动态特征矛盾;被它置换出去的页面并不一定是进程近期不会访问的

    2、综合比较局部页替换算法

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

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

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

    ② LRU、FIFO和Clock的比较:开销上,LRU开销大,FIFO开销小但BELADY,折中的是Clock算法,开销较小。对内存中还未被访问的页面,Clock效果等同LRU。Clock对曾经被访问过的则不能记住其准确位置,而LRU算法可以。

     

    五、工作集置环算法

    1、全局置换算法

    ①思路:全局置换算法为进程分配可变数目的物理页面

    ②解决问题:进程在不同阶段的内存需求是变化的;分配给进程的内存也需要在不同阶段有所变化;全局置换算法需要确定分配给进程的物理页面数

    2、工作集(working set)

    ①定义:一个进程当前使用的逻辑页面集合,可以用一个二元函数W(t,Δ),t是当前执行时刻,Δ是工作集窗口(working-set window),一个定长的页面访问的时间窗口。t+Δ构成了一个时间段,W(t,Δ)就是在当前时刻t之前的Δ时间内所有访问页面组成的集合,在随t不断更新。| W(t,Δ)|是工作集的大小即页面数目。

    ②工作集的变化:进程开始后,随着访问新页面逐步建立较稳定的工作集,当内存访问的局部性区域的位置大致稳定时| W(t,Δ)|波动很小,在过渡阶段,则会快速扩张和收缩过渡到下一个稳定值。有波峰,有波谷。

    3、常驻集

    ①定义:在当前时刻,进程实际驻留在内存当中的页面集合。

    ②工作集与常驻集的关系:工作集是固有性质,常驻集取决于系统分配给进程的物理页面数目和所采用的置换算法。

    ③缺页率与常驻集的关系:如果一个进程的常驻集与工作集尽量重叠,则不会造成太多缺页中断。当常驻集大小达到某个数目后,再分配物理页帧也不会有明显下降的缺页率——可以把多出来的物理页帧分给其他程序了。

    4、工作集置换算法

    ①思路:换出不在工作集中的页面

    ②实现方法:访存链表:维护窗口内的访存页面链表;在访存时,换出不在工作集的页面;缺页时,换入页面,更新访存链表。

     

    六、缺页率置环算法

    1、缺页率

    缺页率=缺页次数/内存访问次数 =1/缺页的平均时间间隔

    影响因素有页面置换算法,分配给进程的物理页面数目(越多越小),页面本身的大小(页面大则会小),编程方法(局部性好就会小)

    2、缺页率算法(PFF, page fault frequency)

    ①思路:动态调整常驻集的大小。性能较好,但增加了系统开销 

    ②算法若缺页率高则增加工作集(Δ)来分配更多物理页面,若过低则减少工作集来减少其物理页面。使缺页率保持在一个合理的范围内。各个程序之间保持一个平衡。

    ③具体机制:根据缺页的时间间隔来判断 动态更新

    保持追踪缺页概率,记录上次缺页到这次的时间间隔 t(current) -t(last),与T比较(自定义一个合理的间隔),若大于T,则缺页率小,置换所有在 [t(current) ,t(last)]时间内没有被引用的页;否则增加缺失页到工作集中。

     

    七、抖动和 负载控制

    1、抖动问题(thrashing)

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

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

    2、加载控制(better criteria for load control: adjust MPL so that):

     

     

     

     

    展开全文
  • 页面置换算法全局页面置换算法工作集和常驻集工作集页置换算法缺页率页面置换算法抖动问题 全局页面置换算法 工作集和常驻集 局部页面置换算法都针对一个程序/进程来进行操作的,然而OS可以同时执行多个程序,如果每...

    全局页面置换算法

    工作集和常驻集

    局部页面置换算法都针对一个程序/进程来进行操作的,然而OS可以同时执行多个程序,如果每一个程序都采取一个固定的局部页面置换算法会带来一些问题,所以我们引入全局页面置换算法。
    在这里插入图片描述
    程序的访问特征是可变的,可能一开始需要的内存比较多,中间可能需要的很少,结束时又很多,也就说对物理内存的需求是可变的。而前面的局部页面置换算法都有一个大前提:分配的物理页帧是固定的
    由于OS可以同时跑多个程序,那么这时候如果给每一个程序分配一个固定的物理页帧,就限制了程序的灵活性。我们想要根据程序进行的不同阶段,动态分配给其不同的物理内存大小。这就是我们全局页面置换算法要考虑到的。
    接下来要介绍的所有算法,都基于一个大前提。
    如果一个算法要有效,那么我们需要这个程序具有局部性。程序局部性原理越好,LRU/clock算法就会产生更少的缺页次数。所以我们想要表现和分析局部性——工作集
    在这里插入图片描述
    一个进程一个时间段内的逻辑页面的集合。t是当前时刻,△是t时刻开始后的一段时间。Wt,W(t,△)是t时刻开始△时间段内的所有访问到的页面集合。t是一直变的,在这种情况下工作集窗口一直在滑动,访问页的集合也会不断变化。Wt,|W(t,△)|是这个集合的大小。
    注意:工作集窗口不包含当前时刻所对应的页面
    在这里插入图片描述
    起始时间是t1,△是从过去到现在一固定长度。表示了程序在不同运行阶段对内存访问特点的展现,t2的工作集的局部性就很好,t1相对于t2的局部性稍差,但是仍然具有一定的局部性。
    下图便于理解:
    在这里插入图片描述

    在这里插入图片描述
    工作集在执行过程中会随着程序执行的特点而变化。可能一开始访问的页不具有局部性,但是到访问到一定区域他的工作集大小也会比较稳定。
    在这里插入图片描述
    常驻是常驻内存的意思,常驻集是当前时刻正在运行的程序驻留在内存中的页面集合。如果说工作集体现了运行中程序在运行过程中在对页面访问的属性,是程序本身的固有属性;常驻集是OS和计算机系统给应用程序分配的物理页-空间的大小,以及采取的页面置换算法来决定到底将哪些页面放入内存。工作集表示要访问的页面有哪些,这些页面有可能不在内存中,这是和常驻集的最大不同。我们希望工作集的页都在常驻集里,一旦工作集中某些页不在常驻集,就会产生缺页中断,所以我们希望这两个集合尽量是重叠的,这样会使得缺页率较小。OS在程序运行时可以分配的常驻集大小是不定的,分配的物理页不是越多越好,可能当物理页多到一定程度时,意义不大了,此时我们想将多余的页分配给其他程序,动态调整物理页大小使得整体的缺页率较低。只要整体缺页次数少,则整体系统性能就会高。

    工作集页置换算法

    在这里插入图片描述
    工作集窗口里的页代表当前这段时间内被访问的页,如果其中的页需要替换时,需要替换不在工作集中的页;随着程序执行,窗口在挪动,评议过程中某个页不再在国工作集窗口内,则这个页也需要丢掉,并不是一定要等到缺页时再置换出去。
    看一个例子:【个人感觉用链表理解更加容易】
    在这里插入图片描述
    工作集窗口τ=4

    阶段 工作集窗口内容
    0 在这里插入图片描述
    1 在这里插入图片描述
    2 在这里插入图片描述
    3 在这里插入图片描述
    4 在这里插入图片描述
    5 在这里插入图片描述
    6 在这里插入图片描述
    7 在这里插入图片描述
    8 在这里插入图片描述
    9 在这里插入图片描述
    10 在这里插入图片描述

    它和前面的局部页面替换算法相比,最大的变化是取决于工作集窗口。所以超出窗口的老页被换出,保证物理内存中始终有足够多的页存在,给其他运行的程序提供更多的内存,从而减少页面置换次数。从整个系统的层面上减少缺页率。

    缺页率页面置换算法

    在这里插入图片描述
    依据:缺页的频度。缺页次数越多也就意味着应该分配给该程序更多的物理页使之缺页率降低;如果缺页次数很少,也就意味着常驻集/分配的物理内存足够多了,所以我们将内存压缩一下。通过缺页率变化来间接地体现出当前程序对内存的需求,从而动态调整常驻集的大小。
    =访×100%缺页率=\frac{缺页次数} {内存访问次数}\times100\%
    影响缺页率的因素:
    1.缺页算法:不同算法会产生不同的缺页率
    2.分配给进程的物理页大小:分配给进程的物理页越多,一般情况下产生的缺页越小
    3.页面本身大小:页面大则缺页次数也会减少
    4.程序的编写方法:局部性好,缺页率低。
    在这里插入图片描述
    若运行程序缺页率高我们会增加工作集,希望他访问的页尽量在内存中,可以降低缺页率。如果缺页率过低,意味着可能分配的内存比较多,则可以减少工作集来减少程序需要的物理页面(意味着常驻集也被减少),使得每个程序的缺页率保持在一个合理的范围内。整体系统的性能从而平衡地提高。
    在这里插入图片描述
    T是一个阈值,如果缺页与上次缺页之间的时间间隔是大的,则说明缺页率低,应该减少工作集空间。如果缺页与上次缺页之间的时间间隔是小的,说明缺页率高,应该增加工作集空间。
    例子:设阈值T=2。工作集窗口τ=4
    在这里插入图片描述

    阶段 过程
    0 默认阶段下,工作集空间内包含ade三个页面
    1 缺页发生,以为没有上一次缺页所以忽略。加入新页c。
    2~3 tctlTt_c-t_l\leq T且没有缺页,工作集不变
    4 tctlTt_c-t_l\geq T,清除在该段时间内未被访问的所有页,在1~3阶段访问了c和d,所以保留cd且因为缺页加入b,则此时工作集内的页为bcd
    5 同2~3阶段
    6 tctlTt_c-t_l\leq T且缺页,加入需要的页e。此时工作集窗口内的页是bcde
    7~8 同5
    9 保留与上次缺页(阶段6)之间访问过的是页ce,且加入当前需要访问的页a
    10 tctlTt_c-t_l\leq T且缺页,加入需要的页d。此时工作集窗口内的页是aced

    与工作集页置换算法的必须在分配的物理空间满时才替换出去相比,该算法即便空间不满在满足一定条件是也会清理一部分空间。从而整体来说使得一些经常访问的页驻留在内存中,对于OS而言,要应对多个正在运行的程序,那么采取全剧页替换算法要优于局部页替换算法。

    抖动问题

    如果,常驻集∈工作集会产生缺页。
    简单来说,如果常驻集包含于工作集,也就意味着在访问内存时,需要频繁进行页面置换,从而增大开销与运行速度。我们需要一个合适的常驻集,尽量使二者一致,这样产生的缺页就会很少且并发程序可以更多。
    在这里插入图片描述
    x轴:有多少程序在跑
    y轴:CPU利用率
    一般情况下CPU利用率是比较高的,但是如果在某段时间内进行大量页面换入换出,使得程序进程变慢,CPU利用率大量降低。
    分析图标,随着同时执行的程序增多,内存很快就用完了,然后会产生大量缺页,OS需要大量的换入换出操作或者中断处理操作。因为频繁执行IO操作,这时候所有的CPU时间都去用来做置换页面的操作,程序利用率大大降低,机器越来越慢。
    因此我们希望能将其维持在峰值,找到一个平衡点。我们希望两个缺页产生的平均时间MTBF完成一次缺页的中断服务的时间PFST尽量相等,二者比值越大意味着缺页频度低,此时CPU大部分时间用于跑程序。随着后来程序增多,缺页次数越来越多。在NIO-balance点,并发执行的程序个数比较多且系统整体利用率比较高。OS可以根据当前CPU利用率来动态调整应该让系统里放多少程序,只要个数合适,就可以领内存抖动现象得到改善。即便只有一个程序运行,如果占据内存足够多,那么也有可能产生抖动现象。
    我们希望通过OS管理,整个系统利用率高且跑的程序尽量多。

    展开全文
  • 页面置换算法

    千次阅读 2015-06-03 10:57:56
    页面锁定framelocking:常驻的逻辑页面,操作系统的关键部分,要求相应速度快的代码和数据,页表中的锁定标志位lock bit。   页面置换算法分类: 局部页面置换算法:置换范围仅限于当前进程占用的物理页面;

    页面置换算法的概念:

        出现缺页异常,则需调入新页面二内存已满时,置换算法选择被置换的物理页面。尽可能减少页面的调如调出次数,把未来不再访问或短期内不访问的页面调出。

    页面锁定framelocking:常驻的逻辑页面,操作系统的关键部分,要求相应速度快的代码和数据,页表中的锁定标志位lock bit。

     

    页面置换算法分类:

    局部页面置换算法:置换范围仅限于当前进程占用的物理页面;

    最优算法、先进先出算法、最近最久未使用算法;

    时钟算法、最不常用算法。

    全局页面置换算法:置换范围是所有可能可换出的物理界面;

                      工作集算法、缺页率算法。

    局部页面置换算法:

    (1)最优页面置换算法OPT,optimal:缺页时,计算内存中每个逻辑页面的下一次访问时间,选择未来最长时间不访问的页面,缺点是太理想,实际无法实现。

    最优页面置换算法实例


    (2)先进先出算法First In First Out,FIFO:在内存驻留时间最长的页面进行置换。维护一个记录逻辑页面链表,缺页时首页面进行置换,新页面加到链尾。

    缺点是:性能较差,进行分配物理空间页面数增加时,缺页不一定能减少(Belady现象,页面刚刚被置换,但是下一次又用上),所以很少单独使用。


    (3)最近最久未使用算法Least Recently Used,LRU:选择最长时间没有 被引用的页面进行置换(假设在过去经常访问,未来也经常访问),缺点是开销比较大。

    实现方法:

    页面链表,按照最近一次访问的时间排序,链尾是最近最久未使用的。

    活动页面栈:访问页面时,将此页号压入栈顶,并抽调之前相同的页号,缺页时,置换栈底的页面。

     

    (4)时钟页面置换算法Clock:仅对页面的访问情况进行大致统计

    数据结构:页表项中增加访问位,页面组成环形链表,指针指向最先调入的页面。

    算法是:访问时记录下访问的情况,缺页时,从指针处开始顺序查找违背访问的页面进行置换。在FIFO和LRU中进行折中考虑。(若访问位为0.则可以替换;访问位1则将访问位置为0,并移至下一位)

     

    (5)最不常用算法Least Frequently Used,LFU:缺页时,置换访问次数最少的页面。

    实现:每个页面设置一个访问技术,每次访问计数+1,缺页时置换最小的页面。

    LRU和LFU:前者是关注多久未访问,后者关注访问次数。


    (6)Belady现象:物理页面增多,缺页次数反而增多的异常现象。

    (7)LRU、LFU、Clock的比较

    LRU性能好,但开销大;FIFO开销少,会发生Belady现象;Clock算法是两者的折中。

     

    全局页面置换算法:为进程分配可变数目的物理页面。

    (1)工作集置换算法:一个进程当前正在使用的逻辑页面集合,可表示为二元函数W(t,△),在当前时刻的△时间窗口中所有访问页面所组成的集合,绝对值是页面数目。常驻集:系统分配给进程的物理页面数目。

    访存时,换出不在工作集的页面,更新访存链表;缺页时换入页面,更新访存链表。


    (2)缺页率置换算法PFF,Page-Fault-Frequency,通过调整常驻集使得每个进程的缺页率保持在一个合理的范围:缺页率过高,则增加常驻集;缺页率过低,则减少常驻集。

    缺页率:缺页次数/内存访问次数。影响因素:置换算法、物理页面数目、页面大小、程序编写方法。

    (3)抖动和负载控制

    抖动thrashing,进程物理页面太少,不能包含工作机;造成大量缺页,频繁置换,进程运行速度慢。原因是:驻留在内存的进程数据增加,分配给每个进程的物理页面减小,缺页率上升。操作系统需要再并发水平和缺页率之间达到一个平衡。

    负载控制:MPL,平均缺页间隔时间MTBF=缺页异常处理时间PFST。


    展开全文
  • 功能与目标硬盘的读写要比内存慢一到两个数量级,所以要尽可能减少页面的换进换出次数有一些需要常驻内存,比如操作系统实验设置与评价方法如何分析比较最优页面置换算法(OPT,optimal)理想状态下我们想要替换很长一...
  • JVM垃圾回收算法

    2018-06-26 01:45:24
    从效率跟空间上来看这种算法存在不足:标记跟清除都需要扫描所有对象,有些对象是常驻内存的,存在着很多多余的操作;清除之后空间存在很多的不连续,以后创建对象地址分配无法找到连续的内存,会频繁的触发垃圾回收...
  • 本篇文章简要总结虚拟存储中的页面置换算法,结构组织如下: ...描述必须常驻内存中的逻辑页 OS 的关键部分 要求响应速度的 code/data 页表项中的锁定页(lock bit) 评价方法 记录访存的页面轨迹(编号) 模拟/记录缺页次数
  • 页面替换算法 1.局部页面置换算法 1.1最优算法OPT 1.2先进先出算法FIFO 1.3最近最久未使用算法LRU 1.4时钟置换算法CLOCK ...1.5改进时钟算法 ...1.6最不常用算法LFU ...3.全局页面置换算法 ...3.1工作集和常驻集 ...
  • 描述必须常驻内存的逻辑页面 操作系统的关键部分 要求响应速度的代码和数据 页表中的锁定标志位(lock bit) 置换算法的评价方法: 模拟页面置换行为,记录产生缺页的次数 更少的缺页, 更好的性能 页面置换算法分类 ...
  • 操作系统页面置换算法c++

    千次阅读 2016-03-21 18:06:01
    描述必须常驻内存的逻辑页面,操作系统的关键部分,要求响应速度的代码和数据,页表中的锁定标志位 置换算法的评价: 记录所有存储单元的轨迹。模拟置换算法,缺页率。 局部置换算法: 仅限于
  • 六、页面置换算法

    千次阅读 2018-04-17 21:46:48
    页面置换算法功能:当出现缺页异常,需调入新页面而内存已满时,置换算法选择被置换的物理页面目标:尽可能减少缺页中断(页面的换入换出)次数。具体来说,把未来不再使用的或短期内较少使用的页面换出,通常只能在...
  • 操作系统(thuOS)笔记(六) 第九讲 页面置换算法9.1 置换算法的概念9.2 最优算法、先进先出算法和最近最久未使用算法最优置换算法(OPT,optimal)先进先出算法(First-In First-Out, FIFO)最近最久未使用算法...
  • 第6章 页面置换算法

    2020-12-29 22:44:46
    第6章 页面置换算法 6.1 页面置换算法的概念 (1)功能目标 功能:当缺页异常发生时,需要...用于描述必须常驻内存的逻辑页面 操作系统的关键部分 要求响应速度的代码和数据 实现方法是,在页表中添加锁定标志位(lock bi
  • 2.1 常驻内存拥塞控制算法 3基本操作 3.1 算法的注册/注销tcp_register_congestion_control 3.2 套接字指定拥塞控制算法tcp_set_congestion_control 3.3 设置默认算法tcp_set_default_congestion_control Linux...
  • GC(是jvm垃圾回收分代收集算法) ...这样的话两个都计数都不可能为0,都会成为常驻内存,引起堆爆 2:复制算法(Copying)(新生区的算法) 年轻代中使用的是Minor GC,这种GC算法采用的是复制算法(Co
  •  进程线性地址空间里的页面不必常驻内存,在执行一条指令时,如果发现他要访问的页没有在内存中(存在位为0),那么停止该指令的执行,并产生一个页不存在异常,对应的故障处理程序可通过从外存加载该页到内存的...
  • 页面锁定:用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程。实现的方法是,在页表中添加锁定标志位。 最优页面置换算法 基本思路: 当一个缺页中断发生时,对于保存在内存当中的每一个逻辑页面,...
  • 工作集:一个进程当前正在使用的逻辑页面集合, ...工作集是进程在运行过程中固有的性质,而常驻集取决于系统分配的进程的物理页面数目,以及采用的页面置换算法 如果一个进程的整个工作集都在内存当中,即
  • 页面置换算法   功能:当出现缺页异常,需调入新页面而内存已满时,置换算法选择被置换的物理页面 ... 页面锁定(frame locking):用于描述必须常驻内存的操作系统的关键部分,或时间关键的应用进程(time-...
  • 当内存中的页面满了之后,需要的数据又在磁盘虚拟内存中,可以使用页面置换算法将需要的页置换到物理内存中。 1、最优页面置换算法 功能:当缺页中断发生...页面锁定(frame locking):用于描述必须常驻内存的操...
  • 一、用户标签 用户标签今日头条常用的用户标签包括用户感兴趣的类别和主题、...常驻地点来自用户授权访问位置信息,在位置信息的基础上通过传统聚类的方法拿到常驻点。常驻点结合其他信息,可以推测用户的工作地点...
  • 背景随着越来越多的AI算法在端侧进行部署(部分是常驻系统的),系统的内存资源消耗变得越来越严重,有些算法只需要几MB的运行内存,有些则要几百MB,程序总运行内存过高可能导致APP卡顿甚至异常退出。如果能够将AI...
  • 功能: 置换算法是指当出现缺页异常时,需要调入新页面而内存已满时,置换算法选择被置换的物理...页面锁定是用来描述某些必须常驻内存的逻辑页面,比如操作系统的关键部分,再比如一些要求响应速度的代码和数据, ...
  • 当内存中的页面满了之后,需要的数据又在磁盘虚拟内存中,可以使用页面置换算法将需要的页置换到物理内存中。...页面锁定(frame locking):用于描述必须常驻内存的操作系统的关键部分或时间关键的应用程序
  • 父子进程的调度由操作系统来负责,具体先调度子进程还是父进程由系统的调度算法决定,当然可以在父进程加上延时或是调用进程回收函数 pcntl_wait 可以先让子进程先运行,进程回收的目的是释放进程创建时占用的内存...
  • 1页面置换算法 目录 1.1 功能目标 功能:当缺页中断发生,需要调入新的页面而内存已满时,选择内存当中哪个物理页面被置换。 目标:尽可能减少页面的换入换出次数(即缺页中断的次数)。把未来不再使用的或短期...
  • 局部页替换算法 一、最优页面置换算法 功能目标 功能:当缺页中断发生,需要调入新的页面。内存已满时,选择内存当中哪个物理页面被...页面锁定(frame locking):用于描述必须常驻内存的操作系统的关键部分或时间...

空空如也

空空如也

1 2 3 4 5 6
收藏数 107
精华内容 42
关键字:

常驻算法