操作系统内存分层

在学习编程语言时，我们仅仅把内存当做一个字节数组（可以用地址下标来访问的一个大的字节数组），但实际上存储系统是一个非常复杂的设备层次结构，它提供了一个抽象，将内存结构抽象成了一个大的线性数组，我们可以体会到多种存储设备之间属性的美妙融合（缓存），以及程序的局部性属性在其中起到的作用。

1 存储技术与趋势（了解各个存储设备的性能和运行速度）

随机访问存储器（RAM），也就是当前的内存，它一般都是被打包成芯片，然后将这样很多个芯片组合就形成了主存，其最基本存储单元为bit。

而RAM又可以分为两种，一种是SRAM，另一种是DRAM，它们之间根据存储单元来区分的，例如，例如DRAM只需要一个晶体管去存储1 bit,而SRAM更复杂,需要约4或6个晶体管来存储1 bit，因为SRAM的每一个存储单元都比DRAM复杂的多，但SRAM的速度也比DRAM快一个数量级
所以我们将SRAM用于那些容量小但速度非常快的芯片中，叫做高速缓存，相比之下。DRAM被广运用于主存。以及图形显卡中的帧缓存中，现在DRAM和SRAM都是易失的,意味着如果断电。就会丢失它们所保存的信息，再把电脑打开时，需要从硬盘中重新加载所有东西。

另一种存储器被称为非易失性存储器RAM，即使断电的情况下也可以保存其中的内容，因此这些非易失性存储器的通用名称是只读存储器(ROM)，它们只可以在其芯片生产期间被原编码一次，然后可以使用20-30年，当然，现在ROM的编程方式和删除方式都有所改进（为了满足BIOS的更新），它们可以重新编码，今天我们所拥有的现代形式是只读内存被称为闪存（EPROM），它提供了擦除功能，你可以删除内存上面的存储块，缺点是闪存约在10W次擦除后就会出现磨损，ROM可以在固件和软件中使用，当你开启电脑会调用BIOS，以及开机后执行的最初指令，都存储在ROM中，然后会有一个boot（装载OS）引导程序，将越来越多的信息和指令都装载到内存中。

tip：I/O设备中也有小型计算机，被称为控制器，控制器由存储在ROM中的指令和数据组成（应该是驱动），同时，SSD（固态硬盘）中可以看到ROM，系统仍然把SSD当做旋转的硬盘，但它们实际上是闪存构成的。

2 数据的读和写

CPU到主存

主存是通过一些电子线路连接到CPU的，这被称为主线（BUS），数据流就可以从内存和CPU芯片之间来回传输。
CPU芯片中有一些寄存器（总共16个），例如%rax，%rdi等通用寄存器（寄存器只完成取值），还有一个算术逻辑单元（ALU）会从寄存器文件读写数据（进行运算）。如果指令需要访问内存数据时，就需要执行一个移动指令（mov），移动指令会读写内存，然后由总线接口处理，该接口连接与另一个接口相连接（北桥），我们称之为系统总线，然后I/O桥连接到另一条主线，叫做存储器主线，连接I/0桥与主存。
tip：另一个接口（这是一个芯片集合，称为I/0桥，inter称之为芯片组），是与CPU芯片区分开来的一个芯片集合。（北桥），负责与CPU通信，并且连接高速设备（内存/显卡）

