《计算机操作系统》（孙雅如版）全套PPT电子课件教案-第3章 存储器管理.ppt

第3章 存 储 器 管 理 第3章 存 储 器 管 理 3.1 存储管理概述 3.2 分区式存储管理 3.3 覆盖和对换 3.4 分页存储管理 3.5 请求分页存储管理 3.6 分段存储管理 3.7 段页式存储管理 第3章 存 储 器 管 理 3.1 存储管理概述 3.1.1 存储管理的概念 在计算机的发展历程中，不管是单道程序系统，还是多道程 序系统，内存利用始终是一个重要环节。在计算机工作时，程序 处理的典型过程是这样的，首先cpu通过程序计数器中的值从内 存中取得相应的指令，指令被译码后根据要求可能会从存储器中 再取得操作数。对操作数处理完成后，操作结果又会存储到存储 器中。在这个过程中，操作系统需要保证程序执行中按照适当的 顺序从正确的存储器单元中存取指令或者数据，也就是说有效管 理存储器的存储空间，根据地址实现上述任务。 第3章 存 储 器 管 理 大容量的内存是我们一直追求和努力的目标，我们看到cpu 由8086到286、386、486，直到目前的p4，内存标准配置也由512 kb到1 mb、2 mb、4 mb，直到现在的256 mb或者更高，甚至 有些计算机主板支持的内存容量达到2 gb以上。但不管如何，内 存管理的主要任务仍然是合理地建立用户程序与内存空间的对应 关系，为各道程序分配内存空间，运行完成后再予以回收，而且 始终要保证系统程序和各用户程序安全。简单地说，内存管理包 括地址映射、内存分配和内存保护功能。虽然现在内存的容量在 不断加大，但价格却不断下降，有资料表明，10年前的内存价格 相当于现在的500倍。但是用户程序的规模也在成百上千倍地增 长，对内存容量的要求似乎没有上限，所以就要求内存管理能够 提供内存扩充功能，即利用单位价格更为便宜的外存来模拟为内 存，让用户透明使用。这就是内存管理的虚拟功能。 第3章 存 储 器 管 理 3.1.2 地址重定位 1地址空间和存储空间 在我们用汇编语言或高级语言编写程序时，总是通过符号名 来访问某一单元。我们把程序中由符号名组成的空间称为名空间 。源程序经过汇编或编译并再经过链接编辑程序所装配形成的程 序，通常是以0为基址进行顺序编址，或者是分成若干个部分，每 个部分以0为基址，这样的地址表示形式称为相对地址,也叫做逻 辑地址或虚地址，把该程序逻辑地址组成的集合叫做程序的逻辑 地址空间(简称地址空间)。而在存储器中每个具体存储单元都有 不同的编号，每个编号就是一个物理地址，整个程序在内存中存 储后所占用的物理地址的集合形成程序的物理地址空间(简称存储 空间)。程序的名空间、地址空间和存储空间的关系如图3-1所示 。 第3章 存 储 器 管 理 图3-1 名空间、地址空间和存储空间的关系 第3章 存 储 器 管 理 2地址的重定位 当一个逻辑地址空间的程序装入到物理地址空间时，由于 两个空间不一致，需要进行地址映射，即地址的重定位。地址 重定位有两种方式：静态重定位和动态重定位。 静态重定位是在程序装入内存，开始执行之前进行地址重 定位。静态重定位工作通常是由装配程序完成的，其过程如图3- 2所示。 第3章 存 储 器 管 理 图3-2 静态重定位 第3章 存 储 器 管 理 静态地址重定位的优点是容易实现，无需硬件支持，它只 要求程序本身是可重定位的，即对那些要修改的地址部分具有 某种标识，地址重定位由专门设计的程序来完成。在早期的操 作系统中大多数都采用这种方法。其主要缺点是程序经地址重 定位后就不能移动了，因而不能重新分配内存，不利于内存的 有效利用。 第3章 存 储 器 管 理 动态地址重定位是在程序执行期间，在每次存储访问之前 进行的。在这种情况下，通常通过基地址寄存器、变址寄存器 计算出指令的有效地址，再利用硬件机构实现地址映射，这样 的硬件设备称为存储管理单元mmu(memory-management unit) 。通常采用的办法是利用一个重定位寄存器，对每一个有效地 址都要加上重定位寄存器中的内容，以形成绝对地址。在图3-3 中，把某一相对地址程序装入地址1000开始的内存区域时，只 要把1000装入重定位寄存器，程序即可运行。这一动态地址重 定位的过程如图3-3所示。 第3章 存 储 器 管 理 图3-3 动态重定位 动态地址重定位的优点是程序在内存中的搬移不会对程序的 正确执行造成影响，使内存得以被充分利用，其缺点是需要附加 的硬件支持，实现存储管理的软件算法比较复杂。 第3章 存 储 器 管 理 3.1.3 虚拟存储器概念的引入 前已述及，一方面用户程序越来越大，所要求的内存存储空 间相应越来越大，但内存的增长却相对有限；另外一方面，外存 又存在着容量远远超过内存容量的剩余空闲区域。所以，寻求一 系列措施，使用户可以将外存的一部分区域（我们称之为辅存） 当作内存来使用，就成为一种有效的选择方式。但这种使用方式 对用户来说应该是透明的，即用户不知道也不用知道当前自己到 底使用的是内存还是外存。这样，用户就是在使用一个比实际内 存储器大得多的存储器，把这个存储器叫做虚拟存储器。在虚拟 存储器系统中主要介绍具体的请求分页存储管理方式和请求分段 存储管理方式。 第3章 存 储 器 管 理 3.2 分区式存储管理 3.2.1 单一连续分配 单一连续分配是一种简单的存储分配方案，主要用于单用户 单任务操作系统。它的实现方案如下： (1) 内存分配：整个内存划分为系统区和用户区。系统区是 操作系统专用区，不允许用户程序直接访问，一般在内存低地址 部分，剩余的其它内存区域为用户区。一道用户程序独占用户区 ，如图3-4所示。 注意：内存区一般划分为系统区和用户区，本章我们所述及 的内存分配与回收都指用户区的分配与回收，除非特别说明。 第3章 存 储 器 管 理 图3-4 内存划分 第3章 存 储 器 管 理 (1) 内存分配：整个内存划分为系统区和用户区。系统区是 操作系统专用区，不允许用户程序直接访问，一般在内存低地 址部分，剩余的其它内存区域为用户区。一道用户程序独占用 户区，如图3-4所示。 注意：内存区一般划分为系统区和用户区，本章我们所述 及的内存分配与回收都指用户区的分配与回收，除非特别说明 。 (2) 地址映射：物理地址=用户区基地址+逻辑地址。 第3章 存 储 器 管 理 (3) 内存保护：通过基址寄存器保证用户程序不会从系统 区开始；另外系统需要一个界限寄存器，里边存储程序逻辑地 址范围，若需要进行映射的逻辑地址超过了界限寄存器中的值 ，则产生一个越界中断信号送cpu。 单一连续分配方案的优点是方法简单，易于实现；缺点是 它仅适用于单道程序，因而不能使处理机和内存得到充分利用 。 第3章 存 储 器 管 理 3.2.2 固定式分区分配 随着多道程序设计的出现和发展，存储管理技术也得到极 大的发展。多道程序存在于一个存储器中，如何实现分配、保 护、访问变得越来越复杂。于是分区式存储管理应运而生，逐 步形成了固定式分区分配、动态分区分配和动态重定位分区分 配等不同策略。 固定式分区分配的“固定”主要体现在系统的分区数目固定和 分区的大小固定两个方面。方案的主要内容为： 第3章 存 储 器 管 理 (1) 内存分配/回收：根据不同的内存容量划分策略有两类情 况：一类是内存等分为多个大小一样的分区，这种方法主要适 用于一些控制多个同类对象的环境，各对象由一道存在于一个 分区的进程控制，但是对于程序规模差异较大的多道环境不太 适合，比如大于分区大小的进程无法装入，而且小进程也会占 用一个分区，造成内存碎片（即无法被利用的空闲存储空间） 太大。另一类是将内存划分为少量大分区，适量的中等分区和 多个小分区，这样可以有效地改善前一种方法的缺陷。 第3章 存 储 器 管 理 表3-1 分 区 说 明 表 分区号 分区大小（kb ） 分区始址（k ） 状态 12051 240251 350650 第3章 存 储 器 管 理 在分区说明表中查找状态为空闲（可以用“0”表示空闲，“1” 表示非空）且大小满足要求的分区予以分配，然后修改分区说 明表中的对应项。 当该进程结束后，再将分区说明表中对应项的“状态”修改为 “0”，就表示对它所占用的分区予以回收，而回收后的分区又可 以作为空闲分区分配给其它的申请进程。 第3章 存 储 器 管 理 图3-5 各个分区的碎片 第3章 存 储 器 管 理 (2) 地址映射：物理地址=分区始址+逻辑地址。 (3) 内存保护：分区始地址保证了各道程序不会由其它程序 所在分区开始，另外逻辑地址与所给分区大小相比较，保证不 会超过该分区而进入其它分区。 固定式分区分配的缺点是内存空间的利用率低，因为基本 上每个分区都会有碎片存在，尤其是某些大分区中只是存放一 道小进程时。例如图3-5，5道进程大小总和为250 kb，但是所 占5个分区总容量却达到1000 kb，内存空间利用率仅达到25% 。 所以说固定式分区分配对每个分区很难做到“物尽其用”，会 形成内存碎片，导致内存浪费严重。 第3章 存 储 器 管 理 3.2.3 动态分区分配 为了改善固定分区分配给系统带来的内存碎片太大、空间浪费 严重的缺陷，提出了动态分区分配，也叫做可变式分区分配的策 略，即根据进程的实际需求动态地划分内存的分区方法。它是在 进程装入和处理过程中建立分区，并要使分区的容量能正好适应 进程的大小。而整个内存分区数目随着进程数目的变化而动态改 变，各个分区的大小随着各个进程的大小各有不同，所以称之为 动态分区分配。 1动态分区的分配过程 在动态分区分配中，各个空闲分区通过指针形成链，称为空 闲分区链，它是系统动态分区分配所需要的一种重要数据结构， 格式如图3-6所示。基于空闲分区链和分区说明表，系统按照图3-7 所示流程实现分区分配。 第3章 存 储 器 管 理 图3-6 空闲分区链 第3章 存 储 器 管 理 图3-7 动态分区流程 第3章 存 储 器 管 理 2动态分区分配算法 动态分区分配算法有以下几种。 1) 首次适应算法（ff, first fit） 空闲分区链以地址递增的顺序链接，分配时从链首开始查找， 找到第一个大小可以满足的分区为止，从其中划分出所需空间分配 给申请的进程，剩余部分仍旧作为一个分区保留在空闲分区链中， 否则给出无法分配的提示。 采用这种方法时，每次分配都需要从链首也就是低地址开始查 找，所以低地址由于被划分的可能性比较大，容易形成多个过小分 区而难以利用，成为外部碎片（前面所描述的在每个分区内的“碎 片”相应称为内部碎片）。同时这些小分区增加了查寻时的判断时 间，降低了效率。 第3章 存 储 器 管 理 2) 循环首次适应算法 为了改变首次适应算法每次从链首开始查寻造成的缺陷， 可以增加一个起始查寻指针，指向下一次开始查寻时的起始分 区，在查寻过程中，该指针向后移动，当移动到最后一个空闲 分区后，重新回到链首。找到适当分区后，按首次适应算法的 划分分区方式进行。这种方法可以使内存区分配比较平均，减 少查寻次数，但又造成了缺少大空闲分区，使得大进程无法进 入。 第3章 存 储 器 管 理 3) 最佳适应算法 空闲分区链按照分区容量递增的方式形成，分配时从链首 开始查找，这样找到的第一个大小可以满足的分区肯定是与进 程申请空间大小最接近，甚至是完全吻合的分区，而且平均查 找次数为分区数的一半，也就是说它是“最佳适应”的。但这种方 法所造成的剩余分区又肯定是相对最小的，通常难以利用，甚 至我们可以说，每次分配一个分区都会造成一个无法再利用的“ 碎片”，而这些“碎片”的总容量可能是比较大的。 第3章 存 储 器 管 理 4) 最差适应算法 “最差”当然不是指这种算法的性能最差，否则我们就没有必 要把它提出来了，相反在某种情况下，它却是一种性能“最佳”的 算法。其实现思想是这样的，空闲分区链按照分区容量递减的方 式形成，分配时从链首开始，若链首分区大小不满足，则可以肯 定不存在能够满足要求的分区；否则对链首分区进行划分，剩余 空间成为“碎片”的可能性肯定是最小的。所以说，最差适应算法 具有查找速度快，分区碎片少的优点，但又会产生缺少大分区的 缺点。 第3章 存 储 器 管 理 在这几种分配算法中，一般情况下，首次适应算法是最简 单，而且是最快和最好的算法。循环首次适应算法比首次适应 算法稍差一些，而最佳适应算法虽然名字中有“最佳”，但实际上 是性能最差的。但在某些应用情况下，上述比较结果会有所变 化。 第3章 存 储 器 管 理 3动态分区的回收 图3-8 动态分区的回收 第3章 存 储 器 管 理 (a) m1、m2都非空，将回收区直接记录在空闲分区表或者插 入空闲分区链中。 (b) m1为空，m2非空，则首先将m1与回收区合并，修改 m1大小为其原大小与回收区之和。 (c) m1非空，m2为空，则首先将m2与回收区合并，修改 m2始地址为回收区的始地址，m2大小为其原大小与回收区之和 。 (d) m1、m2都为空，将m1、回收区、m2合并，修改m1大 小为原大小、回收区大小和m2大小三者之和，从空闲分区链中 去掉m2。 第3章 存 储 器 管 理 3.2.4 动态重定位分区分配 在动态分区分配中，多个无法利用的小分区所形成的“碎片 ”是一种很大的资源浪费。如图3-9（a）所示，空闲分区之和为 10 kb，但是无法装入一个8 kb的程序。 为了解决类似问题，我们采用一种称为“紧凑”的方法，通 过移动程序将原来分散的空闲小分区拼接为一个大的分区，就 可以使某些比较大的进程进入，如图3-9（b）所示。一般情况 下，当某进程因为没有足够大的分区，而所有“碎片”之和又大 于进程大小时将进行“紧凑”。 第3章 存 储 器 管 理 图3-9 紧凑 第3章 存 储 器 管 理 请思考：可否每分配或者回收一个分区就进行紧凑？ 采用内存“紧凑”以后，由于程序和数据的位置都发生了变 化，如果不进行相应的地址修改，则程序就无法执行。所以必 须要采用3.1.2节介绍的动态重定位方法来进行地址映射，于是 称这种方案为动态重定位分区分配。 动态重定位分区分配算法实际上是在动态分区分配算法中 增加了“紧凑”环节，即无法找到满足大小的分区时，进行“紧凑 ”之后再进行分区分配。 第3章 存 储 器 管 理 3.2.5 分区分配方案的评价 在分区分配方案中，地址映射都遵循“物理地址=分区始地址 +逻辑地址”，固定分区分配与动态分区分配的分区始地址都来自 于硬件“基址寄存器”，动态重定位分区分配的分区始地址来自于 “重定位寄存器”。内存保护由“基址寄存器”和“限长寄存器”共同 实现，也可以用一对下限寄存器和上限寄存器来实现，一旦超过 限长，则发出越界中断信号。 分区分配方案的主要优点可归纳如下： (1) 多道程序下的内存共享，改善了系统吞吐量，在内存利 用率方面，从固定式分区到动态分区，再到动态重定位分区依次 提高。 第3章 存 储 器 管 理 (2) 相对于后面介绍的存储管理方式，为实现分区分配所使 用的数据结构占用的存储容量相对较少，算法也相对简单。 (3) 实现存储保护的措施也比较简单。 第3章 存 储 器 管 理 分区分配的主要缺点有： (1) 内存仍不能充分利用，除了动态重定位式分区法外，都 存在着严重的碎片问题。 (2) 不能实现对内存的扩充，因此进程的大小受到内存可用 空间的限制。 (3) 与单一连续分配一样，要求一个进程在执行之前必须全 部装入内存，因此在内存中可能包含不会被使用的信息。 (4) “紧凑”提高了内存利用率，但是进程移动所产生的额外 开销增加了cpu的负担。 (5) 几个并行进程之间不能共享存入内存的单一信息副本( 如公用子程序、数据段等)。 第3章 存 储 器 管 理 3.3 覆 盖 和 对 换 3.3.1 覆盖(overlay) 覆盖技术的基本思想是将内存的同一区域按照使用的先后 顺序，分配给几个不同进程或一个进程的几个程序段或数据段 ，即允许进程运行时，可以不用把它的所有程序段都调入内存 ，当进程处理需要某程序段时将它装入到原来已经占用的某分 区中，原来存储在这个分区中的程序就被“覆盖”了。 第3章 存 储 器 管 理 采用覆盖技术后，进程可以分为常驻内存部分和覆盖部分 ，常驻内存部分是指进程处理过程中始终需要的程序段，而覆 盖部分是进程处理过程中动态调入内存的程序段。这样，当进 程要求运行时，系统根据其覆盖结构，给它分配一段存储空间 ，其大小等于常驻部分和覆盖区之和。覆盖区长度由相应覆盖 段中最大程序段的长度确定。处理过程是先把常驻内存部分调 入，然后将首先需要的可覆盖程序段由辅存调入，随着进程执 行，再将其它存放在辅存的覆盖部分陆续调入。 第3章 存 储 器 管 理 我们看到，采用覆盖技术后，就可以用小于进程申请大小 的内存空间来满足一个进程的处理空间，有效地利用内存。但 采用覆盖技术存在以下缺点： (1) 用户难以预知他的程序的覆盖情况，尤其是通过合作设 计实现大型软件系统，基本上程序员不能保证十分熟悉整个程 序，而在小程序中是不需要采用覆盖技术的。 (2) 用户只能有效地利用自己程序所占用的内存，而不能对 整个内存加以有效利用。 (3) 各进程占用的分区仍会存在碎片。 第3章 存 储 器 管 理 3.3.2 对换 (swapping) 所谓对换，就是把内存中暂时无法运行的进程或者暂时不需 要的程序、数据写入辅存，并将具备运行条件的进程或者需要的 程序、数据从辅存读入内存。采用对换技术可以很好地提高内存 的利用率和cpu的处理效率。 在引入对换技术的存储管理系统中，外存被划分为两个部分 ，一部分是文件区，另外一部分是对换区（swapping area）。对 换区用来暂时存放对换的进程或者程序、数据，对它的磁盘i/o速 度比文件区要快。因为对换技术重在频繁的交换操作中保证换入 换出的速度，而对磁盘利用率不作严格要求，所以对辅存对换区 存储空间的管理采用连续分配，它的分配与回收与动态分区分配 类似。 第3章 存 储 器 管 理 3.4 分页存储管理 3.4.1 分页原理 我们把逻辑地址空间划分为一些相等的片，这些片称为页或 页面。同样，物理地址空间也被划分为同样大小的片，称为块。 这样用户程序进入内存时，就可以一页对应存入到一个块中。对 整个程序来说，只有可能在最后一块存在碎片（称为页内碎片） ，而且碎片大小不会超过一块，所以内存利用率可以大大提高。 第3章 存 储 器 管 理 页面(或块)的大小由系统硬件地址结构规定，通常是2的幂 ，例如1 kb、2 kb、4 kb等。这样的规定可以使地址映射容易 实现，后面的例子可以帮助我们理解这个问题。页面不能过大 ，也不能过小。过小会造成页面过多，页表过长，页表又会占 用较大的内存空间，而且在虚拟存储中增加了页面换入换出次 数，增加了系统开销；过大又会造成页内碎片太大，内存利用 率不高。早期的页面大小一般都在512 b4 kb，随着计算机性 能的提高，现在一般在2 kb8 kb，甚至有的系统支持多种页 面大小，比如solaris就有4 kb和8 kb两种页面。 第3章 存 储 器 管 理 图3-10 分页式存储管理的系统地址结构 第3章 存 储 器 管 理 在这个完整的地址结构中，对页号、页内偏移量（也叫页 内地址）位数的确定，我们通过一个例子说明。比如对于一个 32位的地址结构，页面大小为4 kb，则页内偏移量由011这12 位表示，剩余1231在表示页号(图3-10中虚线两边所示)。 若给定某一个逻辑地址，通过下面式子可以得出页号和页 内偏移量： 页号=逻辑地址 din 页面大小 页内偏移量=逻辑地址 mod 页面大小 第3章 存 储 器 管 理 例如页面大小为4 kb的系统中，若逻辑地址为28024，则由 上式求得页号为6，页内偏移量为3448，如图3-11所示。而计算机 内部如何得到页号和页内地址呢？28024的二进制用32位表示为 (0000 0000 0000 0000 0110 1101 0111 1000)2，因为页面大小为4 kb，则取低12位为页内地址，剩余高位是页号。把这两部分换算 为十进制，我们可以验算出通过上述公式计算的结果的正确性。 图3-11 页号与页内偏移量举例 第3章 存 储 器 管 理 3.4.2 分页存储分配与回收算法 实现分页存储管理需要如下的数据结构： 页面映射表pmt：也称页表。每个进程一张，用于该进程的 地址映射，记录了进程每个页号及其对应的存储块号。 存储分块表mbt：整个系统一张，记录每个存储块及其状态 （已分配或空闲）。 图3-12给出了上述两种表格的结构及其关系。当有一个进程 进入系统时，为页表分配一个存储区，然后搜索存储分块表，查 看有哪些存储块是空闲的，如有空闲的存储块，则将存储块号填 入页表。当该进程所需的块数都分配完后，系统便可按照pmt的 内容对该进程进行处理。 第3章 存 储 器 管 理 图3-12 页表、存储分块表及其关系 第3章 存 储 器 管 理 当某个进程因为结束或者其它一些原因退出系统，则归还 原来所占用的物理块。首先修改存储分块表，将归还的物理块 块号在表中的状态栏改为空闲标志，然后释放该进程页表所占 用的空间。 第3章 存 储 器 管 理 3.4.3 地址映射机构 1动态地址映射机构 分页存储管理中，由于页和块大小是一致的，每页的页内地 址与物理块的块内单元地址也完全一致，所以在逻辑地址到物理 地址的映射中，主要从一个页找到对应的内存块，而这种页与块 的对应关系是页表记录的。每个进程调度时，从该进程pcb中取 得页表始址和页表长度（页表长度指页表的项数），装入到系统 中设置的一个页表寄存器ptr内。 图3-13给出了分页存储管理的地址变换机构和工作流程（页 大小为1024 b，给定逻辑地址3795，即页号为3，页内地址为723 ）。 第3章 存 储 器 管 理 图3-13 分页式地址变换过程 第3章 存 储 器 管 理 页号3与页表寄存器中的页表长度比较判断是否越界，如 果越界，则转错误中断处理，否则转； 页表中该项在内存中的对应地址=页表始地址r+页号3 页表项长度i，访问该地址r+3i，得到物理块号11； 11(页号)1024(页大小)+723(页内地址) = 11987(物理地址 )； 访问内存11987单元，得到需要的数据365。 第3章 存 储 器 管 理 2联想存储器 页表存放在内存中，由操作系统实施管理，在进程执行时 ，每一条指令的执行都必须进行地址映射。因此，每条指令都 必须两次访问内存储器：一次是访问页表，由页号找到对应的 物理块号，另一次是在物理地址中实际存取所要的数据或指令 。这样就增加了指令执行的机器时间，影响了计算机的速度。 为了加快查表速度，在地址映射机构中加入一组高速寄存器(8个 或16个)，构成了一个容量较小的存储器，称之为联想存储器， 也称快表。在联想存储器中，存放正在运行进程的当前最常用 的页号和相应块号，这个联想存储器具有并行查询能力，而且 查找速度可以做到比一般磁芯存储器的速度快一个数量级。图3- 14给出了利用联想存储器加速查表的过程。 第3章 存 储 器 管 理 图3-14 引入快表的地址映射 第3章 存 储 器 管 理 在采用联想存储器的系统中，先按给出的页号检索联想存 储器，一旦检索到所要的块号，就利用联想存储器给出的块号 访问内存，即在图3-14中走一条的路径。如果在联想 存储器中检索不到所要的块号，应利用pmt表进行查找，并将 页号以及所对应的块号一起填入联想存储器内的空白单元中。 如果没有空白单元，应根据某种规则(如先进先出)淘汰一个单元 内容后再行填入，即在图3-14中走一条的路径。 在多道程序系统中，当把处理的控制权由一道进程转到另 一道进程时，相应地把页表寄存器(ptr)以及联想存储器内容加 以更换。 第3章 存 储 器 管 理 3.4.4 多级页表 对于现代的计算机系统来说，所支持的逻辑地址空间越来越 大，已达232264。按照前面介绍的方法，所形成的页表将会非 常庞大并占用大量的内存空间。例如一个32位的系统，页面大小 为4 kb，则页表项数达到1 m项，如果每项占用4 b，则页表会占 用4 mb空间，而且是连续的4 mb空间。在多道程序环境下，这 是一个过于苛刻的要求。 一种解决办法就是对页表本身再分页，形成两级页表。比如 对于上边的例子，以前是将逻辑地址分成两部分，低12位为页内 地址，剩余高20位为页号。现在我们将这个20位的页号再分成两 部分，10位外层页号和10位内层页号，如图3-15所示。 第3章 存 储 器 管 理 图3-15 多级页表结构地址 第3章 存 储 器 管 理 图3-16 两级页表 第3章 存 储 器 管 理 3.4.5 分页存储管理方案的评价 综上所述，分页存储管理便于多道程序设计，提高了内存 的利用率，而不必像动态分区分配那样执行紧凑操作。但分页 存储管理仍然存在如下严重缺点： (1) 采用动态地址映射会增加计算机成本和降低处理机的速 度。 (2) 各种表格要占用一定容量的内存空间，而且还要花费一 部分处理机时间来建立和管理这些表格。 第3章 存 储 器 管 理 (3) 虽然消除了大量碎片，但每个作业的最后一页一般都有 不能充分利用的空白区。例如，假定页面大小为4 kb，如果某 一作业需要9 kb内存，则应该为它分配三个物理存储块，最后 一块的3 kb空间被浪费了。如果减少页面大小，使页面大小为2 kb，则对于需要9 kb内存的作业应分配5个存储块，其中有1 kb的内存被浪费了。减少页面大小，可以减少内存的浪费，但 页表的长度又增加了，这也是一个矛盾。 (4) 存储扩充问题仍未得到解决。当没有足够空间能装下整 个作业地址空间时，该作业还是无法运行。 第3章 存 储 器 管 理 3.5 请求分页存储管理 3.5.1 请求分页原理 1局部性特征 在多道程序环境下，可能有一些程序因为内存空间不够无法 装入，而已被装入内存的程序是否被充分执行呢？1968年， p.denning就指出，程序执行时呈现出局部性特征，表现为： (1) 时间局部性。程序中大量的循环结构和各种数据结构， 使某段程序一旦执行，很快又会被再次执行，某数据结构被访问 后，可能在短时间内再次被访问。 第3章 存 储 器 管 理 (2) 空间局部性。程序顺序执行和局部存储的连续性，使程 序访问某存储单元后，与它临近的存储单元会被访问。 通过这样分析，我们了解到程序只需要将当前必须的一部分 内容存在于内存中就可以开始执行，随着向前推进，再将所需 的其它内容调入。但是在调入时，可能出现内存不够的情况， 这样就要采用3.3节介绍的技术对换。在请求分页管理中， 对换的对象是页。 第3章 存 储 器 管 理 2请求分页存储管理的页表 现在一个新问题是程序执行一段时间后，系统是如何知道 所需的页不在内存而需调入呢？系统通过检查带有状态项的页 表判断该页是否在内存。该页表结构为： 页号块号状态位外存地址访问字段修改位 第3章 存 储 器 管 理 其中增加的表项如下： 状态位：表示该页是否在内存。 外存地址：该页存放在外存的地址，也就是存放在外存的 块号。 访问字段：记录该页的访问频度，作为置换的参考依据。 修改位：记录该页在内存访问过程中是否被修改。若未被 修改，则可以将该块直接标为空闲；若被修改，则首先应将该 块中的内容记录到对换区中，再将该块标为空闲。 第3章 存 储 器 管 理 3缺页中断 当要访问的页不在内存时，产生一个缺页中断，请求操作系 统将所缺页调入。该中断除了具有一般中断的保护现场、分析 中断、转中断处理程序的过程外，还具有指令执行期间产生和 处理中断而且可能多次中断的特征。比如图3-17，执行move a to b一条指令共发生6次中断。其中这条指令跨两个页面，而a、b 两个数据块也都是跨页面的。 第3章 存 储 器 管 理 图3-17 发生6次缺页中断的指令 第3章 存 储 器 管 理 4请求分页存储管理的地址变换 图3-18 请求分页存储管理地址映射 第3章 存 储 器 管 理 3.5.2 页面置换算法 1先进先出算法fifo(first in , first out) 算法的基本思想是，总是先淘汰那些驻留在内存时间最长的 页面，即先进入内存的页面先被淘汰。因为最早调入内存的页面 不再被访问的可能性最大，这种算法实现起来比较简单。设分配 给一个进程的物理块数为m，用一个由m个元素组成的队列表示 按次序存放进入内存的页面，以及一个替换指针，指向其中最早 进入的页。例如对于某进程，分配的物理块数m=3，执行时的页 面顺序为1、2、4、5、2、3、1、4，则处理时队列和指针状况如 图3-19所示。 第3章 存 储 器 管 理 先进先出算法实现简单，但是与进程实际运行的规律不适 应，一般缺页率较高，也就是说发生置换的次数较多，而这种 置换增加了系统开销。例如，从图3-19中可以看到，页面4刚被 调出，又发生缺页中断而被重新调入。 第3章 存 储 器 管 理 图3-19 fifo置换算法 第3章 存 储 器 管 理 2最优页面置换算法opr（optimal page replacement） 最优页面置换算法的思想是选择以后最远将来才会用到甚 至是以后再不会用到的页面予以置换。采用这种算法，可以保 证只发生最少页面置换次数，见图3-20。但是我们又可以看到， 因为它是依据进程将来的执行情况来决定置换对象的，而实际 的操作系统是不可能具有预知“未来”的能力的，所以说这种算法 无法由计算机实现，但是它可以作为衡量某种置换算法性能的 一个参考标准。 第3章 存 储 器 管 理 3最近最久未用置换算法lru (least recently used) 该算法的基本思想是依据局部性原理，如果某一页被访问 了，那么它很可能马上又被访问；反之，如果某一页很久没被 访问，那么最近也不会再被访问。所以这种算法的实质是当需 要置换一页时，选择在最近一段时间最久未用的页予以淘汰。 该算法的实现过程如图3-20所示，图中ri表示置换出i号页。从 图3-20中我们可以看到，采用lru置换算法，对于上述页面序列 产生了4次置换。 第3章 存 储 器 管 理 图3-20 lru置换算法与opr置换算法举例 第3章 存 储 器 管 理 lru算法能够比较普遍地适用于各种类型的程序，但是实 现起来比较困难。因为要对先前的访问历史时时加以记录和更 新，如果这种连续的修改完全由软件来做，则系统开销太大， 如果由硬件完成，会增加计算机成本。因此，在实际应用中得 到推广的是一种简单而又有效的lru近似算法。 第3章 存 储 器 管 理 4lru近似算法 这种算法在页表中设置一个“引用位”，当某页被访问时，该 位由硬件自动置“1”，而页面管理软件周期地(设周期为t)把所有 引用位置“0”。这样，在时间t内，某些被访问的页的引用位为 “1”，而未被访问过的页面的引用位为“0”。因此，根据引用位的 状态来判别各页最近的使用情况，当需要置换一个最“老”页时， 选择其引用位为“0”的页。 第3章 存 储 器 管 理 这种算法比较简单，易于实现，其缺点是周期t的大小不易 确定。t太大，会使得所有的引用位都为“1”，无法确定哪一页是 最近最久未用的页。t太小，引用位为“0”的块可能会相当多，因 而所选择页面未必是最近最久未用的页。例如，如果缺页中断刚 好发生在系统对所有引用位重置“0”之后，则几乎所有块的引用 位为“0”，因而也有可能把常用的页淘汰出去。 第3章 存 储 器 管 理 3.5.3 页面分配 1页面分配数目 既然请求分页式存储管理允许只将进程的一部分页面调入内 存即可运行，那么这一部分到底最少是多少？这个最小物理块数 是由系统的指令机制决定的。例如，单地址指令且采用直接寻址 方式所需的最少物理块数为2，其中一块是用于存放指令的页面， 而另一块则是用于存放数据的页面。如果该机器允许间接寻址时 ，则至少要求有三个物理块。对于某些功能较强的机器，其指令 长度可能是两个或多于两个字节，因而其指令本身有可能跨两个 页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。 正如前面所介绍的在缺页中断机构中要发生6次中断的情况一样， 对于这种机器，至少要为每个进程分配6个物理块，以装入6个页 面。 第3章 存 储 器 管 理 至于每个进程可允许的最大物理块数，显然取决于可用的物 理内存空间大小。还有一个问题，对于内存中的m个进程，它们 是如何分配n个空闲物理块的？一种是平均分配的策略，即每个 进程获得n/m个空闲物理块，但这种方法对于一些大进程来说不 公平，而一些小进程又会出现浪费，比如只需要5个物理块的进 程却被分配了10个物理块。另外一种是按比例分配，即按照进程 的大小按比例分配物理块，进程越大所获得的物理块越多，反之 越少。不管是平均分配还是按比例分配，对于高优先级的进程来 说，它和低优先级进程是被同样对待的，但是我们希望高优先级 的进程能够获得更多的内存物理块以保证更高速的运行，所以说 按照优先级分配应该是一种最合理的策略。 第3章 存 储 器 管 理 2分配置换策略 1) 固定分配局部置换(fixed allocation，local replacement) 为每个进程分配一固定页数的内存空间，在整个运行期间都 不再改变。采用该策略时，如果进程在运行中发现缺页，只能从 该进程在内存的n个页面中选出一页置换，保证分配给该进程的 内存物理块数不变。这种策略要求必须为每个进程分配合理的物 理块数目。若太少，会频繁地出现缺页中断，降低系统的吞吐量 ；若太多，又必然使内存中驻留的进程数目减少，进而可能造成 cpu空闲或其它资源空闲的情况，而且在实现进程对换时会花费 更多的时间。 第3章 存 储 器 管 理 2) 可变分配全局置换(variable allocation，global replacement) 先为系统中的每个进程分配一定数目的物理块，系统同时保 持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物 理块队列中取出一物理块分配给该进程，并将欲调入的缺页装入 其中。这样，凡产生缺页的进程都将获得新物理块。但当空闲物 理块队列中的物理块用完时，才会从内存中选择一页置换，该页 可能是系统中任一进程的页，这样自然又会使那个进程的物理块 减少，进而使其缺页率增加。这样系统处于一种动态的“协调”之 中，基本上可以保持一种稳定的状态。 第3章 存 储 器 管 理 3) 可变分配局部置换(variable allocation，local replacement) 系统为每个进程分配一定数目的内存物理块，另外自己保留 一定数量的空闲物理块作为调节使用。当某进程发生缺页时， 只允许从该进程在内存的页面中选出一页换出，这样就不会影 响其它进程的运行。如果进程在运行中频繁地发生缺页中断， 则系统再为该进程分配若干附加的物理块，直至进程的缺页率 降低到适当程度为止；反之，若一个进程在运行过程中的缺页 率特别低，则此时可适当减少分配给该进程的物理块，但不应 引起其缺页率的明显增加。 第3章 存 储 器 管 理 3.5.4 抖动 操作系统会对cpu的工作情况进行监督，如果发现cpu出现 空闲，它会调入新的进程来增加多道程序度（内存中并发执行的 进程数目），保持cpu的高利用率。但是在采用全局置换的方式 下，它会导致其它进程的某些页被置换出内存，而该进程执行时 会因此产生缺页，所以它又会置换另外进程的页，由此造成连锁 反应，使得整个系统中页面置换频繁发生。在每次置换过程中， 都需要启动磁盘i/o，这种低速的延迟操作会造成cpu等待，操 作系统发现cpu空闲后，又开始增加多道程序度 于是整个 系统就在进行频繁的页面置换，这种状况就称为“抖动”，它会严 重地影响到系统的性能。图3-21就显示了系统性能与多道程序度 的关系，图3-21中后半段显示了抖动的发生。 第3章 存 储 器 管 理 图3-21 抖动的发生 第3章 存 储 器 管 理 为了减少抖动的产生，保证系统性能，可以采用局部置换 的方法。发生缺页的进程不能置换其它进程的物理块，只能从 系统为自己所分配的地址空间中置换。这样当一个进程发生抖 动时，不会造成其它进程后继抖动，将抖动的影响限制在一个 小的范围内。但是，这种方法有一定的局限性，因为发生抖动 的进程会因为频繁进行磁盘i/o而形成一个等待队列，这个等待 队列也会造成正常的进程置换页面时间的增加，从而影响cpu 的吞吐量。 为了预防抖动，应该给进程尽可能提供一段时间所需的所 有页面，但系统又如何得知到底需要哪些页面呢？有多种技术 可以满足这个要求，下面介绍的工作集就是一种方法。 第3章 存 储 器 管 理 3.5.5 工作集 所谓的工作集模型是基于局部性原理，由denning提出并被 广泛采用的。工作集是指在某一时刻t，进程最近一段时间内被 访问的页面集合，表示为ws（，t），参数称为工作集的窗口 。如果某页在内存中活动，则说明它在工作集中，反之则不在工 作集中，除非它再次换入内存被访问。我们可以通过下面的例子 来看工作集的表示。 如图3-22所示的页面序列，如果=10，则t1时刻的工作集是 1，2，3，5，6，7，t2时刻的工作集是2，3，4，8。 第3章 存 储 器 管 理 图3-22 工作集模型 从这个模型中我们可以看到，工作集是和t的非减函数， 它的精确度取决于窗口尺寸的大小。如果太小，不能准确反 映局部性特征，会引起频繁的缺页置换；如果太大，可能将整 个进程全部装入，也就失去虚拟存储器管理的意义。 第3章 存 储 器 管 理 3.5.6 性能分析 请求分页存储管理保留了分页存储管理的全部优点，特别是 它较好地解决了碎片的问题。此外，还有以下优点： (1) 提供了大容量的虚拟存储器，作业地址空间不再受内存 容量的限制。 (2) 更有效地利用了内存，一个作业的地址空间不必全部都 装入内存，只装入其必要部分，其它部分根据请求装入，或者根 本就不装入(如错误处理程序等)。 (3) 更加有利于多道程序的运行，从而提高了系统效率。 (4) 虚拟存储器的使用对用户是透明的，方便了用户。 第3章 存 储 器 管 理 但请求分页还存在以下缺点： (1) 为处理缺页中断，增加了处理机时间的开销，即请求分 页系统是用时间的代价换取空间的扩大。 (2) 可能因作业地址空间过大或多道程序道数过多以及其它 原因而造成系统抖动。 (3) 为防止系统抖动所采取的各种措施会增加系统的复杂性 。 第3章 存 储 器 管 理 3.6 分段存储管理 3.6.1 分段原理 一个用户作业的程序按其逻辑结构可划分为若干段，例如主 程序段、子程序段、数据段、堆栈段等。这些段中的每一段在逻 辑上都是完整的，因此每一段都是一组逻辑信息，有自己的名字 ，且都有一段连续的地址空间。这样的分段组织便于实现段共享 和保护，便于实现动态链接和数据动态增长。 第3章 存 储 器 管 理 在分段式存储管理中，段名用段号代替，段地址从0开始编 址，因为各段的逻辑信息内容不同，所以段长度不同。这样用段 号和段内地址构成一个如图3-23所示的二维地址空间。它表示程 序最多为256段，段最大长度为64 kb。 当一个用户程序装入内存时，系统为每个段分配一个连续 的内存区域，而各个段之间可以离散存放。 图3-23 分段地址的构成 第3章 存 储 器 管 理 3.6.2 地址映射机构 表3-2 段 表 第3章 存 储 器 管 理 图3-24给出了分段存储管理的地址变换机构和工作流程（给 定逻辑地址中段号为3，段内地址为723）。 段号3与段表寄存器存放的段表长度比较以判断是否越界 ，如果越界，则转错误中断处理，否则转； 计算：段表始地址+段号段表项长度，得到段表中3号段 这一项在内存中的地址，访问该地址得到对应段基址为8 k； 8 k(段基址)+723(段内地址)=8915(物理地址)； 访问内存8915单元，得到需要的数据365。 第3章 存 储 器 管 理 图3-24 分段式地址变换过程 第3章 存 储 器 管 理 3.6.3 请求分段存储管理 我们可以看出，分段式存储分配与分页式存储分配在处理 上有非常多的相似之处，当然为了提高内存利用率，也可以采 用请求分段的存储管理方案。 首先我们看请求分段存储管理中的段表机制。 段号段长段始址状态位外存始址访问字段修改位存取方式增补位 第3章 存 储 器 管 理 其中增加的表项如下： 状态位：表示该段是否在内存。 外存始址：该段存放在外存的始地址。 访问字段：记录段的访问频度。 修改位：记录段在内存访问过程中是否被修改。若未被修 改，则可以将该段所占内存空间直接释放；若被修改，则首先 应将该段中的内容记录到对换区中，再将所占内存空间释放。 第3章 存 储 器 管 理 存取方式：表示该段是只读、只执行或者可读/写。 增补位：表示该段执行过程中