3.1内存管理概念

3.1.1_1内存的基础知识

内存可以存放数据。程序执行前需要先放到内存中才能被 $CPU$ 处理，起到缓存 $CPU$ 与硬盘之间速度差异的作用。

一、什么是内存，有何作用

1. 存储单元、内存地址的概念和联系
2. 按字节编址 $vs$ 按字编址

二、进程运行的基本原理

1. 指令的工作原理

指令由操作码 + 若干参数（可能包含地址参数）构成。

2. 逻辑地址（相对地址） $vs$ 物理地址（绝对地址）

• 逻辑地址：相对于模块起始位置的地址，从 $0$ 开始编号，也叫相对地址。
• 物理地址：内存中真实的绝对地址。

3. 从写程序到程序运行

1. 编辑：程序员编写源代码文件 $*.c$。
2. 编译：编译程序将源代码编译为若干目标模块，将高级语言翻译为机器语言，生成 $*.o$。
3. 链接：链接程序将一组目标模块、所需库函数链接在一起，生成完整装入模块，形成完整的逻辑地址，生成 $*.exe$。
4. 装入（装载）：装入程序将装入模块放入内存运行，完成逻辑地址到物理地址的映射。

4. 三种链接方式

1. 静态链接
   程序运行之前，把各目标模块与所需库函数链接成一个完整可执行装入模块，程序运行后不可拆分。

2. 装入时动态链接
   将目标模块装入内存时，边装入边完成链接。

3. 运行时动态链接
   程序执行过程中，需要用到目标模块时才进行链接。
   优点：便于修改更新，支持目标模块共享。

5. 三种装入方式

1. 绝对装入
   编译阶段就确定程序在内存中的存放位置，编译直接生成绝对地址的目标代码。

   仅适用于单道程序环境。

2. 可重定位装入（静态重定位）
   装入模块内地址从 $0$ 开始，全部是逻辑地址。装入内存时一次性完成地址重定位，把逻辑地址转换为物理地址。
   特点：

• 作业装入时必须一次性分配全部所需内存空间。
• 一旦装入内存，运行期间不能移动，也不能再申请内存。

3. 动态运行时装入（动态重定位）
   装入内存时不做地址转换，地址映射推迟到指令真正执行的时候。
   需要重定位寄存器支持，寄存器存放装入模块在内存的起始物理地址。
   特点：

• 程序可以分配到不连续的内存区域。
• 运行前只需要装入部分代码即可运行。
• 运行期间可以动态申请内存。
• 支持程序段共享，可向用户提供更大的地址空间。
• 允许程序在内存中移动。

3.1.1_2内存管理的概念

操作系统对内存的管理主要包含四大功能：

1. 内存空间的分配与回收
2. 内存空间的扩充（实现虚拟性）
3. 地址转换
4. 存储保护

地址转换

操作系统负责实现逻辑地址到物理地址的转换，该过程也称为地址重定位。 为了使编程更方便，程序员写程序时只需要关注指令、数据的逻辑地址，逻辑地址到物理地址的转换由操作系统完成，程序员不需要关注物理内存的实际情况。

地址转换共有三种装入方式：

• 绝对装入：编译器负责地址转换（单道程序阶段，无操作系统）
• 可重定位装入：装入程序负责地址转换（早期多道批处理阶段）
• 动态运行时装入：运行时才进行地址转换（现代操作系统）

存储保护

目标：保证各进程在自己的内存空间内运行，不会越界访问，进程之间互不干扰。

内存保护有两种实现方式：

1. 设置上下限寄存器 在 $CPU$ 中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，$CPU$ 检查是否越界。
2. 利用重定位寄存器、界地址寄存器进行判断 采用**重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）**进行越界检查。 重定位寄存器中存放的是进程的起始物理地址。 界地址寄存器中存放的是进程的最大逻辑地址。

3.1.1_3进程的内存映象

3.1.1_4覆盖与交换

覆盖技术

背景：早期计算机内存容量小，用于解决程序大小超过物理内存总和的问题。
覆盖技术思想：将程序拆分为多个段（模块），常用段常驻内存，不常用段在需要时调入内存。

内存分为两部分：

1. 一个固定区
   存放最活跃的程序段。
   固定区中的程序段在运行过程中不会调入调出。
2. 若干覆盖区
   不可能同时被访问的程序段可共享一个覆盖区。
   覆盖区中的程序段在运行过程中会根据需要调入调出。

要点：

• 必须由程序员声明覆盖结构，操作系统完成自动覆盖。
• 缺点：对用户不透明，增加了用户编程负担。
• 覆盖技术仅用于早期操作系统，现已淘汰。

交换技术（对换技术）

设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存，实现进程在内存与磁盘间动态调度。

三个核心问题：

