概述

操作系统中管理分层存储器体系的部分称为存储管理器（memory manager）。它的任务是有效地管理内存，即记录哪些内存是正在使用的，哪些内存是空闲的；在进程需要时为其分配内存，在进程使用完后释放内存。

这里会研究几个不同的存储管理方案。

无存储器抽象

最简单的存储器抽象就是根本没有抽象，每一个程序都直接访问物理内存。

地址空间

概述

要使多个应用程序同时处于内存中并且不互相影响，需要解决两个问题：保护和重定位。不太好的解决方式：

给内存块标记上一个保护键，并且比较执行进程的键和其访问的每个内存字的保护键。
在程序被装载时重定位程序，这是一个缓慢且复杂的解决方法。

一个更好的办法是创造一个新的存储器抽象：地址空间。地址空间为程序创造了一种抽象的内存，它是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间，并且这个地址空间独立于其他进程的地址空间（除了在一些特殊情况下进程需要共享它们的地址空间外）。

比较难的是给每个程序一个自己独有的地址空间，使得一个程序中的地址28所对应的物理地址与另一个程序中的地址28所对应的物理地址不同。有一种比较简单的方法是：基址寄存器与界限寄存器。

这个简单的解决办法是使用动态重定位，简单地把每个进程的地址空间映射到物理内存的不同部分。当使用基址寄存器和界限寄存器时，程序装载到内存中连续的空闲位置且装载期间无须重定位，当一个进程运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中。

每次一个进程访问内存，取一条指令，读或写一个数据字，CPU硬件会在把地址发送到内存总线前，自动把基址值加到进程发出的地址值上。同时，它检査程序提供的地址是否等于或大于界限寄存器里的值。如果访问的地址超过了界限，会产生错误并中止访问。

使用基址寄存器和界限寄存器重定位的缺点是，每次访问内存都需要进行加法和比较运算。比较运算可以做得很快，但是加法运算由于进位传递时间的问题，在没有使用特殊电路的情况下会显得很慢。

实际上，所有进程所需的RAM数量总和通常要远远超出存储器能够支持的范围，有两种处理内存超载的通用方法：

交换技术，即把一个进程完整调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行时就不会占用内存
虚拟内存，该策略甚至能使程序在只有一部分被调入内存的情况下运行

交换技术

交换技术的操作如下图所示：

开始时内存中只有进程A。之后创建进程B和C或者从磁盘将它们换入内存。图d显示A被交换到磁盘。然后D被调入，B被调出，最后A再次被调入。由于A的位置发生变化，所以在它换入的时候通过软件或者在程序运行期间(多数是这种情况)通过硬件对其地址进行重定位。例如，基址寄存器和界限寄存器就适用于这种情况。

交换在内存中产生了多个空闲区(hole,也称为空洞)，通过把所有的进程尽可能向下移动，有可能将这些小的空闲区合成一大块。该技术称为内存紧缩(memory compaction)，通常不进行这个操作，因为它要耗费大量的CPU时间。例如，一台有16GB内存的计算机可以每8ns复制8个字节，它紧缩全部内存大约要花费16s。

如果进程的数据段可以增长，例如，很多程序设计语言都允许从堆中动态地分配内存，那么当进程空间试图增长时，就会出现问题。若进程与一个全闲区相邻，那么可把该空闲区分配给进程供其增大。另一方面，若进程相邻的是另一个进程，那么要么把需要增长的进程移到内存中一个足够大的区域中去，要么把一个或多个进程交换出去，以便生成一个足够大的空闲区。若一个进程在内存中不能增长，而且磁盘上的交换区也已满了，那么这个进程只有挂起直到一些空间空闲(或者可以结束该进程)。

如果大部分进程在运行时都要增长，为了减少因内存区域不够而引起的进程交换和移动所产生的开销，一种可用的方法是，当换入或移动进程时为它分配一些额外的内存。然而，当进程被换出到磁盘上时，应该只交换进程实际上使用的内存中的内容，将额外的内存交换出去是一种浪费。

