内存分配

分区分配算法主要有FF分配算法、BF分配算法、WF分配算法、buddy分配算法

FF分配

FF分配:First Fit ，首次适应算法，

从空闲分区表的第一个表目起查找该表

，把最先能够满足要求的空闲区分配给作业。

若要满足FF算法，空闲分区表（空闲区链）中的

空闲分区地址要从小到大进行排序

。算法优先使用低地址部分空闲区。

优点：能够减少查找时间。

缺点：在低地址空间造成许多小的空闲区，在高地址空间保留了大的空闲区。

BF分配

BF分配：Best Fit，最佳适配算法，

从全部空闲区中找到能满足作业要求且大小最小的空闲分区，


若要满足BF算法，空闲分区表（空闲区链）中的空闲区要按照从小到大的顺序进行排序，且

从表头

开始查找第一个满足要求的自由分区分配。

优点：使碎片最小化。

缺点：该算法保留了大的空闲区，但造成较多的小空闲区。

WF分配

WF分配：Worst Fit，最差适配算法，

从全部空闲区中找到能满足作业要求且大小最大的空闲分区。


若要满足WF算法，需要将空闲区链中的空闲分区按从大到小进行排序，

从表头

开始查找第一个满足要求的自由分区分配。

优点：使空闲区表中的结点大小趋于均匀，适用于内存大小范围较窄的系统。减少了小的碎片产生。

缺点：保留了较小的空闲分区。

buddy分配

伙伴

这里给出伙伴的概念，满足以下三个条件的称为伙伴：

1）两个块大小相同；

2）两个块地址连续；

3）两个块必须是同一个大块中分离出来的；

解释

伙伴系统中可用内存块的大小为2k个字，L≤K≤U，其中2L表示分配的最小块的尺寸，2U表示分配的最大块的尺寸，通常2U是可供分配的整个内存的大小。

最初，可用于分配的整个空间被视为一个大小块为2U的块。

若请求的大小s满足2U-1 ≤ s ≤ 2U，则分配整个空间。否则，该块分成两个大小相等的伙伴，大小均为2U-1。

若有2U-2 < s ≤ 2U-1，则给该请求分配两个伙伴中的任何一个；否则，其中的一个伙伴又被分成两半，持续这一过程，直到产生大于等于s的最小块，并且分配给该请求。

在任何时候，伙伴系统中为所有大小为2i的“空洞”维护一个列表。空洞可通过对半分裂从i+1列表中移出，并且在i列表中产生两个大小为2i的伙伴。当i列表中的一对伙伴都变成未分配的块时，将他们从i列表中移出，合并为i+1列表中的一个块。