含请求功能的Banker's Algorithm程序误报死锁，求助调试

云上老周

2026-7-13

问题：银行家算法请求分配后安全序列检测失效

我给原本无请求分配功能的银行家算法程序添加了新的请求分配逻辑，程序能正常更新Available矩阵和Need矩阵，但第88行之后的安全序列检测功能异常：在实际存在安全序列的测试场景中，程序却输出---DEADLOCK OCCURED---，且安全序列检测循环里只打印一次变量i的值。

预期输出

Enter the Number of Processes : 5
Enter the Number of Resources : 3

ALLOCATION MATRIX

Enter the Allocation for P1 : 0 1 0
Enter the Allocation for P2 : 2 0 0
Enter the Allocation for P3 : 3 0 2
Enter the Allocation for P4 : 2 1 1
Enter the Allocation for P5 : 0 0 2

MAXIMUM MATRIX

Enter the Maximum for P1 : 7 5 3
Enter the Maximum for P2 : 3 2 2
Enter the Maximum for P3 : 9 0 2
Enter the Maximum for P4 : 2 2 2
Enter the Maximum for P5 : 4 3 3

NEED MATRIX

 7  4  3
 1  2  2
 6  0  0
 0  1  1
 4  3  1

AVAILABLE MATRIX

Enter the Available : 3 3 2

REQUEST MATRIX

Enter the Requested Allocation : 1 0 2
Which Process you want to Request (0 - 4): 1

---SAFESEQUENCE---
P1 ==> P3 ==> P4 ==> P0 ==> P2

实际输出

Enter the Number of Processes : 5
Enter the Number of Resources : 3

ALLOCATION MATRIX

Enter the Allocation for P1 : 0 1 0
Enter the Allocation for P2 : 2 0 0
Enter the Allocation for P3 : 3 0 2
Enter the Allocation for P4 : 2 1 1
Enter the Allocation for P5 : 0 0 2

MAXIMUM MATRIX

Enter the Maximum for P1 : 7 5 3
Enter the Maximum for P2 : 3 2 2
Enter the Maximum for P3 : 9 0 2
Enter the Maximum for P4 : 2 2 2
Enter the Maximum for P5 : 4 3 3

NEED MATRIX

 7  4  3
 1  2  2
 6  0  0
 0  1  1
 4  3  1

AVAILABLE MATRIX

Enter the Available : 3 3 2

REQUEST MATRIX

Enter the Requested Allocation : 1 0 2
Which Process you want to Request (0 - 4): 1

New Available :  2  3  0

NEED MATRIX

 7  4  3
 0  2  0
 6  0  0
 0  1  1
 4  3  1

---DEADLOCK OCCURED---

完整代码

#include<stdio.h>

void main()
{
    int n,m,reqprocess;
    printf("Enter the Number of Processes : ");
    scanf("%d",&n);
    printf("Enter the Number of Resources : ");
    scanf("%d",&m);

    int alloc[n][m],max[n][m],need[n][m],avai[m],req[m];

    printf("\nALLOCATION MATRIX\n\n");
    for(int i = 0 ; i < n ; i++)
    {
        printf("Enter the Allocation for P%d : ",i+1);
        for(int j = 0 ; j < m ; j++)
        {
            scanf("%d",&alloc[i][j]);
        }
    }

    printf("\MAXIMUM MATRIX\n\n");
    for(int i = 0 ; i < n ; i++)
    {
        printf("Enter the Maximum for P%d : ",i+1);
        for(int j = 0 ; j < m ; j++)
        {
            scanf("%d",&max[i][j]);
        }
    }
    printf("\nNEED MATRIX\n\n");
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < m ; j++)
        {
            need[i][j] = max[i][j] - alloc[i][j];
            printf(" %d ",need[i][j]);
        }
        printf("\n");
    }
    printf("\nAVAILABLE MATRIX\n\n");
    printf("Enter the Available : ");
    for(int i = 0 ; i < m ; i++)
    {
        scanf("%d",&avai[i]);
    }

    printf("\nREQUEST MATRIX\n\n");
    printf("Enter the Requested Allocation : ");
    for(int i = 0 ; i < m ; i++)
    {
        scanf("%d",&req[i]);
    }
    printf("Which Process you want to Request (0 - %d): ",n-1);
    scanf("%d",&reqprocess);

    for(int i = 0 ; i < m ; i++)
    {
        int flag = 0;
        if(req[i] > avai[i])
        {
            flag = 1;
            printf("REQUEST NOT POSSIBLE\n");
            break;
        }
        if(flag == 0)
        {
            avai[i] -= req[i];
            need[reqprocess][i] -= req[i];
        }

    }
    printf("New Avaialable : ");
    for(int i = 0 ; i < m ; i++)
    {
        printf(" %d ",avai[i]);
    }
    printf("\nNEED MATRIX\n\n");
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < m ; j++)
        {
            printf(" %d ",need[i][j]);
        }
        printf("\n");
    }
