主存空間的分配與回收實驗報告講解

1、實驗報告課程名稱：操作系統(tǒng)實驗名稱：主存空間的分配與回收學(xué) 號：110310014學(xué)生姓名：于釗班 級：信管1101班指導(dǎo)教師：吳聯(lián)世實驗日期： 2013年12月5日1、實驗?zāi)康模菏煜ぶ鞔娴姆峙渑c回收。理解在不同的存儲管理方式下，如何實現(xiàn)主存空間 的分配與回收。掌握動態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法及動態(tài)分區(qū)存儲 管理方式及其實現(xiàn)過程。2、實驗要求實驗要求使用可變分區(qū)存儲管理方式，分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)采用空閑分區(qū)表和空閑分區(qū)鏈來進行，分區(qū)分配中所用的算法采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng) 算法三種算法來實現(xiàn)主存的分配與回收。同時，要求設(shè)計一個實用友好的用戶界面，并顯示 分配與

2、回收的過程。 03、實驗環(huán)境硬件：CPU : AMD QL64內(nèi)存：2GB顯卡：ATI 4570硬盤：日立250G軟件：Windows 2000/XP。 開發(fā)工具：VC+6.0。4、實驗內(nèi)容1）實現(xiàn)原理主存的分配和回收的實現(xiàn)是與主存儲器的管理方式有關(guān)的。所謂分配，就是 解決多道作業(yè)或多進程如何共享主存空間的問題。所謂回收，就是當作業(yè)運行完 成時將作業(yè)或進程所占的主存空間歸還給系統(tǒng)?？勺兎謪^(qū)管理是指在處理作業(yè)過程中建立分區(qū)，使分區(qū)大小正好適合作業(yè)的 需求，并且分區(qū)個數(shù)是可以調(diào)整的。當要裝入一個作業(yè)時，根據(jù)作業(yè)需要的主存 量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)； 若無

3、，則作業(yè)不能裝入，作業(yè)等待。隨著作業(yè)的裝入、完成，主存空間被分成許 多大大小小的分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。操作系統(tǒng)（10KB作業(yè) 1 （10KB作業(yè) 4 （25KB 空閑區(qū)1 （20KB 作業(yè) 2 （45KB空閑區(qū)2 (146KB為了說明那些分區(qū)是空閑的，可以用來裝入新作業(yè)，必須有一張空閑說明表 例如：010k20k45k65k110k256k空閑區(qū)說明表格式如下：起始地址長度狀態(tài)第一欄45 K20KB未分配第二欄110 K146 KB未分配1空表目1空表目33其中，起址一一指出一個空閑區(qū)的主存起始地址，長度指出空閑區(qū)的大小 長度一一指出從起始地址開始的一個連續(xù)空閑的長度。

4、狀態(tài)一一有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對應(yīng)的由起址指出的 某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應(yīng)的登記項目 是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)完成后，它所占的區(qū)域就 成了空閑區(qū)，應(yīng)找一個“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。由于分區(qū)的個數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄 目，否則造成表格“溢出”無法登記。2、當有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個 足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需要量，這時應(yīng)把原來的空閑 區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個較小的空閑區(qū)，留在 空

5、閑區(qū)表中。為了盡量減少由于分割造成的空閑區(qū)，盡可能分配低地址部分的空 閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。 為此，在空閑區(qū)說明表中，把每個空閑區(qū)按其地址順序從低到高登記，即每個后 繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮” ，總是 讓“空表目”項留在表格的后部。3、采用最先適應(yīng)算法（順序分配算法）分配主存空間。按照作業(yè)的需要量，查空閑區(qū)說明表，順序查看登記欄，找到第一個能滿足 要求的空閑區(qū)。當空閑區(qū)大于需要量時，一部分用來裝入作業(yè)，另一部分仍為空 閑區(qū)登記在空閑區(qū)說明表中。由于本實驗是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實際啟動裝

6、 入程序裝入作業(yè)，而用輸出“分配情況”來代替。4、當一個作業(yè)執(zhí)行完成撤離時，作業(yè)所占的分區(qū)應(yīng)該歸還給系統(tǒng)，歸還的分 區(qū)如果與其它空閑區(qū)相鄰，則應(yīng)合成一個較大的空閑區(qū)，登記在空閑區(qū)說明表中。 例如，在上述中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時，應(yīng)與上、 下相鄰的空閑區(qū)一起合成一個大的空閑區(qū)登記在空閑區(qū)說明表中。2）程序結(jié)構(gòu)（流程圖）輸出分配至泣首次適應(yīng)分配模擬算法申蕭社生存區(qū)查嚏度嗎；a口狀態(tài)為三襄目長發(fā)工工京量;a起址起址+妹戰(zhàn)1 空襲號E程卷記始址CS 限度L狀態(tài)g “未分配叫無無有下鑼的空L，=歸還區(qū)氏度S t4白誣區(qū)祗此與歸M有5藏言題序曲瞬f；jr縮岑后區(qū)稅明表有Lr =

