页面置换算法实验报告(共25页).doc

精选优质文档-倾情为你奉上专心-专注-专业操作系统课程设计报告 课课程程名名称称： 操操作作系系统统课课程程设设计计课程设计题目课程设计题目： 页面置换算法页面置换算法 学院：学院： 计算机科学与技术学院计算机科学与技术学院 专专业业： 科科技技小小组组成成员员 : : 庞庞思思慧慧 E E 王王蒙蒙 E E 姚姚慧慧乔乔 E E 朱朱潮潮潮潮 E E指导老师：指导老师： 邱剑锋邱剑锋精选优质文档-倾情为你奉上专心-专注-专业 目录目录1实验目的实验目的 .32实验要求实验要求 .33实验内容与步骤实验内容与步骤 .34算法思想算法思想 .45模块设计模块设计 .46程序设计程序设计 .57测试结果测试结果 .78结果分析结果分析 .99程序代码程序代码 .910课程设计小结课程设计小结 .24精选优质文档-倾情为你奉上专心-专注-专业 页面置换算法模拟设计页面置换算法模拟设计1.1.实验目的实验目的（1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。（2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。（3）通过对几种置换算法命中率的比较，来对比他们的优缺点。2.2.实验要求实验要求 计算并输出下述各种算法在不同内存容量下的命中率。 A A 先进先出的算法（FIFO） B B 最近最少使用算法（LRU） C C 最佳淘汰算法（OPT）3.3.实验内容与步骤实验内容与步骤(1)通过随机数产生一个指令序列，共 320 条指令，具体的实施方法是：A 0，319的指令地址之间随机选取一起点 M;B 顺序执行一条指令，即执行地址为 M+1 的指令；C 在前地址0，M+1中随机选取一条指令并执行，该指令的地址为 M;D 顺序执行一条指令，其地址为 M+1；E 在后地址M+2，319中随机选取一条指令并执行；F重复 AE，直到执行 320 次指令。(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： 这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。2.最近最久未使用算法 LRU（least recently used）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3.最佳淘汰算法 OPT其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。5.5.模块设计模块设计精选优质文档-倾情为你奉上专心-专注-专业 入口产生随机数、要调入的页面、离现在处理时间最长的页面、最长的页面初始化页面情况t1N根据选择的算法进行置换，缺页数加 1计算缺页率，并输出数据 结束YN直接存入内存开始输入内存数调用各种置换算法，并显示地址流、页面流、页面置换过程和命中率命中率比较结束结束 总模块图总模块图 主程序图精选优质文档-倾情为你奉上专心-专注-专业6.6.程序设计程序设计struct Pro /内存页的结构体int num； /记录页面号int time； /页面从未被利用的时间;#define M 320 /定义指令条数Pro PM; /产生的随机指令数组void Input() /产生随机数int s; /随机数int i; srand(time(0); s = rand()%M;/coutn-随机产生指令流-n; for (i=0; iM; 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;iM;i+)pi.time=0; int Search(int e,Pro*page1,int N) /查找内存中是否存在要调入的页面int t;Pro*page=new ProN;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; /找最长时间的下标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;jLRUCLOCKFIFO。实际上，在内存页面数较少（45 页面）时，3 种算法的命中率差别不大，可是 50%左右。在内存页面为 725 个页面之间时，3 种算法的访内命中率大致在 52%至 87%之间变化。在内存页面精选优质文档-倾情为你奉上专心-专注-专业为 2532 个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。从而算法之间的差别不大。9.9.程序代码程序代码/ 页面置换算法模拟设计 Dlg.cpp : implementation file#include stdafx.h#include 页面置换算法模拟设计.h#include 页面置换算法模拟设计 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 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_EDIT3, m_suiji);DDX_Radio(pDX, IDC_RADIO1, m_iFifo);DDX_Text(pDX, IDC_EDIT1, N);DDX_Text(pDX, IDC_EDIT2, MZL);/AFX_DATA_MAP精选优质文档-倾情为你奉上专心-专注-专业BEGIN_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_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. 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 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 painting精选优质文档-倾情为你奉上专心-专注-专业SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 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:OnPaint();/ 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/内存页的结构体int num,time;Pro pM;精选优质文档-倾情为你奉上专心-专注-专业void Input()/输入函数，输入实际页号和实际页数int s;/随机数inti; srand(time(0);/每次运行时进程号不同，用来作为初始化随机数队列的种子 s = rand()%M;/coutn-随机产生指令流-n; for (i=0; iM; 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;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; /测试数据 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)/查找内存中是否存在要调入的页面int t;Pro*page=new ProN;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;/找最长时间的下标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;jM;j+)if(paget.num=pj.num/10) break;/当前页面开始往后查找在内存中的页帧号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)str1+=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;/记录缺页数int i=0;CString str3,tmp3;str3=;m_yemian.SetWindowText(_T(str3);while(i=0) +i;/找到相同的页面elsen+;paget.num=pi.num/10;/如果没有找到相同的页，则进行页面替换，缺页数加一/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);/t=(+t)%N;精选优质文档-倾情为你奉上专心-专注-专业MZL=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=0)pagek.time=0;for(p2=0;p2N;p2+)if(p2!=k)pagep2.time+;elseif(t1N)n+;paget.num=pi.num/10;/如果没有找到相同的页，则进行页面替换，缺页数加一+t1;t+;paget.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 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;/记录缺页数int t=0,t1=0;CString str3,tmp3;str3=;m_yemian.SetWindowText(_T(str3);while(i=0)i+;elseif(t1N)n+;paget.num=pi.num/10;/如果没有找到相同的页，则进行页面替换，缺页数加 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+)/查找下次访问距离最远的那个页面 if(tempCompfu(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;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 herevoid 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 CDialog: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(确认退出?);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;/记录缺页数while(i1=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=t2=0;int i2=0;for(j=0;jN;j+)/初始化页面基本情况pagej.num=-1;pagej.time=0;while(i2=0)pagek.time=0;for(p2=0;p2N;p2+)精选优质文档-倾情为你奉上专心-专注-专业if(p2!=k)pagep2.time+;elseif(ttN)n2+;paget2.num=pi2.num/10;/如果没有找到相同的页，则进行页面替换，缺页数加一+tt;t2+;paget2.time=0;elsen2+;t2=Max(page,N);paget2.num=pi2.num/10;paget2.time=0;for(p2=0;p2N;p2+)if(p2!=t2)pagep2.time+;i2+;s2=1-n2/M;/OPT 页面置换int i3=0;float n3=0;/记录缺页数int t3=0;int ttt=0;for(j=0;jN;j+)/初始化页面基本情况pagej.num=-1;pagej.time=j;while(i3=0)i3+;elseif(ttt=N)int temp=-1,cn;for(t3=0;t3N;t3+)/查找下次访问距离最远的那个页面 if(tempCompfu(page,i3,t3,p)temp=Compfu(page,i3,t3,p);cn=t3;pagecn.num=pi3.num/10;n3+;i3+;else break;s3=1-n3/M;CString st,kg,bt;st=;kg= ;bt=FIFO,LRU,OPT 命中率分别为：;st.Format(%s%s%-4f%s%-4f%s%-4f,bt,kg,s1,kg,s2,kg,s3);MessageBox(st,命中率比较);UpdateData(false);精选优质文档-倾情为你奉上专心-专注-专业10.10.课程设计小结课程设计小结 这次实验相对于以前来说比较不一样的是对于界面的制作，是一个比较新奇的体验。整体来说的话还算是比较简单，需要注意的是在编写程序之前要将课程设计的要求及解决思路。通过此次实验,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储和页面置换有了一定的了解。