下面我们继续来讨论置换算法
那首先我们讨论的
是时间片轮转算法
在时间片轮转算法里头呢
我们首先要约定一个
进程调度的基本时间单位
就这里的时间片
它是处理机资源分配的基本单位
每个进程上来之后执行一个时间片
那我们用下面这个图示
来说明时间片轮转算法
它的基本工作原理
这头呢是CPU
然后这是它的就绪队列
中间会时间片结束的时候
会有时钟中断导致后续的处理
那具体处理是这样的
时间片结束的时候
那按照先来先服务算法
切换到下一个就绪进程
那这里的下一个就绪进程
是排到这里的第一位
好 结束的这个呢
是排到它的队的最后
好 这样一来的话
就是如果有n个进程
那每个进程呢占一个时间片
那这就是每隔n-1个时间片
进程占用一个时间片来执行
那在这个周期性的轮转当中
每一个进程呢分到了1/n的时间
这是时间片轮转算法的基本思路
下面我们通过一个例子
来说明它的运行过程
那这地方呢假定时间片的长度是20
然后现在有四个进程
它们分别的执行时间在这里
下面我看一下 它的执行过程
我们用下面这个图来表示
首先每个进程执行20个时间单位
那在这里头呢 P2呢只有8个
那执行到这儿呢
20到28 它就结束了
好 第一圈执行下来之后呢
进程二就结束了
好 接着来第二圈
那么这时候呢只有三个1 3 4
第二圈结束的时候呢 我们看到
P4又已经全部执行完毕了
那它也退出 整个进程结束
现在还剩P1和P3
好 再接着往下来
到这个时候呢
P1也执行完了P3执行
最后还剩一个P3
好 这是它整个执行过程的
CPU的占用情况
那我们来看看它的等待时间特征
这是四个进程
在执行过程当中的等待时间
我们以其中的一个为例
比如说P1 它执行了几次呢
第一次 第二次 第三次
分三个时间片它就执行完了
那么中间等待的时间是什么呢
起头它是第一个所以没有等待时间
然后第二的话就是20到68
然后第三次是从88到112
那这地方就是68-20
112-88 好 那这个地方呢
这是它的等待时间
那我们算一下
它的平均等待时间 是66.25
那我们看到
这是一个时间片轮转算法
它的运行过程
那我们看到中间等待的时间呢
相对来说比较长的
好 那这时候说
我们时间片到底设置为多长合适呢
那我们说在这里头呢
时间片轮转算法由于它靠时钟中断
强行把正在执行的进程结束掉了
所以它在这儿呢
有额外的上下文切换的开销
不像我们前面的一些算法
它只在进程到等待状态的时候
它才会有进程切换
那我们说在这里头
我们把时间片设多大合适呢
那先看两个极端的情况
时间片很大
大到可以任何一个进程
都在一个时间片内能完成
那这时候它的算法变成什么样了
变成一个先来先服务了
也就是说来了之后
按照来的顺序去就绪队列里排
一次执行肯定结束
那这就变成了先来先服务
而这时候呢它的等待时间呢
就跟我们先来先服务是一样的。
好 那这是很长 不太合适
而对于时间片短
那你比如说我们在这里极端的情况
我大量一半以上的时间是在做切换
执行的时间只是按其中的一半
那么这时候呢
这个上下文切换
它是有很大的开销的
好 这些开销呢
会影响到系统的吞吐量
所以我们这儿呢
时间片大了对进程的响应时间不好
小了对系统的开销不好
那这时候我们要选择一个合适的尺度
目前呢对这个问题呢
只有一些经验值在这里来设
你比如说在这里头我们现在系统
通常情况下呢
它是10毫秒左右一个时间片
这个时间片呢
上下文切换的开销呢是在百分之一左右
好 这是关于时间片的问题
那我们说在这里头
我们想看一下它的这个等待时间
到底是什么样的情况
我们还是以刚才的那个例子来说
那我们把它对照
先来先服务和时间片轮转算法
这两个算法它的等待时间
那我们先假定呢
上下文切换的时间呢为零 忽略不计
好 那这时候我看
每一个做法它的平均等待时间
这地方最后的这两个呢
先来先服务算法到达情况影响很大
所以我们在这儿取两个极端的情况
一个是最差 一个是最好
实际上最好的呢
就相当于是短进程优先
好 最差的呢相当于长进程优先
那中间呢这几个是我取不同的时间片
我们看一下算出来的结果
那这是它的平均等待时间
我们看到最好和最差的情况
都是先来先服务的
所以你到达的序列
对它的实际情况抖动很大
好 而对于时间片轮转呢
那么这时候呢
它基本上是在它们的中间
这是这两种算法的比较
好 那接下来说
每一个进程占用CPU
执行多长时间这件事情定下来了
然后我们排队的事情也定下来了
但这时候 它仍然没有办法
用一个算法满足我们应用的所有需求
好 那这时候 我们就想到
是不是可以把这算法组合到一起
实际上我们刚才的时间片轮转算法
已经是把先来先服务
和时间片划分的这种做法
两个结合到一起
好 那在这儿呢
第一个做法呢就是多级队列调度算法
它把就绪队列分成若干个子队列
每个子队列是相互独立的
比如说我们在这里头
前台 那是交互的应用
那这时候我要求时间片短
那后台呢 是计算时间比较长的
那这时候呢我可能用先来先服务算法
好 这两个交替到一起
我用一个时间片算法
好 然后说我各个队列之间
可以有自己的调度算法
这我们前台 用时间片轮转
后台 用先来先服务
然后队列之间怎么办
那队列之间 既可以说我固定优先级
前台想想是该优先
好 后台呢有空的时候我再来处理
好 这时候就可能有什么
我们前面讨论到的
你按照这个来的话
它就会导致饥饿
就是后台的这些长进程它的优先级低
而且运算时间很长
前台的交互进程的短进程
数量很大的话
那么它就会出现饥饿
好 那说我换种办法
用时间片轮转 那在这里呢
每个队列分得一定的时间配额
保证它总的时间占一定比例
好 那你比如说这里头
前台占80% 后台占20%
前台有作业的时候呢
它可以很好的得到及时的响应
后台呢也不至于完全处于饥饿的状态
在刚才的多极队列里头呢
各个队列之间呢是没有交互的
那进一步往前改进呢
就是多级反馈队列
那么多级反馈队列呢
是队列之间可以相互移动
也就说我一个进程
在执行一段时间可以在队列A
执行一段时间之后
可以把它放到队列B里头
那这种做法呢 它会变得更灵活
比如说我们在这里头一种做法
时间片的大小
我可以在不同队列之间做调整
那优先级越高的
那它时间片越小
优先级越低的呢它时间片越大
好 然后在这里头
如果说你执行的时间越长
我把你的优先级调的更低
那这地方我们用这样一个图示来表示
我这个地方分了N个优先级
由高到低
然后时间片q呢
t0是基本的时间单位
优先级越低 那它就会倍增
好 那这时候每一个进程
上来之后在优先级最高的一级
好 如果说它一个时间片用完
它还没有执行完 那它就降级
好 这样一来的话
我们这个算法就得到这样一个特征
CPU密集型的进程
那它的优先级会逐步降低
并且时间片会分的很大
好 这样的话
它切换的这个开销呢相对来说变小
而对于I/O密集型的进程
那这时候呢它会停留在高优先级上
因为每一次它算的时间都很短
它的时间片没用完
好 这样一来的话
我们有可能在这里
形成一个很好的多级反馈队列的算法
好 在这个算法之上呢
我们又有一类公平共享调度算法
那它强调的是资源访问的公平
把用户和进程分组
一些用户呢比另一些用户重要
那这样的话 它分的时间会更大
然后不重要的这些用户呢
不能让它垄断资源
也就的说按用户的优先级来做这件事情
那实际上我们在这儿
用这个图示来描述
系统资源我在调度器控制下
分成若干组
每一组占用的时间
在执行的过程当中
我是进行相应统计的
好 这样一来的话我们就可以
没有使用完的资源那就按比例分
好 那在这里头呢
如果说我的资源没用到
我所约定的份额
那这时候我优先获得相应的使用权
这些时候呢的问题是说
这个算法到底怎么来实现
它的开销是什么样子
我在这儿就不做仔细介绍了
有兴趣同学可以下去进一步去看
好 到这儿呢我们就说清楚了
六种经典的 或者叫传统的调度算法
每一种算法呢它各有特点
对于先来先服务呢
这个算法是很简单 但它不公平
平均等待时间变动很大
然后改进的一种办法是进程优先
那这时候它不公平
但是有一个特征是平均周转时间最小
然后它有的毛病是
需要预测未来的执行时间
然后可能导致饥饿
好 而高响应比优先呢
实际上它考虑的是我的等待时间
然后在这里呢
它是基于短进程优先来改进的
只是换了一下它排队的指标
然后时间片轮转算法 它是公平的
然后平均等待时间呢性能会比较差
但它的交互性会很好
然后多级反馈队列呢提供一套机制
使得我多种算法可以集成到一起
实际上我们现在
在实际系统里用到的算法呢
基本上是这种综合的算法
只是综合的方式呢
各个系统不一样
而公平共享算法呢
它强调的是
公平是它第一个要衡量的指标
好 那么刚才我们讨论清楚了
这个传统的调度算法当中
各自的特点和基本的做法
那么我们对于实际系统里头
我们还是以ucore为例
介绍一下它的调度算法
是怎么在系统里工作的
首先呢我们看一下它的调度队列
那在调度队列这个数据结构里头
我们看到它有相应的指针结构
来描述我就绪队列的排法
然后每一个进程的相关的
时间片的信息 在这里有描述
好 这样一来的话
就可以通过它把所有的进程串到一起
放到各自的队列当中
从而形成调度算法所需要的调度信息
然后再一个就是说
我们这里调度和进程状态之间的关联
我们前面讲了三进程状态模型
和我们调度之间的关系
而我们的ucore呢更简单
只有两种基本的状态
创建和退出 这两个状态呢
相对来说执行的时间很少
那主要的是可执行和等待状态
那在这里头呢
我们相应的状态转变
分别在这几个相应的函数
你比如说创建结束之后
放在就绪队列里
我们前面已经说过
在proc_init里头
好 那在这里头呢
会有这样几个函数
会导致运行状态的进程变到等待状态
好 等待事件出现的时候
它会回到运行状态
然后exit 它会出来
那在这些状态里头呢
会和我们的进程切换联络到一起
我们看一下它的切换的过程
这是我们进程执行过程当中的
内核和用户态之间的交互
我们如果说只有一个进程的话
在用户态执行
那可能会出现中断或者系统调用
这时候切换到内核
这两个的切换呢对于我们来说
在我们这个层面上来讲是一致的
好 切换过去之后
它保护中断的现场
然后处理中断
正常情况下处理完之后
它回到用户态继续执行了 对吗
好 现在我们在这儿呢
在中间加了一个调度
也就说我处理完了之后
并不是直接恢复最后的现场
而是在这里呢加了一个调度
调度之后呢我就可以到另外的进程
好 另外的进程呢最后会回到这儿来
那这时候我们看一下整个的过程
首先 是在执行的过程当中
出现系统调用
或者说中断 或者说异常
这时候呢它切到内核
那切过来的时候呢
它会保存中断的现场
保存完之后 那我进行中断处理
因为这是要求时间的
那 处理完之后呢
正常情况下我就恢复用户态的现场
然后就回去了
但是现在调度之后
调度的结果 如果说你是
仍然是执行这个进程
那跟原来一样
好 如果说你是执行其它进程
那么就切到另一个进程了
而假定另一个进程
实际上刚才也是执行到这个地方
然后做的切换
那到这儿来的时候呢
它就会回到恢复中断现场
那到这儿呢 确实是恢复中断现场
恢复完之后它怎么办
它就回到用户态去了
就到这儿
好 到用户态继续执行
那在这里执行的过程当中呢
它还会再出现中断
比如说我时间片用完
这时候再出现中断
中断怎么办
跟刚才这地方是一样的
它进到内核态
好 这时候呢保存中断现场
进行中断处理 然后进行调度
调度完了之后
如果说切回上一回执行的那个进程
怎么办
切回去 好 这时候对于这个进程来说
你可以理解为它处理完中断现场
然后恢复用户态的现场
然后回到用户态继续执行
那整个这个切换的过程就完成了
好 然后调度实际在哪
就是由内核态返回到用户态
之前那个时刻
那我做这个调度，
调度完之后到别的了
回来的时候我再恢复
然后回到用户态
这样的话 既不影响到中断的及时处理
也可以让各个进程之间
能够交替运行
好 那这个过程呢
希望大家下去之后
通过实际的ucore代码阅读
来理解这个过程的执行情况
好 那如果说我们在这里
要加自己的调度算法 我怎么加呢
在ucore里呢定义了一个调度类
在这里头呢
约定了调度算法对外提供的接口
比如说我们在这里头
调度算法会什么
我有一个进程变成就绪状态
我如何把它加到就绪队列里头
我要选择下一个进程占用CPU来运行
我选择哪个进程
那这时候呢 对应着两个函数
一个是入队 一个是出队
有了这两个函数之后
我就知道不同的调度算法
就可以按照自己的调度方法
由等待状态变成就绪状态的进程
放到就绪队列里头
也可以从里头选择出
下一个要执行的进程
来从这个就绪队列里头取出来
好 那除此之外还有几个函数
一个是pick_next
就是我选择下一个进程
然后还有一个呢 就是proc_tick
tick实际上相当于
我们在这里呢会支持时钟中断
时钟中断的时候
在不同的调度算法呢
你的计数 或者说对优先级的修改
是不一致的 好 那在这儿有这个
再加上一个初始化 OK
我整个调度算法的内容呢
都可以从这儿和我的系统接起来了
好 那这样一来的话
我的系统其它部分
不需要了解你的调度算法的细则
我只要这个接口能接上
那你的调度算法
就可以在我这个系统里面工作了
好 每个人呢只需要实现这几个函数
你就可以把你自己的调度算法呢实现出来了
并且和系统对接起来
好 那实际上
我们系统里怎么用这些东西呢
那这就是我们ucore调度框架
那我们说在用户态
前面讲进程控制的时候
已经说过了这样一些函数
这些函数都和进程控制相关
然后这地方是调度
其中一部分是直接到这儿来
重要的都是从schedule过来
好 这个地方接的
就是我们刚才说的
调度类接口里的那些接口函数
好 你的实现的函数呢
通过填这个数据结构的函数指针
那把你的调度算法接到这里头来
那上面的系统调用和用户态
通过这一边连到这儿来
那这样的话系统应用
就依据你的调度算法再进行调度
这是ucore的调度框架
那在实验当中呢
要求大家去实现一种
简单的调度算法 叫stride