十二、全局置换算法

2021年9月1日 8点热度 0条评论 来源: Dragon Fly

文章目录

1、局部置换算法的问题

\qquad 局部置换算法给每个程序分配固定的页帧数,但是一个程序在不同的运行阶段所需要的页帧数量可能大不相同,因此局部置换算法总是不会分配刚好的页帧数程序,总是会造成一定的页帧冗余或者页帧不足的情况。

2、工作集模型

\qquad 之前介绍的各种页面置换算法,都是基于程序的局部性原理,若局部性原理不成立,那么各种页面置换算法就没有什么分别,也没有什么意义。例如:假设进程对逻辑页面的访问顺序是1,2,3,4,5,…,即单调递增,那么在物理页面数有限的情况下,不管采用何种置换算法,每次的页面访问都必然导致缺页中断。
\qquad 如果局部性原理是成立的,那么需要用到工作集模型来证明它存在并对它进行定量地分析。

2.1 工作集

\qquad 工作集值得是一个进程当前正在使用的逻辑页面的集合,可以用一个二元函数 W ( t , Δ ) W(t, \Delta ) W(t,Δ)来表示:其中
t : t: t指当前的执行时刻;
Δ : \Delta: Δ称为工作集窗口,寄一个定长的页面访问的时间窗口;
W ( t , Δ ) : W(t, \Delta ): W(t,Δ)表示在当前时刻 t t t之前的 Δ \Delta Δ时间窗口中的所有页面所组成的集合(随着 t t t的变化,该集合也在不断变化)
∣ W ( t , Δ ) ∣ : |W(t, \Delta )|: W(t,Δ)指工作集的大小,即页面的个数
\qquad 工作集大小的变化:进程开始执行后,随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定之后,工作集的大小也大致稳定;局部性区域的位置改变时,工作集快速扩张和收缩过渡到下一个稳定值。

\qquad 上图是工作集的一个示意图。

2.2 常驻集

\qquad 常驻集指在当前时刻,进程实际驻留在内存当中的页面集合
⋅ \qquad\cdot 工作集市进程在运行过程中固有的属性,而常驻集取决于系统分配给进程的物理页面数目,以及所采用的的页面置换算法;
⋅ \qquad\cdot 如果一个进程的整个工作集都在内存当中,即常驻集 ⊆ \subseteq 工作集,那么进程将很顺利地运行,而不会造成太多的缺页中断(直到工作集发生剧烈变动,从而过渡到另一个状态);
⋅ \qquad\cdot 当进程常驻集的大小达到某个数目之后,在给他分配更多的物理页面,缺页率也不会明显下降。

3、两个全局置换算法

3.1 工作集页置换算法

\qquad 追踪前 τ \tau τ个访问的页面的引用,建立工作集, τ \tau τ称作工作集的时间窗口大小, e x a m p l e : τ = 4   r e f e r e n c e s example:\tau = 4 \ references exampleτ=4 references。在程序执行的过程中,不是等到缺页之后才开始进行置换,而是一旦某个页面不属于工作集了,则直接将这个页面从工作集之中丢掉。

\qquad 上图是工作集页置换算法的一个示意图。

3.2 缺页率页面置换算法

\qquad 可变分配策略: 常驻集大小可变。例如:每个进程在刚开始运行的时候,先根据程序大小给它分配一定数目的物理页面,然后再进程运行的过程中,再动态调整常驻集的大小。
\qquad ·可以采用全局页面置换算法的方式,当发生一个缺页中断时,被置换的页面可以是在其他进程当值的,各个并发进程竞争地使用物理页面。
\qquad ·优缺点:性能较好,但增加了系统开销。
\qquad ·具体实现:可以采用缺页率算法(PFF, Page Fault Frequency)来动态调整常驻集的大小。
\qquad · **缺页率:**表示“缺页次数 / 内存访问次数”(比率),或者“缺页平均时间间隔的倒数”。影响缺页率的因素包括以下几个方面:页面置换算法;分配给进程的物理页面数目;页面本身的大小;程序的编写方法。
\qquad 在程序开始运行时,若运行的程序缺页率过高,则通过增加工作集来分配更多的物理页面;若运行的程序的缺页率过低,则通过减少工作集来减少他的物理页面数量。力图使运行的每一个程序的缺页率在一个合理的范围之内。
\qquad 缺页率算法直观的想法就是:当缺页率高的时候,增加工作集;当缺页率低的时候,减少工作集。缺页率算法的算法流程如下所示:

保持追踪缺失发生概率
\qquad 当缺页发生时,从上次页缺失起计算这个时间,记录上次缺页的时间为 t l a s t t_{last} tlast,记录本次缺页的时间为 t c u r r e n t t_{current} tcurrent
\qquad 若发生页缺之间的时间是“大”的,之后减少工作集,
\qquad e.g. i f   t c u r r e n t − t l a s t > T if \ t_{current}-t_{last}>T if tcurrenttlast>T,之后从内存中移除所有在 [ t l a s t ,   t c u r r e n t ] [t_{last}, \ t_{current}] [tlast, tcurrent]时间内没有被引用的页。
\qquad 若发生页缺失的时间是“小”的,之后增加工作集,
\qquad e.g. i f   t c u r r e n t − t l a s t < T if \ t_{current}-t_{last}<T if tcurrenttlast<T,之后增加缺失页到工作集之中。


\qquad 上图是缺页率页置换算法的一个示意图。

THE END

    原文作者:Dragon Fly
    原文地址: https://blog.csdn.net/weixin_43160744/article/details/120003882
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。