《第6章 虚拟存储器管理ppt课件.ppt》由会员分享，可在线阅读，更多相关《第6章 虚拟存储器管理ppt课件.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 虚拟存储器管理第第6 6章章 虚拟存储器管理虚拟存储器管理操作系统（第四版）操作系统（第四版）第6章 虚拟存储器管理6.1 6.1 概述概述6.2 6.2 分页虚拟存储管理方式分页虚拟存储管理方式6.3 6.3 分段虚拟存储管理分段虚拟存储管理6.4 Linux6.4 Linux的内存管理的内存管理6.1 概述虚拟存储器就是使用虚拟技术从逻辑上对存储器进行扩充。虚拟存储器就是使用虚拟技术从逻辑上对存储器进行扩充。q概述概述 局部性原理局部性原理 一次性和驻留性严重地降低内存的利用率，显著地减一次性和驻留性严重地降低内存的利用率，显著地减少了系统吞吐量少了系统吞吐量 研究表明，程序在执行
2、过程中呈现局部性原理研究表明，程序在执行过程中呈现局部性原理 时间局部性时间局部性：一条指令被执行后，那么它可能很快会再一条指令被执行后，那么它可能很快会再次被执行次被执行 空间局部性空间局部性：若某一存储单元被访问，那么与该存储单若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问元相邻的单元可能也会很快被访问 局部性原理使得虚拟存储技术的实现成为可能。一个局部性原理使得虚拟存储技术的实现成为可能。一个程序特别是一个大型程序的一部分装入内存是可以运行的程序特别是一个大型程序的一部分装入内存是可以运行的6.1 概述虚拟存储器的特征虚拟存储器的特征可以把一个程序分多次装入内存，每次
3、装入当前运行需可以把一个程序分多次装入内存，每次装入当前运行需要使用的部分要使用的部分多次性多次性；在程序执行过程中，可以把当前暂不使用的部分换出内在程序执行过程中，可以把当前暂不使用的部分换出内存，若以后需要时再换进内存存，若以后需要时再换进内存交换性即非驻留性交换性即非驻留性；程序在内存中可分段存放，每一段是连续的程序在内存中可分段存放，每一段是连续的离散性离散性。虚拟存储器还有一个最重要的特征虚拟存储器还有一个最重要的特征虚拟性虚拟性，从逻辑，从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。内存容量。 6.1 概述 虚拟存储
4、器定义虚拟存储器定义 所谓所谓虚拟存储器虚拟存储器，是指仅把程序的一部分装入内存便，是指仅把程序的一部分装入内存便可运行程序的存储器系统。具体地说，所谓虚拟存储器是指可运行程序的存储器系统。具体地说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统扩充的一种存储器系统 虚拟存储器并非可以无限大，其容量受外存大小和指虚拟存储器并非可以无限大，其容量受外存大小和指令中地址长度两方面的限制令中地址长度两方面的限制6.2 分页虚拟存储器q分页虚拟存储管理分页虚拟存储管理 基本原理基本原理 分页虚拟存储管理方式
5、是在分页系统的基础上，分页虚拟存储管理方式是在分页系统的基础上，增加增加了请求调页功能、页面置换功能了请求调页功能、页面置换功能所形成的虚拟存储器系统。所形成的虚拟存储器系统。 在分页虚拟存储管理时使用的页表，是在原来页表的在分页虚拟存储管理时使用的页表，是在原来页表的基础上发展起来的，包括以下基础上发展起来的，包括以下内容内容：物理块号、状态位、访：物理块号、状态位、访问位、修改位、外存地址问位、修改位、外存地址 6.2 分页虚拟存储器 缺页中断机构缺页中断机构 每当要访问的页面不在内存时，便产生一缺页中断，请每当要访问的页面不在内存时，便产生一缺页中断，请求操作系统把所缺页面调入内存。，请
6、求操作系统把所缺页求操作系统把所缺页面调入内存。，请求操作系统把所缺页面调入内存。缺页中断作为中断，它同样需要经历诸如保护面调入内存。缺页中断作为中断，它同样需要经历诸如保护CPUCPU现场环境、分析中断原因、转入缺页中断处理程序进行现场环境、分析中断原因、转入缺页中断处理程序进行处理、恢复处理、恢复CPUCPU环境等几个步骤。环境等几个步骤。 缺页中断与与一般的中断的区别缺页中断与与一般的中断的区别 在指令执行期间产生和处理中断信号。在指令执行期间产生和处理中断信号。 一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间，可能产生多次缺页中断。6.2 分页虚拟存储器 地址变换机构地址
7、变换机构 在分页存储管理方式中的地址变换机构的基础上，增加在分页存储管理方式中的地址变换机构的基础上，增加了产生和处理缺页中断，以及从内存中换出一页等功能。具体了产生和处理缺页中断，以及从内存中换出一页等功能。具体过程：过程： - - 保存当前进程的保存当前进程的CPUCPU现场环境，从辅存中找到该页；现场环境，从辅存中找到该页； - - 查看当前内存是否有空闲空间调入该页，如果有则启动查看当前内存是否有空闲空间调入该页，如果有则启动I/OI/O，将该页由辅存调入内存，同时修改页表，再按分页存储，将该页由辅存调入内存，同时修改页表，再按分页存储管理方式的地址变换过程转换地址；如果内存已满，则按
8、照某管理方式的地址变换过程转换地址；如果内存已满，则按照某种算法选择一页作为淘汰页调出，腾出空间后再调入。当然如种算法选择一页作为淘汰页调出，腾出空间后再调入。当然如果被淘汰的页在内存中已经被修改过，则需将该页写回辅存。果被淘汰的页在内存中已经被修改过，则需将该页写回辅存。6.2 分页虚拟存储器 页面置换算法页面置换算法 如果内存空间己被装满而又要装入新页时，必须如果内存空间己被装满而又要装入新页时，必须按某种算法将内存中的一些页淘汰出去，以便调入新按某种算法将内存中的一些页淘汰出去，以便调入新页，这个工作称为页，这个工作称为“页面置换页面置换”。选择被淘汰页的方。选择被淘汰页的方法成为法成为
9、页面置换算法页面置换算法。6.2 分页虚拟存储器最佳置换算法最佳置换算法 算法：淘汰那些以后永不使用，或者是在最长时间内不再算法：淘汰那些以后永不使用，或者是在最长时间内不再被访问的页被访问的页 无法实现的，只能作为其它置换算法的衡量标准无法实现的，只能作为其它置换算法的衡量标准 6.2 分页虚拟存储器先进先出算法先进先出算法 算法：每次淘汰最先进入内存的页算法：每次淘汰最先进入内存的页 优点：简单，易于实现优点：简单，易于实现 缺点：效率不高，可能产生缺点：效率不高，可能产生“抖动抖动”现象现象 思考：如何实现？思考：如何实现？6.2 分页虚拟存储器最近最久未使用（最近最久未使用（LRULR
10、U）算法）算法 算法：淘汰那些在最近一段时间里最久未被使用的一页算法：淘汰那些在最近一段时间里最久未被使用的一页 LRULRU算法是较好的一个算法，但是开销太大，要求系统算法是较好的一个算法，但是开销太大，要求系统有较多的支持硬件有较多的支持硬件( (移位寄存器或栈）移位寄存器或栈）6.2 分页虚拟存储器实现方案：实现方案： - - 栈式算法栈式算法：在内存维护一张进程所有页的链表，表中各项：在内存维护一张进程所有页的链表，表中各项按访问时间先后排序，最近访问的页排在表头，最久末用的按访问时间先后排序，最近访问的页排在表头，最久末用的页排在表尾。每当要置换一页时，必须对链表中的各项进行页排在表
11、尾。每当要置换一页时，必须对链表中的各项进行修改。修改。 - - 改进改进使用链表时费时方法，可使用一个特殊硬件实现使用链表时费时方法，可使用一个特殊硬件实现LRULRU。 系统为每个在内存中的页面配置一个系统为每个在内存中的页面配置一个移位寄存器移位寄存器，可，可表示为表示为R=Rn-1Rn-2R=Rn-1Rn-2R3R2R1R3R2R1 当进程访问某页时，便将相应的寄存器的最高位（当进程访问某页时，便将相应的寄存器的最高位（Rn-Rn-1 1）置）置1 1；定时信号将每隔一定时间将寄存器右移一位。；定时信号将每隔一定时间将寄存器右移一位。 具有最小数的寄存器所对应的页面，就是最近最久未具有
12、最小数的寄存器所对应的页面，就是最近最久未使用的页。使用的页。6.2 分页虚拟存储器 利用一个特殊的栈来保存当前使用的各个页面的页面利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈中移出，将它压入栈顶。 栈底就是最近最久未使用页面的页面号。栈底就是最近最久未使用页面的页面号。 简单简单ClockClock置换算法（最近未使用算法置换算法（最近未使用算法NRCNRC） 算法：每页设置一个访问位，置换算法在选择一页淘算法：每页设置一个访问位，置换算法在选择一页淘汰时，只须检查其访问位
13、，如果是汰时，只须检查其访问位，如果是0 0，就选择该页换出；若，就选择该页换出；若为为1 1，则重新将它复，则重新将它复0 0 ，检查下一个页面。当检查到队列中，检查下一个页面。当检查到队列中的最后的最后个页面时，若其访问值仍为个页面时，若其访问值仍为1 1、则再返回到队首再、则再返回到队首再去检查第一个页面去检查第一个页面 该算法只能考虑该页面是否被访问过该算法只能考虑该页面是否被访问过 6.2 分页虚拟存储器图6-2 简单Clock置换算法置换流程置换流程6.2 分页虚拟存储器 改进型改进型ClockClock置换算法置换算法 算法：除了考虑到页面的使用情况外，还增加了置换代算法：除了考
14、虑到页面的使用情况外，还增加了置换代价，选择换出页面时，价，选择换出页面时，既要是未使用过的页面，又要是未被修既要是未使用过的页面，又要是未被修改过的页面改过的页面把同时满足两条件的页面作为首选被淘汰的页。把同时满足两条件的页面作为首选被淘汰的页。 该算法与简单该算法与简单ClockClock算法比较，可减少磁盘的算法比较，可减少磁盘的I/OI/O操作次操作次数数 ，但实现该算法本身的开销将有所增加，但实现该算法本身的开销将有所增加 具体算法：具体算法： 由访问位由访问位A A和修改位和修改位M M可以组合成可以组合成4 4种类型的页面：种类型的页面：6.2 分页虚拟存储器 1 1类（类（A=
15、0A=0，M=0M=0），表示该页最近既没有被访问、又没有），表示该页最近既没有被访问、又没有被修改，是最佳淘汰页。被修改，是最佳淘汰页。 2 2类（类（A=0A=0，M=1M=1），表示该页最近末被访问，但已被修改。），表示该页最近末被访问，但已被修改。并不是很好的淘汰页。并不是很好的淘汰页。 3 3类（类（A=lA=l，M=0M=0），最近已被访问，但未被修改，该页有），最近已被访问，但未被修改，该页有可能再被访问。可能再被访问。 4 4类（类（A=1A=1，M=1M=1），最近已被访问且被修改，该页可能再），最近已被访问且被修改，该页可能再被访问。被访问。 6.2 分页虚拟存储器 改进型
16、改进型ClockClock算法算法，其执行过程可分成以下三步：，其执行过程可分成以下三步： 从指针所指示的当前位置开始，扫描循环队列，寻找从指针所指示的当前位置开始，扫描循环队列，寻找A=0A=0，M=0M=0的第一类页面，将所遇到的第一个页面作为所选中的的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位淘汰页。在第一次扫描期间不改变访问位A A。 如果第一步失败，即查找如果第一步失败，即查找周后未遇到第周后未遇到第类页面，则类页面，则开始第二轮扫描，寻找开始第二轮扫描，寻找A=0A=0，M=1M=1的第二类页面，将所遇到的第的第二类页面，将所遇到的第一个这类页
17、面作为淘汰页，在第二轮扫描期间，将所有经过的一个这类页面作为淘汰页，在第二轮扫描期间，将所有经过的页面的访问位置页面的访问位置0 0。 如果第二步也失败，即未找到第二类页面，则将指针返如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置，并将所有访问位置回到开始的位置，并将所有访问位置0 0。然后，重复第一步，。然后，重复第一步，如果仍失败，必要时再重复第二步。如果仍失败，必要时再重复第二步。6.2 分页虚拟存储器内存分配策略和分配算法内存分配策略和分配算法最小物理块数最小物理块数 - - 最小物理块数是指能保证进程正常运行所需的最少物理块最小物理块数是指能保证进程正常运行所需的最少
18、物理块数。数。 - - 进程所需的最少物理块数与计算机的硬件结构有关，取决进程所需的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。于指令的格式、功能和寻址方式。 物理块的分配策略物理块的分配策略固定分配局部置换固定分配局部置换 - -基于进程的类型或根据程序员的建议，为每个进程分配基于进程的类型或根据程序员的建议，为每个进程分配一定数量的物理块，在整个运行期间都不再改变。一定数量的物理块，在整个运行期间都不再改变。 6.2 分页虚拟存储器 - - 如果进程在运行期间发现缺页，则只能在该进程在内存的如果进程在运行期间发现缺页，则只能在该进程在内存的n n个页面中选出一页换
19、出，然后在调入一页，保证分配给个页面中选出一页换出，然后在调入一页，保证分配给该进程的物理块数保持不变。该进程的物理块数保持不变。 - - 困难：难以确定为每个进程分配的物理块数，若太少，则困难：难以确定为每个进程分配的物理块数，若太少，则会频繁地出现缺页中断，降低了系统的吞吐量；若太多，会频繁地出现缺页中断，降低了系统的吞吐量；若太多，则必然使内存中驻留的进程数目减少，进而可能造成则必然使内存中驻留的进程数目减少，进而可能造成CPUCPU空间或其它资源的浪费，而且在实现进程交换时，会花费空间或其它资源的浪费，而且在实现进程交换时，会花费更多的时间。更多的时间。 6.2 分页虚拟存储器可变分配
20、全局置换可变分配全局置换 - - 先为系统中的每个进程分配一定数量的物理块，而操作先为系统中的每个进程分配一定数量的物理块，而操作系统本身也保留一个空闲物理块队列。系统本身也保留一个空闲物理块队列。 - - 当某个进程发现缺页时，由系统从空闲物理块队列中，当某个进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。仅当空闲物理块队列中的物理块用完时，操作系入其中。仅当空闲物理块队列中的物理块用完时，操作系统才从内存中选择一页调出，该页可能是系统中任一进程统才从内存中选择一页调出，该页可能是系统中任一
21、进程的页，的页， - - 会使被淘汰页的那个进程的物理块数减少，进而使其缺会使被淘汰页的那个进程的物理块数减少，进而使其缺页率增加。页率增加。 - - 最容易实现的一种物理块分配和置换策略。最容易实现的一种物理块分配和置换策略。 6.2 分页虚拟存储器可变分配局部置换可变分配局部置换 - - 进程的类型或根据程序员的要求，为每个进程分配一定进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块；但当某进程发生缺页时，只允许从该进程数目的物理块；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出。在内存的页面中选出一页换出。 - - 如果进程在运行中频繁地发生缺页中断，则系统须
22、再为如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至进程的缺页率减低到该进程分配若干附加的物理块，直至进程的缺页率减低到适当程度为止；反之，若一个进程在运行过程中的缺页率适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块，但不特别低，则此时可适当减少分配给该进程的物理块，但不应引起其缺页率的明显增加。应引起其缺页率的明显增加。 6.2 分页虚拟存储器物理块分配算法物理块分配算法 - - 平均分配算法平均分配算法: :将系统中所有可供分配的物理块，等分给将系统中所有可供分配的物理块，等分给各个的进程。各个的进程。 - -
23、 按比例分配算法按比例分配算法 根据进程的大小按比例分配物理块。根据进程的大小按比例分配物理块。 如果系统各进程页面数总和为如果系统各进程页面数总和为S,S,又假设又假设m m为内存空间可用为内存空间可用物理块数，则分配给进程物理块数，则分配给进程PiPi的物理块数的物理块数aiai为：为：aiaisi/Ssi/Sm m ai ai应取整，而且必须大于最小物理块数。应取整，而且必须大于最小物理块数。 - - 考虑优先权的分配算法考虑优先权的分配算法: :即根据进程的优先级别按比例分即根据进程的优先级别按比例分配内存物理块。配内存物理块。6.2 分页虚拟存储器调页策略调页策略 请求调页策略请求调
24、页策略 - - 当缺页中断发生时进行调度，即当访问某一页面而该页当缺页中断发生时进行调度，即当访问某一页面而该页面不在内存时由操作系统将其调入内存。面不在内存时由操作系统将其调入内存。 预调页策略预调页策略 - - 也称先行调度，是当缺页中断发生前进行调度，即当一也称先行调度，是当缺页中断发生前进行调度，即当一个页面即将被访问之前就将其调入内存。个页面即将被访问之前就将其调入内存。 - - 预调页可以节省进程因缺页中断而等待页面调入的时间。预调页可以节省进程因缺页中断而等待页面调入的时间。6.2 分页虚拟存储器 抖动问题抖动问题 进程的大部分时间，都用于页面的换进换出，而几乎不进程的大部分时间
25、，都用于页面的换进换出，而几乎不能再去做任何有效的工作，从而导致发生处理机利用率急剧下能再去做任何有效的工作，从而导致发生处理机利用率急剧下降，而趋于零的现象，我们称此时系统处于抖动状态。降，而趋于零的现象，我们称此时系统处于抖动状态。 产生抖动的原因产生抖动的原因 产生抖动的根本原因是，系统中进程的数量太多，因此分产生抖动的根本原因是，系统中进程的数量太多，因此分配给每个进程的物理块数量太少，使得每个进程在运行时频繁配给每个进程的物理块数量太少，使得每个进程在运行时频繁的发生缺页中断的发生缺页中断 工作集工作集 所谓工作集就是指在某段时间间隔所谓工作集就是指在某段时间间隔内，进程访问页面的内
26、，进程访问页面的集合。为了使进程有较低的缺页率，应在该段时间内把进程的集合。为了使进程有较低的缺页率，应在该段时间内把进程的全部工作集装入内存中全部工作集装入内存中6.2 分页虚拟存储器 抖动问题抖动问题 预防抖动的方法预防抖动的方法 采用局部置换策略采用局部置换策略 利用工作集算法防止抖动利用工作集算法防止抖动 利用利用“L=SL=S”准则调节缺页率准则调节缺页率 挂起某些进程挂起某些进程6.3 分段虚拟存储器q分段虚拟存储管理分段虚拟存储管理 基本原理基本原理 分段虚拟存储管理原理同分页虚拟存储管理原理一样，分段虚拟存储管理原理同分页虚拟存储管理原理一样，在程序运行前，不必调入所有分段，只
27、需先调入若干个分段便在程序运行前，不必调入所有分段，只需先调入若干个分段便可启动运行。当所访问的段不在内存中时，可请求操作系统将可启动运行。当所访问的段不在内存中时，可请求操作系统将所缺的段调入内存所缺的段调入内存 分段虚拟存储管理中的段表包括：段名、段长、段的基分段虚拟存储管理中的段表包括：段名、段长、段的基址、存取方式、访问位、修改位、存在位、增补位和外存地址址、存取方式、访问位、修改位、存在位、增补位和外存地址 6.3 分段虚拟存储器 缺段中断机构缺段中断机构 在分段虚拟存储管理系统中，如果访问的段不在内存中，在分段虚拟存储管理系统中，如果访问的段不在内存中，系统将产生一个缺段中断，请求
28、操作系统将该段调入到内存系统将产生一个缺段中断，请求操作系统将该段调入到内存 缺段中断和缺页中断一样缺段中断和缺页中断一样 ，但段是信息的逻辑单位，所，但段是信息的逻辑单位，所以不可能出现一条指令和一组信息被分割在两个段里的情况以不可能出现一条指令和一组信息被分割在两个段里的情况 段的动态链接段的动态链接 在分段虚拟存储管理中，每个程序模块构成独立的分段，且在分段虚拟存储管理中，每个程序模块构成独立的分段，且地址空间是二维的，因而为实现动链接创造了条件地址空间是二维的，因而为实现动链接创造了条件6.3 分段虚拟存储器6.3 分段虚拟存储器 段的共享段的共享 利用段的动态链接很容易利用段的动态链接很容易实现段的共享，一个共享段在实现段的共享，一个共享段在不同作业中可具有不同的段号不同作业中可具有不同的段号 设立一张共享段表对段的设立一张共享段表对段的共享进行集中管理共享进行集中管理 - - 可重入代码又称为可重入代码又称为“纯代纯代码码”是一种允许多个进程同时访问的是一种允许多个进程同时访问的代码。代码。