操作系统——内存管理(2)

本系列文章为408考研操作系统知识点整理仅涉及到一些重要的考研知识点并不是完全系统全面的知识，参考书目和视频资料：汤小丹 计算机操作系统（第四版），操作系统考研复习指导，B站王道考研操作系统视频课。

3.2.1 虚拟内存的基本概念

前面我们讨论过的内存管理策略都有以下特点：

一次性：作业必须一次性全部装入内存后，才能开始运行，这就导致两种情况
当作业很大而不能全部装入内存时，将导致作业无法运行
当大量作业要求运行时，由于内存不足以容纳所有作业，所以只能使少数作业先运行，无疑降低了多道程序的并发度
驻留性：作业被装入内存后，就会一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。因此运行中的进程会因为等待IO而被阻塞，长期处于等待状态

(1)定义
虚拟内存：基于局部性原理，可以这样控制程序
程序装入时：将程序中很快会用到的部分先装入内存，暂时用不到的留在外存
程序执行时：如果所访问的信息不在内存，则由操作系统负责将所需要的信息从外存调入内存
发现内存不够时：由操作系统负责将内存中暂时用不到的信息换出外存
因此，在虚拟内存的世界中，用户会感觉内存要比实际显示的大得多，但这只是在逻辑上进行了扩充
注意：
虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的
虚拟内存的实际容量是“内存和外存容量之和”与“CPU寻址范围'”中较小的一个

虚拟内存特征：有以下三个主要特征
多次性：作业运行时无需一次全部装入内存，而是允许分批次调入内存
对换性：作业运行时无需一直常驻内存，而是允许在运行时进行换入和换出
虚拟性：从逻辑上扩充了内存的容量

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。主要有以下三种
请求分页存储管理
请求分段存储管理
请求段页式存储管理
与传统的非连续存储管理方式相比，区别在于
所访问信息不在内存时，由操作系统负责将信息从外存调入内存——请求调页功能
如果内存空间不够，由操作系统负责将内存中暂时用不到的信息换出外存——页面置换功能

3.2.2 请求分页管理方式

页表机制

请求分页系统的页表机制不同于基本分页系统，需要增加如下字段

状态位：操作系统需要知道每个页面是否已经调入内存，供程序访问时参考
访问字段：可以记录最近该页面被访问的频次，供页面置换算法选择页面时进行参考
修改位段：标识该页面调入后是否被修改过
外存地址：页面在外存的存放位置，通常是物理块号，供调入该页时参考

缺页中断机制

在请求分页系统中，每当所要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺页调入内存。此时，缺页的进程将会被阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
内存若有空闲块：分配一个块，将要调入的页装入该块，并修改页表中的页表项
内存若没有空闲块：由页面置换算法淘汰一个页面。而目如果被淘汰的页面在内存期间被修改过，还要写回页面

需要注意以下两点：
缺页中断属于内中断
一条指令在执行期间，可能会发生多次缺页中断

地址变换机构

对于请求分页管理方式，需要额外进行以下几点
请求调页，查找到页表项时进行判断
页面置换，调入时没有空闲内存块
修改请求页表中的新增表项
如果某个页面被换出外存，则快表也必须也要进行修改

3.2.3 页面分配策略

驻留集

驻留集：对于分页式虚拟内存，在进程准备执行时，操作系统必须决定读取多少页，也即决定给特定的进程分配多少页框。所以给一个进程分配物理页框的集合就是这个进程的驻留集。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。驻留集太大和太小都会对进程或系统产生一定影响，所以要选择一个合适的驻留集大小
若驻留集太小：导致缺页频繁，系统需要花费大量时间来处理缺页，实际用于推进进程的时间很少
若驻留集太大：导致多道程序并发度下降，资源利用率降低
根据驻留集大小是否可变，可以有如下两种分配方式
固定分配：操作系统为每个进程分配一组固定数目的物理块，进程运行期间不再改变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可以根据情况做适当的增加或者减少

根据置换时置换的范围不同，可以有两种置换方式
局部置换：发生缺页时只能选进程自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给进程；也可以将别的进程持有的物理块置换到外存，然后再分配给缺页进程

固定分配局部置换：系统为每个进程分配一定数量的内存块，在整个运行期间都不改变；若进程在运行期间发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面
缺点：很难在刚开始就确定应该为每个进程分配多少个物理块才算合理
可变分配全局置换：刚开始会为每个进程分配一定数量的内存块。操作系统会保持一个空闲物理块队列，当进程发生缺页时，从空闲物理块中取出一块分配该进程；若己经没有空闲物理块了，则可以选择一个未锁定（被锁定的可能是很重要的页面）的页面换出外存，再将该物理块分配给缺页的进程
使用该策略，只要进程发生缺页，都将会获得新的物理块；仅当空闲物理块用完时，系统才会选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程的页，因此被选中的进程拥有的物理块会减少，缺页率会增加
可变分配局部置换：列开始会为每个进程分配一定数量的物理块。当进程发生缺页时，只允许从该进程自己的物理块中选出一个换出外存。如果进程在运行中频繁缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势变得适当且平稳；反之如果缺页率很低，则可以适当减少分配给该进程的物理块
使用该策略，会根据缺页率来动态增加或减少进程的物理块

