《现代操作系统》第三章——内存管理（读后笔记）_外存读入页表项后还得重新找吗-CSDN博客

本文链接：https://blog.csdn.net/j2_o2/article/details/106579723

本文深入探讨了虚拟内存系统的原理，包括分层存储体系、地址空间抽象、虚拟内存的实现机制，以及页面置换算法等核心概念。介绍了分页、分段技术，以及内存分配策略，旨在理解现代操作系统如何高效管理内存资源。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

分层存储器体系：高速缓存、内存、硬盘

存储管理器：管理分层存储器体系

最底层高速缓存管理由硬件完成，本章讲解对内存管理

对磁盘抽象和管理，文件系统部分在讲。

3.1 无存储器抽象

存储器模型就是物理内存。

无法同时运行两个程序

在不使用存储器抽象的情况下运行多个程序

将当前内存中所有内容保存到磁盘，将下个程序读入内存即可。

后面略过感觉上古机器不重要（希望憋打脸

3.2 一种存储器抽象：地址空间

直接使用物理地址缺点

操作系统容易被破坏
执行多个程序困难

3.2.1 地址空间

地址空间：进程可用于寻址内存的一套地址集合。每个进程有一个自己的地址空间，独立于其他进程（除非特殊情况）

重定位：把每个进程的地址空间映射到物理内存不同部分。

一个简单实现重定位方法，基址寄存器与界限寄存器

每个 CPU 配置两个特殊硬件寄存器

装载程序：装载到内存中连续的空闲位置且装载期间无需重定位。

当一个程序运行时，程序的起始物理地址装载到『基址寄存器』，程序的长度装载到『界限寄存器』

每次访问内存（取一条指令，读或写一个数据字）CPU硬件会把地址发送到内存总线前，自动把基址值加到进程发出的地址值，并检查地址值是否大于界限寄存器里的值。

使用 基址寄存器与界限寄存器 重定位缺点，每次访问需要加法和比较运算，加法运算没有特殊电路的情况会比较慢。

3.2.2 交换技术

内存常常不够用，内存超载两种通常处理方法：

交换技术：将进程存进磁盘
虚拟内存：该方法甚至能在程序只有一部分被调入内存的情况下运行。

下面先讨论交换技术

换入内存，会进行重定位

内存紧缩：交换内存会产生空闲区，通过将所有进程尽可能向下移动，将空闲区合并，会耗费大量CPU时间

有个问题，进程被创建或换入时应该分配多大内存？

一种方法，当换入或移动进程，为他分配一些额外的内存。进程交换到磁盘时，只交换实际使用的内存中的内容。

3.2.3 空闲内存管理

跟踪内存使用情况一般有两种方法：

位图
空闲区链表

使用位图的存储管理

内存被划分成若干分配单元，每个分配单元对应位图中一位，0 表示空闲，1 表示占用（或者相反）。

分配单元越小，位图越大。若进程大小不是分配单元整数倍，存在内存浪费。

位图缺点慢，如加载一个进程需要 k 位 0 串，无法快速搜索。

使用链表的存储管理

维护一个记录已分配内存段和空闲内存段的链表。其中链表一个节点或者包含一个进程，或者包含两个进程j间的一块空闲区。

每个结点包含：一个P（进程）/H（空闲区）的指示符，起始地址，长度，下一结点指针。

双向链表更合适，以便检查上个结点是否可以合并。

创建进程（或从磁盘换入进程）方法，假设知道为进程分配多少内存

首次适配法，找到第一个足够大的空闲区，快因为尽可能少搜索链表
下次适配法，和『首次适配法』比较接近，不同的是每次找到合适空闲区就记录当前位置，以便下次寻找，性能略低于首次适配法
最佳适配算法，搜索整个链表，找到最能容纳进程的最小空闲区域。比『首次适配法』慢，并且浪费内存更多（惊），因为产生大量无用小空闲区
最差适配算法，总是分配最大的可用空闲区，仿真程序表明该算法也不太行

进程和空闲区维护各自独立的链表，可以提高创建的效率，但降低内存释放的效率。

分离的保存空闲区的链表可用做个优化，利用空闲区存储节点信息

快速适配算法

为常用大小的空闲区，再维护一个链表。这样可以快速找到一个指定大小的空闲区，但内存释放费时。

3.3 虚拟内存

基本思想：每个程序拥有自己的地址空间，这个空间被分割成多个块，每一个块称作『一页』或『页面』，每一页有连续的地址范围，这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。

