Banker's Algorithm Java

2025年5月6日 | 阅读 6 分钟

在 Java 中，银行家算法是一种死锁避免和资源分配算法。该算法通过模拟所有资源可能达到的最大数量的分配来测试安全性。之后，在决定是否允许继续分配之前，它会创建一个 **“安全状态”** 检查，以测试所有可能的活动。

为了在 Java 中实现银行家算法，我们使用以下数据结构：

假设系统中我们有 **N** 个进程和 **M** 种资源类型。

Available 数据结构

我们使用的第一个数据结构是 **Available 数据结构**。该数据结构由一个大小为 **M**（可用资源数量）的一维数组构成。如果有 **K** 个 **R_J** 类型的资源实例，它将被表示为：

Available[ J ] = K

Max 数据结构

银行家算法中使用的另一个数据结构是 **Max 数据结构**。该数据结构由一个大小为 **M*N** 的二维数组构成。在系统中，它定义了每个进程的最大需求。

如果一个进程 P_I 请求 **K** 个 **R_J** 类型的资源实例，它将被表示为：

Max[ I, J ] = K

Allocation 数据结构

与 **Available** 和 **Max** 数据结构一样，**Allocation 数据结构** 是一个大小为 **M*N** 的二维数组。它定义了分配给进程的资源总数。

如果进程 **P**_I 目前被分配了 **K** 个 **R_J** 类型的资源实例，它将被表示为：

Allocation[ I, J ] = K

Need 数据结构

**Need 数据结构** 也是一个大小为 **M*N** 的二维数组。它定义了一个进程所需的剩余资源总数。

如果进程 **P**_I 目前被分配了 **K** 个 **R_J** 类型的资源实例，它将被定义为：

Need [ I, J ] = Max[ I, J ] - Allocation [ I, J ]

简而言之，**(Allocation)_I** 定义了目前分配给进程 **P_I** 的资源总数，而 **(Need)_I** 定义了进程 **P_I** 完成其任务所需的剩余资源总数。

我们知道银行家算法是 **资源请求算法** 和 **安全算法** 的组合。

让我们先概览这两种算法，然后用 Java 实现它们来构建银行家算法程序。

资源请求算法

资源请求算法在为进程分配资源时起着重要作用。该算法检查系统在进程发出每种类型的资源请求时将如何表现，并将其视为一个请求矩阵。

资源请求算法如下：

1. 如果 Request_I <= Need_I

跳转到步骤 (2)

否则

打印一条错误消息，指示超过其最大声明。

2. 如果 Request_I <= Available

跳转到步骤 (3)；

否则

打印错误消息“资源不可用”。

3. 为进程分配资源，并从 Available 和 Need 中减去分配给进程的资源数量，如下所示：

Available = Available - Request_I

Allocation_I = Allocation_I + Request_I

Need_I = Need_I - Request_I

安全算法

安全算法用于确定我们的系统是否处于安全状态。如果系统在银行家算法中遵循安全序列，那么我们的系统就处于安全状态。安全算法如下：

1. 令 **Work** 和 **Finish** 为长度分别为 **M** 和 **N** 的两个向量。

初始化：Work = Available

对于 1 到 N

Finish [ i ] = false;

2. 查找 i，使得同时满足：

Finish [ i ] = false
Need_i <= work

如果不存在这样的 i，则转到步骤 (4)。

3. Work = Work + Allocation_i

Finish[ i ] = true

转到步骤 (2)。

4. 如果所有 i 都满足 Finish[ i ] = true，

则系统处于安全状态。

要了解更多关于银行家算法、资源请求算法和安全算法的知识，请访问以下链接：bankers-algorithm-in-operating-system

现在，让我们使用上面讨论的资源请求算法和安全算法在 Java 中实现银行家算法的代码。

BankersAlgoExample.java

// import required classes and packages
import java.util.*; 
import java.io.*; 
import java.util.Scanner;

// create BankersAlgoExample class to implement Banker's algorithm in Java
class BankersAlgoExample
{

	// create findNeedValue() method to calculate the need of each process
	static void findNeedValue(int needArray[][], int maxArray[][], int allocationArray[][], int totalProcess, int totalResources)
	{
		// use nested for loop to calculate Need for each process
		for (int i = 0 ; i < totalProcess ; i++){	// for each process
			for (int j = 0 ; j < totalResources ; j++){	//for each resource
				needArray[i][j] = maxArray[i][j] - allocationArray[i][j];
			}
		}
	}

