Home > 算法研究 > 操作系统 模拟可变分区内存管理实验 C语言描述

操作系统 模拟可变分区内存管理实验 C语言描述

操作系统 模拟可变分区内存管理实验 C语言描述
《知识共享协议》下修改、传播、发行,
如需网络转载请保留作者注释
调试环境 GCC , Borland Turbo C , MS VC++

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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
/*<!--HTML */
/*
*author CG
*www.lidaren.com
*环境 GCC ,Turbo C
*/
#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#define NULL 0
#define MAXSIZE 2000
#define MINSIZE 10
#define OFFSET 0
#define FALSE 0
#define TRUE 1
typedef int address;/*定义地址类型*/
typedef struct node{
    int size, used; /*定义分区大小和已经使用大小*/
    address add;/*定义起始地址*/
    int able;
    int id;/*分区ID*/
    char *info;/*其他信息*/
    struct node *pre, *next;
    }node,*list;
/**********以下定义全局变量********/
static int method=0;/*管理方法*/
static int jobId=0;/*作业ID*/
static list L=NULL;/*内存管理链表*/
static node * cnext=NULL;/*指向下以节点指针*/
/***********************************/
/*功能:分配分区,完成分区的分配功能
参数:node *n 被分配的空闲分区指针
int size请求的空间大小 int id 作业的ID
返回: ADD 分配后的节点的起始地址*/
node * distribute(node *n , int size , int id){
	node *p;
	if(n->size - size <= MINSIZE){
/*找到的节点符合需要且分配后剩余空间小于
MINSIZE,直接分配分区*/
		n->able = FALSE;
		n->used = size;
		n->size = size;
		n->id = id;
		return n;
	}/*if*/
	else{
/*找到的节点符合需要且分配后剩余空间大于
MINSIZE,将空闲分区切割,再分配分区*/
		p = (node *)malloc(sizeof(node));/*分配新空间节点*/
/*剩余空间重新组成的空间*/
		p->size = n->size-size;/*新节点初始化*/
		p->used = 0;
		p->add = n->add+size;/*新节点的起始地址*/
		p->able = TRUE;
		p->next = n->next;/*修改指针,完成节点插入*/
		n->next->pre = p;
		p->pre = n;
		n->next = p;
/*修改被分配分区节点的数据*/
		n->used = size;
		n->size = size;
		n->id = id;
		n->able = FALSE;
		return n;
	}/*else*/
}/*distribute*/
/*recycle 节点资源回收函数
*参数: node*n 传递要回收的节点指针
*返回:bool 返回操作是否成功*/
int recycle(node *n){
	node *r;/*备份指针*/
	if(n->pre->able == TRUE &#038;& n->add != 0)
	{
/*向上合并空闲区间,要求n节点的首地址不为0,为0直接
释放地址空间,n->add!=0可以防止地址假溢出*/
		r = n->pre;/*修改指针,删除节点*/
		r->pre->next = n;
		n->pre = r->pre;
		n->size += r->size;/*修改节点数据*/
		n->add = r->add;
		free(r);/*释放r*/
		recycle(n);/*递归调用回收函数*/
		return TRUE;
	}/*if*/
	else if(n->next->able == TRUE &#038;& n->next->add != 0)
	{
/*向下合并空闲区间,要求n节点的下一节点的首地址不为0,
为0会产生跨高低地址的分区n->next->add!=0可以防止地址假溢出*/
		r = n->next;/*修改指针*/
		n->next = r->next;
		r->next->pre = n;
		n->size += r->size;/*修改节点数据*/
		free(r);/*释放r*/
		recycle(n);/*递归调用回收函数*/
		return TRUE;
	}/*if*/
	else{
/*独立节点直接分配空间,以下也用于清理数据结构数据*/
		n->used = 0;
		n->able = TRUE;
		return TRUE;
	}/*else*/
}/*recycle*/
/*firstadapt 首次适应算法函数
*参数 list L 链表头节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针,失败返回NULL*/
node * firstAdapt(list L , int size){
	node * n;
	n = L;
	do{
	if(n->able == TRUE &#038;& n->size-MINSIZE >= size)
		return n;/*如果符合要求,返回n*/
	else n = n->next;/*n指针下移*/
	}while(n != L);/*n到达起始节点*/
	return NULL;
}/*firstadapt*/
/*cyclefirstadapt 循环首次适应算法函数
*参数 list start 链表开始查找节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针,失败返回NULL*/
node * cycleFirstAdapt(node * start , int size){
	node * n;
	n = start;
	do{
	if(n->able == TRUE &#038;& n->size - MINSIZE >= size)
		return n;
	else n = n->next;
	}while(n != start);
	return NULL;
}/*cyclefirstadapt*/
/*bestadapt 最佳适应算法函数,贪心算法
*参数 list L 链表头节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针,失败返回NULL*/
node * bestAdapt(list L , int size){
	node * n;/*遍历指针*/
	node * temp;/*临时指针,用于存放符合条件的节点*/
	int t ,flag;/*临时变量t存放结果差值,flag 成功标志位*/
	flag = FALSE;/*初始化标志*/
	n = L;
	temp = n;
	do{
	if(n->size - MINSIZE >= size){/*如果大小符合*/
		t = n->size - size;
		temp = n;
		flag = TRUE;/*查找标志置1*/
		break;
		}
	n = n->next;
	}while(n != L);
	do{
	if(n->size - MINSIZE >= size){/*取得第二个t*/
		if(t > n->size - size)
		{/*如果差值小于t, 替换t和temp*/
			t = n->size - size;
			temp = n;
			flag = TRUE;/*查找标志置1*/
		}/*if*/}/*if*/
	n = n->next;
	}while(n != L);
	if(flag)/*检查标志位*/
		return temp;
	else
		return NULL;
}/*bestadapt*/
/*worstadapt 首次适应算法函数
*参数 list L 链表头节点
	int size 节点大小用于判断是否符合空间要求
* 返回 node * 成功查找获得的节点指针,失败返回NULL*/
node * worstAdapt(list L , int size){
	node * n;/*变量指针*/
	node * temp;/*临时存放指针,用于存放查找结果*/
	n = L;/*n指向头节点*/
	temp = n;/*temp 初始值 n*/
	do{
	if(temp->size < n->next->size)
		temp=n->next;/*循环求最大的空间*/
	n = n->next;
	}while(n != L);
	if(temp->size - MINSIZE >= size)/*检查最大值是否符合分配前提*/
		return temp;
	else
		return NULL;
}/*worstadapt*/
/*searchbyid ID搜索函数
*参数:list L 链表头指针 int ID 要查找的ID
*返回:node * 节点指针,查找失败返回NULL*/
node * searchById(list L , int id){
	node * n;/*定义遍历指针*/
	n = L;
	do{
		if(n->id == id) return n;/*符合要求返回ID*/
		n = n->next;/*指针后移*/
	}while(n != L);
	return NULL;/*查找失败返回NULL*/
}/*search by id*/
/*schedule 算法调度函数,根据要求选择不同算法
参数 list L 链表头节点 int size 要分配的大小
返回 node * 返回的节点指针,失败返回NULL*/
node * schedule(list L , int size){
	node * n;
	switch(method){
	case 1 : n=firstAdapt(L,size); break;
	case 2 : n=cycleFirstAdapt(cnext,size);cnext=n->next; break;
	case 3 : n=bestAdapt(L , size); break;
	case 4 : n=worstAdapt(L , size); break;
	case 0 : leave();break;
	default : printf("ERROR: Unknown methodn");return NULL;
	}/*switch*/
	if(n)/*检查是否返回成功*/
		return n;
	else
		return NULL;
}/*schedule*/
/*newpart 新建分区函数
*返回 bool 分配空间是否成功
输入 int size 要分配的空间的大小*/
int newPart(){
	int size;/*定义空间大小*/
	node * n;
	printf("input SIZE the part needed:");
	scanf("%d",&#038;size);/*输入空间大小*/
	if(size <= MINSIZE){/*size太小*/
		printf("ERROR:Size too small!n");
		return FALSE;
	}/*if*/
	else if(size > MAXSIZE){/*size>最大可分配空间*/
		printf("ERROR:Size too large!n");
		return FALSE;
		}/*else*/
	if(method == 2)/*method=2,判断method是否为2?*/
		n = schedule( (list)cnext , size);/*查找空间 method=2*/
	else
		n = schedule(L , size);/*查找空间*/
	if(n == NULL){/*n返回为空?*/
		printf("ERROR:Can not distribute space!n");
		return FALSE;
		}/*if*/
	n = distribute(n , size , ++jobId);/*分配空间*/
	if(n){/*n返回成功*/
		printf("Distribute a part OKntWID:%d size:%d address:0x%Xn",
			n->id , n->used , n->add );
		return TRUE;
	}/*if*/
	else printf("ERRORn");
}/*newpart*/
/*freepart 释放空间函数
返回 bool 释放是否成功
输入 int id 输入要释放的wID*/
int freePart(){
	int id;
	node * n;
	printf("Input part WID you need to free:");
	scanf("%d",&#038;id);/*输入wid*/
	n = searchById(L , id);/*在L中查找ID*/
	if(n){/*查找成功*/
		if(recycle(n)){/*回收成功*/
			printf("Recycle a space successed WID:%dn",n->id);
			return TRUE;
			}
		else/*回收失败*/
			return FALSE;
	}/*if*/
	else{/*查找失败*/
	printf("ERROR:ID:%d Not found!n",id);
	return FALSE;
	}/*else*/
}/*freepart*/
/*output 结果输出函数
输出 列表形式输出L中的每一个节点的数据*/
int output(){
	node * n;/*定义遍历指针*/
	int count = 0;/*定义计数器,初始化为0*/
	n = L;
	printf("n|__BID___|__SIZE__|__ADD___|__USED__|__WID___|n");
	do{
		printf("|%8d|%8d|0x%-6X" , ++count , n->size , n->add);
		if(n -> able == TRUE)/*可用空间*/
			printf("|  FREE  |  FREE  |n");
		else/*已用空间*/
			printf("|%8d|%8d|n" , n->used , n->id);
	n = n->next;/*指针下移*/
	}while(n != L);
	return TRUE;/*输出完毕*/
}/*output*/
/*mainmenu 主菜单输出函数
输出 列表显示猪菜单
返回 bool 返回菜单是否打印成功*/
int mainmenu(){
printf("Method:method to manage partitionn");
printf(" -FtFirst Adpat (FA)n");
printf(" -CtCycle First Adapt (CFA)n");
printf(" -BtBest Adapt (BA)n");
printf(" -WtWorst Adapt (WA)n");
printf(" -XtExitn");
printf("ttype 'H' show help menun");
return TRUE;
}/*mainmenu*/
/*submenu 子菜单输出函数
输出 列表显示猪菜单
返回 bool 返回菜单是否打印成功*/
int submenu(){
printf("Command:command to operate listn");
printf(" -DtDistribute a new spacen");
printf(" -FtFree a exsit pacen");
printf(" -OtOutput all space listn");
printf(" -CtClear space listn");
printf(" -RtReturn to main menun");
printf(" -XtExitn");
printf("ttype 'H' show help menun");
return TRUE;
}/*submenu*/
/*init 初始化函数,用于初始化list L
返回 bool 初始化是否成功?*/
int init(){
	L = (node *)malloc(sizeof(node));/*分配节点*/
	L->next = L;/*初始化指针next=L,pre=L*/
	L->pre = L;
	L->add = 0;/*初始化数据结构*/
	L->able = TRUE;
	L->size = MAXSIZE;
	L->used = 0;
	L->id = 0;
	L->info = NULL;
	cnext = L;/*初始化全局变量cnext*/
	return TRUE;
}/*init*/
/*clear 链表清空函数
返回 bool 链表清除是否成功?*/
int clear(){
	node * n , * t;
	n = L;
	do{/*遍历链表*/
		t = n;
		n = n->next;/*指针下移*/
		free(t);
	}while(n != L);/*while*/
	L->next = L;/*初始化L指针*/
	L->pre = L;
	L->add = 0;/*初始化L数据结构*/
	L->able = TRUE;
	L->size = MAXSIZE;
	L->used = 0;
	L->info = NULL;
	printf("Clear list successed!n");
	return TRUE;
}/*init*/
/*leave 退出函数,用于退出时清理内存空间
返回 boo 清理是否成功?*/
int leave(){
	node *n,*t;/*定义遍历指针和临时指针 */
	n = L;
	do{/*遍历链表*/
		t = n;
		n = n->next;/*指针下移*/
		free(t);/*释放t*/
	}while(n != L);/*while*/
	free(L);/*释放头节点*/
	exit(0);
}/*leave*/
/*process 调度进程函数,用于整个进程的调度
返回 bool 程序是否正确执行?
输入 char 用于程序操作的命令*/
int process(){
char SELECT = NULL;/*定义输入字符*/
submenu();/*打印菜单*/
while(1){
	putchar('-');
	SELECT = getch();/*输入SELECT*/
switch(SELECT){
	case 'd':
	case 'D': newPart(); break;/*新建分区*/
	case 'f':
	case 'F': freePart(); break;/*释放分区*/
	case 'o':
	case 'O': output(); break;/*输出链表*/
	case 'c':
	case 'C': clear(); break;/*清空链表*/
	case 'x':
	case 'X': leave(); break;/*离开*/
	case 'h':
	case 'H': submenu(); break;/*帮助*/
	case 'r':
	case 'R': return TRUE;/*返回*/
	default : printf("ERRORn"); continue;/*输入错误*/
	}/*switch*/
}/*while*/
return FALSE;
}/*process*/
/*main 主函数*/
int main(){
char SELECT = NULL;/*定义输入区间*/
init();/*初始化*/
start: clrscr();/*清屏*/
	printf("Memeory Manage Use Flexable partitionn");
	printf("by CG t cg45@yahoo.cnnn");
	mainmenu();/*打印主菜单*/
while(1){
	putchar('-');
	SELECT = getch();/*输入SELECT*/
	switch(SELECT){
	case 'f':
	case 'F': method = 1; break;/*FA*/
	case 'c':
	case 'C': method = 2; break;/*CFA*/
	case 'b':
	case 'B': method = 3; break;/*BA*/
	case 'w':
	case 'W': method = 4; break;/*WA*/
	case 'x':
	case 'X': leave(); break;/*退出*/
	case 'h':
	case 'H': mainmenu(); continue;/*帮助*/
	default : printf("ERRORn"); continue;/*输入错误*/
	}/*switch*/
	if(process()==1)/*执行进程调度成功?*/
		goto start;
	else/*调度错误或失败*/
		leave();
}/*while*/
}/*main*/
/*-->*/
Categories: 算法研究 Tags: ,
  1. No comments yet.
  1. No trackbacks yet.