第五章 虚拟存储器

1、第五章第五章 虚拟存储器虚拟存储器5.1 5.1 虚拟存储器概述虚拟存储器概述 5.2 5.2 请求分页存储管理方式请求分页存储管理方式 5.3 5.3 页面置换算法页面置换算法 5.4 “5.4 “抖动抖动”与工作集与工作集5.5 5.5 请求分段存储管理方式请求分段存储管理方式 5.1 虚拟存储器 分页内存分配和分段内存分配方法可以解决程序在内存中离散存放的问题，但是，这两种方式都要求程序整个装入内存。事实上，很多时候，程序本身比内存要大得多，那么简单的分页和分段的内存方式就无法解决这个问题了。可以采用虚拟存储器的方法，使用请求分配和置换策略请求分配和置换策略来实现存储管理。5.1 虚拟存

2、储器为什么需要虚拟存储器： 程序大于内存 程序暂时不执行或运行完是否还要占用内存 程序的局部性原理5.1 5.1 虚拟存储器虚拟存储器5.1.1 5.1.1 引入引入1.1.常规存储管理的特征：常规存储管理的特征： 一次性（指全部装入）、一次性（指全部装入）、 驻留性（指驻留在内存不换出）驻留性（指驻留在内存不换出）2 2、局部性原理、局部性原理 时间局部性：如循环执行时间局部性：如循环执行 空间局部性：如顺序执行。空间局部性：如顺序执行。3 3、虚拟存贮器、虚拟存贮器 具有请求调入功能和置换功能，能从逻辑上对具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。内存容量进行

3、扩充的一种存储系统。 实质：以时间换空间，但时间牺牲不大。实质：以时间换空间，但时间牺牲不大。 虚存大小由虚存大小由_决定。决定。 虚拟存储器技术需要解决的问题 ：地址映射 分配策略 置换策略 装载控制 5.1.2 5.1.2 虚拟存储器的实现方式虚拟存储器的实现方式需要需要动态重定位动态重定位1 1、请求分页系统、请求分页系统 以页为单位转换以页为单位转换 需硬件：需硬件：（1 1）请求分页的页表机制）请求分页的页表机制（2 2）缺页中断）缺页中断（3 3）地址变换机构）地址变换机构 需实现请求分页机制的软件（页面请调、置换软件等）需实现请求分页机制的软件（页面请调、置换软件等）2 2、请求

4、分段系统、请求分段系统 以段为单位转换以段为单位转换: :（1 1）请求分段的段表结构）请求分段的段表结构（2 2）缺段中断）缺段中断（3 3）地址变换机构）地址变换机构 需实现请求分段机制的软件（段请调、置换软件等）需实现请求分段机制的软件（段请调、置换软件等）5.1.3 5.1.3 虚存特征虚存特征1 1多次性多次性：局部装入，多次装入。：局部装入，多次装入。2 2对换性对换性：换进、换出：换进、换出3 3虚拟性虚拟性：从逻辑上扩充内存：从逻辑上扩充内存离散分配离散分配：支持多次性和对换性，若连续：支持多次性和对换性，若连续则不可能提供虚存，无法支持大作业小则不可能提供虚存，无法支持大作业

5、小内存运行内存运行请求分页概念请求分页概念 在进程开始运行之前，不是装入全部页面，而是装入几个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。5.2.1 5.2.1 请求分页中的数据结构及硬件支持请求分页中的数据结构及硬件支持1 1、页表机制、页表机制 页表项：页表项：2 2、缺页中断机构、缺页中断机构：可在指令执行期间产生（如图：可在指令执行期间产生（如图5-15-1）转入缺页中断处理程序。转入缺页中断处理程序。3 3、地址变换机构、地址变换机构比较简单分页机制，增加了中断处理，（比较简单分页机制，增加了中

6、断处理，（如图如图5-25-2）5.2 5.2 请求分页存储管理方式请求分页存储管理方式页号页号物理块号物理块号状态位状态位P P 访问字段访问字段A A修改位修改位M M 外存地址外存地址 图图5-1 5-1 涉及涉及6 6次缺页中断的指令次缺页中断的指令图图5-2 请求分页中的地址变换过程请求分页中的地址变换过程 MMU例6 现有一请求调页系统，页表保存在寄存器中。若有一个被替换的页未被修改过，则处理一个缺页中断需要8ms；若被替换的页已被修改过，则处理一个缺页中断需要20ms；内存存取时间为1s，访问页表的时间可忽略不计。假定70%被替换的页被修改过，为保证有效存取时间不超过2s，可接受

