操作系统-Part3——内存管理

[TOC]

内存管理

内存的基础知识

编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）
链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块
装入（装载）：由装入程序将装入模块装入内存运行

装入的三种方式

绝对装入：
- 编译后，在可执行文件中直接指出程序装入内存后的绝对地址。
- 由编译器完成，因为此时还未出现操作系统。
- 缺点：
  - 只适用于一台机器
  - 只适用于单道程序环境
- 程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。
静态重定位（可重定位装入）：
- 编译后，装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。
- 根据内存的情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）。
- 特点：
  - 在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。
  - 作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
动态重定位（动态运行时装入）：
- 编译后，装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。（同静态重定位）
- 装入程序把装入模块装入内存后，并不会把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正执行时进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持，用于存放装入模块的起始位置。
- 特点：
  - 可将程序分配到不连续的存储区中
  - 程序只需装入部分代码即可运行，并根据需要动态申请分配内存
  - 便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
  - 采用动态重定位时允许程序在内存中发生移动

链接的三种方式

静态链接：
- 在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。
装入时动态链接：
- 将各目标模块装入内存时，边装入边链接的链接方式。
运行时动态链接：
- 在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。
- 优点：灵活性更高，提高对内存的利用率

内存管理的概念

操作系统对内存管理需要实现的四个功能

操作系统需要负责内存空间的分配与回收
操作系统需要提供某种技术从逻辑上对内存空间进行扩充
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
- 即装入的三种方式：绝对装入、可重定位装入（静态重定位）、动态运行时装入（动态重定位）
操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰
- 方法一：在 CPU 中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU 检查是否越界。
- 方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。分别存放进程的起始物理地址和最大逻辑地址。

覆盖与交换

覆盖技术
- 思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。
- 内存中分为一个“固定区”和若干个“覆盖区”。
  - 需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）
  - 不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
    - 按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区，覆盖区大小以最大的程序段为准
    - 必须由程序员声明覆盖结构，操作系统完成自动覆盖。
- 缺点：对用户不透明，增加了编程负担。因此，只用于早期的操作系统中，现在已成为历史。
交换技术
- 思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
  - 中级调度（内存调度），决定将哪个处于挂起状态的进程重新调入内存。
  - 挂起队列中的 PCB 要负责记录挂起进程在磁盘中的位置。因此，PCB 会常驻内存，不会被换出外存
  - 暂时换出外存等待的进程状态为挂起状态（suspend），进一步细分为就绪挂起、阻塞挂起两种状态
- 交换的进程在外存中保存的位置
  - 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。
  - 文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式
  - 对换区空间只占磁盘空间的小部分，用于存放被换出的进程数据，主要追求换入换出速度以提升系统的整体速度，因此通常对换区采用连续分配方式。
  - 总之，对换区的 I/O 速度比文件区的更快。
- 交换的时机
  - 交换通常在许多进程运行且内存吃紧（经常发生缺页）时进行，而系统负荷降低（缺页率明显下降）就暂停。
- 交换的对象进程
  - 可优先换出阻塞进程
  - 可换出优先级低的进程
  - 为了防止优先级低的进程在频繁调入调出内存，有的系统还会考虑进程在内存的驻留时间

连续分配管理方式

连续分配：为用户进程分配的必须是一个连续的内存空间。
非连续分配：为用户进程分配的可以是一些分散的内存空间。

三种连续分配方式：

单一连续分配
- 在单一连续分配方式中，内存被分为系统区和用户区。
  - 系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。
  - 内存中只能有一道用户程序，用户程序独占整个用户区空间。
- 优点：
  - 实现简单
  - 无外部碎片
  - 可以采用覆盖技术扩充内存
  - 不一定需要采取内存保护（eg：早期的 PC 操作系统 MS-DOS）。
- 缺点：
  - 只能用于单用户、单任务的操作系统中
  - 有内部碎片（分配给某进程的内存区域中，没有使用的部分）
  - 存储器利用率极低。
