模拟linux内存管理代码 转

这个代码模拟实现了linux内存管理的三个算法ff、wf、bf。这三个算法都是连续分配的方式，这种方式的缺点就是内存碎片很难被再次利用。

#include <stdio.h> #include <stdlib.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;           /*当前分配算法*/ static int pid=0;  /*初始pid*/ int flag = 0;/*设置内存大小标志*/ /*描述每一个空闲块的数据结构*/ 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;

void king(struct free_block_type *h)//为有参的函数 { struct free_block_type *p; //对相邻区的处理，和对size==0的处理 if(h->next!=NULL)//感觉这里不对 {  if((h->start_addr+h->size)==h->next->start_addr)  {  p=h->next;  h->size=h->size+p->size;  h->next=p->next;  free(p);  king(h);  } else if(h->next!=NULL) king(h->next); } }

/*连表的销毁*/ void freenode(struct free_block_type *h) {  struct free_block_type *p;  while(h!=NULL)  {p=h;  h=h->next;   free(p);  } } void freenode1(struct allocated_block *h) {  struct allocated_block *p;  while(h!=NULL)  {p=h;  h=h->next;   free(p);  } }

/*初始化空闲块，默认为一块，可以指定大小及起始地址*/ 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算法重新整理内存空闲块链表*/ void rearrange_FF()//按照地址递增顺序 { struct free_block_type *head,*p,*q,*s,*m,*h; h=free_block; m=free_block; // h=h->next;没有头节点这里为了处理方便，暂且申请头结点 head=(struct free_block_type *)malloc(sizeof(struct free_block_type));  head->next=NULL;  s=head;//保存头结点地址  p=(struct free_block_type *)malloc(sizeof(struct free_block_type));  p->size=h->size;  p->start_addr=h->start_addr;  s->next=p; p->next=NULL;  h=h->next;

 while(h!=NULL)  {   q=(struct free_block_type *)malloc(sizeof(struct free_block_type));   q->size=h->size;   q->start_addr=h->start_addr;   h=h->next;//记录下一个节点   head=s;   p=head->next;   while(head!=NULL)   {    if(head->next==NULL)    {     head->next=q;  q->next=NULL;     break;    }    else if(q->start_addr<p->start_addr)//这里可以修改排序顺序    {     head->next=q;  q->next=p;     break;   }

   else    {head=head->next;    p=head->next;    }   }  }  freenode(m);  m=s;  s=s->next;  free(m);  free_block=s; } /*按BF算法重新整理内存空闲块链表*/ void rearrange_BF()//按照容量从小到大 {     struct free_block_type *head,*p,*q,*s,*m,*h;  h=free_block; m=free_block; // h=h->next;没有头节点这里为了处理方便，暂且申请头结点 head=(struct free_block_type *)malloc(sizeof(struct free_block_type));  head->next=NULL;  s=head;//保存头结点地址  p=(struct free_block_type *)malloc(sizeof(struct free_block_type));  p->size=h->size;  p->start_addr=h->start_addr;  s->next=p; p->next=NULL;  h=h->next;

 while(h!=NULL)  {   q=(struct free_block_type *)malloc(sizeof(struct free_block_type));   q->size=h->size;   q->start_addr=h->start_addr;   h=h->next;//记录下一个节点   head=s;   p=head->next;   while(head!=NULL)   {    if(head->next==NULL)    {     head->next=q;  q->next=NULL;     break;    }    else if(q->size<p->size)//这里可以修改排序顺序    {     head->next=q;  q->next=p;     break;   }

   else    {head=head->next;    p=head->next;    }   }  }  freenode(m);  m=s;  s=s->next;  free(m);  free_block=s; } /*按WF算法重新整理内存空闲块链表*/ void rearrange_WF()//按照容量从大到小 {     struct free_block_type *head,*p,*q,*s,*m,*h;  h=free_block; m=free_block; // h=h->next;没有头节点这里为了处理方便，暂且申请头结点 head=(struct free_block_type *)malloc(sizeof(struct free_block_type));  head->next=NULL;  s=head;//保存头结点地址  p=(struct free_block_type *)malloc(sizeof(struct free_block_type));  p->size=h->size;  p->start_addr=h->start_addr;  s->next=p; p->next=NULL;  h=h->next;

 while(h!=NULL)  {   q=(struct free_block_type *)malloc(sizeof(struct free_block_type));   q->size=h->size;   q->start_addr=h->start_addr;   h=h->next;//记录下一个节点   head=s;   p=head->next;   while(head!=NULL)   {    if(head->next==NULL)    {     head->next=q;  q->next=NULL;     break;    }    else if(q->size>p->size)//这里可以修改排序顺序    {     head->next=q;  q->next=p;     break;   }

   else    {head=head->next;    p=head->next;    }   }  }  freenode(m);  m=s;  s=s->next;  free(m);  free_block=s; }

