設計頁式存儲管理的分配與回收

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

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

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

4、 位移量W 圖1 頁的劃分 頁號 塊號圖2 基本頁表示例靜態(tài)分頁管理的第一步是為要求內存的作業(yè)或進程分配足夠的頁面。系統(tǒng)通過存儲頁面表、請求表以及頁表來完成內存的分配工作。頁表指的是內存中的一塊固定存儲區(qū)。頁式管理時每個進程至少有一個頁表。請求表指的是用來確定作業(yè)或進程的虛擬空間的各頁在內存中的實際對應位置；另外整個系統(tǒng)有一個存儲頁面表，其描述了物理內存空間的分配使用狀況。圖3 請求表的示例存儲頁面表有兩種構成方法：1、位示圖法2、空閑頁面鏈表法模擬設計頁式存儲管理的分配與回收要求能夠滿足如下的要求:(1) 輸入給定的內存頁面數，頁面大小，進程的個數及每個進程的頁數。(2) 要求當某進程提出申

5、請空間的大小后，顯示能否滿足申請，以及為該進程分配資源后內存空間的使用情況（被進程占用的頁面，空閑的頁面）。2 功能設計2.1 算法分析首先，請求表給出進程或作業(yè)要求的頁面數。然后，由存儲頁面表檢查是否有足夠的空閑頁面，如果沒有，則本次無法分配。如果有則首先分配設置頁表，并請求表中的相應表項后，按一定的查找算法搜索出所要求的空閑頁面，并將對應的頁好填入頁表中。 圖4 分配頁面的算法流程2.2 數據結構頁式管理把內存空間按頁的大小劃分成片或者頁面,再按照一定的規(guī)律建立起頁表,并通過請求表將分配內容顯示出來.將頁表和請求表的內容使用結構體來定義是比較方便的. /頁表項結構 typedef stru

6、ct _pagetableitempageid pagenum;/頁號blockid blocknum;/塊號pgtabitem;/頁表typedef pgtabitem * pagetable;/請求表結構typedef struct _reqtableunsigned pid;/進程號unsigned reqpagenum;/請求頁面數pagetable pgtabadr; /頁表始址bool state;/狀態(tài) reqtabitem;請求表還引入了支持快速插入和刪除的list順序容器來進行相關操作.list<reqtabitem> reqtable因為模擬設計的關系,頁面的起

7、始地址均應該為隨機的數值,所以程序在設計過程中加入了隨機數類的編寫.class RandomNumberprivate: unsigned long randseed;public: RandomNumber(unsigned long s=0); unsigned short Random(unsigned long n); double fRandom(void);采用當前系統(tǒng)的時間值來生成偽隨機數分配地址.定義隨機數產生器:RandomNumber random 定義內存頁面數:int pagenum 定義頁面大小:int pagesize定義進程個數:int pnum用整數數組模擬分配

