动态内存分配算法（详解加代码）
程序员文章站
2022-05-02 14:03:45
...
动态内存分配主要有四种算法：
(1) 首次适应算法：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
(2) 循环首次适应算法：首次适应算法每次要从头找，增加了查找的开销，也可能在低地
址上产生难以利用的小碎片。循环首次适应算法从上一次结束的位置开始查找。
(3) 最佳适应算法：为了保证当“大进程”到来时能有连续的大片空间，可以尽可能的多
留下大片空闲区，即，优先使用更小的空闲区。
(4) 最坏适应算法：为了解决最佳适应算法的问题——留下太多难以利用的小碎片。可以优先使用最大的连续空闲区。
各自的优缺点：
(1) 首次适应算法：综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序。
(2) 循环首次适应算法：不用每次都从低地址的小分区开始检索。算法开销小，但会使高地址的大分区也被用完。
(3) 最佳适应算法：会有更多的大分区被保留下来，更能满足大进程的需求。但会产生很多太小的、难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序。
(4) 最坏适应算法：可以减少难以利用的小碎片。但大分区容易被利用完，不利于大进程，算法开销大。
这里我们说说代码的构造：
你要有一个分区块的类，用来保存分区块的起始地址，大小，和状态
class Zone{ //分区结点信息类
private int size; //分区大小
private int head; //分区起始位置
private boolean isFree; //空闲状态
public Zone(int head, int size) {
this.head = head;
this.size = size;
this.isFree = true;
}
}
之外嵌套我们的主类：
private int size; //总内存大小
private LinkedList<Zone> zones; //保存内存分区
private int pointer; //上次分配的空闲区位置
代码逻辑图：1、我们先初始化内存的大小
2、进入主界面
- 输入作业
- 回收内存
- 显示分区
3、输入作业后，先输入大小，然后选择分配的算法
- 首次适应算法
- 循环首次算法
- 最佳适应算法
- 最坏适应算法
下面是源码阶段：
package Experiment;
import java.util.LinkedList;
import java.util.Scanner;
public class Test2{
private int size; //内存大小
private LinkedList<Zone> zones; //内存分区
private int pointer; //上次分配的空闲区位置
class Zone{ //分区结点信息类
private int size; //分区大小
private int head; //分区起始位置
private boolean isFree; //空闲状态
public Zone(int head, int size) {
this.head = head;
this.size = size;
this.isFree = true;
}
}
public Test2(){
this.size = 400;
this.pointer = 0;
this.zones = new LinkedList<>();
zones.add(new Zone(0, size));
}
public Test2(int size) {
this.size = size;
this.pointer = 0;
this.zones = new LinkedList<>();
zones.add(new Zone(0, size));
}
private void doAlloc(int size, int location, Zone tmp) {
//size 作业大小 location 内存位置 tmp可用空闲区
Zone newHome = new Zone(tmp.head + size, tmp.size - size);
//产生一个新空闲区;
zones.add(location + 1, newHome);//插入新节点
tmp.size = size;
tmp.isFree = false;
System.out.println("成功分配 " + size + "KB 内存!");
}
public void FirstFit(int size){
//将point赋值为零 从头开始找
for (pointer = 0; pointer < zones.size(); pointer++){
Zone tmp = zones.get(pointer);
//找到可用分区（空闲且大小足够）
if (tmp.isFree && (tmp.size > size)){
doAlloc(size, pointer, tmp);
return;
}
}
//遍历结束后未找到可用分区, 则内存分配失败
System.out.println("无可用内存空间!");
}
public void NextFit(int size){
//直接获得上次point位置，开始遍历分区链表
Zone tmp = zones.get(pointer);
if (tmp.isFree && (tmp.size > size)){
doAlloc(size, pointer, tmp);
return;//查看当前块是否符合要求
}
int len = zones.size();
int i = (pointer + 1) % len; //循环的过程，
for (; i != pointer; i = (i+1) % len){
tmp = zones.get(i);
//找到可用分区（空闲且大小足够）
if (tmp.isFree && (tmp.size > size)){
doAlloc(size, i, tmp);
return;
}
}
//遍历结束后未找到可用分区, 则内存分配失败
System.out.println("无可用内存空间!");
}
public void BestFit(int size){
//最佳适应算法
int flag = -1;//记录位置
int min = this.size;//初始化为内存长度，用来保存最小碎片大小;
for (pointer = 0; pointer < zones.size(); pointer++){//从头开始遍历;
Zone tmp = zones.get(pointer);
if (tmp.isFree && (tmp.size > size)){//找到合适条件的内存区
if (min > tmp.size - size){//如果产生的碎片小于上一个最小值，就重新标记最小值位置
min = tmp.size - size;
flag = pointer;//更新位置
}
}
}
if (flag == -1){//初始值，没找到
System.out.println("无可用内存空间!");
}else {
doAlloc(size, flag, zones.get(flag));
}
}
public void WorstFit(int size){//最坏适应算法
int flag = -1;
int max = 0;//类似于最佳算法
for (pointer = 0; pointer < zones.size(); pointer++){
Zone tmp = zones.get(pointer);
if (tmp.isFree && (tmp.size > size)){
if (max < tmp.size - size){
max = tmp.size - size;
flag = pointer;
}
}
}
if (flag == -1){
System.out.println("无可用内存空间!");
}else {
doAlloc(size, flag, zones.get(flag));
}
}
public void collection(int id){//id 指定要回收的分区号
if (id >= zones.size()){
System.out.println("无此分区编号!");
return;
}
Zone tmp = zones.get(id);//找到分区块
int size = tmp.size;//取出大小
if (tmp.isFree) {//判断状态
System.out.println("指定分区未被分配, 无需回收");
return;
}
//检查前面是否空闲，是则合并
if (id > 0 && zones.get(id - 1).isFree){
Zone fronKuer = zones.get(id - 1);
fronKuer.size += tmp.size;
zones.remove(id);
id--;
}
//检查后面是否空闲，是则合并
if (id < zones.size() - 1 && zones.get(id + 1).isFree){
Zone nextKuer = zones.get(id + 1);//取到下一个区块
tmp.size += nextKuer.size;
zones.remove(nextKuer);
}
zones.get(id).isFree = true;
System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
}
public void showZones(){//展示内存分区状况
System.out.println("***************************************");
System.out.println("*分区编号 分区始址 分区大小 空闲状态 *");
for (int i = 0; i < zones.size(); i++){
Zone tmp = zones.get(i);
System.out.println("* "+i + " "
+ tmp.head + " "
+ tmp.size + " "
+ tmp.isFree+" *");
}
System.out.println("****************************************");
}
}
这是我们算法的类，下面是调用的类
package Experiment;
import java.util.Scanner;
public class Main {
public static Test2 user; //声明一个用户;
public static void Init(){ //初始化内存大小
System.out.println("请输入内存大小(如果输入0，则按默认400分配)");
Scanner scanner=new Scanner(System.in);
int choose=scanner.nextInt();
if(choose==0){
user=new Test2();
}else {
user=new Test2(choose);
}
}
public static void mainMenu(){
System.out.println("***********************");
System.out.println("* 1.输入作业 *");
System.out.println("* 2.回收内存块 *");
System.out.println("* 3.展示分区情况 *");
System.out.println("* 4.退出系统 *");
System.out.println("***********************");
System.out.println("请输入你要进行的操作:");
}
public static void algorithmMenu(int size){
System.out.println("请选择分配算法:");
System.out.println("1.首次适应算法");
System.out.println("2.循环首次算法");
System.out.println("3.最佳适应算法");
System.out.println("4.最坏适应算法");
Scanner in = new Scanner(System.in);
int choose = in.nextInt();
switch (choose){
case 1:
user.FirstFit(size);break;
case 2:
user.NextFit(size);break;
case 3:
user.BestFit(size);break;
case 4:
user.WorstFit(size);break;
default:
System.out.println("请重新选择!");
}
}
public static void main(String[] args) {
Init(); //初始化内存条大小
Scanner sc=new Scanner(System.in);
while(true){
mainMenu(); //主菜单
int choice=sc.nextInt();
if(choice == 4){
return;
}else if(choice == 1){
System.out.println("请输入你要插入的内存块大小");
int length=sc.nextInt();
algorithmMenu(length);
}else if(choice==2){
System.out.println("请输入你要回收的分区号码");
int ID=sc.nextInt();
user.collection(ID);
}else if(choice == 3){
user.showZones();
}else{
System.out.println("输入错误，请检查");
}
}
}
}
注释写得很清楚，有什么不懂可以私信。
上一篇： 【软工】软件测试