7、的最大缺页率是多少？注：（缺页率=缺页次数/总的页面访问次数） 解：解： 如果用p表示缺页率，则有效存取时间不超过2s可表示为：(1-p)1s+p(0.720ms+0.38ms+1s) 2s因此可计算出：p 1/164000.000065.2.2 5.2.2 内存分配策略和分配算法内存分配策略和分配算法1 1、最小物理块数：、最小物理块数：与计算机的硬件结构有关与计算机的硬件结构有关不同的作业要求不同。不同的作业要求不同。如：允许间接寻址：则至如：允许间接寻址：则至少要求少要求3 3个物理块。个物理块。Mov A, B Mov A, B 物理块是否越大越好？缺页次数缺页次数 Versus 物理

8、页框数物理页框数临界点临界点5.2.2 5.2.2 内存分配策略和分配算法内存分配策略和分配算法2 2、页面分配和置换策略。、页面分配和置换策略。1 1）固定分配局部置换。）固定分配局部置换。 缺点：难以确定固定分配的页数缺点：难以确定固定分配的页数.(.(少：少：置换率高置换率高 多：浪费多：浪费) )2 2）可变分配全局置换）可变分配全局置换3 3）可变分配局部置换）可变分配局部置换 根据进程的缺页率进行页面数调整，根据进程的缺页率进行页面数调整，进程之间相互不会影响。进程之间相互不会影响。3 3、分配算法、分配算法 1 1）平均分配算法）平均分配算法2 2）按进程大小比例分配算法：）按进

9、程大小比例分配算法：3 3）考虑优先权分配算法）考虑优先权分配算法 mssbiiniiss15.2.3 5.2.3 页面调入策略页面调入策略 1.1.调入时机：调入时机： 预调：（根据空间局部性）预调：（根据空间局部性） 目前：成功率目前：成功率5050；适合于首次调入时；适合于首次调入时 请求调页：每次调入一页，较费系统开销请求调页：每次调入一页，较费系统开销 各有优劣各有优劣2 2从何处调页：从何处调页： 对换区：修改过的页被换出时入对换区，对换区：修改过的页被换出时入对换区， 快快 文件区：稍慢文件区：稍慢 UnixUnix方式方式 对共享页，应判断其是否在内存区。对共享页，应判断其是否

10、在内存区。3.3.页面调入过程页面调入过程目的：减少对换量，提高系统性能目的：减少对换量，提高系统性能 5.3.1 5.3.1 最佳置换算法和先进先出算法最佳置换算法和先进先出算法1 1、最佳（、最佳（OptimalOptimal）置换算法（理论上的）置换算法（理论上的）5.3 5.3 页置换算法页置换算法 图图 5-3 利用最佳页面置换算法时的置换图利用最佳页面置换算法时的置换图 5.3 5.3 页面置换算法页面置换算法 2 2、先进先出（、先进先出（FIFOFIFO）页面置换算法）页面置换算法 图图 5-4 利用利用FIFO置换算法时的置换图置换算法时的置换图 是否页框数增加就一定会减少缺

11、页数呢？是否页框数增加就一定会减少缺页数呢？2 2、先进先出（、先进先出（FIFOFIFO）页面置换算法（续）页面置换算法（续） Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process)4 framesFIFO Replacement Beladys Anomaly more frames less page faults1231234125349 page faults10 page faults12312351245443FIF

12、O Illustrating Beladys Anomaly5.3.2 5.3.2 最近最久未用最近最久未用LRULRU置换置换1 1、算法描述、算法描述 将将“最近的过去最近的过去”，作为，作为“最近的将来最近的将来”。图图 5-5 LRU页面置换算法页面置换算法 2. LRU2. LRU置换算法的硬件支持置换算法的硬件支持 1) 1) 寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为: R=Rn-1Rn-2Rn-3 R2R1R0 2) 2) 栈栈 图图 5-7 用栈保存当前使用页面时栈的变化情况用栈保存当前使用页面时栈的变化情况 5.3

