操作系统原理之内存管理 #

目录 #

存储器和存储单元介绍 #

内存设备是数字系统（ digital system），可以临时或长期存储数据。从数字计算机到硬盘都有内置的存储设备（memory devices），可以存储用户或制造商的数据。这些数据要么是控制程序的形式，要么是启动系统的程序。因此，为了存储如此大量的数据，内存设备必须有巨大的容量（capacity）。我们面临的挑战是如何建造具有大容量但成本可控的存储设备。存储器设备必须能够存储永久数据（permanent data）和瞬时数据（instantaneous data）。

存储器（Memories）是由寄存器（registers）组成的。存储器中的每个寄存器就是一个存储位置（storage location）。存储位置也被称为内存位置（memory location）。存储器位置是用地址（Address）来识别的。一个存储器可以存储的总位数就是它的容量（capacity）。

一个存储元素（storage element）被称为存储单元（Cell）。每个寄存器是由一个存储元素组成的，其中存储着一位数据（bit）。存储器中的数据分别通过称为写（writing）和读（reading）的过程进行存储（stored）和检索（retrieved）。

一个字（word）是一组比特（bits），一个存储单元（memory unit）在这里存储二进制信息。一组 8 位（bits）的字被称为一个字节（byte）。一个存储单元由数据线（data lines）、地址选择线（address selection lines）和指定传输方向的控制线（control lines）组成。一个存储单元的如下所示：

数据线提供要存储在存储器中的信息。控制输入线指定数据的直接传输。k-address 线指定选择的字。当有 k 条地址线时，可以访问 2^k个内存字。

以下是一些重要的存储单元 :

• 位（Bit，Binary Units）：位是电气状态（electric state）的逻辑表示。它可以是 1 或 0。
• Nibble：它指的是 4 个比特的组。
• 字节（Byte）：一个字节是由 8 个比特组成的一组。
• 字（Word）：它是一个固定位数的组，它因计算机而异，但对每个设备来说是相同的。计算机以字的形式存储信息。

以下是存储单元的转换：

• Kilobyte (kb): 1kb = 1024 byte
• Megabyte (mb): 1mb = 1024 kb
• Gigabyte (gb): 1gb = 1024 mb
• Terabyte (tb): 1tb = 1024 gb
• Petabyte (pb): 1pb = 1024 tb

参考：

• Random Access Memory (RAM) and Read Only Memory (ROM) - GeeksforGeeks
• Different Types of RAM (Random Access Memory ) - GeeksforGeeks
• Cache Memory - GeeksforGeeks
• Secondary Memory - GeeksforGeeks

存储器层次结构设计及其特点 #

在计算机系统设计（Computer System Design）中，内存层次（Memory Hierarchy）是对内存组织的一种改进，它可以使访问时间（access time）最小化。存储器层次结构是基于一种被称为参考定位（locality of references）的程序行为而开发的。下图清楚地展示了存储器层次结构的不同级别。

这种内存层次结构设计主要分为 2 种类型：

• 外部存储器或二级存储器（External Memory or Secondary Memory）：包括磁盘（Magnetic Disk）、光盘（Optical Disk）、磁带（Magnetic Tape），即处理器通过 I/O 模块（I/O Module）访问的外围存储设备（peripheral storage devices）。
• 内部存储器或主存储器（Internal Memory or Primary Memory）：由主存储器（Main Memory）、缓存存储器（Cache Memory）和 CPU 寄存器组成（CPU registers）。这是由处理器直接访问的。

我们可以从上图中推断出存储器层次结构设计的以下特点：

• 容量（Capacity）。它是内存可以存储的总体信息量（global volume of information）。当我们在层次结构中从上到下移动时，容量会增加。
• 访问时间（Access Time）。它是读 / 写请求（read/write request）和数据可用性（availability of the data）之间的时间间隔。随着我们在层次结构中从上到下的移动，访问时间会增加。
• 性能（Performance）。早些时候，当计算机系统在设计时没有采用内存层次结构，由于访问时间的巨大差异，CPU 寄存器和主内存之间的速度差距增加。这导致了系统性能的降低，因此需要加强。这种改进是以内存层次设计（Memory Hierarchy Design）的形式进行的，因为它提高了系统的性能。提高系统性能的最重要的方法之一是最大限度地减少操作数据所需的内存层次的深度。
• 单位成本（Cost per bit）。当我们在层次结构中从下往上移动时，单位成本就会增加，即内部存储器比外部存储器成本高。

内存管理中的分区方法 #

在操作系统中，以下是四种常见的内存管理技术（memory management techniques）：

• 单一连续分配（Single contiguous allocation）。MS-DOS 使用的最简单的一种分配方法。所有的内存（除了一些为操作系统保留的内存）都可以供一个进程使用。
• 分区式分配（Partitioned allocation）。内存被划分为不同的块或分区（blocks or partitions）。每个进程根据需求被分配。
• 分页内存管理（Paged memory management）。内存被分为固定大小的单元（units），称为页帧（page frames），在虚拟内存环境（virtual memory environment）中使用。
• 分段式内存管理（Segmented memory management）。内存被划分为不同的段（段（segments）是进程数据或代码的逻辑分组）。在这种管理中，分配的内存不一定是连续的。

大多数操作系统（例如 Windows 和 Linux）使用分段分页（Segmentation with Paging）的方式。一个进程被划分为若干段，每个段都有页。

分区分配方法 #

在分区分配（Partition Allocation）中，当有一个以上的分区可以自由地满足一个进程的要求时，必须选择一个分区。为了选择一个特定的分区，需要一种分区分配方法（partition allocation method）。如果一种分区分配方法能够避免内部碎片（internal fragmentation），则被认为是更好的。

当需要将一个进程加载到主内存时，如果有超过一个足够大的空闲内存块，那么操作系统就会决定分配哪个空闲块。有不同的放置算法（Placement Algorithm）。

• First Fit：首项匹配
• Best Fit：最佳匹配
• Worst Fit：最差匹配
• Next Fit：尾项匹配

First Fit #

在 First Fit 算法中，分配的分区是来自主内存顶部的第一个足够大的块。它从头开始扫描内存并选择第一个足够大的可用块。因此，它分配了第一个足够大的洞（hole）。

Best Fit #

将进程分配到空闲可用分区中第一个最小的充分分区（first smallest sufficient partition）。它搜索整个洞的列表，以找到最小的洞，其大小大于或等于进程的大小。

Worst Fit #

