预防死锁的银行家算法

package experiment;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

class Process

{

private String Name; //名称

private int []Allocation;//占用的资源

private int []Need;//仍需要的资源

private boolean Finish;//是否完成

private int LoopCount;

Process(){}

Process(String Name,int []Allocation,int []Need)

{

this.Name=Name;

this.Allocation=Allocation;

this.Need=Need;

}

public String getName() {

return Name;

}

public int[] getAllocation() {

return Allocation;

}

public int[] getNeed() {

return Need;

}

public int getLoopCount() {

return LoopCount;

}

public boolean isFinish() {

return Finish;

}

public void setName(String name) {

Name = name;

}

public void setAllocation(int[] allocation) {

Allocation = allocation;

}

public void setNeed(int[] need) {

Need = need;

}

public void setFinish(boolean finish) {

Finish = finish;

}

public void setLoopCount(int LoopCount) {

this.LoopCount = LoopCount;

}

public void SafeOrder(Process[]process,int []Available)

{

//求安全序列

/*

  从第一个进程开始，对每一个进程，去判断系统剩余的资源能不能满足该进程仍需要的资源，

  能则分配给该进程，然后将该进程名加入到安全序列，并将该进程原来占用的资源加入到系统 剩余资源；

不能则跳过该进程，对下一个进程进行判断；

  */

String safeOrder="";

Queue<Integer> queue = new LinkedList<Integer>(); //创建一个队列，用于队列的排队

for(int i=0;i<process.length;i++)

{

queue.add(i);//将进程加入队列

}

int oldSize=queue.size();//原队列数量

int ProcessCantEnough=0;//进程不能满足数量

for(int i=queue.peek();i<process.length; i=queue.peek())

{

if(oldSize==ProcessCantEnough)

{

//每一个进程都无法满足

for(int n=0;n<queue.size();n++)

{

int peek=queue.peek();

System.out.println("进程"+process[peek].Name+"无法满足");

queue.remove();

}

System.out.println("所以该新请求不能允许");

break;

}

if(Compare(process[i].getNeed(),Available)&&process[i].isFinish()==false)

{

//当前进程的请求系统可以满足

Add(process[i].getAllocation(),Available);//把进程占用的资源还给系统

safeOrder=safeOrder+process[i].getName()+"->";//把当前进程的名字加入安全序列

process[i].setFinish(true); //标记进程完成

queue.remove();//完成则将进程移除队列

            if(!queue.isEmpty())

            continue;

}

if(!Compare(process[i].getNeed(),Available))

{

//当前进程的请求系统不能满足

process[i].setLoopCount(process[i].getLoopCount()+1);//当前进程第一次不能满足

int peek=queue.peek();  //取队首

queue.remove();  //移除队首

queue.add(peek);//加入队尾

ProcessCantEnough++;//不能满足进程数量+1

}

if(queue.isEmpty())

break;

}

if(queue.size()==0)

System.out.println("当前状态安全  ;"+"安全序列为:"+new String(safeOrder.substring(0, safeOrder.length()-2)));  

}

public boolean Compare(int []Need,int []Available )

{

if(Need.length==Available.length)

{

for(int i=0;i<Need.length;i++)

{

if(Available[i]>=Need[i])

continue;

else

return false;

}

return true;

}

else return false;

}

public int[] Add(int []Allocation,int []Available)

{

if(Allocation.length==Available.length)

{

for(int i=0;i<Allocation.length;i++)

Available[i]+=Allocation[i];

}

else

System.out.println("长度不一样,相加失败");

return Available;

}

public void Subtraction (int []Allocation,int []Available)

{

if(Allocation.length==Available.length)

{

for(int i=0;i<Allocation.length;i++)

Available[i]-=Allocation[i];

}

else

System.out.println("长度不一样,相减失败");

}

public void Request(Process[]process,int []Available,int []newNeed,String Name)

{

//安全则提出新一轮的安全请求

for(int i=0;i<process.length;i++)

{

if(process[i].getName().equals(Name))

{

Add(newNeed,process[i].getNeed());

Subtraction(newNeed,Available);

break;

}

}

new Process().SafeOrder(process,Available);

}

public void Print_Allocation_Need(Process[]process,int []Available)

{

System.out.println("进程的名称"+"        "+"进程占用的资源"+"            "+"  进程仍需要的资源");

for(int i=0;i<process.length;i++)

{

System.out.print("  "+process[i].getName()+"      ");

for(int j=0;j<process[i].Allocation.length;j++)

System.out.print(process[i].Allocation[j]+" ");

System.out.print("        ");

for(int j=0;j<process[i].getNeed().length;j++)

System.out.print(+process[i].Need[j]+" ");

System.out.println();

}

System.out.print("系统剩余资源为：");

    for(int i=0;i<Available.length;i++)

    System.out.print(Available[i]+" ");

    System.out.println();

}

}

