模擬設(shè)計頁式存儲管理的分配與回收

1、題 目: 模擬設(shè)計頁式存儲管理的分配與回收1需求分析頁式管理是一種內(nèi)存空間存儲管理的技術(shù)，頁式管理分為靜態(tài)頁式管理和動態(tài)頁式管理。基本原理是將各進(jìn)程的虛擬空間劃分成若干個長度相等的頁(page)，頁式管理把內(nèi)存空間按頁的大小劃分成片或者頁面（page frame），然后把頁式虛擬地址與內(nèi)存地址建立一一對應(yīng)頁表，并用相應(yīng)的硬件地址變換機(jī)構(gòu)，來解決離散地址變換問題。頁式管理采用請求調(diào)頁或預(yù)調(diào)頁技術(shù)實現(xiàn)了內(nèi)外存存儲器的統(tǒng)一管理。 圖1 頁的劃分圖2 基本頁表示例靜態(tài)分頁管理的第一步是為要求內(nèi)存的作業(yè)或進(jìn)程分配足夠的頁面。系統(tǒng)通過存儲頁面表、請求表以及頁表來完成內(nèi)存的分配工作。頁表指的是內(nèi)存中的一塊固

2、定存儲區(qū)。頁式管理時每個進(jìn)程至少有一個頁表。請求表指的是用來確定作業(yè)或進(jìn)程的虛擬空間的各頁在內(nèi)存中的實際對應(yīng)位置；另外整個系統(tǒng)有一個存儲頁面表，其描述了物理內(nèi)存空間的分配使用狀況。圖3 請求表的示例存儲頁面表有兩種構(gòu)成方法：1、位示圖法2、空閑頁面鏈表法模擬設(shè)計頁式存儲管理的分配與回收要求能夠滿足如下的要求:(1) 輸入給定的內(nèi)存頁面數(shù)，頁面大小，進(jìn)程的個數(shù)及每個進(jìn)程的頁數(shù)。(2) 要求當(dāng)某進(jìn)程提出申請空間的大小后，顯示能否滿足申請，以及為該進(jìn)程分配資源后內(nèi)存空間的使用情況（被進(jìn)程占用的頁面，空閑的頁面）。2 功能設(shè)計2.1 算法分析首先，請求表給出進(jìn)程或作業(yè)要求的頁面數(shù)。然后，由存儲頁面表檢

3、查是否有足夠的空閑頁面，如果沒有，則本次無法分配。如果有則首先分配設(shè)置頁表，并請求表中的相應(yīng)表項后，按一定的查找算法搜索出所要求的空閑頁面，并將對應(yīng)的頁好填入頁表中。 圖4 分配頁面的算法流程2.2 數(shù)據(jù)結(jié)構(gòu)頁式管理把內(nèi)存空間按頁的大小劃分成片或者頁面,再按照一定的規(guī)律建立起頁表,并通過請求表將分配內(nèi)容顯示出來.將頁表和請求表的內(nèi)容使用結(jié)構(gòu)體來定義是比較方便的. /頁表項結(jié)構(gòu) typedef struct _pagetableitempageid pagenum;/頁號blockid blocknum;/塊號pgtabitem;/頁表typedef pgtabitem * pagetable;

4、/請求表結(jié)構(gòu)typedef struct _reqtableunsigned pid;/進(jìn)程號unsigned reqpagenum;/請求頁面數(shù)pagetable pgtabadr; /頁表始址bool state;/狀態(tài) reqtabitem;請求表還引入了支持快速插入和刪除的list順序容器來進(jìn)行相關(guān)操作.list<reqtabitem> reqtable因為模擬設(shè)計的關(guān)系,頁面的起始地址均應(yīng)該為隨機(jī)的數(shù)值,所以程序在設(shè)計過程中加入了隨機(jī)數(shù)類的編寫.class RandomNumberprivate: unsigned long randseed;public: Random

