C语言模拟银行家算法

大家好，又见面了，我是你们的朋友全栈君。

银行家算法需求:

1. 一个程序对资源的最大需求量不超过系统的最大资源
2. 程序可以分多次申请资源,但是申请资源的总量不能超过最大需求量
3. 当系统现有资源不能满足程序的需求时,可以推迟分配资源,但是总能满足程序对资源的需求
4. 当程序获得了全部的资源后,要在有限的时间内归还资源

系统的安全/不安全状态:

在程序申请资源时,当系统的拥有的资源不能满足程序剩余所需的全部资源时,则处于不安全状态

C代码实现:

1. 头文件的导入和预定义

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>

#define RESOURCES_MAX 5//系统拥有5种资源
#define u32 unsigned int
#define u8 char
#define TRUE 1
#define FALSE 0
#define programs_t struct programs *
#define critical_resources_t struct critical_resources *

2. 结构体和枚举的创建

/*创建资源名枚举类型*/
enum Resources
{ 
   
	resource1 , resource2 , resource3 , resource4 , resource5
};

/* 父进程和子进程的共享资源 system_possess_resouces 临界资源 系统剩余的资源数量 wait_visit_number 判断有多少个进程在等待访问临界资源 wait_get_number 判断有多少个进程在等待资源的分配，等待数量等于总进程数时代表出现死锁 all_programs_size 总进程数量 sinal_number 信号量 program_set_up 当前进程的数量 max_programs 存储最大进程数(当n个进程都初始化完毕后才接着往下运行) sleep_time 每个子进程创建出来后都会通过休眠来和其他子进程错开cpu时间避免随机数相同 */
struct critical_resources
{ 
   
		u32 system_possess_resources[RESOURCES_MAX];
		u8  wait_visit_number;
		u8  wait_get_number;
		u8	all_programs_size;
		u8  signal_number; 
		u8  program_set_up;
		u8  max_programs;
		u8  sleep_time;
};

/* 进程需求结构体 max_resources 进程需要的全部资源 get_resources 进程获取的资源数量 need_resources 进程需要的资源数量 random_next_resources 进程这次要申请多少资源,利用随机数来确定 program_number 进程号 judge_success_get_resources 判断是否成功分配到了资源,是则random_next_resources清空 */ 
struct programs 
{ 
   
	u32 max_resources[RESOURCES_MAX];
	u32 get_resources[RESOURCES_MAX];
	u32 need_resources[RESOURCES_MAX];
    u32 random_next_resources[RESOURCES_MAX];
    pid_t  program_number;
    u8  judge_success_get_resources;
};

3. 进程阻塞函数

/* 循环等待信号量 */
void program_wait(critical_resources_t crts)
{ 
   
	if(crts->signal_number <= 0)
	{ 
    
		crts->wait_visit_number++;//等待进程数量+1
	    while(TRUE)
	    { 
   
	        if(crts->signal_number > 0)//如果信号量可用则跳出
	            break;
	    }
	}	
    crts->signal_number--;//信号量-1
    crts->wait_visit_number--;
}

4. 释放信号量函数

void release_signal(critical_resources_t crts)
{ 
   
	crts->signal_number++;
}

5. 申请资源函数

u8 request_resources(critical_resources_t crts , programs_t prg)
{ 

/*如果为TRUE则代表上一次的资源申请已经分配完毕, 可以再进行新的信号量个数申请, 如果为FALSE则代表上一次的资源申请系统并没有满足, 接着进行上一次的申请*/
if(TRUE == prg->judge_success_get_resources)
{ 

for(int i = 0 ; i < RESOURCES_MAX ; i++)
{ 

if(0 == prg->need_resources[i])
{ 

printf("%d need resource%d zero:\n" ,prg->program_number, i + 1);
prg->random_next_resources[i] = 0;
continue;
}
prg->random_next_resources[i] = (random()%prg->need_resources[i] + 1);
printf("%d random request resource%d size:%d \n" ,prg->program_number, i + 1 , prg->random_next_resources[i]);
//usleep(1000);
}
}
/* 对系统安全性进行判断,如果分配资源后系统处于不安全状态则不给予分配 */
if( prg->need_resources[resource1] <= crts->system_possess_resources[resource1]
&& prg->need_resources[resource2] <= crts->system_possess_resources[resource2]
&& prg->need_resources[resource3] <= crts->system_possess_resources[resource3]
&& prg->need_resources[resource4] <= crts->system_possess_resources[resource4]
&& prg->need_resources[resource5] <= crts->system_possess_resources[resource5])
{ 

for(int i = 0 ; i < RESOURCES_MAX ;i++)
{ 

crts->system_possess_resources[i] -= prg->random_next_resources[i];
prg->need_resources[i] -= prg->random_next_resources[i];
prg->get_resources[i] += prg->random_next_resources[i];
}
bzero(prg->random_next_resources,sizeof(prg->random_next_resources));
}
else
{ 

printf("System resources not suffice satisfy %d operation\n" , prg->program_number);
return FALSE;
}
return TRUE;
}

