[算法]操作系统进程通信(预防死锁)算法 Dijkstra银行家算法 C语言实现

今天完成昨天的算法，银行家算法，这个大家如果知道操作系统这门课程的话应该会明白，昨天一直忙于复习，今天也是，不过下午还是完成了基本调试，调试环境GCC和TC，现在我把代码奉献给大家 银行家算法说明：最早由算法大师 迪杰克斯拉 (Edsger Dijkstra) 提出，银行家算法，顾名思义，它的原理来源于银行系统的存贷款发放管理，即银行（系统）要将一定的款项（资源）贷款（分配）给N个人（进程），当然不需要考虑信用问题< _>，在已经发放了一定的金额后，要使得银行的每一次放款（分配资源）都能使得银行（系统）的运行安全（预防死锁）（可以这么理解吧），因此银行家要对现有的资金进行合理分配发放，基本要求要银行必须保留一定的存款不能低于一定的限度（临界资源），同时又不能不放贷款不然会让客户“饿死”（进程饥饿），客户在使用完贷款后要返还（释放）这笔贷款，当然是没有利息的，然后银行要再分配给客户，直到满足客户的多有贷款请求 具体可以参照http://baike.baidu.com/view/93075.htm 代码如下： /**银行家算法*code CG 2008 01 05*/#include"stdio.h"#define FALSE 0#define TRUE 1#define W 10#define R 20int M ; /*总进程数*/int N ; /*资源种类*/int ALL_RESOURCE[W];/*各种资源的数目总和*/int MAX[W][R]; /*M个进程对N类资源最大资源需求量*/int AVAILABLE[R]; /*系统可用资源数*/int ALLOCATION[W][R]; /*M个进程已经得到N类资源的资源量*/int NEED[W][R]; /*M个进程还需要N类资源的资源量*/int REQUEST[R]; /*请求资源个数*//**函数名：output*功能：输出资源分配情况*/void output(){ int i,j; printf("All Resource:n"); for(j = 0 ; j < N jbr> printf("R%d:%dn", j , ALL_RESOURCE[j]); printf("Resource Available:n"); for(j = 0 ; j < N jbr> printf("R%d:%dn", j , AVAILABLE[j]); printf("Process Resource Needed:n"); printf("| PID |"); for(j = 0 ; j < N jbr> printf(" R%d |", j); printf("n"); for(i = 0 ; i < M ibr> for(i = 0 ; i < M ibr> { printf("|%-5d|", i); for(j = 0 ; j < N jbr> printf("%-4d|", NEED[i][j]); printf("n"); } printf("Process Resource Allocated:n"); printf("| PID |"); for(j = 0 ; j < N jbr> printf(" R%d |", j); printf("n"); for(i = 0 ; i < M ibr> { printf("|%-5d|", i); for(j = 0 ; j < N jbr> printf("%-4d|", ALLOCATION[i][j]); printf("n"); }}/*output*//**函数名 ：modify*功能：改变可用资源和已经拿到资源和还需要的资源的值*参数：int k 修改编号为K的P的数据*/void modify(int k){ int j; for(j = 0 ; j < N jbr> AVAILABLE[j] = AVAILABLE[j] - REQUEST[j];/*修改可用资源*/ ALLOCATION[k][j] = ALLOCATION[k][j] + REQUEST[j];/*修改分配资源*/ NEED[k][j] = NEED[k][j] - REQUEST[j];/*修改资源需求*/ }}/**函数名：undo*功能：还原可用资源和已经拿到资源和还需要的资源的值*参数：参数：int k 修改编号为K的P的数据*/void undo(int k){ int j; for(j = 0 ; j < N jbr> AVAILABLE[j] = AVAILABLE[j] + REQUEST[j]; /*修改可用数据*/ ALLOCATION[k][j] = ALLOCATION[k][j] - REQUEST[j]; /*修改分配的资源*/ NEED[k][j] = NEED[k][j] + REQUEST[j];/*修改资源需求*/ }}/**函数名：chkerr*功能：检查修改操作是否安全*/int chkerr(int s){ int WORK , FINISH[W]; int i , j; for(i = 0 ; i < M iFINISHbr> FINISH[i] = FALSE; for(j = 0 ; j < N jbr> WORK = AVAILABLE[j]; i = s; do{ if(FINISH[i] == FALSE && NEED[i][j] < WORKbr> WORK = WORK + ALLOCATION[i][j]; FINISH[i] = TRUE; i = 0; } else i++; }while(i for(i = 0 ; i < M ibr> if(FINISH[i] == FALSE){ printf("Error : UnSafe Allocation!n"); return 1; } } printf("OK : Allocation OKn"); return 0; } /* *函数名：bank *功能 ：银行家算法的实现 */ void bank() { int i , j; int flag = TRUE; printf("Use Ctrl+C break..n"); while(TRUE){ i = -1; while(i < 0 i >= M) { printf("Input Process to Allocat PID="); scanf("%d", &i); if(i < 0 i >= M) printf("Error: Invalid Input!n"); } printf("Input Resource Needn"); for (j = 0 ; j < N jbr> { printf("R%d=", j); scanf("%d", &REQUEST[j]); if(REQUEST[j] > NEED[i][j]){/*请求的资源数大于请求资源*/ printf("Error: Invalid Input!n"); flag = FALSE; } else{ if(REQUEST[j]>AVAILABLE[j]){/*若请求的资源数大于可用资源数*/ printf("Error: Invalid Input!n"); flag = FALSE; } }/*else*/ }/*for*/ if(flag) { modify(i); /*修改资源数*/ if(chkerr(i)){/*安全?*/ undo(i); /*恢复资源数*/ output();/*输出*/ } else output(); /*输出*/ } else output(); }/*while*/ }/*bank*/ /*主函数*/ int main(){ int i , j , p; printf("Input Process Numbers M=");/*进程数量*/ scanf("%d", &M); printf("Input Resource Category N=");/*资源种类*/ scanf("%d", &N); printf("Input Number of All Resource each Category:n");/*资源数目*/ for(i = 0 ; i < N ibr> scanf("%d", &ALL_RESOURCE[i]); printf("Input Max Resource Process Need:n");/*最大资源需求*/ for (i = 0 ; i < M ibr> for (j = 0 ; j < N jbr> do{ scanf("%d", &MAX[i][j]); if (MAX[i][j] > ALL_RESOURCE[j])/*大于最大可用？*/ printf("nError: Invalid Input!n"); }while (MAX[i][j] > ALL_RESOURCE[j]); } }/*for*/ printf("Input Resource Process Allocated:n"); for (i = 0 ; i < M ibr> for (j = 0 ; j < N jbr> do{ scanf("%d", &ALLOCATION[i][j]); if (ALLOCATION[i][j] > MAX[i][j])/*大于最大需求？*/ printf("nError: Invalid Input!n"); }while (ALLOCATION[i][j] > MAX[i][j]); } }/*for*/ for(j = 0 ; j < N jbr> p = ALL_RESOURCE[j]; for(i = 0 ; i < M ibr> p -= ALLOCATION[i][j];/*减去已经分配资源*/ AVAILABLE[j] = p; if(AVAILABLE[j]<0) AVAILABLE[j] = 0;/*清理数据*/ }/*for*/ }/*for*/ for (i = 0 ; i < M ibr> for(j = 0 ; j < N jbr> NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];/*求还需要的资源*/ output(); bank();/*银行家算法*/ return 0; }/*main*/ -------------------------------------------------------------------------------------- - 版权声明： - 如在本页面内无特别说明，本文内容均为[李大仁博客]原创，本文版权归[李大仁博客]所有。 - 欢迎转载，转载请务必在文章页面明显位置提供原文链接并注明出处。欢迎您在转载本文时保留本段声明。 - 文章标题： [算法]操作系统进程调度与通信算法 Dijkstra银行家算法 C语言实现 - 独立博客： 李大仁博客 - 永久链接：http://www.lidaren.com/archives/287 -------------------------------------------------------------------------------------- 以上内容由博客自动发布工具自动发布，最终显示内容和效果会与原文内容有所偏差，敬请谅解。