荐 《操作系统导论》学习笔记（七）：内存虚拟化 (机制及策略)

内存扩容技术

物理内存空间不够用时，需要使用覆盖、交换等内存扩容技术。
覆盖（overlay）：应用程序手动把需要的指令和数据保存在内存中
交换（swapping）：操作系统自动把暂时不能执行的程序保存到外存中

1. 覆盖

覆盖：进程地址空间根据调用结构将进行分段；物理地址空间划分常驻区和若干个覆盖区。常用的必要部分代码和数据放在常驻区，其他的部分放在其他程序模块中，需要时装入内存。不存在调用关系的模块可共享内存并相互覆盖。

不足：增加编程困难增加编程困难，增加了编程的复杂度；增加执行时间，需要从外存装入覆盖模块

进程模块按照调用结构分为三组，A单独为一组，B、C 为一组，D、E、F为一组。物理地址空间按照各组最大值划分，常驻区为 20K、覆盖区$0$为 50K、覆盖区$1$为 40K。进程开始运行，A调入常驻区，B、D分别调入覆盖区$0$和覆盖区$1$；B、D运行完毕，调入C到覆盖区$0$，E到覆盖区$1$；最后调入F到覆盖区$1$输出结果。

2. 交换

交换：整个进程的逻辑地址空间为单位，将暂时不能运行的进程保存到外存，读入外存中需要运行的进程。

3. 内存虚拟化

内存虚拟化是将部分需要执行的内存块装入内存，指令执行产生新的内存块需求时，CPU通知操作系统将暂时不用的内存块调到外存，并将需要的内存块调入内存。从而， 提供给用户的虚拟内存可大于实际的物理内存。

内存虚拟化的实质是交换技术，但交换是以整个进程的逻辑地址空间为单位，而内存虚拟化是以部分内存块为单位，实现的基础是局部性原理。

局部性原理使得装入内存的内存块可以得到充分运行，避免频繁地交换内存块，降低运行效率。局部性原理包括时间局部性和空间局部性：

• 时间局部性(temporal locality)：当一个数据被访问后，它很有可能会在不久的将来被再次访问，比如循环代码中的数据或指令本身。
• 空间局部性(spatial locality)：当程序访问地址为x的数据时，很有可能会紧接着访问x周围的数据，比如遍历数组或指令的顺序执行。

内存虚拟化

内存虚拟化方式根据逻辑地址空间管理方式可分为：虚拟页式存储、虚拟段式存储和虚拟段页式存储，此处仅以虚拟页式存储为例。页式存储管理的硬件支持包括内存、页表、缺页中断及地址转换机构，而虚拟页式存储管理的需要增加 请求调页机制 和 页面置换策略

1. 请求调页机制

请求调页机制需要参考页表控制位并使用缺页中断请求页面。

页表控制位：

页式存储管理只使用页表项的虚页号、物理帧号以及存在位( present，P )，页面的存在位为0时，返回缺页错误，进程运行结束；虚拟页式存储管理使用更多的控制位，检查页面状况，指导操作系统调入页面，从而进程能够继续执行。

• 访问位（accessed，A）：记录本页一段时间内的访问次数，或记录本页多久未被访问，供大多数置换算法换出页面时参考
• 修改位（dirty，D）：表示页面在调入内存后是否被修改过，供时钟置换算法及调出页面时是否要回写到外存

缺页中断：

• 检查页表项的存在位，存在位为0则向操作系统发出缺页异常，操作系统在外存中查找对应页面
• 内存没有空闲物理页帧时，操作系统根据页面置换算法选择被替换的物理页帧和对应的虚页面，修改位为1则回写到外存，存在位修改位0，产生空闲物理页帧
• 内存有空闲物理页帧时，操作系统将页面装入内存，并页表项填入页帧号，存在位修改为1

2. 局部页面置换

局部页面置换：置换页面的选择范围仅限于当前进程占用的物理页面内，分配的物理页面数量可以固定也可以变化。

• 最佳置换算法(OPT)
  最佳置换算法(OPT)置换在未来最长时间不访问的页面，从而保证获得理想状态的最低缺页率。因为无法预知进程页面的访问情况，所以该算法无法实现，但可用于评价其他算法的性能。
• 先进先出算法(FIFO)
  先进先出算法(FIFO)置换驻留内存时间最长的页面。维护一个记录内存所有页面的链表，链表元素按驻留内存时间降序排列，缺页时置换链首页面，访问页面时加入链尾。
• 最近最久未使用算法(LRU)
  最近最久未使用算法(LRU)置换最长时间未被访问的页面。维护活动页面栈，缺页时置换栈底页面，访问页面时将页号压入栈底，并将栈内相同的页号抽出。

