对操作系统内存管理的模拟（应用）

今天来续写，觉得昨天那种安排不合理，于是将原理与应用分两篇来写，不至于让大家和我看的有些烦。

　　温故而知新可以为师矣，如果不能为师，给自己当老师也不错哦。好了，写一个模拟内存管理的程序吧，老师说有原理，也要有具体实现，这是提升分析问题的一种途径。下面写写程序，并进行解说，这个程序我当时也完善了一下。

　　先写一些宏定义和全局变量

View Code

 1 #define PROCESS_NAME_LEN 32        //进程名称的最大长度
 2 #define MIN_SLICE    10            //最小碎片的大小
 3 #define DEFAULT_MEM_SIZE 1024       //默认内存的大小
 4 #define DEFAULT_MEM_START 0        //默认内存的起始位置
 5 
 6 // 内存分配算法 
 7 #define MA_FF 1        //首次适应算法,地址递增
 8 #define MA_BF 2        //最佳适应算法,空闲区容量从大到小
 9 #define MA_WF 3        //循环首次适应算法,
10 
11 int mem_size=DEFAULT_MEM_SIZE;        //内存大小
12 int ma_algorithm = MA_FF;            //当前分配算法
13 static int pid = 0;                    //初始pid
14 int flag = 0;                    //设置内存大小标志

　　哦，以前写的时候就有注释，所以碰到一些注释不明确的我在解释解释。

　　下面是几个重要的数据结构，看过linux内核代码的童鞋对操作系统的数据结构应该有所了解，其实也就是比我们平时用的更深入、更精巧而已，基本原理还是一样，有些只是我们没那么用过，我这个还是一般的用法。

 

View Code

 1 //描述每一个空闲块的数据结构
 2 struct free_block_type{
 3     int size;
 4     int start_addr;
 5     struct free_block_type *next;
 6 };  
 7 
 8 //指向内存中空闲块链表的首指针
 9 struct free_block_type *free_block;
10 
11 /*每个进程分配到的内存块的描述*/
12 struct allocated_block{
13     int pid;
14     int size;
15     int start_addr;
16     char process_name[PROCESS_NAME_LEN];
17     struct allocated_block *next;
18 };
19 
20 //进程分配内存块链表的首指针
21 struct allocated_block *allocated_block_head = NULL; 

　　linux内核也是这样命名的，基本都能见名知意，我就不费话了。

 

View Code

 1 /*初始化空闲块，默认为一块，可以指定大小及起始地址*/
 2 struct free_block_type* init_free_block(int mem_size){
 3     struct free_block_type *fb;
 4 
 5     fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));
 6     if(fb==NULL){
 7         printf("No mem\n");
 8         return NULL;
 9     }
10     fb->size = mem_size;
11     fb->start_addr = DEFAULT_MEM_START;
12     fb->next = NULL;
13     printf("init_free_block fished\n\n");
14     return fb;
15 }

　　写过单片机或者ARM程序的同学可能对初始化有比较深刻的理解，因为在做一些事情之前，总是要做一些准备工作，举个最简答的例子，吃饭之前要做什么准备工作，洗手？错了，我说的不是这个。吃饭你得有筷子、碗和饭菜，这些就是初始化工作，接下来你才能吃饭呀。

 

 

View Code

 1 //显示菜单
 2 void display_menu(){
 3     printf("\n");
 4     printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);
 5     printf("2 - Select memory allocation algorithm\n");
 6     printf("3 - New process \n");
 7     printf("4 - Terminate a process \n");
 8     printf("5 - Display memory usage \n");
 9     printf("0 - Exit\n");
10 }

　　这个相当于菜单，就这样。

 

View Code

 1 //设置内存的大小
 2 int set_mem_size(){
 3     int size;
 4     if(flag!=0){  //防止重复设置
 5         printf("Cannot set memory size again\n");
 6         return 0;
 7     }
 8     printf("Total memory size =");
 9     scanf("%d", &size);
10     if(size>0) {
11         mem_size = size;
12         free_block->size = mem_size;
13     }
14     flag=1;  
15     return 1;
16 }

　　这个其实也相当于初始化，只不过你有了选择权。

 

