《操作系统（OS）》课件-第三章

第三章存储器管理学习目标1.理解计算机系统的存储体系，掌握操作系统存储管理的目的和任务。2.理解并掌握各种存储管理方法的管理思想和手段，熟练掌握相应的地址重定位方法、辨析其优缺点。3.了解覆盖与对换技术的原理。学习目标4.理解虚拟存储管理技术的原理，熟练掌握页式虚拟存储管理的管理思想和手段、地址重定位机构及计算方法、常用页面置换策略及其效率分析。5.理解虚拟存储管理中相关的软件策略。目录3.1存储器管理概述3.2重定位3.3存储器管理技术3.4分区管理技术3.5分页存储管理3.6分段存储管理3.7段页式存储管理3.8虚拟存储器管理3.9常用的页面置换算法3.10虚拟存储管理中的软件策略3.1.1存储器管理的目的3.1.2存储器管理的任务3.1存储器管理概述计算机的用户对存储器的需求归纳起来只有两点，一是够用，二是安全。从操作系统的资源管理者角度来看，存储器管理的目的是有效地组织和管理存储空间、提高存储器的利用率。3.1.1存储器管理的目的1.主存分配与回收2.地址映射3.主存保护4.信息共享5.主存扩充3.1.2存储器管理的任务为充分利用主存空间，尤其是在多道程序设计的环境中，最关键的工作之一就是选取适当的存储划分原则，不同的划分原则下，主存分配和回收方法以及为具体实现时系统所要维护的数据结构也不同，如分页、分段或段页结合的存储方案。1.主存分配与回收地址映射也称地址变换，或重定位。存储管理要完成用户地址空间中的地址与主存存储空间地址的变换，地址变换可以在程序执行前就完成，也可以一边执行根据需要再进行变换，即静态重定位和动态重定位，不同的方法所需的系统硬件结构和软件方法也不同。2.地址映射在多道程序设计环境中，主存中同时驻留多道作业或者说多个进程，为了确保它们彼此之间在空间访问上不互相干扰，或是出现非法访问造成不可预知的错误，要求系统必须具备主存保护的功能。主存保护的方法主要有上下界保护法和键保护法。3.主存保护也称为界地址法，是利用2个专门寄存器分别保存当前进程的主存起始地址（上界）和结束地址（下界），当有地址访问发生时，主存保护机构自动进行合法性检查。（1）上下界保护法（1）上下界保护法100K500K受保护的程序或数据……100K500K上界寄存器下界寄存器内存合法访问100K≤访问地址﹤500K键保护法是指作业装入主存的同时就根据它的权限赋予一个键值，当地址访问发生时，主存保护机构对作业持有的键值与其欲访问的主存区域的键值相比较，相同则是合法的，否则将拒绝。（2）键保护法（2）键保护法键2K6K4K……0RW2W内存…2…当前PSW正确访问

LOAD15000STORE25200非法访问

