模擬設(shè)計動態(tài)分區(qū)存儲管理的分配與回收

1、學 號： 課 程 設(shè) 計題 目模擬設(shè)計動態(tài)分區(qū)存儲管理的分配與回收學 院計算機科學與技術(shù)學院專 業(yè)班 級姓 名指導教師吳利軍2013年01月16日課程設(shè)計任務(wù)書學生姓名： 專業(yè)班級： 指導教師： 吳利軍 工作單位： 計算機科學與技術(shù)學院 題 目: 模擬設(shè)計動態(tài)分區(qū)存儲管理的分配與回收初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，理解動態(tài)分區(qū)存儲管理，掌握動態(tài)分區(qū)管理內(nèi)存的分配和回收過程。2實踐準備：掌握一種計算機高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1采用動態(tài)分區(qū)管理方案實施內(nèi)存分配和回收。能夠處理以下的情形 能夠輸入給定的內(nèi)

2、存大小，進程的個數(shù)，每個進程所需內(nèi)存空間的大??； 當某進程提出申請空間的大小后，顯示能否滿足申請，以及為該進程分配資源后有關(guān)內(nèi)存空間使用的情況； 當某進程撤消時，顯示內(nèi)存回收后內(nèi)存空間的使用情況（注意回收后的合并）。2設(shè)計報告內(nèi)容應(yīng)說明： 需求分析； 功能設(shè)計（數(shù)據(jù)結(jié)構(gòu)及模塊說明）； 開發(fā)平臺及源程序的主要部分； 測試用例，運行結(jié)果與運行情況分析； 自我評價與總結(jié)：i）你認為你完成的設(shè)計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；時間安排：設(shè)計安

3、排一周：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收、撰寫課程設(shè)計報告。（注意事項：嚴禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導教師簽名： 年 月 日系主任（或責任教師）簽名： 年 月 日模擬設(shè)計動態(tài)分區(qū)存儲管理的分配與回收1.需求分析1.1動態(tài)分區(qū)動態(tài)分區(qū)分配又稱為可變式分區(qū)分配，是一種動態(tài)劃分存儲器的分區(qū)方法。不事先將內(nèi)存劃分成一塊塊的分區(qū)，而是在作業(yè)進入內(nèi)存時，根據(jù)作業(yè)的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。這種分配方法管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。進程的大小與某個

4、分區(qū)大小相等，從而主存的利用率有所提高。動態(tài)分區(qū)雖然解決了固定分區(qū)所造成的內(nèi)存浪費問題，但隨著進程的動態(tài)變化，系統(tǒng)也將進行一系列的內(nèi)存空間的分配和回收活動，每個進程所釋放的內(nèi)存空間就作為一個空閑區(qū)加以再分配。由于再分配時只能分給不大于當前空閑區(qū)的進程，所以每個空閑區(qū)再分配時多數(shù)情況下會變成兩個區(qū)：一個區(qū)分給當前請求內(nèi)存空間的進程，剩下的空間依然作為空閑區(qū)等待分配。這樣，分配后剩余的空閑區(qū)將會越分越少，從而導致內(nèi)存中存在大量分散的小空閑區(qū)，這種小得不能再利用的空閑區(qū)稱之為“碎片”。1.2分配內(nèi)存 系統(tǒng)利用某種分配算法，從空閑分區(qū)表/鏈中找到所需大小的分區(qū)。size(size是事先規(guī)定的不再切割的

5、剩余分區(qū)的大小)，說明多余部分大小，可不再切割，將整個分區(qū)分配給請求者；否則，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)表/鏈中，然后，將分配區(qū)的首址返回給調(diào)用者。 1.3回收內(nèi)存 當作業(yè)執(zhí)行結(jié)束時，應(yīng)回收已使用完畢的分區(qū)。系統(tǒng)根據(jù)回收分區(qū)的大小及首地址，在空閑分區(qū)表中檢查是否有鄰接的空閑分區(qū)，如有，則合成為一個大的空閑分區(qū)，然后修改有關(guān)的分區(qū)狀態(tài)信息。回收分區(qū)與已有空閑分區(qū)的相鄰情況有以下四種： 回收分區(qū)上鄰接一個空閑分區(qū),合并后首地址為空閑分區(qū)的首地址,大小為二者之和。 回收分區(qū)下鄰接一個空閑分區(qū),合并后首地址為回收分區(qū)的首地址,大小為二者之和。 回收分區(qū)上

