uCoreOS lab6 实验报告

实验目的

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

实验内容

查看lab6相关的代码

练习0：填写已有实验

本实验依赖实验1/2/3/4/5。请把你做的实验2/3/4/5的代码填入本实验中代码中有“LAB1”/“LAB2”/“LAB3”/“LAB4”“LAB5”的注释相应部分。并确保编译通过。注意：为了能够正确执行lab6的测试应用程序，可能需对已完成的实验1/2/3/4/5的代码进行进一步改进。

要修改的文件有proc.c default_pmm.c pmm.c swap_fifo.c vmm.c trap.c kdebug.c

另外，有部分需要在原代码基础上修改

proc.c
static struct proc_struct *
alloc_proc(void) {
    ...
     //LAB6 YOUR CODE : (update LAB5 steps)
    /*
     * below fields(add in LAB6) in proc_struct need to be initialized
     *     struct run_queue *rq;                       // running queue contains Process
     *     list_entry_t run_link;                      // the entry linked in run queue
     *     int time_slice;                             // time slice for occupying the CPU
     *     skew_heap_entry_t lab6_run_pool;            // FOR LAB6 ONLY: the entry in the run pool
     *     uint32_t lab6_stride;                       // FOR LAB6 ONLY: the current stride of the process
     *     uint32_t lab6_priority;                     // FOR LAB6 ONLY: the priority of process, set by lab6_set_priority(uint32_t)
     */        
    proc->rq = NULL;//置运行队列为空
    //该进程的调度链表结构，该结构内部的链接组成了运行队列列表
    list_init(&(proc->run_link));//初始化运行队列的指针
    //该进程剩余的时间片，只对当前进程有效
    proc->time_slice = 0;//初始化时间片
    //该进程在优先队列中的节点，仅在lab6中使用
    proc->lab6_run_pool.left = proc->lab6_run_pool.right = proc->lab6_run_pool.parent = NULL; //初始化各类指针为空
    //该进程的调度步进值，仅在lab6中使用
    proc->lab6_stride = 0;//初始化当前运行步数
    //该进程的调度优先级，仅在lab6中使用
    proc->lab6_priority = 0;//初始化优先级
    ...
}

trap.c
static void
trap_dispatch(struct trapframe *tf) {
    ...
    case IRQ_OFFSET + IRQ_TIMER:    
         ...
		ticks++;
-		//if(ticks%TICK_NUM == 0){//每次时钟中断之后ticks就会加一 当加到TICK_NUM次数时 打印并重新开始
-		//	//print_ticks();//前面有定义 打印字符串
-		//	assert(current != NULL);
-		//	current->need_resched = 1;
-		//}
        /* LAB6 YOUR CODE */
        /* IMPORTANT FUNCTIONS:
	     * run_timer_list
	     *----------------------
	     * you should update your lab5 code (just add ONE or TWO lines of code):
         *    Every tick, you should update the system time, iterate the timers, and trigger the timers which are end to call scheduler.
         *    You can use one funcitons to finish all these things.
         */
		// 在时钟中断下 添加以下几行 并去掉之前设置 进程需要调度标记
    	// 这个标记现在已经被 调度程序所使用了 不再需要自己控制
+        assert(current != NULL);
+        run_timer_list(); //更新定时器 并根据参数调用调度算法
         break;
    ...
}

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

完成练习0后，建议大家比较一下（可用kdiff3等文件比较软件）个人完成的lab5和练习0完成后的刚修改的lab6之间的区别，分析了解lab6采用RR调度算法后的执行过程。执行make grade，大部分测试用例应该通过。但执行priority.c应该过不去。

请在实验报告中完成：

• 请理解并分析sched_class中各个函数指针的用法，并结合Round Robin 调度算法描ucore的调度执行过程
• 请在实验报告中简要说明如何设计实现“多级反馈队列调度算法”，给出概要设计，鼓励给出详细设计

实验过程

执行make grade

执行priority.c失败

回答问题

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