将进程分配到主内存中可自由使用的分区中最大的足够的分区（largest sufficient）。它与最佳匹配算法相反。它搜索整个洞的列表，以找到最大的洞并将其分配给进程。

Next Fit #

Next Fit 与 First Fit 类似，但它将从最后一个分配点搜索第一个足够的分区。

最佳匹配最好吗？ #

尽管最佳匹配使浪费的空间最小化，但它消耗了大量的处理器时间来搜索接近所需尺寸的块。另外，在某些情况下，Best-fit 的表现可能比其他算法要差。

连续内存分配 #

连续内存分配（Contiguous memory allocation）是一种内存分配技术。它只允许以一种连续的方式存储进程数据和代码。因此，整个进程必须作为一个单一的实体存储在内存的一个地方。

静态分区和动态分区 #

有两种流行的技术用于连续的内存分配：静态分区、动态分区。

静态分区 #

静态分区（Static partitioning）是一种固定大小（fixed size）的分区方案。在这种技术中，主内存被预先划分为固定大小的分区。每个分区的大小是固定的，不能被改变。每个分区只允许存储一个进程。

示例：

在固定大小的分区方案下，一个大小为 10KB 的内存可以被划分为固定大小的分区，即：

这些分区在进程到达时被分配给它们，分配给到达的进程的分区取决于所采用的算法。

优势：

• 它简单而容易实现。
• 它支持多程序设计（multiprogramming），因为多个进程可以存储在主内存中。
• 只需要一次内存访问，减少了访问时间。

缺点：

• 它同时受到内部碎片和外部碎片的影响。
• 它对内存的利用效率很低。
• 多重编程的程度受到限制，与分区的数量相等。
• 对进程的大小有限制，因为规模大于最大分区规模的进程不能被存储和执行。

动态分区 #

动态分区（Dynamic Partitioning）是一种可变大小的（variable size）分区方案。它以动态的方式进行分配。当一个进程到达时，一个大小等于进程大小的分区被创建。然后，该分区被分配给该进程。

优势：

• 它不会受到内部碎片的影响。
• 多重编程的程度（Degree of multiprogramming）是动态的。
• 对进程的大小没有限制。

缺点：

• 它受到外部碎片的影响。
• 内存的分配和取消分配很复杂。

伙伴系统内存分配技术 #

静态分区（Static partition）方案存在着活动进程数量固定的限制，而且空间的使用也可能不是最佳的。伙伴系统（buddy system）是一种内存分配和管理算法，它以二次增量幂（power of two increments）来管理内存。假设内存大小为 2^U，假设需要一个大小为 S 的内存。

• 如果2^U-1<S<=2^U（最大容量）：分配整个区块。
• 否则，递归地平均分配区块（不断除以 2），每次都测试此条件，当条件满足时，分配区块并退出循环。

系统还保留了所有未分配块的记录，可以将这些不同大小的块合并成一个大块。

优点：

• 容易实现
• 分配正确大小的区块
• 很容易合并相邻的洞（holes）
• 分配内存和取消分配内存的速度快

缺点：

• 它要求所有的分配单元都是 2 的幂。
• 它导致了内部碎片化

例子：考虑一个有物理地址空间为 128KB 的 buddy system，计算 18KB 进程的分区大小。因此，18KB 进程的分区大小 = 32KB。它除以 2，直到可能得到适合 18KB 的最小块。

固定（或静态）分区 #

在操作系统中，内存管理（Memory Management）是负责分配和管理计算机主内存（main memory）的功能。内存管理功能跟踪每个内存位置的状态，无论是分配还是释放，以确保有效和高效地使用主内存（Primary Memory）。

有两种内存管理技术：连续分配和非连续分配。在连续分配技术中，执行进程必须完全加载在主内存中。连续分配技术可以分为：

• 固定（或静态）分区（Fixed (or static) partitioning）
• 可变（或动态）分区（Variable (or dynamic) partitioning）

固定分区（Fixed Partitioning） #

这是最古老和最简单的技术，用于在主内存中放置一个以上的进程。在这种分区中，RAM 中的分区（非重叠，non-overlapping）数量是固定的，但每个分区的大小可能是相同的，也可能是不相同的。由于它是一个连续的分配（contiguous allocation），因此不允许跨区（spanning）。这里的分区是在进程执行之前或在系统配置期间进行的。

如上图所示，第一个进程只消耗了主内存 4MB 中的 1MB。因此，第一个区块的内部碎片是 (4-1) = 3MB 。每个区块的内部碎片总和 = (4-1)+(8-7)+(8-7)+(16-14)= 3+1+1+2 = 7MB 。

假设大小为 7MB 的进程 P5 到来。但是，尽管有可用的自由空间，但由于连续分配（因为不允许跨区），这个进程不能被容纳。因此，7MB 成为外部碎片（External Fragmentation）的一部分。

固定分区的优点：

• 易于实现。实现固定分区所需的算法很容易实现。它只需要将一个进程放入某个分区，而不需要关注内部和外部碎片的出现。
• 很少的操作系统开销（Little OS overhead）。固定分区的处理需要较少的多余和间接计算能力。

固定分区的缺点：

• 内部碎片化。主内存的使用效率很低。任何程序，无论多么小，都会占据整个分区。这可能导致内部碎片化。
• 外部碎片化。各个分区未使用的总空间（如上所述）不能用于加载进程，即使有可用的空间，但不是以连续的形式加载（因为不允许跨区）。
• 限制进程大小。大于主存储器中的分区大小的进程不能被容纳。分区的大小不能根据进入的进程大小而变化。因此，上述例子中 32MB 的进程大小是无效的。
• 对多程序化程度的限制（Limitation on Degree of Multiprogramming）。主内存（Main Memory）中的分区是在执行前或在系统配置时进行的。主内存被划分为固定数量的分区。假设 RAM 中存在 n1 个分区，并且进程的数量为 n2，那么就必须满足条件 n2<=n1。在固定分区中，进程的数量大于 RAM 中的分区数量是无效的。

可变（或动态）分区 #

它是连续分配技术（Contiguous allocation technique）的一部分。它被用来缓解固定分区所面临的问题。与固定分区相比，分区不是在执行前或在系统配置期间进行的。与可变分区有关的各种特征如下：

• 最初 RAM 是空的，在运行期间（run-time）根据进程的需要进行分区，而不是在系统配置期间进行分区。
• 分区的大小将与进入的进程的大小相等。
• 分区的大小根据进程的需要而变化，这样就可以避免内部碎片，以确保有效地利用 RAM。
• RAM 中的分区数量不是固定的，取决于进入的进程数量和主内存的大小。

