上傳人：紫***

認(rèn)證信息

認(rèn)證類(lèi)型：個(gè)人認(rèn)證

認(rèn)證主體：陳**（實(shí)名認(rèn)證）

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2021-01-16 格式：DOC 頁(yè)數(shù)：28 大小：476.50KB 積分：20 舉報(bào) 版權(quán)申訴

1、.一、實(shí)驗(yàn)?zāi)康氖煜ぶ鞔娴姆峙渑c回收。理解在不同的存儲(chǔ)管理方式下.如何實(shí)現(xiàn)主存空間的分配與回收。掌握動(dòng)態(tài)分區(qū)分配方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法及動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式及其實(shí)現(xiàn)過(guò)程。二、實(shí)驗(yàn)內(nèi)容和要求主存的分配和回收的實(shí)現(xiàn)是與主存儲(chǔ)器的管理方式有關(guān)的。所謂分配.就是解決多道作業(yè)或多進(jìn)程如何共享主存空間的問(wèn)題。所謂回收.就是當(dāng)作業(yè)運(yùn)行完成時(shí)將作業(yè)或進(jìn)程所占的主存空間歸還給系統(tǒng)?？勺兎謪^(qū)管理是指在處理作業(yè)過(guò)程中建立分區(qū).使分區(qū)大小正好適合作業(yè)的需求.并且分區(qū)個(gè)數(shù)是可以調(diào)整的。當(dāng)要裝入一個(gè)作業(yè)時(shí).根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間.若有.則按需要量分割一個(gè)分區(qū)分配給該作業(yè)；若無(wú).則作業(yè)不能裝入.作業(yè)

2、等待。隨著作業(yè)的裝入、完成.主存空間被分成許多大大小小的分區(qū).有的分區(qū)被作業(yè)占用.而有的分區(qū)是空閑的。實(shí)驗(yàn)要求使用可變分區(qū)存儲(chǔ)管理方式.分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)采用空閑分區(qū)表和空閑分區(qū)鏈來(lái)進(jìn)行.分區(qū)分配中所用的算法采用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法三種算法來(lái)實(shí)現(xiàn)主存的分配與回收。同時(shí).要求設(shè)計(jì)一個(gè)實(shí)用友好的用戶界面.并顯示分配與回收的過(guò)程。同時(shí)要求設(shè)計(jì)一個(gè)實(shí)用友好的用戶界面,并顯示分配與回收的過(guò)程。三、實(shí)驗(yàn)主要儀器設(shè)備和材料實(shí)驗(yàn)環(huán)境硬件環(huán)境：PC或兼容機(jī)軟件環(huán)境：VC+ 6.0四、實(shí)驗(yàn)原理及設(shè)計(jì)分析某系統(tǒng)采用可變分區(qū)存儲(chǔ)管理.在系統(tǒng)運(yùn)行當(dāng)然開(kāi)始.假設(shè)初始狀態(tài)下.可用的內(nèi)存空間為640

3、KB.存儲(chǔ)器區(qū)被分為操作系統(tǒng)分區(qū)（40KB）和可給用戶的空間區(qū)（600KB）。 （作業(yè)1 申請(qǐng)130KB、 作業(yè)2 申請(qǐng)60KB、 作業(yè)3 申請(qǐng)100KB 、 作業(yè)2 釋放 60KB 、 作業(yè)4 申請(qǐng) 200KB、 作業(yè)3釋放100KB、 作業(yè)1 釋放130KB 、 作業(yè)5申請(qǐng)140KB 、 作業(yè)6申請(qǐng)60KB 、作業(yè)7申請(qǐng)50KB） 當(dāng)作業(yè)1進(jìn)入內(nèi)存后.分給作業(yè)1（130KB）.隨著作業(yè)1、2、3的進(jìn)入.分別分配60KB、100KB.經(jīng)過(guò)一段時(shí)間的運(yùn)行后.作業(yè)2運(yùn)行完畢.釋放所占內(nèi)存。此時(shí).作業(yè)4進(jìn)入系統(tǒng).要求分配200KB內(nèi)存。作業(yè)3、1運(yùn)行完畢.釋放所占內(nèi)存。此時(shí)又有作業(yè)5申請(qǐng)140KB

