主存空间地分配与回收.docx
《主存空间地分配与回收.docx》由会员分享，可在线阅读，更多相关《主存空间地分配与回收.docx（18页珍藏版）》请在冰点文库上搜索。
主存空间地分配与回收
操作系统实验报告
实验三：
主存空间的分配与回收
一、实验题目
采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收
二、实验内容
主存是中央处理机能直接存取指令和数据的存储器。
能否合理而有效地使用主存，在很大程度上将影响到整个计算机系统的性能。
本实验采用可变式分区管理，使用首次或最佳适应算法实现主存空间的分配与回收。
要求采用分区说明表进行。
三、实验目的
通过本次实验，帮助学生理解在可变式分区管理方式下，如何实现主存空间的分配与回收。
提示：
（1）可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。
当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无，则作业等待。
随着作业的装入、完成，主存空间被分割成许多大大小小的分区。
有的分区被作业占用，有的分区空闲。
例如，某时刻主存空间占用情况如图1所示。
0
表1空闲区说明表
操作系统（10KB）
10K
作业1（10KB）
20K
作业4（25KB）
45K
空闲区1（20KB）
65K
作业2（45KB）
110K
256K
空闲区2（146KB）
起始地址
长度
状态
45K
20KB
未分配
110K
146KB
未分配
空表目
空表目
空表目
…
…
…
图1主存空间占用情况
为了说明哪些分区是空闲的，可以用来装入新的作业，必须要有一张空闲区说明表，如表1所示。
其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。
状态栏未分配指该栏目是记录的有效空闲区，空表目指没有登记信息。
由于分区个数不定，所以空闲区说明表中应有足够的空表目项，否则造成溢出，无法登记。
同样，再设一个已分配区表，记录作业或进城的主存占用情况。
（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。
有时找到的空闲区可能大于作业需求量，这时应该将空闲区一分为二。
一个分给作业，另一个仍作为空闲区留在空闲区表中。
为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。
为此在空闲区表中，按空闲区首地址从低到高进行登记。
为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。
其分配框图如图2所示。
（3）当一个作业执行完时，作业所占用的分区应归还给系统。
在归还时要考虑相邻空闲区合并的问题。
作业的释放区与空闲区的邻接分一下4种情况考虑：
A．释放区下邻（低地址邻接）空闲区；
B．释放区上邻（高地址邻接）空闲区；
C．释放区上下都与空闲区邻接；
D．释放区与空闲区不邻接。
首次适应算法回收框图如图3所示。
若采用最佳适应算法，则空闲区说明表中的空闲区按其大小排序。
有关最佳适应算法的分配和回收框图由学生自己给出。
（4）请按首次（或最佳）适应算法设计主存分配和回收程序。
以图1作为主存当前使用的基础，初始化空闲区和已分配区说明表的值。
学生自己设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配与回收。
把空闲区说明表的变化情况以及各作业的申请、释放情况显示或打印出来。
为了说明哪些分区是空闲的，必须要有一张空闲区说明表，格式如下表所示：
起始地址
长度
状态
20K
20K
1
80K
50K
1
150K
100K
1
300K
30K
0（空表目）
600K
100K
1
…
…
空表目
…
…
…
四、代码及运行结果分析
Main.java
packageExp4;
importjava.util.ArrayList;
importjava.util.Scanner;
publicclassMain{
staticScannerscanner=newScanner（System.in）;
staticArrayListblockList=newArrayList（）;
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）{
//best
intminSize=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）{
//first
intminAdr=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_adr<0）{
print（"错误：
首地址小于最小地址（0）！
\n"）;
returnfalse;
}
//检查：
回收空间大于最大空间（32766）
if（p_end>32766）{
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（）+block2.getSize（））;
blockList.remove（block2）;
printAll（）;
returntrue;
}
}
printAll（）;
returntrue;
}
}
//检查：
后有接续（前肯定没有接续）
for（FreeBlockblock:
blockList）{
if（p_end+1==block.getAdr（））{
block.setAdr（p_adr）;
block.setSize（block.getSize（）+p_size）;
printAll（）;
returntrue;
}
}
//前后均无接续
FreeBlockfreeBlock=newFreeBlock（p_adr,p_size）;
blockList.add（freeBlock）;
printAll（）;
returntrue;
}
publicstaticvoidprint（StringprintString）{
System.out.print（printString）;
}
}
FreeBlock.java
packageExp4;
publicclassFreeBlock{
privateintadr;
privateintsize;
publicFreeBlock（intp_adr,intp_size）{
adr=p_adr;
size=p_size;
}
publicvoidprintME（）{
System.out.println（this.getAdr（）+"\t"+this.getEnd（）+"\t"
+this.getSize（））;
System.out.println（"----------------------------"）;
}
publicintgetEnd（）{
if（size>0）{
returnadr+size-1;
}else{
return0;
}
}
publicintgetAdr（）{
returnadr;
}
publicvoidsetAdr（intadr）{
this.adr=adr;
}
publicintgetSize（）{
returnsize;
}
publicvoidsetSize（intsize）{
this.size=size;
}
}
最佳适应算法结果
首次适应算法结果
五、心得体会
经过这次实验，对可变式分区管理方式下，如何实现主存空间的分配与回收，有了很深的了解，使用了两种不同的算法，来实现对主存空间的控制，两种算法使用的数据结构相同，只是在分配的时候有差异。
同时在回收内存的时候，要尤其注意回收空间与空闲空间的位置对应关系。
升级会员 