当程序引用到不在物理内存中的地址空间时，由操作系统将缺失的部分装入物理内存并重新执行失败命令。

虚拟内存适合多道程序设计系统，程序等待读入内存时，可以把 CPU 交给另一个进程使用。

3.3.1 分页

程序产生的地址称为『虚拟地址』。使用虚拟内存的情况，虚拟地址被送到内存管理单元（MMU），MMU将虚拟地址映射为物理内存地址。

页面：虚拟地址按照固定空间大小划分成的单元

页框：页面在物理内存中对应的单元

页面和页框大小通常一样。

RAM 和磁盘之间的交换以整个页面为单元进行。

操作系统支持对不同大小页面的混合使用匹配。

缺页中断（缺页错误）：访问页面没有被映射的虚拟地址

操作系统会找一个很少使用的页框且把他内容写入磁盘（如果它不在磁盘上），随后把所需要访问的页面读到刚才回收的页框中，修改映射关系，重新启动引起陷阱的指令。

3.3.2 页表

虚拟地址被分成『虚拟页号』（高位部分）和『偏移量』（低位部分）

虚拟页号作为『页表』的索引

例如对于 16 位地址和 4KB 的页面大小，高四位可以指定 16 个虚拟页面，低 12 位确定所选页面字节偏移量 $2^{12} = 4096 = 4KB$

虚拟页号可用作页表的索引，以找到该虚拟页面对应的页表项。由页表项找到页框号（如果有），再用页框号拼接到偏移量高位替代虚拟页号，形成送往内存的物理地址。

从数学角度说，页表是一个函数，通过这个函数可以把虚拟地址页面域替换成页框域，形成物理地址。

PS：我的感受

a 虚拟地址
b[] 页表
例如前四位是虚拟页号
c = ((1<<12)-1) = 0000 1111 1111 1111
d = ~c = 1111 0000 0000 0000)
物理地址 = (b[(a&d)>>12]<<12) | (a&c)

页表项结构

页框号

『在/不在』位

保护位（如三位，读、写、执行）

修改位：写入一页时硬件自动设置修改位，可以用来判断页面是否被修改过，没有可以直接丢弃，因为磁盘上副本仍在

访问位：读和写都会设置访问位。被用来帮助操作系统发生缺页中断时选择淘汰页面。

高速缓存禁止位：禁止该页面被告诉缓存，比如内存映射的 I/O 机器需要这一位（这位没搞懂）

需要注意

某个页面不在内存中，保存该页面磁盘地址由操作系统内部的软件表格记录，而不是页表。

3.3.3 加速分页过程

分页系统需要主要考虑的两个问题

虚拟地址到物理地址的映射速度
虚拟地址空间太大，页表也会很大

最简单的设计是使用由『快速硬件寄存器』阵列组成的单一页表，每一个表项对应一个虚拟页面，虚拟页号作为索引。启动一个进程，操作系统把保存在内存中的进程页表副本载入到寄存器，不必再为页表访问内存。

优点：简单、映射快

缺点：页表很大时，代价高，每次上下文切换都必须装载页表（每次切换进程都要载入）

另个极端方法

将整个页表存在内存中，这样只需要一个指向页表起始页的寄存器。

缺点：上下文切换快，但平时其他操作慢了，需要多次读取内存。

1. 轮换检查缓冲区

一种现象：大多数程序总是对很少量的页面进行多次访问。因此只有很少的页表项会被反复读取，大多数页表项很少被访问。

可以考虑，为计算机设置一个小型的硬件设备『转换检测缓冲区（TLB）』又称『相联存储器』、『快表』，将虚拟地址直接映射到物理地址，而不必再访问页表。

该设备存储少量的表项

大致流程：MMU 优先从 TLB 中搜索，无法找到再从页表中搜索。

2. 软件TLB管理

目前为止，假设一台具有虚拟内存的机器，都由硬件识别页表，以及一个 TLB。MMU 硬件管理 TLB。只有内存中没找到某页面才会陷入操作系统中。

现在许多现代机器，几乎所有的页面管理都是在软件中实现。TLB 表项被操作系统显示装载，当发生 TLB 访问失效，由操作系统解决。

TLB 失效比缺页中断发生得更频繁

TLB 变大可以减少失效率，TLB 软件管理变得足够有效

使用软件管理的好处，MMU 会变得非常简单，为高速缓存及其他性能改善腾出空间

两种 TLB 失效

软失效：页面访问在内存中而不在 TLB 中，更新一下 TLB 即可，不产生磁盘I/O，快。

