练习解答
练习0
填写实验
- kern/process/proc.c
- kern/mm/pmm.c
有需要更改的文件，建议看Kiprey
练习1
练习1: 使用 Round Robin 调度算法（不需要编码） 完成练习0后，建议大家比较一下（可用kdiff3等文件比较软件）个人完成的lab5和练习0完成后的刚修改的lab6之间的区别，分析了解lab6采用RR调度算法后的执行过程。执行make grade，大部分测试用例应该通过。但执行priority.c应该过不去。 请在实验报告中完成：
- 请理解并分析sched_class中各个函数指针的用法，并结合Round Robin 调度算法描ucore的调度执行过程
- 请在实验报告中简要说明如何设计实现”多级反馈队列调度算法“，给出概要设计，鼓励给出详细设计
请理解并分析sched_class中各个函数指针的用法，并结合Round Robin 调度算法描ucore的调度执行过程
在kern/schedule/sched.h不难找到：
123456789101112131415161718192021 | struct sched_class { // the name of sched_class const char *name; // Init the run queue void (*init)(struct run_queue *rq); // put the proc into runqueue, and this function must be called with rq_lock void (*enqueue)(struct run_queue *rq, struct proc_struct *proc); // get the proc out runqueue, and this function must be called with rq_lock void (*dequeue)(struct run_queue *rq, struct proc_struct *proc); // choose the next runnable task struct proc_struct *(*pick_next)(struct run_queue *rq); // dealer of the time-tick void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc); /* for SMP support in the future * load_balance * void (*load_balance)(struct rq* rq); * get some proc from this rq, used in load_balance, * return value is the num of gotten proc * int (*get_proc)(struct rq* rq, struct proc* procs_moved[]); */}; |
|---|
由于时间较紧，且根据注释易于理解，此处不再赘述
在kern/schedule/default_sched.c不难找到rr算法的实现，
123456789101112131415161718192021222324252627282930313233343536373839404142434445 | static voidRR_init(struct run_queue *rq) { list_init(&(rq->run_list)); rq->proc_num = 0;}//初始化对应的list//run queue的进程号设置为0static voidRR_enqueue(struct run_queue *rq, struct proc_struct *proc) { assert(list_empty(&(proc->run_link))); list_add_before(&(rq->run_list), &(proc->run_link)); if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) { //进程时间片等于0或者大于最大时间片时，重新赋值 proc->time_slice = rq->max_time_slice; } proc->rq = rq; rq->proc_num ++;}//将进程添加至队列，static voidRR_dequeue(struct run_queue *rq, struct proc_struct *proc) { assert(!list_empty(&(proc->run_link)) && proc->rq == rq); list_del_init(&(proc->run_link)); rq->proc_num --;}//去除队列static struct proc_struct *RR_pick_next(struct run_queue *rq) { list_entry_t *le = list_next(&(rq->run_list)); if (le != &(rq->run_list)) { return le2proc(le, run_link); } return NULL;}//选择队列最前面的进程static voidRR_proc_tick(struct run_queue *rq, struct proc_struct *proc) { if (proc->time_slice > 0) { proc->time_slice --; } if (proc->time_slice == 0) { proc->need_resched = 1; }}//tick,用于时间片的处理，等于0是重新安排（resched） |
|---|
如注释所示。
那么也就是说，ucore的RR算法，首先调用kern/schedule/sched.c中的sched_init函数进行初始化（加入list），之后初始化进程(proc目录下的函数)，ucore执行cpu_idle（proc目录下）函数，调用sched_class_enqueue加入队列，启动进程计时器。之后pick_next,有可以执行的进程就dequeue,继续proc_run.
相关调用图：
请在实验报告中简要说明如何设计实现”多级反馈队列调度算法“，给出概要设计，鼓励给出详细设计
多级反馈队列实际上是通过设置多个优先级不同的队列实现，其中优先级越高，时间片越高。在enqueue中，如果该进程时间片为0则不改变其优先级，大于0则降低其优先级；调度时，参照ostep的规则，如果 A 的优先级 > B 的优先级，运行 A（不运行 B）；如果 A 的优先级 = B 的优先级，轮转运行A 和 B；新进程进入系统时，放在最高优先级（最上层队列）；一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）；经过一段时间 S，就将系统中所有工作重新加入最高优先级队列。
练习二
练习2: 实现 Stride Scheduling 调度算法（需要编码） 首先需要换掉RR调度器的实现，即用default_sched_stride_c覆盖default_sched.c。然后根据此文件和后续文档对Stride度器的相关描述，完成Stride调度算法的实现。 后面的实验文档部分给出了Stride调度算法的大体描述。这里给出Stride调度算法的一些相关的资料（目前网上中文的资料比较欠缺）。
- strid-shed paper location1
- strid-shed paper location2
- 也可GOOGLE “Stride Scheduling” 来查找相关资料
执行：make grade。如果所显示的应用程序检测都输出ok，则基本正确。如果只是priority.c过不去，可执行 make run-priority 命令来单独调试它。大致执行结果可看附录。（ 使用的是 qemu-1.0.1 ）。 请在实验报告中简要说明你的设计实现过程。
所谓stride算法，实际上就是通过对每一个进程添加一个stride以及一个pass数据，每次选择最小stride(或者说离cpu最近)的进程执行，执行后该进程的stride添加步长pass.其中pass与优先级成反比，pass=BIG_STRIDE / priority
关于BIG_STRIDE的详细推导建议参考yuerer
具体代码实现建议参考kiprey
这里贴一下代码：
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 | #include <defs.h>#include <list.h>#include <proc.h>#include <assert.h>#include <default_sched.h>#define USE_SKEW_HEAP 1/* You should define the BigStride constant here*//* LAB6: YOUR CODE */#define BIG_STRIDE ((uint32_t) -1) / 2//选取合适的进程static intproc_stride_comp_f(void *a, void *b){ struct proc_struct *p = le2proc(a, lab6_run_pool); struct proc_struct *q = le2proc(b, lab6_run_pool); int32_t c = p->lab6_stride - q->lab6_stride; if (c > 0) return 1; else if (c == 0) return 0; else return -1;}//直接选取斜堆的顶端，static struct proc_struct *stride_pick_next(struct run_queue *rq) { skew_heap_entry_t* she = rq->lab6_run_pool; if (she != NULL) { struct proc_struct* p = le2proc(she, lab6_run_pool); //更新stride p->lab6_stride += BIG_STRIDE / p->lab6_priority; return p; } return NULL;}//初始化，多了一个指针static voidstride_init(struct run_queue *rq) { list_init(&(rq->run_list)); rq->lab6_run_pool = NULL; rq->proc_num = 0;}//enqueue以及dequeue更新指针即可static voidstride_enqueue(struct run_queue *rq, struct proc_struct *proc) { rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f); if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) { proc->time_slice = rq->max_time_slice; } proc->rq = rq; rq->proc_num ++;}static voidstride_dequeue(struct run_queue *rq, struct proc_struct *proc) { rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f); rq->proc_num --;}//tick正常static voidstride_proc_tick(struct run_queue *rq, struct proc_struct *proc) { if (proc->time_slice > 0) { proc->time_slice --; } if (proc->time_slice == 0) { proc->need_resched = 1; }}//改一下名字就好了struct sched_class default_sched_class = { .name = "stride_scheduler", .init = stride_init, .enqueue = stride_enqueue, .dequeue = stride_dequeue, .pick_next = stride_pick_next, .proc_tick = stride_proc_tick,}; |
|---|
到这里，执行make grade时，会出错。
根据网上博客，解决办法是注释掉grade.sh的221到233行，我们来看一下这一段：
1234567891011121314151617 | # found和not相等就为真# found,not都是标志变量，# not在代码没有错误的情况下为0# found=$(($? == 0)),不是很清楚在干什么。。。if [ $found -eq $not ]; then if [ $found -eq 0 ]; then msg="!! error: missing '$i'" else msg="!! error: got unexpected line '$i'" fi okay=no if [ -z "$error" ]; then error="$msg" else error="$error\n$msg" fi fi |
|---|
这一段是在check_regexps里面，okay为no时就会报错，而ucore的最终得分就是通过检查有无报错产生的。如果想蒙混过关，把这个no改成yes或者注释掉这一段代码或者把-eq改成-ne就行了
但如果每一次验收实验都只是为了验收而验收，自己什么都没学到，那还有什么意思呢？
当然对os不感兴趣的话混就得了
实际上，我们的错误是由于一个细节，在之前的kern/schedule/default_sched.c中，优先级初始化为0，而0在stride中是不能作为被除数存在的，因此需要更改kern/process/proc.c中的proc->lab6_priority为1。
结果：
Challenge 1
扩展练习 Challenge 1 ：实现 Linux 的 CFS 调度算法
在ucore的调度器框架下实现下Linux的CFS调度算法。可阅读相关Linux内核书籍或查询网上资料，可了解CFS的细节，然后大致实现在ucore中。
CFS （完全公平调度器）实现的主要思想是维护为任务提供处理器时间方面的平衡（公平性）。它给每个进程设置了一个虚拟时钟vruntime。其中vruntime=实际运行时间∗1024/进程权重 进程按照各自不同的速率在物理时钟节拍内前进，优先级高则权重大，其虚拟时钟比真实时钟跑得慢，但获得比较多的运行时间；CFS调度器总是选择虚拟时钟跑得慢的进程来运行，从而让每个调度实体的虚拟运行时间互相追赶，进而实现进程调度上的平衡。 CFS使用红黑树来进行快速高效的插入和删除进程。
先上结果：
下面分析佬的代码，
kern/schedule/cfs_sched.h没有什么大的改变，改个名字就好了
kern/schedule/cfs_sched.c中，
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 | #define NICE_0_LOAD 1024static intproc_cfs_comp_f(void *a, void *b){ struct proc_struct *p = le2proc(a, lab6_run_pool); struct proc_struct *q = le2proc(b, lab6_run_pool); int32_t c = p->lab6_stride - q->lab6_stride; if (c > 0) return 1; else if (c == 0) return 0; else return -1;}//绝对公平，不需要list或者其他数据static voidcfs_init(struct run_queue *rq) { rq->lab6_run_pool = NULL; rq->proc_num = 0;}//enqueue以及dequeue没什么说的static voidcfs_enqueue(struct run_queue *rq, struct proc_struct *proc) { rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_cfs_comp_f); if (proc->time_slice == 0 || proc->time_slice > rq->max_time_slice) { proc->time_slice = rq->max_time_slice; } proc->rq = rq; rq->proc_num += 1;}static voidcfs_dequeue(struct run_queue *rq, struct proc_struct *proc) { rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_cfs_comp_f); rq->proc_num -= 1;}//通过设置进程的时间来改变优先级，类似与stride//可以对比一下，/*static struct proc_struct *stride_pick_next(struct run_queue *rq) { skew_heap_entry_t* she = rq->lab6_run_pool; if (she != NULL) { struct proc_struct* p = le2proc(she, lab6_run_pool); //更新stride p->lab6_stride += BIG_STRIDE / p->lab6_priority; return p; } return NULL;}*/static struct proc_struct *cfs_pick_next(struct run_queue *rq) { if (rq->lab6_run_pool == NULL) return NULL; struct proc_struct* min_proc = le2proc(rq->lab6_run_pool, lab6_run_pool); if (min_proc->lab6_priority == 0) { min_proc->lab6_stride += NICE_0_LOAD; } else if (min_proc->lab6_priority > NICE_0_LOAD) { min_proc->lab6_stride += 1; } else { min_proc->lab6_stride += NICE_0_LOAD / min_proc->lab6_priority; } return min_proc;}//tick没什么static voidcfs_proc_tick(struct run_queue *rq, struct proc_struct *proc) { if (proc->time_slice > 0) { proc->time_slice --; } if (proc->time_slice == 0) { proc->need_resched = 1; }}struct sched_class cfs_sched_class = { .name = "cfs_scheduler", .init = cfs_init, .enqueue = cfs_enqueue, .dequeue = cfs_dequeue, .pick_next = cfs_pick_next, .proc_tick = cfs_proc_tick,}; |
|---|
Challenge 2
腾讯云开发者
