模擬設(shè)計(jì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理的分配與回收

學(xué)號(hào)：課程設(shè)計(jì)題目模擬設(shè)計(jì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理的分配與回收學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)姓名指導(dǎo)教師2011年01月20日課程設(shè)計(jì)任務(wù)書學(xué)生姓名：專業(yè)班級(jí)：計(jì)算機(jī)指導(dǎo)教師：工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院題目:模擬設(shè)計(jì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理的分配與回收初始條件：1．預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，理解動(dòng)態(tài)分區(qū)的思想，并體會(huì)動(dòng)態(tài)分區(qū)主存的分配的具體實(shí)施方法。2．實(shí)踐準(zhǔn)備：掌握一種計(jì)算機(jī)高級(jí)語言的使用。要求完成的主要任務(wù):〔包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求〕1．采用動(dòng)態(tài)分區(qū)管理方案實(shí)施內(nèi)存分配和回收。能夠處理以下的情形⑴能夠輸入給定的內(nèi)存大小，進(jìn)程的個(gè)數(shù)，每個(gè)進(jìn)程所需內(nèi)存空間的大??；⑵當(dāng)某進(jìn)程提出申請(qǐng)空間的大小后，顯示能否滿足申請(qǐng)，以及為該進(jìn)程分配資源后有關(guān)內(nèi)存空間使用的情況；⑶當(dāng)某進(jìn)程撤消時(shí)，顯示內(nèi)存回收后內(nèi)存空間的使用情況。能夠處理以下的情形：主存回收函數(shù)實(shí)現(xiàn)：有上鄰空閑區(qū)和下鄰空閑區(qū)，它們與回收區(qū)的合并；有上鄰空閑區(qū)，無下鄰空閑區(qū)，回收區(qū)與上鄰空閑區(qū)的合并；無上鄰空閑區(qū)，有下鄰空閑區(qū)，回收區(qū)與下鄰空閑區(qū)的合并。2．設(shè)計(jì)報(bào)告內(nèi)容應(yīng)說明：⑴課程設(shè)計(jì)目的與功能；⑵需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明(功能與框圖)；⑶源程序的主要局部；⑷測(cè)試用例，運(yùn)行結(jié)果與運(yùn)行情況分析；⑸自我評(píng)價(jià)與總結(jié)：=1\*romani〕你認(rèn)為你完成的設(shè)計(jì)哪些地方做得比擬好或比擬出色；=2\*romanii〕什么地方做得不太好，以后如何改正；=3\*romaniii〕從本設(shè)計(jì)得到的收獲〔在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗(yàn)和教訓(xùn)〕；=4\*romaniv〕完成此題是否有其他的其他方法〔如果有，簡(jiǎn)要說明該方法〕；=5\*romanv〕對(duì)實(shí)驗(yàn)題的評(píng)價(jià)和改良意見，請(qǐng)你推薦設(shè)計(jì)題目。時(shí)間安排：設(shè)計(jì)安排一周：周1、周2：完成程序分析及設(shè)計(jì)。周2、周3：完成程序調(diào)試及測(cè)試。周4、周5：驗(yàn)收、撰寫課程設(shè)計(jì)報(bào)告?！部记绊氈簢?yán)禁抄襲，一旦發(fā)現(xiàn)，抄與被抄的一律按0分記〕指導(dǎo)教師簽名：年月日系主任〔或責(zé)任教師〕簽名：年月日模擬設(shè)計(jì)動(dòng)態(tài)分區(qū)存儲(chǔ)管理的分配與回收1.課程設(shè)計(jì)目的與功能1.1課程設(shè)計(jì)的目的深入了解動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式的主存分配回收的實(shí)現(xiàn)。1.2課程設(shè)計(jì)的功能1.能夠輸入給定的內(nèi)存大小，進(jìn)程的個(gè)數(shù)，每個(gè)進(jìn)程所需內(nèi)存空間的大?。?.當(dāng)某進(jìn)程提出申請(qǐng)空間的大小后，顯示能否滿足申請(qǐng)，以及為該進(jìn)程分配資源后有關(guān)內(nèi)存空間使用的情況；3.當(dāng)某進(jìn)程撤消時(shí)，顯示內(nèi)存回收后內(nèi)存空間的使用情況。能夠處理以下的情形：主存回收函數(shù)實(shí)現(xiàn)：有上鄰空閑區(qū)和下鄰空閑區(qū)，它們與回收區(qū)的合并；有上鄰空閑區(qū)，無下鄰空閑區(qū)，回收區(qū)與上鄰空閑區(qū)的合并；無上鄰空閑區(qū)，有下鄰空閑區(qū)，回收區(qū)與下鄰空閑區(qū)的合并。2.需求分析，數(shù)據(jù)結(jié)構(gòu)或模塊說明2.1需求分析動(dòng)態(tài)分區(qū)管理方式預(yù)先不將主存劃分成幾個(gè)區(qū)域，而把主存除操作系統(tǒng)占區(qū)域外的空間看作一個(gè)大的空閑區(qū)。當(dāng)作業(yè)要求裝入主存時(shí)，根據(jù)作業(yè)需要的主存空間的大小查詢主存內(nèi)各個(gè)空閑區(qū)，當(dāng)從主存空間中找到一個(gè)大于或等于該作業(yè)大小的主存空閑區(qū)時(shí)，選擇其中一個(gè)空閑區(qū)，按作業(yè)需求量劃出一個(gè)分區(qū)裝入該作業(yè)。作業(yè)執(zhí)行完后，它所占的主存分區(qū)被收回，成為一個(gè)空閑區(qū)。如果該空閑區(qū)的相鄰分區(qū)也是空閑區(qū)，那么需要將相鄰空閑區(qū)合并成一個(gè)空閑區(qū)。實(shí)現(xiàn)動(dòng)態(tài)分區(qū)的分配和回收，主要考慮的問題有三個(gè)：第一，設(shè)計(jì)記錄主存使用情況的數(shù)據(jù)表格，用來記錄空閑區(qū)和作業(yè)占用的區(qū)域；第二，在設(shè)計(jì)的數(shù)據(jù)表格根底上設(shè)計(jì)主存分配算法；第三，在設(shè)計(jì)的數(shù)據(jù)表格根底上設(shè)計(jì)主存回收算法。實(shí)驗(yàn)中主存分配算法采用“最優(yōu)適應(yīng)”算法。最優(yōu)適應(yīng)算法是按作業(yè)要求挑選一個(gè)能滿足作業(yè)要求的最小空閑區(qū)，這樣保證可以不去分割一個(gè)大的區(qū)域，使裝入大作業(yè)時(shí)比擬容易得到滿足。但是最優(yōu)適應(yīng)算法容易出現(xiàn)找到的一個(gè)分區(qū)可能只比作業(yè)所要求的長(zhǎng)度略大一點(diǎn)的情況，這時(shí)，空閑區(qū)分割后剩下的空閑區(qū)就很小，這種很小的空閑區(qū)往往無法使用，卻影響了主存的使用。為了一定程度上解決這個(gè)問題，如果空閑區(qū)的大小比作業(yè)要求的長(zhǎng)度略大一點(diǎn)，不再將空閑區(qū)分成已分分區(qū)和空閑區(qū)兩局部，而是將整個(gè)空閑區(qū)分配給作業(yè)。在實(shí)現(xiàn)最優(yōu)適應(yīng)算法時(shí)，可把空閑區(qū)按長(zhǎng)度以遞增方式登記在空閑區(qū)表中。2.2結(jié)構(gòu)說明分區(qū)說明表structPST{//partitionspecificationtableintid;//分區(qū)號(hào)intaddr;//起始地址intsize;//分區(qū)長(zhǎng)度Statusstate;//狀態(tài)};2.1.2雙向鏈structNode{//雙向鏈表結(jié)點(diǎn)PSTdata;Node*back;//前驅(qū)Node*next;//后繼Node(){back=NULL;next=NULL;} Node(intid,intsize) { data.ID=id; data.size=size; back=NULL; next=NULL; }};2.1.3StatusFFA(intid,intsize){//headfitalgorithm Node*temp=newNode(id,size); temp->data.state=BUSY; Node*cur=head->next; while(cur) { if(cur->data.state==FREE&&cur->data.size==size) {//如果空閑塊大小剛好與請(qǐng)求大小相等,直接分配 cur->data.ID=id; cur->data.state=BUSY; returnOK; break; } if(cur->data.state==FREE&&cur->data.size>size) {//如果大于 temp->back=cur->back; temp->next=cur; cur->back->next=temp; temp->data.addr=cur->data.addr; cur->back=temp; cur->data.addr=cur->data.addr+size; cur->data.size=cur->data.size-size; returnOK; break; } cur=cur->next; } returnERROR;}2.1.4StatusBFA(intid,intsize){//bestfitalgorithm Node*temp=newNode(id,size); temp->data.state=BUSY; intmin;//記錄符合滿足請(qǐng)求的最小空閑塊大小 Node*fit;//指向采用最正確適應(yīng)算法的插入位置 Node*cur=head->next; while(cur) {//取得第一個(gè)可以分配的位置〔不一定是最正確位置〕 if(cur->data.state==FREE&&cur->data.size>=size) { fit=cur; min=cur->data.size-size; break; } cur=cur->next; } while(cur) { if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配 cur->data.state=BUSY; cur->data.ID=id; returnOK; break; } if(cur->data.state==FREE&&cur->data.size>size) {//獲取最正確位置 if(cur->data.size-size<min) { min=cur->data.size-size; fit=cur; } } cur=cur->next; } if(fit) {//假設(shè)最正確，插入 temp->back=fit->back; temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp; fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; returnOK; } else returnERROR;}2.1.5StatusWFA(intid,intsize){//worstfitalgorithm Node*temp=newNode(id,size); temp->data.state=BUSY; intmax;//記錄符合滿足請(qǐng)求的最小空閑塊大小 Node*fit;//指向采用最壞適應(yīng)算法的插入位置 Node*cur=head->next; while(cur) {//取得第一個(gè)可以分配的位置〔不一定是最正確位置〕 if(cur->data.state==FREE&&cur->data.size>=size) { fit=cur; max=cur->data.size-size; break; } cur=cur->next; } while(cur) {/* if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配 cur->data.state=BUSY; cur->data.ID=id; returnOK; break; } */ if(cur->data.state==FREE&&cur->data.size>size) {//獲取最正確位置 if(cur->data.size-size>max) { max=cur->data.size-size; fit=cur; } } cur=cur->next; } if(fit) {//假設(shè)最正確，插入 temp->back=fit->back; temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp; fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; returnOK; } else returnERROR;}2.3結(jié)構(gòu)框圖圖13.源程序#include<iostream>usingnamespacestd;//#defineMAX_LEN1024//定義內(nèi)存大小，1024字節(jié)enumStatus{FREE,BUSY,OK,ERROR};structPST{//partitionspecificationtableintID;//分區(qū)號(hào) intaddr;//起始地址intsize;//分區(qū)長(zhǎng)度 Statusstate;//狀態(tài)};structNode{//雙向鏈表結(jié)點(diǎn) PSTdata;Node*back;//前驅(qū)Node*next;//后繼Node() { back=NULL; next=NULL;} Node(intid,intsize) { data.ID=id; data.size=size; back=NULL; next=NULL; }};intarea;//輸入內(nèi)存空間Node*head,*last;voidInit(intarea){ head=newNode();last=newNode(); head->next=last; last->back=head; last->data.addr=0; last->data.ID=0; last->data.size=area;last->data.state=FREE;}StatusFFA(intid,intsize){//headfitalgorithmNode*temp=newNode(id,size); temp->data.state=BUSY; Node*cur=head->next;while(cur){if(cur->data.state==FREE&&cur->data.size==size){//如果空閑塊大小剛好與請(qǐng)求大小相等,直接分配cur->data.ID=id;cur->data.state=BUSY;returnOK;break; } if(cur->data.state==FREE&&cur->data.size>size) {//如果大于temp->back=cur->back;temp->next=cur;cur->back->next=temp;temp->data.addr=cur->data.addr;cur->back=temp;cur->data.addr=cur->data.addr+size;cur->data.size=cur->data.size-size;returnOK;break;} cur=cur->next;} returnERROR;}StatusBFA(intid,intsize){//bestfitalgorithm Node*temp=newNode(id,size);temp->data.state=BUSY;intmin;//記錄符合滿足請(qǐng)求的最小空閑塊大小Node*fit;//指向采用最正確適應(yīng)算法的插入位置Node*cur=head->next;while(cur){//取得第一個(gè)可以分配的位置〔不一定是最正確位置〕if(cur->data.state==FREE&&cur->data.size>=size){fit=cur;min=cur->data.size-size;break; }cur=cur->next; }while(cur) { if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配cur->data.state=BUSY;cur->data.ID=id;returnOK;break; } if(cur->data.state==FREE&&cur->data.size>size){//獲取最正確位置if(cur->data.size-size<min){min=cur->data.size-size;fit=cur;} } cur=cur->next; }if(fit) {//假設(shè)最正確，插入 temp->back=fit->back; temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp;fit->data.addr=fit->data.addr+size; fit->data.size=fit->data.size-size; returnOK; }elsereturnERROR;}StatusWFA(intid,intsize){//worstfitalgorithmNode*temp=newNode(id,size); temp->data.state=BUSY;intmax;//記錄符合滿足請(qǐng)求的最小空閑塊大小 Node*fit;//指向采用最壞適應(yīng)算法的插入位置 Node*cur=head->next; while(cur) {//取得第一個(gè)可以分配的位置〔不一定是最正確位置〕if(cur->data.state==FREE&&cur->data.size>=size){fit=cur;max=cur->data.size-size;break;} cur=cur->next; }while(cur){/*if(cur->data.state==FREE&&cur->data.size==size) {//如果相等直接分配cur->data.state=BUSY;cur->data.ID=id;returnOK;break;}*/if(cur->data.state==FREE&&cur->data.size>size){//獲取最正確位置if(cur->data.size-size>max){max=cur->data.size-size;fit=cur;}}cur=cur->next; } if(fit) {//假設(shè)最正確，插入 temp->back=fit->back;temp->next=fit; fit->back->next=temp; temp->data.addr=fit->data.addr; fit->back=temp; fit->data.addr=fit->data.addr+size;fit->data.size=fit->data.size-size; returnOK;} elsereturnERROR;}voidFree(intid){Node*cur=head;while(cur){if(cur->data.ID==id){cur->data.state=FREE;cur->data.ID=FREE;if(cur->back->data.state==FREE)//與前面的空閑塊相連{cur->back->data.size+=cur->data.size;cur->back->next=cur->next;cur->next->back=cur->back;}if(cur->next->data.state==FREE)//與后面的空閑塊相連{cur->data.size+=cur->next->data.size;cur->next->next->back=cur->back;cur->back->next=cur->next;}break;}cur=cur->next;}}StatusAssign(intchoice){ intid,size; cout<<"請(qǐng)輸入?yún)^(qū)號(hào):"; cin>>id; cout<<endl<<"請(qǐng)輸入分區(qū)長(zhǎng)度(KB):"; cin>>size; if(size<=0) { cout<<"輸入錯(cuò)誤!"<<endl; returnERROR; } if(choice==1) { if(FFA(id,size)==OK) cout<<"分配成功！"<<endl; else cout<<"分配失敗！"<<endl; } elseif(choice==2) { if(BFA(id,size)==OK) cout<<"分配成功！"<<endl; else cout<<"分配失??！"<<endl; } elseif(choice==3) { if(WFA(id,size)==OK) cout<<"分配成功！"<<endl; else cout<<"分配失?。?<<endl; } else returnERROR;}voidShow(){ Node*cur=head->next; while(cur) { cout<<"***********************************"<<endl; cout<<"區(qū)號(hào):"; if(cur->data.ID==FREE) cout<<"無"<<endl; else cout<<cur->data.ID<<endl; cout<<"起始地址:"<<cur->data.addr<<endl; cout<<"分區(qū)長(zhǎng)度:"<<cur->data.size<<endl; cout<<"狀態(tài):"; if(cur->data.state==BUSY) cout<<"已分配"<<endl; else cout<<"未分配"<<endl; cur=cur->next; }}intmain(){ cout<<"動(dòng)態(tài)分區(qū)分配方式的模擬"<<endl; cout<<"********************************************"<<endl; cout<<"請(qǐng)輸入內(nèi)存大小(KB):"; cin>>area; while(area<=0) { cout<<"輸入錯(cuò)誤，請(qǐng)重新輸入內(nèi)存大小(KB)"; cin>>area; } while(1) { cout<<"********************************************"<<endl; cout<<"**1.FFA2.BFA3.WFA0.EXIT**"<<endl; cout<<"********************************************"<<endl; cout<<"請(qǐng)選擇:"; intch; cin>>ch; if(ch==0) { break; } Init(area); intchoice; while(1) { cout<<"********************************************"<<endl; cout<<"**1.分配2.回收3.查看0.退出**"<<endl; cout<<"********************************************"<<endl; cout<<"請(qǐng)輸入您的操作："; cin>>choice; if(choice==1) { cout<<"請(qǐng)輸入進(jìn)程個(gè)數(shù)"; intnum; cin>>num; for(;num>0;num--) {