练习0：填写已有实验

代码迁移与修改

与lab5类似，lab6除了需要把之前实验的代码迁移过来之外，也要在上一个实验的基础上进行一些修改。

首先，进程控制块中又增加了新内容：

static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
        // 略...
        proc->rq = NULL;                 // running queue contains Process
        list_init(&proc->run_link);      // the entry linked in run queue
        proc->time_slice = 0;            // time slice for occupying the CPU

        skew_heap_init(&proc->lab6_run_pool);    // FOR LAB6 ONLY: the entry in the run pool
        proc->lab6_stride = 0;                   // FOR LAB6 ONLY: the current stride of the process
        proc->lab6_priority = 0;                 // FOR LAB6 ONLY: the priority of process, set by lab6_set_priority(uint32_t)
    }
    return proc;
}

此外，从lab6开始操作系统对CPU时钟中断的响应处理，完全交由调度器接口完成：

static void
trap_dispatch(struct trapframe *tf) {
    // 略...
    switch (tf->tf_trapno) {
        // 略...
        case IRQ_OFFSET + IRQ_TIMER:
            ++ticks;
            assert(current != NULL);
            sched_class_proc_tick(current);
            break;
        // 略...
    }
}

这里用到了sched_class_proc_tick函数，但在kern/schedule/sched.c中该函数被定义为一个静态函数。我们需要去掉它的static关键字，否则编译会通不过！

修复uCore中cprintf的bug

uCore官方实现的提供给用户程序使用的cprintf函数实现是非原子的。这会导致什么问题呢？

举个例子，假设有两个进程A和B，如果进程A想打印字符串"Hello World"，进程B想打印字符串"Thanks for You"，则可能最终会在设备屏幕上输出"Hello Thanks for World"或者其他的混乱结果。这显然会影响我们正常开展本次实验，以及导致无法使用make grade对我们的代码进行评测！

这是因为uCore中用户进程每打印一个ASCII字符，都需要请求一次SYS_putc系统调用，因此虽然每次系统调用的执行是原子的，但这个用户程序在逐个打印字符的过程中仍然可能会被时钟中断，转而执行其他进程，从而导致屏幕输出结果的混乱。

这里我决定使用最简单粗暴的方式来修复这个bug——即给cprintf函数加一把大锁。

首先，由于lab6中uCore还没有实现锁机制，我们需要在内核代码中自行封装一个自旋锁。

代码如下，其中原子操作__sync_lock_test_and_set和__sync_lock_release由gcc编译器提供，我们无需关心其具体实现：

// kern/sync/my_spin_lock.h
// 这个结构体用于表示自旋锁
typedef struct {
    volatile int locked;
} spinlock_t;

void spin_lock(spinlock_t* lock);
void spin_unlock(spinlock_t* lock);

extern spinlock_t global_print_lock;

// kern/sync/my_spin_lock.c
#include <my_spin_lock.h>
#include <sched.h>

// 加锁函数
void spin_lock(spinlock_t *lock) {
    while (__sync_lock_test_and_set(&(lock->locked), 1)) {
        schedule();  
    }
}

// 解锁函数
void spin_unlock(spinlock_t *lock) {
    __sync_lock_release(&(lock->locked));
}

// 初始化一个全局的自旋锁
spinlock_t global_print_lock = {0}; // 全局锁初始化为未锁定状态

请你自行思考以下问题：

• 为什么不能在提供给用户程序的标准库中实现锁相关的代码？
• 在spin_lock函数中，在锁被抢占的情况下，为什么我们不能直接让当前进程通过while死循环自旋，等待时钟中断的到来以被动放弃CPU使用权，而必须让它调用schedule函数主动放弃CPU控制权？

然后，我们把加锁/解锁函数封装成系统调用，以便用户程序使用：

// libs/unistd.h
#define SYS_print_lock 100
#define SYS_print_unlock 101

// kern/syscall/syscall.c
#include <my_spin_lock.h>

static int sys_print_lock(uint32_t arg[]) {
    spin_lock(&global_print_lock);
    return 0;
}

static int sys_print_unlock(uint32_t arg[]) {
    spin_unlock(&global_print_lock);
    return 0;
}

static int (*syscalls[])(uint32_t arg[]) = {
    // ...
    [SYS_print_lock]        sys_print_lock,
    [SYS_print_unlock]      sys_print_unlock,
};

添加用户程序库中的系统调用接口：

// user/libs/syscall.h
void sys_print_lock(void);
void sys_print_unlock(void);

// user/libs/syscall.c
void sys_print_lock(void) {
    syscall(SYS_print_lock);
}

void sys_print_unlock(void) {
    syscall(SYS_print_unlock);
}

最后，修改cprintf函数的底层代码：

// user/libs/stdio.c
int vcprintf(const char *fmt, va_list ap) {
    int cnt = 0;
    sys_print_lock();  // 加锁
    vprintfmt((void*)cputch, &cnt, fmt, ap);
    sys_print_unlock();  // 解锁
    return cnt;
}

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

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

sched_class与抽象接口

从lab6开始，uCore中支撑进程调度算法需要按struct sched_class结构体所描述的规范进行函数封装，并挂载到一个名为default_sched_class的该结构体的实例上，藉此以实现进程调度算法和uCore本体代码的分离。

该结构体的定义如下：

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

lab6中uCore默认使用的该结构体实例为：

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

从这个结构体的定义中我们也能够大概猜测出来，uCore是如何将进程调度抽象成方便易用的接口的：

• uCore会将所有可供调度的进程通过一个struct run_queue结构体实例（也就是uCore官方文档中所谓的"队列"）来进行管理。
• 当新创建一个进程，或者需要暂时暂停某个进程的执行转而执行其他进程时，就通过enqueue将它放到"队列"里。
• 执行调度时，首先通过pick_next决策接下来计算机要执行哪个进程，再通过dequeue从"队列"里取出要执行的这个进程。

