操作系统(3)：存储器管理

这是《操作系统》课程的课程笔记系列。本文整理部分为“第3章：存储器管理”。

3.1 内存管理概念

3.1.1 内存管理的基本原理和要求

• 逻辑地址（虚拟地址）与物理地址（绝对地址）
• 从源代码文件到内存中可执行程序的步骤：
  • 编译：由源代码文件生成目标模块
  • 链接：由目标模块生成装入模块，链接后形成完整的逻辑地址
  • 装入：将装入模块装入内存，装入后形成物理地址
• 三种链接方式：
  • 静态链接：装入前链接成一个完整装入模块
  • 装入时动态链接：运行前边装入边链接
  • 运行时动态链接：运行时需要目标模块才装入并链接
• 三种装入方式：
  • 绝对装入：编译时产生绝对地址（单道程序阶段，无操作系统）
  • 可重定位装入（静态重定位）：装入时将逻辑地址转换为物理地址（早期多道批处理阶段）
  • 动态运行时装入（动态重定位）：运行时将逻辑地址转换为物理地址，需设置重定位寄存器（现代操作系统）
• 内存管理的功能：
  • 内存空间的分配和回收
  • 内存空间的扩充：实现虚拟性
  • 地址转换：实现逻辑地址到物理地址的转换
    • 三种方式：绝对装入、可重定位装入、动态运行时装入
  • 存储保护：保证各进程在自己的内存空间内运行，不会越界访问
    • 方法一：设置上下限寄存器，存放进程的上、下限地址
    • 方法二：利用重定位寄存器、界地址寄存器进行越界判断
      • 重定位寄存器：又称基址寄存器，存放进程的起始物理地址
      • 界地址寄存器：又称限长寄存器，存放进程的最大逻辑地址
• 进程的内存映像：
  • 操作系统内核区：内核代码、内核数据结构等，如进程控制块 PCB
  • 用户栈：由各函数的栈帧组成，包含局部变量、函数调用相关的信息
  • 共享库的存储映射区：被调用的库函数代码
  • 堆：动态分配的变量，由 malloc / free 分配和回收
  • 读 / 写数据：全局变量、静态变量（由 static 修饰）
  • 只读代码 / 数据：程序代码、只读数据（由 const 修饰的常变量）

3.1.2 连续分配管理方式

• 内部碎片：分配给某些进程的内存区域中，如果有些部分没有用上
• 外部碎片：指内存中某些空闲分区由于太小而难以利用

1. 单一连续分配

• 特点：只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
• 优点：实现简单；无外部碎片；可采用覆盖技术扩充内存；不一定需要采取内存保护
• 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低

2. 固定分区分配

• 特点：支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业
• 两种分区方式：分区大小相等、分区大小不等
• 记录方式：分区说明表，每个表项包括对应分区的大小、起始地址、状态（是否已分配）
• 优点：实现简单；无外部碎片
• 缺点：用户程序太大时需要覆盖技术；有内部碎片，内存利用率低

3. 动态分区分配

• 特点：支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区
• 记录方式：
  • 空闲分区表：
    • 每个空闲分区对应一个表项
    • 表项包含分区号、分区大小、分区起始地址等
  • 空闲分区链：
    • 每个分区的起始部分和末尾部分分别设置前向指针和后向指针
    • 起始部分处还可记录分区大小等
• 碎片情况：无内部碎片，有外部碎片（外部碎片可通过紧凑技术解决）
• 分区回收：回收后要合并前后相邻的空闲分区
• 动态分区分配算法：当多个空闲分区都能满足需求时，应该选择哪个分区进行分配

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

3.1.3 基本分页存储管理

• 基本思想：把进程分页，各个页面可离散地放到各个的内存块中
• 概念辨析：
  • “页框、页帧、内存块、物理块、物理页”与“页、页面”
  • “页框号、页帧号、内存块号、物理块号、物理页号”与“页号、页面号”
• 页表：记录了页面和实际存放的内存块之间的映射关系
  • 一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由页号和块号组成
  • 每个页表项的大小是相同的；页号是隐含的，不占存储空间
  • i 号页表项存放地址 = 页表始址 + i * 页表项大小
• 逻辑地址结构：可分解为【页号，页内偏移量】
  • 页号 = 逻辑地址 / 页面大小
  • 页内偏移量 = 逻辑地址 % 页面大小
• 页表寄存器：存放页表起始地址、页表长度
  • 进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中
  • 当进程被调度时，操作系统内核会把它们放到页表寄存器中
