《页面置换算法实验报告》由会员分享，可在线阅读，更多相关《页面置换算法实验报告（24页珍藏版）》请在金锄头文库上搜索。
1、操作系统课程设计报告课程名称：操作系统课程设计课程设计题目：页面置换算法学院：计算机科学与技术学院专业：科技小组成员:庞思慧E01114081王蒙E01114161姚慧乔E01114349朱潮潮E01114408指导老师：目录1实验目的 32实验要求 33实验内容与步骤 34算法思想 45模块设计 46程序设计 57测试结果 78结果分析 99程序代码 910课程设计小结 24页面置换算法模拟设计1. 实验目的（1）通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。（2）掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种 算法来模拟实现。（3）通过对几种置换算
2、法命中率的比较，来对比他们的优缺点。2. 实验要求计算并输出下述各种算法在不同内存容量下的命中率。A 先进先出的算法（FIFO）B最近最少使用算法（LRU）C最佳淘汰算法（OPT）3. 实验内容与步骤（1）通过随机数产生一个指令序列，共320条指令，具体的实施方法是：A. 0, 319的指令地址之间随机选取一起点M;氏顺序执行一条指令，即执行地址为M+1的指令；C. 在前地址0, M+1中随机选取一条指令并执行，该指令的地址为M;D. 顺序执行一条指令，其地址为M +1；E. 在后地址M +2, 319中随机选取一条指令并执行；F. 重复AE，直到执行320次指令。（2）指令序列变换成页地址流
3、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）： 算法的基本思想：当需
5、要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过 的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反 过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3. 最佳淘汰算法OPT 其所选择的被淘汰的页面将是以后永不使用，或许是未来最长时间内不使用的页面，该算法 可保证获得最低的淘汰率，但在实际运用中无法实现，可用来评价其他算法的命中率。5.模块设计总模块图主程序图6.程序设计struct Proint num；int time； ;/内存页的结构体/记录页面号/定义指令条数/产生的随机指令数组/页面从未被利用的时间#define M 320
6、 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;/任选一指令访问点 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.num)*(rand()/(RAND_MAX+1.0)
7、 + 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
8、=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;jLoadIcon(IDR_MAINFRAME);void CMyDlg:DoDataExchange(CDataExchange* pDX) CDialog:DoDataExchange(pDX); /AFX_DATA_
9、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_MESSAGE_MAP(CMyDlg, CDialog)/AFX_MSG_MAP(CMyDlg)ON_WM_PAI
10、NT()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_MAPE
11、ND_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 T
