计算机操作系统第六章 虚拟存储器

大家好，欢迎来到IT知识分享网。

文章目录

6.1 概述

6.1.1 虚拟存储器的定义和特征

6.1.2 虚拟存储器的实现方法

6.2 请求分页存储管理方式

6.2.1 内存分配

6.2.2 页面调入策略

6.2.3 页面置换算法

6.2.4 访问内存的有效时间

6.3 抖动与工作集

6.4 请求分段存储管理

6.4.1 硬件支持

6.4.2 分段的共享与保护

6.1 概述

• 虚拟内存管理的主要作用或主要解决的问题：从逻辑上扩大了内存的容量
• 在存储管理这一章中介绍的连续分配存储管理方式、分页存储管理方式、分段存储管理方式统称为传统存储器管理方式，具有如下共同特征
  • 一次性：作业必须一次性全部装入内存后才能运行
  • 驻留性：作业在调入内存后，其中任何部分都不会被换出，直至作业运行结束
• 局部性原理：在一较短时间内，程序执行仅限于某一部分，相应地，访问地存储空间页局限于某一部分
  • 时间局限性：程序某指令（数据）被执行（访问）不久以后可能再次被执行（访问），典型原因：存在大量循环操作
  • 空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内访问的地址空间在一定范围内，典型情况：程序顺序执行
• 虚拟存储器的基本工作情况：
  • 由局部性原理可知，作业没有必要一次性全部装入，只需装入当前要运行的少量页（段）即可；如果程序访问的页（段）在内存中，便可继续运行；否则，发出缺页（段）中断，由OS将之调入内存；如果内存已满，OS将根据置换算法，将内存中暂时不用的页（段）换出内存

6.1.1 虚拟存储器的定义和特征

• 定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统
• 运行速度接近于内存，成本却接近于外存，广泛用于大中小型机器和微型机中
• 特征：多次性、对换性、虚拟性
  • 虚拟性基于多次行、对换性，而对换性、多次性基于离散分配

6.1.2 虚拟存储器的实现方法

• 分页请求系统
  • 在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统，置换单位：页
  • 每次调入、换出的基本单位是固定的，因此成为最常用的一种实现方式
  • 要求
    • 硬件支持
      • 请求分页的页表机制
      • 缺页中段机构
      • 地址变换机构
    • 实现请求分页的软件
• 请求分段系统（原理同分页请求系统）

6.2 请求分页存储管理方式

• 请求页表机制
  • 在分页存储管理的页表结构的基础上加上四个字段：
    • 状态位P：一位，又称位字，用于指示该页是否已调入内存，供访存时参考
    • 访问字段A：用于记录本页在一段时间的访问次数，或记录本页多长时间未被访问，供换出时参考
    • 修改位M：标识该页在调入内存后是否被修改过。由于在外村上保有每一页的副本，故当未发生修改时不需再写会外存，以减少系统开销和启动磁盘的次数，若发生修改，则需重写外存，以保副本始终是最新的，供换出时参考
    • 外存地址：用于指示该页在外存上的地址，供调入时参考

• 缺页中断机制
  • 每当访问的页面不在内存时便产生一次缺页中断
  • 缺页中断同一般中断一样需要经历保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理，以及在中断处理完成后再恢复CPU环境，但又有不同之处：
    • 在指令执行时期产生和处理中断信号。通常是在CPU执行完一条指令后才处理中断
    • 一条指令在执行期间可能多次产生缺页中断
• 地址变换机制
  • 在进行地址变换时，首先检查快表，如果找到，需修改访问字段A，对于写指令还需将修改位置 1
  • 如果未找到，则从内存中的页表中查找，根据状态位判断该页表项是否已调入内存，同时将改页表项写入快表，如果快表已满，则先调出按照某种算法确定的页表项，如果未调入内存，则产生缺页中断，请求OS将之调入内存

6.2.1 内存分配

• 最小物理块数：保证进程正常运行的最小物理块数，当系统分配的物理块数少于这个数，进程将无法运行
  • 由计算机的硬件决定，取决于指令格式、功能和寻址方式