• 基本地址变换机构：
  • 地址转换的过程：需要访问内存两次
    1. 根据逻辑地址计算出页号、页内偏移量
    2. 越界检查，确认页号小于页表长度
    3. 若合法，查页表，即根据页表起始地址、页号找到对应页表项
    4. 根据页表项中记录的内存块号、页内偏移量得到最终的物理地址
       • 物理地址 = 页面始址 + 页内偏移量
    5. 访问物理内存对应的内存单元
  • 注意：
    • 页内偏移量位数与页面大小之间的关系
    • 页式管理中地址是一维的，程序员只需给出一个记忆符即可表示一个地址
    • 实际应用中，通常使一个页框恰好能放入整数个页表项
    • 为了方便找到页表项，页表一般存放在连续的内存块中
• 具有快表的地址变换机构：
  • 快表（TLB）：用于存放最近访问的页表项的副本，可以加速地址变换的速度
  • 快表清空：当发生进程切换时，操作系统会清空快表内容
  • 地址转换的过程：若快表命中，只需访问内存一次（未命中则两次）
    1. 根据逻辑地址计算出页号、页内偏移量
    2. 越界检查，确认页号小于页表长度
    3. 若合法，则根据页号查快表
    4. 若快表命中，即可知道页面存放的内存块号，可直接进行 f
    5. 若未命中，查页表，找到页面存放的内存块号，并且将页表项复制到快表中
    6. 根据内存块号、页内偏移量得到最终的物理地址
    7. 访问物理内存对应的内存单元
• 两级页表：将页表再分页，建立页目录表（又称外层页表、顶级页表）
  • 单级页表的问题：
    • 所有页表项必须连续存放，页表过大时需要很大的连续空间
    • 在一段时间内并非所有页面都用得到，因此没必要整个页表常驻内存
  • 逻辑地址结构：可分解为【一级页号，二级页号，页内偏移量】
  • 地址转换过程：需要访问内存三次（假设没有快表机构）
    1. 按照地址结构将逻辑地址分解为一级页号、二级页号、页内偏移量
    2. 从 PCB 中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
    3. 根据二级页号查表，找到最终想访问的内存块号
    4. 结合页内偏移量得到物理地址
  • 注意：多级页表中，各级页表的大小不能超过一个页面；若两级页表不够，可以分更多级

3.1.4 基本分段存储管理

• 分段：将地址空间按照程序自身的逻辑关系划分为若干个段，每段从 0 开始编址
  • 每个段在内存中占据连续空间，但各段之间可以不相邻
• 逻辑地址结构：可分解为【段号，段内地址】
  • 段号的位数决定了每个进程最多可以分几个段
  • 段内地址位数决定了每个段的最大长度
• 段表：记录逻辑段到实际存储地址的映射关系
  • 每个段对应一个段表项，每个段表项由段号、段长、基址组成
  • 各段表项长度相同；段号是隐含的，不占存储空间
• 地址变换过程：
  1. 由逻辑地址得到段号、段内地址
  2. 段号与段表寄存器中的段长度比较，检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的段长，检查段内地址是否越界
  5. 由段表中的“基址+段内地址”得到最终的物理地址
  6. 访问目标单元
• 分段和分页的对比：
  • 分页对用户不可见，分段对用户可见
  • 分页的地址空间是一维的，分段的地址空间是二维的
    • 程序员在标识一个地址时，既要给出段名，也要给出段内地址
  • 分段更容易实现信息的共享和保护（纯代码或可重入代码可以共享）
  • 分页（单级）或分段访问一个逻辑地址都需要两次访存；分段存储中也可以引入快表机构

3.1.5 段页式存储管理

• 分段再分页：将地址空间按照程序自身的逻辑关系划分为多段，再将各段分为大小相等的页面
  • 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
• 逻辑地址结构：可分解为【段号，页号，页内偏移量】
• 段表与页表：
  • 段表：每个段对应一个段表项，各段表项长度相同
    • 由段号（隐含）、页表长度、页表存放地址组成
  • 页表：每个页对应一个页表项，各页表项长度相同
  • 由页号（隐含）、页面存放的内存块号组成
• 地址变换过程：
  1. 由逻辑地址得到段号、页号、页内偏移量
  2. 段号与段表寄存器中的段长度比较，检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的页表长度，检查页号是否越界
  5. 由段表中的页表地址、页号得到查询页表，找到相应页表项
  6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
  7. 访问目标单元
• 访存次数：访问一个逻辑地址需要三次访存
  • 第一次–查段表、第二次–查页表、第三次–访问目标单元
  • 可引入快表机构，以段号和页号为关键字查询快表，命中则仅需一次访存

