操作系统：第4章 存储器管理 页面置换算法

第四章存储器管理虚拟存储分配方式2/15回顾2.请求分段存储管理1.请求分页存储管理基本分页/段+请求调入+置换功能实现方式虚拟存储器虚拟存储器：仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充。3/15页面置换算法也称为页面淘汰算法，是用来选择换出页面的算法。4.8页面置换算法4/154.8页面置换算法3最佳（Optimal）置换算法124先进先出（FIFO）置换算法最近最久未使用（LRU）置换算法时钟（Clock）置换算法5/15最佳置换算法1算法思想： 选择今后永远不用的页面或者在最远的将来才用的页面作为被淘汰页面。不再用的很晚才用的稍后才用的6/15最佳置换算法150120304202314241451501505012032042142145缺页率：9/20342(2)例：假定系统采用最佳置换算法。为某进程分配了3个物理块，进程运行时的页面走向为5,0,1,2,0,3,0,4,2,0,2,3,1,4,2,4,1,4,5,1，开始时3个物理块均为空，表示出页面置换过程，并计算缺页率。7/15最佳置换算法1一种理想化的算法。可以用作算法的评价标准。优点：通常可以保证获得最低缺页率。缺点：无法实现。(3)优缺点：8/15先进先出置换算法12算法思想： 按照页面进入内存的先后顺序选择被淘汰页面。9/15先进先出置换算法1250120304202314241451501505012312304231425缺页率：14/20234302204431421125(2)例：优点：直观，实现简单。缺点：与进程实际运行规律不相适应， 性能最差。(3)优缺点：10/153以程序局部性原理为依据，根据页面最近一段时间的使用情况预测未来趋势。3最近最久未使用置换算法算法思想： 选择最近最久未使用的页面作为被淘汰页面。11/153最近最久未使用置换算法50120304202314241451501505012032034123145缺页率：12/20023024143142优点：较理想的缺页率。缺点：要求较多硬件支持。(2)例：(3)优缺点：12/15时钟置换算法4①为每页设置一个访问位，所有页面连接成一个循环队列。当某页被访问时，其访问位被置1。②在选择一页淘汰时，块号页号访问位指针1402013开始访问位=0？选择该页淘汰指针移动到下一页面置访问位0YN③当检查到队列中最后一个页面时，若其访问位为1，则返回队首检查第一个页面。检查页的访问位，若为0，就选择该页换出；若为1，则重新将它置0，暂不换出，再按照先进先出算法检查下一页面。(1)算法思想2113/15时钟置换算法501203042023142414515015050120320341035422032341431424204512(2)例：123000111524013缺页率：14/2014/15练习159页习题26分别采用四种页面置换算法，计算页面分配过程和缺页率。15/15时钟置换算法4(3)优缺点：优点：较理想的缺页率，较少的硬件支持。缺点：没有考虑页面的置换代价。16/15本章总结连续存储分配方式单一连续分配固定分区分配