第四章 存储器管理（二）中国民航大学 计算机科学与技术学院第四章 存储器管理 4.1 存储器的存储层次4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 4.6 虚拟存储器的基本概念 l 传统的内存管理方式要求将一个作业全部装入内存才可以运行，由此造成了以下两种情况：大作业对内存的要求超出物理内存总容量，致使其无法运行内存由于容量的限制，只能装入少量的作业使其运行，而其它大量作业留在外存上l 怎么办？方法一：从物理上增加内存容量，成本高！方法二：从逻辑上扩充内存容量！虚拟存储技术！4.6.1 虚拟存储器的引入 传统思路：进程必须全部进入内存，直至运行结束“一次性”全部 装入内存，对空 间浪费非常大在进程运行的过程 中，始终“驻留” 在内存。暂时不用 的数据无法释放1、常规存储器管理方式的特征一次性、 驻留性。 2. 局部性原理 早在1968年， Denning.P就曾指出： 程序在执行时呈现局部性规律。在较短时间内，程序的执行局限于某个部分；访问的存储空间局限于某个区域。l 程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。l 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。l 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。l 程序中还包括许多对数据结构的处理， 如对数组进行操作， 它们往往都局限于很小的范围内。 局限性又表现在下述两个方面：l 时间局限性。如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。l 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。基于局部性原理：l 在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。l 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），利用OS提供的请求调页（段）功能，将相应的页或段调入到内存，然后继续执行程序。l 如果此时内存已满，无法装入新的页（段），则还必须调用页（段）置换功能。l 这样，便可是一个大的用户程序，在较小的内存空间运行；也可在内存中同时装入更多进程并发运行。3. 虚拟存储器定义 l 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。l 其逻辑容量由内存容量和外存容量之和所决定l 其运行速度接近于内存速度l 成本却又接近于外存l 虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、 中、 小型机器和微型机中。 地址空间存贮空间 (编程)(运行)逻辑物理虚空间(虚存)实存、实空间交换 o.sl 程序的访问地址称为虚地址而程序可访问的虚地址范围叫做程序的虚地址空间。可使用的实地址范围叫实地址空间(即主存)l 在多道程序运行环境下，o.s把实际内存扩充成若干个虚存系统为每个用户建立一个虚拟存贮器，各用户可独立在虚存上编程运行。X X X X 7 X 5 X X X 3 4 0 6 1 260K-64K56K-60K 52K-56K48K-52K 44K-48K 40K-44K 36K-40K 32K-36K28K-32K24K-28K 20K-24K16K-20K 12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K 20K-24K16K-20K 12K-16K8K-12K4K-8K0K-4K虚地址空间物理地址空间 虚页页框15 14 13 12 11 109876543210000 0000 0000 0000 1111 0000 1011 0000 0000 0000 1101 1001 0001 1101 0111 0101 00010000000000100011000000000100011 在/不在内存页表虚地址 8196物理地址 245804.6.2 虚拟存储器的实现方法 l 实现原理进程运行只装入部分程序和数据在外存保留完整副本运行中动态调整进程在内存中的部署l 技术难点如何确定和记录当前哪些部分在内存？执行中访问不在内存的指令和数据时如何处理？从外存中调入某页时,内存中空间不够如何处理？l 优点: 利用率高，方便用户，对多道程序运行有较强的支持l 有两种典型虚拟存储器实现方式1. 分页请求系统 l 在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统l 基本思想分页管理，装入少量页运行，缺页故障后调整l 页表结构进行了调整:页号+ 标志位+ 块号+ 外存地址l 地址转换:正常地址转换缺页时：缺页中断2. 请求分段系统 l在分段系统的基础上，增加请求调段及分段置换功能后，所形成的 段式虚拟存储系统。l基本思想装入部分段动态装入或调出段l段表结构进行了扩充：段号+ 主存起址+ 长度+ 辅存起址+标志位+扩充位l缺段中断机构l地址变换机构4.5.3 虚拟存储器的特征 l 离散性在内存分配时采用离散分配方式l 多次性一个作业被分成多次地调入内存运行l 对换性允许作业在运行过程中换进、换出l 虚拟性从逻辑上扩充内存容量，使用户可使用的内存空间大于实际物理内存。第四章 存储器管理 4.1 存储器的存储层次4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式 4.5 基本分段存储管理方式 4.6 虚拟存储器的基本概念 4.7 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式 4.7.1 请求分页中的硬件支持 l 为了实现请求分页，系统要提供一定的硬件支持。除了一定容量的内存和外存，还需要有：页表机制、缺页中断机构和地址变换机构问题一：怎样发现页不在内存？扩充表(以前页表结构只包含页号和块号两个信息，这是进行地址变换机构所必须的，为了判断页面在不在主存，可在原页表上扩充）！1. 页表机制 页号 物理块号 状态位P 访问字段A 修改位M外存地址 用于将用户逻辑地址空间变换为内存的物理地址空间。在页表中增加若干项，以便于标志程序或数据的状态。页表项：状态位（存在位）P：表示该页是否调入内存访问字段A：用于记录该页在某段时间内被访问的次数修改位M：表示该页在调入内存后是否被修改过外存地址：该页在外存上的地址，通常是物理块号缺页中断管理！问题二：如何处理缺页？2. 缺页中断机构 l 在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使进程继续运行下去。l 如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的状态位及相应的内存块号。l 若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。 处理过程：保护CPU现场、分析中断原因、转入缺页中断处理程序、恢复CPU环境。 特点 缺页中断发生在指令执行期间，而通常情况 下，CPU是在一条指令执行完后，才检查是否有 中断请求到达； 一条指令在执行期间，可能产生多次缺页中 断。图 4-23 涉及6次缺页中断的指令 硬件机构应能保存多 次中断时的状态，并 保证最后能返回到中 断前产生缺页中断的 指令处，继续执行。问题三：缺页中断，调入所缺页，如果内存不 足，选一页淘汰，选择哪一页呢？页号 物理块号 状态位P 访问位A 修改位M外存地址 访问位是来指示某页最近被访问过没有。修改位是来指示某页的数据修改过没有。“ 0”表示没有访问过“ 1”表示已被访问过访问位修改位1修改位 写回辅存0未修改过 不必写回辅存问题四：如何实现地址变换？3. 地址变换机构 图 4-24 请求分页中的地址变换过程 1.在地址变换时，首先检索快表，试图从中找到要访问的页。如找到，修改其访问位。对于“写”指令，还要设置修改位的值。如未找到，则转3。2.利用页表项中的物理块号和页内地址，形成物理地址。3.查找页表，找到页表项后，判断其状态位P，查看该页是否在内存中。如果在，则将该页写入快表（若快表已满，则应该先调出某个或某些页表项）。如果不在，则产生缺页中断，由OS从外存将该页调入内存。工作区入内存填写页表中各项进程调度该进程执行启动待执行指令计算页号与页内相对地址该页在主存吗？执行下一条指令访内存执行完成该指令地址变换保存当前进程现场有空闲页面吗？调入所需虚页调整页表及空闲页面表恢复被中断进程现场选择一页淘汰该页修改过？把该页写回外存缺页中断是否否否是是硬件完成请求分页的处理流程。L 1, 2120 ADD 1, 3410 00680201k2k3k01k2k3k-10 1k2k3k-10062514k-1job1job2job3005106210021042131008 103 21ososjob2(0页)job3(1页)L 1, 2120 ADD 1, 3410job1(0页)job1(1页)空 job3(0页)空0 1k2k3k10-k4k5k 6k7k8k9k辅存块号主存请求页式映象存贮图：4.7.2 内存分配策略和分配算法 l 在为进程分配物理块时，要解决下列的三个问题：保证进程可正常运行所需要的最少物理块数每个进程的物理块数，是固定值还是可变值（分配策略）不同进程所分配的物理块数，是采用平均分配算法还是根据进程的大小按照比例予以分配（分配算法）。4.7.2 内存分配策略和分配算法 进程应获得的最少物理块数与计算机的硬件机构有关，取决于指令的格式、功能和寻址方式。一、最小物理块数在请求分页中，可采取两种分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换（置换范围不同）。于是组合出三种适用的策略： 二、页面分配和置换策略1、固定分配局部置换l 思路分配固定数目的内存空间，在整个运行期间都不改变l 策略如果缺页，则先从该进程在内存的页面中选中一页，进行换出操作，然后再调入一页。l 特点为每个进程分配多少页是合适的值难以确定。2、可变分配全局置换l 思路：l 每个进程预先分配一定数目的物理块，同时OS也保持一个空闲物理块队列。l 策略l 当缺页时，首先将对OS所占有的空闲块进行分配，从而增加了各进程的物理块数。当OS的空闲块全部用完，将引起换出操作。l 思路l系统根据缺页率动态调整各进程占有的物理块数目，使其保持在一个比较低的缺页率状态下。l 特点l使大部分进程可以达到比较近似的性能。3、可变分配局部置换在采用固定分配策略时，可使用下列方法来分配：1、平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。2、按比例分配算法：按照进程的大小比例分配物理块。3、考虑优先权的分配算法：为了对于紧迫的作业，能够尽快完成。可以将内存的物理块分成两部分，一部分按照比例分配给各进程，另一部分根据进程优先级，适当增加其相应的份额，分配给各进程。三、分配算法1) 平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。 例如，当系统中有100个物理块，有5个进程在运行