7 Main Memory¶

7.1 Background¶

程序必须从磁盘加载到内存并置于进程上下文中才能执行，而CPU只能直接访问主存和寄存器：寄存器访问极快（通常1个时钟周期以内），主存则慢得多，需多个周期；为弥合速度差距，现代系统在两者之间引入高速缓存（Cache）；同时，为保障系统安全与稳定，还需内存保护机制防止进程越界访问。

逻辑地址空间与物理地址空间的分离是内存管理的核心概念。

逻辑地址（又称虚拟地址或相对地址）由CPU生成，是程序在编译或汇编后产生的地址，通常以0为起始，其他地址相对于首地址进行偏移，用户程序使用的是这种地址，但不能直接用于内存访问。
物理地址（又称绝对地址或实地址）是内存单元的实际地址，由内存硬件直接识别和寻址。

操作系统通过地址转换机制将逻辑地址映射为物理地址，从而实现内存的高效、安全管理和多任务隔离。

基址寄存器（base register）和限长寄存器（limit register）共同定义了一个进程的逻辑地址空间：基址寄存器存储该进程在物理内存中的起始地址，限长寄存器则记录其地址空间的大小。当CPU生成一个逻辑地址时，系统会将其与限长寄存器中的值比较，若超出范围则触发越界异常；否则将逻辑地址加上基址寄存器的值，得到对应的物理地址，从而实现对内存的保护和隔离，确保每个进程只能访问自己的合法内存区域。

现代操作系统多采用分页机制

指令和数据的地址绑定（即地址映射或重定位）可以在三个不同阶段发生：

编译时，如果内存位置在编译前已知，可生成绝对代码，但一旦起始地址改变就需要重新编译；
装入时，若编译时未知内存位置，则需生成可重定位代码，在程序装入内存时进行地址调整；
运行时，当进程在执行过程中可能被移动到不同内存段时，地址绑定延迟到运行时完成，此时需要硬件支持（如基址和限长寄存器）来动态实现地址转换，从而实现灵活的内存管理与保护。

一个用户程序是如何被加载到内存中的呢？

内存管理单元（MMU）是一种硬件设备，负责将用户程序生成的逻辑地址（虚拟地址）映射为物理地址。在MMU的工作机制中，每当用户进程产生一个逻辑地址并发送到内存时，系统会将重定位寄存器（relocation register）中的基址值加到该地址上，从而得到对应的物理地址。这一过程对用户程序是透明的，即程序始终使用逻辑地址进行访问，永远不会直接看到或操作实际的物理地址，从而实现了地址空间的隔离与保护，支持多任务环境下的安全内存管理。

重定位寄存器实际上就是机制寄存器

动态装入（Dynamic Loading）是一种在程序运行过程中按需加载外部库的技术。与静态链接不同，使用动态装入时，外部库不会在进程启动时就被加载到内存中，而是以可重定位的形式存储在磁盘上，仅在程序实际调用相关函数时才被加载。这种方式提高了内存空间的利用率，因为未使用的代码不会被载入内存

动态装入不需要操作系统提供特殊支持，主要通过程序设计实现，具有良好的灵活性和效率。

动态链接（Dynamic Linking）是一种在程序运行时将外部库函数与程序连接的机制，允许共享库（如 Linux 中的 .so 文件或 Windows 中的 .dll 文件）被预先加载到共享内存中。当进程调用某个库函数时，系统会确定该函数在内存中的物理地址，并通过一个称为“存根”（stub）的小段代码来定位并执行对应的库例程；存根在首次调用时会被替换为实际的函数地址，从而实现高效访问。操作系统负责检查该例程是否已存在于进程的内存空间中，若未加载则进行映射。动态链接特别适用于频繁使用的公共库，可实现多个进程共享同一份库代码，节省内存和磁盘空间，因此也被称为“共享库”（shared libraries），其典型形式即为动态链接库（Dynamically Linked Library）。

7.2 Swapping¶

交换技术（Swapping）是一种内存管理机制，允许将一个进程的整个内存映像暂时从主存移出到磁盘上的备份存储区（backing store），并在需要时再调回内存继续执行。

备份存储区通常是高速磁盘空间，用于存放所有用户进程的内存镜像，如Linux和UNIX系统中的“交换区”（swap space），Windows系统中的“交换文件”（pagefile.sys）。