4、.作業(yè)6申請(qǐng)60KB.作業(yè)7申請(qǐng)50KB。為它們進(jìn)行主存分配和回收。1、采用可變分區(qū)存儲(chǔ)管理.使用空閑分區(qū)鏈實(shí)現(xiàn)主存分配和回收。空閑分區(qū)鏈：使用鏈指針把所有的空閑分區(qū)鏈成一條鏈.為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接.在每個(gè)分區(qū)的起始部分設(shè)置狀態(tài)位、分區(qū)的大小和鏈接各個(gè)分區(qū)的前向指針.由狀態(tài)位指示該分區(qū)是否分配出去了；同時(shí).在分區(qū)尾部還設(shè)置有一后向指針.用來(lái)鏈接后面的分區(qū)；分區(qū)中間部分是用來(lái)存放作業(yè)的空閑內(nèi)存空間.當(dāng)該分區(qū)分配出去后.狀態(tài)位就由“0”置為“1”。設(shè)置一個(gè)內(nèi)存空閑分區(qū)鏈.內(nèi)存空間分區(qū)通過(guò)空閑分區(qū)鏈來(lái)管理.在進(jìn)行內(nèi)存分配時(shí).系統(tǒng)優(yōu)先使用空閑低端的空間。設(shè)計(jì)一個(gè)空閑分區(qū)說(shuō)明鏈.設(shè)計(jì)一個(gè)某時(shí)刻

5、主存空間占用情況表.作為主存當(dāng)前使用基礎(chǔ)。初始化空間區(qū)和已分配區(qū)說(shuō)明鏈的值.設(shè)計(jì)作業(yè)申請(qǐng)隊(duì)列以及作業(yè)完成后釋放順序.實(shí)現(xiàn)主存的分配和回收。要求每次分配和回收后顯示出空閑內(nèi)存分區(qū)鏈的情況。把空閑區(qū)說(shuō)明鏈的變化情況以及各作業(yè)的申請(qǐng)、釋放情況顯示打印出來(lái)。2.采用可變分區(qū)存儲(chǔ)管理.分別采用首次適應(yīng)算法、最佳適應(yīng)算法和最壞適應(yīng)算法實(shí)現(xiàn)主存分配和回收。3、主存空間分配 （1）首次適應(yīng)算法在該算法中.把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲(chǔ)空間時(shí).從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找.直到找到第一個(gè)能滿足要求的空閑區(qū).從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè).余下的空閑區(qū)

6、仍留在空閑區(qū)鏈中。（2）最佳適應(yīng)算法在該算法中.把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲(chǔ)空間時(shí).從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找.直到找到一個(gè)能滿足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都小.從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè).余下的空閑區(qū)仍留在空閑區(qū)鏈中（3）最壞適應(yīng)算法在該算法中.把主存中所有空閑區(qū)按其起始地址遞增的次序排列。在為作業(yè)分配存儲(chǔ)空間時(shí).從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找.直到找到一個(gè)能滿足要求的空閑區(qū)且該空閑區(qū)的大小比其他滿足要求的空閑區(qū)都大.從中劃出與請(qǐng)求的大小相等的存儲(chǔ)空間分配給作業(yè).余下的空閑區(qū)仍留在空閑

7、區(qū)鏈中。4、主存空間回收 當(dāng)一個(gè)作業(yè)執(zhí)行完成撤離時(shí).作業(yè)所占的分區(qū)應(yīng)該歸還給系統(tǒng)。歸還的分區(qū)如果與其它空閑區(qū)相鄰.則應(yīng)合成一個(gè)較大的空閑區(qū).登記在空閑區(qū)說(shuō)明鏈中.此時(shí).相鄰空閑區(qū)的合并問(wèn)題.要求考慮四種情況：（1） 釋放區(qū)下鄰空閑區(qū)（低地址鄰接）（2） 釋放區(qū)上鄰空閑區(qū)（高地址鄰接）（3） 釋放區(qū)上下都與空閑區(qū)鄰接（4） 釋放區(qū)上下鄰都與空閑區(qū)不鄰接五、程序流程圖main函數(shù)里的流程圖初始化first和end整理分區(qū)序號(hào)顯示空閑分區(qū)鏈選擇算法aa=1，首次適應(yīng)算法a=2，最佳適應(yīng)算法a=3，最壞適應(yīng)算法選擇操作ii=1，分配空間函數(shù)ai=0，退出程序i=2，回收空間函數(shù)結(jié)束分配空間里的流程圖p

