c++动态分区分配算法模拟(操作系统课程设计)演示教学.doc

Good is good, but better carries it.精益求精，善益求善。c+动态分区分配算法模拟(操作系统课程设计)-课程设计课程设计名称：操作系统课程设计专业班级：学生姓名：学号：指导教师：课程设计时间：6月13日-6月17日计算机科学专业课程设计任务书学生姓名马飞扬专业班级学号题目动态分区分配方式的模拟1课题性质其它课题来源自拟课题指导教师同组姓名主要内容1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200KB；作业3释放100KB；作业1释放130KB；作业5申请140KB；作业6申请60KB；作业7申请50KB；作业6释放60KB请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。任务要求了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。参考文献任满杰等操作系统原理实用教程电子工业出版社2006汤子瀛计算机操作系统（修订版）西安电子科技大学出版社2001张尧学史美林计算机操作系统教程实验指导清华大学出版社2000罗宇等操作系统课程设计机械工业出版社2005审查意见指导教师签字：教研室主任签字：年月日说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页1：需求分析（1） 用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。（2） 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200KB；作业3释放100KB；作业1释放130KB；作业5申请140KB；作业6申请60KB；作业7申请50KB；作业6释放60KB。采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。2：概要设计（1） 数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。已分配内存块的双向链表，记录当前系统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业总数，已分配的内存块数，剩余的内存块数。（2） 主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函数，循环处理11个作业步。（3） 分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于系统额定的最小碎片值，把空闲块全部分配，否则进行分割分配，最后显示分配的内存信息。（4） 回收函数free()：首次适应算法检索已分配的内存块链表，找到要释放的内存块后，在已分配链表中删除该结点，并把该结点挂到未分配内存块链表的结尾处，然后进行两次调整，把未分配的内存块链表调整为首地址从小到大的排列顺序，并且物理上相邻的空闲内存块要进行合并，以方便下次进行分配。调度分配函数，循环处理阻塞作业队列，最后显示回收后的内存情况。调度图如下：Free()主函数Alloc()3：运行环境硬件：计算机软件：windowsXPvc+6.04:开发工具和编程语言开发工具：vc+6.0编程语言：C语言5：详细设计（1）：数据结构模块structjob/作业结点intnum;/作业编号intstate;/0表示释放，1表示申请intlength;/作业要求处理大小;structyifenpei/已分配内存块结点intnum;/占有内存区域的作业编号intfirstadd;/内存区域的首地址intlength;/内存区域的大小structyifenpei*forward;structyifenpei*next;structweifenpei/未分配内存块结点intfirstadd;/空闲区域的首地址intlength;/空闲区域的大小structweifenpei*forward;structweifenpei*next;structtotal/内存分配状况记录结点inttotalyifen;/已分配的总内存块数inttotalweifen;/未分配的总内存块数inttotalzuse;/阻塞的作业个数;structjobjobarray11;/作业处理队列structyifenpei*headyifen=(structyifenpei*)malloc(len2);/已分配的内存块所构成的双向链表的头指针structweifenpei*headweifen=(structweifenpei*)malloc(len3);/未分配的内存块所构成的双向链表的头指针structjobzuse11;/阻塞作业队列structtotaltotalnow;2：主函数模块voidmain()jobarray0.num=1;jobarray0.state=1;jobarray0.length=130;/*初始化请求序列，共11个作业步*/jobarray1.num=2;jobarray1.state=1;jobarray1.length=60;jobarray2.num=3;jobarray2.state=1;jobarray2.length=100;jobarray3.num=2;jobarray3.state=0;jobarray3.length=60;jobarray4.num=4;jobarray4.state=1;jobarray4.length=200;jobarray5.num=3;jobarray5.state=0;jobarray5.length=100;jobarray6.num=1;jobarray6.state=0;jobarray6.length=130;jobarray7.num=5;jobarray7.state=1;jobarray7.length=140;jobarray8.num=6;jobarray8.state=1;jobarray8.length=60;jobarray9.num=7;jobarray9.state=1;jobarray9.length=50;jobarray10.num=6;jobarray10.state=0;jobarray10.length=60;totalnow.totalyifen=0;totalnow.totalweifen=1;totalnow.totalzuse=0;/初始化系统内存分配状况structweifenpei*weifen=(structweifenpei*)malloc(len3);weifen->firstadd=1;weifen->forward=headweifen;weifen->length=640;weifen->next=NULL;headweifen->forward=NULL;headweifen->next=weifen;/初始化未分配的内存块双向链表headyifen->next=NULL;headyifen->forward=NULL;/初始化已分配的内存块双向链表for(intm=0;m<11;m+)/初始化阻塞作业队列zusem.num=0;zusem.state=0;zusem.length=0;for(inti=0;i<11;i+)/循环处理11个作业步if(jobarrayi.state=1)alloc(jobarrayi,jobarrayi.num);/调用分配函数elsefree(jobarrayi,jobarrayi.num);/调用释放函数printf("全部作业已处理完成!");3：分配函数模块voidalloc(structjobjobnow,inti)intj=1;structweifenpei*weifennow1=NULL;structweifenpei*weifennow2=NULL;structyifenpei*yifennow2=NULL;structyifenpei*yifennow1=NULL;weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;while(yifennow2!=NULL)yifennow1=yifennow2;yifennow2=yifennow2->next;yifennow2=(structyifenpei*)malloc(len2);while(weifennow2!=NULL)/首次适应算法检索合适的内存块if(weifennow2->length>=jobnow.length)if(weifennow2->length-jobnow.length)<=erding)/内存碎片小于额定值全部分配weifennow1->next=weifennow2->next;yifennow2->num=i;yifennow2->firstadd=weifennow2->firstadd;yifennow2->length=weifennow2->length;yifennow2->forward=yifennow1;yifennow1->next=yifennow2;yifennow2->next=NULL;totalnow.totalyifen+;totalnow.totalweifen-;else/否则进行分割分配诶yifennow2->num=i;yifennow2->firstadd=weifennow2->firstadd;yifennow2->length=jobnow.length;yifennow2->next=NULL;yifennow2->forward=yifennow1;yifennow1->next=yifennow2;weifennow2->length=weifennow2->length-jobnow.length;weifennow2->firstadd=weifennow2->firstadd+jobnow.length;totalnow.totalyifen+;j=0;break;weifennow1=weifennow2;weifennow2=weifennow2->next;if(j)/未找到合适内存块则把作业放入阻塞队列for(inty=0;y<11;y+)if(zusey.num=0)zusey.num=jobnow.num;zusey.length=jobnow.length;zusey.state=jobnow.state;totalnow.totalzuse+;break;weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;printf("当前阻塞作业个数为:%dn",totalnow.totalzuse);/显示分配后的信息printf("当前已分配%d个存储块:n",totalnow.totalyifen);while(yifennow2!=NULL)printf("作业号:%d首地址:%d大小:%dn",yifennow2->num,yifennow2->firstadd,yifennow2->length);yifennow1=yifennow2;yifennow2=yifennow2->next;printf("当前还有%d个空闲存储块:n",totalnow.totalweifen);while(weifennow2!=NULL)printf("首地址:%d大小:%dn",weifennow2->firstadd,weifennow2->length,"n");weifennow1=weifennow2;weifennow2=weifennow2->next;printf("n");4：回收函数模块voidfree(structjobjobnow,inti)intj=1;structweifenpei*weifennow1=NULL;structweifenpei*weifennow2=NULL;structyifenpei*yifennow2=NULL;structyifenpei*yifennow1=NULL;weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;while(weifennow2!=NULL)weifennow1=weifennow2;weifennow2=weifennow2->next;while(yifennow2!=NULL)/首次适应算法检索已分配链表if(yifennow2->num=jobnow.num)&&(yifennow2->length=jobnow.length)/找到后直接释放到未分配的内存块的表尾yifennow1->next=yifennow2->next;yifennow2->next->forward=yifennow1;weifennow2=(structweifenpei*)malloc(len3);weifennow2->forward=weifennow1;weifennow2->next=NULL;weifennow1->next=weifennow2;weifennow2->firstadd=yifennow2->firstadd;weifennow2->length=yifennow2->length;totalnow.totalyifen-;totalnow.totalweifen+;j=0;break;yifennow1=yifennow2;yifennow2=yifennow2->next;if(j=1)/未找到则作业队列有问题printf("参数错误!");else/将放到未分配的链表尾部的结点移动到合适的位置structweifenpei*weifennow3=headweifen;structweifenpei*weifennow4=headweifen->next;while(weifennow4!=weifennow2)if(weifennow4->next=weifennow2)if(weifennow2->firstadd+weifennow2->length)<weifennow4->firstadd)weifennow4->next=weifennow2->next;weifennow3->next=weifennow2;weifennow2->forward=weifennow3;weifennow2->next=weifennow4;weifennow4->forward=weifennow2;break;if(weifennow2->firstadd+weifennow2->length)=weifennow4->firstadd)weifennow2->length+=weifennow4->length;weifennow3->next=weifennow2;weifennow2->forward=weifennow3;totalnow.totalweifen-;break;elseif(weifennow2->firstadd+weifennow2->length)<weifennow4->firstadd)weifennow2->forward->next=NULL;weifennow3->next=weifennow2;weifennow2->forward=weifennow3;weifennow2->next=weifennow4;weifennow4->forward=weifennow2;break;if(weifennow2->firstadd+weifennow2->length)=weifennow4->firstadd)weifennow2->forward->next=NULL;weifennow2->length+=weifennow4->length;weifennow3->next=weifennow2;weifennow2->forward=weifennow3;weifennow2->next=weifennow4->next;weifennow4->next->forward=weifennow2;totalnow.totalweifen-;break;weifennow3=weifennow4;weifennow4=weifennow4->next;weifennow1=headweifen;weifennow2=headweifen->next;while(weifennow2!=NULL)/对未分配的内存块的双向链表进行合并紧凑操作，使得物理上相邻的内存块放到一个记录中if(weifennow1!=headweifen)&&(weifennow1->firstadd+weifennow1->length)=weifennow2->firstadd)weifennow2->length+=weifennow1->length;weifennow2->firstadd=weifennow1->firstadd;weifennow2->forward=weifennow1->forward;weifennow1->forward->next=weifennow2;totalnow.totalweifen-;weifennow1=weifennow2;weifennow2=weifennow2->next;if(totalnow.totalzuse!=0)/释放内存后再循环处理阻塞队列中的阻塞作业，若仍无合适内存块则继续阻塞for(intx=0;x<11;x+)if(zusex.num!=0)totalnow.totalzuse-;zusex.num=0;zusex.state=0;zusex.length=0;alloc(zusex,zusex.num);if(totalnow.totalzuse=0)break;weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;printf("当前阻塞作业个数为:%dn",totalnow.totalzuse);/显示释放内存以及处理完阻塞作业后的内存分配情况printf("当前已分配%d个存储块:n",totalnow.totalyifen);while(yifennow2!=NULL)printf("作业号:%d首地址:%d大小:%dn",yifennow2->num,yifennow2->firstadd,yifennow2->length);yifennow1=yifennow2;yifennow2=yifennow2->next;printf("当前还有%d个空闲存储块:n",totalnow.totalweifen);while(weifennow2!=NULL)printf("首地址:%d大小:%dn",weifennow2->firstadd,weifennow2->length);weifennow1=weifennow2;weifennow2=weifennow2->next;printf("n");6：调试分析（1）设计数据结构时考虑到有两种可供选择，一种是用一个数据结构来描述内存块的分配情况，另外一种是分开描述，我采用了第二种，用两个双向链表来分别描述已分配和未分配的内存块。（2）设计主函数以及分配函数时都是借鉴书上的知识，过程也很顺利。设计回收函数时，我发现我的这种数据结构若采用书上的算法，将很难实现，于是就另外设计了一种针对我这种数据结构的简单可行的回收算法，于是就解决了这个问题。7：测试结果程序运行结果如图1,2,3：图1：图2：图3：参考文献：【1】任满杰操作系统原理实用教程电子工业出版社2006【2】汤子瀛计算机操作系统（修订版）西安电子科技大学出版社2001【3】张尧学计算机操作系统教程实验指导清华大学出版社2000【4】罗宇等操作系统课程设计机械工业出版社2005【5】动态分区模拟算法（网络文章）心得体会这次课程设计时间上比较紧迫，因为我们还有几门课程要考试，因此要留出一部分时间用于复习，所以我就压缩了课程设计的时间，选择了一个难度不是太大的题目。以前虽然老师让自学C语言，但总感觉没学到什么，但通过这次课程设计我对C语言的相关知识点又加深了认识和理解，同时在设计的过程中又设计了新的数据结构以及回收算法，提高了创新能力，总之，在这次课程设计中也收获了很多东西，但如果时间能再充裕点的话，我会做的更好。以后的自己还要再接再厉，努力，加油！-