模拟实现内存动态分区分配与回收

一、目的

四个动态分区分配算法：最佳适应算法，循环首次适应算法，最坏适应算法，首次适应算法；四种回收情况：上邻不下邻，上不邻下邻，上下都邻，上下都不邻；要求有录入界面，动态初始化内存使用情况，动态录入进程对内存的分配与回收请求；有算法选择界面，动态选择分区分配算法；有输出界面，能够查看内存分配与回收结果。

二、原理

首先创建memory类，类中包含四个内存分配回收算法：

首次适应算法private void FristFit(int size) 从链首开始顺序查找循环首次适应算法private void NextFit(int size) 从上次找到的空闲分区的下一个空闲分区开始查找最佳适应算法private void BestFit(int size) 总是把满足要求的，最小的空闲分区分配给作业最坏适应算法private void WorstFit(int size) 总是把满足要求的，最大的空闲分区分配给作业

若通过以上四种算法 找到可用的空闲分区并且分区的大小足够

通过Distribute(size, location, temp)函数执行分配。通过public void showmpartition()函数展示内存分区的状况。通过public void allocation(int size)进行内存的动态分配函，通过public void collection(int id)进行内存的回收 。

然后创建main类，里面主要时main函数，通过输入不同的选择调用不同的函数。

三、主要过程及步骤

1.主要模块及数据流程图

（1）主要函数：

public void allocation(int size)：内存分配public void showmpartition()：展示内存分区状况public void collection(int id)：内存回收,id 指定要回收的分区号private void Distribute(int size, int location, Partition

temp)：执行分配函数

（2）核心算法及解析：

1）首次适应算法：

首次适应算法进行内存分配时，从链首开始顺序查找。首先找到可用的空闲分区并且分区的大小足够，通过Distribute(size, location, temp)函数执行分配，若遍历完整个链表任然没有找到可用空闲分区则内存分配失败，输出提示语句。

//首次适应算法//size 指定需要分配的大小private void FristFit(int size){//遍历分区链表for (location = 0; location < mpartition.size(); location++){//每次从链首开始查找Partition temp =mpartition.get(location);if (temp.Free && (temp.size > size)){//找到可用空闲分区且大小足够Distribute(size, location, temp);return;}}//遍历结束后未找到可用分区, 则内存分配失败System.out.println("无可用内存空间!");}

2）循环首次适应算法：

循环首次适应算法进行内存分配时，从上次找到的空闲分区的下一个空闲分区开始查找。首先，从上次分配的空闲区位置开始遍历分区链表，如果，找到可用的空闲分区并且分区的大小足够，通过Distribute(size, location, temp)函数执行分配。若遍历完整个链表任然没有找到可用空闲分区则内存分配失败，输出提示语句。

//循环首次适应算法// size 指定需要分配的大小private void NextFit(int size){Partition temp = mpartition.get(location);//从上次分配的空闲区位置开始遍历分区链表if (temp.Free && (temp.size > size)){Distribute(size, location, temp);return;}int length= mpartition.size();int i = (location + 1) % length;for (; i != location; i = (i+1) % length){temp = mpartition.get(i);//找到可用分区（空闲且大小足够）if (temp.Free && (temp.size > size)){Distribute(size, i, temp);return;}}//遍历结束后未找到可用分区, 则内存分配失败System.out.println("无可用内存空间!");}

3）最佳适应算法：

最佳适应算法为作业分配内存时，总是把满足要求的，最小的空闲分区分配给作业。首先遍历分区链表，如果，找到可用的空闲分区并且分区的大小足够，再判断min > temp.size – size是否成立，最后根据flag的值判断有无可用内存空间，若有则通过Distribute(size, location, temp)函数执行分配。

// 最佳适应算法//size 指定需要分配的大小private void BestFit(int size){int flag = -1;int min = this.size;for (location = 0; location < mpartition.size(); location++){Partition temp = mpartition.get(location);if (temp.Free && (temp.size > size)){if (min > temp.size - size){min = temp.size - size;flag = location;}}}if (flag == -1){System.out.println("无可用内存空间!");}else {Distribute(size, flag, mpartition.get(flag));}}

4）最坏适应算法：

最坏适应算法为作业分配内存时，总是把满足要求的，最大的空闲分区分配给作业。首先遍历分区链表，如果，找到可用的空闲分区并且分区的大小足够，再判断max < temp.size – size是否成立，最后根据flag的值判断有无可用内存空间，若有则通过Distribute(size, location, temp)函数执行分配。

