第4节1 存储器管理

2020/2/251第四章存储器管理(MemoryManagement)存储器是计算机系统的重要组成部分。近年来，虽然内存容量在不断扩大，但内存仍是宝贵资源。如何提高主存储器利用率，并扩充主存，对主存信息实现有效保护是存储器管理主要任务，也是各种不同存储管理方法的目标。2020/2/2524.1存储器的层次结构外存(secondarystorage)快速缓存(cache)寄存器(register)内存(primarystorage)图4.1存储层次结构2020/2/253寄存器是CPU内的硬件，存取速度非常快，可与CPU执行速度匹配，但是价格昂贵，容量小。内存用来存放进程运行时程序和数据。CPU的控制部件只能从内存中取得指令和数据，数据能够从内存中读取并将它们装入到寄存器，或者是从寄存器存入内存中。内存数据存取速度也很快很难与CPU速度匹配。2020/2/254快速缓存：将内存中一些经常被访问的信息存放在缓存中，减少访问内存的次数，可大幅度的提高程序的执行速度。有的计算机设置了两级或者多级缓存。紧靠内存的那一级速度最快而容量小。外存：就是硬盘和移动U盘等。对外存的管理属于设备管理的范畴。2020/2/2554.2程序的装入和链接将一个用户源程序变为一个可在内存中执行的程序要经过下面的几个步骤：库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存…图4-2对用户程序的处理步骤2020/2/256逻辑地址（相对地址）：相对用户程序模块，以0地址为起始地址的编址方式。物理地址（绝对地址）：相对于内存，每一单元有唯一地址的编址方式。地址重定位（Relocation)：把相对地址转换成内存中的绝对地址的过程，也叫地址映射（map）。2020/2/2574.2.1程序的装入一个源程序经过编译和链接之后，将会形成一个装入模块。将一个装入模块装入内存时，可采用下面的三种方式：1绝对装入方式(AbsoluteLoadingMode)它是将装入模块装入到内存中事先指定的位置。它只适用于单道程序环境，不适用于多道程序（为什么？），它的缺点很明显。2静态重定位装入方式(staticRelocationLoadingMode)在装入时，由装入程序对目标程序中的相对地址进行重定位修改，一次完成，（装入时重定位）。2020/2/258LOAD1,2500365LOAD1,2500365100001100012500150005000250010000作业地址空间内存空间图4-3作业装入内存时的情况返回2020/2/259在程序中需要修改的位置称为重定位项。程序装入内存中的起始地址称为重定位因子。由于地址变换是在装入时一次完成，以后不再改变故也叫做静态重定位。静态重定位虽然有无须硬件支持的优点，容易实现，但是也存在明显的缺点：一是程序重定位以后就不能在内存中移动；二是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。2020/2/25103动态重定位装入方式在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。动态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件—重定位寄存器的支持。如图：2020/2/2511重定位寄存器2020/2/2512程序的目标模块在装入内存时，与地址有关的指令都不必进行修改，如在图中LOAD1，300这条指令中仍保持相对地址300。当该模块被操作系统调度到处理机上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图中该模块的基地址为0），然后将其差值装入重定位寄存器。2020/2/2513当CPU取一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据。由此可见，动态重定位是在指令执行过程中动态进行，这样可以带来两个好处：⑴目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，程序在执行期间可以换入和换出内存，这样可以缓解内存紧张的矛盾，解决了静态重定位不可移动的问题。2020/2/2514⑵不必给程序分配连续的内存空间，可以较好地利用较小的内存块，这便于存储器用紧缩来解决存储器的碎片问题。动态地址再定位的缺点：需要附加的硬件支持，而且实现存储管理的软件算法比较复杂。2020/2/25154.3连续分配存储方式计算机对装入内存的程序有两种分配方式：连续分配和离散分配。连续分配：为一个用户程序分配一个连续的内存空间，主要用于60－70年代。它又分为二种：单一连续分配方式和分区式分配方式离散分配：将一个用户程序离散的分配到内存空间中去，它有分页和分段两种分配方式。2020/2/25164.3.1、单一连续分配这是一种最简单的存储管理方式，在内存中只有一道程序，如在8位和16位微机上MS-DOS操作系统。它将内存分为两个区：系统区：仅供操作系统使用，通常设置在内存的低段；用户区：指除系统区以外的全部内存空间，提供给用户使用。2020/2/2517单一连续分区的优点是：简单，适用于单用户、单任务的操作系统(比如CP/M和DOS操作系统)，不需要复杂的硬件支持。单一连续分区的缺点是：一个作业运行时要占用整个内存的地址空间，即使很小的程序也是如此，对内存造成了很大的浪费，内存的利用率很低。2020/2/25184.3.2固定分区(FixedPartitioning)分配固定式分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。这种分区方式一般将内存的用户区域划分成大小不等的分区（各个分区也可大小相等），以适应不同大小的作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。2020/2/2519图4-4固定分区使用表改为20K2020/2/2520☻如果系统使用尺寸相等的分区，那么当系统欲把一个进程装入内存时，系统只要找到一个可用的分区即可。☻如果系统使用尺寸不等的分区，那么当系统欲把一个进程装入内存时，系统可选用下述两种方案中的一种：☻保证所选择的分区既能放得下相关进程同时该分区没有被使用的空间最小；☻仅仅保证所选择的分区能够放得下相关进程即可。2020/2/2521☻长处：实现简单；系统开销小。☻不足：因已分配分区存在内零头(InternalFragment)而使存储利用率不高；因分区尺寸固定而使系统无法运行大程序；因分区数目固定而使活动进程的数目受限。2020/2/25224.3.3动态式分区分配(DynamicPartitioning)动态式分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。动态式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为可变式分区。2020/2/2523可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收一个已经运行完的作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。2020/2/25242020/2/25252020/2/2526分析：会产生外零头(ExternalFragment)。在上图中，如果这个时候进程3执行完了，则将相邻的空闲分区合并，以得到更大的空闲分区，不相邻则不能合并。和固定分区分配比较起来，内存内的分区数目不定，是动态发生改变的，故称为动态分区分配。如果这个时候有一个100K大小的进程进入内存，则会怎么样？如何解决?2020/2/25271、可变式分区中用到的数据结构管理空闲内存区的数据结构可采用连续线性表格法和链接法。（1）空闲区表形式在系统中设置一张空闲分区表，用于记录每个空闲分区的情况，包括分区的序号、大小、始址和状态，每个空闲分区作为一个表项。2020/2/2528（2）空闲区链形式为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。2020/2/25292、分区分配算法(PartitioningPlacementAlgorithm)（1）首次适应算法（FirstFit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。2020/2/2530（2）循环首次适应算法（next-fit）：该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。2020/2/2531（3）最佳适应算法（BestFit）：它从全部空闲区中找出能满足作业要求的、且是最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。2020/2/2532（4)）最坏适应算法(worst-first)最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲分区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。算法基本不留下小空闲分区，但较大的空闲分区不会被保留。2020/2/2533最坏适应算法的优点：分配的时候只需查找一次就可以成功，分配的算法很快。最坏适应算法的缺点：最后剩余的分区会越来越小，无法运行大程序。2020/2/25344.3.4伙伴系统-buddysystem在伙伴系统中，我们假设整个内存的大小为2U，系统初始启动时整个内存将被视作单一的空闲分区。伙伴系统主要涉及内存的分配与回收两个方面的内容。下面先看一个例题：2020/2/25352020/2/2536从上面的例题可以看出伙伴系统的分配算法如下：当系统欲把一个大小为k的进程装入内存时，如果2i-1＜k≤2i，那么系统将使用下面的算法为该进程分配一个尺寸为2i的空闲分区：1、如果i=U+1，那么意味着进程的大小超出了整个内存，故分配失败；2、如果尺寸为2i的空闲分区链表为空，那么意味着当前不存在尺寸为2i的空闲分区，故：⑴设法找到一个尺寸为2i+1的空闲分区，为此把i调整为i+1并再次调用本算法；⑵把找到的尺寸为2i+1的空闲分区分解为两个尺寸为2i的伙伴分区；⑶把两个尺寸为2i的伙伴分区加入到尺寸为2i的空闲分区链表中；3、取尺寸为2i的空闲分区链表中的第一个空闲分区作为本算法的返回结果。2020/2/2537当一个进程释放一个尺寸为2i的分区时，系统将使用下面的算法回收该分区：如果被回收分区其伙伴分区不是空闲的，那么把被回收分区加入到尺寸为2i的空闲分区链表中否则⑴将被回收分区其伙伴分区从尺寸为2i的空闲分区链表中摘除；⑵合并被回收分区及其伙伴分区，从而得到一个尺寸为2i+1的空闲分区；⑶系统再次调用本算法回收上一步得到的尺寸为2i+1的空闲分区。2020/2/25384.3.6动态重定位分区分配1拼接/紧凑技术当系统欲把一个进程装入内存时，它将为该进程分配一个大小合适的分区。显然，这样做