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

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

2、程所需内存空间的大小：当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况；当某进程撤消时，显示内存回收后内存空间的使用情况。能够处理以下的情形：主存回收函数实现：有上邻空闲区和下邻空闲区，它们与回收区的合并；有上邻空闲区，无下邻空闲区，回收区与上邻空闲区的合并；无上邻空闲区，有下邻空闲区，回收区与下邻空闲区的合并。2 .设计报告内容应说明：（1）课程设计目的与功能；需求分析，数据结构或模块说明（功能与框图）；源程序的主要局部；测试用例，运行结果与运行情况分析；（5）自我评价与总结：i）你认为你完成的设计哪些地方做得比拟好或比拟出色；ii）什么地方做得不

3、太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成此题是否有其他的其他方法（如果有，简要说明该方法）；V）对实验题的评价和改良意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（考前须知：严禁抄袭，一旦发现，抄与被抄的一律按O分记）指导教师签名：年月日系主任（或责任教师）签名：年月日模拟设计动态分区存储管理的分配与回收.课程设计目的与功能1.l课程设计的目的深入了解动态分区存储管理方式的主存分配回收的实现。1. 2课程设计的功能1 .能够输入给定的内

4、存大小，进程的个数，每个进程所需内存空间的大小；2 .当某进程提出申请空间的大小后，显示能否满足申请，以及为该进程分配资源后有关内存空间使用的情况；3 .当某进程撤消时，显示内存回收后内存空间的使用情况。能够处理以下的情形：主存回收函数实现：有上邻空闲区和下邻空闲区，它们与回收区的合并；有上邻空闲区，无下邻空闲区，回收区与上邻空闲区的合并；无上邻空闲区，有下邻空闲区，回收区与下邻空闲区的合并。1 .需求分析，数据结构或模块说明1.1 需求分析动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要的主存空间的大小查询主存

5、内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，那么需要将相邻空闲区合并成一个空闲区。实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格根底上设计主存分配算法；第三，在设计的数据表格根底上设计主存回收算法。实验中主存分配算法采用“最优适应”算法。最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使

6、装入大作业时比拟容易得到满足。但是最优适应算法容易出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法使用，却影响了主存的使用。为了一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成己分分区和空闲区两局部，而是将整个空闲区分配给作业。在实现最优适应算法时，可把空闲区按长度以递增方式登记在空闲区表中。2.2结构说明分区说明表structPST/partitionspecificationtableintid;源区号intaddr;起始地址intsize;分区长度Statusstate;状态)；2.

7、L2双向链表structNode双向链表结点PSTdata;Node*back;/前驱Node*next;后继Node()(back=NLL;next=NULL;Node(intid,intsize)(data.lD=id;data.size=size;back=NLL;next=NULL;)；2.1.3最先适应算法StatusFFA(intid,intsize)/headfitalgorithmNode*temp=newNode(id,size);temp-data.state=BUSY;Node*cur=head-next;while(cur)(if(cur-data.state=FREE

8、cur-data.size=size)如果空闲块大小刚好与请求大小相等,直接分配cur-data.lD=id;cur-data.state=BUSY;returnOK;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.size=cur-data.size-size;ret

9、urnOK;break;)cur=cur-next;)returnERROR;)2.L4最正确适应算法StatusBFA(intid,intsize)/bestfitalgorithmNode*temp=newNode(id,size);temp-data.state=BUSY;intmin;/记录符合满足请求的最小空闲块大小Node*世;指向采用最正确适应算法的插入位置Node*cur=head-next;while(cur)取得第一个可以分配的位置(不一定是最正确位置)if(cur-data.state=FREE&cur-data.size=size)(fit=cur;min=cur-da

10、ta.size-size;break;)cur=cur-next;)while(cur)if(cur-data.state=FREE&cur-data.size=size)如果相等直接分配cur-data.state=BUSY;cur-data.lD=id;returnOK;break;if(cur-data.state=FREE&cur-data.sizesize)获取最正确位置if(cur-data.size-sizedata.size-size;fit=cur;)cur=cur-next;)ifm)假设最正确，插入temp-back=fit-back;temp-next=fit;fit-

11、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;returnOK;)elsereturnERROR;)2.1. 5最坏适应算法StatusWFA(intid,intsize)/worstfitalgorithmNode*temp=newNode(id,size);temp-data.state=BUSY;intmax;记录符合满足请求的最小空闲块大小Node*fit;指向采用最坏适应算法的插入位置

12、Node*cur=head-next;while(cur)取得第一个可以分配的位置(不一定是最正确位置)if(cur-data.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.lD=id;returnOK;break;)7if(cur-data.state=FREE&cur-data.sizesize

13、)获取最正确位置if(cur-data.size-sizemax)(max=cur-data.size-size;fit=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;returnOK;)elsereturnERROR;)2 .3结构框图图13 .源程序#

14、includeusingnamespacestd;/#defineMAX_LEN1024/定义内存大小，1024字节enumStatUSFREE,BUSY,OK,ERROR;structPST/partitionspecificationtableintID;分区号intaddr;起始地址intsize;/分区长度Statusstate;状态)；structNode双向链表结点PSTdata;Node*back;前驱Node*next;后继Node()(back=NULL;next=NULL;)Node(intid,intsize)(data.lD=id;data.size=size;back

15、NULL;next=NULL;)；intarea;输入内存空间Node*head,*last;voidlnit(intarea)(head=newNode();last=newNode();head-next=last;Iast-back=head;last-data.addr=O;last-data.lD=O;last-data.size=area;last-data.state=FREE;)StatusFFA(intid,intsize)/headfitalgorithmNode*temp=newNode(id,size);temp-data.state=BUSY;Node*cur=he

