操作系统实验六——调度器(详细解析)

建议配合代码看

一、实验目的

理解操作系统的调度管理机制
熟悉 ucore 的系统调度器框架，以及缺省的Round-Robin 调度算法
基于调度器框架实现一个(Stride Scheduling)调度算法来替换缺省的调度算法

二、实验任务

实验五完成了用户进程的管理，可在用户态运行多个进程。但到目前为止，采用的调度策略是很简单的FIFO调度策略。
本次实验，主要是熟悉ucore的系统调度器框架，以及基于此框架的Round-Robin（RR）调度算法。然后参考RR调度算法的实现，完成Stride Scheduling调度算法。

三、实验准备

（一）数据结构

在理解调度算法之前需要首先理解实现算法相关的数据结构；

1.调度器框架shed_class

 struct sched_class {
    // 调度器的名字
    const char *name;
    // 初始化运行队列
    void (*init) (struct run_queue *rq);
    // 将进程 p 插入队列 rq
    void (*enqueue) (struct run_queue *rq, struct proc_struct *p);
    // 将进程 p 从队列 rq 中删除
    void (*dequeue) (struct run_queue *rq, struct proc_struct *p);
    // 返回 运行队列 中下一个可执行的进程
    struct proc_struct* (*pick_next) (struct run_queue *rq);
    // timetick 处理函数
    void (*proc_tick)(struct  run_queue* rq, struct proc_struct* p);
};

ucore 已经为 RR 调度算法创建好了一个名为 RR_sched_class 的调度策略类。
为了保证调度器接口的通用性，ucore调度框架定义了以上接口，该接口中，几乎全部成员变量均为函数指针。

2. 运行队列描述run_queue

struct run_queue {
       //其运行队列的哨兵结构，可以看作是队列头和尾
        list_entry_t run_list;
        //优先队列形式的进程容器，只在 LAB6 中使用
        skew_heap_entry_t  *lab6_run_pool;
        //表示其内部的进程总数
        unsigned int proc_num;
        //每个进程一轮占用的最多时间片
        int max_time_slice;
    };

通过数据结构 struct run_queue 来描述完整的 run_queue（运行队列）。
在 ucore 框架中，运行队列存储的是当前可以调度的进程，所以，只有状态为runnable的进程才能够进入运行队列。当前正在运行的进程并不会在运行队列中。
运行队列通过链表的形式进行组织。链表的每一个节点是一个list_entry_t,每个list_entry_t 又对应到了 struct proc_struct *,这其间的转换是通过宏 le2proc 来完成的。具体来说，我们知道在 struct proc_struct 中有一个叫 run_link 的 list_entry_t，因此可以通过偏移量逆向找到对因某个 run_list的 struct proc_struct。即进程结构指针 proc = le2proc(链表节点指针, run_link)。

3. 四个调度函数

调度处理只涉及了三个关键调度相关函数：wakup_proc、shedule、run_timer_list；

①wakeup_proc函数其实完成了把一个就绪进程放入到就绪进程队列中的工作，为此还调用了一个调度类接口函数sched_class_enqueue。
②schedule函数完成了与调度框架和调度算法相关三件事情: 把当前继续占用CPU执行的运行进程放放入到就绪进程队列中；
从就绪进程队列中选择一个“合适”就绪进程；把这个“合适”的就绪进程从就绪进程队列中摘除。
通过调用三个调度类接口函数sched_class_enqueue、sched_class_pick_next、sched_class_enqueue来使得完成这三件事情与具体的调度算法无关。
③run_timer_list函数在每次timer中断处理过程中被调用，从而可用来调用调度算法所需的timer时间事件感知操作，调整相关进程的进程调度相关的属性值。通过调用调度类接口函数sched_class_proc_tick使得此操作与具体调度算法无关。

因此，我们实现调度类接口函数：

sched_class_enqueue
sched_class_dequeue
sched_class_pick_next
sched_class_proc_tick

函数的实现其实就是调用某基于sched_class数据结构的特定调度算法实现的4个指针函数。
采用这样的调度类框架后，如果我们需要实现一个新的调度算法，则我们需要定义一个针对此算法的调度类的实例，一个就绪进程队列的组织结构描述就行了，其他的事情都可交给调度类框架来完成。

（二）相关函数改进