固定分区分配
- 将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。是最早的、最简单的一种可运行多道程序、不会相互干扰的内存管理方式。
- 特点：
  - 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
    - 比如：钢铁厂有 n 个相同的炼钢炉，就可把内存分为 n 个大小相等的区域存放 n 个炼钢炉控制程序
  - 分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分
    - 比如：划分多个小分区、适量中等分区、少量大分区
- 分区说明表
  - 实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。
  - 优点：实现简单，无外部碎片。
  - 缺点：
    - 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能
    - 会产生内部碎片，内存利用率低。
动态分区分配
- 动态分区分配（可变分区分配），不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。
  - 因此系统分区的大小和数目是可变的。
- 记录内存使用情况的数据结构
  - 两种常用的数据结构：空闲分区表、空闲分区链
- 多个空闲分区的分配选择
  - 四种动态分区分配算法
- 分区的分配与回收
  - 回收内存分区时，相邻分区需要合并
    - 回收区的后面有一个相邻的空闲分区（修改分区大小和起始地址）
    - 回收区的前面有一个相邻的空闲分区（修改分区大小）
    - 回收区的前、后各有一个相邻的空闲分区（合并分区表项，修改分区大小）
    - 回收区的前、后都没有相邻的空闲分区（新建分区表项）
  - 注：各表项的顺序不一定按照地址递增顺序排列，需要依据动态分区分配算法来确定。
- 动态分区分配没有内部碎片，但是有外部碎片。
  - 内部碎片，内存中进程所属的分区中没有利用的部分
  - 外部碎片，内存中非进程所属分区中没有利用的部分
  - 可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。
    - 移动进程分区首地址以腾出连续空间
    - 适用于动态重定位
    - 紧凑之后需要修改 CPB 中的起始地址信息

动态分区分配算法

首次适应算法（First Fit）
- 算法思想：从低地址开始找到第一个适合的分区
- 分区排列顺序：空闲分区以地址递增次序排列
- 优点：
  - 综合看性能最好。算法开销小（回收分区后不需要对空闲分区队列重新排序）
  - 每次都需要检索低地址的小分区。有可能把高地址部分的大分区保留下来（最佳适应算法的优点）
最佳适应算法（Best Fit）
- 算法思想：优先使用更小的分区，以保留更多大分区
- 分区排列顺序：空闲分区以容量递增次序排列
- 优点：会有更多的大分区被保留下来，更能满足大进程需求
- 缺点：会产生越来越多太小的、难以利用的碎片；算法开销大（回收分区后可能需要对空闲分区队列重新排序）
最坏适用算法（Worst Fit）
- 算法思想：优先使用更大的分区，以防止产生太小的不可用的碎片
- 分区排列顺序：空闲分区以容量递减次序排列
- 优点：可以减少难以利用的小碎片
- 缺点：大分区容易被用完，不利于后续的大进程；算法开销大
临近适应算法（Next Fit）
- 算法思想：由首次适应演变而来，每次从上次查找结束位置开始查找
- 分区排列顺序：空闲分区以地址递增次序排列（可排列成循环链表）
- 优点：不用每次都从低地址的小分区开始检索。算法开销小
- 缺点：可能会使高地址的大分区也被用完

基本分页存储管理的基本概念（重点）

分页存储：
- 将内存空间分为一个个大小相等的分区，每个分区就是一个页框（页框=页帧=内存块=物理块=物理页面）。
  - 每个页框有一个页框号（页框号=页帧号=内存块号=物理块号=物理页号），页框号从 0 开始。
- 将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页（页=页面）。
  - 每个页面有一个“页号”，页号从 0 开始。
- 注意区别：页、页面 vs 页框、页帧、物理页
- 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。进程的页面与内存的页框有一一对应的关系。
  - 各个页面不必连续存放，可以放到不相邻的各个页框中。
