頁面置換算法實(shí)驗(yàn)報(bào)告(2)

1、.操作系統(tǒng)課程設(shè)計(jì)報(bào)告課程名稱：操作系統(tǒng)課程設(shè)計(jì)課程設(shè)計(jì)題目： 頁面置換算法學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè) ：科 技小組成員:龐 思 慧E01114081王 蒙E01114161姚 慧 喬E01114349朱 潮 潮E01114408指導(dǎo)老師：邱劍鋒;.目錄1實(shí)驗(yàn)?zāi)康?2實(shí)驗(yàn)要求33實(shí)驗(yàn)內(nèi)容與步驟34算法思想45模塊設(shè)計(jì)46程序設(shè)計(jì)57測試結(jié)果78結(jié)果分析99程序代碼910課程設(shè)計(jì)小結(jié)24;.頁面置換算法模擬設(shè)計(jì)1. 實(shí)驗(yàn)?zāi)康模?）通過模擬實(shí)現(xiàn)幾種基本頁面置換的算法，了解虛擬存儲技術(shù)的特點(diǎn)。（2）掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想，并至少用三種算法來模擬實(shí)現(xiàn)。（3）

2、通過對幾種置換算法命中率的比較，來對比他們的優(yōu)缺點(diǎn)。2. 實(shí)驗(yàn)要求計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。ABC先進(jìn)先出的算法（FIFO）最近最少使用算法（LRU）最佳淘汰算法（OPT）3. 實(shí)驗(yàn)內(nèi)容與步驟(1) 通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共 320 條指令，具體的實(shí)施方法是：A 0 ， 319 的指令地址之間隨機(jī)選取一起點(diǎn)M;B 順序執(zhí)行一條指令，即執(zhí)行地址為M+1的指令；C 在前地址 0 ， M+1中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為M ;D 順序執(zhí)行一條指令，其地址為M +1；E 在后地址 M +2， 319 中隨機(jī)選取一條指令并執(zhí)行；F 重復(fù) A E，直到執(zhí)行320 次指

3、令。(2) 指令序列變換成頁地址流A. 頁面大小為 1K；B. 用戶內(nèi)存容量為 4 頁到 32 頁；;.C.用戶虛存容量為32K。在用戶虛存中，按每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) 計(jì)算并輸出上述各種算法在不同內(nèi)存容量下的命中率。命中率 =1- 缺頁次數(shù) / 頁地址流長度4. 算法思想在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存

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

5、總是指向最老的頁面。2. 最近最久未使用算法LRU（leastrecentlyused）：算法的基本思想： 當(dāng)需要淘汰某一頁時(shí)， 選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點(diǎn)是，如果某頁被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁很長時(shí)間未被訪問，則它在最近一段時(shí)間不會被訪問。3. 最佳淘汰算法 OPT其所選擇的被淘汰的頁面將是以后永不使用，或許是未來最長時(shí)間內(nèi)不使用的頁面，該算法可保證獲得最低的淘汰率，但在實(shí)際運(yùn)用中無法實(shí)現(xiàn)，可用來評價(jià)其他算法的命中率。5. 模塊設(shè)計(jì);.開始輸入內(nèi)存數(shù)調(diào)用各種置換算法， ，并顯示地址流、頁面流、頁面置換過程和命中率命中

6、率比較結(jié)束總模塊圖入口產(chǎn)生隨機(jī)數(shù)、 要調(diào)入的頁面、 離現(xiàn)在處理時(shí)間最長的頁面、初始化頁面情況Yt1<N直接存入內(nèi)存N根據(jù)選擇的算法進(jìn)行置換，缺頁數(shù)加1計(jì)算缺頁率， 并輸出數(shù)據(jù)結(jié)束;.主程序圖6. 程序設(shè)計(jì)struct Pro/內(nèi)存頁的結(jié)構(gòu)體int num；/記錄頁面號int time ；/頁面從未被利用的時(shí)間;#define M 320/定義指令條數(shù)Pro PM;/ 產(chǎn)生的隨機(jī)指令數(shù)組void Input()/產(chǎn)生隨機(jī)數(shù)int s;/隨機(jī)數(shù)inti;srand(time(0);s = rand()%M;/cout<<"n- 隨機(jī)產(chǎn)生指令流 -n"for (

