第五章虚拟存储器.

东北农业大学王艳操作系统原理Page2第五章虚拟存储器5.1虚拟存储器概述5.1.1常规存储管理方式的特征和局部性原理将作业全部装入内存后才能运行有的作业大，无法运行内存容量小有大量作业，少数能运行物理增加逻辑扩充1常规存储器管理方式的特征（1）一次性（2）驻留性2局部性原理（1）时间局部性（2）空间局部性Page33虚拟存储器的基本工作情况（1）将少数页面或段装入内存（2）若访问的页或段不在内存，则发出中断请求（3）将需要的页面调入内存（4）若页面已满，则调用页（段）的置换功能第五章虚拟存储器5.1虚拟存储器概述5.1.1常规存储管理方式的特征和局部性原理Page41虚拟存储的定义（1）具备请求调入功能和置换功能（2）从逻辑上对内存容量加以扩充（3）逻辑容量=内存容量+外层容量（4）速度接近于内存（5）成本接近于外存第五章虚拟存储器5.1虚拟存储器概述5.1.2虚拟存储器的定义和特征Page52虚拟存储的特征（1）多次性（2）对换性（3）虚拟性第五章虚拟存储器5.1虚拟存储器概述5.1.2虚拟存储器的定义和特征Page61分页请求系统（1）允许装入少数页，便启动（2）再利用请求调入和页面置换（3）置换以页面为单位（4）硬件支持：页表机制、缺页中断机构、地址变换机构5.1.3虚拟存储器的实现第五章虚拟存储器5.1虚拟存储器概述（5）软件支持：实现请求调页的软件、实现页面置换的软件Page72请求分段系统（1）允许装入少数段，便启动（2）再利用请求调入和段的置换（3）置换以段为单位（4）硬件支持：段表机制、缺段中断机构、地址变换机构5.1.3虚拟存储器的实现第五章虚拟存储器5.1虚拟存储器概述（5）硬件支持：实现请求调段的软件、实现段置换的软件Page8第五章虚拟存储器虚拟存储请求调入置换功能请求分段系统：段分页请求系统：页虚拟存储的特征多次性对换性虚拟性Page9第五章虚拟存储器5.2请求分页存储管理方式1请求页表机制5.2.1请求分页中的硬件支持（1）P:记录该页是否已调入内存—程序访问时参考（2）A：记录被访问的次数—选择换出页面时参考（3）M：记录该页是否被修改过—置换页面时参考页号物理块号状态位P访问字段A修改位M外存地址（4）外存地址：块号—供调入该页时参考Page102缺页中断机构（1）过程保护CPU环境分析中断原因缺页中断处理程序恢复CPU环境出页：实存→辅存入页：辅存→实存抖动：频繁反复入页或出页第五章虚拟存储器5.2请求分页存储管理方式5.2.1请求分页中的硬件支持Page112缺页中断机构（2）不同＊在指令执行期间产生和处理中断信号＊一条指令在执行期间可能产生多次缺页中断3地址变换机构分页地址变换机构+虚拟功能第五章虚拟存储器5.2请求分页存储管理方式5.2.1请求分页中的硬件支持Page12第五章虚拟存储器3地址变换机构缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号＞页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是Page13最小物理块的确定5.2.2请求分页中的内存分配1最小物理块数的确定（1）最小物理块（2）与计算机硬件结构有关（3）直接寻址→2，间接寻址→3物理块的分配策略物理块的分配算法第五章虚拟存储器5.2请求分页存储管理方式Page142内存分配策略内存分配：固定、可变置换：全局、局部（1）固定分配局部置换＊每个进程分配一定数目的物理块，且运行期间固定不变＊发现缺页，从该进程页面中选取一个换出＊分配多少个很难确定：太少，缺页率高；太多，资源浪费5.2.2请求分页中的内存分配第五章虚拟存储器5.2请求分页存储管理方式Page152内存分配策略（2）可变分配全局置换＊每个进程分配一定数目的物理块，留空闲块＊缺页时，调入页到空闲块，换页（任意进程的页）＊导致部分进程缺页率明显升高5.2.2请求分页中的内存分配第五章虚拟存储器5.2请求分页存储管理方式Page162内存分配策略（3）可变分配局部置换＊每个进程分配一定数目的物理块，留空闲块＊缺页时，从自己块中换页＊缺页率高，则分配物理块；缺页率低，则回收物理块5.2.2请求分页中的内存分配第五章虚拟存储器5.2请求分页存储管理方式Page173物理块的分配算法（固定分配策略）（1）平均分配算法＊平均分配给进程＊不公平，未考虑进程大小＊200页：20块；10页：20块5.2.2请求分页中的内存分配第五章虚拟存储器5.2请求分页存储管理方式Page183物理块的分配算法（固定分配策略）（2）按比例分配＊根据进程大小按比例分配＊n个进程，页面数Si，页面总和为S，可用块数m，每个进程分到的物理块数为bi。则bi=（Si/S）Xm（3）考虑优先权分配算法＊重要紧迫作业分配较多的内存空间＊内存分两部分，一部分按比例，一部分按优先权分配5.2.2请求分页中的内存分配第五章虚拟存储器5.2请求分页存储管理方式Page191何时调入页面（1）预调页策略（2）请求调页策略2从何处调入页面（1）系统拥有足够的对换区：全部从对换区调入所需页面5.2.3页面调入策略第五章虚拟存储器5.2请求分页存储管理方式（2）系统缺少足够的对换区：不会被修改的文件，从文件区可能被修改的，对换区（3）UNIX方式：未运行过的，文件区，反之在对换区Page203页面调入过程（1）页面未在内存时，则向CPU发出缺页中断（2）查找新页，有内存，则调入内存；内存满，则换页（3）若页面未被修改过，则不必写回磁盘，否则写回磁盘5.2.3页面调入策略第五章虚拟存储器5.2请求分页存储管理方式（4）修改快表Page214缺页率（1）进程逻辑空间n页，内存物理块m（m≤n）（2）访问页面成功的次数为S，访问页面失败的次数为F（3）访问页面的总次数为A=S+F5.2.3页面调入策略第五章虚拟存储器5.2请求分页存储管理方式（4）缺页率f=F/A（5）影响缺页率因素：页面大小、物理块数、页面置换算法、程序固有特性。Page22第五章虚拟存储器5.3页面置换算法目的：确定在诸多页面中淘汰哪个页面5.3.1最佳置换算法和FIFO置换算法1最佳置换算法（1）选择以后永不使用的页面置换（2）例子目标：应具有较高的页面更换频率Page235.3.1最佳置换算法和FIFO置换算法1最佳置换算法70120304230321201701770701201203243203201701（3）理论上的算法，无法实现。评判其他算法的标准。第五章虚拟存储器5.3页面置换算法Page242先进先出算法（FIFO）70120304230321201701770701201231430023013712（3）进入内存的页面，按先后链成一个队列，并设置一个替换指针。（1）淘汰驻留内存时间最长的页面2304204230127027015.3.1最佳置换算法和FIFO置换算法第五章虚拟存储器5.3页面置换算法Page255.3.2最近最久未使用算法（LRU）1选择最近最长时间未被使用的页面70120304230321201701770701201203403032132107（3）过去和未来，没有必然联系，性能不稳定，需硬件支持（栈或寄存器）2例子402432102第五章虚拟存储器5.3页面置换算法Page265.3.3性能分析1优缺点（1）消除了主存容量限制，作业同时执行，提高了效率（2）页面调入调出增加I/O负担2缺页率S：成功访问页次数F：不成功访问页次数f：缺页率A=F+Sf=F/A缺页率越大，效率越低，算法越不合理第五章虚拟存储器5.3页面置换算法Page275.3.3性能分析3影响缺页率因素（1）局部化程度（2）页面大小（3）主存块数（4）调度算法第五章虚拟存储器5.3页面置换算法Page284例题（1）设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置换算法采用FIFO。缺页中断次数F=9缺页率f=9/12=75%第五章虚拟存储器5.3页面置换算法Page29（2）设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=4，置换算法采用FIFO。缺页中断次数F=10缺页率f=10/12=83%第五章虚拟存储器5.3页面置换算法Page30（3）设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置换算法采用LRU。缺页中断次数F=10缺页率f=10/12=83%第五章虚拟存储器5.3页面置换算法Page31（4）设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=4，置换算法采用LRU。第五章虚拟存储器5.3页面置换算法Page325练习（1）设有一作业调用次序如下：3502502101745041620115097203004002529若页面大小为100字，主存300字，求LRU与FIFO算法缺页率若页面大小为100字，主存400字，求LRU与FIFO算法缺页率若页面大小为50字，主存300字，求LRU与FIFO算法缺页率第五章虚拟存储器5.3页面置换算法Page336作业1（1）设某程序有460行，内存访问序列按以下顺序进行，10，35，104，170，73，309，185，245，434，364(1)设页面大小是一页100行，请给出访问顺序页面号(2)该程序可用内存是200行，采用FIFO算法，f为多少？(3)采用LRU算法，f为多少？(4)采用OPT算法，f为多少？第五章虚拟存储器5.3页面置换算法Page346作业1（2）内存访问序列按以下顺序进行，115，228，120，88，446，102，321，432，260，167，若第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，回答下列问题(1)按FIFO算法，将产生多少次缺页中断，依次淘汰的页号都是什么？缺页中断率多少？(2)按LRU算法，将产生多少次缺页中断，依次淘汰的页号都是什么？缺页中断率多少？第五章虚拟存储器5.3页面置换算法Page351多道程序度与处理机的利用率5.4.1多道程序度与“抖动”第五章虚拟存储器5.4抖动与工作集Page362产生“抖动”的原因5.4.1多道程序度与“抖动”第五章虚拟存储器5.4抖动与工作集系统中运行的进程太多分配给每一个进程的物理块太少频繁缺页，调进/调出进程数目增加CPU利用率急剧下降并趋于0Page371工作集的基本概念5.4.2工作集第五章虚拟存储器5.4抖动与工作集Page381工作集的概念5.4.2工作集第五章虚拟存储器5.4抖动与工作集（2）程序运行期间，对页面的访问是不均匀的（3）一段时间内局限于少部分页面，称为活跃页面（4）如果能预知某段时间间隔内要访问的页面，并调入内存，将大大降低缺页率（1）1968年Denning提出并推广Page392工作集的定义5.4.2工作集第五章虚拟存储器5.4抖动与工作集（1）所谓工作集，是指在某段时间间隔△里，进程实际所要访问的页面集合。（2）为了较少的产生缺页，应将程序的全部工作集装入内存中。（3）无法预知程序在不同时刻访问哪些页面，用程序的过去某段时间内的行为作为程序在将来某段时间内的行为近似。Page40第五章虚拟存储器5.4抖动与工作集（4）某进程在时间t的工作集记为w（t,△），其中△称为工作集的窗口尺寸。（5）可以将工作集定义为，进程在（t-△，t）中引用页面的集合。Page412工作集的定义5.4.2工作集第五章虚拟存储器5.4抖动与工作集（6）不同时间t的工作集大小不同，所含的页面数也不同。（7）工作集与窗口尺寸有关，是窗口尺寸的非降函数。w（t,△）⊆w（t,△+1）Page421采