1、人和以專實驗報告學院（系）名稱： 計算機與通信工程學院姓名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. 當一個新作業要求裝入主存時，必須查空閑區表，

2、從中找出一個足夠大的空閑區。若找到的空閑區 大于作業需要量，這是應把它分成二部分，一部分為占用區，加一部分又成為一個空閑區。4. 當一個作業撤離時，歸還的區域如果與其他空閑區相鄰，則應合并成一個較大的空閑區，登在空閑 區表中。5. 運行所設計的程序，輸出有關數據結構表項的變化和內存的當前狀態。實驗要求：1. 詳細描述實驗設計思想、程序結構及各模塊設計思路；2. 詳細描述程序所用數據結構及算法；3. 明確給出測試用例和實驗結果；4. 為增加程序可讀性，在程序中進行適當注釋說明；5. 認真進行實驗總結，包括：設計中遇到的問題、解決方法與收獲等；6. 實驗報告撰寫要求結構清晰、描述準確邏輯性強；7.

3、 實驗過程中，同學之間可以進行討論互相提高，但絕對禁止抄襲。【實驗過程記錄（源程序、測試用例、測試結果及心得體會等） 】 源程序:MemoryBlock.java:/ 內存塊類，包含各種操作public class MemoryBlock staticfinal int BLOCK_SIZE= 4096;privateint baseBlock ;/ 內存塊基地址privateint blockNum ;/ 大小privateboolean inUse ;/ 是否已分配privateMemoryBlock prev ,next ;publicMemoryBlock( int blockNum)

4、 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 b

5、lockNum) 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 =

6、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) intnewBase =baseBlock + blockNum;intnewBlock

7、=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( blo

8、ckNum +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 + ", 大小 =" + bl

9、ockNum + ", " + 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(

10、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(MemoryBlo

11、ck 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.getNex

12、t();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(

13、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

14、(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:extends MemoryTab

15、le int blockNum) public class FirstFit public FirstFit(super (blockNum);Overrideint blockNum) memList ;public boolean allocate(MemoryBlock memBlock = while (memBlock!= null ) if (!memBlock.inUse() if (memBlock.getBlockNum()>blockNum) MemoryBlock newBlock = memBlock.allocate(blockNum); insert(memB

16、lock, 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.getPre

17、v()!= 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() &&

18、amp; (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

19、 ) 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 ;Overrideint blockNum) me

20、mList ; null ;public boolean allocate(MemoryBlock memBlock =MemoryBlock minBlock = for (;memBlock!= null ; memBlock = memBlock.getNext() if (!memBlock.inUse()&&(memBlock.getBlockNum()>=blockNum) minBlock = memBlock; break ;if (minBlock != null ) remove(minBlock);if (minBlock.getBlockNum()

21、!=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 ;Ov

22、erridepublic 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 (m

23、emBlock = 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

24、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 newBlo

25、ck) 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

26、 !=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 al

27、locate( int blockNum) MemoryBlock maxBlock = memList ;if (maxBlock.getBlockNum()<blockNum)return false ;remove(maxBlock);if (maxBlock.getBlockNum()!=blockNum) MemoryBlock newBlock = maxBlock.allocate(blockNum); insertUnused(newBlock);insertUsed(maxBlock);return true ;boolean freeMemory(MemoryBloc

28、k 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)

29、; 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.getPr

30、ev().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 ;pre

31、Block = memBlock;memBlock = memBlock.getNext();insert(preBlock, newBlock);void insertUsed(MemoryBlock newBlock) if ( usedMemory = null ) usedMemory = newBlock;else MemoryBlock memBlock =usedMemorywhile (memBlock.getNext() != null ) memBlock = memBlock.getNext(); memBlock.setNext(newBlock); newBlock.

32、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) testFir

33、stFit ();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( &qu