2、堆栈型替换算法 堆栈型替换算法的定义: 对任意一个程序的页地址流作两次主存页面数分配,分别分配m个主存页面 和n个主存页面,并且有m≤n。如果在任何时刻t,主存页面数集合Bt都满足 关系 Bt(m)c Bt (n) 则这类算法称为堆栈型替换算法。 堆栈型算法的基本特点是:随着分配给程序的主存页面数增加,主存的命中 率也提高,至少不下降。 时间t 23456789101112|实际 页地址流P1P2P3PP1P2P5P1P2P3P4P5命中次数 4*55555*5* 主存页面数222* N=3菱333* 2222 入调入调入替换替换替换替换命中命中替换替换命中3次 1*1*55 5*4 主存页面数2 22*2*1 1|1* N=4多接33333 2222* 调入调入调入调入命中命中替换替換换替换替换替换替换2次 FIFO算法在主存页面数增加时命中率反而下降 LFU算法、LRU算法和PT算法都是堆栈型算法。 FIFO算法不是堆栈型算法 3.2.5提高主存命中率的方法 影响主存命中率的主要因素: (1)程序在执行过程中的页地址流分布情况。 (2)所采用的页面替换算法 (3)页面大小。 (4)主存储器的容量 (5)所采用的页面调度方法。 以下,对后三个因素进行分析 1、页面大小与命中率的关系 页面大小为某个值时,命中率达到最大。 解释:假设A1和A是相邻两次访问主存储器的逻辑地址,d=|At-A+1|。 如果d<Sp,随着Sp的增大,At和A+在同一页面的可能性增加,即 H随着Sp的增大而提高。 如果d>Sp,At和A+1一定不在同一个页面内。随着Sp的增大,主存 的页面数减少,页面的替换将更加频繁。H随着Sp的增大而降低。3—3 2、堆栈型替换算法 堆栈型替换算法的定义： 对任意一个程序的页地址流作两次主存页面数分配，分别分配 m 个主存页面 和 n 个主存页面，并且有 m≤n。如果在任何时刻 t，主存页面数集合 Bt 都满足 关系： Bt（m） Bt（n） 则这类算法称为堆栈型替换算法。 堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中 率也提高，至少不下降。 时间 t 1 2 3 4 5 6 7 8 9 10 11 12 实际 页地址流 P1 P2 P3 P4 P1 P2 P5 P1 P2 P3 P4 P5 命中次数 1 1 1* 4 4 4* 5 5 5 5 5* 5* 主存页面数 2 2 2* 1 1 1* 1* 1* 3 3 3 N＝3 3 3 3* 2 2 2 2 2* 4 4 调入 调入 调入 替换 替换 替换 替换 命中 命中 替换 替换 命中 3 次 1 1 1 1 1* 1* 5 5 5 5* 4 4 主存页面数 2 2 2 2 2* 2* 1 1 1 1* 5 N＝4 3 3 3 3 3 3* 2 2 2 2* 4 4 4 4 4 4* 3 3 3 调入 调入 调入 调入 命中 命中 替换 替换 替换 替换 替换 替换 2 次 FIFO 算法在主存页面数增加时命中率反而下降 LFU 算法、LRU 算法和 OPT 算法都是堆栈型算法。 FIFO 算法不是堆栈型算法 3.2.5 提高主存命中率的方法 影响主存命中率的主要因素： (1) 程序在执行过程中的页地址流分布情况。 (2) 所采用的页面替换算法。 (3) 页面大小。 (4) 主存储器的容量 (5) 所采用的页面调度方法。 以下，对后三个因素进行分析。 1、页面大小与命中率的关系 页面大小为某个值时，命中率达到最大。 解释：假设 At 和 At+1 是相邻两次访问主存储器的逻辑地址，d＝｜At－At+1｜。 如果ｄ＜Sp，随着 Sp 的增大，At 和 At+1 在同一页面的可能性增加，即 Ｈ随着 Sp 的增大而提高。 如果ｄ＞Sp，At 和 At+1 一定不在同一个页面内。随着 Sp 的增大，主存 的页面数减少，页面的替换将更加频繁。Ｈ随着 Sp 的增大而降低