银行家算法 c++版
发布网友
发布时间：2023-10-29 13:24
共1个回答
热心网友
时间：2024-11-15 13:34
#include <stdio.h>
#include <conio.h>
typedef struct Available
{
int Avai_Num;
struct Available *next;
}Available; /* 系统当前可用资源,使用链表实现 */
Available *Creat_Available(int R_Num) /* R_Num资源的数目 */
{
int i;
struct Available *p, *q, *head;
q = malloc(sizeof(struct Available));
head = q;
p = q;
printf("Please input Available resource of current systme\n");
for(i = 0; i < R_Num; i++)
{
q = malloc(sizeof(struct Available));
p->next = q;
p = q;
scanf("%d",&p->Avai_Num);
}
p = head;
for(i = 0; i < R_Num; i++)
{
p = p->next;
printf("R[%d]= %d\n",i, p->Avai_Num);
}
return head;
} /* 生成系统当前可用资源链表 */
void free_Available(struct Available *head, int R_Num)
{
struct Available *p, *q;
int i;
q = head;
p = q;
q = q->next;
for(i = 0; i <= R_Num; i++)
{
free(p);
p = q;
q = q->next;
}
}
typedef struct Allocation
{
int Allo_Num;
struct Allocation *next;
}Allocation; /* 进程已分配资源 */
Allocation *Creat_Allocation(int P_Num,int n)
{
int i;
struct Allocation *p, *q, *head;
q = malloc(sizeof(struct Allocation));
head = q;
p = q;
printf("Please input Allocation of P%d\n", P_Num);
for(i = 0; i < n; i++)
{
q = malloc(sizeof(struct Allocation));
p->next = q;
p = q;
scanf("%d",&p->Allo_Num);
}
p = head;
for(i = 0; i < n; i++)
{
p = p->next;
printf("R[%d]= %d\n",i, p->Allo_Num);
}
return head;
} /* 生成进程已分配资源链表 */
void free_Allocation(struct Allocation *head, int R_Num)
{
struct Allocation *p, *q;
int i;
q = head;
p = q;
q = q->next;
for(i = 0; i <= R_Num; i++)
{
free(p);
p = q;
q = q->next;
}
}
typedef struct Max
{
int Max_Num;
struct Max *next;
}Max; /* 进程最大资源 */
Max *Creat_Max(int P_Num,int n)
{
int i;
struct Max *p, *q, *head;
q = malloc(sizeof(struct Max));
head = q;
p = q;
printf("Please input Max of P%d\n", P_Num);
for(i = 0; i < n; i++)
{
q = malloc(sizeof(struct Max));
p->next = q;
p = q;
scanf("%d",&p->Max_Num);
}
p = head;
for(i = 0; i < n; i++)
{
p = p->next;
printf("R[%d]= %d\n",i, p->Max_Num);
}
return head;
} /* 生成进程最大资源链表 */
void free_Max(struct Max *head, int R_Num)
{
struct Max *p, *q;
int i;
q = head;
p = q;
q = q->next;
for(i = 0; i <= R_Num; i++)
{
free(p);
p = q;
q = q->next;
}
}
typedef struct Need
{
int Need_Num;
struct Need *next;
}Need; /* 进程运行结束还需资源 */
Need *Creat_Need(struct Max *M_Head, struct Allocation *A_Head,int P_Num,int
n)
{
int i;
struct Need *p, *q, *head;
struct Max *Max_Temp;
struct Allocation *Allo_Temp;
Max_Temp = M_Head;
Allo_Temp = A_Head;
q = malloc(sizeof(struct Need));
head = q;
p = q;
for(i = 0; i < n; i++)
{
Max_Temp = Max_Temp->next;
Allo_Temp = Allo_Temp->next;
q = malloc(sizeof(struct Need));
p->next = q;
p = q;
p->Need_Num = Max_Temp->Max_Num - Allo_Temp->Allo_Num;
}
p = head;
for(i = 0; i < n; i++)
{
p = p->next;
printf("P_Need R[%d]= %d\n",i, p->Need_Num);
}
return head;
} /* 生成进程运行结束还需资源链表 */
void free_Need(struct Need *head, int R_Num)
{
struct Need *p, *q;
int i;
q = head;
p = q;
q = q->next;
for(i = 0; i <= R_Num; i++)
{
free(p);
p = q;
q = q->next;
}
}
typedef struct Resource
{
struct Allocation *Allo_R;
struct Max *Max_R;
struct Need *Need_R;
struct Resource *next;
int Finish;
}Resource;
Resource *Creat_Resource(int P_Num, int R_Num)
{
int i;
struct Resource *p, *q, *head;
q = malloc(sizeof(struct Resource));
head = q;
p = q;
printf("Creat initial state of Resource \n");
for(i = 0; i < P_Num; i++)
{
q = malloc(sizeof(struct Resource));
p->next = q;
p = q;
p->Allo_R = Creat_Allocation(i,R_Num);
p->Max_R = Creat_Max(i, R_Num);
p->Need_R = Creat_Need( p->Max_R,p->Allo_R, P_Num, R_Num);
p->Finish = 0;
}
p = head;
return head;
} /* 进程资源状况 */
void free_Resource(struct Resource *head, int R_Num)
{
struct Resource *p, *q;
int i;
q = head;
p = q;
q = q->next;
for(i = 0; i <= R_Num; i++)
{
free(p);
p = q;
q = q->next;
}
}
void free_memory(struct Resource *Resource_head, struct Available
*Available_head, int P_Num, int R_Num)
{
struct Resource *p, *q;
int i;
q = Resource_head;
p = q;
q = q->next;
for(i = 0; i <= P_Num; i++)
{
p = q;
q = q->next;
free_Need(p->Need_R, R_Num);
free_Max(p->Max_R, R_Num);
free_Allocation(p->Allo_R, R_Num);
}
q = Resource_head;
p = q;
free_Resource(p, R_Num);
free_Available(Available_head, R_Num);
}
int compair(struct Resource *Compair_Process, struct Available
*Available_Head, int R_Num)
/*比较当前的资源是否能满足进程q的运行，如可以返回1*/
{
struct Need *Current_Resource_Needed;
struct Available *Temp_Available_Resource;
int i;
int temp;
Current_Resource_Needed = Compair_Process->Need_R;
Temp_Available_Resource = Available_Head;
temp = 1;
for(i = 0; i < R_Num; i++)
{
Current_Resource_Needed = Current_Resource_Needed->next;
Temp_Available_Resource = Temp_Available_Resource->next;
temp = temp && (Current_Resource_Needed->Need_Num <=
Temp_Available_Resource->Avai_Num ? 1 : 0);
}
return temp;
}
void change_available(struct Resource *Compair_Process, struct Available
*Available_Head, int R_Num)
{ /*修改进程执行后的系统可用资源表*/
struct Allocation *Current_Resource_Allocated;
struct Available *Temp_Available_Resource;
int i;
Current_Resource_Allocated = Compair_Process->Allo_R;
Temp_Available_Resource = Available_Head;
for(i = 0; i < R_Num; i++)
{
Current_Resource_Allocated = Current_Resource_Allocated->next;
Temp_Available_Resource = Temp_Available_Resource->next;
Temp_Available_Resource->Avai_Num = Current_Resource_Allocated-
>Allo_Num + Temp_Available_Resource->Avai_Num;
}
}
void print_available(struct Available *Available_Head, int R_Num)
{ /*输出系统可用资源表*/
struct Available *Temp_Available_Resource;
int i;
Temp_Available_Resource = Available_Head;
for(i = 0; i < R_Num; i++)
{
Temp_Available_Resource = Temp_Available_Resource->next;
printf("Available_R%d = %d\n", i, Temp_Available_Resource->Avai_Num);
}
}
void Safty_judgement(struct Resource *head, struct Available *Available_Head,
int R_Num)
{ /*系统安全性判断*/
struct Resource *p, *q;
int Safty;
int one_can_finish;
one_can_finish = 1;
printf("\n\n");
while(one_can_finish)
{ /*当这一次执行没有一个进程可以完成，时
退出*/
p = head;
p = p->next;
one_can_finish = 0;
while(p)
{ /*进行一遍搜索*/
if(p->Finish == 1)
p = p->next;
else if(compair(p,Available_Head,R_Num) == 1)
{
change_available(p,Available_Head,R_Num);
p->Finish = 1;
one_can_finish = 1; /*如果有一个进程能完成，那么标识
one_can_finish为1*/
p = p->next;
}
else p = p->next;
}
}
p = head;
p = p->next;
Safty = 1; /*假定当前状态是安全的*/
while(p)
{
if( p->Finish == 0)
Safty = 0; /*如果有一个进程不能完成，那么把状态置
为不安全*/
p = p->next;
}
if(Safty)
printf("The State is safety!");
else
printf("Can not allocate the resource!");
}
main()
{
struct Resource *Process_Head;
struct Available *Available_Head;
int P_Num, R_Num, i;
printf("\n");
printf("Please input Process_Number ");
scanf("%d",&P_Num);
printf("\n");
printf("Please input Resource_Number ");
scanf("%d", &R_Num);
Available_Head = Creat_Available(R_Num);
Process_Head = Creat_Resource(P_Num,R_Num);
Safty_judgement(Process_Head, Available_Head, R_Num);
free_memory(Process_Head, Available_Head, P_Num, R_Num);
getch();
}
