课程主页：https://www.xuetangx.com/course/THU08091000267/5883104?channel=i.area.learn_title
实验指导书：https://objectkuan.gitbooks.io/ucore-docs/content/
github：https://github.com/chyyuu/ucore_os_lab (master 分支)

前置知识

进程调度算法。

改动点

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

// 将默认的处理器调度算法设为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,
};

结合具体算法描述ucore调度执行过程：

  • 正如前文中所提及到的那样，在ucore中调用调度器的主体函数（不包括init，proc_tick）的代码仅存在在wakeup_proc和schedule，前者的作用在于将某一个指定进程放入可执行进程队列中，后者在于将当前执行的进程放入可执行队列中，然后将队列中选择的下一个执行的进程取出执行；
  • 当需要将某一个进程加入就绪进程队列中，则需要将这个进程的能够使用的时间片进行初始化，然后将其插入到使用链表组织的队列的对尾；这就是具体的Round-Robin enqueue函数的实现；
  • 当需要将某一个进程从就绪队列中取出的时候，只需要将其直接删除即可；
  • 当需要取出执行的下一个进程的时候，只需要将就绪队列的队头取出即可；
  • 每当出现一个时钟中断，则会将当前执行的进程的剩余可执行时间减1，一旦减到了0，则将其标记为可以被调度的，这样在ISR中的后续部分就会调用schedule函数将这个进程切换出去；

简要说明如何设计实现多级反馈队列调度算法：

  • 在proc_struct中添加总共N个多级反馈队列的入口，每个队列都有着各自的优先级，编号越大的队列优先级约低，并且优先级越低的队列上时间片的长度越大，为其上一个优先级队列的两倍；并且在PCB中记录当前进程所处的队列的优先级；

  • 处理调度算法初始化的时候需要同时对N个队列进行初始化；

  • 在处理将进程加入到就绪进程集合的时候，观察这个进程的时间片有没有使用完，如果使用完了，就将所在队列的优先级调低，加入到优先级低1级的队列中去，如果没有使用完时间片，则加入到当前优先级的队列中去；

  • 在同一个优先级的队列内使用时间片轮转算法；

  • 在选择下一个执行的进程的时候，有限考虑高优先级的队列中是否存在任务，如果不存在才转而寻找较低优先级的队列；（有可能导致饥饿）

  • 从就绪进程集合中删除某一个进程就只需要在对应队列中删除即可；

  • 处理时间中断的函数不需要改变；

  • 至此完成了多级反馈队列调度算法的具体设计；

练习二

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

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

stride相关资料：http://web.eecs.umich.edu/~mosharaf/Readings/Stride.pdf

接下来，给出 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
73
// BIG_STRIDE 取值具有一定原因，它可以保证即使 stride 取值溢出，仍可正确实现两个进程的 stride 比较操作，原理请看下方问答。
#define BIG_STRIDE    (((uint32_t)-1) / 2) // 即 0X7FFFFFFF

// 两个进程的 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 值最小的进程），并更新其 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;
     }
}

// 设置默认调度策略为 stride
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,
};

如何证明STRIDE_MAX – STRIDE_MIN <= PASS_MAX？

  • 假如该命题不成立，则可以知道就绪队列在上一次找出用于执行的进程的时候，假如选择的进程是P，那么存在另外一个就绪的进程P’，并且有P’的stride比P严格地小（因为步进值最大为PASS_MAX，若该命题不成立，那么上一次调度时被选择执行并增加stride的进程一定不是stride最小的进程）。这也就说明上一次调度出了问题，这和stride算法的设计是相违背的；因此通过反证法证明了上述命题的成立；

在 ucore 中，目前Stride是采用无符号的32位整数表示。则BigStride应该取多少，才能保证比较的正确性？

  • 开始有A=B,最大步进值S

  • B+S不溢出，则需A<B+S，即0<S,即S<2^31

  • B+S溢出代表B+S >= 2^32

    溢出后B’ = B+S-2^32

    此时为使 A-B’ < 0,需要 A >= B’+2^31

    即A >= B+S-2^32+2^31=B+S-2^31

    又由A=B，有0>=S-2^31，即S<=2^31

  • 综合有S<2^31，即S<=0x7FFFFFFF