301 内存管理

内存管理概念

基本原理和要求

基本概念

• 内存管理：是操作系统对内存的划分和动态分配
• 目的：
  • 为了更好地支持多道程序并发执行
  • 方便用户
  • 提高内存利用率
• 功能：
  • 内存空间的分配与回收：由 OS 完成主存储器空间的分配与管理
  • 地址转换：存储管理将逻辑地址转换为物理地址
  • 内存空间的扩充：利用虚拟存储技术从逻辑上扩充内存
  • 内存共享：允许多个进程访问内存的同一部分
  • 存储保护：保证多道作业在各自的存储空间运行，互不干扰
• 分配方式：
  • 连续分配：
    • 单一连续分配 -⇒ 固定分区分配【单道发展到多道 OS】 -⇒ 动态分区分配【为了适应大小不同的程序】
  • 不连续分配：
    • 分页存储管理 -⇒ 分段存储管理 -⇒ 段页存储管理

程序的链接与装入

• 创建进程首先要将程序和数据装入内存，将用户源程序变为可在内存中执行的程序，需要的步骤如下：

1. 编译：由编译程序将用户源代码编译成若干目标模块
2. 链接：由链接程序将编译后形成的一组目标模块，以及它们所需的库函数链接在一起，形成一个完整的装入地址，有三种方式：
   • 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开
   • 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
   • 运行时动态链接：在程序执行中需要改目标模块时，才对它进行链接，优点时便于修改和更新，便于实现对目标模块的共享
3. 装入：由装入程序将装入模块装入内存运行，有三种方式：
   • 绝对装入：
     • 在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码装入程序按照装入模块中的地址，将程序和数据装入内存
     • 程序中的逻辑地址与实际内存地址完全相同
     • 只适用于单道程序环境
   • 可重定位装入【静态重定位】：
     • 编译、链接后的装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址
     • 装入时对地址进行“重定位”，将逻辑地址变换为物理地址【地址变换是在装入时一次完成的】
     • 装入时，必须给作业分配所要求的全部内存空间
   • 动态运行时装入【动态重定位】：
     • 编译、链接后的装入模块的地址都是从 0 开始的
     • 装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行
     • 因此装入内存后所有的地址依然是逻辑地址
     • 这种方式需要一个重定位寄存器的支持

逻辑地址与物理地址

• 逻辑地址【相对地址】：编译后，每个目标模块都从 0 号单元开始编址，这称为该目标模块的逻辑地址
• 逻辑地址空间【虚拟地址空间】：链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始的编址空间【32 位系统，范围 0 ~ $2^{32}-1$ 】
• 物理地址空间：内存中物理单元的集合，它是地址转换的最终地址
• 地址重定位：装入程序将可执行代码装入内存时，将逻辑地址转换成物理地址的过程
• 不同进程可以有相同的逻辑地址，这些逻辑地址映射到主存的不同位置
• 进程运行时，看到和使用的是逻辑地址

进程的内存映像

• 当一个进程调入内存运行时，就构成了进程的内存映像
• 组成要素：
  • 代码段：程序的二进制代码【代码段是只读的，可以被多个进程共享】
  • 数据段：程序运行时加工处理的对象，包括全局变量和静态变量
  • 进程控制块 PCB：存放在系统区，OS 通过 PCB 控制和管理进程
  • 堆：用来存放动态分配的变量【通过调用 malloc 函数动态地向高地址分配空间】
  • 栈：用来实现函数调用的【从用户空间的最大地址往低地址方向增长】

内存保护

• 目的：确保每个进程都有一个单独的内存空间
• 方法一：在 CPU 设置一对上、下限寄存器，存放用户进程在主存中的上限和下限地址，判断 CPU 访问的地址是否越界
• 方法二：采用重定位寄存器（也称基址寄存器）和界地址寄存器（也称限长寄存器）
  • 重定位寄存器存放进程的起始物理地址
  • 界地址寄存器存放进程的最大逻辑地址
  • 逻辑地址 + 重定位寄存器的值 = 实际物理地址

内存共享

