一下操作系统是如何创建内存并管理他们的？模型

主存储器 (RAM) 是一种非常重要的资源，必须小心对待。虽然目前大多数内存的增长速度比 IBM 7094 快得多，但程序大小的增长速度却比内存快得多。正如帕金森定律所说：无论内存有多大，程序大小的增长速度都比内存容量快得多。让我们探索一下操作系统是如何创建和管理内存的。

经过多年的讨论，提出了一种内存层次结构，下面是层次结构的分类

顶级内存速度最高，但容量最小，成本非常高。层次结构越低，访问效率越慢，容量越大，但成本越便宜。

操作系统中管理内存层次结构的部分称为内存管理器，它的主要工作是有效地管理内存，跟踪正在使用的内存，在进程需要时分配内存，在进程需要时回收内存。已经完成了 。

下面我们将讨论不同的内存管理模型，从简单到复杂。由于最底层的缓存是由硬件管理的，所以我们主要讨论主存模型以及如何管理主存。

无记忆抽象

最简单的内存抽象是无存储。早期的大型机（1960 年代之前）、小型机（1970 年代之前）和个人计算机（1980 年代之前）没有内存抽象。每个程序都可以直接访问物理内存。当程序执行以下命令时：

MOV REGISTER1, 1000

计算机会将物理内存位置 1000 的内容移动到 REGISTER1。因此，当时呈现给程序员的内存模型是物理内存玩游戏应用程序错误 该内存不能为read，内存地址从0开始到最大内存地址，每个地址包含一个8位单元。

所以在这种情况下，一台计算机不能同时在内存中有两个应用程序。如果第一个程序将一个值写入内存中地址 2000 的该位置，该值将替换第二个程序在该位置的值，因此同时运行两个应用程序将无法工作。该程序将立即崩溃。

但即使内存模型是物理内存，也有一些选择。三种变体如下所示

在上图a中，操作系统位于RAM（随机存取存储器）的底部，或如图b所示位于ROM（只读存储器）的顶部；而在图 c 中，设备驱动程序位于顶部的 ROM 中，而操作系统位于底部的 RAM 中。图a中的模型以前用于大型机和小型机，但现在很少使用；图 b 中的模型通常用于手持或嵌入式系统。第三种模型用于早期的个人计算机。ROM 系统的一部分成为 BIOS（基本输入输出系统）。模型 a 和 c 的缺点是用户程序中的错误可能会破坏操作系统，从而产生潜在的灾难性后果。

当以这种方式组织系统时，通常一次只能运行一个线程。一旦用户输入命令，操作系统将所需程序从磁盘复制到内存并执行；该过程完成后，操作系统会在用户终端上显示提示并等待新命令。收到新命令后，它会将新程序加载到内存中，覆盖之前的程序。

在没有内存抽象的系统中实现并行性的一种方法是使用多线程进行编程。由于同一进程中的多个线程在内部共享相同的内存映像，因此实现并行性不是问题。

运行多个程序

然而，即使没有内存抽象，也可以同时运行多个程序。操作系统只需要将当前内存中的所有内容保存到磁盘文件中，然后再将程序读入内存即可。只要一次只有一个程序，就不会有冲突。

在额外的特殊硬件的帮助下，即使没有交换也可以并行运行多个程序。IBM 360 早期模型就是这样解决的

System/360是IBM于1964年4月7日推出的划时代的大型计算机。该系列是世界上第一台指令集兼容计算机。

在 IBM 360 中，内存被划分为 2KB 的区域块，每个区域分配一个 4 位的保护密钥，保护密钥存储在 CPU 的一个特殊寄存器中。1MB内存的机器只需要512个这样的4位寄存器，总容量为256字节（这个会算）。PSW（Program Status Word，程序状态字）中有一个4位代码。如果正在运行的进程使用与其 PSW 代码不同的密钥访问内存，360 硬件会检测到这一点，因为只有操作系统才能修改保护密钥，从而防止进程、用户进程和操作系统之间的干扰。

这个解决方案有一个缺陷。如下图，假设有两个程序，每个程序大小为 16 KB

