c++动态分区分配算法模拟(操作系统课程设计)课程设计课程设计名称：操作系统课程设计专业班级：学生姓名：学号：指导教师：课程设计时间：6月13日-——6月17日计算机科学专业课程设计任务书说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页1：需求分析（1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。
其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请50KB；作业6释放60 KB。
采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。
2：概要设计（1）数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。
已分配内存块的双向链表，记录当前系统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业总数，已分配的内存块数，剩余的内存块数。
（2）主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函数，循环处理11个作业步。
（3）分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于系统额定的最小碎片值，把空闲块全部分配，否则进行分割分配，最后显示分配的内存信息。
（4）回收函数free()：首次适应算法检索已分配的内存块链表，找到要释放的内存块后，在已分配链表中删除该结点，并把该结点挂到未分配内存块链表的结尾处，然后进行两次调整，把未分配的内存块链表调整为首地址从小到大的排列顺序，并且物理上相邻的空闲内存块要进行合并，以方便下次进行分配。
调度分配函数，循环处理阻塞作业队列，最后显示回收后的内存情况。
（5）调度图如下：3：运行环境硬件：计算机软件：windowsXP vc++6.04:开发工具和编程语言开发工具：vc++6.0编程语言：C语言5：详细设计（1）：数据结构模块struct job//作业结点{int num;//作业编号int state;//0表示释放，1表示申请int length;//作业要求处理大小};struct yifenpei//已分配内存块结点{int num;//占有内存区域的作业编号int firstadd;//内存区域的首地址int length;//内存区域的大小struct yifenpei*forward;struct yifenpei*next;};struct weifenpei//未分配内存块结点{int firstadd;//空闲区域的首地址int length;//空闲区域的大小struct weifenpei*forward;struct weifenpei*next;};struct total//内存分配状况记录结点{int totalyifen;//已分配的总内存块数int totalweifen;//未分配的总内存块数int totalzuse;//阻塞的作业个数};struct job jobarray[11];//作业处理队列struct yifenpei*headyifen=(struct yifenpei*)malloc(len2);//已分配的内存块所构成的双向链表的头指针struct weifenpei*headweifen=(struct weifenpei*)malloc(len3);//未分配的内存块所构成的双向链表的头指针struct job zuse[11];//阻塞作业队列struct total totalnow;2：主函数模块void main(){jobarray[0].num=1; jobarray[0].state=1; jobarray[0].length=130;/* 初始化请求序列，共11个作业步*/jobarray[1].num=2; jobarray[1].state=1; jobarray[1].length=60;jobarray[2].num=3; jobarray[2].state=1; jobarray[2].length=100;jobarray[3].num=2; jobarray[3].state=0; jobarray[3].length=60;jobarray[4].num=4; jobarray[4].state=1; jobarray[4].length=200;jobarray[5].num=3; jobarray[5].state=0; jobarray[5].length=100;jobarray[6].num=1; jobarray[6].state=0; jobarray[6].length=130;jobarray[7].num=5; jobarray[7].state=1; jobarray[7].length=140;jobarray[8].num=6; jobarray[8].state=1; jobarray[8].length=60;jobarray[9].num=7; jobarray[9].state=1; jobarray[9].length=50;jobarray[10].num=6; jobarray[10].state=0; jobarray[10].length=60;totalnow.totalyifen=0;totalnow.totalweifen=1;totalnow.totalzuse=0;//初始化系统内存分配状况struct weifenpei*weifen=(struct weifenpei*)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(int m=0;m<11;m++)//初始化阻塞作业队列{zuse[m].num=0;zuse[m].state=0;zuse[m].length=0;}for(int i=0;i<11;i++)//循环处理11个作业步{if(jobarray[i].state==1){alloc(jobarray[i],jobarray[i].num);//调用分配函数}else{free(jobarray[i],jobarray[i].num);//调用释放函数}}printf("全部作业已处理完成!");}3：分配函数模块void alloc(struct job jobnow,int i){int j=1;struct weifenpei*weifennow1=NULL;struct weifenpei*weifennow2=NULL;struct yifenpei*yifennow2=NULL;struct yifenpei*yifennow1=NULL;weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;while(yifennow2!=NULL){yifennow1=yifennow2;yifennow2=yifennow2->next;}yifennow2=(struct yifenpei*)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(int y=0;y<11;y++){if(zuse[y].num==0){zuse[y].num=jobnow.num;zuse[y].length=jobnow.length;zuse[y].state=jobnow.state;totalnow.totalzuse++;break;}}}weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;printf("当前阻塞作业个数为:%d\n",totalnow.totalzuse);//显示分配后的信息printf("当前已分配%d个存储块:\n",totalnow.totalyifen);while(yifennow2!=NULL){printf("作业号:%d 首地址:%d 大小:%d\n",yifennow2->num,yifennow2->firstadd,yifennow2->length);yifennow1=yifennow2;yifennow2=yifennow2->next;}printf("当前还有%d个空闲存储块:\n",totalnow.totalweifen);while(weifennow2!=NULL){printf("首地址:%d 大小:%d\n",weifennow2->firstadd,weifennow2->length,"\n");weifennow1=weifennow2;weifennow2=weifennow2->next;}printf("\n");}4：回收函数模块void free(struct job jobnow,int i){int j=1;struct weifenpei*weifennow1=NULL;struct weifenpei*weifennow2=NULL;struct yifenpei*yifennow2=NULL;struct yifenpei*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=(struct weifenpei*)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//将放到未分配的链表尾部的结点移动到合适的位置{struct weifenpei*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;}}else{if((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(int x=0;x<11;x++){if(zuse[x].num!=0){totalnow.totalzuse--;zuse[x].num=0;zuse[x].state=0;zuse[x].length=0;alloc(zuse[x],zuse[x].num);}if(totalnow.totalzuse==0){break;}}}weifennow1=headweifen;weifennow2=headweifen->next;yifennow1=headyifen;yifennow2=headyifen->next;printf("当前阻塞作业个数为:%d\n",totalnow.totalzuse);//显示释放内存以及处理完阻塞作业后的内存分配情况printf("当前已分配%d个存储块:\n",totalnow.totalyifen);while(yifennow2!=NULL){printf("作业号:%d 首地址:%d 大小:%d\n",yifennow2->num,yifennow2->firstadd,yifennow2->length);yifennow1=yifennow2;yifennow2=yifennow2->next;}printf("当前还有%d个空闲存储块:\n",totalnow.totalweifen);while(weifennow2!=NULL){printf("首地址:%d 大小:%d\n",weifennow2->firstadd,weifennow2->length);weifennow1=weifennow2;weifennow2=weifennow2->next;}printf("\n");}6：调试分析（1）设计数据结构时考虑到有两种可供选择，一种是用一个数据结构来描述内存块的分配情况，另外一种是分开描述，我采用了第二种，用两个双向链表来分别描述已分配和未分配的内存块。