如果进程有两个可增长的段，例如，供变量动态分配和释放的作为堆使用的一个数据段，以及存放普通局部变量与返回地址的一个堆栈段，则可使用另一种安排：进程的堆栈段在进程所占内存的顶端并向下增长，紧接在程序段后面的数据段向上增长。在这两者之间的内存可以供两个段使用。如果用完了，进程或者必须移动到足够大的空闲区中（它可以被交换出内存直到内存中有足够的空间），或者结束该进程。

空闲内存管理

在动态分配内存时，操作系统必须对其进行管理。一般而言，有两种方法跟踪内存使用情况：

位图
空闲区链表

如下图所示：

位图

使用位图方法时，内存可能被划分成小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）。

分配单元的大小是一个重要的设计因素。分配单元越小，位图越大。若进程的大小不是分配单元的整数倍，那么在最后一个分配单元中就会有一定数量的内存被浪费了。

在决定把一个占n个分配单元的进程调入内存时，存储管理器必须捜索位图，在位图中找出有n个连续0的串。査找位图中指定长度的连续0串是耗时的操作（因为在位图中该串可能跨越字的边界），这是位图的缺点。

链表

另一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表。其中链表中的一个结点或者包含一个进程，或者是两个进程间的一块空闲区。

进程表中表示终止进程的结点中通常含有指向对应于其段链表结点的指针，因此段链表使用双向链表可能要比单向链表更方便。这样的结构更易于找到上一个结点，并检査是否可以合并。

虚拟内存

概述

程序大于内存的问题早在计算时代伊始就产生了，虽然存储器容量增长快速，但是软件大小的增长更快。这一发展的结果是，需要运行的程序往往大到内存无法容纳，而且必然需要系统能够支持多个程序同时运行，它们很容易超出了内存大小。交换技术并不是一个具有吸引力的解决方案，因为一个典型SATA磁盘的峰值传输率髙达每秒好几百兆，这意味着需要好几秒才能换出或换入一个1GB的程序。

虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作一页（page），毎一页有连续的地址范围。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

从某个角度来讲，虚拟内存是对基址寄存器和界限寄存器的一种综合。

分页

大部分虚拟内存系统中都使用一种称为分页(paging)的技术，当程序执行指令MOV REG, 1000时，它把地址为1000的内存单元的内容复制到REG中(或者相反)。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。

由程序产生的这些地址称为虚拟地址(virtual address)**，它们构成了一个虚拟地址空间(virtual address space)。在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字；而在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元(Memory Management Unit，MMU)**, MMU把虚拟地址映射为物理内存地址。

举例如下：

在这个例子中，有一台可以产生16位地址的计算机，地址范围从0到64K-1,且这些地址是虚拟地址。然而，这台计算机只有32KB的物理内存，因此，虽然可以编写64KB的程序，但它们却不能被完全调人内存运行。在磁盘上必须有一个最多64KB的程序核心映像的完整副本，以保证程序片段在需要时能被调入内存。

虚拟地址空间按照固定大小划分成被称为页面(page)**的若干单元。在物理内存中对应的单元称为页框(page frame)**。页面和页框的大小通常是一样的，在本例中是4KB。

当程序试图访问地址0时，将虚拟地址0送到MMU。MMU看到虚拟地址落在页面0(0~4095)，根据其映射结果，这一页面对应的是页框2 (8192〜12287)，因此MMU把地址变换为8192，并把地址8192送到总线上。内存对MMU无所知，它只看到一个读或写地址8192的请求并执行它。MMU从而有效地把所有从0〜4095的虚拟地址映射到了8192-12287的物理地址。

当程序访问了一个未映射的页面，例如访问地址32780：MMU注意到该页面没有被映射(在图中用叉号表示)，于是使CPU陷入到操作系统，这个陷阱称为**缺页中断或缺页错误(page fault)**。操作系统找到一个很少使用的页框且把它的内容写入磁盘(如果它不在磁盘上)。随后把需要访问的页面读到刚才回收的页框中，修改映射关系，然后重新启动引起陷阱的指令。

页表

页表的目的是把虚拟页面映射为页框。作为一种最简单的实现，虚拟地址到物理地址的映射可以槪括如下：虚拟地址被分成虚拟页号（髙位部分）和偏移量（低位部分）两部分。例如，对于16位地址和4KB的页面大小，髙4位可以指定16个虚拟页面中的一页，而低12位接着确定了所选页面中的字节偏移量（0~4095）。

