我们在第六章讨论了进程对CPU的共享。CPU调度可以改善CPU利用率并提高计算机对用户的响应速度。然而，为了提高性能我们必须要同时把多个进程保存在内存中；也就是说，我们要共享内存。
我们将在本章讨论各种管理内存的方法。根据基本的计算机硬件，内存管理算法有分页和分段两种策略。（The memory management algorithms vary from a primitive bare-machine approach to paging and segmentation strategies.）每种方法都有自身的优缺点。为一个特定的系统选择一种内存管理方法（memory-management method）要考虑众多因素，尤其是系统的硬件设计。我们即将看到，许多算法需要硬件支持，虽然最新的设计已经将硬件和操作系统紧密的整合在一起了。
9.1 背景知识
如在第一章所见，内存是现代计算机系统操作的核心。内存由大量的字或字节队列构成，每个字或字节都有它自己的地址。CPU根据程序计数器的值从内存中取指令（fetch instruction）。这些指令可能会从指定的内存地址读取数据或将数据存入指定的内存地址。
例如，在一个典型的指令执行周期（instruction-execution cycle）里，首先要从内存中取出一条指令。然后，对这条指令进行解码（decode），这有可能需要从内存中取出操作数。在用这个操作数执行指令之后，可能需要将结果存储回内存中。内存单元只会看到内存地址流；它不知道它们是怎样产生的（通过指令计数器、变址寻址、间接寻址、文字地址（literal address）等等），也不知道它们是什么（指令或数据）。因此，我们可以忽视程序是怎样产生内存地址的，而只考虑正在运行的程序所产生的内存地址序列。
9.1.1 地址绑定（Address Binding）
通常程序以二进制可执行文件（binary executable file）的方式驻留在磁盘中。必须要把程序装入内存并将其置于一个进程中才可以执行它。根据所采用的内存管理策略，进程在执行期间可能会在磁盘和内存之间移动。在磁盘中等待执行的进程形成了输入队列（input queue）。
通常是从输入队列中选择一个进程并将其装入内存。进程在执行过程中从内存中获取指令和数据。最终，进程终止，宣告释放它所占用的内存空间。
大多数系统允许用户进程驻留在内存的任意区域中。因此，虽然计算机的地址空间从00000开始，但是用户进程的首地址不必是00000。这种设计影响到了用户程序可以使用的地址空间。在大多数情况下，用户程序在执行之前要经过多个阶段（有些阶段是可选的）（图9.1）。在这些阶段中可能要以不同的方式来表示地址。在源程序中，地址通常是一些符号（如count）。编译器常常将这些符号绑定（bind）为可重定位地址（如“从这个模块开始的第14个字节”)。然后连接编辑程序（linkage editor）或装入程序（loader）将这些可重定位地址绑定为绝对地址（如：74014）。每次绑定都是从一个地址空间映射到另一个地址空间。
指令和数据到内存地址空间的绑定通常有如下的几步：
? 编译时间（compile time）：如果在编译时间知道进程将处于内存的什么位置，那么就可以产生绝对代码（absolute code）。例如，如果预先知道一个用户进程的驻留地点将从R开始，那么产生的编译代码将从这个地点开始并以此延伸。如果日后程序的开始地点有所变动，那么就必须重新编译。MS-DOS的.COM格式程序是在编译时间进行的绝对代码绑定。
? 装入时间（load time）：如果在编译时间不知道进程将处于内存的什么位置，那么编译程序必须要产生可重定位代码。在这种情况下，最终的绑定延迟到装入时间。如果开始地址有所变动，那么我们只需要利用变动后的地址重新装入用户代码。
? 执行时间（execution time）：如果在进程执行期间可以把它从内存的一段移动到另一段，那么必须要把绑定延迟到运行时间（run time）。这种机制需要特殊的硬件，将在9.1.2节描述。大多数通用操作系统采用了这种方法。
图 9.1 用户程序的多个处理步骤
本章主要讨论在计算机系统中如何高效的实现各种类型的绑定并讨论相关的硬件支持。
9.1.2 逻辑地址空间和物理地址空间
CPU产生的地址通常被称为逻辑地址（logical address）。而物理地址（physical address）则是内存单元的地址，也就是被装入内存的内存地址寄存器（memory-address register）的地址。
编译时和装入时的地址绑定产生的逻辑地址和物理地址是一样的。然而，执行时间地址绑定机制则产生不同的逻辑地址和物理地址。此时，我们往往把逻辑地址视为虚拟地址（virtual address）。在本书中我们把逻辑地址和虚拟地址看作是同一种地址。程序产生的所有逻辑地址形成了逻辑地址空间（logical-address space）；这些逻辑地址所对应的物理地址构成了物理地址空间（physical-address space）。因此，在执行时地址绑定机制中，逻辑地址和物理地址是不同的。
运行时从虚拟地址到物理地址的映射由一个硬件设备完成，它被称为内存管理单元（MMU, memory-management unit）。有多种不同的方法可以完成这种映射，我们将在9.3、9.4、9.5和9.6节介绍。我们临时利用一种简单的MMU机制来阐述这种映射，这种机制是一种一般化的基址寄存器（2.5.3节）。
如图9.2所示，这种方法所需的硬件支持与2.4节讨论的硬件配置略有不同。现在把基址寄存器（base register）称为重定位寄存器（relocation register）。用户程序产生的地址在发送到内存时与重定位寄存器的值相加。例如，如果基地址是14000，那么用户要访问的地址0被动态重定位到地址14000；对地址346的访问将映射到地址14346。运行在Intel 80x86系列处理器上的MS-DOS操作系统在装入和运行进程时要使用四个重定位寄存器。
用户进程从来就不使用实际的物理地址。程序可以创建一个指向地址346的指针，将它存储在内存中，对它进行操作，并把它与其它地址进行比较——所有这些工作都以数字346进行。只有在把它当作内存地址使用时（或许进行间接装入或存储）才根据基地址寄存器对它进行重定位。用户程序对逻辑地址进行处理。内存映射硬件（memory-mapping hardware）则将逻辑地址转换为物理地址。9.1.1节讨论执行时的绑定。最终的地址只有在绑定完成之后才可以确定。（The final location of a referenced memory address is not determined until the reference is made.）
我们现在知道了两种不同类型的地址：逻辑地址（范围从0到最大值）和物理地址（对于基地址R，物理地址的范围从R + 0到R + max）。用户只产生逻辑地址并认为进程运行在从0到max这样的地址空间中。用户程序提供逻辑地址；在使用这些逻辑地址之前必须要把它们转换成为物理地址。
图 9.2 利用重定位寄存器的动态重定位
把逻辑地址空间绑定到物理地址空间的概念是内存管理的核心。
9.1.3 动态装入
讨论至今，必须要把整个程序和进程的数据装入物理内存才可执行进程。进程的大小受物理内存大小的限制。为了获得更好的内存空间利用率，我们使用动态装入（dynamic loading）。利用动态装入，程序（routine）只有在执行之前才被装入内存。所有的程序以可重定位装入格式（relocatable load format）保留在磁盘中。主程序被装入内存并执行。当一个程序调用另一个程序时，这个程序首先检查另一个程序（被调用的程序）是否已经被装入内存。如果没有，那么调用可重定位链接装入程序（relocatable linking loader）把所需的程序装入内存并更新程序的地址表（address table）来反映这次变动。然后把控制转交给新装入的程序。
动态装入的优点是无需把不需执行的程序装入内存。如果程序中有大量的代码是用来处理不常发生的事件（如错误处理函数），那么动态装入是十分有用的。在这种情况下，虽然整个程序可能非常庞大，但是使用（并因此而装入）的部分很小。
动态装入不需要操作系统的专门支持。这是用户的问题，他们利用这种方法来设计程序。操作系统可能会为程序员提供实现动态装入的库函数。
9.1.4 动态链接和共享库
图9.1也描绘了动态链接库（dynamically linked library）。有些操作系统只支持静态链接（static linking），在这种系统中，语言库像其它目标模块（object module）一样被装入二进制程序映象。动态链接（dynamic linking）的概念与动态装入很相似。动态链接直到执行时才进行链接。通常把这种特性用于系统库（system library），如语言子函数库（language subroutine library）。如果没有这种机制，系统中所有的程序都需要在可执行映象（executable image）中包含一份自己的语言库（language library）拷贝。这浪费了磁盘和主内存空间。利用动态链接，在映象中为每个库函数引用（library-routine reference）包含一个占位程序（stub）。占位程序是一小段代码，它指明了怎样定位驻留在内存中的库函数或函数不在内存中时怎样装入库。
占位程序执行时，它检查所需的函数（routine）是否已经在内存中。如果没有，就把函数装入内存。或者以另外一种方式，占位程序用函数地址取代自身并执行这个函数。这样，下一次到达这段代码时，可以直接执行库函数（library routine）而无需动态链接。利用这种机制，使用一个语言库的所有的程序只需要执行一份库代码拷贝。
可以把这种特性用于库的升级（update）（如：消除bug（bug fix））。可以用库的新版本取代旧版本，引用这个库的所有程序将自动使用这个新版本。如果不采取动态链接，引用这个库的所有程序都必须通过重新链接才能来访问新版本库。程序和库中都保留有版本信息，这样程序就不会意外执行新的不兼容的库。可以将一个库的多个版本装入内存，每个程序利用自己的版本信息来确定使用哪个库拷贝。如果对库的更新较少，我们可以不更新版本号；而对主要的更新则提高版本号。这样，只有用新版本库编译的程序不可以使用旧版本库。（Thus, only programs that are compiled with the new library version are affected by the incompatible changes incorporated in it.）其它程序在新库安装之前继续使用旧库。这种系统被称为共享库（shared library）。
与动态装入不同，动态链接通常需要操作系统的支持。如果内存中的进程受到保护（9.3节），那么只有操作系统才能够检查所需的程序是否位于另一个进程的内存空间中；或者说只有操作系统才可以允许多个进程访问同样的内存地址空间。当我们在9.4.5节讨论分页机制时将详细讨论这个概念。
9.1.5 覆盖
为了允许一个进程大于它所获得的内存容量，我们可以使用覆盖（overlay）技术。覆盖的思想是只把随时会用到的指令和数据保留在内存中。当需要其它指令时，把这些指令装入不再需要的指令所占用的内存空间中。
例如：考虑一个两遍汇编程序（two-pass assembler）。在第一遍中构建一个符号表；然后，在第二遍中产生机器语言代码（machine-language code）。我们可以把这样的一个汇编程序分为四个部分：第一遍的代码、第二遍的代码、符号表和第一遍和第二遍所需的共同支持程序。假设这些组件的大小如下：
第一遍的代码 70 KB
第二遍的代码 80 KB
符号表 20 KB
共同支持程序 30 KB
要一次性装入所有组件，我们需要200KB内存。如果只有150KB内存可用，那么我们就不能执行这个程序。然而，注意到第一遍和第二遍不需要同时在内存中。因此，我们定义两个overlays：Overlay A是符号表、共同程序和第一遍代码，Overlay B是符号表、共同程序和第二遍代码。
我们在内存中增加一个overlay驱动程序（10KB）并以Overlay A开始。当第一遍结束的时候，我们跳到overlay驱动程序（overlay driver），它把Overlay B读取到内存中，覆盖Overlay A，并将控制移交给第二遍。Overlay A只需要120KB，而Overlay B需要130KB（图9.3）。我们可以在150KB内存中运行这个汇编程序。它的装入稍微的快了一些，因为在执行之前需要的数据少了一些。然而，由于在Overlay A之后读取Overlay B的代码需要额外的I/O操作，所以它将运行的慢一些。
Overlay A和Overlay B的代码作为绝对内存映象（absolute memory image）保留在磁盘中，在需要的时候由Overlay驱动器读取。构建overlays需要专门的重定位和链接算法。
利用动态装入，overlays无需专门的操作系统支持。可完全由用户实现：利用简单的文件结构，从内存中读取文件，然后跳转到内存并执行新的读取指令。（They can be implemented completely by the user with simple file structures, reading from the files into memory and then jumping to that memory and executing the newly read instructions.）操作系统只会注意到I/O操作比平常多了一些。
另一方面，程序员必须完全设计并对overlay结构编程。这个任务可不轻松，需要完全掌握程序结构、编码和数据结构。因为根据定义程序很大（小程序无需使用overlays），完全理解程序可能会非常困难。为此，overlays的使用通常限于微型计算机和其它物理内存有限而且缺乏支持更高级技术的硬件的系统中。有些微型计算机编译程序为程序员提供了对overlays的支持。当然，可以自动在有限的内存中执行大程序的技术是最好的。
图 9.3 对两遍汇编程序的Overlays
完整内容请见 http://www.tulipsys.com