• 只有只读区域的进程空间可以共享
• 可重入代码【也称纯代码】：允许多个进程同时访问但不允许被任何进程修改的代码，不属于临界资源
• 可重入程序通过减少交换数量来改善系统性能
• 实现方式：段的共享，内存映射文件，基于共享内存的进程通信

内存空间的分配管理方式

连续分配方式

• 定义：为一个用户程序分配一个连续的内存空间
• 特点：
  • 用户程序在主存中都是连续存放的
  • 存储密度大
• 外部碎片：内存中产生的小内存块，存在于所有分区的外部
• 内部碎片：分配给某进程的内存区域中，没有被用上的部分

单一连续分配

• 定义：内存被分为系统区与用户区
  • 系统区：仅供 OS 使用，通常在低地址部分
  • 用户区：内存中仅有一道用户程序
• 优点：
  • 简单、无外部碎片
  • 不需要进行内存保护
• 缺点：
  • 只能用于单用户、单任务的操作系统
  • 有内部碎片
  • 存储器的利用率极低

固定分区分配

• 定义：将用户内存空间大小划分若干固定大小的分区，每个分区只装入一道作业
• 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
• 分区大小不等：增加了灵活性，可以满足不同大小的进程需求，根据常在系统中运行的作业大小情况进行划分
• 为了方便分配与回收，建立一张分区使用表，每个表项对应一个分区，包括分区大小、起始地址及状态
• 优点：实现简单，无外部碎片
• 缺点：
  • 程序太大可能放不下任何一个分区
  • 程序太小也要占用一个完整分区，产生内部碎片
  • 不能实现多进程共享一个主存区，存储空间利用率低

动态分区分配

• 定义：进程在装入内存时，根据进程的实际需要，动态地为之分配内存，并使分区的大小正好适合进程的需要
• 优点：支持多道程序，无内部碎片
• 缺点：有外部碎片【可通过紧凑技术处理】
• 回收内存分区时，可能会遇到四种情况【原则：相邻的空闲分区要合并】：
  • 回收区之后有相邻的空闲分区
  • 回收区之前有相邻的空闲分区
  • 回收区前、后都要相邻的空闲分区
  • 回收区前、后都没有相邻的空闲分区
• 基于顺序搜索的分配算法：

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序
最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片，算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程，算法开销大（原因同上）
邻近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列（可排列成循环链表）	不用每次都从低地址的小分区开始检索，算法开销小（原因同首次适应）	内存低、高地址部分的空闲分区以同等概率被分配，划分为小分区，导致内存高地址部分没有大空闲区可用

• 基于索引搜索的分配算法【大、中型系统】：

算法	算法思想	优点	缺点
快速适应算法	首先根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表；然后从链表中取出第一块进行分配	查找效率高、不产生内部碎片	回收分区时，需要有效合并分区，算法比较复杂，系统开销较大
伙伴系统	规定所有分区的大小均为 2 的 k 次幂 操作系统学习笔记（九）：连续内存分配——伙伴系统_伙伴系统是一种内存分配算法,其特点是-CSDN博客
哈希算法	根据空闲分区链表的分区规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针。分配时，根据所需分区大小，通过哈希函数计算得到哈希表中的位置，从中得到相应的空闲分区链表

基本分页存储管理

分页思想

• 将内存空间分为若干固定大小（如 4 KB）的分区，称为页框、页帧或物理块
• 内存空间中的每个页框有一个编号，称为页框号、物理块号，从 0 开始
• 进程的逻辑地址空间也分为与块大小相等的若干区域，称为页或页面
• 进程的逻辑地址空间中的每个页面有一个编号，称为页号，从 0 开始
• 进程在执行时需要申请内存空间，即要为每个页面分配内存中的可用页框，形成一一对应的关系
• 特点：
  • 不产生外部碎片
  • 产生内部碎片（很小）
  • 分页是面向计算机的

页表

