「OS」内存管理
基本概念
地址空间：一个进程能够用于访问内存的地址集合
程序：是静止的，存放在磁盘上的可执行文件，是进程的实体。
进程：是动态的，包括进程控制块 PCB，程序和程序处理对象（数据集），是一个程序的执行过程，是资源分配的基本单位。通常把进程分为系统进程和用户进程。
作业：用户需要计算机完成的某项任务，是要求计算机所做工作的集合。通常包括程序、数据、操作说明书。
系统碎片：内存中无法被利用的存储空间称为碎片
内部碎片：分配给作业的存储空间中未被利用的部分
外部碎片：系统中无法利用的小的空闲分区，如分区与分区之间存在的碎片。这是造成内存系统性能下降的主要原因，它可以通过紧凑技术等被整理后清除。
紧凑技术：通过移动作业，把多个分散的小分区拼接成一个大分区。
- 时机：找不到足够大的空闲分区，但总空闲分区容量满足要求。
- 实现支撑：动态重定位
存储管理的功能
- 存储分配和回收
- 地址变换
可执行文件生成中的链接技术、程序加载时的重定位技术、进程运行时硬件和软件的地址变换技术 - 存储共享和保护
- 存储器扩充
分区式内存管理
分区式分配
把内存分为大小相等或不等的分区，每个应用程序占用一个或几个分区。
固定式分区
系统初始化时，内存划分为若干固定大小（不一定相等）的连续分区。程序适应分区。
- 易于实现
- 但内碎片会造成浪费，并且分区总数固定，限制了并发执行的程序数目
- 采用分区表来记录分区大小和使用情况
可变式分区
分区边界可移动
- 没有内碎片，但会有外碎片
闲置空间的管理
跟踪内存使用情况的方法有：位图表示法和链表表示法
位图表示法
给每个分配单元赋予一个二进制数位,用来记录该分配单元是否闲置
- 空间开销固定，时间开销低，但没有容错能力。
链表表示法
将分配单元按照是否闲置链接起来。
- 有一定的容错能力：链表有被占空间和闲置空间的表项，可以相互验证
分配算法
基于顺序搜索
首次适应算法
每个空闲区按其在内存中地址递增的顺序连在一起，在为作业分配存储区域时，从空闲区域链的始端开始查找，选第一个满足请求的空白块。
- 导致空闲碎片集中在低地址区
下次适应算法
将所有空闲区组织成一个循环链表，每次为存储请求查找合适分区时，总是从上次查找结束的地方开始
- 可能会导致缺乏大的空闲分区
最佳适应算法
寻找大小最接近作业要求的存储区域
- 产生许多难以利用的小空闲碎片
最坏适应算法
总是寻找最大的空闲区
- 缺乏大的空闲分区
基于索引搜索
比顺序搜索快，一般用于大中型系统
快速适应算法
把空闲分区按容量大小进行分类，常用大小的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。
伙伴系统
介于固定分区与可变分区之间的动态分区技术。规定：无论已分配分区或空闲分区，其大小均为$2^k(k\in int)$
目前应用于 Linux 系统和多处理机系统。
伙伴：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块称为”伙伴”。
分配流程：
当一个长度为 n 的进程申请内存，若$2^{i-1}<n<2^i$，则在空闲分区大小为$2^i$的空闲分区链表中查找
若该长度空闲分区耗尽，则查找大小为$2^{i+1}$的一个空闲分区，将其分为相等的两个分区，一个用于分配，一个加入大小为$2^{i}$的空闲链表中。以此向上类推。
内存释放：考虑将被释放块与其伙伴和并成一个大的空闲块，然后继续合并直至不能合并为止。
分区的存储保护
界限寄存器法
- 上下界寄存器
对于一个地址，将其与上界寄存器和下界寄存器比较，如果越界就报告地址错误 - 基址、限长寄存器
存储保护键法
给每个存储块赋予一个单独保护键，相当于一把锁；进入系统的每个作业也赋予一个保护键，相当于一把钥匙。内存扩充
覆盖与交换可以解决小的内存空间运行大的作业的问题。(现代 OS 主要用交换）
覆盖
把一个程序划分为一系列功能相对独立的程序段，让执行时不要求同时装入内存的程序段组成一组（称为覆盖段），共享主存的同一个区域。
一般要求作业各模块之间有明确的调用结构，程序员向系统指明覆盖结构，由 os 自动完成覆盖。
交换
把暂时不用的进程（等待 I/O）及其数据从主存移至辅存，把指定程序或数据从辅存读入主存，让其在系统中运行。
交换时，需要：1. 保存前一个进程的现场，寄存器 & 堆栈等。2. 创建新进程的运行现场
- 覆盖可以减少单个程序运行所需的空间，交换可以减少多个程序同时占用的内存。
分页式存储管理
把一个逻辑地址连续的程序分散存放到若干不连续的内存区域内。既可充分利用内存空间，也可减少移动带来的开销。
基本概念
页：把每个作业的地址空间分成一些大小相等的片，称之为页面。
存储块/页框：把物理内存的存储空间也分成和页面大小相同的片。
页表：存放在内存中，记录进程的内存分配情况，实现进程运行时的动态重定位。
纯分页系统：不具备页面对换功能的分页存储管理方式。在调度一个作业时，必须把它的所有页一次装到主存的页框内。若页框数不足，则作业必须等待。
地址结构：
- 逻辑地址：
31~页号~12|11~页内偏移~0 - 物理地址：
21~块号~12|11~块内偏移~0
有效内存访问时间：（对一级页表）
$$
EAT=(单次内存访问时间+TLB 查询时间)\times TLB 命中率+(2\times 单次内存访问时间+TLB 查询时间)\times(1-TLB 命中率)
$$
地址转换
逻辑地址：把相对地址分为页号和页内地址两部分。
页表定位：页表始址＋页号 x 页表项长度。
查询页表：读出块号。
物理地址：块号＋块内地址。（块内地址＝页内地址）
多级页表
由于一级页表在划分页面数很多时会导致页表项很多，占用内存多，因此需要多级页表来实现页表分级，从而实现动态调入页表。
二级页表
将页表再进行分页，离散地将各个页表页面存放在不同的物理块中，同时再建立一张外部页表（即页目录）用于记录页表页面对应的物理块号。
正在运行的进程需要把页目录调入内存，然后将当前所需的二级页表调入内存，其余二级页表待需要时再调入。
快表 TLB
页表机制导致内存访问效率下降。不分页时获取数据只需访存 1 次，而一级页表需要访存 2 次，二级页表需要访存 3 次。
快表是一种特殊的高速缓冲存储器（Cache），内容是页表中的一部分或全部内容。CPU 产生逻辑地址的页号，首先在快表中寻找，若命中就找出其对应的物理块；若未命中，再到页表中找其对应的物理块，并将相应的页表项复制到快表。若快表中内容满，则按某种算法淘汰某些页。
其他特性
- 有的 TLB 在每个 TLB 表项中还保存有 ASID（ASID 可用来唯一标识进程），这样 TLB 就可以同时包含多个进程的条目。否则每当进程切换时，TLB 就需要被 flushed，因为不同的进程虚拟地址空间相同，不冲刷可能会导致解析为其他进程的虚拟页。
页目录自映射
哈希页表
反置页表
页共享与保护
共享
各进程把需要共享的数据/程序的相应页指向相同物理块
但如果共享数据与不共享数据在同一块中，不易保密。而事实上也很难只把共享数据与非共享数据隔离，因为”数据共享”是程序处理逻辑层面的需求。
保护
- 地址越界保护
- 在页表中设置保护位（定义操作权限：只读、读写、执行等）
段式内存管理
一个段可定义为一组逻辑信息，每个作业的地址空间是由一些分段构成的。每个段都有自己的段名（一般为段号）且是一段连续的地址空间，其大小不定。
段表：保存在内存中，记录了段与内存位置的对应关系。
地址结构：逻辑地址由段和段内地址组成。
信息共享
多用户同时使用一个程序时，我们可以将代码共享而将数据分别保存，这要求代码是可重入的。
可重入代码：也称纯代码，是指在多次并发调用时能安全运行的代码。(不能使用全局/静态变量，不能修改代码本身，不能调用其他不可重入代码）
优缺点
段式存储管理的作业地址空间是二维的，页式存储管理的作业地址空间是一维的。
因为段号是程序员自己定义的，要想找到某个数据或指令，需要指定段号和位移两个变量，因此是二维的。而页号是系统自动生成的，本身地址是线性连续的，当要访问特定地址时，只需要提供地址即可。系统会自动将地址划分为页号和页内位移，页号对于程序员来说是没有实际意义的，因此是一维的。
段页式存储管理
将用户程序分为若干段，再将每个段分成若干页。
地址结构：段号+段内页号+页内偏移量。因此访问一次数据或指令需访问内存 3 次。
段表与页表
每个进程有一张段表，每个段有一张页表。
段表包含段号、页表始址和页表长度（每个段的页面数不同）。页表包含页号和页框号。
地址变换
- 首先从 PCB 中取出段表始址和段表长度，装入段表寄存器。
- 利用段表始址与段号得到该段表项在段表中的位置，取出该段的页表始址和页表长度
- 利用页表始址和页号得到该页表项在页表中的位置。
- 取出该页的物理块号，与页内地址拼接得到物理地址
（段表长度和页表长度用于发现并产生越界中断）Intel X86
X86 的地址映射机制分为： - 段映射机制：将逻辑地址映射到线性地址
- 页映射机制：将先行地址映射到物理地址
虚拟内存管理
覆盖与交换技术虽部分解决了扩大存储空间的问题，但引入了很多额外的开销。引起这些问题的主要原因是一个作业必须存放在一个连续的内存中。
虚拟内存是计算机系统存储管理的一种技术，它为每个进程提供了一个一致的、连续完整的私有地址空间。采用虚拟存储技术的操作系统只需将当前所需执行的部分页或段读入内存，将内存与外存统一管理，达到扩充内存的目的。局部性原理使得这一技术有了良好的支撑。
基本概念
进程的逻辑空间
一个进程的逻辑空间的建立是通过链接器（Linker），将构成进程所需要的所有程序及运行所需环境，按照某种规则装配链接而形成的一种规范格式（布局），按字节从0开始编址。也称为进程的虚拟地址空间。
交换分区
交换分区是一段连续的磁盘空间（按页划分的），对用户不可见。它的功能是在物理内存不够的情况下，操作系统把内存中暂时不用的数据，存到硬盘的交换空间，留出物理内存让别的程序运行。
在 Linux系统中，交换分区为Swap；在 Windows系统中则以文件的形式存在（pagefile.sys）
虚拟页式存储管理
需要在页表中增加：驻留位（标识该页在内存中还是外存中）、外存地址。
缺页中断
若从页表中查出该页的信息不在主存而在磁盘上时，发生缺页中断。缺页中断流程如下：
- 现场保护：陷入内核态，保存必要的信息（OS及用户进程状态相关的信息）
- 页面定位：查找出发生缺页中断的虚拟页面（进程地址空间中的页面）。这个虚拟页面的信息通常会保存在一个硬件寄存器中，如果没有的话，操作系统必须检索程序计数器，取出这条指令，用软件分析该指令，通过分析找出发生页面中断的虚拟页面。
- 权限检查：检查虚拟地址的有效性及安全保护位。如果发生保护错误，则杀死该进程
- 新页面调入 1 ：查找一个空闲的页框（物理内存中的页面），如果没有空闲页框则需要通过页面置换算法找到一个需要换出的页框
- 旧页面写回：如果找到的页框中的内容被修改了，则需要将修改的内容保存到磁盘上。（注：此时需要将页框置为忙状态，以防页框被其它进程抢占掉）
- 新页面调入 2 ：页框“干净”后，操作系统将保持在磁盘上的页面内容复制到该页框中
- 更新页表：当磁盘中的页面内容全部装入页框后，向CPU发送一个中断。操作系统更新内存中的页表项，将虚拟页面映的页框号更新为写入的页框，并将页框标记为正常状态
- 恢复现场：恢复缺页中断发生前的状态，将 PC 重新指向引起缺页中断的指令，继续执行
页面调度策略
虚拟存储器系统通常定义三种策略来规定如何进行页面调度：调入策略、置页策略和置换策略。
调入策略
调入策略决定什么时候将一个页由外存调入内存之中。
请求调页（demand paging）
只调入发生缺页时所需的页面。这种调入策略实现简单，但容易产生较多的缺页中断，造成对外存I/O次数多，时间开销过大，容易产生抖动现象。
预调页（prepaging）
在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。这种策略提高了调页的I/O效率，减少了I/O次数。但由于这是一种基于局部性原理的预测，若调入的页在以后很少被访问，则造成浪费。这种方式常在程序装入时使用。
置页策略
当线程产生缺页中断时，内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则称为“置页策略”。
选择页框应使CPU内存高速缓存不必要的震荡最小。
置换策略
如果缺页中断发生时物理内存已满，“置换策略”被用于确定哪个虚页面必须从内存中移出，为新的页面腾出空位，即调整驻留集的大小。
固定分配局部置换
为每一进程分配固定的页数的内存空间，在整个运行期间都不再改变。如果进程在运行中出现缺页，则只能从该进程的N个页面中选出一个换出，再调入一页，以保证分配给该进程的内存空间不变。
可变分配全局置换
先为系统中的每一进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时，由系统的空闲物理块队列中取出一物理块分配给该进程。但当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一块调出。该块可能是系统中任意一个进程的页。
可变分配局部置换
为每一进程分配一定数目的内存空间。如果进程在运行的过程中，频繁地发生缺页中断，则系统再为该进程分配若干物理块，直到进程的缺页率降低到适当程度为止。
页面置换算法
当主存空间已被装满而又需调入新页，就需要根据算法将已在主存中的一些页淘汰
- 最优置换 OPT
置换掉未来最久不被使用的页。但它需要页面访问序列的先验知识，是无法实现的。通常用于比较性研究。
- 先进先出 FIFO
置换最久的页。性能差，可能会出现 Belady 异常。
注：Belady 异常：随着分配的页框增多，缺页率反而上升。
- second chance
如果被淘汰的页之前被访问过，则给其第二次机会。每个页面会增加一个访问标志位，用于标识此数据装入内存后是否被再次访问过。
- clock
改进的 second chance。将数据组织成环形队列。
1）如果没有缺页错误，将所访问页的访问位置1，指针不动；
2）如果产生缺页错误：
如果当前页面的访问位是 1 ，首先将当前页面的访问位置0，将指针向前移一个位置；重复这个过程，直到找到访问位为0的页面，然后转下一步。
如果当前页面的访问位是 0 ，替换当前页面，并将其访问位置为1，并将指针向前移动一个位置。
页面清除策略
页面清除策略决定系统何时把被置换页面写回外存。
当正在执行的进程发生缺页中断时，需要阻塞，并等待一个页面的写出和另一个页面的读入，这可能降低处理机的使用效率。
一种有效的页面清除策略是结合页缓冲（Page Buffering）技术。当发生缺页中断时，不必首先写出置换页，而是将被选中的置换页暂时保留在内存的一个缓冲区，在以后某个合适的时候将被置换页批量写出到外存，减少磁盘I/0的次数，提高处理机的效率。
最近最少使用 LRU
是局部性原理的合理近似，性能接近 OPT，但需要记录页面使用的先后关系，实现开销大。
工作集算法
工作集：进程运行正在使用的页面的集合。它会逐渐稳定。
驻留集：每个进程驻留在内存的页面集合。
本算法选择不在工作集中的页面进行替换。
抖动问题
随着驻留内存的进程数目增加，即进程并发程度的提高，处理器利用率先上升，然后下降。
这里下降的原因通常称为虚拟存储器发生“抖动”，每个进程的驻留集不断减小，当驻留集小于工作集后，缺页率急剧上升，频繁调页使得调页开销增大。
因此，OS要选择一个适当的进程数目，以在并发水平和缺页率之间达到一个平衡。
抖动的消除与预防
局部置换策略：如果一个进程出现抖动，它不能从另外的进程那里夺取内存块，从而不会引发其他进程出现抖动，使抖动局限于一个小的范围内
挂起若干进程：挂起一个或几个进程，以便腾出内存空间供抖动进程使用，从而消除抖动现象
引入工作集算法
预留部分页面