虚拟页号可用作页表的索引，以找到该虚拟页面对应的页表项。由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的髙位端，以替换掉虚拟页号，形成送往内存的物理地址。

—个典型的页表项：[Data][髙速缓存禁止位][访问位保护位][修改位][“在/不在”位][页框号]。

页框号：通过它找到真正的物理地址
“在/不在”位：表示该表项对应的虚拟页面在不在内存中，访问该页面是否会引起缺页中断
保护位：指出一个页允许什么类型的访问，是否启用读、写、执行该页面。
修改（modified）位和访问（referenced）位：在写入一页时由硬件自动设置修改位。该位在操作系统重新分配页框时是非常有用的。如果一个页面已经被修改过，则必须把它写回磁盘。如果一个页面没有被修改过，则只简单地把它丢弃就可以了，因为它在磁盘上的副本仍然是有效的。这一位有时也被称为脏位（dirty bit），因为它反映了该页面的状态。
高速缓存禁止位：用于禁止该页面被髙速缓存。对那些映射到设备寄存器而不是常规内存的页面而言，这个特性是非常重要的。假如操作系统正在紧张地循环等待某个I/O设备对它刚发出的命令作出响应，保证硬件是不断地从设备中读取数据而不是访问一个旧的被髙速缓存的副本是非常重要的。

应该注意的是，若某个页面不在内存中，用于保存该页面的磁盘地址不是页表的组成部分。原因很简单，页表只保存把虚拟地址转换为物理地址时硬件所需要的信息。操作系统在处理缺页中断时需要把该页面的磁盘地址等信息保存在操作系统内部的软件表格中。硬件不需要它。

虚拟内存本质上是用来创造一个新的抽象槪念——地址空间，这个槪念是对物理内存的抽象，类似于进程是对物理处理器（CPU）的抽象。虚拟内存的实现，是将虚拟地址空间分解成页，并将每一页映射到物理内存的某个页框或者（暂时）解除映射。

在任何分页系统中，都需要考虑两个主要问题：

虚拟地址到物理地址的映射必须非常快。
如果虚拟地址空间很大，页表也会很大。

加速分页过程

转换检测缓冲区

为计算机设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再访问页表。这种设备称为转换检测缓冲区（Translation Lookaside Buffer, TLB）,有时又称为相联存储器（associate memory）或快表。

这种解决方案的建立基干这样一种观察：大多数程序总是对少量的页面进行多次的访问，而不是相反。因此，只有很少的页表项会被反复读取，而其他的页表项很少被访问。

它通常在MMU中，包含少量的表项，每个表项记录了一个页面的相关信息，包括虚拟页号、页面的修改位、保护码（读/写/执行权限）和该页所对应的物理页框。除了虚拟页号（不是必须放在页表中），这些域与页表中的域是一一对应的。另外还有一位用来记录这个表项是否有效（即是否在使用）。

软件TLB管理

在过去，对TLB的管理和TLB的失效处理都完全由MMU硬件来实现，只有在内存中没有找到某个页面时，才会陷入到操作系统中。但是，许多现代的机器几乎所有的页面管理都是在软件中实现的，在这些机器上，TLB表项被操作系统显式地装载。当发生TLB访问失效时，不再是由MMU到页表中査找并取出需要的页表项，而是生成一个TLB失效并将问题交给操作系统解决。系统必须先找到该页面，然后从TLB中删除一个项，接着装载一个新的项，最后再执行先前出错的指令。当然，所有这一切都必须在有限的几条指令中完成，因为TLB失效比缺页中断发生得更加频繁。

如果TLB大到（如64个表项）可以减少失效率时，TLB的软件管理就会变得足够有效。这种方法的最主要的好处是获得了一个非常简单的MMU,这就在CPU芯片上为髙速缓存以及其他改善性能的设计腾出了相当大的空间。

大内存页表

多级页表

一个二多级页表如下所示：

