动态分区管理的主存分配模拟设计--最先适应法、最优适应法.doc

武汉理工大学操作系统课程设计说明书学 号： 012课 程 设 计题 目动态分区管理的主存分配模拟设计-最先适应法、最优适应法学 院计算机科学与技术学院专 业计算机科学与技术专业班 级姓 名指导教师2011年01月18日课程设计任务书学生姓名： 专业班级： 计算机 指导教师： 工作单位： 计算机科学与技术学院 题 目: 动态分区管理的主存分配模拟设计-最先适应法、最优适应法初始条件：1预备内容：阅读操作系统的内存管理章节内容，理解动态分区的思想，并体会各分配算法的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： 随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日动态分区管理的主存分配模拟设计-最先适应法、最优适应法1. 目的与功能采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： 随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能。2. 需求分析，数据结构或模块说明2.1需求分析对于一台完全无软件的计算机系统，即使功能再强，也必定是难于使用的。所以在计算机上覆盖了OS后，便可获的一台功能显著使用极为方便的计算机。因此操作系统是最重要的计算机系统软件，而进程调度是操作系统中最核心的内容。存储器是计算机的重要组成部分,存储空间是操作系统管理的宝贵资源,虽然其容量在不断扩大,但仍然远远不能满足软件发展的需要。对存储资源进行有效的管理,不仅关系到存储器的利用率,而且还对操作系统的性能和效率有很大的影响。操作系统的存储管理的基本功能有：存储分配、地址转换和存储保护、存储共享、存储扩充。存储分配指为选中的多道运行的作业分配主存空间；地址转换是把逻辑地址空间中的用户程序通过静态重定位或动态重定位转换和映射到分给的物理地址空间中,以便用户程序的执行；存储保护指各道程序只能访问自己的存储区域,而不能互相干扰,以免其他程序受到有意或无意的破坏；存储共享指主存中的某些程序和数据可供不同用户进程共享。最简单的单道系统中,一旦一个程序能装入主存,它将一直运行直到结束。如果程序长度超出了主存的实际容量,可以通过覆盖和交换的技术获得解决。更多的操作系统支持多个用户进程在主存同时执行,能满足多道程序设计需要的最简单的存储管理技术是分区方式,有分固定分区和可变分区。可变分区的分配（如图（1）所示）算法包括：最先适应、下次适应、最佳适应、最坏适应和快速适应等分配算法。图（1）动态内存分配采用分区方式管理存储器,每道程序总是要求占用主存的一个或几个连续的存储区域,主存中会产生许多碎片。因此,有时为了接纳一个新的作业而往往要移动已在主存的信息,这不仅不方便,而且开销不小。现代计算机都有某种虚存硬设备支持,简单也是常用的虚存是请求分页式虚存管理,于是允许把一个进程的页面存放到若干不相邻的主存页框中。从搜索速度上看，最先适应算法具有最佳性能。并且从回收过程来看，最先适应法也是最佳的。它的另一个优点就是尽可能地利用了低地址空间。从而保证高地址有较大的空闲区来放置要求内存过多的进程或作业。最坏适应法是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能再分配。本课程设计就是分析动态分区法，与固定分区法相比，动态分区法在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变。这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。2.2模块说明2.2.1数据结构结构体定义进程struct areaint start;int end;int len;int sign;struct area * next;5个数据成员，分别为： start（分区的首地址）、end、（分区尾地址）len（分区的长度）、sign（标志进程状态）、next（指针用来指向下一个进程）。内存分配表的图类似与图（3）所示：2.2.2最先适应法（first-fit）按分区起始地址的递增次序，从头查找，找到符合要求的第一个分区。该算法的分配和释放的时间性能较好，一旦找到大于或等于所要求内存长度的分区，则结束探索。最先适应法的程序段：void listID()int n=0;area *p9=freehead-next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL)p0=p0-next;n+;p0=freehead;if (n=1)return;else while(p9!=NULL)p12=p0;p13=p9;p0=p0-next; p9=p9-next; while(p13!=NULL) if(p12-start)(p13-start)p11=new area;p11-end=p13-end;p11-len=p13-len;p11-sign=p13-sign;p11-start=p13-start;p11-next=NULL;swap(p13,p12);swap(p12,p11); p13=p13-next;该模块完成的功能如下图进程进入内存最先适应法流程如下图所示：最先适应算法流程从空闲区表第一表目顺序查找表目查完？该空闲区长度SIZE？该空闲区长度=SIZE？从可用表中移去该表目，调整可用表返回分配起始地址从该空闲区中截取所需大小，修改调整可用表取下一表项无法分配是否是是否请求SIZE大小的分区2.2.3最优适应法(best-fit) 按分区大小的递增次序，组成空闲区可用表或自由链。申请分区时从头开始查找，当找到第一个满足要求的空闲区时，停止查找。如果该空闲区大于请求表中请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中。最优适应法代码段为：void listlen()int n=0; area *p9=freehead-next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL)p0=p0-next;n+;p0=freehead;if (n=1)return;else while(p9!=NULL)p12=p0; p13=p9;p0=p0-next; p9=p9-next; while(p13!=NULL) if(p12-len)(p13-len)p11=new area;p11-end=p13-end;p11-len=p13-len;p11-sign=p13-sign;p11-start=p13-start;p11-next=NULL;swap(p13,p12);swap(p12,p11); p13=p13-next;3. 源程序本程序的源代码为：#includeusing namespace std;#includestruct areaint start;int end;int len;int sign;struct area * next; struct area*freehead=NULL; struct area*usedhead=NULL;void create();void print(area*);void ask(area*);void ask1(area*);void correct(area*,int);area * delempty();void inserused(area *,int ,int );void inserfree(area * );void setfree();void listID();void listlen();void swap(area *,area *);/初始化area * delempty() area * p1=freehead; if(p1-len=0) if(p1-next=NULL)return NULL; else p1=p1-next; /最优适应法void listlen()int n=0; area *p9=freehead-next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL)p0=p0-next;n+;p0=freehead;if (n=1)return;else while(p9!=NULL)p12=p0; p13=p9;p0=p0-next; p9=p9-next; while(p13!=NULL) if(p12-len)(p13-len)p11=new area;p11-end=p13-end;p11-len=p13-len;p11-sign=p13-sign;p11-start=p13-start;p11-next=NULL;swap(p13,p12);swap(p12,p11); p13=p13-next;void swap(area *p13,area *p14)p13-len=p14-len;p13-sign=p14-sign;p13-end=p14-end;p13-start=p14-start;/最先适应法void listID()int n=0;area *p9=freehead-next,*p0=freehead,*p11,*p12,*p13;while(p0!=NULL)p0=p0-next;n+;p0=freehead;if (n=1)return;else while(p9!=NULL)p12=p0;p13=p9;p0=p0-next; p9=p9-next; while(p13!=NULL) if(p12-start)(p13-start)p11=new area;p11-end=p13-end;p11-len=p13-len;p11-sign=p13-sign;p11-start=p13-start;p11-next=NULL;swap(p13,p12);swap(p12,p11); p13=p13-next;void inserfree(area * p3)int flag=0;area *pf=freehead,*pe=freehead,*pe1; while(pf!=NULL)if(pf-end!=p3-start)/判断是否有前继空闲块pf=pf-next; else break; if(pf!=NULL)flag=5;/flag=5 有前置空闲块else flag=1;/没有置1 while(pe!=NULL)/判断是否有后继空闲块if(pe-start!=p3-end)pe1=pe; pe=pe-next;else break; if(pe!=NULL) if(flag=5) flag=6; else flag=4; /有前置且有后置FLAG=6，只有后置=4 else if(flag=1) flag=2; /前后都没有置2 switch(flag) case 5:pf-end=pf-end+p3-len; pf-len=pf-len+p3-len; break; case 4:pe-start=pe-start-p3-len; pe-len=pe-len+p3-len; break; case 2: area* p8; p8=new area; p8-start=p3-start; p8-len=p3-len; p8-sign=0; p8-end=p3-end; p8-next=freehead; freehead=p8; break; case 6:pf-end=pe-end; pf-len=pf-len+pe-len+p3-len; if(pe-next=NULL) pe1-next=NULL; delete pe; else if(pe=freehead)freehead=pe-next;delete pe;else pe1-next=pe-next;delete pe; break; default :break; void setfree()int chose;coutchose; area*p7=usedhead,*p2;while( p7!=NULL) /寻找有无此进程if( p7-sign!=chose )p2=p7;p7=p7-next;else break;if(p7=NULL)cout没有此进程，释放内存失败，返回修改!next=NULL) usedhead=NULL; elseif(p7-next=NULL)p2-next=NULL;delete p7;/将次进城从已分配表中删除else if(p7=usedhead)usedhead=p7-next;delete p7;else p2-next=p7-next;delete p7; cout成功释放所选任务的内存！当前内存状况为：endl;print(freehead);print(usedhead);coutstart=p3-start;p5-len=need; p5-sign=num;p5-end=p3-start+need;p5-next=NULL;usedhead=p5;elsep5=new area;p5-start=p3-start;p5-len=need; p5-sign=num;p5-end=p3-start+need;p5-next=usedhead;usedhead=p5;void correct(area*p3,int need1)p3-len=p3-len-need1;p3-start=p3-start+need1;void create()area* p1;p1=new area;p1-start=0;p1-end=999;p1-len=999;p1-sign=0;p1-next=NULL;freehead= p1;void ask1(area*freehead)/读文件初始化，只用一次int num,need; area*p3=freehead;ifstream infile(123.TXT);while(infilenum) infileneed; if(p3-lenneed) cout内存不足，分配失败！endl; return; else inserused(p3,num,need);correct(p3,need);void ask(area*freehead)int num,need; area*p3=freehead,*p31=freehead;coutinput num and need! num;cinneed;while( p3!=NULL)if(p3-lennext;else break; if(p3=NULL)cout内存不足，分配失败！endl;return;inserused(p3,num,need);correct(p3,need); freehead=delempty();cout成功分配申请，当前内存状况为：endl;print(freehead);print(usedhead);coutendl;void print(area*pp)area*p;p=pp;coutn;if(p=NULL)coutempty list!endl; coutn;return;elsedocoutstart:start end:end len:len sign:signnext;while(p!=NULL);coutn;int main() int yourchose,flag1=0,flag2=0; int what; cout现在初始化内存n; coutflag2; create(); if(flag2=2)ask1(freehead); cout内存初始状态为：n; print(freehead);print(usedhead);coutendl; cout-菜单选项-n;cout1.申请内存 2.释放作业的内存n;cout3.查看空闲块链 4.查看已分配块链n;cout5.查看内存状态 0.退出n;cout-endl;while(flag1=0) coutyourchose; switch(yourchose) case 1: coutwhat;if(what=1)listID();else listlen(); ask(freehead);break; case 2:setfree();break; case 3:print(freehead);break; case 4:print(usedhead);break;case 5: print(freehead);print(usedhead);break;case 0:flag1=1;break;default: break; return 0;4. 运行结果与运行情况分析首先在名为“123.txt”的文本文档中输入几个正在内存中运行的进程号和分区长度，如下图：运行程序，首先读取文本文档中的数据，按顺存入内存中运行，内存状态如下图所示：其中上方进程号为0的分区为空闲区，下面的为正在运行和待运行的程序。如果要增加进程则选择“1.申请内存”为进程申请一段内存，由于各进程都是已经按从高到低顺序排好的，所以选择最先适应法或最优适应法没有什么不同，在这里选择最先适应，然后输入需要加入的进程的进程号和大小，这里加入的进程号为7，大小为30，如下图所示：如要修改已分配内存的区表，则先选择“2.释放作业的内存”，然后选择需要释放内存的序号，当把想要释放的进程都结束后再选择“1.申请内存”为新加入的进程分配内存，选择分配的方法，进行分配。在这里首先释放1，3，5，6进程，结果如下：然后申请内存，使用最先适应法，进程号为8，大小为30，进程加入到首地址为0，尾地址为30，长度为10的内存段中，如下图所示：再申请一段内存，使用最优适应法，进程号为9，大小为70，则由于是用了最有适应法，所以进程存入到了首地址为175，尾地址为245，长度为70的内存段中：5. 自我评价与总结5.1设计哪些地方做得比较好或比较出色实验结果能够很好的和操作系统的理论结合起来，验证最先适应法、最优适应法的流程和优缺点，用链表将进程连接起来，方便分配内存后把内存碎片连接起来，用指针很方便的进行对进程分配内存块。程序的运行界面做的比较友好，能使人较容易的看懂，并且基本上能够实现任务书上要求的全部功能。5.2什么地方做得不太好，以后如何改正在本实验中所有进程都是人为产生的，如果内存空闲区改变时需要改变程序文本比较麻烦，而且是连续排列的，不能够很好地模拟在计算机内存上的存储形式。应该要将内存空闲区改成自动生成比较好。本程序的可视化程度不够，虽然通过本程序提供的表格数据能够很好的说明最先适应法和最优适应法，但是在输出的表格中无法按照首地址