View Code

  1 // 设置当前的分配算法 
  2 void set_algorithm(){
  3     int algorithm;
  4     printf("\t1 - First Fit\n");                    //首次适应算法，简称FF
  5     printf("\t2 - Best Fit \n");                   //最佳适应算法
  6     printf("\t3 - Worst Fit \n");                 //最差适应算法
  7     scanf("%d", &algorithm);
  8     if(algorithm>=1 && algorithm <=3)
  9     ma_algorithm=algorithm;
 10     
 11     rearrange(ma_algorithm); //按指定算法重新排列空闲区链表
 12 }
 13 
 14 //按指定的算法整理内存空闲块链表
 15 void rearrange(int algorithm){
 16     switch(algorithm){
 17         case MA_FF:   rearrange_FF(); break;
 18         case MA_BF:   rearrange_BF(); break;
 19         case MA_WF:  rearrange_WF(); break;        
 20     }
 21 }
 22 //按FF算法重新整理内存空闲块链表
 23 void rearrange_FF(){
 24     
 25     struct free_block_type *position, *min, *current;
 26     int size;
 27     int start_addr;
 28     printf("Rearrange free blocks for FF \n\n");
 29     position = free_block;
 30 
 31     //空闲块按地址顺序进行简单选择排序
 32     while (position != NULL) {     
 33     min = position;
 34                 current = position->next;
 35 
 36                 while(current != NULL){
 37         if( current->start_addr < min->start_addr) {
 38                                          min = current;
 39                                 }
 40                     current = current->next;            
 41                 }
 42 
 43                 size = position->size;        
 44                 position->size = min->size;
 45                 min->size = size;
 46 
 47                 start_addr = position->start_addr;
 48                 position->start_addr = min->start_addr;
 49                 min->start_addr = start_addr;
 50 
 51                 position = position->next;
 52      }     
 53 }
 54 
 55 //按BF算法重新整理内存空闲块链表
 56 void rearrange_BF(){
 57 
 58     struct free_block_type *position, *min, *current;
 59     int size;
 60     int start_addr;
 61     printf("Rearrange free blocks for BF\n\n");
 62     position = free_block;
 63 
 64     //空闲块按由小到大进行简单选择排序
 65     while (position != NULL) {                min = position;
 66     current = position->next;
 67 
 68                 while(current != NULL){
 69         if( current->size < min->size) {    
 70             min = current;
 71                                 }
 72         current = current->next;            
 73                 }
 74 
 75                 size = position->size;        
 76     position->size = min->size;
 77     min->size = size;
 78 
 79     start_addr = position->start_addr;
 80     position->start_addr = min->start_addr;
 81     min->start_addr = start_addr;
 82 
 83     position = position->next;
 84     }     
 85 }
 86 
 87 
 88 //按WF算法重新整理内存空闲块链表
 89 void rearrange_WF(){
 90     struct free_block_type *position, *min, *current;
 91     int size;
 92     int start_addr;
 93     printf("Rearrange free blocks for WF \n\n");
 94     position = free_block;
 95 
 96     //空闲块按由大到小进行简单选择排序
 97     while (position != NULL) {                min = position;
 98     current = position->next;
 99 
100         while(current != NULL){
101         if( current->size > min->size) {    
102             min = current;
103                                 }
104         current = current->next;            
105     }
106 
107     size = position->size;        
108     position->size = min->size;
109     min->size = size;
110 
111     start_addr = position->start_addr;
112     position->start_addr = min->start_addr;
113     min->start_addr = start_addr;
114 
115     position = position->next;
116     }     
117 }

　　这段是按三种排序算法进行内存整理，如果你了解这三种排序算法，就没必要看这些了，我觉得只要对算法核心思想理解了，写基本是没问题的，最大的差异可能就是效率和风格。

　　

View Code

 1 //创建新的进程，主要是获取内存的申请数量
 2 int new_process(){
 3     struct allocated_block *ab;
 4     int size;
 5     int ret;
 6     ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));
 7     if(!ab) exit(-5);
 8     ab->next = NULL;
 9     pid++;
10     sprintf(ab->process_name, "PROCESS-%02d", pid);  //格式化字符串复制，将引号中数据复制到ab->process_name字符数组中去
11     ab->pid = pid;
12     
13     printf("Memory for %s:", ab->process_name);
14     scanf("%d", &size);
15     if(size>0) ab->size=size;
16     ret = allocate_mem(ab);            // 从空闲区分配内存，ret==1表示分配ok
17 //如果此时allocated_block_head尚未赋值，则赋值
18     if((ret==1) &&(allocated_block_head == NULL)){ 
19         allocated_block_head=ab;
20         printf("new_process was created\n\n");
21         return 1;
22         }
23     //分配成功，将该已分配块的描述插入已分配链表
24     else if (ret==1) {
25         ab->next=allocated_block_head;
26         allocated_block_head=ab;
27         printf("new_process was created\n\n");
28         return 2;
29         }
30     else if(ret==-1){ //分配不成功
31         printf("Allocation fail\n");
32         free(ab);
33         return -1;
34         }
35     return 3; 
36 }

