好 那我们看看
接下来我们要完成的练习就是
stride scheduling
这是一个我们在原理课
没有讲的一个算法
这个算法呢
来自于一篇比较有名的一个论文
大家有兴趣的话可以看看这篇论文
这边给出了一个相应的链接
当然我们也通过简单的图示
来给大家展示一下
这个算法它大致的一个含义是什么
假定我们现在有三个进程
P1 P2 P3
那么呢 每个进程有两个属性
一个属性是什么呢 它的步长
就是说它现在执行到了什么地方
你可以把这个理解为一个跑道
可以看出来
这个stride有三个
P1是100 P2是106
P3是102
也就意味着现在最落后的是谁 是P1
那么跑的最快的是谁呢 P2
因为它这个106最大的一个值
这是一个参数
就是当前的它的位置
第二个呢
pass 要代表它一次要前进的步数
比如说P1它一次前进的步数是16
P2一次前进的步数是7
P3一次前进的步数是10
那我们这个调度的
算法的策略怎么来选择呢
我们要选择当前
步长最小的一个值的进程去执行它
然后呢 它执行的长度是多少呢
是这个当前的步长加上它这个pass
所以说我们可以看到
在这种情况下我们要选择哪个呢
很明显 这个P1
它这个当前的步长是最小的
所以我们选择它
然后呢 它会去走一段距离
是stride加上pass
我们叫做步进值
一个是步长值
一个是步进值 OK
它到这个位置了
好 我们接下来再看一看
当前谁的步长是最小的呢
P3现在是102
所以说我们接下来呢
我们的调度算法应该选择P3
然后它执行的步长是什么呢
10 102加上10等于112
到这个位置
好 再接下来是P2
它走的步长会到113这个位置
好 这三个进程都走了一轮之后呢
我们接下来再判断
第二轮的时候谁最小呢 P3最小
所以在这个时候应该选择P3去执行
这时候它已经变成122了
再接下来很明显P2执行
然后周而复始来完成这个
所有进程的一个选择 让谁去执行
那可以看出来
这里面谁的步进值越小
那么它被调度的次数会越多
大家想想为什么
这给大家留一个思考
那这个算法呢 它具有两个特点
它可以基于
进程的优先级来进行调度
那么这个优先级会和
我们的步进长度成一个反比
我们后面会讲到
第二个呢
它整个这个调度的选择是确定的
每一次选择不是
一个随机出现的一个值
而是一个确定的值
所以这个算法具有这两个优势
我们希望大家采取一定的数据结构
和一定的操作过程
来完成对这个算法的一个实现
这里面首先就要选择合适数据结构
为什么呢
因为我们基于数据结构
要完成相应的插入 查找 删除操作
而这个和我们
这个数据结构紧密联系
到底是取的list还是一个特殊的队列
比如优先队列等等
这些都影响到你后续的
这个算法的实现
那我们完成的步骤
第一步就是选择完数据结构之后呢
你就要去实现里面的
很重要的初始化函数init
从而可以完成对这个相应的队列
数组 堆 等的初始化
紧接着呢
会基于这种数据结构
来实现入队和出队这么两个函数
这里面再次提醒一下
这个入队出队是一个抽象的概念
它并不代表说
你处理的数据结构
一定要是一个queue
一个队列
第二个呢 我们要实现什么呢
就是选择操作
就是到底选择哪一个来
作为接下来占用CPU执行的进程
这是pick_next要完成的工作
假定我们选择了之后呢
接下来还要干的一个事情
是proc_tick
proc_tick是要改变当前的
一个调度的一个参数
是否需要调度了
proc_tick在哪改呢
我们前面也讲到
是在中断的
关于时钟中断处理例程里面
会对这做一定的设置
如果认为当前进程用完了时间片
因为它每一个时钟中断
代表一个时间片的一小部分
当比如说一百个时钟中断
代表一个时间片的话
那么用完了时间片
那么就需要重新调度
这时候就要设置一个调度的一个
我们前面讲的
设置一个调度的变量
叫做need_resched
把它置为1之后呢
在接下来的某一个调度点
就会完成对schedule这个函数的调用
好 这前面几个函数执行完之后
我们还要完成一个
入队和出队的一个实现
把这个实现了那我们就认为
我们就把这个关于这个调度算法
最关键的几个函数实现完毕
最后还需要干的一个事情就是
把它的这个调度类设置对
就是在sched_init这个函数里面呢
来设置一个default_sched_class
设置好之后就意味着
我们的schedule函数能够找到
你所设计的这个特定的一个调度类
针对你的这个Stride调度算法的调度类
来完成具体的调度过程
当你完成了上述的函数和相应的一个
关于这个算法的
调度类的一个设置之后呢
我们可以通过执行如下这个命令
make run-priority
来检查你是否正确的实现了这个
stride调度算法
那我们接下来呢
给大家做一些提示
使大家可以比较方便的
来完成这个实验
首先第一点就在于
你怎么选择一个合适的数据结构
那么这个数据结构呢
会有助于你完成针对
stride这个调度算法的
插入 删除和选择这么几个操作
这里面可以用前面讲的list
双向链表来完成
也可以用一些更新的一些数据结构
priority queue
这代表是优先队列
那么优先队列呢
又可以用进一步的具体的叫做
斜堆（skew heap）这么一个数据结构
来完成相应的操作
就是哪三个操作呢
插入 删除 查找
如果采取双向链表
那么它的这个时间开销
是和我们进程个数呈一个线性关系
就O(n)这么一个关系
那它的执行开销比较大
如果我们采取一种新的数据结构
比如说基于斜堆的优先队列的话
那么它的这个执行开销
就是查找 删除 插入
会比基于双向链表这个开销呢
要优化很多
所以说我们这里可以
采取基于斜堆的优先队列
来完成这么一个数据结构一个组织
那这里面很重要就在于一个比较
因为它是一个堆结构
这个比较函数呢
大家可以看它怎么实现的
有了这个斜堆这么一个结构之后呢
我们就可以完成
关于这个数据结构的初始化
插入 移除这么一个操作
那么通过比较呢
能够很快找着当前
最值得去执行的那个进程在哪
它正好是这个堆顶很容易找着
那么进一步我们会去修改
关于进程控制块的这么一个结构
增加一些相关的信息
比如说它有一个针对
斜堆的这么一个运行队列
那么我们会把我们这个
就绪进程呢挂到这个队列里面去
第二个呢这里面有一个stride
代表当前进程它这个步长值是多少
还有是一个优先级
这个优先级什么意思呢
就是说你优先级越高
证明你越有优先执行的权限
它和我们刚才说那个步进值pass
正好起一个反比
优先级越高它的pass值越低
而pass值越低呢
也意味着它有
更多的机会被调度去执行
另外还需要整个队列一个结构
我们还是一个run_queue
但是这里面专门有一个
特殊的 叫lab6的run_queue
来完成对这个结构管理和记录
当然这个结构跟前面不太一样
在哪呢
我们前面一般是用list
list entry是一个双向链表
这里面是skew_heap
基于斜堆这么一个数据结构
好 这里面还给大家一些提示就是
这个pass和priority
到底什么样一个关系
我们这里面来设置就是pass
等于一个BIG_VALUE / lab6_priority
这个lab6的priority
代表某一个进程它的优先级
这个值可以设置成不一样的
可以设置很大
也可以设置很小
那么BIG_VALUE就可以
设置一个相当大的值
就说有这些priority都不会大于这个BIG_VALUE
使得这个BIG_VALUE除以这个priority
会得到一个pass就是步进值
那步进值越小它前进的越慢
那我们调度时候呢
就会更多的选择这种进程去执行
这也是为什么这个pass和priority
正好是起反比的作用
第二个需要大家注意的是什么呢
这个步长
这个stride这个值呢
随着它不停地累加 其实会溢出
你怎么保证这个溢出
不会影响到对这个值判断
比如到底选择哪一个
最小那个stride去执行
这个我们是需要有一些特殊的考虑
大家要想到这里面有一些约束条件
比如说STRIDE_MAX减去STRIDE_MIN
要小于PASS_MAX 这是一个约束条件
第二个呢我们还做一个特定设置
STRIDE和PASS是无符号整数
大家可以关注一下我们数据结构
可以看到都是unit32_t 32位无符号整型
那么有了这个之后呢
我们再做比较的时候
是用的有符号值来比较
那么这一种设计技巧呢
使得我们可以避免出现溢出之后
无法去做正确的判断
到底这个stride
谁大谁小这么一种情况
在这里面大家有必要去
深入理解一下这个stride
的比较是怎么来完成的
在它不停累加情况下
依然能正确的判断出
到底是谁的这个stride值最小
好 那前面给大家做了简单介绍
希望大家 能够基于这些介绍
能够理解关于这个调度算法的
一个支撑框架怎么来的
第二 基于这个支撑框架知道
我们ucore操作系统
在什么时候可以完成
对调度算法一个函数的执行 这是一个
第三个希望大家能够
参考Round Robin这个调度算法
来完成对这个stride调度算法的实现