内存管理策略
前言
- 由于CPU调度，我们可以提高CPU的利用率和计算机响应用户的速度。然而，为了实现性能的改进，应将多个进程保存在内存中;也就是说,必须共享内存。
背景
- 内存是现代计算机运行的核心。内存由一个很大的字节数组来组成,每个字节都有各自的地址。CPU根据程序计数器的值从内存中提取指令，这些指令可能引起对特定内存地址的额外加载与存储。
基本硬件
CPU可以直接访问的通用存储只有内存和处理器内置的寄存器。机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。因此，执行指令以及指令使用的数据，应处在这些可直接访问的存储设备上。如果数据不在内存中，那么在CPU使用它们之前应先把数据移到内存。
CPU内置寄存器通常可以在一个CPU时钟周期内完成访问。对于寄存器的内容，大多数CPU可以在一个时钟周期内解释并执行一条或多条指令。而对于内存(它可通过内存总线的事务来访问)，访问可能需要多个CPU时钟周期。在这种情况下，由于没有数据以便完成正在执行的指令，CPU通常需要暂停( stall)。由于内存访问的频繁，这种情况是无法容忍的。补救措施是在CPU与内存之间，通常是在CPU芯片上，增加更快的内存;这称为高速缓存( cache)。为管理CPU内置的缓存，硬件自动加快内存访问，无需任何操作系统的控制。
首先，我们需要确保每个进程都有一个单独的内存空间。单独的进程内存空间可以保护进程而不互相影响，这对于将多个进程加到内存以便并发执行来说至关重要。为了分开内存空间，我们需要能够确定一个进程可以访问的合法地址的范围;并且确保该进程只能访问这些合法地址。通过两个寄存器，通常为基地址和界限地址，基地址寄存器base register)含有最小的合法的物理内存地址,而界限地址寄存器（ limit register)指定了范围的大小。例如，如果基地址寄存器为300040而界限寄存器为120900，那么程序可以合法访问从300040到420939(含)的所有地址。
内存空间保护的实现是通过CPU硬件对在用户模式下产生的地址与寄存器的地址进行比较来完成的。当在用户模式下执行的程序试图访问操作系统内存或其他用户内存时，会陷入操作系统,而操作系统则将它作为致命错误来处理。这种方案防止用户程序无意或故意修改操作系统或其他用户的代码或数据结构。
只有操作系统可以通过特殊的特权指令，才能加载基地址寄存器和界限地址寄存器。由于特权指令只能在内核模式下执行，而只有操作系统才能在内核模式下执行，所以只有操作系统可以加载基地址寄存器和界限地址寄存器。这种方案允许操作系统修改这两个寄存器的值,而不允许用户程序修改它们。
在内核模式下执行的操作系统可以无限制地访问操作系统及用户的内存。这项规定允许操作系统:加载用户程序到用户内存，转储出现错误的程序，访问和修改系统调用的参数，执行用户内存的IO，以及提供许多其他服务等。
地址绑定
概念
通常，程序作为二进制的可执行文件，存放在磁盘上。为了执行，程序应被调入内存,并放在进程中。根据采用的内存管理，进程在执行时可以在磁盘和内存之间移动。在磁盘上等待调到内存以便执行的进程形成了输入队列(input queue)。
正常的单任务处理过程是:从输入队列中选取一个进程并加载到内存;进程在执行时，会访问内存的指令和数据;最后，进程终止时，它的内存空间将会释放。
源程序中的地址通常是用符号表示(如变量count)。编译器通常将这些符号地址绑定( bind)到可重定位的地址。链接程序或加载程序再将这些可重定位的地址绑定到绝对地址(如74014)。每次绑定都是从一个地址空间到另一个地址空间的映射。
通常，指令和数据绑定到存储器地址可在沿途的任何一步中进行:
- 编译时（ compile time):如果在编译时就已知道进程将在内存中的驻留地址,那么就可以生成绝对代码（ absolute code)。如果将来开始地址发生变化，那么就有必要重新编译代码。MS-DOS的.COM格式的程序就是在编译时绑定成绝对代码的。
- 加载时( load time):如果在编译时并不知道进程将驻留在何处，那么编译器就应生成可重定位代码( relocatable code)。对这种情况，最后绑定会延迟到加载时才进行。如果开始地址发生变化，那么只需重新加载用户代码以合并更改的值。
- 执行时( runtime time):如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定应延迟到执行时才进行。采用这种方案需要特定硬件才行。大多数的通用计算机操作系统采用这种方法。
逻辑地址空间和物理地址空间
CPU生成的地址通常称为逻辑地址(logical address)，而内存单元看到的地址(即加载到内存地址寄存器(memory-address register)的地址)通常称为物理地址(physical address)。
编译时和加载时的地址绑定方法生成相同的逻辑地址和物理地址。然而，执行时的地址绑定方案生成不同的逻辑地址和物理地址。在这种情况下，我们通常称逻辑地址为虚拟地址( virtual address)。由程序所生成的所有逻辑地址的集合称为逻辑地址空间( logical address space)，这些逻辑地址对应的所有物理地址的集合称为物理地址空间( physical address space)。因此，对于执行时地址绑定方案，逻辑地址空间与物理地址空间是不同的。
从虚拟地址到物理地址的运行时映射是由内存管理单元(Memory-Management Unit,MMU)的硬件设备来完成。基地址寄存器这里称为重定位寄存器( relocation register)。用户进程所生成的地址在送交内存之前，都将加上重定位寄存器的值。
用户程序处理逻辑地址，内存映射硬件将逻辑地址转变为物理地址。所引用的内存地址只有在引用时才最后定位。我们现在有两种不同类型的地址:逻辑地址(范围为0 ～max)和物理地址(范围为R＋0～R + max，其中R为基地址的值)。用户只生成逻辑地址，且以为进程的地址空间为0 ~ max。然而，这些逻辑地址在使用之前应映射到物理地址。逻辑地址空间绑定到另一单独物理地址空间的这一概念对内存的管理至关重要。
动态加载
- 一个进程的整个程序和所有数据都应在物理内存中，以便执行。因此，进程的大小受限于内存的大小。为了获得更好的内存空间利用率，可以使用动态加载( dynamic loading)。采用动态加载时，一个程序只有在调用时才会加载。所有程序都以可重定位加载格式保存在磁盘上。主程序被加载到内存，并执行。当一个程序需要调用另一个程序时，调用程序首先检查另一个程序是否已加载。如果没有，可重定位链接程序会加载所需的程序到内存，并更新程序的地址表以反映这一变化。接着，控制传递给新加载的程序。
- 动态加载的优点是，只有一个程序被需要时，它才会被加载。可能虽然整个程序可能很大,但是所用的（和加载的)部分可能很小。
- 动态加载不需要操作系统提供特别支持。用户的责任是，设计他们的程序利用这种方法的优点。然而，操作系统可以通过实现动态加载的程序库来帮助程序员。
动态链接与共享库
- 动态链接库( dynamically linked library)为系统库，可链接到用户程序，以便运行。有的操作系统只支持静态链接（static linking)，它的系统库与其他目标模块一样，通过加载程序，被合并到二进制程序映像。动态链接类似于动态加载。这里，不是加载而是链接，会延迟到运行时。这种功能通常用于系统库，如语言的子程序库。没有这种功能，系统内的所有程序都需要一份语言库的副本(或至少那些被程序所引用的子程序)。这种要求浪费了磁盘空间和内存空间。
- 如果有动态链接，在二进制映像内，每个库程序的引用都有一个存根(stub)。存根是一小段代码，用来指出如何定位适当的内存驻留库程序，或者在程序不在内存内时应如何加载库。当执行存根时，它首先检查所需程序是否已在内存中。如果不在，就将程序加到内存。不管如何，存根会用程序地址来替换自己，并开始执行程序。因此，下次再执行该程序代码时，就可以直接进行，而不会因动态链接产生任何开销。采用这种方案，使用语言库的所有进程只需要一个库代码副本就可以了。
- 动态链接也可用于库的更新。一个库可以被新的版本所替代，而且使用该库的所有程序会自动使用新的版本。没有动态链接，所有这些程序应当重新链接以便访问新的库。这种系统也称为共享库(shared library )。
- 与动态加载不同，动态链接通常需要操作系统的帮助。如果内存中的进程是彼此保护的，那么只有操作系统才可以检查所需程序是否在某个进程的内存空间内，或是允许多个进程访问同样的内存地址。
交换
描述
- 进程必须在内存中以便执行。不过,进程可以暂时从内存交换( swap)到备份存储( backing store)，当再次执行时再调回到内存中。交换有可能让所有进程的总的物理地址空间超过真实系统的物理地址空间,从而增加了系统的多道程序程度。
标准交换
- 标准交换在内存与备份存储之间移动进程。备份存储通常是快速磁盘。它应足够大,以容纳所有用户的所有内存映像的副本;并且它应提供对这些存储器映像的直接访问。系统维护一个可运行的所有进程的就绪队列( ready queue)，它们的映像在备份存储或内存中。当CPU调度器决定要执行一个进程时，它调用分派器。分派器检查队列中的下一个进程是否在内存中。如果不在，并且没有空闲内存区域，那么分派器会换出 (swap out)当前位于内存中的一个进程，并换入( swap in)所需进程。然后，重新加载寄存器，并且将控制权转移到所选进程。
- 这种交换系统的上下文切换时间相当高。
- 请注意，交换时间的主要部分是传输时间。总的传输时间与交换的内存大小成正比。
- 交换也受到其他因素的约束。如果我们想要换出一个进程，那么应确保该进程是完全处于空闲的。特别关注的是任何等待IO。当需要换出一个进程以释放内存时，该进程可能正在等待I/O操作。如果我们需要换出进程P1而换入进程P2，那么I/О操作可能试图使用现在已属于进程P2的内存。解决这个问题有两种主要方法:一是不能换出等待处理I/O的进程，二是I/O操作的执行只能使用操作系统的缓冲。只有在进程换入时，操作系统缓冲与进程内存之间才能进行数据转移。注意，这种双缓冲（double buffering)本身增加了开销。我们现在需要再次复制数据，从内核内存到用户内存，然后用户进程可以访问它。
- 现代操作系统现在并不使用标准交换。它的交换时间太多，它提供的执行时间太少，不是合理的内存管理的解决方案。一个常用的变种是:正常情况下，禁止交换;当空闲内存(未被操作系统或进程使用的内存)低于某个阈值时，启用交换。当空闲内存的数量增加了，就停止交换。另一变种是交换进程的部分(而不是整个进程)，以降低交换时间。通常，这些交换的变种通常与虚拟内存一起工作。
连续分配内存
前言
- 内存通常分为两个区域:一个用于驻留操作系统，另一个用于用户进程。操作系统可以放在低内存，也可放在高内存。影响这一决定的主要因素是中断向量的位置。由于中断向量通常位于低内存，因此程序员通常将操作系统也放在低内存。
- 在采用连续内存分配( contiguous memory allocation)时,每个进程位于一个连续的内存区域，与包含下一个进程的内存相连。
内存保护
- 重定位寄存器含有最小的物理地址值;界限寄存器含有逻辑地址的范围值（例如，重定位=100040，界限=74600 )。每个逻辑地址应在界限寄存器规定的范围内。MMU通过动态地将逻辑地址加上重定位寄存器的值，来进行映射。映射后的地址再发送到内存。
- 当CPU调度器选择一个进程来执行时，作为上下文切换工作的一部分，分派器会用正确的值来加载重定位寄存器和界限寄存器。由于CPU所产生的每个地址都需要与这些寄存器进行核对，所以可以保证操作系统和其他用户的程序和数据不受该运行进程的影响。
内存分配
最为简单的内存分配方法之一，就是将内存分为多个固定大小的分区( partition)。每个分区可以只包含一个进程。因此，多道程序的程度受限于分区数。如果使用这种多分区方法( multiple-partition method)，那么当一个分区空闲时，可以从输人队列中选择一个进程，以调入空闲分区。当该进程终止时，它的分区可以用于其他进程。这种方法最初为IBM OS/360操作系统(称为MFT)所使用，现在已不再使用。下面所描述的方法是固定分区方案的推广(称为MVT)，它主要用于批处理环境。
对于可变分区( variable-partition)方案，操作系统有一个表，用于记录哪些内存可用和哪些内存已用。开始，所有内存都可用于用户进程，因此可以作为一大块的可用内存，称为孔(hole)。内存有一个集合，以包含各种大小的孔。
随着进程进入系统，它们将被加人输入队列。操作系统根据所有进程的内存需求和现有可用内存的情况，决定哪些进程可分配内存。当进程分配到空间时，它就加载到内存，并开始竞争CPU。当进程终止时，它将释放内存，该内存可以被操作系统分配给输入队列内的其他进程。
任何时候，都有一个可用块大小的列表和一个输入队列。操作系统根据调度算法来对输入队列进行排序。内存不断地分配给进程，直到下一个进程的内存需求不能满足为止，这时没有足够大的可用块(或孔)来加载进程。操作系统可以等到有足够大的空间，或者可以往下扫描输人队列，以确定是否有其他内存需求较小的进程可以被满足。
通常，可用的内存块为分散在内存里的不同大小的孔的集合。当新进程需要内存时，系统为该进程查找足够大的孔。如果孔太大，那么就分为两块:一块分配给新进程，另一块还回到孔集合。当进程终止时，它将释放内存，该内存将还给孔的集合。如果新孔与其他孔相邻，那么将这些孔合并成大孔。这时，系统可以检查:是否有进程在等待内存空间，以及新合并的内存空间是否满足等待进程等。
动态存储分配问题(dynamic storage-allocation problem)从一组可用孔中选择一个空闲孔的方法包括:首次适应(first-fit)、最优适应(best-fit)及最差适应（worst-fit)。
- 首次适应:分配首个足够大的孔。查找可以从头开始（首次适应），也可以从上次首次适应（下次适应）结束时开始。一旦找到足够大的空闲孔,就可以停止。
- 最优适应:分配最小的足够大的孔。这种方法可以产生最小剩余孔。（空间最优，时间多）
- 最差适应:分配最大的孔。这种方法可以产生最大剩余孔，但是该空的剩余空间大，可可重用性大。（空间时间均不优）
首次适应和最优适应在执行时间和利用空间方面都好于最差适应。首次适应和最优适应在利用空间方面难分伯仲,但是首次适应要更快些。
碎片
- 用于内存分配的首次适应和最优适应算法都有外部碎片( external fragmentation)的问题。随着进程加载到内存和从内存退出，空闲内存空间被分为小的片段。当总的可用内存之和可以满足请求但并不连续时，这就出现了外部碎片问题:存储被分成了大量的小孔。
- 内存碎片可以是内部的，也可以是外部的。按固定大小的块为单位(而不是字节)来分配内存。采用这种方案，进程所分配的内存可能比所需的要大。这两个数字之差称为内部碎片(internal fragmentation)，这部分内存在分区内部，但又不能用。
- 外部碎片问题的一种解决方法是紧缩( compaction)。它的目的是移动内存内容，以便将所有空闲空间合并成一整块。然而，紧缩并非总是可能的。如果重定位是静态的，并且在汇编时或加载时进行的，那么就不能紧缩。只有重定位是动态的（换入与换出后的地址可以不同），并且在运行时进行的，才可采用紧缩。最简单的合并算法是简单地将所有进程移到内存的一端，而将所有的孔移到内存的另一端，从而生成一个大的空闲块。这种方案比较昂贵。
- 外部碎片化问题的另一个可能的解决方案是:允许进程的逻辑地址空间是不连续的;这样，只要有物理内存可用，就允许为进程分配内存。有两种互补的技术可以实现这个解决方案:分段和分页。这两个技术也可以组合起来。
分段
基本方法
- 当编写程序时,程序员认为它是由主程序加上一组方法、过程或函数所构成的。每个模块或数据元素通过名称来引用。程序员会说“堆栈”、“数学库”和“主程序”等，而并不关心这些元素所在内存的位置。这些段的长度是不同的，,其长度是由这些段在程序中的目的决定的。段内的元素是通过它们距段首的偏移来指定。
- 分段( segmentation)就是支持这种用户视图的内存管理方案。逻辑地址空间是由一组段构成。每个段都有名称和长度。地址指定了段名称和段内偏移。因此用户通过两个量来指定地址:段名称和段偏移。
- 为了实现简单起见，段是编号的，是通过段号而不是段名称来引用。因此，逻辑地址由有序对(two tuple）组成:<段号，偏移>
分段硬件
- 我们应定义一个实现方式，以便映射用户定义的二维地址到一维物理地址。这个地址是通过段表（( segment table)来实现的。段表的每个条目都有段基地址( segment base)和段界限( segment limit)。段基地址包含该段在内存中的开始物理地址，而段界限指定该段的长度。
- 每个逻辑地址由两部分组成:段号s和段偏移d。段号用作段表的索引，逻辑地址的偏移d应位于0和段界限之间。如果不是这样，那么会陷入操作系统中(逻辑地址试图访问段的外面)。如果偏移d合法，那么就与基地址相加而得到所需字节的物理内存地址。因此，段表实际上是基址寄存器值和界限寄存器值的对的数组。
分页
前言
- 分段允许进程的物理地址空间是非连续的。分页( paging)避免了外部碎片和紧缩，而分段不可以。分页也避免了将不同大小的内存块匹配到交换空间的麻烦问题。
基本方法
- 实现分页的基本方法涉及将物理内存分为固定大小的块，称为帧或页帧(frame);而将逻辑内存也分为同样大小的块，称为页或页面（ page)。当需要执行一个进程时，它的页从文件系统或备份存储等源处，加载到内存的可用帧。备份存储划分为固定大小的块，它与单个内存帧或与多个内存帧(簇)的大小一样。
- 由CPU生成的每个地址分为两部分:页码（ pagenumber)(p)和页偏移(page offset)(d)。页码作为页表的索引。页表包含每页所在物理内存的基地址。这个基地址与页偏移的组合就形成了物理内存地址，可发送到物理单元。
页大小(与帧大小一样)是由硬件来决定的。页的大小为2的幂，将页的大小选为2的幂可以方便地将逻辑地址转换为页码和页偏移。如果逻辑地址空间为2^m，且页大小为2 ^n字节，那么逻辑地址的高m-n位表示页码，而低n位表示页偏移。其中p作为页表的索引，而d作为页的偏移。都是从零开始计数。
采用分页方案不会产生外部碎片:每个空闲帧都可以分配给需要它的进程。不过,分页有内部碎片。注意,分配是以帧为单位进行的。如果进程所要求的内存并不是页的整数倍,那么最后一个帧就可能用不完。在最坏情况下，一个需要n页再加1字节的进程，需要分配n+1个帧,这样几乎产生整个帧的内部碎片。
如果进程大小与页大小无关，那么每个进程的内部碎片的均值为半页。从这个角度来看，小的页面大小是可取的。不过，由于页表内的每项也有一定的开销，该开销随着页的增大而降低。再者，磁盘I/O操作随着传输量的增大也会更为有效。一般来说，随着时间的推移，页的大小也随着进程、数据和内存的不断增大而增大。研究人员正在研究，以便支持快速可变的页大小。
硬件支持
- 页表的硬件实现有多种方法。最为简单的一种方法是，将页表作为一组专用的寄存器来实现。由于每次访问内存都要经过分页映射，因此效率是一个重要的考虑因素。CPU分派器在加载其他寄存器时，也需要加载这些寄存器。当然，加载或修改页表寄存器的指令是特权的，因此只有操作系统才可以修改内存映射表。
- 如果页表比较小，那么页表使用寄存器还是令人满意的。大多数现代计算机都允许页表非常大，采用快速寄存器来实现页表就不可行了。因而需要将页表放在内存中，并将页表基地址寄存器（Page-TableBase Register，PTBR)指向页表。改变页表只需要改变这一寄存器就可以，这也大大降低了上下文切换的时间。
- 采用这种方法的问题是访问用户内存位置的所需时间。如果需要访问位置i，那么应首先利用PTBR的值，再加上i的页码作为偏移，来查找页表。这一任务需要内存访问。根据所得的帧码，再加上页偏移，就得到了真实物理地址。接着就可以访问内存内的所需位置。采用这种方案，访问一个字节需要两次内存访问(一次用于页表条目，一次用于字节)。这样，内存访问的速度就减半。在大多数情况下，这种延迟是无法忍受的。我们还不如采用交换机制!
- 这个问题的标准解决方案是采用专用的、小的、查找快速的高速硬件缓冲，它称为转换表缓冲区（Translation Look-aside Buffer，TLB)。TLB是关联的高速内存。TLB条目由两部分组成:键(标签）和值。当关联内存根据给定值查找时，它会同时与所有的键进行比较。如果找到条目，那么就得到相应值的字段。搜索速度很快;有些CPU采用分开的指令和数据地址的TLB。这可以将TLB条目的数量扩大一倍，因为查找可以是并行的。
- TLB与页表一起使用的方法如下:TLB只包含少数的页表条目。当CPU产生一个逻辑地址后，它的页码就发送到TLB。如果找到这个页码，它的帧码也就立即可用，可用于访问内存。如果页码不在TLB中(称为TLB未命中(TLB miss))，那么就需访问页表。取决于CPU，这可能由硬件自动处理或通过操作系统的中断来处理。当得到帧码后，就可以用它来访问内存。另外，将页码和帧码添加到TLB，这样下次再用时就可很快查找到。如果TLB内的条目已满，那么会选择一个来替换。替换策略有很多，从最近最少使用替换（LRU)，到轮转替换，到随机替换等。通常，重要内核代码的条目是固定下来的。
- 在TLB中查找到感兴趣页码的次数的百分比称为命中率( hit ratio)。需要根据概率来进行加权:有效访问时间=（访问内存时间 + 访问页表TLB时间）* 命中率 +（访问内存时间 * 2 + 访问TLB时间）*（1 - 命中率）
保护
- 分页环境下的内存保护是通过与每个帧关联的保护位来实现的。通常，这些位保存在页表中。
- 用一个位可以定义一个页是可读可写或只可读。每次内存引用都要通过页表，来查找正确的帧码;在计算物理地址的同时，可以通过检查保护位来验证有没有对只可读页进行写操作。对只读页进行写操作会向操作系统产生硬件陷阱或内存保护冲突)。
- 我们可以创建硬件来提供只读、读写或只执行保护;或者，通过为每种类型的访问提供单独的保护位，我们可以允许这些访问的任何组合。非法访问会陷入操作系统。
- 还有一个位通常与页表中的每一条目相关联:有效-无效位(valid-invalid bit)。当该位为有效时，该值表示相关的页在进程的逻辑地址空间内，因此是合法(或有效)的页。当该位为无效时，该值表示相关的页不在进程的逻辑地址空间内。通过使用有效–无效位，非法地址会被捕捉到。操作系统通过对该位的设置，可以允许或不允许对某页的访问。
共享页
- 分页的优点之一是可以共享公共代码。如果代码是可重入代码( reentrant code)或纯代码（ pure code)，则可以共享。
- 可重入代码是不能自我修改的代码:它在执行期间不会改变。因此，两个或更多个进程可以同时执行相同代码。每个进程都有它自己的寄存器副本和数据存储，以便保存进程执行的数据。共享代码映射到同一物理地址，私有代码映射到不同地址。
页表结构
- 组织页表的一些最常用技术：包括分层分页、哈希页表和倒置页表。
分层分页
- 大多数现代计算机系统支持大逻辑地址空间。在这种情况下，页表本身可以非常大。例如，假设具有32位逻辑地址空间的一个计算机系统。如果系统的页大小为4KB ( 2^12)，那么页表可以多达100万的条目(2^32/2^12 )。假设每个条目有4字节，那么每个进程需要4MB物理地址空间来存储页表本身。显然，我们并不想在内存中连续地分配这个页表。这个问题的一个简单解决方法是将页表划分为更小的块。完成这种划分有多个方法。
- 一种方法是使用两层分页算法，就是将页表再分页。例如，再次假设一个系统，具有32位逻辑地址空间和4K大小的页。一个逻辑地址被分为20位的页码和12位的页偏移。因为要对页表进行再分页，所以该页码可分为10位的页码和10位的页偏移。这样，一个逻辑地址就分为如下形式:
- 其中p1是用来访问外部页表的索引，而p2是内部页表的页偏移。由于地址转换由外向内，这种方案也称为向前映射页表( forward-mapped page table)。
- 为了转换每个逻辑地址，64位的UltraSPARC将需要7个级别的分页，如此多的内存访问是不可取的。
哈希页表
- 处理大于32位地址空间的常用方法是使用哈希页表(hashed page table)，采用虚拟页码作为哈希值。哈希页表的每一个条目都包括一个链表，该链表的元素哈希到同一位置(该链表用来解决处理碰撞)。每个元素由三个字段组成:1)虚拟页码，2)映射的帧码，3）指向链表内下一个元素的指针。
- 该算法工作如下:虚拟地址的虚拟页码哈希到哈希表。用虚拟页码与链表内的第一个元素的第一个字段相比较。如果匹配，那么相应的帧码(第二个字段)就用来形成物理地址;如果不匹配，那么与链表内的后续节点的第一个字段进行比较，以查找匹配的页码。
倒置页表
- 通常，每个进程都有一个关联的页表。该进程所使用的每个页都在页表中有一项(或者每个虚拟页都有一项，不管后者是否有效)。这种方法的缺点之一是，每个页表可能包含数以百万计的条目。这些表可能需要大量的物理内存，以跟踪其他物理内存是如何使用的。
- 为了解决这个问题，我们可以使用倒置页表( inverted page table)。对于每个真正的内存页或帧，倒置页表才有一个条目。每个条目包含保存在真正内存位置上的页的虚拟地址，以及拥有该页进程的信息。因此，整个系统只有一个页表，并且每个物理内存的页只有一条相应的条目。由于一个倒置页表通常包含多个不同的映射物理内存的地址空间，通常要求它的每个条目保存一个地址空间标识符。地址空间标识符的保存确保了，具体进程的每个逻辑页可映射到相应的物理帧。
为了说明这种方法，这里描述一种用于IBM RT的倒置页表的简化版本。系统内的每个虚拟地址为一个三元组:
- 〈进程id，页码，偏移〉
每个倒置页表条目为二元组〈进程id，页码)，这里进程 id用来作为地址空间的标识符。当发生内存引用时，由〈进程id，页码〉组成的虚拟地址被提交到内存子系统。然后，搜索倒置页表来寻找匹配。如果找到匹配条目，如条目i，则生成物理地址〈i，偏移〉。如果找不到匹配，则为非法地址访问。
虽然这种方案减少了存储每个页表所需的内存空间，但是它增加了由于引用页而查找页表所需的时间。由于倒置页表是按物理地址来排序的，而查找是根据虚拟地址的，因此查找匹配可能需要搜索整个表。
采用倒置页表的系统在实现共享内存时会有困难。共享内存的通常实现为，将多个虚拟地址(共享内存的每个进程都有一个虚拟地址）映射到一个物理地址。这种标准的方法不能用于倒置页表，因为每个物理页只有一个虚拟页条目，一个物理页不可能有两个(或多个)共享的虚拟地址。解决这个问题的一个简单技术是，只允许页表包含一个虚拟地址到共享物理地址的映射。这意味着，对未映射的虚拟地址的引用会导致页错误。