这里我要给"队列"打引号，是因为根据调度器算法的不同，这个管理可供调度进程的容器不一定是个queue，还可能是红黑树或者其他更复杂的数据结构。

注意区分struct run_queue容器和前两个lab中涉及的全体进程链表proc_list！

通过查看kern/schedule/sched.c中schedule函数的实现，我们可以很容易地验证我们主观猜测的正确性：

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;
        }
        next->runs ++;
        if (next != current) {
            proc_run(next);
        }
    }
    local_intr_restore(intr_flag);
}

基于Round Robin算法的uCore调度

根据已有的操作系统知识，我们不难意识到，在uCore中用户想要创建一个用户进程，最主要的方法是通过SYS_fork系统调用来实现的。这里我就从一个新进程的创建开始分析。

在do_fork中，创建完新进程后会为其调用wakeup_proc函数：

int do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    // 略...
    //    1. call alloc_proc to allocate a proc_struct
    struct proc_struct* child_proc = alloc_proc();
    // 略...
    //    6. call wakeup_proc to make the new child process RUNNABLE
    wakeup_proc(child_proc);
    // 略...
}

在wakeup_proc函数，会将这个新进程的状态标记为PROC_RUNNABLE，并且放进调度器"队列"当中去，这就为新进程被调度器调度执行创造了基本的条件：

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

进一步分析可知，在本实验中实际上操作系统会把我们的新进程给放到"队列"的队尾，并且将其的所剩时间片值拉满：

// kern/schedule/sched.c
static inline void
sched_class_enqueue(struct proc_struct *proc) {
    if (proc != idleproc) {
        sched_class->enqueue(rq, proc);
    }
}

// kern/schedule/default_sched.c
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 ++;
}

在被uCore广泛使用的循环双向链表中，将节点插入到链表头节点的前方，相当于将该节点插入到链表的末尾。这体现了循环双向链表是极端好用的。

接下来的某个时刻，当前CPU正在执行的进程current被时钟中断，sched_class_proc_tick函数会被调用。而根据前面对default_sched_class结构体的分析可知，在本次实验中，正常情况下RR_proc_tick函数又会被进一步调用。

// kern/schedule/sched.c
void sched_class_proc_tick(struct proc_struct *proc) {
    if (proc != idleproc) {
        sched_class->proc_tick(rq, proc);  // RR_proc_tick(rq, proc)
    }
    else {
        proc->need_resched = 1;
    }
}

// kern/trap/trap.c
static void trap_dispatch(struct trapframe *tf) {
    // 略...
    switch (tf->tf_trapno) {
        // 略...
        case IRQ_OFFSET + IRQ_TIMER:
            ++ticks;
            assert(current != NULL);
            sched_class_proc_tick(current);
            break;
        // 略...
    }
}

可以看到RR_proc_tick的实现非常简单：将当前进程的时间片自减；如果当前进程的时间片归零了，则将其need_resched属性值置为1，即将其标记为"让操作系统从该进程切换到其他进程执行"。

// kern/schedule/default_sched.c
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_class_proc_tick被标记为"让操作系统从该进程切换到其他进程执行"，那么等待它的结果便是要主动暂时放弃CPU的使用权，让给其他进程继续执行：

void trap(struct trapframe *tf) {
    // dispatch based on what type of trap occurred
    // used for previous projects
    if (current == NULL) {
        trap_dispatch(tf);
    }
    else {
        // keep a trapframe chain in stack
        struct trapframe *otf = current->tf;
        current->tf = tf;
    
        bool in_kernel = trap_in_kernel(tf);
    
        trap_dispatch(tf);
    
        current->tf = otf;
        if (!in_kernel) {
            if (current->flags & PF_EXITING) {
                do_exit(-E_KILLED);
            }
            if (current->need_resched) {
                schedule();
            }
        }
    }
}

接下来又进入到了我们熟悉的schedule（代码上面已经贴过了）。由于正常情况当前进程的状态理应为PROC_RUNNABLE，我们首先将它放回调度器"队列"的尾部。接下来需要挑选一个其他的进程继续执行，而挑选的逻辑非常简单，直接取"队列"中的首个进程就行（有点FIFO的味道了）：

// kern/schedule/sched.c
static inline struct proc_struct *
sched_class_pick_next(void) {
    return sched_class->pick_next(rq);
}

// kern/schedule/default_sched.c
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;
}

如果当前进程在"队列"中的下一个进程就是用户用fork新创建的那个进程的话，它就会被从"队列"中取出，并且进入proc_run函数进行真正的进程切换流程。这部分涉及x86硬件细节的操作就是前两个lab的内容了，这里不再复述。

与其他进程一样，在我们新创建的进程的时间片耗尽之后，上述的流程还会再次发生，不过这次是由我们的新进程再将CPU转让给其他进程执行了。

当我们的用户进程执行完毕后会执行SYS_exit系统调用，这在上个lab中我已经介绍过了。

int do_exit(int error_code) {
    // 略...
    current->state = PROC_ZOMBIE;
    current->exit_code = error_code;
    // 略...
    schedule();
    panic("do_exit will not return!! %d.\n", current->pid);
}

在该系统调用中，用户进程的状态会被标记为PROC_ZOMBIE，并且立即调用schedule放弃CPU的使用权。结合schedule的源码可知，由于它的状态已经不是可供调度器调度的PROC_RUNNABLE了，因此它作为僵尸进程不会被放入调度器"队列"中，也就再也不可能被调度器调度了，只有静静地等待被父进程回收PCB块彻底销号。

实现 Stride Scheduling 调度算法