存儲(chǔ)器管理動(dòng)態(tài)分區(qū)分配算法的模擬

1、計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)報(bào)告指導(dǎo)老師：吳 江 紅 題 目：存儲(chǔ)器管理-動(dòng)態(tài)分區(qū)分配算法的模擬 班 級(jí)： 031024班 姓 名：張佳（03102417）趙慧（03102419） 一、 設(shè)計(jì)任務(wù)： 編寫程序完成“存儲(chǔ)器管理動(dòng)態(tài)分區(qū)分配算法”的模擬，設(shè)計(jì)主界面來(lái)靈活選擇各算法，其中包括首次適應(yīng)算法，最佳適應(yīng)算法，最壞適應(yīng)算法以及回收算法。二、 設(shè)計(jì)目的：通過(guò)課程設(shè)計(jì)，進(jìn)一步理解內(nèi)存分配算法的思想，并在此基礎(chǔ)上熟練編程語(yǔ)言的具體的操作。三、 設(shè)計(jì)思想：內(nèi)存管理有空區(qū)表管理空閑得空間，空區(qū)表記錄某個(gè)空閑塊的大小和首地址信息，建立空區(qū)表的雙向鏈表，對(duì)空區(qū)鏈表的操作達(dá)到內(nèi)存分配的管理。四、 設(shè)計(jì)方案：建立空

2、區(qū)表的雙向鏈表結(jié)構(gòu)，建立已分配表的雙向鏈表結(jié)構(gòu)；分別建立最先適應(yīng)、循環(huán)最先適應(yīng)、最佳適應(yīng)和最差適應(yīng)得類結(jié)構(gòu)；采用c+builder作界面設(shè)計(jì)；設(shè)計(jì)界面如下：五、 核心代碼： 作業(yè)數(shù)據(jù)類型的定義#ifndef job_h#define job_htypedef struct job int size;/作業(yè)大小 int address;/作業(yè)首地址 ansistring name;/作業(yè)名(ansistring是c+builder的字符串類型)job;#endif 最先適應(yīng)算法的代碼：#ifndef firstfit_h#define firstfit_h#include "job.h

3、"/最先適應(yīng)算法頭文件class first_fit_link;class linknodefriend class first_fit_link;private: int size;/作業(yè)大小 int address;/作業(yè)首地址 linknode * forward; linknode * next;public: linknode(int s,int a,linknode * f,linknode * n)/初始化 size=s; address=a; forward=f; next=n; ;class first_fit_linkprivate: linknode * hea

4、d;/頭指針 linknode * rear;/尾指針 linknode * work;/標(biāo)記指針public: first_fit_link()/初始化 head=null; rear=null; work=null; first_fit_link()/析構(gòu)函數(shù) linknode * point1; while(head!=null) point1=head; head=head->next; delete point1; void init(int address,int size);/初始化建空區(qū)表 job returnjob();/返回鏈表元素 int allot(int siz

5、e);/分配,成功返回地址，否則返回?zé)o窮大 void free(int address,int size);/釋放 bool over();/判斷是否輸出完節(jié)點(diǎn)元素;/空區(qū)表的建立void first_fit_link:init(int address,int size) if(head=null)/如果是空鏈，新建一個(gè)鏈 head=rear=work=new linknode(size,address,null,null);/申請(qǐng)新的節(jié)點(diǎn) else linknode * point1=head; linknode * point2; while(point1!=null) if(addres

6、s<point1->address) point2=new linknode(size,address,null,null); if(point1=head)/如果是首部，則改動(dòng)頭指針 point2->next=head; head->forward=point2; head=point2; work=point2; else/如果插入點(diǎn)在鏈中 point2->forward=point1->forward; point2->next=point1; point1->forward->next=point2; point1->forw

7、ard=point2; break;/插入完成，退出 else point1=point1->next;/尋找下一個(gè)位置 if(point1=null)/如果插入點(diǎn)在鏈尾，改動(dòng)尾指針 point2=new linknode(size,address,rear,null); rear->next=point2; rear=point2; /分配函數(shù)，如果分配成功，返回作業(yè)地址，否則返回1000int first_fit_link:allot(int size) int address=1000; linknode * point1=head; linknode * point2; w

8、hile(point1!=null) if(size<point1->size)/如果申請(qǐng)空間小于該節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)改動(dòng) address=point1->address; point1->size=point1->size-size; point1->address=point1->address+size; return address;/分配成功，返回address if(size=point1->size)/如果申請(qǐng)空間與該節(jié)點(diǎn)大小一致，刪除該節(jié)點(diǎn) if(point1=head)/如果是頭節(jié)點(diǎn) address=head->address

9、; point2=head; head=head->next; head->forward=null; work=head; delete point2; return address;/分配成功，返回address if(point1=rear)/如果是尾節(jié)點(diǎn) address=rear->address; point2=rear; rear=rear->forward; rear->next=null; delete point2; return address;/分配成功，返回address if(point1!=head&&point1!=r

10、ear) address=point1->address; point2=point1->forward; linknode * point3=point1->next; point2->next=point3; point3->forward=point2; delete point1; return address;/分配成功，返回address point1=point1->next;/尋找下一個(gè)位置 if(point1=null) return address;/沒(méi)有合適的空間，分配不成功，返回1000 /釋放空間函數(shù)void first_fit_l

