ucore—8至10讲:虚拟内存管理

本文主要是介绍ucore—8至10讲:虚拟内存管理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

第八讲:虚拟存储概念
- 8.1 虚拟存储的需求背景
- 8.2 覆盖和交换
- - 覆盖
  - 交换
- 8.3 局部性原理
- 8.4 虚拟存储概念(重要)
- 8.5 虚拟页式存储
- 8.6 缺页异常
第九讲:页面置换算法
- 9.1 页面置换算法的概念
- 9.2 局部页面置换算法(为什么LRU开销大？？)
- - 最优置换算法(OPT)
  - 先进先出算法(FIFO)
  - 最近最久未使用/最近最少使用(LRU)
  - 时钟置换算法(Clock)
  - 最不常用算法(LFU)
  - 局部置换算法间的比较及Belady现象
- 9.3 全局页面置换算法
- - 全局算法概述
  - 工作集算法
  - 缺页率置换算法
  - 抖动和负载控制
第十讲(实验3):虚拟内存管理
- 10.1 实验目标：虚存管理
- 10.2 回顾lab1、lab2
- 10.3 lab3处理流程、关键数据结构与功能
- 10.4 页访问异常
- 10.5 页换入换出机制

第八讲:虚拟存储概念

8.1 虚拟存储的需求背景

什么是虚拟存储
虚拟存储是非连续物理内存分配方式的延续 => 虚拟存储是在非连续物理内存分配的基础上，可以将一部分内容放到外存的做法。
注：这里所说的虚拟存储其实就是swap，而csapp所说的虚拟内存，主要是指虚拟地址空间…注意区分
虚拟存需求：解决物理内存不够用的情况
覆盖：应用程序手动将需要的指令和数据加载到内存中。只加载进程/程序的部分模块，而不是整个进程；新的模块加载进来时可直接覆盖内存中不再需要的模块；
交换：操作系统自动把暂时不能执行的程序保存到外存，换出以整个进程为单位！
虚拟内存：在容量有限的内存中，以页为单位自动装入更多更大的程序。 => 可见虚拟存储几乎就是交换，只是它以页为单位！

8.2 覆盖和交换

覆盖

覆盖技术
覆盖技术示例
假设物理内存小于程序需要的内存空间：
1.程序员先手动划分程序(如图A、B、C…模块)；
2.互不相关的模块分为一组(BC一组、DEF一组)，给每组分配组内最大模块对应的物理内存；
3.先执行A模块，将A调入第一组对应的物理内存区域；

4.依次调用模块B、D，如图示

5.当调用C模块时，它还会调用E，此时将C、E调入内存，直接覆盖内存中的B、C；

6.假设C要调用F，则用F覆盖内存中的E

交换

交换技术
交换技术面临的问题
交换与覆盖的区别
覆盖讨论的是，对于单一进程，整个物理内存仍然不够单一进程使用时的情况；
交换讨论的是，对于多道程序，每个进程只占物理内存的一部分，交换的目的是让正在运行的进程可占用更多的物理内存，防止剩余可用的物理内存不够当前进程使用(假设物理内存至少能存下一个完整的进程)；注意交换的单位是整个进程！

8.3 局部性原理

虚拟内存的目标
局部性原理
时间局部性：…
空间局部性：…

8.4 虚拟存储概念(重要)

虚拟存储的基本概念
一方面，虚拟内存指加载进程的一部分到内存便可执行，而不是加载整个进程，缺页时才会加载缺少的部分；
另一方面，虚拟内存会将部分页换出到磁盘的特定区域，这个区域通常称为交换分区
虚拟存储的基本特征

8.5 虚拟页式存储

虚拟页式存储管理的基本思路
虚拟页式存储中的地址转换
与页式存储的地址转换基本基本一样；只是虚拟页式管理中会发生缺页异常；
如何发现缺页异常？ => 检查页表项中的标志位
虚拟页式存储的页表项
注：图中的标志位似乎没有画正确标志位应该在低12位
虚拟页式存储示例
x86-32页表项结构

1.注意标志位中的WT和CD，这与cache缓存策略相关 =>
比如对于IO操作，不能缓存在cache中，需要通过CD位进行控制!
2.注意标志位D，在一级页表中始终为0!我们只需要关注二级页表项映射的物理页

8.6 缺页异常

缺页异常(缺页中断)的处理流程
虚拟页式存储中的外存管理
对于图中的交换空间有两种做法 =>
1.直接使用一个磁盘分区来存放从物理内存交换出来的数据(linux/unix做法)；
2.使用一个文件来存储；

内存中的内容换出时，并不是全部都放到交换空间：
代码段：直接指向磁盘中的可执行文件(因为它本来就是从磁盘加载到内存的，没有必要换出时放到交换空间，这样反而浪费了空间)
动态加载的共享库程序段：直接指向磁盘中的动态调用的库文件，理由同上
其他段：交换空间 => 因为这些部分的内容可能会程序运行过程中修改、新增等，磁盘上没有与其原本就一一对应的地方，只好放到交换空间!