从图中可以看出，这是两个不同的16KB程序的加载过程。a 程序会先跳转到地址 24，这里是一条 MOV 指令，而 b 程序会先跳转到地址 28，地址 28 是一条 CMP 命令。这是两个程序一个接一个地加载到内存中的情况。如果两个程序同时加载到内存中，并从地址0开始，则内存的状态如上图c所示。程序加载后，开始运行。一个程序从地址0开始，执行JMP 24指令，然后依次执行后面的指令（很多指令没有显示），一段时间后，执行第一个程序，然后执行第二个程序。第二个程序的第一条指令是 28。该指令将导致程序跳转到第一个程序的ADD，而不是预先设置的跳转指令CMP。由于对内存地址的访问不正确，这个程序可能会在 1 秒内崩溃。

同时执行上述两个程序的核心问题是，两者都引用了绝对物理地址。这不是我们想看到的。我们想要的是每个程序都会引用一个私有的本地地址。IBM 360 使用一种称为静态重定位的技术在第二个程序加载到内存时对其进行修改。它的工作原理如下：当在地址 16384 加载程序时，常数 16384 被添加到每个程序地址（因此 JMP 28 变为 JMP 16412）。尽管此机制可以正常工作，但它不是通用解决方案，并且会减慢加载速度。更进一步，它需要所有可执行程序中的额外信息来指示哪些包含（可重定位）地址，哪些不包含。毕竟，上面b中的JMP 28可以重定向（修改），而像MOV REGISTER1，28 将数字 28 移动到 REGISTER 不会。因此，加载器（loader）需要一定的区分地址和常量的能力。

内存抽象：地址空间

将物理内存暴露给进程有几个主要缺点：首先，如果用户程序可以寻址内存的每个字节，它们很容易破坏操作系统，使系统陷入停顿（除非使用锁键模式，如IBM 360 或特殊硬件进行保护）。即使只有一个用户进程正在运行，也存在此问题。

第二点，这个模型很难运行多个程序（如果只有一个CPU，就是顺序执行）。在个人电脑上玩游戏应用程序错误 该内存不能为read，一般会打开很多应用程序，比如输入法、电子邮件、浏览器等，这些进程会有一个进程在不同的时间运行，其他的应用程序都可以通过鼠标来唤醒。系统中没有物理内存就很难实现。

地址空间的概念

如果要让多个应用程序同时在内存中运行，则必须解决两个问题：保护和重定位。让我们看看 IBM 360 是如何解决的：第一个解决方案是用保护密钥标记一块内存，并将执行过程的密钥与提取的每个存储单词的密钥进行比较。这种方法只能解决第一个问题，但仍然不能解决多个进程同时在内存中运行的问题。

更好的方法是创建内存抽象：地址空间。正如进程的概念创建了 CPU 的抽象来运行程序一样，地址空间也创建了内存的抽象供程序使用。地址空间是进程可以用来寻址内存的一组地址。每个进程都有自己的地址空间，独立于其他进程的地址空间，但有些进程可能希望共享地址空间。

基址寄存器和索引寄存器

最简单的方法是使用动态重定位，这是一种将每个进程的地址空间映射到物理内存的不同区域的简单方法。从 CDC 6600（世界上最早的超级计算机）到 Intel 8088（最初的 IBM PC 的核心）使用的经典方法是为每个 CPU 配置两个特殊的硬件寄存器，通常称为基本寄存器和索引寄存器。寄存器（限制寄存器）。当使用基址和索引寄存器时，程序被加载到内存中的一个连续空间中，并且在加载过程中不需要重定位。当一个进程运行时，程序的起始物理地址被加载到基址寄存器中，程序的长度被加载到索引寄存器中。在上面的图c中，当一个程序运行时，加载到这些硬件寄存器中的基址和索引寄存器值分别为 0 和 16384。第二个程序运行时，这些值分别是16384和32768。如果第三个 16 KB 的程序直接加载到第二个程序的地址并执行，则基址和索引寄存器的值将分别为 32768 和 16384。那么我们可以得出结论