与固定分区相比，可变分区有一些优点和缺点，如下所述。

可变分区的优点：

• 没有内部碎片（No Internal Fragmentation）。在可变分区中，主内存的空间是严格按照进程的需要分配的，因此不存在内部碎片化的情况。分区中不会有未使用的空间。
• 对多程序化的程度没有限制（No restriction on Degree of Multiprogramming）。由于没有内部碎片化，可以容纳更多的进程。一个进程可以被加载，直到内存被用完。
• 对进程的大小没有限制（No Limitation on the size of the process）。在固定分区中，如果进程的大小大于最大分区的大小，就不能被加载，而且进程不能被分割，因为在连续分配技术中这是无效的。在可变分区中，进程的大小不能被限制，因为分区的大小是根据进程的大小决定的。

可变分区的缺点：

• 实现困难（Difficult Implementation）。与固定分区相比，实施可变分区是很困难的，因为它涉及到在运行时而不是在系统配置时分配内存。
• 外部碎片化（External Fragmentation）。尽管没有内部碎片，也会有外部碎片。例如，假设在上面的例子中，进程 P1（2MB）和进程 P3（1MB）完成了它们的执行。因此，剩下两个空间，即 2MB 和 1MB。让我们假设大小为 3MB 的进程 P5 到来。内存中的空位不能被分配，因为在连续分配中不允许有跨区。规则规定，进程必须在主内存中连续储存才能被执行。因此，这导致了外部碎片化。

现在，尽管有必要的可用空间，但 3MB 大小的 P5 不能被容纳，因为在连续的情况下不允许跨区。

非连续内存分配 #

分页（Paging）和分段（Segmentation）是允许一个进程的物理地址空间不连续（non-contiguous）的两种方式。它的优点是减少了内存的浪费，但它增加了由于地址转换（address translation）而产生的开销。由于在地址转换中消耗了时间，它减慢了内存的执行速度。

在非连续分配（non-contiguous allocation）中，操作系统需要为每个进程维护一个叫做 "页表"（Page Table）的表格，其中包含了进程在内存空间中获得的每个块的基本地址（base address）。在非连续的内存分配中，一个进程的不同部分被分配到主内存的不同地方。允许跨区（Spanning），这在其他技术中是不可能的，如动态或静态连续内存分配。这就是为什么需要分页来确保有效的内存分配。分页是为了消除外部碎片（External Fragmentation）。

在操作系统中，有五种非连续的内存分配方式：

• 分页（Paging）
• 多级分页（Multilevel Paging）
• 倒置分页（Inverted Paging）
• 分段式（Segmentation）
• 分段分页（Segmented Paging）

工作原理：

一个进程可以以非连续的方式（non-consecutive manner）跨越主存储器中的不同空间。假设进程 P 的大小为 4KB。考虑到主存储器有两个空位（slots），每个空位的大小为 2KB。因此，总的自由空间是 2*2=4KB。在连续的内存分配中，进程 P 不能被容纳，因为不允许跨区。

在连续分配中，内存中的空间应该被分配给整个进程。如果没有，那么这个空间就无法被分配。但是在非连续分配中，进程可以被分成不同的部分，从而填充主内存中的空间。在这个例子中，进程 P 可以被分成两个大小相同的部分 --2KB。因此，进程 P 的一部分可以被分配到主内存的第一个 2KB 空间，进程的另一部分可以被分配到主内存的第二个 2KB 空间。

但是，我们以何种方式划分进程以将其分配到主内存中是非常重要的。进程是在分析了主内存中的空位（empty spaces）数量和它们的大小之后划分的。然后我们才对进程进行划分。这是一个非常耗时的过程。由于主内存中已经存在的进程的执行，空位的数量和大小每次都在变化。

为了避免这个耗时的过程，我们在到达主内存执行之前，提前在二级内存（secondary memory）中划分我们的进程。每个进程都被划分为大小相同的不同部分，称为页（Pages）。我们也将主内存划分为大小相等的不同部分，称为帧（Frames）。其中：进程中的页大小 = 内存中帧的大小。

尽管它们的数字可能不同。下面的图表将使你更好地理解它：考虑空的主内存，每一帧的大小为 2KB，两个进程 P1 和 P2 各为 2KB。

分页允许一个进程的内存地址空间不连续。分页更加灵活，因为只有进程的页面被移动。与连续的内存分配相比，它允许更多的进程驻留（reside）在主内存中。

逻辑地址和物理地址 #

逻辑地址和物理地址的概念 #

逻辑地址（Logical Address）是由 CPU 在程序运行时产生的。逻辑地址是虚拟地址，因为它在物理上不存在，所以它也被称为虚拟地址（Virtual Address）。这个地址被 CPU 用来作为访问物理内存位置（physical memory location）的参考。术语 "逻辑地址空间"（Logical Address Space）是指由一个程序的视角产生的所有逻辑地址的集合。

内存管理单元（Memory-Management Unit）的硬件设备用于将逻辑地址映射到其相应的物理地址。

物理地址（Physical Address）确定了所需数据在内存中的物理位置。用户从不直接处理物理地址，但可以通过其相应的逻辑地址进行访问。用户程序产生逻辑地址并认为程序在这个逻辑地址中运行，但程序的执行需要物理内存，因此，逻辑地址在使用前必须由 MMU 映射到物理地址。物理地址空间（Physical Address Space）这一术语用于与逻辑地址空间中的逻辑地址相对应的所有物理地址。

逻辑和物理地址的区别 #

逻辑地址和物理地址的基本区别是：

• 逻辑地址是由 CPU 从程序的角度产生的，而物理地址是存在于内存单元（memory unit）中的一个位置。
• 逻辑地址空间是 CPU 为程序生成的所有逻辑地址的集合，而映射到相应逻辑地址的所有物理地址的集合被称为物理地址空间。
• 逻辑地址在内存中并不存在，而物理地址是内存中可以被物理访问的位置。
• 相同的逻辑地址是由编译时（Compile-time）和加载时（Load time）的地址绑定方法（address binding）产生的，而在运行时（run-time）的地址绑定方法中它们是不同的。详情请参考这个。
• 逻辑地址是由 CPU 在程序运行时产生的，而物理地址是由内存管理单元（MMU）计算的。

比较表：

虚拟地址到物理地址的映射 #

内存分配技术：

