第6章 层次结构存储系统 存储器概述 主存与CPU的连接及其读写操作 磁盘存储器 高速缓冲存储器(cache) 虚拟存储器 IA-32/Linux中的地址转换

层次结构存储系统 主要教学目标 理解CPU执行指令过程中为何要访存 理解访存操作的大致过程及涉及到的部件 了解层次化存储器系统的由来及构成 掌握Cache机制并理解其对程序性能的影响 理解程序局部性的重要性并能开发局部性好的程序 了解虚拟存储管理的基本概念和实现原理 理解访存操作完整过程以及所涉及到的部件之间的关联 地址转换（查TLB、查页表）、访问Cache、访问主存、读写磁盘 理解访存过程中硬件和操作系统之间的协调关系

层次结构存储系统 分以下六个部分介绍 第一讲：存储器概述 第二讲：主存与CPU的连接及其读写操作 主存模块的连接和读写操作 “装入”指令和“存储”指令操作过程 第三讲：磁盘存储器 第四讲：高速缓冲存储器(cache) 程序访问的局部性、cache的基本工作原理 cache行和主存块之间的映射方式 cache和程序性能 第五讲：虚拟存储器 虚拟地址空间、虚拟存储器的实现 第六讲：IA-32/Linux中的地址转换 逻辑地址到线性地址的转换 线性地址到物理地址的转换

替换算法-先进先出（FIFO） 1 2 3 4 1 2 5 1 2 3 4 5 1* 1* 1* 4 4 4* 5 5 5 5 5* 5* 总是把最先从图书馆搬来的书还回去！ 总是把最先进入的那一块淘汰掉。 例：假定主存中的5块{1,2,3,4,5}同时映射到Cache同一组中，对于同一地址流，考察3行/组、 4行/组的情况。 注：通常一组中含有2k行，这里3行/组主要为了简化问题而假设 1 2 3 4 1 2 5 1 2 3 4 5 1* 1* 1* 4 4 4* 5 5 5 5 5* 5* 3行/组 2 2 2* 1 1 1* 1* 1* 3 3 3 3 3 3* 2 2 2 2 2* 4 4 √ √ √ 1* 1* 1* 1* 5* 4 4 1* 1* 5 5 5 2 2 2 2 2 2* 1 1 1 1* 5 4行/组 3 3 3* 3 3 3* 2 2 2 2* 4 4 4 4 4 4* 3 3 3 √ √ 由此可见，FIFO不是一种堆栈算法，即命中率并不随组的增大而提高。

替换算法-最近最少用(LRU) 总是把最长时间不看的书还回去！ 总是把最近最少用的那一块淘汰掉。 例：假定主存中的5块{1,2,3,4,5}同时映射到Cache同一组中，对于同一地址流，考察3行/组、 4行/组、 5行/组的情况。 1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 1 2 5 1 2 3 4 5 1 2 3 4 1 2 1 5 2 3 4 1 2 3 4 1 2 5 1 2 3 1 2 3 4 4 4 5 1 2 3 3 3 4 5 1 3行/组 4行/组 5行/组 √ √ √ √ √ √ √ √ √ √ √ √ √

替换算法-最近最少用 LRU是一种堆栈算法，它的命中率随组的增大而提高。 当分块局部化范围(即：某段时间集中访问的存储区)超过了Cache存储容量时，命中率变得很低。极端情况下，假设地址流是1,2,3,4,1 2,3,4,1,……，而Cache每组只有3行，那么，不管是FIFO，还是LRU算法，其命中率都为0。这种现象称为颠簸(Thrashing / PingPong)。 LRU具体实现时，并不是通过移动块来实现的，而是通过给每个cache行设定一个计数器，根据计数值来记录这些主存块的使用情况。这个计数值称为LRU位。 具体实现

