操作系统课程设计报告课程名称：操作系统课程设计课程设计题目：页面置换算法学院：计算机科学与技术学院专业：科技小组成员: 庞思慧E01114081王蒙E01114161姚慧乔E01114349朱潮潮E01114408指导老师：***目录1 实验目的 (3)2 实验要求 (3)3 实验内容与步骤 (3)4 算法思想 (4)5 模块设计 (4)6 程序设计 (5)7 测试结果 (7)8 结果分析 (9)9 程序代码 (9)10 课程设计小结 (24)页面置换算法模拟设计1.实验目的（1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。

（2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。

（3）通过对几种置换算法命中率的比较，来对比他们的优缺点。

2.实验要求计算并输出下述各种算法在不同内存容量下的命中率。

A 先进先出的算法（FIFO）B 最近最少使用算法（LRU）C最佳淘汰算法（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次指令。

(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.算法思想在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。

但应将哪个页面调出，须根据一定的算法来确定。

通常，把选择换出页面的算法称为页面置换算法。

一个好的页面置换算法，应具有较低的页面更换频率。

从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。

1.先进先出算法FIFO：这是最早出现的置换算法。

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

2.最近最久未使用算法LRU（least recently used）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。

该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。

3.最佳淘汰算法OPT其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。

5.模块设计总模块图主程序图6.程序设计struct Pro //内存页的结构体{int num；//记录页面号int time；//页面从未被利用的时间};#define M 320 //定义指令条数Pro P[M]; //产生的随机指令数组void Input() //产生随机数{int s; //随机数int i;srand(time(0));s = rand()%M;//cout<<"\n------------随机产生指令流------------\n";for (i=0; i<M; i+=4) //产生指令队列{p[i].num=s; //任选一指令访问点mp[i+1].num=p[i].num+1; //顺序执行一条指令p[i+2].num=(int)((float)p[i].num*(rand()/(RAND_MAX+1.0)));//执行前地址指令m'p[i+3].num=p[i+2].num+1; //顺序执行一条指令s=(int)((float)(319-p[i+2].num)*(rand()/(RAND_MAX+1.0))) +p[i+2].num;}for(i=0;i<M;i++){p[i].time=0;}}int Search(int e,Pro*page1,int N) //查找内存中是否存在要调入的页面{int t;Pro*page=new Pro[N];page=page1;for(int i=0;i<N;i++){t=e/10;if(t==page[i].num)return i;}return -1;}int Max(Pro*page1,int N) //查找最久最久未被使用的页面{Pro*page=new Pro[N];page=page1;int e=page[0].time,i=0;while(i<N){if(e<page[i].time) e=page[i].time; //找最长时间i++;}for(i=0;i<N;i++)if(e==page[i].time) return i; //找最长时间的下标return -1;}int Compfu(Pro*page1,int i,int t,Pro p[M]) //找到最久不使用的页面{Pro*page=new Pro[N];page=page1;int count=0;for(int j=i;j<M;j++){if(page[t].num==p[j].num/10) break;//当前页面开始往后查找是否命中内存中的页号else ++count; //内存中的页面下次出现经过的页面数}return count;}7.测试结果选中算法，输入内存数点击计算点击命中率按钮点击退出按钮8.结果分析理论上，四种替换算法的命中率由高到底排列应该是OPT>LRU>CLOCK>FIFO。

实际上，在内存页面数较少（4~5页面）时，3种算法的命中率差别不大，可是50%左右。

在内存页面为7~25个页面之间时，3种算法的访内命中率大致在52%至87%之间变化。

在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。

从而算法之间的差别不大。

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 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 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 paintingSendMessage(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);}else{CDialog::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<iostream.h>#include<cstdlib>#include<ctime>#define M 320int N;struct Pro//内存页的结构体{int num,time;};Pro p[M];void Input()//输入函数，输入实际页号和实际页数{int s;//随机数int i;srand(time(0));//每次运行时进程号不同，用来作为初始化随机数队列的种子s = rand()%M;//cout<<"\n------------随机产生指令流------------\n";for (i=0; i<M; i+=4)//产生指令队列{p[i].num=s;//任选一指令访问点mp[i+1].num=p[i].num+1;//顺序执行一条指令p[i+2].num=(int)((float)p[i].num*(rand()/(RAND_MAX+1.0)));//执行前地址指令m'p[i+3].num=p[i+2].num+1;//顺序执行一条指令s=(int)((float)(319-p[i+2].num)*(rand()/(RAND_MAX+1.0))) + p[i+2].num;}for(i=0;i<M;i++){p[i].time=0;}/* p[0].num=10;p[1].num=22;p[2].num=33;p[3].num=44;p[4].num=50;p[5].num=13;p[6].num=32;p[7].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 Pro[N];page=page1;精选文库for(int i=0;i<N;i++){t=e/10;if(t==page[i].num)return i;}return -1;}int Max(Pro*page1,int N)//找出离现在时间最长的页面{Pro*page=new Pro[N];page=page1;int e=page[0].time,i=0;while(i<N){if(e<page[i].time) e=page[i].time;//找最长时间i++;}for(i=0;i<N;i++)if(e==page[i].time) return i;//找最长时间的下标return -1;}int Compfu(Pro*page1,int i,int t,Pro p[M])//找到最久不使用的页面{Pro*page=new Pro[N];page=page1;int count=0;for(int j=i;j<M;j++){if(page[t].num==p[j].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;i<M;i++){tmp1.Format("%-4d",p[i].num);str1+=tmp1;k++;if(k%16==0){str1+="\n\r\n\r\n\r";}}m_suiji.SetWindowText(_T(str1));//————————页面流————————CString str2,tmp2;tmp2=str2="";for(i=0;i<M;i++){tmp2.Format("%-4d",p[i].num/10);str2+=tmp2;k++;if(k%16==0){str2+="\n\r\n\r\n\r";}}m_suiji2.SetWindowText(_T(str2));Pro*page=new Pro[N];for(int j=0;j<N;j++)//初始化页面基本情况{page[j].num=-1;page[j].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(p[i].num,page,N)>=0) ++i;//找到相同的页面else{n++;page[t].num=p[i].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加一//——————————tmp3="";m_yemian.GetWindowText(_T(str3));for(int i=0;i<N;i++)if(page[i].num==-1){tmp3.Format("%s"," ");str3+=tmp3;}else{tmp3.Format("%-4d",page[i].num);str3+=tmp3;}str3+="\n\r\n\r\n\r";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<M){int k;k=Search(p[i].num,page,N);if(k>=0){page[k].time=0;for(p2=0;p2<N;p2++){if(p2!=k)page[p2].time++;}}else{if(t1<N){ n++;page[t].num=p[i].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加一++t1;t++;page[t].time=0;//——————————tmp3="";m_yemian.GetWindowText(_T(str3));for(int i=0;i<N;i++)if(page[i].num==-1){tmp3.Format("%s"," ");str3+=tmp3;}else{tmp3.Format("%-4d",page[i].num);str3+=tmp3;}str3+="\n\r\n\r\n\r";m_yemian.SetWindowText(_T(str3));//——————————}else{n++;t=Max(page,N);page[t].num=p[i].num/10;page[t].time=0;//——————————tmp3="";m_yemian.GetWindowText(_T(str3));for(int i=0;i<N;i++)if(page[i].num==-1){tmp3.Format("%s"," ");str3+=tmp3;}else{tmp3.Format("%-4d",page[i].num);str3+=tmp3;}str3+="\n\r\n\r\n\r";m_yemian.SetWindowText(_T(str3));//——————————}for(p2=0;p2<N;p2++){if(p2!=t)page[p2].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(p[i].num,page,N)>=0)i++;else{if(t1<N){ n++;page[t].num=p[i].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加1++t1;t++;i++;//——————————tmp3="";m_yemian.GetWindowText(_T(str3));for(int i=0;i<N;i++)if(page[i].num==-1){tmp3.Format("%s"," ");str3+=tmp3;}else{tmp3.Format("%-4d",page[i].num);str3+=tmp3;}str3+="\n\r\n\r\n\r";m_yemian.SetWindowText(_T(str3));//——————————}else if(t1>=N){int temp=-1,cn;for(t=0;t<N;t++)//查找下次访问距离最远的那个页面{if(temp<Compfu(page,i,t,p)){temp=Compfu(page,i,t,p);//下次命中经历的页面计数cn=t;//最远的页面号}}page[cn].num=p[i].num/10;n++;//——————————tmp3="";m_yemian.GetWindowText(_T(str3));for(int i=0;i<N;i++)if(page[i].num==-1){tmp3.Format("%s"," ");str3+=tmp3;}else{tmp3.Format("%-4d",page[i].num);str3+=tmp3;}str3+="\n\r\n\r\n\r";m_yemian.SetWindowText(_T(str3));//——————————i++;}else break;}}MZL=1-n/M;UpdateData(false);}void CMyDlg::OnRadio1(){// TODO: Add your control notification handler code here}void CMyDlg::OnRadio2(){// TODO: Add your control notification handler code here}void CMyDlg::OnRadio3(){// 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 into the mask.// TODO: Add your control notification handler code here}void CMyDlg::OnButton2(){// TODO: Add your control notification handler code hereMessageBox(_T("确认退出?"));ExitProcess(0);}void CMyDlg::OnButton3(){UpdateData(true);Pro*page=new Pro[N];for(int j=0;j<N;j++)//初始化页面基本情况{page[j].num=-1;page[j].time=j;}int t1=0;int i1=0;float n1=0;float s1,s2,s3;//FIFO页面置换n1=0;//记录缺页数while(i1<M){if(Search(p[i1].num,page,N)>=0) ++i1;//找到相同的页面else{n1++;page[t1].num=p[i1].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;j<N;j++)//初始化页面基本情况{page[j].num=-1;page[j].time=0;}while(i2<M){int k;k=Search(p[i2].num,page,N);if(k>=0){page[k].time=0;for(p2=0;p2<N;p2++){if(p2!=k)page[p2].time++;}}else{if(tt<N){n2++;page[t2].num=p[i2].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加一++tt;t2++;page[t2].time=0;}else{n2++;t2=Max(page,N);page[t2].num=p[i2].num/10;page[t2].time=0;}for(p2=0;p2<N;p2++){if(p2!=t2)page[p2].time++;}}i2++;}s2=1-n2/M;//OPT页面置换int i3=0;float n3=0;//记录缺页数int t3=0;int ttt=0;for(j=0;j<N;j++)//初始化页面基本情况{page[j].num=-1;page[j].time=j;}while(i3<M){if(Search(p[i3].num,page,N)>=0)i3++;else{if(ttt<N){ n3++;page[t3].num=p[i3].num/10;//如果没有找到相同的页，则进行页面替换，缺页数加一++ttt;t3++;i3++;}else if(ttt>=N){int temp=-1,cn;for(t3=0;t3<N;t3++)//查找下次访问距离最远的那个页面{if(temp<Compfu(page,i3,t3,p)){temp=Compfu(page,i3,t3,p);cn=t3;}}page[cn].num=p[i3].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.课程设计小结这次实验相对于以前来说比较不一样的是对于界面的制作，是一个比较新奇的体验。