Java实现简单银行家算法

什么是银行家算法

银行家算法是一种避免进程死锁的算法，其主要用于资源分配的场景中（如操作系统、数据库系统等），能够有效地预防死锁的发生。

银行家算法的规则

银行家算法基于以下规则判断系统是否可以在不发生死锁的情况下分配资源：
- 每个进程对资源的最大需求量是确定的，也就是说一个进程一旦声明了最大需求量，就不能再超过它所声明的最大值。
- 系统可用的资源是确定的，资源总数不能够变化。也就是说，一旦某类资源的总数被分配完毕，别的进程就无法在得到该类资源。
- 当一个进程需要某些资源时，它必须申请并明确说明它需要多少资源（这样系统才能够判断是否可以满足该进程的资源需求）。如果当前可分配的资源数不足，进程必须等待。

Java实现银行家算法的步骤

1. 确定资源总数与各进程的最大需求量；
2. 维护一个数组available，表示当前系统可用资源量；
3. 维护一个数组allocation，表示当前已经分配给各进程的资源量；
4. 维护一个数组need，表示每个进程还需要的资源量；
5. 假设请求分配的资源量为request_vector，请求的进程编号为pid；
6. 判断request_vector是否小于等于need[pid]的值；
7. 若request_vector小于等于need[pid]的值，则判断request_vector是否小于等于available；
8. 若request_vector小于等于available，则进行分配，调整available、allocation和need数组；
9. 若request_vector大于available，则拒绝分配。

示例说明

这里给出两个简单的示例，以帮助理解银行家算法的原理。

示例1：

假设系统中有5个进程和3类资源，每个进程对各类资源的最大需求量和已分配资源量如下表所示：

进程号	Max	Alloc
0	7 5 3	0 1 0
1	3 2 2	2 0 0
2	9 0 2	3 0 2
3	2 2 2	2 1 1
4	4 3 3	0 0 2

系统可用资源情况为：3 3 2。进程1提出请求（1，0，2）。

根据银行家算法的步骤，可以得到以下结果：

• 首先判断请求量是否小于等于该进程本身还需要的资源量，即request_vector <= need[pid]的值，根据表中Max和Alloc的数据，可以得到该进程本身还需要的资源量是（1 2 2）。因此，(1，0，2) <= （1 2 2）；
• 进一步判断该请求是否小于等于系统目前可用的资源总量，即request_vector <= available的值，因为目前可用资源总量是（3 3 2），所以（1，0，2）<=（3 3 2）；
• 因此可以进行资源分配，根据银行家算法的规则分配后可得到以下结果：

进程号	Max	Alloc	Need	Avail
0	7 5 3	0 1 0	7 4 3	1 3 2
1	3 2 2	2 0 0	1 2 2
2	9 0 2	3 0 2	6 0 0
3	2 2 2	2 1 1	0 1 1
4	4 3 3	0 0 2	4 3 1

• 最终可得到系统可用资源情况是（0 3 0）。

示例2：

与示例1相同，提供请求量信息（1,1,0）。

• 首先判断请求量是否小于等于该进程本身还需要的资源量，即request_vector <= need[pid]的值，根据表中Max和Alloc的数据，可以得到该进程本身还需要的资源量是（3 1 2）。因此，(1，1，0) <=（3 1 2）；
• 进一步判断该请求是否小于等于系统目前可用的资源总量，即request_vector <= available的值，因为目前可用资源总量是（0 3 0），所以（1，1，0）!<=（0 3 0）；
• 因此拒绝资源分配，避免进程死锁。