页面置换算法的实验报告.doc

操作系统课程设计报告院（系）： 计算机工程学院 专业： 计算机科学与技术专业 学生姓名: * 班级：*学号: * 题目： 页面置换算法 起迄日期: * 设计地点: * 指 导 教 师: * 一、 课程设计目的操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。 课程设计是学生学习完计算机操作系统课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 二、 课程设计内容 模拟仿真请求分页调度算法OPT、FIFO、LRU、LFU、CLOCK等模拟页面调度算法，并提供性能比较分析功能。三、 系统分析与设计1、系统分析由于分区式管理尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高。再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程的大小或内存可用空间的限制。而且分区式管理也不利于程序段和数据段的共享。页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存利用率而提出来的页式管理有动态页式管理和静态页式管理之分，动态页式管理是在静态页式管理的基础上发展起来的。请求页式管理属于动态页式管理中的一种，它的地址变换过程与静态页式管理时的相同，也是通过页表查出相应的页面号，由页面号与页内相对地址相加而得到实际物理地址。有关的地址变换部分是由硬件自动完成的。当硬件变换机构发现所要求的页不在内存时，产生缺页中断信号，由中断处理程序做出相应的处理。中断处理程序是由软件实现的。除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外，还要从外存读入所需要的虚页。这个过程要启动相应的外存和涉及到文件系统。因此，请求页式管理是一个十分复杂的过程，内存利用率的提高是以牺牲系统开销的代价换来的。这里用到了置换算法。它是在内存中没有空闲页面时被调用。目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率低的页，将它们移出内存。调页策略 1)何时调入页面如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。 2)请求调页策略 当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。 从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入 所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。 (2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。 (3)UNIX方式。2、系统设计：在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_ReplacementAlgorithms)。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。则有以下页面置换方法：1）、先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。2）、最近最久未使用页面置换算法LRU（leastrecentlyused）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3）、最佳页面置换置换算法（OPT）其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。4）、简单Clock置换算法该算法是当某页被访问时，其访问位被设置为1，置换算法选择某一页淘汰时，只需检查页的访问位，如果是0，则将该页换出，如果为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列的最后一个页面时，若其访问位仍为1，则再返回到队首的第一个页面。 5）最少使用置换算法（LFU）该置换算法选择在最近一段时间内使用最少的页面作为淘汰页。LFU算法并不能真正的反映出页面的使用情况。 3、模块设计：系统功能结构图 运行程序页面置换算法的主界面输入页面序列和物理块数OPTLRUFIFO简单ClockLFU 性能分析4、数据结构说明：程序中用到了structstruct Pagetime /字段 private int num;/页面的序号 private int timer;/不同的算法有不同的含义 private int count;/页面访问次数 /属性 public int Num get return num; set num = value; public int Timer get return timer; set timer = value; public int Count get return count; set count = value; 程序中用到了字符串和数组public string page;/用于接收页面序列 public string strsize;/用于接收物理块数page = page_textBox.Text; strsize = size_textbox.Text; /声明struct数组，用于存储内存中页面的信息 Pagetime X = new Pagetime20;5、算法流程图：开始输入页面序列输入物理块数调用各种置换算法，简单，并输出结果性能分析结束主流程图 入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择最先进入的页面作为淘汰页计算缺页率，并输出数据 结束置u为1将页面放到空闲的物理块处ipage.LengthYYYNNNFIFO置换算法的流程图 入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择以后最长时间内（未来）不在被访问的页面作为淘汰页计算缺页率，并输出数据 结束置u为1，重新获取离该页面最近的下个相同页面的位置，为Timer将页面放到空闲的物理块处，获取Timeripage.LengthYYYNNNOPT页面置换算法入口初始化数据指向下一个页面页面访问位=0选择该页淘汰置页面访问位为0YN计算缺页率，并输出数据结束简单Clock置换算法 入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择最近最久未使用的页面作为淘汰页计算缺页率，并输出数据 结束置u为1，并置其Timer为0将页面放到空闲的物理块处ipage.LengthYYYNNNLRU页面置换算法 入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择访问次数最少的页面作为淘汰页计算缺页率，并输出数据 结束置u为1，置访问次数加1将页面放到空闲的物理块处ipage.LengthYYYNNNLFU页面置换算法四、模块调试与系统测试1、模块调试l 输入的页面序列是数字串，输入的物理块数是数字，且设置其范围在10之内。l 输出的形式是字符串。l 页面置换算法是选择页面换出的算法，通过OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用置换算法）、简单Clock置换算法、LFU（最少使用置换算法）计算每种置换算法的访问次数、页面置换的次数、缺页中断的次数和缺页率，然后进行性能分析。2、系统测试l 测试方法：黒盒测试l 测试报告：测试数据描述测试数据输入预期结果输出实际结果输出是否符合预定结果随机输入页面序列，物理块数页面序列：7012030423032120物理块数：3得到提示，提示输入成功出来提示框，提示输入成功符合预定结果随机输入页面序列，物理块数页面序列：7013e物理块数：3得到提示，提示输入错误出来提示框，提示“输入错误，输入的页面序列必须为数字”符合预定结果随机输入页面序列，物理块数页面序列：7102635物理块数：e得到提示，提示输入错误出来提示框，提示“输入错误，输入的物理块必须为数字，且物理块数必须在10之内”符合预定结果选择页面置换算法，按“置换结果”按钮在未输入页面序列和物理块数时选择算法，按“置换结果按钮”得到提示出来提示，提示“输入的页面序列或物理块数不能为空”符合预定结果选择页面置换算法，按“置换结果”按钮在页面序列和物理块数输入成功时，选择算法，按“置换结果”按钮在可视化界面上，会得到相应的结果输出在可视化界面上，有相应算法的结果输出符合预定结果选择“性能分析”按钮在五种置换算法没有全部得到结果时，按“性能分析”按钮得到提示得到提示框，提示“必须在各算法都得到结果时在进行性能分析”符合预定结果 3、调试分析：页面置换算法是用的可视化的形式，在刚开始编程时遇到的问题如何接收数据和显示数据，在接收页面序列的数据时我用的是字符串的形式，因为在C#中可以像数据一样访问字符串中的数据，例如有字符串S，访问第三个数据时可以这么访问S2，在接收物理块数的数据时我刚开始用的int型，对textBox里的数据进行强制转换，但是在对输入数据进行限制时，出现了错误，所以后来我还是改用了字符串的形式进行接收，在对物理块数的限制，刚开始没有限制，后来发现数据过大的话得到的结果没有太大的意义，因为这次课程课程设计知识仿真模拟页面置换的过程，所以我将物理块数限制在10之内。在显示数据的地方，有试过很多方法，才开始想用ListView控件，但是有考虑到页面序列的长度不定，用ListView控件太死板，所以改用了Label控件，通过换行实现了比较好看的输出形式。在各个算法的显示时，才开始想用Button控件，但是又觉得界面不够好看，换成了tabControl控件，窗口效果比较好。再各算法的设计中，也遇到了一些困难，对于页面用了struct，而struct里timer，在不同的算法里面有不同的含义。五、用户手册1、使用平台是Microsoft Visual Studio 2008，需要安装该软件，直接双击安装即可。2、该程序无需安装。3、对于程序的使用，请按照如下步骤执行：(1)双击PageChange.exe,得到如下的界面(2)输入页面序列，物理块数。输入的页面必须为数字，物理块数也必须为数字，且在10之内，否则会有相应的错误提示，具体的运行结果如下(3)选择页面置换算法，按“置换结果”按钮，相应的结果如下（4）在五种页面置换算法都得到结果时，才能进行分析，若如上只得到了两种置换结果时，按“性能分析”按钮，会有下面相应的结果显示(5)在五种算法都得到置换结果时，按“性能分析”按钮，其结果如下六、程序清单 (1)OPT页面置换算法 private void OPT_button1_Click(object sender, EventArgs e) /没有输入数据之前不能进行页面置换 if (page.Length = 0 | strsize.Length = 0) MessageBox.Show(输入得页面序列或物理块数不能为空, 提示, MessageBoxButtons.OK); else /初始化，设置第一个数据 int i, j, u, losecount, changecount = 0; for (i = 0; i size; i+) Xi.Num = -1; Xi.Timer = 0; X0.Num = page0; GetTime(0, 0); losecount = 1; OPT_label.Text = OPTn + (X0.Num - 48).ToString() + n; /循环，具体的算法 for (i = 1; i page.Length; i+) u = 0; /若内存中存在该页面，进行如下计算 for (j = 0; j size; j+) if (Xj.Num = pagei) GetTime(i, j); u = 1; break; /若内存中没有足够的兑换空间且不存在该页面，进行如下置换 if (u != 1 & Xsize - 1.Num != -1) j = GetMaxTime(); Xj.Num = pagei; GetTime(i, j); losecount+; changecount+; /若有空闲的空间，则进行如下置换 if (u != 1 & Xsize - 1.Num = -1) for (j = 0; j size; j+) if (Xj.Num = -1) Xj.Num = pagei; GetTime(i, j); losecount+; break; /将数据进行输出 for (j = 0; j size; j+) if (Xj.Num != -1) OPT_label.Text += (Xj.Num - 48).ToString(); else OPT_label.Text += ; OPT_label.Text += n; OPTlosepage = (float)losecount / (float)(page.Length); OPT_label.Text += 访问次数是: + page.Length + n页面置换次数： + changecount + n缺页中断次数： + losecount + n缺页率是： + OPTlosepage; (2)FIFO页面置换算法 private void FIFO_button1_Click(object sender, EventArgs e) if (page.Length = 0 | strsize.Length = 0) MessageBox.Show(输入得页面序列或物理块数不能为空, 提示, MessageBoxButtons.OK); else /初始化数据，并访问第一个页面 int i, j, u, losecount, changecount = 0; for (i = 0; i size; i+) Xi.Num = -1; Xi.Timer = 0; X0.Num = page0; X0.Timer = 1; FIFO_label.Text = FIFOn + (X0.Num - 48).ToString() + n; losecount = 1; /循环，按照页面序列，选择淘汰的页面并进行置换 for (i = 1; i page.Length; i+) u = 0;/进程的内存中是否存在要访问的页面的标记 /若内存中存在要访问的页面，则设置u=1，并退出循环 for (j = 0; j size; j+) if (Xj.Num = pagei) u = 1; break; /若内存中不存在要访问的页面，且内存中无空闲的空间则进行下列置换 if (u != 1 & Xsize - 1.Num != -1) j = GetMaxTime();/选择呆的时间最长的页面进行置换 Xj.Num = pagei; Xj.Timer = 0; changecount+; losecount+; /若内存中不存在要访问的页面，且内存中有空闲的空间则进行下列置换 if (u != 1 & Xsize - 1.Num = -1) for (j = 0; j size; j+) if (Xj.Num = -1) Xj.Num = pagei; losecount+; break; /对内存中不为空的页面的时间加1 for (j = 0; j size; j+) if (Xj.Num != -1) Xj.Timer+; /输出数据 for (j = 0; j size; j+) if (Xj.Num != -1) FIFO_label.Text += (Xj.Num - 48).ToString(); else FIFO_label.Text += ; FIFO_label.Text += n; FIFOlosepage = (float)losecount / (float)(page.Length);/缺页率 FIFO_label.Text += 访问次数是: + page.Length + n页面置换次数： + changecount + n缺页中断次数： + losecount + n缺页率是： + FIFOlosepage; (3)LRU置换算法 private void LRU_button1_Click(object sender, EventArgs e) if (page.Length = 0 | strsize.Length = 0) MessageBox.Show(输入得页面序列或物理块数不能为空, 提示, MessageBoxButtons.OK); else /初始化数据，并访问第一个页面，并输出访问结果 int i, j, u, losecount, changecount = 0; for (i = 0; i size; i+) Xi.Num = -1; Xi.Timer = 0; X0.Num = page0; X0.Timer = 1; losecount = 1; LRU_label.Text = LRUn + (X0.Num - 48).ToString() + n; /循环，按照页面序列依次访问页面，并输出访问结果 for (i = 1; i page.Length; i+) u = 0; /如果内存中存在要访问的页面，则置Timer为0,u为1 for (j = 0; j size; j+) if (Xj.Num = pagei) Xj.Timer = 0;/因为该算法是将最近最久为使用的页面作为淘汰页 u = 1; break; /若内存中不存在空余的空间，且不存在要访问的页面，则进行如下置换 if (u != 1 & Xsize - 1.Num != -1) j = GetMaxTime(); Xj.Num = pagei; Xj.Timer = 0; losecount+;/发生缺页中断 changecount+;/发生页面置换 /若内存中，不存在要访问的页面，且有空闲的空间，则进行如下置换 if (u != 1 & Xsize - 1.Num = -1) for (j = 0; j size; j+) if (Xj.Num = -1) Xj.Num = pagei; losecount+; break; /对内存中的页面呆的时间进行加1 for (j = 0; j size; j+) if (Xj.Num != -1) Xj.Timer+; /数据输出 for (j = 0; j size; j+) if (Xj.Num != -1) LRU_label.Text += (Xj.Num - 48).ToString(); else LRU_label.Text += ; LRU_label.Text += n; LRUlosepage = (float)losecount / (float)(page.Length); LRU_label.Text+= 访问次数是: + page.Length + n页面置换次数： + changecount + n缺页中断次数： + losecount + n缺页率是： + LRUlosepage; (4)简单Clock置换算法 private void simpleClock_button1_Click(object sender, EventArgs e) if (page.Length = 0 | strsize.Length = 0) MessageBox.Show(输入得页面序列或物理块数不能为空, 提示, MessageBoxButtons.OK); else /初始化，并访问第一个页面，输出访问结果 int i, j, u, losecount, changecount = 0; for (i = 0; i size; i+) Xi.Num = -1; Xi.Timer = 0; X0.Num = page0; X0.Timer = 1;/此算法中Timer的含义是访问位，表示该页是否被访问 losecount = 1; simpleClock_label.Text = 简单Clockn + (X0.Num - 48).ToString() + n; /循环，按照页面序列进行访问，并输出访问结果 for (i = 1; i page.Length; i+) u = 0; /如果内存中存在要访问的页面，则置访问位为1，u位1，并退出循环 for (j = 0; j size; j+) if (Xj.Num = pagei) Xj.Timer = 1; u = 1; break; /若内存中不存在要访问的页面，且内存中无空闲的空间，则进行如下置换 if (u != 1 & Xsize - 1.Num != -1) int tag = 0; for (j = 0; j size; j+) if (Xj.Timer = 1) tag+; else Xj.Num = pagei; Xj.Timer = 1; losecount+; changecount+; break; if (tag = size)/