为了存储数据和管理进程，我们需要一个大尺寸的内存，同时，我们需要尽可能快地访问数据。但是，如果我们增加内存的大小，访问时间也会增加，正如我们所知，CPU 总是为二级内存（secondary memory）生成地址，即逻辑地址。但我们想访问主存储器（main memory），所以我们需要将逻辑地址转换为物理地址。

主内存与用户进程和操作系统都有互动。所以我们需要有效地使用主内存。主内存被划分为不重叠的（non-overlapping）内存区域，称为分区。

MMU（内存管理单元） #

虚拟地址和物理地址之间的运行时的映射是由一个称为 MMU 的硬件设备完成的。在内存管理中，操作系统将处理进程并在磁盘（disk）和内存（memory）之间移动进程进行执行。它跟踪可用和已用的内存。

MMU 模式: CPU → MMU → Memory 。

• CPU 将产生逻辑地址，例如：346
• MMU 将产生一个重定位寄存器（relocation register）（基础寄存器，base register），例如：14000
• 在内存中，物理地址被定位，例如：(346+14000=14346)

在地址被发送到内存的时候，重定位寄存器中的值被添加到用户进程产生的每个地址中。用户程序永远不会看到真正的物理地址。程序可以创建一个指向 346 位置的指针，将其存储在内存中，对其进行操作，并与其他地址进行比较。用户程序只产生逻辑地址。然而，这些逻辑地址在使用前必须被映射到物理地址。

地址绑定（Address binding） #

地址绑定（Address binding）是指从一个地址空间映射到另一个地址空间的过程。逻辑地址是 CPU 在执行过程中产生的地址，而物理地址是指内存单元（memory unit）中的位置（被加载到内存中的位置）。逻辑地址要经过 MMU 或地址转换单元（address translation unit）的特别转换。这个过程的输出是确切的物理地址或 RAM 中的代码 / 数据的位置。

地址绑定可以通过三种不同的方式完成：

• 编译时（Compile Time）：在编译时进程将驻留在内存中，那么就会产生一个绝对地址，即物理地址在编译时被嵌入到程序的可执行文件中。将可执行文件作为一个进程加载到内存中是非常快的。但是，如果生成的地址空间被其他进程占据，那么程序就会崩溃，这就需要重新编译程序以改变地址空间。

• 加载时（Load time）：如果在编译时不知道进程将位于何处，那么将生成一个可重定位的地址（relocatable address）。装载器（loader）将可重定位的地址转换为绝对地址。进程在主内存中的基地址（base address）被加载器加到所有的逻辑地址上，以产生一个绝对地址。在此，如果进程的基址发生变化，那么我们需要再次重新加载进程。

• 执行时（Execution time）：指令在内存中，由 CPU 处理。这时可能会分配和 / 或取消分配额外的内存。如果一个进程在执行过程中可以从一个内存移动到另一个内存（动态链接（dynamic linking）-- 在加载或运行时进行链接），就可以使用这个方法。 例如 Compaction。

物理地址的映射 #

在连续内存分配中，从虚拟地址到物理地址的映射并不是一项困难的任务，因为如果我们从二级内存中取出一个进程并将其复制到主内存中，地址将以连续的方式存储，所以如果我们知道该进程的基本地址，我们可以找出下一个地址。

内存管理单元是由 2 个寄存器组合而成：

• 基址寄存器（Base Register）（重新定位寄存器，Relocation Register）。包含进程的起始物理地址。
• 限制寄存器（Limit Register）。指出相对于进程所占区域的基本地址的限制。

CPU 产生的逻辑地址首先由限制寄存器（limit register）检查，如果产生的逻辑地址值小于限制寄存器的值，存储在重定位寄存器中的基址被加到逻辑地址中，得到内存位置的物理地址。如果逻辑地址的值大于限制寄存器的值，那么 CPU 就会向操作系统发出陷阱（traps），操作系统通过给出致命的错误来终止程序。

在非连续内存分配中，进程可以被分配到可用空间的任何地方。非连续内存分配中的地址转换是困难的。有几种技术用于非连续内存分配中的地址转换，如分页、多级分页、倒置分页、分段、分段分页（Paging, Multilevel paging, Inverted paging, Segmentation, Segmented paging）。在这些技术中需要不同的数据结构和硬件支持，如 TLB。

操作系统中的分页 #

分页是一种内存管理方案，它消除了对物理内存连续分配的需要。这种方案允许一个进程的物理地址空间是不连续的。

• 逻辑地址或虚拟地址（用比特表示）。一个由 CPU 生成的地址。
• 逻辑地址空间或虚拟地址空间（以字或字节表示）。由一个程序产生的所有逻辑地址的集合。
• 物理地址（以比特为单位）。存储器单元上实际可用的地址。
• 物理地址空间（用字或字节表示）。与逻辑地址相对应的所有物理地址的集合。

示例：

• 如果 Logical Address = 31 bit, 则 Logical Address Space = 2³¹ words = 2 G words (1 G = 2³⁰)
• 如果 Logical Address Space = 128 M words = 2⁷ * 2²⁰ words, 则 Logical Address = log2 (2²⁷) = 27 bits
• 如果 Physical Address = 22 bit, 则 Physical Address Space = 2²² words = 4 M words (1 M = 2²⁰)
• 如果 Physical Address Space = 16 M words = 2⁴ * 2²⁰ words, then Physical Address = log2 (2²⁴) = 24 bits

从虚拟地址到物理地址的映射是由内存管理单元（MMU）完成的，它是一个硬件设备，这种映射被称为分页技术（paging technique）。

• 物理地址空间在概念上被划分为若干固定大小的块，称为帧（frames）。
• 逻辑地址空间也被分割成固定大小的块，称为页（pages）。
• 页大小 = 帧大小（Page Size = Frame Size）

让我们考虑一个例子：

• 物理地址 = 12 位，那么物理地址空间 = 4K 字
• 逻辑地址 = 13 位，那么逻辑地址空间 = 8K 字
• 页大小 = 帧大小 = 1 K 字（假设）

由 CPU 产生的地址被分为：

• 页数 (p，Page number)。表示逻辑地址空间中的页或页号所需的比特数。
• 页偏移 (d，Page offset)。表示逻辑地址空间的页中的特定字或页大小或页的字数或页偏移所需的比特数。

物理地址被划分为：

• 帧号 (f，Frame number)。表示物理地址空间的帧或帧号所需的比特数。
• 帧偏移 (d，Frame offset)。表示物理地址空间的一帧或一帧大小的特定字或一帧的字数或帧偏移所需的位数。