/*按指定的算法整理内存空闲块链表*/ void rearrange(int algorithm){     switch(algorithm){         case MA_FF:  rearrange_FF(); break;         case MA_BF:  rearrange_BF(); break;         case MA_WF: rearrange_WF(); break;         } }

/* 设置当前的分配算法 */ void set_algorithm(){     int algorithm;     printf("/t1 - First Fit/n");     printf("/t2 - Best Fit /n");     printf("/t3 - Worst Fit /n");     scanf("%d", &algorithm);     if(algorithm>=1 && algorithm <=3)               ma_algorithm=algorithm;     //按指定算法重新排列空闲区链表     rearrange(ma_algorithm); } /*分配内存模块*/ int allocate_mem(struct allocated_block *ab) {

    struct free_block_type  *h;     int request_size=ab->size;  rearrange(ma_algorithm);//这里虽然能够排序，但是地址发生了变化   h=free_block; while(h!=NULL) {  if(h->size>=request_size)   break;  h=h->next; } if(h==NULL) {  printf("不符合分配条件");  return -1; } else {  printf("符合分配条件");  if(h->size-request_size<MIN_SLICE)          h->size=0;//注意这里只是修改了链表中值的大小，链表的本体还在  else   h->size=h->size-request_size;    ab->start_addr=h->start_addr;    h->start_addr=ab->start_addr+ab->size;  return 1; }

}

struct allocated_block *find_process(int p) {  struct allocated_block *h;  h=allocated_block_head; while(h!=NULL) {  if(h->pid==p)   break;  else   h=h->next; } return h; }

/*删除进程，归还分配的存储空间，并删除描述该进程内存分配的节点*/ void kill_process(){     struct allocated_block *ab;     int p;//这里的pid和全局变量的pid怎么说     printf("Kill Process, pid=");     scanf("%d", &p);     ab=find_process(p);//注意这个函数,可能是遗漏     if(ab!=NULL){         free_mem(ab); /*释放ab所表示的分配区*/         dispose(ab);  /*释放ab数据结构节点*/         } } /*将ab所表示的已分配区归还，并进行可能的合并*/ int free_mem(struct allocated_block *ab){     int algorithm = ma_algorithm;//算法     struct free_block_type *h,*fbt;  h=free_block;   fbt=(struct free_block_type*) malloc(sizeof(struct free_block_type));     fbt->size=ab->size;  fbt->start_addr=ab->start_addr;

    // 进行可能的合并，基本策略如下     // 1. 将新释放的结点插入到空闲分区队列末尾     // 2. 对空闲链表按照地址有序排列     // 3. 检查并合并相邻的空闲分区     // 4. 将空闲链表重新按照当前算法排序    // 请自行补充…… while(h->next!=NULL) h=h->next; h->next=fbt; fbt->next=NULL; rearrange_FF();//2 king(free_block);//3 rearrange(ma_algorithm);//4  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;     ret = allocate_mem(ab);  /* 从空闲区分配内存，ret==1表示分配ok*/   /*如果此时allocated_block_head尚未赋值，则赋值*/     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 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;    }

/* 显示当前内存的使用情况，包括空闲区的情况和已经分配的情况 */ 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){   if(fbt->size==0)   {    fbt=fbt->next;    continue;   }         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;     }

int main(){     char choice;      pid=0;     free_block = init_free_block(mem_size); //初始化空闲区     while(1)  {     display_menu();    //显示菜单     fflush(stdin);//这里的这个函数，linux下可以用其他的代替     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': freenode(free_block);freenode1(allocated_block_head); exit(0);    //释放链表并退出         default: break;      }    }  return 0; }