页面置换算法教案文档格式.doc
- 文档编号:913585
- 上传时间:2023-04-29
- 格式:DOC
- 页数:6
- 大小:246.50KB
页面置换算法教案文档格式.doc
《页面置换算法教案文档格式.doc》由会员分享,可在线阅读,更多相关《页面置换算法教案文档格式.doc(6页珍藏版)》请在冰点文库上搜索。
教学重点:
最佳置换算法和LRU置换算法的实现原理及技术,以及不同页面置换算法性能的比较和评价。
教学难点:
理解并掌握LRU算法的原理及性能评价。
课的类型
传授知识课
教学方法
说教法、启发提问法等
教学用具
多媒体演示,黑板等
教
学
过
程
6.3.1最佳置换算法和先进先出算法
两种极端的算法,前者具有最好的性能,却难于实现,后者是性能最差的算法,却是最直观的算法,实际应用很少。
一、最佳置换算法
最佳置换算法是有Belady于1966年提出的算法。
其所选择的被淘汰的页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。
对于固定分配方式,该算法可获得最低的缺页率。
由于无法预知一个进程在内存的若干个页面中,哪个页面是未来最长时间内不再被访问的,所以,该算法是无法实现的。
但可用它去评价其它算法。
例:
假定系统为某进程分配了三个物理块,并有以下的页面号引用串:
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次页面置换。
二、先进先出页面置换算法
这是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面,即
选择内存中驻留时间最久的页面予以淘汰。
该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指向最老页面的替换指针即可。
例:
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个页框,访问串:
1,2,3,4,1,,2,5,1,2,3,4,5
缺页9次,
若分配4个页框,发生10次缺页。
原因:
没有考虑程序执行的动态特征。
6.3.2最近最久未使用LRU置换算法
一、LRU算法的描述
最近最久未使用(LRU)的页面置换算法,是根据页面调入内存后的
使用情况进行决策的。
由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。
例:
对页面号引用串:
利用LRU算法进行页面置换,其结果如图:
二、LRU算法的硬件支持
LRU对各种类型的程序都能适用,但实现复杂,须利用一些硬件支持解决一些问题:
(1)一个进程在内存中的各个页面各有多久时间未被进程访问
(2)如何快速地知道哪一页是最近最久未使用的页面。
1、寄存器
用于记录某进程在内存中各页的使用情况,需为每个在内存中的页面配置一个移位寄存器,表示为:
R=Rn-1Rn-2Rn-3…R2R1R0
2、堆栈
利用一个特殊的栈来保存当前使用的各个页面的页面号。
当进程访问某页面时,将该页面的页面号从栈中移出,将它压入栈顶,所以,栈顶始终是最新被访问的页面的编号,而栈底则是最近最久未使用页面的页面号。
6.3.3Clock置换算法
一、简单的Clock置换算法(最近未用算法NUR)
该算法只须为每页设置一位访问位表示是否已使用过,再将内存中的所有页面都通过链接指针链成一个循环队列。
当某页被访问时,其访问位被置为1。
置换算法在选择一页淘汰时,只须检查其访问位,若是0,就选择该页换出,若为1,则重新将它复为0,暂不换出而给该页第二次驻留内存的机会,再按照FIFO算法检查下一个页面。
当检查到队列中的最后一个页面时,若其访问位仍为1,则返回队首再去检查第一个页面。
该算法:
只有一位访问位,表示是否已经使用过,置换时是将未使用过的页面换出去,所以,又称为最近未用算法NUR(notusedrecently),系统周期性地对引用位清零。
二、改进型Clock置换算法
将一个页面换出时,若该页已被修改过,则须将它重新写到磁盘上,若未被修改过,则不必写回磁盘。
改进型Clock算法中,增加了一个置换代价,利用一个修改位实现之。
选择换出页面时,既要是最近未访问过的页面,又要是未被修改过的页面。
6.3.4其他置换算法
一、最少使用置换算法LFU(LeastFrequentlyUsed)
该算法,为在内存中的每个页面设置一移位寄存器,每次访问时,对该页移位寄存器的最高位置为1,每隔一定时间T右移一次,用于记录该页面被访问的频率。
二、页面缓冲算法PBA(PageBufferingAlgorithm)
该算法采用的可变分配和局部置换方式,置换算法采用FIFO,规定将一个被淘汰的页放入两个链表中的一个。
即:
若页面未被修改,就将它直接放入空闲链表中,否则,便放入已修改页面的链表中。
此时,页面在内存并不做物理上的移动,而只是将页表中的表项移到上述两个链表之一中。
另外,
(1)随机淘汰算法。
随机选择某个用户的页面进行置换。
(2)轮转法,循环换出内存空间中的页,无论该页是否刚被换进或已换进内存很长时间。
课后作业:
1.了解各种页面置换算法的工作原理;
2.熟练掌握最佳置换算法、先进先出置换算法、LRU置换算法、CLOCK置换算法等常用置换算法;
3.思考影响缺页中断率的因素有哪些?
(1)分配给作业的主存块数。
成反比。
(2)页面的大小。
反比。
(3)作业本身的程序编制方法。
(4)调度算法。
对教案执行的意见
自
我
分
析
小
组
意
见
该同学备课认真充分,教态自然,课堂讲授生动,举例分析易于理解,语速应稍放慢。
表现很好。
指
导
师
中学指导教师意见:
该实习生谦虚谨慎,积极认真备课、授课,积极学习。
教案做的有条有理,知识点安排顺序合理,学生接收效果较好。
系指导教师意见:
备
注
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 页面 置换 算法 教案