1. 外存存放位置
   具有对换功能的操作系统，磁盘分为文件区和对换区。

• 文件区：存放文件，追求存储空间利用率，采用离散分配。
• 对换区：存放被换出的进程数据，追求换入换出速度，采用连续分配；对换区的 $I/O$ 速度比文件区更快。

2. 交换时机
   多个进程运行、内存吃紧时触发交换；系统负荷降低后停止交换。
   例：大量进程频繁缺页，代表内存紧张，可换出进程；缺页率明显下降，则停止换出。
3. 换出进程选择
   优先换出阻塞进程；可换出优先级低的进程；部分系统会考虑进程在内存的驻留时间，避免进程刚换入内存就被换出。

注意：$PCB$ 会常驻内存，不会被换出外存。

覆盖与交换的区别

• 覆盖：在同一个程序/进程内部进行段的调入调出。
• 交换：在**不同进程（或作业）**之间进行整体换入换出。

3.1.2_1连续分配方式管理

核心前提：为用户进程分配的必须是一个连续的内存空间

1. 单一连续分配

• 内存划分为系统区、用户区；只支持单道程序，用户程序放在用户区，内存中只能有一道用户程序，用户程序独占整个用户区空间。
• 碎片特点：无外部碎片，有内部碎片
• 优点
  1. 实现简单
  2. 无外部碎片
  3. 可使用覆盖技术扩充内存
  4. 不一定需要内存保护（例：早期 $PC$ 操作系统 $MS-DOS$）
• 缺点
  1. 仅适用于单用户、单任务操作系统
  2. 存在内部碎片
  3. 存储器利用率极低

2. 固定分区分配

• 支持多道程序；内存用户空间预先划分为若干固定大小的分区，每个分区只能装入一道作业。
• 分区的两种划分方式
  • 分区大小相等：缺乏灵活性；适合一台计算机控制多个相同对象的场景。
  • 分区大小不等：灵活性更高，可满足不同大小进程需求，按作业常见大小划分（多个小分区、适量中等分区、少量大分区）。
• 管理数据结构：分区说明表，每个表项包含分区大小、起始地址、分配状态。
• 碎片特点：无外部碎片，有内部碎片
• 优点：实现简单，无外部碎片
• 缺点
  1. 若用户程序过大，现有分区均无法满足，需要覆盖技术，降低性能
  2. 产生内部碎片，内存利用率低

3. 动态分区分配（可变分区分配）

• 不会预先划分内存分区；进程装入内存时，根据进程大小动态建立分区，分区大小刚好适配进程，分区数量与大小可变。

• 碎片特点：无内部碎片，有外部碎片

  • 内部碎片：分配给进程的内存区域中，未被使用的部分。
  • 外部碎片：内存中部分空闲分区过小，难以利用；空闲空间总和可以满足进程需求，但进程需要连续内存，碎片无法使用。
  • 外部碎片可使用**紧凑（拼接，$Compaction$）**技术解决。

• 内存分区回收的四种情况

  1. 回收区之后有相邻的空闲分区
  2. 回收区之前有相邻的空闲分区
  3. 回收区前、后都有相邻的空闲分区
  4. 回收区前、后都没有相邻的空闲分区

  原则：相邻的空闲分区要合并

• 管理空闲分区的数据结构

  1. 空闲分区表：每个空闲分区对应一个表项，记录分区号、分区大小、起始地址、状态。
  2. 空闲分区链：分区头部、尾部设置前向指针、后向指针；头部同时记录分区大小。

4. 覆盖与交换

覆盖技术

• 分为一个固定区 + 若干覆盖区
  • 固定区：存放最活跃程序段，固定区中的程序段在运行过程中不会调入调出。
  • 覆盖区：不可能同时访问的程序段可共享同一个覆盖区，覆盖区中的程序段在运行过程中会根据需要调入调出。
• 要求：必须由程序员声明覆盖结构，操作系统完成自动覆盖。
• 缺点：对用户不透明，增加用户编程负担。

交换技术

• 核心逻辑：内存紧张时，换出部分进程腾出内存空间，再换入其他进程。
• 磁盘划分为文件区和对换区，被换出的进程存放于对换区。

覆盖与交换的区别

• 覆盖：作用在同一个程序/进程内部。
• 交换：作用在不同进程（作业）之间。

补充概念总结

• 内部碎片：分配给进程的内存空间，进程用不完，剩余部分浪费。
• 外部碎片：内存存在空闲块，但块太小、不连续，无法分配给新进程。

3.1.2_2动态分区分配算法

动态分区分配属于连续内存分配方式，分配给进程的内存空间必须是连续的一整片区域。空闲分区一般用空闲分区表、空闲分区链两种数据结构管理。

首次适应算法

算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
实现方式：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