考虑32位虚拟地址0x00403004，它的虚拟地址对应PT1 = 1，PT2 = 3, Offset = 4。MMU首先用PT1作为索引访问顶级页表得到表项1，它对应的地址范围是4M到8M-1。然后，它用PT2作为索引访问刚刚找到的二级页表并得到表项3，它对应的虚拟地址范围是在它的4M块内的12288〜16383（即绝对地址4206592-4 210687）。这个表项含有虚拟地址0x00403004所在页面的页框号。如果该页面不在内存中，页表项中的“在/不在”位将是0，引发一次缺页中断。如果该页面在内存中，从二级页表中得到的页框号将与偏移量（4）结合形成物理地址。该地址被放到总线上并送到内存中。

倒排页表

当虚拟地址空间比物理内存大得多的时候，倒排页表节省了大量的空间，但是从虚拟地址到物理地址的转换会变得很困难。

页面置换算法

“页面置换”问题在计算机设计的其他领域中也同样会发生。例如高速缓存的更换等。

若每执行几条指令程序就发生一次缺页中断，那么就称这个程序发生了颠簸。

最优页面置换算法

该算法是这样工作的：在缺页中断发生时，有些页面在内存中，其中有一个页面（包含紧接着的下一条指令的那个页面）将很快被访问，其他页面则可能要到10、100或1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。

这个算法唯一的问题就是它是无法实现的。

最近未使用页面置换算法

为使操作系统能够收集有用的统计信息，在大部分具有虚拟内存的计算机中，系统为每一页面设置了两个状态位。当页面被访问（读或写）时设置R位：当页面被写入（即修改）时设置M位。这些位包含在每个页表项中，每次访问内存时更新这些位，因此由硬件来设置它们是必要的。一旦设置某位为1，它就一直保持1直到操作系统将它复位。

当启动一个进程时，它的所有页面的两个位都由操作系统设置成0, R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。当发生缺页中断时，操作系统检査所有的页面并根据它们当前的R位和M位的值，把它们分为4类：

第0类：没有被访问，没有被修改
第1类：没有被访问，已被修改
第2类：已被访问，没有被修改
第3类：已被访问，已被修改

NRU（Not Recently Used，最近未使用）算法随机地从类编号最小的非空类中挑选一个页面淘汰。这个算法隐含的意思是，在最近一个时钟滴答中（典型的时间是大约20ms）淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好。NRU的主要优点是易于理解和能够有效地被实现，虽然它的性能不是最好的，但是已经够用了。

先进先出页面置换算法

另一种开销较小的页面置换算法是FIFO（First-In First-Out，先进先出）算法。由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。

第二次机会页面置换算法

FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：检査最老页面的R位。如果R位是0，那么这个页面既老又没有被使用，可以立刻置换掉：如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续捜索。这一算法称为第二次机会（second chance）算法。

时钟页面置换算法

尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。当发生缺页中断时，算法首先检査表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置：如果R位是1就清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面为止。

最近最少使用页面置换算法

最近最少使用页面置换算法（LRU）在理论上是可以实现的，但代价很髙。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作，即使使用硬件实现也一样费时（假设有这样的硬件）。

然而，还是有一些使用特殊硬件实现LRU的方法。首先考虑一个最简单的方法，这个方法要求硬件有一个64位计数器C，它在每条指令执行完后自动加1，每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的C值保存到被访问页面的页表项中。一旦发生缺页中断，操作系统就检査所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最近最少使用的页面。

最不常用页面置换算法

前面一种LRU算法虽然在理论上是可以实现的，但只有非常少的计算机拥有这种硬件。因此，需要一个能用软件实现的解决方案。一种可能的方案称为NFU（Not Frequently Used，最不常用）算法。该算法将每个页面与一个软件计数器相关联，计数器的初值为0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的R位（它的值是0或1）加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。

工作集页面置换算法

在单纯的分页系统里，刚启动进程时，在内存中并没有页面。在CPU试图取第一条指令时就会产生一次缺页中断，使操作系统装入含有第一条指令的页面。其他由访问全局数据和堆栈引起的缺页中断通常会紧接着发生。一段时间以后，进程需要的大部分页面都已经在内存了，进程开始在较少缺页中断的情况下运行。这个策略称为请求调页(demand paging)，因为页面是在需要时被调入的，而不是预先装入。

