存储器层次结构
计算机的存储器一般分为多个层次：寄存器-多级缓存-主存-磁盘
为什么要分为这么多层呢？
程序员在使用时希望有无限数量的快速存储器，假如这一点能实现，存储器这一章就不要学了。本章就是在讲在资源有限的情况下，如何进行调度和分配。
“程序员在使用时希望有无限数量的快速存储器”这句话包含两个需求：空间大和速度快。但当前的存储器存在一个矛盾，在预算固定的情况下，速度快的空间不大，空间大的速度不快。于是聪明的体系结构研究者就想到了一个方法-构建存储器层次结构。把速度快的存储器越接近处理器，保证了处理器获取数据的速度，离处理器远的存储器虽然速度越慢，但是存储容量大。通过这样的平衡，可以在一定程度上享受高速的存储器与大容量的存储器。
以上是一些常用设备的存储器层次结构，我看了一下我的笔记本，L1 cache为384KB，L2 cache为1.5MB，L3 cache为12MB，Memory为16GB，硬盘空间为1TB。好像比图里的稍微大一点，是不是技术又进步了？
这是intel i7 Core 解剖图：
存储器层次结构工作原理
Q1：如何获取数据？
- 如果在cache中找不到某个字，就必须从层次结构的一个较低层级去提取这个字，并把它放在缓存中，然后才能继续。
- 出于效率考虑，会一次移动多个字。这是因为空间局域性原理，大多数程序并不是均衡地访问所有代码和数据，而是集中在一段空间中访问。
- 这里移动的多个字，被称为**块(block)**。每个缓存块都有一个标记，指明它与哪个存储器地址相对应。
Q2：如何从主存储器中加载数据到缓存？
由于主存储器块远多于高速缓存块，主存储器块需要竞争才能获取高速缓存中的对应位置。通过对主存储器地址的各个位划分并规定特殊意义来实现地址转换，将地址的二进制位分为不同的组（2～3个地址域）。主要有直接映射、全关联、组关联等。
高速缓存存储器不能通过地址访问，而是按照内容进行存取，因此又被称为内容寻址的存储器（content addressable memory, CAM)，在大部分高速缓存映射策略方案中，要检查或搜索高速缓存的入口确定所需数值是否存放在告诉缓存中。
以上说的比较专业，其实更便于程序员理解的话就是哈希，就是把一个大容量的容器哈希到一个小容器上，而且哈希的方式非常简单，就是对地址直接取模。下面细说一下：
高速缓存的通用组织:
内存的地址一般分为多个区域：
| 标记位 | 组索引位 | 块偏移位 |
|---|---|---|
| t位 | s位 | b位 |
内存中不同的地址根据组索引值会映射到缓存对应的组上，也就是说cache从内存中加载一个块，这个块是放在固定的组上。如果这个组已经占满了，就会把组里的某一个块替换出去（这里又产生了一个新的问题：替换哪一个块呢？于是就有了LRU等替换策略），哪怕其他的组是空的，这个块还是只能放在这个组里。
我们看到一个组可能有很多行，所以cache访问某一个地址能迅速定位到组，但组里怎么找某一行呢？标记位就发挥作用了，只有标记相同才是我对应的数据，如果组里所有标记位都没对上，则表示cache里没有该数据。找到对应行后，根据b就可以迅速找到需要的字节了。
根据E的不同取值，高速缓存可分为很多类别：
直接映射高速缓存(direct mapped)
对于直接映射高速缓存，E=1。每个块中只有一行。假设cache有4个组（S=4），每组1行（E=1），每个块两个字节（b=2），则有
| 地址（十进制） | 标记位 | 索引位 | 偏移位 | 块号 |
|---|---|---|---|---|
| 0 | 0 | 00 | 0 | 0 |
| 1 | 0 | 00 | 1 | 0 |
| 2 | 0 | 01 | 0 | 1 |
| 3 | 0 | 01 | 1 | 1 |
| 4 | 0 | 10 | 0 | 2 |
| 5 | 0 | 10 | 1 | 2 |
| 6 | 0 | 11 | 0 | 3 |
| 7 | 0 | 11 | 1 | 3 |
| 8 | 1 | 00 | 0 | 4 |
| 9 | 1 | 00 | 1 | 4 |
| 10 | 1 | 01 | 0 | 5 |
| 11 | 1 | 01 | 1 | 5 |
| 12 | 1 | 10 | 0 | 6 |
| 13 | 1 | 10 | 1 | 6 |
| 14 | 1 | 11 | 0 | 7 |
| 15 | 1 | 11 | 1 | 7 |
可以看到块0、块4会被映射到同一组里，且对4取模余数相同的块都会被映射到同一组里。
下面来模拟一下这个过程，cache依次读取地址0的字、地址13的字、地址1的字、地址8的字、地址0的字。
- 读地址0
| 组 | 有效位 | 标记位 | 块0 | 块1 |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 0 | |||
| 3 | 0 |
- 读地址13
| 组 | 有效位 | 标记位 | 块0 | 块1 |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
- 读地址1
| 组 | 有效位 | 标记位 | 块0 | 块1 |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
首先找组0，发现组0的标记位为0，cache命中。不需要从缓存中加载。
- 读地址8
| 组 | 有效位 | 标记位 | 块0 | 块1 |
|---|---|---|---|---|
| 0 | 1 | 1 | m[7] | m[8] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
首先找到组0，发现组0标记位为0，没有对上。去内存中找，再把组0原来的块替换掉。
- 读地址0
| 组 | 有效位 | 标记位 | 块0 | 块1 |
|---|---|---|---|---|
| 0 | 1 | 0 | m[0] | m[1] |
| 1 | 0 | |||
| 2 | 1 | 1 | m[12] | m[13] |
| 3 | 0 |
首先找到组0，发现组0标记位为1，没有对上。去内存中找，再把组0原来的块替换掉。
可以看到，以上设置下如果有一个循环，读取数组的值依次隔4个字节，那cache中某一个组就会反复替换，出现“抖动”现象，效率很低。
组相联高速缓存(set associative)
对于组相联高速缓存，$1 < E < \frac{C}{B}(C=BES)$。
逻辑和直接相连差不多，但是由于每个组有很多行，所有电路更复杂，高速缓存必须搜索组中的每一行进行匹配。同时，直接映射发生冲突时可以直接进行替换，组相联高速缓存冲突时，还必须考虑替换哪一行。
全相联高速缓存(full associative)
对于组相联高速缓存，$E =\frac{C}{B}$。
也就是说，全相联高速缓存只有一个组，于是以上提到的组索引地址都不要了，组索引地址直接合到标记位里。
由于只有一组，当空间增大时，行数就会很多。由于在查询时需要扫描所有的行，所以这种方式是比较慢的。高速缓存电路也可以并行地搜索许多相匹配的标记，但构造一个又大又快的相联高速缓存很困难而且很贵。所以全相联高速缓存只适合小的高速缓存，例如虚拟内存中的TLB中缓存页表项。
可以看到最常用的一般还是组相联高速缓存，如果要我用两个词总结以上三种缓存映射的方式，我会用“哈希”和“分块”。之前学过的算法的思想在这里也能运用，这也是为什么在算法课上我会给孩子们说，算法是灵魂，学会了算法，其他的知识都会让你感到似曾相识。
Q3: 缓存应该替换哪一个块？
主要有以下三个策略：
- 随机
- 最近最少使用（LRU）
- FIFO（先进先出）
其实，就是随机算法、贪心算法和队列，感觉没必要再细写了。但有一点值得注意，LRU需要统计每个块最近使用的次数，严格来算的话代价太大，一般实际使用时会采取一些近似的方式，例如通过一个标记位标记上几个使用的块，然后在所有未被标记的块中随机踢出一块。
Q4: 如何写入？
刚才一直在讨论如何读取数据，但写入数据也是一个常用的操作。写入数据当然是要写到主存里，肯定不能只写在缓存里。但是写入数据每次都访问主存比较慢，所以也有一种策略先写在缓存里，当数据从缓存里替换出的时候再写到主存。于是就有两种策略：
- 直写(Write-through)——数据写到缓存和低一级存储器的块
- 写回(Write-back)——数据仅写到缓存，当被替换出缓存时再写入主存储器
直写的好处是很容易实现，且低一级存储器拥有数据的最新副本，从而简化了数据一致性的问题。
写回虽然快，但是数据一致性的处理更麻烦。数据一致性也就是数据在反复读写的时候如何保持一致，尤其是多个处理器读取同一个数据时，如何保证不同处理器能读到最新的数据。
对于写回策略来说，数据仅写到缓存可能会出现write miss的情况，要写的数据不在cache中，这时又有两种策略：
- write allocate： 先把要写的数据从memory加载到cache中，然后再写cache
- no write allocate: 直接写回memory
cache 性能的计算与优化
cache性能计算
CPU执行时间 = （CPU时钟周期 + 存储器停顿周期） * 时钟周期时间
CPU execution = (CPU clock cycles + Memory stall cycles) * Clock cycle time
有了存储器停顿周期(Memory stall clock cycles)取决于缺失数目(Number of misses）和每次缺失的成本（Miss penalty)，后者称为缺失代价：（IC表示指令数）
$$
\begin{array}{lll}
\text{Memory stall clock cycles} &=& \text{Number of misses} \times \text{Miss penalty} \\
&=&IC \times \frac{\text{Misses}}{\text{Instruction}}\times \text{Miss penalty}\\
&=&IC \times \frac{\text{Memory accesses}}{\text{Instruction}}\times \text{Miss rate}\times\text{Miss penalty}
\end{array}
$$
cache性能优化
根据上面的计算公式，优化cache的性能主要考虑两个方面：降低缺失率和减小缺失代价。最基础的方法有以下几种：
- 调整cache的大小：更大的cache可以降低缺失率，但太大的cache会延长命中时间、增加成本和能耗。而过小的cache不能充分利用局部性原理，缺失率较高。
- 调整block的大小：较小的块不能充分利用空间局部性，缺失率较高。但太大的块会增加缺失代价。
- 调整associativity：更高的相联度可以降低缺失率，但会延迟命中时间（想一想全相联）；更小的相联度命中时间降低，但是缺失率提高。
- 软件优化：例如遍历二维数组的时候，改变循环顺序
存储器技术
SRAM和DRAM
说完存储层次结构如何读取写入数据整个大框架，我们再进入底层，看看这些数据是怎么存储的。自1975年以来，几乎所有计算机都采用DRAM作为主存储器，采用SRAM作为缓存。
SRAM第一个字母表示static，DRAM第一个字母表示dyamic。从上面电路图可以看到，DRAM要不断刷新电路，才能保证数据在电容上保存。SRAM通过交叉耦合，数据可以在反相器上存在很久，不需要刷新电路。我们PC在待机时消耗的电量很大一部分来自于对内存的刷新。
那为什么不直接使用SRAM作为内存呢？
可以从电路图上看到SRAM复杂很多，SRAM需要6个晶体管，DRAM只要1个晶体管和1个电容。1个SRAM的花费大概是1个DRAM的1000倍。
Memory Module
DRAM芯片封装在内存模块中，当输入一个地址时，会由多个DRAM芯片输出它对应的8位内容，并组成一个64位字。
Multi-Core Issues in Caching
多处理器体系结构
symmetric (shared-memory) multiprocessors (SMP)
对称（共享存储器）多处理器（SMP），这种结构特点是核心数目较少，通常不超过32个。由于处理器数目小，所以处理器可能共享一个集中式存储器，所有处理器能平等地访问它，这也是为什么叫做“symmetric ”。
distributed shared memory (DSM)
当处理器数量足够多时，SMP就很难扩展。多处理器采用物理分布式存储器，称为分布式共享存储器。在这种结构中，存储器分散在节点之间，既增加了带宽，也缩短了到本地存储器的延迟。但缺点是在处理器之间传送数据的过程变得更复杂了。
缓存一致性问题
在上面的SMP结构中，可以看到每个处理器拥有自己的专用数据，同时多个处理器还有共享数据。虽然说人多力量大，但是这有一个前提是这些人是有组织、有纪律、有合作的。如果所有处理器没有交流都埋头单干，反而会造成数据的混乱，这就是缓存一致性问题。例如，当一个处理器修改了一条数据，但只在自己的专有数据中修改，暂时还没写到共享数据中，它不告诉别人我改了数据，其他处理器就拿不到最新数据。或者一个处理器缓存了某个地址的数据，但这个数据在共享数据中被修改了，如果不做额外处理，该处理器不知道这条数据已过时，就会一直使用过时数据。
所以要解决缓存一致性问题，就相当于我们在小组合作过程中需要增加一些沟通与交流，并达成一个统一的协议——缓存一致性协议。目前使用的协议有两类：
- 目录式(Directory based)：有一个位置保存特定物理存储块的共享状态。在SMP中使用一个集中目录，在DSM中，使用分布式目录。
- 监听式(Snooping)：监听式不需要将共享状态存在一个目录里，而是通过广播的方式，让所有缓存了某个数据副本的cache可以跟踪这个块的共享状态。
通俗地说，目录式就是在小组合作时搞一个共享文档，每个人把自己的修改写进去。监听式就是开一个语音交流，把自己修改的状态跟大伙说一声。
监听一致性
监听一致性协议存在两种策略：
- 一种是Write Invalidate（写无效），当一个处理器更新某共享单元时让其他共享单元的其他备份全部无效
- 一种是Write Update（写更新），当一个处理器更新某共享单元时把更新的内容传播给所有拥有该共享单元的处理器
Write Invalidate通常用于减少数据传输的带宽，它只需要发送一个无效信号，但其他处理器不能及时得到最新的副本。在这种策略下，对于写回缓存的设置，其他处理器读取最新数据要困难一些，当处理器发现自己缓存的块无效，会向低一级存储发出读请求，其他处理器也监听共享总线上的所有地址，如果处理器发现自己的专用缓存拥有被请求的最新数据，则会把最新数据传输给发起读请求的处理器。
Write Update可以减少读操作的延迟，因为其他处理器可以更迅速获得最新数据，但每次写入需要传输更多的数据会占用更多带宽。
简而言之，写无效就是小组合作中给其他组员说”我把数据改了，你们先别用这条数据了。要用的时候来找我。“写更新”就是在说“我把数据改了，你们也一起改一下，修改后的数据是114514…“。
目前Write Invalidate是绝大多数系统的设计，下面以Write Invalidate且写回式cache为例，具体说明实现细节，这个实现和上面简单的介绍略有不同，考虑了效率增加了一些状态，有亿点点不同。
为了表示每条数据是否有效，需要一个状态位来表达这个信息（I）。如果缓存上的数据没被修改（即和内存保持一致），在数据块踢出cache时也没必要写回（M/S）。如果一条数据只有一个处理器拥有，即被独占了，那这条独占的数据被修改，则不需要通知其他处理器缓存，别人都没这条数据，为了效率考虑，我需要一个状态位表示（M/S）。
于是有了MSI协议，该协议设定了三种状态：
- Modified：该数据是否被修改（包含数据块是否独占）
- Shared：数据是否可能被共享
- Invalid：数据是否无效
这三种状态的转移通过两个图可以清晰地表达：
基于cpu请求的状态转移：
基于总线请求的状态转移：
这其实就是有限状态机，学过AC自动机算法的应该很容易看懂。注意这里第二张图中M状态写回块时是会中止主存访问的，读写缺失时M状态提供最新数据。而S状态在读缺失时没有任何操作的，因为如果所有含有该副本的缓存状态都是S状态，说明主存的数据也是最新的，数据由主存提供。其他细节就不细说了，建议细细品味这两张图，非常的巧妙。
在MSI协议中，S状态比较特别，它表示的是一个数据库可能被共享，也就是说会由一些独占的状态被表示成S。例如，初始时所有cache为空，从memory里加载了一个数据，这个数据就是S状态，因为M状态要求这个数据是被修改的，尽管这个数据被处理器独占，但它是S状态。这带来一个问题，我对这种独占的S状态不断写入，它会以为自己被共享，于是向总线发送无效请求，但这是多余的。为了避免这种影响效率的问题，就有了MESI协议，添加了Exclusive状态，表达独占这个状态。当然还可以增加更多状态来提高效率，但是状态转移更加复杂，这里就不展开了。
目录式一致性
之前做了一个比喻：目录式协议就是小组合作中创建了一个共享文档，那么这个文档需要记录什么？一个简单的想法是，需要记录每个数据地址是什么状态，是由一个处理器缓存还是多个处理器缓存？哪些处理器共享这个地址？上面这一串文字可以浓缩为这张表：
| Tag | State | Sharers |
|---|---|---|
| 0xA | Ex | {0} |
| 0xB | Sh | {1, 2} |
这张表涉及到目录的状态这一问题，缓存状态和刚才一样使用MSI目录协议，目录状态稍作调整：
- Uncached：所有处理器都未没有这个缓存块的副本
- Shared：多个处理器缓存了这个块
- Exclusive：一个处理器独占这个块，已经对这个块进行了写操作，存储器副本已经过期
cache中数据的状态转移和snooping的状态转移图基本一致，只是读缺失和写缺失不是发送到总线，而是发给主目录。目录的状态图如下：
虚拟内存
在以上的讨论中，我们的层次结构一直到了memory，现在再向下一层考虑Disk。一般来说进程资源都占用内存，但如果内存不够用了，是否能借用更大的磁盘资源？磁盘如何与内存进行资源调度？多个进程之间如何保证空间隔离？这就要用到虚拟内存。虚拟内存和物理内存不同，它将主存看作是一个存储在磁盘上的地址空间的高速缓存，并每个进程提供一致的地址空间，保护了每个进程不被其他进程破坏。上文我们讨论了cache-memory之间的调度，虚拟内存就是在做memory-disk之间的调度，思想基本是一致的。
有了虚拟内存，cpu生成一个虚拟地址来访问主存，虚拟地址只是为了简化不同进程之间内存管理的一个代号，最终要获取数据还是得用真实地址。就比如中科院计算所只是一个虚拟地址，但我可以根据这个虚拟地址可以找到物理地址“北京市海淀区科学院南路6号”。当然，这就需要一个内存管理单元（memory management unit）来翻译虚拟地址。
类似cache中的块，虚拟内存将磁盘连续空间分为很多页。一部分页缓存在物理内存，一部分页在磁盘上，为了管理这些页，物理内存上存放一个页表，页表每一个条目称为PTE（page table entry)。里面有一位有效位，用来指示该虚拟页存放在主存还是磁盘，后n位地址位表示真实的物理地址。
下面来看一下虚拟内存寻址的具体流程，以下将高速缓存和内存简化为一个整体，首先cpu发出虚拟地址，MMU从虚拟地址中获取前几位表示页表的地址PTEA，去高速缓存中的页表找，如果没找到，再去下一级存储结构中找，假设找到了PTE，就返回给MMU，注意PTE只是存储了一个页面的基址，MMU将虚拟地址的后几位表示的页偏移量位拼上PTE就可以得到真实物理地址，再去高速缓存中获取数据。以上是理想的情况下，如果主存没有缓存对应页，即PTE有效位为0，则称之为缺页，MMU触发异常，操作系统缺页异常处理程序将选择物理内存的牺牲页进行剔除，并调入新的页面更新PTE。
以上流程中，每次cpu产生一个虚拟地址，MMU都要去获取PTE，再翻译成物理地址，为了加速这个过程，MMU直接连了一个小的、虚拟寻址的缓存TLB（Translation Lookaside Buffer），如果命中可以更快获取PTE。
