ucore lab6

lab5完成了用户进程的管理，可在用户态运行多个进程。但是lab5所采用的调度策略为简单的FIFO策略，未考虑到进程的特征，性能比较差。lab 6对ucore的调度部分进行了修改，设计了系统调度器框架，不涉及具体的调度算法。之后，ucore基于此框架实现了RR调度算法。另外，考虑到进程优先级的问题，又引入了stride调度算法。

填写已有实验

本实验依赖实验1/2/3/4/5。请把你做的实验2/3/4/5的代码填入本实验中代码中有“LAB1”/“LAB2”/“LAB3”/“LAB4”“LAB5”的注释相应部分。并确保编译通过。注意：为了能够正确执行lab6的测试应用程序，可能需对已完成的实验1/2/3/4/5的代码进行进一步改进。
由于proc数据结构有所扩展，所以在proc.c中alloc_proc初始化需添加以下内容

static struct proc_struct *alloc_proc(void) {
    proc->rq = NULL;//进程所属运行队列
    list_init(&(proc->run_link));//运行队列的哨兵结构
    proc->time_slice = 0;//进程时间片
}

在响应时钟中断时让操作系统感知操作

case IRQ_OFFSET + IRQ_TIMER:
        ticks ++;
        assert(current != NULL);
        sched_class_proc_tick(current);//设置当前进程的调度状态
        break;

在之前的ucore中，中断时调用run_timer_list，先检查timer_list中的进程时间是否到期，若到期则唤醒该进程，若没有则expires–;再调用sche_proc_proc_tick设置当前进程的调度状态。进程如果需要等待一段时间后再唤醒，则需要用到timer结构，timer记录唤醒的时间，每次中断时从timer_list中查找到期的进程进行唤醒。让人奇怪的在于,之前的ucore中定义了timer的数据结构，以及对应的函数，却没有什么进程会面临这种情况。现在的ucore只是简单初始化timer_list,后续也并没有使用到此数据结构。

// the list of timer
static list_entry_t timer_list;
void
sched_init(void) {
    list_init(&timer_list);

    sched_class = &default_sched_class;

    rq = &__rq;
    rq->max_time_slice = MAX_TIME_SLICE;
    sched_class->init(rq);

    cprintf("sched class: %s\n", sched_class->name);
}

进程状态

进程调度算法涉及到进程状态的转换。在ucore的具体实现中，进程控制块结构proc_struct 中成员变量state 用于描述进程的运行状态。其中运行态和就绪态的状态值相同，均为PROC_RUNNABLE ,二者区别在于运行态的进程不会放在运行队列中。

进程的正常生命周期如下：

1. 进程首先在cpu初始化或sys_fork的时候被创建，当为该进程分配了一个进程控制块之后，该进程进入uninit态。
2. 当进程完全初始化后，该进程转为runnable态
3. 当到达调度点时，由调度器 sched_class 根据运行队列rq的内容来判断一个进程是否应该被运行，即把处于runnable态的进程转换成running状态，从而占用CPU执行。
4. running态的进程通过wait等系统调用被阻塞，进入sleeping态。
5. sleeping态的进程被wakeup变成runnable态的进程。
6. running态的进程主动 exit 变成zombie态，然后由其父进程完成对其资源的最后释放，子进程的进程控制块成为unused。
7. 所有从runnable态变成其他状态的进程都要出运行队列，反之，被放入某个运行队列中。

进程调度实现

内核抢占点

对于用户进程而言，中断的产生可以随时打断用户进程的执行，转到操作系统内部，从而操作系统拥有了调度控制权，可以选择其他用户执行，所以用户进程是可以抢占的。ucore内核执行同样是可抢占的，在执行任意内核代码时，cpu控制权可强制剥夺。

但是以下几种例外情况不可剥夺：

• 进行同步互斥操作，比如争抢一个信号量、锁；
• 进行磁盘读写等耗时的异步操作，由于等待完成的耗时太长，ucore会调用schedule让其他就绪进程执行。

以上情况都是由于当前进程所需的某个资源得不到满足而无法继续下去，不得不主动放弃对cpu的控制权。

调度点

lab6涉及到的调度点：

