页面置换算法实验报告(2)

1、.操作系统课程设计报告课程名称：操作系统课程设计课程设计题目： 页面置换算法学院：计算机科学与技术学院专 业 ：科 技小组成员:庞 思 慧E01114081王 蒙E01114161姚 慧 乔E01114349朱 潮 潮E01114408指导老师：邱剑锋;.目录1实验目的32实验要求33实验内容与步骤34算法思想45模块设计46程序设计57测试结果78结果分析99程序代码910课程设计小结24;.页面置换算法模拟设计1. 实验目的（1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。（2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。（3）

2、通过对几种置换算法命中率的比较，来对比他们的优缺点。2. 实验要求计算并输出下述各种算法在不同内存容量下的命中率。ABC先进先出的算法（FIFO）最近最少使用算法（LRU）最佳淘汰算法（OPT）3. 实验内容与步骤(1) 通过随机数产生一个指令序列，共 320 条指令，具体的实施方法是：A 0 ， 319 的指令地址之间随机选取一起点M;B 顺序执行一条指令，即执行地址为M+1的指令；C 在前地址 0 ， M+1中随机选取一条指令并执行，该指令的地址为M ;D 顺序执行一条指令，其地址为M +1；E 在后地址 M +2， 319 中随机选取一条指令并执行；F 重复 A E，直到执行320 次指

3、令。(2) 指令序列变换成页地址流A. 页面大小为 1K；B. 用户内存容量为 4 页到 32 页；;.C.用户虚存容量为32K。在用户虚存中，按每K 存放 10 条指令排列虚存地址，即320 条指令在虚存中的存放方式为：第 0 条第 9 条指令为第 0页（对应虚存地址为 0，9 ）；第 10 条第 19 条指令为第1 页（对应虚存地址为10 ， 19 ）；。第 310 条第 319 条指令为第31 页（对应虚存地址为310 ，319 ）；(3) 计算并输出上述各种算法在不同内存容量下的命中率。命中率 =1- 缺页次数 / 页地址流长度4. 算法思想在进程运行过程中，若其所要访问的页面不在内存

4、而需把它们调入内存，但内存已无空闲空间时， 为了保证该进程能正常运行， 系统必须从内存中调出一页程序或数据， 送磁盘的对换区中。 但应将哪 个页面调出， 须根据一定的算法来确定。通常， 把选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。1. 先进先出算法 FIFO：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。 该算法实现简单只需把一个进程已调入内存的页面， 按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它

5、总是指向最老的页面。2. 最近最久未使用算法LRU（leastrecentlyused）：算法的基本思想： 当需要淘汰某一页时， 选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3. 最佳淘汰算法 OPT其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。5. 模块设计;.开始输入内存数调用各种置换算法， ，并显示地址流、页面流、页面置换过程和命中率命中

6、率比较结束总模块图入口产生随机数、 要调入的页面、 离现在处理时间最长的页面、初始化页面情况Yt1<N直接存入内存N根据选择的算法进行置换，缺页数加1计算缺页率， 并输出数据结束;.主程序图6. 程序设计struct Pro/内存页的结构体int num；/记录页面号int time ；/页面从未被利用的时间;#define M 320/定义指令条数Pro PM;/ 产生的随机指令数组void Input()/产生随机数int s;/随机数inti;srand(time(0);s = rand()%M;/cout<<"n- 随机产生指令流 -n"for (

7、i=0; i<M; i+=4)/产生指令队列pi.num=s;/任选一指令访问点m;.pi+1.num=pi.num+1; /顺序执行一条指令 pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0);/执行前地址指令m'pi+3.num=pi+2.num+1;/顺序执行一条指令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)/查找内存中是

8、否存在要调入的页面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; /找最长时间 i+;for(i=0;i<N;i+)if(e=pagei.time) return i; /找最

9、长时间的下标 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;/当前页面开始往后查找是否命中内存中的页号else +count;/内存中的页面下次出现经过的页面数return count;7. 测试结果选中算法，输入内存数点击计算;.;.点击命中率按钮点击退出按钮8. 结果分析理论上，四种替换算法的命中率由高到底排列应该是OPT>

10、LRU>CLOCK>FIFO。实际上，在内存页面数较少（45 页面）时， 3 种算法的命中率差别不大，可是50%左右。在内存页面为 725 个页面之间时，3 种算法的访内命中率大致在52%至 87%之间变化。在内存页面为2532 个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。从而算法之间的差别不大。9. 程序代码/ 页面置换算法模拟设计 Dlg.cpp : implementation file #include "stdafx.h"#include " 页面置换算法模拟设计 .h" #include " 页

11、面置换算法模拟设计 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/ 内存页的结构体int num,time;Pro pM;void Input()/ 输入函数，输入实际页号和实际页数int

19、s;/随机数inti;srand(time(0);/ 每次运行时进程号不同，用来作为初始化随机数队列的种子s = rand()%M;/cout<<"n-随机产生指令流-n"for (i=0; i<M; i+=4)/产生指令队列pi.num=s;/任选一指令访问点mpi+1.num=pi.num+1;/ 顺序执行一条指令pi+2.num=(int)(float)pi.num*(rand()/(RAND_MAX+1.0); /执行前地址指令 m'.pi+3.num=pi+2.num+1;/ 顺序执行一条指令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;/ 测试数据 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)/查找内存中是否存在要调入的页面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)/ 找出离现在时间最长的页面Pro*page=new ProN;page=page1;int e=page0.time,i=0;while(i<N)if(e<pagei.time)e=pagei.time;/找最长时间i+;.for(i=0;i<N;i+)if(e=pagei.time)return i;/找最长时间的下标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;/当前页面开始往后查找在内存中的页帧号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;/ 记录缺页数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;/ 如果没有找到相同的页，则进行页面替换，缺页数加一/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;/ 记录缺页数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、的页， 则进行页面替换，缺页数加一+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;/ 记录缺页数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;/ 如果没有找到相同的页，则进行页面替换，缺页数加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+)/ 查找下次访问距离最远的那个页面if(temp<Compfu(page,i,t,p)temp=Compfu(page,i,t,p);/ 下次命中经历的页面计数cn=t;/ 最远的页面号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(" 确认退出 ?");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;/ 记录缺页数while(i1<M)if(Search(pi1.num,page,N)>=0)+i1;/ 找到相同的页面elsen1+;paget1.num=pi1.num/10;/ 如果没有找到相同的页，则进行页面替换，缺页数加一t1=(+t1)%N;.i1+;s1=1-n1/M;/LRU 页面置换int p2;float n2=0;/ 记录缺页数int tt,t2;tt=t