6、下鄰接空閑分區(qū),合并后首地址為上空閑分區(qū)的首地址,大小為三者之和。 回收分區(qū)不鄰接空閑分區(qū)，這時在空閑分區(qū)表中新建一表項，并填寫分區(qū)大小等信息。2.功能設(shè)計2.1數(shù)據(jù)結(jié)構(gòu)2.1.1空閑分區(qū)表用來登記系統(tǒng)中的空閑分區(qū)(分區(qū)號,分區(qū)起始地址,分區(qū)大小及狀態(tài)). 分區(qū)號大小KB起始地址KB狀態(tài)132352空閑2空表目3520504空閑4空表目52.1.2 空閑分區(qū)鏈用鏈頭指針將系統(tǒng)中的空閑分區(qū)鏈接起來，構(gòu)成空閑分區(qū)鏈。每個空閑分區(qū)的起始部分存放相應(yīng)的控制信息(如大小,指向下一空閑分區(qū)的指針等).2.2 模塊說明2.12.1 分區(qū)說明表struct PST/partition specificatio

7、n table int id;/分區(qū)號int addr;/起始地址 int size;/分區(qū)長度 Status state;/狀態(tài);2.2.2 雙向鏈表struct Node/雙向鏈表結(jié)點 PST data; Node *back;/前驅(qū)Node *next;/后繼 Node() back=NULL; next=NULL; Node(int id,int size)data.ID=id;data.size=size;back=NULL;next=NULL;2.2.3 最先適應(yīng)算法空閑分區(qū)（鏈）按地址遞增的次序排列。在進行內(nèi)存分配時,從空閑分區(qū)表/鏈首開始順序查找,直到找到第一個滿足其大小要求的

8、空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。算法特點:優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區(qū)的開銷。Status FFA(int id,int size)/head fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;Node *cur=head-next;while(cur)

9、if(cur-data.state=FREE&cur-data.size=size)/如果空閑塊大小剛好與請求大小相等,直接分配 cur-data.ID=id;cur-data.state=BUSY;return OK;break;if(cur-data.state=FREE&cur-data.sizesize)/如果大于temp-back=cur-back;temp-next=cur;cur-back-next=temp;temp-data.addr=cur-data.addr;cur-back=temp;cur-data.addr=cur-data.addr+size;cur-data.s

10、ize=cur-data.size-size;return OK;break;cur=cur-next;return ERROR;2.2.4 最佳適應(yīng)算法空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區(qū)為止。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)表/鏈中。 算法特點：若存在與作業(yè)大小一致的空閑分區(qū),則它必然被選中，若不存在與作業(yè)大小一致的空閑分區(qū)，則只劃分比作業(yè)稍大的空閑分區(qū)，,從而保留

