内存管理概念

引入多道程序的并发执行后，进程之间共享的不仅仅是处理机，还有主存储器。然而，共享主存会形成一些特殊的挑战。若不对内存进行管理，则易导致内存数据的混乱，以至于限制进程的并发执行。因此，为了更好地支持多道程序并发执行，必须进行内存管理。

内存管理

操作系统对内存的划分和动态分配。

内存管理主要功能

有效的内存管理在多道程序设计中非常重要，它不仅可以方便用户使用存储器、提高内存利用率，还可以通过虚拟技术从逻辑上扩充内存。

  • 内存空间的分配与回收
  • 地址转换（逻辑 → 物理）
  • 内存空间的扩充（利用虚拟存储技术在逻辑上扩充内存）
  • 内存共享（支持多进程对内存共享区域进行受控访问）
  • 存储保护（保证各个进程在各自的存储空间内运行，互不干扰）

程序的链接和装入

将用户程序变为可在内存中执行的程序的步骤

  1. 编译

    可细分为预处理、编译、汇编三个步骤，用来对每个模块（即源程序文件）生成可重定位目标文件。

  2. 链接

    由链接程序(linker)将编译后形成的一组可重定位目标文件以及它们所需要的库函数链接在一起，形成一个完整的可执行目标文件，即装入模块(load module)。

  3. 装入

    由装入程序(loader)将装入模块装入内存。

    当启动一个可执行目标文件执行时，首先会通过某种方式调出常驻内存的一个称为加载器(loader)的操作系统程序来进行处理。例如，任何 UNIX 程序的加载执行都是通过调用 execve 系统调用函数来启动加载器进行的。加载器根据可执行目标文件中的程序头表信息，将可执行目标文件中相关节的内容与虚拟地址空间中的只读代码段和可读写数据段通过页表建立映射，然后启动可执行目标文件中的第一条指令执行。

目标文件

一个目标模块就是一个字节序列，而一个目标文件就是一个以文件形式存放在磁盘中的目标模块，两个术语常常互换使用。

目标文件有三种形式：

  1. 可重定位目标文件

    包含二进制代码和数据，其形式可以在链接时与其他可重定位目标文件合并起来，创建一个可执行目标文件。

  2. 可执行目标文件

    包含二进制代码和数据，其形式可以被直接复制到内存并执行。

  3. 共享目标文件/共享库文件

    一种特殊类型的可重定位目标文件，可以在可执行文件装入或者运行时被动态地装入内存并自动被链接（该过程称为动态链接）。

编译器和汇编器生成可重定位目标文件（包括共享目标文件），链接器则将多个可重定位目标文件合成一个可执行目标文件。

可重定位目标文件和可执行目标文件都是机器语言目标文件，所不同的是前者是单个模块生成的，而后者是多个模块组合而成的。因而，对于前者，代码总是从 0 开始，而对于后者，代码在 ABI 规范规定的虚拟地址空间中产生。

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

编译后，每个模块都从 0 号开始编址，称为该目标模块的相对地址/逻辑地址。

当链接程序将各模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始编址的逻辑地址空间。

⚠注意区分编译后形成的逻辑地址和链接后形成的最终逻辑地址。

而物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址。

程序的链接

链接器的任务

链接器主要完成以下两个任务：

  1. 符号解析

    符号解析的目的是将每个符号的引用与一个确定的符号定义建立关联。

    符号包括全局静态变量名和函数名，而非静态局部变量名则不是符号。

  2. 重定位

    重定位的目的是分别合并代码和数据，并根据代码和数据在虚拟地址空间中的位置，确定每个符号的最终存储地址（虚拟地址），然后根据符号的确切地址来修改符号的引用处的地址。

    可重定位目标文件中的代码区和数据区都是从地址 0 开始的，链接器需要将不同模块中相同的节合并起来生成一个新的单独的节，并将合并后的代码区和数据区按照 ABI 规范确定的虚拟地址空间划分（也称存储器映像）来重新确定位置。

    例如，对于 32 位 Linux 系统存储器映像，其只读代码段总是从地址 0x8048000 开始，而可读可写数据段总是在代码段后面的第一个 4KB 对齐的地址处开始。因而链接器需要重新确定每条指令和每个数据的地址，并且在指令中需要明确给定所引用符号的地址，这种重新确定代码和数据的地址并更新指令中被引用符号地址的工作称为 重定位(relocation)。

使用链接的好处

  1. 模块化

    它能使一个程序被划分成多个模块，由不同的程序员进行编写，并且可以构建公共的函数库（如数学函数库、标准 I/O 函数库等）以提供给不同的程序进行重用。

  2. 效率高

    每个模块可以分开编译，在程序修改时只需重新编译那些修改过的源程序文件，然后再重新链接，因而从时间上来说能够提高程序开发的效率；

    同时，因为源程序文件中无须包含共享库的所有代码，只要直接调用即可，而且在可执行文件运行时的内存中，也只需要包含所调用函数的代码而不需要包含整个共享库，所以链接也有效地提高了空间利用率（动态链接）。

链接中的重定位

链接中的重定位的目的是在符号解析的基础上将所有关联的目标模块合并，并确定运行时每个定义符号在虚拟地址空间中的地址，在定义符号的引用处重定位引用的地址。

例如，编译器编译一个源程序文件时并不知道其中的外部调用符号指向哪个地址，所以编译器只是将一个 “临时地址” 放到可重定位目标文件中外部调用对应的 call 指令中，在链接阶段，这个 “临时地址” 将被修正为正确的引用地址，这个过程叫重定位。具体来说，重定位有以下两方面工作:

  1. 节和定义符号的重定位

    链接器将相互关联的所有可重定位文件中相同类型的节合并生成一个同一类型的新节。例如，所有模块中的 .data 节合并为一个大的 .data 节，它就是生成的可执行目标文件中的 .data 节。然后链接器根据每个新节在虚拟地址空间中的起始位置以及新节中每个定义符号的位置，为新节中的每个定义符号确定存储地址。

  2. 引用符号的重定位

    链接器对合并后新代码节（.text）和新数据节（.data）中的引用符号进行重定位，使其指向对应的定义符号起始处。为了实现这一步工作，显然，链接器要知道目标文件中哪些引用符号需要重定位、所引用的是哪个定义符号等，这些称为重定位信息，放在重定位节（.rel.text 和 .rel.data）中。

注意与装入时的重定位的区分。多数场合下说的重定位指的是装入时的重定位，即逻辑地址向物理地址的转化。

链接方式

链接分为静态链接和动态链接两种：

  • 静态链接处理的是可重定位目标文件，它将多个可重定位目标模块中相同类型的节合并起来，以生成完全链接的可执行目标文件，其中所有符号的引用都是确定的在虚拟地址空间中的最终地址，因而可以直接被加载执行；
  • 动态链接方式下的可执行目标文件是部分链接的，还有一部分符号的引用地址没有确定，需要利用共享库中定义的符号进行重定位，因而需要由动态链接器来加载共享库并重定位可执行文件中部分符号的引用。

静态链接

在程序运行之前完成链接（将各目标模块及它们所需的库函数链接成一个完成的装入模块），之后不再拆开。

动态链接

静态链接方式下，库函数代码被合并、包含在可执行文件中，会造成磁盘空间和主存空间的极大浪费。此外，程序员还需要定期维护和更新静态库，关注它是否有新版本出现，在出现新版本时需要重新对程序进行链接操作，以将静态库中最新的目标代码合并到可执行文件中。因此，静态链接方式更新困难、使用不便。

针对上述静态链接方式下的这些缺点，提出了一种共享库的动态链接方式。共享库以动态链接的方式被正在加载或执行中的多个应用程序共享，因而，共享库的动态链接有两个方面的特点：一是 “共享性”，二是 “动态性”。

  1. 共享性

    指共享库中的代码段在内存只有一个副本，当应用程序在其代码中需要引用共享库中的符号时，在引用处通过某种方式确定指向共享库中对应定义符号的地址即可。

  2. 动态性

    指共享库只在使用它的程序被加载或执行时才加载到内存，因而在共享库更新后并不需要重新对程序进行链接，每次加载或执行程序时所链接的共享库总是最新的。可以利用共享库的这个特性来实现软件分发或生成动态 Web 网页等。

动态链接有两种方式，一种是在程序加载过程中加载和链接共享库，另一种是在程序执行过程中加载和链接共享库。

装入时动态链接

将用户源程序编译后得到的一组目标模块，在装入内存时，采用边装入边链接的方式。