• 内存分配策略
  • 内存分配：固定和可变分配
    • 固定分配：为每个进程分配一组数目一定的物理块，在进程运行期间不再改变
    • 可变分配：当某进程频繁发生缺页中断，可再为该进程分配若干物理块，直到缺页率减少到适当程度为止，反之，某个进程缺页率非常低，可适当减少分配给该进程的物理块数
  • 置换策略：全局置换和局部置换
    • 局部置换：在进程运行出现缺页时，只从分配给该进程的特定n块中换出一页以调入所缺页
    • 全局置换：在进程运行出现缺页时，从系统中空闲的物理块中分配一块给该进程
      • 如果系统中已没有空闲的物理块，则从内存中调出一页，这样会导致被选中的进程拥有的物理块减少，从而缺页率增加
  • 可组合的策略：固定分配局部置换、可变分配全局置换、可变分配局部置换
• 物理块分配法
  • 平均分配、按（进程大小）比例分配
  • 按优先权分配
    • 实际应用中，将可分配的所有物理块分成两部分：一部分按比例分配给进程，一部分按进程优先权分配

6.2.2 页面调入策略

• 何时调入页面
  • 预调页策略
    • 将那些在不久后便会被访问的页面先调入内存
    • 应用场景：工作集
  • 请求调页策略
• 从何处调入
  • 请求分页系统的外存分为两部分，用于存放文件的文件区，和用于存放对换页面的对换区
  • 对换区采用连续分配方式，文件区采用离散分配方式
  • 当系统有足够的对换区，可全部从对换区调入所需页面，为此，在进程运行前将于该进程有关的文件从文件区拷贝到对换区
  • 当系统缺少组足够的对换区时
    • 不会被修改的文件直接从文件区调入，换出时也无需再写回磁盘
    • 会被修改的文件，在换出时将其调到对换区，之后在需要时直接从对换区调入
  • UNIX方式：未运行过的页面从文件区调入，凡是运行过但又被换出的页面直接从对换区调入
    • 由于UNIX系统支持，进程所请求的页面可能被其它进程调入内存，故无需再调入
• 页面调入过程：当请求页不在内存，对用户透明

1. 保存CPU环境，分析中断原因再转入缺页中断处理程序
2. 缺页中断处理程序查找页表获得该页在外存的物理块，如果此时内存能容纳新页，则启动IO磁盘，调入内存并修改页表；如果内存已满，则需先按照某种置换算法将内存中的某页换出，若换出的页未被修改，可直接丢弃，否则写回磁盘，之后再修改页表并将页表项写入快表

• 缺页率：访问页面失败次数 / 访问页面总次数

• 影响因素：页面大小、物理块数目、页面置换算法、程序固有特性（程序局部化程度越高，缺页率越低）

6.2.3 页面置换算法

• 最佳置换算法 Optimal，理想化的算法，实际无法实现，可作为置换算法性能衡量的标准，是Belady于1996年提出的理论
  • 特点：“向后看”，将在后续一段时间内不会访问的的页面换出
• 先进先出置换算法 FIFO，总是将最先进入内存的页面换出，不符合页面使用规律，故性能较差
• 最近最久未使用置换算法 LRU
  • 特点：“向前看”，将在之前一段时间内未被访问的页面换出
  • 硬件支持 ：成本高
    • （移位）寄存器：记录进程在内存中各页的使用情况，每隔一定时间将寄存器向右移动一位
    • 栈：栈顶始终是最新被访问的页面
• 最少使用算法 LFU
  • 同样需要移位寄存器记录进程在内存中各页的使用情况，将最近一段时间内使用次数最少的页面换出
  • LFU 的页面访问图和LRU 的页面访问图一致
  • 和LRU 都不能反映页面的真实的使用情况，因为在寄存器移位的一段时间内，访问一次和访问一千次是完全等效的
• CLOCK 置换算法：LRU的近似算法，也称最近未使用算法、NRU
  • 增设一位访问位
  • 将所有页面链接成一个循环队列，当某页被访问时，将其访问位置1。该算法只检查访问位，是0就换出，是1置0，再按照FIFO算法检查下一个页面，当检查到最后一页访问位都是1，则回到队首重新检查
• 改进的CLOCK 置换算法
  • 在该算法中，置换页面时需考虑页面的置换“代价”，即修改过的页面由于需要写回磁盘故置换代价大
  • 由访问位 A和修改位 M将置换的页面分为4类

1. A=0，M=0：最佳置换页面
2. A=0，M=1
3. A=1，M=0
4. A=0，M=1

• 执行流程 可能需要多轮扫描

1. 寻找第一类页面，不修改访问位
2. 如果第一步失败，寻找第二类页面，同时修改访问位置0
3. 如果第二失败，回到开始处，并将所有的访问位复0，然后重复第一步，如果第一步再失败，则重复第二步，则一定能找到

