4、虚拟存储器举例 例3.7:IMB3η0/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地 址长36位,页面大小为4KB,每个用户最多占用4K个页面,最多允许16G个用 户,但同时上机的用户数一般不超过6个 (书上第62页)图3.30IBM370/168计算机的虚拟存储器快表结构 采用了两项新的措施: 一是采用两个相等比较器。 二是用相联寄存器组把24位用户号U压缩成3位 3.2.4页面替换算法及其实现方法 页面替换发生时间:当发生页面失效时,要从磁盘中调入一页到主存。如果 主存所有页面都已经被占用,必须从主存储器中淘汰掉一个不常使用的页面, 以便腾出主存空间来存放新调入的页面。 评价页面替换算法好坏的标准:一是命中率要高,二是算法要容易实现。 页面替换算法的使用场合: (1)虚拟存储器中,主存页面的替换,一般用软件实现。 (2) Cache中的块替换,一般用硬件实现 (3)虚拟存储器的快慢表中,快表存储字的替换,用硬件实现 (4)虚拟存储器中,用户基地址寄存器的替换,用硬件实现。 (5)在有些虚拟存储器中,目录表的替换。 1、页面替换算法 常用的页面替换算法: (1)随机算法( RAND Random 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两种算法 例3.8:一个程序共有5个页面组成,分别为P1~P5。程序执行过程中的页 地址流(即程序执行中依次用到的页面)如下: P1,P2,P1,P5,P5,P1,P3,P4,P3,P43—1 4、虚拟存储器举例 例 3.7：IMB370/168 计算机的虚拟存储器快表结构及地址变换过程。虚拟地 址长 36 位，页面大小为 4KB，每个用户最多占用 4K 个页面，最多允许 16G 个用 户，但同时上机的用户数一般不超过 6 个。 （书上第 62 页） 图 3.30 IBM370/168 计算机的虚拟存储器快表结构 采用了两项新的措施： 一是采用两个相等比较器。 二是用相联寄存器组把 24 位用户号 U 压缩成 3 位 3.2.4 页面替换算法及其实现方法 页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果 主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面， 以便腾出主存空间来存放新调入的页面。 评价页面替换算法好坏的标准：一是命中率要高，二是算法要容易实现。 页面替换算法的使用场合： (1) 虚拟存储器中，主存页面的替换，一般用软件实现。 (2) Cache 中的块替换，一般用硬件实现。 (3) 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。 (4) 虚拟存储器中，用户基地址寄存器的替换，用硬件实现。 (5) 在有些虚拟存储器中，目录表的替换。 1、页面替换算法 常用的页面替换算法： (1) 随机算法（RAND Random 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 两种算法。 例 3.8：一个程序共有 5 个页面组成，分别为 P1～P5。程序执行过程中的页 地址流（即程序执行中依次用到的页面）如下： P1，P2，P1，P5，P5，P1，P3，P4，P3，P4