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

2、是否有足夠的空閑空間，若有，則按需求量分割一部分給作業(yè)；若無，則作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分割成許多大大小小的分區(qū)。有的分區(qū)被作業(yè)占用，有的分區(qū)空閑。例如，某時(shí)刻主存空間占用情況如圖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）起始地址長(zhǎng)度狀態(tài)45K20KB未分配110K146KB未分配空表目空表目空表目圖1 主存空間占用情況為了說明哪些分區(qū)是空閑的，可以用來裝入新的作業(yè)，必須要有一張空閑區(qū)說明表，如表1所示。其中，起始地址指出各空閑

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

4、速查找，要不斷地對(duì)表格進(jìn)行緊縮，即讓“空表目”項(xiàng)留在表的后部。其分配框圖如圖2所示。（3）當(dāng)一個(gè)作業(yè)執(zhí)行完時(shí)，作業(yè)所占用的分區(qū)應(yīng)歸還給系統(tǒng)。在歸還時(shí)要考慮相鄰空閑區(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）請(qǐng)按首次（或最佳）適應(yīng)算法設(shè)計(jì)主存分配和回收程序。以圖1作為主存當(dāng)前使用的基礎(chǔ)，初始化空閑區(qū)和已分配區(qū)說明表的值。

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

6、ner(System.in); static ArrayList blockList = new ArrayList(); static int application; static int adr; static int size; public static void main(String args) initalize(); public static void initalize() / 將整個(gè)存儲(chǔ)區(qū)作為freeBlock初始化并顯示信息 FreeBlock freeBlock = new FreeBlock(0, 32767); blockList.add(freeBlock);

7、 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 = getRequest(); if (type = 1) assign(1, application); else if (type = 2) acc

8、ept(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); firstClass(); public static void printAll() print(adrtendtsizen); print(-n); for (FreeBlock bloc

9、k : blockList) block.printME(); public static int getRequest() print(Assign or Accept (1-Assign,2-Accept):); int type = scanner.nextInt(); if (type = 1) print(input Application:); application = scanner.nextInt(); else if (type = 2) print(input adr and size:); adr = scanner.nextInt(); size = scanner.

10、nextInt(); else print(Error!n); return type; public static boolean assign(int p_way, int p_application) / 判斷是否有空閑區(qū) if (blockList.isEmpty() print(沒有任何空閑區(qū)域可供分配！n); return false; / 按各自的原則查找空閑區(qū) if (p_way = 1) / best int minSize = 32767; int minIndex = -1; for (FreeBlock block : blockList) if (block.getS

11、ize() = p_application) minSize = block.getSize(); minIndex = 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; FreeBloc

12、k tempBlock2 = new FreeBlock(tempBlock1.getAdr(), tempBlock1.getSize() - 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() = p_application) minAdr = blo

13、ck.getSize(); minIndex = 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(tempBlo

14、ck1.getAdr(), 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 32766) print(錯(cuò)誤：回收空間大于最大空間(32766)！n); return false; / 檢查：回收空間和空閑空間重疊 for (FreeBlock block : blockList) if (p_adr = block.getAdr() & p_adr = block.getAdr() & p_end 0) return adr + size - 1; else return 0; public int getAdr() return adr; public void setAdr(int adr) this.adr =