13、.3 Clock5.3.3 Clock置换算法置换算法（一种LRU近似算法：硬件消耗少）1 1、简单的、简单的ClockClock算法算法( (最近未用算法最近未用算法NRUNRU）：）： 设一访问位：图设一访问位：图5-85-8；循环扫描，每次扫描时将访问；循环扫描，每次扫描时将访问位复位。位复位。图图 5-8 简单简单Clock置换算法的流程和示例置换算法的流程和示例 页面页面12使用位使用位=1页面页面2使用位使用位=1页面页面36使用位使用位=0页面页面6使用位使用位=1页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0页面页

14、面12使用位使用位=0页面页面2使用位使用位=1页面页面9使用位使用位=1页面页面6使用位使用位=0页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0(a)页面置换前状态页面置换前状态(b)页面置换后状态页面置换后状态01234567时钟算法时钟算法2. 2. 改进型改进型ClockClock置换算法置换算法 由访问位A和修改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 2类(A=0, M=1)： 3类(A=1, M=0)： 4类(A=1, M=1): 其执行过程可分成以下几步：5.3.4 5.3.4 其它置换算法其

15、它置换算法1 1、最少使用算法、最少使用算法 LFULFU（访问频率）（访问频率） 与与LRULRU类似（记录访问次数），设置一个访问计数类似（记录访问次数），设置一个访问计数器。器。2 2、页面缓冲算法：、页面缓冲算法： 特点：淘汰的页只是修改标志；若页被修改过，则特点：淘汰的页只是修改标志；若页被修改过，则在欲复盖它时回写，否则成批回写。在欲复盖它时回写，否则成批回写。 在欲重访问该页时，若页换出则只需修改标志。在欲重访问该页时，若页换出则只需修改标志。5.4 “抖动抖动”与工作集与工作集5.5 5.5 请求分段存储管理方式请求分段存储管理方式5.5.1 5.5.1 请求分段中的硬件支持请

16、求分段中的硬件支持1 1、段表机制：、段表机制：2 2、缺段中断机构：、缺段中断机构： 段不定长，处理起来比缺页中断复杂。段不定长，处理起来比缺页中断复杂。图图5-125-123 3、地址变换机构、地址变换机构 图图5-135-13段名段名 段长段长 段的段的基址基址 存取存取方式方式 访问访问字段字段A 修改修改位位M 存在存在位位P 增补增补位位 外存外存始址始址 图图 5-12 5-12 请求分段系统中的中断处理过程请求分段系统中的中断处理过程图图 5-13 5-13 请求分段系统的地址变换过程请求分段系统的地址变换过程5.5.2 5.5.2 分段的共享与保护分段的共享与保护1 1、共享

17、段表：、共享段表：（整个系统一张）（整个系统一张）1 1）共享进程计数。）共享进程计数。2 2）存取控制字段。）存取控制字段。3 3）段号：不同的进程可以使用不同的段号去共享段。）段号：不同的进程可以使用不同的段号去共享段。图图 4-34 4-34 共享段表项共享段表项 5.5.2 5.5.2 分段的共享与保护分段的共享与保护2 2、共享段的分配与回收、共享段的分配与回收1 1）分配：）分配： 第一次访问：分配内存，（第一次访问：分配内存，（1 1）增加共享段表；）增加共享段表；（2 2）修改进程段表。）修改进程段表。 第二次访问：（第二次访问：（1 1）修改共享段表；（）修改共享段表；（2

18、2）修改）修改进程段表。进程段表。2 2）回收：）回收： （1 1）count=0 count=0 （2 2）count0count05.5.2 5.5.2 分段的共享与保护分段的共享与保护3 3、分段保护、分段保护1 1）越界检查）越界检查 段号越界检查。段号越界检查。 段内偏移越界检查。段内偏移越界检查。2 2）存取控制检查。）存取控制检查。 R R；R/WR/W；E E3 3）环保护机构）环保护机构（1 1）内环可访问相同环或外环数据；）内环可访问相同环或外环数据；（2 2）外环可请求相同环或内环服务。）外环可请求相同环或内环服务。段式存储管理段式存储管理页式存储管理页式存储管理段页式存储管理段页式存储管理虚拟存储器虚拟存储器虚拟存储技术虚拟存储技术程序局部性原理程序局部性原理虚拟页式管理虚拟页式管理虚拟段式管理虚拟段式管理页面淘汰算法页面淘汰算法抖动（颠簸）抖动（颠簸）工作集模型工作集模型用户程序划分用户程序划分逻辑地址逻辑地址内存空间划分内存空间划分内存分配内存分配管理考虑