ucore-lab6

本文最后更新于：2023年6月22日 上午

练习解答

练习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不难找到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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算法的实现，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static void
RR_init(struct run_queue *rq) {
    list_init(&(rq->run_list));
    rq->proc_num = 0;
}
//初始化对应的list
//run queue的进程号设置为0
static void
RR_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 void
RR_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 void
RR_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调度算法的一些相关的资料（目前网上中文的资料比较欠缺）。

执行：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

这里贴一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#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 int
proc_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 void
stride_init(struct run_queue *rq) {
    list_init(&(rq->run_list));
   
    rq->lab6_run_pool = NULL;
    rq->proc_num = 0;
}
//enqueue以及dequeue更新指针即可
static void
stride_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 void
stride_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 void
stride_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行，我们来看一下这一段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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使用红黑树来进行快速高效的插入和删除进程。

仍是参考PKUanonym的仓库：ucore

先上结果：

下面分析佬的代码，

kern/schedule/cfs_sched.h没有什么大的改变，改个名字就好了

kern/schedule/cfs_sched.c中，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#define NICE_0_LOAD 1024

static int
proc_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 void
cfs_init(struct run_queue *rq) {
	rq->lab6_run_pool = NULL;
	rq->proc_num = 0;
}
//enqueue以及dequeue没什么说的
static void
cfs_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 void
cfs_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 void
cfs_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

看着就知道工作量大，没空，也不会。

闲了再说。

blog
cs ucore

本文作者: Heeler-Deer
本文链接: https://heeler-deer.top/posts/44538/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！