即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，链接完成后将其装入内存。

优点：便于修改和更新（各目标模块分开存放）；便于实现对目标模块的共享。

假定有一个 main.c 程序，其中调用了 mylib.so 中的函数 myfunc1：

1
2
3
4
5
void myfunc1(void);
int main {
    myfunc1();
    return 0;
}

为了生成可执行目标文件 myproc，可以先将 main.c 编译并汇编为可重定位目标文件 main.o，然后再将 main.o 和 mylib.so 以及标准 C 函数共享库 libc.so 进行链接。

静态链接生成的可执行目标文件在加载后可以直接运行，因为所有外部函数都已包含在可执行目标文件中，而动态链接生成的可执行目标文件在加载执行过程中需要和共享库进行动态链接，否则不能运行。这是因为在动态链接生成可执行目标文件时，其中对外部函数的引用地址是未知的。因此，在动态链接生成的可执行目标文件运行前，系统会首先将动态链接器以及所使用的共享库文件加载到内存。动态链接器和共享库文件的路径都包含在可执行目标文件中，其中，动态链接器由加载器加载，而共享库由动态链接器加载。

上图给出了动态链接的全过程。整个过程被分成两步：

  1. 首先，进行静态链接以生成部分链接的可执行目标文件 myproc，该文件中仅包含共享库（包括指定的共享目标文件 mylib.so 和默认的标准共享库文件 libc.so）中的符号表和重定位表信息，而共享库中的代码和数据并没有被合并到 myproc 中；

  2. 然后，在加载 myproc 时，由加载器将控制权转移到指定的动态链接器，由动态链接器对共享目标文件 libc.so、mylib.so 和 myproc 中的相应模块内的代码和数据进行重定位并加载共享库，以生成最终的存储空间中完全链接的可执行目标，在完成重定位和加载共享库后，动态链接器把控制权转移到程序 myproc。

在执行 myproc 的过程中，共享库中的代码和数据在存储空间的位置一直是固定的。

运行时动态链接

将对某些模块的链接推迟到程序执行中需要该目标模块时才进行。凡在程序执行中未用到的目标模块，都不会被调入内存和链接到装入模块上。

延迟绑定技术：动态链接器对共享库中外部符号的引用不在加载时进行重定位，而是延迟到第一次函数调用时进行重定位。

优点：加快装入过程；节省内存空间。

程序的装入

加载器在加载可执行目标文件时，只读代码段和可读写数据段对应的页表项都被初始化为 “未缓存页”（即有效位为 0），并指向磁盘中可执行目标文件中适当的地方。因此，程序加载过程中，实际上并没有真正从磁盘上加载代码和数据到主存，而是仅仅创建了只读代码段和可读写数据段对应的页表项。只有在执行代码过程中发生了 “缺页” 异常时，才会真正从磁盘加载代码和数据到主存（不过也有预调页策略）。

根据逻辑地址和物理地址的转换方式，程序的装入方式可分为：绝对装入、可重定位装入/静态重定位、动态运行时装入/动态重定位。

绝对装入

在编译时，若知道程序将放到内存的哪个位置，则编译程序将产生绝对地址的目标代码，即程序中的逻辑地址与物理地址完全相同。装入程序按照装入模块的绝对地址（不需进行修改或转换）将程序和数据直接装入内存。

程序中使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。通常是在程序中采用符号地址，在编译或汇编时再转换为绝对地址。

⚠使用这种方式的前提是，计算机系统很小，且仅能运行单道程序，此时完全有可能知道程序将驻留在内存的什么位置。

可重定位装入/静态重定位

根据内存的当前状况，将装入模块装入内存的适当位置，装入时进行重定位。

因为重定位通常是在进程装入时一次完成的，所以称为静态重定位。

特点：一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则无法装入。作业一旦进入内存，整个运行期间不能在内存中移动，也不能再申请内存空间。

在进程的内存分配方式中，只有单一连续分配和固定分区分配能够采用静态重定位，而其他管理方案均可能在运行过程中改变程序位置，故一般采用动态重定位。

动态运行时装入/动态重定位

地址转换推迟到程序真正执行时进行。装入模块装入内存时无需任何修改，故装入模块装入内存后所有地址仍都是逻辑地址。

可重定位方式不允许程序运行时在内存中移动位置，但在实际运行过程中程序在内存中的位置可能经常要改变，例如在具有对换功能的系统中，一个进程可能被多次换出换入，每次换入后的位置通常是不同的；又例如，在具有 “紧凑” 功能的系统中，会经常移动内存中作业的位置。在这些情况下就应采用动态运行时装入的方式。

需要一个重定位寄存器/基址寄存器的支持：用于存放装入模块在内存中的起始地址。

特点：可将程序分配到不连续的存储区；装入程序的部分代码即可投入运行，运行期间再根据需要动态申请分配内存；便于程序段的共享，可向用户提供一个比存储空间大得多的地址空间。

静态重定位/动态重定位均由可重定位装入程序完成。

内存管理部件 MMU

操作系统通过 MMU（硬件）将进程使用的逻辑地址转换为物理地址。

逻辑地址 (PC (有效地址) + 段寄存器 (段选择子)) —MMU—> MAR (物理地址)。

位置无关代码

共享库代码在磁盘上和内存中都只有一个备份，在磁盘上就是一个共享库文件，如类 UNIX 系统中的 .so 文件或 Windows 系统中的 .dll 文件。为了让一份共享库代码可以和不同的应用程序进行链接，共享库代码必须与地址无关，也就是说，在生成共享库代码时，要保证将来不管共享库代码加载到哪个位置都能够正确执行，也即共享库代码的加载位置可以是不确定的，而且共享库代码的长度发生变化也不影响调用它的程序。

满足上述这种特征的代码称为位置无关代码 PIC (Position-Independent Code)。显然，共享库文件必须是位置无关代码。

符号之间的所有引用包含以下四种情况：

  1. 模块内过程调用和跳转；
  2. 模块内数据引用；
  3. 模块间数据引用；
  4. 模块间过程调用和跳转。

对于前两种情况，因为是在模块内进行函数（过程）和数据的引用，因而采用 PC 相对偏移寻址方式就可以方便地实现位置无关代码。对于后面两种情况，由于涉及模块之间的访问所以无法通过 PC 相对偏移寻址来生成位置无关代码，需要有专门的实现机制——全局偏移量表。

对于模块间数据引用，因为任何引用符号的指令与本模块数据段起始处之间的位移量是确定的，因而，可以在数据段开始处设置一个表，只要在程序执行时外部变量的地址已记录在这个表中，那么引用外部变量的指令就可以通过访问这个表中的地址来实现对外部变量的引用。

这个设置在数据段起始处的用于存放全局变量地址的表称为全局偏移量表 COT (Global0ffsetTable)，其中每个表项对应一个全局变量，用于在动态链接时记录对应的全局变量的地址。

与块间数据引用一样，模块间过程调用也可以通过在数据段起始处增加一个全局偏移量表 COT 来解决位置无关代码的生成问题，只要在 GOT 中增加外部函数对应的表项即可。

进程的内存映像

根据 ABI 规范，特定的系统平台中的每个可执行目标文件都采用统一的存储器映像，映射到一个统一的虚拟地址空间（所谓 “统一” 是指不同的可执行文件所映射的虚拟地址空间大小一样，地址空间的区域划分结构也相同），使得链接器在重定位时可以按照一个统一的虚拟存储空间来确定每个符号的地址，而不用关心其数据和代码将来存放在主存或磁盘的何处。因此，引人统一的虚拟地址空间简化了链接器的设计和实现。

同样，引人虚拟地址空间也简化了程序加载过程。因为统一的虚拟地址空间映像使得每个可执行目标文件的只读代码段都映射到从 0x8048000 开始的一块连续区域，而可读写数据段也映射到虚拟地址空间中的一块连续区域，因而加载器可以非常容易地对这些连续区域进行分页，并初始化相应页表项的内容（IA-32 中页大小通常是 4KB，因而，这里的可装入段都按 2$^{12}$ = 4KB 对齐）。

下图是 IA-32 + Linux 系统中一个进程对应的虚拟地址空间映像：

一个进程的内存映像一般有这些要素：代码段、数据段、堆、栈、进程控制块。每个区域都有相应的起始位置。

内存保护

内存保护的内容

确保每个进程都有一个单独的内存空间。内存分配前，需要：

  • 保护操作系统不受用户进程的影响。
  • 保护用户进程不受其他用户进程的影响。

内存保护的方法