16、ad-next;while(cur)(if(cur-data.state=FREE&cur-data.size=size)如果空闲块大小刚好与请求大小相等,直接分配cur-data.lD=id;cur-data.state=BUSY;returnOK;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+

17、size;cur-data.size=cur-data.size-size;returnOK;break;)cur=cur-next;)returnERROR;)StatusBFA(intid,intsize)/bestfitalgorithmNode*temp=newNode(id,size);temp-data.state=BUSY;intmin;记录符合满足请求的最小空闲块大小Node*租;指向采用最正确适应算法的插入位置Node*cur=head-next;while(cur)取得第一个可以分配的位置(不一定是最正确位置)if(cur-data.state=FREE&cur-data.

18、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.lD=id;returnOK;break;if(cur-data.state=FREE&cur-data.sizesize)获取最正确位置if(cur-data.size-sizedata.size-size;fit=cur;)cur=cur-next;)if(fit)假设最正确，插入temp-

19、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;returnOK;)elsereturnERROR;)StatusWFA(intid,intsize)/worstfitalgorithmNode*temp=newNode(id,size);temp-data.state=BUSY;intmax;记录符合满足请求的最小空闲块大小Node

20、fit;指向采用最坏适应算法的插入位置Node*cur=head-next;while(cur)取得第一个可以分配的位置(不一定是最正确位置)if(cur-data.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.lD=id;returnOK;break;)7if(cur-data.state=FR

21、EE&cur-data.sizesize)获取最正确位置if(cur-data.size-sizemax)(max=cur-data.size-size;fit=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;returnOK;)elsereturnERRO

22、R;)voidFree(intid)Node*cur=head;while(cur)(if(cur-data.lD=id)(cur-data.state=FREE;cur-data.lD=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)与后面的空闲块相连(cur-data.size+=cur-next-data.size;cur-next-ne

23、xt-back=cur-back;cur-back-next=cur-next;)break;)cur=cur-next;)StatusAssign(intchoice)(intid,size;COUtVV”请输入区号:；cinid;CoUtVVendIVV”请输入分区长度(KB):；cinsize;if(size=O)(COUtVV输入错误Fvvendl;returnERROR;)if(choice=1)(if(FFA(id,size)=OK)CoUtVV”分配成功!endl;elseCoUtVV”分配失败!endl;)elseif(choice=2)if(BFA(id,size)=OK)C

24、OUtVV”分配成功!edl;elseCoUtVV”分配失败!endl;)elseif(choice=3)if(WFA(id,size)=OK)ColltVV”分配成功!endl;elseCoUtVV分配失败！next;while(cur)cout*dl,coutdata.lD=FREE)COUtVV无vvendl;elsecoutdata.IDdata.addrvvendl;CoUtVV”分区长度:“VVCUrdata.sizevvendl;COUtVV状态:；if(cur-data.state=BUSY)CoUtVV已分酉己vvendl;elseCOUtVV”未分配VVendI;cur=c

25、ur-next;)intmain()cout动态分区分配方式的模拟,area;while(areaarea;)while(1)cout,*dl,cout*1.FFA2.BFA3.WFAO.EXIT*endl;cout*ch;if(ch=O)break;)lnit(area);intchoice;while(1)cout*dl*COUtVV1.分配2.回收3.查看0.退出*,endl;cout*choice;if(choice=1)COUtVV”请输入进程个数”;intnum;cinnum;for(;num0;num-)Assign(ch);/分配内存)elseif(choice=2)/内存回收

26、intID;CoUtVV”请输入您要释放的分区号：cinID;Free(ID);)elseif(choice=3)ShOW();/显示主存elseif(choice=0)break;else输入操作有误COUtVV”输入有误，请重试！vvendl;continue;)returnO;4.测试用例，运行结果与运行情况分析；4.1 运行情况4.1.1 输入内存4.L2内存分配可用表4.1.4内存回收4.1.5归还区有上临空闲区4.1.5归还区有下临空闲区5.自我评价与总结：对于这一次的课程设计总体上来说自己还是比拟满意的，设计的思路清晰，程序模块清楚，各种功能也有比拟好的实现。运行窗口内容设计友好

27、便于操作，能够很清晰地让人明白这一次课程设计的内容。但是对于动态分区回收主存时还欠缺了一些考虑，动态分区方式下回收主存空间时，应该检查是否有与归还区相邻的空闲区。假设有，那么应该合并成一个空闲区。一个归还区可能有上邻空闲区，也可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区也无下邻空闲区。我只是考虑其中了三个方面即“上临空闲区”、“下临空闲区”和“既无上临也无下临空闲区”，所以设计程序时还有些许漏洞，对于各种情况考虑的不够周全。以后再次进行设计的时候应该多注意各种可能发生的情况，并一一做出解决的方案，令自己的设计趋于完善。经过本一次的课程设计从编写程序直至最后运行，自己

28、对于编程的理解自然是更进一步，对于一个题目的研究及思考方面都有了长足进步，我觉得最重要的是学习到了一种思考的方式，从不同的角度多个方面的来看这个问题，尝试着处理各种有可能发生的情况，从中收获良多。我觉得以后应设计开放的题目，对于学生要求要用开放思想来解决、对待这个问题。其中帮助或许更大。本科生课程设计成绩评定表班级：姓名：学号:序号评分工程总分值实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的标准性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：20年月日