搜索
最佳适应算法(BF)算法要求：空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍按容量大小递增的次序保留在空闲分区表/链中。例：系统中的空闲分区表如下，现有三个作业申请分配内存空间100KB、30KB及7KB。给出按最佳适应算法的内存分配情况及分配后空闲分区表。区号大小起址18k72k232k20k3120k100k4331k320k分配前的空闲分区表0k20k52k80k651k内存空闲分区图72k100k220K320K2134解：按最佳适应算法，分配前的空闲分区表如上表。申请作业100k，分配3号分区，剩下分区为20k,起始地址200K；申请作业30k，分配2号分区，剩下分区为2k，起始地址50K；申请作业7k，分配1号分区，剩下分区为1k，起始地址79K；其内存分配图及分配后空闲分区表如下区号大小起址18k72k320k200k232k20k4331k320k作业100K分配后的空闲分区表区号大小起址22k50k18k72k320k200k4331k320k作业30K分配后的空闲分区表区号大小起址11k79k22k50k320k200k4331k320k作业7K分配后的空闲分区表(2)该算法分配后的空闲分区表区号大小起址11k79k22k50k320k200k4331k320k(1)内存分配示意图0k20k52k80k651k50k72k79k100k200k220K320K4132算法特点若存在与作业大小一致的空闲分区，则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，从而保留了大的空闲分区，但空闲区一般不可能正好和它申请的内存空间大小一样，因而将其分割成两部分时，往往使剩下的空闲区非常小，从而在存储器中留下许多难以利用的小空闲区（外碎片或外零头）。最坏适应算法(WF)算法要求空闲分区表/链按容量大小递减的次序排列。在进行内存分配时，从空闲分区表/链首开始顺序查找，找到的第一个能满足作业要求的空闲分区，一定是个最大的空闲区。这样可保证每次分割后的剩下的空闲分区不至于太小（还可被分配使用，以减少“外碎片”），仍把它按从大到小的次序保留在空闲分区表/链中。区号大小起址1331k320k2120k100k332k20k48k72k空闲分区表例：系统中的空闲分区表如下，现有三个作业申请分配内存空间100KB、30KB及7KB。给出按最坏适应算法的内存分配情况及分配后空闲分区表。0k20k52k80k651k内存空闲分区图72k100k220K320K3421区号大小起址1231k420k2120k100k332k20k48k72k作业100K分配后的空闲分区表区号大小起址1201k450k2120k100k332k20k48k72k作业30K分配后的空闲分区表区号大小起址1194k457k2120k100k332k20k48k72k作业7K分配后的空闲分区表解：按最坏适应算法，分配前的空闲分区表如上表。申请作业100k，分配1号分区，剩下分区为231k,起始地址420K；申请作业30k，分配1号分区，剩下分区为201k，起始地址450K；申请作业7k，分配1号分区，剩下分区为194k，起始地址457K；其内存分配图及分配后空闲分区表如下区号大小起址1194k457k2120k100k332k20k48k72k(2)该算法分配后的空闲分区表(1)内存分配图0k20k52k80k457k651k72k100k220K320K420k450k3421算法特点总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。快速适应算法(QF)算法要求又叫分类搜索法，将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区（链）表。系统中存在多个空闲分区（链）表，同时在内存中设立一张管理索引表，每个表项对应了一种空闲分区类型，并指向该类型的空闲分区表的表头。空闲分区的分类是根据进程常用的空间大小进行划分的。快速适应算法(QF)优点：查找效率高，找到该类后，取下第一块分配即可；不会产生碎片；缺点：分区归还给系统时算法复杂，系统开销大；内存空间存在一定的浪费。3、分区分配操作_分配内存和回收内存（1）分配内存系统利用某种分配算法，从空闲分区表/链中找到所需大小的分区。分区的切割：设请求的分区大小为u.size，空闲分区的大小为m.size,若m.size-u.sizesize（size是事先规定的不再切割的剩余分区的大小），说明多余部分大小，可不再切割，将整个分区分配给请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中，然后，将分配区的首址返回给调用者。分配流程图如下从头开始查表从该分区中划出u.size大小的分区检索完否？返回m.sizeu.sizem.size-u.sizesize将该分区分配给请求者，修改有关数据结构返回将该分区从分区表/链中移出继续检索下一个表项YYYNNN内存分配流程图（2）回收内存当作业执行结束时，释放所占有的内存空间，OS应回收已使用完毕的内存分区。系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。回收分区与已有空闲分区的相邻情况有以下四种：（2）回收内存…回收分区R空闲分区F1…(a)内存回收情况1)回收分区R上面邻接一个空闲分区F1，合并后首地址为空闲分区F1的首地址，大小为F1和R二者大小之和。这种情况下，回收后空闲分区表中表项数不变。（2）回收内存…空闲分区F2回收分区R…(b)内存回收情况2)回收分区R下面邻接一个空闲分区F2，合并后首地址为回收分区R的首地址，大小为R和F2二者大小之和。这种情况下，回收后空闲分区表中表项数不变。（2）回收内存…空闲分区F2回收分区R空闲分区F1…(c)内存回收情况3)回收分区R上下邻接空闲分区F1和F2，合并后首地址为上空闲分区F1的首地址，大小为F1、R和F2三者大小之和。这种情况下，回收后空闲分区表中表项数不但没有增加，反而减少一项。（2）回收内存内存回收情况…回收分区R…(d)4)回收分区R不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区首地址、大小等信息。这种情况下，回收后空闲分区表中表项数增加一项。四、伙伴系统1、固定分区：限制了活动进程的数目，内存利用率低动态分区：算法复杂，系统开销大折中方案：伙伴系统2、伙伴系统规定：已分配/空闲分区的大小都是2的k次幂（l≤k≤m）3、分配和回收方法：P1264、分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间5、在当前OS中，普遍采用虚拟内存机制在多处理机系统中，伙伴系统得到大量的应用五、哈希算法（1）1、分类搜索算法（快速适应算法）和伙伴系统的共同特点：将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。为进程分配内存空间时，需在一张管理索引表中查找所需空间大小所对应的表项，通过指针找到一个空闲分区。五、哈希算法（2）2、哈希算法利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，每一个表项记录了一个对应的空闲分区链链表表头指针。3、进行分配时，根据所需空闲分区大小，通过哈希函数计算，得到在哈希表中的位置，找到相应的空闲分区链表，实现最佳分配策略。六、可重定位分区分配方式1、碎片问题在分区存储管理方式中，必须把作业装入到一片连续的内存空间。如果系统中有若干个小的分区，其总容量大于要装入的作业，但由于它们不相邻接，也将导致作业不能装入内存。例：如图所示系统中有四个小空闲分区，不相邻，但总容量为90KB，如果现有一作业要求分配40KB的内存空间，由于系统中所有空闲分区的容量均小于40KB，故此作业无法装入内存。操作系统作业A20KB作业B30KB作业C15KB作业D25KB系统中的碎片（1）os用户程序p4p1p20k20k56k65k125k135k内部碎片内部碎片内部碎片内部碎片内部碎片：指分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。这种内存中无法被利用的存储空间称为“零头”或“碎片”。根据碎片出现的情况分为以下两种：系统中的碎片（2）25KB作业D15KB作业C30KB作业B20KB作业A操作系统外部碎片外部碎片外部碎片外部碎片外部碎片外部碎片：指系统中无法利用的小的空闲分区。如动态分区中存在的碎片。2、碎片问题的解决方法对系统中存在碎片，目前主要有两种技术(之一)：拼接或紧凑或紧缩技术将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换即称为重定位），使本来分散的多个小空闲分区连成一个大的空闲区。如图所示。这种通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为拼接或紧凑或紧缩。拼接时机：分区回收时；当找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。作业D作业C作业B20KB30KB90KB15KB25KB作业A操作系统动态重定位分区分配算法流程图有大于x的空闲分区吗？返回分区号空闲分区总和大于x吗？拼接并修改相应数据结构返回修改有关数据结构按动态分区分配方式进行分配YYNN无法分配，返回请求分配一个大小为x的分区动态重定位分区分配技术在动态分区分配算法中增加拼接功能，在找不到足够大的空闲分区来满足作业要求，而系统中总空闲分区容量可以满足作业要求时，进行拼接。可重定位分区分配方式主要特点可以充分利用存储区中的“零头/碎片”，提高主存的利用率。但若“零头/碎片”太多，则拼接频率过高会使系统开销加大。七、分区的存储保护（1）存储保护是为了防止一个作业有意或无意地破坏操作系统或其它作业，常用的存储保护方法有：1、界限寄存器方法上下界寄存器方法：用这两个寄存器分别存放作业的起始地址和结束地址。在作业运行过程中，将每一个访问内存的地址都同这两个寄存器的内容比较，如超出这个范围便产生保护性中断。七、分区的存储保护（2）存储保护是为了防止一个作业有意或无意地破坏操作系统或其它作业，常用的存储保护方法有：1、界限寄存器方法基址、限长寄存器方法：用这两个寄存器分别存放作业的起始地址和作业的地址空间长度。当作业执行时，将每一访问内存的相对地址和限长寄存器比较，如果超过了限长寄存器的值，则发出越界中断信号，并停止作业的运行。七、分区的存储保护（3）2、存储保护键方法给每个存储块（大小相同，一个分区为存储块的整数倍）分配一个单独的保护键，它相当于一把锁。进入系统的每个作业也赋予一个保护键，它相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，停止作业运行。八、覆盖与交换覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法。覆盖技术主要用在早期的OS中。交换技术则主要用在现代OS中，解决在小的内存空间运行大作业的问题，是“扩充”内存容量和提高内存利用率的有效措施。1、覆盖技术覆盖技术主要用在早期的OS中（内存64KB），可用的存储空间受限，某些大作业不能一次全部装入内存，产生了大作业与小内存的矛盾。例：大作业：108KB内存：64KB1、覆盖技术覆盖：把一个程序划分为一系列功能相对独立的程序段（称为覆盖），让执行时并不要求同时装入内存的覆盖组成一组（称为覆盖段），共享主存的同一个区域，从而解决在小的存储空间中运行大作业的问题。这种内存扩充技术就是覆盖。主程序A20KB子程序B15KB子程