在优先级调度中，系统可采用“调出（roll out）”和“调进（roll in）”策略：低优先级进程被换出，以便为高优先级进程腾出内存空间。交换过程的主要开销是数据传输时间，与交换数据量成正比。

现代操作系统（如UNIX、Linux、Windows）都实现了改进的交换机制，并维护一个就绪队列，包含已在磁盘上保存其内存镜像、随时可调入运行的进程，以提高系统整体资源利用率和响应能力。

现代操作系统（如 UNIX、Linux 和 Windows）通常默认禁用交换操作，以避免因频繁的磁盘 I/O 导致性能下降；只有当系统检测到空闲内存低于某一预设阈值时，才会启动交换机制，将部分进程换出到磁盘上的交换空间以释放内存；而一旦空闲内存回升到安全水平以上，系统便会停止换出操作，必要时还将已换出的进程重新调入内存

“能不换就不换，内存紧张时才换，内存缓解后就停”。

7.3 Contiguous Allocation¶

连续分配（Contiguous Allocation）是一种将主存划分为两个固定分区的内存管理方式：低地址区域用于存放常驻操作系统（Resident Operating System），通常包含中断向量表等关键系统代码；高地址区域则分配给用户进程使用。

为保护系统和用户进程的安全，系统使用

重定位寄存器实现内存隔离——基址寄存器（Base Register）保存当前进程在物理内存中的起始地址
限长寄存器（Limit Register）限制其逻辑地址范围，确保每个进程只能访问自己的合法地址空间，防止越界访问或破坏操作系统代码。
同时，内存管理单元（MMU）动态地将用户程序生成的逻辑地址转换为物理地址

从而支持多道程序的运行与内存保护。然而，该方案存在内存利用率低的问题，因为用户区往往有大量空闲空间无法被有效利用。

内存利用率低的主要原因在于内存被划分为固定或半固定的连续区域，且每个进程必须占用一块连续的内存空间，不可避免地产生内部碎片和外部碎片

内碎片和外碎片

内碎片（Internal Fragmentation）是指在单个进程的内存空间中，由于分配单位大于实际需求而造成的未使用内存，例如固定分区或分页系统中多余的空闲空间；外碎片（External Fragmentation）则是指系统中存在足够总量的空闲内存，但由于这些空闲块分散且不连续，无法满足一个需要连续内存的进程请求，从而导致可运行进程数量减少。

紧缩与拼接

为减少外部碎片化，可通过紧缩（compaction）或拼接（defragmentation）技术将内存中的进程重新排列，使所有空闲内存块合并成一个连续的大块，从而提高内存利用率并支持更大进程的加载。紧缩过程涉及大量数据移动，开销较大，因此属于昂贵的操作，通常只在必要时执行。

多分区分配（Multiple-partition allocation）是一种将主存划分为若干个连续区域（称为“分区”）的内存管理方式，每个分区只能存放一个进程。这种管理方式分为两种类型：

固定分区（Fixed Partitioning），即在系统初始化时将内存划分为大小固定的分区，每个分区可容纳一个特定大小的进程，存在内部碎片和利用率低的问题；
动态分区（Dynamic Partitions）或可变分区（Variable Partition），即根据进程大小动态划分内存，按需分配，减少了内部碎片，但可能产生外部碎片，且需要更复杂的内存管理机制来支持。

对于动态分区来说，按需分配，分配的方式可以有几种不同的方式

First-Fit: 选择第一个足够大的空闲块，查找速度快
Best-Fit: 选择能满足需求的最小空闲块，能产生最小的剩余碎片，提高存储利用率，但需遍历整个空闲链表（除非按大小排序）
Worst-Fit: 选择最大的空闲块，目的是保留较小的空闲块用于后续小请求，但会留下较大的剩余碎片，且同样需要搜索完整个列表。
Next-Fit: 类似首次适应，每次分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就把它划分后分配出去。

总体而言，首次适应和最佳适应在速度和存储利用率方面均优于最差适应，因此在实际系统中更常被采用。

Example

7.4 Paging¶

7.4.1 Basic Method¶

分页（Paging）是一种将进程的逻辑地址空间划分为固定大小的块（称为“页”，pages），并将物理内存划分为同样大小的块（称为“帧”或“页框”，frames）的内存管理机制。每个页可以被独立地映射到任意可用的物理帧中，因此进程的逻辑地址空间无需连续，物理内存也可非连续分配，只要系统有空闲帧即可。

