动态分区算法（FF,NF,BF,WF四种）
package experiment;
import java.util.Scanner;
class FreePartition
{
int number;//分区编号
int total;//分区总容量
int left;//分区剩余容量
FreePartition(){}
FreePartition(int number,int total)
{
this.number=number;
this.total=total;
this.left=total;
}
public int getNumber() {
return number;
}
public int getTotal() {
return total;
}
public int getLeft() {
return left;
}
public void setNumber(int number) {
this.number = number;
}
public void setTotal(int total) {
this.total = total;
}
public void setLeft(int left) {
this.left = left;//使用总容量去初始化分区剩余容量
}
}
class Process
{
String name;//进程名称
int need;//进程所需分区大小
boolean done;//进程是否完成
int where;//进程位于哪个分区
Process(){}
Process(String name,int need)
{
this.name=name;
this.need=need;
}
public String getName() {
return name;
}
public int getNeed() {
return need;
}
public boolean isDone() {
return done;
}
public int getWhere() {
return where;
}
public void setName(String name) {
this.name = name;
}
public void setNeed(int need) {
this.need = need;
}
public void setDone(boolean done) {
this.done = done;
}
public void setWhere(int where) {
this.where = where;
}
public void Print_ProcessAndFreePartion(Process [] process,FreePartition [] free)
{
for(int i=0;i<process.length;i++)
{
System.out.println("进程"+process[i].getName()+" "+"需要的空间大小是"+process[i].getNeed()+" "+"装入"+process[i].getWhere()+"号空闲区");
}
for(int i=0;i<free.length;i++)
{
System.out.println("分区编号为"+free[i].getNumber()+" "+"分区总容量为"+free[i].getTotal()+" "+"分区剩余容量为"+free[i].getLeft());
}
}
public void FF(Process [] process,FreePartition [] free)
{
//首次适应算法
//测试数据为5个空闲分区，5个进程
//空闲分区：1 12，2 26 ，3 32 ，4 40，5 10
//进程：A 7,B 9,C 12,D 5,E 28
//预期结果：1-2-2-1-3
// 分区编号 分区大小 时间 剩余容量 进程名称 所需分区大小 位于几号空闲区
// 1 12 0 A 7 1
// 2 26 5 B 9 2
// 3 32 4 C 12 2
// 4 40 40 D 5 1
// 5 10 10 E 28 3
for(int j=0;j<process.length;j++)
{
//进程处于外层循环，因为每次都从空闲分区的第一个开始找
for(int i=0;i<free.length;i++)
{
//进程没有被服务过
if(process[j].isDone()==false)
{
//进行所需要的资源小于当前分区所剩余的资源
if(free[i].getLeft()>=process[j].getNeed())
{
free[i].setLeft(free[i].getLeft()-process[j].getNeed());
process[j].setDone(true);
process[j].setWhere(free[i].getNumber());
continue;
}
}
else
continue;
}
}
Print_ProcessAndFreePartion(process,free);
}
public void NF(Process [] process,FreePartition [] free)
{
//循环首次适应算法
//测试数据为5个空闲分区，5个进程
//空闲分区：1 12，2 26 ，3 32 ，4 40，5 10
//进程：A 7,B 9,C 12,D 5,E 28
//预期结果：1-2-2-1-3
// 分区编号 分区大小 时间 剩余容量 进程名称 所需分区大小 位于几号空闲区
// 1 12 5 A 7 1
// 2 26 17 B 9 2
// 3 32 20 C 12 3
// 4 40 7 D 5 4
// 5 10 10 E 28 4
System.out.println("NF算法开始:————————————");
int i;
int j;
int cur=0;//cur用于保存下一个空闲分区开始的位置
for(j=0;j<process.length;j++)
{
for(i=0;i<free.length;i++)
{
if(free[(i+cur)%free.length].getLeft()>=process[j].getNeed())
{
free[(i+cur)%free.length].setLeft(free[(i+cur)%free.length].getLeft()-process[j].getNeed());//当前分区减去进程所需要的资源
process[j].setDone(true);//标记该进程已经被服务过
process[j].setWhere(free[(i+cur)%free.length].getNumber());//把当前分区的编号给当前进程
cur=(cur+i+1)%free.length;//+1是因为同时从0开始，不管当前空闲分区能不能满足当前进程需要，都必须指向下一个分区
break;
}
}
if(i==free.length)
{
//对于某个进程j,如果当前进程没有找到合适的分区，i=6时退出了循环，即没有找到合适的分区
System.out.print("空闲分区大小无法满足进程"+process[j].getName()+"的需求 ");
return;
}
}
Print_ProcessAndFreePartion(process,free);
System.out.println("NF算法结束:————————————");
}
public void sort_1_n(Process [] process,FreePartition [] free)
{
for(int q=0;q<free.length;q++)
{
//将分区容量从小到大排序
for(int p=q+1;p<free.length;p++)
{
if(free[q].getLeft()>free[p].getLeft())
swap(free,q,p);
else continue;
}
}
}
public void sort_n_1(Process [] process,FreePartition [] free)
{
for(int q=0;q<free.length;q++)
{
//将分区容量从大到小排序
for(int p=1+q;p<free.length;p++)
{
if(free[q].getLeft()<free[p].getLeft())
swap(free,q,p);
else continue;
}
}
}
public void BF(Process [] process,FreePartition [] free)
{
//最佳适应算法
//测试数据为5个空闲分区，5个进程
//空闲分区：1 12，2 26 ，3 32 ，4 40，5 10
//进程：A 7,B 9,C 12,D 5,E 28
//预期结果：5-1-2-2-3
// 分区编号 分区大小 时间 剩余容量 进程名称 所需分区大小 位于几号空闲区
// 1 12 3 A 7 5
// 2 26 9 B 9 1
// 3 32 4 C 12 2
// 4 40 40 D 5 2
// 5 10 3 E 28 3
//冒泡排序，从小到大
System.out.println("BF算法如下:————————————");
sort_1_n(process,free);
for(int i=0;i<process.length;i++)
{
for(int j=0;j<free.length;j++)
{
if(process[i].isDone()==false)
{
if(free[j].getLeft()>=process[i].getNeed())
{
free[j].setLeft(free[j].getLeft()-process[i].getNeed());
process[i].setDone(true);
process[i].setWhere(free[j].getNumber());
sort_1_n(process,free);
break;
}
else continue;//空闲分区无法满足，找下一个分区
}
else
break; //进程被服务过
}
if(process[i].getNeed()>Max(free))
{
//当前进程需求大于当前的最大容量，则说明无法满足
System.out.println("空闲分区最大容量现为"+Max(free)+",已经无法满足进程"+process[i].getName()+"容量需求为"+process[i].getNeed()+"的请求,自动退出,无法打印");
return;
}
}
//打印
Print_ProcessAndFreePartion(process,free);
System.out.println("BF算法结束:————————————");
}
public void WF(Process [] process,FreePartition [] free)
{
//最坏适应算法
//测试数据为5个空闲分区，5个进程
//空闲分区：1 12，2 26 ，3 32 ，4 40，5 10
//进程：A 7,B 9,C 12,D 5,E 28
//预期结果：4-4-3-2-(-1)
// 分区编号 分区大小 时间 剩余容量 进程名称 所需分区大小 位于几号空闲区
// 1 12 12 A 7 4
// 2 26 26 B 9 4
// 3 32 4 C 12 3
// 4 40 7 D 5 2
// 5 10 10 E 28 无法满足
//冒泡排序，从大到小
System.out.println("WF算法如下:————————————");
sort_n_1(process,free);
for(int j=0;j<process.length;j++)
{
for(int i=0;i<free.length;i++)
{
//该进程没有被服务
if(process[j].isDone()==false)
{
//当前空闲分区大于该进程需求分区大小
if(free[i].getLeft()>=process[j].getNeed())
{
free[i].setLeft(free[i].getLeft()-process[j].getNeed());
process[j].setDone(true);
process[j].setWhere(free[i].getNumber());
sort_n_1(process,free);//产生了无法满足的情况
break;
}
else continue;//空闲分区无法满足，找下一个分区
}
else
break;//进程被服务过
}
if(process[j].getNeed()>Max(free))
{
//当前进程需求大于当前的最大容量，则说明无法满足
System.out.println("空闲分区最大容量现为"+Max(free)+",已经无法满足进程"+process[j].getName()+"容量需求为"+process[j].getNeed()+"的请求,自动退出,无法打印");
return;
}
}
//打印
Print_ProcessAndFreePartion(process,free);
System.out.println("WF算法结束:————————————");
}
public int Max(FreePartition[]free)
{
int max=0;
for(int i=0;i<free.length;i++)
{
if(free[i].getLeft()>max)
max=free[i].getLeft();
}
return max;
}
public void swap(FreePartition[]free,int i,int j)
{
FreePartition newfree=new FreePartition();
newfree=free[i];
free[i]=free[j];
free[j]=newfree;
}
}
public class Experiment {
public static void main(String[] args) {
Scanner Input=new Scanner(System.in);
// System.out.println("请输入空闲分区个数：");
// int n=Input.nextInt();
// FreePartition [] free=new FreePartition[n];
// for(int i=0;i<n;i++)
// {
// System.out.println("请输入第"+(i+1)+"个空闲分区的编号和大小：");
// int number=Input.nextInt();
// int space=Input.nextInt();
// free[i]=new FreePartition(number,space);
// }
// System.out.println("请输入进程的个数：");
// int m=Input.nextInt();
// Process []process=new Process[m];
// for(int i=0;i<m;i++)
// {
// System.out.println("请输入第"+(i+1)+"个进程的名称和所需要的分区大小");
// String name=Input.next();
// int need=Input.nextInt();
// process[i]=new Process(name,need);
// }
FreePartition [] free=new FreePartition[5];
Process []process=new Process[5];
free[0]=new FreePartition(1,12);
free[1]=new FreePartition(2,26);
free[2]=new FreePartition(3,32);
free[3]=new FreePartition(4,40);
free[4]=new FreePartition(5,10);
process[0]=new Process("A",7);
process[1]=new Process("B",9);
process[2]=new Process("C",12);
process[3]=new Process("D",5);
process[4]=new Process("E",28);
System.out.println("请输入选项来选择算法:0-退出,1-首次适应算法,2-循环首次适应算法,3-最佳适应算法，,4-最坏适应算法");
int option=Input.nextInt();
Input.close();
if(option==0)
return;
if(option==1)
new Process().FF(process,free);
if(option==2)
new Process().NF(process,free);
if(option==3)
new Process().BF(process,free);
if(option==4)
new Process().WF(process,free);
}
}