• proc.c:do_exit　户线程执行结束，主动放弃CPU
• proc.c:do_wait　用户线程等待子进程结束，主动放弃CPU
• proc.c::cpu_idle　idleproc内核线程选取一个就绪进程并切换
• trap.c::trap　　若时间片用完，则设置need_resched为1，让当前进程放弃CPU

数据结构

在进程的执行过程中，就绪进程的等待时间和执行进程的执行时间是调度考虑的主要部分。这两者随着时间的流逝和时间的发生动态变化。为了让操作系统感知进程状态变化的情况，引入timer时间感知操作，在进程运行或等待的过程中，调度器可以调整进程控制块中与进程调度相关的属性值。

ucore调度框架定义了以下接口：

struct sched_class {
    // 调度器的名字
    const char *name;
    //初始化运行队列
    void (*init)(struct run_queue *rq);
    //将进程p插入队列rq
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
    //将进程p从队列中删除
    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);
};

proc.h中的proc_struct中调度相关信息有：

struct proc_struct {
    //该进程是否需要调度，只对当前进程有效
    volatile bool need_resched;                 
    //运行队列
    struct run_queue *rq;
    //该进程的调度链表结构
    list_entry_t run_link;
    //该进程剩余的时间片，只对当前进程有效
    int time_slice;
    //RR算法并不会用到以下成员
    skew_heap_entry_t lab6_run_pool;
    //在优先队列中的节点
    uint32_t lab6_stride;
    //该进程的调度优先级
    uint32_t lab6_priority;
    //该进程的调度步进值
};

通过数据结构run_queue来描述run_queue,主要结构为

struct run_queue {
    //某运行队列的头或尾
    list_entry_t run_list;
    //内部的进程总数
    unsigned int proc_num;
    //每个进程一轮占用的最多时间
    int max_time_slice;
    //优先队列形式的进程容器
    skew_heap_entry_t *lab6_run_pool;
};

在ucore中，运行队列中存储当前可调度的进程，只有状态为runnable的进程才可以进入运行队列，其中当前正在运行的进程不会进入运行队列。

Round Robin调度算法

RR调度算法的调度思想是让所有运行队列中的进程分时轮流使用CPU时间。当前进程的时间片用完之后，调度器将当前进程放置到运行队列的尾部，再从其头部取出进程进行调度。RR调度算法的就绪队列在组织结构上也是一个双向链表，只是增加了一个成员变量，表明在此就绪进程队列中的最大执行时间片。而且在进程控制块proc_struct中增加了一个成员变量time_slice，用来记录进程当前的可运行时间片段。在每个timer到期的时候，操作系统会递减当前执行进程的time_slice，当time_slice为0时，就意味着这个进程运行了一段时间（这个时间片段称为进程的时间片），需要把CPU让给其他进程执行，于是操作系统就需要让此进程重新回到rq的队列尾，且重置此进程的时间片为就绪队列的成员变量最大时间片max_time_slice值，然后再从rq的队列头取出一个新的进程执行。

RR调度算法具体实现如下：

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

RR_enqueue把某进程的进程控制块指针放入到rq队列末尾，如果进程控制块时间片为0，则需要把它重置为rq成员变量max_time_slice，等待分配下一个时间片再运行。

static struct proc_struct *
FCFS_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;
}

RR_pick_next选区就绪进程队列rq中的队首队列元素，并根据队列元素找到对应的进程控制块。

static void
FCFS_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 --;
}

RR_dequeue把就绪进程队列rq的进程控制块指针的队列元素删除，并把表示就绪进程个数的proc_num减一。

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

每次timer到时后，trap函数将会间接调用RR_proc_tick来把当前执行进程的时间片time_slice减一。如果time_slice降到零，则设置此进程成员变量need_resched标识为1，这样在下一次中断来后执行trap函数时，会由于当前进程程成员变量need_resched标识为1而执行schedule函数，从而把当前执行进程放回就绪队列末尾，而从就绪队列头取出在就绪队列上等待时间最久的那个就绪进程执行。

sched_class中各个函数指针的用法

• init 初始化运行队列的参数。
• **enqueue ** 将可调度的进程放入调度队列
• dequeue 将该进程从调度队列删除
• pick_next 根据调度策略选择下一个进程
• proc_tick响应时钟中断，减少当前进程时间片，若为0则重新调度

ucore的调度过程：