• 为了能知道进程的每个页面在内存中存放的位置，OS 要为每个进程建立一张页表
• 进程的每个页面对应一个页表项
• 每个页表项由页号和块号组成【大小相同】，记录了页面在内存中对应的物理块号
• 页表项连续存放，因此页号可以是隐含的，不占用存储空间【i 号页表项存放地址=页表始址 + i * 页表项大小】
• 页表的作用是实现从页号到物理块号的地址映射
• 计算：每个页表项占多少字节？

地址结构

• 页号 + 页内偏移量
• 如果有 K 位表示“页内偏移量”，则说明该系统中，一个页面的大小是 $2^K$ 个内存单元
• 如果有 M 位表示“页号”，则说明在该系统中，一个进程最多允许有 $2^M$ 个页面
• 地址结构决定了虚拟内存的寻址空间有多大
• 页号 = 逻辑地址 / 页面长度（取除法的整数部分）
• 页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）
• 页面大小刚好是 2 的整数幂有什么好处？
  • 逻辑地址的拆分更加迅速：如果每个页面大小为 $2^k$ B，用二进制数表示逻辑地址，则不需要除法运算可知，末尾 k 位为页内偏移量，其余部分是页号
  • 物理地址的计算更加迅速：根据逻辑地址得到页号，根据页号查询页表从而找到页面存放的内存块号，将二进制表示的内存块号和页内偏移量拼接起来，就可得到最终的物理地址
• 页面太小会使进程的页面数过多，页表过长，占用大量内存，增加硬件地址转换的开销，降低页面换入/换出的效率
• 页面太大会使页内碎片增多，降低内存的利用率

基本地址变换机构

• 任务：将逻辑地址转换为内存中的物理地址
• 页表寄存器（PTR）：
  • 存放页表在内存的始址 F 和页表长度 M
  • 单 CPU 系统中只设置一个
  • 进程未执行时，F 和 M 存放在本进程的 PCB 中；当进程被调度执行时，将装入 PTR
• 设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下：
  1. 计算页号 P = A / L、页内偏移量 W = A % L
  2. 判断页号是否越界：若 P >= M，产生越界中断，否则，继续执行
  3. 在页表中查询页号对应的页表项，确定页面存放的物理块号【页号 P 对应的页表项地址 = F + P * 页表项长度，取出该页表项内容 b，即为物理块号 】
  4. 计算物理地址 E = b * L + W，并用物理地址访存【页面在内存中的始址 = b * L 】
• 整个地址变换过程均由硬件自动完成
• 页式管理中地址空间是一维的
• 两次访存：
  • 第一次：访问页表，确定所存取的数据或指令的物理地址
  • 第二次：访问目标内存单元

具有快表的地址变换机构

• 快表（TLB）【相联存储器】：
  • 具有并行查找能力的高速缓冲存储器
  • 用来存放当前访问的若干页表项，以加速地址变换的过程
  • 基于局部性原理

1. 计算页号、页内偏移量
2. 检查页号合法性
3. 查快表，若找到匹配的页号，直接读出对应的物理块号，一次访存
4. 若没有找到，访问主存的页表，读出页表项后，同时将其存入快表，两次访存

两级页表

• 逻辑地址结构：一级页号 + 二级页号 + 页内偏移量
• 在页表的每个表项中，存放的是进程的某页对应的物理块号
• 在外层页表（页目录）的每个表项中，存放的是每个页表分页的始址
• 需要增设一个外层页表寄存器【页目录基址寄存器】，用于存放页目录始址
• 利用页目录和页表实现从逻辑地址到物理地址的转换：
  • 从 PCB 中读出页目录表始址
  • 根据页目录号查页目录表，从而找到对应页表的地址【第一次访存】
  • 根据二级页号查页表，从而找到对应的页表项【第二次访存】
  • 将页表项中的物理块号和页内偏移量拼接，即为物理地址，再访问对应内存单元【第三次访存】
• 注意：一般来说各级页表的大小不能超过一个页面
• 若没有快表机构，N 级页表访问一个逻辑地址需要 N + 1 次访存

基本分段存储管理方式

分段思想

