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

1、學(xué) 號： 課 程 設(shè) 計題 目模擬設(shè)計頁式存儲管理的分配與回收學(xué) 院計算機(jī)科學(xué)與技術(shù)專 業(yè)班 級姓 名指導(dǎo)教師吳利軍2013年01月09日課程設(shè)計任務(wù)書學(xué)生姓名： 指導(dǎo)教師： 吳利軍 工作單位： 計算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 模擬設(shè)計頁式存儲管理的分配與回收初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，理解有關(guān)虛擬存儲器、頁式存儲管理等概念，掌握頁式管理內(nèi)存的分配和回收過程。2實踐準(zhǔn)備：掌握一種計算機(jī)高級語言的使用。要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1采用頁式管理方案實施內(nèi)存分配和回收。能夠處理以下的情形 能夠輸入給定的內(nèi)存頁面數(shù)，頁面

2、大小，進(jìn)程的個數(shù)及每個進(jìn)程的頁數(shù)。 當(dāng)某進(jìn)程提出申請空間的大小后，顯示能否滿足申請，以及為該進(jìn)程分配資源后內(nèi)存空間的使用情況（被進(jìn)程占用的頁面，空閑的頁面）； 當(dāng)某進(jìn)程撤消時，顯示內(nèi)存回收后內(nèi)存空間的使用情況。2設(shè)計報告內(nèi)容應(yīng)說明： 需求分析； 功能設(shè)計（數(shù)據(jù)結(jié)構(gòu)及模塊說明）； 開發(fā)平臺及源程序的主要部分； 測試用例，運行結(jié)果與運行情況分析； 自我評價與總結(jié)：i）你認(rèn)為你完成的設(shè)計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓(xùn)）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；時間安排：設(shè)計安排一周

3、：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收、撰寫課程設(shè)計報告。（注意事項：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日模擬設(shè)計頁式存儲管理的分配與回收1需求分析頁式管理是一種內(nèi)存空間存儲管理的技術(shù)，頁式管理分為靜態(tài)頁式管理和動態(tài)頁式管理?；驹硎菍⒏鬟M(jìn)程的虛擬空間劃分成若干個長度相等的頁，頁式管理把內(nèi)存空間按頁的大小劃分成片或者頁面，然后把頁式虛擬地址與內(nèi)存地址建立一一對應(yīng)頁表，并用相應(yīng)的硬件地址變換機(jī)構(gòu)，來解決離散地址變換問題。頁式管理采用請求調(diào)頁或預(yù)調(diào)頁技術(shù)實現(xiàn)了內(nèi)外存存儲器的統(tǒng)一管理。 頁號P

4、 位移量W 圖1 頁的劃分 頁號 塊號圖2 基本頁表示例靜態(tài)分頁管理的第一步是為要求內(nèi)存的作業(yè)或進(jìn)程分配足夠的頁面。系統(tǒng)通過存儲頁面表、請求表以及頁表來完成內(nèi)存的分配工作。頁表指的是內(nèi)存中的一塊固定存儲區(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)程提出申

5、請空間的大小后，顯示能否滿足申請，以及為該進(jìn)程分配資源后內(nèi)存空間的使用情況（被進(jìn)程占用的頁面，空閑的頁面）。2 功能設(shè)計2.1 算法分析首先，請求表給出進(jìn)程或作業(yè)要求的頁面數(shù)。然后，由存儲頁面表檢查是否有足夠的空閑頁面，如果沒有，則本次無法分配。如果有則首先分配設(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 stru

6、ct _pagetableitempageid pagenum;/頁號blockid blocknum;/塊號pgtabitem;/頁表typedef pgtabitem * pagetable;/請求表結(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)系,頁面的起

7、始地址均應(yīng)該為隨機(jī)的數(shù)值,所以程序在設(shè)計過程中加入了隨機(jī)數(shù)類的編寫.class RandomNumberprivate: unsigned long randseed;public: RandomNumber(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ù)組模擬分配

8、的內(nèi)存頁面數(shù)int * mempage=new intpagenum2.3模塊說明2.3.1 主函數(shù)主函數(shù)依次運行了程序中所實現(xiàn)的關(guān)鍵函數(shù). int main() InitSys(); /初始化系統(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

9、)手動創(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ù) 打印出進(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) 選擇運行

10、分支:void MainChoice() 3開發(fā)平臺3.1開發(fā)平臺(1) 使用系統(tǒng)：Windows 7(2) 使用語言：C+(3) 開發(fā)工具：Visual C+ 6.04測試用例，運行結(jié)果與運行情況分析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 <

11、list>#include "page.h"#include "Random.h"using namespace std;list<reqtabitem> 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=

12、new intpagenum; /用整數(shù)數(shù)組模擬內(nèi)存頁面數(shù)void Init_Mempage(void)int i=0;for(i=0;i<int(pagenum);i+)mempagei=0; /數(shù)組全部賦初值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)被使用void Init_Reqtable(void)int i;for(i=1;i<=int(pnum);i+)reqtabitem preq;preq.

