Lab6 report

练习0：填写已有实验

用meld对比修改了以下文件：

kdebug.c
trap.c
default_pmm.c
pmm.c
swap_fifo.c
vmm.c
proc.c

其中需要对trap.c和proc.c中以前实验完成的部分做如下改动：

trap.c

trap_dispatch函数：

static void
trap_dispatch(struct trapframe *tf) {
    ......
    //if (ticks % TICK_NUM == 0) {
        //print_ticks();
                assert(current != NULL);
                //current->need_resched = 1;//主要是将时间片设置为需要调度
    //}
    ......
}

proc.c

alloc_proc()函数：

static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
        ......
        proc->rq = NULL; //初始化运行队列为空
        list_init(&(proc->run_link)); //初始化运行队列的指针
        proc->time_slice = 0; //初始化时间片
        proc->lab6_run_pool.left = proc->lab6_run_pool.right = proc->lab6_run_pool.parent = NULL; //初始化各类指针为空，包括父进程等待
        proc->lab6_stride = 0; //步数初始化
        proc->lab6_priority = 0; //初始化优先级
    }
    return proc;
}

练习1: 使用 Round Robin 调度算法（不需要编码）

分析

Round Robin调度算法的调度思想是让所有 runnable 态的进程分时轮流使用 CPU 时间。Round Robin 调度器维护当前 runnable进程的有序运行队列。当前进程的时间片用完之后,调度器将当前进程放置到运行队列的尾部，再从其头部取出进程进行调度。
算法的实现在default_sched.c之中，主要分析以下函数：

RR_init()：

完成了对进程队列的初始化。

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

RR_enqueue()：

把进程的进程控制块指针放入到rq队列末尾；如果进程控制块的时间片为0，则需要把它重置为max_time_slice（这表示如果进程在当前的执行时间片已经用完，需要等到下一次有机会运行时，才能再执行一段时间）；然后rq的进程数目加1。

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_dequeue()：

把就绪进程队列rq的进程控制块指针的队列元素删除，然后使就绪进程个数的proc_num减1。

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

RR_pick_next()：

选取就绪进程队列rq中的队头队列元素，并把队列元素转换成进程控制块指针，即置为当前占用CPU的程序。

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

RR_proc_tick()：

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

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_calss中各个函数指针的用法，并接合Round Robin 调度算法描ucore的调度执行过程。

sched_calss中各个函数指针的用法：

void (*init)(struct run_queue *rq)：初始化run queue队列
void (*enqueue)(struct run_queue *rq, struct proc_struct *proc)：将当前的线程入队
void (*dequeue)(struct run_queue *rq, struct proc_struct *proc)：将proc线程出队
struct proc_struct *(*pick_next)(struct run_queue *rq)：在rq队列中选择一个符合条件的队列。
void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc)：在产生时钟中断时将proc的时间片减少，并对其进行判断是否需要调度。

ucore的调度过程：ucore通过schedule()函数进行调度，在这个函数中，当需要进行线程的切换时，他会先将当前的线程通过sched_class_enqueue()函数加入队列，然后通过sched_class_pick_next()函数选择下一个要执行的线程并将其从队列中删除。

请在实验报告中简要说明如何设计实现”多级反馈队列调度算法“，给出概要设计，鼓励给出详细设计

1. 进程在进入待调度的队列等待时，首先进入优先级最高的Q1队列等待；
2. 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程；
3. 对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成；
4. 在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业。

练习2: 实现 Stride Scheduling 调度算法（需要编码）

实验思路

根据资料可知，Stride Scheduling调度算法为：

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

实现过程

default_sched.c

定义BIG_STRIDE的值为long int的最大值。

#define BIG_STRIDE 0X7FFFFFFF

stride_init()函数：

开始初始化运行队列，并初始化当前的运行队，然后设置当前运行队列内进程数目为0。

static void
stride_init(struct run_queue *rq) {
     list_init(&(rq->run_list));
     rq->lab6_run_pool = NULL;
     rq->proc_num = 0;
}

stride_enqueue()函数：

入队函数。初始化刚进入运行队列的进程 proc 的stride属性，然后比较队头元素与当前进程的步数大小，选择步数最小的运行，即将其插入放入运行队列中去，这里并未放置在队列头部。最后初始化时间片，然后将运行队列进程数目加一。

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

stride_dequeue()函数：

出队函数stride_dequeue，即完成将一个进程从队列中移除的功能，这里使用了优先队列。最后运行队列数目减一。

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

stride_pick_next()函数：

进程的调度函数stride_pick_next，观察代码，它的核心是先扫描整个运行队列，返回其中stride值最小的对应进程，然后更新对应进程的stride值，将步长设置为优先级的倒数，如果为0则设置为最大的步长。

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

stride_proc_tick()函数：

时间片函数stride_proc_tick，主要工作是检测当前进程是否已用完分配的时间片。如果时间片用完,应该正确设置进程结构的相关标记来引起进程切换。这里和之前实现的Round Robin调度算法一样，所以不赘述。

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