操作系统os课件第五章

第五章虚拟存储器outline5.1虚拟存储器概述

5.2请求分页存储管理方式5.3页面置换算法5.4抖动与工作集5.5请求分段存储管理方式5.1虚拟存储器概述5.1.1常规存储管理方式的特征和局部性5.1.2虚拟存储器的定义和特征5.1.3虚拟存储器的实现方法5.1.1常规存储管理方式的特征和局部性常规存储器的特征一次性驻留性这些特征是否是进程在运行时所必需的和不可改变的呢？5.1.1常规存储管理方式的特征和局部性局部性原理在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内5.1.1常规存储管理方式的特征和局部性局部性原理表现在两个方面时间局限性：如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作空间局限性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行5.1.1常规存储管理方式的特征和局部性虚拟存储器的基本工作情况先部分装入，让程序执行起来缺页(段)中断处理置换5.1.2虚拟存储器的定义和特征定义具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中特征多次性对换性虚拟性5.1.3虚拟存储器的实现方法建立在离散分配的存储管理方式原因分页请求系统请求分段系统1.分页请求系统硬件支持请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求OS将所缺的页调入内存地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。软件实现请求调页的软件和实现页面置换的软件2.请求分段系统硬件支持请求分段的段表机制缺段中断机构地址变换机构软件实现请求调段的软件和实现段置换的软件outline5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4抖动与工作集5.5请求分段存储管理方式5.2请求分页存储管理方式相对简单，目前最为常用的一种实现虚拟存储器的方式5.2.1请求分页中的硬件支持5.2.2请求分页中的内存分配5.2.3页面调入策略5.2.1请求分页中的硬件支持1.页表页号物理块号状态位P访问字段A修改位M外存地址2.缺页中断机构在指令执行期间产生和处理中断一条指令在执行期间，可能产生多次缺页中断3.地址变换机构图4-25请求分页中的地址变换过程5.2.2内存分配策略和分配算法最小物理块数的确定内存分配策略物理块的分配算法5.2.2内存分配策略和分配算法最小物理块数的确定物理块的分配策略收到多方面的限制考虑：性能进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。5.2.2内存分配策略物理块的分配策略固定分配局部置换固定分配全局置换可变分配全局置换可变分配局部置换思考：页错误率的变化5.2.2物理块分配算法物理块的分配算法平均分配算法：貌似公平按比例分配算法考虑优先权的分配算法5.2.3页面调入策略何时从何处调入页面何时预调页策略、请求调页何处系统拥有足够的对换区空间系统缺少足够的对换区空间UNIX方式outline5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法

5.4抖动与工作集5.5请求分段存储管理方式5.3页面置换算法需要置换的情况？不适当的算法可能会导致进程发生抖动追求最低的页错误率5.3.1最佳置换算法和先进先出置换算法5.3.2最近最久未使用和最少使用置换算法5.3.3Clock置换算法5.3.4页面缓冲算法5.3.5访问内存的有效时间需要页置换的情况页置换过程页置换算法通过运行一特殊字符串（引用串，referencestring）来检验算法，计算其页错误率为了讨论页转换算法，将采用以下引用串，而可用帧的数量为37,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1页错误与帧数量关系图最佳页置换7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1页错误率最低，没有Belady异常缺陷？FIFO每个页记录进入内存的时间，当必须置换一页时，将选择最旧的页7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1Referencestring:1,2,3,4,1,2,5,1,2,3,4,53frames(3pagescanbeinmemoryatatimeperprocess)4framesBelady’s

Anomaly1231234125349pagefaults1231235124510pagefaults443一个采用FIFO置换引用串的页错误曲线最近最久未使用置换(LRU)使用“最近的过去”作为“最近的将来”的预测，置换最长时间没有使用的页。701203042303212017012.LRU置换算法的硬件支持1)寄存器:为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为2)栈图4-29用栈保存当前使用页面时栈的变化情况最少使用(LFU)置换算法为内存中的每个页面设置一个移位寄存器，记录页面被访问的频率被访问时，最高位置1，每隔一段时间右移4.7.3Clock置换算法1.简单的Clock置换算法图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的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。

(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。5.3.4页缓冲算法影响页面换入换出效率的若干因素页面置换算法写回磁盘的频率读入内存的频率页面缓冲算法PBA空闲页面链表修改页面链表5.3.5访问内存的有效时间

outline5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4抖动与工作集5.5请求分段存储管理方式5.4抖动与工作集5.4.1多道程序度与抖动5.4.2工作集5.4.3抖动的预防方法5.4.1多道程序度与“抖动”多道程序度与处理机的利用率5.4.1多道程序度与“抖动”产生抖动的原因同时在系统中运行的进程太多进程频繁缺页系统中排队等待页面调入调出的进程数目增加不能做有效工作5.4.2工作集工作集的基本概念进程发生缺页率的时间间隔与进程所获得的物理块数有关上限、下限局部性原理活跃页面5.4.2工作集工作集的定义在某段时间间隔Δ，进程实际所要访问页面的集合虽然程序只需要少量几页在内存便可运行，但为了较少产生缺页，应将程序的全部工作集装入到内存中只能用最近的过去作为将来某段时间内行为的近似工作集记为w(t,Δ)Δ称为工作集的窗口尺寸二元函数，是Δ的非降函数w(t,Δ)⊆w(t,Δ+1)5.4.3“抖动”的预防方法采用局部置换策略把工作集算法融入到处理机调度中调度程序从外存调入作业之前，必须先检查每个进程在内存的驻留页面是否足够多利用L=S准则调节缺页率L为缺页之间的平均时间，S为平均缺页服务时间L>S说明很少缺页，L<S缺页频繁,L与S接近时，磁盘和处理机利用率最高选择暂停的进程多道程序度偏高时，可以暂停一些正在活动的进程考虑一个请求调页系统，它采用全局置换策略和平均分配内存块的算法。如果在系统中测得如下的CPU和对换空间利用率，请问能否用增加多道程序的度数来增加CPU的利用率？为什么？(1)CPU利用率为13%，盘利用率为97%；(2)CPU利用率为87%，盘利用率为3%；(3)CPU利用率为13%，盘利用率为3%；

outline5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4抖动与工作集5.5请求分段存储管理方式5.5请求分段存储管理方式5.5.1请求分段的硬件支持5.5.2分段的共享与保护5.5.1请求分段中的硬件支持1.段表机制段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址2.缺段中断机构图4-31请求分段系统中的中断处理过程3.地址变换机构图4-32请求分段系统的地址变换过程5.5.2分段的共享与保护1.共享段表图4-33共享段表项2.共享段的分配与回收1)共享段的分配在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段。2)共享段的回收当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该