C语言模拟银行家算法

全栈程序员站长

发布于 2022-09-15 15:51:50

1.6K0

发布于 2022-09-15 15:51:50

文章被收录于专栏：全栈程序员必看

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

银行家算法需求:

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

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

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

C代码实现:

头文件的导入和预定义

#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 *

结构体和枚举的创建

/*创建资源名枚举类型*/
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;
};

进程阻塞函数

/* 循环等待信号量 */
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--;
}

释放信号量函数

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

申请资源函数

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;
}

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;
}