大部分进程都表现出一种局部性访问行为，即在进程运行的任何阶段，它都只访问较少的一部分页面。一个进程当前正在使用的页面的集合称为它的工作集，如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段(例如，编译器的下一遍扫描)之前，不会产生很多缺页中断。

所以不少分页系统都会设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了。该方法称为工作集模型。在进程运行前预先装入其工作集页面也称为预先调页(prepaging)。

为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。通过这些信息可以直接推导出一个合理的页面置换算法：当发生缺页中断时，淘汰一个不在工作集中的页面。为了实现该算法，就需要一种精确的方法来确定哪些页面在工作集中。根据定义，工作集就是最近A次内存访问所使用过的页面的集合。

一种常见的近似方法就是，不是向后找最近A次的内存访问，而是考虑其执行时间。一个进程从它开始执行到当前所实际使用的CPU时间总数通常称作当前实际运行时间。通过这个近似的方法，进程的工作集可以被称为在过去的实际运行时间中它所访问过的页面的集合。

该算法工作方式如下：假定使用硬件来置R位和M位，同样，假定在每个时钟滴答中，有一个定期的时钟中断会用软件方法来清除R位。每当缺页中断发生时，扫描页表以找出一个合适的页面淘汰之。在处理毎个表项时，都需要检査R位：

如果它是1，就把当前实际时间写进页表项的“上次使用时间”域，以表示缺页中断发生时该页面正在被使用。既然该页面在当前时钟滴答中已经被访问过，那么很明显它应该出现在工作集中，并且不应该被删除。
如果R是0，那么表示在当前时钟滴答中，该页面还没有被访问过，则它就可以作为候选者被置换。为了知道它是否应该被置换，需要计算它的生存时间（即当前实际运行时间减去上次使用时间）。如果它的生存时间大于t，那么这个页面就不再在工作集中，而用新的页面置换它。扫描会继续进行以更新剩余的表项。

然而，如果R是0同时生存时间小于或等于t，则该页面仍然在工作集中。这样就要把该页面临时保留下来，但是要记录生存时间最长（“上次使用时间”的最小值）的页面。如果扫描完整个页表却没有找到适合被淘汰的页面，也就意味着所有的页面都在工作集中。在这种情况下，如果找到了一个或者多个R = 0的页面，就淘汰生存时间最长的页面。在最坏情况下，在当前时间滴答中，所有的页面都被访问过了（也就是都有R=l），因此就随机选择一个页面淘汰，如果有的话最好选一个干净页面。

工作集时钟页面置换算法

当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较费时的。有一种改进的算法，它基于时钟算法，并且使用了工作集信息，称为WSClock（工作集时钟）算法，由于它实现简单，性能较好，所以在实际工作中得到了广泛应用。

与时钟算法一样，所需的数据结构是一个以页框为元素的循环表，参见图a，最初，该表是空的。当装入第一个页面后，把它加到该表中。随着更多的页面的加入，它们形成一个环。每个表项包含来自基本工作集算法的上次使用时间，以及R位（已标明）和M位（未标明）。

与时钟算法一样，每次缺页中断时，首先检査指针指向的页面。如果R位被置为1，该页面在当前时钟滴答中就被使用过，那么该页面就不适合被淘汰。然后把该页面的R位置为0，指针指向下一个页面，并重复该算法。该事件序列之后的状态参见图b。

如果R位被置为0，如果页面的生存时间大于t并且该页面是干净的，它就不在工作集中，并且在磁盘上有一个有效的副本。申请此页框，并把新页面放在其中，如图d所示。另一方面，如果此页面被修改过，就不能立即申请页框，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个旧的且干净的页面可以立即使用。

总结

算法	注释
最优算法	不可实现，但可用作基准
NRU（最近未使用）算法	LRU的粗糙版
FIFO（先进先出）算法	可能抛弃重要页面
第二次机会算法	比FIFO有较大的改善
时钟算法	现实
LRU（最近最少使用）算法	很优秀，但很难实现
最不经常使用算法	LRU的相对粗略的近似
老化算法	非常近似LRU的有效算法
工作集算法	实现起来开销很大
工作集时钟算法	好的有效算法

