操作系统之内存管理

操作系统的内存管理分为物理内存管理和虚拟内存管理。

物理内存管理包括程序装入等概念、交换技术、连续分配管理方式和非连续分配管理方式（分页、分段、段页式）。

虚拟内存管理包括虚拟内存概念、请求分页管理方式、页面置换算法、页面分配策略、工作集和抖动。

我们以计算机存储结构来开始探讨。

计算机存储体系

内存是计算机很重要的一个资源，因为程序只有被加载到内存中才可以运行；此外，CPU 所需要的指令与数据也都是来自内存的。可以说，内存是影响计算机性能的一个很重要的因素。

分层存储器体系

在介绍内存管理的细节前，先要了解一下分层存储器体系：

大部分的计算机都有一个存储器层次结构，即少量的非常快速、昂贵、易变的高速缓存 (cache)；若干兆字节的中等速度、中等价格、易变的主存储器 (RAM)；数百兆或数千兆的低速、廉价、不易变的磁盘。这些资源的合理使用与否直接关系着系统的效率。

CPU 缓存（Cache Memory）：是位于 CPU 与内存之间的临时存储器，它的容量比内存小的多但是交换速度却比内存要快得多。缓存的出现主要是为了解决 CPU 运算速度与内存 读写速度不匹配的矛盾，因为 CPU 运算速度要比内存读写速度快很多，这样会使 CPU 花费很长时间等待数据到来或把数据写入内存。

计算机是一种数据处理设备，它由 CPU 和内存以及外部设备组成。CPU 负责数据处理，内存负责存储，外部设备负责数据的输入和输出，它们之间通过总线连接在一起。CPU 内部主要由控制器、运算器和寄存器组成。控制器负责指令的读取和调度，运算器负责指令的运算执行，寄存器负责数据的存储，它们之间通过 CPU 内的总线连接在一起。每个外部设备 (例如：显示器、硬盘、键盘、鼠标、网卡等等) 则是由外设控制器、I/O 端口、和输入输出硬件组成。外设控制器负责设备的控制和操作，I/O 端口负责数据的临时存储，输入输出硬件则负责具体的输入输出，它们间也通过外部设备内的总线连接在一起。

上面计算机系统结构图中我们可以看出硬件系统的这种组件化的设计思路总是贯彻到各个环节。

在冯诺伊曼设计体系中：总是有一部分负责控制、一部分负责执行、一部分则负责存储，它之间进行交互以及接口通信则总是通过总线来完成 。这种设计思路一样的可以应用在我们的软件设计体系里面：组件和组件之间通信通过事件的方式来进行解耦处理，而一个组件内部同样也需要明确好各个部分的职责 (一部分负责调度控制、一部分负责执行实现、一部分负责数据存储)。

计算存储的层次结构

当前技术没有能够提供这样的存储器，因此大部分的计算机都有一个存储器层次结构:

高速缓存 (cache): 少量的非常快速、昂贵、易变的高速缓存 (cache)；

主存储器 (RAM): 若干兆字节的中等速度、中等价格、易变的主存储器 (RAM)；

磁盘：数百兆或数千兆的低速、廉价、不易变的磁盘。

这些资源的合理使用与否直接关系着系统的效率。

内存使用演化

没有内存抽象

在早些的操作系统中，并没有引入内存抽象的概念。 程序直接访问和操作的都是物理内存 ，内存的管理也非常简单，除去操作系统所用的内存之外，全部给用户程序使用，想怎么折腾都行，只要别超出最大的容量。比如当执行如下指令时：mov reg1,1000

1、无内存抽象存在的问题：

这条指令会毫无想象力的将物理地址 1000 中的内容赋值给寄存器。不难想象，这种内存操作方式使得操作系统中存在多进程变得完全不可能，比如 MS-DOS，你必须执行完一条指令后才能接着执行下一条。如果是多进程的话，由于直接操作物理内存地址，当一个进程给内存地址 1000 赋值后，另一个进程也同样给内存地址赋值，那么第二个进程对内存的赋值会覆盖第一个进程所赋的值，这回造成两条进程同时崩溃。

带来两个问题：

1. 用户程序可以访问任意内存，容易破坏操作系统，造成崩溃
2. 同时运行多个程序特别困难