LOAD13000保护键在多道环境中各作业之间有存储区被保护的需求，也有共享的需求，即当多个作业需要使用相同的一部分程序或数据时，只存储同一个副本支持共享地使用它，显然比为每个作业存储一个副本更合理，存储管理部分必须在不破坏存储保护机制的基础上，授权相关作业对主存共享区域进行访问。4.信息共享主存容量有限并不意味着系统中运行的用户作业要绝对受制于主存的容量，已经实现了多种存储管理技术向用户呈现比实际主存要大得多的地址空间，这些技术都是借助了大容量的辅助存储器，如覆盖、对换和虚拟存储器等，必须相应地解决主辅存之间的信息传输，特别是虚拟存储管理中，涉及读取、放置、替换、驻留集管理等多种策略的设计问题。5.主存扩充3.2.1绝对地址与相对地址3.2.2地址空间与重定位3.2重定位1.绝对地址主存储器的每个存储单元的地址称为绝对地址，也称为物理地址和主存地址。3.2.1绝对地址与相对地址2.相对地址对于高级语言的程序员来说没有地址的概念，而处理器必须知道它的指令从哪里取、数据从哪里读再往哪里写，即必须有明确的地址这种名空间到地址空间的转换由编译程序完成，因为此时并不能知道它将被装入主存的哪个位置，地址的上限由该文件自身的需要决定，所以称为相对地址，也称为逻辑地址3.2.1绝对地址与相对地址目标文件再经过链接形成可执行程序，以后备作业的形式等待被调度装入主存中以便运行，所以将目标文件的相对地址空间称为作业地址空间，而主存储器中的绝对地址空间称为存储空间。3.2.2地址空间与重定位这种将作业地址空间中要访问的地址变换为实际访问的存储空间中地址的过程就叫地址重定位，简称重定位，也称为地址映射。3.2.2地址空间与重定位作业A的地址空间是0~1KB，而它被装入到主存空间中1K~2K的位置上，因此，作业地址空间中的地址都要加上1KB才是正确的。3.2.2地址空间与重定位作业A的地址空间1K115212802K内存的存储空间…LOAD1,2560128256X1K………LOAD1,256X……LA（256）+BA（1024）＝PA（1280）图3-3地址重定位示例如果作业被装入主存时立即进行相对地址到绝对地址的变换，则称为静态重定位。参考图3-3中的示例，实施静态重定位就是将作业地址空间中的逻辑地址LA，依次增加该作业装入主存后所分得的空间首地址BA，得到实际要访问的物理地址PA。1.静态重定位静态重定位的优点就是方法简便，不需要额外的硬件支持，不影响作业的执行速度。但缺点也是很明显的，首先，它必须要求程序在执行前完成全部的链接工作，否则无法得到正确的物理地址。其次作业在装入后不允许再移动，无法实现虚拟存储等主存扩充技术，不利于多道程序设计。1.静态重定位动态重定位是指作业装入主存时并不立即进行逻辑地址到物理地址的变换，而是CPU执行到具体的指令时，再把该指令中访问的逻辑地址修改为实际的物理地址，并继续执行，因此地址的重定位是在程序执行过程中动态完成的。2.动态重定位这种重定位的方法会延误指令的执行，因此通常要增加硬件机构，如一个或多个基址寄存器、逻辑地址寄存器、加法器等，在较复杂的系统中还可能开辟有多个缓冲以提高定位的速度。2.动态重定位优点：更有利于多道程序设计（1）程序执行前不要求全部装入主存，因为计算物理地址的工作是在执行某一指令时才做的，这是主存扩充技术实现的基础；（2）允许作业在主存中改变位置，甚至是多次在主、辅存间交换。（3）更适于实现不连续的存储分配。2.动态重定位3.3.1覆盖技术3.3.2对换技术3.3存储器管理技术先来看一个基本的程序结构示例，它包含有5个模块，相互调用关系及占用空间大小如图3-4所示。3.3.1覆盖技术M0(20KB)M2(20KB)M1(15KB)M1.1(20KB)M1.2(30KB)M2.1(40KB)20K存储空间M0M1M1.1…覆盖区1(20K)…覆盖区2(40K)从图3-4中所示的实例可以看出，利用覆盖技术后，在主存中占用80K的空间可以运行总大小145K的程序，节省了主存空间，也就能够使得更多的程序在主存中的同时驻留，从用户的角度来看，就达到了主存扩充的效果。3.3.1覆盖技术覆盖技术有一定的缺点。第一，覆盖的顺序要由程序员来设计，这意味着程序员必须完全清楚整个程序的结构，这不单单是增加了程序员的工作负担，对于开发较大型软件系统来说做到这点是非常困难的；另一方面覆盖方法不能灵活地适应程序自身的变化，如果程序发生变化，比如模块间的调用顺序更换或模块本身需要更多的空间时往往要全部重新设计。3.3.1覆盖技术对换技术是另一种主存管理技术，与覆盖技术以程序自身的逻辑模块为单位进行主辅存之间的交流不同，对换是以进程为单位，当有新的进程请求进入主存又没有空闲空间可供使用时，则选择主存中不活跃的进程将其换出到辅存中专门开辟的对换区。3.3.2对换技术如图3-5所示，主存中依次进入了P1、P2、P3、P4，当P5要求进入时无可供分配的空间，此时P2进程处于非活跃状态（阻塞或是由于某种原因而挂起），则将P2换出（非活跃进程可能有多个，选择时还要考虑空间等因素），允许P5进入，P6的情形与P5相同，随着进程的推进，其他进程结束或进入非活跃状态后，还可以将P2、P3等再换入回主存继续执行。3.3.2对换技术主存P2P7P3P8P1P5P4P6………辅存对换区对换技术的优点：（1）利用对换技术实现了主存扩充，因为存放进程的区域扩展到了辅存的对换区中。（2）加快了作业的周转，提高了处理器的利用率。虽然进程仍然要被装入主存才能够执行，但辅存对换区的帮助使得主存中可以“集中精力”存放活跃进程，使它们能够更快地被调度执行。3.3.2对换技术（3）置换范围是全局的，适应性更好。对进程换入换出的选择范围不是单个程序的局部区域，而是整个系统的全局范围。（4）利用对换技术最突出的优点在于进程的换入与换出是由系统根据进程和存储空间的状态自动完成的，对于程序员来说是不可见的。3.3.2对换技术但是对换技术对作业周转速度的提升并不总是一致的，从单个进程的角度看，进程在执行过程中不能始终处于主存中，被换出到辅存后再次进入必须经过一段时间的排队等候，将会推迟进程的下一步操作；3.3.2对换技术从系统效率的角度看，如果选择换入/换出的进程不当，可能导致进程的频繁进出主存，出现所谓的“抖动”现象，即处理器消耗了过多的时间解决换入/换出操作，相对地减少了供给进程本身执行所需的服务时间，处理器的效率反而下降。3.3.2对换技术3.4.1固定式分区管理3.4.2可变式分区管理3.4.3可重定位分区分配3.4分区管理技术固定式分区管理是指将主存空间预先划分成若干边界固定，但大小不等的区域，每个区域供一个作业占用。系统建立一张分区表，记录分区的使用情况，如图3-6所示。3.4分区管理技术3.4分区管理技术主存J1OS占用区J2空闲空闲…分区号起始地址空闲/占用大小032K116K148K016K264K132K作业号J1J2396K032K分区表32K48K64K96K……由于每一个分区可以装入一个作业，所以，固定式分区管理方案支持了多道程序运行，但是这种简单的管理方案有如下的缺点：（1）主存储器的内部碎片较多，降低了主存利用率。3.4分区管理技术由于作业独占一个分区，当分区大小超过作业大小时剩余的空间也不能再被利用，称为内部碎片，平均看来每个分区将有一半的碎片，整个主存中碎片量约为：（2）可同时运行的作业道数受分区个数限制。（3）大作业（超过最大分区容量的）无法运行。3.4分区管理技术可变式分区管理方案仍然是以分区为基础，每一个分区存放一个作业，但与固定式分区不同的是，不再事先对主存进行区域的划分，而是当有作业申请进入主存时，由系统根据当时主存的使用情况划分一个与作业大小相等的空闲区域供其使用3.4.2可变式分区管理3.4.2可变式分区管理进程A（8K）进程B（32K）进程C（16K）进程队列OS主存（ABC进入后）进程A（8K）进程C（16K）OS进程A（8K）进程B（32K）进程C（16K）进程B（32K）空闲…OS主存（初始）进程A（8K）进程C（16K）OS进程A（8K）进程B（32K）进程C（16K）进程B（32K）空闲为完成对主存空间的管理和分区分配，系统维护一个数据结构称为空闲分区表，表中记录空闲分区的起始地址和大小，空闲分区表可以按照以下两种方式组织。1.分区的分配（1）最先适应（FirstFit）分区分配算法此时，空闲分区表以空闲区的起始地址由低到高排序，有新的作业申请空间时，从头开始查找，找到第一个可以满足新作业空间需要的则分配之。1.分区的分配（2）最佳适应（BestFit）分区分配算法空闲分区表以空闲区容量的大小由小到大排序，从空闲分区表的起始处开始查找，最先找到的能够满足作业要求的空闲区也是所有空闲区中最适合的，因此称为最佳适应分区分配。1.分区的分配最先适应法空闲分区表分区始址分区大小32K16K126K2K是否否是是否查找空闲分区表当前表项长度满足要求分配，并将此项从空闲分区表中移除分区表结束当前表项长度等于申请量无法分配下一项截取所需大小，并将剩余部分插回空间分区表结束开始……最佳适应法空闲分区表分区大小分区始址32K16K126K2K……(a)(b)(c)当作业完成要释放出所占用的空间，操作系统完成回收工作。对分区的回收有4种不同的情况，具体的操作也有所不同1.回收分区既无上邻空闲分区也无下邻空闲分区。此时空闲分区表（以最先适应分区分配算法为例，下同）增加一项，记录新回收分区起始地址和大小。2.分区的回收2.回收分区有上邻空闲分区但无下邻空闲分区。此时需要将新回收分区与其上邻合并，修改空闲分区表中上邻空闲分区的大小即可。2.分区的回收3.回收分区有下邻空闲分区但无上邻空闲分区此时的合并操作有两步，一是用新回收分区的起始地址更新空闲分区表中该下邻空闲区的起始地址，二是更新该下邻空闲区的大小。2.分区的回收4.回收分区既有上邻空闲分区也有下邻空闲分区，此时的合并操作将致使空闲分区表减少一项，留用新回收分区的上邻起始地址，并将其大小更新为三者之和。2.分区的回收2.分区的回收(a)(b)(c)(d)占用空闲toptoptoptop…X……X……X……X…sizesizesizesize[例3-1]已知在某一时刻，系统内有J1（8K）、J2（24K）、J3（16K）、J4（12K）、J5（12K）等5道作业同时驻留，主存的分配情况如图3-10a所示（分区中无作业编号的为空闲分区），从此时刻开始，相继出现如下事件：J2完成、J4完成、J3完成、J6（8K）申请进入、J7（64K）申请进入，试完成相应的主存空间分配与回收操作。2.分区的回收J18KJ18KJ18KJ18KJ224K24K24K68KJ316KJ316KJ316K16K16K28KJ412KJ412KJ512KJ512KJ512KJ512K8K8K8K8K图3-10可变分区存储管理示例过程模拟1最先适应法（FF）最佳适应法（BF）起点分区始址分区大小分区大小分区始址48168888881648J2完成分区始址分区大小分区大小分区始址82488848161648888248J4完成分区始址分区大小分区大小分区始址82488848282488882848J3完成分区始址分区大小分区大小分区始址868888888688图3-11可变分区分配示例之分区表变化1在这一阶段来看，最先适应和最佳适应的区别不是很明显，但已经可以体会出，最优适应法在寻找邻接分区和调整分区表时要比最先适应开销大。接下来，再陆续发生J6（8K）申请进入、J7（64K）申请进入两个事件，此时主存分配和分区表变化如图3-12和图3-13所示。2.分区的回收J18KJ18KJ18KJ18KJ68K68KJ68KJ764K60K60K4KJ512KJ512KJ512KJ512K8KJ68K8KJ68K(a)J6申请进入(b)J7申请进入FF成功BF成功FF失败BF成功图3-12可变分区存储管理示例过程模拟2在这一阶段，两种分配方法出现了显著的不同，J6请求进入时，虽然它只要求8K的空间，但根据最先适应法的算法规则，它也会从低地址端寻找适合的分区，剩余部分则会调整填入空闲分区表，最优适应法则会寻求尺寸上更适合的一个；而当J7请求进入时，最先适应法会报告无法分配，最优适应则可以接收。2.分区的回收最先适应法（FF）最优适应法（BF）J6请求进入分区始址分区大小分区大小分区始址860688888