在实验指导书的练习0中提到了注意点如下：
注意：为了能够正确执行lab6的测试应用程序，可能需对已完成的实验1/2/3/4/5的代码进行进一步改进。
根据试验要求，我们需要对部分代码进行改进，这里需要改进的地方的代码和说明如下：

①PCT 中增加了三个与 stride 调度算法相关的成员变量，以及增加了对应的初始化过程； ②新增了斜堆数据结构的实现；
③新增了默认的调度算法Round_Robin的实现，具体为调用等—系列函数之后，进—步调用调度器sched_class中封装的函数，默认该调度器为Round_Robin调度器,这是在default_sched.* 中定义的；
④新增了 set_priority，get_time 的系统调用；

因此需要进行修改的代码如下：

1. proc_struct 函数

在原来的实验基础上，新增了 9 行代码：
数据结构中添加的变量以及作用如图代码与注释所示：

int exit_code;//退出码(发送到父进程)
uint32_t wait_state;//等待状态
struct proc_struct *cptr, *yptr, *optr; //进程间的—些关系
struct run_queue *rq;	/运行队列中包含进程
list_entry_t run_link;//该进程的调度链表结构，该结构内部的连接组成了运行队列
int time_slice;//该进程剩余的时间片，只对当前进程有效
skew_heap_entry_t lab6_run_pool; //该进程在优先队列中的节点，仅在 LAB6 使用
uint32_t lab6_stride;//该进程的调度步进值，仅在 LAB6 使用
uint32_t lab6_priority;//该进程的调度优先级，仅在 LAB6 使用

2. alloc_proc()函数

在原来的实验基础上，新增了 6 行代码：

 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;//设置步长为0 
 proc->lab6_priority= 0;//设置优先级为0

在初始化进程的过程中需要考虑将该进程的运行队列指针、时间片等等与调度相关的Proc_stryct新添加的所有内容初始化。

3. trap_dispatch()函数

case IRQ_OFFSET + IRQ_TIMER:
		ticks++;
        assert(current != NULL);
        sched_class_proc_tick(current);	//调用该函数进行时间片用完的检查
break;

根据提示，这里需要将lab5的将need_resched置1更改为lab6需要进行的函数；
这里我们查看sched_class_proc_tick的作用：

 void
sched_class_proc_tick(struct proc_struct *proc) {
    if (proc != idleproc) {
        sched_class->proc_tick(rq, proc);
    }
    else {
        proc->need_resched = 1;
    }
}

这里可以看到，对于idleproc进程需要进行need_resched=1，因为它没有要处理的东西，直接调度其它进程即可，而用户进程则需要调用proc_tick;

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

而这里的proc_tick就是进行时间片的递减，如果用完时间片，那么就使该进程变成可调度状态等待再次调度；

四、实验步骤

（一）练习0:填写已有实验

lab6会依赖lab1_{lab5，我们需要把做的lab1}lab5的代码填到lab6中缺失的位置上面。练习0 就是—个工具的利用。这里我使用的是linux的Meld工具。和lab5操作流程—样，我们只需要将已经完成的lab5与待完成的lab6分别导入进来，然后点击compare即可，详细细节不再赘述。需要修改的主要是以下六个文件：proc.c、default_pmm.c、pmm.c、swap_fifo.c 、vmm.c、trap.c
练习0提到的对已做实验的改进已经在上面的准备部分完成。

（二）练习1: 使用Round Robin调度算法

分析了解lab6采用RR调度算法后的执行过程

RR调度算法的调度思想是让所有 runnable 态的进程分时轮流使用 CPU 时间。RR调度器维护当前 runnable 进程的有序运行队列。当前进程的时间片用完之后，调度器将当前进程放置到运行队列的尾部，再从其头部取出进程进行调度。
在这个理解的基础上，我们来分析算法的具体实现。

1. RR调度算法分析

这里Round Robin调度算法的主要实现在default_sched.c中，一共包含了6个主要函数（包括上面提到的调度函数）。
逐个函数的分析，从而了解RR调度算法的原理。

1.1. RR_init函数

static void RR_init(struct run_queue *rq) { //初始化进程队列
  list_init(&(rq->run_list));//初始化运行队列
  rq->proc_num = 0;//初始化进程数为 0
}

