页面置换算法教案

《页面置换算法教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实习生试教教案计算机科学学院(系)计算机科学与技术专业2009年级班实习生试教课程页面置换算法实习学校实习班级七年级二班实习课时3月19日(星期二)第3节中学指导教师__________3月18日批准系指导教师3月18日批准课题页面置换算法教学目的使学生了解实现请求分页系统时，为解决内存空间不足的问题所采用的几种页面置换算法的各自的原理及实现的技术。教学重点和难点教学重点：最佳置换算法和LRU置换算法的实现原理及技术，以及不同页面置换算法性能的比较和评价。教学难点：理解并掌握LRU算法的原理及性能评价。课的类型传授知识课教学方法说教法、启发提问法等

2、教学用具多媒体演示，黑板等教学过程6.3.1最佳置换算法和先进先出算法两种极端的算法，前者具有最好的性能，却难于实现，后者是性能最差的算法，却是最直观的算法，实际应用很少。一、最佳置换算法最佳置换算法是有Belady于1966年提出的算法。其所选择的被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。对于固定分配方式，该算法可获得最低的缺页率。由于无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，所以，该算法是无法实现的。但可用它去评价其它算法。例：假定系统为某进程分配了三个物理块，并有以下的页面号

3、引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1进程运行时先将7,0，1三个页面装入内存，以后，当访问页面2时，产生缺页中断，OS根据最佳置换算法，选择页面7予以淘汰，因为页面0在第5次时被再访问，页面1在第14次再被访问，而页面7要在第18次时被再访问时才需调入。再访问0页面时，则不会产生缺页中断，而当进程访问页面3时，又引发页面1被淘汰，以此类推，直至进程完成，其运行过程中只发生了6次页面置换。二、先进先出页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即教学过程选择内存中驻留时间最久

4、的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指向最老页面的替换指针即可。例：假定系统为某进程分配了三个物理块，并有以下的页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1若采用先进先出置换算法，共发生12次置换。Belady现象陷阱现象：分配的页面数增多，缺页次数反而增加。正常情况，例：一进程分配3个页框，页面访问次序：7,0，1,2，0,3，0,4，2,3，0,3，2,1，2,0，1缺页12次，若分配4个页面，发生9次缺页；另一情况，例：一进程分配3

5、个页框，访问串：1,2，3,4，1，,2，5,1，2,3，4,5缺页9次，若分配4个页框，发生10次缺页。原因：没有考虑程序执行的动态特征。6.3.2最近最久未使用LRU置换算法一、LRU算法的描述最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。例：对页面号引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1利用LRU算法进行页面置换，其结果如图

6、：教学过程二、LRU算法的硬件支持LRU对各种类型的程序都能适用，但实现复杂，须利用一些硬件支持解决一些问题：(1)一个进程在内存中的各个页面各有多久时间未被进程访问(2)如何快速地知道哪一页是最近最久未使用的页面。1、寄存器用于记录某进程在内存中各页的使用情况，需为每个在内存中的页面配置一个移位寄存器，表示为：R=Rn-1Rn-2Rn-3…R2R1R02、堆栈利用一个特殊的栈来保存当前使用的各个页面的页面号。当进程访问某页面时，将该页面的页面号从栈中移出，将它压入栈顶，所以，栈顶始终是最新被访问的页面的编号，而栈底则是最近最久未使用页面的页面号。

7、6.3.3Clock置换算法一、简单的Clock置换算法（最近未用算法NUR）该算法只须为每页设置一位访问位表示是否已使用过，再将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位被置为1。置换算法在选择一页淘汰时，只须检查其访问位，若是0，就选择该页换出，若为1，则重新将它复为0，暂不换出而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则返回队首再去检查第一个页面。该算法：只有一位访问位，表示是否已经使用过，置换时是将未使用过的页面换出去，所以，又称为最近未用

8、算法NUR(notusedrecently)，系统周期性地对引用位清零。二、改进型Clock置换算法将一个页面换出时，若该