3 内存管理
3.1 背景
CPU所能直接访问的存储器只有内存和处理器内部的寄存器。CPU只能从内存和处理器内的寄存器中读取指令或数据，如果数据不在内存或缓存中，那么CPU必须先通过指令将数据从外存中转移到内存中。
首先确保每个进程都有独立的内存空间。需要确定进程可以访问的合法地址的范围，并确保进程只访问其合法地址。
基地址寄存器
界限地址寄存器
使用基地址寄存器保存用户进程合法的最小物理地址，使用界限地址寄存器保存用户进程的地址的范围大小

3.2 地址绑定
输入队列：进程在执行时可以在磁盘和内存之间移动。在磁盘上等待调入内存以便执行的进程形成输入队列（input queue）。

在进程装入内存时，指令和数据应该装入内存的哪一块地址，应该如何分配，也就是地址绑定（Address binding）的方式。
地址绑定通常在以下几个阶段发生：
编译时(compile time)，如果编译时知道进程将要驻留在内存中的绝对地址，那么就可以生成绝对代码（absolute code），但这种方式一旦开始地址发生变化，就需要重新编译。
加载时(load time)，如果编译时不清楚绝对地址，那么编译器就必须生成可重定位代码(relocatable code)，这样地址绑定就会延迟到加载时进行，这样开始地址如果变化，只需要在加载时引入改变值即可
执行时(execution time)，如果一个进程在执行时可以从一个内存段移动到另一个内存段，那么绑定就必须发生在执行时。执行时完成地址绑定是绝大多数通用计算机系统采用的方法。

逻辑地址(logical address)：CPU生成的地址称为逻辑地址
物理地址(physical address)：加载到内存地址寄存器中的地址称为物理地址。
逻辑地址空间(logical address space)：由程序生成的所有逻辑地址的集合。
物理地址空间(physical address space)：由这些逻辑地址所有相对应的物理地址的集合。

内存管理单元：当虚拟地址和物理地址不同时，需要通过一个映射关系来完成两者的转换，完成这个操作的设备称为内存管理单元(memory-management unit，MMU)。

3.3 内存分配
3.3.1 连续内存分配
外部碎片
内部碎片

3.3.2 分页
分页是另一种内存管理方案，它允许进程的物理地址空间是非连续的。
• 物理内存分为固定大小的块，称为帧(frame)
• 将逻辑内存也分为同样大小的块，称为页(page)
执行进程时，进程以页面为单位加载到可用的帧中(可以不连续)，CPU在生成地址时，生成相应的页号§和页偏移(d)。每个进程都拥有了一个页表，页号是页表的索引，页表能够通过索引找到每页所在的物理内存的基地址，而基地址与页偏移的组合代表了真正的物理地址。

TLB：
页表一般都很大，并且存放在内存中，所以处理器引入MMU后，读取指令、数据需要访问两次内存：首先通过查询页表得到物理地址，然后访问该物理地址读取指令、数据。为了减少因为MMU导致的处理器性能下降，引入了TLB，TLB是Translation Lookaside Buffer的简称，可翻译为“地址转换后援缓冲器”，也可简称为“快表”。简单地说，TLB就是页表的Cache，其中存储了当前最可能被访问到的页表项，其内容是部分页表项的一个副本。只有在TLB无法完成地址翻译任务时，才会到内存中查询页表，这样就减少了页表查询导致的处理器性能下降。
TLB中的项由两部分组成：标识和数据。标识中存放的是虚地址的一部分，而数据部分中存放物理页号、存储保护信息以及其他一些辅助信息。虚地址与TLB中项的映射方式有三种：全关联方式、直接映射方式、分组关联方式。

3.3.3 分段
分段是支持用户视角的内存管理方案。
2.6版的Linux只有在80x86结构下才需要使用分段。
四个主要的Linux段的段描述符：
用户代码段
用户数据段
内核代码段
内核数据段

3.4 虚拟内存
3.4.1 背景
内存管理算法都是基于一个基本要求：执行指令必须在物理内存中，满足这一要求的第一种方法是整个进程放在内存中。动态载入能帮助减轻这一限制，但是它需要程序员特别小心地做一些额外的工作。
指令必须都在物理内存内的这一限制，似乎是必须和合理的，但也是不幸的，因为这使得程序的大小被限制在物理内存的大小内。事实上，研究实际程序会发现，许多情况下并不需要将整个程序放到内存中。即使在需要完整程序的时候，也并不是同时需要所有的程序。
因此运行一个部分在内存中的程序不仅有利于系统，还有利于用户。
虚拟内存（virtual memory）将用户逻辑内存和物理内存分开。这在现有物理内存有限的情况下，为程序员提供了巨大的虚拟内存。