注意：没有固定分配全局置换这种分配策略，因为全局置换意味着一个进程拥有的物理块数必定会改变，因此不可能采用固定分配

调入页面的时机

主要有以下两种调页策略，实际场景中，两种策略会结合使用
预调页策略：根据局部性原理，一次调入若干相邻的页面可能要比一次只调入一个页面更加高效，但如果调入的一批页面中大多数都没被访问，效率就会很低。因此，需要采用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存，但目前预测成功率平均不超过50%
这种策略主要用于进程的首次调入，也就是运行前调入
请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。该策略下，调入的页面一定会被访问到，但是由于一次只能调入一页，所以I/O开销较大。（运行期间调入）

从何处调入页面

具有对换功能的操作系统中，通常会把磁盘空间分为文件区和对换区两部分：其中文件区主要用于存放文件，追求存储空间利用率；对换区空间仅占一小部分。被换出的进程数据就存放在对换区。由于对换的速度直接影响系统的整体速度，因此对换区空间的管理主要追求换入换出速度，所以对换区采用连续分配方式。总之，对换区的I/O速度要远快于文件区

由于对换区磁盘I/O速度要快于文件区，因此就有如下三种情况
若系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，将相关数据从文件区复制到对换区，之后把需要的页面从对换区调入内存。

若系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下一次需要时再从文件区调入即可。对于可能被修改的部分，换出时需要写回对换区，下次需要时再从对换区调入

UNIX方式：运行之前进程有关的数据全部放在文件区，所以未使用过的页面，都可以从文件区调入；被使用过页面的换出时，则写回对换区，下次需要直接从对换区调入

抖动

抖动：刚换出的页面马上又要换入内存、刚换入的页面马上又要换出内存的频繁的页面调度行为。产生抖动的根本原因是进程频繁访问的页面数目高于可用的物理块数
为了研究应该为每个进程分配多少个物理块，Denning提出了工作集的概念

工作集

工作集：指在某段时间间隔里，进程实际访问页面的集合

工作集大小可能小于窗口尺寸。实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。比如窗口尺寸为5，经过一段时间监测后发现某进程的工作集最大为3，那么说明该进程具有良好的局部性，所以可以给该进程分配三个以上的内存块即可满足运行时的需要。
一般来说，驻留集大小不能小于工作集大小，否则将导致频繁换页

3.2.4 页面置换算法

最佳置换算法(OPT)

最佳置换算法(OPT,Optima):每次淘汰的页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证最低的缺页率

由于操作系统无法提前预知页面的问序列，所以OPT算法是无法实现的，属于一种理想化算法

先进先出置换算法(FIFO):每次淘汰的页面是最早进入内存的页面。具体来说，可以把调入内存的页面根据调入先后顺序排成一个队列，需要换出页面时选择队头即可，队列的最大长度取决于系统为进程分配了多少个内存块

随着为进程分配的物理块数增大时，缺页次数不减反增，这种现象称之为Belady异常（只有FIFO算法会产生）
另外，FIFO算法实现虽然简单，但是该算法与进程实际运行时的规律不相适应，因为先进入的页面也有可能是需要经常访问的，所以性能差

近期最少用置换算法(LRU)

近期最少用置换算法(LRU,least recently used):每次淘汰的页面是最近最久未使用的页面。具体来说，在每个页面对应的页表项中用访问字段记录该页面自上次被访问以来所经历的时间t,需要淘汰页面时，选择值最大的那个页面。

可以看，LRU算法性能非常好，但是实现困难，开销也比较大，而且需要专门的硬件支持

简单时钟置换算法(NRU）

简单时钟置换算法：为每个页面设置一个访问位，再将内存中的页面通过链接指针链接成一个循环队列。当某页被访问时，访问位置设置为1。当需要淘汰一个页面时，只需要检查页的访问位：
如果是0，表示最近没有访问过：选择该页换出
如果是1，表示最近访问过：将其置为0，暂不换出，继续下一个页面

简单总结规则：转圈找0，遇1变0，遇0换出。

改进型时钟置换算法

改进型时钟置换算法：为每个页面再设置一个修改位，淘汰页面时优先淘汰没有被修改过的页面
如果修改位为0：表示页面没有被修改过
如果修改位为1：表示页面被修改过

同时为了方便讨论，可以使用（访问位，修改位）这样二元组的形式表示各页面的状态
(0,0)：一个页面既没有被访问过也没有被修改过（最佳置换页面）
(0,1)：一个页面没有被访问但是被修改过
(1,0)：一个页面被访问过但没有被修改过
(1,1)：一个页面被访问过且被修改过

具体规则：将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描到第一个(0,0)的页面用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮失败，则重新扫描，查找第一个(0,1)的页面用于替换。本轮将所有扫描过的页面访问位设为0
第三轮：若第二轮失败，则重新扫描，查找第一个(0,0)的页面用于替换。本轮扫描不修改任何标志位
第四轮：若第三轮失败，则重新扫描，查找第一个(0,1)的页面用于替换
由于第二轮已将所有页面的访问位设置为了0，所以经过第三轮、第四轮扫描一定有一个页面被选中，所以改进型CLOCK算法选择一个淘汰页面至多进行四轮扫描

分段分页管理方式比较