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

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

今天完成昨天的算法,银行家算法,这个大家如果知道操作系统这门课程的话应该会明白,昨天一直忙于复习,今天也是,不过下午还是完成了基本调试,调试环境GCC和TC,现在我把代码奉献给大家

银行家算法说明:最早由算法大师 迪杰克斯拉 (Edsger Dijkstra) 提出,银行家算法,顾名思义,它的原理来源于银行系统的存贷款发放管理,即银行(系统)要将一定的款项(资源)贷款(分配)给N个人(进程),当然不需要考虑信用问题< '_'>,在已经发放了一定的金额后,要使得银行的每一次放款(分配资源)都能使得银行(系统)的运行安全(预防死锁)(可以这么理解吧),因此银行家要对现有的资金进行合理分配发放,基本要求要银行必须保留一定的存款不能低于一定的限度(临界资源),同时又不能不放贷款不然会让客户“饿死”(进程饥饿),客户在使用完贷款后要返还(释放)这笔贷款,当然是没有利息的,然后银行要再分配给客户,直到满足客户的多有贷款请求


具体可以参照http://baike.baidu.com/view/93075.htm

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
/*
*银行家算法
*code CG 2008 01 05
*/
 
#include"stdio.h"
 
#define FALSE 0
#define TRUE 1
#define W 10
#define R 20
int 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 ;j++)
		printf("R%d:%dn", j , ALL_RESOURCE[j]);
 
	printf("Resource Available:n");
	for(j = 0 ; j < N ; j++)
		printf("R%d:%dn", j , AVAILABLE[j]);
 
	printf("Process Resource Needed:n");
 
	printf("| PID |");
	for(j = 0 ; j < N ; j++)
		printf(" R%d |", j);
	printf("n");
 
	for(i = 0 ; i < M ; i++)
		for(i = 0 ; i < M ; i++)
		{
			printf("|%-5d|", i);
				for(j = 0 ; j < N ; j++)
					printf("%-4d|", NEED[i][j]);
			printf("n");
	}
 
	printf("Process Resource Allocated:n");
 
	printf("| PID |");
	for(j = 0 ; j < N ; j++)
		printf(" R%d |", j);
	printf("n");
 
	for(i = 0 ; i < M ; i++)
	{
	 printf("|%-5d|", i);
		for(j = 0 ; j < N ; j++)
			printf("%-4d|", ALLOCATION[i][j]);
	 printf("n");
	}
}/*output*/
 
/*
*函数名 :modify
*功能:改变可用资源和已经拿到资源和还需要的资源的值
*参数:int k 修改编号为K的P的数据
*/
void modify(int k)
{
	int j;
	for(j = 0 ; j < N ; j++){/*修改数据*/
	 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 ; j++){/*修改数据*/
	 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 ; i++)/*清空FINISH*/
		FINISH[i] = FALSE;
	for(j = 0 ; j < N ; j++){/*逐一检查*/
		WORK = AVAILABLE[j];
		i = s;
		do{
			if(FINISH[i] == FALSE && NEED[i][j] <= WORK){/*符合条件?*/
					WORK = WORK + ALLOCATION[i][j];
				FINISH[i] = TRUE;
				i = 0;
			}
			else
				i++;
		}while(i<m);
 
		for(i = 0 ; i < M ; i++)/*只要一个不满足,不安全*/
			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 ; j++)
		 {
			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 ; i++)
		scanf("%d", &ALL_RESOURCE[i]);
	printf("Input Max Resource Process Need:n");/*最大资源需求*/
	for (i = 0 ; i < M ; i++){
		for (j = 0 ; j < N ; j++){
		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 ; i++){
		for (j = 0 ; j < N ; j++){
			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 ; j++){
		p = ALL_RESOURCE[j];
		for(i = 0 ; i < M ; i++){
			p -= ALLOCATION[i][j];/*减去已经分配资源*/
			AVAILABLE[j] = p;
			if(AVAILABLE[j]&lt;0)
				AVAILABLE[j] = 0;/*清理数据*/
		}/*for*/
	 }/*for*/
	for (i = 0 ; i < M ; i++)
		for(j = 0 ; j < N ; j++)
			NEED[i][j] = MAX[i][j] - ALLOCATION[i][j];/*求还需要的资源*/
	output();
	bank();/*银行家算法*/
	return 0;
}/*main*/
Categories: 算法研究 Tags: , ,
  1. January 5th, 2009 at 19:21 | #1

    看来是个开发人员呀,顶你

  2. January 5th, 2009 at 22:57 | #2

    其实CG的C语言底子好,我建议你去学python,学完你就很强了~

  3. January 5th, 2009 at 23:03 | #3

    呵呵,最近在啃Ruby

  4. January 6th, 2009 at 10:33 | #4

    你好,希望能交换友情连接, http://www.php123.org. 已经做好连接向贵站 !!

  5. 计算机bot?o
    January 7th, 2009 at 12:31 | #5

    Adiciona um bot?o de Publica??o e Vota??o Remota a todas as Páginas.

  6. January 10th, 2009 at 00:51 | #6

    我现在看到“银行”两个就气

  7. January 10th, 2009 at 00:51 | #7

    我现在看到“银行”两个字就气

  8. January 10th, 2009 at 14:26 | #8

    过来学习下 呵呵·!

  9. January 11th, 2009 at 13:21 | #9

    cg啊,python绝不亚于ruby哦!

  1. No trackbacks yet.