J7请求进入分区始址分区大小分区大小分区始址860472888

图3-13可变分区分配示例的分区表变化2可变分区存储管理方案与固定分区方式相比，虽然管理上增加了一定的复杂性，但取得三方面的优势：1.不会产生内部碎片，因为各作业所占用的空间就是它所需要的大小；2.可同时运行的作业的道数不再有分区个数的限制，更有利于多道程序设计；3.较大作业也有了运行的机会。2.分区的回收问题：随着作业的进入和退出，本来连续的大空闲区很快被分割成了多个分散的小的空闲区，有些甚至不能满足任何新作业在空间上的要求，而无法分配出去，把这种不能分配给任何作业的存储“零头”称为外部碎片。2.分区的回收[例3-2]假设某系统主存容量128K，操作系统占用32K，初启状态时的空闲分区表如图3-14a所示，设作业最小为8K，试运用最先适应分区分配算法模拟事件序列：J1（16K）进入、J2（48K）进入、J3（30K）进入、J1完成、J4（10K）进入的主存分配与回收过程。2.分区的回收在模拟作业进入和退出的过程中，主要是对空闲分区表进行更新，如题意按照最先适应分配算法，空间分区表按空闲区始地址由小到大排序，其变化过程如图3-14a~f所示，全部事件结束后主存区域的状态如图3-15a所示。2.分区的回收（b）J1进入分区编号分区始址分区大小132K96KFirstFit空闲分区表更新过程分区编号分区始址分区大小148K80K（a）初始状态（c）J2进入分区编号分区始址分区大小196K32K（d）J3进入分区编号分区始址分区大小1126K2K（e）J1完成分区编号分区始址分区大小132K16K2126K2K（f）J4进入分区编号分区始址分区大小142K6K2126K2K图3-14可变分区产生外部碎片的示例(b)空闲(a)“压缩”后J4OS占用区J2J36K2KJ4OS占用区J2J38K图3-15外部碎片与压缩外部碎片的存在是可变分区管理的主要弊端，可以使用“压缩”技术进行改进，即由操作系统不断调整作业的位置，使其始终连续地占据主存的一端，而另一端则整理成整块的空闲区（如图3-15b所示），这样作业在装入主存后是可以移动的，因此也将这种改进的可变分区管理方法称为可重定位的分区分配。3.4.3可重定位分区分配以上的三种分区管理方案在地址映射方面都比较简单，即作业地址空间中要访问逻辑地址只需加上其装入主存时所占用的物理分区的首地址就是实际访问的物理地址。此外，可重定位的分区分配方案比较适合采用动态重定位方法，因为作业装入后可能多次移动，不适宜用静态重定位的方法一次性完成全部地址转换工作，而另外两种分区方案则没有要求。3.4.3可重定位分区分配3.5.1基本原理3.5.2存储空间的分配与回收3.5.3分页系统中的地址映射3.5.4页的共享与保护3.5分页存储管理采用分页存储管理是指将作业地址空间和存储空间按相同的尺寸进行相等大小的划分（大小一般为2的方幂），对作业地址空间划分后称为逻辑页，简称页。3.5.1基本原理对存储空间进行划分后形成一个个相等大小的物理块，简称块，从0开始编号，主存储器件的容量是确定的，所以块的数量也是一定的。当有作业装入主存时，一页装入一个空闲块中，但不要求连续的页也占用连续的块。3.5.1基本原理主存…12340678951234010作业A5个逻辑页1234001234图3-16分页存储管理原理图页式存储管理时存储空间的分配以块为单位，操作系统为每一个作业维护一张页表，记录作业页装入哪一个物理块，如图3-17所示。由于页与块大小相等，因此消除了外部碎片，仅在作业的最后一页才可能存在约为页尺寸一半大小的页内碎片，对存储空间的浪费已经大大减少。3.5.2存储空间的分配与回收此外，主存空间的管理开销也很低，仅需以块号作索引，记录其分配状态，作业完成释放物理块后，将其状态置为空闲，不需要再对空闲区域的大小及始址进行管理3.5.2存储空间的分配与回收3.5.2存储空间的分配与回收页号块号07142833页表46图3-17作业A的页表分页式存储管理方案提高了主存的利用率，而且分配与回收工作的开销也较小，但是在进行地址映射时要比分区式管理复杂得多。分页式系统的地址映射机构由硬件和软件两部分构成。软件部分即作业的页表，作业装入时也将其页表存放在主存中，其入口保存在页表基址寄存器中；硬件部分除页表基址寄存器外还有地址转换硬件。3.5.3分页系统中的地址映射3.5.3分页系统中的地址映射PBPb页表页表起址寄存器页表始址b页号P偏移W逻辑地址LA块号B偏移W物理地址PAb+P图3-18页式存储管理地址映射机构及过程作业地址空间中任一逻辑地址LA变换为物理地址PA的过程为：（1）将LA拆分为页号P和页内偏移量W：P=LA/SIZE