每当进程引用内存以获取指令或读取或写入数据字时，CPU 硬件会自动将基地址值添加到进程生成的地址上，然后再将其发送到内存总线上。同时检查程序提供的地址是否等于或大于变址寄存器中的值。如果程序提供的地址超出变址寄存器的范围，则会产生错误并中止访问。这样，执行上图c中的JMP 28指令后，硬件会将其解释为JMP 16412，所以程序可以跳转到CMP指令，流程如下

使用基址和索引寄存器是为每个进程提供私有地址空间的一种非常好的方法，因为每个内存地址在发送到内存之前都带有基址寄存器的内容。在许多实际系统中，基址和索引寄存器受到保护，只有操作系统才能修改它们。CDC 6600 提供了对这些寄存器的保护，但 Intel 8088 没有，甚至没有索引寄存器。然而，英特尔 8088 提供了许多允许程序代码和数据独立重定位的基址寄存器，但不提供针对超出范围的内存引用的保护。

所以你可以知道使用基址寄存器和变址寄存器的缺点，每次访问内存时，都会执行ADD和CMP操作。比较可以很快进行，但加法会比较慢，除非使用特殊的加法电路，否则会因进位传播时间而减慢。

交换技术

如果计算机的物理内存足够大，可以容纳所有进程，那么前面提到的方案或多或少是可行的。但实际上，所有进程所需的 RAM 总量远高于内存量。在 Windows、OS X 或 Linux 中，计算机完成启动（Boot）后，大约会启动 50 – 100 个进程。例如，当安装 Windows 应用程序时，它通常会发出命令，以便在随后的系统启动时，将启动一个进程，该进程除了检查应用程序的更新之外什么都不做。一个简单的应用程序可能会使用 5 – 10MB 的内存。其他后台进程检查电子邮件、网络连接和许多其他此类任务。这一切都发生在第一个用户开始之前。今天，像 Photoshop 这样的重要用户应用程序只需要 500 MB 即可启动，但是一旦他们开始处理数据，他们可能需要数 GB 才能处理。这样一来，始终将所有进程都保存在内存中需要大量的内存，如果内存不够，就无法做到。

因此，针对上述内存不足的问题，提出了两种处理方法：最简单的方法是交换技术，即将一个进程完全转移到内存中，然后在内存中运行一段时间，然后将其放入内存中。回到磁盘。空闲进程存储在磁盘上，因此这些进程在不运行时不会占用太多内存。另一种策略叫做虚拟内存（virtual memory），虚拟内存技术可以让应用程序的一部分在内存中运行。让我们先讨论交换

交换过程

以下是换货流程

一开始只有进程A在内存中，然后进程B和进程C被创建或者从磁盘交换到内存中，然后在图d中，A从内存中被交换到磁盘，最后A又回来了。因为进程A在图 g 中现在位于不同的位置，它需要在加载期间重新定位，或者在交换程序时通过软件进行，或者在程序执行期间通过硬件进行。基址寄存器和变址寄存器适合这种情况。

交换在内存中创建了多个空闲区域（空洞），内存将所有空闲区域尽可能向下移动，并将它们合并为一个大的空闲区域。这种技术称为内存压缩。但是这种技术通常不会被使用，因为它会消耗大量的 CPU 时间。例如，在一台 16GB 内存的机器上，每 8ns 复制 8 个字节，压缩整个内存大约需要 16s。

一个值得注意的问题是，在创建进程或将其交换到内存时，应该为其分配多少内存。如果一个进程以固定大小创建并且从不改变，那么分配策略会更简单：操作系统会根据需要进行分配。

但是如果进程的数据段可以自动增长，比如在堆中动态分配内存，那肯定会有问题。这里再次提到什么是数据段。从逻辑层面来说，操作系统将数据分成不同的段（不同的区域）来存储：

也称为文本段，用于存储指令和运行代码的内存空间

这个空间的大小是在代码运行之前确定的

内存空间一般是只读的，有些架构的代码也允许可写

在代码段中，还可能存在一些只读的常量变量，比如字符串常量等。

读和写

存储初始化的全局变量和初始化的静态变量

数据段中数据的生命周期随程序持久（persistent with the process），随进程持久：进程创建时存在，进程死亡时消失

