模拟设计动态分区存储管理的分配与回收

1、学 号： 课 程 设 计题 目模拟设计动态分区存储管理的分配与回收学 院计算机科学与技术学院专 业班 级姓 名指导教师吴利军2013年01月16日课程设计任务书学生姓名： 专业班级： 指导教师： 吴利军 工作单位： 计算机科学与技术学院 题 目: 模拟设计动态分区存储管理的分配与回收初始条件：1预备内容：阅读操作系统的内存管理章节内容，理解动态分区存储管理，掌握动态分区管理内存的分配和回收过程。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1采用动态分区管理方案实施内存分配和回收。能够处理以下的情形 能够输入给定的内

2、存大小，进程的个数，每个进程所需内存空间的大小； 当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况； 当某进程撤消时，显示内存回收后内存空间的使用情况（注意回收后的合并）。2设计报告内容应说明： 需求分析； 功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安

3、排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日模拟设计动态分区存储管理的分配与回收1.需求分析1.1动态分区动态分区分配又称为可变式分区分配，是一种动态划分存储器的分区方法。不事先将内存划分成一块块的分区，而是在作业进入内存时，根据作业的大小动态地建立分区，并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。这种分配方法管理简单，只需小量的软件和硬件支持，便于用户了解和使用。进程的大小与某个

4、分区大小相等，从而主存的利用率有所提高。动态分区虽然解决了固定分区所造成的内存浪费问题，但随着进程的动态变化，系统也将进行一系列的内存空间的分配和回收活动，每个进程所释放的内存空间就作为一个空闲区加以再分配。由于再分配时只能分给不大于当前空闲区的进程，所以每个空闲区再分配时多数情况下会变成两个区：一个区分给当前请求内存空间的进程，剩下的空间依然作为空闲区等待分配。这样，分配后剩余的空闲区将会越分越少，从而导致内存中存在大量分散的小空闲区，这种小得不能再利用的空闲区称之为“碎片”。1.2分配内存 系统利用某种分配算法，从空闲分区表/链中找到所需大小的分区。size(size是事先规定的不再切割的

5、剩余分区的大小)，说明多余部分大小，可不再切割，将整个分区分配给请求者；否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中，然后，将分配区的首址返回给调用者。 1.3回收内存 当作业执行结束时，应回收已使用完毕的分区。系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。回收分区与已有空闲分区的相邻情况有以下四种： 回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首地址,大小为二者之和。 回收分区下邻接一个空闲分区,合并后首地址为回收分区的首地址,大小为二者之和。 回收分区上

6、下邻接空闲分区,合并后首地址为上空闲分区的首地址,大小为三者之和。 回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息。2.功能设计2.1数据结构2.1.1空闲分区表用来登记系统中的空闲分区(分区号,分区起始地址,分区大小及状态). 分区号大小KB起始地址KB状态132352空闲2空表目3520504空闲4空表目52.1.2 空闲分区链用链头指针将系统中的空闲分区链接起来，构成空闲分区链。每个空闲分区的起始部分存放相应的控制信息(如大小,指向下一空闲分区的指针等).2.2 模块说明2.12.1 分区说明表struct PST/partition specificatio

7、n table int id;/分区号int addr;/起始地址 int size;/分区长度 Status state;/状态;2.2.2 双向链表struct Node/双向链表结点 PST data; Node *back;/前驱Node *next;/后继 Node() back=NULL; next=NULL; Node(int id,int size)data.ID=id;data.size=size;back=NULL;next=NULL;2.2.3 最先适应算法空闲分区（链）按地址递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的

8、空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。算法特点:优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。Status FFA(int id,int size)/head fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;Node *cur=head-next;while(cur)

9、if(cur-data.state=FREE&cur-data.size=size)/如果空闲块大小刚好与请求大小相等,直接分配 cur-data.ID=id;cur-data.state=BUSY;return OK;break;if(cur-data.state=FREE&cur-data.sizesize)/如果大于temp-back=cur-back;temp-next=cur;cur-back-next=temp;temp-data.addr=cur-data.addr;cur-back=temp;cur-data.addr=cur-data.addr+size;cur-data.s

10、ize=cur-data.size-size;return OK;break;cur=cur-next;return ERROR;2.2.4 最佳适应算法空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍留在空闲分区表/链中。 算法特点：若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，,从而保留

