内存管理
3.1 概念
3.1.1
内存管理（Memory Management）：操作系统对内存的划分和动态分配。
内存管理的功能：
- 内存空间的分配和回收
- 地址转换：逻辑地址<->物理地址
- 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充
- 存储保护：保证各道作业在各自的存储空间内运行，互不干涉。
1.程序装入和连接
创建进程首先需要将程序和数据装入内存，主要步骤为：
- 编译：由编译程序将用户源代码编译成若干目标模块
- 链接：由连接程序将编译后形成的一组目标模块和所需库函数进行链接，形成装入模块。主要有以下三种方式：
- 静态链接：在程序运行之前将各自模块和所需库函数链接成一个完整的可执行程序
- 装入时动态链接：目标模块在装入内存时边装入边链接
- 运行时动态链接：在程序执行中需要目标模块时才对其进行链接
- 装入：由装入程序将装入模块装入内存运行。主要有以下三种方式：
- 绝对装入：编译时，确定程序常驻在目标的某个位置，则产生绝对地址的目标代码，不必对程序和数据的地址进行修改。只适用于单道环境。
- 静态重定位：多道程序环境下，多个目标模块起始地址都从0开始，则需要重定位（装入时对目标程序和数据的地址进行修改）。此类地址变换是在装入时一次完成的，因此称为静态重定位。特点是装入内存时需要分配要求的所有内存空间，如果没有则不能装入。且装入后不能移动或申请空间。
- 动态重定位（运行时装入）：装入程序将装入模块装入内存后，不立即将相对地址转为绝对地址，而是将地址转换推迟到真正执行程序时，因此所有装入的程序地址均为相对地址。需要一个重定位寄存器的支持。运行期间可以动态申请分配内存，便于程序段共享，可以向用户提供比储存空间大得多的地址空间。
2.逻辑地址空间和物理地址空间
编译后每个目标模块从0开始编址，称为相对地址（逻辑地址）。链接程序将各模块链接为可执行目标程序，按顺序将各个模块的相对地址构成连续的从0号单元开始的逻辑地址空间。
物理地址空间是内存中物理单元的集合，是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址在主存存取。装入程序将逻辑地址转为物理地址的过程称为重定位。
3.内存保护
内存分配前需要保护操作系统不受用户进程影响，同时保护用户进程不受其他用户进程影响。方法有两种：
- CPU中设置一对上、下限寄存器存放用户作业在主存的上下限地址，每当访问地址时判断有无越界
- 采用重定位寄存器（基址寄存器，用来加）和界地址寄存器（限长寄存器，用来比）实现保护：重定位寄存器含物理地址的最小值，界地址寄存器含逻辑地址的最大值。内存管理机构将逻辑地址和界地址寄存器进行比较，若无越界则加上重定位寄存器的值后映射为物理地址。
3.1.2 覆盖与交换
覆盖和交换是多道程序环境下扩充内存的两种方法
1.覆盖
把用户空间分为一个固定区、多个覆盖区，将活跃部分放入固定区，其余按调用关系分段。
首先将即将访问的部分放入覆盖区，其他部分放在外存中。需要调用前才将其他部分调入覆盖区并覆盖覆盖区原有的段。
特点：
- 打破了必须将所有资源装入主存才能运行程序的限制；但同时运行的程序代码量依然不能大于主存。
- 内存中只有覆盖区的段可以更新，固定区常驻
2.交换
基本思想：
- 将处于等待状态（或由于CPU调度被剥夺）的程序冲内存移到外存：换入
- 将准备好竞争CPU资源的程序从辅存移到主存：换入。
中级调度就是一种交换。
特点：
- 需要备份存储，一般是快速磁盘。必须足够大并且可以提供内存映像的直接访问
- 每个进程的执行时间应该比交换时间长，从而有效使用CPU。转移时间最耗时，与交换内存空间成正比。
- 换出时必须保证该进程处于完全空闲状态。
- 交换空间常常独立于文件系统且是一整块磁盘空间。
- 交换一般在内存空间吃紧时启动，系统负荷高时暂停
- 普通交换不常使用，但交换策略的变种很常用。
虚拟内存
现代操作系统都是通过虚拟内存来解决内存不足的，也属于交换技术。覆盖已经成为历史。
3.1.3 连续分配管理方式
1.单一连续分配
此方式下，内存分为系统区和用户区。
- 系统区仅供操作系统使用，在底地址部分
- 用户区是系统区以外的空间
无需进行内存保护，因为内存中永远只有一道程序。
特点：
- 简单、无外部碎片、可覆盖
- 只能用于单用户、单任务，有内部碎片，储存器利用率低
2.固定分区分配
是一种多道程序储存管理方式。将用户内存空间分为若干个固定大小的区域，每个区域装入一道作业。有空闲分区时即可从外存的作业队列选择并装入，如此循环。分区一般在MB级别。
- 分区大小相等：利于一台计算机控制多个相同对象
- 具有灵活性，有多个小分区、适量中分区、少量大分区
特点：
- 适用于多道程序、无内部碎片，但多个进程不能共享一个主存区
- 程序不能放入一个分区时，需要采取覆盖技术；程序远小于一个分区大小时，产生内部碎片造成空间浪费。
动态分区分配
又称可变分区分配，是一种动态划分内存的方式，在装入时才建立分区，因此分区大小和数目可变。
某个占用空间较大的进程结束运行释放内存后，若分配给另一个占用较小的进程，则会出现外部碎片，与固定分区的内部碎片相对。
外部碎片可以使用紧凑（compaction）技术进行处理，这需要动态重定位寄存器支持。
分配策略包括：
- 首次适应 First Fit：按地址次序形成分区链，找到第一个符合条件的空闲分区
- 最佳适应 Best Fit：按容量递增形成分区链，找到第一个符合条件的空闲分区
- 最坏适应 Worst Fit：容量递减。找到第一个（最大的）
- 临近适应 Next Fit：又称循环首次适应算法：从上次查找结束的位置继续查找。
通常首次适应算法最简单且最好和最快。但是每次都是重新扫描，会使得内存的低地址部分出现很多小的空闲分区且每次查找都要经过，增加了开销。
而循环首次适应算法试图解决这个问题，但是会导致内存末尾分配空间分裂为小碎片而缺乏大的分区。
最佳适应取最小的分区，形成最多碎片，小而多。最差适应会使得最大的连续空间被分开，导致没有可用的大内存块。
连续分配-总结
| 方式 | 道数 | 内部碎片 | 外部碎片 | 硬件支持 | 其它特性 |
|---|---|---|---|---|---|
| 单道连续分配 | 1 | 有 | 无 | 界地址寄存器、越界检查 | 覆盖：解决空间不足；交换：提高作业道数 |
| 多道固定连续分配 | N | 有 | 无 | 上下界寄存器+越界检查or基址+长度寄存器+动态地址转换 | |
| 多道可变连续分配 | N | 无 | 有 | 同上 | 空间可用链表、数组管理，可用紧凑解决碎片问题 |
共性：连续存放
3.1.4 非连续分配管理
按是否固定：分页存储、分段存储
分页存储：按是否将所有页面装入：基本分页存储、请求分页存储
1.基本分页存储
基本概念：
- 页面和页面大小
- 页 Page：进程中的快
- 页框 Page Frame：内存中同样单位的划分
- 块 Block：外存中同样单位的划分
- 地址结构
-
页号 P：一般为地址的
31-12位（32位地址中） -
页内偏移量 W：一般为地址的
11-0位 - 地址结构决定了虚拟内存的寻址空间大小。
-
页号 P：一般为地址的
- 页表：记录页面在内存中对应的物理块号，一般存放在内存中。
- 页表由页表项组成，两部分分别为：页号、物理内存中的块号，也就是实现了从页号到实际物理块之间的映射。
基本地址变换机构：
分页类似分区相等的固定分区技术，但是块的大小相对于分区小得多，且进程也是按照块进行划分的。因此，进程只会在为最后一个不完整的块申请空间时才会产生碎片（只会产生内部碎片），且每个进程平均只产生半个块大小的内部碎片（称页内碎片）。
页表存放于内存中，且系统中会包含一个页表寄存器（Page Table Register），来存放页表在内存中的首地址F和页表长度M。页表长度就是页表编号的最大值。
进程未执行时，F和M在PCB中；执行时才放入PTR中。
页面大小L、逻辑地址A、物理地址E的变换过程如下：
- 计算页号
P=A/L以及页内偏移量W=A%L - 比较页号
P和页表长度M，若P>=M发生越界中断； -
页表中页号P对应的页表项地址 = 页表起始地址F + 页号P * 页表中单项长度。取出此页表项，即为物理块号b。 -
物理地址
E = b * L + W，即可访问主存。
为了方便转换，页面大小L一般为2的整数幂，可以将乘法改为移位。
确定页表项大小：
以32位逻辑空间为例，字节为编址单位，一页4KB，地址空间内一共有4GB/4KB=1M页，从而需要log2(1M)=20位的页表项来保证容纳所有页面。转化为字节，则需要ceil(20/8)=3Byte，因此页表项的大小应该有3个字节。
基本分页管理方式的两个问题：
- 每次访问都需要计算，过长拖慢访问速度
- 每个进程都具有页表，过大降低内存利用率。
可以改进为：
具有快表的地址变换机构
快表，又称联想寄存器TLB，是具有并行查找能力的高速缓冲存储器，用来存放当前访问的多个页表项。与之对应，主存中的页表被称为慢表。
具有快表的分页机制中地址的变换过程：
- CPU给出逻辑地址，硬件进行地址转换，将页号送入高速缓存寄存器，并与快表中所有的页号进行比较
- 找到匹配页号
P，则说明要访问的项在快表中，直接取出对应的块号b，和页内偏移量拼接形成物理地址 - 未找到，则计算并访问慢表，并将其内容装入快表，若已满则采用替换机制
也有快慢表同时查找的机制进一步加速，而一般快表的命中率能达到90%。这是由于局部性原理
两级页表：
假设页面大小为4KB，40MB的进程，需页表项(40MB/4KB)*4B=40KB，则4G内存需要总共4M用于存放页表。显然不切实际，可以使用多级页表进行进一步的索引和对应
2.基本分段存储
分页管理方便了计算机，通过硬件实现，对用户完全透明；而分段管理则主要考虑了用户和开发者，用于方便编程、信息保护和共享、动态增长和链接等需要。
分段：段式管理按照用户进程中的自然段划分逻辑空间，如：如果用户进程包括主程序、两个子程序、栈、一段数据，则将这五部分分别分为一段，总共五段，每段从0开始编址，分配一段连续的地址空间（段内要求连续，段间不需要，从而产生二维的地址空间），逻辑地址的组成就是段号
S和段内偏移量W。而这需要被用户显式提供。段表：每个进程中都具备，用于从逻辑空间向内存空间映射。分为三部分：段号、段表项（段长以及本段在主存的起始地址。）段长就是段表项前几位。
-
地址变换：系统中应该设置段表寄存器，存放段表首地址
F和段表长度M。具体交换过程为：- 比较段号
S和段表长度M，若S>=M越界中断 -
段号S对应的段表项地址=段表起始地址F+段号S*单个段表项长度取该段表项的段长C和段内偏移量W比较，若W>=C则越界中断。 - 取出段表项中后几位，即主存中的初始地址
b，则物理地址E就是E=b+W
- 比较段号
-
段的共享和保护
- 段的共享：两个作业段表中相应表项指向被共享的段的同一个物理副本，一个作业正在读取时需要避免其他作业修改共享段中的数据。
- 不能修改的代码称为纯代码或可重入代码，但是这并非临界资源。纯代码和不能修改的数据可以共享，但可修改的代码和数据不能共享。
- 段的保护：存取控制保护、地址越界保护（
S和M，W和C） - 与页式管理不同：段式管理的段长度不固定，不能给出一个整数通过整除和取余取得段号、段内偏移，必须显式给出。
3.段页式管理方式
结合页式管理和段式管理，首先分段，每段再分页。 因此逻辑地址包括三部分：段号S、页号P、页内偏移量W。
一个进程中只能有一个段号，但能有多个分页-多个页号。
3.2 虚拟内存管理
3.2.1 虚拟内存概念
1.传统存储管理方式的特征
- 一次性：一次性装入内存才能运行
- 驻留性：直到运行结束都不会被换出，阻塞后会长期等待。
2.局部性原理
高速缓存技术（如快表和多层缓存）的理论基础。
- 时间局部性：某个指令执行后未来可能再次执行
- 空间局部性：某个被访问的存储单元附近的存储单元也会被访问
3.虚拟存储器
外存中提供的比内存更大的供调入和置换的空间。虚拟储存器的特征有：
- 多次性：无需一次装入
- 对换性：不必常驻
- 虚拟性：逻辑上的扩充
4.实现方式
不应连续分配造成空闲，因此需要建立在离散分配的基础上。
实现方式：
- 请求分页
- 请求分段
- 请求段页式
硬件支持：
- 内存、外存
- 页表或段表
- 中断机制：用户访问部分未调入内存时发生
- 地址变换
3.2.2 请求分页管理方式
建立在基本分页系统基础上，为支持虚拟存储器增加了请求调页功能、页面置换功能。是最常用的方式
1.页表机制
页表项中从两个增加了四个字段
- 页号
- 物理块号
- 状态位P：用于指示是否已经调入内存
- 访问字段A：用于记录本页在一段时间内的访问次数，作为换出换入的参考。
- 修改位M：标识该页在调入内存后是否被修改过
- 外存地址
2.缺页中断机构
要访问的页面不在内存时，产生缺页中断请求将该页调入内存，此时缺页的进程处于阻塞状态。若内存中有空闲块则分配并装入该页并修改相应页表项，否则淘汰该页（若修改过则将修改后的写回外存）
缺页中断作为中断同样需要保护现场等步骤。但是：
- 在指令执行期间产生中断信号而非执行完成后，属于内部中断
- 指令执行期间可以有多次缺页中断
3.地址变换机构
判断越界->访问快表->访问页表->是否在内存，在则修改对应页表项字段并结束
若不在：判断内存是否满，是则换出一页，然后从外存读取并放入和修改相应页表项，再次进行第一步，直到出现在页表。
3.2.3 页面置换算法
最佳置换算法（OPT）：淘汰最长时间内不被访问的页面，保证最低的缺页率，由于无法提前预知长时间不被访问的，因此无法实现。只作为其他算法的评价依据（事后诸葛）。
FIFO置换算法：优先淘汰在内存中驻留最久的页面，算法简单：只需将调入内存的页面按顺序链接为队列即可，但导致经常访问的页面反而容易被调出，且会产生Belady异常（当前所分配物理块数增大但故障数不减反增）
最近最久未使用（LRU，Least Recent used）：利用了访问字段记录上次被访问以来经历的时间，淘汰页面中该字段值最大的。属于“向前看”（相对于OPT的“向后看），但是需要寄存器和栈的支持。此外，不可能出现Belady异常。
-
时钟置换算法（CLOCK）：性能接近OPT但实现困难且开销很大。
- 一般做法：给每一帧关联一个附加位称为使用位，当某一页首次被装入内存时置1，被访问到时也置1。将用于替换的候选页帧看做循环缓冲区并将一个指针与其关联，当某一页被替换时指针指向缓冲区的下一帧。需要替换时，指针扫描缓冲区，找到为0的一帧并替换。期间每遇到一个为1的帧都将其替换为0。全部为1时则循环置0并将第一个替换。
- 由于循环检查各页面，又称为最近未使用（NRU，Not Recently Used）算法。只增加一个使用位时性能接近LRU。
-
若在使用位（
u）的基础上再加一个修改位（m），则得到改进型CLOCK，用这两位标记每帧的状态：- 最近未被访问且未被修改(
!u, !m) - 最近被访问但未被修改（
!u, m） - 最近未被访问但被修改（
u, !m） - 最近被访问且被修改（
u, m）
具体修改步骤：
- Step1：选择
u==0 && m==0用于替换 - Step2：未找到，则找
u==0 && m==1的帧，在此过程中将所有经过的帧的u改为0 - Step3：未找到（代表全部使用过），则回到最初位置，此时所有的
u都是0，重复Step1。
规律：首先找没有改过没有用过的，然后是用过但是没改过的、没用过但改过的、用过和改过的。（
00->01->10->11） - 最近未被访问且未被修改(
3.2.4 页面分配策略
1.驻留集大小
给特定进程分配主存空间大小的依据：
- 分配越小，同时驻留在主存的进程就更多，提高处理器效率
- 进程在主存页数越少，页错误率越高
- 页数过多，由于局部性原理，给特定进程分配更多主存空间对错误率没有明显影响。
三种策略分别为：
- 固定分配局部置换：为每个进程分配一定数目物理块（整个运行期间都不变）。缺页时从该进程在内存中页面选一页换出，
- 可变分配全局置换：最易于实现。为每个进程分配一定数目物理块，操作系统也保持一个空闲物理块队列。缺页时从空闲物理块队列取出一个物理块给该进程，并将所需的页放入。因此比固定分配灵活，但会盲目给进程物理块，导致并发能力下降。
- 可变分配局部置换：给每个进程分配一定数目物理块，缺页时只允许从该进程在内存的页面选一页换出，如果该进程频繁缺页才分配更多物理块。反之，若该进程缺页率低，则减少物理块。
2.调入页面的时机
- 预调页策略：根据局部性原理，将预计将会使用的页面调入内存，但是成功率仅为50%
- 请求调页策略：进程在运行中需要访问的页面不在内存时提出请求，而后调入内存。易于实现且最常用的策略。缺点是每次只调入一页。
- 从何处调入
用于请求分页的外存分为两部分：存放文件的文件区（离散分配）、存放对换页面的对换区（连续分配）。- 对换区空间足够：全部从对换区调入，需要运行前将所有相关文件从文件区复制到对换区。
- 兑换区空间不足：直接从文件区换入。若未修改则不必换出，被修改则需要在换出时调到对换区。
- UNIX方式：进程有关的文件都放在文件区，未运行过的页面都从文件区调入。运行过并被换出的页面在对换区，因此从对换区调入。
3.2.5 抖动
又称颠簸：刚换出的页面马上需要换入主存，刚换入的马上换出。
频繁发生抖动的原因：某个进程频繁访问的页面数目高于可用的物理页帧数目。会因为频繁调入调出降低系统效率。
3.2.6 工作集
工作集（驻留集）就是某段时间间隔内进程访问的页面集合。为了防止抖动需要合理设置工作集大小。
原理：让操作系统跟踪每个进程的工作集并未进程分配大于工作集的物理块。如果还有空闲物理块，则可以再调用一个进程到内存来提高多道程序数。如果工作集之和超过了可用物理块总数，则会暂停一个进程并将其物理块分给其他进程，防止抖动现象。
3.2.7 地址翻译
TLB-页表（TLB不命中）-Cache-主存（Cache不命中）-外存（缺页）
