内存管理

内存由很大一组字或字节组成，每个字或字节都有自己的地址。CPU根据程序计数器（PC）的值从内存中提取指令，这些指令可能会引起进一步对特定内存地址的读取和写入。

背景

基本硬件

CPU所能直接访问的存储器只有内存和处理器内的寄存器。机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。CPU内置寄存器通常可以在一个CPU时间周期内完成访问。对于寄存器中的内容，绝大多数CPU可以在一个时间周期内解析并执行一个或多个指令，而对于内存（其访问通过内存总线上的事物进行）就不行了。完成内存访问需要多个CPU时间周期，由于没有数据以便完成正在执行的指令，CPU通常需要暂停，CPU通常需要暂停。由于内存访问频繁，这种情况是难以忍受的。解决方法是在CPU与内存之间，增加高速内存。这种协调速度差异的内存缓存区，称为高速缓存（cache）。首先需要确定每个进程都有独立的内存空间，为此需要确定进程可以反问的合法地址的范围，并确保进程只访问其合法地址。

通过两个寄存器即基地址寄存器和界限地址寄存器，可以实现这种保护。基地址寄存器（base register）含有最小的合法物理内存地址，而界限地址寄存器（limit register）决定了范围的大小。例如，如果基地址寄存器为300040，而界限寄存器位120900，那么程序可以合法访问从300040到420940（含）的所有地址。

内存空间保护的实现，是通过CPU硬件对用户模式所产生的每一个地址与寄存器的地址进行比较来完成的。如果用户模式下执行的程序试图访问操作系统内存或其他用户内存，则会陷入到操作系统，并作为致命错误处理。如下

这种方案防止用户程序（有意或无意地）修改操作系统或其他用户的代码或数据结构。

只有操作系统可以通过特殊的特权指令来加载基地址寄存器和界限地址寄存器。由于特权指令只可在内核模式下执行，而只有操作系统在内核模式下执行，所以只有操作系统可以加载基地址寄存器和界限地址寄存器。这种方案允许操作系统修改这两个寄存器的值，而不允许用户程序修改它们。操作系统在内核模式下执行，可以无限制地访问操作系统和用户的内存。因此操作系统可以将用户程序装入用户内存，在出错时输出这些程序，访问并修改系统调用的参数等。

地址绑定

通常，程序以二进制可执行文件的形式存储在磁盘上。为了执行，程序被调入内存并放在进程空间内。根据所使用的内存管理方案，进程在执行时可以在磁盘和内存之间移动。在磁盘上等待调入内存以便执行的进程形成输入队列（input queue）。

通常的步骤是从输入队列中选取一个进程并装入内存。进程在执行时，会访问内存中的指令和数据。最后，进程终止，其地址空间将释放。

许多系统允许用户进程放在物理内存的任意位置。因此，虽然计算机的地址空间从00000开始，但用户进程的开始地址不必也是000000。这种组织方式会影响用户程序能够使用的地址空间。绝大多数情况下，用户程序执行前，需要经过好几个步骤

在这些步骤中，地址可能有不同的表现形式。源程序中的地址通常是用符号来表示（如count）。编译器通常将这些符号地址绑定（bind）在可重定位的地址（如"从本模块开始的第14个字节"）。链接程序或加载程序再将这些可重定位的地址绑定成绝对地址（如74014）。每次绑定都是从一个地址空间到另一个地址空间的映射。

通常将指令与数据绑定到内存地址有以下几种情况

编译时（complike time）：如果在编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码（absolute code）。例如，如果事先就知道用户进程驻留在内存地址R处，那么所生成的编译代码就可以从该位置开始并向后扩展。如果将来开始地址发生改变，那么就必须重新编译代码。MS-DOS的.COM格式程序就是在编译时绑定成绝对代码的。

加载时（load time）：如果在编译时并不知道进程将驻留在内存的什么地方，那么编译器就必须生成可重定位代码（relocatable code）。对于这种情况，最后绑定会延迟到加载时才进行。如果开始地址发生变化，只需重新加载用户代码以引入改变值。