替换算法-最近最少用 即：计数值为0的行中的主存块最常被访问，计数值为3的行中的主存块最不经常被访问，先被淘汰！ 通过计数值来确定cache行中主存块的使用情况 计数器变化规则： 每组4行时，计数器有2位。计数值越小则说明越被常用。 命中时，被访问行的计数器置0，比其低的计数器加1，其余不变。 未命中且该组未满时，新行计数器置为0，其余全加1。 未命中且该组已满时，计数值为3的那一行中的主存块被淘汰，新行计数器置为0，其余加1。 1 2 3 4 1 2 5 1 2 3 4 5 1 1 1 2 1 3 1 1 1 1 2 1 1 1 1 2 1 3 1 5 2 1 2 2 2 3 2 2 1 2 2 2 2 1 2 2 2 3 4 3 1 3 2 3 3 3 5 1 5 2 5 3 5 4 2 3 4 1 4 2 4 3 4 3 4 3 4 3 1 3 1 2

举例 6 4 5 4352/64=68，所以访问过程实际上是对前68块连续访问10次。 假定计算机系统主存空间大小为32Kx16位，且有一个4K字的4路组相联Cache，主存和Cache之间的数据交换块的大小为64字。假定Cache开始为空，处理器顺序地从存储单元0、1、…、4351中取数，一共重复10次。设Cache比主存快10倍。采用LRU算法。试分析Cache的结构和主存地址的划分。说明采用Cache后速度提高了多少？采用MRU算法后呢？ 答：假定主存按字编址。每字16位。 主存：32K字=512块 x 64字 / 块 Cache：4K字=16组 x 4行 / 组 x 64 字 / 行 主存地址划分为： 字号 标志位 组号 6 4 5 4352/64=68，所以访问过程实际上是对前68块连续访问10次。

举例 第0 行 第1 行 第2 行 第3 行 第0组 第1组 第2组 第3组 第4组 …… 第15组 0/64/48 1/65/49 2/66/50 3/67/51 4 …… 15 16/0/64 17/1/65 18/2/66 19/3/67 20 …… 31 32/16 33/17 34/18 35/19 36 …… 47 48/32 49/33 50/34 51/35 52 …… 63 LRU算法：第一次循环,每一块只有第一字未命中,其余都命中; 以后9次循环,有20块的第一字未命中,其余都命中. 所以,命中率p为 (43520-68-9x20)/43520=99.43% 速度提高：tm/ta=tm/(tc+(1-p)tm)=10/(1+10x(1-p))=9.5倍

举例 第0 行 第1 行 第2 行 第3 行 第0组 第1组 第2组 第3组 第4组 …… 第15组 0/16/32/48 1/17/33/49 2/18/34/50 3/19/35/52 4 … 15组 16/32/48/64 17/33/49/65 18/34/50/66 19/35/51/67 20 … 31 32/48/64/0 33/49/65/1 34/50/66/2 35/51/67/3 36 … 47 48/64/0/16 49/65/1/17 50/66/2/18 51/67/3/19 52 … 63 MRU算法：第一次68字未命中；第2,3,4,6,7,8,10次各有4字未命中；第5,9次各有8字未命中；其余都命中. 所以,命中率p为 (43520-68-7x4-2 x8)/43520=99.74% 速度提高：tm/ta=tm/(tc+(1-p)tm)=10/(1+10x(1-p))=9.77倍

写策略（Cache一致性问题） 为何要保持在Cache和主存中数据的一致？ 因为Cache中的内容是主存块副本，当对Cache中的内容进行更新时，就存在Cache和主存如何保持一致的问题。 以下情况也会出现“Cache一致性问题” 当多个设备都允许访问主存时 例如：I/O设备可直接读写内存时，如果Cache中的内容被修改，则I/O设备读出的对应主存单元的内容无效；若I/O设备修改了主存单元的内容，则Cache中对应的内容无效。 当多个CPU都带有各自的Cache而共享主存时 某个CPU修改了自身Cache中的内容，则对应的主存单元和其他CPU中对应的内容都变为无效。 写操作有两种情况 写命中（Write Hit）：要写的单元已经在Cache中 写不命中（Write Miss）：要写的单元不在Cache中

写策略（Cache一致性问题） 处理Cache读比Cache写更容易，故指令Cache比数据Cache容易设计 对于写命中，有两种处理方式 Write Through (通过式写、写直达、直写) 同时写Cache和主存单元 What!!! How can this be? Memory is too slow(>100Cycles)? 10%的存储指令使CPI增加到：1.0+100x10%=11 使用写缓冲（Write Buffer） Write Back (一次性写、写回、回写) 只写cache不写主存，缺失时一次写回，每行有个修改位（“dirty bit-脏位”），大大降低主存带宽需求，控制可能很复杂 对于写不命中，有两种处理方式 Write Allocate (写分配) 将主存块装入Cache，然后更新相应单元 试图利用空间局部性，但每次都要从主存读一个块 Not Write Allocate (非写分配) 直接写主存单元，不把主存块装入到Cache 直写Cache可用非写分配或写分配 回写Cache通常用写分配 为什么？ SKIP

