操作系统的内存管理

这篇文章属于《恰同学少年》系列，写于2010年。

引言

内存管理，或者更广泛的存储管理，是计算机系统非常重要的一方面。实现有效的存储管理需求是一个处理器硬件和操作系统软件共同合作完成的复杂任务。本文主要从软件的角度，对操作系统的内存管理策略做一综述。

一个计算机系统，从顶层来看，可以分为四个结构化的部件：处理器（processor）、内存（main memory）、输入输出模块（I/O module）、系统总线（system bus）。其中，内存用来存储运行时的程序和数据。事实上，计算机的存储系统分布于不同的层次。除内存以外，还有：存在于处理器内部的少量在执行具体指令时使用的寄存器组（速度最快，容量也最小）；属于外部设备的辅助存储器，或外存（即平常说的磁盘之类）；以及各种高速缓存，用于提高各级存储间转存过程的速度（从本质上说缓存不是为了存储，只起到桥梁的作用）。但毫无疑问的是：内存处于整个存储系统的核心。处理器从内存中取指令、取绝大部分操作数（因为有些操作数存在于处理器内部的寄存器中），并且将指令执行的结果放回内存。可见，内存是处理器直接交互的对象，在作为计算机运行本质的指令执行过程中起着非常重要的作用。随着计算机执行程序的复杂度的不断发展，内存也需要越来越复杂的管理方式。

内存模块由一组单元构成，这些单元由一系列顺序编号的地址定义。每个单元包含一个8位的二进制数。这些数可以解释为指令或是数据。通过地址可以访问内存单元，获取其中的内容或是向其中写内容。所谓内存管理，就是对通过地址来访问内存单元的方式进行实现和规范，以满足特定的需求。

以下先对内存管理的需求进行说明，之后对操作系统的内存管理策略进行分析。由于不论需求还是管理策略都是随着计算机的发展而不断演变的，我们会从中看到一个逐步复杂和完善的过程：从最初的不需要内存管理，到现代操作系统普遍采用的虚拟内存管理方案。文章的最后部分进行总结和展望。

内存管理的需求

从计算机和操作系统的发展看内存使用的变化

内存管理的需求是随着计算机和操作系统的发展而不断变化的。早期的计算机不存在操作系统，直接由人工给每个作业加载程序并运行，当然也不存在对内存管理的需求。但这样对每个作业由人工进行调度和准备是非常浪费时间的，而且处理器不能得到充分的利用。为了充分利用处理器时间，人们开发了批处理操作系统。这类简单的操作系统就是一段监控程序。大部分监控程序必须常驻内存并且可执行。由监控程序依次从输入设备读取一个作业，并把控制权交给这个作业，由它使用处理器。这个作业完成后再把控制权交回监控程序，监控程序读入下一个作业。这样就可以自动成批的处理多个作业，期间减少了人工的干预。

这种早期的操作系统依赖于处理器能从内存的不同部分读取指令即进行跳转的能力。我们对其实现不做过多论述，只强调它在内存方面的特性。上述操作系统虽然简单，但已经需要对内存访问进行限制了。考虑其机制会发现，内存被分为两个部分，一部分用于监控程序的驻留，另一部分用于运行用户的应用程序。而用户程序运行时，不能改变或者访问包含监控程序的内存区，否则会无意或恶意的导致系统崩溃。这种内存保护可以说是最早的“内存管理”。其实，这种内存保护是由处理器硬件实现了，还不属于操作系统内存管理的范畴。

即使对于批处理系统提供的自动作业序列，处理器仍然大部分时间处于空闲状态。因为I/O设备往往相对于处理器速度极其缓慢。当程序进行I/O操作时，处理器不得不等待这种费时的过程结束，才能继续顺序执行下面的指令。避免这种低效的方法就是多任务系统（又称多道程序设计），这是现代操作系统的主要方案。多道程序设计的思想如下：内存中除了操作系统，可以同时驻留不止一个用户程序。这样当一个程序（即上面提到的作业）需要进行I/O操作时，处理器切换为执行另一个程序而不必等待；第一个程序所需的I/O完成后告诉处理器，处理器就可以接着执行。这种机制一般由中断来实现，而且需要在多个进程间进行调度，还涉及互斥与同步、避免死锁与饥饿等一系列问题。但本文主要关注其对内存管理的需求。

当前内存管理的需求