• 优点：综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序。
• 缺点：低地址区域会不断产生很多很小的空闲分区，后续每次分配查找时，都要经过这些小分区，增加查找开销。

最佳适应算法

算法思想：优先使用更小的分区，以保留更多大分区，保证大进程到来时有连续大片内存可用。
实现方式：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

• 优点：会有更多的大分区被保留下来，更能满足大进程需求。
• 缺点：会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序。

最坏适应算法（最大适应算法）

算法思想：优先使用更大的分区，以防止产生太小的不可用的碎片。
实现方式：空闲分区以容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

• 优点：可以减少难以利用的小碎片。
• 缺点：大分区容易被用完，不利于大进程；算法开销大。

邻近适应算法

算法思想：由首次适应演变而来，每次从上一次查找结束位置开始查找。

首次适应每次都从链头查找，会造成低地址堆积大量小空闲分区，检索开销大；邻近适应以此优化。
实现方式：空闲分区以地址递增次序排列，可排列成循环链表。每次分配内存时从上一次查找结束的位置开始检索空闲分区链，找到大小能满足要求的第一个空闲分区。

• 优点：不用每次都从低地址的小分区开始检索。算法开销小。
• 缺点：会使高地址的大分区也被用完。

四种算法对比汇总

总结：四种算法中，首次适应算法综合效果最好。

3.1.3_1基本分页管理概念

分页存储的基本思想

将内存空间划分为大小相等的分区，每个分区称为页框（页框 = 页帧 = 内存块 = 物理块 = 物理页），页框编号称为页框号，从 $0$ 开始。

将进程的逻辑地址空间划分为与页框大小相等的片段，每一片段称为页 / 页面，页面编号称为页号，从 $0$ 开始。

操作系统以页框为单位分配内存，进程的页面可以离散存放在不相邻的页框中，页面内部地址连续。

易混概念区分

• 页、页面（逻辑侧） $vs$ 页框、页帧、物理页（物理内存侧）
• 页号、页面号（逻辑） $vs$ 页框号、物理页号（物理）

页表

操作系统为每一个进程单独建立一张页表，一般存放在 $PCB$（进程控制块）中。

• 进程的每一个页面，对应一个页表项。
• 每个页表项记录页号与**内存块号（页框号）**的映射关系。
• 所有页表项长度相同，页号是隐含的，不需要显式存储。
  $$
  i\text{ 号页表项存放地址} = \text{页表始址} + i \times \text{页表项大小}
  $$

注意：页表中存放的是内存块号，不是内存块的起始地址。
$$
J\text{ 号内存块的起始地址}=J \times \text{内存块大小}
$$

例题：页表项字节计算

已知物理内存 $4\mathrm{GB}$，页面大小 $4\mathrm{KB}$
$$
\text{内存块大小}=4\mathrm{KB}=2^{12}\mathrm{B}
$$
$$
\text{内存块总数}=2^{32}/2^{12}=2^{20}
$$
内存块号范围 $0 \sim 2^{20}-1$，至少需要 $20\mathrm{bit}$ 存储块号，因此每个页表项至少占 $3\mathrm{B}$。

逻辑地址结构

逻辑地址拆分为两部分：页号 $P$，页内偏移量 $W$。

• 若有 $K$ 位表示页内偏移量，则页面大小为 $2^{K}$ 个内存单元。
• 若有 $M$ 位表示页号，则一个进程最多拥有 $2^{M}$ 个页面。

核心考点：页面大小 等价于 页内偏移量位数，决定逻辑地址划分。

通用计算公式（页面大小不一定是 $2$ 的整数次幂时适用）

$$
\text{页号} = \lfloor \text{逻辑地址} / \text{页面长度} \rfloor
$$
$$
\text{页内偏移量} = \text{逻辑地址} \bmod \text{页面长度}
$$

例题：页面大小 $50\mathrm{B}$，逻辑地址 $110$
$$
\text{页号}=110 / 50 = 2
$$
$$
\text{页内偏移量}=110 \bmod 50 = 10
$$

逻辑地址→物理地址转换步骤

1. 根据逻辑地址，拆分得到页号、页内偏移量。
2. 查询页表，找到该页号对应的内存块（页框）起始地址。
3. $$\textbf{物理地址} = \text{页面在内存中的起始地址} + \text{页内偏移量}$$

特点：进程页面离散存放，页面内部地址连续。

3.1.3_2基本地址变换机构

基本地址变换机构借助进程的页表，将逻辑地址转换为物理地址。
系统设置页表寄存器（$PTR$），存放页表在内存中的起始地址 $F$ 和页表长度 $M$。
进程未执行时，页表始址与页表长度存放在进程控制块（$PCB$）；进程被调度时，操作系统内核将这两个信息载入页表寄存器。

注意：页面大小是 $2$ 的整数幂。