5、Number(unsigned long s=0); unsigned short Random(unsigned long n); double fRandom(void);采用當(dāng)前系統(tǒng)的時間值來生成偽隨機(jī)數(shù)分配地址.定義隨機(jī)數(shù)產(chǎn)生器:RandomNumber random 定義內(nèi)存頁面數(shù):int pagenum 定義頁面大小:int pagesize定義進(jìn)程個數(shù):int pnum用整數(shù)數(shù)組模擬分配的內(nèi)存頁面數(shù)int * mempage=new intpagenum2.3模塊說明2.3.1 主函數(shù)主函數(shù)依次運行了程序中所實現(xiàn)的關(guān)鍵函數(shù). int main() InitSys(); /初始化系

6、統(tǒng) MainChoice();/輸出系統(tǒng)菜單 Destroy(); /釋放申請的動態(tài)內(nèi)存 return 0;2.3.2 各個功能函數(shù) 初始化內(nèi)存頁面: void Init_Mempage(void)獲取內(nèi)存使用情況: int Get_Mempagenum(void)初始化默認(rèn)的請求表: void Init_Reqtable(void)為默認(rèn)的進(jìn)程分配內(nèi)存: void Init_DistMem(void)手動創(chuàng)建進(jìn)程,并分配內(nèi)存: void Dist_Mem(void)釋放申請的動態(tài)內(nèi)存: void Destroy(void)結(jié)束指定進(jìn)程: void Kill(void) 2.3.3 打印函數(shù)

7、打印出進(jìn)程請求表: void PrintReqtable(void) 打印出頁表: void PrintPageTable(void) 打印出內(nèi)存使用情況: void PrintMem(void) 打印出物理塊的大小: void PrintBlockSize(void)2.3.4 其他函數(shù) 初始化系統(tǒng): void InitSys(void)輸出主菜單: void MainMenu(void) 選擇運行分支:void MainChoice() 3開發(fā)平臺3.1開發(fā)平臺(1) 使用系統(tǒng)：Windows 7(2) 使用語言：C+(3) 開發(fā)工具：Visual C+ 20084測試用例，運行結(jié)果與運行

8、情況分析4.1測試方法 通過輸入正常數(shù)據(jù)以及非正常數(shù)據(jù)對程序進(jìn)行全方位測試4.2測試結(jié)果(1)程序主界面(2)輸入進(jìn)程號和頁面數(shù):(3)顯示進(jìn)程頁表:(4)顯示請求表(5)顯示內(nèi)存使用情況以及物理塊大小(6)錯誤檢驗5源程序的主要部分#include <iostream>#include <cstdlib>#include <iomanip>#include <list>#include "page.h"#include "Random.h"using namespace std;list<reqta

9、bitem> reqtable;RandomNumber random; /隨機(jī)數(shù)產(chǎn)生器unsigned pagenum=random.Random(80)+21; /內(nèi)存頁面數(shù)21-100unsigned pagesize=random.Random(16)+5; /頁面大小5-20 unsigned pnum=random.Random(4)+5;/進(jìn)程的個數(shù)5-8int * mempage=new intpagenum; /用整數(shù)數(shù)組模擬內(nèi)存頁面數(shù)/*初始化內(nèi)存頁面*/void Init_Mempage(void)int i=0;for(i=0;i<int(pagenum);

10、i+)mempagei=0; /數(shù)組全部賦初值/*獲取內(nèi)存的使用情況*/int Get_Mempagenum(void)int sum=0;for(int i=0;i<int(pagenum);i+)if(mempagei=0)sum+;return sum; /判斷有多少內(nèi)存頁面已經(jīng)被使用/*初始化默認(rèn)的請求表*/void Init_Reqtable(void)int i;for(i=1;i<=int(pnum);i+)reqtabitem preq;preq.pid=i;preq.reqpagenum=random.Random(4)+2;/進(jìn)程請求的頁面大小-5preq.st

