在C语言中使用银行家算法预防死锁
什么是死锁
死锁是指在一个并发系统中,两个或以上的线程互相等待对方的资源而无限制地等待下去,使得进程无法继续运行而陷入一种“死循环”,形成死锁。
银行家算法
银行家算法是一种避免死锁的算法。它通过动态地分配资源,避免进程因竞争资源而发生死锁,并保证分配的资源不会导致系统不安全。
银行家算法的实现需要考虑以下信息:
- Available:当前可用的资源数目。
- Max:系统中每种资源的最大需求量。
- Allocation:系统中每种资源当前已分配的数量。
- Need:系统中每种资源还需要的数量。
死锁避免的步骤
使用银行家算法避免死锁可以分为以下步骤:
- 初始化资源可用数量 Available,系统的所有进程以及它们的资源需求量 Max 和已分配资源数量 Allocation。
- 检查系统是否处于安全状态,也就是系统是否有足够的资源满足后续进程的请求。如果是,则接受请求并更新资源分配情况;否则,拒绝请求,等待其他进程释放资源。
- 继续进行死锁预防工作。每当分配或释放资源时,都要重新计算实际可用资源和各个进程还需要的资源数量,并尝试将之前因拒绝请求而被阻塞的进程重新考虑分配资源。
示例1:使用银行家算法避免死锁
假设系统中有5个进程,申请资源的顺序为 P1、P2、P3、P4、P5。分别显示它们对三类资源的最大需求量 Max 和已分配资源数量 Allocation 如下表所示。
进程 | Allocation | Max | Need |
---|---|---|---|
P1 | 1 1 0 | 2 1 1 | 1 0 1 (Max-Allo) |
P2 | 1 0 1 | 2 1 2 | 1 1 1 |
P3 | 1 0 0 | 1 2 0 | 0 2 0 |
P4 | 0 0 1 | 3 0 0 | 3 0 2 |
P5 | 0 0 1 | 2 0 1 | 2 0 0 |
此时可用资源数量 Available 为 1 2 0。
假设现在进程 P4 申请 1 0 0 资源,判断如下:
- 检查系统是否处于安全状态,此时 Available 与 Need 比较结果如下:
进程 | Need | Available | Work | Finish |
---|---|---|---|---|
P1 | 1 0 1 | 0 2 0 | 0 0 0 | No |
P2 | 1 1 0 | |||
P3 | 0 2 0 | |||
P4 | 3 0 2 | |||
P5 | 2 0 0 |
则 P2 或 P3 可以被分配资源,我们选择 P2,分配资源后,状态如下:
进程 | Allocation | Need | Available | Work | Finish |
---|---|---|---|---|---|
P1 | 1 0 1 | 1 0 0 | 0 1 0 | 1 0 0 | No |
P2 | 1 1 1 | 1 0 1 | 1 1 0 | 0 1 0 | Yes |
P3 | 1 0 0 | 0 2 0 | 1 2 1 | 0 0 0 | No |
P4 | 0 0 1 | 3 0 1 | 1 2 1 | 0 0 1 | No |
P5 | 0 0 1 | 2 0 0 | 1 2 2 | 0 0 0 | No |
- P4 的申请可以被满足,并更新 Allocation 和 Available 信息,状态如下:
进程 | Allocation | Max | Need |
---|---|---|---|
P1 | 1 0 1 | 2 1 1 | 1 1 0 |
P2 | 1 1 1 | 2 1 2 | 1 0 1 |
P3 | 1 0 0 | 1 2 0 | 0 2 0 |
P4 | 0 0 2 | 3 0 0 | 3 0 0 |
P5 | 0 0 1 | 2 0 1 | 2 0 0 |
1 1 4 | 10 5 8 | 5 3 9 (Max-Allo) |
- 继续进行死锁预防工作,更新各个进程需要的资源数量,状态如下:
进程 | Allocation | Max | Need |
---|---|---|---|
P1 | 1 0 1 | 2 1 1 | 1 1 0 |
P2 | 1 1 1 | 2 1 2 | 1 0 1 |
P3 | 1 0 0 | 1 2 0 | 0 2 0 |
P4 | 0 0 2 | 3 0 0 | 3 0 0 |
P5 | 0 0 1 | 2 0 1 | 2 0 0 |
示例2:配合源代码使用银行家算法避免死锁
下面是一个基于 C 语言的简单死锁避免示例代码,使用了银行家算法的思想。它让两个线程按不同的顺序执行,增加了产生死锁的概率,验证了死锁验证的正确性。
#include<stdio.h>
#include<stdlib.h>
int available[10],max[10][10],allocation[10][10],need[10][10],flag[10],work[10];
int num_process,num_res;
int input_data() {
int i,j;
printf("Enter the number of processes: ");
scanf("%d",&num_process);
printf("Enter the number of types of resources: ");
scanf("%d",&num_res);
for(i=1;i<=num_process;i++){
printf("Enter the allocation of process %d: ",i);
for(j=1;j<=num_res;j++){
scanf("%d",&allocation[i][j]);
}
flag[i]=0;
}
printf("\n");
for(i=1;i<=num_process;i++){
printf("\nEnter the Max Matrix for process %d : ",i);
for(j=1;j<=num_res;j++){
scanf("%d",&max[i][j]);
}
}
printf("\n");
printf("\nEnter the Available Resources : ");
for(i=1;i<=num_res;i++){
scanf("%d",&available[i]);
work[i]=available[i];
}
printf("\n");
return 0;
}
void calculate_need(){
int i,j;
for(i=1;i<=num_process;i++){
for(j=1;j<=num_res;j++){
need[i][j]=max[i][j]-allocation[i][j];
}
}
}
int check_availability(int j){
int i;
for(i=1;i<=num_res;i++){
if (need[j][i]>work[i]){
return 0;
}
}
return 1;
}
int wait_or_exit(){
int i,j,found,flag;
for(i=1;i<=num_process;i++){
if(flag[i]==0 && check_availability(i)){
flag[i]=1;
for(j=1;j<=num_res;j++){
work[j]=work[j]+allocation[i][j];
}
break;
}
}
if(i>num_process){
return 0;
}
else{
return 1;
}
}
void detect_deadlock(){
int i,j,found,flag;
calculate_need();
int process_allocated = 0;
while(process_allocated<num_process){
found = 0;
for(i=1;i<=num_process;i++){
if(flag[i]==0 && check_availability(i)){
flag[i]=1;
found = 1;
printf("\nProcess %d is allocated resources ",i);
for(j=1;j<=num_res;j++){
work[j]=work[j]+allocation[i][j];
}
process_allocated++;
}
}
if(found==0){
printf("\nSystem is not in safe state\n");
return;
}
}
printf("\nSystem is in safe state\n");
}
int main(){
input_data();
detect_deadlock();
return 0;
}
这个代码输入了最大需求量、当前已分配数量和可用资源数量。它先计算出需要的资源数量,然后检查系统是否处于安全状态。如果不是,就需要等待其他资源释放。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:在C语言中使用银行家算法预防死锁 - Python技术站