这种机制打破了连续分配的限制，提高了内存利用率和灵活性。

当运行一个大小为 $n$ 页的程序时，系统需要找到 $n$ 个连续或不连续的空闲帧，并将程序的各页加载到这些帧中。为了实现逻辑地址到物理地址的映射，操作系统为每个进程建立一个页表（page table），该表记录了进程的每一页在主存中对应的物理帧号，从而实现地址转换。

尽管分页有效解决了外部碎片问题，但可能产生内部碎片：当进程的最后一页未完全填满一个帧时，剩余空间将被浪费。

在分页系统中，CPU生成的逻辑地址被划分为两部分：页号（page number, p） 和 页内偏移（page offset, d）。其中，页号作为索引用于访问页表，查找到对应页在物理内存中的起始地址（即帧号）；页内偏移则与该物理地址结合，形成最终的物理地址并发送给内存单元进行访问。

页表通常存储在主存中，由页表基址寄存器（PTBR，如x86架构中的cr3寄存器）指向其起始地址，页表长度寄存器（PRLR）则指示页表的大小。在每次访问数据或指令时，系统需进行两次内存访问：一次用于查页表获取物理帧号，另一次用于访问实际数据，这会降低性能。为解决这一问题，现代系统引入了快表（Translation Lookaside Buffer, TLB），即一种高速缓存硬件，也称为联想寄存器，用于缓存最近使用的页表项，从而避免频繁访问主存中的页表。

部分TLB条目还包含地址空间标识符（ASID），用于唯一标识进程，确保不同进程之间的地址空间隔离与保护（比如说进程A,B 都要映射某个虚拟地址，但是对应的物理地址的帧号并不一样，这时候需要这个 ASID 作为标识）

接下来我们讨论一下有效访问时间：假设快表（TLB）的访问时间为 $\varepsilon$ 个时钟周期，主存访问时间为 $t$ 个时钟周期，且快表命中率为 $\alpha$，即有 $\alpha$ 的概率在快表中找到所需的页表项。

当快表命中时，只需一次快表访问和一次主存访问（用于取数据），总时间为 $t + \varepsilon$；
当未命中时，需先访问主存中的页表（耗时 $t$），再访问数据（耗时 $t$），加上快表访问时间 $\varepsilon$，总时间为 $2t + \varepsilon$。

因此，有效访问时间（Effective Access Time, EAT）的计算公式为：

$$ \text{EAT} = (t + \varepsilon)\alpha + (2t + \varepsilon)(1 - \alpha) $$ 内存保护通过为每个物理帧关联保护位 valid bit 来实现，其中页表中的每一项都包含一个 valid-invalid位：当该位为“有效”时，表示对应的页属于进程的逻辑地址空间，是合法可访问的页面；当为“无效”时，则表示该页不在进程的逻辑地址空间内，访问将触发异常。

共享页机制允许多个进程共享相同的代码，以提高内存利用率和系统效率。

共享代码（Shared Code）是指一段只读的、可重入（reentrant）的代码。它们在所有进程中只需维护一份物理副本；为实现共享，这些代码必须在每个进程的逻辑地址空间中映射到相同的位置，以便正确访问。
私有代码和数据则由每个进程独立拥有，各自保留一份副本，其对应的页可以在逻辑地址空间中的任意位置分配。

7.4.2 Structure of the Page Table¶

接下来我们将讨论页表的不同类型，常见的有以下三种

Hierarchical Paging 分级页表
Hashed Page Tables 哈希页表
Inverted Page Tables 反向(反置)页表

Hierarchical Paging¶

x86 的逻辑地址空间有 $2^{32}$ Byte，如页面大小为4 KB（$2^{12}$ Byte），则页表项最多有1M（$2^{20}$）个，每个页表项占用 4 Byte，故每个进程的页表占用4 MB内存空间，还要求是连续的，显然这是不现实的。

在 Linux 中是四级页表，在 Windows 中是两级页表