7、i=0; i<M; i+=4)/產(chǎn)生指令隊(duì)列pi.num=s;/任選一指令訪問點(diǎn)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;i<M;i+)pi.time=0;int Search(int e,Pro*page1,int N)/查找內(nèi)存中是

8、否存在要調(diào)入的頁面int t;Pro*page=new ProN;page=page1;for(int i=0;i<N;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(i<N)if(e<pagei.time) e=pagei.time; /找最長時(shí)間 i+;for(i=0;i<N;i+)if(e=pagei.time) return i; /找最

9、長時(shí)間的下標(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=i;j<M;j+)if(paget.num=pj.num/10) break;/當(dāng)前頁面開始往后查找是否命中內(nèi)存中的頁號else +count;/內(nèi)存中的頁面下次出現(xiàn)經(jīng)過的頁面數(shù)return count;7. 測試結(jié)果選中算法，輸入內(nèi)存數(shù)點(diǎn)擊計(jì)算;.;.點(diǎn)擊命中率按鈕點(diǎn)擊退出按鈕8. 結(jié)果分析理論上，四種替換算法的命中率由高到底排列應(yīng)該是OPT>

10、LRU>CLOCK>FIFO。實(shí)際上，在內(nèi)存頁面數(shù)較少（45 頁面）時(shí)， 3 種算法的命中率差別不大，可是50%左右。在內(nèi)存頁面為 725 個(gè)頁面之間時(shí)，3 種算法的訪內(nèi)命中率大致在52%至 87%之間變化。在內(nèi)存頁面為2532 個(gè)頁面時(shí)，由于用戶進(jìn)程的所有指令基本上都已裝入內(nèi)存，從而命中率已較大。從而算法之間的差別不大。9. 程序代碼/ 頁面置換算法模擬設(shè)計(jì) Dlg.cpp : implementation file #include "stdafx.h"#include " 頁面置換算法模擬設(shè)計(jì) .h" #include " 頁

11、面置換算法模擬設(shè)計(jì) 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 that LoadIcon does not require a su

12、bsequent DestroyIcon in Win32 m_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_EDIT3, m_suiji);DDX_Radio(pD

13、X, 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_RADIO2, OnRadio2)ON_BN_CLIC

14、KED(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.The framework does this auto

15、matically/ when the application's 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 TRUEunless you set the focus to a control/ If you add a minimize button to your dialog, you will nee

16、d 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.GetSafeHdc(), 0);/ Center icon in

17、 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 icon dc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPaint();./ The system calls

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