设页面大小为 $L$，逻辑地址 $A$ 到物理地址 $E$ 的变换过程：

1. 计算页号 $P$、页内偏移量 $W$
   $$
   P = A / L,\quad W = A % L
   $$
   计算机硬件依靠固定的逻辑地址结构，可快速通过二进制拆分得到页号、页内偏移量。
2. 页号合法性检查：比较页号 $P$ 与页表长度 $M$，若 $P \ge M$，触发越界中断；否则继续执行。>

   页号从 $0$ 开始，$(P=M)$ 同样属于越界。

3. 查找页表项：
   $$
   \text{页表项地址} = F + P \times \text{页表项长度}
   $$
   取出页表项内容 $b$，即为内存块号。>

   区分概念：

   • 页表长度：页表内页表项总个数，即进程拥有页面总数
   • 页表项长度：单个页表项占用存储空间大小
   • 页面大小：一个页面占用存储空间大小

4. 计算物理地址：
   $$
   E = b \times L + W
   $$
   二进制下，直接拼接内存块号与页内偏移量，即可得到物理地址。
5. 访问物理内存对应的内存单元。

页表寄存器的作用

• 存放页表起始地址
• 存放页表长度

页表项相关探讨

每个页表项长度相同，页号是隐含的。
举例：系统物理内存大小为 $4\mathrm{GB}$，页面大小为 $4\mathrm{KB}$。
$$
2^{32}/2^{12}=2^{20}
$$
内存总共有 $2^{20}$ 个内存块，内存块号范围 $0 \sim 2^{20}-1$。
表示该范围至少需要 $20$ 位二进制，至少占用 $3$ 字节（$24$ 位）。

页表项按顺序连续存放在内存。若页表起始地址为 $X$，$M$ 号页对应的页表项地址：
$$
\text{地址}=X + 3 \times M
$$

• 页面 $4\mathrm{KB}$，页框可存放 $(4096/3=1365)$ 个页表项，剩余 $4096 % 3 = 1\mathrm{B}$，产生页内碎片。
• 若页表项占 $4$ 字节，一个页框刚好存放 $1024$ 个页表项，无碎片。

结论：理论上 $3\mathrm{B}$ 即可表示内存块号；工程上为方便查询，通常让一个页面恰好存放整数个页表项。

其他小细节

1. 页内偏移量位数与页面大小可以互相推导。
2. 页式管理中地址是一维的。确定页面大小，逻辑地址结构即确定。给出一个逻辑地址，系统自动算出页号、页内偏移量，无需显式告知页内偏移占多少位。
3. 实际应用中，通常使一个页框恰好能放入整数个页表项。
4. 为方便查找页表项，页表一般存放在连续的内存块中。

3.1.3_3有块表的地址变换机构

局部性原理

1. 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。
   产生原因：程序中存在大量的循环。
2. 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。
   产生原因：很多数据在内存中都是连续存放的。

基本地址变换机构每次访问逻辑地址，都需要查询内存中的页表。依托局部性原理，会连续多次查询同一个页表项，因此引入快表加速地址转换。

什么是快表（$TLB$）

快表，又称联想寄存器（$TLB$, $translation$ $lookaside$ $buffer$），是访问速度远快于内存的高速缓存，$TLB$ 不是内存。
作用：存放最近访问的页表项的副本，加速地址变换。
内存中存放的原始页表，称为慢表。

引入快表后的地址变换过程

1. $CPU$ 给出逻辑地址，硬件计算得到页号、页内偏移量，将页号与快表内所有页号进行比较。
2. 快表命中：找到匹配页号，直接取出内存块号，拼接内存块号与页内偏移量得到物理地址，访问内存单元。
   快表命中时，访问一个逻辑地址仅需要一次访存。
3. 快表未命中：访问内存中的慢表，查询页表项得到内存块号；拼接得到物理地址，访问内存单元；同时将本次页表项存入快表，若快表已满，则使用替换算法淘汰旧页表项。
   快表未命中时，访问一个逻辑地址需要两次访存。

依托局部性原理，快表命中率通常可达 $90%$ 以上。

平均访存时间计算示例

条件：访问快表耗时 $1\mathrm{\mu s}$，访问一次内存耗时 $100\mathrm{\mu s}$，快表命中率 $90%$。

• 串行查找（先查快表，不命中再查内存页表）
  $$
  (1+100) \times 0.9 + (1+100+100) \times 0.1 = 111 \ \mathrm{\mu s}
  $$
• 并行查找（快表与慢表同时查找）
  $$
  (1+100) \times 0.9 + (100+100) \times 0.1 = 110.9 \ \mathrm{\mu s}
  $$

对比基本地址变换机构

补充考点

$TLB$ 和普通 $Cache$ 的区别：$TLB$ 中只存放页表项的副本，普通 $Cache$ 可以存放各类数据的副本。