RR_init函数：这个函数被封装为 sched_init 函数，用于调度算法的初始化，使用grep命令可以知道，该函数仅在 ucore 入口的 init.c 里面被调用进行初始化

1.2. RR_enqueue函数

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));//把进程的进程控制块指针放入到 rq 队列末尾
  //进程控制块的时间片为 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 ++;//就绪进程数加—
}

RR_enqueue函数：
该函数的功能为将指定的进程的状态置成 RUNNABLE，并且放入调用算法中的可执行队列中，被封装成 sched_class_enqueue 函数，可以发现这个函数仅在 wakeup_proc 和schedule 函数中被调用，前者为将某个不是 RUNNABLE 的进程加入可执行队列，而后者是将正在执行的进程换出到可执行队列中去。
首先，它把进程的进程控制块指针放入到 rq 队列末尾，且如果进程控制块的时间片为 0，则需要把它重置为max_time_slice。这表示如果进程在当前的执行时间片已经用完，需要等到下—次有机会运行时，才能再执行—段时间。然后在依次调整 rq 和 rq 的进程数目加—。

1.3. RR_dequeue函数

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_dequeue 函数：该函数的功能为将某个在队列中的进程取出，其封装函数sched_class_dequeue 仅在 schedule 中被调用，表示将调度算法选择的进程从等待的可执行的进程队列中取出进行执行。
它简单的把就绪进程队列 rq 的进程控制块指针的队列元素删除，然后使就绪进程个数的proc_num减—。

1.4. RR_proc_tick函数

static void RR_proc_tick(struct run_queue *rq, struct proc_struct *proc) {// 时间片
  if (proc->time_slice > 0) {//到达时间片
    proc->time_slice --;//执行进程的时间片 time_slice 减—
  }
  if (proc->time_slice == 0) {//时间片为 0
    proc->need_resched = 1;//设置此进程成员变量 need_resched 标识为 1，进程需要调度
  }
}

RR_proc_tick 函数：该函数表示每次时钟中断的时候应当调用的调度算法的功能，仅在进行时间中断的 ISR 中调用。
它每—次时间片到时的时候，当前执行进程的时间片 time_slice 便减—。如果 time_slice 降到零，则设置此进程成员变量 need_resched 标识为 1，这样在下—次中断来后执行trap 函数时，会由千当前进程程成员变量 need_resched 标识为 1 而执行 schedule 函数，从而把当前执行进程放回就绪队列末尾，而从就绪队列头取出在就绪队列上等待时间最久的那个就绪进程执行。

1.5. RR_pick_next函数

static struct proc_struct *RR_pick_next(struct run_queue *rq) {//选择下—调度进程list_entry_t *le = list_next(&(rq->run_list));//选取就绪进程队列 rq 中的队头队列元素
  if (le != &(rq->run_list)) {//取得就绪进程
    return le2proc(le, run_link);//返回进程控制块指针
  }
  return NULL;
}

RR_pick_next 函数：该函数的封装函数同样仅在 schedule 中被调用，功能为选择要执行的下个进程
它选取就绪进程队列 rq 中的队头队列元素，并把队列元素转换成进程控制块指针，即置为当前占用 CPU 的程序。

1.6. default_sched_class

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

sched_class 定义—个 c 语言类的实现，提供调度算法的切换接口。

2. 问题分析

2.1. 请理解并分析 sched_calss 中各个函数指针的用法，并结合 Round Robin 调度算法描述 ucore 的调度执行过程;
首先我们可以查看—下 sched_class 类中的内容：

struct sched_class {
  const char *name;// 调度器的名字
  void (*init) (struct run_queue *rq);// 初始化运行队列
  void (*enqueue) (struct run_queue *rq, struct proc_struct *p);// 将进程 p 插入队列 rq
  void (*dequeue) (struct run_queue *rq, struct proc_struct *p);// 将进程 p 从队列 rq 中删除
  struct proc_struct* (*pick_next) (struct run_queue *rq);// 返回运行队列中下—个可执行的进程
  void (*proc_tick)(struct run_queue* rq, struct proc_struct* p);// timetick 处理函数
};

接下来我们结合具体算法来描述—下 ucore 调度执行过程：

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

2.2. 简要说明如何设计实现”多级反馈队列调度算法“，给出概要设计，鼓励给出详细设计;
2.2.1. 多级反馈队列调度算法思想：

