从ucore来总结操作系统(6)----线程调度算法

线程调度算法

0X00 环境准备

本lab基于前所有lab，但是需要对其进行一些扩展：

lab6的proc_struct结构体发生了变化:

struct proc_struct {
    enum proc_state state;                      // Process state
    int pid;                                    // Process ID
    int runs;                                   // the running times of Proces
    uintptr_t kstack;                           // Process kernel stack
    volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
    struct proc_struct *parent;                 // the parent process
    struct mm_struct *mm;                       // Process's memory management field
    struct context context;                     // Switch here to run process
    struct trapframe *tf;                       // Trap frame for current interrupt
    uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
    uint32_t flags;                             // Process flag
    char name[PROC_NAME_LEN + 1];               // Process name
    list_entry_t list_link;                     // Process link list 
    list_entry_t hash_link;                     // Process hash list
    int exit_code;                              // exit code (be sent to parent proc)
    uint32_t wait_state;                        // waiting state
    struct proc_struct *cptr, *yptr, *optr;     // relations between processes

    /*以下为新增*/

    // 包含该线程的就绪队列(多级多列调度时，系统中存在多个就绪队列)
    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
    // lab6中支持stride算法的斜堆节点
    skew_heap_entry_t lab6_run_pool;            // FOR LAB6 ONLY: the entry in the run pool
    // lab6中支持stride算法的当前线程stride步长
    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)
};

这里说一下这里的rq和run_link

struct run_queue *rq : process_struct中的rq指针指向的是包含该线程的就绪队列，这样就可以通过该指针找到该线程所在的就绪队列，从而可以对该就绪队列进行操作。同时，全局还会包含一个或者多个rq，这些rq可能对应不同的优先级，其内部都是可运行线程组成的链表。

list_entry_t run_link : 运行队列通过链表的形式进行组织。链表的每一个节点是一个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)。

为了能够支持不同的线程调度算法，lab6中引入了就绪队列的概念。就绪队列（run_queue）是一个包含了所有就绪态线程集合的队列结构，能够在有就绪线程出现时令其高效的入队，当线程脱离就绪态时高效的将其从就绪队列中移除。

就绪队列是一个抽象的队列，其底层实现可以是双向链表，平衡二叉树或是堆等等。由于堆结构中的元素只需要满足堆序性，而不像平衡二叉树一样需要满足全局的有序性，因此其整体效率还要略高于平衡二叉树，很适合用来实现优先级队列。这也是lab6中引入斜堆skew_heap作为stride调度算法中就绪队列的底层实现的原因。

由于结构体发生改变，所以初始化函数也要改变:

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;
        proc->runs = 0;
        proc->kstack = 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);
        // Lab5 code
        proc->wait_state = 0;
        proc->cptr = proc->optr = proc->yptr = NULL;
        // Lab6 新增code
        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 = 1;
    }
    return proc;
}

由于调度时机由中断控制，所以还需要在中断函数里增加对应的调度:

case IRQ_OFFSET + IRQ_TIMER:
    ticks++;
    assert(current != NULL);
    sched_class_proc_tick(current);
    break;

0X01 Round Robin 调度算法

这就是轮询调度，在ucore中，调度器引入run-queue链表，用于存储所有的可运行(就绪)的进程。当调度发生时，会从run-queue中挑选一个进程，将其标记为运行中，并切换到对应上下文中。

RR调度算法是默认的调度算法，但在认识调度算法之前，我们得先知道什么时候会进行调度。在ucore中，以下几种情况发生时会进行调度:

函数	说明
proc.c::do_exit	用户线程结束，主动放弃CPU
proc.c::do_wait	用户线程等待子线程结束，主动放弃CPU
proc.c::init_main	1. initproc内核线程等待所有用户进程结束，如果没有结束，就主动放弃CPU控制权; 2. initproc内核线程在所有用户进程结束后，让kswapd内核线程执行10次，用于回收空闲内存资源
proc.c::cpu_idle	idleproc内核线程的工作就是等待有处于就绪态的进程或线程，如果有就调用schedule函数
sync.h::lock	在获取锁的过程中，如果无法得到锁，则主动放弃CPU控制权
trap.c::trap	如果在当前进程在用户态被打断(时钟调度)，且当前进程控制块的成员变量need_resched设置为1，则当前线程会放弃CPU控制权

为什么将need_resched设置为1就会执行调度

这是因为时间片中断发生时，trap并不是直接执行trap_dispatch，而是有所改变

/* *
 * trap - handles or dispatches an exception/interrupt. if and when trap() returns,
 * the code in kern/trap/trapentry.S restores the old CPU state saved in the
 * trapframe and then uses the iret instruction to return from the exception.
 * */
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();
            }
        }
    }
}

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

// 初始化RR调度算法的运行队列rq
static void RR_init(struct run_queue *rq)
{
    list_init(&(rq->run_list));
    rq->proc_num = 0;
}

