lab6 — 调度器

前置知识

进程调度算法。

改动点

相比于 lab5 源代码,lab6 主要做了如下改动:

  • proc.h 扩展 struct proc_struct 成员属性

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct proc_struct {
    ... // 同以往结构的属性
    struct run_queue *rq; // 该进程所在的 run_queue
    list_entry_t run_link; // 以链表形式链接各就绪进程
    int time_slice; // 该进程所占用的 CPU 时间片
    skew_heap_entry_t lab6_run_pool; // FOR LAB6 ONLY: 以优先队列形式链接各就绪进程
    // 当前进程的 stride 和优先级属性。
    uint32_t lab6_stride; // FOR LAB6 ONLY: 该进程对应的 stride 属性 (此二者用于 stride 调度算法)
    uint32_t lab6_priority; // FOR LAB6 ONLY: 该进程对应的 priority 属性
    };

    alloc_proc() 实现中,增加这些属性的初始化工作:

    1
    2
    3
    4
    5
    list_init(&(proc->run_link));
    proc->time_slice = 0;
    skew_heap_init(&(proc->lab6_run_pool));
    proc->lab6_stride = 0;
    proc->lab6_priority = 0;
  • schedule.[ch] 增加调度器框架信息

    ucore 调度器框架使用 struct sched_class 加以表示:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    struct sched_class {
    // 调度器名称
    const char *name;
    // 初始化调度器
    void (*init)(struct run_queue *rq);
    // 进程入队
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
    // 进程出队
    void (*dequeue)(struct run_queue *rq, struct proc_struct *proc);
    // 选择待运行的进程
    struct proc_struct *(*pick_next)(struct run_queue *rq);
    // 时钟触发的处理函数
    void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc);
    };

    ucore 调度器具体使用 struct run_queue 进行处理:

    1
    2
    3
    4
    5
    6
    struct run_queue {
    list_entry_t run_list; // 进程集合的链表形式
    unsigned int proc_num; // 进程集合总数
    int max_time_slice; // 进程运行的最大时间片
    skew_heap_entry_t *lab6_run_pool; // For LAB6 ONLY: 进程集合的优先队列形式
    };
  • trap.c 更新时钟中断的处理程序

    每当发生时钟中断,调用 ucore 调度器的 proc_tick() 函数,从而使得调度器能够动态感知时间变化,并更新相关进程的某些调度属性信息。

    1
    2
    3
    case IRQ_OFFSET + IRQ_TIMER:
    ticks++;
    sched_class_proc_tick(current);
  • default_sched.[ch] 实现 Round-Robin 调度算法

  • sched.c 更新 wakeup_proc() 操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void wakeup_proc(struct proc_struct *proc) {
    assert(proc->state != PROC_ZOMBIE);
    bool intr_flag;
    local_intr_save(intr_flag);
    {
    // proc 若未处于 RUNNABLE 状态,则置为此状态。
    if (proc->state != PROC_RUNNABLE) {
    proc->state = PROC_RUNNABLE;
    proc->wait_state = 0;
    // 若当前进程并非 proc,则将 proc 入队 (出现情况:当前进程创建子进程,子进程的 do_fork 最后一步会调用此函数,从而将其入队管理)。
    if (proc != current) {
    sched_class_enqueue(proc);
    }
    }
    else {
    warn("wakeup runnable process.\n");
    }
    }
    local_intr_restore(intr_flag);
    }
  • skew_heap.h 提供斜堆的具体实现

练习一

该练习用于了解 Round-Robin 调度算法的具体实现。

Round-Robin 调度算法比较简单,直接查看源代码实现:

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
// 初始化 RR,只需初始化进程集合,并重置相关属性即可 (max_time_slice 属性由调用者自主设置)。
static void RR_init(struct run_queue *rq) {
list_init(&(rq->run_list));
rq->proc_num = 0;
}

// 入队。
static void RR_enqueue(struct run_queue *rq, struct proc_struct *proc) {
// 放置当前进程于进程集合尾部。
list_add_before(&(rq->run_list), &(proc->run_link));
// 如果其所剩时间片为 0,或不符合条件,则重置之。
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 ++;
}

// 出队,进程集合中删除此进程,并初始化此进程的 run_link 即可。
static void RR_dequeue(struct run_queue *rq, struct proc_struct *proc) {
//
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;
}

// 每次发生时钟中断,更新当前进程可用的时间片,如果可用时间片为 0,则设置 need_resched 以调度其他进程 (该字段在 trap() 的 if(!in_kernel) 内起作用)。
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;
}
}

// sched_class 的 RR 实现
struct sched_class default_sched_class = {
.name = "RR_scheduler",
.init = RR_init,
.enqueue = RR_enqueue,
.dequeue = RR_dequeue,
.pick_next = RR_pick_next,
.proc_tick = RR_proc_tick,
};

练习二

该练习用于实现 Stride 调度算法。

首先简单介绍 Stride 调度算法的基本思想:Stride 调用算法仍是基于时间片以调度进程,但是它每次选择进展最慢 (表征进程的 struct proc_struct 结构中,stride 表示当前进程的进展度,BIG_STRIDE / priority 表征当前进程被调度后的进展增加值) 的进程加以调度。

接下来,给出 Stride 调度算法的具体实现:

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
// BIG_STRIDE 取值具有一定原因,它可以保证即使 stride 取值溢出,仍可正确实现两个进程的 stride 比较操作,原理忽略。
#define BIG_STRIDE (((uint32_t)-1) / 2)

// 两个进程的 stride 比较操作,用于构建斜堆。
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;
}

// 初始化 Stride,只需初始化进程集合,并重置相关属性即可。
static void stride_init(struct run_queue *rq) {
list_init(&(rq->run_list)); // 是否初始化进程集合的链表形式都可,因为不会用到。
rq->lab6_run_pool = NULL;
rq->proc_num = 0;
}

// 入队,插入当前进程至斜堆,并更新相关属性。
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);
// 如果尚未初始化 priority,则默认取值为 1。
if (proc->lab6_priority == 0)
{
proc->lab6_priority = 1;
}

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--;
}

// 选择 stride 最小的进程作为待运行的进程,并更新其 stride 取值。
static struct proc_struct * stride_pick_next(struct run_queue *rq) {
if (rq->lab6_run_pool != NULL)
{
struct proc_struct* proc = le2proc(rq->lab6_run_pool, lab6_run_pool);
proc->lab6_stride += (BIG_STRIDE / proc->lab6_priority);
return proc;
}
return NULL;
}

// 与 RR 所取操作相同。
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,
};