6. main主函数体

int main(int argc , char ** argv)
{ 

if(argc < 2)
{ 

perror("parameter error");
exit(1);
}
//使用mmap的文件映射来实现父进程和子进程的共享内存,因为进程之间有从属关系,所以在fd处只需要传入-1
critical_resources_t crt = (critical_resources_t)mmap(NULL , sizeof(struct critical_resources) , PROT_READ | PROT_WRITE , MAP_ANON | MAP_SHARED , -1 , 0); 
//共享内存的初始化
for(int i = 0 ; i < RESOURCES_MAX ; i++)
crt->system_possess_resources[i] = 10;	
crt->wait_visit_number = 0;
crt->wait_get_number = 0;
crt->all_programs_size = atoi(argv[1]);
crt->signal_number = 1; 
crt->program_set_up = 0;
crt->sleep_time = 1;
crt->max_programs = 0;
pid_t pid;
//循环创建进程
for(int i = 0 ; i < atoi(argv[1]) ; ++i)
{ 

if(0 == (pid = fork()))
break;
}
if(pid > 0)
{ 

//父进程循环等待子进程的结束
while(TRUE)
{ 

if(atoi(argv[1]) == crt->program_set_up)
{ 

crt->program_set_up = 0;	
}
if(0 == crt->all_programs_size)
break;
wait(NULL);
}
printf("all programs operation end..\n");
}
else
{ 

sleep(crt->sleep_time++);	
//随机数种子
srand((unsigned)time(NULL));
//创建进程资源需求结构体
struct programs prm;
//初始化进程需求结构体
bzero(prm.get_resources , sizeof(prm.get_resources));
bzero(prm.need_resources , sizeof(prm.need_resources));
bzero(prm.random_next_resources , sizeof(prm.random_next_resources));
prm.program_number = getpid();
prm.judge_success_get_resources = TRUE;
printf("program %d set up success\n" , prm.program_number);
//进程数量+1
crt->program_set_up++;
//循环随机生成进程需要的最大资源
for(int i  = 0 ; i < RESOURCES_MAX ; i++) 
{ 

prm.max_resources[i] = (rand()%10 + 1);
prm.need_resources[i] = prm.max_resources[i];
}
//printf("%d max need resources : %d , %d , %d , %d , %d" , prm.program_number , prm.max_resources[resource1] , prm.max_resources[resource2] , prm.max_resources[resource3] , prm.max_resources[resource4]);
printf("%d max need resources : " , prm.program_number);
for(int i = 0 ; i < RESOURCES_MAX ; i++)
{ 

printf("%d " , prm.max_resources[i]);
}
printf("\n");
while(TRUE)//运行到这里开始阻塞等待所有子进程都初始化完毕再接着运行
{ 

if(crt->max_programs == atoi(argv[1]))
break;
}
while(TRUE)
{ 

//阻塞等待信号量
program_wait(crt);
//申请资源
if(TRUE == (prm.judge_success_get_resources = request_resources(crt,&prm)))
bzero(prm.random_next_resources,sizeof(prm.random_next_resources));
else
usleep(1000);
//判断是否用完所有的资源
if(0 == prm.need_resources[resource1] && 
0 == prm.need_resources[resource2] &&
0 == prm.need_resources[resource3] &&
0 == prm.need_resources[resource4] &&
0 == prm.need_resources[resource5])
{ 

printf("\n%d operantion end..." , prm.program_number);
for(int i = 0 ; i < RESOURCES_MAX ; i++)//归还系统的资源
crt->system_possess_resources[i] += prm.max_resources[i];
crt->all_programs_size--;//运行进程数-1
release_signal(crt);//释放信号量
break;//跳出循环
}
release_signal(crt);
}
}
return 0;
}

这是之前的一个操作系统作业,本来还希望实现打印进程资源需求表,但是似乎需要再创建一个共享内存进行链表操作,比较懒就没有实现

在打印过程中是否存在一个进程还未打印结束出现另一个进程抢占打印造成两个进程的输出内容错乱的风险?