	// create checkSafeSystem() method to determine whether the system is in safe state or not
	static boolean checkSafeSystem(int processes[], int availableArray[], int maxArray[][], int allocationArray[][], int totalProcess, int totalResources)
	{
		int [][]needArray = new int[totalProcess][totalResources];

		// call findNeedValue() method to calculate needArray
		findNeedValue(needArray, maxArray, allocationArray, totalProcess, totalResources);

		// all the process should be infinished in starting
		boolean []finishProcesses = new boolean[totalProcess];

		// initialize safeSequenceArray that store safe sequenced
		int []safeSequenceArray = new int[totalProcess];

		// initialize workArray as a copy of the available resources
		int []workArray = new int[totalResources];
		
		for (int i = 0; i < totalResources ; i++)	//use for loop to copy each available resource in the workArray
			workArray[i] = availableArray[i];

		// initialize counter variable whose value will be 0 when the system is not in the safe state or when all the processes are not finished.
		int counter = 0;
		
		// use loop to iterate the statements until all the processes are not finished
		while (counter < totalProcess)
		{
			// find infinished process which needs can be satisfied with the current work resource.
			boolean foundSafeSystem = false;
			for (int m = 0; m < totalProcess; m++)
			{
				if (finishProcesses[m] == false)		// when process is not finished
				{
					int j;
					
					//use for loop to check whether the need of each process for all the resources is less than the work
					for (j = 0; j < totalResources; j++)
						if (needArray[m][j] > workArray[j])		//check need of current resource for current process with work
							break;

					// the value of J and totalResources will be equal when all the needs of current process are satisfied
					if (j == totalResources)
					{
						for (int k = 0 ; k < totalResources ; k++)
							workArray[k] += allocationArray[m][k];

						// add current process in the safeSequenceArray
						safeSequenceArray[counter++] = m;

						// make this process finished
						finishProcesses[m] = true;

						foundSafeSystem = true;
					}
				}
			}

			// the system will not be in the safe state when the value of the foundSafeSystem is false
			if (foundSafeSystem == false)
			{
				System.out.print("The system is not in the safe state because lack of resources");
				return false;
			}
		}

		// print the safe sequence
		System.out.print("The system is in safe sequence and the sequence is as follows: ");
		for (int i = 0; i < totalProcess ; i++)
			System.out.print("P"+safeSequenceArray[i] + " ");

		return true;
	}

	// main() method start
	public static void main(String[] args)
	{	
		int numberOfProcesses, numberOfResources;
		
		//create scanner class object to get input from user
		Scanner sc = new Scanner(System.in);
		
		// get total number of resources from the user
		System.out.println("Enter total number of processes");
		numberOfProcesses = sc.nextInt();
		
		// get total number of resources from the user
		System.out.println("Enter total number of resources");
		numberOfResources = sc.nextInt();
		
		int processes[] = new int[numberOfProcesses];
		for(int i = 0; i < numberOfProcesses; i++){
			processes[i] = i;
		}
		
		int availableArray[] = new int[numberOfResources];
		for( int i = 0; i < numberOfResources; i++){
			System.out.println("Enter the availability of resource"+ i +": ");
			availableArray[i] = sc.nextInt();
		}
		
		int maxArray[][] = new int[numberOfProcesses][numberOfResources];
		for( int i = 0; i < numberOfProcesses; i++){
			for( int j = 0; j < numberOfResources; j++){
				System.out.println("Enter the maximum resource"+ j +" that can be allocated to process"+ i +": ");
				maxArray[i][j] = sc.nextInt();
			}
		}
		
		int allocationArray[][] = new int[numberOfProcesses][numberOfResources];
		for( int i = 0; i < numberOfProcesses; i++){
			for( int j = 0; j < numberOfResources; j++){
				System.out.println("How many instances of resource"+ j +" are allocated to process"+ i +"? ");
				allocationArray[i][j] = sc.nextInt();
			}
		}
		
		//call checkSafeSystem() method to check whether the system is in safe state or not
		checkSafeSystem(processes, availableArray, maxArray, allocationArray, numberOfProcesses, numberOfResources);
	}
}

输出