8、-data.length=request分配不成功分配空間函數(shù)a=1a=2a=3輸入申請(qǐng)內(nèi)存大小按順序找空閑塊初始化q，使它指向空閑塊中長(zhǎng)度小的一塊輸入申請(qǐng)內(nèi)存大小初始化q，使它指向空閑塊中長(zhǎng)度大的一塊p-data.lengthrequestp的狀態(tài)為已分配剩下p-data.length-=request輸入申請(qǐng)內(nèi)存大小YYNN返回到整理分區(qū)序號(hào)回收空間里的流程圖p的狀態(tài)改為空閑回收p，p的前一個(gè)為firstp的后一個(gè)是endp的后一個(gè)狀態(tài)空與后面空閑塊相連將p 的狀態(tài)改為空閑將p 的狀態(tài)改為空閑回收空間函數(shù)p的后一個(gè)是endYNYNYNp的前一個(gè)狀態(tài)空p的前一個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空p的后一

9、個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空p的后一個(gè)狀態(tài)空YYYNNN與前面空閑塊相連p的狀態(tài)改為空閑與前面空閑塊相連與后面空閑塊相連YN返回到整理分區(qū)序號(hào)六、相關(guān)數(shù)據(jù)結(jié)構(gòu)及關(guān)鍵函數(shù)說(shuō)明本程序采用了一個(gè)struct free_table數(shù)據(jù)結(jié)構(gòu).里面包含分區(qū)序號(hào)（num）、起始地址（address）、分區(qū)長(zhǎng)度（length）和分區(qū)狀態(tài)（state）。還用了線性表的雙性鏈表存儲(chǔ)結(jié)構(gòu)（struct Node）.里面包含前區(qū)指針（prior）和后繼指針（next）。一開(kāi)始定義一條（含有first和end）的鏈.用開(kāi)始指針和尾指針開(kāi)創(chuàng)空間鏈表。然后分別按三種算法進(jìn)行分配和回收。在該程序中關(guān)鍵函數(shù)有.sort（）、all

10、ocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函數(shù)是用來(lái)整理分區(qū)序號(hào)的.如在刪序號(hào)3時(shí).她與前面序號(hào)2相連在一起了.然后序號(hào)2中的長(zhǎng)度總滿足申請(qǐng)的內(nèi)存大小.就會(huì)在序號(hào)2中分配.然后序號(hào)在2的基礎(chǔ)上加1.一直加.加到與原本序號(hào)3的下一個(gè)序號(hào)也就是4相等.這時(shí)sort（）就開(kāi)始有明顯的工作了；allocation（）是分配空間的.也是過(guò)渡到三個(gè)算法中的.當(dāng)三個(gè)算法中滿足或者不滿足分配請(qǐng)求.都會(huì)又返回值給allocation（）；recovery（）是用來(lái)回收內(nèi)存的.里面包含了四種情況相連結(jié)果.即釋放區(qū)上與空閑區(qū)鄰接

11、、釋放區(qū)下與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)鄰接、釋放區(qū)上下都與空閑區(qū)不鄰接這四種情況的結(jié)果。七、源代碼#include#include#define OK 1 /完成#define ERROR 0 /出錯(cuò)typedef int Status;typedef struct free_table/定義一個(gè)空閑區(qū)說(shuō)明表結(jié)構(gòu) int num; /分區(qū)序號(hào) long address; /起始地址 long length; /分區(qū)大小 int state; /分區(qū)狀態(tài)ElemType;typedef struct Node/ 線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu) ElemType data; struct Node

