分區(qū)存儲(chǔ)管理模擬實(shí)驗(yàn)報(bào)告

1、存儲(chǔ)管理模擬實(shí)驗(yàn)報(bào)告文檔編制序號(hào)：KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688分區(qū)存儲(chǔ)管理模擬實(shí)驗(yàn)報(bào)告1 .實(shí)驗(yàn)?zāi)康牧私鈩?dòng)態(tài)分區(qū)存儲(chǔ)管理方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法，加深對(duì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式及其實(shí)現(xiàn)技術(shù)的理解。2 .實(shí)驗(yàn)內(nèi)容用C語言或Pascal語言分別實(shí)現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動(dòng)態(tài)分區(qū)分配過程Allocate。和回收過程Free。其中，空閑分區(qū)采用空閑分區(qū)鏈來組織，內(nèi)存分配時(shí)，優(yōu)先使用空閑區(qū)低地址部分的空間。假設(shè)初始狀態(tài)，可用內(nèi)存空間為640KB,作業(yè)請求序列如下（也可以編程從鍵盤輸入，R表示請求，F(xiàn)表示釋放）：作業(yè)1請求130KBo作業(yè)2請求60KBo作業(yè)

2、3請求100KBo作業(yè)2釋放60KBo作業(yè)4請求200KBo作業(yè)3釋放100KBo作業(yè)1釋放130KBo作業(yè)5請求140KBo作業(yè)6請求60KBo作業(yè)7請求50KBo作業(yè)6釋放60KBo要求每次分配和回收后顯示出空閑區(qū)鏈的情況。如果不能為作業(yè)的請求進(jìn)行內(nèi)存分配，給出相應(yīng)的提示信息。3 .實(shí)驗(yàn)分析和思考采用首次適應(yīng)算法和最佳適應(yīng)算法，對(duì)內(nèi)存的分配和回收速度有什么影響？如何解決碎片片問題？詳細(xì)設(shè)計(jì)首次適應(yīng)算法：當(dāng)要分配內(nèi)存空間時(shí)，就查表，在各空閑區(qū)中查找滿足大小要求的可用塊。只要找到第一個(gè)足以滿足要球的空閑塊就停止查找，并把它分配出去；如果該空閑空間與所需空間大小一樣，則從空閑表中取消該項(xiàng)；如果還

3、有剩余，則余下的部分仍留在空閑表中，但應(yīng)修改分區(qū)大小和分區(qū)始址。最佳適應(yīng)算法：當(dāng)要分配內(nèi)存空間時(shí)，就查找空閑表中滿足要求的空閑塊，并使得剩余塊是最小的。然后把它分配出去，若大小恰好合適，則直按分配；若有剩余塊，則仍保留該余下的空閑分區(qū)，并修改分區(qū)大小的起始地址。內(nèi)存回收：將釋放作業(yè)所在內(nèi)存塊的狀態(tài)改為空閑狀態(tài)，刪除其作業(yè)名，設(shè)置為空。并判斷該空閑塊是否與其他空閑塊相連，若釋放的內(nèi)存空間與空閑塊相連時(shí)，則合并為同一個(gè)空閑塊，同時(shí)修改分區(qū)大小及起始地址。typedefstructfreeareaElemType;定義一個(gè)空閑區(qū)說明表結(jié)構(gòu)，每申請一個(gè)作業(yè)，改作業(yè)便具有此結(jié)構(gòu)體typedefstruc

4、tDuLNodeDuLNode,*DuLinkList;定義一個(gè)雙向鏈表StatusInitblock()開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表,通過雙向鏈表把申請的作業(yè)鏈接起來，作業(yè)的插入和刪除，和鏈表中節(jié)點(diǎn)的插入和刪除類似。雙向鏈表如圖1所示StatusFirst_fit(intID,intrequest)傳入作業(yè)名及申請量采用首次適應(yīng)算法實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存分區(qū)分配的模擬，初始態(tài)640KB,只是一個(gè)虛態(tài)，每申請成功一個(gè)作業(yè)，便相應(yīng)的640KB做相應(yīng)的減少，同過雙向鏈表模擬主存的分配情況。內(nèi)存分配流程如圖2所示Statusfree(intID)傳過來需要回收的分區(qū)號(hào)實(shí)現(xiàn)分區(qū)的回收，對(duì)不同情況采取不同的處理vo

5、idshow()顯示當(dāng)前主存的分配情況源程序/動(dòng)態(tài)分區(qū)分配方式的模擬/#include<iostream.h>#include<stdlib.h>ttdefineFree0空閑狀態(tài)ftdefineBusy1己用狀態(tài)ttdefineOK1完成ttdefineERROR0出錯(cuò)ttdefineMAX_length640最大內(nèi)存空間為640KBtypedefintStatus;typedefstructfreearea定義一個(gè)空閑區(qū)說明表結(jié)構(gòu)intID;分區(qū)號(hào)longsize;分區(qū)大小longaddress;/分區(qū)地址intstate;狀態(tài)ElemType;/線性表的雙向鏈表存

6、儲(chǔ)結(jié)構(gòu)typedefstructDuLNode/doublelinkedlistElemTypedata;structDuLNode*prior;前趨指針structDuLNode*next;后繼指針DuLNode,*DuLinkList;DuLinkListblock_first;頭結(jié)點(diǎn)DuLinkListblock_last;尾結(jié)點(diǎn)Statusalloc(int);內(nèi)存分配Statusfree(int);內(nèi)存回收StatusFirst_fit(int,int);首次適應(yīng)算法StatusBest_fit(int,int);/最佳適應(yīng)算法voidshow。；查看分配StatusInitbloc

7、k();開創(chuàng)空間表StatusInitblock()開創(chuàng)帶頭結(jié)點(diǎn)的內(nèi)存空間鏈表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first->prior=NULL;blockfirst->next=blocklast;block_last->prior=block_first;block_last->next=NULL;block_last->data.address=O;block_last->data.siz

8、e=MAX_length;block_last->data.ID=O;block_last->data.state=Free;returnOK;)/分配主存Statusalloc(intch)intID,request;cout<<請輸入作業(yè)(分區(qū)號(hào)分;cin»ID;coutG請輸入需要分配的主存大小(單位:KB):；cin>>request;if(request<0request=0)(cout<<分配大小不合適，請重試！"<<endl;returnERROR;)if(ch=2)選擇最佳適應(yīng)算法if(Bes

9、t_fit(ID,request)=0K)cout<<分配成功!，<<endl;elsecout<內(nèi)存不足，分配失?。?lt;<endl;returnOK;)else默認(rèn)首次適應(yīng)算法(if(First_fit(ID,request)=0K)cout<分配成功！<<endl;elsecout<內(nèi)存不足，分配失??！<<endl;returnOK;)/首次適應(yīng)算法StatusFirst_fit(intID,intrequest)傳入作業(yè)名及申請量(為申請作業(yè)開辟新空間且初始化DuLinkListtemp=(DuLinkList)

10、malloc(sizeof(DuLNode);temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode*p=block_first->next;while(p)(if(p->data.state二二Free&&p->data.size二二request)有大小恰好合適的空閑塊p->data.state二Busy;p->data.ID=ID;returnOK;break;)if(p->data.state二二Free&&p-&g

11、t;data.size>request)有空閑塊能滿足需求且有剩余temp->prior=p->prior;temp-next=p;temp->data.address=p->data.address;p->prior->next:ztemp;p->prior=ztemp;p->data.address=:temp->data.address+temp->data.size;p->data.size-=request;returnOK;break;p=p->next;returnERROR;/最佳適應(yīng)算法Status

12、Best-fit(intID,intrequest)(intch;記錄最小剩余空間DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode);temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode*p=block_first->next;DuLNode*q二NULL;記錄最佳插入位置while(p)初始化最小空間和最佳位置(if(p->data.state二二Free&&(p->data.size>request

13、p->data.size-request)Q-P；ch=p->data.size-request;break;)p=p->next;rhile(p)if(p->data.state二二Free&&p->data.size二二request)空閑塊大小恰好合適p->data.ID=ID;p->data.state二Busy;returnOK;break;)if(p->data.state二二Free&&p->data.size>request)空閑塊大于分配需求if(p->data.size-req

14、uestch)剩余空間比初值還小(ch=p->data.size-request;更新剩余最小值q二P；更新最佳位置指向p=p->next;if(q二二NULL)returnERROR;沒有找到空閑塊else找到了最佳位置并實(shí)現(xiàn)分配temp->prior=:q->prior;temp-next=q;temp->data.address=q->data.address;q->prior->next=:temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return

15、OK;)/主存回收Statusfree(intID)(DuLNode*p=block_first;while(p)if(p->data.ID=ID)p->data.state=Free;p->data.ID=Free;if(p->prior->data.state=Free)/與前面的空閑塊相連p->prior->data.size+=p->data.size;p->prior->next=:p->next;p->next->prior=p->prior;)if(p->next->data.stat

16、e=Free)/與后面的空閑塊相連p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;)break;)p=p->next;)returnOK;)/顯示主存分配情況voidshow()cout<<z/n;cout«z，主存分配情況n;cout<<z/n;DuLNode*p=block_first->next;while(p)(cout。分區(qū)號(hào)：；if(p->data.ID二二Free)co

17、ut<<，F(xiàn)ree，<<endl;elsecout<<p->data.ID<<endl;cout<起始地址：<<p->data.address<<endl;cout<<分區(qū)大?。海?lt;<p->data.size<<z，KB，<<endl;cout<狀態(tài)：；if(p->data.state=Free)cout<"空閑<<endl;elsecout<<”已分配endl;cout<<，z<endl;p=p->next;/主函數(shù)voidmain()(intch;算法選擇標(biāo)記cout«，z動(dòng)態(tài)分區(qū)分配方式的模擬n;cout<<z，n;cout«，z-1)首次適應(yīng)算法2)最佳適應(yīng)算法一n；cout<<，zn;COUtG請選擇分配算法：；cin>>ch;InitblockO;開創(chuàng)空間表intchoice;操作選擇標(biāo)記while(1)cout<<z/n;cout<<z/1:分配內(nèi)存2:回收