• 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从 0 开始编址
• 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以互不相邻【段内要求连续，段间不要求连续】
• 由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高
• 特点：
  • 方便编程、信息保护和共享
  • 方便动态链接、增长
  • 会产生外部碎片

段表

• 每个进程都有一张逻辑空间与内存空间映射的段表
• 进程的每个段对应一个段表项，记录了该段在内存中的起始位置【基址】和段的长度
• 各个段表项的长度相同，因此段号可以是隐含的，不占用存储空间
• 段表用于实现从逻辑段到物理内存区的映射

地址结构

• 段号 + 段内偏移量
• 段号的位数决定了每个进程最多可以分几个段
• 段内偏移量的位数决定了每个段的最大长度是多少
• 段号和段内偏移量必须由用户显示提供【在高级程序设计语言中，这个工作由编译程序完成】

地址变换机构

• 任务：实现进程从逻辑地址到物理地址的变换功能
• 段表寄存器：
  • 存放段表始址 F 和段表长度 M
  • 存放于进程的 PCB 中
• 地址变换过程：
  1. 从逻辑地址 A 中取出前几位为段号 S，后几位为段内偏移量 W
  2. 判断段号是否越界，若段号 S >= 段表长度 M，则产生越界中断，否则继续执行
  3. 在段表中查询段号对应的段表项【段号 S 对应的段表项地址 = F + S * 段表项长度】，取出该段的段长 C，若 W >= C，则产生越界中断，否则继续执行
  4. 取出段表项中该段的始址 b，计算物理地址 E = b + W，用物理地址去访存
• 地址空间是二维的
• 两次访存：
  • 第一次：查内存中的段表
  • 第二次：访问目标内存单元

分页和分段的对比

• 页是信息的物理单位，分页的主要目的是提供内存利用率，分页完全是系统行为，对用户不可见
• 段是信息的逻辑单位，分段的主要目的是更好地满足用户需求，用户按照逻辑关系将程序划分为若干段，分段对用户是可见的
• 页的大小固定且有系统决定
• 段的长度不固定，具体取决于用户编写的程序
• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址
• 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址
• 分段比分页更容易实现信息的共享和保护

段的共享与保护

• 共享实现：
  • 在每个进程的段表中设置一个段表项，指向被共享的同一物理段
  • 为了防止程序在执行时修改共享代码，在每个进程中都必须配以局部数据区，将在执行过程中可能改变的部分复制到数据区
• 保护实现：
  • 存取控制保护
  • 地址越界保护：两次越界判断【段号、段内偏移】

段页式存储管理方式

段页思想

• 分页存储管理能有效提高内存利用率，分段存储管理能反映程序的逻辑结构并有利于段的共享和保护，于是将两种方式结合起来
• 进程的地址空间：首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页
• 内存空间：和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位

地址结构

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

地址变换机构

• 每个进程建立一张段表，每个段对应一个段表项，每个段表项至少包括段号、页表长度和页表始址【每个段表项长度相等，段号隐含】
• 每个段有一张页表，每个页面对应一个页表项，每个页表项至少包括页号、页面存放的内存块号【每个页表项长度相等，页号隐含】
• 系统中有一个段表寄存器，指出进程的段表始址和段表长度【用于寻址和判断越界】
• 地址空间是二维的
• 三次访存：
  • 第一次：查段表
  • 第二次：查页表
  • 第三次：访问目标内存单元

虚拟内存管理

虚拟内存

传统存储管理方式的特征

• 一次性：
  • 作业必须一次性全部装入内存，才能开始运行
• 驻留性：
  • 作业被装入内存后，就一直驻留在内存中，直到作业结束
  • 运行中的进程会因等待 I/O 而被阻塞，可能处于长期等待状态

局部性原理

• 时间局部性：
  • 程序中的某条指令一旦执行，不久后该指令可能再次运行
  • 原因是程序中存在着大量的循环结构
• 空间局部性：
  • 程序在一段时间内所访问的地址，可能集中在一定的范围内
  • 因为指令通常是顺序存放、顺序执行的
• 局部性原理既适用于程序结构，又适用于数据结构

虚拟存储器

