程序放在哪儿？

本博客参考操作系统实战 45 讲》

上一个博客介绍了如何在程序中转换地址，这个博客介绍程序放在哪里？

我们已经知道了 CPU 如何执行程序，也研究了程序的地址空间，在这里我们终于到了程序的存储位置-内存。

你知道什么是 Cache 是吗？在你心中，真正的内存是什么样子的？今天，让我们识它 Cache 和内存，这对我们有用 Cache 编写高性能的程序代码和管理操作系统的内存有很大的帮助。

通过本课程的内容，让我们来看看内存是什么，它的特点是什么。有了这种理解，你可以对我们看似熟悉的东西有更深的理解局部性原理，找出为什么 Cache 是解决内存瓶颈的神来之笔。最后，我会带你去分析 x86 平台上的 Cache，规避 Cache 一致性问题，让你掌握获取内存视图的方法。

不知道，你还记得吗？ C 用语言打印99乘法表的代码并不重要。让我把它贴出来。代码很短，很简单。即使你自己写一个，也不需要一分钟，如下所示。

#include <stdio.h> int main(){ 
           int i,j;   for(i=1; i<=9; i ){ 
             for(j=1; j<=i; j ){ 
               printf("%d*%d=- ", i, j, i*j);     }     printf("\n");   }   return 0; } 

当然，我们不研究代码本身。这个代码很简单。在这里，我们主要观察这个结构。代码的结构主要是顺序、分支、循环，这三种结构可以写所有现存算法的程序。

我们通常写的代码大多是顺序和循环结构。上述代码有两个循环，内部循环的次数受外部循环变量的影响。就是这么简单，但是东西越简单，就越容易看到本质。

可以看出，这个代码大部分时间都在执行计算和调用乘法 printf 函数，一旦程序被编译并装载到内存中，它的地址就会确定。也就是说，CPU 大部分时间访问相同或相邻的地址，换句话说：CPU 大部分时间都在执行相同的指令或相邻的指令。这就是为什么 是名鼎鼎局部程序原理。

在理解了程序的局部原理后，让我们来看看内存。你可能会觉得这个跨度有点大，但只有理解了内存的结构和特性，你才能理解程序局部原理的应用场景及其重要性。

内存也可以称为主存储器。无论硬盘有多大，存储了多少程序和数据，只要程序运行或数据需要计算，它们都必须首先包含在内存中。让我们看看内存是什么样子的（你也可以在网上搜索），如下图所示。

尽管 CPU 和内存是同时代发展的，但 CPU 所使用技术工艺的材料和内存是不同的，侧重点也不同，价格也不同。如果内存使用 CPU 的工艺和材料制造，那内存条的昂贵程度会超乎想象，没有多少人能买得起。

由于这些不同，导致了 CPU 和内存条的数据吞吐量天差地别。尽管最新的 DDR4 内存条带宽高达 34GB/s，然而这相比 CPU 的数据吞吐量要慢上几个数量级。再加上多核心 CPU同时访问内存，会导致总线争用问题，数据吞吐量会进一步下降。

CPU 要数据，内存一时给不了怎么办？CPU 就得等，通常 CPU 会让总线插入等待时钟周期，直到内存准备好，到这里你就会发现，无论 CPU 的性能多高都没用，而内存才是决定系统整体性能的关键。显然依靠目前的理论直接提升内存性能，达到 CPU 的同等水平，这是不可行的，得想其它的办法。

让我们重新回到前面的场景中，回到程序的局部性原理，它告诉我们：CPU 大多数时间在访问相同或者与此相邻的地址。那么，我们立马就可以想到用一块小而快的储存器，放在CPU 和内存之间，就可以利用程序的局部性原理来缓解 CPU 和内存之间的性能瓶颈。这块小而快的储存器就是 Cache，即高速缓存。

Cache 中存放了内存中的一部分数据，CPU 在访问内存时要先访问 Cache，若 Cache 中有需要的数据就直接从 Cache 中取出，若没有则需要从内存中读取数据，并同时把这块数据放入 Cache 中。但是由于程序的局部性原理，在一段时间内，CPU 总是能从 Cache 中 读取到自己想要的数据。

Cache 可以集成在 CPU 内部，也可以做成独立的芯片放在总线上，现在 x86 CPU 和ARM CPU 都是集成在 CPU 内部的。其逻辑结构如下图所示。

Cache 主要由高速的静态储存器、地址转换模块和 Cache 行替换模块组成。