sched.h
// The introduction of scheduling classes is borrrowed from Linux, and makes the 
// core scheduler quite extensible. These classes (the scheduler modules) encapsulate 
// the scheduling policies. 
struct sched_class {
    // the name of sched_class
    const char *name;
    // Init the run queue
    void (*init)(struct run_queue *rq);
    // put the proc into runqueue, and this function must be called with rq_lock
    void (*enqueue)(struct run_queue *rq, struct proc_struct *proc);
    // get the proc out runqueue, and this function must be called with rq_lock
    void (*dequeue)(struct run_queue *rq, struct proc_struct *proc);
    // choose the next runnable task
    struct proc_struct *(*pick_next)(struct run_queue *rq);
    // dealer of the time-tick
    void (*proc_tick)(struct run_queue *rq, struct proc_struct *proc);
    /* for SMP support in the future
     *  load_balance
     *     void (*load_balance)(struct rq* rq);
     *  get some proc from this rq, used in load_balance,
     *  return value is the num of gotten proc
     *  int (*get_proc)(struct rq* rq, struct proc* procs_moved[]);
     */
};

• init 函数指针用于初始化调度器
• enqueue 函数指针用于将一个进程放入调度队列中
• dequeue 函数指针用于将一个进程从调度队列中出队
• pick_next 函数指针用于从调度队列中根据算法选出下一个要被运行的进程
• proc_tick 函数指针用于系统时钟中断时通知调度器

查看default_sched.c

使用RR调度算法

时间片轮转法（Round-Robin，RR）主要用于分时系统中的进程调度。为了实现轮转调度，系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。时间片是一个小的时间单位，通常为10~100ms数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复。

default_sched.c
#include <defs.h>
#include <list.h>
#include <proc.h>
#include <assert.h>
#include <default_sched.h>
// 初始化算法所需要的数据结构
static void
RR_init(struct run_queue *rq) {
    list_init(&(rq->run_list));
    rq->proc_num = 0;
}
/* 进程入队 将进程加入就绪队列(不同的就绪队列的时间片不同 也就是说有不同优先级的就绪队列)
 在 RR调度中 
 当进程时间片为0 或 应某种情况被阻塞 则将其加入到就绪队列 并将其 时间片进行重置 */
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 ++;
}
// 进程出队 将进程从就绪队列中删去
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调度中 直接按照就绪队列的顺序轮询FCFS
    */
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调度中 每次调用都会减少当前进程时间片
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;//直到 剩余时间片 为 0 当前进程的 need_resched 被置1 意为 需要被调度
    }
}

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

./default_sched.h:extern struct sched_class default_sched_class;

sched.c
#include <list.h>
#include <sync.h>
#include <proc.h>
#include <sched.h>
#include <stdio.h>
#include <assert.h>
#include <default_sched.h>

// the list of timer
static list_entry_t timer_list;

static struct sched_class *sched_class;

static struct run_queue *rq;

static inline void
sched_class_enqueue(struct proc_struct *proc) {//入队列
    if (proc != idleproc) {
        sched_class->enqueue(rq, proc);
    }
}

static inline void
sched_class_dequeue(struct proc_struct *proc) {//出队列
    sched_class->dequeue(rq, proc);
}

static inline struct proc_struct *
sched_class_pick_next(void) {//选择下一个要执行的进程时间片
    return sched_class->pick_next(rq);
}

static void
sched_class_proc_tick(struct proc_struct *proc) {//进程运行
    if (proc != idleproc) {
        sched_class->proc_tick(rq, proc);
    }
    else {
        proc->need_resched = 1;//当前进程置1 需要被调度（0号进程被调度 不断遍历线程池 直达找到一个RUNNABLE状态的进程 调用进程切换来执行它)
    }
}

static struct run_queue __rq;

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

void
wakeup_proc(struct proc_struct *proc) {//唤醒进程
    assert(proc->state != PROC_ZOMBIE);
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        if (proc->state != PROC_RUNNABLE) {
            proc->state = PROC_RUNNABLE;
            proc->wait_state = 0;
            if (proc != current) {
                sched_class_enqueue(proc);
            }
        }
        else {
            warn("wakeup runnable process.\n");
        }
    }
    local_intr_restore(intr_flag);
}
//实现调度算法部分是一个原子操作
void
schedule(void) {//调度函数
    bool intr_flag;//定义中断变量
    struct proc_struct *next;//下一进程
    local_intr_save(intr_flag);//中断禁止函数
    {
        current->need_resched = 0;//设置当前进程不需要调度
        if (current->state == PROC_RUNNABLE) {//就绪态入队
            sched_class_enqueue(current);
        }
        if ((next = sched_class_pick_next()) != NULL) {//如果队列非空则出队调度该进程
            sched_class_dequeue(next);
        }
        if (next == NULL) {
            next = idleproc;//未找到可以调度的进程 运行dileproc继续等待新进程
        }
        next->runs ++;//运行次数加一
        if (next != current) {
            proc_run(next);//运行新进程,调用proc_run函数
        }
    }
    local_intr_restore(intr_flag);//允许中断
}

