下面是在C语言中使用银行家算法预防死锁的完整使用攻略。
什么是银行家算法
银行家算法是一种预防死锁的算法，在多进程环境下，通过判断每个进程所需资源量和系统当前资源量的关系来决定是否分配资源，从而避免死锁。它主要分为安全性算法和避免死锁算法两种。
安全性算法
安全性算法主要用于在分配前就判断是否会发生死锁。算法流程如下：
- 建立资源分配图，其中节点表示进程和资源，边表示进程和资源的关系。
- 计算每个节点的可用资源数，以及每个节点还需要的资源数。
- 寻找可满足的节点（既满足节点还需要的资源数不大于系统可用的资源数），将这些节点从图中删除，将它们的资源归还给系统。
- 重复上一步，直到所有节点都能找到满足的资源位置，或者没有可用资源位置来满足节点的需求。
如果在实际的执行中，所有节点都能找到满足的资源位置，则说明系统是安全的，能避免死锁。否则，系统是不安全的，需要采取措施防止死锁。
避免死锁算法
避免死锁算法主要用于在运行中防止死锁。算法流程如下：
- 初始化时，记录下系统中每种资源的总量和已使用量。
- 当进程请求资源时，判断系统能否满足它的需求。如果可以，分配资源；否则挂起进程，等待资源变得可用。
- 进程归还资源时，对系统资源进行更新，以保持系统的资源数不变。
- 判断系统是否安全，如果安全，继续执行；如果不安全，回滚资源分配，等待资源变得可用。
- 重复上一步，直到所有进程都能够得到所需资源。
其中，第4步是银行家算法最核心的一步。在回滚资源分配前，需要判断回滚后的系统是否仍然是安全的，如果不是，需要继续等待资源变得可用。
示例说明
下面我将通过两个简单的示例，分别说明采用安全性算法和避免死锁算法如何在C语言中使用，具体实现代码可以架构不同而不同。
安全性算法示例
假设系统中有3个进程和4个资源，资源分别为A、B、C、D，而每个进程所需的资源如下：
| 进程 | A | B | C | D |
|---|---|---|---|---|
| P1 | 2 | 1 | 0 | 1 |
| P2 | 0 | 1 | 0 | 2 |
| P3 | 1 | 2 | 3 | 0 |
现在需要判断系统是否安全。根据安全性算法，我们需要按照以下流程进行计算。
-
建立资源分配图，其中节点表示进程和资源，边表示进程和资源的关系。
“`
+—–+ +—+
| P1 | -> | A |
+—–+ +-+-+
|
+—+—+
| P1/P2 |
+—+—+
A/ | |
+-+-+ +-+-+
| B | | D |
+-+-+ +-+-+
| |
+—–+—–+—–+
| P2 | P3 | P3 |
+—–+—–+—–+
| | |
+-++ +-++ +-++ +-+
|B | |C | |A | |A |
+-++ +-++ +-++ +-+“`
-
计算每个节点的可用资源数，以及每个节点还需要的资源数。
+-----+ +---+
| P1 | -> | A | Available=2
+-----+ +-+-+ B=1
| C=3
+---+---+ D=1
| P1/P2 |
+---+---+
A/ | | P1/A = 2
+-+-+ +-+-+ P1/B = 1
| B | | D | P1/C = 0
+-+-+ +-+-+ P1/D = 1
| |
+-----+-----+-----+
| P2 | P3 | P3 | P2/A = 0
+-----+-----+-----+ P2/B = 0
| | | P2/C = 0
+-++ +-++ +-++ +-+ P2/D = 2
|B | |C | |A | |A |
+-++ +-++ +-++ +-+
| |
| |
+-+-+ +-+-+
| D | | B |
+-+-+ +-+-+
| |
+-----+ -
寻找可满足的节点，将这些节点从图中删除，将它们的资源归还给系统。
根据上面的表格，我们可以找到安全序列：P1,P3,P2。这表示从P1开始，每个进程都能获得它所需要的资源。
-
重复上一步，直到所有节点都能找到满足的资源位置，或者没有可用资源位置来满足节点的需求。
由于已经找到了安全序列，这一步就可以跳过了。
因此，我们判断出这个系统是安全的，可以避免死锁。
避免死锁算法示例
以下是一个简单的代码示例，说明如何在C语言中使用银行家算法进行资源调度。假设系统中有5个进程和3个资源，各进程所需的资源如下：
| 进程 | A | B | C |
|---|---|---|---|
| P1 | 3 | 2 | 2 |
| P2 | 1 | 2 | 3 |
| P3 | 1 | 3 | 5 |
| P4 | 2 | 0 | 4 |
| P5 | 4 | 3 | 2 |
代码示例：
#include<stdio.h>
int main()
{
int available[3]={3,3,2};//系统可用资源
int max[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//最大需求矩阵
int allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//已分配矩阵
int need[5][3];//需求矩阵
int finish[5]={0,0,0,0,0};
int request[3]={1,0,2};
int flag=0;
int count=0;
//计算需求矩阵
for(int i=0;i<5;i++){
for(int j=0;j<3;j++){
need[i][j]=max[i][j]-allocation[i][j];
}
}
//查找可行状态
while(1){
flag=0;
for(int i=0;i<5;i++){
if(finish[i]==0){
int j;
for(j=0;j<3;j++){
if(need[i][j]>available[j]){
break;
}
}
if(j==3){//能找到满足的资源位置
for(int k=0;k<3;k++){
available[k]=available[k]+allocation[i][k];//归还资源
}
finish[i]=1;
flag=1;//标记找到一个满足的进程
count++;
}
}
if(i==4&&flag==0){//没有可行状态
break;
}
}
if(count==5){//这个状态是安全的
printf("System is safe.\n");
break;
}
}
//向系统申请资源
for(int i=0;i<3;i++){
if(request[i]>need[3][i]){//请求超过了需求量
printf("Request denied.\n");
return 0;
}
if(request[i]>available[i]){//请求超过了可用资源量
printf("Request denied.\n");
return 0;
}
}
for(int i=0;i<3;i++){//修改已分配矩阵和需求矩阵
allocation[3][i]=allocation[3][i]+request[i];
need[3][i]=need[3][i]-request[i];
available[i]=available[i]-request[i];
}
//重新查找可行状态
for(int i=0;i<5;i++){//重置finish数组
finish[i]=0;
}
count=0;//重置count
while(1){
flag=0;
for(int i=0;i<5;i++){
if(finish[i]==0){
int j;
for(j=0;j<3;j++){
if(need[i][j]>available[j]){
break;
}
}
if(j==3){//能找到满足的资源位置
for(int k=0;k<3;k++){
available[k]=available[k]+allocation[i][k];//归还资源
}
finish[i]=1;
flag=1;//标记找到一个满足的进程
count++;
}
}
if(i==4&&flag==0){//没有可行状态
break;
}
}
if(count==5){//这个状态是安全的
printf("Request granted.\n");
break;
}
}
return 0;
}
在这个示例中，我们通过银行家算法来判断请求是否能够被满足。如果能够被满足，我们就将对应的资源归还给系统，并修改已分配矩阵和需求矩阵。如果不能被满足，就拒绝请求。