内存保护是内存管理的一部分，是操作系统的任务，但出于安全性和效率考虑，必须由硬件实现，所以需要操作系统和硬件机构的合作来完成。

内存保护可采取两种方法：

  1. 设置一对上、下限寄存器进行越界检查

    上下限寄存器存放用户作业在内存中的上下限地址，每当 CPU 要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。

  2. 采用 重定位寄存器/基址寄存器 + 界地址寄存器/限长寄存器 进行越界检查

    重定位寄存器存放的是进程的起始物理地址，界地址寄存器存放的是进程的最大逻辑地址。

    内存管理机构将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。

    ⚠访问重定位寄存器和界地址寄存器时必须使用特权指令。

页式管理中有页地址越界保护（1 次），段式管理中有段地址越界保护（2 次）。

内存共享

进程内存空间中只有只读的区域才可以共享。

在进程管理中介绍过基于共享内存的进程通信，由操作系统提供同步互斥工具。在本章后面还将介绍另一种内存共享的实现——内存映射文件。

可重入代码/纯代码

一种允许多个进程同时访问但不允许被任何进程修改的代码。

可重入程序主要是通过共享来使用同一块存储空间的，或通过动态链接的方式将所需的程序段映射到相关进程中去。

其最大的优点是减少了对程序段的调入/调出，从而减少了对换数量。

内存分配与回收

存储管理方式随着操作系统的发展而发展：

  • 在操作系统由单道向多道发展时，存储管理方式便由单一连续分配发展为固定分区分配。
  • 为了能更好地适应不同大小的程序要求，又从固定分区分配发展到动态分区分配。
  • 为了更好地提高内存利用率，进而从连续分配方式发展到离散分配方式——页式存储管理。
  • 引入分段存储管理的目的，主要是满足用户在编程和使用方面的要求，其中某些要求是其他几种存储管理方式难以满足的。

覆盖与对换*

多道程序环境下用来扩充内存的两种方法（以时间换空间）。

覆盖与对换技术现在已经很少使用。

覆盖（同一个进程）

把用户空间分成一个固定区和若干覆盖区，程序经常活跃的部分放在固定区，其余部分按调用关系分段，将那些即将要访问的段放入覆盖区，其他段放在外存中。

打破了必须将一个进程的全部信息装入主存后才能运行的限制（但当同时运行程序的代码量大于主存时仍不能运行）。

覆盖技术要求给出程序段之间的覆盖结构，对用户和程序员不透明，所以对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的，覆盖技术已成历史。

覆盖技术是早期在单一连续存储管理中使用的扩大存储容量的一种技术，它同样可用于固定分区分配的存储管理。

对换（不同进程/作业之间）

换出：把处于等待状态（阻塞/就绪）的程序从内存移到外存。

换入：把准备好竞争 CPU 运行的程序从外存移到内存。

中级调度采用的就是对换技术。

若换出进程，须确保该进程完全处于空闲状态。

正在 I/O 操作的进程不能被换出。处于临界区的进程不一定。

为了有效使用 CPU，需要使每个进程的执行时间比对换时间长。

对换需要备份存储，通常是快速磁盘，足够大，并提供对这些内存映像的直接访问。

对换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来可能很快。

对换通常在有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停。

普通的对换使用不多，但对换策略的某些变体在许多系统（如 UNIX）中仍发挥作用。

对外存对换区的管理应以提高换入、换出速度为主要目标。

连续分配管理方式

连续分配方式指为一个用户程序分配一个连续的内存空间。

单一连续分配

内存划分

内存⚠在此方式下分为系统区和用户区：

  • 系统区：仅供操作系统使用，通常在低地址部分⚠。
  • 用户区：用户区中仅有一道用户程序，即整个内存的用户空间由该程序独占。

优点

简单、无外部碎片；无须进行内存保护（因为内存中永远只有一道程序）；可采用覆盖技术；不需要额外的技术支持。

缺点

只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

固定分区分配

将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区。

分区划分方法

  1. 分区大小相等

    缺乏灵活性：程序太小会造成浪费，程序太大又无法装入。

    一般用于利用一台计算机去控制多个相同对象的场合。

  2. 分区大小不等

    划分为多个较小的分区、适量的中等分区和少量大分区。

分区说明表

为便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表（起始地址、大小、状态），分配内存时检索该表。

未找到合适分区时，拒绝为该用户程序分配内存。

优点

可用于多道程序设计的最简单的存储分配；无外部碎片。

缺点

① 程序可能太大而放不进任何一个分区；

② 存在内部碎片；

③ 不能实现多进程共享一个主存区，存储空间利用率低。

固定分区分配很少用于现在通用的操作系统中，但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用。

动态分区分配/可变分区分配

不预先划分内存，而是在进程装入内存时，动态地为该进程分配正好适合其需要的内存。因此，系统中分区的大小和数量是可变的。

空闲分区链（表）

在动态分区分配中，与固定分区分配类似，设置一张空闲分区链（表），包含空闲分区的始址和大小信息，可以按始址排序。

在分配和回收内存时都需相应修改空闲分区链。

分配内存时，检索空闲分区链，找到所需的分区，若其大小大于请求大小，则从该分区中按请求大小分割一块空间分配给装入进程（若剩余部分小到不足以划分, 则不需要分割），余下部分仍然留在空闲分区链中。

⚠回收内存时，系统根据回收分区的始址，从空闲分区链中找到相应的插入点，此时可能出现四种情况：

  1. 回收区与插入点的前一空闲分区相邻，此时将这两个分区合并，并修改前一分区表项的大小为两者之和；
  2. 回收区与插入点的后一空闲分区相邻，此时将这两个分区合并，并修改后一分区表项的始址和大小；
  3. 回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，并取消后一分区表项；
  4. 回收区没有相邻的空闲分区，此时应该为回收区新建一个表项，填写始址和大小，并插入空闲分区链。

动态分区分配算法

基于顺序搜索的分配算法

依次搜索空闲分区链上的空闲分区，以寻找一个大小满足要求的分区。

  1. 首次适应 FF (First Fit) 算法

    从低地址开始查找第一个能满足大小的空闲分区（空闲分区按地址地址的次序排列）。

    优点：① 保留了内存高地址部分的大空闲分区，有利于后续大作业的装入。② 最简单，通常也是最好和最快的。

    缺点：会使内存低地址部分出现很多小碎片，而每次分配查找时都要经过这些分区，因此增加了开销。

  2. 临近适应 NF (Next Fit) 算法 / 循环首次适应算法

    由首次适应算法演变而成，不同之处是，分配内存时从上次查找结束的位置开始继续查找。

    优点：试图解决首次适应算法的问题，它让内存中的空闲分区分布得更均匀，从而减少了查找空闲分区的开销。

    缺点：会缺乏大的空闲分区，通常比首次适应算法要差。

  3. 最佳适应 BF (Best Fit) 算法

    空闲分区会按容量增序形成分区链，从链首开始查找第一个能满足大小的空闲分区。

    优点：能更多地留下大空闲分区。

    缺点：性能通常很差，会容易产生最多的碎片，因为每次最佳的分配会留下很小的难以利用的内存块。

  4. 最坏适应 WF (Worst Fit) 算法

    空闲分区会按容量降序形成分区链，从链首开始查找第一个能满足大小的空闲分区（与最佳适应算法相反）。

    优点：使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。

    缺点：使存储器中缺乏大的空闲分区。

基于索引搜索的分配算法

