计算机技术的成功很大程度上源自于存储技术的巨大进步。本章首先对一些基本的存储技术进行了介绍，然后介绍了编写良好的程序所具有的局部性原理，最后介绍了存储器的层次结构，缓解了内存速度过慢无法和处理器速度相匹配的问题。
CPU执行指令，而存储器系统为CPU存放指令和数据。存储器系统(memory system)是由具有不同容量、成本和访问时间的存储设备组成的层次结构。
存储器层次结构对应用程序的性能有巨大影响。如果数据存储在寄存器中，那么0个始终周期内就能访问到它们；如果存储在高速缓存中，则需要4 ~ 75个周期；如果存储在主存中，则需要上百个周期；如果存储在磁盘上，则需要几千万个周期。
之所以会有这样的差异，是因为不同存储器中使用的存储技术不同。基本的存储技术包括SRAM存储器，DRAM存储器，ROM存储器，磁盘以及固态硬盘。
存储技术
随机访问存储器
随机访问存储器(Random-Access Memory, RAM)分为两类：静态的和动态的。静态RAM(SRAM)比动态RAM(DRAM)更快，但也更贵。SRAM常用来作为高速缓存存储器，DRAM常用来作为主存以及图形系统的帧缓冲区。
- SRAM：将每个位存储在一个双稳态存储器单元中，其中每个单元用一个六晶体管电路来实现。双稳态是指该存储器单元可以无限期地保持在两个不同的电压配置之一，其他任何状态都是不稳定的。只要有电，SRAM存储器单元就会保持它的值，即使有干扰扰乱电压，当干扰消除时电路就会恢复到稳定值。
- DRAM：将每个位存储为对一个电容的充电。每个单元由一个电容柜和一个访问晶体管组成。与SRAM不同，DRAM存储器单元对干扰非常敏感，当电容的电压被扰乱之后，它就不会恢复了。暴露在光线下会导致电容电压改变，实际上，数码相机中的传感器本质上就是DRAM单元的阵列。
非易失性存储器
如果断电，DRAM和SRAM会丢失它们的信息，而非易失性存储器即使在关电后，仍然保存着它们的信息。现在有很多种非易失性存储器，虽然有的可以读也可以写，但整体上被称为只读存储器(ROM)。
可编程ROM(PROM)只能被编程一次。可擦除可编程ROM(EPROM)能够被擦除和重编程的次数可达千次。电子可擦除PROM(EEPROM)能够被编程的次数可达次。
闪存(flash memory)是一种基于EEPROM的存储技术，为大量的电子设备提供快速而持久的非易失性存储。
磁盘存储
RAM必须在有电的时候才能存取数据，而磁盘则能永久存储大量数据。磁盘是一种机械的非易失性存储设备。不过从磁盘上读数据的时间为毫秒级，比DRAM慢了10万倍，比SRAM慢了100万倍。
磁盘由盘片和主轴构成。每个盘片有两面(也称表面)，表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴，使得盘片以固定的旋转速率旋转，通常为5400 ~ 15000转每分钟。磁盘通常包含一个或多个叠放在一起的盘片，封装在一个密封的包装里。
盘片的每个表面由一组称为磁道的同心圆组成。每个磁道被划分为一组扇区。每个扇区包含相等数量的数据位(通常是512字节)，编码在扇区上的磁性材料中。扇区之间由一些间隙隔开，间隙中不存储数据位，而是用来存储标识扇区的格式化位。
通常磁盘又被称为旋转磁盘或机械硬盘，以区别于基于闪存的固态硬盘，固态硬盘是没有移动部分的。
一个磁盘上可以记录的最大位数称为磁盘容量。
磁盘通过读写头来读写存储在磁性表面的位。读写头连接到一个传动臂上，通过沿着半径方向移动传动臂，可以将读写头定位在盘片的任何磁道上。在这个过程中读写头垂直排列，一致行动。
磁盘读写数据(访问扇区)的时间主要受以下因素影响：
- 寻道时间：读写数据时，传动臂首先要将读写头定位到包含目标扇区的磁道上，这个移动过程所花的时间称为寻道时间。寻道时间主要依赖于读写头的初始位置和传动臂在盘面上移动的速度。
- 旋转时间：一旦读写头移动到目标磁道上，就需要等待目标扇区的第一个位旋转到读写头下，这个过程所花的时间称为旋转时间。最坏的情况下，读写头刚错过目标扇区，必须等待磁盘转一整圈。
- 传送时间：当目标扇区的第一个位位于读写头下时，驱动器开始读或写该扇区的内容。
逻辑磁盘块：
为了对操作系统隐藏磁盘构造的复杂性，现代磁盘将它们的构造呈现为一个简单的视图，一个B个扇区大小的逻辑块的序列，编号为0,1，...，B-1。
磁盘封装中有一个小的硬件设备，称为磁盘控制器，维护着逻辑块号与实际物理磁盘扇区之间的映射关系。
当操作系统想要执行一个I/O操作时，例如读一个磁盘扇区的数据到主存，操作系统会发送一个命令到磁盘控制器，让它读某个逻辑块号。控制器执行一个快速表查找，将一个逻辑块号翻译成一个(盘面、磁道、扇区)三元组，唯一标识了对应的物理扇区。控制器上的硬件会解释这个三元组，将读写头移到适当的柱面，等待扇区移动到读写头下，将读写头感知到的位放到控制器上的一个小缓冲区中，然后将它们复制到主存中。
固态硬盘
固态硬盘(Solid Sate Disk, SSD)是一种基于闪存的存储技术，由一个或多个闪存芯片以及闪存翻译层组成。闪存芯片替代了磁盘中的机械驱动器，闪存翻译层替代了磁盘控制器，将对逻辑块的请求翻译成对底层物理设备的访问。
如图所示，一个闪存由B个块组成，每个块又由P个页组成。通常，页的大小为512B ~ 4KB，块的大小为16KB ~ 512KB。
数据在SSD中是以页为单位读写的。在写入数据前，需要对一页所属的块进行擦除，即将该块中所有位都设置为1，而写入操作其实就是将部分位置设置为0。
当擦除次数过多后，块会因磨损而损坏。为了减少这种磨损带来的影响，闪存翻译层使用一种平均磨损算法，来将擦除平均分布在所有块上来最大化每个块的寿命。
局部性原理
一个编写良好的程序通常要求具有良好的局部性。也就是它们倾向于引用最近被引用过的数据项邻近的数据项，或最近引用过的数据项本身，这种倾向被称为局部性原理，对硬件和软件系统的设计和性能有极大影响。
局部性分为时间局部性和空间局部性。时间局部性是指被引用过一次的数据项很可能在不远的将来再被多次引用。空间局部性是指一个内存位置被引用了一次，那么程序很可能在不远的将来引用它附近的内存位置。
e.g. 比如遍历读取二维数组的每个元素时，采样行优先顺序读的程序的空间局部性就比采用列优先顺序读的程序的空间局部性好，因为二维数组在内存中是按照行优先顺序存储的。
存储器层次结构
为了将不同存储技术的差异性和计算机软件对局部性的要求两者结合起来，人们构造了存储器层次结构来组织存储器系统。
存储器层次结构的中心思想是：每一层都缓存来自下一层的数据对象。
数据总是以块大小为传送单元在第k层和第k+1层之间来回复制。
- 缓存命中：当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的块中查找d，若d刚好缓存在第k层，就是缓存命中。这时程序直接从第k层读取d。
- 缓存不命中：如果第k层没有缓存数据对象d，就是缓存不命中。此时第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。第k层从第k+1层取出目标块后，程序就可以像前面一样从第k层读出d了。
覆盖现存的一个块的过程称为替换或驱逐这个块。决定该替换哪个块是由替换策略控制的，比如随机替换策略、最近最少被使用(LRU)替换策略。
高速缓存
早期计算机系统的存储器层次结构只有三层：CPU寄存器、DRAM主存储器和磁盘。但是，随着CPU和主存之间的性能差距不断增大，系统设计者被迫在CPU寄存器和主存之间插入了高速缓存存储器。
读的问题：
高速缓存关于读的操作非常简单。首先，在高速缓存中查找所需字w的副本，如果命中，立即返回字w给CPU；如果不命中，从存储器层次结构中较低层取出包含字w的块，将这个块存到某个高速缓存行中(可能会驱逐一个有效的行)，然后返回字w。
写的问题：
写的情况要复杂一些。假设要写一个已经缓存了的字w (写命中)，在高速缓存更新了w的副本之后，还需要更新它在层次结构下一层的副本。
- 直写：立即将w的高速缓存块写回到下一层中，缺点是每次写都会引起总线流量。
- 写回：尽可能推迟更新，直到替换算法要驱逐这个更新过的块时才把它写到下一层中。这样显著减少了总线流量，但是增加了复杂性，因为这样高速缓存行需要维护一个额外的修改位，表明这个高速缓存块是否被修改过。
在写的时候也会出现写不命中的问题，这是有两种方法：
- 写分配：加载相应的下一层中的块到高速缓存中，然后更新这个高速缓存块。写分配试图利用写的空间局部性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。
- 非写分配：避开高速缓存，直接把这个字写到下一层中。
建议程序员在心里采用一个使用写回和写分配的高速缓存模型。