（式3-1）W=LA%SIZE

（式3-2）其中SIZE代表页尺寸。3.5.3分页系统中的地址映射（2）查询页表，即页号P与页表基址相加，得到该页的页表项，若发生越界错误则执行第4步；若为合法页号，则从对应页表项中取出物理块号B，计算该块的起始地址BA：BA=B*SIZE

（式3-3）3.5.3分页系统中的地址映射（3）计算物理地址PA并返回：PA＝BA+W

（式3-4）（4）报告非法地址错误，转相应处理，返回。3.5.3分页系统中的地址映射通过上面的描述可见，在页式存储管理时为完成一次指令或数据的读取，要两次访问主存：第一次查询页表第二次才是真正的取指令或数据，为了加快地址变换的速度，常常加入联想页表。3.5.3分页系统中的地址映射联想页表是一种硬存储器件，查找速度快，所以也称为快表，相对地，原页表称为慢表。加入快表后，地址映射工作的过程在上述第2步时有变化，不再单一地查询慢表，而是同时查询快表，快表如果未命中（未有记录当前被转换地址相应的P、B），则按原过程执行，并将该慢表项存入快表，如果快表命中，则直接执行第3步形成物理地址。3.5.3分页系统中的地址映射图3-19加入快表的页式存储管理地址映射过程

BPBPb页表页表起址寄存器页表始址b页号P偏移W逻辑地址LAPB联想页表块号B偏移W物理地址PAb+P[例3-3]若在一分页存储管理系统中，某作业的页表如图3-17所示，已知页面大小为1024B，试将逻辑地址2148转化为相应的物理地址。3.5.3分页系统中的地址映射解答：步骤①运用（式3-1）和（式3-2），由逻辑地址2148得到页号和页内偏移量：

P=2148/1024=2W=2148%1024=100步骤②查页表，页号为2时，有对应的块号为8，运用（式3-3）计算该物理块的始址：

BA=8*1024=8192步骤③运用（式3-4），则待求的物理地址为