当系统很大时，空闲分区链可能很长，采用顺序分配算法可能很慢，因此在大、中型系统中往往采用索引分配算法。

  1. 快速适应(quick fit)算法 / 分类搜索法

    将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。

    空闲分区的分类是根据进程常用的空间大小进行划分的，如 2KB、4KB、8KB 等，对于其它大小的分区，如 7KB 这样的空闲区既可以放在 8KB 的链表中，也可以放在一个特殊的空闲区链表中。

    该算法在搜索可分配的空闲分区时分为两步：

    1）根据进程的长度，从索引表中去寻找到能容纳它的最小空闲区链表；

    2）从链表中取下第一块进行分配。

    另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。

    优点：查找效率高。

    缺点：① 为了有效合并分区，在分区归还时的算法复杂，系统开销较大。② 该算法在分配空闲分区时，是以进程为单位的，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。这是典型的以空间换时间的做法。

  2. 伙伴系统(buddy system)

    该算法规定，无论已分配分区或空闲分区，其大小均为 2 的 $k$ 次幂（$k$ 为整数，$1 \leq k \leq m$)，通常 $2^m$ 是整个可分配内存的大小（也就是最大分区的大小）。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表，这样不同大小的空闲分区形成了 $k$ 个空闲分区链表。

    当需要为进程分配大小为 $n$ 的分区时（$2^{i-1} < n \leq 2^i$），在大小为 $2^i$ 的空闲分区链中查找。若找到，则将该空闲分区分配给进程。否则意味着大小为 $2^i$ 的空闲分区已耗尽，需要在大小为 $2^{i+1}$ 的空闲分区链中继续查找，若仍找不到，则继续查找 $2^{i+2}$，以此类推。若存在大小为 $2^{i+1}$ 的空闲分区，则将其等分为两个分区（这两个分区称为一对伙伴），其中一个用于分配，另一个加入大小为 $2^i$ 的空闲分区链。若不存在大小为 $2^{i+1}$ 的空闲分区，而存在大小为 $2^{i+2}$ 的空闲分区，则需要对其进行两次分割：第一次，将其分割为两个大小为 $2^{i+1}$ 的空闲分区，一个用于分配，另一个加入大小为 $2^{i+1}$ 的空闲分区链；第二次，将第一次用于分配的空闲区分割为两个大小为 $2^i$ 的空闲分区，一个用于分配，另一个加入大小为 $2^i$ 的空闲分区链。依此类推，在最坏情况下，可能需要对 $2^k$ 的空闲分区进行 $k$ 次分割才能得到所需分区。

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

    并非两个相邻的大小相同的分区就是一对伙伴，不然有的分区会没有伙伴。对于一个大小为 $2^k$、地址为 $x$ 的内存块，其伙伴块的地址用 $\text{buddy}_k(x)$ 表示，其通式为：

    $\text {buddy}_{k}(x)=\left{\begin{array}{ll}
    x+2^{k} (\text {若 } x \text { MOD } \left.2^{k+1}=0\right) \
    x-2^{k} (\text {若 } x \text { MOD } \left.2^{k+1}=2^{k}\right)
    \end{array}\right.$

    在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比快速适应算法差。但由于它采用了索引搜索算法，比顺序搜索算法好；而其空间性能，由于对空闲分区进行合并，减少了小的空闲分区，提高了空闲分区的可使用率，故优于快速适应算法，比顺序搜索法略差。

  3. 哈希算法

    在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，如果对空闲分区分类较细，则相应索引表的表项也就较多，因此会显著地增加搜索索引表的表项的时间开销。

    哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。

    当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。

动态可重定位分区分配

紧凑(compaction)

通过移动内存中作业的位置，把原来多个分散的空闲小分区拼接成一个大分区的方法，称为 “拼接” 或 “紧凑”。

为了提高内存的利用率，系统在运行过程中是经常需要进行 “紧凑” 的（动态分区分配方式下），每 “紧凑” 一次，就要对移动了的程序或数据的地址进行修改，因此需要采用动态重定位和动态重定位寄存器的支持，以避免对移动了的程序或数据的地址进行频繁地修改。

动态重定位分区分配算法

动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。通常，当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行 “紧凑”，将经 “紧凑” 后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。

非连续分配管理方式

基本分页存储管理方式

引入目的

固定分区会产生内部碎片，动态分区会产生外部碎片，为了内存的使用能尽量避免碎片的产生，故引入了分页的思想。

思想

内存空间分为若干固定大小的分区，称为页框(page frame)、页帧或物理块；进程的逻辑地址空间也分为与页框大小相等的若干区域，称为页或页面。

操作系统以页框为单位为各个进程分配内存空间。

分页 vs 固定分区

相同：不会产生外部碎片。

不同：

  • 页相对分区要小很多。
  • 进程也按照页进行划分。
  • 进程运行时按页申请主存可用空间并执行。
  • 一个进程可占据多页且不需要连续。
  • 只有进程申请的最后一个页框时才会出现内部碎片。平均每个进程只产生半页大小的内部碎片，也称页内碎片。

优点

页表简单，调入方便。

缺点

最后一页存在页内碎片；页不是逻辑上独立的实体，所以处理、保护和共享不及段式方便。

逻辑地址结构

页号和页内偏移量对用户透明。

这里每页大小 $2^{12}$ B = 4KB，最多允许 $2^{20}$ = 2M 页。

页表

页面映射表，简称页表，存储进程页到内存页帧的映射。

OS 为每个进程都维护了一个页表。另外还维护一个空闲页框列表。

进程在执行时不需要将所有页调入内存页框。

进程的页表驻留在内存中（二级或多级页表中的顶级页表一定驻留内存）。

页面大小

应是 2 的整数幂。

页面太小则页表过长，占用大量内存，增加硬件地址转换的开销，降低页面换入/换出的效率，并且不能充分利用访存的空间局部性来提高命中率。

页面过大则使页内碎片增大，降低内存的利用率。

确定页面大小有很多因素，如进程的平均大小、页表占用的长度等。

页的大小固定且由系统决定。

页表项大小

若逻辑地址空间 32 位、一页 4 KB，则一共有 1M 页，那么页表项至少需要 20 位才能表示完，若以字节为编址单位，则页表项至少为 3B。

当然也可以选择更大的页表项，让一个页面能够正好容纳整数个页表项，或便于增加一些其他信息。

基本地址变换机构

已知页面大小 L 和逻辑地址 A，求物理地址 E。

⚠整个地址变换过程均由硬件自动完成。

由上图的第 ③ 步可知，页表必须在物理内存中连续存放。

ps：数组的连续存放是逻辑空间上的连续，而且要是跨页的话不一定是相邻的页。

页表寄存器 PTR (Page-Table Register)

进程未执行时，页表始址和长度一开始放在本进程的 PCB 中，当调度切换到某进程时，才将这两个数据装入 PTR。因此在单处理机环境下，虽然系统中可运行多个进程，但只需一个 PTR。

IA-32 中页表寄存器 CR3 中保存的是进程顶级页表的物理地址，task_struct.pgdir 是顶级页表的虚拟地址，在调度切换到某进程时，会将该进程的 task_struct.pgdir 转换成物理地址再加载到 CR3 中。

访存次数

存取一个数据/指令至少访问两次内存（不考虑 TLB 和 Cache）：第一次访存是访问页表，得到数据/指令物理地址；第二次根据该物理地址访存去存取数据/指令。

分页管理方式需要处理好的两个问题

  1. 每次操作都需要进行逻辑地址到物理地址的转换，因此地址转换过程必须足够快，否则访存速度会降低。
  2. 每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。

快表 TLB (Translation Lookaside Buffer)

是一种相联存储器(Associative Memory)，具有并行查找能力的高速缓冲存储器，位于 CPU，属于 SRAM。

基于局部性原理，存放有若干页表项，以减少访存次数，加速地址变换过程。

相应地，内存中的页表就称为慢表。

和逻辑地址的映射方式通常采用全相联或组相联方式。

具有快表的地址变换机构

查页表时，可以先查快表再查慢表（默认），也可以快慢表一起查。两种计算不一样：

一般快表的命中率可达 90% 以上。

快表才真正存储了页号（即 Tag 字段，全相联是虚页号，组相联是虚页号去除末尾 $\log_2\text{N}$ 位组号的高位）。

若快表中未找到匹配的页号，则从慢表中读出页表项后，应同时将其存入快表。若快表已满，则须按照特定算法淘汰一个旧页表项。

两级页表

按一页 4 KB、一个页表项 4B 来算，若要实现进程对全部逻辑地址空间（32 位）的映射，则每个进程需要 4MB（1024 页）并且连续的主存空间存放页表。即使不考虑对全部逻辑地址空间进行映射的情况，以 40MB 的进程为例，页表 40KB，若将所有页表项存放在内存中，则需要 10 个内存页框保存，而整个进程实际执行时只需要几十个页面进入内存，这无疑降低了内存利用率；从另一方面，根据局部性原理，大多数情况下映射所需要的页表项都在页表的同一个页面中，因此 10 页的页表项也并不需要同时保存在内存中。

为了压缩页表，我们进一步延伸映射的思想，就可得到二级分页。

为了查询方便，顶级页表大小最多占一页。

两级页表下，页表寄存器是针对顶级页表设置的。

上述对页表施行离散分配的方法，只解决了对于大页表无需大片连续存储空间的问题（顶级页表还是需要连续的），并未解决用较少的内存空间去存放大页表的问题。换言之，只用离散分配空间的办法并未减少页表所占用的内存空间（甚至还增加了）。

要解决占用内存过大的问题，可再利用虚拟存储思想，即不用把所有的页表都调入内存，只在需要它时才调入。因此为了表征某页的二级页表是否已经调入内存，还应在顶级页表项中增设一个状态位。

所以采用虚拟内存 + 两级页表的情况下，会发生页表不在内存而需要产生中断去磁盘 I/O 的情况。

多级页表

对于更大的逻辑地址空间，两级分页中的顶级页表也要占用很大的连续内存空间，因此必须采用多级页表。

建立两级及多级页表的目的在于建立索引，以便不用浪费内存空间去存储无用的页表项。

多级页表解决了当逻辑地址空间过大时，页表的长度会大大增加的问题。

但也导致存取一次数据或指令需要多次访问内存甚至磁盘，会大大增加一次访存的时间。

基本分段存储管理方式

引入目的

分页管理方式是从计算机的角度考虑设计，目的是提高内存的利用率，提升计算机的性能，通过硬件机制实现，对用户完全透明。

分段管理方式的提出则考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接⚠等多方面需要。

段的划分

分段系统将用户进程的逻辑地址空间划分为大小不等的段（段长不固定），例如主程序段、子程序段、数据段及栈段等。

每段从 0 开始编址，并分配一段的地址空间。段内要求连续，段间不要求连续。

逻辑地址结构

在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在分段系统中，段号和段内偏移量必须由用户显式提供（高级程序设计语言中由编译程序完成）。因为每段的长度是不固定的，无法通过除法得出段号，无法通过求余得出段内偏移。

分段系统进程的地址空间是二维的。

确定一个地址需要几个参数，作业地址空间就是几维的：

分页管理的地址空间是一维的：页号。
分段管理的地址空间是二维的：段号、段内偏移。
段页式管理的地址空间是二维的：段号、页号。

段表

地址变换机构

变换过程与分页类似。

从逻辑地址取段号和段内偏移量无法通过除法和取模得到，因为段长不固定，故需要显式提供段号和段内偏移。

越界保护除了要比较段表长度和段号，还要比较段长和段内偏移量（而分页中的页内偏移是不可能越界的）。

注意上图里是段表寄存器。

段表寄存器

系统中设置了一个段表寄存器，用于存放段表始址和段表长度。

段表寄存器和页表寄存器的作用都有两个，一个是在段表或页表中寻址，二是判断是否越界。

IA-32 中的描述符表寄存器即为段表寄存器。

分页 vs 分段

  • 页是信息的物理单位，段是信息的逻辑单位。

    分页完全是系统的行为，对用户不可见；分段的主要目的是更好地满足用户需求，用户按照逻辑关系将程序划为若干段，分段对用户是可见的。

  • 页的大小固定且由系统确定；段的长度不固定，具体取决于用户所编写的程序。

  • 分页管理的地址空间是一维的，分段管理的地址空间是二维的。

动态分区 vs 分段

分段和动态分区很像，但分段是进程内分配，属于非连续分配；动态分区是进程间分配，属于连续分配。

分段的优点

具有逻辑独立性（段的分界与程序的自然分界相对应），使得它易于编译、管理、修改和维护，也便于多道程序的共享。

分段的缺点

段长可变，分配空间不便，容易在段间留下碎片。

段的共享

分页系统也能实现程序和数据的共享，但远不如分段系统来得方便。若被共享的代码占 N 个页框，则每个进程的页表中都要建立 N 个页表项，指向被共享的 N 个页框。

在分段系统中，不管该段有多大，都只需为该段设置一个段表项，因此非常容易实现共享。只需在每个进程的段表中设置一个段表项，指向被共享的同一个物理段。

为了防止程序在执行时修改共享代码，在每个进程中都必须配以局部数据区，将在执行过程中可能改变的部分复制到数据区，这样进程就可对该数据区中的内容进行修改。

也可用一个单独的共享段表来描述这些共享段，而不需要在每个进程的段表中都保存一份。

段的保护

  1. 存取控制保护

  2. 地址越界保护

    将段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断；

    再将段表项中的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，也会产生越界中断。

段页式管理方式

引入目的

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。将这两种存储管理方法结合起来，便形成了段页式存储管理方式。

即：用分段方法来分配和管理用户地址空间，用分页方法管理物理存储空间。

优点

兼具页式和段式的优点，可以按段实现共享和保护。

缺点

地址变换过程中需要两次查表，系统开销大。

段页的划分

作业的地址空间先被划分成若干逻辑段，每段再分成若干大小固定的页

对内存空间的管理仍和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。

逻辑地址结构

段表和页表

系统为每个进程建立一张段表，每个分段又分别有一张页表。

在一个进程中，段表只有一个，而页表可能有多个。

地址变换机构

存取一次数据/指令一般需要访问三次内存（段表→页表→数据/指令）。

同样可以使用快表来加快查找，其关键字由段号和页号组成，值是对应的页框号和保护码。

段表寄存器

系统中应有一个段表寄存器，指出进程的段表始址和段表长度。

虚拟内存管理

在物理上扩展内存相对有限，尝试以一些其他可行的方式在逻辑上扩充内存。

基本概念

传统存储管理方式的特征

  1. 一次性

    作业必须一次性全部装入内存后才能开始运行。这会导致两种情况：

    1）不能全部被装入内存的大作业永远无法运行。

    2）当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序并发度的下降。

  2. 驻留性

    作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业结束运行。运行中的进程会因等待 I/O 而被阻塞，可能处于长期等待状态。

局部性原理

从广义上讲，快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。

局部性原理既适用于程序结构，又适用于数据结构。

局部性原理表现在以下两个方面：

  1. 时间局部性

    程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。

    产生的典型原因：程序中存在大量的循环操作。

    通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现时间局部性。

  2. 空间局部性

    一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围内。

    因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

    空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。

虛拟内存技术实际上建立了 “内存-外存” 的两级存储器结构，利用局部性原理实现高速缓存。

局部性越好，虚拟存储系统越能更好地发挥作用。

虚拟存储器的定义

具有部分装入、请求调入和置换功能，能从逻辑上对内存容量加以扩充的存储器系统。

虚拟存储器的主要特征

  • 多次性

    一个作业中的程序和数据无需在作业运行时一次性地全部装入内存。

    只需将当前要运行的那部分程序和数据装入内存即可开始运行。以后每当要运行到尚未调入的那部分程序和数据时，再将它们调入。

  • 对换性

    一个作业中的程序和数据无需在作业运行时常驻内存。

    允许在作业运行过程中，将那些暂不使用的程序和数据从内存调至外存的对换区（换出），待以后需要时再将它们从外存调至内存（换进）。

  • 虚拟性

    从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际。

虚存空间大小的决定因素（要满足的条件）

  • 虚存实际容量 ≤ 内存容量 + 外存容量。
  • 虚存最大容量 ≤ 计算机的地址位数能容纳的最大容量。

实际虚存的容量是取两个条件的交集，即两个条件都要满足。

虚拟内存技术的实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。

采用连续分配方式时，会使相当一部分内存空间都处于暂时或 “永久” 的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。

虚拟内存的实现有以下三种方式：

  • 请求分页存储管理。
  • 请求分段存储管理。
  • 请求段页式存储管理。

需要的硬件支持：

  • 一定容量的内存和外存。
  • 页表机制/段表机制（作为主要的数据结构）。
  • 中断机构（当用户程序要访问的部分尚未调入内存时，则产生中断）。
  • 地址变换机构（逻辑地址 → 物理地址）。

请求分页管理方式

建立在基本分页系统基础上，为了支持虚拟存储器功能而增加了请求调页（换入）功能和页面置换（换出）功能。

请求分页式目前最常用的一种实现虚拟存储器的方法。

虚拟地址空间中的页面

虚拟地址空间中有一些 “空洞” 的没有内容的页面。例如，堆区和栈区都是动态生长的，因而在栈和共享库映射区之间、堆和共享库映射区之间都可能没有内容存在。这些没有和任何内容相关联的页称为 “未分配页”；对于代码和数据等有内容的区域所关联的页面，称为 “已分配页”。已分配页中又有两类：已调入主存而被缓存在 DRAM 中的页面称为 “缓存页”；未调入主存而存在硬盘上的页称为 “未缓存页”。

因此，任何时刻一个进程中的所有页面都被划分成三个不相交的页面集合：未分配页集合、缓存页集合、未缓存页集合。

页表机制

相比基本分页，页表项增加了几个字段：

  • 有效位 / 装入位 / 状态位 P

    指示该页是否已调入内存。

    供程序访问时参考。

  • 引用位 / 使用位 / 访问字段 A

    记录本页在一段时间内被访问的次数 / 本页最近已有多长时间未被访问。

    供置换算法换出页面时参考。

  • 脏位 / 修改位 M

    标识该页在调入内存后是否被修改过。

    虚存机制中采用回写策略，利用脏位可判断替换时是否需要写回外存。

  • 外存地址

    记录该页在外存上的地址。

    通常是该页在外存的物理块号，供调入该页时参考。

    有时会将物理块号和外存地址两个字段合并，使用时根据有效位来区分。

另外，袁书中还给出了其他几个字段：

  • 访问权限位

    用来说明页面是可读可写、只读还是只可执行等，用于存储保护。

  • 禁止缓存位

    用来说明页面是否可以装入 Cache，通过正确设置该位，可以保证磁盘、主存和 Cache 数据的一致性。

下面是袁书中给出的页表示例（页框号和外存地址合并为存放位置字段），其中有 4 个缓存页：VP1、VP2、VP5 、VP7；有 2 个未分配页：VP0、VP4；有 2 个未缓存页：VP3、VP6。

有效位 1：表示该虚拟页已从外存调人主存，属于缓存页。

有效位 0、外存地址非 null：未缓存页。

有效位 0、外存地址 null：未分配页。

对于上图所示的页表，假如 CPU 执行一条指令要求访问某个数据，若该数据正好在虚拟页 VP1 中，则根据页表得知，VP1 对应的装入位为 1，该页的信息存放在物理页 PP0 中，因此，可通过地址转换部件将虚拟地址转换为物理地址，然后到 PP0 中访问该数据；若该数据在 VP6 中，则根据页表得知，VP6 对应的装入位为 0，表示页面缺失，发生缺页异常，需要调出操作系统的缺页异常处理程序进行处理。缺页异常处理程序根据页表中 VP6 对应表项的存放位置字段，从磁盘中将所缺失的页面读出，然后找一个空闲的物理页框存放该页信息。若主存中没有空闲的页框，则还要选择一个页面淘汰出来替换到磁盘上。因为采用回写策略，所以页面淘汰时，需根据修改位确定是否要写回磁盘。缺页处理过程中需要对页表进行相应的更新，缺页异常处理结束后，程序回到原来发生缺页的指令继续执行。

对于上图所示的页表，虚拟页 VP0 和 VP4 是未分配页，但随着进程的动态执行，可能会使这些未分配页中有了具体的数据。例如，调用 malloc 函数会使堆区增长，假若新增的堆区与 VP4 对应，则操作系统内核就在磁盘上分配一个存储空间给 VP4，用于存放新增堆区中的内容，同时，对应 VP4 的页表项中的存放位置字段被填上该磁盘空间的起始地址，VP4 从未分配页转变为未缓存页。

缺页中断机构

缺页中断属于异常/内中断，由操作系统的缺页中断处理程序处理。

若内存中有空闲页框，则为产生缺页中断的进程分配一个页框，将所缺页面从外存装入该页框，并修改页表中的相应表项；若此时内存中没有空闲块，则根据页面置换算法选择一个页面淘汰。若被淘汰页在内存期间被修改过，则要将其写回外存，未修改过的页面则不用写回外存。

在指令执行期间而非一条指令执行完后产生和处理中断信号。

一条指令在执行期间可能产生多次缺页中断。

地址变换机构

在基本分页系统地址变换基础上，增加了产生和处理缺页中断，以及从内存中换出一页的功能。

更新快表时，若快表已满，也需采用某种算法替换（上图没画出来），为降低开销，TLB 常采用随机替换策略。

⚠虚拟存储器中，地址映射由操作系统和硬件共同完成（基本存储管理方式是由硬件自动完成）。

快表命中则该页必然在内存中。

快表每个表项的内容由页表表项内容加上一个 TLB 标记字段组成。

页面很大或很小造成操作速度变慢的原因

页式虚拟存储器中，页面很大或很小都会使操作速度变慢，但原因不同：

页面很小，虚拟存储器中包含的页面数就会过多，导致：①页表的体积过大；②不能充分利用访存的空间局部性来提高命中率⚠。

页面很大，虚拟存储器中的页面数会变少，由于主存的容量比虚拟存储器的容量小，主存中的页面数会更少，进而会导致：①平均页内剩余空间（内部碎片）较大。②页面调入/调出时间较长。③页面调度频率较高，换页次数增加⚠。

相对的，页面小和页面大的好处：

页面小：平均页内剩余空间（内部碎片）较少，可节省存储空间。

页面大：减少页表空间。

请求分页中的页框分配

驻留集

指给特定进程分配的物理页框的集合。

对于分页式的虚拟内存，在进程准备执行时，不需要也不可能把一个进程的所有页都读入主存。因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。给一个进程分配的物理页框的集合就是这个进程的驻留集。

驻留集可以说就是进程已装入内存的页面的集合（王道 P226 选择 29），一般不会存在 OS 给进程分配了页框但进程实际未装入的情况（猜的）。

驻留集的大小

驻留集越小，驻留在内存中的进程就越多，可以提高多道程序的并发度，但分配给每个进程的页框太少，会导致缺页率较高，CPU 需耗费大量时间来处理缺页。

驻留集越大，当分配给进程的页框超过某个数目时，由于局部性原理，再为进程增加页框对缺页率的改善是不明显的，反而只能是浪费内存空间，使得多道程序并发度的下降，进而可能造成 CPU 空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。

驻留集大小不能小于工作集，否则进程在运行过程中会频繁缺页（发生抖动）。

页框分配策略

即驻留集的大小设置。

固定分配(fixed-allocation)

为一个进程在内存中分配固定数量的页框，在进程运行期间都不改变。

如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法：

1）平均分配算法

2）按比例分配算法（根据进程的大小）

3）优先权分配算法（为重要和紧迫的进程分配较多的物理块）

通常采取的方法是把所有可分配的物理块分成两部分：一部分按比例分配给各个进程，一部分则根据优先权分配。

采用该策略时，为每个进程分配多少物理块是根据进程类型（交互型或批处理型等)或根据程序员、程序管理员的建议来确定的。实现这种策略的困难在于，应为每个进程分配多少个物理块（即驻留集的大小设置）难以确定。

