体系结构课件chapter42章节.pptVIP

每次只有2nv行载入 因为省略了虚页号字段，所以表宽为nv+1 因为很多行没用，所以进行改进，见下页的相联目录表法 4步检查对应主存地址的载入位是否为1 * 要想把该道程序的虚页调入主存，必须给出该页在辅存中的实际地址。为了提高调页效率，辅存一般是按信息块编址的，而且让块的大小通常等于页面的大小。以磁盘为例，辅存实(块)地址Nvd的格式为 磁盘机号 柱面号 磁头号 块号 Nvd 主存页面失效，辅存调页 * 图 4.19 虚地址到辅存实地址的变换 ① ② ③ * 替换算法 页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。 替换算法的确定 主存的命中率 是否便于实现，软、硬件成本 * 页面替换算法的使用场合 虚拟存储器中，主存页面的替换，一般用软件实现 Cache块替换一般用硬件实现 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现 虚拟存储器中，用户基地址寄存器的替换，用硬件实现 * 替换算法（续） 随机算法（Random，RAND）：用软的或硬的随机数产生器来形成主存重要被替换页的页号。 简单，易于实现 没有利用历史信息 命中率低，很少使用 先进先出算法（First-In First-Out，FIFO）：选择最早装入主存的页作为被替换的页。 配置计数器字段 虽然利用历史信息，但不一定反映出程序的局部性 * 替换算法（续） 近期最少使用算法（Least Recently Used，LRU）：选择近期最少访问的页作为被替换的页。 配有计数器字段。 比较正确反映程序的局部性。 优化替换算法（Optimal Replacement Algorithm， OPT）:是在时刻t找出主存中每个页将要用到时刻ti，然后选择其中ti-t最大的那一页作为替换页。 理想化算法 * 举例1 设有一道程序，有1至5共5页，执行时的地址流为： 2，3，2，1，5，2，4，5，3，2，5，2 分别采用FIFO、LRU、OPT算法。 * * 说明 命中率与地址流有关 例如：一个循环程序，FIFO、LRU的命中率明显低于OPT。（下一张） 颠簸现象：连续不断出现页面失效。 命中率与分配给程序的主存页数有关。 主存页数增加，LRU命中率提高，至少不会下降，而FIFO不一定。 * 图 4.17 FIFO法的实页数增加， 命中率反而有可能下降 * 举例 一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。 * * 举例2 一个程序共有5个页面组成，程序执行过程中的页地址流如下： P1, P2, P1, P5, P5, P1, P3, P4, P3, P4假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU、OPT 三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。 * * 堆栈型替换算法的定义 设A是长度为L的任意一个页面地址流，t为已处理过t-1个页面的时间点，n为分配给该地址流的主存页面数，Bt(n)表示在t时间点、在n页的主存中的页面集合，Lt表示到t时间点已遇到过的地址流中相异页的页数。如果替换算法具有下列包含性质： 则此替换算法属堆栈型的替换算法。 * 堆栈型替换算法的定义(2) 对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt(m)í Bt(n)，则这类算法称为堆栈型替换算法。 * 堆栈型算法的基本特点 随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。 LRU、OPT都是堆栈型算法 FIFO是非堆栈型算法 提出使系统性能可以更优的动态算法。 由操作系统来动态调节分配给每道程序的实页数。 * 虚拟存储器工作的全过程 * 页式虚拟存储器实现中的问题 页面失效的处理 页面失效会在一条指令的分析或执行过程中发出。 页面失效是一种故障，不是一般的中断； 注意保护现场,采用后援寄存器技术、预判技术； 选择合适的替换算法； * 页式虚拟存储器实现中的问题 提高虚拟存储器等效访问速度的措施 要求：提高命中率，加快访存时间； 命中率受很多因素影响，如：地址流、页面调度策略、替换算法、页面大小、主存容量等。 访存时间，解决Ns?np的转换。 快表：相联目录表，慢表：页表 快表-慢表存储层次的替换算法一般采用LRU法。