南京大学：《操作系统》课程教学资源（PPT课件）第四章（4.4）页面replace

4.52.4页面替换策略 ●页面替换 当主存空间已装满而又要装入新页时,必须按一定的 算法把已在主存的一些页调出去,这个工作称页面替 换 页面替换就是用来确定应该淘汰哪页的算法,也称淘汰 算法 选用了一个不适合的算法,就会出现这样的现象:刚被 淘汰的页面又立即要用,因而又要把它调入,而调入 不久再被淘汰,淘汰不久再被调入。如此反复,使得 整个系统的页面调度非常频繁以至于大部时间都化在 来回调度页面上。这种现象叫做“抖动”( Thrashing) 又称“颠簸”,一个好的调度算法应减少和避免抖动 现象

4.5.2.4 页面替换策略 页面替换 当主存空间已装满而又要装入新页时，必须按一定的 算法把已在主存的一些页调出去，这个工作称页面替 换。 页面替换就是用来确定应该淘汰哪页的算法,也称淘汰 算法。 选用了一个不适合的算法，就会出现这样的现象：刚被 淘汰的页面又立即要用，因而又要把它调入，而调入 不久再被淘汰，淘汰不久再被调入。如此反复，使得 整个系统的页面调度非常频繁以至于大部时间都化在 来回调度页面上。这种现象叫做“抖动”(Thrashing)， 又称“颠簸” ，一个好的调度算法应减少和避免抖动 现象

替换策略要处理的是 ◆当把一个新的页面调入主存时,选择己在主存 的哪个页面作替换。由于下列因素,使得替换 策略变得比较困难 ①分给每个活跃进程多少页框? ②页面替换时,仅限于缺页中断进程还是包括 主存中所有页面? ③在被考虑的压面集合中,选出哪个页面进行 替换?

替换策略要处理的是: 当把一个新的页面调入主存时,选择己在主存 的哪个页面作替换。由于下列因素,使得替换 策略变得比较困难: ①分给每个活跃进程多少页框? ②页面替换时,仅限于缺页中断进程还是包括 主存中所有页面? ③在被考虑的压面集合中,选出哪个页面进行 替换?

个理论算法 假定作业p共计n页,而系统分配给它的主存块 只有m块(m,n均为正整数,且1≤m≤n),即 最多主存中只能容纳该作业的m页。如果作业 p在运行中成功的访问次数为s(即所访间的页 在主存中),不成功的访问次数为F(即缺页 中断次数),则总的访问次数A为: CA=S+F 又定义: Cf=F/A

一个理论算法 假定作业p共计n页，而系统分配给它的主存块 只有m块（m,n均为正整数，且１≤m≤n），即 最多主存中只能容纳该作业的m页。如果作业 p在运行中成功的访问次数为s（即所访问的页 在主存中）， 不成功的访问次数为F（即缺页 中断次数），则总的访问次数Ａ为： A = S + F 又定义： f = F / A

●则称f为缺页中断率。影响缺页中断率f的因 素有: ●●主存页框数。作业分得的主存块数多,则 缺页中断率就低,反之,缺页中断率就高 ●●页面大小。如果划分的页面大,则缺页中 断率就低,否则缺页中断率就高 ●●页面替换算法。 ●●程序特性。程序编制的方法不同,对缺页 中断的次数有很大影响,程序的局部性要好

则称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[0:=0 则每执行一次A[]:=0就要产生一次缺页中断,于是总 共要产生(128×128-1)次缺页中断。如果重新编制这个 程序如下 Var A: arrayl1. 128] of array[. 128] of integer; forj: =1 to128 do for i=1 to 128 doA[而:=0 ●那么,总共只产生(128-1)次缺页中断

一个程序要将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)

理论算法(最佳算法) 当要调入一页而必须淘汰一个旧页时，所淘汰 的页应该是以后不再访问的页或距现在最长时 间后再访问的页。这样的调度算法使缺页中断 率为最低。然而这样的算法是无法实现的因为 在程序运行中无法对以后要使用的页面作出精 确的断言。不过，这个理论上的算法可以用来 作为衡量各种具体算法的标准。这个算法是由 Belady提出来的，所以叫做Belady算法，又 叫做最佳算法（Optimal）

1)随机页面替换算法 ●要淘汰的页面是由一个随机数产生程序 所产生的随机数来确定,选择一个不常使 用的页面会使系统性能较好,但这种调度 算法做不到这一点,虽很简单但效率却低, 般不采用

1）随机页面替换算法 要淘汰的页面是由一个随机数产生程序 所产生的随机数来确定,选择一个不常使 用的页面会使系统性能较好,但这种调度 算法做不到这一点,虽很简单但效率却低， 一般不采用

2)先进先出页面替换算法(FIFO ●先进先出调度算法是一种低开销的页面 替换算法,基于程序总是按线性顺序来 访问物理空间这一假设 ●这种算法总是淘汰最先调入主存的那 页,或者说在主存中驻留时间最长的那 页(常驻的除外)

2)先进先出页面替换算法（FIFO) 先进先出调度算法是一种低开销的页面 替换算法，基于程序总是按线性顺序来 访问物理空间这一假设。 这种算法总是淘汰最先调入主存的那一 页，或者说在主存中驻留时间最长的那 一页（常驻的除外）

实现技术 种实现方法是系统中设置一张具有m个元素的 页号表,它是由M个数: P[O],P[1 P[m-1] 所组成的一个数组,其中每个P(=0,1,m-1) 存储一个在主存中的页面的页号。假设用指针k 指示当前调入新页时应淘汰的那一页在页号表中 的位置,则淘汰的页号应是PKk]。每当调入一个 新页后,执行 P[k]:=新页的页号 k+1) mod m

实现技术 一种实现方法是系统中设置一张具有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;

另一个简单的实现算法 ●引入指针链成队列,只要 把进入主存的页面按时间 的先后次序链接,新进入的 页面从队尾入队,淘汰总是 从队列头进行

另一个简单的实现算法 引入指针链成队列，只要 把进入主存的页面按时间 的先后次序链接,新进入的 页面从队尾入队,淘汰总是 从队列头进行