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

分區(qū)存儲管理模擬實驗報告分區(qū)存儲管理模擬實驗報告了解動態(tài)分區(qū)存儲管理方式中的數(shù)據(jù)結(jié)構(gòu)和分配算法，加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)技術(shù)的理解。2.實驗內(nèi)容用C語言或Pascal語言分別實現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動態(tài)分區(qū)分配過程Allocate()和回收過程Free()。其中，空閑分區(qū)采用空閑分區(qū)鏈來組織，內(nèi)存分配時，優(yōu)先使用空閑區(qū)低地址部分的空假設(shè)初始狀態(tài)，可用內(nèi)存空間為640KB，作業(yè)請求序列如下(也可以編要求每次分配和回收后顯示出空閑區(qū)鏈的情況。如果不能為作業(yè)的請求進(jìn)行內(nèi)存分配，給出相應(yīng)的提示信息。3．實驗分析和思考采用首次適應(yīng)算法和最佳適應(yīng)算法，對內(nèi)存的分配和回收速度有什么影詳細(xì)設(shè)計首次適應(yīng)算法：當(dāng)要分配內(nèi)存空間時，就查表，在各空閑區(qū)中查找滿足大小要求的可用塊。只要找到第一個足以滿足要球的空閑塊就停止查找，并把它分配出去；如果該空閑空間與所需空間大小一樣，則從空閑表中取消該項；如果還有剩余，則余下的部分仍留在空閑表中，但應(yīng)修改分區(qū)大小和分區(qū)始址。最佳適應(yīng)算法：當(dāng)要分配內(nèi)存空間時，就查找空閑表中滿足要求的空閑直按分配；若有剩余塊，則仍保留該余下的空閑分區(qū)，并修改分區(qū)大小的起始地址。內(nèi)存回收：將釋放作業(yè)所在內(nèi)存塊的狀態(tài)改為空閑狀態(tài)，刪除其作業(yè)名，設(shè)置為空。并判斷該空閑塊是否與其他空閑塊相連，若釋放的內(nèi)存空間與空閑塊相連時，則合并為同一個空閑塊，同時修改分區(qū)大小及起始地址。typedefstructfreearea{}ElemType;定義一個空閑區(qū)說明表結(jié)構(gòu)，每申請一個作業(yè)，改作業(yè)便具有此結(jié)構(gòu)體typedefstructDuLNode{}DuLNode,*DuLinkList;定義一個雙向鏈表StatusInitblock(){}開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表,通過雙向鏈表把申請的作業(yè)鏈接起來，作業(yè)的插入和刪除，和鏈表中節(jié)點的插入和刪除類似。雙向鏈表如圖1所示StatusFirst_fit(intID,intrequest){}傳入作業(yè)名及申請量采用首次適應(yīng)算法實現(xiàn)動態(tài)內(nèi)存分區(qū)分配的模擬，初始態(tài)640KB，只是一個虛態(tài)，每申請成功一個作業(yè)，便相應(yīng)的640KB做相應(yīng)的減少，同過雙向鏈表模擬主存的分配情況。內(nèi)存分配流程如圖2所示Statusfree(intID)傳過來需要回收的分區(qū)號實現(xiàn)分區(qū)的回收，對不同情況采取不同的處理voidshow()顯示當(dāng)前主存的分配情況源程序//----------------------------------------------------------------//---------動態(tài)分區(qū)分配方式的模擬---------//----------------------------------------------------------------#include<iostream.h>#include<stdlib.h>#defineFree0//空閑狀態(tài)#defineBusy1//已用狀態(tài)#defineOK1//完成#defineERROR0//出錯#defineMAX_length640//最大內(nèi)存空間為640KBtypedefintStatus;typedefstructfreearea//定義一個空閑區(qū)說明表結(jié)構(gòu){intID;//分區(qū)號longsize;//分區(qū)大小longaddress;//分區(qū)地址intstate;//狀態(tài)}ElemType;//----------線性表的雙向鏈表存儲結(jié)構(gòu)------------typedefstructDuLNode//doublelinkedlist{ElemTypedata;structDuLNode*prior;//前趨指針structDuLNode*next;//后繼指針}DuLNode,*DuLinkList;DuLinkListblock_first;//頭結(jié)點DuLinkListblock_last;//尾結(jié)點Statusalloc(int);//內(nèi)存分配Statusfree(int);//內(nèi)存回收StatusFirst_fit(int,int);//首次適應(yīng)算法StatusBest_fit(int,int);//最佳適應(yīng)算法voidshow();//查看分配StatusInitblock();//開創(chuàng)空間表StatusInitblock()//開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表{block_first=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_first->prior=NULL;block_first->next=block_last;block_last->prior=block_first;block_last->next=NULL;block_last->data.address=0;block_last->data.size=MAX_length;block_last->data.ID=0;block_last->data.state=Free;returnOK;}//-----------------------分配主存-------------------------Statusalloc(intch){intID,request;cout<<"請輸入作業(yè)(分區(qū)號)：";cin>>ID;cout<<"請輸入需要分配的主存大小(單位:KB)：";cin>>request;{coutendl;returnERROR;}if(ch==2)//選擇最佳適應(yīng)算法{if(Best_fit(ID,request)==OK)cout<<"分配成功！"<<endl;elsecout<<endl;returnOK;}else//默認(rèn)首次適應(yīng)算法{if(First_fit(ID,request)==OK)cout<<"分配成功！"<<endl;elsecout<<endl;returnOK;}}//------------------首次適應(yīng)算法-----------------------StatusFirst_fit(intID,intrequest)//傳入作業(yè)名及申請量{//為申請作業(yè)開辟新空間且初始化DuLinkListtemp=(DuLinkList)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->data.size>request){//有空閑塊能滿足需求且有剩余"temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;returnOK;break;}p=p->next;}returnERROR;}//--------------------最佳適應(yīng)算法------------------------StatusBest_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||p->data.size==request)){qp;ch=p->data.size-request;break;}p=p->next;}while(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-request<ch)//剩余空間比初值還小{ch=p->data.size-request;//更新剩余最小值q=p;//更新最佳位置指向}}p=p->next;}if(q==NULL)returnERROR;//沒有找到空閑塊e{//找到了最佳位置并實現(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;returnOK;}}//-----------------------主存回收--------------------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.state==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<<"---------------------------------------\n";cout<<"---主存分配情況---\n";cout<<"---------------------------------------\n";DuLNode*p=block_first->next;while(p){if(p->data.ID==Free)cout<<"Free"<<endl;elsecout<<p->data.ID<<endl;cout"<<p->data.address<<endl;cout<<"分區(qū)大?。?<<p->data.size<<"KB"<<endl;if(p->data.state==Free)cout<<"空閑"<<endl;elsecout<<"已分配"<<endl;cout<<"--------------"<<endl;p=p->next;}}//-----------------------主函數(shù)---------------------------voidmain(){intch;//算法選擇標(biāo)記cout<<"動態(tài)分區(qū)分配方式的模擬\n";cout<<"------------------------------------\n";cout<<"--1)首次適應(yīng)算法2)最佳適應(yīng)算法--\n";cout<<"------------------------------------\n";cin>>ch;Initblock();//開創(chuàng)空間表intchoice;//操作選擇標(biāo)記while(1){cout<<"--------------------------------------------\n";cout<<"--1:分配內(nèi)存2:回收內(nèi)存--\n"