以两级页表为例，在32位机器上，若页大小为 4 KB（即 $2^{12}$ 字节），则逻辑地址由 32 位组成，其中低 12 位为页内偏移（page offset），用于定位页内的具体位置；高 20 位为页号（page number），用于索引页表。由于页表本身可能很大，无法放入一个页框中，因此采用两级分页机制：将 20 位的页号进一步划分为两个 10 位的部分——$p_1$ 和 $p_2$。其中，$p_1$ 作为索引访问外层页表（outer page table），查得对应页框的基址；$p_2$ 则作为偏移量，用于在该页框中查找目标页的物理帧号。

Hashed Page Tables¶

哈希页表（Hashed Page Tables）常用于地址空间大于32位的系统中，以高效管理庞大的虚拟地址空间。在这种机制下，虚拟页号通过哈希函数映射到页表中的某个位置，而该位置可能对应一个链表，存储所有哈希到同一地址的页表项（即处理哈希冲突）。

当需要查找某个虚拟页号时，系统先计算其哈希值，定位到对应的链表，然后在链表中逐项比较虚拟页号以寻找匹配项；若找到匹配，则提取对应的物理帧号完成地址转换。

例如 SPARC Solaris 操作系统就采用了这种机制来支持大规模虚拟内存管理。

Inverted Page Table¶

反向页表（Inverted Page Table）是一种用于管理虚拟内存的页表结构，其核心思想是为物理内存中的每一个真实页帧（real page of memory）设置一个表项，而不是为每个虚拟页创建一个条目。每个表项包含该物理帧中存储的虚拟页地址以及所属进程的相关信息（如进程ID和ASID），从而实现从物理页到虚拟页的映射。这种设计显著减少了存储所有页表所需的内存空间，尤其适用于大地址空间系统（如64位架构），因为表的大小仅取决于物理内存的页数，而非虚拟地址空间的大小。

然而，由于查找时需要根据虚拟页号在表中搜索匹配项，会增加访问时间；为此，通常结合哈希表来加速查找过程，将搜索范围限制在少数几个表项内，提升效率。该机制被应用于 UltraSPARC 和 PowerPC 等 64 位体系结构中，以优化内存管理性能。

当CPU生成一个逻辑地址时，系统将其拆分为进程标识符（pid）、虚拟页号（p）和页内偏移（d）；随后，以（pid, p）作为关键字在反向页表中进行查找——通常借助哈希函数快速定位到可能的表项链表，并在其中逐项比对是否匹配；若找到对应项，则从中提取出该页所在的物理帧号（i），结合页内偏移（d）构成完整的物理地址并访问内存；若未找到，则说明该页当前不在物理内存中，触发缺页中断，由操作系统从外存调入后再更新反向页表。

Example

7.5 Segmentation¶

分段（Segmentation）是一种内存管理方案，旨在支持用户对内存的逻辑划分方式。在这种机制下，一个程序被划分为多个逻辑上独立的段（segment），每个段代表程序中的一个有意义的逻辑单元，例如主程序、过程、函数、方法、对象、局部变量、全局变量、公共块、栈、符号表或数组等，每个段具有独立的大小和访问权限。

在分段内存管理架构中，逻辑地址由一个二元组构成：<段号, 段内偏移>，其中段号标识程序中的某个逻辑段，段内偏移表示在该段内的具体位置。

系统通过段表（Segment Table） 实现逻辑地址到物理地址的映射，每个段表项包含两个关键字段：

base（基址），存储该段在物理内存中的起始地址；
limit（长度），规定该段的大小，用于内存保护。

段表的起始位置由段表基址寄存器（STBR） 指向，而段表长度寄存器（STLR） 则记录当前进程使用的段数，用于验证段号合法性——只有当段号 s<STLR 时，该段才被视为合法，从而防止越界访问。

整个过程如下描述：CPU生成的逻辑地址由段号（s）和段内偏移（d）组成，例如 <s=3, d=200> 表示访问第3号段中的第200字节。系统首先通过段表基址寄存器（STBR）定位段表起始地址，并以段号 s 为索引查找对应的段表项，从中获取该段的基址（base）和长度限制（limit）。随后进行合法性检查：若偏移量 d 小于 limit，则视为合法访问；否则触发“地址错误”异常，防止越界访问。若检查通过，物理地址即为 base + d，该地址被发送至主存控制器，完成实际的数据读取或写入操作。

Example

我们发现这里采用的是寻址方式和之前 contiguous allocation 的方式很像，是否可以结合分页的想法呢？进而提出段页式系统

评论区

对你有帮助的话请给我个赞和 star =>

欢迎跟我探讨！！！