3.1.3_4两级页表

单级页表存在的问题

1. 所有页表项必须连续存放，页表过大时需要很大的连续内存空间
2. 在一段时间内并非所有页面都用得到，没必要让整个页表常驻内存

示例：某系统按字节寻址，支持 $32$ 位逻辑地址，页面大小为 $4KB$，页表项长度为 $4B$
$4KB=2^{12}B$，页内地址占 $12$ 位，剩余 $20$ 位表示页号。
进程最多存在 $2^{20}$ 页，对应页表最多包含 $2^{20}$ 个页表项，页表总大小 $2^{20} \times 4B=2^{22}B$，需要 $2^{10}$ 个连续页框存放页表。
页表项查找公式：$K$ 号页对应的页表项存放位置 = 页表始址 $+K \times 4$，该公式建立在页表项连续存放的基础上。

两级页表基本思想

将长长的页表再次分页，把原本连续的大页表拆分，离散存放在内存中；同时为拆分后的页表建立上层索引表。

• 术语：页目录表 / 外层页表 / 顶级页表
• 逻辑地址结构：$(\text{一级页号},\ \text{二级页号},\ \text{页内偏移量})$

两级页表地址变换步骤

1. 按照地址结构将逻辑地址拆分成三部分
2. 从 $PCB$ 中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查表，找到最终访问的内存块号
4. 结合页内偏移量得到物理地址

示例：逻辑地址 $(0000000000,0000000001,111111111111)$ 转换物理地址
查表得到内存块号为 $4$，页面大小 $4096$，块起始地址：$4 \times 4096=16384$，再拼接页内偏移得到物理地址。

重要细节

1. 多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以划分更多级。

   例题：某系统按字节编址，$40$ 位逻辑地址，页面大小 $4KB$，页表项大小 $4B$。
   页面大小 $4KB=2^{12}B$，页内偏移量 $12$ 位，页号共 $40-12=28$ 位。
   单个页面可存放页表项数量：$2^{12}/4=2^{10}$，每一级页号需要 $10$ 位。
   $28$ 位页号至少分为三级：一级页号 $8$ 位，二级页号 $10$ 位，三级页号 $10$ 位，页内偏移 $12$ 位。

2. 访存次数（无快表）

• 两级页表：第 $1$ 次访问页目录表，第 $2$ 次访问二级页表，第 $3$ 次访问目标内存单元，一共 $3$ 次访存。
• 通用结论：$N$ 级页表访问一个逻辑地址，需要 $(N+1)$ 次访存。

多级页表优缺点

• 优点：不需要给整个页表分配连续的内存；不需要把全部页表常驻内存，只有需要的页表页才调入内存，节省内存空间。
• 缺点：无快表时，访存次数增加，内存访问速度下降。

3.1.4基本分段存储管理方式

分段

1. 将地址空间按照程序自身的逻辑关系划分为若干个段，每段从 $0$ 开始编址。
2. 内存分配规则：以段为单位分配内存，每个段在内存中占据连续空间，但各段之间可以不相邻。
3. 逻辑地址结构：$(\text{段号},\ \text{段内地址})$
   • 段号的位数：决定每个进程最多可以划分的段数量。
   • 段内地址位数：决定单个段的最大长度。

     示例：段号占 $16$ 位，段内地址占 $16$ 位。
     最多段数：$2^{16}=64K$ 个段；单个段最大长度：$2^{16}=64KB$。

段表

1. 作用：记录逻辑段到实际物理存储地址的映射关系。为每一个进程建立一张段映射表。
2. 段表项：每个段对应一个段表项，各段表项长度相同，由段长、基址组成，段号是隐含的，不占用存储空间。

   示例：段表存放起始地址为 $M$，$K$ 号段对应的段表项地址：$M+K\times\text{段表项长度}$。

地址变换步骤

1. 由逻辑地址拆分得到段号、段内地址。
2. 段号与段表寄存器中的段表长度比较，检查段号是否越界，越界则触发中断。
3. 由段表始址、段号找到对应的段表项。
4. 根据段表记录的段长，检查段内地址是否越界，越界则触发中断。
5. 由段表中 $\text{基址}+\text{段内地址}$，计算得到物理地址。
6. 访问目标内存单元。

分段与分页对比

1. 页是信息的物理单位；分页目的是离散分配、提升内存利用率，分页是系统行为，对用户不可见。
   段是信息的逻辑单位；分段目的是满足用户编程需求，段包含一组逻辑模块信息，对用户可见。
2. 页的大小固定，由系统决定；段长度不固定，由用户编写的程序决定。
3. 分页地址空间是一维；分段地址空间是二维，标识地址需要段号+段内地址。
4. 分段更容易实现信息共享与保护。纯代码/可重入代码（不可修改）可以多进程共享，可修改代码不能共享。
   实现方法：多个进程段表项指向内存中同一个段。
