頁面置換算法實驗報告完整參考模板

1、1 / 26操作系統(tǒng)課程設(shè)計報告 課課程程名名稱稱： 操操作作系系統(tǒng)統(tǒng)課課程程設(shè)設(shè)計計課程設(shè)計題目課程設(shè)計題目： 頁面置換算法頁面置換算法 學(xué)院：學(xué)院： 計算機科學(xué)與技術(shù)學(xué)院計算機科學(xué)與技術(shù)學(xué)院 專專業(yè)業(yè)： 科科技技小小組組成成員員 : : 龐龐思思慧慧 E E0 01 11 11 14 40 08 81 1 王王蒙蒙 E E0 01 11 11 14 41 16 61 1 姚姚慧慧喬喬 E E0 01 11 11 14 43 34 49 9 朱朱潮潮潮潮 E E0 01 11 11 14 44 40 08 8指導(dǎo)老師：指導(dǎo)老師： 邱劍鋒邱劍鋒 目錄目錄1實驗?zāi)康膶嶒災(zāi)康?32實驗要求實驗要求

2、.33實驗內(nèi)容與步驟實驗內(nèi)容與步驟.34算法思想算法思想.45模塊設(shè)計模塊設(shè)計.46程序設(shè)計程序設(shè)計.57測試結(jié)果測試結(jié)果.78結(jié)果分析結(jié)果分析.99程序代碼程序代碼.910課程設(shè)計小結(jié)課程設(shè)計小結(jié).24 頁面置換算法模擬設(shè)計頁面置換算法模擬設(shè)計1.1.實驗?zāi)康膶嶒災(zāi)康模?）通過模擬實現(xiàn)幾種基本頁面置換的算法，了解虛擬存儲技術(shù)的特點。（2）掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想，并至少用三種算法來模擬實現(xiàn)。（3）通過對幾種置換算法命中率的比較，來對比他們的優(yōu)缺點。2.2.實驗要求實驗要求 計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。 A A 先進(jìn)先出的算法（FIFO）

3、 B B 最近最少使用算法（LRU） C C 最佳淘汰算法（OPT）3.3.實驗內(nèi)容與步驟實驗內(nèi)容與步驟(1)通過隨機數(shù)產(chǎn)生一個指令序列，共 320 條指令，具體的實施方法是：A 0，319的指令地址之間隨機選取一起點 M;B 順序執(zhí)行一條指令，即執(zhí)行地址為 M+1 的指令；C 在前地址0，M+1中隨機選取一條指令并執(zhí)行，該指令的地址為 M;D 順序執(zhí)行一條指令，其地址為 M+1；E 在后地址M+2，319中隨機選取一條指令并執(zhí)行；F重復(fù) AE，直到執(zhí)行 320 次指令。(2)指令序列變換成頁地址流A.頁面大小為 1K； B.用戶內(nèi)存容量為 4 頁到 32 頁；C.用戶虛存容量為 32K。在用

4、戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令在虛存中的存放方式為：第 0 條第 9 條指令為第 0 頁（對應(yīng)虛存地址為0，9） ； 第 10 條第 19 條指令為第 1 頁（對應(yīng)虛存地址為10，19） ； 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 第 310 條第 319 條指令為第 31 頁（對應(yīng)虛存地址為310，319） ； (3)計算并輸出上述各種算法在不同內(nèi)存容量下的命中率。 命中率=1-缺頁次數(shù)/頁地址流長度4.4.算法思想算法思想 在進(jìn)程運行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時

5、，為了保證該進(jìn)程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應(yīng)將哪 個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。 1.先進(jìn)先出算法 FIFO： 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。2.最近最久未使用算法 LRU（l

6、east recently used）：算法的基本思想：當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁很長時間未被訪問，則它在最近一段時間不會被訪問。3.最佳淘汰算法 OPT其所選擇的被淘汰的頁面將是以后永不使用，或許是未來最長時間內(nèi)不使用的頁面，該算法可保證獲得最低的淘汰率，但在實際運用中無法實現(xiàn)，可用來評價其他算法的命中率。5.5.模塊設(shè)計模塊設(shè)計 入口產(chǎn)生隨機數(shù)、要調(diào)入的頁面、離現(xiàn)在處理時間最長的頁面、最長的頁面初始化頁面情況t1N根據(jù)選擇的算法進(jìn)行置換，缺頁數(shù)加 1計算缺頁

