《计算机操作系统原理培训及实操第3章.pdf》由会员分享，可在线阅读，更多相关《计算机操作系统原理培训及实操第3章.pdf（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 存 储 器 管 理第第3 3章章 存存 储储 器器 管管 理理3.1 存储管理概述存储管理概述3.2 分区式存储管理分区式存储管理3.3 覆盖和对换覆盖和对换3.4 分页存储管理分页存储管理3.5 请求分页存储管理请求分页存储管理3.6 分段存储管理分段存储管理3.7 段页式存储管理段页式存储管理第3章 存 储 器 管 理3.1 存储管理概述存储管理概述3.1.1 存储管理的概念存储管理的概念 在计算机的发展历程中，不管是单道程序系统，还是多道程序系统，内存利用始终是一个重要环节。在计算机工作时，程序处理的典型过程是这样的，首先CPU通过程序计数器中的值从内存中取得相应的指令，指令被译
2、码后根据要求可能会从存储器中再取得操作数。对操作数处理完成后，操作结果又会存储到存储器中。在这个过程中，操作系统需要保证程序执行中按照适当的顺序从正确的存储器单元中存取指令或者数据，也就是说有效管理存储器的存储空间，根据地址实现上述任务。第3章 存 储 器 管 理 大容量的内存是我们一直追求和努力的目标，我们看到CPU由8086到286、386、486，直到目前的P4，内存标准配置也由512 KB到1 MB、2 MB、4 MB，直到现在的256 MB或者更高，甚至有些计算机主板支持的内存容量达到2 GB以上。但不管如何，内存管理的主要任务仍然是合理地建立用户程序与内存空间的对应关系，为各道程序
3、分配内存空间，运行完成后再予以回收，而且始终要保证系统程序和各用户程序安全。简单地说，内存管理包括地址映射、内存分配和内存保护功能。虽然现在内存的容量在不断加大，但价格却不断下降，有资料表明，10年前的内存价格相当于现在的500倍。但是用户程序的规模也在成百上千倍地增长，对内存容量的要求似乎没有上限，所以就要求内存管理能够提供内存扩充功能，即利用单位价格更为便宜的外存来模拟为内存，让用户透明使用。这就是内存管理的虚拟功能。第3章 存 储 器 管 理3.1.2 地址重定位地址重定位 1地址空间和存储空间地址空间和存储空间 在我们用汇编语言或高级语言编写程序时，总是通过符号名来访问某一单元。我们把
4、程序中由符号名组成的空间称为名空间。源程序经过汇编或编译并再经过链接编辑程序所装配形成的程序，通常是以0为基址进行顺序编址，或者是分成若干个部分，每个部分以0为基址，这样的地址表示形式称为相对地址,也叫做逻辑地址或虚地址，把该程序逻辑地址组成的集合叫做程序的逻辑地址空间(简称地址空间)。而在存储器中每个具体存储单元都有不同的编号，每个编号就是一个物理地址，整个程序在内存中存储后所占用的物理地址的集合形成程序的物理地址空间(简称存储空间)。程序的名空间、地址空间和存储空间的关系如图3-1所示。第3章 存 储 器 管 理图3-1 名空间、地址空间和存储空间的关系Goto L1L1：源程序编译Got
5、o 2目标代码0123名空间地址空间装入Goto a2内存(运行程序)aa1存储空间a2第3章 存 储 器 管 理 2地址的重定位地址的重定位 当一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，需要进行地址映射，即地址的重定位。地址重定位有两种方式：静态重定位和动态重定位。静态重定位是在程序装入内存，开始执行之前进行地址重定位。静态重定位工作通常是由装配程序完成的，其过程如图3-2所示。第3章 存 储 器 管 理图3-2 静态重定位Load ah,7810783651000Load ah,10781001相对地址装入装入模块内存绝对地址1078365第3章 存 储 器 管 理
6、静态地址重定位的优点是容易实现，无需硬件支持，它只要求程序本身是可重定位的，即对那些要修改的地址部分具有某种标识，地址重定位由专门设计的程序来完成。在早期的操作系统中大多数都采用这种方法。其主要缺点是程序经地址重定位后就不能移动了，因而不能重新分配内存，不利于内存的有效利用。第3章 存 储 器 管 理 动态地址重定位是在程序执行期间，在每次存储访问之前进行的。在这种情况下，通常通过基地址寄存器、变址寄存器计算出指令的有效地址，再利用硬件机构实现地址映射，这样的硬件设备称为存储管理单元MMU(Memory-Management Unit)。通常采用的办法是利用一个重定位寄存器，对每一个有效地址都
7、要加上重定位寄存器中的内容，以形成绝对地址。在图3-3中，把某一相对地址程序装入地址1000开始的内存区域时，只要把1000装入重定位寄存器，程序即可运行。这一动态地址重定位的过程如图3-3所示。第3章 存 储 器 管 理图3-3 动态重定位 动态地址重定位的优点是程序在内存中的搬移不会对程序的正确执行造成影响，使内存得以被充分利用，其缺点是需要附加的硬件支持，实现存储管理的软件算法比较复杂。Load ah,7810783651000Load ah,7810011078365相对地址装入模块781 000重定位寄存器第3章 存 储 器 管 理3.1.3 虚拟存储器概念的引入虚拟存储器概念的引入
8、 前已述及，一方面用户程序越来越大，所要求的内存存储空间相应越来越大，但内存的增长却相对有限；另外一方面，外存又存在着容量远远超过内存容量的剩余空闲区域。所以，寻求一系列措施，使用户可以将外存的一部分区域（我们称之为辅存）当作内存来使用，就成为一种有效的选择方式。但这种使用方式对用户来说应该是透明的，即用户不知道也不用知道当前自己到底使用的是内存还是外存。这样，用户就是在使用一个比实际内存储器大得多的存储器，把这个存储器叫做虚拟存储器。在虚拟存储器系统中主要介绍具体的请求分页存储管理方式和请求分段存储管理方式。第3章 存 储 器 管 理3.2 分区式存储管理分区式存储管理3.2.1 单一连续分
9、配单一连续分配 单一连续分配是一种简单的存储分配方案，主要用于单用户单任务操作系统。它的实现方案如下：(1)内存分配：整个内存划分为系统区和用户区。系统区是操作系统专用区，不允许用户程序直接访问，一般在内存低地址部分，剩余的其它内存区域为用户区。一道用户程序独占用户区，如图3-4所示。注意：内存区一般划分为系统区和用户区，本章我们所述及的内存分配与回收都指用户区的分配与回收，除非特别说明。第3章 存 储 器 管 理图3-4 内存划分进程1OS系统区用户区第3章 存 储 器 管 理 (1)内存分配：整个内存划分为系统区和用户区。系统区是操作系统专用区，不允许用户程序直接访问，一般在内存低地址部分
10、，剩余的其它内存区域为用户区。一道用户程序独占用户区，如图3-4所示。注意：内存区一般划分为系统区和用户区，本章我们所述及的内存分配与回收都指用户区的分配与回收，除非特别说明。(2)地址映射：物理地址=用户区基地址+逻辑地址。第3章 存 储 器 管 理 (3)内存保护：通过基址寄存器保证用户程序不会从系统区开始；另外系统需要一个界限寄存器，里边存储程序逻辑地址范围，若需要进行映射的逻辑地址超过了界限寄存器中的值，则产生一个越界中断信号送CPU。单一连续分配方案的优点是方法简单，易于实现；缺点是它仅适用于单道程序，因而不能使处理机和内存得到充分利用。第3章 存 储 器 管 理3.2.2 固定式分
11、区分配固定式分区分配 随着多道程序设计的出现和发展，存储管理技术也得到极大的发展。多道程序存在于一个存储器中，如何实现分配、保护、访问变得越来越复杂。于是分区式存储管理应运而生，逐步形成了固定式分区分配、动态分区分配和动态重定位分区分配等不同策略。固定式分区分配的“固定”主要体现在系统的分区数目固定和分区的大小固定两个方面。方案的主要内容为：第3章 存 储 器 管 理 (1)内存分配/回收：根据不同的内存容量划分策略有两类情况：一类是内存等分为多个大小一样的分区，这种方法主要适用于一些控制多个同类对象的环境，各对象由一道存在于一个分区的进程控制，但是对于程序规模差异较大的多道环境不太适合，比如
12、大于分区大小的进程无法装入，而且小进程也会占用一个分区，造成内存碎片（即无法被利用的空闲存储空间）太大。另一类是将内存划分为少量大分区，适量的中等分区和多个小分区，这样可以有效地改善前一种方法的缺陷。第3章 存 储 器 管 理表表3-1 分分 区区 说说 明明 表表分区号分区大小（KB）分区始址（k）状态12051240251350650第3章 存 储 器 管 理 在分区说明表中查找状态为空闲（可以用“0”表示空闲，“1”表示非空）且大小满足要求的分区予以分配，然后修改分区说明表中的对应项。当该进程结束后，再将分区说明表中对应项的“状态”修改为“0”，就表示对它所占用的分区予以回收，而回收后的
13、分区又可以作为空闲分区分配给其它的申请进程。第3章 存 储 器 管 理图3-5 各个分区的碎片分区1 100 KB分区2 150 KB分区3 250 KB分区4 250 KB分区5 250 KB程序4 100 KB程序5 50 KB程序1 20 KB程序2 30 KB程序3 50 KB第3章 存 储 器 管 理 (2)地址映射：物理地址=分区始址+逻辑地址。(3)内存保护：分区始地址保证了各道程序不会由其它程序所在分区开始，另外逻辑地址与所给分区大小相比较，保证不会超过该分区而进入其它分区。固定式分区分配的缺点是内存空间的利用率低，因为基本上每个分区都会有碎片存在，尤其是某些大分区中只是存放一
14、道小进程时。例如图3-5，5道进程大小总和为250 KB，但是所占5个分区总容量却达到1000 KB，内存空间利用率仅达到25%。所以说固定式分区分配对每个分区很难做到“物尽其用”，会形成内存碎片，导致内存浪费严重。第3章 存 储 器 管 理3.2.3 动态分区分配动态分区分配 为了改善固定分区分配给系统带来的内存碎片太大、空间浪费严重的缺陷，提出了动态分区分配，也叫做可变式分区分配的策略，即根据进程的实际需求动态地划分内存的分区方法。它是在进程装入和处理过程中建立分区，并要使分区的容量能正好适应进程的大小。而整个内存分区数目随着进程数目的变化而动态改变，各个分区的大小随着各个进程的大小各有不
15、同，所以称之为动态分区分配。1动态分区的分配过程动态分区的分配过程 在动态分区分配中，各个空闲分区通过指针形成链，称为空闲分区链，它是系统动态分区分配所需要的一种重要数据结构，格式如图3-6所示。基于空闲分区链和分区说明表，系统按照图3-7所示流程实现分区分配。第3章 存 储 器 管 理图3-6 空闲分区链前向指针N20后向指针N20第3章 存 储 器 管 理图3-7 动态分区流程空闲分区大于程序大小?查找空闲分区链空闲分区程序大小规定剩余大小?该空闲区分给申请程序从该分区划分出申请空间找完?YYNN无法分配Y修改分区说明表、空闲链返回N第3章 存 储 器 管 理 2动态分区分配算法动态分区分
16、配算法 动态分区分配算法有以下几种。1)首次适应算法（FF,First Fit）空闲分区链以地址递增的顺序链接，分配时从链首开始查找，找到第一个大小可以满足的分区为止，从其中划分出所需空间分配给申请的进程，剩余部分仍旧作为一个分区保留在空闲分区链中，否则给出无法分配的提示。采用这种方法时，每次分配都需要从链首也就是低地址开始查找，所以低地址由于被划分的可能性比较大，容易形成多个过小分区而难以利用，成为外部碎片（前面所描述的在每个分区内的“碎片”相应称为内部碎片）。同时这些小分区增加了查寻时的判断时间，降低了效率。第3章 存 储 器 管 理 2)循环首次适应算法 为了改变首次适应算法每次从链首开
17、始查寻造成的缺陷，可以增加一个起始查寻指针，指向下一次开始查寻时的起始分区，在查寻过程中，该指针向后移动，当移动到最后一个空闲分区后，重新回到链首。找到适当分区后，按首次适应算法的划分分区方式进行。这种方法可以使内存区分配比较平均，减少查寻次数，但又造成了缺少大空闲分区，使得大进程无法进入。第3章 存 储 器 管 理 3)最佳适应算法 空闲分区链按照分区容量递增的方式形成，分配时从链首开始查找，这样找到的第一个大小可以满足的分区肯定是与进程申请空间大小最接近，甚至是完全吻合的分区，而且平均查找次数为分区数的一半，也就是说它是“最佳适应”的。但这种方法所造成的剩余分区又肯定是相对最小的，通常难以
18、利用，甚至我们可以说，每次分配一个分区都会造成一个无法再利用的“碎片”，而这些“碎片”的总容量可能是比较大的。第3章 存 储 器 管 理 4)最差适应算法 “最差”当然不是指这种算法的性能最差，否则我们就没有必要把它提出来了，相反在某种情况下，它却是一种性能“最佳”的算法。其实现思想是这样的，空闲分区链按照分区容量递减的方式形成，分配时从链首开始，若链首分区大小不满足，则可以肯定不存在能够满足要求的分区；否则对链首分区进行划分，剩余空间成为“碎片”的可能性肯定是最小的。所以说，最差适应算法具有查找速度快，分区碎片少的优点，但又会产生缺少大分区的缺点。第3章 存 储 器 管 理 在这几种分配算法
19、中，一般情况下，首次适应算法是最简单，而且是最快和最好的算法。循环首次适应算法比首次适应算法稍差一些，而最佳适应算法虽然名字中有“最佳”，但实际上是性能最差的。但在某些应用情况下，上述比较结果会有所变化。第3章 存 储 器 管 理3动态分区的回收动态分区的回收图3-8 动态分区的回收M1回收区M2回收M1空白区M2(a)M1回收区M2回收M1M2(b)M1回收区M2回收M1M2(c)M1回收区M2回收M1(d)第3章 存 储 器 管 理 (a)M1、M2都非空，将回收区直接记录在空闲分区表或者插入空闲分区链中。(b)M1为空，M2非空，则首先将M1与回收区合并，修改M1大小为其原大小与回收区之
20、和。(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的程序。为了解决类似问题，我们采用一种称为“紧凑”的方法，通过移动程序将原来分散的空闲小分区拼接为一个大的分区，就可以使某些比较大
21、的进程进入，如图3-9（b）所示。一般情况下，当某进程因为没有足够大的分区，而所有“碎片”之和又大于进程大小时将进行“紧凑”。第3章 存 储 器 管 理图3-9 紧凑系统区程序A5 KB程序B3 KB程序C2 KB紧凑系统区程序A程序B程序C10 KB(a)(b)第3章 存 储 器 管 理 请思考：可否每分配或者回收一个分区就进行紧凑？采用内存“紧凑”以后，由于程序和数据的位置都发生了变化，如果不进行相应的地址修改，则程序就无法执行。所以必须要采用3.1.2节介绍的动态重定位方法来进行地址映射，于是称这种方案为动态重定位分区分配。动态重定位分区分配算法实际上是在动态分区分配算法中增加了“紧凑”
22、环节，即无法找到满足大小的分区时，进行“紧凑”之后再进行分区分配。第3章 存 储 器 管 理3.2.5 分区分配方案的评价分区分配方案的评价 在分区分配方案中，地址映射都遵循“物理地址=分区始地址+逻辑地址”，固定分区分配与动态分区分配的分区始地址都来自于硬件“基址寄存器”，动态重定位分区分配的分区始地址来自于“重定位寄存器”。内存保护由“基址寄存器”和“限长寄存器”共同实现，也可以用一对下限寄存器和上限寄存器来实现，一旦超过限长，则发出越界中断信号。分区分配方案的主要优点可归纳如下：(1)多道程序下的内存共享，改善了系统吞吐量，在内存利用率方面，从固定式分区到动态分区，再到动态重定位分区依次
23、提高。第3章 存 储 器 管 理 (2)相对于后面介绍的存储管理方式，为实现分区分配所使用的数据结构占用的存储容量相对较少，算法也相对简单。(3)实现存储保护的措施也比较简单。第3章 存 储 器 管 理 分区分配的主要缺点有：(1)内存仍不能充分利用，除了动态重定位式分区法外，都存在着严重的碎片问题。(2)不能实现对内存的扩充，因此进程的大小受到内存可用空间的限制。(3)与单一连续分配一样，要求一个进程在执行之前必须全部装入内存，因此在内存中可能包含不会被使用的信息。(4)“紧凑”提高了内存利用率，但是进程移动所产生的额外开销增加了CPU的负担。(5)几个并行进程之间不能共享存入内存的单一信息
24、副本(如公用子程序、数据段等)。第3章 存 储 器 管 理3.3 覆覆 盖盖 和和 对对 换换3.3.1 覆盖覆盖(Overlay)覆盖技术的基本思想是将内存的同一区域按照使用的先后顺序，分配给几个不同进程或一个进程的几个程序段或数据段，即允许进程运行时，可以不用把它的所有程序段都调入内存，当进程处理需要某程序段时将它装入到原来已经占用的某分区中，原来存储在这个分区中的程序就被“覆盖”了。第3章 存 储 器 管 理 采用覆盖技术后，进程可以分为常驻内存部分和覆盖部分，常驻内存部分是指进程处理过程中始终需要的程序段，而覆盖部分是进程处理过程中动态调入内存的程序段。这样，当进程要求运行时，系统根据
25、其覆盖结构，给它分配一段存储空间，其大小等于常驻部分和覆盖区之和。覆盖区长度由相应覆盖段中最大程序段的长度确定。处理过程是先把常驻内存部分调入，然后将首先需要的可覆盖程序段由辅存调入，随着进程执行，再将其它存放在辅存的覆盖部分陆续调入。第3章 存 储 器 管 理 我们看到，采用覆盖技术后，就可以用小于进程申请大小的内存空间来满足一个进程的处理空间，有效地利用内存。但采用覆盖技术存在以下缺点：(1)用户难以预知他的程序的覆盖情况，尤其是通过合作设计实现大型软件系统，基本上程序员不能保证十分熟悉整个程序，而在小程序中是不需要采用覆盖技术的。(2)用户只能有效地利用自己程序所占用的内存，而不能对整个
26、内存加以有效利用。(3)各进程占用的分区仍会存在碎片。第3章 存 储 器 管 理3.3.2 对换对换(Swapping)所谓对换，就是把内存中暂时无法运行的进程或者暂时不需要的程序、数据写入辅存，并将具备运行条件的进程或者需要的程序、数据从辅存读入内存。采用对换技术可以很好地提高内存的利用率和CPU的处理效率。在引入对换技术的存储管理系统中，外存被划分为两个部分，一部分是文件区，另外一部分是对换区（Swapping Area）。对换区用来暂时存放对换的进程或者程序、数据，对它的磁盘I/O速度比文件区要快。因为对换技术重在频繁的交换操作中保证换入换出的速度，而对磁盘利用率不作严格要求，所以对辅存
27、对换区存储空间的管理采用连续分配，它的分配与回收与动态分区分配类似。第3章 存 储 器 管 理3.4 分页存储管理分页存储管理3.4.1 分页原理分页原理 我们把逻辑地址空间划分为一些相等的片，这些片称为页或页面。同样，物理地址空间也被划分为同样大小的片，称为块。这样用户程序进入内存时，就可以一页对应存入到一个块中。对整个程序来说，只有可能在最后一块存在碎片（称为页内碎片），而且碎片大小不会超过一块，所以内存利用率可以大大提高。第3章 存 储 器 管 理 页面(或块)的大小由系统硬件地址结构规定，通常是2的幂，例如1 KB、2 KB、4 KB等。这样的规定可以使地址映射容易实现，后面的例子可以
28、帮助我们理解这个问题。页面不能过大，也不能过小。过小会造成页面过多，页表过长，页表又会占用较大的内存空间，而且在虚拟存储中增加了页面换入换出次数，增加了系统开销；过大又会造成页内碎片太大，内存利用率不高。早期的页面大小一般都在512 B4 KB，随着计算机性能的提高，现在一般在2 KB8 KB，甚至有的系统支持多种页面大小，比如Solaris就有4 KB和8 KB两种页面。第3章 存 储 器 管 理图3-10 分页式存储管理的系统地址结构页号页内偏移量3112 110第3章 存 储 器 管 理 在这个完整的地址结构中，对页号、页内偏移量（也叫页内地址）位数的确定，我们通过一个例子说明。比如对于
29、一个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位为
30、页内地址，剩余高位是页号。把这两部分换算为十进制，我们可以验算出通过上述公式计算的结果的正确性。图3-11 页号与页内偏移量举例0000 0000 0000 0000 01101101 0111 10002802463448第3章 存 储 器 管 理3.4.2 分页存储分配与回收算法分页存储分配与回收算法 实现分页存储管理需要如下的数据结构：页面映射表PMT：也称页表。每个进程一张，用于该进程的地址映射，记录了进程每个页号及其对应的存储块号。存储分块表MBT：整个系统一张，记录每个存储块及其状态（已分配或空闲）。图3-12给出了上述两种表格的结构及其关系。当有一个进程进入系统时，为页表分配一个
31、存储区，然后搜索存储分块表，查看有哪些存储块是空闲的，如有空闲的存储块，则将存储块号填入页表。当该进程所需的块数都分配完后，系统便可按照PMT的内容对该进程进行处理。第3章 存 储 器 管 理图3-12 页表、存储分块表及其关系页号012块号103920号页表1号页表页号01块号953块号0状态03191101存储分块表第3章 存 储 器 管 理 当某个进程因为结束或者其它一些原因退出系统，则归还原来所占用的物理块。首先修改存储分块表，将归还的物理块块号在表中的状态栏改为空闲标志，然后释放该进程页表所占用的空间。第3章 存 储 器 管 理3.4.3 地址映射机构地址映射机构 1动态地址映射机构
32、动态地址映射机构 分页存储管理中，由于页和块大小是一致的，每页的页内地址与物理块的块内单元地址也完全一致，所以在逻辑地址到物理地址的映射中，主要从一个页找到对应的内存块，而这种页与块的对应关系是页表记录的。每个进程调度时，从该进程PCB中取得页表始址和页表长度（页表长度指页表的项数），装入到系统中设置的一个页表寄存器PTR内。图3-13给出了分页存储管理的地址变换机构和工作流程（页大小为1024 B，给定逻辑地址3795，即页号为3，页内地址为723）。第3章 存 储 器 管 理图3-13 分页式地址变换过程页表始址页表长度页表寄存器页号3页内地址723越界中断111024723页号块号016
33、15425311RRiR3i365物理地址1198711987内存内存中的页表逻辑地址3795第3章 存 储 器 管 理 页号3与页表寄存器中的页表长度比较判断是否越界，如果越界，则转错误中断处理，否则转；页表中该项在内存中的对应地址=页表始地址R+页号3页表项长度i，访问该地址R+3i，得到物理块号11；11(页号)1024(页大小)+723(页内地址)=11987(物理地址)；访问内存11987单元，得到需要的数据365。第3章 存 储 器 管 理 2联想存储器联想存储器 页表存放在内存中，由操作系统实施管理，在进程执行时，每一条指令的执行都必须进行地址映射。因此，每条指令都必须两次访问内
34、存储器：一次是访问页表，由页号找到对应的物理块号，另一次是在物理地址中实际存取所要的数据或指令。这样就增加了指令执行的机器时间，影响了计算机的速度。为了加快查表速度，在地址映射机构中加入一组高速寄存器(8个或16个)，构成了一个容量较小的存储器，称之为联想存储器，也称快表。在联想存储器中，存放正在运行进程的当前最常用的页号和相应块号，这个联想存储器具有并行查询能力，而且查找速度可以做到比一般磁芯存储器的速度快一个数量级。图3-14给出了利用联想存储器加速查表的过程。第3章 存 储 器 管 理图3-14 引入快表的地址映射页表始址页表长度页表寄存器页号页内地址越界中断 b365物理地址内存逻辑地
35、址页号块号b内存页号块号b快表第3章 存 储 器 管 理 在采用联想存储器的系统中，先按给出的页号检索联想存储器，一旦检索到所要的块号，就利用联想存储器给出的块号访问内存，即在图3-14中走一条的路径。如果在联想存储器中检索不到所要的块号，应利用PMT表进行查找，并将页号以及所对应的块号一起填入联想存储器内的空白单元中。如果没有空白单元，应根据某种规则(如先进先出)淘汰一个单元内容后再行填入，即在图3-14中走一条的路径。在多道程序系统中，当把处理的控制权由一道进程转到另一道进程时，相应地把页表寄存器(PTR)以及联想存储器内容加以更换。第3章 存 储 器 管 理3.4.4 多级页表多级页表
36、对于现代的计算机系统来说，所支持的逻辑地址空间越来越大，已达232264。按照前面介绍的方法，所形成的页表将会非常庞大并占用大量的内存空间。例如一个32位的系统，页面大小为4 KB，则页表项数达到1 M项，如果每项占用4 B，则页表会占用4 MB空间，而且是连续的4 MB空间。在多道程序环境下，这是一个过于苛刻的要求。一种解决办法就是对页表本身再分页，形成两级页表。比如对于上边的例子，以前是将逻辑地址分成两部分，低12位为页内地址，剩余高20位为页号。现在我们将这个20位的页号再分成两部分，10位外层页号和10位内层页号，如图3-15所示。第3章 存 储 器 管 理图3-15 多级页表结构地址
37、外层页号内层页号页内偏移量3122 2112 110第3章 存 储 器 管 理图3-16 两级页表外层页表页号块号07814321920号内层页表(78号块)页号块号010132921号内层页表(43号块)页号块号09153存储分块表块号状态003191101第3章 存 储 器 管 理3.4.5 分页存储管理方案的评价分页存储管理方案的评价 综上所述，分页存储管理便于多道程序设计，提高了内存的利用率，而不必像动态分区分配那样执行紧凑操作。但分页存储管理仍然存在如下严重缺点：(1)采用动态地址映射会增加计算机成本和降低处理机的速度。(2)各种表格要占用一定容量的内存空间，而且还要花费一部分处理机
38、时间来建立和管理这些表格。第3章 存 储 器 管 理 (3)虽然消除了大量碎片，但每个作业的最后一页一般都有不能充分利用的空白区。例如，假定页面大小为4 KB，如果某一作业需要9 KB内存，则应该为它分配三个物理存储块，最后一块的3 KB空间被浪费了。如果减少页面大小，使页面大小为2 KB，则对于需要9 KB内存的作业应分配5个存储块，其中有1 KB的内存被浪费了。减少页面大小，可以减少内存的浪费，但页表的长度又增加了，这也是一个矛盾。(4)存储扩充问题仍未得到解决。当没有足够空间能装下整个作业地址空间时，该作业还是无法运行。第3章 存 储 器 管 理3.5 请求分页存储管理请求分页存储管理3
39、.5.1 请求分页原理请求分页原理 1局部性特征局部性特征 在多道程序环境下，可能有一些程序因为内存空间不够无法装入，而已被装入内存的程序是否被充分执行呢？1968年，P.Denning就指出，程序执行时呈现出局部性特征，表现为：(1)时间局部性。程序中大量的循环结构和各种数据结构，使某段程序一旦执行，很快又会被再次执行，某数据结构被访问后，可能在短时间内再次被访问。第3章 存 储 器 管 理 (2)空间局部性。程序顺序执行和局部存储的连续性，使程序访问某存储单元后，与它临近的存储单元会被访问。通过这样分析，我们了解到程序只需要将当前必须的一部分内容存在于内存中就可以开始执行，随着向前推进，再
40、将所需的其它内容调入。但是在调入时，可能出现内存不够的情况，这样就要采用3.3节介绍的技术对换。在请求分页管理中，对换的对象是页。第3章 存 储 器 管 理 2请求分页存储管理的页表请求分页存储管理的页表 现在一个新问题是程序执行一段时间后，系统是如何知道所需的页不在内存而需调入呢？系统通过检查带有状态项的页表判断该页是否在内存。该页表结构为：页号块号状态位外存地址访问字段修改位第3章 存 储 器 管 理 其中增加的表项如下：状态位：表示该页是否在内存。外存地址：该页存放在外存的地址，也就是存放在外存的块号。访问字段：记录该页的访问频度，作为置换的参考依据。修改位：记录该页在内存访问过程中是否
41、被修改。若未被修改，则可以将该块直接标为空闲；若被修改，则首先应将该块中的内容记录到对换区中，再将该块标为空闲。第3章 存 储 器 管 理 3缺页中断缺页中断 当要访问的页不在内存时，产生一个缺页中断，请求操作系统将所缺页调入。该中断除了具有一般中断的保护现场、分析中断、转中断处理程序的过程外，还具有指令执行期间产生和处理中断而且可能多次中断的特征。比如图3-17，执行Move a to b一条指令共发生6次中断。其中这条指令跨两个页面，而a、b两个数据块也都是跨页面的。第3章 存 储 器 管 理图3-17 发生6次缺页中断的指令a123456Move a to bb第3章 存 储 器 管 理
42、4请求分页存储管理的地址变换请求分页存储管理的地址变换图3-18 请求分页存储管理地址映射访问内存完成该指令执行下一条指令Y硬件完成软件完成该页在内存?计算页号、页内地址启动要处理的指令N保护现场有空闲页面?Y分配并调入所需页修改页表恢复现场启动被中断指令选择一页淘汰修改页表该页修改过?该页写回到外存NNY第3章 存 储 器 管 理3.5.2 页面置换算法页面置换算法 1先进先出算法先进先出算法FIFO(First In,First Out)算法的基本思想是，总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被淘汰。因为最早调入内存的页面不再被访问的可能性最大，这种算法实现起来比较简
43、单。设分配给一个进程的物理块数为m，用一个由m个元素组成的队列表示按次序存放进入内存的页面，以及一个替换指针，指向其中最早进入的页。例如对于某进程，分配的物理块数m=3，执行时的页面顺序为1、2、4、5、2、3、1、4，则处理时队列和指针状况如图3-19所示。第3章 存 储 器 管 理 先进先出算法实现简单，但是与进程实际运行的规律不适应，一般缺页率较高，也就是说发生置换的次数较多，而这种置换增加了系统开销。例如，从图3-19中可以看到，页面4刚被调出，又发生缺页中断而被重新调入。第3章 存 储 器 管 理图3-19 FIFO置换算法装入前3页置换存在，不置换置换置换置换第3章 存 储 器 管
44、 理 2最优页面置换算法最优页面置换算法OPR（Optimal Page Replacement）最优页面置换算法的思想是选择以后最远将来才会用到甚至是以后再不会用到的页面予以置换。采用这种算法，可以保证只发生最少页面置换次数，见图3-20。但是我们又可以看到，因为它是依据进程将来的执行情况来决定置换对象的，而实际的操作系统是不可能具有预知“未来”的能力的，所以说这种算法无法由计算机实现，但是它可以作为衡量某种置换算法性能的一个参考标准。第3章 存 储 器 管 理 3最近最久未用置换算法最近最久未用置换算法LRU(Least Recently Used)该算法的基本思想是依据局部性原理，如果某
45、一页被访问了，那么它很可能马上又被访问；反之，如果某一页很久没被访问，那么最近也不会再被访问。所以这种算法的实质是当需要置换一页时，选择在最近一段时间最久未用的页予以淘汰。该算法的实现过程如图3-20所示，图中Ri表示置换出i号页。从图3-20中我们可以看到，采用LRU置换算法，对于上述页面序列产生了4次置换。第3章 存 储 器 管 理图3-20 LRU置换算法与OPR置换算法举例页面序列：11LRU21241245245R12452352312314314R4R5R21OPR12124512R4512513513413R2R5第3章 存 储 器 管 理 LRU算法能够比较普遍地适用于各种类型
46、的程序，但是实现起来比较困难。因为要对先前的访问历史时时加以记录和更新，如果这种连续的修改完全由软件来做，则系统开销太大，如果由硬件完成，会增加计算机成本。因此，在实际应用中得到推广的是一种简单而又有效的LRU近似算法。第3章 存 储 器 管 理 4LRU近似算法近似算法 这种算法在页表中设置一个“引用位”，当某页被访问时，该位由硬件自动置“1”，而页面管理软件周期地(设周期为T)把所有引用位置“0”。这样，在时间T内，某些被访问的页的引用位为“1”，而未被访问过的页面的引用位为“0”。因此，根据引用位的状态来判别各页最近的使用情况，当需要置换一个最“老”页时，选择其引用位为“0”的页。第3章
47、 存 储 器 管 理 这种算法比较简单，易于实现，其缺点是周期T的大小不易确定。T太大，会使得所有的引用位都为“1”，无法确定哪一页是最近最久未用的页。T太小，引用位为“0”的块可能会相当多，因而所选择页面未必是最近最久未用的页。例如，如果缺页中断刚好发生在系统对所有引用位重置“0”之后，则几乎所有块的引用位为“0”，因而也有可能把常用的页淘汰出去。第3章 存 储 器 管 理3.5.3 页面分配页面分配 1页面分配数目页面分配数目 既然请求分页式存储管理允许只将进程的一部分页面调入内存即可运行，那么这一部分到底最少是多少？这个最小物理块数是由系统的指令机制决定的。例如，单地址指令且采用直接寻址
48、方式所需的最少物理块数为2，其中一块是用于存放指令的页面，而另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。正如前面所介绍的在缺页中断机构中要发生6次中断的情况一样，对于这种机器，至少要为每个进程分配6个物理块，以装入6个页面。第3章 存 储 器 管 理 至于每个进程可允许的最大物理块数，显然取决于可用的物理内存空间大小。还有一个问题，对于内存中的m个进程，它们是如何分配n个空闲物理块的？一种是平均分配的策略，即每个进程获
49、得n/m个空闲物理块，但这种方法对于一些大进程来说不公平，而一些小进程又会出现浪费，比如只需要5个物理块的进程却被分配了10个物理块。另外一种是按比例分配，即按照进程的大小按比例分配物理块，进程越大所获得的物理块越多，反之越少。不管是平均分配还是按比例分配，对于高优先级的进程来说，它和低优先级进程是被同样对待的，但是我们希望高优先级的进程能够获得更多的内存物理块以保证更高速的运行，所以说按照优先级分配应该是一种最合理的策略。第3章 存 储 器 管 理 2分配置换策略分配置换策略 1)固定分配局部置换(Fixed Allocation，Local Replacement)为每个进程分配一固定页数
50、的内存空间，在整个运行期间都不再改变。采用该策略时，如果进程在运行中发现缺页，只能从该进程在内存的n个页面中选出一页置换，保证分配给该进程的内存物理块数不变。这种策略要求必须为每个进程分配合理的物理块数目。若太少，会频繁地出现缺页中断，降低系统的吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而可能造成CPU空闲或其它资源空闲的情况，而且在实现进程对换时会花费更多的时间。第3章 存 储 器 管 理 2)可变分配全局置换(Variable Allocation，Global Replacement)先为系统中的每个进程分配一定数目的物理块，系统同时保持一个空闲物理块队列。当某进程发现缺页时，