主存空間地分配與回收

1、精選優(yōu)質(zhì)文檔-傾情為你奉上操作系統(tǒng)實驗報告實驗三：主存空間的分配與回收一、 實驗題目采用可變式分區(qū)管理，使用首次或最佳適應(yīng)算法實現(xiàn)主存的分配與回收二、 實驗內(nèi)容主存是中央處理機能直接存取指令和數(shù)據(jù)的存儲器。能否合理而有效地使用主存，在很大程度上將影響到整個計算機系統(tǒng)的性能。本實驗采用可變式分區(qū)管理，使用首次或最佳適應(yīng)算法實現(xiàn)主存空間的分配與回收。要求采用分區(qū)說明表進行。三、 實驗?zāi)康耐ㄟ^本次實驗，幫助學(xué)生理解在可變式分區(qū)管理方式下，如何實現(xiàn)主存空間的分配與回收。提示：（1） 可變式分區(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的需要，并且分區(qū)個數(shù)是可以調(diào)整的。當(dāng)要裝入一個作業(yè)時，

2、根據(jù)作業(yè)需要的主存量，查看是否有足夠的空閑空間，若有，則按需求量分割一部分給作業(yè)；若無，則作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分割成許多大大小小的分區(qū)。有的分區(qū)被作業(yè)占用，有的分區(qū)空閑。例如，某時刻主存空間占用情況如圖1所示。 0表1 空閑區(qū)說明表操作系統(tǒng)（10KB）10K作業(yè)1（10KB） 20K作業(yè)4（25KB） 45K空閑區(qū)1（20KB） 65K作業(yè)2（45KB）110K256K空閑區(qū)2（146KB）起始地址長度狀態(tài)45K20KB未分配110K146KB未分配空表目空表目空表目圖1 主存空間占用情況為了說明哪些分區(qū)是空閑的，可以用來裝入新的作業(yè)，必須要有一張空閑區(qū)說明表，如表1所示

3、。其中，起始地址指出各空閑區(qū)的主存起始地址，長度指出空閑區(qū)大小。狀態(tài)欄未分配指該欄目是記錄的有效空閑區(qū)，空表目指沒有登記信息。由于分區(qū)個數(shù)不定，所以空閑區(qū)說明表中應(yīng)有足夠的空表目項，否則造成溢出，無法登記。同樣，再設(shè)一個已分配區(qū)表，記錄作業(yè)或進城的主存占用情況。（2） 當(dāng)有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需求量，這時應(yīng)該將空閑區(qū)一分為二。一個分給作業(yè)，另一個仍作為空閑區(qū)留在空閑區(qū)表中。為了盡量減少由于分割造成的碎片，盡可能分配低地址部分的空閑區(qū)，將較大空閑區(qū)留在高地址端，以利于大作業(yè)的裝入。為此在空閑區(qū)表中，按空閑區(qū)首地址從

4、低到高進行登記。為了便于快速查找，要不斷地對表格進行緊縮，即讓“空表目”項留在表的后部。其分配框圖如圖2所示。（3）當(dāng)一個作業(yè)執(zhí)行完時，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。在歸還時要考慮相鄰空閑區(qū)合并的問題。作業(yè)的釋放區(qū)與空閑區(qū)的鄰接分一下4種情況考慮：A釋放區(qū)下鄰（低地址鄰接）空閑區(qū)；B釋放區(qū)上鄰（高地址鄰接）空閑區(qū)；C釋放區(qū)上下都與空閑區(qū)鄰接；D釋放區(qū)與空閑區(qū)不鄰接。首次適應(yīng)算法回收框圖如圖3所示。若采用最佳適應(yīng)算法，則空閑區(qū)說明表中的空閑區(qū)按其大小排序。有關(guān)最佳適應(yīng)算法的分配和回收框圖由學(xué)生自己給出。（4）請按首次（或最佳）適應(yīng)算法設(shè)計主存分配和回收程序。以圖1作為主存當(dāng)前使用的基礎(chǔ)，初始化空

5、閑區(qū)和已分配區(qū)說明表的值。學(xué)生自己設(shè)計一個作業(yè)申請隊列以及作業(yè)完成后的釋放順序，實現(xiàn)主存的分配與回收。把空閑區(qū)說明表的變化情況以及各作業(yè)的申請、釋放情況顯示或打印出來。為了說明哪些分區(qū)是空閑的，必須要有一張空閑區(qū)說明表，格式如下表所示：起始地址長度狀態(tài)20K20K180K50K1150K100K1300K30K0（空表目）600K100K1空表目四、代碼及運行結(jié)果分析Main.javapackage Exp4; import java.util.ArrayList; import java.util.Scanner; public class Main static Scanner scann

6、er = new Scanner(System.in); static ArrayList<FreeBlock> blockList = new ArrayList<FreeBlock>(); static int application; static int adr; static int size; public static void main(String args) initalize(); public static void initalize() / 將整個存儲區(qū)作為freeBlock初始化并顯示信息 FreeBlock freeBlock = new

7、 FreeBlock(0, 32767); blockList.add(freeBlock); printAll(); print("Please input the way (1-best,2-first):"); int way = scanner.nextInt(); if (way = 1) bestClass(); /最佳適應(yīng)算法 else if (way = 2) firstClass(); /首次適應(yīng)算法 else print("Error!n"); public static void bestClass() int type = get

8、Request(); if (type = 1) assign(1, application); else if (type = 2) accept(adr, size); else print("Error!n"); bestClass(); public static void firstClass() int type = getRequest(); if (type = 1) assign(2, application); else if (type = 2) accept(adr, size); else print("Error!n"); f

9、irstClass(); public static void printAll() print("adrtendtsizen"); print("-n"); for (FreeBlock block : blockList) block.printME(); public static int getRequest() print("Assign or Accept (1-Assign,2-Accept):"); int type = scanner.nextInt(); if (type = 1) print("inpu

10、t Application:"); application = scanner.nextInt(); else if (type = 2) print("input adr and size:"); adr = scanner.nextInt(); size = scanner.nextInt(); else print("Error!n"); return type; public static boolean assign(int p_way, int p_application) / 判斷是否有空閑區(qū) if (blockList.isEm

11、pty() print("沒有任何空閑區(qū)域可供分配！n"); return false; / 按各自的原則查找空閑區(qū) if (p_way = 1) / best int minSize = 32767; int minIndex = -1; for (FreeBlock block : blockList) if (block.getSize() <= minSize && block.getSize() >= p_application) minSize = block.getSize(); minIndex = blockList.index

12、Of(block); if (minIndex = -1) print("沒有符合要求的空閑區(qū)域！n"); return false; else FreeBlock tempBlock1 = blockList.get(minIndex); if (tempBlock1.getSize() = p_application) blockList.remove(tempBlock1); printAll(); return true; FreeBlock tempBlock2 = new FreeBlock(tempBlock1.getAdr(), tempBlock1.get

13、Size() - p_application); blockList.set(minIndex, tempBlock2); printAll(); return true; else if (p_way = 2) / first int minAdr = 32766; int minIndex = -1; for (FreeBlock block : blockList) if (block.getAdr() <= minAdr && block.getSize() >= p_application) minAdr = block.getSize(); minInd

14、ex = blockList.indexOf(block); if (minIndex = -1) print("沒有符合要求的空閑區(qū)域！n"); return false; else FreeBlock tempBlock1 = blockList.get(minIndex); if (tempBlock1.getSize() = p_application) blockList.remove(tempBlock1); printAll(); return true; FreeBlock tempBlock2 = new FreeBlock(tempBlock1.getA

15、dr(), tempBlock1.getSize() - p_application); blockList.set(minIndex, tempBlock2); printAll(); return true; else print("Error!n"); return false; public static boolean accept(int p_adr, int p_size) int p_end = adr + size - 1; / 檢查：首地址小于最小地址（0） if (p_adr < 0) print("錯誤：首地址小于最小地址（0）！n&

16、quot;); return false; / 檢查：回收空間大于最大空間(32766) if (p_end > 32766) print("錯誤：回收空間大于最大空間(32766)！n"); return false; / 檢查：回收空間和空閑空間重疊 for (FreeBlock block : blockList) if (p_adr >= block.getAdr() && p_adr <= block.getEnd() print("錯誤：回收空間和空閑空間重疊！n"); return false; if (p

17、_end >= block.getAdr() && p_end <= block.getEnd() print("錯誤：回收空間和空閑空間重疊！n"); return false; / 檢查：前有接續(xù) for (FreeBlock block : blockList) if (p_adr - 1 = block.getEnd() block.setSize(block.getSize() + p_size); / 在前有接續(xù)的基礎(chǔ)上，檢查：后有接續(xù) for (FreeBlock block2 : blockList) if (block.getE

18、nd() + 1 = block2.getAdr() block.setSize(block.getSize() + block2.getSize(); blockList.remove(block2); printAll(); return true; printAll(); return true; / 檢查：后有接續(xù)（前肯定沒有接續(xù)） for (FreeBlock block : blockList) if (p_end + 1 = block.getAdr() block.setAdr(p_adr); block.setSize(block.getSize() + p_size); printAll(); return true; / 前后均無接續(xù) FreeBlock freeBlock = new FreeBlock(p_adr, p_size); blockList.add(freeBlock); printAll(); return true; public static void print(String printString) System.out.print(printString); FreeBlock.javapackage Exp4; public class FreeBlock private int adr;