11、ate=false;preq.pgtabadr=NULL;reqtable.push_back(preq); /依次壓入容器 /*為默認(rèn)的進(jìn)程分配內(nèi)存*/void Init_DistMem(void)int reqpnum;/進(jìn)程請求頁面數(shù)int i;list<reqtabitem>:iterator pos=reqtable.begin();for(;pos!=reqtable.end();pos+)reqpnum=(*pos).reqpagenum;if(reqpnum>int(Get_Mempagenum()/判斷請求的內(nèi)存頁面數(shù)目是否大于剩余的cout<<

12、"沒有足夠的內(nèi)存!"<<endl; cout<<endl; else(*pos).state=true;pagetable temp = new pgtabitemreqpnum; /新建臨時頁表項數(shù)組if(temp=NULL)cout<<"內(nèi)存分配失敗!"<<endl;exit(0);(*pos).pgtabadr=temp;for(i=0;i<reqpnum;i+)tempi.pagenum=i;/頁表的頁號int randnum=random.Random(pagenum)+1;/隨機(jī)產(chǎn)生一個塊

13、號while(mempagerandnum=1)randnum=random.Random(pagenum)+1;tempi.blocknum=randnum;/頁表的塊號mempagerandnum=1;/*手動創(chuàng)建進(jìn)程,并分配內(nèi)存*/void Dist_Mem(void)int i;reqtabitem preq;/新創(chuàng)建進(jìn)程記錄int pid;/進(jìn)程號int reqpnum;/請求頁面數(shù)bool flag=false;docout<<"請輸入進(jìn)程號:"flag=false;cin>>pid;for(list<reqtabitem>:

14、iterator pos=reqtable.begin();pos!=reqtable.end();pos+)if(*pos).pid=pid)flag=true;cout<<"該進(jìn)程號已經(jīng)存在,請重新輸入"<<endl;cout<<endl;break;while(flag=true); /循環(huán)直到輸入的Pid滿足條件preq.pid=pid;cout<<"請輸入需要的頁面數(shù):"cin>>reqpnum;preq.reqpagenum=reqpnum;preq.state=false;preq

15、.pgtabadr=NULL;reqpnum=preq.reqpagenum;if(reqpnum>Get_Mempagenum()cout<<"沒有足夠的內(nèi)存,進(jìn)程創(chuàng)建失敗!"<<endl; cout<<endl;elsepreq.state=true;pagetable temp = new pgtabitemreqpnum;if(temp=NULL)cout<<"內(nèi)存分配失敗!"<<endl;exit(0);preq.pgtabadr=temp;for(i=0;i<int(re

16、qpnum);i+)tempi.pagenum=i;/頁表的頁號int randnum=random.Random(pagenum)+1;/隨機(jī)產(chǎn)生一個塊號while(mempagerandnum=1)randnum=random.Random(pagenum)+1;tempi.blocknum=randnum;/頁表的塊號mempagerandnum=1;reqtable.push_back(preq);/將該進(jìn)程的記錄加入請求表/*程序結(jié)束時,釋放申請的動態(tài)內(nèi)存*/void Destroy(void)list<reqtabitem>:iterator pos=reqtable.

17、begin();for(pos=reqtable.begin();pos!=reqtable.end();pos+)if(*pos).state=true)delete (*pos).pgtabadr;reqtable.clear();/* 打印出進(jìn)程請求表*/void PrintReqtable(void) cout<<endl; cout<<"|-|"<<endl; cout<<"| 進(jìn)程請求表 |"<<endl; cout<<"|-|"<<end

18、l; cout<<"|"<<setw(8)<<"進(jìn)程號" <<setw(16)<<"請求頁面數(shù)" <<setw(16)<<"頁表起始地址" <<setw(16)<<"頁表長度" <<setw(16)<<"狀態(tài) |"<<endl; cout<<"|-|"<<endl; list<reqt

19、abitem>:iterator pos=reqtable.begin(); for(pos=reqtable.begin();pos!=reqtable.end();pos+) cout<<"|"<<setw(8)<<(*pos).pid<<setw(16)<<(*pos).reqpagenum<<setw(16)<<(*pos).pgtabadr<<setw(16)<<(*pos).reqpagenum) * pagesize;if(*pos).state)

20、cout<<setw(4)<<"已分配 |"<<endl;else cout<<setw(4)<<"未分配 |"<<endl;if(*pos).pid!=reqtable.back().pid)cout<<"|-|"<<endl;elsecout<<"|-|"<<endl; /*打印頁表*/void PrintPageTable(void) unsigned pid; int i; bool fl

