6.1虛拟存储器的基本概念 第六章虛拟存储器 虚拟存储器的引入 虚拟存储器的概念 作系统 程序的分段执行 请求页式管理 局部性原理 在执行中的程序,某一段时间内 页面置换算法 总是集中地访问程序中的某一 请求段式管理 时间局限性 空间局限性 虚存容量 虚拟存储器的定义 在多道程序环境下,系统可分为每个用户 利用请求调入和交换技术,为用户提供 建一个虚存 一个存储容量比实际内存容量大得多的存 储器,称之为虚拟存储器 一其容量可为内存与外存的容量之和,成由 计算机地址结构和寻址方式确定 虚存的形式 基础条件 单段式虚存:一个连续线性地址空间。 有相当容量的外存。 多段式虚存:把地址空间分成若干段 每一段是一个连续的线性空间。 有一定容量的内存。 地址变换机构。 >虚拟存储器的实现方式 请求分页系统 虚拟存储器的特征 在分风系统的基础上,增加了请求调和贝面量 高散性 换功能所形成的页式虚拟存储系统 多次性 请求分页的页夜机制 对换性 →地址变换机构 虚拟性 请求分段系统 请求分段的页表机制 一缺段中断机构
1 第六章 虚拟存储器 虚拟存储器的概念 请求页式管理 页面置换算法 请求段式管理 操 作 系 统 | 虚 拟 存 储 器 2 CUIT 徐虹 6．1 虚拟存储器的基本概念 ¾虚拟存储器的引入 ¾程序的分段执行 ¾局部性原理 ¾在执行中的程序，某一段时间内， CPU 总是集中地访问程序中的某一 部分。 ¾时间局限性 ¾空间局限性 操 作 系 统 | 虚 拟 存 储 器 3 CUIT 徐虹 ¾虚拟存储器的定义 ¾利用请求调入和交换技术，为用户提供 一个存储容量比实际内存容量大得多的存 储器，称之为虚拟存储器。 ¾虚存的形式 ¾单段式虚存：一个连续线性地址空间。 ¾多段式虚存：把地址空间分成若干段， 每一段是一个连续的线性空间。 操 作 系 统 | 虚 拟 存 储 器 4 CUIT 徐虹 ¾虚存容量 ¾在多道程序环境下，系统可分为每个用户 建一个虚存。 ¾其容量可为内存与外存的容量之和，或由 计算机地址结构和寻址方式确定。 ¾基础条件 ¾有相当容量的外存。 ¾要有一定容量的内存。 ¾地址变换机构。 操 作 系 统 | 虚 拟 存 储 器 5 CUIT 徐虹 ¾虚拟存储器的实现方式 ¾请求分页系统 ¾在分页系统的基础上，增加了请求调页和页面置 换功能所形成的页式虚拟存储系统。 ¾请求分页的页表机制 ¾缺页中断机构 ¾地址变换机构 ¾请求分段系统 ¾请求分段的页表机制 ¾缺段中断机构 ¾地址变换机构 操 作 系 统 | 虚 拟 存 储 器 6 CUIT 徐虹 ¾虚拟存储器的特征 ¾离散性 ¾多次性 ¾对换性 ¾虚拟性
6.2请求分页存储管理 实现原理 >请求页式管理和预调入页式管理 基本问题 要访问的虚页在不在内存 请求页式管理 扩充贝表功能:增加中断位和外存地址 当执行的指令取访问的据不在内存 作系统 页中断,系统将外存中相应的 虚页不在内存时的处理 页面调入内存 建坤姓变参,糗页龄州*斯址它 预调入页式管理 存调入内存,然后继执行 算,估计出这些页中的指令和据的执 和调出内存 页面的调入调出 调入:有无空白页,是否淘汰一页,修改页 >请求分页中的硬件支持 调出(淘汰) 页表机制 夜的构成:页号、物理块号、状态位P、访问 系>处理过程 字段A、修改位M和外存地址 传输进程某页时,阻嘉,系统调度另 缺页中断机构 处理过程:保护CP现场、分析中斷原因和 >外页面表 入中斷处理程序 除在5 地址变换机构 页面表建立页表 He nfa Transation lakeside la
2 操 作 系 统 | 虚 拟 存 储 器 7 CUIT 徐虹 6．2 请求分页存储管理 ¾请求页式管理和预调入页式管理 ¾请求页式管理 ¾当需要执行的指令或访问的数据不在内存 时，产生缺页中断，系统将外存中相应的 页面调入内存。 ¾预调入页式管理 ¾系统对那些在外存中的页进行调入顺序计 算，估计出这些页中的指令和数据的执行 和被访问的顺序，并按此顺序将它们调入 和调出内存。 操 作 系 统 | 虚 拟 存 储 器 8 CUIT 徐虹 ¾实现原理 ¾基本问题 ¾要访问的虚页在不在内存 ¾扩充页表功能：增加中断位I 和外存地址 ¾虚页不在内存时的处理 ¾由动态地址变换机构产生一缺页中断。OS 进行中断处理后，根据该页的外存地址把它 从外存调入内存，然后继续执行。 操 作 系 统 | 虚 拟 存 储 器 9 CUIT 徐虹 ¾页面的调入调出 ¾调入：有无空白页，是否淘汰一页，修改页 表。 ¾调出（淘汰） ¾处理过程 ¾当传输进程某页时，阻塞，系统调度另一进 程。 ¾外页面表 ¾对于进入系统的每个作业，除在外存建立文 件目录外，还需建立外页面表：页号，物理 块号（磁盘上的位置），保护信息。调度一 个作业时，在内存中根据外页面表建立页表。 操 作 系 统 | 虚 拟 存 储 器 10 CUIT 徐虹 ¾请求分页中的硬件支持 ¾页表机制 ¾页表的构成：页号、物理块号、状态位P、访问 字段A、修改位M和外存地址。 ¾缺页中断机构 ¾处理过程：保护CPU现场、分析中断原因和转 入中断处理程序。 ¾特点 ¾地址变换机构 操 作 系 统 | 虚 拟 存 储 器 11 CUIT 徐虹 ¾联 想 存 储 器 操 作 系 统 | 虚 拟 存 储 器 12 CUIT 徐虹
页面分配 最小物理块数:能保证一个进程 分配算法 正常运行所需的最小物理块数 平均分配算法 页面分配和置换策略 分配策略:固定和可变 作系统 按比例分配算法 考虑优先权的分配算法 将内存分为两部分:一部分按比例分配 换策略:全局和局部 一部分根据优先级增加分配的物理 固定分配局部置换 可变分配全局量换 可变分配局部量换 性能评价 对换区的管理 优点 对换空间充足:全部从对换区换入。 有效地解决了碎片闻题 对换空间不够:分为修改和不修改两 虚存的实现 种方法。 >缺点 UNIX方式:未运行过的,从文件区调 一要求相应的硬件支持 入;曾修改过的,从交换区调入 增加系统开销 请求调页的算法选择不当,可能产生抖 动现象。 没有彻底消除碎片闻题。 6.3 置换算法 先进先出算法(FIFO) 法的效能是和作业运行过程 原理 动态特征)紧密相关的,而这个变化规 选择在内存驻留时间最长的一页将其淘 对同一程序,对不 实现方法 >随机淘汰算法( Random 按页调入内存顺序建立一队列表Q(0 Glongram) Q(m-1)和一菅换指针,指针指向 >最佳置换算法OPI( Optimal 最早调入内存的一页 Replacement Algorithm) 一把这个队列裘建立在存储分块表中 趁准漆时同两芣伤開的买面或
3 操 作 系 统 | 虚 拟 存 储 器 13 CUIT 徐虹 ¾页面分配 ¾最小物理块数：能保证一个进程 正常运行所需的最小物理块数。 ¾页面分配和置换策略 ¾分配策略：固定和可变 ¾置换策略：全局和局部 ¾固定分配局部置换 ¾可变分配全局置换 ¾可变分配局部置换 操 作 系 统 | 虚 拟 存 储 器 14 CUIT 徐虹 ¾分配算法 ¾平均分配算法 ¾按比例分配算法 ¾考虑优先权的分配算法 ¾将内存分为两部分：一部分按比例分配； 另一部分根据优先级增加分配的物理块。 操 作 系 统 | 虚 拟 存 储 器 15 CUIT 徐虹 ¾对换区的管理 ¾对换空间充足：全部从对换区换入。 ¾对换空间不够：分为修改和不修改两 种方法。 ¾UNIX方式：未运行过的，从文件区调 入；曾修改过的，从交换区调入。 操 作 系 统 | 虚 拟 存 储 器 16 CUIT 徐虹 ¾性能评价 ¾优点 ¾有效地解决了碎片问题 ¾虚存的实现 ¾缺点 ¾要求相应的硬件支持 ¾增加系统开销 ¾请求调页的算法选择不当，可能产生抖 动现象。 ¾没有彻底消除碎片问题。 操 作 系 统 | 虚 拟 存 储 器 17 CUIT 徐虹 6．3 置换算法 ¾一个置换算法的效能是和作业运行过程 中访问地址空间的变化规律（即程序的 动态特征）紧密相关的，而这个变化规 律是难以预测的。即对同一程序，对不 同的程序，其规律都不同。 ¾随机淘汰算法（Random Glongram） ¾最佳置换算法OPT（Optimal Replacement Algorithm） ¾被淘汰的页面是永远不使用的页面，或 是在最长时间内不再被访问的页面。 操 作 系 统 | 虚 拟 存 储 器 18 CUIT 徐虹 ¾先进先出算法（FIFO ） ¾原理 ¾选择在内存驻留时间最长的一页将其淘 汰。 ¾实现方法 ¾按页调入内存顺序建立一队列表Q （0） ---Q（m—1）和一替换指针，指针指向 最早调入内存的一页。 ¾把这个队列表建立在存储分块表中
算法效率 最近最久未用页面置换算法(Leat 这种算法只有在按线性顺序访问地址空 recently used 间时才理想,否则效率不高 m>原理:当需要置换一页时,选择在最近段 Belady现象 时间内最久未用的页予以淘汰 在使用FIFO算法时,未给进程或作业 实现 分配足够的页面数时,有时会出现分配 的页面数增多,缺页次数反而增加 通过周期性地对“引用位进 并利用它来记录一个页面自上次被访间 原因在于它根本没考虑程序执行的动态 以来所经历的时间T;淘汰时, 为 最大的页 >硬件支持 寄存器法 为每个页面配一个移位寄存器,当访 m图国甲围甲圉围軍图 问到某物理块时,将相应寄存器的RN 位成1,每隔一段时间将寄存器右移 一位。海汰寄存器值最小的页面 利用一个特殊的栈来保存当前使用的各 个页面的页面号,每当进程访闻某页面 m国图甲甲申图甲图甲军 时,便将该页面的页面号从栈中移出 将它压入栈顶。则栈底为最近最久为使 用页面的页面号 a灬wx鬥圉團圉雷'熠圉 >Clok置换算法 最近没使用算法NRU 淘汰最近一段时间T内未被访问的一页 设置引用位 「例:页面13>4>6>9 报引用位110 优点:简单,实现容易 缺点:时间周期T选择不易确定 Example of Clock Policy Operation
4 操 作 系 统 | 虚 拟 存 储 器 19 CUIT 徐虹 ¾算法效率 ¾这种算法只有在按线性顺序访问地址空 间时才理想，否则效率不高。 ¾Belady 现象 ¾在使用FIFO 算法时，未给进程或作业 分配足够的页面数时，有时会出现分配 的页面数增多，缺页次数反而增加。 ¾原因在于它根本没考虑程序执行的动态 特征。 操 作 系 统 | 虚 拟 存 储 器 20 CUIT 徐虹 ¾最近最久未用页面置换算法（Least recently used） ¾原理：当需要置换一页时，选择在最近一段 时间内最久未用的页予以淘汰 ¾实现 通过周期性地对“引用位”进行检查， 并利用它来记录一个页面自上次被访问 以来所经历的时间T；淘汰时，选择T 为 最大的页。 操 作 系 统 | 虚 拟 存 储 器 21 CUIT 徐虹 ¾硬件支持 ¾寄存器法 ¾为每个页面配置一个移位寄存器，当访 问到某物理块时，将相应寄存器的RN-1 位置成1。每隔一段时间将寄存器右移 一位。淘汰寄存器值最小的页面。 ¾栈 ¾利用一个特殊的栈来保存当前使用的各 个页面的页面号，每当进程访问某页面 时，便将该页面的页面号从栈中移出， 将它压入栈顶。则栈底为最近最久为使 用页面的页面号。 操 作 系 统 | 虚 拟 存 储 器 22 CUIT 徐虹 操 作 系 统 | 虚 拟 存 储 器 23 CUIT 徐虹 ¾Clock置换算法 ¾最近没使用算法NRU 淘汰最近一段时间T内未被访问的一页。 设置引用位。 例： 页面 1——>3——>4——>6——>9 引用位 1 1 0 0 1 优点：简单，实现容易 缺点：时间周期T 选择不易确定 操 作 系 统 | 虚 拟 存 储 器 24 CUIT 徐虹
NRU改进算法 A:访问位M:修改位 (A=0,M=0)最近既未被访问,又未被修 「"类(A,M=1)最近既未被访间,但已被修 漠类(A=,MHD)最近被访同,未被修改 类(A=1,M=1)最近被访问,且被修改 ( State of hailer knf after the next 1 Example of Clock Policy Operation n 步骤 一扫描循环队列,找出一类页面,找到则淘 汰该页 未找到,开始第二轮扫描,找第二类页面 找到淘汰该页,并将所有经过的页面的访 都失败,黛复(1),(2),直到找到淘 汰页面 其它置换算法 最少使用( Least Frequently Used) 系统抖动 换算法 访问次数最少的一页。在页表种增加 抖动现象 问计数 一设移位寄存器(每一页):高位1 指系统页面量换频,大飞CPU时间 七在来回进行页的调度上,小部分时 )页面缓冲算法( Page buffering 间用于实际运算 一个较优的算法应尽可能兔出现抖 换算法采用FIFO 的页面挂在下列 动现象。一且引起了这种局面,系统 应能立即采取措施加以排除 质糖表的骂衡改实圈这面建赛量喜
5 操 作 系 统 | 虚 拟 存 储 器 25 CUIT 徐虹 操 作 系 统 | 虚 拟 存 储 器 26 CUIT 徐虹 ¾NRU 改进算法 A ：访问位 M：修改位 1类（A=0，M=0） 最近既未被访问，又未被修 改； 2类（A=0，M=1） 最近既未被访问，但已被修 改； 3类（A=1，M=0） 最近被访问，未被修改； 4类（A=1，M=1） 最近被访问，且被修改。 操 作 系 统 | 虚 拟 存 储 器 27 CUIT 徐虹 ¾步骤： ¾扫描循环队列，找出一类页面，找到则淘 汰该页。 ¾未找到，开始第二轮扫描，找第二类页面， 找到淘汰该页，并将所有经过的页面的访 问位置0。 ¾都失败，重复（1），（2），直到找到淘 汰页面。 操 作 系 统 | 虚 拟 存 储 器 28 CUIT 徐虹 操 作 系 统 | 虚 拟 存 储 器 29 CUIT 徐虹 ¾其它置换算法 ¾最少使用（Least Frequently Used）置 换算法 ¾淘汰访问次数最少的一页。在页表种增加 访问计数。 ¾设置移位寄存器（每一页）：高位置1， 定时右移。 ¾页面缓冲算法（Page Buffering Algorithm） ¾置换算法采用FIFO，淘汰的页面挂在下列 两个链表的尾部：空闲页面链表和已修改 页面链表。当修改页面达到一定数量，再 写回磁盘。 操 作 系 统 | 虚 拟 存 储 器 30 CUIT 徐虹 6．4 系统抖动 ¾抖动现象 ¾指系统页面置换频繁，大量CPU 时间 花在来回进行页的调度上，小部分时 间用于实际运算。 ¾一个较优的算法应尽可能避免出现抖 动现象。一旦引起了这种局面，系统 应能立即采取措施加以排除
预防抖动问题(减少缺页中断次数 程序设计质量:程序的局部化程度 分配适当的内存 作集:在段时间内进程实际访闻的面 实验证明:对所有的程序来说,买使其有效的 工作它在内存中的页面微应不低于总页面微 的一半 L=S准则 产生缺页的平均时间等于系统处理进程快页的 平均时间 Typical Paging Behavior of a Program 解决抖动问题的办法 改进算法 6.5请求分段存储管理 在进行淘汰或置换时,一般总 进程懺住不让其换出,而调入的 硬件支持 是占据那些暂时得不到执行的进 的内存区域,从而扩大峡页进程 段表:段名、段长、段基址、存 数>挂起若干进程 取方式、访问字段A、修改字段 存在位P、增补位和外存始址 缺段中断机构 地址变换机构 分段共享与保护 共享段表 共享段裘包括共享进程计数、存取控制 字段和段号 共享段的分配与回收 分段保护
6 操 作 系 统 | 虚 拟 存 储 器 31 CUIT 徐虹 ¾预防抖动问题（减少缺页中断次数） ¾程序设计质量：程序的局部化程度 ¾分配适当的内存 ¾工作集：在某段时间内，进程实际访问的页面 的集合。 ¾实验证明：对所有的程序来说，要使其有效的 工作，它在内存中的页面数应不低于总页面数 的一半。 ¾L = S 准则 ¾产生缺页的平均时间等于系统处理进程缺页的 平均时间。 操 作 系 统 | 虚 拟 存 储 器 32 CUIT 徐虹 操 作 系 统 | 虚 拟 存 储 器 33 CUIT 徐虹 ¾解决抖动问题的办法 ¾改进算法 ¾在进行淘汰或置换时，一般总是把缺页 进程锁住不让其换出，而调入的页或段总 是占据那些暂时得不到执行的进程所占有 的内存区域，从而扩大缺页进程的工作集 ¾挂起若干进程 操 作 系 统 | 虚 拟 存 储 器 34 CUIT 徐虹 6．5 请求分段存储管理 ¾硬件支持 ¾段表：段名、段长、段基址、存 取方式、访问字段A、修改字段M、 存在位P、增补位和外存始址。 ¾缺段中断机构 ¾地址变换机构 操 作 系 统 | 虚 拟 存 储 器 35 CUIT 徐虹 ¾分段共享与保护 ¾共享段表 ¾共享段表包括共享进程计数、存取控制 字段和段号。 ¾共享段的分配与回收 ¾分段保护