计算机系统基础——存储器层次结构
存储器层次结构
存储器系统
存储器系统是一个由具有不同容量，不同成本，不同访问时间的若干存储设备组成的层次结构，从上到下依次是：寄存器，高速缓存存储器，主存，硬盘，网络文件。 层次越高，容量越小，成本越高，访问时间越短，高层的存储设备是底层存储设备的缓存区。 这样，一个编写良好的程序总是倾向于频繁的访问某一个层次上的存储设备。
存储技术
1.随机访问存储器
随机访问存储器：RAM，分为两类，静态的（SRAM）和动态的（DRAM）。静态RAM相比动态RAM来说，速度更快，价格更高，因此SRAM常用来作高速缓存存储器，而DRAM常用来作内存。
关于传统的DRAM
DRAM芯片中的单元（位）被分成了d个超单元（字），每个超单元都是由w个位组成的。因此总位数就是dw.
这d个超单元，被组织成了r行c列的长方形阵列，所以d=rc。这样，每个超单元就可以用(i,j)这样的地址来索引，i表示行，j表示列。
比如一个168的DRAM芯片，d=16，w=8。可以组织成44=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芯片组织称二位阵列而不是线性数组的结构，是因为这样可以减少地址引脚的数量，缺点是必须分两次传送地址信息。
2.非易失性存储器非易失性存储器
RAM如果掉电的话，就会失去存储内容，因此他们是易失的。
而非易失性存储器，即是在掉电后仍然可以保存信息。由于历史的原因，虽然ROM中有的类型可读也可写，但是还是称他们为只读存储器。ROM以能够重写的次数和重写使用的机制进行区分。
PROM，只能被写一次，
EPROM可以被擦写多次，另外还有EERPROM。
一般ROM的用处是存储“固件”，当计算机上电后，会首先运行ROM中的固件，比如BIOS。
3.访问主存
处理器和DRAM主存之间，通过总线来进行交互，CPU和主存之间的数据传送通过一系列的步骤来完成，这些步骤成为总线事务，读事务是主存传送数据到CPU，写事务是CPU传送到主存。
总线是一组并行的导线，能携带地址，数据和控制信号。在实际的计算机系统中，CPU和主存之间的交互需要经过IO桥芯片组，存储控制器就在其中，系统总线连接CPU和IO桥，存储器总线连接IO桥和主存。
4.磁盘构造
磁盘是由盘片构成的。每个盘片有两面或被称为表面，表面覆盖着磁性纪录材料。盘片中间有一个可以旋转的主轴，它使得盘片以固定的速率旋转，通常是5400～15000转每分钟。磁片通常包括一个或多个这样的盘片，并密封在一个封闭的容器内。
5.磁盘容量
一个磁盘上可以记录的最大位数称为它的最大容量，或者简称为容量。磁盘容量由以下技术因素决定：
1.记录密度：磁道一英寸的段中可放入的位数。
2.磁道密度：从盘片中心出发半径上一英寸的段内可以有的磁道数。
3.面密度：记录密度与磁道密度的乘积。
磁盘容量的公式：字节数/扇面X平均扇面数/磁道数X磁道数/表面X表面数/盘片X盘片数/磁盘
例如：比如，一个磁盘，包含5个盘片，每个扇区512个字节，每个面20000条磁道，每条磁道平均300个扇区，所以，该磁盘的总容量是：5123002000025=30.72GB
6.磁盘操作
磁盘用读写头来在表面上进行读写，读写头连接传动臂，通过传动臂前后移动，读写头可以定位在表面上的任何磁道上，这种机械运动叫做“寻道”，定位在磁道上的读写头，通过磁道的转动，可以定位不同的扇区。每个盘面都有一个读写头，所有的读写头位于同一柱面上。
磁盘是以扇区大小的块来进行读写的。对扇区的访问时间包括：寻道时间，旋转时间，传送时间。
寻道时间，就是将读写头定位到包含目的扇区的磁道上的时间，也就是移动传送臂的时间。
旋转时间，就是等待目标扇区旋转到读写头下的时间。这依赖于读写头所在的位置和盘面的旋转速度。
传送时间，就是目标扇区旋转到读写头下面后，就开始读写了，依赖于旋转速度和扇区数目。
所以，磁盘访问时间主要取决于寻道时间和旋转时间，也就是说，访问扇区的第一个字节需要较长的时间，但是访问剩下的字节几乎不用时间。
7.固态硬盘
固态硬盘（SSD),是一种基于闪存的存储技术，在某些情况下是传统旋转磁盘的极有吸引力的替代产品。
其基本思想如图：
局部性
一个编写良好的计算机程序常常具有良好的局部性。
局部性原理：引用最近引用过的数据项。这种局部性原理对硬件和软件系统的设计和性能都有着极大的影响。
局部性原理包括：时间局部性和空间局部性。时间局部性是指，被引用过一次的存储器位置，在不远的将来可能再次被引用。
空间局部性是指，如果一个存储器位置被引用了一次，那么在不远的将来，程序可能会引用它临近的存储区。
一般而言，具有良好局部性的程序要比局部性差的程序运行的更快。
1.对程序数据引用的局部性
int sumvec(int v[N]){
int i, sum=0;
for(i=0;i<N;i++)
sum+=v[i];
return sum;
}
以上的简单函数，变量sum在每次循环迭代中被引用一次，因此，对于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的主存，可以在几个到几百个时钟周期内访问到，接下来是慢速但容量很大的磁盘系统，最后还有远程网络上的存储器系统。
1.存储器层次结构中的缓存
高速缓存是一个小而快的存储设备，他作为存储在更大也更慢的设备中的数据对象的缓冲区域。使用其的过程称为缓存。
存储器层次结构的中心思想是：**k层的更小更快的存储设备，作为k+1层的更大更慢的存储设备的缓存。**也就是说，层次结构中的每一层都缓存来自较低一层的数据对象。
比如，k+1层的存储设备被划分成连续的块，每个块都有唯一的地址或者名字。第k层的存储器被划分成较少的块的集合，每个块的大小与k+1层的块大小是一样的。在任何时刻，k层的缓存是k+1层的块的子集。
当程序需要第k+1层的某个数据对象d时，它会首先在第k层寻找，如果d刚好在第k层，那就是缓存命中。那么程序就会从第k层直接读取d。
当程序需要第k+1层的某个数据对象d时，它会首先在第k层寻找，如果d刚好在第k层，那就是缓存命中。那么程序就会从第k层直接读取d。
反之，称为缓存不命中。当发生缓存不命中时，第k层的缓存会从k+1层中取出包含d的那个块，如果k层缓存已经满了的话，就会覆盖一个块，称之为替换或者驱逐，有相应的替换策略来决定替换哪个数据块。当k层缓存了k+1层的块后，程序就能从k层直接读取数据d了。
缓存不命中有不同的种类，比如，如果k层的缓存是空的，那么此时的访问都不会命中，称之为冷缓存，在不断的访问过程中，k层的缓存逐渐趋于稳定，称之为暖身。冲突不命中是指，尽管缓存足够大，但是因为多次访问的数据对象，他们会映射到同一个k层的块，缓存就会一直不命中。
2.高速缓存存储器
早期的存储器层次只有三层：寄存器，内存，硬盘。不过，由于CPU和内存之间的差距的不断加大，出现了高速缓存存储器，高速缓存存储器可以有多个层次，比如L1，L2，L3。比如L1，可以在2-4个周期内访问。而L2可以在10个周期内访问，L3可以在30-40个周期内访问。
高速缓冲存储器通用组织：如果存储器地址有m位，这样就有2m，此时，高速缓存有S个缓存组，S=2s，每个组包含E个缓存行，每个缓存行有一个数据块，数据块大小为B个字节，B=2^b。存储器以及缓存中的数据都是以块为单位进行读写的。缓存行中还有有效位标志，表明该行是否包含有意义的信息。另外行中还有t个标记位，他们标示了行中的块。因为会有多个块映射到同一行中。
这样，高速缓存就可以用（S，E，B，m）来描述，高速缓存的大小就是C=SEB。其中不包括标记位和有效位。
当CPU需要从主存地址A中读取一个字时，它将地址A发送到高速缓存。如果高速缓存保存着地址A的数据，就会发给CPU。高速缓存如何知道是否包含A的数据，是根据下面的逻辑处理：
参数S和B将m地址位分成了三部分，m个地址位中，有s个位表示组，于是根据s就知道了该地址对应于哪一个组。找到了相应的组后，就根据t个标记位，找到组中的行，当且仅当设置了有效位并且该行的标记位与地址A中的标记位相匹配时，组中的这一行才包含这个字。找到了这一行后，b指示了在B个字节的数据块中的字节偏移。这样，就能正确的找到该读取的字。
3.组连高速缓存和全相联高速缓存
组相连高速缓存，指的是高速缓存组中包含有多于一个的缓存行。2路组相连高速缓存就是缓存组包含2个缓存行。
组相连高速缓存的行匹配要比直接映射高速缓存复杂，因为必须检查多个行的标记位和有效位。并且，如果出现不命中时，必须选择一行进行替换，这需要有相应的替换策略。
全相连高速缓存指的是缓存组只有一个，组中包含多个缓存行。