读和写

存储未初始化的全局变量和未初始化的静态变量

bss 段中数据的生命周期与进程保持一致

bss段中的数据一般默认为0

只读数据，例如 printf 语句中的格式字符串和 switch 语句的跳转表。也就是恒定面积。例如， const int ival = 10 在全局范围内， ival 存储在 .rodata 部分；另一个例子，printf(“Hello world %d\n”, c); 中的格式字符串；函数本地范围内的语句“Hello world %d\n”，也存储在 .rodata 部分中。

读和写

存储的是函数或代码中的局部变量（非静态变量）

堆栈的生命周期随着代码块继续。当代码块运行时，代码块会为你分配空间。当代码块结束时，空间会被自动回收。

读和写

存储程序执行期间动态分配的 malloc/realloc 空间

堆的生命周期随着进程持续存在，从 malloc/realloc 到 free

这是我们用 Borland C++ 编译后的结果

_TEXT   segment dword public use32 'CODE'
_TEXT   ends
_DATA   segment dword public use32 'DATA'
_DATA   ends
_BSS    segment dword public use32 'BSS'
_BSS    ends

段定义（segment）用于区分或划分范围区域的含义。汇编语言中的segment指令表示段定义的开始，ends指令表示段定义的结束。段定义是一个连续的内存空间

因此，处理内存自动增长区域的方法有3种。

上述方法仅用于单个或少数需要增长的进程​​。如果大部分进程需要在运行时增长，为了减少内存区域不足导致的进程交换和移动的开销，一个可用的方法是，在进程被换入或移动时为其分配一些额外的内存。但是，当一个进程被换出到磁盘时，只需要换出实际使用的内存，换出多余的内存也是一种浪费。这是为两个进程分配增长空间的内存配置。

如果进程有两个可增长的段，例如一个数据段用作堆（全局变量），用于动态分配和释放变量，一个堆栈段用于局部变量和返回地址，如图b所示。图中可以看到，所示进程的堆栈段在进程占用的内存顶部向下增长，然后在紧接程序段之后的数据段处向上增长。当为增长预留的内存区域不够时，处理方法同上流程图（数据段自动增长的三种处理方法）。

空闲内存管理

当内存被动态分配时，操作系统必须管理它。从广义上讲，有两种方法可以监控内存使用情况

接下来，我们将讨论这两种使用方式

使用位图进行存储管理

当使用位图方法时，内存可能被划分为小至几个字或大至几千字节的分配单元。每个分配单元对应位图中的一个位，0 表示空闲，1 表示占用（反之亦然）。一个内存区域及其对应的位图如下

图a表示一段内存，有5个进程，3个空闲区，比例为内存分配单位，阴影区表示空闲（位图中用0表示）；图b表示对应的位图；图c表示链表相同的信息

分配单元的大小是一个重要的设计因素，分配单元越小，位图越大。然而，即使使用 4 字节的分配单元，32 位内存也只需要位图中的 1 位。32n位内存需要n位位图，所以1个位图只占内存的1/32。如果选择更大的内存单元，位图应该更小。如果进程的大小不是分配单元的整数倍，那么在最后一个分配单元中浪费了大量内存。

位图提供了一种简单的方法来跟踪固定大小内存中的内存使用情况，因为位图的大小取决于内存和分配单元的大小。这种方法的一个问题是，当决定将具有 k 个分配单元的进程放入内存时，内存管理器必须在位图中搜索能够运行 k 个连续零位的位图。细绳。在位图中查找指定长度的连续0串是非常耗时的操作，这是位图的一个缺点。（可以简单理解为在杂乱无章的数组中寻找一长串空闲数组单元）

用链表管理

跟踪内存使用情况的另一种方法是维护已分配和空闲内存段的链表，其中可能包含一个或两个进程的空闲区域。内存使用情况可以用上面的图 c 表示。链表中的每一项都可以代表一个空闲区域（H）或进程（P）开始标志、长度和下一个链表项的位置。

