第三章存储系统ppt课件.ppt

《第三章存储系统ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.2.4页面替换算法及其实现方法页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。评价页面替换算法好坏的标准：一是命中率要高，二是算法要容易实现。页面替换算法的使用场合：(1)虚拟存储器中，主存页面的替换，一般用软件实现。(2)Cache中的块替换，一般用硬件实现。(3)虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。(4)虚拟存储器中，用户基地址寄存器的替换，用硬件实现。(5)在有些虚拟存储器中，目录表

2、的替换。1、页面替换算法常用的页面替换算法：(1)随机算法（RANDRandomalgorithm）：算法简单，容易实现。没有利用历史信息，没有反映程序的局部性，命中率低。(2)先进先出算法（FIFOFirst-InFirst-Outalgorithm）：比较容易实现，利用了历史信息，没有反映程序的局部性。最先调入主存的页面，很可能也是经常要使用的页面。(3)近期最少使用算法（LFULeastFrequentlyUsedalgorithm）：既充分利用了历史信息，又反映了程序的局部性实现起来非常困难。(4)最久没有使用算法（LR

3、ULeastRecentlyUsedalgorithm）：它把LFU算法中的“多”与“少”简化成“有”与“无”，实现起来比较容易。(5)最优替换算法（OPTOPTimalreplacemantalgorithm）：是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。在虚拟存储器中，实际上有可能采用只有FIFO和LRU两种算法。例3.8：一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）如下：P1，P2，P1，P5，P4，P1，P3，P4，P2，P4假设分配给这个程序的主存储

4、器共有3个页面。给出FIFO、LRU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。R*例3.9：一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。R2、堆栈型替换算法堆栈型替换算法的定义：对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主

5、存页面数集合Bt都满足关系：Bt（m）Bt（n）则这类算法称为堆栈型替换算法。堆栈型算法的基本特点是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。LFU算法、LRU算法和OPT算法都是堆栈型算法。FIFO算法不是堆栈型算法堆栈模拟图：t123456789101112命中次数pp2p3P2P1P5P2P4P5P3P2P5P2主存页面2321524532522321524532532152453333112444331111N=10N=2**2N=3*****5N=4******6N=5*******73.2.

6、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的增大，主存的页面数减少，页

7、面的替换将更加频繁。Ｈ随着Sp的增大而降低。当Sp比较小的时候，前一种情况是主要的，Ｈ随着Sp的增大而提高。当Sp达到某一个最大值之后，后一种情况成为主要的，Ｈ随着Sp的增大而降低。当页面大小增大时，造成的浪费也要增加。当页面大小减小时，页表和页面表在主存储器中所占的比例将增加。（书上第170页）图3.36页面大小与主存命中率的关系2、主存容量与命中率的关系主存命中率H随着分配给该程序的主存容量S的增加而单调上升。在S比较小的时候，H提高得非常快。随着S的逐渐增加，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。p

8、1713、页面调度方式与命中率的关系请求式：当使用到的时候，再调入主存预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。可以避免在程序开始运行时，频繁发生页面失效的情况。如果调入的页面用不上，浪费了调入的时