例题：
在一个请求分页存储管理系统中，一个作业的页面走向为 4,3,2,1,4,3,5,4,3,2,1,5，当分配给进程的物理块是3时，试计算分别采用OPT、FIFO和LRU的缺页率（假设开始执行时主存中没有页面），并比较结果。

OPT：

访问	4	3	2	1	4	3	5	4	3	2	1	5
帧号1	4	4	4	4	4	4	4	4	4	2	2	2
帧号2		3	3	3	3	3	3	3	3	3	1	1
帧号3			2	1	1	1	5	5	5	5	5	5
缺页	√	√	√	√			√			√	√

缺页率：7/12

FIFO ：

访问	4	3	2	1	4	3	5	4	3	2	1	5
帧号1	4	4	4	1	1	1	5	5	5	5	5	5
帧号2		3	3	3	4	4	4	4	4	2	2	2
帧号3			2	2	2	3	3	3	3	3	1	1
缺页	√	√	√	√	√	√	√			√	√

缺页率：9/12

LRU：

访问	4	3	2	1	4	3	5	4	3	2	1	5
帧号1	4	4	4	1	1	1	5	5	5	2	2	2
帧号2		3	3	3	4	4	4	4	4	4	1	1
帧号3			2	2	2	3	3	3	3	3	3	5
缺页	√	√	√	√	√	√	√			√	√	√

缺页率：10/12

Bleady现象
Bleady现象是指采用FIFO算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象。

访问	4	3	2	1	4	3	5	4	3	2	1	5
帧号1	4	4	4	4	4	4	5	5	5	5	1	1
帧号2		3	3	3	3	3	3	4	4	4	4	5
帧号3			2	2	2	2	2	2	3	3	3	3
帧号4			1	1	1	1	1	1	1	2	2	2
缺页	√	√	√	√			√	√	√	√	√	√

缺页率：10/12

• 时钟算法(CLOCK)
  LRU算法性能接近OPT，但实现困难且开销大，而时钟算法根据环形链表检索及置换页面，利用页表项的访问位和修改位大致统计页面访问情况，减小开销且性能接近LRU。
  
  简单CLOCK算法只利用页表项的访问位：页面装入内存时，访问位初始化为0；访问页面（读/写)时，访问位置1；缺页时从指针当前位置检查环形链表，访问位为0则置换该页，访问位为1则修改为0并继续寻找。

改进型CLOCK算法利用页表项的访问位和修改位：

• 页面装入内存时，访问位和修改位初始化为0
• 访问页面时，访问位置1，修改页面时，修改位置1
• 缺页时从指针当前位置检查环形链表，访问位0和修改位0则置换页，否则访问位0和修改位1置换页面
• 查找置换页面失败，第一圈置指针所指页面访问位为0，同时查找置换页面；再次查找失败，第二圈置指针所指页面修改位为0，同时查找置换页面

3. 全局页面置换

全局页面置换：置换页面的选择范围是所有可换出的物理页面，分配每个进程的物理页面数量是可变化的。

• “抖动” 现象
  局部置换算法只适用于单个进程，而系统只运行单个进程时，CPU利用率很低。提高并发进程数，可提高CPU利用率；但当进程对页面的需求超过物理页面数时，缺页率上升，系统需要频繁地置换页面，从而降低系统性能，该现象称为 抖动。
  
  消除 “抖动” 现象可从进场的页面需求和物理页面数量两个角度考虑。从下图可见，随着物理页面数量的增加，缺页率降低，意味着“抖动” 现象减轻。
  
  但系统不可能无限度地增加物理页面数量，且缺页率降低速率是下降的，所以需要平衡每个进场的页面需求和进场获得的物理页面数量，即为进场提供与活跃页面相等的物理页面数。

• 工作集
  页面访问具有时间局部性，所以可以根据过去一段时间的页面访问情况推测未来需要访问的页面。以当前时间 $t$ 为界，向前回溯一个定长的页面访问时间窗口 $\Delta$，该段时间访问逻辑页面的集合称为 工作集，表示为二元函数 $W(t，\Delta)$ 。

工作集大小和内容每时每刻在变动，但工作集的大小经过短暂快速扩张和收缩后会趋向于稳定。

• 工作集算法
  工作集算法置换不在工作集的页面。维护窗口 $\Delta$ 内的访存页面链表，访存时，换出不在工作集的页面并更新访存链表；缺页时，换入页面并更新访存链表。
  
  

本文地址：https://blog.csdn.net/K_Xin/article/details/107095217