操作系统模拟首次适应算法

老师程序基础上改动的，也是老师布置的作业。

亮点：实现循环首次适应算法

	多一个p空闲块的指针；rearrange_NF()循环首次适应算法；由于要实现这个算法连动着的改了很多地方例如：set_algorithm()选择算法函数，还多弄了个free_mem1()，用于区别于前三个算法。
	大佬互喷哈，卑微求赞。
1
2

 /*宏定义*/
#include<stdio.h>
#include<stdlib.h>
#include<sys/types.h>
#define PROCESS_NAME_LEN     32        /*进程名称的最大长度*/
#define MIN_SLICE            10        /*最小碎片的大小*/
#define DEFAULT_MEM_SIZE     1024      /*默认内存的大小*/
#define DEFAULT_MEM_START    0         /*默认内存的起始位置*/
/* 内存分配算法 */
#define MA_FF      1
#define MA_BF      2
#define MA_WF      3
int mem_size=DEFAULT_MEM_SIZE;         /*内存大小*/
int ma_algorithm = MA_FF;              /*当前分配算法*/
int flag = 0;            		       /*设置内存大小标志*/
static int pid = 0;                    /*初始pid*/
int algorithm;
void rearrange(int algorithm);
/*描述每一个空闲块的数据结构*/
struct free_block_type{
    int size;
    int start_addr;
    struct free_block_type *next;
};
/*指向内存中空闲块链表的首指针*/
struct free_block_type *free_block;
struct free_block_type *p;
/*每个进程分配到的内存块的描述*/
struct allocated_block{
    int pid;
    int size;
    int start_addr;
    char process_name[PROCESS_NAME_LEN];
    struct allocated_block *next;
};
/*进程分配内存块链表的首指针*/
struct allocated_block *allocated_block_head = NULL;  
struct allocated_block *find_process(int id)
{
    struct allocated_block *q;
	//printf("ce shi");
	q=allocated_block_head;
	printf("ce shi");
	while(q!=NULL)
	{
	    if (q->pid==id){return q;}
		q = q->next;
	}
	return NULL;
}
void swap(int *t,int *q)
{
    int temp;
     temp  =  *t;
       *t  =  *q;
       *q  =  temp;
}
void do_exit()
{
   exit(0);
}
/*初始化空闲块，默认为一块，可以指定大小及起始地址*/
struct free_block_type* init_free_block(int mem_size){
    struct free_block_type *fb;
    fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
    if(fb==NULL){
        printf("No mem\n");
        return NULL;
    }
    fb->size = mem_size;
    fb->start_addr = DEFAULT_MEM_START;
    fb->next = NULL;
    return fb;
}
/*显示菜单*/
void display_menu(){
    printf("\n");
    printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
    printf("2 - Select memory allocation algorithm\n");
    printf("3 - New process \n");
    printf("4 - Terminate a process \n");
    printf("5 - Display memory usage \n");
    printf("0 - Exit\n");
}
/*设置内存的大小*/
int set_mem_size(){
    int size;
    if(flag!=0){  //防止重复设置
        printf("Cannot set memory size again\n");
        return 0;
        }
    printf("Total memory size =");
    scanf("%d", &size);
    if(size>0) {
        mem_size = size;
        free_block->size = mem_size;
        }
    flag=1;  return 1;
}
/*按FF算法重新整理内存空闲块链表*/
int rearrange_NF(allocated_block *ab)
{
	struct free_block_type *pre, *temp,*work; 
    int request_size=ab->size;
    while(p!=NULL)
	{
        if(p->size>=request_size)
		{
			if (p->size - request_size >= MIN_SLICE) /*分配后空闲空间足够大，则分割*/
			{
			    mem_size -= request_size;
				p->size -= request_size; 
			    ab->start_addr= p->start_addr;
				p->start_addr +=  request_size;
				if(p->next==NULL)
				{
					rearrange(1);
					p = free_block;
				}
				else
					p = p->next;
			}  
			else  if (((p->size - request_size) < MIN_SLICE)&&((p->size - request_size) > 0))
			   /*分割后空闲区成为小碎片，一起分配*/
			{
			     mem_size -= p->size;
			     pre = p->next;
                 ab->start_addr= p->start_addr;
				 p->start_addr +=  p->size;
				 free(p);
			}
			else 
			{
			    temp = free_block;
				
				while(temp!=NULL)
				{
				    work = temp->next;
                    
					if(work!=NULL)/*如果当前空闲区与后面的空闲区相连，则合并*/
					{             
                         	           if (temp->start_addr+temp->size == work->start_addr)
				               { 
                            		           temp->size += work->size;
                                                   temp->next = work->next;
                                                   free(work);
                                                   continue;
					       }
					}
                    
					temp = temp->next;
			        }
				break;
			}

			 return 1;
		}
	}
    return -1;
}
void rearrange_FF(){
    struct free_block_type *tmp, *work;
    printf("Rearrange free blocks for FF \n");
    tmp = free_block;
    while(tmp!=NULL)
    { 
		work = tmp->next;
		while(work!=NULL)
		{
			if ( work->start_addr < tmp->start_addr)
			{ /*地址递增*/
				swap(&work->start_addr, &tmp->start_addr);
				swap(&work->size, &tmp->size);
			}
			work=work->next;            
        }
		tmp = tmp -> next;
     }
}
/*按BF最佳适应算法重新整理内存空闲块链表*/
void rearrange_BF(){
    struct free_block_type *tmp, *work;
    printf("Rearrange free blocks for BF \n");
    tmp = free_block;
	while(tmp!=NULL)
    { 
		work = tmp->next;
		while(work!=NULL)
		{
			if ( work->size < tmp->size) 
			{ /*地址递增*/
				swap(&work->start_addr, &tmp->start_addr);
				swap(&work->size, &tmp->size);
            }
			work=work->next;            
        }
      tmp = tmp -> next;
     }
}
/*按WF算法重新整理内存空闲块链表*/
void rearrange_WF(){
    struct free_block_type *tmp, *work;
    printf("Rearrange free blocks for WF \n");
    tmp = free_block;
	while(tmp!=NULL)
    { 
		work = tmp->next;
		while(work!=NULL)
		{
			if ( work->size > tmp->size) 
			{ /*地址递增*/
				swap(&work->start_addr, &tmp->start_addr);
				swap(&work->size, &tmp->size);
            }
			work=work->next;            
        }
      tmp = tmp -> next;
     }
}
/*按指定的算法整理内存空闲块链表*/
void rearrange(int algorithm){
    switch(algorithm){
        case MA_FF:  rearrange_FF(); break;
        case MA_BF:  rearrange_BF(); break;
        case MA_WF:  rearrange_WF(); break;
		case 4: ;break;
        }
}
/* 设置当前的分配算法 */
void set_algorithm(){
    printf("\t1 - First Fit\n");
    printf("\t2 - Best Fit \n");
    printf("\t3 - Worst Fit \n");
	printf("\t4 - NF \n");
    scanf("%d", &algorithm);
    if(algorithm>=1 && algorithm <=4) ma_algorithm=algorithm;
	//按指定算法重新排列空闲区链表
    if(algorithm>=1 && algorithm <=3)rearrange(ma_algorithm); 
}
/*分配内存模块*/
int allocate_mem(struct allocated_block *ab){
    struct free_block_type *fbt, *pre, *temp,*work; 
    int request_size=ab->size;
    fbt = free_block;
    while(fbt!=NULL)
	{
        if(fbt->size>=request_size)
		{
			if (fbt->size - request_size >= MIN_SLICE) /*分配后空闲空间足够大，则分割*/
			{
			    mem_size -= request_size;
				fbt->size -= request_size; 
			    ab->start_addr= fbt->start_addr;
			}  
			else  if (((fbt->size - request_size) < MIN_SLICE)&&((fbt->size - request_size) > 0))
			   /*分割后空闲区成为小碎片，一起分配*/
			{
			     mem_size -= fbt->size;
			     pre = fbt->next;
                 ab->start_addr= fbt->start_addr;
				 fbt->start_addr +=  fbt->size;
				 free(fbt);
			}
			else 
			{
			    temp = free_block;
				
				while(temp!=NULL)
				{
				    work = temp->next;
                    
					if(work!=NULL)/*如果当前空闲区与后面的空闲区相连，则合并*/
					{             
                         	           if (temp->start_addr+temp->size == work->start_addr)
				               { 
                            		           temp->size += work->size;
                                                   temp->next = work->next;
                                                   free(work);
                                                   continue;
					       }
					}
                    
					temp = temp->next;
			        }
				fbt = free_block;
				break;
			}
			 rearrange(algorithm); /*重新按当前的算法排列空闲区*/ 
			 return 1;
		}
      
		pre = fbt;
           fbt = fbt->next;
	}
    return -1;
}
/*创建新的进程，主要是获取内存的申请数量*/
int new_process(){
    struct allocated_block *ab;
    int size;
    int ret;
    ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
    if(!ab) exit(-5);
    ab->next = NULL;
    pid++;
    sprintf(ab->process_name, "PROCESS-%02d", pid);
    ab->pid = pid;
    printf("Memory for %s:", ab->process_name);
    scanf("%d", &size);
    if(size>0) ab->size=size;
	if(ma_algorithm>=1&&ma_algorithm<=3)ret = allocate_mem(ab);  /* 从空闲区分配内存，ret==1表示分配ok*/
/*如果此时allocated_block_head尚未赋值，则赋值*/
	if(ma_algorithm=4)ret = rearrange_NF(ab);
    if((ret==1) &&(allocated_block_head == NULL)){ 
        allocated_block_head=ab;
        return 1;
        }
    /*分配成功，将该已分配块的描述插入已分配链表*/
    else if (ret==1) {
        ab->next=allocated_block_head;
        allocated_block_head=ab;
        return 2;
        }
    else if(ret==-1){ /*分配不成功*/
        printf("Allocation fail\n");
        free(ab);
        return -1;
        }
    return 3;
}
/*将ab所表示的已分配区归还，并进行可能的合并*/
int free_mem(struct allocated_block *ab)
{
    int algorithm = ma_algorithm;
    struct free_block_type *fbt, *work;

    fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
    if(!fbt) return -1;
    fbt->size = ab->size;
    fbt->start_addr = ab->start_addr;
    /*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
    fbt->next = free_block;
    free_block=fbt;
    rearrange(MA_FF);
    fbt=free_block;
    while(fbt!=NULL){
        work = fbt->next;
        if(work!=NULL)
        {
            /*如果当前空闲区与后面的空闲区相连，则合并*/
             if(fbt->start_addr+fbt->size == work->start_addr)
             { 
                    fbt->size += work->size;
                    fbt->next = work->next;
                    free(work);
                    continue;
			}
        }
        fbt = fbt->next;
    }
    rearrange(algorithm); /*重新按当前的算法排列空闲区*/
    return 1;
}
int free_mem1(struct allocated_block *ab)
{
    int algorithm = ma_algorithm;
    struct free_block_type *fbt, *work;

    fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
    if(!fbt) return -1;
    fbt->size = ab->size;
    fbt->start_addr = ab->start_addr;
	/*插入到空闲区链表的头部并将空闲区按地址递增的次序排列*/
	fbt->next = free_block;
    free_block=fbt;
    rearrange(1);
    fbt=free_block;
    while(fbt!=NULL){
        work = fbt->next;
        if(work!=NULL)
        {
            /*如果当前空闲区与后面的空闲区相连，则合并*/
             if(fbt->start_addr+fbt->size == work->start_addr)
             { 
                    fbt->size += work->size;
                    fbt->next = work->next;
                    free(work);
                    continue;
			}
        }
        fbt = fbt->next;
    }
    return 1;
}
 /*释放ab数据结构节点*/