// 将进程proc加入到RR调度算法的运行队列rq中
static void RR_enqueue(struct run_queue *rq, struct proc_struct *proc)
{
    // 因为要把proc加入到rq中，说明proc之前不在rq里
    // 所以proc对应的run_link是空的，不应指向某个rq
    // (因为如果指向某个rq，就说明proc已经在rq里了
    // 既然已经在rq，为什么还要加入呢？说明此时出现了bug)
    assert(list_empty(&(proc->run_link)));
    // 把proc加入到rq->run_list队列的末尾
    // 其实就是list类的entry，list类所有成员都通过list_entry_t来定位
    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++;
}

// 将进程proc从RR调度算法的运行队列rq中删除
static void RR_dequeue(struct run_queue *rq, struct proc_struct *proc)
{
    // 同样需要保证proc对应的run_link不为空(保证proc在某个rq中)
    // 然后保证proc对应的run_link指向的rq就是当前的rq
    // 这样就确认了proc在当前的rq里
    assert(!list_empty(&(proc->run_link)) && proc->rq == rq);

    // 删掉对应的proc的entry
    list_del_init(&(proc->run_link));
    rq->proc_num--;
}

// 选择下一个要运行的进程
// 选择进程但不将从队列中移除
static struct proc_struct *RR_pick_next(struct run_queue *rq)
{
    // 直接选择rq中的下一个
    list_entry_t *le = list_next(&(rq->run_list));
    if (le != &(rq->run_list))
    {
        return le2proc(le, run_link);
    }
    return NULL;
}

// 该函数会在时间中断处理例程中被调用，以减小当前运行进程的剩余时间片。
// 若时间片耗尽，则设置当前进程的need_resched为1。
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;
    }
}

因此，在调度时机到达时，先调用schedule函数调度，RR算法调用RR_pick_next函数选出下一个rq中的进程，然后调用proc_run来切换到对应的上下文上运行，当时间片用完或主动挂起就重复此过程。

0X02 实现 Stride Scheduling 调度算法

uCore的Round-Robin算法可以保证每个进程得到的CPU资源是相等的，但我们希望调度器能够更加智能的为每个进程分配合理的CPU资源，让每个进程得到的时间资源与它们的优先级成正比关系。而Stride Scheduling调度算法就是这样的一种典型而简单的算法。

其中，该算法的有如下几个特点：

• 实现简单
• 可控性：可以证明Stride Scheduling对进程的调度次数正比于其优先级
• 确定性：在不考虑计时器事件的情况下，整个调度机制都是可预知和重现的。

而该算法的基本思想如下：

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

不过这里有个点需要注意一下，随着进程的执行，stride属性值会一直在增加，那么就有可能造成整数溢出。当stride溢出后，不当的比较可能会造成错误。那应该怎么做呢？

这里有一个结论：STRIDE_MAX – STRIDE_MIN <= PASS_MAX == BIG_STRIDE / 1 （注意最小的Priority为1）。所以我们只要将BIG_STRIDE限制在某个范围内，即可保证任意两个stride之差都会在机器整数表示的范围之内。

首先，需要实现其初始化函数

static void stride_init(struct run_queue *rq) 
{
    // 注意这里不要使用skew_heap_init(rq->lab6_run_pool)
    // 因为rq->lab6_run_pool只是一个指针，而不是一个对象。
    list_init(&(rq->run_list));
    
    // 堆初始化为空
    rq->lab6_run_pool = NULL;
    rq->proc_num = 0;
}

stride_enqueue和stride_dequeue与RR算法相差不大，主要就是通过一个堆来管理进程的调度权。由于堆比较简单，所以不再赘诉。

// 插入进程
static void stride_enqueue(struct run_queue *rq, struct proc_struct *proc) 
{
    // 按照stride的大小插入到堆中
    rq->lab6_run_pool = skew_heap_insert(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
    // 如果是超时需要重置时间片
    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 stride_dequeue(struct run_queue *rq, struct proc_struct *proc) 
{
    rq->lab6_run_pool = skew_heap_remove(rq->lab6_run_pool, &(proc->lab6_run_pool), proc_stride_comp_f);
    rq->proc_num --;
}

// 比较两个进程的优先级，用于调度
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;
}

// 选择下一个进程用于调度
static struct proc_struct *stride_pick_next(struct run_queue *rq)
{

    skew_heap_entry_t *she = rq->lab6_run_pool;
    if (she != NULL)
    {
        struct proc_struct *p = le2proc(she, lab6_run_pool);
        // 这里需要防止溢出，就使用之前的公式
        p->lab6_stride += BIG_STRIDE / p->lab6_priority;
        return p;
    }
    return NULL;
}

0X03 总结

通过这个lab6，我们学习了以下内容:

• 进程调度时机
• 进程调度具体过程
• 进程调度算法的实现