Cache 会把自己的高速静态储存器和内存分成大小相同的行，一行大小通常为 32 字节或者 64 字节。Cache 和内存交换数据的最小单位是一行，为方便管理，在 Cache 内部的高速储存器中，多个行又会形成一组。

除了正常的数据空间外，Cache 行中还有一些标志位，如脏位、回写位，访问位等，这些位会被 Cache 的替换模块所使用。

Cache 大致的逻辑工作流程如下。

1. CPU 发出的地址由 Cache 的地址转换模块分成 3 段：组号，行号，行内偏移。
2. Cache 会根据组号、行号查找高速静态储存器中对应的行。如果找到即命中，用行内偏移读取并返回数据给 CPU，否则就分配一个新行并访问内存，把内存中对应的数据加载到Cache 行并返回给 CPU。写入操作则比较直接，分为回写和直通写，回写是写入对应的Cache 行就结束了，直通写则是在写入 Cache 行的同时写入内存。
3. 如果没有新行了，就要进入行替换逻辑，即找出一个 Cache 行写回内存，腾出空间，替换行有相关的算法，替换算法是为了让替换的代价最小化。例如，找出一个没有修改的Cache 行，这样就不用把它其中的数据回写到内存中了，还有找出存在时间最久远的那个 Cache 行，因为它大概率不会再访问了。

以上这些逻辑都由 Cache 硬件独立实现，软件不用做任何工作，对软件是透明的。

Cache 虽然带来性能方面的提升，但同时也给和硬件和软件开发带来了问题，那就是数据一致性问题。

为了搞清楚这个问题，我们必须先搞清楚 Cache 在硬件层面的结构，下面我画了 x86 CPU的 Cache 结构图：

这是一颗最简单的双核心 CPU，它有三级 Cache，第一级 Cache 是指令和数据分开的，第二级 Cache 是独立于 CPU 核心的，第三级 Cache 是所有 CPU 核心共享的。

下面来看看 Cache 的一致性问题，主要包括这三个方面.

1. 一个 CPU 核心中的指令 Cache 和数据 Cache 的一致性问题。
2. 多个 CPU 核心各自的 2 级 Cache 的一致性问题。
3. CPU 的 3 级 Cache 与设备内存，如 DMA、网卡帧储存，显存之间的一致性问题。这里我们不需要关注这个问题。

我们先来看看 CPU 核心中的指令 Cache 和数据 Cache 的一致性问题，对于程序代码运行而言，指令都是经过指令 Cache，而指令中涉及到的数据则会经过数据 Cache。

所以，对自修改的代码（即修改运行中代码指令数据，变成新的程序）而言，比如我们修改了内存地址 A 这个位置的代码（典型的情况是 Java 运行时编译器），这个时候我们是通过储存的方式去写的地址 A，所以新的指令会进入数据 Cache。

但是我们接下来去执行地址 A 处的指令的时候，指令 Cache 里面可能命中的是修改之前的指令。所以，这个时候软件需要把数据 Cache 中的数据写入到内存中，然后让指令 Cache无效，重新加载内存中的数据。

再来看看多个 CPU 核心各自的 2 级 Cache 的一致性问题。从上图中可以发现，两个 CPU核心共享了一个 3 级 Cache。比如第一个 CPU 核心读取了一个 A 地址处的变量，第二个CPU 也读取 A 地址处的变量，那么第二个 CPU 核心是不是需要从内存里面经过第 3、2、1 级 Cache 再读一遍，这个显然是没有必要的。

在硬件上 Cache 相关的控制单元，可以把第一个 CPU 核心的 A 地址处 Cache 内容直接复制到第二个 CPU 的第 2、1 级 Cache，这样两个 CPU 核心都得到了 A 地址的数据。不过如果这时第一个 CPU 核心改写了 A 地址处的数据，而第二个 CPU 核心的 2 级 Cache 里面还是原来的值，数据显然就不一致了。

为了解决这些问题，硬件工程师们开发了多种协议，典型的多核心 Cache 数据同步协议有MESI 和 MOESI。MOESI 和 MESI 大同小异，下面我们就去研究一下 MESI 协议。

前面我们研究了大量的 Cache 底层细节和问题，就是为了使用 Cache，目前 Cache 已经成为了现代计算机的标配，但是 x86 CPU 上默认是关闭 Cache 的，需要在 CPU 初始化时将其开启。

