第6章--虚拟存储管理

1、2022-4-66.1虚拟存储器的引入虚拟存储器的引入前面介绍的存储管理方案要求作业全部装入内存才可运行。但这会出现两种情况：有的作业因太大，内存装不下而无法运行。有的作业因太大，内存装不下而无法运行。系统中作业数太多，因系统容量有限只能让少数作业先运系统中作业数太多，因系统容量有限只能让少数作业先运行。行。局部性原理（理论基础）1968年P.Denning 提出程序执行时，大多数情况下是顺序执行的。过程调用会使程序的执行轨迹从一部分内存区域转至另一部分区域， 但过程调用的深度不会超过5。程序中有许多循环语句，这些语句会重复多次执行。程序中对数据结构的操作，往往局限在很小的范围内。局部性原理局

2、限性的表现时间局限性时间局限性程序中的的某条指令一旦执行，不久后会再次执行。空间局限性空间局限性程序一旦访问某存储单元，不久后会访问其附近的存储单元。虚拟存储器的定义 所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。离散性离散性作业不装入连续的存储空间，内存分配采用离散分配方多次性多次性一个作业被分割，被多次调入内存。对换性对换性作业在运行过程中换进、换出内存。虚拟性虚拟性从逻辑上扩充了内存的容量。虚拟存储器的特征虚拟存储器的特征从外存装入页/段更新页/段表交换页/段内存满？是否缺页/段中断页/段在内存是否进程执行图 实现虚拟存储的典型过程虚存的基本