7、L+下綁空用區(qū)長度區(qū)此下都空闈區(qū)登記摟：中始址；=. 長度=L無有與明-區(qū)上部的空困把下韓空闈區(qū)登 記欄中狀想置成 “空表目r上等空鬧區(qū)登記 粒中長度增加L主存回收算法3）實現(xiàn)步驟實現(xiàn)動態(tài)分區(qū)的分配與回收，主要考慮三個問題：第一，設(shè)計記錄主存使用情 況的數(shù)據(jù)表格，用來記錄空閑區(qū)和作業(yè)占用的區(qū)域；第二，在設(shè)計的數(shù)據(jù)表格基 礎(chǔ)上設(shè)計主存分配算法；第三，在設(shè)計的數(shù)據(jù)表格基礎(chǔ)上設(shè)計主存回收算法。1 .設(shè)計記錄主存使用情況的數(shù)據(jù)表格由于動態(tài)分區(qū)的大小是由作業(yè)需求量決定的，故分區(qū)的長度是預(yù)先不固定的， 且分區(qū)的個數(shù)也隨主存分配和回收變動。總之，所有分區(qū)情況隨時可能發(fā)生變化， 數(shù)據(jù)表 格的設(shè)計必須和這個特點

8、相適應(yīng)。由于分區(qū)長度不同，因此設(shè)計的表格 應(yīng)該包括分區(qū)在主存中的起始地址和長度。由于分配時，空閑區(qū)有時會變成兩個 分區(qū)：空閑區(qū) 和已分分區(qū)，回收主存分區(qū)時，可能會合并空閑區(qū)，這樣如果整 個主存采用一張表格記錄已分分區(qū)和空閑區(qū)，就會使表格操作繁瑣。主存分配時 查找空閑區(qū)進行分 配，然后填寫已分配區(qū)表，主要操作在空閑區(qū)；某個作業(yè)執(zhí) 行完后，將該分區(qū)貶詞空閑區(qū)，并將其與相鄰的空閑區(qū)合并，主要操作也在空閑 區(qū)。由此可見，主存的分 配與回收主要時對空閑區(qū)的操作。這樣為了便于對主 存空間的分配與回收，就建立兩張分區(qū)表記錄主存的使用情況：”已分配區(qū)表”記錄作業(yè)占用分區(qū)，“空閑區(qū)表”記錄空閑區(qū)。這兩張表的實現(xiàn)

9、方法一般由兩種：鏈表形式、順序表形式。在本實驗中，采 用順序表形式，用數(shù)組模擬。由于順序表的長度必須提前固 定，所以無論是“已 分配區(qū)表”還是“空閑區(qū)表”都必須事先確定長度。它們的長度必須是系統(tǒng)可能 的最大項數(shù)，系統(tǒng)運行過程中才不會出錯，因此在多數(shù)情況下，無論是“已分配表區(qū)”還是“空閑區(qū)表”都是空閑欄目。已分配區(qū)表中除了分區(qū)起始地址、長 度外，也至少還有一項“標志”，如果是空閑欄目，內(nèi)容為“空”，如果為某個作業(yè)占用分區(qū)的登記項，內(nèi)容為該作業(yè)的作業(yè)名；空閑區(qū)表除了分區(qū)起始地址、長度外，也要有一項“標志”，如果是空閑欄目，內(nèi)容為“空”，如果為某 個空 閑區(qū)的登記項，內(nèi)容為“未分配”。在實際系統(tǒng)中，

10、這兩個表格的內(nèi)容可能還要為此，“已分配區(qū)表”和“空閑區(qū)表”在 實已分配區(qū)表的定義：#define n 10/struct float address; / float length; / int flag; /used_tablen; /空閑區(qū)表的定義：#define m 10/struct float address; / float length; / int flag; /free_tablem; /多，實驗中僅僅使用上述必須的數(shù)據(jù) 驗中有如下的結(jié)構(gòu)定義。假定系統(tǒng)允許的最大作業(yè)數(shù)量為 n已分分區(qū)起始地址已分分區(qū)長度，單位為字節(jié)已分配表區(qū)登記欄標志，用0表示空欄目，已分配區(qū)表假定系統(tǒng)允許的