　　这部分主要是创建线程并作一些初始化工作。

　　

View Code

 1 //分配内存模块
 2 int allocate_mem(struct allocated_block *ab){
 3     struct free_block_type *fbt, *pre;
 4     int request_size=ab->size;
 5     int sum_size = 0;
 6     fbt = pre = free_block;
 7 
 8     while(fbt!=NULL){
 9 
10         if( (fbt->size - request_size) >= MIN_SLICE ){    //分配后空闲空间足够大，则分割         
11             ab->start_addr = fbt->start_addr;
12             fbt->size = fbt->size - request_size;
13             fbt->start_addr = fbt->start_addr + request_size;
14             rearrange(ma_algorithm);
15             return 1;
16         }
17         else if( (fbt->size > request_size) && (fbt->size - request_size < MIN_SLICE) ){    //分割后空闲区成为小碎片，一起分配
18              ab->start_addr = fbt->start_addr;
19             ab->size = fbt->size;
20             if(fbt == free_block) {
21                 free_block = fbt->next;
22                 free(fbt);
23             }
24             else{
25                 pre->next = fbt->next;
26                 free(fbt);
27             }
28             rearrange(ma_algorithm);
29             return 1;
30         }
31 
32         sum_size += fbt->size;
33         pre = fbt;
34         fbt = fbt->next;
35     }
36     if(sum_size < request_size)
37         return -1;
38     else {
39         compress(ab,request_size,sum_size);
40         return 1;
41     }
42 }

　　这部分主要是如何去分配内存，下面的代码是在碰到还有内存时，但这些内存大小都不足以满足所要申请的大小，我们就要进行碎片整理，如果整理后还不能满足要求，我们只能对程序说声对不起。

 

View Code

 1 //**********紧缩后分配
 2 void compress(struct allocated_block *ab, int request_size, int sum_size){   
 3 
 4     struct allocated_block *ab1, *ab2;
 5     struct free_block_type *fb1, *fb2;
 6     ab1 = allocated_block_head;
 7     ab1->start_addr = 0;
 8     ab2 = ab1->next;
 9 
10     while(ab2 != NULL){
11         ab2->start_addr = ab1->start_addr + ab1->size;
12         ab1 = ab2;
13         ab2 = ab2->next;
14     }
15     printf("free block was compressed\n\n");
16     ab->start_addr = ab1->start_addr + ab1->size;
17     
18     fb1 = free_block->next;        //紧缩后只有一个空闲块，无需排序
19     while(fb1 != NULL){            //其他空闲块释放
20         fb2 = fb1->next;
21         free(fb1);
22         fb1 = fb2;
23     }
24     printf("free block was set free\n\n");
25     free_block->start_addr = ab->start_addr + ab->size;
26     free_block->size = sum_size - request_size;
27     free_block->next = NULL;
28 
29     if( (sum_size >= request_size) && (sum_size - request_size < MIN_SLICE) ) {
30         ab->size = sum_size;
31         free_block->start_addr = -1;
32         free_block->size = 0;
33     }
34 }    

　　上面就是碎片整理的代码。

 

　　下面介绍杀死一个进程并对其内存空间的释放与回收：

 

