1 第六章虚拟存储器 虚拟存储器的概念 请求页式管理 页面置换算法 请求段式管理 操 作 系 统 | 虚 拟 存 储 器 2 CUIT 徐虹 6．1虚拟存储器的基本概念 ?虚拟存储器的引入 ?程序的分段执行 ?局部性原理 ?在执行中的程序，某一段时间内， CPU 总是集中地访问程序中的某一 部分。 ?时间局限性 ?空间局限性 操 作 系 统 | 虚 拟 存 储 器 3 CUIT 徐虹 ?虚拟存储器的定义 ?利用请求调入和交换技术，为用户提供 一个存储容量比实际内存容量大得多的存 储器，称之为虚拟存储器。 ?虚存的形式 ?单段式虚存：一个连续线性地址空间。 ?多段式虚存：把地址空间分成若干段， 每一段是一个连续的线性空间。 操 作 系 统 | 虚 拟 存 储 器 4 CUIT 徐虹 ?虚存容量 ?在多道程序环境下，系统可分为每个用户 建一个虚存。 ?其容量可为内存与外存的容量之和，或由 计算机地址结构和寻址方式确定。 ?基础条件 ?有相当容量的外存。 ?要有一定容量的内存。 ?地址变换机构。 操 作 系 统 | 虚 拟 存 储 器 5 CUIT 徐虹 ?虚拟存储器的实现方式 ?请求分页系统 ?在分页系统的基础上，增加了请求调页和页面置 换功能所形成的页式虚拟存储系统。 ?请求分页的页表机制 ?缺页中断机构 ?地址变换机构 ?请求分段系统 ?请求分段的页表机制 ?缺段中断机构 ?地址变换机构 操 作 系 统 | 虚 拟 存 储 器 6 CUIT 徐虹 ?虚拟存储器的特征 ?离散性 ?多次性 ?对换性 ?虚拟性 2 操 作 系 统 | 虚 拟 存 储 器 7 CUIT 徐虹 6．2请求分页存储管理 ?请求页式管理和预调入页式管理 ?请求页式管理 ?当需要执行的指令或访问的数据不在内存 时，产生缺页中断，系统将外存中相应的 页面调入内存。 ?预调入页式管理 ?系统对那些在外存中的页进行调入顺序计 算，估计出这些页中的指令和数据的执行 和被访问的顺序，并按此顺序将它们调入 和调出内存。 操 作 系 统 | 虚 拟 存 储 器 8 CUIT 徐虹 ?实现原理 ?基本问题 ?要访问的虚页在不在内存 ?扩充页表功能：增加中断位I 和外存地址 ?虚页不在内存时的处理 ?由动态地址变换机构产生一缺页中断。OS 进行中断处理后，根据该页的外存地址把它 从外存调入内存，然后继续执行。 操 作 系 统 | 虚 拟 存 储 器 9 CUIT 徐虹 ?页面的调入调出 ?调入：有无空白页，是否淘汰一页，修改页 表。 ?调出（淘汰） ?处理过程 ?当传输进程某页时，阻塞，系统调度另一进 程。 ?外页面表 ?对于进入系统的每个作业，除在外存建立文 件目录外，还需建立外页面表：页号，物理 块号（磁盘上的位置），保护信息。调度一 个作业时，在内存中根据外页面表建立页表。 操 作 系 统 | 虚 拟 存 储 器 10 CUIT 徐虹 ?请求分页中的硬件支持 ?页表机制 ?页表的构成：页号、物理块号、状态位P、访问 字段A、修改位M和外存地址。 ?缺页中断机构 ?处理过程：保护CPU现场、分析中断原因和转 入中断处理程序。 ?特点 ?地址变换机构 操 作 系 统 | 虚 拟 存 储 器 11 CUIT 徐虹 ?联 想 存 储 器 操 作 系 统 | 虚 拟 存 储 器 12 CUIT 徐虹 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）和一替换指针，指针指向 最早调入内存的一页。 ?把这个队列表建立在存储分块表中。 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 徐虹 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 时间 花在来回进行页的调度上，小部分时 间用于实际运算。 ?一个较优的算法应尽可能避免出现抖 动现象。一旦引起了这种局面，系统 应能立即采取措施加以排除。 6 操 作 系 统 | 虚 拟 存 储 器 31 CUIT 徐虹 ?预防抖动问题（减少缺页中断次数） ?程序设计质量：程序的局部化程度 ?分配适当的内存 ?工作集：在某段时间内，进程实际访问的页面 的集合。 ?实验证明：对所有的程序来说，要使其有效的 工作，它在内存中的页面数应不低于总页面数 的一半。 ?L = S 准则 ?产生缺页的平均时间等于系统处理进程缺页的 平均时间。 操 作 系 统 | 虚 拟 存 储 器 32 CUIT 徐虹 操 作 系 统 | 虚 拟 存 储 器 33 CUIT 徐虹 ?解决抖动问题的办法 ?改进算法 ?在进行淘汰或置换时，一般总是把缺页 进程锁住不让其换出，而调入的页或段总 是占据那些暂时得不到执行的进程所占有 的内存区域，从而扩大缺页进程的工作集 ?挂起若干进程 操 作 系 统 | 虚 拟 存 储 器 34 CUIT 徐虹 6．5请求分段存储管理 ?硬件支持 ?段表：段名、段长、段基址、存 取方式、访问字段A、修改字段M、 存在位P、增补位和外存始址。 ?缺段中断机构 ?地址变换机构 操 作 系 统 | 虚 拟 存 储 器 35 CUIT 徐虹 ?分段共享与保护 ?共享段表 ?共享段表包括共享进程计数、存取控制 字段和段号。 ?共享段的分配与回收 ?分段保护