操作系统银行家算法C语言实现

文章目录

算法简介

银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

算法目的

为了了解系统的资源分配情况，假定系统的任何一种资源在任意时刻只能被一个进程使用，任何进程已经占用的资源只能由进程自己释放，而不能由其他进程抢占，当进程申请的资源不能满足时，必须等待。因此只要资源分配算法能保证进程的资源请求，且不出现循环等待，则系统不会出现死锁。

算法原理

在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。

银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。

(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：

AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];

NEED[cusneed][i]-=REQUEST[cusneed][i];

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

安全性检查算法

（1）设置两个工作向量Work=AVAILABLE;FINISH
（2）从进程集合中找到一个满足下述条件的进程，

FINISH==false;

NEED<=Work;

如找到，执行（3)；否则，执行（4)

(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work=Work+ALLOCATION;

Finish=true;

GOTO 2

算法流程图

算法C语言实现版本1

#include<stdio.h>
#define true 1
#define false 0
#define processNum 5
#define resourceNum 3
#define MAXINT 9999
typedef int bool;

int available[resourceNum]={3,3,2};
int maxRequest[processNum][resourceNum]={7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};
int allocation[processNum][resourceNum]={0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};
int need[processNum][resourceNum]={7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};
bool Finish[processNum];
int safeSeries[processNum]={MAXINT, MAXINT , MAXINT , MAXINT , MAXINT};
int request[resourceNum];

void Init()
{
    int i, j;
    printf("输入进程数量、资源数量\n");
    //scanf("%d %d",&processNum,&resourceNum);
    printf("输入当前资源可用数目\n");
    for(i = 0; i < resourceNum; i++){
        scanf("%d",&available[i]);
    }
    printf("输入最大需求矩阵\n");
    for(i = 0; i < processNum; i++){
        for(j = 0; j < resourceNum; j++){
            scanf("%d",&maxRequest[i][j]);
        }
    }
    printf("输入分配矩阵\n");
    for(i = 0; i < processNum; i++){
        for(j = 0; j < resourceNum; j++){
            scanf("%d",&allocation[i][j]);
        }
    }
    printf("输入当前需求矩阵\n");
    for(i = 0; i < processNum; i++){
        for(j = 0; j < resourceNum; j++){
            scanf("%d",&need[i][j]);
        }
    }
}

void showInfo()
{
    int i,j;
    printf("当前资源剩余：");
    for(j = 0; j < resourceNum; j++){
        printf("%d ",available[j]);
    }
    printf("\n");
    printf(" PID\t Max\t\tAllocation\tNeed\n");
    for(i = 0; i < processNum; i++){
        printf(" P%d\t",i);
        for(j = 0; j < resourceNum; j++){
            printf("%d ",maxRequest[i][j]);
        }
        printf("\t\t");
        for(j = 0; j < resourceNum; j++){
            printf("%d ",allocation[i][j]);
        }
        printf("\t\t");
        for(j = 0; j < resourceNum; j++){
            printf("%d ",need[i][j]);
        }
        printf("\n");
    }
}

bool isSafe()
{
    int i,j,k;
    int trueFinished = 0;
    int work[resourceNum];
    for(i = 0; i < resourceNum; i++){
        work[i]=available[i];
    }

    for(i = 0; i < processNum; i++){
        Finish[i]=false;
    }
    i = 0;
    int temp = 0;
    while(trueFinished != processNum){
        int j =0;
        if(Finish[i]!= true){
            for(j = 0; j < resourceNum; j++){
                if(need[i][j] > work[j]){break;}
            }
        }
        if(j == resourceNum){
            Finish[i]=true;
            SafeInfo(work,i);
            for(k = 0; k < resourceNum; k++){
                work[k]+=allocation[i][k];
            }
            int k2;
            safeSeries[trueFinished++] = i;
        }
        i++;
        if(i >= processNum)
        {
            i = i % processNum;
            if(temp == trueFinished)
                break;
        }
        temp = trueFinished;
    }

    if(trueFinished == processNum){
        printf("\n系统安全！\n\n安全序列为：");
        for(i = 0; i < processNum; i++){
            printf("%d ",safeSeries[i]);
        }
        return true;
    }
    printf("******系统不安全！******\n");
    return false;
}

void SafeInfo(int *work, int i)
{
    int j;
    printf(" P%d\t",i);
    for(j = 0; j < resourceNum; j++){
        printf("%d ",work[j]);
    }
    printf("\t\t");
    for(j = 0; j < resourceNum; j++){
        printf("%d ",need[i][j]);
    }
    printf("\t ");
    for(j = 0; j < resourceNum; j++){
        printf("%d ",allocation[i][j]);
    }
    printf("\t\t");
    for(j = 0; j < resourceNum; j++){
        printf("%d ",allocation[i][j]+work[j]);
    }
    printf("\n");
}


int main()
{
    int i,j,curProcess;
    int wheInit = 0;
    printf("是否使用内置数据？0是，1否：");
    scanf("%d",&wheInit);
    if(wheInit)
        Init();  //可以不使用，选用内置的数据进行测试
    printf("---------------------------------------------------------\n");
    showInfo();
    printf("\n系统安全情况分析\n");
    printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");
    isSafe();
    while(true){
        printf("\n---------------------------------------------------------\n");
        printf("\n输入要分配的进程：");
        scanf("%d",&curProcess);
        printf("\n输入要分配给进程P%d的资源：",curProcess);
        for(j = 0; j < resourceNum; j++){
            scanf("%d", &request[j]);
        }
        for(j = 0; j < resourceNum; j++){
            if(request[j] <= need[curProcess][j])continue;
            else{printf("ERROR！\n");break;}
        }
        if(j == resourceNum){
            for(j = 0; j < resourceNum; j++){
                if(request[j] <= need[curProcess][j])continue;
                else{printf("资源不足，等待中！\n");break;}
            }
            if(j == resourceNum){
                for(j = 0; j < resourceNum; j++){
                    available[j] -= request[j];
                    allocation[curProcess][j] += request[j];
                    need[curProcess][j] -= request[j];
                }
                printf("\n系统安全情况分析\n");
                printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");
                if(isSafe()){
                    printf("分配成功！\n");
                    showInfo();
                }else{
                    for(j = 0; j < resourceNum; j++){
                        available[j] += request[j];
                        allocation[curProcess][j] -= request[j];
                        need[curProcess][j] += request[j];
                    }
                    printf("分配失败！\n");
                    showInfo();
                }
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

#include<stdio.h>

#define true 1

#define false 0

#define processNum 5

#define resourceNum 3

#define MAXINT 9999

typedef int bool;

int available[resourceNum]={3,3,2};

int maxRequest[processNum][resourceNum]={7,5,3,3,2,2,9,0,2,2,2,2,4,3,3};

int allocation[processNum][resourceNum]={0,1,0,2,0,0,3,0,2,2,1,1,0,0,2};

int need[processNum][resourceNum]={7,4,3,1,2,2,6,0,0,0,1,1,4,3,1};

bool Finish[processNum];

int safeSeries[processNum]={MAXINT, MAXINT , MAXINT , MAXINT , MAXINT};

int request[resourceNum];

void Init()

{

int i, j;

printf("输入进程数量、资源数量\n");

//scanf("%d %d",&processNum,&resourceNum);

printf("输入当前资源可用数目\n");

for(i = 0; i < resourceNum; i++){

scanf("%d",&available[i]);

}

printf("输入最大需求矩阵\n");

for(i = 0; i < processNum; i++){

for(j = 0; j < resourceNum; j++){

scanf("%d",&maxRequest[i][j]);

}

printf("输入分配矩阵\n");

for(i = 0; i < processNum; i++){

for(j = 0; j < resourceNum; j++){

scanf("%d",&allocation[i][j]);

}

printf("输入当前需求矩阵\n");

for(i = 0; i < processNum; i++){

for(j = 0; j < resourceNum; j++){

scanf("%d",&need[i][j]);

}

void showInfo()

{

int i,j;

printf("当前资源剩余：");

for(j = 0; j < resourceNum; j++){

printf("%d ",available[j]);

}

printf("\n");

printf(" PID\t Max\t\tAllocation\tNeed\n");

for(i = 0; i < processNum; i++){

printf(" P%d\t",i);

for(j = 0; j < resourceNum; j++){

printf("%d ",maxRequest[i][j]);

}

printf("\t\t");

for(j = 0; j < resourceNum; j++){

printf("%d ",allocation[i][j]);

}

printf("\t\t");

for(j = 0; j < resourceNum; j++){

printf("%d ",need[i][j]);

}

printf("\n");

}

bool isSafe()

{

int i,j,k;

int trueFinished = 0;

int work[resourceNum];

for(i = 0; i < resourceNum; i++){

work[i]=available[i];

}

for(i = 0; i < processNum; i++){

Finish[i]=false;

}

i = 0;

int temp = 0;

while(trueFinished != processNum){

int j =0;

if(Finish[i]!= true){

for(j = 0; j < resourceNum; j++){

if(need[i][j] > work[j]){break;}

}

if(j == resourceNum){

Finish[i]=true;

SafeInfo(work,i);

for(k = 0; k < resourceNum; k++){

work[k]+=allocation[i][k];

}

int k2;

safeSeries[trueFinished++] = i;

}

i++;

if(i >= processNum)

{

i = i % processNum;

if(temp == trueFinished)

break;

}

temp = trueFinished;

}

if(trueFinished == processNum){

printf("\n系统安全！\n\n安全序列为：");

for(i = 0; i < processNum; i++){

printf("%d ",safeSeries[i]);

}

return true;

}

printf("******系统不安全！******\n");

return false;

}

void SafeInfo(int *work, int i)

{

int j;

printf(" P%d\t",i);

for(j = 0; j < resourceNum; j++){

printf("%d ",work[j]);

}

printf("\t\t");

for(j = 0; j < resourceNum; j++){

printf("%d ",need[i][j]);

}

printf("\t ");

for(j = 0; j < resourceNum; j++){

printf("%d ",allocation[i][j]);

}

printf("\t\t");

for(j = 0; j < resourceNum; j++){

printf("%d ",allocation[i][j]+work[j]);

}

printf("\n");

}

int main()

{

int i,j,curProcess;

int wheInit = 0;

printf("是否使用内置数据？0是，1否：");

scanf("%d",&wheInit);

if(wheInit)

Init(); //可以不使用，选用内置的数据进行测试

printf("---------------------------------------------------------\n");

showInfo();

printf("\n系统安全情况分析\n");

printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");

isSafe();

while(true){

printf("\n---------------------------------------------------------\n");

printf("\n输入要分配的进程：");

scanf("%d",&curProcess);

printf("\n输入要分配给进程P%d的资源：",curProcess);

for(j = 0; j < resourceNum; j++){

scanf("%d", &request[j]);

}

for(j = 0; j < resourceNum; j++){

if(request[j] <= need[curProcess][j])continue;

else{printf("ERROR！\n");break;}

}

if(j == resourceNum){

for(j = 0; j < resourceNum; j++){

if(request[j] <= need[curProcess][j])continue;

else{printf("资源不足，等待中！\n");break;}

}

if(j == resourceNum){

for(j = 0; j < resourceNum; j++){

available[j] -= request[j];

allocation[curProcess][j] += request[j];

need[curProcess][j] -= request[j];

}

printf("\n系统安全情况分析\n");

printf(" PID\t Work\t\tNeed\tAllocation\tWork+Allocation\n");

if(isSafe()){

printf("分配成功！\n");

showInfo();

}else{

for(j = 0; j < resourceNum; j++){

available[j] += request[j];

allocation[curProcess][j] -= request[j];

need[curProcess][j] += request[j];

}

printf("分配失败！\n");

showInfo();

}

实现效果

安全性检查

分配资源与安全性检查

网站所有原创代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权

操作系统银行家算法C语言实现

文章目录

算法简介

算法目的

算法原理

算法流程图

算法C语言实现版本1

实现效果

大模型AlpacaFarm分析

NLG文本评估任务或许并不需要真值或参考文本

大模型中的RepE表征工程

大模型也是一种优化器（LLM as Optimizer）

全栈开发与快速部署Demo

学术idea自动发现与生成

自回归语言模型（language model）Python实现

粉丝期待的三体电影宇宙（近四十部电影与电视剧集）

基于历史对比学习的时序知识图谱推理

泰拉瑞亚Terriaria快速部署Linux服务器

留下评论取消回复

文章目录

算法简介

算法目的

算法原理

算法流程图

算法C语言实现版本1

实现效果

相关文章

留下评论取消回复