11.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架在线视频

下面我们继续来讨论置换算法

那首先我们讨论的

是时间片轮转算法

在时间片轮转算法里头呢

我们首先要约定一个

进程调度的基本时间单位

就这里的时间片

它是处理机资源分配的基本单位

每个进程上来之后执行一个时间片

那我们用下面这个图示

来说明时间片轮转算法

它的基本工作原理

这头呢是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