页面置换算法_计算机软件及应用_IT计算机_专业资料

《页面置换算法_计算机软件及应用_IT计算机_专业资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

3、法很重要那么什么样的置换算法，才是好的页面置换算法呢？这里，我们将具有较低的页而更换频率的算法称为好的页而置换算法。我们用缺页率来衡量。缺页率二缺页次数访问次数*100%2、常用的页面置换算法目前存在着许多种置换算法，下而介绍我们来学习三种常见的置换算法:最佳置换算法、先进先出置换算法、最近最久未使用置换算法(1)最佳(Optimal)置换算法首先我们來看第一种，最佳置换算法。请同学们记住这样一句II诀：往后看选择永远不再使用的页而或者最后使用的页而加以淘汰怎样理解这句话的含义，我们来看一个例子：假定系统为某进程分配了三个物理块，并考虑有以卜•的页

4、面号引用吊:7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1进程运行，先吋将7、0、1三个页面装入内存7一个页框代表一个物理块1接下来，当进程要访问页而2时，将会产生缺页中断。页而0将作为第5个被访问的页面，页面1最为第14个被访问的页面，页面7作为第18个被访问的页面,根据我们的口诀，永远不再使用的页面或者最后使用的页面加以淘汰，因此我们应该选择页面7予以淘汰。注意了，这里的最后使用的页面，并不是最后一个页面。201同理，我们看下一个页面。当要访问页面0时，因为它已在内存而不必产生缺页中断。我们将会产生缺页中断的页框

5、卜•画一个勾，不产生缺页中断的页框卜•画一个叉。最开始装入的三个页而视为不产生缺页中断问：当访问页面3吋，同学们思考，我们应该置换岀哪个页面?答：页面1利用最佳页面置换算法的置换图70120304230321201722222000400111331701701由图可看出采用最佳置换算法发牛了6次页面置换，缺页率为6/20*100%=30请同学们用2分钟的吋间熟悉该算法(1)先进先岀(FIFO)页而置换算法下面我们来看笫二种，先进先出页面置换算法，由该算法的名字可知道，最先进入的页面，最先被置换出。请同学们再记住一个口诀：曲最老页面至最新页面排序，

6、淘汰最老页面述是同一个例子，我们用先进先出置换算法来做3042224433321000701。0720011我们将最老的页面放在最上面，新页面放在最下面。当访问页面2时，根据页面的新老，将置换页面7,访问页面3时，将置换页面0.・・・・・・・剩下的请同学们按照口诀，画出置换图问：由图可看出采用最佳置换算法发牛了儿次页面置换？答：12次因此缺页率为：12/20*100%二60%同样请同学们快速的回忆卜•该算法(1)最近最久未使用(LRU)置换算法下面我们来看最后一种算法，最近最久未使用置换算法。口诀：最老页面排上面，淘汰最老页面，但是页面每使用一次刷

7、新一次。细心的同学发现了，我们这种算法与刚刚的先进先出置换算法冇相通的地方，就是淘汰最老的页面，但是我们这种算法，每使用一次都会刷新一次。那么怎样理解这个“刷新”，我们述是用同样的例子701203042701201201203当访问页面2时，置换页面7淘汰，因为页面2是新页面，因此将它放在最下面,接着访问页面0,因为内存屮有该页面，虽然不会发生缺页屮断，但是根据口诀,页面每使用一次，就要刷新一次，因此，将页面0放在最下面。请同学们动手，完成接下来的置换图，熟悉该置换算法并计算出缺页率。（45%）问：我们已经学习了三种置换算法，根据上述例子比较缺页率

8、的大小，你有什么发现？可以同桌之间讨论。答：物理块数相同时，最佳置换算法最好，其次是最近最久未使用算法，先进先出算法最次。