操作系统课程设计-动态分区分配存储管理

1操作系统课程设计动态分区分配存储管理吕霆20102675计算机10-01班设计题目学号专业班级学生姓名号指导教师第一章课程设计概述1.1设计任务:动态分区分配存储管理1.2设计要求建立描述内存分配状况的数据结构；建立描述进程的数据结构；使用两种方式产生进程：（a）自动产生，（b）手工输入；在屏幕上显示内存的分配状况、每个进程的执行情况；建立分区的分配与回收算法，支持紧凑算法；时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位；(b)响应WM_TIMER；将一批进程的执行情况存入磁盘文件，以后可以读出并重放；支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法。1.3设计目的旨在让我们更好的了解动态分区管理方面的知识.第二章原理及算法描述2.1动态分区分配算法原理首次适应算法*算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中*实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对应作业的值循环首次适应算法*算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区开始查找*实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位置最佳适应算法*算法概述：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区3分配给作业*实现方法：我们决定每次分配先把空闲分区按从小到大的顺序排列，然后将第一个匹配分区分配给作业最坏适应算法*算法概述：每次为作业分配内存时，总是挑选一个最大的空闲分区分割给作业使用*实现方法：算法与最佳适应算法几乎相同，仅在排序时把空闲分区表按从大到小的顺序排列，所以未作详细注释回收分区当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一;1)回收区与插入点的前一个空闲分区F1相邻接,此时应将回收区与插入点的前一分区合并,不必为回收区分配新表项,而只需修改其前一分区F1的大小.2)回收分区与插入点的后一空闲分区F2相邻接,此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和.3)回收区同时与插入点的前,后两个分区邻接,此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和.4)回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置.紧凑算法通过移动内存中的作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法.第三章开发环境此程序是本人利用c++语言在vs2012的开发环境中实现的第四章程序实现--数据结构#includeiostream#includestring#includefstreamusingnamespacestd;ofstreamstream;//输出流对象intary1[20][4];//内存分配状态intary2[20][3];//空闲分区状态intary3[10];//进程分配状态4intrecycle;//需要回收的盘块序号intid1;//算法选择号intm;//内存区数intn;//空闲区数intq;//进程数intr=0;//循环首次适应算法：对应的这次查找到的空闲分区序号//打印输出函数voidvision(){inti;intj;if(id1==1)stream.open(first_fit.txt,ios::app);if(id1==2)stream.open(nextfirst_fit.txt,ios::app);if(id1==3)stream.open(best_fit.txt,ios::app);if(id1==4)stream.open(worst_fit.txt,ios::app);if(id1==5)stream.open(compact.txt,ios::app);if(id1==6)stream.open(huishou.txt,ios::app);cout-------------内存分配状态-------------endl;cout分区号大小/KB始址/KB状态endl;stream-------------内存分配状态-------------endl;stream分区号大小/KB始址/KB状态endl;for(j=0;jm;j++){coutary1[j][0];streamary1[j][0];coutary1[j][1];streamary1[j][1];coutary1[j][2];streamary1[j][2];if(ary1[j][3]==2){cout已分配;stream已分配;}else{cout未分配;stream未分配;}coutendl;streamendl;}coutendl;cout--------空闲分区链--------endl;cout分区号大小/KB起址/KBendl;stream--------空闲分区链--------endl;stream分区号大小/KB起址/KBendl;for(i=0;in;i++)5{coutary2[i][0];streamary2[i][0];coutary2[i][1];streamary2[i][1];coutary2[i][2];streamary2[i][2];coutendl;streamendl;}cout--------------------------endl;stream--------------------------endl;coutendl;stream.close();}//作业信息的自动产生voidcreate_pro(){inti;for(i=0;iq;i++){ary3[i]=rand()%100;if(ary3[i]==0){i--;}}ary3[0]=42;ary3[1]=86;cout产生q个随机进程endl;cout大小分别是:;for(i=0;iq;i++){cout[ary3[i]];}coutendl;}//作业的手动生成voidcreate_zuoye(){intj;intchoice2;intid3=rand()%10;m=id3;//内存区数量6cout---您将创建几个进程---：;cinchoice2;q=choice2;cout输入想创建的作业请求大小endl;for(inti=0;ichoice2;i++){cinj;ary3[i]=j;}cout你创建了choice2个进程;for(inti=0;ichoice2;i++){coutary3[i];}coutendl;}//内存信息的自动产生voidcreate_apply(){inti;for(i=0;im;i++){ary1[i][0]=i+1;ary1[i][1]=rand()%100;if(i==0)ary1[i][2]=0;else{ary1[i][2]=ary1[i-1][2]+ary1[i-1][1];}ary1[i][3]=rand()%3;//coutiendl;if(ary1[i][1]==0){i--;}}intk=0;//空闲区数量for(i=0;im;i++){if(ary1[i][3]!=2){ary2[k][0]=ary1[i][0];ary2[k][1]=ary1[i][1];ary2[k][2]=ary1[i][2];k++;}7}n=k;//空闲块数量}//内存信息的手动生成intcreate_fenqu(){intk,x,y,o=0;inta=0;cout输入想创建的内存分区块数:;cink;cout输入k个内存分区块大小endl;for(inti=0;ik;i++){ary1[i][0]=i;//序号cinx;ary1[i][1]=x;//大小}cout输入内存块的分配状态endl;for(inti=0;ik;i++){ciny;if(y==2){n++;}ary1[i][3]=y;//状态}ary1[0][2]=0;ary1[1][2]=ary1[0][1];for(inti=2;ik;i++){ary1[i][2]=ary1[i-1][2]+ary1[i-1][1];//起始地址}m=k;for(inti=0;ik;i++){if(ary1[i][3]!=2){ary2[a][0]=ary1[i][0];ary2[a][1]=ary1[i][1];ary2[a][2]=ary1[i][2];a++;}}n=a;returnm,n;}//首次适应算法voidfirst_fit()8{vision();inti;intj;intk;intl;intd;//用来保存第k个的值intid2=0;for(i=0;iq;i++)//为每个进程分配空间{for(j=0;jn;j++)//查找空闲链表每项{if(ary2[j][1]=ary3[i])//进程占用空间小于等于其中一个空闲区的大小{cout[ary3[i]]与[ary2[j][1]]相匹配endl;stream.open(first_fit.txt,ios::app);stream[ary3[i]]与[ary2[j][1]]相匹配endl;stream.close();if(ary2[j][1]==ary3[i])//进程占用空间等于其中一个空闲区块大小{ary1[ary2[j][0]-1][3]=2;for(k=j+1;kn;k++){ary2[k-1][0]=ary2[k][0];ary2[k-1][1]=ary2[k][1];ary2[k-1][2]=ary2[k][2];}n--;}else//否则的话，空闲链对应的地方盘块大小小了进程占用的大小，并且内存分配从对应的那一项开始增加一项{l=ary2[j][0];d=ary1[l-1][1];//大小ary1[l-1][1]=ary3[i];ary1[l-1][3]=2;m++;for(k=m;kary2[j][0]+1;k--){ary1[k-1][0]=ary1[k-2][0]+1;ary1[k-1][1]=ary1[k-2][1];ary1[k-1][2]=ary1[k-2][2];ary1[k-1][3]=ary1[k-2][3];}l=ary2[j][0];9ary1[l][0]=l+1;ary1[l][1]=d-ary3[i];ary1[l][2]=ary1[l-1][1]+ary1[l-1][2];ary1[l][3]=0;k=0;for(id2=0;id2m;id2++){if(ary1[id2][3]!=2){ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;}}n=k;}break;}else{cout[ary3[i]]与[ary2[j][1]]不匹配endl;stream.open(first_fit.txt,ios::app);stream[ary3[i]]与[ary2[j][1]]不匹配endl;stream.close();}}vision();}}//首次循环适应算法voidnext_fit(){vision();inti;intj;intk;ints