lab6 — 调度器

发表于 分类于
本文字数： 5.8k 阅读时长 ≈ 5 分钟

前置知识

进程调度算法。

改动点

相比于 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,
};