主存空间的分配与回收

操作系统实验报告实验三：主存空间的分配与回收一、实验题目采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收二、实验内容主存是中央处理机能直接存取指令和数据的存储器。能否合理而有效地使用主存，在很大程度上将影响到整个计算机系统的性能。本实验采用可变式分区管理，使用首次或最佳适应算法实现主存空间的分配与回收。要求采用分区说明表进行。三、实验目的通过本次实验，帮助学生理解在可变式分区管理方式下，如何实现主存空间的分配与回收。提示：（1）可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。例如，某时刻主存空间占用情况如图1所示。0操作系统（10KB）10K作业1（10KB）20K作业4（25KB）45K空闲区1（20KB）65K作业2（45KB）110K256K空闲区2（146KB）表1空闲区说明表为了说明哪些分区是空闲的，可以用来装入新的作业，必须要有一张空闲区说明表，如表1所示。其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。状态栏未分配指该栏目是记录的有效空闲区，空表目指没有登记信息。由于分区个数不定，所以空闲区说明表中应有足够的空表目项，否则造成溢出，无法登记。同样，再设一个已分配区表，记录作业或进城的主存占用情况。（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应该将空闲区一分为二。一个分给作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。其分配框图如图2所示。开始申请XK主存J=0J=J+1查看第J个表目的登记项状态为“未分配”吗？长度=XK?长度＝长度－XK始址＝始址＋XK置状态为“空表目将空表目向后移登记已分配区表和空闲区表，输出系统中各数据结构的值。返回分配给作业的主存始址J为空闲区说明表的最后一个表目?作业等待返回NY等于Y大于N小于图2首次适应算法分配框图（3）当一个作业执行完时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区起始地址长度状态45K20KB未分配110K146KB未分配空表目空表目空表目………图1主存空间占用情况合并的问题。作业的释放区与空闲区的邻接分一下4种情况考虑：A．释放区下邻（低地址邻接）空闲区；B．释放区上邻（高地址邻接）空闲区；C．释放区上下都与空闲区邻接；D．释放区与空闲区不邻接。首次适应算法回收框图如图3所示。开始S=释放区始址L＝释放区长度查空闲区说明表有与释放区的高地址邻接（上邻）的空闲区吗?把上邻空闲区登记栏中的状态置为“空表目”，且将空表目向后调整在空闲区说明表中找一空闲表目登记：始址＝S长度＝L状态＝未分配按地址顺序调整和紧缩空闲区说明表把下邻空闲区登记栏中的长度改为：长度＝长度＋L把上邻空闲区登记栏中的始址改为S，长度为L返回N图3首次适应算法回收框图有与释放区下邻的空闲区吗?有与释放区下邻的空闲区吗?有等待装入的作业吗？唤醒等待的作业并返回L＝L＋上邻空闲区长度NYYYN若采用最佳适应算法，则空闲区说明表中的空闲区按其大小排序。有关最佳适应算法的分配和回收框图由学生自己给出。（4）请按首次（或最佳）适应算法设计主存分配和回收程序。以图1作为主存当前使用的基础，初始化空闲区和已分配区说明表的值。学生自己设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配与回收。把空闲区说明表的变化情况以及各作业的申请、释放情况显示或打印出来。为了说明哪些分区是空闲的，必须要有一张空闲区说明表，格式如下表所示：起始地址长度状态20K20K180K50K1150K100K1300K30K0（空表目）600K100K1……空表目………四、代码及运行结果分析Main.javapackageExp4;importjava.util.ArrayList;importjava.util.Scanner;publicclassMain{staticScannerscanner=newScanner(System.in);staticArrayListFreeBlockblockList=newArrayListFreeBlock();staticintapplication;staticintadr;staticintsize;publicstaticvoidmain(String[]args){initalize();}publicstaticvoidinitalize(){//将整个存储区作为freeBlock初始化并显示信息FreeBlockfreeBlock=newFreeBlock(0,32767);blockList.add(freeBlock);printAll();print(Pleaseinputtheway(1-best,2-first):);intway=scanner.nextInt();if(way==1){bestClass();//最佳适应算法}elseif(way==2){firstClass();//首次适应算法}else{print(Error!\n);}}publicstaticvoidbestClass(){inttype=getRequest();if(type==1){assign(1,application);}elseif(type==2){accept(adr,size);}else{print(Error!\n);}bestClass();}publicstaticvoidfirstClass(){inttype=getRequest();if(type==1){assign(2,application);}elseif(type==2){accept(adr,size);}else{print(Error!\n);}firstClass();}publicstaticvoidprintAll(){print(adr\tend\tsize\n);print(----------------------------\n);for(FreeBlockblock:blockList){block.printME();}}publicstaticintgetRequest(){print(AssignorAccept(1-Assign,2-Accept):);inttype=scanner.nextInt();if(type==1){print(inputApplication:);application=scanner.nextInt();}elseif(type==2){print(inputadrandsize:);adr=scanner.nextInt();size=scanner.nextInt();}else{print(Error!\n);}returntype;}publicstaticbooleanassign(intp_way,intp_application){//判断是否有空闲区if(blockList.isEmpty()){print(没有任何空闲区域可供分配！\n);returnfalse;}//按各自的原则查找空闲区if(p_way==1){//bestintminSize=32767;intminIndex=-1;for(FreeBlockblock:blockList){if(block.getSize()=minSize&&block.getSize()=p_application){minSize=block.getSize();minIndex=blockList.indexOf(block);}}if(minIndex==-1){print(没有符合要求的空闲区域！\n);returnfalse;}else{FreeBlocktempBlock1=blockList.get(minIndex);if(tempBlock1.getSize()==p_application){blockList.remove(tempBlock1);printAll();returntrue;}FreeBlocktempBlock2=newFreeBlock(tempBlock1.getAdr(),tempBlock1.getSize()-p_application);blockList.set(minIndex,tempBlock2);printAll();returntrue;}}elseif(p_way==2){//firstintminAdr=32766;intminIndex=-1;for(FreeBlockblock:blockList){if(block.getAdr()=minAdr&&block.getSize()=p_application){minAdr=block.getSize();minIndex=blockList.indexOf(block);}}if(minIndex==-1){print(没有符合要求的空闲区域！\n);returnfalse;}else{FreeBlocktempBlock1=blockList.get(minIndex);if(tempBlock1.getSize()==p_application){blockList.remove(tempBlock1);printAll();returntrue;}FreeBlocktempBlock2=newFreeBlock(tempBlock1.getAdr(),tempBlock1.getSize()-p_application);blockList.set(minIndex,tempBlock2);printAll();returntrue;}}else{print(Error!\n);returnfalse;}}publicstaticbooleanaccept(intp_adr,intp_size){intp_end=adr+size-1;//检查：首地址小于最小地址（0）if(p_adr0){print(错误：首地址小于最小地址（0）！\n);returnfalse;}//检查：回收空间大于最大空间(32766)if(p_end32766){print(错误：回收空间大于最大空间(32766)！\n);returnfalse;}//检查：回收空间和空闲空间重叠for(FreeBlockblock:blockList){if(p_adr=block.getAdr()&&p_adr=block.getEnd()){print(错误：回收空间和空闲空间重叠！\n);returnfalse;}if(p_end=block.getAdr()&&p_end=block.getEnd()){print(错误：回收空间和空闲空间重叠！\n);returnfalse;}}//检查：前有接续for(FreeBlockblock:blockList){if(p_adr-1==block.getEnd()){block.setSize(block.getSize()+p_size);//在前有接续的基础上，检查：后有接续for(FreeBlockblock2:blockList){if(block.getEnd()+1==block2.getAdr()){block.setSize(block.getSize()+bl