在多道程序设计或多任务系统中，由于有多个程序同时驻留在内存里，因此必须对内存中除操作系统区域外的用户部分进一步细分，来满足同时运行多个程序（以下用更准确的术语“进程”代替）的要求。这种细分的任务在软件方面由操作系统动态完成，这就是真正的操作系统内存管理。具体来说，对内存管理有五点需求：

（1）重定位

多任务系统中，可用的内存空间通常被多个进程共享。而且，为了最大程度地利用处理器时间，还希望能够有一个更大的就绪进程池，把磁盘也利用起来。也就是说，如果内存中的所有进程都需等待，可以把其中的某个等待进程从内存换出，写到磁盘上，从而腾出空间加载一个新的进程。而当换出的那个进程等待结束后，再把它换入内存中继续执行。一方面，不可能事先知道进程被放置在内存的那一段；另一方面，在换入换出的过程中进程所处实际位置也可能改变。这需要操作系统提供一种重定位机制，使得程序内部的寻址你能够正确指向所需的内存单元。总结来说，必须通过某种方式把程序代码中的内存访问转换成实际的物理内存地址，并且反映程序在内存中的当前位置。这需要处理器硬件和操作系统软件合作实现。

（2）保护

这在单任务系统中也涉及到了，当时指的是需要保护监控程序（即操作系统）区不受用户程序区的非法访问。而在多任务系统中，每个进程都需要受保护。一个程序在未授权时不仅不能访问操作系统区，也不能访问其他任一个进程的内存区。如前所述，程序在内存中的位置是可能变化且不可预测的，所以检查必须在运行时进行。如果发现一个程序试图访问不属于自己的内存单元（授权和共享的除外），处理器必须终止执行这样的指令。

这里要说明的是，内存保护的需求需要处理器硬件来满足，而非操作系统软件，因为操作系统不可能提前预见某个程序中可能产生的所有内存访问。下面会看到，操作系统所做的只是协助处理器实现该需求。

（3）共享

这是保护机制所具有的灵活性。有些公共子程序（例如操作系统提供的底层函数）可以让多个进程共享一个副本，而合作完成统一任务的进程有时需要访问同一份数据。因此，内存管理必须能够在不损害基本保护的前提下允许受控的共享。

（4）逻辑组织

物理内存都是线性的地址空间，但实际的程序一般都是按照逻辑进行模块化组织的。各模块可以独立，也可以互相合作使用。计算机和操作系统应该能够支持这种模块化的需求。一般通过内存分段来满足这种需求。

（5）物理组织

正如引言中所说，计算机系统的存储一般都是分级的。内部主存和外部辅存、以及主存和缓存之间，需要经常交换数据。在重定向需求的分析中，已经体现了内存和磁盘交换数据的重要性。程序员不应来关心存储系统的物理组织，所以这种在不同级存储器间移动信息的任务应是一种系统责任。事实上，该任务恰恰就是存储管理的本质所在。

以上对内存管理的需求进行了分析。为满足这些需求，需要处理器硬件和操作系统软件的配合。下面人们相继提出的内存分区、分页和分段技术。它们在有效解决上面提到的问题方面发挥了重要的作用，而且现代操作系统普遍采用的虚拟内存管理就是以分段和分页为基础的。

分区、分页与分段技术

内存分区

内存分区技术存在于许多现在已过时的系统中。它曾经用于满足多任务系统对内存管理的需求。内存管理最基本的操作就是把程序装入内存中由处理器执行。在大多数的管理方案中，都假定操作系统占据内存中固定的一部分，而其余部分供多个进程使用，称为用户内存空间。分区技术就是简单的把用户内存空间进行分区。分区方法中最原始的是固定分区。它把整个内存分成固定的多个区域（可以是定长的或是不定长的）。需要转载一个程序时，选择足够大的分区装入即可；如果所有分区都满了，则操作系统将处于非运行态的进程换出，从而腾出可用的分区。这种固定分区方案比较简单，需要的操作系统开销很小，但其缺点也是明显的：由于分区大小是固定的，有些小的作业不能恰好填满一个分区，就会导致无用的“洞”，造成内存浪费；另外，分区数目在系统生成时也已确定，这就限制了系统中活动进程的数目。

