2023年分區(qū)存儲管理模擬實驗報告

分區(qū)存儲管理模擬實驗報告1.實驗目的了解動態(tài)分區(qū)存儲管理方式中的數據結構和分派算法，加深對動態(tài)分區(qū)存儲管理方式及其實現技術的理解。２.實驗內容用C語言或Pａsｃal語言分別實現采用初次適應算法和最佳適應算法的動態(tài)分區(qū)分派過程Allocate（)和回收過程Fｒeｅ（)。其中,空閑分區(qū)采用空閑分區(qū)鏈來組織，內存分派時，優(yōu)先使用空閑區(qū)低地址部分的空間。假設初始狀態(tài)，可用內存空間為640KB,作業(yè)請求序列如下（也可以編程從鍵盤輸入,Ｒ表達請求，Ｆ表達釋放):作業(yè)1請求１30ＫB。作業(yè)2請求60KＢ。作業(yè)3請求100ＫB。作業(yè)2釋放６0KB。作業(yè)4請求20０KB。作業(yè)3釋放1０0ＫB。作業(yè)１釋放13０KＢ。作業(yè)5請求140KB。作業(yè)6請求60KB。作業(yè)７請求50KＢ。作業(yè)6釋放6０KB。規(guī)定每次分派和回收后顯示出空閑區(qū)鏈的情況。假如不能為作業(yè)的請求進行內存分派,給出相應的提醒信息。3.實驗分析和思考采用初次適應算法和最佳適應算法，對內存的分派和回收速度有什么影響？如何解決碎片片問題？具體設計初次適應算法：當要分派內存空間時，就查表,在各空閑區(qū)中查找滿足大小規(guī)定的可用塊。只要找到第一個足以滿足要球的空閑塊就停止查找，并把它分派出去;假如該空閑空間與所需空間大小同樣，則從空閑表中取消該項；假如尚有剩余,則余下的部分仍留在空閑表中,但應修改分區(qū)大小和分區(qū)始址。最佳適應算法：當要分派內存空間時,就查找空閑表中滿足規(guī)定的空閑塊，并使得剩余塊是最小的。然后把它分派出去，若大小恰好合適，則直按分派;若有剩余塊,則仍保存該余下的空閑分區(qū),并修改分區(qū)大小的起始地址。內存回收：將釋放作業(yè)所在內存塊的狀態(tài)改為空閑狀態(tài)，刪除其作業(yè)名,設立為空。并判斷該空閑塊是否與其他空閑塊相連,若釋放的內存空間與空閑塊相連時，則合并為同一個空閑塊，同時修改分區(qū)大小及起始地址。tyｐedｅfstructfreearｅa｛｝ElｅｍTyｐe;定義一個空閑區(qū)說明表結構，每申請一個作業(yè)，改作業(yè)便具有此結構體tｙpedefstructDuLNｏｄe{}DuLNodｅ，*DuＬinkList；定義一個雙向鏈表StaｔusInｉｔblｏck(){}開創(chuàng)帶頭結點的內存空間鏈表,通過雙向鏈表把申請的作業(yè)鏈接起來,作業(yè)的插入和刪除,和鏈表中節(jié)點的插入和刪除類似。雙向鏈表如圖1所示StａｔusFiｒｓt_fiｔ(iｎtＩD,iｎtrｅquesｔ)｛｝傳入作業(yè)名及申請量采用初次適應算法實現動態(tài)內存分區(qū)分派的模擬,初始態(tài)6４0ＫＢ,只是一個虛態(tài)，每申請成功一個作業(yè),便相應的640ＫB做相應的減少，同過雙向鏈表模擬主存的分派情況。內存分派流程如圖２所示Ｓｔatusfrｅe(intID)傳過來需要回收的分區(qū)號實現分區(qū)的回收,對不同情況采用不同的解決voidshoｗ（)顯示當前主存的分派情況源程序//－－---------－--－－--------－--－－-－---－-------－-－--－---------－-－----／/-－-－-----動態(tài)分區(qū)分派方式的模擬--－----－-／／---－----－--－--－－---－－-----－---------－－----－-－---－--－－－-－--------#incｌｕde<iostream.h>#iｎcｌude<ｓtｄlｉb.h＞#deｆｉneFree０／/空閑狀態(tài)#deｆｉneＢusy1／／已用狀態(tài)#defineOK1//完畢＃defineERROＲ0//犯錯#defineMAX＿lｅｎgth64０／/最大內存空間為640ＫBtｙｐｅdefiｎtＳtatuｓ；ｔypedｅｆsｔrucｔfreeａreａ//定義一個空閑區(qū)說明表結構{ ｉntID；//分區(qū)號 lｏngｓize；/／分區(qū)大小 lｏnｇａddress;／／分區(qū)地址?iｎtｓtate；//狀態(tài)｝EleｍTypｅ；//----－--－--線性表的雙向鏈表存儲結構----－-－-----typedefｓtrｕctＤuLNode//doublelinkedｌist{?ＥlｅmＴypｅｄａt(yī)ａ; ｓtruｃtDｕLＮode＊pｒior；//前趨指針?struｃtDuLＮｏde*nexｔ;//后繼指針}DuLＮｏdｅ，＊ＤuLinkＬｉst;DuLinkLｉｓｔblock_ｆirst;／/頭結點ＤuLinkLisｔbｌock_last;//尾結點Statusalloc(iｎt);//內存分派Statuｓfｒee（int）;//內存回收StatusFirst＿fit(inｔ,int);／/初次適應算法ＳtatusＢest＿fｉt（int，int）;//最佳適應算法voidｓhow();/／查看分派StatuｓＩnitｂlock();//開創(chuàng)空間表ＳtatusIｎitblock()／/開創(chuàng)帶頭結點的內存空間鏈表{?bloｃk＿fｉrst＝(DuＬiｎkLiｓｔ)malｌｏc(sizeof(DuＬNｏｄe));?ｂｌock_last=(DｕLinkList)malｌoｃ(sizeｏf（DuLNoｄe）)；?bｌoｃｋ＿firsｔ->pｒiｏr=NULL;?block_fiｒｓt－>ｎext=bｌock_lａst;?bｌock_last->pｒior=bｌocｋ_first； ｂｌocｋ_last－>next=NUＬL; ｂloｃk_lａsｔ->ｄatａ.addrｅss=0;?bｌock_lasｔ->datａ.size=MAＸ_leｎgth; blｏck＿laｓt->data.IＤ=0; bloｃk_laｓt－＞ｄａt(yī)a.sｔatｅ=Ｆrｅe;?reｔuｒnOK;}//－－-－－-----－--－---－-－---分配主存－------－---－----－--－－－---Statusallｏc（iｎtcｈ){?intＩD,requesｔ；?couｔ<<"請輸入作業(yè)(分區(qū)號)：";?cｉn>>ID; cout<<"請輸入需要分派的主存大?。▎挝?KＢ）：";?cin>>ｒｅquesｔ; iｆ（ｒequｅｓt<0｜|rｅquesｔ==0）?{ cｏｕt＜<＂分派大小不合適，請重試!"<<ｅnｄl； ?reｔuｒｎERROR； ｝ if（ch=＝2）／/選擇最佳適應算法 ｛ ?if(Best_fit（ID,request)==ＯK)cｏｕt<<"分派成功！"＜<endl; ?elsecout＜＜"內存局限性，分派失敗!＂＜<ｅndl；??rｅｔurnOK; } else//默認初次適應算法?{ if（First_fiｔ(ID,reqｕｅst)＝=ＯK)ｃout<＜"分派成功!"<＜endl;? eｌsecout<<＂內存局限性,分派失敗!＂＜＜ｅndl;? returｎＯK;?}}//-－－－-－-----－-----－初次適應算法－-------－------－-－－----StatusFirst_fit(intＩD,intreｑｕeｓｔ)／/傳入作業(yè)名及申請量{?//為申請作業(yè)開辟新空間且初始化 DuＬiｎｋListｔeｍｐ=(DｕＬinｋＬisｔ)malｌoc(sizeof(DｕLNodｅ）)；?temｐ->daｔa.ＩD=ID; teｍｐ->data.size=requeｓt; temp－＞daｔa.ｓtate＝Bｕｓy;?DｕLNodｅ*p＝blocｋ_ｆirｓt-＞next;?ｗhｉle(p) {??if(ｐ-＞ｄata.staｔe＝=Fｒeｅ＆&p－＞data.ｓize==rｅｑuest)? {／/有大小恰好合適的空閑塊 ??p->datａ．ｓtaｔｅ=Busy; ?p－＞ｄata.IＤ=ID; ｒetｕｒｎOK;? ?bｒeak; ?}??if（p－>ｄata.statｅ＝=Ｆｒｅe&＆p->dａt(yī)a.ｓiｚe>ｒｅｑuｅst) ｛//有空閑塊能滿足需求且有剩余" ?temp->ｐrｉoｒ＝p->prior;?? temp->next=p； ??teｍp->datａ.aｄdresｓ=p->datａ.aｄdｒess； p->prioｒ-＞neｘt=temp;? p->prioｒ=teｍp; p-＞data.adｄrｅsｓ=tｅmp-＞data.adｄｒeｓs＋teｍｐ-＞ｄata.ｓｉze;?? p->data．siｚe-＝request;? ?reｔurnOK;?? brｅak; ?} ?p=p－＞nexｔ;?}?reｔｕrｎERROR;}//--------－--－-－----－-最佳適應算法－-－－-－－----－---------－--Stａt(yī)usBest＿ｆit(ｉnｔＩD,intｒｅquest)｛ intch;／／記錄最小剩余空間?DｕLiｎkＬｉsttemp=(DuＬinkList）malｌｏc(siｚeｏｆ(DuＬNode)); temp->datａ.ＩD=ID;?tｅmp->datａ.ｓｉｚe=requeｓt; ｔemp->daｔa.state=Buｓy;?DuLNode＊p=blｏcｋ_firｓt－＞nｅxt;?ＤｕLNoｄe*q＝NＵLL；//記錄最佳插入位置 whｉlｅ（p)//初始化最小空間和最佳位置?｛ ?if(p->data.sｔaｔe=＝Frｅe&＆? ?(ｐ->data.sｉze＞ｒeqｕest||p->data．siｚe==reｑuest）) ?{???q=p; ? ch=p－>dａt(yī)a．size－rｅqｕeｓt; brｅａk; ｝ p=p－>nｅxt;?}?wｈile(p) { if(ｐ->ｄａt(yī)a.ｓｔate==Frｅe＆&ｐ->data．size=＝requｅst) {／/空閑塊大小恰好合適 ??ｐ->ｄata.ID=ID;? p－＞data.state＝Buｓy;???retｕrｎOK; ?break；??}? iｆ(p－>data．staｔe=＝Free&＆p－＞data.sizｅ>rｅqｕesｔ) {//空閑塊大于分派需求 ?if(p-＞data.sizｅ－reｑｕeｓt<cｈ)／／剩余空間比初值還小 ? ｛? ｃh=p->data．size－ｒequeｓt;／/更新剩余最小值 ?q=p;//更新最佳位置指向 ?}? }??p=p->nexｔ； ｝?if(q==NULＬ）reｔｕrｎERＲＯR;//沒有找到空閑塊?eｌｓe?{/／找到了最佳位置并實現分派??temｐ->pｒior=q－>prior;??ｔｅmｐ－＞neｘt=q； ?tｅｍp->ｄａt(yī)a.addreｓs=q－>datａ.aｄｄrｅｓs; ?q->pｒior-＞nexｔ=temp；? ｑ->pｒior＝ｔemp；??q－>dａt(yī)a.aｄdresｓ+=rｅquest;??ｑ->dａt(yī)a.siｚe=ｃh;??rｅtuｒnOK； }}／/－-----－-－-----－---－－---主存回收--－--－－----－－-------Statｕsfree(ｉntＩD){?DuLNode*p=ｂｌocｋ＿first;?whiｌe（ｐ)?｛??if(p->data.ＩＤ=＝ID）??{? p－＞daｔa．staｔe=Ｆree; ??ｐ－>daｔａ.ID=Ｆｒee;???ｉf(p-＞prｉoｒ-＞daｔa.ｓｔate==Free）／/與前面的空閑塊相連 ?{ p－>prｉｏr->datａ.sｉze+=ｐ->data.siｚe; ???p->prior-＞next＝p->ｎexｔ；? ｐ->next-＞prｉor=p－>prior; ? }?? iｆ（p-＞ｎext->ｄata．sｔate==Ｆree)／／與后面的空閑塊相連???{ ?? p->ｄata.siｚe+=p－>next－>dａt(yī)a.siｚe;? ??p－>nｅｘt－>nｅxt－>pｒior=ｐ; ??p－>nexｔ=ｐ－>ｎext-＞nｅxt； ?? ??}?? ?breaｋ; ? } ?p=p->next;?｝ returｎOＫ；}//---------------顯示主存分派情況---－－--－---－－--－--vｏidshoｗ(）｛ cｏut<<"－---－--－－－-－－---－－---－--------------－--\n"; coｕt＜<"--－主存分配情況--－\n"; cｏut<<＂-----------－------－-－-－--－------－－--－--\n"； DｕＬNode*p=ｂlock_fiｒｓt－>neｘt；?whilｅ（p)?{? cout＜＜＂分區(qū)號：＂；? if(p->dａt(yī)a．IＤ==Freｅ)cｏut<<"Free"<＜endl;??elｓecouｔ<<p->ｄaｔa．ＩD＜＜ｅｎdl； ?ｃouｔ＜<"起始地址："<<p->ｄａt(yī)a．address<<ｅnｄl；??cout＜<"分區(qū)大小:＂<<p->datａ.size<<＂KB"<<endl; couｔ＜<"狀態(tài)："; ?if(ｐ->datａ.ｓtate=＝Ｆree)coｕt<<"空閑"<<endl; ｅｌsｅcouｔ<＜"已分派"<＜endｌ;??coｕt＜<"-----－－-----－-"＜＜endl;? p=p->nexｔ;?｝}／/－---－-－－----－----－-－－--主函數------------－-－----－---－---voiｄｍain（){ inｔch;//算法選擇標記?ｃout<<"動態(tài)分區(qū)分派方式的模擬\n"； coｕt<＜"--－－－-----－--－----－－－--－-------－----＼n"; ｃout<<"--1)初次適應算法2）最佳適應算法