分页系统的设计问题

局部/全局分配策略

三个进程A、B、C构成了可运行进程的集合。假如A发生了缺页中断，页面置换算法在寻找最近最少使用的页面时是只考虑分配给A的页面呢？还是考虑所有在内存中的页面？

负载控制

即使是使用最优页面置换算法并对进程采用理想的全局页框分配，系统也可能会发生颠簸。事实上，一旦所有进程的组合工作集超出了内存容量，就可能发生颠簸。

减少竞争内存的进程数的一个好方法是将一部分进程交换到磁盘，并释放他们所占有的所有页面。即使是使用分页，交换也是需要的，只是现在交换是用来减少对内存潜在的需求，而不是收回它的页面。

页面大小

分离的指令空间和数据空间

共享页面

共享库

可以使用其他的粒度取代单个页面来实现共享。如果一个程序被启动两次，大多数操作系统会自动共享所有的代码页面，而在内存中只保留一份代码页面的副本。代码页面总是只读的，因此这样做不存在任何问题。

依赖于不同的操作系统，每个进程都拥有一份数据页面的私有副本，或者这些数据页面被共享并且被标记为只读。如果任何一个进程对一个数据页面进行修改，系统就会为此进程复制这个数据页面的一个副本，并且这个副本是此进程私有的，也就是说会执行“写时复制”。

现代操作系统中，有很多大型库被众多进程使用，例如，处理浏览文件以便打开文件的对话框的库和多个图形库。把所有的这些库静态地与磁盘上的每一个可执行程序绑定在一起，将会使它们变得更加庞大。

一个更加通用的技术是使用共享库。

内存映射文件

共享库实际上是一种更为通用的机制——内存映射文件(memory-mapped file)的一个特例。这种机制的思想是：进程可以通过发起一个系统调用，将一个文件映射到其虚拟地址空间的一部分。在多数实现中，在映射共享的页面时不会实际读入页面的内容，而是在访问页面时才会被每次一页地读入，磁盘文件则被当作后备存储。当进程退出或显式地解除文件映射时，所有被改动的页面会被写回到磁盘文件中。

内存映射文件提供了一种I/O的可选模型。可以把一个文件当作一个内存中的大字符数组来访问，而不用通过读写操作来访问这个文件。在一些情况下，程序员发现这个模型更加便利。如果两个或两个以上的进程同时映射了同一个文件，它们就可以通过共享内存来通信。一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，它就可以立刻看到上一个进程写操作的结果。因此，这个机制提供了一个进程之间的高带宽通道，而且这种应用很普遍(甚至扩展到用来映射无名的临时文件)。很显然，如果内存映射文件可用，共享库就可以使用这个机制。

清除策略

如果发生缺页中断时系统中有大量的空闲页框，此时分页系统工作在最佳状态。如果每个页框都被占用，而且被修改过的话，再换入一个新页面时，旧页面应首先被写回磁盘。为保证有足够的空闲页框，很多分页系统有一个称为分页守护进程(paging daemon)的后台进程，它在大多数时候睡眠，但定期被唤醒以检査内存的状态。如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存。如果这些页面装入内存后被修改过，则将它们写回磁盘。

在任何情况下，页面中原先的内容都被记录下来。当需要使用一个已被淘汰的页面时，如果该页框还没有被覆盖，将其从空闲页框缓冲池中移出即可恢复该页面。保存一定数目的页框供给比使用所有内存并在需要时捜索一个页框有更好的性能。分页守护进程至少保证了所有的空闲页框是“干净”的，所以空闲页框在被分配时不必再急着写回磁盘。

一种实现清除策略的方法就是使用一个双指针时钟。前指针由分页守护进程控制。当它指向一个脏页面时，就把该页面写回磁盘，前指针向前移动。当它指向一个干净页面时，仅仅指针向前移动。后指针用于页面置换，就像在标准时钟算法中一样。现在，由于分页守护进程的工作，后指针命中干净页面的概率会增加。

虚拟内存接口

到现在为止，所有的讨论都假定虚拟内存对进程和程序员来说是透明的，也就是说，它们都可以在一台只有较少物理内存的计算机上看到很大的虚拟地址空间。对于不少系统而言这样做是对的，但对于一些髙级系统而言，程序员可以对内存映射进行控制，并可以通过非常规的方法来增强程序的行为。