Write Through中的Write Buffer Cache CPU Memory Controller DRAM Write Buffer 在 Cache 和 Memory之间加一个Write Buffer CPU同时写数据到Cache和Write Buffer Memory controller（存控）将缓冲内容写主存 Write buffer (写缓冲) 是一个FIFO队列 一般有4项 在存数频率不 高时效果好 最棘手的问题 当频繁写时，易使写缓存饱和，发生阻塞 如何解决写缓冲饱和？ 加一个二级Cache 使用Write Back方式的Cache BACK

写策略（Cache一致性问题） 问题1：以下描述的是哪种写策略？ Write Through 、Write Allocate！ 问题2：如果用非写分配， 则如何修改算法？ BACK

写策略2：Write Back算法 问题：以下算法描述的是哪种写策略？ Write Back 、Write Allocate！

写策略2：Write Back中的修改（“脏”）位

Cache大小、Block大小和缺失率的关系 而缺失率与Cache大小、Block大小、Cache级数等有关 Cache大小：Cache越大，Miss率越低，但成本越高！ Block大小：Block大小与Cache大小有关，且不能太大，也不能太小！

Block Size Tradeoff (块大小的选择) 块大能很好利用 spatial locality， BUT: 块大，则需花更多时间读块，缺失损失变大 块大，则Cache行数变少，缺失率上升 Average Access Time: = Hit Time x (1 - Miss Rate) + Miss Penalty x Miss Rate Average Access Time Increased Miss Penalty & Miss Rate Block Size Miss Penalty Block Size Miss Rate Exploits Spatial Locality Fewer blocks: compromises temporal locality Block Size 所以，块大小必须适中！

系统中的Cache数目 刚引入Cache时只有一个Cache。近年来多Cache系统成为主流 多Cache系统中，需考虑两个方面： [1] 单级/多级？ 片内(On-chip)Cache: 将Cache和CPU作在一个芯片上 外部(Off-chip)Cache:不做在CPU内而是独立设置一个Cache 单级Cache：只用一个片内Cache 多级Cache：同时使用L1 Cache和L2 Cache，有些高端系统甚至有L3 Cache，L1 Cache更靠近CPU，其速度比L2快，其容量比L2大 [2] 联合/分立？ 分立：指数据和指令分开存放在各自的数据和指令Cache中 一般L1 Cache都是分立Cache，为什么？ L1 Cache的命中时间比命中率更重要！为什么？ 联合：指数据和指令都放在一个Cache中 一般L2 Cache都是联合Cache，为什么？ L2 Cache的命中率比命中时间更重要！为什么？ 因为缺失时需从主存取数，并要送L1和L2cache，损失大！

多核处理器中的多级Cache

设计支持Cache的存储器系统 指令执行若发生Cache缺失，必须到DRAM中取数据或指令 在DRAM和Cache之间传输的单位是Block 假定存储器访问过程： CPU发送地址到内存：1个总线时钟 访问内存的初始化时间：10个总线时钟 从总线上传送一个字：1个总线时钟 CPU MM 可以有三种不同的组织形式！ 假定一个Block有4个字，则缺失损失各为多少时钟？

设计支持Cache的存储器系统 4x(1+10+1)=48 假定存储器访问过程： CPU发送地址到内存：1个总线时钟 内存访问时间：10个总线时钟 从总线上传送一个字：1个总线时钟 4x(1+10+1)=48 缺失损失为48个时钟周期 代价小，但速度慢！

设计支持Cache的存储器系统 Two-word: 2x(1+10+1)=24 Four-word: 1+10+1=12 假定存储器访问过程： CPU发送地址到内存：1个总线时钟 内存访问时间：10个总线时钟 从总线上传送一个字：1个总线时钟 Two-word: 2x(1+10+1)=24 Four-word: 1+10+1=12 缺失损失各为24或12个时钟周期 速度快，但代价大！