现在，执行一个装载操作，如执行movq指令，将A地址处8个字节加载到寄存器%rax，之所现我们称之为加载(load,是从CPU的角度出发来考虑的我们是加载数据到CPU中，但实际上我们是从主存中加载数据到CPU的。
首先,CPU将A的地址放到存储器主线上,然后主存储器感知到这个信号后。读取这个地址A处8字节的内容也就是它会从该地址取得一个8字节的字的内容然后将其放回总线上,这些比特会在I/O桥上传递回总线接口，然后CPU从总线数据中读取这个字x,然后放到寄存器%rax中，写入类似。
CPU也将地址写在存储器总线上，主存读取这个地址，然后等待数据到总线，主存再读取这些数据，将其存放在地址A处。

其中的关键操作就是寄存器的读写，因为寄存器是很接近算术逻辑单元的，这一切都发生在大约几个CPU周期内，然而，内存距离CPU较远，当你读写内存时，就必须在总线上做多个操作，数据必须通过总线传播，所有这些操作都需要时间，所以对于内存的读写，典型地需要大约50-100纳秒，而寄存器之间的一些操作所需时间甚至不到1纳秒，所以它们之间大约差了两个数量级。如果需要离开CPU芯片，到主存那取东西，这就是内存系统引入的第一个损耗。

硬盘

硬盘是极其广泛应用的存储技术，硬盘其实是一系列的盘片，每个盘片都涂有磁性材料，然后在该磁性材料中编码1和0的二进制位，如图，有一个部件叫做传动臂，然后它可以漂浮在盘片上它漂浮在盘片上方的薄薄一层空气中，在最末端有一个读/写头，可以感应编码位的磁场变化，这些盘片以逆时针旋转，传动臂可以前后移动（有很多齿轮等机械装置），所以旋转磁盘是机械性质，意味着它会比DRAM和SRAM慢，而且他还有电子设备，类似固件中的一台小电脑一样，控制了驱动器的操作，该驱动器控制磁臂如何移动，并且控制如何从读写头读取数据。

其中细节，磁盘由盘片组成，一个盘片有两个表面，上面和下面，每一个表面都包含一系列的同心圆，称之为磁道，每一个磁道包含很多扇区，扇区存储着数据（典型每个扇区存放512字节），在这些扇区之间有一些空隙，这些空隙是不保存数据的。

盘片在主轴上是彼此对齐的，因此在不同表面，轨道也是对齐的，这些轨道的集合，我们称之为一个柱面，因为它形成额一个圆柱形（磁柱），磁柱也是一般我们分割硬盘时的最小单位了!

磁盘的容量就是它可以存储的位数，由两个因素决定：

1. 记录密度，决定单独一个扇区可以存放多少bit
2. 磁道密度，指可以将相连磁道放置得多临近
   这两者的乘积被称为面密度，决定了磁盘的存储容量。
   以前的磁盘面密度很低，每一个磁道上包含的扇区是一个常数，越往外，扇区的间隙越大，浪费了很多磁盘上的空间，不过盘面密度较低时还可以接受，但随着技术的发展，浪费空间这不太能接受。

现代系统将磁盘划分为所谓的记录区，每个新的记录区的每一条磁道包含更多数量的扇区，越往外的磁道比靠内的磁道有更多的扇区（解决扇区之间间隙过大的方法），所以每一条磁道所包含的扇区不再是一个常数，于是使用平均值，简单的写法如下:Head x Cylinder x Sector x 512 Bytes。

硬盘如何工作呢？
磁盘以逆时针旋转，磁臂沿着半径轴前后移动，可以定位到任何一个磁道上。

当多个盘片时，每一个盘片都有磁臂（每个表面都有一个读写头），所以一个盘片有两个磁头，然后将这些磁头连接在一起，控制器可以控制器一点点移动来匹配所有表面上的所有轨道。

下面我们看一下读取数据的方式，箭头表示磁头位置，磁盘以逆时针旋转。
当蓝色扇区在读写头下旋转，读写头当前位置正好可以读取这个蓝色的扇区，它会检测这些比特，并将它们发送到控制器，控制器将他们传递回CPU。

现在，CPU请求磁盘，要求磁盘读写红扇区的数据，所以控制器需要操控读写头，先将其移回红色扇区所在的磁道，然后等待磁盘旋转，等到该扇区旋转到读写头的下方，然后读取红色扇区中的数据。

所以这里一共有三个因素，决定访问一个扇区需要的时长。

1. 寻道时间，等待移动磁头的时间 （3-9毫秒，且这个值改变不了，是一种基本的机械限制）
2. 旋转延迟，等待磁盘旋转的时间（平均情况就是磁盘旋转一整圈所花时间的一半，也有机械限制，限制你可以用多快的速度旋转他们）
3. 传送时间，该轨道在读写头下通过的时间

这三个元素加起来就是磁盘访问数据的平均时间，磁盘访问数据的时间主要是寻道时间。
tip：一个好的经验法则，用于估计从磁盘读取数据所需时间就是2*寻道时间。

现代磁盘控制器是将磁盘作为一系列逻辑块提供给CPU（如何做到的？），每个块是扇区的整数倍，所以在最简单的情况下，一个逻辑块就是一个扇区，快从零开始编号，块号是一系列增长的数字，然后磁盘控制器保存映射保持物理扇区和逻辑块之间的映射，所以这是一个间接层面，磁盘控制器将一些柱面保留为备用柱面，这些柱面没有被映射为逻辑块，如果有个柱面的一个扇区坏了，磁盘控制器可以将数据复制到备用柱面。然后磁盘就可以继续工作（这就是为什么格式容量比实际容量要小的原因）。

现在，像磁盘这样的设备连接到CPU和内存，通过另一种I/0桥连接（南桥）。
PCI总线是广播总线，这意味着它只是单一路线，因此，如果这根总线上的任何一个设备更改了某个值，该总线上的每个设备都可以看到这些值。（广播总线也是将事物连接在一起最简单的方式）

因此只需将此总线视为一组电子线路即可。每根电线都有一个比特信息。并且连接在总线的每个设备都可以看到所有电线上的值，有一些设备直接焊接在主板上，直接连接到总线上，磁盘是直接插入主板的插槽。还有诸如图形适配器和USB控制器，然后系统提供一个接口，因此你的鼠标和键盘灯插入USB控制器，然后还有扩展插槽，允许你添加其他设备，将其连接到总线上，如网络适配器。

ps:这是以前的PCI总线，现在的系统并不是这么简单。
现代系统使用成为PCI Express的总线结构，虽然它有PCI这个词，但它是完全不同的结构，它是点对点的，因此设备通过一组点对点连接进行连接，通过某种开关来管理，它是一种更有效的设计，更快且提供相同的功能，它允许你将所有设备连接到CPU。

CPU通过编写三元组来启动此读取行为（缺页），写了三个不同的值

1. 指令，比如read
2. 逻辑块号，写入一个想要访问的逻辑块号
3. 内存地址，想将逻辑块号内容放在内存中的哪个地址

磁盘控制器接收到CPU的三元组，取得总线控制权，读取与该逻辑块对应的任何扇区，然后通过南桥将数据复制到北桥，直接复制到主存储器，而无需通知CPU，然后数据一旦传输到主存，就会使用中断来通知CPU（CPU芯片的一个引脚）它将该引脚从0更改为1，通知CPU该扇区已经被复制，对CPU来说，现在某处有某个程序在等待，将数据读入内存，所以现在CPU可以指向该程序并处理该内存。
**这个机制做的事情就是CPU将此请求发送给磁盘控制器，然后。虽然那个非常缓慢的磁盘读取过程在进行CPU可以同时执行其他指令，执行其他有用的工作，所以这对于获得合理的性能非常重要。**防止由于磁盘系统减慢了整个系统的速度。

访问不同存储的重要信息（速度）

1. 访问SRAM取得一个double的双字，时间大约4纳秒‘
2. DRAM大约60ns，所以DRAM比SRAM慢一个数量级
3. 磁盘比SRAM慢4W倍，比DRAM慢250倍，所以磁盘和其他内存类型之间存在巨大的差距

tip：之前CPU频率与内存频率一样，为了使他们的处理器更快他们只会使时钟频率加倍，现在这一切都在2003年结束。这是计算机历史上有趣的一年，因为有一种不幸的特性，就CPU消耗的电能与时钟频率成正比（已经到达能源瓶颈了）。所以现在他们在芯片上放置更多的处理器内核，每个核心都执行自己的指令，然后并行运行。

3 程序的局部性

所以我想说的是DRAM、SSD、磁盘和CPU之间存在着访问时间的巨大差距，而且在某些情况下。随着时间的推移y它甚至会变得越来越糟,因此这是一个问题，我们的程序都需要数据，我们的数据存储在内存和磁盘中，所以如果你的计算机变得越来越快，我们的存储设备的访问速度却保持相对不变，甚至变得相对较慢，然后我们就遇到了一个问题就是我们的计算机性确实际上不会增加（程序运行不会变的更快）。这也是我们必须解决的问题，所以就需要弥合CPU和内存之间的差距–关键：程序的基本属性——程序的局部性

程序倾向于使用其地址接近或等于最近使用过的数据和指令的那些数据和地址——程序局部性
如果程序访问是一个数据项,那么它将在不久的将来的某个时间访问该数据项或附近的数据项的可能性非常高。

局部性有两种不同的形式：

时间局部性

时间局部性是最近引用的存储器位置可能在不久的将来再次被引用的属性
你有可能再次阅读该变量
例如。你读取了一个变量，你可能再次访问该变量。
例如。假设你在循环内。不断累加结果到一个变量，循环中每一次迭代都会访问这个变量

空间局部性

空间局部性是指引用临近存储器位置的倾向，如果我们访问了一个存储器位置,那么有很高的可能性我们在将来会访问一个临近位置

ps：数组里的元素是连续的，循环每一次迭代i++,然后读取a[i]，a[i]是空间局部性，因为我们正在访问附件的存储器地址。而对于循环内部，不断引用sum这个变量（寄存器都是%rax），就体现了程序的时间局部性。
那现在来考虑一下指令，循环中的每一次迭代。我们引用的都是一系列(相同的)指令，这体现了空间局部性
，但是我们反复地执行这个循环，因此。在每次循环迭代,我们很有可能将访问那些指令，随着程序进行。我们只是执行相同的指令，执行的是相同的,实现此循环体的汇编语言指令，即是时间局部性

ps：作为一个专业的程序员，这是一项必不可少的技能，你观看代码时，就需要获得对其局部性的定性认识，因为好的程序局部性能带来良好的性能，你需要做的是避免代码出现差的局部性

如下图，如果你以使其具有较差的局部性方式编写此代码，则它将以慢一个数量级的速度运行。

1. 首先，分析数组a在内存中的布局，行优先顺序存储。
2. a[i][j]保持j的不变，最快的速度改变着i，即我们每一次访问下一个元素步长都需要N，不满足步长为1的引用模式，每次都需要主存与缓存之间数据交换，所以其是一个槽糕的空间局部性。

ps：我们希望右边的索引是变化

4 内存分层

我们已经研究了了一些存储技术的技术属性，我们的存储设备和CPU之间存在着访问速度的差距，但好在程序具有局部性的这个原理，即程序的局部性原理与存储技术相互补充的非常完美，为人们提供了一种设计怎样存储系统的建议和信息，这种设计被称为存储器层次结构

你将内存系统分层设计，而不是单一的平层，在这个层次结构的顶部，你拥有存储容量较小，访问速度更快，但也更昂贵的存储设备，在每一个CPU周期内，寄存器每执行一条指令，都可以被CPU访问，但由于其造价及其昂贵，我们在顶层只有16个寄存器，接下来是一个或多个SRAM，SRAM是更快的一种内存，存在于CPU芯片内，它们虽然容量比寄存器大得多，但它们也只是MB这么大，接下来是主存，可以有几个GB，再下来一层就是磁盘，我们甚至可以把像网络服务器这样的东西认为是存储器层次结构的一部分，但比磁盘更低一层，关键点是在存储层次结构中，存储层次结构中的每一层都包含从下一层较低级别层次所检索的数据，CPU寄存器保存着从L1高速缓存中取出的数据，L1高速缓存保存从L2高速缓存中检索的数据，L3高速缓存从主存中取出的数据，主存又保存着从磁盘取得的数据，依次类推，内存设计如此的原因，就是当你拥有这种系统时，一般来说，在层次结构的顶部，你可以以最快的方式来访问内存，但是在层次结构较低层，访问速度较慢，但利用缓存技术，以一个更小的更快的存储设备，充当更慢的设备中数据的暂存区域，所以就像这里一样，你可以把你的主存认为是存储在磁盘上数据的缓存，你从磁盘读取数据，然后将其存储在主存中，一旦从磁盘获取数据，就不会再在磁盘上访问它，而是在内存中访问它，速度要快的多（这种想法一直在层次结构中转播），举个例子，将你的背包比喻为缓存，当你早上来上学的时候，比如你的公寓离学校有点远，你要带一些东西，你可以把他们放在你的背包里，你背着背包来上学，然后你需要用到那些东西，你就从背包中拿出来，如果你不利用背包，每次你需要用到某样东西，你都必须走回家拿，然后再带回学校，这就是缓存的概念，事实证明其非常强大，并且出现在计算机系统的所有部分中，对于存储器层次结构中分每一层，我们现在假设为第k层，第k以上的层都是缓存，体系的层次从L0开始到最高，所以最小的数字实际上是最高的级别，层次结构每进一步，我们提高级别，在层次结构中不断深入，现在他们为什么这么做？因为程序的局部性原理，程序倾向于访问存储在第K层的数据，比访问第K+1层更常见，而如果我们访问第K+1层的单元，我们会将其拷贝到第k层，因为我们很有可能再次访问它，然后我们以第k层的设备访问速度，多次访问第k层的数据，而不是第k+1层的速度，这就是这个层次结构的有趣之处。而且因为我们不经常访问第k+1层的数据，使得我们可以负担得起使用更便宜的，速度较慢的存储设备，在这方面，因此我们可以使他们的容量更大，存储每比特的价格更便宜，而层次结构就创造了一个大型的存储池，即抽象的大数组，其存储容量大小大约等于最底层存储设备的大小，却可以以最高层存储设备的速度来访问。

缓存的一般工作方式

缓存是一种非常通用的概念，可以应用于存储器层次结构中的所有层，且在各自缓存中都有某种传输单元，在层次之间来回拷贝，如图，假设有一个可以容纳四个快的缓存，而CPU需要的数据又在底层的内存，且这些内存被划分为一些固定大小的块，这就是接近存储器层次结构上层存储的工作方式。

若处于较低级别，就像你从Web服务器访问数据一样，在这个例子中，通过将数据划分为文件，但它的上层数据被划分为快，现在假设为主存，在主存之上还有一堆高速缓存，所以我们只要将内存分成一个个的快，每个快的字节数相同，然后，数据将以快大小为传输单位在内存和高速缓存之间传输，如果你需要来自内存中的数据，如果告诉缓存需要来自于主存的数据，那么它将获取整个块，然后在任何时间点，高速缓存都保存主存储器中的一个子集。当CPU要求第4块中包含的数据时，CPIU会去查看这个数据是否存在于高速缓存中，若在缓存中找到，则直接使用，若没找到，缓存则要求主存给它第4块数据，这样这个块就从内存拷贝到了缓存中，覆盖原来缓存中的数据（调度算法），而现在将4这块拷贝到缓存中的想法是希望在CPU上执行的程序能多的重用我们拷贝到高速缓存中的一个块，因为从内存拷贝到缓存，这相对于在缓存中处理还是很慢。

缓存命中

缓存命中：当CPU需要的某个块数据刚好在缓存中，因此可以直接返回，我们成之为缓存命中,CPU能迅速的获得这个块。而与缓存命中刚好相反的是缓存不命中（cache miss），就是在缓存中查找没找到，则需要去主存，甚至硬盘中中取数据，所以CPU需要更长的时间等待高速缓存从内核中取出该块，所以一旦出现缓存不命中，访问速度就会很慢。
我们通常区分几种不同的缓存不命中的种类：
1.冷不命中（cold miss）这是因为高速缓存中没有任何数据（最初缓存是空的，没有数据块），当我们要读取数据时，就要从下一层获取快，将它们放入缓存中，缓存将慢慢填满，也就增加了缓存命中的可能性。即无法避免冷不命中，将数据加载到空的缓存，这被称为缓存的暖身。
2.容量不命中
容量不命中的原因是高速缓存的大小是有限的，你不能容纳超过缓存大小的工作集，在我们看到的例子中，我们高速缓存只有四个快大小，如果我们的程序局部性需要用到8个快的数据。假设我们正在访问循环数组中的元素，这个数组包含了8个快的数据，那么自然容量仅有4个块的高速缓存无法放下整个8个块的数组。因此我们可以只要有足够大的缓存，就能很好的利用该程序中的空间和时间局部性。我们一般将程序运行时不断被程序访问的快称为工作集，工作集是会改变的，当你的程序从一个循环执行到另一个循环，从一个函数到另一个函数时，这些都是工作集。
3.冲突不命中，这与缓存的实现方式有关，因为大多数缓存，特别是硬件缓存，其设计较为简单，所以会限制了块的存储位置。块只能被放在缓存中的一个小组位置，如块号为i的快只能放在(i mod 缓存大小处)，所以假设我们有一个缓存，只能容纳四个块，当我们从主存中取出0块存放在我们的缓存的块0处，而下次找4,8都会被放在cache中的第0块，而即使我们有足够大的缓存，而我们下一层块号肯定远大于缓存，使得每一次拷贝新的块到cache都会导致驱逐另一个块，缓存就会一直不命中。

可以将寄存器看成是一种缓存，但其最大只能缓存8个字节的字。而其缓存在CPU核心上没有延迟。发送在一条指令的执行周期内，（必须有东西来管理缓存）当有请求从层次结构中较低层读取数据时，必须有一个过程决定如何处理这个请求，如何将其放入在缓存的某一个位置，我们称之为缓存管理（有一个索引表在管理者身上）。寄存器是由编译器管理缓存。当你编译C语言代码时，编译器会确定由哪个寄存器来存储来自内存的数据项（根据参数，返回值等）（rdi rdx rax）
TLB（后备缓冲）是一种在虚拟内存中使用的缓存.
L1和L2能存储64字节块，他们被缓存于CPU芯片上，由SRAM制成，集成在CPU上，两者都是由硬件来管理。如果出现了未命中，就会从L2缓存中加载一个块，L1缓存中的硬件决定在哪里存放这个块，时间需要4个周期。都是由硬件管理下完成的
磁盘包含由OS维护的缓冲区缓存，这种情况下，缓存的是文件的一部分，他们被缓存在主存中，缓存到主存的延迟大约100个时钟周期左右，这些都是由OS管理的，因此OS会保留一部分内存来加载你已加载的文件（索引），当读取文件时，它实际上将从主存中的文件缓存中读取，而不是去磁盘上读取。网络也维护着一份本地硬盘的缓存，例如网络文件系统，浏览器会把这些文件存储在本地硬盘上，以便再次引用这些网页，然后这些文件就会从你的本地磁盘读取，而不是一直通过网络重新请求。

5 总结

1.CPU和存储器设备之间存在访问速度的巨大差异，而且其还在不断扩大。
2.编写良好程序具有的局部性属性。
3.缓存的概念。
4.利用缓存的概念和程序的局部性原理，我们可以构建存储器层次结构，以便我们以最快的设备速率访问数据，但却有着底层容量大，造价低廉的优点。