计算机系统结构 （第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)，则这类算法称为堆栈型替 换算法