21、ag=false; cout<<"請輸入進(jìn)程號:" cin>>pid; list<reqtabitem>:iterator pos=reqtable.begin(); for(pos=reqtable.begin();pos!=reqtable.end();pos+) if(*pos).pid=pid&&(*pos).state=true) flag=true;cout<<"|-|"<<endl;cout<<"| 此進(jìn)程的頁表 |"<<

22、endl;cout<<"|-|"<<endl;cout<<"|"<<setw(16)<<"頁號"<<setw(6)<<"塊號 |"<<endl;cout<<"|-|"<<endl;int reqpagenum=(*pos).reqpagenum;for(i=0;i<reqpagenum;i+)cout<<"|"<<setw(16

23、)<<(*pos).pgtabadri.pagenum<<setw(6)<<(*pos).pgtabadri.blocknum<<" |"<<endl;if(i!=reqpagenum-1)cout<<"|-|"<<endl;elsecout<<"|-|"<<endl; if(flag=false) cout<<"系統(tǒng)中不存在該進(jìn)程或者該進(jìn)程還沒有被分配內(nèi)存!n" cout<<endl

24、;void PrintMem(void)cout<<"內(nèi)存總塊數(shù)為"<<pagenum<<",已經(jīng)使用了"<<pagenum-Get_Mempagenum()<<"塊!"<<endl;cout<<"現(xiàn)在還有"<<Get_Mempagenum()<<"塊內(nèi)存區(qū)域空閑!"<<endl;cout<<endl;void PrintBlockSize(void)cout<

25、;<"物理塊大小為:"<<pagesize<<"KB"<<endl;cout<<endl;/*結(jié)束指定進(jìn)程*/void Kill(void)bool flag;int i;reqtabitem temp;list<reqtabitem>:iterator pos=reqtable.begin();int pid;docout<<"請輸入進(jìn)程號:"flag=false;cin>>pid;for(pos=reqtable.begin();pos!=r

26、eqtable.end();pos+)if(*pos).pid=pid)flag=true;temp=*pos;break;if(flag=false)cout<<"系統(tǒng)中不存在該進(jìn)程!"<<endl; cout<<endl;while(flag=false);for(i=0;i<int(temp.reqpagenum);i+)mempagetemp.pgtabadri.blocknum=0;reqtable.remove(temp);/重新為沒有分配到內(nèi)存的進(jìn)程分配內(nèi)存for(pos=reqtable.begin();pos!=r

27、eqtable.end();pos+)if(*pos).state=false)int reqpnum;reqpnum=(*pos).reqpagenum;if(reqpnum<=Get_Mempagenum()(*pos).state=true;pagetable temp = new pgtabitemreqpnum;if(temp=NULL)cout<<"內(nèi)存分配失敗!"<<endl;cout<<endl;exit(0);(*pos).pgtabadr=temp;for(i=0;i<int(reqpnum);i+)tem

28、pi.pagenum=i;/頁表的頁號int randnum=random.Random(pagenum)+1;/隨機(jī)產(chǎn)生一個塊號while(mempagerandnum=1)randnum=random.Random(pagenum)+1;tempi.blocknum=randnum;/頁表的塊號mempagerandnum=1;/*初始化系統(tǒng)*/void InitSys(void)cout.setf(ios:left);/左對齊Init_Mempage();Init_Reqtable();Init_DistMem();/*輸出主菜單*/void MainMenu(void) cout<

29、;<"頁式存儲管理的分配與回收"<<endl; cout<<"1.手動創(chuàng)建進(jìn)程"<<endl; cout<<"2.顯示進(jìn)程頁表"<<endl; cout<<"3.顯示請求表"<<endl; cout<<"4.撤銷進(jìn)程"<<endl; cout<<"5.顯示內(nèi)存使用情況"<<endl; cout<<"6.顯示物理塊大小"<<endl; cout<<"7.退出系統(tǒng)"<<endl; cout<<"請輸入您的選擇(0-7):"/*選擇函數(shù)*/void MainChoice()int choice;do MainMenu(); cin>>choice; swi