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

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

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

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

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

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

7、n table int id;/分區號int addr;/起始地址 int size;/分區長度 Status state;/狀態;2.2.2 雙向鏈表struct Node/雙向鏈表結點 PST data; Node *back;/前驅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 最先適應算法空閑分區（鏈）按地址遞增的次序排列。在進行內存分配時,從空閑分區表/鏈首開始順序查找,直到找到第一個滿足其大小要求的

8、空閑分區為止。然后再按照作業大小，從該分區中劃出一塊內存空間分配給請求者，余下的空閑分區仍留在空閑分區表（鏈）中。算法特點:優先利用內存低地址部分的空閑分區,從而保留了高地址部分的大空閑區。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區的開銷。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 最佳適應算法空閑分區表/鏈按容量大小遞增的次序排列。在進行內存分配時，從空閑分區表/鏈的首開始順序查找，直到找到第一個滿足其大小要求的空閑分區為止。按這種方式為作業分配內存，就能把既滿足作業要求又與作業大小最接近的空閑分區分配給作業。如果該空閑分區大于作業的大小，則與首次適應算法相同，將剩余空閑分區仍留在空閑分區表/鏈中。 算法特點：若存在與作業大小一致的空閑分區,則它必然被選中，若不存在與作業大小一致的空閑分區，則只劃分比作業稍大的空閑分區，,從而保留

11、了大的空閑分區,但空閑區一般不可能正好和它申請的內存空間大小一樣,因而將其分割成兩部分時,往往使剩下的空閑區非常小,從而在存儲器中留下許多難以利用的小空閑區（碎片或零頭）。Status BFA(int id,int size)/best fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int min;/記錄符合滿足請求的最小空閑塊大小Node *fit;/指向采用最佳適應算法的插入位置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 最壞適應算法空閑分區表/鏈按容量大小遞減的次序排列。在進行內存分配時，從空閑分區表的首開始順序查找，直到找到第一個比之大的空閑分區為止。剩下的空閑仍留在空閑分區表/鏈中。算法特點：總是挑選滿足

14、作業要求的最大的分區分配給作業。這樣使分給作業后剩下的空閑分區也較大，可裝下其它作業。但由于最大的空閑分區總是因首先分配而劃分，當有大作業到來時，其存儲空間的申請往往會得不到滿足。Status WFA(int id,int size)/worst fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int max;/記錄符合滿足請求的最小空閑塊大小Node *fit;/指向采用最壞適應算法的插入位置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.開發平臺及源程序的主要部分3.1開發平臺 本次課程設計開發平臺Microsoft Visual C+ 6.0 3.2 源程序的主要部分/#define MAX

17、_LEN 1024/定義內存大小，1024字節enum StatusFREE,BUSY,OK,ERROR;struct PSTstruct Nodeint area;/輸入內存空間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分區長度:data.sizeendl;coutdata.state=BUSY)cout已分配endl;else cout未分配next;int main()cout 動態分區分配方式的模擬

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