页表（page table）的硬件实现可以通过使用专用寄存器来完成。但是，只有在页表很小的情况下，页表的使用才会令人满意。如果页表包含大量的条目，那么我们可以使用 TLB（Translation Look-aside buffer），一个特殊的、小型的、快速查找的硬件缓存。

• TLB 是一个可关联的（associative）、高速的存储器（memory）。
• TLB 的每个条目由两部分组成：一个标签和一个值（a tag and a value）。
• 当这个存储器被使用时，一个项目被同时（simultaneously）与所有的标签进行比较。如果找到这个项目，则返回相应的值。

主内存访问时间（Main memory access time）=m，如果页表被保存在主内存中，有效访问时间（Effective access time） = m (页表) + m (页表中的特定页面)

两级分页和多级分页 #

分页是指我们将整个进程转换为同等大小的页（equal-sized pages）的过程。每个页又由固定数量的字组成（如果它是可字寻址的，word addressable）。这些页是由 CPU 产生的虚拟地址表示的。这些页是由 MMU 映射到物理地址的。所以，为了帮助这种映射，我们使用了页表的概念。在页表中，索引代表页号（Page Numbers），内容包含帧号（Frame Number）的地址，即进程在主内存中被实际加载位置。因为虚拟 / 逻辑地址是相对的，应该被映射到主内存的实际物理地址空间。页表的大小可以从页表的每个条目的大小信息计算出来，否则如果没有给定，那么我们可以找到主存中每个帧的地址所需的比特数（这并不正确，但在问题中没有给定的时候应该使用）。即页表大小 = 页表条目数（总页数）*（页表每个条目的大小）。

当页表的大小小于一个 Frame 的大小时，我们不必担心，因为我们可以直接将页表放在主内存的一个 frame 中。因此，我们可以直接访问页表。但是如果 page table 的大小大于 Frame 的大小，那么页表将被分成若干页，这些页表将被存储在主内存中。因此，一个外部页表（Outer Page Table）就出现了。这个外部页表将包含主内存中包含内页表（即页表一页，Inner Page Table）的帧的地址。这个外页（Outer Page）的大小也是按照上面解释的方法计算的，并被用来计算内页表的大小。现在，如果内页表的大小小于或等于一个帧的大小，那么我们就可以止步于此，因为我们能够将最外层的表（outermost table）保持在一个帧中。这就是所谓的两级分页（Two Level Paging）。

例子：考虑给定 Physical Address Space = 2⁴⁴ B，Virtual Address Space = 2³² B，Page Entry = 4B，Page Size = 4KB。所以 No.of Frame = 2³²，No. of Pages Of the Process = 2²⁰，Page Table 1 size =2²⁰ * 4 B= 4 MB。由于它大于 4KB（帧大小）。因此，这个页表必须被转换为页。页表 2（外页表）的页数 = 2²² * 2^-12= 2¹⁰ pages。 所以，外页表的大小 = 2¹⁰ * 4B = 4KB。

因此，在这里我们的外页表（Page Table 2）可以被存储在一个帧中。因此，我们可以到此为止。这就是两级分页，因为这里我们有 2 个页表。

但是，如果页表的大小仍然大于帧大小，那么我们必须继续下去，直到我们达到一个阶段，即最外层表的大小小于帧大小。这个概念被称为多级分页（MultiLevel Paging）。我们的目标应该是将最外层的页表保存在一个帧中。

多级分页 #

多级分页（Multilevel Paging）是一种分页方案，由两个或更多级别的分页表以分层的方式组成。它也被称为分层分页（hierarchical paging）。第一级页表的条目是指向第二级页表的指针，第二级页表的条目是指向第三级页表的指针，依此类推。最后一级页表的条目存储实际的帧信息。第 1 级包含一个单页表（single-page table），该表的地址存储在 PTBR（页表基础寄存器，Page Table Base Register）。

为什么需要它？如果主存的帧大小小于页的大小，而进程不能适应这种方式，那么我们就把页分成更多的页，这个概念被称为多级分页。

虚拟地址：

在多级分页中，不管是哪一级的分页，所有的页表都将存储在主内存中。因此，它需要不止一次的内存访问来获得帧的物理地址。每个级别都需要一次访问。除了最后一级页表条目外，每个页表条目都包含下一级页表的基本地址。

引用真实页帧：

• 第 1 级页表中 PTE 引用 = PTBR 值 + 虚拟地址中存在的第 1 级偏移。
• 第 2 级页表中 PTE 引用 = 基址（存在于第 1 级 PTE 中）+ 第 2 级偏移（存在于 VA 中）。
• 第 3 级页表中 PTE 引用 = 基址（存在于第 2 级 PTE 中）+ 第 3 级偏移（存在于 VA 中）。
• 实际地址 = PTE（存在于第 3 级）。

一般来说，页表的大小将等于页面的大小。

假设字节可寻址（Byte addressable）内存，n 是用于表示虚拟地址的比特数。重要的公式如下：

• Number of entries in page table = (virtual address space size) / (page size) = Number of pages
• Virtual address space size = 2ⁿ B
• Size of page table: <>= (number of entries in page table)*(size of PTE)

如果页表大小 > 帧大小，则再创建 1 层。

缺点：额外的内存引用来访问地址转换表（address translation tables）会使程序的速度降低 2 倍或更多。使用翻译预留缓冲区（TLB，translation look aside buffer ），通过存储页表条目（page table entries）来加速地址翻译。

页表中的页表项 #

页表有页表项（table entries），每个页表项存储一个帧号（frame number）和可选的状态（如保护）位。许多状态位（status bits）在虚拟内存系统（virtual memory system）中使用。PTE 中最重要的东西是帧号。

页表项有以下信息：

