对操作系统内存管理的模拟(原理)

XJzy

对操作系统内存管理的模拟(原理)
在刚过去的最近的一段时间，老师在讲linux内存管理，她让我们每周都写周报告，看来她是用管理研究生的方式来对付我们了。哎，没办法，人在屋檐下，不得不低头，谁让咱是人家的学生捏。

　　其实老师也是对大家的一个督促，渐渐地，我发现，其实也周报告有一个好处就是把以前自己不太关注的问题摆到台面上，使自己对一个老的问题有了新的认识，这样其实也是不错的，还是非常感谢老师的良苦用心。

　　下面我将我对内存管理的一些问题的理解列出来，如果你看了之后有什么不同意见，可以留言给我，我很期待你的意见或者建议，上次写了一个ARM串行通信的例子，结果没人留言，不知道为什么，园子里没人做这方面的工作吗？对此表示怀疑，呵呵...

　　我是按照一问一答的形式进行的，所以在这也就这样了，最近心情起伏比较大，见谅。老师说做学问最忌讳的是摘抄不指明出处，所以我说明一下，一些这些总结是我从计算机的心智上总结归纳出来的，要是现在不说以后有人告发我，说我抄袭怎么办。

1.为什么要进行内存管理？
CPU需要两种信息：数据和代码，这些数据存放在内存，操作系统要控制CPU的运行，就要对内存进行管理。

2.几个难以区分的概念
用户空间 地址空间 进程空间 内核空间 虚拟内存（虚拟地址空间）
进程空间：进程所要的所有资源
内核空间：供内核使用的空间
虚拟内存：每个进程可以通过系统调用进入内核，所以内核空间其实是所有进程共享，从进程角度看，每个进程都可拥有4GB的虚拟地址空间（目前）

3.内存管理的目标
地址保护：一个程序不能访问另一个程序地址空间
地址独立：程序发出的地址应与物力主存地址无关

4.多道编程的内存管理
多道编程环境下，无法将程序加到固定的内存地址上，即：无法使用静态地址翻译，这就需要动态地址翻译

虚拟地址                    物理地址
用户进程——————>地址翻译器——————>物理内存

5.地址翻译的方法
一个程序是加载到内存事先划分好的某片区域，而且该程序是整个加在进去
物理地址 = 虚拟地址 + 程序所在区域的起始地址
多个程序需要地址保护，并进行合法访问

合法访问条件：程序所在区域起始地址<=有效地址<=程序所在区域起始地址 + 程序长度

动态地址翻译的优点：
1.灵活
2.　保护地址
3.实现虚拟内存

6. 内存管理方法
固定加载地址  固定分区  分固定分区  交换

7.页式内存管理
内存管理出现的问题：空间浪费   程序大小受限
页式内存管理克服外部碎片，增大程序的可用空间

8. 分页系统的优缺点
优点：
i.不产生外部碎片
ii.可以共享小的地址

缺点：
1.1.页表很大，占用空间
2.降低系统速度

9. 为什么要进行页面更换
不是因为一个页面过时而找一个新的页面来替换，而是因为需要使用新的页面而找一个过时的页面作为替换牺牲品

更换原则：
a) 最好是再也不会访问的页面
b) 选择一个没有修改过的页面

10.  页面更换算法
1.随机更换算
2.先进先出算
3.最有更换算法（判断算法优劣标准）
4.NRU(Not Recent Used)算法
5.LUR(Least Recent Used)算法

11.  为什么提出段式内存管理？
由于分页系统的缺点
分段管理实际是基本内存管理的一般化，而基本内存管理是分段管理的特例

12.  分段的优缺点
优点：
1.1.1.每个逻辑单元可独享一个虚拟地址空间，使编程空间大增
2.共享方便
3.对空间稀疏的程序，节省大量空间

缺点：
i. 产生外部碎片
ii. 一个段必须全部加载到内存

13.  为什么要使用段页式进行内存管理？
将分段和分页组合使用，同时获得分段和分页的好处，但又避免了单独分段和分页的缺陷
对操作系统内存管理的模拟（应用）
今天来续写，觉得昨天那种安排不合理，于是将原理与应用分两篇来写，不至于让大家和我看的有些烦。

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

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

