存储器管理动态分区分配算法的模拟

1、计算机操作系统课程设计报告指导老师：吴 江 红 题 目：存储器管理-动态分区分配算法的模拟 班 级： 031024班 姓 名：张佳（03102417）赵慧（03102419） 一、 设计任务： 编写程序完成“存储器管理动态分区分配算法”的模拟，设计主界面来灵活选择各算法，其中包括首次适应算法，最佳适应算法，最坏适应算法以及回收算法。二、 设计目的：通过课程设计，进一步理解内存分配算法的思想，并在此基础上熟练编程语言的具体的操作。三、 设计思想：内存管理有空区表管理空闲得空间，空区表记录某个空闲块的大小和首地址信息，建立空区表的双向链表，对空区链表的操作达到内存分配的管理。四、 设计方案：建立空

2、区表的双向链表结构，建立已分配表的双向链表结构；分别建立最先适应、循环最先适应、最佳适应和最差适应得类结构；采用c+builder作界面设计；设计界面如下：五、 核心代码： 作业数据类型的定义#ifndef job_h#define job_htypedef struct job int size;/作业大小 int address;/作业首地址 ansistring name;/作业名(ansistring是c+builder的字符串类型)job;#endif 最先适应算法的代码：#ifndef firstfit_h#define firstfit_h#include "job.h

3、"/最先适应算法头文件class first_fit_link;class linknodefriend class first_fit_link;private: int size;/作业大小 int address;/作业首地址 linknode * forward; linknode * next;public: linknode(int s,int a,linknode * f,linknode * n)/初始化 size=s; address=a; forward=f; next=n; ;class first_fit_linkprivate: linknode * hea

4、d;/头指针 linknode * rear;/尾指针 linknode * work;/标记指针public: first_fit_link()/初始化 head=null; rear=null; work=null; first_fit_link()/析构函数 linknode * point1; while(head!=null) point1=head; head=head->next; delete point1; void init(int address,int size);/初始化建空区表 job returnjob();/返回链表元素 int allot(int siz

5、e);/分配,成功返回地址，否则返回无穷大 void free(int address,int size);/释放 bool over();/判断是否输出完节点元素;/空区表的建立void first_fit_link:init(int address,int size) if(head=null)/如果是空链，新建一个链 head=rear=work=new linknode(size,address,null,null);/申请新的节点 else linknode * point1=head; linknode * point2; while(point1!=null) if(addres

6、s<point1->address) point2=new linknode(size,address,null,null); if(point1=head)/如果是首部，则改动头指针 point2->next=head; head->forward=point2; head=point2; work=point2; else/如果插入点在链中 point2->forward=point1->forward; point2->next=point1; point1->forward->next=point2; point1->forw

7、ard=point2; break;/插入完成，退出 else point1=point1->next;/寻找下一个位置 if(point1=null)/如果插入点在链尾，改动尾指针 point2=new linknode(size,address,rear,null); rear->next=point2; rear=point2; /分配函数，如果分配成功，返回作业地址，否则返回1000int first_fit_link:allot(int size) int address=1000; linknode * point1=head; linknode * point2; w

8、hile(point1!=null) if(size<point1->size)/如果申请空间小于该节点，对该节点改动 address=point1->address; point1->size=point1->size-size; point1->address=point1->address+size; return address;/分配成功，返回address if(size=point1->size)/如果申请空间与该节点大小一致，删除该节点 if(point1=head)/如果是头节点 address=head->address

9、; point2=head; head=head->next; head->forward=null; work=head; delete point2; return address;/分配成功，返回address if(point1=rear)/如果是尾节点 address=rear->address; point2=rear; rear=rear->forward; rear->next=null; delete point2; return address;/分配成功，返回address if(point1!=head&&point1!=r

10、ear) address=point1->address; point2=point1->forward; linknode * point3=point1->next; point2->next=point3; point3->forward=point2; delete point1; return address;/分配成功，返回address point1=point1->next;/寻找下一个位置 if(point1=null) return address;/没有合适的空间，分配不成功，返回1000 /释放空间函数void first_fit_l