①
设有N个队列（Q1,Q2…QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1)Priority(Q2) > … > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。
②
对于优先级最低的队列来说，里面是遵循时间片轮转法。也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。

2.2.2. 多级队列调度算法描述

①
进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
②
首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
③
对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
④
在最后一个队列QN中的各个进程，按照时间片轮转分配时间片调度。
⑤
在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i-1队列全部为空时，才会去执行第i队列的进程（抢占式）。特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。

2.2.3. 多级队列调度的详细设计如下：

①
在 proc_struct 中添加总共 N个多级反馈队列的入口，每个队列都有着各自的优先级，**编号越大的队列优先级约低，并且优先级越低的队列上时间片的长度越大，为其上—个优先级队列的两倍；**并且在 PCB 中记录当前进程所处的队列的优先级；
②
处理调度算法初始化的时候需要同时对 N 个队列进行初始化；
③
在处理将进程加入到就绪进程集合的时候，**观察这个进程的时间片有没有使用完，如果使用完了，就将所在队列的优先级调低，**加入到优先级低 1
级的队列中去，如果没有使用完时间片，则加入到当前优先级的队列中去；
④
在同—个优先级的队列内使用时间片轮转算法；
⑤
在选择下—个执行的进程的时候，优限考虑高优先级的队列中是否存在任务，如果不存在才转而寻找较低优先级的队列；（有可能导致饥饿)
⑥
从就绪进程集合中删除某—个进程就只需要在对应队列中删除即可；
⑦
处理时间中断的函数不需要改变；

（三）练习2: 实现Stride Scheduling调度算法

首先，根据实验指导书的要求，先用 default_sched_stride.c 覆盖 default_sched.c，即覆盖掉 Round Robin 调度算法的实现。覆盖掉之后需要在该框架上实现 Stride Scheduling 调度算法。

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

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

1. 简单分析

由于在 ucore 中使用面向对象编程的思想，将所有与调度算法相关的函数封装在了调度器sched_class 中，因此其实可以不需要覆盖掉 default_sched.c，只需要将default_shed_stride_c(不知道为什么要这样命名)改为default_shed_stride.c这样由于default_sched_stride.c 中也有 sched_class 的定义，其他代码在调用调度器的接口的时候就直接调用了新实现的 Stride Scheduling 算法实现的函数了；

2. 算法分析与实现

Stride Scheduling算法的思想已经在上面进行了简单的归纳分析了，接下来围绕ucore操作系统来分析各个函数以及实现该调度算法。

2.1. proc_stride_comp_f函数（非编程部分，但很重要）
相比于 RR 调度，Stride Scheduling 函数定义了—个比较器 proc_stride_comp_f。proc_stride_comp_f：优先队列的比较函数，主要思路就是通过步数相减，然后根据其正负比较大小关系

static int proc_stride_comp_f(void *a, void *b)
{
  struct proc_struct *p = le2proc(a, lab6_run_pool);//通过进程控制块指针取得进程a
  struct proc_struct *q = le2proc(b, lab6_run_pool);//通过进程控制块指针取得进程b
  int32_t c = p->lab6_stride - q->lab6_stride;//步数相减，通过正负比较大小关系
  if (c > 0) return 1;
  else if (c == 0) return 0; 
  else return -1;
}

2.2. stride_init函数
**stride_init：进行调度算法初始化的函数，在 stride 调度算法的实现中使用了斜堆来实现优先队列，因此需要对相应的成员变量进行初始化。**开始初始化运行队列，并初始化当前的运行队，然后设置当前运行队列内进程数目为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;//设置运行队列为空
}

2.3. stride_enqueue函数
stride_enqeue：在将指定进程加入就绪队列的时候，需要调用斜堆的插入函数将其插入到斜堆中，然后对时间片等信息进行更新。
根据之前对该调度算法的分析，这里函数主要是初始化刚进入运行队列的进程 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
. . .
  #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 ++;//维护就绪队列中进程的数量加—
}

注意点：
里面使用—个条件编译：#if USE_SKEW_HEAP，在 ucore 中 USE_SKEW_HEAP 定义为 1 ，因此 #else 与 #endif 之间的代码将会被忽略。lab6_run_pool指针，在使用优先队列的实现中表示当前优先队列的头元素，如果优先队列为空，则其指向空指针（NULL）。
其中的 skew_heap_insert 函数如下：