• 定义：系统为用户提供的一个比实际内存容量大得多的存储器
  • 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
  • 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存【请求调页/段】，然后继续执行程序
  • 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存【页面/段置换】
• 特征：
  • 多次性：只需将当前运行的那部分程序和数据装入内存即可开始运行【最重要的特征】
  • 对换性：作业无需一直常驻内存，暂不使用的从内存调至外存的对换区（换出），要用时换入
  • 虚拟性：从逻辑上扩充内存的容量【最重要的目标】
• 注意：
  • 虚拟内存的最大容量是由计算机的地址结构（CPU 寻址范围）确定的
  • 虚拟内存的实际容量 = min（内存和外存容量之和，CPU 寻址范围）

虚拟内存的实现

• 方式 【离散分配】：
  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理
• 需要的东西：
  • 一定的硬件支持，一定容量的内存和外存
  • 页表/段表机制，作为主要的数据结构
  • 中断机制，当程序要访问的部分还未调入内存时，产生中断
  • 地址变换机构

请求分页管理方式

基本概念

• 只要求将当前一部分页面装入内存，便可启动作业运行，不需要一次全部装入
• 在作业执行的过程中，当访问的页面不存在时，再通过调页功能将其调入
• 相比基本分页管理，增加的功能：
  • 请求调页功能：将要用的页面调入内存【调入】
  • 页面置换功能：将不用的页面换出到外存【调出】

页表机制

• 页表的构成：页号 + 页框号 + 状态位 P + 访问字段 A + 修改位 M + 外存地址【新增后四个字段】
• 状态位/合法位 P：标记该页是否已被调入内存中供程序访问时参考，用于判断是否触发缺页异常
• 访问字段 A：记录本页在一段时间内被访问的次数供置换算法换出页面时参考
• 修改位 M：标识该页在调入内存后是否被修改过当页面被淘汰时，若页面数据没有修改，则不用写回外存
• 外存地址：用于指出该页在外存上的地址，通常是物理块号供写回外存和从外存中调入此页时参考

缺页中断机构

• 缺页：
  • 是在 CPU 执行某条指令过程中，进行取指令或读写数据时发生的一种故障，是内中断【异常】
  • 每当要访问的页面不在内存中时，便产生一个缺页中断，请求 OS 将所缺的页调入内存
  • 缺页中断是访存指令引起的，说明所要访问的页面不在内存中
  • 进行缺页中断处理并调入所要访问的页后，访存指令应该重新执行
  • 特点：
    • 在指令执行期间而非一条指令执行完后产生和处理中断信号
    • 一条指令在执行期间，可能产生多次缺页中断
• 处理过程：
  • 假设此时要访问逻辑地址=（页号，页内偏移量）=（0, 1024）
  • 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
  • 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
  • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
  • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存【未修改过的页面不用写回外存】

地址变换机构

• 相比基本分页管理，增加的步骤：
  • 请求调页（查到页表项时进行判断）
  • 页面置换（需要调入页面，但没有空闲内存块时进行）
  • 需要修改请求页表中新增的表项

1. 先检索快表，若命中，从相应表项中取出该页的物理块号，并修改页表项中的访问位，以供置换算法换出页面时参考
2. 若快表未命中，则要到页表中查找，若找到，则从相应表项中取出物理块号，并将该页表项写入快表，若快表已满，则需采用某种算法替换
3. 若在页表中未找到，则需要进行缺页中断处理，请求系统将该页从外存换入内存，页面被调入内存后，由 OS 负责更新页表和快表，并获得物理块号
4. 根据形成的物理地址访存 注意：

• 只有“写指令”才需要修改“修改位”，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表【这样可以减少访存次数】
• 换入/换出页面都需要启动慢速的 I/O 操作，可见，如果换入/换出太频繁，会有很大的开销
• 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中

页框分配策略

驻留集