可变分配(variable-allocation)

允许分配给一个进程的页框在该进程的生命周期中不断地发生变化，根据缺页率使进程分得的页框数动态增加或减少。

看起来性能更优，但难点在于它要求 OS 评估活动进程的行为，这必然会增加 OS 的软件开销，并取决于处理器平台所提供的硬件机制。

页面置换策略

局部置换

指如果进程在运行中发现缺页，则只能从分配给该进程的 $n$ 个页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。

全局置换

指如果进程在运行中发现缺页，则将 OS 所保留的空闲物理块（一般组织为一个空闲物理块队列）去除一块分配给该进程，或者以所有进程的全部物理块为标的（通常仅当空闲物理块用完时），选择一块换出，然后将所缺之页调入，这样，分配给该进程的内存空间就随之增加。

比局部置换更加灵活，可以动态增加进程的物理块，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降。

内存分配策略

即页框分配策略和页面置换策略的组合。

固定分配全局置换

冲突，无此方案。

固定分配局部置换

不灵活，难点在确定驻留集大小。

可变分配全局置换

可能最容易实现，被许多 OS 使用。难点在于置换页的选择，没有任何原则用于确定应该让哪个进程的驻留集给出一页。

可变分配局部置换

该策略同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止。反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。

这种策略在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。