11、ink:free(int address,int size) linknode * point1=head; linknode * point2; while(point1!=null) if(address<point1->address) if(point1=head)/如果point1是头指针 if(address+size)=point1->address) head->address=address; head->size=head->size+size; break; else point2=new linknode(size,address,n

12、ull,head); head->forward=point2; head=point2; break; if(point1->forward->address+point1->forward->size)=address)/如果与前一个相邻 if(address+size)=point1->address)/如果同时与后一个相邻, 合并三者，删除point1 point2=point1->forward; point2->size=point2->size+size+point1->size; if(point1=rear)/如果p

13、oint1是尾指针 rear=point2; delete point1; break; else point2->next=point1->next; point1->next->forward=point2; delete point1; break; else /只与前一个相邻，则与前一个合并 point1->forward->size=point1->forward->size+size; break; if(address+size)=point1->address)/如果与后一个相邻 point1->size=point1

14、->size+size;/与后一个合并 break; /如果前后都不相邻，申请新的节点 point2=new linknode(size,address,point1->forward,point1); point1->forward->next=point2; point1->forward=point2; point1=point1->next; if(point1=null)/ if(rear->address+rear->size)=address)/如果与rear相邻 rear->size=rear->size+size;

15、else /另立新的rear point2=new linknode(size,address,rear,null); rear->next=point2; rear=point2; /判断是否输出完节点bool first_fit_link:over() if(work=null) work=head; return true; else return false; /返回链表元素job first_fit_link:returnjob() linknode * point1=work; job pointnum; if(point1!=null) pointnum.size=poin

16、t1->size; pointnum.address=point1->address; work=work->next; return pointnum;#endif最佳适应算法代码#ifndef bestfit_h#define bestfit_h#include "job.h"/最佳适应算法头文件class bestfit_link;class bestnode friend class bestfit_link;private: int size;/作业大小 int address;/作业首地址 bestnode * forward; bestnod

17、e * next;public: bestnode(int s,int a,bestnode * f,bestnode * n)/初始化 size=s; address=a; forward=f; next=n; ;class bestfit_linkprivate: bestnode * head;/头指针 bestnode * rear;/尾指针 bestnode * work;/标记指针public: bestfit_link()/初始化 head=null; rear=null; work=null; bestfit_link()/析构函数 bestnode * point1; whi

18、le(head!=null) point1=head; head=head->next; delete point1; void init(int address,int size);/初始化建空区表 job returnjob();/返回链表元素 bool over();/判断是否输出完节点元素 int allot(int size);/分配;/分配函数，如果分配成功，返回作业地址，否则返回1000int bestfit_link:allot(int size) int address=1000; bestnode * point1=head; bestnode * point2; w

19、hile(point1!=null) if(size<point1->size)/如果申请空间小于该节点，对该节点改动 address=point1->address; point1->size=point1->size-size; point1->address=point1->address+size; return address;/分配成功，返回address if(size=point1->size)/如果申请空间与该节点大小一致，删除该节点 if(point1=head)/如果是头节点 address=head->address

20、; point2=head; head=head->next; head->forward=null; work=head; delete point2; return address;/分配成功，返回address if(point1=rear)/如果是尾节点 address=rear->address; point2=rear; rear=rear->forward; rear->next=null; delete point2; return address;/分配成功，返回address if(point1!=head&&point1!=r

21、ear) address=point1->address; point2=point1->forward; bestnode * point3=point1->next; point2->next=point3; point3->forward=point2; delete point1; return address;/分配成功，返回address point1=point1->next;/寻找下一个位置 if(point1=null) return address;/没有合适的空间，分配不成功，返回1000 /按空间大小递增建立链表void bestfi

22、t_link:init(int address,int size) if(head=null) head=rear=work=new bestnode(size,address,null,null); else bestnode * point1=head; bestnode * point2; while(point1!=null) if(size<=point1->size) point2=new bestnode(size,address,null,null); if(point1=head)/如果是首部，则改动头指针 point2->next=head; head-&

23、gt;forward=point2; head=point2; work=point2; else/如果插入点在链中 point2->forward=point1->forward; point2->next=point1; point1->forward->next=point2; point1->forward=point2; break;/插入完成，退出 else point1=point1->next;/寻找下一个位置 if(point1=null)/如果插入点在链尾，改动尾指针 point2=new bestnode(size,address,rear,null); rear->next=point2; rear=point2; /判断是否输出完节点bool bestfit_link:over() if(work=null) work=head; return true; else return false; /返回链表元素job bestfit_link:returnjob() bestnode * point1=work; job