页面置换算法

1、页面置换算法课题：页面置换算法 教学目的：通过本节内容的学习，掌握三种页面置换算法教学重点：三种页面置换算法的算法过程教学难点：区分每种算法的算法过程，比较算法的的好坏，选用合理的算法教学方法：讲授法、讨论法教学对象：高中学生教学内容：一、复习旧知识问1：上节课我们学习了内存分配策略和分配算法，请同学们回顾一下，当我 们在为进程分配内存时，会涉及到哪三个问题？答1：最小物理块数的确定、物理块的分配策略、物理块的分配算法问2：那么在请求分页系统中，我们知道可以采用两种内存分配策略，分别是？答2：固定和可变分配策略问3：在进行置换时，也可采取两种策略，它们是？答3：全局置换和局部置换结论：因此物理

2、块的分配策略有三种：固定分配局部置换、可变分配全局置换、 可变分配局部置换二、新知识1、页面置换算法的概念我们知道，在进程运行过程中，若其所要访问的页面不在内存，需要把它们 调入内存。但是如果内存中已无空闲空间，我们为了保证该进程能正常运行，系 统就必须从内存中调出一页程序或数据送磁盘的对换区中。但是请同学们思考一 下，我们应该将哪个页面调出呢？同学们注意了，确定将哪个页面调出，并不是凭空想象的，而是须要根据一 定的算法来确定。通常把选择换出页面的算法称为页面置换算法置换算法的好坏，将直接影响到系统的性能，因此置换算法很重要那么什么样的置换算法，才是好的页面置换算法呢？这里，我们将具有较低的页

3、面更换频率的算法称为好的页面置换算法。我们用缺页率来衡量。缺页率=缺页次数访问次数100%2、常用的页面置换算法目前存在着许多种置换算法，下面介绍我们来学习三种常见的置换算法: 最佳置换算法、先进先出置换算法、最近最久未使用置换算法（1）最佳（Optimal）置换算法首先我们来看第一种，最佳置换算法。请同学们记住这样一句口诀：往后看选择永远不再使用的页面或者最后使用的页面加以淘汰怎样理解这句话的含义，我们来看一个例子：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串:7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1进程运行，先时将7、0、1三个页面装入

4、内存7一个页框代表一个物理块01接下来，当进程要访问页面2时，将会产生缺页中断。页面0将作为第5个被访 问的页面，页面1最为第14个被访问的页面，页面7作为第18个被访问的页面， 根据我们的口诀，永远不再使用的页面或者最后使用的页面加以淘汰，因此我们 应该选择页面7予以淘汰。注意了，这里的最后使用的页面，并不是最后一个页 面。同理，我们看下一个页面。当要访问页面0时，因为它已在内存而不必产生缺页 中断。我们将会产生缺页中断的页框下画一个勾，不产生缺页中断的页框下画一个叉。 最开始装入的三个页面视为不产生缺页中断 问：当访问页面3时，同学们思考，我们应该置换出哪个页面?答：页面1利用最佳页面置换

5、算法的置换图701203042303212017222222 00.0011131701701由图可看出采用最佳置换算法发生了 6次页面置换，缺页率为6/20*100%=30 请同学们用2分钟的时间熟悉该算法（2）先进先出（FIFO）页面置换算法下面我们来看第二种，先进先出页面置换算法，由该算法的名字可知道，最先进 入的页面，最先被置换出。请同学们再记住一个口诀：由最老页面至最新页面排序，淘汰最老页面还是同一个例子，我们用先进先出置换算法来做7003042722244003332111000我们将最老的页面放在最上面，新页面放在最下面。当访问页面2时，根据页面 的新老，将置换页面7,访问页面3

6、时，将置换页面0.剩下的请同学们按照口诀，画出置换图问：由图可看出采用最佳置换算法发生了几次页面置换？答：12次因此缺页率为：12/20*100%=60%同样请同学们快速的回忆下该算法 （3）最近最久未使用（LRU）置换算法下面我们来看最后一种算法，最近最久未使用置换算法。口诀：最老页面排上面，淘汰最老页面，但是页面每使用一次刷新一次。细心的同学发现了，我们这种算法与刚刚的先进先出置换算法有相通的地方，就 是淘汰最老的页面，但是我们这种算法，每使用一次都会刷新一次。那么怎样 理解这个“刷新”，我们还是用同样的例子当访问页面2时，置换页面7淘汰，因为页面2是新页面，因此将它放在最下面， 接着访问页面0，因为内存中有该页面，虽然不会发生缺页中断，但是根据口诀， 页面每使用一次，就要刷新一次，因此，将页面0放在最下面。请同学们动手，完成接下来的置换图，熟悉该置换算法并计算出缺页率。（45%）问：我们已经学习了三种置换算法，根据上述例子比较缺页率的大小，你有什 么发现？可以同桌之间讨论。答：物理块数相同时，最佳置换算法最好，其次是最近最久未使用算法，先进先 出算法最次。3、总结今天我们学习了三种页面置换算法，他们分别是最佳置换算法，先进先出置换 算法以及最近