• 驻留集：给一个进程分配的物理页框（也叫做物理块）的集合
• 驻留集越小：驻留在内存的进程就越多，可以提高多道程序的并发度，但分配给每个进程的页框太少，会导致缺页率较高，CPU 需耗费大量时间处理缺页
• 驻留集越大：分配的页框过多时，对缺页率的改善不明显，反而是浪费内存空间，还会导致多道程序并发度下降

页面分配、置换策略

• 两种内存分配策略：
  • 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，驻留集大小不变，分配的算法有：
    • 平均分配算法
    • 按比例分配算法
    • 优先权分配算法
  • 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，驻留集大小可变
• 两种页面置换策略：
  • 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
  • 局部置换：发生缺页时只能选进程自己的物理块进行置换
• 固定分配局部置换：
  • 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面
  • 缺点：很难在刚开始就确定应为每个进程分配多少个物理块才算合理
• 可变分配全局置换：
  • 刚开始会为每个进程分配一定数量的物理块，操作系统会保持一个空闲物理块队列
  • 当某进程发生缺页时，从空闲物理块中取出一块分配给该进程
  • 优点：只要某进程发生缺页，都将获得新的物理块
  • 缺点：被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加
• 可变分配局部置换：
  • 刚开始会为每个进程分配一定数量的物理块
  • 当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存
  • 根据发生缺页的频率来动态地增加或减少进程的物理块【频率高，多分配几个物理块】

何时调入页面

• 预调页策略【运行前调入】：
  • 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效
  • 主要用于进程的首次调入，由程序员指出应该先调入哪些部分
• 请求调页策略【运行时调入】：
  • 进程在运行期间发现缺页时才将所缺页面调入内存
  • 优点：调入的页面一定会被访问到
  • 缺点：每次只能调入一页，每次都要磁盘 I/O 操作，开销较大

从何处调页

• 对换区：存放对换页面，采用连续分配方式，速度更快
• 文件区：存放文件，采用离散分配方式，速度更慢

1. 系统拥有足够的对换区空间：
   • 页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快
   • 在进程运行前，需将进程相关的数据从文件区复制到对换区
2. 系统缺少足够的对换区空间：
   • 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可
   • 对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入
3. UNIX 方式：
   • 运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入
   • 若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入

如何调入页面

• 情况 1：所访问的页面不在内存时 -⇒ 缺页中断 -⇒ 无空闲物理块 -⇒ 决定淘汰页 -⇒ 调出页面 -⇒ 调入所缺页面
• 情况 2：所访问的页面不在内存时 -⇒ 缺页中断 -⇒ 有空闲物理块 -⇒ 调入所缺页面

其他概念

抖动 （颠簸）现象

• 定义：在页面置换时，出现频繁的页面调度行为
• 产生原因：
  • 系统中同时运行的进程太多，分配给每个进程的物理块太少，导致进程在运行时频繁出现缺页，出现频繁的页面调度行为
  • 主要原因是因为页面置换算法不合理
• 解决办法：
  • 撤销部分进程
  • 增加磁盘交换区大小和提高用户进程优先级都与抖动无关

工作集

• 定义：在某段时间间隔内，进程实际访问的页面集合
• 如何确定：基于局部性原理，用最近访问过的页面来确认
• 作用：
  • 工作集反映了进程在接下来一段时间内很可能频繁访问的页面集合
  • 为了防止抖动现象，要使分配给进程的物理块数 【驻留集大小】>= 工作集大小

页面置换算法

最佳置换算法 OPT

• 基本思想：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率
• 特点：
  • 可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面
  • 操作系统无法提前预判页面访问序列，因此，最佳置换算法是无法实现的

先进先出置换算法 FIFO

• 基本思想：每次选择淘汰的页面是最早进入内存的页面
• 实现方法：
  • 把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可
  • 队列的最大长度取决于系统为进程分配了多少个内存块
• 特点：
  • Belady 异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象
  • 只有 FIFO 算法才会出现 Belady 异常
  • 实现简单
  • 与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问，故算法性能差

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

• 基本思想：每次淘汰的页面是最近最久未使用的页面
• 实现方法：
  • 赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间 t
  • 当需要淘汰一个页面时，选择现有页面中 t 值最大的，即最近最久未使用的页面
