操作系统(7) 虚拟内存管理页面置换算法

秒速五厘米 2022-12-31 01:19 241阅读 0赞

# 虚拟内存管理 #

### 文章目录 ###

*  虚拟内存管理
 *   *  一、虚拟内存的基本概念
     *   *  1. 传统存储管理方式的缺点
         *  2. 虚拟内存的定义
         *  3. 虚拟内存的特征
         *  4. 知识回顾
     *  二、请求分页管理方式
     *   *  1. 页表机制
         *  2. 缺页中断机构
         *  3. 知识回顾
     *  三、页面置换算法
     *   *  1. 最佳置换算法(OPT)
         *  2. 先进先出置换算法(FIFO)
         *  3. 最近最久未使用置换算法(LRU)
         *  4. 知识回顾

## 一、虚拟内存的基本概念 ##

### 1. 传统存储管理方式的缺点 ###

连续分配与非连续分配都属于传统存储管理方式

(1) 一次性

作业必须一次性全部装入内存后才能开始运行

(2) 驻留性

一旦作业被装入内存，就会一直驻留在内存中直至作业运行结束；  
但事实上，一个时间段内，只需要作业的一小部分数据即可正常运行

### 2. 虚拟内存的定义 ###

(1) 程序装入内存时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存

(2) 程序运行过程中，所要访问的信息不在内存时，由操作系统负责将所需信息从外存调入内 存，然后继续执行程序

(3) 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存

(4) 使得用户感觉有一个比实际内存大得多的内存，实际上物理内存大小并未改变，只是在逻 辑上进行了扩充，这就是虚拟内存

### 3. 虚拟内存的特征 ###

(1) 多次性

作业被分成多次调入内存

(2) 对换性

作业在运行过程中，可以将作业换入、换出

(3) 虚拟性

从逻辑上扩充了内存的容量，使用户感觉有一个更大的内存

### 4. 知识回顾 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70]

## 二、请求分页管理方式 ##

请求分页管理方式与基本分页管理的主要区别在于增加了请求调页和页面置换两个功能

### 1. 页表机制 ###

(1) 为了实现请求调页，操作系统需要通过状态位知道每个页面是否已经调入内存；如果还没 有调入，也需要知道该页面在外存中存放的位置

(2) 为了实现页面置换，操作系统需要决定将哪个页面换出到外存：有的页面没有被修改过， 就不必浪费时间写回外存；有的页面被修改过，就需要将外存中的旧数据覆盖；因此，操 作系统还需要记录每个页面是否被修改过的信息

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 1]

### 2. 缺页中断机构 ###

(1) 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系 统的缺页中断处理程序处理中断；此时缺页的进程阻塞，放入阻塞队列中，调页完成后再 将其唤醒，放回就绪队列

(2) 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相 应的页表项

(3) 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修 改过，则要将其写回外存；未修改过的页面不用写回外存

### 3. 知识回顾 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 2]

## 三、页面置换算法 ##

使用页面置换算法决定将哪个页面换出，好的页面置换算法应当追求更少的缺页率，即换入、换出 的次数尽可能的少

### 1. 最佳置换算法(OPT) ###

每次选择淘汰的页面是以后永不使用或者最长时间内不再被访问的页面，以保证最低的缺页率

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 3]

操作系统无法预判页面访问顺序，故最佳置换算法无法实现

### 2. 先进先出置换算法(FIFO) ###

每次选择淘汰的页面是最早进入内存的页面

实现方法：每次向内存中调入页面时，将页面添加到一个队列的队尾，需要换出页面时换出队 头的页面即可，队列的最大长度取决于内存块的个数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 4]

注意：FIFO算法会产生Belady异常，即为进程分配的内存块增多时，缺页次数不减反增的现象，  
因此，FIFO算法性能较差

### 3. 最近最久未使用置换算法(LRU) ###

每次选择淘汰的页面是最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的 时间t，当需要淘汰一个页面时，选择现有页面中t值最大的

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 5]

注意：手动做题时，若需要淘汰页面，从当前页面开始逆向检查此时在内存中的页面，淘汰最 后出现的页面即可

### 4. 知识回顾 ###

![在这里插入图片描述][20201227132735208.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70]: /images/20221120/bb12bc7de6f84a8caeb9fe01e1c837bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 1]: /images/20221120/51399b31b40d4cfd9ee19d91b014aa46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201227132707611.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201227132717866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201227132724177.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201227132730300.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80OTM0MzE5MA==,size_16,color_FFFFFF,t_70
[20201227132735208.png]: https://img-blog.csdnimg.cn/20201227132735208.png