硬失效：页面访问在磁盘中，需要从磁盘存取以装入该页面，慢。

页表遍历：页表结构中查找相应的映射

程序访问非法地址，不需要向 TLB 中新增映射，此时，操作系统会报告『段错误』终止进程，属于程序错误。

3.3.4 针对大内存的页表

1. 多级页表

多级页表避免全部页表一直保存在内存中。

例子

32 位虚拟地址分为 10 位 PT1 域、10 位 PT2 域、 12 位 Offset（偏移量）域。

用 PT1 在顶级页表中找到二级页表地址，用 PT2 在二级页表中找到页框号

另种寻址实现形式：页目录指针表，扩展页表项位，处理更大的地址空间。

2. 倒排页表

书没怎么看懂，看了眼网图，大概是用 hashmap 将虚拟页号存储，多记录一个进程 ID，查找时只需要在 hashmap 以进程 ID 为区分找到某一哈希值下的某一进程即可。

这样可能会很慢，哈希的时候值都一样就成链了

倒排页表在 64 位机器中比较常见

3.4 页面置换算法

发生缺页中断，操作系统从内存中选择一个页面将其换出内存，为调入内存腾空间。

如果换出页面在内存驻留期间被修改过，必须写回磁盘以更新磁盘的副本。

如果没被修改过，不需要写回。

页面置换算法解决该淘汰哪个页面。

3.4.1 最优页面置换算法

知道每个页面将在多久以后使用，所以不可能实现。然后根据时间长短替换（越长越优先被置换）。

该算法虽然不能实现，但是可以用来当其他算法上限，使得其他算法之间比较有个量化指标。

3.4.2 最近未使用页面置换算法『NUR』

R = 0，M = 0
R = 0，M = 1
R = 1，M = 0
R = 1，M = 1

从编号小的类中随机选一个置换。（看到总结才看到这条信息）

隐藏意思：淘汰一个没有被访问已修改页面优于被频繁读取无修改的页面

优点：易于理解和能够有效实现

性能不行

3.4.3 先进先出页面置换算法『FIFO』

实现一个链表，最新进入放链尾，从链表头开始淘汰。

发生页面中断时淘汰最早的页面

3.4.4 第二次机会页面置换算法

先进先出算法的改进。

如果最早页面的 R 位是 1，将 R 位清 0 重新放入链表尾部。如果最早页面 R 位是 0 直接置换。

3.4.5 时钟页面置换算法

环形链表实现的『第二次机会页面置换算法』，表针指向当前检查页面

置换直接把新页面替换，再指针向前移动一位。

R位是 1 ，就清楚 R 位，在指针向前移动一位

3.4.6 最近最少使用页面置换算法『LRU』

在缺页中断发生时，置换未使用时间最长的页面。

硬件要求高，需要知道各个页面各有多久时间未被进程访问，以及快速找到最近最久未使用的页面

3.4.7 用软件模拟 LRU『NFU』

前面一种硬件实现，支持的计算机比较少。所以这里提供一个软件实现的解决方案『NFU』算法。

为每个页面与一个软件计数器关联，计数器初值为 0，每次时钟中断扫描内存中所有页面的 R 位加到计算器上，发生缺页中断，置换计数器值最小页面。

NFU 不会忘记，可能之前常常出现后面不会出现，所以提供老化算法。每次修改，计数器先右移一位再将R值加入左端位。

NFU 算法与 LRU 区别

每次修改，不是及时的，期间会有多个页面已经被访问。

老化算法计数器位有限

3.4.8 工作集页面置换算法

颠簸：每执行几条指令程序就发生一次缺页中断。

工作集模型：为了降低中断率，不少分页系统都会设法跟踪进程的工作集，以确保在让进程运行以前，工作集已在内存中了。

预先调页：在程序运行前预先装入其工作集页面

发生缺页中断时，淘汰一个不在工作集中的页面。

工作集确定：最近 k 次访问所使用过的页面的集合

设想 k 位寄存器类似先进先出的页面置换算法维护页号。

不好维护没实现过，存在近似方法。

另种工作集确定：过去一段时间内内存访问所用到的页面集合。

容易实现，每个进程计算自己执行时间

表项至少包含：上次使用该页面近似时间、访问位『R』

找到 R 是 0 的表示当前时钟滴答中该页面没有被访问，可以作为候选者。然后计算多久没被使用，用一个值比较，大了就置换它。

全都找了找不到从候选者里找，候选者空的随机删除（最好是干净页面）

3.4.9 工作集时钟页面置换算法『WSClock』