• 帧号（Frame Number） - 它给出了你要找的当前页所在的帧号。所需的位数取决于帧的数量。帧位（Frame bit）也被称为地址转换位（address translation bit）。帧的比特数 = 物理内存的大小 / 帧的大小。
• 存在 / 不存在位（Present/Absent bit） - 存在或不存在位表示你正在寻找的特定页面是存在还是不存在。如果它不存在，这被称为 "页面故障"（Page Fault）。如果相应的页面不在内存中，它就被设置为 0。被操作系统用来控制页面故障，以支持虚拟内存（virtual memory）。有时这个位也被称为有效 / 无效位（valid/invalid）。
• 保护位（Protection bit） - 保护位表示你想对该页进行何种保护。所以，这些位用于保护页面框架（读、写等）。
• 引用位（Referenced bit） - 引用位将说明这个页面在上一个时钟周期（clock cycle）是否被引用过。当该页被访问时，它被硬件设置为 1。
• 启用 / 禁用缓存（Caching enabled/disabled） - 有些时候我们需要新鲜的数据。比方说，用户在键盘上输入一些信息，而你的程序应该根据用户的输入来运行。在这种情况下，这些信息将进入主内存。因此，主存储器包含用户输入的最新信息。现在如果你试图把这个页面放到缓存中，这个缓存将显示旧的信息。因此，每当需要新鲜信息（freshness）的时候，我们不希望使用缓存或许多层的内存。存在于离 CPU 最近的一层的信息和存在于离用户最近的一层的信息可能是不同的。因此，我们希望信息必须是一致的，这意味着无论用户给了什么信息，CPU 都应该能够尽可能快地看到它。这就是我们要禁用缓存的原因。所以，这个位启用或禁用页面的缓存。
• 修改位（Modified bit） - Modified bit 表示页面是否被修改过。修改意味着有时你可能试图在页面上写些东西。如果一个页面被修改了，那么每当你要用其他的页面替换这个页面时，修改过的信息应该被保留在硬盘上，或者必须被写回去，或者必须被保存回去。硬件在写入页面时将其设置为 1，用于避免在换出时写入。有时这个修改过的位也被称为 "脏位"（Dirty bit）。

倒置页表 #

以下是结构化（structuring）页表最常见的技术 -- 分层页表（Hierarchical Paging）、哈希页表（Hashed Page Tables）和倒置页表（Inverted Page Tables）。

什么是倒置页表 #

大多数操作系统为每个进程实现了单独的页表，也就是说，对于在多进程（Multiprocessing）/ 分时（Timesharing）操作系统上运行的 "n" 个进程，内存中存储有 "n" 个页表。有时，当一个进程的规模非常大，它占用了虚拟内存，那么随着进程规模的增加，其页表的规模也会大幅增加。

例如一个大小为 2GB 的进程，其页面大小 = 512 字节，页表项的大小 = 4 字节，那么进程中的页数 = 2 GB / 512 B = 2²²，页表大小 = 2²² * 2² = 2²⁴字节。

通过这个例子，可以得出这样的结论：对于在操作系统中同时运行的多个进程，相当一部分内存被页表占据。操作系统还加入了多级分页方案（multilevel paging schemes），进一步增加了存储页表所需的空间，大量的内存被投入到存储页表中。分页表所占用的内存量可能会变成一个巨大的开销，而且这是不可接受的，因为主内存是一种稀缺资源。为了有效地利用内存，并在多编程和有效利用 CPU 的水平上保持良好的平衡，人们做出了各种努力。

倒置页表（Inverted Page Table）：使用倒置页表结构，该结构由主存储器的每一帧的一个页表项组成。因此，倒置页表中的页表项的数量减少到物理内存中的帧的数量，并且用一个页表来表示所有进程的分页信息。通过倒置页表，为每个进程存储一个单独的页表的开销被消除了，只需要固定的一部分内存来一起存储所有进程的分页信息。这种技术被称为倒置分页（inverted paging），因为索引（indexing）是根据帧号而不是逻辑页号来完成的。页表中的每个条目都包含以下字段：

• 页号（Page number） - 它指定了逻辑地址的页号范围。
• 进程 ID（Process id） - 一个倒置页表包含所有正在执行的进程的地址空间信息。由于两个不同的进程可以有一组相似的虚拟地址，因此有必要在反转页表中存储每个进程的进程 ID，以唯一地识别其地址空间（address space）。这是通过使用 PId 和页号的组合来完成的。因此，这个进程标识作为一个地址空间标识符（address space identifier ），确保一个特定进程的虚拟页能够正确地映射到相应的物理帧。
• 控制位（Control bits） - 这些位用于存储与分页有关的额外信息。这些包括有效位（valid bit）、脏位（dirty bit）、引用位（reference bits）、保护位（protection bits）和锁定信息位（locking information bits）。
• 链指针（Chained pointer） - 有时可能会出现两个或更多的进程共享主内存的一部分。在这种情况下，两个或更多的逻辑页映射到同一个页表项，然后用一个链式指针将这些逻辑页的细节映射到根页表（root page table）。

倒置页表的工作原理 #

由 CPU 产生的虚拟地址包含字段，每个页表条目包含分页相关机制中所需要的其他相关信息。当一个内存引用发生时，这个虚拟地址被内存映射单元（MMU，Memory-Mapping unit）匹配，反转页表被搜索并获得相应的帧号。如果在第 1 个条目中找到了匹配，那么进程的物理地址将被作为实际地址发送，否则如果没有找到匹配，就会产生分段故障（Segmentation Fault）。注：反转页表中的条目数 = 物理地址空间（PAS，Physical address Space）中的帧数。

例子：倒置页表及其变种在各种系统中实现，如 PowerPC、UltraSPARC 和 IA-64 架构。在 RT-PC 上的 Mach 操作系统的实现也使用了这种技术。

优点和缺点：

• 减少内存空间（Reduced memory space）：倒置页表通常将存储页表所需的内存量减少到物理内存的大小界限。最大的条目数可以是物理内存中的帧数（page frames）。
• 较长的查找时间（Longer lookup time）：倒置页表是按帧数排序的，但内存查找是相对于虚拟地址进行的，所以，通常需要较长的时间来查找适当的条目，但通常这些页表是用哈希数据结构（hash data structures）来实现的，以提高查找速度。
• 困难的共享内存实现（Difficult shared memory implementation）：由于倒置页表为每一帧存储一个条目，在页表中实现共享内存变得很困难。链式技术（Chaining techniques）被用来将一个以上的虚拟地址映射到按帧号顺序指定的条目上。

哈希页表 #

什么是哈希表？请参见：

在哈希页表（Hashed Page Tables，散列页表）中，虚拟地址中的虚拟页号被散列到散列表中。它们被用来处理高于 32 位的地址空间。哈希表的每个条目都有一个链表，其中的元素被哈希到相同的位置（以避免碰撞（collisions）-- 因为不同的页码可获得相同的哈希函数值）。哈希值就是虚拟页号。虚拟页号（Virtual Page Number）是所有不属于页偏移的比特位。

对于哈希表中的每个元素，有三个字段：

• 虚拟页号（也就是哈希值，Virtual Page Number）。
• 映射的页帧的值。
• 一个指向链表中下一个元素的指针。