执行时（execution time）:如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才进行。

逻辑地址空间与物理地址空间

CPU所生成的地址通常称为逻辑地址（logical address），而内存单元所看到的地址（即加载到内存寄存器（memory-address register）中的地址）通常称为物理地址（physical address）。

编译和加载时的地址绑定方法生成相同的逻辑地址和物理地址。但是，执行时的地址绑定方案导致不同的逻辑地址和物理地址。对于这种情况，通常称逻辑地址为虚拟地址(virtual address)。逻辑地址和虚拟地址不作区分。由程序所生成的所有逻辑地址的集合称为逻辑地址空间（logical address space），与这些逻辑地址相对应的所有物理地址的集合称为物理地址空间（physical address space）。

运行时从虚拟地址到物理地址的映射是由被称为内存管理单元（memory-management unit,MMU）的硬件设备来完成的。下图用一个简单的MMU方案来实现这种映射，基地址寄存器在这里称为重定位寄存器（relocation register）。用户进程所生成的地址在送交内存之前，都将加上重定位寄存器的值。

逻辑地址（范围0到max）和物理地址(范围为R+0到R+max，其中R为基地址)。用户只生成逻辑地址，且认为进程的地址空间为0到max。用户提供逻辑地址，这些地址在使用前必须映射到物理地址。

动态加载

迄今为止所讨论的是一个进程的整个程序和数据必须处于物理内存中，以便执行。因此进程的大小受物理内存大小的限制。为了获得更好的内存空间使用率，可以使用动态加载（dynamic loading）。采用动态加载时，一个子程序只有在调用后时才被加载。所有子程序都以可重定位的形式保存在磁盘上。主程序装入内存并执行。当一个子程序需要调用另一个子程序时，调用子程序首先检查另一个子程序是否已加载。如果没有，可重定位的链接程序将用来加载所需要的子程序，并更新程序的地址表以反映这一变化。接着，控制传递给新加载的子程序。

动态加载的优点是不用的子程序绝不会被加载。

动态链接与共享库

动态链接库（dynamically linked library）,有的操作系统只支持静态链接（static linking）,此时系统语言库的处理与其他目标模块一样，由加载程序合并到二进制程序镜像中。动态链接的概念与动态加载相似。只是这里不是将加载延迟到运行时，而是将链接延迟到运行时。

二进制镜像中对每个库程序的引用都有一个存根（stub）。存根是一小段代码，用来指出如和定位适当的内存驻留库程序，或如果该程序不再内存时如何装入内存。不管怎么样存根会用子程序地址来替换自己，并开始执行子程序。

交换

进程需要在内存中以便执行。不过，进程可以暂时从内存中交换（swap）到备份存储（backing store）上，当需要再次执行时再调回到内存中。

在优先级调度中，如果有一个更高优先级的进程需要服务，内存管理器可以交换出低优先级的进程，以便可以装入和执行更高优先级的进程。当更高优先级的进程执行完后，低优先级进程可以交换回内存以继续执行。这种交换有时称为滚入（roll in）和滚出（roll out）。

一般一个交换出的进程需要交换回它原来所占有的内存空间。这一限制是由地址绑定方式决定的。如果绑定是在汇编时或加载时所定的，那么就不可以移动到不同的位置。如果绑定在运行时才确定，由于物理地址是在运行时才确定的，那么进程可以移动到不同的地址空间。

系统有一个就绪队列，它包括在备份存储或在内存中准备运行的所有进程。当CPU调度程序决定执行进程时，它调用调度程序。调度程序检查队列中的下一个进程是否在内存中。如果不在内存中且没有空闲内存空间，调度程序将一个已在内存中的进程交换出去，并换入所需要的进程。然后，它重新转载寄存器，并将控制转交给所选择的进程。