// add timer to timer_list
void
add_timer(timer_t *timer) {//往定时器列表添加计时器
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        assert(timer->expires > 0 && timer->proc != NULL);
        assert(list_empty(&(timer->timer_link)));
        list_entry_t *le = list_next(&timer_list);
        while (le != &timer_list) {
            timer_t *next = le2timer(le, timer_link);
            if (timer->expires < next->expires) {
                next->expires -= timer->expires;
                break;
            }
            timer->expires -= next->expires;
            le = list_next(le);
        }
        list_add_before(le, &(timer->timer_link));
    }
    local_intr_restore(intr_flag);
}

// del timer from timer_list
void
del_timer(timer_t *timer) {//删除定时器
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        if (!list_empty(&(timer->timer_link))) {
            if (timer->expires != 0) {
                list_entry_t *le = list_next(&(timer->timer_link));
                if (le != &timer_list) {
                    timer_t *next = le2timer(le, timer_link);
                    next->expires += timer->expires;
                }
            }
            list_del_init(&(timer->timer_link));
        }
    }
    local_intr_restore(intr_flag);
}

// call scheduler to update tick related info, and check the timer is expired? If expired, then wakup proc
void
run_timer_list(void) {//用循环实现计时器
    bool intr_flag;
    local_intr_save(intr_flag);
    {
        list_entry_t *le = list_next(&timer_list);
        if (le != &timer_list) {
            timer_t *timer = le2timer(le, timer_link);
            assert(timer->expires != 0);
            timer->expires --;
            while (timer->expires == 0) {
                le = list_next(le);
                struct proc_struct *proc = timer->proc;
                if (proc->wait_state != 0) {
                    assert(proc->wait_state & WT_INTERRUPTED);
                }
                else {
                    warn("process %d's wait_state == 0.\n", proc->pid);
                }
                wakeup_proc(proc);
                del_timer(timer);
                if (le == &timer_list) {
                    break;
                }
                timer = le2timer(le, timer_link);
            }
        }
        sched_class_proc_tick(current);
    }
    local_intr_restore(intr_flag);
}

• 设置当前进程剩余时间片
• 每次时钟中断 都将当前进程剩余时间片 -1
• 直到 剩余时间片 为 0 当前进程的 need_resched 被置1 意为 需要被调度
• 中断服务进程 一发现当前进程需要被调度 就 调用 schedule() 将它调度
• 会将当前进程 放入就绪队列中 并将其时间片设为当前队列的最大时间片
• 接着调用 pick_next() 选择下一个需要换上处理机的进程 若选择成功 就让其 出就绪队列
• 若查找不到 则 内核线程 idle() 运行 该进程会死循环 不断查找可被调度的进程
• 最后调用 proc_run() 进行进程切换实现新进程的运行

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

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

其与RR调度算法的区别的是对各进程的时间片大小进行了有规定过的量化

算法思想：

1. 时间片大小随优先级级别增加而增加
2. 进程在当前时间片没有完成 则降到下一优先级
3. I/O密集型在高优先级 CPU密集型在低优先级

算法说明

例如，一个多级反馈队列的调度程序有三个队列，从 0 到 2。调度程序首先执行队列 0 内的所有进程。只有当队列 0 为空时，它才能执行队列 1 内的进程。类似地，只有队列 0 和 1 都为空时，队列 2 的进程才能执行。到达队列 1 的进程会抢占队列 2 的进程。同样，到达队列 0 的进程会抢占队列 1 的进程。

每个进程在进入就绪队列后，就被添加到队列 0 内。队列 0 内的每个进程都有 8ms 的时间片。如果一个进程不能在这一时间片内完成，那么它就被移到队列 1 的尾部。如果队列 0 为空，队列 1 头部的进程会得到一个 16ms 的时间片。如果它不能完成，那么将被抢占，并添加到队列 2。只有当队列 0 和 1 为空时，队列 2 内的进程才可根据 FCFS 来运行。