关于此图的解释可参见：hash - Explain Hashed page tables in operating system - Computer Science Stack Exchange

虚拟页号与链表第一个元素中的字段 1 进行比较。如果匹配，相应的页帧（字段 2）被用来形成所需的物理地址。否则，链表中的后续条目（subsequent entries）被检查，直到虚拟页号匹配。

参考：

• Hashed PageTables Tutorial-21 - YouTube

为了使这种算法也适用于 64 位地址空间，使用了簇状页表（clustered page tables）。

簇状页表类似于散列页表，不同的是哈希表中的每个条目映射到多页，而不是散列页表中的一页。因此，簇状页表的一个条目可以存储多个物理页帧的映射关系。

簇状页表对于稀疏的地址空间（sparse address spaces）特别有用，其内存引用分散在整个地址空间（非连续的）。

分段（Segmentation） #

一个进程被划分为若干段（Segments）。一个程序被分成的不一定都是相同大小的块（chunks）被称为段（segments）。分段（Segmentation）提供了用户对进程的看法，这是分页所不能提供的。在这里，用户的观点被映射到物理内存上。

分段有多种类型：

• 虚拟内存分段（Virtual memory segmentation）：每个进程被划分为若干段，在任何一个时间点上都不是全部驻留（resident）。
• 简单分段（Simple segmentation）：每个进程被分为若干段，所有这些段在运行时被加载到内存中，尽管不一定是连续的。

在分段中，逻辑地址和物理地址之间的关系并不简单。一个表存储了所有这些段的信息，被称为段表（Segment Table）。

段表将二维逻辑地址映射成一维物理地址。它的每个表项都有：

• 基准地址（Base Address）：它包含段在内存中的起始物理地址。
• 极限（Limit）：它规定了段的长度。

二维逻辑地址到一维物理地址的转换：

由 CPU 产生的地址被分为：

• 段编号（s，Segment number）：代表该段的所需比特数。
• 段偏移（d，Segment offset）：代表段的大小所需的比特数。

分段的优点：

• 没有内部分片（Internal fragmentation）。
• 与页表相比，段表消耗的空间更少。

分段的缺点：

• 当进程从内存中加载和移除时，空闲的内存空间被分割成小块，造成外部碎片（External fragmentation）。

虚拟内存 #

虚拟内存（Virtual Memory）是一种存储分配方案，在这种方案中，二级内存（secondary memory）可以被寻址，就好像它是主内存（main memory）的一部分。程序可能用来引用内存的地址与内存系统用来识别物理存储点（physical storage sites）的地址是有区别的，程序生成的地址被自动转换为相应的机器地址（machine addresses）。

虚拟存储的大小受到计算机系统寻址方案（addressing scheme）的限制，二级存储器的数量不是由主存储位置的实际数量决定的。

它是一种使用硬件和软件实现的技术。它将程序使用的内存地址（称为虚拟地址，virtual addresses）映射为计算机内存中的物理地址。

• 一个进程内的所有内存引用都是逻辑地址，在运行时被动态地转化为物理地址。这意味着一个进程可以从主内存中换入和换出，从而在执行过程中的不同时期占据主内存中的不同位置。
• 一个进程可以被分解成若干片断（pieces），这些片断在执行过程中不需要持续地位于主内存中。这得益于动态运行时地址（dynamic run-time address）转换和使用页或段表的组合。

如果这些特征存在，那么在执行过程中，就不需要所有的页或段都在主内存中出现。这意味着所需的页面需要在需要的时候被加载到内存中。虚拟内存是使用按需分页（Demand Paging）或按需分段（Demand Segmentation）来实现的。

按需分页 #

按需加载页面到内存的过程（无论何时发生页面故障）被称为需求分页（Demand Paging）。

这个过程包括以下步骤：

• 如果 CPU 试图引用一个目前在主内存中不可用的页面，它将产生一个中断（interrupt），表示一个内存访问故障（memory access fault）。
• 操作系统将被中断的进程置于一个阻塞（blocking）状态。为了继续执行，操作系统必须将所需的页面带入内存。
• 操作系统将在逻辑地址空间（logical address space）中搜索所需的页面。
• 所需的页将被从逻辑地址空间带到物理地址空间。页面替换算法（page replacement algorithms）被用来决定替换物理地址空间中的页面。
• 页表（page table ）将被相应地更新。
• 信号将被发送到 CPU 以继续程序的执行，它将使进程回到准备（ready）状态。

优势:

• 在主内存中可以维持更多的进程。因为我们将只加载任何特定进程的一些页面，所以有空间容纳更多的进程。这使得处理器更有效地被利用，因为在任何特定时间，更多的进程中至少有一个处于准备状态。
• 编程中最基本的限制之一，即一个进程可能比所有的主存储器都大，被解除了。由于按需分页的存在，一个大于主内存的进程可以被执行。操作系统本身根据需要在主内存中加载一个进程的页面。 通过为每个进程使用较少的可用（主）内存，它允许更大的多程序水平。

页故障服务时间（Page Fault Service Time）:

为页故障提供服务的时间被称为页故障服务时间。页面故障服务时间包括执行上述所有六个步骤所需的时间。假设主内存访问时间（Main memory access time）为：m，页面故障服务时间（Page fault service time）为：s，页面故障率（Page fault rate）为：p，那么，有效内存访问时间 = (p*s) + (1-p)*m 。

调换（Swapping）：

将一个进程换出意味着从内存中删除它的所有页面，或者标记它们，使它们被所需页面替换进程所删除。暂停一个进程可以确保它在被换出的时候不能运行。在以后的某个时间，系统会将该进程从二级存储（secondary storage）中换回主内存。当一个进程忙于换入和换出页面时，这种情况被称为激动（thrashing）。

Thrashing #

在任何时候，任何进程都只有几个页面在主内存中，因此可以在内存中维持更多的进程。此外，由于未使用的页面不被换入和换出内存，因此节省了时间。然而，操作系统必须对如何管理这一方案进行巧妙的处理。在稳定状态（steady-state）下，所有的主内存都将被进程页占据，因此处理器和操作系统可以直接访问尽可能多的进程。因此，当操作系统换入一个页面时，它必须换出另一个页面。如果它在一个页面被使用之前就把它换出，那么它就必须几乎立即再次获得这个页面。这种情况太多，就会导致一种被称为 Thrashing 的情况，系统将大部分时间花在交换页面而不是执行指令上。因此，需要一个好的页面替换算法。

