模擬設(shè)計(jì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理的分配與回收

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

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

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

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

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

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

7、n table int id;/分區(qū)號(hào)int addr;/起始地址 int size;/分區(qū)長(zhǎng)度 Status state;/狀態(tài);2.2.2 雙向鏈表struct Node/雙向鏈表結(jié)點(diǎn) 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ū)（鏈）按地址遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí),從空閑分區(qū)表/鏈?zhǔn)组_(kāi)始順序查找,直到找到第一個(gè)滿(mǎn)足其大小要求的

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

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

14、作業(yè)要求的最大的分區(qū)分配給作業(yè)。這樣使分給作業(yè)后剩下的空閑分區(qū)也較大，可裝下其它作業(yè)。但由于最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有大作業(yè)到來(lái)時(shí)，其存儲(chǔ)空間的申請(qǐng)往往會(huì)得不到滿(mǎn)足。Status WFA(int id,int size)/worst fit algorithmNode *temp=new Node(id,size);temp-data.state=BUSY;int max;/記錄符合滿(mǎn)足請(qǐng)求的最小空閑塊大小Node *fit;/指向采用最壞適應(yīng)算法的插入位置Node *cur=head-next;while(cur)/取得第一個(gè)可以分配的位置（不一定是最佳位置）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.開(kāi)發(fā)平臺(tái)及源程序的主要部分3.1開(kāi)發(fā)平臺(tái) 本次課程設(shè)計(jì)開(kāi)發(fā)平臺(tái)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輸入錯(cuò)誤!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無(wú)endl;else coutdata.IDendl;cout起始地址:data.addrendl;cout分區(qū)長(zhǎng)度:data.sizeendl;coutdata.state=BUSY)cout已分配endl;else cout未分配next;int main()cout 動(dòng)態(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輸入有誤，請(qǐng)重試！endl;continue