这种调度算法将给那些 CPU 执行不超过 8ms 的进程最高优先级。这类进程可以很快得到 CPU，完成 CPU 执行，并且处理下个 I/O 执行。

所需超过 8ms 但不超过 24ms 的进程也会很快得以服务，但是它们的优先级要低一点。长进程会自动沉入队列 2，队列 0 和 1 不用的 CPU 周期按 FCFS 顺序来服务。

算法实现：

• init
  初始化算法维护的数据结构

• enqueue
  （所有进程一开始都进入高优先级队列）
  如果当前进程的时间片计时器值为0(意味着该进程要么不能在相应时间片里运行结束，要么是新来的进程)

  ​ 如果是新进程，将其入队到最高优先级队列，设置时间片为该优先级的最大值

  ​ 否则将其从当前优先级队列复制入队到更低优先级队列，再将其从原队列dequeue，并且将当前时间片计数器值设置为原队列最大时间片大小的2倍，（等待下一次的调度）

• dequeue
  从相应优先级的队列中删去该进程

• pick_next
  从最高优先级队列中开始查找进程，若无则往更低的优先级队列继续查找，直到找到可运行的进程，并将其换上处理机去运行

• proc_tick
  时钟中断所使用 每次时钟中断 减少当前进程的时间片 若为0 则 将进程标记为需要调度 调用enqueue进行从新调度

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

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

后面的实验文档部分给出了Stride调度算法的大体描述。这里给出Stride调度算法的一些相关的资料（目前网上中文的资料比较欠缺）。

• strid-shed paper location1
• strid-shed paper location2
• 也可GOOGLE “Stride Scheduling” 来查找相关资料

执行：make grade。如果所显示的应用程序检测都输出ok，则基本正确。如果只是priority.c过不去，可执行 make run-priority 命令来单独调试它。大致执行结果可看附录。（ 使用的是 qemu-1.0.1 ）。

请在实验报告中简要说明你的设计实现过程。

使用斜堆数据结构

实验过程

首先，根据的要求覆盖掉Round Robin调度算法。 覆盖掉之后需要在该框架上实现Stride Scheduling调度算法。

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

由于算法涉及到每次取出当前stride最小的进程，用优先队列(斜堆)存放各进程的stride，降低算法时间复杂度。

**斜堆数据结构 **:

libs/skew_heap.h

#ifndef __LIBS_SKEW_HEAP_H__
#define __LIBS_SKEW_HEAP_H__

struct skew_heap_entry {
     struct skew_heap_entry *parent, *left, *right;
};

typedef struct skew_heap_entry skew_heap_entry_t;

typedef int(*compare_f)(void *a, void *b);

static inline void skew_heap_init(skew_heap_entry_t *a) __attribute__((always_inline));
static inline skew_heap_entry_t *skew_heap_merge(
     skew_heap_entry_t *a, skew_heap_entry_t *b,
     compare_f comp);
static inline skew_heap_entry_t *skew_heap_insert(
     skew_heap_entry_t *a, skew_heap_entry_t *b,
     compare_f comp) __attribute__((always_inline));
static inline skew_heap_entry_t *skew_heap_remove(
     skew_heap_entry_t *a, skew_heap_entry_t *b,
     compare_f comp) __attribute__((always_inline));

static inline void
skew_heap_init(skew_heap_entry_t *a)
{
     a->left = a->right = a->parent = NULL;//初始化根节点
}

static inline skew_heap_entry_t *
skew_heap_merge(skew_heap_entry_t *a, skew_heap_entry_t *b,
                compare_f comp)
{//合并两个斜堆
     if (a == NULL) return b;
     else if (b == NULL) return a;
     
     skew_heap_entry_t *l, *r;
     if (comp(a, b) == -1)
     {
          r = a->left;
          l = skew_heap_merge(a->right, b, comp);
          
          a->left = l;
          a->right = r;
          if (l) l->parent = a;

          return a;
     }
     else
     {
          r = b->left;
          l = skew_heap_merge(a, b->right, comp);
          
          b->left = l;
          b->right = r;
          if (l) l->parent = b;

          return b;
     }
}

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);
     return skew_heap_merge(a, b, comp);
}

