这个代码模拟实现了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; }