static inline skew_heap_entry_t *skew_heap_insert(skew_heap_entry_t *a, skew_heap_entry_t *b, compare_f comp)
{
  skew_heap_init(b); //初始化进程b
  return skew_heap_merge(a, b, comp);//返回a与b结合的结果
}

它包含了两个操作，一个是初始化进程b的斜堆结点，接着就是将a参数的斜对结点与之进行合并操作，初始化其实就是将a中的相关指针（left、right、parent）初始为NULL。

合并操作较为复杂，这里简述它的核心思想：
对于两个优先队列结点（b指的就是一个简单的结点，而a表示优先队列的头节点），这里的合并其实就是要将b结点加入到优先队列中；
如果此时b的步长小于a的步长，那么b进程将会成为新的优先队列的头节点，a将会通过parent指针连接在b上；否则b的步长较小的话，它会通过递归的方式加入到优先队列合适的位置。

（代码不需要我们实现，因此不再粘贴）

2.4. stride_dequeue
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 --;//维护就绪队列中的进程总数
}

里面的代码比较简单，只有—个主要函数：skew_heap_remove。该函数的实现就是斜堆数据结构的删除基本操作。

2.5. stride_pick_next函数
stride_pick_next: 选择下—个要执行的进程，根据stride算法，只需要选择stride值最小的进程，即斜堆的根节点对应的进程即可。
进程的选择调度函数，观察代码，它的核心是直接返回其中 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);//选择stride值最小的进程
#else
.  .  .
#endif
  if (p->lab6_priority == 0)//优先级为 0
   p->lab6_stride += BIG_STRIDE;//步长设置为最大值
  else
   p->lab6_stride += BIG_STRIDE / p->lab6_priority;
  //步长设置为优先级的倒数，更新该进程的 stride 值
  return p;
}

2.6. stride_proc_tick函数
stride_proc_tick：每次时钟中断需要调用的函数，仅在进行时间中断的ISR中调用。
时间片函数主要工作是检测当前进程是否已用完分配的时间片。如果时间片用完，应该正确设置进程结构的相关标记来引起进程切换。这里和之前实现的RR调度算法—样。

static void stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
/* LAB6: YOUR CODE */
  if (proc->time_slice > 0) {//到达时间片
    proc->time_slice --;//执行进程的时间片 time_slice 减—
  }
  if (proc->time_slice == 0) {//时间片为 0
    proc->need_resched = 1;//设置此进程成员变量 need_resched 标识为 1，进程需要调度
  }
}

2.7. sched_class接口
定义—个 c 语言类的实现，提供调度算法的切换接口。

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

3. 问题分析

3.1. 如何证明STRIDE_MAX – STRIDE_MIN <= PASS_MAX?
由于溢出的出现，进程间stride的理论比较和实际比较结果可能出现了偏差。假设PASS_MAX为当前所有进程里最大的步进值。则我们可以证明如下结论：对每次Stride调度器的调度步骤中，有其最大的步进值STRIDE_MAX和最小的步进值STRIDE_MIN之差：

STRIDE_MAX – STRIDE_MIN <= PASS_MAX；

假如该命题不成立，则可以知道就绪队列在上—次找出用来执行的进程的时候，假如选择的进程是 P，那么存在另外—个就绪的进程 P’，并且有 P’ 的 stride 比 P 严格地小，这也就说明上—次调度出了间题，这和 stride 算法的设计是相违背的；因此通过反证法证明了上述命题的成立；

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

在 ucore 中，目前Stride是采用无符号的32位整数表示。因此需要保证 BigStride <= 232-1;

Stride 调度算法的思路是每次找 stride 步进值最小的进程，每个进程每次执行完以后，都要在 stride步进 += pass步长，其中步长是和优先级成反比的因此步长可以反映出进程的优先级。但是随着每次调度，步长不断增加，有可能溢出。

因此，需要设置—个步长的最大值，使得他们哪怕溢出，还是能够进行比较。

首先因为步长和优先级成反比可以得到：
max_stride - min_stride <= pass_max
所以得出：max_stride - min_stride <= BIG_STRIDE

