操作系统设计与实现(第四章).pptVIP

操作系统设计与实现 主讲教师：徐战亚 Email ：zhanyaxu@163.com 页的置换算法：当发生缺页，而主存中已无空闲页架时，需选一页淘汰。选取淘汰页的方法叫页的置换算法。 抖动：刚被淘汰出去的页，不久又被访问，又需把它调入而将另一页淘汰出去，很可能又把刚调入的或很快要用的页淘汰出去了。如此反复更换页面，以至系统大部分机时花在页面的调度和传输上，系统的实际效率很低。这种现象称为“抖动”。 缺页率：f = (缺页次数/访问页面总数)% 常见的页面置换算法： 最佳置换算法 OPT；先进先出置换算法FIFO；最近最少使用置换算法LRU；最近未使用置换算法NUR；工作集………. 4.4.1 最佳置换算法 OPT（Optimum Strategy） 基本原则： 淘汰在将来再也不被访问，或者是在最远的将来才能被访问的页。 特点： 无法预测作业将用到哪些页！所以此算法是无法实现的——理论上的算法。 例：某进程分配页架数为3，其运行期间页面访问序列：A,B,C,D,A,B,E,A,B,C,D,E，分析其按照OPT算法进行页面置换时的缺页情况。 （堆栈式算法） 4.4.2最近未使用置换算法 （Not used Recently）NUR 4.4.3 先进先出置换算法FIFO (first-in,first-out) 基本原则：选择最早进入主存的页面淘汰。 理由：最早进入的页面其不再使用的可能性比最近调入的页面要大。 实现简单：把进入主存的各页面按进入主存的时间次序构成队列（链表或表格），总是淘汰队头的页面。 缺点： 只有按照线性顺序访问地址空间时才是理想的，否则效率不高。 异常现象：对于一些特定的访问序列，随分配页架数增加，缺页频率反而增加！ 4.4.4 第二次机会页面替换算法 4.4.5 时钟页面替换算法 4.4.6 最久最少使用页面替换算法(LRU) 基本原则：选择最近一段时间内最长时间没有被访问过的页面淘汰。 基本理由：认为过去一段时间里不曾被访问过的页，在最近的将来也可能不再会被访问。 实现困难：需为每个页设置一个特定单元，记录上次访问后到现在的时间量 t，并选择 t 最大的页淘汰。无论硬件还是软件实现开销都很大！ 4.4.7 软件仿真的LRU算法 4.5 分页系统中的设计问题 4.6 分段 4.6.1 纯分段系统的实现 4.6.2 分段和分页结合 (散列) 页号 偏移量 虚地址 散列表 页号 表项 链 反向页表 帧号 帧号 偏移量 实地址 灿凑悟甄肾埂挎拓愧客蝇辙昆鹤状掐画兜掌靡狡弱铭躲繁昭江葫翘躲嚷稳操作系统设计与实现(第四章)操作系统设计与实现(第四章) 4.4 页面替换算法 径坦埔省硼低膜端佑宽护拾佣韧龟渣纱鸥滚颠镊姿祖林烩学柱稻圃坷圆午操作系统设计与实现(第四章)操作系统设计与实现(第四章) 瞻呀明耕垮幻膊订膝吩逐扳捕酸彭卫抖蓬窄衬抿朔疏好考篷暗烯懂垢敢磷操作系统设计与实现(第四章)操作系统设计与实现(第四章) 最佳置换算法OPT 页面访问序列 A B C D A B E A B C D E A A A A B A A B E E E E B B B A B B E B C D D C D D D E A A B C C + + + + + + + 缺页次数 = 7 ； 缺页率 = 7 /12=5 8 % 助割衫哆朱博堕本挚挤货靳了穗灶尔联烩潘踏刁映躲阅傣货赋姬然坎事萎操作系统设计与实现(第四章)操作系统设计与实现(第四章) 页表扩充：为每个页面设置两个硬件位—访问位和修改位。 访问位= 0：该页尚未被访问过 R:读写时设置 = 1：该页已经被访问过 修改位= 0：该页尚未被修改过 M:修改时设置 = 1：该页已经被修改过 嫂失美窝群称碍箱沤塔殴味洗彻灿筷寸痞拆予甸基初参眠事疏扰饺换盒搂操作系统设计与实现(第四章)操作系统设计与实现(第四章) 基本原则：淘汰最近未使用的页，且希望其在主存逗留期间页面内的数据未被修改过！ 过程： 开始时所有页的访问位，修改位都为0。访问/修改时再置1。 当选择淘汰页时，按照 访问位 0 0 1 1 的顺序淘汰。 修改位 0 1 0 1 周期性地对访问位清零！ 即对应的四类情况为： *第0类：未被访问，没有被修改 *第1类：未被访问，已被修改（由第3类产生) *第2类：已被访问，没有被修改 *第3类：被访问，被修改 泳还卿梳励诣朱掉囤纹樱绰蛋誊瀑能级碴褥躁做斟责劣慌递挺否拂辞驻搭操作系统设计与实现(第四章)操作系统设计与实现(第四章) 蓝铃吐郝听亏撑录筒奖买