需要更复杂的实现，也需要更大的开销，但对比频繁地换入换出所浪费的计算机资源，这种牺牲还是值得的。

调入页面的时机

预调页策略

如果进程的许多页是存放在外存的一个连续区域中，一次调入若干个相邻的页会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。于是便考虑采用一种以预测为基础（基于局部性原理）的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。

如果预测较准确，那么这种策略显然是很有吸引力的。但遗憾的是，目前预调页的成功率仅约 50%。

但预调页策略又因其特有的长处取得了很好的效果。

  1. 首先可用于在第一次将进程调入内存时，此时可将程序员指出的那些页先调入内存。
  2. 其次是，在采用工作集的系统中，每个进程都具有一张表，表中记录有运行时的工作集，每当程序被调度运行时，将工作集中的所有页调入内存。

请求调页策略

即请求了再调入。

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由 OS 将其所需页面调入内存。由请求调页策略所确定调入的页是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。

优点：易于实现。

缺点：每次仅调入一页，增加了磁盘 I/O 开销。

一般情况下两种调页策略同时使用：运行前预调入，运行期间请求调入。

从何处调入页面

请求分页系统外存的划分

  1. 文件区：存放文件（通常采用离散分配）。
  2. 对换区：存放对换页面（通常采用连续分配，因此磁盘 I/O 比文件区快）。