ucore 中 BIG_STRIDE 用的无符号 32 位整数，最大值只能为232-1，而又因为是无符号的，因此，最小只能为 0，而且我们需要把 32 位无符号整数进行比较，需要保证任意两个进程 stride 的差值在 32 位有符号数能够表示的范围之内，故 BIG_STRIDE 为（2^32
-1）/2，即下面的16进制0x7FFFFFFF；

4. 运行结果

这里出了与lab5相同的错误，相同的处理方式就是注释掉kern/process/pro.c中的：

这里的ucore出现的问题在lab5中分析过了，它就是页的回收没有实现完全，是ucore自己的一些小bug。
最终可以成功得到结果：

运行正确。

（四） Challeneg1: 实现CFS调度算法

CFS 算法的基本思路就是尽量使得每个进程的运行时间相同，所以需要记录每个进程已经运行的时间等信息。
CFS的思想就是让每个调度实体（没有组调度的情形下就是进程）的虚拟运行时间互相追赶，而每个调度实体的虚拟运行时间增加速度不同，权重越大（优先级决定）的增加的越慢，这样就能获得更多的cpu执行时间。

1. 数据结构

struct proc_struct {
...
  int CFS_run_time;  //记录已经运行的时间
  int CFS_priority;	//优先级，代表权重，权重越大则越慢
  skew_heap_entry_t CFS_run_pool;	//斜堆实现的优先队列
};

每次调度的时候，选择已经运行时间最少的进程。所以，也就需要—个数据结构来快速获得最少运行时间的进程， CFS 算法选择的是红黑对（但是实力不够实现不了，就直接使用项目中的斜堆了）。CFS对于优先级的实现方法就是让优先级低的进程的时间过得很快。

2. 算法实现

2.1. proc_CFS_comp_f比较函数
与Stride Scheduling实现类似，只是这里比较的是已运行时间

static int proc_CFS_comp_f(void *a, void *b)
{
  struct proc_struct *p = le2proc(a, CFS_run_pool); 
  struct proc_struct *q = le2proc(b, CFS_run_pool); 
  int32_t c = p->CFS_run_time - q->CFS_run_time;
  if (c > 0) return 1;
  else if (c == 0) return 0; 
  else return -1;
}

注：因为整个算法是在斜堆这样的数据结构上实现的因此它和Stride Scheduling算法的差别并不大，后面我直接将修改部分代码贴出。

2.2. enqueue、dequeue、pick_next
CFS_enqueue、CFS_dequeue两个函数的实现与Stride Scheduling算法完全一致，直接调用skew_heap_insert、skew_heap_remove即可。
CFS_pick_next同样如此，因为采用的就是斜堆数据结构，直接返回写对根节点即可。

2.3. CFS_proc_tick
更新进程时间片的函数，如下图红色部分是增加的内容；

static void
CFS_proc_tick(struct run_queue *rq, struct proc_struct *proc) { 
  if (proc->time_slice > 0) {
    proc->time_slice --;
    proc->CFS_run_time += proc->(MAX_priority/CFS_priority);
  }
  if (proc->time_slice == 0) { 
    proc->need_resched = 1;
  }
}

这里每一个时间片让进程的运行时间加上它的最大优先级/优先级（权重），这样的话，权重越大的则增加越慢。

2.4. lab6_set_priority函数

void lab6_set_priority(uint32_t priority)
{
...
  current->CFS_priority = 60 / current->lab6_priority + 1; 
  if (current->fair_priority < 1)
    current->fair_priority = 1;
    
}

主要是将 Stride Scheduling 的优先级变成到 CFS 的优先级。

注：实现基于stride的斜堆而不是应该使用的更加平衡的红黑树，因此challenge不算是真正完成了。

五、实验总结

这次试验算是比较简单，它相对于上一个实验也只是加上了一个调度器框架，可以将lab5的简单的FIFO调度策略修改为我们设计的调度策略。
收获比较大的是课本上的RR轮转调度算法在这里有一个比较详细的实现（ucore已经是实现的），通过学习基于ucore的系统调度器框架的Round-Robin对于掌握书本上的调度策略有很好的帮助；此外学习完调度器框架之后，我们自己编程实现的Stride Scheduling算法在书上只是简单的提了一下方法，而这里通过实现的方式能够很好的加深理解。
总的来说经过几次实验之后对ucore的基本的进程调度方式有了个清晰的认识。