计算机操作系统第五章-虚拟存储器教材

1、第五章 虚拟存储器第一节 虚拟存储器的基本概念一、虚拟存储器的引入在前面介绍的各种存储管理方式中，用户作业一旦被装入内存， 就会一直驻留其中， 直到进程运行结束 (驻留性 )。有些存储管理方式还 存在一次性。因此，用户作业要最终运行完毕，系统必须给它提供不 短于作业长度的存储空间。于是就出现了两种问题：? 长作业无法运行? 大量作业无法同时运行程序运行的 局部性原理 ：在一段时间内一个程序的执行往往呈现 出高度的局部性。前期讨论：P112-113;局部性还表现在两方面：(1) 一条指令被执行， 则不久以后该指令很可能再次执行； 某个数 据被访问，则不久以后该数据附近的数据很可能被访问。产生这类

2、局 部性的典型原因，是由于在程序中存在着大量的循环操作。(2) 程序在 一段时间内 所访问的地址，可能 集中 在一定的范围之 内。若某一存储单元被使用，则在一定时间内，与该存储单元相邻 的单元很可能被使用。其典型情况便是程序的顺序执行、数组的处理等。局部性原理是在存储分配时克服驻留性、实现虚拟存储的依据。二、虚拟存储器的定义 定义： 具有 请求调入 功能和置换功能，能从 逻辑上 对内存容量进行扩 充的一种存储器系统。其访问速度接近于内存，而其容量和每位的成本却又接近于外存。从整体看 速度是主存 容量是辅存特性：虚拟存储器连续性离散性一次性多次性驻留性交换性虚拟性对用户而言，它访问特性和内存一样

3、；它以 CPU时间和外存空间 换取宝贵内存空间，是操作系统中的一种资源转换技术。容量：? 一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址宽度为32位，则程序可以寻址范围 是0232-1，即 虚存容量可达4GB。?虚拟存储器的容量与主存的实际大小没有直接的关系，而是在主存与辅存的容量之和的范围内。三、虚拟存储技术基本原理：P115把内存与外存有机地结合起来使用，从而得到一个容量很大的“内 存”。当进程开始运行时，先将它的一部分内容装入内存，另一部分暂 时留在外存。 在运行过程中， 当要访问的指令 /数据不在内存时， 由 OS 自动将内存中的一些内容调到外存，藤出空间，

4、再将马上要访问的内 容从外存调入内存。目的： 提高内存利用率；为大作业的运行提供可能。实现方法：? 请求分页系统? 请求分段系统第二节 请求分页式存储管理方式一、基本原理对静态分页式存储管理进行改进 ：请求分页式存储管理在进程开 始运行之前，不是将作业的全部页装入，而是装入开始的少数几页 （甚 至一页）入内存。之后根据进程运行的 需要，利用请求调入 技术，动态 地装入后续页；当内存空间已满，而又需要装入新的页时，则又利用 置换技术，根据某种算法 淘汰 一个页，以便藤出空间 装入 新的一页。请求分页式存储管理需要解决下面三个问题：? OS 如何知道进程要访问的页面在不在内存中；? 当发现缺页时，

5、如何把所缺页面调入内存；? 当内存中没有空闲块时，为了要接受一个新页，需要把老的一页淘 汰出去，根据什么策略选择准备淘汰的页。二、硬件的支持1、改进页表的结构页号物理块号状态位P访问字段A修改位M外存地址?状态位（驻留位）：表示该页目前是在内存还是在外存；?访问字段：记录该页最近 是否被访问过或被访问的次数；?修改位：表示该页在本次读入内存后 是否在内存中被改写过；?外存地址：用于指出该页在 外存上的地址，通常是物理块号，供调 入该页时参考。2、增加缺页中断机构：每当进程要访问的一个逻辑地址所属的页目前不在内存，就产生缺页中断，进行调页或换页处理。?在地址变换过程中，在页表中发现所要访问的页不

