lagrange's blog

what's dead may never die

0%

Lab6 实验报告

发表于 更新于 分类于

Lab6

Round Robin 调度算法

请理解并分析 sched_class 中各个函数指针的用法，并结合 Round Robin 调度算法描 ucore 的调度执行过程

sched_class 中各个函数指针的用法

sched_class 的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// The introduction of scheduling classes is borrrowed from Linux, and makes the
// core scheduler quite extensible. These classes (the scheduler modules) encapsulate
// the scheduling policies.
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[]);
     */
};

其中，const char *name指向了当前调度算法的名称字符串

void (*init)(struct run_queue *rq)用于初始化传入的就绪队列。RR 算法中只初始化了对应 run_queue 的 run_list 成员。

1
2
3
4
5
static void
RR_init(struct run_queue *rq) {
    list_init(&(rq->run_list));
    rq->proc_num = 0;
}

void (*enqueue)(struct run_queue *rq, struct proc_struct *proc)用于将某个进程添加进传入的队列中。RR 算法除了将进程添加进队列中，还重置了相关的时间片。

1
2
3
4
5
6
7
8
9
10
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) {
        proc->time_slice = rq->max_time_slice;
  }
    proc->rq = rq;
    rq->proc_num ++;
}

void (*dequeue)(struct run_queue *rq, struct proc_struct *proc)用于将某个进程从传入的队列中移除。以下是 RR 算法的实现

1
2
3
4
5
6
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 --;
}

struct proc_struct *(*pick_next)(struct run_queue *rq)用于在传入的就绪队列中选择出一个最适合运行的进程（选择进程但不将从队列中移除）。在 RR 算法中每次都只选择队列最前面那个进程。

1
2
3
4
5
6
7
8
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;
}

void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc)。该函数会在时间中断处理例程中被调用，以减小当前运行进程的剩余时间片。若时间片耗尽，则设置当前进程的 need_resched 为 1。

1
2
3
4
5
6
7
8
9
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;
    }
}

结合 Round Robin 调度算法描 uCore 的调度执行过程

首先，uCore 调用 sched_init 函数用于初始化相关的就绪队列。

之后在 proc_init 函数中，建立第一个内核进程，并将其添加至就绪队列中。

当所有的初始化完成后，uCore 执行 cpu_idle 函数，并在其内部的 schedule 函数中，调用 sched_class_enqueue 将当前进程添加进就绪队列中（因为当前进程要被切换出 CPU 了）
然后，调用 sched_class_pick_next 获取就绪队列中可被轮换至 CPU 的进程。如果存在可用的进程，则调用 sched_class_dequeue 函数，将该进程移出就绪队列，并在之后执行 proc_run 函数进行进程上下文切换。

需要注意的是，每次时间中断都会调用函数 sched_class_proc_tick。该函数会减少当前运行进程的剩余时间片。如果时间片减小为 0，则设置 need_resched 为 1，并在时间中断例程完成后，在 trap 函数的剩余代码中进行进程切换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void trap(struct trapframe *tf) {
    if (current == NULL)
        trap_dispatch(tf);
    else {
        struct trapframe *otf = current->tf;
        current->tf = tf;
        bool in_kernel = trap_in_kernel(tf);
        // 执行对应的中断处理例程
        trap_dispatch(tf);
        // 恢复对应的trapframe
        current->tf = otf;
        // 如果当前中断的是用户进程
        // 注意这里体现出用户进程的可抢占性
        if (!in_kernel) {
            if (current->flags & PF_EXITING)
                do_exit(-E_KILLED);
            // 如果在中断处理例程中设置need_resched为1，则在此处切换进程
            if (current->need_resched)
                schedule();
        }
    }
}