PA=8192+100=82923.5.3分页系统中的地址映射[例3-4]设某页式存储系统页大小为2K，主存64K，现有作业A（8K）装入主存，页表见图3-20中所示，试将逻辑地址0x0ABC转换为实际访问的物理地址。3.5.3分页系统中的地址映射3.5.3分页系统中的地址映射1315141211109876543210000010101011110011位页内偏移W2位页号P页号块号07142833作业A的页表001000101011110011位页内偏移W5位块号BLA＝0x0ABCPA=0x22BC①②③图3-20页式存储管理地址映射实例模拟分析：本题中，作业总长度为8K，包含213个地址单元，即有效的逻辑地址由13位二进制数构成，其中，页大小为2K（211），即页内编址由11位二进制数表示，作业共分4页（22），即页号由2位二进制数构成。3.5.3分页系统中的地址映射解答：预先的处理工作：将十六进制表示的逻辑地址转换成二进制地址，即0x0ABC(16)=0000101010111100(2)地址映射工作：步骤①通过逻辑地址拆分出页内偏移和页号，即逻辑地址的0~10位（低位起为0位）为页内偏移量W（也称页内地址），11~12位为逻辑页号P。3.5.3分页系统中的地址映射步骤②查页表，即从页表基址寄存器中获得页表首项地址，与页号P相加，找到第P项，得到对应的物理块号B。步骤③将块号与页内偏移相“加”，即物理地址的0~10位对应页内偏移量，11~15位对应块号。最后将二进制地址转换为十六进制表示，故实际访问的物理地址为0x22BC。3.5.3分页系统中的地址映射1.页的共享2.页的保护3.5.4页的共享与保护允许作业用共享的方式使用公共部分有利于主存利用率的提高。在共享的要求上需要注意区分数据页共享和程序页共享的问题。对于数据页，各作业可以各自编排不同的页号；但是程序页则不同，程序页中各指令存在顺序执行或跳转到某处执行的相对定位问题，为确保可以映射到正确的物理地址，必须要求各作业用相同的页号共享程序段。1.页的共享页号块号071429363作业A的页表48页号块号07142933作业B的页表46…BAB_SP21…AB_SD主存AB_SP1AAB_SP3…3号块4号块5号块6号块7号块9号块10号块8号块图3-21页的共享（A：作业A占用；B：作业B占用；SP：共享的程序段；SD：共享的数据段）由于作业被分为多页且装入主存的互不连续的区域中，所以对页的保护适用保护键（见3.1.2所述）方法，即同一个作业所分配的物理块赋予相同的数字锁，“钥匙”被存储于该作业（实际上是进程）的程序状态字里，这里不再赘述。2.页的保护3.6.1基本原理3.6.2存储空间的分配与回收3.6.3地址转换与存储保护3.6分段存储管理分页的存储管理首先实现了将作业分割、灵活地占用主存的思想，大大减少了碎片的数量，但是由于分页操作由系统自动地、机械地完成分割，没有考虑指令与指令之间可能存在的逻辑连续性固定大小的页面使得程序发生变化时，页与页之间相互影响很大。鉴于分页方式存在的不足，考虑从程序自身的结构特征出发，出现了分段的存储管理。3.6分段存储管理在分段管理系统中，对作业地址空间的看法不再是一维线性的，而是先从程序自身的结构特征出发，每一组在逻辑上紧密相关的信息，如子程序、数据区等各形成一个分段，分别编号，从段号0开始到作业结束，而分段内部再从0开始按字节编址，到本段结束，即整个作业地址空间是二维地址[段号S，段内地址D]。3.6.1基本原理3.6.2存储空间的分配与回收L1-10段0段1段3段2长度L3长度L1长度L2长度L0…主存作业A子程序1子程序2主程序数据集合A子程序1子程序2主程序数据集合A………子程序1的段内编址1…图3-22段式存储管理原理图1.地址转换系统为每一个作业维护一个数据结构称为段表，随作业装入主存，段表结构中要记录段号、段长和该段分配得到的主存空间的起始地址。3.6.3地址转换与存储保护任一逻辑地址LA的重定位过程如下。（1）从逻辑地址中提取段号S和段内地址D；（2）查找段表，得到S段的物理主存起始地址SA；（3）段内地址D与S段长L比较，超出L为非法地址，结束，否则执行第4步；（4）物理主存起始地址SA与段内地址D相加，得到实际要访问的物理地址PA，结束。段表的形式和地址映射过程如图3-23所示。3.6.3地址转换与存储保护3.6.3地址转换与存储保护SSASb段表段表起址寄存器段表始址b段号S段内地址D逻辑地址LA内存始址SA段内地址D物理地址PAb+S段号S段长L内存始址SA图3-23分段存储管理的地址映射过程2.存储保护和共享段式存储管理系统通常采用界地址保护方法（参见3.1.2）实现主存保护，但无需另设上下限寄存器，因为作业段表中主存始地址和段长就起到了定界的功能。此外，一个分段集中存放，也有利于实现共享。3.6.3地址转换与存储保护[例3-5]设某分段存储管理系统中，作业X的段表如表3-2所列，试计算逻辑地址[2,560]和[0,218]的物理地址。3.6.3地址转换与存储保护段号段长主存始址0200300015006402800125033202400分析：分段存储管理中逻辑地址为2维，即[段号，段内地址]，因此在地址映射时首先将段号与段表基址相加得到对应的段表项目，进而取得该段在主存的起始地址，接下来，若段内地址未越界（通过比较段内地址和段长来判断），则可以直接将主存始址和段内地址相加得到物理地址。3.6.3地址转换与存储保护解答：1.第一个待求逻辑地址[2,560]由段表可知，2号段的主存始址为1250，段内地址560不超过段长800，未越界，则所求物理地址为560+1250＝1810。2.第二个待求逻辑地址[0,218]由段表可知，0号段的主存始址为3000，但段内地址218超过段长200，即该地址为非法地址，地址映射中止。3.6.3地址转换与存储保护3.7.1基本原理3.7.2存储空间的分配与回收3.7.3地址映射3.7段页式存储管理简要回顾分页和分段的优缺点。两种技术都实现了作业分割、化整为零装入主存，提高了存储分配的灵活性、有利于主存利用率的提升。分页的方法消除了外部碎片，但机械分割的方式破坏了程序的天然逻辑结构，不便支持程序的动态变化、不便共享和保护；分段的方法克服了分页的缺点，但又出现了外部碎片。考虑取二者之长、并弥补其不足，出现了段页式存储管理。3.7段页式存储管理主存储空间按相同大小等分为物理块，作业地址空间首先按其逻辑特征划分为段，再将段内划分为等大小的逻辑页，页尺寸与物理块的尺寸相同，段内地址若不是页尺寸的整数倍，最后剩余的不足一页的部分仍然按一页处理，这样作业地址空间中形成了三维的逻辑地址[段号，段内页号，页内偏移]。3.7.1基本原理在进行存储空间的分配时，首先以段为单位为其分配主存，再以页为单位装入物理块。因此，从作业的角度看，采用的是分段技术，满足逻辑上的结构关系要求、动态变化要求、便于保护和共享的要求，再从主存的角度看，则采用了分页技术，满足了消除碎片、提高主存利用率的要求。3.7.2存储空间的分配与回收段页式存储管理的地址映射需要由系统维护2张表：段表和页表，硬件部分设有段表基址寄存器、联想页表和地址转换硬件，其映射过程如图3-24所示。3.7.3地址映射3.7.3地址映射②②’BPSb段表页表段表起址寄存器段表地址b段号S页号P偏移D逻辑地址LA＝（S,P,D）SPB联想页表物理块号B偏移D物理地址PAb+S①③④⑤③’图3-24段页式存储管理的地址映射过程3.8.1虚拟存储器的概念与特征3.8.2请求分页式虚拟存储管理技术3.8虚拟存储器管理3.8虚拟存储器管理覆盖对换优点缺点优点缺点作业不要求完全进入主存，节省空间人工操作，工作量大作业可重入，并由系统自行完成整个作业为单位进出主存，开销大虚拟存储器＋＋－－图3-25主存扩充技术的革新虚拟存储器的实现有一个重要的理论前提，那就是局部性原理。我们可以分析程序执行中处理器取指令和数据时的各种情况，比如：（1）除了分支和调用指令外，程序执行通常是顺序的，而这两类控制指令在所有程序指令中只占了一小部分，即大多数情况下，处理器要取的下一条指令都是紧跟在上一条指令之后；3.8.1虚拟存储器的概念与特征（2）在较短的时间内，程序中过程调用的深度不会很大（过于频繁且长度极小的过程调用本身就是不合理的），此时，指令的引用也局限在很少的几个过程中；（3）在循环结构中，处理器的执行范围被限制在程序的一个小局部内；（4）程序中涉及到处理数组、记录序列之类的数据结构时，对它们的引用往往也是在相邻的或较连续的一段相对位置中。3.8.1虚拟存储器的概念与特征通过以上分析，说明了在一段时间主存储器访问表现出集簇性，称为局部性原理。在局部性原理的支持下，为用户作业分配主存空间时可以不必一次性满足其全部要求，只要保证当前及最近的将来处理器需要的部分（称为常驻工作集）驻留在主存中即可，而其余部分则是借助辅存存储。3.8.1虚拟存储器的概念与特征由于这些工作对用户是不可见的，所以从用户作业的角度来看，无论其需求如何，系统都为其分配了与其作业地址空间一致的存储空间，因此称为虚拟存储器。虚拟存储器的实现由硬件和系统软件两部分共同完成。3.8.1虚拟存储器的概念与特征从以上虚拟存储器的基本概念可见，虚拟存储器有以下特征：（1）虚拟扩充（2）部分安装（3）离散分配（4）多次对换3.8.1虚拟存储器的概念与特征1.请页式虚存管理的基本原理请求分页是最典型的虚拟存储管理方案，在基本的分页管理基础上，做了一些改进。（1）作业执行前不一次性分配所需全部主存，而只装入初启所需的一个或几个页面；（2）增加缺页中断机构，当访问的页面不在主存时报告缺页错误；并由缺页中断处理例程进行调页；在不再增加分配给作业的物理块数时，要选用某种页面置换算法进行淘汰；

