页面置换算法的模拟.doc

《页面置换算法的模拟.doc》由会员分享，可在线阅读，更多相关《页面置换算法的模拟.doc（21页珍藏版）》请在沃文网上搜索。

1、操作系统课程设计报告页面置换算法的模拟 学院 (系)： 计算机科学与工程学院 班 级： 107030801 学生姓名： xx 学 号： 10703080102 指导教师： 周 敏 时间： 从 2009年 6月30日 到 2009 年 7月3日目 录第一章 设计任务 4第二章 思想 42.1 先进先出（FIFO）页面置换算法 42.2 最近最久未使用（LRU）页面置换算法 52.3 最佳（OPT）页面置换算法 6第三章 任务目的 7第四章 设计方案 74.1 界面及主要流程 74.2 核心代码 84.2.1. 生成页面引用号 84.2.2. 启动演示窗体 84.2.3. 先进先出（FIFO）页面

2、置换演示代码 94.2.4. 动画增量代码 104.2.5. 最近最久未使用（LRU）置换演示代码 114.2.6. 最佳（OPT）页面置换演示代码 134.2.7. 获取物理块的图像函数代码 14第五章 程序截图 165.1 主窗体界面 165.2 先进先出（FIFO）算法演示界面 165.3 最近最久未使用（LRU）算法演示界面 175.4 最佳（OPT）算法演示界面 185.5 关于对话框 19第六章 结论总结 20第七章 参考文献 21第一章 设计任务设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率：要求设计主界面以灵活选择某算法，且以下算法都要实现1

3、）先进先出算法（FIFO）2）最近最久未使用算法（LRU）3）最佳置换算法（OPT）第二章 思 想2.1 先进先出（FIFO）页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。以下为采用FIFO算法进行页面置换的例子（图1）。当进程第一次访问页面2时，将

4、把第7页置换出，因为它是最先被调入内存的；在第一次访问页面3时，又将把页0置换出，因为它在现有的2，0，1三个页面中是最老的页。由图1可以看出，利用FIFO算法时进行了12次页面置换。引用率70120304230321201701777222444000777000333222111001110003332221页框图1 利用FIFO置换算法时的置换图2.2 最近最久未使用（LRU）置换算法LRU（Least Recently Used）置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）

5、的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。利用LRU算法对上例进行页面置换算法的结果如图2所示。当进程第一次对页面2进行访问时，由于页面7是最近最久未访问的，故将它置换出去。当进程第一次对页面3进行访问时，第1页成为最近最久未使用的页，将它换出。根据各页以前的使用情况来判断，页面过去和未

6、来的走向之间并无必然的关系。引用率70120304230321201701777224440111000000333001133222227页框图1 利用LRU置换算法时的置换图2.3 最佳（Optimal）置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。现举例说明如下（图3）。进程运行时，先将前

7、三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问时才需要调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程第一次访问页面3时，又将引起页面1被淘汰，因为，它在现有的1，2，0三个页面中，将是以后最晚才被访问的。由图可以看出，采用最佳置换算法发生了6次页面置换。引用率70120304230321201701777222227000040001133311页框图1 利用LRU置换算法时的置换图第三章 任务目的3.1 通过模拟

8、实现请求页式存储管理的几种基本页面置换算法，了解虚拟储技术的特点。3.2 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3.3 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。第四章 设计方案4.1 界面及主要流程设计C#程序图形界面程序来分别实现上述3种算法。FrmMain主窗口用来进行算法选择以及参数设置（系统分配的物理块个数blocks、最大页面pages、页面号引用串refs）。在参数设置里设置好最大页面和页面引用串长度后点击“产生”按钮将会随机产生出相应的页面引用串。点击“演示”按钮，将会根据算法选

9、择的不同打开不同算法的演示。演示窗体为动态演示图，以动画的方式来展示各个算法的内存引用时页面置换的不同。演示结束后将会以对话框（MessageBox）的方式提交算法信息，包含页面置换次数以及页面访问命中率。4.2 核心代码4.2.1 生成页面引用号： / / 按下生成按钮时触发 / / / private void buttonGenerate_Click(object sender, EventArgs e) int pages = (int) numericPages.Value; Random r = new Random(); StringBuilder builder = new S

