4.3　连续分配存储管理方式

本节概览：先建立「连续分配存储管理方式」的框架，再依次展开下列小节。

1. 单一连续分配
2. 固定分区分配
3. 动态分区分配
4. 基于顺序搜索的动态分区分配算法
5. 基于索引搜索的动态分区分配算法
6. 动态可重定位分区分配

单道环境下内存分系统区与用户区：系统区供OS使用，位于低址部分；用户区仅装一道用户程序，整个用户空间由该程序独占。

为便于分配，将分区按大小排队并建立分区使用表，表项含起始地址、大小及状态。

固定分区将内存用户空间划分为若干固定大小分区，有两种方法。

1. 分区大小相等：缺乏灵活性，适合控制多个相同对象的场合
2. 分区大小不等：增加分配灵活性，划分为若干大小不等分区

连续分配将每个用户程序装入一片连续内存空间，是早期OS常用的管理方式。

1. 单一连续分配
2. 固定分区分配
3. 基于顺序搜索的动态分区分配算法
4. 基于索引搜索的动态分区分配算法
5. 动态可重定位分区分配

动态分区分配算法

为把一个新作业装入内存，需要按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。

② 空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。

分区分配操作

系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一。

1. 回收区与插入点的前一个空闲分区F1相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小
2. 回收分区与插入点的后一空闲分区F2相邻接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和

回收内存

1. 回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和
2. 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。图4-10示出了内存回收时的流程

结合插图「图4-10 内存回收流程」理解本节要点。

BF每次把能满足要求且最小的空闲分区分配给作业，避免大材小用。

为加速查找，要求空闲分区按容量从小到大排成空闲分区链。

FF要求空闲分区链按地址递增链接。

分配时从链首顺序查找，找到首个满足大小的空闲分区，从中划出作业所需空间，余下留在链中。

若遍历到链尾仍无满足分区，则分配失败。

NF每次不再从链首查找，而是从上次找到分区的下一个空闲分区开始查找。

找到满足要求的分区即划出空间分配，避免低址留下过多小空闲分区，减少查找开销。

WF与BF相反：扫描时总是挑选最大的空闲分区，从中分割一部分给作业。

该策略使存储器中缺乏大的空闲分区，故称最坏适应算法。

伙伴系统规定分区大小均为2的k次幂(k为整数，1≤k≤m)，2^m为整个可分配内存。

系统运行时整个内存是一个2^m空闲分区；相同大小的空闲分区单独设双向链表，形成k个链表。

哈希算法利用哈希快速查找的优点，以空闲分区大小为关键字建立哈希表。

每项记录对应空闲分区链表表头指针；分配时按所需大小经哈希函数定位链表，实现最佳分配。

快速适应又称分类搜索法：按容量对空闲分区分类，每类设单独空闲分区链表。

内存中设管理索引表，每项对应一类空闲分区并记录链表表头指针。

连续分配要求程序装入一片连续内存；运行一段时间后内存被切成小分区，缺乏大空闲空间。

即使小分区容量总和足够，因不相邻接也无法装入程序。紧凑后程序位置变化，须修改地址否则无法执行。

动态重定位

为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

动态重定位分区分配算法

动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。 当该算法不能找到一个足够大的空闲分区以满足用户需求时，如果所有的小的空闲分区的容量总和大于用户的要求，这时便须对内存进行“紧凑”，将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求，则返回分配失败信息。