3.8.2请求分页式虚拟存储管理技术（3）作业页表增加了描述页面状态的信息位，如存在位和修改位。当页面存在位为1时表示在主存中，反之将发生缺页中断；当页面修改位为1时表示在其装入主存后被修改，因此该页被置换时要重新写出辅存，相反则不需此项操作。3.8.2请求分页式虚拟存储管理技术在作业执行过程中，究竟装入哪些页，装入多少页呢？工作集模型理论解释了这个问题。工作集模型认为，每个作业在任何一个时间段△t，都存在一个页面子集H(t)，其中包含了作业当前需要频繁访问的一组页面。根据局部性原理，这个子集不会很大。但是如果这个子集不全部在主存，将会发生频繁的调页。这个子集就称为该进程在时刻t的工作集。页式虚拟存储管理系统应该时时力图积累并保持进程的工作集在主存中。3.8.2请求分页式虚拟存储管理技术显然，工作集的大小是随着时间变化着的，因此分配给作业的物理块数应该也是可变的，这里称其为页框数M，它恰好能够容纳当时的工作集。3.8.2请求分页式虚拟存储管理技术①装入作业的第一页，让作业运行。②发生页面故障时，增大M，调入新页，积累工作集。③当缺页率趋于稳定（比如小于某个阈值）时，便完成了这一时段的工作集积累。此时主存的页面便是这一时段的工作集。④此后若继续有页面故障，不再增加页框数，而要先淘汰某个页后再调入。同时不断地计算缺页率。3.8.2请求分页式虚拟存储管理技术⑤当页面故障率超过某个阈值时，继续增大分配的页框数，以便调整工作集尺寸，积累新的工作集。从以上的叙述可见，请页式的虚拟存储方案实现起来是比较复杂的，为了获得局部性原理支持下的工作集维护，以及由此带来的诸多好处，需要硬件和软件共同完成，如图3-26所示，所幸的是这些工作都是系统完成的。3.8.2请求分页式虚拟存储管理技术是否是否是否启动当前指令提取页号查页表完成该指令存在位为1？执行页面淘汰算法有空闲块？取辅存中的页更新页表报告缺页中断处理完成，重启被中断的指令更新页表取下一条指令修改位为1？写出辅存硬件机制软件策略图3-26请页式虚拟存储管理下指令的执行过程[例3-6]某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7。而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。3.8.2请求分页式虚拟存储管理技术分析：由题意可知，作业共6页，即作业地址空间合法范围为0x0000~0x1800，并且作业前4页已经装入主存，即逻辑地址0x0000~0x1000（16进制）可以按照基本分页管理地址映射方法计算物理地址。页大小1K，由10位2进制数表示页内偏移量，页数6，由3位2进制数表示。3.8.2请求分页式虚拟存储管理技术解答：LA1：0x0A5C(16)=0000101001011100(2)，PA1＝0x125C，过程如图3-27所示。LA2：逻辑地址0x103C所在页尚未装入主存，无法计算。LA3：逻辑地址0x1A5C超出有效的作业地址空间，是非法地址，不计算。3.8.2请求分页式虚拟存储管理技术3.8.2请求分页式虚拟存储管理技术1315141211109876543210000010100101110010位页内偏移W3位页号P页号块号051102437作业A的页表000100100100110010位页内偏移W6位块号BLA＝0x0A5CPA=0x125C图3-27例3-6请页式虚拟存储管理地址映射实例模拟请页式的虚拟存储管理是在缺页中断的驱动之下实现的，因此也可以说它存在一个缺点，就是当要访问的页不在主存时去依次执行中断、处理和恢复工作，对指令的执行是一种延误，而另外一种基于分页的虚拟存储管理——预约式页式存储管理方案，则力图避免这种不足。3.8.2请求分页式虚拟存储管理技术预约式与请页式的区别在于，由系统估计最近的将来作业执行所需的页面集，将其事先调入，这样要访问的页是永远在主存中的，只是这种方案实现起来意义不大，因为对未来的估计往往是不准确，反而造成更大的开销。3.8.2请求分页式虚拟存储管理技术2.二级页表结构对于大型作业，页表本身也可以按照分页管理的方式进行存储。如一个支持32位寻址的系统，页尺寸为4KB，那么4GB的作业由220页组成，每个页表项占4B，则该作业页表需要222B即4MB的空间，可分210页，在虚存管理技术下，这个庞大的页表不必要完全装入主存，而是像作业一样，将页表自身也划分为页后，每一页映射到一个页表项上，则只需212（4KB），1页的空间，如图3-28所示。3.8.2请求分页式虚拟存储管理技术3.8.2请求分页式虚拟存储管理技术……一级页表4KB二级页表4MB作业4GB图3-28二级页表结构另外还有两种虚拟存储管理方案：请求分段和段页式虚存。请求分段是在基本的分段式存储管理的基础上的改进，利用局部性原理，工作集的维护是以作业的逻辑段为单位的。段页式虚存管理则是请页式和请段式的综合，是现代操作系统中使用比较广泛的方案。3.8.2请求分页式虚拟存储管理技术3.9.1先进先出置换法3.9.2最近最久未使用置换法3.9.3最近未使用置换法3.9.4最佳置换法3.9常用的页面置换算法页面置换，也称页面淘汰，是指在页式虚拟存储系统中发生缺页中断时，在不增加分配给作业的页框数的情况下，选择由新调入页去替换掉已经装入主存中的哪一页的操作，它也是实现虚拟存储管理的关键环节之一，本节介绍主要的置换算法，为比较不同算法的性能，引入缺页率作为指标（见公式3-5所示）。

