天津理工大学操作系统存储器的分配与回收算法实现实验报告.docx
《天津理工大学操作系统存储器的分配与回收算法实现实验报告.docx》由会员分享，可在线阅读，更多相关《天津理工大学操作系统存储器的分配与回收算法实现实验报告.docx（23页珍藏版）》请在冰点文库上搜索。
天津理工大学操作系统存储器的分配与回收算法实现实验报告
实验报告
学院（系）名称：
计算机与通信工程学院
姓名
nasta
学号
http:
//nasta.tk
专业
计算机科学与技术
班级
2010级2班
实验项目
实验二：
存储器的分配与回收算法实现
课程名称
操作系统
课程代码
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．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
【实验过程记录（源程序、测试用例、测试结果及心得体会等）】
源程序:
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;
}
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-blockNum>0）{
intnewBase=baseBlock+blockNum;
intnewBlock=this.blockNum-blockNum;
this.blockNum=blockNum;
setUse（）;
returnnewMemoryBlock（newBase,newBlock）;
}
elseif（this.blockNum-blockNum==0）{
this.blockNum=0;
}
returnnull;
}
//判断内存块是否能合并
publicbooleanmerge（MemoryBlockmemBlock）{
if（baseBlock+blockNum==memBlock.getBaseBlock（））{
setBlockNum（blockNum+memBlock.blockNum）;
memBlock.setBaseBlock（0）;
memBlock.setBlockNum（0）;
returntrue;
}
else
returnfalse;
}
@Override
publicStringtoString（）{
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）;
}
//在memBlock后插入newBlock
publicvoidinsert（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）;
break;
}
}
memBlock=memBlock.getNext（）;
}
}
//分配内存（抽象函数）
publicabstractbooleanallocate（intblockNum）;
//释放内存（抽象函数）
publicabstractbooleanfree（intbaseBlock）;
}
FirstFit.java:
publicclassFirstFitextendsMemoryTable{
publicFirstFit（intblockNum）{
super（blockNum）;
}
@Override
publicbooleanallocate（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）{
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;
}
}
}
@Override
publicbooleanfree（intbaseBlock）{
MemoryBlockmemBlock=memList;
while（memBlock!
=null）{
if（memBlock.getBaseBlock（）==baseBlock）{
freeMemory（memBlock）;
returntrue;
}
memBlock=memBlock.getNext（）;
}
returnfalse;
}
}
BestFit.java:
publicclassBestFitextendsMemoryTable{
privateMemoryBlockusedMemory;
publicBestFit（intblockNum）{
super（blockNum）;
usedMemory=null;
}
@Override
publicbooleanallocate（intblockNum）{
MemoryBlockmemBlock=memList;
MemoryBlockminBlock=null;
for（;memBlock!
=null;memBlock=memBlock.getNext（））{
if（!
memBlock.inUse（）&&（memBlock.getBlockNum（）>=blockNum））{
minBlock=memBlock;
break;
}
}
if（minBlock!
=null）{
remove（minBlock）;
if（minBlock.getBlockNum（）!
=blockNum）{
MemoryBlocknewBlock=minBlock.allocate（blockNum）;
insertUnused（newBlock）;
}
insertUsed（minBlock）;
returntrue;
}
else
returnfalse;
}
booleanfreeMemory（MemoryBlockfreeBlock）{
if（freeBlock!
=null）{
freeBlock.free（）;
removeUsed（freeBlock）;
insertUnused（freeBlock）;
returntrue;
}
returnfalse;
}
@Override
publicbooleanfree（intbaseBlock）{
MemoryBlockmemBlock=usedMemory;
while（memBlock!
=null）{
if（memBlock.getBaseBlock（）==baseBlock）{
freeMemory（memBlock）;
merge（memBlock）;
returntrue;
}
memBlock=memBlock.getNext（）;
}
returnfalse;
}
//在已分配链表删除
publicvoidremoveUsed（MemoryBlockmemBlock）{
if（memBlock==usedMemory）
usedMemory=memBlock.getNext（）;
if（memBlock.getNext（）!
=null）
memBlock.getNext（）.setPrev（memBlock.getPrev（））;
if（memBlock.getPrev（）!
=null）
memBlock.getPrev（）.setNext（memBlock.getNext（））;
}
//插入未分配链表
voidinsertUnused（MemoryBlocknewBlock）{
if（memList==null）
memList=newBlock;
else{
MemoryBlockmemBlock=memList;
MemoryBlockpreBlock=null;
while（memBlock!
=null）{
if（newBlock.getBlockNum（）<=memBlock.getBlockNum（））{
insertBefore（memBlock,newBlock）;
return;
}
preBlock=memBlock;
memBlock=memBlock.getNext（）;
}
insert（preBlock,newBlock）;
}
}
//插入已分配链表
voidinsertUsed（MemoryBlocknewBlock）{
if（usedMemory==null）
usedMemory=newBlock;
else{
MemoryBlockmemBlock=usedMemory;
while（memBlock.getNext（）!
=null）
memBlock=memBlock.getNext（）;
memBlock.setNext（newBlock）;
newBlock.setPrev（memBlock）;
}
}
publicvoidprint（）{
super.print（）;
MemoryBlockmemBlock=usedMemory;
inti=0;
while（memBlock!
=null）{
System.out.print（i+""）;
System.out.println（memBlock）;
i++;
memBlock=memBlock.getNext（）;
}
}
}
WorstFit.java:
publicclassWorstFitextendsMemoryTable{
//已分配链表
privateMemoryBlockusedMemory;
publicWorstFit（intblockNum）{
super（blockNum）;
usedMemory=null;
}
@Override
publicbooleanallocate（intblockNum）{
MemoryBlockmaxBlock=memList;
if（maxBlock.getBlockNum（）returnfalse;
remove（maxBlock）;
if（maxBlock.getBlockNum（）!
=blockNum）{
MemoryBlocknewBlock=maxBlock.allocate（blockNum）;
insertUnused（newBlock）;
}
insertUsed（maxBlock）;
returntrue;
}
booleanfreeMemory（MemoryBlockfreeBlock）{
if（freeBlock!
=null）{
freeBlock.free（）;
removeUsed（freeBlock）;
insertUnused（freeBlock）;
returntrue;
}
returnfalse;
}
@Override
publicbooleanfree（intbaseBlock）{
//已分配链表
MemoryBlockmemBlock=usedMemory;
while（memBlock!
=null）{
if（memBlock.getBaseBlock（）==baseBlock）{
freeMemory（memBlock）;
merge（memBlock）;
returntrue;
}
memBlock=memBlock.getNext（）;
}
returnf
升级会员 