练习0 填写已有实验

meld的软件进行对比即可

现在将需要修改的文件罗列如下：

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

根据注释的提示，主要是一下两个函数需要额外加以修改。

alloc_proc函数


完整代码如下：

static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
        proc->state = PROC_UNINIT; //设置进程初始状态
        proc->pid = -1;            //进程id=-1
        proc->runs = 0;            //初始化时间片为0
        proc->kstack = 0;          //初始化内存栈的地址为0
        proc->need_resched = 0;    //是否需要调度设为不需要
        proc->parent = NULL;       //将父节点置空
        proc->mm = NULL;           //置空虚拟内存
        memset(&(proc->context), 0, sizeof(struct context));//初始化上下文
        proc->tf = NULL;           //将中断帧指针置空
        proc->cr3 = boot_cr3;      //将页目录设内核页目录表的基址
        proc->flags = 0;           //初始化标志位
        memset(proc->name, 0, PROC_NAME_LEN);//置空进程名
        proc->wait_state = 0;      //初始化进程等待状态  
        proc->cptr=proc->yptr=proc->optr = 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;
}

相比于lab5，lab6对proc_struct结构体再次做了扩展，这里主要是多出了以下部分

    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;     //初始化优先级

trap_dispatch

函数

static void
trap_dispatch(struct trapframe *tf) {
    ......
    ......
    ticks ++;  
    assert(current != NULL);  
    run_timer_list(); //更新定时器，并根据参数调用调度算法  
    break;  
    ......
    ......
}

练习1 使用Round Robin调度算法

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

0x1 执行过程

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

0x2 算法实现

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

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

RR_enqueue的函数实现如下表所示。即把某进程的进程控制块指针放入到rq队列末尾，且如果进程控制块的时间片为0，则需要把它重置为rq成员变量max_time_slice。这表示如果进程在当前的执行时间片已经用完，需要等到下一次有机会运行时，才能再执行一段时间。

    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减一。

    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中的队头队列元素，并把队列元素转换成进程控制块指针。

    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的函数实现如下表所示。即每次timer到时后，trap函数将会间接调用此函数来把当前执行进程的时间片time_slice减一。如果time_slice降到零，则设置此进程成员变量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;  
    }  
}  

练习2 实现Stride Scheduling调度算法

首先需要换掉RR调度器的实现，即用default_sched_stride_c覆盖default_sched.c。然后根据此文件和后续文档对Stride度器的相关描述，完成Stride调度算法的实现。

首先，根据实验指导书的要求，先用default_sched_stride_c覆盖default_sched.c，即覆盖掉Round Robin调度算法的实现。

覆盖掉之后需要在该框架上实现Stride Scheduling调度算法。

关于Stride Scheduling调度算法，经过查阅资料和实验指导书，我们可以简单的把思想归结如下：

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

首先是初始化函数stride_init。

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

static void  
stride_init(struct run_queue *rq) {  
     /* LAB6: YOUR CODE */  
     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) {  
     /* LAB6: YOUR CODE */  
#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));//将 proc插入放入运行队列中去  
#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，即完成将一个进程从队列中移除的功能，这里使用了优先队列。最后运行队列数目减一。

static void  
stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {  
     /* LAB6: YOUR CODE */  
#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值最小的对应进程，然后更新对应进程的stride值，将步长设置为优先级的倒数，如果为0则设置为最大的步长。

static struct proc_struct *
stride_pick_next(struct run_queue *rq) {
     /* LAB6: YOUR CODE */
#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
    //更新对应进程的stride值
     if (p->lab6_priority == 0)//优先级设置  
          p->lab6_stride += BIG_STRIDE;//步长为0则设置为最大步长保持相减的有效性  
     else p->lab6_stride += BIG_STRIDE / p->lab6_priority;//步长设置为优先级的倒数  
     return p;  
}

函数stride_proc_tick的主要工作是检测当前进程的时间片是否已经用完。如果时间片已经用完,就会按照正确的流程进行进程的切换工作。这里和之前实现的Round Robin调度算法一样，所采用的思想也是一致的

优先队列比较函数proc_stride_comp_f的实现，主要利用思路是通过相减之后的值，进行判断大小

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法有了更多的了解，stride法其实就是轮转法的一种升级。stride法加入了对进程优先级的调整，步数越小，进程优先级越大。这种改变更加合理。进程的调度极大的提高了CPU的利用率。更加深刻的理解了进程切换的原理，对Stride Schedule算法的原理和算法可控性和确定性有了更深的认识。