4第四章存储器管理第四版.

第四章存储器管理•4.1存储器的层次结构•4.2程序的装入与链接•4.3连续分配存储管理方式•4.4对换（Swapping）•4.5分页存储管理方式•4.6分段存储管理方式4.1存储器的层次结构4.1.1多层结构的存储器系统1.存储器的层次结构在现代计算机系统中，存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存4.1.2主存储器与寄存器（引导阅读）1．主存储器2.寄存器4.1.3高速缓存和磁盘缓存（引导阅读）1.高速缓存2.磁盘缓存•高速缓存Cache：少量的、非常快速、昂贵、易变的•内存RAM：若干兆字节、中等速度、中等价格、易变的•磁盘：数百兆或数千兆字节、低速、价廉、不易变的•由操作系统协调这些存储器的使用4.2程序的装入和链接编译：由编译程序(Compiler)将用户源代码编译成若干个目标模块(ObjectModule)；链接：由链接程序(Linker)将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块(LoadModule)；装入：由装入程序(Loader)将装入模块装入内存。对用户程序的处理步骤4.2.1程序的装入1.绝对装入方式程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。2.可重定位装入方式作业装入内存时的情况3.动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。4.2.2程序的链接程序链接示意图1.静态链接方式2.装入时动态链接装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。3.运行时动态链接这种链接方式是将对某些模块的链接推迟到执行时才执行，即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4.2.3重定位把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。如下图，作业i经过重定位，把地址集合映射到以1000为始址的内存中，作为作业i的存储空间。4.3.1单一连续分配•在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：系统区、用户区、空闲区。用户占用区是一个连续的存储区所以又称单一连续区存储管理。•单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用4.3连续分配存储管理用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统0单一连续区存储分配示意图工作流程：单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。单用户系统缺点：•不支持多道。•主存利用率不高。•程序的运行受主存容量限制。4.3.2固定分区分配分区式管理是满足多道程序的最简单的存储管理方案。它的基本思想是将内存划分成若干个连续区域，称为分区。每个分区只能存储一个程序，而且程序也只能在它所驻留的分区中运行。•预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同。但分区大每个分区装一个且只能装一个作业小固定不变。(1)分区大小相等，即使所有的内存分区大小相等，其缺点是缺乏灵活性。(2)分区大小不等。为了克服分区大小相等而缺乏灵活性的这个缺点，可把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。1.划分分区的方法分区4分区3分区2分区1操作系统多个等待队列单个等待队列分区4分区3分区2分区1操作系统固定分区示意图2.内存分配固定分区使用表存储分配：如果有一个空闲区,则分配给进程，通过设置内存分配表，内存分配简单。缺点：内存利用率不高4.3.3动态分区分配•基本思想：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间•内存管理：设置内存空闲块表——记录了空闲区起始地址和长度•内存分配：动态分配•内存回收：当某一块归还后，前后空间合并，修改内存空闲块表1.分区分配中的数据结构(1)分区分配表(2)空闲分区链空闲链结构前向指针0N个字节可用后向指针0N+2N+20K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配80K30K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分区分配表：0K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配空空始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K3.分区分配操作1)分配内存系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.size≤size(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图示出了分配流程。内存分配流程从头开始查表检索完否？m.size＞u.size?m.size-u.size≤size?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN2)回收内存当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：(1)回收区与插入点的前一个空闲分区F1相邻接，见图(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。(2)回收分区与插入点的后一空闲分区F2相邻接，见图(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。(3)回收区同时与插入点的前、后两个分区邻接，见图(c)。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。(4)回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。内存回收时的情况4.3.4基于顺序搜索的动态分区分配算法有以下四种算法：•最佳适应法•最坏适应法•首次适应法•下次适应法（循环首次适应法）1)首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。2)下次适应法类似首次适应法每次分区时，总是从上次查找结束的地方开始，找到一个足够大的空白区分配。3)最佳适应算法•接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配•为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。•特点：用最小空间满足要求4)最坏适应算法•接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配，与最佳适应法相反，它在作业选择存储块时，总是寻找最大的空白区。•特点：当分割后空闲块仍为较大空块4.3.5基于索引搜索的动态分区算法1）快速适应算法（quickfit）2）伙伴系统（buddysystem）3）哈希算法1.快速适应算法2.伙伴系统固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0≤k≤m)个空闲分区链表。当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i－1n≤2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i＋1的空闲分区链表中寻找。若存在2i＋1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i＋1的空闲分区也不存在，则需要查找大小为2i＋2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i＋1的两个分区，一个用于分配，一个加入到大小为2i＋1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i＋3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为2i的空闲分区时，若事先已存在2i的空闲分区时，则应将其与伙伴分区合并为大小为2i＋1的空闲分区，若事先已存在2i＋1的空闲分区时，又应继续与其伙伴分区合并为大小为2i＋2的空闲分区，依此类推。在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种方法相比较，由于该算法在回收空闲分区时，需要对空闲分区进行合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能则远优于前面所述的分类搜索法，比顺序搜索法略差。3.哈希算法在上述的分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找到所需空间大小所对应的表项，从中得到对应的空闲分区链表表头指针，从而通过查找得到一个空闲分区。如果对空闲分区分类较细，则相应的空闲分区链表也较多，因此选择合适的空闲链表的开销也相应增加，且时间性能降低。哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得