12、 *prior; /前趨指針 struct Node *next; /后繼指針Node,*LinkList; LinkList first; /頭結(jié)點(diǎn)LinkList end; /尾結(jié)點(diǎn)int flag;/記錄要?jiǎng)h除的分區(qū)序號(hào)Status Initblock()/開(kāi)創(chuàng)帶頭結(jié)點(diǎn)的內(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;

13、end-data.address=40; end-data.length=600; end-data.state=0; return OK;void sort()/分區(qū)序號(hào)重新排序 Node *p=first-next,*q; q=p-next; 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;/用來(lái)記錄分區(qū)序號(hào) Node *p=first; p-data.num=0; p-data.address=0

14、; p-data.length=40; p-data.state=1; sort(); printf(ntt主存空間分配情況n); printf(*nn); printf(分區(qū)序號(hào)t起始地址t分區(qū)大小t分區(qū)狀態(tài)nn); while(p) printf(%dtt%dtt%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) /為申請(qǐng)作

15、業(yè)開(kāi)辟新空間且初始化 Node *p=first-next; LinkList temp=(LinkList)malloc(sizeof(Node); temp-data.length=request; temp-data.state=1; p-data.num=1; while(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) /有空閑塊能滿足需求且有剩余 te

16、mp-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.address+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; /

17、記錄最小剩余空間 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) /初始化最小空間和最佳位置 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)

18、 q=p; ch=p-data.length-request; p=p-next; if(q=NULL) return ERROR;/沒(méi)有找到空閑塊 else if(q-data.length=request) q-data.state=1; return OK; else temp-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.leng

19、th=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); temp-data.length=request; temp-data.state=1; p-data.num=1; while(p) /初始化最大空間和最佳位置 if(p-data.state=0 & (p-data.len

20、gth=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;/沒(méi)有找到空閑塊 else if(q-data.length=request) q-data.length=1; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; tem

21、p-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;/申請(qǐng)內(nèi)存大小 printf(請(qǐng)輸入申請(qǐng)分配的主存大小(單位:KB):); scanf(%d,&request); if(requestnext) if(q=p) if(q-prior-data.state=0&q-next-data.state

22、!=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=q-next-next; q-next-next-prior=q; q-data.state=0; q-data.num=flag; if(q-prior-data

23、.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 deal2(Node *p)/處理回收空間 Node *q=first; for(;q!=NULL;q=q-next) if(q=

24、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.state=0; if(q-prior-data.state=0&q-next-data.state=0) q-prior-data.length

25、+=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!=end

26、)/當(dāng)前P指向的下一個(gè)不是最后一個(gè)時(shí) if(p-next-data.state=0) /與后面的空閑塊相連 p-data.length+=p-next-data.length; p-next-next-prior=p; p-next=p-next-next; p-data.state=0; p-data.num=flag; else p-data.state=0; if(p-next=end)/當(dāng)前P指向的下一個(gè)是最后一個(gè)時(shí) p-data.state=0; /結(jié)束if(p-prior=block_first)的情況 else if(p-prior!=first) if(p-next!=end)

27、 deal1(p); else deal2(p); /結(jié)束if(p-prior!=block_first)的情況 /結(jié)束if(p-data.num=flag)的情況 printf(t*回收成功*); return OK; /主函數(shù)void main() int i; /操作選擇標(biāo)記 int a;/算法選擇標(biāo)記 printf(*n); printf(tt用以下三種方法實(shí)現(xiàn)主存空間的分配n); printf(t(1)首次適應(yīng)算法t(2)最佳適應(yīng)算法t(3)最差適應(yīng)算法n);printf(*n); printf(n); printf(請(qǐng)輸入所使用的內(nèi)存分配算法:); scanf(%d,&a); wh

28、ile(a3) printf(輸入錯(cuò)誤.請(qǐng)重新輸入所使用的內(nèi)存分配算法:n); scanf(%d,&a); switch(a) case 1:printf(nt*使用首次適應(yīng)算法：*n);break; case 2:printf(nt*使用最佳適應(yīng)算法：*n);break; case 3:printf(nt*使用最壞適應(yīng)算法：*n);break; Initblock(); /開(kāi)創(chuàng)空間表 while(1) show(); printf(t1: 分配內(nèi)存t2: 回收內(nèi)存t0: 退出n); printf(請(qǐng)輸入您的操作：); scanf(%d,&i); if(i=1) allocation(a); / 分配內(nèi)存 else if(i=2) / 內(nèi)存回收 printf(請(qǐng)輸入您要釋放的分區(qū)號(hào)：); scanf(%d,&flag); recovery(flag); else if(i=0) printf(n退出程序n);break; /退出 else /輸入操作有誤 printf(輸入有誤.請(qǐng)重試！); continue; 八、執(zhí)行結(jié)果和結(jié)果