性能好、实现简单、实际工作中广泛应用

数据结构是循环表，记录：上次使用时间、R 位，M位

与时钟算法类似，缺页中断，先检查指针指向页面（扫描中记录干净页面位置）。

R 位是 1，将 R 位值 0 不淘汰，指向下个指针重复该步骤。
R 位是 0，如果生存时间大于阈值且页面干净，它就不在工作集。
- 如果页面不干净（修改过），指针继续向前走。
走了一圈
- 至少调度一次写操作，置换第一个遇到的干净页面，因为最终会有某个写操作完成。
- 没有调度写操作，随便置换一个干净页面，没有干净页面置换当前页面。

没搞懂写操作位怎么清 0 的？不应该是置换后才能清 0 吗？以后再看书再说，没时间了。

3.4.10 小结

3.5 分页系统中的设计问题

页面置换算法一直没有考虑，相互竞争的程序之间如何分配内存。

全局的页面置换算法通常情况下比局部页面置换算法好。

全局算法时，系统不停确定每个进程应该分配多少页框。

PFF 算法 ：管理内存动态分配，指出何时增加或减少分配给一个进程的页面，没有说明缺页中断应该替换哪个。

PFF 假定：缺页中断率随着分配的页面增加而降低。

PFF尽可能让每个进程缺页中断率控制在可接受范围内。

3.5.2 负载控制

将一部分进程交换到磁盘以减少竞争内存数。

决定交换出哪个进程需要考虑：

进程大小
分页率（啥叫分页率）
特性（CPU 密集型、I/O 密集型）
以及其他进程的特性

3.5.3 页面大小

确定页面大小的矛盾有如下

小页面的优：

进程的内部碎片（进程的内存空间未被利用部分）少，大尺寸页面比小尺寸页面浪费了更多内存。

小页面更能充分利用TLB空间

小页面的劣：

更大的页表

磁盘和内存交换大部分时间花在寻道和旋转延迟上，所以传输页面的大小影响不大，数量影响更大

切换进程时硬件寄存器装入页表花费时间长

操作系统有时会为系统中不同部分使用不同页面的大小，如内核大页面，用户空间小页面

3.5.4 分离的指令空间和数据空间

指令（程序正文）：I 空间

数据：D 空间

链接器必须知道如何使用分离的空间

3.5.5 共享页面

如多个用户执行同一个程序，共享页面效率更高，不是所有页面都适合共享。

只读页面（诸如程序文本）可以共享，数据页面不能共享。

如果系统支持分离指令空间和数据空间，多个进程共享程序将变得简单。每个进程的进程表有两个指针一个指向 I 空间页表，一个指向 D 空间页表。

即使没用支持分离空间，进程也可以共享程序（有时为库），但机制复杂。

在两个进程 A、B 同时运行一个编辑器并共享页面，如果调度程序决定从内存移走 A，撤销其页面填充其他程序，那 B 会引起大量缺页中断。需要专门的数据结构记录共享页面。

如果共享单元是单个页面而不是整个页表，更加复杂，但不是不可能。如 UNIX 系统中，fork 系统调用后，父进程和子进程共享程序文本和数据。分页系统通常让这些进程分别拥有他们自己的页表，但是指向同一个页面集合。当然页面都是只读的。

写时复制：当一个进程更新了一点数据，触发只读保护，生成该页副本，每个进程都有自己的专用副本。两个复制都是可读写的。对副本修改不会触发陷阱。

3.5.6 共享库

现代操作系统，许多大型库被众多进程使用。所以需要『共享库』（DDL 或动态链接库）

未定义外部函数：任何在目标文件中被调用但没用被定义的函数（如 printf），未定义外部函数调用但不存在的函数也是未定义外部函数（printf 调用 write）

传统的链接，链接一个程序时，链接器的命令中指定一个或多个目标文件，可能包括库文件。链接器会在库中寻找未定义外部函数。如果找到，则将它们加载到可执行二进制文件中。当链接器完成任务，一个可执行二进制文件被写入磁盘，其中包含了所需全部函数，库中定义但是没被调用的函数不会被加载进去。当程序被装入内存执行时，所需所有函数都已经准备就绪。

有些库被众多程序使用照常内存浪费，所以引入共享库。

当一个程序和共享库链接时，链接器没有加载被调用的函数，而是加载一小段能够在运行时被调用函数绑定的『存根例程』

依赖与系统和配置信息，共享库或者和程序一起被装载，或者在其所包含函数第一次被调用时装载。整个库根据需要以页面为单位装载。

共享库优点