1. 设置当前进程剩余时间片
2. 每次时钟中断，当前进程剩余时间片减一
3. 剩余时间片为0时，会将当前进程的 need_resched 设置为1
4. 从trap函数可知，在trap_dispatch之后，由于need_resched = 1，因此进入schedule进入调度器
   将当前进程加入到数据结构中，并且取出数据结构中优先级最高的进程。

• 若sched_class_pick_next返回不为null，则选择该进程
• 若sched_class_pick_next返回为null，则设置下一进程为idleproc，idleproc死循环查找可被调度的进程

5. 调用 proc_run() 进行进程切换

设计实现多级反馈队列调度算法

多级反馈队列算法初步设计如下：

• init 初始化所有队列，将优先级设置为最高
• enqueue 该进程时间片为0时判断进程是否处于zombie状态，若不是，则降低有限级放入对应队列中，将时间片设置为该优先级队列的时间片
• dequeue 将该进程从对应优先级调度队列删除
• pick_next 根据优先级算法啊判断是否需要转移队列
• proc_tick 与之前实现一致

Stride 调度算法

RR算法所有进程得到的时间是相等的，而我们希望每个进程得到的时间资源与其优先级成正比关系，由此引入了Stride Scheduling算法。

基本思路

基本思想如下：

1. 为每个runnable的进程设置一个当前状态stride，表示该进程当前的调度权。另外定义其对应的pass值，表示对应进程在调度后，stride 需要进行的累加值。
2. 每次需要调度时，从当前 runnable 态的进程中选择 stride最小的进程调度。
3. 对于获得调度的进程P，将对应的stride加上其对应的步长pass（只与进程的优先权有关系）。
4. 在一段固定的时间之后，回到 2.步骤，重新调度当前stride最小的进程。

特征

stride调度算法为动态优先级调度算法，线程的执行时间与步进值的倒数成正比，简单易于实现。

• 可控性 可以证明stride scheduling对进程的调度次数正比于其优先级
• 确定性 在不考虑计时器时间的情况下，整个调度机制都是可预知和可实现的

具体实现

Stride Scheduling 需要用到proc_struct中的几个成员变量，在alloc_proc中再添加初始化部分如下：

proc->lab6_run_pool.parent = proc->lab6_run_pool.left = proc->lab6_run_pool.right = NULL;
proc->lab6_priority = 0;//优先级
proc->lab6_stride = 0;//步进值

Stride Scheduling的具体实现在alloc_proc中。

首先定义BIG_STRIDE的值为0x7FFFFFFF,即32位有符号整数中最大的整数的表示形式。步进值定义为 P.pass =BigStride/P.priority ， 其中 P.priority 表示进程的优先权（大于 1），而 BigStride 表示一个预先定义的大常数，则该调度方案为每个进程分配的时间将与其优先级成正比。STRIDE_MAX-STRIDE_MIN<=BIG_STRIDE，为了使溢出次数尽可能少，同时保证对于任意两个Stride差值在32位有符号整数的表示范围内，将BIGSTRIDE取为32位有符号整数中的最大值，。

stride值在累加过程中很可能会溢出，为了避免溢出导致比较失败，stride scheduling采取无符号数来解决此问题。piazza上相关的讨论摘录如下：

设置无符号整数ab作为两个stride
假设开始的时候a=b，之后b先增加。如果b没有溢出，此时a-b<0，之后应该轮到a增加，此时是成功的。

如果b溢出，首先看到schedule/default_sched.c中有一句 #define BIG_STRIDE 0x7FFFFFFF，因为stride每次的增量都是 BIG_STRIDE / priority，所以stride每次最大的增量不会超过BIG_STRIDE 。

在加上步进值以后b溢出了，那么b之前必然大于0x7FFFFFFF,和一个小于0x7FFFFFFF的数相加才会溢出。在b溢出之后，无符号表示中，a仍为原来的值，而b会小于0x7FFFFFFF。a-b无符号大于0x7FFFFFFF（因为b的步进值小于0x7FFFFFFF），也就是有符号小于0，仍然是成功的。

所以问题的关键就在于#define BIG_STRIDE 0x7FFFFFFF
这个值必须是有符号整数的最大值，这个是保证stride不会出错的原因
举个例子，把BIG_STRIDE增大，BIG_STRIDE=0xE0000000
那么初始令a=b=0xE0000000，b先前进0xE0000000，b变为0xC0000000​，此时就有a-b>0，stride算法就错了。