6、在内存，则产生 缺页中断。操作系统接到此中断信号后，就调出 缺页中断处理程序， 根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去（实 现了请求调入）；?如果内存中有空闲块，则 分配一块，将新调入页 装入内存，并修改 页表中相应页表项目的驻留位及相应的内存块号；?若此时内存中没有空闲块，则要 淘汰某页。若将被淘汰的页在内存 期间被修改过，则要将其 写回外存（实现了置换）；缺页中断的中断处理过程，见下图左。3、修改后的地址变换流程，见下图右P158T穿留CPU现场老多TO硯伴将一页賦外存换入内存从外存申授到猷页将该页写回外存8命令CPU.以丹存读缺页倏改页表图4124请 的三、存储分配

7、方法1、存储分配方法的改进：?在进程开始执行时，只将最开始和最常用的部分（如主程序、主菜单） 按页装入内存。为整个进程建立页表，记录进程各页使用内存的情况。其他页在进程执行的过程中被动态地装入。?当需要访问的页不在内存中时，系统产生并处理缺页中断。?页表在页被调入、换出时要被改写，记录进程的各页对内存使用情 况的变化。2、物理块的分配策略和分配算法 ?最小物理块数及其确定最小物理块数是指能保证进程正常运行所需要的最小物理块数。它取决于指令的格式、功能和寻址方式。? 物理块的分配算法P138-140? 物理块的置换策略P135-137四、调页策略1、调页时机 确定何时调页? 预调入：一次调入一批

8、预计即将访问的页。本方法主要用于进程的首次页调入。? 请求调入：缺页时调入，一次调入一页。2、调页地址 确定从何处调入? 全部从 对换区 调入、调出；? 需要修改的部分从对换区调入、调出，其他部分从文件区调入；? 初次调入，从文件区；调出放到交换区；再次调入，从交换区。3、调页过程 确定如何调页调页过程即缺页中断处理程序的处理过程，如前面的框图。调页 过程中，重要的一步是按照一定的 页面置换算法 淘汰内存中的一页， 空出一块来存放新调入的页。第三节 页面置换算法页面置换算法 是“ 选择一页，换出内存 ”时选择哪一页的原则和 方法。置换算法的好坏，直接影响存储管理的 性能 。置换算法的理想方案，

9、是将那些访问概率高的页面留在内存中， 而将那些访问概率最低的页面换出内存。对换出页面的不同选择形成 不同的置换算法。 一个好的页面置换算法应该 有较低 的页面更换频率 ， 避免频繁地换页造成系统性能的下降。一、几种简单的算法1、随机淘汰算法当系统设计人员无法确定哪类页访问的频率低的情况下，就随机 地选择一个用户页，将其换出。2、最佳置换算法(只是一种理论上的算法)每次将以后最长时间内不再被访问或永远不再被访问的页换出。 该算法保证最低的缺页率。二、先进先出(FIFO)置换算法1、算法思想：选择在内存中驻留时间最长的页，交换出去。例如：假定系统为某进程分配了三个物理块，并考虑有以下的页面访问串：

10、7，0，1, 2，0，3, 0，4，2, 3, 0，3，2，1, 2，0，1,7, 0, 1页框图4-26利用FIFO置换算法时的置换图2、算法的实现：将一个进程已调入的 页按进入的先后次序链成一个 队列，设一个头指针、一个尾指针。每次将头指针指向的页替换出去；新调入的页插到队尾。3、算法的特点:?简单、易实现，需要的硬件支持少。?但是，经常要使用的页，频繁地被选择换出（最先被调入的页可能是 最常使用的）。三、最近最久未使用（LRU）置换算法1、算法思想：选择最后一次访问时间距离当前时间最长的一页并淘汰 之。即淘汰没有使用的时间最长的页。该算法需要较多的硬件支持。页框图427 LRU页面置换算