3.2 虚拟内存管理

3.2.1 虚拟内存的基本概念

• 传统存储管理方式的特征和缺点：
  • 一次性：作业数据必须一次全部调入内存
  • 驻留性：作业数据在整个运行期间都会常驻内存
• 局部性原理：
  • 时间局部性：现在访问的指令、数据在不久后很可能会被再次访问
  • 空间局部性：现在访问的内存单元周围的内存空间，很可能在不久后会被访问
  • 高速缓存技术：使用频繁的数据放到更高速的存储器中
• 虚拟内存：程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据
• 虚拟内存的特征：
  • 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
  • 对换性：无需在作业运行时一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
  • 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量
• 虚拟内存的功能要求：
  • 请求调页功能：访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存
  • 页面置换功能：内存空间不够时，将内存中暂时用不到的信息换出到外存
• 虚拟内存技术的实现：请求分页存储管理、请求分段存储管理、请求段页式存储管理

3.2.2 请求分页管理方式

• 页表机制：在基本分页的基础上增加了几个表项
  • 状态位：表示页面是否已在内存中
  • 访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
  • 修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存
  • 外存地址：页面在外存中存放的位置
• 缺页中断机构：
  • 缺页中断的产生：找到页表项后检查页面是否已在内存，若没在内存，产生缺页中断
  • 缺页中断的处理：将目标页面调入内存，有必要时还要换出页面
  • 缺页中断属于内中断，属于内中断中的“故障”，即可能被系统修复的异常
  • 一条指令在执行过程中可能产生多次缺页中断
• 地址变换机构：与基本分页的不同之处
  • 找到页表项是需要检查页面面是否在内存中
  • 若页面不再内存中，需要请求调页
  • 若内存空间不够，还需换出页面
  • 页面调入内存后，需要修改相应页表项

3.2.3 页面置换算法

算法名称	算法规则	优缺点
最佳置换算法（OPT）	优先淘汰最长时间内不会被访问的页面	缺页率最小，性能最好；但无法实现
先进先出置换算法（FIFO）	优先淘汰最先进入内存的页面	实现简单；但性能很差，可能出现 Belady 异常
最近最久未使用置换算法（LRU）	优先淘汰最近最久没访问的页面	性能很好；但需要硬件支持，算法开销大
时钟置换算法（CLOCK）	循环扫描各页面；第一轮淘汰访问位为 0 的，并将扫描过的页面访问位改为 0；若第一轮没选中，则进行第二轮扫描	实现简单，算法开销小；但未考虑页面是否被修改过
改进型时钟置换算法	若用（访问位，修改位）的形式表述，则第一轮：淘汰（0,0）；第二轮：淘汰（0,1），并将扫描过的页面访问位都置 0；第三轮：淘汰（0,0）；第四轮：淘汰（0,1）	算法开销较小，性能也较好

3.2.4 页面分配策略

• 驻留集：指请求分页存储管理中给进程分配的内存块的集合
• 页面分配与置换策略：
  • 固定分配 / 可变分配：区别在于进程运行期间驻留集大小是否可变
  • 局部置换 / 全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
  • 固定分配局部置换：进程运行前就分配一定数量物理块，缺页时只能换出进程自己的某一页
  • 可变分配全局置换：只要缺页就分配新物理块，可能来自空闲物理块，也可能需换出别的进程页面
  • 可变分配局部置换：频繁缺页的进程，多分配一些物理块；缺页率很低的进程，回收一些物理块；直到缺页率合适
• 何时调入页面：
  • 预调页策略：一般用于进程运行前
  • 请求调页策略：进程运行时，发现缺页再调页
• 从何处调页：
  • 对换区足够大：运行前将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
  • 对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
  • UNIX 方式：第一次使用的页面都从文件区调入；调出的页面都写回对换区，再次使用时从对换区调入

• 对换区：采用连续存储方式，速度更快
• 文件区：采用离散存储方式，速度更慢

• 抖动现象：页面频繁换入换出的现象，主要原因是分配给进程的物理块不够
• 工作集：在某段时间间隔里，进程实际访问页面的集合
  • 驻留集大小一般不能小于工作集大小

3.2.5 内存映射文件

• 特性：
  • 进程可使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间
  • 以访问内存的方式读写文件
  • 进程关闭文件时，操作系统负责将文件数据写回磁盘，并解除内存映射
  • 多个进程可以映射同一个文件，方便共享
• 优点：
  • 程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可
  • 文件数据的读入/写出完全由操作系统负责，I/O 效率可以由操作系统负责优化