• 1. 第五章虚拟存储器管理
  • 2. 前面介绍的各种存储器管理方式,要求将一个作业全部装入内存后方能运行。于是出现了两种情况: 有的作业很大,所要求的内存空间超过内存总容量,作业不能被全部装入内存,致使该作业无法运行。 有大量作业要求运行,但内存容量不足以容纳所有作业,只能将少数作业装入内存使其运行,其他大量作业留在外存上等待。5.1.1 常规存储管理方式的特征和局部性原理
  • 3. 解决方法 (1)*增加内存容量。 (2)从逻辑上扩充内存容量 ----覆盖 ----对换 ----虚拟存储器5.1.1 常规存储管理方式的特征和局部性原理
  • 4. 1.常规存储管理的特征 一次性(指全部装入) 驻留性(指驻留在内存不换出) 上述两点是否有必要? 2、局部性原理 时间局部性:如循环执行 空间局部性:如顺序执行。5.1.1 常规存储管理方式的特征和局部性原理
  • 5. 3. 虚拟存储器的基本工作情况   基于局部性原理可知,应用程序在运行之前没有必要将之全部装入内存,而仅须将那些当前要运行的少数页面或段先装入内存便可运行,其余部分暂留在盘上。 5.1.1 常规存储管理方式的特征和局部性原理
  • 6. 5.1.2 虚拟存储器的定义和特征1、虚拟存储器定义 定义:具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储系统。 实质:以时间换空间,但时间牺牲不大。 逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存速度,而每位的成本却又接近于外存。可见,虚拟存储技术是一种性能非常优越的存储器管理技术,故被广泛地应用于大、 中、 小型机器和微型机中。
  • 7. 2、虚拟存储器的特征 多次性:一个作业被分成多次调入内存运行 对换性:允许在作业的运行过程中进行换进、换出。 虚拟性:能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。 虚拟性以多次性和对换性为基础;多次性和对换性又必须建立在离散分配的基础上。5.1.2 虚拟存储器的定义和特征
  • 8. 5.1.3 虚拟存储器的实现方式需要动态重定位 一、请求分页系统 在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。 需硬件: (1)请求分页的页表机制 (2)缺页中断 (3)地址变换机构 需软件:请求调页功能和页置换功能的软件。
  • 9. 5.1.2 虚拟存储器的实现方式二、请求分段系统 在分段系统的基础上,增加了请求调段功能、分段置换功能所形成的段式虚拟存储器系统。 需硬件: (1)请求分段的页表机制 (2)缺段中断 (3)地址变换机构 需软件:请求调段功能和段置换功能的软件。
  • 10. 5.2 请求分页存储管理5.2.1 请求分页中的硬件支持 1. 页表机制 页号 物理块号 状态位P 访问字段A 修改位M外存地址 指示该页是否已调入内存记录本页在一段时间内被访问的次数,或记录本页最近已有多长时间未被访问,供选择换出页面时参考该页在调入内存后是否被修改过,供置换页面时参考指出该页在外存上的地址,供调入该页时参考
  • 11. 2. 缺页中断机构 与一般中断相比的区别: 1、一般中断在指令执行完后,检查是否有中断;缺页中断是在指令执行期间 2、一条指令在执行期间,可能产生多次缺页中断TO B 指令 copy A A: B:页面654321
  • 12. 3. 地址变换机构
  • 13. 5.2.2 内存分配策略和分配算法进程应获得的最少物理块数与计算机的硬件结构有关,取决于指令的格式、 功能和寻址方式。 如: Mov A, [B] 允许间接寻址:则至少要求3个物理块。 在请求分页系统中,为进程分配内存时,将涉及以下三个问题: 1. 最小物理块数的确定
  • 14. 5.2.2 内存分配策略和分配算法2. 物理块的分配策略 内存分配策略:固定和可变分配策略 置换策略:全局置换和局部置换 固定分配局部置换(Fixed Allocation, Local Replacement) 缺点:难以确定固定分配的页数(少:置换率高/多:浪费) 2) 可变分配全局置换(Variable Allocation, Global Replacement) 3) 可变分配局部置换(Variable Allocation, Local Replacement) 根据进程的缺页率进行页面数调整,进程之间相互不会影响
  • 15. 5.2.2 内存分配策略和分配算法3. 物理块分配算法 1) 平均分配算法 将系统中所有可供分配的物理块,平均分配给各个进程。 缺点:未考虑各进程本身的大小。
  • 16. 5.2.2 内存分配策略和分配算法2) 按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程,每个进程的页面数为Si,则系统中各进程页面数的总和为: 又假定系统中可用的物理块总数为m,则每个进程所能分到的物理块数为bi,将有: b应该取整,它必须大于最小物理块数。
  • 17. 5.2.2 内存分配策略和分配算法3) 考虑优先权的分配算法  在实际应用中,为了照顾重要的、急迫的作业尽快完成,应为它分配较多的内存空间。 方法:一部分按比例分配给各进程;另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程。
  • 18. 5.2.3 页面调入策略 1.调入页面的时机 (1)请调(demand paging) 发生缺页中断时调入(较费系统开销) (2)预调(prepaging) 将要访问时调入(根据程序顺序行为,不一定准)(根据空间局部性,目前:成功率≤50%) 预调必须辅以请调。 首次:预调页; 运行时:请求调页。
  • 19. 5.2.3 页面调入策略 2.确定从何处调页 在请求分页系统中,通常将外存分成了文件区和对换区,文件区按离散分配方式存放文件,对换区按连续分配方式存放对换页。 对换区:系统有足够的对换区空间,运行前可将与进程相关的文件从文件区复制至对换区,以后缺页时,全部从对换区调页。 文件区:系统没有足够的对换区空间,凡是不会被修改的文件,每次都直接从文件区调页,换出时不必换出。
  • 20. 5.2.3 页面调入策略 文件区、对换区:系统没有足够的对换区空间,对可能会修改的文件第一次调页直接从文件区,换出时换至对换区,以后从对换区调页。 UNIX方式:凡未运行过的页面均从文件区调页,运行过的页面和换出的页面均从对换区调页。
  • 21. 5.2.3 页面调入策略 3.页面调入过程 每当程序所要访问的页面未在内存时,便向CPU发出一缺页中断,中断处理程序首先保留CPU环境,分析中断原因后, 转入缺页中断处理程序。该程序通过查找页表,得到该页在外存的物理块后, 如果此时内存能容纳新页,则启动磁盘I/O将所缺之页调入内存,然后修改页表。如果内存已满,则须先按照某种置换算法从内存中选出一页准备换出;如果该页未被修改过,可不必将该页写回磁盘;但如果此页已被修改, 则必须将它写回磁盘,然后再把所缺的页调入内存,并修改页表中的相应表项,置其存在位为“1”,并将此页表项写入快表中。在缺页调入内存后,利用修改后的页表, 去形成所要访问数据的物理地址,再去访问内存数据。
  • 22. 保留CPU现场内存满吗?将一页从外存换入内存OS命令CPU从外存读缺页启动I/O硬件Y从外存中找到缺页选择一页换出该页被修改否?将该页写回外存修改页表NYN
  • 23. 补充:抖动:刚被淘汰出内存的页面,过后不久又要访问它,需要再次将其调入,而该页调入内存后不入又再次被淘汰出内存,然后又要访问它,如此反复,使得系统把大部分时间用在了页面的调进换出上,而几乎不能完成任何有效的工作,这种现象称为抖动(又称颠簸)。 4.8.1 最佳置换算法和先进先出置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面,将是以后永不使用的, 或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法,通常可保证获得最低的缺页率。5.3 页置换算法
  • 24. 【例】假定系统为某进程分配了三个物理块, 并考虑有以下的页面号引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 5.3.1 最佳置换算法和先进先出置换算法7F7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1引用序列缺页标志70F701F201F201203F203243F243243203F203203201F201201201701F701701缺页9次,总访问次数20次,缺页率9/20=45%技巧:检查后面的序列
  • 25. 2. 先进先出(FIFO)页面置换算法 Windows NT的请求分页存储管理系统采用易于实现的先进出的页面置换算法5.3.1 最佳置换算法和先进先出置换算法7F7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1引用序列缺页标志70F701F201F201231F230F430F420F423F023F023023013F012F012012712F702F701F缺页15次,总访问次数20次,缺页率15/20=75%技巧:从检查点向前检查图中哪个点持续最长就选哪个
  • 26. 5.3.2 最近最久未用LRU置换一、算法描述 将“最近的过去”,作为“最近的将来”。7F7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1引用序列缺页标志70F701F201F201203F203403F402F432F032F032032132F132102F102107F107107缺页12次,总访问次数20次,缺页率12/20=60%技巧:从检查点向前检查序列中哪个页离它最远就选哪个
  • 27. 2. LRU置换算法的硬件支持 1)寄存器 2) 栈 5.3.2 最近最久未用LRU置换
  • 28. 1)寄存器 为每个在内存中的页面配置一个移位寄存器,用来记录某进程在内存中各页的使用情况。移位寄存器表示为 R=Rn-1Rn-2Rn-3…R2R1R0 当进程访问某物理块时,要将相应寄存器的Rn-1(最高位)位置成1。此时,定时信号将每隔一定时间将寄存器右移一位。如果把n位寄存器的数看作一个整数,那么具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。5.3.2 最近最久未用LRU置换R0R1R2R3R4R5R6R7 R 实页0 0 0 1 0 1 1 11 0 0 1 1 1 1 00 1 1 0 1 0 1 10 1 0 1 0 1 0 11 0 0 0 1 0 0 00 1 0 1 0 1 0 11 0 0 1 1 0 0 10 1 0 0 1 0 0 01 2 3 4 5 6 7 8某进程具有8个页面时的LRU访问情况
  • 29. 2)栈 利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶。因此,栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号。设一进程访问页面的页面号序列为: 4,7,0,7,1,0,1,2,1,2,6 随着进程的访问,栈中页面号的变化情况:44477470040774071147100470114701224702114701227012665.3.2 最近最久未用LRU置换
  • 30. 【例】在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的字地址序列是:115,228,120,88,446,102,321,432,260,167,若该作业的第0页已经装入主存,现分配给该作业的主存共300字,页的大小为100字,请回答下列问题:   (1)按FIFO调度算法将产生 次缺页中断,依次淘汰的页号为 ,缺页中断率为?   (2)按LRU调度算法将产生 次缺页中断,依次淘汰的页号为 ,缺页中断率为? (3)按Optimal调度算法将产生 次缺页中断,依次淘汰的页号为 ,缺页中断率为?
  • 31. 地址序列:115,228,120,88,446,102,321,432,260,167 分别对应的页号: 1,2,1,0,4,1,3,4,2,1
  • 32. 【解】地址序列:115,228,120,88,446,102,321,432,260,167 分别对应的页号: 1,2,1,0,4,1,3,4,2,1,则: (1)按FIFO调度算法将产生5次缺页中断; 依次淘汰的页号为:0,1,2; 缺页中断率为:5/10=50% (2)按LRU调度算法将产生6次缺页中断; 依次淘汰的页号为:2,0,1,3; 缺页中断率为:6/10=60%
  • 33. 5.3.3 clock置换1. 简单的Clock置换算法 每页设置一位访问位,内存中的所有页链接成一个循环队列; 循环检查各页面的使用情况,访问位为“0”,选择该页淘汰;访问位为“1”,复位访问位为“0”,查询指针前进一步。 又称为“最近未使用”置换算法(NRU)
  • 34. 5.3.3 clock置换入口查寻指针前进一步,指向下一个表目页面访问位=0?选择该页面淘汰是返回置页面访问位=“0”否块号页号访问位指针0124034215650711替换指针
  • 35. 5.3.3 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): 最近已被访问且被修改,该页可能再被访问。
  • 36. 执行过程 访问位A,修改位M共同表示一个页面的状态 四种状态:00 01 10 11 三轮扫描: 第一轮:查找00页面,未找到,下一步; 第二轮:查找01页面,A位复位为“0”,未找到,下一步; 第三轮:查找10页面,未找到,重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页。5.3.3 clock置换
  • 37. 5.3.4 其它置换算法1)最少使用(LFU: Least Frequently Used)置换算法 选择到当前时间为止被访问次数最少的页面被置换; 每页设置访问计数器,每当页面被访问时,该页面的访问计数器加1; 发生缺页中断时,淘汰计数值最小的页面,并将所有计数清零;
  • 38. 5.3.4 其它置换算法2)页面缓冲算法(PBA: Page Buffering Algorithm) 它是对FIFO算法的发展,通过被置换页面的缓冲,有机会找回刚被置换的页面; 被置换页面的选择和处理:用FIFO算法选择被置换页,把被置换的页面放入两个链表之一。 如果页面未被修改,就将其归入到空闲页面链表的末尾 否则将其归入到已修改页面链表。
  • 39. 5.3.4 其它置换算法需要调入新的物理页面时,将新页面内容读入到空闲页面链表的第一项所指的页面,然后将第一项删除(从空闲链表摘下)。 空闲页面和已修改页面,仍停留在内存中一段时间,如果这些页面被再次访问,只需较小开销,而被访问的页面可以返还作为进程的内存页。 当已修改页面达到一定数目后,再将它们一起调出到外存,然后将它们归入空闲页面链表,这样能大大减少I/O操作的次数。
  • 40. 由于请求分页式虚拟存储器系统的性能优越,在正常运行情况下,它能有效地减少内存碎片,提高处理机的利用率和吞吐量,故是目前最常用的一种系统。但如果在系统中运行的进程太多,进程在运行中会频繁地发生缺页情况,这又会对系统的性能产生很大的影响,故还须对请求分页系统的性能做简单的分析。 5.4  “抖动”与工作集
  • 41. 1. 多道程序度与处理机的利用率   由于虚拟存储器系统能从逻辑上扩大内存,这时,只需装入一个进程的部分程序和数据便可开始运行,故人们希望在系统中能运行更多的进程,即增加多道程序度,以提高处理机的利用率。但处理机的实际利用率却如图5-9中的实线所示。 5.4.1 多道程序度与“抖动”
  • 42. 图5-9 处理机的利用率5.4.1 多道程序度与“抖动”
  • 43. 2. 产生“抖动”的原因   发生“抖动”的根本原因是,同时在系统中运行的进程太多,由此分配给每一个进程的物理块太少,不能满足进程正常运行的基本要求,致使每个进程在运行时,频繁地出现缺页,必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然,对磁盘的有效访问时间也随之急剧增加,造成每个进程的大部分时间都用于页面的换进/换出,而几乎不能再去做任何有效的工作,从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。5.4.1 多道程序度与“抖动”
  • 44. 1. 工作集的基本概念   进程发生缺页率的时间间隔与进程所获得的物理块数有关。图5-10示出了缺页率与物理块数之间的关系。 5.4.2 工作集
  • 45. 图5-10 缺页率与物理块数之间的关系5.4.2 工作集
  • 46. 2. 工作集的定义   所谓工作集,是指在某段时间间隔Δ里,进程实际所要访问页面的集合。Denning指出,虽然程序只需要少量的几页在内存便可运行,但为了较少地产生缺页,应将程序的全部工作集装入内存中。然而我们无法事先预知程序在不同时刻将访问哪些页面,故仍只有像置换算法那样,用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。 5.4.2 工作集
  • 47. 图5-11 窗口为3、4、5时进程的工作集5.4.2 工作集
  • 48. 1. 采取局部置换策略   在页面分配和置换策略中,如果采取的是可变分配方式,则为了预防发生“抖动”,可采取局部置换策略。 5.4.3 “抖动”的预防方法
  • 49. 2. 把工作集算法融入到处理机调度中   当调度程序发现处理机利用率低下时,它将试图从外存调入一个新作业进入内存,来改善处理机的利用率。 5.4.3 “抖动”的预防方法
  • 50. 3. 利用“L=S”准则调节缺页率   Denning于1980年提出了“L=S”的准则来调节多道程序度,其中L是缺页之间的平均时间,S是平均缺页服务时间,即用于置换一个页面所需的时间。如果是L远比S大,说明很少发生缺页,磁盘的能力尚未得到充分的利用;反之,如果是L比S小,则说明频繁发生缺页,缺页的速度已超过磁盘的处理能力。只有当L与S接近时,磁盘和处理机都可达到它们的最大利用率。理论和实践都已证明,利用“L=S”准则,对于调节缺页率是十分有效的。5.4.3 “抖动”的预防方法
  • 51. 4. 选择暂停的进程   当多道程序度偏高时,已影响到处理机的利用率,为了防止发生“抖动”,系统必须减少多道程序的数目。 5.4.3 “抖动”的预防方法
  • 52. 5.5 请求分段存储管理方式5.5.1 请求分段中的硬件支持1. 段表机制段名 段长 段的基址 存取方式 访问字段A 修改位M 存在位P 增补位 外存始址 标志本分段的存取属性记录该段被访问的频繁程度(与分页相应字段同)该段在调入内存后是否被修改过,供置换时参考指示本段是否已调入内存,供程序访问时参考本段在运行过程中,是否做过动态增长本段在外存中的起始地址
  • 53. 2. 缺段中断机构 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗?从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足?空区拼接,以形成一个合适的空区淘汰一个或几个实段,以形成一个合适空区否否是是
  • 54. 3. 地址变换机构 访问[s][w]W≤段长?符合存取方式?段S在主存?修改访问字段,如写访问,置修改位=1形成访问主存地址(A)=(主存始址)+(位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否
  • 55. 5.5.2 分段的共享与保护1.共享进程计数。 2.存取控制字段。 3.段号:不同的进程可以使用不同的段号去共享段。一、共享段表(整个系统一张)段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制………………共享段表
  • 56. 5.5.2 分段的共享与保护二、共享段的分配与回收 1.分配: 第一次访问:分配内存,(1)增加共享段表;(2)修改进程段表。 第二次访问:(1)修改共享段表;(2)修改进程段表。 2.回收: (1)count=0 (2)count< >0
  • 57. 5.5.2 分段的共享与保护三、分段保护 1.越界检查 段号越界检查。 段内偏移越界检查。 2.存取控制检查。 R;R/W;E 3.环保护机构 (1)内环可访问外环数据; (2)外环可请求内环服务。
  • 58. 5.5.2 分段的共享与保护可以访问驻留在相同环或较低特权环中的数据; 可以调用驻留在相同环或较高特权环中的服务。
  • 59. 本章基础要点实现虚拟存储器的目的是:从逻辑上扩充主存容量。虚拟的基础是局部性原理,其基本含义是指令的局部性(时间局部性与空间局部性)。 在虚存管理中,虚拟地址空间是指逻辑地址空间,实地址空间是指物理地址空间;前者的大小受 的限制,而后者的大小受 的限制。机器的地址长度;物理内存大小。
  • 60. 本章基础要点在请求页式系统中,OPT是 ;LRU是 ;NRU是 ;LFU是 。最佳置换算法;最近最久未使用置换算法;最近未使用置换算法;最不经常使用置换算法。页式虚拟存储管理的主要特点是:不要求将作业同时全部装入到主存的连续区域。在请求分页存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,缺页中断的次数 :可能增加也可能减少。
  • 61. 本章基础要点在请求分页系统中,地址变换过程可能会因为 、 、 错误等原因而产生中断。 缺页、地址越界、访问权限错误。若页面置换算法选择不当,可能会引起系统抖动。在请求分段存储管理中,系统必须至少具有三种支持机构,分别为 :段表、缺段中断机构、地址变换机构。
  • 62. 1.什么叫虚拟存储器?答:根据程序执行的互斥性和局部性两个特点,我们允许作业装入的时候只装入一部分,另一部分放在磁盘上,当需要的时候再装入到主存,这样以来,在一个小的主存空间就可以运行一个比它大的作业。同时,用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说,用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说,好象计算机系统具有一个容量很大的主存储器,称为“虚拟存储器”。
  • 63. 2.叙述页式存储管理实现虚拟存储器的基本思想。答:基本思想是:只需将作业的全部信息作为副本存放在磁盘上,作业被调度投入到运行时,至少把第一页信息装入主存储器,在作业执行过程中访问到不在主存储器的页的时候,再把它们装入到主存。
  • 64. 【练习题2】1、假定系统为某进程分配了3个物理块,进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5,开始时3个物理块均为空,计算采用最佳置换页面淘汰算法时的缺页率?(7/12)页面走向123412512345物理块11111133物理块2222224物理块334555缺页缺缺缺缺缺缺缺解答如下表
  • 65. 【练习题2】解答如下表2、假定系统为某进程分配了3个物理块,进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5,开始时3个物理块均为空,计算采用先进先出页面淘汰算法时的缺页率?(9/12)页面走向123412512345物理块1111444555物理块222211133物理块33332224缺页缺缺缺缺缺缺缺缺缺
  • 66. 【练习题2】解答如下表3、假定系统为某进程分配了3个物理块,进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5,开始时3个物理块均为空,计算采用最近最久未使用页面淘汰算法时的缺页率?(9/12)页面走向123412512345物理块11114445333物理块2222111144物理块333322225缺页缺缺缺缺缺缺缺缺缺缺