主存动态连续分配与回收算法(FF,BF,WF)

①首次适应算法(First Fit)
FF算法要求空闲分区链以地址递增的次序链接。
— 在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;
— 然后再按照作业的大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中。
— 若从链首直至链尾都不能找到一个能满足要求的分区,则此次内存分配失败,返回。

首次适应算法倾向于优先利用内存中低址部分的空闲分区,从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分,会留下许多难以利用的、很小的空闲分区,而每次查找又都是从低址部分开始,这无疑会增加查找可用空闲分区时的开销。

流程图:


代码:

 

下面两个算法类似,写在一起

②最佳适应算法(Best Fit)
所谓“最佳”是指每次为作业分配内存时,总是把能满足要求、又是最小的空闲分区分配给作业,避免“大材小用”。为了加速寻找,该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样,第一次找到的能满足要求的空闲区,必然是最佳的。
孤立地看,最佳适应算法似乎是最佳的,然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的,这样,在存储器中会留下许多难以利用的小空闲区。

 

③最坏适应算法(Worst Fit)
最坏适应分配算法要扫描整个空闲分区表或链表,总是挑选一个最大的空闲区分割给作业使用,其优点是可使剩下的空闲区不至于太小,产生碎片的几率最小,对中、小作业有利,同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链,查找时只要看第一个分区能否满足作业要求。
但是该算法的缺点也是明显的,它会使存储器中缺乏大的空闲分区。

FF与WF代码:

网站所有原创代码采用Apache 2.0授权 
网站文章采用知识共享许可协议BY-NC-SA4.0授权

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注