5. 访存次数（无快表）
   • 单级分页：$2$ 次访存。
   • 分段存储：$2$ 次访存。
   • 分段系统同样可以引入快表，缓存段表项，减少访存次数，加速地址变换。

3.1.5段页式管理方式

分段+分页基本思想

将地址空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面。 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存。 逻辑地址结构：$(段号,\ 页号,\ 页内偏移量)$

段表、页表

• 每个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表存放地址组成。
• 每个页对应一个页表项。各页表项长度相同，由页号（隐含）、页面存放的内存块号组成。

逻辑地址结构

段页式管理的地址结构是二维的。

• 段号的位数决定了每个进程最多可以分几个段
• 页号位数决定了每个段最大有多少页
• 页内偏移量决定了页面大小、内存块大小是多少

“分段”对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。

示例：段号占 $16$ 位，页号占 $4$ 位，页内偏移量占 $12$ 位，按字节寻址。 $$ 2^{16}=64K \text{ 个段},\quad 2^{4}=16\text{ 页},\quad 2^{12}=4096=4KB $$

地址变换步骤

1. 由逻辑地址得到段号、页号、页内偏移量
2. 段号与段表寄存器中的段长度比较，检查是否越界
3. 由段表始址、段号找到对应段表项
4. 根据段表中记录的页表长度，检查页号是否越界
5. 由段表中的页表地址、页号得到查询页表，找到相应页表项
6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
7. 访问目标单元

访存次数

1. 无快表：第一次——查段表、第二次——查页表、第三次——访问目标单元，一共 $3$ 次访存。
2. 引入快表机构：以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需 $1$ 次访存。

3.2虚拟内存

3.2.1虚拟内存的基本概念

传统存储管理方式的特征、缺点

传统存储管理分为连续分配、非连续分配两类。

• 连续分配：单一连续分配、固定分区分配、动态分区分配
• 非连续分配：基本分页存储管理、基本分段存储管理、基本段页式存储管理

一次性：作业必须一次性全部装入内存后才能开始运行。

1. 作业很大时，不能全部装入内存，导致大作业无法运行
2. 大量作业请求运行时，内存无法容纳全部作业，多道程序并发度下降

驻留性：一旦作业被装入内存，就会一直驻留内存，直至作业运行结束。 在一段时间内，仅需要访问作业的一小部分数据即可正常运行，大量暂时不用的数据长期占用内存，内存利用率低。

局部性原理

虚拟内存的实现基础。

1. 时间局部性：现在访问的指令、数据在不久后很可能会被再次访问
2. 空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后会被访问
3. 高速缓存技术：使用频繁的数据放到更高速的存储器中

虚拟内存的定义和特征

基于局部性原理，程序装入内存时，仅将很快会用到的部分装入内存，暂时不用的部分留在外存，程序即可开始执行。 程序运行时，访问信息不在内存，则操作系统将所需信息从外存调入内存；内存不足时，操作系统将内存中暂时不用的数据换出到外存。在用户视角，内存容量远大于实际物理内存，这就是虚拟内存。

虚拟内存三大特征：

• 多次性：无需在作业运行时一次性全部装入内存，允许作业被分成多次调入内存。
• 对换性：无需在作业运行时一直常驻内存，允许作业在运行过程中换入、换出。
• 虚拟性：从逻辑上扩充内存的容量，用户可见的内存容量远大于实际物理容量。

如何实现虚拟内存技术

虚拟内存需要建立在离散分配的内存管理方式之上。 需要操作系统提供两项核心功能：

1. 请求调页功能：访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存。
2. 页面置换功能：内存空间不够时，将内存中暂时用不到的信息换出到外存。

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

1. 请求分页存储管理
2. 请求分段存储管理
3. 请求段页式存储管理

传统非连续分配（基本分页、基本分段、基本段页式）与虚拟内存的主要区别： 程序执行过程中，访问信息不在内存时，操作系统将信息从外存调入内存；内存不足时，操作系统将内存中暂时不用信息换出到外存。

3.2.2请求分页管理方式

页表机制

对比基本分页存储管理，请求分页的请求页表新增四个字段：

1. 状态位：标记页面是否已经调入内存。
2. 访问字段：记录页面最近被访问次数，或者上次访问时间，用于页面置换算法挑选待淘汰页面。
3. 修改位：标记页面调入内存后是否被修改；只有修改过的页面，置换时才需要写回外存。
4. 外存地址：记录页面在外存上存放的位置。

缺页中断机构

