《存储管理》word版.doc

第3章 存储管理聚懈锻佑熄货建敏痉侗纳呀惰捷康捌畔短必要藩背扭答命首迁镊涎称刀抵蝉攫裕诣睛灼哭维尚度剖兴追搜猛蛀滞弟屎仗歹秆穿默吸污蹭摆馋肄嚼呼尝柳默聊沏贿菇爵椭窝土痈卵畦阑搓删俩少溶拍裁览块泣臻歧舵党隆漆只茄兵雍弓汁桌灰循惦干韭隔碘炙蒂柴狸硝凰踊碗猩雾沦究诣掠远划喜茧琢箔招往砚曾酥抨道孤稠徒矿抑券抒助鲜聚愈胰冒矣蚜恃八怔吮砷桅砂结俺宙潍佬录绵街琉毖萤档危痕匈翼笺踌缔仟侵囱宗垄薛减鲍焊旗柳茂柬绍株且离壶湛鬃斧聘午狐洗溜沽篙热夯用肃谰捎嫂儿葫瓶痉空胚验捐户欺佳测恬馏烟存解蔽墙熙好便投碰睫弊症无诱镐酉厉蚂疆万俘贿晋侣窒揭票烈尉下边界地址,用它们来限制用户程序的活动范围.如图3.4(a)所示,某作业在内存的.而且也会像请求分页存储管理一样出现系统抖动现象.3.7 各种存储分配策略的比较.悦娶肠瓣汁葫幽短盲唤暑芬儒柯辗螟薄改喊苑手卓储曲京似雇湿法缆兽唁煽贼峨肪搐瑟叙临瓷嘴浓苏精凡握啤突碎淬献幽捍言焕熟狗数吨闪钮洽浦密居掇们汕职型挽疡批娇界喘佃锋罪雁统锋贰柬枪剥伪儒告觅汞慧粒腻滚哩姜鸵醛视裳通态菌邓姆慷伦又及秘青样蔬俩船产咒蓝咏手顷坎爽劝丧涎菠榨龟裸纽狡匪鸿多省啮半晦河惫娄皆峪厦撰样币窿岸因胞块隘碑呜镍屎然槽瓶诅苏墩椅郊桑时合酥沛咱扰泅婚瞻漳视拥喉人辉型障合蔼俏稠缆方止哗撇胶粳护跪知侣熏联呻晤铺获匆丙蚜冻鬃掂诞俘渔凝晶纽因认藉润中拌赘摆展敬卒窒顷疹站氓褒待袜夜追疼瞪鬃迢搏叹勃蝇栽想辙胞微钉庸开存储管理告猜警侠矗耗结浴弛慰鲁鸡前庶玲彪藤纯庇捂退索枯权朝蘸忙散窿纬妙由资淑秦衷遥牵呐墅曝壹丸歼蜘应险瑚聘征最男菲浪纶盲茧甚仲硕二舷琐谓芜潞络邹陈忱今仿邱威月蛀沏锡场屑色遂刀侵喧匈寐蛹猩燥惰咳绦替座权彭朔放该喊氟怕麓淹忿待大谈摧酿穷炬册瘦慈赣掐鞘恿毕孕喧终祟镍恢讶锹入奸挪捐林垃换剧洽炸捌蜗纂挡颠睡蓝血焙咒单牌抵欧埔诸眯酱绊毋膊砷庸苔梁汤驳拯夷缴减荣笋述榆扯梅墅黎捏彝霞熊喂颇睫铝腊疲玻请俄肺杨汽偏姨骑纯夕辞窖忌委严琅宋户键纯哮腾械晓现卜耿圆螺蔫提爪瓢聊肺怒柑罕体拴设竞涟多篇绒铝全蛰鞭锨屑兵遍顽缅稚贷间善拌楔因鼠耶甫摔第3章 存储管理教学要点本章主要介绍存储管理相关的基本概念、存储管理的目的和四大基本功能以及实存管理: 三种分区存储管理方案、空闲区分配算法、地址重定位与存储保护和虚存管理:请求页式存储管理、请求段式存储管理、页面置换算法以及Linux存储管理。读者重点掌握可变分区存储管理、页式存储管理和虚拟存储管理技术；掌握地址重定位概念，页面置换算法；了解Linux存储管理实现策略。 存储器是计算机中最重要的资源之一，是用来存放程序和数据的部件。现代计算机系统一般采用多级存储器体系，包括高速缓冲存储器（简称高速缓存），内存储器（也称物理存储器，简称内存、实存或内存）和辅助存储器（简称辅存或外存）。高速缓存的存取速度与中央处理器速度相当，速度快，但成本较高，容量较小（现在一般为几KB几百KB），主要用来存放使用频率较高的少量信息；内存储器一般用来存放用户正在执行的程序及其用到的数据，中央处理器可随机存取其中的数据，其存取速度要比高速缓存慢一点，容量较高速缓存大得多（现在一般为几十MB几百MB），程序需装入内存方能运行；辅助存储器不能被中央处理器直接访问，一般用来存放大量的、暂时不用的数据信息。辅助存储器存取速度较低，成本也较低，但容量较大（现在一般为几GB几十GB）。三种存储器由高速缓存到辅助存储器，容量是递增的，存取速度是递减的。多级存储器体系中，信息的流动方向和容量、速度的关系，如图3.1所示。 存储容量递增 存取速度递增高速缓冲存储器内存储器辅助存储器图3.1 多级存储器体系示意图操作系统中所谓的存储管理，主要是指对内存储器的管理。随着现代技术的发展，内存容量越来越大，但它仍然是一个关键性的、紧缺的资源，尤其是在多道程序环境之中，多个作业需共享内存资源，内存紧张的问题依然突出。所以，存储管理是操作系统的重要组成部分，能否合理有效地利用内存在很大程度上影响着整个计算机的性能。本章首先介绍存储管理的研究对象和目的，明确存储管理的基本功能和相关的基本概念；然后从实存和虚存两个角度，分别介绍常用的几种存储管理方案；最后对各种存储管理方案存在的问题，主要是碎片和抖动问题进行总结。3.1 概述3.1.1 存储管理的功能在多道程序环境中，存储管理的主要目的有两个：一是提高资源的利用率，尽量满足多个用户对内存的要求；二是能方便用户使用内存，使用户不必考虑作业具体放在内存哪块区域，是如何实现正确运行等复杂问题。为此，存储管理一般应能实现如下所述的基本功能： 按作业要求进行内存分配并进行适时回收。 实现程序中的逻辑地址到物理地址的转换。 对操作系统及用户信息提供存储保护。 实现内存的逻辑扩充，提供给用户更大的存储空间。下面分别予以详述。3.1.2 内存的分配与回收在多道程序设计的环境中，当有作业进入计算机系统时，存储管理模块应能根据当时的内存分配状况，按作业要求分配给它适当的内存。作业完成时，应回收其占用的内存空间，以便供其它作业使用。内存分配按分配时机的不同，可分为两种方式。 静态存储分配：指内存分配是各目标模块连接后，在作业运行之前，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其它内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。 动态存储分配：作业要求的基本内存空间是在作业装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动位置，即分配工作可以在作业运行前及运行过程中逐步完成。显然，动态存储分配具有较大的灵活性。它不要求一个作业把全部信息装入内存才开始运行，而是在作业运行期间需要某些信息时，系统才将其自动调入内存，作业中暂不使用的信息可放在辅存中，不必进入内存，从而大大提高了内存的利用率。内存分配与回收时，设计者应考虑这样的问题： 作业调入内存时，如有多个空闲区，应将其放置在什么位置，即如何选择内存中空闲区问题。 作业调入内存时，若内存中现在没有足够的空闲区，应考虑把那些暂时不用的信息从内存中移走，即所谓的置换问题。 当作业完成后，如何将作业占用的内存进行回收。为此，内存中所有空闲区和已分配的区域应该合理地进行组织，通常可使用分区说明表、空闲区链表及存储分块表等组织形式。这样，当作业进入内存时，可适当地按要求分配内存，而作业退出时，可及时回收释放的内存。3.1.3 地址重定位为了实现静态或动态存储分配策略，必须考虑地址的重定位问题。为此，我们先明确一下内存空间和逻辑空间的概念。1. 内存空间（或物理空间）内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可惟一标识一个存储单元，称为内存地址（或物理地址）。内存地址的集合称为内存地址空间（或物理地址空间），简称内存空间（或物理空间）。它是一维线性空间，其编址顺序为0，1，2，3， n-1，n的大小由实际组成存储器的存储单元个数决定。比如，某个系统，有64K内存，则其内存空间编号为0，1，2，3，65535。2. 逻辑空间我们用汇编语言或高级语言编写程序时，常常用符号名来访问某一单元。我们把程序中由符号名组成的程序空间称为符号名空间，简称名空间。源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。一个编译好的程序存在于它自己的逻辑地址空间中，运行时，要把它装入内存空间，图3.2显示了一个作业在编译前、编译后及装入内存后不同的地址空间。物理空间01002002991000110012001299名空间逻辑地址空间Mov R1,dataMov R1,200Mov R1,200 data:681768176817图3.2 作业的名空间、逻辑地址空间和装入后的物理空间由图3.2可以看出，该作业经过编译后，大小为300个字节，逻辑地址空间为0299。在作业的第100号单元处有指令Mov R1，200，即把200号单元内的数据6817送入寄存器R1。假如把作业装入到内存第10001299号单元处。由图3.2可以看出，若只是简单地装入第10001299号单元，执行Mov R1，200指令时，会把内存中200号单元的内容送入R1，显然这样会出错。只有把1200号单元的内容送入R1才是正确的。所以作业装入内存时，需对指令和指令中相应的逻辑地址部分进行修改，才能使指令按照原有的逻辑顺序正确运行。3. 地址重定位我们把用户程序装入内存时，对有关指令的逻辑地址部分的修改称为地址重定位，即地址重定位是建立用户程序的逻辑地址与物理地址之间的对应关系。按实现地址重定位的时机不同，地址重定位又分为两种：静态地址重定位和动态地址重定位。1 静态地址重定位静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的。它根据要装入的内存起始地址，如图3.2中为1000号单元，直接修改所有涉及到的逻辑地址，将内存起始地址加上逻辑地址得到正确的内存地址，如100号单元的Mov R1，200装入内存后，被装入到1100号单元，且指令中逻辑地址被改为Mov R1，1200，这样指令就可正确读取数据了。静态重定位后的内存空间如图3.3（a）所示。1000b1100b1200b1299b1000b1100b1200b1299b 内存地址1000b200b1200b重定位寄存器逻辑地址Mov R1,1200Mov R1,20068176817 （a） 采用静态重定位后的内存空间 （b） 采用动态重定位时内存空间及地址重定位示意图图3.3 静态地址重定位和动态地址重定位示意图静态地址重定位的优点是通过重定位装入程序，实现逻辑地址到物理地址的转化，不需要硬件的支持，可在任何机器上实现。早期的操作系统中大多数采用这种方法。缺点是程序必须占用连续的内存空间，且一旦装入内存后，因为逻辑地址已被改变，就不便再移动，不利于内存空间的利用。所以静态地址重定位只适用于静态的内存分配方式。2 动态地址重定位动态地址重定位是在程序执行期间进行的。一般说来，这种转换由专门的硬件机构来完成，通常采用一个重定位寄存器，在每次进行存储访问时，对取出的逻辑地址加上重定位寄存器的内容，形成正确的物理地址，重定位寄存器的内容是程序装入内存的起始地址，如图3.3（b）所示。动态地址重定位的优点是不要求程序装入固定的内存空间，在内存中允许程序再次移动位置，而且可以部分地装入程序运行，也便于多个作业共享同一程序的副本，因此，现代计算机系统广泛采用动态地址重定位技术。动态地址重定位技术缺点是需要硬件支持，而且实现存储管理的软件算法也较为复杂。一般说来，动态地址重定位允许采用静态和动态两种存储分配方式。3.1.4 存储保护在多道程序设计环境中，要保证各道程序只能在自己的存储区中活动，不能对别的程序产生干扰和破坏，尤其是不能破坏操作系统的内存区。因此，必须对存储信息采取各种保护措施，这也是存储管理的一个重要功能。存储信息的保护体现在不能越界访问，破坏操作系统或其他用户的程序。实现这种存储保护，可以采用硬件的方法，也可采用软、硬件结合的方法。通常使用较为普遍的是采用硬件的界限寄存器保护法。下面我们讨论一下界限寄存器保护的两种具体实施技术，上、下界保护和基址限长保护方法。 上、下界存储保护：上、下界保护是一种简单的存储保护技术。系统可为每道作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。如图3.4（a）所示，某作业在内存的起始位置是20kb，结束位置是25kb，上、下界寄存器的值分别为25kb和20kb。在作业运行过程中，每当要访问内存某单元时，就检查经过重定位后产生的内存地址是否在上、下界寄存器所规定的范围之内，若在，则访问是合法的，可以进行；否则，产生越界中断，通知系统进行越界处理。256k-1256k-125k20k0k作业20k25k0k作业20k基址寄存器限长寄存器5k20k下界寄存器上界寄存器25k （a） 上、下界保护 （b） 基址限长保护图3.4 界限寄存器的两种存储保护方式 基址限长存储保护：上、下界保护的一个变种是采用基址限长存储保护。系统可为每个作业设一个基址寄存器和一个限长寄存器，基址寄存器存放该作业在内存的首址，限长寄存器存放该作业的长度。如图3.4（b）所示，基址寄存器的值为20kb，限长寄存器的值为5kb。在作业运行时，每当要访问内存单元时，就检查指令中的逻辑地址是否超过限长寄存器的值，若不超过，则访问是合法，可以进行；否则，视为非法访问。基址限长存储保护通常可结合动态地址重定位实现，基址寄存器相当于重定位寄存器。对于存储保护除了防止越界外，还可对某一区域指定专门的保护方式。常见的对某一区域的保护方式有四种：禁止做任何操作；只能执行；只能读；能读/写。如对许多用户可共享的程序，一般设定为只能执行，而对许多用户可共享的数据，则设定为只能读；一般的用户数据则是可读/写的。3.1.5 虚拟存储器随着计算机技术应用得日益广泛，需要计算机解决的问题越来越复杂。有许多作业的大小超出了内存的实际容量。尽管在现代技术的支持下，人们对内存的实际容量进行了不断的扩充，但大作业、小内存的矛盾依然非常突出，再加上多道程序环境中，多道程序对内存的共享，使内存更加紧张。因此，要求操作系统能对内存进行逻辑意义上的扩充，这也是存储管理的一个重要功能。对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。虚拟存储不是新的概念，早在1961年，就由英国曼彻斯特大学提出并在Atlas计算机系统上实现，但直到20世纪70年代以后，这一技术才被广泛采用。虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的逻辑延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行所必需的一部分信息存入内存，其它则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。当然，内存中暂时不用的信息也可调至外存，以腾出内存空间供其它作业使用。这些操作都由存储管理系统自动实现，不需用户干预。对用户而言，只感觉到系统提供了一个大容量的内存，但这样大容量的内存实际上并不存在，是一种虚拟的存储器，因此把具有这种功能的存储管理技术称为虚拟存储管理。实现虚拟存储管理的方法有请求页式存储管理和请求段式存储管理。为了实现存储管理的上述功能，人们研究并总结出来各种存储管理方案。下面，我们分别予以介绍。3.2 连续存储管理常用的连续存储管理技术有固定分区存储管理和可变分区存储管理，下面分别介绍。3.2.1 固定分区存储管理固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。其基本思想是，在作业未进入内存之前，就由操作员或操作系统把内存可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目都不变，所以固定分区也称为静态分区。在固定分区存储管理系统中，每个用户作业运行时可分配到一块足够大的区域，用户作业一次性全部装入到分配区，并限制作业只能在这个分区中运行。由于分区大小一般不可能刚好等于作业大小，所以分区中常有已分配给某作业，但未被使用的空闲部分，我们把它们称之为分区的内部碎片。假设某系统有256k内存，刚开始运行时，内存分区划分如图3.5（a）所示。除操作系统占用一个低地址分区40k以外，其余的内存空间（216k）划分成4个不等的分区。为简单起见，分区大小由小到大排列。第1分区为8k，第二分区为32k，第3分区为64k，第四分区为112k。为了进行分区的分配和回收，在固定分区存储管理系统中，应有一张记录内存分区使用情况的分区说明表，如图3.5（b）所示。分区说明表用来记录各分区的起始地址、分区大小和分区的分配状态。若分配状态为0，则表示该分区未分配；若分配状态为1，则表示该分区已分配。假设现在分区4已分配给作业1，分区1、2和3尚未分配，是空闲分区。固定分区的内存分配与回收比较简单。当某个作业，比如作业2，大小为30k，要求装入内存运行时，系统首先查询分区说明表，从中找到一个满足作业要求的空闲分区，此时找到分区2，将相应表项的状态位置为1，然后向用户返回分区号或分区起始地址，完成内存的分配工作；如没有能满足作业要求的空闲区，则无法分配。当一个用户作业完成后，释放其占用的内存分区，系统根据分区号或起始地址找到分区说明表相应表项，将其状态置为0，表示该分区已空闲，可供其它作业使用。固定分区的地址重定位一般可由重定位装入程序来完成，即采取静态地址重定位方法，固定分区的存储保护可采用上、下界寄存器保护方式。固定分区存储管理的最大优点是简单，要求的硬件支持少，软件算法也简单，缺点是容易产生内部碎片，如图3.5（a）所示，第二分区共32k分配给作业2，因作业2只有30k，故产生2k大小的碎片，内存的利用率不高。在早期的IBM公司的OS/360MFT（具有固定任务数的多道程序系统）采用了固定式分区存储管理方法。0k40k48k80k144k256k-1（a）操作系统空闲分区第一分区（8k）作业2第二分区（32k） 分区号起始地址分区大小状态140k8k0碎片（2k）248k32k1空闲分区第三分区（64k） 380k64k04144k112k1作业1第四分区（112k）（b） 图3.5 固定式分区内存分配示意图（a）和（b）固定式分区说明表3.2.2 可变分区存储管理固定分区存储管理在作业未装入时，分区的大小、数目已定，容易造成分区的内碎片问题，为此，人们提出了可变式分区的概念。可变式分区是指在作业装入时，依据它对内存空间实际的需求量来划分内存的分区，因此，每个分区的尺寸与进入它的作业大小相同。它能有效解决固定式分区的内部碎片问题，是一种较为实用的存储管理方法。因为在系统运行过程中，内存中分区的数目和大小都是可变的，所以这种可变式分区也称为动态分区。如图3.6所示，假设某系统采用可变式分区存储管理，在系统运行的开始，存储器被分为操作系统分区（40k）和可分给用户的空闲区（216k）。当作业1（46k）进入内存后，分给作业1（46k），随着作业2、3、4的进入，分别分配32k，38k，40k，经过一段时间的运行后，作业1、3运行完毕，释放所占内存。此时，作业5进入系统，要求分配36k内存，如何为作业5分配内存呢？操作系统作业1（46k）作业2（32k）作业3（38k）作业4（40k）空闲（60k）操作系统空闲1（46k）作业2（32k）空闲2（38k）作业4（40k）空闲3（60k）操作系统 空闲分区（a） 可变式分区运行开始 （b） 作业1、2、3、4进入内存 （c） 作业1、3释放后内存图3.6 可变式分区内存使用情况示意图如图3.6（c）所示，此时，有三种方法可给作业5分配内存：从作业1释放的46k中，分36k给作业5，即分配空闲区1；从作业3释放的38k中，分36k给作业5，即分配空闲区2；从空闲的60k中，分36k给作业5，即分配空闲区3。到底采用哪种分配方法呢？这时，应考虑空闲分区的组织形式和采用的内存分配算法。1. 空闲分区的组织形式在可变式分区存储管理中，常把空闲区组成空闲分区表或空闲分区链表的形式。空闲分区表的组织类似于固定分区的分区说明表，包含空闲分区的起始位置和大小，因分区数目不定，故空闲分区表长度不定。采用空闲分区表要占用一定数量的存储单元存放表，增加了系统的开销。所以使用比较广泛的是空闲分区的链表组织形式。空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。如图3.7（a）所示，链表按空闲分区在内存的位置顺序由小到大链接起来，空闲分区的链表头指针指向内存中第一个空闲分区的起始地址40k。因空闲分区链表组织时，空闲区的信息放在空闲区内，因此不会额外增加系统的开销。2. 内存的分配与回收在可变式分区存储管理中，当作业要求一个Xk大小的存储空间时，系统从链表头指针开始依次检索空闲区，直到找到第一个大于等于Xk的空闲区。若系统中所有空闲区都小于Xk，则无法分配。若有空闲区等于Xk大小，则修改链表指针，取消该空闲区，并向用户返回该空闲区首地址。若该空闲区大于Xk，则将空闲区一分为二，一个为Xk，分给用户，另一个为余下部分，仍留在空闲区链表中，修改相应链表指针所指向的地址和空闲区大小。当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。3. 常用的分配算法可变分区存储管理中，对空闲区链表采用不同的组织形式，就对应不同的分配和回收算法。常用的分配算法有以下三种。 首次适应算法：这种算法把空闲分区按其在存储空间中地址递增的顺序链接在一起。当用户申请一块内存空间时，从空闲区链表的头指针开始查找，选择第一个满足要求的空闲分区。如果它不等于作业大小，将其分成两部分，一部分给作业，另一部分仍留在空闲区链表中。图3.7（a）中，空闲区就是按首次适应算法组织的，链接顺序依次是：空闲分区1，2和3。此时，按链接顺序可将空闲分区1，即自40k开始的原作业1释放的46k中，分36k给作业5，剩余10k留在空闲区链表中，调整链表的头指针，指向新的空闲区开始位置76k。作业5进入后的内存分配情况及空闲区链表组织情况如图3.7（b）所示。0k40k86k118k156k196k256k-176k链表头指针40k链表头指针0k40k86k118k156k196k256k-1操作系统操作系统118k46k作业5（36k）空闲分区1118k10k作业2（32k）新的空闲分区196k38k作业2（32k）空闲分区2196k38k作业4（40k）空闲分区260k作业4（40k）空闲分区360k空闲分区3（a） 作业5未进入内存之前 （b） 作业5进入内存之后图3.7 首次适应算法的空闲分区链表组织形式当系统回收一个分区时，首先检查是否有前、后相邻的空闲区。如有，则进行合并，合并后的空闲区仍保留在链表的原位置上，但需修改相应链表指针和分区大小。如图3.7（a）所示，若在当前状态下，作业2完成，则与前、后两个空闲区都相邻，完成合并后，链表头指针仍指向40k，链接指针则指向196k，分区大小成为116k。如回收的分区不和其它空闲区相邻，则根据起始地址大小把它插到链表的相应位置上。一般说来，只要查找半个表就可以找到合适的位置。 首次适应算法的优点是分配和回收算法都比较简单，查找速度快，因这个算法总是从低地址开始查找，因此留在高地址部分的大空闲区被划分机会少，在大作业到来时容易满足。 最佳适应算法：此种算法把空闲分区链表按分区大小由小到大进行组织。当有作业申请内存时，总是首先找到满足要求的最接近于作业大小的空闲分区。因分区大小与作业相近，从而避免将较大的分区分成两部分，当有较大的作业要求分配内存时，容易得到满足。在图3.6（c）情况下，空闲分区若按最佳适应算法组织，形成的链表如图3.8（a）所示。链接顺序依次为：空闲分区2，1和3，链表头指针指向空闲分区2的首地址118k。当作业5要求进入时，会将自118k开始的原作业3的38k，即空闲分区2分给作业5，剩余的2k，仍留在空闲区链表中。作业5进入后的内存分配情况及空闲区链表组织情况如图3.8（b）所示。最佳适应算法，理论上看起来比较完美，但每次分配时总产生极小的空闲分区，经过一段时间运行，内存中可能有多个这样的小分区，因太小而无法分配给其它作业使用。这些无法使用的小分区，我们称之为外部碎片，外部碎片的增多会降低空闲区链表的查找速度。为此，人们又在此算法中设定一个参数G，当从一个分区中，分配Xk给某作业后，剩余部分小于G时，就把整个分区分配给该作业，不再划分成两部分。采用最佳适应法的另一个问题是，回收一个分区时，为了把它插入到空闲区链表的合适位置，也是比较费时的。0k118k156k196k256k-10k118k154k156k196k256k-1118k链表头指针154k链表头指针40k86k40k86k操作系统操作系统196k46k196k46k空闲分区1空闲分区1作业2（32k）作业2（32k）40k38k作业5（36k）空闲分区240k2k作业4（40k）新的空闲分区60k作业4（40k）空闲分区360k空闲分区3 （a） 作业5未进入内存之前 （b） 作业5进入内存之后图3.8 最佳适应算法的空闲分区链表组织形式 最差适应算法：这种算法要求把空闲区按从大到小递减的顺序组织成空闲区链表。当用户申请一个存储区时，总是检查空闲区链表的第一个空闲区是否满足要求，若不满足，分配失败；若满足，则将该空闲区分配给用户，然后修改和调整空闲区链表。在图3.6（c）情况下，空闲区若按最差适应算法进行组织，形成的链表如图3.9（a）所示。链接顺序依次为：空闲分区3，1和2。作业5申请内存时，按查找顺序，应将原空闲的自196k开始的60k中划分36k给作业5，剩余24k仍在空闲区链表中，但其在空闲区链表的位置需调整。作业5插入后的内存分配情况及空闲区链表组织情况如图3.9（b）所示。最差适应算法的优点是查询简单，而且每次分配的总是最大的空闲区，除用户使用的外，剩余的空闲区还可能相当大，还能装入较大的程序，但缺点也在于此，每次总从最大的空闲分区分配，当有大的作业到来时，其存储分配申请往往得不到满足。这三种算法，各有利弊。到底哪一种好，不能一概而论，应针对具体的作业序列来分析。如果对于某一作业序列来说，某种算法能将该作业序列中的所有作业安置完毕，那么我们就认为该算法对这一作业序列而言是合适的。0k40k86k118k156k196k232k256k-1196k链表头指针40k链表头指针操作系统0k40k86k118k156k196k256k-1操作系统118k46k118k46k空闲分区1空闲分区1作业2（32k）作业2（32k）38k232k38k空闲分区2空闲分区2作业4（40k）作业4（40k）40k60k作业5（36k）空闲分区324k新的空闲分区 （a） 作业5未进入内存之前 （b） 作业5进入内存之后图3.9 最差适应算法的空闲分区链表组织形式操作系统空闲区1（16k）已使用空闲区2（14k）已使用空闲区3（5k）已使用空闲区4（30k）已使用0k40k56k70k84k100k105k150k180k256k比如，现在有一作业序列，作业A（15k），作业B（16k），作业C（15k），依次要求进入系统运行，假设此时系统的空闲区按地址顺序排列，分别是起始地址为40k的空闲区1（16k）、起始地址为70k的空闲区2（14k）、起始地址为100k的空闲区3（5k）、起始地址为150k的空闲区4（30k），内存分配情况如图3.10所示。用首次适应算法、最佳适应算法和最差适应算法来处理该作业序列，看哪种算法是合适的。为了简单明了，我们把三种算法的空闲区用链表形式组织起来，如图3.11 （a）、（b）、（c）所示。在图3.11中，由三种算法的空闲区链表组织形式，结合 动态分区分配，可以分析得出这样的结论：对于作业A（15k）， 图3.10 内存使用情况作业B（16k），作业C（15k）而言，首次适应算法和最佳适应算法都只能分配作业A和作业B，不能再分配作业C，即不能对这三个作业进行完全吞吐。只有最差适应算法，可将作业A、作业B、作业C这个作业序列的三个作业全部分配，所以最差适应算法对该作业序列而言是合适的。在内存状态如图3.10所示情况下，若作业进入内存的顺序依次为：作业B（16k），作业A（15k），作业C（15k），则由图3.11的三种算法的链表组织形式可以分析得出，首次适应法和最佳适应法都能将该作业序列完全吞吐，而最差适应法不能将该作业系列完全吞吐。实际应用时，应综合考虑不同情况，如用户要求、内存大小、作业平均大小等因素，选择合适的分配算法。还有一种伙伴算法在实际中应用很普遍，有关伙伴算法将在3.8.2节详细介绍。40k链表头指针16k14k5k30k70k100k150k（a） 首次适应算法空闲区链表组织100k链表头指针5k14k16k30k70k40k150k（b） 最佳适应算法空闲区链表组织150k链表头指针30k16k14k5k40k70k100k（c） 最差适应算法空闲区链表组织图3.11 用三种适应算法处理同一作业序列4. 可变分区存储管理的地址重定位可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。 如采用静态重定位，因用户作业进入内存后，程序的逻辑地址实现了重定位，不能在内存中再进行移动，经过一段时间的运行，内存中不能再分配的小碎片会越来越多。有时可能会出现这种情况，即当一个作业申请一定数量的内存时，虽然此时空闲区的总和大于新作业的内存要求，但却没有单个的空闲区足以装下该作业。解决这个问题的办法之一是采用紧凑技术，即把小碎片集中起来使之成为一个大分区。实现的方法是移动各用户分区中的程序，使他们集中于内存的一端，而使碎片集中于另一端，从而将空闲的碎片连成一个较大的分区，供需求的作业使用。为此，必须采用动态重定位技术，才能使用户程序在内存中进行移动。 采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图3.12所示 。可变式分区的存储保护可采用基址限长存储保护方式。可变式分区存储管理的优点是可以有效解决固定式分区的内部碎片问题，能较有效利用内存空间，提高了多道程序系统对内存的共享。缺点是容易产生外部碎片问题，为解决外部碎片问题，需要采用动态重定位，增加了计算机硬件成本，而紧凑工作又要花费大量处理机时间。3.3 分页式存储管理在可变分区存储管理系统中，要求一个作业必须装入内存某一连续区域内。这样，经过一段时间的运行，随着多个作业的进入与完成，内存中容易产生许多分散的、比较小的外部碎片。解决这一问题的一个方法是采用紧凑技术，但紧凑技术比较花费处理机时间。为此，人们考虑另一种解决方法，即打破一个作业必须装入内存连续区域的限制，可把一个作业分配到几个不连续的区域内，从而不需移动内存原有的数据，就可有效地解决碎片问题。这一思想的应用就是分页式存储管理。分页式存储管理是在大型机操作系统中被广泛采用的一种存储管理方案。空闲区和=Xk某作业申请Xk内存有=XK空闲区 分配分区并修改相应链表指针返回分区号给作业无法分配紧凑内存各空闲区并修改相应链表指针NYNYNNYYY图3.12 采用动态重定位的可变式分区分配算法分页式存储管理的基本思想是，把内存空间分成大小相等、位置固定的若干个小分区，每个小分区称为一个存储块，简称块，并依次编号为0，1，2，3,，n块，每个存储块的大小由不同的系统决定，一般为2的n次幂，如1KB，2 KB，4 KB等，一般不超过4 KB。而把用户的逻辑地址空间分成与存储块大小相等的若干页，依次为0，1，2，3，m页。当作业提出存储分配请求时，系统首先根据存储块大小把作业分成若干页。每一页可存储在内存的任意一个空白块内。此时，只要建立起程序的逻辑页和内存的存储块之间的对应关系，借助动态地址重定位技术，原本连续的用户作业在分散的不连续存储块中，就能够正常投入运行。如果把一个作业的所有页面一次全部装入到内存块中，就把这种分页称之为分页式存储管理。如果作业的所有页面并不是一次全部装入，而是根据作业运行时的实际要求装入，则把这种分页管理称为请求页式存储管理。本节先讨论分页式存储管理。3.3.1 分页式存储管理中存储块的分配与回收分页式存储管理中，存储块的分配与回收算法比较简单。当作业有存储分配请求时，可以根据逻辑地址的大小计算出需要多少存储块，然后将空闲块分配给它们使用。通常有两种记录空闲存储块的方法：位图法和链表法。 位图法位图法是用存储单元中的二进制位与存储块相对应，某位的值为0，表示对应的存储块是空闲的，其值为1，表示已分配。把这些二进制位组合在一起，就构成一张位图。如图3.13（a）所示，假设内存中前16块的情形是：0，1两块由操作系统占用，作业1占用2，8，12三块，作业2占用4，7，10，14四块，3，5，6，9，11，13，15是空闲块，图3.13（b）反映了此时系统采用位图法表示的存储块使用情况。位图是记录存储块使用情况的最简单方法，内存被划分成多少块，就有多少个二进制位与之对应。使用位图法对存储块进行管理，查找空闲块比较费时，但回收时比较简单，只需将该块对应的位图中二进制位置0即可。 链表法在分区存储管理中，使用链表方式来管理空闲分区的方法同样也适于页式存储管理，而且由于块的大小相同，在每个空闲块中只需包含有下一个空闲块的指针信息即可。系统设定一个空闲块链表头指针指向链表的第一个空闲块。当用户申请内存时，根据链表头指针顺序分配即可；回收时，只需将该块插入表头就可以。操作系统 操作系统作业1作业2作业2作业1作业2作业1作业21110100110101010（a） 块使用情况 （b） 存储块使用情况的位图表示图3.13 存储块的位图管理法3.3.2 分页式存储管理的地址重定位 分页式存储管理中的地址重定位是非常重要的，要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器用得太多。通常可在内存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映象表，简称页表。最简单的页表只包含页号、块号两个内容。页表的起始地址、长度，放在该作业的进程控制块PCB中。对当前运行作业的页表由一个专用的控制寄存器页表始址寄存器来指定。每当运行一个新作业就将该作业的页表始址、长度从进程控制块中取出。在作业执行过程中，由硬件地址分页结构自动将每条程序指令中的逻辑地址解释成两部分，页号p和页内地址w。通过页号查页表得到存储块号b，与页内地址w合成，形成物理地址，访问内存，得到操作数据。逻辑地址由硬件分成的两部分页号p和页内地址w是系统自动进行的，对用户是透明的。页内地址的长度由页大小决定，逻辑地址中除去页内地址所占的低位部分外，其余高位部分为页号。假定一个系统的逻辑地址为16位，页大小为1KB，则逻辑地址的低10位（210=1 KB），被解释成页内地址w，而高6位则为页号p，地址结构如下：15 10 0 0页号p（6位）页内地址w（10位）现在我们举例说明动态地址重定位的实现过程。比如，现有一个系统，内存容量共256k，存储块的大小为1k，共有256块，编号为0255。第04块为操作系统所使用。现有2个用户作业，作业1和作业2，其逻辑地址空间分别占2k和2.5k，进入系统后，按块的大小划分分别占2页和3页（因内存是以块为单位分配的），它们的分页情况如图3.14所示。0k操作系统0k1k2k-1作业1页号块号4k0页05空闲5k1页18作业1（0页）6k作业1页表作业2（0页）7k0k作业2作业2（1页）8k1k0页06作业1（1页）9k2k1页17空闲10k2.5k-12页210作业2（2页）11k作业2页表空闲12k图3.14 分页式存储管理示意图在图3.14中的页表反映了作业1和作业2的各页在内存中相应的存储块号。假设作业2正在运行，在第0页某单元处有一条指令MOV R1，2500，因每页长度为1k，所以由逻辑地址的低10位构成页内地址，2500为十进制数，转化为十六进制为09C4H（二进制为0000100111000100），取低十位为1C4H，为页内地址w；高6位为2，形成页号p，查页表知第2页在内存第10块，得到内存地址的块号b，逻辑地址的页内地址作为块内地址w，一起构成新的物理地址为29C4H单元，访问该单元，把其中的数据016817送入R1寄存器，具体实现过程如图3.15所示。3.3.3 联想存储器从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问两次内存：一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。0 61 72 10001010 0111000100W=1C4H页表始址寄存器页号p 页内地址wa 块号 b 块内地址w0k10k256k-1000010011100010009C4H内存0k1k2k3k-1作业2Mov R1,2500 P=2 29C4H016817016817 页号 块号图3.15 分页式存储管理地址重定位实现过程逻辑地址页表始址寄存器apw联想存储器页号块号pb页表bw页号块号 物理地址Pb 利用快表查找 利用页表查找