由于需要对主存和备份存储之间进行转移，所以交换系统的上下文切换时间比较长。总的转移时间与所交换的内存空间总量成正比。因此，知道一个用户进程所真正需要的内存空间，而不是其可能所需要的内存空间，是非常有用的。为了有效使用这种方法，用户需要告诉系统其内存需求情况。因此，具有动态内存需求的进程要通过系统调用（请求内存和释放内存）来通知操作系统其内存需求变化的情况。

交换也受其他因素所限制。如果交换进程必须确保该进程完全处于空闲状态。特备是对于I/O操作。有两种解决方法来处理I/O异步访问的问题，一是不能换出有待处理I/O的进程，二是I/O操作的执行只能使用操作系统缓冲区，仅当换入进程后，才执行操作系统缓冲与进程内存之间的数据转移。

连续内存分配

内存必须容纳操作系统和各种用户进程，因此应该尽可能有效地分配内存的各个部分。

内存通常分为两个区域：一个用于驻留操作系统，另一个用于用户进程。操作系统可以位于低内存，也可位于高内存。影响这一决定的主要因素是中断向量的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统也放在低内存。

通常需要将多个进程同时放入到内存中，因此需要考虑如何为输入队列中需要调入内存的进程分配内存空间。采用连续内存分配（contiguous memory allocation）时，每个进程位于一个连续的内存区域。

内存映射与保护

在讨论内存分配前，必须先讨论内存映射与保护问题。通过采用重定位寄存器含有最小的物理地址值：界限地址寄存器含有逻辑地址的范围（例如，重定位=100040，界限=74600）。有了重定位寄存器和界限地址寄存器，每个逻辑地址必须小于界限地址寄存器。MMU动态地将逻辑地址加上重定位寄存器的值后映射成物理地址。映射后的物理地址再送交内存单元。

当CPU调度器选择一个进程来执行时，作为上下文切换工作的一部分，调度程序会用正确的值来初始化重定位寄存器和界限地址寄存器。由于CPU所产生的每一个地址都需要与寄存器进行核对，所以可以保证操作系统和其他用户程序不受该进程的运行所影响

重定位寄存器机制为允许操作系统动态改变提供了一个有效方法。许多情况都需要这一灵活性。例如，操作系统的驱动程序需要代码和缓冲空间。如果某驱动程序（或其他操作系统服务）不常使用，可以不必再内存中保留该代码和数据，这部分空间可以用于其他目的。这类代码有时称为暂停（transient）操作系统代码；它们根据需要调入或调出。因此，使用这种代码可以在程序执行时动态改变操作系统的大小。

内存

分配

最为简单的内存分配方法之一就是将内存分为多个固定大小的分区（partition）。每个分区只能容纳一个进程。多道程序的程度会受分区数所限制。如果使用这种多分区方法（multiple-partition method）,当一个分区空闲时，可以从输入队列中选择一个进程，以调入到空闲分区。当进程终止时，其分区可以被其他进程所使用。

在可变分区（variabl-partition）方案里，操作系统有一个表，用于记录哪些内存可用和那些内存已被占用。一开始，所有内存都可用于用户进程，因此可以作为一大块可用内存，称为孔（hole）。当有新进程需要内存时，为该进程查找足够大的孔。如果找到，可以从该孔为该进程分配所需的内存，孔内未分配的内存可以下次再用。

随着进程进入系统，它们被加入到输入队列。操作系统根据所有进程的内存需要和现有可用内存情况来决定哪些进程可分配内存，当进程分配到空间时，它就被装入内存，并开始竞争CPU。当进程终止时，它将释放内存，该内存可以被操作系统分配给输入队列中的其他进程。

在任意时候，有一组可用孔（块）大小列表和输入队列。操作系统根据调度算法来对输入队列进行排序。内存不断地分配给进程，直到下一个进程的内存需求不能满足为止，这时没有足够大的可用孔来装入进程。操作系统可以等到有足够大的空间，或者往下扫描输入队列以确定是否有其他内存需求较小的进程可以被满足。