11、ink:free(int address,int size) linknode * point1=head; linknode * point2; while(point1!=null) if(address<point1->address) if(point1=head)/如果point1是頭指針 if(address+size)=point1->address) head->address=address; head->size=head->size+size; break; else point2=new linknode(size,address,n

12、ull,head); head->forward=point2; head=point2; break; if(point1->forward->address+point1->forward->size)=address)/如果與前一個(gè)相鄰 if(address+size)=point1->address)/如果同時(shí)與后一個(gè)相鄰, 合并三者，刪除point1 point2=point1->forward; point2->size=point2->size+size+point1->size; if(point1=rear)/如果p

13、oint1是尾指針 rear=point2; delete point1; break; else point2->next=point1->next; point1->next->forward=point2; delete point1; break; else /只與前一個(gè)相鄰，則與前一個(gè)合并 point1->forward->size=point1->forward->size+size; break; if(address+size)=point1->address)/如果與后一個(gè)相鄰 point1->size=point1

14、->size+size;/與后一個(gè)合并 break; /如果前后都不相鄰，申請(qǐng)新的節(jié)點(diǎn) point2=new linknode(size,address,point1->forward,point1); point1->forward->next=point2; point1->forward=point2; point1=point1->next; if(point1=null)/ if(rear->address+rear->size)=address)/如果與rear相鄰 rear->size=rear->size+size;

15、else /另立新的rear point2=new linknode(size,address,rear,null); rear->next=point2; rear=point2; /判斷是否輸出完節(jié)點(diǎn)bool first_fit_link:over() if(work=null) work=head; return true; else return false; /返回鏈表元素job first_fit_link:returnjob() linknode * point1=work; job pointnum; if(point1!=null) pointnum.size=poin

16、t1->size; pointnum.address=point1->address; work=work->next; return pointnum;#endif最佳適應(yīng)算法代碼#ifndef bestfit_h#define bestfit_h#include "job.h"/最佳適應(yīng)算法頭文件class bestfit_link;class bestnode friend class bestfit_link;private: int size;/作業(yè)大小 int address;/作業(yè)首地址 bestnode * forward; bestnod

17、e * next;public: bestnode(int s,int a,bestnode * f,bestnode * n)/初始化 size=s; address=a; forward=f; next=n; ;class bestfit_linkprivate: bestnode * head;/頭指針 bestnode * rear;/尾指針 bestnode * work;/標(biāo)記指針public: bestfit_link()/初始化 head=null; rear=null; work=null; bestfit_link()/析構(gòu)函數(shù) bestnode * point1; whi

18、le(head!=null) point1=head; head=head->next; delete point1; void init(int address,int size);/初始化建空區(qū)表 job returnjob();/返回鏈表元素 bool over();/判斷是否輸出完節(jié)點(diǎn)元素 int allot(int size);/分配;/分配函數(shù)，如果分配成功，返回作業(yè)地址，否則返回1000int bestfit_link:allot(int size) int address=1000; bestnode * point1=head; bestnode * point2; w

19、hile(point1!=null) if(size<point1->size)/如果申請(qǐng)空間小于該節(jié)點(diǎn)，對(duì)該節(jié)點(diǎn)改動(dòng) address=point1->address; point1->size=point1->size-size; point1->address=point1->address+size; return address;/分配成功，返回address if(size=point1->size)/如果申請(qǐng)空間與該節(jié)點(diǎn)大小一致，刪除該節(jié)點(diǎn) if(point1=head)/如果是頭節(jié)點(diǎn) address=head->address

20、; point2=head; head=head->next; head->forward=null; work=head; delete point2; return address;/分配成功，返回address if(point1=rear)/如果是尾節(jié)點(diǎn) address=rear->address; point2=rear; rear=rear->forward; rear->next=null; delete point2; return address;/分配成功，返回address if(point1!=head&&point1!=r

21、ear) address=point1->address; point2=point1->forward; bestnode * point3=point1->next; point2->next=point3; point3->forward=point2; delete point1; return address;/分配成功，返回address point1=point1->next;/尋找下一個(gè)位置 if(point1=null) return address;/沒(méi)有合適的空間，分配不成功，返回1000 /按空間大小遞增建立鏈表void bestfi

22、t_link:init(int address,int size) if(head=null) head=rear=work=new bestnode(size,address,null,null); else bestnode * point1=head; bestnode * point2; while(point1!=null) if(size<=point1->size) point2=new bestnode(size,address,null,null); if(point1=head)/如果是首部，則改動(dòng)頭指針 point2->next=head; head-&

23、gt;forward=point2; head=point2; work=point2; else/如果插入點(diǎn)在鏈中 point2->forward=point1->forward; point2->next=point1; point1->forward->next=point2; point1->forward=point2; break;/插入完成，退出 else point1=point1->next;/尋找下一個(gè)位置 if(point1=null)/如果插入點(diǎn)在鏈尾，改動(dòng)尾指針 point2=new bestnode(size,address,rear,null); rear->next=point2; rear=point2; /判斷是否輸出完節(jié)點(diǎn)bool bestfit_link:over() if(work=null) work=head; return true; else return false; /返回鏈表元素job bestfit_link:returnjob() bestnode * point1=work; job