当前课程知识点：操作系统 > 第九讲 页面置换算法 > 9.5 工作集置换算法 > 9.5 工作集置换算法
接下来我们介绍全局置换算法
那在前边讲的
局部置换算法里头呢
我们没有讨论分配给一个进程的
物理页面数到底是多少
而全局置换算法呢
我们在这里需要考虑这个问题
也就是说考虑到不同的进程之间
它对内存需求量的这种差异性
那具体做法呢 我们这给出了两种
一种叫工作集 一种叫缺页率
工作集置换算法你可以理解为
是我们前边说到的
最优算法在全局里的一种体现
它们之间有一定的关系
好 我们说在局部置换算法里头
它没有考虑到不同进程之间的差异
也就是说在某些情况下
你可能多给进程增加一个物理页面
可能缺页率就会大幅度下降
那么在这呢 我们先举一个例子
在这是以FIFO
实际上即使用LRU也会有类似的情况
这地方呢 是说我有四个页面
然后你分配给它三页 那这三页呢
由于我这访问比较分散
你分配给三页的时候
在这给出来的例子是
后边这是一片的缺页
那缺页的次数有九次
但实际上这时候对于这种情况
你给它四页多一页之后
缺页次数就变成了只有一次
实际上这一次还是说
我们因为两者之间的差异
我把这一次算到里头
那实际上按道理来说
你把这四页全给它了
它就没有缺页了
对于这种情况你多给它一页
实际上这时候所带来的好处是很大的
那我们需要在全局置换算法里面
就是要考虑到这种情况
那具体说起来我们怎么考虑呢
全局置换算法就是
给进程分配可变数目的物理页面
那分配可变 可变的依据是什么呢
可变的依据会是说进程需求的量
那这个需求量是变化的
那我接下来的问题是说
你要依据这个需求的不同
而给它分配可变的数目
我这个需求我怎么来度量
好 那针对这个需求呢
它度量是这样的
我们先对进程的内存访问特征
做某种程度的分析 在不同的阶段
它所需求的量是不一样的
你比如说我一个排序程序
我可能会分成三段
刚开始的时候是数据读入
那这是一段情况 然后后边是一段
中间一段我是排序
排完了之后 结果我把它输出
这三个阶段 你从直观上来想
它肯定是它们之间有很大的区别的
那有了这个之后
我们依据这种需求
来给它分配物理页面数
那这时候算法要讨论的问题就是
如何来确定我给它分配多少
你可以把这件事情分成两段
一个是用来确定
给进程分配的物理页面数
另一个是说我到底是哪些页面
也可以把这两个问题混在一起
我不考虑到底分配多少
分配哪一个 我把它搁在一起
你需要的时候我就往里加
这种方式也可以
好 在具体讨论做法之前呢
我们再进一步来分析CPU的利用率
和并发进程数之间的关系
这是一张图说纵轴是CPU的利用效率
横轴是并发的进程数
我们直观上想象会是说
你只有一个进程的时候
CPU的利用效率肯定是低的
那我可以让多个进程并发运行
随着并发运行的进程的增加
这条线 CPU的利用效率是增加的
但是这条线大家也可以想象
它肯定没有办法无限制的增加上去
好 那增加到一定程度
这个时候你的内存开始紧张之后
这条线就增加的没那么快了
然后到某一个位置之后
你再往上增加
它有可能就会直线下降
好 那这种关系体现成什么样呢
这样来描述CPU利用率和并发进程数
存在相互促进和制约的关系
前边是促进 后边就变成制约了
那我们需要让CPU效率提的好
就是我得掌握一个合适的尺度
那怎么叫合适呢
也就是说我在这里头
我需要考察它的状态
进程数少的时候那是前边这一段
它CPU效率提高
好 进程数增加的时候
那这个访存的也增加了
那再增加的时候到这
那我的局部性就下降了
因为并发进程的使用
导致我们切换之后
你执行两个完全不相干的事
那这时候它的局部性
我们前边说那些就没有了
至少两个进程之间是没有了
那这时候呢 它就会导致这一段
如果再继续增加
那它就会CPU用更多的时间
来进行缺页处理
而这个缺页处理的增加呢
就会导致你CPU利用效率的下降
那这样我们就能
把这条曲线解释清楚了
如果说我们把这条曲线解释清楚之后
我们想要达到的状态是什么呢
尽可能让系统里的
并发进程数对内存使用
在这两者之间这个状态
好 那对这种情况我们怎么来描述呢
我们引入一个概念叫做工作集
工作集是指进程当前使用的
逻辑页面的集合
那这里头比较诡异的地方
是在于当前俩字 什么算是当前
过去一段时间 过去多长时间
好 那在这我们也给它一个近似
实际上这已经开始有近似了
把它表示成一个二元组
W（t,Δ）那在这里头呢
t是你当前的时刻 随着时间的移动
那你当前正在使用的逻辑页面数
它是会不同的 然后过去一段时间
我会有一个定长的访问时间窗口
那这里头呢我们有一个定长两个字
正常情况下根据你的
程序的特征的不同
时间的窗口可能也会不同的
但是在我们这个算法里呢
这一段我就没考虑了
好 我把它设置成一个定长的
然后在这里头呢
得到当前时刻往过去一段时间里头
它访问的这些页面所构成的集合
就是这里的W 那也是这里说的
W是我们当前时刻之前的
Δ时间窗口内
所有访问的页面的集合
那这时候呢 就把我们前边说的
当前俩字给具体化了
也就是说我做了个近似
然后这里头页面的数的大小
就是你的工作集的大小
然后在这我们给了工作集一个定义
那具体说起来呢
我们在这给了一个示例
说这是你的一个进程的
页面访问顺序
然后在这我给它定了一个
时间窗口是10 就是这一段
然后我们看在这一段时间里
它访问了哪些页面
从当前起头的状态来看
这是1 2 5 6 7 这是当前这一段
我们把这个时间轴
随着时间轴往后移
这里的状态是变的
在某一段时间呢 它是相对稳定的
到这 到这一段的时候
基本上到最后就只剩3 4
因为这一段它在访问3 4
我们考察了两个时间点t1和t2
这是它最后访问工作集的大小
那从这可以看到 在不同时间段里头
它访问的页面的数目是不一样的
好 如果说我能根据这个来确定
到后边这段的时候给它分配两页
到前边这段的时候给它分配五页
那这样的话就能很好的
满足进程的这种需求了
刚才我们给了工作集的
定义和一个图示
给出我如何来看到
一个进程它实际的工作集
那接下来呢
我们看一下工作集它变化
有些什么样的规律
那这是一个示意图
说横轴是时间轴
纵轴是工作集的大小
那随着这个进程的变化呢
它这条曲线会体现出某种规律
这些规律呢 我们把它分成这样几条
第一个是说我在刚开始起头的时候
进程访问的页面是增加
然后到一个阶段逐步稳定 就到了这
然后在这些稳定的阶段呢
大致稳定这些区域呢
基本上是理解为我在系统里头
这个进程正在做某一件事情
你比如说这里头数据采集
数据处理和最后的数据展现
那根据你当前做的事情不同
它所需要的内存量
工作集的大小是不一样的
然后在两者之间做切换的时候
这个工作集会有一个快速的
扩张和收缩的过程
那这里头呢 就对应着我这个峰值
这个峰值和这个峰值
如果说我们给出来的全局置换算法
能够很好的近似这条曲线
那我们这件事情做起来就相对容易了
好我们来看怎么来做这件事情
为了对工作集有个刻画
我们在这定义了一个叫常驻集
常驻集是指什么呢
当前时刻进程
实际驻留内存的页面的集合
实际上我们用常驻集
来对进程的工作集做一个近似
工作集和常驻集是什么联系呢
工作集是进程运行过程当中的
固有属性 它是它的特征
随着你那个运行的过程的不同而不同
而常驻集是系统分配给进程的
物理页面数和置换算法都有关系
那实际在的这些页
那我们这个置换算法要干的事情
就是依据置换算法
和进程运行的特征
来确定我给常驻集到底有多大
里头都有哪些页面
好 具体做起来的时候呢
我们是以这样一个做法来实施的
这就是常驻集和我的缺页率
也就是说我通过控制常驻集
来影响缺页率
那这个缺页率和常驻集有什么关系
如果说常驻集包含了工作集
也就相当于工作集里当前正在访问的
这些面都在内存里 都在常驻集里头
那这时候它的缺页率是比较小的
如果说你在这里头
进程正在执行的功能 模块有切换
那这时候工作集会发生一个变化
这个变化呢
你需要去调整你的常驻集
这时候缺页率会比较多
如果说我在这里头常驻集
达到一定的尺度之后 你继续去增加
也就相当于你能够满足它
当前功能需要的内存之后
你再加内存 放的其它东西
实际上这时候对它缺页率
并没有明显的影响
也就是说它不会明显的下降
你这时候再给它分配多的页面
这个效率是下降的 在这种情况下
我们希望是CPU的利用效率提高
整个系统的并发程度提高
好 有了这几条之后
我们就可以来讨论工作集置换算法
它的思路是什么样的
它的思路是把不在工作集的页面
把它换出去 这跟我们前边的
讨论局部置换算法不一样
局部置换算法基本上是说
我把缺的那一页拿进来
这个时刻来靠把哪一页置换出去
来得到它的集合
在这它并不一定是在
你这个缺页的时候来做这件事情
好 那这时候呢 怎么做呢
在这里面还有一个τ
这是一个参数 是窗口大小
相当于我们在这考察的时候
过去一段时间
这个τ这个时刻就是它窗口大小
具体做法是这样的
我们在这里维护一个访存的链表
有点像我们LRU里头的特殊的栈
然后在访存的时候 这个算法呢
需要去把不在工作集的页面 把它换出
那我们说访存实际上是非常频繁的
你要做换出的判断和动作呢
它的开销是很大的
那在这里头呢 而在缺页的时候
这件事情反倒是简单
它在缺页的时候只是需要
把你缺的那一页加进来就行了
那这时候 我们在前边局部置换算法
复杂的地方是在缺页里头
现在它把它复杂的地方
放到了访存的时候 那这种算法呢
相对来讲它肯定也是开销大的
我们在这也还是用一个实例
来说一下它的工作过程 它怎么在做
以前我们基本上不考虑
在刚开始的时候有哪几个页面
为了让这个地方能够进行的顺利
我们在这先假定了一个起头的时候
这几个页面的顺序
假设它的意思是在于
我想知道在第一个时刻的时候
过去有几个页面
它是已经超出了工作集
这只是个假例
好 那在这里头呢
我们访问第一个页面
缺页的时候按照工作集置换算法
它怎么做 缺哪个 把哪个补进来
我在访存的时候 这个正好访存
但是这时候我在访存的时候
还需要判断
我哪一个页面不在工作集里头
我们这个τ是4 从这个开始往4
那这个时候那个E
就已经过去超过四个了
没有访问过
这时候我得把它去掉了
再访问D的时候呢
那这时候说在这的这三个
D肯定是要有的 C A还在里头
那这时候看的情况是这样的
然后再访问B是加进来
那这个时候 你在访问B的时候
A也已经超过4个了
过去是C D B这三个
这个A就给剔除出去了
再访问C还会有哪 C在里头
那是访问成功的 然后B和D在里头
那还是这三个 然后再访问E的时候
把E加进来 E过去这四个
应该就是这四个
然后再访问C的时候
C B 那个D应该去掉了
这时候D去掉了
再访问E的时候呢
这四个加起来只有C和E
这B也会去掉 然后再访问A
这回是有一个缺页
然后再访问D仍然没在里头
再缺页 这时候A C E D
这是它整个执行的过程情况
那在这我们可以看到
你平时在访问的时候
你要做的判断是比较多的
你维护了那个链表
我们这时候可以理解为
那个链表是什么
是你访问的先后顺序
这和我们的LRU的算法
维护的那个栈是类似的
所以在这 这个工作集置换算法
它的开销也是很大的
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