7、率，并輸出數(shù)據(jù) 結(jié)束YN直接存入內(nèi)存開始輸入內(nèi)存數(shù)調(diào)用各種置換算法，并顯示地址流、頁面流、頁面置換過程和命中率命中率比較結(jié)束結(jié)束 總模塊圖總模塊圖 主程序圖6.6.程序設(shè)計程序設(shè)計struct Pro /內(nèi)存頁的結(jié)構(gòu)體int num； /記錄頁面號int time； /頁面從未被利用的時間;#define M 320 /定義指令條數(shù)Pro PM; /產(chǎn)生的隨機指令數(shù)組void Input() /產(chǎn)生隨機數(shù)int s; /隨機數(shù)int i; srand(time(0); s = rand()%M;/coutn-隨機產(chǎn)生指令流-n; for (i=0; iM; i+=4) /產(chǎn)生指令隊列 pi.n

8、um=s; /任選一指令訪問點 m pi+1.num=pi.num+1; /順序執(zhí)行一條指令 pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0); /執(zhí)行前地址指令 m pi+3.num=pi+2.num+1; /順序執(zhí)行一條指令 s=(int)(float)(319-pi+2.num)*(rand()/(RAND_MAX+1.0) + pi+2.num; for(i=0;iM;i+)pi.time=0; int Search(int e,Pro*page1,int N) /查找內(nèi)存中是否存在要調(diào)入的頁面int t;Pro*page=new P

9、roN;page=page1;for(int i=0;iN;i+)t=e/10;if(t=pagei.num)return i;return -1; int Max(Pro*page1,int N)/查找最久最久未被使用的頁面Pro*page=new ProN;page=page1;int e=page0.time,i=0;while(iN)if(epagei.time) e=pagei.time; /找最長時間i+;for(i=0;iN;i+)if(e=pagei.time) return i; /找最長時間的下標(biāo)return -1; int Compfu(Pro*page1,int i,i

10、nt t,Pro pM) /找到最久不使用的頁面Pro*page=new ProN;page=page1;int count=0;for(int j=i;jLRUCLOCKFIFO。實際上，在內(nèi)存頁面數(shù)較少（45 頁面）時，3 種算法的命中率差別不大，可是 50%左右。在內(nèi)存頁面為 725 個頁面之間時，3 種算法的訪內(nèi)命中率大致在 52%至 87%之間變化。在內(nèi)存頁面為 2532 個頁面時，由于用戶進(jìn)程的所有指令基本上都已裝入內(nèi)存，從而命中率已較大。從而算法之間的差別不大。9.9.程序代碼程序代碼/ 頁面置換算法模擬設(shè)計 Dlg.cpp : implementation file#inclu

11、de stdafx.h#include 頁面置換算法模擬設(shè)計.h#include 頁面置換算法模擬設(shè)計 Dlg.h#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endif/ CMyDlg dialogCMyDlg:CMyDlg(CWnd* pParent /*=NULL*/): CDialog(CMyDlg:IDD, pParent)/AFX_DATA_INIT(CMyDlg)m_iFifo = 0;N = 0;MZL = 0.0;/AFX_DATA_INIT/ Note th

12、at LoadIcon does not require a subsequent DestroyIcon in Win32m_hIcon = AfxGetApp()-LoadIcon(IDR_MAINFRAME);void CMyDlg:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CMyDlg)DDX_Control(pDX, IDC_EDIT4, m_suiji2);DDX_Control(pDX, IDC_EDIT5, m_yemian);DDX_Control(pDX, IDC_

13、EDIT3, m_suiji);DDX_Radio(pDX, IDC_RADIO1, m_iFifo);DDX_Text(pDX, IDC_EDIT1, N);DDX_Text(pDX, IDC_EDIT2, MZL);/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CMyDlg, CDialog)/AFX_MSG_MAP(CMyDlg)ON_WM_PAINT()ON_WM_QUERYDRAGICON()ON_BN_CLICKED(IDC_BUTTON1, OnButton1)ON_BN_CLICKED(IDC_RADIO1, OnRadio1)ON_BN_CLICKED(IDC

14、_RADIO2, OnRadio2)ON_BN_CLICKED(IDC_RADIO3, OnRadio3)ON_EN_CHANGE(IDC_EDIT2, OnChangeEdit2)ON_BN_CLICKED(IDC_BUTTON2, OnButton2)ON_BN_CLICKED(IDC_BUTTON3, OnButton3)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CMyDlg message handlersBOOL CMyDlg:OnInitDialog()CDialog:OnInitDialog();/ Set the icon for this dialog.