3.5 为什么要引入虚拟内存
在进入正题前先来谈谈操作系统内存管理机制的发展历程，了解这些有利于我们更好的理解目前操作系统的内存管理机制。
3.5.1 早期的内存分配机制
在早期的计算机中，要运行一个程序，会把这些程序全都装入内存，程序都是直接运行在内存上的，也就是说程序中访问的内存地址都是实际的物理内存地址。当计算机同时运行多个程序时，必须保证这些程序用到的内存总量要小于计算机实际物理内存的大小。那当程序同时运行多个程序时，操作系统是如何为这些程序分配内存的呢？下面通过实例来说明当时的内存分配方法：
某台计算机总的内存大小是128M，现在同时运行两个程序A和B，A需占用内存10M，B需占用内存110。计算机在给程序分配内存时会采取这样的方法：先将内存中的前10M分配给程序A，接着再从内存中剩余的118M中划分出110M分配给程序B。这种分配方法可以保证程序A和程序B都能运行，但是这种简单的内存分配策略问题很多。
图一 早期的内存分配方法

问题1：进程地址空间不隔离。由于程序都是直接访问物理内存，所以恶意程序可以随意修改别的进程的内存数据，以达到破坏的目的。有些非恶意的，但是有bug的程序也可能不小心修改了其它程序的内存数据，就会导致其它程序的运行出现异常。这种情况对用户来说是无法容忍的，因为用户希望使用计算机的时候，其中一个任务失败了，至少不能影响其它的任务。
　　问题2：内存使用效率低。在A和B都运行的情况下，如果用户又运行了程序C，而程序C需要20M大小的内存才能运行，而此时系统只剩下8M的空间可供使用，所以此时系统必须在已运行的程序中选择一个将该程序的数据暂时拷贝到硬盘上，释放出部分空间来供程序C使用，然后再将程序C的数据全部装入内存中运行。可以想象得到，在这个过程中，有大量的数据在装入装出，导致效率十分低下。
　　问题3：程序运行的地址不确定。当内存中的剩余空间可以满足程序C的要求后，操作系统会在剩余空间中随机分配一段连续的20M大小的空间给程序C使用，因为是随机分配的，所以程序运行的地址是不确定的。
3.5.2 分段
　　为了解决上述问题，人们想到了一种变通的方法，就是增加一个中间层，利用一种间接的地址访问方法访问物理内存。按照这种方法，程序中访问的内存地址不再是实际的物理内存地址，而是一个虚拟地址，然后由操作系统将这个虚拟地址映射到适当的物理内存地址上。这样，只要操作系统处理好虚拟地址到物理内存地址的映射，就可以保证不同的程序最终访问的内存地址位于不同的区域，彼此没有重叠，就可以达到内存地址空间隔离的效果。
当创建一个进程时，操作系统会为该进程分配一个4GB大小的虚拟进程地址空间。之所以是4GB，是因为在32位的操作系统中，一个指针长度是4字节，而4字节指针的寻址能力是从0x00000000_{0xFFFFFFFF，最大值0xFFFFFFFF表示的即为4GB大小的容量。与虚拟地址空间相对的，还有一个物理地址空间，这个地址空间对应的是真实的物理内存。如果你的计算机上安装了512M大小的内存，那么这个物理地址空间表示的范围是0x00000000}0x1FFFFFFF。当操作系统做虚拟地址到物理地址映射时，只能映射到这一范围，操作系统也只会映射到这一范围。当进程创建时，每个进程都会有一个自己的4GB虚拟地址空间。要注意的是这个4GB的地址空间是“虚拟”的，并不是真实存在的，而且每个进程只能访问自己虚拟地址空间中的数据，无法访问别的进程中的数据，通过这种方法实现了进程间的地址隔离。那是不是这4GB的虚拟地址空间应用程序可以随意使用呢？很遗憾，在Windows系统下，这个虚拟地址空间被分成了4部分：NULL指针区、用户区、64KB禁入区、内核区。应用程序能使用的只是用户区而已，大约2GB左右(最大可以调整到3GB)。内核区为2GB，内核区保存的是系统线程调度、内存管理、设备驱动等数据，这部分数据供所有的进程共享，但应用程序是不能直接访问的。
人们之所以要创建一个虚拟地址空间，目的是为了解决进程地址空间隔离的问题。但程序要想执行，必须运行在真实的内存上，所以，必须在虚拟地址与物理地址间建立一种映射关系。这样，通过映射机制，当程序访问虚拟地址空间上的某个地址值时，就相当于访问了物理地址空间中的另一个值。人们想到了一种分段(Sagmentation)的方法，它的思想是在虚拟地址空间和物理地址空间之间做一一映射。比如说虚拟地址空间中某个10M大小的空间映射到物理地址空间中某个10M大小的空间。这种思想理解起来并不难，操作系统保证不同进程的地址空间被映射到物理地址空间中不同的区域上，这样每个进程最终访问到的
物理地址空间都是彼此分开的。通过这种方式，就实现了进程间的地址隔离。还是以实例说明，假设有两个进程A和B，进程A所需内存大小为10M，其虚拟地址空间分布在0x00000000到0x00A00000，进程B所需内存为100M，其虚拟地址空间分布为0x00000000到0x06400000。那么按照分段的映射方法，进程A在物理内存上映射区域为0x00100000到0x00B00000，，进程B在物理内存上映射区域为0x00C00000到0x07000000。于是进程A和进程B分别被映射到了不同的内存区间，彼此互不重叠，实现了地址隔离。从应用程序的角度看来，进程A的地址空间就是分布在0x00000000到0x00A00000，在做开发时，开发人员只需访问这段区间上的地址即可。应用程序并不关心进程A究竟被映射到物理内存的那块区域上了，所以程序的运行地址也就是相当于说是确定的了。 图二显示的是分段方式的内存映射方法。
图二 分段方式的内存映射方法

