4.5.2.4 页面替换策略页面替换当主存空间已装满而又要装入新页时，必须按一定的算法把已在主存的一些页调出去，这个工作称 页面替换 。
页面替换就是用来确定应该淘汰哪页的算法,也称淘汰算法 。
选用了一个不适合的算法,就会出现这样的现象：刚被淘汰的页面又立即要用,因而又要把它调入,而调入不久再被淘汰,淘汰不久再被调入 。 如此反复,使得整个系统的页面调度非常频繁以至于大部时间都化在来回调度页面上 。 这种现象叫做,抖动,(Thrashing)，
又称,颠簸,,一个好的调度算法应减少和避免抖动现象 。
替换策略要处理的是,
当把一个新的页面调入主存时,选择己在主存的哪个页面作替换。由于下列因素,使得替换策略变得比较困难,
① 分给每个活跃进程多少页框?
② 页面替换时,仅限于缺页中断进程还是包括主存中所有页面?
③ 在被考虑的压面集合中,选出哪个页面进行替换?
一个理论算法假定作业 p共计 n页,而系统分配给它的主存块只有 m块 （ m,n均为正整数,且１ ≤m≤n）,即最多主存中只能容纳该作业的 m页 。 如果作业
p在运行中成功的访问次数为 s（ 即所访问的页在主存中 ）,不成功的访问次数为 F（ 即缺页中断次数 ）,则总的访问次数Ａ为：
A = S + F
又定义：
f = F / A
则称 f为缺页中断率 。 影响缺页中断率 f的因素有：
l主存页框数 。 作业分得的主存块数多,则缺页中断率就低,反之,缺页中断率就高 。
l页面大小 。 如果划分的页面大,则缺页中断率就低,否则缺页中断率就高 。
l页面替换算法 。
l程序特性 。 程序编制的方法不同,对缺页中断的次数有很大影响,程序的局部性要好 。
一个程序要将 128× 128的数组置初值,0”。
现假定分给这个程序的主存块数只有一块,页面的尺寸为每页 128个字,数组中的元素每一行存放在一页中,开始时第一页在主存 。 若程序如下编制：
Var A,array[1..128] of array [1..128] of integer;
for j,= 1 to 128
do for i,= 1 to 128
do A[i][j]:=0
则每执行一次Ａ [i][j],＝０就要产生一次缺页中断,于是总共要产生 （ 128× 128－ 1） 次缺页中断 。 如果重新编制这个程序如下：
Var A,array[1..128] of array[1..128] of integer;
for j,= 1 to128
do for i,= 1 to 128
do A[i][j],= 0
那么,总共只产生 （ 128－ 1） 次缺页中断 。
理论算法 (最佳算法 )
当要调入一页而必须淘汰一个旧页时,所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页 。 这样的调度算法使缺页中断率为最低 。 然而这样的算法是无法实现的因为在程序运行中无法对以后要使用的页面作出精确的断言 。 不过,这个理论上的算法可以用来作为衡量各种具体算法的标准 。 这个算法是由
Belady提出来的,所以叫做 Belady算法,又叫做最佳算法 （ Optimal） 。
1）随机页面替换算法要淘汰的页面是由一个随机数产生程序所产生的随机数来确定,选择一个不常使用的页面会使系统性能较好,但这种调度算法做不到这一点,虽很简单但效率却低,
一般不采用 。
2)先进先出页面替换算法 （ FIFO)
先进先出调度算法是一种低开销的页面替换算法，基于程序总是按线性顺序来访问物理空间这一假设。
这种算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。
实现技术一种实现方法是系统中设置一张具有 m个元素的页号表,它是由Ｍ个数：
P[0],P[1],…,P[m-1]
所组成的一个数组,其中每个 P[i] (i =0,1,… m-1)
存储一个在主存中的页面的页号 。 假设用指针 k
指示当前调入新页时应淘汰的那一页在页号表中的位置,则淘汰的页号应是 P[k]。 每当调入一个新页后,执行
P[k],= 新页的页号 ;
k,= （ k+1） mod m;
另一个简单的实现算法引入指针链成队列,只要把进入主存的页面按时间的先后次序链接,新进入的页面从队尾入队,淘汰总是从队列头进行 。
3）最近最少用页面替换算法（ LRU,least
Recently used）
该算法淘汰的页面是在最近一段时间里较久未被访问的那一页 。 它是根据程序执行时所具有的局部性来考虑的,即那些刚被使用过的页面,
可能马上还要被使用,而那些在较长时间里未被使用的页面,一般说可能不会马上使用到 。
维护一个特殊的队列该队列中存放当前在主存中的页号,每当访问一页时就调整一次,使队列尾总指向最近访问的页,队列头就是最近最少用的页 。 显然,发生缺页中断时总淘汰队列头所指示的页；而执行一次页面访问后,需要从队列中把该页调整到队列尾 。
例：给某作业分配了三块主存，该作业依次访问的页号为,4,3,0,4,1,1,2,3,2。于是当访问这些页时，页面淘汰序列的变化情况如下：
4 4
3 4 3
0 4 3 0
4 3 0 4
1 0 4 1 3
1 0 4 1
2 4 1 2 0
3 1 2 3 4
2 1 3 2
LRU算法实现第一种模拟方法可以通过设置标志位来实现。
给每一页设置一个引用标志位 R，每次访问某一页时，由硬件将该页的标志 R置 1，
隔一定的时间 t将所有页的标志 R均清 0。
在发生缺页中断时，从标志位 R为 0的那些页中挑选一页淘汰。在挑选到要淘汰的页后，也将所有页的标志 R清 0。
第二种模拟方法是为每个页设置一个多位寄存器 r
当页面被访问时,对应的寄存器的最左边位置 1；每隔时间 t,将 r寄存器右移一位；在发生缺页中断时,找最小数值的 r寄存器对应的页面淘汰 。
例如,r寄存器共有四位，页面 P0、
P1,P2在 T1,T2,T3时刻的 r寄存器内容如下：
页面 时刻
T1 T2 T3
P0 1000 0100 1010
P1 1000 1100 0110
P2 0000 1000 0100
4)第二次机会页面替换算法
FIFO算法可能会把经常使用的页面淘汰掉,可以对 FIFO算法进行改进,把 FIFO算法与页表中的,
引用位,结合起来使用,算法可实现如下：
首先检查 FIFO中的队首页面 (这是最早进入主存的页面 ),如果它的,引用位,是 0,那么这个页面既老又没有用,选择该页面淘汰 ; 如果它的,引用位,
是 1,说明虽然它进入主存较早,但最近仍在使用 。
于是把它的,引用位,清成 0,并把这个页面移到队尾,把它看作是一个新调入的页 。 这一算法称为第二次机会 (second chance)算法,其含义是最先进入主存的页面,如果最近还在被使用的话,仍然有机会作为像一个新调入页面一样留在主存中 。
5）时钟页面替换算法 (Clock Policy)
算法的实现要点如下：
l一个页面首次装入主存时,其,引用位,置 0。
l在主存中的任何一个页面被访问时,其,引用位,
置 1。
l淘汰页面时,存储管理从指针当前指向的页面开始扫描循环队列,把所迁到的,引用位,是 1的页面的,引用位,清成 0,并跳过这个页面 ; 把所迁到的,引用位,是 0的页面淘汰掉,指针推进一步 。
扫描循环队列时,如果迁到的所有页面的,引用位,为 1,指针就会绕整个循环队列一圈,把碰到的所有页面的,引用位,清 0;指针停在起始位置,并淘汰掉这一页,然后,指针推进一步 。
时钟页面替换算法的一个例子
Page9
use=1
Page19
Use=1 Page1
Use=0
Page45
Use=1
Page191
Use=1
Page556
Use=0
Page13
Use=0
Page67
Use=1
Page33
Use=1
Page222
Use=0
下一个帧指针
n 0
1
2
3
4
56
7
8
（ a） 一个页替换前的缓冲区状态
Page9
use=1
Page19
Use=1 Page1
Use=0
Page45
Use=0
Page191
Use=1
Page727
Use=1
Page13
Use=0
Page67
Use=1
Page33
Use=1
Page222
Use=0
n 0
1
2
3
4
56
7
8
（ b） 下一页替换后的缓冲区状态
1第 1页框改进时钟页面替换算法如果把页表中的,引用位,和,修改位,
结合起来使用可以,共组合成四种情况：
(1)最近没有被引用,没有被修改 (r=0,m=0)
(2)最近被引用,没有被修改 (r=1,m=0)
(3)最近没有被引用,但被修改 (r=0,m=1)
(4)最近被引用过,也被修改过 (r=1,m=1)
改进的时钟算法可如下执行：
步 1：选择最佳淘汰页面,从指针当前位置开始,
扫描循环队列 。 扫描过程中不改变,引用位,,
把迂到的第一个 r=0,m=0的页面作为淘汰页面 。
步 2：如果步 1失败,再次从原位置开始,查找
r=0且 m=1的页面,把把迂到的第一个这样的页面作为淘汰页面,而在扫描过程中把指针所扫过的页面的,引用位,r置 0。
步 3：如果步 2失败,指针再次回到了起始位置,
由于此时所有页面的,引用位,r均己为 0,再转向步 1操作,必要时再做步 2操作,这次一定可以挑出一个可淘汰的页面 。
其主要优点是没有被修改过的页面会被优先选出来,淘汰这种页面时不必写回磁盘,从而节省时间,但查找一个淘汰页面可能会经过多轮扫描,算法的实现开销较大 。
Unix SVR4的双指针 clock算法。
其实现思想如下,主存中每个合法的页面 (指不锁住,可淘汰的页面 )都有,引用位,相连 ;当一个页面被替换进主存时,”引用位,置 0; 当一个页面被引用时,”引用位,置 1;系统设置了两个时钟指针，称前指针和后指针,每隔固定时间间隔,两个指针都扫描一遍 ;第一遍,前向指针依次扫过合法页面并把,引用位,置 0;再延迟一定时间之后,后指针依次扫描合法页面,若该页面的,引用位,为 1,表明期间页面被引用过,则跳过该页面,
继续扫描,若该页面的,引用位,为 0,表明期间页面未被引用过,那么,此页面可被淘汰。
6）最不常用页面替换算法（ LFU：
Least Erequently used）
如果对应每一页设置一个计数器,每当访问一页时,就使它对应的计数器加１ 。 过一定时间 t后,将所有计数器全部清０ 。
当发生缺页中断时,可选择计数值最小的对应页面淘汰,显然它是在最近一段时间里最不常用的页面 。 这种算法实现不难,
但代价太高而且选择多大的 t最适宜也是个难题 。
一个例子，分别用 Opt,FIFI、
LRU和 Clock替换算法来计算缺页中断次数和被淘汰的页面，
并对他们的性能作简单的比较。
假设采用固定分配策略，进程分得三个页框,它在执行中按下列次序引用 5个独立的页面,2
3 2 1 5 2 4 5 3 2 5 2。
用上述四种算法计算的结构曲线假设分配给进程的页框数是固定的,运行的 FORTRAN程序共有 0.25× 106次页面引用,页面大小为 256个字 。 在这个实验中,分配给进程的页框数分别为 6,8,10、
12和 14。 当分配给进程的页框数比较少时,四种算法的差距明显,且 FIFO所产生的缺页中断基本上是 Opt的 2倍,Clock
则比较接近于 LRU。
0
5
10
15
20
25
35
40
30
0 66 86 10 12 14
FIFO
CLOCK
LRU
OPT
分配的页数每千次访问的缺页中断数
4.5.2.5页式虚拟存储系统的几个设计问题
1） 页面大小
.从页表大小考虑
.从主存利用率考虑
.从读写一个页面所需的时间考虑最佳页面尺寸假定 S表示用户作业程序的平均长度,P表示以字为单位的页面长度,且有 S>>P。 则每个作业的也表长度为 S/P（ 为简单起见,假定每个页表项占用一个字 ） 。 在作业的最后一页,假定耗费主存 P/2字 。 若定义
f = (浪费的存储字 /作业所需总存储量 )
来表示一个作业耗损主存量的比率,则对一个作业而言,有：
浪费的存储字 = 页表使用的主存空间 + 内部碎片 = S/P + P/2
f = (S/P + P/2) / S = 1/P + P/2S
对于确定的 S,可视 f是页面尺寸 P的函数 。 于是可以求使 f最小的 P值 。 方法是先对 P求一阶导数
f’(P) = df /dP = -1/P2 + 1/2S
令 df /dP = 0,求得 P0 = 开根号 (2S)
再对 P求二阶导数
f,(P) = d2f /dP2 = 2/P3
将 P0 = 开根号 (2S)代入,得到
f”(P0) = 2/(开根号 (2S))3 > 0
这表明函数 f(P)在 P0处取得极小值 。 也就是说,当选取
P0 = 开根号 (2S)时,存储耗损比率 f0 = (开根号 (2/S)
为最小 。 这是称 P0为最佳页面尺寸 。
反之,对于给定的页面尺寸,也可以使用同样的方法求得一个最佳的作业长度 S0。 下表给出了各种页面尺寸 P0 (2的幂次 )时对应的 f0和 S0值 。
著名操作系统选择的页面尺寸,
Atlas为 512字 (每字 48位 )、
IBM370系列机为 2048或 4096字节,
VAX为 512字节,
IBM as/400为 512字节,
Intel 486和 Motorola 68040(Macintosh)
为 4096字节 。
2）工作集模型
P.J.Denning认为,应该将处理机调度和主存管理结合起来进行考虑,并在 1968年提出了工作集模型 。
工作集指在某一段时间内作业运行所要访问的那些页面的集合。
工作集的演变过程如果在一段时间内,作业占用的主存块数目小于工作集时,运行过程中就会不断出现缺页中断,从而导致系统的抖动 。 所以为了保证作业的有效运行,在相应时间段内就应该根据工作集的大小分配给它主存块,以保证工作集中所需要的页面能够进入主存 。
推而广之,为了避免系统发生抖动,就应该限制系统内的作业数,使它们的工作集总尺寸不超过主存块总数 。
24
15
18
23
24
17
18
24
18
17
17
15
24
17
24
18
24
1524
1815
2318
2423
1724
1817
2418
1824
1718
17
1517
2415
1724
2417
1824
24
1524
1815 24
2318 15
2423 18
1724 23
1817 24
*
*
*
*
1517 18
2415 17
*
*
1824 17
24
1524
1815 24
2318 15 24
*
1724 23 18
*
*
*
*
*
1517 18 24
*
*
*
*
24
1524
1815 24
2318 15 24
*
1724 23 18 15
*
*
*
*
*
*
*
*
*
*
52 3 4
窗口大小页面访问序列用 W(t,△ )表示从时刻 t-△ 到时刻 t之间所访问的不同页面的集合,t是进程实际耗用的时间,可以通过执行的指令周期来计算 ; △ 是时间窗口尺寸,通过窗口来观察进程的行为 。 W(t,△ )就是作业在时刻 t的工作集,
表示在最近 △ 个实际时间单位内进程所引用过的页面的集合 ;
∣ W(t,△ )∣ 表示工作集中的页面数目,称工作集尺寸 。
如果系统能随 ∣ W(t,△ )∣ 的大小来分配主存块的话,
就既能有效的利用主存,又可以使缺页中断尽量少地发生,或者说程序要有效运行,其工作集必须在主存中 。
考察二元函数 W的两个变量,首先 W是 t的函数，即随时间不同,工作集也不同。
其一是不同时间的工作集所包含的页面数可能不同 (工作集尺寸不同 );
其二是不同时间的工作集所包含的页面可能不同 (不同内容的页面 )。其次,W是窗口尺寸△的函数,而且工作集的大小是窗口大小的非递减函数。
正确选择工作集窗口尺寸的大小对系统性能有很大影响如果△过大，甚至把作业地址空间全包括在内，就成了实存管理 ;
如果△过小，则会引起频繁缺页,降低了系统的效率。
通过工作集概念来指导确定常驻集的大小,
① 监视每个进程的工作集 。
② 定期地从一个进程常驻集中删去那些不在工作集中的页 。
③ 仅当一个进程的工作集在主存即常驻集包含了它的工作集时,进程才能执行 。
页面故障率是分配的页框数的函数页面故障率（ Page Fault Frequency）
包括 LRU在内的一大类页面替换算法的故障率随着分配的页框数的增加而减少,如图 4-28所示 。 虚线
A对应的是一个过高的故障率,发生故障的进程将被分配更多的页框以减少故障率；虚线 B对应的是一个过低的故障率,可以得出结论分配给这个进程的内存太多了,可以收回一些页框 。
PFF试图把页面故障率保持在一个可接受的范围内 。
如果发现内存中进程太多以至于不可能使所有进程的故障率都低于 A,那么就必须从内存中移去某些进程,把他们的页框分给余下的进程或放进一个空闲页框池中供后面发生页面故障时使用 。 从内存中移去一个进程的决定实际上是一种负载控制,它表明即使在分页系统中交换仍然是需要的,不同的只是现在交换是为了降低潜在的对内存的需求,而不是为了立刻使用收回的内存页框 。
3）页面交换区替换算法常常要挑选一个页面淘汰出主存,但是这个被淘汰出去的页面可能很快又要使用,被重新装入主存 。 因而,
操作系统必须把被淘汰的页面内容保存在磁盘上,例如 Unix使用交换区临时保存页面,系统初始化时,保留一定盘空间作交换区,不能被文件系统使用 。
4) 写时复制写时复制 (copy-on-write)是存储管理用来节省物理内存 (页框 )的一种页面级优化技术,已被 unix和 Windows等许多操作系统所采用,它能减少主存页面内容的复制操作,减少相同内容页面在主存的副本数目 。
当两个进程 (如父子进程 )共享一个页面时,并不是立即为每个进程各建一个页面副本,而是把该页面定义为只读方式,让诸进程共享 。 当其中某个进程要修改页面内容执行写操作时,
会产生一个,写时复制,中断,操作系统处理这个中断信号,为该进程分配一个空闲页框,
复制页面的一个副本,且修改相应的页表项,
当进程重新执行写页面操作时指令被顺利执行,图 5-28 是写时复制的示意 。 可见操作系统采用写时复制技术后,就可以延迟到修改时才对共享页面做出副本,从而,节省了大量页面复制操作和副本占用空间 。
页面3
页面1
页面2
页面3
页面1
页面2
页面2
副本原始数据原始数据原始数据原始数据原始数据原始数据原始数据修改数据原始数据原始数据原始数据原始数据进程地址空间 进程地址空间物理地址空间图 4-29写时复制前 (上图 ),写时复制后 (下图 )
进程地址空间物理地址空间进程地址空间
页面替换就是用来确定应该淘汰哪页的算法,也称淘汰算法 。
选用了一个不适合的算法,就会出现这样的现象：刚被淘汰的页面又立即要用,因而又要把它调入,而调入不久再被淘汰,淘汰不久再被调入 。 如此反复,使得整个系统的页面调度非常频繁以至于大部时间都化在来回调度页面上 。 这种现象叫做,抖动,(Thrashing)，
又称,颠簸,,一个好的调度算法应减少和避免抖动现象 。
替换策略要处理的是,
当把一个新的页面调入主存时,选择己在主存的哪个页面作替换。由于下列因素,使得替换策略变得比较困难,
① 分给每个活跃进程多少页框?
② 页面替换时,仅限于缺页中断进程还是包括主存中所有页面?
③ 在被考虑的压面集合中,选出哪个页面进行替换?
一个理论算法假定作业 p共计 n页,而系统分配给它的主存块只有 m块 （ m,n均为正整数,且１ ≤m≤n）,即最多主存中只能容纳该作业的 m页 。 如果作业
p在运行中成功的访问次数为 s（ 即所访问的页在主存中 ）,不成功的访问次数为 F（ 即缺页中断次数 ）,则总的访问次数Ａ为：
A = S + F
又定义：
f = F / A
则称 f为缺页中断率 。 影响缺页中断率 f的因素有：
l主存页框数 。 作业分得的主存块数多,则缺页中断率就低,反之,缺页中断率就高 。
l页面大小 。 如果划分的页面大,则缺页中断率就低,否则缺页中断率就高 。
l页面替换算法 。
l程序特性 。 程序编制的方法不同,对缺页中断的次数有很大影响,程序的局部性要好 。
一个程序要将 128× 128的数组置初值,0”。
现假定分给这个程序的主存块数只有一块,页面的尺寸为每页 128个字,数组中的元素每一行存放在一页中,开始时第一页在主存 。 若程序如下编制：
Var A,array[1..128] of array [1..128] of integer;
for j,= 1 to 128
do for i,= 1 to 128
do A[i][j]:=0
则每执行一次Ａ [i][j],＝０就要产生一次缺页中断,于是总共要产生 （ 128× 128－ 1） 次缺页中断 。 如果重新编制这个程序如下：
Var A,array[1..128] of array[1..128] of integer;
for j,= 1 to128
do for i,= 1 to 128
do A[i][j],= 0
那么,总共只产生 （ 128－ 1） 次缺页中断 。
理论算法 (最佳算法 )
当要调入一页而必须淘汰一个旧页时,所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页 。 这样的调度算法使缺页中断率为最低 。 然而这样的算法是无法实现的因为在程序运行中无法对以后要使用的页面作出精确的断言 。 不过,这个理论上的算法可以用来作为衡量各种具体算法的标准 。 这个算法是由
Belady提出来的,所以叫做 Belady算法,又叫做最佳算法 （ Optimal） 。
1）随机页面替换算法要淘汰的页面是由一个随机数产生程序所产生的随机数来确定,选择一个不常使用的页面会使系统性能较好,但这种调度算法做不到这一点,虽很简单但效率却低,
一般不采用 。
2)先进先出页面替换算法 （ FIFO)
先进先出调度算法是一种低开销的页面替换算法，基于程序总是按线性顺序来访问物理空间这一假设。
这种算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。
实现技术一种实现方法是系统中设置一张具有 m个元素的页号表,它是由Ｍ个数：
P[0],P[1],…,P[m-1]
所组成的一个数组,其中每个 P[i] (i =0,1,… m-1)
存储一个在主存中的页面的页号 。 假设用指针 k
指示当前调入新页时应淘汰的那一页在页号表中的位置,则淘汰的页号应是 P[k]。 每当调入一个新页后,执行
P[k],= 新页的页号 ;
k,= （ k+1） mod m;
另一个简单的实现算法引入指针链成队列,只要把进入主存的页面按时间的先后次序链接,新进入的页面从队尾入队,淘汰总是从队列头进行 。
3）最近最少用页面替换算法（ LRU,least
Recently used）
该算法淘汰的页面是在最近一段时间里较久未被访问的那一页 。 它是根据程序执行时所具有的局部性来考虑的,即那些刚被使用过的页面,
可能马上还要被使用,而那些在较长时间里未被使用的页面,一般说可能不会马上使用到 。
维护一个特殊的队列该队列中存放当前在主存中的页号,每当访问一页时就调整一次,使队列尾总指向最近访问的页,队列头就是最近最少用的页 。 显然,发生缺页中断时总淘汰队列头所指示的页；而执行一次页面访问后,需要从队列中把该页调整到队列尾 。
例：给某作业分配了三块主存，该作业依次访问的页号为,4,3,0,4,1,1,2,3,2。于是当访问这些页时，页面淘汰序列的变化情况如下：
4 4
3 4 3
0 4 3 0
4 3 0 4
1 0 4 1 3
1 0 4 1
2 4 1 2 0
3 1 2 3 4
2 1 3 2
LRU算法实现第一种模拟方法可以通过设置标志位来实现。
给每一页设置一个引用标志位 R，每次访问某一页时，由硬件将该页的标志 R置 1，
隔一定的时间 t将所有页的标志 R均清 0。
在发生缺页中断时，从标志位 R为 0的那些页中挑选一页淘汰。在挑选到要淘汰的页后，也将所有页的标志 R清 0。
第二种模拟方法是为每个页设置一个多位寄存器 r
当页面被访问时,对应的寄存器的最左边位置 1；每隔时间 t,将 r寄存器右移一位；在发生缺页中断时,找最小数值的 r寄存器对应的页面淘汰 。
例如,r寄存器共有四位，页面 P0、
P1,P2在 T1,T2,T3时刻的 r寄存器内容如下：
页面 时刻
T1 T2 T3
P0 1000 0100 1010
P1 1000 1100 0110
P2 0000 1000 0100
4)第二次机会页面替换算法
FIFO算法可能会把经常使用的页面淘汰掉,可以对 FIFO算法进行改进,把 FIFO算法与页表中的,
引用位,结合起来使用,算法可实现如下：
首先检查 FIFO中的队首页面 (这是最早进入主存的页面 ),如果它的,引用位,是 0,那么这个页面既老又没有用,选择该页面淘汰 ; 如果它的,引用位,
是 1,说明虽然它进入主存较早,但最近仍在使用 。
于是把它的,引用位,清成 0,并把这个页面移到队尾,把它看作是一个新调入的页 。 这一算法称为第二次机会 (second chance)算法,其含义是最先进入主存的页面,如果最近还在被使用的话,仍然有机会作为像一个新调入页面一样留在主存中 。
5）时钟页面替换算法 (Clock Policy)
算法的实现要点如下：
l一个页面首次装入主存时,其,引用位,置 0。
l在主存中的任何一个页面被访问时,其,引用位,
置 1。
l淘汰页面时,存储管理从指针当前指向的页面开始扫描循环队列,把所迁到的,引用位,是 1的页面的,引用位,清成 0,并跳过这个页面 ; 把所迁到的,引用位,是 0的页面淘汰掉,指针推进一步 。
扫描循环队列时,如果迁到的所有页面的,引用位,为 1,指针就会绕整个循环队列一圈,把碰到的所有页面的,引用位,清 0;指针停在起始位置,并淘汰掉这一页,然后,指针推进一步 。
时钟页面替换算法的一个例子
Page9
use=1
Page19
Use=1 Page1
Use=0
Page45
Use=1
Page191
Use=1
Page556
Use=0
Page13
Use=0
Page67
Use=1
Page33
Use=1
Page222
Use=0
下一个帧指针
n 0
1
2
3
4
56
7
8
（ a） 一个页替换前的缓冲区状态
Page9
use=1
Page19
Use=1 Page1
Use=0
Page45
Use=0
Page191
Use=1
Page727
Use=1
Page13
Use=0
Page67
Use=1
Page33
Use=1
Page222
Use=0
n 0
1
2
3
4
56
7
8
（ b） 下一页替换后的缓冲区状态
1第 1页框改进时钟页面替换算法如果把页表中的,引用位,和,修改位,
结合起来使用可以,共组合成四种情况：
(1)最近没有被引用,没有被修改 (r=0,m=0)
(2)最近被引用,没有被修改 (r=1,m=0)
(3)最近没有被引用,但被修改 (r=0,m=1)
(4)最近被引用过,也被修改过 (r=1,m=1)
改进的时钟算法可如下执行：
步 1：选择最佳淘汰页面,从指针当前位置开始,
扫描循环队列 。 扫描过程中不改变,引用位,,
把迂到的第一个 r=0,m=0的页面作为淘汰页面 。
步 2：如果步 1失败,再次从原位置开始,查找
r=0且 m=1的页面,把把迂到的第一个这样的页面作为淘汰页面,而在扫描过程中把指针所扫过的页面的,引用位,r置 0。
步 3：如果步 2失败,指针再次回到了起始位置,
由于此时所有页面的,引用位,r均己为 0,再转向步 1操作,必要时再做步 2操作,这次一定可以挑出一个可淘汰的页面 。
其主要优点是没有被修改过的页面会被优先选出来,淘汰这种页面时不必写回磁盘,从而节省时间,但查找一个淘汰页面可能会经过多轮扫描,算法的实现开销较大 。
Unix SVR4的双指针 clock算法。
其实现思想如下,主存中每个合法的页面 (指不锁住,可淘汰的页面 )都有,引用位,相连 ;当一个页面被替换进主存时,”引用位,置 0; 当一个页面被引用时,”引用位,置 1;系统设置了两个时钟指针，称前指针和后指针,每隔固定时间间隔,两个指针都扫描一遍 ;第一遍,前向指针依次扫过合法页面并把,引用位,置 0;再延迟一定时间之后,后指针依次扫描合法页面,若该页面的,引用位,为 1,表明期间页面被引用过,则跳过该页面,
继续扫描,若该页面的,引用位,为 0,表明期间页面未被引用过,那么,此页面可被淘汰。
6）最不常用页面替换算法（ LFU：
Least Erequently used）
如果对应每一页设置一个计数器,每当访问一页时,就使它对应的计数器加１ 。 过一定时间 t后,将所有计数器全部清０ 。
当发生缺页中断时,可选择计数值最小的对应页面淘汰,显然它是在最近一段时间里最不常用的页面 。 这种算法实现不难,
但代价太高而且选择多大的 t最适宜也是个难题 。
一个例子，分别用 Opt,FIFI、
LRU和 Clock替换算法来计算缺页中断次数和被淘汰的页面，
并对他们的性能作简单的比较。
假设采用固定分配策略，进程分得三个页框,它在执行中按下列次序引用 5个独立的页面,2
3 2 1 5 2 4 5 3 2 5 2。
用上述四种算法计算的结构曲线假设分配给进程的页框数是固定的,运行的 FORTRAN程序共有 0.25× 106次页面引用,页面大小为 256个字 。 在这个实验中,分配给进程的页框数分别为 6,8,10、
12和 14。 当分配给进程的页框数比较少时,四种算法的差距明显,且 FIFO所产生的缺页中断基本上是 Opt的 2倍,Clock
则比较接近于 LRU。
0
5
10
15
20
25
35
40
30
0 66 86 10 12 14
FIFO
CLOCK
LRU
OPT
分配的页数每千次访问的缺页中断数
4.5.2.5页式虚拟存储系统的几个设计问题
1） 页面大小
.从页表大小考虑
.从主存利用率考虑
.从读写一个页面所需的时间考虑最佳页面尺寸假定 S表示用户作业程序的平均长度,P表示以字为单位的页面长度,且有 S>>P。 则每个作业的也表长度为 S/P（ 为简单起见,假定每个页表项占用一个字 ） 。 在作业的最后一页,假定耗费主存 P/2字 。 若定义
f = (浪费的存储字 /作业所需总存储量 )
来表示一个作业耗损主存量的比率,则对一个作业而言,有：
浪费的存储字 = 页表使用的主存空间 + 内部碎片 = S/P + P/2
f = (S/P + P/2) / S = 1/P + P/2S
对于确定的 S,可视 f是页面尺寸 P的函数 。 于是可以求使 f最小的 P值 。 方法是先对 P求一阶导数
f’(P) = df /dP = -1/P2 + 1/2S
令 df /dP = 0,求得 P0 = 开根号 (2S)
再对 P求二阶导数
f,(P) = d2f /dP2 = 2/P3
将 P0 = 开根号 (2S)代入,得到
f”(P0) = 2/(开根号 (2S))3 > 0
这表明函数 f(P)在 P0处取得极小值 。 也就是说,当选取
P0 = 开根号 (2S)时,存储耗损比率 f0 = (开根号 (2/S)
为最小 。 这是称 P0为最佳页面尺寸 。
反之,对于给定的页面尺寸,也可以使用同样的方法求得一个最佳的作业长度 S0。 下表给出了各种页面尺寸 P0 (2的幂次 )时对应的 f0和 S0值 。
著名操作系统选择的页面尺寸,
Atlas为 512字 (每字 48位 )、
IBM370系列机为 2048或 4096字节,
VAX为 512字节,
IBM as/400为 512字节,
Intel 486和 Motorola 68040(Macintosh)
为 4096字节 。
2）工作集模型
P.J.Denning认为,应该将处理机调度和主存管理结合起来进行考虑,并在 1968年提出了工作集模型 。
工作集指在某一段时间内作业运行所要访问的那些页面的集合。
工作集的演变过程如果在一段时间内,作业占用的主存块数目小于工作集时,运行过程中就会不断出现缺页中断,从而导致系统的抖动 。 所以为了保证作业的有效运行,在相应时间段内就应该根据工作集的大小分配给它主存块,以保证工作集中所需要的页面能够进入主存 。
推而广之,为了避免系统发生抖动,就应该限制系统内的作业数,使它们的工作集总尺寸不超过主存块总数 。
24
15
18
23
24
17
18
24
18
17
17
15
24
17
24
18
24
1524
1815
2318
2423
1724
1817
2418
1824
1718
17
1517
2415
1724
2417
1824
24
1524
1815 24
2318 15
2423 18
1724 23
1817 24
*
*
*
*
1517 18
2415 17
*
*
1824 17
24
1524
1815 24
2318 15 24
*
1724 23 18
*
*
*
*
*
1517 18 24
*
*
*
*
24
1524
1815 24
2318 15 24
*
1724 23 18 15
*
*
*
*
*
*
*
*
*
*
52 3 4
窗口大小页面访问序列用 W(t,△ )表示从时刻 t-△ 到时刻 t之间所访问的不同页面的集合,t是进程实际耗用的时间,可以通过执行的指令周期来计算 ; △ 是时间窗口尺寸,通过窗口来观察进程的行为 。 W(t,△ )就是作业在时刻 t的工作集,
表示在最近 △ 个实际时间单位内进程所引用过的页面的集合 ;
∣ W(t,△ )∣ 表示工作集中的页面数目,称工作集尺寸 。
如果系统能随 ∣ W(t,△ )∣ 的大小来分配主存块的话,
就既能有效的利用主存,又可以使缺页中断尽量少地发生,或者说程序要有效运行,其工作集必须在主存中 。
考察二元函数 W的两个变量,首先 W是 t的函数，即随时间不同,工作集也不同。
其一是不同时间的工作集所包含的页面数可能不同 (工作集尺寸不同 );
其二是不同时间的工作集所包含的页面可能不同 (不同内容的页面 )。其次,W是窗口尺寸△的函数,而且工作集的大小是窗口大小的非递减函数。
正确选择工作集窗口尺寸的大小对系统性能有很大影响如果△过大，甚至把作业地址空间全包括在内，就成了实存管理 ;
如果△过小，则会引起频繁缺页,降低了系统的效率。
通过工作集概念来指导确定常驻集的大小,
① 监视每个进程的工作集 。
② 定期地从一个进程常驻集中删去那些不在工作集中的页 。
③ 仅当一个进程的工作集在主存即常驻集包含了它的工作集时,进程才能执行 。
页面故障率是分配的页框数的函数页面故障率（ Page Fault Frequency）
包括 LRU在内的一大类页面替换算法的故障率随着分配的页框数的增加而减少,如图 4-28所示 。 虚线
A对应的是一个过高的故障率,发生故障的进程将被分配更多的页框以减少故障率；虚线 B对应的是一个过低的故障率,可以得出结论分配给这个进程的内存太多了,可以收回一些页框 。
PFF试图把页面故障率保持在一个可接受的范围内 。
如果发现内存中进程太多以至于不可能使所有进程的故障率都低于 A,那么就必须从内存中移去某些进程,把他们的页框分给余下的进程或放进一个空闲页框池中供后面发生页面故障时使用 。 从内存中移去一个进程的决定实际上是一种负载控制,它表明即使在分页系统中交换仍然是需要的,不同的只是现在交换是为了降低潜在的对内存的需求,而不是为了立刻使用收回的内存页框 。
3）页面交换区替换算法常常要挑选一个页面淘汰出主存,但是这个被淘汰出去的页面可能很快又要使用,被重新装入主存 。 因而,
操作系统必须把被淘汰的页面内容保存在磁盘上,例如 Unix使用交换区临时保存页面,系统初始化时,保留一定盘空间作交换区,不能被文件系统使用 。
4) 写时复制写时复制 (copy-on-write)是存储管理用来节省物理内存 (页框 )的一种页面级优化技术,已被 unix和 Windows等许多操作系统所采用,它能减少主存页面内容的复制操作,减少相同内容页面在主存的副本数目 。
当两个进程 (如父子进程 )共享一个页面时,并不是立即为每个进程各建一个页面副本,而是把该页面定义为只读方式,让诸进程共享 。 当其中某个进程要修改页面内容执行写操作时,
会产生一个,写时复制,中断,操作系统处理这个中断信号,为该进程分配一个空闲页框,
复制页面的一个副本,且修改相应的页表项,
当进程重新执行写页面操作时指令被顺利执行,图 5-28 是写时复制的示意 。 可见操作系统采用写时复制技术后,就可以延迟到修改时才对共享页面做出副本,从而,节省了大量页面复制操作和副本占用空间 。
页面3
页面1
页面2
页面3
页面1
页面2
页面2
副本原始数据原始数据原始数据原始数据原始数据原始数据原始数据修改数据原始数据原始数据原始数据原始数据进程地址空间 进程地址空间物理地址空间图 4-29写时复制前 (上图 ),写时复制后 (下图 )
进程地址空间物理地址空间进程地址空间