为了克服固定分区的缺点，出现了动态分区方法。顾名思义，这种方案中分区数目和大小可以在系统运行时动态的改变。在装入一个进程时，系统分配给它一个与其大小一样的分区。但由于各个进程大小有区别，在经历多次换入换出后，仍不可避免会产生很多小的“内存洞”。但因为分区本就是动态的，操作系统可以通过在内存中“移动”进程来“压缩”这些碎片。这是一个十分费时的操作，所以应尽量采用比较好的放置算法，在将进程分派到内存中时能尽量塞住洞或避免洞。由于分区管理已经基本不再采用，所以此处不再做过多介绍。详情可参考文献[1].

分区方案虽然有很多不尽人意之处，但是也已经基本满足了内存管理的需求，能保证多道程序系统的运行。对于前面提到的重定向要求，采取的解决方案是：在编写程序时使用逻辑地址，例如相对于程序起始处的相对地址，而在运行时将逻辑地址转换为物理地址。操作系统只需要记住把程序起始处放在了哪一个实际的物理地址处，就可以通过相对地址访问到对应的正确物理单元。这种把逻辑地址转换为物理地址的过程需要硬件机制实现，方法如在基址寄存器中保存程序起始地址，通过在基址加上相对地址得到实际用于访问内存的物理地址。类似的硬件机制在现代的虚拟内存管理中也是需要的，只是更为复杂。

分页技术

分区技术在内存的使用上因为会产生洞故而是低效的，但这种思想的进一步延伸就是分页技术——把每个“区”都设定的足够小，而为一个进程分配多个这样的小“区”，而且这些“区”也不一定要连续。在分页技术中，一个进程被分为大小固定相等的块，称为页（page）；内存的用户区域则被分成同样大小的块来容纳页，称之为页框（page frame）。加载一个进程时，可以将其中的页填进任意空闲的页框中，不需要连续，只需操作系统为进程维护一个页表，能够查找该进程的各个页所对应的页框即可。这样程序中的逻辑地址就用页号和页中的偏移量来表示。一般页的大小都是2的幂，故只需简单的使用地址的高位和低位来分别表示页号和偏移量。对处理器而言，需要硬件机制来支持这种分页技术中的寻址过程。前面提到的基址寄存器用于保存页表的首地址，从而使处理器能通过页号检索到对应的页框号，进而与偏移量相加得到物理地址。

可见，分页技术是从固定分区技术进化而来。由于每个页相对很小，而且进程也不需要使用连续的页框，这就基本上避免了内存空洞的产生。但也相对增加了操作系统维护每个进程的页表和内存空闲页表的软件负担。而且，更重要的，由于“分配单元”的增多，在增加灵活性的同时也增加了替换和放置时可设计算法的复杂性。详情参见下面虚拟内存管理部分。

分段技术

分页对程序员来说是不可见的。程序员只需要在程序中使用逻辑地址，不需要关心程序运行时内存在物理上具体是如何分配的。另一种对程序员可见的技术是分段。这也是针对逻辑组织需求而提出的技术。分段针对程序进行。程序员可以把程序和其相关的数据分开放置在几个段中，段的长度可以任意，但需要指定一个段的最大长度空间用于越界的检查。在运行一个程序时，程序的各个段都被加载进内存，但可以位于不连续的区域。这要求操作系统为每个进程维护一个段表，每个段表项除了给定该段在内存中的实际起始地址，还要给出该段的长度，以确保不会越界。同样，每个进程段表的首地址需要装载进一个寄存器，来为支持分段的内存管理硬件所用。

本质上看，分段技术类似于动态分区。不同的是，段很小，所以可以避免产生很大的碎片。另外，分段机制让程序员可以更灵活地控制程序中各个部分（代码或数据），便于模块化处理。

分页和分段构成了现代操作系统中虚拟内存管理的技术基础。虚拟内存的引入使得每个用户程序可引用的内存空间极大，从而程序员不再感到内存受限；同时使得系统中可以同时驻留的进程数目也极多，从而处理器资源得到了更有效地利用。以下详细阐述虚拟内存管理。

虚拟内存管理策略

基本思想和可行性

虚拟内存管理基于如下的基本思想：一个程序的运行，不需要其全部都在内存中，只要当前存储器访问所涉及的那部分内容在内存中，执行就可以顺利进行；一旦访问涉及到了不在内存中的部分，再向磁盘去取所需的部分装载进内存。这样对实际内存来说，由于只需含有一个进程的部分块，于是就有足够的空间放置更多的进程；而对某个进程来说，由于自己当前不用的部分可放置在磁盘上，它就相当于拥有了磁盘存储器这样大的内存空间。而且这种机制对程序员是透明的：操作系统会自动把需要的进程快转载进内存，程序员只需要不受限地使用用户空间地址能表示的巨大内存区域就行了。