通常，一组不同大小的孔分散在内存中。当新进程需要内存时，系统为该进程查找足够大的孔。如果孔太大，那么久分为两块：一块分配给新进程，另一块还回到孔集合。当进程终止时，它将释放其内存，该内存将还给孔集合。如果新孔与其他孔相邻，那么将这些孔合并成打孔。这时，系统可以检查是否有进程在等待内存空间，新合并的内存空间是否满足等待进程。

这种方法是通用动态内存分配问题的一种情况（根据一组空闲孔来分配大小为n的请求）。这个问题有许多解决方法。从一组可用孔中选择一个空闲孔的最为常用方法有首次适应（first-fit）、最佳适应（best-fit）、最差适应（worst-fit）。

首次适应：分配第一个足够大的孔。查找可以从头开始，也可以从上次首次适应结束时开始。一旦找到足够大的空闲孔，就可以停止。

最佳适应：分配最小的足够大的孔。必须查找整个列表，除非列表按大小排序。这种方法可以产生最小剩余孔。

最差适应：分配最大的孔。该孔可能比最佳适应方法产生的较小剩余孔更为有用。

碎片

首次适应方法和最佳适应方法算法都有外部碎片问题（external fragmentation）。随着进程装入和移除内存，空闲内存空间被分为小片段。当所有总的可用内存之和可以满足请求，但并不连续时，这就会出现了外部碎片问题。

内存碎片可以是内部的，也可以是外部的。维护一个小孔的开销要比孔本身大得多。因此，通常将内存以固定大小的块为单元（而不是字节）来分配。采用这种方案，进程所分配的内存可能比所要的要打。这两个数字之差称为内部碎片，这部分内存在分区内，但又不能使用。

一种解决外部碎片问题的方法是紧缩（compaction）。紧缩的目的是移动内存内容，以便所有空闲空间合并成一整块。紧缩仅在重定位是动态并在运行时可采用。

另一种可能解决外部碎片问题的方法是允许物理地址空间为非连续，这样只要有物理内存就可为进程分配。这种方案有两种互补的实现技术：分页和分段。这两种技术也可合并。

分页

分页（paging）内存管理方案允许进程的物理地址空间可以是非连续的。分页避免了将不同大小的内存块匹配到交换空间上这样的麻烦。传统上，分页支持一直是由硬件来处理。然而，最近的设计师通过将硬件和操作系统相配合来实现分页。

基本方法

实现分页的基本方法涉及将物理内存分为固定大小的块，称为帧（frame）;而将逻辑内存也分为同样大小的块，称为页（page）。当需要执行进程时，其页从备份存储中调入到可用的内存帧中。备份存储也分为固定大小的块，其大小与内存帧一样。

分页硬件支持如图所示。由CPU生成的每个地址分为两个部分：页号(p)和页偏移(d)。页号作为页表中的索引。页表包含页内所在物理内存的基地址，这些基地址与页偏移的组合就形成了物理地址，就可送交物理单元。内存的页模型如下图

页大小（与帧大小一样）是由硬件来决定的。页的大小通常为2的幂，根据计算机结构的不同，其每页大小从512B~16MB不等。选择页的大小为2的幂可以方便地将逻辑地址转换为页号也页偏移。如果逻辑地址空间为2^m，且页大小为2^n单元（字节或字），那么逻辑地址的高m-n位表示页号，而低n位表示页偏移。这样，逻辑地址如下所示：

其中P作为页表的索引，而d作为页的偏移。

一个分页的例子如下：

分页也是一种动态重定位。每个逻辑地址由分页硬件绑定为一定的物理地址。采用分页类似于使用一组基（重定位）地址寄存器，每个基地址对应着一个内存帧。

采用分页不会产生外部碎片：每个帧都可以分配给需要它的进程。不过，分页有内部碎片。注意分配是以帧为单元进行的。如果进程需要求的内存并不是页的整数倍，那么最后一个帧就可能用不完。

每个页表的条目通常为4B，不过这是可变的。一个32位的条目可以指向2^23个物理帧中的任一个。如果帧为4KB，那么具有4B条目的系统可以访问2^44B大小（或16TB）的物理内存。

