一步步编写操作系统 35 内存为何要分页

一直以来我们都直接在内存分段机制下工作，目前未出问题看似良好，的确目前咱们的应用过于简单了，就一个loader在跑，能出什么问题呢。可是想像一下，当我们物理内存不足时会怎么办呢？比如系统里的应用程序过多、或者内存碎片过多无法容纳新的进程、或者曾经被换出到硬盘中的内存段需要再次重新装到内存，可是内存中找不到合适大小的内存区域怎么办？也许有人会说，这简单啊，停止想像呗…….嘿嘿，开玩笑而已，问题还是要解决的。

也许文字说得并不是很清楚，下面以图示说明这些情况

上图模拟了多个进程并行的情况。在第1步中，系统里有3个进程正在运行，进程A、B、C各占了10MB、20MB、30MB的内存空间，物理内存还是挺宽裕的，还剩下15MB可用。到了第2步就悲催了，此时进程B已经运行结束，腾出了20MB的内存，可是待加载运行的进程D需要20MB+3KB的内存空间，即20483KB。现在的运行环境是未开启分页功能，“段基址+段内偏移”产生的线性地址就是物理地址，程序中引用的线性地址是连续的，所以物理地址也连续。虽然总共剩下35MB内存可用，可问题是明摆着的，现在连续的内存块只有原来进程B的20MB和最下面可用内存15MB。哪一块都不够进程D用的，这怎么办呢？

两个解决方案：

• 等待进程C运行完后腾出内存，这样连续可用的内存就够运行进程D了
• 将进程A的段A3或进程C的段C1换出到硬盘上，腾出一部分空间，加上邻接的20MB，足够容纳进程D。

第一个方案比较简单直接，但就是要等待，而且咱们也不知道程序C啥时候执行完，等个没完没了，用户还以为死机了呢，说不定一气之下就给重启了，算啦，这个方法不好，看第二个吧。

第二个方案看上去先进很多，原理是将老进程不常用的段换出到硬盘，腾出空间给新进程用，等老进程再次需要该段时，再从硬盘上将该段载入内存。如图:

看上去方案完美无懈可击，虽然要用到低速的硬盘，但至少能干活。这就是当系统物理内存不足的情况下，硬盘灯会不停闪烁的原因。不过这一切是需要硬件的配合才能实现，咱们一会介绍下这种内存管理，不过在这之前先扯点别的。

我曾经一度搞不清楚操作系统和硬件的内在联系，比如，某种功能是操作系统自己实现的还是硬件直接支持的？甚至在更早些时候，由于知识掌握的不足，有些问题迷惑到不知该如何表达，后来才搞清楚，操作系统和硬件之间是相互依赖、相互推动、相互促进而发展起来的。比如，起初的操作系统无法对内存段做访问限制，有了这样的需求后，cpu厂商决定采用段描述符来实现相关功能，在硬件一级上添加了GDTR和LDTR寄存器来支持全局描述符表和局部描述符表，并由硬件负责周边的安全检测。当初cpu硬件厂商可不是凭空造出这样一个概念的，是与操作系统厂商共同协商后才有了一套硬件方面的支持。这不仅仅在计算机行业中是这样，其它行业也一样，比如机械制造行业，如果要生产一个精度较高的零件，而目前的车床无法加工，生产车床的厂商就要提高自身水平，制造出加工精度更高的车床，而不是让零件去适应车床而降低精度。另外一个最典型的例子就是人类的直立行走，最早的时候是用四肢行走，人在思想上想把双手腾出来做其它事，所以身体便给予了“硬件”支持，慢慢发展成了只用下肢行走，这是典型的软件督促硬件发展。

虽然操作系统和cpu相互促进，但说到底，操作系统是软件，软件中的指令是靠cpu来执行，如果计算机是有生命的，软件相当于思想、灵魂，而硬件才是真正的身体，思想指导身体的行为。

但并不是思想指导了所有的行为，就拿人类的运动来说，咱们的大脑产生了跑的意识后，左腿右腿就交替向前迈进。但跑起来之后，心脏会加速跳动，肺也加速了呼吸的频率，这并不是咱们主动控制的，这些器官的行为是由身体里的植物神经控制。也就是说，咱们在跑步时，虽然大脑思想上只负责跑步的动作，不用向身体发命令：心脏加速、呼吸加速等，但这些器官的行为确实存在着，而且是在生理一级上自动完成不受意识控制。