10、tringBuilder(); / 随机生成 numericRefs.Value 个页面引用号 for (int i = 0; i numericRefs.Value; i+) builder.Append(r.Next(pages) + ,); builder.Length = builder.Length - 1; textPageRef.Text = builder.ToString(); 4.2.2 启动演示窗体 / / 开始启动演示 / / / private void buttonShow_Click(object sender, EventArgs e) / 处理参数 Progr

11、am.blocks = (int) numericBlocks.Value; /物理块 int pages = (int) numericPages.Value; / 总页面数 string strs = textPageRef.Text.Split(,); int refs = new intstrs.Length; / 页面引用号数组 try for (int i = 0; i strs.Length; i+) int n = int.Parse(strsi); if (n pages) / 页面号非法则抛出异常, 中断执行 throw new ArgumentOutOfRangeExce

12、ption(); refsi = n; catch / 页面引用号异常则退出演示 MessageBox.Show(输入的页面号引用串中含有非法数字, 或包括负数, 页面号引用串, MessageBoxButtons.OK, MessageBoxIcon.Error); return; Program.refs = refs; / 根据不同算法选择打开不同演示窗体 if (radioFIFO.Checked) new FrmFIFO().Show(this); else if (radioLRU.Checked) new FrmLRU().Show(this); else if (radioOP

13、T.Checked) new FrmOPT().Show(this); 4.2.3 先进先出（FIFO）置换算法演示代码 / / 先进先出(FIFO)置换算法演示函数 / public void startTest() int size = Program.blocks; / 内存储器大小 int refs = Program.refs; / 页面引用数组 int count = 0; / 置换页面次数 for (int i = 0; i size; i+) / 前blocks个引用不用置换页 memoryi = refsi; / 当前引用填充到内存中 readi = i; / 记录当前内存块

14、是第几个被读取的 / 产生页框, 并开始动画 blocksi = new Block(memory); changesi = true; now = i; startAnimation(); for (int i = size; i refs.Length; i+) / 判断新页面号是否在物理块中 int k = 0; for (int j = 0; j size; j+) if (memoryj != refsi) k+; if (k = size) / 如果不在 count+; / 发生了一次页面置换 changesi = true; / 找到最后一个读入页的索引 int index =

15、0; for (int j = 1, min = read0; j size; j+) if (readj min) min = readj; index = j; memoryindex = refsi; readindex = i; / 刷新刚读入的页的索引 blocksi = new Block(memory); else changesi = false; blocksi = new Block(memory); / 产生动画 now = i; startAnimation(); MessageBox.Show(页面置换了 + count + 次, 命中率为 + (refs.Lengt

16、h - count) * 100 / refs.Length + %, 先进先出(FIFO)页面置换算法, MessageBoxButtons.OK, MessageBoxIcon.Information); 4.2.4 动画增量代码 int tops; / 记录每个页框的坐标值 / / 动画演示方法 / public void startAnimation() int top = 154; topsnow = top; for (int i = 0; topsnow 35; i+) / 循环递减信号量 topsnow 来改变页框 blocksnow 的y坐标值 topsnow -= 4; T