进程实际运行所在的是真实的物理内存，称之为实内存（real memory）；而程序员或用户感觉到的是一个更大的内存，通常被分配在磁盘上，称为虚拟内存（virtual memory）。虚拟内存允许更有效地执行多任务，并解除了用户和内存间的约束，它是当前普遍采用的内存管理策略。

分页和分段为实现上述虚拟存储的想法提供了基本条件，因为利用它们可以进行所需的程序分块（就按前述段和页的方法来分）。但上述想法的效率优势值得怀疑——进程在执行过程中仅仅因为没有装入所需的块就被中断，而且取新块还要去进行缓慢的磁盘I/O。事实是，虚拟内存的这种消耗无法掩盖它所带来的优势，众多操作系统的实验证明了这一点。而虚拟内存可行性的理论基础则可以由局部性原理说明。局部性原理描述了一个进程执行时代码和数据引用的集簇倾向，即一段时间内访问的都是局部相邻区域，典型的例子是循环语句（代码块）和数组的使用（数据块）。因此假设短时内仅需要程序的一部分块是合理的。

具体实现虚拟内存系统就要处理器硬件和操作系统软件合作完成了。前面已经说过，采用分页和分段时的寻址都需要硬件的支持，而对操作系统来说，则需要有管理不同页或段在主存（实际内存）和辅存（磁盘）之间移动的软件程序。后者是操作系统中一个复杂的问题，涉及多种算法，且都在不断发展之中。下面我们就着重介绍当前操作系统所用的虚拟内存管理的各种策略和算法。在此之前，先简单介绍硬件对分页和分段寻址的支持。

硬件机制的支持

目前，虚拟内存管理一般与采用分段和分页技术的系统联系在一起，至少也应是采用分页技术的系统。前面介绍分页和分段时已经大致分析了寻址时的硬件机制，此处将段页式系统的寻址方法总结说明于下图。

（摘自文献[2]）

可见，用户在程序中使用的是虚拟地址，由高位到低位可分为三部分：段号、页号和页内偏移量。事实上正如前面提到的，分页对程序员来说是透明的，因此程序员在程序中指定的是段号和段内偏移量，由系统为其将段内偏移量解释为页号和页内偏移量。处理器执行一个进程时，这个进程的段表首地址被调入寄存器。处理器通过段号和段表首地址找到相应的段表项。段表项中存有含有段长度和一个基域，基域指向该段对应的一个页表（如果一个段长度小于一页，则用一页表示，即页表中只有一项）。此外，段表项中还会含有基于共享和保护目的的一些控制位（下面详述）。处理器通过页号和页表地址就可以找到相应的页表项。页表项作用与简单分页相同，为了将页号映射到实际内存中的页框号。有了页框号，再加上偏移量，就得到了真正的物理地址，从而完成了寻址过程。

与前述简单分段和分页不同的是，采用虚拟内存时的段表或页表项中要增加许多控制位。一方面是因为并非程序的所有页都在内存中，因此需在页表项中记录该页是否在内存中这一信息；另一方面，进程的某个段或页在换出内存时需要看它是否被更改，从而判断是否需要写回磁盘（如果没有改动就无需写回）。此外，实现页级和段级的保护和共享，也需要相应的控制位。

为了避免每次存储器可能需要的多次物理存储访问（如需要查询页表和段表），大多数虚拟存储方案还会使用特殊的高速缓存，称为“转换后备缓冲区”。这就要求更复杂的硬件支持。关于硬件机制的更多内容这里不再叙述，可参考相关文献。

操作系统软件策略

操作系统作为软件程序，采用一套算法进行虚拟内存的管理，完成不同页或段在主存（实际内存）和辅存（磁盘）之间准确高效移动的任务。现代操作系统中除了特殊设计的，几乎所有都采用分页机制。因此在研究操作系统对虚拟内存的管理时集中与分页相关的问题。概括来说，操作系统需要实现取策略、放置策略、替换策略、清除策略，等等。