当系统进程需要执行时，它将检查该进程的大小（按页来计算），进程的每页都需要一帧。因此，如果进程需要n页，那么内存中至少应有n个帧。如果有，那么久可分配给新进程。进程的第一页装入一个已分配的帧，帧号放入进程的页表中。下一页分配给另一帧，其帧号也放入进程的页表中等。

由于操作系统管理物理内存，它必须知道物理内存的分配细节：哪些帧已占用，哪些帧可用，总共有多少帧，等等。这些信息通常保存在称为帧表的数据结构中。在帧表（frame table）中，每个条目对应着一个帧，以表示该帧是空闲还是已占用，如果占用，是被那个进程的哪个页所占用。

另外，操作系统必须意识到用户进程是在用户空间内执行，且所有逻辑地址必须映射到物理地址。如果用户执行一个系统调用（例如进行I/O），并提供地址作为参数（如一个缓冲），那么这个地址必须映射成物理地址。操作系统为每个进程维护一个页表的副本，就如同它需要维护指令计数器和寄存器的内容一样。当操作系统必须手工将逻辑地址映射成物理地址时，这个副本可用来将逻辑地址转化为物理地址。当一个进程可分配到CPU时，CPU调度程序可以根据该副本定义硬件页表。因此，分页增加了切换时间。

硬件支持

每个操作都有自己的方法来保存页表。绝大多数都为每个进程分配一个页表。页表的指针与其他寄存器的值（如指令计数器）一起存入进程控制块中。当调度程序需启动一个进程时，它必须首先装入用户寄存器，并根据所保存的用户页表来定义正确的硬件页表值。

页表的硬件实现方式有很多种方法。最为简单的一种方法是将页表作为一组专用寄存器（regiser）来实现。这些寄存器应用高速逻辑电路来构造，以便有效地进行分页地址的转换。CPU调度程序在装入其他寄存器时，也需要装入这些寄存器。装入或修改页表寄存器的指令是特权级的，因此只有操作系才可以修改内存映射图。

如果页表比较小（例如256个条目），那么页表使用寄存器还是比较合理的。但是，绝大多数当代计算机都允许页表非常大（如1百万个条目）。对于这些机器，采用快速寄存器来实现页表就不可行了。因而需要将页表放在内存中，并将页表基寄存器（page-table base register,PTBR）指向页表。改变页表只需要改变这一寄存器就可以，这也大大降低了切换时间。

采用这种方法的问题是访问用户内存位置要一些时间。如果要访问位置i，那么必须先用PTBR中的值再加上页号i的偏移，来查找页表。这一任务需要内存访问。根据所得的帧号，再加上页偏移，就得到了真实物理地址。接着就可以访问内存中所需的位置。采用这种方案，访问一个字节需要两次内存访问(一次用于页表条目，一次用于字节)。这样，内存访问的速度就减半。

对于这一问题的标准解决方案是采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲区（translation look-aside buffer,TLB）。TLB是关联的快速内存。TLB条目由两部分组成：键（标签）和值。当内联内存根据给定值查找时，它会同时与所有键进行比较。如果找到条目，那么就得到相应的值域。这种查找方式比较快，不过硬件也比较昂贵。通常，TLB的条目数并不多，通常在64~1024之间。

TLB与页表一起按如下方法使用：TLB只包括页表中的一小部分条目。当CPU产生逻辑地址后，其页号提交给TLB。如果找到页号，那么也就的得到了帧号，并可用来访问内存。整个任务与不采用内存映射相比，其时间增加不会超过10%。

如果页码不在TLB（称为TLB失效），那么就需要访问页表。当得到帧号后，就可以用它来访问内存。同时，将页号和帧号增加到TLB中，这样下次再用时就可很快查找到。如果TLB中的条目已满，那么操作系统会选择一个来替换。替换策略有很多，从最近最少使用替换（LRU）到随机替换等。另外，有的TLB允许有些条目固定下来，也就是它们不会从TLB中替换。通常内核代码的条目是固定下来的。

保护