- 注：进程的最后一个页面可能没有一个页框那么大。即，分页存储有可能产生内部碎片。因此页框不能太大，否则可能产生过大的内部碎片造成浪费
页表：
- 一个进程对应一张页表
- 进程的每个页面对应一个页表项
- 每个页表项由“页号”和“块号”组成
- 页表记录进程页面和实际存放的内存块之间的映射关系
- 每个页表项的长度是相同的
- 指向页表的指针存在于 PCB（进程控制块）中
每个页表项的长度计算
- Eg：假设某系统物理内存大小为 4GB，页面大小为 4KB，则每个页表项至少应该为多少字节？
- 内存块大小=页面大小=4KB= 2^12^B
  - 4GB 的内存总共会被分为 2^32^ / 2^12^ = 2^20^ 个内存块
  - 内存块号的范围应该是 0 ~ 2^20^-1
  - 内存块号至少要用 20bit 来表示
  - 至少要用 3B 来表示块号（3*8=24bit）
    - 重要考点：计算机中内存块的数量 -> 页表项中块号至少占多少字节
  - 页表中的页号是隐含的，即页号不占用存储空间
- 每个页表项占 3B，存储整个页表至少需要 (n+1)*3B
- 注意：页表记录的只是内存块号，而不是内存块的起始地址。*J 号内存块的起始地址 = J * 内存块大小*
实现地址的转换（重点）
- 逻辑地址A对应的物理地址 = P号页面在内存中的起始地址 + 页内偏移量W
  - 页号 = 逻辑地址 / 页面长度
  - 页内偏移量 = 逻辑地址 % 页面长度
  - *起始地址 = 页表[页号] * 内存块大小*
- 如果页面大小为 2^K^B，逻辑地址可以快速拆分为页号、页内偏移量
  - 在逻辑地址中，末尾 K 位为页内偏移量，其余前半部分为页号
  - 在物理地址中，末尾 K 位为页内偏移量，其余前半部分为页表[页号]
  - 即，对于页面大小为 2^K^B 的情况来说，直接将逻辑地址的页号部分替换成页框号
逻辑地址结构
- 地址长度为 32 位；其中 0~~11位为“页内偏移量”（页内地址）；12~~31 位为“页号”。
- 如果有 K 位表示“页内偏移量”，则说明该系统中一个页面的大小是 2^K^ 个内存单元
- 如果有 M 位表示“页号”，则说明在该系统中一个进程最多允许有 2^M^ 个页面

基本地址变换机构（重点）

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址：（重点）
- 进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中；当进程被调度时，操作系统内核会把它们放到页表寄存器中。
- 设页面大小为 L、起始地址 F、页表长度 M、逻辑地址 A 到物理地址 E 的变换过程：
  1. 计算页号 P 和页内偏移量 W
    - P=A/L，W=A%L
  2. 比较页号 P 和页表长度 M，若 P≥M，则产生越界中断
  3. 页表中页号 P 对应的*页表项地址 = 页表起始地址 F + 页号 P * 页表项长度*。取出该页表项内容 b，即为内存块号。
    - 注意：区分页表项长度、页表长度、页面大小。
    - 页表长度，指这个页表中总共有几个页表项，即总共有几个页
    - 页表项长度，指的是每个页表项占多大的存储空间
    - 页面大小，指的是一个页面占多大的存储空间
  4. 计算 E = b * L + W，用得到的物理地址 E 去访存。
    - 如果内存块号、页面偏移量是用二进制表示的，则直接把二者拼接即物理地址
- 在分页存储管理（页式管理）的系统中：
  - 页面的大小和逻辑地址结构是互相确定的：页面大小 L 为 1K 字节 == 某系统按字节寻址，逻辑地址结构中，页内偏移量占 10 位
  - 页式管理中地址是一维的（只需要一个参数）：只要给出一个逻辑地址，就可以直接求得页号、页内偏移量
对页表项大小的进一步探讨
- 一般不会考察，当问最小的页表长度时，按 3B 回答

具有快表的地址变换机构