允许程序员对内存映射进行控制的一个原因就是为了允许两个或者多个进程共享同一部分内存。如果程序员可以对内存区域进行命名，那么就有可能实现共享内存：通过让一个进程把一片内存区域的名称通知另一个进程，而使得第二个进程可以把这片区域映射到它的虚拟地址空间中去。通过两个进程(或者更多)共享同一部分页面，髙带宽的共享就成为可能——一个进程往共享内存中写内容而另一个从中读出内容。

页面共享也可以用来实现高性能的消息传递系统。

虚拟内存系统的实现问题

与分页相关的工作

操作系统要在下面的四段时间里做与分页相关的工作：进程创建时，进程执行时，缺页中断时和进程终止时。

当在分页系统中创建一个新进程时，操作系统要确定程序和数据在初始时有多大，并为它们创建一个页表。操作系统还要在内存中为页表分配空间并对其进行初始化。当进程被换出时，页表不需要驻留在内存中，但当进程运行时，它必须在内存中。另外，操作系统要在磁盘交换区中分配空间，以便在一个进程换出时在磁盘上有放置此进程的空间。操作系统还要用程序正文和数据对交换区进行初始化，这样当新进程发生缺页中断时，可以调入需要的页面。某些系统直接从磁盘上的可执行文件对程序正文进行分页，以节省磁盘空间和初始化时间。最后，操作系统必须把有关页表和磁盘交换区的信息存储在进程表中。
当调度一个进程执行时，必须为新进程重置MMU，刷新TLB，以清除以前的进程遗留的痕迹。新进程的页表必须成为当前页表，通常可以通过复制该页表或者把一个指向它的指针放进某个硬件寄存器来完成。有时，在进程初始化时可以把进程的部分或者全部页面装入内存中以减少缺页中断的发生，例如，PC（程序计数器）所指的页面肯定是需要的。
当缺页中断发生时，操作系统必须通过读硬件寄存器来确定是哪个虚拟地址造成了缺页中断。通过该信息，它要计算需要哪个页面，并在磁盘上对该页面进行定位。它必须找到合适的页框来存放新页面，必要时还要置换老的页面，然后把所需的页面读入页框。最后，还要回退程序计数器，使程序计数器指向引起缺页中断的指令，并重新执行该指令。
当进程退出的时候，操作系统必须释放进程的页表、页面和页面在硬盘上所占用的空间。如果某些页面是与其他进程共享的，当最后一个使用它们的进程终止的时候，才可以释放内存和磁盘上的页面。

缺页中断处理

硬件陷入内核，在堆栈中保存程序计数器。大多数机器将当前指令的各种状态信息保存在特殊的CPU寄存器中。
启动一个汇编代码例程保存通用寄存器和其他易失的信息，以免被操作系统破坏。这个例程将操作系统作为一个函数来调用。
当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面。通常一个硬件寄存器包含了这一信息，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。
一旦知道了发生缺页中断的虚拟地址，操作系统检査这个地址是否有效，并检査存取与保护是否一致。如果不一致，向进程发出一个信号或杀掉该进程。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。
如果选择的页框“脏”了，安排该页写回磁盘，并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。无论如何，该页框被标记为忙，以免因为其他原因而被其他进程占用。
—旦页框“干净”后（无论是立刻还是在写回磁盘后），操作系统査找所需页面在磁盘上的地址，通过磁盘操作将其装入。该页面正在被装入时，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。
恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。
调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。
该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

指令备份

当程序访问不在内存中的页面时，引起缺页中断的指令会半途停止并引发操作系统的陷阱。在操作系统取出所需的页面后，它需要重新启动引起陷阱的指令。但这并不是一件容易实现的事。

锁定内存中的页面

虚拟内存和I/O通过微妙的方式相互作用着。

