Word版可编辑-操作系统课程设计报告DOC精心整理.doc

课程设计报告题 目： 模拟请求页式管理 课程名称： 计算机操作系统 学 院： 信息工程学院 专 业： 计算机科学与技术 班 级： 14计本（1） 学生姓名： * * * 学 号： 201403031* 指导教师： * * 成 绩： 开课时间： 2016-2017 学年 一 学期 模拟请求页式管理第1章 需求分析1.1设计要求请求页式管理是一种常用的虚拟存储管理技术。本设计通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。本实验要求用Vc或其他高级语言编写和调试。编写程序实现： （1）先进先出页面置换算法（FIFO）（2）最近最久未使用页面置换算法（LRU）最佳置换页面置换算法（OPT）设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。1.2解决方案 首先确定实现语言使用c#实现图形化界面，后确定要实现哪些功能，比如算法选择，页面添加，模拟控制。然后确定输出结构以便于程序的测试和验证。将基本框架建立后再进行编程。编程前进行算法结构分析最后编程实现。1.3算法实现原理1、先进先出置换算法（FIFO）：发生缺页中断时按照页面进入内存顺序总是淘汰最先进入内存的页面。2、最近最久未使用置换算法（LRU）：发生缺页中断时总是淘汰存在内存中最长时间未被使用的页面。3、最佳置换算法（OPT）：发生缺页中断时若一个或几个页面将来将不会被调用则按先进先出原则淘汰页面，若将来都有调用则比较调用时刻选择最远时刻页面淘汰。4、缺页率：缺页次数占页面调用次数的百分比。第2章 概要设计2.1数据设计常变量：调用页面最大数量（MaxN），内存最大页面数（MaxM）待调用页面数组：page_ddMaxN存放等待调用的页面号页面数组专用指针 page_p，用于指向page_dd数组中正需调入内存的页号内存块数组：MemeryMaxM，存放内存当前存放的页号缺页计数器：count，记录缺页次数内存块状态数组：M1MaxN,M2MaxN,M3MaxN，记录每次页面调用结束后内存各块的状态缺页记录数组sMaxN，用于记录页面调用时是否产生缺页中断，初始化为是2.2函数设计1、页面添加函数：void btnAdd_Click(object sender, EventArgs e)用于实现通过点击按钮实现数据输入。2、内存初始化函数：init(int a, int b,int m1,intm2,intm3)参数有页面数组、内存数组、状态数组，采用先进先出算法对内存先进行装满服务于先进先出页面置换函数和最佳置换函数。3、 输出函数：void display(inta,intm1,intm2,intm3,charc)用于输出模拟结果，参数有页面数组，内存数组，状态数组，缺页记录数组。再模拟之后调用。4、模拟控制函数：void btnmo_Click(object sender, EventArgs e）用于实现通过单击模拟按钮，根据用户所选算法进行模拟并显示结果。5、先进先出算法模拟函数：void FIFO(int a, int b,intm1,intm2,intm3,char s)用于实现先进先出算法模拟，参数有页面数组，内存数组、内存状态记录数组，缺页记录数组。在模拟函数中调用。6、 最近最久未使用算法模拟函数：void LRU(int a, int b, int m1, int m2, int m3, char s)用于实现最近最久未使用算法模拟，参数有页面数组，内存数组，内存状态记录数组，缺页记录数组。在模拟函数中被调用。7、 最近最久未使用函数辅助函数：void LUR_I(int a,int e)用于对最近最久未使用算法中所用辅助数组（记录页面存在时长）进行调整，参数有辅助数组及需调整的数据下标。在最近最久未使用函数中调用。8、最佳置换算法模拟函数：void OPT(int a, int b, int m1, int m2, int m3, char s)用于模拟最佳置换算法。参数有页面数组，内存数组，内存状态记录数组，缺页记录数组。在模拟函数中被调用。9、 最佳置换算法辅助函数：void OPT_F(int a, int e)用于对最佳置换算法中的辅助数组进行调整。参数有辅助数组，需调整数据下标。在最佳置换算法中被调用。10、 重置函数：void btncz_Click(object sender, EventArgs e)用于重新选择算法进行新的模拟。2.3主要算法设计1、初始化函数算法：第一步：将第一个页面调入内存，调整最佳置换算法辅助数组，缺页计数器加一，保存内存数组状态。第二步：调用下一个页面并判断内存中是否有本页面有转第三步，无转第四步。第三步：更改缺页数组对应下标值，记录当前内存状态，调整最佳置换算法辅助数组，页面指针指向下一页。第四步：将页面调入内存，调整最佳置换算法辅助函数，缺页计数器加一，保存内存数组状态。若内存尚不满转第一步。具体见图1初始化算法流程图。图1 初始化算法流程图2、 先进先出页面置换算法：第一步：检查内存中是否已有需调用页面，有则转第二步，无则转第三步。第二步：记录当前内存状态，修改缺页数组对应下标值。第三步：内存中无需要调用的页面，进行出队操作，然后进行入队操作，记录内存块状态，缺页计数器加一。第四步：若页面数组未被调用结束转第一步。具体见图2先进先出算法流程图。图2 先进先出算法流程图3、 最近最久未使用置换算法：第一步：将页面调入内存，记录内存状态，缺页计数器加一，调整辅助数组，页面指针加一。第二步：检查内存中是否已有所需页面，有转第三步，无转第一步。第三步：修改缺页数组对应下标记录，记录内存状态，调整辅助数组，页面指针加一。第四步：内存是否已满，无则转第一步，是则转第五步。第五步：检查内存中是否有所需页面，有则记录当前内存状态，修改缺页数组对应下标值。无则转第六步。第六步：检查辅助数组找出最大值并记录其下标，置换内存中对应下标的数据，调整辅助数组，缺页计数器加一。第七步：页面是否调用结束未结束则转第五步。具体见图3最近最久未使用算法流程图。图3 最近最久未使用算法4、 最佳置换算法：第一步：检查内存中是否已有所需页面，有则记录内存状态，修改缺页数组对应下标数值。无则转第二步。第二步：判断内存中各页面的未来调用情况，记录是否还有调用，若有则记录调用时刻。第三步：分析调用情况，内存中页面都在将来不会被调用转第四步，有一个被调用转第五步，有两个被调用转第六步，全被调用转第七步。第四步:查找辅助数组找到内存中存在时间最长的页面进行置换，修改内存状态，缺页计数器加一，修改辅助数组。第五步：查找到不会被调用的页面，并根据辅助数组选择最早进入内存的页面将其置换。修改内存状态，缺页计数器加一，修改辅助数组。第六步：查找辅助数组找到将来不需要在调用的页面将其置换，修改辅助数组，记录内存状态，缺页计数器加一。第七步：查找辅助数组，找寻最晚被调用的页面，将其置换。记录内存状态，修改辅助数组，缺页计数器加一。第八步：页面是否调用完成，否则转第一步。具体见图4最佳置换算法流程图图4 最佳置换算法流程图2.4界面设计采用c# 设计windows窗体应用程序，使用下拉列表框选择算法，通过按钮添加待调用的页面。通过文本控件显示模拟结果。显示样式：第一行：算法名称； 第二行：调用页面顺序； 第三行至第五行显示内存在每调用一次页面后的状态； 第六行：是否缺页； 最后一行显示缺页率；第3章 详细设计与实现3.1函数设计 1、添加按钮功能实现代码主要功能：实现单击一次添加一个调用页面，并给出相应的提示，如正在输入的是第几次调度页面，在输入为空时能够弹出对话框提示用户，在输入完成时为避免数组越界应在输入完成时隐藏；输入过程中始终保证时输入焦点。private void btnAdd_Click(object sender, EventArgs e) if (txtAdd.Text != )/输入不为空才能继续输入 page_ddi_add = Convert.ToInt32(txtAdd.Text); /*将输入值赋值给页面数组*/ txtShow.Text += txtAdd.Text + ; /*显示供用户查阅*/ i_add+; txtAdd.Clear(); /*清空*/ if (i_add = MaxN)/输入结束时 txtAdd.ReadOnly = true;/不允许继续输入 btnAdd.Hide();/按钮隐藏 return; txtAdd.Focus();/设置为输入焦点 label2.Text = 第 + (i_add + 1) + 次调度页面：; /*提示用户正在输入的是第几次调度页面*/ /*输入为空则弹出对话框提示用户输入为空*/ else MessageBox.Show(请输入调用页面！, 输入为空, MessageBoxButtons.OK, MessageBoxIcon.Warning); txtAdd.Focus(); 2、 初始化函数主要功能：将内存一先进先出方式填满，并记录每个页面进入时间，服务于先进先出页面置换算法和最佳置换算法。 void init(int a, int b,int m1,intm2,intm3) /*内存未满时循环*/ for (int i = 0; i MaxM&page_p MaxN ; i+) bi = apage_p;/调入内存 /调整辅助数组将刚进入内存的页面的对应时间 OPT_F (O_Q ,i)； count+;/缺页计数器加一 m1page_p = b0;/保存内存状态 m2page_p = b1; m3page_p = b2; page_p+;/调用下一页面 /检查内存中是否原先就有需要的页面； for (int j = 0; j = i&page_p MaxN ; j+) if (bj = apage_p) /找到这样的页面 spage_p = F;/缺页数组对应数据更改 m1page_p = b0;/记录内存状态 m2page_p = b1; m3page_p = b2; OPT_F(O_Q, -1);/调整最佳置换算法辅助函数 page_p+;/调用下一页 j = -1;/重新开始寻找 3、 先进先出页面置换函数主要功能：根据先进先出算法要求在产生缺页中断时采用先进先出方式确定淘汰页面，并在每次页面调用时记录下内存状态，缺页次数；采用循环队列使得每次出队的一定是最先进入内存的。 private void FIFO(int a, int b,intm1,intm2,intm3,char s) int Fpage_p = page_p; int front, rear; /定义队列对手和对尾指针并初始化 front = 0; rear = MaxM - 1; int sa; /定义页面处理标志为1则表明此页面已处理 for (; Fpage_p MaxN; Fpage_p+) /从当前位置开始往后扫描 sa = 0; for (int i = 0; i MaxM; i+) /检查内存中是否已有要调用的页面。 /有需要的页面则保存内存状态，修改缺页数组对应位值 if (bi = aFpage_p) m1Fpage_p = b0; m2Fpage_p = b1; m3Fpage_p = b2; sFpage_p = F; sa = 1; break; /找到就退出应为只可能有一个符合页面 if (sa = 0) /未找到一致页面产生缺页中断进行出队操作淘汰最早进入内存的页面/并记录内存状态，计数器加一。 front = (front + 1) % MaxM; rear = (rear + 1) % MaxM; brear = aFpage_p; m1Fpage_p = b0; m2Fpage_p = b1; m3Fpage_p = b2; count+; else continue; /内存原有一样的页面则结束本次循环 4、 最近最久未使用函数 主要功能：实现对最近最久页面置换算法的模拟，记录缺页次数和每次页面对应的内存状态。 private void LRU(int a, int b, int m1, int m2, int m3, char s) int L_Q = new intMaxM3,3,3;/辅助数组记录页面存在时间，初始值都是3，每次对应位置有新页面进入就刷/新为1，比原来值小的加一大于原来值得不变 int sa;/页面已调用标志 for (int i = 0; i MaxM & page_p MaxN; i+) /内存不满时执行将内存装满因其于先进先出不符合故不能调用初始化函数 bi = apage_p;/调入内存 count+; m1page_p = b0;/保存内存状态 m2page_p = b1; m3page_p = b2; LUR_I(L_Q, i);/调整辅助数组 page_p+; for (int j = 0; j = i & page_p MaxN ; j+) /判断已在内存中的页面中是否有与将要调用页面一致的页面 if (bj = apage_p) /有则修改缺页状态函数并记录当前内存状态 spage_p = F; m1page_p = b0; m2page_p = b1; m3page_p = b2; LUR_I(L_Q, j); page_p+; j = -1; for (; page_p MaxN; page_p+) /内存装满后从当前位置向后调用页面 sa = 0; for (int i = 0; i MaxM; i+)/检查内存中是否已有要调用的页面。 if (bi = apage_p) /有则记录内存状态修改缺页数组调整辅助函数 m1page_p = b0; m2page_p = b1; m3page_p = b2; spage_p = F; LUR_I(L_Q, i); sa = 1; break; if (sa = 0) for (int i = 0; i MaxM; i+) /产生缺页中断 if (L_Qi = 3)/查找辅助数组找到值为3的位置对应下标并 /替换此下标代表的内存块页面并记录内存状态，调整辅助函数，计数器加一 bi = apage_p; m1page_p = b0; m2page_p = b1; m3page_p = b2; LUR_I(L_Q, i); break; count+; else continue; 5、 最佳置换算法 主要功能：模拟实现最佳页面置换算法，淘汰内存中永远不会调用的页面，如果有多个则采用先进先出原则进行置换，若多个页面在以后都有调用则淘汰最后被调用的页面，记录每次页面调用后内存状态，记录缺页中断数 private void OPT(inta,intb,intm1,intm2,intm3,chars) int sa;/页面调用处理标志 int O_p;/页面数组辅助指针 int Ocount;/辅助计数变量 int OPT_I=new int MaxM -1 ,-1 ,-1 ;/辅助数组记录页面将来调用与否 int OPT_J=new int MaxMMaxN ,MaxN ,MaxN ;/辅助数组记录页面将来被调用时刻 for (; page_p MaxN; page_p+) for (int i = 0; i MaxM; i+) OPT_Ii = -1;/刷新状态数组 OPT_Ji = MaxN; sa = 0; for (int i = 0; i MaxM; i+)/检查内存中是否已有要调用的页面。 /将要调用页面存在于内存中 if (bi = apage_p) /记录内存状态修改缺页数组，调整辅助数组 m1page_p = b0; m2page_p = b1; m3page_p = b2; OPT_F(O_Q,-1); spage_p = F; sa = 1; break; if (sa = 0)/缺页 Ocount = 0; for (int i = 0; i MaxM; i+) /向后查找页面调用情况用辅助数组记录 O_p = page_p + 1; for (; O_p MaxN; O_p+) if (bi = aO_p) Ocount+; OPT_Ii = 1;/表示下标代表页面将来会被调用 OPT_Ji = O_p;/表示其调用时刻 break; switch (Ocount) case 0:/全部页面以后都不会再度调用，查找辅助函数替换最先进入内存数组 int temp = 0; for (int i = 0; i O_Qtemp) temp = i; btemp = apage_p; m1page_p = b0; m2page_p = b1; m3page_p = b2; OPT_F (O_Q ,temp); count+; break; case 1:/有一个页面将在以后调用，比较两个不会被调用的页面谁先进入内存并置换之 temp = 0; for (int i = 0; i O_Qtemp) temp = i; btemp = apage_p; m1page_p = b0; m2page_p = b1; m3page_p = b2; OPT_F (O_Q ,temp); count+; break; case 2: /有两个页面将在以后被调用，直接淘汰将来不会调用的那个 for (int i = 0; i MaxM; i+) if (OPT_Ii = -1) bi = apage_p; m1page_p = b0; m2page_p = b1; m3page_p = b2; OPT_F(O_Q, i); count+; break; case 3: /所有页面都将被调用，查找辅助函数，得到最晚被调用的页面并淘汰之 int p = 0; for (int i = 0; i OPT_Jp) p = i; bp = apage_p; m1page_p = b0; m2page_p = b1; m3page_p = b2; OPT_F(O_Q, p); count+; break; 6、 输出函数 主要功能：按既定形式输出模拟结果，并计算缺页率并输出 private void display(inta,intm1,intm2,intm3,charc) lblshow.Text = ; lblshow.Text =comboBox1.Text + :n;/输出算法名称 for (int i = 0; i MaxN; i+) /输出页面调用输出顺序 lblshow.Text += ai.ToString()+ ; lblshow.Text += n; for (int i = 0; i MaxN; i+) /输出1号内存块变换情况 if (m1i = -1) lblshow.Text += ; else lblshow.Text += m1i.ToString() + ; lblshow.Text += n; for (int i = 0; i MaxN; i+) /输出2号内存块变换情况 if (m2i = -1) lblshow.Text += ; else lblshow.Text += m2i.ToString() + ; lblshow.Text += n; for (int i = 0; i MaxN; i+) /输出3号内存块变换情况 if (m3i = -1) lblshow.Text += ; else lblshow.Text += m3i.ToString() + ; lblshow.Text += n; for (int i = 0; i MaxN; i+) /输出缺页情况 lblshow.Text += c i + ; /计算并输出缺页率 lblshow.Text += n缺页率：+ count*100/MaxN +%; 3.2界面设计程序执行开始显示本程序具体模拟内容如图5进入模拟界面所示图5 进入模拟界面点击开始模拟按钮进入主界面，如图6所示主界面包含提示文本如“算法选择”，“第1次调度页面”、“页面调度顺序”。包含三个按钮分别为添加按钮用于添加调用页面，重置按钮清除当前操作，以便重新模拟。模拟按钮，单击即可开始模拟。图6 模拟主界面第4章 调试分析4.1实验步骤及结果第一步：运行程序显示模拟入口如图7模拟入口所示 图7 模拟入口第二步：单击开始模拟进入主界面，可以看出程序默认是选择先进先出页面置换算法，显示页面调用顺序处不可随意修改。如图8主界面所示图8 主界面第三步：选择先进先出算法进行模拟，添加页面调度序列如图9所示。期间若输入空字符则弹出对话框如图10所示，点击确定继续输入，输入完成则禁止输入如图11所示；图9 页面添加图10 输入为空警告对话框图11 输入结束第四步：单击模拟按钮可以看见模拟结果如图12所示。按照算法原理页面置换过程应为：其中3，5，1号页面进入内存是因为原本内存中没有所以产生了三次中断。2号页面调用时产生缺页中断，这是3号页面最先进入内存故将3号页面置换出去。3号页面调用时产生缺页中断，此时5号在内存中时间最长故将5号页面置换出去1号页面进入时，内存中本来就有故不产生中断。5号页面进入时产生中断，此时1号页面存留时间最长故置换出去。1号页面调用时产生中断，此时2号页面存留时间最长故置换出去。2号页面调用时产生中断，将3号页面置换出去。3号页面调用时产生中断，置换处5号。4号页面调用时产生中断，置换出1号页面。1号页面调用产生中断置换出2号。3号页面调用不产生中断。1号调用不产生中断。5号页面调用置换出3号。缺页次数为12次缺页率为80%。程序运行结果正确。图12 先进先出算法模拟结果第五步：单击重置按钮，将算法改为最近最久未使用算法并单击模拟按钮，显示结果如图13所示。按照算法原理页面置换过程应为：其中3，5，1号页面进入内存是因为原本内存中没有所以产生了三次中断。2号页面调用时产生缺页中断，这是3号页面最先进入内存且未被使用故将3号页面置换出去。3号页面调用时产生缺页中断，此时5号在内存中时间最长且近期未调用故将5号页面置换出去。1号页面进入时，内存中本来就有故不产生中断。5号页面进入时产生中断，此时2号页面存留时间最长并未使用故置换出去。1号页面调用时不产生中断。2号页面调用时产生中断，将3号页面置换出去。3号页面调用时产生中断，置换处5号。4号页面调用时产生中断，置换出1号页面。1号页面调用产生中断置换出2号。3号页面调用不产生中断。1号调用不产生中断。5号页面调用置换出4号。缺页次数为11次缺页率为73%。程序运行结果正确。图13 最近最久未使用算法模拟第六步：单击重置按钮，将算法改为最佳置换算法并单击模拟按钮，显示结果如图14所示。按照算法原理页面置换过程应为：其中3，5，1号页面进入内存是因为原本内存中没有所以产生了三次中断。2号页面调用时产生缺页中断，这是5号页面最晚被再次调用故将5号页面置换出去。3号页面调用时不产生缺页中断。1号页面进入时，内存中本来就有故不产生中断。5号页面进入时产生中断，此时3号页面最晚被再次调用故置换出去。1号页面调用时不产生中断。2号页面调用时不产生中断。3号页面调用时产生中断，置换出2号。4号页面调用时产生中断，置换出5号页面。1号页面调用不产生中断。3号页面调用不产生中断。1号调用不产生中断。5号页面调用置换出1号。缺页次数为8次缺页率为53%。程序运行结果正确。图14 最佳置换算法总结*参考资料1.王万森,孙卫真，温绍洁，霍其润，汪国安.计算机操作系统原理北京：高等教育出版社，20072.罗福强,白忠建,杨剑VisualC#.NET程序设计北京：人民邮电出版社，2012附录using System;using System.Collections.Generic;using System.Linq;using System.Windows.Forms;namespace yeshi static class Program / / 应用程序的主入口点。 / STAThread static void Main() Ap