前言

五一佳节,宜学习。继续我们的lab6,lab6涉及到的是进程的调度,在lab5中进程调度只是简单的FIFO,而我们要在这里学习,实现调度器的部分(ps:咕到现在才传,有点累)。

正文

Part0

同样是利用clion的compare功能,将lab1,2,3,4,5的内容填入到lab6中,然后我们还需要调整一部分代码来满足lab6。

主要填补的文件是:

  • default_pmm.c
  • kedebug.c
  • pmm.c
  • proc.c
  • swap_fifo.c
  • trap.c
  • vmm.c

然后需要更改的几个文件

proc.c,添加了几个需要初始化的状态

trap.c中的trap_dispatch函数,需要改变下使用时钟的函数

Part1 使用 Round Robin 调度算法(不需要编码)

我们需要看下整个进程调度的架构

类似页面置换,我们同样拥有一个算法的框架调度器,让具体算法抽象出来,然后我们怎么维护进程呢,ucore里面维护了一个全局变量,一个双向链表来维护进程队列,

然后看一下proc.h中同样维护了一些信息

然后我们看下rr算法的具体思想:RR调度算法的调度思想 是让所有runnable态的进程分时轮流使用CPU时间。RR调度器维护当前runnable进程的有序运行队列。当前进程的时间片用完之后,调度器将当前进程放置到运行队列的尾部,再从其头部取出进程进行调度。

RR_init初始化,初始化rq的run_list队列,然后设置运行队列中的数目

RR_enqueue加入进程到rq的末尾,如果proc时间用完了要重置一下max_time_slice,然后指定好这个proc的rq是哪一个方便从proc struct反向找到rq,

RR_dequeue删除,删除就绪队列中的进程控制块指针

RR_pick_next来选下一个进程,选择下一个,然后判断不是自己本身,就是说存在proc在rq中,那么就返回proc

RR_proc_tick,大于0时,就-1,为0时就标记为可调度

最后完成函数接口的完成,实现了算法分离

Part2 实现 Stride Scheduling 调度算法(需要编码)

首先将default_sched_stride_c中的内容覆盖default_sched.c的内容,然后我们需要完成ss算法的具体内容,然后我们看下ss算法的大概思路.

  1. 为每个runnable的进程设置一个当前状态stride,表示该进程当前的调度权。另外定义其对应的pass值,表示对应进程在调度后,stride 需要进行的累加值。
  2. 每次需要调度时,从当前 runnable 态的进程中选择 stride最小的进程调度。
  3. 对于获得调度的进程P,将对应的stride加上其对应的步长pass(只与进程的优先权有关系)。
  4. 在一段固定的时间之后,回到 2.步骤,重新调度当前stride最小的进程。
    可以证明,如果令 P.pass =BigStride / P.priority 其中 P.priority 表示进程的优先权(大于 1),而 BigStride 表示一个预先定义的大常数,则该调度方案为每个进程分配的时间将与其优先级成正比。

然后我们分别填充里面的函数

首先定义定义一个宏

然后他给我们提供了提个比较函数proc_stride_comp_f

rq中的lab6_run_pool是一个优先队列结构的,用来指向优先队列的头元素

然后我们实现第一个函数stride_init,初始化rq的run_list,然后将lab6_run_pool指向空

stride_enqueue

有个条件编译USE_SKEW_HEAP为1所以只执行if,这里是插入到优先队列中,然后判断时间片是否用完,如果是就重置

然后是删除stride_dequeue,删除优先队列中的

stride_pick_next,因为是用优先队列所以可以用le2proc直接拿一下proc,如果优先级为0则设置一下步长,否则BIG_STRIDE / p->lab6_priority

最后是stride_proc_tick,差不多

最后make grade能过全部的测试说明可以了.

流程总结

这里没有太大的改变就是,添加了sched的算法分离的结构,然后有几个地方会调用到schedule这个函数,来进行到进程调度,然后我们看下在init.c中添加了一个sched_init();进行初始化调度结构,然后看下有几个调度点:

编号位置原因
1proc.c::do_exit用户线程执行结束,主动放弃CPU控制权。
2proc.c::do_wait用户线程等待子进程结束,主动放弃CPU控制权。
3proc.c::init_main1. initproc内核线程等待所有用户进程结束,如果没有结束,就主动放弃CPU控制权; 2. initproc内核线程在所有用户进程结束后,让kswapd内核线程执行10次,用于回收空闲内存资源
4proc.c::cpu_idleidleproc内核线程的工作就是等待有处于就绪态的进程或线程,如果有就调用schedule函数
5sync.h::lock在获取锁的过程中,如果无法得到锁,则主动放弃CPU控制权
6trap.c::trap如果在当前进程在用户态被打断去,且当前进程控制块的成员变量need_resched设置为1,则当前线程会放弃CPU控制权

主要就是主动放弃例如1,2,5,然后3,4,initproc内核线程等待用户进程结束而执行schedule函数;idle内核线程在没有进程处于就绪态时才执行,一旦有了就绪态的进程,它将执行schedule函数完成进程调度.最特殊的是6是trap来完成的进程切换,只有用户态的进程可以被打断,然后need_resched为1才行,类似一下代码

总结

这个lab6还是比较简单的,但是最近太忙了并且有点累,就先写到这里吧