• 页面缓冲算法 PBA

• 影响页面换进换出的最重要的因素是：页面置换算法
• 每次将修改过的页面写回磁盘都需要启动一次IO磁盘
• 该算法通过在内存中增设一个已修改换出页面的链表，将换出的已修改的页面暂时不写回磁盘，而是挂到链表上，故当某进程需要用到该页面时，可直接从链表上获取，降低将已修改页面写回磁盘的频率，从而大大降低了页面换进换出的频率

6.2.4 访问内存的有效时间

• 内存的访问时间包括：页表访问时间、访问实际物理地址时间、缺页中断处理时间
• 在采用了快表（高速缓冲寄存器）的请求分页管理方式中，还须包括快表修改时间、快表访问时间
  • 当访问页面在内存中，对应的页表项在快表中，访问时间=快表访问时间 + 访问实际物理地址时间
  • 当访问页面在内存中，对应的页表项不在快表中，访问时间=快表访问时间 + 页表访问时间 + 访问实际物理地址时间 + 修改快表时间
  • 当访问页面不在内存中，访问时间=快表访问时间 + 页表访问时间 + 中断处理时间 + 访问实际物理地址时间 + 修改快表时间

6.3 抖动与工作集

• 抖动：刚换出的页面又要调入，频繁更换页面
  • 根本原因：系统中同时运行的进程太多，分配给每个进程的物理块太少，不能满足基本运行要求，导致进程的大部分时间处于换进换出中
• 工作集
  • 1968年，Denning提出工作集，基于局部性原理，程序在一段时间内局限于一小部分页面，在另一段时间又局限于另一些页面，这些页面称为活动页面
  • 工作集：在某段时间内，实际进程所要访问的页面的集合，同样是“向前看”
• 抖动的预防方法
  • 采用局部置换策略，将某个进程的抖动的影响限制在较小的范围，不会对其它进程产生影响
    • 这种方法效果不是很好，因为发生抖动后，该进程将长期处于磁盘IO的等待队列，延长了缺页中断处理时间
  • 引入工作集：当CPU利用率低时，试图从外存调入新作业以改善处理机的利用率
    • 在调入作业时，必须检查该进程在内存中的可驻留的页面是否足够，如果不够，则为该进程增加新的物理块，此时不调入新作业，反之则相反
  • 利用 L=S准则调节缺页率
    • L：缺页的平均间隔时间，S：平均缺页服务时间
  • 选择暂停某些进程（优先级低、不重要又非常大）的活动，调出内存

6.4 请求分段存储管理

6.4.1 硬件支持

• 请求段表机制
  • 除了请求分页机制中的访问字段A、修改位M、存在位P、外存始址，还需增加存取方式字段和增补字段
  • 存取方式字段：由于段时信息的逻辑单位，需要进行保护（读、写、执行保护）
  • 增补位：请求分段存储管理特有的字段，用于记录该段在运行中是否做过动态增长
• 缺段中断机制
  • 同缺页中断机制类似，但由于分段是信息的逻辑单位，故不存在一条指令或一组信息被分在两个段中的情况，同时由于段长不确定，故处理比缺页中断复杂
• 地址变换机制
  • 类似于 请求分页存储管理方式的地址变换机制

6.4.2 分段的共享与保护

• 共享段表：记录所有的共享段，表项包括段号、段长、内存始址、状态位、外存地址以及共享计数等
  • 共享计数count：非共享字段仅为一个进程服务，当该进程不需要该段时，又系统回收。共享段由多个进程共享，只有当所有的进程都不需要该段时才由系统回收，用count记录正在共享该段的进程数
  • 存取控制段：对进程进行读写、执行保护
  • 段号：对于一个共享段在不同的进程中可以有不同的段号
• 共享段的分配与回收
  • 对第一个请求该共享段的进程，由系统为共享段分配一个物理区，同时将该物理区的首址写入进程的外存地址字段中，同时在共享段表中增加一表项，并记录该共享段的相关信息，每当有进程共享该段，count++
  • 回收：count–，若count=0，则取消共享段表对应的段表项并由系统回收，否则只取消共享进程在共享段表中的有关记录
• 分段保护
  • 越界检查、存取控制
  • 环保护机构
    • 内层的环具有较高优先级，OS核心处于0号环内
    • 访问规则，一个程序可以访问和调用驻留在同一环中的数据和访问较低特权环（外环）中的数据和调用较高优先特权（内环）中的数据