天津理工大学_操作系统_存储器的分配与回收算法实现_实验报告
实验报告学院（系）名称：计算机与通信工程学院
【实验过程记录（源程序、测试用例、测试结果及心得体会等）】源程序:
MemoryBlock.java:
//内存块类，包含各种操作
public class MemoryBlock {
static final int BLOCK_SIZE = 4096;
private int baseBlock; //内存块基地址
private int blockNum; //大小
private boolean inUse; //是否已分配
private MemoryBlock prev, next;
public MemoryBlock(int blockNum) {
this.baseBlock = 0;
this.blockNum = blockNum;
inUse = false;
prev = null;
next = null;
}
public MemoryBlock(int base, int blockNum) {
this.baseBlock = base;
this.blockNum = blockNum;
inUse = false;
prev = null;
next = null;
}
public int getBlockNum() {
return blockNum;
}
public void setBlockNum(int blockNum) {
this.blockNum = blockNum;
}
public MemoryBlock getPrev() {
return prev;
}
public void setPrev(MemoryBlock prev) {
this.prev = prev;
public MemoryBlock getNext() {
return next;
}
public void setNext(MemoryBlock next) {
this.next = next;
}
public boolean inUse() {
return inUse;
}
public void setUse() {
inUse = true;
}
public void free() {
inUse = false;
}
public int getBaseBlock() {
return baseBlock;
}
public void setBaseBlock(int baseBlock) { this.baseBlock = baseBlock;
}
//分配内存块，如果可分配，则返回剩余内存块
public MemoryBlock allocate(int blockNum) { if(this.blockNum - blockNum>0) {
int newBase = baseBlock + blockNum;
int newBlock = this.blockNum-blockNum;
this.blockNum = blockNum;
setUse();
return new MemoryBlock(newBase, newBlock);
}
else if(this.blockNum - blockNum ==0) {
this.blockNum = 0;
}
return null;
}
//判断内存块是否能合并
public boolean merge(MemoryBlock memBlock) {
if(baseBlock+blockNum==memBlock.getBaseBlock()) {
setBlockNum(blockNum+memBlock.blockNum);
memBlock.setBaseBlock(0);
memBlock.setBlockNum(0);
return true;
}
else
return false;
}
@Override
public String toString() {
String inUse = null;
if(inUse())inUse = "已分配";
else inUse = "未分配";
return"内存块 [基地址=" + baseBlock + ", 大小=" + blockNum +
", " + inUse + "]";
}
}
MemoryTable.java:
//虚类MemTable，提供内存链表的各种基本方法
public abstract class MemoryTable {
//MemoryBlock链表表头
protected MemoryBlock memList;
public MemoryTable(int blockNum) {
memList = new MemoryBlock(0, blockNum);
}
//把newBlock插入到memBlock前面
public void insertBefore(MemoryBlock memBlock, MemoryBlock newBlock){
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
public void insert(MemoryBlock memBlock, MemoryBlock newBlock) { if(memBlock.getNext() != null)
memBlock.getNext().setPrev(newBlock);
newBlock.setNext(memBlock.getNext());
memBlock.setNext(newBlock);
newBlock.setPrev(memBlock);
}
//删除块的连接关系，但不释放块
public void remove(MemoryBlock memBlock) {
if(memBlock == memList)
memList = memBlock.getNext();
if(memBlock.getNext()!=null)
memBlock.getNext().setPrev(memBlock.getPrev());
if(memBlock.getPrev()!=null)
memBlock.getPrev().setNext(memBlock.getNext());
}
public void print() {
MemoryBlock memBlock = memList;
int i=0;
while(memBlock != null) {
System.out.print(i+" ");
System.out.println(memBlock);
i++;
memBlock = memBlock.getNext();
}
}
//合并邻接的空闲内存
public void merge(MemoryBlock newBlock) {
MemoryBlock memBlock = 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());
break;
}
}
memBlock = memBlock.getNext();
}
}
//分配内存（抽象函数）
public abstract boolean allocate(int blockNum);
//释放内存（抽象函数）
public abstract boolean free(int baseBlock);
}
FirstFit.java:
public class FirstFit extends MemoryTable{
public FirstFit(int blockNum) {
super(blockNum);
}
@Override
public boolean allocate(int blockNum) {
MemoryBlock memBlock = memList;
while(memBlock!=null) {
if(!memBlock.inUse()) {
if(memBlock.getBlockNum()>blockNum) {
MemoryBlock newBlock = memBlock.allocate(blockNum);
insert(memBlock, newBlock);
return true;
}
else if(memBlock.getBlockNum()==blockNum) {
memBlock.setUse();
}
}
memBlock = memBlock.getNext();
}
return false;
}
//分配内存（类内使用）
void freeMemory(MemoryBlock freeBlock) {
MemoryBlock prev = freeBlock.getPrev();
MemoryBlock next = freeBlock.getNext();
freeBlock.free();
while(!prev.inUse() && (prev.merge(freeBlock))) {
prev.setBlockNum( prev.getBlockNum() +
freeBlock.getBlockNum());
remove(freeBlock);
freeBlock = prev;
if(freeBlock.getPrev()!=null)
prev = freeBlock.getPrev();
else return;
}
}
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();
else return;
}
}
}
@Override
public boolean free(int baseBlock) {
MemoryBlock memBlock = memList;
while(memBlock != null) {
if(memBlock.getBaseBlock() == baseBlock) {
freeMemory(memBlock);
return true;
}
memBlock = memBlock.getNext();
}
return false;
}
}
BestFit.java:
public class BestFit extends MemoryTable {
private MemoryBlock usedMemory;
public BestFit(int blockNum) {
super(blockNum);
usedMemory = null;
}
@Override
public boolean allocate(int blockNum) {
MemoryBlock memBlock = memList;
MemoryBlock minBlock = 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) {
MemoryBlock newBlock = minBlock.allocate(blockNum);
insertUnused(newBlock);
}
insertUsed(minBlock);
return true;
}
else
return false;
}
boolean freeMemory(MemoryBlock freeBlock) {
if(freeBlock != null) {
freeBlock.free();
removeUsed(freeBlock);
insertUnused(freeBlock);
return true;
}
return false;
}
@Override
public boolean free(int baseBlock) {
MemoryBlock memBlock = usedMemory;
while(memBlock != null) {
if(memBlock.getBaseBlock() == baseBlock) {
freeMemory(memBlock);
merge(memBlock);
return true;
}
memBlock = memBlock.getNext();
return false;
}
//在已分配链表删除
public void removeUsed(MemoryBlock memBlock) {
if(memBlock == usedMemory)
usedMemory = memBlock.getNext();
if(memBlock.getNext()!=null)
memBlock.getNext().setPrev(memBlock.getPrev());
if(memBlock.getPrev()!=null)
memBlock.getPrev().setNext(memBlock.getNext());
}
//插入未分配链表
void insertUnused(MemoryBlock newBlock) {
if(memList == null)
memList = newBlock;
else {
MemoryBlock memBlock = memList;
MemoryBlock preBlock = null;
while(memBlock!=null) {
if(newBlock.getBlockNum()<=memBlock.getBlockNum()) { insertBefore(memBlock, newBlock);
return;
}
preBlock = memBlock;
memBlock = memBlock.getNext();
}
insert(preBlock, newBlock);
}
}
//插入已分配链表
void insertUsed(MemoryBlock newBlock) {
if(usedMemory == null)
usedMemory = newBlock;
else {
MemoryBlock memBlock = usedMemory;
while(memBlock.getNext() != null)
memBlock = memBlock.getNext();
memBlock.setNext(newBlock);
newBlock.setPrev(memBlock);
}
}
public void print() {
super.print();
MemoryBlock memBlock = usedMemory;
int i=0;
while(memBlock != null) {
System.out.print(i+" ");
System.out.println(memBlock);
i++;
memBlock = memBlock.getNext();
}
}
}
WorstFit.java:
public class WorstFit extends MemoryTable {
//已分配链表
private MemoryBlock usedMemory;
public WorstFit(int blockNum) {
super(blockNum);
usedMemory = null;
}
@Override
public boolean allocate(int blockNum) {
MemoryBlock maxBlock = memList;
if(maxBlock.getBlockNum() return false; remove(maxBlock); if(maxBlock.getBlockNum()!=blockNum) { MemoryBlock newBlock = maxBlock.allocate(blockNum); insertUnused(newBlock); } insertUsed(maxBlock); return true; } boolean freeMemory(MemoryBlock freeBlock) { if(freeBlock != null) { freeBlock.free(); removeUsed(freeBlock); insertUnused(freeBlock); } return false; } @Override public boolean free(int baseBlock) { //已分配链表 MemoryBlock memBlock = usedMemory; while(memBlock != null) { if(memBlock.getBaseBlock() == baseBlock) { freeMemory(memBlock); merge(memBlock); return true; } memBlock = memBlock.getNext(); } return false; } public void removeUsed(MemoryBlock memBlock) { if(memBlock == usedMemory) usedMemory = memBlock.getNext(); if(memBlock.getNext()!=null) memBlock.getNext().setPrev(memBlock.getPrev()); if(memBlock.getPrev()!=null) memBlock.getPrev().setNext(memBlock.getNext()); } void insertUnused(MemoryBlock newBlock) { if(memList == null) memList = newBlock; else { MemoryBlock memBlock = memList; MemoryBlock preBlock = null; while(memBlock!=null) { if(newBlock.getBlockNum()>=memBlock.getBlockNum()) { insertBefore(memBlock, newBlock); return; } preBlock = memBlock; memBlock = memBlock.getNext(); } insert(preBlock, newBlock); } void insertUsed(MemoryBlock newBlock) { if(usedMemory == null) usedMemory = newBlock; else { MemoryBlock memBlock = usedMemory; while(memBlock.getNext() != null) memBlock = memBlock.getNext(); memBlock.setNext(newBlock); newBlock.setPrev(memBlock); } } public void print() { super.print(); MemoryBlock memBlock = usedMemory; int i=0; while(memBlock != null) { System.out.print(i+" "); System.out.println(memBlock); i++; memBlock = memBlock.getNext(); } } } 测试用例: Main.java: public class Main { public static void main(String[] args) { testFirstFit(); System.out.println(); testBestFit(); System.out.println(); testWorstFit(); } public static void testFirstFit() { MemoryTable mem = new FirstFit(1024); System.out.println("测试首次适应法:"); mem.allocate(512); mem.allocate(256); mem.allocate(128); mem.print(); mem.free(768); mem.print(); } public static void testBestFit() { MemoryTable mem = new BestFit(1024); System.out.println("测试最佳适应法:"); mem.allocate(1); mem.allocate(2); mem.allocate(3); mem.print(); mem.free(0); mem.free(1); mem.print(); } public static void testWorstFit() { MemoryTable mem = new WorstFit(1024); System.out.println("测试最坏适应法:"); mem.allocate(1); mem.allocate(2); mem.allocate(3); mem.print(); mem.free(0); mem.free(3); mem.print(); } } 测试结果: 测试首次适应法: 分配 512 内存 分配 256 内存 分配 128 内存 内存单元: 0 内存块 [基地址=0, 大小=512, 已分配] 1 内存块 [基地址=512, 大小=256, 已分配] 2 内存块 [基地址=768, 大小=128, 已分配] 3 内存块 [基地址=896, 大小=128, 未分配] 释放 512 处内存 释放 768 处内存 内存单元: 0 内存块 [基地址=0, 大小=512, 已分配] 1 内存块 [基地址=512, 大小=512, 未分配] 测试最佳适应法: 分配 1 内存 分配 2 内存 分配 3 内存 内存单元: 0 内存块 [基地址=6, 大小=1018, 未分配] 0 内存块 [基地址=0, 大小=1, 已分配] 1 内存块 [基地址=1, 大小=2, 已分配] 2 内存块 [基地址=3, 大小=3, 已分配] 释放 0 处内存 释放 1 处内存 内存单元: 0 内存块 [基地址=0, 大小=3, 未分配] 1 内存块 [基地址=6, 大小=1018, 未分配] 0 内存块 [基地址=3, 大小=3, 已分配] 测试最坏适应法: 分配 1 内存 分配 2 内存 分配 3 内存 内存单元: 0 内存块 [基地址=6, 大小=1018, 未分配] 0 内存块 [基地址=0, 大小=1, 已分配] 1 内存块 [基地址=1, 大小=2, 已分配] 2 内存块 [基地址=3, 大小=3, 已分配] 释放 0 处内存 释放 3 处内存 内存单元: 0 内存块 [基地址=3, 大小=1021, 未分配] 1 内存块 [基地址=0, 大小=1, 未分配] 0 内存块 [基地址=1, 大小=2, 已分配] 心得体会: 1.使用类来进行一些方法的重用 2.释放内存时，根据不同的分配方法进行相邻的内存合并 3.链表应根据具体情况优化从而简化代码