static inline skew_heap_entry_t *
skew_heap_remove(skew_heap_entry_t *a, skew_heap_entry_t *b,
                 compare_f comp)
{
     skew_heap_entry_t *p   = b->parent;
     skew_heap_entry_t *rep = skew_heap_merge(b->left, b->right, comp);
     if (rep) rep->parent = p;
     
     if (p)
     {
          if (p->left == b)
               p->left = rep;
          else p->right = rep;
          return a;
     }
     else return rep;
}

#endif    /* !__LIBS_SKEW_HEAP_H__ */

对default_sched_stride_c文件进行修改，依照default_sched.c对各函数进行仿写补充

proc_stride_comp_f函数

#include <defs.h>
#include <list.h>
#include <proc.h>
#include <assert.h>
#include <default_sched.h>

#define USE_SKEW_HEAP 1

/* You should define the BigStride constant here*/
/* LAB6: YOUR CODE */
#define BIG_STRIDE    0x3f3f3f3f  /* you should give a value, and is ??? */ /* 定义一个大整数处以优先级 */

/* The compare function for two skew_heap_node_t's and the
 * corresponding procs*/
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_init函数

首先初始化调度器类的信息，初始化运行队列为一个空的容器结构，然后设置当前运行队列内进程数目为0

/*
 * stride_init initializes the run-queue rq with correct assignment for
 * member variables, including:
 *
 *   - run_list: should be a empty list after initialization.
 *   - lab6_run_pool: NULL
 *   - proc_num: 0
 *   - max_time_slice: no need here, the variable would be assigned by the caller.
 *
 * hint: see libs/list.h for routines of the list structures.
 */
static void
stride_init(struct run_queue *rq) {
     /* LAB6: YOUR CODE 
      * (1) init the ready process list: rq->run_list
      * (2) init the run pool: rq->lab6_run_pool
      * (3) set number of process: rq->proc_num to 0       
      */
      //与RR算法差异，增加容器元素
      list_init(&(rq->run_list));//初始化调度器类的信息
      rq->lab6_run_pool = NULL;//初始化当前的运行队列为一个空的容器结构
      rq->proc_num = 0;//设置rq->proc_num为 0  
}

stride_enqueue函数

初始化刚进入运行队列的进程proc的stride属性。 比较队头元素(队头即为最小堆的最小值元素)与当前进程的步数大小，选择步数最小的运行，将proc插入放入运行队列中去（注意：这里并不要求放置在队列头部）。 最后初始化时间片，然后将运行队列进程数目加一。

/*
 * stride_enqueue inserts the process ``proc'' into the run-queue
 * ``rq''. The procedure should verify/initialize the relevant members
 * of ``proc'', and then put the ``lab6_run_pool'' node into the
 * queue(since we use priority queue here). The procedure should also
 * update the meta date in ``rq'' structure.
 *
 * proc->time_slice denotes the time slices allocation for the
 * process, which should set to rq->max_time_slice.
 * 
 * hint: see libs/skew_heap.h for routines of the priority
 * queue structures.
 */
