在日常的编程中，我们简单的把存储器系统看成一个线性的字节数组，但实际的存储系统并不是这样的。
存储器系统是一个由具有不同容量，不同成本，不同访问时间的若干存储设备组成的层次结构，从上到下依次是：寄存器，高速缓存存储器，主存，硬盘，网络文件。层次越高，容量越小，成本越高，访问时间越短，高层的存储设备是底层存储设备的缓存区。这样，一个编写良好的程序总是倾向于频繁的访问某一个层次上的存储设备。这样，整体效果就是一个大的存储池，其单位成本与最底层的存储设备相当，但是访问速度却可以达到最高层的存储设备。
程序员需要理解存储器的这种层次结构，因为这对程序的性能有很大的影响，比如如果数据存储在寄存器中，那么在一个时钟周期内就能访问，如果存储在高速缓存中，那么需要1-30个周期，如果放在内存中，需要50-200个周期，放在磁盘上需要几千万个周期。
程序的“局部性”属性，使得这种层次结构得以可行，局部性是指：程序倾向于多次访问相同的数据项，或者是倾向于访问临近的数据项。
一：存储技术
1：随机访问存储器
随机访问存储器：RAM，分为两类，静态的（SRAM）和动态的（DRAM）。静态RAM相比动态RAM来说，速度更快，价格更高，因此SRAM常用来作高速缓存存储器，而DRAM常用来作内存。
2：DRAM芯片的简单原理
DRAM芯片中的单元（位）被分成了d个超单元（字），每个超单元都是由w个位组成的。因此总位数就是d*w.
这d个超单元，被组织成了r行c列的长方形阵列，所以d=r*c。这样，每个超单元就可以用(i,j)这样的地址来索引，i表示行，j表示列。
比如一个16*8的DRAM芯片，d=16，w=8。可以组织成4*4=16的阵列，这样，地址信息用2位来传输就可以了，因为2^2=4，数据信息用8位来传输。
每个DRAM芯片都连接到存储控制器，为了读出超单元（i，j）的内容，存储控制器将行地址i发送到DRAM，然后是列地址j，然后DRAM把该地址的内容发送给控制器。行地址i称为RAS请求，列地址j称为CAS请求。RAS请求和CAS请求使用相同的地址引脚。
比如，要读出（2，1）的内容，存储控制器先发送行地址2，此时，DRAM就把行2的整个内容都拷贝到一个内部行缓冲区中，接下来存储控制器发送列地址1，DRAM就把行缓冲区中的单元（2，1）发送给存储控制器。
之所以要把DRAM芯片组织称二位阵列而不是线性数组的结构，是因为这样可以减少地址引脚的数量，缺点是必须分两次传送地址信息。
为了跟上迅速增长的处理器速度，DRAM生产商会定期的推出改进的DRAM存储器。它们基于传统的DRAM最初了改进。
3：非易失性存储器
RAM如果掉电的话，就会失去存储内容，因此他们是易失的。而非易失性存储器，即是在掉电后仍然可以保存信息。由于历史的原因，虽然ROM中有的类型可读也可写，但是还是称他们为只读存储器。ROM以能够重写的次数和重写使用的机制进行区分。
PROM，只能被写一次，
EPROM可以被擦写多次，另外还有EERPROM。
一般ROM的用处是存储“固件”，当计算机上电后，会首先运行ROM中的固件，比如BIOS。
4：访问主存
处理器和DRAM主存之间，通过总线来进行交互，CPU和主存之间的数据传送通过一系列的步骤来完成，这些步骤成为总线事务，读事务是主存传送数据到CPU，写事务是CPU传送到主存。
总线是一组并行的导线，能携带地址，数据和控制信号。在实际的计算机系统中，CPU和主存之间的交互需要经过IO桥芯片组，存储控制器就在其中，系统总线连接CPU和IO桥，存储器总线连接IO桥和主存。见图：
IO桥的作用就是将系统总线的电子信号翻译成存储器总线的电子信号。
比如一个指令：movl A, %eax
将地址A的内容加载到寄存器eax中，CPU发起读事务，读事务由三个步骤组成，首先CPU将地址A放到系统总线上，然后IO桥将信号传送到存储器总线，然后存储器接收到存储器总线上的地址信息，读出地址，取出数据，然后将数据写到存储器总线上，IO桥又把存储器总线的信号翻译成系统总线中，CPU读出系统总线的内容，存储到寄存器中。其中，CPU发送的地址信息，要经过IO桥的转换，成为(i,j)形式的地址。
再比如下面的指令：movl %eax,A
将寄存器的内容写道地址A中的存储器中，CPU发起写事务，首先，CPU将地址放到系统总线上，地址信息经过IO桥传送到存储器总线，主存从存储器总线中读出地址，并且等待数据达到。CPU然后将数据拷贝到系统总线中，经IO桥到了存储器总线，主存在从存储器总线中读取数据存储到相应的单元中。
5：磁盘构造
磁盘中保存着大量信息，但是访问时间却很长，SRAM比磁盘快100万倍，DRAM比磁盘快10万倍。
磁盘有“盘片”，每个盘片都有2个“表面”，表面上覆盖存储材料。盘片以固定速率旋转，通常是5400-15000转每分钟（RPM）。
在表面上，同心圆就是“磁道”，每个磁道被划分为一组“扇区”，每个扇区包含数量相等的数据位，通常是512字节。扇区之间还有“间隙”，间隙用来记录标示扇区的格式化位。
“柱面”，就是多个盘片上，半径相同的磁道组成的。
磁盘容量由以下决定：记录密度，磁道密度，面密度。
记录密度就是磁道上一英寸的段可以存储的位数，磁道密度就是圆心出发的半径上，一英寸的磁道数。面密度就是记录密度和磁道密度的乘积。
在最初的设计中，将每个磁道分为数据相同的扇区，这样，扇区的数量就是由最里面的磁道所决定的，这样越外面的磁道，他的扇区间隔越大。后来，磁盘使用了“记录区”，每个区包含一组连续的柱面，在一个区中，所有的磁道包含相同的扇区。
这样，比如，一个磁盘，包含5个盘片，每个扇区512个字节，每个面20000条磁道，每条磁道平均300个扇区，所以，该磁盘的总容量是：5*2*20000*300*512=30.72GB
注意：在DRAM，SRAM中，K，M，G，T是2^10为基准的。而在磁盘和网络中，却是以10^3位基准的。
6：磁盘操作
磁盘用读写头来在表面上进行读写，读写头连接传动臂，通过传动臂前后移动，读写头可以定位在表面上的任何磁道上，这种机械运动叫做“寻道”，定位在磁道上的读写头，通过磁道的转动，可以定位不同的扇区。每个盘面都有一个读写头，所有的读写头位于同一柱面上。
磁盘是以扇区大小的块来进行读写的。对扇区的访问时间包括：寻道时间，旋转时间，传送时间。
寻道时间，就是将读写头定位到包含目的扇区的磁道上的时间，也就是移动传送臂的时间。
旋转时间，就是等待目标扇区旋转到读写头下的时间。这依赖于读写头所在的位置和盘面的旋转速度。
传送时间，就是目标扇区旋转到读写头下面后，就开始读写了，依赖于旋转速度和扇区数目。
所以，磁盘访问时间主要取决于寻道时间和旋转时间，也就是说，访问扇区的第一个字节需要较长的时间，但是访问剩下的字节几乎不用时间。
7：逻辑磁盘块
可以看见磁盘有着较复杂的结构，为了对操作系统隐藏这样的复杂，将磁盘结构抽象成B个扇区所组成的逻辑序列，编号位0-（B-1），在磁盘中，有一个小的硬件/固件设备，称为磁盘控制器，它负责逻辑块号和实际物理磁盘扇区之间的映射关系。当操作系统想要进行一个IO操作时，比如读一个扇区的数据到主存，操作系统发送命令到磁盘控制器，让他读某个逻辑块，控制器上的固件执行一个快速查找表，将逻辑块号翻译成（盘面，磁道，扇区）的三元组，通过这个三元组就可以唯一的确定一个物理扇区。然后，控制器上的硬件解释这个三元组，将读写头定位到目标扇区所在的柱面上，然后将目标扇区的数据放在控制器中的缓冲区中，最后拷贝到主存。
在磁盘存储数据之前，必须进行格式化，格式化包括把标示扇区的信息填写到扇区之间的间隙之中，标示出有故障的柱面，以及在记录区中预留备用柱面等。
8：访问磁盘
像显卡，监视器，鼠标，键盘，磁盘这样的IO设备，都是通过IO总线连接到CPU和主存的，系统总线和存储器总线与CPU相关，但是IO总线与CPU无关。如图：
CPU使用“存储器映射IO”的技术向IO设备发出命令，这种技术，就是把地址空间中的一块地址当作IO端口，IO端口与IO设备相关联。
比如，假设磁盘控制器被映射到端口0xa，CPU可以通过执行三个对0xa的存储指令，来执行磁盘读操作，第一条指令发送一个命令字，告诉磁盘发起一个读操作，同时还有其他的一些参数，比如读完成时是否中断CPU。
第二条指令指明要读取的逻辑块号
第三条指令指明内存地址。
CPU发起了请求之后，在磁盘进行读的过程中，CPU就可以进行其他的工作了，回想一下，CPU的时钟周期位ns级别，而读磁盘要ms级别，如果在磁盘操作时CPU不能作其他的事情，是一种很大的浪费，因为期间他至少可以执行上千万条指令。
当磁盘控制器接收到读指令后，它将逻辑块号翻译成物理扇区地址，读取该扇区的内容，然后存储到主存中，这个过程是不需要CPU的干涉。设备可以自己执行读或者写的总线事务，而不需要CPU干涉，称为直接存储器访问DMA。在DMA传送完成后，磁盘的内容就存储在了主存中，磁盘控制器可以通过给CPU发送一个中断信号来通知CPU。就是发送信号到CPU的一个外部引脚上，这会导致CPU暂停目前的工作，跳转到一个系统调用中，这个系统调用记录IO操作已经完成，然后，控制返回到CPU被中断的地方。整个过程如图：
a：CPU通过将命令、逻辑块号和目的存储器地址写到与磁盘相关联的存储器映射地址，发起一个磁盘读操作。
b：磁盘控制器读扇区，并执行到主存的DMA传送
c：当DMA传送完成时，磁盘控制器以一个中断通知CPU：
目前的存储技术的趋势是，不同的存储技术有着不同的价格和性能，简单来说就是越快越贵。不同的存储技术的价格和性能的变化有着不同的速率，DRAM和磁盘的性能滞后于CPU的性能，虽然SRAM的性能也滞后于CPU的性能，但是SRAM的性能还是在增长。但是DRAM和磁盘的性能与CPU的性能差距却是在加大的。
二：局部性
局部性原理：引用最近引用过的数据项。这种局部性原理对硬件和软件系统的设计和性能都有着极大的影响。
局部性原理包括：时间局部性和空间局部性。时间局部性是指，被引用过一次的存储器位置，在不远的将来可能再次被引用。空间局部性是指，如果一个存储器位置被引用了一次，那么在不远的将来，程序可能会引用它临近的存储区。
一般而言，具有良好局部性的程序要比局部性差的程序运行的更快。
1：程序数据引用的局部性
int sumvec(int v[N])
{
int i, sum = 0;
for (i = 0; i < N; i++)
sum += v[i];
return sum;
}
sum在每次循环中都会被引用，因此，对于sum来说，具有好的时间局部性，但是没有空间局部性。
因为数组v的元素是顺序排列的，因此对于数组v，具有良好的空间局部性。但是时间局部性较差。所以，综合看来这个程序具有良好的局部性。
上面的程序具有步长为1的引用模式（相对于元素大小）。步长为1的引用模式也叫做顺序引用模式。如果在连续的数组中，每隔k个元素进行访问，就叫做步长为k的引用模式。一般而言，随着步长的增加，空间局部性下降。
int sumarrayrows(int a[M][N])
{
int i, j, sum = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
sum += a[i][j];
return sum;
}
这个函数的引用是步长为1的，因为它按照数组被存储的行优先顺序来访问的。具有很好的空间局部性，但是如果作很小的改动，比如：
int sumarraycols(int a[M][N])
{
int i, j, sum = 0;
for (j = 0; j < N; j++)
for (i = 0; i < M; i++)
sum += a[i][j];
return sum;
}
该程序的访问并不是按照行优先顺序的，因为C数组在存储器中是行优先的，所以，他的步长是N，空间局部性很差。
2：取指令的局部性
对于指令的访问也有局部性的原理，比如for循环中的指令，它是按照连续的存储器顺序执行的，因此具有良好的空间局部性，因为循环会被执行多次，也有很好的时间局部性。对于循环来说，循环体越小，循环的次数越多，局部性越好。
三：存储器层次结构
所有的现代计算机系统中都采用这种方法，一般而言，从上到下，存储设备变的更慢，更便宜，容量更大。高层是寄存器，可以在一个时钟周期内访问，接下来是一个或者多个的基于SRAM的高速缓存存储器，可以在几个CPU时钟周期内访问。下面是基于DRAM的主存，可以在几个到几百个时钟周期内访问到，接下来是慢速但容量很大的磁盘系统，最后还有远程网络上的存储器系统。
存储器层次结构的中心思想是：k层的更小更快的存储设备，作为k+1层的更大更慢的存储设备的缓存。也就是说，层次结构中的每一层都缓存来自较低一层的数据对象。
比如，k+1层的存储设备被划分成连续的块，每个块都有唯一的地址或者名字。第k层的存储器被划分成较少的块的集合，每个块的大小与k+1层的块大小是一样的。在任何时刻，k层的缓存是k+1层的块的子集。
数据总是以块的大小来进行传送的。虽然在层次结构中，相邻层次之间的块大小是相同的，但是其他的层次对之间可以有不同的块大小。
当程序需要第k+1层的某个数据对象d时，它会首先在第k层寻找，如果d刚好在第k层，那就是缓存命中。那么程序就会从第k层直接读取d。
反之，称为缓存不命中。当发生缓存不命中时，第k层的缓存会从k+1层中取出包含d的那个块，如果k层缓存已经满了的话，就会覆盖一个块，称之为替换或者驱逐，有相应的替换策略来决定替换哪个数据块。当k层缓存了k+1层的块后，程序就能从k层直接读取数据d了。
缓存不命中有不同的种类，比如，如果k层的缓存是空的，那么此时的访问都不会命中，称之为冷缓存，在不断的访问过程中，k层的缓存逐渐趋于稳定，称之为暖身。冲突不命中是指，尽管缓存足够大，但是因为多次访问的数据对象，他们会映射到同一个k层的块，缓存就会一直不命中。
在一层上，必须有管理缓存的逻辑存在，缓存管理负责将缓存划分成块，在不同的缓存之间传送块，判定命中还是不命中，并且进行处理。管理缓存的可以是硬件，软件，或者两者的结合。
比如L1，L2，L3的缓存管理完全由缓存中的硬件逻辑负责。DRAM作为硬盘的缓存，是由操作系统和CPU的地址翻译硬件负责的。
四：高速缓存存储器
早期的存储器层次只有三层：寄存器，内存，硬盘。不过，由于CPU和内存之间的差距的不断加大，出现了高速缓存存储器，高速缓存存储器可以有多个层次，比如L1，L2，L3。比如L1，可以在2-4个周期内访问。而L2可以在10个周期内访问，L3可以在30-40个周期内访问，此处我们假设只有L1存在。
如果存储器地址有m位，这样就有2^m个存储地址。此时，高速缓存有S个缓存组，S=2^s，每个组包含E个缓存行，每个缓存行有一个数据块，数据块大小为B个字节，B=2^b。存储器以及缓存中的数据都是以块为单位进行读写的。缓存行中还有有效位标志，表明该行是否包含有意义的信息。另外行中还有t个标记位，他们标示了行中的块。因为会有多个块映射到同一行中。
这样，m位的地址信息就被分割成了若干部分：其中s位，表示该地址会缓存在哪个组；其中的b位，会表示该地址在数据块中的偏移；剩下的t位，是为了区分映射到相同块的地址。因此：t=m-s-b。当然，不要忘了，缓存中还有一个有效位。
这样，高速缓存就可以用（S，E，B，m）来描述，高速缓存的大小就是C=S*E*B。其中不包括标记位和有效位。
当CPU需要从主存地址A中读取一个字时，它将地址A发送到高速缓存。如果高速缓存保存着地址A的数据，就会发给CPU。高速缓存如何知道是否包含A的数据，是根据下面的逻辑处理：
参数S和B将m地址位分成了三部分，m个地址位中，有s个位表示组，于是根据s就知道了该地址对应于哪一个组。找到了相应的组后，就根据t个标记位，找到组中的行，当且仅当设置了有效位并且该行的标记位与地址A中的标记位相匹配时，组中的这一行才包含这个字。找到了这一行后，b指示了在B个字节的数据块中的字节偏移。
根据E的大小，可以将高速缓存划分成不同的类型，当E=1时，称为直接映射高速缓存。以直接映射高速缓存为例，下面讲一下高速缓存的工作方式：
这样一个系统，CPU，寄存器，L1和主存，当CPU需要读取存储在w的指令时，它首先会到L1寻找这个字，如果L1中有这个字，那么就是L1高速缓存命中，否则就是不命中，此时，L1会向主存请求包含w的块，这个时候CPU必须等待，当被请求的数据块达到后，L1会把这个块放到高速缓存行里面，然后在取出w，发送给CPU。告诉缓存确定一个请求是否命中，然后抽取请求字的过程分为：组选则，行匹配，字抽取。
举例来说，如果高速缓存描述如下：
（S，E，B，m）=（4，1，2，4），也就是说，该高速缓存有4个组，即是组表示位有2位，每组有一个缓存行，每行的数据块有2个字节，也就是b=1，存储地址总共有4位，所以，标记位有4-2-1=1位。如图：
当CPU需要读取地址为0的数据时，因为地址是（0000），所以，对应的组号是0，因为组0的开始有效位是0，所以不命中，那么高速缓存直接从内存中取出块0，放到组0中，并且置有效位为1，标记位为0（因为地址是0000）。
当需要读取地址为1的数据时，因为地址是（0001），所以，对应的组号是0，并且组0的有效位为1，并且标记位匹配，所以命中了，那就将块中偏移为1的字节取出来。高速缓存的状态不变。
当需要读取地址13的数据时，因为地址是（1101），所以，对应的组号是2，组2的开始有效位是0，不命中，直接从内存中取出来，放到组2中，并且置有效位为1，标记位为1.
当读取地址8的数据时，会发生不命中，因为地址为（1000），此时，组0的标记位为0，不匹配，所以，覆盖。置标记位为1.
考虑下面的程序：
float dotprod(float x[8], float y[8])
{
float sum = 0.0;
int i;
for (i = 0; i < 8; i++)
sum += x[i] * y[i];
return sum;
}对于数组x和y来说，步长为1，具有良好的空间局部性，但是，并不保证命中率会高，原因如下：
假设float长4个字节，x有8个元素，就是32个字节，假设它被加载到0-31的地址，而y被加载到32-63的地址。假设高速缓存有2个组，是直接映射的，每一个块有16个字节，此时，x[i]和y[i]就会映射到同一个组中，这样，每一次的引用都会出现不命中，这种现象成为抖动。可见，即使程序有良好的空间局部性，高速缓存也有足够的空间存放，但是每次引用还是会导致冲突不命中，这是因为每一次引用的块都映射到了同一个高速缓存组中。这种问题是现实存在的。
组相连高速缓存，指的是高速缓存组中包含有多于一个的缓存行。2路组相连高速缓存就是缓存组包含2个缓存行。
组相连高速缓存的行匹配要比直接映射高速缓存复杂，因为必须检查多个行的标记位和有效位。并且，如果出现不命中时，必须选择一行进行替换，这需要有相应的替换策略。
全相连高速缓存指的是缓存组只有一个，组中包含多个缓存行。
上面讨论的都是读内存的情况，对于写内存，要稍微复杂一些。
比如要写一个已经缓存了的字w，这个是写命中，在高速缓存已经更新了w的缓存后，如何更新下一层的拷贝？可以“直写”，就是立即将w的高速缓存写回到紧邻低一层的缓存中。直写的缺点是每次都会引起总线流量。也可以“写回”，就是尽可能的推迟存储器更新，只有当该缓存行需要被替换的时候，才写低一层的缓存。缺点是增加了复杂性。
上面是写命中的情况，如果写不命中，如何处理？可以“写分配”，先加载低一层的块到高速缓存中，然后在更新高速缓存块。可以“非写分配”，避开高速缓存，直接写到低一层中。
直写高速缓存通常是非写分配的。写回高速缓存通常是写分配的。
高速缓存越大，命中率会提高，但是命中时间也就越长；缓存块越大，空间局部性好的程序就会受益，但是，高速缓存容量一定的情况下，块越大，缓存行也就越少，那么，时间局部性更好的程序就会受损。较高的相连度，会降低抖动的可能性，但是成本也就越高，速度会变慢。
程序员应该尝试去编写高速缓存友好的代码。高速缓存既保存数据，也保存指令。
《深入理解计算机系统》第六章：存储器层次结构笔记