计算机系统结构第3章资料.ppt

3.2.3 页面替换算法及其实现方法 当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都被占用，须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。 评价页面替换算法好坏的标准：一是命中率要高，二是算法要容易实现。 1、页面替换算法 常用的页面替换算法： (1) 随机算法（RAND Random algorithm）： 算法简单，容易实现。 没有利用历史信息，没有反映程序的局部性，命中率低。 (2) 先进先出算法（FIFO First-In First-Out algorithm）； 比较容易实现，利用了历史信息，没有反映程序的局部性。 最先调入主存的页面，很可能也是经常要使用的页面。 (3) 近期最少使用算法（LRU Least Recently Used algorithm）： 既充分利用了历史信息，又反映了程序的局部性，实现起来非常困难。 (4) 最久没有使用算法（LFU Least Frequently Used algorithm）： 它把LRU算法中的“多”与“少”简化成“有”与“无”， 实现起来比较容易。 (5) 最优替换算法（OPT OPTimal replacemant algorithm）： 是理想化算法。用来作为评价其它页面替换算法好坏的标准。 在虚拟存储器中，实际有可能采用的只有FIFO和LFU两种算法。 例：一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）如下： P1，P2，P1，P5，P4，P1，P3，P4，P2，P4 假设分配给这个程序的主存储器共有3个页面。给出FIFO、LFU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。 例：一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LFU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LFU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。 2、堆栈型替换算法 堆栈型替换算法的定义： 对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt（m）? Bt（n） 则这类算法称为堆栈型替换算法。 堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不会下降。 LFU、LRU和OPT算法都是堆栈型算法。 FIFO算法不是堆栈型算法 FIFO算法在主存页面数增加时命中率反而下降 3.2.4 提高主存命中率的方法 影响主存命中率的主要因素： (1) 程序在执行过程中的页地址流分布情况。 (2) 所采用的页面替换算法。 (3) 页面大小。 (4) 主存储器的容量 (5) 所采用的页面调度方法。 1、页面大小与命中率的关系 页面大小为某个值时，命中率达到最大。 假设At和At+1是相邻两次访问主存储器的逻辑地址，d＝｜At－At+1｜。 如果ｄ＜Sp，随着Sp的增大，Ｈ提高。 如果ｄ＞Sp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。Ｈ随着Sp的增大而降低。 P170 ：图3.36 页面大小与主存命中率的关系 2、主存容量与命中率的关系 H随着分配给该程序的主存容量S的增加而单调上升。 在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。 P171：图3.37 主存命中H率与主存容量S的关系 3、页面调度方式与命中率的关系 分页式 请求页式 预取式 3.4 三级存储系统 在大部分计算机系统中，既有虚拟存储器，也有Cache存储系统。 存储系统可以有多种构成方法。 不同的构成只是实现技术不同。 1、两个存储系统的组织方式： 目前的大部分处理机均采用这种两级存储系统。 2、一个存储系统组织方式： 虚拟地址Cache存储系统 如Intel公司的i860等处理机采用这种组织方式。 3、全Cache系统。 没有主存储器，“Cache—磁盘”存储系统。 本章重点： 1、存储系统的定义及主要性能。 2、并行存储器的工作原理。 3、虚拟存储系统的工作原理。 4、虚拟存储系统的页面替换算法。 5、Cache存储系统的地址映象及变换方法。 6、Cache存储系统的块替换算法。 7、Cache存储系统的一致性问题。 题1 Cache存储系统中，Cache的访问周期为10ns，主存储器的访问周期为60ns,每个数据在Cache中平均重复使用4次。当块的大小为1个字时，存储系统的访问效率只有0.5