最初的多程序化程度达到一定程度的点 (λ)，CPU 的利用率增高，系统资源被 100% 利用。但是，如果我们进一步增加多编程的程度，CPU 的利用率将急剧下降，系统将花费更多的时间在页面替换（page replacement）上，完成进程执行的时间将增加。系统中的这种情况被称为激动（thrashing）。

Thrashing 的原因 :

• 高度的多程序化（High degree of multiprogramming）：如果内存中的进程数量不断增加，那么分配给每个进程的帧的数量将减少。因此，每个进程可用的帧数将减少。由于这个原因，页面故障（page fault）将更频繁地发生，更多的 CPU 时间将被浪费在换入和换出页面上，利用率将不断下降。比如说，空闲的 frames=400，情况 1：进程的数量 = 100，那么，每个进程将得到 4 个 frame。情况 2：进程数 = 400，每个进程将得到 1 个帧。这是一个 Thrashing 的情况，随着进程数的增加，每个进程的帧数会减少。因此，CPU 时间将被消耗在交换页面上。
• 缺少帧（Lacks of Frames）。如果一个进程的帧数较少，那么该进程能够驻留在内存中的页数就会减少，因此需要更频繁的换入和换出。这可能会导致 thrashing。因此，必须为每个进程分配足够数量的帧，以防止 thrashing。

崩溃的恢复：

• 通过指示长期调度器（long-term scheduler）不要在阈值（threshold）之后将进程带入内存，不允许系统进入 thrashing 状态。
• 如果系统已经处于 thrashing 状态，那么指示中期调度器（mid-term scheduler）暂停一些进程，以便我们能够从 thrashing 中恢复系统。

页面替换算法 #

在一个使用分页进行内存管理的操作系统中，需要一个页面替换算法来决定当一个新的页面进入时，哪个页面需要被替换。

页故障（Page Fault）：当一个正在运行的程序访问一个映射到虚拟地址空间但没有加载到物理内存中的内存页时，就会发生页故障。由于实际的物理内存要比虚拟内存小得多，所以会发生了页面故障。在发生页面故障的情况下，操作系统可能不得不用新需要的页面替换现有的一个页面。不同的页面替换算法提出了不同的方法来决定替换哪个页面。所有算法的目标都是为了减少页面故障的数量。

页面替换算法（Page Replacement Algorithms）：

先入先出（FIFO） #

这是最简单的页面替换算法。在这种算法中，操作系统在一个队列中跟踪内存中的所有页面，最老的页面在队列的前面。当一个页面需要被替换时，队列前面的页面被选择移除。

示例：考虑页面参考字符串 1，3，0，3，5，6，3，有 3 个页面帧，找出页面故障的数量。

最初，所有的槽都是空的，所以当 1、3、0 来的时候，它们被分配到空的槽里 -->3 个页面错误。

当 3 到来时，它已经在内存中了，所以 ->0 页故障。然后 5 来了，它在内存中不可用，所以它取代了最老的页槽，即 1。6 来了，它在内存中也不可用，所以它取代了最老的页槽，即 3->1 页故障。最后，当 3 来时，它是不可用的，所以它取代了 0->1 页故障。

Belady 的反常现象（Belady’s anomaly）证明，在使用先进先出（FIFO）的页面替换算法时，增加页面帧的数量，有可能出现更多的页面故障。例如，如果我们考虑参考字符串 3，2，1，0，3，2，4，3，2，1，0，4 和 3 个槽，我们得到 9 个总的页面故障，但如果我们把槽增加到 4，我们得到 10 个页面故障。

参考：

• Belady's Anomaly in Page Replacement Algorithms - GeeksforGeeks

最优页面替换（Optimal Page replacement） #

在这种算法中，将替换那些在未来最长时间内不会被使用的页面。

示例：考虑页面参考 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 与 4 个页面框架。找到页面故障的数量。

最初，所有的槽都是空的，所以当 7 0 1 2 被分配到空的槽里时 ->4 个页面故障。然后 0 被命中，所以 -> 0 页故障。当 3 来的时候，它将取代 7 的位置，因为它在未来最长的时间里没有被使用。 -> 1 页故障。0 已经在那里了，所以 -> 0 页故障。4 将取代 1->1 页故障。现在，对于进一步的页面引用字符串 ->0 页面故障，因为它们在内存中已经可用。

最佳页面替换是完美的，但在实践中是不可能的，因为操作系统不能知道未来的请求（future requests）。最佳页面替换的用途是建立一个基准，以便其他替换算法可以对照它进行分析。

最近最少使用（Least Recently Used） #

在这种算法中，页面将被替换为最近使用最少的。

示例：考虑页面参考字符串 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 与 4 个页面帧。找出页面故障的数量。

最初，所有的槽位都是空的，所以当 7 0 1 2 被分配到空槽位时 -> 4 页故障；当 3 出现时，它将取代 7，因为它是最近使用的最少的 -->1 页故障。0 已经在内存中了，所以 ->0 页故障。4 将取代 1 的位置 -> 1 页故障。现在，对于更多的页面引用字符串 ->0 页面故障，因为它们在内存中已经可用。

最近最多使用（MRU，Most Recently Used） #

在这种算法中，最近使用过的页面将被替换，可能会出现贝拉迪异常现象（Belady’s anomaly）。

内存管理中的叠加（Overlays） #

固定分区的主要问题是，一个进程的大小必须受到最大分区大小的限制，这意味着一个进程永远不能跨越另一个进程。为了解决这个问题，早期人们使用了一些解决方案，这被称为叠加（Overlays）。

叠加（overlays）的概念是，当一个进程运行时，它不会同时使用完整的程序，它将只使用其中的一部分，无论你需要哪一部分，你都要加载它，一旦这个部分完成了，你就把它卸载下来，也就是把它拉取你需要的部分，然后运行它。从形式上看，即为 "将程序代码块或其他数据转移到内部存储器中，取代已经存储的数据的过程"。有时会发生这样的情况，与最大的分区的大小相比，程序的大小会更大，那么在这种情况下，你应该使用叠加（overlays）。

因此，叠加是一种通过只保留那些在任何时候都需要的指令和数据来运行比物理内存大小更大的程序的技术。将程序分成模块（modules），不需要所有模块在同一时间出现在内存中。

优势：

• 减少对内存的要求
• 减少时间要求

缺点：

• 重叠图（Overlap map）必须由程序员指定
• 程序员必须知道内存需求（memory requirement）
• 重叠的模块（Overlapped module）必须是完全不相干的
• 重叠结构的编程设计很复杂，并非在所有情况下都能做到