1. 缺页中断产生时机：访问目标页面不在内存时，触发缺页中断，属于内中断（内部异常），归类为故障（$fault$），故障类异常可以被修复。
2. 中断特点：一条指令执行期间，可以产生多次缺页中断。
3. 处理流程：
   • 发生缺页中断后，当前进程阻塞，进入阻塞队列；调页完成后唤醒进程，放回就绪队列。
   • 内存存在空闲块：分配空闲内存块，从外存调入目标页面，更新页表项。
   • 内存无空闲块：使用页面置换算法选择页面淘汰；若被淘汰页面的修改位为 $1$，需要写回外存；未修改则无需写回。

地址变换机构

请求分页与基本分页存储管理的核心区别：程序执行访问不在内存的页面时，操作系统完成请求调页；内存不足时执行页面置换。 新增步骤：

1. 请求调页：检索页表项，判断页面是否在内存，不在内存则触发缺页中断。
2. 页面置换：需要调入页面，但内存无空闲块时执行页面置换。
3. 更新页表：页面调入内存后，修改请求页表对应的表项。

快表关联规则：快表内的页面一定位于内存。页面被换出外存时，需要同步删除快表里对应的表项，防止访问错误页面。

补充细节

① 只有写指令才需要修改修改位。一般仅修改快表中的数据；只有删除快表项时，才需要写回内存中的慢表，以此减少访存次数。 ② 和普通中断处理一致，缺页中断处理过程需要保留 $CPU$ 现场。 ③ 需要使用页面置换算法，确定要换出的页面。 ④ 页面换入、换出都要启动慢速 $I/O$ 操作；页面交换过于频繁，会带来很大系统开销。 ⑤ 页面调入内存后，修改内存慢表，同时把表项复制到快表中。

3.2.4页面置换算法

当请求的页面不在内存，内存又无空闲块时，需要从内存中淘汰一页，这个选择页面的算法就是页面置换算法。

$OPT$ 最佳置换算法

算法规则：优先淘汰最长时间内不会被访问的页面。

• 原理：淘汰以后永不使用，或者最长时间不再访问的页面，可以保证最低缺页率。
• 局限性：进程执行前无法预知未来页面访问序列，无法实际实现，仅作为理论参考标准。
• 优缺点：缺页率最小，性能最好；但无法实现。

$FIFO$ 先进先出置换算法

算法规则：优先淘汰最先进入内存的页面。

• 实现：将调入内存的页面按调入先后排成队列，淘汰时直接选择队头页面。
• $Belady$ 异常：为进程分配的物理块数增大时，缺页次数不减反增的现象。只有 $FIFO$ 会产生 $Belady$ 异常。
• 优缺点：实现简单；但性能很差，可能出现 $Belady$ 异常。

$LRU$ 最近最久未使用置换算法

算法规则：优先淘汰最近最久没访问的页面。

• 实现：页表项设置访问字段，记录页面自上次访问后经历的时间 $t$，淘汰时选 $t$ 最大的页面。
• 做题技巧：淘汰页面时，逆向扫描访问序列，内存页面里最后出现的页号就是被淘汰页。
• 优缺点：性能很好，最接近 $OPT$；但需要硬件支持，算法开销大。

$CLOCK$（$NRU$）时钟置换算法

算法规则：循环扫描各页面。第一轮淘汰访问位=$0$ 的，并将扫描过的页面访问位改为 $1$。若第一轮没选中，则进行第二轮扫描。

• 实现：每个页面设置访问位，内存页面连成循环队列；页面被访问则访问位置 $1$。淘汰时检查访问位：为 $0$ 直接换出；为 $1$ 则置 $0$，继续扫描。
• 最多两轮扫描，一定能找到淘汰页面。
• 优缺点：实现简单，算法开销小；但未考虑页面是否被修改过。

改进型 $CLOCK$（改进型 $NRU$）

核心思想：除访问位，额外增加修改位。优先淘汰没有修改过的页面，避免不必要的 $I/O$ 写回外存操作。 用（访问位, 修改位）描述页面状态：

1. 第一轮：寻找 $((0,0))$，直接淘汰，不修改标志位

2. 第二轮：寻找 $((0,1))$，淘汰；本轮将扫描过页面访问位全部置 $0$

3. 第三轮：寻找 $((0,0))$，直接淘汰，不修改标志位

4. 第四轮：寻找 $((0,1))$，淘汰

   最多四轮扫描，一定能选出淘汰页面。

• 优缺点：算法开销较小，性能也不错。

算法对比汇总表

3.2.5页面分配策略

驻留集

驻留集：指请求分页存储管理中给进程分配的内存块的集合。

• 虚拟存储系统中，驻留集大小一般小于进程总大小。
• 驻留集太小：缺页频繁，大量时间用于缺页处理，进程推进效率低。
• 驻留集太大：多道程序并发度下降，资源利用率降低。
• 目标：选择合适的驻留集大小。

