【操作系统】内存管理
本文最后更新于：2023年12月17日 下午
前言
操作系统是每个程序员都该钻研学习的知识，最近也是在复习回顾，所以趁此机会做个简单的记录和总结，而本文将主要介绍操作系统中内存管理相关的内容。
本文的一些图片和文字将引用参考北京大学陈向群老师的《操作系统高级课程》中的PPT课件，以及MIT 6.S081 课程相关内容。
重要概念
首先引入一些重要概念/前置知识点：
- 程序以文件形式（可执行文件格式，如Linux上的ELF文件格式，window上的PE文件格式）保存在磁盘，程序装载到内存才可以运行
- 现代操作系统采用多道程序设计模型：即允许多个程序同时进入内存
- 每个进程都有自己独立的地址空间，体现了隔离性和安全性：一个进程在执行时不能访问另一个进程的地址空间，也不能去执行不适当的操作
- 局部性原理：程序在执行的时候往往呈现局部性规律，也就是说在某个较短的时间段内，程序执行局限于某一小部分，程序访问的存储空间也局限于某个区域
- 时间局部性： 如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型例子，就是在程序中存在着大量的循环操作；
- 空间局部性： 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定范围之内，这是因为指令通常是顺序存放、顺序执行的，数据一般是以向量、数组、表等形式簇聚存储的。
- 存储体系：存储器主要有3个性能指标：速度、容量、每位价格（位价），一般来说速度快的存储器容量偏小，位价较贵；容量大的，速度慢，位价便宜。计算机中的存储体系如下图所示，越上层的存储器性能（速度）越好，但位价越贵。
- 程序执行前的准备过程
- 在程序运行前，通常要经过编译、链接、装载、运行等过程，如下图所示。那就产生一个问题，就是什么时候将指令和数据绑定到内存地址/物理地址？也就是下面要探讨的地址重定位。
地址重定位：将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址的过程，其作用是保证CPU执行指令时可以正确地访问内存单元
- 逻辑地址（相对地址，虚拟地址）：用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能使用逻辑地址在内存中读取信息。
- 物理地址（绝对地址，实地址）：内存中存储单元的地址，可以直接寻址。
地址重定位又可以分为静态重定位和动态重定位。
- 在静态重定位中，地址转换发生在装载时：当程序装载到内存中时，
store指令对应的地址已经转变成了物理地址 - 在动态重定位中，地址转换发生在运行时：当程序装载到内存中时，
store指令对应的地址仍然是逻辑地址，当真正运行该条指令时，会通过硬件MMU（内存管理单元）将逻辑地址转换为物理地址
- 在静态重定位中，地址转换发生在装载时：当程序装载到内存中时，
这也引出了内存管理的基本目标：
- 给进程分配内存——地址空间
- 往内存加载内容——映射进程地址空间到物理内存
- 存储保护——地址越界、权限控制
- 管理共享的内存
- 最小化存储访问时间
内存管理方案
空闲物理内存管理
数据结构：
- 位图：每个分配单元对应于位图中的一位，0表示空闲，1表示占用（或者相反）
- 空闲区表、已分配区表：表中的每一项记录了空闲区（或已分配区）的起始地址、长度、标志
- 空闲块链表
内存分配算法：
- 首次适配 (first fit) ：在空闲区表中找到第一个满足进程要求的空闲区
- 下次适配 (next fit) ：从上次找到的空闲区处接着查找
- 最佳适配 (best fit)：查找整个空闲区表，找到能够满足进程要求的最小空闲区
- 最差适配 (worst fit)：总是分配满足进程要求的最大空闲区
伙伴系统——Linux底层采用的内存管理方案
下图是伙伴系统的一个例子：
可以看到分配时，将可用区间不断分成两块，直到划分出能满足需求的最小块（满足2的幂次）；在回收时，只有当两个大小相同且相邻的内存块被释放后，可以进行回收合并，“伙伴系统”的含义也是由此而来。
内存管理基本方案汇总
单一用户（连续区）
特点：一段时间内只有一个进程在内存。
简单，但是内存利用率低。
固定分区
把内存空闲分割成若干区域，成为分区。（每个分区的大小可以相同也可以不同）
分区的大小固定不变。
每个分区装一个且只能装一个进程。
存在的问题：有内部碎片，对内存的使用不充分，活动进程的最大数目是固定的。
可变分区
根据进程的需要，把内存空闲空间分割出一个分区，分配给该进程。
剩余部分成为新的空闲区。
实现的数据结构：空闲区表，已分配表。
存在的问题：存在外碎片，导致内存利用率下降。
解决方案：可以采用紧凑技术。在内存中移动程序，将所有小的空闲区合并为较大的空闲区，但需要考虑系统开销和移动时机。
页式存储管理
设计思想：
- 用户程序地址空间划分成大小相等的区域——页 page
- 物理内存空间按页大小划分大小相等的区域，成为内存块（物理页面，页框，页帧）page frame
- 内存分配规则：以页为单位机械能分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻
- 典型的页面尺寸：4K 或 4M
- 逻辑地址：对于32位机器，页面大小为4K，其逻辑地址可分成页号（前20位）和页内偏移（后12位）。
相关数据结构以及地址转换：
- 页表
- 页表项：记录了逻辑页号与页框号的对应关系
- 每个进程一个页表，存放在内存中
- 进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
- 空闲内存管理
- 地址转换（硬件支持）：CPU取到逻辑地址，自动划分为页号和页内地址；用页号查页表，得到页框号，再与页内地址（页内偏移）拼接得到物理地址
优缺点：
- 优点
- 虚存量大，适合多道程序运行，用户不必担心内存不够的调度操作。
- 内存利用率高，不常用的页面尽量不留在内存。
- 不要求作业连续存放，有效地解决了外碎片问题（但可能还是会有内碎片产生）。
- 缺点
- 地址变换机构复杂，为提供速度采用硬件实现，增加了机器成本
- 需要相应的硬件支持，来处理页面中断、缺页中断处理等，增加系统开销。
段式存储管理
设计思想：
- 用户程序地址空间：按程序自身的逻辑划分为若干个程序段，每个程序段都有一个段名
- 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定
- 内存分配规则：以段为单位进行分配，每一个段在内存中占据连续空间，但各段之间可以不相邻
- 逻辑地址：分为段号和段内地址
相关数据结构及地址转换：
- 段表
- 记录了段号、段首地址和段长度之间的关系
- 每个进程一个段表，存放在内存
- 物理内存管理：同可变分区
- 地址转换（硬件支持）
- CPU取到逻辑地址，用段号查段表，得到段的起始地址，再与段内偏移地址相加计算出物理地址
优缺点[1]：
- 优点
- 段式管理是不连续分配内存技术中的一种。其最大特点在于他按照用户观点，即按程序段、数据段等有明确逻辑含义的“段”，分配内存空间。克服了页式的、硬性的、非逻辑划分给保护和共享与支态伸缩带来的不自然性[2]。
- 可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位进行共享，包括通过动态链接进行代码共享。
- 缺点：会产生外部碎片
这里再解释一个问题，为什么说页式存储的地址空间是一维的，而段式存储的地址空间是二维的？[3]
段号和页号的来历是不同的，段号是程序员自己定义的，每个段都是有特定含义的，因此不同段的大小不同，代表的意义也不相同，因此要想找到某个数据或指令，需要指定段号和位移两个变量。而页号是系统自动生成的，本身地址是线性连续的，当要访问特定地址时，只需要提供地址即可。系统会自动将地址划分为页号和页内偏移，而页号对于程序员来说是没有实际意义的，因此是一维的。
段页式存储管理方案
产生背景
- 结合页式段式优点，克服二者的缺点
设计思想
- 用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统来讲，按页划分每一段）
- 内存划分：按页式存储管理方案
- 内存分配：以页为单位进行分配
数据结构及有关操作
- 段表：记录了每一段的页表起始地址和页表长度
- 页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）
- 空闲区管理以及分配回收：同页式管理
地址转换
- 通过段号查段表，获得该段的页表起始地址，再通过段内地址对应的页号查页表，获得对应的页帧号，拼接上页内地址，最终得到物理地址
内存扩充技术
当内存不足时如何管理？
- 内存紧凑（例如：可变分区）
- 覆盖技术
- 交换技术
- 虚存技术
上面技术的目标都是为了解决在较小的存储空间中运行较大程序时遇到的矛盾，本小节将重点介绍覆盖技术和交换技术，虚存技术会在下一节着重介绍。
覆盖技术（Overlaying）
解决的问题：程序大小超过物理内存总和
定义描述：在程序执行过程中，程序的不同部分在内存中相互替代
- 按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
- 要求程序个模块之间有明确的调用结构
- 程序员声明覆盖结构，操作系统完成自动覆盖
- 主要用在早期的操作系统
如上图所示，程序段B和C能共用同一块内存区，D、E、F能共用同一块内存区（之所以能共用，是因为程序的逻辑保证这些程序段不会同时运行）。
覆盖技术的不足：
- 增加编程困难
- 需要程序员划分功能模块，并确定模块间的覆盖关系
- 增加了编程的复杂度
- 增加执行时间
- 从外存装入覆盖模块
- 时间换空间
交换技术（Swapping）
设计思想
- 内存空间紧张时，系统间该内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域（进程在内存与外存之间的动态调度）
- 最早用于小型分时系统（roll in roll out）
讨论：实现时需要考虑的问题
- 进程的什么部分需要交换到磁盘？
- 运行时创建或修改的内容，也就是栈和堆。而代码段和数据段在磁盘本身就有来源，所以无需交换
- 在磁盘的什么位置保存被换出的进程？
- 交换区：一般系统会指定一块特殊的磁盘区域作为交换空间（swap space），包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问
- 何时需要发生交换？
- 只要不用就换出（很少再用）；内存空间不够或有不够的危险时换出
- 与调度器结合使用
- 如何选择被换出的进程？
- 需要考虑进程的各种属性；不应该换出正处于等待I/O状态的进程
- 换出后再换入的进程是否回到原处？
- 换出后又换入的进程不一定回到原处（采用动态重定位）
虚拟存储管理
相关术语辨识
虚拟内存
把物理内存与磁盘结合起来使用，得到一个容量很大的“内存”，即虚存
程序引用内存所使用的的地址与内存物理地址是不同的， 可被自动转换成物理地址
虚存大小受计算机系统寻址机制和可用磁盘容量的限制
虚拟地址空间
- 分配给进程的虚拟内存
虚拟地址
- 虚拟内存中某一位置的地址，该位置可以被访问，仿佛它是内存的一部分
虚拟存储技术
- 当进程运行时，先将其一部分装入内存，另一部分暂时保存在磁盘；当要执行的指令或访问的数据不再内存时，由操作系统自动完成将它们从磁盘调入内存的工作
虚拟页式存储管理
基本思想
- 装载程序时，不是装入全部页面，而是装入几个甚至零个页面
- 如果进程执行时需要的页面不在内存（Page Fault），则动态装入所需页面
- 需要时，将内存中暂时不用的一些页面交换到磁盘，以便获得更多的内存空间
通常由两种方式
- 请求调页（demand paging）：当需要的页面不在内存时，引发缺页错误，去装入所需页面
- 预先调页（prepaging）：利用局部性原理，将预计在不久之后便会被访问的页面预先调入内存。
调页机制
- 进程的虚拟地址空间与为例地址空间分离
- 调页系统的3个重要策略
- 系统何时把页面载入内存——取页策略（fetch policy）
- 系统把页面放在何处——防止策略（placement policy）
- 执行放置操作时发生页框不足时，如何选择从内存里“删除”其他页框——置换策略（replacement policy）
设计与实现时要解决的问题：
- 页表表项的设计
- 如何处理页表巨大的问题？
- 地址重定位与块表（TLB)
- 一种最常见的Page Fault —— 缺页中断
- 驻留集管理
- 置换策略
- 清除策略
- 加载控制
接下来将详细介绍以上各个问题。
页表表项的设计
页表表项通常包含页框号、有效位、访问位、修改位、保护位等。
- 页框号（内存块号、物理页面号、页帧号）
- 有效位（驻留位、中断位）：表示该页是在内存还是在磁盘（Valid、Present）
- 访问位：引用位（Referenced、Accessed）
- 修改位：查看此页是否在内存中被修改过（Dirty、Modified）
- 保护位：读/写/执行（Protection）
下面两张图给出了i386(intel 32位机器)以及RISC-V的页表项设计。
对于RISC-V页表项布局的解释：
- V位决定了该页表项是否有效（V=1时有效）
- R、W、X位分别表示此页是否可以读取、写入和执行。如果这个三个位都是0，那么这个页表项是指向下一级页表的指针，否则它是页表树的一个叶节点（多级页表）
- U位表示该页是否是用户页面（U=0，则用户模式不能访问此页面）
- G位表示这个映射是否对所有虚拟地址空闲有效，硬件可以用这个信息来提高地址转化的性能。
- A位表示自上次A位被清除以来，该页面是否被访问过。
- D位表示自从上次清除D位依赖，该页面是否被弄脏（例如被写入）
- RSW 留给操作系统使用，它会被硬件忽略。
- PPN 表示物理页号，这是物理地址的一部分。若这是一个页目录项，则PPN给出下一个页表的地址；若这是一个页表项，则PPN是转换后物理地址的一部分。
多级页表
多级页表的引入，是为了解决页表连续存放，导致占用过多的问题，因为虽然一个进程的虚拟地址空间很大，但是实际占用的空间很小，所以页表会很稀疏（即大部分页表项都是无效的）。如果采用一级页表，则一个进程有 2^19 页（计算过程如图所示，2G / 4K），即需要有2^19个页表项，那么光是页表项的存储就需要512页（即2MB），而进程本身实际大小或许都没这么大。
所以引入多级页表，通过索引的思想，让一个进程的页表的各页不用再内存中连续存放，也不用给所有页表项都分配内存，只需要为实际使用到的虚拟地址建立页表项映射即可。
- 因为如果一级页表中的一个 PTE 为空，那么相应的二级页表就根本不会存在。这是一种巨大的内存节约。
下图给出了二级页表的结构，以及地址映射的过程。这里虚拟地址是32位的，每个页表项占4个字节（页大小为4K，因此每页都有1K个页表项）。进行地址映射时，前10位作为页目录偏移，查找页目录（一级页表，由全局页目录寄存器记录其物理地址）上的页表项，得到下一级页表的物理地址，再根据后10位作为页表偏移，查找二级页表上的页表项，得到对应数据/代码所在的页号，再拼接末尾12位的页内偏移，得到最终的物理地址。
快表（TLB）
在引入二级页表或者多级页表后，就需要两次或两次以上的内存访问。而CPU的指令处理速度与内存指令的访问速度差异大，因此CPU的速度得不到充分利用。
为了加快地址映射速度，以改善系统性能，就引入了快表（也体现了程序访问的局部性原理）。
快表英文名TLB——Translation Look-aside Buffers，实际上一个相联存储器，其特点是按内容进行并行查找。快表保存正在运行进程的页表的子集（部分表项）。
其工作原理就是采用联想映射技术按内容同时查找，当要转换的虚拟地址在TLB中有记录/命中时，则TLB可以直接返回对应的物理地址，而不再需要根据页表进行转换。而没有命中时，则再去查找页表。
当TLB命中返回对应数据/代码的物理地址时，还需要再去访问内存，为了进一步减少内存访问，又有了高速缓存Cache，缓存了部分内存中的数据，当命中缓存时，可以直接得到数据而无需访问内存。
缺页异常处理
在地址映射过程中，硬件检查页表时发现所要访问的页不再内存，则产生该异常——缺页异常。
操作系统执行缺页异常处理程序：获得磁盘地址（在PCB中记录），启动磁盘IO，将该页调入内存
- 如果内存中有空闲页框，则分配一页，将新调入的页装入内存，并修改页表中相应页表项的驻留位/有效位，以及相应的页框号
- 若内存中没有空闲页框，则需要置换某一页；若该页在内存期间被修改过，则要将其写会磁盘
驻留集管理
驻留集大小：即给每个进程分配多少页框。显然，当驻留集越大时，出现缺页异常的概率越小。
可以采取不同的分配策略：
- 固定分配策略
- 进程创建时就确定驻留集大小。可以根据进程类型（交互、批处理、应用类）或者基于程序员或管理员的需要来确定。
- 可变分配策略
- 根据缺页率评估局部性表现。当缺页率高时增加页框数，当缺页率低时减少页框数。
页面置换算法
置换策略
根据置换范围（计划置换页面的集合是局限在产生缺页中断的进程，还是所有进程的页框），又可分为：
- 局部置换策略：仅在产生本次缺页的进程的驻留集中选择
- 全局置换策略：将内存中所有位锁定的页框都作为置换的候选
置换策略：决定置换当前内存中的哪一个页框。
所有策略的目标都是为了置换最近最不可能访问的页。
- 根据局部性原理，最近的访问历史和最近将要访问的模式间存在相关性，因此大多数策略都基于过去的行为来预测将来的行为。
- 同时要注意，置换策略设计得约精致、越复杂，实现的软硬件开销就越大。
- 置换时的约束条件：不能置换被锁定的页框。
- 给每个页框增加一个锁定位，通过设置锁定位，不让操作系统将进程使用的页面换出内存，避免产生由交换过程带来的不确定的延迟。
- 例如操作系统核心代码、关键数据结构、I/O缓冲区（正在IO的内存页面）
各种置换算法
理想（最佳、最优）置换算法（OPT）
- 设计思想：置换以后不再需要的或最远的将来才会用到的页面
- 实现很难，因为无法预测未来的使用情况
先进先出页面置换算法（FIFO）
- 设计思想：选择内存中驻留时间最长的页并置换
- 实现：页面链表法
- FIFO算法会出现Belady现象，即当分配给进程的物理页面数增加时，缺页次数反而增加
第二次机会置换算法（SCR，Second Chance)
设计思想：按照先进先出算法选择某一页面，检查其访问位R，如果为0（表明近期未访问），则置换该页；如果为1，则给第二次机会，并将访问位置0
时钟算法（Clock），是SCR的一种实现
最近未使用算法（NRU，Not Recently Used）
- 设计思想：选择在最近一段时间内未使用的一页并置换
最近最久未使用算法（LRU，Least Recently Used）
- 选择最后一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页
- 性能上接近OPT
- 实现：使用时间戳或维护一个访问页的栈，但是开销大
最不经常使用算法（NFU，Not Frequently Used）
- 设计思想：选择访问次数最少的页面置换
- 实现：
- 软件计数器，一页一个，初值为0
- 每次时钟中断时，计数器加R
- 发生缺页中断时，选择计数器最小的一页置换
NFU老化算法是软件模拟，NFU老化算法的计数器只有有限位数n，因此置换信息仅限于n个时钟滴答内
工作集模型[4]
- 基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的页框太少了，使得该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断
- 如果能为进程提供与活跃页面数相等的页框数，则可减少缺页中断次数
- 活页页面的集合就是工作集。工作集随着时间可能会发生变化，但在一定时间内是比较稳定的
工作集算法
总结
清除策略
这里的清除策略主要是指，定期地回收页面，以保证系统始终有一定数量的空闲页框。具体内容描述可参考下图。
加载控制
系统并发度：驻留在内存中的进程数目。
通过调节并发进程数对系统负载进行控制。
当系统并发度过高时，会导致进程切换频繁，而CPU利用率下降。
解决方案：进程挂起，即释放一部分进程所占有的页面，把它们交换到磁盘上
地址转换练习
最后为了巩固地址转换的过程，来做道练习题吧。如下图所示，求给出的虚拟地址对应的PDE和PTE的物理地址，假设采用的是二级页表，左边表格是TLB的数据，右边表格是某个物理地址上对应数据。
再此之前，再介绍一下TLB快表的查询方式。如下图所示，给定了一个14位的虚拟地址，前8位为VPN（虚拟地址页号），后6位为地址偏移。VPN又被划分为 TLBT（TLB Tag）和 TLBI（TLB Index），因为这里表格显示的是4行，即TLB是四路相连，所以Index需要两位。在查TLB的时候，现根据TLBI 去查对应的行数，再根据TLBT 值比对 该行中的Tag中。如果存在对应的Tag值，并且Valid有效，则表明命中TLB，可以直接返回对应的PPN（物理页框号）
下图演示了虚拟地址0x9fd28c10的地址映射过程，另外两个地址的映射过程也是类似的。
