第六章 存储器层次结构
存储器系统是一个具有不同容量、成本和访问时间的存储器设备的层次结构。
6.1 存储技术
计算机技术的成功很大程度上源自于存储技术的巨大进步。
6.1.1 随机访问存储器
随机访问存储器分为：静态的SRAM、动态的DRAM
1、静态RAM
SRAM的特点：存储器单元具有双稳态特性，只要有电就会永远保持它的值，干扰消除时，电路就会恢复到稳定值。
2、动态RAM
DRAM的特点：每一位的存储是对一个电容的充电；对干扰非常敏感。
用途：数码照相机和摄像机的传感器
DRAM存储不稳定的应对机制：
（1）存储器系统必须周期性地通过读出，或者重写来刷新存储器的每一位；（2）使用纠错码。
SRAM和DRAM的区别：
（1)只要有电，SRAM就会保持不变，而DRAM需要不断刷新；（2）SRAM比DRAM快；（3）SRAM对光和电噪声等干扰不敏感；（4）SRAM比DRAM需要使用更多的晶体管，所以更昂贵。
3、传统的DRAM
行地址i：RAS
列地址j：CAS DRAM组织成二位阵列而不是线性数组的一个原因是降低芯片上地址引脚的数量。
二维阵列组织的缺点是必须分两步发送地址，这增加了访问时间。
4、存储器模块
分类：
168个引脚的双列直插存储器模块，以64位为块传送数据；
72个引脚的单列直插存储器模块，以32位为块传送数据
5、增强的DRAM
快页模式DRAM（FPM DRAM）：异步控制信号，允许对同一行连续的访问可以直接从行缓冲区得到服务。
扩展数据输出DRAM（EDO DRAM）：异步控制信号，允许单独的CAS信号在时间上靠的更紧密一点
同步DRAM（SDRAM）：同步的控制信号，比异步的快
双倍数据速率同步DRAM（DDR SDRAM）：使用两个时钟沿作为控制信号，使DRAM速度翻倍。
Rambus DRAM（RDRAM）：一种私有技术
视频RAM（VRAM）：用在图形系统的帧缓冲区中。
VRAM和FPM DRAM的区别：
（1）VRAM的输出是通过依次对内部缓冲区的整个内容进行移位得到的
（2）VRAM允许对存储器并行地读和写，系统可以在下一次更新的新值写的同时，用帧缓冲区中的像素刷屏幕。
6、非易失性存储器
存储在ROM中的程序通常称为固件。
可编程ROM（PROM）：只能被编程一次
可擦写可编程ROM（EPROM）:使用紫外线实现
电子可擦除PROM（EEROM）:使用印制电路卡实现
闪存（FM）：非易失性存储设备
7、访问主存
读事务：从主存传送数据到CPU
写事务：从CPU传送数据到主存
总线：一组并行的导线，能携带地址、数据和控制信号。
系统总线：连接总线接口和I/O桥
存储器总线：连接I/O桥和主存
6.1.2 磁盘存储
1、磁盘构造
盘片
表面：每个盘片有两个表面
主轴：盘片中央，可旋转
旋转速率：通常5400~15000/min
磁道：同心圆们
扇区：每个磁道被划分为一组扇区
数据位：每个扇区包含相等数量的~，通常为512字节
间隙：存储用来标识扇区的格式化位
磁盘驱动器-磁盘-旋转磁盘
柱面：所有盘片表面上到主轴中心的距离相等的磁道的集合。
2、磁盘容量
记录密度：磁道一英寸的段中可以放入的位数
磁道密度：从盘片中心出发半径上一英寸的段内可以有的磁道数
面密度：记录密度与磁道密度的乘积
记录区：柱面的集合被分割成不相交的子集合
计算磁盘容量的公式：
磁盘容量 = 字节数/扇区 X 平均磁盘数/磁道 X 磁道数/表面 X 表面数/盘片 X 盘片数/磁盘
3、磁盘操作
读写头：磁盘用读写头来读写存储在磁性表面的位
寻道：通过沿着半径轴前后移动的这个传动臂，驱动器可以将读写头定位在盘片上的任何磁道上
在任何时刻，所有的读写头都位于同一个柱面上
读写头碰撞：读写头碰到了阻碍，读写头就会停下来
磁盘以扇区大小的块来读写数据。
访问时间=寻道时间+旋转时间+传送时间
寻道时间：移动传送臂所需要的时间
旋转时间：一旦读写头定位你到了期望的磁道，驱动器等待目标扇区的第一个位旋转到读写头下。
该性能依赖于当读写头到达目标磁道时盘面的位置和磁盘的旋转速度。
最大旋转延迟=1/RPM X 60secs/1min (s)
平均旋转时间是最大旋转时间的一半
传送时间：一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目。
平均传送时间= 1/RPM x 1/(平均扇区数/磁道) x 60s/1min
一个磁盘扇区内容的平均时间为平均寻道时间、平均旋转延迟和平均传送时间之和。
3、逻辑磁盘块
磁盘控制器：磁盘中一个小的硬件、固件设备，维护着逻辑块号和实际物理磁盘扇区之间的映射关系。
三元组（盘面，磁道，扇区）：唯一地标示了对应的物理扇区
4、连接到I/O设备
外围设备互连（PCI）：连接到CPU和主存 I/O总线的分类：
通用串行总线（USB)：包括键盘、鼠标、调制解调器、数码相机、游戏操纵杆、打印机、外部磁盘驱动器和固态硬盘等
图形卡（适配器）：负责代表CPU在显示器上画像素
主机总线适配器：使用特别的主机总线接口定义的通信协议
5、访问磁盘
CPU使用一种称为存储器映射I/O的技术来向I/O设备发出命令。在使用存储器映射I/O的系统中，地址空间中有一块地址是为与I/O设备通信保持的，这样的地址称为一个I/O端口。
CPU通过将命令、逻辑块号和目的存储器地址写到与磁盘相关联的存储器映射地址，发起一个磁盘读。
CPU执行对地址的存储命令，发起磁盘读：
第一条指令时发送一个命令字；第二条指令指明应该读的逻辑块号；第三条指令指明应该存储磁盘扇区内内容的主存地址。
直接存储器访问：设备可以自己执行读或者写总线事务，而不需要CPU干涉的过程。这种数据传送称为DMA传送
基本思想：中断会发信号到CPU芯片的一个外部引脚上。这会导致CPU暂停它当前正在做的工作，跳转到一个操作系统例程。这个程序会记录下I/O已经完成，然后将控制返回到CPU被中断的地方。
6.1.3固态硬盘（SSD）
一个SSD包由一个或多个闪存芯片和闪存翻译层组成，闪存芯片代替传统旋转磁盘中的机械驱动器，而闪存翻译层是一个硬件/固件设备,扮演与磁盘控制器相同的角色，将对逻辑块的请求翻译成对底层物理设备的访问。
随机读和写的性能差别是由底层闪存基本属性决定的。
读写很慢的原因：
1、擦除块需要相对较长的时间2、写操作试图修改一个包含已经有数据的页p，那么这个二块中的所有带有用数据的页都必须被拷贝到一个新（擦除过的）块，然后才能进行对页p的写。
SSD比旋转磁盘更好地优点:随机访问时间比旋转磁盘块，能耗更低，更结实。
缺点是：闪存翻译层中的平均磨损逻辑试图通过将擦除平均分布在所有的块上来最大化每个块的寿命。
6.1.4 存储技术趋势
不同的存储技术有不同的价格和性能折中。
不同存储技术的价格和性能属性以截然不同的速率变化着。
增加密度从而降低成本比降低访问时间更容易。
DRAM和磁盘的性能滞后于CPU的性质。
6.2局部性
局部性：倾向于引用邻近与其他最近引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性，被称为局部性原理。
局部性包括时间局部性和空间局部性。
时间局部性：被引用过一次的存储器位置很可能在不远的将来再被多次引用。
空间局部性：一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置。
6.2.1 对程序数据引用的局部性
步长为k的引用模式：一个连续变量中，每隔k个元素进行访问。
顺序引用模式：具有步长为1的引用模式
随着步长的增加，空间局部性下降。
int sumarraycols(int a[M][N])
{
int i,j,sum = 0;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
sum += a[i][j];
return sum;
}
该程序有良好的空间局部性，是因为数组是按照与它存储在存储器中一样的行优先顺序来被访问的。
int sumarraycols(int a[M][N])
{
int i,j,sum = 0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
sum += a[i][j];
return sum;
}
该程序的空间局部性很差，这是因为它使用步长为N 的引用模式来扫描存储器。
6.2.2 取指令的局部性
循环体里的指令是按照连续的存储器顺序执行的，因此循环有良好的空间局部性，因为循环体会被执行多次，所以它也有良好的时间局部性。
代码区别于程序数据的一个重要属性时在运行时是不能被修改的。
6.2.3 局部性小结
评价一个程序中局部性的简单原则：
重复引用同一个变量的程序有良好的时间局部性；
对于具有步长为k的引用模式的程序，步长越小，空间局部性越好；
对于取指令来说，循环有好的时间和空间局部性，循环体越小，循环迭代次数越多，局部性越好。
6.3 存储器层次结构
存储器层次结构：硬件和软件的这些基本属性（存储技术、计算机软件）互相补充得很完美，这种互相补充的性质使人想到一种组织存储器系统的方法。
6.3.1 存储器层次结构中的缓存
高速缓存：是一个小而快速地存储设备，它作为存储在更大、也更慢的设备中的数据对象的缓冲区域。 缓存：使用高速缓存的过程。
块：第k+1层的存储器被划分成连续的对象片。每个块有一个唯一的地址或名字，使之区别于其他的块。
传送单元：数据总是以块大小为传送单元。
1、缓存命中
但程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d，如果d刚好缓存在第k层中，那么就是我们说的缓存命中。
2、缓存不命中
若第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中。
替换或驱逐：覆盖一个现存的块的过程。
牺牲块：被驱逐的这个块。
替换策略：决定应该替换哪个块。
包括随机替换策略、最近最少被使用替换策略（LRU）等
3、缓存不命中的种类
冷缓存（强制不命中\冷不命中）：一个空的缓存，对于有效位为0的情况
缓存暖身：反复访问存储器使缓存暖身之后的稳定状态
放置策略：发生了不命中，第k层的缓存就必须执行某个放置策略，确定把它从第k+1层中取出来的块放在哪里。
硬件缓存通常使用的是更严格的放置策略。例如：第k+1层的块0、4、8、12会映射到第k层的块0；块1、5、9、13会映射到块1；以此类推。
冲突不命中：限制性的放置策略会引起的一种不命中。
工作集：程序是按照一系列阶段来运行的，每个阶段访问缓存块的某个相对稳定不变的集合。 容量不命中：当工作集的大小超过缓存的大小时。
4、缓存管理
缓存管理：某个东西要将缓存划分成块，在不同的层之间传送块，判定是命中还是不命中，并处理它们。
编译器管理寄存器文件，缓存层次结构的最高层。
L1、L2、L3层的缓存完全是由内置在缓存中的硬件逻辑来管理的。
DRAM主存是有操作系统软件和CPU上的地址翻译硬件共同管理的。
6.4 高速缓存存储器
存储器层次结构只有三层：CPU寄存器、DRAM主存储器和磁盘存储。
6.4.1 通用的高速缓存存储器结构
每个存储器地址有m位，形成M=2^m个不同的地址。
高速缓存组：S = 2^m个高速缓存组的数组
高速缓存行：B = 2^m字节的数据块组成
有效位：指明这个行是否包含有意义的信息
标记位：唯一地标识存储在这个高速缓存行中的块，t = m -(b+s)
高速缓存的大小（容量）C指的是所有块的大小的和。标记位和有效位不包括在内，C = SES。
6.4.2 直接映射高速缓存
直接映射高速缓存：每个组只有一行的高速缓存。
高速缓存确定一个请求是否命中，然后抽取出被请求的字的过程，分为三步：（1）组选择（2）行匹配（3）字抽取
1、直接映射高速缓存中的组选择
2、直接映射高速缓存中的行匹配
当且仅当设置了有效位，而且高速缓存行中的标记与w的地址中的标记相匹配时，这一行中包含w的一个拷贝。
3、直接映射高速缓存中的自选择
4、直接映射高速缓存中不命中时的行代替
用新取出来的行替换当前的行。
5、直接映射高速缓存中的冲突不命中
抖动：高速缓存反复地加载和驱逐相同的高速缓存块的组。
6.4.3 组相联高速缓存
E路组相联高速缓存：1<E<C/B
1、组相联高速缓存中的组选择
2、组相联高速缓存中的行匹配和自选择
基本思路：组中的任何一行都可以包含任何映射到这个组的存储器块。
3、组相联高速缓存中不命中时的行替换
随机选择替换策略：最简单 ****最不常使用策略：替换在过去某个时间窗口内引用次数最少的那一行 最近最少使用策略：替换最后一次访问时间最久远的那一行
6.4.5 有关写的问题
直写：立即将w的高速缓存块写回到紧接着的第一层中
缺点是每次写都会引起总线流量。
写回：只有当替换算法要驱逐更新过的块时，才能把它写到紧接着的低一层中，由于局部性，写回能显著减少总线流量。
缺点是增加了复杂性。
高速缓存必须为每个高速缓存行维护一个额外的修改位，表明这个高速缓存块是否被修改过。
另一个问题是如何处理写不命中。
写分配：加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。
缺点是每次不命中都会导致一个块从低一层传送到高速缓存。
非写分配：避开高速缓存，直接把这个字写到低一层中。
直写高速缓存通常是非写分配的。写回高速缓存是写分配的。
存储器层次结构中较低层的缓存更可能使用写回，而不是直写。
例如，虚拟存储器系统只使用写回。
6.4.6 一个真实的高速缓存层次结构的剖析
即保存指令有包括数据的高速缓存称为统一的高速缓存。
现代处理器包括独立的i-cache和d-cache。
有不同的高速缓存的优点是确保了数据访问不会与指令访问形成冲突不命中，缺点是可能引起容量不命中增加。
6.4.7 高速缓存参数的性能影响
不命中率：不命中数量/引用数量 命中率：1-不命中率 命中时间：组选择、行确认和字选择的时间 不命中处罚：不命中需要的额外的时间。
1、高度缓存大小的影响
较大的高速缓存可能会提高命中率，但也可能增加命中时间。
2、块大小的影响
较大的块能利用程序中可能存在的空间局部性，帮助提高命中率。快越大意味着高速缓存行数越少，对不命中处罚也有负面影响。
3、相联度的影响
相联度E较高，降低了高速缓存由于冲突不命中出现抖动的可能性。 但价格昂贵，运行速度慢，不命中处罚增加。
4、写策略的影响
直写高速缓存能使用独立于高速缓存的写缓冲区，用来更新存储器。高速缓存越往下层，可能使用写回而不是直写。
遇到的问题
1、练习题6.4为什么一旦读/写定位到第一个扇区，需要磁盘转整两圈而不是一圈？
原因：磁盘盘片是有两面的。
参考文献
1、《深入理解计算机系统》课本第六章
2、实验楼实验指导书：https://www.shiyanlou.com/courses/413 实验六、七
3、每周重点：http://group.cnblogs.com/topic/73069.html