第5章 虚拟存储器

第五章虚拟存储器重点理解虚拟存储器的基本概念掌握请求分页系统的基本原理掌握页面置换算法页面抖动的工作集模型难点请求分页系统的地址转换页面置换算法第五章虚拟存储器知识点虚拟存储器的基本概念、特征页面置换技术请求分页系统，页表机制、地址变换页面置换算法页面抖动工作集模型第五章虚拟存储器5.1虚拟存储器概述5.2请求分页存储管理方式5.3页面置换算法5.4“抖动”与工作集5.5请求分段存储管理方式5.1虚拟存储器概述5.1.1常规存储管理方式的特征和局部性原理5.1.2虚拟存储器的定义和特征5.1.3虚拟存储器的实现方法5.1.1常规存储管理方式的特征和局部性原理连续分配离散分配(基本)分页(基本)分段段页式方便程序装入提高内存利用率程序装入内存时可能出现的问题程序太大，要求的空间超出了内存总容量大量作业要求运行，但内存不能容下所有作业常规存储器管理方式的特征一次性要求作业全部装入内存才能运行驻留性程序装入内存后便一直驻留内存，直至运行结束许多不用或暂时不用的程序占用了大量内存空间，而其他程序却无法装入！是否必要？5.1.1常规存储管理方式的特征和局部性原理局部性原理（1968年，Denning.P）程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的；过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5；程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行；程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内5.1.1常规存储管理方式的特征和局部性原理局限性的表现时间局限性某条指令被执行=不久以后该指令可能再次执行数据被访问过=不久以后该数据可能再次被访问典型原因：因在程序中存在着大量循环操作空间局限性存储单元被访问=不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内典型情况：程序的顺序执行。5.1.1常规存储管理方式的特征和局部性原理虚拟存储器的基本工作情况程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。虚拟存储器支持多道程序设计技术5.1.1常规存储管理方式的特征和局部性原理5.1.2虚拟存储器的定义和特征虚拟存储器定义具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而其成本却又接近于外存。注意：虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0～(232-1)，即虚存容量为4GB。5.1.2虚拟存储器的定义和特征虚拟存储器的特征多次性一个作业被分成多次调入内存运行对换性允许在作业的运行过程中进行换进、换出虚拟性能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量注意：以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术。5.1.3虚拟存储器的实现方法虚拟存储器的实现建立在离散分配的存储管理方式基础上。主要实现方式请求分页系统请求分段系统5.1.3虚拟存储器的实现方法请求分页系统：在分页系统的基础上增加了请求调页功能和页面置换功能硬件支持页表机制。在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构。每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构。在纯分页地址变换机构的基础上发展形成的软件支持实现请求调页的软件和实现页面置换的软件5.1.3虚拟存储器的实现方法请求分段系统系统同样需要必要的硬件支持：段表机制。在纯分段的段表机制基础上，增加若干项而形成的；缺段中断机构。每当用户程序所要访问的段尚未调入内存时，产生一缺段中断，请求OS将所缺的段调入内存；地址变换机构。与请求调页类似，实现请求调段和置换功能也需要得到OS的支持。5.2请求分页存储管理方式5.2.1请求分页中的硬件支持5.2.2请求式分页中的内存分配5.2.3页面调入策略5.2.1请求分页中的硬件支持系统需要解决的问题如何获知进程当前所需页面不在主存？如何把所缺页面调入主存？采用什么策略选择欲淘汰的页面？当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去。5.2.1请求分页中的硬件支持请求页表机制状态位P（中断位）指示该页是在内存还是在外存访问位A用于记录本页在一段时间内被访问的次数或记录本页在最近多长时间未被访问修改位M表示该页在内存中是否被修改过外存地址该页在外存上的地址，通常是物理块号。页号物理块号状态位P访问位A修改位M外存地址5.2.1请求分页中的硬件支持缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断。相应的中断处理程序把控制转向缺页中断子程序，执行此子程序，即把所缺页面装入主存，然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。缺页中断与一般中断的区别在指令执行期间产生和处理中断信号一条指令在执行期间可能产生多次缺页中断。涉及6次缺页中断的指令页页B页A页654321页页COPYATOB例.COPY,能够移动256B块可能跨越页边界；移动部分字符后出现页错误；如果源和目的块有重叠，源块可能已被修改。解决方案试图存取两个块的两端；使用临时寄存器保存被覆盖位置的值。5.2.1请求分页中的硬件支持5.2.1请求分页中的硬件支持地址变换机构在分页系统地址变换机构的基础上，增加实现虚拟存储器某些功能形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。地址变换过程检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位。对于写指令，还须将修改位置成“1”；然后利用页表项中给出的物理块号和页内地址形成物理地址，结束。内存中去查找页表，再从找到的页表项中的状态位P，来了解该页是否已调入内存。请求分页中的地址变换过程缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号＞页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是OS命令CPU从外存读缺页5.2.2请求分页中的内存分配最小物理块数的确定指保证进程正常运行所需的最小物理块数。当系统分配的物理块数少于此值时，进程将无法运行与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式单地址指令且采用直接寻址方式的机器，则所需最少2个物理块。其中，一块存放指令页面，另一块则存放数据页面允许间接寻址的机器，至少要求有3个物理块两个或多于两个字节指令的机器，其指令本身可能跨两个页面，且源和目标地址所涉及的区域也可能跨两个页面，至少需要6个物理块5.2.2请求分页中的内存分配最小物理块数的确定不同的作业要求不同。如：允许间接寻址：则至少要求3个物理块。MovA,[B]Load1,1000直接寻址方式，则所需的最少物理块数为2movA,[B]1000XXXX5.2.2请求分页中的内存分配物理块的分配策略在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略固定分配局部置换(FixedAllocation,LocalReplacement)可变分配全局置换(VariableAllocation,GlobalReplacement)可变分配局部置换(VariableAllocation,LocalReplacemen问题：分配块数难确定，太少，缺页频繁，吞吐量降低；太多，内存驻留进程数减少，CPU或其它资源可能空闲先分配给各进程一定数的物理块，系统有一空闲物理块队列，缺页时从空闲队列取，若空闲队列空时，再选页调出先分配给各进程一定数的物理块，缺页时从该进程在内存的页选一换出，若其频繁缺页，系统再分配若干附加物理块5.2.2请求分页中的内存分配物理块分配算法平均分配算法将系统中所有可供分配的物理块，平均分配给各个进程例：当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用5.2.2请求分页中的内存分配物理块分配算法按比例分配算法根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数niiSS1mSSbii5.2.2请求分页中的内存分配物理块分配算法考虑优先权的分配算法在实际应用中，为了使重要的、紧迫的用户程序能尽快地完成，为它分配较多的内存空间。通常方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在重要的系统，如实时控制系统，则可能是完全按优先权为各进程分配其物理块的。5.2.3页面调入策略调入页面的时机预调页策略采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存，成功率50%请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便提出请求，由OS将其所需页面调入内存目前的虚拟存储中大多采用此种策略5.2.3页面调入策略从何处调入页面外存分为两部分用于存放文件的文件区用于存放对换页面的对换区通常，对换区采用连续分配方式，文件采用离散分配方式。系统应从何处将缺页调入内存，分成三种情况系统拥有足够的对换区空间系统缺少足够的对换区空间UNIX方式文件区对换区5.2.3页面调入策略系统拥有足够的对换区空间所需的页面全部从对换区调入，以提高调页速度。为此，在进程运行前，将与该进程有关的文件，从文件区拷贝到对换区。系统缺少足够的对换区空间凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。对于那些可能被修改的部分，在将它们换出时，调到对换区，以后需要时，再从对换区调入。5.2.3页面调入策略UNIX方式由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。5.2.3页面调入策略页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断。①查找所需页在磁盘上的位置；②查找一空闲帧；i)如果有空闲帧，那么就使用它；ii)如果没有空闲帧，那么就使用页置换算法以选择一个“牺牲”帧（victimframe）；iii)将“牺牲”帧的内容写到磁盘上，改变页表和帧表。③将所需页读入（新）空闲帧，改变页表和帧表；④重启用户进程。请求分页中的地址变换过程缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页