11、空閑區(qū)表最大為 m空閑區(qū)起始地址空閑區(qū)長度，單位為字節(jié)空閑區(qū)表登記欄目用0表示空欄目，1表示未分配？ 空閑區(qū)表其中分區(qū)起始地址和長度數(shù)值太大，超出了整形表達范圍，所有采用float類型2 .在設(shè)計的表格上進行主存分配當 要裝入一個作業(yè)時，從空閑區(qū)表中查找標志為“未分配”的空閑區(qū)，從中找一個能容納該作業(yè)的空閑區(qū)。如果找到的空閑區(qū)正好等于該作業(yè)的長度，則把該分區(qū)全部分配給該作業(yè)。這時應(yīng)該把該空閑區(qū)登記欄中的標志改為“空”，同時 在已分配區(qū)表中找到一個標志為“空”的欄目登記新裝入作業(yè)所占用分區(qū)的起始 地址、長度和 作業(yè)名。如果找到的空閑區(qū)大于作業(yè)長度，則把空閑區(qū)分成兩部 分，一部分用來裝入作業(yè)，另一

12、部分你仍然為空閑區(qū)，這時只要修改空閑區(qū)的長 度，且把新裝入的作 業(yè)登記到已分配區(qū)表中。主存分配算法目前一般采用三種算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳 適應(yīng)算法。本實驗中采用最佳適應(yīng)算法為作業(yè)分配主存。最佳適應(yīng)算法會出現(xiàn)空閑分區(qū)分割后剩下的空閑分區(qū)很小以至于無法使用的情況，為了在一定程度上解決這個問題，如果空閑分區(qū)的大小比作業(yè)要求的長度略大一點， 不再將空閑區(qū)分區(qū)分割成已分分區(qū)和空閑分區(qū)兩部分， 而是將整個空閑區(qū)分配給 作業(yè)。在實現(xiàn)最佳適應(yīng)算法時，可把空閑分區(qū)按長度遞增方式登記在空閑區(qū)表中。 分配時順序查找空閑表，查找到的第一個空閑區(qū)就是滿足作業(yè)要求的最小分區(qū)。 這樣查找速度快，但是為使

13、空閑區(qū)按照長度遞增登記在空閑表中，就必須在分 配回收時進行空閑區(qū)的調(diào)整?？臻e區(qū)表調(diào)整時移動標模的代價要高于查詢整張表 的代價，所以實 驗中不采用空閑區(qū)有序登記在空閑表中的方法。3 .動態(tài)分區(qū)方式下的主存回收動態(tài)分區(qū)方式下回收主存空間時應(yīng)該檢查是否有與歸還區(qū)相鄰的空閑區(qū)域。 若有，則應(yīng)該合并成一個空閑區(qū)。一個歸還區(qū)可能有上鄰空閑區(qū)，也可能有下鄰 空閑區(qū)，或者既有上鄰空閑區(qū)又有下鄰空閑區(qū)，或者既無上鄰空閑區(qū)也無下鄰空閑區(qū)。在實現(xiàn)回收時，首先將作業(yè)歸還的區(qū)域在已分配表中找到，將該欄目的狀態(tài) 變?yōu)椤翱铡?，然后檢查空閑區(qū)表中標志為“未分配”欄目，查找是否又相鄰空閑 區(qū)；最后合并空閑區(qū)，修改空閑區(qū)表。假定

14、歸還作業(yè)的分區(qū)起始地址為S,長度為L,貝1）歸還區(qū)又下鄰空閑區(qū)如果S+ L正好等于空閑區(qū)表中某個登記欄目（假定為第 j欄）的起始地址則表 明歸還區(qū)有一個下鄰空閑區(qū)。這時候只需要修改第 j欄登記項的內(nèi)容：起始地址=S;第j欄長度=第j欄長度+ L則第j欄指示的空閑區(qū)時歸還區(qū)和下鄰空閑區(qū)合并后的大空閑區(qū)。2）歸還區(qū)又上鄰空閑區(qū)如果空閑區(qū)表中某個登記欄目（假定為第 k欄）的“起始地址+長度”正好等于 S,則表明歸還區(qū)有一個上鄰空閑區(qū)。這時要修改第 k欄登記項的內(nèi)容（起始地 址不變）：第k欄長度=第k欄長度+ L；于是第k欄指示的空閑區(qū)是歸還區(qū)和上鄰空閑區(qū)合并后的大空閑區(qū)。3）歸還區(qū)既有上鄰空閑區(qū)又有

