各位同学大家好
今天我们来开始介绍置换算法
那在置换算法这一部分里头呢
我们分成这样三部分来讨论
首先是置换算法的概念
也就是说置换算法
到底是干什么的
然后接下来两个部分是
两种类型的置换算法
局部置换算法是说我
假定分配给一个物理页面数
已经定了之后
然后我去选择到底哪个被置换
而全局置换算法
是不区分置换的这个页面
到底属于哪个进程 这样的话
隐含着后边有每个进程
分配的物理页面数
也会做调整的这样一种情况
好 那我们接下来一个一个的说
置换算法是干什么的呢
置换算法是说我们在
虚拟存储系统当中
出现缺页的时候
我需要把一个新的页面
换到内存当中来 换入
但这时候内存当中的页面
已经全部都用完了
那这时候我必须选择一个页面
把它放到外存当中去
那我新要用的页面才能放进来
置换算法的功能就是
选择被置换的物理页面
你到底选择哪一个
那你说我选择的时候
我怎么来选择呢
那选择有它的依据
那这时候就是我们在这里头
你的依据到底是啥
这就是置换算法的设计目标
那在这里头呢
我们想要来设计一种置换算法
它的目标呢 是说我希望尽可能的
减少页面的调入和调出的次数
那要想让你这个调入调出的次数
实际上这个时候
跟你实际运行的那个程序
对存储访问的特征
是有密切关系的
好 那这时候我希望能够了解
程序在执行的过程当中
它的内存的访问特征
然后我来设计这个置换算法
那这样一来
你得是针对
每一个应用程序来设计吗
那不是这样的
我在操作系统没办法这么做
我只能是设计一个置换算法
然后考虑到它可能运行环境的
这一系列的进程的访问特征
然后从里头找出
适用面比较广的这种情况
那具体说起来呢 我们希望是这样的
把未来不再访问
或者说近期不再访问的
这些页面调出去
那这一条实际上很大的麻烦
是在于我如何能知道这一点
我如何能对未来的情况做一个估计
而这是我们在设计置换算法的时候
考虑最多的一些因素
好 在具体讨论我如何来做这种选择
如何来设计置换算法之前呢
还有一个小问题需要在这先说一下
就是页面锁定
这个是虚拟存储当中的一个概念
说我在进行置换的时候
有一些页面
你是不可以把它换到外存里头的
那这种情况呢 通常情况下是说
我有一些必须在内存里头的
重要的这些逻辑页面
这时候你比如说
操作系统里头的关键代码
然后还有一些呢
它并不一定是操作系统里的关键代码
但是它要求响应速度比较快
你要是说访问的那页在外存里头
那这个性能下降是它接受不了的
好 这些代码我也放在这里头
好 我们怎么来做到这一点呢
实际上在虚拟页式里头
它就在页表里的页表项
相应的页面上加一个锁定标志
有了这个标志之后
置换算法在运行的过程当中就
不会把这个页面放在外存里面去
那在具体讨论之前呢
我们还有一个问题需要大家讨论
那就是我设计了一种置换算法
你设计一种 到底我们俩谁算好
那这种好 实际上在这
是通过统计测试用例
的形式来给出来的
那在这我们为了后续讨论方便
我们需要给出一些约定
也就是说我怎么知道
一个进程的访问内存的序列呢
我就是记录它访问
所有存储单元的这个轨迹
然后那你比如说这里头
我们通常情况下
访问页面的时候是页号 页内偏移
那在我们这里头呢
我们关心的是访问的是哪一页
实际上一页内部
到底是哪一个存储单元
这时候是我们不太关心的
好 我们在这页号 页内偏移
我得到这个序列
然后我把页内偏移都去掉
做简化就变成了底下这个序列了
好 为了我们在后边说置换算法的时候
说起来方便
我们在这里头又给它换了一种表示
用字母来表示
这样避免和我们的顺序的1 2 3 4搞混了
好 有了这个之后
那这时候哪种算法比较好呢
那我们的评价标准是
模拟置换算法的行为 然后记录
在这个置换的过程当中
各个算法到底有多少次缺页
少的就是好的 那有了这两条之后
我们大概就可以开始
来讨论置换算法了
那在讨论之前呢
我们还是首先把置换算法做一个分类
因为你要界定你在讨论
置换算法的时候能够借用的外界条件
那在这里头呢
按照借用的外界条件的不同
我们分成两类
一类叫做局部置换算法
那在局部置换算法里头呢
分配给一个进程的物理页面数
是已经确定了
那我们在置换的时候
选择的范围仅限于当前进程
有了这一条之后
那也就相当于我在置换的过程当中
每个进程分配的
页面的总数是不会变化的
那这里头呢
我们有一系列的算法 最优算法
也就是说如果我能预测未来的话
我依据未来来决定我换哪个页面
这个是理论上的最好状态
没有算法比它更好
但是它的问题是
这个算法你在实际用的时候
你没办法知道
它所依赖的那个前提条件
就是未来什么时候会用到这个页面
第二个呢 是先进先出
这个算法是说用最简单的办法
我不知道它未来是啥情况
我就按照进来的时候的先后顺序
但是这个进来的先后顺序呢
并不一定反映了
实际的存储的访问特征
好 那这样的话
这个算法的性能不好
再有一个就是
最近最久未使用算法
那它实际上是在这里头呢
这个算法先进先出太差
最优算法没法实现
因为你是预测未来没法实现
好 那在这最近最久未使用算法
就是我把预测未来
变成是我统计过去
在过去一段时间的特征
我们通常情况下认为你过去的特征
对你未来是一种预测
好 我们基于这样一种假设前提呢
来讨论最近最久未使用算法
但是这种算法呢 它可能实现
但是仍然它的复杂度比较高
好 那这时候呢
就由它的这两种近似算法
我们这会说到
时钟算法和最不常用算法
那这都是对最近最久
未使用算法的一种近似
那具体的近似的做法呢
我们在后边再详细去说
这是一类 也就是相当于
我在当前进程暂用的页面里
来讨论我换谁
还有一类算法呢
叫全局置换算法
它不关心你当前换的这个页面
属于哪个进程
它讨论的范围是说置换的范围
是在所有可能换出的物理页面
它不管是哪个进程的
这隐含着 如果说我在置换的时候
是进程A的一个需要访问的页面
被置换出去那是进程B的
实际上这时候就隐含了
这两个进程之间分配的
物理页面数的一个变化
好 这时候呢 它也有两种算法
我们在这会说到
工作集算法和缺页率算法
好 有了这样一个大致分类之后
我们就先按照局部置换算法和
全局置换算法的顺序
来一个一个的进行讨论