8、的內存頁面數int * mempage=new intpagenum2.3模塊說明2.3.1 主函數主函數依次運行了程序中所實現的關鍵函數. int main() InitSys(); /初始化系統(tǒng) MainChoice();/輸出系統(tǒng)菜單 Destroy(); /釋放申請的動態(tài)內存 return 0;2.3.2 各個功能函數 初始化內存頁面: void Init_Mempage(void)獲取內存使用情況: int Get_Mempagenum(void)初始化默認的請求表: void Init_Reqtable(void)為默認的進程分配內存: void Init_DistMem(void

9、)手動創(chuàng)建進程,并分配內存: void Dist_Mem(void)釋放申請的動態(tài)內存: void Destroy(void)結束指定進程: void Kill(void) 2.3.3 打印函數 打印出進程請求表: void PrintReqtable(void) 打印出頁表: void PrintPageTable(void) 打印出內存使用情況: void PrintMem(void) 打印出物理塊的大小: void PrintBlockSize(void)2.3.4 其他函數 初始化系統(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測試用例，運行結果與運行情況分析4.1測試方法 通過輸入正常數據以及非正常數據對程序進行全方位測試4.2測試結果(1)程序主界面(2)輸入進程號和頁面數:(3)顯示進程頁表:(4)顯示請求表(5)顯示內存使用情況以及物理塊大小(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; /隨機數產生器unsigned pagenum=random.Random(80)+21; /內存頁面數21-100unsigned pagesize=random.Random(16)+5; /頁面大小5-20 unsigned pnum=random.Random(4)+5;/進程的個數5-8int * mempage=

12、new intpagenum; /用整數數組模擬內存頁面數void Init_Mempage(void)int i=0;for(i=0;i<int(pagenum);i+)mempagei=0; /數組全部賦初值int Get_Mempagenum(void)int sum=0;for(int i=0;i<int(pagenum);i+)if(mempagei=0)sum+;return sum; /判斷有多少內存頁面已經被使用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;/進程請求的頁面大小-5preq.state=false;preq.pgtabadr=NULL;reqtable.push_back(preq); /依次壓入容器 /*為默認的進程分配內存*/void Init_DistMem(void)int reqpnum;/進程請求頁面數int i;list<reqtabitem>:iterator pos=reqtable.begin();for(;pos!=reqtable.end();pos+)reqpnum=(*pos).reqpagenum;if(re

14、qpnum>int(Get_Mempagenum()/判斷請求的內存頁面數目是否大于剩余的cout<<"沒有足夠的內存!"<<endl; cout<<endl; else(*pos).state=true;pagetable temp = new pgtabitemreqpnum; /新建臨時頁表項數組if(temp=NULL)cout<<"內存分配失敗!"<<endl;exit(0);(*pos).pgtabadr=temp;for(i=0;i<reqpnum;i+)tempi.p

15、agenum=i;/頁表的頁號int randnum=random.Random(pagenum)+1;/隨機產生一個塊號while(mempagerandnum=1)randnum=random.Random(pagenum)+1;tempi.blocknum=randnum;/頁表的塊號mempagerandnum=1;/*手動創(chuàng)建進程,并分配內存*/void Dist_Mem(void)int i;reqtabitem preq;/新創(chuàng)建進程記錄int pid;/進程號int reqpnum;/請求頁面數bool flag=false;docout<<"請輸入進程號

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

17、gt;>reqpnum;preq.reqpagenum=reqpnum;preq.state=false;preq.pgtabadr=NULL;reqpnum=preq.reqpagenum;if(reqpnum>Get_Mempagenum()cout<<"沒有足夠的內存,進程創(chuàng)建失敗!"<<endl; cout<<endl;elsepreq.state=true;pagetable temp = new pgtabitemreqpnum;if(temp=NULL)cout<<"內存分配失敗!"

18、;<<endl;exit(0);preq.pgtabadr=temp;for(i=0;i<int(reqpnum);i+)tempi.pagenum=i;/頁表的頁號int randnum=random.Random(pagenum)+1;/隨機產生一個塊號while(mempagerandnum=1)randnum=random.Random(pagenum)+1;tempi.blocknum=randnum;/頁表的塊號mempagerandnum=1;reqtable.push_back(preq);/將該進程的記錄加入請求表/*程序結束時,釋放申請的動態(tà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();/* 打印出進程請求表*/void PrintReqtable(void) cout<<endl; cout<<"|-|"<<endl; cout<<"| 進程請求表

20、 |"<<endl; cout<<"|-|"<<endl; cout<<"|"<<setw(8)<<"進程號" <<setw(16)<<"請求頁面數" <<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<<"請輸入進程號:" 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<<"| 此進程的頁表 |"<<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)中不存在該進程或者該進程還沒有被分配內存!n" cout<<endl;void PrintMem(void)cout<<"內存總塊數為"<<pagenum<<",已經使用了"<<pagenum-Get_Mempagenum()<<"塊!"<<endl;cout<<"現在還有"<<Get_Mempagenum()<<"塊內存區(qū)域空閑!"&l

27、t;<endl;cout<<endl;void PrintBlockSize(void)cout<<"物理塊大小為:"<<pagesize<<"KB"<<endl;cout<<endl;/*結束指定進程*/void Kill(void)bool flag;int i;reqtabitem temp;list<reqtabitem>:iterator pos=reqtable.begin();int pid;docout<<"請輸入進程號:&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)中不存在該進程!"<<endl; cout<<endl;while(flag=false);for(i=0;i<int(temp.reqpagenum);i+)mempagetemp.pgtabadri.blocknum=0;reqtable.re

29、move(temp);/重新為沒有分配到內存的進程分配內存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<<"內存分配失敗!"<<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;/隨機產生一個塊號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)建進程"<<endl; cout<<"2.顯示進程頁表"<<endl; cout<<"3.顯示請求表"<<endl; cout<<"4.撤銷進程"<<endl; cout<<"5.顯示內存使用情況"<<endl; cout<<"6.顯示物理塊大小"<<endl; cout<<"7.退出系統(tǒng)"<<endl; cout<<"請輸入您的選擇(0-7):"/*選擇函數*/void MainChoice()int choice;do MainMenu(); c