View Code

 1 //删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点
 2 void kill_process(){
 3     struct allocated_block *ab;
 4     int pid;
 5     printf("Kill Process, pid=");
 6     scanf("%d", &pid);
 7     ab=find_process(pid);
 8     if(ab != NULL){
 9       free_mem(ab); //释放ab所表示的分配区
10        dispose(ab);  //释放ab数据结构节点
11        printf("process %2d was killed\n", pid);
12     }
13     else printf("no this process %2d\n", pid);
14 }
15 
16 struct allocated_block * find_process(int pid){
17     struct allocated_block * ab;
18     ab = allocated_block_head;
19 
20     while(ab != NULL){
21         if(ab->pid == pid)
22             return ab;
23         ab = ab->next;
24     }
25 
26     return ab;
27 
28 }
29 
30 //将ab所表示的已分配区归还，并进行可能的合并
31 int free_mem(struct allocated_block *ab){
32     int algorithm = ma_algorithm;
33     struct free_block_type *fbt, *pre;
34 
35     fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));
36     if(!fbt) {
37         printf("malloc free_block_type error\n"); 
38         return -1;
39     }
40     fbt->start_addr = ab->start_addr; //保存结点信息并将释放结点插入到空闲队列开头
41     fbt->size = ab->size;
42     fbt->next = free_block;
43     free_block = fbt;
44     
45     rearrange_FF();    //按地址有序排列
46     printf("free block was sorted according to address\n");
47     
48     pre = free_block;    //合并相邻空闲分区
49     fbt = free_block->next;
50     while(fbt != NULL){
51         if(pre->start_addr + pre->size == fbt->start_addr)
52         {
53             pre->size = pre->size + fbt->size;
54             pre->next = fbt->next;
55             free(fbt);
56             fbt = pre->next;
57         }
58         else {
59             pre = fbt->next;
60             fbt = fbt->next;
61         }
62     }
63     printf("free block combined\n\n");
64     rearrange(ma_algorithm);    //按当前算法重新排序
65 
66     return 1;
67     
68 }
69 
70  //释放ab数据结构节点
71 int dispose(struct allocated_block *free_ab){
72     struct allocated_block *pre, *ab;
73     
74     if(free_ab == allocated_block_head) { //如果要释放第一个节点
75         allocated_block_head = allocated_block_head->next;
76         free(free_ab);
77         printf("Node ab has been free\n");
78         return 1;
79         }
80 
81     pre = allocated_block_head;  //释放的是其他节点 
82     ab = allocated_block_head->next;
83 
84     while(ab != free_ab){    
85         pre = ab;  
86         ab = ab->next; 
87     }
88     pre->next = ab->next;
89     free(ab);
90     return 2;
91 }

 

　　当然这只一个对内存管理的模拟，如果在运行这个程序时，我们没释放所有内存空间，我们就要在程序结束之前，自动对其释放，要不就会造成内存泄露。

 

View Code

 1 void do_exit(){        //释放空间
 2     struct free_block_type *fb1, *fb2;
 3     struct allocated_block *ab1, *ab2;
 4     
 5     fb1 = free_block;
 6     while(fb1 !=NULL){
 7         fb2 = fb1->next;
 8         free(fb1);
 9         fb1 = fb2;
10     }
11     printf("free_block_type free\n\n");
12 
13     ab1 = allocated_block_head;
14     while (ab1 != NULL){
15         ab2 = ab1->next;
16         free(ab1);
17         ab1 = ab2;
18     }
19     printf("allocated_block free\n\n");
20 }

　　

　　好了，再来一个最原始的显示内存使用情况的界面吧。　　

View Code

 1 // 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 
 2 int display_mem_usage(){
 3     struct free_block_type *fbt=free_block;
 4     struct allocated_block *ab=allocated_block_head;
 5 
 6     //if(fbt==NULL) return(-1);
 7 
 8     printf("----------------------------------------------------------\n");
 9 
10     // 显示空闲区 
11     printf("Free Memory:\n");
12     printf("%20s %20s\n", "      start_addr", "       size");
13     while(fbt!=NULL){
14         printf("%20d %20d\n", fbt->start_addr, fbt->size);
15         fbt=fbt->next;
16     }  
17     
18     // 显示已分配区 
19     printf("\nUsed Memory:\n");
20     printf("%10s %20s %10s %10s\n", "PID", "ProcessName", "start_addr", " size");
21 
22     while(ab!=NULL){
23         printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);
24         ab=ab->next;
25         }
26     printf("----------------------------------------------------------\n");
27 
28     return 0;
29 }
30           

　　

主函数是最简单的，也相当于一个菜单。

 

View Code

 1 main(){
 2     char choice;
 3     pid=0;
 4     free_block = init_free_block(mem_size); //初始化空闲区
 5     for(;;){
 6         display_menu();    //显示菜单
 7         fflush(stdin);
 8         choice=getchar();    //获取用户输入
 9 
10         switch(choice){
11         case    '1'    : set_mem_size(); break;             //设置内存大小
12         case    '2'    : set_algorithm();flag=1; break;        //设置分配算法   
13         case    '3'    : new_process(); flag=1; break;        //创建新进程
14         case    '4'    : kill_process(); flag=1; break;        //删除进程
15         case    '5'    : display_mem_usage(); flag=1; break;        //显示内存使用    
16         case    '0'    : do_exit(); exit(0);            //释放链表并退出
17         
18         default: break;
19         }
20 
21     } 
22 }

　　结束了，太长了是不，慢慢看，刚开始我也是慢慢理解了才写的，如果哪块有更好的解决办法，请各位多多指教，我会虚心接受，期待你的意见或建议。今天天气不错，艳阳高照，在初冬时节，有这样的天气，感觉很舒适，希望这样的天气保持到星期天。