分区存储管理算法模拟

2013--2014学年第3学期实验项目名称分区存储管理算法模拟实验日期2014/12/25实验成绩实验类型验证型实验目的与要求一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。实验原理用最先使用算法模拟内存的分配和回收实验环境C语言DevC++实验方案设计实验内容1.可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。如下图3.1所示。图3.1主存分区分配示意图为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下表3.1所示。其中，起址——指出一个空闲区的主存起始地址。长度——指出从起始地址开始的一个连续空闲的长度。状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。表3.1空闲区说明表起址长度状态第一栏14K12K未分配第二栏32K96K未分配空表目空表目上述的这张说明表的登记情况是按图3.1中的例子所装入的三个作业占用的主存区域后填写的。2.当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。3.采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图3.2。4.当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在图3.1中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图3.3。5.请按最先适应算法设计主存分配和回收的程序。然后按图3.1中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。调试过程及实验结果总结此实验还可以写一个用户自己的输入来验证，增加验证的准确性附录#includestdio.h#includemath.h#defineCOUNT512typedefstructNODE{charname;//名称floatstart;//起始位置floatend;//大小intflag;//是否分配的标志}NODE;NODEOS[COUNT];//数组intcount;//被分成的块数统计intapplyfree;floatnumb;charc;//先对数组进行初始化，使没有分配的名称为pvoidinit(){count=1;OS[0].name='P';OS[0].start=0;OS[0].end=COUNT;OS[0].flag=1;}//对数组的插入操作voidinsert(intm,floatst,floaten){inti;count++;for(i=count;im+1;i--){OS[i]=OS[i-1];}OS[m].start=st;OS[m].end=en;}//移动操作，即对数组的删除操作voidmove(intm){inti;for(i=m;icount-1;i++){OS[i]=OS[i+1];}count--;}//如果相邻块都没有分配，则要合并到一起voidrremove(intm,floatst,floaten){if(!OS[m-1].flag&&!OS[m+1].flag){OS[m].name='P';OS[m].flag=1;}if(OS[m-1].flag){OS[m-1].end=OS[m-1].end+en;move(m);}if(OS[m+1].flag){OS[m].end=OS[m].end+OS[m+1].end;OS[m].name='P';OS[m].flag=1;move(m+1);}}//打印输出voidshow(){inti;printf(名称标识起址长度状态\n);for(i=0;icount;i++){if(OS[i].flag)printf(P);elseprintf(%c,OS[i].name);printf(%d%1.0f%1.0f,i,OS[i].start,OS[i].end);if(OS[i].flag)printf(未分配\n);elseprintf(已分配\n);}}//从键盘输入数据voidputin(){printf(请输入申请或者释放的进程名称及资源数量：\n);rewind(stdin);scanf(%c,&c);scanf(%d,&applyfree);scanf(%f,&numb);}intapply(){inti=0;intapplyflag=0;intfreeflag=0;if(applyfree)//提出申请资源{while(!applyflag&&icount){if(OS[i].end=numb&&OS[i].flag){if(OS[i].end==numb){OS[i].name=c;OS[i].flag=0;}else{insert(i+1,OS[i].start+numb,OS[i].end-numb);OS[i+1].flag=1;OS[i+1].name='P';OS[i].start=OS[i].start;OS[i].name=c;OS[i].end=numb;OS[i].flag=0;}applyflag=1;}i++;}if(applyflag){printf(申请成功！\n);return1;}else{printf(申请失败！没有足够大的空闲空间。\n);return0;}}else//提出释放资源{while(!freeflag&&icount){if(OS[i].name==c){if(OS[i].end==numb){rremove(i,OS[i].start,OS[i].end);}else{if(OS[i].endnumb){insert(i+1,OS[i].start+numb,OS[i].end-numb);OS[i+1].name='P';OS[i+1].flag=0;OS[i].end=numb;OS[i].flag=1;if(OS[i-1].flag){rremove(i,OS[i].start,OS[i].end);}}else{printf(释放失败，因为正使用的数量小于要求释放的数量。\n);return0;}}freeflag=1;}i++;}if(freeflag){printf(释放成功！\n);return1;}else{printf(释放失败！未找到匹配的进程名称。\n);return0;}}}voidmain(){init();show();while(1){putin();apply();show();}}指导教师评语及成绩