取策略指的是确定一个页何时被取来放入内存。两种常用方法是请求式和预约式。前者只有当需要访问某页中的字时才将它取入内存，即完全根据缺页故障的中断来进行页面调度。后者则连续取多个页，这种方法考虑了辅存的延迟，但常因取进的页并未用到而导致低效。一般来说，在进程初次启动时采用预约式取页，而运行过程中则采用请求式。

放置策略考虑把取进内存的页放在哪里。这并非主要问题，因为对上述一个处理器的硬件寻址机制来说，放置于任何一个空闲的页框都是没有区别的。只有当涉及到多处理器的不一致存储访问时才应仔细考虑该策略。

替换策略指的是，当取进一个新页时是否替换旧页以及应该替换掉哪个旧页。这可以说是操作系统内存管理中最复杂的一部分。它涉及到为每个进程分配多少个页面、可替换的旧页集合为哪些，以及应选取该集合内的那个页面。常用的算法包括最优（OPT）、最近最少使用（LRU）、先进先出（FIFO）以及广泛使用的时钟算法（Clock）。OPT策略选择替换据下次访问最久的页，从而导致最少的缺页，但它实现困难且开销大，一般不用。LRU和FIFO容易顾名思义地理解，下面主要介绍一下应用广泛的时钟算法。最简单的时钟策略需要为每一页框提供一个“使用位”，当某一页装入该框时其使用位置1。所有候选框集合被认为是一个循环缓冲区，有一指针与之关联，每一页被替换后就指向下一页框。需要替换时，操作系统如果发现缓冲区内所有页框使用位都为0，则替换第一个框；否则就顺序扫描缓冲区，查找第一个使用位为0的框来替换，途中遇到使用位为1的则置0。这种时钟算法及其变体（如扩展“使用位”）在Macintosh和UNIX的多种操作系统中都有使用。

清除策略主要处理内存中被修改过的页何时写回磁盘。这可认为是与取策略相反的过程，相应也分为两种方式：一旦将要被替换时才写回的请求式和在所占据页框被用到前就写回（可以成批）的预约式。

除了上述内容外，操作系统还需要控制同时驻留在内存中的进程总数（称为“加载控制”），以及当所有驻留的进程都需要等待时的换出问题（有点类似调度），等等。限于篇幅，本文不再详述。各种策略的算法也在不断地改进和增加，在进行操作系统设计时应结合其他设计因素，根据具体的应用需求进行选优。

结论和展望

由于其优秀的性能和灵活性，虚拟内存管理目前广泛运用到包括Windows和Linux在内的各种操作系统中。内存管理发展到现在，已经形成了一套成熟的机制和算法。我们看到，从最初简单进行监控程序和用户程序间的隔离和保护，到现在复杂但有效而灵活的虚拟内存机制，都是处理器硬件和操作系统理论共同发展、互相结合的结果。在未来，随着多处理器系统、集群系统乃至分布式系统的发展，可能对计算机的存储管理有更多的需求；本文没有过多分析缓存机制，但未来可能更多级的缓存会加入；而且存储器的安全性也需要更好的保障。所有这些和更多的因素将促进存储管理理论和技术的向前发展。更快速、更大容量、更安全的存储器访问将是不断追求的目标。

参考文献

[1] William Stallings, 陈渝译.操作系统：精髓与设计原理.电子工业出版社.2007.

[2]William Stallings. Operating Systems Internals and Design Principles. Prentice Hall; 6 edition (April 19, 2008)

[3] William Stallings, 张昆藏等译.计算机组成与体系结构.北京：清华大学出版社.2005.

[4] 任乔伟. Linux内核修炼之道. 人民邮电出版社. 2010

[5] Bray, 金治平等译. Intel微处理器. 机械工业出版社.2008

[6] Alfred V. Aho等, 赵建华等译. 编译原理. 机械工业出版社.2008

[7]百度百科·虚拟内存： http://baike.baidu.com/view/976.htm

[8]虚拟内存管理：http://www.chinaunix.net/jh/23/650593.html

[9] Linux内存管理：http://wenku.baidu.com/view/dcd4c24bcf84b9d528ea7ac9.html

[10]Linux管理员手册(4)： http://www.sudu.cn/info/article/articleInfo.php?aId=90374

[11]内存管理内幕： http://www.ibm.com/developerworks/cn/linux/l-memory/

[12] Windows内存管理：http://wenku.baidu.com/view/98882542336c1eb91a375df9.html