17、hread.Sleep(25); / 每变化一次使线程睡眠 25ms 达到动画效果 try / 由于交叉线程间无法直接调用不同线程控件方法,所以使用托管方式刷新窗口 this.Invoke(new Invoker(refresh); catch / / 委托刷新 / public void refresh() this.Refresh(); 4.2.5 最近最久未使用（LRU）置换算法演示代码 / / 最近最久未使用(LRU)置换算法演示函数 / public void startTest() int size = Program.blocks; / 内存储器大小 int refs = Pro

18、gram.refs; / 页面引用数组 int count = 0; / 置换页面次数 for (int i = 0; i size; i+) / 前blocks个引用不用置换页 memoryi = refsi; / 当前引用填充到内存中 usesi = i; / 记录当前内存块最近被读入是第几个 / 产生页框,并开始动画 blocksi = new Block(memory); changesi = true; now = i; startAnimation(); for (int i = size; i refs.Length; i+) / 判断新页面号是否在物理块中 int k = 0;

19、 for (int j = 0; j size; j+) if (memoryj != refsi) k+; else usesj = i; / 存在的话刷新uses值 if (k = size) / 如果不在 count+; / 发生了一次页面置换 changesi = true; / 找到最近最久读入的页的索引 int index = 0; for (int j = 1, min = uses0; j size; j+) if (usesj min) min = usesj; index = j; memoryindex = refsi; usesindex = i; / 这个页刚使用过,

20、记录 blocksi = new Block(memory); else changesi = false; blocksi = new Block(memory); / 生成动画 now = i; startAnimation(); MessageBox.Show(页面置换了 + count + 次, 命中率为 + (refs.Length - count) * 100 / refs.Length + %, 最近最久未使用(LRU)置换算法, MessageBoxButtons.OK, MessageBoxIcon.Information); 4.2.6 最佳（OPT）页面置换算法演示代码

21、/ / 最佳(OPT)页面置换算法演示函数 / public void startTest() int size = Program.blocks; / 内存储器大小 int refs = Program.refs; / 页面引用数组 int count = 0; / 置换页面次数 for (int i = 0; i size; i+) / 前blocks个引用不用置换页 memoryi = refsi; / 当前引用填充到内存中 / 产生页框,开始动画 blocksi = new Block(memory); changesi = true; now = i; startAnimation(

22、); for (int i = size; i refs.Length; i+) / 判断新页面号是否在物理块中 int k = 0; for (int j = 0; j size; j+) if (memoryj != refsi) k+; if (k = size) / 如果不在 count+; / 发生了一次页面置换 changesi = true; / 开始寻找未来最后使用的页面索引 for (int j = 0; j size; j+) bool finded = false; for (int m = i + 1; m refs.Length; m+) if (memoryj =

23、refsm) / 找到了就记录他的位置 usesnextj = m; finded = true; break; if (!finded) usesnextj = refs.Length; / 寻找最后使用的页面索引 int index = 0; for (int j = 1, max = usesnext0; j max) max = usesnextj; index = j; memoryindex = refsi; blocksi = new Block(memory); else changesi = false; blocksi = new Block(memory); / 产生动画

24、 now = i; startAnimation(); MessageBox.Show(页面置换了 + count + 次, 命中率为 + (refs.Length - count) * 100 / refs.Length + %, 最佳(OPT)置换算法, MessageBoxButtons.OK, MessageBoxIcon.Information); 4.2.7 获取物理块的图像函数代码 / / 根据物理块结构获得图像 / / / 是否发生页面置换 / public static Bitmap GetBlockBmp(Block b, bool isChanged) Bitmap bm

25、p = new Bitmap(20, b.Length * 27); Graphics g = Graphics.FromImage(bmp); / 设置文字渲染模式为抗锯齿 g.TextRenderingHint = System.Drawing.Text.TextRenderingHint.AntiAlias; Font font = new Font(SimSun, 8); Pen pen = new Pen(Color.Black, 2); if (!isChanged) / 没有发生页面置换,画笔颜色改变为灰色 pen.Color = Color.Gray; else / 发生页面置

26、换,则画出边框 for (int i = 0; i b.Length; i+) g.DrawRectangle(pen, 0, i * 26, 19, 26); / 渲染物理块每一个单元的页号 for (int i = 0; i b.Length; i+) int? num = b.bitsi; if (num.HasValue) SizeF sz = g.MeasureString(num.ToString(), font); g.DrawString(num.ToString(), font, pen.Brush, (20 - sz.Width) / 2, (27 - sz.Height)

27、 / 2 + i * 27); / 释放内存,垃圾处理 pen.Dispose(); font.Dispose(); g.Dispose(); return bmp; 第五章 程序截图5.1 主窗体界面如图，为算法选择区域，在这里可以选择一种算法来演示；为参数设置区域，在这里可以对演示细节进行调整。点击“产生”按钮可以自动生成随机页面引用串5.2 先进先出（FIFO）算法演示界面如图为动画正在进行中。每次对一个新页面进行引用，则会显示出当前物理块中的页号情况。如图为演示结束时的截图。演示结束后会以消息框（MessageBox）的形式报告演示结果，包含页面置换次数和访问命中率。5.3 最近最久未使用（LRU）算法演示界面如图为该算法演示中的截图如图为演示结束的截图如图为该算法结果报告5.4 最佳（OPT）算法演示界面如图为演示中的截图如图为演示结束的截图如图为该算法结果报告5.5 关于对话框第六章 结论总结上述例子，三种算法命中率分别为 40%、55%、70%，单从访问命中率上来说三