说这些就是想告诉大家，我们所写的代码仅仅是完成了某件事的一部分而已，也许是大部分，还有一部分是cpu硬件上负责的，这部分咱们不用管，由cpu自动完成。比如，调用一个函数时，cpu自动将返回地址压入栈；进入中断时，cpu除了压入返回地址、标志寄存器外，还要根据当前特权级决定是否压入当前栈段寄存器及指针……这样的例子太多了不再一一列举。

东扯西扯地说了这么多后，开始说下例子中内存管理的原理，内存段是怎样被换出的。

在保护模式下，段描述符是内存段的身份证。cpu在引用一个段时，都要先查看段描述符。很多时候，段描述符存在于描述符表中（GDT或LDT），但与此对应的段并不在内存中，也就是说，cpu允许在描述符表中已注册的段不在内存中存在，这就是它提供给软件使用的策略，我们利用它实现段式内存管理。如果该描述符中的P位为1，表示该段在内存中存在。访问过该段后，cpu将段描述符中的A位置1，表示近来刚访问过该段。相反，如果P位为0，说明内存中并不存在该段，这时候cpu将会抛出个NP（段不存在）异常，转而去执行中断描述符表中NP异常对应的中断处理程序，此中断处理程序是操作系统负责提供的，该程序的工作是将相应的段从外存（比如硬盘）中载入到内存，并将段描述符的P位置1，中断处理函数结束后返回，cpu重复执行这个检查，继续查看该段描述符的P位，此时已经为1了，在检查通过后，将段描述符的A位置1。

以上是cpu加载内存段的过程，内存段是何时移出到外存上的呢？

段描述符的A位是由cpu置1，但清0工作可是由操作系统来完成的。此位干吗用的呢？如果仅仅用来表示该段被访问过，这也意义不大啊。其实这正是软件和硬件相互配合的体现，操作系统每发现该位为1后就将该位清0，这样一来，在一个周期内统计该位为1的次数就知道该段的使用频率了，从而可以找出使用频率最低的段。当物理内存不足时，可以将使用频率最低的段换出到硬盘，以腾出内存空间给新的进程。当段被换出到硬盘后，操作系统将该段描述符的P位置0。当下次这个进程上cpu运行后，如果访问了这个段，这样程序流就回到了刚开始cpu检查出P位为0、紧接着抛出异常、执行操作系统中断处理程序、换入内存段的循环。

另外，内存中的数据是二进制的，段被换出到硬盘上也是以二进制形式存储，数据内容都是一样的，只是存储介质不同而已，不要因为陌生而觉得段的换入换出深不可测，这无非是一段二进制数据在内存和外存之间拷贝来拷贝去而已，其过程就像将一个txt文件读到内存中修改后再保存到硬盘一样。

第二个方法虽然解决了内存不足的问题，但也有缺陷。比如物理内存特别小，无法容纳任何一个进程的段，这就没法运行进程了，更没法做段的换入换出。也许有人会说，这是用户的问题，这么小的内存还拿出来用，这不是“逗比”吗。您还别说，一会介绍的内存分页机制，理论上只要4K内存就可以让程序运行下去。另外一种情况是，若进程的段比较大，换出时要将整个段全部搬到外存上，这种IO操作太多了机器响应奇慢无比，用户是无法接受的。还有没有更好的方法呢？

想一想，出现这种问题的原因是什么？问题的本质是，在目前只分段的情况下，cpu认为线性地址等于物理地址。而线性地址是由编译器编译出来的，它本身是连续的，所以物理地址也必须要连续才行，但我们可用的物理地址不连续。换句话说，如果线性地址连续，而物理地址可以不连续，不就解决了吗。

按照这种思路，我们首先要做的是解除线性地址与物理地址一一对应的关系，然后将它们的关系重新建立。通过某种映射关系，可以将线性地址映射到任意物理地址。

有很多实现映射的方法，比如可以写个哈希算法，将线性地址做key，而value是物理地址。不过，这都是软件实现的算法，时间复杂度再低，效率肯定不如硬件“短、平、快”，因为硬件中的操作更直接，并且已经在电路上做过优化，而软件的效率主要取决于代码的算法和编译器的优化能力，即使能产生出最优的机器码，也是被当做普通指令处理：先要到内存中取指、译码、再执行，不说别的，就光是取指这步就已经很慢了，毕竟内存在cpu眼里是低速设备。所以，对于地址转换这种实时性较高的需求，cpu已经给予了我们最大的硬件支持，在cpu实现中，这种映射关系是通过一张表来实现的，该表就是我们所说的页表，查找页表的工作也是由硬件完成的。这张表是什么样的呢？我们在下一节中给出答案