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

第1页 共14页

实验报告

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

姓名 nasta 学号 专业 计算机科学与技术

班级 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． 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。 第2页 共14页

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

源程序:

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;

} 第3页 共14页 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;

}

第4页 共14页 //判断内存块是否能合并

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

}

第5页 共14页 //在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());

remove(memBlock);