• 特点：
  • 堆栈类算法
  • 需要寄存器和栈的硬件支持
  • 实现困难，开销大
  • 算法性能好

时钟置换算法 CLOCK

• 基本思想：基于访问位和循环队列，考虑一个页面最近是否被访问过，又称为最近未用算法（NRU）
• 实现方法：
  • 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列
  • 当某页被访问时，其访问位置为 1
  • 当需要淘汰一个页面时，只需检查页的访问位
    • 如果是 0，就选择该页换出
    • 如果是 1，则将它置为 0，暂不换出，继续检查下一个页面
  • 若第一轮扫描中所有页面都是 1，则将这些页面的访问位依次置为 0 后，再进行第二轮扫描
• 特点：
  • 选择一个淘汰页面最多会经过两轮扫描
  • 性能和开销较为均衡
  • 实现简单
  • 未考虑页面是否被修改

改进型的时钟置换算法

• 基本思想：
  • 对于 NRU 算法，如果被淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存【只有被淘汰的页面被修改过时，才需要写回外存】
  • 增加一个置换代价——修改位
  • 优先淘汰既未使用又未修改过的页面
• 实现方法：
  • 用 （访问位，修改位） 的形式表示各页面状态【如（1，1）表示一个页面近期被访问过，且被修改过】
  • 将所用可能被置换的页面排成一个循环队列
  • 第一轮：从当前位置开始扫描到第一个 （0，0）【第一优先级】 的帧用于替换，本轮扫描不修改任何标志位
  • 第二轮：若第一轮扫描失败，则重新扫描，查找第一个 （0，1）【第二优先级】 的帧用于替换，本轮将所有扫描过的帧访问位设为 0
  • 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）【原本（1，0）第三优先级】的帧用于替换，本轮扫描不修改任何标志位
  • 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0，1）【原本（1，1）第四优先级】的帧用于替换
• 特点：
  • 选择一个淘汰页面最多会进行四轮扫描
  • 可减少磁盘的 I/O 操作次数
  • 算法开销较小，相比 NRU 稍有增加

其他概念

内存映射文件

• 定义：

  • 是 OS 向应用程序提供的一个系统调用
  • 与虚拟内存有些相似，在磁盘文件与进程的虚拟地址空间之间建立映射关系

• 特性：

  • 进程可使用系统调用，请求 OS 将文件映射到进程的虚拟地址空间
  • 以访问内存的方式读文件【将一个文件当作内存中的一个大字符数组，不通过 I/O 访问，更便利】
  • 磁盘文件的读入/写出操作由 OS 负责完成，对进程透明
  • 当映射进程的页面时，不会实际读入文件的内容【访问时才被每次一页地读入】
  • 当进程退出或关闭文件映射时，所用被改动的页面才被写回磁盘文件
  • 多个进程可以映射一个文件，方便共享

• 优点：

  • 程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可
  • 文件数据的读入/写出完全由 OS 负责，I/O 效率可以由 OS 负责优化

虚拟存储器性能影响因素

1. 页面较大 -⇒ 缺页率较低 -⇒ 可以减少页表长度，但使得页内碎片增大
2. 页面较小 -⇒ 缺页率较高
   • 可以减少内存碎片，提高内存利用率
   • 使得页表过长，占用大量内存
3. 分配给进程的物理块数越多，缺页率就越低
4. 分配给进程的物理块数超过某个值时，对缺页率的改善并不明显
5. 好的页面置换算法可以使进程在运行过程中具有较低的缺页率
6. LRU，CLOCK 将未来可能要用到的进程保存在内存中，可以提高页面的访问速度
7. 在系统建立一个已修改换出页面的链表，这些页面暂不写回磁盘，仅当换出页面数达到给定值时，才一起写回磁盘，可以显著减少磁盘的 I/O 次数
8. 编写程序的局部化程度越高，执行时的缺页率越低
9. 存储和访问尽量使用相同的访问方式（如按行存储就进行按行访问）

地址翻译

• 见王道书 2025 版 p223，举例较为清晰