随着计算机技术发展，要求操作系统支持多进程的需求，所谓多进程，并不需要同时运行这些进程，只要它们都处于 ready 状态，操作系统快速地在它们之间切换，就能达到同时运行的假象。每个进程都需要内存，Context Switch 时，之前内存里的内容怎么办？简单粗暴的方式就是先 dump 到磁盘上，然后再从磁盘上 restore 之前 dump 的内容（如果有的话），但效果并不好，太慢了！

内存抽象：地址空间

那怎么才能不慢呢？把进程对应的内存依旧留在物理内存中，需要的时候就切换到特定的区域。这就涉及到了内存的保护机制，毕竟进程之间可以随意读取、写入内容就乱套了，非常不安全。因此操作系统需要对物理内存做一层抽象，也就是「地址空间」(Address Space)，一个进程的地址空间包含了该进程所有相关内存，比如 code /stack/heap。一个 16 KB 的地址空间可能长这样：

当程序运行时，heap 和 stack 共用中间 free 的区域，当然这只是 OS 层面的抽象。比如下面这段代码：

int x;
x = x + 3; //this is the line of code we are interested in

变成汇编指令后，大概是这样：

128: movl 0x0 (% ebx), % eax  ;load 0+ebx into eax
132: addl $0x03, % eax ;add 3 to eax register
135: movl % eax, 0x0 (% ebx) ;store eax back to mem

最前面的是 PC (Program Counter)，用来表示当前 code 的索引，比如 CPU 执行到 128 时，进行了 Context Switch（上下文切换），那么在 Switch 回来后，还可以接着从 132 开始执行（当然需要先把 PC 存起来）。之后的就是汇编代码，告诉 CPU 该如何操作。

从进程的角度看，内存可能是这样的：

基址寄存器与界限寄存器可以简单的动态重定位： 每个内存地址送到内存之前，都会自动加上基址寄存器的内容。

从 32KB 处作为开始，48KB 作为结束。那 32 / 48 可不可以动态设置呢，只要在 CPU 上整两个寄存器， 基址寄存器 base 和 界限寄存器 bounds 就可以了，base 指明从哪里开始，bounds 指定哪里是边界。 因此真实物理地址和虚拟地址之间的关系是：

因此真实物理地址和虚拟地址之间的关系是：

physical address = virtual address + base

有时，CPU 上用来做内存地址翻译的也会被叫做「内存管理单元 MMU」(Memory Management Unit)，随着功能越来越强大，MMU 也会变得越来越复杂。

base and bounds 这种做法最大的问题在于空间浪费，Stack 和 Heap 中间有一块 free space，即使没有用，也被占着，那如何才能解放这块区域呢，进入虚拟内存。

虚拟内存

虚拟内存是现代操作系统普遍使用的一种技术。前面所讲的 抽象满足了多进程的要求，但很多情况下，现有内存无法满足仅仅一个大进程的内存要求 。物理内存不够用的情况下，如何解决呢？

覆盖 overlays： 在早期的操作系统曾使用覆盖技术来解决这个问题，将一个程序分为多个块，基本思想是先将块 0 加入内存，块 0 执行完后，将块 1 加入内存。依次往复，这个解决方案最大的问题是需要程序员去程序进行分块，这是一个费时费力让人痛苦不堪的过程。后来这个解决方案的修正版就是虚拟内存。

交换 swapping： 可以将暂时不能执行的程序（进程）送到外存中，从而获得空闲内存空间来装入新程序（进程），或读入保存在外存中而处于就绪状态的程序。

虚拟内存： 虚拟内存的基本思想是，每个进程有用独立的逻辑地址空间，内存被分为大小相等的多个块，称为 页 (Page). 每个页都是一段连续的地址。对于进程来看，逻辑上貌似有很多内存空间，其中 一部分对应物理内存上的一块 (称为页框，通常页和页框大小相等)，还有一些没加载在内存中的对应在硬盘上。

物理内存分配方式

物理内存分配分为连续内存分配管理和非连续内存分配管理，其中非连续内存分配分为页式、段式和段页式。

连续内存分配管理

连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。

单一连续存储管理

在这种管理方式中，内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CP／M 和 DOS 2．0 以下就是采用此种方式。这种方式的最大优点就是易于管理。但也存在着一些问题和不足之处，例如对要求内存空间少的程序，造成内存浪费；程序全部装入，使得很少使用的程序部分也占用 — 定数量的内存。

分区式存储管理

