操作系统教学课件：第4章 存储器管理-4

1、第四章第四章 存储器管理存储器管理虚拟存储分配方式虚拟存储分配方式2/15回 顾2.2.请求分段请求分段存储管理存储管理1.1.请求分页请求分页存储管理存储管理基本分页基本分页/段段+ 请求调入请求调入+ 置换功能置换功能实现方式实现方式虚拟存储器虚拟存储器虚拟存储器：仅把作业的一部分装入虚拟存储器：仅把作业的一部分装入内存便可运行作业的存储管理系统，内存便可运行作业的存储管理系统，它具有请求调入功能和置换功能，能它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充。从逻辑上对内存容量进行扩充。3/15页面置换算法也称为页面淘汰算法，页面置换算法也称为页面淘汰算法，是用来选择换出页面的算

2、法。是用来选择换出页面的算法。4.8 页面置换算法页面置换算法4/154.8 页面置换算法页面置换算法3最佳（Optimal）置换算法124先进先出（FIFO）置换算法最近最久未使用（LRU）置换算法时钟（Clock）置换算法5/15最佳置换算法1(1)算法思想：算法思想： 选择今后永远不用的页面或者在最选择今后永远不用的页面或者在最远的将来才用的页面作为被淘汰页面。远的将来才用的页面作为被淘汰页面。不再用的很晚才用的稍后才用的6/15最佳置换算法15 0 1 2 0 3 0 4 2 0 2 3 1 4 2 4 1 4 5 1501505012032042142145缺页率：缺页率：9/209

3、/20342(2) (2) 例：例：假定系统采用最佳置换算法。为某进程分配假定系统采用最佳置换算法。为某进程分配了了3 3个物理块，进程运行时的页面走向为个物理块，进程运行时的页面走向为5,0,1,2,0,3,0,4,2,0,2,3,1,4,2,4,1,4,5,15,0,1,2,0,3,0,4,2,0,2,3,1,4,2,4,1,4,5,1，开始时开始时3 3个物理块均为空，表示出页面置换过个物理块均为空，表示出页面置换过程，并计算缺页率。程，并计算缺页率。7/15最佳置换算法1一种理想化的算法。一种理想化的算法。可以用作算法的评价标准。可以用作算法的评价标准。优点：通常可以保证获得最低缺页率

4、。优点：通常可以保证获得最低缺页率。缺点：无法实现。缺点：无法实现。(3) (3) 优缺点：优缺点：8/15先进先出置换算法1 2(1)算法思想：算法思想： 按照页面进入内存的先后顺序选按照页面进入内存的先后顺序选择被淘汰页面。择被淘汰页面。9/15先进先出置换算法1 25 0 1 2 0 3 0 4 2 0 2 3 1 4 2 4 1 4 5 1501505012312304231425缺页率：缺页率：14/2014/20234302204431421125(2) (2) 例：例：优点：直观，实现简单。优点：直观，实现简单。缺点：与进程实际运行规律不相适应，缺点：与进程实际运行规律不相适应，

5、 性能最差。性能最差。(3) (3) 优缺点：优缺点：10/153以程序局部性原理为依据，根据页面最以程序局部性原理为依据，根据页面最近一段时间的使用情况预测未来趋势。近一段时间的使用情况预测未来趋势。3最近最久未使用置换算法(1)算法思想：算法思想： 选择最近最久未使用的页面作为被选择最近最久未使用的页面作为被淘汰页面。淘汰页面。11/153最近最久未使用置换算法5 0 1 2 0 3 0 4 2 0 2 3 1 4 2 4 1 4 5 1501505012032034123145缺页率：缺页率：12/2012/20023024143142优点：较理想的缺页率。优点：较理想的缺页率。缺点：要

6、求较多硬件支持。缺点：要求较多硬件支持。(2) (2) 例：例：(3) (3) 优缺点：优缺点：12/15时钟置换算法4为每页设置一个访问位，所有页面连接成一个循环队列。当某页被访问时，其访问位被置1。在选择一页淘汰时，块号页号 访问位 指针1 4 02 0 13开始访问位=0？选择该页淘汰指针移动到下一页面置访问位0YN当检查到队列中最后一个页面时，若其访问位为1，则返回队首检查第一个页面。检查页的访问位，若为0，就选择该页换出；若为1，则重新将它置0，暂不换出，再按照先进先出算法检查下一页面。(1) (1) 算法思想算法思想 2 113/15时钟置换算法5 0 1 2 0 3 0 4 2

7、0 2 3 1 4 2 4 1 4 5 15015050120320341035422032341431424204512(2) (2) 例：例：1230001115 2 401 3缺页率：缺页率：14/2014/2014/15练习159159页习题页习题2626分别采用四种页面置换算法，分别采用四种页面置换算法，计算页面分配过程和缺页率。计算页面分配过程和缺页率。15/15时钟置换算法4(3) (3) 优缺点：优缺点：优点：较理想的缺页率，较少的硬件支持。优点：较理想的缺页率，较少的硬件支持。缺点：没有考虑页面的置换代价。缺点：没有考虑页面的置换代价。16/15本本 章章 总总 结结连续存储分配方式连续存储分配方式单一连续分配单一连续分配固定分区分配固定分区分配动态分区分配动态分区分配可重定位分区分配可重定位分区分配离散存储分配方式离散存储分配方式基本分页存储分配基