15、下鄰空閑區(qū)如果S+ L正好等于空閑區(qū)表中某個登記欄目（假定為第 j欄）的起始地址，同 時還有某個登記欄目（假定為第 k欄）的“起始地址+長度”正好等于 S,這表 明歸還區(qū)既有一個上鄰空閑區(qū)又又一個下鄰空閑區(qū)。此時對空閑區(qū)的修改如下：第k欄的長度=第k欄的長度+第j欄的長度+ L；（第k欄的起始地址不 變）第j欄的狀態(tài)=空”（將第j欄的登記項刪除）這樣，第k欄指示的空閑區(qū)是歸還區(qū)和上、下鄰空閑區(qū)合并后的大空閑區(qū)； 原來的下鄰空閑區(qū)登記項（第j欄）被刪除，置為“空”。4）歸還區(qū)既無上鄰空閑區(qū)又無下鄰空閑區(qū)如果在檢查空閑區(qū)表時，無上述三種情況出現(xiàn)，則表明歸還區(qū)既無上鄰空閑區(qū)又 無下鄰空閑區(qū)。這時，應(yīng)

16、該在空閑區(qū)表中查找一個狀態(tài)為“空”的欄目（假定查 到的是第t欄），則第t欄的內(nèi)容修改如下：第t欄起始地址=S;第t欄的長度=L;第t欄的狀態(tài)=未分配”；這樣，第t欄指示的空閑區(qū)是歸還區(qū)。由于是實驗，沒有真正的主存要分配，所有在實驗中，首先應(yīng)建立一張空 閑區(qū)表，初始狀態(tài)只有一個空閑登記項（假定的主存空閑區(qū)）和一張所有狀態(tài)都 為“空”的已分配區(qū)表，假定主存空間100KB全部為空閑區(qū)（實際上操作系統(tǒng) 需要占用一部分）；然后，可以選擇進行主存分配或回收，如果是分配，要求輸 入作業(yè)名和 所需主存空間大?。蝗绻腔厥?，輸入回收作業(yè)名；循環(huán)進行主存 分配和回收后，如果需要，則顯示兩張表的內(nèi)容，以檢查主存的分

17、配和回收是否 正確。4）實驗測試及分析:- XK*- 存c - 勺 - 一熊贏 拓機 f作到業(yè)用分片 化解空己碎 始業(yè)成一盟明茬 F初作完當當拼退 E 12 3 4 5 6 7Joi*1 存7炯fe.* B./I“內(nèi)方的銀- 作可業(yè)闈制二 - 二 二 二 二- 二 二 二 二-一可翠宣n*壞， 一地成一 一 f?，撗┊旔?選擇可以自由選擇速入分區(qū)的作業(yè)樂 選國，職自接傳，仆仆:6、實驗心得體會這次實驗比較復(fù)雜，用了很多時間，但同時收獲了很多，對主存空間分配認識加深了很 多附錄：源代碼#include#include#define OK 1/完成#define ERROR 0 / 出錯type

18、def int Status;typedef struct free_table/定義一個空閑區(qū)說明表結(jié)構(gòu) int num; 分區(qū)序號long address; 起始地址long length; / 分區(qū)大小int state; 分區(qū)狀態(tài)ElemType;typedef struct Node/線性表的雙向鏈表存儲結(jié)構(gòu)ElemType data;struct Node *prior; / 前趨指針struct Node *next; 后繼指針Node,*LinkList;LinkList first; / 頭結(jié)點LinkList end;/尾結(jié)點int flag;/ 記錄要刪除的分區(qū)序號Sta

