
计算机系统结构 (第12讲) 主讲人:郑纬民教授 清华大学计算机系
计算机系统结构 (第12讲) 主讲人: 郑纬民 教授 清华大学计算机系

3.2.4页面替换算法及其实现方法 页面替换发生时间: 当发生页面失效时,要从磁盘中调入 一页到主存。如果主存所有页面都已 经被占用,必须从主存储器中淘汰掉 一个不常使用的页面,以便腾出主存 空间来存放新调入的页面。 评价页面替换算法好坏的标准: 一是命中率要高 二是算法要容易实现
3.2.4 页面替换算法及其实现方法 页面替换发生时间: 当发生页面失效时,要从磁盘中调入 一页到主存。如果主存所有页面都已 经被占用,必须从主存储器中淘汰掉 一个不常使用的页面,以便腾出主存 空间来存放新调入的页面。 评价页面替换算法好坏的标准: 一是命中率要高 二是算法要容易实现

页面替换算法的使用场合: (1)虚拟存储器中,主存页面的替换 一般用软件实现 (2)Cache块替换一般用硬件实现 (3)虚拟存储器的快慢表中,快表存储 字的替换,用硬件实现 (4)虚拟存储器中,用户基地址寄存器 的替换,用硬件实现 (⑤)在有些虚拟存储器中目录表的替换 1、页面替换算法 (1)随机算法(RAND Random algorithm):
页面替换算法的使用场合: (1) 虚拟存储器中,主存页面的替换, 一般用软件实现 (2) Cache块替换一般用硬件实现 (3) 虚拟存储器的快慢表中,快表存储 字的替换,用硬件实现 (4) 虚拟存储器中,用户基地址寄存器 的替换,用硬件实现 (5) 在有些虚拟存储器中目录表的替换 1、页面替换算法 (1) 随机算法(RAND Random algorithm):

算法简单,容易实现: 没有利用历史信息,没有反映程序的 局部性,命中率低。 (2)先进先出算法FIFO First--In First-Out algorithm): 比较容易实现,利用了历史信息,没 有反映程序的局部性。 最先调入主存的页面,很可能也是经 常要使用的页面。 (3)近期最少使用算法LFU Least Frequently Used algorithm):
算法简单,容易实现; 没有利用历史信息,没有反映程序的 局部性,命中率低。 (2) 先进先出算法 (FIFO First-In First-Out algorithm): 比较容易实现,利用了历史信息,没 有反映程序的局部性。 最先调入主存的页面,很可能也是经 常要使用的页面。 (3) 近期最少使用算法 (LFU Least Frequently Used algorithm):

既充分利用了历史信息,又反映了程 序的局部性,实现起来非常困难。 (4)最久没有使用算法(LRU Least Recently Used algorithm): 把LRU算法中的“多”与“少”简化 成“有”与“无”,实现起来比较容 (5)最优替换算法(OPT OPTimal replacemant algorithm): 是一种理想化的算法。用来作为评价 其它页面替换算法好坏的标准。 在虚拟存储器中,实际上有可能采用 只有FIFO和LRU两种算法
既充分利用了历史信息,又反映了程 序的局部性,实现起来非常困难。 (4) 最久没有使用算法 (LRU Least Recently Used algorithm): 把LRU算法中的“多”与“少”简化 成“有”与“无”,实现起来比较容 易。 (5) 最优替换算法 (OPT OPTimal replacemant algorithm): 是一种理想化的算法。用来作为评价 其它页面替换算法好坏的标准。 在虚拟存储器中,实际上有可能采用 只有FIFO和LRU两种算法

例3.8: 个程序共有5个页面组成,程序执行过 程中的页地址流如下: P1,P2,P1,P5,P5,P1,P3,P4,P3,P4 假设分配给这个程序的主存储器共有3个 页面。给出FIFO、LRU、OPT三种页面 替换算法对这3页主存的使用情况,包括 调入、替换和命中等
例3.8: 一个程序共有5个页面组成,程序执行过 程中的页地址流如下: P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 假设分配给这个程序的主存储器共有3个 页面。给出FIFO、LRU、OPT 三种页面 替换算法对这3页主存的使用情况,包括 调入、替换和命中等

