前言下面是《深入理解计算机系统》第六章节的一段话对系统的研究中我们依赖于一个简单的计算机系统模型 CPU 执行指令而存储器系统为 CPU 存放指令和数据 。 在简单模型中存储器系统是一个线性 的字节数组而 CPU 能够在一个常数时间内访问每个存储器位置。虽然迄今为止这都是一个有效的模型但是它没有反映现代系统实际工作的方式 。存储器系统(memory system)是一个具有不同容量、成本和访问时间的存储设备的层次结构。 CPU 寄存器保存着最常用的数据。靠近 CPU 的小的、快速的高速缓存存储器 (cache memory)作为一部分存储在相对慢速的主存储器(main memory) 中数据和指令的缓冲区域。 主存缓存存储在容量较大的、慢速磁盘上的数据而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域 。存储器层次结构是可行的这是因为与下一个更低层次的存储设备相比来说一个编写良好的程序倾向于更频繁地访问某一个层次上的存储设备。所以下一层的存储设备可以更慢速一点也因此可以更大每个比特位更便宜。整体效果是一个大的存储器池其成本与层次结构底层最便宜的存储设备相当但是却以接近于层次结构顶部存储设备的高速率向程序提供数据。作为一个程序员你需要理解存储器层次结构因为它对应用程序的性能有着巨大的影响 。 如果你的程序需要的数据是存储在 CPU 寄存器中的那么在指令的执行期间在 0 个周期内就能访问到它们。如果存储在高速缓存中需要 4~7 5 个周期 。 如果存储在主存中需要上百个周期。而如果存储在磁盘上需要大约几千万个周期存储技术随机访问存储器随机访问存储器 (Random-Acces s Memory, RAM)分为两类静态的和动态的。静态 RAM(SRAM) 比动态 RAM(DRAM) 更快但也贵得多。 SRAM 用来作为高速缓存存储器既可以在 CPU 芯片上也可以在片下 。 DRAM 用来作为主存以及图形系统的帧缓冲区。典型地一个桌面系统的 SRAM 不会超过几兆字节但是 DRAM 却有几百或几千兆字节 。SRAM将每个位存储在一个双稳态的 (bistable) 存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性它可以无限期地保持在两个不同的电压配置 (configuration)或状态 (state) 之一。其他任何状态都是不稳定的从不稳定状态开始电路会迅速地转移到两个稳定状态中的一个。由千 SRAM 存储器单元的双稳态特性只要有电它就会永远地保持它的值。即使有干扰例如电子噪音来扰乱电压当干扰消除时电路就会恢复到稳定值。DRAM每个位用一个电容 一个晶体管存储。电容有电荷表示 1无电荷表示 0电容很小容易漏电一般 10100 毫秒内就可能丢失电荷所以必须周期性地 读出再写回也就是刷新对光、电噪声比较敏感优点是结构简单、密度高、成本低适合做主存。有些系统还会给 DRAM 加 纠错码 ECC比如 64 位数据用 72 位存储这样可以发现并纠正单比特错误。传统的DRAMDRAM 芯片中的位被组织成超单元 supercell。每个超单元包含 w 位共有 d 个超单元所以总容量是 d×w 位。这些超单元排成 r 行 c 列的二维阵列满足 rc d。访问时采用行列复用内存控制器先发送 行地址 i称为 RASDRAM 把第 i 行复制到内部 行缓冲区再发送 列地址 j称为 CAS从行缓冲区中取出第 j 个超单元的数据返回。内存模块DIMM多个 DRAM 芯片会封装成 内存模块插到主板上。常见的是 DIMM一次以 64 位为单位与内存控制器交换数据。例如一个模块用 8 个 8M×8 的 DRAM 芯片每个芯片提供 8 位合起来就是 64 位。访问某个主存地址时内存控制器把地址转换成行列地址广播给所有芯片每个芯片返回自己的 8 位最后拼成一个 64 位字。增强的DRAM为了弥补传统 DRAM 速度慢的问题出现了多种改进FPM DRAM同一行连续访问时行缓冲区可以复用后续访问只需 CAS不用每次都发 RASEDO DRAM在 FPM 基础上进一步缩短 CAS 之间的间隔SDRAM和系统时钟同步比异步 DRAM 更快DDR SDRAM在时钟上升沿和下降沿都传输数据使有效带宽翻倍DDR、DDR2、DDR3 等通过增大预取缓冲区继续提升带宽VRAM用于图形帧缓冲区支持并行读写适合一边刷新屏幕一边写入新像素。非易失性存储器SRAM 和 DRAM 都是 易失性存储器断电后数据会丢失。非易失性存储器即使断电也能保存数据。常见类型PROM只能编程一次EPROM可用紫外线擦除再重新编程EEPROM可用电信号擦除和编程能在电路板上直接改写Flash基于 EEPROM 发展而来广泛用于 U 盘、SSD、手机存储等存储在 ROM 中的程序常称为 固件 firmware比如 PC 的 BIOS。访问主存数据流通过称为总线 (bus) 的共享电子电路在处理器和 DRAM 主存之间来来回回 。 每次 CPU 和主存之间的数据传送都是通过一系列步骤来完成的这些步骤称为总线事务 (bus transaction) 。读事务(read transaction)从主存传送数据到 CPU。写事务(write trans-action)从 CPU 传送数据到主存 。总线是一组并行的导线能携带地址、 数据和控制信号 。 取决于总线的设计数据和地址信号可以共享同一组导线也可以使用不同的。同时两个以上的设备也能共享同一总线 。 控制线携带的信号会同步事务 并标识出 当前正在被执行的事务的类型。现在有一个命令movq A,%rax地址A的内容被加载到寄存器%rax中。CPU芯片上称为总线接口的电路在总线上发起读事务。读事务是由三个步骤组成的。首先 CPU 将地址 A 放到系统总线上。 I/0 桥将信号传递到内存总线。 接下来主存感觉到内存总线上的地址信号从内存总线读地址从 DRAM 取出数据字并将数据写到内存总线 。 I/0 桥将内存总线信号翻译成系统总线信号然后沿着系统总线传递。最后 CPU 感觉到系统总线上的数据从总线上读数据并将数据复制到寄存器 %rax。反过来CPU执行这样一个存储操作movq %rax A这里寄存器%rax 的内容被写到地址 A, CPU 发起写事务。同样有三个基本步骤。首先 CPU 将地址放到系统总线上。内存从内存总线读出地址并等待数据到达 。接下来 CPU 将 %rax 中的数据字复制到系统总线 。最后主存从内存总线读出数据字并且将这些位存储到 DRAM 中 。内存映射IOCPU 向 I/O 设备发命令时使用一种叫内存映射 I/O 的技术。普通内存地址用来访问 RAM但地址空间里有一部分地址被保留给 I/O 设备。这些地址叫 I/O 端口。当一个设备接到总线上时它会被映射到一个或多个端口。比如磁盘控制器被映射到地址 0xa0。CPU 想读磁盘时可以连续执行三次存储指令写入一个命令字告诉磁盘“开始读”并附带参数比如读完后是否中断 CPU写入要读的逻辑块号写入数据要存放的主存地址。CPU 发完命令后不会一直等着磁盘读完。因为磁盘访问可能要十几毫秒而 1GHz 的 CPU 在这期间可以执行上千万条指令。所以 CPU 会继续做别的事。DMA 磁盘控制器直接把数据写到内存磁盘控制器收到读命令后会把逻辑块号翻译成物理扇区地址然后读出扇区内容。关键点是数据不是先交给 CPU再由 CPU 写进内存而是由磁盘控制器直接写到主存。这个过程叫DMA直接内存访问。DMA 的好处很明显CPU 不用参与数据搬运可以继续执行其他指令效率更高。中断数据到达后通知 CPU当 DMA 传送完成磁盘扇区的数据已经安全放进主存后磁盘控制器会向 CPU 发送一个中断信号。CPU 收到中断后会暂停当前工作跳转到操作系统的一段中断处理程序。这个程序记录“I/O 已完成”然后恢复 CPU 之前被中断的地方。所以整个读磁盘过程可以概括成CPU 发命令 → 磁盘控制器翻译逻辑块 → DMA 传数据到内存 → 中断通知 CPU。固态硬盘SSDSSD 是基于闪存的存储设备通常通过 SATA、USB 等接口接入 I/O 总线对外表现得像普通磁盘一样可以接收 CPU 发出的逻辑块读写请求。一个 SSD 主要由两部分组成组成部分作用闪存芯片替代传统磁盘中的机械盘片用于存储数据闪存翻译层 FTL类似磁盘控制器把逻辑块地址映射到物理闪存块和页闪存的读写机制闪存内部结构是分层的页最小读写单位通常为 512B4KB。块由多个页组成通常为 32128 页大小约 16KB512KB。擦除单位是块只有整个块被擦除后才能重新写入其中的页。写限制一个块擦除后其中每个页可以写一次再次修改需要先擦除整个块。磨损问题闪存块有写入寿命大约 10 万次重复写入后可能磨损失效。因此SSD 写入比读取复杂尤其是随机写擦除块耗时较长通常在毫秒级远高于页访问时间。如果要修改某个已有数据的页必须把该块中仍然有效的数据复制到新块再擦除旧块最后写入新数据。这会导致额外的内部写操作称为写放大。FTL 会通过磨损均衡等机制把擦写操作尽量均匀分布到不同块上从而延长 SSD 寿命。SSD 与旋转磁盘的比较优点没有机械部件随机访问速度快。能耗较低。抗震性更好。读写延迟通常远低于机械磁盘。缺点闪存块存在写入寿命限制。单位容量成本高于机械磁盘。随机写性能通常不如随机读。目前 SSD 已经在便携设备中广泛替代机械磁盘在笔记本、台式机甚至服务器中也越来越常见。局部性一个编写良好的计算机程序常常具有良好的局部性 (locality) 。也就是它们倾向于引用邻近于其他最近引用过的数据项的数据项或者最近引用过的数据项本身。这种倾向性被称为局部性原理 (principle of locality), 是一个持久的概念。**局部性分为两种形式时间局部性和空间局部性。**在一个具有良好时间局部性的程序中被引用过一次的内存位置很可能在不远 的将来再被多次引用 。 在一个具有良好空间局部性的程序中如果一个内存位置被引用了一次那么程序很可能在不远的将来引用附近的一个内存位置。现代计算机系统的各个层次从硬件到操作系统、再到应用程序它们的设计都利用了局部性 。在硬件层局部性原理允许计算机设计者通过引入称为高速缓存存储 器的小而快速的存储器来保存最近被引用的指令和数据项从而提高对主存的访问速度。 在操作系统级局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存 。对程序数据引用的局部性下面给出一个函数sumvec()intsumvec(intv[N]){inti,sum0;for(i0;iN;i)sumv[i];returnsum;}变量sum在每次循环迭代中被引用一次对于sum来说有很好的时间局部性。sum是标量所以没有空间局部性。向量v的元素是顺序读取的对于变量v函数有很好的空间局部性但是时间局部性很差因为每个向量元素只被访问一次。对于循环体中的每个变量这个函数要么有好的空间局部性要么有好的时间局部性所以我们可以断定 sumvec 函数有良好的局部性。sumvec 这样顺序访问一个向最每个元素的函数我们说它具有步长为 1 的引用模式。有时我们称步长为 1 的引用模式为顺序引用模式。一个连续向鼠中每隔 k 个元素进行访问就称为步长为 k 的引用模式。步长为 1 的引用模式是程序中空间局部性常见和重要的来源。一般而言随着步长的增加空间局部性下降。对千引用多维数组的程序来说步长也是一个很重要的问题。下面给出函数sumarrayrows它对一个二维数组的元素求和。双重嵌套循环按照行优先顺序 (row­ major order)读数组的元素。内层循环读第一行的元素然后读第二行依此类推。intsumarrayrows(inta[M][N]){inti,j,sum0;for(i0;iM;i)for(j0;jN;j)suma[i][j];returnsum;}函数 sumarrayrows 具有良好的空间局部性因为它按照数组被存储的行优先顺序来访问这个数组 。其结果是得到一个很好的步长为 1 的引用模式具有良好的空间局部性。数组a的引用格式如下地址048121620内容a00a_{00}a00​a01a_{01}a01​a02a_{02}a02​a10a_{10}a10​a11a_{11}a11​a12a_{12}a12​访问顺序123456下面给出另一个同样是对一个二维数组的元素求和的函数sumarraycols与sumarrayrows的区别是交换了i和j的循环这样导致sumarraycols的局部性很差。intsumarrayrows(inta[M][N]){inti,j,sum0;for(j0;jN;j)for(i0;iM;i)suma[i][j];returnsum;}地址048121620内容a00a_{00}a00​a01a_{01}a01​a02a_{02}a02​a10a_{10}a10​a11a_{11}a11​a12a_{12}a12​访问顺序135246存储器层次结构硬件与软件的特性正好互补。硬件层面存储技术中速度越快的设备每字节成本越高、容量越小CPU与主存之间的速度差距正在扩大。软件层面编写良好的程序往往表现出良好的局部性时间局部性和空间局部性。两者的互补性催生了存储器层次结构这一组织方法所有现代计算机系统均采用此设计。层级存储设备特点访问速度L0CPU寄存器容量极小成本最高1个时钟周期内L1/L2/L3高速缓存SRAM容量较小成本较高几个时钟周期内L4主存DRAM容量较大成本较低几十到几百个时钟周期L5本地磁盘容量大成本低慢L6远程二级存储分布式文件系统、Web服务器容量极大成本最低最慢需网络访问从上往下存储设备变得更慢、更便宜、容量更大。从下往上每一层保存着从下一层取出的数据副本如L1缓存保存从L2取出的缓存行主存保存从磁盘取出的块。存储器层次结构中的缓存高速缓存Cache一个小而快速的存储设备作为更大、更慢设备中数据的缓冲区域。缓存Caching使用高速缓存的过程。核心思想存储器层次结构中第 k 层更快、更小作为第 k1 层更大、更慢的缓存每一层都缓存来自较低一层的数据对象。第 k1 层存储器被划分为连续的数据对象组块称为块每个块有唯一地址/名字。块可以是固定大小通常或可变大小如 Web 服务器上的 HTML 文件。数据总是以块为传送单元在相邻层之间复制。不同层对之间的块大小可以不同越靠近 CPU 的层块越小如 L1L0 用 1 个字越远离 CPU 的层块越大如 L5L4 用几百到几千字节以补偿较长的访问时间。缓存命中与不命中当程序需要第 k 1 层的某个数据对象 d 时它首先在当前存储在第 k 层的一个块中查找 d 。如果 d 刚好缓存在第 k 层中那么就是我们所说的缓存命中。从k层直接读取d比从k1层读取快。如果第 k 层中没有缓存数据对象 d, 那么就是我们所说的缓存不命中 (cache miss)。当发生缓存不命中时第 k 层的缓存从第 k 1 层缓存中取出包含 d 的那个块如果第 k 层的缓存已经满了可能就会覆盖现存的一个块。覆盖一个现存的块的过程称为替换 (replacing) 或驱逐 (evicting) 这个块。被驱逐的这 个块有时也称为牺牲块 (victim block) 。决定该替换哪个块是由缓存的替换策略 (replace­ment policy)来控制的。缓存不命中的种类类型说明强制性不命中Cold Miss冷缓存空缓存时首次访问必然不命中缓存暖身后不再出现冲突不命中Conflict Miss缓存足够大但因放置策略限制如块 i 只能映射到 i mod 4多个块映射到同一位置导致反复不命中容量不命中Capacity Miss程序某阶段的工作集Working Set超过缓存容量缓存太小无法容纳放置策略Placement Policy决定从第 k1 层取出的块放在第 k 层的哪个位置。灵活策略任意块可放任意位置但硬件实现成本高定位代价大。严格策略第 k1 层的块 t 只能放在第 k 层的特定位置如 t mod 4硬件缓存常用此策略但可能引发冲突不命中。缓存管理不同层次的缓存由不同逻辑管理寄存器文件L0由编译器管理决定加载时机和寄存器分配。L1/L2/L3 高速缓存完全由硬件逻辑管理。主存DRAM在虚拟内存系统中由操作系统 CPU 地址翻译硬件共同管理。本地磁盘在分布式文件系统如 AFS中由本地客户端进程管理。高速缓存存储器通用的高速缓存存储器组织结构计算机的高速缓存被组织成一个有S2sS2^sS2s个高速缓存组的数组。每个组包含E个高速缓存行每个行是由一个B2bB2^bB2b字节的数据块 (block)组成的一个有效位 (valid bit) 指明这个行是否包含有意义的信息还有 tm-(bs)个标记位 (tag bit)(是当前块的内存地址的位的一个子集它们唯一地标识存储在这个高速缓存行中的块。高速缓存可描述为元组 (S, E, B, m)。S 2s2^s2s高速缓存组Set数E每组包含的高速缓存行Line数B 2b2^b2b每行的数据块大小字节m物理地址位数地址空间 M 2^mt m − (s b)标记位Tag数缓存容量CS×E×BC S × E × BCS×E×B仅计数据字节不含有效位和标记位每行包含1 位有效位 t 位标记位 B 字节数据块。假设有一条加载指令指示CPU从主存地址A中读取一个字它将地址A发送给高速缓存。如果高速缓存正保存着地址 A 处那个字的副本它就立即将那个字发回给 CPU。下面我们来看下它是如何工作的m 位地址被划分为三段[标记 t 位 | 组索引 s 位 | 块偏移 b 位]。CPU 访问地址 A 时分三步组选择用 s 位组索引定位到具体组。行匹配在该组内逐行检查——有效位为 1 且标记位匹配则命中。字抽取用 b 位块偏移从数据块中取出目标字节。直接映射高速缓存每组仅一行实现最简单但也最容易发生冲突不命中。不命中时替换策略极其简单直接用新块覆盖当前行。工作示例S4, E1, B2, m4地址空间仅 16 字节8 个内存块映射到 4 个组块 0 和块 4 都映射到组 0靠标记位区分。模拟读序列 0→1→13→8→0 可观察到第 5 步读地址 0 时因之前读地址 8 已将块 4 装入组 0块 0 被驱逐产生冲突不命中。冲突不命中与抖动Thrashing当程序访问的两个数组恰好映射到同一组时会在两组数据间反复驱逐/加载称为抖动性能可下降 2~3 倍。经典案例dotprod(x[8], y[8])x 从地址 0 开始y 从地址 32 开始块大小 16 字节缓存仅 2 组。x[0]~x[3] 与 y[0]~y[3] 全部映射到组 0每次迭代都冲突不命中。解决方法在数组末尾添加 B 字节填充如 float x[12] 代替 float x[8]使 x 和 y 的块映射到不同组即可消除抖动。级相联高速缓存直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行组相联高速缓存的每个组都保存有多于一个的高速缓存行。一个1EC/B的高速缓存通常称为 E 路 组相联高速缓存。三个关键步骤组选择与直接映射高速缓存完全相同组索引位标识组行匹配与字选择比直接映射更复杂需要并行检查组内所有行有效位必须设置某一行的标记位必须与地址中的标记位匹配若命中用块偏移从块中选择起始字节不命中时的行替换有空行直接放入无空行选择牺牲行全相联高速缓存全相联是组相联的特例整个高速缓存只有一个组即EC/BEC/BEC/B所有行都在该组中。组选择只有一个组默认总是选择组 0。地址中没有组索引位只划分为| 标记t 位 | 块偏移b 位 |行匹配与字选择与组相联原理相同但规模更大——需要并行搜索所有行的标记。三种映射方式对比特性直接映射组相联全相联每组行数 E11 E C/BC/B组数 SC/BC/(B×E)1地址划分标记|组索引|块偏移标记|组索引|块偏移标记|块偏移冲突不命中最多中等无硬件复杂度最低中等最高高速缓存写策略策略做法优点缺点直写每次写缓存时立即写回低一层实现简单总线流量大写回先只更新缓存等到该行被替换时才写回减少总线流量利用局部性需要额外维护修改位写回需要给每一行增加一个 dirty bit如果该行被修改过替换时就必须写回主存如果没有被修改则可以直接丢弃。写不命中策略做法特点写分配先把低层块加载到缓存再更新利用空间局部性但每次不命中都要传块非写分配不加载到缓存直接写低层避免传块但无法利用缓存局部性常见组合是直写缓存通常配合 非写分配。写回缓存通常配合 写分配。现代系统更倾向于采用写回 写分配模型因为越往下层传送代价越高减少不必要传送更重要。