3、思想虚存管理目的：提供用户进程一个巨大的虚拟存储空间.手段：利用外存(磁盘)实现此虚空间.系统为进程提供一个比物理内存大得多的虚拟存储空间，虚拟空间大小不受物理内存大小的限制。 虚拟空间的最大容量由系统的有效地址长度决定。假设地址长度为32，按字节寻址，则虚拟存储空间大小为232个字节。它的实际容量为内存容量+外存容量1.虚拟存储技术是（ ）。A 补充内存物理空间的技术B 补充相对地址空间的技术C 扩充外存空间的技术D 扩充输入输出缓冲区的技术2.在虚拟内存管理中,地址变换机构将逻辑地址变换为物理地址,形成该逻辑地址的阶段是（ ）。A 编辑B 编译C 链接D 装载3.虚拟内存的基础是( ）。A

4、 局部性理论B 代码的顺序执行C 变量的连续访问D 指令局部性4.实现虚拟内存是主要的技术是（ ）。A 整体覆盖B 整体对换C 部分对换D 多道程序设计5.以下不属于虚拟内存的特征是（ ）。A 一次性B 多次性C 对换性D 离散性6.在一个计算机系统中,其虚拟存储器的最大容量是由( )决定的,其实际容量是由（ ）决定。A 计算机字长B 内存容量C 硬盘容量D 内存与硬盘容量之和7.设主存容量是1MB,硬盘容量是400MB,计算机系统的地址寄存器有24位,那么虚存的最大容量是（ ）。A 1MBB 401MBC 1MB+224BD 224B状态位P： 记录该页是否在内存记录该页是否在内存。P=1该

5、页在内存；该页在内存； P=0该页不在内存。该页不在内存。访问字段A：记录该页在一段时间内被访问的次数记录该页在一段时间内被访问的次数。修改位M： 记录该页在内存期间是否被修改过。记录该页在内存期间是否被修改过。M=1该页调入内存后被修改过；该页调入内存后被修改过； M=0该页调入内存后未被修改过。该页调入内存后未被修改过。外存地址： 记录记录该页在外存的地址。该页在外存的地址。 页号 存储块号 状态位P 访问字段A 修改位M 外存地址页表的扩充页表的扩充6.2请求页式存储管理缺页中断机构主要表现在：主要表现在：在指令执行期间产生和处理中断信号。一条指令执行期间，可能产生多次缺页中断。如在执行

6、一条指令COPO A TO B时，可能要产生6次缺页中断，其中指令本身跨了两个页面，A和B又分别各是一个数据块，也都跨了两个页面。页面B：A：654321指令COPY ATO B地址变换机构开始页号页表长度越界中断Y查快表查页表页在快表中？NY页在内存？Y修改快表修改访问字段和修改位N形成物理地址结束保留CPU现场从外存找到缺页N内存满否？Y选择一页换出将该页写回外存该页修改过吗？Y从外存读入缺页修改页表NN缺页中断处理请求页式存储管理驻留集管理驻留集管理包括以下内容：驻留集管理包括以下内容：保证进程正常运行所需的最少物理块数最少物理块数是多少？为每个进程分配物理块时，其数目是固定的、固定的、

7、还是可变的可变的？如何为进程置换物理块，是局部置换局部置换？还是全局全局置换置换？物理块越多越好！虚拟？随着为进程分配的物理块数目的减少，将使进程执行中的缺页率提高，从而降低进程的执行速度。能保证进程正常运行所需的最小最小物理块数是多少？这与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。最少物理块数影响物理块分配的主要因素 缺页率缺页率缺页率缺页率（a）页尺寸页尺寸（b）分配的物理块数分配的物理块数PNP表示整个进程的页大小，表示整个进程的页大小，N进程中的总块数进程中的总块数页面大小与物理块数对缺页率的影响页面大小与物理块数对缺页率的影响驻留集管理 固定分配、局部置换固定分配、局部

8、置换为每个进程分配固定页数的内存空间、且运行过程中不变。当进程缺页时，只能从该进程在内存的几个页面中选出一页换出，然后再调入一页，保证进程的页数不变。可变分配、全局置换可变分配、全局置换系统开始先为每个进程分配一定数目的物理块。整个系统有一空闲物理块链，当某进程缺页时，系统从空闲链中选出一块分配给进程。空闲链为空时，OS从所有进程的页面中权衡选择一页换出。可变分配、局部置换可变分配、局部置换分配同上，但进程缺页时，只能从该进程在内存的页面中选出一页换出。请求页式存储管理的调入策略请求页式存储管理的调入策略 何时调入页面何时调入页面预调请调从何处调入从何处调入进程的所有页面都放在对换区对换区。只

9、将修改过的页面放在对换区对换区，未改的放在文文件区件区。 UNIX系统方式，首次从文件区调入，换出时放在对换区，以后从对换区调入。页面调入过程页面调入过程访问的页在内存访问的页在内存产生缺页中断产生缺页中断内存中有空块内存中有空块从外存调入要访问的页从外存调入要访问的页换出某些暂时不用的页换出某些暂时不用的页运行运行NONOu页面置换算法：在指定的置换范围内，决定将哪一个页面换出内存。u置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。u当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程

10、使用，则又需要将其换入内存。u如果系统花费大量的时间把程序和数据频繁地装入和移出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。u根本原因：选择的页面或段不恰当。请求页式存储管理的页面置换算法 请求页式存储管理的页面置换算法 最佳置换算法OPT先进先出置换算法FIFO最近最久未使用置换算法LRU CLOCK置换算法最佳置换算法举例：驻留集大小为举例：驻留集大小为3 3，访问串为，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3

11、, 2.770701201201203203243243243203203203O O O O O O O淘汰下次访问距当前最远的那些页中序号最小的页。淘汰下次访问距当前最远的那些页中序号最小的页。 OPT方法特点： 最优的固定驻留集大小置换策略。最优的固定驻留集大小置换策略。 不可实现。不可实现。OPTOPT策略对任意一个访问串的控制均有最小的时策略对任意一个访问串的控制均有最小的时空积。（进程所占空间与时间的乘积）空积。（进程所占空间与时间的乘积）由于由于需要预先得知整个访问串的序，故不能用需要预先得知整个访问串的序，故不能用于实践于实践。仅作为一种标准，用以测量其他可行。仅作为一种标准，

12、用以测量其他可行策略的性能。策略的性能。先进先出页面置换算法替换最早进入的页举例：驻留集大小为举例：驻留集大小为3 3，访问串为，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.770701201201231230430420423023023023O O O O O O O O O OFIFO方法的特点： 实现方便。不需要额外硬件。实现方便。不需要额外硬件。 效果不好，有效果不好，有BeladyBelady奇异。奇异。Belady奇异：指置换策略不满足随着驻留指置换策略不满足随着

13、驻留集的增大，页故障数一定减少的规律。集的增大，页故障数一定减少的规律。Belady奇异页面走向页面走向 物理块物理块012301401234000012300014411123011142222301444233缺页缺页OOOOOOOOO页面走向页面走向 物理块物理块0123014012340000000123401111111234012222223401233333401234缺页缺页OOOOOOOOOO最近最久未使用LRU页面置换算法淘汰上次使用距当前最远的页。淘汰上次使用距当前最远的页。举例：驻留集大小为举例：驻留集大小为3 3，访问串为，访问串为 7, 0, 1, 2, 0, 3,

14、 0, 4, 2, 3, 0, 3, 2.7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.770701201201203203403402432032032032O O O O O O O O OCLOCK页面置换算法 LRU性能较好，但实现困难！因此可用CLOCK算法。为每页设一访问位，再将内存中的所有页面链接成一循环队列。 当某页被访问时，其访问位置1。 置换算法在选择一页淘汰时，只需检查其访问位。如果是如果是0，就选择该页换出；，就选择该页换出；如果是如果是1，则重新将其置为，则重新将其置为0，暂不换出。，暂不换出。33/19页面页面12使用位使用位=1页面页

15、面2使用位使用位=1页面页面36使用位使用位=0页面页面6使用位使用位=1页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0页面页面12使用位使用位=0页面页面2使用位使用位=1页面页面9使用位使用位=1页面页面6使用位使用位=0页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0(a)页面置换前状态页面置换前状态(b)页面置换后状态页面置换后状态01234567新调入9号页面CLOCK页面置换算法除了考虑页面的使用情况外，还要考虑该页是否被修改被修改过。由访问位访问位A和修改

16、位修改位M组合成下面四种情况的组合： A=0，M=0该页既未被访问过、又未被修改过，是最佳淘汰页。 A=0，M=1该页最近未被访问、但已被修改，可以被淘汰。 A=1，M=0最近已被访问，但未被修改，该页有可能再被访问。 A=1，M=1最近已被访问且被修改，该页可能再被访问。1从当前位置扫描循环队列，寻找1类页面。2若1失败，开始第二轮扫描，寻找类页面，并将所经过的页面的访问位置0。3若2也失败，返回到开始位置，将所有的访问位复0，goto 1。块号块号页号页号访问位访问位修改位修改位571120108111Clock置换算法置换算法7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0

17、 1 7 0 1驻留集正确选择驻留集窗口大小：窗口大小选择得过小，频繁产生缺页中断。窗口大小选择得很大，失去了虚拟存储器的意义。1824151823241718241817171524172424 182424 1515 1818 2323 2424 1717 1818 2418 1717 1515 2424 1717 24 182424 1524 15 1815 18 2318 23 2423 24 1724 17 1818 17 1517 15 24页访问序列窗口大小2 3 4 52424 1524 15 1824 15 18 2318 23 24 1724 18 17 152424 15

18、24 15 1824 15 18 2315 18 23 24 17驻留集驻留集：即在某段时间间隔内，进程实际要访问的页面的集合。缺页率与物理块数的关系下限上限物理块数缺页率为进程分配的物理块数达到一定值图中拐点拐点处，缺页率保持在上下限之间CPU的利用率与多道程序数的关系多道程序度CPU利用率抖动的产生抖动的产生在多道程序环境下，并不是“多道程序的度越高，系统吞吐量越大。”当CPU的利用率达到某一峰值后，若继续增加多道程度，将产生抖动抖动。抖动预防方法抖动预防方法加载控制 L=S准则（产生缺页的平均时间L等于系统处理缺页的平均时间 S）采用局部置换挂起若干进程1.在请求分页系统中,分页是由(

19、）实现。A 程序员B 编译器C 系统调用D 操作系统2.系统的抖动是指（ ）。A 使用机器时,造成屏幕闪烁的现象B 则调出的页面又立即被装入所形成的频繁装入/调出的现象C 系统盘有问题,造成系统不稳定的现象D 由于主存分配不当,偶然造成主存不够的现象3.（ ）是请求分页存储管理方式与基本分页存储管理方式的区别。A 地址重定位B 不必将作业全部装入内存C 采用快表技术D 不改将作业装入连续区域4.在请求分页存储管理系统中,LRU算法是指( ）。A 最早进入内存的页先淘汰B 近期最长时间以来没被访问的页先淘汰C 近期被访问次数最少的页先淘汰D 以后再也不用到页先淘汰5.在请求页式存储管理中,页表项

20、使用修改位的目的是（ ）。A 实现LRU算法B 实现FIFO算法C 在快表中检查页面是否进入内存D 检查页表是否最近被写过6.在请求页式管理中,页面的大小与可能产生的缺页中断次数（ ）。A 成正比B 成反比C 无关D 成固定比例7.作业在执行中发生缺页中断,经操作系统处理后,应让其执行（ ）命令。A 被中断的前一条B 被中断的后一条C 被中断的那一条D 启动时第一条8.在一个采用页式虚拟存储管理的系统中，某进程依次要访问的字地址序列为：115，228，128，88，446，102，321，432，260，167，若作为的第0页已经装入内存，现分配给该作业的主存共300字，页的大小为100字，则

21、： 1) 按FIFO调度算法将产生多少次缺页中断，依次淘汰的页号是什么？ 2) 按LRU调度算法将产生多少次缺页中断，依次淘汰的页号是什么？9.页面调度算法中有LRU,FIFO和Clock算法，针对以下条件，计算上述3个算法下的页面调度过程和缺页中断率。页面访问序列：2，3，2，1，5，2，4，5，3，2，5，2分配内存块：3块请段式系统中段表的扩充请段式系统中段表的扩充 6.3请求段式存储管理 段号 段长 段始址 存取方式 状态位 访问字段 修改位 增补位 外存地址增加了以下表项：存取方式：用于标识本段的存取属性是只执行、只读，还是允许读/写状态位：指示该段是否已进驻内存访问字段：用于记录本段有多长时间没有被访问。置换算法在选择换出段时参考修改位：表示该段调入内存后是否被修改过增补位：这是请求段式存储管理系统中特有的字段，用于表示本段在运行过程中是否进行过动态增长外存地址：