天津理工大学-操作系统-存储器的分配与回收算法实现-实验报告

第1页共14页实验报告学院（系）名称：计算机与通信工程学院姓名nasta学号班实验项目实验二：存储器的分配与回收算法实现课程名称操作系统课程代码0668036实验时间2012年12月13日第7、8节2012年12月17日第3、4节2012年12月20日第7、8节实验地点软件实验室7-215批改意见成绩教师签字：实验内容：1.模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。2.采用最先适应法、最佳适应法、最坏适应法分配主存空间。3.当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4.当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5.运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。实验要求：1．详细描述实验设计思想、程序结构及各模块设计思路；2．详细描述程序所用数据结构及算法；3．明确给出测试用例和实验结果；4．为增加程序可读性，在程序中进行适当注释说明；5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；6．实验报告撰写要求结构清晰、描述准确逻辑性强；7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。第2页共14页【实验过程记录（源程序、测试用例、测试结果及心得体会等）】源程序:MemoryBlock.java://内存块类，包含各种操作publicclassMemoryBlock{staticfinalintBLOCK_SIZE=4096;privateintbaseBlock;//内存块基地址privateintblockNum;//大小privatebooleaninUse;//是否已分配privateMemoryBlockprev,next;publicMemoryBlock(intblockNum){this.baseBlock=0;this.blockNum=blockNum;inUse=false;prev=null;next=null;}publicMemoryBlock(intbase,intblockNum){this.baseBlock=base;this.blockNum=blockNum;inUse=false;prev=null;next=null;}publicintgetBlockNum(){returnblockNum;}publicvoidsetBlockNum(intblockNum){this.blockNum=blockNum;}publicMemoryBlockgetPrev(){returnprev;}publicvoidsetPrev(MemoryBlockprev){this.prev=prev;}第3页共14页publicMemoryBlockgetNext(){returnnext;}publicvoidsetNext(MemoryBlocknext){this.next=next;}publicbooleaninUse(){returninUse;}publicvoidsetUse(){inUse=true;}publicvoidfree(){inUse=false;}publicintgetBaseBlock(){returnbaseBlock;}publicvoidsetBaseBlock(intbaseBlock){this.baseBlock=baseBlock;}//分配内存块，如果可分配，则返回剩余内存块publicMemoryBlockallocate(intblockNum){if(this.blockNum-blockNum0){intnewBase=baseBlock+blockNum;intnewBlock=this.blockNum-blockNum;this.blockNum=blockNum;setUse();returnnewMemoryBlock(newBase,newBlock);}elseif(this.blockNum-blockNum==0){this.blockNum=0;}returnnull;}第4页共14页//判断内存块是否能合并publicbooleanmerge(MemoryBlockmemBlock){if(baseBlock+blockNum==memBlock.getBaseBlock()){setBlockNum(blockNum+memBlock.blockNum);memBlock.setBaseBlock(0);memBlock.setBlockNum(0);returntrue;}elsereturnfalse;}@OverridepublicStringtoString(){StringinUse=null;if(inUse())inUse=已分配;elseinUse=未分配;return内存块[基地址=+baseBlock+,大小=+blockNum+,+inUse+];}}MemoryTable.java://虚类MemTable，提供内存链表的各种基本方法publicabstractclassMemoryTable{//MemoryBlock链表表头protectedMemoryBlockmemList;publicMemoryTable(intblockNum){memList=newMemoryBlock(0,blockNum);}//把newBlock插入到memBlock前面publicvoidinsertBefore(MemoryBlockmemBlock,MemoryBlocknewBlock){if(memBlock.getPrev()!=null)memBlock.getPrev().setNext(newBlock);if(memList==memBlock)memList=newBlock;newBlock.setPrev(memBlock.getPrev());newBlock.setNext(memBlock);memBlock.setPrev(newBlock);}第5页共14页//在memBlock后插入newBlockpublicvoidinsert(MemoryBlockmemBlock,MemoryBlocknewBlock){if(memBlock.getNext()!=null)memBlock.getNext().setPrev(newBlock);newBlock.setNext(memBlock.getNext());memBlock.setNext(newBlock);newBlock.setPrev(memBlock);}//删除块的连接关系，但不释放块publicvoidremove(MemoryBlockmemBlock){if(memBlock==memList)memList=memBlock.getNext();if(memBlock.getNext()!=null)memBlock.getNext().setPrev(memBlock.getPrev());if(memBlock.getPrev()!=null)memBlock.getPrev().setNext(memBlock.getNext());}publicvoidprint(){MemoryBlockmemBlock=memList;inti=0;while(memBlock!=null){System.out.print(i+);System.out.println(memBlock);i++;memBlock=memBlock.getNext();}}//合并邻接的空闲内存publicvoidmerge(MemoryBlocknewBlock){MemoryBlockmemBlock=memList;while(memBlock!=null){if(!memBlock.inUse()){if(memBlock.merge(newBlock)){memBlock.setBlockNum(memBlock.getBlockNum()+newBlock.getBlockNum());remove(newBlock);break;}if(newBlock.merge(memBlock)){newBlock.setBlockNum(newBlock.getBlockNum()+memBlock.getBlockNum());remove(memBlock);第6页共14页break;}}memBlock=memBlock.getNext();}}//分配内存（抽象函数）publicabstractbooleanallocate(intblockNum);//释放内存（抽象函数）publicabstractbooleanfree(intbaseBlock);}FirstFit.java:publicclassFirstFitextendsMemoryTable{publicFirstFit(intblockNum){super(blockNum);}@Overridepublicbooleanallocate(intblockNum){MemoryBlockmemBlock=memList;while(memBlock!=null){if(!memBlock.inUse()){if(memBlock.getBlockNum()blockNum){MemoryBlocknewBlock=memBlock.allocate(blockNum);insert(memBlock,newBlock);returntrue;}elseif(memBlock.getBlockNum()==blockNum){memBlock.setUse();}}memBlock=memBlock.getNext();}returnfalse;}//分配内存（类内使用）voidfreeMemory(MemoryBlockfreeBlock){MemoryBlockprev=freeBlock.getPrev();MemoryBlocknext=freeBlock.getNext();freeBlock.free();if(freeBlock.getPrev()!=null){第7页共14页while(!prev.inUse()&&(prev.merge(freeBlock))){prev.setBlockNum(prev.getBlockNum()+freeBlock.getBlockNum());remove(freeBlock);freeBlock=prev;if(freeBlock.getPrev()!=null)prev=freeBlock.getPrev();elsereturn;}}if(freeBlock.getNext()!=null){while(!next.inUse()&&(freeBlock.merge(next))){freeBlock.setBlockNum(next.getBlockNum()+freeBlock.getBlockNum());remove(next);freeBlock=next;if(freeBlock.getNext()!=null)next=freeBlock.getNext();elsereturn;}}}@Overridepublicbooleanfree(intbaseBlock){MemoryBlockmemBlock=memList;while(memBlock!=null){if(memBlock.getBaseBl