有效的BIG_STRIDE取值范围

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

1. B+S不溢出则需$0$<A<B+S<2^ 31​,比较粗略的范围，即0<S<​2^31
2. 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

【约定】

• 根据课上向老师的思路，我们可以将4字节的int简化为1字节来讨论。
• 考虑有A、B两个进程，其stride值分别记作unsigned a,b。
• 增量步长pass记作s。
• stride值溢出，指的是无符号数的溢出，即a >= 256。
• “无符号数的有符号比较”这一技巧，下面简称“技巧”。它指的是(signed)(a-b)。

【已知结论】

• 结论1：“stride值不溢出且a,b相差不超过127时，技巧是合理的。”

• 结论2：“若进程A的stride值溢出，则应转而执行进程B。”

• 结论3：“s<=255。”

说明如下——

结论1：若a=1, b=2，则显然signed(a-b) = -1<0合理；

若a=1, b=200，则signed(a-b) = signed(-199) = 57>0不合理；

若a=127, b=255，则signed(a-b) = signed(-128) = -128<0合理；

若a=255, b=127，则signed(a-b) = signed(128) = -128<0不合理。

故a, b至多相差127。

结论2：这是合理的做法。

结论3：否则，若s=256，则有a+s = a，进程A将永远进行下去，不合理。

【stride值溢出时的情况分析】

根据结论2，我们的“技巧”应保证：

对于至多相差127的任意a, b，若①signed(a-b) <= 0（说明当前A在运行），且②a + s >= 256（A的stride溢出），则有signed(a + s - b) > 0（则应转为B来运行）。

假设a<=127，则由于结论3，溢出后的a + s < a，signed(a-b) < 0，不满足要求。

故128 <= a <= b <= 255。

假设128 <= s <= 255，由于我们需要对任意满足条件的a, b都成立，故不妨取a = 255，b = 255，则signed(a + s - b) = signed(s) < 0，不满足要求。

故s <= 127。

因此，若进程A发生stride值溢出，则增加s之前的情形为，128 <= a <= b <= 255。

当步长s <= 127时，可以使得在溢出后，“技巧”仍能保证算法的正确性。

【最终结论：最大步长限制】

结合结论1，我们得到了如下结论：

当（任意进程的）步长s <= 127时，“技巧”可以保证算法的正确性。（无论是否发生stride值溢出。）

#define BIG_STRIDE    0x7FFFFFFF

具体比较函数实现如下：

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 void
stride_init(struct run_queue *rq) {
     list_init(&(rq->run_list));//run_list供list操作使用
     rq->lab6_run_pool = NULL;//run_pool供skew_heap操作使用
     rq->proc_num = 0;
}

static void
stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
#if USE_SKEW_HEAP
     rq->lab6_run_pool =
          skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
#else
     assert(list_empty(&(proc->run_link)));//确保不在run_list中
     list_add_before(&(rq->run_list), &(proc->run_link));
#endif
     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) {
#if USE_SKEW_HEAP
     rq->lab6_run_pool =
          skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
#else
     assert(!list_empty(&(proc->run_link)) && proc->rq == rq);
     list_del_init(&(proc->run_link));
#endif
     rq->proc_num --;
}

static struct proc_struct *
stride_pick_next(struct run_queue *rq) {
#if USE_SKEW_HEAP
     if (rq->lab6_run_pool == NULL) return NULL;
     struct proc_struct *p = le2proc(rq->lab6_run_pool, lab6_run_pool);
     //堆顶即为stride最小的进程
#else
     list_entry_t *le = list_next(&(rq->run_list));
     if (le == &rq->run_list)
          return NULL;
     
     struct proc_struct *p = le2proc(le, run_link);
     le = list_next(le);
     while (le != &rq->run_list)
     {
          struct proc_struct *q = le2proc(le, run_link);
          if ((int32_t)(p->lab6_stride - q->lab6_stride) > 0)
               p = q;
          le = list_next(le);
     }
#endif
     if (p->lab6_priority == 0)
          p->lab6_stride += BIG_STRIDE;
     else p->lab6_stride += BIG_STRIDE / p->lab6_priority;
     return p;
}

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