操作系统实验内存分配（链表实现）

#include #include #include struct memory //内存块 { char pro; //内存块的内容，'o'代表操作系统，'\\0'代表空闲块，其它代表被进程占有 int size; //内存块的大小 int begin; //内存块的起始地址 memory *next; //下一块内存块 };

memory *base; //代表内存，一个头指针,内存总大小为256k void init(int manage) //内存的初始化 { memory *p,*q; if(base!=NULL) //这一块是释放链表 { p=base; while(p) { q=p->next; delete p; p=q; } } base=new memory; //操作系统，大小5k,起始地址是0k base->begin=0; base->pro='o'; base->size=5; if(manage==0) //静态内存，初始化7个内存块，第一个内存块是操作系统 { p=base; q=new memory; //空闲块1，大小20，起始地址5k q->begin=5; q->pro=0; q->size=20; p->next=q; p=q; q=new memory; //空闲块2，大小50，起始地址25k q->begin=25; q->pro=0;

q->size=50; p->next=q; p=q; q=new memory; //空闲块3，大小30，起始地址75k q->begin=75; q->pro=0; q->size=30; p->next=q; p=q; q=new memory; //空闲块4，大小45，起始地址105k q->begin=105; q->pro=0; q->size=45; p->next=q; p=q; q=new memory; //空闲块5，大小54，起始地址150k q->begin=150; q->pro=0; q->size=54; p->next=q; p=q; q=new memory; //空闲块6，大小52，起始地址204k q->begin=204; q->pro=0; q->size=52; p->next=q; q->next=NULL; } else //动态内存，只有一个大的内存块 { p=new memory; //空闲块251k,起始地址是5k p->begin=5; p->pro=0; p->size=251; p->next=NULL; base->next=p; } }

void assign(memory *q,char pro,int size) //动态，给进程pro在内存块q->next上分配size大小，q不为空且q->next不为空

{ //因为要进行插入操作，所以传的是要分配内存块的前指针 memory *p=q->next; memory *temp=new memory; temp=new memory; //代表进程pro的内存块 temp->begin=p->begin; temp->size=size; temp->pro=pro; q->next=temp; if(p->size!=size) //插入的内存块小于空闲区块 { p->size=p->size-size; p->begin=temp->begin+temp->size; temp->next=p; } else //插入的内存块等于空闲区块 { temp->next=p->next; delete p; } }

int ff(int manage,char pro,int size) //最先适应法 { memory *p=base; memory *q=p; while(p) //遍历内存找到第一个适合进程pro的内存块，保存它的前指针 { if(p->sizepro!=0) { q=p; p=p->next; } else break; } if(p==NULL)return 0; //没找到,返回0 else //找到了,返回1 { if(manage==0)p->pro=pro; //静态，直接让进程进驻内存 else assign(q,pro,size); //动态，调用assign来给进程pro分配 } return 1; }

int bf(int manage,char pro,int size) //最佳适应法

{ memory *p=base,*temp=NULL,*q,*front; int min=256; while(p) //遍历内存找到最佳的内存块，保存它的前指针 { if(p->pro==0&&p->size>=size&&min>p->size) { min=p->size; front=q; temp=p; } q=p; p=p->next; } if(temp==NULL)return 0; //没找到,返回0 else { if(manage==0)temp->pro=pro; //静态，直接让进程进驻内存 else assign(front,pro,size); //动态，调用assign来给进程pro分配 } return 1; }

int wf(int manage,char pro,int size) //最坏适应法 { memory *p=base,*temp=NULL,*q,*front; int max=0; while(p) //遍历内存，找到最大的一块内存 { if(p->pro==0&&p->size>=size&&maxsize) { max=p->size; front=q; temp=p; } q=p; p=p->next; } if(temp==NULL)return 0; //没找到,返回0 else //找到了,返回1 { if(manage==0)temp->pro=pro; //静态，直接让进程进驻内存 else assign(front,pro,size); //动态，调用assign来给进程pro分配 } return 1;

}

int delpro(int manage,char pro) //撤销进程，可能要进行内存块的合并 { memory *p=base,*q; while(p) //遍历内存，寻找进程pro { if(p->pro!=pro) { q=p; p=p->next; } else break; } if(p==NULL)return 0; //没找到,返回0 else //找到了,返回1 { if(manage==0)p->pro=0; //静态内存，直接撤销进程，不用内存块合并 else //动态内存，可能要进行内存合并，分4种情况 { if(q->pro!=0) { if(p->next==NULL||p->next->pro!=0) //前后内存块都不是空闲块 p->pro=0; else //前内存块不是空闲块，后内存块是空闲块 { q->next=p->next; p->next->begin=p->begin; p->next->size=p->size+p->next->size; delete p; } } else { if(p->next==NULL||p->next->pro!=0) //前内存块是空闲块，后内存块不是空闲块 { q->next=p->next; q->size=q->size+p->size; delete p; } else //前后内存块都是空闲块 { q->next=p->next->next;

q->size=q->size+p->size+p->next->size; delete p->next; delete p; } } } } return 1; }

void print(char ch,int begin,int size) //根据内存块内容，格式化输入一块内存块 { switch(ch) { case 'o':printf(\操作系统区\\t=k\\t=k~=k\\n\ case 0 :printf(\空闲区 \\t=k\\t=k~=k\\n\ default :printf(\进程%c \\t=k\\t=k~=k\\n\ } }

void show() //格式化显示内存的储存情况 { memory *p=base; int count=1; cout<<\内存现在的储存情况是：\ printf(\块号\\t 内容\\t\\t大小\\t起始-结束地址\\n\ while(p) { printf(\ \ print(p->pro,p->begin,p->size); p=p->next; } }

void del_pro(int manage) //撤销进程pro，调用delpro { memory *p=base; char pro,result; cout<<\请输入你要撤销的进程的名字：\ cin>>pro; if(pro=='o')cout<<\操作系统不可撤销\ else { result=delpro(manage,pro); if(result==0)cout<<\没有找到进程\撤销失败\ else cout<<\进程\撤销成功\ }

}

void assign_pro(int manage) //给进程pro根据选择情况分配内存 { int size,result=-1; char choose ,pro; cout<<\请输入进程的名字:\ cin>>pro; cout<<\请输入进程请求的内存大小:\ cin>>size; cout<<\请选择分配算法：1，最先适应法。2，最佳适应法。3，最坏适应法\ cin>>choose; switch(choose) { case '1': result=ff(manage,pro,size); break; case '2': result=bf(manage,pro,size); break; case '3': result=wf(manage,pro,size); break; } if(result==0)cout<<\进程\分配失败\ else if(result==1)cout<<\进程\分配成功\ else cout<<\输入错误\}

void childmenu(int manage) //子菜单 { char choice; init(manage); while(1) { system(\ if(manage==0)cout<<\静态分配\ else cout<<\动态分配\ show(); cout<<\请选择操作：\\n1、建立进程并分配\\n2、撤销进程\\n3、返回上一目录(内存将被初始化)\ cin>>choice; if(choice=='1') { assign_pro(manage);system(\ }

else if(choice=='2') { del_pro(manage);system(\ } else if(choice=='3')break; } }

void main() { char choice; int manage; while(1) //主菜单 { system(\ cout<<\内存分配算法演示\ cout<<\、静态分配\\n2、动态分配\\n3、退出程序\ cin>>choice; if(choice=='1')manage=0; else if(choice=='2')manage=1; else if(choice=='3')break; childmenu(manage); } }

本文来源：https://www.bwwdw.com/article/t93p.html