快表，联想寄存器（TLB， translation lookaside buffer）
- TLB 不是内存，是 cache
- 用来存放最近访问的页表项的副本
- 与此对应，内存中的页表常称为慢表。
引入快表之后的地址变换过程
- CPU 给出逻辑地址，由硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
- 若命中，则直接从 TLB 取出目标的内存块号，与页内偏移量拼接形成物理地址，访问对应的内存单元。
  - 因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
- 若没有命中，则需要访问内存中的页表，通过页表始址和页号定位对应页表项，得到目标的内存块号，再将内存块号与页内偏移量拼接形成物理地址，访问该对应的内存单元。
  - 因此，若快表未命中，则访问某个逻辑地址需要两次访存
  - 在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。
  - 若快表已满，则必须按照一定的算法对旧的页表项进行替换
局部性原理
- 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。
  - 因为程序中存在大量的循环
- 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。
  - 因为很多数据在内存中都是连续存放的

总结

两级页表

针对问题：
- 单级页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框，与离散分配存储管理相悖。
- 没有必要让整个页表常驻内存，因为根据局部性原理，进程在一段时间内可能只需要访问某几个特定的页面。
改进方向：
- 把页表再分页并离散存储，建立一张页表记录页表各个部分的存放位置
- 该页表称为页目录表/外层页表/顶层页表
二级页表的结构
- 与单级页表的结构意义是相同的，前半部分来找到内存块号，后半部分为页内偏移量
- 页目录表的 item 记录二级页表在内存中的内存块号，二级页表的 item 记录数据在内存中的内存块号
- 页目录表、二级页表的每个页表项都增加一个标志位，用于表示该页面是否已经调入内存，否则产生缺页中断（内中断/异常）
注意：
- 若分为两级页表后，页表依然很长，则可以采用更多级页表，各级页表的大小不能超过一个页面
- 两级页表的访存次数分析（假设没有快表机构）
  - 第一次访存：访问内存中的页目录表
  - 第二次访存：访问内存中的二级页表
  - 第三次访存：访问目标内存单元

基本分段存储管理方式

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从 0 开始编址。
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
分段存储管理方式的优点：按逻辑功能模块划分，编程更方便，程序的可读性更高。
分段系统的逻辑地址结构：
- 段号的位数决定了每个进程最多可以分几个段
- 段内地址位数决定了每个段的最大长度是多少
段表
- 每个段对应一个段表项，其中记录了该段在内存中的基址和长度。
- 各个段表项的长度是相同的。因此，段号也是隐含的。
  - 例如：某系统按字节寻址，采用分段存储管理，逻辑地址结构为（段号 16 位, 段内地址 16 位），因此用 16 位即可表示最大段长。物理内存大小为4GB（可用 32 位表示整个物理内存地址空间）。因此，可以让每个段表项占 16+32 = 48位，即 6B。
地址变换过程
信息的共享和保护
- 不可修改的代码（纯代码/可重入代码）是可以共享的。可修改的代码是不能共享的。
  - 不可修改的代码不属于临界资源。
  - 可修改的代码（代码段）可能包含很多变量，各进程并发访问可能造成数据不一致
- 只需让各进程的段表项指向同一个段即可实现共享

分段、分页管理的对比

目的

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

长度

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

维度

分页的用户进程地址空间是一维的，只需给出一个记忆符即可表示一个地址。

分段的用户进程地址空间是二维的，在标识一个地址时，既要给出段名，也要给出段内地址。

共享与保护

分段比分页更容易实现信息的共享和保护。不可修改的代码（纯代码/可重入代码）是可以共享的。可修改的代码是不能共享的。

访存次数

分页（单级页表）：查内存中的页表（第一次访存）+ 访问目标内存单元（第二次访存）。总共两次访存

分段：查内存中的段表（第一次访存）+ 访问目标内存单元（第二次访存）。总共两次访存。

分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

段页式管理方式

针对问题：
- 分页管理
  - 优点：内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片
  - 缺点：不方便按照逻辑模块实现信息的共享和保护