// line 88
    int work[m],finish[n],safeSequence[n],ind = 0;

    printf("Work : ");
    for(int i = 0 ; i < m ; i++)
    {
        work[i] = avai[i];
        printf(" %d ",work[i]);
    }
    for(int i = 0 ; i < n ; i++)
    {
        finish[i] = 0;
    }

    for(int k = 0 ; k < n ; k++)
    {
        for(int i = 0 ; i < n ; i++)
        {
            if(finish[i] == 0)
            {
                int flag = 0;
                for(int j = 0 ; j < m ; j++)
                {
                    if(need[i][j] > work[j])
                    {
                        flag = 1;
                        break;
                    }
                }
                if(flag == 0)
                {
                    printf("i : %d",i);
                    safeSequence[ind++] = i;
                    for(int y = 0 ; y < m ; y++)
                    {
                        work[y] = work[y] + alloc[i][y];
                        finish[i] = 1;
                    }

                }
            }
        }
    }
    int flag = 1;
    for(int i = 0 ; i < n ; i++)
    {
        if(finish[i] == 0)
        {
            flag = 0;
            printf("\n---DEADLOCK OCCURED---\n");
            break;
        }
    }
    if(flag == 1)
    {
        printf("\n---SAFESEQUENCE---\n");
        for(int i = 0 ; i < n-1 ; i++)
        {
            printf("P%d ==> ",safeSequence[i]);
        }
        printf("P%d",safeSequence[n-1]);

    }
}

问题原因及修复方案

1. 核心错误：未更新Allocation矩阵

请求分配成功后，你只更新了Available和Need矩阵，但漏掉了更新对应进程的Allocation矩阵。安全序列检测时，work需要累加进程完成后释放的已分配资源，旧的Allocation值会导致work累加错误，无法满足后续进程的资源需求，最终误判为死锁。

修复请求分配逻辑，同时补全银行家算法的前置校验（请求不能超过进程的Need值）：

int flag = 0;
// 先检查请求是否合法
for(int i = 0 ; i < m ; i++)
{
    if(req[i] > need[reqprocess][i])
    {
        flag = 1;
        printf("REQUEST EXCEEDS PROCESS'S NEED\n");
        break;
    }
    if(req[i] > avai[i])
    {
        flag = 1;
        printf("REQUEST NOT POSSIBLE (INSUFFICIENT RESOURCES)\n");
        break;
    }
}
// 合法则更新所有相关矩阵
if(flag == 0)
{
    for(int i = 0 ; i < m ; i++)
    {
        avai[i] -= req[i];
        alloc[reqprocess][i] += req[i]; // 新增：更新已分配矩阵
        need[reqprocess][i] -= req[i];
    }
}

2. 安全检测循环的逻辑优化

原代码中finish[i] = 1被放在资源累加循环内，虽不影响结果但冗余；同时找到可执行进程后未跳出内层循环，会导致同一轮检查中重复判断其他进程。优化后的安全检测逻辑更清晰：

for(int k = 0 ; k < n ; k++)
{
    int found = 0;
    for(int i = 0 ; i < n ; i++)
    {
        if(finish[i] == 0)
        {
            int flag = 0;
            for(int j = 0 ; j < m ; j++)
            {
                if(need[i][j] > work[j])
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0)
            {
                printf("i : %d ",i);
                safeSequence[ind++] = i;
                // 累加资源，标记进程完成
                for(int y = 0 ; y < m ; y++)
                {
                    work[y] += alloc[i][y];
                }
                finish[i] = 1;
                found = 1;
                break; // 找到一个进程后，重新从第一个进程开始检查
            }
        }
    }
    if(!found) break; // 本轮无可用进程，提前退出
}

3. 其他小问题修复

修正拼写错误：printf("\MAXIMUM MATRIX\n\n");改为printf("\nMAXIMUM MATRIX\n\n");
修正拼写错误：printf("New Avaialable : ");改为printf("New Available : ");

修复后效果

修复完成后，程序会正确计算安全序列，输出与预期完全一致。

内容的提问来源于stack exchange，提问作者Ashique

含请求功能的Banker's Algorithm程序误报死锁，求助调试

预期输出 #

实际输出 #

完整代码 #

问题原因及修复方案 #

1. 核心错误：未更新Allocation矩阵 #

2. 安全检测循环的逻辑优化 #

3. 其他小问题修复 #

修复后效果 #