11、了大的空閑分區(qū),但空閑區(qū)一般不可能正好和它申請的內(nèi)存空間大小一樣,因而將其分割成兩部分時,往往使剩下的空閑區(qū)非常小,從而在存儲器中留下許多難以利用的小空閑區(qū)（碎片或零頭）。Status BFA(int id,int size)/best fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int min;/記錄符合滿足請求的最小空閑塊大小Node *fit;/指向采用最佳適應(yīng)算法的插入位置Node *cur=head-next;while(cur)/取得第一個可以分配的位置（不一定是最佳位置）if(cur-data.st

12、ate=FREE&cur-data.size=size)fit=cur;min=cur-data.size-size;break;cur=cur-next;while(cur)if(cur-data.state=FREE&cur-data.size=size)/如果相等直接分配 cur-data.state=BUSY;cur-data.ID=id;return OK;break;if(cur-data.state=FREE&cur-data.sizesize)/獲取最佳位置if(cur-data.size-sizedata.size-size;fit=cur;cur=cur-next;if(f

13、it)/若最佳，插入temp-back=fit-back;temp-next=fit;fit-back-next=temp;temp-data.addr=fit-data.addr;fit-back=temp;fit-data.addr=fit-data.addr+size;fit-data.size=fit-data.size-size;return OK;elsereturn ERROR;2.2.5 最壞適應(yīng)算法空閑分區(qū)表/鏈按容量大小遞減的次序排列。在進行內(nèi)存分配時，從空閑分區(qū)表的首開始順序查找，直到找到第一個比之大的空閑分區(qū)為止。剩下的空閑仍留在空閑分區(qū)表/鏈中。算法特點：總是挑選滿足

14、作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當有大作業(yè)到來時，其存儲空間的申請往往會得不到滿足。Status WFA(int id,int size)/worst fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int max;/記錄符合滿足請求的最小空閑塊大小Node *fit;/指向采用最壞適應(yīng)算法的插入位置Node *cur=head-next;while(cur)/取得第一個可以分配的位置（不一定是最佳位置）if(cur-da

15、ta.state=FREE&cur-data.size=size)fit=cur;max=cur-data.size-size;break;cur=cur-next;while(cur)/*if(cur-data.state=FREE&cur-data.size=size)/如果相等直接分配 cur-data.state=BUSY;cur-data.ID=id;return OK;break;*/if(cur-data.state=FREE&cur-data.sizesize)/獲取最佳位置if(cur-data.size-sizemax)max=cur-data.size-size;fit=

16、cur;cur=cur-next;if(fit)/若最佳，插入temp-back=fit-back;temp-next=fit;fit-back-next=temp;temp-data.addr=fit-data.addr;fit-back=temp;fit-data.addr=fit-data.addr+size;fit-data.size=fit-data.size-size;return OK;elsereturn ERROR;3.開發(fā)平臺及源程序的主要部分3.1開發(fā)平臺 本次課程設(shè)計開發(fā)平臺Microsoft Visual C+ 6.0 3.2 源程序的主要部分/#define MAX

17、_LEN 1024/定義內(nèi)存大小，1024字節(jié)enum StatusFREE,BUSY,OK,ERROR;struct PSTstruct Nodeint area;/輸入內(nèi)存空間Node *head,*last;void Init(int area)head=new Node(); last=new Node();head-next=last;last-back=head;last-data.addr=0;last-data.ID=0;last-data.size=area; last-data.state=FREE;Status FFA(int id,int size)Status BFA

18、(int id,int size) Status WFA(int id,int size)void Free(int id) Node *cur=head; while(cur) if(cur-data.ID=id) cur-data.state=FREE; cur-data.ID=FREE; if(cur-back-data.state=FREE)/與前面的空閑塊相連 cur-back-data.size+=cur-data.size; cur-back-next=cur-next; cur-next-back=cur-back; if(cur-next-data.state=FREE)/與

19、后面的空閑塊相連 cur-data.size+=cur-next-data.size; cur-next-next-back=cur-back; cur-back-next=cur-next; break; cur=cur-next; Status Assign(int choice)int id,size;coutid;coutendlsize;if(size=0)cout輸入錯誤!endl;return ERROR;if(choice=1)if(FFA(id,size)=OK)cout分配成功！endl;elsecout分配失??！endl;else if(choice=2)if(BFA(i

20、d,size)=OK)cout分配成功！endl;elsecout分配失??！endl;else if(choice=3)if(WFA(id,size)=OK)cout分配成功！endl;elsecout分配失??！next;while(cur)cout*endl;coutdata.ID=FREE)cout無endl;else coutdata.IDendl;cout起始地址:data.addrendl;cout分區(qū)長度:data.sizeendl;coutdata.state=BUSY)cout已分配endl;else cout未分配next;int main()cout 動態(tài)分區(qū)分配方式的模擬

21、 endl; cout*endl;coutarea;while(area=0)coutarea; while(1)cout*endl;cout* 1.FFA 2.BFA 3.WFA 0.EXIT *endl;cout*endl;coutch;if(ch=0)break;Init(area); int choice; while(1)cout*endl;cout* 1.ASSIGN 2.FREE 3.SHOW 0.QUIT *endl;cout* *endl;coutchoice;if(choice=1) coutnum;for(;num0;num-)Assign(ch); else if(choice=2) int ID;coutID;Free(ID);else if(choice=3) Show();else if(choice=0) break;elsecout輸入有誤，請重試！endl;continue