（式3-5）

3.9常用的页面置换算法先进先出（FIFO）的置换方法即选择最先进入主存的页面进行置换（或称淘汰）。实现时，系统将作业的常驻页面集维护成先进先出的队列，新调入的页加在队尾，需要置换时取队头页面。3.9.1先进先出置换法[例3-7]作业A在某一时间段内的页面访问序列为P（2，3，2，1，5，2，4，5，3，2，5，2），页框数为3，则页面访问过程中缺页率、页面工作集队列更新过程如图3-29所示。3.9.1先进先出置换法3.9.1先进先出置换法23215245325223315244335222315224435231552243×××××××××缺页次数9总页面访问次数12缺页率为75%图3-29FIFO置换算法示例先进先出的置换方法实现起来简便，但是它的推论是最先进入主存的页面不会再用到，没有考虑到有些“先期”进入的页面可能在将来还会频繁使用到，因此它存在一个严重的缺陷就是有的情况下，增加分配给作业的页框数，缺页率反而更大，称为先进先出异常（比莱迪异常Belady’sanomaly）。3.9.1先进先出置换法[例3-8]某作业页面访问序列为P（4，3，2，1，4，3，5，4，3，2，1，5），当页框数为3和4时，页面集队列的变化过程和缺页次数如图3-30所示。3.9.1先进先出置换法3.9.1先进先出置换法页框数为3时：432143543215432143555211432143335224321444355×××××××××缺页次数9总页面访问次数12缺页率为75%

3.9.1先进先出置换法页框数为4时：432143543215432111543215432221543214333215432444321543××××××××××从本例可以看出，在页框数为3时，作业A的缺页率为75%，而页框数增加到4时，缺页率反而变大，为83%，即出现先进先出异常现象。

