快速适应(QF)算法
空闲分区按容量大小分类,每类设立空闲分区链表,并设管理索引表
哈希算法
宜用管理索引表查找所需空间对应的表项,得到对应空闲分区链表的表头指针,得到一个空闲分区
利用空间表中的分布规律,构造一张以空闲分区大小为关键字的哈希表,每个表项记录一个对应的空闲分区链表表头指针
伙伴系统(BS)
固定分区和动态分区的不足之处
固定分区:限制活动进程的数目,进程大小与空闲分区大小不匹配时,内存空间利用率很低
动态分区:算法复杂,回收空闲分区时需进行分区合并等,系统开销较大
伙伴系统方式是对以上两种内存方式的一种折衷方案
分区划分:无论已分配分区或空闲分区,大小均为2的k次幂,k为整数,l ≤ k ≤ m,2^m^是最大分区的大小。
最坏的情况下,可能需要对2^k的空闲分区进行k次分割才能得到所需分区
时间性能:比前面所述的分类搜索算法差,但比顺序搜索算法好;<br>
空间性能:远优于分类搜索法,比顺序搜索法略差