设想一个进程刚刚通过系统调用从文件或其他设备中读取数据到其地址空间中的缓冲区。在等待I/O完成时，该进程被挂起，另一个进程被允许运行，而这个进程产生一个缺页中断。如果分页算法是全局算法，包含I/O缓冲区的页面会有很小的机会（但不是没有）被选中换出内存。如果一个I/O设备正处在对该页面进行DMA传输的过程之中，将这个页面移出将会导致部分数据写入它们所属的缓冲区中，而部分数据被写入到最新装入的页面中。

一种解决方法是锁住正在做I/O操作的内存中的页面以保证它不会被移出内存。锁住一个页面通常称为在内存中钉住（pinning）页面。

另一种方法是在内核缓冲区中完成所有的I/O操作，然后再将数据复制到用户页面。

后备存储

在磁盘上分配页面空间的最简单的算法是在磁盘上设置特殊的交换分区，甚至从文件系统划分一块独立的磁盘（以平衡I/O负载）。大多数UNIX是这样处理的。在这个分区里没有普通的文件系统，这样就消除了将文件偏移转换成块地址的开销。取而代之的是，始终使用相应分区的起始块号。

策略和机制的分离

控制系统复杂度的一种重要方法就是把策略从机制中分离出来。通过使大多数存储管理器作为用户级进程运行，就可以把该原则应用到存储管理中。

一个如何分离策略和机制的简单例子可以参见下图：

其中存储管理系统被分为三个部分：

一个底层MMU处理程序
一个作为内核一部分的缺页中断处理程序
一个运行在用户空间中的外部页面调度程序

所有关于MMU工作的细节都被封装在MMU处理程序中，该程序的代码是与机器相关的，而且操作系统每应用到一个新平台就要被重写一次。

缺页中断处理程序是与机器无关的代码，包含大多数分页机制。策略主要由作为用户进程运行的外部页面调度程序所决定。

当一个进程启动时，需要通知外部页面调度程序以便建立进程页面映射，如果需要的话还要在磁盘上分配后备存储。当进程正在运行时，它可能要把新对象映射到它的地址空间，所以还要再一次通知外部页面调度程序。

一旦进程开始运行，就有可能出现缺页中断。缺页中断处理程序找出需要哪个虚拟页面，并发送一条消息给外部页面调度程序告诉它发生了什么问题。外部页面调度程序从磁盘中读入所需的页面，把它复制到自己的地址空间的某一位置。然后告诉缺页中断处理程序该页面的位置。缺页中断处理程序从外部页面调度程序的地址空间中清除该页面的映射，然后请求MMU处理程序把它放到用户地址空间的正确位置，随后就可以重新启动用户进程了。

分段

概述

作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例程序段、数据段等。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间是二维的。

段的长度在运行期间可以动态改变，比如，堆栈段的长度在数据被压入时会增长，在数据被弹出时又会减小。

因为每个段都构成了一个独立的地址空间，所以它们可以独立地增长或减小而不会影响到其他的段。如果一个在某个段中的堆栈需要更多的空间，它就可以立刻得到所需要的空间，因为它的地址空间中没有任何其他东西阻挡它增长。段当然有可能会被装满，但通常情况下段都很大，因此这种情况发生的可能性很小。要在这种分段或二维的存储器中指示一个地址，程序必须提供两部分地址，一个段号和一个段内地址。

纯分段实现

分段和分页的实现本质上是不同的：页面是定长的而段不是。下图演示了使用分段的过程（最后通过内存紧缩实现）：

分段和分页结合

在段页式存储管理系统中，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于主存空间也分成大小相等的页，主存的分配以页为单位。

段页式系统中，作业的地址结构包含三部分的内容：段号，页号，页内位移量

程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。

分段和分页的区别

段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。
段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定
段向用户提供二维地址空间；页向用户提供的是一维地址空间
段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。

内部碎片和外部碎片

内部碎片（internalfragment)，通常是指将内存以固定大小的块进行分配，采用这种方案，进程所分配的内存可能比所需的大，多出来的未被使用的内存叫做内部碎片。内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间。
外部碎片（externalfragment)，通常是指随着进程移进移出内存，内存的空闲空间被分割成小片段，当所有的总的可用内存之和可以满足分配请求，但是却不连续，就出现了外部碎片问题。外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

页式虚拟存储系统存在内部碎片，段式虚拟存储系统存在外部碎片。