缺页次数10总页面访问次数12缺页率为83%图3-30FIFO置换方法出现的异常最近最久未使用（LRU）置换法是指当有页面需要被淘汰时，选择在最久的过去使用过的页，此时，作业的页面集被维护为后进先出的栈，新调入页从栈顶压入，栈底的页自动被淘汰。为保证栈底的页一定是最近最长时间没被使用的，页面访问过程中即使未发生缺页中断系统也将调整栈中的页面顺序，以保证最近被使用的页面在栈顶一侧。3.9.2最近最久未使用置换法[例3-9]作业A在某一时间段内的页面访问序列为P（2，3，2，1，5，2，4，5，3，2，5，2），页框数为3，则使用最近最久未使用置换法时页面访问过程中缺页率、页面工作集更新过程如图3-31所示。3.9.2最近最久未使用置换法3.9.2最近最久未使用置换法23215245325223215245325223215245325321524533×××××××缺页次数7总页面访问次数12缺页率为58%图3-31LRU置换算法示例LRU算法不会出现所谓的先进先出时的异常情况（验证工作可自行完成），因为此算法置换时推论最近最长时间以来没被使用的页面被淘汰，根据局部性原理所说明的集簇倾向，在最近的过去一直被闲置不用的页通常也是最近的将来最不可能被使用的；但是LRU算法在实现起来开销要比先进先出大的多。3.9.2最近最久未使用置换法LRU算法获得了比较好的页面调度效率，但是它要比FIFO算法复杂且开销大，最近未使用算法试图以较小的开销接近LRU的性能。图3-32给出了最近未使用算法的示例，该策略也称为时钟（Clock）策略，因为页面集被想像成环状，关联的指针在其中顺时针转动。3.9.3最近未使用置换法3.9.3最近未使用置换法...页8使用位0页7使用位1页5使用位1页1使用位1页10使用位1页6使用位0页12使用位1...页13使用位1页7使用位0页5使用位0页1使用位1页10使用位1页6使用位0页12使用位1(a)某一时刻发生替换前的状态(b)发生替换后（8->13）的状态图3-32最近未使用（时钟）算法示意某一时刻，进程A候选页面集的关联指针指向主存中的5号页，当有新页13要求进入时，当前指针位置的使用位为1则将其置0，指针指向下一位置，下一位置的7号页使用位也为1则再次置0，再指向下一位置，此时8号页使用位为0，则将新页13调入置换8号页，且13号页的使用位为1。3.9.3最近未使用置换法[例3-10]某作业的页面访问序列为P（2，3，2，1，5，2，4，5，3，2，5，2），通过最近未使用算法获得的页面访问过程中缺页率、页面工作集更新过程如图3-33所示。3.9.3最近未使用置换法3.9.3最近未使用置换法23215245325222225555333333332222222111444455××××××××缺页次数8总页面访问次数12缺页率为67%图3-33Clock置换算法示例时钟算法还有一种改进的方案，即将页面的使用位U和修改位M同时应用，这样每个页面在主存中会有4种状态：（1）U＝0，M＝0——最近未被访问，也未被修改；（2）U＝1，M＝0——最近被访问，但未被修改；（3）U＝0，M＝1——最近未被访问，但被修改过；（4）U＝1，M＝1——最近被访问，也被修改过。3.9.3最近未使用置换法此时，时钟算法可以按下面的步骤执行：①从指针的当前位置开始，扫描候选页缓冲区。在这次扫描过程中，对U位不做任何修改，选择遇到的第一个U、M同时为0的页用于替换。②如果第一步失败，则重新扫描，查找U＝0、M＝1的页。选择遇到的第一个这样的页用于替换。在这个过程中，对每个跳过的页的U位置0。③如果第二步失败，指针将回到它的最初位置，并且集合中所有页的使用位均为0。重复第一步，并且，如果有必要，重复第二步。3.9.3最近未使用置换法3.9.3最近未使用置换法页8U=1,M=1页15U=1,M=0页5U=0,M=1页7U=1,M=0页22U=1,M=1页14U=0,M=0页28U=0,M=0……缓冲区首012345n-1第一个被置换图3-34增加修改位的时钟算法在不考虑新装入页的情况下，被置换的页面依次为14，28，5，15，8，7，22。

最佳置换法（OPT）意即获得最好的页面置换性能，最佳置换算法在页面淘汰时选择主存中永远不会用到的页面或者在最久的将来才会用到的页面，此时的作业页面集维护为随机存取的数组，新调入页直接替换被选中淘汰的页。3.9.4最佳置换法[例3-11]作业A的页面访问序列为P（2，3，2，1，5，2，4，5，3，2，5，2），页框数为3，使用最佳置换法时页面访问过程中缺页率、页面工作集更新过程如图3-35所示。3.9.4最佳置换法3.9.4最佳置换法23215245325222222244444433333333222155555555××××××缺页次数6总页面访问次数12缺页率为50%图3-35OPT置换算法示例以上的例3-7、3-9、3-10、3-11是对相同的页面访问序列P（2，3，2，1，5，2，4，5，3，2，5，2）采用不同的置换算法，验证结果会发现，OPT算法的缺页率是最低的，但问题在于，OPT是一种无法实现的策略，因为要求系统必须知道将来的事件，显然这是不可能的；因此，OPT算法作为一种标准来衡量其他算法的性能，在相同条件下越接近OPT算法的效率则表示该算法越好3.9.4最佳置换法[例3-12]假设有一系统采用请求分页的虚拟存储管理，当有一用户程序，它访问其地址空间的字节地址序列为：70、305、215、321、56、140、453、23、187、456、378、401。若主存大小为384B，页大小为128B，试按FIFO算法和LRU算法，分别计算缺页率。分析：题中已知的是逻辑地址，故首先要将逻辑地址转换为逻辑页号，且已知页大小为128B，页框数为3。3.9.4最佳置换法解答：1.由作业地址空间的地址序列，计算相对应的页号，即“页号＝逻辑地址/页尺寸”，得字节访问序列依次对应于页号：0、2、1、2、0、1、3、0、1、