11、法2、硬件支持与实现（1）移位寄存器：为每个在内存中的页面配置一个移位寄存器（字），可表示为R=Rn-lRn-2Rn-3 R2R1R0?当该页面被访问时，将R的最高位置1;?系统定时将所有页面的移位寄存器逻辑右移一位，进行除2操作；?换页时将移位寄存器值最小的页淘汰。（2）栈：保存当前页面使用的变化情况为每个进程建立一个 栈，栈的大小等于分配给进程的块数。换页 时淘汰栈底的页，最近访问的页放在栈顶3、算法特点?比较接近理想的置换算法；?需要较多的硬件支持。四、Clock置换算法（简化的LRU算法）1、算法思想：页每被访问一次，将该页的访问位置 1块号页号访问位指针替换01240指针342156

12、50711V图4-30简单Clock置换算法的流程和示例2、改进型Clock置换算法由访问位A和修改位M可以组合成下面四种类型的页面：?1类（A=0，M=0）:表示该页最近既未被访问，又未被修改，是最佳淘汰页。? 2类（A=0，M=1）:表示该页最近未被访问，但已被修改，并不是很 好的淘汰页。? 3类(A=1 , M=0):最近已被访问， 但未被修改，该页有可能再被 访问。? 4类(A=1 , M=1):最近已被访问且被修改，该页有可能再被访问。其淘汰的过程可分成以下三步:(1) 从指针所指示的当前位置开始，循环扫描队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个这样的页面作为所

13、选中的淘汰页。 在第一次扫描期间不改变访问位 A。(2) 如果第一步失败， 即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找 A=0 且 M=1 的第二类页面， 将所遇到的第一个这类页面作 为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3) 如果第二步也失败， 即未找到第二类页面， 则将指针返回到开始的 位置，并已将所有的访问位 A 复 0。然后重复第一步，如果仍失败， 必要时再重复第二步，此时就一定能找到被淘汰的页。五、其他置换算法1、最少使用(LFU : Least Frequently Used置换算法2、 页面缓冲算法 (PBA：Page Buffering A

14、lgorithm)P166-169六、虚拟存储器的性能问题缺页次数是影响性能的一个主要因素。1 、影响缺页次数的因素? 分配给进程的物理块数? 页面本身的大小 ? 程序的编制方法?页面淘汰算法2、抖动问题在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所 需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导 致系统崩溃。这种现象称为颠簸或抖动。原因：?分配给进程的物理页面数太少?页面淘汰算法不合理第四节 请求分段存储管理方式一、硬件支持1、改进段表：P171-172段名段长段的存取访问修改存在增补外存基址方式字段A位M位P位始址2、增加缺段中断机构，每当进程要调用或访问的一个逻辑

15、段目前 不在 内存，就产生缺段中断。图4-31请求分段系统中的缺断处理过程3、改变地址变换过程(访问訂寸|是是否 _1分段越界 中断处理分段保护 中断处理否 缺段中段长？合存取万式二是修改访问字段，如写 访问，置修改位=1形成访问主存地址(A)蛙存始址)-K位移量段主存？返回图432请求分段系统的地址变换过程二、段的共享与保护1、共享段表为实现段的共享，系统建立一个 共享段表，每个共享段在其中占一个表项。1駐1舷主密址tts共享段的作遊席lij段名|段検|主存始址|状态共亭本段的作遊沽作业名作业号段号存取控制2、共享段的存储分配?对第一个请求使用该共享段的进程，由系统为该共享段分配一物理 区，再把共享段调入该区，同时将该区的有关信息填入请求进程的段表的相应项中。还须在共享段表中增加一表项，填写有关信息，把count 置为1；?当又有其它进程请求调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在 请求进程的段表 中，增 加一表项，填写该共享段的有关信息；在 共享段的段表中，填上请求 进程的进程名、存取控制等信息，再执行 count ：二count+1操作，以表 明增加了一个进程共享该段。3、共