• #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;            //当前分配算法
• static int pid = 0;                    //初始pid
• int flag = 0;                    //设置内存大小标志
  

复制代码


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

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

• //描述每一个空闲块的数据结构
• struct free_block_type{
•     int size;
•     int start_addr;
•     struct free_block_type *next;
• };
• //指向内存中空闲块链表的首指针
• struct free_block_type *free_block;
• /*每个进程分配到的内存块的描述*/
• 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;
  

复制代码


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

• /*初始化空闲块，默认为一块，可以指定大小及起始地址*/
• 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;
•     printf("init_free_block fished\n\n");
•     return fb;
• }
  

复制代码


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

• //显示菜单
• 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;
• }
  

复制代码


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

• // 设置当前的分配算法
• void set_algorithm(){
•     int algorithm;
•     printf("\t1 - First Fit\n");                    //首次适应算法，简称FF
•     printf("\t2 - Best Fit \n");                   //最佳适应算法
•     printf("\t3 - Worst Fit \n");                 //最差适应算法
•     scanf("%d", &algorithm);
•     if(algorithm>=1 && algorithm <=3)
•     ma_algorithm=algorithm;
•     rearrange(ma_algorithm); //按指定算法重新排列空闲区链表
• }
• //按指定的算法整理内存空闲块链表
• void rearrange(int algorithm){
•     switch(algorithm){
•         case MA_FF:   rearrange_FF(); break;
•         case MA_BF:   rearrange_BF(); break;
•         case MA_WF:  rearrange_WF(); break;
•     }
• }
• //按FF算法重新整理内存空闲块链表
• void rearrange_FF(){
•     struct free_block_type *position, *min, *current;
•     int size;
•     int start_addr;
•     printf("Rearrange free blocks for FF \n\n");
•     position = free_block;
•     //空闲块按地址顺序进行简单选择排序
•     while (position != NULL) {
•     min = position;
•                 current = position->next;
•                 while(current != NULL){
•         if( current->start_addr < min->start_addr) {
•                                          min = current;
•                                 }
•                     current = current->next;
•                 }
•                 size = position->size;
•                 position->size = min->size;
•                 min->size = size;
•                 start_addr = position->start_addr;
•                 position->start_addr = min->start_addr;
•                 min->start_addr = start_addr;
•                 position = position->next;
•      }
• }
• //按BF算法重新整理内存空闲块链表
• void rearrange_BF(){
•     struct free_block_type *position, *min, *current;
•     int size;
•     int start_addr;
•     printf("Rearrange free blocks for BF\n\n");
•     position = free_block;
•     //空闲块按由小到大进行简单选择排序
•     while (position != NULL) {                min = position;
•     current = position->next;
•                 while(current != NULL){
•         if( current->size < min->size) {
•             min = current;
•                                 }
•         current = current->next;
•                 }
•                 size = position->size;
•     position->size = min->size;
•     min->size = size;
•     start_addr = position->start_addr;
•     position->start_addr = min->start_addr;
•     min->start_addr = start_addr;
•     position = position->next;
•     }
• }
• //按WF算法重新整理内存空闲块链表
• void rearrange_WF(){
•     struct free_block_type *position, *min, *current;
•     int size;
•     int start_addr;
•     printf("Rearrange free blocks for WF \n\n");
•     position = free_block;
•     //空闲块按由大到小进行简单选择排序
•     while (position != NULL) {                min = position;
•     current = position->next;
•         while(current != NULL){
•         if( current->size > min->size) {
•             min = current;
•                                 }
•         current = current->next;
•     }
•     size = position->size;
•     position->size = min->size;
•     min->size = size;
•     start_addr = position->start_addr;
•     position->start_addr = min->start_addr;
•     min->start_addr = start_addr;
•     position = position->next;
•     }
• }
  

复制代码


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