在分页环境下，内存保护是通过与每个帧关联的保护位来实现的。通常，这些保护存在页表中。

可以用一个位来定义一个页是可读写还是只读的。可以创建硬件以提供只读、读写、只执行保护。或者，通过为每种访问情况提供独立保护位。还有一个位通常与页表中的每一条目相关联：有效-无效位。当该位为有效时，表示相关的页在进程的逻辑地址空间内，因此是合法（或有效）的页。当该位为无效时，表示相关的页不在进程的逻辑地址空间内。通过使用有效-无效位可以捕捉到非法的地址。操作系统通过对该位的设置可以允许或不允许对某页的访问。

有些系统提供硬件如页表长度寄存器（page-table lengthregister,PTLR）来表示页表的大小。该寄存器的值可用于检查每个逻辑地址以验证其是否位于进程的有效范围内。如果检测无法通过，会被操作系统捕获到。

共享页

分页的优点之一在于可以共享公共代码，这种考虑对分时环境特别重要。考虑一个支持40个用户的系统，每个用户都执行一个文本编辑器。如果文本呢编辑器包括150KB的代码及50KB的数据空间，则需要8000KB来只支持这40个用户。如果代码是可重入代码（reentrant code,纯代码），则可以共享。在此将看到3个页的编辑器----每页50KB大小------在3个进程间共享。每个进程都有它自己的数据页。如下所示

可重入代码是不能自我修改的代，它从不会再执行期间改变。因此，两个或更多的进程可以在相同的时间执行相同的代码。每个进程都有它自己的寄存器副本和数据存储，以控制进程执行的数据。当然，两个不同的进程的数据也将不同。

页表结构

层次页表

绝大多数现代计算机系统支持大逻辑地址空间（2^32-2^64）。这个问题的一个简单解决方法是将页表划分为更小部分。

哈希页表

处理超过32位地址空间的常用方法是使用哈希页表（hashed page table）,并以虚拟页码作为哈希值。哈希页表的每一条目都包括一个链表的元素，这些元素哈希成同一位置（要处理碰撞）。每个元素有3个域：（1）虚拟页码，（2）所映射的帧号，（3）指向链表中下一个元素的指针。

该算法按如下方式工作：虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的每一个元素的第一个域相比较。如果匹配，那么相应的帧号（第二个域）就用来形成物理地址；如果不匹配，那么就对链表的下一个节点进行比较，以寻找一个匹配的页号。

反向页表

通常，每个进程都有一个相关的页表。该进程所使用的每个页都在页表中的一项（或者每个虚拟地址都有一项，不管后者是否有效）。这种页的表示方式比较自然，这是因为进程是通过页的虚拟地址来引用页的。操作系统必须将这种引用转换成物理内存地址。由于页表是按虚拟地址排序的，操作系统能够计算出所对应条目在页表中的位置，并可以直接使用该值。这种方法的缺点之一是每个页表可能有很多项。这些表可能消耗大量物理内存，却仅用来跟踪物理内存是如何使用的。

为了解决这个问题，可以使用反向页表（inverted page table）。反向页表对于每个真正的内存页或帧才有一个条目。每个条目保存在真正内存位置的页的虚拟地址以及拥有该页的进程的信息。因此，整个系统只有一个页表，对每个物理内存的页只有一条相应的条目。因为系统只有一个页表，而有多个地址空间映射物理内存，所以反向页表的条目通常需要一个地址空间标识符以确保一个特定进程的一个逻辑页可以映射到相应的物理帧。

虽然这种方案减少了存储每个页表所需要的内存空间，但是当引用页时，它增加了查找页表所需要的时间。为了解决这一问题，可以使用哈希页表来将查找限制在一个或少数几个页表条目。当然，每次访问哈希页表也为整个过程增加了一次内存引用，因此一次虚拟地址引用至少需要两个内存读：一个查找哈希页表条目，另一个查找页表。为了改善性能，可以在访问哈希页表时先查找TLB。