int dispose(struct allocated_block *free_ab){
    struct allocated_block *pre, *ab;
   
    if(free_ab == allocated_block_head) { /*如果要释放第一个节点*/
        allocated_block_head = allocated_block_head->next;
        free(free_ab);
        return 1;
        }

    pre = allocated_block_head;  
    ab = allocated_block_head->next;

    while(ab!=free_ab){ pre = ab;  ab = ab->next; }
    pre->next = ab->next;
    free(ab);
    return 2;
    }
/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */
int display_mem_usage(){
    struct free_block_type *fbt=free_block;
    struct allocated_block *ab=allocated_block_head;
    if(fbt==NULL) return(-1);
    printf("----------------------------------------------------------\n");

    /* 显示空闲区 */
    printf("Free Memory:\n");
    printf("%20s %20s\n", "      start_addr", "       size");
    while(fbt!=NULL){
        printf("%20d %20d\n", fbt->start_addr, fbt->size);
        fbt=fbt->next;
	}    
/* 显示已分配区 */
    printf("\nUsed Memory:\n");
    printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
	while(ab!=NULL)
	{
		printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
        ab=ab->next;
    }
    printf("----------------------------------------------------------\n");
    return 0;
}
/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/
void kill_process()
{
    struct allocated_block *ab;
    int pid;
    printf("Kill Process, pid=");
    scanf("%d", &pid);
    ab=find_process(pid);
	printf("found");
    if(ab!=NULL)
    {
		if(ma_algorithm>=1&&ma_algorithm<=3)free_mem(ab); /*释放ab所表示的分配区*/
		if(ma_algorithm=4)free_mem1(ab);
        dispose(ab);  /*释放ab数据结构节点*/
    }
}
int main()
{
    char choice;
    pid=0;
    free_block = init_free_block(mem_size); //初始化空闲区
	p = free_block;
    for(;;)
    {
		  display_menu();	//显示菜单
		  fflush(stdin);
		  choice=getchar();	//获取用户输入
		  switch(choice)
		  {
				 case '1':  set_mem_size();                   break;       //设置内存大小
				 case '2': set_algorithm();        flag=1;    break;	       //设置分配算法
				 case '3': new_process();          flag=1;    break;	       //创建新进程
				 case '4':   kill_process();       flag=1;    break;	       //删除进程
				 case '5':   display_mem_usage();  flag=1;    break;         //显示内存使用
				 case '0':   do_exit(); exit(0);                break;	    //释放链表并退出
				 default: break;
		  }
   } 
}

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
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477