动态分区分配算法

一、首次适应算法(First Fit)

1.思想

每次都从低地址开始查找，找到第一个能满足大小的空闲分区

2.实现

以递增次序排列空闲分区，按顺序查找空闲分区链/空闲分区表，分配第一个满足要求的空闲分区

3.缺点

会导致低地址部分出现很多很小的空闲分区，使得每次分配查找开销更大。

二、最佳适应算法(Best Fit)

1.思想

为保证大进程能有连续的大片空间，多留大片空闲区，优先使用更小的空闲区。

2.实现

空闲分区按容量递增次序链接，按顺序查找空闲分区链/空闲分区表，分配第一个满足要求的空闲分区

3.缺点

会产生很多很小的外部碎片，需要更新排列顺序

三、最坏适应算法(Worst Fit)

1.思想

为减少外部碎片，多留大片空闲区，优先使用更大的空闲区。

2.实现

空闲分区按容量递减次序链接，按顺序查找空闲分区链/空闲分区表，分配第一个满足要求的空闲分区

3.缺点

会导致大进程到达时无内存分区可用，需要更新排列顺序

四、邻近适应算法(Next Fit)

1.思想

为减少首次适应算法的查找开销，每次查找从上次查找结束位置开始

2.实现

以递增次序排列空闲分区，从上次查找结束位置开始查找空闲分区链/空闲分区表，分配第一个满足要求的空闲分区

3.缺点

会更多占用高地址部分的大分区，导致无大分区可用