《操作系统原理及实验（应用型本科） 教学课件 ppt 作者 石国华(4)》由会员分享，可在线阅读，更多相关《操作系统原理及实验（应用型本科） 教学课件 ppt 作者 石国华(4)（41页珍藏版）》请在金锄头文库上搜索。
1、07操作系统原理与实验,作者：郑增威,责任编辑：石国华 出版日期：2009年8月 IDPN：308-2008-00 课件章数：8,第五章 虚拟存储器管理,chap3,3,本章摘要,采用简单存储管理技术，将严重降低系统性能和内存利用率，从而显著地减少系统吞吐率。 为解决问题，引入虚拟存储器相关知识 虚拟存储器的硬件特征 使用分页、分段和段页式三者情况 操作系统中虚拟存储器机制的设计问题,chap3,4,分级存储体系,chap3,5,虚拟存储器,扩大内存的物理地址空间 研制更大容量的内存 虚拟存储技术 虚拟存储器(Virtual Memory) 使操作系统给用户提供一个比真实内存空间大得多的地址空
2、间。 虚拟存储器并不是实际的内存，它的大小比内存空间大得多，是操作系统对逻辑内存的扩充。,chap3,6,局部性原理,程序在执行时将呈现出局部性规律，即在一个较短时间内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。 最重要的是90/10局部性规则：程序花费90%的执行时间运行指令集中10%的指令代码。 时间局部性：如果某个参数被引用，那它不久将再次被引用。 空间局部性：如果某一参数被引用，则它附近的参数不久也将被引用。,chap3,7,chap3,8,虚拟存储器特征,虚拟扩充 虚拟存储器不是扩大物理内存空间，而是扩充逻辑内存容量。 用户编程时所用到的地址空间可以远大于
3、实际内存的容量。 部分装入： 每个进程不是全部一次性地装入内存，而是分为若干部分分批按需加载。 离散分配： 一个进程分成多个部分，它们没有被全部装入内存。 装入内存的那部分也不必占用连续的内存空间。 多次交换： 在一个进程运行期间，它所需的全部程序和数据分成多次调入内存。 每次调入一部分，只解决当前需要，而在内存的那些暂时不被使用的程序和数据，可以换出到外存的交换区；甚至可以把暂时不能使用的进程在内存的全部映像都换出到交换区，以腾出尽可能多的内存空间供可运行进程使用。 被调出的程序和数据在需要时可以重新调入内存中。,chap3,9,虚拟分页存储管理,虚拟分页存储管理建立在简单分页存储管理系统基
4、础上 基本思想是： 当一个进程的部分页面在内存时就可调度运行； 在运行的过程中若用到的页面不在内存中，则将它们动态换入内存。 减少了交换时间和所需内存数量， 增加加载到内存的进程道数。,chap3,10,硬件支持,系统必须提供一定的硬件支持 一定数量的内存和外存 页表机制 缺页中断机构 地址变换机构。,chap3,11,页表机制,虚拟分页存储管理方式建立在简单分页技术基础上 需在页表中添加若干项，作为进程换进、换出时的参考。 态位：用于表示该页当前是否在内存中。 引用位：用于记录最近对该页是否访问，无论读或写，在访问该页时都会修改引用位。发生缺页时，引用位中的数据作为置换算法选择换出页面的参考
5、。 修改位：表示该页在调入内存后是否被修改。 外存地址：用于表示该页在外存中的地址，供调入该页时使用。,chap3,12,缺页中断机构,一旦发现所访问的页面不在内存中，立即产生中断信号，随后转入缺页中断处理程序进行相应的处理。 缺页中断处理过程包括 保存CPU环境 分析中断原因 转入缺页中断处理程序 恢复CPU环境 缺页中断处理由硬件和软件共同实现的。,chap3,13,缺页中断的处理,chap3,14,两级页表和多级页表,现代计算机系统都支持虚拟存储器管理技术 ，页表就变得非常大，要占用大量的内存空间 。 通过以下两个方面来解决该问题： 对页表所需的内存空间，采用离散分配方式来解决难以找到一
6、块连续的大内存空间的问题； 只将当前需要的部分页表项调入内存，其余的页表项仍保存在磁盘上，需要时再将它们调入内存。,chap3,15,两级页表（Two-Level Page Table）,二级页表逻辑地址结构 地址转换的方法是： 利用外层页号p1检索外层页表，从中找到相应内层页表的基址； 再利用p2作为该内层页表的索引，找到该页面在内存的物理块号； 用该物理块号和页内地址d拼接起来，形成访问内存的物理地址,chap3,16,chap3,17,两级页表的地址转换,chap3,18,反置页表,为了避免页表占用过多地址空间，也可以采用反置页表(Inverted Page Table)。 一般页表的表
7、项是按照页号进行排序，页表项中的内容是物理块号。 反置页表是为每一个物理块设置一个页表项，并将它按物理块的号数排序，其中的内容是页号及其所属进程的标识符。 这样，系统中只有一个页表，每一个内存块对应唯一的表项,chap3,19,反置页表,chap3,20,利用反置页表进行地址变换,用进程标识符和页号去检索反置页表， 若找到与之匹配的表项，则该表项的序号就是该页在内存中的块号，块号与逻辑地址中的页内地址拼接起来就构成访问内存中的物理地址； 如果检索完整个页表，都没有找到匹配的表项，则表示该页此时尚未调入内存，对于具有请求调页功能的存储器系统，此时产生调页或缺页中断；若无此功能，则表示地址出错。,
8、chap3,21,反置页表,性能 减少页表所占用的内存， 增加了检索页表所耗费的时间。 Hash页表 用一个简单的Hash函数将逻辑地址的页号映射到Hash表，Hash表项中包括指向反置页表的指针。 通过对Hash表的检索，能够很快找到在反置页表中的相应页表项。 对Hash表的访问也增加了访问内存的次数：一次是访问Hash页表，另一次是访问反置页表。 为了改善性能，反置页表可以和快表一起使用。,chap3,22,页面置换算法,在进程运行过程中，若其所需要访问的页面不在内存中，则需将该页调入内存，但是如果此时内存没有空闲空间，为了保证进程能够正常地运行，系统必须将内存中的一个页面换出，但是将哪个
9、页面换出，则需要根据一定的算法来确定。,chap3,23,页面置换过程,找出所需页面在磁盘上的位置。 找出一个空闲物理块。如果有空闲块，就将该块分配给进程；如果没有空闲块，就用页面置换算法选择一个被替换的页面。将这个被置换的页面写入外存，并相应地修改页表和快表。 把所需页面读入物理块，修改页表和快表。 重新启动该进程。,chap3,24,最佳置换算法(OPT),该算法所选择的被淘汰页总是不再使用的，或者未来最长时间不再使用的页面。采用最佳置换算法可以保证获得最低的缺页率。 不过，该算法只是理论上的最优算法，实际上由于人们无法预知哪一个页面为未来最长时间内不再被访问的，因此该算法无法实现。 可以
10、利用该算法去评价其他算法。,chap3,25,FIFO页面踪迹分析,chap3,26,最近最久未使用算法(LRU),思想： 当需要置换一个页面时，选择在最近一段时间最久没有使用过的页面予以淘汰。 LRU算法效率相对较高。 实现比较复杂，它需要解决的问题有： 需要记录一个进程在内存中的各个页面有多久没有被进程访问； 如何快速查找最近最久未使用的页面。,chap3,27,LRU算法页面踪迹分析,chap3,28,时钟置换算法(Clock),chap3,29,改进的Clock算法,改进型Clock算法中，在页表项中增加了一个标识页面是否修改的状态位，即页表项中有两个状态位： 引用位A：页面是否被使用
11、 修改位M：页面是否被修改 根据引用位A和修改位M的取值，可把页面分为： 1类(A=0，M=0)，表示该页最近既没有被访问，又没有被修改。 2类(A=0，M=1)，表示该页最近未被访问，但已被修改。 3类(A=1，M=0)，表示该页最近被访问，但未被修改。 4类(A=1，M=1)，表示该页最近被访问，也被修改。,chap3,30,算法,当发生缺页时，该算法的执行过程分为以下三步： 从指针当前位置开始，循环扫描环形队列，寻找第一个A=0且M=0的页面，将该页面换出后结束扫描，返回。 如果循环一周都没有找到可以置换的页面，则继续循环扫描，将遇到的第一个A=0且M=1的页面置换出去，然后结束扫描，返
12、回。在扫描过程中，每扫描过的页面，都将其引用位A置为0。 如果第步也没有找到可置换的页，则重复和必能找到一个可置换的页面。,chap3,31,驻留集管理,驻留集 是一个进程加载到内存中的页面集合，驻留集尺寸或大小是指一个进程驻留在内存中的页面数量。 页面调入策略 请求调页策略 预先调页策略 驻留集管理 固定分配局部置换 可变分配全局置换 可变分配局部置换,chap3,32,固定分配局部置换,一种静态的分配策略，系统一旦给进程分配了可用的物理块后，该进程运行中不再增加新的物理块。 如果遇到缺页的情况发生，系统就从该进程自己占用的物理块中置换一个页面。 这种方式可以保证分配给该进程的内存空间不变。
13、 但是难度在于如何确定分配给一个进程的物理块数量。如果少了，会频繁出现缺页，降低系统效率；如果太多，占用内存过多，必然导致内存中驻留的进程数减少，可能会造成CPU空闲或其他资源空闲，造成浪费。,chap3,33,可变分配全局置换,系统预留一部分可用物理块，其他的分配给各个进程。 当进程缺页时，系统从预留的物理块中分配一个给该进程。直到系统预留的页面都分配完了，系统再根据某种算法，从内存中选取某个页面置换出去。 这种方法易于实现，应用于多个操作系统。但是，这种方法也会导致某些被换出页面的进程缺页率增加。,chap3,34,可变分配局部置换,系统先预留一部分物理块，然后为每个进程分配一定数量的物理
14、块，当进程发生缺页时，只允许该进程从自己分配用的物理块中实施替换。 如果进程在运行中频繁地发生缺页，系统就分配部分物理块给该进程，直至该进程的缺页率下降到适当的程度； 反之，如果一个进程在运行期间，缺页率特别低，就可以适当的减少该进程所拥有的物理块，将部分物理块收回，归系统管理，但是不应引起该进程缺页率明显增加。,chap3,35,抖动,可变分配、局部置换策略的关键要素是用于确定驻留集大小的原则和变化的时间安排。 如果某一时刻驻留的进程太少，所有进程被阻塞的概率可能比较大，因而有许多时间都花费在交换上。 另一方面，如果驻留的进程太多，平均每个进程的驻留集大小将会不够用，就会频繁发生缺页，从而导
15、致系统抖动.,chap3,36,工作集,工作集概念是基于引用局部性原理的一种可变分配局部置换的方法。 一个进程在t时刻的工作集W(,t)是指在最近个虚拟时间（virtual time）内所访问过的页面集合。 任一时刻t，工作集W(,t)的大小是关于的非减函数；W(,t) 近似反映一个进程的局部性。,chap3,37,工作集策略存在的问题,过去并不总能预测将来。工作集的大小和成员都会随着时间而变化。 为每个进程真实地测量其工作集是不实际的，它需要为每个进程的每次页访问使用该进程的虚拟时间作时间标记，然后需要为每个进程维护一个基于时间顺序的页队列。 的最优值是未知的，并且在任何情况下都会变化。,c
16、hap3,38,虚拟分段存储管理,虚拟（或请求式）分段存储管理也可以为用户提供比主存实际容量大得多的虚拟存储空间。虚拟分段存储系统把进程的所有分段的副本都存放在外存中，当进程被调度投入运行时，首先把当前需要的一段或几段装入主存，在执行过程中访问到不在内存的段时再把它们动态装入。,chap3,39,段表,在段表中，除了一般的段表项外，还增加了一些内容： 存取方式：用于标识该段的存取属性。 引用位：用于记录最近对该段是否访问过，无论读或写，在访问该段时都会修改引用位。 修改位：表示该段在调入内存后是否被修改。由于内存中的每一段都在外存上保留一个副本，因此，如果未被修改，在置换该段时就不需要将该段写回到外存，减少系统的开销；若已被修改，则必须将该段重写到外存，保证外存中保存的始终为最新的副本。 外存地址：用于表示该段在外存中的地址，供调入该段时使用。 存在位：指示本段是否已经调入内存。 增补位：进程在运行中是否添加了新内容，用于表明该段的长度变化情况。,chap3,40,地址变换机构,增加了缺段中断处理技术,chap3,41,缺段中断机制,在虚拟分段