15、The framework does this automatically/ when the applications main window is not a dialogSetIcon(m_hIcon, TRUE);/ Set big iconSetIcon(m_hIcon, FALSE);/ Set small icon/ TODO: Add extra initialization herereturn TRUE; / return TRUE unless you set the focus to a control/ If you add a minimize button to

16、your dialog, you will need the code below/ to draw the icon. For MFC applications using the document/view model,/ this is automatically done for you by the framework.void CMyDlg:OnPaint() if (IsIconic()CPaintDC dc(this); / device context for paintingSendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafe

17、Hdc(), 0);/ Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;GetClientRect(&rect);int x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;/ Draw the icondc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPa

18、int();/ The system calls this to obtain the cursor to display while the user drags/ the minimized window.HCURSOR CMyDlg:OnQueryDragIcon()return (HCURSOR) m_hIcon;#include#include#include#define M 320int N;struct Pro/內(nèi)存頁的結(jié)構(gòu)體int num,time;Pro pM;void Input()/輸入函數(shù)，輸入實際頁號和實際頁數(shù)int s;/隨機數(shù)inti; srand(time(0

19、);/每次運行時進(jìn)程號不同，用來作為初始化隨機數(shù)隊列的種子 s = rand()%M;/coutn-隨機產(chǎn)生指令流-n; for (i=0; iM; i+=4)/產(chǎn)生指令隊列 pi.num=s;/任選一指令訪問點 m pi+1.num=pi.num+1;/順序執(zhí)行一條指令 pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0);/執(zhí)行前地址指令 m pi+3.num=pi+2.num+1;/順序執(zhí)行一條指令 s=(int)(float)(319-pi+2.num)*(rand()/(RAND_MAX+1.0) + pi+2.num; for(i=0

20、;iM;i+)pi.time=0;/*p0.num=10;p1.num=22;p2.num=33;p3.num=44;p4.num=50;p5.num=13;p6.num=32;p7.num=22; /測試數(shù)據(jù) 1,2,3,4,5,1,3,2 fifo 5,1,2,4 LRU 5,1,3,2 opt 置換 1,2,3,5*/int Search(int e,Pro*page1,int N)/查找內(nèi)存中是否存在要調(diào)入的頁面int t;Pro*page=new ProN;page=page1;for(int i=0;iN;i+)t=e/10;if(t=pagei.num)return i;retu

21、rn -1;int Max(Pro*page1,int N)/找出離現(xiàn)在時間最長的頁面Pro*page=new ProN;page=page1;int e=page0.time,i=0;while(iN)if(epagei.time) e=pagei.time;/找最長時間i+;for(i=0;iN;i+)if(e=pagei.time) return i;/找最長時間的下標(biāo)return -1;int Compfu(Pro*page1,int i,int t,Pro pM)/找到最久不使用的頁面Pro*page=new ProN;page=page1;int count=0;for(int j

22、=i;jM;j+)if(paget.num=pj.num/10) break;/當(dāng)前頁面開始往后查找在內(nèi)存中的頁幀號else +count;return count;void CMyDlg:OnButton1() / TODO: Add your control notification handler code hereUpdateData(true);Input();/地址流CString str1,tmp1;tmp1=str1=;int k=0,t=0,i=0;for(i=0;iM;i+)tmp1.Format(%-4d,pi.num);str1+=tmp1;k+;if(k%16=0)s

23、tr1+=nrnrnr;m_suiji.SetWindowText(_T(str1);/頁面流CString str2,tmp2;tmp2=str2=;for(i=0;iM;i+)tmp2.Format(%-4d,pi.num/10);str2+=tmp2;k+;if(k%16=0)str2+=nrnrnr;m_suiji2.SetWindowText(_T(str2);Pro*page=new ProN;for(int j=0;jN;j+)/初始化頁面基本情況pagej.num=-1;pagej.time=j;if(m_iFifo=0)/FIFO 頁面置換float n=0;/記錄缺頁數(shù)in

24、t i=0;CString str3,tmp3;str3=;m_yemian.SetWindowText(_T(str3);while(i=0) +i;/找到相同的頁面elsen+;paget.num=pi.num/10;/如果沒有找到相同的頁，則進(jìn)行頁面替換，缺頁數(shù)加一/tmp3=;m_yemian.GetWindowText(_T(str3);for(int i=0;iN;i+)if(pagei.num=-1)tmp3.Format(%s, );str3+=tmp3;elsetmp3.Format(%-4d,pagei.num);str3+=tmp3;str3+=nrnrnr;m_yemi

25、an.SetWindowText(_T(str3);/t=(+t)%N;MZL=1-n/M;if(m_iFifo=1) /LRU 頁面置換int p2;float n=0;/記錄缺頁數(shù)int i=0;int t1=t=0;CString str3,tmp3;str3=;m_yemian.SetWindowText(_T(str3);while(i=0)pagek.time=0;for(p2=0;p2N;p2+)if(p2!=k)pagep2.time+;elseif(t1N)n+;paget.num=pi.num/10;/如果沒有找到相同的頁，則進(jìn)行頁面替換，缺頁數(shù)加一+t1;t+;paget

26、.time=0;/tmp3=;m_yemian.GetWindowText(_T(str3);for(int i=0;iN;i+)if(pagei.num=-1)tmp3.Format(%s, );str3+=tmp3;elsetmp3.Format(%-4d,pagei.num);str3+=tmp3;str3+=nrnrnr;m_yemian.SetWindowText(_T(str3);/elsen+;t=Max(page,N);paget.num=pi.num/10;paget.time=0;/tmp3=;m_yemian.GetWindowText(_T(str3);for(int

27、i=0;iN;i+)if(pagei.num=-1)tmp3.Format(%s, );str3+=tmp3;elsetmp3.Format(%-4d,pagei.num);str3+=tmp3;str3+=nrnrnr;m_yemian.SetWindowText(_T(str3);/for(p2=0;p2N;p2+)if(p2!=t)pagep2.time+;i+;MZL=1-n/M;if(m_iFifo=2)/OPT 頁面置換int i=0;float n=0;/記錄缺頁數(shù)int t=0,t1=0;CString str3,tmp3;str3=;m_yemian.SetWindowTex

28、t(_T(str3);while(i=0)i+;elseif(t1N)n+;paget.num=pi.num/10;/如果沒有找到相同的頁，則進(jìn)行頁面替換，缺頁數(shù)加 1+t1;t+;i+;/tmp3=;m_yemian.GetWindowText(_T(str3);for(int i=0;i=N)int temp=-1,cn;for(t=0;tN;t+)/查找下次訪問距離最遠(yuǎn)的那個頁面 if(tempCompfu(page,i,t,p)temp=Compfu(page,i,t,p);/下次命中經(jīng)歷的頁面計數(shù)cn=t;/最遠(yuǎn)的頁面號pagecn.num=pi.num/10;n+;/tmp3=;m

29、_yemian.GetWindowText(_T(str3);for(int i=0;iN;i+)if(pagei.num=-1)tmp3.Format(%s, );str3+=tmp3;elsetmp3.Format(%-4d,pagei.num);str3+=tmp3;str3+=nrnrnr;m_yemian.SetWindowText(_T(str3);/i+;else break;MZL=1-n/M;UpdateData(false);void CMyDlg:OnRadio1() / TODO: Add your control notification handler code h

30、erevoid CMyDlg:OnRadio2() / TODO: Add your control notification handler code herevoid CMyDlg:OnRadio3() / TODO: Add your control notification handler code herevoid CMyDlg:OnChangeEdit2() / TODO: If this is a RICHEDIT control, the control will not/ send this notification unless you override the CDial

31、og:OnInitDialog()/ function and call CRichEditCtrl().SetEventMask()/ with the ENM_CHANGE flag ORed into the mask./ TODO: Add your control notification handler code herevoid CMyDlg:OnButton2() / TODO: Add your control notification handler code hereMessageBox(_T(確認(rèn)退出?);ExitProcess(0);void CMyDlg:OnButton3() UpdateData(true);Input();Pro*page=new ProN;for(int j=0;jN;j+)/初始化頁面基本情況pagej.num=-1;pagej.time=j;int t1=0;int i1=0;float n1=0;float s1,s2,s3; /FIFO 頁面置換n1=0;/記錄缺頁數(shù)while(i1=0) +