- 分段管理
  - 优点：很方便按照逻辑模块实现信息的共享和保护
  - 缺点：1. 当段长过大时，分配很大的连续空间会很不方便。2. 会产生外部碎片（可以用“紧凑”来解决，只是需要付出较大的时间代价）
段页式管理的实现
- 理论：将进程按逻辑先按模块分段，再将各段分页
- 段页式系统的逻辑地址结构：
  - 由段号、页号、页内地址（页内偏移量）组成。
  - 段号的位数决定了每个进程最大段数
    - 段号占 16 位，每个进程最多有 2^16^=64K 个段
  - 页号位数决定了每个段最大页数
    - 页号占 4 位，每个段最多有 2^4^=16 页
  - 页内偏移量决定了页面/内存块大小
    - 页内偏移量占 12 位，每个页面\每个内存块大小为 2^12^=4096=4KB
- 分段对用户是可见的，编程时需要显式地给出段号、段内地址。而将各段分页对用户是不可见的，系统会根据段内地址自动划分页号和页内偏移量。
  - 段页式管理的地址结构是二维的。
- - 每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。每个段表项长度相等，段号是隐含的。
  - 每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。
- 地址转换过程
  - 得到段号、页号、页内偏移量
  - 检查段号越界
  - 根据段号找到段表项，取页表起始块号、长度
  - 检查页号越界
  - 根据页号找到页表项，取目标数据的内存块号
  - 访问目标内存单元

虚拟内存管理

虚拟内存的基本概念

传统存储管理方式的特征、缺点
- 一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：
  - 作业很大时，不能全部装入内存，导致大作业无法运行
  - 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
- 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。
  - 事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量暂时用不到的数据，浪费了宝贵的内存资源。
虚拟内存的定义：
- 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
- 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
  - 操作系统要提供请求调页（请求调段）功能
- 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
  - 操作系统要提供页面置换（段置换）的功能
- 在操作系统的管理下，在用户角度看虚拟内存比实际内存大得多
易混知识点：
- 虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的
- 虚拟内存的实际容量 = min（内存和外存容量之和，CPU寻址范围）
虚拟内存的三个主要特征：
- 多次性：无需将作业一次性全部装入内存，而是允许分多次调入内存。
- 对换性：在作业运行时无需一直常驻内存，而是允许将作业换入、换出。
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
实现虚拟内存技术：
- 传统的非连续分配存储管理：基本分页存储管理，基本分段存储管理，基本段页式存储管理
- 虚拟内存实现：请求分页存储管理，请求分段存储管理，请求段页式存储管理

请求分页管理方式

页表机制
缺页中断机构
- 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
- 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
- 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
- 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
- 缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断、故障（fault）
- 一条指令在执行期间，可能产生多次缺页中断。
地址变换机构
- 新增步骤
  - 请求调页（查到页表项时根据状态位判断）
  - 页面置换（需要调入页面，但没有空闲内存块时进行）
  - 需要修改请求页表中新增的表项
- - 查快表（未命中）—— 查慢表（发现未调入内存）—— 调页（调入的页面对应的表项会直接加入快表）—— 查快表（命中）—— 访问目标内存单元
- 注意
  - 快表中的页面一定是在内存中的。若某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面
  - 只有写指令才需要修改修改位。并且，一般只需修改快表中的数据，只有当将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
  - 和普通的中断处理一样，缺页中断处理依然需要保留 CPU 现场。
  - 换入/换出页面都需要启动慢速的 I/O 操作，如果换入/换出太频繁，会有很大的开销。
  - 页面调入内存后，需要同时修改慢表、快表。

页面置换算法

最佳置换算法（OPT，Optimal）：
- 每次选择淘汰的页面都是以后永不使用，或者在最长时间内不再被访问的页面。
- 最佳置换算法可以保证最低的缺页率，但实际上，操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
先进先出置换算法（FIFO）
- 每次选择淘汰的页面是最早进入内存的页面
- Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
  - 只有 FIFO 算法会产生 Belady 异常。
