页面置换算法实验报告.docx

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

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

3、重复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（lea

5、strecentlyused）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3.最佳淘汰算法OPT其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。5.模块设计 总模块图 主程序图6.程序设计struct Pro /内存页的结构体int num； /记录页面号int time； /页面从未被利用的时间;#defi

6、ne 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)(f

7、loat)(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=pa

8、ge1; 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种算法的命中率差别不大，可是5

9、0%左右。在内存页面为725个页面之间时，3种算法的访内命中率大致在52%至87%之间变化。在内存页面为2532个页面时，由于用户进程的所有指令基本上都已装入内存，从而命中率已较大。从而算法之间的差别不大。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/

10、 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 Win32 m_hIcon = AfxGetApp()-LoadIcon(IDR_MAINFRAME);void CMyDlg:DoDataExchange(CD

11、ataExchange* 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_MAPBEGIN

12、_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, O

13、nButton2) 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 dialog SetIcon(m_hIcon, TRUE); /

14、 Set big icon SetIcon(m_hIcon, FALSE); / Set small icon / TODO: Add extra initialization here return 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 mo

15、del,/ 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 rectangle int cxIcon = GetSystemMetrics(SM_CXICON); int cyIcon = GetSys

16、temMetrics(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); else CDialog:OnPaint(); / The system calls this to obtain the cursor to display while the user drags/ the minimized

17、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; /随机数 int i; srand(time(0); /每次运行时进程号不同，用来作为初始化随机数队列的种子 s = rand()%M; /coutn-随机产生指令流-n; for (i=0; iM; i+=4) /产生指令队列

18、 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

19、.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

20、; 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; /当前页面开始往后查找在内存中的

21、页帧号 else +count; return count;void CMyDlg:OnButton1() / TODO: Add your control notification handler code here UpdateData(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(str

22、1); /页面流 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,tm

23、p3; str3=; m_yemian.SetWindowText(_T(str3); while(i=0) +i;/找到相同的页面 else n+; 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; else tmp3.Format(%-4d,pagei.num); str3+=tmp3; str3+=nrnrnr; m_yemian.

24、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+; else if(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; else tmp3.Format(%