这种分段的映射方法虽然解决了上述中的问题一和问题三，但并没能解决问题二，即内存的使用效率问题。在分段的映射方法中，每次换入换出内存的都是整个程序，这样会造成大量的磁盘访问操作，导致效率低下。所以这种映射方法还是稍显粗糙，粒度比较大。实际上，程序的运行有局部性特点，在某个时间段内，程序只是访问程序的一小部分数据，也就是说，程序的大部分数据在一个时间段内都不会被用到。基于这种情况，人们想到了粒度更小的内存分割和映射方法，这种方法就是分页(Paging)。
3.5.3 分页
分页的基本方法是，将地址空间分成许多的页。每页的大小由CPU决定，然后由操作系统选择页的大小。目前Inter系列的CPU支持4KB或4MB的页大小，而PC上目前都选择使用4KB。按这种选择，4GB虚拟地址空间共可以分成1048576个页，512M的物理内存可以分为131072个页。显然虚拟空间的页数要比物理空间的页数多得多。
在分段的方法中，每次程序运行时总是把程序全部装入内存，而分页的方法则有所不同。分页的思想是程序运行时用到哪页就为哪页分配内存，没用到的页暂时保留在硬盘上。当用到这些页时再在物理地址空间中为这些页分配内存，然后建立虚拟地址空间中的页和刚分配的物理内存页间的映射。
下面通过介绍一个可执行文件的装载过程来说明分页机制的实现方法。一个可执行文件(PE文件)其实就是一些编译链接好的数据和指令的集合，它也会被分成很多页，在PE文件执行的过程中，它往内存中装载的单位就是页。当一个PE文件被执行时，操作系统会先为该程序创建一个4GB的进程虚拟地址空间。前面介绍过，虚拟地址空间只是一个中间层而已，它的功能是利用一种映射机制将虚拟地址空间映射到物理地址空间，所以，创建4GB虚拟地址空间其实并不是要真的创建空间，只是要创建那种映射机制所需要的数据结构而已，这种数据结构就是页目和页表。
当创建完虚拟地址空间所需要的数据结构后，进程开始读取PE文件的第一页。在PE文件的第一页包含了PE文件头和段表等信息，进程根据文件头和段表等信息，将PE文件中所有的段一一映射到虚拟地址空间中相应的页(PE文件中的段的长度都是页长的整数倍)。这时PE文件的真正指令和数据还没有被装入内存中，操作系统只是根据PE文件的头部等信息建立了PE文件和进程虚拟地址空间中页的映射关系而已。当CPU要访问程序中用到的某个虚拟地址时，当CPU发现该地址并没有相相关联的物理地址时，CPU认为该虚拟地址所在的页面是个空页面，CPU会认为这是个页错误(Page Fault)，CPU也就知道了操作系统还未给该PE页面分配内存，CPU会将控制权交还给操作系统。操作系统于是为该PE页面在物理空间中分配一个页面，然后再将这个物理页面与虚拟空间中的虚拟页面映射起来，然后将控制权再还给进程，进程从刚才发生页错误的位置重新开始执行。由于此时已为PE文件的那个页面分配了内存，所以就不会发生页错误了。随着程序的执行，页错误会不断地产生，操作系统也会为进程分配相应的物理页面来满足进程执行的需求。
分页方法的核心思想就是当可执行文件执行到第x页时，就为第x页分配一个内存页y，然后再将这个内存页添加到进程虚拟地址空间的映射表中,这个映射表就相当于一个y=f(x)函数。应用程序通过这个映射表就可以访问到x页关联的y页了。