19、s;/隨機(jī)數(shù)inti;srand(time(0);/ 每次運(yùn)行時(shí)進(jìn)程號不同，用來作為初始化隨機(jī)數(shù)隊(duì)列的種子s = rand()%M;/cout<<"n-隨機(jī)產(chǎn)生指令流-n"for (i=0; i<M; i+=4)/產(chǎn)生指令隊(duì)列pi.num=s;/任選一指令訪問點(diǎn)mpi+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

20、.num)*(rand()/(RAND_MAX+1.0) + pi+2.num;for(i=0;i<M;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,2fifo 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(

21、int i=0;i<N;i+)t=e/10;if(t=pagei.num)return i;return -1;int Max(Pro*page1,int N)/ 找出離現(xiàn)在時(shí)間最長的頁面Pro*page=new ProN;page=page1;int e=page0.time,i=0;while(i<N)if(e<pagei.time)e=pagei.time;/找最長時(shí)間i+;.for(i=0;i<N;i+)if(e=pagei.time)return i;/找最長時(shí)間的下標(biāo)return -1;int Compfu(Pro*page1,int i,int t,Pro

22、 pM)/找到最久不使用的頁面Pro*page=new ProN;page=page1;int count=0;for(int j=i;j<M;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 here UpdateData(true);Input();/ 地址流CString str1,tmp1;tmp1=str1=""

23、;int k=0,t=0,i=0;for(i=0;i<M;i+)tmp1.Format("%-4d",pi.num);str1+=tmp1;k+;if(k%16=0)str1+="nrnrnr".m_suiji.SetWindowText(_T(str1);/ 頁面流CString str2,tmp2;tmp2=str2=""for(i=0;i<M;i+)tmp2.Format("%-4d",pi.num/10);str2+=tmp2;k+;if(k%16=0)str2+="nrnrnr&qu

24、ot;m_suiji2.SetWindowText(_T(str2);Pro*page=new ProN;for(int j=0;j<N;j+)/初始化頁面基本情況pagej.num=-1;pagej.time=j;if(m_iFifo=0)/FIFO 頁面置換float n=0;/ 記錄缺頁數(shù)int i=0;CString str3,tmp3;str3=""m_yemian.SetWindowText(_T(str3);while(i<M)if(Search(pi.num,page,N)>=0)+i;/ 找到相同的頁面elsen+;paget.num=p

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

26、L=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<M)int k;k=Search(pi.num,page,N);if(k>=0)pagek.time=0;for(p2=0;p2<N;p2+);.if(p2!=k)pagep2.time+;elseif(t1<N)n+;paget.num=pi.num/10;/ 如果沒有找到相同

27、的頁， 則進(jìn)行頁面替換，缺頁數(shù)加一+t1;t+;paget.time=0;/ tmp3=""m_yemian.GetWindowText(_T(str3);for(int i=0;i<N;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

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

29、for(p2=0;p2<N;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.SetWindowText(_T(str3);while(i<M)if(Search(pi.num,page,N)>=0)i+;else;.if(t1<N)n+;paget.num=pi.num/10;/ 如果沒有找到相同的頁，則進(jìn)行頁面替換，缺頁數(shù)加1+t1;t

30、+;i+;/ tmp3=""m_yemian.GetWindowText(_T(str3);for(int i=0;i<N;i+)if(pagei.num=-1)tmp3.Format("%s"," ");str3+=tmp3;elsetmp3.Format("%-4d",pagei.num);str3+=tmp3;str3+="nrnrnr"m_yemian.SetWindowText(_T(str3);/ else if(t1>=N)int temp=-1,cn;for(t=0;

31、t<N;t+)/ 查找下次訪問距離最遠(yuǎn)的那個(gè)頁面if(temp<Compfu(page,i,t,p)temp=Compfu(page,i,t,p);/ 下次命中經(jīng)歷的頁面計(jì)數(shù)cn=t;/ 最遠(yuǎn)的頁面號pagecn.num=pi.num/10;n+;/tmp3=""m_yemian.GetWindowText(_T(str3);.for(int i=0;i<N;i+)if(pagei.num=-1)tmp3.Format("%s"," ");str3+=tmp3;elsetmp3.Format("%-4d&q

32、uot;,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 herevoid CMyDlg:OnRadio2()/ TODO: Add your control notification handler code herevoid CMyDlg:OnRadio3

33、()/ TODO: Add your control notification handler code here;.void CMyDlg:OnChangeEdit2()/ TODO: If this is a RICHEDIT control, the control will not/ send this notification unless you override the CDialog:OnInitDialog()/ function and call CRichEditCtrl().SetEventMask()/ with the ENM_CHANGE flag ORed in

34、to the mask./ TODO: Add your control notification handler code herevoid CMyDlg:OnButton2()/ TODO: Add your control notification handler code here MessageBox(_T(" 確認(rèn)退出 ?");ExitProcess(0);void CMyDlg:OnButton3()UpdateData(true);Input();Pro*page=new ProN;for(int j=0;j<N;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<M)if(Search(pi1.num,page,N)>=0)+i1;/ 找到相同的頁面elsen1+;paget1.num=pi1.num/10;/ 如果沒有找到相同的頁，則進(jìn)行頁面替換，缺頁數(shù)加一t1=(+t1)%N;.i1+;s1=1-n1/M;/LRU 頁面置換int p2;float n2=0;/ 記錄缺頁數(shù)int tt,t2;tt=t