在 x86 CPU 上开启 Cache 非常简单，只需要将 CR0 寄存器中 CD、NW 位同时清 0 即可。CD=1 时表示 Cache 关闭，NW=1 时 CPU 不维护内存数据一致性。所以 CD=0、NW=0 的组合才是开启 Cache 的正确方法。

开启 Cache 只需要用四行汇编代码，代码如下：

mov eax, cr0
;开启 CACHE
btr eax,29 ;CR0.NW=0
btr eax,30 ;CR0.CD=0
mov cr0, eax

作为系统软件开发人员，与其了解内存内部构造原理，不如了解系统内存有多大。这个作用更大。

根据前面课程所讲，给出一个物理地址并不能准确地定位到内存空间，内存空间只是映射物理地址空间中的一个子集，物理地址空间中可能有空洞，有 ROM，有内存，有显存，有I/O 寄存器，所以获取内存有多大没用，关键是要获取哪些物理地址空间是可以读写的内存。

物理地址空间是由北桥芯片控制管理的，那我们是不是要找北桥要内存的地址空间呢？当然不是，在 x86 平台上还有更方便简单的办法，那就是 BIOS 提供的实模式下中断服务，就是 int 指令后面跟着一个常数的形式。

由于 PC 机上电后由 BIOS 执行硬件初始化，中断向量表是 BIOS 设置的，所以执行中断自然执行 BIOS 服务。这个中断服务是 int 15h，但是它需要一些参数，就是在执行 int 15h之前，对特定寄存器设置一些值，代码如下。

_getmemmap:
	xor ebx,ebx ;ebx设为0
	mov edi,E80MAP_ADR ;edi设为存放输出结果的1MB内的物理内存地址
loop:
	mov eax,0e820h ;eax必须为0e820h
	mov ecx,20 ;输出结果数据项的大小为20字节：8字节内存基地址，8字节内存长度，4字节内存类型
	mov edx,0534d4150h ;edx必须为0534d4150h
	int 15h ;执行中断
	jc error ;如果flags寄存器的C位置1，则表示出错
	add edi,20;更新下一次输出结果的地址
	cmp ebx,0 ;如ebx为0，则表示循环迭代结束
	jne loop ;还有结果项，继续迭代
		ret
error:;出错处理

上面的代码是在迭代中执行中断，每次中断都输出一个 20 字节大小数据项，最后会形成一个该数据项（结构体）的数组，可以用 C 语言结构表示，如下。

#define RAM_USABLE 1 //可用内存
#define RAM_RESERV 2 //保留内存不可使用
#define RAM_ACPIREC 3 //ACPI表相关的
#define RAM_ACPINVS 4 //ACPI NVS空间
#define RAM_AREACON 5 //包含坏内存
typedef struct s_e820{ 
        
	u64_t saddr; /* 内存开始地址 */
	u64_t lsize; /* 内存大小 */
	u32_t type; /* 内存类型 */
}e820map_t;

今天我们主要讲了四部分内容，局部性原理、内存结构特性、Cache 工作原理和 x86 上的应用。我们一起来回顾一下这节课的重点。

首先从一个场景开始，我们了解了程序通常的结构。通过观察这种结构，我们发现 CPU 大多数时间在访问相同或者与此相邻的地址，执行相同的指令或者与此相邻的指令。这种现象就是程序局部性原理。

然后，我们研究了内存的结构和特性。了解它的工艺标准和内部原理，知道内存容量相对可以做得较大，程序和数据都要放在其中才能被 CPU 执行和处理。但是内存的速度却远远赶不上 CPU 的速度。

因为内存和 CPU 之间性能瓶颈和程序局部性原理，所以才开发出了 Cache（即高速缓存），它由高速静态储存器和相应的控制逻辑组成。

Cache 容量比内存小，速度却比内存高，它在 CPU 和内存之间，CPU 访问内存首先会访问 Cache，如果访问命中则会大大提升性能，然而它却带来了问题，那就是数据的一致性问题，为了解决这个问题，工程师又开发了 Cache一致性协议 MESI。这个协议由 Cache 硬件执行，对软件透明。

最后，我们掌握了 x86 平台上开启 Cache 和获取物理内存视图的方法。

因为这节课也是我们硬件模块的最后一节，可以说没有硬件平台知识，写操作系统就如同空中建楼，通过这个部分的学习，就算是为写操作系统打好了地基。为了让你更系统地认识这个模块，我给你整理了的知识导图。