三种情况

  1. 对换区空间足够

    全部从对换区调入所需页面。

    进程运行前需要将与该进程有关的文件从文件区复制到对换区。

  2. 对换区空间不足

    不会被修改的文件都从文件区调入，需要调出这些文件时，因为它们未被修改而不必被调出。

    对于可能被修改的部分，换出时调到对换区，以后需要时就从对换区调入。

  3. UNIX 方式

    与进程有关的文件一开始都放在文件区，换出时再都放在对换区（因此，文件区存放的都是未运行过的页面，对换区存放的都是曾经运行过但又被换出的页面）。UNIX 允许页面共享，若某进程请求的共享页面已被其他进程调入内存时便无需再调入。

如何调入页面

当进程所访问的页面不在内存中时（存在位为 0），便向 CPU 发出缺页中断，中断响应后便转入缺页中断处理程序。该程序通过查找页表得到该页在外存的物理块后，此时如果内存未满（存在空闲页框），则启动磁盘 I/O，将所缺页调入内存。如果内存已满（没有空闲的页框），则先按某种置换算法和置换范围从内存中选出一页准备换出：如果该页未被修改过（修改位为 0），则无须将该页写回磁盘；但若该页已被修改（修改位为 1），则必须将该页写回磁盘对换区。然后将所缺页调入内存。调入内存的同时需要修改页表中的相应表项，置其存在位为 1，并将此页表项写入快表中。完成后，进程就可利用修改后的页表形成所要访问数据的内存物理地址，再去访问内存数据。

页面置换算法

进程运行时，若其访问的页面不在内存中而需将其调入，但内存已无空闲空间时（或采取局部置换策略时），就需要从内存中调出一页程序或数据，送入磁盘的对换区中。

页面的换入、换出需要磁盘 I/O，开销较大，因此好的页面置换算法应该追求更低的缺页率，不适当的算法则可能会导致进程发生 “抖动”。

最佳置换算法 OPT

换出以后永不使用或（未来）最长时间内不再被访问的页面。

理想算法（因为无法预知未来），无法实现。

能得到最低的缺页率，故用来评价其他算法。

先进先出页面置换算法 FIFO

优先淘汰最早进入内存的页面，即当前在内存中驻留时间最久的页面。

实现简单：将页面中的页面根据调入的先后顺序排成一个队列，需要换出时选择队头的页面即可。

性能较差：没有利用局部性原理，与进程实际运行时的规律不适应（因为先进入的页面也有可能最经常被访问）。

可能出现 Belady 异常：给进程分配的物理块增多，缺页率反而上升（只有 FIFO 算法可能出现）。

最近最久未使用算法 LRU

选择最近最长时间未访问的页面予以淘汰（认为它们在最近的将来也不太可能会被访问）。

为每个页面设置访问字段，来记录该页距离上次被访问的时间。

算法性能较好，性能接近于 OPT 算法：利用 “最近的过去” 作为 “最近的将来” 的近似，以 “过去” 预测 “未来”。

LRU 置换算法的硬件支持

LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的硬件支持，实现起来开销大。

开销大的原因是需要对所有的页排序，而需要硬件支持只是耗费高的体现而非原因。

为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有寄存器和栈两类硬件之一的支持。

  1. 寄存器

    为进程每个在内存中的页面配置一个移位寄存器，可表示为：$R=R_{n-1} R_{n-2} R_{n-3} \cdots R_2 R_1 R_0$.

    当进程访问某物理块时，要将相应寄存器的 $R_{n-1}$ 位置为 1。此时，定时信号将每隔一定时间（如 100ms）将寄存器右移一位。如果把 $n$ 位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面就是最近最久未使用的页面。

  2. 栈

    利用一个特殊的栈保存当前使用的各个页面的页面号，每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

    也可以说是一种 FIFO，只不过 LRU 是针对页面最近访问的时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序（因为其中某个页面的最近访问时间改变了）；而 FIFO 是针对页面进入内存的时间来进行排序的，这个时间是固定不变的，所以各个页面之间的先后顺序时固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是他进入内存的时间。换句话说，如果内存当中的所有页面都未曾访问过，那么 LRU 算法就退化为 FIFO 算法。

时钟置换算法 CLOCK

虽然 LRU 是一种较好的算法，但由于它要求有较多的硬件支持，使得其实现所需的成本较高，故在实际应用中，大多采用 LRU 的近似算法。CLOCK 算法就是用得较多的一种 LRU 近似算法。

简单 CLOCK 算法

为每页设置一位使用位 U（即访问位 A），将置换范围内的候选页，即所属进程的驻留集（局部置换）或整个内存的页面（此时内存已满），通过指针链接成一个循环队列，并用一个替换指针与之关联。

当某页被装入或被访问时，U 置 1。

置换时顺序查找循环链：U 为 0，置换该页；U 为 1，改置为 0；替换指针前移。

因为该算法只有一位访问位，置换时是将未使用过的页面换出去，故又把该算法称为最近未用 NRU 算法。

改进型 CLOCK 算法

除考虑页面使用情况外，还增加了置换代价——修改位，某页被修改时置 1。

使用位 U 指示未来被访问的可能性，修改位 M 代表置换代价。

⚠注意：第一轮扫描不改变访问位，第二轮扫描期间才将所有扫描过的页面访问位置 0。若第二轮也失败，此时所有帧的访问位都已复 0，则在接下来的两轮扫描中一定能找到被淘汰的页。

增加使用的位数可使时钟算法更有效（位数减少至 0 则退化为 FIFO）。改进 CLOCK 算法优于简单 CLOCK 算法的地方在于，可减少磁盘 I/O 次数。但为了找到一个可置换的页，可能要经过几轮扫描，即实现算法本身的开销将有所增加。

之所以 U = 0，M = 1 的页要比 U = 1，M = 0 的页优先被淘汰，是因为 U 为首要考虑因素。操作系统中的页面置换算法都有一个原则，即尽可能保留访问过的页面。虽然置换这样的页必须先写回而造成时间开销，但根据局部性原理，它不会很快被用到。

抖动与工作集

系统并发度与处理机利用率

抖动(thrashing)/颠簸

频繁的页面调度行为（换页时间 ＞ 执行时间）。

在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存。

可以简单理解为缺页率高。

根本原因：系统中同时运行的进程太多，使得分配给每个进程的物理块太少，不能满足进程正常运行的基本要求。

主要原因：页面置换算法不合理。

抖动的解决

  1. 挂起一些进程，释放它们的帧（减少多道程序的度数）。
  2. 增大内存的容量。

增大交换区和使用更快的交换区都没用。

工作集

工作集 W 指在某段时间间隔 Δ 里，进程实际所要访问页面的集合。

一般来说，工作集 W 可由时间 t 和工作集窗口大小 Δ 来确定，即工作集 W 为 t 时刻进程的工作集为在时间间隔 (t-Δ, t) 中引用页面的集合。

实际应用中，工作集窗口会设置的很大，即对于局部性好的程序，工作集大小一般会比工作集窗口小很多。

工作集反映了进程在接下来一段时间内很有可能会频繁访问的页面集合，因此驻留集大小不能小于工作集，否则进程在运行过程中会频繁缺页（发生抖动）。

工作集 vs 驻留集

工作集不一定是驻留集的子集，因为有些工作集中的页面可能还未调入内存，或已被换出内存。

只有当工作集完全包含在驻留集中时，才能保证进程不发生缺页中断。

工作集大小变化

稳定阶段（局部性阶段）与瞬变阶段交替出现。

在瞬变阶段，来自原局部性阶段中的某些页仍留在窗口 Δ 中，导致访问新页时工作集大小剧增。当窗口滑过这些页访问后，工作集大小减小，直到它包含那些满足新的局部性的页。

工作集模型（工作集策略）

  • 原理

    让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。

    落在工作集内的页面需要调入驻留集中，而落在工作集外的页面可从驻留集中换出。

    若还有空闲物理块，则可再调一个进程到内存。

    若所有进程的工作集之和超过了可用物理块总数，则操作系统会暂停一个进程，将其页面调出并将物理块分配给其他进程，防止出现抖动现象。

  • 问题

    过去未必能预示将来，工作集大小和成员会随时间变化。

    记录工作集变化要求开销太大。

    Δ 的最优值是未知的。