采用反向页表的系统在实现共享内存时存在困难。解决该问题的一个简单方法是允许页表仅包含一个虚拟地址到共享物理地址的映射，这意味着对未被映射的虚拟地址的引用将导致页错误。

分段

采用分页内存管理有一个不可避免的问题：用户视角的内存和实际物理内存的分离。前面已经看到，用户视角的内存与实际物理内存不一样。用户视角的内存需要映射到实际物理内存，该映射允许区分逻辑内存和物理内存。

基本方法

用户通常愿意将内存看做是一组不同长度的段的集合，这些段之间并没有一定的顺序，而不是将内存看作是一个线性字节数组。

分段（segmentation）就是支持这种用户视角的内存管理方案。逻辑地址空间是由一组段来组成的。每个段都有名称和长度。地址指令了段名称和段内偏移。因此用户通过两个量来指定地址：段名称和偏移。为了实现简单起见，段是编号的，是通过段号而不是段名来引用的。因此，逻辑地址由有序对组成：

通常，在编译用户程序时，编译器会自动根据输入程序来构造段。

一个C编译器可能会创建如下段：

代码
全局变量
堆
栈
标准的C库函数

在编译时链接的库可能被分配不同的段。加载程序会装入所有这些段，并为它们分配段号。

硬件

虽然用户现在能够通过二维地址来引用程序中的对象，但是实际物理内存仍然是一维序列的字节。因此，必须定义一个实现方式，以便将二维的用户定义地址映射为一维物理地址。这个地址是通过段表（segment table）来实现的。段表的每个条目都有段基地址和段界限。段基地址包含该段在内存中的开始物理地址，而段界限指定该段的长度。

小结

用于多道程序设计的操作系统的内存管理算法，包括从简单的单用户系统方法到分页分段方法。一个特定系统所采用方法的最大决定因素是硬件所提供的支持。CPU所产生的每个内存地址都必须进行合法性检查，才可映射成为物理地址。检查是不能通过软件实现，因此实现受到可用硬件的限制。

不同的内存管理算法（连续分配，分页，分段，以及分页与分段结合）在许多方面都呈现出不同的特点。在比较不同内存管理策略时，需要考虑如下几点：

硬件支持:对于单分区和多分区方案，只需要一个基地址寄存器和一对基地址和界限寄存器就够了；而对于分页和分段，需要映射表以定义地址映射。

性能：随着内存管理算法变得越来越复杂，逻辑地址到物理地址的映射所需要的时间也有所增加。对于简单系统，只需要对逻辑地址进行比较和加减操作（这些较为简单）。如果表能通过快速寄存器来加以实现，那么分页和分段操作也会很快。不过，如果表在内存中，那么用户内存访问速度就大大降低。TLB可以用来改善性能。

碎片：如果多道程序的级别更高，那么多道程序系统通常会更有效地执行。对于给定的一组进程，可以通过将更多进程装入内存以增加多道程序的程度。为了完成这一任务，必须降低内存浪费或碎片。采用固定大小分配单元（如单个分区和分页）的系统会有内部碎片问题。采用可变大小分配单元（如多个分区和分段）的系统会有外部碎片问题。

重定位：外部碎片问题的解决方案之一是紧缩。紧缩涉及在内存中移动程序而不影响程序。这种方案要求在执行时逻辑地址能动态地进行重定位。如果地址只能在装入时进行重定位，那么久不能采用紧缩。

交换：任何算法都可加上交换操作。进程可以定时地（由操作系统来定，通常由CPU调度策略来决定）从内存交换到外存，之后再交换到内存。这种方法能允许更多进程运行，但它们不能同时装入内存。

共享：另一个增加多道程序程度的方法是让不同用户共享代码和数据。共享通常要求分页或分段，以便共享较小的信息区域（如页或段）。共享在有限内存情况下能运行许多进程，但是共享的程序和数据需要仔细设计。

保护：如果提供了分页和分段，那么用户程序的不同区域可以声明为只可执行，只读或可读写。这种限制对于共享代码和数据是必要的，对于常见程序设计错误能提供简单的运行时检查。