11、了大的空闲分区,但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。Status BFA(int id,int size)/best fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int min;/记录符合满足请求的最小空闲块大小Node *fit;/指向采用最佳适应算法的插入位置Node *cur=head-next;while(cur)/取得第一个可以分配的位置（不一定是最佳位置）if(cur-data.st

12、ate=FREE&cur-data.size=size)fit=cur;min=cur-data.size-size;break;cur=cur-next;while(cur)if(cur-data.state=FREE&cur-data.size=size)/如果相等直接分配 cur-data.state=BUSY;cur-data.ID=id;return OK;break;if(cur-data.state=FREE&cur-data.sizesize)/获取最佳位置if(cur-data.size-sizedata.size-size;fit=cur;cur=cur-next;if(f

13、it)/若最佳，插入temp-back=fit-back;temp-next=fit;fit-back-next=temp;temp-data.addr=fit-data.addr;fit-back=temp;fit-data.addr=fit-data.addr+size;fit-data.size=fit-data.size-size;return OK;elsereturn ERROR;2.2.5 最坏适应算法空闲分区表/链按容量大小递减的次序排列。在进行内存分配时，从空闲分区表的首开始顺序查找，直到找到第一个比之大的空闲分区为止。剩下的空闲仍留在空闲分区表/链中。算法特点：总是挑选满足

14、作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。Status WFA(int id,int size)/worst fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int max;/记录符合满足请求的最小空闲块大小Node *fit;/指向采用最坏适应算法的插入位置Node *cur=head-next;while(cur)/取得第一个可以分配的位置（不一定是最佳位置）if(cur-da

15、ta.state=FREE&cur-data.size=size)fit=cur;max=cur-data.size-size;break;cur=cur-next;while(cur)/*if(cur-data.state=FREE&cur-data.size=size)/如果相等直接分配 cur-data.state=BUSY;cur-data.ID=id;return OK;break;*/if(cur-data.state=FREE&cur-data.sizesize)/获取最佳位置if(cur-data.size-sizemax)max=cur-data.size-size;fit=

16、cur;cur=cur-next;if(fit)/若最佳，插入temp-back=fit-back;temp-next=fit;fit-back-next=temp;temp-data.addr=fit-data.addr;fit-back=temp;fit-data.addr=fit-data.addr+size;fit-data.size=fit-data.size-size;return OK;elsereturn ERROR;3.开发平台及源程序的主要部分3.1开发平台 本次课程设计开发平台Microsoft Visual C+ 6.0 3.2 源程序的主要部分/#define MAX

17、_LEN 1024/定义内存大小，1024字节enum StatusFREE,BUSY,OK,ERROR;struct PSTstruct Nodeint area;/输入内存空间Node *head,*last;void Init(int area)head=new Node(); last=new Node();head-next=last;last-back=head;last-data.addr=0;last-data.ID=0;last-data.size=area; last-data.state=FREE;Status FFA(int id,int size)Status BFA

18、(int id,int size) Status WFA(int id,int size)void Free(int id) Node *cur=head; while(cur) if(cur-data.ID=id) cur-data.state=FREE; cur-data.ID=FREE; if(cur-back-data.state=FREE)/与前面的空闲块相连 cur-back-data.size+=cur-data.size; cur-back-next=cur-next; cur-next-back=cur-back; if(cur-next-data.state=FREE)/与

19、后面的空闲块相连 cur-data.size+=cur-next-data.size; cur-next-next-back=cur-back; cur-back-next=cur-next; break; cur=cur-next; Status Assign(int choice)int id,size;coutid;coutendlsize;if(size=0)cout输入错误!endl;return ERROR;if(choice=1)if(FFA(id,size)=OK)cout分配成功！endl;elsecout分配失败！endl;else if(choice=2)if(BFA(i

20、d,size)=OK)cout分配成功！endl;elsecout分配失败！endl;else if(choice=3)if(WFA(id,size)=OK)cout分配成功！endl;elsecout分配失败！next;while(cur)cout*endl;coutdata.ID=FREE)cout无endl;else coutdata.IDendl;cout起始地址:data.addrendl;cout分区长度:data.sizeendl;coutdata.state=BUSY)cout已分配endl;else cout未分配next;int main()cout 动态分区分配方式的模拟

21、 endl; cout*endl;coutarea;while(area=0)coutarea; while(1)cout*endl;cout* 1.FFA 2.BFA 3.WFA 0.EXIT *endl;cout*endl;coutch;if(ch=0)break;Init(area); int choice; while(1)cout*endl;cout* 1.ASSIGN 2.FREE 3.SHOW 0.QUIT *endl;cout* *endl;coutchoice;if(choice=1) coutnum;for(;num0;num-)Assign(ch); else if(choice=2) int ID;coutID;Free(ID);else if(choice=3) Show();else if(choice=0) break;elsecout输入有误，请重试！endl;continue