内存映射文件

原理

内存映射文件 (Memory-Mapped Files) 是操作系统向应用程序提供的一个系统调用。进程通过该系统调用，将磁盘文件全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，之后便可用访问内存的方式读写文件，而不必执行文件 I/O 操作，也无须对文件内容进行缓存处理。

使用内存映射文件所进行的任何实际交互都是在内存中进行的，并且是以标准的内存地址形式来访问的。

磁盘文件的读写由操作系统完成，对进程透明。当映射进程的页面时，不会实际读入文件的内容，而只在访问页面时才被每次一页地读入。当进程退出或显式地解除文件映射时，所有被改动的页面才会被写回磁盘文件。

类型

内存映射文件分为两种类型：

  1. 持久化内存映射文件

    持久化文件是与磁盘上的源文件相关联的内存映射文件。当最后一个进程处理完文件或显式地解除文件映射时，所有被改动的页面会被写回磁盘文件。此类内存映射文件适用于处理非常大的源文件。

  2. 非持久化内存映射文件

    非持久化文件是不与磁盘上的文件相关联的内存映射文件。当最后一个进程处理完文件时，数据会丢失，且文件被垃圾回收器回收。此类文件适合创建共享内存，以进行进程内通信 IPC。

内存映射与共享内存

多个进程允许并发地映射同一文件，以便允许数据共享。

实际上很多时候共享内存就是通过映射相同文件到通信进程的虚拟地址空间实现的。当多个进程映射到一个文件时，各进程的虚拟地址空间都是互相独立的，但操作系统将对应的这些虚拟地址空间映射到相同的物理内存（用页表实现）。一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。

总结

虚拟存储器性能影响因素

缺页率是影响虚拟存储器性能的主要因素。

缺页率又受到页面大小、分配给进程的物理块数即驻留集大小、页面置换算法以及程序的编制方法的影响。

  • 页面较大：缺页率低、减少页表长度；页内碎片增大。

    页面较小：减少了内存碎片，有利于提高内存利用率；使每个进程要求较多的页面，导致页表过长，占用大量内存。

  • 分配给进程的物理块数越多，缺页率就越低，但是当物理块超过某个数目时，再为进程增加物理块对缺页率的改善是不明显的，只是浪费内存空间。只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。

  • 好的页面置换算法可使进程在运行过程中具有较低的缺页率。选择 LRU、CLOCK 等置换算法，将未来有可能访问的页面尽量保存在内存中，从而提高页面的访问速度。

  • 编写程序的局部化程度越高，执行时的缺页率就越低。

    如果存储采用的是按行存储，访问时就要尽量采用相同的访问方式，避免按列访问造成缺页率过高的现象。

另外磁盘 I/O 次数对虚拟存储器性能造成影响。脏页攒够一定数量再成批一次换出，不仅可以显著较少磁盘 I/O 的次数，即较少换出脏页的开销，若有进程在这批脏页还未写回磁盘时需要再次访问这些页面时，还可以减少页面从磁盘读入内存的频率，减少页面换进的开销。

地址翻译示例

系统参数

  • 存储器按字节编址
  • 虚拟地址 14 位，物理地址 12 位
  • 有一个 TLB 与一个 data Cache
  • 页面大小 64B
  • TLB 四路组相联，共 16 个条目
  • data Cache 直接映射，行长 4 B，共 16 行（也可视为 16 组，即一行一组）

地址结构分析

页面大小 64B = $2^6$B → 页内偏移 6 位 → 虚拟页号 8 位、物理页号 6 位。

TLB 四路组相联，共 16 条，即分为 4 = $2^2$ 组 → TLB 组号 2 位、标记位数 = 虚拟页号 8 位 - 组号 2 位 = 6 位。

data Cache 行长 4 = $2^2$ B → 行内偏移 2 位。

data Cache 看作一路组相连映射，16 行即为 16 = $2^4$ 组 → Cache 组号 4 位、标记位数 = 物理地址 12 位 - 行内偏移 2 位 - 组号 4 位 = 6 位。

数据内容

访问过程

以访问虚拟地址 0x03d4、0x00f1、0x0229 为例。

1）首先需要将虚拟地址转化为物理地址，先快表后慢表。虚拟地址化为二进制形式：

0x03d4 TLB 组索引为 3，TLB 标记为 03H，查 TLB 发现有匹配项且有效位为 1，得到物理页号 0D，拼接页内地址后得到物理地址 0x354。

0x00f1 TLB 组索引为 3，TLB 标记为 00H，TLB 查无此项，再用虚拟页号 03H 去内存中的页表找，匹配的页表项有效位为 1，得到物理页号 02H，拼接页内地址后得到物理地址 0x0b1。

0x0229 TLB 组索引为 0，TLB 标记为 02H，TLB 查无此项，再用虚拟页号 08H 去内存中的页表找，匹配的页表项有效位为 0，页面不在内存中，产生缺页中断。

2）接下来通过物理地址访问数据，先 Cache 后主存。物理地址的二进制形式为：

0x354 Cache 组号为 5，Cache 标记为 0DH，查 Cache 发现有匹配行且有效位为 1，说明要访问的数据在此行中，再根据行内偏移 0 得到要访问的数据内容为 36H。

0x0b1 Cache 组号为 C，Cache 标记为 02H，查 Cache 发现有匹配行但有效位为 0，说明要访问的数据不在 Cache 中，只能去主存中取物理页号为 2、页内偏移为 31H 的内容。

刷题总结

  • 动态重定位的过程依赖于：可重定位装入程序、重定位寄存器、地址变换机构。

  • 动态重定位不依赖于目标程序。

  • 只有单一连续分配和固定分区分配采用静态重定位；其他管理方案均可能在运行过程中改变程序位置，采用动态重定位。

    硬件地址变换机构用于动态重定位，需要硬件地址变换机构 = 采用动态重定位。

  • 内存保护需要操作系统和硬件的配合。

  • 基本存储管理方式的地址转换过程由硬件自动完成，不需要操作系统或其他软件的干预。

    例如，在基本页式存储管理中， CPU 将虚拟地址分解为页号和页内偏移量，然后通过硬件中的页表寄存器和内存管理单元 MMU，查找内存中的页表，将页号转为物理地址，再拼接上页内偏移量，得到最终的内存物理地址。

    虚拟内存管理方式的地址转换过程由操作系统和硬件共同完成。

  • 采用段式存储管理时，一个程序如何分段是在用户编程时决定的。

  • 程序的动态链接与程序的逻辑结构有关，分段存储管理有利于动态链接。

  • 操作系统实现分区存储管理的代价最小。

    实现分页、分段和段页式存储管理需要特定的数据结构支持，如页表、段表等。为了提高性能，还需要硬件提供快存和地址加法器等，代价高。

    分区存储管理是满足多道程序设计的最简单的存储管理方案，特别适合嵌入式等微型设备。

  • 段表寄存器和页表寄存器的作用都有两个，一是在段表或页表中寻址，二是判断是否越界。

  • 采用分页或分段管理后，提供给用户的物理地址空间大小不能确定。

    页表和段表同样存储在内存中，系统提供给用户的物理地址空间为总空间减去页表或段表的长度。由于页表和段表的长度不能确定，所以提供给用户的物理地址空间大小也不能确定。

  • 求系统的平均访问时间别忘了加上最终访问数据/指令的那一次。

  • 虚拟存储管理系统的基础是程序的局部性理论：

    在程序装入时，不必将其全部读入内存，而只需将当前需要执行的部分页或段读入内存，就可让程序开始执行。

    在程序执行过程中，若需执行的指令或访问的数据尚未在内存（称为缺页或缺段）中，则由处理器通知操作系统将相应的页或段调入内存，然后继续执行程序。

    由于程序具有局部性，虚拟存储管理在扩充逻辑地址空间的同时，对程序执行时内存调换的代价很小。

  • 增大页面可以提高 TLB 命中率：可用较少的页面覆盖更大的地址空间，从而减少页表项，因此可以提高 TLB 命中率。

    反之减小页面则会降低 TLB 命中率。

  • 能加快虚实地址转换的措施：增大快表 TLB 容量、让页表常驻内存。

  • 系统有 $m$ 个物理块，初始时全空，页面引用串长度为 $p$，包含了 $n$ 个不同的页号，则无论用什么页面置换算法，页故障数的上限。