19、tus Initblock()/ 開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表first=(LinkList)malloc(sizeof(Node); end=(LinkList)malloc(sizeof(Node); first-prior=NULL;first-next=end;end-prior=first;end-next=NULL;end-data.num=1;end-data.address=40;end-data.length=600;end-data.state=0;return OK;void sort()/ 分區(qū)序號重新排序 Node *p=first-next,*q; q=p-next;

20、for(;p!=NULL;p=p-next) for(q=p-next;q;q=q-next) if(p-data.num=q-data.num) q-data.num+=1;/顯示主存分配情況void show() int flag=0;/ 用來記錄分區(qū)序號Node *p=first;p-data.num=0;p-data.address=0;p-data.length=40;p-data.state=1;sort();printf(ntt 主存空間分配情況 n);printf(*nn);printf(分區(qū)序號t起始地址t分區(qū)大小t分區(qū)狀態(tài)nn);while(p)printf(%dtt%dt

21、t%d,p-data.num,p-data.address,p-data.length);if(p-data.state=0) printf(tt 空閑 nn);else printf(tt 已分配 nn);p=p-next;printf(*nn);/首次適應(yīng)算法Status First_fit(int request)/為申請作業(yè)開辟新空間且初始化Node *p=first-next;LinkList temp=(LinkList)malloc(sizeof(Node);temp-data.length=request;temp-data.state=1;p-data.num=1;while

22、(p)if(p-data.state=0)&(p-data.length=request)/ 有大小恰好合適的空閑塊p-data.state=1;return OK;break;else if(p-data.state=0) & (p-data.lengthrequest)/ 有空閑塊能滿足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;temp-data.num=p-data.num;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.add

23、ress+temp-data.length;p-data.length-=request;p-data.num+=1;return OK;break;p=p-next;return ERROR;/最佳適應(yīng)算法Status Best_fit(int request)int ch; /記錄最小剩余空間Node *p=first;Node *q=NULL; / 記錄最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node);temp-data.length=request;temp-data.state=1;p-data.num=1;while(p) / 初始

24、化最小空間和最佳位置if(p-data.state=0) & (p-data.length=request) )if(q=NULL)q=p;ch=p-data.length-request;else if(q-data.length p-data.length)q=p;ch=p-data.length-request;p=p-next;if(q=NULL) return ERROR;/ 沒有找到空閑塊else if(q-data.length=request)q-data.state=1;return OK;elsetemp-prior=q-prior;temp-next=q;temp-dat

25、a.address=q-data.address;temp-data.num=q-data.num;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.length=ch;q-data.num+=1;return OK; return OK;/最差適應(yīng)算法Status Worst_fit(int request) int ch; /記錄最大剩余空間Node *p=first-next;Node *q=NULL; / 記錄最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node);te

26、mp-data.length=request;temp-data.state=1;p-data.num=1;while(p) / 初始化最大空間和最佳位置if(p-data.state=0 & (p-data.length=request) ) if(q=NULL)q=p;ch=p-data.length-request;else if(q-data.length data.length)q=p;ch=p-data.length-request;p=p-next;if(q=NULL) return ERROR;/ 沒有找到空閑塊else if(q-data.length=request)q-d

27、ata.length=1;return OK;elsetemp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;temp-data.num=q-data.num;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.length=ch;q-data.num+=1;return OK;return OK;/分配主存Status allocation(int a)int request;/ 申請內(nèi)存大小printf( 請輸入申請分配的主存大小(單位 :KB):

28、);scanf(%d,&request);if(requestnext) (if(q=p) (if(q-prior-data.state=0&q-next-data.state!=0) q-prior-data.length+=q-data.length;q-prior-next=q-next;q-next-prior=q-prior;q=q-prior;q-data.state=0;q-data.num=flag-1;)if(q-prior-data.state!=0&q-next-data.state=0) (q-data.length+=q-next-data.length;q-next

29、=q-next-next;q-next-next-prior=q;q-data.state=0;q-data.num=flag;)if(q-prior-data.state=0&q-next-data.state=0)q-prior-data.length+=q-data.length;q-prior-next=q-next;q-next-prior=q-prior;q=q-prior;q-data.state=0;q-data.num=flag-1;)if(q-prior-data.state!=0&q-next-data.state!=0)(q-data.state=0;)return O

30、K;Status deal2(Node *p)/ 處理回收空間 (Node *q=first;for(;q!=NULL;q=q-next)(if(q=p)(if(q-prior-data.state=0&q-next-data.state!=0) (q-prior-data.length+=q-data.length;q-prior-next=q-next;q-next-prior=q-prior;q=p-prior;q-data.state=0;q-data.num=flag-1;)if(q-prior-data.state!=0&q-next-data.state=0)(q-data.st

31、ate=0;)if(q-prior-data.state=0&q-next-data.state=0)(q-prior-data.length+=q-data.length;q-prior-next=q-next;q-next-prior=q-prior;q=q-prior;q-data.state=0;q-data.num=flag-1;)if(q-prior-data.state!=0&q-next-data.state!=0)(q-data.state=0;) return OK;)/主存回收Status recovery(int flag)(Node *p=first;for(;p!=NULL;p=p-next)if(p-data.num=flag)if(p-prior=first)if(p-next!=