- FIFO 算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。
最近最久未使用置换算法（LRU）
- 每次淘汰的页面是最近最久未使用的页面
- 实现方法：
  - 赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间 t。
  - 当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面。
  - 虽然性能好，但是实现困难、开销大。
- 做题时，仅需逆向扫描过程中最后出现的页号，即要淘汰的页面。
时钟置换算法（CLOCK）
- 时钟置换算法（CLOCK 算法/最近未用算法（NRU，Not Recently Used）），是一种性能和开销较均衡的算法。
- 简单的 CLOCK 算法实现方法：
  - 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。
  - 算法规则：
    - 当某页被访问时，其访问位置为 1。
    - 当需要淘汰一个页面时，只需检查页的访问位：如果是 0，就选择该页换出；如果是 1，则将它置为 0，暂不换出
    - 若第一轮扫描中所有页面都是 1，则将这些页面的访问位依次置为 0 后，再进行第二轮扫描
  - 简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描
- 改进型的时钟置换算法：
  - 针对问题：只有被淘汰的页面被修改过时，才需要写回外存。
  - 改进方向：在其他条件都相同时，应优先淘汰没有修改过的页面，避免 I/O 操作。
  - 修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。用（访问位，修改位）的形式表示各页面状态。
  - 算法规则：
    - 第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
      - 第一优先级：最近没访问，且没修改的页面
    - 第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为 0
      - 第二优先级：最近没访问，但修改过的页面
    - 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
      - 第三优先级：最近访问过，但没修改的页面
    - 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。
      - 第四优先级：最近访问过，且修改过的页面
  - 改进型 CLOCK 置换算法选择一个淘汰页面最多会进行四轮扫描
- NRU 相比 LRU：
  - 记录谁最早被使用很难，那么换一种思路，把时间分成一个个周期，如果最近一个周期都没有被使用，那就干脆当做一直没有被使用。
  - 不一定要最早被使用的被淘汰，只要不是最近被使用的被淘汰就好了。

页面分配策略

驻留集：
- 指请求分页存储管理中给进程分配的物理块的集合。
- 在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
- 选择一个合适的驻留集大小
  - 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；
  - 若驻留集太大，会导致多道程序并发度下降，资源利用率降低。
页面分配：
- 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
- 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
- 局部置换：发生缺页时只能选进程自己的物理块进行置换。
- 全局置换：可以将内存中任意的物理块分配给缺页进程（包括操作系统保持的空闲物理块、争夺别的进程持有的物理块）
置换策略：
- 固定分配局部置换：
  - 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
  - 缺点：很难在最初为每个进程确定分配合理的物理块数量。（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）
- 可变分配全局置换：
  - 刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。
  - 特点：只要缺页就给分配新物理块。
  - 缺点：当空闲物理块用完时，系统可以选择任意一个进程中未锁定的页面调出，因此这个被选中的进程拥有的物理块减少，缺页率增加。
- 可变分配局部置换：
  - 刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
  - 特点：要根据发生缺页的频率来动态地增加或减少进程的物理块
何时调入页面
- 预调页策略：
  - 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有 50% 左右。
  - 故这种策略主要用于进程的首次调入（运行前调入），由程序员指出应该先调入哪些部分。
    - 主要指空间局部性，即：如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的
- 请求调页策略：
  - 进程在运行期间发现缺页时才将所缺页面调入内存（运行时调入）。
  - 由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘 I/O 操作，因此 I/O 开销较大。
从何处调入页
- 系统拥有足够的对换区空间：
  - 页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
- 系统缺少足够的对换区空间：
  - 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
- UNIX 方式：
  - 运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
抖动（颠簸）现象
- 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存。
  - 产生原因：进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
- 为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率
- 为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程“工作集”的概念
  - 驻留集：指请求分页存储管理中给进程分配的内存块的集合。
  - 工作集：指在某段时间间隔里，进程实际访问页面的集合。
  - 工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。
  - 一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
  - 拓展：可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法——选择一个不在工作集中的页面进行淘汰。