下面我们来介绍调度算法
那么在这里头呢
我们的调度算法呢分成了六种
大致可以分成这样几类
第一类呢关于就绪队列怎么排
然后第二类呢
是关于每一次执行时间
的长短的控制
然后再有后面两种
是关于多种算法
如何把它综合到一起
那首先是这几种算法的一个大致说明
首先是先来先服务算法
这个算法呢 它是按着
到就绪队列里的先后顺序来排队的
那我们在找就绪进程的时候
也是按照这个先后顺序来的
跟我们前面讲的FIFO是很相似的
那在那个地方呢
是用来做置换算法的
第二个是说 第一种算法它
按先来后到没有考虑到进程的特征
那在这儿 第二类呢
就是短进程优先
这里头呢会有几种
稍微有一些小区别的变种
那它们是按照
作业执行时间的长短来进行排队的。
然后第三个 是高响应比优先算法
在这个算法里头呢
它考虑的是进程在就绪队列里的等待时间
依据等待时间的长短呢
来考虑它排的这个队的情况
好 下面呢是时间片轮转算法
那它是让各个进程
轮流占用一个基本的时间片
然后在这里头
排到就绪队列里头呢
仍然按照我们前面的
先来先服务算法来进行排队
在那基础上呢多了一个
执行时间的最大长度限制
你最长不能执行超过一个时间片
在这之前 你可以由于等待
或者结束而让出CPU使用权
而多级反馈队列呢
是把我们的就绪队列排成多个子队列
不同的子队列里头呢
我可以有不同的算法
并且可以在多个队列之间
调整一个进程所排的队列
这样的话就形成了一种综合的算法
而最后的公平共享调度算法呢
它强调的是按照
进程占用的资源的情况来进行调度
保证我们每一个进程
占用的资源呢是相对公平的
好 下面我们具体来说每一种算法
首先是先来先服务算法
那这种算法呢
它是按照进程进入就绪状态
的先后顺序来排队
那这是就绪队列里的排法
取的时候怎么办呢
我一个进程在进入 等待或者结束
也就说进程主动让出CPU
然后我从就绪队列当中
选择下一个进程占用CPU
那在这种算法里头呢
它的特征是啥样子的
那我们在这儿呢
对它的周转时间做一个分析
假定我有三个进程
它们分别的执行时间是12 3 3
然后假定它们到达的顺序
是这样一个顺序
好 那我们按照先来先服务算法的要求
那就是第一个执行完
执行第二个 再执行第三个
第一个12 到了12
然后第二个是3 到了15
第三个是3 到了18
好 这是我们来看它的周转时间
周转时间假定它们到达的时间
基本上是同一个时刻到达
好 那这样它的周转时间
就变成是12 15 18
除以3得15
好这时候我们直观上就感觉到
由于第一个进程执行时间比较长
后面两个等的时间比较长
好 这样的话周转时间变得长了
如果说我换一个顺序
假定到达顺序是这样子的
那两个短的在前头
那么这时候它的周转时间是什么样
那周转时间就变成了9
从这两个比较的角度来看呢
我们看到 这个算法
它的周转跟你这个
队列到达的时间有很大的关系
如果说你运气不好
排到一个长的执行时间的进程的后面
那么你的等待时间呢那就很长
好 这是呢我们这种算法它的特征
它的好处是简单
排队的依据很容易获得
排队过程当中呢也不需要什么变化
所以这种算法比较简单
它的麻烦呢是
平均等待时间波动非常大
也就说如果你一个进程
短的进程排在一个长的进程后面
那你的等待时间就长了
所以这时候呢你排的位置
对你这算法特征呢影响很大
再有一个呢是它资源的利用效率比较低
那你说我一个进程进入等待
另一个马上不就运行了嘛
这时候它怎么会CPU利用效率低呢
那我们看一种情况
说有一个CPU密集型的进程
那这时候它一直算
算的时候它就会
实际上I/O设备的操作
可以和CPU并行的
但是由于你CPU密集型进程呢正在运行
那这时候I/O设备呢就空闲了
那后面如果说你还有
很多要进行I/O的这样一些进程呢
也不会因为你当前CPU占用
然后I/O设备空闲
而让你可以先来执行I/O
好 那这样一来
你的I/O设备它的利用效率就低了
好 那我们这时候
要想对这种算法做改进
改进怎么办呢
我们排队的时候
刚才说没有考虑到进程的特征
那我们现在呢短进程优先算法
它考虑到进程的特征
考虑到进程什么特征呢
考虑到进程的执行时间
我在选择的时候呢
选择执行时间最短的进程
占用CPU进入运行状态
那这时候说我选择最短的
那这时候就按照预期的执行时间
因为执行时间
我是到执行的时候才会准确的知道
事先我没有办法知道得很准确
我只能是预期
那这个预期就会有一个麻烦
说我在这里头
这是我们的进程状态图
那我们在这里排的什么
实际上排的就是
把这个就绪队列按照这个来排了
好 那在这里头呢
这个预期的时间呢
排完之后如果说我这里头
还有一个新的进程到达
并且它预计时间
比当前正在执行的还短怎么办
好 那这地方呢就有一个变种
叫短剩余时间优先
好 那也就是说相当于
我一个进程正在执行
它预期的执行时间很长
我又来了一个新的进程
它预期的执行时间
比当前正在已经执行了一半的这个进程
剩下那个时间还要短
那这时候我允许它抢先
那就是短剩余时间优先
好 那这种算法有些什么样的特征呢
那我们看
它具有一个最优平均周转时间的特征
也就说你别的算法
你的平均周转时间都只能比它长
不会比它短
那我们看 它如何得到这个特点的
在这儿呢我们假定有一个序列
是进程的执行时间的序列
好 那如果说我按照
由短到长的这个顺序来排
它的执行顺序
那么这时候呢
它得到的周转时间是什么
这个地方ri实际上是
从0到执行完毕这个时间的长度
好 我们说这个时间呢
是它的最短时间
那我调整一下顺序
是不是只会比它长吗
那实际上这是可以证明的
那我们看一下
假定 我调整
这时候不管你做什么样的调整
都可以转换成一系列的基本调整
我只要保证每一次调整
它的时间你只会变长 不会变短
那么你总的时间就不会比我这个还短
那每一个最基本的调整是什么呢
实际上我是把两个对掉
那在这儿呢我把3 4 5倒了一下
那在这里头呢
2 前面两个还是跟原来一样
现在不是执行3了 而是执行4
那4呢 我倒了一遍之后
这时候它的完成时间是什么
是从这个点减去它的长度
我给了这个表示
然后5呢实际上是从这个地方
5减去3 也就相当于它串到后面来
把它俩往前串了
然后这个P3执行结束呢
本来就是一个r5
为了后边我说起来方便
我把它表示成r3在这个时间
加上这两个的长度
这里C3 C4 C5
都是进程Pi的执行时间。
好 有了这个之后
我们继续来算它的平均周转时间
这是把它全加在一起
然后我做一个等式变换
好 这时候呢把最后变的这一段加到这儿
那我们看到
由于我们这一个
是按照由小到大排的
所以这里的C3一定是小于C4 C5
所以这个数 肯定是一个非负的数
也就说 是0或者是一个正数
那么这样一来的话
你这个下面这个周转时间
一定是比上面这个大的
好 那从这个角度来讲呢
我们看到短作业优先呢
它可以有最优的平均周转时间
这是它的好的特征
但是它也会有麻烦
它的麻烦是什么呢
如果我一台机器里头
就绪进程不断地产生
不断地产生正在执行
因为你是按照由短到长来排的
那如果说我短的很多
那这么长的就会一直得不到CPU的资源
好 那这时候呢就会导致饥饿
也就是说我有一个进程处于就绪状态
由于它声称它的运行时间比较长
好 所有的短的作业呢 进程呢
都在它前面加塞了
好 那这时候它就得不到CPU资源了
好 那同时呢
这时候还有一个问题
它需要预知你的执行时间
那我如何来估计CPU的进程
的下一个执行时间长短呢
那这和我们前面做
内存的置换算法的时候
的状态是一样的
我们希望知道未来的情况
但是要知道未来是很麻烦的
好 那这时候我们用过去来预测
那实际上在这里头
我们的预测有这样几种办法
第一个 我到底要执行多长时间
我去问用户 用户你自己来说
这时候就可能有两种情况
一种是说用户
因为我想很快能运行
我告诉你我只需要执行一秒钟
实际上我执行了一分钟
那这时候怎么办呢
那说对于操作系统来讲
你声称你执行多长时间
那你就排到相应队列里头
好 那就把你声称时间到了之后
你还没执行完
系统可以把你强行终止掉
那还有一种情况
用户干脆我不知道我会执行多长时间
因为它在某些情况下
它不知道数据处理
到底要什么样的复杂程度
好 这种情况怎么办
这时候我们还是有另一种做法
就是用过去预测未来
那这就是执行时间的预估
那怎么来预估呢
就是利用历史信息来预测
预估未来的执行时间
那具体的做法呢是这样的
这是一个小事例
说 我在这个程序里呢做一组循环
读数据 数据处理 那这就相当于I/O
然后进行CPU 执行
那在这个过程当中
我们给出这样一个公式
说我下一次执行时间的预测
在这里头呢
就是这一次的执行时间
你N次的执行时间
前面加上一个衰减系数
然后加上你上一次的预估值
把它俩加在一起
就是你下一次的预估值
就实际上把当前时间
和你上一次预估值做一个校正
好 那这时候我得到一个新的预估值
那这一种呢相当于如果我把它展开之后
实际上就是把前面的
每一次的执行时间做衰减
当前最近的这一次呢
它的影响权重是最大的
后面呢以前的个次依次衰减
到一定时间长度之后就可以忽略不计了
这是在这里预测的做法
那这种预测的做法呢
带来的结果是说
这是我实际的执行的过程当中
的每一次占用CPU的时候
进入等待状态之前它的执行时间
好 然后在这上头呢我作为一个预测
依据我刚才的公式 就是这一条线
那么这一条线
和我们前面这条黄的线
它们俩之间可以有一个比较好的拟合
那这就是我这里用过去
预测未来的预测的结果
好 那这是短作业优先算法
然后第三个算法呢是最高响应比优先
那在前面呢
我只是考虑到进程执行时间的因素
那有可能刚才说
短进程优先
会因为长进程等的时间而出现饥饿
那现在呢我为了避免这种情况出现
高响应比优先 我是在这里
按照响应比R的值来排序
这个R怎么计算呢
W是你的等待时间
S是你预估的执行时间
那在这里头呢我这个等的时间越长
我R因为它在分子 R会越来越大
等的时间越长
它的优先级越高
那这样的话在一定程度上
就可以避免我们刚才说的
短进程优先里头的
长进程等待时间长的这种情况
而导致出现饥饿
好 那么在这种算法里头呢
那它是基于短进程优先算法之上的改进
那在这里头呢它不允许强占
好 那这时候呢它关注的是
进程的等待时间 好
这时候呢它可以避免无限期的等待
因为你等的时间越长
你的优先级越高
最终你会变成最高优先级
所以你能得到CPU的使用权
好 到这个地方呢我们就说清楚了
前面三种关于就绪队列排序的算法
它根据先后到达顺序
执行时间 等待时间
这样几个指标来排序