第5章虚拟存储器

《第5章虚拟存储器》由会员分享，可在线阅读，更多相关《第5章虚拟存储器（160页珍藏版）》请在金锄头文库上搜索。

1、第5章 虚拟存储器,5.0 交换技术与覆盖技术 5.1 虚拟存储器概述 5.2 请求分页存储管理方式 5.3 页面置换算法 5.4 抖动与工作集 5.5 请求分段存储管理方式,5.0 交换技术与覆盖技术,5.0.1 覆盖技术 覆盖(overlay)技术的目标是在较小的可用内存中运行较大的程序，常用于多道程序系统，与分区存储管理配合使用。 覆盖技术不需要任何来自操作系统的特殊支持，可以完全由用户实现，即overlay，是用户程序自己附加的控制。,1覆盖技术的原理 通常一个程序的几个代码段或数据段是按照时间先后来占用公共的内存空间的，它们装入时可以采用如下几种： (1) 将程序的必要部分(常用功能

2、)的代码和数据常驻内存。 (2) 将可选部分(不常用功能)在其他程序模块中实现，平时存放在外存中的覆盖文件中，在用到时才装入到内存。,(3) 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。 覆盖技术的原理如图5.1所示。,图5.1 覆盖技术原理,2覆盖技术的优缺点 覆盖技术使一个作业能够有效地利用内存，但是它有如下的缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加了编程复杂度；从外存装入覆盖文件，是以时间延长来换取空间节省的；各个作业占用的分区仍然存在着碎片。,5.0.2 交换技术 交换技术(swapping)最早应用于麻省理工学院的兼容分时系统CTSS中。 交换技术

3、用于多个程序并发执行的系统中。当某一个作业的存储空间不够时，可以将暂时不能执行的程序所占用的地址空间换出到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前处于就绪状态的程序。交换单位为整个进程的地址空间。交换技术常用于多道程序系统或小型分时系统中，可与分区存储管理配合使用。它又称作“对换”或“滚进/滚出(roll-in/roll-out)”。,程序暂时不能执行的可能原因是：处于阻塞状态，低优先级(确保高优先级程序先执行)。其处理方法同上。 如果将简单的交换技术加以发展，就可用于固定分区或者可变分区的存储管理技术中。在采用可变分区存储管理的多道程序设计中，当要运行一个高优先级的

4、作业而又没有足够的空闲内存时，可以按某一个算法从主存中换出一个或多个作业，腾出空间装入高优先级的作业，使之能够运行。在Windows操作系统中，就是利用交换技术运行多个任务的。,交换技术的优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构。 交换技术的缺点：对换入和换出的控制增加了处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。还存在两个问题：程序换入时的重定位问题；交换过程中传送的信息量特别大的问题。,5.1 虚 拟 存 储,5.1.1 虚拟存储管理的引入 虚拟存储(virtual memory)管理的基础是程序的局部性原理(p

5、rinciple of locality)。所谓局部性原理，是指程序在执行过程中的一个较短时期内，所执行的指令地址和指令的操作数地址分别局限于一定的区域，主要表现为：,(1) 时间局部性：指一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内。 (2) 空间局部性：指当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。,局部性原理具体体现在以下几方面： 程序中大部分是顺序执行的指令，少部分是转移和过程调用指令。 过程调用的嵌套深度一般不超过5层，因此执行的范围不超过这组嵌套的过程。 程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行

6、。 程序中存在相当多的对一定数据结构的操作，如数组操作，这些操作往往局限在较小范围内。,虚拟存储管理就是基于程序的局部性原理，利用大容量的磁盘作为后备，当作业要占用的内存空间不够大时，将作业的一部分暂时先放在磁盘上，当需要时再从磁盘上调入。 虚拟存储的基本原理是在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。,引入虚拟存储技术的好处是： 可在较小的可用内存中执行较大的用户程序。 可在内存中容纳更多程序并发执行。 不必影响编程时的程序结构(与覆盖技术比较)。 提供给用户可用的虚拟内存空间通常大于物理内存(real memory)。,在虚拟存储

7、器中,允许一个作业分多次调入内存。如果采用连续存储分配方式时，应将作业装入一个连续的内存区域中。为此，须事先为它一次性地申请足够的内存空间，以便将整个作业先后分多次装入内存。这不仅会使相当一部分内存空间都处于暂时或永久的空闲状态，造成内存资源的严重浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟存储器的实现，都毫不例外地建立在离散分配的存储管理方式的基础上。 虚拟存储技术分为三类：请求分页、请求分段和请求段页式存储管理。,5.2 请求分页存储管理方式 （虚拟页式存储管理） 1基本工作原理 在分页式存储管理中，必须一次性将所有的页面全部装入，有可能造成其他的作业无法装入，从而造成系统的性能下降。

8、,有三个问题必须解决： (1) 如果不把一个作业全部装入内存，那么该作业能否开始运行并运行一段时间呢？ (2) 在作业运行了一段时间之后，必然要访问没有装入的页面，也就是说，要访问的虚页不在内存，系统怎么发现呢？ (3) 如果系统已经发现某一个虚页不在内存，就应该将其装入，怎么装入呢？,答案是： (1) 程序在运行期间，往往只使用全部地址空间的一部分。 (2) 根据程序局部性原理，程序员在写程序的时候总是满足结构化的思想，使得程序具有模块化的特点。 (3) 使用缺页中断即可，而缺页中断是属于程序中断的。,2页表表项 在请求分页系统中所使用的主要数据结构仍然是页表，它对页式存储系统中的页表机制进

