存储器层次结构（一）
目录：
1、存储器层次结构：
2、静态RAM：
3、动态RAM：
4、DRAM阵列：
5、南北桥：
6、磁盘：
7、对扇区的访问时间：
8、格式化的磁盘容量：
9、操作系统执行读数据到主存的底层：
10、读文件时间：
11、适配器：
12、固态硬盘：
13、局部性原理：
14、应用局部性原理代码示例：
1、存储器层次结构：
从①到⑦：更大、更慢和每字节成本更低的存储设备。
①寄存器：CPU寄存器保存着从高速缓存存储器取出的字
②L1高速缓存(SRAM)：L1高速缓存保存着从L2高速缓存取出的缓存行
③L2高速缓存(SRAM)：L2高速缓存保存着从L3高速缓存取出的缓存行
④L3高速缓存(SRAM)：L3高速缓存保存着从主存高速缓存取出的缓存行
⑤主存(DRAM)：主存保存着从本地磁盘取出的磁盘块
⑥本地二级存储(本地磁盘)：本地磁盘保存着从远程网络服务器磁盘上取出的文件
⑦远程二级存储(分布式文件系统、Web服务器)
2、静态RAM：
（Static Random-Access Memory，静态随机访问存储器），每个位存储在一个双稳态的存储器单元里，每个位晶体管数为6；相对访问时间快；具有双稳态特性，所以只要有电，就会永远地保持它的值；即使有干扰，当干扰消除时，电路就会恢复到稳定值；相对花费贵，主要应用在高速缓冲存储器上。
3、动态RAM：
（Dynamic Random-Access Memory，动态随机访问存储器），每个位存储在一个对干扰非常敏感的存储单元里，每个位晶体管数为1；相对访问时间慢；当电容的电压被扰乱后，它就永远不会恢复了；相对花费便宜，主要应用在主存以及图形系统的帧缓冲区。
4、DRAM阵列：
（1）电路设计者将DRAM组织成二维阵列而不是线性数组的一个原因是降低芯片上地址引脚的数量。
（2）示例：设r表示一个DRAM阵列中的行数，c表示列数，br表示行寻址所需的位数，bc表示列寻址所需的位数。对于下面的每个DRAM，确定2的幂数的阵列维数，使得max(br,bc)最小，max(br,bc)是对阵列的行或列寻址所需的位数中较大的值。
图4.2 示例参考答案
5、南北桥：
（1）北桥：一块电脑主板，以CPU插槽为北，靠近CPU插槽的一个起连接作用的芯片称为北桥芯片。北桥芯片是主板上离CPU最近的芯片，主要是考虑到北桥芯片与处理器之间通信最密切，为了提高通信性能而缩短传输距离。
北桥被用来处理高速信号，通常处理CPU（处理器），RAM（内存），AGP端口或PCI Express,和南桥芯片之间的通信。
（2）南桥：一般位于主板上离CPU插槽较远的下方，它所连接的I/O总线比较多，离处理器远一些有利于布线。
南桥芯片负责I/O总线之间的通信，如PCI总线（Peripheral Component Interconnect,外围设备互连）、USB、LAN、ATA、SATA、音频控制器、键盘控制器、实时时钟控制器、高级电源管理等。
（3）Intel系统使用北桥的芯片组将CPU连接到内存，使用南桥的芯片组将CPU连接到I/O设备。
（4）示意图：
图5.1 南北桥芯片示意图
6、磁盘：
（1）磁盘转速：
磁盘转速决定磁盘的速度。转速越快，磁盘寻找文件的速度就越快，传输速度越快。目前大部分笔记本电脑所采用的机械式硬盘均是依靠主轴的马达带动盘片高速旋转以产生浮力，使磁头漂浮在盘片上方，要将所要存取数据的扇区带到磁头下方，转速越快则等待时间也就越短，从而也就意味了高效率的工作。
（2）磁盘构造：
①磁盘是由盘片(platter)构成的，每个盘片有两个表面(surface)，表面覆盖着磁性材料。盘片中央有一个可以旋转的主轴，使得盘片以固定的旋转速率旋转，通常是5400-15000转/分钟(Revolution Per Minute,RPM)。
②每个表面由磁道(track,一组同心圆)组成。
③每个磁道被划分为一组扇区(sector)，每个扇区包含数量相等的数据位，这些数据编码在扇区上的磁性材料中。
④扇区之间由一些间隙(gap)分隔，间隙存储用来标识扇区的格式化位。
⑤柱面(cylinder)：所有盘片表面上到主轴中心的距离相等的磁道的集合。
图6.1 磁盘构造
（3）磁盘容量计算：
磁盘容量 = 字节数/扇区 * 扇区数/磁道 * 磁道数/表面 * 表面数/盘片 * 盘片数/磁盘
（4）示例：计算一个磁盘的容量，它有两个盘片，10000个柱面，每条磁道平均有400个扇区，而每个扇区有512个字节。
解：磁盘容量 = 512 * 400 * 10000 * 2 * 2 = 8192 * 10^6字节 = 8.192GB
注意：对于DRAM和SRAM容量的计量单位，通常K=2^10、M=2^20、G=2^20；
对于磁盘和网络的I/O设备容量相关的计量单位，通常K=10^3、M=10^6、G=10^9。
7、对扇区的访问时间：
（1）磁盘用读/写头来读写存储在磁性表面的位，而读/写头连接到一个传动臂的一端，通过沿着半径轴前后移动这个传动臂，驱动器可以将读/写头定位在盘面上的任何磁道上。
在任何时刻，所有的读/写头都位于同一个柱面上。
（2）主要决定部分：
①寻道时间：移动传动臂所需的时间。
②旋转时间：到达期望磁道后，驱动器等待目标扇区的第一个位旋转到读/写头下的时间。
③传送时间：第一个位位于读/写头下时，驱动器开始读或者写该扇区内容的时间。
（3）示例：估计访问下面这个磁盘上一个扇区的访问时间（单位：ms）
图7.1 示例题目
解：T(平均寻道时间) = 8ms
T(平均旋转时间) = 1/2 * 1 / 15000(r/m) * 60(s/m) * 1000(ms/s) * 1(r) = 2ms
T(平均传送时间) = 1 / 15000(r/m) * 60(s/m) * 1000(ms/s) * 1(r) / 500 = 0.008ms
所以T(访问时间) = T(平均寻道时间) + T(平均旋转时间) + T(平均传送时间) = 10.008ms
8、格式化的磁盘容量：
磁盘控制器必须对磁盘进行格式化，然后才能在该磁盘上存储数据。格式化包括：
①用标识扇区的信息填写扇区之间的间隙
②标识出表面有故障的柱面且不使用它们
③在每个区中预留出一组柱面作为备用，当区中柱面损坏，则使用备用柱面
9、操作系统执行读数据到主存的底层：
操作系统首先发送一个命令到磁盘控制器，让它读某个逻辑块号。控制器上的固件执行一个快速表查找，将一个逻辑块号翻译成一个(盘面，磁道，扇区)的三元组，三元组唯一地标识了对应的物理扇区。控制器上的硬件会解释这个三元组，将读/写头移动到适当的柱面，等待扇区移动到读/写头下，将读/写头感知到的位放到控制器上的一个小缓冲区中，然后将它们复制到主存中。
10、读文件时间：
假设1MB的文件由512个字节的逻辑块组成，存储在具有如下特性的磁盘驱动器上：
图10.1 示例题目
（1）最好的情况：给定逻辑块到磁盘扇区的最好的可能的映射（即顺序的）。估计读这个文件需要的最优时间（以ms为单位）。对于下面的情况，假设程序顺序地读文件的逻辑块，一个接一个，将读/写头定位到第一块上的时间是T avg seek + T avg rotation。
解：最好的情况，块被映射在同一柱面上，不用移动读/写头。
逻辑块数量：1MB / 512KB = 2000个
2000 / 1000 = 2圈
T(平均寻道时间) = 5ms
T(平均旋转时间) = 1/2 * 1/10000 * 60 * 1000 = 3ms
T(最大旋转时间) = 1 /10000 * 60 * 1000 = 6ms
T(读/写头定位到第一块上的时间) = 5 + 3 = 8ms
T(最优时间) = T(读/写头定位到第一块上的时间) + 2 * T(最大旋转时间) = 8 + 2 * 6 = 20ms
（2）随机的情况：如果块是随机地映射到磁盘扇区的，估计读这个文件需要的时间（以ms为单位）。
解：随机的情况：读2000块中的每一块都需要T avg seek + T avg rotation（ms）
T(平均寻道时间) = 5ms
T(平均旋转时间) = 1/2 * 1/10000 * 60 * 1000 = 3ms
T(最优时间) = (5 + 3) * 2000 = 16000ms = 16s
11、适配器：
（1）适配器是一个接口转换器，它允许硬件或电子接口与其它硬件或电子接口相连。
（2）不同类型的设备连接到I/O总线：
①通用串行总线控制器（Universal Serial Bus，USB）是一个连接到USB总线的设备的中转机构，USB总线连接各种外围I/O设备，包括键盘、鼠标、调制解调器、数码相机、游戏操纵杆、打印机、外部磁盘驱动器和固态硬盘。USB3.0总线的最大带宽为625MB/s。USB3.1总线的最大带宽为1250MB/s。
②图形适配器：负责代表CPU在显示器上画像素。
③主机总线适配器：将一个或多个磁盘连接到I/O总线，使用的是一个特别的主机总线接口定义的通信协议。
12、固态硬盘：
（1）固态硬盘（Solid State Disk,SSD），基于闪存的存储技术。一个SSD封装由一个或多个闪存芯片和闪存翻译层组成。
（2）SSD优缺点：
①优点：由半导体存储器组成，没有移动的部件，所以随机访问时间比旋转磁盘要快，能耗更低，也更结实。
②缺点：反复写后，闪存块会磨损，因此闪存翻译层中的平均磨损逻辑将擦除平均分布在所有的块上来最大化每个块的寿命。
（3）示例：
如下所示的SSD，Intel保证能够经得起128PB(128 * 10^15B)的写。根据下面的工作负载，估计该SSD的寿命。
图12.1 示例题目
①顺序写的最糟情况：以470MB/s的速度持续地写SSD。
解：128 * 10^15 / (470 * 10^6) = 0.272 * 10^9s = 8.6年
②随机写的最糟情况：以303MB/s的速度持续地写SSD。
解：128 * 10^15 / (303* 10^6) = 0.422 * 10^9s = 13.4年
③平均情况：以20GB/天的速度写SSD。
解：128 * 10^15 / (20 * 10^9) / 365 = 17534年
所以即使在SSD连续工作，也能持续至少八年时间，这大于大多数计算机的预期寿命。
13、局部性原理：
（1）具有良好时间局部性的程序：被引用过一次的内存位置很可能在不远的将来被多次引用。
具有良好空间局部性的程序：一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。
（2）一个连续向量中，每隔k个元素进行访问，就称为步长为k的引用模式(stride-k reference pattern)。对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。具有步长为1的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。
（3）对于取指令来说，循环有很好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。
（4）重复引用相同变量的程序有很好的时间局部性。
14、应用局部性原理代码示例：
（1）改变函数中循环的顺序，使得它以步长为1的引用模式扫描三维数组a：
图14.1 题目示例
解：将a[k][i][j]修改为a[i][j][k]。
（2）下列函数，以不同的空间局部性程度，执行相同的操作。对空间局部性进行排序。
图14.2 题目示例
图14.3 函数一
图14.4 函数二
图14.5 函数三
函数一采用步长为1的引用模式访问数组，跳到下列相对于结构起始位置的偏移处：0、4、8、16、20、24。空间局部性最优。
函数二采用步长不为1的模式，跳到下列相对于结构起始位置的偏移处：0、12、4、16、8、20。所以空间局部性相对clear1函数要差。
函数三跳跃的相对于结构起始位置的偏移处为：0、24、48、72……24(n-2)、24(n-1)、16、40、64……16+24(n-2)、16+24(n-1)。所以空间局部性最差。
综上所得，空间局部性排序为 函数一 优于 函数二 优于 函数三。
参考文献：Randal E.Bryant、David R. O’Hallaron.Computer Systems A Programmer’s Perspective Third Edition 北京：机械工业出版社，2017.4