//最坏适应算法//size 指定需要分配的大小private void WorstFit(int size){int flag = -1;int max = 0;for (location= 0; location < mpartition.size(); location++){Partition temp = mpartition.get(location);if (temp.Free && (temp.size > size)){if (max < temp.size - size){max = temp.size - size;flag = location;}}}if (flag == -1){System.out.println("无可用内存空间!");}else {Distribute(size, flag, mpartition.get(flag));}

4）四种回收情况：

此处将上邻下不邻，上不邻下邻，上下都不邻和上下都邻四种回收情况合并为两种，即：如果回收分区不是尾分区且后一个分区为空闲, 则与后一个分区合并（上不邻下邻或者上下都邻），如果回收分区不是首分区且前一个分区为空闲, 则与前一个分区合并（上邻下不邻或者上下都邻）。

//内存回收,id 指定要回收的分区号public void collection(int id){if (id >= mpartition.size()){System.out.println("没有此分区号!");return;}Partition temp = mpartition.get(id);int size = temp.size;if (temp.Free) {System.out.println("分区未被分配, 无需回收");return;}//如果回收分区不是尾分区且后一个分区为空闲, 则与后一个分区合并（上不邻下邻或者上下都邻）if (id < mpartition.size() - 1 && mpartition.get(id + 1).Free){Partition next = mpartition.get(id + 1);temp.size += next.size;mpartition.remove(next);}//如果回收分区不是首分区且前一个分区为空闲, 则与前一个分区合并（上邻下不邻或者上下都邻）if (id > 0 && mpartition.get(id - 1).Free){Partition previous = mpartition.get(id - 1);previous.size += temp.size;mpartition.remove(id);id--;}mpartition.get(id).Free = true;System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");}

（3）数据流程图：

2. 运行结果分析

(1)内存初始状态：

（2）动态分区分配：

对四种算法均执行如下操作序列：申请300K，申请100K，释放300K，申请150K，申请50K，申请90K。在选择算法指令中输入相对应的指令。

（3）结果显示及分析：

1）首次适应算法：

首先申请300K，再申请100K，再释放300K，此时第一个空闲分区起始地址为0，大小为300K。第二个空闲分区起始地址为400，大小为112K。由于首次适应算法进行内存分配时，从链首开始，所以申请150K，50K，90K都是在已经释放的300K空闲区中分配。此时，第一个空闲分区起始地址为290，大小为10K，第二个空闲分区起始地址为400，大小为112K。

2）循环首次适应算法：

首先申请300K，再申请100K，再释放300K，此时第一个空闲分区起始地址为0，大小为300K。第二个空闲分区起始地址为400，大小为112K。由于循环首次适应算法进行内存分配时，从上次找到的空闲分区的下一个空闲分区开始查找，所以当申请150K时下一个空闲分区的始址为150，大小为150K；再申请50K，它的下一个空闲分区始址为200，大小为100K；再申请90K，它的下一个空闲分区的始址为290，大小为10K。综上所述，第一个空闲分区的始址为290，大小为10K，第二个空闲分区的始址为400，大小为112K。

3）最佳适应算法

首先申请300K，再申请100K，再释放300K，此时第一个空闲分区起始地址为0，大小为300K。第二个空闲分区起始地址为400，大小为112K。由于最佳适应算法在分配内存时，总是把满足要求的最小的空闲分区分配给作业。所以当申请150K时，将满足要求的300K分配给它，此时第一个空闲分区的起址为150，大小为150K，第二个空闲分区不变；申请50K时，满足要求的且最小的为第二个空闲分区，分配完后第二空闲分区的起址为450，大小为62K；申请90K，将第一个空闲分区分配给它，最终可得，第一个空闲分区的始址为240，大小为60K，第二个空闲分区的始址为450，大小为62K。

4）最坏适应算法：

首先申请300K，再申请100K，再释放300K，此时第一个空闲分区起始地址为0，大小为300K。第二个空闲分区起始地址为400，大小为112K。由于最坏适应算法在分配内存时，总是把满足要求的最大的空闲分区分配给作业。所以当申请150K时，将满足要求的300K分配给它，此时第一个空闲分区的起址为150，大小为150K，第二个空闲分区不变；申请50K时，第一个空闲分区大小为150K，第二空闲分区大小为112K，所以将第一分区分配给它，分配完后第一空闲分区的起址为200，大小为100K；申请90K，由于第一空闲分区为100K，第二个空闲分区为112K，所以将第二个空闲分区分配给它，最终可得，第一个空闲分区的始址为200，大小为100K，第二个空闲分区的始址为490，大小为22K。

得出结论：若随后又要申请80K，首次适应算法可以分配成功，而最佳适应算法则没有足够大的空间分配。这说明首次适应算法尽可能地使用了低地址部分的空闲区域，留下了高地址部分的大空闲区，更有可能满足进程的申请。