9、行了扩充，但其基本作用仍然是实现由用户地址空间到物理内存地址空间的映射。 为了实现请求分页式存储管理，必须对分页式存储管理中的地址变换机构进行扩充：除了页号和对应的物理块号外，还增加了存在位、修改位、外存地址和访问统计等，如图5.2所示。,图5.2 扩充的页表,驻留位 / 中断位,存在位(present bit)：用于指示该页是否已经调入了物理内存中。 修改位(modified bit)：表示该页调入内存之后是否被修改过。 外存地址(disk address)：用于指出该页在外存上的地址，供调入该页时使用。 访问统计位：描述了在近期内被访问的次数或最近一次访问到现在的时间间隔，可作为淘汰页面时

10、的参数。,3缺页中断 在请求分页存储系统中，由CPU的地址变换机构根据页表中的状态位判断是否产生缺页中断(page fault)，然后调用操作系统提供的中断处理例程。缺页中断的特殊性主要体现在如下两点：,(1) 缺页中断是在指令执行期间产生和进行处理的，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。 (2) 一条指令的执行可能产生多次缺页中断。如：swap A, B指令，若指令本身和两个操作数A、B都跨越相邻外存页的分界处，则产生5次缺页中断(不可能出现指令本身的两次缺页)，如图5.3所示。,图5.3 一条指令的5次缺页中断,影响缺页次数的因素有以下几种： (1) 分

11、配给进程的物理页面数。 (2) 页面本身的大小。 (3) 程序的编制方法。 (4) 页面淘汰算法。,例5.1 在一个请求分页存储管理系统中，把主存分成大小为128字节的块。设有一个用户要把128128的数组置成初值“0”，在分页时把数组中的元素每一行放在一页中。假定分给用户可用来存放数组信息的工作区只有一块(只能放数组中的一行元素)，用户编制了如下两个不同的程序来实现数字的初始化：,(1) var A:array1128 of array1128 of integer; for j:= 1 to 128 do for i:=1 do 128 do Aij := 0; 那么，由于该程序按列把数组

12、中的元素逐一地清0，所以每执行一次Ai，j：=0就会产生一次缺页中断。假设一开始已经把第一页装入主存，则程序执行时就可以对A1,1赋0，但下一个元素A2,1不在该页中，就产生缺页中断。这样总共要产生128128-1次缺页中断。,(2) var A: :array1128 of array1128 of integer; for i:= 1 to 128 do for j:=1 do 128 do Aij := 0; 那么，每装入一页就能对一行128个元素逐一的清零，之后才产生缺页中断，同样假设一开始已经把第一页装入主存，则程序执行时总共只产生128-1次缺页中断。,4页面调度策略 1) 页面调

13、入策略 页面调入策略决定了什么时候将一个页由外存调入物理内存。 (1) 请求调页(demand paging)：只调入发生缺页时所需的页面。 (2) 预调页(prepaging)：在发生缺页需要调入一页时，一次调入该页以及相邻的几个页。,通常对外存交换区的I/O操作效率比文件区的高。关于调入页面，通常有两种做法： 进程装入时将其全部页面复制到交换区，以后总是从交换区调入，执行时调入速度快，但要求交换区空间较大。 是未被修改的页，都直接从文件区读入，而被置换时不需要调出；已被修改的页面，被置换时需要调出到交换区，以后从交换区调入。这种方式节省了交换区空间，但是也可能引发一些问题。,2) 页面置换

14、策略 当进程产生缺页中断时，内存管理器还必须确定将调入的虚拟页放在物理内存的什么地方。用于确定最佳位置的一组规则称为“置页策略”。 如果缺页中断发生时物理内存已满，则由“页面置换策略”确定哪个虚页面必须从内存中移出，为新的页面腾出空间。在请求分页系统中，可以采用两种分配策略，即固定分配和可变分配。在进行置换时，也可以采用两种策略，即全局置换和局部置换。将分配策略组合起来，有如下三种策略(不包括固定分配全局置换，因为对各进程进行固定分配时不可能进行全局置换)：,(1) 固定分配局部置换(fixed allocation，local replacement)。采用该策略时，可以根据进程的类型，为每

15、一个进程分配固定页数的内存空间，且在整个运行期间不再改变。 (2) 可变分配全局置换(variable allocation，global replacement)。采用这种策略时，先为系统中的每一个进程分配一定数量的物理块，操作系统本身也保持一个空闲物理块队列。,(3) 可变分配局部置换(variable allocaton，local replacement)。采用这种策略时，同样根据进程的类型，为每一个进程分配一定数目的内存空间。,3)物理块分配算法 在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法。 （1）平均分配算法 这是将系统中所有可供分配的

16、物理块平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因它未考虑各进程本身的大小。如有一个进程其大小为200页，只分给它20块，显然会有很高的缺页率,而另一个进程只有10页，却又20个物理块闲置。,（2）按比例平均分配算法 根据进程的大小按比例分配物理块的算法。如果系统中有n个进程，每个进程的页面数为Si，则系统中各进程页面数总和为：,假定系统中可用的物理块总数为m，则每个进程能分到的物理块数为bi，将有,5.页面淘汰算法(page replacement algorithm) 页面淘汰(置换)算法决定在需要调入页面时，内存中哪个物理页面被置换。页面置换算法的出发点是把未来不再使用的或者短时期内较少使用的页面调出。,页面置换常用的算法有以下几种： (1) 最佳算法(optimal，OPT)：置换“未来不再使用的”或“在离当前最远位置上出现的”页面。 (2) 先进先出页面淘汰算法(Fi