13、pid=i;preq.reqpagenum=random.Random(4)+2;/進(jìn)程請求的頁面大小-5preq.state=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(re

14、qpnum>int(Get_Mempagenum()/判斷請求的內(nèi)存頁面數(shù)目是否大于剩余的cout<<"沒有足夠的內(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.p

15、agenum=i;/頁表的頁號int randnum=random.Random(pagenum)+1;/隨機(jī)產(chǎn)生一個塊號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)程號

16、:"flag=false;cin>>pid;for(list<reqtabitem>: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&

17、gt;>reqpnum;preq.reqpagenum=reqpnum;preq.state=false;preq.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)存分配失敗!"

18、;<<endl;exit(0);preq.pgtabadr=temp;for(i=0;i<int(reqpnum);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)存*/voi

19、d Destroy(void)list<reqtabitem>:iterator pos=reqtable.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)程請求表

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

21、;endl; cout<<"|-|"<<endl; list<reqtabitem>: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<<s

22、etw(16)<<(*pos).reqpagenum) * pagesize;if(*pos).state)cout<<setw(4)<<"已分配 |"<<endl;else cout<<setw(4)<<"未分配 |"<<endl;if(*pos).pid!=reqtable.back().pid)cout<<"|-|"<<endl;elsecout<<"|-|"<<endl; /*

23、打印頁表*/void PrintPageTable(void) unsigned pid; int i; bool flag=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<<"|-|&

24、quot;<<endl;cout<<"| 此進(jìn)程的頁表 |"<<endl;cout<<"|-|"<<endl;cout<<"|"<<setw(16)<<"頁號"<<setw(6)<<"塊號 |"<<endl;cout<<"|-|"<<endl;int reqpagenum=(*pos).reqpagenum;for(i=0

25、;i<reqpagenum;i+)cout<<"|"<<setw(16)<<(*pos).pgtabadri.pagenum<<setw(6)<<(*pos).pgtabadri.blocknum<<" |"<<endl;if(i!=reqpagenum-1)cout<<"|-|"<<endl;elsecout<<"|-|"<<endl; if(flag=false) cout&

26、lt;<"系統(tǒng)中不存在該進(jìn)程或者該進(jìn)程還沒有被分配內(nèi)存!n" cout<<endl;void PrintMem(void)cout<<"內(nèi)存總塊數(shù)為"<<pagenum<<",已經(jīng)使用了"<<pagenum-Get_Mempagenum()<<"塊!"<<endl;cout<<"現(xiàn)在還有"<<Get_Mempagenum()<<"塊內(nèi)存區(qū)域空閑!"&l

27、t;<endl;cout<<endl;void PrintBlockSize(void)cout<<"物理塊大小為:"<<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)程號:&qu

28、ot;flag=false;cin>>pid;for(pos=reqtable.begin();pos!=reqtable.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.re

29、move(temp);/重新為沒有分配到內(nèi)存的進(jìn)程分配內(nèi)存for(pos=reqtable.begin();pos!=reqtable.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;e

30、xit(0);(*pos).pgtabadr=temp;for(i=0;i<int(reqpnum);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;/*初始化系統(tǒng)*/void InitSys(void)cout.setf(ios:left);/左對齊Init_Mempage();Init_Re

31、qtable();Init_DistMem();/*輸出主菜單*/void MainMenu(void) cout<<"頁式存儲管理的分配與回收"<<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(); c