为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。

分区式存储管理引入了两个新的问题：内碎片和外碎片。内碎片是占用分区内未被利用的空间，外碎片是占用分区之间难以利用的空闲分区 (通常是小空闲分区)。

为实现分区式存储管理，操作系统应维护的数据结构为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态 (是否已分配)。

分区式存储管理常采用的一项技术就是 内存紧缩 (compaction)。

固定分区

固定式分区的特点是把内存划分为若干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个相同程序的并发执行 (处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。

优点 ：易于实现，开销小。

缺点 ：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目

动态分区

动态分区的特点是动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。与固定分区相比较其优点是：没有内碎片。但它却引入了另一种碎片 —— 外碎片。动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为 “占用”，而另一个分区为余下部分并标记为 “空闲”。分区分配的先后次序通常是从内存低端到高端。动态分区的分区释放过程中有一个要注意的问题是，将相邻的空闲分区合并成一个大的空闲分区。

下面列出了几种常用的分区分配算法：

最先适配法 (nrst-fit)： 按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。

下次适配法 (循环首次适应算法 next fit)： 按分区在内存的先后次序，从上次分配的分区起查找 (到最后 {区时再从头开始}，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大空闲分区不易保留。

最佳适配法 (best-fit)： 按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配。从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保留。

最坏适配法 (worst- fit)： 按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，当对内存需求较大的进程需要运行时，其要求不易被满足。

伙伴系统

固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。
伙伴系统规定，无论已分配分区或空闲分区，其大小均为 $2^k$，$k$ 为整数， $l≤k≤m$，其中：

$2^l$ 表示分配的最小分区的大小，

$2^m$ 表示分配的最大分区的大小，

通常 $2^m$ 是整个可分配内存的大小。
假设系统的可利用空间容量为 $2^m$ 个字， 则系统开始运行时， 整个内存区是一个大小为 $2^m$ 的空闲分区。在系统运行过中， 由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了 $k (0≤k≤m)$ 个空闲分区链表。

分配步骤

当需要为进程分配一个长度为 $n$ 的存储空间时:

首先计算一个 $i$ 值，使 $2^{i－1} <n ≤ 2^i$，

然后在空闲分区大小为 $2^i$ 的空闲分区链表中查找。

若找到，即把该空闲分区分配给进程。

否则，表明长度为 $2^i$ 的空闲分区已经耗尽，则在分区大小为 $2^{i＋1}$ 的空闲分区链表中寻找。

若存在 $2^{i＋1}$ 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配， 而把另一个加入分区大小为 $2^i$ 的空闲分区链表中。

若大小为 $2^{i＋1}$ 的空闲分区也不存在，则需要查找大小为 $2^{i＋2}$ 的空闲分区， 若找到则对其进行两次分割：

第一次，将其分割为大小为 $2^{i＋1}$ 的两个分区，一个用于分配，一个加入到大小为 $2^{i＋1}$ 的空闲分区链表中；

第二次，将第一次用于分配的空闲区分割为 $2^i$ 的两个分区，一个用于分配，一个加入到大小为 $2^i$ 的空闲分区链表中。

若仍然找不到，则继续查找大小为 $2^{i＋3}$ 的空闲分区，以此类推。

由此可见，在最坏的情况下，可能需要对 $2^k$ 的空闲分区进行 $k$ 次分割才能得到所需分区。

与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 $2^i$ 的空闲分区时，若事先已存在 $2^i$ 的空闲分区时，则应将其与伙伴分区合并为大小为 $2^{i＋1}$ 的空闲分区，若事先已存在 $2^{i＋1}$ 的空闲分区时，又应继续与其伙伴分区合并为大小为 $2^{i＋2}$ 的空闲分区，依此类推。

在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。 需要指出的是，在当前的操作系统中，普遍采用的是下面将要讲述的基于分页和分段机制的虚拟内存机制，该机制较伙伴算法更为合理和高效，但在多处理机系统中，伙伴系统仍不失为一种有效的内存分配和释放的方法，得到了大量的应用。

内存紧缩

内存紧缩是一种内存碎片化处理的方案。它将各个占用分区向内存一端移动，然后将各个空闲分区合并成为一个空闲分区。这种技术在提供了某种程度上的灵活性的同时，也存在着一些弊端，例如：对占用分区进行内存数据搬移占用 CPU 时间；如果对占用分区中的程序进行 “浮动”，则其重定位需要硬件支持。

紧缩时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时。

堆结构的存储管理的分配算法

在动态存储过程中，不管哪个时刻，可利用空间都是 - 一个地址连续的存储区，在编译程序中称之为 “堆”，每次分配都是从这个可利用空间中划出一块。其实现办法是：设立一个指針，称之为堆指针，始终指向堆的最低（或锻联）地址。当用户申请 N 个单位的存储块时，堆指针向高地址（或 低地址）称动 N 个存储单位，而移动之前的堆指针的值就是分配给用户的占用块的初始地址。例如，某个串处理系统中有 A、B、C、D 这 4 个串，其串值长度分别為 12, 6, 10 和 8. 假设堆指针 free 的初值为零，则分配给这 4 个串值的存储空间的初始地址分别为 0.12.18 和 28, 如图所示，分配后的堆指针的值为 36。 因此， 这种堆结构的存储管理的分配算法非常简单 ，

释放内存空间执行内存紧缩

回收用户释放的空闲块就比较麻烦。由于系统的可利用空间始终是一个绝址连续的存储块，因此回收时必须将所释放的空间块合并到整个堆上去才 能重新使用，这就是 “存储策缩” 的任务。通常，有两种做法：

一种是一旦有用户释放存储块即进行回收紧缩，例始，上图中 a 的堆，在 c 串释放存储块时即回收紧缩，例如 b 的堆，同时修改串的存储映像成 c 的状态；

另一种是在程序执行过程中不回收用户随时释放的存储块，直到可利用空同不够分配或堆指针指向最高地址时才进行存储紧缩。此时紧缩的目的是将堆中所有的空间块连成一块，即将所有的占用块部集中到 可利用空间的低地地区，而剩余的高地址区成为一整个地继连续的空闲块，如下图所示，其中（a）为紧缩前的状态，(b) 为紧缩后的状态

和无用单元收集类似，为实现存储紧编，首先要对占用块进行 “标志”，标志算法和无用单元收集类同 (存储块的结构可能不同）, 其次需进行下列 4 步雄作：

1. 计算占用块的新地址。从最低地址开始巡査整个存储空间，对每一个占用块找到它在紧缩后的新地址。 为此，需设立两个指针随巡查向前移动，这两个指针分别指示占用 块在紧缩之前和之后的原地址和新地址。因此，在每个占用块的第 -・个存储单位中，除了 设立长度域 (存储该占用换的大小）和标志域 (存储区别该存储块是占用块或空闲块的标 志）之外，还需设立一个新地址城，以存储占用块在紧缩后应有的新地址，即建立一张新， 旧地址的对照表 m
2. 修改用户触初始变量表，以便在存储紧缩后用户程序能继续正常运行。
3. 检查每个占用块中存储的数据， 若有指向其他存储换的指针，则需作相应修改。
4. 将所有占用块迁移到新地址走，这实质上是作传送数据的工作。

至此，完成了存储紧缩的操作，最后，将堆指针赋以新值（即紧缩后的空闲存储区的最低地址）。

可见，存储紧缩法比无用单元收集法更为复杂，前者不仅要传送数据（进行占用块迁移），而且还有需要修改所有占用块中的指针值。因此，存储紧缩也是个系统操作，且非不得已就不用。

覆盖技术

引入覆盖 (overlay) 技术的目标是在较小的可用内存中运行较大的程序。这种技术常用于多道程序系统之中，与分区式存储管理配合使用。

覆盖技术的原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序必要部分 (常用功能) 的代码和数据常驻内存；可选部分 (不常用功能) 平时存放在外存 (覆盖文件) 中，在需要时才装入内存。不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。

在任何时候只在内存中保留所需的指令和数据；当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的内存空间；

如在同一时刻，CPU 只能执行 B，C 中某一条。B，C 之间就可以做覆盖。

覆盖技术的缺点是编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度；从外存装入覆盖文件，以时间延长换取空间节省。

覆盖的实现方式有两种：以函数库方式实现或操作系统支持。

交换技术

交换 (swapping) 技术在多个程序并发执行时，可以将暂时不能执行的程序（进程）送到外存中，从而获得空闲内存空间来装入新程序（进程），或读入保存在外存中而处于就绪状态的程序。交换单位为整个进程的地址空间。交换技术常用于多道程序系统或小型分时系统中，因为这些系统大多采用分区存储管理方式。与分区式存储管理配合使用又称作 “对换” 或 “滚进／滚出” (roll-in／roll-out)。

原理： 暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出 swap out），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入 swap in）。

交换 技术优点之一是增加并发运行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比交换技术另一个显著的优点是不影响程序结构。交换技术本身也存在着不足，例如：对换入和换出的控制增加处理器开销；程序整个地址空间都进行对换，没有考虑执行过程中地址访问的统计特性。

与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。交换主要是在进程与作业之间进行，而覆盖则主要在同一作业或进程内进行。 另外覆盖只能覆盖那些与覆盖程序段无关的程序段。

非连续内存分配管理

在前面的几种存储管理方法中， 为进程分配的空间是连续的，使用的地址都是物理地址 。如果允许将一个进程分散到许多不连续的空间，就可以避免内存紧缩，减少碎片。基于这一思想，通过引入进程的逻辑地址，把进程地址空间与实际存储空间分离，增加存储管理的灵活性。地址空间和存储空间两个基本概念的定义如下：

地址空间：将源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。地址空间是逻辑地址的集合。

存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址存储空间是物理地址的集合。

根据分配时所采用的基本单位不同，可将离散分配的管理方式分为以下三种：

页式存储管理、段式存储管理和段页式存储管理。其中段页式存储管理是前两种结合的产物。

页式存储管理

将程序的逻辑地址空间划分为固定大小的页 (page)，而物理内存划分为同样大小的页框 (page frame)。程序加载时，可将任意一页放入内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要 CPU 的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成，前一部分是页号，后一部分为页内地址 w（位移量），如图所示：

页式管理方式的优点是：

1. 没有外碎片，每个内碎片不超过页大
2. 一个程序不必连续存放。
3. 便于改变程序占用空间的大小 (主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。

缺点 是：要求程序全部装入内存，没有足够的内存，程序就不能执行。

数据结构

在页式系统中进程建立时，操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间，如果允许进程动态地申请空间，操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能，必须记录系统内存中实际的页框使用情况。操作系统还要在进程切换时，正确地切换两个不同的进程地址空间到物理内存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能，— 个页式系统中，一般要采用如下的数据结构。

进程页表 ：完成逻辑页号 (本进程的地址空间) 到物理页面号 (实际内存空间，也叫块号) 的映射。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的 PCB 中，当该进程被调度时，就将它们装入页表寄存器。
每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序，如图

物理页面表： 整个系统有一个物理页面表，描述物理内存空间的分配使用状况，其数据结构可 采用位示图和空闲页链表 。

对于位示图法，即如果该页面已被分配，则对应比特位置 1，否置 0.

请求表： 整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换也可以结合到各进程的 PCB (进程控制块) 里。如图：

地址变换

在页式系统中，指令所给出的地址分为两部分：逻辑页号和页内地址。CPU 中的内存管理单元 (MMU) 按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内地址相加形成物理地址。逻辑页号，页内偏移地址－> 查进程页表，得物理页号－> 物理地址。

上述过程通常由处理器的硬件直接完成，不需要软件参与。通常，操作系统只需在进程切换时，把进程页表的首地址装入处理器特定的寄存器中即可。一般来说，页表存储在主存之中。这样处理器每访问一个在内存中的操作数，就要访问两次内存。

第一次用来查找页表将操作数的逻辑地址变换为物理地址；

第二次完成真正的读写操作。

这样做时间上耗费严重。为缩短查找时间，可以将页表从内存装入 CPU 内部的关联存储器 (例如，快表) 中，实现按内容查找。此时的地址变换过程是：在 CPU 给出有效地址后，由地址变换机构自动将页号送入快表，并将此页号与快表中的所有页号进行比较，而且这 种比较是同时进行的。若其中有与此相匹配的页号，表示要访问的页的页表项在快表中。于是可直接读出该页所对应的物理页号，这样就无需访问内存中的页表。由于关联存储器的访问速度比内存的访问速度快得多。

快表

如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样 CPU 存一个数据必须访问两次内存，从而使计算机的处理速度降低了 1/2。

为了提高地址变换的速度，在地址变换机构中增设了一个具有并行查询功能的特殊的高速缓冲存储器，称为 “联想存储器” 或 “快表”，用以存放当前访问的那些页表项。

其地址变换过程：

1. CPU 给出有效地址
2. 地址变换机构自动地将页号送入高速缓存，确定所需要的页是否在快表中
3. 若是，则直接读出该页所对应的物理块号，送入物理地址寄存器
4. 若快表中未找到对应的页表项，则需再访问内存中的页表
5. 找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项

两级和多级页表

主要是有的时候页表太多了，要化简。格式：外层页号 P1 + 外层页内地址 P2 + 页内地址 d

基本方法：将页表进行分页，每个页面的大小与内存物理块的大小相同，并为它们进行编号，可以离散地将各个页面分别存放在不同的物理块中。

反置页表

为每一个物理块（页框）设置一个页表项，并按物理块排序，其内容则是页号和其所属进程的标识。

段式存储管理

在段式存储管理中，将程序的地址空间划分为若干个段 (segment)，这样每个进程有一个二维的地址空间。在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在段式存储管理系统中，则为每个段分配一个连续的分区，而进程中的各个段可以不连续地存放在内存的不同分区中。程序加载时，操作系统为所有段分配其所需内存，这些段不必连续，物理内存的管理采用动态分区的管理方法。

在为某个段分配物理内存时，可以采用首先适配法、下次适配法、最佳适配法等方法。

在回收某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。

段式存储管理也需要硬件支持，实现逻辑地址到物理地址的映射。

程序通过分段划分为多个模块，如代码段、数据段、共享段：

• 可以分别编写和编译
• 可以针对不同类型的段采取不同的保护
• 可以按段为单位来进行共享，包括通过动态链接进行代码共享

这样做的优点是：可以分别编写和编译源程序的一个文件，并且可以针对不同类型的段采取不同的保护，也可以按段为单位来进行共享。

总的来说， 段式存储管理的优点是 ：没有内碎片，外碎片可以通过内存紧缩来消除；便于实现内存共享。缺点与页式存储管理的缺点相同，进程必须全部装入内存。

数据结构

为了实现段式管理，操作系统需要如下的数据结构来实现进程的地址空间到物理内存空间的映射，并跟踪物理内存的使用情况，以便在装入新的段的时候，合理地分配内存空间。

进程段表 ：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址 (baseaddress)，即段内地址。在系统中为每个进程建立一张段映射表，如图：

​

系统段表 ：系统所有占用段（已经分配的段）。

空闲段表 ：内存中所有空闲段，可以结合到系统段表中。

地址变换

​

在段式管理系统中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。为了完成进程逻辑地址到物理地址的映射，处理器会查找内存中的段表，由段号得到段的首地址，加上段内地址，得到实际的物理地址。这个过程也是由处理器的硬件直接完成的，操作系统只需在进程切换时，将进程段表的首地址装入处理器的特定寄存器当中。这个寄存器一般被称作段表地址寄存器。

页式和段式的区别

页式和段式系统有许多相似之处。比如，两者都采用离散分配方式，且都通过地址映射机构来实现地址变换。但概念上两者也有很多区别，主要表现在：

1. 需求：是信息的物理单位，分页是为了实现离散分配方式，以减少内存的碎片，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。
2. 一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。
3. 大小：页大小固定且由系统决定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的。段的长度不固定，且决定于用户所编写的程序，通常由编译系统在对源程序进行编译时根据信息的性质来划分。
4. 逻辑地址表示：页式系统地址空间是一维的，即单一的线性地址空间，程序员只需利用一个标识符，即可表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
5. 比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。

段页式存储管理

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享 。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。段页式管理就是 将程序分为多个逻辑段，在每个段里面又进行分页，即将分段和分页组合起来使用 。这样做的目的就是想同时获得分段和分页的好处，但又避免了单独分段或单独分页的缺陷。如果我们将每个段看做一个单独的程序，则逻辑分段就相当于同时加载多个程序。

数据结构

在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量，如图所示。

地址变换

为了实现地址变换，系统为每个进程建立一张段表，而每个分段有一张页表（在一个进程中，段表只有一个，而页表可能有多个）。段表表项中至少包括段号、页表长度和页表起始地址，页表表项中至少包括页号和块号。此外，系统中还应有一个段表寄存器，指出作业的段表起始地址和段表长度。

在进行地址变换时，首先通过 段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址 。如图所示，进行一次访问实际需要三次访问主存，这里同样可以使用快表以加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。

在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。