第九讲:页面置换算法

9.1 页面置换算法的概念

页面置换算法的基本概念

注意部分重要的页被锁定，不能从内存换出的外存 => 通过页表项中的锁定标志位
页面置换算法的评价准则：缺页率！
局部页面置换算法
置换页面的选择范围仅限于当前进程占用的物理页面，进程可占用的物理页面总数固定不变！
局部页面置换算法有：
1.最优算法 => 不能实现
2.先进先出算法(FIFO)
3.最近最久未使用(即最近最少使用，LRU) => 复杂度较高(见lc，hash+双向链表实现)
4.时钟算法(Clock) => LRU的近似
5.最不常用算法 (LFU)=> 也是LRU的近似或者改进
全局页面置换算法
置换页面的选择范围是所有可换出的物理页面，任何一个进程的物理页面都有可能被换出，而不仅仅是当前进程 (这个说法真的对吗?? 11.21)
全局页面置换算法有：
1.工作集算法
2.缺页率算法

9.2 局部页面置换算法(为什么LRU开销大？？)

最优置换算法(OPT)

基本思路
置换在未来最长时间不访问的页面
算法实现
缺页时，计算内存中每个逻辑页面的下一次访问时间
选择未来最长时间不访问的页面
算法特征
缺页最少，是理想情况
但是实际系统中无法实现 => 因为不能预测下一次是什么时候访问该逻辑页面
不过可以作为评价其他页面置换算法性能的依据 => 在模拟器上运行某个页面置换算法并记录页面访问情况，然后第二遍运行时使用最优算法
示例

先进先出算法(FIFO)

概述
示例

最近最久未使用/最近最少使用(LRU)

概述
OPT是向前看，LRU是向后看
LRU是OPT的一种近似，但是比较复杂，系统开销大
个人感觉翻译成“最近最久未使用”更贴切
如何理解LRU性能好，但是系统开销大？
性能好是指：它几乎是对OPT的最好近似(缺页率最接近OPT的)
系统开销大是因为：?？网上的解释难以令人信服，按照hash+双向链表的思路，不是只需要O(1)的时间吗？？系统开销大是因为硬件实现困难吗？？
示例
LRU的实现方法
可以有如下两种方法：
栈实现LRU

时钟置换算法(Clock)

概述
Clock是LRU的简化=>
CLOCK算法也是希望淘汰更久未使用的页面，但是不一定是最久未使用的；
实现
示例
改进的时钟算法
为什么跳过修改过的页效率更高 => 因为如果要替换修改过的页，则需要将该页写回硬盘，更浪费时间；如果只是替换没有修改过的页，直接覆盖即可！

最不常用算法(LFU)

思路
缺页时，置换访问次数最少的页面 => LFU也是LRU的简化
(LRU关注的是时间，LFU关注的是次数)
实现
每个页面设置一个访问计数；
访问页面时，访问计数加1；
缺页时，置换计数最小的页面；
算法特征
1.算法开销大；
2.开始时使用频繁，但是以后几乎不使用的页面很难置换出去 => 改进：计数定期右移
示例

局部置换算法间的比较及Belady现象

Belady现象
FIFO有Belady现象
3个物理页面时:

4个物理页面时：

物理页面数增多，缺页次数缺反而增多 => Belady
LRU算法有Belady现象
没有的原因是有严谨的证明的，此处略去；
LRU、FIFO、Clock算法的区别

9.3 全局页面置换算法

全局算法概述

局部算法没有考虑进程间的访存差异

可见，对于某个物理页个数被限制的进程，如果给他更多的物理页，性能可能得到明显提升 => 如果采用全局的算法，进程的可用物理页面数没有被固定值限制，可能尽可能地分配到更多物理页面
全局置换算法
CPU利用率和并发进程数的关系

工作集算法

工作集概念
工作集是对一个进程而言的
进程运行过程中工作集的变化

全局置换算法的目的就是近似图中这条曲线
常驻集
常驻集：当前时刻，进程实际驻留在内存中的页面的集合
工作集与常驻集的关系
工作集是进程在运行过程中固有的性质；
常驻集取决于系统分配给进程的物理页面数目和页面置换算法；
缺页率与常驻集的关系
=> 通过控制常驻集来影响缺页率
工作集置换算法
1.局部置换算法只有在缺页时才会发生页面置换；
2.而工作集算法在访存时也会置换页面；
3.局部算法复杂的地方在于缺页时的页面置换 <=> 工作集算法复杂的地方在于访存时的页面置换；

缺页率置换算法

缺页率
缺页率置换算法

为什么缺页率很低时竟然需要减少常驻集？
=> 缺页率过低，说明并发数很少，CPU工作效率不高。减少常驻集是为了提高并发进程数，从而提升CPU利用率
缺页率算法的实现

可见，对于缺页率算法，进程的物理页面数是动态调整的(即没有限定进程最多可以有多少个物理页面)；
缺页时才会发生置换，这一点上与局部算法是一致的；而工作集算法在访存时也可能发生置换；