static void
stride_enqueue(struct run_queue *rq, struct proc_struct *proc) {
     /* LAB6: YOUR CODE 
      * (1) insert the proc into rq correctly
      * NOTICE: you can use skew_heap or list. Important functions
      *         skew_heap_insert: insert a entry into skew_heap
      *         list_add_before: insert  a entry into the last of list   
      * (2) recalculate proc->time_slice
      * (3) set proc->rq pointer to rq
      * (4) increase rq->proc_num
      */ 
#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函数

从运行队列中删除相应的元素,完成将一个进程从队列中移除的功能,使用优先队列。最后运行队列数目减一。

/*
 * stride_dequeue removes the process ``proc'' from the run-queue
 * ``rq'', the operation would be finished by the skew_heap_remove
 * operations. Remember to update the ``rq'' structure.
 *
 * hint: see libs/skew_heap.h for routines of the priority
 * queue structures.
 */
static void
stride_dequeue(struct run_queue *rq, struct proc_struct *proc) {
     /* LAB6: YOUR CODE 
      * (1) remove the proc from rq correctly
      * NOTICE: you can use skew_heap or list. Important functions
      *         skew_heap_remove: remove a entry from skew_heap
      *         list_del_init: remove a entry from the  list
      */
#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值，即pass = BIG_STRIDE / P->priority; P->stride += pass。将步长设置为优先级的倒数，如果为0则设置为最大的步长。

/*
 * stride_pick_next pick the element from the ``run-queue'', with the
 * minimum value of stride, and returns the corresponding process
 * pointer. The process pointer would be calculated by macro le2proc,
 * see kern/process/proc.h for definition. Return NULL if
 * there is no process in the queue.
 *
 * When one proc structure is selected, remember to update the stride
 * property of the proc. (stride += BIG_STRIDE / priority)
 *
 * hint: see libs/skew_heap.h for routines of the priority
 * queue structures.
 */
static struct proc_struct *
stride_pick_next(struct run_queue *rq) {
     /* LAB6: YOUR CODE 
      * (1) get a  proc_struct pointer p  with the minimum value of stride
             (1.1) If using skew_heap, we can use le2proc get the p from rq->lab6_run_poll
             (1.2) If using list, we have to search list to find the p with minimum stride value
      * (2) update p;s stride value: p->lab6_stride
      * (3) return p
      */
#if USE_SKEW_HEAP  
    if (rq->lab6_run_pool == NULL) {
        return NULL;  
    }
    //找到相应指针指向rq->lab6_run_pool
    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) { //优先级设置
        //步长为0则设置为最大步长保持相减的有效性 
        p->lab6_stride += BIG_STRIDE;
    }    
    else {//步长设置为优先级的倒数  
        p->lab6_stride += BIG_STRIDE / p->lab6_priority;
    }
    return p;  
}

stride_proc_tick函数

检测当前进程是否已用完分配的时间片。如果时间片用完，应该正确设置进程结构的相关标记来引起进程切换。 一个进程最多可以连续运行 rq.max_time_slice个时间片。 具体思想同RR算法思想，该部分代码和RR算法完全相同

/*
 * stride_proc_tick works with the tick event of current process. You
 * should check whether the time slices for current process is 
 * exhausted and update the proc struct ``proc''. proc->time_slice
 * denotes the time slices left for current
 * process. proc->need_resched is the flag variable for process
 * switching.
 */
static void
stride_proc_tick(struct run_queue *rq, struct proc_struct *proc) {
     /* LAB6: YOUR CODE */
    if (proc->time_slice > 0) {  
        proc->time_slice --;  
    }  
    if (proc->time_slice == 0) {//时间片为0说明需要被重新分配调度
        proc->need_resched = 1;  
    }  
}

stride_sched_class

定义一个c语言类的实现，提供调度算法的切换接口，这里将原来的default_sched_class改为stride_sched_class

struct sched_class stride_sched_class = {
     .name = "stride_scheduler",
     .init = stride_init,
     .enqueue = stride_enqueue,
     .dequeue = stride_dequeue,
     .pick_next = stride_pick_next,
     .proc_tick = stride_proc_tick,
};

替换调用接口

cp default_sched_stride_c default_sched_stride.c

default_sched.h
#ifndef __KERN_SCHEDULE_SCHED_RR_H__
#define __KERN_SCHEDULE_SCHED_RR_H__

#include <sched.h>

//extern struct sched_class default_sched_class;
extern struct sched_class stride_sched_class;
#endif /* !__KERN_SCHEDULE_SCHED_RR_H__ */

sched.c
void
sched_init(void) {
    list_init(&timer_list);

    //sched_class = &default_sched_class;
    sched_class = &stride_sched_class;

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

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

测试代码

make run-priority

make grade

测试通过

如果测验未能通过，问题可能出现在MAX_TIME_SLICE上，这个MAX_TIME_SLICE的值有时候能通过priority测验，有时候却不行，如果不行的话，可以将sched.h的MAX_TIME_SLICE的值进行调节（例如把20改成5）看是否能通过测验。

实验总结

​ 本次实验的主要知识点在于对处理机调度算法的掌握和理解，这次试验我了解了时间中断的具体实现方法，即是用计数器循环减一来实现的。通过此次实验我了解了Round Robin调度算法 和 Stride Scheduling 调度算法的具体实现方法，对课上的知识有了更深的理解和掌握。