run_queue
数据结构。这个数据结构虽然没有保存在调度类中,但是是由调度类来管理的。目前ucore仅支持单个CPU核心,所以只有一个全局的run_queue
。run_queue
实现了运行队列,其内部结构如下:enqueue
操作。RR算法直接把需要入队的进程放在调度队列的尾端,并且如果这个进程的剩余时间片为0(刚刚用完时间片被收回CPU),则需要把它的剩余时间片设为最大时间片。具体的实现如下:dequeue
操作非常普通,将相应的项从队列中删除即可:pick_next
选取队列头的表项,用le2proc
函数获得对应的进程控制块,返回:proc_tick
函数在每一次时钟中断调用。在这里,我们需要对当前正在运行的进程的剩余时间片减一。如果在减一后,其剩余时间片为0,那么我们就把这个进程标记为“需要调度”,这样在中断处理完之后内核判断进程是否需要调度的时候就会把它进行调度:round-robin
调度器,在假设所有进程都充分使用了其拥有的 CPU 时间资源的情况下,所有进程得到的 CPU 时间应该是相等的。但是有时候我们希望调度器能够更智能地为每个进程分配合理的 CPU 资源。假设我们为不同的进程分配不同的优先级,则我们有可能希望每个进程得到的时间资源与他们的优先级成正比关系。Stride调度是基于这种想法的一个较为典型和简单的算法。除了简单易于实现以外,它还有如下的特点:P.pass =BigStride / P.priority
其中P.priority
表示进程的优先权(大于 1),而 BigStride
表示一个预先定义的大常数,则该调度方案为每个进程分配的时间将与其优先级成正比。证明过程我们在这里略去,有兴趣的同学可以在网上查找相关资料。将该调度器应用到 ucore 的调度器框架中来,则需要将调度器接口实现如下:init
:enqueue
dequeue
pick_next
pass = BIG_STRIDE / P->priority; P->stride += pass
。proc_tick
:rq.max_time_slice
个时间片。PASS_MAX
为当前所有进程里最大的步进值。则我们可以证明如下结论:对每次Stride调度器的调度步骤中,有其最大的步进值STRIDE_MAX
和最小的步进值STRIDE_MIN
之差:STRIDE_MAX – STRIDE_MIN <= PASS_MAX
Priority > 1
限制,我们有STRIDE_MAX – STRIDE_MIN <= BIG_STRIDE
,于是我们只要将BigStride取在某个范围之内,即可保证对于任意两个 Stride 之差都会在机器整数表示的范围之内。而我们可以通过其与0的比较结构,来得到两个Stride的大小关系。在上例中,虽然在直接的数值表示上 98 < 65535,但是 98 - 65535 的结果用带符号的 16位整数表示的结果为99,与理论值之差相等。所以在这个意义下 98 > 65535。基于这种特殊考虑的比较方法,即便Stride有可能溢出,我们仍能够得到理论上的当前最小Stride,并做出正确的调度决定。