固定分配 $VS$ 可变分配：区别在于进程运行期间驻留集大小是否可变。 局部置换 $VS$ 全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出。

页面分配、置换策略

1. 固定分配局部置换 进程运行前就分配一定数量物理块，运行期间驻留集大小不变。缺页时，只能换出该进程自身的页面。 缺点：很难预先确定每个进程合适的物理块数量。 物理块数量确定依据：进程大小、优先级、程序员参数。
2. 可变分配全局置换 初始给每个进程分配若干物理块，系统维护空闲物理块队列。 只要缺页就分配新物理块：优先取空闲块；无空闲块时，可换出任意其他进程的页面。 被换页的进程物理块减少，缺页率会上升。
3. 可变分配局部置换 初始分配一定物理块。缺页时，仅能置换本进程内部页面。

• 频繁缺页的进程：多分配一些物理块。
• 缺页率很低的进程：回收部分物理块。 动态调整，直到缺页率维持在合适区间。

全局置换会改变其他进程物理块数量，因此不能搭配固定分配。

何时调入页面

1. 预调页策略 根据局部性原理，一次性调入若干相邻页面。 预测成功率约 $50%$，主要用于进程运行前（首次调入），由程序员指定预先调入的内容。 空间局部性：访问某内存单元后，后续大概率访问相邻内存单元。
2. 请求调页策略 进程运行时，发现缺页再调入页面。 调入页面一定会被访问；每次只调入一页，每次调页都触发磁盘 $I/O$，$I/O$ 开销较大。

从何处调页

外存分为对换区、文件区：

• 对换区：连续存储，读写速度更快。
• 文件区：离散存储，读写速度更慢。

1. 对换区足够大：进程运行前，把数据从文件区复制到对换区；后续页面调入调出都在内存 ↔ 对换区之间。
2. 对换区不足： 不会修改的数据，每次直接从文件区调入，换出时不用写回磁盘； 会修改的数据，换出写入对换区，需要时从对换区调入。
3. $UNIX$ 方式： 第一次使用页面从文件区调入；页面被换出时写回对换区；再次访问时从对换区调入。

抖动（颠簸）现象

定义：刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，也叫颠簸。 主要原因：分配给进程的物理块不够，进程频繁访问的页面数目高于可用物理块数。

• 物理块太少：引发抖动。
• 物理块太多：系统并发度下降，资源利用率降低。 $Denning$ 提出工作集概念，用来研究进程应当分配多少物理块。

工作集

工作集：在某段时间间隔里，进程实际访问页面的集合。 操作系统使用窗口尺寸统计工作集。

示例：窗口尺寸为 $4$ 页面访问序列：$24,\ 15,\ 18,\ 23,\ 24,\ 17,\ 18,\ 24,\ 18,\ 17,\ 17,\ 15$

• 前 $4$ 个访问页面：工作集 ${24,15,18,23}$
• 窗口滑动后：工作集 ${18,24,17}$

注意：

1. 工作集大小可以小于窗口尺寸。
2. 驻留集大小一般不能小于工作集大小，否则进程运行会频繁缺页。
3. 原理：局部性原理，进程近期访问页面和后续访问页面具有相关性。
4. 应用：页面置换算法，优先淘汰不在工作集中的页面。

3.2.7内存映射文件

传统文件访问方式

依赖系统调用完成文件读写：

1. $open$ 系统调用 —— 打开文件
2. $seek$ 系统调用 —— 将读写指针移动到指定位置
3. $read$ 系统调用 —— 从读写指针指向位置读取数据，从磁盘载入内存

进程需要主动调用系统调用完成磁盘与内存之间的数据传输。

内存映射文件（$Memory$-$Mapped$ $Files$）

内存映射文件是操作系统向上层程序员提供的系统调用功能。

访问流程

1. $open$ 系统调用 —— 打开文件
2. $mmap$ 系统调用 —— 将文件映射到进程的虚拟地址空间

核心特性

• 以访问内存的方式读写文件数据，直接操作虚拟地址即可
• 文件数据的读入、写出由操作系统自动完成
• 进程关闭文件时，操作系统自动将修改后的数据写回磁盘，同时解除内存映射
• 多个进程可以映射同一个文件，便于进程间共享数据

优点

• 编程简单：建立映射之后，只需要像访问普通内存一样读写文件内容
• 文件 $I/O$ 由操作系统自动管理，操作系统可以对 $I/O$ 效率做优化

核心作用

1. 简化程序员访问文件数据的操作
2. 方便多个进程共享同一个文件

对比总结

传统文件访问：需要手动调用 $seek$、$read$ 等系统调用，主动控制磁盘数据拷贝。 内存映射文件：文件映射到虚拟地址空间，缺页中断触发时操作系统自动完成磁盘和内存的数据交换。