在此示例中，段列表按地址排序。这种方法的优点是在进程终止或交换时更新列表很简单。一个终止的进程通常有两个邻居（除了内存的顶部和底部）。相邻的可能是进程或空闲区域，它们有四种组合。

当按地址顺序在链表中存储进程和空闲区域时，有几种算法可以为创建的（或从磁盘换入的）进程分配内存。让我们首先假设内存管理器知道应该分配多少内存，最简单的算法是使用先拟合。内存管理器扫描段列表，直到找到足够大的空闲区域。除非空闲区域的大小与要分配的空间大小相同，否则空闲区域分为两部分，一部分供进程使用；另一部分生成一个新的空闲区域。第一次拟合算法是一种快速算法，因为它尽可能多地搜索链表。

第一次拟合的小变化是下一次拟合。和第一次匹配的方式一样，唯一不同的是下次匹配每次找到合适的空闲区域时都会记录当前位置，这样下次找到空闲区域时，就会从结束的地方开始最后一次搜索，而不是像第一次匹配算法那样每次都从头开始。Bays(1997)证明了下一个算法的性能略低于第一个匹配算法。

另一种众所周知且广泛使用的算法是最合适的。最佳拟合会从头到尾搜索整个链表，以找到可以容纳该进程的最小空闲区域。最佳拟合算法将尝试找到最接近实际需要的空闲区域，以最佳匹配请求和可用空闲区域，而不是一次分割一大块空闲区域以供以后使用。比如现在我们需要一个大小为2的块，那么第一个匹配算法会分配位置5的空闲区域的块，而最佳匹配算法会分配位置18的空闲区域的块，如下

那么最佳拟合算法的表现如何呢？最佳拟合遍历整个链表，因此最佳拟合算法的性能比第一次匹配算法差。但令人惊讶的是，best-fit算法比first-match和next-match算法浪费更多的内存，因为它会产生很多无用的小缓冲区，而first-match算法产生的空闲区域会更大。

最适合的自由区域将分成许多非常小的缓冲区。为避免此问题，请考虑使用最差拟合算法。也就是说，总是分配最大的内存区域（所以你现在明白了为什么最佳拟合算法会分割许多小缓冲区），使新分配的空闲区域更大，以便它可以继续使用。仿真程序表明，最差拟合算法也不是一个好主意。

如果为进程和空闲区域维护单独的链表，则可以提高所有四种算法的速度。这样，这四种算法的目标是检查空闲区域而不是进程。但是这种增加的分配速度的一个不可避免的成本是增加了复杂性和更慢的内存释放，因为回收的段必须从进程链表中删除并插入到空闲链表区域中。

如果进程和空闲区使用不同的链表，可以对空闲区链表进行大小排序，以提高最佳拟合算法的速度。当使用最佳匹配算法搜索从小到大排列的空闲区域链表时，只要找到合适的空闲区域，这个空闲区域就是能够容纳作业的最小空闲区域，因此是最佳匹配。由于空闲区域链表被组织为单链表，因此不需要进一步搜索。当空闲区域链表按大小排序时，first fit算法和best fit算法一样快，next fit算法在这里没有意义。

另一种分配算法是快速拟合算法，它为那些常见大小的空闲区域维护单独的链表。例如，有一个有n个项目的表，表的第一项是指向4KB大小的空闲区链表头的指针，第二项是指向空闲区链表头的指针大小为 8 KB，第三项是指向大小为 12 KB 的空闲区域链表头部的指针，以此类推。例如，21KB这样的空闲区域可以放在20KB的链表中，也可以放在具有特殊存储大小的空闲区域的链表中。

快速匹配算法对于给定的货物找到空闲区域也非常快，但它与所有按大小对空闲区域进行排序的方案一样，有一个共同的缺点，即当进程终止或被换出时，它看起来因为它的相邻块并查看它们是否可以合并的过程非常耗时。如果没有合并，内存将很快分裂成大量进程无法使用的小的空闲区域。

文章参考：

内存/103614?fr=aladdin

数据段/5136260?fromtitle=data%20segment&fromid=18082638&fr=aladdin

现代操作系统第四版

《现代操作系统》第四期

硬盘/3947233?fr=aladdin