public class Experiment {

public static void main(String[] args) {

// System.out.print("请输入进程个数:");

Scanner Input=new Scanner(System.in);

// int num=Input.nextInt();

// Process[] process=new  Process[num];

// System.out.print("请输入资源种类：");

// int typeCount=Input.nextInt();

// for(int i=0;i<process.length;i++)

// {

// System.out.println("请输入第"+(i+1)+"个进程的名称，已分配的资源,还需要分配的资源");

// String Name=Input.next();

// String getAllocation=Input.next();

//     String getNeed=Input.next();

//     int Allocation[]=new int [typeCount];

//       for(int j=0;j<typeCount;j++)

//       Allocation[j]=(int)(getAllocation.charAt(j)-'0');

//       int Need[]=new int [typeCount];

//       for(int j=0;j<typeCount;j++)

//       Need[j]=(int)(getNeed.charAt(j)-'0');

//       process[i]=new Process(Name,Allocation,Need);

// }

// System.out.println("请输入系统剩余资源：");

// String getAvailable=Input.next();

// int Available[]=new int [typeCount];

// for(int i=0;i<typeCount;i++)

// Available[i]=(int)(getAvailable.charAt(i)-'0');

// int []Available_copy=Available.clone();

// new Process().SafeOrder(process,Available);  

// new Process().Print_Allocation_Need(process,Available_copy);

// System.out.println("请输入新一轮的请求: 进程名 + 需求的资源"+"(提示:需求的资源最好不要超过系统剩余资源)");

// String name=Input.next();

// String getNewNeed=Input.next();

// int newNeed[]=new int [typeCount];

// for(int i=0;i<typeCount;i++)

// newNeed[i]=(int)(getNewNeed.charAt(i)-'0');

// new Process().Request(process,Available_copy,newNeed,name);

// Input.close();

  int Allocation0[]= {0,0,3,2};

  int Allocation1[]= {1,0,0,0};

  int Allocation2[]= {1,3,5,4};

  int Allocation3[]= {0,3,3,2};

  int Allocation4[]= {0,0,1,4};  

  int Need0[]= {0,0,1,2};

  int Need1[]= {1,7,5,0};

  int Need2[]= {2,3,5,6};

  int Need3[]= {0,6,5,2};

  int Need4[]= {0,6,5,6};

  Process[] process=new  Process[5];

  process[0]=new Process("A",Allocation0,Need0);

  process[1]=new Process("B",Allocation1,Need1);

  process[2]=new Process("C",Allocation2,Need2);

  process[3]=new Process("D",Allocation3,Need3);

  process[4]=new Process("E",Allocation4,Need4);

  int Available[]= {1,6,2,2};

  int []Available_copy=Available.clone();

  new Process().SafeOrder(process,Available);  

  new Process().Print_Allocation_Need(process,Available_copy);

//   System.out.println("请输入新一轮的请求: 进程名 + 需求的资源"+"(提示,需求的资源最好不要超过系统剩余资源)");

//

//   String name=Input.next();

// String getNewNeed=Input.next();

// int newNeed[]=new int [4];

// for(int i=0;i<4;i++)

// newNeed[i]=(int)(getNewNeed.charAt(i)-'0');

// new Process().Request(process,Available_copy,newNeed,name);

  int []newNeed= {1,2,2,2};

  new Process().Request(process,Available_copy,newNeed,"C");

}

}