时间t 10 实际 页地址流 命中次数 米 4* 4* 先进先出算法 2* 1* (FIFO算法) 5 5* 3* 调 命中 周入 替换替换替换命中替换替换 2次 1* 2 2 最久没有使用算法 2* 4米 4 4 (LRU算法) 5 5* 5* 3 3 3*3* 调入调入命中调入替换命中替换命中替换命中 4次 1*3*3* 3 最优替换算法 2* 22 (OPT算法) 5* 4 44 调入调入命中调入替换命中替换命中命中命中5次 三种页面替换算法对同一个页地址流的调度过程
时间 t 1 2 3 4 5 6 7 8 9 10 实际 页地址流 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4 命中次数 1 1 1 1* 4 4 4* 4* 2 2 先进先出算法 2 2 2 2* 1 1 1 1* 4 (FIFO 算法) 5 5 5* 3 3 3 3* 调入 调入 命中 调入 替换 替换 替换 命中 替换 替换 2 次 1 1 1 1 1 1 1 1* 2 2 最久没有使用算法 2 2 2* 4 4 4* 4 4 4 (LRU 算法) 5 5* 5* 3 3 3* 3* 调入 调入 命中 调入 替换 命中 替换 命中 替换 命中 4 次 1 1 1 1 1 1* 3* 3* 3 3 最优替换算法 2 2 2 2* 2 2 2 2 2 (OPT 算法) 5* 4 4 4 4 4 4 调入 调入 命中 调入 替换 命中 替换 命中 命中 命中 5 次 三种页面替换算法对同一个页地址流的调度过程

例3.9: 个循环程序,依次使用P1,P2,P3, P4四个页面,分配给这个程序的主存页 面数为3个。FIFO、LRU和OPT三种页面 替换算法对主存页面的调度情况如下图 所示。在IFO和LRU算法中,总是发生 下次就要使用的页面本次被替换出去的 情况,这就是“颠簸”现象
例3.9: 一个循环程序,依次使用P1,P2,P3, P4四个页面,分配给这个程序的主存页 面数为3个。FIFO、LRU和OPT三种页面 替换算法对主存页面的调度情况如下图 所示。在FIFO和LRU算法中,总是发生 下次就要使用的页面本次被替换出去的 情况,这就是“颠簸”现象

时间t 1 2 3 45 6 7 8 实际 页地址流 P1 P2 P3 P4 P1 P2 P3P4 命中次数 1 1*44 4* 3 先进先出算法 2 2 2*1 1 1* 4 (FIFO算法) 3 33* 2 22* 调入调入调入替换替换替换替换替换 0次 1 1* 4 4 4米 3 最久没有使用算法物 2 22* 1 1* 4 (LRU算法) 3 33米 222* 调入调入调入替换替换替换替换替换 0次 1 1 11米 1 11 最优替换算法 2 2 22 2*3*3 (0PT算法) 3* 4*4 444* 调入调入调入替换命中命中替换命中 3次
时 间 t 1 2 3 4 5 6 7 8 实 际 页地址流 P 1 P 2 P 3 P 4 P 1 P 2 P 3 P 4 命中次数 1 1 1 * 4 4 4 * 3 3 先进先出算法 2 2 2 * 1 1 1 * 4 (FIFO 算法) 3 3 3 * 2 2 2 * 调 入 调 入 调 入 替 换 替 换 替 换 替 换 替 换 0 次 1 1 1 * 4 4 4 * 3 3 最久没有使用算法 2 2 2 * 1 1 1 * 4 (LRU 算法) 3 3 3 * 2 2 2 * 调 入 调 入 调 入 替 换 替 换 替 换 替 换 替 换 0 次 1 1 1 1 1 * 1 1 1 最优替换算法 2 2 2 2 2 * 3 * 3 (OPT 算法) 3 * 4 * 4 4 4 4 * 调 入 调 入 调 入 替 换 命 中 命 中 替 换 命 中 3 次

2、堆栈型替换算法 定义: 对任意一个程序的页地址流作两次主存 页面数分配,分别分配m个主存页面和n 个主存页面,并且有m≤n。如果在任何 时刻t,主存页面数集合Bt都满足关系: Btm)sBtn),则这类算法称为堆栈型替 换算法
2、堆栈型替换算法 定义: 对任意一个程序的页地址流作两次主存 页面数分配,分别分配m个主存页面和n 个主存页面,并且有m≤n。如果在任何 时刻t,主存页面数集合Bt都满足关系: Bt(m) Bt(n),则这类算法称为堆栈型替 换算法