那前面给大家介绍了
整个调度算法的一个支撑框架
我们也知道
支撑框架何时会去驱动
那些调度算法的函数
接下来我们看一看
一个具体的调度算法
是怎么来实现的
那我们这里面是以Round Robin
调度算法来作为一个例子来介绍
这里面Round Robin
就是我们叫做时间片轮转
那么这个时间片轮转调度算法呢
它主要是基于
每个进程都有一个时间片
当时间片用完之后
它就会等到下一轮再去执行
这是它的一个基本原理
我们来看看它是怎么实现的
前面已经介绍我们要完成一个
就是schedule一个class
要把这些相应的函数填完
这些函数的具体实现
就体现了你这个
时间片轮转的一个特征
它的接口是一样的
包括初始化 进队 出队 选择和tick
这是大致它这几个关键的一些函数
我们看看它怎么来实现的
首先是这个初始化
我们可以知道一个运行队列
就是说就绪队列
需要来把所有这些
处于就绪态的这个进程管理起来
这么一个run_list
同时还记录了一个
当前这个进程的个数
就是处于就绪态进程的个数
这是一个关键的数据结构
然后呢 在初始化的时候呢
我们会把这个队列
给做一个初始化清空
使得这个proc_num等于0
这是最开始的时候要做的一个事情
那我们来看一下
关于Round Robin调度算法
它怎么来实现tick这个函数的
首先我们要知道tick函数
什么时候被调用
它是在产生时钟中断的时候呢
会触发这个函数的调用
那么产生一次时钟中断
意味着时间流失了一小段
所以说呢
它这个time_slice会做减操作
减一这么一个操作
在最开始初始化的时候
一个进程
它有它的一个time_slice
一旦它的time_slice
从它的减操作变成0之后
也就意味着
这个进程的时间片用完了
它有必要就是放弃对CPU的执行
让另一个进程去执行
所以说就可以看到
在这里面一旦time_slice等于0了
我们就会把一个重要的标记
就是need_resched
就是存在着进程控制块里面的
这个need_resched置成1
代表着这个进程应该被换出去
在接下来的中断处理例程中呢
会探询这个当前进程
这个标记位是否为1
一旦为1 它就会执行schedule完成切换
那我们再看看就是进队出队的实现
我们说这个
所有处于就绪态的进程呢
它是在一个就绪队列里面
就绪队列呢
我们是用前面讲到的一个
就是双向链表来实现的
当有一个进程要进队列的时候呢
我们会把它插入到就绪队列的头
就是list_add_before
这是它的一个大致实现
同时呢 也会对它的其它
一些参数做一定的调整 这是进队
那如果说我们要去选择一个进程
就是pick_next怎么来实现的呢
它是从这个队列的尾选出一个进程
这个进程代表当前应该去
占用CPU执行的一个进程
就是说所以说用
list_next来完成这个选择
一旦选择出这个进程之后呢
我们会进一步去做switch_to
来完成对这个进程的切换
那接下来我们看一下
完成这个pick_next怎么来实现的
这个pick_next函数要选择下一个
要占用CPU执行的这个进程
OK 那会从处于
就绪队列里面的进程选一个
选哪个呢 list_next
很明显可以看出来
它是取就绪队列里面最尾的那个
这个进程就代表当前
应该占用CPU执行的进程
这个list是一个双向链表
就是我们前面在lab0的时候
给大家介绍过的一个数据结构
有两种情况
有可能你得到这个元素entry可能是空
或者是一个具体的值
一个具体的值呢
就代表我们选着了
有就绪的这个进程存在
但是如果是空的话
就意味着选不出来
当前没有就绪进程
存在在就绪队列里面
这时候怎么办
这时候我们会让idle_thread去执行
这个idle_thread是一个内核线程
它干的主要工作就是不停的轮询
看这个就绪队列里面
是否有就绪进程存在
如果有就会去执行它
好 一旦我们选择到一个进程之后呢
我们会把这个进程
从就绪队列里面取出来
前面只是选择没有取
所以取出来是一个dequeue的实现
那么这个list_del_init就完成了
从就绪队列里面
把具体的进程取出来这么一个过程
从而就绪队列里面少这么一个元素
OK假定我们实现了这些函数
init 进队 出队 pick_next和tick
其实我们就完成了这个时间片轮转
可以看出来这个实现过程
其实还是挺简单的
然后呢 最后还有哪一步呢
就是在schedule初始化的时候呢
要让我们实现的这个
调度算法的这个类呢
指向具体的一个sched_class
从而可以使得我们
这个schedule这个函数呢
可以找到一个正确的一个调度算法
对应的函数去完成具体的调度过程
这就是说Round Robin这个调度算法
它大致的一个设计
和实现的一个方法
可以看出来比较简单
只要能够明确这几个函数就OK了