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

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

实验报告

学院（系）名称：计算机与通信工程学院

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

【实验过程记录（源程序、测试用例、测试结果及心得体会等）】 源程序:

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() { } public void setNext(MemoryBlock next) { } public boolean inUse() { } public void setUse() { } public void free() { } public int getBaseBlock() { } public void setBaseBlock(int baseBlock) { } //分配内存块，如果可分配，则返回剩余内存块 public MemoryBlock allocate(int blockNum) { } if(this.blockNum - blockNum>0) { } else if(this.blockNum - blockNum ==0) { } return null; this.blockNum = 0; int newBase = baseBlock + blockNum; int newBlock = this.blockNum-blockNum; this.blockNum = blockNum; setUse(); return new MemoryBlock(newBase, newBlock); this.baseBlock = baseBlock; return baseBlock; inUse = false; inUse = true; return inUse; this.next = next; return next;

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

} public boolean merge(MemoryBlock memBlock) { } @Override public String toString() { } String inUse = null; if(inUse())inUse = "已分配"; else inUse = "未分配"; return "内存块 [基地址=" + baseBlock + ", 大小=" + blockNum + ", " + inUse + "]"; if(baseBlock+blockNum==memBlock.getBaseBlock()) { } else return false; setBlockNum(blockNum+memBlock.blockNum); memBlock.setBaseBlock(0); memBlock.setBlockNum(0); return true;

MemoryTable.java:

//虚类MemTable，提供内存链表的各种基本方法

public abstract class MemoryTable {

//MemoryBlock链表表头 protected MemoryBlock memList; public MemoryTable(int blockNum) { } //把newBlock插入到memBlock前面 public void insertBefore(MemoryBlock memBlock, MemoryBlock } if(memBlock.getPrev() != null) memBlock.getPrev().setNext(newBlock); memList = newBlock; if(memList == memBlock) newBlock.setPrev(memBlock.getPrev()); newBlock.setNext(memBlock); memBlock.setPrev(newBlock); memList = new MemoryBlock(0, blockNum); newBlock){

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

public void insert(MemoryBlock memBlock, MemoryBlock newBlock) { } //删除块的连接关系，但不释放块 public void remove(MemoryBlock memBlock) { } public void print() { } //合并邻接的空闲内存 public void merge(MemoryBlock newBlock) { MemoryBlock memBlock = memList; while(memBlock != null) { if(!memBlock.inUse()) { if(memBlock.merge(newBlock)) {

memBlock.setBlockNum( memBlock.getBlockNum() +

newBlock.getBlockNum()); MemoryBlock memBlock = memList; int i=0; while(memBlock != null) { } System.out.print(i+" "); System.out.println(memBlock); i++; memBlock = memBlock.getNext(); if(memBlock == memList) memList = memBlock.getNext(); memBlock.getNext().setPrev(memBlock.getPrev()); memBlock.getPrev().setNext(memBlock.getNext()); if(memBlock.getNext()!=null) if(memBlock.getPrev()!=null) if(memBlock.getNext() != null) memBlock.getNext().setPrev(newBlock); newBlock.setNext(memBlock.getNext()); memBlock.setNext(newBlock); newBlock.setPrev(memBlock);

} remove(newBlock); break; if(newBlock.merge(memBlock)) { newBlock.setBlockNum( newBlock.getBlockNum() + remove(memBlock);

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{

@Override public boolean allocate(int blockNum) { } //分配内存（类内使用） void freeMemory(MemoryBlock freeBlock) { MemoryBlock prev = freeBlock.getPrev(); MemoryBlock next = freeBlock.getNext(); freeBlock.free(); if(freeBlock.getPrev()!=null) {

public FirstFit(int blockNum) { } super(blockNum); MemoryBlock memBlock = memList; while(memBlock!=null) { } return false; if(!memBlock.inUse()) { } memBlock = memBlock.getNext(); if(memBlock.getBlockNum()>blockNum) { } else if(memBlock.getBlockNum()==blockNum) { } memBlock.setUse(); MemoryBlock newBlock = memBlock.allocate(blockNum); insert(memBlock, newBlock); return true;

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

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) { } return false; if(memBlock.getBaseBlock() == baseBlock) { } memBlock = memBlock.getNext(); freeMemory(memBlock); return true;

BestFit.java:

public class BestFit extends MemoryTable {

private MemoryBlock usedMemory; public BestFit(int blockNum) { } super(blockNum); usedMemory = null;

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

@Override public boolean allocate(int blockNum) { } boolean freeMemory(MemoryBlock freeBlock) { } @Override public boolean free(int baseBlock) { MemoryBlock memBlock = usedMemory; while(memBlock != null) { }

MemoryBlock memBlock = memList; MemoryBlock minBlock = null; for(;memBlock!=null; memBlock = memBlock.getNext()) { } if(minBlock != null) { } else return false; remove(minBlock); if(minBlock.getBlockNum()!=blockNum) { } insertUsed(minBlock); return true; MemoryBlock newBlock = minBlock.allocate(blockNum); insertUnused(newBlock); if(!memBlock.inUse()&&(memBlock.getBlockNum()>=blockNum)) { } minBlock = memBlock; break; if(freeBlock != null) { } return false; freeBlock.free(); removeUsed(freeBlock); insertUnused(freeBlock); return true; if(memBlock.getBaseBlock() == baseBlock) { } memBlock = memBlock.getNext(); freeMemory(memBlock); merge(memBlock); return true;

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

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 {

boolean freeMemory(MemoryBlock freeBlock) { if(freeBlock != null) { freeBlock.free(); removeUsed(freeBlock); insertUnused(freeBlock); return true;

//已分配链表 private MemoryBlock usedMemory; public WorstFit(int blockNum) { } @Override public boolean allocate(int blockNum) { } MemoryBlock maxBlock = memList; if(maxBlock.getBlockNum()<blockNum) return false; super(blockNum); usedMemory = null; remove(maxBlock); if(maxBlock.getBlockNum()!=blockNum) { } insertUsed(maxBlock); return true; MemoryBlock newBlock = maxBlock.allocate(blockNum); insertUnused(newBlock);

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

}

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);

}

}

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

} } 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(); if(usedMemory == null) } usedMemory = newBlock; MemoryBlock memBlock = usedMemory; while(memBlock.getNext() != null) memBlock = memBlock.getNext(); memBlock.setNext(newBlock); newBlock.setPrev(memBlock); else {

测试用例:

Main.java:

public class Main {

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(512);

public static void main(String[] args) { } testFirstFit(); System.out.println(); testBestFit(); System.out.println(); testWorstFit();

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

}

} mem.print(); public static void testBestFit() { } 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(); 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();

测试结果:

测试首次适应法:

分配 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. 链表应根据具体情况优化从而简化代码

本文来源：https://www.bwwdw.com/article/nepi.html