• //创建新的进程，主要是获取内存的申请数量
• 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->process_name字符数组中去
•     ab->pid = pid;
•     printf("Memory for %s:", ab->process_name);
•     scanf("%d", &size);
•     if(size>0) ab->size=size;
•     ret = allocate_mem(ab);            // 从空闲区分配内存，ret==1表示分配ok
• //如果此时allocated_block_head尚未赋值，则赋值
•     if((ret==1) &&(allocated_block_head == NULL)){
•         allocated_block_head=ab;
•         printf("new_process was created\n\n");
•         return 1;
•         }
•     //分配成功，将该已分配块的描述插入已分配链表
•     else if (ret==1) {
•         ab->next=allocated_block_head;
•         allocated_block_head=ab;
•         printf("new_process was created\n\n");
•         return 2;
•         }
•     else if(ret==-1){ //分配不成功
•         printf("Allocation fail\n");
•         free(ab);
•         return -1;
•         }
•     return 3;
• }
  

复制代码


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

• //分配内存模块
• int allocate_mem(struct allocated_block *ab){
•     struct free_block_type *fbt, *pre;
•     int request_size=ab->size;
•     int sum_size = 0;
•     fbt = pre = free_block;
•     while(fbt!=NULL){
•         if( (fbt->size - request_size) >= MIN_SLICE ){    //分配后空闲空间足够大，则分割
•             ab->start_addr = fbt->start_addr;
•             fbt->size = fbt->size - request_size;
•             fbt->start_addr = fbt->start_addr + request_size;
•             rearrange(ma_algorithm);
•             return 1;
•         }
•         else if( (fbt->size > request_size) && (fbt->size - request_size < MIN_SLICE) ){    //分割后空闲区成为小碎片，一起分配
•              ab->start_addr = fbt->start_addr;
•             ab->size = fbt->size;
•             if(fbt == free_block) {
•                 free_block = fbt->next;
•                 free(fbt);
•             }
•             else{
•                 pre->next = fbt->next;
•                 free(fbt);
•             }
•             rearrange(ma_algorithm);
•             return 1;
•         }
•         sum_size += fbt->size;
•         pre = fbt;
•         fbt = fbt->next;
•     }
•     if(sum_size < request_size)
•         return -1;
•     else {
•         compress(ab,request_size,sum_size);
•         return 1;
•     }
• }
  

复制代码


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

• //**********紧缩后分配
• void compress(struct allocated_block *ab, int request_size, int sum_size){
•     struct allocated_block *ab1, *ab2;
•     struct free_block_type *fb1, *fb2;
•     ab1 = allocated_block_head;
•     ab1->start_addr = 0;
•     ab2 = ab1->next;
•     while(ab2 != NULL){
•         ab2->start_addr = ab1->start_addr + ab1->size;
•         ab1 = ab2;
•         ab2 = ab2->next;
•     }
•     printf("free block was compressed\n\n");
•     ab->start_addr = ab1->start_addr + ab1->size;
•     fb1 = free_block->next;        //紧缩后只有一个空闲块，无需排序
•     while(fb1 != NULL){            //其他空闲块释放
•         fb2 = fb1->next;
•         free(fb1);
•         fb1 = fb2;
•     }
•     printf("free block was set free\n\n");
•     free_block->start_addr = ab->start_addr + ab->size;
•     free_block->size = sum_size - request_size;
•     free_block->next = NULL;
•     if( (sum_size >= request_size) && (sum_size - request_size < MIN_SLICE) ) {
•         ab->size = sum_size;
•         free_block->start_addr = -1;
•         free_block->size = 0;
•     }
• }
  

复制代码


上面就是碎片整理的代码。
下面介绍杀死一个进程并对其内存空间的释放与回收：

• void do_exit(){        //释放空间
•     struct free_block_type *fb1, *fb2;
•     struct allocated_block *ab1, *ab2;
•     fb1 = free_block;
•     while(fb1 !=NULL){
•         fb2 = fb1->next;
•         free(fb1);
•         fb1 = fb2;
•     }
•     printf("free_block_type free\n\n");
•     ab1 = allocated_block_head;
•     while (ab1 != NULL){
•         ab2 = ab1->next;
•         free(ab1);
•         ab1 = ab2;
•     }
•     printf("allocated_block free\n\n");
• }
  

复制代码


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

• // 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况
• 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;
• }
  

复制代码


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

• main(){
•     char choice;
•     pid=0;
•     free_block = init_free_block(mem_size); //初始化空闲区
•     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);            //释放链表并退出
•         default: break;
•         }
•     }
• }