首次适应算法[first fit]
每次都从低地址开始查找,找到对歌能满足大小的空闲分区
空闲分区以地址递增的次序排列,每次分配内存时顺序查找空闲分区链或表,找到大小能满足要求的第一个空闲分区
最佳适应算法[best fit]
由于动态分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域,因此为了保证大进程到来的时候可以有连续的大片空间,我们尽可能留下大片空闲区,优先使用小空闲区
按照容量递增次序连接,每次分配内存时,顺序查找,找到大小能满足要求的第一个空闲分区 (分配后可能需要让链或者表重新排列)
每次都选最小的分区进行分配,会留下越来越多的,很小的,难以利用的内存卡,因此这个方法会有很多外部碎片
最坏适应算法[worst fit]
又叫最大适应算法
与上方的方法相反,优先使用最大的连续空闲区,这样分配后剩余的空间不会太小,更方便使用
按照内存递减次序连接,每次分配内存时,顺序查找,找到大小能满足要求的第一个空闲分区 (分配后也可能需要让链或者表重新排列)
缺点:每次都选用最大的分区进行分配,虽然可以让分配后留下的空闲区更大,更可用,但是这种方式会导致较大的连续空闲区被迅速用完,如果之后有大进程到达,就没有内存分区可用了
邻近适应算法[next fit]
空闲分区以地址递增的顺序排列,排列成一个循环链表,每次分配内存都从上次查找结束的位置开始查找空闲分区链,找到大小能满足的第一个空闲区域(不需要重新排列,算法开销小)
邻近适应算法,会导致无论低地址或者高地址部分的空闲分区,都有相同的概率被使用,导致了高地址部分的大分区可能会被使用,导致最后没有大分区可用了
以上四种算法中,首次适应算法的效果反而是最好的