3.6 分段分页历史背景
1971 年 11 月 15 日，Intel 推出世界第一块个人微型处理器 4004（4位处理器）。
随后又推出了 8080（8 位处理器）。
那时候访问内存就只有直白自然的想法，用具体物理地址。
所有的内存访问就是通过绝对物理地址去访问的，那时候还没有段的概念。
段的概念是起源于 8086，这个 16 位处理器。
限于当时的技术背景和经济，寄存器只有 16 位，而地址总线是 20 位。
那 16 的位的寄存器如何能访问 20 位的地址？
2 的16 次方如果直着来如何能访问到 2 的 20 次方所表达的数？
直着来是不可能的，因此就需要操作一下。
也就是引入段的概念，让 CPU 通过「段基地址+段内偏移」来访问内存。
有人可能就问你这都只有 16 位，两个 16 位加起来最多只能表示 17 位呀。
你说的没错。
所以再具体一点的计算规则其实是：段基地址左移 4 位（就是乘16）再加上段内偏移，这样得到的就是 20 位的地址。
比如现在的要访问的内存地址是0x05808，那么段基地址可以是 0x0580，偏移量就是 0x0008。

这样内存的寻址空间就扩大到 20 位了。
至于为什么称之为段，其实就是因为寄存器只有 16 位一段只能访问 64 KB，所以需要移动基地址，一段一段的去访问所有的内存空间。
对了，专门为分段而生的寄存器为段寄存器，当时里面直接存放段基地址。
不过渐渐地人们就考虑到安全问题，因为在这个时候程序之间的地址没有隔离，我的程序可以访问你的程序地址，这就很不安全。
于是在 1982 年 80286 推出时，就有了保护模式。
其实就是 CPU 在访问地址的时候做了约束，会判断地址是否在允许的范围内，会判断当前的程序对目的地址是否有访问权限。
搞了个 GDT （全局描述符表）存放所有段描述符。

段寄存器里面也不是直接放段基地址了，而是放了一个叫选择子的东西。
大致可以认为就是段描述符的索引，也就是通过这个索引去找到段描述符，所以叫选择子。
这个选择子里面还有一点属性。

这个 T1 就是标明要去哪个表找，而 RPL 就是特权级了，一共分为四层，0 为最高特权级，3 为最低特权级。
当地址访问时，如果 RPL 的权限低于目标特权级（DPL）时，就会拒绝访问，于是就起到了保护的作用。
所以称之为保护模式，之前的那种没有判断权限的称之为实模式。

当时 80286 的地址总线已经是 24 位，但是用于寻址的通用寄存器还是 16 位，虽然段基地址的位数已经足够访问到 24 位（因为已经放到 GDT 中，且有 24位）。
但是因每次一段只有 64 KB，这样访问就很不方便，需要不断的更换段基地址，于是 80286 很快就被淘汰，换上了 80386。
这是 Intel 第一代 32 位处理器。
除了段寄存器还是 16 位之外，地址总线和寄存器都是 32 位，这就意味着以前为了寻址搞的段机制其实没用了。
因为单单段内偏移就可以访问到 4GB 空间，但是为了向前兼容段机制还是保留了下来，段寄存器还是 16 位是因为够用了，所以没必要扩充。
不过上有政策，下有对策。
虽说段机制保留了，但是咱可以“忽悠”着用，把段基值都设置为 0 ，就用段内偏移地址来访问内存空间就好了。
这其实就意味着每个段的起始地址都是一样的，那就等于不分段了，这就叫平坦模式。
Linux 就是这样实现的。
3.6.1 那为什么要分页？
因为分段粒度太粗了，导致内存碎片大，不利于管理。
当时加载到内存等于一个段都得搞到内存中，而段的范围过大，举个例子。
假设此时你有 200M 内存，此时有 3 个应用在运行，分别是 LOL、chrome、微信。

此时内存中明明有 30MB 的空闲，但是网易云加载不进来，这内存碎片就有点大了。
然后就得把 chrome 先换到磁盘中，然后再让 chrome 加载进来到微信的后面，这样空闲的 30MB 就连续了，于是网易云就能加载到内存中了。
但是这样等于要把 50MB 的内存来个反复横跳，磁盘的访问太慢了，所以效率就很低。
总体而言可以认为分段内存的管理粒度太粗了，所以随着 80386 就出来了个分页管理，一个更加精细化的内存管理方式。
简单地说就是把内存等分成一页一页，每页 4KB 大小，按页为单位来管理内存。
你看按一页一页来管理这样就不用把一段程序都加载进内存，只需要将用到的页加载进内存。
这样内存的利用率就更高了，能同时运行的程序就更多了。
并且由于一页就 4KB， 所以内存交换的性能问题得以缓解，毕竟只要换一定的页，而不需要整个段都换到磁盘中。
对应的还有个虚拟内存的概念。
分页机制构造了一个虚拟内存空间，让每个进程误以为自己掌控所有的内存。