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

实验报告学院（系）名称：计算机与通信工程学院姓名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:/内存块类，包含各种操作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 - blockNum0) 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;elsereturn false;Overridepublic 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后插入newBlockpublic 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);break;memBlock = memBlock.getNext();/分配内存（抽象函数）public abstract boolean allocate(int blockNum);/释放内存（抽象函数）public abstract boolean free(int baseBlock);FirstFit.java:public class FirstFit extends MemoryTablepublic FirstFit(int blockNum) super(blockNum);Overridepublic 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();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();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;Overridepublic 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;Overridepublic 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;elsereturn false;boolean freeMemory(MemoryBlock freeBlock) if(freeBlock != null) freeBlock.free();removeUsed(freeBlock);insertUnused(freeBlock);return true;return false;Overridepublic 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;Overridepublic boolean allocate(int blockNum) MemoryBlock maxBlock = memList;if(maxBlock.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(512);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