import java.util.LinkedList;
import java.util.Scanner;
/**
* @author caoxingxing
* @version 11.0
* @className all05
* @description TODO
* @since 2020/12/2 13:50
*/
public class all05 {
public static void main(String[] args) {
pcb pcb = null;
Scanner in = new Scanner(System.in);
System.out.print("请输入初始内存大小（KB）:");
int size = in.nextInt();
pcb = new pcb(size);
pcb.show();
while (true){
System.out.println("请输入您的选择:");
System.out.println("1.申请空间");
System.out.println("2.回收空间");
System.out.println("3.显示分区情况");
System.out.println("4.退出");
size = in.nextInt();
switch (size) {
case 1:
System.out.print("请输入需要申请的空间大小（KB）:");
size = in.nextInt();
pcb.neicunfenpei(size);
break;
case 2:
System.out.print("请输入需要回收的分区号:");
size = in.nextInt();
pcb.collection(size);
break;
case 3:
pcb.show();
break;
case 4:
System.out.println("老板走好！欢迎下次使用！");
System.exit(0);
default:
System.out.println("请重新选择!");
}
}
}
}
class pcb {
//内存大小
private int size;
//最小剩余分区大小
private static final int MIN_SIZE = 5;
//内存分区
private LinkedList<Jiedian> Jiedians;
//上次分配的空闲区位置
private int pointer;
//分区节点类
class Jiedian {
//分区大小
private int size;
//分区始址
private int head;
//空闲状态
private boolean isFree;
public Jiedian(int head, int size) {
this.head = head;
this.size = size;
this.isFree = true;
}
}
public pcb(int size) {
this.size = size;
this.pointer = 0;
this.Jiedians = new LinkedList<>();
Jiedians.add(new Jiedian(0, size));
}
public void neicunfenpei(int size) {
System.out.println("1.最先适应法 2.最佳适应法 3.最坏适应法");
System.out.print("请选择分配算法:");
Scanner in = new Scanner(System.in);
int algorithm = in.nextInt();
switch (algorithm) {
case 1:
fristFit(size);
break;
case 2:
bestFit(size);
break;
case 3:
worstFit(size);
break;
default:
System.out.println("输入错误！程序退出！");
System.exit(0);
}
}
// 最先适应算法
private void fristFit(int size) {
//遍历分区链表
for (pointer = 0; pointer < Jiedians.size(); pointer++) {
Jiedian tmp = Jiedians.get(pointer);
//找到可用分区（空闲且大小足够）
if (tmp.isFree && (tmp.size > size)) {
doneicunfenpei(size, pointer, tmp);
return;
}
}
//遍历结束后未找到可用分区, 则内存分配失败
System.out.println("分配失败！无可用内存空间!");
}
//最佳适应算法
private void bestFit(int size) {
int flag = -1;
int min = this.size;
//先遍历链表
for (pointer = 0; pointer < Jiedians.size(); pointer++) {
Jiedian tmp = Jiedians.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 {
doneicunfenpei(size, flag, Jiedians.get(flag));
}
}
//最坏适应算法
private void worstFit(int size) {
int flag = -1;
int max = 0;
for (pointer = 0; pointer < Jiedians.size(); pointer++) {
Jiedian tmp = Jiedians.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 {
doneicunfenpei(size, flag, Jiedians.get(flag));
}
}
private void doneicunfenpei(int size, int location, Jiedian tmp) {
//如果分割后分区剩余大小过小（MIN_SIZE）则将分区全部分配，否则分割为两个分区
if (tmp.size - size <= MIN_SIZE) {
tmp.isFree = false;
} else {
Jiedian split = new Jiedian(tmp.head + size, tmp.size - size);
Jiedians.add(location + 1, split);
tmp.size = size;
tmp.isFree = false;
}
System.out.println("成功分配 " + size + "KB 内存!");
}
// 内存回收
public void collection(int id) {
if (id >= Jiedians.size()) {
System.out.println("无此分区编号!");
return;
}
Jiedian tmp = Jiedians.get(id);
int size = tmp.size;
if (tmp.isFree) {
System.out.println("指定分区未被分配, 无需回收");
return;
}
//如果回收分区不是尾分区且后一个分区为空闲, 则与后一个分区合并
if (id < Jiedians.size() - 1 && Jiedians.get(id + 1).isFree) {
Jiedian next = Jiedians.get(id + 1);
tmp.size += next.size;
Jiedians.remove(next);
}
//如果回收分区不是首分区且前一个分区为空闲, 则与前一个分区合并
if (id > 0 && Jiedians.get(id - 1).isFree) {
Jiedian previous = Jiedians.get(id - 1);
previous.size += tmp.size;
Jiedians.remove(id);
id--;
}
Jiedians.get(id).isFree = true;
System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
}
//
public void show() {
System.out.println("------------------------------------");
System.out.println("区号\t\t分区始址\t\t分区大小\t\t状态\t");
System.out.println("------------------------------------");
for (int i = 0; i < Jiedians.size(); i++) {
Jiedian tmp = Jiedians.get(i);
System.out.println(i + "\t\t" + tmp.head + "\t\t\t" +
tmp.size + " \t\t" + tmp.isFree);
}
System.out.println("------------------------------------");
}
}