设计支持Cache的存储器系统 假定存储器访问过程： CPU发送地址到内存：1个总线时钟 内存访问时间：10个总线时钟 从总线上传送一个字：1个总线时钟 Interleaved four banks one-word: 1+1x10+4x1=15 第1个字 10 1 第2个字 10 1 第3个字 10 1 第4个字 10 1 缺失损失为15个时钟周期 代价小，而且速度快！

实例：奔腾机的Cache组织 主存：4GB=220x 27块x 25B/块 Cache：8KB=128组x2行/组 替换算法： LRU，每组一位LRU位 0：下次淘汰第0路 1：下次淘汰第1路 写策略： 默认为Write Back，可动态设置为Write Through。 Cache一致性： 支持MESI协议

实例：Pentium 4的cache存储器 指令cache及指令预取部件 有3个cache，分成两级： L1cache 64位,时钟频率 前端总线 指令cache及指令预取部件 有3个cache，分成两级： L1cache 数据缓存（L1数据cache），8KB 指令缓存， 8KB L2 cache，容量为256 KB～2MB 总线 接口部件 预取 控制逻辑 L2 cache (48GB/s) 256位，时钟频率 L1数据cache(8KB)

实例：Intel Core i7处理器的cache结构 i-cache和d-cache都是32KB、8路、4个时钟周期；L2 cache：256KB、8路、11个时钟周期。所有核共享的L3 cache：8MB、16路、30~40个时钟周期。Core i7中所有cache的块大小都是64B

缓存在现代计算机中无处不在

Cache和程序性能 程序的性能指执行程序所用的时间 考虑程序的访问局部性通常在数据的访问局部性上下工夫 数据的访问局部性主要是指数组、结构等类型数据访问时的局部性，这些数据结构的数据元素访问通常是通过循环语句进行的，所以，如何合理地处理循环对于数据访问局部性来说是非常重要的。

Cache和程序性能举例 （1）不考虑用于一致性和替换的控制位，数据cache的总容量为多少？ 举例：某32位机器主存地址空间大小为256 MB，按字节编址。指令cache和数据cache均有8行，主存块为64B，数据cache采用直接映射。假定编译时i, j, sum均分配在寄存器中，数组a按行优先方式存放，其首址为320。 （1）不考虑用于一致性和替换的控制位，数据cache的总容量为多少？ （2）a[0][31]和a[1][1]各自所在主存块对应的cache行号分别是多少？ （3）程序A和B的数据访问命中率各是多少？哪个程序的执行时间更短？

Cache和程序性能举例 举例：某32位机器主存地址空间大小为256 MB，按字节编址。指令cache和数据cache均有8行，主存块为64B，数据cache采用直接映射。假定编译时i, j, sum均分配在寄存器中，数组a按行优先方式存放，其首址为320。 （1）主存地址空间大小为256MB，因而主存地址为28位，其中6位为块内地址，3位为cache行号（行索引），标志信息有28-6-3=19位。在不考虑用于cache一致性维护和替换算法的控制位的情况下，数据cache的总容量为： 8×(19+1+64×8)=4256位=532字节 。 （2）a[0][31]的地址为320+4×31=444，[444/64]=6（取整），因此a[0][31]对应的主存块号为6。6 mod 8=6，对应cache行号为6。 或: 444=0000 0000 0000 0000 000 110 111100B，中间3位110为行号（行索引），因此，对应的cache行号为6。 a[1][1]对应的cache行号为： [(320+4×(1×256+1))/64] mod 8=5。 （3）A中数组访问顺序与存放顺序相同，共访问64K次，占4K个主存块；首地址位于一个主存块开始，故每个主存块总是第一个元素缺失，其他都命中，共缺失4K次，命中率为1-4K/64K=93.75%。 方法二：每个主存块的命中情况一样。对于一个主存块，包含16个元素，需访存16次，其中第一次不命中，因而命中率为15/16=93.75%。 B中访问顺序与存放顺序不同，依次访问的元素分布在相隔256×4=1024的单元处，它们都不在同一个主存块中,cache共8行，一次内循环访问16块，故再次访问同一块时，已被调出cache，因而每次都缺失，命中率为0。