第三章-2存储器的层次结构.ppt

2003.3.1 计算机系统结构 3.1.2 存储器的层次结构 Data location Data identifacation Data replacement Data Write policy 地址映象与变换(P174) 存储层次的管理方式(P147) 相联目录表技术 4种常见的地址映象方式 全相联的地址映象方式与地址变换原理示意图(c) 3.3.2 直接相联(P176) 直接相联的地址映象方式与地址变换原理 3.3.3 组相联(P178) 组相联的地址变换 3.3.4 段相联(P184) ? 段相联方式的主要优点： 段表比较简单，实现成本低。 例如：容量为256KB Cache，分8段，每段2048块，每块16B。 在段表存储器中只需要存储8个主存地址的段号S。 ? 段相联方式的主要缺点： 当发生段失效时，要把本段内已经建立的映象关系全部撤消。 段相联映象方式的虚实段内页号对应关系是固定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以虚段号比实段号位数多，也就意味着“多→少”的映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。 多用户虚地址格式 3.4 替换算法(P164) 3.4.1 几种常用的替换算法(P164) 从LFU到LRU的近似 算法模拟：实存状况图（P166图3.32） 3.4.2 堆栈型替换算法(P166) 实例：堆栈模拟图 3.6 虚拟存储器与Cache的特点(P146，P172) 工作流程 Cache的写操作 1. 全写法，亦称写直达法(WT法——Write through)： 在对Cache进行写操作的同时，也对主存该内容进行写。 Cache的实用举例 1. Cache的分体 本章小结 第三章补充练习 这是对某些替换算法的统称。如果某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集（当容量超过虚页总数时，保留页面集合相同），则小容量下的命中点到大容量情况下仍然是命中点，并且随着容量加大，还可能会有新的命中点产生。具有这一特性的一类替换算法中成为“堆栈型算法”。 例如：P166图3.32中，对LRU算法，如果实页数增加到4，则t=5时为了调入虚页4就不必替换掉虚页2，而是将虚页1、2、4、5都留在实存，这时大容量分区情况下的保留页面集合S2 = {1，2，4，5}，同一时刻的小容量分区情况下的保留页面集合S1 = {1，4，5}。显然有S1 S2。 P167第4～8行是堆栈型算法的数学定义。 堆栈型替换算法的主要性质就是命中率H随着实页分区容量n的上升而单调上升（不减性）。 可以证明，LFU、LRU、OPT等算法都是堆栈型算法，而RAND和FIFO算法不是堆栈型算法。P168的图3.34是一个实例，当实页数从3增加到4时，FIFO的命中率反倒从3降到2。具体观察，比如t = 7时，S1 = {1，2，5}，S2 = {2，3，4，5}，不满足子集关系。所以FIFO不能保证当实页数增加时，原来的命中点不丢。 研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如P167倒数第3行的PFF法），另一方面也可推导出一些分析工具，例如“堆栈模拟法”。 堆栈模拟图可以通过一次作图，描述同一地址流在各种实存分区容量下的命中情况。 例3.4 3.5 提高命中率的方法 影响命中率的主要因素： (1) 程序在执行过程中的页地址流分布情况。 (2) 所采用的页面替换算法。 (3) 页面大小。 (4) 存储器的容量 (5) 所采用的页面调度方法。 以下，对后三个因素进行分析。 1. 页面大小与命中率的关系 页面大小为某个值时，命中率达到最大。 解释：假设At和At+1是相邻两次访问主存储器的逻辑地址，d=|At - At+1|。 如果dSp，随着Sp的增大，At和At+1在同一页面的可能性增加，即Ｈ随着Sp的增大而提高。 如果dSp，At和At+1一定不在同一个页面内。随着Sp的增大，主存的页面数减少，页面的替换将更加频繁。Ｈ随着Sp的增大而降低。 1 命 2S 中 率 S H 页面大小SP