页面置换算法实验报告

1操作系统课程设计报告课程名称：操作系统课程设计课程设计题目：页面置换算法学院：计算机科学与技术学院专业：科技小组成员:庞思慧E01114081王蒙E01114161姚慧乔E01114349朱潮潮E01114408指导老师：邱剑锋2目录1实验目的.................................................................................................................................32实验要求.................................................................................................................................33实验内容与步骤.....................................................................................................................34算法思想.................................................................................................................................45模块设计.................................................................................................................................46程序设计.................................................................................................................................57测试结果.................................................................................................................................78结果分析.................................................................................................................................99程序代码.................................................................................................................................910课程设计小结.......................................................................................................................243页面置换算法模拟设计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页；4C.用户虚存容量为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（leastrecentlyused）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3.最佳淘汰算法OPT其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。5.模块设计5入口产生随机数、要调入的页面、离现在处理时间最长的页面、最长的页面初始化页面情况t1N根据选择的算法进行置换，缺页数加1计算缺页率，并输出数据结束YN直接存入内存总模块图主程序图开始输入内存数调用各种置换算法，ＦＩＦＯ，ＬＲＵ，ＯＰＴ，并显示地址流、页面流、页面置换过程和命中率命中率比较结束66.程序设计structPro//内存页的结构体{intnum；//记录页面号inttime；//页面从未被利用的时间};#defineM320//定义指令条数ProP[M];//产生的随机指令数组voidInput()//产生随机数{ints;//随机数inti;srand(time(0));s=rand()%M;//cout\n------------随机产生指令流------------\n;for(i=0;iM;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;iM;i++){p[i].time=0;}}intSearch(inte,Pro*page1,intN)//查找内存中是否存在要调入的页面{intt;Pro*page=newPro[N];page=page1;for(inti=0;iN;i++){t=e/10;if(t==page[i].num)returni;7}return-1;}intMax(Pro*page1,intN)//查找最久最久未被使用的页面{Pro*page=newPro[N];page=page1;inte=page[0].time,i=0;while(iN){if(epage[i].time)e=page[i].time;//找最长时间i++;}for(i=0;iN;i++)if(e==page[i].time)returni;//找最长时间的下标return-1;}intCompfu(Pro*page1,inti,intt,Prop[M])//找到最久不使用的页面{Pro*page=newPro[N];page=page1;intcount=0;for(intj=i;jM;j++){if(page[t].num==p[j].num/10)break;//当前页面开始往后查找是否命中内存中的页号else++count;//内存中的页面下次出现经过的页面数}returncount;}7.测试结果选中算法，输入内存数点击计算89点击命中率按钮点击退出按钮8.结果分析理论上，四种替换算法的命中率由高到底排列应该是OPTLRUCLOCKFIFO。实际上，在内存页面数较少（4~5页面）时，3种算法的命中率差别不大，可是50%左右。在内存页面为7~25个页面之间时，3种算法的访内命中率大致在52%至87%之间变化。在内存页面为1025~32个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。从而算法之间的差别不大。9.程序代码//页面置换算法模拟设计Dlg.cpp:implementationfile#includestdafx.h#include页面置换算法模拟设计.h#include页面置换算法模拟设计Dlg.h#ifdef_DEBUG#definenewDEBUG_NEW#undefTHIS_FILEstaticcharTHIS_FILE[]=__FILE__;#endif///////////////////////////////////////////////////////////////////////////////CMyDlgdialogCMyDlg::CMyDlg(CWnd*pParent/*=NULL*/):CDialog(CMyDlg::IDD,pParent){//{{AFX_DATA_INIT(CMyDlg)m_iFifo=0;N=0;MZL=0.0;//}}AFX_DATA_INIT//NotethatLoadIcondoesnotrequireasubsequentDestroyIconinWin32m_hIcon=AfxGetApp()-LoadIcon(IDR_MAINFRAME);}voidCMyDlg::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}11BEGIN_MESSAGE_MAP(CMyDlg,CDialog)//{{AFX_MSG_MAP(CMyDlg)ON_WM_PAINT()